linux-kernel - Re: [PATCH v4 0/2] Improving topology_span

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <2584aac4-fceb-422c-bc35-a52f6c988c13@amd.com>
Date: Thu, 6 Mar 2025 12:16:53 +0530
From: K Prateek Nayak <kprateek.nayak@....com>
To: Steve Wahl <steve.wahl@....com>, Ingo Molnar <mingo@...hat.com>, Peter
 Zijlstra <peterz@...radead.org>, Juri Lelli <juri.lelli@...hat.com>, Vincent
 Guittot <vincent.guittot@...aro.org>, Dietmar Eggemann
	<dietmar.eggemann@....com>, Steven Rostedt <rostedt@...dmis.org>, Ben Segall
	<bsegall@...gle.com>, Mel Gorman <mgorman@...e.de>, Valentin Schneider
	<vschneid@...hat.com>, <linux-kernel@...r.kernel.org>, Vishal Chourasia
	<vishalc@...ux.ibm.com>, samir <samir@...ux.ibm.com>
CC: Naman Jain <namjain@...ux.microsoft.com>, Saurabh Singh Sengar
	<ssengar@...ux.microsoft.com>, <srivatsa@...il.mit.edu>, Michael Kelley
	<mhklinux@...look.com>, Russ Anderson <rja@....com>, Dimitri Sivanich
	<sivanich@....com>
Subject: Re: [PATCH v4 0/2] Improving topology_span_sane

Hello Steve,

On 3/4/2025 9:38 PM, Steve Wahl wrote:
> toplogy_span_sane() has an O(N^2) algorithm that takes an inordinate
> amount of time on systems with a large number of cpus.
> 
> The first patch in this series replaces the algorithm used with a O(N)
> method that should exactly duplicate the previous code's results.
> 
> The second patch simplifies the first, taking a similar amount of time
> to run, but potentially has different results than previous code under
> situations believed to not truly exist, like a CPU not being included
> in its own span.

I've tested Patch 1 individually and the whole series as is on top of
tip:sched/core and I haven't run into any issues with the optimization
on my 3rd Generation EPYC system.

Please feel free to include:

Tested-by: K Prateek Nayak <kprateek.nayak@....com>

-- 
Thanks and Regards,
Prateek

> 
> Version 1:
>    * Original patch
> 
> Version 2:
> 
>    * Adopted simplifications from K Prateek Nayak,and fixed use of
>      num_possible_cpus().
> 
> Version 3:
> 
>    * Undid the simplifications from version 2 when noticed that results
>      could differ from original code; kept num_possible_cpus() fix.
> 
> Version 4:
> 
>    * Turned the patch into a series of 2, the second re-introduces the
>      simplifications, and includes further simplification suggested by
>      Valentin Schneider in the discussion for Version 2.
> 
> Steve Wahl (2):
>    sched/topology: improve topology_span_sane speed
>    sched/topology: Refinement to topology_span_sane speedup
> 
>   kernel/sched/topology.c | 73 +++++++++++++++++++++++++++--------------
>   1 file changed, 48 insertions(+), 25 deletions(-)
>