DTS

Github: IDR

Email: BuddyZhang1 buddy.zhang@aliyun.com

目录

DTS

IDR 原理

IDR 简介

系统许多资源都用整数 ID 来标识，如进程 ID、文件描述符 ID、IPC ID 等；资源信息 通常存放在对应的数据结构中 (如进程信息存放在 task_struct 中、ipc 信息存放在 ipc_perm 中)，id 与 数据结构的关联机制有不同的实现，IDR 机制是其中的一种。

IDR，ID Radix 的缩写。IDR 主要用于建立 id 与指针(指向对应的数据结构) 之间的 对应关系。IDR 用类基数树结构来构造一个稀疏数组，以 id 为索引找到对应数组元素， 进而找到对应的数据结构指针。用到 IDR 机制的主要有：IPC id (消息队列 id、 信号量 id、共享内存 id 等)，磁盘分区 id (sda 中数字部分）等。

内核中的 IDR

Linux 内核提供了一套完整的 IDR 实现机制，其基于 Radix-tree。在 linux 4.19 之前 内核并未采用 xarray 代替 radix，但 linux 4.20 之后，内核采用 xarray 替代了 radix-tree，因此 IDR 的底层实现也发生了改变，但这不影响上层 IDR 的接口功能。 内核关于 IDR 的源码位于：

include/linux/idr.h
lib/idr.c

在 Linux 内核中，IDR 作为重要的基础数据，内核定义了相应的数据结构对 IDR 进行维护。

struct idr
struct idr {
        struct radix_tree_root  idr_rt;
        unsigned int            idr_base;
        unsigned int            idr_next;
};

内核定义了 struct idr 结构用来维护一个 IDR。idr_rt 成员定义了一棵 radix-tree 树； idr_base 成员用于指定 ID 分配的起始地址；idr_next 成员指定下一个 ID 的偏移号。

IDR 的架构原理

Linux 内核中，每个 IDR 都包含一个 radix-tree 树，内核在初始化完 IDR 之后，每当 需要分配新的 ID 与指针绑定的时候，IDR 通过计算 idr_base + idr_next 的值计算下一 个 ID 的值，并且从 radix-tree 中找到 ID 对应的 slot 供存储指针。由于 ID 申请 是连续的，因此从 radix-tree 来看，树都是往一侧偏移退化形成一个稀疏数组。如下图， 连续的 ID 导致树的偏移退化。

DTS

IDR 实践

IDR 内核中最小实践

驱动源码

实践源码 IDR on GitHub

/*
 * IDR.
 *
 * (C) 2019.06.04 <buddy.zhang@aliyun.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */

#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/mm.h>

/* header of radix-tree */
#include <linux/idr.h>

/* private node */
struct node {
	const char *name;
};

/* Root of IDR */
static DEFINE_IDR(BiscuitOS_idr);

/* node set */
static struct node node0 = { .name = "IDA" };
static struct node node1 = { .name = "IDB" };
static struct node node2 = { .name = "IDC" };
static struct node node3 = { .name = "IDD" };
static struct node node4 = { .name = "IDE" };

/* ID array */
#define IDR_ARRAY_SIZE	5
static int idr_array[IDR_ARRAY_SIZE];

static __init int idr_demo_init(void)
{
	struct node *np;
	int id;

	/* proload for idr_alloc */
	idr_preload(GFP_KERNEL);

	/* Allocate a id from IDR */
	idr_array[0] = idr_alloc_cyclic(&BiscuitOS_idr, &node0, 1,
							INT_MAX, GFP_ATOMIC);
	idr_array[1] = idr_alloc_cyclic(&BiscuitOS_idr, &node1, 1,
							INT_MAX, GFP_ATOMIC);
	idr_array[2] = idr_alloc_cyclic(&BiscuitOS_idr, &node2, 1,
							INT_MAX, GFP_ATOMIC);
	idr_array[3] = idr_alloc_cyclic(&BiscuitOS_idr, &node3, 1,
							INT_MAX, GFP_ATOMIC);
	idr_array[4] = idr_alloc_cyclic(&BiscuitOS_idr, &node4, 1,
							INT_MAX, GFP_ATOMIC);

	/* Interate over all slots */
	idr_for_each_entry(&BiscuitOS_idr, np, id)
		printk("%s's ID %d\n", np->name, id);

	/* end preload section started with idr_preload() */
	idr_preload_end();

	return 0;
}
device_initcall(idr_demo_init);

驱动安装

驱动的安装很简单，首先将驱动放到 drivers/BiscuitOS/ 目录下，命名为 idr.c， 然后修改 Kconfig 文件，添加内容参考如下：

diff --git a/drivers/BiscuitOS/Kconfig b/drivers/BiscuitOS/Kconfig
index 4edc5a5..1a9abee 100644
--- a/drivers/BiscuitOS/Kconfig
+++ b/drivers/BiscuitOS/Kconfig
@@ -6,4 +6,14 @@ if BISCUITOS_DRV
config BISCUITOS_MISC
        bool "BiscuitOS misc driver"
+config BISCUITOS_IDR
+       bool "IDR"
+
+if BISCUITOS_IDR
+
+config DEBUG_BISCUITOS_IDR
+       bool "IDR mini"
+
+endif # BISCUITOS_IDR
+
endif # BISCUITOS_DRV

接着修改 Makefile，请参考如下修改：

diff --git a/drivers/BiscuitOS/Makefile b/drivers/BiscuitOS/Makefile
index 82004c9..9909149 100644
--- a/drivers/BiscuitOS/Makefile
+++ b/drivers/BiscuitOS/Makefile
@@ -1 +1,2 @@
obj-$(CONFIG_BISCUITOS_MISC)     += BiscuitOS_drv.o
+obj-$(CONFIG_BISCUITOS_IDR)     += idr.o
--

驱动配置

驱动配置请参考下面文章中关于驱动配置一节。在配置中，勾选如下选项，如下：

Device Driver--->
    [*]BiscuitOS Driver--->
        [*]IDR
            [*]IDR mini

具体过程请参考：

Linux 4.19.1 开发环境搭建 – 驱动配置

驱动编译

驱动编译也请参考下面文章关于驱动编译一节：

Linux 4.19.1 开发环境搭建 – 驱动编译

驱动运行

驱动的运行，请参考下面文章中关于驱动运行一节：

Linux 4.19.1 开发环境搭建 – 驱动运行

启动内核，并打印如下信息：

usbcore: registered new interface driver usbhid
usbhid: USB HID core driver
IDA's ID 1
IDB's ID 2
IDC's ID 3
IDD's ID 4
IDE's ID 5
aaci-pl041 10004000.aaci: ARM AC'97 Interface PL041 rev0 at 0x10004000, irq 24
aaci-pl041 10004000.aaci: FIFO 512 entries
oprofile: using arm/armv7-ca9

IDR 在应用程序中最小实践

实践源码

实践源码 IDR on GitHub

开发者也可以使用如下命令获得：

wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDR/Basic/Makefile
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDR/Basic/idr_run.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDR/Basic/idr.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDR/Basic/idr.h
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDR/Basic/radix.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDR/Basic/radix.h

实践源码具体内容如下：

/*
 * IDR Manual.
 *
 * (C) 2019.06.01 <buddy.zhang@aliyun.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */
#include <stdio.h>
#include <stdlib.h>

/* IDR/IDA */
#include <idr.h>

/* private node */
struct node {
	const char *name;
};

/* Root of IDR */
static DEFINE_IDR(BiscuitOS_idr);

/* node set */
static struct node node0 = { .name = "IDA" };
static struct node node1 = { .name = "IDB" };
static struct node node2 = { .name = "IDC" };

/* ID array */
static int idr_array[8];

int main()
{
	struct node *np;
	int id;

	/* preload for idr_alloc() */
	idr_preload(GFP_KERNEL);

	/* Allocate a id from IDR */
	idr_array[0] = idr_alloc_cyclic(&BiscuitOS_idr, &node0, 1,
							INT_MAX, GFP_ATOMIC);
	idr_array[1] = idr_alloc_cyclic(&BiscuitOS_idr, &node1, 1,
							INT_MAX, GFP_ATOMIC);
	idr_array[2] = idr_alloc_cyclic(&BiscuitOS_idr, &node2, 1,
							INT_MAX, GFP_ATOMIC);

	idr_for_each_entry(&BiscuitOS_idr, np, id)
		printf("%s's ID %d\n", np->name, id);

	/* end preload section started with idr_preload() */
	idr_preload_end();
	return 0;
}

源码编译

使用如下命令进行编译：

make clean
make

源码运行

实践源码的运行很简单，可以使用如下命令，并且运行结果如下：

IDR/Basic$ ./idr
IDA's ID 1
IDB's ID 2
IDC's ID 3

DTS

IDR 在内核中的应用

IDR 初始化操作

IDR 机制中，内核使用 struct idr 数据结构维护着 IDR。在使用 IDR 之前需要对 IDR 进行初始化。初始化的内容主要包括 IDR 包含 radix-tree 的初始化，以及 分配 ID 的起始值。内核提供了多个接口函数用于 IDR 的初始化，开发者可以参考 下面的文章进行实践：

IDR 插入操作

IDR 插入操作就是从内核中分配一个 ID 与给定的指针进行绑定操作。IDR 机制中， 通过分配一个 ID 之后，并在 IDR 对应的 radix-tree 中找到 ID 对应的 slot， 然后将给定的指针存储在 slot 中，以此实现 ID 与指针绑定的原理。内核也提供了 相应的函数用于 ID 的插入操作，开发者可以参考下面的文章进行实践：

IDR 查询操作

IDR 查询操作就是通过 ID 找到对应的指针。IDR 通过 radix-tree 机制提供的函数， 实现了 ID 的快速查找到对应的 slot 之后，以此获得对应的指针。内核也提供了 相应的函数用于 ID 的查找操作，开发者可以参考下面的文章进行实践：

IDR 修改操作

IDR 修改操作就是通过 ID 替换与之绑定的指针。IDR 通过 radix-tree 机制提供的函数， 找到 ID 在 radix-tree 中对应的 slot，然后将 slot 的值替换成新值，以此实现 IDR 的修改操作。内核也提供了相应的函数用于 ID 的修改操作，开发者可以参考下面的 文章进行实践：

IDR 删除操作

IDR 删除操作指的是解除 ID 与之绑定的指针关系。IDR 通过删除操作将 ID 与指针 解除关系之后，并回收 ID。内核也提供了相应的函数用于 ID 的删除操作，开发者可以 参考下面的文章进行实践：

IDR 遍历操作

IDR 的遍历操作指的是遍历 IDR 所有 ID 对应的指针。内核也提供了相应的函数用于 ID 的遍历操作，开发者可以参考下面的文章进行实践：

IDR 其他操作

IDR 机制还提供了许多有用的接口，开发者可以参考如下文档进行实践：

IDR 内核接口函数列表

附录

BiscuitOS Home

BiscuitOS Driver

BiscuitOS Kernel Build

Linux Kernel

Bootlin: Elixir Cross Referencer

搭建高效的 Linux 开发环境

赞赏一下吧 🙂

MMU