The function searches for next zero bit.
Also add interface for BdrvDirtyBitmap.
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@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
On 10/02/2017 09:39 AM, Vladimir Sementsov-Ogievskiy wrote:
> The function searches for next zero bit.
> Also add interface for BdrvDirtyBitmap.
>
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@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(+)
>
> +++ 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);
> +}
Returns an answer in the same scale as the underlying hbitmap; if this
is applied before my byte-based dirty bitmap series, that means offset
is a sector count and the result is likewise a sector number (awkward);
if this is applied after my series, you pass in a byte offset start and
get a byte result (nice).
I don't see any obvious errors in the implementation, but DO think that
you should include a testsuite enhancement in tests/test-hbitmap.c to
cover the new functionality before we accept this.
--
Eric Blake, Principal Software Engineer
Red Hat, Inc. +1-919-301-3266
Virtualization: qemu.org | libvirt.org
02.10.2017 18:43, Eric Blake wrote:
> On 10/02/2017 09:39 AM, Vladimir Sementsov-Ogievskiy wrote:
>> The function searches for next zero bit.
>> Also add interface for BdrvDirtyBitmap.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@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(+)
>>
>> +++ 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);
>> +}
> Returns an answer in the same scale as the underlying hbitmap; if this
> is applied before my byte-based dirty bitmap series, that means offset
> is a sector count and the result is likewise a sector number (awkward);
> if this is applied after my series, you pass in a byte offset start and
> get a byte result (nice).
Oh, I forget to say it: it's based on your series)
>
> I don't see any obvious errors in the implementation, but DO think that
> you should include a testsuite enhancement in tests/test-hbitmap.c to
> cover the new functionality before we accept this.
>
--
Best regards,
Vladimir
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 <vsementsov@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;
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 <jsnow@redhat.com>
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 <vsementsov@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;
> 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 <jsnow@redhat.com>
--
Best regards,
Vladimir
© 2016 - 2026 Red Hat, Inc.