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

Message-Id: <20250304160844.75373-1-steve.wahl@hpe.com>
Date: Tue,  4 Mar 2025 10:08:42 -0600
From: Steve Wahl <steve.wahl@....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, 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: [PATCH v4 0/2] Improving topology_span_sane

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.

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

-- 
2.26.2