linux-kernel - [RFC PATCH v4 04/15] find_bit: add _find_last_and_bit() to support finding the most significant set bit

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

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20240209031441.943012-5-weilin.wang@intel.com>
Date: Thu,  8 Feb 2024 19:14:30 -0800
From: weilin.wang@...el.com
To: weilin.wang@...el.com,
	Ian Rogers <irogers@...gle.com>,
	Kan Liang <kan.liang@...ux.intel.com>,
	Namhyung Kim <namhyung@...nel.org>,
	Arnaldo Carvalho de Melo <acme@...nel.org>,
	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...hat.com>,
	Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
	Jiri Olsa <jolsa@...nel.org>,
	Adrian Hunter <adrian.hunter@...el.com>
Cc: linux-perf-users@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	Perry Taylor <perry.taylor@...el.com>,
	Samantha Alt <samantha.alt@...el.com>,
	Caleb Biggers <caleb.biggers@...el.com>,
	Mark Rutland <mark.rutland@....com>
Subject: [RFC PATCH v4 04/15] find_bit: add _find_last_and_bit() to support finding the most significant set bit

From: Weilin Wang <weilin.wang@...el.com>

This function is required for more efficient PMU counter assignment.

When we use bitmap to log available PMU counters and counters that support a
given event, we want to find a most significant set bit so that we could
starting assigning counters with larger index first. This is helpful
because counters with smaller indexes usually are more generic and
support more events.

Signed-off-by: Weilin Wang <weilin.wang@...el.com>
---
 tools/include/linux/find.h | 18 ++++++++++++++++++
 tools/lib/find_bit.c       | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 51 insertions(+)

diff --git a/tools/include/linux/find.h b/tools/include/linux/find.h
index 38c0a542b0e2..fce336ec2b96 100644
--- a/tools/include/linux/find.h
+++ b/tools/include/linux/find.h
@@ -18,6 +18,8 @@ extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long si
 extern unsigned long _find_first_and_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_and_bit(const unsigned long *addr1,
+					 const unsigned long *addr2, unsigned long size);
 
 #ifndef find_next_bit
 /**
@@ -174,4 +176,20 @@ unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 }
 #endif
 
+#ifndef find_last_and_bit
+static inline
+unsigned long find_last_and_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 ? __fls(val) : size;
+	}
+
+	return _find_last_and_bit(addr1, addr2, size);
+}
+#endif
+
 #endif /*__LINUX_FIND_H_ */
diff --git a/tools/lib/find_bit.c b/tools/lib/find_bit.c
index 6a3dc167d30e..e475a7368e36 100644
--- a/tools/lib/find_bit.c
+++ b/tools/lib/find_bit.c
@@ -67,6 +67,27 @@ out:										\
 	sz;									\
 })
 
+/*
+ * Common helper for find_bit() function family
+ * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
+ * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
+ * @size: The bitmap size in bits
+ */
+#define FIND_LAST_BIT(FETCH, MUNGE, size)					\
+({										\
+	unsigned long idx, val, sz = (size);					\
+										\
+	for (idx = ((size - 1) / BITS_PER_LONG); idx >= 0; idx--) {			\
+		val = (FETCH);							\
+		if (val) {							\
+			sz = min(idx * BITS_PER_LONG + __fls(MUNGE(val)), sz);	\
+			break;							\
+		}								\
+	}									\
+										\
+	sz;									\
+})
+
 #ifndef find_first_bit
 /*
  * Find the first set bit in a memory region.
@@ -121,3 +142,15 @@ unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits
 	return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
 }
 #endif
+
+#ifndef find_last_and_bit
+/*
+ * Find the last set bit in two memory regions.
+ */
+unsigned long _find_last_and_bit(const unsigned long *addr1,
+				  const unsigned long *addr2,
+				  unsigned long size)
+{
+	return FIND_LAST_BIT(addr1[idx] & addr2[idx], /* nop */, size);
+}
+#endif
\ No newline at end of file
-- 
2.42.0