理解并使用Linux内核链表

1. 引言

1.1 什么是链表？

链表，这东西就像是你小时候玩的串珠子游戏，只不过这里的“珠子”变成了一个个节点，每个节点除了有自己的“颜色”（数据）之外，还有一根线（指针）连着下一个珠子。这样一来，即使珠子们散落在内存的各个角落，我们也能通过那根线把它们串起来。在Linux内核中，链表的应用简直无处不在，特别是在内存管理、进程调度、文件系统等领域。因为它们不仅能灵活地增删节点，还能大大减少内存分配和回收的麻烦，让我们的系统跑得更快更稳。

1.2 内核链表的特点

  • 简洁性：内核里的链表结构简单到不能再简单了，主要就是struct list_head，里面只有两个指针，一个指向前一个节点，另一个指向后一个节点。这样不仅节省了宝贵的内存空间，还让链表的维护变得超级简单。
  • 高效性：双向链接的设计，让内核链表在插入和删除节点时特别快，完全不用挨个找节点，直接就搞定了。想象一下，如果你在一堆珠子里想快速拿走一个，是不是直接拉出来就好，而不是一个一个数？
  • 模块化：内核链表设计得非常模块化，提供了一堆宏和函数，比如list_add()、list_del()等，让你在不同的地方都能轻松上手，玩转链表。这就像是你有一套万能工具箱，无论遇到什么问题，总能找到合适的工具。
  • 操作与数据分离：这是内核链表的一大亮点。链表的操作（比如插入、删除）和节点的数据是分开的。struct list_head只负责串珠子，真正的数据则藏在更大的结构里。这样设计的好处是，无论节点的数据是什么，链表都能灵活管理，不用为每种数据重新定义链表结构。这就像你有一个通用的挂钩，可以挂任何东西，而不需要为每件东西单独设计一个挂钩。

2. C语言课程中的链表与Linux内核链表对比

在我们深入内核链表之前，先来看看C语言课上的链表是怎么回事。

2.1 数据结构

  • C语言课程中的链表：在课堂上，链表通常以一个简单的节点结构呈现，每个节点至少包含一个数据字段和一个指向下一个节点的指针。对于双向链表，则会增加一个指向前一个节点的指针。这种实现方式有助于初学者理解和实践链表的基本概念。想象一下，你手里拿着一张纸条，上面写着数字，然后用一根线连着下一张纸条，这就是最简单的链表了。

    struct Node {
    int data;
    struct Node *next;
    struct Node *prev; // 双向链表特有
};

  • Linux内核链表：内核中的链表结构更加抽象，主要依赖于struct list_head，它不直接持有数据，而是作为一个链表元素的连接点存在。实际的数据通常嵌入到包含struct list_head的更大结构中。这种设计增加了灵活性，允许链表元素携带任何类型的数据。这就像是你有一个通用的挂钩，可以挂任何东西，而不需要为每件东西单独设计一个挂钩。

    struct list_head {
    struct list_head *next, *prev;
};

struct my_data {
    int value;
    struct list_head list;
};

2.2 应用场景

  • C语言课程中的链表：其主要目的是教授学生数据结构的基础知识和编程技能，如链表的创建、遍历、添加和删除节点等。此外，也强调了内存管理和错误处理的重要性，为后续学习更复杂的数据结构和算法奠定基础。这就像你在学骑自行车，先从平衡车开始，再慢慢过渡到有辅助轮的自行车。
  • Linux内核链表：在实际的系统开发中，内核链表的设计更加关注于性能和安全性。它广泛应用于内核的各个部分，如任务调度、文件系统管理和设备驱动程序中，是实现系统高效运行的关键技术之一。这就像你已经熟练掌握了自行车，现在开始骑摩托车，速度更快，功能更强大。

总之，内核链表的这些特点使其成为Linux内核中不可或缺的一部分，为系统的高效和稳定运行提供了坚实的基础。接下来，我们将深入探讨内核链表的具体实现。

3. 内核链表的定义和初始化

3.1 struct list_head的定义和意义

struct list_head是Linux内核中链表节点的基础结构体，设计极其简洁，包含两个指针：next和prev。这两个指针分别指向链表中的下一个节点和前一个节点，从而实现了双向链表的结构。每个链表节点通过这两个指针与其他节点连接，从而能够实现高效的增删查操作。

struct list_head {
    struct list_head *next, *prev;
};
  • next：指向链表中下一个节点。
  • prev：指向链表中前一个节点。

内核链表的这种设计没有包含数据部分，数据部分通常存储在其它结构体中，而链表节点通过嵌入的struct list_head来实现链接。这样的设计使得链表操作更加灵活和高效。这就像是你有一个通用的挂钩，可以挂任何东西，而不需要为每件东西单独设计一个挂钩。

3.2 双向链表的特点与对比

双向链表与单向链表相比，具有以下特点：

  • 双向链表：每个节点不仅有指向下一个节点的指针（next），还拥有指向前一个节点的指针（prev）。这种设计允许我们从链表的任意位置进行双向遍历，从而提升了遍历和修改节点的灵活性。想象一下，你不仅可以从头到尾走一遍，还可以从尾到头走一遍，是不是方便多了？
  • 单向链表：每个节点只包含一个指向下一个节点的指针。要删除或修改某个节点，通常需要从链表头部开始遍历，找到其前驱节点，这在某些情况下可能导致较低的效率。这就像是你只能从头走到尾，想回头还得重新走一遍。

为什么选择双向链表？

  • 更高效的节点插入/删除：由于双向链表中每个节点都知道自己的前驱节点，删除或插入节点时，不需要遍历整个链表来找到前驱节点，操作可以在常数时间内完成。这就像是你有一个双向的传送门，可以直接跳到你想去的地方。
  • 双向遍历：双向链表使得我们可以从链表的尾部开始遍历，而不仅仅是从头部开始。这在某些操作中是非常有用的，比如在进程调度、内存管理等内核模块中。这就像是你有两个方向的电梯，上下都可以。

3.3 使用INIT_LIST_HEAD宏初始化链表

INIT_LIST_HEAD是内核提供的宏，用于初始化一个空链表。当你创建一个链表头时，你可以使用此宏将其next和prev指针都指向自身，表示这是一个空链表。

示例：

struct list_head my_list;
INIT_LIST_HEAD(&my_list);

这个宏的作用是将my_list的next和prev指针都指向自己，表示链表为空，且可以开始向其中添加节点。这就像是你刚刚打开了一扇新的门，准备迎接新的挑战。

3.4 LIST_HEAD_INIT与LIST_HEAD的区别与应用

  • LIST_HEAD_INIT：用于静态初始化链表头，适用于在编译时已知链表头，并希望将其初始化为一个空链表。它不会像INIT_LIST_HEAD那样在运行时进行初始化。

    示例：

    struct list_head my_list = LIST_HEAD_INIT(my_list);

    这个宏定义了一个链表头my_list，并将其初始化为一个空链表。这就像是你已经准备好了一切，随时可以开始行动。

  • LIST_HEAD：这是一个用于声明并初始化链表头的宏。在声明时，它不仅定义了一个list_head类型的变量，还会自动初始化它为一个空链表。

    示例：

    LIST_HEAD(my_list);

    该宏既声明了一个链表头变量my_list，又自动调用INIT_LIST_HEAD进行初始化。这就像是你一眨眼，所有准备工作都完成了。

3.5 内核链表初始化的代码示例与剖析

下面是一个简单的示例，演示了如何创建和初始化链表，以及如何向链表中添加节点。

#include <linux/list.h>

struct my_data {
    int value;
    struct list_head list;
};

int main() {
    // 创建链表头
    struct list_head my_list;
    INIT_LIST_HEAD(&my_list);

    // 创建两个数据节点
    struct my_data data1 = { .value = 10 };
    struct my_data data2 = { .value = 20 };

    // 将data1添加到my_list的头部
    list_add(&data1.list, &my_list);

    // 将data2添加到my_list的尾部
    list_add_tail(&data2.list, &my_list);

    return 0;
}

代码分析：

  • INIT_LIST_HEAD(&my_list)：初始化一个空链表头my_list，这时链表是空的，my_list.next和my_list.prev都指向自己。这就像是你刚刚打开了一扇新的门，准备迎接新的挑战。
  • list_add(&data1.list, &my_list)：将data1节点插入到链表my_list的头部。此时，data1.list.prev指向my_list，data1.list.next指向链表中的第一个节点（如果有的话）。这就像是你把一个新的珠子加到了项链的最前面。
  • list_add_tail(&data2.list, &my_list)：将data2节点插入到链表my_list的尾部，data2.list.prev指向链表中的最后一个节点，data2.list.next指向my_list。这就像是你把一个新的珠子加到了项链的最后面。

这段代码展示了如何在内核中使用链表头来组织节点，并利用list_add和list_add_tail来分别在链表头部和尾部添加节点。这就像是你有了一个强大的工具箱，可以轻松地组装和拆卸珠子。

3.6 小结

  • struct list_head是Linux内核链表的基本结构，包含两个指针（next和prev），实现了双向链表。
  • 双向链表在内核中的使用具有高效的插入/删除和双向遍历优势。
  • 内核链表的初始化可以通过INIT_LIST_HEAD、LIST_HEAD_INIT或LIST_HEAD来实现，根据不同的场景选择合适的初始化方式。

通过掌握链表的初始化，我们为下一步的链表操作（如添加、删除、遍历等）做好了准备。在接下来的部分，我们将深入探讨链表节点的增删改查操作。这就像你已经学会了如何打开门，接下来就要学会如何自如地进出房间了。

4. 链表的核心操作

在Linux内核中，链表的核心操作包括添加节点、删除节点、遍历链表等。通过这些操作，内核能够高效地管理各种数据结构。接下来，我们将详细讨论这些核心操作，并结合实际例子进行讲解。

4.1 添加节点操作

在Linux内核链表中，添加节点的操作有两个常用的宏：list_add和list_add_tail。它们用于将节点插入到链表的不同位置。

  • list_add：在链表的头部插入节点。

    原型：

    void list_add(struct list_head *new, struct list_head *head);
    • new：指向新节点的指针。
    • head：指向链表头部的指针。

    list_add会将新节点插入到链表的头部，并更新头部节点的指针。这就像是你把一个新的珠子加到了项链的最前面。

    示例：

    struct my_data data1 = { .value = 10 };
list_add(&data1.list, &my_list);

  • list_add_tail：在链表的尾部插入节点。

    原型：

    void list_add_tail(struct list_head *new, struct list_head *head);
    • new：指向新节点的指针。
    • head：指向链表头部的指针。

    list_add_tail将新节点插入到链表的尾部，并更新尾部节点的指针。这就像是你把一个新的珠子加到了项链的最后面。

    示例：

    struct my_data data2 = { .value = 20 };
list_add_tail(&data2.list, &my_list);

4.2 删除节点操作

删除节点是链表操作中非常重要的一部分。内核提供了几个宏来处理节点的删除。常用的删除操作有list_del和list_del_init。

  • list_del：删除指定节点。

    原型：

    void list_del(struct list_head *entry);
    • entry：指向要删除节点的指针。

    list_del会将节点从链表中移除，但不会对该节点进行初始化。如果节点被删除后不再使用，最好使用list_del_init。这就像是你从项链上取下了一个珠子，但还没有把它放好。

    示例：

    list_del(&data1.list); // 删除data1节点

  • list_del_init：删除指定节点并初始化该节点为一个空链表。

    原型：

    void list_del_init(struct list_head *entry);
    • entry：指向要删除并初始化的节点指针。

    list_del_init会将节点从链表中移除，并将该节点的next和prev指针指向自己，表示这是一个空节点。这就像是你从项链上取下了一个珠子，并把它放在一个安全的地方。

    示例：

    list_del_init(&data1.list); // 删除并初始化data1节点

4.3 遍历链表

遍历链表是链表操作中的另一项常见操作。内核提供了多种方式来遍历链表：

  • list_for_each：遍历链表中的所有节点。

    原型：

    #define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
    • pos：指向链表当前节点的指针。
    • head：指向链表头部的指针。

    list_for_each宏遍历链表中的所有节点，直到head节点再次出现。这就像是你沿着项链一颗一颗地检查珠子。

    示例：

    struct list_head *pos;
list_for_each(pos, &my_list) {
    struct my_data *data = list_entry(pos, struct my_data, list);
    printk("%d\n", data->value);
}

    list_entry宏用于从链表节点获取实际的数据结构。这就像是你从项链上取下一个珠子，看看它的颜色。

  • list_for_each_safe：遍历链表并支持在遍历过程中删除节点。

    原型：

    #define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
    • pos：指向当前节点的指针。
    • n：指向当前节点的下一个节点的指针，用于避免在遍历过程中删除当前节点时发生指针失效。
    • head：链表头部指针。

    list_for_each_safe适用于在遍历链表时，如果需要删除节点，可以安全地避免丢失链表中的后续节点。这就像是你一边检查项链，一边可以安全地取下某些珠子。

    示例：

    struct list_head *pos, *n;
list_for_each_safe(pos, n, &my_list) {
    struct my_data *data = list_entry(pos, struct my_data, list);
    if (data->value == 20) {
        list_del(pos);
        kfree(data); // 删除节点并释放内存
    }
}

  • list_for_each_entry：遍历链表中的结构体元素。

    原型：

    #define list_for_each_entry(pos, head, member) \
    for (pos = list_entry((head)->next, typeof(*pos), member); &pos->member != (head); pos = list_entry(pos->member.next, typeof(*pos), member))
    • pos：指向当前链表节点数据部分的指针。
    • head：链表头部指针。
    • member：指向list_head的成员名。

    list_for_each_entry宏不仅遍历链表节点，还可以直接访问结构体中的数据成员。这就像是你直接检查每个珠子的颜色，而不需要先取下来再看。

    示例：

    struct my_data *data;
list_for_each_entry(data, &my_list, list) {
    printk("%d\n", data->value);
}

  • list_for_each_entry_safe：类似于list_for_each_entry，但是支持在遍历过程中删除节点。

    原型：

    #define list_for_each_entry_safe(pos, n, head, member) \
    for (pos = list_entry((head)->next, typeof(*pos), member), n = list_entry(pos->member.next, typeof(*n), member); &pos->member != (head); pos = n, n = list_entry(n->member.next, typeof(*n), member))

    list_for_each_entry_safe宏在遍历过程中安全地删除节点，避免丢失后续节点。这就像是你一边检查每个珠子的颜色，一边可以安全地取下某些珠子。

    示例：

    struct my_data *data, *tmp;
list_for_each_entry_safe(data, tmp, &my_list, list) {
    if (data->value == 10) {
        list_del(&data->list);
        kfree(data); // 删除节点并释放内存
    }
}

4.4 小结

  • 添加节点：list_add和list_add_tail分别在链表头部和尾部插入节点。这就像是你可以在项链的任何一端加上新的珠子。
  • 删除节点：list_del用于删除指定节点，list_del_init用于删除节点并将其初始化为空链表。这就像是你可以从项链上取下珠子，并决定是否需要放回某个地方。
  • 遍历链表：list_for_each、list_for_each_safe、list_for_each_entry和list_for_each_entry_safe提供了不同的遍历方式，支持在遍历过程中进行节点删除操作。这就像是你可以沿着项链一颗颗地检查珠子，甚至在检查过程中取下某些珠子。

通过掌握这些链表操作，你可以灵活地在内核模块中管理和操作链表。接下来，我们可以深入探讨如何利用这些操作来实现更复杂的链表管理功能。这就像是你已经学会了如何制作一条美丽的项链，接下来可以尝试制作更复杂的首饰了。

5. 其他操作与list_entry宏

在深入使用Linux内核链表时，除了基本的增删改查操作，还需要一些其他操作和宏来优化链表的使用和提高代码的可读性与效率。内核为此提供了多个实用的宏和功能，帮助开发者高效地管理和操作链表。以下是几个常见且实用的宏及其应用。

5.1 判断链表状态

在操作链表时，判断链表的状态是非常常见的需求。Linux内核提供了以下几个宏来判断链表的状态。

  • list_empty：判断链表是否为空。

    原型：

    int list_empty(const struct list_head *head);
    • head：指向链表头的指针。

    如果链表为空（即头节点的next指针指向自身），list_empty会返回true，否则返回false。这个宏常用于在执行链表操作之前检查链表是否为空。这就像是你先检查项链上是否有珠子，再决定要不要继续操作。

    示例：

    if (list_empty(&my_list)) {
    printk("链表为空\n");
}

  • list_is_last：判断某个节点是否是链表的最后一个节点。

    原型：

    int list_is_last(const struct list_head *list, const struct list_head *head);
    • list：指向要检查的节点的指针。
    • head：指向链表头部的指针。

    list_is_last宏会检查给定的节点是否是链表中的最后一个节点。如果是，返回true，否则返回false。它主要用于需要确定某个节点是否是链表的尾节点时。这就像是你检查项链上的最后一个珠子，确认是不是已经到了尽头。

    示例：

    if (list_is_last(&node->list, &my_list)) {
    printk("这是链表的最后一个节点\n");
}

5.2 通过list_entry获取包含链表节点的结构体

  • 还记得内核链表的数据与链表节点分离的特性吗? 那么如何通过链表节点找到它关联是数据呢?

  • 链表中的每个节点本身是struct list_head类型的。为了从链表节点中获取完整的数据结构，我们需要使用一些宏来从链表节点反向获取到包含它的结构体。

  • list_entry：通过链表节点获取其所属的结构体。

    原型：

    #define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

  • 实际上就是调用 container_of：通过成员变量获取包含该成员的结构体。

    原型：

    #define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))
    • ptr：指向结构体成员的指针（如链表节点）例如,结构体地址是0xffff00, ptr地址是0xffffff08。
    • type：结构体类型。
    • member：结构体成员的名称。

  • offsetof宏就是用来获取成员在结构体中的偏移量

    • #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    • 关键点就是把0作为地址转换成TYPE*类型, 这样再用->取成员时就得到了相对于0的偏移地址, 也就是在结构体中的偏移量了, 例如0x08

  • 最后再用ptr减去这个偏移量就是结构体的地址了

container_of是一个通用宏，用于通过结构体的成员获取整个结构体的指针。它是一个非常常用的宏，在很多内核数据结构中都有应用，尤其是在链表节点操作时，用来获取包含list_head的结构体。这就像是你从一个零件，找到了整个机器。

  • 设计结构体时应注意的事项：

在设计自定义链表节点时，最常见的错误之一是没有考虑到struct list_head成员的位置。为了方便链表操作，list_head通常会作为结构体的一个成员来使用。为了能够方便地从链表节点获取整个结构体，我们通常使用list_entry或container_of宏。

  1. list_head的位置：struct list_head成员应该放置在结构体中适当的位置。通常它会放在结构体的最前面或最后面，具体取决于设计需要，但必须确保它在结构体中有明确的位置。
  2. 访问链表节点时的结构体指针：由于struct list_head保存的并不是结构体的地址，因此在访问链表节点时，不能像C语言那样直接使用&node。而需要使用list_entry或container_of来获取结构体指针。

示例：

struct my_data {
    int value;
    struct list_head list;  // 链表节点
};

在这种设计中，list是my_data结构体的一部分，因此可以使用list_entry来获取到my_data结构体：

struct my_data *entry = list_entry(node, struct my_data, list);
printk("数据: %d\n", entry->value);

通过这些实用宏，你可以更加高效和灵活地使用Linux内核中的链表，帮助开发更加复杂和高效的内核模块。这就像是你已经掌握了所有的工具，可以随心所欲地打造各种精美的项链了。

# linux # 链表
Logo
openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

cover

逐行拆解 `move_to_user_mode` 的降维密码

avatar openEuler 社区

统信 UOS 升级后报 Device Error 无法启动：grub.efi 局部坏区定位与修复（附完整命令）

统信 UOS Desktop 20 专业版 1070 升级后重启，屏幕报 unexpected return from initial read: Device Error, buffersize 0、failed to load image \EFI\uos\grub.efi: device error、start_image() returned device error，随后提示「未发现操作

avatar openEuler 社区

银河麒麟上nproc命令教程详解

nproc 是银河麒麟操作系统中的处理器资源查询工具，用于获取当前进程可使用的处理器（逻辑 CPU）数量，其返回值直接受 CPU 亲和性、cgroup 配额与容器资源限制的影响，是并行任务调度的基础依据。（2）若 --all 显示 16 而 nproc 显示 8，说明进程被限制在 8 个处理器上运行。（2）常用于脚本中动态计算业务进程并发度，如 nproc --ignore=1。（1）--all

avatar openEuler 社区