Linux内核中的链表实现

一.内核链表

内核链表一般就是在一个结构体有一个结构体成员变量，该结构体成员变量只有 next 和 prev两个指针，分别指向下一个结点和上一个结构，就像一条绳子串起所有的结构体，这样做的好处，就是可以用内核链表来串起各个不同类型的结构体。

二.linux内核链表常见函数（包含在linux/list.h里面）

1.链表的结构体

2.链表节点初始化（next,prev都指向自己）

3.节点加入链表的三个函数

list_add()函数用于形成栈

list_add_tail形成队列

4.删除函数

5.遍历链表节点的函数

（知道结构体某成员的地址倒推该结构体地址的重要函数）

首先 &((type*)0)->member：把0地址转换成（type*）类型，然后就可以映射出 member（因为member是结构体x的一个成员），0地址上的结构体是不存在的，只是虚拟出来，然后 &((type*)0)->member 是上图A部分的大小，因为同是 type型结构体，所以A部分大小 = B部分大小。然后再用指向member 的指针pos 减去B部分就等于结构体x的起始地址。

练习代码如下：

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

typedef struct student{
　　char name[20];
　　int index;
　　struct list_head stulist;
}stu;

static stu *CreateHeadP(void)
{
　　stu *p = (stu *)kmalloc(sizeof(stu),GFP_KERNEL);
　　memset(p,0,sizeof(stu));

　　INIT_LIST_HEAD(&(p->stulist));
　　return p;
}

static stu *NewStu(int i)
{
　　stu *p = (stu *)kmalloc(sizeof(stu),GFP_KERNEL);
　　memset(p,0,sizeof(stu));

　　sprintf(p->name,"stu:%d",i);
　　p->index = i;
　　INIT_LIST_HEAD(&(p->stulist));

　　return p;
}

static void show(stu *head)
{
　　stu *pos = NULL;

　　list_for_each_entry(pos,&(head->stulist),stulist)
　　{
　　　　printk("name:%s index:%d\r\n",pos->name,pos->index);
　　}
}

static int __init stu_operation(void)
{
　　int i = 0;

　　stu *stu_new = NULL;
　　stu *stu_head = NULL;

　　stu_head = CreateHeadP();

　　for(i = 0;i < 5;i++)
　　{
　　　　stu_new = NewStu(i);
　　　　list_add(&(stu_new->stulist),&(stu_head->stulist));
　　}

　　show(stu_head);

　　return 0;
}

static void __exit stu_exit(void)
{
　　int i = 0;

　　struct list_head *pos = NULL;
　　stu *stu_index = NULL;

　　for(i=0;i < 5;i++)
　　{
　　　　pos = stu_head->stulist.next;
　　　　stu_index = list_entry(pos,stu,stulist);
　　　　list_del(pos);
　　　　kfree(stu_index);
　　}

　　printk("free all!\r\n");
}

module_init(stu_operation);
module_exit(stu_exit);

MODULE_LICENSE("GPL");

运行结果如下

加载模块

卸载模块

Linux内核中的链表实现

推荐阅读