Linked List in Linux Kernel

Linux Kernel實現的鏈表與眾不同,大多數人所熟悉的方式應該是在「鏈表中包含結構體」,而Linux內核的實現方式則是所謂的「結構體中包含鏈表」。這樣的說法聽起來很玄乎,不如給出具體的定義和實例。

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

這就是內核代碼中Linked List的結構體定義,從list_head定義可以看出,內核的鏈表是循環鏈表。我們可以這麼用它:

struct these_shit_dictators{
    char   name[MAX_LEN];
    char   country[MAX_LEN];
    struct list_head list;
};

鏈表的操作接口

一般在使用指針時要初始化,這是一個好的編程習慣,操作內核提供的鏈表也是如此。首先用INIT_LIST_HEAD()函數對其初始化。INIT_LIST_HEAD()做的工作很簡單:

#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

可以看到初始化就是把指針指向自己。在不同版本的源碼中,這些函數的實現方式略有不同,例如在linux-2.6.26中,此函數不是宏定義,而是一個內聯函數,不過它們所做的工作都是大同小異的,這一點在本文其他部分都一樣,下面就不再提醒了。

list_add操作

插入操作所做的操作非常簡單,只要學過基礎的數據結構的人一眼就能看明白:

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

對於循環鏈表來說,在頭部插入和在尾部插入是一樣的,確實,內核也是這麼做的,看一段很有意思的代碼:

void list_add(struct list_head *new, struct list_head *head){
    __list_add(new, head, head->next);
}

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

對於刪除、合併等操作也都類似,有興趣的讀者可以自己翻看源碼,比較簡單的。

遍歷操作、獲取結構體成員操作

我認為kernel實現的鏈表最優意思的部分是list_entry、list_for_each等幾個宏的實現。

首先有個問題:使用這種「Items contains the list」的方式如何通過這個list_head成員獲得結構體的其他成員? 答案是list_entry宏,我們先來看內核源碼是怎麼寫的:

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
    //  in 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) );})

用法: tmp=list_entry(ptr, type, member) 其中,

ptr是指向結構體中struct list_head 成員的指針;
type是本結構體的名字;
member是指在結構體中struct list_head叫什麼名字,本例中叫list;
最後返回的是指向這個結構體的指針,有了這個指針,我們就可以調用其他成員了,比如tmp->name;

然後,我們來分析一下這個有意思的宏:

1、const typeof( ((type )0)->member ) mptr = (ptr); 這句是聲明瞭一個與名叫member的成員的類型一樣的一個指針mptr,並賦值為ptr;

2、(type )( (char )__mptr – offsetof(type,member) ); mptr指向的地址減去member在type中的偏移,就得到了type的地址了;

至於為什麼要重新聲明一個mptr,不直接用ptr呢?

我想大概是因為不破壞ptr指針的內容,以便後續的代碼繼續正常使用ptr。

Update: 感謝 肉兔、Fleuria、Bearice 同學的幫助~

感覺應該就是為了加一層類型的靜態檢查吧,C的宏是沒有類型的,但可以做點功夫給它模擬一點類型檢查。假如沒有這句,這個ptr若是個無關的類型(比如偶爾可能會敲錯變量)在編譯時不會報錯,甚至warning也不會有。 加上這麼一句,如果ptr的類型不對,在編譯時就可以報一個warning之類的了。刪掉這句內核該依然可以正常編譯,但有它可以讓開發者的日子更好過一點。

其他幾個有意思的宏,例如list_for_each(pos, head)之類的實現原理也類似,在此就不詳細寫了,有興趣的話請參看 include/linux/list.h

—————–

參考資料:

1、《Linux內核設計與實現》 2、淺析Linux Kernel中的那些鏈表