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

[Vladimir Sementsov-Ogievskiy]

10.10.2017 00:51, John Snow wrote:
> 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;

here is a hidden mistake: we must consider case when start is not 
aligned to granularity, and if start bit is considered zero we should 
return start, not ((start >> gran) << gran)

> > +}
> > +
> >   bool hbitmap_empty(const HBitmap *hb)
> >   {
> >       return hb->count == 0;
> And a test would be nice.
>
> Reviewed-by: John Snow <address@hidden>


--
Best regards,
Vladimir