From patchwork Sun Dec 3 01:44:29 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tetsuo Handa X-Patchwork-Id: 10089093 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 7B4D46020A for ; Sun, 3 Dec 2017 01:48:23 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6B34D29101 for ; Sun, 3 Dec 2017 01:48:23 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 5F1C629111; Sun, 3 Dec 2017 01:48:23 +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.9 required=2.0 tests=BAYES_00,RCVD_IN_DNSWL_HI 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 D1C3029101 for ; Sun, 3 Dec 2017 01:48:22 +0000 (UTC) Received: from localhost ([::1]:37519 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eLJOH-0006Uv-JX for patchwork-qemu-devel@patchwork.kernel.org; Sat, 02 Dec 2017 20:48:21 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:54948) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eLJNZ-0005oT-Pk for qemu-devel@nongnu.org; Sat, 02 Dec 2017 20:47:39 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eLJNW-0003el-GF for qemu-devel@nongnu.org; Sat, 02 Dec 2017 20:47:37 -0500 Received: from www262.sakura.ne.jp ([2001:e42:101:1:202:181:97:72]:40077) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eLJNV-0002h7-RF for qemu-devel@nongnu.org; Sat, 02 Dec 2017 20:47:34 -0500 Received: from fsav303.sakura.ne.jp (fsav303.sakura.ne.jp [153.120.85.134]) by www262.sakura.ne.jp (8.14.5/8.14.5) with ESMTP id vB31iW42035756; Sun, 3 Dec 2017 10:44:33 +0900 (JST) (envelope-from penguin-kernel@I-love.SAKURA.ne.jp) Received: from www262.sakura.ne.jp (202.181.97.72) by fsav303.sakura.ne.jp (F-Secure/fsigk_smtp/530/fsav303.sakura.ne.jp); Sun, 03 Dec 2017 10:44:32 +0900 (JST) X-Virus-Status: clean(F-Secure/fsigk_smtp/530/fsav303.sakura.ne.jp) Received: from AQUA (softbank126072090071.bbtec.net [126.72.90.71]) (authenticated bits=0) by www262.sakura.ne.jp (8.14.5/8.14.5) with ESMTP id vB31iWEs035752; Sun, 3 Dec 2017 10:44:32 +0900 (JST) (envelope-from penguin-kernel@I-love.SAKURA.ne.jp) To: willy@infradead.org From: Tetsuo Handa References: <1511963726-34070-1-git-send-email-wei.w.wang@intel.com> <1511963726-34070-6-git-send-email-wei.w.wang@intel.com> <201711301934.CDC21800.FSLtJFFOOVQHMO@I-love.SAKURA.ne.jp> <201711302235.FAJ57385.OFJHOVQOFtMSFL@I-love.SAKURA.ne.jp> <20171130143952.GB12684@bombadil.infradead.org> In-Reply-To: <20171130143952.GB12684@bombadil.infradead.org> Message-Id: <201712031044.AJJ00592.VHOStQLMOFJFFO@I-love.SAKURA.ne.jp> X-Mailer: Winbiff [Version 2.51 PL2] X-Accept-Language: ja,en,zh Date: Sun, 3 Dec 2017 10:44:29 +0900 Mime-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2001:e42:101:1:202:181:97:72 Subject: Re: [Qemu-devel] [PATCH v18 05/10] xbitmap: add more operations 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, 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, wei.w.wang@intel.com, quan.xu@aliyun.com, nilal@redhat.com, cornelia.huck@de.ibm.com, mhocko@kernel.org, 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 Matthew Wilcox wrote: > On Thu, Nov 30, 2017 at 10:35:03PM +0900, Tetsuo Handa wrote: > > According to xb_set_bit(), it seems to me that we are trying to avoid memory allocation > > for "struct ida_bitmap" when all set bits within a 1024-bits bitmap reside in the first > > 61 bits. > > > > But does such saving help? Is there characteristic bias that majority of set bits resides > > in the first 61 bits, for "bit" is "unsigned long" which holds a page number (isn't it)? > > If no such bias, wouldn't eliminating radix_tree_exception() case and always storing > > "struct ida_bitmap" simplifies the code (and make the processing faster)? > > It happens all the time. The vast majority of users of the IDA set > low bits. Also, it's the first 62 bits -- going up to 63 bits with the > XArray rewrite. Oops, 0...61 is 62 bits. What I meant is below (untested) patch. If correct, it can save lines and make the code easier to read. lib/radix-tree.c | 20 +------------ lib/xbitmap.c | 88 +++++--------------------------------------------------- 2 files changed, 8 insertions(+), 100 deletions(-) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index a039588..fb84b91 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -2152,25 +2152,7 @@ int ida_pre_get(struct ida *ida, gfp_t gfp) */ __must_check bool xb_preload(gfp_t gfp) { - if (!this_cpu_read(ida_bitmap)) { - struct ida_bitmap *bitmap = kmalloc(sizeof(*bitmap), gfp); - - if (!bitmap) - return false; - /* - * The per-CPU variable is updated with preemption enabled. - * If the calling task is unlucky to be scheduled to another - * CPU which has no ida_bitmap allocation, it will be detected - * when setting a bit (i.e. __xb_set_bit()). - */ - bitmap = this_cpu_cmpxchg(ida_bitmap, NULL, bitmap); - kfree(bitmap); - } - - if (__radix_tree_preload(gfp, XB_PRELOAD_SIZE) < 0) - return false; - - return true; + return __radix_tree_preload(gfp, XB_PRELOAD_SIZE) == 0; } EXPORT_SYMBOL(xb_preload); diff --git a/lib/xbitmap.c b/lib/xbitmap.c index 816dd3e..426d168 100644 --- a/lib/xbitmap.c +++ b/lib/xbitmap.c @@ -18,7 +18,7 @@ * This function is used to set a bit in the xbitmap. If the bitmap that @bit * resides in is not there, the per-cpu ida_bitmap will be taken. * - * Returns: 0 on success. %-EAGAIN indicates that @bit was not set. + * Returns: 0 on success. Negative value on failure. */ int xb_set_bit(struct xb *xb, unsigned long bit) { @@ -28,46 +28,19 @@ int xb_set_bit(struct xb *xb, unsigned long bit) struct radix_tree_node *node; void **slot; struct ida_bitmap *bitmap; - unsigned long ebit; bit %= IDA_BITMAP_BITS; - ebit = bit + 2; err = __radix_tree_create(root, index, 0, &node, &slot); if (err) return err; bitmap = rcu_dereference_raw(*slot); - if (radix_tree_exception(bitmap)) { - unsigned long tmp = (unsigned long)bitmap; - - if (ebit < BITS_PER_LONG) { - tmp |= 1UL << ebit; - rcu_assign_pointer(*slot, (void *)tmp); - return 0; - } - bitmap = this_cpu_xchg(ida_bitmap, NULL); - if (!bitmap) { - __radix_tree_delete(root, node, slot); - return -EAGAIN; - } - memset(bitmap, 0, sizeof(*bitmap)); - bitmap->bitmap[0] = tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT; - rcu_assign_pointer(*slot, bitmap); - } - if (!bitmap) { - if (ebit < BITS_PER_LONG) { - bitmap = (void *)((1UL << ebit) | - RADIX_TREE_EXCEPTIONAL_ENTRY); - __radix_tree_replace(root, node, slot, bitmap, NULL); - return 0; - } - bitmap = this_cpu_xchg(ida_bitmap, NULL); + bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT | __GFP_NOWARN); if (!bitmap) { __radix_tree_delete(root, node, slot); - return -EAGAIN; + return -ENOMEM; } - memset(bitmap, 0, sizeof(*bitmap)); __radix_tree_replace(root, node, slot, bitmap, NULL); } @@ -82,7 +55,7 @@ int xb_set_bit(struct xb *xb, unsigned long bit) * @bit: index of the bit to set * * A wrapper of the xb_preload() and xb_set_bit(). - * Returns: 0 on success; -EAGAIN or -ENOMEM on error. + * Returns: 0 on success; -ENOMEM on error. */ int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp) { @@ -113,25 +86,10 @@ void xb_clear_bit(struct xb *xb, unsigned long bit) struct radix_tree_node *node; void **slot; struct ida_bitmap *bitmap; - unsigned long ebit; bit %= IDA_BITMAP_BITS; - ebit = bit + 2; bitmap = __radix_tree_lookup(root, index, &node, &slot); - if (radix_tree_exception(bitmap)) { - unsigned long tmp = (unsigned long)bitmap; - - if (ebit >= BITS_PER_LONG) - return; - tmp &= ~(1UL << ebit); - if (tmp == RADIX_TREE_EXCEPTIONAL_ENTRY) - __radix_tree_delete(root, node, slot); - else - rcu_assign_pointer(*slot, (void *)tmp); - return; - } - if (!bitmap) return; @@ -164,20 +122,7 @@ void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) unsigned long bit = start % IDA_BITMAP_BITS; bitmap = __radix_tree_lookup(root, index, &node, &slot); - if (radix_tree_exception(bitmap)) { - unsigned long ebit = bit + 2; - unsigned long tmp = (unsigned long)bitmap; - - nbits = min(end - start + 1, BITS_PER_LONG - ebit); - - if (ebit >= BITS_PER_LONG) - continue; - bitmap_clear(&tmp, ebit, nbits); - if (tmp == RADIX_TREE_EXCEPTIONAL_ENTRY) - __radix_tree_delete(root, node, slot); - else - rcu_assign_pointer(*slot, (void *)tmp); - } else if (bitmap) { + if (bitmap) { nbits = min(end - start + 1, IDA_BITMAP_BITS - bit); if (nbits != IDA_BITMAP_BITS) @@ -212,12 +157,6 @@ bool xb_test_bit(const struct xb *xb, unsigned long bit) if (!bitmap) return false; - if (radix_tree_exception(bitmap)) { - bit += RADIX_TREE_EXCEPTIONAL_SHIFT; - if (bit >= BITS_PER_LONG) - return false; - return (unsigned long)bitmap & (1UL << bit); - } return test_bit(bit, bitmap->bitmap); } EXPORT_SYMBOL(xb_test_bit); @@ -236,20 +175,7 @@ static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, unsigned long bit = start % IDA_BITMAP_BITS; bmap = __radix_tree_lookup(root, index, &node, &slot); - if (radix_tree_exception(bmap)) { - unsigned long tmp = (unsigned long)bmap; - unsigned long ebit = bit + 2; - - if (ebit >= BITS_PER_LONG) - continue; - if (set) - ret = find_next_bit(&tmp, BITS_PER_LONG, ebit); - else - ret = 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 (bmap) { if (set) ret = find_next_bit(bmap->bitmap, IDA_BITMAP_BITS, bit); @@ -258,7 +184,7 @@ static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, IDA_BITMAP_BITS, bit); if (ret < IDA_BITMAP_BITS) return ret + index * IDA_BITMAP_BITS; - } else if (!bmap && !set) { + } else if (!set) { return start; } }