Geekly articles weekly

OS1: kernel primitif di Rust untuk x86. Bagian 3. Kartu memori, pengecualian kesalahan halaman, tumpukan dan alokasi

Bagian pertama
Bagian kedua


Topik pembicaraan hari ini adalah bekerja dengan memori. Saya akan berbicara tentang menginisialisasi direktori halaman, memetakan memori fisik, mengelola virtual dan tumpukan organisasi saya untuk pengalokasi.


Seperti yang saya katakan di artikel pertama, saya memutuskan untuk menggunakan halaman 4 MB untuk menyederhanakan hidup saya dan tidak harus berurusan dengan tabel hirarkis. Di masa depan, saya berharap untuk membuka halaman 4 KB, seperti kebanyakan sistem modern. Saya bisa menggunakan yang sudah jadi (misalnya, pengalokasi blok seperti itu ), tetapi menulis sendiri sedikit lebih menarik dan saya ingin memahami sedikit lebih banyak bagaimana memori hidup, jadi saya punya sesuatu untuk memberitahu Anda.


Terakhir kali saya memilih metode setup_pd yang bergantung pada arsitektur dan ingin melanjutkannya, ada satu detail lagi yang tidak saya bahas dalam artikel sebelumnya - output VGA menggunakan Rust dan println macro standar. Karena implementasinya sepele, saya akan menghapusnya di bawah spoiler. Kode tersebut ada dalam paket debug.


Cetak makro
#[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(); }

Sekarang, dengan hati nurani yang bersih, saya kembali ke memori.


Inisialisasi Direktori Halaman


Metode kmain kami mengambil tiga argumen sebagai input, salah satunya adalah alamat virtual dari tabel halaman. Untuk menggunakannya nanti untuk alokasi dan manajemen memori, Anda perlu menentukan struktur catatan dan direktori. Untuk x86, direktori Halaman dan tabel Halaman dijelaskan dengan cukup baik, jadi saya akan membatasi diri hanya untuk pengantar kecil. Entri direktori Halaman adalah struktur ukuran penunjuk, bagi kami ini adalah 4 byte. Nilai tersebut berisi alamat fisik halaman 4KB. Byte terkecil dari catatan dicadangkan untuk bendera. Mekanisme untuk mengubah alamat virtual menjadi alamat fisik terlihat seperti ini (dalam kasus granularitas 4 MB saya, perubahan terjadi oleh 22 bit. Untuk rincian lainnya, perubahan akan berbeda dan tabel hirarkis akan digunakan!):


Alamat virtual 0xC010A110 -> Dapatkan indeks dalam direktori dengan memindahkan alamat 22 bit ke kanan -> indeks 0x300 -> Dapatkan alamat fisik halaman dengan indeks 0x300, centang bendera dan status -> 0x1000000 -> Ambil 22 bit bawah alamat virtual sebagai offset, tambahkan ke alamat fisik halaman -> 0x1000000 + 0x10A110 = alamat fisik dalam memori 0x110A110

Untuk mempercepat akses, prosesor menggunakan TLB - terjemahan lookaside buffer, yang menyimpan alamat halaman.


Jadi, inilah cara direktori saya dan entri-entrinya dijelaskan, dan metode setup_pd diimplementasikan. Untuk menulis halaman, metode "konstruktor" diimplementasikan, yang menjamin penyelarasan sebesar 4 KB dan mengatur flag, dan metode untuk mendapatkan alamat fisik halaman. Direktori hanyalah sebuah array dari 1024 entri empat byte. Direktori dapat mengaitkan alamat virtual dengan halaman menggunakan metode 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); }

Saya sangat canggung membuat inisialisasi statis awal alamat tidak ada, jadi saya akan berterima kasih jika Anda akan menulis kepada saya bagaimana itu kebiasaan di komunitas Rust untuk melakukan inisialisasi tersebut dengan penugasan kembali tautan.


Sekarang kita dapat mengelola halaman dari kode tingkat tinggi, kita dapat beralih ke kompilasi inisialisasi memori. Ini akan terjadi dalam dua tahap: melalui pemrosesan kartu memori fisik dan menginisialisasi manajer virtual


  match mb_magic { 0x2BADB002 => { println!("multibooted v1, yeah, reading mb info"); boot::init_with_mb1(mb_pointer); }, . . . . . . } memory::init();

Kartu memori GRUB dan kartu memori fisik OS1


Untuk mendapatkan kartu memori dari GRUB, pada tahap boot saya mengatur flag yang sesuai di header, dan GRUB memberi saya alamat fisik struktur. Saya memindahkannya dari dokumentasi resmi ke notasi Rust, dan juga menambahkan metode untuk beralih dengan nyaman di kartu memori. Sebagian besar struktur GRUB tidak akan diisi, dan pada tahap ini tidak terlalu menarik bagi saya. Yang utama adalah saya tidak ingin menentukan jumlah memori yang tersedia secara manual.


Ketika menginisialisasi melalui Multiboot, pertama-tama kita mengubah alamat fisik menjadi virtual. Secara teoritis, GRUB dapat memposisikan struktur di mana saja, jadi jika alamat melampaui halaman, Anda perlu mengalokasikan halaman virtual di direktori Halaman. Dalam praktiknya, struktur hampir selalu terletak di sebelah megabyte pertama, yang telah kami alokasikan pada tahap boot. Untuk berjaga-jaga, kami memeriksa tanda bahwa kartu memori ada dan melanjutkan analisisnya.


 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"); } }

Kartu memori adalah daftar tertaut yang alamat fisik awalnya ditentukan dalam struktur dasar (jangan lupa untuk menerjemahkan semuanya menjadi yang virtual) dan ukuran array dalam byte. Anda harus mengulang daftar berdasarkan ukuran masing-masing elemen, karena secara teoritis ukurannya dapat berbeda. Seperti inilah bentuk iterasi:


 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) } }

Ketika mem-parsing kartu memori, kita beralih melalui struktur GRUB dan mengubahnya menjadi bitmap, yang OS1 akan bekerja dengan untuk mengelola memori fisik. Saya memutuskan untuk membatasi diri pada serangkaian kecil nilai yang tersedia untuk kontrol - bebas, sibuk, dipesan, tidak tersedia, meskipun GRUB dan BIOS menyediakan lebih banyak opsi. Jadi, kami mengulang entri peta dan mengonversi statusnya dari nilai GRUB / BIOS ke nilai untuk 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 } }

Memori fisik dikelola dalam modul memori :: fisik, yang kami namakan metode peta di atas, meneruskannya alamat wilayah, panjang dan statusnya. Semua 4 GB memori berpotensi tersedia untuk sistem dan dibagi menjadi empat megabyte halaman diwakili oleh dua bit dalam bitmap, yang memungkinkan Anda untuk menyimpan 4 status untuk 1024 halaman. Secara total, konstruksi ini membutuhkan 256 byte. Bitmap mengarah ke fragmentasi memori yang mengerikan, tetapi itu dapat dimengerti dan mudah diimplementasikan, yang merupakan hal utama untuk tujuan saya.


Saya akan menghapus implementasi bitmap di bawah spoiler agar tidak mengacaukan artikel. Struktur ini dapat menghitung jumlah kelas dan memori bebas, menandai halaman dengan indeks dan alamat, dan juga mencari halaman gratis (ini akan diperlukan di masa depan untuk mengimplementasikan heap). Kartu itu sendiri adalah array dari elemen 64 u32, untuk mengisolasi dua bit yang diperlukan (blok), konversi ke chunk yang disebut (indeks dalam array, pengemasan 16 blok) dan blok (posisi bit di chunk) digunakan.


Bitmap memori fisik
 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 } }

Dan sekarang kita sampai pada analisis satu elemen peta. Jika elemen peta menggambarkan area memori kurang dari satu halaman 4 MB atau sama dengan itu, kami menandai halaman ini secara keseluruhan. Jika lebih - kocok menjadi 4 MB dan tandai setiap bagian secara terpisah melalui rekursi. Pada tahap inisialisasi bitmap, kami menganggap semua bagian dari memori tidak dapat diakses, sehingga ketika kartu habis, misalnya, pada 128 MB, bagian yang tersisa ditandai sebagai tidak dapat diakses.


 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); } }

Tumpukan dan kelola dia


Manajemen memori virtual saat ini terbatas hanya untuk manajemen tumpukan, karena kernel tidak tahu banyak. Di masa depan, tentu saja, perlu untuk mengatur seluruh memori, dan manajer kecil ini akan ditulis ulang. Namun, saat ini, yang saya butuhkan adalah memori statis, yang berisi kode yang dapat dieksekusi dan tumpukan, dan memori tumpukan dinamis, di mana saya akan mengalokasikan struktur untuk multithreading. Kami mengalokasikan memori statis pada tahap boot (dan sejauh ini kami telah membatasi 4 MB, karena kernel cocok untuk mereka) dan secara umum tidak ada masalah dengan itu sekarang. Juga, pada tahap ini, saya tidak memiliki perangkat DMA, jadi semuanya sangat sederhana, tetapi dapat dimengerti.


Saya memberi 512 MB ruang memori kernel paling atas (0xE0000000) ke heap, saya menyimpan peta penggunaan heap (0xDFC00000) 4 MB lebih rendah. Saya menggunakan bitmap untuk menggambarkan keadaan, seperti halnya untuk memori fisik, tetapi hanya ada 2 status di dalamnya - sibuk / gratis. Ukuran blok memori adalah 64 byte - ini banyak untuk variabel kecil seperti u32, u8, tetapi, mungkin, ini optimal untuk menyimpan struktur data. Namun, kecil kemungkinan bahwa kita perlu menyimpan variabel tunggal di heap, sekarang tujuan utamanya adalah menyimpan struktur konteks untuk multitasking.


Blok 64 byte dikelompokkan ke dalam struktur yang menggambarkan keadaan seluruh halaman 4 MB, sehingga kami dapat mengalokasikan memori dalam jumlah kecil dan besar ke beberapa halaman. Saya menggunakan istilah berikut: chunk - 64 bytes, paket - 2 KB (satu u32 - 64 bytes * 32 bit per paket), halaman - 4 MB.


 #[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], }

Saat meminta memori dari pengalokasi, saya mempertimbangkan tiga kasus, tergantung pada rinciannya:


  • Permintaan untuk memori kurang dari 2 KB datang dari pengalokasi. Anda perlu menemukan paket di mana ia akan [ukuran / 64 gratis, sisa non-nol menambahkan satu] potongan berturut-turut, tandai potongan ini sebagai sibuk, kembalikan alamat potongan pertama.
  • Permintaan datang dari pengalokasi untuk memori kurang dari 4 MB, tetapi lebih dari 2 KB. Anda perlu menemukan halaman dengan [ukuran / 2048 gratis, sisa bukan nol menambahkan satu] paket berturut-turut. Tandai [size / 2048] paket sebagai sibuk, jika ada sisa, tandai [sisa] potongan dalam paket terakhir sebagai sibuk.
  • Permintaan untuk memori lebih dari 4 MB datang dari pengalokasi. Cari [size / 4 Mi, sembarang saldo nol menambahkan satu] halaman berturut-turut, tandai halaman [size / 4 Mi] sebagai sibuk, jika ada paket [balance] tandai balance sebagai sibuk. Di paket terakhir, tandai sisa bidak sibuk.

Pencarian untuk area gratis juga tergantung pada granularity - array dipilih untuk iterasi atau bit mask. Setiap kali Anda pergi ke luar negeri, OOM terjadi. Saat deallokasi, algoritma yang sama digunakan, hanya untuk menandai dirilis. Memori yang dibebaskan tidak diatur ulang. Seluruh kode besar, saya akan meletakkannya di bawah spoiler.


Bitmap memori virtual
 //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); } } }

Alokasi dan kesalahan Halaman


Untuk menggunakan heap, Anda memerlukan pengalokasi. Menambahkannya akan membuka bagi kita vektor, pohon, tabel hash, kotak, dan lainnya, yang tanpanya mustahil untuk hidup. Segera setelah kita pasang modul alokasi dan mendeklarasikan pengalokasi global, hidup akan segera menjadi lebih mudah.


Implementasi pengalokasi sangat sederhana - hanya mengacu pada mekanisme yang dijelaskan di atas.


 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); } }

Alokasi di lib.rs dinyalakan sebagai berikut:


 #![feature(alloc, alloc_error_handler)] extern crate alloc; #[global_allocator] static ALLOCATOR: memory::allocate::Os1Allocator = memory::allocate::Os1Allocator;

Dan ketika kami mencoba untuk mengalokasikan diri kami sedemikian rupa, kami mendapatkan pengecualian kesalahan Halaman, karena kami belum mengerjakan alokasi memori virtual. Nah, bagaimana bisa begitu! Nah, Anda harus kembali ke materi artikel sebelumnya dan menambahkan pengecualian. Saya memutuskan untuk menerapkan alokasi memori virtual yang malas, yaitu, bahwa halaman tersebut dialokasikan bukan pada saat permintaan memori, tetapi pada saat upaya untuk mengaksesnya. Untungnya, prosesor x86 memungkinkan dan bahkan mendorong ini. 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());

:
OS1 heap


, , . 3,5 + 3 , . 3,5 .


IRQ 1 — Alt + PrntScrn :)


, , Rust — , — , !


, .


Terima kasih atas perhatian anda!

Source: https://habr.com/ru/post/id446214/

More articles:


All Articles