From: Juan Quintela <quintela@redhat.com>
To: qemu-devel@nongnu.org
Cc: Laurent Vivier <lvivier@redhat.com>,
Richard Henderson <rth@twiddle.net>,
Paolo Bonzini <pbonzini@redhat.com>,
kvm@vger.kernel.org,
"Dr. David Alan Gilbert" <dgilbert@redhat.com>,
Juan Quintela <quintela@redhat.com>,
Thomas Huth <thuth@redhat.com>, Peter Xu <peterx@redhat.com>
Subject: [PULL 11/19] bitmap: Add bitmap_copy_with_{src|dst}_offset()
Date: Fri, 12 Jul 2019 16:31:59 +0200 [thread overview]
Message-ID: <20190712143207.4214-12-quintela@redhat.com> (raw)
In-Reply-To: <20190712143207.4214-1-quintela@redhat.com>
From: Peter Xu <peterx@redhat.com>
These helpers copy the source bitmap to destination bitmap with a
shift either on the src or dst bitmap.
Meanwhile, we never have bitmap tests but we should.
This patch also introduces the initial test cases for utils/bitmap.c
but it only tests the newly introduced functions.
Signed-off-by: Peter Xu <peterx@redhat.com>
Reviewed-by: Juan Quintela <quintela@redhat.com>
Message-Id: <20190603065056.25211-5-peterx@redhat.com>
Signed-off-by: Juan Quintela <quintela@redhat.com>
---
Bitmap test used sizeof(unsigned long) instead of BITS_PER_LONG.
---
include/qemu/bitmap.h | 9 +++++
tests/Makefile.include | 2 +
tests/test-bitmap.c | 72 +++++++++++++++++++++++++++++++++++
util/bitmap.c | 85 ++++++++++++++++++++++++++++++++++++++++++
4 files changed, 168 insertions(+)
create mode 100644 tests/test-bitmap.c
diff --git a/include/qemu/bitmap.h b/include/qemu/bitmap.h
index 5c313346b9..82a1d2f41f 100644
--- a/include/qemu/bitmap.h
+++ b/include/qemu/bitmap.h
@@ -41,6 +41,10 @@
* bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area
* bitmap_to_le(dst, src, nbits) Convert bitmap to little endian
* bitmap_from_le(dst, src, nbits) Convert bitmap from little endian
+ * bitmap_copy_with_src_offset(dst, src, offset, nbits)
+ * *dst = *src (with an offset into src)
+ * bitmap_copy_with_dst_offset(dst, src, offset, nbits)
+ * *dst = *src (with an offset into dst)
*/
/*
@@ -271,4 +275,9 @@ void bitmap_to_le(unsigned long *dst, const unsigned long *src,
void bitmap_from_le(unsigned long *dst, const unsigned long *src,
long nbits);
+void bitmap_copy_with_src_offset(unsigned long *dst, const unsigned long *src,
+ unsigned long offset, unsigned long nbits);
+void bitmap_copy_with_dst_offset(unsigned long *dst, const unsigned long *src,
+ unsigned long shift, unsigned long nbits);
+
#endif /* BITMAP_H */
diff --git a/tests/Makefile.include b/tests/Makefile.include
index a983dd32da..fd7fdb8658 100644
--- a/tests/Makefile.include
+++ b/tests/Makefile.include
@@ -65,6 +65,7 @@ check-unit-y += tests/test-opts-visitor$(EXESUF)
check-unit-$(CONFIG_BLOCK) += tests/test-coroutine$(EXESUF)
check-unit-y += tests/test-visitor-serialization$(EXESUF)
check-unit-y += tests/test-iov$(EXESUF)
+check-unit-y += tests/test-bitmap$(EXESUF)
check-unit-$(CONFIG_BLOCK) += tests/test-aio$(EXESUF)
check-unit-$(CONFIG_BLOCK) += tests/test-aio-multithread$(EXESUF)
check-unit-$(CONFIG_BLOCK) += tests/test-throttle$(EXESUF)
@@ -538,6 +539,7 @@ tests/test-image-locking$(EXESUF): tests/test-image-locking.o $(test-block-obj-y
tests/test-thread-pool$(EXESUF): tests/test-thread-pool.o $(test-block-obj-y)
tests/test-iov$(EXESUF): tests/test-iov.o $(test-util-obj-y)
tests/test-hbitmap$(EXESUF): tests/test-hbitmap.o $(test-util-obj-y) $(test-crypto-obj-y)
+tests/test-bitmap$(EXESUF): tests/test-bitmap.o $(test-util-obj-y)
tests/test-x86-cpuid$(EXESUF): tests/test-x86-cpuid.o
tests/test-xbzrle$(EXESUF): tests/test-xbzrle.o migration/xbzrle.o migration/page_cache.o $(test-util-obj-y)
tests/test-cutils$(EXESUF): tests/test-cutils.o util/cutils.o $(test-util-obj-y)
diff --git a/tests/test-bitmap.c b/tests/test-bitmap.c
new file mode 100644
index 0000000000..cb7c5e462d
--- /dev/null
+++ b/tests/test-bitmap.c
@@ -0,0 +1,72 @@
+/*
+ * SPDX-License-Identifier: GPL-2.0-or-later
+ *
+ * Bitmap.c unit-tests.
+ *
+ * Copyright (C) 2019, Red Hat, Inc.
+ *
+ * Author: Peter Xu <peterx@redhat.com>
+ */
+
+#include <stdlib.h>
+#include "qemu/osdep.h"
+#include "qemu/bitmap.h"
+
+#define BMAP_SIZE 1024
+
+static void check_bitmap_copy_with_offset(void)
+{
+ unsigned long *bmap1, *bmap2, *bmap3, total;
+
+ bmap1 = bitmap_new(BMAP_SIZE);
+ bmap2 = bitmap_new(BMAP_SIZE);
+ bmap3 = bitmap_new(BMAP_SIZE);
+
+ bmap1[0] = random();
+ bmap1[1] = random();
+ bmap1[2] = random();
+ bmap1[3] = random();
+ total = BITS_PER_LONG * 4;
+
+ /* Shift 115 bits into bmap2 */
+ bitmap_copy_with_dst_offset(bmap2, bmap1, 115, total);
+ /* Shift another 85 bits into bmap3 */
+ bitmap_copy_with_dst_offset(bmap3, bmap2, 85, total + 115);
+ /* Shift back 200 bits back */
+ bitmap_copy_with_src_offset(bmap2, bmap3, 200, total);
+
+ g_assert_cmpmem(bmap1, total / BITS_PER_LONG,
+ bmap2, total / BITS_PER_LONG);
+
+ bitmap_clear(bmap1, 0, BMAP_SIZE);
+ /* Set bits in bmap1 are 100-245 */
+ bitmap_set(bmap1, 100, 145);
+
+ /* Set bits in bmap2 are 60-205 */
+ bitmap_copy_with_src_offset(bmap2, bmap1, 40, 250);
+ g_assert_cmpint(find_first_bit(bmap2, 60), ==, 60);
+ g_assert_cmpint(find_next_zero_bit(bmap2, 205, 60), ==, 205);
+ g_assert(test_bit(205, bmap2) == 0);
+
+ /* Set bits in bmap3 are 135-280 */
+ bitmap_copy_with_dst_offset(bmap3, bmap1, 35, 250);
+ g_assert_cmpint(find_first_bit(bmap3, 135), ==, 135);
+ g_assert_cmpint(find_next_zero_bit(bmap3, 280, 135), ==, 280);
+ g_assert(test_bit(280, bmap3) == 0);
+
+ g_free(bmap1);
+ g_free(bmap2);
+ g_free(bmap3);
+}
+
+int main(int argc, char **argv)
+{
+ g_test_init(&argc, &argv, NULL);
+
+ g_test_add_func("/bitmap/bitmap_copy_with_offset",
+ check_bitmap_copy_with_offset);
+
+ g_test_run();
+
+ return 0;
+}
diff --git a/util/bitmap.c b/util/bitmap.c
index cb618c65a5..1753ff7f5b 100644
--- a/util/bitmap.c
+++ b/util/bitmap.c
@@ -402,3 +402,88 @@ void bitmap_to_le(unsigned long *dst, const unsigned long *src,
{
bitmap_to_from_le(dst, src, nbits);
}
+
+/*
+ * Copy "src" bitmap with a positive offset and put it into the "dst"
+ * bitmap. The caller needs to make sure the bitmap size of "src"
+ * is bigger than (shift + nbits).
+ */
+void bitmap_copy_with_src_offset(unsigned long *dst, const unsigned long *src,
+ unsigned long shift, unsigned long nbits)
+{
+ unsigned long left_mask, right_mask, last_mask;
+
+ /* Proper shift src pointer to the first word to copy from */
+ src += BIT_WORD(shift);
+ shift %= BITS_PER_LONG;
+
+ if (!shift) {
+ /* Fast path */
+ bitmap_copy(dst, src, nbits);
+ return;
+ }
+
+ right_mask = (1ul << shift) - 1;
+ left_mask = ~right_mask;
+
+ while (nbits >= BITS_PER_LONG) {
+ *dst = (*src & left_mask) >> shift;
+ *dst |= (src[1] & right_mask) << (BITS_PER_LONG - shift);
+ dst++;
+ src++;
+ nbits -= BITS_PER_LONG;
+ }
+
+ if (nbits > BITS_PER_LONG - shift) {
+ *dst = (*src & left_mask) >> shift;
+ nbits -= BITS_PER_LONG - shift;
+ last_mask = (1ul << nbits) - 1;
+ *dst |= (src[1] & last_mask) << (BITS_PER_LONG - shift);
+ } else if (nbits) {
+ last_mask = (1ul << nbits) - 1;
+ *dst = (*src >> shift) & last_mask;
+ }
+}
+
+/*
+ * Copy "src" bitmap into the "dst" bitmap with an offset in the
+ * "dst". The caller needs to make sure the bitmap size of "dst" is
+ * bigger than (shift + nbits).
+ */
+void bitmap_copy_with_dst_offset(unsigned long *dst, const unsigned long *src,
+ unsigned long shift, unsigned long nbits)
+{
+ unsigned long left_mask, right_mask, last_mask;
+
+ /* Proper shift dst pointer to the first word to copy from */
+ dst += BIT_WORD(shift);
+ shift %= BITS_PER_LONG;
+
+ if (!shift) {
+ /* Fast path */
+ bitmap_copy(dst, src, nbits);
+ return;
+ }
+
+ right_mask = (1ul << (BITS_PER_LONG - shift)) - 1;
+ left_mask = ~right_mask;
+
+ *dst &= (1ul << shift) - 1;
+ while (nbits >= BITS_PER_LONG) {
+ *dst |= (*src & right_mask) << shift;
+ dst[1] = (*src & left_mask) >> (BITS_PER_LONG - shift);
+ dst++;
+ src++;
+ nbits -= BITS_PER_LONG;
+ }
+
+ if (nbits > BITS_PER_LONG - shift) {
+ *dst |= (*src & right_mask) << shift;
+ nbits -= BITS_PER_LONG - shift;
+ last_mask = ((1ul << nbits) - 1) << (BITS_PER_LONG - shift);
+ dst[1] = (*src & last_mask) >> (BITS_PER_LONG - shift);
+ } else if (nbits) {
+ last_mask = (1ul << nbits) - 1;
+ *dst |= (*src & last_mask) << shift;
+ }
+}
--
2.21.0
next prev parent reply other threads:[~2019-07-12 14:32 UTC|newest]
Thread overview: 30+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-07-12 14:31 [PULL 00/19] Migration patches Juan Quintela
2019-07-12 14:31 ` [PULL 01/19] migration: fix multifd_recv event typo Juan Quintela
2019-07-12 14:31 ` [PULL 02/19] migration-test: rename parameter to parameter_int Juan Quintela
2019-07-12 14:31 ` [PULL 03/19] migration-test: Add migration multifd test Juan Quintela
2019-07-12 14:31 ` [PULL 04/19] migration/multifd: call multifd_send_sync_main when sending RAM_SAVE_FLAG_EOS Juan Quintela
2019-07-12 14:31 ` [PULL 05/19] migration/xbzrle: update cache and current_data in one place Juan Quintela
2019-07-12 14:31 ` [PULL 06/19] cutils: remove one unnecessary pointer operation Juan Quintela
2019-07-12 14:31 ` [PULL 07/19] migration/multifd: sync packet_num after all thread are done Juan Quintela
2019-07-12 14:31 ` [PULL 08/19] migration/ram.c: reset complete_round when we gets a queued page Juan Quintela
2019-07-12 14:31 ` [PULL 09/19] migration: No need to take rcu during sync_dirty_bitmap Juan Quintela
2019-07-12 14:31 ` [PULL 10/19] memory: Don't set migration bitmap when without migration Juan Quintela
2019-07-12 14:31 ` Juan Quintela [this message]
2019-07-12 14:32 ` [PULL 12/19] memory: Pass mr into snapshot_and_clear_dirty Juan Quintela
2019-07-12 14:32 ` [PULL 13/19] memory: Introduce memory listener hook log_clear() Juan Quintela
2019-07-12 14:32 ` [PULL 14/19] kvm: Update comments for sync_dirty_bitmap Juan Quintela
2019-07-12 14:32 ` [PULL 15/19] kvm: Persistent per kvmslot dirty bitmap Juan Quintela
2019-07-12 14:32 ` [PULL 16/19] kvm: Introduce slots lock for memory listener Juan Quintela
2019-07-12 14:32 ` [PULL 17/19] kvm: Support KVM_CLEAR_DIRTY_LOG Juan Quintela
2019-07-12 14:32 ` [PULL 18/19] migration: Split log_clear() into smaller chunks Juan Quintela
2019-07-12 14:32 ` [PULL 19/19] migration: allow private destination ram with x-ignore-shared Juan Quintela
2019-07-12 16:33 ` [Qemu-devel] [PULL 00/19] Migration patches Peter Maydell
2019-07-12 17:54 ` Dr. David Alan Gilbert
2019-07-15 11:16 ` Peter Maydell
2019-07-15 13:44 ` Juan Quintela
2019-07-15 13:48 ` Peter Maydell
2019-07-15 14:10 ` Juan Quintela
2019-07-15 14:15 ` Peter Maydell
2019-07-15 14:04 ` [Qemu-devel] " Daniel P. Berrangé
2019-07-15 14:17 ` Peter Maydell
-- strict thread matches above, loose matches on Subject: below --
2019-07-11 10:43 Juan Quintela
2019-07-11 10:44 ` [PULL 11/19] bitmap: Add bitmap_copy_with_{src|dst}_offset() Juan Quintela
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=20190712143207.4214-12-quintela@redhat.com \
--to=quintela@redhat.com \
--cc=dgilbert@redhat.com \
--cc=kvm@vger.kernel.org \
--cc=lvivier@redhat.com \
--cc=pbonzini@redhat.com \
--cc=peterx@redhat.com \
--cc=qemu-devel@nongnu.org \
--cc=rth@twiddle.net \
--cc=thuth@redhat.com \
/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).