From mboxrd@z Thu Jan 1 00:00:00 1970 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 kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3E351C433F5 for ; Sat, 18 Dec 2021 21:24:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8E2A56B007E; Sat, 18 Dec 2021 16:20:51 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 8B7DC6B0080; Sat, 18 Dec 2021 16:20:51 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7325D6B0081; Sat, 18 Dec 2021 16:20:51 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0231.hostedemail.com [216.40.44.231]) by kanga.kvack.org (Postfix) with ESMTP id 66D2A6B007E for ; Sat, 18 Dec 2021 16:20:51 -0500 (EST) Received: from smtpin27.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 2EC5084CF9 for ; Sat, 18 Dec 2021 21:20:41 +0000 (UTC) X-FDA: 78932184282.27.A60DF52 Received: from mail-oo1-f47.google.com (mail-oo1-f47.google.com [209.85.161.47]) by imf28.hostedemail.com (Postfix) with ESMTP id D0A6FC0048 for ; Sat, 18 Dec 2021 21:20:40 +0000 (UTC) Received: by mail-oo1-f47.google.com with SMTP id p2-20020a4adfc2000000b002c2676904fdso1817933ood.13 for ; 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=2WF6KgKUUDCsChVduweXjkss9DQCHItQcrVmCMcy8U7Mt3wS/MBqK7XQcZEv7P7en0 yft7qA1J5FE82Zvdwa+Iu9TIBafNrZhD35HIsyNu7Zz5N5Idp5X8f3IqSZhpznavdXXm LNkCt0NUUJ4UgrUB3i57vKOYB2xVq83Ba98k5fowonxRain3xlCKcwXIPbWglcS8IEjT 8go7PQRiJJd1TyW5zj9WbuTVYAXvg1KykMRnBFBkBCfOHUgZkwYBFIMtbCFYwdJODB1d T+/EThajPo1mCB7bEanr+9NZrptGlq2W1lMz/6oFMbOIuYLtwZjilWsV5XukaBImrBir /lmA== X-Gm-Message-State: AOAM532btdzN1IaOIU6VBK2ovRWKWyhGZyDkQZoKqxxTcLlWujJtaV3m otDk006a69y9DuUHu2rzrF+5ikoW0VGbig== 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?q?Micha=C5=82=20Miros=C5=82aw?= , "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 Content-Type: text/plain; charset=UTF-8 X-Rspamd-Server: rspam03 X-Rspamd-Queue-Id: D0A6FC0048 X-Stat-Signature: yjgjy6kgbo9cejep7ornt8569jzoy4xk Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=ky3nIm4V; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf28.hostedemail.com: domain of yury.norov@gmail.com designates 209.85.161.47 as permitted sender) smtp.mailfrom=yury.norov@gmail.com X-HE-Tag: 1639862440-813417 Content-Transfer-Encoding: quoted-printable X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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=C5=82 Miros= =C5=82aw 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=C5=82 Miros=C5=82aw" (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 *sr= c? * bitmap_full(src, nbits) Are all bits set in *src= ? * bitmap_weight(src, nbits) Hamming Weight: number s= et bits + * bitmap_weight_cmp(src, nbits) compare Hamming Weight w= ith a number + * bitmap_weight_eq(src, nbits, num) Hamming Weight =3D=3D nu= m + * bitmap_weight_gt(src, nbits, num) Hamming Weight > num + * bitmap_weight_ge(src, nbits, num) Hamming Weight >=3D num + * bitmap_weight_lt(src, nbits, num) Hamming Weight < num + * bitmap_weight_le(src, nbits, num) Hamming Weight <=3D 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 ar= ea @@ -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); =20 @@ -403,6 +410,79 @@ static __always_inline int bitmap_weight(const unsig= ned long *src, unsigned int return __bitmap_weight(src, nbits); } =20 +/** + * 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) <=3D 0 + * + * Consider an example: + * bitmap_weight_cmp(1000 0000 0000 0000, 1) < 0 + * ^ + * stop here + * + * bitmap_weight_cmp(1000 0000 0000 0000, 0) <=3D 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) =3D=3D 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) <=3D 0; +} + +static __always_inline +bool bitmap_weight_le(const unsigned long *src, unsigned int nbits, int = num) +{ + return bitmap_weight_cmp(src, nbits, num) <=3D 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, uns= igned int bits) } EXPORT_SYMBOL(__bitmap_weight); =20 +int __bitmap_weight_cmp(const unsigned long *bitmap, unsigned int bits, = int num) +{ + unsigned int k, w, lim =3D bits / BITS_PER_LONG; + + for (k =3D 0, w =3D 0; k < lim; k++) { + if (w + bits - k * BITS_PER_LONG < num) + goto out; + + w +=3D hweight_long(bitmap[k]); + + if (w > num) + goto out; + } + + if (bits % BITS_PER_LONG) + w +=3D 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 =3D map + BIT_WORD(start); --=20 2.30.2