[Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence

[Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence

[Fam Zheng]

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

[Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Fam Zheng]

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

Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Vladimir Sementsov-Ogievskiy]

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.

Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Fam Zheng]

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.
> 

Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Vladimir Sementsov-Ogievskiy]

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.

Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Vladimir Sementsov-Ogievskiy]

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.

Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Fam Zheng]

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.
> 

Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Vladimir Sementsov-Ogievskiy]

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.

Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Vladimir Sementsov-Ogievskiy]

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.

Re: [Qemu-devel] [PATCH RFC for-2.6 1/3] HBitmap: Introduce "meta" bitmap to track bit changes

[Fam Zheng]

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

[Qemu-devel] [PATCH RFC for-2.6 2/3] tests: Add test code for meta bitmap

[Fam Zheng]

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

[Qemu-devel] [PATCH RFC for-2.6 3/3] 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.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

Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence

[Vladimir Sementsov-Ogievskiy]

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.

Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence

[Fam Zheng]

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.

Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence

[Vladimir Sementsov-Ogievskiy]

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.

Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence

[John Snow]

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(-)
> 

Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence

[Fam Zheng]

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(-)
> > 

Re: [Qemu-devel] [PATCH RFC for-2.6 0/3] block: Add meta dirty bitmap for migration/persistence

[Vladimir Sementsov-Ogievskiy]

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.