Erster Teil
Zweiter Teil

Das Thema des heutigen Gesprächs ist die Arbeit mit dem Gedächtnis. Ich werde über das Initialisieren des Seitenverzeichnisses, das Zuordnen des physischen Speichers, das Verwalten des virtuellen und meines Organisationsheaps für den Allokator sprechen.

Wie ich im ersten Artikel sagte, habe ich beschlossen, 4 MB Seiten zu verwenden, um mein Leben zu vereinfachen und mich nicht mit hierarchischen Tabellen befassen zu müssen. Ich hoffe, dass ich in Zukunft wie bei den meisten modernen Systemen auf 4-KB-Seiten gehen kann. Ich könnte ein fertiges verwenden (zum Beispiel einen solchen Blockzuweiser ), aber mein eigenes zu schreiben war etwas interessanter und ich wollte ein bisschen mehr verstehen, wie das Gedächtnis lebt, also habe ich Ihnen etwas zu sagen.

Als ich mich das letzte Mal für die architekturabhängige Methode setup_pd entschieden habe und damit fortfahren wollte, gab es jedoch ein weiteres Detail, das ich im vorherigen Artikel nicht behandelt habe - die VGA-Ausgabe mit Rust und dem Standard-Println-Makro. Da seine Implementierung trivial ist, werde ich es unter dem Spoiler entfernen. Der Code befindet sich im Debug-Paket.

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

Jetzt kehre ich mit gutem Gewissen in die Erinnerung zurück.

Seitenverzeichnis-Initialisierung

Unsere kmain-Methode hat drei Argumente als Eingabe verwendet, von denen eines die virtuelle Adresse der Seitentabelle ist. Um es später für die Zuordnung und Speicherverwaltung zu verwenden, müssen Sie die Struktur von Datensätzen und Verzeichnissen festlegen. Für x86 sind das Seitenverzeichnis und die Seitentabelle recht gut beschrieben, daher beschränke ich mich auf eine kleine Einführung. Der Seitenverzeichniseintrag ist eine Zeigergrößenstruktur, für uns sind es 4 Bytes. Der Wert enthält eine physikalische Adresse von 4 KB der Seite. Das niedrigstwertige Byte des Datensatzes ist für Flags reserviert. Der Mechanismus zum Konvertieren einer virtuellen Adresse in eine physische Adresse sieht folgendermaßen aus (bei meiner 4-MB-Granularität erfolgt die Verschiebung um 22 Bit. Bei anderen Granularitäten ist die Verschiebung unterschiedlich und es werden hierarchische Tabellen verwendet!):

Virtuelle Adresse 0xC010A110 -> Holen Sie sich den Index in das Verzeichnis, indem Sie die Adresse 22 Bit nach rechts verschieben -> Index 0x300 -> Holen Sie sich die physische Adresse der Seite durch Index 0x300, überprüfen Sie Flags und Status -> 0x1000000 -> Nehmen Sie die unteren 22 Bits der virtuellen Adresse als Offset, fügen Sie hinzu an die physikalische Adresse der Seite -> 0x1000000 + 0x10A110 = physikalische Adresse im Speicher 0x110A110

Um den Zugriff zu beschleunigen, verwendet der Prozessor TLB - Translation Lookaside Buffer, der Seitenadressen zwischenspeichert.

Hier ist also, wie mein Verzeichnis und seine Einträge beschrieben werden und die Methode setup_pd implementiert ist. Zum Schreiben einer Seite wird die Konstruktormethode implementiert, die die Ausrichtung um 4 KB und das Setzen von Flags garantiert, sowie eine Methode zum Abrufen der physischen Adresse der Seite. Ein Verzeichnis ist nur ein Array von 1024 Vier-Byte-Einträgen. Das Verzeichnis kann einer Seite mithilfe der Methode set_by_addr eine virtuelle Adresse zuordnen.

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

Ich habe die anfängliche statische Initialisierung sehr umständlich zu einer nicht vorhandenen Adresse gemacht. Ich wäre Ihnen dankbar, wenn Sie mir schreiben würden, wie es in der Rust-Community üblich ist, solche Initialisierungen mit Neuzuweisung von Links durchzuführen.

Jetzt, da wir Seiten aus Code auf hoher Ebene verwalten können, können wir mit der Kompilierung der Speicherinitialisierung fortfahren. Dies geschieht in zwei Schritten: durch Verarbeiten der physischen Speicherkarte und Initialisieren des virtuellen Managers

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

GRUB-Speicherkarte und OS1-Speicherkarte

Um eine Speicherkarte von GRUB zu erhalten, habe ich beim Booten das entsprechende Flag im Header gesetzt und GRUB hat mir die physikalische Adresse der Struktur gegeben. Ich habe es aus der offiziellen Dokumentation in die Rust-Notation portiert und Methoden hinzugefügt, um bequem über die Speicherkarte zu iterieren. Der größte Teil der GRUB-Struktur wird nicht gefüllt, und zu diesem Zeitpunkt ist es für mich nicht sehr interessant. Die Hauptsache ist, dass ich die Menge des verfügbaren Speichers nicht manuell bestimmen möchte.

Bei der Initialisierung über Multiboot konvertieren wir zuerst die physische Adresse in eine virtuelle. Theoretisch kann GRUB die Struktur an einer beliebigen Stelle positionieren. Wenn die Adresse über die Seite hinausgeht, müssen Sie eine virtuelle Seite im Seitenverzeichnis zuweisen. In der Praxis liegt die Struktur fast immer neben dem ersten Megabyte, das wir bereits beim Booten zugewiesen haben. Für alle Fälle überprüfen wir das Flag, dass die Speicherkarte vorhanden ist, und fahren mit ihrer Analyse fort.

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

Eine Speicherkarte ist eine verknüpfte Liste, für die die anfängliche physikalische Adresse in der Grundstruktur angegeben ist (vergessen Sie nicht, alles in virtuelle zu übersetzen) und die Größe des Arrays in Bytes. Sie müssen die Liste basierend auf der Größe jedes Elements durchlaufen, da sich ihre Größen theoretisch unterscheiden können. So sieht die Iteration aus:

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

Beim Parsen einer Speicherkarte durchlaufen wir die GRUB-Struktur und konvertieren sie in eine Bitmap, mit der OS1 den physischen Speicher verwaltet. Ich habe mich entschlossen, mich auf einen kleinen Satz verfügbarer Werte für die Steuerung zu beschränken - frei, beschäftigt, reserviert, nicht verfügbar, obwohl GRUB und BIOS mehr Optionen bieten. Also durchlaufen wir die Karteneinträge und konvertieren ihren Status von GRUB / BIOS-Werten in Werte für 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 } } 

Der physische Speicher wird im memory :: Physical-Modul verwaltet, für das wir die obige Map-Methode aufrufen und ihm die Adresse, die Länge und den Status der Region übergeben. Alle 4 GB Speicher, die dem System möglicherweise zur Verfügung stehen und in vier Megabyte-Seiten unterteilt sind, werden in einer Bitmap durch zwei Bits dargestellt, sodass Sie 4 Status für 1024 Seiten speichern können. Insgesamt benötigt diese Konstruktion 256 Bytes. Eine Bitmap führt zu einer schrecklichen Speicherfragmentierung, ist aber verständlich und einfach zu implementieren, was für meinen Zweck die Hauptsache ist.

Ich werde die Bitmap-Implementierung unter dem Spoiler entfernen, um den Artikel nicht zu überladen. Die Struktur kann die Anzahl der Klassen und den freien Speicher zählen, Seiten nach Index und Adresse markieren und auch nach freien Seiten suchen (dies wird in Zukunft benötigt, um den Heap zu implementieren). Die Karte selbst ist ein Array von 64 u32-Elementen. Um die erforderlichen zwei Bits (Blöcke) zu isolieren, wird die Umwandlung in den sogenannten Chunk (Index im Array, Packen von 16 Blöcken) und Block (Bitposition im Chunk) verwendet.

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

Und jetzt kommen wir zur Analyse eines Elements der Karte. Wenn ein Kartenelement einen Speicherbereich mit weniger als einer Seite von 4 MB oder mehr beschreibt, markieren wir diese Seite als Ganzes. Wenn mehr - in Stücke von 4 MB schlagen und jedes Stück durch Rekursion separat markieren. In der Phase der Initialisierung der Bitmap betrachten wir alle Speicherabschnitte als unzugänglich, sodass die verbleibenden Abschnitte als unzugänglich markiert werden, wenn die Karte beispielsweise 128 MB leer ist.

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

Haufen und sie verwalten

Die Verwaltung des virtuellen Speichers beschränkt sich derzeit nur auf die Heap-Verwaltung, da der Kernel nicht viel mehr weiß. In Zukunft wird es natürlich notwendig sein, den gesamten Speicher zu verwalten, und dieser kleine Manager wird neu geschrieben. Im Moment brauche ich jedoch nur statischen Speicher, der den ausführbaren Code und den Stapel enthält, sowie dynamischen Heap-Speicher, in dem ich die Strukturen für Multithreading zuweisen werde. Wir weisen statischen Speicher beim Booten zu (und bisher haben wir 4 MB begrenzt, weil der Kernel in sie passt) und im Allgemeinen gibt es jetzt keine Probleme damit. Außerdem habe ich zu diesem Zeitpunkt keine DMA-Geräte, daher ist alles sehr einfach, aber verständlich.

Ich habe dem Heap 512 MB des obersten Kernel-Speicherplatzes (0xE0000000) gegeben, ich speichere die Heap-Nutzungszuordnung (0xDFC00000) 4 MB niedriger. Ich benutze eine Bitmap, um den Zustand zu beschreiben, genau wie für den physischen Speicher, aber es gibt nur 2 Zustände darin - beschäftigt / frei. Die Größe des Speicherblocks beträgt 64 Byte - dies ist viel für kleine Variablen wie u32, u8, aber möglicherweise optimal zum Speichern von Datenstrukturen. Es ist jedoch unwahrscheinlich, dass wir einzelne Variablen auf dem Heap speichern müssen. Jetzt besteht der Hauptzweck darin, Kontextstrukturen für Multitasking zu speichern.

Blöcke mit 64 Bytes sind in Strukturen gruppiert, die den Status einer gesamten 4-MB-Seite beschreiben, sodass wir mehreren Seiten sowohl kleine als auch große Speichermengen zuweisen können. Ich verwende die folgenden Begriffe: Chunk - 64 Bytes, Pack - 2 KB (ein U32 - 64 Bytes * 32 Bit pro Paket), Seite - 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], } 

Wenn ich Speicher von einem Allokator anfordere, betrachte ich drei Fälle, abhängig von der Granularität:

• Eine Anforderung für einen Speicher von weniger als 2 KB kam vom Allokator. Sie müssen ein Paket finden, in dem es frei ist [Größe / 64, jeder Rest ungleich Null fügt eins hinzu], Chunks hintereinander markieren, diese Chunks als beschäftigt markieren und die Adresse des ersten Chunks zurückgeben.
• Vom Allokator wurde eine Anforderung für Speicher mit weniger als 4 MB, aber mehr als 2 KB gestellt. Sie müssen eine Seite mit kostenlosen [Größe / 2048, jeder Rest ungleich Null fügt eine hinzu] Packs in einer Reihe finden. Markieren Sie [size / 2048] -Packs als beschäftigt. Wenn ein Rest vorhanden ist, markieren Sie [rest] Chunks im letzten Pack als beschäftigt.
• Eine Anforderung für einen Speicher von mehr als 4 MB kam vom Allokator. Suchen Sie [Größe / 4 Mi, jeder Kontostand ungleich Null fügt eine] Seite in einer Reihe hinzu, markieren Sie [Größe / 4 Mi] Seiten als belegt, wenn ein Kontostand vorhanden ist - markieren Sie [Kontostand] -Pakete als belegt. Markieren Sie in der letzten Packung den Rest der Blöcke als beschäftigt.

Die Suche nach freien Bereichen hängt auch von der Granularität ab - ein Array wird für Iterations- oder Bitmasken ausgewählt. Wann immer Sie ins Ausland gehen, passiert OOM. Bei der Freigabe wird ein ähnlicher Algorithmus verwendet, nur zum Markieren freigegeben. Der freigegebene Speicher wird nicht zurückgesetzt. Der ganze Code ist groß, ich werde ihn unter den Spoiler stellen.

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

Zuordnung und Seitenfehler

Um den Heap verwenden zu können, benötigen Sie einen Allokator. Wenn wir es hinzufügen, öffnen sich für uns ein Vektor, Bäume, Hash-Tabellen, Kisten und mehr, ohne die es fast unmöglich ist, weiterzuleben. Sobald wir das Allokationsmodul anschließen und einen globalen Allokator deklarieren, wird das Leben sofort einfacher.

Die Implementierung des Allokators ist sehr einfach - sie bezieht sich einfach auf den oben beschriebenen Mechanismus.

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

Der Allokator in lib.rs wird wie folgt aktiviert:

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

Und wenn wir versuchen, uns nur so zuzuweisen, erhalten wir eine Seitenfehlerausnahme, da wir die Zuweisung des virtuellen Speichers noch nicht ausgearbeitet haben. Nun, wie so! Nun, Sie müssen zum Material des vorherigen Artikels zurückkehren und Ausnahmen hinzufügen. Ich habe mich für die verzögerte Zuweisung des virtuellen Speichers entschieden, dh, die Seite wurde nicht zum Zeitpunkt der Speicheranforderung, sondern zum Zeitpunkt des Zugriffsversuchs zugewiesen. Glücklicherweise erlaubt und fördert der x86-Prozessor dies. 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 — , — , !

, .

Vielen Dank für Ihre Aufmerksamkeit!