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 <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;
> >+}
> 
> 
> -- 
> Best regards,
> Vladimir
> * now, @virtuozzo.com instead of @parallels.com. Sorry for this inconvenience.
>