Re: [Qemu-devel] questions about AIO Bitmap

[Yaodong Yang]

Hello Laszlo,

Thank you very much for your very informative answer! It makes me understood 
totally about the bitmap calculation. 

Thanks again!

Yaodong

On Aug 16, 2013, at 9:45 AM, Laszlo Ersek <address@hidden> wrote:

> On 08/16/13 15:39, Yaodong Yang wrote:
>> Hello everyone,
>> 
>> in QEMU 1.5.1, block-migration.c, there is a function below:
>> 
>> static void alloc_aio_bitmap(BlkMigDevState *bmds)
>> {
>>    BlockDriverState *bs = bmds->bs;
>>    int64_t bitmap_size;
>> 
>>    bitmap_size = (bdrv_getlength(bs) >> BDRV_SECTOR_BITS) +
>>            BDRV_SECTORS_PER_DIRTY_CHUNK * 8 - 1;
>>    bitmap_size /= BDRV_SECTORS_PER_DIRTY_CHUNK * 8;
>> 
>>    bmds->aio_bitmap = g_malloc0(bitmap_size);
>> }
>> 
>> I do not understand the calculation for the bitmap_size. Could someone
>> explain it for me? 
> 
> I'm making this up right now:
> 
> bdrv_getlength(bs) returns the size in bytes.
> 
> bdrv_getlength(bs) >> BDRV_SECTOR_BITS gives you the size in 512-byte sectors.
> 
> In the bitmap, each bit will track a chunk of sectors, not one individual 
> sector.
> 
> #define BLOCK_SIZE                       (1 << 20)
> #define BDRV_SECTORS_PER_DIRTY_CHUNK     (BLOCK_SIZE >> BDRV_SECTOR_BITS)
> 
> So, each bit will track 2048 sectors, or (equivalently) 1MB of data.
> 
> You must allocate memory for the bitmap in bytes. That is, the memory 
> allocation granularity is 8 bits, which covers 16384 sectors (16MB of data).
> 
> The multiplication and division "trick" just rounds up to a full byte.
> 
> Step by step:
> 
> 
> (1) bitmap_size = (bdrv_getlength(bs) >> BDRV_SECTOR_BITS);
> 
> This is how many sectors there are.
> 
> 
> (2) bitmap_size = (bdrv_getlength(bs) >> BDRV_SECTOR_BITS) /
>                  BDRV_SECTORS_PER_DIRTY_CHUNK;
> 
> This is how many bits we want to allocate.
> 
> 
> (3) bitmap_size = (bdrv_getlength(bs) >> BDRV_SECTOR_BITS) /
>                  (BDRV_SECTORS_PER_DIRTY_CHUNK * 8);
> 
> This is how many bytes we want to allocate.
> 
> Oops, this will round down (truncate) the result; we should round up.
> 
> 
> For rounding up the a/b division, where a>=0, b>0, we can use
> 
>    (a+(b-1))/b
> 
> Suppose that "a" is divisible by "b":
> 
>    a == k*b  (for a suitable integer "k")
> 
> Then both integer divisions
> 
>    a/b         == ( k*b )         / b
>    (a+(b-1))/b == ( k*b + (b-1) ) / b
> 
> return "k". The remainder is different (0 versus b-1), but in C that's thrown 
> away. In this case, rounding up doesn't change the quotient, which is 
> correct, because the division is exact.
> 
> 
> Now suppose that "a" is not divisible by "b":
> 
>    a == k*b + r  (for a suitable integer "k", and a suitable 0 < r < b)
> 
> Note that this decomposition always exists and is unique, "k" is simply the 
> quotient and "r" the remainder (which is always smaller than the divisor); 
> the above just says that the remainder is nonzero, hence "a" is not divisible 
> by "b".
> 
> In this case we're comparing
> 
>    a/b         == ( k*b + r         ) / b
>    (a+(b-1))/b == ( k*b + r + (b-1) ) / b
> 
> The first division returns "k" (note that "r" is positive and strictly 
> smaller than "b"). The remainder is "r", and it is thrown away.
> 
> We can reorder the second division as
> 
>    (a+(b-1))/b == ( k*b + r + (b-1) ) / b == ( (k+1)*b + (r-1) ) / b
> 
> Now (r-1) is non-negative (because r is positive). (r-1) is also smaller than 
> "b" (because "r" too is smaller than "b"). Therefore this integer division 
> will return (k+1). The remainder is (r-1), and it is thrown away.
> 
> 
> In total we have
> 
>             a/b has zero remainder  a/b has nonzero remainder
>             ----------------------  -------------------------
> a/b          k                       k
> (a+(b-1))/b  k                       k+1
> 
> and the second row is called "rounding up".
> 
> 
> So, we were at
> 
> (3) bitmap_size = (bdrv_getlength(bs) >> BDRV_SECTOR_BITS) /
>                  (BDRV_SECTORS_PER_DIRTY_CHUNK * 8);
> 
> but this truncates instead of rounding up. Let's use the above formula:
> 
>  a := (bdrv_getlength(bs) >> BDRV_SECTOR_BITS)
>  b := (BDRV_SECTORS_PER_DIRTY_CHUNK * 8)
> 
> (4) bitmap_size = (
>                    (bdrv_getlength(bs) >> BDRV_SECTOR_BITS) +
>                    (BDRV_SECTORS_PER_DIRTY_CHUNK * 8) - 1
>                  ) / (BDRV_SECTORS_PER_DIRTY_CHUNK * 8);
> 
> Which is broken up as
> 
>>    bitmap_size = (bdrv_getlength(bs) >> BDRV_SECTOR_BITS) +
>>            BDRV_SECTORS_PER_DIRTY_CHUNK * 8 - 1;
>>    bitmap_size /= BDRV_SECTORS_PER_DIRTY_CHUNK * 8;
> 
> Laszlo