From patchwork Wed Dec 20 17:10:19 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10125955 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 6F26260388 for ; Wed, 20 Dec 2017 17:11:22 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 55F902977C for ; Wed, 20 Dec 2017 17:11:22 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 54599297B8; Wed, 20 Dec 2017 17:11:22 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=unavailable version=3.3.1 Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 850142979F for ; Wed, 20 Dec 2017 17:11:21 +0000 (UTC) Received: from localhost ([::1]:60122 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eRhto-0002kQ-4r for patchwork-qemu-devel@patchwork.kernel.org; Wed, 20 Dec 2017 12:11:20 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:54102) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eRhtC-0002PB-Lp for qemu-devel@nongnu.org; Wed, 20 Dec 2017 12:10:44 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eRht8-00031w-T8 for qemu-devel@nongnu.org; Wed, 20 Dec 2017 12:10:42 -0500 Received: from bombadil.infradead.org ([65.50.211.133]:45339) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eRht8-0002tM-8W for qemu-devel@nongnu.org; Wed, 20 Dec 2017 12:10:38 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=In-Reply-To:Content-Type:MIME-Version :References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=/c0jc+L6oj+n6CZyNMNmo22iw8jdxLJg5+k91XlhiuA=; b=aaxo1rqmK8GlPctkgWwRJv8Gd FqWWV9tHOLtzqPMv9jPsRJbLnPEfHbTRBYrdT+WDkaC4jTmiwCnxNQcNdZMlTGk9n4OYlo7MWV9Qy +CDbDrZlKE9Pmf4s077LPTSAcfXDHVKslYu0qmapb9xvmc6ZbrBB60NkbhM1KoyOATyJsFrMVLPlq CK/YsiFtFMkDQxqdJWXZm2PA1xTAzlvC9H26z4WBLtT/s4T+RA67Tt95osk7m8dfAnLdA/N5b9CQQ ugh10cn3GSmjU1ODC8KPOtWyh8mQ643cQk4MS9DSYkerY5JL9p3Qr7CxxUqLX6eFagYFLsDtSUFD4 8pbgmqL1Q==; Received: from willy by bombadil.infradead.org with local (Exim 4.89 #1 (Red Hat Linux)) id 1eRhsp-0004sH-Oe; Wed, 20 Dec 2017 17:10:19 +0000 Date: Wed, 20 Dec 2017 09:10:19 -0800 From: Matthew Wilcox To: "Wang, Wei W" Message-ID: <20171220171019.GA12236@bombadil.infradead.org> References: <1513685879-21823-1-git-send-email-wei.w.wang@intel.com> <201712192305.AAE21882.MtQHJOFFSFVOLO@I-love.SAKURA.ne.jp> <5A3A3CBC.4030202@intel.com> <20171220122547.GA1654@bombadil.infradead.org> <286AC319A985734F985F78AFA26841F73938CC3E@shsmsx102.ccr.corp.intel.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <286AC319A985734F985F78AFA26841F73938CC3E@shsmsx102.ccr.corp.intel.com> User-Agent: Mutt/1.9.1 (2017-09-22) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 65.50.211.133 Subject: Re: [Qemu-devel] [PATCH v20 0/7] Virtio-balloon Enhancement 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: "yang.zhang.wz@gmail.com" , "kvm@vger.kernel.org" , "mst@redhat.com" , Tetsuo Handa , "liliang.opensource@gmail.com" , "qemu-devel@nongnu.org" , "virtualization@lists.linux-foundation.org" , "linux-mm@kvack.org" , "aarcange@redhat.com" , "virtio-dev@lists.oasis-open.org" , "mawilcox@microsoft.com" , "david@redhat.com" , "nilal@redhat.com" , "cornelia.huck@de.ibm.com" , "mhocko@kernel.org" , "quan.xu0@gmail.com" , "linux-kernel@vger.kernel.org" , "amit.shah@redhat.com" , "pbonzini@redhat.com" , "akpm@linux-foundation.org" , "mgorman@techsingularity.net" Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" X-Virus-Scanned: ClamAV using ClamSMTP On Wed, Dec 20, 2017 at 04:13:16PM +0000, Wang, Wei W wrote: > On Wednesday, December 20, 2017 8:26 PM, Matthew Wilcox wrote: > > unsigned long bit; > > xb_preload(GFP_KERNEL); > > xb_set_bit(xb, 700); > > xb_preload_end(); > > bit = xb_find_set(xb, ULONG_MAX, 0); > > assert(bit == 700); > > This above test will result in "!node with bitmap !=NULL", and it goes to the regular "if (bitmap)" path, which finds 700. > > A better test would be > ... > xb_set_bit(xb, 700); > assert(xb_find_set(xb, ULONG_MAX, 800) == ULONG_MAX); > ... I decided to write a test case to show you what I meant, then I discovered the test suite didn't build, then the test I wrote took forever to run, so I rewrote xb_find_set() using the radix tree iterators. So I have no idea what bugs may be in your implementation, but at least this function passes the current test suite. Of course, there may be gaps in the test suite. And since I changed the API to not have the ambiguous return value, I also changed the test suite, and maybe I introduced a bug. diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h index ede1029b8a27..96e7e3560a0e 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -37,8 +37,7 @@ bool xb_test_bit(const struct xb *xb, unsigned long bit); void xb_clear_bit(struct xb *xb, unsigned long bit); void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long nbits); -unsigned long xb_find_set(struct xb *xb, unsigned long size, - unsigned long offset); +bool xb_find_set(struct xb *xb, unsigned long max, unsigned long *bit); unsigned long xb_find_zero(struct xb *xb, unsigned long size, unsigned long offset); diff --git a/lib/xbitmap.c b/lib/xbitmap.c index 0bd3027b082d..58c26c8dd595 100644 --- a/lib/xbitmap.c +++ b/lib/xbitmap.c @@ -150,48 +150,39 @@ EXPORT_SYMBOL(xb_test_bit); /** * xb_find_set - find the next set bit in a range of bits * @xb: the xbitmap to search from - * @offset: the offset in the range to start searching - * @size: the size of the range + * @max: the maximum position to search to + * @bit: the first bit to examine, and on exit, the found bit * - * Returns: the found bit or, @size if no set bit is found. + * Returns: %true if a set bit was found. @bit will be updated. */ -unsigned long xb_find_set(struct xb *xb, unsigned long size, - unsigned long offset) +bool xb_find_set(struct xb *xb, unsigned long max, unsigned long *bit) { - struct radix_tree_root *root = &xb->xbrt; - struct radix_tree_node *node; + struct radix_tree_iter iter; void __rcu **slot; struct ida_bitmap *bitmap; - unsigned long index = offset / IDA_BITMAP_BITS; - unsigned long index_end = size / IDA_BITMAP_BITS; - unsigned long bit = offset % IDA_BITMAP_BITS; - - if (unlikely(offset >= size)) - return size; - - while (index <= index_end) { - unsigned long ret; - unsigned int nbits = size - index * IDA_BITMAP_BITS; - - bitmap = __radix_tree_lookup(root, index, &node, &slot); - if (!node) { - index = (index | RADIX_TREE_MAP_MASK) + 1; - continue; - } - + unsigned long index = *bit / IDA_BITMAP_BITS; + unsigned int first = *bit % IDA_BITMAP_BITS; + unsigned long index_end = max / IDA_BITMAP_BITS; + + radix_tree_for_each_slot(slot, &xb->xbrt, &iter, index) { + if (iter.index > index_end) + break; + bitmap = radix_tree_deref_slot(slot); if (bitmap) { - if (nbits > IDA_BITMAP_BITS) - nbits = IDA_BITMAP_BITS; - - ret = find_next_bit(bitmap->bitmap, nbits, bit); - if (ret != nbits) - return ret + index * IDA_BITMAP_BITS; + unsigned int nbits = IDA_BITMAP_BITS; + if (iter.index == index_end) + nbits = max % IDA_BITMAP_BITS + 1; + + first = find_next_bit(bitmap->bitmap, nbits, first); + if (first != nbits) { + *bit = first + iter.index * IDA_BITMAP_BITS; + return true; + } } - bit = 0; - index++; + first = 0; } - return size; + return false; } EXPORT_SYMBOL(xb_find_set); @@ -246,19 +237,30 @@ static DEFINE_XB(xb1); void xbitmap_check_bit(unsigned long bit) { + unsigned long nbit = 0; + xb_preload(GFP_KERNEL); assert(!xb_test_bit(&xb1, bit)); assert(xb_set_bit(&xb1, bit) == 0); assert(xb_test_bit(&xb1, bit)); - assert(xb_clear_bit(&xb1, bit) == 0); + assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == true); + assert(nbit == bit); + assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == true); + assert(nbit == bit); + nbit++; + assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == false); + assert(nbit == bit + 1); + xb_clear_bit(&xb1, bit); assert(xb_empty(&xb1)); - assert(xb_clear_bit(&xb1, bit) == 0); + xb_clear_bit(&xb1, bit); assert(xb_empty(&xb1)); xb_preload_end(); } static void xbitmap_check_bit_range(void) { + unsigned long nbit; + /* * Regular tests * set bit 2000, 2001, 2040 @@ -273,14 +275,23 @@ static void xbitmap_check_bit_range(void) assert(!xb_set_bit(&xb1, 2000)); assert(!xb_set_bit(&xb1, 2001)); assert(!xb_set_bit(&xb1, 2040)); - assert(xb_find_set(&xb1, 2048, 0) == 2000); - assert(xb_find_set(&xb1, 2002, 2000) == 2000); - assert(xb_find_set(&xb1, 2041, 2002) == 2040); - assert(xb_find_set(&xb1, 2040, 2002) == 2040); + nbit = 0; + assert(xb_find_set(&xb1, 2048, &nbit) == true); + assert(nbit == 2000); + assert(xb_find_set(&xb1, 2002, &nbit) == true); + assert(nbit == 2000); + nbit = 2002; + assert(xb_find_set(&xb1, 2041, &nbit) == true); + assert(nbit == 2040); + nbit = 2002; + assert(xb_find_set(&xb1, 2040, &nbit) == true); + assert(nbit == 2040); assert(xb_find_zero(&xb1, 2048, 2000) == 2002); assert(xb_find_zero(&xb1, 2060, 2048) == 2048); xb_clear_bit_range(&xb1, 0, 2048); - assert(xb_find_set(&xb1, 2048, 0) == 2048); + nbit = 0; + assert(xb_find_set(&xb1, 2048, &nbit) == false); + assert(nbit == 0); xb_preload_end(); /* @@ -295,15 +306,22 @@ static void xbitmap_check_bit_range(void) xb_preload_end(); xb_preload(GFP_KERNEL); assert(!xb_set_bit(&xb1, ULONG_MAX - 4)); - assert(xb_find_set(&xb1, ULONG_MAX, ULONG_MAX - 4) == ULONG_MAX - 4); - assert(xb_find_set(&xb1, ULONG_MAX + 4, ULONG_MAX - 3) == - ULONG_MAX + 4); + nbit = ULONG_MAX - 4; + assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == true); + assert(nbit == ULONG_MAX - 4); + nbit++; + assert(xb_find_set(&xb1, ULONG_MAX + 4, &nbit) == false); + assert(nbit == ULONG_MAX - 3); assert(xb_find_zero(&xb1, ULONG_MAX + 4, ULONG_MAX - 4) == ULONG_MAX + 4); xb_clear_bit_range(&xb1, ULONG_MAX - 4, 4); - assert(xb_find_set(&xb1, ULONG_MAX, ULONG_MAX - 10) == ULONG_MAX); + nbit = ULONG_MAX - 10; + assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == false); + assert(nbit == ULONG_MAX - 10); xb_clear_bit_range(&xb1, 0, 2); - assert(xb_find_set(&xb1, 2, 0) == 2); + nbit = 0; + assert(xb_find_set(&xb1, 2, &nbit) == false); + assert(nbit == 0); xb_preload_end(); } @@ -313,6 +331,10 @@ void xbitmap_checks(void) xbitmap_check_bit(0); xbitmap_check_bit(30); xbitmap_check_bit(31); + xbitmap_check_bit(62); + xbitmap_check_bit(63); + xbitmap_check_bit(64); + xbitmap_check_bit(700); xbitmap_check_bit(1023); xbitmap_check_bit(1024); xbitmap_check_bit(1025); diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 34ece7883629..adf36e34dd77 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -1,9 +1,9 @@ # SPDX-License-Identifier: GPL-2.0 CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -LDFLAGS += -fsanitize=address -LDLIBS+= -lpthread -lurcu -TARGETS = main idr-test multiorder +LDFLAGS += -fsanitize=address $(LDLIBS) +LDLIBS := -lpthread -lurcu +TARGETS = main idr-test multiorder xbitmap CORE_OFILES := radix-tree.o idr.o linux.o test.o find_bit.o OFILES = main.o $(CORE_OFILES) regression1.o regression2.o regression3.o \ tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o \ diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index c3bc3f364f68..426f32f28547 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -17,6 +17,4 @@ #define pr_debug printk #define pr_cont printk -#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) - #endif /* _KERNEL_H */