268 lines
10 KiB
Markdown
268 lines
10 KiB
Markdown
# Buddy Allocator: `buddy.rs`
|
||
|
||
## Концептуальная модель
|
||
|
||
Buddy-аллокатор — это алгоритм управления памятью, который:
|
||
- Делит память на блоки размером `2^order` страниц.
|
||
- Каждый блок может быть либо свободен, либо занят.
|
||
- При освобождении блок объединяется (coalesce) с соседом (buddy),
|
||
если тот тоже свободен, образуя блок вдвое большего размера.
|
||
|
||
```
|
||
Пример: порядок 0 (1 страница), порядок 1 (2 страницы), порядок 2 (4 страницы)
|
||
|
||
Order 2: [ 0-3 ] [ 4-7 ] [ 8-11 ]
|
||
Order 1: [ 0-1 ][ 2-3 ] [ 4-5 ][ 6-7 ] [ 8-9 ][ 10-11 ]
|
||
Order 0: [0][1][2][3] [4][5][6][7] [8][9][10][11] [12][13][14][15]
|
||
^
|
||
buddy-пара: (0,1), (2,3), (4,5)...
|
||
buddy(i) = i XOR (1 << order)
|
||
```
|
||
|
||
## Intrusive List (список в самих страницах)
|
||
|
||
Вместо отдельной структуры данных для списков свободных блоков,
|
||
Elyz использует **intrusive linked list** — указатели хранятся прямо
|
||
внутри свободных физических страниц:
|
||
|
||
```
|
||
Страница (4 KiB):
|
||
┌──────────────┐
|
||
│ next: usize │ ← указатель на следующую свободную страницу
|
||
├──────────────┤
|
||
│ prev: usize │ ← указатель на предыдущую свободную страницу
|
||
├──────────────┤
|
||
│ │
|
||
│ (не занято) │
|
||
│ │
|
||
└──────────────┘
|
||
```
|
||
|
||
Для доступа к странице по индексу используется HHDM:
|
||
```rust
|
||
fn page_virt(&self, idx: usize) -> VirtAddr {
|
||
PhysAddr(self.base_phys + idx as u64 * 4096).to_virt()
|
||
}
|
||
```
|
||
|
||
## Структура BuddyAllocator
|
||
|
||
```rust
|
||
pub struct BuddyAllocator {
|
||
free_heads: [usize; MAX_ORDER + 1], // головы списков для каждого порядка
|
||
total_pages: usize, // всего страниц в управлении
|
||
free_pages: usize, // свободно страниц
|
||
base_phys: u64, // физический адрес начала
|
||
}
|
||
```
|
||
|
||
- `MAX_ORDER = 11` — максимальный порядок (2^11 = 2048 страниц = 8 MiB).
|
||
- `NEXT_SENTINEL = usize::MAX` — маркер конца списка.
|
||
- `free_heads[order]` — индекс первой свободной страницы порядка `order`.
|
||
|
||
## Операции со списком
|
||
|
||
### flist_push(order, idx) — добавить в голову
|
||
|
||
```rust
|
||
fn flist_push(&mut self, order: usize, idx: usize) {
|
||
let head = self.free_heads[order];
|
||
// Устанавливаем: node.next = head, node.prev = SENTINEL
|
||
self.write_node(idx, head, NEXT_SENTINEL);
|
||
if head != NEXT_SENTINEL {
|
||
// head.prev = idx
|
||
self.write_node(head, self.read_next(head), idx);
|
||
}
|
||
self.free_heads[order] = idx;
|
||
}
|
||
```
|
||
|
||
### flist_remove(order, idx) — удалить из списка
|
||
|
||
```rust
|
||
fn flist_remove(&mut self, order: usize, idx: usize) {
|
||
let next = self.read_next(idx);
|
||
let prev = self.read_prev(idx);
|
||
// Очищаем указатели удаляемого узла
|
||
self.write_node(idx, NEXT_SENTINEL, NEXT_SENTINEL);
|
||
if prev != NEXT_SENTINEL {
|
||
self.write_node(prev, next, self.read_prev(prev));
|
||
} else {
|
||
self.free_heads[order] = next; // удалили голову
|
||
}
|
||
if next != NEXT_SENTINEL {
|
||
self.write_node(next, self.read_next(next), prev);
|
||
}
|
||
}
|
||
```
|
||
|
||
### flist_pop(order) — извлечь из головы
|
||
|
||
```rust
|
||
fn flist_pop(&mut self, order: usize) -> Option<usize> {
|
||
let head = self.free_heads[order];
|
||
if head == NEXT_SENTINEL { return None; }
|
||
self.flist_remove(order, head);
|
||
Some(head)
|
||
}
|
||
```
|
||
|
||
## Инициализация: `new(total_pages, base_phys)`
|
||
|
||
Стратегия: разбить весь диапазон на максимально возможные блоки.
|
||
|
||
```rust
|
||
pub fn new(total_pages: usize, base_phys: u64) -> Self {
|
||
let mut this = Self {
|
||
free_heads: [NEXT_SENTINEL; MAX_ORDER + 1],
|
||
total_pages, free_pages: 0, base_phys,
|
||
};
|
||
if total_pages == 0 { return this; }
|
||
|
||
let mut idx = 0;
|
||
while idx < total_pages {
|
||
let remaining = total_pages - idx;
|
||
// Максимальный порядок с учётом выравнивания и остатка
|
||
let align_order = /* макс порядок по выравниванию idx */;
|
||
let size_order = /* макс порядок по remaining */;
|
||
let order = MAX_ORDER.min(align_order).min(size_order);
|
||
let block_size = 1usize << order;
|
||
this.flist_push(order, idx);
|
||
this.free_pages += block_size;
|
||
idx += block_size;
|
||
}
|
||
this
|
||
}
|
||
```
|
||
|
||
### Как определяются align_order и size_order
|
||
|
||
- `align_order`: если `idx == 0` — `MAX_ORDER`; иначе `(idx.trailing_zeros()).min(MAX_ORDER)`.
|
||
Чем больше нулевых битов в idx, тем выше порядок выравнивания.
|
||
- `size_order`: `(64 - 1) - remaining.leading_zeros()` — максимальная степень двойки
|
||
≤ remaining.
|
||
|
||
## Аллокация: `alloc(order)`
|
||
|
||
```rust
|
||
pub fn alloc(&mut self, order: usize) -> Option<usize> {
|
||
// 1. Ищем первый непустой список начиная с order
|
||
let found_order = (order..=MAX_ORDER)
|
||
.find(|&o| self.free_heads[o] != NEXT_SENTINEL)?;
|
||
|
||
// 2. Извлекаем блок из found_order
|
||
let block_idx = self.flist_pop(found_order);
|
||
self.free_pages -= 1 << found_order;
|
||
|
||
// 3. Разбиваем до нужного порядка (split)
|
||
let mut cur_order = found_order;
|
||
while cur_order > order {
|
||
cur_order -= 1;
|
||
let buddy_idx = block_idx + (1 << cur_order);
|
||
self.flist_push(cur_order, buddy_idx);
|
||
self.free_pages += 1 << cur_order;
|
||
}
|
||
|
||
Some(block_idx)
|
||
// Возвращается индекс первого блока
|
||
}
|
||
```
|
||
|
||
### Пример split
|
||
|
||
```
|
||
Запрос: order 1 (2 страницы)
|
||
Найден: order 3 (8 страниц, блок [0-7])
|
||
|
||
Шаг 1: cur_order = 3 → 2
|
||
buddy = 0 + 4 = 4
|
||
push(order=2, idx=4) — блок [4-7] в order 2
|
||
Шаг 2: cur_order = 2 → 1
|
||
buddy = 0 + 2 = 2
|
||
push(order=1, idx=2) — блок [2-3] в order 1
|
||
Результат: order=1, idx=0 — блок [0-1]
|
||
```
|
||
|
||
## Освобождение: `free(block_idx, order)` + coalesce
|
||
|
||
```rust
|
||
pub fn free(&mut self, mut block_idx: usize, mut order: usize) {
|
||
// Пытаемся объединить с buddy
|
||
while order < MAX_ORDER {
|
||
let buddy_idx = block_idx ^ (1 << order);
|
||
|
||
// Проверка: buddy в пределах памяти?
|
||
let buddy_end = buddy_idx.checked_add(1 << order)?;
|
||
if buddy_end > self.total_pages { break; }
|
||
|
||
// Buddy свободен?
|
||
if self.flist_contains(order, buddy_idx) {
|
||
// Удаляем buddy из его списка
|
||
self.flist_remove(order, buddy_idx);
|
||
self.free_pages -= 1 << order;
|
||
// Объединяем: block_idx = min(block_idx, buddy_idx)
|
||
block_idx = block_idx.min(buddy_idx);
|
||
order += 1;
|
||
} else {
|
||
break; // buddy занят, не можем объединить
|
||
}
|
||
}
|
||
|
||
// Добавляем объединённый блок в список
|
||
self.free_pages += 1 << order;
|
||
self.flist_push(order, block_idx);
|
||
}
|
||
```
|
||
|
||
### Пример coalesce
|
||
|
||
```
|
||
Освобождаем: order 0, idx = 0
|
||
Блок [0] возвращается в список order 0.
|
||
|
||
Проверка: buddy(0, order 0) = 0 XOR 1 = 1
|
||
Если idx=1 тоже свободен в order 0:
|
||
- Удаляем idx=1 из order 0
|
||
- block_idx = min(0, 1) = 0
|
||
- order = 1
|
||
- Проверка: buddy(0, order 1) = 0 XOR 2 = 2
|
||
Если idx=2 свободен в order 1:
|
||
- Удаляем idx=2 из order 1
|
||
- order = 2
|
||
- ...
|
||
```
|
||
|
||
## alloc_pages(page_count) — универсальная аллокация
|
||
|
||
```rust
|
||
pub fn alloc_pages(&mut self, page_count: usize) -> Option<(usize, usize)> {
|
||
let order = order_for(page_count);
|
||
self.alloc(order).map(|idx| (idx, order))
|
||
}
|
||
```
|
||
|
||
`order_for()` вычисляет `ceil(log2(page_count))`.
|
||
|
||
## Вспомогательные функции
|
||
|
||
- `free_pages()` / `total_pages()` — геттеры.
|
||
- `is_exhausted()` — `free_pages == 0`.
|
||
- `stats()` — возвращает `[(order, count)]` для каждого порядка (количество
|
||
свободных блоков). Используется для отладки.
|
||
- `flist_contains(order, idx)` — проверка, есть ли блок в списке
|
||
(проверяет `prev != NEXT_SENTINEL` или `head == idx`).
|
||
|
||
## Почему Intrusive List?
|
||
|
||
1. **Zero overhead**: не нужно отдельной аллокации для списков.
|
||
2. **O(1)**: push/pop/remove — все O(1) операции.
|
||
3. **Константная память**: аллокатор не потребляет дополнительной памяти
|
||
сверх управляемых страниц.
|
||
4. **Кэш-дружественность**: доступ к next/prev обращается к той же странице,
|
||
которая будет выделена.
|
||
|
||
## Где используется
|
||
|
||
- `PMActor` содержит `BuddyAllocator` для управления своим диапазоном.
|
||
- Прямые тесты в `kmain()` демонстрируют all/alloc/free/coalesce/exhaustion.
|