The function searches for next zero bit. Also add interface for BdrvDirtyBitmap.
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsement...@virtuozzo.com> --- 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; + 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; -- 2.11.1