目录
Bit 原理
Bit 简介
bit 中文翻译 ‘位’，即代表计算机里最小的计数单位。bit 在计算机里可用于表示 ‘0’ 和 ‘1’ 两个值，由于表征数字信号高低电平，为计算机提供了最基础的数据基础。 计算机中，多个 bit 的集合构成了固定长度不同的数据类型，比如字节，字，双字等 数据类型；多个 bit 也可以构成长度不同的位图 (bitmap), 因此位图就是包含了多个 bit 的数组。
由于 bit 的值只包含了 ‘0’ 和 ‘1’ 两种结果，因此在计算机中，bit 经常用于标识 数据的状态。例如使用 bit 标识外围硬件开关的状态等。bit 从低位 (LSB) 开始编号 到高位 (MSB) 将 bit 定义为有序的 bit 序列，程序可以通过特定的算法，有序的管理 每个 bit 的使用，从而构造复杂的数据结构。
Bit 框架
Linux 内核广泛使用 bit 作为其基础数据结构，包括 bitmap (位图), bitops, bitmask, bit find 等，基于这些基础数据结构，将 bit 运用到复杂的数据结构 中，例如 Bit，虚拟文件系统，进程管理等。因此 bit 是内核运行必不可少的部分。
bitmap 位图
Linux 定义了位图 bitmap 为 bit 的数组，数组的成员就是独立的 bit。内核提供 了 bitmap 的通用框架和接口函数，以此便捷使用 bitmap，其定义如下：
linux/lib/bitmap.c 文件包含了 bitmap 的核心实现以及通用接口。
linux/include/linux/bitmap.h bitmap 头文件，包含了 bitmap 相关的宏以及内嵌函数接口
linux/Documentation/core-api/kernel-api.rst bitmap 内核文档bitops
Linux 提供了一套用于操作与机器位宽相同的位操作函数，这套函数用于操作 bitmap 长度在 BITS_PER_LONG 以内的 bit 集合，包括了 bit 的置位，清零，以及 翻转操作。bitops 的函数实现与体系架构有关，因此不同的体系结构有不同的 实现方式，但实现的效果都是一致，因此 bitops 又分为通用部分和与体系相关 部分。Linux 提供了一套通用框架接口函数，其定义基本如下：
linux/include/asm-generic/bitops/non-atomic.h bitops 函数最通用实现。
linux/arch/arm/include/asm/bitops.h 与 ARM 相关的 bitops 函数实现bitmask
Linux 提供了一套用于掩码操作的函数。由于 bit 是内核的基础组成部分，多种 复杂的数据结构都也基于 bit 实现，为了实现多个 bit 的掩码操作，内核也提供 多个函数以及宏用于便捷实现其功能。bitmask 的实现与机器的位宽实现密切相关， 其实现与 BITS_PER_LONG 的实现有关。Linux 提供了一套通过的框架接口，其 定义如下：
linux/include/linux/bitmap.h 包含了 bitmap 掩码相关的宏以及内嵌函数接口
linux/include/bits.h 包含了 bit 基础的掩码宏。bit find
由于 bitmap 包含了多个 bit，需要在 bit 集合中找到符合要求的 bit， 由于 bit 序与大小端有关系，并与体系结构也有关系，因此内核提供了一套 用于查找 bit 的函数接口，其定义如下：
linux/lib/find_bit.c bit 查找的通用接口函数
linux/arch/arm/include/asm/bitops.h ARM 相关的 bit find 接口。
linux/lib/find_bit_benchmark.c bit 查找测试接口函数
Bit 实践
Bit 内核中最小实践
驱动源码
/*
* Bitmap.
*
* (C) 2019.06.10 <buddy.zhang@aliyun.com>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*/
#include <linux/kernel.h>
#include <linux/init.h>
/* header of bitmap */
#include <linux/bitmap.h>
static __init int bitmap_demo_init(void)
{
unsigned long bitmap = 0xf000000;
/* Set range bits on bitmap */
bitmap_set(&bitmap, 4, 8);
printk("Bitmap: %#lx\n", bitmap);
return 0;
}
device_initcall(bitmap_demo_init);驱动安装
驱动的安装很简单，首先将驱动放到 drivers/BiscuitOS/ 目录下，命名为 Bit.c， 然后修改 Kconfig 文件，添加内容参考如下：
diff --git a/drivers/BiscuitOS/Kconfig b/drivers/BiscuitOS/Kconfig
index 4edc5a5..1a9abee 100644
--- a/drivers/BiscuitOS/Kconfig
+++ b/drivers/BiscuitOS/Kconfig
@@ -6,4 +6,14 @@ if BISCUITOS_DRV
config BISCUITOS_MISC
bool "BiscuitOS misc driver"
+config BISCUITOS_Bit
+ bool "Bit"
+
+if BISCUITOS_Bit
+
+config DEBUG_BISCUITOS_Bit
+ bool "Bit mini"
+
+endif # BISCUITOS_Bit
+
endif # BISCUITOS_DRV接着修改 Makefile，请参考如下修改：
diff --git a/drivers/BiscuitOS/Makefile b/drivers/BiscuitOS/Makefile
index 82004c9..9909149 100644
--- a/drivers/BiscuitOS/Makefile
+++ b/drivers/BiscuitOS/Makefile
@@ -1 +1,2 @@
obj-$(CONFIG_BISCUITOS_MISC) += BiscuitOS_drv.o
+obj-$(CONFIG_BISCUITOS_BITMAP) += bitmap.o
--驱动配置
驱动配置请参考下面文章中关于驱动配置一节。在配置中，勾选如下选项，如下：
Device Driver--->
[*]BiscuitOS Driver--->
[*]Bitmap
[*] bitmap mini具体过程请参考：
驱动编译
驱动编译也请参考下面文章关于驱动编译一节：
驱动运行
驱动的运行，请参考下面文章中关于驱动运行一节：
启动内核，并打印如下信息：
usbcore: registered new interface driver usbhid
usbhid: USB HID core driver
Bitmap: 0xf000ff0
aaci-pl041 10004000.aaci: ARM AC'97 Interface PL041 rev0 at 0x10004000, irq 24
aaci-pl041 10004000.aaci: FIFO 512 entries
oprofile: using arm/armv7-ca9
Bit 在应用程序中最小实践
实践源码
开发者也可以使用如下命令获得：
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/bitmap/Basic/Makefile
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/bitmap/Basic/bitmap_run.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/bitmap/Basic/bitmap.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/bitmap/Basic/bitmap.h实践源码具体内容如下：
/*
* Bitmap Manual.
*
* (C) 2019.06.10 <buddy.zhang@aliyun.com>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*/
#include <stdio.h>
#include <stdlib.h>
/* bitmap header */
#include <bitmap.h>
int main()
{
unsigned long bitmap[2] = {0};
u64 map = 0x123456789abcdef;
/* Cover u64 to bitmap */
bitmap_from_u64(bitmap, map);
printf("%#llx cover to [0]%#lx [1]%#lx\n", map, bitmap[0], bitmap[1]);
return 0;
}源码编译
使用如下命令进行编译：
make clean
make源码运行
实践源码的运行很简单，可以使用如下命令，并且运行结果如下：
0x123456789abcdef cover to [0]0x123456789abcdef [1]0
Bitmap 在内核中的应用
Linux 定义了位图 bitmap 为 bit 的数组，数组的成员就是独立的 bit。内核提供 了 bitmap 的通用框架和接口函数，以此便捷使用 bitmap，其定义如下：
linux/lib/bitmap.c 文件包含了 bitmap 的核心实现以及通用接口。
linux/include/linux/bitmap.h bitmap 头文件，包含了 bitmap 相关的宏以及内嵌函数接口
linux/Documentation/core-api/kernel-api.rst bitmap 内核文档Bitmap 与、或、非、异或、与非操作
Bitmap 提供了一套基础的算术逻辑，包括与运算、或运算、非运算、异或运算、与非 运算等，这将大大增加 bitmap 的可用性，其函数接口及实践接口如下：
Bitmap 置位、清零、填充操作
Bitmap 提供了一套用于置位、清零、填充的函数接口，使用这些接口可以便捷的对特定 位进行操作，其函数接口及实践入口如下：
Bitmap 转换操作
在 Linux 中，由于不同的位宽导致 bitmap 所包含的 bit 数目不一样，其与 BITS_PER_LONG 有直接的关系，32-bit 系统中，BITS_PER_LONG 代表一个 long 变量中包含 32 个 bit；在 64-bit 系统中，BIST_PER_LONG 代表一个 long 变量中包含 64 个 bit。由于体系位宽的 差异，内核也为 bitmap 提供了一套用于转换的函数，函数接口及实践入口如下：
Bitmap 位移操作
Bitmap 在特定的需求中需要将其左移或右移多个 bit，因此内核提供了专门用于 bitmap 位移的函数，函数接口及实践入口如下：
Bitmap 查找操作
Bitmap 同样提供了一套用于查找特定 bit 的函数接口，以便在 bitmap 中找到指定 的 bit，函数接口及实践入口如下：
Bitmap 掩码操作
Bitmap 也提供了一套用于掩码的操作，和 bitops 的掩码相比，bitmap 提供的掩码 涉及的 bit 范围更广阔，可以超出 BITS_PER_LONG 的限制，函数接口及实践入口如下：
Bitmap 遍历操作
Bitmap 提供了一套函数用于遍历 bitmap 中置位或者清零的位置，这些函数中可以从 头还是遍历，也可以从指定位置遍历，函数接口及实践入口如下：
Bitmap 其余操作
Bitmap 还提供了其余特定需求的函数，函数接口及实践入口如下：
Bitops 在内核中的应用
Linux 提供了一套用于操作与机器位宽相同的位操作函数，这套函数用于操作 bitmap 长度在 BITS_PER_LONG 以内的 bit 集合，包括了 bit 的置位，清零，以及 翻转操作。bitops 的函数实现与体系架构有关，因此不同的体系结构有不同的 实现方式，但实现的效果都是一致，因此 bitops 又分为通用部分和与体系相关 部分。Linux 提供了一套通用框架接口函数，其定义基本如下：
linux/include/asm-generic/bitops/non-atomic.h bitops 函数最通用实现。
linux/arch/arm/include/asm/bitops.h 与 ARM 相关的 bitops 函数实现Bitops 置位
bitops 的置位操作就是将 bit 中特定的位设置为 ‘1’ 的操作。由于置位操作与体系有关， 因此内核提供了置位的公用部分和与体系相关的部分，其定义基本如下：
Bitops 清零
bitops 的清零操作就是将 bit 中特定的位设置为 ‘0’ 的操作。由于置位操作与体系有关， 因此内核提供了清零的公用部分和与体系相关的部分，其定义基本如下：
Bitops 翻转
bitops 的翻转操作就是将 bit 中特定的位设置值设置为相反的操作。由于翻转操作与体系有关， 因此内核提供了翻转的公用部分和与体系相关的部分，其定义基本如下：
Bitops 测试
bitops 的测试操作就是返回 bit 中特定的位的值，其定义基本如下：
Bitops 遍历操作
Bitops 提供了一套函数用于遍历 bit 中置位或者清零的位置，这些函数中可以从 头还是遍历，也可以从指定位置遍历，但不能超过 BITS_PER_LONG，函数接口及实践入口如下：
Bitops 移位
Bitops 提供了一套函数用于移位操作，函数接口如下:
Bitmask 在内核中的应用
Linux 提供了一套用于掩码操作的函数。由于 bit 是内核的基础组成部分，多种 复杂的数据结构都也基于 bit 实现，为了实现多个 bit 的掩码操作，内核也提供 多个函数以及宏用于便捷实现其功能。bitmask 的实现与机器的位宽实现密切相关， 其实现与 BITS_PER_LONG 的实现有关。Linux 提供了一套通过的框架接口，其 定义如下：
linux/include/linux/bitmap.h 包含了 bitmap 掩码相关的宏以及内嵌函数接口
linux/include/bits.h 包含了 bit 基础的掩码宏。由于掩码与体系位宽有直接的联系，那么在讨论掩码之前，开发者可以先了解各种数据 类型的长度，如下：
char/unsigned char 8-bit
short/unsigned short 16-bit
int/unsigend short 32-bit
long/unsigned long 32-bit(32 位系统)、64-bit (64 位系统)
long long/unsigned long long 64-bit内核使用 BITS_PER_LONG 定义了 long/unsigned long 所包含的 bit 数，以此 为基础，构建内核中的 bitmap 以及 bitmask。内核也定义了 BITS_PER_LONG_LONG 定义 了一个 long long/unsigned long long 所包含的 bit 数。内核的很多宏的位移也 基于位宽长度，如 u/ul/ull/U/UL/ULL 其定义如下：
1U 32-bit
1UL 32-bit(32 位系统)、64-bit (64 位系统)
1ULL 64-bit同理内核中在使用 printk、sprintf 的标准化参数的时候，也限定了位宽，如下：
%d/%u/%x 32-bit
%ld/%lu/%lx 32-bit(32 位系统)、64-bit (64 位系统)
%lld/%llu/%llx 64-bitlinux 为了满足所有的 bit 需求，定义了多种掩码，开发者可以参考如下进行实践 和使用：
Bit find 在内核中的应用
由于 bitmap 包含了多个 bit，需要在 bit 集合中找到符合要求的 bit， 由由于 bit 序与大小端有关系，并与体系结构也有关系，因此内核提供了一套 用于查找 bit 的函数接口，其定义如下：
linux/lib/find_bit.c bit 查找的通用接口函数
linux/arch/arm/include/asm/bitops.h ARM 相关的 bit find 接口。
linux/lib/find_bit_benchmark.c bit 查找测试接口函数bit find: bitmap 相关接口
内核提供了一套通用的 bit find 接口，用于查找特殊需求的 bit 位置，接口说明 以及实践入口如下：
bit find: bitops 相关接口
内核也提供了一套 bit find 的接口，用于在 BITS_PER_LONG 范围内找到需求的 位置，接口说明以及实践入口如下：
bit find: 编译器相关的接口
为了加速 bit 的查找，GCC 编译器也提供了一套函数用于 bit 的查找，这套 函数查找 bit 的范围限定在 BITS_PER_LONG 内。如下：
__builtin_ffs() 找到第一个置位的位置
__builtin_clz() 找到最后一个清零的位置
__builtin_ctzl() 找到第一个置位的位置
__builtin_clzl() 找到最后一个置位的位置
bitmap 可视化工具
Ubuntu 提供了一个 bitmap 的可视化工具，开发者可以使用 bitmap 可视化工具来 学习调试 bitmap。开发者可以使用如下命令使用该工具：
$> bitmap
Bit 内核接口函数列表
附录
赞赏一下吧 🙂
