From nobody Sat Nov 1 22:28:30 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) client-ip=208.118.235.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; spf=pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org Return-Path: Received: from lists.gnu.org (208.118.235.17 [208.118.235.17]) by mx.zohomail.com with SMTPS id 1509697845337481.10553113406525; Fri, 3 Nov 2017 01:30:45 -0700 (PDT) Received: from localhost ([::1]:35376 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eAXN9-00064M-B8 for importer@patchew.org; Fri, 03 Nov 2017 04:30:39 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:45727) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eAXL9-0004qp-LH for qemu-devel@nongnu.org; Fri, 03 Nov 2017 04:28:37 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eAXL6-0001zO-GF for qemu-devel@nongnu.org; Fri, 03 Nov 2017 04:28:35 -0400 Received: from mga14.intel.com ([192.55.52.115]:64782) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eAXL6-0001yr-2z for qemu-devel@nongnu.org; Fri, 03 Nov 2017 04:28:32 -0400 Received: from fmsmga006.fm.intel.com ([10.253.24.20]) by fmsmga103.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 03 Nov 2017 01:28:19 -0700 Received: from devel-ww.sh.intel.com ([10.239.48.92]) by fmsmga006.fm.intel.com with ESMTP; 03 Nov 2017 01:28:16 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.44,337,1505804400"; d="scan'208";a="171493290" From: Wei Wang To: virtio-dev@lists.oasis-open.org, linux-kernel@vger.kernel.org, qemu-devel@nongnu.org, virtualization@lists.linux-foundation.org, kvm@vger.kernel.org, linux-mm@kvack.org, mst@redhat.com, mhocko@kernel.org, akpm@linux-foundation.org, mawilcox@microsoft.com Date: Fri, 3 Nov 2017 16:13:02 +0800 Message-Id: <1509696786-1597-3-git-send-email-wei.w.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1509696786-1597-1-git-send-email-wei.w.wang@intel.com> References: <1509696786-1597-1-git-send-email-wei.w.wang@intel.com> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 192.55.52.115 Subject: [Qemu-devel] [PATCH v17 2/6] radix tree test suite: add tests for xbitmap X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: aarcange@redhat.com, yang.zhang.wz@gmail.com, david@redhat.com, penguin-kernel@I-love.SAKURA.ne.jp, liliang.opensource@gmail.com, willy@infradead.org, amit.shah@redhat.com, wei.w.wang@intel.com, quan.xu@aliyun.com, cornelia.huck@de.ibm.com, pbonzini@redhat.com, mgorman@techsingularity.net Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail: RSF_0 Z_629925259 SPT_0 Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" From: Matthew Wilcox Add the following tests for xbitmap: 1) single bit test: single bit set/clear/find; 2) bit range test: set/clear a range of bits and find a 0 or 1 bit in the range. Signed-off-by: Wei Wang Cc: Matthew Wilcox Cc: Andrew Morton Cc: Michael S. Tsirkin --- tools/include/linux/bitmap.h | 34 ++++ tools/include/linux/kernel.h | 2 + tools/testing/radix-tree/Makefile | 7 +- tools/testing/radix-tree/linux/kernel.h | 2 - tools/testing/radix-tree/main.c | 5 + tools/testing/radix-tree/test.h | 1 + tools/testing/radix-tree/xbitmap.c | 278 ++++++++++++++++++++++++++++= ++++ 7 files changed, 326 insertions(+), 3 deletions(-) create mode 100644 tools/testing/radix-tree/xbitmap.c diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h index e8b9f51..890dab2 100644 --- a/tools/include/linux/bitmap.h +++ b/tools/include/linux/bitmap.h @@ -36,6 +36,40 @@ static inline void bitmap_zero(unsigned long *dst, int n= bits) } } =20 +static inline void __bitmap_clear(unsigned long *map, unsigned int start, + int len) +{ + unsigned long *p =3D map + BIT_WORD(start); + const unsigned int size =3D start + len; + int bits_to_clear =3D BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_clear =3D BITMAP_FIRST_WORD_MASK(start); + + while (len - bits_to_clear >=3D 0) { + *p &=3D ~mask_to_clear; + len -=3D bits_to_clear; + bits_to_clear =3D BITS_PER_LONG; + mask_to_clear =3D ~0UL; + p++; + } + if (len) { + mask_to_clear &=3D BITMAP_LAST_WORD_MASK(size); + *p &=3D ~mask_to_clear; + } +} + +static inline __always_inline void bitmap_clear(unsigned long *map, + unsigned int start, + unsigned int nbits) +{ + if (__builtin_constant_p(nbits) && nbits =3D=3D 1) + __clear_bit(start, map); + else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) && + __builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8)) + memset((char *)map + start / 8, 0, nbits / 8); + else + __bitmap_clear(map, start, nbits); +} + static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) { unsigned int nlongs =3D BITS_TO_LONGS(nbits); diff --git a/tools/include/linux/kernel.h b/tools/include/linux/kernel.h index 77d2e94..21e90ee 100644 --- a/tools/include/linux/kernel.h +++ b/tools/include/linux/kernel.h @@ -12,6 +12,8 @@ #define UINT_MAX (~0U) #endif =20 +#define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) =3D=3D 0) + #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) =20 #define PERF_ALIGN(x, a) __PERF_ALIGN_MASK(x, (typeof(x))(a)-1) diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/M= akefile index 6a9480c..fc7cb422 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -5,7 +5,8 @@ LDLIBS+=3D -lpthread -lurcu TARGETS =3D main idr-test multiorder CORE_OFILES :=3D radix-tree.o idr.o linux.o test.o find_bit.o OFILES =3D main.o $(CORE_OFILES) regression1.o regression2.o regression3.o= \ - tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o + tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o \ + xbitmap.o =20 ifndef SHIFT SHIFT=3D3 @@ -24,6 +25,9 @@ idr-test: idr-test.o $(CORE_OFILES) =20 multiorder: multiorder.o $(CORE_OFILES) =20 +xbitmap: xbitmap.o $(CORE_OFILES) + $(CC) $(CFLAGS) $(LDFLAGS) $^ -o xbitmap + clean: $(RM) $(TARGETS) *.o radix-tree.c idr.c generated/map-shift.h =20 @@ -33,6 +37,7 @@ $(OFILES): Makefile *.h */*.h generated/map-shift.h \ ../../include/linux/*.h \ ../../include/asm/*.h \ ../../../include/linux/radix-tree.h \ + ../../../include/linux/xbitmap.h \ ../../../include/linux/idr.h =20 radix-tree.c: ../../../lib/radix-tree.c diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-= tree/linux/kernel.h index b21a77f..c1e6088 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -16,6 +16,4 @@ #define pr_debug printk #define pr_cont printk =20 -#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) - #endif /* _KERNEL_H */ diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/mai= n.c index bc9a784..6f4774e 100644 --- a/tools/testing/radix-tree/main.c +++ b/tools/testing/radix-tree/main.c @@ -337,6 +337,11 @@ static void single_thread_tests(bool long_run) rcu_barrier(); printv(2, "after copy_tag_check: %d allocated, preempt %d\n", nr_allocated, preempt_count); + + xbitmap_checks(); + rcu_barrier(); + printv(2, "after xbitmap_checks: %d allocated, preempt %d\n", + nr_allocated, preempt_count); } =20 int main(int argc, char **argv) diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/tes= t.h index 0f8220c..f8dcdaa 100644 --- a/tools/testing/radix-tree/test.h +++ b/tools/testing/radix-tree/test.h @@ -36,6 +36,7 @@ void iteration_test(unsigned order, unsigned duration); void benchmark(void); void idr_checks(void); void ida_checks(void); +void xbitmap_checks(void); void ida_thread_tests(void); =20 struct item * diff --git a/tools/testing/radix-tree/xbitmap.c b/tools/testing/radix-tree/= xbitmap.c new file mode 100644 index 0000000..bee8a38 --- /dev/null +++ b/tools/testing/radix-tree/xbitmap.c @@ -0,0 +1,278 @@ +#include +#include +#include +#include "../../../include/linux/xbitmap.h" + +static DEFINE_XB(xb1); + +int xb_set_bit(struct xb *xb, unsigned long bit) +{ + int err; + unsigned long index =3D bit / IDA_BITMAP_BITS; + struct radix_tree_root *root =3D &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned long ebit; + + bit %=3D IDA_BITMAP_BITS; + ebit =3D bit + 2; + + err =3D __radix_tree_create(root, index, 0, &node, &slot); + if (err) + return err; + bitmap =3D rcu_dereference_raw(*slot); + if (radix_tree_exception(bitmap)) { + unsigned long tmp =3D (unsigned long)bitmap; + + if (ebit < BITS_PER_LONG) { + tmp |=3D 1UL << ebit; + rcu_assign_pointer(*slot, (void *)tmp); + return 0; + } + bitmap =3D this_cpu_xchg(ida_bitmap, NULL); + if (!bitmap) + return -EAGAIN; + memset(bitmap, 0, sizeof(*bitmap)); + bitmap->bitmap[0] =3D tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT; + rcu_assign_pointer(*slot, bitmap); + } + + if (!bitmap) { + if (ebit < BITS_PER_LONG) { + bitmap =3D (void *)((1UL << ebit) | + RADIX_TREE_EXCEPTIONAL_ENTRY); + __radix_tree_replace(root, node, slot, bitmap, NULL, + NULL); + return 0; + } + bitmap =3D this_cpu_xchg(ida_bitmap, NULL); + if (!bitmap) + return -EAGAIN; + memset(bitmap, 0, sizeof(*bitmap)); + __radix_tree_replace(root, node, slot, bitmap, NULL, NULL); + } + + __set_bit(bit, bitmap->bitmap); + return 0; +} + +int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp) +{ + int ret =3D 0; + + if (!xb_preload(gfp)) + return -ENOMEM; + + ret =3D xb_set_bit(xb, bit); + xb_preload_end(); + + return ret; +} + +bool xb_test_bit(struct xb *xb, unsigned long bit) +{ + unsigned long index =3D bit / IDA_BITMAP_BITS; + const struct radix_tree_root *root =3D &xb->xbrt; + struct ida_bitmap *bitmap =3D radix_tree_lookup(root, index); + + bit %=3D IDA_BITMAP_BITS; + + if (!bitmap) + return false; + if (radix_tree_exception(bitmap)) { + bit +=3D RADIX_TREE_EXCEPTIONAL_SHIFT; + if (bit > BITS_PER_LONG) + return false; + return (unsigned long)bitmap & (1UL << bit); + } + + return test_bit(bit, bitmap->bitmap); +} + +void xb_clear_bit(struct xb *xb, unsigned long bit) +{ + unsigned long index =3D bit / IDA_BITMAP_BITS; + struct radix_tree_root *root =3D &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned long ebit; + + bit %=3D IDA_BITMAP_BITS; + ebit =3D bit + 2; + + bitmap =3D __radix_tree_lookup(root, index, &node, &slot); + if (radix_tree_exception(bitmap)) { + unsigned long tmp =3D (unsigned long)bitmap; + + if (ebit >=3D BITS_PER_LONG) + return; + tmp &=3D ~(1UL << ebit); + if (tmp =3D=3D RADIX_TREE_EXCEPTIONAL_ENTRY) + __radix_tree_delete(root, node, slot); + else + rcu_assign_pointer(*slot, (void *)tmp); + return; + } + + if (!bitmap) + return; + + __clear_bit(bit, bitmap->bitmap); + if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { + kfree(bitmap); + __radix_tree_delete(root, node, slot); + } +} + +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long = end) +{ + struct radix_tree_root *root =3D &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned int nbits; + + for (; start < end; start =3D (start | (IDA_BITMAP_BITS - 1)) + 1) { + unsigned long index =3D start / IDA_BITMAP_BITS; + unsigned long bit =3D start % IDA_BITMAP_BITS; + + bitmap =3D __radix_tree_lookup(root, index, &node, &slot); + if (radix_tree_exception(bitmap)) { + unsigned long ebit =3D bit + 2; + unsigned long tmp =3D (unsigned long)bitmap; + + nbits =3D min(end - start + 1, BITS_PER_LONG - ebit); + + if (ebit >=3D BITS_PER_LONG) + continue; + bitmap_clear(&tmp, ebit, nbits); + if (tmp =3D=3D RADIX_TREE_EXCEPTIONAL_ENTRY) + __radix_tree_delete(root, node, slot); + else + rcu_assign_pointer(*slot, (void *)tmp); + } else if (bitmap) { + nbits =3D min(end - start + 1, IDA_BITMAP_BITS - bit); + + if (nbits !=3D IDA_BITMAP_BITS) + bitmap_clear(bitmap->bitmap, bit, nbits); + + if (nbits =3D=3D IDA_BITMAP_BITS || + bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { + kfree(bitmap); + __radix_tree_delete(root, node, slot); + } + } + } +} + +static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, + unsigned long end, bool set) +{ + struct radix_tree_root *root =3D &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bmap; + unsigned long ret =3D end + 1; + + for (; start < end; start =3D (start | (IDA_BITMAP_BITS - 1)) + 1) { + unsigned long index =3D start / IDA_BITMAP_BITS; + unsigned long bit =3D start % IDA_BITMAP_BITS; + + bmap =3D __radix_tree_lookup(root, index, &node, &slot); + if (radix_tree_exception(bmap)) { + unsigned long tmp =3D (unsigned long)bmap; + unsigned long ebit =3D bit + 2; + + if (ebit >=3D BITS_PER_LONG) + continue; + if (set) + ret =3D find_next_bit(&tmp, BITS_PER_LONG, ebit); + else + ret =3D find_next_zero_bit(&tmp, BITS_PER_LONG, + ebit); + if (ret < BITS_PER_LONG) + return ret - 2 + IDA_BITMAP_BITS * index; + } else if (bmap) { + if (set) + ret =3D find_next_bit(bmap->bitmap, + IDA_BITMAP_BITS, bit); + else + ret =3D find_next_zero_bit(bmap->bitmap, + IDA_BITMAP_BITS, bit); + if (ret < IDA_BITMAP_BITS) + return ret + index * IDA_BITMAP_BITS; + } else if (!bmap && !set) { + return start; + } + } + + return ret; +} + +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, + unsigned long end) +{ + return xb_find_next_bit(xb, start, end, 1); +} + +unsigned long xb_find_next_zero_bit(struct xb *xb, unsigned long start, + unsigned long end) +{ + return xb_find_next_bit(xb, start, end, 0); +} + +static void xbitmap_check_bit(unsigned long bit) +{ + assert(!xb_test_bit(&xb1, bit)); + assert(!xb_preload_and_set_bit(&xb1, bit, GFP_KERNEL)); + assert(xb_test_bit(&xb1, bit)); + xb_clear_bit(&xb1, bit); + assert(xb_is_empty(&xb1)); +} + +static void xbitmap_check_bit_range(void) +{ + xb_preload(GFP_KERNEL); + + /* Set a range of bits */ + assert(!xb_set_bit(&xb1, 1060)); + assert(!xb_set_bit(&xb1, 1061)); + assert(!xb_set_bit(&xb1, 1064)); + assert(!xb_set_bit(&xb1, 1065)); + assert(!xb_set_bit(&xb1, 8180)); + assert(!xb_set_bit(&xb1, 8181)); + assert(!xb_set_bit(&xb1, 8190)); + assert(!xb_set_bit(&xb1, 8191)); + + /* Test a range of bits */ + assert(xb_find_next_set_bit(&xb1, 0, 10000) =3D=3D 1060); + assert(xb_find_next_zero_bit(&xb1, 1061, 10000) =3D=3D 1062); + assert(xb_find_next_set_bit(&xb1, 1062, 10000) =3D=3D 1064); + assert(xb_find_next_zero_bit(&xb1, 1065, 10000) =3D=3D 1066); + assert(xb_find_next_set_bit(&xb1, 1066, 10000) =3D=3D 8180); + assert(xb_find_next_zero_bit(&xb1, 8180, 10000) =3D=3D 8182); + xb_clear_bit_range(&xb1, 0, 1000000); + assert(xb_find_next_set_bit(&xb1, 0, 10000) =3D=3D 10001); + + assert(xb_find_next_zero_bit(&xb1, 20000, 30000) =3D=3D 20000); + + xb_preload_end(); +} + +void xbitmap_checks(void) +{ + xb_init(&xb1); + + xbitmap_check_bit(0); + xbitmap_check_bit(30); + xbitmap_check_bit(31); + xbitmap_check_bit(1023); + xbitmap_check_bit(1024); + xbitmap_check_bit(1025); + xbitmap_check_bit((1UL << 63) | (1UL << 24)); + xbitmap_check_bit((1UL << 63) | (1UL << 24) | 70); + + xbitmap_check_bit_range(); +} --=20 2.7.4