Linuxカーネル内のリスト型データ構造とその操作

# list in linux kernel
## カーネルに於けるリスト型データ構造
LinuxカーネルはCで書かれており、C言語には標準でリストが無い。
どうやってリストを作るかは実装した本人次第だ。
Linuxカーネルのような大規模なコードでは、リストの標準化を行っている。
その実装はCの特異な言語仕様を駆使したものであり、Cをある程度理解していないとかなり難しい。
## 実装
***リストにしたいデータ構造(構造体)に特殊なデータ構造をメンバとして持たせる事で、リストを実装している。***

```c
struct student_entry {
    char    *name;
    int     num;
    struct list_head head;
};
```

以降、このデータ構造をサンプルとする。

## `list_head`
`list_head`自体は至極シンプルなデータ構造で、前後の要素のポインタを持つだけだ。

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

つまり、リストとして繋がっているのはあくまで`list_head`同士である。
それをメンバとして持つ構造体をリストとして操作する為に使うのが、非常に複雑な仕組みだ。
## リスト操作
- [初期化](#初期化)
- [追加](#追加)
- [削除](#削除)
- [走査](#走査)

### 初期化
リストの初期化はマクロ`LIST_HEAD(name)`で行う。
`name`はリストにしたいデータ構造の名前を指定する。

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

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

サンプル

```c
LIST_HEAD(student_list);

struct student_entry {
    char *name;
    int num;
    struct list_head head;
};
```

これで`student_entry`というリストの要素の型と`student_list`という名前のリストを定義する。

### 追加
- [リストの先頭に追加する](#`list_add`)
- [リストの末尾に追加する](#`list_add_tail`)

### `list_add`
カーネルでの定義は少し複雑なので、動きは変えずに少しシンプルに書く

```c
void list_add(struct list_head *new, struct list_head *head) {
    struct list_head *next = head->next;
    next->prev = new;
    new->next = next;
    new->prev = head;
    head->next = new;
}
```
サンプル

```c
struct student_entry *e = malloc(sizeof(student_entry));
list_add(&e->head, &student_list);
```

### `list_add_tail`
また少し簡略化
勘の良い方は何かに気づくと思うが詳細は後で

```c
void list_add_tail(struct list_head *new, struct list_head *head) {
    struct list_head *prev = head->prev;
    head->prev = new;
    new->next = head;
    new->prev = prev;
    prev->next = new;
}
```

### 削除
`list_del`
リストの前の要素の`next`を次の要素に、
リストの次の要素の`prev`を前の要素にする事でリストから削除する。

```c
void list_del(struct list_head *entry) {
    struct list_head *next = entry->next, *prev = entry->prev;
    next->prev = prev;
    prev->next = next;
    next = LIST_POISON1;
    prev = LIST_POISON2;
}
```

また、削除する要素の`next`、`prev`には`NULL`ではない値を入れる。
### 走査
リストに対する走査も複数あり、マクロで定義されたfor文が多い。
ここでは、リストの各要素に対して操作を行う`list_for_each_entry`を例に解説する。

```c
#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))
```

posに指定したリストの先頭要素を代入し、リスト末尾まで走査するfor文。
サンプル

```c
LIST_HEAD(student_list);

struct student_entry {
    char *name;
    int num;
    struct list_head head;
};

struct student_entry *e = malloc(sizeof(student_entry));
e->name = "hoge";
e->num = 1;
list_add(&e->head, &student_list);

struct student_entry *itr;
list_for_each_entry(itr, &student_list, head) {
    printf("%s %d\n", itr->name, itr->num);
}
```
## マクロ
上で解説した事がわかれば、使用する上では充分だろう。
しかし完全に理解できていない。
それぞれ簡略化して説明した部分を改めて掘り下げる。

### 本当の`list_add`
実際のカーネル内での`list_add`の定義は

```c
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}
```

`__list_add`を呼び出している。
また、`list_add_tail`も

```c
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}
```

引数が違うだけで、同じように`__list_add`を呼び出している。
では`__list_add`はどうなっているのか

```c
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);
}
```
まず最初の`__list_add_valid`だが、`CONFIG_DEBUG_LIST`が定義されていない場合はただ`true`を返す。

```c
#ifdef CONFIG_DEBUG_LIST
extern bool __list_add_valid(struct list_head *new, 
                struct list_head *prev,
                struct list_head *next);
#else
static inline bool __list_add_valid(struct list_head *new, 
                struct list_head *prev,
                struct list_head *next) {
    return true;
}
```
`CONFIG_DEBUG_LIST`が定義されていた場合の動作は`list_debug.c`で定義されている

```c
bool __list_add_valid(struct list_head *new, struct list_head *prev,
		      struct list_head *next)
{
	if (CHECK_DATA_CORRUPTION(next->prev != prev,
			"list_add corruption. next->prev should be prev (%px), but was %px. (next=%px).\n",
			prev, next->prev, next) ||
	    CHECK_DATA_CORRUPTION(prev->next != next,
			"list_add corruption. prev->next should be next (%px), but was %px. (prev=%px).\n",
			next, prev->next, prev) ||
	    CHECK_DATA_CORRUPTION(new == prev || new == next,
			"list_add double add: new=%px, prev=%px, next=%px.\n",
			new, prev, next))
		return false;

	return true;
}
```
~~めんどくさい~~

`next->prev != prev` `prev->next != next` `new == prev` のいずれかが`true`だった場合、(場合によっては警告を出し、)`false`を返す。
次に、`next->prev`を`new`にするなどしているが

```c
	next->prev = new;
	new->next = next;
	new->prev = prev;
	WRITE_ONCE(prev->next, new);
```
`WRITE_ONCE`とは

```c
static __always_inline void __write_once_size(volatile void *p, void *res, int size)
{
	switch (size) {
	case 1: *(volatile __u8 *)p = *(__u8 *)res; break;
	case 2: *(volatile __u16 *)p = *(__u16 *)res; break;
	case 4: *(volatile __u32 *)p = *(__u32 *)res; break;
	case 8: *(volatile __u64 *)p = *(__u64 *)res; break;
	default:
		barrier();
		__builtin_memcpy((void *)p, (const void *)res, size);
		barrier();
	}
}

#define WRITE_ONCE(x, val) \
({							\
	union { typeof(x) __val; char __c[1]; } __u =	\
		{ .__val = (__force typeof(x)) (val) }; \
	__write_once_size(&(x), __u.__c, sizeof(x));	\
	__u.__val;					\
})
```
簡潔に言うと、gccによって余計な最適化が行われる事を防ぎながら代入を行っている。
即ち、`prev->next = new`と読み替えても本質的な意味は変わらない。

### 本当の`list_for_each_entry`
サンプルでは`list_for_each_entry(itr, &student_list, head) {`
定義は変わらない。

```c
#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_first_entry`、`list_next_entry`はどうなっているのか。

```c
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)
```
で、またラッパー

```c
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)
```
またラッパー。
そしてこの`container_of`はLinuxカーネルにおいて超重要頻出変態マクロ
`kernel.h`で定義されている。

```c
#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))); })
```

早速またマクロ
まず`BUILD_BUG_ON_MSG`
名前の通り、第一引数が`true`ならビルド時にエラーメッセージを出力する。
第一引数は

```c
!__same_type(*(ptr), ((type *)0)->member) && !__same_type(*(ptr), void)
```
`__same_type`は名前通り引数の方が一致しているか返すマクロ
つまりこの行は

**`*ptr`と`((type*)0)->member`の型が異なり、かつ`*ptr`が`void`型で無い時にビルドエラーを発生させる**

次の行が本質的で

```c
	((type *)(__mptr - offsetof(type, member))); })
```

`__mptr`は`void*`にキャストした`ptr`
また別のマクロがある
`offsetof`も名前通り、`member`を持つ`type`での、`member`のオフセットを求める。

```c
#define offsetof(type, member) ((size_t) &((type*)0)->member)
```

よって展開すると、`container_of`は

```c
    ((type*)((void*)ptr - ((size_t) &((type*)0)->member)));
```

何をしているか簡潔に言うと

***`ptr`を`member`というメンバ名で持つ`type`型のポインタを求めている***

コレが理解出来れば良いだろう。
本題に戻る。

`list_for_each_entry`の理解の為、マクロを少しずつ展開してみると

```c
list_for_each_entry(itr, &student_list, head) {
```
が

```c
for (itr = list_first_entry(&student_list, typeof(*itr), head);
        &itr->head != student_list;
        itr = list_next_entry(itr, head))
```
となり、さらに

```c
for (itr = container_of((&student_list)->next, typeof(*itr), head);
        &itr->head != student_list;
        itr = container_of(itr->head.next, typeof(*itr), head))
```
となる
つまり、サンプルコードのマクロを少し展開すると

```c
struct list_head student_list { &student_list, &student_list};

struct student_entry {
    char *name;
    int num;
    struct list_head head;
};

struct student_entry *e = malloc(sizeof(student_entry));
e->name = "hoge";
e->num = 1;
list_add(&e->head, &student_list);

struct student_entry *itr;
for(itr = container_of((&student_list)->next, struct student_entry, head);
    &itr->head != student_list;
    itr = container_of(itr->head.next, struct student_entry, head)) {
    printf("%s %d\n", itr->name, itr->num);
}
```

- `struct student_entry *`型の`itr`に、リストの先頭要素を代入。
- `head`のアドレスが`student_entry`になる(つまりリスト終端)まで
- `itr`を`itr->head.next`を持つリストの要素(リストの次の要素)で更新




## sample code
```c
#include <stdio.h>
#include <stdlib.h>

struct list_head list_head;

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

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

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

#define offsetof(type, member) ((size_t) &((type *)0)->member)

#define container_of(ptr, type, member) ({      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type, member) );})

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

#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))

void list_add(struct list_head *new, struct list_head *head) {
    struct list_head *next = head->next;
    next->prev = new;
    new->next = next;
    new->prev = head;
    head->next = new;
}

LIST_HEAD(student_list);

struct student_entry {
    char *name;
    int num;
    struct list_head head;
};

int main() {
    struct student_entry *a = malloc(sizeof(struct student_entry));
    a->name = "hoge";
    a->num = 1;
    struct student_entry *b = malloc(sizeof(struct student_entry));
    b->name = "fuga";
    b->num = 2;

    struct student_entry *itr;

    list_add(&b->head, &student_list);
    list_add(&a->head, &student_list);

    list_for_each_entry(itr, &student_list, head) {
        printf("%s %d\n", itr->name, itr->num);
    }
}
```