From patchwork Thu Dec 21 02:30:06 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: 10126919 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 03C7460245 for ; Thu, 21 Dec 2017 02:47:33 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E1E4029917 for ; Thu, 21 Dec 2017 02:47:32 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D62692992C; Thu, 21 Dec 2017 02:47:32 +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 E86F829917 for ; Thu, 21 Dec 2017 02:47:31 +0000 (UTC) Received: from localhost ([::1]:54652 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eRqtO-0000M7-NV for patchwork-qemu-devel@patchwork.kernel.org; Wed, 20 Dec 2017 21:47:30 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:48421) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eRqsl-0008Iz-CO for qemu-devel@nongnu.org; Wed, 20 Dec 2017 21:46:53 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eRqsi-0007SE-4t for qemu-devel@nongnu.org; Wed, 20 Dec 2017 21:46:51 -0500 Received: from mga06.intel.com ([134.134.136.31]:53849) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eRqsh-0007O6-On for qemu-devel@nongnu.org; Wed, 20 Dec 2017 21:46:48 -0500 X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by orsmga104.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 20 Dec 2017 18:46:44 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.45,434,1508828400"; d="scan'208";a="3598723" Received: from devel-ww.sh.intel.com ([10.239.48.110]) by fmsmga002.fm.intel.com with ESMTP; 20 Dec 2017 18:46:42 -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, penguin-kernel@I-love.SAKURA.ne.jp Date: Thu, 21 Dec 2017 10:30:06 +0800 Message-Id: <1513823406-43632-1-git-send-email-wei.w.wang@intel.com> X-Mailer: git-send-email 2.7.4 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 134.134.136.31 Subject: [Qemu-devel] [PATCH v20 3/7 RESEND] 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: , 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 | 6 ++ lib/xbitmap.c | 205 +++++++++++++++++++++++++++++++++++++++++++ tools/include/linux/bitmap.h | 34 +++++++ tools/include/linux/kernel.h | 2 + 4 files changed, 247 insertions(+) v20 RESEND Changes: - fixed the !node path - added the test cases for the !node path - change __builtin_constant_p(start & 7) to __builtin_constant_p(start) diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h index 108f929..ede1029 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -35,6 +35,12 @@ static inline void xb_init(struct xb *xb) int xb_set_bit(struct xb *xb, unsigned long bit); 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); +unsigned long xb_find_zero(struct xb *xb, unsigned long size, + unsigned long offset); static inline bool xb_empty(const struct xb *xb) { diff --git a/lib/xbitmap.c b/lib/xbitmap.c index a1c0abd..1c99586 100644 --- a/lib/xbitmap.c +++ b/lib/xbitmap.c @@ -3,6 +3,16 @@ #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_set, or xb_find_clear to operate on the same ida bitmap. + * - The current implementation of xb_clear_bit_range, xb_find_set and + * xb_find_clear may cause long latency when the bit range to operate + * on is super large (e.g. [0, ULONG_MAX]). + */ + /** * xb_set_bit - set a bit in the xbitmap * @xb: the xbitmap tree used to record the bit @@ -72,6 +82,49 @@ void xb_clear_bit(struct xb *xb, unsigned long bit) EXPORT_SYMBOL(xb_clear_bit); /** + * xb_clear_bit_range - clear a range of bits in the xbitmap + * @start: the start of the bit range, inclusive + * @nbits: number of bits to clear + * + * This function is used to clear a range of bits in the xbitmap. If all the + * bits in the bitmap are 0, the bitmap will be freed. + */ +void xb_clear_bit_range(struct xb *xb, unsigned long start, + unsigned long nbits) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void __rcu **slot; + struct ida_bitmap *bitmap; + unsigned long index = start / IDA_BITMAP_BITS; + unsigned long bit = start % IDA_BITMAP_BITS; + + if (nbits > ULONG_MAX - start) + nbits = ULONG_MAX - start; + + while (nbits) { + unsigned int __nbits = min(nbits, + (unsigned long)IDA_BITMAP_BITS - bit); + + bitmap = __radix_tree_lookup(root, index, &node, &slot); + if (bitmap) { + 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); + } + } + bit = 0; + index++; + nbits -= __nbits; + } +} +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 @@ -94,6 +147,98 @@ bool xb_test_bit(const struct xb *xb, unsigned long bit) } 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 + * + * Returns: the found bit or, @size if no set bit is found. + */ +unsigned long xb_find_set(struct xb *xb, unsigned long size, + unsigned long offset) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + 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 && !bitmap) + return size; + + 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; + } + bit = 0; + index++; + } + + return size; +} +EXPORT_SYMBOL(xb_find_set); + +/** + * xb_find_zero - find the next zero 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 + * + * Returns: the found bit or, @size if no zero bit is found. + */ +unsigned long xb_find_zero(struct xb *xb, unsigned long size, + unsigned long offset) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + 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 (bitmap) { + if (nbits > IDA_BITMAP_BITS) + nbits = IDA_BITMAP_BITS; + + ret = find_next_zero_bit(bitmap->bitmap, nbits, bit); + if (ret != nbits) + return ret + index * IDA_BITMAP_BITS; + } else { + return bit + index * IDA_BITMAP_BITS; + } + bit = 0; + index++; + } + + return size; +} +EXPORT_SYMBOL(xb_find_zero); + #ifndef __KERNEL__ static DEFINE_XB(xb1); @@ -111,6 +256,64 @@ void xbitmap_check_bit(unsigned long bit) xb_preload_end(); } +static void xbitmap_check_bit_range(void) +{ + /* Regular test1: node = NULL */ + xb_preload(GFP_KERNEL); + xb_set_bit(&xb1, 700); + xb_preload_end(); + assert(xb_find_set(&xb1, ULONG_MAX, 0) == 700); + assert(xb_find_set(&xb1, ULONG_MAX, 800) == ULONG_MAX); + xb_clear_bit_range(&xb1, 0, 1024); + + /* + * Regular test 2 + * set bit 2000, 2001, 2040 + * Next 1 in [0, 2048) --> 2000 + * Next 1 in [2000, 2002) --> 2000 + * Next 1 in [2002, 2041) --> 2040 + * Next 1 in [2002, 2040) --> none + * Next 0 in [2000, 2048) --> 2002 + * Next 0 in [2048, 2060) --> 2048 + */ + xb_preload(GFP_KERNEL); + 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); + 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); + xb_preload_end(); + + /* + * Overflow tests: + * Set bit 1 and ULONG_MAX - 4 + * Next 1 in [ULONG_MAX - 4, ULONG_MAX) --> ULONG_MAX - 4 + * Next 1 [ULONG_MAX - 3, ULONG_MAX + 4) --> none + * Next 0 [ULONG_MAX - 4, ULONG_MAX + 4) --> none + */ + xb_preload(GFP_KERNEL); + assert(!xb_set_bit(&xb1, 1)); + 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); + 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); + xb_clear_bit_range(&xb1, 0, 2); + assert(xb_find_set(&xb1, 2, 0) == 2); + xb_preload_end(); +} + void xbitmap_checks(void) { xb_init(&xb1); @@ -122,6 +325,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..6b559ee 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) && IS_ALIGNED(start, 8) && + __builtin_constant_p(nbits) && 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)