Linux 內核數(shù)據(jù)結構：位圖（Bitmap）

位圖和位運算

除了各種鏈式和樹形數(shù)據(jù)結構，Linux內核還提供了位圖接口。位圖在Linux內核中大量使用。下面的源代碼文件包含這些結構的通用接口：

lib/bitmap.c

include/linux/bitmap.h

除了這兩個文件，還有一個特定的架構頭文件，對特定架構的位運算進行優(yōu)化。對于x86_64架構，使用下面頭文件：

arch/x86/include/asm/bitops.h

正如我前面提到的，位圖在Linux內核中大量使用。比如，位圖可以用來存儲系統(tǒng)在線/離線處理器，來支持CPU熱插拔；再比如，位圖在Linux內核等初始化過程中存儲已分配的中斷請求。

因此，本文重點分析位圖在Linux內核中的具體實現(xiàn)。

位圖聲明

位圖接口使用前，應當知曉Linux內核是如何聲明位圖的。一種簡單的位圖聲明方式，即unsigned long數(shù)組。比如：

C

unsigned long my_bitmap[8]

1

unsigned long my_bitmap[8]

第二種方式，采用DECLARE_BITMAP宏，此宏位于頭文件include/linux/types.h中：

C

#define DECLARE_BITMAP(name,bits) unsigned long name[BITS_TO_LONGS(bits)]

1

2

#define DECLARE_BITMAP(name,bits)

unsigned long name[BITS_TO_LONGS(bits)]

DECLARE_BITMAP宏有兩個參數(shù)：

name – 位圖名字；

bits – 位圖中比特總數(shù)目

并且擴展元素大小為BITS_TO_LONGS(bits)、類型unsigned long的數(shù)組，而BITS_TO_LONGS宏將位轉換為long類型，或者說計算出bits中包含多少byte元素：

C

#define BITS_PER_BYTE 8#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))

1

2

3

#define BITS_PER_BYTE?????????? 8

#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))

#define BITS_TO_LONGS(nr)?????? DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))

例如：DECLARE_BITMAP(my_bitmap, 64)結果為：

C

>>> (((64) + (64) - 1) / (64))1

1

2

>>> (((64) + (64) - 1) / (64))

1

和：

C

unsigned long my_bitmap[1];

1

unsigned long my_bitmap[1];

位圖聲明后，我們就可以使用它了。

特定架構的位運算

我們已經(jīng)查看了操作位圖接口的兩個源碼文件和一個頭文件。位圖最重要最廣泛的應用接口是特定架構，它位于頭文件arch/x86/include/asm/bitops.h中

首先，我們來看兩個重要的函數(shù)：

set_bit;

clear_bit.

我認為沒有必要介紹這些函數(shù)是做什么的，通過函數(shù)名就可以知曉。我們來看函數(shù)的實現(xiàn)。進入頭文件arch/x86/include/asm/bitops.h，你會注意到每個函數(shù)分兩種類型：原子類型和非原子類型。在深入這些函數(shù)實現(xiàn)前，我們需要先了解一些原子性運算。

一言以蔽之，原子性操作保障，位于同一數(shù)據(jù)上的兩個甚至多個運算，不能并發(fā)執(zhí)行。x86架構提供一組原子性指令，如指令xchg、指令cmpxchg。除了原子性指令，一些非原子性指令可借助指令lock進行原子性運算。目前我們了解這些原子性運算就足夠了，接下來可以開始考慮set_bit和clear_bit函數(shù)。

先從非原子性類型的函數(shù)開始，非原子性set_bit和clear_bit函數(shù)名始于雙下劃線。正如你所了解的，所有的函數(shù)定義在頭文件arch/x86/include/asm/bitops.h中，第一個函數(shù)__set_bit：

C

static inline void __set_bit(long nr, volatile unsigned long *addr){ asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");}

1

2

3

4

static inline void __set_bit(long nr, volatile unsigned long *addr)

{

asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");

}

它擁有兩個參數(shù)：

nr – 位圖中比特數(shù)目

addr – 位圖中某個比特需要設值的地址

注意參數(shù)addr定義為volatile，告訴編譯器此值或許被某個地址改變。而__set_bit容易實現(xiàn)。正如你所見，恰好它包含一行內聯(lián)匯編代碼。本例中，使用指令bts選擇位圖中的某個比特值作為首個操作數(shù)，將已選擇比特值存入寄存器CF標簽中，并設置此比特。

此處可以看到nr的用法，那addr呢？或許你已猜到其中的奧秘就在ADDR中。而ADDR是定義在頭文件中的宏，擴展字符串，在該地址前面加入+m約束：

C

#define ADDR BITOP_ADDR(addr)#define BITOP_ADDR(x) "+m" (*(volatile long *) (x))

1

2

#define ADDR????????????????BITOP_ADDR(addr)

#define BITOP_ADDR(x) "+m" (*(volatile long *) (x))

除了+m，我們可以看到__set_bit函數(shù)中其它約束。讓我們查看這些約束，試著理解其中的含義：

+m – 表示內存操作數(shù)，+表示此操作數(shù)為輸入和輸出操作數(shù)；

I – 表示整數(shù)常數(shù)；

r -表示寄存器操作數(shù)

除了這些約束，還看到關鍵字memory，它會告知編譯器此代碼會更改內存中的值。接下來，我們來看同樣功能，原子類型函數(shù)。它看起來要比非原子類型函數(shù)復雜得多：

C

static __always_inline voidset_bit(long nr, volatile unsigned long *addr){ if (IS_IMMEDIATE(nr)) { asm volatile(LOCK_PREFIX "orb %1,%0" : CONST_MASK_ADDR(nr, addr) : "iq" ((u8)CONST_MASK(nr)) : "memory"); } else { asm volatile(LOCK_PREFIX "bts %1,%0" : BITOP_ADDR(addr) : "Ir" (nr) : "memory"); }}

1

2

3

4

5

6

7

8

9

10

11

12

13

static __always_inline void

set_bit(long nr, volatile unsigned long *addr)

{

if (IS_IMMEDIATE(nr)) {

asm volatile(LOCK_PREFIX "orb %1,%0"

: CONST_MASK_ADDR(nr, addr)

: "iq" ((u8)CONST_MASK(nr))

: "memory");

} else {

asm volatile(LOCK_PREFIX "bts %1,%0"

: BITOP_ADDR(addr) : "Ir" (nr) : "memory");

}

}

注意它與函數(shù)__set_bit含有相同的參數(shù)列表，不同的是函數(shù)被標記有屬性__always_inline。__always_inline是定義在include/linux/compiler-gcc.h中的宏，只是擴展了always_inline屬性：

C

#define __always_inline inline __attribute__((always_inline))

1

#define __always_inline inline __attribute__((always_inline))

這意味著函數(shù)會被內聯(lián)以減少Linux內核鏡像的大小。接著，我們試著去理解函數(shù)set_bit實現(xiàn)。函數(shù)set_bit伊始，便對比特數(shù)目進行檢查。IS_IMMEDIATE是定義在相同頭文件中的宏，用于擴展內置函數(shù)gcc：

C

#define IS_IMMEDIATE(nr) (__builtin_constant_p(nr))

1

#define IS_IMMEDIATE(nr)????????(__builtin_constant_p(nr))

內置函數(shù)__builtin_constant_p返回1的條件是此參數(shù)在編譯期為常數(shù)；否則返回0。無需使用指令bts設置比特值，因為編譯期比特數(shù)目為一常量。僅對已知字節(jié)地址進行按位或運算，并對比特數(shù)目bits進行掩碼，使其高位為1，其它為0. 而比特數(shù)目在編譯期若非常量，函數(shù)__set_bit中運算亦相同。宏CONST_MASK_ADDR：

C

#define CONST_MASK_ADDR(nr, addr) BITOP_ADDR((void *)(addr) + ((nr)>>3))

1

#define CONST_MASK_ADDR(nr, addr)?? BITOP_ADDR((void *)(addr) + ((nr)>>3))

采用偏移量擴展某個地址為包含已知比特的字節(jié)。比如地址0x1000，以及比特數(shù)目0x9。0x9等于一個字節(jié)，加一個比特，地址為addr+1：

C

>>> hex(0x1000 + (0x9 >> 3))'0x1001'

1

2

>>> hex(0x1000 + (0x9 >> 3))

'0x1001'

宏CONST_MASK表示看做字節(jié)的某已知比特數(shù)目，高位為1，其它比特為0：

C

#define CONST_MASK(nr) (1 << ((nr) & 7))

1

#define CONST_MASK(nr)??????????(1 << ((nr) & 7))

C

>>> bin(1 << (0x9 & 7))'0b10

1

2

>>> bin(1 << (0x9 & 7))

'0b10

最后，我們使用按位或運算。假設address為0x4097，需要設置ox9比特：

C

>>> bin(0x4097)'0b100000010010111'>>> bin((0x4097 >> 0x9) | (1 << (0x9 & 7)))'0b100010'

1

2

3

4

>>> bin(0x4097)

'0b100000010010111'

>>> bin((0x4097 >> 0x9) | (1 << (0x9 & 7)))

'0b100010'

第九個比特將被設置

注意所有的操作均標記有LOCK_PREFIX，即擴展為指令lock，確保運算以原子方式執(zhí)行。

如我們所知，除了set_bit和__set_bit運算，Linux內核還提供了兩個逆向函數(shù)以原子或非原子方式清理比特，clear_bit和__clear_bit。這個兩個函數(shù)均定義在相同的頭文件中，并擁有相同的參數(shù)列表。當然不僅是參數(shù)相似，函數(shù)本身和set_bit以及 __set_bit都很相似。我們先來看非原子性函數(shù)__clear_bit

C

static inline void __clear_bit(long nr, volatile unsigned long *addr){ asm volatile("btr %1,%0" : ADDR : "Ir" (nr));}

1

2

3

4

static inline void __clear_bit(long nr, volatile unsigned long *addr)

{

asm volatile("btr %1,%0" : ADDR : "Ir" (nr));

}

正如我們所看到的，它們擁有相同參數(shù)列表，以及相似的內聯(lián)匯編函數(shù)塊。不同的是__clear_bit采用指令btr代替指令bts。從函數(shù)名我們可以看出，函數(shù)用來清除某個地址的某個比特值。指令btr與指令bts類似，選擇某個比特值作為首個操作數(shù)，將其值存入寄存器CF標簽中，并清除位圖中的這個比特值，且將位圖作為指令的第二個操作數(shù)。

__clear_bit的原子類型為clear_bit:

C

static __always_inline voidclear_bit(long nr, volatile unsigned long *addr){ if (IS_IMMEDIATE(nr)) { asm volatile(LOCK_PREFIX "andb %1,%0" : CONST_MASK_ADDR(nr, addr) : "iq" ((u8)~CONST_MASK(nr))); } else { asm volatile(LOCK_PREFIX "btr %1,%0" : BITOP_ADDR(addr) : "Ir" (nr)); }}

1

2

3

4

5

6

7

8

9

10

11

12

13

static __always_inline void

clear_bit(long nr, volatile unsigned long *addr)

{

if (IS_IMMEDIATE(nr)) {

asm volatile(LOCK_PREFIX "andb %1,%0"

: CONST_MASK_ADDR(nr, addr)

: "iq" ((u8)~CONST_MASK(nr)));

} else {

asm volatile(LOCK_PREFIX "btr %1,%0"

: BITOP_ADDR(addr)

: "Ir" (nr));

}

}

正如我們所看到的，它和set_bit相似，僅有兩處不同。第一個不同，使用指令btr進行比特清理，而set_bit使用指令bts比特存儲。第二個不同，使用消除掩碼以及指令and清理某個byte中的bit值，而set_bit使用指令or。

到目前為止，我們可以給任何位圖設值、清除或位掩碼運算。

位圖最常用的運算為Linux內核中位圖的設值以及比特值的清除。除了這些運算外，為位圖添加額外的運算也是有必要的。Linux內核中，另一個廣泛的運算是判定位圖是否已設置比特值?？山柚鷗est_bit宏進行判定，此宏定義在頭文件arch/x86/include/asm/bitops.h中，并依據(jù)比特數(shù)目，選擇調用constant_test_bit 或 variable_test_bit：

C

#define test_bit(nr, addr) (__builtin_constant_p((nr)) ? constant_test_bit((nr), (addr)) : variable_test_bit((nr), (addr)))

1

2

3

4

#define test_bit(nr, addr)??????????

(__builtin_constant_p((nr))????????????????

? constant_test_bit((nr), (addr))??????????

: variable_test_bit((nr), (addr)))

若nr在編譯期為常數(shù)，調用test_bit中函數(shù)constant_test_bit，否則調用函數(shù)variable_test_bit。我們來看這些函數(shù)實現(xiàn)，先從函數(shù)variable_test_bit開始：

C

static inline int variable_test_bit(long nr, volatile const unsigned long *addr){ int oldbit; asm volatile("bt %2,%1nt" "sbb %0,%0" : "=r" (oldbit) : "m" (*(unsigned long *)addr), "Ir" (nr)); return oldbit;}

1

2

3

4

5

6

7

8

9

10

11

static inline int variable_test_bit(long nr, volatile const unsigned long *addr)

{

int oldbit;

asm volatile("bt %2,%1nt"

"sbb %0,%0"

: "=r" (oldbit)

: "m" (*(unsigned long *)addr), "Ir" (nr));

return oldbit;

}

函數(shù)variable_test_bit擁有set_bit等函數(shù)相似的參數(shù)列表。同樣，我們看到內聯(lián)匯編代碼，執(zhí)行指令bt、sbb。指令bt或bit test，從位圖中選擇某個比特值作為首個操作數(shù)，而位圖作為第二個操作數(shù)，并將選定的比特值存入寄存器CF標簽中。而指令sbb則會將首個操作數(shù)從第二個操作數(shù)中移除，并移除CF標簽值。將位圖某個比特值寫入CF標簽寄存器，執(zhí)行指令sbb，計算CF為00000000 ，最后將結果寫入oldbit。

函數(shù)constant_test_bit與set_bit相似：

C

static __always_inline int constant_test_bit(long nr, const volatile unsigned long *addr){ return ((1UL << (nr & (BITS_PER_LONG-1))) & (addr[nr >> _BITOPS_LONG_SHIFT])) != 0;}

1

2

3

4

5

static __always_inline int constant_test_bit(long nr, const volatile unsigned long *addr)

{

return ((1UL << (nr & (BITS_PER_LONG-1))) &

(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;

}

它能夠產(chǎn)生一個字節(jié)，其高位時1，其它比特為0，對這個包含比特數(shù)目的字節(jié)做按位與運算。

接下來比較廣泛的位圖運算是，位圖中的比特值的改變運算。為此，Linux內核提供兩個幫助函數(shù)：

__change_bit;

change_bit.

或許你已能猜到，與set_bit和 __set_bit相似，存在兩個類型，原子類型和非原子類型。我們先來看函數(shù)__change_bit的實現(xiàn)：

C

static inline void __change_bit(long nr, volatile unsigned long *addr){ asm volatile("btc %1,%0" : ADDR : "Ir" (nr));}

1

2

3

4

static inline void __change_bit(long nr, volatile unsigned long *addr)

{

asm volatile("btc %1,%0" : ADDR : "Ir" (nr));

}

很容易，難道不是嗎？__change_bit與__set_bit擁有相似的實現(xiàn)，不同的是，前者采用的指令btc而非bts。指令選擇位圖中的某個比特值，然后將此值放入CF中，然后使用補位運算改變其值。若比特值為1則改變后的值為0，反之亦然：

C

>>> int(not 1)0>>> int(not 0)1

1

2

3

4

>>> int(not 1)

0

>>> int(not 0)

1

函數(shù)__change_bit的原子版本為函數(shù)change_bit：

C

static inline void change_bit(long nr, volatile unsigned long *addr){ if (IS_IMMEDIATE(nr)) { asm volatile(LOCK_PREFIX "xorb %1,%0" : CONST_MASK_ADDR(nr, addr) : "iq" ((u8)CONST_MASK(nr))); } else { asm volatile(LOCK_PREFIX "btc %1,%0" : BITOP_ADDR(addr) : "Ir" (nr)); }}

1

2

3

4

5

6

7

8

9

10

11

12

static inline void change_bit(long nr, volatile unsigned long *addr)

{

if (IS_IMMEDIATE(nr)) {

asm volatile(LOCK_PREFIX "xorb %1,%0"

: CONST_MASK_ADDR(nr, addr)

: "iq" ((u8)CONST_MASK(nr)));

} else {

asm volatile(LOCK_PREFIX "btc %1,%0"

: BITOP_ADDR(addr)

: "Ir" (nr));

}

}

與函數(shù)set_bit相似，但有兩處不同。第一處不同的是xor運算而非or；第二處不同的是btc而非bts。

至此，我們了解了最重要的位圖架構相關運算，接下來我們來查看通用位圖接口。

通用比特運算

除了來自頭文件arch/x86/include/asm/bitops.h的特定架構接口，Linux內核還提供了位圖的通用接口。從前文就已了解，頭文件include/linux/bitmap.h，以及* lib/bitmap.c源碼文件。不過在查看源碼文件之前，我們先來看頭文件include/linux/bitops.h，它提供了一組有用的宏。我們來看其中的一些：

先看下面四個宏：

for_each_set_bit

for_each_set_bit_from

for_each_clear_bit

for_each_clear_bit_from

這些宏提供了位圖迭代器，首個宏迭代集合set，第二個宏也是，不過從集合指定的比特處開始。后面兩個宏也是如此，不同的是迭代清空的比特。我們先來看宏for_each_set_bit的實現(xiàn)：

C

#define for_each_set_bit(bit, addr, size) for ((bit) = find_first_bit((addr), (size)); (bit) < (size); (bit) = find_next_bit((addr), (size), (bit) + 1))

1

2

3

4

#define for_each_set_bit(bit, addr, size)

for ((bit) = find_first_bit((addr), (size));????????

(bit) < (size);????????????????????

(bit) = find_next_bit((addr), (size), (bit) + 1))

正如大家所看到的，此宏擁有三個參數(shù)，以及循環(huán)從set集合第一個比特開始，到最后一個比特結束，迭代比特數(shù)目小于最后一個size，循環(huán)最后返回函數(shù)find_first_bit。

除了這四個宏，arch/x86/include/asm/bitops.h還提供了64位或32位等值的迭代。

同樣，頭文件也提供了位圖的其它接口。比如下面的這兩個函數(shù)：

bitmap_zero;

bitmap_fill.

清除位圖，并為其填值1 。我們來看函數(shù)bitmap_zero實現(xiàn)：

C

static inline void bitmap_zero(unsigned long *dst, unsigned int nbits){ if (small_const_nbits(nbits)) *dst = 0UL; else { unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); memset(dst, 0, len); }}

1

2

3

4

5

6

7

8

9

static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)

{

if (small_const_nbits(nbits))

*dst = 0UL;

else {

unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);

memset(dst, 0, len);

}

}

同樣，先檢查nbits，函數(shù)small_const_nbits定義在相同頭文件中的宏，具體如下：

C

#define small_const_nbits(nbits) (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

1

2

#define small_const_nbits(nbits)

(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

正如大家所見，檢查nbits在編譯期是否為一常量，nbits值是否超過BITS_PER_LONG或64 。倘若bits的數(shù)目沒有超出long類型的總量，將其設置為0 。否則，需計算多少個long類型值填入位圖中，當然我們借助memset填入。

函數(shù)bitmap_fill的實現(xiàn)與bitmap_zero相似，不同的是位圖的填值為0xff或0b11111111：

C

static inline void bitmap_fill(unsigned long *dst, unsigned int nbits){ unsigned int nlongs = BITS_TO_LONGS(nbits); if (!small_const_nbits(nbits)) { unsigned int len = (nlongs - 1) * sizeof(unsigned long); memset(dst, 0xff, len); } dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);}

1

2

3

4

5

6

7

8

9

static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)

{

unsigned int nlongs = BITS_TO_LONGS(nbits);

if (!small_const_nbits(nbits)) {

unsigned int len = (nlongs - 1) * sizeof(unsigned long);

memset(dst, 0xff,??len);

}

dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);

}

除了函數(shù)bitmap_fill和bitmap_zero，頭文件include/linux/bitmap.h還提供了函數(shù)bitmap_copy，它與bitmap_zero相似，不一樣的是使用memcpy而非memset。與此同時，也提供了諸如bitmap_and、bitmap_or, bitamp_xor等函數(shù)進行按位運算?？紤]到這些函數(shù)實現(xiàn)容易理解，在此我們就不做說明；對這些函數(shù)感興趣的讀者朋友們，請打開頭文件include/linux/bitmap.h進行研究。

就寫到這里。

?