イントルーシブ・リンクト・リスト

この記事では、イントルーシブ・リンクト・リストとは何か、そしてそれがLinuxでプロセスを管理するためにどのように使用されるかを学びます。 イントルーシブ・リンクト・リストとは何か？ イントルーシブ・リンクト・リストは、リンクがリンクされる構造体自体に埋め込まれるリンクト・リストのバリエーションです。 典型的なリンクト・リストの実装では、リストノードはリンクされるデータへのポインタと、リスト内の次のノードへのポインタを含みます。 図1: リンクト・リスト イントルーシブ・リンクト・リストの実装では、リストノードは次のリストノードへのポインタを含みますが、リスト自体がリンクされるオブジェクトに埋め込まれているため、データポインタは含みません。 図2: イントルーシブ・リンクト・リスト イントルーシブ単方向リンクト・リストのリスト構造体は、別のリストノードへの単一のnextポインタを含みます。 typedef struct list { struct list *next; } list; このlist構造体は、リンクされる構造体に埋め込まれます。例えば、valメンバーを持つitem構造体があるとします。 typedef struct item { int val; list items; } item; 新しいアイテムi2をi1のリストに追加するには、i1のitems.nextポインタをi2のアドレスに設定します。 items:item* i1 = create_item(16); item* i2 = create_item(18); i1->items.next = &i2->items; リストノードを含むオブジェクトには、まずリストオブジェクトのアドレスを取得し（例: i1.items.nextの値）、次にリストメンバーのオフセットをリストオブジェクトのアドレスから減算することでアクセスできます。 オフセットとは、メンバーがそのコンテナオブジェクトの先頭からどのくらいの位置にあるか（バイト単位）です。 図3: 埋め込みリストを持つオブジェクトのアドレス メモリアドレス0x18にあるオブジェクトi2のリストオブジェクトを考えます。リストメンバーはitemデータ構造体の先頭から8バイトの位置にあります。したがって、i2オブジェクトの先頭アドレスは0x18 - 8 = 0x10です。 GCCでコンパイルされたCでは、ポインタ変数をvoidポインタ（GCCでコンパイルされた場合、サイズは1バイト）にキャストすることで、ポインタからバイトを減算できます。これにより、数値がnum * sizeof(structure)にスケーリングされることなく、ポインタ値からバイトを減算できます。 item* _i2 = (void *)(i1->items.next) - 8; 注: voidポインタに対するポインタ演算はCでは不正ですが、GCCではサポートされています。LinuxはGCCを使用してコンパイルされるため、voidポインタに対するポインタ演算を実行できます。 絶対値の減算は移植性がありません。なぜなら、CPUアーキテクチャによってデータ型のサイズが異なる可能性があるからです。より良い方法はoffsetofマクロを使用することです。offsetofは、コンテナ構造体からのメンバーのオフセット（バイト単位）を返します。 item* _s2 = (void *)(i1->items.next) - (offsetof(item, items)); 要約すると: リストノードはコンテナオブジェクトに埋め込まれます。 リストノードは、リンクされるオブジェクトに埋め込まれた別のリストノードを指します。 リンクされるオブジェクトのベースアドレスは、リストメンバーのオフセットをリンクリストオブジェクトのメモリアドレスから減算することによって計算されます。 これらすべてのポインタ演算の後、あなたはなぜ常識のある人が通常のリンクト・リストよりもイントルーシブ・リンクト・リストを使用するのか疑問に思っているかもしれません。 なぜイントルーシブ・リンクト・リストを使用するのか？ イントルーシブ・リストを非イントルーシブ・リンクト・リストよりも使用する主な理由は2つあります。 メモリ割り当ての削減。 キャッシュスラッシングの低減。 非イントルーシブ・リンクト・リストでは、新しいオブジェクトを作成してリストに追加するには、2つのメモリ割り当てが必要です。1つはオブジェクト用、もう1つはリストノード用です。イントルーシブ・リンクト・リストでは、リストノードがオブジェクトに埋め込まれているため、オブジェクトを1つだけ割り当てる必要があります。これは、メモリ割り当てが失敗するケースが半分になるため、処理すべきエラーが少なくなることを意味します。 イントルーシブ・リンクト・リストは、キャッシュスラッシングの影響も受けにくいです。非イントルーシブ・リストノードを反復処理するには、リストノードの逆参照、次にリストデータの逆参照が必要です。イントルーシブ・リンクト・リストでは、次のリストノードの逆参照のみが必要です。 Linuxでリンクト・リストを使用してプロセスがどのように管理されるかを見る前に、双方向リストと循環リストを理解する必要があります。 双方向リストと循環リスト 双方向リストと循環リストは、単方向リストのバリエーションです。Linuxは循環双方向リストを使用するため、このセクションでは両方のバリエーションをカバーします。 双方向リストは、次のノードと前のノードの両方へのポインタを保持するリンクト・リストです。 図4: 双方向リスト リスト構造体は、追加のprevポインタを含みます。 typedef struct dlist { struct dlist *next; struct dlist *prev; } dlist; 双方向リストは、単一のノードへの参照があれば削除や挿入を実行できるため、それらをより簡単にします。 リンクト・リストのもう1つのバリエーションは循環リストです。循環リストは、null値を指さないリンクト・リストです。代わりに、最後のノードが最初のノードを指します。循環双方向リストでは、最初のノードも最後のノードを指します。 図5: 循環双方向リスト 循環リストを使用すると、特定のリストヘッドへの参照を保持せずに、任意のノードからリスト全体を簡単に反復処理できます。 void list_print_each(list* node) { list* start = node; do { printf("%d,", node->val); node = node->next; } while (node != start); } Linuxで最も人気のあるリンクト・リストは循環双方向リストです。 Linuxにおけるリンクト・リスト Linuxはリンクト・リストを広範囲に使用しています。空きメモリのスラブの追跡から、実行中の各プロセスの反復処理まで、あらゆる種類のタスクに使用されています。struct list_head構造体の検索は、Linux 5.2で10,000件以上の結果を返します。 Linuxでは、リストノードはトラバースされるよりも追加および削除されることがはるかに多いです。通常のLinux使用時の分析によると、トラバースは全リンクト・リスト操作のわずか6%でした。そのうち、28%のトラバースは空のリストで発生したか、または1つのノードのみを訪問しました（Rusty Russelのリンクト・リスト分析を参照）。 Rustyの分析が示唆するように、Linuxは主に、トラバースがまれであるか、またはリストサイズが小さい場合にオブジェクトのリストを保持するためにリンクト・リストを使用しています。 Linuxにはいくつかの異なるリスト構造が含まれています。最も人気があるのは、イントルーシブな循環双方向リンクト・リストです。 イントルーシブ・リンクト・リストの実装 Linuxの循環双方向リンクト・リストは、include/linux/list.hで定義されています。 リスト構造体はlist_headと呼ばれます。nextとprevポインタを含みます。 struct list_head { struct list_head *next, *prev; }; オブジェクトのリンクト・リストを作成するには、list_headをリストにされる構造体のメンバーとして埋め込みます。 struct atmel_sha_drv { struct list_head head; // .. }; 新しいリストは、静的または動的に初期化できます。 静的に初期化されたリストは、LIST_HEAD_INITマクロを使用できます。 static struct atmel_sha_drv atmel_sha = { .dev_list = LIST_HEAD_INIT(atmel_sha.dev_list), // .. }; LIST_HEAD_INITは、リストノードのnextとprevポインタを自身を指すように設定するために展開されます。 #define LIST_HEAD_INIT(name) { &(name), &(name) } リストを動的に初期化するには、INIT_LIST_HEADマクロを使用できます。多くの場合、別のlist_headがヘッドノードとして保持されます。 static struct list_head hole_cache; INIT_LIST_HEAD(&hole_cache); INIT_LIST_HEADは、リストノードへのポインタとともに呼び出されます。ここでも、リストのnextとprevポインタは自身を指すように設定されます。 static inline void INIT_LIST_HEAD(struct list_head *list) { WRITE_ONCE(list->next, list); list->prev = list; } 注: WRITE_ONCEマクロは、値を代入する際に不要なコンパイラの最適化を防ぎます。 リストが初期化された後、list_addを使用して新しいアイテムを追加できます。 struct hole { // .. struct list_head list; }; static struct hole initholes[64]; // .. for(i = 0; i < 64; i++) list_add(&(initholes[i].list), &hole_cache); list_addはヘッドノードポインタと挿入されるノードへのポインタを受け取ります。次に、ヘッドノードとhead->nextの間に新しいノードを挿入するために__list_addを呼び出します。 static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } __list_addは、新しいリストノードを追加するためにポインタを再割り当てします。 static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { // .. next->prev = new; new->nex