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: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <aB41j_3g4KHnoXaz@gpd3>
Date: Fri, 9 May 2025 19:04:15 +0200
From: Andrea Righi <arighi@...dia.com>
To: Yury Norov <yury.norov@...il.com>
Cc: linux-kernel@...r.kernel.org,
	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Yicong Yang <yangyicong@...ilicon.com>, Tejun Heo <tj@...nel.org>,
	Catalin Marinas <catalin.marinas@....com>
Subject: Re: [PATCH] topology: make for_each_node_with_cpus() O(N)

Hi Yury,

On Fri, May 09, 2025 at 12:20:08PM -0400, Yury Norov wrote:
> From: Yury Norov [NVIDIA] <yury.norov@...il.com>
> 
> for_each_node_with_cpus() calls nr_cpus_node() at every iteration, which
> makes it O(N^2). Kernel tracks such nodes with N_CPU record in node_states
> array. Switching to it makes for_each_node_with_cpus() O(N).

Makes sense to me.

Maybe we should mention that previously we were only considering online
nodes with CPUs assigned. Now, we can include also offline nodes with CPUs
assigned (assuming it's possible)?

Semantically speaking, since the name doesn't include "online", it seems
more logical to ignore the state of the node. And if checking the online
state is required, the user can just use node_online() within the loop.

Thanks,
-Andrea

> 
> Signed-off-by: Yury Norov [NVIDIA] <yury.norov@...il.com>
> ---
>  include/linux/nodemask.h | 1 +
>  include/linux/topology.h | 5 +----
>  2 files changed, 2 insertions(+), 4 deletions(-)
> 
> diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h
> index f0ac0633366b..1e2bdda1a0a5 100644
> --- a/include/linux/nodemask.h
> +++ b/include/linux/nodemask.h
> @@ -541,6 +541,7 @@ static __always_inline int node_random(const nodemask_t *maskp)
>  
>  #define for_each_node(node)	   for_each_node_state(node, N_POSSIBLE)
>  #define for_each_online_node(node) for_each_node_state(node, N_ONLINE)
> +#define for_each_node_with_cpus(node)	for_each_node_state(node, N_CPU)
>  
>  /*
>   * For nodemask scratch area.
> diff --git a/include/linux/topology.h b/include/linux/topology.h
> index 24e715f0f6d2..ffee6b4a071a 100644
> --- a/include/linux/topology.h
> +++ b/include/linux/topology.h
> @@ -29,6 +29,7 @@
>  
>  #include <linux/arch_topology.h>
>  #include <linux/cpumask.h>
> +#include <linux/nodemask.h>
>  #include <linux/bitops.h>
>  #include <linux/mmzone.h>
>  #include <linux/smp.h>
> @@ -39,10 +40,6 @@
>  #define nr_cpus_node(node) cpumask_weight(cpumask_of_node(node))
>  #endif
>  
> -#define for_each_node_with_cpus(node)			\
> -	for_each_online_node(node)			\
> -		if (nr_cpus_node(node))
> -
>  int arch_update_cpu_topology(void);
>  
>  /* Conform to ACPI 2.0 SLIT distance definitions */
> -- 
> 2.43.0
> 

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ