DTS

Github: IDA

Email: BuddyZhang1 buddy.zhang@aliyun.com

目录

DTS

IDA 原理

IDA 简介

IDA 是一种基于 Radix 的 ID 分配机制。IDA 与 IDA 类似，也是基于 Radix-tree 的数 据结构。Radix-tree 是一种实现长整数与指针绑定的机制。其中 IDA 是将一个 ID 与指针 进行绑定。IDA 只不过是对 IDA 的一个封装, IDA 不需要记录指针, 仅仅是分配与管理 ID. 因此 IDA 的树叶的每个分支指向一个 struct ida_bitmap 结构或一个 bitmap, 这个 bitmap 中的每一个 bit 负责记录 ID, 置 1 表示已分配, 置 0 表示未分配. ID 号由对应 的 bit 在 IDA bitmap 中的位置以及 IDA bitmap 在整个树中的位置表示.内核中经常使用 IDA 进行 ID 分配。

内核中的 IDA

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

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

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

struct ida
struct ida {
        struct radix_tree_root  ida_rt;
};

内核定义了 struct ida 结构用来维护一个 IDA。ida_rt 成员定义了一棵 radix-tree 树； IDA 将 bitmap 存储在 radix-tree 的叶子节点上，如果是一般 bitmap，那么 IDA 将存储 bitmap 的节点标记为 exceptional 节点。如果叶子节点存储着 struct ida_bitmap 结构， 那么该节点作为一般节点存储 ida_bitmap.

struct ida_bitmap
struct ida_bitmap {
        unsigned long           bitmap[IDA_BITMAP_LONGS];
};

DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap);

内核定义了 struct ida_bitmap 结构，该结构用于存储 bitmap 数组。每个 ida_bitmap 结构一共能表示 IDA_BITMAP_LONGS * sizeof(unsigend long) * 8 个 bit。IDA 的 叶子节点可以存储 ida_bitmap 结构，并根据叶子在 IDA radix-tree 树中的位置计算出 bitmap 的位置，以此计算 ID 号。内核还未每个 CPU 定义了一个 ida_bitmap 的指针。

IDA 的架构原理

Linux 内核中，每个 IDA 都包含一个 radix-tree 树，IDA 不在注重长整数与指针的绑定， 而是将 bitmap 或 ida_bitmap 绑定在 radix-tree 树的叶子上，通过计算叶子在 radix-tree 的位置，以此计算每个 bit 的 ID 号。内核通过这种机制，能够管理和分配系统所需要的 ID， 确保 ID 不重复。以及 ID 的释放和回收，对系统的长久稳定运行提供了基础。

IDA 实践

IDA 内核中最小实践

驱动源码

实践源码 IDA on GitHub

/*
 * IDA.
 *
 * (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 IDA/IDA */
#include <linux/idr.h>

/* Root of IDA */
static DEFINE_IDA(BiscuitOS_ida);

static __init int ida_demo_init(void)
{
	int id;

	/* Allocate an unused ID */
	id = ida_alloc(&BiscuitOS_ida, GFP_KERNEL);

	printk("IDA-ID: %#x\n", id);

	/* Release an allocated ID */
	ida_free(&BiscuitOS_ida, id);

	return 0;
}
device_initcall(ida_demo_init);

驱动安装

驱动的安装很简单，首先将驱动放到 drivers/BiscuitOS/ 目录下，命名为 ida.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_IDA
+       bool "IDA"
+
+if BISCUITOS_IDA
+
+config DEBUG_BISCUITOS_IDA
+       bool "IDA mini"
+
+endif # BISCUITOS_IDA
+
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_IDA)     += ida.o
--

驱动配置

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

Device Driver--->
    [*]BiscuitOS Driver--->
        [*]IDA
            [*]IDA 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-ID: 0x0
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

IDA 在应用程序中最小实践

实践源码

实践源码 IDA on GitHub

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

wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDA/Basic/Makefile
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDA/Basic/ida_run.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDA/Basic/ida.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDA/Basic/ida.h
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDA/Basic/radix.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/IDA/Basic/radix.h

实践源码具体内容如下：

/*
 * IDA Manual.
 *
 * (C) 2019.06.03 <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>

/* IDA/IDA */
#include <ida.h>

/* Root of IDA */
static DEFINE_IDA(BiscuitOS_ida);

int main()
{
	unsigned long i;
	int id;

	for (i = 0; i < 1000; i++) {
		/* Allocate an unused ID */
		id = ida_alloc(&BiscuitOS_ida, GFP_KERNEL);
		printf("IDA-ID: %d\n", id);
	}


	/* Release an allocated ID */
	ida_free(&BiscuitOS_ida, id);

	return 0;
}

源码编译

使用如下命令进行编译：

make clean
make

源码运行

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

IDA/Basic$ ./ida
IDA-ID: 0
IDA-ID: 1
IDA-ID: 2
IDA-ID: 3
.....
IDA-ID: 1007
IDA-ID: 1008
IDA-ID: 1009
IDA-ID: 1010

DTS

IDA 在内核中的应用

IDA 初始化操作

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

ID 分配操作

ID 分配操作就是从内核中分配一个 ID 操作。IDA 机制中，通过分配一个 ID 之后，并在 IDA 对应的 radix-tree 中找到 ID 对应的 slot，然后将 bitmap 或者 ida_bitmap 存储 在 slot 里。bit 在 bitmap 的位置以及 bitmap 在 radix-tree 的位置决定了新分配 ID 的值。内核也提供了相应的函数用于 ID 的分配操作，开发者可以参考下面的文章进行实践：

ID 回收操作

ID 回收操作是 IDA 将 ID 从 radix-tree 中指定的 bitmap 中清除，如果达到释放 bitmap 的条件，IDA 也会释放 bitmap 对应的 slot 节点。开发者可以参考下面的文章进行实践：

IDA 其他操作

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

IDA 内核接口函数列表

附录

BiscuitOS Home

BiscuitOS Driver

BiscuitOS Kernel Build

Linux Kernel

Bootlin: Elixir Cross Referencer

搭建高效的 Linux 开发环境

赞赏一下吧 🙂

MMU