marcs blog

Eine meiner Nachrichtenquellen aus der IT-Welt ist seit vielen, vielen Jahren die Webseite OSNews. Wie der Name schon andeutet, liegt der Schwerpunkt in der Berichterstattung auf Neuigkeiten über alle möglichen Betriebssysteme. Oder sollte ich sagen: "lag"?

Vor kurzem gab es dort einen Artikel Why OSNews Is No Longer OSNews. Dort wird auf einen Kritikpunkt der Leser eingegangen, daß sich der Schwerpunkt von Betriebssystemen mehr zu Themen verlagert habe, die das Web oder Mobil-Telefone betreffen. Der Antwort, daß sich in der Hinsicht einfach weniger aufregendes ereignet im Vergleich zu früher, kann ich nicht uneingeschränkt zustimmen.

Bestes Gegenbeispiel wäre unter anderem Heises Kernel-Log, wo detailliert über aktuelle Entwicklungen, den Linux-Kernel betreffend, berichtet wird.
Nun habe ich nicht vor es dem Heise-Verlag gleichzutun, schon allein deshalb, weil das Lesen (und Verstehen) der Beiträge auf der LKML einen Vollzeit-Job erforderte.

Ich habe allerdings vor von nun an regelmäßige Neuigkeiten aus der Welt der Betriebssysteme aufzugreifen und hin und wieder auch den ein oder anderen Praxisbericht zu erstellen. Da ich schon immer ein Faible dafür hatte, alle möglichen Betriebssysteme auszuprobieren, die mir unter die Finger kamen, bin ich in der Thematik also auch nicht ganz unbedarft, insbesondere was so manch exotische oder eingebettete Systeme betrifft.

Hierfür gibt es auch eine neue Kategorie im Blog, nämlich BSNews, in der die Einträge diesbezüglich einsortiert werden.

Und den Anfang heute macht der Hinweis auf eine Beitragsreihe über Embedded Programing Pattern des BeRTOS-Projekts, in dem sich der erste Beitrag dieser Reihe mit der Entwicklung einer Applikation ohne drunterliegenden Kernel befaßt.

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.

• Lücke in WordPress ermöglicht Ändern von Nutzerbeiträgen
Irgendwie bin ich ja doch froh, daß ich gewechselt habe. Als hätte man's geahnt.


• Rainbow Hash Cracking
Interessanter Artikel über Rainbow Tables mit ein paar Zahlen über die Effizienz. Allerdings ist der Teil über gesalzene Hashes etwas auf Kritik gestoßen, die sich unter


• Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes
findet. Durchaus lesenswert, wenn man sich mal Gedanken drüber machen muß, wie und ob man Paßwörter speichert.


• Real Time and Embedded Guide
Umfangreicher Guide über den Aufbau von Echtzeit-Betriebsystemen auf embedded devices. Schwerpunkt liegt auf RTAI


• Traverso DAW
Multitrack audio recording & editing mit einem ungewöhnlichen Bedienkonzept. Noch nicht getestet, aber notiert