io_uringのためのロックフリーMPSC FIFOキュー

Jonathan Corbet · 2026年7月15日 io_uringを使用するプロセスは、多くのボールを空中に保つ傾向があります。一度に多くの操作を実行できることは、そもそもそのAPIのポイントの一部です。その結果、io_uringサブシステムは、適切なタイミングで実行される必要がある多くのタスクを追跡する必要があります。 現在のカーネルでは、io_uringはこれらの作業項目を追跡するために標準的なカーネルの連結リストプリミティブを使用しています。しかし、7.2カーネルリリース以降、io_uringは代わりに新しいロックフリー・マルチプロデューサー・シングルコンシューマー（MPSC）キューを使用するようになり、顕著なパフォーマンス向上が期待されます。 ロックフリーアルゴリズムはトリッキーなことが多いですが、ここで使用されているものは比較的アプローチしやすく、これらのアルゴリズムがどのように機能するかを示しています。 古い方法の欠点 7.2より前のio_uringのタスクキューは、カーネルのロックフリー単方向連結リスト（llist）APIに基づいています。このタイプのコアは単純な構造です。 ```c struct llist_node { struct llist_node *next; }; ``` この構造体は、関心のある実際のデータを含む別の構造体に埋め込まれると、それらの外部構造体をリストに結合するリンクを含みます。 このリストタイプは、パフォーマンスのために設計されているにもかかわらず、io_uringには理想的ではない理由がいくつかあります。 llistは単方向連結リストであるため、現実的には先頭からしかアクセスできません。プロデューサーがアイテムを追加し、コンシューマーがアイテムを削除するリストの場合、llistは基本的にスタックになります。io_uringの作業項目は、少なくとも基本的な公平性の目的のために、受信した順序で処理される必要があります。そのため、各処理実行の前にタスクキューを反転させるパスが必要です。 さらに悪いことに、io_uringはリストが長すぎる場合にリスト全体を処理しないことを選択する場合がありますが、反転された順序の残りのアイテムは、単にタスクリストに戻すことができません。そのため、反転されたが未処理のアイテム用の別のリストを維持する必要があります。 最後に、llistにアイテムを追加するには、単一の先頭ポインタにアクセスする必要があります。これはロックを取得せずに実行できますが、リトライループが必要です。競合が多いリストでは、それらのリトライ（および関連するキャッシュラインのバウンス）がパフォーマンスを低下させる可能性があります。 これらの問題を解決するには、io_uringサブシステムが必要とするものに適したデータ構造が必要です。ロックなしで、最小限の競合で、リストに作業項目を追加する複数のプロデューサーを処理できる必要があります。各リストには単一のコンシューマーがいます。そのコンシューマーは、可能な限りプロデューサーとのキャッシュ競合を避けるべきです。そして明らかに、処理前にリストを並べ替える必要があってはなりません。 ロックフリーMPSCキュー 解決策は、Jens Axboeが投稿し、Dmitry Vyukovに帰属するアルゴリズムを使用したロックフリーMPSCキューです。 このキューはまだリストのエントリを連結するためにstruct llist_nodeを使用しますが、リストの先頭は次のようになります。 ```c struct mpscq { struct llist_node *tail; struct llist_node stub; }; ``` 「先頭」という言葉は、実際にはここにはリストの先頭へのポインタがないため、少し誤解を招きます。後で説明します。 このリストのビューは、リストの末尾にアイテムを追加する必要があるプロデューサーの使用を意図しています。 stubエントリは、リストにエントリが1つしかない場合にのみ存在するセンチネルです。つまり、リストが空の場合です。 リストが初期化されると、tailポインタはstubエントリを指すように設定されます。stubエントリのnextポインタはNULLに設定されます。 リストの末尾にノードを追加するには、この短い関数を呼び出します。 ```c static inline bool mpscq_push(struct mpscq *q, struct llist_node *node) { struct llist_node *prev; node->next = NULL; prev = xchg(&q->tail, node); WRITE_ONCE(prev->next, node); return prev == &q->stub; } ``` 新しいエントリのnextポインタはNULLに設定され、リストの末尾であることを示します。次に、xchg()呼び出しは、リストのtailポインタに新しいエントリへのポインタをアトミックに格納し、その前の値を返します。空のリストの場合、それはstubエントリへのポインタになります。 前のリスト末尾エントリ（stubであった可能性のある）のnextポインタは、新しいエントリに設定され、そのエントリをリストに追加するタスクが完了します。 ここで注目すべきロックフリーアルゴリズムの微妙な点があります。tailポインタが新しいリストエントリを指すようになると、そのエントリは他のプロセスから見えるようになります。他のことの中でも、その可視性は、新しいエントリのnextポインタが変更される前に正しく設定されている必要があることを意味します。 通常、コンパイラまたはCPUは、nextとtailへの代入を再注文する権利があると主張する可能性がありますが、xchg()操作は完全なバリアとして定義されています。これは、それらの代入（nextへの代入など）よりも前に発生する操作は、交換が行われる前にシステム全体に表示される必要があることを意味します。 バリア操作がない場合、それらの2つの代入の間に手動でバリアを挿入する必要があったでしょう。 複数のCPUが同時に同じリストにエントリを追加しようとすると、xchg()呼び出しがそれらをシリアル化し、tailポインタが順序正しく更新されることを保証します。 2つのCPUが同時にxchg()呼び出しを実行した場合、一方が「勝ち」、最初に行き、次にもう一方が続きます。 これにより、一時的にリストが次のようになります。 ``` CPU1: tail -> NodeA CPU2: tail -> NodeB ``` 各xchg()呼び出しはtailポインタの前の状態を返すため、各追加はリスト内の前のエントリの場所を知っています。これにより、それに応じてnextポインタを設定できます。 2つの追加が完了すると、リストは次のようになります。 ``` NodeA -> NodeB ^ tail ``` リストを整合性の取れた状態に保つためにロックは必要なく、リトライループも不要なため、追加操作は高速です。追加は、任意のカーネルコンテキスト内で実行中に実行できます。 コンシューマーのビュー コンシューマー側は少し手間がかかります。コンシューマーは、リストの先頭へのポインタをmpscq構造体とは別に維持します。これは、リストの最初のエントリのアドレスを保持する単純なstruct llist_nodeポインタです。 この分離の目的は、先頭と末尾のポインタが別々のキャッシュラインに配置され、プロデューサーとコンシューマー間のキャッシュ競合を回避することです。 リストの最初のエントリを削除するには、コンシューマーはその先頭ポインタを次のように渡します。 ```c static inline struct llist_node *mpscq_pop(struct mpscq *q, struct llist_node **headp); ``` この関数が準備する必要があるいくつかのケースがあります。 リストが最初に作成されたとき、空の状態（上記参照）では、リストの先頭ポインタにはstubエントリのアドレスが含まれます。追加は先頭ポインタを変更しないため、リストから最初のアイテムが削除されるまでその状況は続きます。 リストからまだアイテムが削除されていないと想像してください。分離された先頭ポインタを使用すると、状況は次のようになります。 ``` headp -> stub ``` その場合のアイテム削除は次のように処理されます。 ```c struct llist_node *head = *headp, *next; if (head == &q->stub) { head = READ_ONCE(head->next); if (!head) return NULL; q->stub.next = NULL; *headp = head; } ``` 最初のエントリの追加がstubのnextポインタをその最初のエントリに設定したことを思い出してください。ここでは、コードはそのポインタをチェックします。 それがNULLであればリストは空なので、NULLが返されます。そうでなければ、headはstubのnextフィールドの値に進められ、その後NULLに設定されます。 stubは、リストが再び空になるまで、リストの管理においてそれ以上の役割を果たしません。 リストにエントリがあることが確立されたら、次のチェックはそれが最後のアイテムかどうかを確認することです。 否定的な場合、つまりさらにエントリが存在する場合、headポインタはそれらのエントリの次のものに進められ、headエントリへのポインタが返されます。 ```c next = READ_ONCE(head->next); if (next) { *headp = next; return head; } ``` この方法でアイテムが返された後、状況は次のようになります。 ``` headp -> NodeA -> NodeB ``` ただし、nextポインタがNULLの場合、リストにはこれ以上エントリがなく、