カーネルのリンクリスト

GCC

何故かExt2ファイルシステムについて調べてました。ちょっとカーネルのソースを覗いてみたら、struct list_head構造体がやたら出てくる。気になって、include/linux/list.hを覗いてみると、驚くべき仕組みが隠れてた。

そんなわけで写経。

#include <stdio.h>

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

#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr);         \
    (ptr)->prev = (ptr);         \
} while(0)

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

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

#define list_entry(ptr, type, member) \
    ((type *)( (char *)(ptr) - (unsigned long)(&((type *)0)->member)))

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); \
            pos = pos->next)

struct my_list {
    int num;
    struct list_head list;
};

int main(void)
{
    int i;
    struct list_head *pos;

    struct my_list root;
    struct my_list childlen[5];

    INIT_LIST_HEAD(&root.list);
    root.num = 99;

    for (i = 0; i < 5; i++) {
        childlen[i].num = i;
        list_add(&childlen[i].list, &root.list);
    }

    printf("\n");

    list_for_each(pos, &root.list) {
        printf("pos    : %p\n", pos);
        printf("offset : %p\n", (&((struct my_list *) 0)->list)); // 0x04
        printf("entry  : %p\n", list_entry(pos, struct my_list, list));
        printf("num    : %d\n", list_entry(pos, struct my_list, list)->num);
        printf("\n");
    }

    return 0;
}


まず、コレ。

struct my_list {
    int num;
    struct list_head list;
};

オカシイ。struct list_head list。ポインタじゃない。調べてみると、sizeof (struct my_list)は12バイト。構造体のネストになってる。何かが匂う。


次。


for_eachなんてC言語にあったっけ・・・「ステキ過ぎる」


しかし、問題がある。posの位置は、あくまでリストポインタの位置で、親ポインタの位置じゃない。numが欲しいのにどうしたらいいんだ!!


最大の秘密が、マクロlist_entry。(実際にはkernel.hに定義してあるcontainer_of)

listのオフセット位置を割り出して、親のポインタ位置を算出。こうすればnumを取り出すことが可能となる。


「C言語でも継承出来るよ!!」


ついでに、

struct my_list {
    int num;
    struct list_head list1;
    struct list_head list2;
};

みたいな事まで出来ちゃうと。うは。ステキ。


カーネルソースは案外普通に書いてあると思ってたけど、かなり変態技満載な予感がする。

参考

追記

  • 2009-08-10 リンク先修正