Linux内核设备驱动之内核中链表的使用笔记整理

1. 简介

在Linux内核中，链表（linked list）是一个常用的数据结构，用于实现不同的数据结构，例如队列、栈、哈希表等。链表的结构相对于数组更加灵活，可以动态地添加和删除元素，但是在访问链表中的元素时需要遍历整个链表，因此访问速度相对较慢。在驱动程序中，链表的使用也很普遍，例如用于管理设备队列、内存块等。

Linux内核提供了链表实现的头文件<linux/list.h>，通过struct list_head结构体定义链表节点。每个节点包含两个指针，next指向链表的下一个节点，prev指向链表的前一个节点。所以可以通过链表遍历访问链表中的所有节点。以下将从链表的定义、初始化、添加/删除、遍历等方面进行详细介绍。

2. 链表定义与初始化

链表是由多个链表节点构成的，每个链表节点都有其自己的数据域和指向前一个节点和后一个节点的指针。所以链表节点的定义如下：

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

struct list_head即是一个链表节点。

在定义好链表节点结构体之后，就可以定义链表了，链表即是由多个链表节点构成的，形式上”的链表即是指向链表节点的指针。

struct list_head my_list_head;

链表的初始化可以使用INIT_LIST_HEAD宏来完成。该宏将链表的头部节点设为空，使所有节点都不再被链接起来。

INIT_LIST_HEAD(&my_list_head);

3. 添加/删除节点

链表添加/删除节点的操作是非常常见的操作。本部分将介绍如何在链表中添加/删除节点。

链表中的每一个元素都被形式化地视为一个链表节点，它的链表属性通过list_head数据结构而实现，我们可插入任何的元素到这个节点的前面或者后面。

以下代码展示如何插入一个元素（一个inode）到链表中。

void add_to_list(struct inode *node, struct list_head *head)
{
    list_add(&node->list, head);
}

list_add是一个Linux提供的宏，以下是它的定义：

#define list_add(new, head) __list_add((new), (head), (head)->next)

可以看到，list_add函数的参数中，第一个参数new是新的节点，第二个参数head是链表的头部节点，第三个参数则是new节点添加的位置。将新节点插入到链表头部或尾部的代码如下：

# 链表头部插入新节点
void add_to_head(struct inode *node, struct list_head *head)
{
    list_add(&node->list, head);
}

# 链表尾部插入新节点
void add_to_tail(struct inode *node, struct list_head *head)
{
    list_add_tail(&node->list, head);
}

在链表中删除一个节点，可以使用list_del宏，该宏对链表节点的前后指针进行处理，将当前节点从链表中删掉：

void delete_one_node(struct inode *node, struct list_head *head)
{
    list_del(&node->list);
}

4. 遍历链表

遍历链表是必不可少的，而Linux内核链表的遍历有两种方式，一种是while loop遍历，另一种则是各种带有foreach宏的快捷方式，以下详细介绍这两种方式。

遍历链表的基本操作就是从链表的头部节点依次往下遍历，对于每一个节点执行想要的操作，这里我们展示如何遍历整个链表并输出每一个节点的地址信息：

void traverse_list(struct list_head *head)
{
    struct inode *pos, *next;
    list_for_each_entry_safe(pos, next, head, list) {
        printk(KERN_INFO "entry: %p\n", pos);
    }
}

在上述代码中，list_for_each_entry_safe是一个宏，其依次遍历链表中的每一个节点，在节点的list成员中获取前/后指针（pos），在代码块中对pos节点进行操作，next则是遍历保护结构体，防止在遍历时节点被意外地删除。