项目Linux研究
Source
Edit
History

内核数据结构之映射

我们一般称键值对数组为映射，也称为哈希。一般查找的时间复杂度可以低至常数级别。在高频次的查询场景中，有较为优异的性能。关于映射的性质，我们不过多讨论，本文主要看看 Linux 中映射的实现，本文以 Linux 2.6.12 版本为例。

Linux 实现的映射，并不是一个通用的映射。他的目标是：映射一个唯一数（UID）到一个指针。

一、实现结构

Linux 提供了结构体 idr 用来完成这一目标。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct idr_layer {
	unsigned long		 bitmap;
	struct idr_layer	*ary[1<<IDR_BITS];  // 64 位机器 IDR_BITS 为 6
	int			 count;
};

struct idr {
	struct idr_layer *top;
	struct idr_layer *id_free;
	int		  layers;
	int		  id_free_cnt;
	spinlock_t	  lock;
};
  • top：指向顶层（最高层），

使用一些接口来构造一个 idr 数据结构，并进行初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static  int init_id_cache(void)
{
	if (!idr_layer_cache)
		idr_layer_cache = kmem_cache_create("idr_layer_cache", 
			sizeof(struct idr_layer), 0, 0, idr_cache_ctor, NULL);
	return 0;
}

void idr_init(struct idr *idp)
{
	init_id_cache();
	memset(idp, 0, sizeof(struct idr));
	spin_lock_init(&idp->lock);
}

其中 idr_layer_cache 是一个全局变量，在初始化 idr 的时候，会尝试对 idr_layer_cache 进行初始化一次。暂时不用理 kmem_cache_create 方法的含义，只需要知道他是为 idr_layer_cache 获取到了内存空间即可。

然后将用户传入的 idr 结构体指针的空间，全部置为 0，并初始化结构体中的锁。

二、分配一个 UID

构造好 idr 之后，就可以分配新的 UID 了。这个过程分为两步。

  • 告诉 idr，我们需要分配新的 UID，允许其在必要时可以调整后备树的大小
  • 请求新的 UID

对于第一步，我们可以使用 idr_pre_get 这个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void free_layer(struct idr *idp, struct idr_layer *p)
{
	/*
	 * Depends on the return element being zeroed.
	 */
	spin_lock(&idp->lock);
	p->ary[0] = idp->id_free;
	idp->id_free = p;
	idp->id_free_cnt++;
	spin_unlock(&idp->lock);
}

int idr_pre_get(struct idr *idp, unsigned gfp_mask)
{
	while (idp->id_free_cnt < IDR_FREE_MAX) {
		struct idr_layer *new;
		new = kmem_cache_alloc(idr_layer_cache, gfp_mask);
		if(new == NULL)
			return (0);
		free_layer(idp, new);
	}
	return 1;
}

IDR_FREE_MAX 这个值经过计算，在 64 位机器上是 12。感兴趣可以去计算一下。