Linux 内核笔记（2.6.36）（二）

C语言基础

• 链表

    linux内核代码中大量使用链表，为了提高效率，内核采用了一套通用的，一般的，可以用到各种不同数据结构的队列操作。在include/linux/ list.h中，有如下申明：

struct list_head {
    struct list_head *next, *prev;
};

    于是，其余数据结构如inode等将其引用而作为一个成员，就可以完成下面将要讲到的若干操作而不去单独定义了。引用该数据结构的结构我们称为宿主结构。

    链表的插入，删除和查找不再赘述，这里主要介绍一种十分巧妙并且在内核中经常用到的链表操作--返回宿主结构。
    如果需要有某种数据结构的队列，就在这种数据结构定义内部放上一个list_head数据结构。 例如，建立数据结构foo链表的方式是，在foo的定义中，嵌入了一个list_head成员list。 这里foo就是所指的"宿主"：

typedef struct foo {
    …
    struct list_head list;
    …
};

     但是，如何通过list_head成员访问到宿主结构项呢？毕竟list_head不过是个连接件，而我们需要的是一个"特定"的数据结构链表。先介绍几个基本宏：offsetof、typeof、containerof。
    offsetof定义在include/linux/stddef.h

#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
#endif /* __KERNEL__ */

    其中__compiler_offsetof(a,b)的定义在include/linux/compiler-gcc4.h

#define __compiler_offsetof(a,b) __builtin_offsetof(a,b)

    而__builtin_offsetof()宏就是在编译器中已经设计好了的函数，直接调用即可。
    解释offsetof：一共4步
1. ( (TYPE *)0 ) 强制 "转换" 为 TYPE结构的指针;
2. ((TYPE *)0)->MEMBER 访问结构中的数据成员;
3. &( ( (TYPE *)0 )->MEMBER)取出数据成员的地址;
4. (size_t)(&(((TYPE*)0)->MEMBER))结果转换类型.巧妙之处在于将0转换成(TYPE*)，结构以内存空间首地址0作为起始地址，则成员地址自然为偏移地址；
    这里使用的是一个利用编译器技术的小技巧（编译器自动算出成员的偏移量），即先求得结构成员变量在结构体中的相对于结构体的首地址的偏移地址，然后根据结构体的首地址为0，从而得出该偏移地址就是该结构体变量在该结构体中的偏移，即：该结构体成员变量距离结构体首的距离。在offsetof()中，这个 member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。对于给定一个结 构，offsetof(type,member)是一个常量，list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。

    typeof的作用可以简单解释为提取变量类型，类似于sizeof（取变量大小），举例如下：

unsigned int i;
typeof(i) x;
x=100;
printf("x:%d/n",x);

    代码中的typeof(i)等效于unsigned int。

    container_of的定义在include/linux/kernel.h

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:    the pointer to the member.
 * @type:    the type of the container struct this is embedded in.
 * @member:    the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({            \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

     分析：

    1.(type *)0->member为设计一个type类型的结构体，起始地址为0，编译器将结构体的起始的地址加上此结构体成员变量的偏移得到此结构体成员变 量的地址，由于结构体起始地址为0，所以此结构体成员变量的偏移地址就等于其成员变量在结构体内距离结构体开始部分的偏移量。即：&(type *)0->member就是取出其成员变量的偏移地址。而其等于其在结构体内的偏移量:即为：(size_t)(& ((type *)0)->member)经过size_t的强制类型转换后，其数值为结构体内的偏移量。该偏移量这里由offsetof()求出。

    2.typeof( ( (type *)0)->member )为取出member成员的变量类型。用其定义__mptr指针；ptr为指向该成员变量的指针。__mptr为member数据类型的常量指针，其指向ptr所指向的变量处。

    3.(char *)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member) )用来求出结构体起始地址（为char *型指针），然后(type *)( (char *)__mptr - offsetof(type,member) )在(type *)作用下进行将字节型的结构体起始指针转换为type *型的结构体起始指针。

    这就是从结构体某成员变量指针来求出该结构体的首指针。指针类型从结构体某成员变量类型转换为该结构体类型。

    介绍了上面的几种基本宏后，对list_entry的理解就容易了。 list_entry()宏，获取当前list_head链表节点所在的宿主结构项，定义在include/linux/list.h。 第一个参数为当前list_head节点的指针，即指向宿主结构项的list_head成员。 第二个参数是宿主数据结构的定义类型。 第三个参数为宿主结构类型定义中list_head成员名。

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

    扩展替换为：

#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

     另外由list_entry()引申的函数有list_first_entry，list_for_each_entry，list_for_each_entry_reverse等都不再赘述。