Elyz/kernel/docs/memory/allocator.md

Slab-аллокатор: куча ядра

Концептуальная модель

SlabAllocator — это глобальный аллокатор кучи для ядра. Rust-программы используют alloc::vec::Vec, alloc::boxed::Box и т.д. — все они в конечном счёте вызывают GlobalAlloc::alloc().

Стратегия

Для маленьких блоков (≤ 2048 байт) — slab lists: предварительно нарезанные блоки фиксированного размера.

Для больших блоков (> 2048 байт) — freelist больших блоков: освобождённые блоки переиспользуются.

Если ни там, ни там нет — bump allocation: последовательная раздача из заранее выделенного региона.

Запрос alloc(32 байта):
  1. list_index(32) = 2 (BLOCK_SIZES[2] = 32)
  2. list_heads[2] есть свободный блок?
     - Да: отдаём его, заменяем голову списка
     - Нет: bump-аллокация блока размером 32 (fallback_alloc)

Запрос alloc(4096 байт):
  1. list_index(4096) = None (максимум 2048)
  2. large_block_free есть блок ≥ 4096?
     - Да: отдаём
     - Нет: bump-аллокация

Структуры данных

Slab списки — list_heads

const BLOCK_SIZES: &[usize] = &[8, 16, 32, 64, 128, 256, 512, 1024, 2048];

struct ListNode {
    next: Option<&'static mut ListNode>,
}

pub struct SlabAllocator {
    list_heads: [Option<&'static mut ListNode>; BLOCK_SIZES.len()],  // 9 списков
    large_block_free: Option<&'static mut LargeBlockNode>,
    heap_start: usize,
    heap_end: usize,
    next_bump: usize,
}

LargeBlockNode — для блоков > 2048 байт

struct LargeBlockNode {
    size: usize,
    next: Option<&'static mut LargeBlockNode>,
}

Инициализация: init(start, size)

pub fn init(&mut self, start: usize, size: usize) {
    self.heap_start = start;
    self.next_bump = start;
    self.heap_end = start + size;
}

Вызывается в kmain() после настройки page table для области 0xFFFF_9000_0000_0000.

GlobalAlloc — реализация

alloc(layout)

unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
    let mut allocator = self.lock();
    match SlabAllocator::list_index(&layout) {
        Some(index) => {
            // 1. Пробуем slab list
            match allocator.list_heads[index].take() {
                Some(node) => {
                    allocator.list_heads[index] = node.next.take();
                    node as *mut ListNode as *mut u8
                }
                None => {
                    // 2. Нет в slab — bump alloc целого блока
                    let block_size = BLOCK_SIZES[index];
                    allocator.fallback_alloc(
                        Layout::from_size_align(block_size, block_size).unwrap()
                    )
                }
            }
        }
        None => allocator.fallback_alloc(layout) // > 2048
    }
}

fallback_alloc(layout)

fn fallback_alloc(&mut self, layout: Layout) -> *mut u8 {
    let size = layout.size().max(layout.align());

    // 1. Пробуем large block free list (для > 2048)
    if size > 2048 {
        // поиск по large_block_free
        while let Some(ref mut node) = *field {
            if node.size >= size {
                // отдаём, удаляем из списка
                return node as *mut u8;
            }
            field = &mut node.next;
        }
    }

    // 2. Bump alloc
    let alloc_start = (self.next_bump + layout.align() - 1) & !(layout.align() - 1);
    let alloc_end = alloc_start.checked_add(layout.size())?;
    if alloc_end > self.heap_end {
        null_mut()  // OOM
    } else {
        self.next_bump = alloc_end;
        alloc_start as *mut u8
    }
}

dealloc(ptr, layout)

unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
    let mut allocator = self.lock();
    match SlabAllocator::list_index(&layout) {
        Some(index) => {
            // Добавляем в slab list (переиспользование)
            let new_node = ListNode { next: allocator.list_heads[index].take() };
            let new_node_ptr = ptr as *mut ListNode;
            unsafe { new_node_ptr.write(new_node); }
            allocator.list_heads[index] = Some(&mut *new_node_ptr);
        }
        None => {
            // Добавляем в large block free list
            let new_node = LargeBlockNode {
                size: layout.size().max(layout.align()),
                next: allocator.large_block_free.take(),
            };
            let new_node_ptr = ptr as *mut LargeBlockNode;
            unsafe { new_node_ptr.write(new_node); }
            allocator.large_block_free = Some(&mut *new_node_ptr);
        }
    }
}

Важно: layout.size() должен быть ≥ size_of::<ListNode>(), чтобы освобождённый блок мог хранить указатели списка. Гарантируется, потому что наименьший BLOCK_SIZE (8) ≥ size_of::<Option<&'static mut ListNode>> (8 байт на 64-bit).

Locked — примитивная spinlock-обёртка

pub struct Locked<A> {
    inner: UnsafeCell<A>,
    lock: AtomicBool,
}

• lock() — spin-wait с CAS + hint::spin_loop().
• LockedGuard — RAII guard, при Drop отпускает блокировку.
• unsafe impl Sync — потому что lock() гарантирует взаимное исключение.

Используется не только для аллокатора, но и для PMM, serial port, VMM KERNEL_SPACE и других глобальных структур.

Глобальный аллокатор

#[global_allocator]
pub static ALLOCATOR: Locked<SlabAllocator> = Locked::new(SlabAllocator::new());

Этот static перехватывает все вызовы alloc::alloc::alloc(), делая возможным использование Vec, Box, String и т.д. в ядре.

Heap init в kmain()

let heap_start = 0xFFFF_9000_0000_0000;
let heap_size = 8 * 1024 * 1024;  // 8 MiB
// Предварительно map'им все страницы кучи
for i in (0..heap_size).step_by(4096) {
    let frame = mem::pmm::alloc_frame().expect("OOM");
    p4.map_page(VirtAddr(heap_start + i), frame, flags);
}
// Инициализируем аллокатор
allocator::ALLOCATOR.lock().init(heap_start as usize, heap_size);

Почему slab?

1. Скорость: alloc/dealloc — O(1) для малых блоков.
2. Нет фрагментации: блоки фиксированного размера.
3. Локальность: блоки одного размера рядом в памяти.
4. Простота: ~180 строк кода.