浅谈linux内核中的idr机制

素颜马尾好姑娘i 2022-06-13 07:47 353阅读 0赞

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结构体，并初始化：  
voididr\_init(struct idr \*idp);  
其中idr定义如下：  
structidr \{  
struct idr\_layer \*top;  
struct idr\_layer\*id\_free;  
int              layers;  
int              id\_free\_cnt;  
spinlock\_t       lock;  
\};  
/\* idr是idr机制的核心结构体\*/

(2)为idr分配内存  
intidr\_pre\_get(struct idr \*idp, unsigned intgfp\_mask);  
每次通过idr获得ID号之前，需要先分配内存。  
返回0表示错误，非零值代表正常

(3)分配ID号并将ID号和指针关联  
intidr\_get\_new(struct idr \*idp, void \*ptr, int \*id);  
intidr\_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, giveup 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，使用：  
voididr\_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头文件\*/  
...  
staticDEFINE\_IDR(i2c\_adapter\_idr); /\* 声明idr\*/  
...

/\*   
采用动态总线号声明并注册一个i2c适配器(adapter)，可睡眠  
针对总线号可动态指定的设备，如基于USB的i2c设备或pci卡  
\*/  
inti2c\_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;  
returni2c\_register\_adapter(adapter);  
\}  
EXPORT\_SYMBOL(i2c\_add\_adapter);

/\*   
采用静态总线号声明并注册一个i2c适配器(adapter)  
\*/  
inti2c\_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);  
returnstatus;  
\}  
EXPORT\_SYMBOL\_GPL(i2c\_add\_numbered\_adapter);

/\*注销一个i2c适配器\*/  
inti2c\_del\_adapter(struct i2c\_adapter \*adap)  
\{  
...  
/\* free busid \*/  
idr\_remove(&i2c\_adapter\_idr, adap->nr);  
...  
returnres;  
\}  
EXPORT\_SYMBOL(i2c\_del\_adapter);

/\*通过ID号获得i2c\_adapter设备结构体\*/  
structi2c\_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);

returnadapter;

EXPORT\_SYMBOL(i2c\_get\_adapter);

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定义如下：  
structidr \{  
        struct idr\_layer\*top;  
        struct idr\_layer\*id\_free;  
        int              layers;  
       int              id\_free\_cnt;  
        spinlock\_t       lock;  
\};  
/\* idr是idr机制的核心结构体\*/  
(2)为idr分配内存  
  
intidr\_pre\_get(struct idr \*idp, unsigned intgfp\_mask);  
每次通过idr获得ID号之前，需要先分配内存。  
返回0表示错误，非零值代表正常  
(3)分配ID号并将ID号和指针关联  
intidr\_get\_new(struct idr \*idp, void \*ptr, int \*id);  
intidr\_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) \{  
    /\* Nomemory, give up entirely \*/  
  \}  
  spin\_lock(&my\_lock);  
result = idr\_get\_new(&my\_idr, &target, &id);  
if(result == -EAGAIN) \{  
    sigh();  
   spin\_unlock(&my\_lock);  
    gotoagain;  
  \}  
(4)通过ID号搜索对应的指针  
void\*idr\_find(struct idr \*idp, int id);  
返回值是和给定id相关联的指针，如果没有，则返回NULL