Linux内核数据结构(链表、队列、红黑树)

Linux和其他大型软件项目一样,需要用到各种各样的数据结构.
在内核场景下,对数据结构的实现主要有以下几点要求:
1) 高性能:作为内核基本库一定要快.
2) 通用性:内核开发者尽可能复用,不重复造轮子防止膨胀.
3) 易用性:接口和参数尽量少,用法明确.
4) 安全性:主要指并发访问等,本文暂不关注.
在这几点的综合考虑权衡下,c语言的内核的相关实现都有其独特的地方.
本文从内核中使用最广的链表(list)、队列(fifo)、红黑树三种结构出发快速考察体验一番.

一、链表

链表list是内核中最简单和使用最多的,早期的做法是每人都为自己的链表类型实现一套操作.
为了不重复开发尽可能使用同一套,现在内核单独把链表抽象成了源码级插件,如果开发者需要,
仅需将内核链表节点插入到自己的结构体中,就可以将其变为链表类型.
链表节点中的指针不是指向wrapper结构体地址,而是指向相邻的链表节点.

这样做有几个好处:
a) 大家都用同一套链表节点定义,因而可以提供统一的链表操作函数.
b) 链表核心结构与用户数据无关,达到了通用(generic).
c) 系统无关,空间分配由上层负责,本身是纯逻辑模块.
d) 使用上扩展起来也更加灵活,比如让同一个实体处于多套链表中只需为其添加链接节点.

具体举例:

//链表结点定义 linux/list.h
struct list_head {
	struct list_head *next, *prev;
};

//链表操作
static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_del(struct list_head *entry);
//lots more...

//使用者代码示例...linux/sched.h
//Linux进程结构体
struct task_struct {
	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
	void *stack;
        //...
	struct list_head children;	/* list of my children */
	struct list_head sibling;	/* linkage in my parent's children list */     
        //...
};

从定义看linux的list本质上是带头结点的双向循环链表.
这种链表的实现可以非常精简高效,头结点作为哨兵结点避免了一些边界情况的判断:
一个链表如果存在,即使为空,也至少包含一个头结点.

上面task_struct中真正作为链接器节点的是sibling(task本身作为子进程),children只是指向其子进程链表(task本身作为父亲).
具体而言,链表节点(list_head)在使用上分为两种:
1. 作为内嵌到用户结构体中的桩,其wrapper struct一定是链表中的数据结点.
2. 作为链表头结点指针,其wrapper struct与链表数据一般没有关系,仅持有对链表的引用.

作图说明:

task_sliblings

task_sliblings


如图所示,sibling是将孩子们串到一起的第1类链接节点,位于所有子进程task_struct中;
children是父进程task_struct中指向该链表的指针,只是恰好也放在了task_struct里.

最后linux提供了一组编译宏方便我们直接在用户结构体层面进行操作,如以下遍历子进程的代码:

//visit each child of (task_struct *)parent;

struct task_struct *child;
list_for_each_entry(child, &parent->children, sibling) {
    //child now points to next task_struct in the children list
    //do sth with child
}

链表适合数据量不大的遍历场景;用链表也可以实现栈和队列.

二、队列
kfifo本质上是个循环队列,空间连续总大小固定,每个元素类型大小一致,
适合容量比较明确的一些生产-消费者场景.
因为无需操作指针,比链表实现的队列更高效.
队列的空间可以由内核初始化时从kmalloc分配,也可以用户指定.
队列大小(元素个数size)会被调整为2的幂次(原因下面会说).

kfifo核心定义:

struct __kfifo {
	unsigned int	in;      //入队列(队尾)虚拟指针,只增,指向下一个空位
	unsigned int	out;     //出队列(队头)虚拟指针,只增,小于等于in,指向下一个出队元素
	unsigned int	mask;    //用于映射计算实际指针,size == mask + 1
	unsigned int	esize;   //元素大小
	void		*data;   //backing memory
};

kfifo的实现也很精炼,有几个特点:
a) in和out本身是只增的,并且始终保持 in>=out.
当in==out时队列为空,in-out==size时队列满.

b) 在需要时才将in和out映射到实际位置(效果同取摸)
为了更快采用位运算即如 in & mask的方式.

mask是根据元素个数事先算好的:mask = size - 1. 这就是为什么要求size为2的幂.

再来看a)中队列为空和队列为满的条件,一般的循环队列为了区分队列为空和队列为满这两种情况,
需要浪费一个元素的空间,而内核的循环队列可以把空间全部利用上,没有任何浪费.
其原因在于in和out的表示,不必始终指向真实位置,而是采用虚拟指针方式,始终自增,从不绕回;
在需要计算实际地址的时候才使用mask临时做映射,判断队列状态只需用in和out之差.
这样就不存在冲突问题了,因为队列为空和为满回到了其原本的判定方式.
作图说明:
kfifo
可以看到,in总是比out大,其差值是当前队列元素个数,这和队列原始逻辑视图是一致的.

需要时再做映射,这样处理本质上是缩小用于work-around的特殊实现部分的范围.
参考入队列的代码:

//剩余空间
static inline unsigned int kfifo_unused(struct __kfifo *fifo)
{
	return (fifo->mask + 1) - (fifo->in - fifo->out);
}

//入队操作
unsigned int __kfifo_in(struct __kfifo *fifo,
		const void *buf, unsigned int len)
{
	unsigned int l;

	l = kfifo_unused(fifo);  
	if (len > l)
		len = l;  //不超过最大空间

	kfifo_copy_in(fifo, buf, len, fifo->in);   //copy到in的实际位置,内部计算地址使用mask
	fifo->in += len;   //更新in指针,in只会一直增加
	return len;
}

三、红黑树

红黑树是一种自平衡的二叉查找树,内核中主要用于大量元素高效查找和动态更新的场景,如CFS调度、epoll等.
红黑树通过维护以下若干特性来保持树的大致平衡:
1) 每个节点要么是红色,要么是黑色.
2) 树根节点是黑色.
3) 叶子节点不含数据,且为黑色.
4) 红色节点的子节点必为黑色.
5) 从树根到任意一叶子节点的路径上的黑色节点个数都相同.
注意4)蕴含了红色结点的父节点必为黑色;5)蕴含了其对红黑树的任意子树也成立.
另外任意黑节点为根的子树是红黑树;红节点为根的子树将其根染黑后也是红黑树.

以上第4和5点可以保证根到叶子的最长路径不超过最短路径的2倍,因而是大致平衡的(树高h<2lg(n+1)).
为什么一定是这一批性质呢,这是由Sedgewick等教授精细设计的(最早从某类B树启发,见wiki).
设计目标是使得在插入、删除等修改场景下对这些性质(即树的平衡)的维护代价尽量小(虽然编程实现不简单),均摊复杂度为O(1). 而作为对比,AVL是高度平衡的,左右子树最多相差一层,对查找而言更高效,但插入、删除等修改操作下对其维护代价更大,算法复杂度为O(lg(n)).
因此如果数据集合是静态的则适合用AVL树,因为只用build一遍;而内核场景状态是快速变化的,显然红黑树更适用.

具体如何维护这些性质呢,简单来说,就是当搜索树发生了插入、删除等操作后,如果有性质被破坏(意味可能已失衡),通过搜索树的基本旋转操作(调整两边树高),加上相关节点颜色的改变等措施,总能使性质得到恢复.

具体算法参考WikiRbtree,linux基本是按此实现的.
linux红黑树的使用和实现有以下几个特点:
a) 和list一样,通过内嵌红黑树节点rb_node到宿主结构体的方式来灵活支持rb树的引入.
b) 提供了插入、删除后的动态平衡调整接口,但不提供查找过程,需使用者自己实现.
c) 在时间和空间上处理细节非常高效到位,特别是前者,后面举例说明.

不提供查找是因为元素的比较逻辑由其宿主数据决定,而树节点本身和链表一样是key无关的,
因此只能通过回调的方式来实现通用的查找操作,但linux主要从性能角度出发不鼓励使用回调,
而是交给开发者自己实现高效查找,好在二叉树查找本身结构很简单,虽然可能会引入一些重复代码.
这里的本质问题是通用性(generic)和高性能上一般不可兼顾,特别对于c语言而言.
(链表list能做到是因为其上的操作与用户数据无关,除了指针的指向,而linux也将其解决了)

树节点的定义:

//linux/rbtree.h
struct rb_node {
	unsigned long  __rb_parent_color;   //父节点指针以及本节点颜色
	struct rb_node *rb_right;
	struct rb_node *rb_left;
};

#define	RB_RED		0
#define	RB_BLACK	1
...
#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

//lib/rbtree.c
static inline struct rb_node *rb_red_parent(struct rb_node *red)
{
	return (struct rb_node *)red->__rb_parent_color;
}

这里看到一个省空间的普遍做法是,由于结构体里都是long类型,整体也是按long做内存地址对齐的,即地址的最后2个bit一定是0,于是parent指针可以同时也用来存color(只需1个bit). 所以rb_parent宏取实际父节点地址时要把后2个bit给mask掉.

另一个细节是在一些场景下,可以事先知道当前节点的颜色,比如新插入节点根据算法一定是红色,而红色bit为0,因此取其parent时不需要mask,于是专门有一个rb_red_parent内部函数优化处理,即不做mask直接返回.

红黑树insert调整算法相对简单,可以浏览下linux的实现:

static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;

	while (true) {
		/*
		 * Loop invariant: node is red
		 *
		 * If there is a black parent, we are done.
		 * Otherwise, take some corrective action as we don't
		 * want a red root or two consecutive red nodes.
		 */
		if (!parent) {
			rb_set_parent_color(node, NULL, RB_BLACK);
			break;
		} else if (rb_is_black(parent))
			break;

		gparent = rb_red_parent(parent);

		tmp = gparent->rb_right;
		if (parent != tmp) {	/* parent == gparent->rb_left */
			if (tmp && rb_is_red(tmp)) {
				/*
				 * Case 1 - color flips
				 *
				 *       G            g
				 *      / \          / \
				 *     p   u  -->   P   U
				 *    /            /
				 *   n            n
				 *
				 * However, since g's parent might be red, and
				 * 4) does not allow this, we need to recurse
				 * at g.
				 */
				rb_set_parent_color(tmp, gparent, RB_BLACK);
				rb_set_parent_color(parent, gparent, RB_BLACK);
				node = gparent;
				parent = rb_parent(node);
				rb_set_parent_color(node, parent, RB_RED);
				continue;
			}

			tmp = parent->rb_right;
			if (node == tmp) {
				/*
				 * Case 2 - left rotate at parent
				 *
				 *      G             G
				 *     / \           / \
				 *    p   U  -->    n   U
				 *     \           /
				 *      n         p
				 *
				 * This still leaves us in violation of 4), the
				 * continuation into Case 3 will fix that.
				 */
				tmp = node->rb_left;
				WRITE_ONCE(parent->rb_right, tmp);
				WRITE_ONCE(node->rb_left, parent);
				if (tmp)
					rb_set_parent_color(tmp, parent,
							    RB_BLACK);
				rb_set_parent_color(parent, node, RB_RED);
				augment_rotate(parent, node);
				parent = node;
				tmp = node->rb_right;
			}

			/*
			 * Case 3 - right rotate at gparent
			 *
			 *        G           P
			 *       / \         / \
			 *      p   U  -->  n   g
			 *     /                 \
			 *    n                   U
			 */
			WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
			WRITE_ONCE(parent->rb_right, gparent);
			if (tmp)
				rb_set_parent_color(tmp, gparent, RB_BLACK);
			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
			augment_rotate(gparent, parent);
			break;
		} else {
                        //对称处理,略.
		}
	}
}

这里代码还是很精简的,但已经可以开始看出临时变量复用的趋势了;尤其是到了delete调整的代码里(未贴出),由于算法本身也更复杂,临时变量复用得也较多,需要从局部细节和整体一起着手理解,毕竟作者应该也是仔细推敲后精细构造的代码;总之总体感受就是细节处很精致,但也牺牲了一定的直观性.

四、其他
内核中其他数据结构如map(idr)、radix-tree、bitmap、B+树等使用场景相对较少,部分与系统耦合,后面遇到了再分享.

五、小结
数据结构和算法原理都是一样的,而linus说过对内核来说"It's all about the details."
在保证良好的通用性、易用性的前提下,内核能把这些工具实现得比任何教科书伪码都更加精炼和极其高效,确实是集体智慧的精彩舞台.

参考资料:
1. Robert Love《Linux Kernel Development》3rd, chapter 6.
2. Linux-4.8.7

发表评论

电子邮件地址不会被公开。