io_uringのためのロックフリーMPSC FIFOキュー
Lockless MPSC FIFO queues for io_uring (lwn.net)
要約
Linuxカーネルのio_uringサブシステムは、タスクキューの管理に従来のロックフリー単方向連結リスト(llist)から、新しいロックフリー・マルチプロデューサー・シングルコンシューマー(MPSC)キューへと移行します。この変更は、io_uringが多数の同時操作を効率的に処理するために必要とされ、特に多数のプロデューサーと単一のコンシューマーを持つキューにおいて、パフォーマンスの向上と競合の低減をもたらします。
全文翻訳
io_uring 用ロックフリー MPSC FIFO キュー
io_uring を使用するプロセスは、多くのタスクを同時に進行させることが多く、APIの目的そのものが、一度に多数の操作を実行できるようにすることです。その結果、io_uringサブシステムは、適切なタイミングで実行されるべき多数のタスクを管理する必要があります。現在のカーネルでは、io_uringはこれらの作業項目を追跡するために標準的なカーネルの連結リスト(linked-list)プリミティブを使用しています。しかし、カーネル7.2リリース以降、io_uringは代わりに新しいロックフリーのマルチプロデューサー・シングルコンシューマー(MPSC)キューを使用するようになり、いくつかの顕著なパフォーマンス向上が見られます。ロックフリーアルゴリズムは一般的に複雑ですが、ここで使用されているものは比較的理解しやすく、これらのアルゴリズムがどのように機能するかを示しています。
従来の方式の短所
カーネル7.2より前のio_uringにおけるタスクキューは、カーネルのロックフリー単方向連結リスト(llist)APIに基づいています。このリストの核となるのは単純な構造体です。
struct llist_node {
struct llist_node *next;
};
この構造体が、実際の関心のあるデータを含む別の構造体に埋め込まれると、それらの外部構造体をリストに結合するリンクを含みます。
パフォーマンスのために設計されたこのリスト型であっても、io_uringにとって理想的でない理由はいくつかあります。llistは単方向連結リストであるため、現実的にはリストの先頭からしかアクセスできません。プロデューサーが項目を追加し、コンシューマーが項目を削除するリストの場合、llistは基本的にスタックとして機能します。io_uringの作業項目は、少なくとも基本的な公平性の目的のために、受信した順序で処理される必要があります。そのため、各処理実行の前にタスクキューを逆順にするパスが必要になります。さらに悪いことに、io_uringはリストが長すぎる場合にリスト全体を処理しないことを選択する可能性がありますが、逆順にされた残りの項目は、タスクリストにそのまま戻すことができません。そのため、逆順にされたがまだ処理されていない項目のための別のリストを維持する必要があります。最後に、llistに項目を追加するには、単一のヘッドポインタにアクセスする必要があります。これはロックを取得せずに実行できますが、リトライループが必要です。競合が多いリストの場合、それらのリトライ(および関連するキャッシュラインのバウンス)がパフォーマンスを低下させる可能性があります。
これらの問題を解決するには、io_uringサブシステムのニーズにより適したデータ構造が必要です。ロックなしで、最小限の競合で、リストに作業項目を追加する複数のプロデューサーを処理できる必要があります。各リストには単一のコンシューマーが存在し、そのコンシューマーは可能な限りプロデューサーとのキャッシュ競合を避けるべきです。そして明らかに、処理前にリストを並べ替える必要があってはなりません。
ロックフリーMPSCキュー
解決策は、ロックフリーMPSCキューであり、Jens Axboeによって投稿され、Dmitry Vyukovに帰属するアルゴリズムを使用しています。このキューは依然として struct llist_node を使用してリストのエントリを結合しますが、リストのヘッドは次のような構造になります。
struct mpscq {
struct llist_node *tail;
struct llist_node stub;
};
「ヘッド」という用語は、実際にはここにはリストのヘッドへのポインタがないため、少し誤解を招きます。後述します。このリストのビューは、リストの末尾に項目を追加する必要があるプロデューサーの使用を意図しています。stubエントリは、リストにエントリが1つだけ存在する場合、つまりリストが空の場合にのみ存在するセンチネルです。リストが初期化されると、tailポインタはstubエントリを指すように設定されます。
[画像: [空のキュー]]
stubエントリのnextポインタはNULLに設定されており、リストの終端であることを示します。リストの末尾へのノードの追加は、この短い関数呼び出しで行われます。
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ポインタが新しいエントリに設定され、そのエントリをリストに追加するタスクが完了します。
[画像: [1つのエントリを持つキュー]]
ここで注意すべきロックフリーアルゴリズムの微妙な点があります。tailポインタが新しいリストエントリを指すようになると、そのエントリは他のすべてのプロセスから可視になります。他のことの中でも、その可視性は、新しいエントリのnextポインタが変更される前に正しく設定されている必要があることを意味します。通常、コンパイラまたはCPUは、nextとtailへの代入の順序を変更する権利があると主張する可能性があります。これにより、新しいtailが新しいノードが完全に初期化される前に可視になる可能性があります。しかし、xchg()操作は完全なバリアとして定義されており、これは、その前に発生する操作(nextへの代入など)が、交換が行われる前にシステム全体に可視でなければならないことを意味します。バリア操作がない場合、それらの2つの代入の間に手動でバリアを挿入する必要があったでしょう。
複数のCPUが同時に同じリストにエントリを追加しようとすると、xchg()呼び出しがそれらをシリアライズし、tailポインタが順序正しく更新されることを保証します。2つのCPUが同時にxchg()呼び出しを実行した場合、一方が「勝ち」、もう一方がそれに続きます。これにより、一時的に次のようなリストが作成される可能性があります。
[画像: [競合中のキュー]]
各xchg()呼び出しはtailポインタの前の状態を返すため、各追加はリスト内の先行エントリがどこにあるかを知っています。これにより、それに応じてnextポインタを設定できます。2つの追加が完了すると、リストは次のようになります。
[画像: [競合後のキュー]]
リストを整合性の取れた状態に保つためにロックは必要なく、リトライループも不要なため、追加操作は高速です。追加は、任意のカーネルコンテキスト内で実行中に実行できます。
コンシューマーの視点
コンシューマー側は少しだけ複雑で、コンシューマーが mpscq 構造体とは別にリストのヘッドポインタを維持することから始まります。これは、リストの最初のエントリのアドレスを保持する単純な struct llist_node ポインタです。この分離の目的は、ヘッドとテールポインタが別々のキャッシュラインに配置され、プロデューサーとコンシューマー間のキャッシュ競合を回避することです。リストの最初のエントリを削除するには、コンシューマーはそのヘッドポインタを次のように渡します。
static inline struct llist_node *mpscq_pop(struct mpscq *q,
struct llist_node **headp);
この関数は、いくつかのケースに対応できるように準備する必要があります。リストが最初に作成され、空の状態(上記参照)にある場合、ヘッドポインタはstubエントリのアドレスを保持します。リストへの追加はヘッドポインタを変更しないため、リストから最初の項目が削除されるまでその状態は維持されます。リストからまだ何も削除されていない状況を想像してください。分離されたヘッドポインタを使用すると、状況は次のようになります。
[画像: [ヘッドポインタを持つキュー]]
この場合の項目削除は次のように処理されます。
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が返されます。そうでなければ、ヘッドはstubのnextフィールドの値に進められ、その後NULLに設定されます。
[画像: [stubが削除されたキュー]]
stubは、リストが再び空になるまで、リストの管理においてそれ以上の役割を果たしません。
リストにエントリが存在することが確立されたので、次のチェックはそれが最後のエントリであるかどうかを確認することです。否定的なケース、つまりさらにエントリが存在する場合、ヘッドポインタはそれらのエントリの次のものに進められ、ヘッドエントリへのポインタが返されます。
next = READ_ONCE(head->next);
if (next) {
*headp = next;
return head;
}
この方法で項目が返された後、状況は次のようになります。
[画像: [項目が1つ削除されたキュー]]
しかし、nextポインタがNULLの場合、リストにはこれ以上エントリがなく、tailポインタは再びstubに設定される必要があります。ただし、ひねりがあります。同時に新しいエントリをリストに追加しているプロデューサーが存在する可能性があります。そのため、リストを空の状態にリセットしようとする比較交換操作が必要です。
if (try_cmpxchg(&q->tail, &head, &q->stub)) {
*headp = &q->stub;
return head;
}
return NULL;
try_cmpxchg()呼び出しは、tailポインタとヘッドポインタ(リスト内の唯一のエントリを指していることを思い出してください)を比較します。両方が等しい場合、tailをstubを指すようにアトミックに設定し、リストを最初の状態にリセットします。その後、リストの最後の項目を返します。
しかし、try_cmpxchg()呼び出しが失敗した場合、コンシューマーは別のプロデューサーと競合しており、そのプロデューサーはコンシューマーの知らないうちにtailポインタを変更しています。この場合、NULLが返され、最後の項目はコンシューマーが次にリトライするまでリストに残ります。コンシューマーは、tailポインタがstubエントリを指しているかどうかを確認することで、リストが空の場合とこの場合を区別できます。
static inline bool mpscq_empty(struct mpscq *q)
{
return READ_ONCE(q->tail) == &q->stub;
}
これでAPI全体の説明が完了しました。コードはio_uring/mpscq.hで見つけることができます。現時点では、lib/の下に配置され、カーネルの他の部分で利用できるようにはなっていません。もちろん、io_uring以外の外部の関心のあるユーザーが現れた場合、それは変更される可能性があります。
7.2以降、この新しいキュータイプはio_uring内のいくつかの異なるタスクリストに使用されています。このパッチで説明されている結果は、オーバーヘッドの削減を伴うパフォーマンスの大幅な向上です。より多くの作業がより迅速に実行され、同時にカーネル内で実行される時間が削減されます。io_uringコードは、リストを逆順にする必要や、タスクリストから削除されたがまだ処理されていない作業項目の別のリストを維持する必要がなくなったため、いくらか簡略化されています。全体として、これは時が来た最適化であると思われます。
(追記: このトピックは取り上げられないリスクがありましたが、LWNの公開トピックページで十分な投票を得たため、購読者(プロジェクトリーダーレベル以上)向けに、もう一度調べることにしました。この記事に値すると考えてくれたLWNの読者に感謝します。)
この記事のインデックスエントリ