位图和位运算
除了各种链式和树形数据结构，Linux内核还供给了位图接口。位图在Linux内核中很多运用。下面的源代码文件包括这些结构的通用接口：
lib/bitmap.c
include/linux/bitmap.h
除了这两个文件，还有一个特定的架构头文件，对特定架构的位运算进行优化。关于x86_64架构，运用下面头文件：
arch/x86/include/asm/bitops.h
正如我前面说到的，位图在Linux内核中很多运用。比方，位图可以用来存储系统在线/离线处理器，来支撑CPU热插拔；再比方，位图在Linux内核等初始化过程中存储已分配的中断请求。
因而，本文要点剖析位图在Linux内核中的详细完成。
位图声明
位图接口运用前，应当知晓Linux内核是怎么声明位图的。一种简略的位图声明方法，即unsigned long数组。比方：
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宏有两个参数：
name – 位图姓名；
bits – 位图中比特总数目
而且扩展元素巨细为BITS_TO_LONGS(bits)、类型unsigned long的数组，而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];
位图声明后，咱们就可以运用它了。
特定架构的位运算
咱们现已查看了操作位图接口的两个源码文件和一个头文件。位图最重要最广泛的运用接口是特定架构，它坐落头文件arch/x86/include/asm/bitops.h中
首要，咱们来看两个重要的函数：
set_bit;
clear_bit.
我以为没有必要介绍这些函数是做什么的，经过函数名就可以知晓。咱们来看函数的完成。进入头文件arch/x86/include/asm/bitops.h，你会留意到每个函数分两种类型：原子类型和非原子类型。在深化这些函数完成前，咱们需求先了解一些原子性运算。
一言以蔽之，原子性操作保证，坐落同一数据上的两个乃至多个运算，不能并发履行。x86架构供给一组原子性指令，如指令xchg、指令cmpxchg。除了原子性指令，一些非原子性指令可凭借指令lock进行原子性运算。现在咱们了解这些原子性运算就足够了，接下来可以开端考虑set_bit和clear_bit函数。
先从非原子性类型的函数开端，非原子性set_bit和clear_bit函数名始于双下划线。正如你所了解的，一切的函数界说在头文件arch/x86/include/asm/bitops.h中，榜首个函数__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”);
}
它具有两个参数：
nr – 位图中比特数目
addr – 位图中某个比特需求设值的地址
留意参数addr界说为volatile，奉告编译器此值或许被某个地址改动。而__set_bit简单完成。正如你所见，刚好它包括一行内联汇编代码。本例中，运用指令bts挑选位图中的某个比特值作为首个操作数，将已挑选比特值存入寄存器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函数中其它束缚。让咱们查看这些束缚，试着了解其间的意义：
+m – 表明内存操作数，+表明此操作数为输入和输出操作数；
I – 表明整数常数；
r -表明寄存器操作数
除了这些束缚，还看到关键字memory，它会奉告编译器此代码会更改内存中的值。接下来，咱们来看相同功用，原子类型函数。它看起来要比非原子类型函数杂乱得多：
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”);
}
}
留意它与函数__set_bit含有相同的参数列表，不同的是函数被符号有特点__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))
这意味着函数会被内联以削减Linux内核镜像的巨细。接着，咱们试着去了解函数set_bit完成。函数set_bit伊始，便对比特数目进行查看。IS_IMMEDIATE是界说在相同头文件中的宏，用于扩展内置函数gcc：
C
#define IS_IMMEDIATE(nr) (__builtin_constant_p(nr))
1
#define IS_IMMEDIATE(nr) (__builtin_constant_p(nr))
内置函数__builtin_constant_p回来1的条件是此参数在编译期为常数；不然回来0。无需运用指令bts设置比特值，由于编译期比特数目为一常量。仅对已知字节地址进行按位或运算，并对比特数目bits进行掩码，使其高位为1，其它为0. 而比特数目在编译期若非常量，函数__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))
选用偏移量扩展某个地址为包括已知比特的字节。比方地址0x1000，以及比特数目0x9。0x9等于一个字节，加一个比特，地址为addr+1：
C
>>> hex(0x1000 + (0x9 >> 3))'0x1001'
1
2
>>> hex(0x1000 + (0x9 >> 3))
'0x1001'
宏CONST_MASK表明看做字节的某已知比特数目，高位为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，保证运算以原子方法履行。
如咱们所知，除了set_bit和__set_bit运算，Linux内核还供给了两个逆向函数以原子或非原子方法整理比特，clear_bit和__clear_bit。这个两个函数均界说在相同的头文件中，并具有相同的参数列表。当然不仅是参数类似，函数自身和set_bit以及 __set_bit都很类似。咱们先来看非原子性函数__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));
}
正如咱们所看到的，它们具有相同参数列表，以及类似的内联汇编函数块。不同的是__clear_bit选用指令btr替代指令bts。从函数名咱们可以看出，函数用来铲除某个地址的某个比特值。指令btr与指令bts类似，挑选某个比特值作为首个操作数，将其值存入寄存器CF标签中，并铲除位图中的这个比特值，且将位图作为指令的第二个操作数。
__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内核中，另一个广泛的运算是断定位图是否已设置比特值。可凭借test_bit宏进行断定，此宏界说在头文件arch/x86/include/asm/bitops.h中，并根据比特数目，挑选调用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在编译期为常数，调用test_bit中函数constant_test_bit，不然调用函数variable_test_bit。咱们来看这些函数完成，先从函数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;
}
函数variable_test_bit具有set_bit等函数类似的参数列表。相同，咱们看到内联汇编代码，履行指令bt、sbb。指令bt或bit test，从位图中挑选某个比特值作为首个操作数，而位图作为第二个操作数，并将选定的比特值存入寄存器CF标签中。而指令sbb则会将首个操作数从第二个操作数中移除，并移除CF标签值。将位图某个比特值写入CF标签寄存器，履行指令sbb，核算CF为00000000 ，最终将成果写入oldbit。
函数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;
}
它可以发生一个字节，其高位时1，其它比特为0，对这个包括比特数目的字节做按位与运算。
接下来比较广泛的位图运算是，位图中的比特值的改动运算。为此，Linux内核供给两个协助函数：
__change_bit;
change_bit.
或许你已能猜到，与set_bit和 __set_bit类似，存在两个类型，原子类型和非原子类型。咱们先来看函数__change_bit的完成：
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具有类似的完成，不同的是，前者选用的指令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
函数__change_bit的原子版别为函数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));
}
}
与函数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的完成：
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))
正如咱们所看到的，此宏具有三个参数，以及循环从set调集榜首个比特开端，到最终一个比特完毕，迭代比特数目小于最终一个size，循环最终回来函数find_first_bit。
除了这四个宏，arch/x86/include/asm/bitops.h还供给了64位或32位等值的迭代。
相同，头文件也供给了位图的其它接口。比方下面的这两个函数：
bitmap_zero;
bitmap_fill.
铲除位图，并为其填值1 。咱们来看函数bitmap_zero完成：
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，函数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的数目没有超出long类型的总量，将其设置为0 。不然，需核算多少个long类型值填入位图中，当然咱们凭借memset填入。
函数bitmap_fill的完成与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);
}
除了函数bitmap_fill和bitmap_zero，头文件include/linux/bitmap.h还供给了函数bitmap_copy，它与bitmap_zero类似，不一样的是运用memcpy而非memset。与此同时，也供给了比如bitmap_and、bitmap_or, bitamp_xor等函数进行按位运算。考虑到这些函数完成简单了解，在此咱们就不做阐明；对这些函数感兴趣的读者朋友们，请打最初文件include/linux/bitmap.h进行研究。
就写到这儿。
