qemu-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Qemu-devel] [PATCH 1/5] hbitmap: add next_zero function


From: John Snow
Subject: Re: [Qemu-devel] [PATCH 1/5] hbitmap: add next_zero function
Date: Mon, 9 Oct 2017 17:51:18 -0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0


On 10/02/2017 10:39 AM, Vladimir Sementsov-Ogievskiy wrote:
> The function searches for next zero bit.
> Also add interface for BdrvDirtyBitmap.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <address@hidden>
> ---
>  include/block/dirty-bitmap.h |  1 +
>  include/qemu/hbitmap.h       |  8 ++++++++
>  block/dirty-bitmap.c         |  5 +++++
>  util/hbitmap.c               | 29 +++++++++++++++++++++++++++++
>  4 files changed, 43 insertions(+)
> 
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 3579a7597c..a591c27213 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -91,5 +91,6 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState 
> *bs);
>  BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>                                          BdrvDirtyBitmap *bitmap);
>  char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
>  
>  #endif
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index 81e78043d1..6b6490ecad 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -292,6 +292,14 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap 
> *hb, uint64_t first);
>   */
>  unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>  
> +/* hbitmap_next_zero:
> + * @hb: The HBitmap to operate on
> + * @start: The bit to start from.
> + *
> + * Find next not dirty bit.
> + */
> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
> +
>  /* hbitmap_create_meta:
>   * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
>   * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index bd04e991b1..7879d13ddb 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -715,3 +715,8 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap 
> *bitmap, Error **errp)
>  {
>      return hbitmap_sha256(bitmap->bitmap, errp);
>  }
> +
> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset)
> +{
> +    return hbitmap_next_zero(bitmap->bitmap, offset);
> +}
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 2f9d0fdbd0..ffcdbc5587 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -188,6 +188,35 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap 
> *hb, uint64_t first)
>      }
>  }
>  
> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
> +{
> +    size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
> +    unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
> +    uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
> +    unsigned long cur = last_lev[pos];
> +    unsigned start_bit_offset =
> +            (start >> hb->granularity) & (BITS_PER_LONG - 1);
> +    int64_t res;

Prefer a line separating declarations from statements.

> +    cur |= (1UL << start_bit_offset) - 1;
> +    assert((start >> hb->granularity) < hb->size);
> +
> +    if (cur == (unsigned long)-1) {
> +        do {
> +            pos++;
> +        } while (pos < sz && last_lev[pos] == (unsigned long)-1);
> +
> +        if (pos >= sz) {
> +            return -1;
> +        }
> +
> +        cur = last_lev[pos];
> +    }
> +
> +    res = (pos << BITS_PER_LEVEL) + ctol(cur);
> +
> +    return res < hb->size ? (res << hb->granularity) : -1;
> +}
> +
>  bool hbitmap_empty(const HBitmap *hb)
>  {
>      return hb->count == 0;
> 

And a test would be nice.

Reviewed-by: John Snow <address@hidden>



reply via email to

[Prev in Thread] Current Thread [Next in Thread]