Linux内核中的位数组和位操作除了基于链和树的不同数据结构外，Linux内核还提供了位数组（或称为位图（bitmap））一个API。位数组在Linux内核中被广泛使用，用于此类结构的通用API包含在以下源代码文件中：lib/bitmap.cinclude/linux/bitmap.h除了这两个文件外，还有架构特定的头文件，为特定架构提供优化的位操作。我们将讨论x86_64架构，因此在我们的例子中它将是arch/x86/include/asm/bitops.h头文件。正如我在上面所写的，位图在Linux内核中被广泛使用。例如，位数组通常用于保存一组在线/离线处理器，以便系统支持热插拔CPU（您可以在cpumasks部分阅读更多相关信息），可以在Linux内核中初始化一个位数组，等等。在此期间保存了一组分配的中断处理程序。因此，本节的主要目的是了解位数组在Linux内核中是如何实现的。让我们现在开始吧。位数组声明在我们开始查看位图操作的API之前，我们必须知道如何在Linux内核中声明它。有两种通用的声明位数组的方法。声明位数组的第一种简单方法是定义一个无符号长数组，例如：unsignedlongmy_bitmap[8]第二种方法是使用DECLARE_BITMAP宏，它在include/linux/types.h头文件中定义：#defineDECLARE_BITMAP(name,bits)\unsignedlongname[BITS_TO_LONGS(bits)]我们可以看到DECLARE_BITMAP宏有两个参数：name——位图名称；bits-位图位；并且只需使用BITS_TO_LONGS(bits)元素来扩展长数组的无符号定义。BITS_TO_LONGS宏将给定的位数转换为长整型数，换句话说，计算位中有多少个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))1with:unsignedlongmy_bitmap[1];在能够声明一个位数组之后，我们就可以使用它了。特定于体系结构的位操作我们已经查看了上面提到的一对源文件和头文件，它们为位数组操作提供了一个API。重要且广泛使用的位数组API是特定于体系结构的，位于提到的头文件arch/x86/include/asm/bitops.h中。首先我们来看两个最重要的函数：set_bit；clear_bit。我认为没有必要解释这些功能的作用。从他们的名字来看，这一点已经很明显了。让我们直接看一下它们的实现。如果您浏览arch/x86/include/asm/bitops.h头文件，您会注意到这些函数中的每一个都有原子和非原子变体。在我们开始深入研究这些函数的实现之前，首先，我们必须了解一些关于原子操作的知识。简而言之，原子操作保证不会对同一数据同时执行两个或多个操作。x86架构提供了一系列原子指令，如xchg、cmpxchg等。除了原子指令，一些非原子指令可以借助锁指令变成原子指令。现在您对原子操作有了足够的了解，我们可以继续讨论set_bit和clear_bit函数的实现。我们首先考虑函数的非原子变体。非原子set_bit和clear_bit名称以双下划线开头。我们知道，所有这些函数都定义在arch/x86/include/asm/bitops.h头文件中，第一个函数是__set_bit:staticinlinevoid__set_bit(longnr,volatileunsignedlong*addr){asmvolatile("bts%1,%0":ADDR:"Ir"(nr):"memory");}可以看出，它有两个参数：nr-位数组中的位数（LCTT译注：从0开始）addr-内存地址我们需要设置的位数组注意addr参数是用volatile关键字定义的，目的是告诉编译器给定地址指向的变量可能会被修改。__set_bit的实现相当简单。正如我们所见，它只包含一行内联汇编代码。在我们的示例中，我们使用bts指令从位数组中选择由***操作数（在我们的示例中为nr）指定的位，将所选位的值存储到CF标志寄存器中并设置该位（LCTTAnnotation:即nr指定的位置为1)。注意我们看到了nr的使用，但是这里还有一个参数addr！您可能已经猜到秘密在ADDR中。ADDR是在同一头文件中定义的宏，它扩展为包含给定地址和+m约束的字符串：#defineADDRBITOP_ADDR(addr)#defineBITOP_ADDR(x)"+m"(*(volatilelong*)(x))此外到+m，我们可以在__set_bit函数中看到其他约束。让我们看看并尝试理解它们的含义：+m-表示内存操作数，其中+表示给定的操作数是输入或输出操作数；I——表示整型常量；r-表示寄存器操作数除了这些约束之外，我们还可以看到内存关键字，它告诉编译器这段代码将修改内存中的变量。现在就这些了，让我们看一下相同的原子变体函数。它看起来比非原子变量更复杂：static__always_inlinevoidset_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/compiler-gcc.h中定义的一个宏，它只是扩展到always_inline属性：#define__always_inlineinline__attribute__((always_inline))这意味着这个函数总是内联以减小Linux内核映像的大小。现在让我们尝试了解set_bit函数的实现。首先，我们检查set_bit函数开头给出的位数。IS_IMMEDIATE宏在同一个头文件中定义并扩展为gcc内置函数的调用：#defineIS_IMMEDIATE(nr)(__builtin_constant_p(nr))如果给定参数是编译时已知的常量，__builtin_constant_p内置in函数返回1，否则case返回0。如果给定的位数是编译时已知的常量，我们不需要使用低效的bts指令来设置位。我们可以简单地对给定地址指向的字节进行按位或运算，该字节包含给定的位，掩码位表示掩码，高位为1，其他位为0。在其他情况下，如果给定的位数不是编译时已知常量，我们做与__set_bit函数相同的事情。CONST_MASK_ADDR宏：#defineCONST_MASK_ADDR(nr,addr)BITOP_ADDR((void*)(addr)+((nr)>>3))扩展到给定地址，偏移量包含给定位的字节，例如，我们有地址0x1000和位数0x9。因为0x9代表一个字节+一个位，我们的地址是addr+1:>>>hex(0x1000+(0x9>>3))'0x1001'CONST_MASK宏将我们给定的位号表示为一个字节，bit对应的位number为高位1，其他位为0：#defineCONST_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就是第一个位）注意，这些操作都使用了LOCK_PREFIX标志位，扩展成一个锁指令，保证操作性的原子性。我们知道，除了set_bit和__set_bit操作外，Linux内核还提供了两个功能相反的函数，分别在原子上下文和非原子上下文中清除位。它们是clear_bit和__clear_bit。这两个函数都在同一个头文件中定义，并采用相同的参数集。不仅参数相似，这些函数在一般情况下也与set_bit和__set_bit非常相似。让我们看看非原子__clear_bit的实现：staticinlinevoid__clear_bit(longnr,volatileunsignedlong*addr){asmvolatile("btr%1,%0":ADDR:"Ir"(nr));}是的，正如我们所见，__clear_bit使用相同的参数集并包含非常相似的内联汇编代码块。它只是将bts替换为btr指令。正如我们从函数名称中理解的那样，通过给出地址，它会清除给定的位。btr指令的行为类似于bts。该指令选择第一个操作数指定的位，将其值存储在CF标志寄存器中，并清除第二个操作数指定的位数组中的相应位。__clear_bit的原子变体是clear_bit：static__always_inlinevoidclear_bit(longnr,volatileunsignedlong*addr){if(IS_IMMEDIATE(nr)){asmvolatile(LOCK_PREFIX"andb%1,%0":CONST_MASK_ADDR(nr,addr):"iq"((u8)~CONST_MASK(nr)));}else{asmvolatile(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调用。#definetest_bit(nr,addr)\(__builtin_constant_p((nr))\?constant_test_bit((nr),(addr))\:variable_test_bit((nr),(addr)))因此，如果nr在编译时是已知常量time，test_bit将扩展为对constant_test_bit函数的调用，否则为variable_test_bit。下面我们看看这些函数的实现，先从variable_test_bit开始：=r"(oldbit):"m"(*(unsignedlong*)addr),"Ir"(nr));returnoldbit;}variable_test_bit函数使用一组与set_bit和其他函数类似的参数。我们还可以看到执行bt和sbb指令的内联汇编代码。bt（或位测试）指令从第二个操作数指定的位数组中选择***操作数指定的指定位，并将该位的值存入标志寄存器的CF位。第二条指令sbb从第二个操作数中减去***操作数，然后减去CF的值。因此，这里从给定的位数组中给定的位编号取一个值写入标志寄存器的CF位，执行sbb指令计算：00000000-CF，并将结果写入oldbit变量。constant_test_bit函数与我们在set_bit中看到的一样：static__always_inlineintconstant_test_bit(longnr,constvolatileunsignedlong*addr){return((1UL<<(nr&(BITS_PER_LONG-1)))&(addr[nr>>_BITOPS_LONG_SHIFT]))!=0;}它生成一个字节，其位数对应于高位1和其他位0（如我们在CONST_MASK中看到的），并将按位与应用于包含给定位数Festival的字。下一个广泛使用的与位数组相关的操作是改变位数组中的位。为此，Linux内核提供了两个辅助函数：__change_bit；更改位。你可能已经猜到了，以set_bit和__set_bit为例，这两个变体分别是原子和非原子版本。首先，让我们看一下__change_bit函数的实现：staticinlinevoid__change_bit(longnr,volatileunsignedlong*addr){asmvolatile("btc%1,%0":ADDR:"Ir"(nr));}很简单，不是吗？__change_bit__set_bit的实现与__set_bit相同，只是我们将bts指令替换为btc。该指令从给定位数组中选择一个给定位，将该位的值存储到CF中，并使用取反运算更改其值，因此值为1的位将变为0，反之亦然：>>>int(not1)0>>int(not0)1__change_bit的原子版本是change_bit函数：staticinlinevoidchange_bit(longnr,volatileunsignedlong*addr){if(IS_IMMEDIATE(nr)){asmvolatile(LOCK_PREFIX"xorb%1,%0":CONST_MASK_ADDR(nr,addr):"iq"((u8)CONST_MASK(nr)));}else{asmvolatile(LOCK_PREFIX"btc%1,%0":BITOP_ADDR(addr):"Ir"(nr));}它与set_bit函数非常相似，但有两处不同。***的不同之处在于xor运算而不是or。第二个区别是btc而不是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宏：#definefor_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位或32位变量循环等的API。下一个头文件提供了用于操作位数组的API。例如，它提供了以下两个函数：bitmap_zero；位图填充。他们可以分别清除一个位数组和用1填充位数组。我们来看一下bitmap_zero函数的实现：staticinlinevoidbitmap_zero(unsignedlong*dst,unsignedintnbits){if(small_const_nbits(nbits))*dst=0UL;else{unsignedintlen=BITS_TO_LONGS(nbits)*sizeof(unsignedlong);memset(dst,0,len);}}首先我们可以看到nbits的检查。small_const_nbits是在同一个头文件中定义的宏：#definesmall_const_nbits(nbits)\(__builtin_constant_p(nbits)&&(nbits)<=BITS_PER_LONG)正如我们所见，它检查nbits是否是编译时已知常量，以及它的Thevalue不能超过BITS_PER_LONG或64。如果位数不超过long变量的位数，我们可以直接设置为0。其他情况，我们需要统计需要多少个long变量来填充位数组并使用memset来填充。bitmap_fill函数的实现与biramp_zero函数非常相似，只是我们需要在给定的位数组中填充0xff或0b11111111：(nbits)){unsignedintlen=(nlongs-1)*sizeof(unsignedlong);memset(dst,0xff,len);}dst[nlongs-1]=BITMAP_LAST_WORD_MASK(nbits);}除了bitmap_fill和bitmap_zero，还包括/linux/bitmap.h头文件还提供了bitmap_copy，它与bitmap_zero非常相似，只是它使用memcpy而不是memset。它还提供了对位数组的按位操作，如bitmap_and、bitmap_or、bitamp_xor等。我们不讨论这些函数的实现，因为如果你把这部分都理解了，这些函数的实现就很容易理解了。总之，如果你对这些功能是如何实现的感兴趣，可以打开include/linux/bitmap.h头文件研究一下。这就是这部分的全部内容。
