Wie `malloc` den JPGLoader von Serenity kaputtmachte, oder: Wie man im Lotto gewinnt (2021)

• Warum malloc den JPGLoader von SerenityOS kaputtmachte

• Untersucht wurde ein Bug, bei dem beim Dekodieren von JPG-Bildern in SerenityOS die Farben falsch angezeigt wurden

  • Zunächst sah es nach einer Verwechslung von RGB und BGR aus, doch auch nach einer Codekorrektur war das Problem nicht behoben

• Fehlersuche per Bisecting

  • Um die Ursache des Problems zu finden, wurde ein Bisecting über die letzten 1000 Commits gestartet
  • SerenityOS verwendet mit AK eine eigene Standardbibliothek, die der STL von C++ ähnelt, aber besser lesbar ist
  • Änderungen an AK wirken sich auf das gesamte Betriebssystem aus, wodurch die Build-Zeiten lang werden

• Ergebnis des Bisecting

  • Der Commit, der das Problem verursachte, wurde gefunden: der Commit zur Implementierung von malloc_good_size()
  • Dieser Commit fügte eine Funktion hinzu, die die Größe von Speicherallokationen optimiert und so Speicherverschwendung reduziert

• Eine überraschende Entdeckung

  • Es wurde untersucht, ob HashTable und Vector die Ursache des Problems sein könnten
  • Nach einer Änderung der Kapazität von HashTable war das Problem behoben

• Nichtdeterministische Iteration serieller Komponenten

  • Der JPGLoader speichert die Komponenten einer JPG-Datei in einer HashTable und verwendet sie iterativ
  • Da die Reihenfolge der Komponenten nicht deterministisch war, trat das Problem auf

• Ursache des Bugs

  • Objekte, bei denen eine Reihenfolge nötig ist, wurden in einer HashTable gespeichert und mit dem Standard-Iterator verwendet
  • Die Hash-Werte der Komponenten-ID waren zufällig in der richtigen Reihenfolge angeordnet
  • Durch die Größenänderung der HashTable änderte sich die Reihenfolge, wodurch das Problem auftrat

• Lösung

  • Der JPGLoader wurde so geändert, dass er die Komponenten deterministisch iteriert
  • Statt HashTable wurde eine Datenstruktur verwendet, die eine garantierte Reihenfolge bietet

• Abschließende Gedanken

  • Selbst ein einfaches Problem kann große Fehler aufdecken
  • Das Problem wurde an der Wurzel behoben, um ein erneutes Auftreten zu verhindern

• Danksagung

  • Dank an die Kolleginnen und Kollegen, die beim Debugging geholfen haben
  • Beim Finden und Beheben des Bugs wurde viel gelernt

Zusammenfassung von GN⁺

• Dieser Artikel behandelt die Nachverfolgung und Behebung eines Bugs bei der Dekodierung von JPG-Bildern in SerenityOS
• Das durch die nichtdeterministische Reihenfolge einer HashTable verursachte Problem wurde gelöst, indem auf eine deterministische Reihenfolge umgestellt wurde
• Der Artikel zeigt die Bedeutung und Komplexität des Software-Debuggings sehr gut
• Ähnliche Projekte mit vergleichbarer Funktionalität sind etwa libjpeg unter Linux