Re: [Qemu-devel] [PATCH 03/21] hbitmap: improve dirty iter

[John Snow]

On 11/09/2016 01:17 PM, Vladimir Sementsov-Ogievskiy wrote:
> Make dirty iter resistant to resetting bits in corresponding HBitmap.
>
> Signed-off-by: Vladimir Sementsov-Ogievskiy <address@hidden>
> Reviewed-by: Max Reitz <address@hidden>
> ---
>  include/qemu/hbitmap.h | 25 +++----------------------
>  util/hbitmap.c         | 23 ++++++++++++++++++++++-
>  2 files changed, 25 insertions(+), 23 deletions(-)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index eb46475..594f6f8 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -243,10 +243,8 @@ 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. Concurrent resetting of bits is OK,
> + * too.
>   */

Minor bikeshed: I might remove "too" because the concurrent resetting of 
bits is perfectly ok in /contrast/ to the concurrent setting of bits, 
which has undesirable side-effects.

I may simply strongly word this as:

"The concurrent resetting of bits is OK."

It's not worth a rewrite on its own.

Reviewed-by: John Snow <address@hidden>

>  void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
>
> @@ -285,24 +283,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;