Linux 内核数据结构：位图（Bitmap）
位图和位运算
除了各种链式和树形数据结构，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 addrbitop_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 <>> bin(1 <>> bin(1 <>> bin(0x4097)'0b100000010010111'>>> bin((0x4097 >> 0x9) | (1 <>> 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 _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 <> _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进行研究。
就写到这里。
5G手机渗透率在节节攀升，推动零部件采购量的大幅提升
常用数控加工计算公式和最全螺纹标准
5G车载网关让医院无人配送车“灵活”起来
超宽带 (UWB) 如何助力打造智能工厂？后面四个落地案例值得参考
从fan-in、fan-out看setup和hold time violation
Linux 内核数据结构：位图（Bitmap）
AG9311MAQ扩展成本低性价比高的Type-C
Reference Design for a High-Cu
米家投影仪青春版评测 将性价比做到了极致
Velox机器人柔性鳍能力独特 既能在水中或水面自如行进
摩托罗拉Razr被iFixit评迄今最复杂的手机 且用“大量工业成就”形容结构设计
人工智能会不会泡沫化
生益科技与和美精艺战略合作签约仪式成功举行
AD56xx系列DAC的驱动设计与实现
各国政府出手，解决汽车芯片荒问题
平衡晶格氧活性和可逆性实现高比能钠离子电池层状正极材料
未来3-5年 边缘计算会是下一个百亿蓝海市场
小米note3什么时候上市？小米note3最新消息：小米note3蓄势待发，8月上市，全曲面屏+双摄像头设计
小米6最新消息：价值10万且无法量产的小米6亮银探索版真机图赏
CMOS图像传感器设计考虑因素及典型应用方案
除了各种链式和树形数据结构，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 addrbitop_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 <>> bin(1 <>> bin(1 <>> bin(0x4097)'0b100000010010111'>>> bin((0x4097 >> 0x9) | (1 <>> 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 _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 <> _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进行研究。
就写到这里。
5G手机渗透率在节节攀升，推动零部件采购量的大幅提升
常用数控加工计算公式和最全螺纹标准
5G车载网关让医院无人配送车“灵活”起来
超宽带 (UWB) 如何助力打造智能工厂？后面四个落地案例值得参考
从fan-in、fan-out看setup和hold time violation
Linux 内核数据结构：位图（Bitmap）
AG9311MAQ扩展成本低性价比高的Type-C
Reference Design for a High-Cu
米家投影仪青春版评测 将性价比做到了极致
Velox机器人柔性鳍能力独特 既能在水中或水面自如行进
摩托罗拉Razr被iFixit评迄今最复杂的手机 且用“大量工业成就”形容结构设计
人工智能会不会泡沫化
生益科技与和美精艺战略合作签约仪式成功举行
AD56xx系列DAC的驱动设计与实现
各国政府出手，解决汽车芯片荒问题
平衡晶格氧活性和可逆性实现高比能钠离子电池层状正极材料
未来3-5年 边缘计算会是下一个百亿蓝海市场
小米note3什么时候上市？小米note3最新消息：小米note3蓄势待发，8月上市，全曲面屏+双摄像头设计
小米6最新消息：价值10万且无法量产的小米6亮银探索版真机图赏
CMOS图像传感器设计考虑因素及典型应用方案