Первая часть Вторая часть Тема сегодняшнего разговора – работа с памятью.
Я расскажу об инициализации каталога страниц, отображении физической памяти, управлении виртуальной памятью и организации кучи для распределителя.
Как я говорил в первой статье, я решил использовать страницы по 4 МБ, чтобы облегчить себе жизнь и не иметь дело с иерархическими таблицами.
В будущем я надеюсь перейти на страницы размером 4 КБ, как в большинстве современных систем.
Я мог бы использовать готовый (например, такой распределитель блоков ), но писать своё было немного интереснее и хотелось немного больше понять, как живёт память, поэтому мне есть что вам рассказать.
В прошлый раз я остановился на архитектурно-зависимом методе setup_pd и хотел продолжить оттуда, но была еще одна деталь, которую я не раскрыл в предыдущей статье — вывод VGA с помощью Rust и стандартного макроса println. Поскольку реализация его тривиальна, помещу под спойлер.
Код находится в отладочном пакете.
Макрос println
Теперь с чистой совестью возвращаюсь к памяти.#[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 представляет собой структуру, основанную на размере указателя, для нас это 4 байта.
Значение содержит выровненный физический адрес страницы размером 4 КБ.
Младший байт записи зарезервирован для флагов.
Механизм преобразования виртуального адреса в физический выглядит следующим образом (в случае моей детализации 4 МБ сдвиг происходит на 22 бита.
Для других детализации сдвиг будет другой и будут использоваться иерархические таблицы!):
Виртуальный адрес 0xC010A110 -> Получить индекс в каталоге, сместив адрес на 22 бита вправо -> индекс 0x300 -> Получить физический адрес страницы по индексу 0x300, проверить флаги и статус -> 0x1000000 -> Взять младший 22 бита виртуального адреса в качестве смещения, добавляем к адресу физической страницы -> 0x1000000 + 0x10A110 = адрес физической памяти 0x110A110Для ускорения доступа процессор использует TLB — буфер трансляции, в который кэшируются адреса страниц.
Итак, вот как описан мой каталог и его записи, и реализован тот же метод 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 может найти структуру где угодно, поэтому, если адрес выходит за пределы страницы, ему необходимо выделить виртуальную страницу в каталоге страниц.
На практике структура почти всегда лежит рядом с первым мегабайтом, который мы уже выделили на этапе загрузки.
На всякий случай проверяем флаг наличия карты памяти и начинаем ее анализировать.
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, для которого мы вызываем метод карты выше, передавая ему адрес региона, его длину и состояние.
Все 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 МБ, поэтому мы можем распределять как небольшие объемы памяти, так и большие по нескольким страницам.
Я оперирую следующими условиями: чанк - 64 байта, пакет - 2 КБ (один u32 - 64 байта * 32 бита на пакет), страница - 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, любой ненулевой остаток добавляет один] пакетов подряд. Пометить пакеты [size/2048] как занятые, если есть остаток, пометить [оставшиеся] чанки в последнем пакете как занятые.
- От распределителя поступил запрос на память объемом более 4 МБ.
Найдите [размер/4 Mi, любой ненулевой остаток добавляет одну] страницу подряд, отметьте [размер/4 Mi] страницы как занятые, если есть остаток, отметьте пакеты [остаток] как занятые.
В последнем пакете отметьте остальные чанки как занятые.
Каждый раз, когда границы пересекаются, происходит ООМ.
При освобождении используется аналогичный алгоритм, только для пометки как освобожденного.
Освободившаяся память не сбрасывается.
Весь код большой, положу под спойлер.
Растровое изображение виртуальной памяти //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);
}
}
}
Ошибка распределения и страницы Чтобы использовать кучу, необходим распределитель.
Его добавление откроет векторы, деревья, хеш-таблицы, ящики и т. д., без которых уже практически невозможно жить.
Как только мы подключим модуль 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 error, потому что мы еще не отработали распределение виртуальной памяти.
Ну как же так! Что ж, придется вернуться к материалу предыдущей статьи и добавить исключения.
Я решил реализовать ленивое выделение виртуальной памяти, то есть чтобы страница выделялась не в момент запроса памяти, а в момент попытки доступа к ней.
К счастью, процессор x86 позволяет и даже поощряет это.
После обработки ошибки страницы он возвращается к инструкции, вызвавшей исключение, и выполняет ее снова, а также передает всю необходимую информацию обработчику исключения — в стеке будет код ошибки, по которому можно восстановить картинку, а Регистр CR2 будет содержать виртуальный адрес, для которого нет страницы.
Для начала сохраним состояние процессора, иначе никогда не знаешь, что будет. Возьмем код ошибки из стека по смещению 32 (мы помещаем в стек все регистры для последующего восстановления состояния процессора, поэтому нам нужно смещение в 32 байта), передадим его в качестве второго аргумента.
Мы передадим виртуальный адрес в качестве первого аргумента и вызовем обработчик в Rust. После обработки главное не забыть восстановить состояние и очистить код ошибки, чтобы указатель стека находился на значении адреса возврата.
К сожалению, нигде не написано, что перед иретом нужно сбрасывать код ошибки, поэтому я долго думал, почему у меня сразу после ошибки страницы появляется ошибка Protection. Так что, если вы столкнулись с непонятной ошибкой Защиты, у вас, вероятно, все еще есть код ошибки в вашем стеке.
eE_page_fault:
pushad
mov eax, [esp + 32]
push eax
Теги: #Процессоры #операционные системы #Rust #Системное программирование #x86 #Ассемблер
-
Игрушки Для 3D-Печати
19 Oct, 24 -
Iphone Делает Скриншоты Всего
19 Oct, 24 -
Выпуск Firefox 28
19 Oct, 24 -
Небольшое Улучшение Gmail
19 Oct, 24
