[11/13] hbitmap: serialization

From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>

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@virtuozzo.com>
[Fix left shift operand to 1UL; add "finish" parameter. - Fam]
Signed-off-by: Fam Zheng <famz@redhat.com>
---
 include/qemu/hbitmap.h |  76 +++++++++++++++++++++++++++
 util/hbitmap.c         | 136 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 212 insertions(+)

On 01/04/2016 05:27 AM, Fam Zheng wrote:
> From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> 
> 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@virtuozzo.com>
> [Fix left shift operand to 1UL; add "finish" parameter. - Fam]
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  include/qemu/hbitmap.h |  76 +++++++++++++++++++++++++++
>  util/hbitmap.c         | 136 +++++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 212 insertions(+)
> 
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index ed672e7..3414113 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -149,6 +149,82 @@ void hbitmap_reset_all(HBitmap *hb);
>  bool hbitmap_get(const HBitmap *hb, uint64_t item);
>  
>  /**
> + * hbitmap_data_size:
> + * @hb: HBitmap to operate on.
> + * @count: Number of bits
> + *
> + * Grunularity of serialization chunks, used by other serializetion functions.
> + * For every chunk:
> + * 1. Chunk start should be aligned to this granularity.
> + * 2. Chunk size should be aligned too, except for last chunk (for which
> + *      start + count == hb->size)
> + */

Whoops, this is the documentation for the function below. Looks like you
updated this one instead of the one adjacent to the prototype, too.

> +uint64_t hbitmap_serialization_granularity(const HBitmap *hb);
> +
> +/**
> + * hbitmap_data_size:
> + * @hb: HBitmap to operate on.
> + * @count: Number of bits
> + *
> + * Return amount of bytes hbitmap_(de)serialize_part needs
> + */
> +uint64_t hbitmap_serialization_size(const HBitmap *hb,
> +                                    uint64_t start, uint64_t count);
> +
> +/**
> + * hbitmap_serialize_part
> + * @hb: HBitmap to operate 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
> + */

I suppose that the buffer needs to be pre-allocated and "count/8" bytes
long; but rather specifically it needs to be hbitmap_serialization_size
bytes long, probably. Worth mentioning in the notes for @count since
we're already writing docs?

> +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.
> + * @finish: Whether to call hbitmap_deserialize_finish automatically.
> + *
> + * Restores HBitmap data corresponding to given region. The format is the same
> + * as for hbitmap_serialize_part.
> + *
> + * if @finish is false, caller must call hbitmap_serialize_finish before using
> + * the bitmap.
> + */
> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
> +                              uint64_t start, uint64_t count,
> +                              bool finish);
> +
> +/**
> + * hbitmap_deserialize_zeroes
> + * @hb: HBitmap to operate on.
> + * @start: First bit to restore.
> + * @count: Number of bits to restore.
> + * @finish: Whether to call hbitmap_deserialize_finish automatically.
> + *
> + * Same as hbitmap_serialize_part, but fills the bitmap with zeroes.
> + */

Fills the bitmap with zeroes?

> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
> +                                bool finish);
> +
> +/**
> + * 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 55d3182..ab8cd81 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -397,6 +397,142 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
>      return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
>  }
>  
> +uint64_t hbitmap_serialization_granularity(const HBitmap *hb)
> +{
> +    return BITS_PER_LONG << hb->granularity;
> +}
> +
> +/* serilization chunk start should be aligned to serialization granularity.
> + * Serilization chunk size scould be aligned to serialization granularity too,
> + * except for last chunk.
> + */

SeriAlization misspelled at the beginning of both lines. (missing the 'a')

> +static void serialization_chunk(const HBitmap *hb,
> +                                uint64_t start, uint64_t count,
> +                                unsigned long **first_el, size_t *el_count)
> +{
> +    uint64_t last = start + count - 1;
> +    uint64_t gran = hbitmap_serialization_granularity(hb);
> +
> +    assert(((start + count - 1) >> hb->granularity) < hb->size);
> +    assert((start & (gran - 1)) == 0);
> +    if ((last >> hb->granularity) != hb->size - 1) {
> +        assert((count & (gran - 1)) == 0);
> +    }
> +
> +    start = (start >> hb->granularity) >> BITS_PER_LEVEL;
> +    last = (last >> hb->granularity) >> BITS_PER_LEVEL;
> +
> +    *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
> +    *el_count = last - start + 1;
> +}
> +
> +uint64_t hbitmap_serialization_size(const HBitmap *hb,
> +                                    uint64_t start, uint64_t count)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur;
> +
> +    if (!count) {
> +        return 0;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);

Seems like a waste just to get the size.

> +
> +    return el_count * sizeof(unsigned long);
> +}
> +
> +void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
> +                            uint64_t start, uint64_t count)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur, *end;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);
> +    end = cur + el_count;
> +
> +    while (cur != end) {
> +        unsigned long el =
> +            (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
> +
> +        memcpy(buf, &el, sizeof(el));
> +        buf += sizeof(el);
> +        cur++;
> +    }
> +}
> +
> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
> +                              uint64_t start, uint64_t count,
> +                              bool finish)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur, *end;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);
> +    end = cur + el_count;
> +
> +    while (cur != end) {
> +        memcpy(cur, buf, sizeof(*cur));
> +
> +        if (BITS_PER_LONG == 32) {
> +            cpu_to_le32s((uint32_t *)cur);
> +        } else {
> +            cpu_to_le64s((uint64_t *)cur);
> +        }
> +
> +        buf += sizeof(unsigned long);
> +        cur++;
> +    }
> +    if (finish) {
> +        hbitmap_deserialize_finish(hb);
> +    }
> +}
> +
> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
> +                                bool finish)
> +{
> +    uint64_t el_count;
> +    unsigned long *first;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &first, &el_count);
> +

I guess this is just to get the el_count, primarily, because we just
bowl over it just below.

Shouldn't this just use the serialization size function up above, anyway?

> +    memset(first, 0, el_count * sizeof(unsigned long));
> +    if (finish) {
> +        hbitmap_deserialize_finish(hb);
> +    }
> +}
> +
> +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] |=
> +                    1UL << (i & (BITS_PER_LONG - 1));
> +            }
> +        }
> +    }
> +
> +    bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
> +}
> +
>  void hbitmap_free(HBitmap *hb)
>  {
>      unsigned i;
>

On 04.01.2016 13:27, Fam Zheng wrote:
> From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>
> 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@virtuozzo.com>
> [Fix left shift operand to 1UL; add "finish" parameter. - Fam]
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>   include/qemu/hbitmap.h |  76 +++++++++++++++++++++++++++
>   util/hbitmap.c         | 136 +++++++++++++++++++++++++++++++++++++++++++++++++
>   2 files changed, 212 insertions(+)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index ed672e7..3414113 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -149,6 +149,82 @@ void hbitmap_reset_all(HBitmap *hb);
>   bool hbitmap_get(const HBitmap *hb, uint64_t item);
>   
>   /**
> + * hbitmap_data_size:
> + * @hb: HBitmap to operate on.
> + * @count: Number of bits
> + *
> + * Grunularity of serialization chunks, used by other serializetion functions.
> + * For every chunk:
> + * 1. Chunk start should be aligned to this granularity.
> + * 2. Chunk size should be aligned too, except for last chunk (for which
> + *      start + count == hb->size)
> + */
> +uint64_t hbitmap_serialization_granularity(const HBitmap *hb);
> +
> +/**
> + * hbitmap_data_size:
> + * @hb: HBitmap to operate on.
> + * @count: Number of bits
> + *
> + * Return amount of bytes hbitmap_(de)serialize_part needs
> + */
> +uint64_t hbitmap_serialization_size(const HBitmap *hb,
> +                                    uint64_t start, uint64_t count);
> +
> +/**
> + * hbitmap_serialize_part
> + * @hb: HBitmap to operate 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.
> + * @finish: Whether to call hbitmap_deserialize_finish automatically.
> + *
> + * Restores HBitmap data corresponding to given region. The format is the same
> + * as for hbitmap_serialize_part.
> + *
> + * if @finish is false, caller must call hbitmap_serialize_finish before using
> + * the bitmap.
> + */
> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
> +                              uint64_t start, uint64_t count,
> +                              bool finish);
> +
> +/**
> + * hbitmap_deserialize_zeroes
> + * @hb: HBitmap to operate on.
> + * @start: First bit to restore.
> + * @count: Number of bits to restore.
> + * @finish: Whether to call hbitmap_deserialize_finish automatically.
> + *
> + * Same as hbitmap_serialize_part, but fills the bitmap with zeroes.
> + */
> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
> +                                bool finish);
> +
> +/**
> + * 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 55d3182..ab8cd81 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -397,6 +397,142 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
>       return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
>   }
>   
> +uint64_t hbitmap_serialization_granularity(const HBitmap *hb)
> +{
> +    return BITS_PER_LONG << hb->granularity;
> +}
> +
> +/* serilization chunk start should be aligned to serialization granularity.
> + * Serilization chunk size scould be aligned to serialization granularity too,
> + * except for last chunk.
> + */
> +static void serialization_chunk(const HBitmap *hb,
> +                                uint64_t start, uint64_t count,
> +                                unsigned long **first_el, size_t *el_count)
> +{
> +    uint64_t last = start + count - 1;
> +    uint64_t gran = hbitmap_serialization_granularity(hb);
> +
> +    assert(((start + count - 1) >> hb->granularity) < hb->size);

'last' may be used instead of '(start + count - 1)', and it is better to 
swap this line with the next line, to be closer with the similar bound 
checking.

> +    assert((start & (gran - 1)) == 0);
> +    if ((last >> hb->granularity) != hb->size - 1) {
> +        assert((count & (gran - 1)) == 0);
> +    }
> +
> +    start = (start >> hb->granularity) >> BITS_PER_LEVEL;
> +    last = (last >> hb->granularity) >> BITS_PER_LEVEL;
> +
> +    *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
> +    *el_count = last - start + 1;
> +}
> +
> +uint64_t hbitmap_serialization_size(const HBitmap *hb,
> +                                    uint64_t start, uint64_t count)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur;
> +
> +    if (!count) {
> +        return 0;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);
> +
> +    return el_count * sizeof(unsigned long);
> +}
> +
> +void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
> +                            uint64_t start, uint64_t count)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur, *end;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);
> +    end = cur + el_count;
> +
> +    while (cur != end) {
> +        unsigned long el =
> +            (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
> +
> +        memcpy(buf, &el, sizeof(el));
> +        buf += sizeof(el);
> +        cur++;
> +    }
> +}
> +
> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
> +                              uint64_t start, uint64_t count,
> +                              bool finish)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur, *end;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);
> +    end = cur + el_count;
> +
> +    while (cur != end) {
> +        memcpy(cur, buf, sizeof(*cur));
> +
> +        if (BITS_PER_LONG == 32) {
> +            cpu_to_le32s((uint32_t *)cur);
> +        } else {
> +            cpu_to_le64s((uint64_t *)cur);

le32_to_cpus and le64_to_cpus should be here. Really it doesn't matter, 
but sounds better for DEserialization.

> +        }
> +
> +        buf += sizeof(unsigned long);
> +        cur++;
> +    }
> +    if (finish) {
> +        hbitmap_deserialize_finish(hb);
> +    }
> +}
> +
> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
> +                                bool finish)
> +{
> +    uint64_t el_count;
> +    unsigned long *first;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &first, &el_count);
> +
> +    memset(first, 0, el_count * sizeof(unsigned long));
> +    if (finish) {
> +        hbitmap_deserialize_finish(hb);
> +    }
> +}
> +
> +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] |=
> +                    1UL << (i & (BITS_PER_LONG - 1));
> +            }
> +        }
> +    }
> +
> +    bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
> +}
> +
>   void hbitmap_free(HBitmap *hb)
>   {
>       unsigned i;

On 08.01.2016 00:11, John Snow wrote:
>
> On 01/04/2016 05:27 AM, Fam Zheng wrote:
>> From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>
>> 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@virtuozzo.com>
>> [Fix left shift operand to 1UL; add "finish" parameter. - Fam]
>> Signed-off-by: Fam Zheng <famz@redhat.com>
>> ---
>>   include/qemu/hbitmap.h |  76 +++++++++++++++++++++++++++
>>   util/hbitmap.c         | 136 +++++++++++++++++++++++++++++++++++++++++++++++++
>>   2 files changed, 212 insertions(+)
>>
>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>> index ed672e7..3414113 100644
>> --- a/include/qemu/hbitmap.h
>> +++ b/include/qemu/hbitmap.h
>> @@ -149,6 +149,82 @@ void hbitmap_reset_all(HBitmap *hb);
>>   bool hbitmap_get(const HBitmap *hb, uint64_t item);
>>   
>>   /**
>> + * hbitmap_data_size:
>> + * @hb: HBitmap to operate on.
>> + * @count: Number of bits
>> + *
>> + * Grunularity of serialization chunks, used by other serializetion functions.
>> + * For every chunk:
>> + * 1. Chunk start should be aligned to this granularity.
>> + * 2. Chunk size should be aligned too, except for last chunk (for which
>> + *      start + count == hb->size)
>> + */
> Whoops, this is the documentation for the function below. Looks like you
> updated this one instead of the one adjacent to the prototype, too.

yes.. delete @count line and 
s/hbitmap_data_size/hbitmap_serialization_granularity

>
>> +uint64_t hbitmap_serialization_granularity(const HBitmap *hb);
>> +
>> +/**
>> + * hbitmap_data_size:
>> + * @hb: HBitmap to operate on.
>> + * @count: Number of bits
>> + *
>> + * Return amount of bytes hbitmap_(de)serialize_part needs
>> + */
>> +uint64_t hbitmap_serialization_size(const HBitmap *hb,
>> +                                    uint64_t start, uint64_t count);
>> +
>> +/**
>> + * hbitmap_serialize_part
>> + * @hb: HBitmap to operate 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
>> + */
> I suppose that the buffer needs to be pre-allocated and "count/8" bytes
> long; but rather specifically it needs to be hbitmap_serialization_size
> bytes long, probably. Worth mentioning in the notes for @count since
> we're already writing docs?

Here @count is number of virtual bits. count is in the same dimension as 
start, as for all other public functions. An amount of real bits to be 
saved is ~ count/granularity.

>
>> +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.
>> + * @finish: Whether to call hbitmap_deserialize_finish automatically.
>> + *
>> + * Restores HBitmap data corresponding to given region. The format is the same
>> + * as for hbitmap_serialize_part.
>> + *
>> + * if @finish is false, caller must call hbitmap_serialize_finish before using
>> + * the bitmap.
>> + */
>> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
>> +                              uint64_t start, uint64_t count,
>> +                              bool finish);
>> +
>> +/**
>> + * hbitmap_deserialize_zeroes
>> + * @hb: HBitmap to operate on.
>> + * @start: First bit to restore.
>> + * @count: Number of bits to restore.
>> + * @finish: Whether to call hbitmap_deserialize_finish automatically.
>> + *
>> + * Same as hbitmap_serialize_part, but fills the bitmap with zeroes.
>> + */
> Fills the bitmap with zeroes?


with finish=1 - yes. with finish=0 - only fills the last level of the 
bitmap, and should be used among other deserialize calls with finish=0.


>
>> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
>> +                                bool finish);
>> +
>> +/**
>> + * 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 55d3182..ab8cd81 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -397,6 +397,142 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
>>       return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
>>   }
>>   
>> +uint64_t hbitmap_serialization_granularity(const HBitmap *hb)
>> +{
>> +    return BITS_PER_LONG << hb->granularity;
>> +}
>> +
>> +/* serilization chunk start should be aligned to serialization granularity.
>> + * Serilization chunk size scould be aligned to serialization granularity too,
>> + * except for last chunk.
>> + */
> SeriAlization misspelled at the beginning of both lines. (missing the 'a')
>
>> +static void serialization_chunk(const HBitmap *hb,
>> +                                uint64_t start, uint64_t count,
>> +                                unsigned long **first_el, size_t *el_count)
>> +{
>> +    uint64_t last = start + count - 1;
>> +    uint64_t gran = hbitmap_serialization_granularity(hb);
>> +
>> +    assert(((start + count - 1) >> hb->granularity) < hb->size);
>> +    assert((start & (gran - 1)) == 0);
>> +    if ((last >> hb->granularity) != hb->size - 1) {
>> +        assert((count & (gran - 1)) == 0);
>> +    }
>> +
>> +    start = (start >> hb->granularity) >> BITS_PER_LEVEL;
>> +    last = (last >> hb->granularity) >> BITS_PER_LEVEL;
>> +
>> +    *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
>> +    *el_count = last - start + 1;
>> +}
>> +
>> +uint64_t hbitmap_serialization_size(const HBitmap *hb,
>> +                                    uint64_t start, uint64_t count)
>> +{
>> +    uint64_t el_count;
>> +    unsigned long *cur;
>> +
>> +    if (!count) {
>> +        return 0;
>> +    }
>> +    serialization_chunk(hb, start, count, &cur, &el_count);
> Seems like a waste just to get the size.

and check all asserts. If we will provide direct access to chunk 
serialization to extern mechanisms (qmp), asserts should be replaced 
with normal error handling.

'cur' is useless here... NULL can be used instead of it with appropriate 
hanges in serialization_chunk, but I don't thing that this is necessary.

>
>> +
>> +    return el_count * sizeof(unsigned long);
>> +}
>> +
>> +void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
>> +                            uint64_t start, uint64_t count)
>> +{
>> +    uint64_t el_count;
>> +    unsigned long *cur, *end;
>> +
>> +    if (!count) {
>> +        return;
>> +    }
>> +    serialization_chunk(hb, start, count, &cur, &el_count);
>> +    end = cur + el_count;
>> +
>> +    while (cur != end) {
>> +        unsigned long el =
>> +            (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
>> +
>> +        memcpy(buf, &el, sizeof(el));
>> +        buf += sizeof(el);
>> +        cur++;
>> +    }
>> +}
>> +
>> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
>> +                              uint64_t start, uint64_t count,
>> +                              bool finish)
>> +{
>> +    uint64_t el_count;
>> +    unsigned long *cur, *end;
>> +
>> +    if (!count) {
>> +        return;
>> +    }
>> +    serialization_chunk(hb, start, count, &cur, &el_count);
>> +    end = cur + el_count;
>> +
>> +    while (cur != end) {
>> +        memcpy(cur, buf, sizeof(*cur));
>> +
>> +        if (BITS_PER_LONG == 32) {
>> +            cpu_to_le32s((uint32_t *)cur);
>> +        } else {
>> +            cpu_to_le64s((uint64_t *)cur);
>> +        }
>> +
>> +        buf += sizeof(unsigned long);
>> +        cur++;
>> +    }
>> +    if (finish) {
>> +        hbitmap_deserialize_finish(hb);
>> +    }
>> +}
>> +
>> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
>> +                                bool finish)
>> +{
>> +    uint64_t el_count;
>> +    unsigned long *first;
>> +
>> +    if (!count) {
>> +        return;
>> +    }
>> +    serialization_chunk(hb, start, count, &first, &el_count);
>> +
> I guess this is just to get the el_count, primarily, because we just
> bowl over it just below.

first is used too.

>
> Shouldn't this just use the serialization size function up above, anyway?
>
>> +    memset(first, 0, el_count * sizeof(unsigned long));
>> +    if (finish) {
>> +        hbitmap_deserialize_finish(hb);
>> +    }
>> +}
>> +
>> +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] |=
>> +                    1UL << (i & (BITS_PER_LONG - 1));
>> +            }
>> +        }
>> +    }
>> +
>> +    bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
>> +}
>> +
>>   void hbitmap_free(HBitmap *hb)
>>   {
>>       unsigned i;
>>

On 04.01.2016 13:27, Fam Zheng wrote:
> From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>
> 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@virtuozzo.com>
> [Fix left shift operand to 1UL; add "finish" parameter. - Fam]
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>   include/qemu/hbitmap.h |  76 +++++++++++++++++++++++++++
>   util/hbitmap.c         | 136 +++++++++++++++++++++++++++++++++++++++++++++++++
>   2 files changed, 212 insertions(+)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index ed672e7..3414113 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -149,6 +149,82 @@ void hbitmap_reset_all(HBitmap *hb);
>   bool hbitmap_get(const HBitmap *hb, uint64_t item);
>   
>   /**
> + * hbitmap_data_size:
> + * @hb: HBitmap to operate on.
> + * @count: Number of bits
> + *
> + * Grunularity of serialization chunks, used by other serializetion functions.
> + * For every chunk:
> + * 1. Chunk start should be aligned to this granularity.
> + * 2. Chunk size should be aligned too, except for last chunk (for which
> + *      start + count == hb->size)
> + */
> +uint64_t hbitmap_serialization_granularity(const HBitmap *hb);
> +
> +/**
> + * hbitmap_data_size:
> + * @hb: HBitmap to operate on.
> + * @count: Number of bits
> + *
> + * Return amount of bytes hbitmap_(de)serialize_part needs
> + */
> +uint64_t hbitmap_serialization_size(const HBitmap *hb,
> +                                    uint64_t start, uint64_t count);
> +
> +/**
> + * hbitmap_serialize_part
> + * @hb: HBitmap to operate 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.
> + * @finish: Whether to call hbitmap_deserialize_finish automatically.
> + *
> + * Restores HBitmap data corresponding to given region. The format is the same
> + * as for hbitmap_serialize_part.
> + *
> + * if @finish is false, caller must call hbitmap_serialize_finish before using
> + * the bitmap.
> + */
> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
> +                              uint64_t start, uint64_t count,
> +                              bool finish);
> +
> +/**
> + * hbitmap_deserialize_zeroes
> + * @hb: HBitmap to operate on.
> + * @start: First bit to restore.
> + * @count: Number of bits to restore.
> + * @finish: Whether to call hbitmap_deserialize_finish automatically.
> + *
> + * Same as hbitmap_serialize_part, but fills the bitmap with zeroes.
> + */
> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
> +                                bool finish);
> +
> +/**
> + * 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 55d3182..ab8cd81 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -397,6 +397,142 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
>       return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
>   }
>   
> +uint64_t hbitmap_serialization_granularity(const HBitmap *hb)
> +{
> +    return BITS_PER_LONG << hb->granularity;

Isn't it bad, that granularity depends on long size? If we serialize on 
32bit machine and deserialize on 64bit one.. This should be carefully 
handled. May be, it is easier to replace it with "64 << 
hb->granularity", to be the same on different machines (for same bitmap, 
of course)

> +}
> +
> +/* serilization chunk start should be aligned to serialization granularity.
> + * Serilization chunk size scould be aligned to serialization granularity too,
> + * except for last chunk.
> + */
> +static void serialization_chunk(const HBitmap *hb,
> +                                uint64_t start, uint64_t count,
> +                                unsigned long **first_el, size_t *el_count)
> +{
> +    uint64_t last = start + count - 1;
> +    uint64_t gran = hbitmap_serialization_granularity(hb);
> +
> +    assert(((start + count - 1) >> hb->granularity) < hb->size);
> +    assert((start & (gran - 1)) == 0);
> +    if ((last >> hb->granularity) != hb->size - 1) {
> +        assert((count & (gran - 1)) == 0);
> +    }
> +
> +    start = (start >> hb->granularity) >> BITS_PER_LEVEL;
> +    last = (last >> hb->granularity) >> BITS_PER_LEVEL;
> +
> +    *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
> +    *el_count = last - start + 1;
> +}
> +
> +uint64_t hbitmap_serialization_size(const HBitmap *hb,
> +                                    uint64_t start, uint64_t count)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur;
> +
> +    if (!count) {
> +        return 0;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);
> +
> +    return el_count * sizeof(unsigned long);
> +}
> +
> +void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
> +                            uint64_t start, uint64_t count)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur, *end;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);
> +    end = cur + el_count;
> +
> +    while (cur != end) {
> +        unsigned long el =
> +            (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
> +
> +        memcpy(buf, &el, sizeof(el));
> +        buf += sizeof(el);
> +        cur++;
> +    }
> +}
> +
> +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
> +                              uint64_t start, uint64_t count,
> +                              bool finish)
> +{
> +    uint64_t el_count;
> +    unsigned long *cur, *end;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &cur, &el_count);
> +    end = cur + el_count;
> +
> +    while (cur != end) {
> +        memcpy(cur, buf, sizeof(*cur));
> +
> +        if (BITS_PER_LONG == 32) {
> +            cpu_to_le32s((uint32_t *)cur);
> +        } else {
> +            cpu_to_le64s((uint64_t *)cur);
> +        }
> +
> +        buf += sizeof(unsigned long);
> +        cur++;
> +    }
> +    if (finish) {
> +        hbitmap_deserialize_finish(hb);
> +    }
> +}
> +
> +void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
> +                                bool finish)
> +{
> +    uint64_t el_count;
> +    unsigned long *first;
> +
> +    if (!count) {
> +        return;
> +    }
> +    serialization_chunk(hb, start, count, &first, &el_count);
> +
> +    memset(first, 0, el_count * sizeof(unsigned long));
> +    if (finish) {
> +        hbitmap_deserialize_finish(hb);
> +    }
> +}
> +
> +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] |=
> +                    1UL << (i & (BITS_PER_LONG - 1));
> +            }
> +        }
> +    }
> +
> +    bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
> +}
> +
>   void hbitmap_free(HBitmap *hb)
>   {
>       unsigned i;