我最早看到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吓到。把几个关键差异放在一起看更清晰对比点Linux list_headTail Queue链表形态循环双向链表头节点参与成环非循环双向链表头结构独立空链状态head-next headtqh_first NULL找尾节点直接取head-prev通过tqh_last间接得到常用的节点指针prev保存前一个节点内部list_head的地址tqe_prev保存上一个节点tqe_next字段的地址适用场景Linux 内核内部的通用需求BSD 系风格、跨平台代码、协议栈移植场景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_firsttqh_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)逐行看先把新元素elm的tqe_next指向旧队首。如果旧队首存在就得把旧队首的tqe_prev改成新元素tqe_next的地址因为旧队首现在的前驱变成新元素了。如果旧队首不存在说明这是空队列插入。空队列时tqh_last是指向tqh_first的但插入一个节点后tqh_last应该指向这个新节点tqe_next字段的地址。所以这里要更新head-tqh_last。让head-tqh_first指向新元素。把新元素的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)一共四步新元素后面没有元素所以tqe_next置 NULL。新元素的tqe_prev保存的是“当前链尾空位的地址”也就是(head)-tqh_last当前的值。把新元素写进那个空位。如果队列是空的这一步等价于head-tqh_first elm如果队列非空这一步等价于old_tail-tqe_next elm。更新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 4id 为 2 的节点被安全删除剩下的节点按原有顺序全部出队。5.2 我在测试中踩过的三个坑第一个坑忘记TAILQ_INIT。如果你定义了头结构就直接TAILQ_INSERT_TAILtqh_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 Queue6.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排查思路应该是先找TAILQ_INIT(queue)在哪里确认初始化过。找到所有TAILQ_INSERT_HEAD、TAILQ_INSERT_TAIL、TAILQ_INSERT_AFTER的调用点看哪些路径会影响队列关系。找到TAILQ_REMOVE的调用点特别关注是否在中断上下文和进程上下文之间共享共享时有没有锁保护。如果是产品代码在出队后立刻看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亲手打几个断点再回去读源码效果会比直接硬啃宏定义好得多。