Der Vorfall, bei dem malloc Serenitys JPGLoader kaputtmachte, oder: Wie man im Lotto gewinnt (2021)

• Der JPG-Farbfehler in SerenityOS sah wie ein Problem mit der Reihenfolge der RGB/BGR-Argumente aus, begann tatsächlich aber damit, dass JPGLoader Komponenten, deren Reihenfolge wichtig ist, der Iterationsreihenfolge einer HashTable überließ
• Durch die Einführung von malloc_good_size() in AK+LibC nutzten Vector und HashTable die tatsächliche Größe von malloc-Chunks aus; dadurch änderte sich die Anzahl der HashTable-Buckets, wodurch ein verborgener Bug sichtbar wurde
• Der bestehende Code las die JPG-Komponenten Y, Cb, Cr zufällig in der richtigen Reihenfolge; weil das Ergebnis von int_hash und die Bucket-Anzahl zusammenpassten, blieb ein Fehler bei der Verarbeitung des Huffman-Streams verborgen
• Die Ursachenforschung begann damit, dass JPGLoader.cpp zuletzt nicht geändert worden war; wegen AK-Änderungen musste beim Bisect über 1000 Commits das etwa 3400 Dateien große OS mehrfach vollständig neu gebaut werden
• Die endgültige Korrektur bestand darin, die Komponenten in deterministischer Reihenfolge zu durchlaufen; ein Workaround, der nur die Reihenfolge der Farbargumente änderte, hätte beim nächsten Reihenfolgewechsel dasselbe Problem erneut verursachen können

---

JPG-Farbfehler, der wie eine RGB/BGR-Verwechslung aussah

• In SerenityOS trat ein Problem auf, bei dem JPG-Bilder mit falschen Farben angezeigt wurden
• Wenn man in JPGLoader.cpp die Reihenfolge der Argumente für den Color-Konstruktor änderte, sah das Bild wieder korrekt aus
  • Bisheriger Code: Übergabe in der Reihenfolge Y, Cb, Cr
  • Vorübergehende Änderung: Übergabe in der Reihenfolge Cr, Cb, Y
• Die letzte Nicht-Revert-Änderung an JPGLoader.cpp lag laut Git jedoch mehr als einen Monat zurück, und es gab die Erinnerung, dass JPG-Hintergrundbilder vor ein bis zwei Wochen noch korrekt angezeigt wurden
• Daher wurde es wahrscheinlicher, dass es sich nicht um einen einfachen Fehler in der Reihenfolge der Farbkanäle handelte, sondern dass eine andere Änderung einen bestehenden Bug offengelegt hatte

Durch AK-Änderungen erschwertes Bisect

• SerenityOS verwendet seine eigene Standardbibliothek namens AK (Agnostic Kit)
  • AK erfüllt eine ähnliche Rolle wie die C++ STL, wird aber im selben Repository zusammen mit dem Betriebssystemcode geändert
• Wenn sich AK ändert, ist der Wirkungsbereich groß
  • Eine Standardbibliothek wird von fast jedem Code eingebunden
  • Da C++-Templates in Headern definiert sein müssen, führen Änderungen an AK-Headern zu umfangreicher Neukompilierung
• Jedes Mal, wenn beim Bisect ein Commit mit AK-Änderungen passiert wurde, musste das gesamte Betriebssystem neu gebaut werden
  • Zum Zeitpunkt des Artikels etwa 3400 Dateien
  • Während des Bisects über einen Bereich von 1000 Commits wurde auf einem Sandy-Bridge-Mobile-Laptop von 2011 vier- bis fünfmal ein vollständiger Build durchgeführt
• Auch ccache konnte diesen Fall nicht abfangen, und wegen der hohen Änderungsgeschwindigkeit des SerenityOS-Projekts änderte sich AK ungefähr alle 100 Commits

Das durch malloc_good_size() sichtbar gewordene versteckte Problem

• Nach dem Bisect über 1000 Commits stellte sich heraus, dass die Änderung, die die JPG-Farben kaputtmachte, nicht in JPGLoader, sondern in AK+LibC lag
• Der Commit, der das Problem sichtbar machte, war f89e8fb71a4893911ee5125f34bd5bbb99327d33
  • Titel: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
  • Zeitpunkt: 15. Mai 2021
• Dieser Commit implementierte die macOS-API malloc_good_size()
  • Sie gibt für eine angeforderte Allokationsgröße die tatsächliche Allokationsgröße zurück
  • Wenn zum Beispiel eine Anfrage über 35 Byte intern einen 64-Byte-Chunk verwendet, können die übrigen 29 Byte genutzt werden
• Nach der Änderung nutzten Vector, HashTable und andere Strukturen den innerhalb eines malloc-Chunks verfügbaren Speicher besser aus
• Da JPG-Bilder im unmittelbar vorherigen Commit korrekt angezeigt wurden, ließ sich eingrenzen, dass diese Änderung ein bereits vorhandenes, verstecktes Problem offengelegt hatte

Decoding, das sich auf die Kapazität der HashTable verließ

• Zunächst bestand der Verdacht, dass JPGLoader oder Code darüber fälschlicherweise von der Kapazität eines Vector abhing und direkt hineinschrieb
• Die betreffende Änderung betraf sowohl HashTable als auch Vector, und beide wurden im JPGLoader-Code verwendet
• Als testweise die Zeile entfernt wurde, die kmalloc_good_size() auf der HashTable-Seite anwendete, und danach neu gebaut wurde, verschwand das Problem
  • Der entfernte Code passte die neue Bucket-Kapazität an die tatsächliche Allokationsgröße an
• Damit war bestätigt, dass eine Änderung der Bucket-Anzahl der HashTable das Ergebnis des JPG-Decodings beeinflusste
• Eine HashTable ist kein Container, der wie ein zusammenhängender Datenstrom verwendet wird; ihre Kapazität oder Iterationsreihenfolge darf daher nicht als Grundlage dienen

Wie JPG-Komponenten verarbeitet wurden

• Der bestehende JPGLoader las im Start-of-Frame-Abschnitt der JPG-Datei Komponenteninformationen und speicherte sie in einer Component-Struktur
• Jede Component besaß eine serial_id, die ihre Position innerhalb der JPG-Datei angab
  • Die Reihenfolge der JPG-Komponenten sollte normalerweise Y, Cb, Cr sein
• Diese Komponenten wurden in einer HashTable gespeichert
  • Später wurden sie verwendet, um sie mit der Komponentenreihenfolge im Start-of-Scan-Abschnitt zu vergleichen und zu prüfen, ob die erwartete Reihenfolge vorliegt
• In der Decoding-Phase wurden diese Komponenten durchlaufen, um die für die Makroblock-Transformation nötigen Informationen zu verwenden
• Das Problem bestand darin, dass Komponenten, deren Reihenfolge wichtig ist, in eine HashTable gelegt und mit dem Standard-Iterator durchlaufen wurden

Unterschiedliche Iterationsreihenfolge zwischen kaputtem und funktionierendem Commit

• In dem Commit mit den kaputten Farben durchlief die Debug-Ausgabe die Komponenten in folgender Reihenfolge
  • 0
  • 2
  • 1
• Im unmittelbar vorherigen, funktionierenden Commit war die Reihenfolge anders
  • 0
  • 1
  • 2
• Dieser Unterschied hing mit dem Ergebnis zusammen, das wie vertauschte Farbkanäle aussah
• Beim manuellen Ändern der Komponentenreihenfolge zusammen mit CxByte trat folgender Fehler auf
  • Huffman stream exhausted. This could be an error!
  • Failed to build Macroblock 3277
• Dieser Fehler machte sichtbar, dass das JPG-Decoding empfindlich gegenüber der Stream-Reihenfolge ist, und bestätigte, dass die Iterationsreihenfolge der Komponenten die zentrale Ursache war

Zufällig passende HashTable-Reihenfolge

• Die eigentliche Ursache war, dass Objekte, für die eine Reihenfolge erforderlich ist, in einer HashTable gespeichert und mit dem Standard-Iterator durchlaufen wurden
• Der Hash der JPG-Komponenten-IDs wurde über int_hash zur Auswahl des Buckets verwendet
• Zuvor hatten zwei Zufälle gleichzeitig gepasst
  • Das Ergebnis von int_hash für die Werte 0, 1, 2 war stabil
  • Die Bucket-Anzahl von AK::HashTable passte genau so, dass die Komponenten in der richtigen Reihenfolge platziert wurden
• Dank dieses Zufalls las JPGLoader den Huffman-Stream für jede Komponente in der richtigen Reihenfolge, und der Bug blieb von Anfang an verborgen
• Mit der Einführung von malloc_good_size() änderte sich die Bucket-Anzahl der HashTable, dadurch änderte sich die Komponentenreihenfolge, und es erschienen Bilder mit vertauschten roten und blauen Kanälen

Endgültige Korrektur durch deterministische Iteration

• Nach etwa 10 Stunden Debugging entstand der Fix-Commit
• Der Fix-Commit ist a10ad24c760bfe713f1493e49dff7da16d14bf39
  • Titel: LibGfx: Make JPGLoader iterate components deterministically
  • Zeitpunkt: 31. Mai 2021
• Der Kern der Korrektur bestand darin, dass JPGLoader die Komponenten in deterministischer Reihenfolge durchläuft
• Auch eine bloße Änderung der Argumentreihenfolge für Color hätte die Bilder zunächst wieder korrekt aussehen lassen, hätte aber bei einer späteren Änderung der Iterationsreihenfolge erneut brechen können
• Ein Problem, das wie ein kleiner Darstellungsfehler aussah, stellte sich als Fall heraus, in dem eine falsche Abhängigkeit von der Iterationsreihenfolge eines Containers zusammen mit einer Änderung der Allokationsgröße sichtbar wurde

[GN⁺]

Hacker-News-Kommentare

• Das ist einer der Gründe, warum viele Hash-Table-Implementierungen ein zufälliges Element in den Algorithmus einbauen.
  Da sich die Reihenfolge der Elemente bei jeder Ausführung ändert, fallen versehentliche Abhängigkeiten von der Reihenfolge schnell auf.
  Wenn der Hash-Algorithmus fest ist, kann man Schlüssel erzeugen, die alle im selben Bucket landen, und das für Denial-of-Service-Angriffe missbrauchen; auch solche Sicherheitsprobleme lassen sich damit ziemlich gut abwehren.

  • Heutzutage gibt es umgekehrt auch viele Implementierungen, die garantieren, dass eine Hash Table immer in Einfügereihenfolge iteriert wird.
    Ich bevorzuge das, weil man dann nicht jedes Mal entscheiden muss, ob man eine sortierte oder eine unsortierte Map braucht.
    Ich bin schon öfter davon ausgegangen, dass eine unsortierte Map reicht, und lag dann aus subtilen Gründen falsch.
  • Wenn das zufällige Element ein Seed ist, der erzwungen, gespeichert, geloggt und reproduziert werden kann, ist es in Ordnung.
    Andernfalls ist es eine wirklich schlechte Idee, weil es das Debuggen anderer Probleme erheblich erschwert.
    Zufälligkeit ist kein Freund, sondern ein Feind.
    Vor etwa 20 Jahren gab es bei Angriffen auf Java-Webserver die Methode, URL-Parameter so zu manipulieren, dass sie alle im selben Bucket landeten; das wurde zu einem großen Denial-of-Service-Angriff.
    Wenn ich mich richtig erinnere, hatten PHP-Webserver genau dasselbe Sicherheitsproblem.
    Behoben wurde es, indem man der Hash Table einen Seed gab, und dieser Seed war natürlich vom Entwickler kontrollierbar. Denn Zufälligkeit ist kein Freund, sondern ein Feind.

• Das wirkt wie ein Fall, in dem man Zeit gespart hätte, wenn man etwas mehr debuggt hätte, statt blind eine bisect-artige binäre Suche zu machen.
  Logs, die die Komponentenreihenfolge ausgeben, musste man am Ende ohnehin einbauen.

• Das Debugging war gut, aber auch die Commit-Message ist hervorragend.
  Sie fasst Ursache und Fix in wenigen Absätzen sehr gut zusammen.

• Wenn man lange genug wartet, bekommt auch C++ irgendwann ein Gegenstück zu malloc_good_size.
  https://github.com/cplusplus/papers/issues/18

• Im Titel braucht es [2021].

• Das ist nicht Gunnars Schuld. Das Problem liegt bei der Seite, die geordnete Daten in einer Hash-Datei gespeichert hat.
  In Jahrzehnten dieser Arbeit habe ich mehrmals erlebt, dass eine geänderte Speicheranordnung versteckte Bugs ans Licht bringt.
  Jedes Mal kostet das Debugging Stunden bis Tage.
  Wenn Programmieren nicht schwierig wäre, würde man uns nicht brauchen. Allerdings weiß ich nicht, wie lange dieser Satz im Zeitalter großer Sprachmodelle noch Bestand hat.

  • Stimmt. Selbst wenn es Gunnars Schuld gewesen wäre, müsste man das wohl nicht unbedingt in die Commit-Message schreiben.
    Gunnar hat etwas verbessert, und dabei ist nur ein Problem in altem kaputtem Code sichtbar geworden.
    Als Lohn für diese Mühe bekommt er dann aber so etwas zu hören wie: „Gunnar, I like you, but please don't make me go through this again. :^)“
  • Solange große Sprachmodelle mit buggy Code trainiert werden, werden sie buggy Code vorschlagen.
  • Stimmt. Und entgegen dem Titel ist es auch nicht die Schuld von malloc().

• Soweit ich weiß, gibt es bei SerenityOS Leute, die einander mit Testressourcen oder PCs aushelfen.

• SerenityOS auf einem Sandy-Bridge-Mobile-Laptop von 2011 vier- bis fünfmal von Grund auf zu bauen, ist ungefähr so, als wollte man auf einem Computer aus der Zeit zwischen Windows 3.1 und Windows 95 Windows Vista entwickeln.

  • Vom zeitlichen Abstand her passt das, aber gemessen an der tatsächlichen Leistung nicht.
    Seit 2011 haben sich CPUs relativ gesehen nicht so stark verändert, während zwischen Windows 3.1 und Vista x64 verbreitet wurde und Multicore-CPUs üblich wurden.
  • Guter Vergleich. Die CPU des Entwicklers ist ungefähr 13 Jahre alt.
    Vista wurde Anfang 2007 international veröffentlicht; eine zum Release-Zeitpunkt 13 Jahre alte CPU wäre also von 1994, etwa ein Jahr nach dem ursprünglichen Pentium.
    Damals nutzten viele noch immer den zuverlässigen 486 DX2-66.
    Es ist ziemlich beeindruckend, dass eine 13 Jahre alte CPU heute noch für die Arbeit an einem modernen Projekt brauchbar ist. Damals konnte man das kaum sagen.
    Ich hoffe, dass auch heute erscheinende CPUs bis nach 2037 zufriedenstellend nutzbar bleiben.
  • Im vergangenen Jahr habe ich als Haupt-Desktop einen Lenovo i5 von 2011 mit Windows 11 und zwei Monitoren verwendet.
    Visual Studio läuft darauf gut, und auch Photoshop ist nur bei den integrierten KI-Tools ein ganz klein wenig träge.
    In Chrome sind vermutlich rund 200 Tabs offen, dazu Slack, WhatsApp und drei Browser zum Testen.
    Bei CapCut wünschte ich mir bei 4K-Schnitt etwas mehr Tempo, aber komplexe 2K-Projekte hält es ausreichend gut durch.
    Nur bei komplexen After-Effects-Projekten bin ich etwas an Grenzen gestoßen. Die mochte es nicht.
    Ich sollte aufrüsten, aber für ein System, das praktisch aus dem Müll gerettet wurde, ist es ziemlich ordentlich.

• Bei „Alien Lenna“ hatte ich ein Gefühl von Déjà-vu; tatsächlich war es ein Beitrag, den ich schon früher gesehen und sogar kommentiert hatte.
  https://news.ycombinator.com/item?id=27374942 (2021)