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

[Eric Blake]

On 12/3/18 4:13 PM, 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, except:
> 
> - it cures a memory leak (bitmap was not being freed),
> 
> - in the cache filter we now mask out existing bits when updating the
>    bitmap.
> ---
> +
> +/* This is the bitmap structure. */
> +struct bitmap {
> +  unsigned blksize;             /* Block size. */
> +  unsigned bpb;                 /* Bits per block (1, 2, 4, 8 only). */
> +  /* bpb = 1 << bitshift   ibpb = 8/bpb
> +     1          0          8
> +     2          1          4
> +     4          2          2
> +     8          3          1
> +  */
> +  unsigned bitshift, ibpb;

As written, you've consumed 16 bytes in the struct by this point.  If 
cache line pressure is a concern, you could make these three values 
unsigned char, and only consume 8 bytes (1 padding) before the next 
field member.

> +
> +  uint8_t *bitmap;              /* The bitmap. */
> +  size_t size;                  /* Size of bitmap in bytes. */
> +};

But even without that compression, a 64-bit architecture should fit the 
struct in 32 bytes, which means cache line pressure may not be a concern.

> +/* This macro calculates the byte offset in the bitmap and which
> + * bit/mask we are addressing within that byte.
> + *
> + * bpb     blk_offset         blk_bit          mask
> + * 1       blk >> 3           0,1,2,...,7      any single bit
> + * 2       blk >> 2           0, 2, 4 or 6     0x3, 0xc, 0x30 or 0xc0
> + * 4       blk >> 1           0 or 4           0xf, 0xf0
> + * 8       blk >> 0           always 0         always 0xff
> + */
> +#define BITMAP_OFFSET_BIT_MASK(bm, blk)                         \
> +  uint64_t blk_offset = (blk) >> (3 - (bm)->bitshift);          \
> +  unsigned blk_bit = (bm)->bpb * ((blk) & ((bm)->ibpb - 1));    \
> +  unsigned mask = ((1 << (bm)->bpb) - 1) << blk_bit

Nice.  Maybe not the easiest indirection when reading a given function 
in isolation (macros don't very often declare variables), but does 
reduce the duplication and chance for errors.

ACK

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