Slaballocator

[FlashBurn]

Ich bin gerade dabei einen Slaballocator in Assembler zu schreiben, das Allozieren klappt schon, nur mit dem Deallozieren habe ich noch so meine Probleme was den Algo betrifft.

Ich dachte daran die Listen (free, full, partial) nach aufsteigender Startadresse zu sortieren um das Deallozieren zu beschleunigen. Dann würde ich aber gleichzeitig das Allozieren verlangsamen :(

Wie macht das eigentlich der Slaballocator der in Solaris verwendet wird? Geht der die Listen durch bis der den richtien Slab Cache (da wo die einzelnen Slabs drin sind) gefunden hat oder wie macht der das?

[Trap]

Ich hab mal kurz das Paper dazu überflogen und versteh nicht wieso du sortieren willst. Zugriff geht doch in O(1), sowohl beim allokieren als auch beim zurückgeben.

[FlashBurn]

Dann habe ich da wohl was nicht ganz verstanden.

Das Problem ist doch das man von dem Objekt nicht auf die Struktur wo die Freelist und andere Dinge des Slabs drin stehen schließen kann. Denn diese Struktur kann innerhalb des Slabs und auch außerhalb stehen und so muss ich dann die Listen durchsuchen. In dem Objekt (also der Speicher den ich bekomme nach dem Allozieren) steht kein Hinweis auf die Slabstruktur! Irgendwie muss ich die ja finden.

[Trap]

Ich hab das Paper wie gesagt nur überflogen, aber soweit ich das verstanden hab ist ein Slab genau eine Page groß und jeder hat eine eigene freelist an einer festen Stelle am Ende.

Wenn man dann einen Pointer hat maskiert man einfach die niedrigen Bits raus, dann hat man die Anfangsadresse vom Slab, dann einfach das aktuelle Objekt in die freelist packen.

[FlashBurn]

Wie gesagt es gibt aber die Möglichkeit diese Struktur wo die Freelist ist auch außerhalb des Slabs zu speichern, wenn z.B. nicht genügend Platz vorhanden ist. Desweiteren ist es auc möglich mehrere Pages für einen Slab zu verwenden, was es auch schwieriger macht die Basisadresse zu finden. Ich beschäftige mich auch gerade nochmal mit den Papers, aber bisher gibt es keine neuen Erkenntnisse :( Zumal es ja auch Erklärungen mit Code gibt, aber nie von der Free Funktion.

Edit::

Da hab ich doch glatt einen Layer übersehen :( Wenn die Slabstruktur nicht innerhalb des Slabs steht oder ein Slab aus mehreren Pages besteht, dann gibt es noch einen zusätzlichen Layer mit dem man dann über eine Hashtabelle auf die Adresse der Slabstruktur kommt. Werd mich dann mal damit beschäftigen müssen!

[Trap]

Im Paper steht zu großen Objekten:
A per-cache self-scaling hash table provides buffer-to-bufctl conversion.