| Message ID | 1453270306-16608-12-git-send-email-famz@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
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; >
On Tue, 01/26 12:01, John Snow wrote: > > > 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? OK, I'll add a comment here. > > 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? Yes.
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. + * 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. + * + * 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; +} + +/* 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); + } + + 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) { + 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); + } +} + +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;