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 <ler...@redhat.com> 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