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