aboutsummaryrefslogtreecommitdiff
path: root/util
diff options
context:
space:
mode:
authorVladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>2017-06-28 15:05:03 +0300
committerMax Reitz <mreitz@redhat.com>2017-07-11 17:44:57 +0200
commitf63ea4e92bad1dbad58b198f51ac48657c1facbd (patch)
tree80dce0f2fd9c4b9df935e28af97c4ac5f784e0a2 /util
parentb348c262cc6d820a43b1453bc7d745c21619f8aa (diff)
downloadqemu-f63ea4e92bad1dbad58b198f51ac48657c1facbd.zip
qemu-f63ea4e92bad1dbad58b198f51ac48657c1facbd.tar.gz
qemu-f63ea4e92bad1dbad58b198f51ac48657c1facbd.tar.bz2
hbitmap: improve dirty iter
Make dirty iter resistant to resetting bits in corresponding HBitmap. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20170628120530.31251-4-vsementsov@virtuozzo.com Signed-off-by: Max Reitz <mreitz@redhat.com>
Diffstat (limited to 'util')
-rw-r--r--util/hbitmap.c23
1 files changed, 22 insertions, 1 deletions
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 35088e1..0b38817 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;