目录

1. Linux内核映射idr常用操作

2. IDR简介

3. Linux内核映射idr简介

4. 编写一个测试映射idr的内核模块

1. Linux内核映射idr常用操作

2. 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 中数字部分）等。

3. Linux内核映射idr简介

Linux内核提供了一套完整的 IDR 实现机制，其基于Radix-tree。

来自头文件linux/idr.h

3.1 内核中的IDR

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

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

3.2 IDR架构原理

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

3.3 初始化操作

DEFINE_IDR宏定义并初始化了一个struct idr类型变量。

#define DEFINE_IDR(name) struct idr name = IDR_INIT(name)

3.4 预加载操作

idr_preload()函数用于预加载 IDR。

idr_preload_end()用于和idr_preload()成对使用。用于结束 IDR 内存池。

void idr_preload(gfp_t gfp_mask)
{
    if (__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE))
        preempt_disable();
}

static inline void idr_preload_end(void)
{
    preempt_enable();
}

3.5 插入操作

idr_alloc_cyclic()函数用于周期性的分配 ID，并将 ID 与指针进行绑定。idr为struct idr类型指针；ptr指向与 ID 进行绑定的指针；start参数限定了 ID 的起始值；end限定了 ID 的终止值；gfp 指向了分配时需要的标识。

int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
{
    u32 id = idr->idr_next;
    int err, max = end > 0 ? end - 1 : INT_MAX;

    if ((int)id < start)
            id = start;

    err = idr_alloc_u32(idr, ptr, &id, max, gfp);
    if ((err == -ENOSPC) && (id > start)) {
            id = start;
            err = idr_alloc_u32(idr, ptr, &id, max, gfp);
    }
    if (err)
            return err;

    idr->idr_next = id + 1;
    return id;
}

3.6 查询操作

idr_find()函数用于通过 ID 查找与之绑定的指针。函数直接通过radix_tree_lookup()函数在radix-tree 中查找指定的节点，如果找到则返回 ID 绑定的指针；反之返回NULL。

void *idr_find(const struct idr *idr, unsigned long id)
{
    return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
}

3.7 修改操作

idr_replace()用于替换 ID 绑定的指针。函数首先判断被替换的内容是不是内部节点，如果是内部节点，那么返回 EINVAL错误码。

void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
{
    struct radix_tree_node *node;
    void __rcu **slot = NULL;
    void *entry;

    if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
            return ERR_PTR(-EINVAL);
    id -= idr->idr_base;

    entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
    if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
            return ERR_PTR(-ENOENT);

    __radix_tree_replace(&idr->idr_rt, node, slot, ptr, NULL);

    return entry;
}

3.8 删除操作

idr_remove()函数用于从 IDR 中移除一个 ID，并将与之绑定的指针接触绑定。参数id代表需要移除的 ID。函数调用 radix_tree_delete_item()函数将id对应的节点从radix-tree中移除。

void *idr_remove(struct idr *idr, unsigned long id)
{
    return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
}

3.9 遍历操作

idr_for_each_entry用于遍历 IDR 中所有与 ID 绑定的指针。idr为struct idr类型指针，entry 指向一个绑定指针的数据结构指针；id用于存储与指针绑定的 ID。从id为0开始遍历，每次遍历通过idr_get_next()获得下一个节点。遍历直到id对应的指针不存在才停止。

#define idr_for_each_entry(idr, entry, id)                      \
        for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id)

3.10 判空操作

idr_is_empty()函数用于判断 IDR 是否为空。如果为空，则返回true，反之返回false。

static inline bool idr_is_empty(const struct idr *idr)
{
    return radix_tree_empty(&idr->idr_rt) &&
        radix_tree_tagged(&idr->idr_rt, IDR_FREE);
}

4. 编写一个测试映射idr的内核模块

本文的实验环境为ubuntu20.04 64位虚拟机

4.1 编写idr.c文件

#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/idr.h>

MODULE_LICENSE("GPL");

struct node
{
    char ch;
};


static int __init testidr_init(void)
{
    DEFINE_IDR(mp);
    int idr_array[20];
    char s[] = "toosmallword";
    struct node t[20], *tmp;
    int i, id;

    idr_preload(GFP_KERNEL);

    for (i = 0; s[i]; ++i)
    {
        t[i].ch = s[i];
        idr_array[i] = idr_alloc_cyclic(&mp, &t[i], 0, INT_MAX, GFP_ATOMIC);
    }

    idr_for_each_entry(&mp, tmp, id)
    {
        printk("%c's ID is %d\n", tmp->ch, id);
    }

    idr_replace(&mp, &t[1], idr_array[0]);
    idr_remove(&mp, idr_array[7]);

    for (i = 0; s[i]; ++i)
    {
        tmp = idr_find(&mp, idr_array[i]);
        if (tmp) printk("%c's ID is %d\n", tmp->ch, idr_array[i]);
        else printk("%d is not used\n", idr_array[i]);
    }


    idr_for_each_entry(&mp, tmp, id)
    {
        printk("%c's ID is %d\n", tmp->ch, id);
    }


    idr_preload_end();

    return 0;
}


static void __exit testidr_exit(void)
{
    printk("exit\n");
}

module_init(testidr_init);
module_exit(testidr_exit);

4.2 编写Makefile文件

# obj-m:=这个赋值语句的含义是说明要使用目标文件idr.o建立一个模块，最后生成的模块名为idr.ko
# .o文件是经过编译和汇编，而没有经过链接的中间文件。
# .ko文件是kernel object文件，也就是内核模块加载文件。

obj-m:=idr.o  

# 模块所在当前路径

CURRENT_PATH:=$(shell pwd) 

# Linux内核源代码的当前版本

LINUX_KERNEL:=$(shell uname -r) 

# Linux内核源代码的绝对路径

LINUX_KERNEL_PATH:=/usr/src/linux-headers-$(LINUX_KERNEL) 

# Makefile文件中，若某一行是命令，则它必须以一个Tab键开头。

all:
    make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules # 编译模块

clean:
    make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) clean # 清理模块

test:
    sudo dmesg -C         # 清除内核环形缓冲区
    sudo insmod idr.ko   # 插入模块
    sudo rmmod idr       # 删除模块
    dmesg                 # 查看该模块的输出