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 >> bin(1 >> bin(0x4097)
'0b100000010010111'
>>> bin((0x4097 >> 0x9) | (1 _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)
0
>>> int(not 0)
1
__change_bit 的原子版本为 change_bit 函数：
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));
}
}
它和 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_bitfor_each_set_bit_fromfor_each_clear_bitfor_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)
