malloc が Serenity の JPGLoader を壊した事件、あるいは: 宝くじ当選の秘訣 (2021)

• malloc が SerenityOS の JPGLoader を壊した理由

• SerenityOS で JPG 画像をデコードする際に色が誤って表示されるバグを調査した

  • RGB と BGR の混同のように見えたが、コードを修正しても問題は解決しなかった

• Bisecting による問題追跡

  • 直近 1000 件のコミットを bisecting して問題の原因を探し始めた
  • SerenityOS は独自の標準ライブラリ AK を使用しており、これは C++ の STL に似ているが、より読みやすい
  • AK の変更が OS 全体に影響するため、ビルド時間が長くなる

• Bisect の結果

  • 問題を引き起こしたコミットを特定した: malloc_good_size() を実装したコミット
  • このコミットは、メモリ割り当てサイズを最適化してメモリの無駄を減らす機能を追加した

• 驚きの発見

  • HashTable と Vector が問題の原因である可能性を調査した
  • HashTable の容量を変更したところ問題が解決した

• 非決定的なシリアルコンポーネント反復

  • JPGLoader は JPG ファイルのコンポーネントを HashTable に保存し、反復的に使用していた
  • コンポーネントの順序が非決定的だったため問題が発生した

• バグの原因

  • HashTable に順序が必要なオブジェクトを保存し、デフォルトのイテレータを使用していた
  • コンポーネント ID のハッシュ値が偶然正しい順序に並んでいた
  • HashTable のサイズ変更によって順序が変わり、問題が発生した

• 解決策

  • JPGLoader がコンポーネントを決定的に反復するよう修正した
  • HashTable の代わりに順序が保証されるデータ構造を使用した

• 最後に

  • 単純な問題でも大きなミスを露呈させることがある
  • 問題を根本的に解決し、再発を防いだ

• 謝辞

  • デバッグに協力してくれた同僚たちに感謝したい
  • バグを発見し解決する過程で多くを学んだ

GN⁺のまとめ

• この記事は、SerenityOS で発生した JPG 画像デコードのバグを追跡し、解決する過程を扱っている
• HashTable の非決定的な順序によって生じた問題を、決定的な順序に変更することで解決した
• この記事は、ソフトウェアのデバッグ過程の重要性と複雑さをよく示している
• 類似の機能を持つプロジェクトとしては Linux の libjpeg などがある