カーネルに於けるリスト型データ構造

LinuxカーネルはCで書かれており、C言語には標準でリストが無い。

どうやってリストを作るかは実装した本人次第だ。

Linuxカーネルのような大規模なコードでは、リストの標準化を行っている。

その実装はCの特異な言語仕様を駆使したものであり、Cをある程度理解していないとかなり難しい。

実装

リストにしたいデータ構造(構造体)に特殊なデータ構造をメンバとして持たせる事で、リストを実装している。

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

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

list_head

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

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

つまり、リストとして繋がっているのはあくまでlist_head同士である。

それをメンバとして持つ構造体をリストとして操作する為に使うのが、非常に複雑な仕組みだ。

リスト操作

初期化

リストの初期化はマクロLIST_HEAD(name)で行う。

nameはリストにしたいデータ構造の名前を指定する。

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

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

サンプル

LIST_HEAD(student_list);

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

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

追加

list_add

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

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;
}

サンプル

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

list_add_tail

また少し簡略化

勘の良い方は何かに気づくと思うが詳細は後で

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を前の要素にする事でリストから削除する。

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を例に解説する。

#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文。

サンプル

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の定義は

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

__list_addを呼び出している。

また、list_add_tailも

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

引数が違うだけで、同じように__list_addを呼び出している。

では__list_addはどうなっているのか

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を返す。

#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で定義されている

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にするなどしているが

	next->prev = new;
	new->next = next;
	new->prev = prev;
	WRITE_ONCE(prev->next, new);

WRITE_ONCEとは

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

定義は変わらない。

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

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

で、またラッパー

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

またラッパー。

そしてこのcontainer_ofはLinuxカーネルにおいて超重要頻出変態マクロ

kernel.hで定義されている。

#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ならビルド時にエラーメッセージを出力する。

第一引数は

!__same_type(*(ptr), ((type *)0)->member) && !__same_type(*(ptr), void)

__same_typeは名前通り引数の方が一致しているか返すマクロ

つまりこの行は

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

次の行が本質的で

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

__mptrはvoid*にキャストしたptr

また別のマクロがある

offsetofも名前通り、memberを持つtypeでの、memberのオフセットを求める。

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

よって展開すると、container_ofは

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

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

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

コレが理解出来れば良いだろう。

本題に戻る。

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

list_for_each_entry(itr, &student_list, head) {

が

for (itr = list_first_entry(&student_list, typeof(*itr), head);
        &itr->head != student_list;
        itr = list_next_entry(itr, head))

となり、さらに

for (itr = container_of((&student_list)->next, typeof(*itr), head);
        &itr->head != student_list;
        itr = container_of(itr->head.next, typeof(*itr), head))

となる

つまり、サンプルコードのマクロを少し展開すると

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);
}

sample code

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