【Linux】Linux内核数据结构:IDR(redix树)
1. 引言最近在系统里遇到了IDR结构体,后来看了一下,是内核的一个基础结构。这个是怎么引入的,引入是为了什么呢?最早的时候,我们的结构体是一个类似于大结构体套小结构体。struct A {int a1;int b1;struct B B1[12];struct C C1[8];...};当然,实际使用会有很多个这样的结构体,这样的结果就是导致A的结构体的size太大,在有些app中临时申请一个就
1. 引言
最近在系统里遇到了IDR结构体,后来看了一下,是内核的一个基础结构。
这个是怎么引入的,引入是为了什么呢?
最早的时候,我们的结构体是一个类似于大结构体套小结构体。
struct A {
int a1;
int b1;
struct B B1[1000];
struct C C1[8];
...
};
当然,实际使用会有很多个这样的结构体,这样的结果就是导致A的结构体的size太大,在有些app中临时申请一个就占掉大量空间。
后来改成了指针.
struct A {
int a1;
int b1;
struct B *B1[1000];
struct C *C1[8];
...
};
但是,当B1,C1的成员ID并不是0,1,2,3,4,5,6……这些很小的ID值时,我们如何定义结构体呢?
比如有1000个变量,ID稀疏的分布在 0 ~ 1000000000之间,他们的ID分别是:
B1[1000], B1[2001],B1[10000], B1[10000000]....
ID无规则且稀疏的分布在一个很大的区间内,这种应该怎么办呢?
- 使用数组
为了一个 B1[1000000000]的值,我们就定义一个B1[1000000000]的数组?这样确实可以快速寻址,但是占用的无效空间也实在是太大了。毕竟1000000000里面只有1000个是真实有效的数据。
struct A {
int a1;
int b1;
struct B B1[1000000000];
struct C *C1[8];
...
};
- ID映射
可能有人说了,我们把真实的ID存在结构体里,比如给struct B添加一项ID,index的下标还是用1、2、3、4、5……把真正的ID给存到结构体的ID里去。这确实也是一种方法,相当于用1、2、3、4、5去映射了真实的ID 1000,2001,10000,10000000……空间节省了,但是这样无法快速寻址。
比如针对上面的需求,我们定义一个B1[1000]的数组,然后把真实的ID存在B1[0].ID,B1[1].ID…这样,当我们需要查找一个ID为9999999的数据时,不得不从0开始,挨个取出所有的数据的ID来做比对。当数据数量很大,且这是一个非常频繁的操作时,就会显得效率低下。
struct B {
int id;
int data;
}
struct A {
int a1;
int b1;
struct B B1[1000];
struct C *C1[8];
...
};
- 链表
同理,我们用链表也是一样,为了找出我们需要的那个ID的数值,我们不得不遍历每一个节点,取出ID进行比对,依然显得效率低下。
那在linux内核里,大牛们是怎么解决这个问题的?
这就是IDR的数据结构。
2. 原理
2.1 树
简单介绍一下树的基本概念,
具体的讲解可以看这个,也是参考链接1。
转一张很好理解的图:
- node 节点:用圆圈表示,节点包含键、值、与指向后继节点的路径。
- root 树根:树的起始节点,一棵树有且仅有一个树根。
- leaf 树叶:树的最下层末梢节点,再无后继节点。
- internal node 内部节点: 树中间的节点,承上启下,在上层与后继都有节点。
- Path 路径:连结两个节点之间的直线,可以是双向箭头,也可以是单向箭头。
2.2 redix树
redix树是IDR的基础,什么是redix树呢,个人理解,就是一种2叉树。
根据一个int数的每一位是0还是1,我们可以选择向左还是向右分叉。
比如一个数据的ID是0b 10101,
但是实际上,一个redix有32位,我们也一般不会用单独的一位来做一个分支,比如IDR。
2.3 IDR
IDR是redix树的一种应用,它把一个32位的整形分成7级,每5位(或者2位)为一级。
31 30 | 29 28 27 26 25 | 24 23 22 21 20 | 19 18 17 16 15 | 14 13 12 11 10 | 9 8 7 6 5 | 4 3 2 1 0
这样形成的redix树,相对简洁一些,找起leaf来更加方便。
3. linux代码解读
Linux中IDR相关的代码位于: include/linux/idr.h. 在线代码
使用IDR的话,需要包含<linux/idr.h>
idr的结构体定义最新的linux版本中已经做了修改(5.10),这里我们还是4.9的老版本分析。
- 结构体
struct idr {
struct idr_layer __rcu *hint; /* 最近一个存储指针数据的的idr_layer结构*/
struct idr_layer __rcu *top; /* idr_layer顶层, 32叉树的根 */
int layers; /* idr树中的idr_layer层数量 */
int cur; /* current pos for cyclic allocation */
spinlock_t lock;
int id_free_cnt; /* idr_layer空闲链表中剩余的idr_layer个数 */
struct idr_layer *id_free; /* 指向idr_layer的空闲链表 */
};
struct idr_layer {
int prefix; /* the ID prefix of this idr_layer */
int layer; /* 层号 distance from leaf */
struct idr_layer __rcu *ary[1<<IDR_BITS]; /* 子idr_layer数组ary[32] */
int count; /* ary数组使用计数 */
union {
/* A zero bit means "space here" */
DECLARE_BITMAP(bitmap, IDR_SIZE); /* 标记位图,标记该idr_layer的ary数组使用情况 */
/* 该数组用于保存具体的指针数据或者指向子idr_layer结构,大小为1<<8=256项 */
struct rcu_head rcu_head;
};
};
- 函数接口是
void *idr_find_slowpath(struct idr *idp, int id);
void idr_preload(gfp_t gfp_mask);
int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask);
int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask);
int idr_for_each(struct idr *idp,
int (*fn)(int id, void *p, void *data), void *data);
void *idr_get_next(struct idr *idp, int *nextid);
void *idr_replace(struct idr *idp, void *ptr, int id);
void idr_remove(struct idr *idp, int id);
void idr_destroy(struct idr *idp);
void idr_init(struct idr *idp);
bool idr_is_empty(struct idr *idp);
这里重点看一下 idr_get_next
void *idr_get_next(struct idr *idp, int *nextidp)
{
struct idr_layer *p, *pa[MAX_IDR_LEVEL + 1];
struct idr_layer **paa = &pa[0];
int id = *nextidp;
int n, max;
/* find first ent */
p = *paa = rcu_dereference_raw(idp->top);
if (!p)
return NULL;
n = (p->layer + 1) * IDR_BITS;
max = idr_max(p->layer + 1);
while (id >= 0 && id <= max) {
p = *paa;
while (n > 0 && p) {
n -= IDR_BITS;
p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
*++paa = p;
}
if (p) {
*nextidp = id;
return p;
}
/*
* Proceed to the next layer at the current level. Unlike
* idr_for_each(), @id isn't guaranteed to be aligned to
* layer boundary at this point and adding 1 << n may
* incorrectly skip IDs. Make sure we jump to the
* beginning of the next layer using round_up().
*/
id = round_up(id + 1, 1 << n);
while (n < fls(id)) {
n += IDR_BITS;
--paa;
}
}
return NULL;
}
- 宏定义
#define idr_for_each_entry(idp, entry, id) \
for (id = 0; ((entry) = idr_get_next(idp, &(id))) != NULL; ++id)
#define idr_for_each_entry_continue(idp, entry, id) \
for ((entry) = idr_get_next((idp), &(id)); \
entry; \
++id, (entry) = idr_get_next((idp), &(id)))
idr_for_each_entry 宏定义是用的比较多的,用来遍历所有的节点。
中间调用了 idr_get_next 的接口去找下一个节点,当符合筛选条件后可以选择break出来。
4. 参考链接
更多推荐
所有评论(0)