From: Juan Quintela <quintela@redhat.com> To: qemu-devel@nongnu.org Cc: "Dr. David Alan Gilbert" <dgilbert@redhat.com>, Juan Quintela <quintela@redhat.com>, Laurent Vivier <lvivier@redhat.com>, kvm@vger.kernel.org, Thomas Huth <thuth@redhat.com>, Richard Henderson <rth@twiddle.net>, Paolo Bonzini <pbonzini@redhat.com>, Peter Xu <peterx@redhat.com> Subject: [PULL 11/19] bitmap: Add bitmap_copy_with_{src|dst}_offset() Date: Thu, 11 Jul 2019 12:44:04 +0200 Message-ID: <20190711104412.31233-12-quintela@redhat.com> (raw) In-Reply-To: <20190711104412.31233-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> --- 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..43f7ba26c5 --- /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 / sizeof(unsigned long), + bmap2, total / sizeof(unsigned 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 index Thread overview: 30+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-07-11 10:43 [PULL 00/19] Migration patches Juan Quintela 2019-07-11 10:43 ` [PULL 01/19] migration: fix multifd_recv event typo Juan Quintela 2019-07-11 10:43 ` [PULL 02/19] migration-test: rename parameter to parameter_int Juan Quintela 2019-07-11 10:43 ` [PULL 03/19] migration-test: Add migration multifd test Juan Quintela 2019-07-11 10:43 ` [PULL 04/19] migration/multifd: call multifd_send_sync_main when sending RAM_SAVE_FLAG_EOS Juan Quintela 2019-07-11 10:43 ` [PULL 05/19] migration/xbzrle: update cache and current_data in one place Juan Quintela 2019-07-11 10:43 ` [PULL 06/19] cutils: remove one unnecessary pointer operation Juan Quintela 2019-07-11 10:44 ` [PULL 07/19] migration/multifd: sync packet_num after all thread are done Juan Quintela 2019-07-11 10:44 ` [PULL 08/19] migratioin/ram.c: reset complete_round when we gets a queued page Juan Quintela 2019-07-11 10:44 ` [PULL 09/19] migration: No need to take rcu during sync_dirty_bitmap Juan Quintela 2019-07-11 10:44 ` [PULL 10/19] memory: Don't set migration bitmap when without migration Juan Quintela 2019-07-11 10:44 ` Juan Quintela [this message] 2019-07-11 10:44 ` [PULL 12/19] memory: Pass mr into snapshot_and_clear_dirty Juan Quintela 2019-07-11 10:44 ` [PULL 13/19] memory: Introduce memory listener hook log_clear() Juan Quintela 2019-07-11 10:44 ` [PULL 14/19] kvm: Update comments for sync_dirty_bitmap Juan Quintela 2019-07-11 10:44 ` [PULL 15/19] kvm: Persistent per kvmslot dirty bitmap Juan Quintela 2019-07-11 10:44 ` [PULL 16/19] kvm: Introduce slots lock for memory listener Juan Quintela 2019-07-11 10:44 ` [PULL 17/19] kvm: Support KVM_CLEAR_DIRTY_LOG Juan Quintela 2019-07-11 10:44 ` [PULL 19/19] migration: allow private destination ram with x-ignore-shared Juan Quintela 2019-07-11 11:19 ` [PULL 00/19] Migration patches Paolo Bonzini 2019-07-11 11:32 ` Juan Quintela 2019-07-11 11:34 ` Dr. David Alan Gilbert 2019-07-11 11:40 ` [Qemu-devel] " Peter Maydell 2019-07-11 12:39 ` Peter Maydell 2019-07-12 14:06 ` Juan Quintela 2019-07-11 12:55 ` Christian Borntraeger 2019-07-11 13:01 ` [Qemu-devel] " Peter Maydell 2019-07-11 13:00 ` no-reply 2019-07-12 14:33 ` no-reply 2019-07-12 14:31 Juan Quintela 2019-07-12 14:31 ` [PULL 11/19] bitmap: Add bitmap_copy_with_{src|dst}_offset() Juan Quintela
Reply instructions: You may reply publically 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=20190711104412.31233-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
KVM Archive on lore.kernel.org Archives are clonable: git clone --mirror https://lore.kernel.org/kvm/0 kvm/git/0.git # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V2 kvm kvm/ https://lore.kernel.org/kvm \ kvm@vger.kernel.org public-inbox-index kvm Example config snippet for mirrors Newsgroup available over NNTP: nntp://nntp.lore.kernel.org/org.kernel.vger.kvm AGPL code for this site: git clone https://public-inbox.org/public-inbox.git