2016-03-06

linux内核中的数据结构

双向循环链表

双向循环链表是linux内核中的一个重要的数据结构。

其节点，定义在 linux/types.h 头，文件中：

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

想初始化一个节点，可以用 linux/list.h 头文件中定义的宏LIST_HEAD()，在stack
中由编译器自动分配一个节点，并且将 prev 和 next 的指向节点自身。

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

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

如果在已经有了一个节点(这个节点可以是在 heap 中动态分配的)，我们可以用
INIT_LIST_HEAD 进行初始化。初始化的效果和 LIST_HEAD 相同。

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

双向循环链表的操作

这里仅列出一些基本的操作。

list_add() 和 list_add_tail
list_add() 在 head 之后插入节点，list_add_tail 在 head 之前插入节点。

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

list_del()

 static inline void list_del(struct list_head *entry)
 {
     __list_del(entry->prev, entry->next);
     entry->next = LIST_POISON1;
     entry->prev = LIST_POISON2;
 }
 
 static inline void __list_del(struct list_head * prev, struct list_head * next)
 {
     next->prev = prev;
     WRITE_ONCE(prev->next, next);
 }

list_replace()

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

list_empty()

 static inline int list_empty(const struct list_head *head)
 {
     return head->next == head;
 }
 
 static inline int list_empty_careful(const struct list_head *head)
 {
     struct list_head *next = head->next;
     return (next == head) && (next == head->prev);
 }

list_for_each()

从 head 开始，遍历整个循环链表。

 #define list_for_each(pos, head) \
     for (pos = (head)->next; pos != (head); pos = pos->next)

节点与数据

双向循环链表的节点并不包含我们所要存储管理的数据，我们通常将 list_head
节点嵌入到一个结构体中。

struct A {
    ...
    struct list_head node;
    ...
}

这样，我们就能够利用 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_head within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

对于 container_of() 的原理，不是节讨论的重点，可能会在其他的文章讨论。

双向循环链表应用实例

kobject 是 linux 内核中的一个重要的结构体。以 kobject 为节点，搭建起了
linux 内核中的设备驱动模型。kset 是 kobject 的集合。

struct kset {
    struct list_head list;
    struct kobject kobj;
    ...
};

struct kobject {
    const char		*name;
    struct list_head	entry;
    struct kset		*kset;
    ...
};

kobject 与 kset 结构体中的 list 和 entry 域，代表了双向循环列表中的节点。
其中，list 表示双向循环链表中最初的根节点; entry 表示之后要添加/删除的节点。
kobject 中的 kset 域指向将要插入的 kset 结构体。可以通过 kobj_kset_join()
将 kobject 插入到与之关联的 kset 中。

static void kobj_kset_join(struct kobject *kobj)
{
    if (!kobj->kset)
        return;

    kset_get(kobj->kset);
    spin_lock(&kobj->kset->list_lock);
    list_add_tail(&kobj->entry, &kobj->kset->list);
    spin_unlock(&kobj->kset->list_lock);
}

可见，将 kobject 插入到 kset 的实质是向以 kset 中 list 域为表头的双向循环
列表尾部添加节点 entry。也就是对 list_add_tail() 的调用。