Linux系统位运算函数以及相应CPU ISA实现收录

函数以及相应CPU ISA实现收录"/>

Linux系统位运算函数以及相应CPU ISA实现收录

以32位数据的二进制表示为例，习惯的写法是LSB在右，MSB在左，注意BIT序和大小端的字节序没有关系。

Linux和BIT操作有关的接口在定义在头文件bitops.h中，bitops.h定义有两层，通用层和架构层，对应两个bitops.h，通用层的定义在./include/linux/bitops.h中，架构层和处理器类型有关，定义在./arch/$ARCH/include/asm/bitops.h中。

除了这两个之外，实际上还有一个不常用到的include/asm-generic/bitops.h，这个头文件一般只能被include/linux/bitops.h引用

所以引用关系可以表示为：

arch目录下的bitops.h定义也仅允许被./include/linux/bitops.h引用。

如果./include/asm-generic/下的头文件没有直接被./include/linux/bitops.h引用，则也可以被ARCH下的头文件直接引用./arch/$ARCH/include/asm/bitops.h

下面分别介绍每个BITOPS函数：

ffs

ffs意思是Find First bit Set in word(From LSB to MSB).BIT从1开始记，返回值是[1,32],当输入0值时，返回是0,也就是ffs(0) = 0;ffs(1)=1, ffs(0x80000000)=32;所以算上返回0的情况，值域是[0,32].

__ffsll

#include <stdio.h>
#include <stdlib.h>int main(void)
{unsigned long sa = 0x1100000;unsigned long sb = 0x80000000;printf("%s line %d, mask = 0x%x.\n",__func__, __LINE__, (1 << (__builtin_ffsll(sa) - 1)) - 1);printf("%s line %d, mask = 0x%x.\n",__func__, __LINE__, (1 << (__builtin_ffsll(sb) - 1)) - 1);printf("%s line %d, mask = %d.\n",__func__, __LINE__, __builtin_ffsll(sb));return 0;
}

__ffs

__ffs意思同样是Find First bit Set in word.(From LSB to MSB).与ffs不同的是，__ffs从0开始记数。由于返回0表示的是bit 0为1,所以没有一个合理返回值表达__ffs(0)，所以__ffs(0)没有定义，应用必须自行主动判断为0的情况，保证输入__ffs的参数为非0值。__ffs(0)=Undefined. __ffs(1) = 0; __ffs(0x80000000)=31;

__ffs/ffs相互实现:

int ffs(int x)
{if (!x) return 0;return __ffs(x) + 1;
}int __ffs(int x)
{return ffs(x) - 1;
}

__ffs对参数的要求条件要强于ffs,所以_ffs的参数可以直接传给ffs，但是ffs的参数需要做0检查才能传递给__ffs。有点类似于C++基类和子类前置条件和后置条件的关系。

ffz

ffz means Find First Zero in word. 值域范围为[0,31].如果输入为0xFFFFFFFF，则结果未定义。在调用前，应用层因该进行条件检查。

ffz恰好是_ffs的逆运算而非ffs的逆运算。所以可以通过_ffs来实现ffz

#define ffz(x) _ffs(~(x))

clz

clz means "Count Leading Zeroes".计算前导0的个数，它从最高有效位（MSB）开始计算第一个位之前存在多少个零。在有些架构的处理器中，专门定义了"clz"指令用来完成此类运算，比如MIPS。

clz是下面将要介绍的fls的小伙伴和好助手，通过clz实现fls非常的简单和方便。由于它是一个计数值而非一个位置，所以值域并非前面的[0,31]或者[1,32],而是[0,32]. czl[0] = 32, czl(0xFFFFFFFF)=0,

clz(0x1)=31; clz(0x80000000)=0;

RISCV B扩展支持CLZ指令，B扩展几乎支持这篇文章讲到的所有BIT 操作指令，包括插入，提取，测试位域，COUNT BIT SET等等。

ctz

ctz means "Count Trailing Zeroes".它和clz有些类似，只是计算的是尾巴上（LSB)连续0的个数。它从最低有效位（LSB）开始计算第一个置位之前存在多少个零。

RISCV对此算法也有ISA指令级别的支持。

fls

fls means Find Last(Most Significant) bit set.和ffs恰恰相反，fls从LSB开始查找，找到最后一个值1的位，并返回其位置。值域为[1,32]. fls(0) = 0; fls(1) = 1; fls(0x80000000) = 32; 算上输入为0的情况，值域为[0,32]

fls可以通过clz实现：

fls(x) = 32-clz(x);

__fls

如同ffs和__ffs的关系一样，__fls也可以通过fls减1实现。同样对于0值，__fls不知如何处理，需要应用负责判断。

int __fls(unsigned long x)
{if(!x) return 0;else return fls(x) - 1;
}

hweight_long/hweight32/hweight64

返回一个数字的加权平衡值，一个数的加权平衡是这个数所有位的总和。定义在文件include/asm-generic/bitops/const_hweight.h

#include <stdio.h>
#include <stdlib.h>
#include "include/asm-generic/bitops/const_hweight.h"int main(void)
{printf("%s line %d, %d, %d, %d.\n", __func__, __LINE__, hweight32(0), hweight32(0xffffffff), hweight32(0x08000000));return 0;
}

find_first_zero_bit

在内存中查找第一个值为0的位。

find_next_zero_bit

在内存中查找下一个值为0的位

bitfield实现

bitfield可以提取，写入，修改数据的指定BIT区域，内核中有bitfield.h文件定义对为域操作的接口：

根据区间生成位MASK：

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>#define ULL unsigned long long
#define ULL_LEN 64#define GENMASK_ULL(h, l) \(((~(ULL)(0)) - ((ULL)(1) << (l)) + 1) & \(~(ULL)(0) >> (ULL_LEN - 1 - (h))))int main(void)
{printf("%s line %d, ULL0 is 0x%llx, 0x%016llx.\n", __func__, __LINE__, (~(ULL)(0)), ~(ULL)(0) >>12);printf("%s line %d, 0x%llx.\n", __func__, __LINE__, GENMASK_ULL(26, 9));return 0;
}

Linux页面大小MASK

#include <stdio.h>
#include <stdlib.h>#define PAGE_SHIFT  12
#define PAGE_SIZE   (1 << PAGE_SHIFT)
#define PAGE_MASK   (~(PAGE_SIZE-1))int main(void)
{printf("%s line %d, PAGE_SIZE 0x%x. PAGE_MASK 0x%x, ~PAGE_MASK=0x%x.\n", \__func__, __LINE__, PAGE_SIZE, PAGE_MASK, ~PAGE_MASK);return 0;
}

atomic_cmpxcg:

1.无论交换与否，都会返回原值。

2.下图的多线程访问是安全的，参考DRM GPU。

位运算的一个应用gen_pool

gen_pool是内核提供的一种内存分配器 ，使用bitmap来管理申请和释放连续内存，被管理的内存被称为chunk.

在BIMAP里，两个连续的unsigned long首尾相接组成整个BITMAP图：

  1 #include <stdio.h>2 #include <stdlib.h>3  4 #define BITS_PER_LONG        (sizeof(long)*8UL)                                                                                                                                                         5 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))6 int main(void)7 {8     int start = 6;9     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);10  11     printf("%s line %d, mask_to_set 0x%lx.\n", __func__, __LINE__, mask_to_set);12  13     return 0;14 }

gen_pool使用无锁内存分配机，基于gen_pool实现的内存分配器可以做到lock free,其根源机制在于gen_pool中RCU锁的使用，以及设置/清理BIT MAP时候的原子操作。

比如，下图中retry逻辑能够安全执行的原因就是，原子操作保证了这样一种情况，如果一段BITMAP位图的后面部分位域监测出了冲突，则前面的已经设置的部分位域一定是自己分配的，可以安全CLAER（否则，BITMAP就不可能走到当前的位置，既然已经走到了当前位置，说明当前进程自身就是前面置1的区域的OWNER，如果和另外的BITMAP设置上下文冲突，有权可以清理设置的BITMAP）。

---

参考资料

斯坦福大学关于位运算的算法总结：

Bit Twiddling Hacks

结束

---