Thema: SLAB-Allocator als Basis fuer kmalloc?

[rizor]

Nabend zusammen,

ich habe jetzt einen fertigen SLAB-Allocator, der stark auf parallelen Zugriff durch feingranulares Locking optimiert ist. Nun wollte ich mir kmalloc schreiben und habe mir ueberlegt, ob es nicht sinnvoll waere kmalloc nur als eine Art Wrapper zu verwenden, der anhand der Groessen entscheidet aus welchem SLAB der Speicher geholt werden soll. Macht sowas sinn? Das erhoeht natuerlich den Verwaltungsoverhead, da ich mehrere Slabs fuer ein kmalloc brauche. Ausserdem erlaubt mein Kernel Speicherallokationen aus bestimmten bereichen (low- oder highmem). Ausserdem wird noch zwischen normalem und boot Speicher unterschieden. Nach dem Bootvorgang wird der gesamte boot Speicher freigegeben, damit der Kernel so wenig Speicher wie moeglich verschwendet. Somit muesste ich auf jeden Fall drei SLABS anlegen, wobei das noch nicht reichen duerfte. Ansonsten muss jeder SLAB grosse Bloecke verteilen, die zu einen starken inneren Fragmentierung fuehren. Also brauchte ich 3 * x SLABS.
Ist das noch praktikabel?

Habe auch lockless Allokation-Algorithmen gefunden, die sind aber vermutlich nicht viel optimaler.

Gruss,
rizor

[FlashBurn]

Also erstmal wird das so z.B. im Linux-Kernel gemacht (die haben aber inzwischen en SLUB-Allocator).

Ich weiß nicht wie dein Kernel-Konzept aussieht, aber brauchst du unbedint ein kmalloc? Ich komme z.B. komplett ohne aus und habe nur den SLAB-Allocator.

[rizor]

Da hast du dann aber auch verschiedene Slabs fuer die verschiedenen Groessen, oder?
Welche verwendest du denn?

[FlashBurn]

Entweder ich verstehe deine Frage nicht richtig oder du hast das Prinzip/den Vorteil vom SLAB-Allocator nicht verstanden.

kmalloc brauchst du für Sachen wo du entweder die Größe zur Compilezeit nicht kennst oder es so viele unterschiedlichen Größen sind, das sich der SLAB-Allocator nicht lohnt.
Der SLAB-Allocator ist für Objekte gedacht z.B. ne Thread-Struktur. Du erstellst also nen Object-Cache der Slabs der Objektgröße einer Thread-Struktur enthält.

Wenn du also nicht alzu viele verschiedene Objekte hast brauchst du kein kmalloc.

[Jidder]

ich habe jetzt einen fertigen SLAB-Allocator, der stark auf parallelen Zugriff durch feingranulares Locking optimiert ist. Nun wollte ich mir kmalloc schreiben und habe mir ueberlegt, ob es nicht sinnvoll waere kmalloc nur als eine Art Wrapper zu verwenden, der anhand der Groessen entscheidet aus welchem SLAB der Speicher geholt werden soll. Macht sowas sinn?

Ja, das macht Sinn. Hast du eigentlich die Papers von Bonwick gelesen?

Ausserdem erlaubt mein Kernel Speicherallokationen aus bestimmten bereichen (low- oder highmem).

Der SLAB sollte virtuellen Speicher verwalten. Ich denke nicht, dass dort die Unterscheidung wo es im physischen Speicher landet, sinnvoll ist.

[FlashBurn]

Der SLAB sollte virtuellen Speicher verwalten. Ich denke nicht, dass dort die Unterscheidung wo es im physischen Speicher landet, sinnvoll ist.

Ich habe zwar bis heute nicht das Konzept von highmem in Linux verstanden, aber der SLAB-Allocator sollte schon wissen wo der Speicher herkommen soll (und das muss er dem virtuellen Speichermanager sagen).

[Jidder]

Warum muss er das wissen?

[FlashBurn]

Na wenn du normalerweise nen kmalloc(size,wo_speicher_herkommen) machst und das gegen nen slab Aufruf ersetzen willst, sollte der Speicher wieder dort herkommen und dazu muss der SLAB-Allocator das wissen.

[Jidder]

Also ich finde kalloc ist nicht die richtige Schnittstelle, um Speicher aus einem bestimmten physischen Speicherbereich anzufordern. Aber auch in dem Fall trifft nicht der Slab Allocator die Entscheidung wo der Speicher herkommt, sondern immer noch kmalloc.

Ein Slab Allocator verwaltet Objekte (structs und so weiter) im virtuellen Speicher. Wenn Anforderungen an die Platzierung im physischen Speicher gestellt werden, will man meistens keine Objekte verwalten, sondern z.B. Puffer. An diese Puffer werden auch strengere Anforderungen als an allgemeine Objekte gestellt (z.B. Alignment, physische Durchgängigkeit, kein Kreuzen von 64 KB Grenzen). Es liegt deswegen ganz im Sinne des Slab Allocators dafür einen anderen Allocator zu verwenden. Zum Beispiel den, der unterhalb des Slab Allocators liegt.

[rizor]

Entweder ich verstehe deine Frage nicht richtig oder du hast das Prinzip/den Vorteil vom SLAB-Allocator nicht verstanden.

kmalloc brauchst du für Sachen wo du entweder die Größe zur Compilezeit nicht kennst oder es so viele unterschiedlichen Größen sind, das sich der SLAB-Allocator nicht lohnt.
Der SLAB-Allocator ist für Objekte gedacht z.B. ne Thread-Struktur. Du erstellst also nen Object-Cache der Slabs der Objektgröße einer Thread-Struktur enthält.

Wenn du also nicht alzu viele verschiedene Objekte hast brauchst du kein kmalloc.

Das macht soweit ja alles Sinn. Das Problem ist, dass ich nicht für jedes Struct einen eigenen Cache aufbauen möchte, da das absolute Verschwendung ist. Also brauche ich einen Cache, der für allgemeinen Speicher zuständig ist. Das ist momentan mein Problem.

Der SLAB sollte virtuellen Speicher verwalten. Ich denke nicht, dass dort die Unterscheidung wo es im physischen Speicher landet, sinnvoll ist.

Ich habe zwar bis heute nicht das Konzept von highmem in Linux verstanden, aber der SLAB-Allocator sollte schon wissen wo der Speicher herkommen soll (und das muss er dem virtuellen Speichermanager sagen).

Das sind Überbleibsel aus vergangenen X86-Zeiten. Es gibt/gab Hardware, die nur Speicher unterhalb der 1GB-Grenze ansprechen konnte. Dafür wurde das Konzept eingeführt, damit die Treiber richtigen SPeicher anfordern können. Außerdem war der Zugriff auch mal auf Speicher oberhalb der 1GB-Grenze langsamer als auf den unter dieser Grenze. Damit hat der Kernel seine Datenstrukturen, die er seltener benötigt, in den Highmem-SPeicher gelegt (und prinzipiell den Speicher der Anwendungen) und alles andere in Lowmem.

Warum muss er das wissen?

Der Slab-Allocator fordert SLABS an, die aus bestimmten Speicherbereichen kommen müssen. Er bittet den virtuellen Verwallter um Speicher mit der Anforderung an die Speicherregion, da dieser sich Speicher vom physischen Verwalter holt.
Natürlich kann ich am SLAB vorbei arbeiten, aber ich hätte ihn ganz gerne als zentrale Instanz, damit ich bei OOM-Problemen dem Kernel schnell Speicher klauen kann, damit der Fehler unter Umständen vermieden werden kann.

[FlashBurn]

Das Problem ist, dass ich nicht für jedes Struct einen eigenen Cache aufbauen möchte, da das absolute Verschwendung ist.

Dann hast du den Vorteil und eigentlichen Grund für den SLAB-Allocator nicht verstanden

Er wurde gerade für die vielen Objekte gleicher Größe entworfen, weil du so weniger Verschnitt produzieren kannst und der Allocator auch schneller ist.
Ich lege für jede Struct einen Cache an.

Wenn du eigentlich eh immer kmalloc() nutzt, dann würde ich dir einen anderen malloc() Algo empfehlen (z.B. dmalloc oder sowas, musst du mal gucken, da gibt es auch welche für Multithreading), aber nen SLAB-Allocator da drunter zu verwenden, das ist Verschwendung!

An diese Puffer werden auch strengere Anforderungen als an allgemeine Objekte gestellt (z.B. Alignment, physische Durchgängigkeit, kein Kreuzen von 64 KB Grenzen).

Ich weiß nicht wie es beim "originalen" SLAB-Allocator aussieht, aber meiner beachtet das Alignment, das gefordert wird. Zumal Puffer so eine Sache ist, jedes Struct ist doch im Endeffekt ein Puffer

So kann ich den SLAB-Allocator z.B. auch für die FPU-Structs nutzen (weil die ja nen spezielles Alignment fordern, obwohl das Aufgrund ihrer Größe schon kein Problem ist).

[rizor]

Das Problem, das ich da sehe ist, dass ich einen großen Verwaltungsaufwand habe und viel Speicher für die Verwaltung verwende, wenn ich das so machen würde. Da stellt sich mir die Frage nach der Effektivität. Ich habe aber auch schon Lösungen gesehen, die SLAB als Basis für malloc verwenden und dann halt 16-, 64- und 512-byte-Blöcke als Caches.

[erik.vikinger]

Hallo,


Für die Frage nach der sinnvollen Verwendung eines SALB-Allocators ist noch relevant ob es sich um einen Micro-Kernel oder um einen Monolithen handelt. Bei ersterem würde ich auch sagen das es keines kmalloc bedarf einfach weil es nur ganz wenige verschiedene Objekt-Größen gibt und deren Größe auch immer zur Compile-Zeit bekannt ist. Des weiteren wird ein Micro-Kernel kaum Speicher mit bestimmten physischen Eigenschaften anfordern, das machen eher die Treiber (im User-Mode) die dafür einen speziellen Syscall bemühen müssen welcher dann direkt bei der physischen Speicherverwaltung anfragt. Bei einem Monolithen hingegen wird man um eine ordentliche kmalloc Implementierung für beliebige Objekt-Größen kaum rum kommen und wenn man beliebige Objekt-Größen mit SLAB-Allocatoren managen will wird man entweder recht viele SLAB-Größen benötigen oder eine enorme Speicherverschwendung in kauf nehmen müssen (oder man baut einen Hybriden der bestimmte Objekt-Größen an den SLAB-Allocator weiter reicht und den Rest klassisch managed).

Das der SLAB-Allocator sich für die physischen Eigenschaften seiner SLABs interessiert halte ich persönlich auch eher für ungeschickt, Objekte bei denen das eine Rolle spielt sollten direkt von der physischen Speicherverwaltung geholt werden. Außerdem gibt es in normalen PCs keine Gründe den Speicher mit bestimmten physischen Eigenschaften zu verwalten, das einzigste Device was mir da einfällt ist der Floppy-Controller und für den muss man eh noch ein paar weitere Extra-Würste aufs Feuer legen so das es IMHO nichts ausmacht wenn es im Start-Code des Kernel ein paar Zeilen Code gibt die speziell für den Floppy-Controller während der Einrichtung der physischen Speicherverwaltung mal spezielle 512 kBytes zur Seite schaffen die dann später der Floppy-Treiber exklusiv benutzen darf.


In meinem Micro-Kernel möchte ich auch kein kmalloc haben sondern direkt immer das richtige SLAB_alloc aufrufen (ich gebe also nicht die gewünschte Objekt-Größe als Parameter mit sondern rufe direkt die passende Funktion auf, das selbe auch beim SLAB_free da ich ja immer weiß was ich für ein Objekt frei geben möchte so das ich mir sparen kann aus dem Objekt-Pointer auf die Objekt-Größe schließen zu müssen was bei einer generischen malloc/free-nach-SLAB-Umsetzung durchaus knifflig sein kann), da ich wohl mit 5 bis 7 Objekt-Größen aus komme sehe ich in der kleinen Code-Vervielfachung auch keine Probleme (soll auch alles aus der selben Vorlage compiliert werden, nur jeweils mit den passenden SLAB-Defines als Compiler-Parameter für die entsprechende Objekt-Größe).


Grüße
Erik

[erik.vikinger]

Hallo,

Ich habe aber auch schon Lösungen gesehen, die SLAB als Basis für malloc verwenden und dann halt 16-, 64- und 512-byte-Blöcke als Caches.

Das ist aber eine enorme Verschwendung wenn Du ne Menge Objekte mit 20 Byte Größe benötigst. Also gröber als in Wurzel-2-Schritten (16, 24, 32, 48, 64, 92, 128, 184, 256, 364 ....., für eine 64Bit-Plattform auch immer auf das nächste Vielfache von 8 und nicht blos 4 aufgerundet) würde ich für eine generische malloc-Implementierung auf SLAB-Basis nicht machen, ansonsten bekommt man eine ziemliche interne Fragmentierung.

Aber ich finde ja Du solltest erst mal Deine Anforderungen genauer spezifizieren, vielleicht kommst Du ja auch mit wenigen fest vorgegebenen Objekt-Größen aus.


Grüße
Erik

[rizor]

Hallo,


Für die Frage nach der sinnvollen Verwendung eines SALB-Allocators ist noch relevant ob es sich um einen Micro-Kernel oder um einen Monolithen handelt. Bei ersterem würde ich auch sagen das es keines kmalloc bedarf einfach weil es nur ganz wenige verschiedene Objekt-Größen gibt und deren Größe auch immer zur Compile-Zeit bekannt ist. Des weiteren wird ein Micro-Kernel kaum Speicher mit bestimmten physischen Eigenschaften anfordern, das machen eher die Treiber (im User-Mode) die dafür einen speziellen Syscall bemühen müssen welcher dann direkt bei der physischen Speicherverwaltung anfragt. Bei einem Monolithen hingegen wird man um eine ordentliche kmalloc Implementierung für beliebige Objekt-Größen kaum rum kommen und wenn man beliebige Objekt-Größen mit SLAB-Allocatoren managen will wird man entweder recht viele SLAB-Größen benötigen oder eine enorme Speicherverschwendung in kauf nehmen müssen (oder man baut einen Hybriden der bestimmte Objekt-Größen an den SLAB-Allocator weiter reicht und den Rest klassisch managed).

Es soll ein Hybrid werden.
Somit möchte ich den Treibern sowohl ein kmalloc bieten und auch das normale SLAB-Interface.



Gibt es Benchmarks zu den Größen

Hallo,

Ich habe aber auch schon Lösungen gesehen, die SLAB als Basis für malloc verwenden und dann halt 16-, 64- und 512-byte-Blöcke als Caches.

Das ist aber eine enorme Verschwendung wenn Du ne Menge Objekte mit 20 Byte Größe benötigst. Also gröber als in Wurzel-2-Schritten (16, 24, 32, 48, 64, 92, 128, 184, 256, 364 ....., für eine 64Bit-Plattform auch immer auf das nächste Vielfache von 8 und nicht blos 4 aufgerundet) würde ich für eine generische malloc-Implementierung auf SLAB-Basis nicht machen, ansonsten bekommt man eine ziemliche interne Fragmentierung.

Aber ich finde ja Du solltest erst mal Deine Anforderungen genauer spezifizieren, vielleicht kommst Du ja auch mit wenigen fest vorgegebenen Objekt-Größen aus.


Grüße
Erik

Gibt es Benchmarks zu den optimalen Größen? Habe leider nichts gefunden. Deine 4- bzw. 8-byte Variante klingt einleuchtend.
WOher hast du die Werte? Selbst ermittelt?

[erik.vikinger]

Hallo,

Es soll ein Hybrid werden.
Somit möchte ich den Treibern sowohl ein kmalloc bieten und auch das normale SLAB-Interface.

Okay, das ist dann natürlich was anderes. Ich kenne die SLAB-Implementierung des Linux-Kernel nur sehr oberflächlich aber vielleicht kannst Du Dir dort die nötigen Inspirationen holen. Ich denke die dortigen Konzepte wurden vor der Umsetzung auch lang und breit auf den einschlägigen Mailing-Lists diskutiert, bestimmt lohnt es sich da mal nen Tag in alten Threads zu stöbern (wenn Du was interessantes findest würden sich hier bestimmt einige über ein paar Links freuen).

Gibt es Benchmarks zu den optimalen Größen? Habe leider nichts gefunden. Deine 4- bzw. 8-byte Variante klingt einleuchtend.
WOher hast du die Werte? Selbst ermittelt?

Die Werte habe ich vorhin einfach mit dem Taschenrechner ermittelt aber das geht auch mit ner simplen Formel zur Laufzeit (oder Du baust ne feste Tabelle o.ä.). Das Aufrunden auf die native Größe der betreffenden Plattform ist wohl logisch. "Benchmarks" kenne ich dazu nicht aber die potentielle Platzverschwendung in Prozent kann man sich auch so ausrechnen (der Verwaltungsoverhead durch die SLABs selber sollte bei geschickter Wahl der Block-Größe eher gering bleiben).


Grüße
Erik

[FlashBurn]

Bei ersterem würde ich auch sagen das es keines kmalloc bedarf einfach weil es nur ganz wenige verschiedene Objekt-Größen gibt und deren Größe auch immer zur Compile-Zeit bekannt ist.

Das (Objekt-Größe zur Compilezeit bekannt) kommt ganz darauf an was für nen SLAB-Allocator du verwendest. Denn ich verwende z.B. den SLAB-Allocator auch für die Objekte die er selber benötigt um verschiedene Objekte zu managen. Das hat den Hintergrund das ich zur Compilezeit halt nicht weiß wieviele CPUs der Computer, wo der Code mal drauf laufen wird, hat und ich wollte es halt nicht so wie es bei den meisten (vllt sogar alle?) OS ist, dass schon zur Compilezeit festgelegt wird was die maximale CPU Anzahl ist und vorallem ist das dann ja auch Speicherverschwendung wenn du deine Datenstrukturen immer auf z.B. 32 CPUs ausrichtest, aber eigentlich nur 2 hast.
So ist die größe bestimmter Datenstrukturen erst zur Laufzeit bekannt und dazu gehören vorallem die zum Managen der verschiedenen Objekte. Da ich die Variante vom SLAB-Allocator verwende, wo man pro CPU ne Art Stack hat und die Objekte immer von diesem Stack holt (so lange dort welche drin sind). Dieses Design skaliert besser mit mehreren CPUs.

[erik.vikinger]

Hallo,

.....
So ist die größe bestimmter Datenstrukturen erst zur Laufzeit bekannt und dazu gehören vorallem die zum Managen der verschiedenen Objekte. Da ich die Variante vom SLAB-Allocator verwende, wo man pro CPU ne Art Stack hat und die Objekte immer von diesem Stack holt (so lange dort welche drin sind). Dieses Design skaliert besser mit mehreren CPUs.

Diese Datenstrukturen möchte ich nicht vom SLAB-Allocator holen (da hätte ich ja auch wieder ein Henne-Ei-Problem) sondern die will ich beim Vorbereiten des Kernels (also zur Boot-Zeit) direkt der physischen Speicherverwaltung entnehmen. Diese Strukturen ändern ihre Größe ja zur Laufzeit nicht mehr und werden auch nie freigegeben so das die ruhig zum Basisverbrauch des Kernels gehören können.


Grüße

[FlashBurn]

Naja, wenn ich mal davon ausgehe, dass ich 256 CPUs unterstützen möchte und dann ja immer für diese maximale Grenze meine Datenstrukturen auslegen müsste. Dann wäre das eine Verschwendung von ca. 8kb pro Objekt-Typ (wenn nur eine CPU genutzt wird) und das finde ich dann schon nicht mehr so wenig.

Das Henne-Ei-Problem war ganz einfach zu lösen und zwar in dem man den ersten SLAB (also den der für die SLAB Datenstruktur zuständig ist) von Hand konstruiert (zur Laufzeit).

Das mit der Größe nicht ändern (zur Laufzeit) trifft doch eh auf alle Objekte zu, die du per SLAB-Allocator holst.

[rizor]

Ich hatte mir überlegt das Ganze so zu lösen.
Aber wie löst du das Problem, dass wenn du ein Objekt brauchst, es aber ein neuer SLAB aufgebaut werden muss, da du keinen freien hast. Dann rufst den Cache für die SLABS auf, oder?
Was passiert, wenn dieser wiederum einen neuen SLAB aufbauen muss, da der keinen freien hat?
Für mich klingt das stark nach einer unendlichen Rekursion, falls du nicht gerade Extra-Funktionen für diese Caches hast.
Wie hast du das Problem gelöst?