Re: [Qemu-devel] [PATCH 01/12] hbitmap: serialization

[Stefan Hajnoczi <stefanha@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 4378 bytes --]

On Fri, Aug 07, 2015 at 12:32:33PM +0300, Vladimir Sementsov-Ogievskiy wrote:
> +/**
> + * hbitmap_serialize_part
> + * @hb: HBitmap to oprate on.

s/oprate/operate/

> + * @buf: Buffer to store serialized bitmap.
> + * @start: First bit to store.
> + * @count: Number of bits to store.
> + *
> + * Stores HBitmap data corresponding to given region. The format of saved data
> + * is linear sequence of bits, so it can be used by hbitmap_deserialize_part
> + * independently of endianness and size of HBitmap level array elements

These functions *are* dependent of HBitmap level array element size.

They always assign full array elements (unsigned long).  If count <
BITS_PER_LONG at some point before the end, the bitmap will be corrupt
because leading bits will be zeroed when the next
hbitmap_deserialize_part() call is made!

> + */
> +void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
> +                            uint64_t start, uint64_t count);
> +
> +/**
> + * hbitmap_deserialize_part
> + * @hb: HBitmap to operate on.
> + * @buf: Buffer to restore bitmap data from.
> + * @start: First bit to restore.
> + * @count: Number of bits to restore.
> + *
> + * Retores HBitmap data corresponding to given region. The format is the same

s/Retores/Restores/

> + * as for hbitmap_serialize_part.
> + *
> + * ! The bitmap becomes inconsistent after this operation.
> + * hbitmap_serialize_finish should be called before using the bitmap after
> + * data restoring.
> + */
> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
> +                              uint64_t start, uint64_t count);
> +
> +/**
> + * hbitmap_deserialize_zeroes
> + * @hb: HBitmap to operate on.
> + * @start: First bit to restore.
> + * @count: Number of bits to restore.
> + *
> + * Same as hbitmap_serialize_part, but fills the bitmap with zeroes.
> + */
> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count);
> +
> +/**
> + * hbitmap_deserialize_finish
> + * @hb: HBitmap to operate on.
> + *
> + * Repair HBitmap after calling hbitmap_deserialize_data. Actually, all HBitmap
> + * layers are restored here.
> + */
> +void hbitmap_deserialize_finish(HBitmap *hb);
> +
> +/**
>   * hbitmap_free:
>   * @hb: HBitmap to operate on.
>   *
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 50b888f..c7c21fe 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -378,6 +378,104 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
>      return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
>  }
>  
> +uint64_t hbitmap_data_size(const HBitmap *hb, uint64_t count)
> +{
> +    uint64_t size, gran;
> +
> +    if (count == 0) {
> +        return 0;
> +    }
> +
> +    gran = 1ll << hb->granularity;
> +    size = (((gran + count - 2) >> hb->granularity) >> BITS_PER_LEVEL) + 1;
> +
> +    return size * sizeof(unsigned long);
> +}
> +
> +void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
> +                            uint64_t start, uint64_t count)
> +{
> +    uint64_t i;
> +    uint64_t last = start + count - 1;
> +    unsigned long *out = (unsigned long *)buf;

I'm not sure if we care but this can lead to unaligned stores if buf
isn't aligned to sizeof(unsigned long).  Unaligned stores are best
avoided:
https://www.linux-mips.org/wiki/Alignment

If you replace out[i - start] = ... with a memcpy() call then the
alignment problem is solved.  If you are worried that all these memcpy()
calls are slow, check the compiler output since gcc probably optimizes
away the memcpy().

> +
> +    if (count == 0) {
> +        return;
> +    }
> +
> +    start = (start >> hb->granularity) >> BITS_PER_LEVEL;
> +    last = (last >> hb->granularity) >> BITS_PER_LEVEL;
> +    count = last - start + 1;
> +
> +    for (i = start; i <= last; ++i) {
> +        unsigned long el = hb->levels[HBITMAP_LEVELS - 1][i];
> +        out[i - start] =
> +            (BITS_PER_LONG == 32 ? cpu_to_le32(el) : cpu_to_le64(el));
> +    }
> +}
> +
> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
> +                              uint64_t start, uint64_t count)
> +{
> +    uint64_t i;
> +    uint64_t last = start + count - 1;
> +    unsigned long *in = (unsigned long *)buf;

Same here.

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]