最近在看 Linux 中双向链表的实现，发现大部分代码都是能看懂的，和上学时学的内容基本一致。

什么头插法，尾插法啊乱七八糟的。

但我注意到有一点似乎不一样，在学校时，我们学的链表包括数据域和指针域，但在 Linux 中双向链表的节点是这样定义的：

1
2
3
struct list_head {
	struct list_head *next, *prev;
};

没有数据域

没有数据域的链表该怎么使用呢？

Recently I’ve been reading the Linux doubly-linked list implementation, and found that most of the code is understandable — basically the same as what I learned in school.

Head insertion, tail insertion, and all that stuff.

But I noticed one thing seems different: in school, we learned that a linked list node includes a data field and a pointer field, but in Linux the doubly-linked list node is defined like this:

1
2
3
struct list_head {
	struct list_head *next, *prev;
};

No data field

How do you use a linked list without a data field?

首先，在我过往的记忆中，链表的指针是为了找到下一个节点的地址，从而能够访问到下一个节点的数据。

就像是这样：

1
2
3
4
5
6
struct node{
    int id;
    void *data;
    struct node *next;
    struct node *prev;
};

画图的话就是下面这种状态。

这种方法可以方便地访问下一个节点的数据，像是这样node->next->id

但缺点就是，针对不同类型的数据，都要创建不同类型的节点。

那么 Linux 中是如何使用双向链表的呢？

我在高通 WLAN 驱动程序的代码中找到了 list.h 的使用示例

https://github.com/WANG-Guangxin/wlan-dirver/blob/master/qca-wifi-host-cmn/scheduler/inc/scheduler_api.h#L85

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * struct scheduler_msg: scheduler message structure
 * @type: message type
 * @reserved: reserved field
 * @bodyval: message body val
 * @bodyptr: message body pointer based on the type either a bodyptr pointer
 *     into memory or bodyval as a 32 bit data is used. bodyptr is always a
 *     freeable pointer, one should always make sure that bodyptr is always
 *     freeable.
 * Messages should use either bodyptr or bodyval; not both !!!
 * @callback: callback to be called by scheduler thread once message is posted
 *   and scheduler thread has started processing the message.
 * @flush_callback: flush callback which will be invoked during driver unload
 *   such that component can release the ref count of common global objects
 *   like PSOC, PDEV, VDEV and PEER. A component needs to populate flush
 *   callback in message body pointer for those messages which have taken ref
 *   count for above mentioned common objects.
 * @node: list node for queue membership
 * @queue_id: Id of the queue the message was added to
 * @queue_depth: depth of the queue when the message was queued
 * @queued_at_us: timestamp when the message was queued in microseconds
 */
struct scheduler_msg {
	uint16_t type;
	uint16_t reserved;
	uint32_t bodyval;
	void *bodyptr;
	scheduler_msg_process_fn_t callback;
	scheduler_msg_process_fn_t flush_callback;
	qdf_list_node_t node; // here
#ifdef WLAN_SCHED_HISTORY_SIZE
	QDF_MODULE_ID queue_id;
	uint32_t queue_depth;
	uint64_t queued_at_us;
#endif /* WLAN_SCHED_HISTORY_SIZE */
};

scheduler_msg 这个结构体中有许多乱七八糟的数据，像是 type reserved 等等

其中一个成员叫做 node , 类型是 qdf_list_node_t, 看名字也可以猜出一半，它就是链表的节点类型。

我们追溯一下它到底是什么类型：

typedef __qdf_list_node_t qdf_list_node_t;

typedef struct list_head __qdf_list_node_t;

所以，qdf_list_node_t 就是 Linux 中的 list_head

于是，我们可以看到在 WLAN 驱动代码中它是这样使用 Linux 中的双向链表的

在自己的 msg 结构体中有一个成员是 list_node 类型，内存布局应该向下面这样

如果是这样的布局，那就引发一个新的问题

既然指针串起来的是 list_node 类型，而不是 msg 类型，那么即使通过 next 指针找到了下一个节点，找到的也是下一个msg 的 list_node ，而不是下一个 msg 啊，该怎么访问 msg 的数据呢？

先从代码中看一下我画的 msg 内存布局对不对，于是找到了 scheduler_mq_put 函数，顾名思义，这是将 msg 放到 msg queue 中的函数，所谓的 msg queue 其实就是双向链表。

https://github.com/WANG-Guangxin/wlan-dirver/blob/master/qca-wifi-host-cmn/scheduler/src/scheduler_core.c#L251

1
2
3
4
5
6
7
8
void scheduler_mq_put(struct scheduler_mq_type *msg_q,
		      struct scheduler_msg *msg)
{
	qdf_spin_lock_irqsave(&msg_q->mq_lock);
	sched_history_queue(msg_q, msg);
	qdf_list_insert_back(&msg_q->mq_list, &msg->node);
	qdf_spin_unlock_irqrestore(&msg_q->mq_lock);
}

可以看到 qdf_list_insert_back 的第二个参数就是 msg 的链表节点成员，也就是说被串起来的就是 node，而不是 msg 本身。

这种做法肯定是反数据结构教科书的，至少我没在书本上见到这样使用链表的。

于是如何根据 msg 的 node 成员访问到 msg 的其他数据成员就成了问题，我当然知道它们内存上是连续的，但是靠强制移动指针然后转换成其他成员的类型也太不优雅了。

我想知道 Linux 的方案，又想到刚刚那个函数名字叫做 put, 那我找找 get 是如何实现的就好了。

https://github.com/WANG-Guangxin/wlan-dirver/blob/master/qca-wifi-host-cmn/scheduler/src/scheduler_core.c#L269

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct scheduler_msg *scheduler_mq_get(struct scheduler_mq_type *msg_q)
{
	QDF_STATUS status;
	qdf_list_node_t *node;

	qdf_spin_lock_irqsave(&msg_q->mq_lock);
	status = qdf_list_remove_front(&msg_q->mq_list, &node);
	qdf_spin_unlock_irqrestore(&msg_q->mq_lock);

	if (QDF_IS_STATUS_ERROR(status))
		return NULL;

	return qdf_container_of(node, struct scheduler_msg, node);
}

首先，看返回值类型，是 scheduler_msg 没错。

关键代码 qdf_list_remove_front(&msg_q->mq_list, &node); 删除链表的头部，然后把被删除的节点地址给 node 变量，然后就 return qdf_container_of(node, struct scheduler_msg, node); 了。

也就是说 qdf_container_of 的返回值就是 scheduler_msg

qdf_container_of 实现了入参是结构体成员的类型，返回值是结构体类型的指针。

既然知道了这个函数的功能，我们可以大概推测一下这个函数是如何实现的。

已知一个结构体成员变量的地址，获得这个结构体首地址的必要条件是什么？

  1. 这个结构体类型的内存结构，也就是要知道这个结构体的类型
  2. 既然知道了这个成员变量的首地址，如果知道它是哪个成员，就能够根据偏移量推算出结构体类型的首地址。

以上两个必要条件就是 qdf_container_of 的第二个和第三个参数。

在 WLAN 驱动的代码中，它最终的定义是这样的。

https://github.com/WANG-Guangxin/wlan-dirver/blob/master/qcacld-3.0/core/dp/htt/htt_h2t.c#L56

1
2
#define container_of(ptr, type, member) \
	((type *)((char *)(ptr) - (char *)(&((type *)0)->member)))

第一个参数：成员变量的指针

第二个参数：结构体类型

第三个参数：成员变量的名字

qdf_container_of(node, struct scheduler_msg, node) 这里第一个 node 是指针，第三个 node 表示名字。

那 container_of 做了些什么呢？

让我们有请 GPT 来给出专业解答吧：

这是一个在C语言中用于获得结构体中某个成员所在的结构体对象的宏。这个宏的功能正如它的名字"container_of"所表达的含义，其主要功能是找到某个成员（member）所在的容器（即包含它的结构体）。

在宏的参数中：

  • ptr 是指向目标成员的指针。
  • type 是包含这个成员的结构体类型。
  • member 是目标成员的名字。

该宏主要利用的是C语言中，对从0地址取得对应元素偏移量，并且利用这个偏移量从而找到这个元素实际可能存放的结构体的起始地址。

具体细解如下：

  1. &((type *)0)->member：这一部分是做了一些计算得到了目标成员在结构体中的偏移量。首先，(type *)0把0转换成了一个类型为type的空指针。然后它去寻找member的地址，因为这个指针的基地址为0，所以这个地址就是member在结构体中的偏移量。

  2. (char *)(ptr) - (char *)(&((type *)0)->member) 这个步骤算出了目标成员的地址 ptr 里面的数据减去该成员的偏移量，得到的其实就是包含此成员的结构体的起始地址。因为在C语言中的内存布局里，一个结构体中的成员是按照他们在结构体定义中的顺序一次存放在内存中的。

  3. ((type *)((char *)(ptr) - (char *)(&((type *)0)->member))) 这一步事将计算得来的包含此成员的结构体的起始地址强制转换为type类型的指针。

因此，整个宏的作用就是找到并返回给定成员所在的结构体的地址。

最后，

其实 list.h 中的 container_of 和 高通这个定义在形式上还有点区别，但本质都是一样的。

1
2
3
#define container_of(ptr, type, member) ({                      \
	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
	(type *)( (char *)__mptr - offsetof(type,member) );})

First, in my past understanding, the pointer in a linked list exists to find the address of the next node, so that you can access the next node’s data.

Like this:

1
2
3
4
5
6
struct node{
    int id;
    void *data;
    struct node *next;
    struct node *prev;
};

Drawn as a diagram, it looks like this.

This approach makes it convenient to access the next node’s data, like node->next->id.

But the downside is that for different data types, you have to create different node types.

So how does Linux use doubly-linked lists?

I found a usage example of list.h in the Qualcomm WLAN driver code

https://github.com/WANG-Guangxin/wlan-dirver/blob/master/qca-wifi-host-cmn/scheduler/inc/scheduler_api.h#L85

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * struct scheduler_msg: scheduler message structure
 * @type: message type
 * @reserved: reserved field
 * @bodyval: message body val
 * @bodyptr: message body pointer based on the type either a bodyptr pointer
 *     into memory or bodyval as a 32 bit data is used. bodyptr is always a
 *     freeable pointer, one should always make sure that bodyptr is always
 *     freeable.
 * Messages should use either bodyptr or bodyval; not both !!!
 * @callback: callback to be called by scheduler thread once message is posted
 *   and scheduler thread has started processing the message.
 * @flush_callback: flush callback which will be invoked during driver unload
 *   such that component can release the ref count of common global objects
 *   like PSOC, PDEV, VDEV and PEER. A component needs to populate flush
 *   callback in message body pointer for those messages which have taken ref
 *   count for above mentioned common objects.
 * @node: list node for queue membership
 * @queue_id: Id of the queue the message was added to
 * @queue_depth: depth of the queue when the message was queued
 * @queued_at_us: timestamp when the message was queued in microseconds
 */
struct scheduler_msg {
	uint16_t type;
	uint16_t reserved;
	uint32_t bodyval;
	void *bodyptr;
	scheduler_msg_process_fn_t callback;
	scheduler_msg_process_fn_t flush_callback;
	qdf_list_node_t node; // here
#ifdef WLAN_SCHED_HISTORY_SIZE
	QDF_MODULE_ID queue_id;
	uint32_t queue_depth;
	uint64_t queued_at_us;
#endif /* WLAN_SCHED_HISTORY_SIZE */
};

The scheduler_msg struct contains a bunch of miscellaneous data, like type, reserved, etc.

One of the members is called node, with the type qdf_list_node_t — as the name suggests, it’s the linked list node type.

Let’s trace what type it actually is:

typedef __qdf_list_node_t qdf_list_node_t;

typedef struct list_head __qdf_list_node_t;

So qdf_list_node_t is Linux’s list_head.

Thus we can see how the WLAN driver code uses Linux’s doubly-linked list:

its own msg struct has a member of type list_node, and the memory layout should look like this

With this layout, a new problem arises: since what gets linked by the pointers is the list_node type, not the msg type, even if you find the next node via the next pointer, what you find is the next msg's list_node, not the next msg itself. How do you access the msg's data?

Let me first check from the code whether the msg memory layout I drew is correct. I found the scheduler_mq_put function — as its name suggests, this puts a msg into the msg queue, and the so-called msg queue is just a doubly-linked list.

https://github.com/WANG-Guangxin/wlan-dirver/blob/master/qca-wifi-host-cmn/scheduler/src/scheduler_core.c#L251

1
2
3
4
5
6
7
8
void scheduler_mq_put(struct scheduler_mq_type *msg_q,
		      struct scheduler_msg *msg)
{
	qdf_spin_lock_irqsave(&msg_q->mq_lock);
	sched_history_queue(msg_q, msg);
	qdf_list_insert_back(&msg_q->mq_list, &msg->node);
	qdf_spin_unlock_irqrestore(&msg_q->mq_lock);
}

You can see that the second parameter of qdf_list_insert_back is the msg’s linked list node member — meaning what gets linked is the node, not the msg itself.

This approach definitely goes against data structure textbooks; at least I’ve never seen linked lists used this way in books.

So the question of how to access the msg’s other data members from the msg’s node member became a problem. Of course I know they’re contiguous in memory, but forcibly moving the pointer and casting to other member types is too inelegant.

I wanted to know Linux’s solution, and since that function was named put, I figured I’d find how get is implemented.

https://github.com/WANG-Guangxin/wlan-dirver/blob/master/qca-wifi-host-cmn/scheduler/src/scheduler_core.c#L269

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct scheduler_msg *scheduler_mq_get(struct scheduler_mq_type *msg_q)
{
	QDF_STATUS status;
	qdf_list_node_t *node;

	qdf_spin_lock_irqsave(&msg_q->mq_lock);
	status = qdf_list_remove_front(&msg_q->mq_list, &node);
	qdf_spin_unlock_irqrestore(&msg_q->mq_lock);

	if (QDF_IS_STATUS_ERROR(status))
		return NULL;

	return qdf_container_of(node, struct scheduler_msg, node);
}

First, look at the return type: it’s scheduler_msg, right.

The key line is qdf_list_remove_front(&msg_q->mq_list, &node); — it removes the head of the list and assigns the removed node’s address to the node variable, then return qdf_container_of(node, struct scheduler_msg, node);.

That is, the return value of qdf_container_of is the scheduler_msg.

qdf_container_of takes a struct member’s type as input and returns a pointer to the struct type.

Now that we know what this function does, we can roughly guess how it’s implemented.

Given the address of a struct member variable, what are the necessary conditions to obtain the struct’s starting address?

  1. The memory structure of this struct type — i.e., we need to know the struct’s type.
  2. Since we know the starting address of this member variable, if we know which member it is, we can deduce the struct type’s starting address from the offset.

These two necessary conditions are exactly the second and third parameters of qdf_container_of.

In the WLAN driver code, its final definition is like this.

https://github.com/WANG-Guangxin/wlan-dirver/blob/master/qcacld-3.0/core/dp/htt/htt_h2t.c#L56

1
2
#define container_of(ptr, type, member) \
	((type *)((char *)(ptr) - (char *)(&((type *)0)->member)))

First parameter: pointer to the member variable

Second parameter: the struct type

Third parameter: the name of the member variable

In qdf_container_of(node, struct scheduler_msg, node), the first node is a pointer, the third node is the name.

So what does container_of do?

Let’s invite GPT to give a professional explanation:

This is a C macro used to obtain the struct object that contains a given member. The macro’s function, as its name “container_of” implies, is mainly to find the container (i.e., the struct that contains it) of a certain member.

In the macro’s parameters:

  • ptr is the pointer to the target member.
  • type is the struct type containing this member.
  • member is the name of the target member.

The macro mainly exploits the fact that in C, taking the offset of an element from address 0 and using this offset to find the actual starting address of the struct that may contain this element.

Detailed breakdown:

  1. &((type *)0)->member: this part computes the offset of the target member within the struct. First, (type *)0 converts 0 into a null pointer of type type. Then it looks up the address of member; since the base address of this pointer is 0, this address is the offset of member within the struct.

  2. (char *)(ptr) - (char *)(&((type *)0)->member): this step computes the address of the target member, subtracting the member’s offset from ptr, which gives the starting address of the struct containing this member. Because in C’s memory layout, the members of a struct are stored in memory in the order they are defined in the struct.

  3. ((type *)((char *)(ptr) - (char *)(&((type *)0)->member))): this step casts the computed starting address of the struct containing this member to a pointer of type type.

Therefore, the whole macro finds and returns the address of the struct containing the given member.

Finally,

Actually, the container_of in list.h differs slightly in form from Qualcomm’s definition, but they’re essentially the same.

1
2
3
#define container_of(ptr, type, member) ({                      \
	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
	(type *)( (char *)__mptr - offsetof(type,member) );})