Linked List in Linux Kernel

Linklist 是最常被使用的一種資料結構，當然在 Link Kernel 中也不例外。下面會介紹在 Linux Kernel 中所使用的 Link List。 當然，按照慣例，排版會按照自己喜歡的格式來進行排 版。

Kernel: 2.6.17

在 Linux 裡面，List 的相關定義函式是放在 linux/include/linux/list.h，而最主要的定義如下：

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

很明顯地可以看出，這是一個 double linked list 的架構，但是看起來跟一般我們寫程式所實作的方式並不相同。如果是我們設計的話，我們可能會設計成這個樣子：

struct my_list
{
  void            *myitem;
  struct my_list  *next;
  struct my_list  *prev;
};

其中 myitem 就是用來存每個 list node 的 Data ，而且為了要泛用，所以使用了 (void *) 這樣的資料型態。 這樣的設計跟 Linux Kernel 的設計到底有什麼差異還不清楚，或許是個人風格吧～
(我同事有發表相關的意見，他認為用 Linux Kernel 的那種作法可以將 list 跟 data 完全的切割，而使用我一般的作法，固然可以達到 list 的效果，但是在參數傳遞上，變數名稱將會是 struct my_list，而無法直覺的看出來實際的資料型態...well ...見仁見智囉)

Linux Kernel list 的使用方式，我們看下面一個範例：

#include < stdio.h >
#include < stdlib.h >
#include "list.h"

struct kool_list
{
  int to;
  struct list_head list;
  int from;
};

int main(int argc, char **argv)
{
  struct kool_list *tmp;
  struct list_head *pos, *q;
  unsigned int i;
  struct kool_list mylist;

  INIT_LIST_HEAD(&mylist.list);

  for(i=5; i!=0; --i)
  {
       tmp= (struct kool_list *)malloc(sizeof(struct kool_list));
       printf("enter to and from:");
       scanf("%d %d", &tmp->to, &tmp->from);
       list_add(&(tmp->list), &(mylist.list));
  }
  printf("\n");

  printf("traversing the list using list_for_each()\n");
  list_for_each(pos, &mylist.list)
  {
      tmp= list_entry(pos, struct kool_list, list);
      printf("to= %d from= %d\n", tmp->to, tmp->from);
  }
  printf("\n");

  printf("traversing the list using list_for_each_entry()\n");
  list_for_each_entry(tmp, &mylist.list, list)
  {
      printf("to= %d from= %d\n", tmp->to, tmp->from);
  }
  printf("\n");

  printf("deleting the list using list_for_each_safe()\n");
  list_for_each_safe(pos, q, &mylist.list)
  {
      tmp= list_entry(pos, struct kool_list, list);
      printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);
      list_del(pos);
      free(tmp);
  }

return 0;
}

這段程式是一個非常簡單的範例，從 data structure 的宣告，到 list 的初始化，新增、刪除全都具備了，而 mylist 在這裡則是當作 dummy header。至於詳細 API or MACRO 的定義請在 linux/include/linux/list.h 自己查詢。下面只介紹我覺得有趣的寫法。

當我們使用 Linux Kernel 裡面的 list 時，也就是自訂一個 Data Structure ，並在裡面使用 list 時，我該如何透過該 list 的節點，取得整個 Data Structure 的內容呢？當然，從上述的範例得知，我們可以使用 list_entry 這個 MACRO，但他是怎麼做到的？先來看看定義：

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

非常好，我們要再繼續追下去，搜尋的節果發現， container_of 這 MACRO 位在 linux/include/linux/kernel.h 裡面。定義如下：

/**
* 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) ({          \
     const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
     (type *)( (char *)__mptr - offsetof(type,member) );})

相當有趣的寫法～ 以上面我們所定的 struct kool_list 為例，我們可以用下圖來表示：

+-----------------+        ^
+    to           +        + offset
+-----------------+ <---- ptr 
+   list_head     + 
+-----------------+ 
+    from         + 
+-----------------+

所以將 ptr 剪去 offset，就是真正資料的位置。

PS 1:
在 Kernel 2.4 的年代， list_entry 的實際作法如下（精神一樣）

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

PS 2：
offsetof 是 C99 新制定的 MACRO，定義如下：
"The offsetof() macro returns the offset of the element name within the struct or union composite. This provides a portable method to determine the offset."

PS 3：
typeof 也是一個常用的 MACRO，用法跟 sizeof 差不多，只是回傳值是輸入變數的型態，下面是一個簡單的範例。

#define max(a,b) \
       ({ typeof (a) _a = (a); \
           typeof (b) _b = (b); \
         _a > _b ? _a : _b; })