双链表的应用在内核中随处可见,list.h头文件集中定义了双链表(struct list_head结构体)的相关操作。
关于list.h的分析,网上资料很多,这里只是记录我在分析list.h中遇到的问题。
struct list_head结构体:
struct list_head { struct list_head *next; struct list_head *prev; };
这个结构经常作为成员与其他数据类型一起组成一个新的结构体(后文若无特别提示,“新结构体”均指类似下面举例的嵌套型结构体),比如:
struct ListNode { int number; struct list_head list; };
由于我在用户态下写链表程序,经常将结构体ListNode中的list声明为指针类型,导致我在内核中编译加载模块后,爆出NULL ptr的bug.
所以在内核中声明list对象,直接用list就好。
List文件位置在include/linux/list.h中,可以查看。
我们在用户态下编一个链表的节点的插入,需要四条语句执行,但是这在内核中是灾难性的,为了高内聚,低耦合的特征,内核把语句分成两个函数,并配合使用inline关键字,来完成特定功能。
拿链表初始化和添加节点举例:
1.链表的初始化
其实可以从后往前看,这样更容易理解。INIT_LIST_HEAD函数形成一个空链表。这个list变量一般作为头指针(非头结点)
static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) #define LIST_HEAD_INIT(name) { &(name), &(name) }
比如我声明了一个结构体ListNode(struct ListNode head;),我只需要在init中调用INIT_LIST_HEAD(&head.list);即可
之后添加节点只需要struct ListNode *node =(struct ListNode*)kmalloc(sizeof(struct ListNode),GFP_KERNEL);
2.添加元素
这两个函数分别给链表头结点后,头结点前添加元素。前者可实现栈的添加元素,后者可实现队列的添加元素。
static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_add_tail(struct list_head *new, struct list_head *head);
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { next->prev = new; new->next = next; new->prev = prev; prev->next = new; } static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); }
list_add和list_add_tail两函数在调用__list_add函数时,对应的各个参数分别是什么?通过所列代码,可以发现这里的参数运用的很巧妙,类似JAVA中的封装。
还有很多函数我就不一一列举了,比如链表节点的删除,修改,分裂等看代码理解即可。
但是我们还需要看一下链表的遍历与取成员函数
下面我们要分析链表的遍历。虽然涉及到遍历的宏比较多,但是根据我们前面分析的那样,掌握好最基本的宏,其他宏就是进行“封装”。便利中的基本宏是:
#define __list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)
head是整个链表的头指针,而pos则不停的往后移动。但是你有没有觉得,这里有些奇怪?因为我们在上篇文章中说过,struct list_head结构经常和其他数据组成新的结构体,那么现在我们只是不停的遍历新结构体中的指针,如何得到其他成员?因此我们需要搞懂list_entry这个宏:
/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member)
这个宏的作用是通过ptr指针获取type结构的地址,也就是指向type的指针。其中ptr是指向member成员的指针。这个list_entry宏貌似很简单的样子,就是再调用container_of宏,可是当你看了container_of宏的定义后……
#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})
是不是让人有点抓狂?别急,我们一点点来分析。
首先这个宏包含两条语句。第一条:const typeof( ((type *)0)->member ) *__mptr = (ptr);首先将0转化成type类型的指针变量(这个指针变量的地址为0×0),然后再引用member成员(对应就是((type *)0)->member ))。注意这里的typeof(x),是返回x的数据类型,那么 typeof( ((type *)0)->member )其实就是返回member成员的数据类型。那么这条语句整体就是将__mptr强制转换成member成员的数据类型,再将ptr的赋给它(ptr本身就是指向member的指针)。
第二句中,我们先了解offsetof是什么?它也是一个宏被定义在:linux/include/stddef.h中。原型为:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER);
这个貌似也很抓狂,不过耐心耐心:((TYPE *)0)->MEMBER)这个其实就是提取type类型中的member成员,那么&((TYPE *)0)->MEMBER)得到member成员的地址,再强制转换成size_t类型(unsigned int)。但是这个地址很特别,因为TYPE类型是从0×0开始定义的,那么我们现在得到的这个地址就是member成员在TYPE数据类型中的偏移量。
我们再来看第二条语句, (type *)( (char *)__mptr – offsetof(type,member) )求的就是type的地址,即指向type的指针。不过这里要注意__mptr被强制转换成了(char *),为何要这么做?因为如果member是非char型的变量,比如为int型,并且假设返回值为offset,那么这样直接减去偏移量,实际上__mptr会减去sizeof(int)*offset!这一点和指针加一减一的原理相同。
有了这个指针,那么就可以随意引用其内的成员了。关于此宏的更具体了解,不妨亲自动手测试这里的程序。
好了,现在不用抓狂了,因为了解了list_entry宏,接下来的事情就很简单了。
很多函数都是这个函数的包装版,安全版。
list_for_each_entry_safe(pos, n, head, member) list_for_each_entry_safe_continue(pos, n, head, member) list_for_each_entry_safe_from(pos, n, head, member) list_for_each_entry_safe_reverse(pos, n, head, member)
下面正好使用这些数据结构,编写一些简单的内核模块
#include <linux/module.h> #include <linux/kernel.h> #include <linux/init.h> #include <linux/slab.h> #include <linux/list.h> #define N 5 struct ListNode { int number; struct list_head list; }; struct ListNode head; struct list_head *pos; struct list_head *temp; struct ListNode *tempNode; static int __init lkp_init(void) { int i=0; printk("Hello List!\n"); INIT_LIST_HEAD(&head.list); for (;i<N;i++) { struct ListNode *node =(struct ListNode*)kmalloc(sizeof(struct ListNode),GFP_KERNEL); node->number = i; list_add(&node->list,&head.list); } list_for_each_safe(pos,temp,&head.list) { tempNode = list_entry(pos,struct ListNode,list); printk("data: %d \n",tempNode->number); } return 0; } static void __exit lkp_exit(void) { int i=0; for(;i<N;i++) list_del_init(&head.list); printk("Goodbye,List!\n"); } module_init(lkp_init); module_exit(lkp_exit); MODULE_LICENSE("GPL"); MODULE_AUTHOR("lzz"); MODULE_DESCRIPTION("list Module"); MODULE_ALIAS("List module");
遍历进程链表,列出当前进程PID与进程名字:
#include< linux/init.h > #include< linux/module.h > #include< linux/sched.h > #include< linux/sem.h > #include< linux/list.h > static int __init traverse_init(void) { struct task_struct *pos; struct list_head *current_head; int count=0; printk("Traversal module is working..\n"); current_head=&(current->tasks); list_for_each_entry(pos,current_head,tasks) { count++; printk("[process %d]: %s\'s pid is %d\n",count,pos->comm,pos->pid); } printk(KERN_ALERT"The number of process is:%d\n",count); return 0; }
具体task_struct内容在 include/linux/sched.h中
comm是描述进程的名字,本质是一个char数组。