電子發(fā)燒友App
hello 大家好，今天給大家介紹一下linux 內(nèi)核鏈表的分析，在寫這篇文章前，筆者自己以前也只是停留在應用層面，沒有深究其中的細節(jié)，很多也是理解的不是很透徹。寫完此文后，發(fā)現(xiàn)對鏈表的理解更加深刻了。很多現(xiàn)代計算機的思想在內(nèi)核里面都有體現(xiàn)。
?
在?Linux 內(nèi)核中使用最多的數(shù)據(jù)結構就是鏈表了，其中就包含了許多高級思想。???比如面向?qū)ο蟆㈩愃?a href="http://www.ttokpm.com/tags/C++/" target="_blank">C++模板的實現(xiàn)、堆和棧的實現(xiàn)。
1. 鏈表簡介
鏈表是一種常用的組織有序數(shù)據(jù)的數(shù)據(jù)結構，它通過指針將一系列數(shù)據(jù)節(jié)點連接成一條數(shù)據(jù)鏈，是線性表的一種重要實現(xiàn)方式。
優(yōu)點：相對于數(shù)組，鏈表具有更好的動態(tài)性，建立鏈表時無需預先知道數(shù)據(jù)總量，可以隨機分配空間，可以高效的在鏈表中的任意位置實時插入或者刪除數(shù)據(jù)。
缺點：訪問的順序性和組織鏈的空間損失。
組成：通常鏈表數(shù)據(jù)結構至少應包括兩個域，數(shù)據(jù)域和指針域。數(shù)據(jù)域用于存儲數(shù)據(jù)，指針域用于建立與下一個節(jié)點的聯(lián)系。
分類：按照指針域的組成以及各節(jié)點的聯(lián)系形式分為，單鏈表、雙鏈表、循環(huán)鏈表等多種組織形式。
1.1 單鏈表
如下圖，為單鏈表。它的特點是僅有一個指針域指向后繼節(jié)點（next）。對單鏈表的遍歷只能從頭至尾順序進行。
1.2 雙鏈表
對比單鏈表，雙鏈表多了一個指針域。分為前驅(qū)（prev）和后繼（next）指針。
雙鏈表可以從兩個方向遍歷，這是它區(qū)別于單鏈表的地方。如果打亂前驅(qū)、后繼的依賴關系，就可以構成"二叉樹"；
如果再讓首節(jié)點的前驅(qū)指向鏈表尾節(jié)點、尾節(jié)點的后繼指向首節(jié)點就構成了循環(huán)鏈表；
如果設計更多的指針域，就可以構成各種復雜的樹狀數(shù)據(jù)結構。
1.3 循環(huán)鏈表
循環(huán)鏈表的特點是尾節(jié)點的后繼指向首節(jié)點。如下圖是雙循環(huán)鏈表示意圖，它的特點是從任意一個節(jié)點出發(fā)，沿兩個方向的任何一個，都能找到鏈表中的任意一個數(shù)據(jù)。如果去掉前驅(qū)指針，就是單循環(huán)鏈表。
2. 內(nèi)核鏈表
在Linux內(nèi)核中使用了大量的鏈表結構來組織數(shù)據(jù)，包括設備列表以及各種功能模塊中的數(shù)據(jù)組織。這些鏈表大多采用在[include/linux/list.h]實現(xiàn)的一個相當精彩的鏈表數(shù)據(jù)結構。事實上，內(nèi)核鏈表就是采用雙循環(huán)鏈表機制。
內(nèi)核鏈表有別于傳統(tǒng)鏈表就在節(jié)點本身不包含數(shù)據(jù)域，只包含指針域。故而可以很靈活的拓展數(shù)據(jù)結構。
2.1 神奇的結構：list_head
要了解內(nèi)核鏈表，就不得不提 list_head。這個結構很有意思，整個結構沒有數(shù)據(jù)域，只有兩個指針域。
這個結構本身意義不大，不過在內(nèi)核鏈表中，起著整個銜接作用，可以說是內(nèi)核鏈表的核心不為過。
?
struct?list_head?{
???struct?list_head?*next,?*prev;
};
?
2.2 鏈表初始化
內(nèi)核提供多種方式來初始化鏈表：宏初始化和接口初始化。
宏初始化
LIST_HEAD_HEAD_INIT 宏 設計的很精妙。這個宏本身不包含任何數(shù)據(jù)類型，也就是說沒有限定唯一的數(shù)據(jù)類型，這就使得整個鏈表足夠靈活。是不是有點C++模板的意思？
對于任意給定的結構指針，將【前驅(qū)】和【后繼】指針都指向自己，作為鏈表頭指針。
LIST_HEAD 宏 本質(zhì)就是賦予了 name 于?【struct list_head】 屬性，由于 list_head 本身不包含數(shù)據(jù)域，所以搭配 LIST_HEAD_HEAD_INIT 宏，就使得整個鏈表上的數(shù)據(jù)更加靈活。具備通用性。
?
#define?LIST_HEAD_INIT(name)?{?&(name),?&(name)?}
#define?LIST_HEAD(name)?
? struct?list_head?name?=?LIST_HEAD_INIT(name)
?
接口初始化
接口操作就比較直接明了，基本上和宏實現(xiàn)的意圖一樣。直接將鏈表頭指針的前驅(qū)和后繼都指向自己
?
static?inline?void?INIT_LIST_HEAD(struct?list_head?*list) { ? list->next?=?list; ? list->prev?=?list; }
?
我們以示例來補充說明，這樣有助于大家輔助理解：
?
//?1.?鏈表節(jié)點初始化，前驅(qū)和后繼都指向自己（初始化） struct?list?=?LIST_HEAD(list);
?
前面說了 list_head 只有指針域，沒有數(shù)據(jù)域，如果只是這樣就沒有什么意義了。所以我們需要創(chuàng)建一個宿主結構，然后再再此結構包含 list 字段，宿主結構，也有其他字段（進程描述符，頁面管理結構等都是采用這種方法創(chuàng)建鏈表的）。假設定義如下：
?
struct?my_data_list?{
????int?data?;
????struct?list_head?list;?/*?list?head?,?這個至關重要，后期遍歷通過container_of?解析my_data_list?地址?*/
};
?
創(chuàng)建一個節(jié)點：
?
struct?my_data_list?first_data?= {? ????.val?=?1, ????/*?這里有點繞，事實上就是將first_data.list?,?前驅(qū)和后繼都指向自己進行初始化?*/ ????.list?=?LIST_HEAD_INIT(first_data.list), };
?
這里 list 的 prev 和 next 都指向list 自己了，并且list 屬于 my_data_list 的成員。只需要遍歷到lst 節(jié)點就能根據(jù) 前面講的 container_of 推導得到其宿主結構的地址，從而訪問val值，如果有其他方法，也可訪問。
分析到這里，應該逐漸明晰，為何list_head 設計很有意思？為什么鏈表本身不包含數(shù)據(jù)域，卻能衍生出無數(shù)數(shù)據(jù)類型，不受特定的數(shù)據(jù)類型限制。
2.3 添加節(jié)點
內(nèi)核相應的提供了添加節(jié)點的接口：
list_add
list_add 如下，最終調(diào)用的是__list_add 函數(shù)，根據(jù)注釋可知，list_add 是頭部插入，總是在鏈表的頭部插入一個新的節(jié)點。
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;
}
?
我們再以示例補充說明：
首先創(chuàng)建一個鏈表頭：listHead
?
LIST_HEAD(listHead);
?
然后再創(chuàng)建第一個鏈表節(jié)點：
?
struct?my_data_list?first_data?=
{?
????.val?=?1,
????.list?=?LIST_HEAD_INIT(first_data.list),
};
?
接著 把這個節(jié)點插入到 listHead 后
?
list_add(&frist_data.list,?&listHead);
?
緊接著我們再創(chuàng)建第二個節(jié)點：
?
struct?my_data_list?second_data?=
{?
????.val?=?2,
????/*?也可以調(diào)用接口?初始化*/
????.list?=?LIST_HEAD_INIT(second_data.list),
};
list_add(&second_data.list,?&listHead);
?
示意圖如下：
以此類推，每次插入一個新節(jié)點，都是緊靠著header節(jié)點，而之前插入的節(jié)點依次排序靠后，那最后一個節(jié)點則是第一次插入header后的那個節(jié)點。
可以看出：先來的節(jié)點靠后，而后來的節(jié)點靠前，符合“先進后出，后進先出”。所以此種結構類似于 stack“棧”， 類似于內(nèi)核stack中的棧頂指針esp， 它都是緊靠著最后push到棧的元素。
list_add_tail
再看內(nèi)核另外一種插入方式，本質(zhì)都是調(diào)用__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);
}
?
我們還是以示例輔助說明：
首先創(chuàng)建一個鏈表頭：
?
LIST_HEAD(listHead);
?
然后創(chuàng)建第一個節(jié)點
?
struct?my_data_list?first_data?=
{?
????.val?=?1,
????.list?=?LIST_HEAD_INIT(first_data.list),
};
?
插入第一個節(jié)點：
?
list_add_tail(&first_data.list,?listHead);
?
緊接著插入第二個節(jié)點：
?
struct?my_data_list?second_data?=
{?
????.val?=?2,
????/*?也可以調(diào)用接口?初始化*/
????.list?=?LIST_HEAD_INIT(second_data.list),
};
list_add_tail(&second_data.list,?&listHead);
?
示意圖如下：
每次插入的新節(jié)點都是緊挨著 header 表尾，而插入的第一個節(jié)點排在了第一位，第二個排在了第二位。
先插入的節(jié)點排在前面，后插入的節(jié)點排在后面，“先進先出，后進后出”（First in First out,FIFO）！這不就是隊列嗎？
總結
由于是雙循環(huán)鏈表，看起來尾部插入和頭部插入是一樣的，其實不然。
我們再來對比尾部和頭部插入的區(qū)別：
頭部插入，結構是逆序，屬于先進后出，最主要的區(qū)別就是頭節(jié)點的prev指針指向第一個節(jié)點。
尾部插入，結構是順序，屬于FIFO結構，最主要的區(qū)別就是頭節(jié)點的next指針指向第一個節(jié)點。
list_add：頭部插入一個節(jié)點
list_add_tail：尾部插入一個節(jié)點
2.4 刪除節(jié)點
內(nèi)核同樣定義了刪除節(jié)點的接口 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：這個接口，根據(jù)prev/next 刪除其節(jié)點，刪除的節(jié)點必須是已知的并且 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：刪除一個節(jié)點。
?
/**
?*?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) 接口就可以刪除鏈表中的任意節(jié)點了，需注意，前提條件是這個節(jié)點是已知的，既在鏈表中真實存在，切prev，next指針都不為NULL。
被剔除下來的 my_data_list.list，prev、next 指針分別被設為 LIST_POSITION2和LIST_POSITION1兩個特殊值，這樣設置是為了保證不在鏈表中的節(jié)點項不可訪問–對LIST_POSITION1和LIST_POSITION2的訪問都將引起頁故障。
與之相對應，list_del_init()函數(shù)將節(jié)點從鏈表中解下來之后，調(diào)用LIST_INIT_HEAD()將節(jié)點置為空鏈狀態(tài)。
list_del() 和 list_del_init 是外部接口。__list_del() 和 __list_entry() 是內(nèi)核內(nèi)部節(jié)點。
list_del() 作用是刪除雙鏈表中的一個節(jié)點。并將節(jié)點的prev和next都指向特定位置，LIST_POSITION1和LIST_POSITION2。
list_del_init() 作用是刪除雙鏈表中的一個節(jié)點，并將節(jié)點的prev和next都指向自己，回到最開始創(chuàng)建節(jié)點前的狀態(tài)。
2.5 搬移
內(nèi)核提供了將原本屬于一個鏈表的節(jié)點移動到另一個鏈表的操作，并根據(jù)插入到新鏈表的位置分為兩類：頭部搬移和尾部搬移。搬移的本質(zhì)就是刪除加插入。
頭部搬移
?
/**
?*?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 合并
內(nèi)核還提供兩組合并操作，將兩條鏈表合并在一起。
當 list1 被掛接到 list2 之后，作為原表頭指針的 list1 的next、prev仍然指向原來的節(jié)點，為了避免引起混亂，Linux提供了一個list_splice_init()函數(shù).該函數(shù)在將list合并到head鏈表的基礎上，調(diào)用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 替換
內(nèi)核還提供一組替換鏈表節(jié)點的操作。list_replace：將新的節(jié)點替換到舊的節(jié)點上。list_replace_init：將新的節(jié)點替換到舊的節(jié)點上。同時將舊的節(jié)點的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?遍歷操作
內(nèi)核提供了一組宏進行遍歷操作。經(jīng)過一系列的增刪減改操作，我們終于到了遍歷的時候。
list_entry 宏
重頭戲來了，遍歷的關鍵就是這個list_entry 宏。本質(zhì)就是container_of 宏。
具體分析見上一篇文章。這個宏的主要作用就是獲取宿主結構的指針地址。
前文提到，我們是以list 指針為節(jié)點組成的一條雙鏈表，遍歷的過程中只能得到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)
/*?根據(jù)list?倒推?my_list_data*/ list_entry(&my_list_data.list,?typeof(&my_list_data),?list)
?
list_for_each
list_for_each 它實際上是一個for循環(huán)，利用傳入的pos作為循環(huán)變量，從表頭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 內(nèi)核 中的雙鏈表結構，以圖文的方式旨在幫助大家理解。
當然還有很多接口限于篇幅沒有介紹，本文只列出了常用了接口，相信只要理解了前面雙鏈表的組成和插入過程，后面的刪除和遍歷就自然而然通了。
審核編輯：湯梓紅
工商網(wǎng)監(jiān)
評論