[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v3 05/12] bitmap: Add bitmap_copy_with_{src|dst}
From: |
Peter Xu |
Subject: |
Re: [Qemu-devel] [PATCH v3 05/12] bitmap: Add bitmap_copy_with_{src|dst}_offset() |
Date: |
Fri, 31 May 2019 09:45:50 +0800 |
User-agent: |
Mutt/1.10.1 (2018-07-13) |
On Thu, May 30, 2019 at 12:05:27PM +0100, Dr. David Alan Gilbert wrote:
> * Peter Xu (address@hidden) wrote:
> > 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 <address@hidden>
> > ---
> > include/qemu/bitmap.h | 9 +++++
> > tests/Makefile.include | 2 ++
> > tests/test-bitmap.c | 81 ++++++++++++++++++++++++++++++++++++++++++
> > util/bitmap.c | 73 +++++++++++++++++++++++++++++++++++++
> > 4 files changed, 165 insertions(+)
> > create mode 100644 tests/test-bitmap.c
> >
> > diff --git a/include/qemu/bitmap.h b/include/qemu/bitmap.h
> > index 5c313346b9..cdaa953371 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 upon src)
>
> 'into' would be better than 'upon'
Ok.
>
> > + * bitmap_copy_with_dst_offset(dst, src, offset, nbits)
> > + * *dst = *src (with an offset upon 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,
> > + long offset, long nbits);
> > +void bitmap_copy_with_dst_offset(unsigned long *dst, const unsigned long
> > *src,
> > + long shift, long nbits);
> > +
> > #endif /* BITMAP_H */
> > diff --git a/tests/Makefile.include b/tests/Makefile.include
> > index 1865f6b322..5e2d7dddff 100644
> > --- a/tests/Makefile.include
> > +++ b/tests/Makefile.include
> > @@ -64,6 +64,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)
> > @@ -529,6 +530,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..36b4c07bf2
> > --- /dev/null
> > +++ b/tests/test-bitmap.c
> > @@ -0,0 +1,81 @@
> > +// SPDX-License-Identifier: GPL-2.0
>
> We probably shouldn't use GPL-2.0 for new; most stuff is 2.0-or-later
Ok.
>
> > +/*
> > + * Bitmap.c unit-tests.
> > + *
> > + * Copyright (C) 2019, Red Hat, Inc.
> > + *
> > + * Author: Peter Xu <address@hidden>
> > + */
> > +
> > +#include <stdlib.h>
> > +#include "qemu/osdep.h"
> > +#include "qemu/bitmap.h"
> > +
> > +#define BMAP_SIZE 1024
> > +
> > +static void check_bitmap_copy_with_offset(void)
> > +{
> > + int i;
> > + unsigned long *bmap1, *bmap2, *bmap3, total;
> > +
> > + bmap1 = bitmap_new(BMAP_SIZE);
> > + bmap2 = bitmap_new(BMAP_SIZE);
> > + bmap3 = bitmap_new(BMAP_SIZE);
> > +
> > + *bmap1 = 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);
> > +
> > + for (i = 0; i < 3; i++) {
> > + g_assert(*(bmap1 + i) == *(bmap2 + i));
> > + }
>
> can we get rid fo these loops with:
> g_assert_cmpmem(bmap1, total / 8, bmap2, total / 8)
Yes. I'm using BITS_PER_LONG instead of 8 though to suite 32bit.
>
> > + 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);
> > + for (i = 0; i < 60; i++) {
> > + g_assert(test_bit(i, bmap2) == 0);
> > + }
>
> g_assert_cmpint(find_first_bit(bmap2, 60), ==, 60)
Fixed.
>
> > + for (i = 60; i < 205; i++) {
> > + g_assert(test_bit(i, bmap2));
> > + }
>
> g_assert_cmpint(find_next_zero_bit(bmap2, 205, 60), == 205)
Fixed.
>
> > + g_assert(test_bit(205, bmap2) == 0);
> > +
> > + /* Set bits in bmap3 are 135-280 */
> > + bitmap_copy_with_dst_offset(bmap3, bmap1, 35, 250);
> > + for (i = 0; i < 135; i++) {
> > + g_assert(test_bit(i, bmap3) == 0);
> > + }
> > + for (i = 135; i < 280; i++) {
> > + g_assert(test_bit(i, bmap3));
> > + }
> > + 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..391a7bb744 100644
> > --- a/util/bitmap.c
> > +++ b/util/bitmap.c
> > @@ -402,3 +402,76 @@ 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,
> > + long shift, long nbits)
> > +{
> > + unsigned long left_mask, right_mask, last_mask;
> > +
> > + assert(shift >= 0);
>
> Just make shift and nbits unsigned long?
> (Interestingly bitops.h uses unsigned long everywhere where as bitmap
> uses long)
Sure.
>
> > + /* Proper shift src pointer to the first word to copy from */
> > + src += BIT_WORD(shift);
> > + shift %= BITS_PER_LONG;
[1]
> > + 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);
>
> src[1] ?
Sure.
>
> Also, perhaps you should only do this line if (right_mask), that way
> if the offset is a multiple of BITS_PER_LONG, you don't access the
> word after the end of the bitmap.
Indeed. Normally the real callers in this series won't happen with
that otherwise we don't need to call this function at all.
Instead of checking right_mask every time I think maybe I can just
provide a quick path at [1] above, then if I found shift==0 I'll go to
another memcpy() quick path.
(but that should never be used because if bitmap can be shifted as
long aligned then we don't even need to copy them in most cases but
instead we can just use bitmap[N])
>
> > + dst++;
> > + src++;
> > + nbits -= BITS_PER_LONG;
> > + }
> > +
> > + if (nbits > BITS_PER_LONG - shift) {
> > + *dst = (*src & left_mask) >> shift;
> > + nbits -= BITS_PER_LONG - shift;
> > + last_mask = (1 << nbits) - 1;
>
> 1ul
>
> > + *dst |= (*(src + 1) & last_mask) << (BITS_PER_LONG - shift);
> > + } else if (nbits) {
> > + last_mask = (1 << nbits) - 1;
>
> and again
>
> > + *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,
> > + long shift, long nbits)
> > +{
> > + unsigned long left_mask, right_mask, last_mask;
> > +
> > + assert(shift >= 0);
> > + /* Proper shift src pointer to the first word to copy from */
> ^^^
>
> dst
>
> > + dst += BIT_WORD(shift);
> > + shift %= BITS_PER_LONG;
> > + 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[1] ?
>
> > + dst++;
> > + src++;
> > + nbits -= BITS_PER_LONG;
> > + }
> > +
> > + if (nbits > BITS_PER_LONG - shift) {
> > + *dst |= (*src & right_mask) << shift;
> > + nbits -= BITS_PER_LONG - shift;
> > + last_mask = ((1 << nbits) - 1) << (BITS_PER_LONG - shift);
>
> 1ul
All fixed up for the rest. Thanks,
--
Peter Xu
- [Qemu-devel] [PATCH v3 00/12] kvm/migration: support KVM_CLEAR_DIRTY_LOG, Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 01/12] checkpatch: Allow SPDX-License-Identifier, Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 02/12] migration: No need to take rcu during sync_dirty_bitmap, Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 03/12] memory: Remove memory_region_get_dirty(), Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 04/12] memory: Don't set migration bitmap when without migration, Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 05/12] bitmap: Add bitmap_copy_with_{src|dst}_offset(), Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 06/12] memory: Pass mr into snapshot_and_clear_dirty, Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 07/12] memory: Introduce memory listener hook log_clear(), Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 08/12] kvm: Update comments for sync_dirty_bitmap, Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 09/12] kvm: Persistent per kvmslot dirty bitmap, Peter Xu, 2019/05/30
- [Qemu-devel] [PATCH v3 10/12] kvm: Introduce slots lock for memory listener, Peter Xu, 2019/05/30