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

留言

這個網誌中的熱門文章

如何將Linux打造成OpenFlow Switch:Openvswitch

如何利用 Wireshark 來監聽 IEEE 802.11 的管理封包

我弟家的新居感恩禮拜分享:善頌善禱