Linux 设备驱动系列 (16) —— 链表 Linked List

作者：Linux内核拾遗

2024-06-08
浙江
本文字数：4522 字
阅读完需：约 15 分钟

关注微信公众号：Linux 内核拾遗
文章来源：https://mp.weixin.qq.com/s/UN0-rYSV1waqgD97ayXNAQ

链表是一种数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表可以动态增长或缩小，适合频繁插入和删除操作。常见的类型有单向链表、双向链表和循环链表。虽然访问速度较慢，但灵活性和操作效率使其在许多应用中非常有用。

本文将介绍 Linux 内核中提供的链表数据结构。

1 Linux 中的链表

链表作为一种非常重要的数据结构，允许高效地存储和操作大量数据，在内核代码中链表的使用随处可见。

在 Linux 内核中，开发者无需自己实现链表或使用第三方库，内核内置了双向链表的实现struct list_head，定义在 linux/list.h 头文件中。

2 Linux 链表使用

下面将详细介绍 Linux 内核链表的常用接口和使用方式。

2.1 链表头初始化

Linux 内核链表用链表头 list_head 来表示，因此链表的初始化其实就是初始化一个链表头。

LIST_HEAD(linked_list);

复制代码

LIST_HEAD 宏将创建一个名为 linked_list 的链表，它是一个双向链表，即在没有插入任何节点之前，它的首尾指针都指向自身（也可以认为首尾指针指向自身时表示链表是空的）。

LIST_HEAD 的内部实现如下：

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \    struct list_head name = LIST_HEAD_INIT(name)
struct list_head {    struct list_head *next;    struct list_head *prev;};

复制代码

因此上面的初始化展开后是下面这个样子：

struct list_head linked_list = { &linked_list , &linked_list};

复制代码

2.2 创建链表节点

Linux 内核的链表节点也使用struct list_head来表示，它通常内嵌在自定义的数据结构中：

struct my_node {    struct list_head list;    int data;};
struct my_node node;

复制代码

链表节点在插入链表之前也需要进行初始化，使用 INIT_LIST_HEAD 宏，例如：

INIT_LIST_HEAD(&node.list);node.data = 42;

复制代码

2.3 添加节点到链表中

链表节点初始化完成后，就可以往链表中添加节点：

inline void list_add(struct list_head *new, struct list_head *head);inline void list_add_tail(struct list_head *new, struct list_head *head);

复制代码

其中 head 表示链表头，new 是要添加的节点。list_add 将 new 添加到链表头部，而 list_add_tail 添加到链表尾部。

2.4 从链表中删除节点

从链表中删除节点实际上就是修改了一下节点及其相邻节点的 prev 和 next 指针指向，它不会释放节点的内存：

inline void list_del(struct list_head *entry);inline void list_del_init(struct list_head *entry);

复制代码

其中 list_del_init 在删除节点后还对该节点重新进行初始化操作。

2.5 从链表中替换节点

和删除节点同理，替换节点也只是修改了 prev 和 next 指针指向，并且 list_replace_init 还会对替换出来的节点（old）进行重新初始化操作：

inline void list_replace(struct list_head *old, struct list_head *new);inline void list_replace_init(struct list_head *old, struct list_head *new);

复制代码

2.6 移动链表中的节点

下面的函数中，list 表示要移动的节点，list_move 将其移动到链表首部，list_move_tail 将其移动到链表尾部：

inline void list_move(struct list_head *list, struct list_head *head);inline void list_move_tail(struct list_head *list, struct list_head *head);

复制代码

2.7 旋转链表节点

list_rotate_left 是 Linux 内核中用于双向链表操作的一个函数，它用于将链表的第一个节点移动到最后一个位置。这个操作可以看作是将链表左旋一次。

inline void list_rotate_left(struct list_head *head);

复制代码

2.8 检查链表

Linux 内核还提供了检查链表的相关函数，例如：

list_is_last：检查节点是否是链表最后一个节点。
list_empty：链表是否为空。
list_is_singular：链表是否只有一个节点。

inline int list_is_last(const struct list_head *list, const struct list_head *head);inline int list_empty(const struct list_head *head);inline int list_is_singular(const struct list_head *head);

复制代码

2.9 链表分割

list_cut_position 函数用于将一个双向链表从指定位置剪切出来，形成一个新的链表段，其中：

list 是新链表头指针。
head 是原链表头指针。
entry 指向原链表中某个节点的指针，从这个节点开始分割链表。

inline void list_cut_position(struct list_head *list,                              struct list_head *head,                              struct list_head *entry);

复制代码

2.10 链表连接

list_splice 是 Linux 内核中用于将一个链表合并到另一个链表中的函数。它可以将整个链表 list 插入到 head 链表中，或者更具体地，将list链表插入到head链表首部。

inline void list_splice(const struct list_head *list,                        struct list_head *head);

复制代码

2.11 链表遍历

Linux 内核提供了一系列的函数来遍历和操作链表中的元素：

list_entry(ptr, type, member)：通过链表节点的指针获取包含该节点的结构体指针。
list_for_each(pos, head)：遍历链表中的每个节点。
list_for_each_entry(pos, head, member)：遍历链表中的每个结构体实例。
list_for_each_entry_safe ( pos, n, head, member)：安全地遍历链表中的每个结构体实例，可以在遍历过程中安全地删除节点。
list_for_each_prev(pos, head)：逆向遍历链表中的每个节点。
list_for_each_entry_reverse(pos, head, member)：逆向遍历链表中的每个结构体实例。

3 Linux 链表代码演示

kernel_driver.c

#include <linux/kernel.h>#include <linux/init.h>#include <linux/module.h>#include <linux/kdev_t.h>#include <linux/fs.h>#include <linux/cdev.h>#include <linux/device.h>#include <linux/slab.h>#include <linux/uaccess.h>#include <linux/sysfs.h>#include <linux/kobject.h>#include <linux/interrupt.h>#include <asm/io.h>#include <linux/err.h>#include <linux/smp.h>
volatile int my_value = 0;
struct my_node{    struct list_head list;    int data;};static LIST_HEAD(my_list);
static struct workqueue_struct *own_workqueue;
static void static_wq_fn(struct work_struct *work){    struct my_node *node = NULL;
    pr_info("Static workqueue function called on CPU[%d]\n", smp_processor_id());
    node = kmalloc(sizeof(struct my_node), GFP_KERNEL);    node->data = my_value;    INIT_LIST_HEAD(&node->list);    list_add_tail(&node->list, &my_list);}static DECLARE_WORK(static_work, static_wq_fn);
static void dynanic_wq_fn(struct work_struct *work){    pr_info("Dynamic workqueue function called on CPU[%d]\n", smp_processor_id());}static struct work_struct dynamic_work;
#define IRQ_NO 63
static irqreturn_t irq_handler(int irq, void *dev_id){    pr_info("Shared IRQ[%d]: Interrupt Occurred\n", irq);    queue_work(own_workqueue, &static_work);    queue_work_on(3, own_workqueue, &dynamic_work);    return IRQ_HANDLED;}
dev_t dev = 0;static struct class *dev_class;static struct cdev my_cdev;struct kobject *kobj_ref;
static ssize_t sysfs_show(struct kobject *kobj,                          struct kobj_attribute *attr, char *buf){    return sprintf(buf, "%d", my_value);}
static ssize_t sysfs_store(struct kobject *kobj,                           struct kobj_attribute *attr, const char *buf, size_t count){    sscanf(buf, "%d", &my_value);    return count;}
struct kobj_attribute my_attr = __ATTR(my_value, 0660, sysfs_show, sysfs_store);
static ssize_t my_read(struct file *filp,                       char __user *buf, size_t len, loff_t *off){    struct my_node *node;    int i = 0;
    list_for_each_entry(node, &my_list, list)    {        pr_info("Node[%d] { data = %d }\n", i++, node->data);    }
    pr_info("Total Nodes = %d\n", i);    return 0;}
static ssize_t my_write(struct file *filp,                        const char __user *buf, size_t len, loff_t *off){    char __buf[10] = {0};
    if (copy_from_user(__buf, buf, len) == 0) {        pr_info("Write: %s", __buf);        sscanf(__buf, "%d", &my_value);    }    generic_handle_irq(IRQ_NO);    return len;}
static struct file_operations fops = {    .owner = THIS_MODULE,    .read = my_read,    .write = my_write,};
static int __init my_driver_init(void){    if ((alloc_chrdev_region(&dev, 0, 1, "my_dev")) < 0)        return -1;
    cdev_init(&my_cdev, &fops);    my_cdev.owner = THIS_MODULE;    my_cdev.ops = &fops;
    if ((cdev_add(&my_cdev, dev, 1)) < 0)        goto r_class;
    if (IS_ERR(dev_class = class_create(THIS_MODULE, "my_class")))        goto r_class;
    if (IS_ERR(device_create(dev_class, NULL, dev, NULL, "my_device")))        goto r_device;
    kobj_ref = kobject_create_and_add("my_sysfs", kernel_kobj);    if (sysfs_create_file(kobj_ref, &my_attr.attr))        goto r_sysfs;
    if (request_irq(IRQ_NO, irq_handler, IRQF_SHARED,                    "my_device", (void *)(irq_handler)))        goto irq;
    INIT_WORK(&dynamic_work, dynanic_wq_fn);
    own_workqueue = create_workqueue("own_wq");
    return 0;irq:    free_irq(IRQ_NO, (void *)(irq_handler));r_sysfs:    kobject_put(kobj_ref);    sysfs_remove_file(kernel_kobj, &my_attr.attr);
r_device:    device_destroy(dev_class, dev);    class_destroy(dev_class);r_class:    unregister_chrdev_region(dev, 1);    cdev_del(&my_cdev);    return -1;}
static void __exit my_driver_exit(void){    struct my_node *cur, *next;    list_for_each_entry_safe(cur, next, &my_list, list)    {        list_del(&cur->list);        kfree(cur);    }
    destroy_workqueue(own_workqueue);    free_irq(IRQ_NO, (void *)(irq_handler));    kobject_put(kobj_ref);    sysfs_remove_file(kernel_kobj, &my_attr.attr);    device_destroy(dev_class, dev);    class_destroy(dev_class);    cdev_del(&my_cdev);    unregister_chrdev_region(dev, 1);}
module_init(my_driver_init);module_exit(my_driver_exit);
MODULE_LICENSE("GPL");MODULE_AUTHOR("feifei <feifei@gmail.com>");MODULE_DESCRIPTION("A simple device driver");MODULE_VERSION("1.15");

复制代码

代码编译运行，运行结果如下：

关注微信公众号：Linux 内核拾遗
文章来源：https://mp.weixin.qq.com/s/UN0-rYSV1waqgD97ayXNAQ

发布于: 刚刚阅读数: 6

原文链接:【http://xie.infoq.cn/article/8b82fe1e4ab66a8c8ce7012c3】。

Linux内核拾遗

关注

聚沙成塔 2023-01-12 加入

分享Linux内核开发相关的编程语言、开发调试工具链、计算机组成及操作系统内核知识、Linux社区最新资讯等

发布

暂无评论

创作场景

Linux 设备驱动系列 (16) —— 链表 Linked List

1 Linux 中的链表

2 Linux 链表使用

2.1 链表头初始化

2.2 创建链表节点

2.3 添加节点到链表中

2.4 从链表中删除节点

2.5 从链表中替换节点

2.6 移动链表中的节点

2.7 旋转链表节点

2.8 检查链表

2.9 链表分割

2.10 链表连接

2.11 链表遍历

3 Linux 链表代码演示

Linux内核拾遗

评论