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中的那些鏈表