[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PULL 19/23] hbitmap: serialization
From: |
Kevin Wolf |
Subject: |
[Qemu-devel] [PULL 19/23] hbitmap: serialization |
Date: |
Mon, 24 Oct 2016 19:02:07 +0200 |
From: Vladimir Sementsov-Ogievskiy <address@hidden>
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 <address@hidden>
[Fix left shift operand to 1UL; add "finish" parameter. - Fam]
Signed-off-by: Fam Zheng <address@hidden>
Signed-off-by: John Snow <address@hidden>
Message-id: address@hidden
Signed-off-by: Max Reitz <address@hidden>
---
include/qemu/hbitmap.h | 79 ++++++++++++++++++++++++++++
util/hbitmap.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 216 insertions(+)
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index 1725919..eb46475 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -146,6 +146,85 @@ void hbitmap_reset_all(HBitmap *hb);
bool hbitmap_get(const HBitmap *hb, uint64_t item);
/**
+ * hbitmap_serialization_granularity:
+ * @hb: HBitmap to operate on.
+ *
+ * Granularity of serialization chunks, used by other serialization 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_serialization_size:
+ * @hb: HBitmap to operate on.
+ * @start: Starting bit
+ * @count: Number of bits
+ *
+ * Return number 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 f303975..5d1a21c 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -397,6 +397,143 @@ 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)
+{
+ /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit
+ * hosts. */
+ 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, uint64_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;
--
1.8.3.1
- [Qemu-devel] [PULL 10/23] iotests: Do not rely on unavailable domains in 162, (continued)
- [Qemu-devel] [PULL 10/23] iotests: Do not rely on unavailable domains in 162, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 03/23] block: Remove "options" indirection from blockdev-add, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 08/23] qemu-nbd: Add --fork option, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 13/23] block: Hide HBitmap in block dirty bitmap interface, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 17/23] block: Add two dirty bitmap getters, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 06/23] throttle: Correct access to wrong BlockBackendPublic structures, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 15/23] tests: Add test code for meta bitmap, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 07/23] qemu-iotests: Test I/O in a single drive from a throttling group, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 16/23] block: Support meta dirty bitmap, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 18/23] block: Assert that bdrv_release_dirty_bitmap succeeded, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 19/23] hbitmap: serialization,
Kevin Wolf <=
- [Qemu-devel] [PULL 11/23] quorum: change child_iter to children_read, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 12/23] quorum: do not allocate multiple iovecs for FIFO strategy, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 14/23] HBitmap: Introduce "meta" bitmap to track bit changes, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 22/23] block: More operations for meta dirty bitmap, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 21/23] tests: Add test code for hbitmap serialization, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 20/23] block: BdrvDirtyBitmap serialization interface, Kevin Wolf, 2016/10/24
- [Qemu-devel] [PULL 23/23] block/replication: Clarify 'top-id' parameter usage, Kevin Wolf, 2016/10/24
- Re: [Qemu-devel] [PULL 00/23] Block layer patches, Peter Maydell, 2016/10/24
- [Qemu-devel] [PULL 00/23] Block layer patches, Kevin Wolf, 2016/10/27