[PATCH v2 0/4] cpumask: add missing API and simplify cpumask_any_housekeeping()

[PATCH v2 0/4] cpumask: add missing API and simplify cpumask_any_housekeeping()

[Yury Norov]

From: Yury Norov [NVIDIA] <yury.norov@gmail.com>

cpumask library missed some flavors of cpumask_any_but(), which makes
users to workaround it by using less efficient cpumask_nth() functions

This series adds missing cpumask_any_andnot_but() and makes
cpumask_any_but() understanding the RESCTRL_PICK_ANY_CPU hint.
This simplifies cpumask_any_housekeeping() significantly.

v1: https://lore.kernel.org/all/20250407153856.133093-1-yury.norov@gmail.com/
v2:
 - switch cpumask_any_but() functions to signed type for CPU (Reinette);
 - change name for the new function to cpumask_any_andnot_but() (James);
 - drop O(n*log(n)) comment. cpumask_nth() is slower, but still linear.

Yury Norov [NVIDIA] (4):
  cpumask: relax cpumask_any_but()
  find: add find_first_andnot_bit()
  cpumask: add cpumask_{first,next}_andnot() API
  x86/resctrl: optimize cpumask_any_housekeeping()

 arch/x86/kernel/cpu/resctrl/internal.h | 28 +++-------
 include/linux/cpumask.h                | 75 ++++++++++++++++++++++++--
 include/linux/find.h                   | 25 +++++++++
 lib/find_bit.c                         | 11 ++++
 4 files changed, 114 insertions(+), 25 deletions(-)

-- 
2.43.0

[PATCH v2 1/4] cpumask: relax cpumask_any_but()

[Yury Norov]

From: "Yury Norov [NVIDIA]" <yury.norov@gmail.com>

Similarly to other cpumask search functions, accept -1, and consider
it as 'any cpu' hint. This helps users to avoid coding special cases.

Tested-by: James Morse <james.morse@arm.com>
Reviewed-by: James Morse <james.morse@arm.com>
Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/cpumask.h | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index beff4d26e605..0c57b9892d80 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -413,14 +413,18 @@ unsigned int cpumask_next_wrap(int n, const struct cpumask *src)
  * @cpu: the cpu to ignore.
  *
  * Often used to find any cpu but smp_processor_id() in a mask.
+ * If @cpu == -1, the function is equivalent to cpumask_any().
  * Return: >= nr_cpu_ids if no cpus set.
  */
 static __always_inline
-unsigned int cpumask_any_but(const struct cpumask *mask, unsigned int cpu)
+unsigned int cpumask_any_but(const struct cpumask *mask, int cpu)
 {
 	unsigned int i;
 
-	cpumask_check(cpu);
+	/* -1 is a legal arg here. */
+	if (cpu != -1)
+		cpumask_check(cpu);
+
 	for_each_cpu(i, mask)
 		if (i != cpu)
 			break;
@@ -433,16 +437,20 @@ unsigned int cpumask_any_but(const struct cpumask *mask, unsigned int cpu)
  * @mask2: the second input cpumask
  * @cpu: the cpu to ignore
  *
+ * If @cpu == -1, the function is equivalent to cpumask_any_and().
  * Returns >= nr_cpu_ids if no cpus set.
  */
 static __always_inline
 unsigned int cpumask_any_and_but(const struct cpumask *mask1,
 				 const struct cpumask *mask2,
-				 unsigned int cpu)
+				 int cpu)
 {
 	unsigned int i;
 
-	cpumask_check(cpu);
+	/* -1 is a legal arg here. */
+	if (cpu != -1)
+		cpumask_check(cpu);
+
 	i = cpumask_first_and(mask1, mask2);
 	if (i != cpu)
 		return i;
-- 
2.43.0

[PATCH v2 2/4] find: add find_first_andnot_bit()

[Yury Norov]

From: "Yury Norov [NVIDIA]" <yury.norov@gmail.com>

The function helps to implement cpumask_andnot() APIs.

Tested-by: James Morse <james.morse@arm.com>
Reviewed-by: James Morse <james.morse@arm.com>
Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/find.h | 25 +++++++++++++++++++++++++
 lib/find_bit.c       | 11 +++++++++++
 2 files changed, 36 insertions(+)

diff --git a/include/linux/find.h b/include/linux/find.h
index 68685714bc18..5a2c267ea7f9 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -29,6 +29,8 @@ unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const unsign
 					unsigned long n);
 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
 					 const unsigned long *addr2, unsigned long size);
+unsigned long _find_first_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
+				 unsigned long size);
 unsigned long _find_first_and_and_bit(const unsigned long *addr1, const unsigned long *addr2,
 				      const unsigned long *addr3, unsigned long size);
 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
@@ -347,6 +349,29 @@ unsigned long find_first_and_bit(const unsigned long *addr1,
 }
 #endif
 
+/**
+ * find_first_andnot_bit - find the first bit set in 1st memory region and unset in 2nd
+ * @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 set bit
+ * If no bits are set, returns >= @size.
+ */
+static __always_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);
+}
+
 /**
  * find_first_and_and_bit - find the first set bit in 3 memory regions
  * @addr1: The first address to base the search on
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 0836bb3d76c5..06b6342aa3ae 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -116,6 +116,17 @@ unsigned long _find_first_and_bit(const unsigned long *addr1,
 EXPORT_SYMBOL(_find_first_and_bit);
 #endif
 
+/*
+ * Find the first bit set in 1st memory region and unset in 2nd.
+ */
+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);
+
 /*
  * Find the first set bit in three memory regions.
  */
-- 
2.43.0

[PATCH v2 3/4] cpumask: add cpumask_{first,next}_andnot() API

[Yury Norov]

From: "Yury Norov [NVIDIA]" <yury.norov@gmail.com>

With the lack of the functions, client code has to abuse less efficient
cpumask_nth().

Tested-by: James Morse <james.morse@arm.com>
Reviewed-by: James Morse <james.morse@arm.com>
Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/cpumask.h | 59 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 0c57b9892d80..7ae80a7ca81e 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -178,6 +178,19 @@ unsigned int cpumask_first_and(const struct cpumask *srcp1, const struct cpumask
 	return find_first_and_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), small_cpumask_bits);
 }
 
+/**
+ * cpumask_first_andnot - return the first cpu from *srcp1 & ~*srcp2
+ * @srcp1: the first input
+ * @srcp2: the second input
+ *
+ * Return: >= nr_cpu_ids if no such cpu found.
+ */
+static __always_inline
+unsigned int cpumask_first_andnot(const struct cpumask *srcp1, const struct cpumask *srcp2)
+{
+	return find_first_andnot_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), small_cpumask_bits);
+}
+
 /**
  * cpumask_first_and_and - return the first cpu from *srcp1 & *srcp2 & *srcp3
  * @srcp1: the first input
@@ -284,6 +297,25 @@ unsigned int cpumask_next_and(int n, const struct cpumask *src1p,
 		small_cpumask_bits, n + 1);
 }
 
+/**
+ * cpumask_next_andnot - get the next cpu in *src1p & ~*src2p
+ * @n: the cpu prior to the place to search (i.e. return will be > @n)
+ * @src1p: the first cpumask pointer
+ * @src2p: the second cpumask pointer
+ *
+ * Return: >= nr_cpu_ids if no further cpus set in both.
+ */
+static __always_inline
+unsigned int cpumask_next_andnot(int n, const struct cpumask *src1p,
+				 const struct cpumask *src2p)
+{
+	/* -1 is a legal arg here. */
+	if (n != -1)
+		cpumask_check(n);
+	return find_next_andnot_bit(cpumask_bits(src1p), cpumask_bits(src2p),
+		small_cpumask_bits, n + 1);
+}
+
 /**
  * cpumask_next_and_wrap - get the next cpu in *src1p & *src2p, starting from
  *			   @n+1. If nothing found, wrap around and start from
@@ -458,6 +490,33 @@ unsigned int cpumask_any_and_but(const struct cpumask *mask1,
 	return cpumask_next_and(cpu, mask1, mask2);
 }
 
+/**
+ * cpumask_any_andnot_but - pick an arbitrary cpu from *mask1 & ~*mask2, but not this one.
+ * @mask1: the first input cpumask
+ * @mask2: the second input cpumask
+ * @cpu: the cpu to ignore
+ *
+ * If @cpu == -1, the function returns the first matching cpu.
+ * Returns >= nr_cpu_ids if no cpus set.
+ */
+static __always_inline
+unsigned int cpumask_any_andnot_but(const struct cpumask *mask1,
+				    const struct cpumask *mask2,
+				    int cpu)
+{
+	unsigned int i;
+
+	/* -1 is a legal arg here. */
+	if (cpu != -1)
+		cpumask_check(cpu);
+
+	i = cpumask_first_andnot(mask1, mask2);
+	if (i != cpu)
+		return i;
+
+	return cpumask_next_andnot(cpu, mask1, mask2);
+}
+
 /**
  * cpumask_nth - get the Nth cpu in a cpumask
  * @srcp: the cpumask pointer
-- 
2.43.0

[PATCH v2 4/4] x86/resctrl: Optimize cpumask_any_housekeeping()

[Yury Norov]

From: "Yury Norov [NVIDIA]" <yury.norov@gmail.com>

With the lack of cpumask_any_andnot_but(), cpumask_any_housekeeping()
has to abuse cpumask_nth() functions.

Update cpumask_any_housekeeping() to use the new cpumask_any_but()
and cpumask_any_andnot_but(). These two functions understand
RESCTRL_PICK_ANY_CPU, which simplifies cpumask_any_housekeeping()
significantly.

Tested-by: James Morse <james.morse@arm.com>
Reviewed-by: James Morse <james.morse@arm.com>
Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 arch/x86/kernel/cpu/resctrl/internal.h | 28 +++++++-------------------
 1 file changed, 7 insertions(+), 21 deletions(-)

diff --git a/arch/x86/kernel/cpu/resctrl/internal.h b/arch/x86/kernel/cpu/resctrl/internal.h
index eaae99602b61..25b61e466715 100644
--- a/arch/x86/kernel/cpu/resctrl/internal.h
+++ b/arch/x86/kernel/cpu/resctrl/internal.h
@@ -47,30 +47,16 @@
 static inline unsigned int
 cpumask_any_housekeeping(const struct cpumask *mask, int exclude_cpu)
 {
-	unsigned int cpu, hk_cpu;
-
-	if (exclude_cpu == RESCTRL_PICK_ANY_CPU)
-		cpu = cpumask_any(mask);
-	else
-		cpu = cpumask_any_but(mask, exclude_cpu);
-
-	/* Only continue if tick_nohz_full_mask has been initialized. */
-	if (!tick_nohz_full_enabled())
-		return cpu;
-
-	/* If the CPU picked isn't marked nohz_full nothing more needs doing. */
-	if (cpu < nr_cpu_ids && !tick_nohz_full_cpu(cpu))
-		return cpu;
+	unsigned int cpu;
 
 	/* Try to find a CPU that isn't nohz_full to use in preference */
-	hk_cpu = cpumask_nth_andnot(0, mask, tick_nohz_full_mask);
-	if (hk_cpu == exclude_cpu)
-		hk_cpu = cpumask_nth_andnot(1, mask, tick_nohz_full_mask);
-
-	if (hk_cpu < nr_cpu_ids)
-		cpu = hk_cpu;
+	if (tick_nohz_full_enabled()) {
+		cpu = cpumask_any_andnot_but(mask, tick_nohz_full_mask, exclude_cpu);
+		if (cpu < nr_cpu_ids)
+			return cpu;
+	}
 
-	return cpu;
+	return cpumask_any_but(mask, exclude_cpu);
 }
 
 struct rdt_fs_context {
-- 
2.43.0

Re: [PATCH v2 0/4] cpumask: add missing API and simplify cpumask_any_housekeeping()

[Reinette Chatre]

Hi Yury,

On 4/27/25 11:52 AM, Yury Norov wrote:
> From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> 
> cpumask library missed some flavors of cpumask_any_but(), which makes
> users to workaround it by using less efficient cpumask_nth() functions
> 
> This series adds missing cpumask_any_andnot_but() and makes
> cpumask_any_but() understanding the RESCTRL_PICK_ANY_CPU hint.
> This simplifies cpumask_any_housekeeping() significantly.
> 
> v1: https://lore.kernel.org/all/20250407153856.133093-1-yury.norov@gmail.com/
> v2:
>  - switch cpumask_any_but() functions to signed type for CPU (Reinette);
>  - change name for the new function to cpumask_any_andnot_but() (James);
>  - drop O(n*log(n)) comment. cpumask_nth() is slower, but still linear.
> 
> Yury Norov [NVIDIA] (4):
>   cpumask: relax cpumask_any_but()
>   find: add find_first_andnot_bit()
>   cpumask: add cpumask_{first,next}_andnot() API
>   x86/resctrl: optimize cpumask_any_housekeeping()

Reviewed-by: Reinette Chatre <reinette.chatre@intel.com>

Does anything in your "bitmap-for-next" branch depend on this
series? If not, would you be ok if this series goes upstream
via tip (pending confirmation from tip maintainers) to make
for smoother upstream of resctrl patches that touch the same area?

Thank you very much for doing this work. 

Reinette

Re: [PATCH v2 0/4] cpumask: add missing API and simplify cpumask_any_housekeeping()

[Yury Norov]

On Thu, May 01, 2025 at 03:06:18PM -0700, Reinette Chatre wrote:
> Hi Yury,
> 
> On 4/27/25 11:52 AM, Yury Norov wrote:
> > From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> > 
> > cpumask library missed some flavors of cpumask_any_but(), which makes
> > users to workaround it by using less efficient cpumask_nth() functions
> > 
> > This series adds missing cpumask_any_andnot_but() and makes
> > cpumask_any_but() understanding the RESCTRL_PICK_ANY_CPU hint.
> > This simplifies cpumask_any_housekeeping() significantly.
> > 
> > v1: https://lore.kernel.org/all/20250407153856.133093-1-yury.norov@gmail.com/
> > v2:
> >  - switch cpumask_any_but() functions to signed type for CPU (Reinette);
> >  - change name for the new function to cpumask_any_andnot_but() (James);
> >  - drop O(n*log(n)) comment. cpumask_nth() is slower, but still linear.
> > 
> > Yury Norov [NVIDIA] (4):
> >   cpumask: relax cpumask_any_but()
> >   find: add find_first_andnot_bit()
> >   cpumask: add cpumask_{first,next}_andnot() API
> >   x86/resctrl: optimize cpumask_any_housekeeping()
> 
> Reviewed-by: Reinette Chatre <reinette.chatre@intel.com>
> 
> Does anything in your "bitmap-for-next" branch depend on this
> series? If not, would you be ok if this series goes upstream
> via tip (pending confirmation from tip maintainers) to make
> for smoother upstream of resctrl patches that touch the same area?
 
Sure, please take it with the resctrl material.

> Thank you very much for doing this work. 

Thanks for warm words. :)

Re: [PATCH v2 0/4] cpumask: add missing API and simplify cpumask_any_housekeeping()

[Reinette Chatre]

Dear x86 Maintainers,

On 5/2/25 8:32 AM, Yury Norov wrote:
> On Thu, May 01, 2025 at 03:06:18PM -0700, Reinette Chatre wrote:
>> Hi Yury,
>>
>> On 4/27/25 11:52 AM, Yury Norov wrote:
>>> From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
>>>
>>> cpumask library missed some flavors of cpumask_any_but(), which makes
>>> users to workaround it by using less efficient cpumask_nth() functions
>>>
>>> This series adds missing cpumask_any_andnot_but() and makes
>>> cpumask_any_but() understanding the RESCTRL_PICK_ANY_CPU hint.
>>> This simplifies cpumask_any_housekeeping() significantly.
>>>
>>> v1: https://lore.kernel.org/all/20250407153856.133093-1-yury.norov@gmail.com/
>>> v2:
>>>  - switch cpumask_any_but() functions to signed type for CPU (Reinette);
>>>  - change name for the new function to cpumask_any_andnot_but() (James);
>>>  - drop O(n*log(n)) comment. cpumask_nth() is slower, but still linear.
>>>
>>> Yury Norov [NVIDIA] (4):
>>>   cpumask: relax cpumask_any_but()
>>>   find: add find_first_andnot_bit()
>>>   cpumask: add cpumask_{first,next}_andnot() API
>>>   x86/resctrl: optimize cpumask_any_housekeeping()
>>
>> Reviewed-by: Reinette Chatre <reinette.chatre@intel.com>
>>
>> Does anything in your "bitmap-for-next" branch depend on this
>> series? If not, would you be ok if this series goes upstream
>> via tip (pending confirmation from tip maintainers) to make
>> for smoother upstream of resctrl patches that touch the same area?
>  
> Sure, please take it with the resctrl material.
> 

Could you please consider this work for inclusion into tip's
x86/cache branch? 

Thank you very much.

Reinette