首页 > 代码库 > 内核中bitmap的使用

内核中bitmap的使用

  在编写应用层代码中使用位图,发现内核中已经有现成的实现便使用之。对位图的使用主要是几个

关键API。

 

第一:bitmap_zero函数用于初始化位图

源码如下:

/* *@dst: 位图的起始地址 *@nbits: 位图的个数 */static inline void bitmap_zero(unsigned long *dst, int nbits){    int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);        memset(dst, 0, len);}

 

第二:bitmap_set函数用于设置特定的位

 1 /* 2  * @map: 位图的内存空间的首地址 3  * @start:需要设置的起始位 4  * @nr : 需要设置的位的数目   5 */ 6 void bitmap_set(unsigned long *map, int start, int nr) 7 { 8     unsigned long *p = map + BIT_WORD(start);   //以unsigned long 为单位的情况,设置起始位置 9     const int size = start + nr;  //需要设置的末位,不包括此位    10     /*11      * @bits_to_set 在一个需要设置的unsigned long中,可能需要设置的位12      * [0_____start_________BITS_PER_LONG)13      *                [0____________________bits_to_set) 14      */15     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);    16     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 17    18     while (nr - bits_to_set >= 0) {19         *p |= mask_to_set;20         nr -= bits_to_set;    21         bits_to_set = BITS_PER_LONG; //经过上一步的操作后,需要设置的位都是BITS_PER_LONG的倍数 22         mask_to_set = ~0UL;23         p++;24     }25     if (nr) {  //nr 必须大于1,此函数才有效果26         mask_to_set &= BITMAP_LAST_WORD_MASK(size);27         *p |= mask_to_set;  //产生最终的效果28     }29 }

 

与bit_set函数相对应的是bit_clear函数用于清除位,其实现原理和bit_set函数类似。

 

第三:find_first_zero_bit函数用于找到第一个清空位

/** Find the first cleared bit in a memory region.* @addr: 位图的起始位置* @size: 位图的大小*/unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size){    const unsigned long *p = addr;    unsigned long result = 0;    unsigned long tmp;    while (size & ~(BITS_PER_LONG-1)) {        //位图的大小超过一个 BIT_PER_LONG的情况下        if (~(tmp = *(p++)))            goto found;        result += BITS_PER_LONG;        size -= BITS_PER_LONG;    }    if (!size)   //此情况成立的时候,也是没有找到。且size应该是 BIT_PER_LONG的整数倍。        return result;            tmp = (*p) | (~0UL << size);          if (tmp == ~0UL)    /* Are any bits zero? */        return result + size;   /* Nope. */      //如果没有找到就会返回 sizefound:    return result + ffz(tmp);}  

 

于此函数对应的是函数find_first_bit寻找第一个设置位。

 

第四:find_next_zero_bit 和 find_next_bit 函数可以在第一次找到后,再次寻找清空位或设置位。

 

具体使用情况可以参考:

内核模块

应用层程序

 

备注:

位图除了应用于内存管理,还可以应用到对共享资源的管理,LDD3的P128就有提到。

 

内核中bitmap的使用