内核级数据结构：侵入式链表 (Intrusive List) 之美

学习过数据结构的同学，写出来的链表通常是这样的（非侵入式）：

struct Node {
    void *data;       // 指向用户数据
    struct Node *next;
};

这种设计的问题在于：它需要两次内存分配（一次给用户数据，一次给节点本身），且节点和数据在内存中是不连续的，对 CPU Cache 极其不友好。

1. 什么是侵入式链表？

侵入式链表（Intrusive List）的思想是：把链表节点直接“埋”在用户数据结构里。

// 链表节点定义（不包含数据！）
struct list_head {
    struct list_head *next, *prev;
};

// 用户数据
struct Task {
    int pid;
    char name[16];
    struct list_head list; // <--- 嵌入在这里
};

Linux 内核源代码中几乎所有的链表都是这种设计。

2. 黑魔法：container_of

现在问题来了：我们拿到了链表节点 struct list_head *ptr，怎么反推回包含它的 struct Task 的首地址？

我们需要用到 C 语言中最著名的宏之一：container_of。

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

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

原理拆解

offsetof：计算 list 成员相对于 struct Task 起始位置的偏移量（字节数）。
ptr 是当前 list 成员的地址。
ptr - offset，自然就是 struct Task 的起始地址！

3. 优势分析

3.1 零内存分配 (No Malloc)

链表节点是用户结构体的一部分。当你创建了一个 Task 的时候，节点内存就已经分配好了。把任务加入队列，根本不需要 malloc 新的节点。这对于由于内存碎片而禁止使用堆的嵌入式系统来说，简直是福音。

3.2 缓存友好 (Cache Locality)

虽然节点本身不存数据，但因为节点就嵌在数据结构里，访问完链表指针，紧接着访问数据 (task->pid) 时，数据很大概率已经在 L1 Cache 里了。

3.3 多态且通用

一个数据结构可以同时存在于多个链表中。

struct Task {
    // ...
    struct list_head ready_list;   // 在就绪队列
    struct list_head wait_list;    // 在等待队列
};

完全不需要修改链表库的代码，也不需要晦涩的 void * 转换。

4. 总结

侵入式链表是 C 语言“指针运算”特性的巅峰应用。它牺牲了一点点类型安全性（还是需要小心强转），换来了极致的性能和灵活性。

hello world