Elyz/kernel/docs/memory/buddy.md

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:

fn page_virt(&self, idx: usize) -> VirtAddr {
    PhysAddr(self.base_phys + idx as u64 * 4096).to_virt()
}

Структура BuddyAllocator

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) — добавить в голову

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) — удалить из списка

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) — извлечь из головы

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)

Стратегия: разбить весь диапазон на максимально возможные блоки.

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)

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

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) — универсальная аллокация

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.