Re: [Qemu-devel] questions about AIO Bitmap

[Laszlo Ersek]

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