| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <20211128035704.270739-2-yury.norov@gmail.com>
Date: Sat, 27 Nov 2021 19:56:56 -0800
From: Yury Norov <yury.norov@...il.com>
To: linux-kernel@...r.kernel.org, Yury Norov <yury.norov@...il.com>,
"James E.J. Bottomley" <jejb@...ux.ibm.com>,
"Martin K. Petersen" <martin.petersen@...cle.com>,
"Paul E. McKenney" <paulmck@...nel.org>,
"Rafael J. Wysocki" <rafael@...nel.org>,
Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
Alexey Klimov <aklimov@...hat.com>,
Amitkumar Karwar <amitkarwar@...il.com>,
Andi Kleen <ak@...ux.intel.com>, Andrew Lunn <andrew@...n.ch>,
Andrew Morton <akpm@...ux-foundation.org>,
Andy Gross <agross@...nel.org>,
Andy Lutomirski <luto@...nel.org>,
Andy Shevchenko <andy@...radead.org>,
Anup Patel <anup.patel@....com>,
Ard Biesheuvel <ardb@...nel.org>,
Arnaldo Carvalho de Melo <acme@...nel.org>,
Arnd Bergmann <arnd@...db.de>, Borislav Petkov <bp@...en8.de>,
Catalin Marinas <catalin.marinas@....com>,
Christoph Hellwig <hch@....de>,
Christoph Lameter <cl@...ux.com>,
Daniel Vetter <daniel@...ll.ch>,
Dave Hansen <dave.hansen@...ux.intel.com>,
David Airlie <airlied@...ux.ie>,
David Laight <David.Laight@...LAB.COM>,
Dennis Zhou <dennis@...nel.org>,
Dinh Nguyen <dinguyen@...nel.org>,
Geetha sowjanya <gakula@...vell.com>,
Geert Uytterhoeven <geert@...ux-m68k.org>,
Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
Guo Ren <guoren@...nel.org>,
Hans de Goede <hdegoede@...hat.com>,
Heiko Carstens <hca@...ux.ibm.com>,
Ian Rogers <irogers@...gle.com>,
Ingo Molnar <mingo@...hat.com>,
Jakub Kicinski <kuba@...nel.org>,
Jason Wessel <jason.wessel@...driver.com>,
Jens Axboe <axboe@...com>, Jiri Olsa <jolsa@...hat.com>,
Jonathan Cameron <jic23@...nel.org>,
Juri Lelli <juri.lelli@...hat.com>,
Kalle Valo <kvalo@...eaurora.org>,
Kees Cook <keescook@...omium.org>,
Krzysztof Kozlowski <krzysztof.kozlowski@...onical.com>,
Lee Jones <lee.jones@...aro.org>,
Marc Zyngier <maz@...nel.org>, Marcin Wojtas <mw@...ihalf.com>,
Mark Gross <markgross@...nel.org>,
Mark Rutland <mark.rutland@....com>,
Matti Vaittinen <mazziesaccount@...il.com>,
Mauro Carvalho Chehab <mchehab@...nel.org>,
Mel Gorman <mgorman@...e.de>,
Michael Ellerman <mpe@...erman.id.au>,
Mike Marciniszyn <mike.marciniszyn@...nelisnetworks.com>,
Nicholas Piggin <npiggin@...il.com>,
Palmer Dabbelt <palmer@...belt.com>,
Peter Zijlstra <peterz@...radead.org>,
Petr Mladek <pmladek@...e.com>,
Randy Dunlap <rdunlap@...radead.org>,
Rasmus Villemoes <linux@...musvillemoes.dk>,
Roy Pledge <Roy.Pledge@....com>,
Russell King <linux@...linux.org.uk>,
Saeed Mahameed <saeedm@...dia.com>,
Sagi Grimberg <sagi@...mberg.me>,
Sergey Senozhatsky <senozhatsky@...omium.org>,
Solomon Peachy <pizza@...ftnet.org>,
Stephen Boyd <sboyd@...nel.org>,
Stephen Rothwell <sfr@...b.auug.org.au>,
Steven Rostedt <rostedt@...dmis.org>,
Subbaraya Sundeep <sbhatta@...vell.com>,
Sudeep Holla <sudeep.holla@....com>,
Sunil Goutham <sgoutham@...vell.com>,
Tariq Toukan <tariqt@...dia.com>, Tejun Heo <tj@...nel.org>,
Thomas Bogendoerfer <tsbogend@...ha.franken.de>,
Thomas Gleixner <tglx@...utronix.de>,
Ulf Hansson <ulf.hansson@...aro.org>,
Vincent Guittot <vincent.guittot@...aro.org>,
Vineet Gupta <vgupta@...nel.org>,
Viresh Kumar <viresh.kumar@...aro.org>,
Vivien Didelot <vivien.didelot@...il.com>,
Vlastimil Babka <vbabka@...e.cz>,
Will Deacon <will@...nel.org>,
bcm-kernel-feedback-list@...adcom.com, kvm@...r.kernel.org,
linux-alpha@...r.kernel.org, linux-arm-kernel@...ts.infradead.org,
linux-crypto@...r.kernel.org, linux-csky@...r.kernel.org,
linux-ia64@...r.kernel.org, linux-mips@...r.kernel.org,
linux-mm@...ck.org, linux-perf-users@...r.kernel.org,
linux-riscv@...ts.infradead.org, linux-s390@...r.kernel.org,
linux-snps-arc@...ts.infradead.org, linuxppc-dev@...ts.ozlabs.org
Subject: [PATCH 1/9] lib/bitmap: add bitmap_weight_{eq,gt,le}
Many kernel users call 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 return earlier.
This patch adds new bitmap_weight_{eq,gt,le} functions to allow this
optimization, and the following patches apply them where appropriate.
Signed-off-by: Yury Norov <yury.norov@...il.com>
---
include/linux/bitmap.h | 33 ++++++++++++++++++++++
lib/bitmap.c | 63 ++++++++++++++++++++++++++++++++++++++++++
2 files changed, 96 insertions(+)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 7dba0847510c..996041f771c8 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -51,6 +51,9 @@ 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_eq(src, nbits, num) Hamming Weight is equal to num
+ * bitmap_weight_gt(src, nbits, num) Hamming Weight is greater than num
+ * bitmap_weight_le(src, nbits, num) Hamming Weight is less than 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 +165,9 @@ 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);
+bool __bitmap_weight_eq(const unsigned long *bitmap, unsigned int nbits, unsigned int num);
+bool __bitmap_weight_gt(const unsigned long *bitmap, unsigned int nbits, unsigned int num);
+bool __bitmap_weight_le(const unsigned long *bitmap, unsigned int nbits, unsigned 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 +409,33 @@ static __always_inline int bitmap_weight(const unsigned long *src, unsigned int
return __bitmap_weight(src, nbits);
}
+static __always_inline bool bitmap_weight_eq(const unsigned long *src,
+ unsigned int nbits, unsigned int num)
+{
+ if (small_const_nbits(nbits))
+ return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)) == num;
+
+ return __bitmap_weight_eq(src, nbits, num);
+}
+
+static __always_inline bool bitmap_weight_gt(const unsigned long *src,
+ unsigned int nbits, unsigned int num)
+{
+ if (small_const_nbits(nbits))
+ return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)) > num;
+
+ return __bitmap_weight_gt(src, nbits, num);
+}
+
+static __always_inline bool bitmap_weight_le(const unsigned long *src,
+ unsigned int nbits, unsigned int num)
+{
+ if (small_const_nbits(nbits))
+ return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)) < num;
+
+ return __bitmap_weight_le(src, nbits, num);
+}
+
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..72e7ab2d7bdd 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -348,6 +348,69 @@ int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
}
EXPORT_SYMBOL(__bitmap_weight);
+bool __bitmap_weight_eq(const unsigned long *bitmap, unsigned int bits, unsigned 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)
+ return false;
+
+ w += hweight_long(bitmap[k]);
+
+ if (w > num)
+ return false;
+ }
+
+ if (bits % BITS_PER_LONG)
+ w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
+
+ return w == num;
+}
+EXPORT_SYMBOL(__bitmap_weight_eq);
+
+bool __bitmap_weight_gt(const unsigned long *bitmap, unsigned int bits, unsigned 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)
+ return false;
+
+ w += hweight_long(bitmap[k]);
+
+ if (w > num)
+ return true;
+ }
+
+ if (bits % BITS_PER_LONG)
+ w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
+
+ return w > num;
+}
+EXPORT_SYMBOL(__bitmap_weight_gt);
+
+bool __bitmap_weight_le(const unsigned long *bitmap, unsigned int bits, unsigned 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)
+ return true;
+
+ w += hweight_long(bitmap[k]);
+
+ if (w >= num)
+ return false;
+ }
+
+ if (bits % BITS_PER_LONG)
+ w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
+
+ return w < num;
+}
+EXPORT_SYMBOL(__bitmap_weight_le);
+
void __bitmap_set(unsigned long *map, unsigned int start, int len)
{
unsigned long *p = map + BIT_WORD(start);
--
2.25.1
Powered by blists - more mailing lists