Re: [Qemu-devel] [PATCH v2 11/13] hbitmap: serialization

[John Snow <jsnow@redhat.com>]

On 01/20/2016 01:11 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 |  78 ++++++++++++++++++++++++++++
>  util/hbitmap.c         | 135 +++++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 213 insertions(+)
> 
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index 595ad65..00dbb60 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -149,6 +149,84 @@ void hbitmap_reset_all(HBitmap *hb);
>  bool hbitmap_get(const HBitmap *hb, uint64_t item);
>  
>  /**
> + * hbitmap_serialization_granularity:
> + * @hb: HBitmap to operate on.
> + *
> + * Grunularity of serialization chunks, used by other serializetion functions.

"Granularity," "serialization."

Perhaps we should be consistent with "hbitmap" vs "HBitmap" as well, too.

> + * 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
> + */

"number of bytes" -- amount is for uncountable nouns (like "water.")

> +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.
> + *
> + * Fills the bitmap with zeroes.
> + *
> + * If @finish is false, caller must call hbitmap_serialize_finish before using
> + * the bitmap.
> + */
> +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 79f6236..1e49ab7 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -397,6 +397,141 @@ 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 64 << hb->granularity;
> +}
> +

Sorry, about to be confused about what this function is meant to do,
please bear with me:

Normally the granularity specifies the mapping of "interface" bits to
"implementation" bits. I've never came up with good terminology for
this, but if the user asks for 128 bits and a granularity of 2, we
secretly only allocate 32 bits.

So "virtually" we have 128, and "physically" we have 32.

What is this function giving us? for the size=128,g=2 example above this
gives us (64 << 2 == 256), which I guess is the number of "virtual" bits
represented by each physical uint64_t.

64 bits, each bit represents 2^g==2^2==4 bits, so 256 bits total for a
uint64_t.

If I'm right, perhaps just a brief comment to help me remember it in the
future?

Further: this function does not appear to be used for any reason other
than making sure the alignment is correct, so it appears that:

- On a 64bit host, an el is 64 bits and we will serialize like that
- On a 32bit host, an el is 32 bits and we'll serialize in multiples of
32 bits
- After transfer, though, the destination host may deserialize assuming
either 32bit or 64bit elements -- hence aligning to 64bits is the safest
bet.

Correct?

> +/* Start should be aligned to serialization granularity, chunk size should 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 & (gran - 1)) == 0);
> +    assert((last >> hb->granularity) < hb->size);
> +    if ((last >> hb->granularity) != hb->size - 1) {
> +        assert((count & (gran - 1)) == 0);
> +    }
> +

So we're just asserting that the serialization chunk we're doing aligns
well to a uint64_t boundary, right? and otherwise we're instantiating
"first_el" and "el_count" with information about the chunk to serialize...

(I assume first_el means "first element.")

> +    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);
> +}
> +

Documentation says "hbitmap_data_size," but the function has been named
hbitmap_serialization_size.

Documentation only mentions @hb and @count, but not @start. (Though it's
obvious, it's still weird.)

> +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) {
> +            le32_to_cpus((uint32_t *)cur);
> +        } else {
> +            le64_to_cpus((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);
> +    }
> +}
> +

I still find this concept funny, since we're not really deserializing
anything :)

The function is fine though, of course.

> +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;
>