フレームポインタの復活

 (brendangregg.com)
3 ポイント 投稿者 GN⁺ 2024-03-18 | 1件のコメント | WhatsAppで共有
  • Fedora と Ubuntu 24.04 LTS が libc などの OS コンポーネントを、デフォルトで フレームポインタ付きビルドに戻したことで、Linux のプロファイリングと Flame Graph がより完全なスタックを見られるようになった
  • フレームポインタがないと、profiler が libc のようなライブラリ層で スタックウォーキングを停止したり、誤ったフレームをたどったりして、CPU・Off-CPU Flame Graph が壊れることがある
  • 2004年の gcc の i386 変更は、レジスタを1つ多く確保するための選択だったが、x86-64 にまで広がり、システム profiler と eBPF ベースの可観測性に長期的なコストを残した
  • Netflix の Java と libc への適用経験では、コストは通常 1%未満で、一部の報告では 1〜2%、特殊なマイクロベンチマークや異常なワークロードでは 10% まで見られた
  • LBR、DWARF、eBPF スタックウォーカー、ORC、SFrames、Shadow Stacks などの代替策はあるが、いま本番環境で性能改善を見つける最も実用的な方法は、フレームポインタをデフォルトで有効にすること

Flame Graph が壊れる理由

  • CPU Flame Graph は一見正常に見えても、libc がフレームポインタなしでコンパイルされたシステムでは、一部のサンプルが [unknown] の上に誤って集まることがある
    • 例では左側の 15% のサンプルが誤った位置にあり、アプリケーションフレームが欠落している
    • profiler がカーネルフレームを通過して syscall と libc syscall wrapper まで到達した後、次のフレームのシンボル解決に失敗する
  • 原因は、コンパイラ最適化によって フレームポインタレジスタがスタックフレームの基準点ではなく、データ保存に使われるため
    • profiler はその値が単なる数値なのか判断できず、関数アドレスとして解釈しようとする
    • 値が次のフレームを指していなければ、スタックウォーキングは停止する
    • 偶然有効なポインタのように見えると、誤った junk frame が生じることがある
    • 値が自分自身を指している場合、perf の最大フレーム制限に達するまで junk frame の塔ができることがある
  • Off-CPU Flame Graph では libc の read/write や mutex 関数が多く登場し得るため、フレームポインタがないとより大きく壊れる
  • アプリケーション自体もフレームポインタなしでビルドされている場合、ライブラリだけでなくスタックトレース全体が不安定になる

フレームポインタが提供する情報

  • x86-64 ABI は %rbp をスタックフレームの base pointer、つまりフレームポインタとして使えると定義している
  • Linux perf や eBPF などの外部 profiler・debugger はこの情報を利用して スタックトレースをたどり、結果を Flame Graph として可視化する
  • x86-64 ABI には %rbp の使用が任意であるという脚注がある
    • %rsp でスタックフレームをインデックスすれば、prologue と epilogue で2つの命令を減らせる
    • %rbp を追加の汎用レジスタとして使える

2004年の削除と20年の余波

  • 2004年、gcc は i386 backend でデフォルトで -fomit-frame-pointer -ffixed-ebp に相当する動作をするよう変更された
  • i386 は汎用レジスタが4つしかないため、%ebp を解放すると使えるレジスタが大きく増える
    • 変更理由には、Intel の icc コンパイラより高い性能を出したいという点も含まれていた
    • 当時は debugger が別のスタックウォーキング手法をサポートしているため壊れない、という判断もあった
  • この変更は x86-64 にも適用された
    • x86-64 はレジスタが12個以上あるため、レジスタを1つ多く得る利点は i386 ほど大きくない
    • eBPF のような現在のシステム profiler は当時存在せず、この変更によって壊れる場合がある
  • Eric Schrock は 2004年に、amd64 で17番目の汎用レジスタを得る利点は、デバッグ可能性の損失に比べて十分ではないと見ていた
    • /usr/bin をフレームポインタなしでコンパイルし始めれば制御不能になる、という評価を残した
    • Linux では /usr/bin だけでなく /usr/lib やアプリケーションコードにまで同じ流れが広がった

Java、libc、Netflix での適用経験

  • Netflix に参加した 2014年には、Java のフレームポインタ対応不足により、アプリケーションスタックがすべて壊れていた
  • JVM c2 compiler 向けの修正が作られ、Oracle がそれを再作業して JDK8u60 の -XX:+PreserveFramePointer オプションとして追加した
  • Java の変更により、アプリケーションコードで複数の性能改善を見つけられたが、libc は依然として一部の CPU サンプルと大半の Off-CPU Flame Graph を壊していた
  • その後、自前でフレームポインタを含む libc を本番用にコンパイルし、Canonical とともに Ubuntu 向けの事前ビルド libc の作業も進めた
    • しばらくは libc6-prof の使用が推奨された
    • libc6-prof はフレームポインタを含む libc6 だった

性能オーバーヘッドと例外事例

  • 本番適用の過程で、フレームポインタを libc と Java に追加したコストは通常 1%未満だった
  • 例外的に 10% のオーバーヘッドが出たアプリケーションがあった
    • Groovy を通じて 1000 フレームを超えるスタックトレースを生成していた特殊なアプリケーションだった
    • Linux perf もこれを処理できず、Red Hat の Arnaldo Carvalho de Melo が Netflix のワークロードのために kernel.perf_event_max_stack sysctl を追加した
    • その環境は低レベルのハードウェア profiling 機能がない仮想マシンだったため、10% がすべてフレームポインタによるものかは確認できなかった
  • 他の報告では、およそ 1% または 2% 程度のコストも見られる
  • マイクロベンチマークでは 10% まで悪化することがある
    • 小さな関数をループで繰り返し実行すると、追加命令が L1 cache warmth や cache line 境界に影響することがある
    • この場合、フレームポインタ自体というより、hot 関数に何かを追加すれば同じ効果が出る可能性がある
  • Python scimark_sparse_mat_mult ベンチマークも 10% に達することがあった
    • Andrii Nakryiko の分析では、大きな関数で gcc が %rsp offset ではなく %rbp relative offset を使い、より多くのバイトが必要になって性能問題が生じた特殊事例だった
    • その後、Python がフレームポインタをデフォルトで再有効化できるよう修正されたという話もあった
  • フレームポインタによって見つかった性能改善は 5% から 500% まであり、通常 1% 未満のコストは正当化できると見ている
  • profiling や debugging ができない機器ならフレームポインタなしでコンパイルしてもよいが、主な対象はエンタープライズ Linux とバックエンドサーバーである

Fedora と Ubuntu のデフォルト有効化

  • Meta、Google、Netflix のような大企業は、すでに自前でフレームポインタを含む libc を使い、profiling 機能を確保していた
  • Fedora にデフォルト有効化を upstream しようとした最初の試みは、長い論争につながった
    • Fedora の議論は 116 件の投稿があるスレッドになった
    • ある参加者は、Meta や Netflix がテスト・ベンチマーク・コードサイズ測定のための side repository インフラを提供すべきだと要求した
    • Jonathan Corbet はこれを Fedora's tempest in a stack frame で整理した
  • Fedora はその後、提案を再検討して受け入れ、フレームポインタを再有効化した最初のディストリビューションになった
  • Ubuntu も Ubuntu 24.04 LTSで frame pointers by default を発表した
  • Arch Linux もフレームポインタ有効化を進めているという情報が追加された
  • OS ライブラリのスタックウォーキングはこの変更で改善されるが、アプリケーションランタイムには別途設定が必要な場合がある
    • Java は -XX:+PreserveFramePointer オプションを提供している
    • Go は数年前にフレームポインタ対応がデフォルトになった

フレームポインタ後のスタックウォーキング候補

  • LBR(Last Branch Record): Intel のハードウェア機能で、16 または 32 フレームの制限があり、大半のアプリケーションスタックには不足するが、一部のスタック情報を得る最後の手段として使える
  • BTS(Branch Trace Store): Intel の機能で、スタック深度の制限は比較的少ないが、メモリ load/store と BTS buffer overflow interrupt の処理コストがある
  • AET(Architectural Event Trace): JTAG ベースの tracer で、低レベル CPU、BIOS、device event を追跡でき、stack trace にも使えるように見えるが、直接使った経験はない
  • DWARF: debugger で長く使われてきた binary debuginfo 方式
    • JIT ランタイムでの JIT-to-DWARF 作業があったという指摘があった
    • 忙しい本番サーバーで c2 が常時動く Java JVM には実用的だとは期待していない
    • DWARF スタックウォーキング自体のコストも高い
  • eBPF stack walking: 外部 tracer がランタイムの支援なしに JVM のようなランタイム内部をたどれる
    • ランタイム内部を user space read で大量に読む必要があり、オーバーヘッドが高くなる可能性がある
    • ランタイムの変更に弱いため、language code base とともに配布・保守されるのが適切
  • ORC(oops rewind capability): Linux kernel の軽量 stack unwinder で、新しい kernel がフレームポインタを削除しながらも stack walking を維持できるようにする
  • SFrames(Stack Frames): ORC ベースの軽量なユーザースタック unwinding 方式
  • Shadow Stacks: Intel と AMD のセキュリティ機能で、関数の return address を別のハードウェアスタックに push して return 時に検証でき、stack trace にも活用できそうである

いま直ちに変わること

  • 2004年にフレームポインタ省略の理由だった i386 の性能上の利点、当時の debugger 互換性の判断、icc との競争は、2024年の状況には合わない
  • x86-64 に適用されたフレームポインタ削除は、当時からデバッグ可能性の損失に比べて利点が十分ではないという評価があった
  • Fedora と Ubuntu がフレームポインタを戻したことで、2024年リリースを使う人は CPU Flame Graph をより理解しやすくなり、Off-CPU Flame Graph を初めて適切に活用できるようになる
  • continuous profiler も、顧客に OS 変更を求めずに、より完全なプロファイルを得やすくなる
  • 将来は SFrames や Shadow Stacks のような方式で、再びフレームポインタなしにスタックトレースできるようになるかもしれないが、いま可能な改善はフレームポインタをデフォルトで有効にすることである

関連記事

1件のコメント

 
GN⁺ 2024-03-18
Hacker News のコメント

  • 2000年代初頭に スタックフレームポインタの省略が広まり始めた頃を覚えている
    当時、貧しい第三世界の国の大学でコンピュータサイエンスを学んでいて、古くて遅いコンピュータのせいで、課題の大半はインタプリタよりコンパイラを使っていた
    低レベルのデータ構造、コンパイラ、アセンブリの数値ルーチン、Minix のデバイスドライバまで実装する面白い授業が多く、プログラムが変な動きをすると gdb でアタッチして、アセンブリレベルで直接 スタックをたどりながら デバッグしていた
    ところが突然 -fomit-frame-pointer が流行し、スタックトレースが意味をなさなくなり始め、セグフォルトや illegal instruction のデバッグがずっと難しくなった
    結局、壊れたデバッグセッションを避けるため、ほとんどすべてに Python を使うようになり、性能は1〜2桁失ったが、Python を学んだことはその後役に立った

    • -fno-omit-frame-pointer を知らなかったのか気になる

  • Fedora が言及されていてうれしい。ディストリビューション全体で フレームポインタを有効にしたまま維持するのは、かなり消耗する戦いだった
    例: https://pagure.io/fesco/issue/3084
    フレームポインタのオーバーヘッドが大きいという神話が根強いが、これはある Python の事例で +10% 遅くなったことに由来しており、今では修正されている
    実際に測定されたオーバーヘッドは 1% 未満で、特定のアプリケーションで得られた利点のほうがはるかに大きい

    • 「実測オーバーヘッドが 1% 未満」というのは誇張に見える。オーバーヘッドは測定する ワークロードに大きく依存するため、普遍的には適用しにくい
      Linux カーネル側の測定ともあまり合わず、そちらでは 5〜10% の範囲だと見た: https://lore.kernel.org/lkml/20170602104048.jkkzssljsompjdwy...
      netperf、ページアロケータのマイクロベンチマーク、pgbench、sqlite などさまざまなワークロードでフレームポインタを有効にすると 5〜10% のオーバーヘッドが出ており、PostgreSQL と SQLite で影響を見たという点が重要
      DBMS はシステムに強い負荷をかける良い方法の一つ
    • OCaml 5 で フレームグラフをきちんと使うには、フレームポインタを使うか、深さに制限があり CPU によっては使えないこともある LBR を使うか、OCaml の2つのスタックを扱えるよう perf/eBPF 側を大きく変える必要がある
      OCaml 5 は OCaml コードと C コードに別々のスタックを使い、GDB は DWARF 情報で両者をつなげられるが、perf の DWARF コールグラフではできない: https://github.com/ocaml/ocaml/issues/12563#issuecomment-193...
      今後のリリースでもフレームポインタを維持すべき根拠が必要なら、OCaml 5 を例に挙げられる
      Fedora 39 で既にデフォルトでフレームポインタが有効になっていることは今知った。普段のプロファイリングは、まだ perf record --call-graph dwarf -F 47 -a を使う CentOS 7 っぽいシステムで主に行っていた
    • 32ビットではフレームポインタはいまだに厄介で、現在の IoT のような領域には合わない
      フレームポインタを取り除いた理由は神話ではなく、64ビット以前の時代の現実から来ており、そこまで大昔の話でもない
      今でも古い 64ビットシステムに新しい命を吹き込むなら、こうした最適化には意味がある
      理想的には、セキュリティが重要なシステムでもデフォルトであるべきで、すべてが「可観測性」のために最適化される必要はない
    • 「1% 未満」のオーバーヘッドが積み重なって、コンピュータの使用感は30年前より測定可能なほど遅くなったと思う。そういう小さなオーバーヘッドは結局累積する

  • Apple が ARM でうまくやった点が一つあり、それは x29 フレームポインタが常に有効なフレームレコードを指すようにしたこと
    leaf 関数や tail call のような一部の関数はリストにエントリを作らないことがあるが、その結果、デバッグ情報がなくてもスタックトレースは常に意味のあるものとして残る
    https://developer.apple.com/documentation/xcode/writing-arm6...

    • Apple プラットフォームには別種の解釈可能性の問題がよくある。Objective-C / Swift アプリは深くネストしたブロックやクロージャが多く、バックトレースが複数のスレッドに散らばることがよくあり、まだ良い解決策を知らない

  • 2005年に Google で反対側の立場にいて、当時の考えは単純だった
    $BIG_COMPANY がすべてをフレームポインタ付きでコンパイルすることにしても、残りのコミュニティはそうしないだろうから、はるかに大きなコミュニティと勝ち目のない議論を続けることになると見ていた
    結果としてその議論はほぼ 20年越しの議論になり、その後 gperftools で libunwind が動くようにするパッチを書いて、数年間 libunwind を保守することになった
    今は別のコンピューティング分野に移って受動的な観察者になったが、反対側の視点から歴史を読むのは興味深い

    • フレームポインタを追加すると、どういう形で足を引っ張られるのか気になる。機能面でどんな問題が起きるのか分からない

  • RBP をフレームポインタとして渡すつもりなら、いっそスタックを 2 つ持つことも可能
    片方は RBP が指してアクティベーションフレームを保存し、もう片方は RSP が指して戻りアドレスだけを保存する、という形
    そうすればコールスタックは文字どおり戻りアドレスの平坦な配列なので、「スタックを歩く」必要もなくなる
    そもそも戻りアドレスをローカル変数の近くに保存する理由が分からないし、欠点が多すぎるように見える

    • ストレージ管理が単純になるため。スタックフレームは常にキャッシュにある単純な bump pointer で、オーバーフローには guard page が 1 つあればよい
      提案された方式では guard page が 2 つ必要になり、スタック操作も 2 倍になり、キャッシュミスの可能性も 2 倍になる
    • 記事で少し触れられていた CPU 機能であるシャドウスタックは、これとかなり似ている。ただし主な目的はセキュリティ側
    • スタックがなぜ「間違った方向」に伸びて、誤動作するプログラムがセキュリティ問題を引き起こすのかも疑問
      理由は分かるが、多くのものと同じく 30 年ほど前に最後に意味を持っていた程度で、その影響は興味深かった
    • Forth を好きになる準備ができているように見える ;-)
      不思議なことに Wikipedia の記事は、Forth がパラメータスタックとリターンスタックの両方にアクセスできる点を、モデルの大きな特徴としてあまり打ち出していないようだ
      https://en.wikipedia.org/wiki/Forth_(programming_language)
    • 戻りアドレスを別の場所に保存する利点は、ハードウェアがシャドウスタックのようなものをサポートしない限り明確ではない
      別ページへ移してポインタを 2 つ管理するコストが、すでに必要な場所にだけ保護を提供するスタッククッキー/プロテクタより実質的に安いことを示す必要がある
      現在のスタックプロテクタより実質的なセキュリティ上の利点もない。任意読み書きが可能なら、最終的には制御フロー完全性の迂回につながり得る

  • Virgil はフレームポインタを使わない。動的スタック割り当てがなければ、特定の関数のフレームサイズは固定であり、単純な二分探索テーブル参照で見つけられる
    Virgil の手法はページインデックスベースの範囲を追加で使い、平均すると数回の比較だけで検索を絞り込み、アンワインド情報と GC 用 stackmap を結合し、容量もごく少なく済む
    主要なコードは https://github.com/titzer/virgil/blob/master/rt/native/Nativ... にあり、同じディレクトリの残りのコードはメタデータのデコードを実装している
    フレームサイズが動的な場合、つまりスタック上にデータを割り当てる場合にだけ、フレームポインタに意味があると思う
    静的メカニズムで十分なのに動的メカニズムを使うのは奇妙で、主にメタデータエンコーディング ABI やアンワインドルーチンについて合意がないためにそうなっているようだ
    1〜2% という測定値は信頼でき、配列境界チェックのコストと同程度
    デバッグとプロファイリングには 1% のコストを特別扱いする一方で、セキュリティ層の追加には拒否感を示すのは、優先順位が非常におかしい

    • C にも境界チェックを追加できるが、1〜2% よりはるかに大きなコストがかかる
      C++ の std::vector はデフォルトで境界チェックをオフにしているが、それは C++ が完全に狂った人たちによって、またそういう人たちのために設計されたからだと思う
      それ以外では、境界チェックのない言語はすぐには思い浮かばない

  • 良い記事。フレームポインタがなくなった時は残念だった
    他のシステムはもちろん Linux でも、多くの人がフレームポインタ不在のために長い間苦しみ、可能な限り多くの環境で維持しようとしてきた
    メインストリームの Linux がそれを戻すのを見るのは、認められたように感じる一方で、少しもどかしくもある

    • 純粋に疑問。DWARF でスタックをアンワインドするのが面倒なのは分かるが、システム全体のコードを遅くするほど悪い理由が分からない
      Debian 系で遅いのは、ライセンス上の理由で perf に遅いアンワインド経路だけをパッケージしているためだが、ツールがまともなら違いはほとんど感じない
      何を見落としているのか気になる

  • 全体としてフレームポインタには賛成だが、この領域で数年働いて感じたことがある
    フレームポインタベースのスタック巻き戻しの多くは、DWARF の巻き戻し情報にはない問題を考慮していない。フレームの設定はアトミックではなく、push $rbp と mov $rsp $rbp という 2 つの命令で構成されており、スナップショットが push の最中に撮られると親フレームを取り逃す可能性がある
    コードを検査すれば緩和できるかもしれないが、スタックフレームとは無関係な push %rbp もあり得るため、ヒューリスティックに近いように見える
    Brendan が言及した BPF ベースの高速なカーネル内巻き戻し手法も開発した: https://web.archive.org/web/20231222054207/https://www.polar...
    この方式は DWARF CFI をそのまま使わず、BPF で使えるランダムアクセス形式に変換する
    現在はフレームポインタのある JIT セクションだけをサポートしているが、JVM インタプリタの巻き戻しをネイティブの巻き戻しとかみ合わせて実装することは可能だと思う
    理想的にはフレームポインタの有効化はケースバイケースで行われるべきで、ベンチマークが鍵になる
    業界やソフトウェアの性質によって、性能、可観測性、ビジネス指標の間のトレードオフは大きく変わり得る
    Fedora 側はここで非常に優れた厳密な仕事をした
    また、依存ライブラリまで含めてシステム全体でこの設定を変えられるビルドシステムは、テストだけでなく本番適用にも非常に有用だ
    最後に、Indu が取り組んでいる SFrame に期待している。ユーザーにフレームポインタを使うかどうか選ばせつつ、現在の問題の多くを解決してくれそうだが、インフラが整い全員がアップグレードするまでには数年かかるかもしれない

    • 良いフレームグラフを得るには、Linux ディストリビューション全体でフレームポインタを有効にする必要がある
      実際に何が起きているかを理解するには システム全体の分析 が必要であり、Fedora や Debian のような現在のバイナリ Linux ディストリビューションの構造では、他の選択肢は事実上不可能だ
    • 1 つの命令でも可能だ: ENTER N,0 はローカル変数用に N だけスタック領域を予約し、おおむね PUSH EBP, MOV ESP,ESP, SUB SP,N と同じだ
      ただし ENTER が x86-64 にあるかは覚えていない
      それでも CALL とフレーム設定の間ではアトミックではないため、CALL の後、ENTER の前にスナップショットが撮られるとフレーム設定を取得できない
      ENTER があまり使われない理由は、遅すぎると判断されたからだ
      LEAVE は置き換える命令列と同じくらい速いか、それ以上に速いため使われるが、ENTER は第 2 オペランドが性能を台無しにする
      そのオペランドはネストした関数が上位のスタックフレームにアクセスするためのもので、使用コストが非常に大きい
    • 非アトミックなフレーム設定は CPU プロファイラには確かに問題だが、アロケーションプロファイリング、Off-CPU プロファイリング、割り込みベースではない他のプロファイリングでは問題にならない
    • JVM の巻き戻し方面でも良い進展がある

  • プロファイルに見えていた [unknown] の山がなぜ生じるのか、ようやく分かって興味深い
    ただし正当化するのは簡単ではない。2% の性能差 は実際にはかなり大きい差だ
    フレームポインタを含めるかどうかを、もっと細かく制御できるとよい
    精密なプロファイリングがあれば、特定の関数やコンパイル単位にフレームポインタが必要かどうかを判断できるはずだ
    フレームポインタを含めることで劇的に遅くなる処理は少数で、残りはほとんど影響を受けないという結果が出ても驚かない

    • 2% の性能差はそれほど大きくない。特にプロファイリングでボトルネックを見つけ、10% 以上の改善を得られるならなおさらだ
    • GCC では関数宣言に属性を付けることで、関数ごとにオン・オフできる。ただし LLVM では動作しない
      __attribute__((optimize("no-omit-frame-pointer")))
      __attribute__((optimize("omit-frame-pointer")))
    • 実際のアプリケーションでは、性能コストは 2% よりはるかに小さいことがある
      こうしたベンチマークはやや人工的なので完全に信じるべきではなく、現実のアプリケーションでは結果が大きく異なることが多い
      プロファイリングは重要で、コードを注意深くプロファイルして複数の区間を最大 20% 速くしたことがある
      性能低下に非常に敏感なアプリケーションなら、ラボではフレームポインタを有効にしてプロファイリングし、顧客に配布するバージョンでは省略すればよい
    • 測定されたオーバーヘッドは 1% を少し下回る。過去にはフレームポインタのために性能が大きく悪化したまれな事例があったが、現在は修正されている
    • 通常は 2% よりはるかに小さい

  • JIT コードのサポートは残念ながら良くないが、LLVM には生成された各メソッドとアドレスを記録する優れたフックがある
    そのため単純な 混合モードのスタック巻き戻し は比較的簡単に作れるが、主にプロセス内部で可能だ
    Intel の DNN 系は perf が読める共有ファイルに情報をダンプしているようだが、oneDNN のカーネル自体が RBP を使い回し続けるため、実質的に役に立たない
    記事の「Java JVM のような JIT ランタイムには DWARF 情報がない」という主張にも驚いた
    デフォルトで無効になっているのか、それとも文字どおり利用できないのか気になる
    検索してみると、たいてい JVM スタックに JNI/C 側を含めたいという話につながる: https://github.com/async-profiler/async-profiler/issues/215