linux学习20,内核中的映射IDR机制

前面几节较为详细的讨论了 linux 内核中的“链表”和“队列”数据类型,本节再来说说中的映射(idr)机制。

先来说说映射适合用于解决什么问题

linux 系统中的许多资源都用整数 ID 标识,例如进程 PID,文件描述符 ID 等等。使用一个整数标识资源的确非常简洁,但是一个整数能够记录表达的信息太有限了,所以整数 ID 的背后常常都有一个结构体与之对应,例如每个进程 ID 都对应着一个巨大的 task_struct 结构体记录着进程的资源。

那么,整数 ID 该如何与结构体对应起来呢?这个问题可以简化为如何将两个整数对应起来。因为只要能根据整数 ID 找到结构体的地址就可以了,而结构体的地址也是一个整数。

要解决这个问题,首先就需要选择一个数据结构。如果使用数组进行索引,一旦 ID 很大,那数组也必须得很大,这样会占据大量的内存空间,所以数组显然是不合适的。而如果使用链表进行索引,则又会有查找效率问题,毕竟链表只能线性遍历查找。

映射就非常适合解决这样的问题。

什么是映射?

映射其实就是将要保存的数值(例如结构体指针)与另一个数关联起来,所谓的“另一个数”常常被称作“键值”。映射一般至少要支持三个模块:
* add(key, value),增加映射
* remove(key),删除映射
* value = lookup(key),根据键查找数值

这么看来,“哈希表”就是一种映射,不过也不是所有映射都需要通过“哈希表”才能实现,映射也可以通过自平衡二叉树(之后的文章会介绍二叉树)实现。

虽然“键值映射”是一个非常宽泛的概念,但是大多情况下都默认是借助自平衡二叉树实现的。

linux 内核是怎样设计和实现“映射”的?

linux 内核实现映射的目标很简单:就是将指针与一个唯一标识数(UID)对应起来。为此,linux 内核不仅实现了映射的三个标准模块外,还提供了自动产生 UID 的模块。这么看来,内核实现的映射更像是一种“定制化”的,而不是通用的映射。

先来看看 linux 内核中用于实现映射的数据结构,请看如下C语言代码:

-    50 struct idr_layer {    
|    51     unsigned long        bitmap; /* A zero bit means "space here" */
|    52     struct idr_layer    *ary[1<<IDR_BITS];
|    53     int          count;  /* When zero, we can release it */
|    54 };
     55 
-    56 struct idr {          
|    57     struct idr_layer *top;
|    58     struct idr_layer *id_free;
|    59     int       layers; 
|    60     int       id_free_cnt;
|    61     spinlock_t    lock;
|    62 }; 


idr_layer 结构很像一个链表,IDR_BITS 和平台相关,在 BITS_PER_LONG == 32 的平台上,IDR_BITS 等于 5,在 BITS_PER_LONG == 64 的平台上,IDR_BITS 等于 6。

也就是说,1<<IDR_BITS 等于 32 或者 64。以下以 IDR_BITS 等于 5 为例行文。

这么看来,idr_layer 结构体可用下图表示:

初始化一个 idr(映射)

初始化一个 idr 非常简单,调用 idr_init() 函数即可,它的C语言代码如下,请看:

void idr_init(struct idr *idp)
{       
     memset(idp, 0, sizeof(struct idr));
     spin_lock_init(&idp->lock);
} 

idr_init() 函数只是将 idr 清零,并初始化锁而已,所以在调用 idr_init() 函数之前,需要静态定义或者动态分配一个 idr,例如:

struct idr myidr;
idr_init(myidr);

分配一个新的 UID

建立好一个新的 idr 后,就可以分配新的 UID 了。这一步 linux 内核是通过 idr_pre_get() 和 idr_get_new() 两个函数完成的。idr_pre_get() 函数的C语言代码如下:

    105 int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
-   106 {               
|-  107     while (idp->id_free_cnt < IDR_FREE_MAX) {
||  108         struct idr_layer *new;
||  109         new = kmem_cache_alloc(idr_layer_cache, gfp_mask);
||  110         if (new == NULL)
||  111             return (0);
||  112         free_layer(idp, new);
||  113     }
|   114     return 1;
|   115 }


idr_pre_get() 函数的核心就是 free_layer() 函数。这里可以看出,即使是 linux 内核的源代码,命名也有可能是不太合适的。 free_layer() 函数并不是如字面意思“释放 idr”,而是将新分配的 new 连接到 idr 的 id_free 成员上,请看:

     61 static void free_layer(struct idr *idp, struct idr_layer *p)
-    62 {       
|    63     unsigned long flags;
|    64         
|    65     /*      
|    66      * Depends on the return element being zeroed.
|    67      */
|    68     spin_lock_irqsave(&idp->lock, flags);
|    69     __free_layer(idp, p);
|    70     spin_unlock_irqrestore(&idp->lock, flags);
|    71 } 


idr_pre_get() 函数执行完毕后,得到的数据结构如下图:

idr_pre_get() 就是实际执行获取 UID 的函数了,它的C语言代码如下,请看:

    306 int idr_get_new(struct idr *idp, void *ptr, int *id)
-   307 {       
|   308     int rv;
|   309         
|   310     rv = idr_get_new_above_int(idp, ptr, 0);
|   311     /*
|   312      * This is a cheap hack until the IDR code can be fixed to
|   313      * return proper error values.
|   314      */
|-  315     if (rv < 0) {
||  316         if (rv == -1)
||  317             return -EAGAIN;
||  318         else /* Will be -3 */
||  319             return -ENOSPC;
||  320     }
|   321     *id = rv;
|   322     return 0;
|   323 }

核心是 idr_get_new_above_int() 函数,继续跟踪:

    236 static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
-   237 {   
|   238     struct idr_layer *pa[MAX_LEVEL];
|   239     int id; 
|   240         
|   241     id = idr_get_empty_slot(idp, starting_id, pa);
|-  242     if (id >= 0) {
||  243         /*
||  244          * Successfully found an empty slot.  Install the user
||  245          * pointer and mark the slot full.
||  246          */
||  247         pa[0]->ary[id & IDR_MASK] = (struct idr_layer *)ptr;
||  248         pa[0]->count++;
||  249         idr_mark_full(pa, id);
||  250     }
|   251     
|   252     return id;
|   253 }

发现实际负责申请 UID 的动作由 idr_get_empty_slot() 函数完成,它的C语言代码如下:

到这里就非常清楚了, int idr_get_new(struct idr* idp, void* ptr, int* id) 函数执行成功后,将获得一个新的 UID,它会被映射到 ptr,并通过指针参数 id 返回。

通过 UID 查找指针地址

根据 UID 查找其对应的指针地址就简单许多了,只需调用 idr_find() 函数即可,它的 C语言代码如下:

    464 void *idr_find(struct idr *idp, int id)
-   465 {       
|   466     int n;
|   467     struct idr_layer *p; 
|   468             
|   469     n = idp->layers * IDR_BITS;
|   470     p = idp->top;
|   471     
|   472     /* Mask off upper bits we don't use for the search. */
|   473     id &= MAX_ID_MASK; 
|   474     
|   475     if (id >= (1 << n))
|   476         return NULL;
|   477 
|-  478     while (n > 0 && p) {
||  479         n -= IDR_BITS;
||  480         p = p->ary[(id >> n) & IDR_MASK];
||  481     }
|   482     return((void *)p);
|   483 }


可以看出 idr_find() 函数执行成功后,会返回 id 关联的指针地址,如果执行失败,则会返回 NULL。从这里也可以看出,应尽量避免将空指针 NULL 与 UID 映射,否则调用 idr_find() 函数时将无法区分是成功还是失败。

到这里,我们就对 linux 内核中的映射有所了解了,其他相关代码的分析(例如删除一个UID映射 idr_remove()函数)也是类似的,这里就不再赘述了。(实际上,linux 内核关于 idr 的设计与实现还是有一定的复杂度的,这里仅仅只是粗略的先留个大体印象,更详细的讨论以后再介绍了。)

阅读更多:   Linux笔记
仅有 1 条评论
  1. 您的博客真好

添加新评论

icon_redface.gificon_idea.gificon_cool.gif2016kuk.gificon_mrgreen.gif2016shuai.gif2016tp.gif2016db.gif2016ch.gificon_razz.gif2016zj.gificon_sad.gificon_cry.gif2016zhh.gificon_question.gif2016jk.gif2016bs.gificon_lol.gif2016qiao.gificon_surprised.gif2016fendou.gif2016ll.gif