[Qemu-devel] [PATCH v4 00/15] Dirty bitmap changes for migration/persistence work

[Qemu-devel] [PATCH v4 00/15] Dirty bitmap changes for migration/persistence work

[Fam Zheng]

v4: Rebase.
    Add rev-by from John in patches 1-5, 7, 8.
    Remove BdrvDirtyBitmap typedef from dirty-bitmap.h in patch 4. [Max]
    Add assertion on bm->meta in patch 9. [John]

Two major features are added to block dirty bitmap (and underlying HBitmap) in
this series: meta bitmap and serialization, together with all other supportive
patches.

Both operations are common in dirty bitmap migration and persistence: they need
to find whether and which part of the dirty bitmap in question has changed with
meta dirty bitmap, and they need to write it to the target with serialization.


Fam Zheng (13):
  backup: Use Bitmap to replace "s->bitmap"
  block: Include hbitmap.h in block.h
  typedefs: Add BdrvDirtyBitmap
  block: Move block dirty bitmap code to separate files
  block: Remove unused typedef of BlockDriverDirtyHandler
  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.c                      | 360 -----------------------------
 block/Makefile.objs          |   2 +-
 block/backup.c               |  25 +-
 block/dirty-bitmap.c         | 535 +++++++++++++++++++++++++++++++++++++++++++
 block/mirror.c               |  15 +-
 include/block/block.h        |  40 +---
 include/block/dirty-bitmap.h |  75 ++++++
 include/qemu/hbitmap.h       |  96 ++++++++
 include/qemu/typedefs.h      |   2 +
 tests/test-hbitmap.c         | 255 +++++++++++++++++++++
 util/hbitmap.c               | 203 ++++++++++++++--
 11 files changed, 1177 insertions(+), 431 deletions(-)
 create mode 100644 block/dirty-bitmap.c
 create mode 100644 include/block/dirty-bitmap.h

-- 
2.4.3

[Qemu-devel] [PATCH v4 01/15] backup: Use Bitmap to replace "s->bitmap"

[Fam Zheng]

"s->bitmap" tracks done sectors, we only check bit states without using any
iterator which HBitmap is good for. Switch to "Bitmap" which is simpler and
more memory efficient.

Meanwhile, rename it to done_bitmap, to reflect the intention.

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 block/backup.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/block/backup.c b/block/backup.c
index 0f1b1bc..ab3e345 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -20,6 +20,7 @@
 #include "qapi/qmp/qerror.h"
 #include "qemu/ratelimit.h"
 #include "sysemu/block-backend.h"
+#include "qemu/bitmap.h"
 
 #define BACKUP_CLUSTER_SIZE_DEFAULT (1 << 16)
 #define SLICE_TIME 100000000ULL /* ns */
@@ -42,7 +43,7 @@ typedef struct BackupBlockJob {
     BlockdevOnError on_target_error;
     CoRwlock flush_rwlock;
     uint64_t sectors_read;
-    HBitmap *bitmap;
+    unsigned long *done_bitmap;
     int64_t cluster_size;
     QLIST_HEAD(, CowRequest) inflight_reqs;
 } BackupBlockJob;
@@ -116,7 +117,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
     cow_request_begin(&cow_request, job, start, end);
 
     for (; start < end; start++) {
-        if (hbitmap_get(job->bitmap, start)) {
+        if (test_bit(start, job->done_bitmap)) {
             trace_backup_do_cow_skip(job, start);
             continue; /* already copied */
         }
@@ -167,7 +168,7 @@ static int coroutine_fn backup_do_cow(BlockDriverState *bs,
             goto out;
         }
 
-        hbitmap_set(job->bitmap, start, 1);
+        set_bit(start, job->done_bitmap);
 
         /* Publish progress, guest I/O counts as progress too.  Note that the
          * offset field is an opaque progress value, it is not a disk offset.
@@ -399,7 +400,7 @@ static void coroutine_fn backup_run(void *opaque)
     start = 0;
     end = DIV_ROUND_UP(job->common.len, job->cluster_size);
 
-    job->bitmap = hbitmap_alloc(end, 0);
+    job->done_bitmap = bitmap_new(end);
 
     bdrv_set_enable_write_cache(target, true);
     if (target->blk) {
@@ -480,7 +481,7 @@ static void coroutine_fn backup_run(void *opaque)
     /* wait until pending backup_do_cow() calls have completed */
     qemu_co_rwlock_wrlock(&job->flush_rwlock);
     qemu_co_rwlock_unlock(&job->flush_rwlock);
-    hbitmap_free(job->bitmap);
+    g_free(job->done_bitmap);
 
     if (target->blk) {
         blk_iostatus_disable(target->blk);
-- 
2.4.3

[Qemu-devel] [PATCH v4 02/15] block: Include hbitmap.h in block.h

[Fam Zheng]

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 include/block/block.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/block/block.h b/include/block/block.h
index 1c4f4d8..00827f7 100644
--- a/include/block/block.h
+++ b/include/block/block.h
@@ -8,6 +8,7 @@
 #include "block/accounting.h"
 #include "qapi/qmp/qobject.h"
 #include "qapi-types.h"
+#include "qemu/hbitmap.h"
 
 /* block.c */
 typedef struct BlockDriver BlockDriver;
@@ -475,7 +476,6 @@ void *qemu_try_blockalign(BlockDriverState *bs, size_t size);
 void *qemu_try_blockalign0(BlockDriverState *bs, size_t size);
 bool bdrv_qiov_is_aligned(BlockDriverState *bs, QEMUIOVector *qiov);
 
-struct HBitmapIter;
 typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
 BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
                                           uint32_t granularity,
-- 
2.4.3

[Qemu-devel] [PATCH v4 03/15] typedefs: Add BdrvDirtyBitmap

[Fam Zheng]

Following patches to refactor and move block dirty bitmap code could use
this.

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 include/block/block.h   | 1 -
 include/qemu/typedefs.h | 1 +
 2 files changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/block/block.h b/include/block/block.h
index 00827f7..5ee9b8f 100644
--- a/include/block/block.h
+++ b/include/block/block.h
@@ -476,7 +476,6 @@ void *qemu_try_blockalign(BlockDriverState *bs, size_t size);
 void *qemu_try_blockalign0(BlockDriverState *bs, size_t size);
 bool bdrv_qiov_is_aligned(BlockDriverState *bs, QEMUIOVector *qiov);
 
-typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
 BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
                                           uint32_t granularity,
                                           const char *name,
diff --git a/include/qemu/typedefs.h b/include/qemu/typedefs.h
index 9a5ead6..fd039e0 100644
--- a/include/qemu/typedefs.h
+++ b/include/qemu/typedefs.h
@@ -10,6 +10,7 @@ typedef struct AddressSpace AddressSpace;
 typedef struct AioContext AioContext;
 typedef struct AllwinnerAHCIState AllwinnerAHCIState;
 typedef struct AudioState AudioState;
+typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
 typedef struct BlockBackend BlockBackend;
 typedef struct BlockBackendRootState BlockBackendRootState;
 typedef struct BlockDriverState BlockDriverState;
-- 
2.4.3

[Qemu-devel] [PATCH v4 04/15] block: Move block dirty bitmap code to separate files

[Fam Zheng]

The only code change is making bdrv_dirty_bitmap_truncate public. It is
used in block.c.

Also two long lines (bdrv_get_dirty) are wrapped.

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 block.c                      | 360 ----------------------------------------
 block/Makefile.objs          |   2 +-
 block/dirty-bitmap.c         | 387 +++++++++++++++++++++++++++++++++++++++++++
 include/block/block.h        |  35 +---
 include/block/dirty-bitmap.h |  44 +++++
 5 files changed, 433 insertions(+), 395 deletions(-)
 create mode 100644 block/dirty-bitmap.c
 create mode 100644 include/block/dirty-bitmap.h

diff --git a/block.c b/block.c
index ba24b8e..3dbaf11 100644
--- a/block.c
+++ b/block.c
@@ -53,23 +53,6 @@
 #include <windows.h>
 #endif
 
-/**
- * A BdrvDirtyBitmap can be in three possible states:
- * (1) successor is NULL and disabled is false: full r/w mode
- * (2) successor is NULL and disabled is true: read only mode ("disabled")
- * (3) successor is set: frozen mode.
- *     A frozen bitmap cannot be renamed, deleted, anonymized, cleared, set,
- *     or enabled. A frozen bitmap can only abdicate() or reclaim().
- */
-struct BdrvDirtyBitmap {
-    HBitmap *bitmap;            /* Dirty sector bitmap implementation */
-    BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
-    char *name;                 /* Optional non-empty unique ID */
-    int64_t size;               /* Size of the bitmap (Number of sectors) */
-    bool disabled;              /* Bitmap is read-only */
-    QLIST_ENTRY(BdrvDirtyBitmap) list;
-};
-
 #define NOT_DONE 0x7fffffff /* used while emulated sync operation in progress */
 
 struct BdrvStates bdrv_states = QTAILQ_HEAD_INITIALIZER(bdrv_states);
@@ -88,9 +71,6 @@ static int bdrv_open_inherit(BlockDriverState **pbs, const char *filename,
                              BlockDriverState *parent,
                              const BdrvChildRole *child_role, Error **errp);
 
-static void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
-static void bdrv_release_named_dirty_bitmaps(BlockDriverState *bs);
-
 /* If non-zero, use only whitelisted block drivers */
 static int use_bdrv_whitelist;
 
@@ -3431,346 +3411,6 @@ void bdrv_lock_medium(BlockDriverState *bs, bool locked)
     }
 }
 
-BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs, const char *name)
-{
-    BdrvDirtyBitmap *bm;
-
-    assert(name);
-    QLIST_FOREACH(bm, &bs->dirty_bitmaps, list) {
-        if (bm->name && !strcmp(name, bm->name)) {
-            return bm;
-        }
-    }
-    return NULL;
-}
-
-void bdrv_dirty_bitmap_make_anon(BdrvDirtyBitmap *bitmap)
-{
-    assert(!bdrv_dirty_bitmap_frozen(bitmap));
-    g_free(bitmap->name);
-    bitmap->name = NULL;
-}
-
-BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
-                                          uint32_t granularity,
-                                          const char *name,
-                                          Error **errp)
-{
-    int64_t bitmap_size;
-    BdrvDirtyBitmap *bitmap;
-    uint32_t sector_granularity;
-
-    assert((granularity & (granularity - 1)) == 0);
-
-    if (name && bdrv_find_dirty_bitmap(bs, name)) {
-        error_setg(errp, "Bitmap already exists: %s", name);
-        return NULL;
-    }
-    sector_granularity = granularity >> BDRV_SECTOR_BITS;
-    assert(sector_granularity);
-    bitmap_size = bdrv_nb_sectors(bs);
-    if (bitmap_size < 0) {
-        error_setg_errno(errp, -bitmap_size, "could not get length of device");
-        errno = -bitmap_size;
-        return NULL;
-    }
-    bitmap = g_new0(BdrvDirtyBitmap, 1);
-    bitmap->bitmap = hbitmap_alloc(bitmap_size, ctz32(sector_granularity));
-    bitmap->size = bitmap_size;
-    bitmap->name = g_strdup(name);
-    bitmap->disabled = false;
-    QLIST_INSERT_HEAD(&bs->dirty_bitmaps, bitmap, list);
-    return bitmap;
-}
-
-bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap)
-{
-    return bitmap->successor;
-}
-
-bool bdrv_dirty_bitmap_enabled(BdrvDirtyBitmap *bitmap)
-{
-    return !(bitmap->disabled || bitmap->successor);
-}
-
-DirtyBitmapStatus bdrv_dirty_bitmap_status(BdrvDirtyBitmap *bitmap)
-{
-    if (bdrv_dirty_bitmap_frozen(bitmap)) {
-        return DIRTY_BITMAP_STATUS_FROZEN;
-    } else if (!bdrv_dirty_bitmap_enabled(bitmap)) {
-        return DIRTY_BITMAP_STATUS_DISABLED;
-    } else {
-        return DIRTY_BITMAP_STATUS_ACTIVE;
-    }
-}
-
-/**
- * Create a successor bitmap destined to replace this bitmap after an operation.
- * Requires that the bitmap is not frozen and has no successor.
- */
-int bdrv_dirty_bitmap_create_successor(BlockDriverState *bs,
-                                       BdrvDirtyBitmap *bitmap, Error **errp)
-{
-    uint64_t granularity;
-    BdrvDirtyBitmap *child;
-
-    if (bdrv_dirty_bitmap_frozen(bitmap)) {
-        error_setg(errp, "Cannot create a successor for a bitmap that is "
-                   "currently frozen");
-        return -1;
-    }
-    assert(!bitmap->successor);
-
-    /* Create an anonymous successor */
-    granularity = bdrv_dirty_bitmap_granularity(bitmap);
-    child = bdrv_create_dirty_bitmap(bs, granularity, NULL, errp);
-    if (!child) {
-        return -1;
-    }
-
-    /* Successor will be on or off based on our current state. */
-    child->disabled = bitmap->disabled;
-
-    /* Install the successor and freeze the parent */
-    bitmap->successor = child;
-    return 0;
-}
-
-/**
- * For a bitmap with a successor, yield our name to the successor,
- * delete the old bitmap, and return a handle to the new bitmap.
- */
-BdrvDirtyBitmap *bdrv_dirty_bitmap_abdicate(BlockDriverState *bs,
-                                            BdrvDirtyBitmap *bitmap,
-                                            Error **errp)
-{
-    char *name;
-    BdrvDirtyBitmap *successor = bitmap->successor;
-
-    if (successor == NULL) {
-        error_setg(errp, "Cannot relinquish control if "
-                   "there's no successor present");
-        return NULL;
-    }
-
-    name = bitmap->name;
-    bitmap->name = NULL;
-    successor->name = name;
-    bitmap->successor = NULL;
-    bdrv_release_dirty_bitmap(bs, bitmap);
-
-    return successor;
-}
-
-/**
- * In cases of failure where we can no longer safely delete the parent,
- * we may wish to re-join the parent and child/successor.
- * The merged parent will be un-frozen, but not explicitly re-enabled.
- */
-BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap(BlockDriverState *bs,
-                                           BdrvDirtyBitmap *parent,
-                                           Error **errp)
-{
-    BdrvDirtyBitmap *successor = parent->successor;
-
-    if (!successor) {
-        error_setg(errp, "Cannot reclaim a successor when none is present");
-        return NULL;
-    }
-
-    if (!hbitmap_merge(parent->bitmap, successor->bitmap)) {
-        error_setg(errp, "Merging of parent and successor bitmap failed");
-        return NULL;
-    }
-    bdrv_release_dirty_bitmap(bs, successor);
-    parent->successor = NULL;
-
-    return parent;
-}
-
-/**
- * Truncates _all_ bitmaps attached to a BDS.
- */
-static void bdrv_dirty_bitmap_truncate(BlockDriverState *bs)
-{
-    BdrvDirtyBitmap *bitmap;
-    uint64_t size = bdrv_nb_sectors(bs);
-
-    QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
-        assert(!bdrv_dirty_bitmap_frozen(bitmap));
-        hbitmap_truncate(bitmap->bitmap, size);
-        bitmap->size = size;
-    }
-}
-
-static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
-                                                  BdrvDirtyBitmap *bitmap,
-                                                  bool only_named)
-{
-    BdrvDirtyBitmap *bm, *next;
-    QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
-        if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
-            assert(!bdrv_dirty_bitmap_frozen(bm));
-            QLIST_REMOVE(bm, list);
-            hbitmap_free(bm->bitmap);
-            g_free(bm->name);
-            g_free(bm);
-
-            if (bitmap) {
-                return;
-            }
-        }
-    }
-}
-
-void bdrv_release_dirty_bitmap(BlockDriverState *bs, BdrvDirtyBitmap *bitmap)
-{
-    bdrv_do_release_matching_dirty_bitmap(bs, bitmap, false);
-}
-
-/**
- * Release all named dirty bitmaps attached to a BDS (for use in bdrv_close()).
- * There must not be any frozen bitmaps attached.
- */
-static void bdrv_release_named_dirty_bitmaps(BlockDriverState *bs)
-{
-    bdrv_do_release_matching_dirty_bitmap(bs, NULL, true);
-}
-
-void bdrv_disable_dirty_bitmap(BdrvDirtyBitmap *bitmap)
-{
-    assert(!bdrv_dirty_bitmap_frozen(bitmap));
-    bitmap->disabled = true;
-}
-
-void bdrv_enable_dirty_bitmap(BdrvDirtyBitmap *bitmap)
-{
-    assert(!bdrv_dirty_bitmap_frozen(bitmap));
-    bitmap->disabled = false;
-}
-
-BlockDirtyInfoList *bdrv_query_dirty_bitmaps(BlockDriverState *bs)
-{
-    BdrvDirtyBitmap *bm;
-    BlockDirtyInfoList *list = NULL;
-    BlockDirtyInfoList **plist = &list;
-
-    QLIST_FOREACH(bm, &bs->dirty_bitmaps, list) {
-        BlockDirtyInfo *info = g_new0(BlockDirtyInfo, 1);
-        BlockDirtyInfoList *entry = g_new0(BlockDirtyInfoList, 1);
-        info->count = bdrv_get_dirty_count(bm);
-        info->granularity = bdrv_dirty_bitmap_granularity(bm);
-        info->has_name = !!bm->name;
-        info->name = g_strdup(bm->name);
-        info->status = bdrv_dirty_bitmap_status(bm);
-        entry->value = info;
-        *plist = entry;
-        plist = &entry->next;
-    }
-
-    return list;
-}
-
-int bdrv_get_dirty(BlockDriverState *bs, BdrvDirtyBitmap *bitmap, int64_t sector)
-{
-    if (bitmap) {
-        return hbitmap_get(bitmap->bitmap, sector);
-    } else {
-        return 0;
-    }
-}
-
-/**
- * Chooses a default granularity based on the existing cluster size,
- * but clamped between [4K, 64K]. Defaults to 64K in the case that there
- * is no cluster size information available.
- */
-uint32_t bdrv_get_default_bitmap_granularity(BlockDriverState *bs)
-{
-    BlockDriverInfo bdi;
-    uint32_t granularity;
-
-    if (bdrv_get_info(bs, &bdi) >= 0 && bdi.cluster_size > 0) {
-        granularity = MAX(4096, bdi.cluster_size);
-        granularity = MIN(65536, granularity);
-    } else {
-        granularity = 65536;
-    }
-
-    return granularity;
-}
-
-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)
-{
-    hbitmap_iter_init(hbi, bitmap->bitmap, 0);
-}
-
-void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
-                           int64_t cur_sector, int nr_sectors)
-{
-    assert(bdrv_dirty_bitmap_enabled(bitmap));
-    hbitmap_set(bitmap->bitmap, cur_sector, nr_sectors);
-}
-
-void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
-                             int64_t cur_sector, int nr_sectors)
-{
-    assert(bdrv_dirty_bitmap_enabled(bitmap));
-    hbitmap_reset(bitmap->bitmap, cur_sector, nr_sectors);
-}
-
-void bdrv_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap, HBitmap **out)
-{
-    assert(bdrv_dirty_bitmap_enabled(bitmap));
-    if (!out) {
-        hbitmap_reset_all(bitmap->bitmap);
-    } else {
-        HBitmap *backup = bitmap->bitmap;
-        bitmap->bitmap = hbitmap_alloc(bitmap->size,
-                                       hbitmap_granularity(backup));
-        *out = backup;
-    }
-}
-
-void bdrv_undo_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap, HBitmap *in)
-{
-    HBitmap *tmp = bitmap->bitmap;
-    assert(bdrv_dirty_bitmap_enabled(bitmap));
-    bitmap->bitmap = in;
-    hbitmap_free(tmp);
-}
-
-void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
-                    int nr_sectors)
-{
-    BdrvDirtyBitmap *bitmap;
-    QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
-        if (!bdrv_dirty_bitmap_enabled(bitmap)) {
-            continue;
-        }
-        hbitmap_set(bitmap->bitmap, cur_sector, nr_sectors);
-    }
-}
-
-/**
- * Advance an HBitmapIter to an arbitrary offset.
- */
-void bdrv_set_dirty_iter(HBitmapIter *hbi, int64_t offset)
-{
-    assert(hbi->hb);
-    hbitmap_iter_init(hbi, hbi->hb, offset);
-}
-
-int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
-{
-    return hbitmap_count(bitmap->bitmap);
-}
-
 /* Get a reference to bs */
 void bdrv_ref(BlockDriverState *bs)
 {
diff --git a/block/Makefile.objs b/block/Makefile.objs
index 58ef2ef..cdd8655 100644
--- a/block/Makefile.objs
+++ b/block/Makefile.objs
@@ -20,7 +20,7 @@ block-obj-$(CONFIG_RBD) += rbd.o
 block-obj-$(CONFIG_GLUSTERFS) += gluster.o
 block-obj-$(CONFIG_ARCHIPELAGO) += archipelago.o
 block-obj-$(CONFIG_LIBSSH2) += ssh.o
-block-obj-y += accounting.o
+block-obj-y += accounting.o dirty-bitmap.o
 block-obj-y += write-threshold.o
 
 common-obj-y += stream.o
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
new file mode 100644
index 0000000..556e1d1
--- /dev/null
+++ b/block/dirty-bitmap.c
@@ -0,0 +1,387 @@
+/*
+ * Block Dirty Bitmap
+ *
+ * Copyright (c) 2016 Red Hat. Inc
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+#include "qemu/osdep.h"
+#include "config-host.h"
+#include "qemu-common.h"
+#include "trace.h"
+#include "block/block_int.h"
+#include "block/blockjob.h"
+
+/**
+ * A BdrvDirtyBitmap can be in three possible states:
+ * (1) successor is NULL and disabled is false: full r/w mode
+ * (2) successor is NULL and disabled is true: read only mode ("disabled")
+ * (3) successor is set: frozen mode.
+ *     A frozen bitmap cannot be renamed, deleted, anonymized, cleared, set,
+ *     or enabled. A frozen bitmap can only abdicate() or reclaim().
+ */
+struct BdrvDirtyBitmap {
+    HBitmap *bitmap;            /* Dirty sector bitmap implementation */
+    BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
+    char *name;                 /* Optional non-empty unique ID */
+    int64_t size;               /* Size of the bitmap (Number of sectors) */
+    bool disabled;              /* Bitmap is read-only */
+    QLIST_ENTRY(BdrvDirtyBitmap) list;
+};
+
+BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs, const char *name)
+{
+    BdrvDirtyBitmap *bm;
+
+    assert(name);
+    QLIST_FOREACH(bm, &bs->dirty_bitmaps, list) {
+        if (bm->name && !strcmp(name, bm->name)) {
+            return bm;
+        }
+    }
+    return NULL;
+}
+
+void bdrv_dirty_bitmap_make_anon(BdrvDirtyBitmap *bitmap)
+{
+    assert(!bdrv_dirty_bitmap_frozen(bitmap));
+    g_free(bitmap->name);
+    bitmap->name = NULL;
+}
+
+BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
+                                          uint32_t granularity,
+                                          const char *name,
+                                          Error **errp)
+{
+    int64_t bitmap_size;
+    BdrvDirtyBitmap *bitmap;
+    uint32_t sector_granularity;
+
+    assert((granularity & (granularity - 1)) == 0);
+
+    if (name && bdrv_find_dirty_bitmap(bs, name)) {
+        error_setg(errp, "Bitmap already exists: %s", name);
+        return NULL;
+    }
+    sector_granularity = granularity >> BDRV_SECTOR_BITS;
+    assert(sector_granularity);
+    bitmap_size = bdrv_nb_sectors(bs);
+    if (bitmap_size < 0) {
+        error_setg_errno(errp, -bitmap_size, "could not get length of device");
+        errno = -bitmap_size;
+        return NULL;
+    }
+    bitmap = g_new0(BdrvDirtyBitmap, 1);
+    bitmap->bitmap = hbitmap_alloc(bitmap_size, ctz32(sector_granularity));
+    bitmap->size = bitmap_size;
+    bitmap->name = g_strdup(name);
+    bitmap->disabled = false;
+    QLIST_INSERT_HEAD(&bs->dirty_bitmaps, bitmap, list);
+    return bitmap;
+}
+
+bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap)
+{
+    return bitmap->successor;
+}
+
+bool bdrv_dirty_bitmap_enabled(BdrvDirtyBitmap *bitmap)
+{
+    return !(bitmap->disabled || bitmap->successor);
+}
+
+DirtyBitmapStatus bdrv_dirty_bitmap_status(BdrvDirtyBitmap *bitmap)
+{
+    if (bdrv_dirty_bitmap_frozen(bitmap)) {
+        return DIRTY_BITMAP_STATUS_FROZEN;
+    } else if (!bdrv_dirty_bitmap_enabled(bitmap)) {
+        return DIRTY_BITMAP_STATUS_DISABLED;
+    } else {
+        return DIRTY_BITMAP_STATUS_ACTIVE;
+    }
+}
+
+/**
+ * Create a successor bitmap destined to replace this bitmap after an operation.
+ * Requires that the bitmap is not frozen and has no successor.
+ */
+int bdrv_dirty_bitmap_create_successor(BlockDriverState *bs,
+                                       BdrvDirtyBitmap *bitmap, Error **errp)
+{
+    uint64_t granularity;
+    BdrvDirtyBitmap *child;
+
+    if (bdrv_dirty_bitmap_frozen(bitmap)) {
+        error_setg(errp, "Cannot create a successor for a bitmap that is "
+                   "currently frozen");
+        return -1;
+    }
+    assert(!bitmap->successor);
+
+    /* Create an anonymous successor */
+    granularity = bdrv_dirty_bitmap_granularity(bitmap);
+    child = bdrv_create_dirty_bitmap(bs, granularity, NULL, errp);
+    if (!child) {
+        return -1;
+    }
+
+    /* Successor will be on or off based on our current state. */
+    child->disabled = bitmap->disabled;
+
+    /* Install the successor and freeze the parent */
+    bitmap->successor = child;
+    return 0;
+}
+
+/**
+ * For a bitmap with a successor, yield our name to the successor,
+ * delete the old bitmap, and return a handle to the new bitmap.
+ */
+BdrvDirtyBitmap *bdrv_dirty_bitmap_abdicate(BlockDriverState *bs,
+                                            BdrvDirtyBitmap *bitmap,
+                                            Error **errp)
+{
+    char *name;
+    BdrvDirtyBitmap *successor = bitmap->successor;
+
+    if (successor == NULL) {
+        error_setg(errp, "Cannot relinquish control if "
+                   "there's no successor present");
+        return NULL;
+    }
+
+    name = bitmap->name;
+    bitmap->name = NULL;
+    successor->name = name;
+    bitmap->successor = NULL;
+    bdrv_release_dirty_bitmap(bs, bitmap);
+
+    return successor;
+}
+
+/**
+ * In cases of failure where we can no longer safely delete the parent,
+ * we may wish to re-join the parent and child/successor.
+ * The merged parent will be un-frozen, but not explicitly re-enabled.
+ */
+BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap(BlockDriverState *bs,
+                                           BdrvDirtyBitmap *parent,
+                                           Error **errp)
+{
+    BdrvDirtyBitmap *successor = parent->successor;
+
+    if (!successor) {
+        error_setg(errp, "Cannot reclaim a successor when none is present");
+        return NULL;
+    }
+
+    if (!hbitmap_merge(parent->bitmap, successor->bitmap)) {
+        error_setg(errp, "Merging of parent and successor bitmap failed");
+        return NULL;
+    }
+    bdrv_release_dirty_bitmap(bs, successor);
+    parent->successor = NULL;
+
+    return parent;
+}
+
+/**
+ * Truncates _all_ bitmaps attached to a BDS.
+ */
+void bdrv_dirty_bitmap_truncate(BlockDriverState *bs)
+{
+    BdrvDirtyBitmap *bitmap;
+    uint64_t size = bdrv_nb_sectors(bs);
+
+    QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
+        assert(!bdrv_dirty_bitmap_frozen(bitmap));
+        hbitmap_truncate(bitmap->bitmap, size);
+        bitmap->size = size;
+    }
+}
+
+static void bdrv_do_release_matching_dirty_bitmap(BlockDriverState *bs,
+                                                  BdrvDirtyBitmap *bitmap,
+                                                  bool only_named)
+{
+    BdrvDirtyBitmap *bm, *next;
+    QLIST_FOREACH_SAFE(bm, &bs->dirty_bitmaps, list, next) {
+        if ((!bitmap || bm == bitmap) && (!only_named || bm->name)) {
+            assert(!bdrv_dirty_bitmap_frozen(bm));
+            QLIST_REMOVE(bm, list);
+            hbitmap_free(bm->bitmap);
+            g_free(bm->name);
+            g_free(bm);
+
+            if (bitmap) {
+                return;
+            }
+        }
+    }
+}
+
+void bdrv_release_dirty_bitmap(BlockDriverState *bs, BdrvDirtyBitmap *bitmap)
+{
+    bdrv_do_release_matching_dirty_bitmap(bs, bitmap, false);
+}
+
+/**
+ * Release all named dirty bitmaps attached to a BDS (for use in bdrv_close()).
+ * There must not be any frozen bitmaps attached.
+ */
+void bdrv_release_named_dirty_bitmaps(BlockDriverState *bs)
+{
+    bdrv_do_release_matching_dirty_bitmap(bs, NULL, true);
+}
+
+void bdrv_disable_dirty_bitmap(BdrvDirtyBitmap *bitmap)
+{
+    assert(!bdrv_dirty_bitmap_frozen(bitmap));
+    bitmap->disabled = true;
+}
+
+void bdrv_enable_dirty_bitmap(BdrvDirtyBitmap *bitmap)
+{
+    assert(!bdrv_dirty_bitmap_frozen(bitmap));
+    bitmap->disabled = false;
+}
+
+BlockDirtyInfoList *bdrv_query_dirty_bitmaps(BlockDriverState *bs)
+{
+    BdrvDirtyBitmap *bm;
+    BlockDirtyInfoList *list = NULL;
+    BlockDirtyInfoList **plist = &list;
+
+    QLIST_FOREACH(bm, &bs->dirty_bitmaps, list) {
+        BlockDirtyInfo *info = g_new0(BlockDirtyInfo, 1);
+        BlockDirtyInfoList *entry = g_new0(BlockDirtyInfoList, 1);
+        info->count = bdrv_get_dirty_count(bm);
+        info->granularity = bdrv_dirty_bitmap_granularity(bm);
+        info->has_name = !!bm->name;
+        info->name = g_strdup(bm->name);
+        info->status = bdrv_dirty_bitmap_status(bm);
+        entry->value = info;
+        *plist = entry;
+        plist = &entry->next;
+    }
+
+    return list;
+}
+
+int bdrv_get_dirty(BlockDriverState *bs, BdrvDirtyBitmap *bitmap,
+                   int64_t sector)
+{
+    if (bitmap) {
+        return hbitmap_get(bitmap->bitmap, sector);
+    } else {
+        return 0;
+    }
+}
+
+/**
+ * Chooses a default granularity based on the existing cluster size,
+ * but clamped between [4K, 64K]. Defaults to 64K in the case that there
+ * is no cluster size information available.
+ */
+uint32_t bdrv_get_default_bitmap_granularity(BlockDriverState *bs)
+{
+    BlockDriverInfo bdi;
+    uint32_t granularity;
+
+    if (bdrv_get_info(bs, &bdi) >= 0 && bdi.cluster_size > 0) {
+        granularity = MAX(4096, bdi.cluster_size);
+        granularity = MIN(65536, granularity);
+    } else {
+        granularity = 65536;
+    }
+
+    return granularity;
+}
+
+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)
+{
+    hbitmap_iter_init(hbi, bitmap->bitmap, 0);
+}
+
+void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
+                           int64_t cur_sector, int nr_sectors)
+{
+    assert(bdrv_dirty_bitmap_enabled(bitmap));
+    hbitmap_set(bitmap->bitmap, cur_sector, nr_sectors);
+}
+
+void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
+                             int64_t cur_sector, int nr_sectors)
+{
+    assert(bdrv_dirty_bitmap_enabled(bitmap));
+    hbitmap_reset(bitmap->bitmap, cur_sector, nr_sectors);
+}
+
+void bdrv_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap, HBitmap **out)
+{
+    assert(bdrv_dirty_bitmap_enabled(bitmap));
+    if (!out) {
+        hbitmap_reset_all(bitmap->bitmap);
+    } else {
+        HBitmap *backup = bitmap->bitmap;
+        bitmap->bitmap = hbitmap_alloc(bitmap->size,
+                                       hbitmap_granularity(backup));
+        *out = backup;
+    }
+}
+
+void bdrv_undo_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap, HBitmap *in)
+{
+    HBitmap *tmp = bitmap->bitmap;
+    assert(bdrv_dirty_bitmap_enabled(bitmap));
+    bitmap->bitmap = in;
+    hbitmap_free(tmp);
+}
+
+void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
+                    int nr_sectors)
+{
+    BdrvDirtyBitmap *bitmap;
+    QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
+        if (!bdrv_dirty_bitmap_enabled(bitmap)) {
+            continue;
+        }
+        hbitmap_set(bitmap->bitmap, cur_sector, nr_sectors);
+    }
+}
+
+/**
+ * Advance an HBitmapIter to an arbitrary offset.
+ */
+void bdrv_set_dirty_iter(HBitmapIter *hbi, int64_t offset)
+{
+    assert(hbi->hb);
+    hbitmap_iter_init(hbi, hbi->hb, offset);
+}
+
+int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap)
+{
+    return hbitmap_count(bitmap->bitmap);
+}
diff --git a/include/block/block.h b/include/block/block.h
index 5ee9b8f..3fbd70d 100644
--- a/include/block/block.h
+++ b/include/block/block.h
@@ -6,6 +6,7 @@
 #include "qemu/option.h"
 #include "qemu/coroutine.h"
 #include "block/accounting.h"
+#include "block/dirty-bitmap.h"
 #include "qapi/qmp/qobject.h"
 #include "qapi-types.h"
 #include "qemu/hbitmap.h"
@@ -476,40 +477,6 @@ void *qemu_try_blockalign(BlockDriverState *bs, size_t size);
 void *qemu_try_blockalign0(BlockDriverState *bs, size_t size);
 bool bdrv_qiov_is_aligned(BlockDriverState *bs, QEMUIOVector *qiov);
 
-BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
-                                          uint32_t granularity,
-                                          const char *name,
-                                          Error **errp);
-int bdrv_dirty_bitmap_create_successor(BlockDriverState *bs,
-                                       BdrvDirtyBitmap *bitmap,
-                                       Error **errp);
-BdrvDirtyBitmap *bdrv_dirty_bitmap_abdicate(BlockDriverState *bs,
-                                            BdrvDirtyBitmap *bitmap,
-                                            Error **errp);
-BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap(BlockDriverState *bs,
-                                           BdrvDirtyBitmap *bitmap,
-                                           Error **errp);
-BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs,
-                                        const char *name);
-void bdrv_dirty_bitmap_make_anon(BdrvDirtyBitmap *bitmap);
-void bdrv_release_dirty_bitmap(BlockDriverState *bs, BdrvDirtyBitmap *bitmap);
-void bdrv_disable_dirty_bitmap(BdrvDirtyBitmap *bitmap);
-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);
-bool bdrv_dirty_bitmap_enabled(BdrvDirtyBitmap *bitmap);
-bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap);
-DirtyBitmapStatus bdrv_dirty_bitmap_status(BdrvDirtyBitmap *bitmap);
-int bdrv_get_dirty(BlockDriverState *bs, BdrvDirtyBitmap *bitmap, int64_t sector);
-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);
-int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
-
 void bdrv_enable_copy_on_read(BlockDriverState *bs);
 void bdrv_disable_copy_on_read(BlockDriverState *bs);
 
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
new file mode 100644
index 0000000..80afe60
--- /dev/null
+++ b/include/block/dirty-bitmap.h
@@ -0,0 +1,44 @@
+#ifndef BLOCK_DIRTY_BITMAP_H
+#define BLOCK_DIRTY_BITMAP_H
+
+#include "qemu-common.h"
+#include "qemu/hbitmap.h"
+
+BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
+                                          uint32_t granularity,
+                                          const char *name,
+                                          Error **errp);
+int bdrv_dirty_bitmap_create_successor(BlockDriverState *bs,
+                                       BdrvDirtyBitmap *bitmap,
+                                       Error **errp);
+BdrvDirtyBitmap *bdrv_dirty_bitmap_abdicate(BlockDriverState *bs,
+                                            BdrvDirtyBitmap *bitmap,
+                                            Error **errp);
+BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap(BlockDriverState *bs,
+                                           BdrvDirtyBitmap *bitmap,
+                                           Error **errp);
+BdrvDirtyBitmap *bdrv_find_dirty_bitmap(BlockDriverState *bs,
+                                        const char *name);
+void bdrv_dirty_bitmap_make_anon(BdrvDirtyBitmap *bitmap);
+void bdrv_release_dirty_bitmap(BlockDriverState *bs, BdrvDirtyBitmap *bitmap);
+void bdrv_release_named_dirty_bitmaps(BlockDriverState *bs);
+void bdrv_disable_dirty_bitmap(BdrvDirtyBitmap *bitmap);
+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);
+bool bdrv_dirty_bitmap_enabled(BdrvDirtyBitmap *bitmap);
+bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap);
+DirtyBitmapStatus bdrv_dirty_bitmap_status(BdrvDirtyBitmap *bitmap);
+int bdrv_get_dirty(BlockDriverState *bs, BdrvDirtyBitmap *bitmap,
+                   int64_t sector);
+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);
+int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
+void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
+
+#endif
-- 
2.4.3

[Qemu-devel] [PATCH v4 05/15] block: Remove unused typedef of BlockDriverDirtyHandler

[Fam Zheng]

Signed-off-by: Fam Zheng <famz@redhat.com>
Reviewed-by: John Snow <jsnow@redhat.com>
---
 include/block/block.h | 2 --
 1 file changed, 2 deletions(-)

diff --git a/include/block/block.h b/include/block/block.h
index 3fbd70d..ff1933a 100644
--- a/include/block/block.h
+++ b/include/block/block.h
@@ -322,8 +322,6 @@ BlockDriverState *check_to_replace_node(BlockDriverState *parent_bs,
                                         const char *node_name, Error **errp);
 
 /* async block I/O */
-typedef void BlockDriverDirtyHandler(BlockDriverState *bs, int64_t sector,
-                                     int sector_num);
 BlockAIOCB *bdrv_aio_readv(BlockDriverState *bs, int64_t sector_num,
                            QEMUIOVector *iov, int nb_sectors,
                            BlockCompletionFunc *cb, void *opaque);
-- 
2.4.3

[Qemu-devel] [PATCH v4 06/15] 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.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               | 15 +++++++++------
 include/block/dirty-bitmap.h |  7 +++++--
 include/qemu/typedefs.h      |  1 +
 5 files changed, 56 insertions(+), 20 deletions(-)

diff --git a/block/backup.c b/block/backup.c
index ab3e345..f5a5e03 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -330,14 +330,14 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
     int64_t last_cluster = -1;
     int64_t sectors_per_cluster = cluster_size_sectors(job);
     BlockDriverState *bs = job->common.bs;
-    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 */
@@ -349,7 +349,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(bs, cluster * sectors_per_cluster,
                                     sectors_per_cluster, &error_is_read,
@@ -357,7 +357,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);
         }
@@ -365,7 +365,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;
@@ -377,6 +377,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 556e1d1..16f73b2 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 an 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 9635fa8..87a5a86 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;
@@ -304,10 +304,11 @@ 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_dirty_iter_free(s->dbi);
+        s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 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);
     }
@@ -330,7 +331,7 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
             mirror_wait_for_io(s);
             /* Now retry.  */
         } else {
-            hbitmap_next = hbitmap_iter_next(&s->hbi);
+            hbitmap_next = bdrv_dirty_iter_next(s->dbi);
             assert(hbitmap_next == next_sector);
             nb_chunks++;
         }
@@ -577,7 +578,8 @@ static void coroutine_fn mirror_run(void *opaque)
         }
     }
 
-    bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
+    bdrv_dirty_iter_free(s->dbi);
+    s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
     for (;;) {
         uint64_t delay_ns = 0;
         int64_t cnt;
@@ -688,6 +690,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);
     if (s->target->blk) {
         blk_iostatus_disable(s->target->blk);
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 fd039e0..7c39f0f 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.4.3

[Qemu-devel] [PATCH v4 07/15] 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         | 66 ++++++++++++++++++++++++++++++++++++++------------
 3 files changed, 69 insertions(+), 16 deletions(-)

diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 16f73b2..0a188f2 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..2d3d04c 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]);
     }
@@ -491,3 +511,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.4.3

[Qemu-devel] [PATCH v4 08/15] 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.4.3

[Qemu-devel] [PATCH v4 09/15] 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 0a188f2..a2413c0 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.4.3

[Qemu-devel] [PATCH v4 10/15] 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 a2413c0..50bb9e0 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.4.3

[Qemu-devel] [PATCH v4 11/15] 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 50bb9e0..295788d 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.4.3

[Qemu-devel] [PATCH v4 12/15] 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>
---
 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 2d3d04c..5f02c17 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.4.3

[Qemu-devel] [PATCH v4 13/15] 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 295788d..3aef91a 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.4.3

[Qemu-devel] [PATCH v4 14/15] 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.4.3

[Qemu-devel] [PATCH v4 15/15] 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>
---
 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 3aef91a..3992eb5 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.4.3

Re: [Qemu-devel] [PATCH v4 06/15] block: Hide HBitmap in block dirty bitmap interface

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 5739 bytes --]

On 08.03.2016 05:44, 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.c.

It's block/dirty-bitmap.c now. :-)

> 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               | 15 +++++++++------
>  include/block/dirty-bitmap.h |  7 +++++--
>  include/qemu/typedefs.h      |  1 +
>  5 files changed, 56 insertions(+), 20 deletions(-)
> 

[...]

> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 556e1d1..16f73b2 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c

[...]

> @@ -373,12 +401,11 @@ void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
>  }
>  
>  /**
> - * Advance an HBitmapIter to an arbitrary offset.
> + * Advance an BdrvDirtyBitmapIter to an arbitrary offset.

This should be "a BdrvDirtyBitmapIter".

>   */
> -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 9635fa8..87a5a86 100644
> --- a/block/mirror.c
> +++ b/block/mirror.c

[...]

> @@ -304,10 +304,11 @@ 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_dirty_iter_free(s->dbi);
> +        s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);

Works, but wouldn't bdrv_set_dirty_iter(s->dbi, 0); suffice?

> +        sector_num = bdrv_dirty_iter_next(s->dbi);
>          trace_mirror_restart_iter(s, bdrv_get_dirty_count(s->dirty_bitmap));
>          assert(sector_num >= 0);
>      }
> @@ -330,7 +331,7 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>              mirror_wait_for_io(s);
>              /* Now retry.  */
>          } else {
> -            hbitmap_next = hbitmap_iter_next(&s->hbi);
> +            hbitmap_next = bdrv_dirty_iter_next(s->dbi);

It would make sense to change this variable's name from hbitmap_next to
e.g. bdrv_dirty_next or bs_next_dirty.

>              assert(hbitmap_next == next_sector);
>              nb_chunks++;
>          }
> @@ -577,7 +578,8 @@ static void coroutine_fn mirror_run(void *opaque)
>          }
>      }
>  
> -    bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
> +    bdrv_dirty_iter_free(s->dbi);
> +    s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);

Again, bdrv_set_dirty_iter(s->dbi, 0); should work just fine.

Since this patch is technically correct, I could still imagine giving an
R-b, but I'm really reluctant to do so because of the
bdrv_dirty_iter_free()/bdrv_dirty_iter_new() pairs.

Max

>      for (;;) {
>          uint64_t delay_ns = 0;
>          int64_t cnt;
> @@ -688,6 +690,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);
>      if (s->target->blk) {
>          blk_iostatus_disable(s->target->blk);
> 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 fd039e0..7c39f0f 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;
> 



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

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

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 2351 bytes --]

On 08.03.2016 05:44, Fam Zheng wrote:
> v4: Rebase.
>     Add rev-by from John in patches 1-5, 7, 8.
>     Remove BdrvDirtyBitmap typedef from dirty-bitmap.h in patch 4. [Max]
>     Add assertion on bm->meta in patch 9. [John]
> 
> Two major features are added to block dirty bitmap (and underlying HBitmap) in
> this series: meta bitmap and serialization, together with all other supportive
> patches.
> 
> Both operations are common in dirty bitmap migration and persistence: they need
> to find whether and which part of the dirty bitmap in question has changed with
> meta dirty bitmap, and they need to write it to the target with serialization.
> 
> 
> Fam Zheng (13):
>   backup: Use Bitmap to replace "s->bitmap"
>   block: Include hbitmap.h in block.h
>   typedefs: Add BdrvDirtyBitmap
>   block: Move block dirty bitmap code to separate files
>   block: Remove unused typedef of BlockDriverDirtyHandler
>   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.c                      | 360 -----------------------------
>  block/Makefile.objs          |   2 +-
>  block/backup.c               |  25 +-
>  block/dirty-bitmap.c         | 535 +++++++++++++++++++++++++++++++++++++++++++
>  block/mirror.c               |  15 +-
>  include/block/block.h        |  40 +---
>  include/block/dirty-bitmap.h |  75 ++++++
>  include/qemu/hbitmap.h       |  96 ++++++++
>  include/qemu/typedefs.h      |   2 +
>  tests/test-hbitmap.c         | 255 +++++++++++++++++++++
>  util/hbitmap.c               | 203 ++++++++++++++--
>  11 files changed, 1177 insertions(+), 431 deletions(-)
>  create mode 100644 block/dirty-bitmap.c
>  create mode 100644 include/block/dirty-bitmap.h

Thanks, applied patches 1 through 5 to my block tree (because of the
large code movement in patch 4):

https://github.com/XanClic/qemu/commits/block

Max


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

Re: [Qemu-devel] [PATCH v4 06/15] block: Hide HBitmap in block dirty bitmap interface

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 6095 bytes --]

On 11.03.2016 14:54, Max Reitz wrote:
> On 08.03.2016 05:44, 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.c.
> 
> It's block/dirty-bitmap.c now. :-)
> 
>> 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               | 15 +++++++++------
>>  include/block/dirty-bitmap.h |  7 +++++--
>>  include/qemu/typedefs.h      |  1 +
>>  5 files changed, 56 insertions(+), 20 deletions(-)
>>
> 
> [...]
> 
>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>> index 556e1d1..16f73b2 100644
>> --- a/block/dirty-bitmap.c
>> +++ b/block/dirty-bitmap.c
> 
> [...]
> 
>> @@ -373,12 +401,11 @@ void bdrv_set_dirty(BlockDriverState *bs, int64_t cur_sector,
>>  }
>>  
>>  /**
>> - * Advance an HBitmapIter to an arbitrary offset.
>> + * Advance an BdrvDirtyBitmapIter to an arbitrary offset.
> 
> This should be "a BdrvDirtyBitmapIter".
> 
>>   */
>> -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 9635fa8..87a5a86 100644
>> --- a/block/mirror.c
>> +++ b/block/mirror.c
> 
> [...]
> 
>> @@ -304,10 +304,11 @@ 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_dirty_iter_free(s->dbi);
>> +        s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
> 
> Works, but wouldn't bdrv_set_dirty_iter(s->dbi, 0); suffice?
> 
>> +        sector_num = bdrv_dirty_iter_next(s->dbi);
>>          trace_mirror_restart_iter(s, bdrv_get_dirty_count(s->dirty_bitmap));
>>          assert(sector_num >= 0);
>>      }
>> @@ -330,7 +331,7 @@ static uint64_t coroutine_fn mirror_iteration(MirrorBlockJob *s)
>>              mirror_wait_for_io(s);
>>              /* Now retry.  */
>>          } else {
>> -            hbitmap_next = hbitmap_iter_next(&s->hbi);
>> +            hbitmap_next = bdrv_dirty_iter_next(s->dbi);
> 
> It would make sense to change this variable's name from hbitmap_next to
> e.g. bdrv_dirty_next or bs_next_dirty.
> 
>>              assert(hbitmap_next == next_sector);
>>              nb_chunks++;
>>          }
>> @@ -577,7 +578,8 @@ static void coroutine_fn mirror_run(void *opaque)
>>          }
>>      }
>>  
>> -    bdrv_dirty_iter_init(s->dirty_bitmap, &s->hbi);
>> +    bdrv_dirty_iter_free(s->dbi);
>> +    s->dbi = bdrv_dirty_iter_new(s->dirty_bitmap, 0);
> 
> Again, bdrv_set_dirty_iter(s->dbi, 0); should work just fine.

OK, here it wouldn't because s->dbi is still NULL. Why do we need the
bdrv_dirty_iter_free(), then? It wasn't present in v3.

Max

> Since this patch is technically correct, I could still imagine giving an
> R-b, but I'm really reluctant to do so because of the
> bdrv_dirty_iter_free()/bdrv_dirty_iter_new() pairs.
> 
> Max
> 
>>      for (;;) {
>>          uint64_t delay_ns = 0;
>>          int64_t cnt;
>> @@ -688,6 +690,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);
>>      if (s->target->blk) {
>>          blk_iostatus_disable(s->target->blk);
>> 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 fd039e0..7c39f0f 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;
>>
> 
> 



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

Re: [Qemu-devel] [PATCH v4 07/15] HBitmap: Introduce "meta" bitmap to track bit changes

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 1087 bytes --]

On 08.03.2016 05:44, 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         | 66 ++++++++++++++++++++++++++++++++++++++------------
>  3 files changed, 69 insertions(+), 16 deletions(-)
> 
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 16f73b2..0a188f2 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);

I guess this should be squashed into patch 6. Good point, by the way,
yes, using bitmap is wrong here. :-)

Max


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

Re: [Qemu-devel] [PATCH v4 08/15] tests: Add test code for meta bitmap

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 6689 bytes --]

On 08.03.2016 05:44, 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(+)
> 
> 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);

Well, but if you'd do an hbitmap_set(data->hb, start, count + 1), then
it would update meta, right?

I forgot to mention in my reply to patch 7 that the check whether
anything in the range passed to hbitmap_set() has been changed in order
to determine whether all of that range should be set in the meta bitmap
seemed a bit excessive. I don't think this will hurt anyone, but still.

(So this is not a NACK, just a question.)

Max

> +
> +    /* 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;
> 



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

Re: [Qemu-devel] [PATCH v4 09/15] block: Support meta dirty bitmap

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 439 bytes --]

On 08.03.2016 05:45, 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(+)

Should we truncate the meta bitmaps in bdrv_dirty_bitmap_truncate()?

Max


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

Re: [Qemu-devel] [PATCH v4 11/15] block: Assert that bdrv_release_dirty_bitmap succeeded

[Max Reitz]

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

On 08.03.2016 05:45, 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 v4 12/15] hbitmap: serialization

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 7920 bytes --]

On 08.03.2016 05:45, Fam Zheng wrote:
> From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> 
> Functions to serialize / deserialize(restore) HBitmap. HBitmap should be
> saved to linear sequence of bits independently of endianness and bitmap
> array element (unsigned long) size. Therefore Little Endian is chosen.
> 
> These functions are appropriate for dirty bitmap migration, restoring
> the bitmap in several steps is available. To save performance, every
> step writes only the last level of the bitmap. All other levels are
> restored by hbitmap_deserialize_finish() as a last step of restoring.
> So, HBitmap is inconsistent while restoring.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> [Fix left shift operand to 1UL; add "finish" parameter. - Fam]
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  include/qemu/hbitmap.h |  79 ++++++++++++++++++++++++++++
>  util/hbitmap.c         | 137 +++++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 216 insertions(+)

[...]

> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 2d3d04c..5f02c17 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));

Looks a bit fishy, but I can't come up with anything better.

(Other than adding cpu_to_leul(); we already do have leul_to_cpu(), so
that wouldn't be too far off.)

> +
> +        memcpy(buf, &el, sizeof(el));

One could have used cpu_to_le32/64w((uint32/64_t *)buf, *cur); instead.

Maybe I'd like the following better:

#if BITS_PER_LONG == 32
cpu_to_le32w((uint32_t *)buf, *cur);
#elif BITS_PER_LONG == 64
cpu_to_le64w((uint64_t *)buf, *cur);
#else
#error Unknown long size
#endif

Or just

#else /* BITS_PER_LONG == 64 */

instead of the #elif. I think that's safe to assume.

> +        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);
> +        }

Here, I'd definitely like that variant better, i.e.

#if BITS_PER_LONG == 32
le32_to_cpuw(cur, *(uint32_t *)buf);
#else /* BITS_PER_LONG == 64 */
le64_to_cpuw(cur, *(uint64_t *)buf);
#endif

Unless a language lawyer NACKs this because the pointer cast violates
strict aliasing.

If so, I still strongly recommend replacing the if by an #if, not least
because this saves us the pointer cast on cur.

(Or does it? Maybe one still needs to explicitly cast an unsigned long *
to uint32_t * even if both have the same size. However, in that case we
can still do *cur = le32/64_to_cpu(*cur). The above would then become:

#if BITS_PER_LONG == 32
*cur = le32_to_cpu(*(uint32_t *)buf);
#else /* BITS_PER_LONG == 64 */
*cur = le64_to_cpu(*(uint64_t *)buf);
#endif

)

> +
> +        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; ) {

I'm always amazed of how much this notation (x-- > 0, or x --> 0, even
worse) confuses me. Or rather I'm always amazed of how much it confuses
me and how much other people love it (as opposed to me, who's rather
unhappy every time he doesn't use all of the three "parameters" for a
for loop).

This time I wondered why we start at HBITMAP_LEVELS - 1 -- that's the
ultimate and not the penultimate level after all. But of course, the
loop condition is evaluated before the loop is executed for the first
time, so we will indeed start at HBITMAP_LEVELS - 2.

So, yeah, this is correct.

> +        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) {

I hate using stand-alone pre-increment for scalars with a passion.

Unfortunately, checkpatch does not.

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

(All of the above are me just nagging and giving optional suggestions.)

> +            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;
> 



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

Re: [Qemu-devel] [PATCH v4 15/15] block: More operations for meta dirty bitmap

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 553 bytes --]

On 08.03.2016 05:45, Fam Zheng wrote:
> 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>
> ---
>  block/dirty-bitmap.c         | 19 +++++++++++++++++++
>  include/block/dirty-bitmap.h |  3 +++
>  2 files changed, 22 insertions(+)

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


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

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

[John Snow]

On 03/11/2016 08:57 AM, Max Reitz wrote:
> On 08.03.2016 05:44, Fam Zheng wrote:
>> v4: Rebase.
>>     Add rev-by from John in patches 1-5, 7, 8.
>>     Remove BdrvDirtyBitmap typedef from dirty-bitmap.h in patch 4. [Max]
>>     Add assertion on bm->meta in patch 9. [John]
>>
>> Two major features are added to block dirty bitmap (and underlying HBitmap) in
>> this series: meta bitmap and serialization, together with all other supportive
>> patches.
>>
>> Both operations are common in dirty bitmap migration and persistence: they need
>> to find whether and which part of the dirty bitmap in question has changed with
>> meta dirty bitmap, and they need to write it to the target with serialization.
>>
>>
>> Fam Zheng (13):
>>   backup: Use Bitmap to replace "s->bitmap"
>>   block: Include hbitmap.h in block.h
>>   typedefs: Add BdrvDirtyBitmap
>>   block: Move block dirty bitmap code to separate files
>>   block: Remove unused typedef of BlockDriverDirtyHandler
>>   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.c                      | 360 -----------------------------
>>  block/Makefile.objs          |   2 +-
>>  block/backup.c               |  25 +-
>>  block/dirty-bitmap.c         | 535 +++++++++++++++++++++++++++++++++++++++++++
>>  block/mirror.c               |  15 +-
>>  include/block/block.h        |  40 +---
>>  include/block/dirty-bitmap.h |  75 ++++++
>>  include/qemu/hbitmap.h       |  96 ++++++++
>>  include/qemu/typedefs.h      |   2 +
>>  tests/test-hbitmap.c         | 255 +++++++++++++++++++++
>>  util/hbitmap.c               | 203 ++++++++++++++--
>>  11 files changed, 1177 insertions(+), 431 deletions(-)
>>  create mode 100644 block/dirty-bitmap.c
>>  create mode 100644 include/block/dirty-bitmap.h
> 
> Thanks, applied patches 1 through 5 to my block tree (because of the
> large code movement in patch 4):
> 
> https://github.com/XanClic/qemu/commits/block
> 
> Max
> 

You're a saint, thank you :)

Re: [Qemu-devel] [PATCH v4 12/15] hbitmap: serialization

[Vladimir Sementsov-Ogievskiy]

On 11.03.2016 19:27, Max Reitz wrote:
> On 08.03.2016 05:45, Fam Zheng wrote:
>> From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>
>> Functions to serialize / deserialize(restore) HBitmap. HBitmap should be
>> saved to linear sequence of bits independently of endianness and bitmap
>> array element (unsigned long) size. Therefore Little Endian is chosen.
>>
>> These functions are appropriate for dirty bitmap migration, restoring
>> the bitmap in several steps is available. To save performance, every
>> step writes only the last level of the bitmap. All other levels are
>> restored by hbitmap_deserialize_finish() as a last step of restoring.
>> So, HBitmap is inconsistent while restoring.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> [Fix left shift operand to 1UL; add "finish" parameter. - Fam]
>> Signed-off-by: Fam Zheng <famz@redhat.com>
>> ---
>>   include/qemu/hbitmap.h |  79 ++++++++++++++++++++++++++++
>>   util/hbitmap.c         | 137 +++++++++++++++++++++++++++++++++++++++++++++++++
>>   2 files changed, 216 insertions(+)
> [...]
>
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index 2d3d04c..5f02c17 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));
> Looks a bit fishy, but I can't come up with anything better.
>
> (Other than adding cpu_to_leul(); we already do have leul_to_cpu(), so
> that wouldn't be too far off.)
>
>> +
>> +        memcpy(buf, &el, sizeof(el));
> One could have used cpu_to_le32/64w((uint32/64_t *)buf, *cur); instead.
>
> Maybe I'd like the following better:
>
> #if BITS_PER_LONG == 32
> cpu_to_le32w((uint32_t *)buf, *cur);
> #elif BITS_PER_LONG == 64
> cpu_to_le64w((uint64_t *)buf, *cur);
> #else
> #error Unknown long size
> #endif
>
> Or just
>
> #else /* BITS_PER_LONG == 64 */
>
> instead of the #elif. I think that's safe to assume.

I think (BITS_PER_LONG == 32 ? .. : ..) should be optimised away by 
compiler in any case.. However adding cpu_to_leul should be better.


>
>> +        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);
>> +        }
> Here, I'd definitely like that variant better, i.e.
>
> #if BITS_PER_LONG == 32
> le32_to_cpuw(cur, *(uint32_t *)buf);
> #else /* BITS_PER_LONG == 64 */
> le64_to_cpuw(cur, *(uint64_t *)buf);
> #endif
>
> Unless a language lawyer NACKs this because the pointer cast violates
> strict aliasing.
>
> If so, I still strongly recommend replacing the if by an #if, not least
> because this saves us the pointer cast on cur.
>
> (Or does it? Maybe one still needs to explicitly cast an unsigned long *
> to uint32_t * even if both have the same size. However, in that case we
> can still do *cur = le32/64_to_cpu(*cur). The above would then become:
>
> #if BITS_PER_LONG == 32
> *cur = le32_to_cpu(*(uint32_t *)buf);
> #else /* BITS_PER_LONG == 64 */
> *cur = le64_to_cpu(*(uint64_t *)buf);
> #endif
>
> )
>
>> +
>> +        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; ) {
> I'm always amazed of how much this notation (x-- > 0, or x --> 0, even
> worse) confuses me. Or rather I'm always amazed of how much it confuses
> me and how much other people love it (as opposed to me, who's rather
> unhappy every time he doesn't use all of the three "parameters" for a
> for loop).
>
> This time I wondered why we start at HBITMAP_LEVELS - 1 -- that's the
> ultimate and not the penultimate level after all. But of course, the
> loop condition is evaluated before the loop is executed for the first
> time, so we will indeed start at HBITMAP_LEVELS - 2.
>
> So, yeah, this is correct.

This strange notation is used in several places in hbitmap.c, so, I've 
reused it) I don't like it, but to fix it it should be fixed everywhere 
in the file as a separate patch I think..

>
>> +        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) {
> I hate using stand-alone pre-increment for scalars with a passion.

I just prefer to write it in the same way for scalars and iterators, for 
c and c++.

>
> Unfortunately, checkpatch does not.
>
> Reviewed-by: Max Reitz <mreitz@redhat.com>
>
> (All of the above are me just nagging and giving optional suggestions.)
>
>> +            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 v4 00/15] Dirty bitmap changes for migration/persistence work

[Vladimir Sementsov-Ogievskiy]

Hi!

Are you going to update the series in the near future?

On 08.03.2016 07:44, Fam Zheng wrote:
> v4: Rebase.
>      Add rev-by from John in patches 1-5, 7, 8.
>      Remove BdrvDirtyBitmap typedef from dirty-bitmap.h in patch 4. [Max]
>      Add assertion on bm->meta in patch 9. [John]
>
> Two major features are added to block dirty bitmap (and underlying HBitmap) in
> this series: meta bitmap and serialization, together with all other supportive
> patches.
>
> Both operations are common in dirty bitmap migration and persistence: they need
> to find whether and which part of the dirty bitmap in question has changed with
> meta dirty bitmap, and they need to write it to the target with serialization.
>
>
> Fam Zheng (13):
>    backup: Use Bitmap to replace "s->bitmap"
>    block: Include hbitmap.h in block.h
>    typedefs: Add BdrvDirtyBitmap
>    block: Move block dirty bitmap code to separate files
>    block: Remove unused typedef of BlockDriverDirtyHandler
>    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.c                      | 360 -----------------------------
>   block/Makefile.objs          |   2 +-
>   block/backup.c               |  25 +-
>   block/dirty-bitmap.c         | 535 +++++++++++++++++++++++++++++++++++++++++++
>   block/mirror.c               |  15 +-
>   include/block/block.h        |  40 +---
>   include/block/dirty-bitmap.h |  75 ++++++
>   include/qemu/hbitmap.h       |  96 ++++++++
>   include/qemu/typedefs.h      |   2 +
>   tests/test-hbitmap.c         | 255 +++++++++++++++++++++
>   util/hbitmap.c               | 203 ++++++++++++++--
>   11 files changed, 1177 insertions(+), 431 deletions(-)
>   create mode 100644 block/dirty-bitmap.c
>   create mode 100644 include/block/dirty-bitmap.h
>


-- 
Best regards,
Vladimir

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

[Fam Zheng]

On Wed, 05/25 17:45, Vladimir Sementsov-Ogievskiy wrote:
> Hi!
> 
> Are you going to update the series in the near future?

Yes, probably in a couple days.

Fam

> 
> On 08.03.2016 07:44, Fam Zheng wrote:
> > v4: Rebase.
> >      Add rev-by from John in patches 1-5, 7, 8.
> >      Remove BdrvDirtyBitmap typedef from dirty-bitmap.h in patch 4. [Max]
> >      Add assertion on bm->meta in patch 9. [John]
> > 
> > Two major features are added to block dirty bitmap (and underlying HBitmap) in
> > this series: meta bitmap and serialization, together with all other supportive
> > patches.
> > 
> > Both operations are common in dirty bitmap migration and persistence: they need
> > to find whether and which part of the dirty bitmap in question has changed with
> > meta dirty bitmap, and they need to write it to the target with serialization.
> > 
> > 
> > Fam Zheng (13):
> >    backup: Use Bitmap to replace "s->bitmap"
> >    block: Include hbitmap.h in block.h
> >    typedefs: Add BdrvDirtyBitmap
> >    block: Move block dirty bitmap code to separate files
> >    block: Remove unused typedef of BlockDriverDirtyHandler
> >    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.c                      | 360 -----------------------------
> >   block/Makefile.objs          |   2 +-
> >   block/backup.c               |  25 +-
> >   block/dirty-bitmap.c         | 535 +++++++++++++++++++++++++++++++++++++++++++
> >   block/mirror.c               |  15 +-
> >   include/block/block.h        |  40 +---
> >   include/block/dirty-bitmap.h |  75 ++++++
> >   include/qemu/hbitmap.h       |  96 ++++++++
> >   include/qemu/typedefs.h      |   2 +
> >   tests/test-hbitmap.c         | 255 +++++++++++++++++++++
> >   util/hbitmap.c               | 203 ++++++++++++++--
> >   11 files changed, 1177 insertions(+), 431 deletions(-)
> >   create mode 100644 block/dirty-bitmap.c
> >   create mode 100644 include/block/dirty-bitmap.h
> > 
> 
> 
> -- 
> Best regards,
> Vladimir
> 
> 

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

[Vladimir Sementsov-Ogievskiy]

Hi, what are the plans?

On 26.05.2016 03:47, Fam Zheng wrote:
> On Wed, 05/25 17:45, Vladimir Sementsov-Ogievskiy wrote:
>> Hi!
>>
>> Are you going to update the series in the near future?
> Yes, probably in a couple days.
>
> Fam
>
>> On 08.03.2016 07:44, Fam Zheng wrote:
>>> v4: Rebase.
>>>       Add rev-by from John in patches 1-5, 7, 8.
>>>       Remove BdrvDirtyBitmap typedef from dirty-bitmap.h in patch 4. [Max]
>>>       Add assertion on bm->meta in patch 9. [John]
>>>
>>> Two major features are added to block dirty bitmap (and underlying HBitmap) in
>>> this series: meta bitmap and serialization, together with all other supportive
>>> patches.
>>>
>>> Both operations are common in dirty bitmap migration and persistence: they need
>>> to find whether and which part of the dirty bitmap in question has changed with
>>> meta dirty bitmap, and they need to write it to the target with serialization.
>>>
>>>
>>> Fam Zheng (13):
>>>     backup: Use Bitmap to replace "s->bitmap"
>>>     block: Include hbitmap.h in block.h
>>>     typedefs: Add BdrvDirtyBitmap
>>>     block: Move block dirty bitmap code to separate files
>>>     block: Remove unused typedef of BlockDriverDirtyHandler
>>>     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.c                      | 360 -----------------------------
>>>    block/Makefile.objs          |   2 +-
>>>    block/backup.c               |  25 +-
>>>    block/dirty-bitmap.c         | 535 +++++++++++++++++++++++++++++++++++++++++++
>>>    block/mirror.c               |  15 +-
>>>    include/block/block.h        |  40 +---
>>>    include/block/dirty-bitmap.h |  75 ++++++
>>>    include/qemu/hbitmap.h       |  96 ++++++++
>>>    include/qemu/typedefs.h      |   2 +
>>>    tests/test-hbitmap.c         | 255 +++++++++++++++++++++
>>>    util/hbitmap.c               | 203 ++++++++++++++--
>>>    11 files changed, 1177 insertions(+), 431 deletions(-)
>>>    create mode 100644 block/dirty-bitmap.c
>>>    create mode 100644 include/block/dirty-bitmap.h
>>>
>>
>> -- 
>> Best regards,
>> Vladimir
>>
>>


-- 
Best regards,
Vladimir

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

[John Snow]

On 06/02/2016 07:43 AM, Vladimir Sementsov-Ogievskiy wrote:
> Hi, what are the plans?
> 

I'm not sure. Fam, part of this series was merged, wasn't it?

Do you have outstanding work that you'd like me to take over and push
through for you?

--js

> On 26.05.2016 03:47, Fam Zheng wrote:
>> On Wed, 05/25 17:45, Vladimir Sementsov-Ogievskiy wrote:
>>> Hi!
>>>
>>> Are you going to update the series in the near future?
>> Yes, probably in a couple days.
>>
>> Fam
>>
>>> On 08.03.2016 07:44, Fam Zheng wrote:
>>>> v4: Rebase.
>>>>       Add rev-by from John in patches 1-5, 7, 8.
>>>>       Remove BdrvDirtyBitmap typedef from dirty-bitmap.h in patch 4.
>>>> [Max]
>>>>       Add assertion on bm->meta in patch 9. [John]
>>>>
>>>> Two major features are added to block dirty bitmap (and underlying
>>>> HBitmap) in
>>>> this series: meta bitmap and serialization, together with all other
>>>> supportive
>>>> patches.
>>>>
>>>> Both operations are common in dirty bitmap migration and
>>>> persistence: they need
>>>> to find whether and which part of the dirty bitmap in question has
>>>> changed with
>>>> meta dirty bitmap, and they need to write it to the target with
>>>> serialization.
>>>>
>>>>
>>>> Fam Zheng (13):
>>>>     backup: Use Bitmap to replace "s->bitmap"
>>>>     block: Include hbitmap.h in block.h
>>>>     typedefs: Add BdrvDirtyBitmap
>>>>     block: Move block dirty bitmap code to separate files
>>>>     block: Remove unused typedef of BlockDriverDirtyHandler
>>>>     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.c                      | 360 -----------------------------
>>>>    block/Makefile.objs          |   2 +-
>>>>    block/backup.c               |  25 +-
>>>>    block/dirty-bitmap.c         | 535
>>>> +++++++++++++++++++++++++++++++++++++++++++
>>>>    block/mirror.c               |  15 +-
>>>>    include/block/block.h        |  40 +---
>>>>    include/block/dirty-bitmap.h |  75 ++++++
>>>>    include/qemu/hbitmap.h       |  96 ++++++++
>>>>    include/qemu/typedefs.h      |   2 +
>>>>    tests/test-hbitmap.c         | 255 +++++++++++++++++++++
>>>>    util/hbitmap.c               | 203 ++++++++++++++--
>>>>    11 files changed, 1177 insertions(+), 431 deletions(-)
>>>>    create mode 100644 block/dirty-bitmap.c
>>>>    create mode 100644 include/block/dirty-bitmap.h
>>>>
>>>
>>> -- 
>>> Best regards,
>>> Vladimir
>>>
>>>
> 
> 

-- 
—js

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

[Fam Zheng]

On Thu, 06/02 18:49, John Snow wrote:
> 
> 
> On 06/02/2016 07:43 AM, Vladimir Sementsov-Ogievskiy wrote:
> > Hi, what are the plans?
> > 
> 
> I'm not sure. Fam, part of this series was merged, wasn't it?
> 
> Do you have outstanding work that you'd like me to take over and push
> through for you?

I will rebase patches 6 - 15, address comments from Max on this revision and
send v5 soon. You are very welcome to take over from there! Thanks a lot!

Fam

> 
> --js
> 
> > On 26.05.2016 03:47, Fam Zheng wrote:
> >> On Wed, 05/25 17:45, Vladimir Sementsov-Ogievskiy wrote:
> >>> Hi!
> >>>
> >>> Are you going to update the series in the near future?
> >> Yes, probably in a couple days.
> >>
> >> Fam
> >>
> >>> On 08.03.2016 07:44, Fam Zheng wrote:
> >>>> v4: Rebase.
> >>>>       Add rev-by from John in patches 1-5, 7, 8.
> >>>>       Remove BdrvDirtyBitmap typedef from dirty-bitmap.h in patch 4.
> >>>> [Max]
> >>>>       Add assertion on bm->meta in patch 9. [John]
> >>>>
> >>>> Two major features are added to block dirty bitmap (and underlying
> >>>> HBitmap) in
> >>>> this series: meta bitmap and serialization, together with all other
> >>>> supportive
> >>>> patches.
> >>>>
> >>>> Both operations are common in dirty bitmap migration and
> >>>> persistence: they need
> >>>> to find whether and which part of the dirty bitmap in question has
> >>>> changed with
> >>>> meta dirty bitmap, and they need to write it to the target with
> >>>> serialization.
> >>>>
> >>>>
> >>>> Fam Zheng (13):
> >>>>     backup: Use Bitmap to replace "s->bitmap"
> >>>>     block: Include hbitmap.h in block.h
> >>>>     typedefs: Add BdrvDirtyBitmap
> >>>>     block: Move block dirty bitmap code to separate files
> >>>>     block: Remove unused typedef of BlockDriverDirtyHandler
> >>>>     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.c                      | 360 -----------------------------
> >>>>    block/Makefile.objs          |   2 +-
> >>>>    block/backup.c               |  25 +-
> >>>>    block/dirty-bitmap.c         | 535
> >>>> +++++++++++++++++++++++++++++++++++++++++++
> >>>>    block/mirror.c               |  15 +-
> >>>>    include/block/block.h        |  40 +---
> >>>>    include/block/dirty-bitmap.h |  75 ++++++
> >>>>    include/qemu/hbitmap.h       |  96 ++++++++
> >>>>    include/qemu/typedefs.h      |   2 +
> >>>>    tests/test-hbitmap.c         | 255 +++++++++++++++++++++
> >>>>    util/hbitmap.c               | 203 ++++++++++++++--
> >>>>    11 files changed, 1177 insertions(+), 431 deletions(-)
> >>>>    create mode 100644 block/dirty-bitmap.c
> >>>>    create mode 100644 include/block/dirty-bitmap.h
> >>>>
> >>>
> >>> -- 
> >>> Best regards,
> >>> Vladimir
> >>>
> >>>
> > 
> > 
> 
> -- 
> —js

Re: [Qemu-devel] [PATCH v4 08/15] tests: Add test code for meta bitmap

[Fam Zheng]

On Fri, 03/11 15:58, Max Reitz wrote:
> > +    /* 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);
> 
> Well, but if you'd do an hbitmap_set(data->hb, start, count + 1), then
> it would update meta, right?

Yes.

> 
> I forgot to mention in my reply to patch 7 that the check whether
> anything in the range passed to hbitmap_set() has been changed in order
> to determine whether all of that range should be set in the meta bitmap
> seemed a bit excessive. I don't think this will hurt anyone, but still.

It is. It has been on my list to optimize the unnecessary meta update away but
I haven't done that yet.

Fam

> 
> (So this is not a NACK, just a question.)
> 
> Max
> 

Re: [Qemu-devel] [PATCH v4 09/15] block: Support meta dirty bitmap

[Fam Zheng]

On Fri, 03/11 16:17, Max Reitz wrote:
> On 08.03.2016 05:45, 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(+)
> 
> Should we truncate the meta bitmaps in bdrv_dirty_bitmap_truncate()?
> 

Yes, adding that. Thanks!

Fam