代码、内容参考来自于包括《操作系统真象还原》、《一个64位操作系统的设计与实现》以及《ORANGE’S：一个操作系统的实现》。
位图，也就是bitmap，广泛用于资源管理，是一种管理资源的方式、手段。比如内存或硬盘，对于此类大容量资源的管理一般都会采用位图的方式。
位图包含两个概念：位和图。
位是指bit，即字节中的位， 1字节中有8个位。 图是指map， map地图，本质上就是映射的意思，即对应关系。计算机最小的单位也是位。
位图就是用字节中的1位来映射其他单位大小的资源，按位与资源之间是一对一的对应关系。
位图中的每一位有两种状态，即 0 和 1，若用位图来管理内存，位图中的每一位都将表示实际物理内存中的4KB，也就是一页，即位图中的一位对应物理内存中的一页，如果某位为0，表示该位对应的页未分配，反之如果某位为1，表示该位对应的页已经被分配出去，在将该页回收之前不可再分配。
lib/kernel/bitmap.c
#include "bitmap.h"
#include "stdint.h"
#include "string.h"
#include "print.h"
#include "interrupt.h"
#include "debug.h"
/* 将位图btmp初始化 */
void bitmap_init(struct bitmap* btmp) {
memset(btmp->bits, 0, btmp->btmp_bytes_len);
}
/* 判断 bit_idx 位是否为 1 ,若为 1, 则返回true, 否则返回false */
bool bitmap_scan_test(struct bitmap* btmp, uint32_t bit_idx) {
uint32_t byte_idx = bit_idx / 8; // 向下取整用于索引数组下标
uint32_t bit_odd = bit_idx % 8; // 取余用于索引数组内的位
return (btmp->bits[byte_idx] & (BITMAP_MASK << bit_odd)); // 00x00000, 判断第x位是否为1
}
/* 在位图中申清连续 cnt 个位, 成功, 则返回其起始位下标, 失败, 返回 -1 */
int bitmap_scan(struct bitmap* btmp, uint32_t cnt) {
uint32_t idx_byte = 0; // 用于记录空闲位所在的字节
/* 先逐字节比较，蛮力法 */
// 一位16进制代表4位二进制, 所以 0xff 代表一字节且该字节全为 1
while ((0xff == btmp->bits[idx_byte]) && (idx_byte < btmp->btmp_bytes_len)) {
idx_byte++;
}
/* 如果找不到可用空间就返回 -1 */
ASSERT(idx_byte < btmp->btmp_bytes_len);
if (idx_byte == btmp->btmp_bytes_len) {
return -1;
}
/* 若在位图数组范围内的某字节内找到了空闲位, 在该字节内逐位比对, 返回空闲位的索引。*/
int idx_bit = 0;
while ((uint8_t) (BITMAP_MASK << idx_bit) & btmp->bits[idx_byte]) {
idx_bit++;
}
int bit_idx_start = idx_byte * 8 + idx_bit; // 空闲位在位图中的下标
if (cnt == 1) {
return bit_idx_start;
}
uint32_t bit_left = (btmp->btmp_bytes_len * 8 - bit_idx_start); // 记录还有多少位可以判断
uint32_t next_bit = bit_idx_start + 1;
uint32_t count = 1; // 记录找到空闲位的个数
bit_idx_start = -1; // 先将其置为-1, 若找不到连续的位就返回-1
while ((bit_left--) > 0) {
if (!bitmap_scan_test(btmp, next_bit)) {
// 若 next_bit为 0
count++;
} else {
// 空间不连续, 重置连续空间数为0, 继续寻找连续空间
count = 0;
}
// 若找到连续的 cnt 个空位
if (count == cnt) {
bit_idx_start = next_bit - cnt + 1;
break;
}
next_bit++;
}
return bit_idx_start;
}
/* 将位图 btmp 的 bit_idx 位设置为 value */
void bitmap_set(struct bitmap* btmp, uint32_t bit_idx, int8_t value) {
ASSERT((value == 0) || (value == 1));
uint32_t byte_idx = bit_idx / 8; // 向下取整用于索引数组下标
uint32_t bit_odd = bit_idx % 8; // 取余用于索引数组内的位
if (value) {
// 如果 vaule 为 1, 按位或
btmp->bits[byte_idx] |= (BITMAP_MASK << bit_odd);
} else {
// 如果 vaule 为 0, 取反再按位与
// 取反: 将除所要操作的位置 0, 其余位全部置 1
// 按位与: 1 & 1 = 1, 0 & 1 = 0, 即其余位不受影响, 目标位置 0
btmp->bits[byte_idx] &= ~(BITMAP_MASK << bit_odd);
}
}bitmap_init 函数只有一个参数，即位图指针 btmp，此函数功能是初始化位图 btmp，它是用 memset函数根据位图的字节大小btmp_bytes_len将位图的每一个字节用0来填充。
bitmap_scan_test函数接受两个参数，分别是位图指针btmp和位索引bit_idx。其功能是判断位图btmp中的第bit_idx位是否为1，若为1，则返回true，否则返回false。此函数是被bitmap_scan调用的，当想在位图中获得连续多个可用位时，逐次调用bitmap_scan_test依次判断。
bitmap_scan函数接受两个参数，分别是位图指针btmp及位的个数cnt。此函数的功能是在位图btmp中找到连续的cnt个可用位，返回起始空闲位下标，若没找到cnt个空闲位，返回-1。位图中的位，其值为0就表示该位对应的资源可用，故此函数的原理是在btmp->bits所指向的位图中先逐字节查找值为0的位所在的字节，以该字节为起始，然后逐个判断每一个位，若找到连续的cnt值为0的空闲位，返回第一个空闲位所在的下标。
bitmap_scan是位图操作的核心方法，其他位图函数也用到了该函数中的方法，下面看其实现。idx_byte用于记录第一个空闲位所在的字节索引，此变量用在下面的whi le循环中，在位图的字节长度btmp_bytes_len范围内逐字节查找，若字节的值不为0xff，就说明该字节里面至少有一个0，于是循环条件不成立，退出循环。如果idx_byte等于位图的字节长度，表示位图已没有空闲位，直接返回-1。
接下来在该字节内逐位判断，定义一个变量idx_bit，用于记录此字节内第一个空闲位的下标。在含有空闲位的字节(idx_byte)内逐个判断所有位，判断的方法是在while循环中，用BITMAP_MASK <<idx_bit将1逻辑左移到各位，然后与该字节内的各位进行按位与操作，直到按位与的结果为0 时退出循环，因此找到空闲位，其下标就记在变量idx_bit中。 idx_bit 仅仅是字节内的索引，其值范围是 0~7，我们声明一个变量 bit_idx_start，将idx_bit转换成整个位图内的位索引，就是加了个空闲位所在字节的位数: idx_byte*8。
然后判断cnt的大小，若只想获取一个空闲位，即cnt为1的话， bit_idx_start就是最终的结果，直接return bit_idx_start;将其返回。 如果 cnt 大于 1，这说明还要继续在位图中找空闲位，但我们得知道位图中还有多少个剩余位，一定不能访问到位图外的内存。 所以用变量bit_left来记录位图内还有多少个位可以判断，它的值等于位图中位的总数量减去第一个空闲位的索引，即 btmp_bytes_len *8-bit_idx_start，next_bit用于记录位图中下一个待查找的位，它是相对于整个位图的位下标。
目前也不知道 next_bit 位是空闲位（0），还是已经占用（1），所以要传给函数 bitmap_scan_test 去判断。 变量count用于记录找到的空闲位的个数，我们不是要找到cnt个空闲位吗，当找到的空闲位count等于cnt时，就表示咱们成功找到了cnt个空闲位。
虽然 bit_idx_start 是位图中第一个空闲位的下标，但我们的目的是找到连续的 cnt 个空闲位，若找不到cnt个连续空闲位就失败返回，将变量bit_idx_start置为-1,，即默认情况下找不到cnt个空闲位。 然后通过调用 bitmap_scan_test 依次判断下一位 next_bit 是否为 0，即是否为空闲，每判断一位就将next_bit++。 每找到一个连续的空闲位就将count++，若下一个位不是空闲，就将count清0，从头再来重新找。
若发现count等于cnt，说明完成任务，将bit_idx_start改为连续cnt 个空闲位的起始，即”bit_idx_start=next_bit-cnt+1″。 通过 break退出循环，执行”return bit_idx_start” 返回。 否则，当bit_left递减为0时，即表示位图中所有的位都检索过了，于是while循环条件不成立，循 环退出，此时 bit_idx_start依然是-1，于是将 bit_idx_start返回表示失败。
bitmap_set接受三个参数，位图指针btmp、位索引bit_idx、位值value，函数功能是将位图btmp中的第 bit_idx 位设置为 value，其中 bit_idx 为整个位图中的位索引。 ASSERT用来监督value的范围，既然是为位设置值，value要么是0，要么是1，将bit_idx转换成相应的字节byte_idx及字节内的偏移bit_odd，然后将字节bits[byte_idx]中的第bit_odd位置为value，也就是将位图中的第bit_idx位的值置为 value。 对于value的值，这里的处理分两种情况。 如果value为1，直接将BITMAP_MASK (宏值为1)左移bit_odd位后与位图中的字节bits[byte_idx]进行按位或运算，这样该字节中的位 bit_odd 便为 1，其他位为原值。 如果value为0，即只将字节 bits[byte_idx]中的bit_odd位置为0，方法是让某个字节中的bit_odd位为0，其他位为1，然后将该字节与bits[byte_idx]做按位与运算。 这样bits[byte_idx]中的第bit_odd位便置为0，其他位为原值。
需要在/kernel/global.h下添加一些宏
#define NULL ((void*)0) #define bool int #define true 1 #define false 0
对应lib/kernel/bitmap.h如下：
#ifndef __LIB_KERNEL_BITMAP_H
#define __LIB_KERNEL_BITMAP_H
#include "global.h"
#define BITMAP_MASK 1
struct bitmap {
uint32_t btmp_bytes_len;
/* 在遍历位图时, 整体上以字节为单位, 细节上是以位为单位, 所以此处位图的指针必须是单字节 */
// 使用位图数组需要知道其长度, 但是长度得以后才能知道, 所以这里可以用指定地址来代替使用数组
uint8_t* bits;
};
/* 将位图btmp初始化 */
void bitmap_init(struct bitmap* btmp);
/* 判断 bit_idx 位是否为 1 ,若为 1, 则返回true, 否则返回false */
bool bitmap_scan_test(struct bitmap* btmp, uint32_t bit_idx);
/* 在位图中申清连续 cnt 个位, 成功, 则返回其起始位下标, 失败, 返回 -1 */
int bitmap_scan(struct bitmap* btmp, uint32_t cnt);
/* 将位图 btmp 的 bit_idx 位设置为 value */
void bitmap_set(struct bitmap* btmp, uint32_t bit_idx, int8_t value);
#endifstruct bitmap 中只定义了两个成员：位图的指针 bits 和位图的字节长度 btmp_bytes_len。
位图长度取决于所管理资源的大小，其长度不固定，因此不能在位图结构struct bitmap中生成固定大小的位图数组。所以在struct bitmap中提供位图的指针，就是uint8_t* bits.
bits的类型是uint8_t*，此类型强调的是字节型指针，最好不要用多字节类型，否则在处理时会复杂。 因为我们在遍历位图时先是通过字节来定位某bit所在的字节，如果将其设为其他类型，比如int32，在遍历位图时会产生4字节的跳跃，每次处理其中的bit时要判断32个bit，不如让数组成员为字节型，这样字节偏移量就是数组元素的索引，定位方便，而且只处理8个bit，因此指针bits的类型最好设为单字节大小。 宏BITMAP_MASK其值为1，用来在位图中逐位判断，主要就是通过按位与&，来判断相应位是否为 1。
参考
郑钢著操作系统真象还原
田宇著一个64位操作系统的设计与实现
丁渊著ORANGE’S：一个操作系统的实现
