深入解析C语言尾队列TAILQ：内存布局与核心宏原理

我最早看到TAILQ_INSERT_TAIL()的时候，心里其实很疑惑：Linux 内核不是已经有一套list_head了吗，为什么还要再搞一套“尾队列”？直到有一次在一段网络驱动代码里追数据的入队和出队逻辑，发现对方用的是 BSD 风味的TAILQ_*宏，和list_head长得像，但内部布局完全不同，才意识到这玩意儿躲不开。这篇文章就专门拆解 tail queue（尾队列）这套数据结构：它是什么、为什么这么设计、核心宏是怎么工作的、以及拿到一段 GNU C 内核代码时怎么快速读懂那些TAILQ_前缀的接口。

1. 尾队列和“普通双向链表”到底差在哪

1.1 传统双向链表做尾插，为什么总会卡在最后一步

大部分教材里，双向链表的节点长这样：

struct node { int data; struct node *prev; struct node *next; };

插入头、删除任意节点，都能 O(1) 完成，因为prev指针告诉你“我前面是谁”。但插入尾部就麻烦一点：你得从head一路 next 到链表末尾，才能把新节点挂上去。如果这个链表很长，尾插就是 O(n)。

于是很多人自然会想到加一个tail指针，指向最后一个节点。尾插变成 O(1)，因为直接把新节点挂到tail->next后面就行。可问题又来了：如果你删掉的恰好是最后一个节点，tail该指向谁？你只知道被删节点的prev，它确实指向倒数第二个节点，但这时候倒数第二个节点的next已经被删节点的prev断开了吗？能拿到倒数第二个节点的地址，但你不知道它是不是最后一个，必须从头再确认一遍。换句话说，只保存“尾节点本身”的地址，删除尾节点时无法 O(1) 更新。

Tail queue 解决这个问题的方法很有意思：它不保存“最后一个节点的地址”，而是保存“最后一个节点里 next 字段的地址”，或者说保存“链尾那个空位的地址”。这样，尾插可以直接把新节点填进空位，删除尾节点时也能通过这个字段地址直接改回上一个节点的 next 指针。一个看似简单的字段设计，把尾部操作彻底变成了 O(1)。

1.2 Tail Queue 和 Linux list_head 是两个流派

很多从 Linux 内核源码入手的人，会先接触include/linux/list.h里的struct list_head。那是循环双向链表：链表头本身也是链表的一个节点，head->next是第一个节点，head->prev是最后一个节点。所以它的头插、尾插、删除、遍历全是 O(1)，接口也很简洁。

而 Tail queue 来自 BSD 系的sys/queue.h，属于另一套思路。它不是循环链表，头节点和元素节点分离；它维护一个tqh_first指向第一个元素、一个tqh_last指向链尾空位；元素内部通过tqe_next和tqe_prev双向互链。Linux 内核的通用链表主要用list_head，但网络协议栈、驱动、以及大量从 BSD 移植或者对齐 BSD 行为的代码里，TAILQ_*宏经常出现。理解了两种流派的差别，读代码才不会被突然冒出来的TAILQ_INSERT_TAIL吓到。

把几个关键差异放在一起看更清晰：

list_head当然也能尾插 O(1)，所以“tail queue 存在的意义”不是说list_head做不到，而是它们各自服务不同的历史代码和设计范式。真正要理解的是 tail queue 内部的指针拓扑，这套拓扑在旧的内核代码里太常出现了。

1.3 Tail Queue 和 Simple Queue 的边界

BSD 的sys/queue.h里不止有 TAILQ，还有 SLIST（单向链表）、STAILQ（单向尾队列）、LIST（双向链表）、TAILQ（双向尾队列）。它们之间的关系可以粗略理解为：

• SLIST 是最简单的单向链表，删除任意节点要遍历找前驱。
• STAILQ 加了“尾指针”，只支持头删、尾插，适合实现严格的 FIFO 队列。
• LIST 是带prev指针的双向链表，但头插/尾插时无法直接利用尾指针。
• TAILQ 在 LIST 的基础上又加了一个特殊的“尾字段地址”，让头插、尾插、任意位置删除全部 O(1)。

所以 TAILQ 是所有队列宏里能力最全的一个。内核里如果只是入队、出队，STAILQ 足够；但如果你需要一个既能 FIFO 追加、又能在中间任意删除、还能方便前后遍历的容器，TAILQ 就是自然选择。

2. 摊开内存布局：两个头字段 + 两个挂点字段

2.1 TAILQ_HEAD 宏生成的头结构

在常见的sys/queue.h里，头结构由这么个宏生成：

#define TAILQ_HEAD(name, type) \ struct name { \ struct type *tqh_first; /* 队首元素 */ \ struct type **tqh_last; /* 链尾 next 字段的地址 */ \ }

比如你写：

TAILQ_HEAD(app_queue, app_item);

实际上展开成：

struct app_queue { struct app_item *tqh_first; struct app_item **tqh_last; };

tqh_first好懂，就是普通的头指针。关键是tqh_last，它的类型不是struct app_item *，而是struct app_item **，也就是“指向一个struct app_item *指针的指针”。头结构里只有两个字段，但这两个字段合起来，就足以描述一条线性双链。

2.2 TAILQ_ENTRY 宏生成的元素挂点

元素结构内部需要埋一个“挂点”，由TAILQ_ENTRY生成：

#define TAILQ_ENTRY(type) \ struct { \ struct type *tqe_next; /* 下一个元素 */ \ struct type **tqe_prev; /* 上一个元素的 next 字段地址 */ \ }

使用方式是在你自己的结构体里嵌入一份：

struct app_item { int id; char payload[64]; TAILQ_ENTRY(app_item) link; };

link展开出来就是两个成员：tqe_next和tqe_prev。注意tqe_prev也是指针的指针，它保存的永远是“谁指向了我”。如果我是第二个元素，那tqe_prev保存的是第一个元素tqe_next字段的地址；如果我是第一个元素，那tqe_prev保存的是头结构里tqh_first字段的地址。

这个设计和传统双向链表最大的不同点就在这里：传统链表里prev保存的是上一个节点的地址，而 TAILQ 的tqe_prev保存的是“上一个节点里指向我的那个指针的地址”。

2.3 一个空队列和三个节点的具体样子

先用空队列热身：

struct app_queue q; TAILQ_INIT(&q);

内存布局是这样的：

q.tqh_first = NULL; q.tqh_last = &q.tqh_first; // 指向自己的 tqh_first

tqh_last指向tqh_first本身，意思就是“目前链尾的空位就是队首那一个指针”。这时候执行尾插，往tqh_first里写入新节点地址就行。

假设队列里已经有 A、B、C 三个节点，布局是：

q.tqh_first -----------> A -----------> B -----------> C -----------> NULL ^ ^ ^ q.tqh_last | | A.tqe_prev B.tqe_prev C.tqe_prev

更准确地说：

q.tqh_first = A A.tqe_next = B A.tqe_prev = &q.tqh_first B.tqe_next = C B.tqe_prev = &A.tqe_next C.tqe_next = NULL C.tqe_prev = &B.tqe_next q.tqh_last = &C.tqe_next

看到没有，q.tqh_last指向的是 C 的tqe_next字段所在的地址，而不是 C 这个结构体本身。这个细节就是 TAILQ 的精髓。

2.4 用“停车位”类比记住 tqh_last

可以把队列想成一条带固定顺序的停车位。tqh_first是第一个车位，tqh_last不是“最后一辆车”，而是“最后一个空位”。车要进场，直接停进最后一个空位，然后把空位标记移动到新车的后面；车要离场，如果它是最后一辆，就把空位标记往前挪到前一辆车的尾巴上。

很多人在读 TAILQ 宏时，卡住的地方都是*(head)->tqh_last = (elm)这行。你只要把tqh_last翻译成“当前链尾那个什么都没装的槽位”，这行代码就变成了：往槽位里塞进新元素。这样理解，后面所有宏都很顺。

3. 核心宏逐行拆解

3.1 TAILQ_INIT 和空队列检查

初始化宏是：

#define TAILQ_INIT(head) do { \ (head)->tqh_first = NULL; \ (head)->tqh_last = &(head)->tqh_first; \ } while (0)

tqh_last指向tqh_first这一点非常重要。这会让“空队列尾插”和“非空队列尾插”共用同一套逻辑，不需要在宏里单独判断当前有没有元素。因为空队列时，*(head)->tqh_last写进去的正好就是head->tqh_first。

判断空队列也很直接：

#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)

不需要遍历，也不需要看尾指针，只看tqh_first是否为 NULL。

3.2 TAILQ_INSERT_HEAD：头部插入的细节

头插宏的具体形式通常是：

#define TAILQ_INSERT_HEAD(head, elm, field) do { \ if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next; \ else \ (head)->tqh_last = &(elm)->field.tqe_next; \ (head)->tqh_first = (elm); \ (elm)->field.tqe_prev = &(head)->tqh_first; \ } while (0)

逐行看：

1. 先把新元素elm的tqe_next指向旧队首。如果旧队首存在，就得把旧队首的tqe_prev改成新元素tqe_next的地址，因为旧队首现在的前驱变成新元素了。
2. 如果旧队首不存在，说明这是空队列插入。空队列时，tqh_last是指向tqh_first的，但插入一个节点后，tqh_last应该指向这个新节点tqe_next字段的地址。所以这里要更新head->tqh_last。
3. 让head->tqh_first指向新元素。
4. 把新元素的tqe_prev指向&head->tqh_first。

这段代码最容易被忽略的是那个else分支。如果漏了，在空队列上执行头插，tqh_last就不会被更新，后续尾插会写到错误的位置。

3.3 TAILQ_INSERT_TAIL：尾部插入为什么 O(1)

尾插宏是：

#define TAILQ_INSERT_TAIL(head, elm, field) do { \ (elm)->field.tqe_next = NULL; \ (elm)->field.tqe_prev = (head)->tqh_last; \ *(head)->tqh_last = (elm); \ (head)->tqh_last = &(elm)->field.tqe_next; \ } while (0)

一共四步：

1. 新元素后面没有元素，所以tqe_next置 NULL。
2. 新元素的tqe_prev保存的是“当前链尾空位的地址”，也就是(head)->tqh_last当前的值。
3. 把新元素写进那个空位。如果队列是空的，这一步等价于head->tqh_first = elm；如果队列非空，这一步等价于old_tail->tqe_next = elm。
4. 更新head->tqh_last，让链尾空位变成新元素的tqe_next字段地址。

因为从头到尾都没有遍历，只是修改几个指针，所以尾插是 O(1)。这里最核心的一点：第 3 步中，我们完全不需要知道旧的尾节点是谁，只要往tqh_last指向的槽位里写值就行。

3.4 TAILQ_INSERT_AFTER 和 TAILQ_INSERT_BEFORE

在中间某个节点listelm后面插入：

#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL) \ (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next; \ else \ (head)->tqh_last = &(elm)->field.tqe_next; \ (listelm)->field.tqe_next = (elm); \ (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ } while (0)

逻辑和头插很像，只是把“旧队首”换成了“listelm 的后继”。如果listelm是尾节点，那么它的tqe_next是 NULL，插入后head->tqh_last要更新为新元素的tqe_next字段地址。

在listelm前面插入：

#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ (elm)->field.tqe_next = (listelm); \ *(listelm)->field.tqe_prev = (elm); \ (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ } while (0)

这里最漂亮的一点是*(listelm)->field.tqe_prev = (elm)，因为tqe_prev保存的是“谁指向我”的地址，所以这一行不管 listelm 是队首还是中间节点，都能正确地把前驱的 next 指针改成新元素。不需要判断“listelm 是不是队首”。

3.5 TAILQ_REMOVE：尾节点特判是关键

删除宏是：

#define TAILQ_REMOVE(head, elm, field) do { \ if (((elm)->field.tqe_next) != NULL) \ (elm)->field.tqe_next->field.tqe_prev = \ (elm)->field.tqe_prev; \ else \ (head)->tqh_last = (elm)->field.tqe_prev; \ *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ } while (0)

这里的分支逻辑是理解 TAILQ 的另一个分水岭。

如果被删节点elm不是尾节点，那么就有后继节点存在。后继节点的tqe_prev应该从“指向 elm 的前驱槽位”改成“指向 elm 的前驱槽位”，这个值就是(elm)->field.tqe_prev。所以：

elm->tqe_next->tqe_prev = elm->tqe_prev;

如果被删节点是尾节点，它的tqe_next是 NULL，不存在后继来改tqe_prev。这时候需要更新的是头结构里的tqh_last。elm->tqe_prev保存的正好是“链尾空位应该回到哪里”，所以：

head->tqh_last = elm->tqe_prev;

最后统一执行：

*(elm)->field.tqe_prev = (elm)->field.tqe_next;

这行把前驱的 next（或者头结构的 tqh_first）直接改成被删节点的后继。由于前一步已经把tqh_last修正了，这行不用区分双向链表里常见的一堆 if-else，一行就能完成删除。

3.6 TAILQ_FOREACH 和 TAILQ_FOREACH_SAFE

正向遍历宏：

#define TAILQ_FOREACH(var, head, field) \ for ((var) = ((head)->tqh_first); \ (var); \ (var) = ((var)->field.tqe_next))

这是最经典的遍历写法。但如果在遍历过程中删除了当前节点，循环体第三部分再访问(var)->field.tqe_next就可能出问题，因为节点已经被释放或断链。所以标准库里还有安全遍历：

#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ for ((var) = TAILQ_FIRST(head); \ (var) && ((tvar) = TAILQ_NEXT(var, field), 1); \ (var) = (tvar))

它用额外的tvar在进入循环体之前就把“下一个节点”缓存下来。这样你在循环体里删除var也不影响下一步移动。

3.7 几个加分组：REPLACE 和 CONCAT

替换节点elm为elm2：

#define TAILQ_REPLACE(head, elm, elm2, field) do { \ if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ (elm2)->field.tqe_next->field.tqe_prev = &(elm2)->field.tqe_next; \ else \ (head)->tqh_last = &(elm2)->field.tqe_next; \ (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ *(elm2)->field.tqe_prev = (elm2); \ } while (0)

本质上就是删除elm再插入elm2的合体版，但省去了一次指针往返。合并两个队列用TAILQ_CONCAT，它把head2整条链接到head1尾部，然后重新初始化head2。实际内核代码里合并队列的诉求经常出现，这个宏是高效完成这件事的标准做法。

4. 为什么内核会反复用宏实现“泛型队列”，而不是封装成函数

4.1 C 语言里最早的泛型手段就是宏

内核代码大量使用宏来实现“任意结构体可复用”的算法，不是因为宏有多优雅，而是因为 C 语言没有 C++ 模板、没有现代泛型。你要写一个“队列模板”，在 C 里最直接的办法就是让宏接受结构体类型和挂点字段名。

TAILQ_HEAD(app_queue, app_item)接受app_item类型；TAILQ_INSERT_TAIL(&q, item, link)接受挂点字段名link。宏展开后，所有操作都针对你传入的具体类型生成代码。这既保留了类型上的直观性，又避免了为每种结构体手写一份队列函数。

4.2 副作用提醒：宏不是安全的函数

宏的好处是灵活、内联，坏处是参数副作用可能被执行多次。看这个宏片段：

(elm)->field.tqe_next = NULL

如果elm本身是一个带副作用的表达式，比如get_next_item()，那这个函数可能被调用多次，行为不可预测。所以内核代码和用户态代码里，调用TAILQ_*宏时一般传简单变量、指针成员表达式，不会在宏参数里做复杂的函数调用。

另外宏不检查类型。如果你把TAILQ_ENTRY(apple)的挂点字段传给了TAILQ_INSERT_TAIL(orange_queue, ..., link)，编译器大概率只会给你一堆晦涩的指针类型警告，不会有一行清晰报错。碰到这种问题，先检查“传入的节点是否属于该队列声明的类型”。

4.3 对比：list_head 的接口是函数，TAILQ 的接口是宏

Linux 的list_head提供的是list_add_tail()、list_del()这种函数接口，配合container_of()使用，原因是内核希望统一抽象。BSD 系 TAILQ 则把模板逻辑写在宏里，调用时需要自己保证类型一致。两种风格没有绝对优劣，但读代码时必须知道：看到list_del()，你就去分析循环链表环形结构；看到TAILQ_REMOVE()，你就要记得它同时维护了tqh_last这个尾空位指针。

5. 实际验证：在用户态把 TAILQ 完整跑一遍

5.1 glibc 自带 sys/queue.h，可以直接实验

Linux 的 glibc 里带了/usr/include/sys/queue.h，提供 BSD 风格的队列宏，而且它也包含TAILQ_*。所以你不需要真的写内核模块，就可以在普通用户态程序里验证全部行为。这个文件对理解 TAILQ 非常方便，我强烈建议你先在用户态跑通，再回内核源码里对照。

写一个简单的任务队列：

#include <stdio.h> #include <stdlib.h> #include <sys/queue.h> struct task { int id; TAILQ_ENTRY(task) link; }; TAILQ_HEAD(task_queue, task); int main(void) { struct task_queue q; struct task *np, *tmp; int i; TAILQ_INIT(&q); for (i = 0; i < 5; i++) { struct task *t = malloc(sizeof(*t)); t->id = i; TAILQ_INSERT_TAIL(&q, t, link); } printf("正序: "); TAILQ_FOREACH(np, &q, link) printf("%d ", np->id); printf("\n"); TAILQ_FOREACH_SAFE(np, &q, link, tmp) { if (np->id == 2) { TAILQ_REMOVE(&q, np, link); free(np); break; } } while (!TAILQ_EMPTY(&q)) { np = TAILQ_FIRST(&q); TAILQ_REMOVE(&q, np, link); printf("pop %d\n", np->id); free(np); } return 0; }

编译运行：

gcc -Wall -o tailq_demo tailq_demo.c ./tailq_demo

预期输出：

正序: 0 1 2 3 4 pop 0 pop 1 pop 3 pop 4

id 为 2 的节点被安全删除，剩下的节点按原有顺序全部出队。

5.2 我在测试中踩过的三个坑

第一个坑：忘记TAILQ_INIT。如果你定义了头结构就直接TAILQ_INSERT_TAIL，tqh_last还没指向tqh_first，写入操作会落到随机地址，程序直接段错误。这类问题不好查，因为不是每次都会稳定复现，和栈上残留数据有关。凡是声明头结构，要么调用TAILQ_INIT，要么用TAILQ_HEAD_INITIALIZER做静态初始化。

第二个坑：在TAILQ_FOREACH里删除当前节点。如果不使用FOREACH_SAFE，删除后循环第三段表达式会访问已被释放节点的tqe_next，可能崩溃，也可能只是读到脏值。正确做法是用SAFE变体，或者删除后立刻break退出遍历。

第三个坑：删除节点后，没有把被删节点的tqe_next和tqe_prev置 NULL，然后再次对同一个节点执行TAILQ_REMOVE。第二次删除时，tqe_prev不再指向有效的链内容，会把无关内存写坏。所以“移出队列后复用一个节点”时，要么重新初始化该节点的挂点字段，要么干脆重新分配内存。

5.3 用 gdb 观察指针的指法

如果你在用户态跑上面的 demo，用 gdb 在TAILQ_INSERT_TAIL那行打断点，观察head->tqh_last的值，会发现它确实等于某个元素tqe_next字段的地址，而不是元素地址。这一点亲眼看到一次，比读十遍宏定义都管用。调试命令大致是：

gdb ./tailq_demo break tailq_demo.c:20 run print q print q.tqh_last print *(q.tqh_last)

*(q.tqh_last)是 NULL，因为tqh_last指向的是链尾那个空槽位。继续插入几个节点后再看，*(q.tqh_last)仍然指向 NULL，但tqh_last的地址已经随着尾节点不断后移。这个观察能直接验证“tqh_last 不是尾节点指针，而是尾空位指针”。

6. 内核代码和跨平台项目里怎么认出 Tail Queue

6.1 看到 TAILQ_HEAD 和 TAILQ_ENTRY 的声明组合

内核或驱动代码里，一个典型的尾队列会像这样出现：

struct page_buf { uint32_t offset; char data[128]; TAILQ_ENTRY(page_buf) free_link; }; TAILQ_HEAD(page_buf_list, page_buf); struct page_buf_list free_pages;

先用TAILQ_ENTRY在结构体里声明挂点，再用TAILQ_HEAD声明队列头类型，然后定义一个队列头变量。当你看到这种“结构体内嵌挂点 + 头结构变量”的组合，就要意识到这不是普通的链表字段，而是完整的队列管理系统。

遍历时：

struct page_buf *pb; TAILQ_FOREACH(pb, &free_pages, free_link) { /* 这里拿到的 pb 直接就是宿主结构指针 */ }

有的链表实现需要container_of从挂点反推宿主，TAILQ 宏因为直接按宿主类型生成代码，遍历时拿到手的就是宿主指针，使用上更直白。

6.2 看 TCP 协议栈、驱动队列时迷路的排查思路

一旦确认代码用的是 TAILQ，排查思路应该是：

1. 先找TAILQ_INIT(&queue)在哪里，确认初始化过。
2. 找到所有TAILQ_INSERT_HEAD、TAILQ_INSERT_TAIL、TAILQ_INSERT_AFTER的调用点，看哪些路径会影响队列关系。
3. 找到TAILQ_REMOVE的调用点，特别关注是否在中断上下文和进程上下文之间共享，共享时有没有锁保护。
4. 如果是产品代码，在出队后立刻看queue.tqh_first是否符合预期，用断言把结构关系锁住。

6.3 跨平台兼容代码里经常见到适配头文件

有些项目为了同时兼容 Linux、BSD、以及其他内核环境，会自带一份queue.h或者用系统自带的sys/queue.h。你会在代码里看到类似“如果这个宏不存在就先 include 本地 queue.h”的条件编译。这种时候，TAILQ 的行为可能因不同发行版对宏的实现细节略有差异，但tqh_first、tqh_last、tqe_next、tqe_prev这四个字段名基本通用，按上面讲的内存布局理解不会有偏差。

6.4 内核为什么不用现成的容器库

内核运行环境要求零动态分配依赖、确定性延迟、精确控制内存布局。C++ 标准库容器在不少场景太重，也不符合内核代码风格。宏模板式的 TAILQ 正好满足“需要什么就展开什么、不要多余代码”的要求。它不引入任何样式，底层就是裸指针的位移和赋值，编译器优化后往往就是几条内存操作指令，性能非常可控。

最后说一个我自己总结的记忆方法：tqh_last永远不要当成“最后一个对象”，要当成“最后一个空位”。所有插入操作的本质都是“把新对象放进当前空位，再更新空位地址”；所有删除操作的本质都是“绕过当前对象，必要时把空位地址回退到前一个对象”。我后来读 BSD 协议栈里那些频繁入队、出队、遍历的代码时，用这个视角看，几乎没有再迷路过。如果你也在啃内核数据结构，建议先启动一个用户态 demo，亲手打几个断点，再回去读源码，效果会比直接硬啃宏定义好得多。