marcs blog

• Das unendliche Hartz-IV-Trauerspiel
  Eine kurze Analyse der aktuellen Hartz-IV Tragödie von Michael Spreng.


• Laufzeitfehlern auf der Spur
  Ein kleiner Blick in die Werkzeugkiste von C-Programmierern.


• (


• hr2 Der Tag
  Empört Euch! heißt das Büchlein des aus Deutschland stammenden Franzosen Stéphane Hessel. Der alte Herr plädiert in seinem längst zum Bestseller gewordenen Manifest, das nun auch in Deutsch erscheint - für die Wiederbelebung der Werte der französischen Résistance, in der er selbst mit gekämpft hat.
  (Download) (via)
  

Ich bin letzte Woche über einen schicken C-Codeschnipsel gestolpert, dessen Quintessenz ich hier gerne im Detail festhalten möchte.

Der wesentliche Knackpunkt hier ist der, daß sich mit folgendem Assert-Makro sizeof-Checks bereits zur Compilezeit machen lassen und nicht erst zur Laufzeit passieren:

#define CONCAT2(X,Y) X##Y

#define CONCAT(X,Y)  CONCAT2(X,Y)

#define MYASSERT(expr) \

  typedef char CONCAT(Assertion_In_Line_,__LINE__)[(expr)?1:-1]

MYASSERT(42 == sizeof(extVar));

Hübsch, nicht?

Aber fangen wir mit den leichten Sachen an.
Die beiden ##-Zeichen in Zeile 1 sind ein Operator für den Präprozessor, die lediglich aus den beiden Strings X und Y einen String XY machen. Das function-like Makro CONCAT2 liefert also einen verbundenen String zurück.

In Zeile zwei wird eine Indirektion hinzugefügt, indem CONCAT auf CONCAT2 gemappt wird. Dies ist notwendig, damit der Präprozessor das __LINE__ in Zeile 4 evaluiert, und nicht einfach das "__LINE__" als solches anhängt.
Eine schöne, detaillierte Erklärung für die Notwendigkeit dieser Indirektion gibt es hier.

Das __LINE__ ist ein vordefiniertes Makro und wird automatisch durch die Zeilennummer ersetzt, in der es verwendet wird. Wir verbinden in Zeile 4 also den Bezeichner "Assertion_In_Line_" mit der aktuellen Zeilennummer. Wenn das Assert zuschlägt, sehen wir in der Compiler-Meldung dann die Zeile, in der das passiert ist.

In Zeile 3 wird jetzt unser Assert-Makro definiert. "expr" sollte eine Bedingung sein, die wahr oder falsch zurückliefert. Das wäre in diesem Fall später der sizeof-Vergleich.

Wer es bis jetzt noch nicht erkannt hat: Zeile 4 enthält eine Array-Deklaration.
Das Array hätte in unserem Fall den Namen "Assertion_In_Line_5", weil das __LINE__ wie gesagt durch die Zeile ersetzt und mit CONCAT an den Array-Namen angehängt wird.

Die Größe des Arrays ist nun abhängig von dem übergebenen Ausdruck. Wir haben in den eckigen Klammern eine if-else Anweisung mittels Fragezeichen-Operator. Wenn der Ausdruck wahr ist, wird 1 zurückgegeben, ist er falsch, bekommt das Array eine Größe von -1.
Die Deklaration von Arrays mit negativer Größe ist in C aber nicht erlaubt und daher gibt es an dieser Stelle dann einen Compilerfehler.

Mal angenommen ich hätte jetzt eine externe Variable namens "extVar", die nicht 42 Byte groß wäre, dann würde mir der GCC folgenden Fehler beim Kompilieren geben:

test.c:5: error: size of array ‘Assertion_In_Line_5’ is negative

Der GCC gibt netterweise schon die Zeilennummer selber aus, d.h. man hätte sich das mit dem __LINE__ auch sparen können, aber so nett ist nicht jeder Compiler.

Bleibt zum Schluß noch eine Frage offen: Warum steht da ein typedef und nicht eine ganz normale Array-Deklaration?
Der Grund ist der, daß ein typedef keinen Platz im Kompilat belegt. Wenn das Assert nicht zuschlägt, hätten wir im kompilierten Binary eventuell mehrere Assertion_In_Line_* Arrays mit jeweils einer Größe von einem Byte enthalten. Durch das typedef wird diese Platz-Verschwendung vermieden.

Beim Programmieren ist einem im Laufe der Jahre ja schon oft genug ein Null-Pointer auf den Fuß gefallen. Aber alle Null-Pointer-Checks der Welt bringen nichts, wenn man einen Zeiger kriegt, der auf die Adresse 0x00000001 zeigt.
So doof habe ich jedenfalls schon lange nicht mehr geschaut, als ich den Bug gefunden habe.

Und das hatte noch nichtmal was mit Zeiger-Arithmetik zu tun, das wär ja auch zu offensichtlich gewesen, sondern eher mit void-Pointer Typecasts auf unterschiedlich geschachtelte Structs, die man erst zur Laufzeit kennt.
Kein schönes Thema, aber ich steh ja auf sowas.

• The Ineffectiveness of Security Cameras
Eine Studie über den Einfluß von Überwachungskameras auf die Verbrechensrate in San Francisco.
Ergebnis: Die Rate ist nicht gesunken, aber angeblich würden sich die Bürger sicherer fühlen. Also nur rausgeschmissenes Geld für ein Sicherheits-Theater ohne effektiven Nutzen, dafür mit Kollateralschäden in der informationellen Selbstbestimmung.


• Wie man einen Staat zerstört
Ein 20 Punkte Plan. 19 davon wurden so wie's aussieht schon ziemlich gut umgesetzt.


• Der Humanist der Physik - zum 150. Geburtstag von Max Planck
Interessanter Artikel, auch das dort verlinkte Video-Selbstporträt war mir neu. Standing on the shoulders of giants.


• unsubscribe-me.org
Eine Aktion von Amnesty International gegen Folter. Die Videos sollen u.a. verdeutlichen was beim harmlos klingenden Waterboarding wirklich passiert.
Das Video kommt allerdings, wie ich finde, nicht annähernd an diese Beschreibung eines Waterboarding-Selbstversuchs ran.

In diesem Zusammenhang auch interessant war eine Fragerunde mit dem US-Justizminister Ashcroft, dessen Argumentation bezüglich Waterboarding von einer 20-jährigen Studentin zerpflückt wurde, und der sich dann brüllend in Wortklaubereien verliert. (via)
Daß Bush ja ein Veto gegen ein Gesetz eingelegt hat, das der CIA das Waterboarden verbieten soll, erwähne ich mal noch der Vollständigkeit halber hier.
Da macht die Menschheit unglaubliche technische Fortschritte, aber gesellschaftlich gesehen sind wir immer noch im finstersten Mittelalter.
Ich möchte übrigens wetten, daß es nicht mehr lange dauert, bis auch hierzulande soetwas von diversen Behörden gefordert wird. Würde sich als Ergänzung zum BKA-Gesetz ja anbieten. Ich tippe mal darauf, daß das noch in diesem Jahr geschieht.
Der ursprüngliche Kandidat für das Vizepräsidentenamt des Bundesverfassungsgericht war ja z.B. ein Befürworter von solchen Foltermethoden, aber der wurde glücklicherweise erstmal abgesägt.


• I2P release 0.6.1.33
Für I2P gibt es ein Update. Die .32er hatte einige Performanceprobleme, die hier wohl behoben wurden.
"The 0.6.1.33 release contains several important bug fixes and performance improvements in SSU reachability detection, floodfill peer selection, tunnel peer selection, tunnel testing, NTCP idle detection, the streaming lib, and news fetching."


• CERT Secure Coding Standards
Eine Sammlung von Ratschlägen zum sicheren Programmieren unter C und C++. Inklusive Risiko-Abschätzung und Wahrscheinlichkeit des Auftretens der sicherheitskritischen Programmierfehler und wie man sie vermeidet.


• Der Konvent für Deutschland und unsere Verfassung
Chris von F!xmbr nimmt die Buchveröffentlichung des Konvents zum Anlass einen kritischen Rundumschlag gegen diese Leute abzuliefern.
(Bei diesem Thema sei auch noch auf das INSM Watchblog verwiesen, das ich hier noch nicht verlinkt hatte.)

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.