Re: [Qemu-devel] [PATCH 11/18] hbitmap: Add @advance param to hbitmap_iter_next()

[Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>]

13.09.2017 21:19, Max Reitz wrote:
> This new parameter allows the caller to just query the next dirty
> position without moving the iterator.
>
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>   include/qemu/hbitmap.h |  4 +++-
>   block/dirty-bitmap.c   |  2 +-
>   tests/test-hbitmap.c   | 26 +++++++++++++-------------
>   util/hbitmap.c         | 10 +++++++---
>   4 files changed, 24 insertions(+), 18 deletions(-)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index d3a74a21fc..6a52575ad5 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -316,11 +316,13 @@ void hbitmap_free_meta(HBitmap *hb);
>   /**
>    * hbitmap_iter_next:
>    * @hbi: HBitmapIter to operate on.
> + * @advance: If true, advance the iterator.  Otherwise, the next call
> + *           of this function will return the same result.

it's not quit right, as hbitmap iterator allows concurrent resetting of 
bits, and in
this case next call may return some other result. (see f63ea4e92bad1db)

>    *
>    * Return the next bit that is set in @hbi's associated HBitmap,
>    * or -1 if all remaining bits are zero.
>    */
> -int64_t hbitmap_iter_next(HBitmapIter *hbi);
> +int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance);
>   
>   /**
>    * hbitmap_iter_next_word:
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 30462d4f9a..aee57cf8c8 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -547,7 +547,7 @@ void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
>   
>   int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
>   {
> -    return hbitmap_iter_next(&iter->hbi);
> +    return hbitmap_iter_next(&iter->hbi, true);
>   }
>   
>   /* Called within bdrv_dirty_bitmap_lock..unlock */
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 1acb353889..e6d4d563cb 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -46,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data,
>   
>       i = first;
>       for (;;) {
> -        next = hbitmap_iter_next(&hbi);
> +        next = hbitmap_iter_next(&hbi, true);
>           if (next < 0) {
>               next = data->size;
>           }
> @@ -435,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
>       /* Note that hbitmap_test_check has to be invoked manually in this test.  */
>       hbitmap_test_init(data, 131072 << 7, 7);
>       hbitmap_iter_init(&hbi, data->hb, 0);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   
>       hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
>       hbitmap_iter_init(&hbi, data->hb, 0);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   
>       hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   
>       hbitmap_test_set(data, (131072 << 7) - 8, 8);
>       hbitmap_iter_init(&hbi, data->hb, 0);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   
>       hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
> -    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
> +    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
>   }
>   
>   static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
> @@ -893,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
>       for (i = 0; i < num_positions; i++) {
>           hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
>           hbitmap_iter_init(&iter, data->hb, 0);
> -        next = hbitmap_iter_next(&iter);
> +        next = hbitmap_iter_next(&iter, true);
>           if (i == num_positions - 1) {
>               g_assert_cmpint(next, ==, -1);
>           } else {
> @@ -919,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>   
>       hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
>   
> -    hbitmap_iter_next(&hbi);
> +    hbitmap_iter_next(&hbi, true);
>   
>       hbitmap_reset_all(data->hb);
> -    hbitmap_iter_next(&hbi);
> +    hbitmap_iter_next(&hbi, true);
>   }
>   
>   int main(int argc, char **argv)
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 21535cc90b..96525983ce 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -141,7 +141,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
>       return cur;
>   }
>   
> -int64_t hbitmap_iter_next(HBitmapIter *hbi)
> +int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
>   {
>       unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
>               hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
> @@ -154,8 +154,12 @@ int64_t hbitmap_iter_next(HBitmapIter *hbi)
>           }
>       }
>   
> -    /* The next call will resume work from the next bit.  */
> -    hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
> +    if (advance) {
> +        /* The next call will resume work from the next bit.  */
> +        hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
> +    } else {
> +        hbi->cur[HBITMAP_LEVELS - 1] = cur;
> +    }
>       item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
>   
>       return item << hbi->granularity;


-- 
Best regards,
Vladimir