Entwicklung eines monolithischen Unix-ähnlichen Betriebssystems - Heap (4)

Im vorherigen Artikel haben wir das Kernel-Systemprotokoll implementiert. Jetzt ist es Zeit, einen dynamischen Speichermanager zu implementieren.

Inhaltsverzeichnis

1. Build-System (make, gcc, gas). Erster Start (Multiboot). Starten Sie (qemu). C-Bibliothek (strcpy, memcpy, strext).
2. C-Bibliothek (sprintf, strcpy, strcmp, strtok, va_list ...). Erstellen der Bibliothek im Kernelmodus und im Benutzeranwendungsmodus.
3. Das Kernel-Systemprotokoll. Videospeicher Ausgabe an das Terminal (kprintf, kpanic, kassert).
4. Dynamischer Speicher, Heap (kmalloc, kfree).
5. Organisation der Speicher- und Interrupt-Behandlung (GDT, IDT, PIC, Syscall). Ausnahmen
6. Virtueller Speicher (Seitenverzeichnis und Seitentabelle).
7. Prozess. Planer Multitasking. Systemaufrufe (kill, exit, ps).
8. Das Dateisystem des Kernels (initrd), elf und seiner Interna. Systemaufrufe (exec).
9. Zeichengerätetreiber. Systemaufrufe (ioctl, fopen, fread, fwrite). C-Bibliothek (fopen, fclose, fprintf, fscanf).
10. Shell als komplettes Programm für den Kernel.
11. Benutzerschutzmodus (Ring3). Aufgabenstatussegment (tss).

Dynamischer Kernelspeicher. Ein Haufen

Die Kernel-Heap-Oberfläche sieht folgendermaßen aus:

void *kmalloc(size_t size); void kfree(void *addr); 

Da es noch keine Heaps gibt, müssen Aufzeichnungen von belegten und freien Speicherbereichen gespeichert werden.
in einem Array von begrenzter Größe. Je kleiner die Abmessung ist, desto geringer ist die Heap-Kapazität um
kleine Fragmente. Unter Linux werden beispielsweise viele Kernelstrukturen wiederverwendbar gespeichert
Speicher, dessen Größe sich beim Freigeben nicht ändert (Platte). Aber davon sind wir noch weit entfernt,
weil Entwicklung ein iterativer Prozess ist.

Jedes Element, das ein Element einer Liste sein soll, die über ein Array organisiert ist
erforderlich, um eine Schnittstelle zu implementieren.

 struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed); 

In C gibt es keine Schnittstellen, diese werden jedoch nicht benötigt. Wir wandeln einfach den Zeiger eines Objekts auf den Typ struct slist_head_t * um, wenn dieses Objekt physisch so aussieht:

 struct my_list_entry_t { struct slist_head_t list_head; ... } 

Damit der verallgemeinerte Algorithmus jedoch die Dimension des Arrays kennt, in dem die Liste gespeichert wird
und die Größe seines Elements, das erste und letzte Element der Liste und die Adresse des Arrays, in dem
Wenn eine Liste gespeichert ist, benötigt jede Funktion der Betriebsliste einen anderen Zeiger
zur Listendefinitionsstruktur:

 struct slist_definition_t { size_t base; u_int slots; size_t slot_size; struct slist_head_t *head; struct slist_head_t *tail; }; 

Die Funktionen zum Bedienen der Liste sehen folgendermaßen aus:

 struct slist_head_t *slist_insert_entry_after(struct slist_definition_t *list, struct slist_head_t *pos); struct slist_head_t *slist_insert_entry_before(struct slist_definition_t *list, struct slist_head_t *pos); void slist_delete_entry(struct slist_definition_t *list, struct slist_head_t *entry); 

Funktionsalgorithmus einfügen:
Suchen Sie einen freien Steckplatz im Array.
Fülle es mit einem neuen Element.
Korrigieren Sie die Zeiger logisch (nicht physisch) benachbarter Listenelemente.
Slot als besetzt markieren.
Passen Sie den Anfang und das Ende der Liste an.

Der Algorithmus der Funktion, die aus der Liste entfernt werden soll:
Korrigieren Sie die Zeiger logisch (nicht physisch) benachbarter Listenelemente.
Passen Sie den Anfang und das Ende der Liste an.
Steckplatz als frei markieren.

Der dynamische Speicher wird durch eine Liste mit folgenden Elementen beschrieben:

 struct kheap_entry_t { struct slist_head_t list_head; /* should be at first */ size_t addr; /* physical address */ size_t size; /* memory block size */ bool is_buzy; /* whether block used */ } attribute(packed); 

Ein Array, das den dynamischen Speicher aus solchen Datensätzen beschreibt, sieht folgendermaßen aus:

 struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES]; 

Das Definieren einer Liste von Speicherbereichen sieht folgendermaßen aus:

 struct slist_definition_t kheap_list = { .head = null, .tail = null, .slot_size = sizeof(struct kheap_entry_t), .slots = KHEAP_MAX_ENTRIES, .base = (size_t)kheap_blocks}; 

Wir haben also das dynamische Gedächtnis beschrieben. Der gesamte Speicher innerhalb eines bestimmten Bereichs
ist in Blöcke beliebiger Größe unterteilt, von denen jeder entweder leer sein kann,
entweder beschäftigt. Zusätzlich wird jeder Block durch ein Array-Element mit dem Flag is_valid = true beschrieben.
Das ist ein Listenelement.

Betrachten Sie nun den einfachsten Heap-Allokator-Algorithmus (kmalloc):
Wenn keine freien Blöcke vorhanden sind, wählen Sie einen neuen Block mit der erforderlichen Größe aus (jedoch nicht mehr als die maximale Heap-Größe).

Ansonsten schauen wir uns alle freien Blöcke an. Wenn wir einen freien Block finden, schauen Sie sich seine Größe an. Wenn es reicht, nimm es. Wenn es einen Überschuss gibt, erstellen Sie einen neuen leeren Block mit der Größe des Überschusses. Andernfalls erweitern wir, wenn es nicht ausreicht und letzteres, die Heap-Grenze (aber nicht mehr als das Maximum).

 /* * Api - Kernel memory alloc */ extern void* kmalloc(size_t size) { struct kheap_entry_t* current_data = null; struct slist_head_t* current = null; struct slist_head_t* head = kheap_list.head; assert(size > 0); /* try to use free block */ for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->is_buzy) { continue; } /* check size is not enough */ if (current_data->size < size) { /* try to ask contribution from free left sibling */ if (current->prev != null) { /* left sibling has found */ struct slist_head_t* sibling = current->prev; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether left sibling is free */ if (!sibling_data->is_buzy) { /* ask lack from left sibling */ size_t lack = size - current_data->size; sibling_data->size -= lack; current_data->addr -= lack; current_data->size += lack; assert(current_data->size == size); /* whether left sibling is collapsed */ if (sibling_data->size == 0) { slist_delete_entry(&kheap_list, sibling); } /* occupy block */ current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to extend borders */ if (current->next == null) { size_t heap_end_addr = current_data->addr + current_data->size; size_t lack = size - current_data->size; /* check free memory size is enought */ if (heap_end_addr + lack < KHEAP_END_ADDR) { /* occupy block */ current_data->size += lack; current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } } else { /* occupy block */ current_data->is_buzy = true; size_t surplus = current_data->size - size; bool is_sibling_bizy = false; /* try to contribute free right sibling */ if (current->next != null) { /* sibling has found */ struct slist_head_t* sibling = current->next; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether sibling is free */ is_sibling_bizy = sibling_data->is_buzy; if (!is_sibling_bizy) { /* give surplus to right sibling */ current_data->size -= surplus; sibling_data->addr -= surplus; sibling_data->size += surplus; assert(current_data->size == size); } } /* try to give surplus to new right sibling */ if (current->next == null || is_sibling_bizy) { { struct slist_head_t* new_sibling; new_sibling = slist_insert_entry_after(&kheap_list, current); struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)new_sibling->data; if (new_sibling != null) { /* give surplus to new right sibling */ assert((size_t)new_sibling == (size_t)sibling_data); current_data->size -= surplus; assert(current_data->size > 0); sibling_data->is_buzy = false; sibling_data->addr = current_data->addr + current_data->size; sibling_data->size = surplus; } } } assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to alloc new block */ size_t heap_end_addr = KHEAP_START_ADDR; /* calculate heap end address */ if (kheap_list.tail) { current = kheap_list.tail; current_data = (struct kheap_entry_t*)current->data; heap_end_addr = current_data->addr + current_data->size; } /* check free memory size is enought */ if (heap_end_addr + size >= KHEAP_END_ADDR) { abort("heap size exceeded\n"); } /* allocate new heap memory block */ struct slist_head_t* tail = kheap_list.tail; current = slist_insert_entry_after(&kheap_list, kheap_list.tail); current_data = (struct kheap_entry_t*)current->data; assert((size_t)current == (size_t)current_data); current_data->addr = heap_end_addr; current_data->size = size; current_data->is_buzy = true; assert(current->next == null); assert(current->prev == tail); assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; } 

Der speicherfreie Algorithmus ist ähnlich (kfree):
Suchen Sie einen Block, dessen Adresse mit der freizugebenden Adresse beginnt. Überprüfen Sie, ob er beschäftigt ist. Als frei markieren.

Wenn es rechts oder links einen freien Nachbarn gibt, der sich in einem Block mit ihm vereinigt.

 /* * Api - Kernel memory free */ extern void kfree(void* addr) { struct slist_head_t* current = null; struct kheap_entry_t* current_data = null; struct slist_head_t* head = kheap_list.head; for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->addr == (size_t)addr && current_data->is_buzy) { struct slist_head_t* prev = current->prev; struct slist_head_t* next = current->next; struct kheap_entry_t* prev_data = prev != null ? (struct kheap_entry_t*)prev->data : null; struct kheap_entry_t* next_data = next != null ? (struct kheap_entry_t*)next->data : null; /* free block */ current_data->is_buzy = false; /* try to merge with free left sibling */ if (prev != null && !prev_data->is_buzy) { prev_data->size += current_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)current); } /* try to merge with free right sibling */ if (next != null && !next_data->is_buzy) { current_data->size += next_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)next); } return; } } abort("invalid address to free\n", addr); } 

Das ist alles. Bis zum nächsten Mal!

Referenzen

Öffnen Sie nun das Video-Tutorial
Und schauen Sie sich das Git-Repository parallel an (Sie benötigen einen Lektion4-Zweig).

Referenzliste

1. James Molloy. Rollen Sie Ihr eigenes UNIX-Klon-Betriebssystem.
2. Zähne. Assembler für DOS, Windows, Unix
3. Kalaschnikow. Assembler ist einfach!
4. Tanenbaum. Betriebssysteme. Implementierung und Entwicklung.
5. Robert Love. Linux-Kernel Beschreibung des Entwicklungsprozesses.