↓跳到主要内容

Linux 内核数据结构-链表

·492 字·3 分钟
目录

Linux 内核实现了一个循环双向链表，而且是侵入式链表，核心数据结构定义在 include/linux/types.h 文件：

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

实现方法都定义在 include/linux/list.h 文件。

1. 初始化链表 #

内核提供了两种初始化链表节点的方法。

一种是初始化宏：

#define LIST_HEAD_INIT(name) { &(name), &(name) }

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

展开后就是：

#define LIST_HEAD(name) \
    struct list_head name = { &(name), &(name) }

它的作用是新建一个 struct list_head 变量 name ，让两个指针指向自己，通常用户新建一个链表的 head ：

另一种是初始化函数 ：

static inline void INIT_LIST_HEAD(struct list_head *list)
{
  WRITE_ONCE(list->next, list);
  list->prev = list;
}

它的作用是让节点 struct list_head *list 的两个指针指向自己，通常用于初始一个节点。

内核的 struct list_head 保持了最简的结构，其他数据结构要表示为链表时，需要将 struct list_head 元素嵌入到自己的数据结构中，例如：

// 新建一个链表，head 就是 students_list
LIST_HEAD(students_list);
    
// 新建两个节点，并初始化
struct student *student_1 = kmalloc(sizeof(struct student), GFP_KERNEL);
struct student *student_2 = kmalloc(sizeof(struct student), GFP_KERNEL);

student_1->id = 1;
strcpy(student_1->name, "Bob");
INIT_LIST_HEAD(&student_1->list);
    
student_2->id = 2;
strcpy(student_2->name, "Alice");
INIT_LIST_HEAD(&student_2->list);

// 将两个节点依次插入队尾
list_add_tail(&student_1->list, &students_list);
list_add_tail(&student_2->list, &students_list);

实际构造的链表结构如下：

2. 添加节点 #

在 head 后面（也就是队头）添加一个 new 节点：

void list_add(struct list_head *new, struct list_head *head)

在 head 前面（也就是队尾）添加一个 new 节点：

void list_add_tail(struct list_head *new, struct list_head *head)

例如：

list_add(&student_1->list, &students_list);

3. 删除节点 #

删除一个节点：

void list_del(struct list_head *entry)

例如：

list_del(&student_1->list);

4. 判断节点的位置 #

判断 list 节点是否是 head 链表的 firts/last 节点，如果正确会返回 1 ，错误返回 0 ：

int list_is_first(const struct list_head *list, const struct list_head *head)
int list_is_last(const struct list_head *list, const struct list_head *head)

判断一个链表是否为空格，如果为空会返回 1 ：

int list_empty(const struct list_head *head)

5. 查找节点 #

作为侵入式链表，需要通过 struct list_head 结构的节点地址获得真正的数据节点，内核提供了 container_of 的重新封装：

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

三个参数分别表示：

  • ptr ：结构体成员变量 member 的地址，就是 struct list_head 成员的地址，

  • type ：数据节点的结构体类型的名称

  • member ：结构体成员变量的名称

例如：

list_entry(&student_1->list, struct student, list)

返回队头/队尾的节点：

list_first_entry(head, type, member)
list_last_entry(head, type, member)

三个参数分别表示：

  • head ：链表头的地址，

  • type ：结构体类型的名称

  • member ：结构体中的成员变量的名称

例如：

struct student *entry;
entry = list_first_entry(&students_list, struct student, list);

获取下一个/上一个节点：

list_next_entry(pos, member)
list_prev_entry(pos, member)

两个参数的含义：

  • pos ：数据节点的地址

  • member：数据节点内 sturct list_head 成员的名称

例如：

struct student *entry;
entry = list_first_entry(&students_list, struct student, list);
entry = list_next_entry(entry, list);

6. 遍历链表 #

内核定义了一个宏，用于从队头开始遍历链表：

#define list_for_each_entry(pos, head, member)        \
  for (pos = list_first_entry(head, typeof(*pos), member);  \
       &pos->member != (head);          \
       pos = list_next_entry(pos, member))

三个参数的含义：

  • pos ：一个数据节点类型的指针，用于遍历链表中的每个节点

  • head ：链表的 head

  • member ：数据节点内 sturct list_head 成员的名称

例如：

list_for_each_entry(entry, &students_list, list)
{
    printk("entry %d:%s\n", entry->id, entry->name);
}

7. 例程 #

hellomod.c ：

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

struct student {
    int id;
    char name[10];
    struct list_head list;
};

static int __init hellomod_init(void)
{
    struct student *entry;
    // 新建一个链表
    LIST_HEAD(students_list);
    
    // 新建两个节点，并初始化
    struct student *student_1 = kmalloc(sizeof(struct student), GFP_KERNEL);
    struct student *student_2 = kmalloc(sizeof(struct student), GFP_KERNEL);

    student_1->id = 1;
    strcpy(student_1->name, "Bob");
    INIT_LIST_HEAD(&student_1->list);
    
    student_2->id = 2;
    strcpy(student_2->name, "Alice");
    INIT_LIST_HEAD(&student_2->list);

    // 将两个节点依次插入队尾
    list_add_tail(&student_1->list, &students_list);
    list_add_tail(&student_2->list, &students_list);

    entry = list_first_entry(&students_list, struct student, list);
    printk("first entry is %d:%s\n", entry->id, entry->name);

    entry = list_next_entry(entry, list);
    printk("next entry of first entry is %d:%s\n", entry->id, entry->name);

    list_for_each_entry(entry, &students_list, list)
    {
        printk("entry %d:%s\n", entry->id, entry->name);
    }
    printk("hellomod init\n");
    
    return 0;
}

static void __exit hellomod_exit(void)
{
    printk("hellomod exit\n");
}

module_init(hellomod_init);
module_exit(hellomod_exit);

MODULE_LICENSE("GPL");

Makefile ：

KERDIR=/lib/modules/$(shell uname -r)/build
PWD=$(shell pwd)

obj-m:=hellomod.o

default:
  make -C ${KERDIR} M=${PWD} modules
clean:
  make -C ${KERDIR} M=${PWD} clean

编译后加载驱动：

$ make
$ sudo insmod hellomod.ko
$ dmesg
[35509.579609] first entry is 1:Bob
[35509.579610] next entry of first entry is 2:Alice
[35509.579611] entry 1:Bob
[35509.579611] entry 2:Alice
[35509.579611] hellomod init
↑