Linuxカーネルのソースコードを読む方法(その3: list.h 前編)

Linux カーネルソースコードを読んだのでメモを公開します.Linuxカーネルを読む際の参考になれば幸いです.

今回のお題: include/linux/list.h

今回はカーネル内部で多用されているデータ構造の一つとして linked list の実装を読みました.主なファイルは linux/list.h になります.ソースコードのバージョンは linux-5.1.8です.

カーネル内部でよく利用されているデータ構造

よく利用されているデータ構造としては以下のものがあります.

  • List
  • Queue
  • Map
  • Binary tree

C++であればSTLの std::list とか std::queue を利用するところです.しかしカーネルの実装しかもC言語です. linux kernel は自前の実装を提供しています.

Singly linked list と Doubly circular linked list

今回読むソースコード include/linux/list.h はいわゆる doubly circular linked list を実装しています.

念の為 Singly linked list と Doubly circular linked list の違いを説明しておきます.

singly linked list

リスト構造には様々な種類があります.例えば singly linked list であれば,ノードを

struct Node {
    struct Node *next;
};

のような形で定義します.そしてこのNode構造体を使ってリスト構造を構築します.アスキーアートで図示すると,例えばノード数3のリスト構造は次のようになります.リストの終端はNULLポインタで表現しています

         +---------+       +---------+       +---------+ 
         |  Node   |       |  Node   |       |  Node   |       
         +---------+  ---> +---------+  ---> +---------+  ---> NULL
                     next             next            
doubly circular linked list

一方,linux/list.hが実装している doubly circular linked list では,ノードを次のように定義します.

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

実際の定義は include/linux/types.h の186行目にあります.

そしてリスト構造を次のように構築します.こちらもノード数3のリスト構造の例です.

   +--------------------------------------------------------+
   | prev             prev             prev                 |  
   +---  +---------+ <--   +---------+ <--   +---------+ <--+  
         |list_head|       |list_head|       |list_head|       
   +---> +---------+  ---> +---------+  ---> +---------+  --+
   |                  next             next            next |
   +--------------------------------------------------------+

singly linked list と異なり doubly linked list には nextのポインタに加えて prevのポインタがあります.この2つのポインタを使って,各ノードは,次ノード,前ノード,双方にリンクを貼っています.

また circular linked list とあるように,リストの終端がありません.リストの末尾はリストの先頭に接続します.

struct list_head の利用例

// ノードの定義
struct Data {
    struct list_head list;
    int value;
};

// ノードを新しく生成する関数
struct Data * new_data()
{
    Data *ptr = kalloc( sizeof (struct Data), GFP_KERNEL );
    INIT_LIST_HEAD(&ptr->list);
    return ptr;
}

// リストを作成する例
void myfunc {
    struct list_head head;
    INIT_LIST_HEAD(&head);
    
    struct Data* A = new_data();
    struct Data* B = new_data();
    list_add(&A->list,  &head);
    list_add(&B->list,  &head);
}

myfunc() の中で生成したリスト構造をアスキーアートで表現すると次のようになります.

   +--------------------------------------------------------+
   | prev             prev             prev                 |  
   +---  +---------+ <--   +---------+ <--   +---------+ <--+  
         |   head  |       | A->list |       | B->list |       
   +---> +---------+  ---> +---------+  ---> +---------+  --+
   |                  next             next            next |
   +--------------------------------------------------------+

リストの操作: list_for_each()

circular linked list にはリストの末尾がありません.foreach()のような,リストの要素を順番に見る処理は次のように実装します.

struct list_head *pos;
for (pos = &head->next; ptr != &head; ptr = ptr->next) {
    // 処理
}

linux カーネルは list_for_each() というマクロを定義しています.(list.hの489行目)

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

このマクロを使うと上記のコードは

  struct list_head *pos;
  list_for_each(pos, &head) {
      // 処理
  }

という風にコーディングできます.

リストの操作: container_of()

list_for_each は list_head を順に走査するマクロです. list_head から strcut Data のポインタを得るには container_ofマクロを使います

  struct list_head *pos;
  list_for_each(pos, &head) {
       struct Data * p = container_of(pos, struct Data, list);
  }

container_of マクロは linux/kernel.h の970行目で定義されているマクロです.

970:
/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:	the pointer to the member.
 * @type:	the type of the container struct this is embedded in.
 * @member:	the name of the member within the struct.
 *
 */
#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))); })

エラーチェックなどを削除すると,container_of の実装は次のように簡略化できます

#define container_of(ptr, type, member) ((type *)( (char *)(ptr) - offsetof(type,member) ))

要は

  • offsetof()を使って構造体 type のメンバ変数 member のオフセットアドレスを計算
  • ptr からオフセットを引いて,構造体typeの先頭アドレスを計算
  • アドレスを type* 型にキャスト

しているだけです.

リストの操作:list_for_each_entry()

意味的には for_each_list と container_of を組み合わせたマクロです

#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_head 構造体を介さず,直接 struct Data のポインタでループを回せます.

  struct Data *p;
  list_for_each_entry(p, &head, list) {
      // 処理
  }