Linux 核心原始程式碼巨集: `container_of`

資料整理: jserv

container_of 巨集在 Linux 核心原始程式碼出現將近 7 千次 (v5.13)，不僅在 linked list 和 hash table 一類通用資料結構中可簡化程式設計，甚至是 Linux 核心達成物件導向程式設計的關鍵機制之一。

若要征服 Linux 核心原始程式碼，對 container_of 巨集的掌握度絕對要充分。

跟你想像不同的 `struct`

考慮以下 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)
















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

編譯和執行:

$ 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; 換為以下程式碼:


    printf("p=%p, &x.c=%p\n", p, &(x.c));

在 Aarch64 (64 位元 Arm 架構) Linux 上執行會得到: (受限於 ASLR，每次執行結果都可能不同，這不影響我們判斷)

p=0xffffd6161a4b, &x.c=0xffffd6161a50

從執行結果可知，表示式 (char *) &x + sizeof(short) + sizeof(char) 和 &(x.c) 實際是不同的數值，既然指標內含值不同，進行 dereference (即 * 操作) 當然不會得到預期的輸出。問題出在我們忽略編譯器為了滿足 alignment 需求，進行的 structure padding。

解決方式之一，是修改上述程式碼的第 6 行，將 }; 改為以下:


} __attribute__((packed));

這裡的 __attribute__((packed)) 是 GNU extension，引述 GCC 手冊 Common Type Attributes:

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 語言：記憶體管理、對齊及硬體特性

為了提升程式碼的可攜性 (portability)，C89/C99 提供 offsetof 巨集，可接受給定成員的型態及成員的名稱，傳回「成員的位址減去 struct 的起始位址」。示意如下:

offsetof 定義於 <stddef.h>，因此我們應該在第 1 行後面新增一行:

#include <stddef.h>

再將上述程式碼的第 13 行的 p += sizeof(char); 敘述換為以下:

p = (char *) &x + offsetof(struct data, c);

這樣無論結構體是否 packed，均可符合預期地執行。

另外，如果你覺得 offsetof(struct data, c) 書寫很冗長，可換為:

offsetof(typeof(x), c)

其中 typeof 也是 GNU extension，可在編譯時期得到物件 x 或 *p (型態也是 struct data) 的型態，這樣改寫後，我們就聚焦在「物件」和「成員名稱」。

在一些老舊的編譯器，如 Sun WorkShop Compiler，用以下方式定義 offsetof 巨集:

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

但後來的 GCC 和 clang 就用 builtin function 取代，例如 __builtin_offsetof。Linux 核心原始程式碼 include/linux/stddef.h 定義 offsetof 巨集:

#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER)	__compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
#endif

上述程式碼已於 commit 14e8307 更改為：

#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 的基礎上，擴充為「給定成員的位址、struct 的型態，及成員的名稱，傳回此 struct 的位址」，以下是示意圖

請不要小看這巨集，畢竟大量在 Linux 核心原始程式碼採用的巨集，應有其獨到之處。在 container_of 巨集出現前，程式設計的思維往往是:

給定結構體起始地址
求出結構體特定成員的記憶體內容
傳回結構體成員的地址，作日後存取使用

container_of 巨集則逆轉上述流程，特別在 C 語言程式設計中，我們通常會定義一系列公開介面 (interface)，從而區隔各式實作 (implementation)。更明確來說，考慮以下 UML:

Object 作為抽象的展現，是所有衍生物件的基底，Vehicle 正如其寓意，泛指交通工具，而 Car 和 Truck 就是特定的交通工具「模板」。在 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

這段程式碼雖然只是印出物件之間的「繼承」關係，但蘊含重要的特性:

Car 是實作本體，無論結構體再複雜，都有 base 這個成員，其型態為 Vehicle
同理，Vehicle 也包含一個 base 成員，後者的型態為 Object
Object 是公開介面，內部只有 ref 成員，可充當 reference counting 使用，本例沒有特別意義

於是，只要依循同樣的規則，無論有多少 Car, Truck 或更多的交通工具「模板」，我們都可藉由結構體的 base 成員，得知繼承關係，從而存取到上一層的公開資訊。物件導向程式設計的「封裝」(encapsulation)、繼承 (inheritance)，和多型 (polymorphism) 都可運用這樣的手法來達成。

延伸閱讀: 你所不知道的 C 語言：物件導向程式設計篇

舉例來說，Linux 核心內建 V4L2 (video for Linux APIs, version 2) 框架來提供豐富的 Linux 多媒體處理，原始程式碼 drivers/media/i2c/imx214.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 的結構體 imx214 是 imx214 這個裝置驅動程式特有的定義，在其他 C 程式也無從得知，但 v4l2_ 開頭的結構體則是 V4L2 框架的公開介面，上述程式碼的 imx214_set_ctrl 函式最終會被註冊為 V4L2 的一個實作，利用 container_of 巨集，我們就可隱藏 imx214 實作細節，但又能存取到 imx214 結構體的開頭，從而繼續存取到其他實作相關的成員。

延伸閱讀: 解析 Linux 共享記憶體機制

也許乍看這沒什麼了不起，又不是語言糖 (syntax sugar)，也不是什麼神奇的演算法，但我們見識到 Linux 核心開發者追求的「優雅」 —— 清晰地界定介面和實作本體。

`container_of` 實作手法

關於 container_of 巨集的實作手法，可參見下圖:

對應的原始程式碼如下:

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

-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 C89 或 C90，注意: C90 和 C89 幾乎一致，差別在於 C90 納入 ISO/IEC 9899:1990 標準時，進行格式和排版調整)，提供 -pedantic 編譯選項，讓編譯器主動提醒開發者，是否用到 C89/C90 以外的特徵。

由於上述巨集用到 typeof 這個 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 的說明)
最後 (type *) 再將起始位置轉型為指向 type 的指標

延伸閱讀:

你所不知道的 C 語言：指標篇

你所不知道的 C 語言：技巧篇

值得留意的是，Linux 核心原始程式碼提供的 container_of 巨集定義事實上更複雜:






#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

關於 __same_type 巨集，可見 include/linux/compiler_types.h:

/* 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 的精簡雙向環狀鏈結串列 (circular doubly-linked list，以下簡稱 list) 實作。關鍵概念是，將結構體 list_head 嵌入到所需的結構體中，再藉由 container_of 巨集得知 list 個別節點的地址。示意如下圖:

自 Head 開始，鏈結 list 各節點，個別節點皆嵌入 list_head 結構體，不過 Head 是個特例，無法藉由 container_of 巨集來找到對應的節點，因為後者並未嵌入到任何結構體之中，其存在是為了找到 list 整體。

程式碼列表:

#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 研究

注意到 list_entry 利用 container_of 巨集，藉由 struct list_head 這個公開介面，「反向」去存取到自行定義的結構體開頭地址。

以下為圖解:

list_head 結構體

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

在自行定義的結構體置入 list_head 物件

typedef struct {
    char *value;
    struct list_head list;
} my_data;

簡化為下圖：

LIST_HEAD - Declare list head and initialize it

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

list_entry() - Calculate address of entry that contains list node

#define list_entry(node, type, member) container_of(node, type, member)

list_for_each - iterate over list nodes

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

延伸閱讀: 你所不知道的C語言: linked list 和非連續記憶體操作

Linux 核心原始程式碼巨集: container_of

跟你想像不同的 struct

container_of 巨集作為資料封裝的基礎

container_of 實作手法

應用案例: 雙向環狀鏈結串列

Read more

單一指令處理器 (OISC)

從 CPU cache coherence 談 Linux spinlock 可擴展能力議題

淺談 Microkernel 設計和真實世界中的應用

並行程式設計: 概念

Linux 核心原始程式碼巨集: `container_of`

跟你想像不同的 `struct`

`container_of` 巨集作為資料封裝的基礎

`container_of` 實作手法