linux 核心中的位數組和位操作
除了不同的基于鍊式和樹的資料結構以外，linux 核心也為位數組(或稱為位圖(bitmap))提供了 api。位數組在 linux 核心裡被廣泛使用，并且在以下的源代碼檔案中包含了與這樣的結構搭配使用的通用 api：
lib/bitmap.c
include/linux/bitmap.h
除了這兩個檔案之外，還有體系結構特定的頭檔案，它們為特定的體系結構提供優化的位操作。我們将探讨 x86_64 體系結構，是以在我們的例子裡，它會是
arch/x86/include/asm/bitops.h
頭檔案。正如我上面所寫的，位圖在 linux 核心中被廣泛地使用。例如，位數組常常用于儲存一組線上/離線處理器，以便系統支援熱插拔的 cpu(你可以在 cpumasks 部分閱讀更多相關知識 )，一個位數組(bit array)可以在 linux 核心初始化等期間儲存一組已配置設定的中斷處理。
是以，本部分的主要目的是了解位數組(bit array)是如何在 linux 核心中實作的。讓我們現在開始吧。
位數組聲明
在我們開始檢視位圖操作的 api 之前，我們必須知道如何在 linux 核心中聲明它。有兩種聲明位數組的通用方法。第一種簡單的聲明一個位數組的方法是，定義一個 unsigned long 的數組，例如：
unsigned long my_bitmap[8]
第二種方法，是使用 declare_bitmap 宏，它定義于 include/linux/types.h 頭檔案：
#define declare_bitmap(name,bits) \
unsigned long name[bits_to_longs(bits)]
我們可以看到 declare_bitmap 宏使用兩個參數：
name - 位圖名稱;
bits - 位圖中位數;
并且隻是使用 bits_to_longs(bits) 元素展開 unsigned long 數組的定義。 bits_to_longs 宏将一個給定的位數轉換為 long 的個數，換言之，就是計算 bits 中有多少個 8 位元組元素：
#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) 将産生：
>>> (((64) + (64) - 1) / (64))
1
與：
unsigned long my_bitmap[1];
在能夠聲明一個位數組之後，我們便可以使用它了。
體系結構特定的位操作
我們已經看了上面提及的一對源檔案和頭檔案，它們提供了位數組操作的 api。其中重要且廣泛使用的位數組 api 是體系結構特定的且位于已提及的頭檔案中 arch/x86/include/asm/bitops.h。
首先讓我們檢視兩個最重要的函數：
set_bit;
clear_bit.
我認為沒有必要解釋這些函數的作用。從它們的名字來看，這已經很清楚了。讓我們直接檢視它們的實作。如果你浏覽 arch/x86/include/asm/bitops.h 頭檔案，你将會注意到這些函數中的每一個都有原子性和非原子性兩種變體。在我們開始深入這些函數的實作之前，首先，我們必須了解一些有關原子(atomic)操作的知識。
簡而言之，原子操作保證兩個或以上的操作不會并發地執行同一資料。x86 體系結構提供了一系列原子指令，例如， xchg、cmpxchg 等指令。除了原子指令，一些非原子指令可以在 lock 指令的幫助下具有原子性。現在你已經對原子操作有了足夠的了解，我們可以接着探讨 set_bit 和 clear_bit 函數的實作。
我們先考慮函數的非原子性(non-atomic)變體。非原子性的 set_bit 和 clear_bit 的名字以雙下劃線開始。正如我們所知道的，所有這些函數都定義于 arch/x86/include/asm/bitops.h 頭檔案，并且第一個函數就是 __set_bit:
static inline void __set_bit(long nr, volatile unsigned long *addr)
{
asm volatile("bts %1,%0" : addr : "ir" (nr) : "memory");
}
正如我們所看到的，它使用了兩個參數：
nr - 位數組中的位号(lctt 譯注：從 0 開始)
addr - 我們需要置位的位數組位址
注意，addr 參數使用 volatile 關鍵字定義，以告訴編譯器給定位址指向的變量可能會被修改。 __set_bit 的實作相當簡單。正如我們所看到的，它僅包含一行内聯彙編代碼。在我們的例子中，我們使用 bts 指令，從位數組中選出一個第一操作數(我們的例子中的 nr)所指定的位，存儲選出的位的值到 cf 标志寄存器并設定該位(lctt 譯注：即 nr 指定的位置為 1)。
注意，我們了解了 nr 的用法，但這裡還有一個參數 addr 呢!你或許已經猜到秘密就在 addr。 addr 是一個定義在同一個頭檔案中的宏，它展開為一個包含給定位址和 +m 限制的字元串：
#define addr bitop_addr(addr)
#define bitop_addr(x) "+m" (*(volatile long *) (x))
除了 +m 之外，在 __set_bit 函數中我們可以看到其他限制。讓我們檢視并試着了解它們所表示的意義：
+m - 表示記憶體操作數，這裡的 + 表明給定的操作數為輸入輸出操作數;
i - 表示整型常量;
r - 表示寄存器操作數
除了這些限制之外，我們也能看到 memory 關鍵字，其告訴編譯器這段代碼會修改記憶體中的變量。到此為止，現在我們看看相同的原子性(atomic)變體函數。它看起來比非原子性(non-atomic)變體更加複雜：
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");
}
(lctt 譯注：bitop_addr 的定義為：#define bitop_addr(x) "=m" (*(volatile long *) (x))，orb 為位元組按位或。)
首先注意，這個函數使用了與 __set_bit 相同的參數集合，但額外地使用了 __always_inline 屬性标記。 __always_inline 是一個定義于 include/linux/compiler-gcc.h 的宏，并且隻是展開為 always_inline 屬性：
#define __always_inline inline __attribute__((always_inline))
其意味着這個函數總是内聯的，以減少 linux 核心映像的大小。現在讓我們試着了解下 set_bit 函數的實作。首先我們在 set_bit 函數的開頭檢查給定的位的數量。is_immediate 宏定義于相同的頭檔案，并展開為 gcc 内置函數的調用：
#define is_immediate(nr) (__builtin_constant_p(nr))
如果給定的參數是編譯期已知的常量，__builtin_constant_p 内置函數則傳回 1，其他情況傳回 0。假若給定的位數是編譯期已知的常量，我們便無須使用效率低下的 bts 指令去設定位。我們可以隻需在給定位址指向的位元組上執行 按位或 操作，其位元組包含給定的位，掩碼位數表示高位為 1，其他位為 0 的掩碼。在其他情況下，如果給定的位号不是編譯期已知常量，我們便做和 __set_bit 函數一樣的事。const_mask_addr 宏：
#define const_mask_addr(nr, addr) bitop_addr((void *)(addr) + ((nr)>>3))
展開為帶有到包含給定位的位元組偏移的給定位址，例如，我們擁有位址 0x1000 和位号 0x9。因為 0x9 代表 一個位元組 + 一位，是以我們的位址是 addr + 1:
>>> hex(0x1000 + (0x9 >> 3))
'0x1001'
const_mask 宏将我們給定的位号表示為位元組，位号對應位為高位 1，其他位為 0：
#define const_mask(nr) (1 << ((nr) & 7))
>>> bin(1 << (0x9 & 7))
'0b10'
最後，我們應用 按位或 運算到這些變量上面，是以，假如我們的位址是 0x4097 ，并且我們需要置位号為 9 的位為 1：
>>> bin(0x4097)
'0b100000010010111'
>>> bin((0x4097 >> 0x9) | (1 << (0x9 & 7)))
'0b100010'
第 9 位 将會被置位。(lctt 譯注：這裡的 9 是從 0 開始計數的，比如0010，按照作者的意思，其中的 1 是第 1 位)
注意，所有這些操作使用 lock_prefix 标記，其展開為 lock 指令，保證該操作的原子性。
正如我們所知，除了 set_bit 和 __set_bit 操作之外，linux 核心還提供了兩個功能相反的函數，在原子性和非原子性的上下文中清位。它們是 clear_bit 和 __clear_bit。這兩個函數都定義于同一個頭檔案 并且使用相同的參數集合。不僅參數相似，一般而言，這些函數與 set_bit 和 __set_bit 也非常相似。讓我們檢視非原子性 __clear_bit 的實作吧：
static inline void __clear_bit(long nr, volatile unsigned long *addr)
asm volatile("btr %1,%0" : addr : "ir" (nr));
沒錯，正如我們所見，__clear_bit 使用相同的參數集合，并包含極其相似的内聯彙編代碼塊。它隻是使用 btr 指令替換了 bts。正如我們從函數名所了解的一樣，通過給定位址，它清除了給定的位。btr 指令表現得像 bts(lctt 譯注：原文這裡為 btr，可能為筆誤，修正為 bts)。該指令選出第一操作數所指定的位，存儲它的值到 cf 标志寄存器，并且清除第二操作數指定的位數組中的對應位。
__clear_bit 的原子性變體為 clear_bit：
clear_bit(long nr, volatile unsigned long *addr)
asm volatile(lock_prefix "andb %1,%0"
: "iq" ((u8)~const_mask(nr)));
asm volatile(lock_prefix "btr %1,%0"
: bitop_addr(addr)
: "ir" (nr));
并且正如我們所看到的，它與 set_bit 非常相似，隻有兩處不同。第一處差異為 clear_bit 使用 btr 指令來清位，而 set_bit 使用 bts 指令來置位。第二處差異為 clear_bit 使用否定的位掩碼和 按位與 在給定的位元組上置位，而 set_bit 使用 按位或 指令。
到此為止，我們可以在任意位數組置位和清位了，我們将看看位掩碼上的其他操作。
在 linux 核心中對位數組最廣泛使用的操作是設定和清除位，但是除了這兩個操作外，位數組上其他操作也是非常有用的。linux 核心裡另一種廣泛使用的操作是知曉位數組中一個給定的位是否被置位。我們能夠通過 test_bit 宏的幫助實作這一功能。這個宏定義于 arch/x86/include/asm/bitops.h 頭檔案，并根據位号分别展開為 constant_test_bit 或 variable_test_bit 調用。
#define test_bit(nr, addr) \
(__builtin_constant_p((nr)) \
? constant_test_bit((nr), (addr)) \
: variable_test_bit((nr), (addr)))
是以，如果 nr 是編譯期已知常量，test_bit 将展開為 constant_test_bit 函數的調用，而其他情況則為 variable_test_bit。現在讓我們看看這些函數的實作，讓我們從 variable_test_bit 開始看起：
static inline int variable_test_bit(long nr, volatile const unsigned long *addr)
int oldbit;
asm volatile("bt %2,%1\n\t"
"sbb %0,%0"
: "=r" (oldbit)
: "m" (*(unsigned long *)addr), "ir" (nr));
return oldbit;
variable_test_bit 函數使用了與 set_bit 及其他函數使用的相似的參數集合。我們也可以看到執行 bt 和 sbb 指令的内聯彙編代碼。bt (或稱 bit test)指令從第二操作數指定的位數組選出第一操作數指定的一個指定位，并且将該位的值存進标志寄存器的 cf 位。第二個指令 sbb 從第二操作數中減去第一操作數，再減去 cf 的值。是以，這裡将一個從給定位數組中的給定位号的值寫進标志寄存器的 cf 位，并且執行 sbb 指令計算： 00000000 - cf，并将結果寫進 oldbit 變量。
constant_test_bit 函數做了和我們在 set_bit 所看到的一樣的事：
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，而其他位為 0 的位元組(正如我們在 const_mask 所看到的)，并将 按位與 應用于包含給定位号的位元組。
下一個被廣泛使用的位數組相關操作是改變一個位數組中的位。為此，linux 核心提供了兩個輔助函數：
__change_bit;
change_bit.
你可能已經猜測到，就拿 set_bit 和 __set_bit 例子說，這兩個變體分别是原子和非原子版本。首先，讓我們看看 __change_bit 函數的實作：
static inline void __change_bit(long nr, volatile unsigned long *addr)
asm volatile("btc %1,%0" : addr : "ir" (nr));
相當簡單，不是嗎? __change_bit 的實作和 __set_bit 一樣，隻是我們使用 btc 替換 bts 指令而已。 該指令從一個給定位數組中選出一個給定位，将該為位的值存進 cf 并使用求反操作改變它的值，是以值為 1 的位将變為 0，反之亦然：
>>> int(not 1)
>>> int(not 0)
__change_bit 的原子版本為 change_bit 函數：
static inline void change_bit(long nr, volatile unsigned long *addr)
asm volatile(lock_prefix "xorb %1,%0"
: "iq" ((u8)const_mask(nr)));
asm volatile(lock_prefix "btc %1,%0"
它和 set_bit 函數很相似，但也存在兩點不同。第一處差異為 xor 操作而不是 or。第二處差異為 btc( lctt 譯注：原文為 bts，為作者筆誤) 而不是 bts。
目前，我們了解了最重要的體系特定的位數組操作，是時候看看一般的位圖 api 了。
通用位操作
除了 arch/x86/include/asm/bitops.h 中體系特定的 api 外，linux 核心提供了操作位數組的通用 api。正如我們本部分開頭所了解的一樣，我們可以在 include/linux/bitmap.h 頭檔案和 lib/bitmap.c 源檔案中找到它。但在檢視這些源檔案之前，我們先看看 include/linux/bitops.h 頭檔案，其提供了一系列有用的宏，讓我們看看它們當中一部分。
首先我們看看以下 4 個 宏：
for_each_set_bit
for_each_set_bit_from
for_each_clear_bit
for_each_clear_bit_from
所有這些宏都提供了周遊位數組中某些位集合的疊代器。第一個宏疊代那些被置位的位。第二個宏也是一樣，但它是從某一個确定的位開始。最後兩個宏做的一樣，但是疊代那些被清位的位。讓我們看看 for_each_set_bit 宏：
#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))
正如我們所看到的，它使用了三個參數，并展開為一個循環，該循環從作為 find_first_bit 函數傳回結果的第一個置位開始，到小于給定大小的最後一個置位為止。
除了這四個宏， arch/x86/include/asm/bitops.h 也提供了 64-bit 或 32-bit 變量循環的 api 等等。
下一個 頭檔案 提供了操作位數組的 api。例如，它提供了以下兩個函數：
bitmap_zero;
bitmap_fill.
它們分别可以清除一個位數組和用 1 填充位數組。讓我們看看 bitmap_zero 函數的實作：
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 的檢查。 small_const_nbits 是一個定義在同一個頭檔案 的宏：
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= bits_per_long)
正如我們可以看到的，它檢查 nbits 是否為編譯期已知常量，并且其值不超過 bits_per_long 或 64。如果位數目沒有超過一個 long 變量的位數，我們可以僅僅設定為 0。在其他情況，我們需要計算有多少個需要填充位數組的 long 變量并且使用 memset 進行填充。
bitmap_fill 函數的實作和 biramp_zero 函數很相似，除了我們需要在給定的位數組中填寫 0xff 或 0b11111111：
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);
除了 bitmap_fill 和 bitmap_zero，include/linux/bitmap.h 頭檔案也提供了和 bitmap_zero 很相似的 bitmap_copy，隻是僅僅使用 memcpy 而不是 memset 這點差異而已。它也提供了位數組的按位操作，像 bitmap_and, bitmap_or, bitamp_xor等等。我們不會探讨這些函數的實作了，因為如果你了解了本部分的所有内容，這些函數的實作是很容易了解的。無論如何，如果你對這些函數是如何實作的感興趣，你可以打開并研究 include/linux/bitmap.h 頭檔案。
本部分到此為止。
作者：0xax
來源：51cto