源碼閱讀之旅，Linux內(nèi)核鏈表妙在哪？

一、導(dǎo)讀

自從上次刷了一題LeetCode兩數(shù)之和后，我就去研讀了uthash的源碼，對其鏈表的使用方法感到非常震撼。

隨后，我又發(fā)現(xiàn)Linux內(nèi)核鏈表的實現(xiàn)也采用了類似的思想。

接下來，我將和大家分享傳統(tǒng)鏈表與Linux內(nèi)核鏈表實現(xiàn)之間的差異。

二、傳統(tǒng)鏈表結(jié)構(gòu)

在C語言中，傳統(tǒng)鏈表的實現(xiàn)通常如下所示：

/**
?* @Author:typedef公眾號
?*/
typedef?struct?Node?{
??int?data; ? ? ? ? ? ? ?// 數(shù)據(jù)域
??struct?Node*?prev;? ? ?// 指向前一個節(jié)點的指針
??struct?Node*?next;? ? ?// 指向后一個節(jié)點的指針
} Node;

每個節(jié)點包含數(shù)據(jù)和指向上一個以及下一個節(jié)點的指針，還有一些用戶數(shù)據(jù)。如下圖所示：

從上述代碼和結(jié)構(gòu)可以看出，傳統(tǒng)鏈表的缺點十分顯著。其數(shù)據(jù)結(jié)構(gòu)緊密依賴于特定的用戶自定義結(jié)構(gòu)體，缺乏通用性。

因為指針指向的用戶區(qū)域結(jié)構(gòu)體變化多樣，所以鏈表的操作函數(shù)難以被重復(fù)利用，在不同的項目或模塊中需要重復(fù)編寫類似的操作邏輯，這極大地降低了開發(fā)效率。

三、Linux 內(nèi)核鏈表結(jié)構(gòu)

Linux 的鏈表結(jié)構(gòu)設(shè)計為鏈表的指針直接指向用戶結(jié)構(gòu)體中的鏈表節(jié)點。例如：

/**
?* @Author:typedef公眾號
?*/
struct?list?{// 定義雙向鏈表節(jié)點結(jié)構(gòu)
struct?list?*prev;
struct?list?*next;
};

typedefstruct?{// 定義包含鏈表節(jié)點的結(jié)構(gòu)體
int?data;
struct?list?node;
} my_struct;

它將鏈表節(jié)點抽象出來，定義在一個通用的結(jié)構(gòu)體struct list中，數(shù)據(jù)結(jié)構(gòu)如下圖所示：

那么問題來了，因為鏈表存放的都是struct list類型對象，而用戶數(shù)據(jù)是my_struct類型對象，這樣我不是獲取不到用戶對象了嘛？

而其中的精髓也就在此處，Linux 是通過container_of?宏實現(xiàn)的，原型如下。

/**
?* container_of - cast a member of a structure out to the containing structure
?* @ptr: the pointer to the member.
?* @type: the type of the container struct this is embedded in.
?* @member: the name of the member within the struct.
?*
?* WARNING: any const qualifier of @ptr is lost.
?*/
#define?container_of(ptr, type, member) ({ ? ?\
?void *__mptr = (void *)(ptr); ? ? \
?static_assert(__same_type(*(ptr), ((type *)0)->member) || \
? ? ? ? __same_type(*(ptr), void), ? \
? ? ? ??"pointer type mismatch in container_of()"); \
?((type *)(__mptr - offsetof(type, member))); })

參數(shù)介紹：

• ptr：指向結(jié)構(gòu)體成員的指針。
• type：包含該成員的結(jié)構(gòu)體的類型。
• member：結(jié)構(gòu)體中的成員名稱。

這個宏的目的是根據(jù)結(jié)構(gòu)體成員的地址獲取該結(jié)構(gòu)體的起始地址。實現(xiàn)的核心原理是利用指針運算和結(jié)構(gòu)體成員的偏移量來獲得結(jié)構(gòu)體的起始地址。

假如有一個類型為my_struct的user對象，則container_of(&user.node, my_struct, node)返回的對象就是user。

我們再來看下內(nèi)部是如何實現(xiàn)的。

void *__mptr = (void *)(ptr);

第一行是將ptr轉(zhuǎn)換為void *，后面再進行減法運算時，實際上是將指針當(dāng)作char *類型來處理（因為void *在進行算術(shù)運算時會被轉(zhuǎn)換為char *類型），這樣就可以按照字節(jié)為單位準(zhǔn)確地減去成員在結(jié)構(gòu)體中的偏移量，而不受原始成員指針類型的影響。

static_assert(__same_type(*(ptr), ((type?)0)->member) ||
__same_type((ptr), void),
"pointer type mismatch in container_of()");

第二行是一個靜態(tài)斷言，用于檢查ptr所指向的成員的類型是否與type結(jié)構(gòu)體中member成員的類型相同，或者ptr是否為void *類型。如果不滿足條件，編譯時會產(chǎn)生錯誤提示 “pointer type mismatch in container_of ()”。

((type *)(__mptr - offsetof(type, member)));

第三行通過offsetof(type, member)獲取成員member在結(jié)構(gòu)體type中的偏移量。然后將__mptr轉(zhuǎn)換為char *類型指針，以便按字節(jié)進行減法運算，從成員的地址__mptr中減去成員相對于結(jié)構(gòu)體起始位置的偏移量，從而計算出整個結(jié)構(gòu)體的首地址。最后，將結(jié)果轉(zhuǎn)換為type *類型的指針，表示整個結(jié)構(gòu)體的首地址。

其中，offsetof宏用于計算結(jié)構(gòu)體成員相對于結(jié)構(gòu)體起始地址的偏移量，其定義如下：

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

它的工作原理是：首先將0強制轉(zhuǎn)換為type *類型的結(jié)構(gòu)體指針（表示結(jié)構(gòu)體起始地址為0），然后通過->MEMBER訪問該假設(shè)結(jié)構(gòu)體的MEMBER成員，此時MEMBER的地址就是其相對于結(jié)構(gòu)體開頭的偏移量。

感覺這些代碼寫的好騷哦，大為震撼，哈哈...

Linux內(nèi)核鏈表結(jié)構(gòu)提供了更高的通用性和操作復(fù)用性。通過將數(shù)據(jù)和節(jié)點解耦，我們可以在不同的數(shù)據(jù)結(jié)構(gòu)中重用相同的鏈表操作，簡化了代碼的復(fù)雜度。

四、鏈接

• https://github.com/torvalds/linux/blob/master/include/linux/container_of.h
• https://github.com/troydhanson/uthash

五、最后

我把uthash?下載并保存到了網(wǎng)盤，如果您也想閱讀源碼但沒有梯子，可以后臺回復(fù)關(guān)鍵字688?獲取鏈接，然后從02-代碼目錄中查找，只要看example.c?以及uthash.h?文件就行了。

我鼓勵大家積極閱讀源碼，盡管過程中可能會遇到一些挑戰(zhàn)和困難，但這也是鍛煉思維和提升技能的寶貴機會。歡迎交流...