From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: linux-kernel@vger.kernel.org,
Thomas Gleixner <tglx@linutronix.de>,
"Paul E . McKenney" <paulmck@kernel.org>,
Boqun Feng <boqun.feng@gmail.com>,
"H . Peter Anvin" <hpa@zytor.com>, Paul Turner <pjt@google.com>,
linux-api@vger.kernel.org, Christian Brauner <brauner@kernel.org>,
Florian Weimer <fw@deneb.enyo.de>,
David.Laight@ACULAB.COM, carlos@redhat.com,
Peter Oskolkov <posk@posk.io>,
Alexander Mikhalitsyn <alexander@mihalicyn.com>,
Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Subject: [PATCH v4 07/25] lib: Implement find_{first,next}_{zero,one}_and_zero_bit
Date: Thu, 22 Sep 2022 06:59:22 -0400 [thread overview]
Message-ID: <20220922105941.237830-8-mathieu.desnoyers@efficios.com> (raw)
In-Reply-To: <20220922105941.237830-1-mathieu.desnoyers@efficios.com>
Allow finding the first or next bit within two input bitmasks which is
either:
- both zero and zero,
- respectively one and zero.
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
include/linux/find.h | 110 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 110 insertions(+)
diff --git a/include/linux/find.h b/include/linux/find.h
index 935892da576e..325707b8bd56 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -76,6 +76,66 @@ unsigned long find_next_and_bit(const unsigned long *addr1,
}
#endif
+#ifndef find_next_one_and_zero_bit
+/**
+ * find_next_one_and_zero_bit - find the next bit which is one in addr1 and zero in addr2 memory region
+ * @addr1: The first address to base the search on
+ * @addr2: The second address to base the search on
+ * @offset: The bitnumber to start searching at
+ * @size: The bitmap size in bits
+ *
+ * Returns the bit number for the next bit set in addr1 and cleared in addr2
+ * If no corresponding bits meet this criterion, returns @size.
+ */
+static inline
+unsigned long find_next_one_and_zero_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_bit(addr1, addr2, size, offset, 0UL, ~0UL, 0);
+}
+#endif
+
+#ifndef find_next_zero_and_zero_bit
+/**
+ * find_next_zero_and_zero_bit - find the next bit which is zero in addr1 and addr2 memory regions
+ * @addr1: The first address to base the search on
+ * @addr2: The second address to base the search on
+ * @offset: The bitnumber to start searching at
+ * @size: The bitmap size in bits
+ *
+ * Returns the bit number for the next bit cleared in addr1 and addr2
+ * If no corresponding bits meet this criterion, returns @size.
+ */
+static inline
+unsigned long find_next_zero_and_zero_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_bit(addr1, addr2, size, offset, ~0UL, ~0UL, 0);
+}
+#endif
+
#ifndef find_next_zero_bit
/**
* find_next_zero_bit - find the next cleared bit in a memory region
@@ -173,6 +233,56 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
}
#endif
+#ifndef find_first_one_and_zero_bit
+/**
+ * find_first_one_and_zero_bit - find the first bit which is one in addr1 and zero in addr2 memory 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 first bit set in addr1 and cleared in addr2
+ * If no corresponding bits meet this criterion, returns @size.
+ */
+static inline
+unsigned long find_first_one_and_zero_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_next_bit(addr1, addr2, size, 0, 0UL, ~0UL, 0);
+}
+#endif
+
+#ifndef find_first_zero_and_zero_bit
+/**
+ * find_first_zero_and_zero_bit - find the first bit which is zero in addr1 and addr2 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 first bit cleared in addr1 and addr2
+ * If no corresponding bits meet this criterion, returns @size.
+ */
+static inline
+unsigned long find_first_zero_and_zero_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_next_bit(addr1, addr2, size, 0, ~0UL, ~0UL, 0);
+}
+#endif
+
#ifndef find_last_bit
/**
* find_last_bit - find the last set bit in a memory region
--
2.25.1
next prev parent reply other threads:[~2022-09-22 11:05 UTC|newest]
Thread overview: 42+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-22 10:59 [PATCH v4 00/25] RSEQ node id and virtual cpu id extensions Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 01/25] rseq: Introduce feature size and alignment ELF auxiliary vector entries Mathieu Desnoyers
2022-10-10 12:42 ` Florian Weimer
2022-10-17 16:09 ` Mathieu Desnoyers
2022-10-17 17:32 ` Mathieu Desnoyers
2022-10-18 15:34 ` Florian Weimer
2022-10-18 19:00 ` Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 02/25] rseq: Introduce extensible rseq ABI Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 03/25] rseq: Extend struct rseq with numa node id Mathieu Desnoyers
2022-09-23 11:13 ` Peter Zijlstra
2022-09-23 13:00 ` Mathieu Desnoyers
2022-09-23 13:09 ` [PATCH v4.1 03/25 1/1] " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 04/25] selftests/rseq: Use ELF auxiliary vector for extensible rseq Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 05/25] selftests/rseq: Implement rseq numa node id field selftest Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 06/25] lib: Invert _find_next_bit source arguments Mathieu Desnoyers
2022-09-27 8:04 ` kernel test robot
2022-09-22 10:59 ` Mathieu Desnoyers [this message]
2022-09-22 10:59 ` [PATCH v4 08/25] cpumask: Implement cpumask_{first,next}_{zero,one}_and_zero Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 09/25] sched: Introduce per memory space current virtual cpu id Mathieu Desnoyers
2022-09-27 13:43 ` [PATCH v4.1 " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 10/25] rseq: Extend struct rseq with per memory space vcpu id Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 11/25] selftests/rseq: Remove RSEQ_SKIP_FASTPATH code Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 12/25] selftests/rseq: Implement rseq vm_vcpu_id field support Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 13/25] selftests/rseq: x86: Template memory ordering and percpu access mode Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 14/25] selftests/rseq: arm: " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 15/25] selftests/rseq: arm64: " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 16/25] selftests/rseq: mips: " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 17/25] selftests/rseq: ppc: " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 18/25] selftests/rseq: s390: " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 19/25] selftests/rseq: riscv: " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 20/25] selftests/rseq: Implement basic percpu ops vm_vcpu_id test Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 21/25] selftests/rseq: Implement parametrized " Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 22/25] selftests/rseq: x86: Implement rseq_load_u32_u32 Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 23/25] selftests/rseq: Implement numa node id vs vm_vcpu_id invariant test Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 24/25] selftests/rseq: parametrized test: Report/abort on negative cpu id Mathieu Desnoyers
2022-09-22 10:59 ` [PATCH v4 25/25] tracing/rseq: Add mm_vcpu_id field to rseq_update Mathieu Desnoyers
2022-09-22 15:14 ` kernel test robot
2022-09-22 15:33 ` [PATCH v4.1 " Mathieu Desnoyers
2022-09-23 9:55 ` [PATCH v4 " kernel test robot
[not found] ` <e753568d-599c-d81a-8456-085bbbb0264d@efficios.com>
[not found] ` <CAEE+ybnLUHjU5-dWcWgcWiq-AM4ocquSbZ=PWiuexEsPB8P5Gw@mail.gmail.com>
2022-09-23 13:46 ` [PATCH v4 00/25] RSEQ node id and virtual cpu id extensions Mathieu Desnoyers
2022-10-10 13:04 ` Florian Weimer
2022-10-17 16:05 ` Mathieu Desnoyers
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20220922105941.237830-8-mathieu.desnoyers@efficios.com \
--to=mathieu.desnoyers@efficios.com \
--cc=David.Laight@ACULAB.COM \
--cc=alexander@mihalicyn.com \
--cc=boqun.feng@gmail.com \
--cc=brauner@kernel.org \
--cc=carlos@redhat.com \
--cc=fw@deneb.enyo.de \
--cc=hpa@zytor.com \
--cc=linux-api@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=pjt@google.com \
--cc=posk@posk.io \
--cc=tglx@linutronix.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).