Slab allocator

Zweck und Grundidee

Ein Slab allocator ist ein Verfahren zur Speicherverwaltung, das viele Betriebssysteme und Anwendungen nutzen. Es soll vor allem die häufige Reservierung kleiner Speicherbereiche schnell ermöglichen und den Arbeitsspeicher mit möglichst wenig Verschwendung nutzen. Slab-Allokatoren sind in unixoiden Betriebssystemen wie FreeBSD und Linux verbreitet.

Speicher wird technisch in großen Speicherseiten organisiert, bei IA-32 mit 4096 Bytes. Das ist für dynamisch angeforderten Speicher oft unzweckmäßig. Betriebssystemobjekte sind meist klein, haben eine begrenzte Lebensdauer und werden nach kurzer Zeit zurückgegeben; außerdem werden oft viele Objekte desselben Typs benötigt. Der Slab allocator nutzt diese Eigenschaften, indem er gleichartige Objekte zusammen verwaltet.

Statt dass jeder Prozess oder jedes Kernelmodul einen privaten Cache führt, trennt Bonwicks Konzept Clients und Central allocator. Clients beschreiben lediglich die benötigten Objekte. Der Central allocator stellt Verwaltungsfunktionen und APIs bereit und soll den Speicher im ganzen System effizient einsetzen.

Slabs, Caches und ihre Aufgaben

Der Central allocator fasst Objekte desselben Typs zu Slabs zusammen. Mehrere Slabs eines Typs werden in einem Cache organisiert, der passende Objekte auf Vorrat hält. Die für Slabs und Caches benötigten Speicherseiten holt der Allocator vom Buddy-System, das nur ganze Speicherseiten liefert. Der Slab allocator teilt diesen gelieferten Speicher weiter auf und vermeidet dadurch häufige aufwändige Zugriffe auf die darunter liegende Buddy-Speicherverwaltung.

Caches haben drei Aufgaben: Sie halten oft benutzte Objekte bereits fertig initialisiert bereit. Sie bieten außerdem allgemeine Vorräte für bestimmte Objektgrößen, unter Linux von 2^5 = 32 bis 2^17 = 131072 Bytes. Schließlich sollen sie Hardwarecaches wie TLB und L1-Cache gut ausnutzen. Ein TLB ist ein Zwischenspeicher für Adressübersetzungen; der L1-Cache ist ein besonders schneller Prozessorcache.

Organisation eines Caches

Unter Linux wird ein Cache durch eine Datenstruktur vom Typ kmem_cache_s repräsentiert. Darin gibt es drei doppelt verkettete Listen in der Unterstruktur list vom Typ kmem_list3. Eine Liste enthält vollständig freie Slabs ("all free"), eine vollständig belegte Slabs ("all used") und eine Slabs mit zugleich belegten und freien Objekten ("mixed free/used").

Seit Bonwicks Version von 2001 besitzt jeder Prozessor zusätzlich einen Zwischenspeicher vom Typ array_cache. Er merkt sich die zuletzt freigegebenen Objekte. Diese werden zuerst wieder vergeben, weil sie mit hoher Wahrscheinlichkeit noch in einem Prozessorcache liegen und daher besonders schnell verfügbar sind.

Linux kann Laufzeitinformationen in /proc/slabinfo anzeigen. Die Spalten bedeuten: name ist der Cachename, active_objs die Zahl aktuell benutzter Objekte, num_objs die Zahl aller Objekte, objsize die Objektgröße in Bytes, objperslab die Objektzahl pro Slab, pagesperslab die Seitenzahl pro Slab und batchcount die Zahl der Objekte, die beim Anlegen oder Freigeben eines Slabs auf einmal verarbeitet werden. Die Ausgabe unterscheidet Caches für bestimmte Objekte von allgemeinen Größencaches, jeweils für DMA-fähigen und nicht-DMA-fähigen Speicher.

Fragmentierung und Colouring

Fragmentierung bezeichnet unvorteilhaft verteilten oder ungenutzten Speicher. Bei interner Fragmentierung ist nach Bonwick "per buffers wasted space" entscheidend, also der pro Slab verschwendete Platz. Sie entsteht erstens, weil Objektgrößen auf ein ganzzahliges Vielfaches der Wortgröße sizeof (void *) des Prozessors aufgerundet werden. Ausgerichtete Adressen beschleunigen auf vielen Architekturen den Zugriff, benötigen aber zusätzlichen Speicher. Zweitens bleibt am Ende eines Slabs häufig ein Rest übrig. Dieser Verschnitt ist kleiner als 1/Objektanzahl der Slabgröße. Größere Slabs enthalten mehr Objekte und verringern damit diesen Rest.

Externe Fragmentierung sind nach Bonwick "unused buffers in the freelist", also freie Objekte innerhalb von Slabs. Sie ist vorhanden, aber relativ gering: Gleichartige Objekte haben oft ähnliche Lebensdauern, sodass Slabs meist entweder ganz voll oder ganz frei sind. Eine Ausnahme bilden Caches bestimmter Größen, die jedoch nicht so häufig verwendet werden. Enthielte ein Slab mehr Objekte, stiege die Wahrscheinlichkeit, dass er nie vollständig leer wird, und damit die externe Fragmentierung.

Colouring verwendet den Rest am Ende eines Slabs: Teile davon werden vor dem ersten Objekt eingefügt. Dadurch liegen gleiche Objekte in unterschiedlichen Slabs versetzt. Eine Ausrichtung an Vielfachen der Cachelinegröße kann gegenseitiges Verdrängen von Objekten im Cache und von Adressen im TLB vermindern.

Anforderung und Verwaltung freier Objekte

Bei einer Speicheranforderung wird zuerst versucht, ein Objekt aus dem per-CPU-Cache zu nehmen. Ist dort keines verfügbar, liefert der Allocator ein freies Objekt aus einem bereits vorhandenen Slab. Gibt es auch dort kein freies Objekt, wird über das Buddy-System ein neuer Slab angelegt. Der negative Einfluss auf Caches und damit auf die Performance steigt bei diesen drei Schritten jeweils an.

Ein Slab enthält einen Verwaltungskopf, eine Verwaltungsstruktur für freie Objekte, die auf die Wortgröße des Prozessors aufgerundeten Objekte und gegebenenfalls den restlichen Verschnitt. Der Verwaltungskopf speichert unter anderem das erste Objekt, den Index des ersten freien Objekts, die Zahl belegter Objekte, die Verschiebung für das Colouring sowie Verknüpfungen zum vorherigen und nächsten Slab der passenden Liste.

Im Linux-Kern werden freie Objekte über eine Liste von Ganzzahlen verwaltet. Sie besitzt ebenso viele Felder wie der Slab Objekte enthält. Ein Feld ist nur relevant, wenn sein Objekt frei ist; dann enthält es den Index des nächsten freien Objekts. Über den im Slab-Kopf gespeicherten Index des ersten freien Objekts lässt sich das nächste freie Objekt schnell finden und zurückgeben.