Linux カーネルのソースコードを読んだのでメモを公開します．Linuxカーネルを読む際の参考になれば幸いです.
今回のお題: include/linux/list.h
今回はカーネル内部で多用されているデータ構造の一つとして linked list の実装を読みました．主なファイルは linux/list.h になります．ソースコードのバージョンは linux-5.1.8です．
カーネル内部でよく利用されているデータ構造
よく利用されているデータ構造としては以下のものがあります．
- List
- Queue
- Map
- Binary tree
C++であればSTLの std::list
Singly linked list と Doubly circular linked list
今回読むソースコード include/linux/list.h はいわゆる doubly circular linked list を実装しています．
念の為 Singly linked list と Doubly circular linked list の違いを説明しておきます．
singly linked list
リスト構造には様々な種類があります．例えば singly linked list であれば，ノードを
struct Node { struct Node *next; };
のような形で定義します．そしてこのNode構造体を使ってリスト構造を構築します．アスキーアートで図示すると，例えばノード数３のリスト構造は次のようになります．リストの終端はNULLポインタで表現しています
+---------+ +---------+ +---------+
| Node | | Node | | Node |
+---------+ ---> +---------+ ---> +---------+ ---> NULL
next next
doubly circular linked list
一方，linux/list.hが実装している doubly circular linked list では，ノードを次のように定義します．
struct list_head { struct list_head *next; struct list_head *prev; };
実際の定義は include/linux/types.h の186行目にあります．
そしてリスト構造を次のように構築します．こちらもノード数３のリスト構造の例です．
+--------------------------------------------------------+
| prev prev prev |
+--- +---------+ <-- +---------+ <-- +---------+ <--+
|list_head| |list_head| |list_head|
+---> +---------+ ---> +---------+ ---> +---------+ --+
| next next next |
+--------------------------------------------------------+singly linked list と異なり doubly linked list には nextのポインタに加えて prevのポインタがあります．この2つのポインタを使って，各ノードは，次ノード，前ノード，双方にリンクを貼っています．
また circular linked list とあるように，リストの終端がありません．リストの末尾はリストの先頭に接続します．
struct list_head の利用例
// ノードの定義 struct Data { struct list_head list; int value; }; // ノードを新しく生成する関数 struct Data * new_data() { Data *ptr = kalloc( sizeof (struct Data), GFP_KERNEL ); INIT_LIST_HEAD(&ptr->list); return ptr; } // リストを作成する例 void myfunc { struct list_head head; INIT_LIST_HEAD(&head); struct Data* A = new_data(); struct Data* B = new_data(); list_add(&A->list, &head); list_add(&B->list, &head); }
myfunc() の中で生成したリスト構造をアスキーアートで表現すると次のようになります．
+--------------------------------------------------------+
| prev prev prev |
+--- +---------+ <-- +---------+ <-- +---------+ <--+
| head | | A->list | | B->list |
+---> +---------+ ---> +---------+ ---> +---------+ --+
| next next next |
+--------------------------------------------------------+
リストの操作： list_for_each()
circular linked list にはリストの末尾がありません．foreach()のような，リストの要素を順番に見る処理は次のように実装します．
struct list_head *pos; for (pos = &head->next; ptr != &head; ptr = ptr->next) { // 処理 }
linux カーネルは list_for_each() というマクロを定義しています．(list.hの489行目)
#define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)
このマクロを使うと上記のコードは
struct list_head *pos; list_for_each(pos, &head) { // 処理 }
という風にコーディングできます．
リストの操作: container_of()
list_for_each は list_head を順に走査するマクロです． list_head から strcut Data のポインタを得るには container_ofマクロを使います
struct list_head *pos; list_for_each(pos, &head) { struct Data * p = container_of(pos, struct Data, list); }
container_of マクロは linux/kernel.h の970行目で定義されているマクロです．
970: /** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \ !__same_type(*(ptr), void), \ "pointer type mismatch in container_of()"); \ ((type *)(__mptr - offsetof(type, member))); })
エラーチェックなどを削除すると，container_of の実装は次のように簡略化できます
#define container_of(ptr, type, member) ((type *)( (char *)(ptr) - offsetof(type,member) ))
要は
- offsetof()を使って構造体 type のメンバ変数 member のオフセットアドレスを計算
- ptr からオフセットを引いて，構造体typeの先頭アドレスを計算
- アドレスを type* 型にキャスト
しているだけです．
リストの操作：list_for_each_entry()
意味的には for_each_list と container_of を組み合わせたマクロです
#define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ &pos->member != (head); \ pos = list_next_entry(pos, member))
これをつかうと list_head 構造体を介さず，直接 struct Data のポインタでループを回せます．
struct Data *p; list_for_each_entry(p, &head, list) { // 処理 }
