LlosLabソフトウェア開発ブログPDF、Delphi、およびドキュメントソフトウェア開発者向けのエンジニアリングノート。

技術記事

HotXLS、zlib-ngのCRC32、そしてDelphiスレッドのスタックオーバーフロー

HotXLS Component

HotXLSは、大きなワークシートXMLパーツを1回の呼び出しでチェックサム計算する際、キャッチ可能な例外を一切発生させずにDelphiのワーカースレッドをクラッシュさせることがある:zlib-ngは入力がおよそ119KBを超えるとChorbaアルゴリズムに切り替わり、そのアルゴリズムの汎用C版は、既定の1MBのスレッドスタックを吹き飛ばすほど大きなスクラッチ配列を割り当てる。Delphiは反応する機会を一切得られない、なぜならスタックオーバーフローはtry/exceptが捕まえるために作られた類の例外ではないからだ

HotXLSはExcelワークブックの読み書き用のネイティブDelphi・C++Builderライブラリであり、このクラッシュは同ライブラリのワークシートライターに遡って追跡された。トラブルの最初の兆候はサポートチケットだった:夜間のエクスポートジョブが週に2回ほどクラッシュし、常に実行の途中で、Delphiの例外ダイアログもログに残ったエラーもなく、ただプロセスが消え、どこにも役立つ情報を指し示さないWindowsエラー報告のエントリだけが残った。それをデスクで再現することは全く別の問題だった。小さなワークブックは問題なく保存できた。大きなワークブックも、保存がすでにデバッガが接続されたメインスレッド上で実行される限りは問題なく保存できた。この不具合を実際に手元へ引き寄せるには、実際のマルチスレッドのエクスポート経路を通る本番サイズのファイルの実際のバッチが必要であり、その時点までにディスクI/O、メモリ圧迫、そして疑わしいテンプレートは、それぞれすでに除外されていた

ワークシートの保存はどうやって1つの巨大なCRC32呼び出しになるのか

XLSXファイルはZIPコンテナであり、ZIP形式はローカルファイルヘッダーと中央ディレクトリの両方に記録される、あらゆるエントリに対するCRC-32チェックサムを要求する。HotXLSは、ZLibCRC32という名前の小さなラッパーを呼び出すことでそのチェックサムを計算し、これがさらにzlib-ng自身のcrc32ルーチンを、SaveAsがワークシートのXMLをメモリ上に組み立て終えた後に呼び出す。そして長い間、この呼び出しは非圧縮バッファ全体を単一の呼び出しで運んでいた。これは小さなワークシートに対しては妥当な設計だ。HotXLSにおける大規模ワークブックのパフォーマンスに関するガイドで扱われている種類のシートである瞬間、それは非常に大きな1回の呼び出しになる。そこでは1枚のシートのXMLが圧縮される前に日常的に数百キロバイトを超えて走る

なぜzlib-ngはCRC32のために巨大なスタックバッファを必要とするのか

zlib-ngは、すべての呼び出しに対して1つのCRC-32実装を使うわけではない。あるサイズのしきい値より下では、意味のある追加メモリを一切必要としないテーブルルックアップと折り畳みのトリックでバッファを歩く。そしてそのしきい値より上——HotXLSがリンクしているビルドではおよそ119KB、正確には118,960バイト——では、Chorbaと呼ばれる特殊な高速アルゴリズムに切り替わる。その経路の汎用C実装はメモリを速度と引き換えにする:それはスクラッチ配列をヒープではなくスタック上に割り当て、呼び出し元のスレッドがたまたま持っているどんなスタック予算にも快適に収まるようにではなく、アルゴリズムの内部ループを速くするようにサイズ設定する。そのいずれも呼び出し元側からは見えない。チェックサム関数は通常リーフ呼び出しであり、いくつかのバイトを読んで数値を返すだけで、議論する価値のある割り当てはない。この前提は、Chorbaのしきい値を越えるほど大きなバッファがそこに歩み込むまでの、zlib-ngへの圧倒的多数の呼び出しに対して成り立つ

function BuildWorksheetPartCrc(const XmlBytes: TBytes): LongWord;
begin
  // One call over the whole worksheet XML buffer: fine for a small
  // sheet, but a large enough input pushes zlib-ng onto its Chorba
  // fast path and that path's stack-hungry scratch buffer
  Result := ZLibCRC32(0, XmlBytes[0], Length(XmlBytes));
end;

なぜワーカースレッドはそれを目撃し、対話的デバッグは決して目撃しなかったのか

このクラッシュを引き起こすには2つの条件が同時に必要である:zlib-ngのChorbaしきい値を越えるほど大きなワークシートXMLパーツと、より余裕のある何かではなく通常の既定のスタックしか持たないスレッドである。本番のエクスポートジョブは両方に該当した。それらはHotXLSの書き込みをワーカースレッドのプールに分散させるサーバーサイドのバッチジョブとして実行され、それぞれが呼び出し元がより多くを要求しない限りWindowsが確保する既定の1MBスタックを持ち、それぞれが重要になるほど大きな顧客のワークブックを処理していた。デスクでのデバッグはどちらの条件にも確実には該当しなかった:サンプルファイルは通常しきい値より小さく、ステップ実行はメインスレッド上で行われがちで、新しく生成されたワーカーの内部ではなかった。そのため本番で揃わなければならなかったこの2つの条件は、開発者のデスクではほとんど揃わなかった

間違った関数を責めたクラッシュを追いかける

チームが手に入れられたクラッシュレポートは、HotXLSのコードのどこでもなく、zlib-ngのdeflate関数内部の場所を指しており、CRC-32のコードを明確に指してもいなかった。その一つの詳細が調査の最初のパスを圧縮経路の方へ向かわせた:deflateに渡されるバッファサイズ、ウィンドウビット、圧縮レベル、ネイティブコーデックから出るクラッシュの通常の容疑者すべてである。そのどれも成立しなかった

誤解を招くトップフレーム

スタックオーバーフローは、記号化するには奇妙な種類のクラッシュである。なぜなら、それが報告される頃には、スタックポインタはそれのために確保されていた領域をすでに走り過ぎているからだ。そのクラッシュレポートを生成した何かは、フォールトしたアドレスを、それでも見つけられる最も近いシンボルに解決した可能性が高く、本当の犯人の隣にたまたま位置していた最も近いエクスポート済みエントリポイントがdeflateだった。実際のフォールトはCRC-32経路の内部のChorbaスクラッチバッファ割り当ての中にあり、同じライブラリにコンパイルされ、バイナリの中で実際に実行されていた関数と誤認されるほど近くにあった

デバッガの代わりにタイムスタンプで二分探索する

プロセス全体を巻き込むクラッシュは、通常のDelphiデバッガセッションが捕まえられるものを何も残さない。そのためチームは、あらゆる容疑の呼び出しの周りに配置したGetTickCountのチェックポイントと、保存経路にまたがる手作業の二分探索に頼り、プロセスが死んだ瞬間にどの操作が実行中だったかを絞り込んだ。それと並行して、既知の良好なベースラインビルドが、その回の変更自体における回帰をこれ以上上流を見る前に除外するために特別に、現行のビルドと並べて同じ本番ファイルを実行した。両方のチェックがきれいに戻ってきて初めて、調査は完全に有効な入力に対して予期しないことをしているサードパーティの依存関係へと落ち着いた

なぜtry/exceptはスタックオーバーフローを捕まえられないのか

スタックオーバーフローは、Delphiのコードが意図的に発生させる例外ではなく、Windowsがアクセス違反やゼロ除算を配信する方法でも配信されない。それはハードウェアのガードページフォールトとして表面化し、Delphiのtry/exceptが構築されているのと同じ構造化例外処理の仕組みを通じて報告されるが、それが発火するまさにその瞬間には、通常ハンドラを実行したり、クリーンアップコードを巻き戻したり、あるいはフォールトのきれいな報告を完了させたりするためのスタック空間が残っていない。既定の1MBの確保分しか持たないワーカースレッド上で、そのサイズのスクラッチバッファがすでに残っていたもののほとんどを消費してしまうと、ランタイムが作業するための何も残らない

procedure TExportWorker.Execute;
var
  Workbook: TXLSXWorkbook;
begin
  Workbook := TXLSXWorkbook.Create;
  try
    try
      BuildWorksheet(Workbook);
      Workbook.SaveAs(FTargetFile);  // crashes the process here on a
                                      // large enough sheet: try/except
                                      // never gets a chance to run
    except
      on E: Exception do
        LogError('Export failed: ' + E.Message);
    end;
  finally
    Workbook.Free;
  end;
end;

そのexceptブロックは安全網のように見え、ほとんどの失敗に対してはそうであるが、ここでは何も機能しない。チームは実践でそれを確認した:try/exceptは何も捕まえず、finallyブロックも確実に実行される機会を一度も得られず、オペレーターは、アプリケーションレベルのログエントリが一切ない死んだプロセスを見た。まさに最初のサポートチケットが説明していた通りである

その修正:1回の巨大な呼び出しの代わりにCRC32を64KBのスライスで供給する

HotXLSが出荷した修正は、zlib-ng自体については何も変更せず、ワークブックの書き込みに使われる圧縮レベルについても何も変更しない。ZLibCRC32は今や入力を固定の64KBスライス(それぞれ65536バイト)で歩き、スライスごとに一度zlib-ngのcrc32を呼び、実行中のチェックサム値を1回の呼び出しから次の呼び出しへとつなぐ。CRC-32は構造上インクリメンタルなアルゴリズムであるため、複数のスライスにわたって積み上げられたチェックサムは、同じバイト列に対して単一の呼び出しで計算されたものとビット単位で同一である:この修正は何が計算されるかではなく、作業がどう分割されるかを変えるだけである

function ZLibCRC32(crc: LongWord; const buffer; count: Longint): LongWord;
const
  // 64 KB keeps every call comfortably under the Chorba threshold
  CrcChunkSize = 65536;
var
  Cursor: PByte;
  ThisChunk: Longint;
begin
  Result := crc;
  Cursor := PByte(@buffer);
  while count > 0 do
  begin
    ThisChunk := count;
    if ThisChunk > CrcChunkSize then
      ThisChunk := CrcChunkSize;
    Result := zng_crc32(Result, Cursor, Cardinal(ThisChunk));
    Inc(Cursor, ThisChunk);
    Dec(count, ThisChunk);
  end;
end;

これが機能するために周囲のSaveAs呼び出しについて何も変える必要はなく、HotXLSが書き込むZIPエントリについても何も変わらない:ローカルファイルヘッダーと中央ディレクトリに最終的に入るCRC-32の値は、単一の巨大な呼び出しが生成していたであろう値と正確に同じであり、単により小さな断片から組み立てられているだけである。zlib-ngをダウングレードするか、より遅くメモリ割り当ての少ないCRC-32実装にフォールバックすることでもこのクラッシュは回避できたはずだが、そもそもしきい値に近づいたことすらないすべてのファイルにとって実質的なコストを伴う。だからこそどちらも出荷されなかった

自分のワーカースレッドからzlib-ngを呼ぶ場合これが意味すること

ここで説明したスタックオーバーフローの失敗モードは、スプレッドシートに特有の何かとは一切関係がない。圧縮であれ展開であれチェックサムであれ、プラットフォームの既定スタックしか持たないスレッドからzlib-ngに大きなバッファを渡すあらゆるアプリケーションは、同じ種類の壁にぶつかりうる。なぜならこのライブラリは入力サイズによってアルゴリズムを選び、それらのアルゴリズムのいくつかは余裕のあるスタックが存在することを前提としているからだ。zlib-ng自体に触れることなく機能する2つの防御策がある:サイズに敏感なルーチンへ大きなバッファを固定チャンクで供給することは、自然にインクリメンタルなあらゆるアルゴリズムに対してこの引き金となる条件を完全に取り除き、チャンク化が選択肢にない場合は、呼び出し元のスレッドにプラットフォームの既定より大きいスタックを与えることがもう一つのレバーである。どちらも、間違った関数を責める本番のクラッシュレポートから文書化されていないサイズのしきい値について知るよりは安上がりである

このしきい値は、十分に大きな本番のワークブックが間違った種類のスレッド上でそれを越えるまで見えないままだった。これはまさに、コードが小さなフィクスチャではなく実際のファイルに対して実行されて初めて現れる類の失敗である。このチャンク化されたCRC-32経路は、DelphiおよびC++Builder向けHotXLS Excelコンポーネントの標準書き込みパイプラインの一部として今や出荷されており、呼び出し元が設定すべきものは何もなく、それをオン・オフするプロパティも存在しない