diff mbox

[05/21] hbitmap: improve dirty iter

Message ID 1482503344-6424-6-git-send-email-vsementsov@virtuozzo.com
State New
Headers show

Commit Message

Vladimir Sementsov-Ogievskiy Dec. 23, 2016, 2:28 p.m. UTC 
Make dirty iter resistant to resetting bits in corresponding HBitmap.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/qemu/hbitmap.h | 24 ++----------------------
 util/hbitmap.c         | 23 ++++++++++++++++++++++-
 2 files changed, 24 insertions(+), 23 deletions(-)

Comments

Stefan Hajnoczi Jan. 31, 2017, 11:20 a.m. UTC | #1 
On Fri, Dec 23, 2016 at 05:28:48PM +0300, Vladimir Sementsov-Ogievskiy wrote:
> Make dirty iter resistant to resetting bits in corresponding HBitmap.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/qemu/hbitmap.h | 24 ++----------------------
>  util/hbitmap.c         | 23 ++++++++++++++++++++++-
>  2 files changed, 24 insertions(+), 23 deletions(-)

Please add a test case to tests/test-hbitmap.c.
Stefan Hajnoczi Jan. 31, 2017, 11:29 a.m. UTC | #2 
On Fri, Dec 23, 2016 at 05:28:48PM +0300, Vladimir Sementsov-Ogievskiy wrote:
> Make dirty iter resistant to resetting bits in corresponding HBitmap.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/qemu/hbitmap.h | 24 ++----------------------
>  util/hbitmap.c         | 23 ++++++++++++++++++++++-
>  2 files changed, 24 insertions(+), 23 deletions(-)
> 
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index eb46475..2873a46 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -243,10 +243,7 @@ void hbitmap_free(HBitmap *hb);
>   * the lowest-numbered bit that is set in @hb, starting at @first.
>   *
>   * Concurrent setting of bits is acceptable, and will at worst cause the
> - * iteration to miss some of those bits.  Resetting bits before the current
> - * position of the iterator is also okay.  However, concurrent resetting of
> - * bits can lead to unexpected behavior if the iterator has not yet reached
> - * those bits.
> + * iteration to miss some of those bits.  Resetting bits is also okay.
>   */
>  void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);

Do you need to modify hbitmap_iter_next_word() as well?  Otherwise it
uses the hbi->cur[] cached information and does not handle clearing bits
ahead of the iterator.

Stefan
diff mbox

Patch

diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index eb46475..2873a46 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -243,10 +243,7 @@  void hbitmap_free(HBitmap *hb);
  * the lowest-numbered bit that is set in @hb, starting at @first.
  *
  * Concurrent setting of bits is acceptable, and will at worst cause the
- * iteration to miss some of those bits.  Resetting bits before the current
- * position of the iterator is also okay.  However, concurrent resetting of
- * bits can lead to unexpected behavior if the iterator has not yet reached
- * those bits.
+ * iteration to miss some of those bits.  Resetting bits is also okay.
  */
 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
 
@@ -285,24 +282,7 @@  void hbitmap_free_meta(HBitmap *hb);
  * Return the next bit that is set in @hbi's associated HBitmap,
  * or -1 if all remaining bits are zero.
  */
-static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
-{
-    unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
-    int64_t item;
-
-    if (cur == 0) {
-        cur = hbitmap_iter_skip_words(hbi);
-        if (cur == 0) {
-            return -1;
-        }
-    }
-
-    /* The next call will resume work from the next bit.  */
-    hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
-    item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
-
-    return item << hbi->granularity;
-}
+int64_t hbitmap_iter_next(HBitmapIter *hbi);
 
 /**
  * hbitmap_iter_next_word:
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 5d1a21c..48d8b2d 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -106,8 +106,9 @@  unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
 
     unsigned long cur;
     do {
-        cur = hbi->cur[--i];
+        i--;
         pos >>= BITS_PER_LEVEL;
+        cur = hbi->cur[i] & hb->levels[i][pos];
     } while (cur == 0);
 
     /* Check for end of iteration.  We always use fewer than BITS_PER_LONG
@@ -139,6 +140,26 @@  unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
     return cur;
 }
 
+int64_t hbitmap_iter_next(HBitmapIter *hbi)
+{
+    unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
+            hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
+    int64_t item;
+
+    if (cur == 0) {
+        cur = hbitmap_iter_skip_words(hbi);
+        if (cur == 0) {
+            return -1;
+        }
+    }
+
+    /* The next call will resume work from the next bit.  */
+    hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
+    item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
+
+    return item << hbi->granularity;
+}
+
 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
 {
     unsigned i, bit;