Linux內(nèi)核代碼中廣泛使用了數(shù)據(jù)結(jié)構(gòu)和算法，其中最常用的兩個是鏈表和紅黑樹。

鏈表

Linux內(nèi)核代碼大量使用了鏈表這種數(shù)據(jù)結(jié)構(gòu)。鏈表是在解決數(shù)組不能動態(tài)擴展這個缺陷而產(chǎn)生的一種數(shù)據(jù)結(jié)構(gòu)。鏈表所包含的元素可以動態(tài)創(chuàng)建并插入和刪除。

鏈表的每個元素都是離散存放的，因此不需要占用連續(xù)的內(nèi)存。鏈表通常由若干節(jié)點組成，每個節(jié)點的結(jié)構(gòu)都是一樣的，由有效數(shù)據(jù)區(qū)和指針區(qū)兩部分組成。有效數(shù)據(jù)區(qū)用來存儲有效數(shù)據(jù)信息，而指針區(qū)用來指向鏈表的前繼節(jié)點或者后繼節(jié)點。因此，鏈表就是利用指針將各個節(jié)點串聯(lián)起來的一種存儲結(jié)構(gòu)。

（1）單向鏈表

單向鏈表的指針區(qū)只包含一個指向下一個節(jié)點的指針，因此會形成一個單一方向的鏈表，如下代碼所示。

?

struct?list?{
????int?data;???/*有效數(shù)據(jù)*/
????struct?list?*next;?/*指向下一個元素的指針*/
};

?

如圖所示，單向鏈表具有單向移動性，也就是只能訪問當前的節(jié)點的后繼節(jié)點，而無法訪問當前節(jié)點的前繼節(jié)點，因此在實際項目中運用得比較少。

單向鏈表示意圖

（2）雙向鏈表

如圖所示，雙向鏈表和單向鏈表的區(qū)別是指針區(qū)包含了兩個指針，一個指向前繼節(jié)點，另一個指向后繼節(jié)點，如下代碼所示。

?

struct?list?{
????int?data;???/*有效數(shù)據(jù)*/
????struct?list?*next;?/*指向下一個元素的指針*/
????struct?list?*prev;?/*指向上一個元素的指針*/
};

?

雙向鏈表示意圖

（3）Linux內(nèi)核鏈表實現(xiàn)

單向鏈表和雙向鏈表在實際使用中有一些局限性，如數(shù)據(jù)區(qū)必須是固定數(shù)據(jù)，而實際需求是多種多樣的。這種方法無法構(gòu)建一套通用的鏈表，因為每個不同的數(shù)據(jù)區(qū)需要一套鏈表。

為此，Linux內(nèi)核把所有鏈表操作方法的共同部分提取出來，把不同的部分留給代碼編程者自己去處理。

Linux內(nèi)核實現(xiàn)了一套純鏈表的封裝，鏈表節(jié)點數(shù)據(jù)結(jié)構(gòu)只有指針區(qū)而沒有數(shù)據(jù)區(qū)，另外還封裝了各種操作函數(shù)，如創(chuàng)建節(jié)點函數(shù)、插入節(jié)點函數(shù)、刪除節(jié)點函數(shù)、遍歷節(jié)點函數(shù)等。

Linux內(nèi)核鏈表使用 struct list_head 數(shù)據(jù)結(jié)構(gòu)來描述。

?

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

?

struct list_head數(shù)據(jù)結(jié)構(gòu)不包含鏈表節(jié)點的數(shù)據(jù)區(qū)，通常是嵌入其他數(shù)據(jù)結(jié)構(gòu)，如struct page數(shù)據(jù)結(jié)構(gòu)中嵌入了一個lru鏈表節(jié)點，通常是把page數(shù)據(jù)結(jié)構(gòu)掛入LRU鏈表。

?

struct?page?{
????...
????struct?list_head?lru;
????...
}

?

鏈表頭的初始化有兩種方法，一種是靜態(tài)初始化，另一種動態(tài)初始化。

把next和prev指針都初始化并指向自己，這樣便初始化了一個帶頭節(jié)點的空鏈表。

?

/*靜態(tài)初始化*/
#define?LIST_HEAD_INIT(name)?{?&(name),?&(name)?}

#define?LIST_HEAD(name)?
????struct?list_head?name?=?LIST_HEAD_INIT(name)

/*動態(tài)初始化*/
static?inline?void?INIT_LIST_HEAD(struct?list_head?*list)
{
????list->next?=?list;
????list->prev?=?list;
}

?

添加節(jié)點到一個鏈表中，內(nèi)核提供了幾個接口函數(shù)，如list_add()是把一個節(jié)點添加到表頭，list_add_tail()是插入表尾。

?

void?list_add(struct?list_head?*new,?struct?list_head?*head)
list_add_tail(struct?list_head?*new,?struct?list_head?*head)

?

遍歷節(jié)點的接口函數(shù)。

?

#define?list_for_each(pos,?head)?
for?(pos?=?(head)->next;?pos?!=?(head);?pos?=?pos->next)

?

這個宏只是遍歷一個一個節(jié)點的當前位置，那么如何獲取節(jié)點本身的數(shù)據(jù)結(jié)構(gòu)呢？這里還需要使用list_entry()宏。

?

#define?list_entry(ptr,?type,?member)?
????container_of(ptr,?type,?member)
//container_of()宏的定義在kernel.h頭文件中。
#define?container_of(ptr,?type,?member)?({????????????
????const?typeof(?((type?*)0)->member?)?*__mptr?=?(ptr);????
????(type?*)(?(char?*)__mptr?-?offsetof(type,member)?);})

#define?offsetof(TYPE,?MEMBER)?((size_t)?&((TYPE?*)0)->MEMBER)

?

其中offsetof()宏是通過把0地址轉(zhuǎn)換為type類型的指針，然后去獲取該結(jié)構(gòu)體中member成員的指針，也就是獲取了member在type結(jié)構(gòu)體中的偏移量。最后用指針ptr減去offset，就得到type結(jié)構(gòu)體的真實地址了。對linux內(nèi)核中container_of()宏的理解?

下面是遍歷鏈表的一個例子。

?

static?ssize_t?class_osdblk_list(struct?class?*c,
????????????????struct?class_attribute?*attr,
????????????????char?*data)
{
????int?n?=?0;
????struct?list_head?*tmp;

????list_for_each(tmp,?&osdblkdev_list)?{
????????struct?osdblk_device?*osdev;

????????osdev?=?list_entry(tmp,?struct?osdblk_device,?node);

????????n?+=?sprintf(data+n,?"%d?%d?%llu?%llu?%s
",
????????????osdev->id,
????????????osdev->major,
????????????osdev->obj.partition,
????????????osdev->obj.id,
????????????osdev->osd_path);
????}
????return?n;
}

?

紅黑樹

紅黑樹（Red Black Tree）被廣泛應用在內(nèi)核的內(nèi)存管理和進程調(diào)度中，用于將排序的元素組織到樹中。紅黑樹被廣泛應用在計算機科學的各個領域中，它在速度和實現(xiàn)復雜度之間提供一個很好的平衡。

紅黑樹是具有以下特征的二叉樹：

每個節(jié)點或紅或黑。

每個葉節(jié)點是黑色的。

如果結(jié)點都是紅色，那么兩個子結(jié)點都是黑色。

從一個內(nèi)部結(jié)點到葉結(jié)點的簡單路徑上，對所有葉節(jié)點來說，黑色結(jié)點的數(shù)目都是相同的。

紅黑樹的一個優(yōu)點是，所有重要的操作（例如插入、刪除、搜索）都可以在O(log n)時間內(nèi)完成，n為樹中元素的數(shù)目。

經(jīng)典的算法教科書都會講解紅黑樹的實現(xiàn)，這里只是列出一個內(nèi)核中使用紅黑樹的例子，供讀者在實際的驅(qū)動和內(nèi)核編程中參考。這個例子可以在內(nèi)核代碼的documentation/Rbtree.txt文件中找到。

?

#include?
#include?
#include?
#include?
#include?
#include?
#include?

MODULE_AUTHOR("figo.zhang");
MODULE_DESCRIPTION("?");
MODULE_LICENSE("GPL");

??struct?mytype?{?
?????struct?rb_node?node;
?????int?key;?
};

/*紅黑樹根節(jié)點*/
?struct?rb_root?mytree?=?RB_ROOT;
/*根據(jù)key來查找節(jié)點*/
struct?mytype?*my_search(struct?rb_root?*root,?int?new)
??{
?????struct?rb_node?*node?=?root->rb_node;

?????while?(node)?{
??????????struct?mytype?*data?=?container_of(node,?struct?mytype,?node);

??????????if?(data->key?>?new)
???????????????node?=?node->rb_left;
??????????else?if?(data->key?rb_right;
??????????else
???????????????return?data;
?????}
?????return?NULL;
??}

/*插入一個元素到紅黑樹中*/
??int?my_insert(struct?rb_root?*root,?struct?mytype?*data)
??{
?????struct?rb_node?**new?=?&(root->rb_node),?*parent=NULL;

?????/*?尋找可以添加新節(jié)點的地方?*/
?????while?(*new)?{
??????????struct?mytype?*this?=?container_of(*new,?struct?mytype,?node);

??????????parent?=?*new;
??????????if?(this->key?>?data->key)
???????????????new?=?&((*new)->rb_left);
??????????else?if?(this->key?key)?{
???????????????new?=?&((*new)->rb_right);
??????????}?else
???????????????return?-1;
?????}

?????/*?添加一個新節(jié)點?*/
?????rb_link_node(&data->node,?parent,?new);
?????rb_insert_color(&data->node,?root);

?????return?0;
??}

static?int?__init?my_init(void)
{
?????int?i;
?????struct?mytype?*data;
?????struct?rb_node?*node;

?????/*插入元素*/
?????for?(i?=0;?i?key?=?i;
??????????my_insert(&mytree,?data);
?????}

?????/*遍歷紅黑樹，打印所有節(jié)點的key值*/
??????for?(node?=?rb_first(&mytree);?node;?node?=?rb_next(node))?
??????????printk("key=%d
",?rb_entry(node,?struct?mytype,?node)->key);

?????return?0;
}

static?void?__exit?my_exit(void)
{
?????struct?mytype?*data;
?????struct?rb_node?*node;
?????for?(node?=?rb_first(&mytree);?node;?node?=?rb_next(node))?{
??????????data?=?rb_entry(node,?struct?mytype,?node);
??????????if?(data)?{
????????????????rb_erase(&data->node,?&mytree);
????????????????kfree(data);
??????????}
?????}
}
module_init(my_init);
module_exit(my_exit);

?

mytree是紅黑樹的根節(jié)點，my_insert()實現(xiàn)插入一個元素到紅黑樹中，my_search()根據(jù)key來查找節(jié)點。內(nèi)核大量使用紅黑樹，如虛擬地址空間VMA的管理。

無鎖環(huán)形緩沖區(qū)

生產(chǎn)者和消費者模型是計算機編程中最常見的一種模型。生產(chǎn)者產(chǎn)生數(shù)據(jù)，而消費者消耗數(shù)據(jù)，如一個網(wǎng)絡設備，硬件設備接收網(wǎng)絡包，然后應用程序讀取網(wǎng)絡包。

環(huán)形緩沖區(qū)是實現(xiàn)生產(chǎn)者和消費者模型的經(jīng)典算法。環(huán)形緩沖區(qū)通常有一個讀指針和一個寫指針。讀指針指向環(huán)形緩沖區(qū)中可讀的數(shù)據(jù)，寫指針指向環(huán)形緩沖區(qū)可寫的數(shù)據(jù)。通過移動讀指針和寫指針實現(xiàn)緩沖區(qū)數(shù)據(jù)的讀取和寫入。

在Linux內(nèi)核中，KFIFO是采用無鎖環(huán)形緩沖區(qū)的實現(xiàn)。FIFO的全稱是“First In First Out”，即先進先出的數(shù)據(jù)結(jié)構(gòu)，它采用環(huán)形緩沖區(qū)的方法來實現(xiàn)，并提供一個無邊界的字節(jié)流服務。

采用環(huán)形緩沖區(qū)的好處是，當一個數(shù)據(jù)元素被消耗之后，其余數(shù)據(jù)元素不需要移動其存儲位置，從而減少復制，提高效率。

（1）創(chuàng)建KFIFO

在使用KFIFO之前需要進行初始化，這里有靜態(tài)初始化和動態(tài)初始化兩種方式。

?

int?kfifo_alloc(fifo,?size,?gfp_mask)

?

該函數(shù)創(chuàng)建并分配一個大小為size的KFIFO環(huán)形緩沖區(qū)。第一個參數(shù)fifo是指向該環(huán)形緩沖區(qū)的struct kfifo數(shù)據(jù)結(jié)構(gòu)；第二個參數(shù)size是指定緩沖區(qū)元素的數(shù)量；第三個參數(shù)gfp_mask表示分配KFIFO元素使用的分配掩碼。

靜態(tài)分配可以使用如下的宏。

?

#define?DEFINE_KFIFO(fifo,?type,?size)
#define?INIT_KFIFO(fifo)

?

（2）入列

把數(shù)據(jù)寫入KFIFO環(huán)形緩沖區(qū)可以使用kfifo_in()函數(shù)接口。

?

int?kfifo_in(fifo,?buf,?n)

?

該函數(shù)把buf指針指向的n個數(shù)據(jù)復制到KFIFO環(huán)形緩沖區(qū)中。第一個參數(shù)fifo指的是KFIFO環(huán)形緩沖區(qū)；第二個參數(shù)buf指向要復制的數(shù)據(jù)的buffer；第三個數(shù)據(jù)是要復制數(shù)據(jù)元素的數(shù)量。

（3）出列

從KFIFO環(huán)形緩沖區(qū)中列出或者摘取數(shù)據(jù)可以使用kfifo_out()函數(shù)接口。

?

#define????kfifo_out(fifo,?buf,?n)

?

該函數(shù)是從fifo指向的環(huán)形緩沖區(qū)中復制n個數(shù)據(jù)元素到buf指向的緩沖區(qū)中。如果KFIFO環(huán)形緩沖區(qū)的數(shù)據(jù)元素小于n個，那么復制出去的數(shù)據(jù)元素小于n個。

（4）獲取緩沖區(qū)大小

KFIFO提供了幾個接口函數(shù)來查詢環(huán)形緩沖區(qū)的狀態(tài)。

?

#define?kfifo_size(fifo)
#define?kfifo_len(fifo)
#define?kfifo_is_empty(fifo)
#define?kfifo_is_full(fifo)

?

kfifo_size()用來獲取環(huán)形緩沖區(qū)的大小，也就是最大可以容納多少個數(shù)據(jù)元素。kfifo_len()用來獲取當前環(huán)形緩沖區(qū)中有多少個有效數(shù)據(jù)元素。kfifo_is_empty()判斷環(huán)形緩沖區(qū)是否為空。kfifo_is_full()判斷環(huán)形緩沖區(qū)是否為滿。

（5）與用戶空間數(shù)據(jù)交互

KFIFO還封裝了兩個函數(shù)與用戶空間數(shù)據(jù)交互。

?

#define????kfifo_from_user(fifo,?from,?len,?copied)
#define????kfifo_to_user(fifo,?to,?len,?copied)

?

kfifo_from_user()是把from指向的用戶空間的len個數(shù)據(jù)元素復制到KFIFO中，最后一個參數(shù)copied表示成功復制了幾個數(shù)據(jù)元素。

kfifo_to_user()則相反，把KFIFO的數(shù)據(jù)元素復制到用戶空間。這兩個宏結(jié)合了copy_to_user()、copy_from_user()以及KFIFO的機制，給驅(qū)動開發(fā)者提供了方便。

審核編輯：劉清