В прошлой части мы загрузили своё мобильное ядро, вывели "Hello world" в UART и нарисовали квадратик на экране.
В этой части я покажу, как улучшилось ядро за это время: поддержка новых устройств (запуск и отладка в QEMU и Raspberry Pi 5), разбиение на модули, и, наконец, полноценный менеджер памяти. В этом нам очень поможет система типов Rust.
Содержание
Устройство модели памяти в ARM64
Как и x86, ARM64 имеет механизм изоляции памяти через трансляцию виртуальных адресов в физические. Это обеспечивает аппаратный контроль прав доступа и изоляцию памяти процессов. Ниже, под спойлером, пробежимся по ключевым регистрам — без паники, это первый и последний раздел с таблицами.
Краткие теоретические сведения о трансляции адересов в ARM64
Структура 64-битного адреса:
Биты | 63:48 | 47:39 | 38:30 | 29:21 | 20:12 | 11:0 |
|---|---|---|---|---|---|---|
Назначение | Sign extend | индекс L0 (9 бит) | индекс L1 (9 бит) | индекс L2 (9 бит) | индекс L3 (9 бит) | offset страницы (12 бит) |
Покрытие | — | 512 ГБ | 1 ГБ | 2 МБ | 4 КБ | внутри страницы |
Работает это следующим образом.
Специальный регистр — TTBR (Translation Table Base Register), хранит физический адрес корневой таблицы страниц (таблица уровня L0). Адрес корневой таблицы должен быть выровнен на 4 КБ. Корневая таблица содержит 512 записей по 64 бита.
Биты транслируемого адреса (индекс L0) содержат индекс записи в этой таблице.
Объединяя адрес корневой таблицы и сдвиг, получаем адрес записи. Часть битов отвечает за настройки, а часть — выровненный адрес таблицы следующего уровня.
Запись в таблице L0 / L1 / L2 (Table descriptor)
Биты | Название | Значение / описание |
|---|---|---|
0 | Valid | Валидность записи |
1 | Table/Block | 1 — указатель на таблицу следующего уровня; 0 — блок (только L1/L2) |
11:2 | Ignored | Игнорируется |
47:12 | Next-level Page Address | Физический адрес таблицы следующего уровня |
49:48 | Ignored | Игнорируется |
50 | Privileged Execute Never | Запрет исполнения для нижележащих таблиц (Ядро) |
51 | Unprivileged Execute Never | Запрет исполнения для нижележащих таблиц (Пользователь) |
53:52 | Access Permissions | Запрет на чтение/запись пользователю/ядру |
54 | Non-secure | Security-атрибут |
63:55 | Ignored / RES0 | Игнорируется |
Таблицы L0, L1, L2 имеют одинаковую структуру записей. Разница в том, что записи L0 могут быть только указателями на таблицу следующего уровня, а записи L1 и L2 могут также являться блоками. Если запись L1 — блок, то она покрывает 1 ГБ пространства, образуя 2-уровневую адресацию. Запись-блок L2 покрывает 2 МБ (3-уровневая адресация).
Запись в таблице L3 или блок L1/L2
Биты | Название | Значение / описание |
|---|---|---|
0 | Valid | Валидность записи |
1 | Block/Page | Запись указывает на страницу (L3) |
11:2 | Атрибуты | AttrIndx (4:2, MAIR), AP (7:6), SH (9:8), AF (10), NS (5), nG (11) |
47:12 | Output Address | Физический адрес страницы |
49:48 | Reserved | RES0 |
50 | Privileged Execute Never | Запрет исполнения (EL1) |
51 | Unprivileged Execute Never | З��прет исполнения (EL0) |
52 | Contiguous | Часть contiguous mapping |
53 | Dirty Bit Modifier | Управление битом "грязности" (dirty-bit механизм) |
54 | Guarded Page | Guarded memory (опционально) |
63:55 | Ignored / RES0 | Игнорируется |
Из полезного, в таблице L3 есть поля, управляющие видимостью доступов к памяти между ядрами процессора (Shareability), и индекс атрибута памяти MAIR.
Это максимальный уровень. При 4-уровневой адресации нам остаётся добавить к физическому адресу страницы сдвиг внутри страницы.
Если трансляция проходит успешно, то мы по некоторому виртуальному адресу получим доступ к физической памяти. Если нам не позволят это сделать права доступа, или для заданного адреса нет записи в таблице, то процессор выполнит переход к обработчику синхронного прерывания. Из специальных регистров можно будет извлечь подробную информацию о месте и причине возникновения прерывания.
Рассмотрим пример для адреса 0xFFFFFFC00AAAA678.
VA = 0xFFFFFFC00AAAA678 L0 = (VA >> 39) & 0x1FF = 0x1FF L1 = (VA >> 30) & 0x1FF = 0x100 L2 = (VA >> 21) & 0x1FF = 0x055 L3 = (VA >> 12) & 0x1FF = 0x0AA off = VA & 0xFFF = 0x678
MAIR (Memory Attribute Indirection Register)
Это 64-битный системный регистр, описывающий типы памяти. В нём упаковано 8 записей (каждый байт - описание одного типа памяти). Здесь поля каждого слота определяют, как CPU будет обрабатывать доступ к памяти. Мы сами конфигурируем эти слоты. Биты AttrIndx из страницы (блока) указывают на конкретный слот этого регистра.
Нам понадобится настроить две основные конфигурации:
Обычная память (normal): Normal (можно переупорядочить), cacheable (доступ через кэш), write-back (запись сперва идёт в кэш, а не в DRAM), с аллокацией при чтении и записи (создание кэш-строки).
Память устройств (device, доступ к регистрам MMIO)
non-Gathering (не объединять несколько записей в одну),
non-Reordering (не переупорядочивать доступы),
Early write acknowledgement (считать запись завершенной ра��ьше, чем она реально дошла).
TCR (Translation Control Register)
Это системный регистр, определяющий геометрию и правила трансляции адресов.
Биты | Поле | Назначение |
|---|---|---|
5:0 | T0SZ | Размер VA (TTBR0): 64 − VA_bits |
9:8 | IRGN0 | Inner cache (TTBR0) |
11:10 | ORGN0 | Outer cache (TTBR0) |
13:12 | SH0 | Shareability (TTBR0) |
15:14 | TG0 | Размер гранулы (TTBR0) |
21:16 | T1SZ | Размер VA (TTBR1): 64 − VA_bits |
25:24 | IRGN1 | Inner cache (TTBR1) |
27:26 | ORGN1 | Outer cache (TTBR1) |
29:28 | SH1 | Shareability (TTBR1) |
31:30 | TG1 | Размер гранулы (TTBR1) |
34:32 | IPS | Размер физического адреса |
36 | AS | ASID size (0=8, 1=16 бит) |
37 | TBI0 | Top Byte Ignore (TTBR0) |
38 | TBI1 | Top Byte Ignore (TTBR1) |
39 | HA | HW Access Flag |
40 | HD | HW Dirty Flag |
Для нашей настройки важны T0SZ, TG, IPS. Половина битов относится к TTBR0, вторая — к TTBR1. Почему этих регистров два, выясним позже.
Здесь нас интересуют поля:
Размер VA — описывает разрядность виртуального адреса (от 36 до 48 бит).
Размер физического адреса — описывает разрядность физического адреса (от 32 до 52 бит).
Granule size — размер гранулы страницы. Выше мы описывали 4 КБ страницы, но на самом деле могут быть 16 КБ или даже 64 КБ страницы. Для блоков L1, L2 размер также будет другим. Поддержка режимов, отличных от 4 КБ, зависит от CPU.
SCTLR (System Control Register)
Этот регистр является главным рубильником включения виртуальной адресации. Он включает MMU, кэши и задаёт базовую модель выполнения.
Бит | Название | Назначение |
|---|---|---|
0 | MMU Enable | Включение MMU |
1 | Alignment Check | Проверка выравнивания доступов |
2 | Data Cache Enable | Включение кэша данных |
3 | Stack Alignment (EL1) | Проверка выравнивания стека (EL1) |
4 | Stack Alignment (EL0) | Проверка выравнивания стека (EL0) |
12 | Instruction Cache Enable | Включение кэша инструкций |
14 | DC ZVA Enable | Разрешение инструкции DC ZVA |
15 | User Access to CTR_EL0 | Доступ пользователя к CTR_EL0 |
19 | Write eXecute Never | Запрет исполнения для записываемых страниц |
24 | Endianness (EL0) | Порядок байт для EL0 |
25 | Endianness (EL1) | Порядок байт для EL1 |
В таблице — основные поля. Нас интересуют только 3 бита:
MMU Enable — включает виртуальную адресацию. Поэтому этот регистр должен включаться последним — когда в память уже записаны все таблицы и настроены остальные регистры. Иначе мы доступ потеряем.
Data Cache и Instruction Cache — названия говорят сами за себя; они включают кэширование для исполняемых инструкций и данных.
На этом с таблицами закончили — дальше пойдёт код и самое интересное.
Поддержка разных устройств
В прошлой части адрес загрузки ядра был захардкоджен, DTB-файл был зашит в файле сборки, не было возможности выбрать разные драйверы.
Чтобы решить эту проблему, я добавил специальный файл, описывающий параметры устройства.
Как он будет выглядеть для моего xiaomi lavender:
devices/spec/xiaomi-lavender.yaml:
device: name: Xiaomi Redmi Note 7 arch: aarch64 boot: dtb: /devices/dtb/sdm660-lavender.dtb format: android_boot_v1 offset: 0x40080000 base: 0x40000000 run: [ "fastboot boot target/build/boot.img" ]
Сама структура простая. Мы описываем архитектуру устройства (вдруг добавятся новые типы архитектур), параметры сборки: dtb файл, формат сборки образа, адрес загрузки и ожидаемый адрес начала RAM - чтобы правильно слинковать ядро.
Кроме того, я добавил два опциональных блока: run - сюда можно добавить команды для сборки, и debug - соответственно команды для отладки.
Подключить отладчик по протоколам отладки ARM к телефону не получится. Отлаживать, конечно, можно логами. Но как быть, когда даже они не отображаются?
Чтобы упростить себе задачу, я решил переключиться на QEMU. Хоть он и не моделирует ARM-архитектуру в точности, но цикл разработки на нем гораздо проще.
devices/spec/qemu-aarch64.yaml:
device: name: QEMU AArch64 arch: aarch64 boot: format: binary offset: 0x40200000 run: [ "qemu-system-aarch64 -machine virt -cpu cortex-a53 -m 512M -nographic -serial mon:stdio -d int,mmu,guest_errors -D qemu.log -kernel target/build/kernel.bin" ] debug: [ "qemu-system-aarch64 -machine virt -cpu cortex-a53 -m 512M -nographic -serial mon:stdio -kernel target/build/kernel.bin -S -gdb tcp::1234" ]
Формат здесь — binary, то есть мы не оборачиваем ядро в Android boot image, и не прикрепляем DTB к ядру.
QEMU использует virtio — набор паравиртуализированных устройств, позволяющих эффективно эмулировать аппаратуру.
Позже мне захотелось что-то среднее: не такое сложное для разработки как телефон с его проприетарным SoC, но при этом не суррогат ARM-устройства. Вскоре после того, как мне пришла эта мысль, я побежал заказывать Raspberry Pi 5.
devices/spec/rpi5.yaml:
device: name: Raspberry Pi 5 arch: aarch64 boot: format: binary offset: 0x200000 run: - "cp target/build/kernel.bin target/build/kernel8.img"
К Raspberry Pi уже можно подключить отладчик (GDB/LLDB) через интерфейс SWD (Serial Wire Debug) с помощью OpenOCD.
На практике при работе с менеджером памяти ошибки сыпались одна за другой — Page Fault, Data Abort, и прочие радости жизни в bare-metal. Чтобы хоть как-то понимать, что происходит, я временно настроил вектор обработки исключений — минимальный обработчик, который просто выводит в UART информацию о причине и адресе падения. Полноценную обработку прерываний мы реализуем в следующей части, а на этом этапе даже такой костыль спасал от слепой отладки.
Для кастомизации с��стемы сборки в Rust-проектах делают специальный модуль, который по соглашению называется xtask. В нем мы получим из командной строки путь к спеке и сможем сформировать нужную команду сборки для cargo. Приводить код системы сборки тут не буду. Его можно найти в файле xtask/src/main.rs.
Модуль xtask парсит YAML-спеку, собирает ядро через cargo build --target aarch64-unknown-none, конвертирует ELF в бинарник (cargo objcopy), и при необходимости упаковывает в Android Boot Image. Для формата binary достаточно одного kernel.bin, а для android_boot_v1/v2 — ещё сжатие в gzip и оборачивание через mkbootimg.
В итоге мы собираем проект следующим образом:
cargo xtask build devices/spec/qemu-aarch64.yaml --run
Новая реализация точки входа
Мы разобрались с теорией виртуальной адресации, теперь пора приступить к реализации.
arch/aarch64/src/start.rs:
// Используем символы из linker.ld unsafe extern "C" { static _stack_top: u8; static _kernel_start: u8; static _bss_start: u8; static _bss_end: u8; } #[unsafe(no_mangle)] #[unsafe(naked)] pub extern "C" fn _start() -> () { naked_asm!( // Сохраняем DTB (x0) в callee-saved регистре "mov x19, x0", // Проверяем EL "mrs x0, CurrentEL", "cmp x0, #0x8", // EL2? "b.ne 1f", // если не EL2, то идем сразу в EL1 // Обработчик EL2 // HCR_EL2: EL1 в AArch64 "mov x0, #(1 << 31)", "msr hcr_el2, x0", // Отключаем ловушки SIMD/FP "mov x0, #0x33ff", "msr cptr_el2, x0", // SPSR_EL2: возврат в EL1h, DAIF masked "mov x0, #0x3c5", "msr spsr_el2, x0", "adr x0, 1f", "msr elr_el2, x0", "eret", // Обработчик EL1 "1:", // Инициализация SP_EL1 "msr spsel, #1", "adrp x1, {stack_top}", "add x1, x1, #:lo12:{stack_top}", "mov sp, x1", // Включаем FP/SIMD "mrs x0, cpacr_el1", "orr x0, x0, #(0x3 << 20)", "msr cpacr_el1, x0", "isb", // Очистка BSS "adrp x0, {bss_start}", "add x0, x0, #:lo12:{bss_start}", "adrp x1, {bss_end}", "add x1, x1, #:lo12:{bss_end}", "cmp x0, x1", "b.ge 11f", "10:", "str xzr, [x0], #8", "cmp x0, x1", "b.lt 10b", "11:", // Восстанавливаем DTB "mov x0, x19", // Переход в Rust "b {early_main}", // Если вернулись — уходим в WaitForEvent "msr daifset, #0b0010", "20:", "wfe", "b 20b", bss_start = sym _bss_start, bss_end = sym _bss_end, stack_top = sym _stack_top, early_main = sym early_main, ) }
Код выше немного усовершенствован, по сравнению с предыдущей реализацией. Некоторые устройства (например, Raspberry Pi) могут передавать управление в режиме EL2 (гипервизор). Наше ядро будет работать в режиме EL1. Поэтому в начале мы смотрим в системный регистр CurrentEL. Если мы оказались в EL2, то спускаемся в EL1. Дальше просто: настраиваем стек, включаем блоки FP/SIMD, очищаем область неинициализированных переменных и переходим к Rust-коду.
Кстати, в режиме EL2 используется аналогичный механизм управления памятью. Только если здесь мы будем распределять память между пользовательскими процессами, то в режиме гипервизора память распределяется между гостевыми ОС.
/// Ранняя инициализация ядра fn early_main(dtb: usize) { // Парсим DTB let device_tree = match DeviceTree::from_ptr(dtb) { Ok(tree) => tree, Err(_) => return, }; // Извлекаем из DTB информацию о регионах памяти. let memory_layout = match build_memory_layout(&device_tree) { Ok(m) => m, Err(_) => return, }; // ... }
Данные о доступной памяти мы будем брать из DTB-файлов. Кроме того, нужно собрать информацию об остальных занятых участках памяти.
arch/aarch64/src/memory/setup.rs:
unsafe extern "C" { /** Код ядра */ static _text_start: u8; static _text_end: u8; /** Статика ядра */ static _rodata_start: u8; static _rodata_end: u8; /** Данные ядра */ static _rw_start: u8; static _rw_end: u8; } pub(crate) struct MemoryLayoutBuildError; pub(crate) fn build_memory_layout( dt: &DeviceTree, ) -> Result<MemoryLayout, MemoryLayoutBuildError> { let mut layout = MemoryLayout::new(); // Извлекаем регионы памяти из DTB let ram_regions = find_ram_regions(dt).ok_or(MemoryLayoutBuildError)?; for ram_region in ram_regions { layout.add(MemoryRegion::new( RegionTag::Heap, ram_region.start(), ram_region.end(), KernelData::flags(), )); } // Device tree layout.add(MemoryRegion::new( RegionTag::Other, dt.base_address(), dt.base_address() + dt.size(), KernelRoData::flags(), )); unsafe { // Kernel секции layout.add(MemoryRegion::new_raw( RegionTag::Kernel, &_text_start, &_text_end, KernelText::flags(), )); layout.add(MemoryRegion::new_raw( RegionTag::Kernel, &_rw_start, &_rw_end, KernelData::flags(), )); layout.add(MemoryRegion::new_raw( RegionTag::Kernel, &_rodata_start, &_rodata_end, KernelRoData::flags(), )); Ok(layout) } }
Для справки, реализация MemoryLayout:
arch/aarch64/src/memory/layout.rs:
// Максимальное количество регионов памяти. pub const MAX_MEMORY_REGIONS: usize = 32; /// Тег типа региона памяти pub enum RegionTag { /// Код и данные ядра Kernel, /// Куча (свободная RAM) Heap, /// Memory-mapped I/O Mmio, /// Неизвестный/служебный регион Other, } /// Раскладка физической памяти ядра. pub struct MemoryLayout { /// Список регионов памяти. regions: Vec<MemoryRegion<PageAlignedAddress>, MAX_MEMORY_REGIONS>, } impl MemoryLayout { pub const fn new() -> Self { Self { regions: Vec::new(), } } pub fn add(&mut self, region: MemoryRegion<PageAlignedAddress>) { self.regions.push(region).expect("Too many memory regions"); } pub fn iter(&self) -> impl Iterator<Item = &MemoryRegion<PageAlignedAddress>> { self.regions.iter() }
MemoryLayout использует самописную реализацию Vec, которая размещает данные в массиве на стеке. Работа схожа с реализацией аналогичной коллекции из библиотеки heapless.
Таким образом пока мы можем обойтись без динамической памяти.
Управление физической памятью
Минимальная единица управления памятью — одна страница. В нашем случае — это 4 КБ. Нам нужно как-то вести учет, какие страницы выделены, а какие свободны.
Один из наиболее простых, но эффективных способов — хранить битовую карту.
Если использовать вектор значений типа u64, то один u64 может отслеживать 64 страницы, то есть 256 КБ. Получается достаточно экономно — по одному биту на 4 КБ страницу.
Для начала введем базовые типы - Frame, PhysicalAddress, AlignedPhysicalAddress. Мы будем использовать их при работе с физическим аллокатором. Здесь и дальше некоторые очевидные методы будут опущены для краткости кода. Полный код можно найти на GitHub по ссылке в конце статьи.
memory/src/frame.rs:
/// Номер фрейма (индекс страницы в физической памяти). pub struct Frame(usize); impl Frame { pub const fn new(number: usize) -> Self { Self(number) } pub const fn number(&self) -> usize { self.0 } }
Frame — основная сущность физического ал��окатора. По сути это индекс 4 КБ блока.
/// Адрес физической памяти pub struct PhysicalAddress(usize); impl PhysicalAddress { pub const fn new(address: usize) -> Self { Self(address) } pub const fn as_usize(self) -> usize { self.0 } pub const fn align_down(self, frame_size: usize) -> PageAlignedAddress { PageAlignedAddress::aligned_down(self) } pub const fn align_up(self, frame_size: usize) -> PageAlignedAddress { PageAlignedAddress::aligned_up(self) } } /// Выровненный физический адрес /// Гарантирует, что адрес выровнен на заданную границу pub struct AlignedPhysicalAddress<const SHIFT: u8>(usize); pub type PageAlignedAddress = AlignedPhysicalAddress<12>;
PhysicalAddress - семантически отвечает за работу с физическими адресами, то есть теми, которые указывают напрямую на данные в RAM.
AlignedPhysicalAddress - частный случай физического адреса, гарантирующий что адрес выровнен. Выравнивание (alignment) - это кратность адреса. Параметр SHIFT означает степень двойки. То есть 4 КБ = 2^12. Поскольку мы работаем с 4 КБ страницами, то часто будем использовать алиас PageAlignedAddress.
/// Битовая карта для отслеживания статуса выделения фреймов pub struct FrameBitmap { // Битовая карта для отслеживания занятых участков bitmap: Box<[u64]>, // Количество свободных фреймов free: usize, // Область памяти, которая управляется битовой картой target_region: MemoryRange<PageAlignedAddress>, // Фрейм начала [target_region] base_frame: Frame, } impl FrameBitmap { // Количество фреймов (битов), описываемых одной записью const BITS_PER_ENTRY: usize = size_of::<u64>() * 8; pub fn new(target_region: MemoryRange<PageAlignedAddress>) -> Self { // Считаем размер вектора - сколько понадобится для разметки региона памяти let entry_count = Self::calc_entry_count(&target_region); let bitmap = vec![0u64; entry_count].into_boxed_slice(); FrameBitmap { bitmap, free: target_region.frame_count(), base_frame: Frame::from(target_region.start()), target_region, } } fn calc_entry_count(region: &MemoryRange<PageAlignedAddress>) -> usize { region.frame_count().div_ceil(Self::BITS_PER_ENTRY) } // Вспомогательная функция для записи fn write<F: Fn(u64) -> u64>(&mut self, index: usize, update: F) { if index < self.bitmap.len() { self.bitmap[index] = update(self.bitmap[index]); } } // Вспомогательная функция для чтения fn read(&self, offset: usize) -> u64 { if offset < self.bitmap.len() { self.bitmap[offset] } else { u64::MAX // За пределами - считаем все биты занятыми } } // Помечает фрейм как выделенный pub fn set_unchecked(&mut self, frame: Frame) { // Вычисляем позицию фрейма в битовой карте. let pos = self.entry_pos(frame); let mask = 1u64 << pos.bit; let old_value = self.read(pos.word); if (old_value & mask) == 0 { // Помечаем фрейм как занятый и обновляем счетчик свободных фреймов self.write(pos.word, |v| v | mask); self.free = self.free.saturating_sub(1); } } }
Ещё пара методов: set_range_unchecked и alloc_contiguous.
impl FrameBitmap { /// Помечает область фреймов как выделенную pub fn set_range_unchecked(&mut self, from_inclusive: Frame, to_exclusive: Frame) { let from = from_inclusive.number(); let to = to_exclusive.number(); if from >= to { return; } let start = self.entry_pos(from_inclusive); let end = self.entry_pos(to_exclusive); let mut allocated_count = 0usize; if start.word == end.word { let mask = Self::mask_range(start.bit, end.bit); if mask != 0 { let old_value = self.read(start.word); // Считаем только новые биты (те, что были 0 и станут 1) let new_bits = mask & !old_value; allocated_count += new_bits.count_ones() as usize; self.write(start.word, |v| v | mask); } self.free = self.free.saturating_sub(allocated_count); return; } // Первое слово let first_mask = Self::mask_from(start.bit); let old_first = self.read(start.word); allocated_count += (first_mask & !old_first).count_ones() as usize; self.write(start.word, |v| v | first_mask); // Средние слова (полностью заполняем) for word_index in (start.word + 1)..end.word { let old_value = self.read(word_index); allocated_count += (!old_value).count_ones() as usize; self.write(word_index, |_| u64::MAX); } // Последнее слово if end.bit > 0 { let last_mask = Self::mask_until(end.bit); let old_last = self.read(end.word); allocated_count += (last_mask & !old_last).count_ones() as usize; self.write(end.word, |v| v | last_mask); } self.free = self.free.saturating_sub(allocated_count); } /// Выделяет до max_count смежных страниц. Возвращает (первый фрейм, количество выделенных). /// Алгоритм first-fit: находит первый свободный участок и выделяет /// максимально возможное количество смежных страниц (до max_count). pub fn alloc_contiguous(&mut self, max_count: usize) -> Option<(Frame, usize)> { if max_count == 0 || self.free == 0 { return None; } // Максимальный номер фрейма в регионе (эксклюзивная граница) let region_frame_count = self.target_region.frame_count(); let max_frame_num = self.base_frame.number() + region_frame_count; // Ищем первый свободный бит let mut word_idx = 0; while word_idx < self.bitmap.len() && self.bitmap[word_idx] == u64::MAX { word_idx += 1; } if word_idx >= self.bitmap.len() { return None; } // Находим первый свободный бит в этом слове let first_bit = (!self.bitmap[word_idx]).trailing_zeros() as usize; let start_frame_num = self.base_frame.number() + word_idx Self::BITS_PER_ENTRY + first_bit; // Проверяем, что первый свободный бит в пределах региона if start_frame_num >= max_frame_num { return None; } // Считаем последовательные свободные биты (до max_count), не выходя за границы региона let mut count = 0; let mut w = word_idx; let mut b = first_bit; while count < max_count && w < self.bitmap.len() { let word = self.bitmap[w]; while b < Self::BITS_PER_ENTRY && count < max_count { // Проверяем, не вышли ли за границу региона let current_frame_num = self.base_frame.number() + w Self::BITS_PER_ENTRY + b; if current_frame_num >= max_frame_num { // Достигли конца региона break; } if (word & (1u64 << b)) != 0 { // Бит занят — прерываем break; } count += 1; b += 1; } // Проверяем причину выхода из внутреннего цикла let current_frame_num = self.base_frame.number() + w * Self::BITS_PER_ENTRY + b; if current_frame_num >= max_frame_num { break; // Достигли конца региона } if b < Self::BITS_PER_ENTRY && (self.bitmap[w] & (1u64 << b)) != 0 { break; // Встретили занятый бит } w += 1; b = 0; } if count == 0 { return None; } // Помечаем биты как занятые let start_frame = Frame::new(start_frame_num); let end_frame = Frame::new(start_frame_num + count); self.set_range_unchecked(start_frame, end_frame); Some((start_frame, count)) } }
Выше приведены ключевые методы FrameBitmap. То есть это просто обёртка над динамическим массивом, в котором мы находим нужный бит и меняем его на единицу.
memory/src/frame_allocator.rs:
pub struct PhysicalFrameAllocator<L: LockCell<FrameBitmap>> { /// Управляемые регионы оперативной памяти. regions: Vec<L, MAX_REGIONS>, /// Индекс текущего региона для поиска свободных фреймов. current_region_index: usize, /// Номер следующего фрейма для выделения. next_frame_hint: AtomicUsize, } /// Помечает диапазон фреймов как занятый fn reserve_frames_exact( &self, from_inclusive: Frame, to_exclusive: Frame, ) -> Result<Frame, ReserveFrameError> { let target_region = self.find_containing_region(from_inclusive, to_exclusive); if let Some(region) = target_region { region.with_lock(|bitmap| bitmap.set_range_unchecked(from_inclusive, to_exclusive)); Ok(from_inclusive) } else { Err(ReserveFrameError::OutOfTargetBoundary { from_inclusive, to_exclusive, }) } } /// Выделяет один фрейм памяти fn allocate_frame(&self) -> Option<Frame> { let next_frame_hint = Frame::new(self.next_frame_hint.load(Ordering::Relaxed)); // Начинаем с подсказки next_frame_hint в текущем регионе let current_region_frame = self.regions[self.current_region_index] .with_lock(|current| Self::try_alloc_in(current, next_frame_hint)); if let Some(frame) = current_region_frame { self.next_frame_hint .store(frame.add(1).number(), Ordering::Relaxed); return Some(frame); } // Ищем в других регионах, пропуская уже проверенный for (index, region) in self.regions.iter().enumerate() { if index == self.current_region_index { continue; // Пропускаем уже проверенный регион } let region_frame = region.with_lock(|region_bitmap| { let range = region_bitmap.range(); Self::try_alloc_in(region_bitmap, Frame::from(range.start())) }); if let Some(frame) = region_frame { self.next_frame_hint .store(frame.add(1).number(), Ordering::Relaxed); return Some(frame); } } // Нет свободных фреймов None } /// Выделяет до [max_count] свободных фреймов fn allocate_frames(&self, max_count: usize) -> Option<(Frame, usize)> { for region in &self.regions { let result = region.with_lock(|bitmap| bitmap.alloc_contiguous(max_count)); if result.is_some() { return result; } } None } /// Помечает фрейм как свободный fn deallocate_frame(&self, frame: Frame) -> Result<(), FrameError> { let target_region = self.find_containing_region(frame, frame.add(1)); if let Some(region) = target_region { let was_allocated = region.with_lock(|bitmap| bitmap.clear(frame)); if was_allocated { Ok(()) } else { Err(FrameError::NotAllocated) } } else { // Фрейм находится за пределами управляемого диапазона памяти Err(FrameError::OutOfRange) } }
Bump Allocator
Можно заметить, что реализованный FrameAllocator выделяет память динамически. То есть, для работы аллокатора памяти нужен аллокатор памяти. Классическая проблема курицы и яйца. Чтобы разорвать этот круг, мы напишем временный аллокатор, который начнёт работать максимально рано.
Один из самых простых — так называемая арена. Это буфер, в котором мы будем просто линейно перемещать указатель. Освобождение памяти в арене не предусмотрено. Можно освободить только всю арену целиком.
pub struct BumpAllocator { /// Начальный адрес управляемого региона. start: usize, /// Конечный адрес управляемого региона (эксклюзивный). end: usize, /// Текущее смещение от начала (следующий свободный байт). offset: usize, } impl BumpAllocator { pub const fn new(from: PageAlignedAddress, to: PageAlignedAddress) -> Self { Self { start: from.as_usize(), end: to.as_usize(), offset: 0, } } pub fn allocate(&mut self, layout: Layout) -> Result<NonNull<u8>, BumpAllocError> { let align = layout.align(); let size = layout.size(); let base = self.start; let current = base + self.offset; let aligned = current.div_ceil(align) * align; let new_offset = (aligned - base) .checked_add(size) .ok_or(BumpAllocError::AddressOverflow)?; let end_addr = base .checked_add(new_offset) .ok_or(BumpAllocError::AddressOverflow)?; if end_addr > self.end { return Err(BumpAllocError::OutOfMemory { required_size: size, available_size: self.remaining(), }); } self.offset = new_offset; unsafe { Ok(NonNull::new_unchecked(aligned as *mut u8)) } } const fn remaining(&self) -> usize { self.end - self.start - self.offset } }
Теперь можно подключить BumpAllocator. Информация о доступной памяти уже есть. Можно взять самый большой регион. Главное, не попасть туда, где уже лежит ядро. Для этого я создал структуру IntervalSet.
/// Множество непересекающихся полуоткрытых интервалов. /// Интервалы хранятся отсортированными. При добавлении смежные и пересекающиеся интервалы автоматически объединяются. /// `N` — максимальное количество интервалов. pub struct IntervalSet<T, const N: usize> { ranges: Vec<Interval<T>, N>, } impl<T: Ord + Copy, const N: usize> IntervalSet<T, N> { /// Добавляет интервал [start, end). pub fn add(&mut self, start: T, end: T) -> Option<()>; /// Удаляет интервал [start, end). pub fn remove(&mut self, start: T, end: T) -> Option<()>; }
/// Ранняя инициализация ядра fn early_main(dtb: usize) { // ... // Устанавливаем ранний bump аллокатор let early_setup = match MemorySetup::<Early>::create(memory_layout) { Ok(setup) => setup.install(), Err(_) => return, };
MemorySetup берет на себя сборку всей цепочки. Внутри примерно следующее:
// Через IntervalSet собираем свободные регионы let free_regions = layout .free_heap_regions(); let largest_region = get_largest_region(&free_regions); let bump_allocator = Self::create_bump_allocator(*largest_region); GLOBAL_ALLOCATOR.set_bump(bump_allocator); // ... // Создаём frame_allocator из очищенных регионов let free_heap_regions_iter = free_regions .iter() .map(|interval| MemoryRange::new(interval.start, interval.end)); // Теперь мы можем создать аллокатор в куче. Получаем из него 'static ссылку через Box::leak. let frame_allocator = Box::leak(Box::new(PhysicalFrameAllocator::new( free_heap_regions_iter, ))); // Замораживаем аллокатор GLOBAL_ALLOCATOR.set_freeze(); // Берем регион использованной аллокатором памяти, чтобы исключить ее из пула свободных фреймов let bump_used = unsafe { GLOBAL_ALLOCATOR.get_bump() }.used(); let bump_start = PageAlignedAddress::aligned_down(bump_used.start()); let bump_end = PageAlignedAddress::aligned_up(bump_used.end()); frame_allocator .reserve_frames_exact(bump_start.into(), bump_end.into()) .expect("Cannot reserve bump allocator memory");
Включаем MMU
Мы определили области памяти и настроили временный аллокатор. Теперь можно динамически выделять память под таблицы трансляции адресов. Но прежде чем включать MMU — посмотрим, как устроен крейт, который будет этим заниматься. Это, пожалуй, самая интересная часть с точки зрения Rust.
Крейт aarch64-paging
В начале статьи мы разобрали структуру записей таблиц страниц — биты, поля, уровни. Теперь нужно выразить всё это в коде. Здесь нам очень поможет система типов Rust: она позволяет закодировать правила ARM64 так, что некорректные комбинации просто не скомпилируются.
Уровни как типы
Каждый уровень таблицы страниц — это отдельный zero-sized тип с трейтом Level:
arch/aarch64-paging/src/level.rs:
/// Уровень таблицы страниц. pub trait Level { /// Сдвиг для извлечения индекса из виртуального адреса. const SHIFT: u8; } /// Уровень 0 (512 ГБ на запись). pub enum L0 {} /// Уровень 1 (1 ГБ на запись). pub enum L1 {} /// Уровень 2 (2 МБ на запись). pub enum L2 {} /// Уровень 3 (4 КБ на запись). pub enum L3 {} impl Level for L0 { const SHIFT: u8 = 39; } impl Level for L1 { const SHIFT: u8 = 30; } impl Level for L2 { const SHIFT: u8 = 21; } impl Level for L3 { const SHIFT: u8 = 12; }
У L0, L1, L2, L3 нет вариантов — это пустые enum'ы, которые существуют только как параметры типов. Зато каждый несёт ассоциированную константу SHIFT — сдвиг для извлечения индекса из виртуального адреса (те самые биты из таблицы в начале статьи).
Используя SHIFT как const generic, мы определяем типизированные физические адреса для каждого уровня:
/// Физический адрес страницы (4 КБ). pub type PagePa = AlignedPhysicalAddress<{ L3::SHIFT }>; /// Физический адрес блока L1 (1 ГБ). pub type L1BlockPa = AlignedPhysicalAddress<{ L1::SHIFT }>; /// Физический адрес блока L2 (2 МБ). pub type L2BlockPa = AlignedPhysicalAddress<{ L2::SHIFT }>;
AlignedPhysicalAddress<12> — адрес, выровненный на 4 КБ. AlignedPhysicalAddress<21> — на 2 МБ. Выравнивание закодировано прямо в типе, и нарушить его невозможно.
Записи таблицы страниц
Напомним: запись в таблице L0 может быть только указателем на таблицу L1 (или невалидной). Запись в L1 — указателем на L2 или блоком 1 ГБ. В L3 — только страницей. Попробуем выразить эти ограничения в типах.
Запись параметризована уровнем и видом:
arch/aarch64-paging/src/entry.rs:
/// Маркеры вида записи. pub enum Invalid {} // Невалидная (биты [1:0] = 0b00) pub enum Table {} // Указатель на следующий уровень таблицы pub enum Block {} // Блочная запись (L1: 1 ГБ, L2: 2 МБ) pub enum Page {} // Страничная запись (4 КБ, только L3) /// Запись таблицы страниц уровня `L` с видом `K`. #[repr(transparent)] pub struct Entry<L: Level, K: Kind> { raw: u64, _p: PhantomData<(L, K)>, }
Entry<L1, Table> — это запись уровня L1, указывающая на таблицу L2. Entry<L2, Block> — блочная запись 2 МБ. Физически это один и тот же u64, но система типов не даст нам перепутать один с другим.
Теперь закодируем правила, какие виды записей допустимы на каждом уровне. Для этого используем sealed traits — трейты, которые реализуются только внутри модуля:
mod seal { pub trait CanTable {} // Уровень поддерживает запись-таблицу pub trait CanBlock {} // Уровень поддерживает блочную запись pub trait CanPage {} // Уровень поддерживает страничную запись } impl seal::CanTable for L0 {} impl seal::CanTable for L1 {} impl seal::CanTable for L2 {} impl seal::CanBlock for L1 {} impl seal::CanBlock for L2 {} impl seal::CanPage for L3 {}
Таблицы могут быть на уровнях L0–L2. Блоки — только на L1 и L2. Страницы — только на L3. Теперь конструкторы записей требуют соответствующий трейт:
impl<L: Level + seal::CanTable> Entry<L, Table> { pub fn new(next_table: PagePa, flags: TableFlags) -> Self { let addr = next_table.as_u64() & 0x0000_FFFF_FFFF_F000; Self::from_raw_unchecked(0b11 | addr | flags.bits()) } } impl Entry<L1, Block> { pub fn new(block_pa: L1BlockPa, flags: MemFlags) -> Self { let addr = block_pa.as_u64() & 0x0000_FFFF_C000_0000; Self::from_raw_unchecked(0b01 | addr | flags.bits()) } } impl Entry<L2, Block> { pub fn new(block_pa: L2BlockPa, flags: MemFlags) -> Self { let addr = block_pa.as_u64() & 0x0000_FFFF_FFE0_0000; Self::from_raw_unchecked(0b01 | addr | flags.bits()) } } impl<L: Level + seal::CanPage> Entry<L, Page> { pub fn new(page_pa: PagePa, flags: MemFlags) -> Self { let addr = page_pa.as_u64() & 0x0000_FFFF_FFFF_F000; Self::from_raw_unchecked(0b11 | addr | flags.bits()) } }
Обратите внимание: Entry<L1, Block>::new принимает L1BlockPa (адрес, выровненный на 1 ГБ), а Entry<L2, Block>::new — L2BlockPa (выровненный на 2 МБ). Невозможно передать неправильно выровненный адрес — типы разные. А попытка написать Entry<L0, Block>::new(...) не скомпилируется — для L0 нет реализации CanBlock.
Атрибуты памяти
Вместо ручной работы с битовыми масками атрибуты задаются через builder:
arch/aarch64-paging/src/mem_flags.rs:
#[repr(transparent)] pub struct MemFlags(u64); impl MemFlags { pub const fn new() -> Self { Self(0) } pub const fn af(self, on: bool) -> Self { /* Access Flag */ } pub const fn pxn(self, on: bool) -> Self { /* Privileged Execute-Never */ } pub const fn uxn(self, on: bool) -> Self { /* Unprivileged Execute-Never */ } pub const fn sh(self, sh: Shareability) -> Self { /* Shareability */ } pub const fn ap(self, ap: Access) -> Self { /* Access Permissions */ } pub const fn attr_index(self, idx: u8) -> Self { /* Индекс MAIR */ } }
Для типовых конфигураций есть готовые пресеты:
arch/aarch64-paging/src/preset.rs:
impl KernelText { pub const fn flags() -> MemFlags { MemFlags::new() .af(true) .sh(Shareability::Inner) .ap(Access::KernelRW) .attr_index(0) // Normal memory (MAIR слот 0) .pxn(false) // Исполнение разрешено .uxn(true) // Пользователю — запрещено } } impl Mmio { pub const fn flags() -> MemFlags { MemFlags::new() .af(true) .sh(Shareability::None) .ap(Access::KernelRW) .attr_index(1) // Device memory (MAIR слот 1) .pxn(true) // Исполнение запрещено .uxn(true) } }
Так гораздо читаемее, чем 0x00000000_00000705.
Таблица страниц и маппер
Сама таблица — обёртка над массивом из 512 записей, параметризованная уровнем:
arch/aarch64-paging/src/page_table.rs:
pub struct PageTable<L: Level> { entries: [u64; 512], _p: PhantomData<L>, } impl<L: Level> PageTable<L> { pub fn set<K: Kind>(&mut self, idx: usize, e: Entry<L, K>) { self.entries[idx] = e.raw(); } pub fn get_raw(&self, idx: usize) -> u64 { self.entries[idx] } }
Метод set принимает Entry<L, K> — запись того же уровня, что и таблица. Нельзя случайно записать Entry<L2, Block> в PageTable<L1>.
Маппинг — это обход дерева таблиц сверху вниз. PageMapper хранит указатель на корневую таблицу L0 и аллокатор для выделения промежуточных таблиц:
arch/aarch64-paging/src/mapper.rs:
pub struct PageMapper<A: TableAlloc> { root: *mut PageTable<L0>, alloc: A, table_flags: TableFlags, }
Ключевой метод — ensure_next. Он спускается на один уровень: берёт таблицу-родителя, проверяет запись по индексу. Если запись пустая — выделяет новую таблицу. Если таблица уже есть — возвращает указатель на неё:
fn ensure_next<PL, CL>( &mut self, parent: *mut PageTable<PL>, target_va: usize, ) -> Result<*mut PageTable<CL>, MapError> where PL: Level + CanTable + DecodeBlock, CL: Level, { let idx = (target_va >> PL::SHIFT) & 0x1FF; let raw = unsafe { (*parent).get_raw(idx) }; match decode::<PL>(raw).map_err(MapError::Decode)? { AnyEntry::Table(te) => { // Таблица существует — извлекаем PA let child_pa = extract_table_pa(te.raw()); Ok(unsafe { self.alloc.table_ptr::<CL>(child_pa, target_va) }) } AnyEntry::Invalid(_) => { // Выделяем новую таблицу let child_pa = self.alloc.alloc_table_page() .ok_or(MapError::OutOfMemory)?; unsafe { (*parent).set(idx, Entry::<PL, Table>::new(child_pa, self.table_flags)); let child = self.alloc.table_ptr::<CL>(child_pa, target_va); child.write(PageTable::new()); Ok(child) } } AnyEntry::Block(_) | AnyEntry::Page(_) => Err(MapError::AlreadyMapped), } }
Обратите внимание на сигнатуру: PL: Level + CanTable + DecodeBlock. Компилятор гарантирует, что мы вызываем ensure_next только для уровней, на которых допустимы записи-таблицы. Попытка вызвать его для L3 — ошибка компиляции.
Публичный метод map_page использует трейт MapLeaf, где const generic задаёт гранулярность маппинга:
pub fn map_page<const SHIFT: u8, P: MapLeaf<SHIFT>>( &mut self, virt: AlignedVirtualAddress<SHIFT>, phys: P, flags: MemFlags, ) -> Result<(), MapError> { P::map_into(self, virt, phys, flags) }
MapLeaf реализован для трёх типов адресов: PagePa (4 КБ страница), L2BlockPa (2 МБ блок) и L1BlockPa (1 ГБ блок). Каждая реализация спускается ровно на столько уровней, сколько нужно. Например, для L2BlockPa маппер проходит L0 → L1 → L2 и записывает блочную запись, не спускаясь до L3.
Аллокация страниц под сами таблицы абстрагирована через трейт TableAlloc:
pub trait TableAlloc { /// Выделяет физическую страницу 4 КБ под таблицу. fn alloc_table_page(&mut self) -> Option<PageAlignedAddress>; /// Возвращает указатель на таблицу по её физическому адресу. unsafe fn table_ptr<L: Level>( &self, pa: PageAlignedAddress, target_va: usize, ) -> *mut PageTable<L>; }
Это позволяет использовать один и тот же маппер с разными стратегиями выделения памяти — например, до включения MMU мы работаем с физическими адресами напрямую, а после — через виртуальные.
В итоге мы получаем систему, где ошибки вроде «записал блочную запись в L0» или «передал адрес с неправильным выравниванием» отлавливаются на этапе компиляции, а не в рантайме — что для кода ядра критически важно.
Релокация в Higher Half
Вспомним, что у ARM64 два регистра базы таблиц страниц — TTBR0 и TTBR1. Процессор выбирает один из них по старшим битам виртуального адреса: если адрес начинается с нулей — используется TTBR0, если с единиц — TTBR1.
Это позволяет разделить 64-битное адресное пространство на две половины:
Нижняя (lower half) — для пользовательских процессов.
Верхняя (higher half) — для ядра.
Смысл в следующем: при переключении контекста между процессами достаточно подменить только TTBR0 — карту памяти пользовательского процесса. Ядро, замапленное через TTBR1, остаётся на месте. Это даёт ощутимый выигрыш в производительности: не нужно сбрасывать TLB-кэш для ядерных адресов при каждом переключении контекста, а системные вызовы не требуют смены таблиц страниц — ядро уже доступно в том же адресном пространстве. Эта техника называется Higher Half Kernel.
Базовый адрес и линейный маппинг
В качестве базы верхней половины выберем:
pub const HIGHER_HALF_BASE: usize = 0xFFFF_FF80_0000_0000;
Стратегия маппинга простая — линейное отображение: для любого физического адреса PA его виртуальный адрес вычисляется как VA = HIGHER_HALF_BASE + PA. Это позволяет в любой момент перевести физический адрес в виртуальный простым сложением.
Подготовка корневых таблиц
Нам нужны две независимые корневые таблицы — по одной на каждый TTBR. Страницы под них выделяем из уже настроенного FrameAllocator:
// Корневая таблица для нижней половины (TTBR0) let lower_root_pa = frame_allocator .allocate_frame() .map(|frame| frame.page_address()) .ok_or(MemorySetupError::OutOfMemory)?; // Корневая таблица для верхней половины (TTBR1) let higher_root_pa = frame_allocator .allocate_frame() .map(|frame| frame.page_address()) .ok_or(MemorySetupError::OutOfMemory)?; let roots = PageTableRoots { lower_pa: lower_root_pa, higher_pa: higher_root_pa, lower_ptr: Self::create_root_table(lower_root_pa), higher_ptr: Self::create_root_table(higher_root_pa), };
Двойной маппинг
Перед включением MMU нужно заполнить обе таблицы:
Higher half (TTBR1) — линейно маппим все регионы: RAM, ядро, MMIO, bump-аллокатор. Формула VA = HIGHER_HALF_BASE + PA:
for region in all_regions.iter() { let va = region.virtual_start(higher_half_base); mapper.map_exact(region.start, va, region.size(), region.flags.bits())?; }
Identity mapping (TTBR0) — маппим регионы ядра и MMIO как VA = PA:
for region in identity_regions { let bootstrap_va = PageAlignedVirtualAddress::identity(region.start); mapper.map_exact(region.start, bootstrap_va, region.size(), region.flags.bits())?; }
Зачем нужен identity mapping? Это один из тех моментов, где легко выстрелить себе в ногу. После включения MMU процессор немедленно начнёт транслировать все адреса — включая текущий PC. А PC в этот момент содержит физический адрес, по которому загружено ядро. Если этот адрес не замаплен — мгновенный Page Fault, и ядро молча падает. Identity mapping (VA = PA) гарантирует, что код продолжит исполняться.
При этом маппить всю RAM в identity нет необходимости — достаточно только тех регионов, к которым код обращается до прыжка в higher half.
Включение MMU
Когда таблицы заполнены, записываем системные регистры и включаем MMU:
pub fn enable<C: MmuConfig>(&self, config: C) { system::barrier::full_system_barrier(); // Атрибуты памяти: normal (кэшируемая RAM) и device (MMIO) self.mair.set(/* normal + device */); // Параметры трансляции адресов для обоих половин self.tcr.set(lower_config, higher_config); // Адреса корневых таблиц self.lower_half_base.set(lower_root); // TTBR0 self.higher_half_base.set(higher_root); // TTBR1 self.tlb.invalidate(); // Включаем MMU + кэши (биты M, C, I в SCTLR) self.sctlr.set(config.mmu_config()); system::barrier::full_system_barrier(); }
После этого вызова процессор транслирует каждый адрес через таблицы страниц. Благодаря identity mapping код продолжает работать — PC по-прежнему указывает на физический адрес, но теперь он транслируется сам в себя.
Прыжок в Higher Half
Осталось переключить PC на адрес в верхней половине. Для этого используем naked-функцию:
#[unsafe(naked)] unsafe extern "C" fn jump_to_higher_half() { const HALF_47_32: u64 = ((HIGHER_HALF_BASE as u64) >> 32) & 0xFFFF; const HALF_63_48: u64 = ((HIGHER_HALF_BASE as u64) >> 48) & 0xFFFF; naked_asm!( "adr x0, 1f", // x0 = текущий адрес метк�� (identity) "movz x1, #{half_32}, lsl #32", // x1 = HIGHER_HALF_BASE "movk x1, #{half_48}, lsl #48", // "add x0, x0, x1", // x0 = identity + HIGHER_HALF_BASE "br x0", // Прыжок "1:", // Сюда попадаем уже по higher half адресу "ret", half_32 = const HALF_47_32, half_48 = const HALF_63_48, ) }
Инструкция adr помещает в x0 текущий PC-relative адрес метки 1: — это физический адрес. Затем мы прибавляем к нему HIGHER_HALF_BASE и делаем br — безусловный переход. Процессор переходит на тот же самый код, но теперь адрес лежит в верхней половине и транслируется через TTBR1.
После прыжка identity mapping через TTBR0 больше не нужен — в будущем этот регистр будет использоваться для таблиц пользовательских процессов. А ядро с этого момента полностью работает в higher half.
Завершает настройку переключение глобального аллокатора на heap-фазу. Все дальнейшие аллокации будут проходить через виртуальные адреса, а указатели на уже существующие объекты (например, stdout драйвер) пересчитываются со сдвигом на HIGHER_HALF_BASE.
Free list allocator
В качестве основного аллокатора будем использовать простой алгоритм на основе intrusive linked list.
Идея алгоритма: свободная память представлена в виде связного списка блоков. Каждый свободный блок хранит свой размер и указатель на следующий свободный блок — прямо внутри самой свободной памяти (отсюда название intrusive). Пройдёмся по шагам на картинке.
(1) Изначально имеем непрерывную область свободной памяти. У нас уже есть FrameAllocator, управляющий физическими страницами. Вся RAM линейно замаплена в higher half, поэтому физический адрес фрейма превращается в виртуальный простым сложением: VA = HIGHER_HALF_BASE + PA.
(2) При первом выделении аллокатор запрашивает страницы у FrameAllocator и записывает в начало полученной памяти структуру FreeBlock. Указатель free_list_head указывает на этот блок. Получается единственный свободный блок, покрывающий всю выделенную область.
(3) При выделении (alloc(256)) аллокатор обходит свой free list и ищет первый блок, который достаточно велик для запроса — это стратегия first-fit. Найдя такой блок, он разделяет его: первая часть отдаётся вызывающему коду, а из остатка формируется новый FreeBlock, который остаётся в списке.
(4) Повторное выделение (alloc(128)) работает так же — свободный блок снова разделяется, свободная область сужается.
(5) Освобождение (dealloc) — обратная операция. Блок превращается обратно в FreeBlock и вставляется в голову списка. Указатель free_list_head теперь ведёт на него, а его next — на предыдущую голову. Освобождённая память снова доступна.
Теперь к реализации. Заголовок свободного блока — минимальная intrusive-структура:
memory/src/heap_allocator.rs:
struct FreeBlock { /// Размер полезной области блока в байтах (без заголовка). size: usize, /// Указатель на следующий свободный блок. next: Option<NonNull<FreeBlock>>, } impl FreeBlock { const fn from_size(size: usize) -> Self { FreeBlock { size, next: None } } }
Размер FreeBlock — 16 байт (два машинных слова). Это также минимальный размер любого выделения: при освобождении на место пользовательских данных нужно уместить заголовок.
Сам аллокатор хранит голову списка, ссылку на FrameAllocator для расширения кучи и базу higher half для пересчёта адресов:
pub struct HeapAllocator { /// Аллокатор физических фреймов frame_allocator: &'static dyn FrameAllocator, /// База higher half для преобразования PA → VA higher_half_base: usize, /// Голова списка свободных блоков free_list_head: Option<NonNull<FreeBlock>>, /// Текущий размер кучи в байтах current_size: usize, }
При выделении аллокатор обходит список в поисках подходящего блока. Если блок найден, он удаляется из списка, а если блок значительно больше запроса — разделяется, и остаток возвращается в free list:
fn find_free_block(&mut self, size: usize) -> Option<NonNull<FreeBlock>> { let mut current = self.free_list_head; let mut prev: Option<NonNull<FreeBlock>> = None; while let Some(block_ptr) = current { unsafe { let block = block_ptr.as_ptr(); if (*block).size >= size { // Удаляем блок из списка if let Some(prev_ptr) = prev { (*prev_ptr.as_ptr()).next = (*block).next; } else { self.free_list_head = (*block).next; } // Разделяем, если блок значительно больше запроса if let Some(remainder) = (*block).split(size) { self.add_to_free_list(remainder); } return Some(block_ptr); } prev = current; current = (*block).next; } } None }
Метод split проверяет, поместится ли в остаток новый FreeBlock + минимальный размер данных. Если да — создаёт новый блок прямо в памяти после выделенной области:
fn split(&mut self, requested_size: usize) -> Option<NonNull<FreeBlock>> { let min_remaining = size_of::<FreeBlock>() + MIN_ALLOC_SIZE; if self.size < requested_size + min_remaining { return None; // Остаток слишком мал — отдаём блок целиком } // Новый FreeBlock после выделенной области let new_block_offset = size_of::<FreeBlock>() + requested_size; let new_block_size = self.size - requested_size - size_of::<FreeBlock>(); let new_block_ptr = unsafe { let new_ptr = ((self as *mut FreeBlock as usize) + new_block_offset) as *mut FreeBlock; *new_ptr = FreeBlock::from_size(new_block_size); NonNull::new_unchecked(new_ptr) }; self.size = requested_size; Some(new_block_ptr) }
Публичный метод allocate объединяет поиск и расширение кучи. Если в free list нет подходящего блока, аллокатор запрашивает у FrameAllocator новые страницы через метод expand:
pub fn allocate(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocationError> { let size = layout.size().max(MIN_ALLOC_SIZE); let alloc_size = size + HEADER_PTR_SIZE + layout.align() - 1; // Ищем подходящий блок в free list if let Some(block_ptr) = self.find_free_block(alloc_size) { return Ok(self.setup_allocated_block(block_ptr, layout.align())); } // Не нашли — расширяем кучу self.expand(alloc_size + size_of::<FreeBlock>())?; let block_ptr = self.find_free_block(alloc_size) .ok_or(AllocationError::OutOfMemory)?; Ok(self.setup_allocated_block(block_ptr, layout.align())) }
Метод expand запрашивает физические фреймы, вычисляет виртуальный адрес (память уже замаплена линейно) и создаёт из полученных страниц новый FreeBlock:
fn expand(&mut self, min_size: usize) -> Result<(), AllocationError> { let pages_needed = align_up(min_size, PAGE_SIZE) / PAGE_SIZE; let mut remaining = pages_needed; while remaining > 0 { let (frame, count) = self.frame_allocator .allocate_frames(remaining) .ok_or(AllocationError::OutOfMemory)?; let block_bytes = count * PAGE_SIZE; // VA = higher_half_base + PA (линейный маппинг) let va = self.higher_half_base + frame.page_address().as_usize(); unsafe { let block_ptr = va as *mut FreeBlock; *block_ptr = FreeBlock::from_size(block_bytes - size_of::<FreeBlock>()); self.add_to_free_list(NonNull::new_unchecked(block_ptr)); } self.current_size += block_bytes; remaining -= count; } Ok(()) }
Обратите внимание — куча растёт лениво: начальный размер нулевой, страницы выделяются по мере необходимости.
Остаётся освобождение. Здесь есть тонкость: deallocate получает только указатель на пользовательские данные, но ничего не знает о FreeBlock. Чтобы найти заголовок, мы при выделении прячем указатель на него прямо перед пользовательскими данными.
Поэтому в deallocate достаточно отступить на один указатель назад:
pub fn deallocate(&mut self, ptr: NonNull<u8>) { // Указатели из lower half — это bump-аллокатор, его dealloc — no-op if (ptr.as_ptr() as usize) < self.higher_half_base { return; } unsafe { // Читаем указатель на заголовок, спрятанный перед данными let header_ptr_location = (ptr.as_ptr() as *mut *mut FreeBlock).sub(1); let block_ptr = *header_ptr_location; if let Some(block) = NonNull::new(block_ptr) { // Обнуляем для защиты от double-free *header_ptr_location = core::ptr::null_mut(); self.add_to_free_list(block); } } }
Добавление блока в free list — вставка в голову списка:
fn add_to_free_list(&mut self, block_ptr: NonNull<FreeBlock>) { unsafe { let mut block = block_ptr.read(); block.next = self.free_list_head; block_ptr.write(block); self.free_list_head = Some(block_ptr); } }
Подключение к глобальному аллокатору
Чтобы в ядре работали Box, Vec и прочие контейнеры из alloc, нужно реализовать трейт GlobalAlloc. Мы уже видели, что аллокатор ядра работает в несколько фаз — bump, затем heap. Для этого я написал обёртку GlobalKernelAllocator, которая хранит оба аллокатора и переключается между ними по атомарному флагу фазы:
arch/aarch64/src/memory/global_allocator.rs:
const PHASE_UNINIT: u8 = 0; // Не инициализирован const PHASE_BUMP: u8 = 1; // Bump-фаза (ранняя инициализация) const PHASE_HEAP: u8 = 2; // Heap-фаза (основная работа) const PHASE_FROZEN: u8 = 3; // Заморожен (аллокации запрещены) #[global_allocator] pub(crate) static GLOBAL_ALLOCATOR: GlobalKernelAllocator = GlobalKernelAllocator::new(); pub struct GlobalKernelAllocator { phase: AtomicU8, bump: UnsafeCell<MaybeUninit<BumpAllocator>>, heap: UnsafeCell<MaybeUninit<HeapAllocator>>, }
Реализация GlobalAlloc просто диспетчеризует вызовы в зависимости от текущей фазы:
unsafe impl GlobalAlloc for GlobalKernelAllocator { unsafe fn alloc(&self, layout: Layout) -> *mut u8 { match self.phase.load(Ordering::Acquire) { PHASE_BUMP => match unsafe { self.get_bump() }.allocate(layout) { Ok(ptr) => ptr.as_ptr(), Err(_) => core::ptr::null_mut(), }, PHASE_HEAP => match unsafe { self.get_heap() }.allocate(layout) { Ok(ptr) => ptr.as_ptr(), Err(_) => core::ptr::null_mut(), }, PHASE_FROZEN => panic!("Allocation attempted while allocator is frozen"), _ => core::ptr::null_mut(), } } unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) { match self.phase.load(Ordering::Acquire) { PHASE_HEAP => { if let Some(non_null_ptr) = NonNull::new(ptr) { unsafe { self.get_heap() }.deallocate(non_null_ptr); } } // Bump-фаза: dealloc — no-op, память не освобождается _ => {} } } }
Переход между фазами: сначала включается bump — он работает с самого старта, пока мы настраиваем таблицы страниц и фрейм-аллокатор. Затем bump замораживается (PHASE_FROZEN), чтобы зафиксировать область использованной памяти и исключить её из пула свободных фреймов. После включения MMU и прыжка в higher half подключается HeapAllocator (PHASE_HEAP) — полноценный аллокатор с поддержкой освобождения памяти.
Запускаем ядро
Все компоненты на месте. Давайте посмотрим на полную картину — как выглядит точка входа ядра после всех доработок.
arch/aarch64/src/start.rs:
fn early_main(dtb: usize) { // Парсим DTB let device_tree = match DeviceTree::from_ptr(dtb) { Ok(tree) => tree, Err(_) => return, }; // Извлекаем из DTB информацию о регионах памяти let memory_layout = match build_memory_layout(&device_tree) { Ok(m) => m, Err(_) => return, }; // Устанавливаем ранний bump аллокатор let early_setup = match MemorySetup::<Early>::create(memory_layout) { Ok(setup) => setup.install(), Err(_) => return, }; // Сканируем драйверы из DTB и привязываем stdout let mut early_registry = DriverRegistry::new(); early_registry.scan_and_probe(&device_tree); let early_registry: &'static DriverRegistry = Box::leak(Box::new(early_registry)); bind_early_stdout(&device_tree, early_registry); // Собираем MMIO-регионы из драйверов для маппинга let mmio_requests: Vec<_> = early_registry .mmio_region_requests() .iter() .map(|r| MemoryRegion::mmio(r.base, r.size)) .collect(); // Настраиваем MMU, включаем heap-аллокатор, прыгаем в higher half if setup_memory(mmio_requests, early_setup).is_err() { return; } // Основная платформозависимая настройка завершена kmain(); loop { spin_loop(); } }
Вот она — вся цепочка инициализации в одном месте. Каждый шаг, который мы по отдельности разбирали в этой статье, здесь занимает пару строк. Парсим DTB, строим раскладку памяти, поднимаем bump-аллокатор, сканируем и привязываем драйверы, настраиваем MMU с прыжком в higher half — и передаём управление в kmain(). Когда этот код наконец заработал от начала до конца без единого Page Fault — это было приятное чувство.
А что в kmain? Я написал мини-тест, чтобы убедиться, что вся цепочка от физического аллокатора через таблицы страниц до GlobalAlloc работает.
kernel/src/kmain.rs:
pub fn kmain() { test_allocator(); } fn test_allocator() { info!("Тест аллокатора"); // Маленький объект let small = Box::new(42u64); info!("u64: ptr = {:p}, value = {}", small.as_ref(), *small); drop(small); // Большой объект (2 страницы) let huge = Box::new([0xAAu8; 8192]); info!("[u8; 8192]: ptr = {:p}", huge.as_ref()); drop(huge); // Vec больше страницы let mut vec: Vec<u64> = Vec::with_capacity(600); for i in 0..600 { vec.push(i); } info!( "Vec<u64>: len = {}, cap = {}, ptr = {:p}", vec.len(), vec.capacity(), vec.as_ptr() ); drop(vec); info!("Тест завершен"); }
Три простых проверки — и они покрывают удивительно много. Box::new(42u64) — это аллокация 8 байт; если HeapAllocator не настроен или GlobalAlloc не подключён — паника. Массив [0xAA; 8192] — это 2 страницы; аллокатор должен запросить фреймы у FrameAllocator, а маппинг higher half должен быть корректным — иначе запись по виртуальному адресу уйдёт в никуда. Наконец, Vec с 600 элементами проверяет, что alloc, realloc и внутренние механизмы роста вектора работают. А drop в конце каждого теста — что освобождение памяти не ломает free list.
Если все четыре строки лога напечатались — значит, менеджер памяти работает.
Записываем kernel8.img на SD-карту Raspberry Pi 5, подключаем UART — и вот что видим:
А видим мы следующие логи
0.95 RPi: BOOTSYS release VERSION:69471177 DATE: 2025/05/08 TIME: 15:13:17
0.95 BOOTMODE: 0x06 partition 0 build-ts BUILD_TIMESTAMP=1746713597 serial fcf21630 boardrev c04170 stc 959161
1.11 Initialising SDRAM rank 2 total-size: 32 Gbit 4267 (0x15 0x00)
1.11 DDR 4267 1 0 32 152 BL:1
...
6.86 Loading 'kernel8.img' to 0x00000000 offset 0x200000
6.75 Read kernel8.img bytes 73800 hnd 0x28fc
6.87 MESS:00:00:06.877562:0: Device tree loaded to 0x2efec600 (size 0x139b5)
6.94 MESS:00:00:06.949710:0: Starting OS 6949 ms
NOTICE: BL31: v2.6(release):v2.6-240-gfc45bc492
NOTICE: BL31: Built : 12:55:13, Dec 4 2024
[I] [Memory layout] - Heap, from 0x0 to 0x3fc00000
[I] [Memory layout] - Other, from 0x2efec000 to 0x2f000000
[I] [Memory layout] - Kernel, from 0x200000 to 0x20e000
[I] [Memory layout] - Kernel, from 0x211000 to 0x223000
[I] [Memory layout] - Kernel, from 0x20e000 to 0x211000
[D] [MemorySetup::prepare] Free heap region: 0x0 - 0x200000 (2097152 bytes)
[D] [MemorySetup::prepare] Free heap region: 0x223000 - 0x2efec000 (786206720 bytes)
[D] [MemorySetup::prepare] Free heap region: 0x2f000000 - 0x3fc00000 (281018368 bytes)
[D] [MemorySetup::prepare] Allocated page table roots: lower=0x1000, higher=0x2000
[D] [MemorySetup::prepare] Created root page tables
[D] [map_higher_half] Mapping Heap: PA 0x0 -> VA 0xffffff8000000000, size=0x200000
[D] [map_higher_half] Mapping Heap: PA 0x22c000 -> VA 0xffffff800022c000, size=0x2edc0000
[D] [map_higher_half] Mapping Heap: PA 0x2f000000 -> VA 0xffffff802f000000, size=0x10c00000
[D] [map_higher_half] Mapping Other: PA 0x2efec000 -> VA 0xffffff802efec000, size=0x14000
[D] [map_higher_half] Mapping Kernel: PA 0x200000 -> VA 0xffffff8000200000, size=0xe000
[D] [map_higher_half] Mapping Kernel: PA 0x211000 -> VA 0xffffff8000211000, size=0x12000
[D] [map_higher_half] Mapping Kernel: PA 0x20e000 -> VA 0xffffff800020e000, size=0x3000
[D] [map_higher_half] Mapping Mmio: PA 0x107d001000 -> VA 0xffffff907d001000, size=0x1000
[D] [map_higher_half] Mapping Other: PA 0x223000 -> VA 0xffffff8000223000, size=0x9000
[D] [map_identity] Identity for Other: PA 0x2efec000, size=0x14000
[D] [map_identity] Identity for Kernel: PA 0x200000, size=0xe000
[D] [map_identity] Identity for Kernel: PA 0x211000, size=0x12000
[D] [map_identity] Identity for Kernel: PA 0x20e000, size=0x3000
[D] [map_identity] Identity for Mmio: PA 0x107d001000, size=0x1000
[D] [map_identity] Identity for Other: PA 0x223000, size=0x9000
[D] [MemorySetup::enable] Enabling MMU with TTBR0=0x1000, TTBR1=0x2000
[D] [MemorySetup::enable] MMU enabled successfully
[D] MMU enabled!
[I] Running in higher half
[D] [MemorySetup<Enabled>::install] Heap allocator created with higher_half_base=0xffffff8000000000
[I] Global allocator switched to heap phase
[I] Тест аллокатора
[I] u64: ptr = 0xffffff800000f018, value = 42
[I] [u8; 8192]: ptr = 0xffffff8000010018
[I] Vec<u64>: len = 600, cap = 600, ptr = 0xffffff8000010018
[I] Тест завершен
Первая часть лога — загрузчик Raspberry Pi 5: инициализация DDR, чтение SD-карты, загрузка kernel8.img по адресу 0x200000. Затем ARM Trusted Firmware (BL31) передаёт управление нашему ядру.
Дальше начинается наш код. Видно, как ядро разбирает раскладку памяти — 1 ГБ RAM, из которых практически всё свободно для кучи (три региона общим объёмом ~1020 МБ — за вычетом ядра и DTB). Создаются корневые таблицы страниц, маппятся регионы в higher half и identity. MMU включается — и ядро прыгает в верхнюю половину адресного пространства.
Последние четыре строки — наш тест. Указатели начинаются с 0xffffff80... — это higher half. Box, Vec, drop — всё работает. Аллокатор выделяет и освобождает память через виртуальные адреса, а за кулисами FrameAllocator управляет физическими страницами, таблицы трансляции корректно преобразуют адреса, и free list исправно ведёт учёт свободных блоков.
Ядро загрузилось на реальном железе. Менеджер памяти работает — от первых байт bump-аллокатора до полноценной кучи с Box и Vec. Такие логи выводятся и в QEMU, и на моём подопытном Xiaomi Redmi Note 7. Путь сюда был непростым: куча Page Fault'ов, часы в GDB, временные обработчики исключений, которые молча проглатывали ошибки. Но теперь у нас есть фундамент, на котором можно строить всё остальное — прерывания, планировщик, драйверы устройств, файловую систему.
Что дальше
Из-за объёма статьи за кадром остались несколько интересных вещей:
register_driver!— макрос для регистрации драйверов через линкер-секции, по аналогии с моделью Linux. Драйвер объявляет себя одной строко��, а ядро автоматически находит все зарегистрированные драйверы при загрузке.klog— собственный логгер: до настройки MMU пишет напрямую в UART, после — через виртуальные адреса.Типобезопасные MMIO-обёртки — чтение и запись в регистры устройств через типизированные структуры, а не через сырые указатели.
RelocatablePtr— умный указатель для релокации fat-указателей (например,&dyn Trait) при переходе из identity mapping в higher half.LockCell— абстракция для переключения между однопоточной и многопоточной синхронизацией без изменения кода.
Всё это можно посмотреть в репозитории на GitHub.
Следующая статья будет посвящена прерываниям. Будет реализована обработка прерываний от устройств, работа с исключениями, переключение в userspace и работа с потоками. Попробую — но не обещаю — запустить другие ядра и написать планировщик процессов и системные вызовы. Прерывания оживят ОС, задав ей пульс.
