Linux内核中的位数组和位操作
除了不同的基于链式[1]和树[2]的数据结构以外，Linux内核也为位数组[3]（或称为位图bitmap）提供了API[4]。位数组在Linux内核里被广泛使用，并且在以下的源代码文件中包含了与这样的结构搭配使用的通用API：
lib/bitmap.c[5]
include/linux/bitmap.h[6]
除了这两个文件之外，还有体系结构特定的头文件，它们为特定的体系结构提供优化的位操作。我们将探讨x86_64[7]体系结构，因此在我们的例子里，它会是
arch/x86/include/asm/bitops.h[8]
头文件。正如我上面所写的，位图在Linux内核中被广泛地使用。例如，位数组常常用于保存一组在线/离线处理器，以便系统支持热插拔[9]的CPU（你可以在cpumasks[10]部分阅读更多相关知识），一个位数组bitarray可以在Linux内核初始化等期间保存一组已分配的中断处理[11]。
因此，本部分的主要目的是了解位数组bitarray是如何在Linux内核中实现的。让我们现在开始吧。
位数组声明
在我们开始查看位图操作的API之前，我们必须知道如何在Linux内核中声明它。有两种声明位数组的通用方法。第一种简单的声明一个位数组的方法是，定义一个unsignedlong的数组，例如：
unsignedlongmy_bitmap[8]
第二种方法，是使用DECLARE_BITMAP宏，它定义于include/linux/types.h[12]头文件：
#defineDECLARE_BITMAP(name,bits)\
unsignedlongname[BITS_TO_LONGS(bits)]
我们可以看到DECLARE_BITMAP宏使用两个参数：
name-位图名称;
bits-位图中位数;
并且只是使用BITS_TO_LONGS(bits)元素展开unsignedlong数组的定义。BITS_TO_LONGS宏将一个给定的位数转换为long的个数，换言之，就是计算bits中有多少个8字节元素：
#defineBITS_PER_BYTE8
#defineDIV_ROUND_UP(n,d)(((n)+(d)-1)/(d))
#defineBITS_TO_LONGS(nr)DIV_ROUND_UP(nr,BITS_PER_BYTE*sizeof(long))
因此，例如DECLARE_BITMAP(my_bitmap,64)将产生：
(((64)+(64)-1)/(64))
1
与：
unsignedlongmy_bitmap[1];
在能够声明一个位数组之后，我们便可以使用它了。
体系结构特定的位操作
我们已经看了上面提及的一对源文件和头文件，它们提供了位数组操作的API[13]。其中重要且广泛使用的位数组API是体系结构特定的且位于已提及的头文件中arch/x86/include/asm/bitops.h[14]。
首先让我们查看两个最重要的函数：
set_bit;
clear_bit.
我认为没有必要解释这些函数的作用。从它们的名字来看，这已经很清楚了。让我们直接查看它们的实现。如果你浏览arch/x86/include/asm/bitops.h[15]头文件，你将会注意到这些函数中的每一个都有原子性[16]和非原子性两种变体。在我们开始深入这些函数的实现之前，首先，我们必须了解一些有关原子atomic操作的知识。
简而言之，原子操作保证两个或以上的操作不会并发地执行同一数据。x86体系结构提供了一系列原子指令，例如，xchg[17]、cmpxchg[18]等指令。除了原子指令，一些非原子指令可以在lock[19]指令的帮助下具有原子性。现在你已经对原子操作有了足够的了解，我们可以接着探讨set_bit和clear_bit函数的实现。
我们先考虑函数的非原子性non-atomic变体。非原子性的set_bit和clear_bit的名字以双下划线开始。正如我们所知道的，所有这些函数都定义于arch/x86/include/asm/bitops.h[20]头文件，并且第一个函数就是__set_bit:
staticinlinevoid__set_bit(longnr,volatileunsignedlong*addr)
{
asmvolatile("bts%1,%0":ADDR:"Ir"(nr):"memory");
}
正如我们所看到的，它使用了两个参数：
nr-位数组中的位号（LCTT译注：从0开始）
addr-我们需要置位的位数组地址
注意，addr参数使用volatile关键字定义，以告诉编译器给定地址指向的变量可能会被修改。__set_bit的实现相当简单。正如我们所看到的，它仅包含一行内联汇编代码[21]。在我们的例子中，我们使用bts[22]指令，从位数组中选出一个第一操作数（我们的例子中的nr）所指定的位，存储选出的位的值到CF[23]标志寄存器并设置该位（LCTT译注：即nr指定的位置为1）。
注意，我们了解了nr的用法，但这里还有一个参数addr呢！你或许已经猜到秘密就在ADDR。ADDR是一个定义在同一个头文件中的宏，它展开为一个包含给定地址和+m约束的字符串：
#defineADDRBITOP_ADDR(addr)
#defineBITOP_ADDR(x)"+m"(*(volatilelong*)(x))
除了+m之外，在__set_bit函数中我们可以看到其他约束。让我们查看并试着理解它们所表示的意义：
+m-表示内存操作数，这里的+表明给定的操作数为输入输出操作数；
I-表示整型常量；
r-表示寄存器操作数
除了这些约束之外，我们也能看到memory关键字，其告诉编译器这段代码会修改内存中的变量。到此为止，现在我们看看相同的原子性atomic变体函数。它看起来比非原子性non-atomic变体更加复杂：
static__always_inlinevoid
set_bit(longnr,volatileunsignedlong*addr)
{
if(IS_IMMEDIATE(nr)){
asmvolatile(LOCK_PREFIX"orb%1,%0"
:CONST_MASK_ADDR(nr,addr)
:"iq"((u8)CONST_MASK(nr))
:"memory");
}else{
asmvolatile(LOCK_PREFIX"bts%1,%0"
:BITOP_ADDR(addr):"Ir"(nr):"memory");
}
}
（LCTT译注：BITOP_ADDR的定义为：#defineBITOP_ADDR(x)"=m"(*(volatilelong*)(x))，ORB为字节按位或。）
首先注意，这个函数使用了与__set_bit相同的参数集合，但额外地使用了__always_inline属性标记。__always_inline是一个定义于include/linux/北京治疗白癜风的医院哪里白癜风医院好