[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH v10 07/13] hbitmap: add hbitmap_merge
From: |
John Snow |
Subject: |
[Qemu-devel] [PATCH v10 07/13] hbitmap: add hbitmap_merge |
Date: |
Mon, 22 Dec 2014 20:12:16 -0500 |
We add a bitmap merge operation to assist in error cases
where we wish to combine two bitmaps together.
This is algorithmically O(bits) provided HBITMAP_LEVELS remains
constant. For a full bitmap on a 64bit machine:
sum(bits/64^k, k, 0, HBITMAP_LEVELS) ~= 1.01587 * bits
We may be able to improve running speed for particularly sparse
bitmaps by using iterators, but the running time for dense maps
will be worse.
We present the simpler solution first, and we can refine it later
if needed.
Signed-off-by: John Snow <address@hidden>
---
include/qemu/hbitmap.h | 11 +++++++++++
util/hbitmap.c | 28 ++++++++++++++++++++++++++++
2 files changed, 39 insertions(+)
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index b645cfc..c48c50a 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -73,6 +73,17 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity);
HBitmap *hbitmap_copy(const HBitmap *bitmap);
/**
+ * hbitmap_merge:
+ * @a: The bitmap to store the result in.
+ * @b: The bitmap to merge into @a.
+ *
+ * Merge two bitmaps together.
+ * A := A (BITOR) B.
+ * B is left unmodified.
+ */
+bool hbitmap_merge(HBitmap *a, const HBitmap *b);
+
+/**
* hbitmap_empty:
* @hb: HBitmap to operate on.
*
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 033ad58..f400dcb 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -415,3 +415,31 @@ HBitmap *hbitmap_copy(const HBitmap *bitmap)
return hb;
}
+
+/**
+ * Given HBitmaps A and B, let A := A (BITOR) B.
+ * Bitmap B will not be modified.
+ */
+bool hbitmap_merge(HBitmap *a, const HBitmap *b)
+{
+ int i, j;
+ uint64_t size;
+
+ if ((a->size != b->size) || (a->granularity != b->granularity)) {
+ return false;
+ }
+
+ /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
+ * It may be possible to improve running times for sparsely populated maps
+ * by using hbitmap_iter_next, but this is suboptimal for dense maps.
+ */
+ size = a->size;
+ for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
+ size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
+ for (j = 0; j < size; j++) {
+ a->levels[i][j] |= b->levels[i][j];
+ }
+ }
+
+ return true;
+}
--
1.9.3
- [Qemu-devel] [PATCH v10 00/13] block: Incremental backup series (RFC), John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 01/13] block: fix spoiling all dirty bitmaps by mirror and migration, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 02/13] qapi: Add optional field "name" to block dirty bitmap, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 03/13] qmp: Add block-dirty-bitmap-add and block-dirty-bitmap-remove, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 04/13] block: Introduce bdrv_dirty_bitmap_granularity(), John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 05/13] hbitmap: Add hbitmap_copy, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 07/13] hbitmap: add hbitmap_merge,
John Snow <=
- [Qemu-devel] [PATCH v10 06/13] block: Add bdrv_copy_dirty_bitmap and bdrv_clear_dirty_bitmap, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 10/13] qmp: Add support of "dirty-bitmap" sync mode for drive-backup, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 08/13] block: add bdrv_reclaim_dirty_bitmap, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 09/13] qmp: Add block-dirty-bitmap-enable and block-dirty-bitmap-disable, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 11/13] qapi: Add transaction support to block-dirty-bitmap-{add, enable, disable}, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 13/13] qemu-iotests: Add tests for drive-backup sync=dirty-bitmap, John Snow, 2014/12/22
- [Qemu-devel] [PATCH v10 12/13] qmp: Add dirty bitmap 'enabled' field in query-block, John Snow, 2014/12/22
- Re: [Qemu-devel] [PATCH v10 00/13] block: Incremental backup series (RFC), Vladimir Sementsov-Ogievskiy, 2014/12/23