Linux 内核数据结构：双向链表（二）

2015-6-24 10:28 |来自: http://blog.jobbole.com/ 1561 0

摘要: 现在我们看看设备驱动是如何使用链表维护设备列表的，首先，我们看一下miscdevice的 struct 定义：struct miscdevice { int minor; const char *name; const struct file_operations *fops; struct list_head li ...

关键词： nbsp list head struct member 成员 miscdevice type 变量指针

现在我们看看设备驱动是如何使用链表维护设备列表的，首先，我们看一下miscdevice 的 struct 定义：

struct miscdevice
{
  int minor;
  const char *name;
  const struct file_operations *fops;
  struct list_head list;
  struct device *parent;
  struct device *this_device;
  const char *nodename;
  mode_t mode;
};

可以看到 miscdevice 的第四个成员 list ，这个就是用于维护已注册设备链表的结构。在源代码文的首部，我们可以看到以下定义：

static LIST_HEAD(misc_list);

这个定义宏展开，可以看到是用于定义 list_head 类型变量：

#define LIST_HEAD(name) 
    struct list_head name = LIST_HEAD_INIT(name)

LIST_HEAD_INIT 这个宏用于对定义的变量进行双向指针的初始化：

#define LIST_HEAD_INIT(name) { &(name), &(name) }

现在我看可以看一下函数 misc_register 是如何进行设备注册的。首先是用INIT_LIST_HEAD 对 miscdevice->list 成员变量进行初始化：

INIT_LIST_HEAD(&misc->list);

这个操作与 LIST_HEAD_INIT 宏一致：

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

接下来，在通过函数 device_create 进行设备创建，同时将设备添加到 Misc 设备列表中：

list_add(&misc->list, &misc_list);

内核的 list.h 文件提供向链表添加节点的 API，这里是添加操作的实现：

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

函数实现很简单，就是入参转换为三个参数后调用内部 __list_add ：

new – new entry;
head – list head after which will be inserted new item;
head->next – next item after list head.

_list_add 函数的实现更加简单：

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;
}

这里设置了新添加结点的 prev 与 next 指针，通过这些操作，就将先前使用LIST_HEAD_INIT 所定义的 misc 链表的双向指针与 miscdevice->list 结构关联起来。

这里还有一个问题，就是如何获取链表中的数据， list_head 提供了一个特殊的宏用于获取数据指针。

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

这里有三个参数

ptr：list_head 结构指针
type：数据对应的 struct 类型
member：数据中 list_head 成员对应的成员变量名

举例如下：

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

接下来我们就够访问 miscdevice 的各个成员，如 p->minor 、 p->name 等等，我们看一下 list_entry 的实现：

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

其实现非常简单，就是使用入参调用 container_of 宏，宏的实现如下：

#define container_of(ptr, type, member) ({                      
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    
    (type *)( (char *)__mptr - offsetof(type,member) );})

注意，宏使用了大括号表达式，对于大括号表达式，编译器会展开所有表达式，同时使用最后一个表达式的结果进行返回。

举个例子：

#include <stdio.h>

int main() {
    int i = 0;
    printf("i = %dn", ({++i; ++i;}));
    return 0;
}

输出结果为 2 。

另一个关键是 typeof 关键字，这个非常简单，这个正如它的名字一样，这个关键字返回的结果是变量的类型。当我第一次看到这个宏时，最让我觉得奇怪的是表达式((type*)0) 中的 0 值，实际上，使用 0 值作为地址这个是成员变量取得 struct 内相对偏移地址的巧妙实现，我们再来看个例子：

#include <stdio.h>
struct s {
  int field1;
  char field2;
  char field3;
};
int main() {
    printf("%pn", &((struct s*)0)->field3);
    return 0;
}

输出结果为 0x5 。

还有一个专门用于获取结构体中某个成员变量偏移的宏，其实现与前面提到的宏非常类似：

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

这里对 container_of 宏做个综述， container_of 宏通过 struct 中的list_head 成员返回 struct 对应数据的内存地址。在宏的第一行定义了指向list_head 成员的指针 __mptr ，并将 ptr 地址赋给 __mptr 。从技术实现的角度来看，实际并不需要这一行定义，但这个对于类型检查而言非常有意义。这一行代码确保结构体（ type ）中存在 member 对应的成员。第二行使用 offsetoff 宏计算出包含 member 的结构体所对应的内存地址，就是这么简单。

当然 list_add 与 list_entry 并非是 <linux/list.h> 中的全部函数，对于双向链表 list_head ，内核还提供了以下的接口：