Received-SPF: pass (google.com: domain of linux-kernel+bounces-143356-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1;
From: weilin.wang@intel.com
To: weilin.wang@intel.com,
	Ian Rogers <irogers@google.com>,
	Kan Liang <kan.liang@linux.intel.com>,
	Namhyung Kim <namhyung@kernel.org>,
	Arnaldo Carvalho de Melo <acme@kernel.org>,
	Peter Zijlstra <peterz@infradead.org>,
	Ingo Molnar <mingo@redhat.com>,
	Alexander Shishkin <alexander.shishkin@linux.intel.com>,
	Jiri Olsa <jolsa@kernel.org>,
	Adrian Hunter <adrian.hunter@intel.com>
Cc: linux-perf-users@vger.kernel.org,
	linux-kernel@vger.kernel.org,
	Perry Taylor <perry.taylor@intel.com>,
	Samantha Alt <samantha.alt@intel.com>,
	Caleb Biggers <caleb.biggers@intel.com>
Subject: [RFC PATCH v5 04/16] find_bit: add _find_last_and_bit() to support finding the most significant set bit
Date: Fri, 12 Apr 2024 14:07:44 -0700
Message-ID: <20240412210756.309828-5-weilin.wang@intel.com>
In-Reply-To: <20240412210756.309828-1-weilin.wang@intel.com>
References: <20240412210756.309828-1-weilin.wang@intel.com>
Precedence: bulk
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit

From: Weilin Wang <weilin.wang@intel.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.

Reviewed-by: Ian Rogers <irogers@google.com>
Signed-off-by: Weilin Wang <weilin.wang@intel.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..a84817d80c46 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
-- 
2.42.0