Linux教程網 >> Linux綜合 >> Linux內核 >> Linux內核部件分析

Linux內核部件分析

日期：2017/2/28 16:05:30 编辑：Linux內核

在linux內核中，有一種通用的雙向循環鏈表，構成了各種隊列的基礎。鏈表的結構定義和相關函數均在include/linux/list.h中，下面就來全面的介紹這一鏈表的各種API。

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

這是鏈表的元素結構。因為是循環鏈表，表頭和表中節點都是這一結構。有prev和next兩個指針，分別指向鏈表中前一節點和後一節點。

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}

在初始化的時候，鏈表頭的prev和next都是指向自身的。

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;
}
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}

雙向循環鏈表的實現，很少有例外情況，基本都可以用公共的方式來處理。這裡無論是加第一個節點，還是其它的節點，使用的方法都一樣。

另外，鏈表API實現時大致都是分為兩層：一層外部的，如list_add、list_add_tail，用來消除一些例外情況，調用內部實現；一層是內部的，函數名前會加雙下劃線，如__list_add，往往是幾個操作公共的部分，或者排除例外後的實現。

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
static inline void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}

list_del是鏈表中節點的刪除。之所以在調用__list_del後又把被刪除元素的next、prev指向特殊的LIST_POSITION1和LIST_POSITION2，是為了調試未定義的指針。

list_del_init則是刪除節點後，隨即把節點中指針再次初始化，這種刪除方式更為實用。

static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
static inline void list_replace_init(struct list_head *old,
struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old);
}

list_replace是將鏈表中一個節點old，替換為另一個節點new。從實現來看，即使old所在地鏈表只有old一個節點，new也可以成功替換，這就是雙向循環鏈表可怕的通用之處。

list_replace_init將被替換的old隨即又初始化。

static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
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_move的作用是把list節點從原鏈表中去除，並加入新的鏈表head中。

list_move_tail只在加入新鏈表時與list_move有所不同，list_move是加到head之後的鏈表頭部，而list_move_tail是加到head之前的鏈表尾部。

static inline int list_is_last(const struct list_head *list,
const struct list_head *head)
{
return list->next == head;
}

list_is_last 判斷list是否處於head鏈表的尾部。

static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
static inline int list_empty_careful(const struct list_head *head)
{
struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}

list_empty 判斷head鏈表是否為空，為空的意思就是只有一個鏈表頭head。

list_empty_careful 同樣是判斷head鏈表是否為空，只是檢查更為嚴格。

static inline int list_is_singular(const struct list_head *head)
{
return !list_empty(head) && (head->next == head->prev);
}

list_is_singular 判斷head中是否只有一個節點，即除鏈表頭head外只有一個節點。

static inline void __list_cut_position(struct list_head *list,
struct list_head *head, struct list_head *entry)
{
struct list_head *new_first = entry->next;
list->next = head->next;
list->next->prev = list;
list->prev = entry;
entry->next = list;
head->next = new_first;
new_first->prev = head;
}
static inline void list_cut_position(struct list_head *list,
struct list_head *head, struct list_head *entry)
{
if (list_empty(head))
return;
if (list_is_singular(head) &&
(head->next != entry && head != entry))
return;
if (entry == head)
INIT_LIST_HEAD(list);
else
__list_cut_position(list, head, entry);
}

list_cut_position 用於把head鏈表分為兩個部分。從head->next一直到entry被從head鏈表中刪除，加入新的鏈表list。新鏈表list應該是空的，或者原來的節點都可以被忽略掉。可以看到，list_cut_position中排除了一些意外情況，保證調用__list_cut_position時至少有一個元素會被加入新鏈表。

static inline void __list_splice(const struct list_head *list,
struct list_head *prev,
struct list_head *next)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
first->prev = prev;
prev->next = first;
last->next = next;
next->prev = last;
}
static inline void list_splice(const struct list_head *list,
struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head, head->next);
}
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head->prev, head);
}

list_splice的功能和list_cut_position正相反，它合並兩個鏈表。list_splice把list鏈表中的節點加入head鏈表中。在實際操作之前，要先判斷list鏈表是否為空。它保證調用__list_splice時list鏈表中至少有一個節點可以被合並到head鏈表中。

list_splice_tail只是在合並鏈表時插入的位置不同。list_splice是把原來list鏈表中的節點全加到head鏈表的頭部，而list_splice_tail則是把原來list鏈表中的節點全加到head鏈表的尾部。

static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head, head->next);
INIT_LIST_HEAD(list);
}
}
static inline void list_splice_tail_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head->prev, head);
INIT_LIST_HEAD(list);
}
}

list_splice_init 除了完成list_splice的功能，還把變空了的list鏈表頭重新初始化。

list_splice_tail_init 除了完成list_splice_tail的功能，還吧變空了得list鏈表頭重新初始化。

list操作的API大致如以上所列，包括鏈表節點添加與刪除、節點從一個鏈表轉移到另一個鏈表、鏈表中一個節點被替換為另一個節點、鏈表的合並與拆分、查看鏈表當前是否為空或者只有一個節點。接下來，是操作鏈表遍歷時的一些宏，我們也簡單介紹一下。

#define list_entry(ptr, type, member) \
container_of(ptr, type, member)

list_entry主要用於從list節點查找其內嵌在的結構。比如定義一個結構struct A{ struct list_head list; }; 如果知道結構中鏈表的地址ptrList，就可以從ptrList進而獲取整個結構的地址(即整個結構的指針) struct A *ptrA = list_entry(ptrList, struct A, list);

這種地址翻譯的技巧是linux的拿手好戲，container_of隨處可見，只是鏈表節點多被封裝在更復雜的結構中，使用專門的list_entry定義也是為了使用方便。