Тема сегодняшнего разговора — работа с памятью. Я расскажу про инициализацию директории страниц, маппинг физической памяти, управление виртуальной и мою организацию кучи для аллокатора.
Как я уже говорил в первой статье, я решил использовать страницы размером 4 МиБ, чтобы упростить себе жизнь и не иметь дела с иерархическими таблицами. В дальнейшем я надеюсь перейти на страницы размером 4 КиБ, как большинство современных систем. Я мог бы использовать готовый (например, такой блочный аллокатор), но написать свой было чуть интереснее и хотелось чуть больше понять, как живет память, так что мне есть, что вам рассказать.
В прошлый раз я остановился на архитектурно-зависимом методе setup_pd и хотел продолжить с него, однако осталась еще одна деталь, которую я не осветил в предыдущей статье — вывод в VGA средствами Rust и стандартный макрос println. Так как его реализация тривиальна, уберу ее под спойлер. Код находится в пакете debug.
#[macro_export]
macro_rules! print {
($($arg:tt)*) => ($crate::debug::_print(format_args!($($arg)*)));
}
#[macro_export]
macro_rules! println {
() => ($crate::print!("n"));
($($arg:tt)*) => ($crate::print!("{}n", format_args!($($arg)*)));
}
#[cfg(target_arch = "x86")]
pub fn _print(args: core::fmt::Arguments) {
use core::fmt::Write;
use super::arch::vga;
vga::VGA_WRITER.lock().write_fmt(args).unwrap();
}
#[cfg(target_arch = "x86_64")]
pub fn _print(args: core::fmt::Arguments) {
use core::fmt::Write;
use super::arch::vga;
// vga::VGA_WRITER.lock().write_fmt(args).unwrap();
}Теперь с чистой совестью я возвращаюсь к памяти.
Инициализация директории страниц
Наш метод kmain принимал на вход три аргумента, один из которых — виртуальный адрес таблицы страниц. Чтобы использовать его в дальнейшем при аллокации и управлении памятью, нужно обозначить структуру записей и директории. Для x86 Page directory и Page table описаны достаточно хорошо, так что ограничусь небольшой вводной. Запись Page directory — структура по размеру указателя, для нас — 4 байта. Значение содержит выровненный на 4 КиБ физический адрес страницы. Самый младший байт записи отведен под флаги. Механизм преобразования виртуального адреса в физический выглядит так (в случае моей гранулярности в 4 МиБ сдвиг происходит на 22 бита. Для других гранулярностей сдвиг будет другим и будут использованы иерархические таблицы!):
Виртуальный адрес 0xC010A110 -> Получить индекс в директории, сдвинув адрес на 22 бита вправо -> индекс 0x300 -> Получить физический адрес страницы по индексу 0x300, проверить флаги и состояние -> 0x1000000 -> Взять нижние 22 бита виртуального адреса в качестве смещения, добавить к физическому адресу страницы -> 0x1000000 + 0x10A110 = физический адрес в памяти 0x110A110
Для ускорения доступа процессор использует TLB — translation lookaside buffer, в который кеширует адреса страниц.
Итак, вот как описана моя директория и ее записи, и реализован тот самый метод setup_pd. Для записи страницы реализован метод “конструктора”, который гарантирует выравнивание на 4 КиБ и установку флагов, и метод получения физического адреса страницы. Директория — всего лишь массив из 1024 четырехбайтных записей. Директория умеет устанавливать ассоциацию виртуального адреса со страницей методом set_by_addr.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PDirectoryEntry(u32);
impl PDirectoryEntry {
pub fn by_phys_address(address: usize, flags: PDEntryFlags) -> Self {
PDirectoryEntry((address as u32) & ADDRESS_MASK | flags.bits())
}
pub fn flags(&self) -> PDEntryFlags {
PDEntryFlags::from_bits_truncate(self.0)
}
pub fn phys_address(&self) -> u32 {
self.0 & ADDRESS_MASK
}
pub fn dbg(&self) -> u32 {
self.0
}
}
pub struct PDirectory {
entries: [PDirectoryEntry; 1024]
}
impl PDirectory {
pub fn at(&self, idx: usize) -> PDirectoryEntry {
self.entries[idx]
}
pub fn set_by_addr(&mut self, logical_addr: usize, entry: PDirectoryEntry) {
self.set(PDirectory::to_idx(logical_addr), entry);
}
pub fn set(&mut self, idx: usize, entry: PDirectoryEntry) {
self.entries[idx] = entry;
unsafe {
invalidate_page(idx);
}
}
pub fn to_logical_addr(idx: usize) -> usize {
(idx << 22)
}
pub fn to_idx(logical_addr: usize) -> usize {
(logical_addr >> 22)
}
}
use lazy_static::lazy_static;
use spin::Mutex;
lazy_static! {
static ref PAGE_DIRECTORY: Mutex<&'static mut PDirectory> = Mutex::new(
unsafe { &mut *(0xC0000000 as *mut PDirectory) }
);
}
pub unsafe fn setup_pd(pd: usize) {
let mut data = PAGE_DIRECTORY.lock();
*data = &mut *(pd as *mut PDirectory);
}Я очень неуклюже сделал первичную статическую инициализацию несуществующим адресом, поэтому я буду благодарен, если вы напишите мне, как принято в Rust сообществе делать подобные инициализации с переприсваиванием ссылки.
Теперь, когда мы можем управлять страницами из высокоуровневого кода, можно перейти к составлению инициализации памяти. Это произойдет в два этапа: через обработку карты физической памяти и инициализацию менеджера виртуальной
match mb_magic {
0x2BADB002 => {
println!("multibooted v1, yeah, reading mb info");
boot::init_with_mb1(mb_pointer);
},
. . . . . .
}
memory::init();Карта памяти GRUB и карта физической памяти OS1
Для того, чтобы от GRUB получить карту памяти, на этапе загрузки я установил в заголовок соответствующий флаг, а GRUB передал мне физический адрес структуры. Я портировал ее из официальной документации в нотацию Rust, а так же добавил методы, чтобы комфортно итерироваться по карте памяти. Большую часть структуры GRUB заполнять не будет, и на данном этапе она мне не сильно интересна. Главное, что я не хочу определять объем доступной памяти вручную.
При инициализации через Multiboot мы в первую очередь преобразуем физический адрес в виртуальный. Теоретически GRUB может расположить структуру где угодно, поэтому если адрес выходит за пределы страницы, необходимо аллоцировать виртуальную страницу в Page directory. Практически же структура почти всегда лежит в рядом с первым мегабайтом, который у нас уже аллоцирован на этапе загрузки. На всякий случай проверяем флаг, что карта памяти присутствует и приступаем к ее разбору.
pub mod multiboot2;
pub mod multiboot;
use super::arch;
unsafe fn process_pointer(mb_pointer: usize) -> usize {
//if in first 4 MB - map to kernel address space
if mb_pointer < 0x400000 {
arch::KERNEL_BASE | mb_pointer
} else {
arch::paging::allocate_page(mb_pointer, arch::MB_INFO_BASE,
arch::paging::PDEntryFlags::PRESENT |
arch::paging::PDEntryFlags::WRITABLE |
arch::paging::PDEntryFlags::HUGE_PAGE
);
arch::MB_INFO_BASE | mb_pointer
}
}
pub fn init_with_mb1(mb_pointer: usize) {
let ln_pointer = unsafe { process_pointer(mb_pointer) };
println!("mb pointer 0x{:X}", ln_pointer);
let mb_info = multiboot::from_ptr(ln_pointer);
println!("mb flags: {:?}", mb_info.flags().unwrap());
if mb_info.flags().unwrap().contains(multiboot::MBInfoFlags::MEM_MAP) {
multiboot::parse_mmap(mb_info);
println!("Multiboot memory map parsed, physical memory map has been built");
} else {
panic!("MB mmap is not presented");
}
}Карта памяти представляет собой связанный список, для которого в базовой структуре задан начальный физический адрес (не забываем все транслировать в виртуальные) и размер массива в байтах. По списку приходится итерироваться на основании размера каждого элемента, так как теоретически их размеры могут отличаться. Вот так выглядит итерация:
impl MultibootInfo {
. . . . . .
pub unsafe fn get_mmap(&self, index: usize) -> Option<*const MemMapEntry> {
use crate::arch::get_mb_pointer_base;
let base: usize = get_mb_pointer_base(self.mmap_addr as usize);
let mut iter: *const MemMapEntry = (base as u32 + self.mmap_addr) as *const MemMapEntry;
for _i in 0..index {
iter = ((iter as usize) + ((*iter).size as usize) + 4) as *const MemMapEntry;
if ((iter as usize) - base) >= (self.mmap_addr + self.mmap_lenght) as usize {
return None
} else {}
}
Some(iter)
}
}При разборе карты памяти, мы итерируемся через структуру GRUB и преобразуем ее в битовую карту, с которой будет работать OS1 для управления физической памятью. Я решил ограничиться небольшим набором доступных значений для управления — свободна, занята, зарезервирована, недоступна, хотя GRUB и BIOS предоставляет больше вариантов. Итак, мы итерируемся по записям карты и преобразуем их состояние из значений GRUB/BIOS в значения для OS1:
pub fn parse_mmap(mbi: &MultibootInfo) {
unsafe {
let mut mmap_opt = mbi.get_mmap(0);
let mut i: usize = 1;
loop {
let mmap = mmap_opt.unwrap();
crate::memory::physical::map((*mmap).addr as usize, (*mmap).len as usize, translate_multiboot_mem_to_os1(&(*mmap).mtype));
mmap_opt = mbi.get_mmap(i);
match mmap_opt {
None => break,
_ => i += 1,
}
}
}
}
pub fn translate_multiboot_mem_to_os1(mtype: &u32) -> usize {
use crate::memory::physical::{RESERVED, UNUSABLE, USABLE};
match mtype {
&MULTIBOOT_MEMORY_AVAILABLE => USABLE,
&MULTIBOOT_MEMORY_RESERVED => UNUSABLE,
&MULTIBOOT_MEMORY_ACPI_RECLAIMABLE => RESERVED,
&MULTIBOOT_MEMORY_NVS => UNUSABLE,
&MULTIBOOT_MEMORY_BADRAM => UNUSABLE,
_ => UNUSABLE
}
}Управление физической памятью происходит в модуле memory::physical, для которого выше мы вызываем метод map, передавая ему адрес региона, его длину и состояние. Все 4 ГиБ памяти, потенциально доступные системе и разбитые на четырех-мегабайтные страницы, представлены двумя битами в битовой карте, что позволяет хранить 4 состояния для 1024 страниц. Всего эта конструкция занимает 256 байт. Битовая карта ведет к ужасной фрагментации памяти, но зато это понятно и просто реализовать, что является главным для моей цели.
Я уберу под спойлер реализацию битовой карты, чтобы не захламлять статью. Структура умеет подсчитывать количество занятий и свободной памяти, маркировать страницы по индексу и адресу, а также искать свободные страницы (это понадобится в дальнейшем для реализации кучи). Сама карта представляет собой массив из 64-х элементов u32, для вычленения необходимых двух битов (блоков) используется преобразование в так называемый чанк (индекс в массиве, упаковка по 16 блоков) и блок (позиция бита в чанке).
pub const USABLE: usize = 0;
pub const USED: usize = 1;
pub const RESERVED: usize = 2;
pub const UNUSABLE: usize = 3;
pub const DEAD: usize = 0xDEAD;
struct PhysMemoryInfo {
pub total: usize,
used: usize,
reserved: usize,
chunks: [u32; 64],
}
impl PhysMemoryInfo {
// returns (chunk, page)
pub fn find_free(&self) -> (usize, usize) {
for chunk in 0..64 {
for page in 0.. 16 {
if ((self.chunks[chunk] >> page * 2) & 3) ^ 3 == 3 {
return (chunk, page)
} else {}
}
}
(DEAD, 0)
}
// marks page to given flag and returns its address
pub fn mark(&mut self, chunk: usize, block: usize, flag: usize) -> usize {
self.chunks[chunk] = self.chunks[chunk] ^ (3 << (block * 2));
let mask = (0xFFFFFFFC ^ flag).rotate_left(block as u32 * 2);
self.chunks[chunk] = self.chunks[chunk] & (mask as u32);
if flag == USED {
self.used += 1;
} else if flag == UNUSABLE || flag == RESERVED {
self.reserved += 1;
} else {
if self.used > 0 {
self.used -= 1;
}
}
(chunk * 16 + block) << 22
}
pub fn mark_by_addr(&mut self, addr: usize, flag: usize) {
let block_num = addr >> 22;
let chunk: usize = (block_num / 16) as usize;
let block: usize = block_num - chunk * 16;
self.mark(chunk, block, flag);
}
pub fn count_total(& mut self) {
let mut count: usize = 0;
for i in 0..64 {
let mut chunk = self.chunks[i];
for _j in 0..16 {
if chunk & 0b11 != 0b11 {
count += 1;
}
chunk = chunk >> 2;
}
}
self.total = count;
}
pub fn get_total(&self) -> usize {
self.total
}
pub fn get_used(&self) -> usize {
self.used
}
pub fn get_reserved(&self) -> usize {
self.reserved
}
pub fn get_free(&self) -> usize {
self.total - self.used - self.reserved
}
}И вот теперь мы добрались до разбора одного элемента карты. Если элемент карты описывает участок памяти меньше одной страницы в 4 МиБ или равен ей, помечаем эту страницу целиком. Если больше — бьем на куски по 4 МиБ и каждый кусок помечаем отдельно через рекурсию. На этапе инициализации битовой карты считаем все участки памяти недоступными, чтобы когда кончится карта например на 128 МиБ, остальные участки были помечены как недоступные.
use lazy_static::lazy_static;
use spin::Mutex;
lazy_static! {
static ref RAM_INFO: Mutex<PhysMemoryInfo> =
Mutex::new(PhysMemoryInfo {
total: 0,
used: 0,
reserved: 0,
chunks: [0xFFFFFFFF; 64]
});
}
pub fn map(addr: usize, len: usize, flag: usize) {
// if len <= 4MiB then mark whole page with flag
if len <= 4 * 1024 * 1024 {
RAM_INFO.lock().mark_by_addr(addr, flag);
} else {
let pages: usize = len >> 22;
for map_page in 0..(pages - 1) {
map(addr + map_page << 22, 4 * 1024 * 1024, flag);
}
map(addr + (pages << 22), len - (pages << 22), flag);
}
}Куча и управление ей
Управление виртуальной памятью на данный момент ограничивается только управлением кучей, так как особо больше ничего ядро и не умеет. В дальнейшем, конечно, необходимо будет управлять всей памятью, и этот небольшой менеджер будет переписан. Однако на данный момент все что мне нужно — это статическая память, в которой находится исполняемый код и стек, и динамическая память кучи, куда я буду аллоцировать структуры для многопоточности. Статическую память мы выделяем еще на этапе загрузки (и вообще пока ограничились 4 МиБ, потому что ядро в них помещается) и в целом с ней сейчас проблем не возникает. Также на данном этапе у меня нет устройств DMA, поэтому все предельно просто, зато понятно.
Я отдал под кучу 512 МиБ самого верхнего пространства памяти ядра (0xE0000000), на 4 МиБ ниже храню карту использования кучи (0xDFC00000). Для описания состояния я как и для физической памяти использую битовую карту, но состояния в ней всего 2 — занято/свободно. Размер блока памяти составляет 64 байта — это много для небольших переменных типа u32, u8, но, пожалуй, оптимально для хранения структур данных. Все-таки вряд ли нам потребуется хранить в куче одиночные переменные, сейчас ее основное предназначение — хранить структуры контекстов для мультизадачности.
Блоки по 64 байта сгруппированы в структуры, описывающие состояние целой страницы 4 МиБ, поэтому мы можем выделять как малые объемы памяти, так и большие, в несколько страниц. Я оперирую следующими терминами: chunk- 64 байта, pack — 2 КиБ (один u32 — 64 байта * 32 бита в упаковке), page — 4 МиБ.
#[repr(packed)]
#[derive(Copy, Clone)]
struct HeapPageInfo {
//every bit represents 64 bytes chunk of memory. 0 is free, 1 is busy
//u32 size is 4 bytes, so page information total size is 8KiB
pub _4mb_by_64b: [u32; 2048],
}
#[repr(packed)]
#[derive(Copy, Clone)]
struct HeapInfo {
//Here we can know state of any 64 bit chunk in any of 128 4-MiB pages
//Page information total size is 8KiB, so information about 128 pages requires 1MiB reserved data
pub _512mb_by_4mb: [HeapPageInfo; 128],
}При запросе памяти от аллокатора я рассматриваю три случая, в зависимости от гранулярности:
- От аллокатора пришел запрос на память меньше 2 КиБ. Необходимо найти пак, в котором в котором будет свободно [размер / 64, любой ненулевой остаток добавляет единицу] чанков подряд, пометить эти чанки как занятые, вернуть адрес первого чанка.
- От аллокатора пришел запрос на память меньше 4 МиБ, но больше 2 КиБ. Необходимо найти страницу, у которой свободно [размер / 2048, любой ненулевой остаток добавляет единицу] паков подряд. Пометить [размер / 2048] паков как занятые, если есть остаток — пометить [остаток] чанков в последнем паке как занятые.
- От аллокатора пришел запрос на память больше 4 МиБ. Найти [размер / 4 Ми, любой ненулевой остаток добавляет единицу] страниц подряд, пометить [размер / 4 Ми] страниц как занятые, если есть остаток — пометить [остаток] паков как занятые. В последнем паке пометить остаток чанков как занятые.
Поиск свободных участков так же зависит от гранулярности — выбирается массив для перебора или битовые маски. При любом выходе за границы случается OOM. При деаллокации применяется аналогичный алгоритм, только для пометки освобожденными. Освобожденная память не обнуляется. Весь код большой, уберу под спойлер.
//512 MiB should be enough for kernel heap. If not - ooops...
pub const KHEAP_START: usize = 0xE0000000;
//I will keep 1MiB info about my heap in separate 4MiB page before heap at this point
pub const KHEAP_INFO_ADDR: usize = 0xDFC00000;
pub const KHEAP_CHUNK_SIZE: usize = 64;
pub fn init() {
KHEAP_INFO.lock().init();
}
#[repr(packed)]
#[derive(Copy, Clone)]
struct HeapPageInfo {
//every bit represents 64 bytes chunk of memory. 0 is free, 1 is busy
//u32 size is 4 bytes, so page information total size is 8KiB
pub _4mb_by_64b: [u32; 2048],
}
impl HeapPageInfo {
pub fn init(&mut self) {
for i in 0..2048 {
self._4mb_by_64b[i] = 0;
}
}
pub fn mark_chunks_used(&mut self, _32pack: usize, chunk: usize, n: usize) {
let mask: u32 = 0xFFFFFFFF >> (32 - n) << chunk;
self._4mb_by_64b[_32pack] = self._4mb_by_64b[_32pack] | mask;
}
pub fn mark_chunks_free(&mut self, _32pack: usize, chunk: usize, n: usize) {
let mask: u32 = 0xFFFFFFFF >> (32 - n) << chunk;
self._4mb_by_64b[_32pack] = self._4mb_by_64b[_32pack] ^ mask;
}
pub fn empty(&self) -> bool {
for i in 0..2048 {
if self._4mb_by_64b[i] != 0 {
return false
}
}
true
}
}
#[repr(packed)]
#[derive(Copy, Clone)]
struct HeapInfo {
//Here we can know state of any 64 bit chunk in any of 128 4-MiB pages
//Page information total size is 8KiB, so information about 128 pages requires 1MiB reserved data
pub _512mb_by_4mb: [HeapPageInfo; 128],
}
impl HeapInfo {
pub fn init(&mut self) {
for i in 0..128 {
self._512mb_by_4mb[i].init();
}
}
// returns page number
pub fn find_free_pages_of_size(&self, n: usize) -> usize {
if n >= 128 {
0xFFFFFFFF
} else {
let mut start_page: usize = 0xFFFFFFFF;
let mut current_page: usize = 0xFFFFFFFF;
for page in 0..128 {
if self._512mb_by_4mb[page].empty() {
if current_page - start_page == n {
return start_page
}
if start_page == 0xFFFFFFFF {
start_page = page;
}
current_page = page;
} else {
start_page = 0xFFFFFFFF;
current_page = 0xFFFFFFFF;
}
}
0xFFFFFFFF
}
}
// returns (page number, 32pack number)
pub fn find_free_packs_of_size(&self, n: usize) -> (usize, usize) {
if n < 2048 {
for page in 0..128 {
let mut start_pack: usize = 0xFFFFFFFF;
let mut current_pack: usize = 0xFFFFFFFF;
for _32pack in 0..2048 {
let _32pack_info = self._512mb_by_4mb[page]._4mb_by_64b[_32pack];
if _32pack_info == 0 {
if current_pack - start_pack == n {
return (page, start_pack)
}
if start_pack == 0xFFFFFFFF {
start_pack = _32pack;
}
current_pack = _32pack;
} else {
start_pack = 0xFFFFFFFF;
current_pack = 0xFFFFFFFF;
}
}
}
(0xFFFFFFFF, 0xFFFFFFFF)
} else {
(0xFFFFFFFF, 0xFFFFFFFF)
}
}
// returns (page number, 32pack number, chunk number)
pub fn find_free_chunks_of_size(&self, n: usize) -> (usize, usize, usize) {
if n < 32 {
for page in 0..128 {
for _32pack in 0..2048 {
let _32pack_info = self._512mb_by_4mb[page]._4mb_by_64b[_32pack];
let mask: u32 = 0xFFFFFFFF >> (32 - n);
for chunk in 0..(32-n) {
if ((_32pack_info >> chunk) & mask) ^ mask == mask {
return (page, _32pack, chunk)
}
}
}
}
(0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF)
} else {
(0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF)
}
}
fn mark_chunks_used(&mut self, page: usize, _32pack: usize, chunk: usize, n: usize) {
self._512mb_by_4mb[page].mark_chunks_used(_32pack, chunk, n);
}
fn mark_chunks_free(&mut self, page: usize, _32pack: usize, chunk: usize, n: usize) {
self._512mb_by_4mb[page].mark_chunks_free(_32pack, chunk, n);
}
fn mark_packs_used(&mut self, page: usize, _32pack:usize, n: usize) {
for i in _32pack..(_32pack + n) {
self._512mb_by_4mb[page]._4mb_by_64b[i] = 0xFFFFFFFF;
}
}
fn mark_packs_free(&mut self, page: usize, _32pack:usize, n: usize) {
for i in _32pack..(_32pack + n) {
self._512mb_by_4mb[page]._4mb_by_64b[i] = 0;
}
}
}
use lazy_static::lazy_static;
use spin::Mutex;
lazy_static! {
static ref KHEAP_INFO: Mutex<&'static mut HeapInfo> =
Mutex::new(unsafe { &mut *(KHEAP_INFO_ADDR as *mut HeapInfo) });
}
fn allocate_n_chunks_less_than_pack(n: usize, align: usize) -> *mut u8 {
let mut heap_info = KHEAP_INFO.lock();
let (page, _32pack, chunk) = heap_info.find_free_chunks_of_size(n);
if page == 0xFFFFFFFF {
core::ptr::null_mut()
} else {
let tptr: usize = KHEAP_START + 0x400000 * page + _32pack * 32 * 64 + chunk * 64;
let res = tptr % align;
let uptr = if res == 0 { tptr } else { tptr + align - res };
//check bounds: more than start and less than 4GiB - 64B
//but according to chunks error should never happen
if uptr >= KHEAP_START && uptr <= 0xFFFFFFFF - 64 * n {
heap_info.mark_chunks_used(page, _32pack, chunk, n);
uptr as *mut u8
} else {
core::ptr::null_mut()
}
}
}
fn allocate_n_chunks_less_than_page(n: usize, align: usize) -> *mut u8 {
let mut heap_info = KHEAP_INFO.lock();
let packs_n: usize = n / 32;
let lost_chunks = n - packs_n * 32;
let mut packs_to_alloc = packs_n;
if lost_chunks != 0 {
packs_to_alloc += 1;
}
let (page, pack) = heap_info.find_free_packs_of_size(packs_to_alloc);
if page == 0xFFFFFFFF {
core::ptr::null_mut()
} else {
let tptr: usize = KHEAP_START + 0x400000 * page + pack * 32 * 64;
let res = tptr % align;
let uptr = if res == 0 { tptr } else { tptr + align - res };
//check bounds: more than start and less than 4GiB - 64B
//but according to chunks error should never happen
if uptr >= KHEAP_START && uptr <= 0xFFFFFFFF - 64 * n {
heap_info.mark_packs_used(page, pack, packs_n);
if lost_chunks != 0 {
heap_info.mark_chunks_used(page, pack + packs_to_alloc, 0, lost_chunks);
}
uptr as *mut u8
} else {
core::ptr::null_mut()
}
}
}
//unsupported yet
fn allocate_n_chunks_more_than_page(n: usize, align: usize) -> *mut u8 {
let mut heap_info = KHEAP_INFO.lock();
let packs_n: usize = n / 32;
let lost_chunks = n - packs_n * 32;
let mut packs_to_alloc = packs_n;
if lost_chunks != 0 {
packs_to_alloc += 1;
}
let pages_n: usize = packs_to_alloc / 2048;
let mut lost_packs = packs_to_alloc - pages_n * 2048;
let mut pages_to_alloc = pages_n;
if lost_packs != 0 {
pages_to_alloc += 1;
}
if lost_chunks != 0 {
lost_packs -= 1;
}
let page = heap_info.find_free_pages_of_size(pages_to_alloc);
if page == 0xFFFFFFFF {
core::ptr::null_mut()
} else {
let tptr: usize = KHEAP_START + 0x400000 * page;
let res = tptr % align;
let uptr = if res == 0 { tptr } else { tptr + align - res };
//check bounds: more than start and less than 4GiB - 64B * n
//but according to chunks error should never happen
if uptr >= KHEAP_START && uptr <= 0xFFFFFFFF - 64 * n {
for i in page..(page + pages_n) {
heap_info.mark_packs_used(i, 0, 2048);
}
if lost_packs != 0 {
heap_info.mark_packs_used(page + pages_to_alloc, 0, lost_packs);
}
if lost_chunks != 0 {
heap_info.mark_chunks_used(page + pages_to_alloc, lost_packs, 0, lost_chunks);
}
uptr as *mut u8
} else {
core::ptr::null_mut()
}
}
}
// returns pointer
pub fn allocate_n_chunks(n: usize, align: usize) -> *mut u8 {
if n < 32 {
allocate_n_chunks_less_than_pack(n, align)
} else if n < 32 * 2048 {
allocate_n_chunks_less_than_page(n, align)
} else {
allocate_n_chunks_more_than_page(n, align)
}
}
pub fn free_chunks(ptr: usize, n: usize) {
let page: usize = (ptr - KHEAP_START) / 0x400000;
let _32pack: usize = ((ptr - KHEAP_START) - (page * 0x400000)) / (32 * 64);
let chunk: usize = ((ptr - KHEAP_START) - (page * 0x400000) - (_32pack * (32 * 64))) / 64;
let mut heap_info = KHEAP_INFO.lock();
if n < 32 {
heap_info.mark_chunks_free(page, _32pack, chunk, n);
} else if n < 32 * 2048 {
let packs_n: usize = n / 32;
let lost_chunks = n - packs_n * 32;
heap_info.mark_packs_free(page, _32pack, packs_n);
if lost_chunks != 0 {
heap_info.mark_chunks_free(page, _32pack + packs_n, 0, lost_chunks);
}
} else {
let packs_n: usize = n / 32;
let pages_n: usize = packs_n / 2048;
let lost_packs: usize = packs_n - pages_n * 2048;
let lost_chunks = n - packs_n * 32;
for i in page..(page + pages_n) {
heap_info.mark_packs_free(i, 0, 2048);
}
if lost_packs != 0 {
heap_info.mark_packs_free(page + pages_n, 0, lost_packs);
}
if lost_chunks != 0 {
heap_info.mark_chunks_free(page + pages_n, packs_n, 0, lost_chunks);
}
}
}Аллокация и Page fault
Для того, чтобы использовать кучу, необходим аллокатор. Его добавление откроет для нас вектор, деревья, хэш-таблицы, коробки и прочее, без чего дальше жить практически невозможно. Как только мы подключим модуль alloc и объявим глобальный аллокатор, жизнь сразу станет проще.
Реализация аллокатора очень проста — она просто обращается к описанному выше механизму.
use alloc::alloc::{GlobalAlloc, Layout};
pub struct Os1Allocator;
unsafe impl Sync for Os1Allocator {}
unsafe impl GlobalAlloc for Os1Allocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
use super::logical::{KHEAP_CHUNK_SIZE, allocate_n_chunks};
let size = layout.size();
let mut chunk_count: usize = 1;
if size > KHEAP_CHUNK_SIZE {
chunk_count = size / KHEAP_CHUNK_SIZE;
if KHEAP_CHUNK_SIZE * chunk_count != size {
chunk_count += 1;
}
}
allocate_n_chunks(chunk_count, layout.align())
}
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
use super::logical::{KHEAP_CHUNK_SIZE, free_chunks};
let size = layout.size();
let mut chunk_count: usize = 1;
if size > KHEAP_CHUNK_SIZE {
chunk_count = size / KHEAP_CHUNK_SIZE;
if KHEAP_CHUNK_SIZE * chunk_count != size {
chunk_count += 1;
}
}
free_chunks(ptr as usize, chunk_count);
}
}Включается аллокатор в lib.rs следующим образом:
#![feature(alloc, alloc_error_handler)]
extern crate alloc;
#[global_allocator]
static ALLOCATOR: memory::allocate::Os1Allocator = memory::allocate::Os1Allocator;И при попытке просто так аллоцироваться мы получим Page fault exception, ведь мы еще не проработали выделение виртуальной памяти. Ну как же так! Что ж, придется возвращаться к материалу предыдущей статьи и дописывать исключения. Я решил реализовать ленивую аллокацию виртуальной памяти, то есть чтобы страница выделялась не в момент запроса памяти, а в момент попытки обращения к ней. Благо, процессор x86 разрешает и даже поощряет это. После обработки Page fault он возвращается к той инструкции, которая вызвала исключение, и выполняет ее повторно, а еще предоставляет в обработчик исключения всю необходимую информацию — в стеке будет находиться код ошибки, по которому можно восстановить картину, а в регистре CR2 — виртуальный адрес, по которому отсутствует страница.
Сначала сохраним состояние процессора, а то мало ли что случится. Достанем код ошибки из стека со смещением 32 (мы сложили все регистры в стек, чтобы позже восстановить состояние процессора, поэтому нужно смещение в 32 байта), передадим как второй аргумент. Виртуальный адрес передадим как первый аргумент и вызовем обработчик в Rust. После обработки главное не забыть восстановить состояние и очистить код ошибки, чтобы указатель стека стоял на значении адреса возврата. К сожалению, нигде не написано, что перед iret нужно чистить код ошибки, поэтому я долго думал, почему у меня после Page fault сразу возникает Protection fault. Так что если вы столкнулись с непонятным Protection fault — вероятно, у вас в стеке еще лежит код ошибки.
eE_page_fault:
pushad
mov eax, [esp + 32]
push eax
mov eax, cr2
push eax
call kE_page_fault
pop eax
pop eax
popad
add esp, 4
iretв Rust обработчик разбирает код ошибки и преобразует его во флаги, которые необходимы таблице страниц. Я делаю это для простоты, чтобы не отслеживать адресное пространство. Также обработчик запрашивает свободную и доступную физическую страницу у менеджера физической памяти. Полученный адрес передается в менеджер виртуальной памяти для аллокации с нужными флагами.
bitflags! {
struct PFErrorCode: usize {
const PROTECTION = 1; //1 - protection caused, 0 - not present page caused
const WRITE = 1 << 1; //1 - write caused, 0 - read caused
const USER_MODE = 1 << 2; //1 - from user mode, 0 - from kernel
const RESERVED = 1 << 3; //1 - reserved page (PAE/PSE), 0 - not
const INSTRUCTION = 1 << 4; //1 - instruction fetch caused, 0 - not
}
}
impl PFErrorCode {
pub fn to_pd_flags(&self) -> super::super::paging::PDEntryFlags {
use super::super::paging;
let mut flags = paging::PDEntryFlags::empty();
if self.contains(PFErrorCode::WRITE) {
flags.set(paging::PDEntryFlags::WRITABLE, true);
}
if self.contains(PFErrorCode::USER_MODE) {
flags.set(paging::PDEntryFlags::USER_ACCESSIBLE, true);
}
flags
}
}
#[no_mangle]
pub unsafe extern fn kE_page_fault(ptr: usize, code: usize) {
use super::super::paging;
println!("Page fault occured at addr 0x{:X}, code {:X}", ptr, code);
let phys_address = crate::memory::physical::alloc_page();
let code_flags: PFErrorCode = PFErrorCode::from_bits(code).unwrap();
if !code_flags.contains(PFErrorCode::PROTECTION) {
//page not presented, we need to allocate the new one
let mut flags: paging::PDEntryFlags = code_flags.to_pd_flags();
flags.set(paging::PDEntryFlags::HUGE_PAGE, true);
paging::allocate_page(phys_address, ptr, flags);
println!("Page frame allocated at Paddr {:#X} Laddr {:#X}", phys_address, ptr);
} else {
panic!("Protection error occured, cannot handle yet");
}
}Возврата физической памяти на данный момент не происходит, только возврат виртуальной. Что ж, теперь можно проверить как работает наша куча. Для этого я создам вектор большого размера и заполню его числами. После этого я создам второй вектор меньшего размера и проверю, какие виртуальные адреса занимают оба вектора. Если все произойдет правильно, то второй вектор должен занять память, освобожденную при переаллокации первого вектора с его ростом:
println!("memory: total {} used {} reserved {} free {}", memory::physical::total(), memory::physical::used(), memory::physical::reserved(), memory::physical::free());
use alloc::vec::Vec;
let mut vec: Vec<usize> = Vec::new();
for i in 0..1000000 {
vec.push(i);
}
println!("vec len {}, ptr is {:?}", vec.len(), vec.as_ptr());
println!("Still works, check reusage!");
let mut vec2: Vec<usize> = Vec::new();
for i in 0..10 {
vec2.push(i);
}
println!("vec2 len {}, ptr is {:?}, vec is still here? {}", vec2.len(), vec2.as_ptr(), vec.get(1000).unwrap());
println!("Still works!");
println!("memory: total {} used {} reserved {} free {}", memory::physical::total(), memory::physical::used(), memory::physical::reserved(), memory::physical::free());Вот что получилось в результате:
Как видим, аллокация памяти отрабатывает, хотя конечно миллионный цикл с большим количеством реаллокаций занимает продолжительное время. Вектор с миллионом целых после всех аллокаций занимает адрес 3,5 ГиБ + 3 МиБ, как и ожидалось. Первый мегабайт кучи был освобожден и в его адресе 3,5 ГиБ разместился второй маленький вектор.
IRQ 1 и непонятные символы — реакция моего ядра на прерывания от клавиш Alt + PrntScrn :)
Итак, мы получили работающую кучу, а значит и структуры данных Rust — теперь мы можем создавать сколько угодно объектов, а значит — можем хранить состояние задач, которые выполняет наш процессор!
В следующей статье я расскажу о том, как реализовать базовую многозадачность и запустить выполняться две глупые функции в параллельных потоках на одном процессоре.
Спасибо за внимание!
Автор: Аксененко Роман
