LKD（Linux内核设计与实现） Chapter 6 Kernel Data Structures

这个章节主要阐述了内核中主要的几种数据结构，如链表、队列以及映射。Linux内核是用C语言写的，所以这些数据结构的实现受限于C语言的特点，大都没有精致的封装，很多细节需要写代码的人自己敲定。学习这些数据倒是可以帮助大家更好理解C语言一些精巧高效的使用方式。

链表

链表应该是内核最通用的结构了。一般来说，在C++这种支持泛型的语言中，链表作为是一个单独的数据类型使用，要存储的数据是被存放到链表中去的；然而Linux链表的实现方式比较奇特，这也是由于C不支持泛型，它把链表作为属性插入其他数据结构中去，这个做法英文叫做Embedded Anchor，下面是一个例子：

在上面的例子中，往struct dog嵌入一个属性struct list_head list，这样struct dog就可以通过这个属性变成一个双向链表了。struct list_head list的定义在include/linux/types.h：

可以通过INIT_LIST_HEAD宏来初始化链表：

include/linux/kernel.h提供了一个宏container_of(ptr, type, member)可以从链表节点找到其所在结构体的指针：

include/linux/list.h定义了很多链表的操作，其中有很多宏用来帮助遍历链表, 其中有代表性的如：

  • list_for_each(pos, head)
  • list_for_each_entry(pos, head, member)

上面只是简单介绍了一下Linux的链表的特点。由于是用C语言实现的，所以Linux采用了另辟蹊径的方式，将链表节点嵌入于不同的数据结构体中，来实现链表的泛型。这种可行性也基于一个事实，Linux的链表只为内核中的数据结构所用，链表和链表的使用者在同一个维度，链表假设它的使用者足够聪明能把问题搞对。

以此类推，Linux内核数据结构的封装程度都不高，他们不需要像C++STL库那样封装得密不透风。因为STL库不知道谁会使用它，以及以怎么样的方式使用它，所以它要把自己的责任划清。而内核的数据结构的使用者知道自己在干什么，过度的封装反而是枷锁。

队列和映射

内核的队列叫做kfifo（include/linux/kfifo.h），是一个定长的循环队列，需要在初始化的时候分配或者指定缓冲区：

  • kfifo_alloc(fifo, size, gfp_mask) 初始化一个fifo并为其分配缓冲区
  • kfifo_init(fifo, buffer, size) 使用指定的缓冲区来初始化一个fifo

然后是一些常规的操作：

  • kfifo_in(fifo, buf, n) 将数据放到fifo
  • kfifo_out(fifo, buf, n) 从fifo取出数据
  • kfifo_out_peek(fifo, buf, n) 从fifo窥取数据

映射是一种关联数据类型，把一个键关联到一个值。因为内核有好多操作都是代表进程执行的，所以这里的映射特指以用户进程id为键的映射，这个数据类型的名字叫idr（include/linux/idr.h）。映射的一般操作包括创建、插入、删除，和查找：

  • void idr_init(struct idr *idp); 初始化这个idr
  • int ida_pre_get(struct ida *ida, gfp_t gfp_mask); 获取一个id前预先分配空间
  • int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); 获取一个最小的空闲id
  • void idr_remove(struct ida *ida, int id); 删除一个id
  • void idr_destroy(struct ida *ida);  销毁一个idr