Linux 内核链表分析与实现原理

链表

链表是开发者学习数据结构时最初的一种数据结构，它的应用是非常广泛的。而且在实际的开发，特别是面试中，对链表的各种应用都是无法绕开的。一些常见的算法也是以链表为基础的。链表的应用形式有很多，一般在教材中学习到的也就是开发中常见到的链表其基本的应用方式如下：

// 双向链表
struct list {
    int iValue;
    int *pData;
    struct list *pNext; // 下一个节点
    struct list *pPrev; // 前一个节点
};

可以把链表当成一个一个索链的结点，它们通过指针象'铁环一样'紧紧的链接在一起，形成一条索链一样的表。

内核链表与传统链表对比

看过内核源码的开发者可能在内核中也看到过链表的定义形势，会发现与教材中的传统的链表有些不同。下面先看一下内核中的代码的链表定义：

// 双向链表
struct list_head {
    struct list_head *next, *prev;
};
// linux-6.9.12/virt/kvm/eventfd.c
struct ioeventfd {
    struct list_head list;
    u64 addr;
    int length;
    struct eventfd_ctx *eventfd;
    u64 datamatch;
    struct kvm_io_device dev;
    u8 bus_idx;
    bool wildcard;
};

把上面的链表代码和教材中的链表代码比较，大家可以发现有什么不同么？最典型的就是教材中的链表包含着数据本身，而在内核中则是数据本身包含链表（这样说可能不太准确，但容易理解）。所以内核中这种链表也可以称为侵入式链表。另外，这种链表可以嵌入到任何的数据结构中形成链表，其通用性非常强，应用非常灵活。对于这种链表，其具体的操作时间复杂度为 O(1)，相对来说要稳定，同时，这种链表不再参与数据本身的内存分配和回收，在设计上将数据结构与数据进行了解耦。最后，这种数据链表内存中的数据存储连续，对缓存友好，访问速度快。这也是内核中使用这种链表的一个重要原因。