Re: [Qemu-devel] [PATCH RFC v3 02/14] hbitmap: serialization

[John Snow <jsnow@redhat.com>]

On 02/18/2015 09:00 AM, Vladimir Sementsov-Ogievskiy wrote:
> Functions to serialize / deserialize(restore) HBitmap. HBitmap should be
> saved to linear sequence of bits independently of endianness and bitmap
> array element (unsigned long) size. Therefore Little Endian is chosen.
>
> These functions are appropriate for dirty bitmap migration, restoring
> the bitmap in several steps is available. To save performance, every
> step writes only the last level of the bitmap. All other levels are
> restored by hbitmap_deserialize_finish() as a last step of restoring.
> So, HBitmap is inconsistent while restoring.
>
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@parallels.com>
> ---
>   include/qemu/hbitmap.h | 59 +++++++++++++++++++++++++++++++
>   util/hbitmap.c         | 96 ++++++++++++++++++++++++++++++++++++++++++++++++++
>   2 files changed, 155 insertions(+)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index c19c1cb..10ce05b 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -129,6 +129,65 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
>   bool hbitmap_get(const HBitmap *hb, uint64_t item);
>
>   /**
> + * hbitmap_data_size:
> + * @hb: HBitmap to operate on.
> + * @count: Number of bits
> + *
> + * Return amount of bytes hbitmap_serialize_part needs
> + */
> +uint64_t hbitmap_data_size(const HBitmap *hb, uint64_t count);
> +
> +/**
> + * hbitmap_serialize_part
> + * @hb: HBitmap to oprate on.
> + * @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
> + */
> +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
> + * 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 962ff29..1a736e7 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -362,6 +362,102 @@ 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;
> +
> +    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] = (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;
> +
> +    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) {
> +        hb->levels[HBITMAP_LEVELS - 1][i] =
> +            (BITS_PER_LONG == 32 ? le32_to_cpu(in[i]) : le64_to_cpu(in[i]));
> +    }
> +}
> +
> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count)
> +{
> +    uint64_t last = start + count - 1;
> +
> +    if (count == 0) {
> +        return;
> +    }
> +
> +    start = (start >> hb->granularity) >> BITS_PER_LEVEL;
> +    last = (last >> hb->granularity) >> BITS_PER_LEVEL;
> +    count = last - start + 1;
> +
> +    memset(hb->levels[HBITMAP_LEVELS - 1] + start, 0,
> +           count * sizeof(unsigned long));
> +}
> +
> +void hbitmap_deserialize_finish(HBitmap *bitmap)
> +{
> +    int64_t i, size, prev_size;
> +    int lev;
> +
> +    /* restore levels starting from penultimate to zero level, assuming
> +     * that the last level is ok */
> +    size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
> +    for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) {
> +        prev_size = size;
> +        size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
> +        memset(bitmap->levels[lev], 0, size * sizeof(unsigned long));
> +
> +        for (i = 0; i < prev_size; ++i) {
> +            if (bitmap->levels[lev + 1][i]) {
> +                bitmap->levels[lev][i >> BITS_PER_LEVEL] |=
> +                    1 << (i & (BITS_PER_LONG - 1));
> +            }
> +        }
> +    }
> +
> +    bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
> +}
> +
>   void hbitmap_free(HBitmap *hb)
>   {
>       unsigned i;
>

Reviewed-by: John Snow <jsnow@redhat.com>