Kernelprogrammierer können auf die effiziente dynamische Speicherverwaltung von Linux bauen. Doch auch für Applikationsentwickler sind Kenntnisse des Buddy-Systems und des Slab-Allokators interessant, denn es stecken trickreiche Algorithmen dahinter.

Das dynamische Management realen und virtuellen Speichers ist eine komplexe Angelegenheit. Linux verwaltet ihn, wie andere Betriebssysteme auch, primär mit so genannten Seiten. Dabei handelt es sich um Speicherbereiche gleicher Größe, die auf einem 32-Bit-System normalerweise 4 KByte, auf einem 64-Bit-System 8 KByte umfassen.

Nicht alle Speicherbereiche besitzen die gleichen Eigenschaften. Nur ein Teil des Speichers ist beispielsweise für ISA-DMA nuztbar[1], ein anderer Teil entzieht sich auf einem x86-System dem direkten Zugriff (Highmem). Aus diesem Grund untergliedert Linux den gesamten, physisch adressierbaren Speicher in die »ZONE_DMA«, »ZONE_NORMAL« und »ZONE_HIGHMEM« und verwaltet den Speicher jeder Zone separat.

Der Kernel bietet es seinen Subsystemen wie dem Pagecache oder dem Sys-Filesystem an, die Speicherseiten einer Zone für den eigenen Gebrauch zu reservieren. Benötigt eine Komponente mehr Speicher als mit einer Page zur Verfügung steht, erhält sie mehrere, direkt aufeinander folgende Seiten. Braucht sie den Speicher nicht mehr, muss sie ihn zurückgeben.

Fragmentierung verhindern

Meist fragmentiert das ständige Reservieren und Freigeben den verfügbaren Speicher: Fordert eine Komponente einen größeren an, gibt es vielleicht nicht mehr genügend direkt aufeinander folgende Speicherseiten. Diese Fragmentierung versucht das Buddy-System (siehe Kasten “Buddy-System”) zu verhindern. Einen Überblick über Funktionen, mit denen Speicher auf Basis der Speicherseiten reserviert wird, gibt der Kasten “Speicherseiten allozieren”.

Das Buddy-System hat im Wesentlichen zwei Nachteile: Erstens ist das Reservieren und Freigeben von Seiten aufwändig. Zweitens verschwendet das Allozieren einer ganzen Page Speicher, wenn das darin abgelegte Objekt nur wenige Bytes groß ist. Kein Wunder also, dass das Buddy-System nur als Basis für eine Speicherverwaltung dient, die auch effizient mit kleineren Objekten umgehen kann. Eine solche Verwaltung bietet zudem die Chance, zusätzlich noch Objekt-Caching zu implementieren. Programmierer sprechen von Objekt-Caching, wenn ein Objekt nicht gleich vollständig zerstört wird, nur weil es aktuell keine Verwendung findet.

Stattdessen verbleibt das Objekt in seinem vorinitialisierten Zustand in einem Cache. Die Vorgänge “Speicher reservieren” und “Objekt vorinitialisieren” sind bei einer erneuten Anforderung damit überflüssig, die Vorgänge “Objekt deinitialisieren” und “Speicher freigeben” können je einmal eingespart werden (siehe Abbildung 1).

Abbildung 1: Einsatz eines Cache: Der Zugriff auf Objekte ist wesentlich effizienter, wenn diese nach Gebrauch nicht komplett deinitialisiert werden und der zugehörige Speicher reserviert bleibt.

Schneller mit Cache

Objekt-Caching ist nur mit typisierten Objekten zu realisieren, schließlich besitzt jeder Typ spezifische Variablen. Das Speichermanagement kennt also seine Objekte. Die zugreifenden Instanzen fordern nicht mehr eine bestimmte Menge Speicher, sondern das Objekt an. In Linux sorgt eine Speicherverwaltung mit dem Namen Slab-Allocator für den effizienten Umgang mit den kleinen Objekten und für das Objekt-Caching.

Mit Hilfe der Funktion »kmem_cache_ create()« (siehe Kasten “Cache-Funktionen für den Kernelprogrammierer”) erzeugt der Programmierer den Cache für einen neuen Objekttyp. Neben der Objektgröße übergibt er zusätzlich die jeweiligen Adressen einer Konstruktor- und einer Destruktor-Funktion. Legt der Cache dann initial ein neues Objekt an, ruft er den Konstruktor auf. Der vom Entwickler programmierte Konstruktor initialisiert die eventuell im Objekt befindliche Spinlocks, Referenzzähler und Variablen.

Zum Löschen eines Cache mit all seinen Objekten ruft der Programmierer die Funktion »kmem_cache_destroy()« auf. Bevor er die Objekte aber wirklich zerstört, ruft der Allokator den Destruktor auf. Dieser gibt zum Beispiel die bei der Initialisierung angeforderten Spinlocks wieder frei. Da der Slab-Allocator immer mehrere Objekte gleichzeitig anlegt beziehungsweise zerstört, ergeben sich Laufzeitvorteile: Der Code des Konstruktors und der des Destruktors muss nicht mehrfach in den Instruktions-Cache des Prozessors geladen werden.

Abbildung 2: Gibt es keinen freien Speicherbereich in der angeforderten Größe, spaltet der Buddy-Algorithmus einen größeren Speicherbereich so lange auf, bis geeignete Speicherbereiche vorliegen.

Zwischen dem Aufruf des Konstruktors und dem des Destruktors kann das Objekt beliebig oft vom Cache angefordert (durch Aufruf der Funktion »kmem_cache_alloc()«) und dem Cache zurückgegeben werden (Aufruf der Funktion »kmem_cache_free()«). Der Objekttyp wird hierbei in Form der Cache-Referenz beim Aufruf der Funktionen festgelegt. Die Cache-Referenz wiederum hat der Programmierer beim Aufruf von »kmem_cache_create()« in Form des Rückgabewerts erhalten.

Node 0, zone   DMA        3    5    4    4 ...
Node 0, zone   Normal   180   49   99   76 ...

Abbildung 3: Der Slab-Allocator nutzt das Buddy-System als Backend. Die Funktionsaufrufe sind in schwarz dargestellt, der Objektfluss blau.

Der Slab-Allocator nutzt das Buddy-System als Backend (siehe Abbildung 3). Die beiden Mechanismen sind dabei so verzahnt, dass Objekte nicht nur durch »kmem_cache_destroy()« zerstört werden, sondern auch dann, wenn das Buddy-System ,,unter Druck steht”. Hat nämlich das Backend für eine Anforderung keinen ausreichend großen Speicherbereich, sammelt es die vom Slab-Allocator gerade nicht benötigten Speicherbereiche wieder ein. Das reicht bereits oft, um die ausstehende Anforderung bedienen zu können. Übrigens sammelt das Buddy-System die Speicherseiten auch dann wieder ein, wenn für einige Sekunden niemand die Objekte im Cache verwendet.

Gut organisiert

Den Einstieg in den Slab-Allocator findet der Kernel über das Objekt »cache_ cache« (siehe Abbildung 4). Es stellt den Anfang einer Liste von Objekt- Caches dar. Jeder Cache (»struct cache«) ist für genau einen Objekttyp verantwortlich. Er verwaltet die so genannten Slabs, in denen sich die Objekte befinden. Ein Slab (Kachel) ist ein aus Seiten bestehender Speicherbereich mit jeweils mehreren Objekten.

Ein Cache verwaltet drei Arten solcher Slabs: erstens die Slabs, deren Objekte alle in Gebrauch sind, zweitens die Slabs, deren Objekte partiell verwendet werden, und schließlich die Slabs, deren Objekte zwar initialisiert, aber unbenutzt sind. Durch diese Dreiteilung beschleunigt sich die Reservierung und Freigabe der Objekte.

Wie viele Seiten einen Slab bilden, hängt vom Speicherbedarf eines einzelnen Objekts ab. Für kleine Objekte (weniger als 512 Byte) reserviert der Allokator grundsätzlich nur eine Speicherseite. Für größere Objekte blockt er dagegen so viele Seiten, dass der Verschnitt nicht mehr als 12,5 Prozent beträgt (1/8 Page). Verschnitt entsteht allerdings schnell: Würde ein Objekt beispielsweise 2052 Byte belegen, könnte man in einer Page von 4 KByte genau ein Objekt unterbringen. Damit blieben 2044 Byte des Speichers ungenutzt.

01 #include <linux/module.h>
02 #include <linux/completion.h>
03 #include <linux/slab.h>
04 ...
07 static int ThreadID=0;
08 static DECLARE_COMPLETION(OnExit);
09 static kmem_cache_t *cache;
10 
11 struct linobj {
12    int dummy_i, dummy_j, dummy_k;
13    char dummy_feld[250];
14 };
15 
16 static void linobj_destructor(void *objp, kmem_cache_t *cache,
17         unsigned long flags)
18 {
19    printk("linobj_destructor(%p)n", objp);
20    return;
21 }
22 
23 static void linobj_constructor(void *objp, kmem_cache_t *cache,
24         unsigned long flags)
25 {
26    if(flags&SLAB_CTOR_VERIFY)
27            return;
28    printk("linobj_constructor(%p)n", objp);
29    return;
30 }
31 
32 static int ThreadCode(void *data)
33 {
34    unsigned long timeout;
35    int i;
36    struct linobj *obj;
37 
38    daemonize("linobj-test");
39    allow_signal(SIGTERM);
40    for(i = 0; i < 5; i++) {
41       obj = (struct linobj *)kmem_cache_alloc(cache, GFP_KERNEL);
42       printk("objadr=%pn", obj);
43       timeout=HZ;
44       set_current_state(TASK_INTERRUPTIBLE);
45       timeout=schedule_timeout(timeout);
46       kmem_cache_free(cache, obj);
47       if(timeout)
48          break;
49    }
50    complete_and_exit(&OnExit, 0);
51 }
52 
53 static int __init slabInit(void)
54 {
55    cache = kmem_cache_create("linobj", sizeof(struct linobj),
56            0, 0, linobj_constructor, linobj_destructor);
57    if(!cache)
58       return -EFAULT;
59    ThreadID = kernel_thread(ThreadCode, NULL, CLONE_KERNEL);
60    if(ThreadID == 0)
61       return -EIO;
62    return 0;
63 }
64 
65 static void __exit slabExit(void)
66 {
67    kill_proc(ThreadID, SIGTERM, 1);
68    wait_for_completion(&OnExit);
69    if(cache)
70       kmem_cache_destroy(cache);
71 }
72
73 module_init(slabInit);
74 module_exit(slabExit);

Abbildung 4: Der Slab-Allocator verwaltet mehr als 100 unterschiedliche Kernelobjekte in jeweils eigenen Cache. Jeder Cache besteht aus drei Gruppen von Slabs, in denen sich die Objekte befinden.

Abbildung 5 zeigt, dass bei Verwendung von zwei Pages der ungenutzte Platz pro Objekt mit knapp 679 Byte wesentlich geringer ausfällt. Vom Verschnitt hängt es auch ab, ob die Verwaltungsstruktur für den Slab (der Slab-Descriptor) im Slab selbst steht oder separat gehalten werden muss.

Abbildung 5: Um den Verschnitt klein zu halten, nutzt der Slab-Allocator für Objekte, die größer als 512 Byte sind, mehrere Pages für eine Kachel (ein Slab).

Konformisten

Der Objekt-Cache kommt auch für nicht typisierte Objekte, also für normalen Speicher zum Einsatz. Die bekannten Funktionen »kmalloc()« und »kfree()« basieren ebenfalls auf dem Slab-Allocator. 26 Caches stellen generische Objekte in den Größen 32, 64, 128, 256 und so weiter bis zu maximal 131072 Byte (je einmal aus der »ZONE_NORMAL« und einmal aus der »ZONE_DMA«) bereit. Der Unterschied zwischen den generischen und den typisierten Objekten besteht darin, dass Erstere keine Konstruktor- und keine Destruktor-Funktion zur Verfügung stellen.

Die fixen Objektgrößen der generischen Objekte deuten aber an, dass ein Programmierer, der 132 Byte anfordert, damit zugleich 124 Byte Verschnitt produziert. Benötigt der Entwickler häufiger einen Speicherbereich dieser krummen Größe, ist das Anlegen eines eigenen Objekt-Cache empfehlenswert. Listing 1 zeigt, wie man das macht. Insbesondere demonstriert es die Verwendung von Konstruktor und Destruktor.

01 TARGET=slab.o
02 
03 ifneq ($(KERNELRELEASE),)
04 obj-m       := ${TARGET}
05 
06 else
07 KDIR    := /lib/modules/$(shell uname -r)/build
08 PWD     := $(shell pwd)
09 
10 default:
11         $(MAKE) -C $(KDIR)  SUBDIRS=$(PWD) modules
12 endif

Abbildung 6: Die Proc-Datei »/proc/slabinfo« informiert über Objekttypen, ihren Aufbau und ihre Verwendung.

Der Parameter »objp« ist der Zeiger auf den Objektspeicher, »cache« spezifiziert den Cache und »flags« übergibt die Zugriffsflags. Die Datei »<linux/slab.h>« definiert drei Flags : »SLAB_CTOR_CONSTRUCTOR« ist beim Aufruf des Konstruktors gesetzt, nicht aber beim Aufruf des Destruktors. »SLAB_CTOR_ATOMIC« bedeutet, dass der Konstruktor nicht schlafen darf, und »SLAB_CTOR_VERIFY« bedeutet, dass der Aufruf des Konstruktors nur der Überprüfung dient. Ist dieses Flag gesetzt, kehrt der Konstruktor im Regelfall direkt zurück (siehe Listing 1, Zeile 27).

Mit Hilfe eines Makefile in Listing 2 lässt sich aus dem Code aus Listing 1 ein Kernelmodul bauen. Nach dem Laden per »insmod slab.ko« legt der Slab-Allocator den neuen Cache »linobj« an. Gleichzeitig startet er einen Thread, der fünf Sekunden lang jeweils ein Objekt anfordert und danach wieder freigibt. Spätestens beim Entladen (»rmmod slab«) ruft er den Destruktor auf.

Ein Blick in »/proc/slabinfo« zeigt, dass das Objekt »linobj« 264 Bytes Speicher benötigt. Damit passen 15 dieser Objekte in einen Slab, wobei ein Slab aus einer Page besteht (Abbildung 6).

kmem_cache_t * kmem_cache_create (const U char *name, size_t size, size_t align, U unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long), void U (*dtor)(void*, kmem_cache_t *, unsigned U long))

int kmem_cache_destroy (kmem_cache_t * U cachep)

void * kmem_cache_alloc (kmem_cache_t U *cachep, int flags)

vvoid kmem_cache_free (kmem_cache_t U *cachep, void *objp)

Solaris’ Erbe

Die anderen, hier nicht erwähnten Parameter in »/proc/slabinfo« deuten an, dass der Slab-Allocator noch weitere Raffinessen bietet. Neugierige sollten einen Blick in die Papers des Slab-Erfinders Jeff Bonwick ([2],[3]) werfen, der 1994 diese Technologie in Solaris eingebaut hat. Wer sich mehr für die Linux-Implementierung interessiert, wird in[4],[5] und[6] fündig. Bleibt zum Abschluss noch der Hinweis, dass sich die hier beschriebenen Verfahren nicht nur in diversen Betriebssystemen finden. Auch Applikationen profitieren von der effizienten Technik, zum Beispiel das Speichermanagement von Perl. (ofr)