链表是一种数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表可以动态增长或缩小，适合频繁插入和删除操作。常见的类型有单向链表、双向链表和循环链表。虽然访问速度较慢，但灵活性和操作效率使其在许多应用中非常有用。
本文将介绍Linux内核中提供的链表数据结构。
01
—
Linux中的链表
链表作为一种非常重要的数据结构，允许高效地存储和操作大量数据，在内核代码中链表的使用随处可见。
在Linux内核中，开发者无需自己实现链表或使用第三方库，内核内置了双向链表的实现struct list_head ，定义在linux/list.h头文件中。
02
—
Linux链表使用
下面将详细介绍Linux内核链表的常用接口和使用方式。
2.1
—
链表头初始化
Linux内核链表用链表头list_head来表示，因此链表的初始化其实就是初始化一个链表头。
LIST_HEAD宏将创建一个名为linked_list的链表，它是一个双向链表，即在没有插入任何节点之前，它的首尾指针都指向自身（也可以认为首尾指针指向自身时表示链表是空的）。
LIST_HEAD的内部实现如下：
#defineLIST_HEAD(name) \struct list_head name = LIST_HEAD_INIT(name)
structlist_head{structlist_head*next;structlist_head*prev;};
因此上面的初始化展开后是下面这个样子：
2.2
—
创建链表节点
Linux内核的链表节点也使用struct list_head来表示，它通常内嵌在自定义的数据结构中：
structmy_nodenode;
链表节点在插入链表之前也需要进行初始化，使用INIT_LIST_HEAD宏，例如：
2.3
—
添加节点到链表中
链表节点初始化完成后，就可以往链表中添加节点：
其中head表示链表头，new是要添加的节点。list_add将new添加到链表头部，而list_add_tail添加到链表尾部。
2.4
—
从链表中删除节点
从链表中删除节点实际上就是修改了一下节点及其相邻节点的prev和next指针指向，它不会释放节点的内存：
其中list_del_init在删除节点后还对该节点重新进行初始化操作。
2.5
—
从链表中替换节点
和删除节点同理，替换节点也只是修改了prev和next指针指向，并且list_replace_init还会对替换出来的节点（old）进行重新初始化操作：
2.6
—
移动链表中的节点
下面的函数中，list表示要移动的节点，list_move将其移动到链表首部，list_move_tail将其移动到链表尾部：
2.7
—
旋转链表节点
list_rotate_left 是 Linux 内核中用于双向链表操作的一个函数，它用于将链表的第一个节点移动到最后一个位置。这个操作可以看作是将链表左旋一次。
2.8
—
检查链表
Linux内核还提供了检查链表的相关函数，例如：
list_is_last：检查节点是否是链表最后一个节点。
list_empty：链表是否为空。
list_is_singular：链表是否只有一个节点。
list_is_last：检查节点是否是链表最后一个节点。
list_empty：链表是否为空。
list_is_singular：链表是否只有一个节点。
2.9
—
链表分割
list_cut_position函数用于将一个双向链表从指定位置剪切出来，形成一个新的链表段，其中：
list是新链表头指针。
head是原链表头指针。
entry指向原链表中某个节点的指针，从这个节点开始分割链表。
list是新链表头指针。
head是原链表头指针。
entry指向原链表中某个节点的指针，从这个节点开始分割链表。
2.10
—
链表连接
list_splice是 Linux 内核中用于将一个链表合并到另一个链表中的函数。它可以将整个链表 list 插入到 head 链表中，或者更具体地，将list链表插入到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)：逆向遍历链表中的每个结构体实例。
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)：逆向遍历链表中的每个结构体实例。
03
—
Linux链表代码演示
kernel_driver.c
volatileintmy_value = 0;
structmy_node{structlist_headlist;intdata;};staticLIST_HEAD(my_list);
staticstructworkqueue_struct*own_workqueue;
staticvoidstatic_wq_fn(struct work_struct *work){structmy_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);}staticDECLARE_WORK(static_work, static_wq_fn);
staticvoiddynanic_wq_fn(struct work_struct *work){pr_info("Dynamic workqueue function called on CPU[%d]\n", smp_processor_id);}staticstructwork_structdynamic_work;
#defineIRQ_NO 63
staticirqreturn_t irq_handler(intirq, 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);returnIRQ_HANDLED;}
dev_tdev = 0;staticstructclass*dev_class;staticstructcdevmy_cdev;structkobject*kobj_ref;
staticssize_t sysfs_show(struct kobject *kobj,struct kobj_attribute *attr, char*buf){returnsprintf(buf, "%d", my_value);}
staticssize_t sysfs_store(struct kobject *kobj,struct kobj_attribute *attr, constchar*buf, size_tcount){sscanf(buf, "%d", &my_value);returncount;}
structkobj_attributemy_attr= __ATTR(my_value, 0660, sysfs_show, sysfs_store);
staticssize_t my_read(struct file *filp,char__user *buf, size_tlen, loff_t*off){structmy_node*node;inti = 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);return0;}
staticssize_t my_write(struct file *filp,constchar__user *buf, size_tlen, 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);returnlen;}
staticstructfile_operationsfops= {.owner = THIS_MODULE,.read = my_read,.write = my_write,};
staticint__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)gotor_class;
if(IS_ERR(dev_class = class_create(THIS_MODULE, "my_class")))gotor_class;
if(IS_ERR(device_create(dev_class, NULL, dev, NULL, "my_device")))gotor_device;
kobj_ref = kobject_create_and_add("my_sysfs", kernel_kobj);if(sysfs_create_file(kobj_ref, &my_attr.attr))gotor_sysfs;
if(request_irq(IRQ_NO, irq_handler, IRQF_SHARED,"my_device", (void*)(irq_handler)))gotoirq;
INIT_WORK(&dynamic_work, dynanic_wq_fn);
own_workqueue = create_workqueue("own_wq");
return0;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;}
staticvoid__exitmy_driver_exit(void){structmy_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_DEION("A simple device driver");MODULE_VERSION("1.15");
代码编译运行，运行结果如下：
