From patchwork Thu Nov 3 20:03:41 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mathieu Desnoyers X-Patchwork-Id: 15159 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp742336wru; Thu, 3 Nov 2022 13:06:26 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5QGjOU520q/cfrASfjk+JctSqs+2XxcZHKVnBlVxXpeDZNWV5m1IHe5IUXkJKoX90ndjEl X-Received: by 2002:a05:6a00:234c:b0:56c:f6e6:976 with SMTP id j12-20020a056a00234c00b0056cf6e60976mr31918566pfj.32.1667505985906; Thu, 03 Nov 2022 13:06:25 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1667505985; cv=none; d=google.com; s=arc-20160816; b=ucwyXlzETpk8FqExHUNvfJ3MobfkrhnUDf+WMmz8/kPKda6efmr5qgNsiSYFpyPy0o Yl69SWs3Mza9mNZPesVjV4cgZtRADlVhZ9a4+xLhW/A0hQxfOmTXHMB1GpgXmdrq0Wgm QhSKQijaP5M2lYlGIMhXox8LyRn+sjr7oqvR7KR+Exn/g8Idlue8rFWEPlC9yuugGNpe m56nqHTLOZ6HdjsXIxfgmqd5LSBTVCrVw2c3Wzou5+r3TTbHScSCjeN9dZ1DQj9j3335 n154nDqoKdAueuMLsTIGHFAzXUJPwUkEscuZoCyd3Fcy/+/1Q2YqwuwTpqxLO408b+AT T3rQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=NBD+Bqe0ypoYJ1j+PIfOR0yI8KRN629Qz9qe/lLEV38=; b=K6gGNzCRaTO6Be6/0NoBOL9aqpzxgiK7c9YmBDrcEhN/Y87vMplfnlJ8XJ3HIQuJjs VsVVNIRY4xCChn+pzLi+/FwOMpRIu0J0w7MUb8AVjt9/9y/8OpM9O2U+Xw5BwbseMM23 yFCE86bf23uJUKcwGds8UNvzXjdgVMAmcN7mI9Xp7GHkMYGLB7oOeZCEJdB7djeqJBlH /9xNaiM20JOdYg5ICx6+Gq1ZMHpdy7l/Xxfler93QKvtDZj4GlLv6QrqsYUC6+7XE8WU tYHoq+mOfZsftfvuBhWUIjvct2g1srOJ37Mu8lFm9Egr3BAQ4BJaSh9KwCFswTs3XX8/ KBkQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@efficios.com header.s=smtpout1 header.b=PX7mVB4A; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=efficios.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id 12-20020a630d4c000000b00470096ba718si2116188pgn.200.2022.11.03.13.06.11; Thu, 03 Nov 2022 13:06:25 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@efficios.com header.s=smtpout1 header.b=PX7mVB4A; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=efficios.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231508AbiKCUFY (ORCPT + 99 others); Thu, 3 Nov 2022 16:05:24 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54546 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230410AbiKCUFA (ORCPT ); Thu, 3 Nov 2022 16:05:00 -0400 Received: from smtpout.efficios.com (smtpout.efficios.com [IPv6:2607:5300:203:5aae::31e5]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F26B92034F; Thu, 3 Nov 2022 13:04:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1667505897; bh=yXMCQTJUBVpgK2HTSfnSaD1+EBfTlpw5kc6q1ePvqj4=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=PX7mVB4AbWTz7C0kIbwTzWLVhDu9iR1/2N6wfo7RmJYJsORUgHmcXRCAd0xvRAHv7 DXWh03M/4BJOlNgqS1ZgQzF8UqBz/jB9/7su1eF1jC8I1rLtKk7XJ0APZFgXlgLccj NfBZoU+kHlhIDZ273o0fpXCQ25oOg3ctODMLbD3R3pMdKrs6idIiCV42MH1WqzVtxi asS6vxrX2gKT9oGasRGXMrKD90XR10NFekdxCXSoojOUV6h5uuxaCAoG3014ZvTViz ar045vXY2WwYLrNxP/VjNlxXgjev7GsulEVyUXCV3nOQ0TRgMRSi2k1flWq42Q9rvT 7oA1QQQB5Ri7Q== Received: from localhost.localdomain (192-222-180-24.qc.cable.ebox.net [192.222.180.24]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4N3F950gLZzftP; Thu, 3 Nov 2022 16:04:57 -0400 (EDT) From: Mathieu Desnoyers To: Peter Zijlstra Cc: linux-kernel@vger.kernel.org, Thomas Gleixner , "Paul E . McKenney" , Boqun Feng , "H . Peter Anvin" , Paul Turner , linux-api@vger.kernel.org, Christian Brauner , Florian Weimer , David.Laight@ACULAB.COM, carlos@redhat.com, Peter Oskolkov , Alexander Mikhalitsyn , Chris Kennelly , Mathieu Desnoyers Subject: [PATCH v5 06/24] lib: Implement find_{first,next,nth}_notandnot_bit, find_first_andnot_bit Date: Thu, 3 Nov 2022 16:03:41 -0400 Message-Id: <20221103200359.328736-7-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20221103200359.328736-1-mathieu.desnoyers@efficios.com> References: <20221103200359.328736-1-mathieu.desnoyers@efficios.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1748506756777488439?= X-GMAIL-MSGID: =?utf-8?q?1748506756777488439?= Allow finding the first, next, or nth bit within two input bitmasks which is zero in both masks. Allow fiding the first bit within two input bitmasks which is set in first mask and cleared in the second mask. find_next_andnot_bit and find_nth_andnot_bit already exist, so find the first bit appears to be missing. Signed-off-by: Mathieu Desnoyers --- include/linux/find.h | 123 +++++++++++++++++++++++++++++++++++++++++-- lib/find_bit.c | 42 +++++++++++++++ 2 files changed, 161 insertions(+), 4 deletions(-) diff --git a/include/linux/find.h b/include/linux/find.h index ccaf61a0f5fd..43c3db92a096 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -14,6 +14,8 @@ unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long unsigned long nbits, unsigned long start); unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long nbits, unsigned long start); +unsigned long _find_next_notandnot_bit(const unsigned long *addr1, const unsigned long *addr2, + unsigned long nbits, unsigned long start); unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, unsigned long start); extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size); @@ -22,8 +24,14 @@ unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long unsigned long size, unsigned long n); unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size, unsigned long n); +unsigned long __find_nth_notandnot_bit(const unsigned long *addr1, const unsigned long *addr2, + unsigned long size, unsigned long n); extern unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size); +extern unsigned long _find_first_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, unsigned long size); +extern unsigned long _find_first_notandnot_bit(const unsigned long *addr1, + const unsigned long *addr2, unsigned long size); extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size); extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size); @@ -95,15 +103,14 @@ unsigned long find_next_and_bit(const unsigned long *addr1, #ifndef find_next_andnot_bit /** - * find_next_andnot_bit - find the next set bit in *addr1 excluding all the bits - * in *addr2 + * find_next_andnot_bit - find the next bit set in *addr1, cleared in *addr2 * @addr1: The first address to base the search on * @addr2: The second address to base the search on * @size: The bitmap size in bits * @offset: The bitnumber to start searching at * - * Returns the bit number for the next set bit - * If no bits are set, returns @size. + * Returns the bit number for the next bit set in *addr1, cleared in *addr2 + * If no such bits are found, returns @size. */ static inline unsigned long find_next_andnot_bit(const unsigned long *addr1, @@ -124,6 +131,37 @@ unsigned long find_next_andnot_bit(const unsigned long *addr1, } #endif +#ifndef find_next_notandnot_bit +/** + * find_next_notandnot_bit - find the next bit cleared in both *addr1 and *addr2 + * @addr1: The first address to base the search on + * @addr2: The second address to base the search on + * @size: The bitmap size in bits + * @offset: The bitnumber to start searching at + * + * Returns the bit number for the next bit cleared in both *addr1 and *addr2 + * If no such bits are found, returns @size. + */ +static inline +unsigned long find_next_notandnot_bit(const unsigned long *addr1, + const unsigned long *addr2, unsigned long size, + unsigned long offset) +{ + if (small_const_nbits(size)) { + unsigned long val; + + if (unlikely(offset >= size)) + return size; + + val = ~*addr1 & ~*addr2 & GENMASK(size - 1, offset); + return val ? __ffs(val) : size; + } + + return _find_next_notandnot_bit(addr1, addr2, size, offset); +} +#endif + + #ifndef find_next_zero_bit /** * find_next_zero_bit - find the next cleared bit in a memory region @@ -255,6 +293,32 @@ unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned lon return __find_nth_andnot_bit(addr1, addr2, size, n); } +/** + * find_nth_notandnot_bit - find N'th cleared bit in 2 memory regions. + * @addr1: The 1st address to start the search at + * @addr2: The 2nd address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed, counting from 0 + * + * Returns the bit number of the N'th cleared bit. + * If no such, returns @size. + */ +static inline +unsigned long find_nth_notandnot_bit(const unsigned long *addr1, const unsigned long *addr2, + unsigned long size, unsigned long n) +{ + if (n >= size) + return size; + + if (small_const_nbits(size)) { + unsigned long val = (~*addr1) & (~*addr2) & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return __find_nth_notandnot_bit(addr1, addr2, size, n); +} + #ifndef find_first_and_bit /** * find_first_and_bit - find the first set bit in both memory regions @@ -280,6 +344,57 @@ unsigned long find_first_and_bit(const unsigned long *addr1, } #endif +#ifndef find_first_andnot_bit +/** + * find_first_andnot_bit - find first set bit in 2 memory regions, + * flipping bits in 2nd region + * @addr1: The first address to base the search on + * @addr2: The second address to base the search on + * @size: The bitmap size in bits + * + * Returns the bit number for the next set bit + * If no bits are set, returns @size. + */ +static inline +unsigned long find_first_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + unsigned long size) +{ + if (small_const_nbits(size)) { + unsigned long val = *addr1 & (~*addr2) & GENMASK(size - 1, 0); + + return val ? __ffs(val) : size; + } + + return _find_first_andnot_bit(addr1, addr2, size); +} +#endif + +#ifndef find_first_notandnot_bit +/** + * find_first_notandnot_bit - find first cleared bit in 2 memory regions + * @addr1: The first address to base the search on + * @addr2: The second address to base the search on + * @size: The bitmap size in bits + * + * Returns the bit number for the next cleared bit + * If no bits are set, returns @size. + */ +static inline +unsigned long find_first_notandnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + unsigned long size) +{ + if (small_const_nbits(size)) { + unsigned long val = (~*addr1) & (~*addr2) & GENMASK(size - 1, 0); + + return val ? __ffs(val) : size; + } + + return _find_first_notandnot_bit(addr1, addr2, size); +} +#endif + #ifndef find_first_zero_bit /** * find_first_zero_bit - find the first cleared bit in a memory region diff --git a/lib/find_bit.c b/lib/find_bit.c index 18bc0a7ac8ee..a1f592f2437e 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -116,6 +116,32 @@ unsigned long _find_first_and_bit(const unsigned long *addr1, EXPORT_SYMBOL(_find_first_and_bit); #endif +#ifndef find_first_andnot_bit +/* + * Find the first set bit in two memory regions, flipping bits in 2nd region. + */ +unsigned long _find_first_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + unsigned long size) +{ + return FIND_FIRST_BIT(addr1[idx] & ~addr2[idx], /* nop */, size); +} +EXPORT_SYMBOL(_find_first_andnot_bit); +#endif + +#ifndef find_first_notandnot_bit +/* + * Find the first cleared bit in two memory regions. + */ +unsigned long _find_first_notandnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + unsigned long size) +{ + return FIND_FIRST_BIT(~addr1[idx] & ~addr2[idx], /* nop */, size); +} +EXPORT_SYMBOL(_find_first_notandnot_bit); +#endif + #ifndef find_first_zero_bit /* * Find the first cleared bit in a memory region. @@ -155,6 +181,13 @@ unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned l } EXPORT_SYMBOL(__find_nth_andnot_bit); +unsigned long __find_nth_notandnot_bit(const unsigned long *addr1, const unsigned long *addr2, + unsigned long size, unsigned long n) +{ + return FIND_NTH_BIT(~addr1[idx] & ~addr2[idx], size, n); +} +EXPORT_SYMBOL(__find_nth_notandnot_bit); + #ifndef find_next_and_bit unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long nbits, unsigned long start) @@ -173,6 +206,15 @@ unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned l EXPORT_SYMBOL(_find_next_andnot_bit); #endif +#ifndef find_next_notandnot_bit +unsigned long _find_next_notandnot_bit(const unsigned long *addr1, const unsigned long *addr2, + unsigned long nbits, unsigned long start) +{ + return FIND_NEXT_BIT(~addr1[idx] & ~addr2[idx], /* nop */, nbits, start); +} +EXPORT_SYMBOL(_find_next_notandnot_bit); +#endif + #ifndef find_next_zero_bit unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)