[Qemu-devel] [PATCH v5 00/10] Dirty bitmap changes for migration/persistence work

[Qemu-devel] [PATCH v5 00/10] Dirty bitmap changes for migration/persistence work

[Fam Zheng]

v5: Rebase: first 5 patches from last revision are already merged.

    Addressed Max's comments:

    01: - "block.c" -> "block/dirty-bitmap.c" in commit message.
        - "an BdrvDirtyBitmapIter" -> "an BdrvDirtyBitmapIter" in code comment.
        - hbitmap_next => next_dirty as variable name.
        - bdrv_dirty_iter_free()/bdrv_dirty_iter_new() pairs =>
          bdrv_set_dirty_iter.

    02: Move the assert fix into 01.

    04: Truncate the meta bitmap (done by hbitmap_truncate).

    06: Add Max's r-b.

    07: I left the memcpy vs cpu_to_le32/64w as is to pick up Max's r-b. That
        could be improved on top if wanted.

    10: Add Max's r-b.

Fam Zheng (8):
  block: Hide HBitmap in block dirty bitmap interface
  HBitmap: Introduce "meta" bitmap to track bit changes
  tests: Add test code for meta bitmap
  block: Support meta dirty bitmap
  block: Add two dirty bitmap getters
  block: Assert that bdrv_release_dirty_bitmap succeeded
  tests: Add test code for hbitmap serialization
  block: More operations for meta dirty bitmap

Vladimir Sementsov-Ogievskiy (2):
  hbitmap: serialization
  block: BdrvDirtyBitmap serialization interface

 block/backup.c               |  14 ++-
 block/dirty-bitmap.c         | 160 ++++++++++++++++++++++++++-
 block/mirror.c               |  24 ++--
 include/block/dirty-bitmap.h |  35 +++++-
 include/qemu/hbitmap.h       |  96 ++++++++++++++++
 include/qemu/typedefs.h      |   1 +
 tests/test-hbitmap.c         | 255 +++++++++++++++++++++++++++++++++++++++++++
 util/hbitmap.c               | 206 +++++++++++++++++++++++++++++++---
 8 files changed, 751 insertions(+), 40 deletions(-)

-- 
2.8.2

[Qemu-devel] [PATCH v5 01/10] block: Hide HBitmap in block dirty bitmap interface

[Fam Zheng]

HBitmap is an implementation detail of block dirty bitmap that should be hidden
from users. Introduce a BdrvDirtyBitmapIter to encapsulate the underlying
HBitmapIter.

A small difference in the interface is, before, an HBitmapIter is initialized
in place, now the new BdrvDirtyBitmapIter must be dynamically allocated because
the structure definition is in block/dirty-bitmap.c.

Two current users are converted too.

Signed-off-by: Fam Zheng <famz@redhat.com>
---
 block/backup.c               | 14 ++++++++------
 block/dirty-bitmap.c         | 39 +++++++++++++++++++++++++++++++++------
 block/mirror.c               | 24 +++++++++++++-----------
 include/block/dirty-bitmap.h |  7 +++++--
 include/qemu/typedefs.h      |  1 +
 5 files changed, 60 insertions(+), 25 deletions(-)

diff --git a/block/backup.c b/block/backup.c
index feeb9f8..ac7ca45 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -317,14 +317,14 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
     int64_t end;
     int64_t last_cluster = -1;
     int64_t sectors_per_cluster = cluster_size_sectors(job);
-    HBitmapIter hbi;
+    BdrvDirtyBitmapIter *dbi;
 
     granularity = bdrv_dirty_bitmap_granularity(job->sync_bitmap);
     clusters_per_iter = MAX((granularity / job->cluster_size), 1);
-    bdrv_dirty_iter_init(job->sync_bitmap, &hbi);
+    dbi = bdrv_dirty_iter_new(job->sync_bitmap, 0);
 
     /* Find the next dirty sector(s) */
-    while ((sector = hbitmap_iter_next(&hbi)) != -1) {
+    while ((sector = bdrv_dirty_iter_next(dbi)) != -1) {
         cluster = sector / sectors_per_cluster;
 
         /* Fake progress updates for any clusters we skipped */
@@ -336,7 +336,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
         for (end = cluster + clusters_per_iter; cluster < end; cluster++) {
             do {
                 if (yield_and_check(job)) {
-                    return ret;
+                    goto out;
                 }
                 ret = backup_do_cow(job, cluster * sectors_per_cluster,
                                     sectors_per_cluster, &error_is_read,
@@ -344,7 +344,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
                 if ((ret < 0) &&
                     backup_error_action(job, error_is_read, -ret) ==
                     BLOCK_ERROR_ACTION_REPORT) {
-                    return ret;
+                    goto out;
                 }
             } while (ret < 0);
         }
@@ -352,7 +352,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
         /* If the bitmap granularity is smaller than the backup granularity,
          * we need to advance the iterator pointer to the next cluster. */
         if (granularity < job->cluster_size) {
-            bdrv_set_dirty_iter(&hbi, cluster * sectors_per_cluster);
+            bdrv_set_dirty_iter(dbi, cluster * sectors_per_cluster);
         }
 
         last_cluster = cluster - 1;
@@ -364,6 +364,8 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
         job->common.offset += ((end - last_cluster - 1) * job->cluster_size);
     }
 
+out:
+    bdrv_dirty_iter_free(dbi);
     return ret;
 }
 
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 4902ca5..ec073ee 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -42,9 +42,15 @@ struct BdrvDirtyBitmap {
     char *name;                 /* Optional non-empty unique ID */
     int64_t size;               /* Size of the bitmap (Number of sectors) */
     bool disabled;              /* Bitmap is read-only */
+    int active_iterators;       /* How many iterators are active */
     QLIST_ENTRY(BdrvDirtyBitmap) list;
 };
 
+struct BdrvDirtyBitmapIter {
+    HBitmapIter hbi;
+    BdrvDirtyBitmap *bitmap;
+};
+
 BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs, const char *name)
 {
     BdrvDirtyBitmap *bm;
@@ -212,6 +218,7 @@ void bdrv_dirty_bitmap_truncate(BlockDriverState *bs)
 
     QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
         assert(!bdrv_dirty_bitmap_frozen(bitmap));
+        assert(!bitmap->active_iterators);
         hbitmap_truncate(bitmap->bitmap, size);
         bitmap->size = size;
     }
@@ -224,6 +231,7 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
     BdrvDirtyBitmap *bm, *next;
     QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
         if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
+            assert(!bitmap->active_iterators);
             assert(!bdrv_dirty_bitmap_frozen(bm));
             QLIST_REMOVE(bm, list);
             hbitmap_free(bm->bitmap);
@@ -320,9 +328,29 @@ uint32_t bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap)
     return BDRV_SECTOR_SIZE << hbitmap_granularity(bitmap->bitmap);
 }
 
-void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, HBitmapIter *hbi)
+BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
+                                         uint64_t first_sector)
 {
-    hbitmap_iter_init(hbi, bitmap->bitmap, 0);
+    BdrvDirtyBitmapIter *iter = g_new(BdrvDirtyBitmapIter, 1);
+    hbitmap_iter_init(&iter->hbi, bitmap->bitmap, first_sector);
+    iter->bitmap = bitmap;
+    bitmap->active_iterators++;
+    return iter;
+}
+
+void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
+{
+    if (!iter) {
+        return;
+    }
+    assert(iter->bitmap->active_iterators > 0);
+    iter->bitmap->active_iterators--;
+    g_free(iter);
+}
+
+int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
+{
+    return hbitmap_iter_next(&iter->hbi);
 }
 
 void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
@@ -373,12 +401,11 @@ void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
 }
 
 /**
- * Advance an HBitmapIter to an arbitrary offset.
+ * Advance a BdrvDirtyBitmapIter to an arbitrary offset.
  */
-void bdrv_set_dirty_iter(HBitmapIter *hbi, int64_t offset)
+void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *iter, int64_t sector_num)
 {
-    assert(hbi->hb);
-    hbitmap_iter_init(hbi, hbi->hb, offset);
+    hbitmap_iter_init(&iter->hbi, iter->hbi.hb, sector_num);
 }
 
 int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
diff --git a/block/mirror.c b/block/mirror.c
index 80fd3c7..1d90aa5 100644
--- a/block/mirror.c
+++ b/block/mirror.c
@@ -52,7 +52,7 @@ typedef struct MirrorBlockJob {
     int64_t bdev_length;
     unsigned long *cow_bitmap;
     BdrvDirtyBitmap *dirty_bitmap;
-    HBitmapIter hbi;
+    BdrvDirtyBitmapIter *dbi;
     uint8_t *buf;
     QSIMPLEQ_HEAD(, MirrorBuffer) buf_free;
     int buf_free_count;
@@ -317,10 +317,10 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
     int64_t end = s->bdev_length / BDRV_SECTOR_SIZE;
     int sectors_per_chunk = s->granularity >> BDRV_SECTOR_BITS;
 
-    sector_num = hbitmap_iter_next(&s->hbi);
+    sector_num = bdrv_dirty_iter_next(s->dbi);
     if (sector_num < 0) {
-        bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
-        sector_num = hbitmap_iter_next(&s->hbi);
+        bdrv_set_dirty_iter(s->dbi, 0);
+        sector_num = bdrv_dirty_iter_next(s->dbi);
         trace_mirror_restart_iter(s, bdrv_get_dirty_count(s->dirty_bitmap));
         assert(sector_num >= 0);
     }
@@ -334,7 +334,7 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
     /* Find the number of consective dirty chunks following the first dirty
      * one, and wait for in flight requests in them. */
     while (nb_chunks * sectors_per_chunk < (s->buf_size >> BDRV_SECTOR_BITS)) {
-        int64_t hbitmap_next;
+        int64_t next_dirty;
         int64_t next_sector = sector_num + nb_chunks * sectors_per_chunk;
         int64_t next_chunk = next_sector / sectors_per_chunk;
         if (next_sector >= end ||
@@ -345,13 +345,13 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
             break;
         }
 
-        hbitmap_next = hbitmap_iter_next(&s->hbi);
-        if (hbitmap_next > next_sector || hbitmap_next < 0) {
+        next_dirty = bdrv_dirty_iter_next(s->dbi);
+        if (next_dirty > next_sector || next_dirty < 0) {
             /* The bitmap iterator's cache is stale, refresh it */
-            bdrv_set_dirty_iter(&s->hbi, next_sector);
-            hbitmap_next = hbitmap_iter_next(&s->hbi);
+            bdrv_set_dirty_iter(s->dbi, next_sector);
+            next_dirty = bdrv_dirty_iter_next(s->dbi);
         }
-        assert(hbitmap_next == next_sector);
+        assert(next_dirty == next_sector);
         nb_chunks++;
     }
 
@@ -601,7 +601,8 @@ static void coroutine_fn mirror_run(void *opaque)
         }
     }
 
-    bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
+    assert(!s->dbi);
+    s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
     for (;;) {
         uint64_t delay_ns = 0;
         int64_t cnt;
@@ -712,6 +713,7 @@ immediate_exit:
     qemu_vfree(s->buf);
     g_free(s->cow_bitmap);
     g_free(s->in_flight_bitmap);
+    bdrv_dirty_iter_free(s->dbi);
     bdrv_release_dirty_bitmap(bs, s->dirty_bitmap);
 
     data = g_malloc(sizeof(*data));
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 80afe60..2ea601b 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -36,8 +36,11 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
                            int64_t cur_sector, int nr_sectors);
 void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
                              int64_t cur_sector, int nr_sectors);
-void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, struct HBitmapIter *hbi);
-void bdrv_set_dirty_iter(struct HBitmapIter *hbi, int64_t offset);
+BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
+                                         uint64_t first_sector);
+void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
+int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
+void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t sector_num);
 int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
 void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
 
diff --git a/include/qemu/typedefs.h b/include/qemu/typedefs.h
index b113fcf..1b8c30a 100644
--- a/include/qemu/typedefs.h
+++ b/include/qemu/typedefs.h
@@ -11,6 +11,7 @@ typedef struct AioContext AioContext;
 typedef struct AllwinnerAHCIState AllwinnerAHCIState;
 typedef struct AudioState AudioState;
 typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
+typedef struct BdrvDirtyBitmapIter BdrvDirtyBitmapIter;
 typedef struct BlockBackend BlockBackend;
 typedef struct BlockBackendRootState BlockBackendRootState;
 typedef struct BlockDriverState BlockDriverState;
-- 
2.8.2

[Qemu-devel] [PATCH v5 02/10] HBitmap: Introduce "meta" bitmap to track bit changes

[Fam Zheng]

Upon each bit toggle, the corresponding bit in the meta bitmap will be
set.

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 block/dirty-bitmap.c   |  2 +-
 include/qemu/hbitmap.h | 17 +++++++++++++
 util/hbitmap.c         | 69 +++++++++++++++++++++++++++++++++++++++-----------
 3 files changed, 72 insertions(+), 16 deletions(-)

diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index ec073ee..628b77c 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -231,7 +231,7 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
     BdrvDirtyBitmap *bm, *next;
     QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
         if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
-            assert(!bitmap->active_iterators);
+            assert(!bm->active_iterators);
             assert(!bdrv_dirty_bitmap_frozen(bm));
             QLIST_REMOVE(bm, list);
             hbitmap_free(bm->bitmap);
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index e29188c..f8ed058 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -178,6 +178,23 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
  */
 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
 
+/* hbitmap_create_meta:
+ * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
+ * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
+ * free it.
+ *
+ * @hb: The HBitmap to operate on.
+ * @chunk_size: How many bits in @hb does one bit in the meta track.
+ */
+HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size);
+
+/* hbitmap_free_meta:
+ * Free the meta bitmap of @hb.
+ *
+ * @hb: The HBitmap whose meta bitmap should be freed.
+ */
+void hbitmap_free_meta(HBitmap *hb);
+
 /**
  * hbitmap_iter_next:
  * @hbi: HBitmapIter to operate on.
diff --git a/util/hbitmap.c b/util/hbitmap.c
index b22b87d..13c0df5 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -79,6 +79,9 @@ struct HBitmap {
      */
     int granularity;
 
+    /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */
+    HBitmap *meta;
+
     /* A number of progressively less coarse bitmaps (i.e. level 0 is the
      * coarsest).  Each bit in level N represents a word in level N+1 that
      * has a set bit, except the last level where each bit represents the
@@ -210,25 +213,27 @@ static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
 }
 
 /* Setting starts at the last layer and propagates up if an element
- * changes from zero to non-zero.
+ * changes.
  */
 static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
 {
     unsigned long mask;
-    bool changed;
+    unsigned long old;
 
     assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
     assert(start <= last);
 
     mask = 2UL << (last & (BITS_PER_LONG - 1));
     mask -= 1UL << (start & (BITS_PER_LONG - 1));
-    changed = (*elem == 0);
+    old = *elem;
     *elem |= mask;
-    return changed;
+    return old != *elem;
 }
 
-/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
-static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last)
+/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
+ * Returns true if at least one bit is changed. */
+static bool hb_set_between(HBitmap *hb, int level, uint64_t start,
+                           uint64_t last)
 {
     size_t pos = start >> BITS_PER_LEVEL;
     size_t lastpos = last >> BITS_PER_LEVEL;
@@ -257,22 +262,27 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
     if (level > 0 && changed) {
         hb_set_between(hb, level - 1, pos, lastpos);
     }
+    return changed;
 }
 
 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
 {
     /* Compute range in the last layer.  */
+    uint64_t first, n;
     uint64_t last = start + count - 1;
 
     trace_hbitmap_set(hb, start, count,
                       start >> hb->granularity, last >> hb->granularity);
 
-    start >>= hb->granularity;
+    first = start >> hb->granularity;
     last >>= hb->granularity;
-    count = last - start + 1;
+    n = last - first + 1;
 
-    hb->count += count - hb_count_between(hb, start, last);
-    hb_set_between(hb, HBITMAP_LEVELS - 1, start, last);
+    hb->count += n - hb_count_between(hb, first, last);
+    if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&
+        hb->meta) {
+        hbitmap_set(hb->meta, start, count);
+    }
 }
 
 /* Resetting works the other way round: propagate up if the new
@@ -293,8 +303,10 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
     return blanked;
 }
 
-/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
-static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t last)
+/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
+ * Returns true if at least one bit is changed. */
+static bool hb_reset_between(HBitmap *hb, int level, uint64_t start,
+                             uint64_t last)
 {
     size_t pos = start >> BITS_PER_LEVEL;
     size_t lastpos = last >> BITS_PER_LEVEL;
@@ -337,21 +349,28 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
     if (level > 0 && changed) {
         hb_reset_between(hb, level - 1, pos, lastpos);
     }
+
+    return changed;
+
 }
 
 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
 {
     /* Compute range in the last layer.  */
+    uint64_t first;
     uint64_t last = start + count - 1;
 
     trace_hbitmap_reset(hb, start, count,
                         start >> hb->granularity, last >> hb->granularity);
 
-    start >>= hb->granularity;
+    first = start >> hb->granularity;
     last >>= hb->granularity;
 
-    hb->count -= hb_count_between(hb, start, last);
-    hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
+    hb->count -= hb_count_between(hb, first, last);
+    if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
+        hb->meta) {
+        hbitmap_set(hb->meta, start, count);
+    }
 }
 
 void hbitmap_reset_all(HBitmap *hb)
@@ -379,6 +398,7 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
 void hbitmap_free(HBitmap *hb)
 {
     unsigned i;
+    assert(!hb->meta);
     for (i = HBITMAP_LEVELS; i-- > 0; ) {
         g_free(hb->levels[i]);
     }
@@ -456,6 +476,9 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
                    (size - old) * sizeof(*hb->levels[i]));
         }
     }
+    if (hb->meta) {
+        hbitmap_truncate(hb->meta, hb->size << hb->granularity);
+    }
 }
 
 
@@ -491,3 +514,19 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
 
     return true;
 }
+
+HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size)
+{
+    assert(!(chunk_size & (chunk_size - 1)));
+    assert(!hb->meta);
+    hb->meta = hbitmap_alloc(hb->size << hb->granularity,
+                             hb->granularity + ctz32(chunk_size));
+    return hb->meta;
+}
+
+void hbitmap_free_meta(HBitmap *hb)
+{
+    assert(hb->meta);
+    hbitmap_free(hb->meta);
+    hb->meta = NULL;
+}
-- 
2.8.2

[Qemu-devel] [PATCH v5 03/10] tests: Add test code for meta bitmap

[Fam Zheng]

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 tests/test-hbitmap.c | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 116 insertions(+)

diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index abe1427..c00c2b5 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -12,6 +12,7 @@
 #include "qemu/osdep.h"
 #include <glib.h>
 #include "qemu/hbitmap.h"
+#include "block/block.h"
 
 #define LOG_BITS_PER_LONG          (BITS_PER_LONG == 32 ? 5 : 6)
 
@@ -21,6 +22,7 @@
 
 typedef struct TestHBitmapData {
     HBitmap       *hb;
+    HBitmap       *meta;
     unsigned long *bits;
     size_t         size;
     size_t         old_size;
@@ -92,6 +94,14 @@ static void hbitmap_test_init(TestHBitmapData *data,
     }
 }
 
+static void hbitmap_test_init_meta(TestHBitmapData *data,
+                                   uint64_t size, int granularity,
+                                   int meta_chunk)
+{
+    hbitmap_test_init(data, size, granularity);
+    data->meta = hbitmap_create_meta(data->hb, meta_chunk);
+}
+
 static inline size_t hbitmap_test_array_size(size_t bits)
 {
     size_t n = (bits + BITS_PER_LONG - 1) / BITS_PER_LONG;
@@ -134,6 +144,9 @@ static void hbitmap_test_teardown(TestHBitmapData *data,
                                   const void *unused)
 {
     if (data->hb) {
+        if (data->meta) {
+            hbitmap_free_meta(data->hb);
+        }
         hbitmap_free(data->hb);
         data->hb = NULL;
     }
@@ -635,6 +648,103 @@ static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
     hbitmap_test_truncate(data, size, -diff, 0);
 }
 
+static void hbitmap_check_meta(TestHBitmapData *data,
+                               int64_t start, int count)
+{
+    int64_t i;
+
+    for (i = 0; i < data->size; i++) {
+        if (i >= start && i < start + count) {
+            g_assert(hbitmap_get(data->meta, i));
+        } else {
+            g_assert(!hbitmap_get(data->meta, i));
+        }
+    }
+}
+
+static void hbitmap_test_meta(TestHBitmapData *data,
+                              int64_t start, int count,
+                              int64_t check_start, int check_count)
+{
+    hbitmap_reset_all(data->hb);
+    hbitmap_reset_all(data->meta);
+
+    /* Test "unset" -> "unset" will not update meta. */
+    hbitmap_reset(data->hb, start, count);
+    hbitmap_check_meta(data, 0, 0);
+
+    /* Test "unset" -> "set" will update meta */
+    hbitmap_set(data->hb, start, count);
+    hbitmap_check_meta(data, check_start, check_count);
+
+    /* Test "set" -> "set" will not update meta */
+    hbitmap_reset_all(data->meta);
+    hbitmap_set(data->hb, start, count);
+    hbitmap_check_meta(data, 0, 0);
+
+    /* Test "set" -> "unset" will update meta */
+    hbitmap_reset_all(data->meta);
+    hbitmap_reset(data->hb, start, count);
+    hbitmap_check_meta(data, check_start, check_count);
+}
+
+static void hbitmap_test_meta_do(TestHBitmapData *data, int chunk_size)
+{
+    uint64_t size = chunk_size * 100;
+    hbitmap_test_init_meta(data, size, 0, chunk_size);
+
+    hbitmap_test_meta(data, 0, 1, 0, chunk_size);
+    hbitmap_test_meta(data, 0, chunk_size, 0, chunk_size);
+    hbitmap_test_meta(data, chunk_size - 1, 1, 0, chunk_size);
+    hbitmap_test_meta(data, chunk_size - 1, 2, 0, chunk_size * 2);
+    hbitmap_test_meta(data, chunk_size - 1, chunk_size + 1, 0, chunk_size * 2);
+    hbitmap_test_meta(data, chunk_size - 1, chunk_size + 2, 0, chunk_size * 3);
+    hbitmap_test_meta(data, 7 * chunk_size - 1, chunk_size + 2,
+                      6 * chunk_size, chunk_size * 3);
+    hbitmap_test_meta(data, size - 1, 1, size - chunk_size, chunk_size);
+    hbitmap_test_meta(data, 0, size, 0, size);
+}
+
+static void test_hbitmap_meta_byte(TestHBitmapData *data, const void *unused)
+{
+    hbitmap_test_meta_do(data, BITS_PER_BYTE);
+}
+
+static void test_hbitmap_meta_word(TestHBitmapData *data, const void *unused)
+{
+    hbitmap_test_meta_do(data, BITS_PER_LONG);
+}
+
+static void test_hbitmap_meta_sector(TestHBitmapData *data, const void *unused)
+{
+    hbitmap_test_meta_do(data, BDRV_SECTOR_SIZE * BITS_PER_BYTE);
+}
+
+/**
+ * Create an HBitmap and test set/unset.
+ */
+static void test_hbitmap_meta_one(TestHBitmapData *data, const void *unused)
+{
+    int i;
+    int64_t offsets[] = {
+        0, 1, L1 - 1, L1, L1 + 1, L2 - 1, L2, L2 + 1, L3 - 1, L3, L3 + 1
+    };
+
+    hbitmap_test_init_meta(data, L3 * 2, 0, 1);
+    for (i = 0; i < ARRAY_SIZE(offsets); i++) {
+        hbitmap_test_meta(data, offsets[i], 1, offsets[i], 1);
+        hbitmap_test_meta(data, offsets[i], L1, offsets[i], L1);
+        hbitmap_test_meta(data, offsets[i], L2, offsets[i], L2);
+    }
+}
+
+static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused)
+{
+    hbitmap_test_init_meta(data, 0, 0, 1);
+
+    hbitmap_check_meta(data, 0, 0);
+}
+
 static void hbitmap_test_add(const char *testpath,
                                    void (*test_func)(TestHBitmapData *data, const void *user_data))
 {
@@ -684,6 +794,12 @@ int main(int argc, char **argv)
                      test_hbitmap_truncate_grow_large);
     hbitmap_test_add("/hbitmap/truncate/shrink/large",
                      test_hbitmap_truncate_shrink_large);
+
+    hbitmap_test_add("/hbitmap/meta/zero", test_hbitmap_meta_zero);
+    hbitmap_test_add("/hbitmap/meta/one", test_hbitmap_meta_one);
+    hbitmap_test_add("/hbitmap/meta/byte", test_hbitmap_meta_byte);
+    hbitmap_test_add("/hbitmap/meta/word", test_hbitmap_meta_word);
+    hbitmap_test_add("/hbitmap/meta/sector", test_hbitmap_meta_sector);
     g_test_run();
 
     return 0;
-- 
2.8.2

[Qemu-devel] [PATCH v5 04/10] block: Support meta dirty bitmap

[Fam Zheng]

The added group of operations enables tracking of the changed bits in
the dirty bitmap.

Signed-off-by: Fam Zheng <famz@redhat.com>
---
 block/dirty-bitmap.c         | 52 ++++++++++++++++++++++++++++++++++++++++++++
 include/block/dirty-bitmap.h |  9 ++++++++
 2 files changed, 61 insertions(+)

diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 628b77c..9c53c56 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -38,6 +38,7 @@
  */
 struct BdrvDirtyBitmap {
     HBitmap *bitmap;            /* Dirty sector bitmap implementation */
+    HBitmap *meta;              /* Meta dirty bitmap */
     BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
     char *name;                 /* Optional non-empty unique ID */
     int64_t size;               /* Size of the bitmap (Number of sectors) */
@@ -103,6 +104,56 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
     return bitmap;
 }
 
+/* bdrv_create_meta_dirty_bitmap
+ *
+ * Create a meta dirty bitmap that tracks the changes of bits in @bitmap. I.e.
+ * when a dirty status bit in @bitmap is changed (either from reset to set or
+ * the other way around), its respective meta dirty bitmap bit will be marked
+ * dirty as well.
+ *
+ * @bitmap: the block dirty bitmap for which to create a meta dirty bitmap.
+ * @chunk_size: how many bytes of bitmap data does each bit in the meta bitmap
+ * track.
+ */
+void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
+                                   int chunk_size)
+{
+    assert(!bitmap->meta);
+    bitmap->meta = hbitmap_create_meta(bitmap->bitmap,
+                                       chunk_size * BITS_PER_BYTE);
+}
+
+void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
+{
+    assert(bitmap->meta);
+    hbitmap_free_meta(bitmap->bitmap);
+    bitmap->meta = NULL;
+}
+
+int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
+                               BdrvDirtyBitmap *bitmap, int64_t sector,
+                               int nb_sectors)
+{
+    uint64_t i;
+    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
+
+    /* To optimize: we can make hbitmap to internally check the range in a
+     * coarse level, or at least do it word by word. */
+    for (i = sector; i < sector + nb_sectors; i += gran) {
+        if (hbitmap_get(bitmap->meta, i)) {
+            return true;
+        }
+    }
+    return false;
+}
+
+void bdrv_dirty_bitmap_reset_meta(BlockDriverState *bs,
+                                  BdrvDirtyBitmap *bitmap, int64_t sector,
+                                  int nb_sectors)
+{
+    hbitmap_reset(bitmap->meta, sector, nb_sectors);
+}
+
 bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap)
 {
     return bitmap->successor;
@@ -233,6 +284,7 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
         if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
             assert(!bm->active_iterators);
             assert(!bdrv_dirty_bitmap_frozen(bm));
+            assert(!bm->meta);
             QLIST_REMOVE(bm, list);
             hbitmap_free(bm->bitmap);
             g_free(bm->name);
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 2ea601b..50e0fca 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -8,6 +8,9 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
                                           uint32_t granularity,
                                           const char *name,
                                           Error **errp);
+void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
+                                   int chunk_size);
+void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap);
 int bdrv_dirty_bitmap_create_successor(BlockDriverState *bs,
                                        BdrvDirtyBitmap *bitmap,
                                        Error **errp);
@@ -36,6 +39,12 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
                            int64_t cur_sector, int nr_sectors);
 void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
                              int64_t cur_sector, int nr_sectors);
+int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
+                               BdrvDirtyBitmap *bitmap, int64_t sector,
+                               int nb_sectors);
+void bdrv_dirty_bitmap_reset_meta(BlockDriverState *bs,
+                                  BdrvDirtyBitmap *bitmap, int64_t sector,
+                                  int nb_sectors);
 BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
                                          uint64_t first_sector);
 void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
-- 
2.8.2

[Qemu-devel] [PATCH v5 05/10] block: Add two dirty bitmap getters

[Fam Zheng]

For dirty bitmap users to get the size and the name of a
BdrvDirtyBitmap.

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 block/dirty-bitmap.c         | 10 ++++++++++
 include/block/dirty-bitmap.h |  2 ++
 2 files changed, 12 insertions(+)

diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 9c53c56..a71c9b7 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -154,6 +154,16 @@ void bdrv_dirty_bitmap_reset_meta(BlockDriverState *bs,
     hbitmap_reset(bitmap->meta, sector, nb_sectors);
 }
 
+int64_t bdrv_dirty_bitmap_size(const BdrvDirtyBitmap *bitmap)
+{
+    return bitmap->size;
+}
+
+const char *bdrv_dirty_bitmap_name(const BdrvDirtyBitmap *bitmap)
+{
+    return bitmap->name;
+}
+
 bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap)
 {
     return bitmap->successor;
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 50e0fca..caa4d82 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -32,6 +32,8 @@ uint32_t bdrv_get_default_bitmap_granularity(BlockDriverState *bs);
 uint32_t bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap);
 bool bdrv_dirty_bitmap_enabled(BdrvDirtyBitmap *bitmap);
 bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap);
+const char *bdrv_dirty_bitmap_name(const BdrvDirtyBitmap *bitmap);
+int64_t bdrv_dirty_bitmap_size(const BdrvDirtyBitmap *bitmap);
 DirtyBitmapStatus bdrv_dirty_bitmap_status(BdrvDirtyBitmap *bitmap);
 int bdrv_get_dirty(BlockDriverState *bs, BdrvDirtyBitmap *bitmap,
                    int64_t sector);
-- 
2.8.2

[Qemu-devel] [PATCH v5 06/10] block: Assert that bdrv_release_dirty_bitmap succeeded

[Fam Zheng]

We use a loop over bs->dirty_bitmaps to make sure the caller is
only releasing a bitmap owned by bs. Let's also assert that in this case
the caller is releasing a bitmap that does exist.

Signed-off-by: Fam Zheng <famz@redhat.com>
---
 block/dirty-bitmap.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index a71c9b7..39e072a 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -305,6 +305,9 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
             }
         }
     }
+    if (bitmap) {
+        abort();
+    }
 }
 
 void bdrv_release_dirty_bitmap(BlockDriverState *bs, BdrvDirtyBitmap *bitmap)
-- 
2.8.2

[Qemu-devel] [PATCH v5 07/10] hbitmap: serialization

[Fam Zheng]

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>
Reviewed-by: Max Reitz <mreitz@redhat.com>
---
 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 f8ed058..26cac7d 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 13c0df5..70dc99b 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -395,6 +395,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, 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;
-- 
2.8.2

[Qemu-devel] [PATCH v5 08/10] block: BdrvDirtyBitmap serialization interface

[Fam Zheng]

From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>

Several functions to provide necessary access to BdrvDirtyBitmap for
block-migration.c

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
[Add the "finish" parameters. - Fam]
Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 block/dirty-bitmap.c         | 37 +++++++++++++++++++++++++++++++++++++
 include/block/dirty-bitmap.h | 14 ++++++++++++++
 2 files changed, 51 insertions(+)

diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 39e072a..8113090 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -453,6 +453,43 @@ void bdrv_undo_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap, HBitmap *in)
     hbitmap_free(tmp);
 }
 
+uint64_t bdrv_dirty_bitmap_serialization_size(const BdrvDirtyBitmap *bitmap,
+                                              uint64_t start, uint64_t count)
+{
+    return hbitmap_serialization_size(bitmap->bitmap, start, count);
+}
+
+uint64_t bdrv_dirty_bitmap_serialization_align(const BdrvDirtyBitmap *bitmap)
+{
+    return hbitmap_serialization_granularity(bitmap->bitmap);
+}
+
+void bdrv_dirty_bitmap_serialize_part(const BdrvDirtyBitmap *bitmap,
+                                      uint8_t *buf, uint64_t start,
+                                      uint64_t count)
+{
+    hbitmap_serialize_part(bitmap->bitmap, buf, start, count);
+}
+
+void bdrv_dirty_bitmap_deserialize_part(BdrvDirtyBitmap *bitmap,
+                                        uint8_t *buf, uint64_t start,
+                                        uint64_t count, bool finish)
+{
+    hbitmap_deserialize_part(bitmap->bitmap, buf, start, count, finish);
+}
+
+void bdrv_dirty_bitmap_deserialize_zeroes(BdrvDirtyBitmap *bitmap,
+                                          uint64_t start, uint64_t count,
+                                          bool finish)
+{
+    hbitmap_deserialize_zeroes(bitmap->bitmap, start, count, finish);
+}
+
+void bdrv_dirty_bitmap_deserialize_finish(BdrvDirtyBitmap *bitmap)
+{
+    hbitmap_deserialize_finish(bitmap->bitmap);
+}
+
 void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
                     int nr_sectors)
 {
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index caa4d82..40a09c0 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -55,4 +55,18 @@ void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t sector_num);
 int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
 void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
 
+uint64_t bdrv_dirty_bitmap_serialization_size(const BdrvDirtyBitmap *bitmap,
+                                              uint64_t start, uint64_t count);
+uint64_t bdrv_dirty_bitmap_serialization_align(const BdrvDirtyBitmap *bitmap);
+void bdrv_dirty_bitmap_serialize_part(const BdrvDirtyBitmap *bitmap,
+                                      uint8_t *buf, uint64_t start,
+                                      uint64_t count);
+void bdrv_dirty_bitmap_deserialize_part(BdrvDirtyBitmap *bitmap,
+                                        uint8_t *buf, uint64_t start,
+                                        uint64_t count, bool finish);
+void bdrv_dirty_bitmap_deserialize_zeroes(BdrvDirtyBitmap *bitmap,
+                                          uint64_t start, uint64_t count,
+                                          bool finish);
+void bdrv_dirty_bitmap_deserialize_finish(BdrvDirtyBitmap *bitmap);
+
 #endif
-- 
2.8.2

[Qemu-devel] [PATCH v5 09/10] tests: Add test code for hbitmap serialization

[Fam Zheng]

Acked-by: John Snow <jsnow@redhat.com>
Signed-off-by: Fam Zheng <famz@redhat.com>
---
 tests/test-hbitmap.c | 139 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 139 insertions(+)

diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index c00c2b5..8f64941 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -12,6 +12,7 @@
 #include "qemu/osdep.h"
 #include <glib.h>
 #include "qemu/hbitmap.h"
+#include "qemu/bitmap.h"
 #include "block/block.h"
 
 #define LOG_BITS_PER_LONG          (BITS_PER_LONG == 32 ? 5 : 6)
@@ -738,6 +739,16 @@ static void test_hbitmap_meta_one(TestHBitmapData *data, const void *unused)
     }
 }
 
+static void test_hbitmap_serialize_granularity(TestHBitmapData *data,
+                                               const void *unused)
+{
+    int r;
+
+    hbitmap_test_init(data, L3 * 2, 3);
+    r = hbitmap_serialization_granularity(data->hb);
+    g_assert_cmpint(r, ==, BITS_PER_LONG << 3);
+}
+
 static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused)
 {
     hbitmap_test_init_meta(data, 0, 0, 1);
@@ -745,6 +756,125 @@ static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused)
     hbitmap_check_meta(data, 0, 0);
 }
 
+static void hbitmap_test_serialize_range(TestHBitmapData *data,
+                                         uint8_t *buf, size_t buf_size,
+                                         uint64_t pos, uint64_t count)
+{
+    size_t i;
+
+    assert(hbitmap_granularity(data->hb) == 0);
+    hbitmap_reset_all(data->hb);
+    memset(buf, 0, buf_size);
+    if (count) {
+        hbitmap_set(data->hb, pos, count);
+    }
+    hbitmap_serialize_part(data->hb, buf, 0, data->size);
+    for (i = 0; i < data->size; i++) {
+        int is_set = test_bit(i, (unsigned long *)buf);
+        if (i >= pos && i < pos + count) {
+            g_assert(is_set);
+        } else {
+            g_assert(!is_set);
+        }
+    }
+    hbitmap_reset_all(data->hb);
+    hbitmap_deserialize_part(data->hb, buf, 0, data->size, true);
+
+    for (i = 0; i < data->size; i++) {
+        int is_set = hbitmap_get(data->hb, i);
+        if (i >= pos && i < pos + count) {
+            g_assert(is_set);
+        } else {
+            g_assert(!is_set);
+        }
+    }
+}
+
+static void test_hbitmap_serialize_basic(TestHBitmapData *data,
+                                         const void *unused)
+{
+    int i, j;
+    size_t buf_size;
+    uint8_t *buf;
+    uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
+    int num_positions = sizeof(positions) / sizeof(positions[0]);
+
+    hbitmap_test_init(data, L3, 0);
+    buf_size = hbitmap_serialization_size(data->hb, 0, data->size);
+    buf = g_malloc0(buf_size);
+
+    for (i = 0; i < num_positions; i++) {
+        for (j = 0; j < num_positions; j++) {
+            hbitmap_test_serialize_range(data, buf, buf_size,
+                                         positions[i],
+                                         MIN(positions[j], L3 - positions[i]));
+        }
+    }
+
+    g_free(buf);
+}
+
+static void test_hbitmap_serialize_part(TestHBitmapData *data,
+                                        const void *unused)
+{
+    int i, j, k;
+    size_t buf_size;
+    uint8_t *buf;
+    uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
+    int num_positions = sizeof(positions) / sizeof(positions[0]);
+
+    hbitmap_test_init(data, L3, 0);
+    buf_size = L2;
+    buf = g_malloc0(buf_size);
+
+    for (i = 0; i < num_positions; i++) {
+        hbitmap_set(data->hb, positions[i], 1);
+    }
+
+    for (i = 0; i < data->size; i += buf_size) {
+        hbitmap_serialize_part(data->hb, buf, i, buf_size);
+        for (j = 0; j < buf_size; j++) {
+            bool should_set = false;
+            for (k = 0; k < num_positions; k++) {
+                if (positions[k] == j + i) {
+                    should_set = true;
+                    break;
+                }
+            }
+            g_assert_cmpint(should_set, ==, test_bit(j, (unsigned long *)buf));
+        }
+    }
+
+    g_free(buf);
+}
+
+static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
+                                          const void *unused)
+{
+    int i;
+    HBitmapIter iter;
+    int64_t next;
+    uint64_t positions[] = { 0, L1, L2, L3 - L1};
+    int num_positions = sizeof(positions) / sizeof(positions[0]);
+
+    hbitmap_test_init(data, L3, 0);
+
+    for (i = 0; i < num_positions; i++) {
+        hbitmap_set(data->hb, positions[i], L1);
+    }
+
+    for (i = 0; i < num_positions; i++) {
+        hbitmap_deserialize_zeroes(data->hb, positions[i], L1, true);
+        hbitmap_iter_init(&iter, data->hb, 0);
+        next = hbitmap_iter_next(&iter);
+        if (i == num_positions - 1) {
+            g_assert_cmpint(next, ==, -1);
+        } else {
+            g_assert_cmpint(next, ==, positions[i + 1]);
+        }
+    }
+}
+
 static void hbitmap_test_add(const char *testpath,
                                    void (*test_func)(TestHBitmapData *data, const void *user_data))
 {
@@ -800,6 +930,15 @@ int main(int argc, char **argv)
     hbitmap_test_add("/hbitmap/meta/byte", test_hbitmap_meta_byte);
     hbitmap_test_add("/hbitmap/meta/word", test_hbitmap_meta_word);
     hbitmap_test_add("/hbitmap/meta/sector", test_hbitmap_meta_sector);
+
+    hbitmap_test_add("/hbitmap/serialize/granularity",
+                     test_hbitmap_serialize_granularity);
+    hbitmap_test_add("/hbitmap/serialize/basic",
+                     test_hbitmap_serialize_basic);
+    hbitmap_test_add("/hbitmap/serialize/part",
+                     test_hbitmap_serialize_part);
+    hbitmap_test_add("/hbitmap/serialize/zeroes",
+                     test_hbitmap_serialize_zeroes);
     g_test_run();
 
     return 0;
-- 
2.8.2

[Qemu-devel] [PATCH v5 10/10] block: More operations for meta dirty bitmap

[Fam Zheng]

Callers can create an iterator of meta bitmap with
bdrv_dirty_meta_iter_new(), then use the bdrv_dirty_iter_* operations on
it. Meta iterators are also counted by bitmap->active_iterators.

Also add a couple of functions to retrieve granularity and count.

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: Max Reitz <mreitz@redhat.com>
---
 block/dirty-bitmap.c         | 19 +++++++++++++++++++
 include/block/dirty-bitmap.h |  3 +++
 2 files changed, 22 insertions(+)

diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 8113090..d94de7b 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -393,6 +393,11 @@ uint32_t bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap)
     return BDRV_SECTOR_SIZE << hbitmap_granularity(bitmap->bitmap);
 }
 
+uint32_t bdrv_dirty_bitmap_meta_granularity(BdrvDirtyBitmap *bitmap)
+{
+    return BDRV_SECTOR_SIZE << hbitmap_granularity(bitmap->meta);
+}
+
 BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
                                          uint64_t first_sector)
 {
@@ -403,6 +408,15 @@ BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
     return iter;
 }
 
+BdrvDirtyBitmapIter *bdrv_dirty_meta_iter_new(BdrvDirtyBitmap *bitmap)
+{
+    BdrvDirtyBitmapIter *iter = g_new(BdrvDirtyBitmapIter, 1);
+    hbitmap_iter_init(&iter->hbi, bitmap->meta, 0);
+    iter->bitmap = bitmap;
+    bitmap->active_iterators++;
+    return iter;
+}
+
 void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
 {
     if (!iter) {
@@ -514,3 +528,8 @@ int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
 {
     return hbitmap_count(bitmap->bitmap);
 }
+
+int64_t bdrv_get_meta_dirty_count(BdrvDirtyBitmap *bitmap)
+{
+    return hbitmap_count(bitmap->meta);
+}
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 40a09c0..3cbed02 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -30,6 +30,7 @@ void bdrv_enable_dirty_bitmap(BdrvDirtyBitmap *bitmap);
 BlockDirtyInfoList *bdrv_query_dirty_bitmaps(BlockDriverState *bs);
 uint32_t bdrv_get_default_bitmap_granularity(BlockDriverState *bs);
 uint32_t bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap);
+uint32_t bdrv_dirty_bitmap_meta_granularity(BdrvDirtyBitmap *bitmap);
 bool bdrv_dirty_bitmap_enabled(BdrvDirtyBitmap *bitmap);
 bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap);
 const char *bdrv_dirty_bitmap_name(const BdrvDirtyBitmap *bitmap);
@@ -47,12 +48,14 @@ int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
 void bdrv_dirty_bitmap_reset_meta(BlockDriverState *bs,
                                   BdrvDirtyBitmap *bitmap, int64_t sector,
                                   int nb_sectors);
+BdrvDirtyBitmapIter *bdrv_dirty_meta_iter_new(BdrvDirtyBitmap *bitmap);
 BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
                                          uint64_t first_sector);
 void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
 int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
 void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t sector_num);
 int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
+int64_t bdrv_get_meta_dirty_count(BdrvDirtyBitmap *bitmap);
 void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
 
 uint64_t bdrv_dirty_bitmap_serialization_size(const BdrvDirtyBitmap *bitmap,
-- 
2.8.2

Re: [Qemu-devel] [PATCH v5 00/10] Dirty bitmap changes for migration/persistence work

[Fam Zheng]

On Fri, 06/03 12:32, Fam Zheng wrote:
> v5: Rebase: first 5 patches from last revision are already merged.

A branch is available at

https://github.com/famz/qemu/tree/meta-bitmap

for convenience.

Fam

Re: [Qemu-devel] [PATCH v5 01/10] block: Hide HBitmap in block dirty bitmap interface

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 923 bytes --]

On 03.06.2016 06:32, Fam Zheng wrote:
> HBitmap is an implementation detail of block dirty bitmap that should be hidden
> from users. Introduce a BdrvDirtyBitmapIter to encapsulate the underlying
> HBitmapIter.
> 
> A small difference in the interface is, before, an HBitmapIter is initialized
> in place, now the new BdrvDirtyBitmapIter must be dynamically allocated because
> the structure definition is in block/dirty-bitmap.c.
> 
> Two current users are converted too.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  block/backup.c               | 14 ++++++++------
>  block/dirty-bitmap.c         | 39 +++++++++++++++++++++++++++++++++------
>  block/mirror.c               | 24 +++++++++++++-----------
>  include/block/dirty-bitmap.h |  7 +++++--
>  include/qemu/typedefs.h      |  1 +
>  5 files changed, 60 insertions(+), 25 deletions(-)

Reviewed-by: Max Reitz <mreitz@redhat.com>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH v5 02/10] HBitmap: Introduce "meta" bitmap to track bit changes

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 1052 bytes --]

On 03.06.2016 06:32, Fam Zheng wrote:
> Upon each bit toggle, the corresponding bit in the meta bitmap will be
> set.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> Reviewed-by: John Snow <jsnow@redhat.com>
> ---
>  block/dirty-bitmap.c   |  2 +-
>  include/qemu/hbitmap.h | 17 +++++++++++++
>  util/hbitmap.c         | 69 +++++++++++++++++++++++++++++++++++++++-----------
>  3 files changed, 72 insertions(+), 16 deletions(-)
> 
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index ec073ee..628b77c 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -231,7 +231,7 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
>      BdrvDirtyBitmap *bm, *next;
>      QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
>          if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
> -            assert(!bitmap->active_iterators);
> +            assert(!bm->active_iterators);

Same comment as for v4, this should be squashed into the previous patch.

Max


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH v5 03/10] tests: Add test code for meta bitmap

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 306 bytes --]

On 03.06.2016 06:32, Fam Zheng wrote:
> Signed-off-by: Fam Zheng <famz@redhat.com>
> Reviewed-by: John Snow <jsnow@redhat.com>
> ---
>  tests/test-hbitmap.c | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 116 insertions(+)

Reviewed-by: Max Reitz <mreitz@redhat.com>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH v5 04/10] block: Support meta dirty bitmap

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 3349 bytes --]

On 03.06.2016 06:32, Fam Zheng wrote:
> The added group of operations enables tracking of the changed bits in
> the dirty bitmap.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  block/dirty-bitmap.c         | 52 ++++++++++++++++++++++++++++++++++++++++++++
>  include/block/dirty-bitmap.h |  9 ++++++++
>  2 files changed, 61 insertions(+)
> 
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 628b77c..9c53c56 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -38,6 +38,7 @@
>   */
>  struct BdrvDirtyBitmap {
>      HBitmap *bitmap;            /* Dirty sector bitmap implementation */
> +    HBitmap *meta;              /* Meta dirty bitmap */
>      BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
>      char *name;                 /* Optional non-empty unique ID */
>      int64_t size;               /* Size of the bitmap (Number of sectors) */
> @@ -103,6 +104,56 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
>      return bitmap;
>  }
>  
> +/* bdrv_create_meta_dirty_bitmap
> + *
> + * Create a meta dirty bitmap that tracks the changes of bits in @bitmap. I.e.
> + * when a dirty status bit in @bitmap is changed (either from reset to set or
> + * the other way around), its respective meta dirty bitmap bit will be marked
> + * dirty as well.

Not wrong, but I'd like a note here that this is not an
when-and-only-when relationship, i.e. that bits in the meta bitmap may
be set even without the tracked bits in the dirty bitmap having changed.

Maybe this should be mentioned somewhere in patch 2, too. Or maybe only
in patch 2.

> + *
> + * @bitmap: the block dirty bitmap for which to create a meta dirty bitmap.
> + * @chunk_size: how many bytes of bitmap data does each bit in the meta bitmap
> + * track.
> + */
> +void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> +                                   int chunk_size)
> +{
> +    assert(!bitmap->meta);
> +    bitmap->meta = hbitmap_create_meta(bitmap->bitmap,
> +                                       chunk_size * BITS_PER_BYTE);
> +}
> +
> +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
> +{
> +    assert(bitmap->meta);
> +    hbitmap_free_meta(bitmap->bitmap);
> +    bitmap->meta = NULL;
> +}
> +
> +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
> +                               BdrvDirtyBitmap *bitmap, int64_t sector,
> +                               int nb_sectors)
> +{
> +    uint64_t i;
> +    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
> +
> +    /* To optimize: we can make hbitmap to internally check the range in a
> +     * coarse level, or at least do it word by word. */

We could also multiply gran by the granularity of the meta bitmap. Each
bit of the meta bitmap tracks at least eight bits of the dirty bitmap,
so we're calling hbitmap_get() at least eight times as often as
necessary here.

Or we just use int gran = hbitmap_granularity(bitmap->meta);.

Not exactly wrong, though, so:

Reviewed-by: Max Reitz <mreitz@redhat.com>

> +    for (i = sector; i < sector + nb_sectors; i += gran) {
> +        if (hbitmap_get(bitmap->meta, i)) {
> +            return true;
> +        }
> +    }
> +    return false;
> +}


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH v5 05/10] block: Add two dirty bitmap getters

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 397 bytes --]

On 03.06.2016 06:32, Fam Zheng wrote:
> For dirty bitmap users to get the size and the name of a
> BdrvDirtyBitmap.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> Reviewed-by: John Snow <jsnow@redhat.com>
> ---
>  block/dirty-bitmap.c         | 10 ++++++++++
>  include/block/dirty-bitmap.h |  2 ++
>  2 files changed, 12 insertions(+)

Reviewed-by: Max Reitz <mreitz@redhat.com>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH v5 06/10] block: Assert that bdrv_release_dirty_bitmap succeeded

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 409 bytes --]

On 03.06.2016 06:32, Fam Zheng wrote:
> We use a loop over bs->dirty_bitmaps to make sure the caller is
> only releasing a bitmap owned by bs. Let's also assert that in this case
> the caller is releasing a bitmap that does exist.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  block/dirty-bitmap.c | 3 +++
>  1 file changed, 3 insertions(+)

Reviewed-by: Max Reitz <mreitz@redhat.com>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH v5 07/10] hbitmap: serialization

[Vladimir Sementsov-Ogievskiy]

On 03.06.2016 07:32, 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>
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> ---
>   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 f8ed058..26cac7d 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 13c0df5..70dc99b 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -395,6 +395,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, 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;
> +

I think it would be better to memcpy the whole part and then loop with 
cpu_to_le64. This loop will go out from compilation for LE case (I 
hope), so in LE case it would be just one memcpy. However in BE case it 
should be better to memcpy large part first and then convert words.
> +    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;
> +

the same here.
> +    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;


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH v5 01/10] block: Hide HBitmap in block dirty bitmap interface

[Vladimir Sementsov-Ogievskiy]

On 03.06.2016 07:32, Fam Zheng wrote:
> HBitmap is an implementation detail of block dirty bitmap that should be hidden
> from users. Introduce a BdrvDirtyBitmapIter to encapsulate the underlying
> HBitmapIter.
>
> A small difference in the interface is, before, an HBitmapIter is initialized
> in place, now the new BdrvDirtyBitmapIter must be dynamically allocated because
> the structure definition is in block/dirty-bitmap.c.
>
> Two current users are converted too.
>
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>   block/backup.c               | 14 ++++++++------
>   block/dirty-bitmap.c         | 39 +++++++++++++++++++++++++++++++++------
>   block/mirror.c               | 24 +++++++++++++-----------
>   include/block/dirty-bitmap.h |  7 +++++--
>   include/qemu/typedefs.h      |  1 +
>   5 files changed, 60 insertions(+), 25 deletions(-)
>
> diff --git a/block/backup.c b/block/backup.c
> index feeb9f8..ac7ca45 100644
> --- a/block/backup.c
> +++ b/block/backup.c
> @@ -317,14 +317,14 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>       int64_t end;
>       int64_t last_cluster = -1;
>       int64_t sectors_per_cluster = cluster_size_sectors(job);
> -    HBitmapIter hbi;
> +    BdrvDirtyBitmapIter *dbi;
>   
>       granularity = bdrv_dirty_bitmap_granularity(job->sync_bitmap);
>       clusters_per_iter = MAX((granularity / job->cluster_size), 1);
> -    bdrv_dirty_iter_init(job->sync_bitmap, &hbi);
> +    dbi = bdrv_dirty_iter_new(job->sync_bitmap, 0);
>   
>       /* Find the next dirty sector(s) */
> -    while ((sector = hbitmap_iter_next(&hbi)) != -1) {
> +    while ((sector = bdrv_dirty_iter_next(dbi)) != -1) {
>           cluster = sector / sectors_per_cluster;
>   
>           /* Fake progress updates for any clusters we skipped */
> @@ -336,7 +336,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>           for (end = cluster + clusters_per_iter; cluster < end; cluster++) {
>               do {
>                   if (yield_and_check(job)) {
> -                    return ret;
> +                    goto out;
>                   }
>                   ret = backup_do_cow(job, cluster * sectors_per_cluster,
>                                       sectors_per_cluster, &error_is_read,
> @@ -344,7 +344,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>                   if ((ret < 0) &&
>                       backup_error_action(job, error_is_read, -ret) ==
>                       BLOCK_ERROR_ACTION_REPORT) {
> -                    return ret;
> +                    goto out;
>                   }
>               } while (ret < 0);
>           }
> @@ -352,7 +352,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>           /* If the bitmap granularity is smaller than the backup granularity,
>            * we need to advance the iterator pointer to the next cluster. */
>           if (granularity < job->cluster_size) {
> -            bdrv_set_dirty_iter(&hbi, cluster * sectors_per_cluster);
> +            bdrv_set_dirty_iter(dbi, cluster * sectors_per_cluster);
>           }
>   
>           last_cluster = cluster - 1;
> @@ -364,6 +364,8 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>           job->common.offset += ((end - last_cluster - 1) * job->cluster_size);
>       }
>   
> +out:
> +    bdrv_dirty_iter_free(dbi);
>       return ret;
>   }
>   
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 4902ca5..ec073ee 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -42,9 +42,15 @@ struct BdrvDirtyBitmap {
>       char *name;                 /* Optional non-empty unique ID */
>       int64_t size;               /* Size of the bitmap (Number of sectors) */
>       bool disabled;              /* Bitmap is read-only */
> +    int active_iterators;       /* How many iterators are active */
>       QLIST_ENTRY(BdrvDirtyBitmap) list;
>   };
>   
> +struct BdrvDirtyBitmapIter {
> +    HBitmapIter hbi;
> +    BdrvDirtyBitmap *bitmap;
> +};
> +
>   BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs, const char *name)
>   {
>       BdrvDirtyBitmap *bm;
> @@ -212,6 +218,7 @@ void bdrv_dirty_bitmap_truncate(BlockDriverState *bs)
>   
>       QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
>           assert(!bdrv_dirty_bitmap_frozen(bitmap));
> +        assert(!bitmap->active_iterators);
>           hbitmap_truncate(bitmap->bitmap, size);
>           bitmap->size = size;
>       }
> @@ -224,6 +231,7 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
>       BdrvDirtyBitmap *bm, *next;
>       QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
>           if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
> +            assert(!bitmap->active_iterators);
>               assert(!bdrv_dirty_bitmap_frozen(bm));
>               QLIST_REMOVE(bm, list);
>               hbitmap_free(bm->bitmap);
> @@ -320,9 +328,29 @@ uint32_t bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap)
>       return BDRV_SECTOR_SIZE << hbitmap_granularity(bitmap->bitmap);
>   }
>   
> -void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, HBitmapIter *hbi)
> +BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
> +                                         uint64_t first_sector)

can you use const BdrvDirtyBitmap * pointer ? To allow iterating through 
const bitmap, in store_to_file function foe ex.

>   {
> -    hbitmap_iter_init(hbi, bitmap->bitmap, 0);
> +    BdrvDirtyBitmapIter *iter = g_new(BdrvDirtyBitmapIter, 1);
> +    hbitmap_iter_init(&iter->hbi, bitmap->bitmap, first_sector);
> +    iter->bitmap = bitmap;
> +    bitmap->active_iterators++;
> +    return iter;
> +}
> +
> +void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
> +{
> +    if (!iter) {
> +        return;
> +    }
> +    assert(iter->bitmap->active_iterators > 0);
> +    iter->bitmap->active_iterators--;
> +    g_free(iter);
> +}
> +
> +int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
> +{
> +    return hbitmap_iter_next(&iter->hbi);
>   }
>   
>   void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> @@ -373,12 +401,11 @@ void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
>   }
>   
>   /**
> - * Advance an HBitmapIter to an arbitrary offset.
> + * Advance a BdrvDirtyBitmapIter to an arbitrary offset.
>    */
> -void bdrv_set_dirty_iter(HBitmapIter *hbi, int64_t offset)
> +void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *iter, int64_t sector_num)
>   {
> -    assert(hbi->hb);
> -    hbitmap_iter_init(hbi, hbi->hb, offset);
> +    hbitmap_iter_init(&iter->hbi, iter->hbi.hb, sector_num);
>   }
>   
>   int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
> diff --git a/block/mirror.c b/block/mirror.c
> index 80fd3c7..1d90aa5 100644
> --- a/block/mirror.c
> +++ b/block/mirror.c
> @@ -52,7 +52,7 @@ typedef struct MirrorBlockJob {
>       int64_t bdev_length;
>       unsigned long *cow_bitmap;
>       BdrvDirtyBitmap *dirty_bitmap;
> -    HBitmapIter hbi;
> +    BdrvDirtyBitmapIter *dbi;
>       uint8_t *buf;
>       QSIMPLEQ_HEAD(, MirrorBuffer) buf_free;
>       int buf_free_count;
> @@ -317,10 +317,10 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>       int64_t end = s->bdev_length / BDRV_SECTOR_SIZE;
>       int sectors_per_chunk = s->granularity >> BDRV_SECTOR_BITS;
>   
> -    sector_num = hbitmap_iter_next(&s->hbi);
> +    sector_num = bdrv_dirty_iter_next(s->dbi);
>       if (sector_num < 0) {
> -        bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
> -        sector_num = hbitmap_iter_next(&s->hbi);
> +        bdrv_set_dirty_iter(s->dbi, 0);
> +        sector_num = bdrv_dirty_iter_next(s->dbi);
>           trace_mirror_restart_iter(s, bdrv_get_dirty_count(s->dirty_bitmap));
>           assert(sector_num >= 0);
>       }
> @@ -334,7 +334,7 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>       /* Find the number of consective dirty chunks following the first dirty
>        * one, and wait for in flight requests in them. */
>       while (nb_chunks * sectors_per_chunk < (s->buf_size >> BDRV_SECTOR_BITS)) {
> -        int64_t hbitmap_next;
> +        int64_t next_dirty;
>           int64_t next_sector = sector_num + nb_chunks * sectors_per_chunk;
>           int64_t next_chunk = next_sector / sectors_per_chunk;
>           if (next_sector >= end ||
> @@ -345,13 +345,13 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>               break;
>           }
>   
> -        hbitmap_next = hbitmap_iter_next(&s->hbi);
> -        if (hbitmap_next > next_sector || hbitmap_next < 0) {
> +        next_dirty = bdrv_dirty_iter_next(s->dbi);
> +        if (next_dirty > next_sector || next_dirty < 0) {
>               /* The bitmap iterator's cache is stale, refresh it */
> -            bdrv_set_dirty_iter(&s->hbi, next_sector);
> -            hbitmap_next = hbitmap_iter_next(&s->hbi);
> +            bdrv_set_dirty_iter(s->dbi, next_sector);
> +            next_dirty = bdrv_dirty_iter_next(s->dbi);
>           }
> -        assert(hbitmap_next == next_sector);
> +        assert(next_dirty == next_sector);
>           nb_chunks++;
>       }
>   
> @@ -601,7 +601,8 @@ static void coroutine_fn mirror_run(void *opaque)
>           }
>       }
>   
> -    bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
> +    assert(!s->dbi);
> +    s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
>       for (;;) {
>           uint64_t delay_ns = 0;
>           int64_t cnt;
> @@ -712,6 +713,7 @@ immediate_exit:
>       qemu_vfree(s->buf);
>       g_free(s->cow_bitmap);
>       g_free(s->in_flight_bitmap);
> +    bdrv_dirty_iter_free(s->dbi);
>       bdrv_release_dirty_bitmap(bs, s->dirty_bitmap);
>   
>       data = g_malloc(sizeof(*data));
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 80afe60..2ea601b 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -36,8 +36,11 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>                              int64_t cur_sector, int nr_sectors);
>   void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>                                int64_t cur_sector, int nr_sectors);
> -void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, struct HBitmapIter *hbi);
> -void bdrv_set_dirty_iter(struct HBitmapIter *hbi, int64_t offset);
> +BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
> +                                         uint64_t first_sector);
> +void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
> +int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
> +void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t sector_num);
>   int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
>   void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
>   
> diff --git a/include/qemu/typedefs.h b/include/qemu/typedefs.h
> index b113fcf..1b8c30a 100644
> --- a/include/qemu/typedefs.h
> +++ b/include/qemu/typedefs.h
> @@ -11,6 +11,7 @@ typedef struct AioContext AioContext;
>   typedef struct AllwinnerAHCIState AllwinnerAHCIState;
>   typedef struct AudioState AudioState;
>   typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
> +typedef struct BdrvDirtyBitmapIter BdrvDirtyBitmapIter;
>   typedef struct BlockBackend BlockBackend;
>   typedef struct BlockBackendRootState BlockBackendRootState;
>   typedef struct BlockDriverState BlockDriverState;


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH v5 01/10] block: Hide HBitmap in block dirty bitmap interface

[Vladimir Sementsov-Ogievskiy]

On 28.06.2016 18:36, Vladimir Sementsov-Ogievskiy wrote:
> On 03.06.2016 07:32, Fam Zheng wrote:
>> HBitmap is an implementation detail of block dirty bitmap that should 
>> be hidden
>> from users. Introduce a BdrvDirtyBitmapIter to encapsulate the 
>> underlying
>> HBitmapIter.
>>
>> A small difference in the interface is, before, an HBitmapIter is 
>> initialized
>> in place, now the new BdrvDirtyBitmapIter must be dynamically 
>> allocated because
>> the structure definition is in block/dirty-bitmap.c.
>>
>> Two current users are converted too.
>>
>> Signed-off-by: Fam Zheng <famz@redhat.com>
>> ---
>>   block/backup.c               | 14 ++++++++------
>>   block/dirty-bitmap.c         | 39 
>> +++++++++++++++++++++++++++++++++------
>>   block/mirror.c               | 24 +++++++++++++-----------
>>   include/block/dirty-bitmap.h |  7 +++++--
>>   include/qemu/typedefs.h      |  1 +
>>   5 files changed, 60 insertions(+), 25 deletions(-)
>>
>> diff --git a/block/backup.c b/block/backup.c
>> index feeb9f8..ac7ca45 100644
>> --- a/block/backup.c
>> +++ b/block/backup.c
>> @@ -317,14 +317,14 @@ static int coroutine_fn 
>> backup_run_incremental(BackupBlockJob *job)
>>       int64_t end;
>>       int64_t last_cluster = -1;
>>       int64_t sectors_per_cluster = cluster_size_sectors(job);
>> -    HBitmapIter hbi;
>> +    BdrvDirtyBitmapIter *dbi;
>>         granularity = bdrv_dirty_bitmap_granularity(job->sync_bitmap);
>>       clusters_per_iter = MAX((granularity / job->cluster_size), 1);
>> -    bdrv_dirty_iter_init(job->sync_bitmap, &hbi);
>> +    dbi = bdrv_dirty_iter_new(job->sync_bitmap, 0);
>>         /* Find the next dirty sector(s) */
>> -    while ((sector = hbitmap_iter_next(&hbi)) != -1) {
>> +    while ((sector = bdrv_dirty_iter_next(dbi)) != -1) {
>>           cluster = sector / sectors_per_cluster;
>>             /* Fake progress updates for any clusters we skipped */
>> @@ -336,7 +336,7 @@ static int coroutine_fn 
>> backup_run_incremental(BackupBlockJob *job)
>>           for (end = cluster + clusters_per_iter; cluster < end; 
>> cluster++) {
>>               do {
>>                   if (yield_and_check(job)) {
>> -                    return ret;
>> +                    goto out;
>>                   }
>>                   ret = backup_do_cow(job, cluster * 
>> sectors_per_cluster,
>>                                       sectors_per_cluster, 
>> &error_is_read,
>> @@ -344,7 +344,7 @@ static int coroutine_fn 
>> backup_run_incremental(BackupBlockJob *job)
>>                   if ((ret < 0) &&
>>                       backup_error_action(job, error_is_read, -ret) ==
>>                       BLOCK_ERROR_ACTION_REPORT) {
>> -                    return ret;
>> +                    goto out;
>>                   }
>>               } while (ret < 0);
>>           }
>> @@ -352,7 +352,7 @@ static int coroutine_fn 
>> backup_run_incremental(BackupBlockJob *job)
>>           /* If the bitmap granularity is smaller than the backup 
>> granularity,
>>            * we need to advance the iterator pointer to the next 
>> cluster. */
>>           if (granularity < job->cluster_size) {
>> -            bdrv_set_dirty_iter(&hbi, cluster * sectors_per_cluster);
>> +            bdrv_set_dirty_iter(dbi, cluster * sectors_per_cluster);
>>           }
>>             last_cluster = cluster - 1;
>> @@ -364,6 +364,8 @@ static int coroutine_fn 
>> backup_run_incremental(BackupBlockJob *job)
>>           job->common.offset += ((end - last_cluster - 1) * 
>> job->cluster_size);
>>       }
>>   +out:
>> +    bdrv_dirty_iter_free(dbi);
>>       return ret;
>>   }
>>   diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>> index 4902ca5..ec073ee 100644
>> --- a/block/dirty-bitmap.c
>> +++ b/block/dirty-bitmap.c
>> @@ -42,9 +42,15 @@ struct BdrvDirtyBitmap {
>>       char *name;                 /* Optional non-empty unique ID */
>>       int64_t size;               /* Size of the bitmap (Number of 
>> sectors) */
>>       bool disabled;              /* Bitmap is read-only */
>> +    int active_iterators;       /* How many iterators are active */
>>       QLIST_ENTRY(BdrvDirtyBitmap) list;
>>   };
>>   +struct BdrvDirtyBitmapIter {
>> +    HBitmapIter hbi;
>> +    BdrvDirtyBitmap *bitmap;
>> +};
>> +
>>   BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs, const 
>> char *name)
>>   {
>>       BdrvDirtyBitmap *bm;
>> @@ -212,6 +218,7 @@ void bdrv_dirty_bitmap_truncate(BlockDriverState 
>> *bs)
>>         QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
>>           assert(!bdrv_dirty_bitmap_frozen(bitmap));
>> +        assert(!bitmap->active_iterators);
>>           hbitmap_truncate(bitmap->bitmap, size);
>>           bitmap->size = size;
>>       }
>> @@ -224,6 +231,7 @@ static void 
>> bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
>>       BdrvDirtyBitmap *bm, *next;
>>       QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
>>           if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
>> +            assert(!bitmap->active_iterators);
>>               assert(!bdrv_dirty_bitmap_frozen(bm));
>>               QLIST_REMOVE(bm, list);
>>               hbitmap_free(bm->bitmap);
>> @@ -320,9 +328,29 @@ uint32_t 
>> bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap)
>>       return BDRV_SECTOR_SIZE << hbitmap_granularity(bitmap->bitmap);
>>   }
>>   -void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, HBitmapIter *hbi)
>> +BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
>> +                                         uint64_t first_sector)
>
> can you use const BdrvDirtyBitmap * pointer ? To allow iterating 
> through const bitmap, in store_to_file function foe ex.

I see, no, because of 'bitmap->active_iterators++'...

>
>>   {
>> -    hbitmap_iter_init(hbi, bitmap->bitmap, 0);
>> +    BdrvDirtyBitmapIter *iter = g_new(BdrvDirtyBitmapIter, 1);
>> +    hbitmap_iter_init(&iter->hbi, bitmap->bitmap, first_sector);
>> +    iter->bitmap = bitmap;
>> +    bitmap->active_iterators++;
>> +    return iter;
>> +}
>> +
>> +void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
>> +{
>> +    if (!iter) {
>> +        return;
>> +    }
>> +    assert(iter->bitmap->active_iterators > 0);
>> +    iter->bitmap->active_iterators--;
>> +    g_free(iter);
>> +}
>> +
>> +int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
>> +{
>> +    return hbitmap_iter_next(&iter->hbi);
>>   }
>>     void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>> @@ -373,12 +401,11 @@ void bdrv_set_dirty(BlockDriverState *bs, 
>> int64_t cur_sector,
>>   }
>>     /**
>> - * Advance an HBitmapIter to an arbitrary offset.
>> + * Advance a BdrvDirtyBitmapIter to an arbitrary offset.
>>    */
>> -void bdrv_set_dirty_iter(HBitmapIter *hbi, int64_t offset)
>> +void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *iter, int64_t sector_num)
>>   {
>> -    assert(hbi->hb);
>> -    hbitmap_iter_init(hbi, hbi->hb, offset);
>> +    hbitmap_iter_init(&iter->hbi, iter->hbi.hb, sector_num);
>>   }
>>     int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
>> diff --git a/block/mirror.c b/block/mirror.c
>> index 80fd3c7..1d90aa5 100644
>> --- a/block/mirror.c
>> +++ b/block/mirror.c
>> @@ -52,7 +52,7 @@ typedef struct MirrorBlockJob {
>>       int64_t bdev_length;
>>       unsigned long *cow_bitmap;
>>       BdrvDirtyBitmap *dirty_bitmap;
>> -    HBitmapIter hbi;
>> +    BdrvDirtyBitmapIter *dbi;
>>       uint8_t *buf;
>>       QSIMPLEQ_HEAD(, MirrorBuffer) buf_free;
>>       int buf_free_count;
>> @@ -317,10 +317,10 @@ static uint64_t coroutine_fn 
>> mirror_iteration(MirrorBlockJob *s)
>>       int64_t end = s->bdev_length / BDRV_SECTOR_SIZE;
>>       int sectors_per_chunk = s->granularity >> BDRV_SECTOR_BITS;
>>   -    sector_num = hbitmap_iter_next(&s->hbi);
>> +    sector_num = bdrv_dirty_iter_next(s->dbi);
>>       if (sector_num < 0) {
>> -        bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
>> -        sector_num = hbitmap_iter_next(&s->hbi);
>> +        bdrv_set_dirty_iter(s->dbi, 0);
>> +        sector_num = bdrv_dirty_iter_next(s->dbi);
>>           trace_mirror_restart_iter(s, 
>> bdrv_get_dirty_count(s->dirty_bitmap));
>>           assert(sector_num >= 0);
>>       }
>> @@ -334,7 +334,7 @@ static uint64_t coroutine_fn 
>> mirror_iteration(MirrorBlockJob *s)
>>       /* Find the number of consective dirty chunks following the 
>> first dirty
>>        * one, and wait for in flight requests in them. */
>>       while (nb_chunks * sectors_per_chunk < (s->buf_size >> 
>> BDRV_SECTOR_BITS)) {
>> -        int64_t hbitmap_next;
>> +        int64_t next_dirty;
>>           int64_t next_sector = sector_num + nb_chunks * 
>> sectors_per_chunk;
>>           int64_t next_chunk = next_sector / sectors_per_chunk;
>>           if (next_sector >= end ||
>> @@ -345,13 +345,13 @@ static uint64_t coroutine_fn 
>> mirror_iteration(MirrorBlockJob *s)
>>               break;
>>           }
>>   -        hbitmap_next = hbitmap_iter_next(&s->hbi);
>> -        if (hbitmap_next > next_sector || hbitmap_next < 0) {
>> +        next_dirty = bdrv_dirty_iter_next(s->dbi);
>> +        if (next_dirty > next_sector || next_dirty < 0) {
>>               /* The bitmap iterator's cache is stale, refresh it */
>> -            bdrv_set_dirty_iter(&s->hbi, next_sector);
>> -            hbitmap_next = hbitmap_iter_next(&s->hbi);
>> +            bdrv_set_dirty_iter(s->dbi, next_sector);
>> +            next_dirty = bdrv_dirty_iter_next(s->dbi);
>>           }
>> -        assert(hbitmap_next == next_sector);
>> +        assert(next_dirty == next_sector);
>>           nb_chunks++;
>>       }
>>   @@ -601,7 +601,8 @@ static void coroutine_fn mirror_run(void *opaque)
>>           }
>>       }
>>   -    bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
>> +    assert(!s->dbi);
>> +    s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
>>       for (;;) {
>>           uint64_t delay_ns = 0;
>>           int64_t cnt;
>> @@ -712,6 +713,7 @@ immediate_exit:
>>       qemu_vfree(s->buf);
>>       g_free(s->cow_bitmap);
>>       g_free(s->in_flight_bitmap);
>> +    bdrv_dirty_iter_free(s->dbi);
>>       bdrv_release_dirty_bitmap(bs, s->dirty_bitmap);
>>         data = g_malloc(sizeof(*data));
>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>> index 80afe60..2ea601b 100644
>> --- a/include/block/dirty-bitmap.h
>> +++ b/include/block/dirty-bitmap.h
>> @@ -36,8 +36,11 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>>                              int64_t cur_sector, int nr_sectors);
>>   void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>>                                int64_t cur_sector, int nr_sectors);
>> -void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, struct 
>> HBitmapIter *hbi);
>> -void bdrv_set_dirty_iter(struct HBitmapIter *hbi, int64_t offset);
>> +BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
>> +                                         uint64_t first_sector);
>> +void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
>> +int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
>> +void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t sector_num);
>>   int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
>>   void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
>>   diff --git a/include/qemu/typedefs.h b/include/qemu/typedefs.h
>> index b113fcf..1b8c30a 100644
>> --- a/include/qemu/typedefs.h
>> +++ b/include/qemu/typedefs.h
>> @@ -11,6 +11,7 @@ typedef struct AioContext AioContext;
>>   typedef struct AllwinnerAHCIState AllwinnerAHCIState;
>>   typedef struct AudioState AudioState;
>>   typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
>> +typedef struct BdrvDirtyBitmapIter BdrvDirtyBitmapIter;
>>   typedef struct BlockBackend BlockBackend;
>>   typedef struct BlockBackendRootState BlockBackendRootState;
>>   typedef struct BlockDriverState BlockDriverState;
>
>


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH v5 01/10] block: Hide HBitmap in block dirty bitmap interface

[John Snow]

On 06/03/2016 12:32 AM, Fam Zheng wrote:
> HBitmap is an implementation detail of block dirty bitmap that should be hidden
> from users. Introduce a BdrvDirtyBitmapIter to encapsulate the underlying
> HBitmapIter.
> 
> A small difference in the interface is, before, an HBitmapIter is initialized
> in place, now the new BdrvDirtyBitmapIter must be dynamically allocated because
> the structure definition is in block/dirty-bitmap.c.
> 
> Two current users are converted too.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  block/backup.c               | 14 ++++++++------
>  block/dirty-bitmap.c         | 39 +++++++++++++++++++++++++++++++++------
>  block/mirror.c               | 24 +++++++++++++-----------
>  include/block/dirty-bitmap.h |  7 +++++--
>  include/qemu/typedefs.h      |  1 +
>  5 files changed, 60 insertions(+), 25 deletions(-)
> 
> diff --git a/block/backup.c b/block/backup.c
> index feeb9f8..ac7ca45 100644
> --- a/block/backup.c
> +++ b/block/backup.c
> @@ -317,14 +317,14 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>      int64_t end;
>      int64_t last_cluster = -1;
>      int64_t sectors_per_cluster = cluster_size_sectors(job);
> -    HBitmapIter hbi;
> +    BdrvDirtyBitmapIter *dbi;
>  
>      granularity = bdrv_dirty_bitmap_granularity(job->sync_bitmap);
>      clusters_per_iter = MAX((granularity / job->cluster_size), 1);
> -    bdrv_dirty_iter_init(job->sync_bitmap, &hbi);
> +    dbi = bdrv_dirty_iter_new(job->sync_bitmap, 0);
>  
>      /* Find the next dirty sector(s) */
> -    while ((sector = hbitmap_iter_next(&hbi)) != -1) {
> +    while ((sector = bdrv_dirty_iter_next(dbi)) != -1) {
>          cluster = sector / sectors_per_cluster;
>  
>          /* Fake progress updates for any clusters we skipped */
> @@ -336,7 +336,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>          for (end = cluster + clusters_per_iter; cluster < end; cluster++) {
>              do {
>                  if (yield_and_check(job)) {
> -                    return ret;
> +                    goto out;
>                  }
>                  ret = backup_do_cow(job, cluster * sectors_per_cluster,
>                                      sectors_per_cluster, &error_is_read,
> @@ -344,7 +344,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>                  if ((ret < 0) &&
>                      backup_error_action(job, error_is_read, -ret) ==
>                      BLOCK_ERROR_ACTION_REPORT) {
> -                    return ret;
> +                    goto out;
>                  }
>              } while (ret < 0);
>          }
> @@ -352,7 +352,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>          /* If the bitmap granularity is smaller than the backup granularity,
>           * we need to advance the iterator pointer to the next cluster. */
>          if (granularity < job->cluster_size) {
> -            bdrv_set_dirty_iter(&hbi, cluster * sectors_per_cluster);
> +            bdrv_set_dirty_iter(dbi, cluster * sectors_per_cluster);
>          }
>  
>          last_cluster = cluster - 1;
> @@ -364,6 +364,8 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>          job->common.offset += ((end - last_cluster - 1) * job->cluster_size);
>      }
>  
> +out:
> +    bdrv_dirty_iter_free(dbi);
>      return ret;
>  }
>  
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 4902ca5..ec073ee 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -42,9 +42,15 @@ struct BdrvDirtyBitmap {
>      char *name;                 /* Optional non-empty unique ID */
>      int64_t size;               /* Size of the bitmap (Number of sectors) */
>      bool disabled;              /* Bitmap is read-only */
> +    int active_iterators;       /* How many iterators are active */
>      QLIST_ENTRY(BdrvDirtyBitmap) list;
>  };
>  
> +struct BdrvDirtyBitmapIter {
> +    HBitmapIter hbi;
> +    BdrvDirtyBitmap *bitmap;
> +};
> +
>  BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs, const char *name)
>  {
>      BdrvDirtyBitmap *bm;
> @@ -212,6 +218,7 @@ void bdrv_dirty_bitmap_truncate(BlockDriverState *bs)
>  
>      QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
>          assert(!bdrv_dirty_bitmap_frozen(bitmap));
> +        assert(!bitmap->active_iterators);
>          hbitmap_truncate(bitmap->bitmap, size);
>          bitmap->size = size;
>      }
> @@ -224,6 +231,7 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
>      BdrvDirtyBitmap *bm, *next;
>      QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
>          if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
> +            assert(!bitmap->active_iterators);

No good -- this function is also used to clear out all named bitmaps
belonging to a BDS, so 'bitmap' may be NULL, so this assertion is bad.

Fixing up in my local branch.

--js

>              assert(!bdrv_dirty_bitmap_frozen(bm));
>              QLIST_REMOVE(bm, list);
>              hbitmap_free(bm->bitmap);
> @@ -320,9 +328,29 @@ uint32_t bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap)
>      return BDRV_SECTOR_SIZE << hbitmap_granularity(bitmap->bitmap);
>  }
>  
> -void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, HBitmapIter *hbi)
> +BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
> +                                         uint64_t first_sector)
>  {
> -    hbitmap_iter_init(hbi, bitmap->bitmap, 0);
> +    BdrvDirtyBitmapIter *iter = g_new(BdrvDirtyBitmapIter, 1);
> +    hbitmap_iter_init(&iter->hbi, bitmap->bitmap, first_sector);
> +    iter->bitmap = bitmap;
> +    bitmap->active_iterators++;
> +    return iter;
> +}
> +
> +void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
> +{
> +    if (!iter) {
> +        return;
> +    }
> +    assert(iter->bitmap->active_iterators > 0);
> +    iter->bitmap->active_iterators--;
> +    g_free(iter);
> +}
> +
> +int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
> +{
> +    return hbitmap_iter_next(&iter->hbi);
>  }
>  
>  void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> @@ -373,12 +401,11 @@ void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
>  }
>  
>  /**
> - * Advance an HBitmapIter to an arbitrary offset.
> + * Advance a BdrvDirtyBitmapIter to an arbitrary offset.
>   */
> -void bdrv_set_dirty_iter(HBitmapIter *hbi, int64_t offset)
> +void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *iter, int64_t sector_num)
>  {
> -    assert(hbi->hb);
> -    hbitmap_iter_init(hbi, hbi->hb, offset);
> +    hbitmap_iter_init(&iter->hbi, iter->hbi.hb, sector_num);
>  }
>  
>  int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
> diff --git a/block/mirror.c b/block/mirror.c
> index 80fd3c7..1d90aa5 100644
> --- a/block/mirror.c
> +++ b/block/mirror.c
> @@ -52,7 +52,7 @@ typedef struct MirrorBlockJob {
>      int64_t bdev_length;
>      unsigned long *cow_bitmap;
>      BdrvDirtyBitmap *dirty_bitmap;
> -    HBitmapIter hbi;
> +    BdrvDirtyBitmapIter *dbi;
>      uint8_t *buf;
>      QSIMPLEQ_HEAD(, MirrorBuffer) buf_free;
>      int buf_free_count;
> @@ -317,10 +317,10 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>      int64_t end = s->bdev_length / BDRV_SECTOR_SIZE;
>      int sectors_per_chunk = s->granularity >> BDRV_SECTOR_BITS;
>  
> -    sector_num = hbitmap_iter_next(&s->hbi);
> +    sector_num = bdrv_dirty_iter_next(s->dbi);
>      if (sector_num < 0) {
> -        bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
> -        sector_num = hbitmap_iter_next(&s->hbi);
> +        bdrv_set_dirty_iter(s->dbi, 0);
> +        sector_num = bdrv_dirty_iter_next(s->dbi);
>          trace_mirror_restart_iter(s, bdrv_get_dirty_count(s->dirty_bitmap));
>          assert(sector_num >= 0);
>      }
> @@ -334,7 +334,7 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>      /* Find the number of consective dirty chunks following the first dirty
>       * one, and wait for in flight requests in them. */
>      while (nb_chunks * sectors_per_chunk < (s->buf_size >> BDRV_SECTOR_BITS)) {
> -        int64_t hbitmap_next;
> +        int64_t next_dirty;
>          int64_t next_sector = sector_num + nb_chunks * sectors_per_chunk;
>          int64_t next_chunk = next_sector / sectors_per_chunk;
>          if (next_sector >= end ||
> @@ -345,13 +345,13 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>              break;
>          }
>  
> -        hbitmap_next = hbitmap_iter_next(&s->hbi);
> -        if (hbitmap_next > next_sector || hbitmap_next < 0) {
> +        next_dirty = bdrv_dirty_iter_next(s->dbi);
> +        if (next_dirty > next_sector || next_dirty < 0) {
>              /* The bitmap iterator's cache is stale, refresh it */
> -            bdrv_set_dirty_iter(&s->hbi, next_sector);
> -            hbitmap_next = hbitmap_iter_next(&s->hbi);
> +            bdrv_set_dirty_iter(s->dbi, next_sector);
> +            next_dirty = bdrv_dirty_iter_next(s->dbi);
>          }
> -        assert(hbitmap_next == next_sector);
> +        assert(next_dirty == next_sector);
>          nb_chunks++;
>      }
>  
> @@ -601,7 +601,8 @@ static void coroutine_fn mirror_run(void *opaque)
>          }
>      }
>  
> -    bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
> +    assert(!s->dbi);
> +    s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
>      for (;;) {
>          uint64_t delay_ns = 0;
>          int64_t cnt;
> @@ -712,6 +713,7 @@ immediate_exit:
>      qemu_vfree(s->buf);
>      g_free(s->cow_bitmap);
>      g_free(s->in_flight_bitmap);
> +    bdrv_dirty_iter_free(s->dbi);
>      bdrv_release_dirty_bitmap(bs, s->dirty_bitmap);
>  
>      data = g_malloc(sizeof(*data));
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 80afe60..2ea601b 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -36,8 +36,11 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>                             int64_t cur_sector, int nr_sectors);
>  void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>                               int64_t cur_sector, int nr_sectors);
> -void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, struct HBitmapIter *hbi);
> -void bdrv_set_dirty_iter(struct HBitmapIter *hbi, int64_t offset);
> +BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
> +                                         uint64_t first_sector);
> +void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
> +int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
> +void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t sector_num);
>  int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
>  void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
>  
> diff --git a/include/qemu/typedefs.h b/include/qemu/typedefs.h
> index b113fcf..1b8c30a 100644
> --- a/include/qemu/typedefs.h
> +++ b/include/qemu/typedefs.h
> @@ -11,6 +11,7 @@ typedef struct AioContext AioContext;
>  typedef struct AllwinnerAHCIState AllwinnerAHCIState;
>  typedef struct AudioState AudioState;
>  typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
> +typedef struct BdrvDirtyBitmapIter BdrvDirtyBitmapIter;
>  typedef struct BlockBackend BlockBackend;
>  typedef struct BlockBackendRootState BlockBackendRootState;
>  typedef struct BlockDriverState BlockDriverState;
> 

Re: [Qemu-devel] [PATCH v5 01/10] block: Hide HBitmap in block dirty bitmap interface

[Vladimir Sementsov-Ogievskiy]

On 13.07.2016 01:49, John Snow wrote:
>
> On 06/03/2016 12:32 AM, Fam Zheng wrote:
>> HBitmap is an implementation detail of block dirty bitmap that should be hidden
>> from users. Introduce a BdrvDirtyBitmapIter to encapsulate the underlying
>> HBitmapIter.
>>
>> A small difference in the interface is, before, an HBitmapIter is initialized
>> in place, now the new BdrvDirtyBitmapIter must be dynamically allocated because
>> the structure definition is in block/dirty-bitmap.c.
>>
>> Two current users are converted too.
>>
>> Signed-off-by: Fam Zheng <famz@redhat.com>
>> ---
>>   block/backup.c               | 14 ++++++++------
>>   block/dirty-bitmap.c         | 39 +++++++++++++++++++++++++++++++++------
>>   block/mirror.c               | 24 +++++++++++++-----------
>>   include/block/dirty-bitmap.h |  7 +++++--
>>   include/qemu/typedefs.h      |  1 +
>>   5 files changed, 60 insertions(+), 25 deletions(-)
>>
>> diff --git a/block/backup.c b/block/backup.c
>> index feeb9f8..ac7ca45 100644
>> --- a/block/backup.c
>> +++ b/block/backup.c
>> @@ -317,14 +317,14 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>>       int64_t end;
>>       int64_t last_cluster = -1;
>>       int64_t sectors_per_cluster = cluster_size_sectors(job);
>> -    HBitmapIter hbi;
>> +    BdrvDirtyBitmapIter *dbi;
>>   
>>       granularity = bdrv_dirty_bitmap_granularity(job->sync_bitmap);
>>       clusters_per_iter = MAX((granularity / job->cluster_size), 1);
>> -    bdrv_dirty_iter_init(job->sync_bitmap, &hbi);
>> +    dbi = bdrv_dirty_iter_new(job->sync_bitmap, 0);
>>   
>>       /* Find the next dirty sector(s) */
>> -    while ((sector = hbitmap_iter_next(&hbi)) != -1) {
>> +    while ((sector = bdrv_dirty_iter_next(dbi)) != -1) {
>>           cluster = sector / sectors_per_cluster;
>>   
>>           /* Fake progress updates for any clusters we skipped */
>> @@ -336,7 +336,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>>           for (end = cluster + clusters_per_iter; cluster < end; cluster++) {
>>               do {
>>                   if (yield_and_check(job)) {
>> -                    return ret;
>> +                    goto out;
>>                   }
>>                   ret = backup_do_cow(job, cluster * sectors_per_cluster,
>>                                       sectors_per_cluster, &error_is_read,
>> @@ -344,7 +344,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>>                   if ((ret < 0) &&
>>                       backup_error_action(job, error_is_read, -ret) ==
>>                       BLOCK_ERROR_ACTION_REPORT) {
>> -                    return ret;
>> +                    goto out;
>>                   }
>>               } while (ret < 0);
>>           }
>> @@ -352,7 +352,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>>           /* If the bitmap granularity is smaller than the backup granularity,
>>            * we need to advance the iterator pointer to the next cluster. */
>>           if (granularity < job->cluster_size) {
>> -            bdrv_set_dirty_iter(&hbi, cluster * sectors_per_cluster);
>> +            bdrv_set_dirty_iter(dbi, cluster * sectors_per_cluster);
>>           }
>>   
>>           last_cluster = cluster - 1;
>> @@ -364,6 +364,8 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
>>           job->common.offset += ((end - last_cluster - 1) * job->cluster_size);
>>       }
>>   
>> +out:
>> +    bdrv_dirty_iter_free(dbi);
>>       return ret;
>>   }
>>   
>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>> index 4902ca5..ec073ee 100644
>> --- a/block/dirty-bitmap.c
>> +++ b/block/dirty-bitmap.c
>> @@ -42,9 +42,15 @@ struct BdrvDirtyBitmap {
>>       char *name;                 /* Optional non-empty unique ID */
>>       int64_t size;               /* Size of the bitmap (Number of sectors) */
>>       bool disabled;              /* Bitmap is read-only */
>> +    int active_iterators;       /* How many iterators are active */
>>       QLIST_ENTRY(BdrvDirtyBitmap) list;
>>   };
>>   
>> +struct BdrvDirtyBitmapIter {
>> +    HBitmapIter hbi;
>> +    BdrvDirtyBitmap *bitmap;
>> +};
>> +
>>   BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs, const char *name)
>>   {
>>       BdrvDirtyBitmap *bm;
>> @@ -212,6 +218,7 @@ void bdrv_dirty_bitmap_truncate(BlockDriverState *bs)
>>   
>>       QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
>>           assert(!bdrv_dirty_bitmap_frozen(bitmap));
>> +        assert(!bitmap->active_iterators);
>>           hbitmap_truncate(bitmap->bitmap, size);
>>           bitmap->size = size;
>>       }
>> @@ -224,6 +231,7 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
>>       BdrvDirtyBitmap *bm, *next;
>>       QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
>>           if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
>> +            assert(!bitmap->active_iterators);
> No good -- this function is also used to clear out all named bitmaps
> belonging to a BDS, so 'bitmap' may be NULL, so this assertion is bad.

Just a note about this. I do not like this hidden behaviour of 
release_bitmap, as it more native for freeing functions to do nothing 
with NULL pointer.. g_free(NULL) do not free all allocations))).. If 
someone agrees, this may be better to be changed.

>
> Fixing up in my local branch.
>
> --js
>
>>               assert(!bdrv_dirty_bitmap_frozen(bm));
>>               QLIST_REMOVE(bm, list);
>>               hbitmap_free(bm->bitmap);
>> @@ -320,9 +328,29 @@ uint32_t bdrv_dirty_bitmap_granularity(BdrvDirtyBitmap *bitmap)
>>       return BDRV_SECTOR_SIZE << hbitmap_granularity(bitmap->bitmap);
>>   }
>>   
>> -void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, HBitmapIter *hbi)
>> +BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
>> +                                         uint64_t first_sector)
>>   {
>> -    hbitmap_iter_init(hbi, bitmap->bitmap, 0);
>> +    BdrvDirtyBitmapIter *iter = g_new(BdrvDirtyBitmapIter, 1);
>> +    hbitmap_iter_init(&iter->hbi, bitmap->bitmap, first_sector);
>> +    iter->bitmap = bitmap;
>> +    bitmap->active_iterators++;
>> +    return iter;
>> +}
>> +
>> +void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
>> +{
>> +    if (!iter) {
>> +        return;
>> +    }
>> +    assert(iter->bitmap->active_iterators > 0);
>> +    iter->bitmap->active_iterators--;
>> +    g_free(iter);
>> +}
>> +
>> +int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
>> +{
>> +    return hbitmap_iter_next(&iter->hbi);
>>   }
>>   
>>   void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>> @@ -373,12 +401,11 @@ void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
>>   }
>>   
>>   /**
>> - * Advance an HBitmapIter to an arbitrary offset.
>> + * Advance a BdrvDirtyBitmapIter to an arbitrary offset.
>>    */
>> -void bdrv_set_dirty_iter(HBitmapIter *hbi, int64_t offset)
>> +void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *iter, int64_t sector_num)
>>   {
>> -    assert(hbi->hb);
>> -    hbitmap_iter_init(hbi, hbi->hb, offset);
>> +    hbitmap_iter_init(&iter->hbi, iter->hbi.hb, sector_num);
>>   }
>>   
>>   int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
>> diff --git a/block/mirror.c b/block/mirror.c
>> index 80fd3c7..1d90aa5 100644
>> --- a/block/mirror.c
>> +++ b/block/mirror.c
>> @@ -52,7 +52,7 @@ typedef struct MirrorBlockJob {
>>       int64_t bdev_length;
>>       unsigned long *cow_bitmap;
>>       BdrvDirtyBitmap *dirty_bitmap;
>> -    HBitmapIter hbi;
>> +    BdrvDirtyBitmapIter *dbi;
>>       uint8_t *buf;
>>       QSIMPLEQ_HEAD(, MirrorBuffer) buf_free;
>>       int buf_free_count;
>> @@ -317,10 +317,10 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>>       int64_t end = s->bdev_length / BDRV_SECTOR_SIZE;
>>       int sectors_per_chunk = s->granularity >> BDRV_SECTOR_BITS;
>>   
>> -    sector_num = hbitmap_iter_next(&s->hbi);
>> +    sector_num = bdrv_dirty_iter_next(s->dbi);
>>       if (sector_num < 0) {
>> -        bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
>> -        sector_num = hbitmap_iter_next(&s->hbi);
>> +        bdrv_set_dirty_iter(s->dbi, 0);
>> +        sector_num = bdrv_dirty_iter_next(s->dbi);
>>           trace_mirror_restart_iter(s, bdrv_get_dirty_count(s->dirty_bitmap));
>>           assert(sector_num >= 0);
>>       }
>> @@ -334,7 +334,7 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>>       /* Find the number of consective dirty chunks following the first dirty
>>        * one, and wait for in flight requests in them. */
>>       while (nb_chunks * sectors_per_chunk < (s->buf_size >> BDRV_SECTOR_BITS)) {
>> -        int64_t hbitmap_next;
>> +        int64_t next_dirty;
>>           int64_t next_sector = sector_num + nb_chunks * sectors_per_chunk;
>>           int64_t next_chunk = next_sector / sectors_per_chunk;
>>           if (next_sector >= end ||
>> @@ -345,13 +345,13 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>>               break;
>>           }
>>   
>> -        hbitmap_next = hbitmap_iter_next(&s->hbi);
>> -        if (hbitmap_next > next_sector || hbitmap_next < 0) {
>> +        next_dirty = bdrv_dirty_iter_next(s->dbi);
>> +        if (next_dirty > next_sector || next_dirty < 0) {
>>               /* The bitmap iterator's cache is stale, refresh it */
>> -            bdrv_set_dirty_iter(&s->hbi, next_sector);
>> -            hbitmap_next = hbitmap_iter_next(&s->hbi);
>> +            bdrv_set_dirty_iter(s->dbi, next_sector);
>> +            next_dirty = bdrv_dirty_iter_next(s->dbi);
>>           }
>> -        assert(hbitmap_next == next_sector);
>> +        assert(next_dirty == next_sector);
>>           nb_chunks++;
>>       }
>>   
>> @@ -601,7 +601,8 @@ static void coroutine_fn mirror_run(void *opaque)
>>           }
>>       }
>>   
>> -    bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
>> +    assert(!s->dbi);
>> +    s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
>>       for (;;) {
>>           uint64_t delay_ns = 0;
>>           int64_t cnt;
>> @@ -712,6 +713,7 @@ immediate_exit:
>>       qemu_vfree(s->buf);
>>       g_free(s->cow_bitmap);
>>       g_free(s->in_flight_bitmap);
>> +    bdrv_dirty_iter_free(s->dbi);
>>       bdrv_release_dirty_bitmap(bs, s->dirty_bitmap);
>>   
>>       data = g_malloc(sizeof(*data));
>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>> index 80afe60..2ea601b 100644
>> --- a/include/block/dirty-bitmap.h
>> +++ b/include/block/dirty-bitmap.h
>> @@ -36,8 +36,11 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>>                              int64_t cur_sector, int nr_sectors);
>>   void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>>                                int64_t cur_sector, int nr_sectors);
>> -void bdrv_dirty_iter_init(BdrvDirtyBitmap *bitmap, struct HBitmapIter *hbi);
>> -void bdrv_set_dirty_iter(struct HBitmapIter *hbi, int64_t offset);
>> +BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
>> +                                         uint64_t first_sector);
>> +void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
>> +int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
>> +void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t sector_num);
>>   int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
>>   void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
>>   
>> diff --git a/include/qemu/typedefs.h b/include/qemu/typedefs.h
>> index b113fcf..1b8c30a 100644
>> --- a/include/qemu/typedefs.h
>> +++ b/include/qemu/typedefs.h
>> @@ -11,6 +11,7 @@ typedef struct AioContext AioContext;
>>   typedef struct AllwinnerAHCIState AllwinnerAHCIState;
>>   typedef struct AudioState AudioState;
>>   typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
>> +typedef struct BdrvDirtyBitmapIter BdrvDirtyBitmapIter;
>>   typedef struct BlockBackend BlockBackend;
>>   typedef struct BlockBackendRootState BlockBackendRootState;
>>   typedef struct BlockDriverState BlockDriverState;
>>


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH v5 01/10] block: Hide HBitmap in block dirty bitmap interface

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 2402 bytes --]

On 13.07.2016 09:57, Vladimir Sementsov-Ogievskiy wrote:
> On 13.07.2016 01:49, John Snow wrote:
>>
>> On 06/03/2016 12:32 AM, Fam Zheng wrote:
>>> HBitmap is an implementation detail of block dirty bitmap that should
>>> be hidden
>>> from users. Introduce a BdrvDirtyBitmapIter to encapsulate the
>>> underlying
>>> HBitmapIter.
>>>
>>> A small difference in the interface is, before, an HBitmapIter is
>>> initialized
>>> in place, now the new BdrvDirtyBitmapIter must be dynamically
>>> allocated because
>>> the structure definition is in block/dirty-bitmap.c.
>>>
>>> Two current users are converted too.
>>>
>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>> ---
>>>   block/backup.c               | 14 ++++++++------
>>>   block/dirty-bitmap.c         | 39
>>> +++++++++++++++++++++++++++++++++------
>>>   block/mirror.c               | 24 +++++++++++++-----------
>>>   include/block/dirty-bitmap.h |  7 +++++--
>>>   include/qemu/typedefs.h      |  1 +
>>>   5 files changed, 60 insertions(+), 25 deletions(-)
>>>

[...]

>>> @@ -224,6 +231,7 @@ static void
>>> bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
>>>       BdrvDirtyBitmap *bm, *next;
>>>       QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
>>>           if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
>>> +            assert(!bitmap->active_iterators);
>> No good -- this function is also used to clear out all named bitmaps
>> belonging to a BDS, so 'bitmap' may be NULL, so this assertion is bad.
> 
> Just a note about this. I do not like this hidden behaviour of
> release_bitmap, as it more native for freeing functions to do nothing
> with NULL pointer.. g_free(NULL) do not free all allocations))).. If
> someone agrees, this may be better to be changed.

The function is not called "bdrv_release_dirty_bitmap()", though, but
"bdrv_do_release_matching_dirty_bitmap()". The "do" means that it's an
internal function, called only by bdrv_release_dirty_bitmap() (aha!) and
bdrv_release_named_dirty_bitmaps(); and the "matching" means that if you
pass NULL, it'll release all bitmaps.

What we could do is make bdrv_release_dirty_bitmap() a no-op if NULL is
passed, or add an assertion that the argument is not NULL. I'd be fine
with either, but I don't think bdrv_do_release_matching_dirty_bitmap()
needs to be adjusted.

Max


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 498 bytes --]

Re: [Qemu-devel] [PATCH v5 02/10] HBitmap: Introduce "meta" bitmap to track bit changes

[John Snow]

On 06/22/2016 11:22 AM, Max Reitz wrote:
> On 03.06.2016 06:32, Fam Zheng wrote:
>> Upon each bit toggle, the corresponding bit in the meta bitmap will be
>> set.
>>
>> Signed-off-by: Fam Zheng <famz@redhat.com>
>> Reviewed-by: John Snow <jsnow@redhat.com>
>> ---
>>  block/dirty-bitmap.c   |  2 +-
>>  include/qemu/hbitmap.h | 17 +++++++++++++
>>  util/hbitmap.c         | 69 +++++++++++++++++++++++++++++++++++++++-----------
>>  3 files changed, 72 insertions(+), 16 deletions(-)
>>
>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>> index ec073ee..628b77c 100644
>> --- a/block/dirty-bitmap.c
>> +++ b/block/dirty-bitmap.c
>> @@ -231,7 +231,7 @@ static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
>>      BdrvDirtyBitmap *bm, *next;
>>      QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
>>          if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
>> -            assert(!bitmap->active_iterators);
>> +            assert(!bm->active_iterators);
> 
> Same comment as for v4, this should be squashed into the previous patch.
> 
> Max
> 

Ah, replied too soon on #1. Thanks :)

Re: [Qemu-devel] [PATCH v5 04/10] block: Support meta dirty bitmap

[John Snow]

On 06/22/2016 11:53 AM, Max Reitz wrote:
> On 03.06.2016 06:32, Fam Zheng wrote:
>> The added group of operations enables tracking of the changed bits in
>> the dirty bitmap.
>>
>> Signed-off-by: Fam Zheng <famz@redhat.com>
>> ---
>>  block/dirty-bitmap.c         | 52 ++++++++++++++++++++++++++++++++++++++++++++
>>  include/block/dirty-bitmap.h |  9 ++++++++
>>  2 files changed, 61 insertions(+)
>>
>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>> index 628b77c..9c53c56 100644
>> --- a/block/dirty-bitmap.c
>> +++ b/block/dirty-bitmap.c
>> @@ -38,6 +38,7 @@
>>   */
>>  struct BdrvDirtyBitmap {
>>      HBitmap *bitmap;            /* Dirty sector bitmap implementation */
>> +    HBitmap *meta;              /* Meta dirty bitmap */
>>      BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
>>      char *name;                 /* Optional non-empty unique ID */
>>      int64_t size;               /* Size of the bitmap (Number of sectors) */
>> @@ -103,6 +104,56 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
>>      return bitmap;
>>  }
>>  
>> +/* bdrv_create_meta_dirty_bitmap
>> + *
>> + * Create a meta dirty bitmap that tracks the changes of bits in @bitmap. I.e.
>> + * when a dirty status bit in @bitmap is changed (either from reset to set or
>> + * the other way around), its respective meta dirty bitmap bit will be marked
>> + * dirty as well.
> 
> Not wrong, but I'd like a note here that this is not an
> when-and-only-when relationship, i.e. that bits in the meta bitmap may
> be set even without the tracked bits in the dirty bitmap having changed.
> 

How?

You mean, if the caller manually starts setting things in the meta
bitmap object?

That's their fault then, isn't it?

> Maybe this should be mentioned somewhere in patch 2, too. Or maybe only
> in patch 2.
> 
>> + *
>> + * @bitmap: the block dirty bitmap for which to create a meta dirty bitmap.
>> + * @chunk_size: how many bytes of bitmap data does each bit in the meta bitmap
>> + * track.
>> + */
>> +void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>> +                                   int chunk_size)
>> +{
>> +    assert(!bitmap->meta);
>> +    bitmap->meta = hbitmap_create_meta(bitmap->bitmap,
>> +                                       chunk_size * BITS_PER_BYTE);
>> +}
>> +
>> +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
>> +{
>> +    assert(bitmap->meta);
>> +    hbitmap_free_meta(bitmap->bitmap);
>> +    bitmap->meta = NULL;
>> +}
>> +
>> +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
>> +                               BdrvDirtyBitmap *bitmap, int64_t sector,
>> +                               int nb_sectors)
>> +{
>> +    uint64_t i;
>> +    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
>> +
>> +    /* To optimize: we can make hbitmap to internally check the range in a
>> +     * coarse level, or at least do it word by word. */
> 
> We could also multiply gran by the granularity of the meta bitmap. Each
> bit of the meta bitmap tracks at least eight bits of the dirty bitmap,
> so we're calling hbitmap_get() at least eight times as often as
> necessary here.
> 
> Or we just use int gran = hbitmap_granularity(bitmap->meta);.
> 
> Not exactly wrong, though, so:
> 
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> 
>> +    for (i = sector; i < sector + nb_sectors; i += gran) {
>> +        if (hbitmap_get(bitmap->meta, i)) {
>> +            return true;
>> +        }
>> +    }
>> +    return false;
>> +}
> 

Re: [Qemu-devel] [PATCH v5 07/10] hbitmap: serialization

[John Snow]

On 06/28/2016 10:15 AM, Vladimir Sementsov-Ogievskiy wrote:
> On 03.06.2016 07:32, 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>
>> Reviewed-by: Max Reitz <mreitz@redhat.com>
>> ---
>>   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 f8ed058..26cac7d 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 13c0df5..70dc99b 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -395,6 +395,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, 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;
>> +
> 
> I think it would be better to memcpy the whole part and then loop with
> cpu_to_le64. This loop will go out from compilation for LE case (I
> hope), so in LE case it would be just one memcpy. However in BE case it
> should be better to memcpy large part first and then convert words.

I tried this out on a 64MB chunk of memory on my x86-64 system: both
approaches were roughly the same speed. I couldn't produce a tangible
difference.

LE-vs-BE conversion made a big difference, but even on the version where
we memcpy all-at-once and then perform no-ops, it wasn't noticeably
different or faster than the bunch-of-memcpy approach.

Going to consider this a premature optimization.

>> +    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;
>> +
> 
> the same here.
>> +    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;
> 
> 

Re: [Qemu-devel] [PATCH v5 04/10] block: Support meta dirty bitmap

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 4879 bytes --]

On 14.07.2016 22:00, John Snow wrote:
> On 06/22/2016 11:53 AM, Max Reitz wrote:
>> On 03.06.2016 06:32, Fam Zheng wrote:
>>> The added group of operations enables tracking of the changed bits in
>>> the dirty bitmap.
>>>
>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>> ---
>>>  block/dirty-bitmap.c         | 52 ++++++++++++++++++++++++++++++++++++++++++++
>>>  include/block/dirty-bitmap.h |  9 ++++++++
>>>  2 files changed, 61 insertions(+)
>>>
>>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>>> index 628b77c..9c53c56 100644
>>> --- a/block/dirty-bitmap.c
>>> +++ b/block/dirty-bitmap.c
>>> @@ -38,6 +38,7 @@
>>>   */
>>>  struct BdrvDirtyBitmap {
>>>      HBitmap *bitmap;            /* Dirty sector bitmap implementation */
>>> +    HBitmap *meta;              /* Meta dirty bitmap */
>>>      BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
>>>      char *name;                 /* Optional non-empty unique ID */
>>>      int64_t size;               /* Size of the bitmap (Number of sectors) */
>>> @@ -103,6 +104,56 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
>>>      return bitmap;
>>>  }
>>>  
>>> +/* bdrv_create_meta_dirty_bitmap
>>> + *
>>> + * Create a meta dirty bitmap that tracks the changes of bits in @bitmap. I.e.
>>> + * when a dirty status bit in @bitmap is changed (either from reset to set or
>>> + * the other way around), its respective meta dirty bitmap bit will be marked
>>> + * dirty as well.
>>
>> Not wrong, but I'd like a note here that this is not an
>> when-and-only-when relationship, i.e. that bits in the meta bitmap may
>> be set even without the tracked bits in the dirty bitmap having changed.
>>
> 
> How?
> 
> You mean, if the caller manually starts setting things in the meta
> bitmap object?
> 
> That's their fault then, isn't it?

No, I mean something that I mentioned in a reply to some previous
version (the patch adding the test):

http://lists.nongnu.org/archive/html/qemu-block/2016-03/msg00332.html

Fam's reply is here:

http://lists.nongnu.org/archive/html/qemu-block/2016-06/msg00097.html

(Interesting how that reply took nearly three months and yours took
nearly one, there most be something about this series that makes
replying to replies very cumbersome :-))

What I meant by “then it would update meta” is that it would update *all
of the range* even though only a single bit has actually been changed.

So the answer to your “how” is: See patch 2, the changes to
hbitmap_set() (and hbitmap_reset()). If any of the bits in the given
range is changed, all of the range is marked as having changed in the
meta bitmap.

So all we guarantee is that every time a bit is changed, the
corresponding bit in the meta bitmap will be set. But we do not
guarantee that a bit in the meta bitmap stays cleared as long as the
corresponding range of the underlying bitmap stays the same.

Max

> 
>> Maybe this should be mentioned somewhere in patch 2, too. Or maybe only
>> in patch 2.
>>
>>> + *
>>> + * @bitmap: the block dirty bitmap for which to create a meta dirty bitmap.
>>> + * @chunk_size: how many bytes of bitmap data does each bit in the meta bitmap
>>> + * track.
>>> + */
>>> +void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>>> +                                   int chunk_size)
>>> +{
>>> +    assert(!bitmap->meta);
>>> +    bitmap->meta = hbitmap_create_meta(bitmap->bitmap,
>>> +                                       chunk_size * BITS_PER_BYTE);
>>> +}
>>> +
>>> +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
>>> +{
>>> +    assert(bitmap->meta);
>>> +    hbitmap_free_meta(bitmap->bitmap);
>>> +    bitmap->meta = NULL;
>>> +}
>>> +
>>> +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
>>> +                               BdrvDirtyBitmap *bitmap, int64_t sector,
>>> +                               int nb_sectors)
>>> +{
>>> +    uint64_t i;
>>> +    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
>>> +
>>> +    /* To optimize: we can make hbitmap to internally check the range in a
>>> +     * coarse level, or at least do it word by word. */
>>
>> We could also multiply gran by the granularity of the meta bitmap. Each
>> bit of the meta bitmap tracks at least eight bits of the dirty bitmap,
>> so we're calling hbitmap_get() at least eight times as often as
>> necessary here.
>>
>> Or we just use int gran = hbitmap_granularity(bitmap->meta);.
>>
>> Not exactly wrong, though, so:
>>
>> Reviewed-by: Max Reitz <mreitz@redhat.com>
>>
>>> +    for (i = sector; i < sector + nb_sectors; i += gran) {
>>> +        if (hbitmap_get(bitmap->meta, i)) {
>>> +            return true;
>>> +        }
>>> +    }
>>> +    return false;
>>> +}
>>
> 



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 498 bytes --]

Re: [Qemu-devel] [PATCH v5 04/10] block: Support meta dirty bitmap

[Max Reitz]

[-- Attachment #1: Type: text/plain, Size: 5395 bytes --]

On 15.07.2016 14:04, Max Reitz wrote:
> On 14.07.2016 22:00, John Snow wrote:
>> On 06/22/2016 11:53 AM, Max Reitz wrote:
>>> On 03.06.2016 06:32, Fam Zheng wrote:
>>>> The added group of operations enables tracking of the changed bits in
>>>> the dirty bitmap.
>>>>
>>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>>> ---
>>>>  block/dirty-bitmap.c         | 52 ++++++++++++++++++++++++++++++++++++++++++++
>>>>  include/block/dirty-bitmap.h |  9 ++++++++
>>>>  2 files changed, 61 insertions(+)
>>>>
>>>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>>>> index 628b77c..9c53c56 100644
>>>> --- a/block/dirty-bitmap.c
>>>> +++ b/block/dirty-bitmap.c
>>>> @@ -38,6 +38,7 @@
>>>>   */
>>>>  struct BdrvDirtyBitmap {
>>>>      HBitmap *bitmap;            /* Dirty sector bitmap implementation */
>>>> +    HBitmap *meta;              /* Meta dirty bitmap */
>>>>      BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
>>>>      char *name;                 /* Optional non-empty unique ID */
>>>>      int64_t size;               /* Size of the bitmap (Number of sectors) */
>>>> @@ -103,6 +104,56 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
>>>>      return bitmap;
>>>>  }
>>>>  
>>>> +/* bdrv_create_meta_dirty_bitmap
>>>> + *
>>>> + * Create a meta dirty bitmap that tracks the changes of bits in @bitmap. I.e.
>>>> + * when a dirty status bit in @bitmap is changed (either from reset to set or
>>>> + * the other way around), its respective meta dirty bitmap bit will be marked
>>>> + * dirty as well.
>>>
>>> Not wrong, but I'd like a note here that this is not an
>>> when-and-only-when relationship, i.e. that bits in the meta bitmap may
>>> be set even without the tracked bits in the dirty bitmap having changed.
>>>
>>
>> How?
>>
>> You mean, if the caller manually starts setting things in the meta
>> bitmap object?
>>
>> That's their fault then, isn't it?
> 
> No, I mean something that I mentioned in a reply to some previous
> version (the patch adding the test):
> 
> http://lists.nongnu.org/archive/html/qemu-block/2016-03/msg00332.html
> 
> Fam's reply is here:
> 
> http://lists.nongnu.org/archive/html/qemu-block/2016-06/msg00097.html
> 
> (Interesting how that reply took nearly three months and yours took
> nearly one, there most be something about this series that makes
> replying to replies very cumbersome :-))

I just remembered that it's very much justified now, as you have only
recently adopted this series.

It's just always funny to get a “What are you talking about?” reply to
some nagging I sent out long enough in the past that I can't even
remember myself, so I have to look it up, too.

Sorry :-)

Max

> What I meant by “then it would update meta” is that it would update *all
> of the range* even though only a single bit has actually been changed.
> 
> So the answer to your “how” is: See patch 2, the changes to
> hbitmap_set() (and hbitmap_reset()). If any of the bits in the given
> range is changed, all of the range is marked as having changed in the
> meta bitmap.
> 
> So all we guarantee is that every time a bit is changed, the
> corresponding bit in the meta bitmap will be set. But we do not
> guarantee that a bit in the meta bitmap stays cleared as long as the
> corresponding range of the underlying bitmap stays the same.
> 
> Max
> 
>>
>>> Maybe this should be mentioned somewhere in patch 2, too. Or maybe only
>>> in patch 2.
>>>
>>>> + *
>>>> + * @bitmap: the block dirty bitmap for which to create a meta dirty bitmap.
>>>> + * @chunk_size: how many bytes of bitmap data does each bit in the meta bitmap
>>>> + * track.
>>>> + */
>>>> +void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>>>> +                                   int chunk_size)
>>>> +{
>>>> +    assert(!bitmap->meta);
>>>> +    bitmap->meta = hbitmap_create_meta(bitmap->bitmap,
>>>> +                                       chunk_size * BITS_PER_BYTE);
>>>> +}
>>>> +
>>>> +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
>>>> +{
>>>> +    assert(bitmap->meta);
>>>> +    hbitmap_free_meta(bitmap->bitmap);
>>>> +    bitmap->meta = NULL;
>>>> +}
>>>> +
>>>> +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
>>>> +                               BdrvDirtyBitmap *bitmap, int64_t sector,
>>>> +                               int nb_sectors)
>>>> +{
>>>> +    uint64_t i;
>>>> +    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
>>>> +
>>>> +    /* To optimize: we can make hbitmap to internally check the range in a
>>>> +     * coarse level, or at least do it word by word. */
>>>
>>> We could also multiply gran by the granularity of the meta bitmap. Each
>>> bit of the meta bitmap tracks at least eight bits of the dirty bitmap,
>>> so we're calling hbitmap_get() at least eight times as often as
>>> necessary here.
>>>
>>> Or we just use int gran = hbitmap_granularity(bitmap->meta);.
>>>
>>> Not exactly wrong, though, so:
>>>
>>> Reviewed-by: Max Reitz <mreitz@redhat.com>
>>>
>>>> +    for (i = sector; i < sector + nb_sectors; i += gran) {
>>>> +        if (hbitmap_get(bitmap->meta, i)) {
>>>> +            return true;
>>>> +        }
>>>> +    }
>>>> +    return false;
>>>> +}
>>>
>>
> 
> 



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 498 bytes --]

Re: [Qemu-devel] [PATCH v5 04/10] block: Support meta dirty bitmap

[John Snow]

On 07/15/2016 08:04 AM, Max Reitz wrote:
> On 14.07.2016 22:00, John Snow wrote:
>> On 06/22/2016 11:53 AM, Max Reitz wrote:
>>> On 03.06.2016 06:32, Fam Zheng wrote:
>>>> The added group of operations enables tracking of the changed bits in
>>>> the dirty bitmap.
>>>>
>>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>>> ---
>>>>  block/dirty-bitmap.c         | 52 ++++++++++++++++++++++++++++++++++++++++++++
>>>>  include/block/dirty-bitmap.h |  9 ++++++++
>>>>  2 files changed, 61 insertions(+)
>>>>
>>>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>>>> index 628b77c..9c53c56 100644
>>>> --- a/block/dirty-bitmap.c
>>>> +++ b/block/dirty-bitmap.c
>>>> @@ -38,6 +38,7 @@
>>>>   */
>>>>  struct BdrvDirtyBitmap {
>>>>      HBitmap *bitmap;            /* Dirty sector bitmap implementation */
>>>> +    HBitmap *meta;              /* Meta dirty bitmap */
>>>>      BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
>>>>      char *name;                 /* Optional non-empty unique ID */
>>>>      int64_t size;               /* Size of the bitmap (Number of sectors) */
>>>> @@ -103,6 +104,56 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
>>>>      return bitmap;
>>>>  }
>>>>  
>>>> +/* bdrv_create_meta_dirty_bitmap
>>>> + *
>>>> + * Create a meta dirty bitmap that tracks the changes of bits in @bitmap. I.e.
>>>> + * when a dirty status bit in @bitmap is changed (either from reset to set or
>>>> + * the other way around), its respective meta dirty bitmap bit will be marked
>>>> + * dirty as well.
>>>
>>> Not wrong, but I'd like a note here that this is not an
>>> when-and-only-when relationship, i.e. that bits in the meta bitmap may
>>> be set even without the tracked bits in the dirty bitmap having changed.
>>>
>>
>> How?
>>
>> You mean, if the caller manually starts setting things in the meta
>> bitmap object?
>>
>> That's their fault then, isn't it?
> 
> No, I mean something that I mentioned in a reply to some previous
> version (the patch adding the test):
> 
> http://lists.nongnu.org/archive/html/qemu-block/2016-03/msg00332.html
> 
> Fam's reply is here:
> 
> http://lists.nongnu.org/archive/html/qemu-block/2016-06/msg00097.html
> 
> (Interesting how that reply took nearly three months and yours took
> nearly one, there most be something about this series that makes
> replying to replies very cumbersome :-))
> 

https://media.giphy.com/media/waG6HzLWKIkhi/giphy.gif

> What I meant by “then it would update meta” is that it would update *all
> of the range* even though only a single bit has actually been changed.
> 

Aha, I understand exactly now, thanks.

> So the answer to your “how” is: See patch 2, the changes to
> hbitmap_set() (and hbitmap_reset()). If any of the bits in the given
> range is changed, all of the range is marked as having changed in the
> meta bitmap.
> 
> So all we guarantee is that every time a bit is changed, the
> corresponding bit in the meta bitmap will be set. But we do not
> guarantee that a bit in the meta bitmap stays cleared as long as the
> corresponding range of the underlying bitmap stays the same.
> 
> Max
> 

I'll work on a followup patch to improve it.

>>
>>> Maybe this should be mentioned somewhere in patch 2, too. Or maybe only
>>> in patch 2.
>>>
>>>> + *
>>>> + * @bitmap: the block dirty bitmap for which to create a meta dirty bitmap.
>>>> + * @chunk_size: how many bytes of bitmap data does each bit in the meta bitmap
>>>> + * track.
>>>> + */
>>>> +void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>>>> +                                   int chunk_size)
>>>> +{
>>>> +    assert(!bitmap->meta);
>>>> +    bitmap->meta = hbitmap_create_meta(bitmap->bitmap,
>>>> +                                       chunk_size * BITS_PER_BYTE);
>>>> +}
>>>> +
>>>> +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
>>>> +{
>>>> +    assert(bitmap->meta);
>>>> +    hbitmap_free_meta(bitmap->bitmap);
>>>> +    bitmap->meta = NULL;
>>>> +}
>>>> +
>>>> +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
>>>> +                               BdrvDirtyBitmap *bitmap, int64_t sector,
>>>> +                               int nb_sectors)
>>>> +{
>>>> +    uint64_t i;
>>>> +    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
>>>> +
>>>> +    /* To optimize: we can make hbitmap to internally check the range in a
>>>> +     * coarse level, or at least do it word by word. */
>>>
>>> We could also multiply gran by the granularity of the meta bitmap. Each
>>> bit of the meta bitmap tracks at least eight bits of the dirty bitmap,
>>> so we're calling hbitmap_get() at least eight times as often as
>>> necessary here.
>>>
>>> Or we just use int gran = hbitmap_granularity(bitmap->meta);.
>>>
>>> Not exactly wrong, though, so:
>>>
>>> Reviewed-by: Max Reitz <mreitz@redhat.com>
>>>
>>>> +    for (i = sector; i < sector + nb_sectors; i += gran) {
>>>> +        if (hbitmap_get(bitmap->meta, i)) {
>>>> +            return true;
>>>> +        }
>>>> +    }
>>>> +    return false;
>>>> +}
>>>
>>
> 
> 

Re: [Qemu-devel] [PATCH v5 04/10] block: Support meta dirty bitmap

[Fam Zheng]

On Fri, 07/15 14:10, Max Reitz wrote:
> 
> I just remembered that it's very much justified now, as you have only
> recently adopted this series.
> 
> It's just always funny to get a “What are you talking about?” reply to
> some nagging I sent out long enough in the past that I can't even
> remember myself, so I have to look it up, too.
> 
> Sorry :-)

This is my fault, the delays were mostly because the motivation of this series
went away from my hands (QBM) and I handed it off to John not quite promptedly.

Fam