原文：http://blogold.chinaunix.net/u3/93926/showart_1874142.html

尚观科技原创文章
浅析linux内核中的idr机制  
 
尚观讲师原创文章
idr在linux内核中指的就是整数ID管理机制，从本质上来说，这就是一种将整数ID号和特定指针关联在一起的机制。这个机制最早是在2003年2月加入内核的，当时是作为POSIX定时器的一个补丁。现在，在内核的很多地方都可以找到idr的身影。
idr机制适用在那些需要把某个整数和特定指针关联在一起的地方。举个例子，在I2C总线中，每个设备都有自己的地址，要想在总线上找到特定的设备，就必须要先发送该设备的地址。如果我们的PC是一个I2C总线上的主节点，那么要访问总线上的其他设备，首先要知道他们的ID号，同时要在pc的驱动程序中建立一个用于描述该设备的结构体。
此时，问题来了，我们怎么才能将这个设备的ID号和他的设备结构体联系起来呢？最简单的方法当然是通过数组进行索引，但如果ID号的范围很大(比如32位的ID号)，则用数组索引显然不可能；第二种方法是用链表，但如果网络中实际存在的设备较多，则链表的查询效率会很低。遇到这种清况，我们就可以采用idr机制，该机制内部采用radix树实现，可以很方便地将整数和指针关联起来，并且具有很高的搜索效率。
(1)获得idr
要在代码中使用idr，首先要包括<linux/idr.h>。接下来，我们要在代码中分配idr结构体，并初始化：
    void idr_init(struct idr *idp);
其中idr定义如下：
struct idr {
        struct idr_layer *top;
        struct idr_layer *id_free;
        int               layers;
        int               id_free_cnt;
        spinlock_t        lock;
};
/* idr是idr机制的核心结构体 */
(2)为idr分配内存
int idr_pre_get(struct idr *idp, unsigned int gfp_mask);
每次通过idr获得ID号之前，需要先分配内存。
返回0表示错误，非零值代表正常
(3)分配ID号并将ID号和指针关联
int idr_get_new(struct idr *idp, void *ptr, int *id);
int idr_get_new_above(struct idr *idp, void *ptr, int start_id, int *id);
idp: 之前通过idr_init初始化的idr指针
id:  由内核自动分配的ID号
ptr: 和ID号相关联的指针
start_id: 起始ID号。内核在分配ID号时，会从start_id开始。如果为I2C节点分配ID号，可以将设备地址作为start_id
函数调用正常返回0，如果没有ID可以分配，则返回-ENOSPC
在实际中，上述函数常常采用如下方式使用：
again:
  if (idr_pre_get(&my_idr, GFP_KERNEL) == 0) {
    /* No memory, give up entirely */
  }
  spin_lock(&my_lock);
  result = idr_get_new(&my_idr, &target, &id);
  if (result == -EAGAIN) {
    sigh();
    spin_unlock(&my_lock);
    goto again;
  }
(4)通过ID号搜索对应的指针
void *idr_find(struct idr *idp, int id);
返回值是和给定id相关联的指针，如果没有，则返回NULL
(5)删除ID
要删除一个ID，使用：
void idr_remove(struct idr *idp, int id);
通过上面这些方法，内核代码可以为子设备，inode生成对应的ID号。这些函数都定义在<linux-2.6.xx/lib/idr.c>中

下面，我们通过分析I2C协议的核心代码，来看一看idr机制的实际应用：
<linux-2.6.23/drivers/i2c/i2c-core.c>
...
<linux/idr.h>   /* idr头文件 */
...
static DEFINE_IDR(i2c_adapter_idr); /* 声明idr */
...
/*
  采用动态总线号声明并注册一个i2c适配器(adapter)，可睡眠
  针对总线号可动态指定的设备，如基于USB的i2c设备或pci卡
 */
int i2c_add_adapter(struct i2c_adapter *adapter)
{
        int     id, res = 0;
retry:
        if (idr_pre_get(&i2c_adapter_idr, GFP_KERNEL) == 0)
                return -ENOMEM;
        mutex_lock(&core_lists);
        /* __i2c_first_dynamic_bus_num是当前系统允许的动态总线号的最大值 */
        res = idr_get_new_above(&i2c_adapter_idr, adapter,                 __i2c_first_dynamic_bus_num, &id);
        mutex_unlock(&core_lists);
        if (res < 0) {
                if (res == -EAGAIN)
                        goto retry;
                return res;
        }
        adapter->nr = id;
        return i2c_register_adapter(adapter);
}
EXPORT_SYMBOL(i2c_add_adapter);

/*
  采用静态总线号声明并注册一个i2c适配器(adapter)
 */
int i2c_add_numbered_adapter(struct i2c_adapter *adap)
{
        int     id;
        int     status;
        if (adap->nr & ~MAX_ID_MASK)
                return -EINVAL;
retry:
        if (idr_pre_get(&i2c_adapter_idr, GFP_KERNEL) == 0)
                return -ENOMEM;
        mutex_lock(&core_lists);
        /* "above" here means "above or equal to", sigh;
         * we need the "equal to" result to force the result
         */
        status = idr_get_new_above(&i2c_adapter_idr, adap, adap->nr, &id);
        if (status == 0 && id != adap->nr) {
                status = -EBUSY;
                idr_remove(&i2c_adapter_idr, id);
        }
        mutex_unlock(&core_lists);
        if (status == -EAGAIN)
                goto retry;
        if (status == 0)
                status = i2c_register_adapter(adap);
        return status;
}
EXPORT_SYMBOL_GPL(i2c_add_numbered_adapter);

/* 注销一个i2c适配器 */
int i2c_del_adapter(struct i2c_adapter *adap)
{
  ...
  /* free bus id */
  idr_remove(&i2c_adapter_idr, adap->nr);
  ...
  return res;
}
EXPORT_SYMBOL(i2c_del_adapter);

/* 通过ID号获得i2c_adapter设备结构体 */
struct i2c_adapter* i2c_get_adapter(int id)
{
        struct i2c_adapter *adapter;
        mutex_lock(&core_lists);
        adapter = (struct i2c_adapter *)idr_find(&i2c_adapter_idr, id);
        if (adapter && !try_module_get(adapter->owner))
                adapter = NULL;
        mutex_unlock(&core_lists);
        return adapter;
}
EXPORT_SYMBOL(i2c_get_adapter);

GitHub 加速计划 / li / linux-dash
6
1
下载
A beautiful web dashboard for Linux
最近提交(Master分支：3 个月前 )
186a802e added ecosystem file for PM2 4 年前
5def40a3 Add host customization support for the NodeJS version 4 年前
Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

avatar GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

avatar GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m

avatar GitCode 开源社区