Rev.4を表示中。最新版はこちら。

list_head構造体はlist_headをさすnext, prevの２つだけのメンバーを持つ構造体です。リスト構造を作りたいstructに埋め込むだけです。あとは提供されているマクロを使って追加、削除、エントリーの取り出し等が操作できるというものです。

リストしたい構造体に埋め込みます。埋め込む位置は対象structのどこでもかまいません。このアドレス解決はcontainer_ofで行います。では何故雑になるのに任意の位置に埋め込むことを可能にしているのでしょうか？　任意に埋め込めるという事は１つの構造体に複数の異なるリストを持たせるためだと思います。実際カーネル内には一つの構造体で３つも４つもリストを持たせている構造体が多々ありました。

じゅじゅ繋ぎのように、最後のnextが先頭のリストへ、先頭のリストのprevが最後のリストへと繋がっています。このような構造だとどこから検索しても目的とするリストに到達できます。また以下に説明するようにリストの最後にリストを追加する場合、リストの最後までたどる必要もありません。先頭のリストに最後のリストが設定されているからです。

リストに新規リストを追加する場合、先頭リストのprevに新規リストを。最後リストのnextに新規リストを、そして新規リストのnextを先頭のリストへ、新規のリストのprevを最後だったリストに繋ぎます。要は先頭のリストと最後のリストをばっさり切って、そこに新規のリストを埋め込む感じです。


LIST_HEADマクロは先頭のリストを定義します。nameが変数となるわけですが、nextもprevも自分自身というわけです。なお先頭リストは対象となる構造体に埋め込まれません。

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
       struct list_head name = LIST_HEAD_INIT(name)

list_add_tailマクロは先頭のリストと最後のリストをばっさり切って、そこに新規のリストを埋め込むマクロです。頭がこんがりそうですが、よく考えるとなるほどとなります。

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

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

list_entryがリストから対象の構造体を取り出すマクロです。このcontainer_ofマクロがトリッキーで、要は自分のアドレスから対象の構造体内の自分のオフセットを引いたアドレスを返すことで実現しています。

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

サンプルプログラムネタ元です。1から１０数字のセットした構造体です。それにすべてのリスト、奇数番だけのリスト、偶数番だけのリストを作成します。

#include <linux/kernel.h>
#include <linux/syscalls.h>
#include <linux/module.h>
#include <linux/moduleparam.h>
#include <linux/unistd.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/list.h>

static LIST_HEAD(head0);
static LIST_HEAD(head1);
static LIST_HEAD(head2);

struct my_object {
  struct list_head list0;
  struct list_head list1;
  struct list_head list2;
  long int sec;
};

int init_module(void)
{
  struct list_head *p;
  struct my_object *myobj;
  int i;

  for (i = 0; i < 10; ++i) {
    myobj = kmalloc(sizeof(struct my_object), GFP_KERNEL);
    myobj->sec = i;
   	list_add_tail(&myobj->list0, &head0);
	if (i % 2) {
    	list_add_tail(&myobj->list1, &head1);
	}
	else {
    	list_add_tail(&myobj->list2, &head2);
	}
  }

  list_for_each(p, &head1) {
    myobj = list_entry(p, struct my_object, list1);
    printk("odd %d\n", myobj->sec);
  }

  list_for_each(p, &head2) {
    myobj = list_entry(p, struct my_object, list2);
    printk("even %d\n", myobj->sec);
  }
  return 0;
}

void cleanup_module(void)
{
  struct my_object *myobj;
  int i = 0;
  while(!list_empty(&head0)) {
    myobj = list_entry(head0.next, struct my_object, list0);
    printk("all %d\n", myobj->sec);
    list_del(&myobj->list0);
    kfree(myobj);
  }
}

[root1@localhost test]# insmod test1.ko
[root1@localhost test]# rmmod test1
[root1@localhost test]# dmesg
odd 1
odd 3
odd 5
odd 7
odd 9
even 0
even 2
even 4
even 6
even 8
all 0
all 1
all 2
all 3
all 4
all 5
all 6
all 7
all 8
all 9

listマクロは他にもリスト操作をするマクロが用意されています。これらはカーネルというのでなく、汎用的なリスト操作ということで使えそうですね。