qemu-devel.nongnu.org archive mirror
 help / color / mirror / Atom feed
From: Kevin Wolf <kwolf@redhat.com>
To: qemu-block@nongnu.org
Cc: kwolf@redhat.com, qemu-devel@nongnu.org
Subject: [Qemu-devel] [PULL 55/76] hbitmap: add hbitmap_merge
Date: Tue, 28 Apr 2015 17:00:37 +0200	[thread overview]
Message-ID: <1430233258-31807-56-git-send-email-kwolf@redhat.com> (raw)
In-Reply-To: <1430233258-31807-1-git-send-email-kwolf@redhat.com>

From: John Snow <jsnow@redhat.com>

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 <jsnow@redhat.com>
Reviewed-by: Max Reitz <mreitz@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>
Message-id: 1429314609-29776-8-git-send-email-jsnow@redhat.com
Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
Signed-off-by: Kevin Wolf <kwolf@redhat.com>
---
 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

  parent reply	other threads:[~2015-04-28 15:02 UTC|newest]

Thread overview: 80+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-04-28 14:59 [Qemu-devel] [PULL 00/76] Block patches Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 01/76] savevm: create snapshot failed when id_str already exists Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 02/76] MAINTAINERS: Add myself as the maintainer of the Quorum driver Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 03/76] bt-sdp: fix broken uuids power-of-2 calculation Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 04/76] hw/arm/nseries: convert ffs(3) to ctz32() Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 05/76] uninorth: " Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 06/76] Convert (ffs(val) - 1) to ctz32(val) Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 07/76] Convert ffs() != 0 callers to ctz32() Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 08/76] sd: convert sd_normal_command() ffs(3) call " Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 09/76] omap_intc: convert ffs(3) to ctz32() in omap_inth_sir_update() Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 10/76] os-win32: drop ffs(3) prototype Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 11/76] checkpatch: complain about ffs(3) calls Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 12/76] block: Switch to host monotonic clock for IO throttling Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 13/76] aio-posix: move pollfds to thread-local storage Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 14/76] AioContext: acquire/release AioContext during aio_poll Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 15/76] iothread: release iothread around aio_poll Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 16/76] block-backend: Expose bdrv_write_zeroes() Kevin Wolf
2015-04-28 14:59 ` [Qemu-devel] [PULL 17/76] qemu-img convert: Rewrite copying logic Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 18/76] qemu-iotests: Some qemu-img convert tests Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 19/76] blkdebug: Add bdrv_truncate() Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 20/76] vhdx: Fix zero-fill iov length Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 21/76] thread-pool: clean up thread_pool_completion_bh() Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 22/76] scripts: add 'qemu coroutine' command to qemu-gdb.py Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 23/76] block/null: Latency simulation by adding new option "latency-ns" Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 24/76] block/null: Support reopen Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 25/76] MAINTAINERS: Add Fam Zheng as Null block driver maintainer Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 26/76] blockjob: Allow nested pause Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 27/76] block: Pause block jobs in bdrv_drain_all Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 28/76] qemu-iotests: Test that "stop" doesn't drain block jobs Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 29/76] blockjob: Update function name in comments Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 30/76] block: avoid unnecessary bottom halves Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 31/76] virtio_blk: comment fix Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 32/76] m25p80: add missing blk_attach_dev_nofail Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 33/76] m25p80: fix s->blk usage before assignment Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 34/76] block: document block-stream in qmp-commands.hx Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 35/76] block: add bdrv_get_device_or_node_name() Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 36/76] block: use bdrv_get_device_or_node_name() in error messages Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 37/76] block: add 'node-name' field to BLOCK_IMAGE_CORRUPTED Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 38/76] Revert "hmp: fix crash in 'info block -n -v'" Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 39/76] qmp: fill in the image field in BlockDeviceInfo Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 40/76] block/iscsi: do not forget to logout from target Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 41/76] block/iscsi: change all iscsilun properties from uint8_t to bool Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 42/76] block/iscsi: rename iscsi_write_protected and let it return void Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 43/76] block/iscsi: store DPOFUA bit from the modesense command Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 44/76] block/iscsi: optimize WRITE10/16 if cache.writeback is not set Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 45/76] block/iscsi: increase retry count Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 46/76] block/iscsi: handle SCSI_STATUS_TASK_SET_FULL Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 47/76] block/iscsi: bump year in copyright notice Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 48/76] block/iscsi: use the allocationmap also if cache.direct=on Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 49/76] docs: incremental backup documentation Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 50/76] qapi: Add optional field "name" to block dirty bitmap Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 51/76] qmp: Ensure consistent granularity type Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 52/76] qmp: Add block-dirty-bitmap-add and block-dirty-bitmap-remove Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 53/76] block: Introduce bdrv_dirty_bitmap_granularity() Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 54/76] hbitmap: cache array lengths Kevin Wolf
2015-04-28 15:00 ` Kevin Wolf [this message]
2015-04-28 15:00 ` [Qemu-devel] [PULL 56/76] block: Add bitmap disabled status Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 57/76] block: Add bitmap successors Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 58/76] qmp: Add support of "dirty-bitmap" sync mode for drive-backup Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 59/76] qmp: add block-dirty-bitmap-clear Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 60/76] qmp: Add dirty bitmap status field in query-block Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 61/76] block: add BdrvDirtyBitmap documentation Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 62/76] block: Ensure consistent bitmap function prototypes Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 63/76] block: Resize bitmaps on bdrv_truncate Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 64/76] hbitmap: truncate tests Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 65/76] iotests: add invalid input incremental backup tests Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 66/76] iotests: add QMP event waiting queue Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 67/76] iotests: add simple incremental backup case Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 68/76] iotests: add incremental backup failure recovery test Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 69/76] iotests: add incremental backup granularity tests Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 70/76] block/mirror: Always call block_job_sleep_ns() Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 71/76] block/dmg: make it modular Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 72/76] vmdk: Widen before shifting 32 bit header field Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 73/76] block: replace bdrv_states iteration with bdrv_next() Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 74/76] block: add bdrv_set_dirty()/bdrv_reset_dirty() to block_int.h Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 75/76] block: extract bdrv_setup_io_funcs() Kevin Wolf
2015-04-28 15:00 ` [Qemu-devel] [PULL 76/76] block: move I/O request processing to block/io.c Kevin Wolf
2015-04-28 17:15   ` [Qemu-devel] [Qemu-block] " Eric Blake
2015-04-29  8:27     ` Kevin Wolf
2015-04-28 17:58 ` [Qemu-devel] [PULL 00/76] Block patches Peter Maydell

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1430233258-31807-56-git-send-email-kwolf@redhat.com \
    --to=kwolf@redhat.com \
    --cc=qemu-block@nongnu.org \
    --cc=qemu-devel@nongnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).