Add functions for load/store HBitmap to BDS, using clusters table:
Last level of the bitmap is splitted into chunks of 'cluster_size'
size. Each cell of the table contains offset in bds, to load/store
corresponding chunk.
Also,
0 in cell means all-zeroes-chunk (should not be saved)
1 in cell means all-ones-chunk (should not be saved)
hbitmap_prepare_store() fills table with
0 for all-zeroes chunks
1 for all-ones chunks
2 for others
Signed-off-by: Vladimir Sementsov-Ogievskiy <address@hidden>
---
block/dirty-bitmap.c | 23 +++++
include/block/dirty-bitmap.h | 11 +++
include/qemu/hbitmap.h | 12 +++
util/hbitmap.c | 209 +++++++++++++++++++++++++++++++++++++++++++
4 files changed, 255 insertions(+)
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index e68c177..816c6ee 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -396,3 +396,26 @@ int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
{
return hbitmap_count(bitmap->bitmap);
}
+
+int bdrv_dirty_bitmap_load(BdrvDirtyBitmap *bitmap, BlockDriverState *bs,
+ const uint64_t *table, uint32_t table_size,
+ uint32_t cluster_size)
+{
+ return hbitmap_load(bitmap->bitmap, bs, table, table_size, cluster_size);
+}
+
+int bdrv_dirty_bitmap_prepare_store(const BdrvDirtyBitmap *bitmap,
+ uint32_t cluster_size,
+ uint64_t *table,
+ uint32_t *table_size)
+{
+ return hbitmap_prepare_store(bitmap->bitmap, cluster_size,
+ table, table_size);
+}
+
+int bdrv_dirty_bitmap_store(const BdrvDirtyBitmap *bitmap, BlockDriverState
*bs,
+ const uint64_t *table, uint32_t table_size,
+ uint32_t cluster_size)
+{
+ return hbitmap_store(bitmap->bitmap, bs, table, table_size, cluster_size);
+}
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 27515af..20cb540 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -43,4 +43,15 @@ void bdrv_set_dirty_iter(struct HBitmapIter *hbi, int64_t
offset);
int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
+int bdrv_dirty_bitmap_load(BdrvDirtyBitmap *bitmap, BlockDriverState *bs,
+ const uint64_t *table, uint32_t table_size,
+ uint32_t cluster_size);
+int bdrv_dirty_bitmap_prepare_store(const BdrvDirtyBitmap *bitmap,
+ uint32_t cluster_size,
+ uint64_t *table,
+ uint32_t *table_size);
+int bdrv_dirty_bitmap_store(const BdrvDirtyBitmap *bitmap, BlockDriverState
*bs,
+ const uint64_t *table, uint32_t table_size,
+ uint32_t cluster_size);
+
#endif
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index 6d1da4d..d83bb79 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -241,5 +241,17 @@ static inline size_t hbitmap_iter_next_word(HBitmapIter
*hbi, unsigned long *p_c
return hbi->pos;
}
+typedef struct BlockDriverState BlockDriverState;
+
+int hbitmap_load(HBitmap *bitmap, BlockDriverState *bs,
+ const uint64_t *table, uint32_t table_size,
+ uint32_t cluster_size);
+
+int hbitmap_prepare_store(const HBitmap *bitmap, uint32_t cluster_size,
+ uint64_t *table, uint32_t *table_size);
+
+int hbitmap_store(HBitmap *bitmap, BlockDriverState *bs,
+ const uint64_t *table, uint32_t table_size,
+ uint32_t cluster_size);
#endif
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 28595fb..1960e4f 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -15,6 +15,8 @@
#include "qemu/host-utils.h"
#include "trace.h"
+#include "block/block.h"
+
/* HBitmaps provides an array of bits. The bits are stored as usual in an
* array of unsigned longs, but HBitmap is also optimized to provide fast
* iteration over set bits; going from one bit to the next is O(logB n)
@@ -499,3 +501,210 @@ char *hbitmap_md5(const HBitmap *bitmap)
const guchar *data = (const guchar *)bitmap->levels[HBITMAP_LEVELS - 1];
return g_compute_checksum_for_data(G_CHECKSUM_MD5, data, size);
}
+
+/* hb_restore_levels()
+ * Using the last level restore all other levels
+ */
+static void hb_restore_levels(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);
+}
+
+/* load_bitmap()
+ * Load dirty bitmap from file, using table with cluster offsets.
+ * Table entries are assumed to be in little endian format.
+ */
+int hbitmap_load(HBitmap *bitmap, BlockDriverState *bs,
+ const uint64_t *table, uint32_t table_size,
+ uint32_t cluster_size)
+{
+ uint32_t i;
+ uint8_t *cur = (uint8_t *)bitmap->levels[HBITMAP_LEVELS - 1];
+ uint8_t *end = cur + ((bitmap->size + 7) >> 3);
+
+ hbitmap_reset_all(bitmap);
+
+ for (i = 0; i < table_size && cur < end; ++i) {
+ uint64_t offset = table[i];
+ uint64_t count = MIN(cluster_size, end - cur);
+
+ /* Zero offset means zero region, offset = 1 means filled region.
+ * Cluster is not allocated in both cases. */
+ if (offset == 1) {
+ memset(cur, 0xff, count);
+ } else if (offset) {
+ int ret = bdrv_pread(bs, offset, cur, count);
+ if (ret < 0) {
+ return ret;
+ }
+ }
+
+ cur += cluster_size;
+ }
+
+ cur = (uint8_t *)bitmap->levels[HBITMAP_LEVELS - 1];
+ while (cur < end) {
+ if (BITS_PER_LONG == 32) {
+ le32_to_cpus((uint32_t *)cur);
+ } else {
+ le64_to_cpus((uint64_t *)cur);
+ }
+
+ cur += sizeof(unsigned long);
+ }
+
+ hb_restore_levels(bitmap);
+
+ return 0;
+}
+
+static bool buffer_is_all_ones(void *buf, size_t len)
+{
+ /* FIXME */
+ return false;
+}
+
+/* hbitmap_prepare_store()
+ * Devide bitmap data into clusters, and then,
+ * for zero cluster: table[i] = 0
+ * for all-ones cluster: table[i] = 1
+ * for other clusters: table[i] = 2
+ */
+int hbitmap_prepare_store(const HBitmap *bitmap,
+ uint32_t cluster_size,
+ uint64_t *table,
+ uint32_t *table_size)
+{
+ HBitmapIter hbi;
+ hbitmap_iter_init(&hbi, bitmap, 0);
+ uint64_t nb_bits_in_cl = (uint64_t)cluster_size << 3;
+ uint32_t need_table_size =
+ (bitmap->size + nb_bits_in_cl - 1) / nb_bits_in_cl;
+
+ if (table == NULL && *table_size == 0) {
+ *table_size = need_table_size;
+ return 0;
+ }
+
+ if (*table_size < need_table_size) {
+ return -ENOMEM;
+ }
+
+ memset(table, 0, *table_size * sizeof(table[0]));
+
+ for (;;) {
+ unsigned long cur;
+ size_t pos = hbitmap_iter_next_word(&hbi, &cur);
+ size_t byte = pos * sizeof(unsigned long);
+ uint64_t bit = byte << 3;
+ uint64_t nbits = MIN(cluster_size << 3, bitmap->size - bit), next_bit;
+ size_t i = byte / cluster_size;
+
+ if (pos == -1) {
+ break;
+ }
+
+ if (pos % cluster_size != 0) {
+ table[i] = 2;
+ } else if (buffer_is_all_ones(&bitmap->levels[HBITMAP_LEVELS - 1][pos],
+ nbits >> 3)) {
+ table[i] = 1;
+ if (nbits & 7) {
+ uint8_t last_byte =
+ *(((uint8_t *)&bitmap->levels[HBITMAP_LEVELS - 1][pos])
+ + (nbits >> 3));
+ if (last_byte != ((1 << (nbits & 7)) - 1)) {
+ table[i] = 2;
+ }
+ }
+ } else {
+ table[i] = 2;
+ }
+
+ next_bit = (i + 1) * cluster_size << 3;
+
+ if (next_bit >= bitmap->size) {
+ break;
+ }
+
+ hbitmap_iter_init(&hbi, bitmap, next_bit << bitmap->granularity);
+ }
+
+ return 0;
+}
+
+static void longs_to_le(unsigned long *longs, size_t count)
+{
+ unsigned long *end = longs + count;
+ while (longs < end) {
+ if (BITS_PER_LONG == 32) {
+ cpu_to_le32s((uint32_t *)longs);
+ } else {
+ cpu_to_le64s((uint64_t *)longs);
+ }
+
+ longs++;
+ }
+}
+
+/* store_bitmap()
+ * update bitmap table by storing bitmap to it.
+ * bitmap table entries are assumed to be in big endian format
+ * On the error, the resulting bitmap table is valid for clearing, but
+ * may contain invalid bitmap */
+int hbitmap_store(HBitmap *bitmap, BlockDriverState *bs,
+ const uint64_t *table, uint32_t table_size,
+ uint32_t cluster_size)
+{
+ int i;
+ uint8_t *cur = (uint8_t *)bitmap->levels[HBITMAP_LEVELS - 1];
+ uint8_t *end = cur +
+ ((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL) *
(sizeof(long));
+
+ for (i = 0; i < table_size && cur < end; ++i) {
+ uint64_t offset = table[i];
+ uint64_t count = MIN(cluster_size, end - cur);
+
+ /* Zero offset means zero region, offset = 1 means filled region.
+ * Cluster is not allocated in both cases. */
+ if (offset > 1) {
+ int ret;
+ if (cpu_to_le16(1) == 1) {
+ ret = bdrv_pwrite(bs, offset, cur, count);