當(dāng)前位置：首頁 > 嵌入式培訓(xùn) > 嵌入式學(xué)習(xí) > 講師博文 > 內(nèi)核鏈表
內(nèi)核鏈表
時間：2018-09-26 來源：未知
在Linux內(nèi)核中使用了大量的鏈表結(jié)構(gòu)來組織數(shù)據(jù)，包括設(shè)備列表以及各種功能模塊中的數(shù)據(jù)組織。這些鏈表大多采用在[include/linux/list.h]實現(xiàn)的一個相當(dāng)精彩的鏈表數(shù)據(jù)結(jié)構(gòu)。
很多l(xiāng)inux下的源代碼都會使用這個頭文件，它里面定義了一個結(jié)構(gòu),以及定義了和其相關(guān)的一組函數(shù)，初學(xué)嵌入式的同學(xué)往往會對內(nèi)核鏈表感到一頭霧水， 本文詳細(xì)分析了3.14 內(nèi)核中鏈表結(jié)構(gòu)的實現(xiàn)，并通過實例對鏈表操作接口進(jìn)行了測試。
一、 鏈表數(shù)據(jù)結(jié)構(gòu)簡介
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(鏈表中每一個元素稱為結(jié)點)組成，結(jié)點可以在運(yùn)行時動態(tài)生成。
使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機(jī)內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。鏈表明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項目的方式可能不同于這些數(shù)據(jù)項目在記憶體或磁盤上順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點，但是不允許隨機(jī)存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。鏈表可以在多種編程語言中實現(xiàn)。像Lisp和Scheme這樣的語言的內(nèi)建數(shù)據(jù)類型中就包含了鏈表的存取和操作。程序語言或面向?qū)ο笳Z言，如C,C++和Java依靠易變工具來生成鏈表。
通常鏈表數(shù)據(jù)結(jié)構(gòu)至少應(yīng)包含兩個域：數(shù)據(jù)域和指針域，數(shù)據(jù)域用于存儲數(shù)據(jù)，指針域用于建立與下一個節(jié)點的聯(lián)系。
按照指針域的組織以及各個節(jié)點之間的聯(lián)系形式，鏈表又可以分為單鏈表、雙鏈表、循環(huán)鏈表等多種類型，下面分別給出這幾類常見鏈表類型的示意圖：
1. 單鏈表
圖1 單鏈表
單鏈表是簡單的一類鏈表，它的特點是僅有一個指針域指向后繼節(jié)點(next)，因此，對單鏈表的遍歷只能從頭至尾(通常是NULL空指針)順序進(jìn)行。
2. 雙鏈表
圖2 雙鏈表
通過設(shè)計前驅(qū)和后繼兩個指針域，雙鏈表可以從兩個方向遍歷，這是它區(qū)別 于單鏈表的地方。如果打亂前驅(qū)、后繼的依賴關(guān)系，就可以構(gòu)成"二叉樹";如果再讓首節(jié)點的前驅(qū)指向鏈表尾節(jié)點、尾節(jié)點的后繼指向首節(jié)點(如圖2中虛線部 分)，就構(gòu)成了循環(huán)鏈表;如果設(shè)計更多的指針域，就可以構(gòu)成各種復(fù)雜的樹狀數(shù)據(jù)結(jié)構(gòu)。
3. 循環(huán)鏈表
循環(huán)鏈表的特點是尾節(jié)點的后繼指向首節(jié)點。前面已經(jīng)給出了雙循環(huán)鏈表的示意圖，它的特點是從任意一個節(jié)點出發(fā)，沿兩個方向的任何一個，都能找到鏈表中的任意一個數(shù)據(jù)。如果去掉前驅(qū)指針，就是單循環(huán)鏈表。
二、 Linux 3.14內(nèi)核鏈表數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)
鏈表數(shù)據(jù)結(jié)構(gòu)的定義很簡單(定義文件在linux-3.14-fs4412\include\linux\Types.h中)：
和第一節(jié)介紹的雙鏈表結(jié)構(gòu)模型不同，這里的list_head沒有數(shù)據(jù)域。在Linux內(nèi)核鏈表中，不是在鏈表結(jié)構(gòu)中包含數(shù)據(jù)，而是在數(shù)據(jù)結(jié)構(gòu)中包含鏈表節(jié)點。list_head結(jié)構(gòu)包含兩個指向list_head結(jié)構(gòu)的指針prev和next，由此可見，內(nèi)核的鏈表具備雙鏈表功能，實際上，通常它都組織成雙循環(huán)鏈表。
在數(shù)據(jù)結(jié)構(gòu)課本中，鏈表的經(jīng)典定義方式通常是這樣的(以單鏈表為例)：
struct list_node {
struct list_node *next;
ElemType data;
};
在Linux內(nèi)核鏈表中，需要用鏈表組織起來的數(shù)據(jù)通常會包含一個 struct list_head成員，
struct list_node
{
struct list_head list;
ElemType data;
};
從下圖中我們可以看到，這種通用的鏈表結(jié)構(gòu)避免了為每個數(shù)據(jù)項類型定義自己的鏈表的麻煩。
圖3 內(nèi)核鏈表鏈表示意圖
三、 鏈表操作接口
1. 聲明和初始化
實際上Linux只定義了鏈表節(jié)點，并沒有專門定義鏈表頭，那么一個鏈表結(jié)構(gòu)是如何建立起來的呢?讓我們來看看LIST_HEAD(和LIST_HEAD_INIT這2個宏：
當(dāng)我們用LIST_HEAD(my_list)聲明一個名為t的鏈表頭時，它的next、prev指針都初始化為指向自己，這樣，我們就有了一個空鏈表.
Linux用頭指針的next是否指向自己來判斷鏈表是否為空：
2. 插入/刪除/合并
a) 插入
對鏈表的插入操作有兩種：在表頭插入和在表尾插入。Linux為此提供了兩個接口：
因為Linux鏈表是循環(huán)表，且表頭的next、prev分別指向鏈表中的第一個和末一個節(jié)點，所以，list_add和list_add_tail的區(qū)別并不大，實際上，Linux分別用
__list_add(new, head, head->next);
和
__list_add(new, head->prev, head);
來實現(xiàn)兩個接口，可見，在表頭插入是插入在head之后，而在表尾插入是插入在head->prev之后。
__list_add的實現(xiàn)如下：
假設(shè)有一個新list_node
結(jié)構(gòu)變量new_list_node需要添加到my_list鏈表頭，我們應(yīng)當(dāng)這樣操作：
list_add(&new_list_node.list, &my_list);
從這里我們看出，my_list鏈表中記錄的并不是new_list_node的地址，而是其中的list元素的地址。如何通過鏈表訪問到new_list_node呢?下面會有詳細(xì)介紹。
b) 刪除
當(dāng)我們需要刪除my_list鏈表中添加的new_sockopt項時，我們這么操作：
list_del(&new_list_node.list);
被剔除下來的new_list_node.list，prev、next指
針分別被設(shè)為LIST_POSITION2和LIST_POSITION1兩個特殊值，這樣設(shè)置是為了保證不在鏈表中的節(jié)點項不可訪問--對
LIST_POSITION1和LIST_POSITION2的訪問都將引起頁故障。與之相對應(yīng)，list_del_init()函數(shù)將節(jié)點從鏈表中解下
來之后，調(diào)用LIST_INIT_HEAD()將節(jié)點置為空鏈狀態(tài)。
c) 搬移
Linux提供了將原本屬于一個鏈表的節(jié)點移動到另一個鏈表的操作，并根據(jù)插入到新鏈表的位置分為兩類：
例如list_move(&new_list_node.list,&my_list)會把new_list_node從它所在的鏈表上刪除，并將其再鏈入my_list的表頭。
d) 合并
除了針對節(jié)點的插入、刪除操作，Linux鏈表還提供了整個鏈表的插入功能：
假設(shè)當(dāng)前有兩個鏈表，表頭分別是list1和list2(都是 struct list_head變量)，當(dāng)調(diào)用list_splice(&list1,&list2)時，只要list1非空，list1鏈表的內(nèi)容 將被掛接在list2鏈表上，位于list2和list2.next(原list2表的第一個節(jié)點)之間。新list2鏈表將以原list1表的第一個節(jié) 點為首節(jié)點，而尾節(jié)點不變。
當(dāng)list1被掛接到list2之后，作為原表頭指針的list1的next、prev仍然指向原來的節(jié)點，為了避免引起混亂，Linux提供了一個list_splice_init()函數(shù)：
static inline void list_splice_init(struct list_head *list, struct list_head *head);
該函數(shù)在將list合并到head鏈表的基礎(chǔ)上，調(diào)用INIT_LIST_HEAD(list)將list設(shè)置為空鏈。
3. 遍歷
遍歷是鏈表經(jīng)常的操作之一，為了方便核心應(yīng)用遍歷鏈表，Linux鏈表將遍歷操作抽象成幾個宏。在介紹遍歷宏之前，我們先看看如何從鏈表中訪問到我們真正需要的數(shù)據(jù)項。
a) 由鏈表節(jié)點到數(shù)據(jù)項變量
我們知道，Linux鏈表中僅保存了數(shù)據(jù)項結(jié)構(gòu)中l(wèi)ist_head成 員變量的地址，那么我們?nèi)绾瓮ㄟ^這個list_head成員訪問到作為它的所有者的節(jié)點數(shù)據(jù)呢?Linux為此提供了一個 list_entry(ptr,type,member)宏，其中ptr是指向該數(shù)據(jù)中l(wèi)ist_head成員的指針，也就是存儲在鏈表中的地址值，type是數(shù)據(jù)項的類型，member則是數(shù)據(jù)項類型定義中l(wèi)ist_head成員的變量名，例如，我們要訪問my_list鏈表中首個 list_node變量，則如此調(diào)用：
list_entry(my_list->next, struct list_node, list);
這里"list"正是nf_sockopt_ops結(jié)構(gòu)中定義的用于鏈表操作的節(jié)點成員變量名。
list_entry的使用相當(dāng)簡單，相比之下，它的實現(xiàn)則有一些難懂：
container_of宏定義在[include/linux/kernel.h]中
offsetof宏定義在[include/linux/stddef.h]中：
size_t終定義為unsigned int(i386)。
這里使用的是一個利用編譯器技術(shù)的小技巧，即先求得結(jié)構(gòu)成員在與結(jié)構(gòu)中的偏移量，然后根據(jù)成員變量的地址反過來得出屬主結(jié)構(gòu)變量的地址。
container_of()和offsetof()并不僅用于鏈表操 作，這里有趣的地方是((type *)0)->member，它將0地址強(qiáng)制"轉(zhuǎn)換"為type結(jié)構(gòu)的指針，再訪問到type結(jié)構(gòu)中的member成員。在container_of 宏中，它用來給typeof()提供參數(shù)(typeof()是gcc的擴(kuò)展，和sizeof()類似)，以獲得member成員的數(shù)據(jù)類型;在 offsetof()中，這個member成員的地址實際上就是type數(shù)據(jù)結(jié)構(gòu)中member成員相對于結(jié)構(gòu)變量的偏移量。
b) 遍歷宏
以下是一個遍歷內(nèi)核鏈表節(jié)點的實例
……
struct list_head *i;
……
list_for_each(i, &nf_sockopts) {
struct nf_sockopt_ops *ops = (struct nf_sockopt_ops *)i;
……
}
……
函數(shù)首先定義一個(struct list_head *)指針變量i，然后調(diào)用list_for_each(i,&my_list)進(jìn)行遍歷。在[include/linux/list.h]中，list_for_each()宏是這么定義的：
它實際上是一個for循環(huán)，利用傳入的pos作為循環(huán)變量，從表頭head開始，逐項向后(next方向)移動pos，直至又回到head(prefetch()可以不考慮，用于預(yù)取以提高遍歷速度)。
大多數(shù)情況下，遍歷鏈表的時候都需要獲得鏈表節(jié)點數(shù)據(jù)項，也就是說list_for_each()和list_entry()總是同時使用。對此Linux給出了一個list_for_each_entry()宏：
#define list_for_each_entry(pos, head, member)
與list_for_each()不同，這里的pos是數(shù)據(jù)項結(jié)構(gòu)指針類型，而不是(struct list_head *)。
某些應(yīng)用需要反向遍歷鏈表，Linux提供了 list_for_each_prev()和list_for_each_entry_reverse()來完成這一操作，使用方法和上面介紹的 list_for_each()、list_for_each_entry()完全相同。
如果遍歷不是從鏈表頭開始，而是從已知的某個節(jié)點pos開始，則可以使 用list_for_each_entry_continue(pos,head,member)。有時還會出現(xiàn)這種需求，即經(jīng)過一系列計算后，如果 pos有值，則從pos開始遍歷，如果沒有，則從鏈表頭開始，為此，Linux專門提供了一個 list_prepare_entry(pos,head,member)宏，將它的返回值作為 list_for_each_entry_continue()的pos參數(shù)，就可以滿足這一要求。
4. 安全性考慮
在并發(fā)執(zhí)行的環(huán)境下，鏈表操作通常都應(yīng)該考慮同步安全性問題，為了方便，Linux將這一操作留給應(yīng)用自己處理。Linux鏈表自己考慮的安全性主要有兩個方面：
a) list_empty()判斷
基本的list_empty()僅以頭指針的next是否指向自己來判 斷鏈表是否為空，Linux鏈表另行提供了一個list_empty_careful()宏，它同時判斷頭指針的next和prev，僅當(dāng)兩者都指向自己 時才返回真。這主要是為了應(yīng)付另一個cpu正在處理同一個鏈表而造成next、prev不一致的情況。但代碼注釋也承認(rèn)，這一安全保障能力有限：除非其他 cpu的鏈表操作只有l(wèi)ist_del_init()，否則仍然不能保證安全，也就是說，還是需要加鎖保護(hù)。
b) 遍歷時節(jié)點刪除
前面介紹了用于鏈表遍歷的幾個宏，它們都是通過移動pos指針來達(dá)到遍 歷的目的。但如果遍歷的操作中包含刪除pos指針?biāo)赶虻墓?jié)點，pos指針的移動就會被中斷，因為list_del(pos)將把pos的next、 prev置成LIST_POSITION2和LIST_POSITION1的特殊值。
當(dāng)然，調(diào)用者完全可以自己緩存next指針使遍歷操作能夠連貫起來，但 為了編程的一致性，Linux鏈表仍然提供了兩個對應(yīng)于基本遍歷操作的"_safe"接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)，它們要求調(diào)用者另外提供一個與pos同類型的指針n，在for循環(huán)中暫存pos下一個節(jié)點的地址，避免因pos節(jié)點被釋放而造成的斷鏈。
四、實例
以下實例為方便應(yīng)用程序測試，直接將內(nèi)核的list.h文件拷貝出來，將要測試的宏拷貝出來，刪除不必要的信息。
//list.h
#ifndef __LIST_H
#define __LIST_H
#if defined(WIN32)
#define INLINE __inline
#else
#define INLINE inline
#endif
/* This file is from Linux Kernel (include/linux/list.h)
* and modified by simply removing hardware prefetching of list items.
* Here by copyright, credits attributed to where ever they belong.
* Get from //isis.poly.edu/kulesh/stuff/src/klist/
*/
/*
* Simple doubly linked list implementation.
*
* Some of the internal functions ("__xxx") are useful when
* manipulating whole lists rather than single entries, as
* sometimes we already know the next/prev entries and we can
* generate better code by using them directly rather than
* using the generic single-entry routines.
*/
struct list_head{
struct list_head*next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
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;
}
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static INLINE void list_add(struct list_head*new,struct list_head*head)
{
__list_add(new, head, head->next);
}
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static INLINE void list_add_tail(struct list_head*new,struct list_head*head)
{
__list_add(new, head->prev, head);
}
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static INLINE void __list_del(struct list_head*prev,struct list_head*next)
{
next->prev= prev;
prev->next= next;
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty on entry does not return true after this, the entry is in an undefined state.
*/
static INLINE void list_del(struct list_head*entry)
{
__list_del(entry->prev, entry->next);
entry->next= (void*)0;
entry->prev= (void*)0;
}
/**
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
static INLINE void list_del_init(struct list_head*entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static INLINE void list_move(struct list_head*list,struct list_head*head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
/**
* list_move_tail - delete from one list and add as another's tail
* @list: the entry to move
* @head: the head that will follow our entry
*/
static INLINE void list_move_tail(struct list_head*list,
struct list_head*head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
static INLINE int list_empty(struct list_head*head)
{
return head->next== head;
}
static INLINE void __list_splice(struct list_head*list,
struct list_head*head)
{
struct list_head*first= list->next;
struct list_head*last= list->prev;
struct list_head*at= head->next;
first->prev= head;
head->next= first;
last->next= at;
at->prev= last;
}
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static INLINE void list_splice(struct list_head*list,struct list_head*head)
{
if(!list_empty(list))
__list_splice(list, head);
}
/**
* list_splice_init - join two lists and reinitialise the emptied list.
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* The list at @list is reinitialised
*/
static INLINE void list_splice_init(struct list_head*list,
struct list_head*head)
{
if(!list_empty(list)) {
__list_splice(list, head);
INIT_LIST_HEAD(list);
}
}
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); \
pos = pos->next)
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); \
pos = pos->prev)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop counter.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop counter.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop counter.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
#endif
#include
#include "list.h"
typedef struct test_struct
{
int test_a;
char test_b;
struct list_head list;
}TEST_LIST;
int main(int argc, char *argv[])
{
int i;
TEST_LIST *p = NULL;
struct list_head *ptr = NULL;
LIST_HEAD(t);
for (i = 0; i < 10; i++) {
p = (TEST_LIST *)malloc(sizeof(TEST_LIST));
p->test_a = i;
p->test_b = i + 1;
list_add(&(p->list), &t);
}
list_for_each(ptr, &t) {
p = list_entry(ptr, TEST_LIST, list);
printf("%d %d/n", p->test_a, p->test_b);
}
return 0;
}
該實例我們實現(xiàn)了鏈表的初始化、節(jié)點插入、鏈表遍歷等操作。
更多鏈表技術(shù)文章：
嵌入式linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)之單向鏈表
嵌入式linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)之雙向鏈表
