* [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence
@ 2015-12-07 5:59 Fam Zheng
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes Fam Zheng
` (4 more replies)
0 siblings, 5 replies; 18+ messages in thread
From: Fam Zheng @ 2015-12-07 5:59 UTC (permalink / raw)
To: qemu-devel
Cc: Kevin Wolf, Vladimir Sementsov-Ogievskiy, qemu-block,
Stefan Hajnoczi, pbonzini, jsnow
Vladimir,
This is what I propose to implement meta bitmap. It's implemented in the
HBitmap level to be more efficient, and the interface slightly varies too.
I'd like to use these operations to make dirty bitmap persistence more
efficient too: unchanged dirty bits don't need to be flushed to disk. So I'm
posting this as a separate series for a common base for both sides.
Posting as RFC as 2.6 dev phase is just starting, we can still tweak the
interface and/or implementation to fit the need.
Fam Zheng (3):
HBitmap: Introduce "meta" bitmap to track bit changes
tests: Add test code for meta bitmap
block: Support meta dirty bitmap
block.c | 46 ++++++++++++++++++++++++++++++-
block/mirror.c | 3 +-
blockdev.c | 3 +-
include/block/block.h | 11 ++++++++
include/qemu/hbitmap.h | 7 +++++
migration/block.c | 2 +-
tests/test-hbitmap.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++
util/hbitmap.c | 22 +++++++++++++++
8 files changed, 164 insertions(+), 4 deletions(-)
--
2.4.3
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2015-12-07 5:59 [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Fam Zheng
@ 2015-12-07 5:59 ` Fam Zheng
2015-12-07 13:32 ` Vladimir Sementsov-Ogievskiy
2015-12-30 10:53 ` Vladimir Sementsov-Ogievskiy
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 2/3] tests: Add test code for meta bitmap Fam Zheng
` (3 subsequent siblings)
4 siblings, 2 replies; 18+ messages in thread
From: Fam Zheng @ 2015-12-07 5:59 UTC (permalink / raw)
To: qemu-devel
Cc: Kevin Wolf, Vladimir Sementsov-Ogievskiy, qemu-block,
Stefan Hajnoczi, pbonzini, jsnow
The meta bitmap will have the same size and granularity as the tracked
bitmap, and upon each bit toggle, the corresponding bit in the meta
bitmap, at an identical position, will be set.
Signed-off-by: Fam Zheng <famz@redhat.com>
---
include/qemu/hbitmap.h | 7 +++++++
util/hbitmap.c | 22 ++++++++++++++++++++++
2 files changed, 29 insertions(+)
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index bb94a00..09a6b06 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -181,6 +181,13 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
*/
unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
+/* hbitmap_create_meta
+ * @hb: The HBitmap to operate on.
+ *
+ * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
+ */
+HBitmap *hbitmap_create_meta(HBitmap *hb);
+
/**
* hbitmap_iter_next:
* @hbi: HBitmapIter to operate on.
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 50b888f..3ad406e 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -81,6 +81,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
@@ -232,6 +235,7 @@ static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t las
/* 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)
{
+ uint64_t save_start = start;
size_t pos = start >> BITS_PER_LEVEL;
size_t lastpos = last >> BITS_PER_LEVEL;
bool changed = false;
@@ -252,6 +256,9 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
}
}
changed |= hb_set_elem(&hb->levels[level][i], start, last);
+ if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
+ hbitmap_set(hb->meta, save_start, last - save_start + 1);
+ }
/* If there was any change in this layer, we may have to update
* the one above.
@@ -298,6 +305,7 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
/* 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)
{
+ uint64_t save_start = start;
size_t pos = start >> BITS_PER_LEVEL;
size_t lastpos = last >> BITS_PER_LEVEL;
bool changed = false;
@@ -336,6 +344,10 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
lastpos--;
}
+ if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
+ hbitmap_set(hb->meta, save_start, last - save_start + 1);
+ }
+
if (level > 0 && changed) {
hb_reset_between(hb, level - 1, pos, lastpos);
}
@@ -384,6 +396,9 @@ void hbitmap_free(HBitmap *hb)
for (i = HBITMAP_LEVELS; i-- > 0; ) {
g_free(hb->levels[i]);
}
+ if (hb->meta) {
+ hbitmap_free(hb->meta);
+ }
g_free(hb);
}
@@ -493,3 +508,10 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
return true;
}
+
+HBitmap *hbitmap_create_meta(HBitmap *hb)
+{
+ assert(!hb->meta);
+ hb->meta = hbitmap_alloc(hb->size, hb->granularity);
+ return hb->meta;
+}
--
2.4.3
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [Qemu-devel] [PATCH RFC for-2.6 2/3] tests: Add test code for meta bitmap
2015-12-07 5:59 [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Fam Zheng
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes Fam Zheng
@ 2015-12-07 5:59 ` Fam Zheng
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 3/3] block: Support meta dirty bitmap Fam Zheng
` (2 subsequent siblings)
4 siblings, 0 replies; 18+ messages in thread
From: Fam Zheng @ 2015-12-07 5:59 UTC (permalink / raw)
To: qemu-devel
Cc: Kevin Wolf, Vladimir Sementsov-Ogievskiy, qemu-block,
Stefan Hajnoczi, pbonzini, jsnow
Signed-off-by: Fam Zheng <famz@redhat.com>
---
tests/test-hbitmap.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 74 insertions(+)
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index abcea0c..6ab9101 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -23,6 +23,7 @@
typedef struct TestHBitmapData {
HBitmap *hb;
+ HBitmap *meta;
unsigned long *bits;
size_t size;
size_t old_size;
@@ -94,6 +95,13 @@ static void hbitmap_test_init(TestHBitmapData *data,
}
}
+static void hbitmap_test_init_meta(TestHBitmapData *data,
+ uint64_t size, int granularity)
+{
+ hbitmap_test_init(data, size, granularity);
+ data->meta = hbitmap_create_meta(data->hb);
+}
+
static inline size_t hbitmap_test_array_size(size_t bits)
{
size_t n = (bits + BITS_PER_LONG - 1) / BITS_PER_LONG;
@@ -637,6 +645,69 @@ 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)
+{
+ 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, start, 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, start, count);
+}
+
+/**
+ * Create an HBitmap and test set/unset.
+ */
+static void test_hbitmap_meta_basic(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);
+ for (i = 0; i < ARRAY_SIZE(offsets); i++) {
+ hbitmap_test_meta(data, offsets[i], 1);
+ hbitmap_test_meta(data, offsets[i], L1);
+ hbitmap_test_meta(data, offsets[i], L2);
+ }
+}
+
+static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused)
+{
+ hbitmap_test_init_meta(data, 0, 0);
+
+ hbitmap_check_meta(data, 0, 0);
+}
+
static void hbitmap_test_add(const char *testpath,
void (*test_func)(TestHBitmapData *data, const void *user_data))
{
@@ -686,6 +757,9 @@ 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/basic", test_hbitmap_meta_basic);
+ hbitmap_test_add("/hbitmap/meta/zero", test_hbitmap_meta_zero);
g_test_run();
return 0;
--
2.4.3
^ permalink raw reply related [flat|nested] 18+ messages in thread
* [Qemu-devel] [PATCH RFC for-2.6 3/3] block: Support meta dirty bitmap
2015-12-07 5:59 [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Fam Zheng
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes Fam Zheng
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 2/3] tests: Add test code for meta bitmap Fam Zheng
@ 2015-12-07 5:59 ` Fam Zheng
2015-12-07 14:19 ` [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Vladimir Sementsov-Ogievskiy
2015-12-07 23:47 ` John Snow
4 siblings, 0 replies; 18+ messages in thread
From: Fam Zheng @ 2015-12-07 5:59 UTC (permalink / raw)
To: qemu-devel
Cc: Kevin Wolf, Vladimir Sementsov-Ogievskiy, qemu-block,
Stefan Hajnoczi, pbonzini, jsnow
The added group of operations enables tracking of the changed bits in
the dirty bitmap.
Signed-off-by: Fam Zheng <famz@redhat.com>
---
block.c | 46 +++++++++++++++++++++++++++++++++++++++++++++-
block/mirror.c | 3 ++-
blockdev.c | 3 ++-
include/block/block.h | 11 +++++++++++
migration/block.c | 2 +-
5 files changed, 61 insertions(+), 4 deletions(-)
diff --git a/block.c b/block.c
index 3a7324b..a9beb04 100644
--- a/block.c
+++ b/block.c
@@ -64,6 +64,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) */
@@ -3153,6 +3154,7 @@ void bdrv_dirty_bitmap_make_anon(BdrvDirtyBitmap *bitmap)
BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
uint32_t granularity,
const char *name,
+ bool create_meta,
Error **errp)
{
int64_t bitmap_size;
@@ -3178,10 +3180,52 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
bitmap->size = bitmap_size;
bitmap->name = g_strdup(name);
bitmap->disabled = false;
+ if (create_meta) {
+ bitmap->meta = hbitmap_create_meta(bitmap->bitmap);
+ }
QLIST_INSERT_HEAD(&bs->dirty_bitmaps, bitmap, list);
return bitmap;
}
+void bdrv_create_meta_dirty_bitmap(BlockDriverState *bs,
+ BdrvDirtyBitmap *bitmap)
+{
+ assert(!bitmap->meta);
+ bitmap->meta = hbitmap_create_meta(bitmap->bitmap);
+}
+
+void bdrv_release_meta_dirty_bitmap(BlockDriverState *bs,
+ BdrvDirtyBitmap *bitmap)
+{
+ assert(bitmap->meta);
+ hbitmap_free(bitmap->meta);
+ 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 < 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;
@@ -3222,7 +3266,7 @@ int bdrv_dirty_bitmap_create_successor(BlockDriverState *bs,
/* Create an anonymous successor */
granularity = bdrv_dirty_bitmap_granularity(bitmap);
- child = bdrv_create_dirty_bitmap(bs, granularity, NULL, errp);
+ child = bdrv_create_dirty_bitmap(bs, granularity, NULL, false, errp);
if (!child) {
return -1;
}
diff --git a/block/mirror.c b/block/mirror.c
index 0e8f556..e381b9d 100644
--- a/block/mirror.c
+++ b/block/mirror.c
@@ -743,7 +743,8 @@ static void mirror_start_job(BlockDriverState *bs, BlockDriverState *target,
s->buf_size = ROUND_UP(buf_size, granularity);
s->unmap = unmap;
- s->dirty_bitmap = bdrv_create_dirty_bitmap(bs, granularity, NULL, errp);
+ s->dirty_bitmap = bdrv_create_dirty_bitmap(bs, granularity, NULL, false,
+ errp);
if (!s->dirty_bitmap) {
g_free(s->replaces);
block_job_unref(&s->common);
diff --git a/blockdev.c b/blockdev.c
index 313841b..2507d96 100644
--- a/blockdev.c
+++ b/blockdev.c
@@ -2671,7 +2671,8 @@ void qmp_block_dirty_bitmap_add(const char *node, const char *name,
granularity = bdrv_get_default_bitmap_granularity(bs);
}
- bdrv_create_dirty_bitmap(bs, granularity, name, errp);
+ bdrv_create_dirty_bitmap(bs, granularity, name, false,
+ errp);
out:
aio_context_release(aio_context);
diff --git a/include/block/block.h b/include/block/block.h
index 3477328..e749461 100644
--- a/include/block/block.h
+++ b/include/block/block.h
@@ -475,7 +475,12 @@ typedef struct BdrvDirtyBitmap BdrvDirtyBitmap;
BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
uint32_t granularity,
const char *name,
+ bool create_meta,
Error **errp);
+void bdrv_create_meta_dirty_bitmap(BlockDriverState *bs,
+ BdrvDirtyBitmap *bitmap);
+void bdrv_release_meta_dirty_bitmap(BlockDriverState *bs,
+ BdrvDirtyBitmap *bitmap);
int bdrv_dirty_bitmap_create_successor(BlockDriverState *bs,
BdrvDirtyBitmap *bitmap,
Error **errp);
@@ -504,6 +509,12 @@ 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);
+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);
int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
void bdrv_enable_copy_on_read(BlockDriverState *bs);
diff --git a/migration/block.c b/migration/block.c
index 656f38f..43b64a5 100644
--- a/migration/block.c
+++ b/migration/block.c
@@ -322,7 +322,7 @@ static int set_dirty_tracking(void)
QSIMPLEQ_FOREACH(bmds, &block_mig_state.bmds_list, entry) {
bmds->dirty_bitmap = bdrv_create_dirty_bitmap(bmds->bs, BLOCK_SIZE,
- NULL, NULL);
+ NULL, false, NULL);
if (!bmds->dirty_bitmap) {
ret = -errno;
goto fail;
--
2.4.3
^ permalink raw reply related [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes Fam Zheng
@ 2015-12-07 13:32 ` Vladimir Sementsov-Ogievskiy
2015-12-08 1:31 ` Fam Zheng
2015-12-30 10:53 ` Vladimir Sementsov-Ogievskiy
1 sibling, 1 reply; 18+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2015-12-07 13:32 UTC (permalink / raw)
To: Fam Zheng, qemu-devel
Cc: Kevin Wolf, pbonzini, jsnow, qemu-block, Stefan Hajnoczi
On 07.12.2015 08:59, Fam Zheng wrote:
> The meta bitmap will have the same size and granularity as the tracked
> bitmap, and upon each bit toggle, the corresponding bit in the meta
> bitmap, at an identical position, will be set.
No, meta bitmap should not have same granularity. If we have 16tb
storage, then 16kb granulated bitmap will occupy more then 128 mb. And
additional meta bitmap of the same size and granularity is redundant
128+ mb of RAM, when actually we need meta bitmap for blocks for example
of 1mb and it should occupy about 128 bits.
>
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
> include/qemu/hbitmap.h | 7 +++++++
> util/hbitmap.c | 22 ++++++++++++++++++++++
> 2 files changed, 29 insertions(+)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index bb94a00..09a6b06 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -181,6 +181,13 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
> */
> unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>
> +/* hbitmap_create_meta
> + * @hb: The HBitmap to operate on.
> + *
> + * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
> + */
> +HBitmap *hbitmap_create_meta(HBitmap *hb);
> +
> /**
> * hbitmap_iter_next:
> * @hbi: HBitmapIter to operate on.
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 50b888f..3ad406e 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -81,6 +81,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
> @@ -232,6 +235,7 @@ static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t las
> /* 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)
> {
> + uint64_t save_start = start;
> size_t pos = start >> BITS_PER_LEVEL;
> size_t lastpos = last >> BITS_PER_LEVEL;
> bool changed = false;
> @@ -252,6 +256,9 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
> }
> }
> changed |= hb_set_elem(&hb->levels[level][i], start, last);
> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
> + }
>
> /* If there was any change in this layer, we may have to update
> * the one above.
> @@ -298,6 +305,7 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
> /* 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)
> {
> + uint64_t save_start = start;
> size_t pos = start >> BITS_PER_LEVEL;
> size_t lastpos = last >> BITS_PER_LEVEL;
> bool changed = false;
> @@ -336,6 +344,10 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
> lastpos--;
> }
>
> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
> + }
> +
> if (level > 0 && changed) {
> hb_reset_between(hb, level - 1, pos, lastpos);
> }
> @@ -384,6 +396,9 @@ void hbitmap_free(HBitmap *hb)
> for (i = HBITMAP_LEVELS; i-- > 0; ) {
> g_free(hb->levels[i]);
> }
> + if (hb->meta) {
> + hbitmap_free(hb->meta);
> + }
> g_free(hb);
> }
>
> @@ -493,3 +508,10 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
>
> return true;
> }
> +
> +HBitmap *hbitmap_create_meta(HBitmap *hb)
> +{
> + assert(!hb->meta);
> + hb->meta = hbitmap_alloc(hb->size, hb->granularity);
> + return hb->meta;
> +}
--
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence
2015-12-07 5:59 [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Fam Zheng
` (2 preceding siblings ...)
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 3/3] block: Support meta dirty bitmap Fam Zheng
@ 2015-12-07 14:19 ` Vladimir Sementsov-Ogievskiy
2015-12-08 1:42 ` Fam Zheng
2015-12-07 23:47 ` John Snow
4 siblings, 1 reply; 18+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2015-12-07 14:19 UTC (permalink / raw)
To: Fam Zheng, qemu-devel
Cc: Kevin Wolf, pbonzini, jsnow, qemu-block, Stefan Hajnoczi
On 07.12.2015 08:59, Fam Zheng wrote:
> Vladimir,
>
> This is what I propose to implement meta bitmap. It's implemented in the
> HBitmap level to be more efficient, and the interface slightly varies too.
What is the benefit?
Hbitmap usage:
1) BdrvDirtyBitmap - need meta
2) BackupBlockJob - doesn't need meta
3) BlockDirtyBitmapState - doesn't need meta
4) now I'm working on series for parallels format and I use HBitmap to
mark allocated/free clusters.. - doesn't need meta
5) your meta hbitmap =) - doesn't need meta..
So, what is the benefit of moving this functionality to parent class?
(Which is complicated without it)..
However, I'm not really against, except my comment to the first patch.
PS:
Actually I don't like HBitmap - BdrvDirtyBitmap..
- No implementation without granularity
I need HBitmap without granularity for my needs and have to use
granularity=0. If there was HBitmap without granularity some operations
can be faster - for example, finding next/previous/last zeros, jumping
by words not by bits..
- It is not sparse. Empty bitmap occupies lots of ram.
- different granularity units for HBitmap and BdrvDirtyBitmap
- different layers with/without granularity in hbitmap.c
- HBitmap with non-zero granularity doesn't know its size (only rounded
up to granularity)
- necessity of writing wrappers like
bdrv_dirty_bitmap_do_something(...)
{
hbitmap_do_something(...)
}
-- Yes, I understand that this is inevitably, but I just don't like it..
- BdrvDirtyBitmap is defined in block.c.. I think, it should have its
own .c file.
>
> I'd like to use these operations to make dirty bitmap persistence more
> efficient too: unchanged dirty bits don't need to be flushed to disk. So I'm
> posting this as a separate series for a common base for both sides.
>
> Posting as RFC as 2.6 dev phase is just starting, we can still tweak the
> interface and/or implementation to fit the need.
>
> Fam Zheng (3):
> HBitmap: Introduce "meta" bitmap to track bit changes
> tests: Add test code for meta bitmap
> block: Support meta dirty bitmap
>
> block.c | 46 ++++++++++++++++++++++++++++++-
> block/mirror.c | 3 +-
> blockdev.c | 3 +-
> include/block/block.h | 11 ++++++++
> include/qemu/hbitmap.h | 7 +++++
> migration/block.c | 2 +-
> tests/test-hbitmap.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++
> util/hbitmap.c | 22 +++++++++++++++
> 8 files changed, 164 insertions(+), 4 deletions(-)
>
--
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence
2015-12-07 5:59 [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Fam Zheng
` (3 preceding siblings ...)
2015-12-07 14:19 ` [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Vladimir Sementsov-Ogievskiy
@ 2015-12-07 23:47 ` John Snow
2015-12-08 1:36 ` Fam Zheng
4 siblings, 1 reply; 18+ messages in thread
From: John Snow @ 2015-12-07 23:47 UTC (permalink / raw)
To: Fam Zheng, qemu-devel
Cc: Kevin Wolf, pbonzini, Vladimir Sementsov-Ogievskiy,
Stefan Hajnoczi, qemu-block
On 12/07/2015 12:59 AM, Fam Zheng wrote:
> Vladimir,
>
> This is what I propose to implement meta bitmap. It's implemented in the
> HBitmap level to be more efficient, and the interface slightly varies too.
>
I missed it: What was wrong with Vladimir's approach / what are the
benefits of this approach?
> I'd like to use these operations to make dirty bitmap persistence more
> efficient too: unchanged dirty bits don't need to be flushed to disk. So I'm
> posting this as a separate series for a common base for both sides.
>
This is a reasonable use of the meta-bitmap strategy in general.
Keep in mind Vladimir's approach to Meta bitmaps used a different
granularity such that 1 physical bit implied 1 sector needed to be
re-transmitted.
A meta-bitmap that keeps track of disk flushes may require a different
granularity than one used for migration.
> Posting as RFC as 2.6 dev phase is just starting, we can still tweak the
> interface and/or implementation to fit the need.
>
> Fam Zheng (3):
> HBitmap: Introduce "meta" bitmap to track bit changes
> tests: Add test code for meta bitmap
> block: Support meta dirty bitmap
>
> block.c | 46 ++++++++++++++++++++++++++++++-
> block/mirror.c | 3 +-
> blockdev.c | 3 +-
> include/block/block.h | 11 ++++++++
> include/qemu/hbitmap.h | 7 +++++
> migration/block.c | 2 +-
> tests/test-hbitmap.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++
> util/hbitmap.c | 22 +++++++++++++++
> 8 files changed, 164 insertions(+), 4 deletions(-)
>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2015-12-07 13:32 ` Vladimir Sementsov-Ogievskiy
@ 2015-12-08 1:31 ` Fam Zheng
2015-12-09 11:51 ` Vladimir Sementsov-Ogievskiy
0 siblings, 1 reply; 18+ messages in thread
From: Fam Zheng @ 2015-12-08 1:31 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy
Cc: Kevin Wolf, qemu-block, qemu-devel, Stefan Hajnoczi, pbonzini, jsnow
On Mon, 12/07 16:32, Vladimir Sementsov-Ogievskiy wrote:
> On 07.12.2015 08:59, Fam Zheng wrote:
> >The meta bitmap will have the same size and granularity as the tracked
> >bitmap, and upon each bit toggle, the corresponding bit in the meta
> >bitmap, at an identical position, will be set.
>
> No, meta bitmap should not have same granularity. If we have 16tb
> storage, then 16kb granulated bitmap will occupy more then 128 mb.
> And additional meta bitmap of the same size and granularity is
> redundant 128+ mb of RAM, when actually we need meta bitmap for
> blocks for example of 1mb and it should occupy about 128 bits.
Makes sense, do you prefer a parameterized granularity, or a fixed scaling like
one bit for 1 word?
Fam
>
>
> >
> >Signed-off-by: Fam Zheng <famz@redhat.com>
> >---
> > include/qemu/hbitmap.h | 7 +++++++
> > util/hbitmap.c | 22 ++++++++++++++++++++++
> > 2 files changed, 29 insertions(+)
> >
> >diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> >index bb94a00..09a6b06 100644
> >--- a/include/qemu/hbitmap.h
> >+++ b/include/qemu/hbitmap.h
> >@@ -181,6 +181,13 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
> > */
> > unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
> >+/* hbitmap_create_meta
> >+ * @hb: The HBitmap to operate on.
> >+ *
> >+ * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
> >+ */
> >+HBitmap *hbitmap_create_meta(HBitmap *hb);
> >+
> > /**
> > * hbitmap_iter_next:
> > * @hbi: HBitmapIter to operate on.
> >diff --git a/util/hbitmap.c b/util/hbitmap.c
> >index 50b888f..3ad406e 100644
> >--- a/util/hbitmap.c
> >+++ b/util/hbitmap.c
> >@@ -81,6 +81,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
> >@@ -232,6 +235,7 @@ static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t las
> > /* 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)
> > {
> >+ uint64_t save_start = start;
> > size_t pos = start >> BITS_PER_LEVEL;
> > size_t lastpos = last >> BITS_PER_LEVEL;
> > bool changed = false;
> >@@ -252,6 +256,9 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
> > }
> > }
> > changed |= hb_set_elem(&hb->levels[level][i], start, last);
> >+ if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
> >+ hbitmap_set(hb->meta, save_start, last - save_start + 1);
> >+ }
> > /* If there was any change in this layer, we may have to update
> > * the one above.
> >@@ -298,6 +305,7 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
> > /* 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)
> > {
> >+ uint64_t save_start = start;
> > size_t pos = start >> BITS_PER_LEVEL;
> > size_t lastpos = last >> BITS_PER_LEVEL;
> > bool changed = false;
> >@@ -336,6 +344,10 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
> > lastpos--;
> > }
> >+ if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
> >+ hbitmap_set(hb->meta, save_start, last - save_start + 1);
> >+ }
> >+
> > if (level > 0 && changed) {
> > hb_reset_between(hb, level - 1, pos, lastpos);
> > }
> >@@ -384,6 +396,9 @@ void hbitmap_free(HBitmap *hb)
> > for (i = HBITMAP_LEVELS; i-- > 0; ) {
> > g_free(hb->levels[i]);
> > }
> >+ if (hb->meta) {
> >+ hbitmap_free(hb->meta);
> >+ }
> > g_free(hb);
> > }
> >@@ -493,3 +508,10 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
> > return true;
> > }
> >+
> >+HBitmap *hbitmap_create_meta(HBitmap *hb)
> >+{
> >+ assert(!hb->meta);
> >+ hb->meta = hbitmap_alloc(hb->size, hb->granularity);
> >+ return hb->meta;
> >+}
>
>
> --
> Best regards,
> Vladimir
> * now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence
2015-12-07 23:47 ` John Snow
@ 2015-12-08 1:36 ` Fam Zheng
2015-12-09 11:57 ` Vladimir Sementsov-Ogievskiy
0 siblings, 1 reply; 18+ messages in thread
From: Fam Zheng @ 2015-12-08 1:36 UTC (permalink / raw)
To: John Snow
Cc: Kevin Wolf, Vladimir Sementsov-Ogievskiy, qemu-block, qemu-devel,
Stefan Hajnoczi, pbonzini
On Mon, 12/07 18:47, John Snow wrote:
>
>
> On 12/07/2015 12:59 AM, Fam Zheng wrote:
> > Vladimir,
> >
> > This is what I propose to implement meta bitmap. It's implemented in the
> > HBitmap level to be more efficient, and the interface slightly varies too.
> >
>
> I missed it: What was wrong with Vladimir's approach / what are the
> benefits of this approach?
The only real difference with this series is, only actual bit toggling will
mark meta dirty. Vladimir's approach was in BdrvDirtyBitmap level which can't
tell bit toggling from repetitive bit set/unset. This is from his patch:
@@ -3390,6 +3428,9 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
{
assert(bdrv_dirty_bitmap_enabled(bitmap));
hbitmap_set(bitmap->bitmap, cur_sector, nr_sectors);
+ if (bitmap->meta_bitmap) {
+ hbitmap_set(bitmap->meta_bitmap, cur_sector, nr_sectors);
+ }
}
void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
@@ -3397,6 +3438,9 @@ void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
{
assert(bdrv_dirty_bitmap_enabled(bitmap));
hbitmap_reset(bitmap->bitmap, cur_sector, nr_sectors);
+ if (bitmap->meta_bitmap) {
+ hbitmap_set(bitmap->meta_bitmap, cur_sector, nr_sectors);
+ }
}
void bdrv_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap)
>
> > I'd like to use these operations to make dirty bitmap persistence more
> > efficient too: unchanged dirty bits don't need to be flushed to disk. So I'm
> > posting this as a separate series for a common base for both sides.
> >
>
> This is a reasonable use of the meta-bitmap strategy in general.
>
> Keep in mind Vladimir's approach to Meta bitmaps used a different
> granularity such that 1 physical bit implied 1 sector needed to be
> re-transmitted.
Yes, I can fix the meta bitmap granularity.
>
> A meta-bitmap that keeps track of disk flushes may require a different
> granularity than one used for migration.
>
> > Posting as RFC as 2.6 dev phase is just starting, we can still tweak the
> > interface and/or implementation to fit the need.
> >
> > Fam Zheng (3):
> > HBitmap: Introduce "meta" bitmap to track bit changes
> > tests: Add test code for meta bitmap
> > block: Support meta dirty bitmap
> >
> > block.c | 46 ++++++++++++++++++++++++++++++-
> > block/mirror.c | 3 +-
> > blockdev.c | 3 +-
> > include/block/block.h | 11 ++++++++
> > include/qemu/hbitmap.h | 7 +++++
> > migration/block.c | 2 +-
> > tests/test-hbitmap.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++
> > util/hbitmap.c | 22 +++++++++++++++
> > 8 files changed, 164 insertions(+), 4 deletions(-)
> >
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence
2015-12-07 14:19 ` [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Vladimir Sementsov-Ogievskiy
@ 2015-12-08 1:42 ` Fam Zheng
2015-12-09 11:46 ` Vladimir Sementsov-Ogievskiy
0 siblings, 1 reply; 18+ messages in thread
From: Fam Zheng @ 2015-12-08 1:42 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy
Cc: Kevin Wolf, qemu-block, qemu-devel, Stefan Hajnoczi, pbonzini, jsnow
On Mon, 12/07 17:19, Vladimir Sementsov-Ogievskiy wrote:
> On 07.12.2015 08:59, Fam Zheng wrote:
> >Vladimir,
> >
> >This is what I propose to implement meta bitmap. It's implemented in the
> >HBitmap level to be more efficient, and the interface slightly varies too.
>
> What is the benefit?
>
> Hbitmap usage:
>
> 1) BdrvDirtyBitmap - need meta
> 2) BackupBlockJob - doesn't need meta
> 3) BlockDirtyBitmapState - doesn't need meta
> 4) now I'm working on series for parallels format and I use HBitmap
> to mark allocated/free clusters.. - doesn't need meta
> 5) your meta hbitmap =) - doesn't need meta..
6) persistence dirty bitmap. - need meta
>
> So, what is the benefit of moving this functionality to parent
> class? (Which is complicated without it)..
See my reply to John's comment on the cover letter. This is more efficient than
doing it in BdrvDirtyBitmap.
>
> However, I'm not really against, except my comment to the first patch.
>
> PS:
> Actually I don't like HBitmap - BdrvDirtyBitmap..
> - No implementation without granularity
> I need HBitmap without granularity for my needs and have to
> use granularity=0. If there was HBitmap without granularity some
> operations can be faster - for example, finding next/previous/last
> zeros, jumping by words not by bits..
> - It is not sparse. Empty bitmap occupies lots of ram.
> - different granularity units for HBitmap and BdrvDirtyBitmap
> - different layers with/without granularity in hbitmap.c
> - HBitmap with non-zero granularity doesn't know its size (only
> rounded up to granularity)
> - necessity of writing wrappers like
> bdrv_dirty_bitmap_do_something(...)
> {
> hbitmap_do_something(...)
> }
> -- Yes, I understand that this is inevitably, but I just don't like it..
> - BdrvDirtyBitmap is defined in block.c.. I think, it should have
> its own .c file.
Yes, I agree we should cut it out during 2.6, with a separate header.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence
2015-12-08 1:42 ` Fam Zheng
@ 2015-12-09 11:46 ` Vladimir Sementsov-Ogievskiy
0 siblings, 0 replies; 18+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2015-12-09 11:46 UTC (permalink / raw)
To: Fam Zheng
Cc: Kevin Wolf, qemu-block, qemu-devel, Stefan Hajnoczi, pbonzini, jsnow
On 08.12.2015 04:42, Fam Zheng wrote:
> On Mon, 12/07 17:19, Vladimir Sementsov-Ogievskiy wrote:
>> On 07.12.2015 08:59, Fam Zheng wrote:
>>> Vladimir,
>>>
>>> This is what I propose to implement meta bitmap. It's implemented in the
>>> HBitmap level to be more efficient, and the interface slightly varies too.
>> What is the benefit?
>>
>> Hbitmap usage:
>>
>> 1) BdrvDirtyBitmap - need meta
>> 2) BackupBlockJob - doesn't need meta
>> 3) BlockDirtyBitmapState - doesn't need meta
>> 4) now I'm working on series for parallels format and I use HBitmap
>> to mark allocated/free clusters.. - doesn't need meta
>> 5) your meta hbitmap =) - doesn't need meta..
> 6) persistence dirty bitmap. - need meta
Your (6) is my (1)
>
>> So, what is the benefit of moving this functionality to parent
>> class? (Which is complicated without it)..
> See my reply to John's comment on the cover letter. This is more efficient than
> doing it in BdrvDirtyBitmap.
>
>> However, I'm not really against, except my comment to the first patch.
>>
>> PS:
>> Actually I don't like HBitmap - BdrvDirtyBitmap..
>> - No implementation without granularity
>> I need HBitmap without granularity for my needs and have to
>> use granularity=0. If there was HBitmap without granularity some
>> operations can be faster - for example, finding next/previous/last
>> zeros, jumping by words not by bits..
>> - It is not sparse. Empty bitmap occupies lots of ram.
>> - different granularity units for HBitmap and BdrvDirtyBitmap
>> - different layers with/without granularity in hbitmap.c
>> - HBitmap with non-zero granularity doesn't know its size (only
>> rounded up to granularity)
>> - necessity of writing wrappers like
>> bdrv_dirty_bitmap_do_something(...)
>> {
>> hbitmap_do_something(...)
>> }
>> -- Yes, I understand that this is inevitably, but I just don't like it..
>> - BdrvDirtyBitmap is defined in block.c.. I think, it should have
>> its own .c file.
> Yes, I agree we should cut it out during 2.6, with a separate header.
>
--
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2015-12-08 1:31 ` Fam Zheng
@ 2015-12-09 11:51 ` Vladimir Sementsov-Ogievskiy
0 siblings, 0 replies; 18+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2015-12-09 11:51 UTC (permalink / raw)
To: Fam Zheng
Cc: Kevin Wolf, qemu-block, qemu-devel, Stefan Hajnoczi, pbonzini, jsnow
On 08.12.2015 04:31, Fam Zheng wrote:
> On Mon, 12/07 16:32, Vladimir Sementsov-Ogievskiy wrote:
>> On 07.12.2015 08:59, Fam Zheng wrote:
>>> The meta bitmap will have the same size and granularity as the tracked
>>> bitmap, and upon each bit toggle, the corresponding bit in the meta
>>> bitmap, at an identical position, will be set.
>> No, meta bitmap should not have same granularity. If we have 16tb
>> storage, then 16kb granulated bitmap will occupy more then 128 mb.
>> And additional meta bitmap of the same size and granularity is
>> redundant 128+ mb of RAM, when actually we need meta bitmap for
>> blocks for example of 1mb and it should occupy about 128 bits.
> Makes sense, do you prefer a parameterized granularity, or a fixed scaling like
> one bit for 1 word?
Parametrized is better I thing. We will be able easily change it. Also
as John writes it may be that it should be different for
persistance/migration..
>
> Fam
>
>>
>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>> ---
>>> include/qemu/hbitmap.h | 7 +++++++
>>> util/hbitmap.c | 22 ++++++++++++++++++++++
>>> 2 files changed, 29 insertions(+)
>>>
>>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>>> index bb94a00..09a6b06 100644
>>> --- a/include/qemu/hbitmap.h
>>> +++ b/include/qemu/hbitmap.h
>>> @@ -181,6 +181,13 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
>>> */
>>> unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>>> +/* hbitmap_create_meta
>>> + * @hb: The HBitmap to operate on.
>>> + *
>>> + * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
>>> + */
>>> +HBitmap *hbitmap_create_meta(HBitmap *hb);
>>> +
>>> /**
>>> * hbitmap_iter_next:
>>> * @hbi: HBitmapIter to operate on.
>>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>>> index 50b888f..3ad406e 100644
>>> --- a/util/hbitmap.c
>>> +++ b/util/hbitmap.c
>>> @@ -81,6 +81,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
>>> @@ -232,6 +235,7 @@ static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t las
>>> /* 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)
>>> {
>>> + uint64_t save_start = start;
>>> size_t pos = start >> BITS_PER_LEVEL;
>>> size_t lastpos = last >> BITS_PER_LEVEL;
>>> bool changed = false;
>>> @@ -252,6 +256,9 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
>>> }
>>> }
>>> changed |= hb_set_elem(&hb->levels[level][i], start, last);
>>> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
>>> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
>>> + }
>>> /* If there was any change in this layer, we may have to update
>>> * the one above.
>>> @@ -298,6 +305,7 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
>>> /* 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)
>>> {
>>> + uint64_t save_start = start;
>>> size_t pos = start >> BITS_PER_LEVEL;
>>> size_t lastpos = last >> BITS_PER_LEVEL;
>>> bool changed = false;
>>> @@ -336,6 +344,10 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
>>> lastpos--;
>>> }
>>> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
>>> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
>>> + }
>>> +
>>> if (level > 0 && changed) {
>>> hb_reset_between(hb, level - 1, pos, lastpos);
>>> }
>>> @@ -384,6 +396,9 @@ void hbitmap_free(HBitmap *hb)
>>> for (i = HBITMAP_LEVELS; i-- > 0; ) {
>>> g_free(hb->levels[i]);
>>> }
>>> + if (hb->meta) {
>>> + hbitmap_free(hb->meta);
>>> + }
>>> g_free(hb);
>>> }
>>> @@ -493,3 +508,10 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
>>> return true;
>>> }
>>> +
>>> +HBitmap *hbitmap_create_meta(HBitmap *hb)
>>> +{
>>> + assert(!hb->meta);
>>> + hb->meta = hbitmap_alloc(hb->size, hb->granularity);
>>> + return hb->meta;
>>> +}
>>
>> --
>> Best regards,
>> Vladimir
>> * now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
>>
--
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence
2015-12-08 1:36 ` Fam Zheng
@ 2015-12-09 11:57 ` Vladimir Sementsov-Ogievskiy
0 siblings, 0 replies; 18+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2015-12-09 11:57 UTC (permalink / raw)
To: Fam Zheng, John Snow
Cc: Kevin Wolf, pbonzini, Stefan Hajnoczi, qemu-devel, qemu-block
On 08.12.2015 04:36, Fam Zheng wrote:
> On Mon, 12/07 18:47, John Snow wrote:
>>
>> On 12/07/2015 12:59 AM, Fam Zheng wrote:
>>> Vladimir,
>>>
>>> This is what I propose to implement meta bitmap. It's implemented in the
>>> HBitmap level to be more efficient, and the interface slightly varies too.
>>>
>> I missed it: What was wrong with Vladimir's approach / what are the
>> benefits of this approach?
> The only real difference with this series is, only actual bit toggling will
> mark meta dirty. Vladimir's approach was in BdrvDirtyBitmap level which can't
> tell bit toggling from repetitive bit set/unset. This is from his patch:
Ok, you are right. It's truth.
>
> @@ -3390,6 +3428,9 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> {
> assert(bdrv_dirty_bitmap_enabled(bitmap));
> hbitmap_set(bitmap->bitmap, cur_sector, nr_sectors);
> + if (bitmap->meta_bitmap) {
> + hbitmap_set(bitmap->meta_bitmap, cur_sector, nr_sectors);
> + }
> }
>
> void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> @@ -3397,6 +3438,9 @@ void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> {
> assert(bdrv_dirty_bitmap_enabled(bitmap));
> hbitmap_reset(bitmap->bitmap, cur_sector, nr_sectors);
> + if (bitmap->meta_bitmap) {
> + hbitmap_set(bitmap->meta_bitmap, cur_sector, nr_sectors);
> + }
> }
>
> void bdrv_clear_dirty_bitmap(BdrvDirtyBitmap *bitmap)
>
>>> I'd like to use these operations to make dirty bitmap persistence more
>>> efficient too: unchanged dirty bits don't need to be flushed to disk. So I'm
>>> posting this as a separate series for a common base for both sides.
>>>
>> This is a reasonable use of the meta-bitmap strategy in general.
>>
>> Keep in mind Vladimir's approach to Meta bitmaps used a different
>> granularity such that 1 physical bit implied 1 sector needed to be
>> re-transmitted.
> Yes, I can fix the meta bitmap granularity.
>
>> A meta-bitmap that keeps track of disk flushes may require a different
>> granularity than one used for migration.
>>
>>> Posting as RFC as 2.6 dev phase is just starting, we can still tweak the
>>> interface and/or implementation to fit the need.
>>>
>>> Fam Zheng (3):
>>> HBitmap: Introduce "meta" bitmap to track bit changes
>>> tests: Add test code for meta bitmap
>>> block: Support meta dirty bitmap
>>>
>>> block.c | 46 ++++++++++++++++++++++++++++++-
>>> block/mirror.c | 3 +-
>>> blockdev.c | 3 +-
>>> include/block/block.h | 11 ++++++++
>>> include/qemu/hbitmap.h | 7 +++++
>>> migration/block.c | 2 +-
>>> tests/test-hbitmap.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++
>>> util/hbitmap.c | 22 +++++++++++++++
>>> 8 files changed, 164 insertions(+), 4 deletions(-)
>>>
--
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes Fam Zheng
2015-12-07 13:32 ` Vladimir Sementsov-Ogievskiy
@ 2015-12-30 10:53 ` Vladimir Sementsov-Ogievskiy
2015-12-30 11:07 ` Fam Zheng
1 sibling, 1 reply; 18+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2015-12-30 10:53 UTC (permalink / raw)
To: Fam Zheng, qemu-devel
Cc: Kevin Wolf, pbonzini, jsnow, qemu-block, Stefan Hajnoczi
On 07.12.2015 08:59, Fam Zheng wrote:
> The meta bitmap will have the same size and granularity as the tracked
> bitmap, and upon each bit toggle, the corresponding bit in the meta
> bitmap, at an identical position, will be set.
>
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
> include/qemu/hbitmap.h | 7 +++++++
> util/hbitmap.c | 22 ++++++++++++++++++++++
> 2 files changed, 29 insertions(+)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index bb94a00..09a6b06 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -181,6 +181,13 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
> */
> unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>
> +/* hbitmap_create_meta
> + * @hb: The HBitmap to operate on.
> + *
> + * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
> + */
> +HBitmap *hbitmap_create_meta(HBitmap *hb);
> +
> /**
> * hbitmap_iter_next:
> * @hbi: HBitmapIter to operate on.
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 50b888f..3ad406e 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -81,6 +81,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
> @@ -232,6 +235,7 @@ static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t las
> /* 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)
> {
> + uint64_t save_start = start;
> size_t pos = start >> BITS_PER_LEVEL;
> size_t lastpos = last >> BITS_PER_LEVEL;
> bool changed = false;
> @@ -252,6 +256,9 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
> }
> }
> changed |= hb_set_elem(&hb->levels[level][i], start, last);
> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
> + }
I thing now, that the same may be accomplished for BdrvDirtyBitmap, all
we need is return "changed" status from hb_set_between and then from
hbitmap_set.
>
> /* If there was any change in this layer, we may have to update
> * the one above.
> @@ -298,6 +305,7 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
> /* 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)
> {
> + uint64_t save_start = start;
> size_t pos = start >> BITS_PER_LEVEL;
> size_t lastpos = last >> BITS_PER_LEVEL;
> bool changed = false;
> @@ -336,6 +344,10 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
> lastpos--;
> }
>
> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
> + }
> +
> if (level > 0 && changed) {
> hb_reset_between(hb, level - 1, pos, lastpos);
> }
> @@ -384,6 +396,9 @@ void hbitmap_free(HBitmap *hb)
> for (i = HBITMAP_LEVELS; i-- > 0; ) {
> g_free(hb->levels[i]);
> }
> + if (hb->meta) {
> + hbitmap_free(hb->meta);
> + }
> g_free(hb);
> }
>
> @@ -493,3 +508,10 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
>
> return true;
> }
> +
> +HBitmap *hbitmap_create_meta(HBitmap *hb)
> +{
> + assert(!hb->meta);
> + hb->meta = hbitmap_alloc(hb->size, hb->granularity);
> + return hb->meta;
> +}
--
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2015-12-30 10:53 ` Vladimir Sementsov-Ogievskiy
@ 2015-12-30 11:07 ` Fam Zheng
2015-12-30 11:26 ` Vladimir Sementsov-Ogievskiy
2016-01-21 10:58 ` Vladimir Sementsov-Ogievskiy
0 siblings, 2 replies; 18+ messages in thread
From: Fam Zheng @ 2015-12-30 11:07 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy
Cc: Kevin Wolf, qemu-block, qemu-devel, Stefan Hajnoczi, pbonzini, jsnow
On Wed, 12/30 13:53, Vladimir Sementsov-Ogievskiy wrote:
> On 07.12.2015 08:59, Fam Zheng wrote:
> >The meta bitmap will have the same size and granularity as the tracked
> >bitmap, and upon each bit toggle, the corresponding bit in the meta
> >bitmap, at an identical position, will be set.
> >
> >Signed-off-by: Fam Zheng <famz@redhat.com>
> >---
> > include/qemu/hbitmap.h | 7 +++++++
> > util/hbitmap.c | 22 ++++++++++++++++++++++
> > 2 files changed, 29 insertions(+)
> >
> >diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> >index bb94a00..09a6b06 100644
> >--- a/include/qemu/hbitmap.h
> >+++ b/include/qemu/hbitmap.h
> >@@ -181,6 +181,13 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
> > */
> > unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
> >+/* hbitmap_create_meta
> >+ * @hb: The HBitmap to operate on.
> >+ *
> >+ * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
> >+ */
> >+HBitmap *hbitmap_create_meta(HBitmap *hb);
> >+
> > /**
> > * hbitmap_iter_next:
> > * @hbi: HBitmapIter to operate on.
> >diff --git a/util/hbitmap.c b/util/hbitmap.c
> >index 50b888f..3ad406e 100644
> >--- a/util/hbitmap.c
> >+++ b/util/hbitmap.c
> >@@ -81,6 +81,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
> >@@ -232,6 +235,7 @@ static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t las
> > /* 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)
> > {
> >+ uint64_t save_start = start;
> > size_t pos = start >> BITS_PER_LEVEL;
> > size_t lastpos = last >> BITS_PER_LEVEL;
> > bool changed = false;
> >@@ -252,6 +256,9 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
> > }
> > }
> > changed |= hb_set_elem(&hb->levels[level][i], start, last);
> >+ if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
> >+ hbitmap_set(hb->meta, save_start, last - save_start + 1);
> >+ }
>
> I thing now, that the same may be accomplished for BdrvDirtyBitmap,
> all we need is return "changed" status from hb_set_between and then
> from hbitmap_set.
That is true, but it makes further optimizing to *really* only set the toggled
meta bits much more difficult (i.e. when only a few bits between start and last
are changed).
I haven't written any code for that optimization, but I did base my other
persistent dirty bitmap work on v2 of this series. It would be great if we can
harmonize on this, so we both have a common base of block dirty bitmap.
I can post v2 to the list very soon, if the idea is okay for you; or if you've
your preferred way, we can take a look together. What do you think?
Fam
>
> > /* If there was any change in this layer, we may have to update
> > * the one above.
> >@@ -298,6 +305,7 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
> > /* 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)
> > {
> >+ uint64_t save_start = start;
> > size_t pos = start >> BITS_PER_LEVEL;
> > size_t lastpos = last >> BITS_PER_LEVEL;
> > bool changed = false;
> >@@ -336,6 +344,10 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
> > lastpos--;
> > }
> >+ if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
> >+ hbitmap_set(hb->meta, save_start, last - save_start + 1);
> >+ }
> >+
> > if (level > 0 && changed) {
> > hb_reset_between(hb, level - 1, pos, lastpos);
> > }
> >@@ -384,6 +396,9 @@ void hbitmap_free(HBitmap *hb)
> > for (i = HBITMAP_LEVELS; i-- > 0; ) {
> > g_free(hb->levels[i]);
> > }
> >+ if (hb->meta) {
> >+ hbitmap_free(hb->meta);
> >+ }
> > g_free(hb);
> > }
> >@@ -493,3 +508,10 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
> > return true;
> > }
> >+
> >+HBitmap *hbitmap_create_meta(HBitmap *hb)
> >+{
> >+ assert(!hb->meta);
> >+ hb->meta = hbitmap_alloc(hb->size, hb->granularity);
> >+ return hb->meta;
> >+}
>
>
> --
> Best regards,
> Vladimir
> * now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
>
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2015-12-30 11:07 ` Fam Zheng
@ 2015-12-30 11:26 ` Vladimir Sementsov-Ogievskiy
2016-01-21 10:58 ` Vladimir Sementsov-Ogievskiy
1 sibling, 0 replies; 18+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2015-12-30 11:26 UTC (permalink / raw)
To: Fam Zheng
Cc: Kevin Wolf, qemu-block, qemu-devel, Stefan Hajnoczi, pbonzini, jsnow
On 30.12.2015 14:07, Fam Zheng wrote:
> On Wed, 12/30 13:53, Vladimir Sementsov-Ogievskiy wrote:
>> On 07.12.2015 08:59, Fam Zheng wrote:
>>> The meta bitmap will have the same size and granularity as the tracked
>>> bitmap, and upon each bit toggle, the corresponding bit in the meta
>>> bitmap, at an identical position, will be set.
>>>
>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>> ---
>>> include/qemu/hbitmap.h | 7 +++++++
>>> util/hbitmap.c | 22 ++++++++++++++++++++++
>>> 2 files changed, 29 insertions(+)
>>>
>>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>>> index bb94a00..09a6b06 100644
>>> --- a/include/qemu/hbitmap.h
>>> +++ b/include/qemu/hbitmap.h
>>> @@ -181,6 +181,13 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
>>> */
>>> unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>>> +/* hbitmap_create_meta
>>> + * @hb: The HBitmap to operate on.
>>> + *
>>> + * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
>>> + */
>>> +HBitmap *hbitmap_create_meta(HBitmap *hb);
>>> +
>>> /**
>>> * hbitmap_iter_next:
>>> * @hbi: HBitmapIter to operate on.
>>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>>> index 50b888f..3ad406e 100644
>>> --- a/util/hbitmap.c
>>> +++ b/util/hbitmap.c
>>> @@ -81,6 +81,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
>>> @@ -232,6 +235,7 @@ static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t las
>>> /* 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)
>>> {
>>> + uint64_t save_start = start;
>>> size_t pos = start >> BITS_PER_LEVEL;
>>> size_t lastpos = last >> BITS_PER_LEVEL;
>>> bool changed = false;
>>> @@ -252,6 +256,9 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
>>> }
>>> }
>>> changed |= hb_set_elem(&hb->levels[level][i], start, last);
>>> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
>>> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
>>> + }
>> I thing now, that the same may be accomplished for BdrvDirtyBitmap,
>> all we need is return "changed" status from hb_set_between and then
>> from hbitmap_set.
> That is true, but it makes further optimizing to *really* only set the toggled
> meta bits much more difficult (i.e. when only a few bits between start and last
> are changed).
>
> I haven't written any code for that optimization, but I did base my other
> persistent dirty bitmap work on v2 of this series. It would be great if we can
> harmonize on this, so we both have a common base of block dirty bitmap.
>
> I can post v2 to the list very soon, if the idea is okay for you; or if you've
> your preferred way, we can take a look together. What do you think?
Hmm, I see, optimization is possible.. Something like call hb_set_elem
for meta bitmap directly? Cool optimization may be done if meta bitmap
has the same granularity, but it is not the case.. Ok, I'll wait for
your v2.
>
> Fam
>
>>> /* If there was any change in this layer, we may have to update
>>> * the one above.
>>> @@ -298,6 +305,7 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
>>> /* 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)
>>> {
>>> + uint64_t save_start = start;
>>> size_t pos = start >> BITS_PER_LEVEL;
>>> size_t lastpos = last >> BITS_PER_LEVEL;
>>> bool changed = false;
>>> @@ -336,6 +344,10 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
>>> lastpos--;
>>> }
>>> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
>>> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
>>> + }
>>> +
>>> if (level > 0 && changed) {
>>> hb_reset_between(hb, level - 1, pos, lastpos);
>>> }
>>> @@ -384,6 +396,9 @@ void hbitmap_free(HBitmap *hb)
>>> for (i = HBITMAP_LEVELS; i-- > 0; ) {
>>> g_free(hb->levels[i]);
>>> }
>>> + if (hb->meta) {
>>> + hbitmap_free(hb->meta);
>>> + }
>>> g_free(hb);
>>> }
>>> @@ -493,3 +508,10 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
>>> return true;
>>> }
>>> +
>>> +HBitmap *hbitmap_create_meta(HBitmap *hb)
>>> +{
>>> + assert(!hb->meta);
>>> + hb->meta = hbitmap_alloc(hb->size, hb->granularity);
>>> + return hb->meta;
>>> +}
>>
>> --
>> Best regards,
>> Vladimir
>> * now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
>>
--
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2015-12-30 11:07 ` Fam Zheng
2015-12-30 11:26 ` Vladimir Sementsov-Ogievskiy
@ 2016-01-21 10:58 ` Vladimir Sementsov-Ogievskiy
2016-01-22 3:10 ` Fam Zheng
1 sibling, 1 reply; 18+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2016-01-21 10:58 UTC (permalink / raw)
To: Fam Zheng
Cc: Kevin Wolf, qemu-block, qemu-devel, Stefan Hajnoczi, pbonzini, jsnow
On 30.12.2015 14:07, Fam Zheng wrote:
> On Wed, 12/30 13:53, Vladimir Sementsov-Ogievskiy wrote:
>> On 07.12.2015 08:59, Fam Zheng wrote:
>>> The meta bitmap will have the same size and granularity as the tracked
>>> bitmap, and upon each bit toggle, the corresponding bit in the meta
>>> bitmap, at an identical position, will be set.
>>>
>>> Signed-off-by: Fam Zheng <famz@redhat.com>
>>> ---
>>> include/qemu/hbitmap.h | 7 +++++++
>>> util/hbitmap.c | 22 ++++++++++++++++++++++
>>> 2 files changed, 29 insertions(+)
>>>
>>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>>> index bb94a00..09a6b06 100644
>>> --- a/include/qemu/hbitmap.h
>>> +++ b/include/qemu/hbitmap.h
>>> @@ -181,6 +181,13 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
>>> */
>>> unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>>> +/* hbitmap_create_meta
>>> + * @hb: The HBitmap to operate on.
>>> + *
>>> + * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
>>> + */
>>> +HBitmap *hbitmap_create_meta(HBitmap *hb);
>>> +
>>> /**
>>> * hbitmap_iter_next:
>>> * @hbi: HBitmapIter to operate on.
>>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>>> index 50b888f..3ad406e 100644
>>> --- a/util/hbitmap.c
>>> +++ b/util/hbitmap.c
>>> @@ -81,6 +81,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
>>> @@ -232,6 +235,7 @@ static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t las
>>> /* 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)
>>> {
>>> + uint64_t save_start = start;
>>> size_t pos = start >> BITS_PER_LEVEL;
>>> size_t lastpos = last >> BITS_PER_LEVEL;
>>> bool changed = false;
>>> @@ -252,6 +256,9 @@ static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last
>>> }
>>> }
>>> changed |= hb_set_elem(&hb->levels[level][i], start, last);
>>> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
>>> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
>>> + }
>> I thing now, that the same may be accomplished for BdrvDirtyBitmap,
>> all we need is return "changed" status from hb_set_between and then
>> from hbitmap_set.
> That is true, but it makes further optimizing to *really* only set the toggled
> meta bits much more difficult (i.e. when only a few bits between start and last
> are changed).
Are you going add some optimization in following versions (v3 ?) or as
separate series, or other plan?
>
> I haven't written any code for that optimization, but I did base my other
> persistent dirty bitmap work on v2 of this series. It would be great if we can
> harmonize on this, so we both have a common base of block dirty bitmap.
>
> I can post v2 to the list very soon, if the idea is okay for you; or if you've
> your preferred way, we can take a look together. What do you think?
>
> Fam
>
>>> /* If there was any change in this layer, we may have to update
>>> * the one above.
>>> @@ -298,6 +305,7 @@ static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t l
>>> /* 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)
>>> {
>>> + uint64_t save_start = start;
>>> size_t pos = start >> BITS_PER_LEVEL;
>>> size_t lastpos = last >> BITS_PER_LEVEL;
>>> bool changed = false;
>>> @@ -336,6 +344,10 @@ static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t la
>>> lastpos--;
>>> }
>>> + if (hb->meta && level == HBITMAP_LEVELS - 1 && changed) {
>>> + hbitmap_set(hb->meta, save_start, last - save_start + 1);
>>> + }
>>> +
>>> if (level > 0 && changed) {
>>> hb_reset_between(hb, level - 1, pos, lastpos);
>>> }
>>> @@ -384,6 +396,9 @@ void hbitmap_free(HBitmap *hb)
>>> for (i = HBITMAP_LEVELS; i-- > 0; ) {
>>> g_free(hb->levels[i]);
>>> }
>>> + if (hb->meta) {
>>> + hbitmap_free(hb->meta);
>>> + }
>>> g_free(hb);
>>> }
>>> @@ -493,3 +508,10 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
>>> return true;
>>> }
>>> +
>>> +HBitmap *hbitmap_create_meta(HBitmap *hb)
>>> +{
>>> + assert(!hb->meta);
>>> + hb->meta = hbitmap_alloc(hb->size, hb->granularity);
>>> + return hb->meta;
>>> +}
>>
>> --
>> Best regards,
>> Vladimir
>> * now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
>>
--
Best regards,
Vladimir
* now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes
2016-01-21 10:58 ` Vladimir Sementsov-Ogievskiy
@ 2016-01-22 3:10 ` Fam Zheng
0 siblings, 0 replies; 18+ messages in thread
From: Fam Zheng @ 2016-01-22 3:10 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy
Cc: Kevin Wolf, qemu-block, qemu-devel, Stefan Hajnoczi, pbonzini, jsnow
On Thu, 01/21 13:58, Vladimir Sementsov-Ogievskiy wrote:
> >>I thing now, that the same may be accomplished for BdrvDirtyBitmap,
> >>all we need is return "changed" status from hb_set_between and then
> >>from hbitmap_set.
> >That is true, but it makes further optimizing to *really* only set the toggled
> >meta bits much more difficult (i.e. when only a few bits between start and last
> >are changed).
>
> Are you going add some optimization in following versions (v3 ?) or
> as separate series, or other plan?
I aim at a seperate series for that.
Fam
^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2016-01-22 3:10 UTC | newest]
Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-12-07 5:59 [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Fam Zheng
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes Fam Zheng
2015-12-07 13:32 ` Vladimir Sementsov-Ogievskiy
2015-12-08 1:31 ` Fam Zheng
2015-12-09 11:51 ` Vladimir Sementsov-Ogievskiy
2015-12-30 10:53 ` Vladimir Sementsov-Ogievskiy
2015-12-30 11:07 ` Fam Zheng
2015-12-30 11:26 ` Vladimir Sementsov-Ogievskiy
2016-01-21 10:58 ` Vladimir Sementsov-Ogievskiy
2016-01-22 3:10 ` Fam Zheng
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 2/3] tests: Add test code for meta bitmap Fam Zheng
2015-12-07 5:59 ` [Qemu-devel] [PATCH RFC for-2.6 3/3] block: Support meta dirty bitmap Fam Zheng
2015-12-07 14:19 ` [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence Vladimir Sementsov-Ogievskiy
2015-12-08 1:42 ` Fam Zheng
2015-12-09 11:46 ` Vladimir Sementsov-Ogievskiy
2015-12-07 23:47 ` John Snow
2015-12-08 1:36 ` Fam Zheng
2015-12-09 11:57 ` Vladimir Sementsov-Ogievskiy
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.