[Qemu-devel] [PATCH 2/8] hbitmap: store / restore

[Vladimir Sementsov-Ogievskiy <vsementsov@parallels.com>]

Functions to store / restore HBitmap. HBitmap should be saved to linear
bitmap format independently of endianess.

These functions are appropriate for dirty bitmap migration, retoring 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_restore_finish as a last step of restoring. So, HBitmap is
inconsistent while restoring.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@parallels.com>
---
 include/qemu/hbitmap.h | 49 ++++++++++++++++++++++++++++
 util/hbitmap.c         | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 136 insertions(+)

diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index c48c50a..f432f7f 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -137,6 +137,55 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
 bool hbitmap_get(const HBitmap *hb, uint64_t item);
 
 /**
+ * hbitmap_data_size:
+ * @hb: HBitmap to operate on.
+ * @count: Number of bits
+ *
+ * Return amount of bytes hbitmap_store_data needs
+ */
+uint64_t hbitmap_data_size(const HBitmap *hb, uint64_t count);
+
+/**
+ * hbitmap_store_data
+ * @hb: HBitmap to oprate on.
+ * @buf: Buffer to store bitmap data.
+ * @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_restore_data
+ * independently of endianess
+ */
+void hbitmap_store_data(const HBitmap *hb, uint8_t *buf,
+                        uint64_t start, uint64_t count);
+
+/**
+ * hbitmap_restore_data
+ * @hb: HBitmap to oprate on.
+ * @buf: Buffer to restore bitmap data from.
+ * @start: First bit to restore.
+ * @count: Number of bits to restore.
+ *
+ * Retores HBitmap data corresponding to given region. The format is the same
+ * as for hbitmap_store_data.
+ *
+ * ! The bitmap becomes inconsistent after this operation.
+ * hbitmap_restore_finish should be called before using the bitmap after
+ * data restoring.
+ */
+void hbitmap_restore_data(HBitmap *hb, uint8_t *buf,
+                          uint64_t start, uint64_t count);
+
+/**
+ * hbitmap_restore_finish
+ * @hb: HBitmap to operate on.
+ *
+ * Repair HBitmap after calling hbitmap_restore_data. Actuall all HBitmap
+ * layers are restore here.
+ */
+void hbitmap_restore_finish(HBitmap *hb);
+
+/**
  * hbitmap_free:
  * @hb: HBitmap to operate on.
  *
diff --git a/util/hbitmap.c b/util/hbitmap.c
index f400dcb..5d1a776 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -366,6 +366,93 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
     return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
 }
 
+uint64_t hbitmap_data_size(const HBitmap *hb, uint64_t count)
+{
+    uint64_t size;
+
+    if (count == 0) {
+        return 0;
+    }
+
+    size = (((count - 1) >> hb->granularity) >> BITS_PER_LEVEL) + 1;
+
+    return size * sizeof(unsigned long);
+}
+
+void hbitmap_store_data(const HBitmap *hb, uint8_t *buf,
+                        uint64_t start, uint64_t count)
+{
+    uint64_t last = start + count - 1;
+    unsigned long *out = (unsigned long *)buf;
+
+    if (count == 0) {
+        return;
+    }
+
+    start = (start >> hb->granularity) >> BITS_PER_LEVEL;
+    last = (last >> hb->granularity) >> BITS_PER_LEVEL;
+    count = last - start + 1;
+
+#ifdef __BIG_ENDIAN_BITFIELD
+    for (i = start; i <= last; ++i) {
+        unsigned long el = hb->levels[HBITMAP_LEVELS - 1][i];
+        out[i] = (BITS_PER_LONG == 32 ? cpu_to_le32(el) : cpu_to_le64(el));
+    }
+#else
+    memcpy(out, &hb->levels[HBITMAP_LEVELS - 1][start],
+           count * sizeof(unsigned long));
+#endif
+}
+
+void hbitmap_restore_data(HBitmap *hb, uint8_t *buf,
+                          uint64_t start, uint64_t count)
+{
+    uint64_t last = start + count - 1;
+    unsigned long *in = (unsigned long *)buf;
+
+    if (count == 0) {
+        return;
+    }
+
+    start = (start >> hb->granularity) >> BITS_PER_LEVEL;
+    last = (last >> hb->granularity) >> BITS_PER_LEVEL;
+    count = last - start + 1;
+
+#ifdef __BIG_ENDIAN_BITFIELD
+    for (i = start; i <= last; ++i) {
+        hb->levels[HBITMAP_LEVELS - 1][i] =
+            (BITS_PER_LONG == 32 ? be32_to_cpu(in[i]) : be64_to_cpu(in[i]));
+    }
+#else
+    memcpy(&hb->levels[HBITMAP_LEVELS - 1][start], in,
+           count * sizeof(unsigned long));
+#endif
+}
+
+void hbitmap_restore_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] |=
+                    1 << (i & (BITS_PER_LONG - 1));
+            }
+        }
+    }
+
+    bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
+}
+
 void hbitmap_free(HBitmap *hb)
 {
     unsigned i;
-- 
1.9.1