ハクソク

世界を動かす技術を、日本語で。

futexがなければ、無駄である

279日前原文(h4x0r.org)

概要

  • The Art of Multiprocessor Programming 第2版の書評と実用性への疑問
  • futex （Fast Userspace Mutex）の重要性と従来のSystem Vロックとの違い
  • futexの 仕組み・API設計 ・各OSでの実装例
  • mutex /スピンロックの基礎・futexを使った実装例
  • 書籍に不足する 実践的な内容 の補完

The Art of Multiprocessor Programming 第2版 書評とfutexの重要性

  • Phil Eaton's book club で扱う書籍は業界評価が高く、2021年にアップデートされた最新版
  • 著者も有名で、 並行プログラミング経験者 としても学びが多いと期待していた
  • しかし、 futex に一切触れていない点に強い疑問
  • futexは単なるmutexではなく、 現代の高性能な並行処理の基盤 となるプリミティブ
  • System V時代の セマフォ中心のロック機構 はスケーラビリティに難あり
  • Linuxが futex を導入（2002年）、以降Windows（2012年）、macOS（2016年）なども追随
  • 現代のpthread等のシステムライブラリは futexベース の実装が主流

futexの基本と従来ロックとの違い

  • futex は「fast user-space mutex」の略だが、mutexそのものではなく 並行プリミティブのビルディングブロック
  • 従来（System V IPC）のロックは セマフォ でロックと待機が一体化していた
  • futexは ロック操作と待機/起床操作を分離 し、柔軟性とパフォーマンス向上を実現
  • 無駄なシステムコール回避 が容易になり、ユーザー空間で完結できる操作が増加
  • 例えば、 unlock時に待機スレッドがなければカーネル呼び出し不要 （System Vでは必須）

futexのAPIと動作概要

  • futex_wait() ：指定した状態（値）でなければ即失敗、合致すればカーネル内の待機リストにスレッドを登録しブロック
  • futex_wake() ：指定したメモリアドレスの待機リストからスレッドを起こす。基本は1または全スレッドを起床
  • WindowsのAPI名「 WaitOnAddress」は本質をよく表現
  • 待機対象は32bit整数（もしくは64bit）。値の意味はOSは関知しない
  • 待機時に 現在値を明示 することで、既に状態変化があった場合に無駄な待機を防止

futexの実装例（Linux/macOS）

  • atomicな32bit整数型 をfutexとして利用
  • Linux ではglibcにラッパーがないため、syscallで直接呼び出し
    • futex_wait_timespec：状態一致時に待機、タイムアウトも指定可能
    • futex_wake：1スレッドまたは全スレッドを起床
  • macOS では__ulock_wait2/__ulock_wakeを利用（新APIもあり）
    • ほぼ同様の機能を提供

mutex/スピンロックの基礎とfutex実装例

  • 書籍は「mutual exclusion」の概念やスピンロックに多く紙面を割く

  • スピンロック は以下のようにatomic操作で簡単に実装可能

    #include <stdatomic.h>
#include <stdint.h>
typedef _Atomic uint32_t h4x0r_spin_lock_t;
static inline void h4x0r_spin_lock_init(h4x0r_spin_lock_t *lock) {
  atomic_store(lock, 0);
}
static inline void h4x0r_spin_lock_acquire(h4x0r_spin_lock_t *lock) {
  while (atomic_fetch_or(lock, 1)) ;
}
static inline void h4x0r_spin_lock_release(h4x0r_spin_lock_t *lock) {
  atomic_store(lock, 0);
}

  • futexベースのmutex を自作することで、無駄なCPU消費やシステムコールを減らせる

書籍に欠けている実践的内容

  • futex のような現代的プリミティブの解説不足
  • 実装例やAPIの使い方 に踏み込んだ説明がほぼ皆無
  • 基礎理論と現実世界のギャップ を埋める知識の重要性
  • 理論だけでなく、 OS・ハードウェア・コンパイラの最適化や落とし穴 にも注意が必要

まとめ

  • The Art of Multiprocessor Programming は理論面で優れているが、 現代的な並行プログラミングの実践 には不十分
  • futex のような重要プリミティブの理解と活用が不可欠
  • 実装例を通じた学習 が、より現実的な並行処理設計の力につながる

Hackerたちの意見

futexの一番クールなところは、ハンドルがないってことだよね。syscallを使ってメモリの割り当てや解放をする必要がなくて、カーネルベースのメモリウォッチャーがあって、これがすごく便利なプリミティブになってる。待機者がいなくなると、すべてがきれいに片付くし、カーネルは競合がないミューテックスすら見ない。だけど、カーネルがこれをパフォーマンスよく管理する方法について、技術的に深掘りしてみたいな。追記：futex2についても今日学んだよ！ https://docs.kernel.org/userspace-api/futex2.html

└

その通り！同時に、スレッドがロックでブロックされるたびにカーネルの内部malloc()を呼び出したくないよね。そのために、多くのOSはスレッドが作成されるときに「キューオブジェクト」を割り当てて、スレッドオブジェクトからそれにポインタをつけるんだ。スレッドが競合するロックに遭遇したとき、そのキューオブジェクトをそのロックに「寄付」することになる。つまり、1人以上の待機者がいるロックには「キューオブジェクト」のリンクリストがついてることになる。スレッドが起こされると、それぞれがそのオブジェクトを持って出て行く。でも、自分のキューオブジェクトが戻ってくる保証はないし、シャッフルされるかもしれない！だから、スレッドが終了する頃には、そのオブジェクトの1つを解放するけど、それが自分が作ったものとは限らない。最初にこの方法を使ったOSはSolarisだったと思う。そこで彼らはこれを「ターンスタイル」と呼んでた。BSDも同じアプローチを採用して、同じ名前を使ってる。 https://www.oreilly.com/library/view/solaristm-internals-cor... https://www.bsdcan.org/2012/schedule/attachments/195_locking...

└

元々のUnixのカーネル内待機キューもそんな感じだったよ。

はっきりさせておこう。あの本はマルチプロセッサプログラミングを理解するためのもので、いろんなサブドメインに応用できるスキルを育てることを目的にしてる。多くのところで、自分で構造を実装するのは避けて、ライブラリや言語、システムが提供する構造を使うべきだって言ってる。特にミューテックスについてはそう言及されてる。あの本は明らかに並行性についてのもので、特定のプラットフォーム向けじゃない。この記事の著者は、futexについてのまあまあ興味深い記事を書くために、ストローマンを作り上げてると思う。個人的には、このアプローチはちょっと不快だな。誇張された対立の視点からのプレゼンは疲れるし、混乱を招く可能性が高い。この記事は「TAoMPが教えてくれないこと」という視点から書かれてもよかったのに、もっと協力的に受け取られたはずだ。もちろん、このブログは新しいもので、この記事はPhilが投稿したし、Philは以前に他の記事を宣伝してたことも知ってる。

└

この記事を書いたのは僕だよ。読んでた本に触発されて書いたんだけど、僕の見積もりでは、あの本は学者にも実務者にもあまり向いてない。今のアカデミアの大部分に共通する問題だと思うし、業界からも、もっと準備が整った状態で大学を出てほしいという声があるし、マスターの学生からも、自分がなりたいスキルを学べてないって話を聞く。だから、これは「おい、futexについて学ぼう！」っていうストローマンを作るつもりではなかった（他の不満があることからも明らかだよ）。実際、僕はその本にかなり失望したから、別の投稿を保留にしたくらい。Philとは数年前に一緒に仕事をしたことがあって、彼は僕の書いたものを読んでる。僕はただ書き始めたわけじゃないし、過去にオーディエンスを見つけるのに問題はなかったよ、Philがどうこう関係なく。

└

そうそう、前のsysvスタイルを恐竜って呼ばないのは、かつては強かったって意味になるから、まるで巨人の肩に乗ってその頭にうんこしてるみたいだよね。ちょっとした謙虚さが必要なんだよ。

記事にもある通り、WindowsはWindows 8でfutexに似たものを導入したんだよね。元々のWin32クリティカルセクションはカーネルレベルのセマフォに基づいてるって知ってるけど、Vistaで導入されたSRWロックはどうなんだろう？

└

CRITICAL_SECTIONもSRWLockも、競合がないときはカーネルに入らないんだよね。（SRWLockはキー付きイベントに基づいてるし、CRITICAL_SECTIONは最近カーネルオブジェクトを必要に応じて作成するけど、失敗したらキー付きイベントに戻るんだ。）

実際、一般的な実装の間での[再帰ロックの]動作は全く一貫性がない。これが未定義のままにされているのには良い理由がある – それはちょっと難しいから。正直言って、ほとんどの標準が持っているこういう立場は非常にイライラする。「まあ、OSや言語の実装者が機能Xを信頼性高く実装できるとは期待できないから、アプリケーションプログラマーに任せよう；彼らは、結局、素晴らしいスキルセットを持っているし、簡単に回避できるだろう」とか。「まあ、実際に標準を実装する人たちに機能Xを強制することはできない（彼らはこの委員会のメンバーだから）、でも下流のユーザーにその機能がないことに対処させるのも簡単じゃないから、正直言って、あの人たちに何ができるっていうの？ベンダーを切り替えるの？」

└

過剰に仕様を決めると、より良い実装の扉を閉ざしてしまう。例えば、C++の標準ハッシュテーブルや正規表現は、サードパーティ製のものよりも1桁遅いのはそのため。標準は「std::unordered_mapをチェーンバケットと追加のメモリ割り当てを持つハッシュテーブルとして実装しなければならない」とは言わなかったけど、いくつかの保証を指定していて、それがオープンアドレッシングのハッシュテーブルを実装するのを非常に難しくしてる。指定する制約は、より良い実装を排除する可能性がある。再帰的rwlockには、実装方法がたくさんある。エラーチェックを少なくする高性能な実装を排除したいの？

└

この現象についてもっと知りたいなら、こちらを見てね: https://en.wikipedia.org/wiki/Worse_is_better 嫌いだけど、事実だよね。

└

その一部は、再帰ロックを使うべきじゃないってことだと思うから、サポートを指定する意味があるのかな？私の意見だけど。

WindowsはWaitForMultipleObjectsを導入して、Linux 5.16（2021年末）が新しいFutex2でそれを真似たんだ。 https://www.phoronix.com/news/Linux-5.16-sys_futex_waitv それ以来、futex2には良い改善が続いてるよ。NUMAサポート（やっと実現！）、 https://www.phoronix.com/news/FUTEX2-NUMA-Small-Futex https://www.phoronix.com/news/FUTEX2-Improvements-Linux-6.16 （最近のNUMAに関する素晴らしい投稿も見てみて、パフォーマンスにとって絶対に重要な内容だよ、 https://news.ycombinator.com/item?id=44936575） 6.7でのIo_uringサポート（2024年）、（PostgreSQLのaioを高速化する素敵な記事もあるよ）、 https://www.phoronix.com/news/IO_uring-FUTEX-Linux-6.7 6.7での小さな再キューとシングルウェイトの追加、 https://www.phoronix.com/news/Linux-6.7-Locking-FUTEX2

└

FutexはWFMOとは関係ないよ。Futexはキー付きイベントと同等なんだ。WFMOのLinux版はselect/poll/epollだね。

└

futexのためのio_uringサポートは本当に素晴らしい。これを使ってRubyのファイバー用にミューテックスとキューを実装したよ： https://github.com/digital-fabric/uringmachine/blob/main/ext...

└

WindowsはWaitForMultipleObjectsを新たに得たわけじゃなくて、最初のWindows NTからあったんだよ、もう30年以上前からね。WaitForMultipleObjectsはWindows NTがUNIXに対して持ってた利点だったけど、新しいものではなかった。IBM PL/Iには1965年に同等の機能がすでにあったし、Windows NTの30年近く前だよ。IBM PL/Iの「wait」関数は実際にはUNIXの「wait」のモデルだったけど、UNIXの関数はすごく単純化されてて、モデルよりもずっと弱かったんだ。UNIXがMulticsから受け継いだ多くの機能も同じだった。残念ながら、UNIXの子孫たちがその先祖たちと同じくらい洗練された機能を持つようになるまで、数十年もかかってしまった。でも、MicrosoftのWaitForSingleObjectとWaitForMultipleObjectsは効率的な実装がなかったから、Linuxのfutexに相当するWaitOnAddressを追加しなきゃいけなかったんだ。ただ、Linuxのfutexには32ビットのfutex値しか使えないとか、単一のイベントにしか待てないっていう面倒な制限があったのは事実だね。futex値に対して原子ビット操作を使えば、実際には複数のイベントに待つこともできるけど、最も効率的な方法ではないんだ。だから、futex値の32ビットサイズが厄介になるんだよ。だから、「futex」の利点をWaitForMultipleObjectsのいくつかの利点と組み合わせようとする試みは大歓迎だね。でも、これはWindowsを真似るわけじゃなくて、Microsoft社よりもずっと古い技術を再実装してるだけなんだ。半世紀以上前から知られていたことだよ。

└

でも、まだfutex_swapはないね。[0] https://lore.kernel.org/all/414e292195d720c780fab2781c749df3... [1] https://blog.linuxplumbersconf.org/2013/ocw/system/presentat...

『The Art of Multiprocessor Programming』の代わりにおすすめの本って何かある？

└

これらの二つ: https://man7.org/tlpi/ https://marabos.nl/atomics/

└

マルチプロセッサプログラミングの技術。再入可能ロックや他のことについても触れてるよ。このレビューが言ってることとは違ってね。でも、もっと面白いのは後半で、ロックの実装を経た後に、ロックベースとロックフリーのデザインを使って実際に問題を解決し始めるところだよ。使ってる言語に合った本を続けて読むといいよ、例えばC++なら「C++ Concurrency in Action」とか（多くの内容は他の言語にも応用できる）。

多くの人はクラッシュしたスレッドについて心配しないだろうけど、スレッドがクラッシュするとプログラム全体が落ちることが多いからね。でも、クラッシュが生成するシグナルをキャッチして、全体のプロセスが終了するのを防ぐことができるよ。もしプロセス全体が何らかの理由で死んじゃったら、ロックをクリーンアップしたいのにそれは助けにならない。これに対する解決策は「ロバスト」ロックと呼ばれるものだよ。sys_set_robust_listを使ってカーネルに保持しているfutexのリストを登録できて、スレッドが死ぬとカーネルは各エントリに特定のビットを設定して、待機者がいるなら起こしてくれる。

└

sys_set_robust_listを使ってカーネルに保持しているfutexのリストを登録できて、スレッドが死ぬとカーネルは各エントリに特定のビットを設定して、待機者がいるなら起こしてくれる。こういうことに関して一番心配なのは、そのロックが何かを守っていて、今は不整合な状態になっていることなんだよね。特定のスレッドがどうやってクラッシュしたのかを十分に理解していないと、データが有効な状態や回復可能な状態にある保証はない。そうなると、アプリ全体をクラッシュさせる方が絶対にいいと思う。単一スレッドがクラッシュした後にクリーンアップや回復をする能力があるのは本当にすごいけど、私の直感的な予想では、95%のエンジニアはロバストロックをロバストなデータ構造と適切に使う方法を知らないし、4%はその種のソリューションを設計する時間がない（ドキュメントも含めて）、残りの1%は本当に高給取り（あるいはそうあるべき）で、そもそもクラッシュが起きないようにするためのより良い方法を見つけるだろうね。

└

確かに、私が見落としてたことについての良いコメントだね（ミューテックスの話はプロセスの境界で止めようとしたんだ、永遠に続かないように）。

└

プロセス間でフューテックスを使う場合（または他のプロセス間の状態を扱う場合）、一般的なアプローチは、各プロセスのためにSOCK_STREAMまたはSOCK_SEQPACKETのUnixドメインソケットを開いておくウォッチドッグプロセスを用意することだね。これで、プロセスがクラッシュしたときに確実に検出して、そのプロセス固有の状態をクリーンアップできるようになるよ。

2014年のLinux futex実装における特に厄介な脆弱性、Pinkie Pieによるものだよ。https://issues.chromium.org/issues/40079619 「requeue-onceルールは、futex_wait_requeue_piにuaddr2として渡されたfutexにのみ再キューイングを許可することで強制されるから、AからB、BからCに再キューイングすることはできないけど、BからBには再キューイングできる。これが起こると、if (!q.rt_waiter)が通過するから、rt_mutex_finish_proxy_lockは呼ばれない。（あと、私の知る限り、free_pi_stateは呼ばれないけど、これはこの変な再キューイングがなくても同じ。futex_requeueが直接requeue_pi_wake_futexを呼ぶ場合、pi_stateはスレッドが終了するまでexit_pi_state_listでクリーンアップされるまで放置される。これは脆弱性ではない。）futex_wait_requeue_piが終了すると、rt_waiterへのさまざまなポインタがダングリングポインタになる。」

アンソニー・ウィリアムズの『C++ Concurrency in Action』はどう？ フューテックスについては触れてないけど、メモリの順序やロックフリーのデータ構造に関する実際の詳細はカバーしてるよ。もしそれでも難しいなら、ポール・マッケニーの素晴らしい無料のモノグラフ「並列プログラミングは難しいのか？ もしそうなら、どうすればいいのか？」もおすすめ。ハードウェアに焦点を当てた視点が得られるし、フューテックスの詳細には触れてないけど、フューテックスベースのプリミティブを実装するための基本的な参考文献、ウルリッヒ・ドレッパーの「フューテックスはトリッキー」を紹介してくれるよ。TAOMPPは高レベルの並行性の概念を教えるにはいいと思うし、OSレベルの実装の詳細を議論するのは場違いだと思う。大事なのは、並行性について考える方法を教えてくれることで、自分で同期プリミティブを書く方法じゃないからね。例えば、ピーターソンやベーカリーのロックは現実世界では役に立たない（本にもそう書いてあるし）、でもその正しさの証明を理解することで、自分で書かなきゃいけない並行アルゴリズムについて考える助けになるよ。

マラ・ボスの『Rust Atomics and Locks』にはフューテックスに関するセクションがあるよ。[0] https://marabos.nl/atomics/os-primitives.html#linux