From patchwork Wed Nov 29 13:55:21 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Wang, Wei W" X-Patchwork-Id: 10082313 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 71B8F6056F for ; Wed, 29 Nov 2017 14:12:58 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6D352298EC for ; Wed, 29 Nov 2017 14:12:58 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 61E76298EE; Wed, 29 Nov 2017 14:12:58 +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 8A2C7298EC for ; Wed, 29 Nov 2017 14:12:57 +0000 (UTC) Received: from localhost ([::1]:43271 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eK36e-0001pW-EG for patchwork-qemu-devel@patchwork.kernel.org; Wed, 29 Nov 2017 09:12:56 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:58961) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eK35J-0001mJ-Fi for qemu-devel@nongnu.org; Wed, 29 Nov 2017 09:11:35 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eK35H-0004Cz-R3 for qemu-devel@nongnu.org; Wed, 29 Nov 2017 09:11:33 -0500 Received: from mga01.intel.com ([192.55.52.88]:52215) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eK35H-0003cm-Df for qemu-devel@nongnu.org; Wed, 29 Nov 2017 09:11:31 -0500 Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 29 Nov 2017 06:11:31 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.44,473,1505804400"; d="scan'208";a="7221778" Received: from devel-ww.sh.intel.com ([10.239.48.110]) by FMSMGA003.fm.intel.com with ESMTP; 29 Nov 2017 06:11:27 -0800 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: Wed, 29 Nov 2017 21:55:21 +0800 Message-Id: <1511963726-34070-6-git-send-email-wei.w.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1511963726-34070-1-git-send-email-wei.w.wang@intel.com> References: <1511963726-34070-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.88 Subject: [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: 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, nilal@redhat.com, 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 This patch adds support to find next 1 or 0 bit in a xbmitmap range and clear a range of bits. More possible optimizations to add in the future: 1) xb_set_bit_range: set a range of bits. 2) when searching a bit, if the bit is not found in the slot, move on to the next slot directly. 3) add tags to help searching. Signed-off-by: Wei Wang Cc: Matthew Wilcox Cc: Andrew Morton Cc: Michal Hocko Cc: Michael S. Tsirkin Cc: Tetsuo Handa Suggested-by: Matthew Wilcox --- include/linux/xbitmap.h | 8 +- lib/xbitmap.c | 180 +++++++++++++++++++++++++++++++++++++++++++ tools/include/linux/bitmap.h | 34 ++++++++ tools/include/linux/kernel.h | 2 + 4 files changed, 223 insertions(+), 1 deletion(-) diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h index b4d8375..eddf0d5e 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -33,8 +33,14 @@ static inline void xb_init(struct xb *xb) } int xb_set_bit(struct xb *xb, unsigned long bit); +int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp); bool xb_test_bit(const struct xb *xb, unsigned long bit); -int xb_clear_bit(struct xb *xb, unsigned long bit); +void xb_clear_bit(struct xb *xb, unsigned long bit); +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, + unsigned long end); +unsigned long xb_find_next_zero_bit(struct xb *xb, unsigned long start, + unsigned long end); +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end); static inline bool xb_empty(const struct xb *xb) { diff --git a/lib/xbitmap.c b/lib/xbitmap.c index 182aa29..816dd3e 100644 --- a/lib/xbitmap.c +++ b/lib/xbitmap.c @@ -3,6 +3,13 @@ #include #include +/* + * Developer notes: locks are required to gurantee there is no concurrent + * calls of xb_set_bit, xb_clear_bit, xb_clear_bit_range, xb_test_bit, + * xb_find_next_set_bit, or xb_find_next_clear_bit to operate on the same + * ida bitamp. + */ + /** * xb_set_bit - set a bit in the xbitmap * @xb: the xbitmap tree used to record the bit @@ -70,6 +77,28 @@ int xb_set_bit(struct xb *xb, unsigned long bit) EXPORT_SYMBOL(xb_set_bit); /** + * xb_preload_and_set_bit - preload the memory and set a bit in the xbitmap + * @xb: the xbitmap tree used to record the 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. + */ +int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp) +{ + int ret = 0; + + if (!xb_preload(gfp)) + return -ENOMEM; + + ret = xb_set_bit(xb, bit); + xb_preload_end(); + + return ret; +} +EXPORT_SYMBOL(xb_preload_and_set_bit); + +/** * xb_clear_bit - clear a bit in the xbitmap * @xb: the xbitmap tree used to record the bit * @bit: index of the bit to clear @@ -115,6 +144,56 @@ void xb_clear_bit(struct xb *xb, unsigned long bit) EXPORT_SYMBOL(xb_clear_bit); /** + * xb_clear_bit - clear a range of bits in the xbitmap + * @start: the start of the bit range, inclusive + * @end: the end of the bit range, inclusive + * + * This function is used to clear a bit in the xbitmap. If all the bits of the + * bitmap are 0, the bitmap will be freed. + */ +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned int nbits; + + for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { + unsigned long index = start / IDA_BITMAP_BITS; + 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) { + nbits = min(end - start + 1, IDA_BITMAP_BITS - bit); + + if (nbits != IDA_BITMAP_BITS) + bitmap_clear(bitmap->bitmap, bit, nbits); + + if (nbits == IDA_BITMAP_BITS || + bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { + kfree(bitmap); + __radix_tree_delete(root, node, slot); + } + } + } +} +EXPORT_SYMBOL(xb_clear_bit_range); + +/** * xb_test_bit - test a bit in the xbitmap * @xb: the xbitmap tree used to record the bit * @bit: index of the bit to test @@ -143,6 +222,80 @@ bool xb_test_bit(const struct xb *xb, unsigned long bit) } EXPORT_SYMBOL(xb_test_bit); +static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, + unsigned long end, bool set) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bmap; + unsigned long ret = end + 1; + + for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { + unsigned long index = start / IDA_BITMAP_BITS; + 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 (set) + ret = find_next_bit(bmap->bitmap, + IDA_BITMAP_BITS, bit); + else + ret = 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; +} + +/** + * xb_find_next_set_bit - find the next set bit in a range + * @xb: the xbitmap to search + * @start: the start of the range, inclusive + * @end: the end of the range, inclusive + * + * Returns: the index of the found bit, or @end + 1 if no such bit is found. + */ +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); +} +EXPORT_SYMBOL(xb_find_next_set_bit); + +/** + * xb_find_next_zero_bit - find the next zero bit in a range + * @xb: the xbitmap to search + * @start: the start of the range, inclusive + * @end: the end of the range, inclusive + * + * Returns: the index of the found bit, or @end + 1 if no such bit is found. + */ +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); +} +EXPORT_SYMBOL(xb_find_next_zero_bit); + #ifndef __KERNEL__ static DEFINE_XB(xb1); @@ -160,6 +313,31 @@ void xbitmap_check_bit(unsigned long bit) xb_preload_end(); } +static void xbitmap_check_bit_range(void) +{ + /* Set a range of bits */ + assert(!xb_preload_and_set_bit(&xb1, 1060, GFP_KERNEL)); + assert(!xb_preload_and_set_bit(&xb1, 1061, GFP_KERNEL)); + assert(!xb_preload_and_set_bit(&xb1, 1064, GFP_KERNEL)); + assert(!xb_preload_and_set_bit(&xb1, 1065, GFP_KERNEL)); + assert(!xb_preload_and_set_bit(&xb1, 8180, GFP_KERNEL)); + assert(!xb_preload_and_set_bit(&xb1, 8181, GFP_KERNEL)); + assert(!xb_preload_and_set_bit(&xb1, 8190, GFP_KERNEL)); + assert(!xb_preload_and_set_bit(&xb1, 8191, GFP_KERNEL)); + + /* Test a range of bits */ + assert(xb_find_next_set_bit(&xb1, 0, 10000) == 1060); + assert(xb_find_next_zero_bit(&xb1, 1061, 10000) == 1062); + assert(xb_find_next_set_bit(&xb1, 1062, 10000) == 1064); + assert(xb_find_next_zero_bit(&xb1, 1065, 10000) == 1066); + assert(xb_find_next_set_bit(&xb1, 1066, 10000) == 8180); + assert(xb_find_next_zero_bit(&xb1, 8180, 10000) == 8182); + xb_clear_bit_range(&xb1, 0, 20000); + assert(xb_find_next_set_bit(&xb1, 0, 10000) == 10001); + + assert(xb_find_next_zero_bit(&xb1, 20000, 30000) == 20000); +} + void xbitmap_checks(void) { xb_init(&xb1); @@ -171,6 +349,8 @@ void xbitmap_checks(void) xbitmap_check_bit(1025); xbitmap_check_bit((1UL << 63) | (1UL << 24)); xbitmap_check_bit((1UL << 63) | (1UL << 24) | 70); + + xbitmap_check_bit_range(); } int __weak main(void) diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h index ca16027..8d0bc1b 100644 --- a/tools/include/linux/bitmap.h +++ b/tools/include/linux/bitmap.h @@ -37,6 +37,40 @@ static inline void bitmap_zero(unsigned long *dst, int nbits) } } +static inline void __bitmap_clear(unsigned long *map, unsigned int start, + int len) +{ + unsigned long *p = map + BIT_WORD(start); + const unsigned int size = start + len; + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); + + while (len - bits_to_clear >= 0) { + *p &= ~mask_to_clear; + len -= bits_to_clear; + bits_to_clear = BITS_PER_LONG; + mask_to_clear = ~0UL; + p++; + } + if (len) { + mask_to_clear &= BITMAP_LAST_WORD_MASK(size); + *p &= ~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 == 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 = BITS_TO_LONGS(nbits); diff --git a/tools/include/linux/kernel.h b/tools/include/linux/kernel.h index 0ad8844..3c992ae 100644 --- a/tools/include/linux/kernel.h +++ b/tools/include/linux/kernel.h @@ -13,6 +13,8 @@ #define UINT_MAX (~0U) #endif +#define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0) + #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) #define PERF_ALIGN(x, a) __PERF_ALIGN_MASK(x, (typeof(x))(a)-1)