2007年10月18日 星期四

Linux Kernel: 強大又好用的list_head結構

程式設計者在設計一個doubly linked list時,通常會在所宣告的結構裡宣告兩個結構指標,如下所示:
struct student {
char name[16];
int id;
struct student *next, *prev;
};

只要經由prev與next兩個結構指標,便能取得該doubly linked list所有資訊。

然而,Linux kernel並非引用此種作法。因此,Linux kernel定義一通用結構 (struct list_head, include/linux/list.h),用以實作doubly linked list,此結構相當簡單,如下所示:
struct list_head {
struct list_head *next, *prev;
};


所以物件student宣告為如下:
struct student
{
char name[16];
int id;
struct list_head list;
};

藉由list變數便能取得doubly linked list所有資訊。

list_head相關Marco與Function

這裡僅介紹較常用的macro與function,如欲進一步得知其它marco請參考include/linux/list.h


LIST_HEAD(name)
struct list_head name = { &(name), &(name) };
將next與prev指到自己,意味著此list為空的。

list_empty(const struct list_head *head)
retrun head->next == head;
檢查此list是否為空的。

list_add(struct list_head *new, struct list_head *head)
head->next->prev = new;
new->next = head->next;
new->prev = head;
head->next = new;
將資料加入至doubly linked list最前端。建議自己動手畫個圖,便可了解這幾個指標指到何處。

list_del(struct list_head *entry)
entry->next->prev = entry->prev;
entry->prev->next = entry->next;
將某一資料從中刪除。

list_entry(ptr,type,member)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
透過此函式便能算出結構的起始位址,並做結構轉型便能取得結構的資料,此計算方式相當好用啊!!!
以struct student為例,如下所示:
  1. (unsigned long)(&((struct student *)0)->member))) ==> 計算出list成員相對位址。通常看到這一個敘述,直覺地覺得應該會記憶體區段錯誤吧 (Segmentation Fault)!? 因為該敘述用NULL的pointer存取list成員,但在(struct student *)0)->member))前面加了&符號,就不會發生記憶體區段錯誤。因為&符號,只意味著存取list的位址,而不是資料,經由此敘述便能取得list的位移植。如下圖所示,該敘述所得之位移植值為20。
    list_head
  2. ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) ==> 取得位移植之後,再將list的位址減去位移植,便能取得該結構的起始位址,如下圖所示 (假設結構起始位址為x),最後再做結構轉型變大功告成。
    list_entry
list_for_each(pos, head)
for (pos = (head)->next; pos != (head); pos = pos->next)
取得該doubly linked list所有資料。

範例程式
光看這些Macro跟函式可能比較無法有sense,因此小弟寫了一簡單的程式,有興趣的可以下載此範例程式玩玩看。XDD

[Reference]
Understanding the Linux Kernel, Third Edition
Linux Kernel Source Code Version 2.6.20-15

5 則留言:

jserv 提到...

Thanks! 非常清楚的解說。

在 openmoko 的處理 GSM daemon / library 實做中,也用到 kernel linked-list,可參考程式碼: http://svn.openmoko.org/trunk/src/target/gsm/

Adrian Huang 提到...

原來是Jserv大大啊~~感謝您的光臨啊!COSCUP 2007會去聽你的演講喔!XDDD
Openmoko也是list_head啊~~水捏!!

Michaels programming world 提到...

不好意思
我是linux kernel 的新手
想請問一下
我有試著跑你的例子
是OK的,
但是在這行:
sprintf(sl[idx].name, "Adrian Huang");
這行如果改寫成:
sl[idx].name="Adrian Huang";
好像會error.
請問您知道為什麼嗎?^^"
謝謝您 如果您可以給我一些意見的話

Adrian Huang (黃圳柏) 提到...

To Michaels:
C語言字串處理不可以直接指定給某一變數, 必須使用字串處理函式, 底下提供幾種方法:

1) sprintf(sl[idx].name, "Adrian Huang");
2) strncpy(sl[idx].name, "Adrian Huang", sizeof("Adrian Huang"));

提供給你參考看看囉.

Michaels programming world 提到...

真的很謝謝你
我寫了一個簡單的C struct做實驗
就知道您的意思了
XD 謝謝
想學 linux kernel,果然C語言要先熟