Signed-off-by: Fam Zheng <address@hidden>
---
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;
+}