Thema: Kernel malloc/free, kompakt und leichtgewichtig

[Dimension]

Diese kompakte und leichtgewichtige Implementierung eines Kernel malloc/free ist aus meinem Treiber-Testkernel und soll der Lowlevel-Community nicht vorenthalten bleiben.

http://pastebin.com/JBcwaTpv

Die Speicherverwaltung weist Speicherblöcke der Größe Seitengröße << n direkt aus dem physischen Speicher zu. Die Seitengröße ist auf 4K festgelegt. In der Standardkonfiguration ist MEMORY_PAGES = 8K, es sind also insgesamt 8K * 4K = 32M für malloc verfügbar. Die Verwaltungsdaten (hier Arrays mit Bitmaps) kommen extra in das data Segment. MEMORY_MEMORY_START_P = 16M bedeutet, dass der Speicherbereich erst ab 16M beginnt und bei MEMORY_MEMORY_END_P = 16M + 32M = 48M endet. Der Bereich darunter (ab 1M) ist also für die text, data und bss Segmente des Kernels

malloc() gibt einen Zeiger auf einen Bereich mit der kleinstmöglichen Speicherklasse zurück. Die Speicherklasse bestimmt die Größe des zugewiesenen Speicherbereichs folgendermaßen: Größe = 1 << Klasse. Die kleinste Klasse ist MEMORY_CLASS_START = 12, da 1 << 12 == MEMORY_PAGE_SIZE == 4K. Die Anzahl unterschiedlicher Speicherklassen wird mit MEMORY_SHIFT_LIMIT = 6 festgelegt. Die größte Klasse (inklusive) ist somit MEMORY_CLASS_END = 12 + 6 = 18.

Wie der Speicher mit MEMORY_SHIFT_LIMIT = 2 und MEMORY_PAGES = 8 aufgeteilt werden würde, zeigt folgendes Beispiel:

0x00000 +---+
        |   | 16x Blöcke der Größe  4K = 64K
        |   |
        |   |
        |   |
0x10000 +---+
        |   |  4x Blöcke der Größe  8K = 32K
        |   |
0x18000 +---+
        |   |  2x Blöcke der Größe 16K = 32K
        |   |
0x20000 +---+

Das Ganze hat dann noch einen Offset von MEMORY_MEMORY_START_P. Die letzte Klasse bekommt dabei einen Slot mehr, da der Platz nun nicht weiter aufgeteilt wird.

Die Referenzen auf printf(), print_str() und halt() müssen in der Umgebung des Kernels aufgelöst werden. Um die Bitmaps zu löschen, muss vor dem ersten malloc() mem_init() ausgeführt werden.

Das Laufzeitverhalten kann verbessert werden, indem freie Slots im Hintergrund gesucht werden. Die Speicherverwaltung weist keine externe Fragmentierung auf und ist weitestgehend robust implementiert, was aber durch Redundanz und/oder Asserts noch gesteigert werden kann.

[Jidder]

Ich würde das nicht als malloc/free bezeichnen. Was dein Code da verwaltet, ist physischer Speicher mit der Granularität einer Seitengröße. Unter malloc/free würde ich Byte-Granularität (plus ggf. geringen Overhead/Fragmentierung) erwarten. Darüber hinaus sollten bei einem modernen System malloc/free auf virtuellem Speicher arbeiten.

Immerhin heißen die Funktionen im Code nicht malloc/free. Gerade wenn man Code anderen zur Verfügung stellt, ist es problematisch, wenn er nicht das tut, was der Name verspricht.

Die Speicherverwaltung weist keine externe Fragmentierung auf

Dafür aber interne Fragmentierung. Wenn ich die Implementierung richtig verstehe, kann dein Allokator maximal 8192x mem_alloc(1) bedienen, und hat dann die kompletten 32 MB verbraucht. Und dann macht dein Algorithmus noch etwas, das irgendwie über interne und externe Fragmentierung hinausgeht. Er kann maximal 2x mem_alloc(200000) erfolgreich bedienen, was 0,5 MB Speicher verbraucht. Die freien 31,5 MB können nicht mehr für weitere mem_alloc(200000) verwendet werden.

Übrigens hat das Wiki auch ein paar interessante Vorschläge für die Speicherwaltung.

[Dimension]

Ich habe das geschrieben, um eine Umgebung für NetBSD-Treiber bereitzustellen. Wobei alle möglichen allocs, frees und reallocs umgeleitet werden.

Er kann maximal 2x mem_alloc(200000) erfolgreich bedienen, was 0,5 MB Speicher verbraucht. Die freien 31,5 MB können nicht mehr für weitere mem_alloc(200000) verwendet werden.

Deshalb ist das auch eine Speichervewaltung für Test-Kernel. Es ging mir in erster Linie darum Speicher-Bereiche mit der Größe von mehr als einer Seite in möglichst wenig Code bereitzustellen.

Die entsprechenden Artikel im Wiki habe ich mir, neben praktischen Beispielen aus realen Kerneln, angeschaut. Ich hatte gehofft, dass ich einen weiteren Artikel im Wiki hinzufügen könnte.

[Dimension]

Was gibt es beim Erstellen eines neuen Artikels im Wiki zu beachten? Gibt es eine Seite mit Richtlinien und Hilfestellungen?

[kevin]

Sowas?

http://www.lowlevel.eu/wiki/Wiki-Crashkurs
http://www.lowlevel.eu/wiki/Designrichtlinien

Und vor allem natürlich: Nur korrekte und nützliche Informationen ins Wiki schreiben. Das Wiki soll helfen, nicht noch mehr verwirren.