数据结构day6——内核链表

发布于：2025-07-02 ⋅ 阅读:(17) ⋅ 点赞:(0)

在 Linux 内核开发中，链表是最基础且重要的数据结构之一。与普通链表不同，Linux 内核采用了一种非常巧妙的 "通用链表" 设计，它不直接包含数据，而是将数据结构嵌入其中，从而实现了一种高度灵活、可复用的链表机制。本文将深入解析 Linux 内核链表的设计思想、实现原理及应用场景。

一、传统链表的局限性

传统链表的实现方式通常是将数据直接包含在节点结构中：

// 传统链表节点结构
typedef struct Student {
    char name[50];
    int age;
    struct Student *next;  // 指向下一个节点的指针
} Student;

这种设计存在以下局限性：

  • 类型不通用：每个链表只能存储特定类型的数据
  • 代码冗余：为每种数据类型都需要实现一套链表操作函数
  • 扩展性差：如果需要在不同链表间共享节点，实现复杂

二、Linux 内核链表的设计思想

Linux 内核链表采用了一种完全不同的设计思路：链表节点只包含指针域，而数据结构通过嵌入这个节点来实现链表功能。核心代码如下：

// 内核链表节点定义（include/linux/list.h）
struct list_head {
    struct list_head *next, *prev;
};

// 初始化链表头
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

// 初始化节点
static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

这种设计的精妙之处在于：链表节点不再包含数据，而是数据结构包含链表节点。通过这种方式，任何数据结构都可以轻松接入链表系统。

三、内核链表的核心实现

1. 节点操作函数

内核提供了一系列用于操作链表的函数：

// 添加新节点到链表头部（头插法）
static inline void list_add(struct list_head *new, struct list_head *head) {
    __list_add(new, head, head->next);
}

// 添加新节点到链表尾部（尾插法）
static inline void list_add_tail(struct list_head *new, struct list_head *head) {
    __list_add(new, head->prev, head);
}

// 从链表中删除节点
static inline void list_del(struct list_head *entry) {
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}

// 判断链表是否为空
static inline int list_empty(const struct list_head *head) {
    return head->next == head;
}

2. 从链表节点到数据结构的转换

内核链表的核心是通过container_of宏从链表节点指针获取包含它的数据结构指针：

// 获取包含链表节点的结构体指针
#define container_of(ptr, type, member) ({                      \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

// offsetof宏计算成员在结构体中的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

3. 遍历链表的宏

内核提供了安全遍历链表的宏：

// 遍历链表
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

// 安全遍历（允许删除当前节点）
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
         pos = n, n = pos->next)

// 遍历链表并获取包含它的数据结构
#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))

四、内核链表的应用示例

下面通过一个实际例子展示如何在内核模块中使用链表：

#include <linux/module.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/slab.h>

// 定义包含链表节点的数据结构
struct person {
    char name[20];
    int age;
    struct list_head list;  // 嵌入的链表节点
};

// 定义链表头
static LIST_HEAD(person_list);

static int __init person_init(void) {
    struct person *p1, *p2, *p3;
    
    // 分配并初始化第一个person
    p1 = kmalloc(sizeof(*p1), GFP_KERNEL);
    strcpy(p1->name, "Alice");
    p1->age = 25;
    INIT_LIST_HEAD(&p1->list);
    
    // 分配并初始化第二个person
    p2 = kmalloc(sizeof(*p2), GFP_KERNEL);
    strcpy(p2->name, "Bob");
    p2->age = 30;
    INIT_LIST_HEAD(&p2->list);
    
    // 分配并初始化第三个person
    p3 = kmalloc(sizeof(*p3), GFP_KERNEL);
    strcpy(p3->name, "Charlie");
    p3->age = 35;
    INIT_LIST_HEAD(&p3->list);
    
    // 添加到链表
    list_add_tail(&p1->list, &person_list);
    list_add_tail(&p2->list, &person_list);
    list_add_tail(&p3->list, &person_list);
    
    // 遍历链表并打印
    struct person *pos;
    list_for_each_entry(pos, &person_list, list) {
        printk(KERN_INFO "Name: %s, Age: %d\n", pos->name, pos->age);
    }
    
    return 0;
}

static void __exit person_exit(void) {
    struct person *pos, *next;
    
    // 安全遍历并删除所有节点
    list_for_each_safe(pos, next, &person_list) {
        list_del(&pos->list);
        kfree(pos);
    }
    
    printk(KERN_INFO "Person module unloaded\n");
}

module_init(person_init);
module_exit(person_exit);

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Example of Linux Kernel Linked List");

五、内核链表的优势与注意事项

优势

  1. 高度通用性：一个链表可以包含不同类型的数据结构，只要它们都嵌入了list_head
  2. 代码复用：所有链表操作函数只需实现一次
  3. 节省内存：链表节点无需额外存储数据指针
  4. 安全遍历：提供安全遍历宏，允许在遍历过程中删除节点

注意事项

  1. 内核环境限制：内核链表只能在内核空间使用，用户空间需使用类似实现
  2. 内存管理：使用kmalloc分配内存，需确保在适当时候释放
  3. 并发安全：在多处理器环境中使用时，需考虑并发访问问题，通常需要配合自旋锁等同步机制
  4. 遍历安全：使用list_for_each_safe进行可能删除节点的遍历操作

六、用户空间实现内核链表

虽然内核链表是为内核开发设计的，但我们也可以在用户空间实现类似的机制：

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

// 链表节点定义
struct list_head {
    struct list_head *next, *prev;
};

// 初始化链表头
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

// 初始化节点
static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

// 添加新节点到链表头部
static inline void list_add(struct list_head *new, struct list_head *head) {
    new->next = head->next;
    new->prev = head;
    head->next->prev = new;
    head->next = new;
}

// 从链表中删除节点
static inline void list_del(struct list_head *entry) {
    entry->prev->next = entry->next;
    entry->next->prev = entry->prev;
}

// 判断链表是否为空
static inline int list_empty(const struct list_head *head) {
    return head->next == head;
}

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

// offsetof宏实现
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

// 遍历链表
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

// 遍历链表并获取包含它的数据结构
#define list_for_each_entry(pos, head, member)                          \
    for (pos = container_of((head)->next, typeof(*pos), member);          \
         &pos->member != (head);                                          \
         pos = container_of(pos->member.next, typeof(*pos), member))

// 用户空间示例
typedef struct {
    int id;
    char name[50];
    struct list_head list;
} User;

int main() {
    LIST_HEAD(user_list);
    
    // 创建并添加用户
    User *user1 = malloc(sizeof(User));
    user1->id = 1;
    strcpy(user1->name, "张三");
    INIT_LIST_HEAD(&user1->list);
    list_add(&user1->list, &user_list);
    
    User *user2 = malloc(sizeof(User));
    user2->id = 2;
    strcpy(user2->name, "李四");
    INIT_LIST_HEAD(&user2->list);
    list_add(&user2->list, &user_list);
    
    // 遍历链表
    User *pos;
    list_for_each_entry(pos, &user_list, list) {
        printf("ID: %d, 姓名: %s\n", pos->id, pos->name);
    }
    
    // 释放内存
    list_for_each_entry(pos, &user_list, list) {
        list_del(&pos->list);
        free(pos);
    }
    
    return 0;
}

七、总结

Linux 内核链表是一种设计精巧、高效灵活的数据结构，它通过将链表节点嵌入到数据结构中，实现了链表操作的高度复用。这种设计思想不仅在内核开发中广泛应用，也为用户空间的软件开发提供了很好的借鉴。

理解和掌握内核链表的原理与使用方法，对于深入理解 Linux 内核工作机制、开发高性能系统软件具有重要意义。通过合理应用内核链表，可以编写出更加简洁、高效且易于维护的代码

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布