深入浅出Linux之内核数据结构


内核使用的数据结构有双向链表，单向链表和hash链表。另外，基树和红黑树也是内核使用的数据结构。实际上，这也是程序代码中通常使用的数据结构，一些偏僻难的数据结构并不常见。

1. container

  container是linux很重要的一个概念。有了container方法，才能实现对对象的封装。

  分析一下container方法。

======================================================================

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

        const typeof( ((type *)0)->member ) *__mptr = (ptr);      \

        (type *)( (char *)__mptr - offsetof(type,member) );})

  这个方法巧妙的实现了通过结构的一个成员找到整个结构的地址。有了container方法，list才

成为了一个通用的数据结构，通过container方法，还可以实现内核的封装，程序之间不暴露

内部的数据。

 

2. 双向链表list

  List定义在/include/linux目录下。首先看看list的结构定义：

  struct list_head {

       struct list_head *next, *prev;

  };

  List是双向链表的一个抽象，list库提供了list_entry，使用了container方法，通过container 可以从list找到整个数据对象，这样list就成为了一种通用的数据结构。

======================================================================

#define list_entry(ptr, type, member) \

       container_of(ptr, type, member)

 

  内核定义了很多对list结构操作的内联函数和宏，计有：

  •    LIST_HEAD：定义并初始化一个list链表
  •    list_add_tail：加一个成员到链表尾

  •    list_del：删除一个list成员

  •    list_empty：检查链表是否为空
  •    list_for_each：遍历链表。得到链表指针。
  •    list_for_each_safe：遍历链表。和list_for_each区别是可以删除遍历的成员
  •    list_for_each_entry：遍历链表，通过container方法返回结构指针。

3.  hash list

  Hash list和双向链表list很相似，它适用于hash表。看一下hash list的head定义：

 struct hlist_head {

       struct hlist_node *first;

};

  和通常的list比较，hlist头只有一个指针，这样就节省了一个指针的内存。如果hash表非常

庞大，那么每个hash 表头节省一个指针，整个hash表节省的内存就很可观了。这就是内核

中专门定义hash list的原因。

 

Hash list库提供的函数和list很相似，计有：

l        HLIST_HEAD：定义并初始化一个hash list链表头

l        hlist_add_head：加一个成员到hash链表头

l        hlist_del：删除一个hash list成员

l        hlist_empty：检查hash 链表是否为空

l        hlist_for_each：遍历hash 链表。

l        hlist_for_each_safe：遍历链表。和hlist_for_each区别是可以删除遍历的成员

l        hlist_for_each_entry：遍历hash 链表，通过container方法返回结构指针

 

4.      单向链表

  内核中，没有提供单向链表的定义。但实际上，有多处使用了单向链表的概念。

======================================================================

       for (i = 0, p -= n; i < n; i++, p++, index++) {

              struct probe **s = &domain->probes[index % 255];

              while (*s && (*s)->range < range)

                     s = &(*s)->next;

              p->next = *s;

              *s = p;

       }

  上面的例子是加入一个新的字符设备到系统的表里面。在系统的字符设备表里，

probe结构其实就是单向链表。这种结构在内核中应用很广泛。

 

5.    red-black tree

  红黑树位于/lib/rbtree.c文件。红黑树是一种自平衡的二叉树。实际上，红黑树可以看做是折半查找。我们知道，排序的快速做法是取队列的中间值比较，然后在剩下的队列中再次取中间值比较，迭代进行直到找到最合适的位置。红黑树实际就是实现了这种算法。

  那么红黑树里面的“红黑”代表什么意思？红黑的颜色处理是避免树的不平衡。举个例子，如果1，2，3，4，5五个数字依次插入一颗红黑树，那么五个值都落在了树的右侧，如果6再插入这颗红黑树，那么需要比较五次。“红黑规则”就要将树旋转，树的根部要落在3这个节点，只需要比较两次，这样就避免了树的不平衡导致的问题。

  内核中的io调度算法和内存管理中都使用了红黑树。红黑树有很多介绍的文章，读者可以结合代码分析一下。

 

6.      radix tree

  内核提供了一个基树库，代码在/lib/radix-tree.c文件。基树是一种空间换时间的数据结构，

通过空间的冗余减少了时间上的消耗。用一张图来分析：

       

   图中显示，元素空间总共为256，但元素个数不固定。那么如果用数组存储，好处是插入查找只用一次操作，但是存储空间需要256，这是不可思议的。如果用链表存储，存储空间节省了，但是极限情况下查找操作次数等于元素的个数。而采用一颗高度为2的基树，第一级最多16个冗余结构，代表元素前四位的索引。第二级代表元素后四位的索引。那么只要两级查找就可以找到特定的元素，而且只有少量的冗余数据。图中假设只有一个元素10001000，那么只有树的第一级有元素，而且树的第二级只有1000这个节点有子节点，其它节点都不必分配空间。这样既可以快速定位查找，也减少了冗余数据。

  基树很适合存储稀疏的数据，内核中文件的页cache就采用了基树。关于基树的文章很多，读者可以结合代码分析一下。

相关内容