---
tags: LINUX KERNEL, LKI
---
# Linux 核心原始程式碼巨集: `container_of`
> 資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv)
:::success
`container_of` 巨集在 Linux 核心原始程式碼出現將近 7 千次 (v5.13)，不僅在 linked list 和 hash table 一類通用資料結構中可簡化程式設計，甚至是 Linux 核心達成物件導向程式設計的關鍵機制之一。
若要征服 Linux 核心原始程式碼，對 `container_of` 巨集的掌握度絕對要充分。
:::
## 跟你想像不同的 `struct`
考慮以下 C 程式:
```c
struct data {
short a;
char b;
double c;
};
```
假設依據 `struct data` 建立的物件為 `x`，也就是宣告為 `struct data x;`，給定指標 `char *p = (char *) &x;`
你或許會認為物件 `x` 在記憶體 (明確來說，是指虛擬記憶體分頁) 展現的樣貌如下圖:
也就是 `data` 這個結構體中，成員 `a` (型態為 `short` 整數) 佔 2 個位元組、成員 `b` (型態為 `char`，在 C 語言規格保證至少佔 1 個位元組)，以及緊接著出現的成員 `c` (型態為 `double`，在 C 語言規格中，至少需要 8 個位元組)。
我們常借助示意圖來理解事物，但也可能無意間偏離事實。以下是測試程式碼 (檔名: `data.c`)
```c=
#include <stdio.h>
struct data {
short a;
char b;
double c;
};
int main() {
struct data x = {.a = 25, .b = 'A', .c = 12.45};
char *p = (char *) &x;
printf("a=%d\n", *((short *) p));
p += sizeof(short);
printf("b=%c\n", *((char *) p));
p += sizeof(char);
printf("c=%lf\n", *((double *) p));
return 0;
}
```
編譯和執行:
```shell
$ gcc -o data data.c
$ ./data
```
輸出的前 2 行符合預期，即 `a=25` 和 `b=A`，但 `c=` 的輸出跟預期的 `12.45` 不同，為什麼呢？你或許會納悶：
> 成員 `c` 在結構體 `data` 中，不就是自開頭位移 `sizeof(short)` (即成員 `a`) 和 `sizeof(char)` (即成員 `b`) 嗎？
我們將第 15 行的 `return 0;` 換為以下程式碼:
```c=15
printf("p=%p, &x.c=%p\n", p, &(x.c));
```
在 Aarch64 (64 位元 Arm 架構) Linux 上執行會得到: (受限於 [ASLR](https://en.wikipedia.org/wiki/Address_space_layout_randomization)，每次執行結果都可能不同，這不影響我們判斷)
```
p=0xffffd6161a4b, &x.c=0xffffd6161a50
```
從執行結果可知，表示式 `(char *) &x + sizeof(short) + sizeof(char)` 和 `&(x.c)` 實際是不同的數值，既然指標內含值不同，進行 dereference (即 `*` 操作) 當然不會得到預期的輸出。問題出在我們忽略編譯器為了滿足 alignment 需求，進行的 [structure padding](http://www.catb.org/esr/structure-packing/)。
解決方式之一，是修改上述程式碼的第 6 行，將 `};` 改為以下:
```c=6
} __attribute__((packed));
```
這裡的 `__attribute__((packed))` 是 GNU extension，引述 GCC 手冊 [Common Type Attributes](https://gcc.gnu.org/onlinedocs/gcc/Common-Type-Attributes.html):
> This attribute, attached to a `struct`, `union`, or C++ `class` type definition, specifies that each of its members (other than zero-width bit-fields) is placed to minimize the memory required. This is equivalent to specifying the packed attribute on each of the members.
原來要額外加上 `packed` 屬性，結構體的成員實際排列和空間佔用才會跟程式碼順序一致，這是 C 語言程式設計其中一個陷阱，`packed` 過的結構體可能會犧牲資料存取的效率。
> 延伸閱讀: [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
為了提升程式碼的可攜性 (portability)，C89/C99 提供 [offsetof](https://man7.org/linux/man-pages/man3/offsetof.3.html) 巨集，可接受給定成員的型態及成員的名稱，傳回「成員的位址減去 struct 的起始位址」。示意如下:
[offsetof](https://man7.org/linux/man-pages/man3/offsetof.3.html) 定義於 `<stddef.h>`，因此我們應該在第 1 行後面新增一行:
```c
#include <stddef.h>
```
再將上述程式碼的第 13 行的 `p += sizeof(char);` 敘述換為以下:
```c
p = (char *) &x + offsetof(struct data, c);
```
這樣無論結構體是否 `packed`，均可符合預期地執行。
另外，如果你覺得 `offsetof(struct data, c)` 書寫很冗長，可換為:
```c
offsetof(typeof(x), c)
```
其中 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 也是 GNU extension，可在編譯時期得到物件 `x` 或 `*p` (型態也是 `struct data`) 的型態，這樣改寫後，我們就聚焦在「物件」和「成員名稱」。
在一些老舊的編譯器，如 [Sun WorkShop Compiler](https://en.wikipedia.org/wiki/Oracle_Developer_Studio)，用以下方式定義 `offsetof` 巨集:
```c
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE*)0)->MEMBER)
```
但後來的 GCC 和 clang 就用 builtin function 取代，例如 `__builtin_offsetof`。Linux 核心原始程式碼 [include/linux/stddef.h](https://github.com/torvalds/linux/blob/master/include/linux/stddef.h) 定義 `offsetof` 巨集:
```c
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER) __compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#endif
```
上述程式碼已於 [commit 14e8307](https://github.com/torvalds/linux/commit/14e83077d55ff4b88fe39f5e98fb8230c2ccb4fb) 更改為：
```c
#define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER)
```
在較新的 GCC 中，對應有效的 `__compiler_offsetof` 巨集。當巨集展開時，針對老舊的編譯器可能會成為 `(size_t)&((TYPE *)0)->MEMBER` 敘述，其原理是先將 TYPE 型態結構體的地址變更為 `0`，然後再加上成員 `MEMBER` 的偏移量。值得思忖的是，`&((TYPE *)0)->MEMBER中` 這樣對地址為 `0` 的記憶體區域進行操作，難道不會導致程式崩潰嗎？答案是，不會！
編譯器處理 `&((TYPE *)0)->MEMBER` 時，不會真正去存取地址為 `0` 的記憶體區段，只是將 `0` 看做指標操作的一個運算元，除非額外有 dereference 操作。
## `container_of` 巨集作為資料封裝的基礎
巨集 `container_of` 則在 [offsetof](https://man7.org/linux/man-pages/man3/offsetof.3.html) 的基礎上，擴充為「給定成員的位址、struct 的型態，及成員的名稱，傳回此 struct 的位址」，以下是示意圖
請不要小看這巨集，畢竟大量在 Linux 核心原始程式碼採用的巨集，應有其獨到之處。在 `container_of` 巨集出現前，程式設計的思維往往是:
1. 給定結構體起始地址
2. 求出結構體特定成員的記憶體內容
3. 傳回結構體成員的地址，作日後存取使用
`container_of` 巨集則逆轉上述流程，特別在 C 語言程式設計中，我們通常會定義一系列公開介面 (interface)，從而區隔各式實作 (implementation)。更明確來說，考慮以下 UML:
`Object` 作為抽象的展現，是所有衍生物件的基底，`Vehicle` 正如其寓意，泛指交通工具，而 `Car` 和 `Truck` 就是特定的交通工具「模板」。在 C 語言可用以下程式碼描述:
```c
typedef struct { int ref; } Object;
typedef struct { Object base; /* Vehicle-specific members */ } Vehicle;
typedef struct { Vehicle base; /* Car-specific members */ } Car;
void vehicleStart(Vehicle *obj) {
if (obj) printf("%x derived from %x\n", obj, obj->base);
}
int main(void) {
Car c;
vehicleStart((Vehicle *) &c);
}
```
> 完整程式碼: [doxygen-oop-in-c](https://github.com/jserv/doxygen-oop-in-c)
這段程式碼雖然只是印出物件之間的「繼承」關係，但蘊含重要的特性:
* `Car` 是實作本體，無論結構體再複雜，都有 `base` 這個成員，其型態為 `Vehicle`
* 同理，`Vehicle` 也包含一個 `base` 成員，後者的型態為 `Object`
* `Object` 是公開介面，內部只有 `ref` 成員，可充當 [reference counting](https://en.wikipedia.org/wiki/Reference_counting) 使用，本例沒有特別意義
於是，只要依循同樣的規則，無論有多少 `Car`, `Truck` 或更多的交通工具「模板」，我們都可藉由結構體的 `base` 成員，得知繼承關係，從而存取到上一層的公開資訊。物件導向程式設計的「封裝」(encapsulation)、繼承 (inheritance)，和多型 (polymorphism) 都可運用這樣的手法來達成。
> 延伸閱讀: [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-oop)
舉例來說，Linux 核心內建 V4L2 (video for Linux APIs, version 2) 框架來提供豐富的 Linux 多媒體處理，原始程式碼 [drivers/media/i2c/imx214.c](https://github.com/torvalds/linux/blob/master/drivers/media/i2c/imx214.c) 則是其中一個裝置驅動程式，部分程式碼列表如下:
```c
struct imx214 {
struct device *dev;
...
struct v4l2_ctrl_handler ctrls;
...
};
static int imx214_set_ctrl(struct v4l2_ctrl *ctrl)
{
struct imx214 *imx214 = container_of(ctrl->handler,
struct imx214, ctrls);
...
/* Applying V4L2 control value only happens
* when power is up for streaming
*/
if (!pm_runtime_get_if_in_use(imx214->dev)) return 0;
...
}
static const struct v4l2_ctrl_ops imx214_ctrl_ops = {
.s_ctrl = imx214_set_ctrl,
};
```
顯然，定義在 [drivers/media/i2c/imx214.c](https://github.com/torvalds/linux/blob/master/drivers/media/i2c/imx214.c) 的結構體 `imx214` 是 imx214 這個裝置驅動程式特有的定義，在其他 C 程式也無從得知，但 `v4l2_` 開頭的結構體則是 V4L2 框架的公開介面，上述程式碼的 `imx214_set_ctrl` 函式最終會被註冊為 V4L2 的一個實作，利用 `container_of` 巨集，我們就可隱藏 imx214 實作細節，但又能存取到 `imx214` 結構體的開頭，從而繼續存取到其他實作相關的成員。
> 延伸閱讀: [解析 Linux 共享記憶體機制](https://hackmd.io/@sysprog/linux-shared-memory)
也許乍看這沒什麼了不起，又不是語言糖 (syntax sugar)，也不是什麼神奇的演算法，但我們見識到 Linux 核心開發者追求的「優雅」 —— 清晰地界定介面和實作本體。
## `container_of` 實作手法
關於 `container_of` 巨集的實作手法，可參見下圖:
對應的原始程式碼如下:
```c
/* container_of() - Calculate address of object that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of object containing ptr
*/
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *(__pmember) = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
解析巨集的過程中，我們可留意 `__extension__`，依據 GCC 手冊 [Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html)
> `-pedantic` and other options cause warnings for many GNU C extensions. You can prevent such warnings within one expression by writing `__extension__` before the expression. `__extension__` has no effect aside from this.
儘管 GCC 幾乎支援 C 和 C++ 最新的規格，但仍考慮到傳統 C 程式 (即最廣泛支援的 [ANSI C](https://en.wikipedia.org/wiki/ANSI_C) C89 或 C90，注意: C90 和 C89 幾乎一致，差別在於 C90 納入 ISO/IEC 9899:1990 標準時，進行格式和排版調整)，提供 `-pedantic` 編譯選項，讓編譯器主動提醒開發者，是否用到 C89/C90 以外的特徵。
由於上述巨集用到 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 這個 GNU extension，於是特別用 `__extension__` 標注，避免 GCC 搭配 `-pedantic` 編譯選項時，會拋出警告訊息。
上述程式碼是從 struct 中的 member 推算出原本 struct 的位址。解析:
* 先透過 `__typeof__` 得到 type 中的成員 `member` 的型別，並宣告一個指向該型別的指標 `__pmember`
* 將 `ptr` 指派到 `__pmember`
* `__pmember` 目前指向的是 `member` 的位址
* `offsetof(type, member)` 可得知 `member` 在 `type` 這個結構體位移量，即 offset
* 將絕對位址 `(char *) __pmember` 減去 `offsetof(type, member)` ，可得到結構體的起始位址。計算 offset 時要轉成 `char *`，以確保 address 的計算符合預期 (可參考 [The (char *) casting in container_of() macro in linux kernel](https://stackoverflow.com/questions/20421910/the-char-casting-in-container-of-macro-in-linux-kernel) 的說明)
* 最後 `(type *)` 再將起始位置轉型為指向 `type` 的指標
> 延伸閱讀:
> * [你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer)
> * [你所不知道的 C 語言：技巧篇](https://hackmd.io/@sysprog/c-trick)
值得留意的是，Linux 核心原始程式碼提供的 `container_of` 巨集定義事實上更複雜:
```c=
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \
!__same_type(*(ptr), void), \
"pointer type mismatch in container_of()"); \
((type *)(__mptr - offsetof(type, member))); })
```
第 3 行藉由 `BUILD_BUG_ON_MSG` 巨集達到 static assert 的作用，儘量在編譯時期就查驗 `container_of` 巨集的使用是否合法：預先進行指標型態的檢查
> 延伸閱讀: [Linux 核心巨集: BUILD_BUG_ON_ZERO](https://hackmd.io/@sysprog/c-bitfield)
關於 `__same_type` 巨集，可見 [include/linux/compiler_types.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler_types.h):
```c
/* Are two types/vars the same type (ignoring qualifiers)? */
#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
```
同樣是運用 GNU extension 達成。
## 應用案例: 雙向環狀鏈結串列
接下來，我們仿效 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的精簡雙向環狀鏈結串列 (circular doubly-linked list，以下簡稱 `list`) 實作。關鍵概念是，將結構體 `list_head` 嵌入到所需的結構體中，再藉由 `container_of` 巨集得知 list 個別節點的地址。示意如下圖:
自 `Head` 開始，鏈結 list 各節點，個別節點皆嵌入 `list_head` 結構體，不過 `Head` 是個特例，無法藉由 `container_of` 巨集來找到對應的節點，因為後者並未嵌入到任何結構體之中，其存在是為了找到 list 整體。
程式碼列表:
```c
#include <stddef.h>
/* struct list_head - Head and node of a doubly-linked list
* @prev: pointer to the previous node in the list
* @next: pointer to the next node in the list
*/
struct list_head {
struct list_head *prev, *next;
};
/* LIST_HEAD - Declare list head and initialize it
* @head: name of the new object
*/
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
/* INIT_LIST_HEAD() - Initialize empty list head
* @head: pointer to list head
*/
static inline void INIT_LIST_HEAD(struct list_head *head) {
head->next = head; head->prev = head;
}
/* list_add_tail() - Add a list node to the end of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add_tail(struct list_head *node, struct list_head *head) {
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
/* list_del() - Remove a list node from the list
* @node: pointer to the node
*/
static inline void list_del(struct list_head *node) {
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
/* list_empty() - Check if list head has no nodes attached
* @head: pointer to the head of the list
*/
static inline int list_empty(const struct list_head *head) {
return (head->next == head);
}
/* list_is_singular() - Check if list head has exactly one node attached
* @head: pointer to the head of the list
*/
static inline int list_is_singular(const struct list_head *head) {
return (!list_empty(head) && head->prev == head->next);
}
/* list_splice_tail() - Add list nodes from a list to end of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*/
static inline void list_splice_tail(struct list_head *list,
struct list_head *head) {
if (list_empty(list))
return;
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next, *list_last = list->prev;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
/* list_cut_position() - Move beginning of a list to another list
* @head_to: pointer to the head of the list which receives nodes
* @head_from: pointer to the head of the list
* @node: pointer to the node in which defines the cutting point
*/
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node) {
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
/* list_entry() - Calculate address of entry that contains list node
* @node: pointer to list node
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*/
#define list_entry(node, type, member) container_of(node, type, member)
/* list_first_entry() - get first entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*/
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
/* list_for_each - iterate over list nodes
* @node: list_head pointer used as iterator
* @head: pointer to the head of the list
*/
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
上方程式碼的好處在於，只要 `list_head` 納入新的結構體的一個成員，即可操作，且不用自行維護一套 doubly-linked list 。
> 延伸閱讀: [Linux 鏈結串列 struct list_head 研究](https://myao0730.blogspot.com/2016/12/linux.html)
注意到 `list_entry` 利用 `container_of` 巨集，藉由 `struct list_head` 這個公開介面，「反向」去存取到自行定義的結構體開頭地址。
以下為圖解:
- [ ] `list_head` 結構體
```c
struct list_head { struct list_head *prev, *next; };
```
```graphviz
digraph list_head {
rankdir=LR;
node[shape=record, style=bold];
head [label="{<prev>prev|<next>next}"];
}
```
- [ ] 在自行定義的結構體置入 `list_head` 物件
```c
typedef struct {
char *value;
struct list_head list;
} my_data;
```
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
node [shape=record];
value [label="{value}"];
head [label="{<prev>prev|<next>next}"];
style=bold;
label=my_data
}
}
```
簡化為下圖：
```graphviz
digraph list_ele {
rankdir=LR;
node[shape=record];
node [shape=record];
head [label="value|{<left>prev|<right>next}", style=bold];
}
```
- [ ] `LIST_HEAD - Declare list head and initialize it`
```c
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
```
```graphviz
digraph list_init {
rankdir=LR;
node[shape=record];
style=bold
node [shape=record];
head [label="{<left>prev|<right>next}", style="bold"];
head:right:e -> head:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
- [ ] `list_entry() - Calculate address of entry that contains list node`
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
```graphviz
digraph container {
rankdir=LR;
node[shape=record];
compound=true;
style=bold;
subgraph cluster_0 {
container [label = "container" style=filled,color=white];
subgraph cluster_1 {
node [shape=record];
element [label="|{|}", style="bold"];
label = "member"
}
}
element -> container[ltail=cluster_1, lhead=cluster_0];
}
```
- [ ] `list_for_each - iterate over list nodes`
```c
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
h [label="head", style=dashed, color=grey];
h -> e1:right:w [style=dashed, color=grey];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="cat|{<left>prev|<right>next}", style="bold"];
e3 [label="...", style="bold"];
e4 [label="eat|{<left>prev|<right>next}", style="bold"];
e5 [label="fat|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
> 延伸閱讀: [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list)
Sign in with Wallet
Connect another wallet