Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

Vinllen Chen


To be a better coder

linux内核中的数据结构

  linux建议开发者使用其内建的数据结构,而不要自作主张搞一套山寨的。本文讲解内核中常用的4种数据结构:链表,队列,映射,二叉树。

1.链表

  链表包括单向链表(有一个后向指针),双向链表(有一个后向指针和一个前向指针),环形链表(首尾相连)。linux内核的标准链表采用环形双向链表形式实现。

1.1 链表数据结构

  linux内核方式与众不同,它不是将数据结构塞入链表,而是将链表节点塞入数据结构。比如,一个普通的链表节点:

struct Node {
  int data;
  struct Node *pre;;
  struct Node *next;
};

  linux下的实现是把前后指针抽出来,形成单独数据结构:

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

  然后插入数据节点中:

struct Node {
  int data;
  struct list_head list;
};

  我们不必担心找不到父结构中所含有的变量(比如Node中的data),可以通过宏container_of()找到任何变量。其实现如下:

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

使用这个宏,可以定义一个简单的函数便可以返回包含list_head的父类型结构体:

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

1.2 定义链表

  list_head本身没有意义--它需要被嵌入到你自己的数据结构中才能生效。
  链表使用前需要初始化,可以采用动态初始化和静态初始化。

1.3 链表头

  内核链表各个结点无差别。由于遍历时需要一个特殊指针索引到整个链表,而不是从一个链表结点触发。定义特殊的索引节点:LIST_HEAD(fox_list)。其实它也是一个常规的list_head。

1.4 操作链表

  添加节点:list_add
  把节点添加到链表尾:list_add_tail
  从链表中删除: list_del
  把一个节点从一个链表移到另一个链表:list_move
  检查链表是否为空:list_empty
  把两个未连接的链表合并在一起:list_splice

1.5遍历链表

  可以使用list_for_each()宏:

struct Node *node;
struct list_head *p;
list_for_each(p, &node_list) {
  p = list_entry(p, struct Node, list);
}

  也可以用list_for_each_entry(),捆绑以上两个宏。
  list_for_each_entry_reverse()用于反向遍历。

2.队列

  linux内核通用队列实现称为kfifo。其提供了两个主要操作:enqueue和dequeue,同时维护了两个偏移量:入口偏移和出口偏移。

2.1 创建队列

  同样有动态和静态方法。
  动态: int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);
  静态:DECLARE_KFIFO(name, size); INIT_KFIFO(name);
2.2 其他操作
  压入数据:kfifo_i\n
  出队列:kfifo_out
  遍历队列:kfifo_out_peek
  获取队列总大小:kfifo_size
  获取队列数据大小:kfifo_len
  获取队列还有的可用空间:kfifo_avail
  判断是否为空:kfifo_is_empty
  判断是否为满:kfifo_is_full
  重置队列,清空所有数据:kfifo_reset
  撤销一个使用kfifo_alloc()分配的队列:kfifo_free()

3.映射

  一个映射,也常称为关联数组,其实是一个由唯一键组成的集合,而每个键必然关联一个特定的值。这种键到值的关联关系称为映射。映射要至少支持三个操作:

  1. Add(key, value)
  2. Remove(key)
  3. value = Lookup(key)

  虽然,键到值的映射属于一个通用说法,但是更多时候特指使用二叉树而非散列表实现的关联数组。
  linux内核提供了简单,有效的映射数据结构。但是它并非一个通用的映射。因为它的目标是:映射一个唯一的标识符(UID)到一个指针。除了提供三个标准的映射操作外,linux还在add操作基础上实现了allocate操作。这个allocate操作不但向map中加入了键值对,而且还可以产生UID。
  idr数据结构用于映射用户空间的UID,比如将inodify_watch的描述符或者POSIX的定时器ID映射到内核中相关联的数据结构上,如inotify_watch或者k_itimer结构体。

3.1 操作

  初始化:idr_init
  分配一个新的UID:id_pre_get,idr_get_new
  查找UID:idr_find
  删除UID:idr_remove
  撤销idr(只释放idr中未使用的内存):idr_destory
  强制删除所有UID:idr_remove_all

4. 二叉树

  参考我另一个篇文章:红黑树和avl树的个人总结
  linux中的红黑树rbtree实现没有提供搜索和插入例程,这些例程希望由rbtree的用户自定义。

5. 数据结构以及选择

  如果对数据集合的主要操作是遍历数据,就使用链表。
  如果代码符合生产者/消费者模式,则使用队列,特别是如果希望要一个定长缓冲。另一个方面,如果你需要存储一个大小不明的数据集合,那么链表可能更合适,因为可以动态添加任何数量的数据项。
  如果需要映射一个UID到一个对象,就使用映射。映射可以帮助维护和分配UID。linux的映射接口是针对UID到指针的映射,它并不适合其他场景。但是如果你在处理发给用户空间的描述符,就考虑一下映射。
  如果需要存储大量数据,并且检索迅速,那么使用红黑树。搜索的时间复杂度是对数关系,同时能保证按序遍历事件复杂度是线性。比其他数据结构复杂一点,但其内存开销不高。但是,如果没有执行太多次时间紧迫的查找,则红黑树不是最好选择。
  另外,还有基树(trie类型)和位图。

参考:《Linux内核设计与实现》


About the author

vinllen chen

Beijing, China

格物致知


Discussions

comments powered by Disqus