[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH v4 07/15] HBitmap: Introduce "meta" bitmap to track
From: |
Fam Zheng |
Subject: |
[Qemu-devel] [PATCH v4 07/15] HBitmap: Introduce "meta" bitmap to track bit changes |
Date: |
Tue, 8 Mar 2016 12:44:58 +0800 |
Upon each bit toggle, the corresponding bit in the meta bitmap will be
set.
Signed-off-by: Fam Zheng <address@hidden>
Reviewed-by: John Snow <address@hidden>
---
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 00/15] Dirty bitmap changes for migration/persistence work, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 01/15] backup: Use Bitmap to replace "s->bitmap", Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 02/15] block: Include hbitmap.h in block.h, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 03/15] typedefs: Add BdrvDirtyBitmap, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 05/15] block: Remove unused typedef of BlockDriverDirtyHandler, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 04/15] block: Move block dirty bitmap code to separate files, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 06/15] block: Hide HBitmap in block dirty bitmap interface, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 07/15] HBitmap: Introduce "meta" bitmap to track bit changes,
Fam Zheng <=
- [Qemu-devel] [PATCH v4 08/15] tests: Add test code for meta bitmap, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 09/15] block: Support meta dirty bitmap, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 10/15] block: Add two dirty bitmap getters, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 11/15] block: Assert that bdrv_release_dirty_bitmap succeeded, Fam Zheng, 2016/03/07
- [Qemu-devel] [PATCH v4 12/15] hbitmap: serialization, Fam Zheng, 2016/03/07