Linux内核中通用链表的解析

在Linux中的list是系统通用链表，它广泛应用在系统各个地方，如系统消息队列、进程列表等地。可以说，只要有表的地方，就会用到这个list。
今天我们先解析一下跟初始化有关的代码：

1. 表头结点结构
struct list_head {
      struct list_head *next, *prev;
};
这和我们通常写链表一样，定义一个表头结点。
从next, prev可以看出，这是一个双向链表。
但区别是，这个结点结构中并没有内容，也就是我们常说的type data;
这也就是“通用”的体现吧。

2. #define LIST_HEAD_INIT(name) { &(name), &(name) }
定义一个LIST_HEAD初始化的宏，后面的大括号中内容我们目前似乎看不懂。

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

这样两个合在一起就看懂了，当执行LIST_HEAD(name)这个宏时，会创建一个头结点，并用&name初始化这个结点的两个成员指针。

3. static inline void INIT_LIST_HEAD(struct list_head *list)
{
      list->next = list;
      list->prev = list;
}
这是一个初始化头结点函数，把next和prev指向本身。
1. 下面介绍list的插入函数:
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
            struct list_head *prev,
            struct list_head *next);
#endif
这个函数的3个参数分别是:
new: 要插入的结点;
prev: 插入之后new的前一个结点;
next: 插入之后new的后一个结点.

下面接着的是:
#ifndef CONFIG_DEBUG_LIST
static inline void list_add(struct list_head *new, struct list_head *head)
{
  __list_add(new, head, head->next);
}
#else
extern void list_add(struct list_head *new, struct list_head *head);
#endif
这是将上面的3参函数改为2参函数的调用, 表示把new插入到head后面.

同理:
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
  __list_add(new, head->prev, head);
}
这表示把new插入到head前面.

接下来的:
static inline void __list_add_rcu(struct list_head * new,
      struct list_head * prev, struct list_head * next)
{
  new->next = next;
  new->prev = prev;
  smp_wmb();
  next->prev = new;
  prev->next = new;
}
引领的是几个rcu protected的插入函数.


2. 下面介绍list的删除函数:
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
  next->prev = prev;
  prev->next = next;
}
通过要删除结点的前后两结点作为参数,使它们互相指向.
static inline void list_del_init(struct list_head *entry)
{
  __list_del(entry->prev, entry->next);
  INIT_LIST_HEAD(entry);
}
删除entry结点, 并把它的prev和next值指向安全区(即自己).

#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{
  __list_del(entry->prev, entry->next);
  entry->next = LIST_POISON1;
  entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head *entry);
#endif
通过调用上面的__list_del函数实现删除结点, 并且指定entry结点prev,next指针的值.
两个宏在linux/poison.h中定义如下:
/********** include/linux/list.h **********/
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1   ((void *) 0x00100100)
#define LIST_POISON2   ((void *) 0x00200200)
细心的人可能发现了, 结点在被从list中删除后并没有释放, 这是因为在创建和插入结点的时候也没有申请资源, 在C/C++中的原则是哪里申请哪里释放.
rcu_del的函数同rcu_add, 不再说明.

3. 下面介绍list的替换函数：
static inline void list_replace(struct list_head *old,
          struct list_head *new)
{
  new->next = old->next;
  new->next->prev = new;
  new->prev = old->prev;
  new->prev->next = new;
}
这个函数用new结点替换list中的old结点.
static inline void INIT_LIST_HEAD(struct list_head *list)
{
  list->next = list;
  list->prev = list;
}
这个函数把参数中的list结点的prev和next指向自己.
static inline void list_replace_init(struct list_head *old,
              struct list_head *new)
{
  list_replace(old, new);
  INIT_LIST_HEAD(old);
}
这个函数是综合上面两个函数, 在用new替换old之后, 使old结点的prev和next指向安全区(即自己).
下面说一下list的move相关函数和empty相关判断函数:
1. static inline void list_move(struct list_head *list, struct list_head *head)
{
      __list_del(list->prev, list->next);
      list_add(list, head);
}
先解释一下参数, list是要移动的结点, head是移动的前一个位置.
即: 把list结点移动到head的后一个位置.
这是通过两步完成的:
先把list结点从链表中删除, 再把list结点插入到适当的位置.

2. static inline void list_move_tail(struct list_head *list,
            struct list_head *head)
{
      __list_del(list->prev, list->next);
      list_add_tail(list, head);
}
这是和move对应的tail函数.
即: 把list结点移动到head的前一个位置.

3. static inline int list_is_last(const struct list_head *list,
          const struct list_head *head)
{
  return list->next == head;
}
这个函数判断list结点是否为该链表的最后一个结点.
其中参数list是被判断结点, head是该链表的头结点.

4. static inline int list_empty(const struct list_head *head)
{
  return head->next == head;
}
这个函数判断链表是否为空, 是通过比较head和head->next的值是否相等实现的, 这与表结点的初始化方法有关.
因为初始化/重置表结点时, 把该结点的prev和next都指向本身.
参数head是表头结点.

5. static inline int list_empty_careful(const struct list_head *head)
{
  struct list_head *next = head->next;
  return (next == head) && (next == head->prev);
}
这个函数判断链表是否为空, 并且检查是否有进程在修改prev和next成员.
首先记录下head->next, 比较next和head是否相等, 同时比较next和prev是否相等, 要确定它们都是指向head本身才行.
这个函数只能与带有_init的函数一起使用(如__list_del_init),因为这些函数是有"重置"操作的.
下面介绍Linux通用链表(list)的splice(合并)函数:
1. static inline void __list_splice(struct list_head *list,
            struct list_head *head)
{
  struct list_head *first = list->next;
  struct list_head *last = list->prev;
  struct list_head *at = head->next;

  first->prev = head;
  head->next = first;

  last->next = at;
  at->prev = last;
}
这个是标准的合并函数,把list合并到另一链表的head的后一个位置.

2. static inline void list_splice_init(struct list_head *list,
              struct list_head *head)
{
  if (!list_empty(list)) {
      __list_splice(list, head);
  }
}
这个函数是上面的应用版, 加了一个判断list是否为空.

3. static inline void list_splice_init(struct list_head *list,
              struct list_head *head)
{
  if (!list_empty(list)) {
      __list_splice(list, head);
      INIT_LIST_HEAD(list);
  }
}
这是一个init版的splice应用, 加判断, 并且在合并之后对list进行重置.
介绍一下list中的关键函数container_of:
/**
* 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)

关于container_of见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) );})
container_of在Linux Kernel中的应用非常广泛,它用于获得某结构中某成员的入口地址.
/*转注： 对于list的操作，这里 (type*)0 -> member 为某个struct list_head 类型的变量.
而typeof( ((type *)0)->member ) 的类型就为 struct list_head, 故最后成了
const struct list_head *__mptr = ptr 了。（用的太巧了!）
*/

关于offsetof见stddef.h中:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
TYPE是某struct的类型 0是一个假想TYPE类型struct,MEMBER是该struct中的一个成员. 由于该struct的基地址为0, MEMBER的地址就是该成员相对与struct头地址的偏移量.
关于typeof,这是gcc的C语言扩展保留字,用于声明变量类型.
const typeof( ((type *)0->member ) *__mptr = (ptr);意思是声明一个与member同一个类型的指针常量 *__mptr,并初始化为ptr.
(type *)( (char *)__mptr - offsetof(type,member) );意思是__mptr的地址减去member在该struct中的偏移量得到的地址, 再转换成type型指针. 该指针就是member的入口地址了.
举例说明:
约定: 地址由高向低分配, 分配后指针指向高地址, 结构按逆序由高向低存储, 不做对齐处理.
struct snow
{
  char name;   // 1
  int size;   // 4
  time_t hold; // 16
};
struct snow *p = (struct snow)malloc(sizeof(struct snow));
上面我们已经在堆中0x121至0x101分配了一个snow的struct, 并用p指针指向这段内存地址.
如果我们想取得p指向的结构中size变量的入口地址, 可以用container_of(p, struct snow, size);
这个调用的步骤是:
1` 取得p的指针地址, 121
2` 取得size在struct中的偏移量, 16
3` 相减获得size的入口地址, 105

通过这一个简单的例子应该能理解container_of的工作原理了, 这只是一个模仿的例子, 具体实现原理请参考ULK中的内存管理.
介绍一些list的iterate over函数：
1. #define list_for_each(pos, head) \
  for (pos = (head)->next; prefetch(pos->next), pos != (head); \
        pos = pos->next)
关于这个遍历的循环似乎没什么好说的, 从head->next开始, 用next指针遍历, prefetch的是将指针推入CPU L1 cache的操作.

#define __list_for_each(pos, head) \
  for (pos = (head)->next; pos != (head); pos = pos->next)
同上, 少了prefetch操作.

#define list_for_each_prev(pos, head) \
  for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
        pos = pos->prev)
这是用prev指针遍历的带prefetch的操作.

#define list_for_each_safe(pos, n, head) \
  for (pos = (head)->next, n = pos->next; pos != (head); \
      pos = n, n = pos->next)
安全的iterate over函数, 参数n是用于临时存储的链表.

2. #define list_for_each_entry(pos, head, member)           \
  for (pos = list_entry((head)->next, typeof(*pos), member);   \
      prefetch(pos->member.next), &pos->member != (head);     \
      pos = list_entry(pos->member.next, typeof(*pos), member))
这个函数中用到了前面解释过的著名的list_entry即container_of函数.
pos是一个type结构型指针, head是list头结点, member是struct中的成员.
可以看出, 这个函数是用next指针对member成员的遍历.

#define list_for_each_entry_reverse(pos, head, member)         \
  for (pos = list_entry((head)->prev, typeof(*pos), member);   \
      prefetch(pos->member.prev), &pos->member !=(head);     \#define list_for_each_entry_from(pos, head,member)         \
  for (; prefetch(pos->member.next), &pos->member != (head);   \
      pos = list_entry(pos->member.next, typeof(*pos), member))
      pos = list_entry(pos->member.prev, typeof(*pos), member))
同上, 是用prev指针对member成员的遍历.

#define list_prepare_entry(pos, head, member) \
  ((pos) ? : list_entry(head, typeof(*pos), member))
获得pos指针, 用于list_for_each_entry_continuer(). 当如果pos为空时, 获得head结点的member成员入口地址.

#define list_for_each_entry_continue(pos, head, member)       \
  for (pos = list_entry(pos->member.next, typeof(*pos), member);   \
      prefetch(pos->member.next), &pos->member != (head);   \
      pos = list_entry(pos->member.next, typeof(*pos), member))
用next指针对member成员进行从pos开始的继续遍历.

#define list_for_each_entry_from(pos, head, member)         \
  for (; prefetch(pos->member.next), &pos->member != (head);   \
      pos = list_entry(pos->member.next, typeof(*pos), member))
用next指针对member成员进行从当前位置开始的继续遍历.

3. safe系列和rcu系统函数类似于上面的, 不再重复.