分享

浅析linux内核中的idr机制

 WUCANADA 2017-10-26 发布于美国

             标签: AMPstruct内核LinuxLinux Kernel
2013-08-20 12:26 4901人阅读 评论(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结构体,并初始化:
    void idr_init(struct idr *idp);
其中idr定义如下:
  1. struct idr {  
  2.         struct idr_layer *top;  
  3.         struct idr_layer *id_free;  
  4.         int               layers;  
  5.         int               id_free_cnt;  
  6.         spinlock_t        lock;  
  7. };  

/* 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
在实际中,上述函数常常采用如下方式使用:
  1. again:  
  2.   if (idr_pre_get(&my_idr, GFP_KERNEL) == 0) {  
  3.     /* No memory, give up entirely */  
  4.   }  
  5.   spin_lock(&my_lock);  
  6.   result = idr_get_new(&my_idr, &target, &id);  
  7.   if (result == -EAGAIN) {  
  8.     sigh();  
  9.     spin_unlock(&my_lock);  
  10.     goto again;  
  11.   }  

(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机制的实际应用:
  1. <linux-2.6.23/drivers/i2c/i2c-core.c>  
  2. ...  
  3. <linux/idr.h>   /* idr头文件 */  
  4. ...  
  5. static DEFINE_IDR(i2c_adapter_idr); /* 声明idr */  
  6. ...  
  7. /*  
  8.   采用动态总线号声明并注册一个i2c适配器(adapter),可睡眠 
  9.   针对总线号可动态指定的设备,如基于USB的i2c设备或pci卡 
  10.  */  
  11. int i2c_add_adapter(struct i2c_adapter *adapter)  
  12. {  
  13.         int     id, res = 0;  
  14. retry:  
  15.         if (idr_pre_get(&i2c_adapter_idr, GFP_KERNEL) == 0)  
  16.                 return -ENOMEM;  
  17.         mutex_lock(&core_lists);  
  18.         /* __i2c_first_dynamic_bus_num是当前系统允许的动态总线号的最大值 */  
  19.         res = idr_get_new_above(&i2c_adapter_idr, adapter,                 __i2c_first_dynamic_bus_num, &id);  
  20.         mutex_unlock(&core_lists);  
  21.         if (res < 0) {  
  22.                 if (res == -EAGAIN)  
  23.                         goto retry;  
  24.                 return res;  
  25.         }  
  26.         adapter->nr = id;  
  27.         return i2c_register_adapter(adapter);  
  28. }  
  29. EXPORT_SYMBOL(i2c_add_adapter);  
  30.   
  31. /*  
  32.   采用静态总线号声明并注册一个i2c适配器(adapter) 
  33.  */  
  34. int i2c_add_numbered_adapter(struct i2c_adapter *adap)  
  35. {  
  36.         int     id;  
  37.         int     status;  
  38.         if (adap->nr & ~MAX_ID_MASK)  
  39.                 return -EINVAL;  
  40. retry:  
  41.         if (idr_pre_get(&i2c_adapter_idr, GFP_KERNEL) == 0)  
  42.                 return -ENOMEM;  
  43.         mutex_lock(&core_lists);  
  44.         /* "above" here means "above or equal to", sigh; 
  45.          * we need the "equal to" result to force the result 
  46.          */  
  47.         status = idr_get_new_above(&i2c_adapter_idr, adap, adap->nr, &id);  
  48.         if (status == 0 && id != adap->nr) {  
  49.                 status = -EBUSY;  
  50.                 idr_remove(&i2c_adapter_idr, id);  
  51.         }  
  52.         mutex_unlock(&core_lists);  
  53.         if (status == -EAGAIN)  
  54.                 goto retry;  
  55.         if (status == 0)  
  56.                 status = i2c_register_adapter(adap);  
  57.         return status;  
  58. }  
  59. EXPORT_SYMBOL_GPL(i2c_add_numbered_adapter);  
  60.   
  61. /* 注销一个i2c适配器 */  
  62. int i2c_del_adapter(struct i2c_adapter *adap)  
  63. {  
  64.   ...  
  65.   /* free bus id */  
  66.   idr_remove(&i2c_adapter_idr, adap->nr);  
  67.   ...  
  68.   return res;  
  69. }  
  70. EXPORT_SYMBOL(i2c_del_adapter);  
  71.   
  72. /* 通过ID号获得i2c_adapter设备结构体 */  
  73. struct i2c_adapter* i2c_get_adapter(int id)  
  74. {  
  75.         struct i2c_adapter *adapter;  
  76.         mutex_lock(&core_lists);  
  77.         adapter = (struct i2c_adapter *)idr_find(&i2c_adapter_idr, id);  
  78.         if (adapter && !try_module_get(adapter->owner))  
  79.                 adapter = NULL;  
  80.         mutex_unlock(&core_lists);  
  81.         return adapter;  
  82. }  
  83. EXPORT_SYMBOL(i2c_get_adapter);  

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多