qemu HBitmap原理

一：磁盘位图HBitmap分析
使用unsigned long已经能够胜任bitmap的实现，但是当bitmap比较大的时候，它的操作效率很低。像BloclDriver维持bitmap，磁盘文件的每个块都对应一个bit为，那么这张bitmap表是很大的。如果在热迁移过程中，需要将镜像文件热迁移到目标宿主机上，每次查询bitmap的效率很低。因此，QEMU针对磁盘镜像文件设计了HBitmap数据结构。

HBitmap数据结构如下：
struct HBitmap {
uint64_t size;
uint64_t count;
int granularity;
HBitmap meta;
unsigned long levels[HBITMAP_LEVELS];
uint64_t sizes[HBITMAP_LEVELS];
};

uint64_t size : 虚拟机磁盘大小，计算方式：size = (size + (1ULL << granularity) - 1) >> granularity。 如虚拟镜像大小为1G，size = (102410241024 + (1ULL<<16) -1 ) >>16 即size=16385
int granularity : 12-16，默认是16
unsigned long *levels[HBITMAP_LEVELS] : 保存每一层的位图
uint64_t sizes[HBITMAP_LEVELS] : 记录levels每一层对应的数组大小

磁盘50g时，HBitmap数据结构对应的信息：
{
size = 819200,
count = 4,
granularity = 16,
meta = 0x0,
levels = {0x56131ac3cce0,0x56131ac3ccc0,0x56131ac3cca0,0x56131a70e090,0x56131a70e060,0x56131ac62eb0,0x56131b630400},
sizes = {1,1,4,200,12800}
}

uint64_t sizes[HBITMAP_LEVELS] 每层设置的最大数组，以上层数组的值向右偏移BITS_PER_LEVEL=6位，算法如下：
for (i = HBITMAP_LEVELS; i-- > 0; ) {
size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL,1);
hb->sizes[i] = size;
hb->levels[i] = g_new0(unsigned long,size);
}

HBitmap层次结构图，总共7层，下层记录上层的修改bit位，当上层某bit位置为1时，下层会相应的位记录

二：根据偏移地址在HBitmap中设置
例如，虚拟机在磁盘的起始位置start=2292187136写入count=262144字节

1. 计算第6层word位置（起始word和结束word）
   startpos = 2292187136 >>16>>6 即start = 546，在第6层的第546个位置开始
   lastpos = (start + count - 1) >>16 >>6。在第6层的第546个位置结束
   lastpos = (2292187136 + 262144 - 1) >> 16 >>6 = 546

2. 计算第6层word中对应的bit位
   firsh = start >> 16 = 2292187136 >> 16 = 34976
   last = (start + count - 1) >> 16 = (2292187136 + 262144 - 1) >> 16 = 34979
   mask = 2UL << (last & (BITS_PER_LONG - 1))
   mask -= 1UL << (firsh & (BITS_PER_LONG - 1))
   mask = 2UL << (34979 & (64 - 1)) - (34976 & (64 - 1)) = 0xf00000000
   转换成二进制，在word中的第32， 33，34，35位分别写入1

3. 第6层有bit位写入为1时，继续设置第5层
   先计算第5层的word位（起始word和结束word）
   startpos = 546 >> 6 = 8
   lastpos = 546 >> 6 = 8
   即写入第5层的第8个word位置

   计算第5层word中对应的bit位
   mask = 2UL << (546 & (64 - 1)) - (546 & (64 - 1)) = 0x400000000
   转换成二进制，在word中第34位写入1

4. 如果该层有bit为修改，依次设置下层，直到第0层

三： 根据地址获取对应的bit位例如，虚拟机在磁盘的起始位置start=2292187136，计算该起始位置对应的bit位是否设置为1bit = 1UL <<(start >>hb->granularity) & (BITS_PER_LONG - 1)bit = 1UL <<((2292187136 >> 16) & (64 -1)) = 0x100000000转换成二进制，在word中第32位为1，与在HBitmap中设置的一致。具体实现见函数hbitmap_get