heap_allocator
1.0.0
Dies ist ein einfacher Heap-Allokator, den ich für ein Hobby-Betriebssystem geschrieben habe, an dem ich gearbeitet habe. Ich habe diesen Allokator mit sehr wenig Recherche geschrieben und er ist so einfach wie möglich verständlich gemacht. Ich denke, dieses Repository kann für diejenigen nützlich sein, die neu in der Betriebssystementwicklung sind (wie ich) oder an einer vereinfachten Version von Funktionen wie malloc und free interessiert sind.
Es gibt zwei Header-Dateien, die den Heap und die verknüpfte Liste definieren. So kompilieren Sie dieses Repository:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
Dadurch wird eine Demo des Allokators ausgeführt und einige Informationen ausgedruckt.
Um diesen Heap zu initialisieren, muss ein Speicherabschnitt bereitgestellt werden. In diesem Repository wird dieser Speicher von malloc bereitgestellt (ja, Zuweisung eines Heaps über Heap). In einer Betriebssystemeinstellung müssten einige Seiten zugeordnet und dem Heap bereitgestellt werden (ein Szenario). Beachten Sie, dass den Bins in der heap_t -Struktur auch Speicher zugewiesen werden muss.
Beim Aufruf der Funktion init_heap muss die Adresse der leeren Heap-Struktur (mit zugewiesenen Bin-Zeigern) angegeben werden. Die Funktion init_heap erstellt dann einen großen Block mit Header ( node_t struct) und einem Footer ( footer_t struct). Um die Größe dieses Blocks zu bestimmen, verwendet die Funktion die Konstante HEAP_INIT_SIZE . Dies wird zum start hinzugefügt, um zu bestimmen, wo der Heap endet.
Jeder Speicherblock hat am Anfang eine Knotenstruktur und am Ende eine Fußzeilenstruktur. Der Knoten enthält die Größe, unabhängig davon, ob der Block frei ist oder nicht, sowie zwei Zeiger, die in der doppelt verknüpften Liste (next und prev) verwendet werden. Die Fußzeilenstruktur enthält einfach einen Zeiger auf die Kopfzeile (wird beim Freigeben benachbarter Blöcke verwendet). Der Block am Ende des Heaps wird als „Wildnis“-Block bezeichnet. Es ist der größte Block und seine minimale und maximale Größe sind in heap.h definiert. Das Zusammenziehen und Erweitern des Heaps ist so einfach wie das Ändern der Größe dieses Wildnisstücks. Freie Speicherblöcke werden in „Bins“ gespeichert. Bei jedem Bin handelt es sich eigentlich nur um eine doppelt verknüpfte Liste von Knoten mit ähnlicher Größe. Die Heap-Struktur enthält eine definierte Anzahl von Bins ( BIN_COUNT in heap.h). Um zu bestimmen, in welcher Bin ein Block platziert werden soll, wird die Größe des Blocks durch die Funktion get_bin_index einem Bin-Index zugeordnet. Diese konsistente Binning-Funktion stellt sicher, dass auf Chunks auf definierte Weise zugegriffen und diese gespeichert werden können. Chunks werden sortiert, wenn sie in die Behälter eingefügt werden, sodass das Einfügen von Chunks nicht O(1) ist. Dies macht es jedoch viel einfacher, Chunks zu finden, die am besten passen. Beachten Sie, dass die Binning-Funktion so definiert werden kann, wie es der Benutzer dieses Heaps für richtig hält. Es kann von Vorteil sein, eine ausgefeiltere Binning-Funktion festzulegen, um das schnelle Abrufen von Chunks zu unterstützen.
Die Funktion heap_alloc übernimmt die Adresse der Heap-Struktur, aus der die Zuweisung erfolgen soll, und eine Größe. Die Funktion verwendet einfach get_bin_index um zu bestimmen, wo sich ein Block dieser Größe befinden SOLL. Natürlich kann es sein, dass kein Block dieser Größe vorhanden ist. Wenn im entsprechenden Bin keine Chunks gefunden werden, wird der nächste Bin überprüft. Dies wird so lange fortgesetzt, bis ein Block gefunden wird oder der letzte Behälter erreicht wird. In diesem Fall wird nur ein Teil des Speichers aus dem Wildnis-Block entnommen. Wenn der gefundene Block groß genug ist, wird er geteilt. Um zu bestimmen, ob ein Block aufgeteilt werden sollte, wird die Menge an Metadaten (Overhead) von dem abgezogen, was unsere aktuelle Zuweisung nicht verwendet. Wenn der Rest größer oder gleich MIN_ALLOC_SZ ist, bedeutet das, dass wir diesen Teil aufteilen und die Reste in den richtigen Behälter legen sollten. Sobald wir bereit sind, den gefundenen Block zurückzugeben, nehmen wir die Adresse des next Felds und geben dieses zurück. Dies geschieht, weil die Felder next und prev während der Zuordnung eines Blocks nicht verwendet werden. Daher kann der Benutzer des Blocks Daten in diese Felder schreiben, ohne dass dies Auswirkungen auf die Funktionsweise des Heaps hat.
Die Funktion heap_free nimmt einen von heap_alloc zurückgegebenen Zeiger entgegen. Es subtrahiert den korrekten Offset, um die Adresse der Knotenstruktur zu erhalten. Anstatt den Chunk einfach in den richtigen Behälter zu legen, werden die Chunks überprüft, die den bereitgestellten Chunk umgeben. Wenn einer dieser Blöcke frei ist, können wir die Blöcke zusammenführen, um einen größeren Block zu erstellen. Um die Blöcke zusammenzuführen, wird die Fußzeile verwendet, um die Knotenstruktur des vorherigen Blocks und die Knotenstruktur des nächsten Blocks abzurufen. Angenommen, wir haben einen Block namens to_free . Um den Block vor diesem Block zu erhalten, subtrahieren wir sizeof(footer_t) um die Fußzeile des vorherigen Blocks zu erhalten. Die Fußzeile enthält einen Zeiger auf den Kopf des vorherigen Abschnitts. Um den nächsten Block zu erhalten, holen wir uns einfach die Fußzeile von to_free und fügen dann sizeof(footer_t) hinzu, um den nächsten Block zu erhalten. Sobald dies alles erledigt ist und die Größen neu berechnet wurden, wird der Brocken wieder in einen Behälter gelegt.
HINWEIS: Dieser Code wurde ursprünglich für 32-Bit-Maschinen kompiliert. Das bedeutet, dass es bei Verwendung dieses Codes akzeptabel war, einen Int in einen Zeiger umzuwandeln, da beide die gleiche Größe haben. Auf einem 64-Bit-System warnt Sie der Compiler vor dem Größenunterschied. Um diese Warnungen zum Schweigen zu bringen, habe ich uintptr_t beim Umwandeln von einem unsigned int in einen Zeiger verwendet. Dadurch wird die Lesbarkeit etwas beeinträchtigt und einige Umwandlungen und Zeigerarithmetik sind ausführlich. Denken Sie also beim Lesen des Codes daran.
