Linux カーネルのソースコードを読んだのでメモを公開します．Linuxカーネルを読む際の参考になれば幸いです.
リストの操作: ノードの初期化
ノードの初期化は INIT_LIST_HEAD()を使います．
struct list_head head; INIT_LIST_HEAD(&head);
INIT_LIST_HEAD() で初期化されると，ノードのポインタ，head.prev と head.next の値は次のようになります．
+-----------------------+
| prev prev |
+--- +---------+ <-----+
| head |
+---> +---------+ ---> +
| next |
+-----------------------+INIT_LIST_HEAD()は include/linux/list.h の26行目で次のように実装されています．
26: static inline void INIT_LIST_HEAD(struct list_head *list) { WRITE_ONCE(list->next, list); list->prev = list; }
WRITE_ONCEはマクロで，WRITE_ONCE(A,B) で変数Aに，値Bをアトミックに代入するインラインアセンブラに展開されます．
アトミック処理を無視すると，INIT_LIST_HEADは下のコードと等価になります．
static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; // 実際には，この代入はアトミック処理 list->prev = list; }
ここで少し話が脱線しますが，重要な点があります．それは，
- なぜアトミック処理が必要になるのか？
- なぜWRITE_ONCE()はnext ポインタのみで，prevポインタは使用されていないのか？
の2点です．
まず1つ目，アトミック処理が必要な理由は「struct list_head が複数のCPUから同時にアクセスされる場合があるから」です．
たとえば list のアドレスが 0x11223344 だったとします．
この場合
list->next = list
というCのコードは，次のようにコンパイルされる場合があります(アセンブラをC言語風に記述します．)
レジスタ0 = list->nextのアドレス レジスタ1 = 0x1122; レジスタ2 = 0x3344; *(レジスタ0) = レジスタ1; *(レジスタ0+1) = レジスタ2;
このようにC言語では一行の処理でも，実際にはアドレス上位とアドレス下位の2つの転送命令にコンパイルされる場合があります．
上記の例だと，list->next のポインタ変数は，4行目と5行目の2命令で更新されます．
このように2命令で nextのポインタ変数を書き換えてしまうと，その書き換え中，つまり4行目が実行されて，5行目が実行される前の期間は，nextポインタのアドレスが無効な値になります．無効な値になるのは一瞬ですが，その瞬間にハードウェア割り込みやプリエンプション（ソフトウェア割り込み）で別の処理が割り込んだ場合，その割り込み処理は 無効なnextアドレスを参照してしまいます．結果カーネルがクラッシュします．
そこでLinuxカーネルは， struct list_head の操作に対して以下のルールを儲けてアトミック性を保証するようになっています．
- nextのアクセスはアトミック処理に実装．具体的には WRITE_ONCE()，READ_ONCE()を使う
- アトミック処理が必要な場面では next のみを使用し， prev は用いない
前述の2つ目の疑問，WRITE_ONCE()がnextのみで prevには使用されていない理由もこれで説明できます．つまり，このルールに従って INIT_LIST_HEAD()が実装されているから，ということになります．
リストの操作: list_empty()
list_empty()は，リストが空である場合 true を返す関数です．
実装は list.hの235行目です
static inline int list_empty(const struct list_head *head) { return READ_ONCE(head->next) == head; }
前述のようにnextポインタへのアクセスはアトミックであるべきなので，この関数はREAD_ONCEマクロを使用して実装されています．意味的には以下の処理をアトミックに行います．
static inline int list_empty(const struct list_head *head) { return head->next == head; }
リストの操作: list_add()
ノードをリストに追加する関数です list.h の69行目で実装されています．
69: /** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */ static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); }
実体は __list_addです
50: /* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { if (!__list_add_valid(new, prev, next)) return; next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new); }
ここで WRITE_ONCE()の使い方に注意すると
- 新しく追加するノード new は，まだリストに登録されていないので他のCPUはアクセスできない WRITE_ONCE()は不要
- 既存のノード prev->next は，他のCPUがアクセスする可能性があるので WRITE_ONCE()を使用
となっています．つまりこの list_add()は排他制御なしで安全に利用できます．
まとめ
- list.h を読みました
- リストは Doubly circular linked list を実装していました．
- ノードは struct list_head; ポインタとして prev と next を持っています
- リストは出来るだけロックフリーで使えるように工夫されています．
- リストへのアクセスはアトミックになるように気をつけましょう．
- API
- データ構造 struct list_head;
- 構造体へのアクセスはマクロ container_of() を使う
- 初期化
- INIT_LIST_HEAD()
- 追加
- list_add()
- 走査
- list_for_each()
- list_for_each_entry()
- 他にもたくさんマクロや関数が定義されています．詳しいことは include/linux/list.h を直接読みましょう．
- データ構造 struct list_head;
