On 01/04/2016 05:27 AM, Fam Zheng wrote:
> From: Vladimir Sementsov-Ogievskiy <vsement...@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 <vsement...@virtuozzo.com>
> [Fix left shift operand to 1UL; add "finish" parameter. - Fam]
> Signed-off-by: Fam Zheng <f...@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;
>
