[Libguestfs] [PATCH nbdkit v2] common: Move shared bitmap code to a common library.

[Eric Blake]

On 12/2/18 10:33 AM, Richard W.M. Jones wrote:
> The cow and cache filters both use a bitmap mapping virtual disk
> blocks to status stored in the bitmap.  The implementation of the
> bitmaps is very similar because one was derived from the other when
> the filters were implemented.
> 
> The main difference is the cow filter uses a simple bitmap (one bit
> per block), whereas the cache filter uses two bits per block.
> 
> This commit abstracts the bitmap structure into a common library.  The
> block size and bits per block are configurable.
> 
> This commit is refactoring.  However it also cures a memory leak
> (bitmap was not being freed).
> ---
>   Makefile.am               |   1 +
>   common/bitmap/Makefile.am |  44 ++++++++++++
>   common/bitmap/bitmap.c    |  74 ++++++++++++++++++++
>   common/bitmap/bitmap.h    | 141 ++++++++++++++++++++++++++++++++++++++

With git's orderfile directive, you can arrange to have all Makefile.am 
appear before all .h before all .c, to make patches a little easier to 
follow logically (what gets built, what interfaces does it need, and how 
is it implemented).  'git config diff.orderFile /path/to/file'; see 
qemu's scripts/git.orderfile for an example.


> +
> +int
> +bitmap_resize (struct bitmap *bm, uint64_t new_size)
> +{
> +  uint8_t *new_bitmap;
> +  const size_t old_bm_size = bm->size;
> +  uint64_t new_bm_size_u64;
> +  size_t new_bm_size;
> +
> +  new_bm_size_u64 = DIV_ROUND_UP (new_size, bm->blksize * 8 / bm->bpb);

Can the computation of bm->blksize * 8 overflow? (blksize is 32-bit 
unsigned; did initialization clamp block size to less than 512M?). But 
appears to be unchanged in the refactor, and at most a pre-existing 
issue.  If so, write bm->blksize * UINT64_C(8) / bm->bpb or similar.


> diff --git a/common/bitmap/bitmap.h b/common/bitmap/bitmap.h
> new file mode 100644
> index 0000000..2e1dd19
> --- /dev/null
> +++ b/common/bitmap/bitmap.h

> +
> +/* This is the bitmap structure. */
> +struct bitmap {
> +  unsigned blksize;             /* Block size. */
> +  unsigned bpb;                 /* Bits per block (1, 2, 4, 8 only). */
> +
> +  uint8_t *bitmap;              /* The bitmap. */
> +  size_t size;                  /* Size of bitmap in bytes. */
> +};
> +
> +static inline void
> +bitmap_init (struct bitmap *bm, unsigned blksize, unsigned bpb)
> +{
> +  assert (is_power_of_2 (blksize));
> +  assert (bpb >= 1);
> +  assert (bpb <= 8);
> +  assert (is_power_of_2 (bpb)); /* Only 1, 2, 4, 8 allowed. */
> +
> +  bm->blksize = blksize;

No validation that blksize is not too big for multiplying by 8 (for bpb 
of 1).

> +  bm->bpb = bpb;
> +
> +  bm->bitmap = NULL;
> +  bm->size = 0;
> +}
> +
> +/* Only frees the bitmap itself, since it is assumed that the struct
> + * bitmap is statically allocated.
> + */
> +static inline void
> +bitmap_free (struct bitmap *bm)
> +{
> +  if (bm)
> +    free (bm->bitmap);
> +}
> +
> +/* Resize the bitmap to the virtual disk size in bytes.
> + * Returns -1 on error, setting nbdkit_error.
> + */
> +extern int bitmap_resize (struct bitmap *bm, uint64_t new_size);
> +
> +/* Return the bit(s) associated with the given block.
> + * If the request is out of range, returns the default value.
> + */
> +static inline unsigned
> +bitmap_get_blk (const struct bitmap *bm, uint64_t blk, unsigned default_)
> +{
> +  uint64_t blk_offset = blk / (8 / bm->bpb);
> +  unsigned blk_bit = bm->bpb * (blk % (8 / bm->bpb));

Would using << and >> instead of / and % aid the compiler, since we know 
we have powers of 2 based on initialization, but the compiler might not 
see it locally?

> +/* Set the bit(s) associated with the given block.
> + * If out of range, it is ignored.
> + */
> +static inline void
> +bitmap_set_blk (const struct bitmap *bm, uint64_t blk, unsigned v)
> +{
> +  uint64_t blk_offset = blk / (8 / bm->bpb);
> +  unsigned blk_bit = bm->bpb * (blk % (8 / bm->bpb));
> +
> +  if (blk_offset >= bm->size) {
> +    nbdkit_debug ("bitmap_set: block number is out of range");
> +    return;
> +  }
> +
> +  bm->bitmap[blk_offset] |= v << blk_bit;

Do you want to mask out the existing bits first, or is this 
intentionally only a saturating set (where you can turn bits on but not 
off)?  Should there be a counterpart for clearing bits?

> +}
> +
> +/* As above bit works with virtual disk offset in bytes. */
> +static inline void
> +bitmap_set (const struct bitmap *bm, uint64_t offset, unsigned v)
> +{
> +  return bitmap_set_blk (bm, offset / bm->blksize, v);
> +}
> +
> +/* Iterate over blocks represented in the bitmap. */
> +#define bitmap_for(bm, /* uint64_t */ blknum)                           \
> +  for (blknum = 0; blknum < (bm)->size * (8 / (bm)->bpb); ++blknum)

For safety, you should probably:

for ((blknum) = 0; (blknum) < (bm)->size * (8 / (bm->bpb); ++(blknum))



-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org