Ich beschäftige mich in letzter Zeit etwas mit Programmierung auf Embedded Systems. Unter anderem habe ich ein Stück Software portiert, was eine dynamische Speicherverwaltung braucht, denn es nutzt
malloc(),
realloc() und
free().
Das Problem ist, daß in meinem Fall die C-Library in dieser Hinsicht suboptimal ist und man eine eigene Speicherverwaltung braucht, da das verwendete OS in dieser Hinsicht auch nichts bietet. Das ganze ist für 1 MB an externem RAM, den die Hardware hat, und den es zu verwalten galt.
Eine Implementierung, die mir anfangs zur Verfügung gestellt wurde, verfolgte den algorithmisch einfachen Ansatz, daß Zeiger auf die belegten Blöcke in einem Array gespeichert wurden, und es für jeden Block einen Memory Control Block gab, der sich die nötigen Daten wie die Größe gemerkt hat und noch einige Flags zur Verwendung.
Diese Implementierung hatte zwei große Probleme: Die Laufzeit skalierte linear, d.h. je mehr Speicher belegt war, desto länger brauchten die Array-Durchläufe um freie Speicherblöcke zu finden, bzw. sie wieder freizugeben. So brauchten einige Funktionen der Software anfangs 10ms, und das schaukelte sich hinterher hoch auf 20 ms, was für dieses System viel zu viel war.
Das zweite Problem war die externe Fragmentierung. Ich bin mir nicht sicher, ob es ein Bug war, oder es wirklich an der Fragmentierung lag, jedenfalls wuchs der Speicherverbrauch bei mir nach einiger Zeit auf bis zu knapp 240 kb an.
Nach etwas Recherche im Netz bin ich dann auf TLSF (Two Level Segregate Fit) gestoßen. Das ganze stammt anscheinend von irgendeinem spanischen Institut. Unter
http://rtportal.upv.es/rtmalloc/ finden sich diverse Papers, Slides und eine Referenzimplementierung unter GPL/LGPL.
Desweiteren gibt es unter
http://tlsf.baisoku.org eine Nachimplementierung anhand des Papers und die steht unter Public Domain. Letztere habe ich auch verwendet und das Teil hat folgende nette Features:
- Konstante Laufzeit von O(1) für malloc, free, realloc
- Geringer Overhead (4 Byte pro Allokierung) und ca. 3 kb pro Memory Pool
- Niedrige Fragmentierung
- Belegt nur wenige KB an Code und Daten (bei mir waren's ca. 6,8 kb)
Das liest sich ja schonmal richtig gut.
Wie das Ding intern genau funktioniert (irgendwas mit doppelt verketteten Listen und Bitmaps) war mir erstmal egal, ich habe mich direkt auf einen praktischen Test gestürzt.
Wie verwendet man das nun in seiner Software?
Man inkludiert die tlsf.h und muß anschließend einen Memory Pool anlegen. Kleines Beispiel: Über Compiler Pragmas wurde einfach ein char Array mit 512kb im externen Ram reserviert, daß man dann dem TLSF übergibt.
unsigned char HEAP[0x80000]; /* im externen Ram, die Pragmas sind Compiler abhängig */
tlsf_pool mempool = tlsf_create(HEAP, 0x80000);
tlsf_create() initialisiert einen Memory Pool für TLSF und verwendet dafür den vorher durch das char Array reservierten Speicherbereich. Zurückgegeben wird ein Zeiger auf ein tlsf_pool Objekt.
Die malloc & Co Funktionen des TLSF haben eine andere Signatur, also baut man sich jetzt noch 3 Wrapper-Funktionen, die die TLSF-Funktionen aufrufen und somit von anderer Software verwendet werden können, ohne daß man diese anfassen muß.
void* malloc(size_t size){
return tlsf_malloc(mempool, size);
}
void* realloc(void *ptr, size_t size){
return tlsf_realloc(mempool, ptr, size);
}
void free(void *ptr){
tlsf_free(mempool, ptr);
}
Die Überprüfung der NULL-Pointer sei als Übung für den Leser gedacht.
Im übrigen sieht man hier auch, daß TLSF mehrere Memory Pools gleichzeitig verwalten kann. Das geht zwar so nicht über die Wrapper-Routinen, aber wenn man eigene Software hat, kann man die TLSF-Routinen ja direkt mit dem passenden Parameter aufrufen.
Hinweis am Rande: Die TLSF-Implementierung ist nicht
thread safe. Wenn das ein Problem ist, könnte man in diesen Wrapper-Funktionen
Critical Sections definieren, falls man den TLSF-Code nicht direkt anfassen möchte. Das ist allerdings auch nicht optimal, da die Section dann relativ groß ist.
Mal zum Vergleich, wo die Laufzeit der Funktionen vorher bei 10-20 ms lag, liegt sie mit der neuen Speicherverwaltung bei 1-2 ms, und das bleibt dank O(1) auch im längeren Betrieb konstant. Das heißt allein die Verwendung einer besseren Speicherverwaltung hat hier einen gewaltigen Performanceschub gebracht. Desweiteren ist der Overhead und die Fragmentierung deutlich geringer. Wo der Speicherverbrauch vorher bei knapp 240 kb lag, liegt er jetzt bei ca. 91 kb.
Also beide Daumen hoch für TLSF, ich bin wirklich begeistert davon.
Einziges Manko der Implementierung ist, daß sie nicht Buch darüber führt, wieviel Speicher gerade wirklich belegt ist. Es sind allerdings Debug-Routinen enthalten, die den Heap durchlaufen und Informationen über die einzelnen Speicherblöcke sammeln. Via
tlsf_walk_heap(mempool, NULL, NULL);
wird ein solcher Durchlauf gestartet und die default_walker()-Funktion gibt für jeden Block die Infos per printf aus. Letzteres ist allerdings nicht so toll, wenn man kein stdout hat.
Hier könnte man z.B alternativ globale Variablen definieren, die dann in dem default_walker() die Werte aufsummieren und im tlsf_walk_heap() immer neu initialisiert werden. Diese Variablen kann man dann schön im Debugger verfolgen. Dafür hab ich im default_walker folgenden if-Zweig ergänzt:
if (used) {
tlsf_used_blocks++; /* Anzahl belegter Blöcke */
tlsf_used_size += size; /* Belegter Speicher in Byte, inklusive Overhead durch TLSF */
/* Zur Laufzeit maximal belegter Speicher */
tlsf_used_size_max = tlsf_max(tlsf_used_size_max, tlsf_used_size);
}
else {
tlsf_free_blocks++; /* Anzahl der freien Blöcke */
tlsf_free_size += size; /* Freier Speicher in Byte */
}
Bis auf tlsf_used_size_max werden diese Variablen dann zu Beginn von tlsf_walk_heap() einfach wieder auf 0 gesetzt.
Ansonsten lassen sich auch eigene Walker-Routinen schreiben, die man dem tlsf_walk_heap() als zweiten Parameter übergeben kann.
Diese walk_heap-Durchläufe hatten bei mir allerdings auch eine nicht kleine Laufzeit von ungefähr 9 ms, wenn ich mich richtig erinnere. Im Produktivcode also definitiv nicht zu empfehlen. Eine interne Buchführung wäre da angenehmer und das sollte die Laufzeit eigentlich auch nicht allzu stark beeinflussen.
