list.h in Kernel
list.h解析与应用
双链表的应用在内核中随处可见，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数组。