[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-block] [PULL 55/76] hbitmap: add hbitmap_merge
From: |
Kevin Wolf |
Subject: |
[Qemu-block] [PULL 55/76] hbitmap: add hbitmap_merge |
Date: |
Tue, 28 Apr 2015 17:00:37 +0200 |
From: John Snow <address@hidden>
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: Eric Blake <address@hidden>
Reviewed-by: Stefan Hajnoczi <address@hidden>
Message-id: address@hidden
Signed-off-by: Stefan Hajnoczi <address@hidden>
Signed-off-by: Kevin Wolf <address@hidden>
---
include/qemu/hbitmap.h | 13 +++++++++++++
util/hbitmap.c | 33 +++++++++++++++++++++++++++++++++
2 files changed, 46 insertions(+)
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index 550d7ce..6cb2d0e 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -65,6 +65,19 @@ 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.
+ * @return true if the merge was successful,
+ * false if it was not attempted.
+ *
+ * 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 5b78613..150d6e9 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -399,3 +399,36 @@ 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.
+ *
+ * @return true if the merge was successful,
+ * false if it was not attempted.
+ */
+bool hbitmap_merge(HBitmap *a, const HBitmap *b)
+{
+ int i;
+ uint64_t j;
+
+ 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.
+ */
+ for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
+ for (j = 0; j < a->sizes[i]; j++) {
+ a->levels[i][j] |= b->levels[i][j];
+ }
+ }
+
+ return true;
+}
--
1.8.3.1
- [Qemu-block] [PULL 45/76] block/iscsi: increase retry count, (continued)
- [Qemu-block] [PULL 45/76] block/iscsi: increase retry count, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 46/76] block/iscsi: handle SCSI_STATUS_TASK_SET_FULL, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 47/76] block/iscsi: bump year in copyright notice, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 48/76] block/iscsi: use the allocationmap also if cache.direct=on, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 49/76] docs: incremental backup documentation, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 50/76] qapi: Add optional field "name" to block dirty bitmap, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 51/76] qmp: Ensure consistent granularity type, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 52/76] qmp: Add block-dirty-bitmap-add and block-dirty-bitmap-remove, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 53/76] block: Introduce bdrv_dirty_bitmap_granularity(), Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 54/76] hbitmap: cache array lengths, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 55/76] hbitmap: add hbitmap_merge,
Kevin Wolf <=
- [Qemu-block] [PULL 56/76] block: Add bitmap disabled status, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 57/76] block: Add bitmap successors, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 58/76] qmp: Add support of "dirty-bitmap" sync mode for drive-backup, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 59/76] qmp: add block-dirty-bitmap-clear, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 60/76] qmp: Add dirty bitmap status field in query-block, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 61/76] block: add BdrvDirtyBitmap documentation, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 62/76] block: Ensure consistent bitmap function prototypes, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 64/76] hbitmap: truncate tests, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 63/76] block: Resize bitmaps on bdrv_truncate, Kevin Wolf, 2015/04/28
- [Qemu-block] [PULL 65/76] iotests: add invalid input incremental backup tests, Kevin Wolf, 2015/04/28