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

Message-ID: <xhsmh34fqfcv1.mognet@vschneid-thinkpadt14sgen2i.remote.csb>
Date: Thu, 06 Mar 2025 15:33:06 +0100
From: Valentin Schneider <vschneid@...hat.com>
To: Steve Wahl <steve.wahl@....com>, 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>, linux-kernel@...r.kernel.org, K Prateek Nayak
 <kprateek.nayak@....com>, 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

On 04/03/25 10:08, 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.
>

Had to hack up arch_topology.c some more to replicate the setup described
in

  ccf74128d66c ("sched/topology: Assert non-NUMA topology masks don't (partially) overlap")

but eventually go there, and it was correctly caught by topology_span_sane().

Thanks!

Reviewed-by: Valentin Schneider <vschneid@...hat.com>
Tested-by: Valentin Schneider <vschneid@...hat.com>