linux-kernel - Re: [PATCH] sched/topology: Assert non-NUMA topology masks don't (partially) overlap

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: <09b2f817-fcd9-8697-38d7-12d141a47a48@arm.com>
Date:   Thu, 16 Jan 2020 15:30:55 +0000
From:   Valentin Schneider <valentin.schneider@....com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     linux-kernel@...r.kernel.org, sudeep.holla@....com,
        prime.zeng@...ilicon.com, dietmar.eggemann@....com,
        morten.rasmussen@....com, mingo@...nel.org
Subject: Re: [PATCH] sched/topology: Assert non-NUMA topology masks don't
 (partially) overlap



On 16/01/2020 15:19, Peter Zijlstra wrote:
> On Thu, Jan 16, 2020 at 11:44:28AM +0100, Peter Zijlstra wrote:
>> On Wed, Jan 15, 2020 at 04:09:15PM +0000, Valentin Schneider wrote:
>>> @@ -1975,6 +2011,9 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
>>>  				has_asym = true;
>>>  			}
>>>  
>>> +			if (WARN_ON(!topology_span_sane(tl, cpu_map, i)))
>>> +				goto error;
>>> +
>>>  			sd = build_sched_domain(tl, cpu_map, attr, sd, dflags, i);
>>>  
>>>  			if (tl == sched_domain_topology)
>>
>> This is O(nr_cpus), but then, that function already is, so I don't see a
>> problem with this.
> 
> Clearly I meant to write O(nr_cpus^2), there's a bunch of nested
> for_each_cpu() in there.
> 

Hm so the sanity check is O(topo_levels * nr_cpus²), and I think that
roughly matches the complexity of building the sched_groups (I say
roughly because you go over less CPUs as you go up the topo levels).

As you said the important bit is that we don't make build_sched_domains()
noticeably worse, which I think is the case...

>> I'll take it, thanks!