147 lines
5.0 KiB
Markdown
147 lines
5.0 KiB
Markdown
# CNode: таблица capability: `mod.rs`
|
||
|
||
## Концептуальная модель
|
||
|
||
**CNode** (Capability Node) — это массив слотов, каждый из которых
|
||
может хранить один capability. Это аналог файловой таблицы в Unix,
|
||
но для capabilities.
|
||
|
||
```
|
||
CNode {
|
||
slots: Vec<Locked<CNodeSlot>>
|
||
}
|
||
|
||
CNodeSlot {
|
||
cap: Capability,
|
||
parent_idx: Option<usize>, // индекс родительского слота
|
||
}
|
||
```
|
||
|
||
## Инициализация
|
||
|
||
```rust
|
||
pub fn new(size: usize) -> Self {
|
||
let mut slots = Vec::with_capacity(size);
|
||
for _ in 0..size {
|
||
slots.push(Locked::new(CNodeSlot {
|
||
cap: Capability::empty(),
|
||
parent_idx: None,
|
||
}));
|
||
}
|
||
Self { slots }
|
||
}
|
||
```
|
||
|
||
Все слоты изначально пустые (`Capability::empty()`).
|
||
|
||
## Операции
|
||
|
||
### insert(slot, cap) — вставка
|
||
|
||
```rust
|
||
pub fn insert(&self, slot: usize, cap: Capability) -> Result<(), &'static str> {
|
||
if slot >= self.slots.len() { return Err("Index out of bounds"); }
|
||
let mut s = self.slots[slot].lock();
|
||
s.cap = cap;
|
||
Ok(())
|
||
}
|
||
```
|
||
|
||
Простая вставка без проверки (перезаписывает существующий).
|
||
|
||
### mint(src, dest, relation, rights) — создание потомка
|
||
|
||
```rust
|
||
pub fn mint(&self, src: usize, dest: usize, relation: Relation, rights: CapRights) -> Result<(), &'static str>
|
||
```
|
||
|
||
**Валидация:**
|
||
- src и dest в пределах массива.
|
||
- src != dest (дедлок не имеет смысла, но блокировка была бы корректна).
|
||
- src содержит валидный capability.
|
||
- src имеет GRANT.
|
||
|
||
**Процесс:**
|
||
1. Захват блокировок в порядке возрастания индекса (lock ranking).
|
||
2. Вычисление `final_rights = src.rights & rights`.
|
||
3. Копирование Capability в dest с новыми правами и relation.
|
||
4. Установка `parent_idx = Some(src)`.
|
||
|
||
### revoke(slot_idx) — отзыв
|
||
|
||
```rust
|
||
pub fn revoke(&self, slot_idx: usize) -> Result<(), &'static str>
|
||
```
|
||
|
||
Каскадное удаление:
|
||
|
||
```
|
||
revoke_internal(slot_idx):
|
||
│
|
||
├── 1. Поиск потомков:
|
||
│ for i in 0..slots.len():
|
||
│ if slots[i].parent_idx == Some(slot_idx):
|
||
│ revoke_internal(i) ← рекурсивно!
|
||
│
|
||
├── 2. Уничтожение себя:
|
||
│ cap = Capability::empty()
|
||
│ parent_idx = None
|
||
│ token = old_token_sig
|
||
│
|
||
└── 3. Отправка token в очередь:
|
||
if token != 0 && token != 0xDEAD_BEEF:
|
||
MMU_REVOCATION_QUEUE.push(token)
|
||
```
|
||
|
||
**Почему нет блокировок при рекурсии?**
|
||
- На каждом шаге проверка `is_child` захватывает и отпускает блокировку.
|
||
- Рекурсивный вызов происходит **после** освобождения блокировки.
|
||
- Это предотвращает взаимоблокировки.
|
||
|
||
**Фильтр токенов:**
|
||
- `token == 0`: пустой/невалидный capability.
|
||
- `token == 0xDEAD_BEEF`: сырой Untyped (для тестов/отладки).
|
||
- Эти токены не отправляются в очередь (бессмысленно).
|
||
|
||
### get_cap(slot) — чтение
|
||
|
||
```rust
|
||
pub fn get_cap(&self, slot: usize) -> Option<Capability> {
|
||
self.slots.get(slot).map(|s| s.lock().cap)
|
||
}
|
||
```
|
||
|
||
## Lock Ranking — детали
|
||
|
||
```rust
|
||
let (src_slot, dest_slot) = if src < dest {
|
||
_guard_low = self.slots[src].lock(); // меньший → первый
|
||
_guard_high = self.slots[dest].lock(); // больший → второй
|
||
} else {
|
||
_guard_low = self.slots[dest].lock();
|
||
_guard_high = self.slots[src].lock();
|
||
};
|
||
```
|
||
|
||
**Причина:** если поток A делает mint(5, 10), а поток B делает mint(10, 5),
|
||
без lock ranking они могут взаимно заблокироваться:
|
||
- A: lock(5) → ждёт lock(10)
|
||
- B: lock(10) → ждёт lock(5)
|
||
|
||
С lock ranking:
|
||
- A: lock(5) → lock(10)
|
||
- B: lock(5) → ждёт... → дождался → lock(10)
|
||
|
||
## Интеграция с событиями
|
||
|
||
После `revoke()`, токен попадает в `MMU_REVOCATION_QUEUE` (см.
|
||
`events.rs`). VMM обрабатывает очередь в `process_pending_revocations()`.
|
||
|
||
## Особенности реализации
|
||
|
||
1. **Vec<Locked<CNodeSlot>>**: каждый слот — отдельная spinlock-ячейка.
|
||
Это позволяет параллельно читать разные слоты.
|
||
2. **`pub slots`**: прямой доступ к слоту возможен (для тестов).
|
||
3. **panic на overflow**: если очередь отзыва переполнена — паника.
|
||
Это критический сбой подсистемы ресурсов.
|