list.h解析与应用

September 3rd, 2014 by JasonLe's Tech Leave a reply »

双链表的应用在内核中随处可见,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数组。

 

参考:http://www.cnblogs.com/Anker/p/3475643.html

http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/