From patchwork Sat Dec 18 21:20:03 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 12686377 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 99C70C433EF for ; Sat, 18 Dec 2021 21:21:30 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-Id:Date:Subject:To:From:Reply-To:Cc:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=B39q8lDUMT6LqqK1L2PbKzExTymZZvcgAnLTnnjMSSc=; b=MEvmvPwl2ZTDIS supuBG0sZvXtM3/x2ZdF4n3g29waoSK4mStGuSx9RoWKPApJ2fdhDNFlWfiP/KYRhQ38bw8dibAtQ GJtY57HqIW/RgkF/u5X5EC84aB9TIiFnFs1i9VJwoZ+dUoGzYEPvyi5oB54Pwz2x3rHR1zf2zAzdp awY/Qc0DeqA3r0vHpTyUq+6CkQd+eY3JHumllaL+OLlYiN8zhoKfHf1pMsUDaLLWtFvCeYEg6/QE8 9Pj/PQeDKnrqJF5mObuf5VBYqMw6FqHyRRXnpWAiH09CVbhlWjgEtCg3ANIZOSDCH88r+X/RrVXw0 B1jRM0EE0qrbbHBovKLA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1myh8q-00EkH7-11; Sat, 18 Dec 2021 21:21:20 +0000 Received: from mail-oo1-xc2a.google.com ([2607:f8b0:4864:20::c2a]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1myh8C-00Ejj1-Nd; Sat, 18 Dec 2021 21:20:43 +0000 Received: by mail-oo1-xc2a.google.com with SMTP id r18-20020a4a7252000000b002c5f52d1834so1864651ooe.0; Sat, 18 Dec 2021 13:20:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=Y8ExfgOcgrA4CHmSecZvjPn/xavwnyrvtMRh3tqxxrw=; b=ky3nIm4VKfqY0Iq4zNauj3NXFN9QLbU64c4NLKd8+eXyY5UHvMFlx9aiNTA/qwjF5p 5WEcS0LUjqwMpD0Ly9X7LVxbhmiOR2GbQ+abrUk6bHvx7+Cvj1ungkoH5D46b1QyLWQz km2XM/SS0wgiVd0HWTiaIFErZ5cDFzoDijXs35dCpitpd1tSBTdIYvXxDqkzZELiy25H 54tm+5ByXHXPQCWtpde4rVewBv2R910Nw8U1BZzohGqANJ92nhEfKoJ9hVS5V3Wa/96H D15GnwPbjMyWcfB02PLIxfn7tGI1glt4iKIi7P1KZiLFMB3n2s8o4pHZOlsQnok+/jIH ei5Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=Y8ExfgOcgrA4CHmSecZvjPn/xavwnyrvtMRh3tqxxrw=; b=kAf5IA5b3amwX5cWNU2HxeR6RbI7Zh8mOEV3/9fp6mgLJdMQztiIeGaecehsdWgQzS GOygWaEKt5N7EBbwOdaqateoqTv74/G9k9wWgfH9qmLKCVuTl/rRZmj9Q647vOWhLJTE ckNWwn3IBs3KhMU1jFo3ekDYHVP1olovi/RokQNXFcvJimEOo4qd5FZk/Pq4F+sTQIMX UaR07yUiJ6hkU5LRJ9LDAUGOyjGtHsBnjPstglhT4elAYFh+hrBrjfPLPqZrper4wLJK VFrltmbaMmybemtKrtlHJr8lf1U1CdqoxD0Wj+MiZrGsXzP1kwApXZcJ+0FDc5D/Vfus S0fg== X-Gm-Message-State: AOAM5319geHoPiDhIk84A0HAzsP5m3l4M1LCWy1KtDqKgXAclriJGiAI ifGOQIW2dQoMfouE2nkeep4= X-Google-Smtp-Source: ABdhPJxRJAChWm8hZEgKNS5uqGfM1GLlIQqNCNXw8p1t/B+Bt/JWEVwLsC+a2lNQnmWVQu7sh+mn1Q== X-Received: by 2002:a05:6820:820:: with SMTP id bg32mr5869341oob.10.1639862439949; Sat, 18 Dec 2021 13:20:39 -0800 (PST) Received: from localhost (searspoint.nvidia.com. [216.228.112.21]) by smtp.gmail.com with ESMTPSA id r26sm2292099otn.15.2021.12.18.13.20.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 18 Dec 2021 13:20:39 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, Yury Norov , "James E.J. Bottomley" , "Martin K. Petersen" , =?utf-8?b?TWljaGHFgiBN?= =?utf-8?b?aXJvc8WCYXc=?= , "Paul E. McKenney" , "Rafael J. Wysocki" , Alexander Shishkin , Alexey Klimov , Amitkumar Karwar , Andi Kleen , Andrew Lunn , Andrew Morton , Andy Gross , Andy Lutomirski , Andy Shevchenko , Anup Patel , Ard Biesheuvel , Arnaldo Carvalho de Melo , Arnd Bergmann , Borislav Petkov , Catalin Marinas , Christoph Hellwig , Christoph Lameter , Daniel Vetter , Dave Hansen , David Airlie , David Laight , Dennis Zhou , Emil Renner Berthing , Geert Uytterhoeven , Geetha sowjanya , Greg Kroah-Hartman , Guo Ren , Hans de Goede , Heiko Carstens , Ian Rogers , Ingo Molnar , Jakub Kicinski , Jason Wessel , Jens Axboe , Jiri Olsa , Joe Perches , Jonathan Cameron , Juri Lelli , Kees Cook , Krzysztof Kozlowski , Lee Jones , Marc Zyngier , Marcin Wojtas , Mark Gross , Mark Rutland , Matti Vaittinen , Mauro Carvalho Chehab , Mel Gorman , Michael Ellerman , Mike Marciniszyn , Nicholas Piggin , Palmer Dabbelt , Peter Zijlstra , Petr Mladek , Randy Dunlap , Rasmus Villemoes , Russell King , Saeed Mahameed , Sagi Grimberg , Sergey Senozhatsky , Solomon Peachy , Stephen Boyd , Stephen Rothwell , Steven Rostedt , Subbaraya Sundeep , Sudeep Holla , Sunil Goutham , Tariq Toukan , Tejun Heo , Thomas Bogendoerfer , Thomas Gleixner , Ulf Hansson , Vincent Guittot , Vineet Gupta , Viresh Kumar , Vivien Didelot , Vlastimil Babka , Will Deacon , bcm-kernel-feedback-list@broadcom.com, kvm@vger.kernel.org, linux-alpha@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linux-crypto@vger.kernel.org, linux-csky@vger.kernel.org, linux-ia64@vger.kernel.org, linux-mips@vger.kernel.org, linux-mm@kvack.org, linux-perf-users@vger.kernel.org, linux-riscv@lists.infradead.org, linux-s390@vger.kernel.org, linux-snps-arc@lists.infradead.org, linuxppc-dev@lists.ozlabs.org Subject: [PATCH 07/17] lib/bitmap: add bitmap_weight_{cmp, eq, gt, ge, lt, le} functions Date: Sat, 18 Dec 2021 13:20:03 -0800 Message-Id: <20211218212014.1315894-8-yury.norov@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211218212014.1315894-1-yury.norov@gmail.com> References: <20211218212014.1315894-1-yury.norov@gmail.com> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20211218_132040_878811_DAC4618A X-CRM114-Status: GOOD ( 23.51 ) X-BeenThere: linux-riscv@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-riscv" Errors-To: linux-riscv-bounces+linux-riscv=archiver.kernel.org@lists.infradead.org Many kernel users use bitmap_weight() to compare the result against some number or expression: if (bitmap_weight(...) > 1) do_something(); It works OK, but may be significantly improved for large bitmaps: if first few words count set bits to a number greater than given, we can stop counting and immediately return. The same idea would work in other direction: if we know that the number of set bits that we counted so far is small enough, so that it would be smaller than required number even if all bits of the rest of the bitmap are set, we can stop counting earlier. This patch adds new bitmap_weight_cmp() as suggested by Michał Mirosław and a family of eq, gt, ge, lt and le wrappers to allow this optimization. The following patches apply new functions where appropriate. Suggested-by: "Michał Mirosław" (for bitmap_weight_cmp) Signed-off-by: Yury Norov --- include/linux/bitmap.h | 80 ++++++++++++++++++++++++++++++++++++++++++ lib/bitmap.c | 21 +++++++++++ 2 files changed, 101 insertions(+) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 7dba0847510c..708e57b32362 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -51,6 +51,12 @@ struct device; * bitmap_empty(src, nbits) Are all bits zero in *src? * bitmap_full(src, nbits) Are all bits set in *src? * bitmap_weight(src, nbits) Hamming Weight: number set bits + * bitmap_weight_cmp(src, nbits) compare Hamming Weight with a number + * bitmap_weight_eq(src, nbits, num) Hamming Weight == num + * bitmap_weight_gt(src, nbits, num) Hamming Weight > num + * bitmap_weight_ge(src, nbits, num) Hamming Weight >= num + * bitmap_weight_lt(src, nbits, num) Hamming Weight < num + * bitmap_weight_le(src, nbits, num) Hamming Weight <= num * bitmap_set(dst, pos, nbits) Set specified bit area * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area @@ -162,6 +168,7 @@ int __bitmap_intersects(const unsigned long *bitmap1, int __bitmap_subset(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits); +int __bitmap_weight_cmp(const unsigned long *bitmap, unsigned int bits, int num); void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); @@ -403,6 +410,79 @@ static __always_inline int bitmap_weight(const unsigned long *src, unsigned int return __bitmap_weight(src, nbits); } +/** + * bitmap_weight_cmp - compares number of set bits in @src with @num. + * @src: source bitmap + * @nbits: length of bitmap in bits + * @num: number to compare with + * + * As opposite to bitmap_weight() this function doesn't necessarily + * traverse full bitmap and may return earlier. + * + * Returns zero if weight of @src is equal to @num; + * negative number if weight of @src is less than @num; + * positive number if weight of @src is greater than @num; + * + * NOTES + * + * Because number of set bits cannot decrease while counting, when user + * wants to know if the number of set bits in the bitmap is less than + * @num, calling + * bitmap_weight_cmp(..., @num) < 0 + * is potentially less effective than + * bitmap_weight_cmp(..., @num - 1) <= 0 + * + * Consider an example: + * bitmap_weight_cmp(1000 0000 0000 0000, 1) < 0 + * ^ + * stop here + * + * bitmap_weight_cmp(1000 0000 0000 0000, 0) <= 0 + * ^ + * stop here + */ +static __always_inline +int bitmap_weight_cmp(const unsigned long *src, unsigned int nbits, int num) +{ + if (num > (int)nbits || num < 0) + return -num; + + if (small_const_nbits(nbits)) + return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)) - num; + + return __bitmap_weight_cmp(src, nbits, num); +} + +static __always_inline +bool bitmap_weight_eq(const unsigned long *src, unsigned int nbits, int num) +{ + return bitmap_weight_cmp(src, nbits, num) == 0; +} + +static __always_inline +bool bitmap_weight_gt(const unsigned long *src, unsigned int nbits, int num) +{ + return bitmap_weight_cmp(src, nbits, num) > 0; +} + +static __always_inline +bool bitmap_weight_ge(const unsigned long *src, unsigned int nbits, int num) +{ + return bitmap_weight_cmp(src, nbits, num - 1) > 0; +} + +static __always_inline +bool bitmap_weight_lt(const unsigned long *src, unsigned int nbits, int num) +{ + return bitmap_weight_cmp(src, nbits, num - 1) <= 0; +} + +static __always_inline +bool bitmap_weight_le(const unsigned long *src, unsigned int nbits, int num) +{ + return bitmap_weight_cmp(src, nbits, num) <= 0; +} + static __always_inline void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits) { diff --git a/lib/bitmap.c b/lib/bitmap.c index 926408883456..fb84ca70c5d9 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -348,6 +348,27 @@ int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) } EXPORT_SYMBOL(__bitmap_weight); +int __bitmap_weight_cmp(const unsigned long *bitmap, unsigned int bits, int num) +{ + unsigned int k, w, lim = bits / BITS_PER_LONG; + + for (k = 0, w = 0; k < lim; k++) { + if (w + bits - k * BITS_PER_LONG < num) + goto out; + + w += hweight_long(bitmap[k]); + + if (w > num) + goto out; + } + + if (bits % BITS_PER_LONG) + w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); +out: + return w - num; +} +EXPORT_SYMBOL(__bitmap_weight_cmp); + void __bitmap_set(unsigned long *map, unsigned int start, int len) { unsigned long *p = map + BIT_WORD(start);