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

[PATCH 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.

Yury Norov (4):
  relax cpumask_any_but()
  find: add find_first_andnot_bit()
  cpumask_first_andnot
  resctrl

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

-- 
2.43.0

[PATCH 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.

Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/cpumask.h | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index beff4d26e605..0f816092c891 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -413,6 +413,7 @@ 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
@@ -420,7 +421,10 @@ unsigned int cpumask_any_but(const struct cpumask *mask, unsigned 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,6 +437,7 @@ 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
@@ -442,7 +447,10 @@ unsigned int cpumask_any_and_but(const struct cpumask *mask1,
 {
 	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 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.

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..d1578cfb667c 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 matched 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 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().

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 0f816092c891..9067c3411cd0 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_andnot_any_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_andnot_any_but(const struct cpumask *mask1,
+				    const struct cpumask *mask2,
+				    unsigned 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 4/4] x86/resctrl: optimize cpumask_any_housekeeping()

[Yury Norov]

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

With the lack of cpumask_andnot_any_but(), users have to abuse
cpumask_nth() functions which are O(N*log(N)), comparing to O(N)
for cpumask_any().

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

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 20c898f09b7e..1db02bab9743 100644
--- a/arch/x86/kernel/cpu/resctrl/internal.h
+++ b/arch/x86/kernel/cpu/resctrl/internal.h
@@ -71,30 +71,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_andnot_any_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 0/4] cpumask: add missing API and simplify cpumask_any_housekeeping()

[Yury Norov]

Ping?

On Mon, Apr 07, 2025 at 11:38:51AM -0400, 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.
> 
> Yury Norov (4):
>   relax cpumask_any_but()
>   find: add find_first_andnot_bit()
>   cpumask_first_andnot
>   resctrl
> 
>  arch/x86/kernel/cpu/resctrl/internal.h | 28 +++-------
>  include/linux/cpumask.h                | 71 +++++++++++++++++++++++++-
>  include/linux/find.h                   | 25 +++++++++
>  lib/find_bit.c                         | 11 ++++
>  4 files changed, 112 insertions(+), 23 deletions(-)
> 
> -- 
> 2.43.0

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

[Reinette Chatre]

Hi Yury,

On 4/22/25 6:50 AM, Yury Norov wrote:
> Ping?

From the resctrl side this looks promising and I have been meaning to review
it with more detail. It looks promising because, apart from simplifying the
resctrl parts, it also looks like it may help to address some new resctrl [1]
requirements.

Thank you.

Reinette

[1] https://lore.kernel.org/lkml/da51ba61-4ff0-4db4-a55f-743f6a3ea7da@intel.com/

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

[Reinette Chatre]

+James

Hi Yury,

On 4/7/25 8:38 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.
> 
> Yury Norov (4):
>   relax cpumask_any_but()
>   find: add find_first_andnot_bit()
>   cpumask_first_andnot
>   resctrl

(sidenote: above list of patch subjects do not match the series)

Thank you very much for doing this work. This simplifies resctrl code
significantly. I do have a couple of comments that you will find in
the individual patches. 

Regarding upstreaming I would like to propose that the upstreaming of
this work be split so that resctrl changes do not go upstream
via separate trees during this cycle. I am ok with delaying the resctrl
portion of this work for a cycle. This is because we hope to include a
huge change [1] to resctrl that includes the code modified in this series.
Having these two changes meet during merge window will be inconvenient
for maintainers involved. If you require a user to upstream these new
helpers then another possibility is to upstream this work via the tip repo
if that is ok with x86 maintainers so that that huge resctrl patch is created on
top if this work.

Reinette

[1] https://lore.kernel.org/lkml/20250411164229.23413-18-james.morse@arm.com/

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

[Reinette Chatre]

Hi Yury,

On 4/7/25 8:38 AM, Yury Norov wrote:
> 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.
> 
> Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> ---
>  include/linux/cpumask.h | 12 ++++++++++--
>  1 file changed, 10 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> index beff4d26e605..0f816092c891 100644
> --- a/include/linux/cpumask.h
> +++ b/include/linux/cpumask.h
> @@ -413,6 +413,7 @@ 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().

Now that -1 is a legal argument, should the "cpu" parameter be of "int" type (instead of
"unsigned int")?


>   * Return: >= nr_cpu_ids if no cpus set.
>   */
>  static __always_inline
> @@ -420,7 +421,10 @@ unsigned int cpumask_any_but(const struct cpumask *mask, unsigned 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,6 +437,7 @@ 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
> @@ -442,7 +447,10 @@ unsigned int cpumask_any_and_but(const struct cpumask *mask1,

Same question here regarding type of "cpu" parameter.

>  {
>  	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;

Reinette

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

[Reinette Chatre]

Hi Yury,

On 4/7/25 8:38 AM, Yury Norov wrote:
> From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> 
> The function helps to implement cpumask_andnot() APIs.
> 
> 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..d1578cfb667c 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 matched bit
> + * If no bits are set, returns >= @size.

Should this be "If no bits are set, returns @size." to match similar document
snippets as well as what the code does?

I am not familiar with the customs of this area but I did notice that
this patch triggers some checkpatch.pl warnings about alignment not
matching open parenthesis ... but looking at the existing content of this
file this custom does not seem to apply here.

Reinette

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

[Reinette Chatre]

Hi Yury,

On 4/7/25 8:38 AM, Yury Norov wrote:

...

> @@ -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)

Looks like the custom followed here is to name parameter that can have
-1 as value "n" and let it have type "int". Should this also apply to
cpumask_andnot_any_but(), cpumask_any_but(), and cpumask_any_and_but()
modified/introduced in this series?

> +{
> +	/* -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_andnot_any_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_andnot_any_but(const struct cpumask *mask1,
> +				    const struct cpumask *mask2,
> +				    unsigned int cpu)

Since -1 is legal argument I expect "cpu" to be int.

> +{
> +	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

Reinette

Re: [PATCH 4/4] x86/resctrl: optimize cpumask_any_housekeeping()

[Reinette Chatre]

Hi Yury,

On 4/7/25 8:38 AM, Yury Norov wrote:
> From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> 
> With the lack of cpumask_andnot_any_but(), users have to abuse
> cpumask_nth() functions which are O(N*log(N)), comparing to O(N)
> for cpumask_any().
> 
> This series adds missing cpumask_andnot_any_but() and makes
> cpumask_any_but() understanding the RESCTRL_PICK_ANY_CPU hint.
> This simplifies cpumask_any_housekeeping() significantly.

The "This series ..." language is more appropriate for the cover
letter. 

This changelog could be something like:

	With the lack of cpumask_andnot_any_but(), cpumask_any_housekeeping()
	abused cpumask_nth() functions which are O(N*log(N)), compared to O(N)                
	for cpumask_any().                                                              
                                                                                
	Update cpumask_any_housekeeping() to use the new cpumask_any_but() and          
	cpumask_andnot_any_but(). These two functions understand RESCTRL_PICK_ANY_CPU   
	and simplifies cpumask_any_housekeeping() significantly.                        


Also, could you please have the subject of this patch start with an
upper case: "x86/resctrl: Optimize cpumask_any_housekeeping()"?

> 
> 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 20c898f09b7e..1db02bab9743 100644
> --- a/arch/x86/kernel/cpu/resctrl/internal.h
> +++ b/arch/x86/kernel/cpu/resctrl/internal.h
> @@ -71,30 +71,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_andnot_any_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 {

This looks good to me. Thank you very much for doing this.

Reinette

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

[Yury Norov]

On Wed, Apr 23, 2025 at 02:28:03PM -0700, Reinette Chatre wrote:
> Hi Yury,
> 
> On 4/7/25 8:38 AM, Yury Norov wrote:
> > 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.
> > 
> > Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> > ---
> >  include/linux/cpumask.h | 12 ++++++++++--
> >  1 file changed, 10 insertions(+), 2 deletions(-)
> > 
> > diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> > index beff4d26e605..0f816092c891 100644
> > --- a/include/linux/cpumask.h
> > +++ b/include/linux/cpumask.h
> > @@ -413,6 +413,7 @@ 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().
> 
> Now that -1 is a legal argument, should the "cpu" parameter be of "int" type (instead of
> "unsigned int")?

Yes, you're right. Need to fix this.

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

[Yury Norov]

On Wed, Apr 23, 2025 at 02:28:26PM -0700, Reinette Chatre wrote:
> Hi Yury,
> 
> On 4/7/25 8:38 AM, Yury Norov wrote:
> > From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> > 
> > The function helps to implement cpumask_andnot() APIs.
> > 
> > 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..d1578cfb667c 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 matched bit
> > + * If no bits are set, returns >= @size.
> 
> Should this be "If no bits are set, returns @size." to match similar document
> snippets as well as what the code does?
> 
> I am not familiar with the customs of this area but I did notice that
> this patch triggers some checkpatch.pl warnings about alignment not
> matching open parenthesis ... but looking at the existing content of this
> file this custom does not seem to apply here.

It was a really unclever decision to make find_bit() API returning
the size exactly, because this ends up with a few extra instructions
that we can avoid. For example, in FIND_FIRST_BIT() we have to return

        min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz);

instead of just

        idx * BITS_PER_LONG + __ffs(MUNGE(val)

Unfortunately, the existing codebase relies on this overly strict
guarantee. For the new API, I encourage people to guarantee '>= size',
not '== size'. There's no difference from practical perspective. But
if one day somebody will decide to clean this up, there will be less 
burden to rework.

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

[Yury Norov]

On Wed, Apr 23, 2025 at 02:28:38PM -0700, Reinette Chatre wrote:
> Hi Yury,
> 
> On 4/7/25 8:38 AM, Yury Norov wrote:
> 
> ...
> 
> > @@ -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)
> 
> Looks like the custom followed here is to name parameter that can have
> -1 as value "n" and let it have type "int". Should this also apply to
> cpumask_andnot_any_but(), cpumask_any_but(), and cpumask_any_and_but()
> modified/introduced in this series?
> 
> > +{
> > +	/* -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_andnot_any_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_andnot_any_but(const struct cpumask *mask1,
> > +				    const struct cpumask *mask2,
> > +				    unsigned int cpu)
> 
> Since -1 is legal argument I expect "cpu" to be int.

Yes, you're right. I overlooked this. Will fix in v2

Re: [PATCH 4/4] x86/resctrl: optimize cpumask_any_housekeeping()

[Yury Norov]

On Wed, Apr 23, 2025 at 02:29:48PM -0700, Reinette Chatre wrote:
> Hi Yury,
> 
> On 4/7/25 8:38 AM, Yury Norov wrote:
> > From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> > 
> > With the lack of cpumask_andnot_any_but(), users have to abuse
> > cpumask_nth() functions which are O(N*log(N)), comparing to O(N)
> > for cpumask_any().
> > 
> > This series adds missing cpumask_andnot_any_but() and makes
> > cpumask_any_but() understanding the RESCTRL_PICK_ANY_CPU hint.
> > This simplifies cpumask_any_housekeeping() significantly.
> 
> The "This series ..." language is more appropriate for the cover
> letter. 
> 
> This changelog could be something like:
> 
> 	With the lack of cpumask_andnot_any_but(), cpumask_any_housekeeping()
> 	abused cpumask_nth() functions which are O(N*log(N)), compared to O(N)                
> 	for cpumask_any().                                                              
>                                                                                 
> 	Update cpumask_any_housekeeping() to use the new cpumask_any_but() and          
> 	cpumask_andnot_any_but(). These two functions understand RESCTRL_PICK_ANY_CPU   
> 	and simplifies cpumask_any_housekeeping() significantly.                        
> 
> 
> Also, could you please have the subject of this patch start with an
> upper case: "x86/resctrl: Optimize cpumask_any_housekeeping()"?

Yep, I'll reword.

> > 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 20c898f09b7e..1db02bab9743 100644
> > --- a/arch/x86/kernel/cpu/resctrl/internal.h
> > +++ b/arch/x86/kernel/cpu/resctrl/internal.h
> > @@ -71,30 +71,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_andnot_any_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 {
> 
> This looks good to me. Thank you very much for doing this.

Thanks for the feedback! I'll send v2 before the end of week.

Thanks,
Yury

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

[Yury Norov]

On Wed, Apr 23, 2025 at 02:27:46PM -0700, Reinette Chatre wrote:
> +James
> 
> Hi Yury,
> 
> On 4/7/25 8:38 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.
> > 
> > Yury Norov (4):
> >   relax cpumask_any_but()
> >   find: add find_first_andnot_bit()
> >   cpumask_first_andnot
> >   resctrl
> 
> (sidenote: above list of patch subjects do not match the series)
> 
> Thank you very much for doing this work. This simplifies resctrl code
> significantly. I do have a couple of comments that you will find in
> the individual patches. 

Sure, glad to see you like it.
 
> Regarding upstreaming I would like to propose that the upstreaming of
> this work be split so that resctrl changes do not go upstream
> via separate trees during this cycle. I am ok with delaying the resctrl
> portion of this work for a cycle. This is because we hope to include a
> huge change [1] to resctrl that includes the code modified in this series.
> Having these two changes meet during merge window will be inconvenient
> for maintainers involved. If you require a user to upstream these new
> helpers then another possibility is to upstream this work via the tip repo
> if that is ok with x86 maintainers so that that huge resctrl patch is created on
> top if this work.
> 
> Reinette
> 
> [1] https://lore.kernel.org/lkml/20250411164229.23413-18-james.morse@arm.com/

I can move all the patches with my branch (bitmap-for-next) if you ack
the restcl part, or let resctl folks (you, I guess) take over the series.
Or we can split it, so I'll move generic part myself, and you'll move
the last patch.

Thanks,
Yury

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

[James Morse]

Hi Yury,

On 07/04/2025 16:38, Yury Norov wrote:
> From: Yury Norov [NVIDIA] <yury.norov@gmail.com>
> 
> With the lack of the functions, client code has to abuse less efficient
> cpumask_nth().


> diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> index 0f816092c891..9067c3411cd0 100644
> --- a/include/linux/cpumask.h
> +++ b/include/linux/cpumask.h

> @@ -458,6 +490,33 @@ unsigned int cpumask_any_and_but(const struct cpumask *mask1,
>  	return cpumask_next_and(cpu, mask1, mask2);
>  }
>  
> +/**
> + * cpumask_andnot_any_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_andnot_any_but(const struct cpumask *mask1,
> +				    const struct cpumask *mask2,
> +				    unsigned int cpu)

Nit: Shouldn't this be named cpumask_any_andnot_but()?
It's any cpu from the first-mask, then 'andnot' the second. This fits with the other
instances of this, e.g. cpumask_any_and_but().


> +{
> +	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);
> +}


Thanks,

James

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

[James Morse]

Hi Yury,

On 07/04/2025 16:38, 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.


For the series - with the unsigned/int thing Reinette pointed out fixed:
Tested-by: James Morse <james.morse@arm.com>
Reviewed-by: James Morse <james.morse@arm.com>


Thanks,

James

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

[James Morse]

Hi Reinette, Yury,

On 24/04/2025 04:11, Yury Norov wrote:
> On Wed, Apr 23, 2025 at 02:27:46PM -0700, Reinette Chatre wrote:
>> On 4/7/25 8:38 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.
>>>
>>> Yury Norov (4):
>>>   relax cpumask_any_but()
>>>   find: add find_first_andnot_bit()
>>>   cpumask_first_andnot
>>>   resctrl
>>
>> (sidenote: above list of patch subjects do not match the series)
>>
>> Thank you very much for doing this work. This simplifies resctrl code
>> significantly. I do have a couple of comments that you will find in
>> the individual patches. 
> 
> Sure, glad to see you like it.
>  
>> Regarding upstreaming I would like to propose that the upstreaming of
>> this work be split so that resctrl changes do not go upstream
>> via separate trees during this cycle. I am ok with delaying the resctrl
>> portion of this work for a cycle. This is because we hope to include a
>> huge change [1] to resctrl that includes the code modified in this series.
>> Having these two changes meet during merge window will be inconvenient
>> for maintainers involved. If you require a user to upstream these new
>> helpers then another possibility is to upstream this work via the tip repo
>> if that is ok with x86 maintainers so that that huge resctrl patch is created on
>> top if this work.

> I can move all the patches with my branch (bitmap-for-next) if you ack
> the restcl part, or let resctl folks (you, I guess) take over the series.

> Or we can split it, so I'll move generic part myself, and you'll move
> the last patch.

That would mean co-ordinating the order those get merged in, which is extra work for the
relevant maintainers.

The patch that moves all the code is easy to regenerate as this series doesn't add any new
functions. Ideally any series touching resctrl in the same merge window would also go via
tip - but it would also possible to rebase onto an immutable branch. (needed if
bitmap-for-next also has dependencies/conflicts on these patches)

I think its easier for the tip folk if I rebase onto this once as/when its got all the
needed tags.


Thanks,

James