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

[John Snow]

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

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

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

[Max Reitz]

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

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

Max



signature.asc
Description: OpenPGP digital signature

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

[Fam Zheng]

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

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

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