[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH RESEND 06/17] hbitmap: add hbitmap_merge
From: |
John Snow |
Subject: |
[Qemu-devel] [PATCH RESEND 06/17] hbitmap: add hbitmap_merge |
Date: |
Fri, 27 Feb 2015 19:47:46 -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>
Reviewed-by: Max Reitz <address@hidden>
Reviewed-by: Stefan Hajnoczi <address@hidden>
---
include/qemu/hbitmap.h | 11 +++++++++++
util/hbitmap.c | 32 ++++++++++++++++++++++++++++++++
2 files changed, 43 insertions(+)
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index 550d7ce..c19c1cb 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -65,6 +65,17 @@ struct HBitmapIter {
HBitmap *hbitmap_alloc(uint64_t size, int granularity);
/**
+ * 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 ab13971..962ff29 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -395,3 +395,35 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
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;
+ }
+
+ if (hbitmap_count(b) == 0) {
+ return true;
+ }
+
+ /* 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 RESEND 00/17] block: transactionless incremental backup series, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 05/17] block: Introduce bdrv_dirty_bitmap_granularity(), John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 03/17] qmp: Ensure consistent granularity type, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 01/17] docs: incremental backup documentation, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 04/17] qmp: Add block-dirty-bitmap-add and block-dirty-bitmap-remove, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 02/17] qapi: Add optional field "name" to block dirty bitmap, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 08/17] block: Add bitmap successors, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 07/17] block: Add bitmap disabled status, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 11/17] qmp: Add dirty bitmap status fields in query-block, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 06/17] hbitmap: add hbitmap_merge,
John Snow <=
- [Qemu-devel] [PATCH RESEND 09/17] qmp: Add support of "dirty-bitmap" sync mode for drive-backup, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 14/17] block: Resize bitmaps on bdrv_truncate, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 12/17] block: add BdrvDirtyBitmap documentation, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 15/17] iotests: add invalid input incremental backup tests, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 17/17] iotests: add incremental backup failure recovery test, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 16/17] iotests: add simple incremental backup case, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 10/17] qmp: add block-dirty-bitmap-clear, John Snow, 2015/02/27
- [Qemu-devel] [PATCH RESEND 13/17] block: Ensure consistent bitmap function prototypes, John Snow, 2015/02/27