From patchwork Sun Nov 28 03:56:56 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 12642667 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 A9B0BC433FE for ; Sun, 28 Nov 2021 03:57:37 +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=dmIHkbi8LOWnTCsZsUcipY10ll3D79U4OYSMrM4BB4Y=; b=fFWTSvRCoePVZt 9PUXO5BcJBuwBLep9RnNk9ghdzJYFHGYHE8TH355A8axSc8wGxj7x+Mp9R7Qvui8uNvDQxeUgKfcE cF8AZJ+ZT/3IWpdDiErsax+KgYMNFtssbVKu6U+VMfQ6ZPxgk15vnBeUhyD7BXZjjQV6OAV3QcKqK IJc3ybhGSWP1asVlta3lTgB85Q7WCVluQeMLNn/c1xGeM5PXdq8nR3okn8v1QA4DMzNued9bOpaTk TULpu0HzVJDqt5As68GGvdZNAD2dg+hRcezbC0g2kWnqCwy7nk6t9sJqNjJr0J/+O3XGYEmDJlHrQ eTYrkwnwAZ5r9pu+h0Qg==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1mrBJT-00ExUc-HG; Sun, 28 Nov 2021 03:57:15 +0000 Received: from mail-qt1-x836.google.com ([2607:f8b0:4864:20::836]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1mrBJN-00ExR6-Rq; Sun, 28 Nov 2021 03:57:11 +0000 Received: by mail-qt1-x836.google.com with SMTP id t34so12906409qtc.7; Sat, 27 Nov 2021 19:57:09 -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=oyYw0S0uIYbzbJlT2sTRB5/AL9ZCZW5naP5e066GZEw=; b=pRmYH3DF71YxuUIeQtUZruUdNNbsy9VbRav7B36MJevKZvkrVj0n380VwT9ymC/6tG I3jRVCazSdBphHgxopQgwYWsemberSxSLLmEZ3tbZZbD8KpHpZflSpa+2S0k6f6QnB63 LB8J/U92ggXSM5heSnBWXElO/lbm0h3GvHDm+xfKfMbvFUiCUQhf7pfNhI/oaY9IVP8w 7t+nf549TZ3BfT1eSpUgpkQbcUE7bqe1pWWQUMdmdt6c2ZEHLOYC5EdviqL4d6Gm0jRf 3M/+zB1qnWTzYKLjhE16NC3G38+E6HR1NvaA5CMDVSJ3aiJNz0XRVEXMB3VTCE4t50qm Oo5Q== 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=oyYw0S0uIYbzbJlT2sTRB5/AL9ZCZW5naP5e066GZEw=; b=5mN7tpFD0cR1UUu9iAeebPyrrC0HfZ+nmKA7/JMd/DVKtud4zdM/SWsqQWj7T4wP10 agRWUsh+J9AZ/FSBb/K7qzNx+Ebr66oMHsbEbAVrPfL9BDwlD9ijbARBpYcnPylMHitB 5O+qeFVfJvpJ+yqmolkkFFy9ptZ/smydmip5yoJSgyq/+GsI38YoYls2o5EEG8C5llUX K3lepuD05kV5N4Pzdp4RMeCcTr8u/H4DYMndYHchAQq4SjQoflqDZx6rRNoL5yIm3JFT xE6Yr/YMY83bX43rNAD51EDcqFvpLvQP54FzZ671zLL79l2lUG2Yx5//MqTWJF8kLjyK 4t8Q== X-Gm-Message-State: AOAM5328pfbz8XArMGQAmnklsoKhb1UvtjUzYbqvris0EJ0jz7XtsccY DqazpN5D/aDsMz4lt7c+hQA= X-Google-Smtp-Source: ABdhPJzCSIHK5gqoZpz/7aPIEpGhuYe/wtGfXQ5VTkZ0R5LJuGRI9ufln+7naenMGGb1nvoOREIAZQ== X-Received: by 2002:ac8:7fca:: with SMTP id b10mr26533825qtk.500.1638071828690; Sat, 27 Nov 2021 19:57:08 -0800 (PST) Received: from localhost ([66.216.211.25]) by smtp.gmail.com with ESMTPSA id v1sm6498979qtw.65.2021.11.27.19.57.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 27 Nov 2021 19:57:08 -0800 (PST) From: Yury Norov To: linux-kernel@vger.kernel.org, Yury Norov , "James E.J. Bottomley" , "Martin K. Petersen" , "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 , Dinh Nguyen , Geetha sowjanya , Geert Uytterhoeven , Greg Kroah-Hartman , Guo Ren , Hans de Goede , Heiko Carstens , Ian Rogers , Ingo Molnar , Jakub Kicinski , Jason Wessel , Jens Axboe , Jiri Olsa , Jonathan Cameron , Juri Lelli , Kalle Valo , 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 , Roy Pledge , 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 1/9] lib/bitmap: add bitmap_weight_{eq,gt,le} Date: Sat, 27 Nov 2021 19:56:56 -0800 Message-Id: <20211128035704.270739-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211128035704.270739-1-yury.norov@gmail.com> References: <20211128035704.270739-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-20211127_195709_929370_008404DA X-CRM114-Status: GOOD ( 20.67 ) 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 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 --- 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);