[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-block] [PATCH 1/5] hbitmap: add next_zero function
From: |
Vladimir Sementsov-Ogievskiy |
Subject: |
[Qemu-block] [PATCH 1/5] hbitmap: add next_zero function |
Date: |
Mon, 2 Oct 2017 17:39:15 +0300 |
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;
+ 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
- [Qemu-block] [PATCH 0/5] backup improvements part 1, Vladimir Sementsov-Ogievskiy, 2017/10/02
- [Qemu-block] [PATCH 5/5] backup: use copy_bitmap in incremental backup, Vladimir Sementsov-Ogievskiy, 2017/10/02
- [Qemu-block] [PATCH 1/5] hbitmap: add next_zero function,
Vladimir Sementsov-Ogievskiy <=
- [Qemu-block] [PATCH 3/5] backup: init copy_bitmap from sync_bitmap for incremental, Vladimir Sementsov-Ogievskiy, 2017/10/02
- [Qemu-block] [PATCH 2/5] backup: move from done_bitmap to copy_bitmap, Vladimir Sementsov-Ogievskiy, 2017/10/02
- Re: [Qemu-block] [Qemu-devel] [PATCH 0/5] backup improvements part 1, Eric Blake, 2017/10/02