hello 大家好，今天給大家介紹一下linux 內核鏈表的分析，在寫這篇文章前，筆者自己以前也只是停留在應用層面，沒有深究其中的細節，很多也是理解的不是很透徹。寫完此文后，發現對鏈表的理解更加深刻了。很多現代計算機的思想在內核里面都有體現。

?

在?Linux 內核中使用最多的數據結構就是鏈表了，其中就包含了許多高級思想。???比如面向對象、類似C++模板的實現、堆和棧的實現。

1. 鏈表簡介

鏈表是一種常用的組織有序數據的數據結構，它通過指針將一系列數據節點連接成一條數據鏈，是線性表的一種重要實現方式。

優點：相對于數組，鏈表具有更好的動態性，建立鏈表時無需預先知道數據總量，可以隨機分配空間，可以高效的在鏈表中的任意位置實時插入或者刪除數據。

缺點：訪問的順序性和組織鏈的空間損失。

組成：通常鏈表數據結構至少應包括兩個域，數據域和指針域。數據域用于存儲數據，指針域用于建立與下一個節點的聯系。

分類：按照指針域的組成以及各節點的聯系形式分為，單鏈表、雙鏈表、循環鏈表等多種組織形式。

1.1 單鏈表

如下圖，為單鏈表。它的特點是僅有一個指針域指向后繼節點（next）。對單鏈表的遍歷只能從頭至尾順序進行。

1.2 雙鏈表

對比單鏈表，雙鏈表多了一個指針域。分為前驅（prev）和后繼（next）指針。

雙鏈表可以從兩個方向遍歷，這是它區別于單鏈表的地方。如果打亂前驅、后繼的依賴關系，就可以構成"二叉樹"；

如果再讓首節點的前驅指向鏈表尾節點、尾節點的后繼指向首節點就構成了循環鏈表；

如果設計更多的指針域，就可以構成各種復雜的樹狀數據結構。

1.3 循環鏈表

循環鏈表的特點是尾節點的后繼指向首節點。如下圖是雙循環鏈表示意圖，它的特點是從任意一個節點出發，沿兩個方向的任何一個，都能找到鏈表中的任意一個數據。如果去掉前驅指針，就是單循環鏈表。

2. 內核鏈表

在Linux內核中使用了大量的鏈表結構來組織數據，包括設備列表以及各種功能模塊中的數據組織。這些鏈表大多采用在[include/linux/list.h]實現的一個相當精彩的鏈表數據結構。事實上，內核鏈表就是采用雙循環鏈表機制。

內核鏈表有別于傳統鏈表就在節點本身不包含數據域，只包含指針域。故而可以很靈活的拓展數據結構。

2.1 神奇的結構：list_head

要了解內核鏈表，就不得不提 list_head。這個結構很有意思，整個結構沒有數據域，只有兩個指針域。

這個結構本身意義不大，不過在內核鏈表中，起著整個銜接作用，可以說是內核鏈表的核心不為過。

?

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

?

2.2 鏈表初始化

內核提供多種方式來初始化鏈表：宏初始化和接口初始化。

宏初始化

LIST_HEAD_HEAD_INIT 宏 設計的很精妙。這個宏本身不包含任何數據類型，也就是說沒有限定唯一的數據類型，這就使得整個鏈表足夠靈活。是不是有點C++模板的意思？

對于任意給定的結構指針，將【前驅】和【后繼】指針都指向自己，作為鏈表頭指針。

LIST_HEAD 宏 本質就是賦予了 name 于?【struct list_head】 屬性，由于 list_head 本身不包含數據域，所以搭配 LIST_HEAD_HEAD_INIT 宏，就使得整個鏈表上的數據更加靈活。具備通用性。

?

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

?

我們以示例來補充說明，這樣有助于大家輔助理解：

?

//?1.?鏈表節點初始化，前驅和后繼都指向自己（初始化）
struct?list?=?LIST_HEAD(list);

?

前面說了 list_head 只有指針域，沒有數據域，如果只是這樣就沒有什么意義了。所以我們需要創建一個宿主結構，然后再再此結構包含 list 字段，宿主結構，也有其他字段（進程描述符，頁面管理結構等都是采用這種方法創建鏈表的）。假設定義如下：

?

struct?my_data_list?{
????int?data?;
????struct?list_head?list;?/*?list?head?,?這個至關重要，后期遍歷通過container_of?解析my_data_list?地址?*/
};

?

創建一個節點：

?

struct?my_data_list?first_data?=
{?
????.val?=?1,
????/*?這里有點繞，事實上就是將first_data.list?,?前驅和后繼都指向自己進行初始化?*/
????.list?=?LIST_HEAD_INIT(first_data.list),
};

?

這里 list 的 prev 和 next 都指向list 自己了，并且list 屬于 my_data_list 的成員。只需要遍歷到lst 節點就能根據 前面講的 container_of 推導得到其宿主結構的地址，從而訪問val值，如果有其他方法，也可訪問。

分析到這里，應該逐漸明晰，為何list_head 設計很有意思？為什么鏈表本身不包含數據域，卻能衍生出無數數據類型，不受特定的數據類型限制。

2.3 添加節點

內核相應的提供了添加節點的接口：

list_add

list_add 如下，最終調用的是__list_add 函數，根據注釋可知，list_add 是頭部插入，總是在鏈表的頭部插入一個新的節點。

list_add

?

/**
?*?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

?

/*
?*?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;
}

?

我們再以示例補充說明：

首先創建一個鏈表頭：listHead

?

LIST_HEAD(listHead);

?

然后再創建第一個鏈表節點：

?

struct?my_data_list?first_data?=
{?
????.val?=?1,
????.list?=?LIST_HEAD_INIT(first_data.list),
};

?

接著 把這個節點插入到 listHead 后

?

list_add(&frist_data.list,?&listHead);

?

緊接著我們再創建第二個節點：

?

struct?my_data_list?second_data?=
{?
????.val?=?2,
????/*?也可以調用接口?初始化*/
????.list?=?LIST_HEAD_INIT(second_data.list),
};

list_add(&second_data.list,?&listHead);

?

示意圖如下：

以此類推，每次插入一個新節點，都是緊靠著header節點，而之前插入的節點依次排序靠后，那最后一個節點則是第一次插入header后的那個節點。

可以看出：先來的節點靠后，而后來的節點靠前，符合“先進后出，后進先出”。所以此種結構類似于 stack“棧”， 類似于內核stack中的棧頂指針esp， 它都是緊靠著最后push到棧的元素。

list_add_tail

再看內核另外一種插入方式，本質都是調用__lis_add。不同的是，一個是頭部插入，一個是尾部插入。

?

/**
?*?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);
}

?

我們還是以示例輔助說明：

首先創建一個鏈表頭：

?

LIST_HEAD(listHead);

?

然后創建第一個節點

?

struct?my_data_list?first_data?=
{?
????.val?=?1,
????.list?=?LIST_HEAD_INIT(first_data.list),
};

?

插入第一個節點：

?

list_add_tail(&first_data.list,?listHead);

?

緊接著插入第二個節點：

?

struct?my_data_list?second_data?=
{?
????.val?=?2,
????/*?也可以調用接口?初始化*/
????.list?=?LIST_HEAD_INIT(second_data.list),
};

list_add_tail(&second_data.list,?&listHead);

?

示意圖如下：

每次插入的新節點都是緊挨著 header 表尾，而插入的第一個節點排在了第一位，第二個排在了第二位。

先插入的節點排在前面，后插入的節點排在后面，“先進先出，后進后出”（First in First out,FIFO）！這不就是隊列嗎？

總結

由于是雙循環鏈表，看起來尾部插入和頭部插入是一樣的，其實不然。

我們再來對比尾部和頭部插入的區別：

頭部插入，結構是逆序，屬于先進后出，最主要的區別就是頭節點的prev指針指向第一個節點。

尾部插入，結構是順序，屬于FIFO結構，最主要的區別就是頭節點的next指針指向第一個節點。

list_add：頭部插入一個節點

list_add_tail：尾部插入一個節點

2.4 刪除節點

內核同樣定義了刪除節點的接口 list_del

list_del：

?

static?inline?void?list_del(struct?list_head?*entry)
{
????/*?__list_del_entry(entry)?也行*/
?  __list_del(entry->prev,?entry->next);
????
????/*?指向特定的位置，反初始化?*/
?  entry->next?=?LIST_POISON1;
?  entry->prev?=?LIST_POISON2;
}

?

__list_del：這個接口，根據prev/next 刪除其節點，刪除的節點必須是已知的并且 prev 和 next 不為空

?

/*
?*?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_entry：刪除一個節點。

?

/**
?*?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_entry(struct?list_head?*entry)
{
?  __list_del(entry->prev,?entry->next);
}

/**
?*?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(entry);
?INIT_LIST_HEAD(entry);
}

?

利用list_del(struct list_head *entry) 接口就可以刪除鏈表中的任意節點了，需注意，前提條件是這個節點是已知的，既在鏈表中真實存在，切prev，next指針都不為NULL。

被剔除下來的 my_data_list.list，prev、next 指針分別被設為 LIST_POSITION2和LIST_POSITION1兩個特殊值，這樣設置是為了保證不在鏈表中的節點項不可訪問–對LIST_POSITION1和LIST_POSITION2的訪問都將引起頁故障。

與之相對應，list_del_init()函數將節點從鏈表中解下來之后，調用LIST_INIT_HEAD()將節點置為空鏈狀態。

list_del() 和 list_del_init 是外部接口。__list_del() 和 __list_entry() 是內核內部節點。

list_del() 作用是刪除雙鏈表中的一個節點。并將節點的prev和next都指向特定位置，LIST_POSITION1和LIST_POSITION2。

list_del_init() 作用是刪除雙鏈表中的一個節點，并將節點的prev和next都指向自己，回到最開始創建節點前的狀態。

2.5 搬移

內核提供了將原本屬于一個鏈表的節點移動到另一個鏈表的操作，并根據插入到新鏈表的位置分為兩類：頭部搬移和尾部搬移。搬移的本質就是刪除加插入。

頭部搬移

?

/**
?*?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_entry(list);
?  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_entry(list);
?  list_add_tail(list,?head);
}

?

2.6 合并

內核還提供兩組合并操作，將兩條鏈表合并在一起。

當 list1 被掛接到 list2 之后，作為原表頭指針的 list1 的next、prev仍然指向原來的節點，為了避免引起混亂，Linux提供了一個list_splice_init()函數.該函數在將list合并到head鏈表的基礎上，調用INIT_LIST_HEAD(list)將list設置為空鏈。

?

static?inline?void?list_splice(const?struct?list_head?*list,?struct?list_head?*head);
static?inline?void?list_splice_init(struct?list_head?*list,?struct?list_head?*head);
static?inline?void?list_splice_tail(const?struct?list_head?*list,?struct?list_head?*head);
static?inline?void?list_splice_tail_init(struct?list_head?*list,?struct?list_head?*head);

?

示意圖如下：

另外一種方式類似，只不過合并時斷開的位置有所不同

2.7 替換

內核還提供一組替換鏈表節點的操作。list_replace：將新的節點替換到舊的節點上。list_replace_init：將新的節點替換到舊的節點上。同時將舊的節點的prev和next指向自己，反初始化

?

static?inline?void?list_replace(struct?list_head?*old,?struct?list_head?*new);
static?inline?void?list_replace_init(struct?list_head?*old,?struct?list_head?*new);

?

2.8?遍歷操作

內核提供了一組宏進行遍歷操作。經過一系列的增刪減改操作，我們終于到了遍歷的時候。

list_entry 宏

重頭戲來了，遍歷的關鍵就是這個list_entry 宏。本質就是container_of 宏。

具體分析見上一篇文章。這個宏的主要作用就是獲取宿主結構的指針地址。

前文提到，我們是以list 指針為節點組成的一條雙鏈表，遍歷的過程中只能得到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)?
???container_of(ptr,?type,?member)

/*?根據list?倒推?my_list_data*/
list_entry(&my_list_data.list,?typeof(&my_list_data),?list)

?

list_for_each

list_for_each 它實際上是一個for循環，利用傳入的pos作為循環變量，從表頭head開始，逐項向后（next方向）移動pos，直至又回到head

?

/**
?*?list_for_each?-?iterate?over?a?list
?*?@pos:?the?&struct?list_head?to?use?as?a?loop?cursor.
?*?@head:?the?head?for?your?list.
?*/
#define?list_for_each(pos,?head)?
?for?(pos?=?(head)->next;?pos?!=?(head);?pos?=?pos->next)

?

list_for_each_entry

遍歷每一個list,然后獲取其宿主結構地址.

?

/**
?*?list_for_each_entry?-?iterate?over?list?of?given?type
?*?@pos:?the?type?*?to?use?as?a?loop?cursor.
?*?@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_prev

反向遍歷得到list.

?

/**
?*?list_for_each_prev?-?iterate?over?a?list?backwards
?*?@pos:?the?&struct?list_head?to?use?as?a?loop?cursor.
?*?@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_entry_reverse

反向遍歷得到list,然后獲取其宿主結構地址。

?

/**
*?list_for_each_entry_reverse?-?iterate?backwards?over?list?of?given?type.
*?@pos:?the?type?*?to?use?as?a?loop?cursor.
*?@head:?the?head?for?your?list.
*?@member:?the?name?of?the?list_struct?within?the?struct.
*/
#define?list_for_each_entry_reverse(pos,?head,?member)???
???for?(pos?=?list_entry((head)->prev,?typeof(*pos),?member);?
????????&pos->member?!=?(head);??
????????pos?=?list_entry(pos->member.prev,?typeof(*pos),?member))

?

3. 總結

本文詳細分析了 linux 內核 中的雙鏈表結構，以圖文的方式旨在幫助大家理解。

當然還有很多接口限于篇幅沒有介紹，本文只列出了常用了接口，相信只要理解了前面雙鏈表的組成和插入過程，后面的刪除和遍歷就自然而然通了。

　　審核編輯：湯梓紅