淺析linux內核中的idr機制，淺析linux內核idr

淺析linux內核中的idr機制，淺析linux內核idr

idr在linux內核中指的就是整數ID管理機制，從本質上來說，這就是一種將整數ID號和特定指針關聯在一起的機制。這個機制最早是在2003年2月加入內核的，當時是作為POSIX定時器的一個補丁。現在，在內核的很多地方都可以找到idr的身影。 idr機制適用在那些需要把某個整數和特定指針關聯在一起的地方。舉個例子，在I2C總線中，每個設備都有自己的地址，要想在總線上找到特定的設備，就必須要先發送該設備的地址。如果我們的PC是一個I2C總線上的主節點，那麼要訪問總線上的其他設備，首先要知道他們的ID號，同時要在pc的驅動程序中建立一個用於描述該設備的結構體。 此時，問題來了，我們怎麼才能將這個設備的ID號和他的設備結構體聯系起來呢？最簡單的方法當然是通過數組進行索引，但如果ID號的范圍很大(比如32位的ID號)，則用數組索引顯然不可能；第二種方法是用鏈表，但如果網絡中實際存在的設備較多，則鏈表的查詢效率會很低。遇到這種清況，我們就可以采用idr機制，該機制內部采用radix樹實現，可以很方便地將整數和指針關聯起來，並且具有很高的搜索效率。http://hovertree.com/menu/linux/ (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機制的核心結構體  何問起 hovertree.com */

(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;
  }/* 何問起 hovertree.com */

(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); 推薦：http://www.cnblogs.com/roucheng/p/3470287.html

http://xxxxxx/Linuxjc/1136971.html TechArticle