list_headはlinux kernel内部でどのように使用されているのか？

まずは双方向リストについて解説する。 Linuxkernel内部ではlist_headというデータ構造が用意されており、これが様々な場面で使用される。 このデータ構造はnextとprevの二つのメンバを持ち、データ構造に前後の概念を導入したいときに使用される。

双方向リスト

list_headの定義

list_headは以下のように定義されている。

struct list_head {
    struct list_head *next, *prev;
};

list_headの作成

list_headの作成にはLIST_HEADマクロを使用する。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
   struct list_head name = LIST_HEAD_INIT(name)

from https://github.com/torvalds/linux/blob/dad9774deaf1cf8e8f7483310dfb2690310193d2/scripts/kconfig/list.h#LL29C1-L32C46

このマクロを使用する際にはLIST_HEAD(list_name)と宣言することで新しいlist_headを作成することができる

list_headの操作

list_headを操作するためにいくつかの関数が用意されている。

• list_add(n, p):　pが指す要素の直後に、nが指す要素を挿入する
• list_add_tail(n, p): pが指す要素の直前に、nが指す要素を挿入する
• list_del(p): pが指す要素を削除する
• list_for_each(p): リストの先頭(h)で指定したリストの各要素を操作する。

プロセスリスト

存在するすべてのプロセスディスクリプタをリンクするためにも、list_headは使われています。

struct task_struct {
    ...
    struct list_head       tasks;
    ...
}

from https://github.com/torvalds/linux/blob/dad9774deaf1cf8e8f7483310dfb2690310193d2/include/linux/sched.h#LL864C1-L866C26

それぞれのtask_struct構造体は上記の通り、list_headがたのtasksメンバを持ち、このtasksメンバのprevメンバがひとつ前のtask_struct要素を指し、nextメンバがひとつ後のtask_struct要素を指しています。

プロセスリストの先頭には常にtask_structがたのinit_taskが格納されており、init_taskはいわゆるプロセス0、つまりswapperのプロセスディスクリプタとなります。