sched/topology: Assert non-NUMA topology masks don't (partially) overlap
PATCH 1/1 sched/topology: Assert non-NUMA topology masks don't (partially) overlap
topology.c::get_group() relies on the assumption that non-NUMA domains do not partially overlap. Zeng Tao pointed out in [1] that such topology descriptions, while completely bogus, can end up being exposed to the scheduler.
In his example (8 CPUs, 2-node system), we end up with:
MC span for CPU3 == 3-7
MC span for CPU4 == 4-7
The first pass through get_group(3, sdd@MC) will result in the following sched_group list:
3 -> 4 -> 5 -> 6 -> 7
^ /
`----------------'
And a later pass through get_group(4, sdd@MC) will "corrupt" that to:
3 -> 4 -> 5 -> 6 -> 7
^ / `-----------'
which will completely break things like 'while (sg != sd->groups)' when using CPU3's base sched_domain.
There already are some architecture-specific checks in place such as x86/kernel/smpboot.c::topology.sane(), but this is something we can detect in the core scheduler, so it seems worthwhile to do so.
Warn and abort the construction of the sched domains if such a broken topology description is detected. Note that this is somewhat expensive (O(t.c²), 't' non-NUMA topology levels and 'c' CPUs) and could be gated under SCHED_DEBUG if deemed necessary.
Testing
=======
Dietmar managed to reproduce this using the following qemu incantation:
$ qemu-system-aarch64 -kernel ./Image -hda ./qemu-image-aarch64.img \ -append 'root=/dev/vda console=ttyAMA0 loglevel=8 sched_debug' -smp \ cores=8 --nographic -m 512 -cpu cortex-a53 -machine virt -numa \ node,cpus=0-2,nodeid=0 -numa node,cpus=3-7,nodeid=1
alongside the following drivers/base/arch_topology.c hack (AIUI wouldn't be needed if '-smp cores=X, sockets=Y' would work with qemu):
8<---
@@ -465,6 +465,9 @@ void update_siblings_masks(unsigned int cpuid)
if (cpuid_topo->package_id != cpu_topo->package_id)
continue;
+ if ((cpu < 4 && cpuid > 3) || (cpu > 3 && cpuid < 4))
+ continue;
+
cpumask_set_cpu(cpuid, &cpu_topo->core_sibling); cpumask_set_cpu(cpu, &cpuid_topo->core_sibling);
8<---
[1]: https://lkml.kernel.org/r/[email protected]
---
A "less intrusive" alternative is to assert the sd->groups list doesn't get re-written, which is a symptom of such bogus topologies. I've briefly tested this, you can have a look at it here:
http://www.linux-arm.org/git?p=linux-vs.git;a=commit;h=e0ead72137332cbd3d69c9055ab29e6ffae5b37b
fetchable via:
git fetch git://linux-arm.org/linux-vs mainline/topology/non_numa_overlap_sg
--- kernel/sched/topology.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+)
kernel/sched/topology.c +39 -0
@@ -1879,6 +1879,42 @@ static struct sched_domain *build_sched_domain(struct sched_domain_topology_levereturn sd; } +/* +* Ensure topology masks are sane, i.e. there are no conflicts (overlaps) for +* any two given CPUs at this (non-NUMA) topology level. +*/ +static bool topology_span_sane (struct sched_domain_topology_level *tl, +const struct cpumask *cpu_map,int cpu) +{ +int i; + +/* NUMA levels are allowed to overlap */ +if (tl->flags &SDTL_OVERLAP ) +return true; + +/* +* Non-NUMA levels cannot partially overlap - they must be either +* completely equal or completely disjoint. Otherwise we can end up +* breaking the sched_group lists - i.e. a later get_group() pass +* breaks the linking done for an earlier span. +*/ +for_each_cpu (i, cpu_map) { +if (i == cpu) +continue ; +/* +* We should 'and' all those masks with 'cpu_map' to exactly +* match the topology we're about to build, but that can only +* remove CPUs, which only lessens our ability to detect +* overlaps +*/ +if (!cpumask_equal (tl->mask (cpu), tl->mask (i)) && +cpumask_intersects (tl->mask (cpu), tl->mask (i))) +return false; + } + +return true; +} +/* * Find the sched_domain_topology_level where all CPU capacities are visible * for all CPUs.
@@ -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)
Signature · 1 line
2.24.0
Peter Zijlstra
maintainerQuoted 5 lines · Valentin Schneider
A "less intrusive" alternative is to assert the
sd->groupslist doesn't get re-written, which is a symptom of such bogus topologies. I've briefly tested this, you can have a look at it here:http://www.linux-arm.org/git?p=linux-vs.git;a=commit;h=e0ead72137332cbd3d69c9055ab29e6ffae5b37b
Something like that might still make sense. Can't never be too careful, right ;-)
Quoted 51 lines
kernel/sched/topology.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+)kernel/sched/topology.c +36
-0@@ -1879,6 +1879,42 @@ static struct sched_domain *build_sched_domain(struct sched_domain_topology_levereturn sd; } +/* +* Ensure topology masks are sane, i.e. there are no conflicts (overlaps) for +* any two given CPUs at this (non-NUMA) topology level. +*/ +static bool topology_span_sane (struct sched_domain_topology_level *tl, +const struct cpumask *cpu_map,int cpu) +{ +int i; + +/* NUMA levels are allowed to overlap */ +if (tl->flags &SDTL_OVERLAP ) +return true; + +/* +* Non-NUMA levels cannot partially overlap - they must be either +* completely equal or completely disjoint. Otherwise we can end up +* breaking the sched_group lists - i.e. a later get_group() pass +* breaks the linking done for an earlier span. +*/ +for_each_cpu (i, cpu_map) { +if (i == cpu) +continue ; +/* +* We should 'and' all those masks with 'cpu_map' to exactly +* match the topology we're about to build, but that can only +* remove CPUs, which only lessens our ability to detect +* overlaps +*/ +if (!cpumask_equal (tl->mask (cpu), tl->mask (i)) && +cpumask_intersects (tl->mask (cpu), tl->mask (i))) +return false; + } + +return true; +} +/* * Find the sched_domain_topology_level where all CPU capacities are visible * for all CPUs.
kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2019
Quoted 9 lines
kernel/sched/topology.c +3
-0@@ -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.
I'll take it, thanks!
Quoted 10 lines · Peter Zijlstra
Quoted 5 lines · Valentin Schneider
A "less intrusive" alternative is to assert the
sd->groupslist doesn't get re-written, which is a symptom of such bogus topologies. I've briefly tested this, you can have a look at it here:http://www.linux-arm.org/git?p=linux-vs.git;a=commit;h=e0ead72137332cbd3d69c9055ab29e6ffae5b37b
Something like that might still make sense. Can't never be too careful, right ;-)
True. I'll ponder about it and see if I can't make it a bit neater
Peter Zijlstra
maintainerQuoted 10 lines · Peter Zijlstra
Quoted 9 lines · Valentin Schneider
kernel/sched/topology.c +3
-0@@ -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);
Quoted 4 lines
kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2019
Quoted 1 line
kernel/sched/topology.c +0
-0if (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.
Quoted 1 line
I'll take it, thanks!
Quoted 11 lines · Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
Quoted 9 lines · Valentin Schneider
kernel/sched/topology.c +3
-0@@ -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);
Quoted 8 lines
Quoted 4 lines
kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2019
Quoted 1 line
kernel/sched/topology.c +0
-0if (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 nestedfor_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...
Quoted 1 line
Quoted 1 line
I'll take it, thanks!
The following commit has been merged into the sched/core branch of tip:
The following commit has been merged into the sched/core branch of tip:
Commit-ID: ccf74128d66ce937876184ad55db2e0276af08d3 Gitweb: https://git.kernel.org/tip/ccf74128d66ce937876184ad55db2e0276af08d3 Author: Valentin Schneider <[email protected]> AuthorDate: Wed, 15 Jan 2020 16:09:15 Committer: Peter Zijlstra <[email protected]> CommitterDate: Fri, 17 Jan 2020 10:19:23 +01:00
sched/topology: Assert non-NUMA topology masks don't (partially) overlap
topology.c::get_group() relies on the assumption that non-NUMA domains do not partially overlap. Zeng Tao pointed out in [1] that such topology descriptions, while completely bogus, can end up being exposed to the scheduler.
In his example (8 CPUs, 2-node system), we end up with:
MC span for CPU3 == 3-7
MC span for CPU4 == 4-7
The first pass through get_group(3, sdd@MC) will result in the following sched_group list:
3 -> 4 -> 5 -> 6 -> 7
^ /
`----------------'
And a later pass through get_group(4, sdd@MC) will "corrupt" that to:
3 -> 4 -> 5 -> 6 -> 7
^ / `-----------'
which will completely break things like 'while (sg != sd->groups)' when using CPU3's base sched_domain.
There already are some architecture-specific checks in place such as x86/kernel/smpboot.c::topology.sane(), but this is something we can detect in the core scheduler, so it seems worthwhile to do so.
Warn and abort the construction of the sched domains if such a broken topology description is detected. Note that this is somewhat expensive (O(t.c²), 't' non-NUMA topology levels and 'c' CPUs) and could be gated under SCHED_DEBUG if deemed necessary.
Testing
=======
Dietmar managed to reproduce this using the following qemu incantation:
$ qemu-system-aarch64 -kernel ./Image -hda ./qemu-image-aarch64.img \ -append 'root=/dev/vda console=ttyAMA0 loglevel=8 sched_debug' -smp \ cores=8 --nographic -m 512 -cpu cortex-a53 -machine virt -numa \ node,cpus=0-2,nodeid=0 -numa node,cpus=3-7,nodeid=1
alongside the following drivers/base/arch_topology.c hack (AIUI wouldn't be needed if '-smp cores=X, sockets=Y' would work with qemu):
8<---
@@ -465,6 +465,9 @@ void update_siblings_masks(unsigned int cpuid)
if (cpuid_topo->package_id != cpu_topo->package_id)
continue;
+ if ((cpu < 4 && cpuid > 3) || (cpu > 3 && cpuid < 4))
+ continue;
+
cpumask_set_cpu(cpuid, &cpu_topo->core_sibling); cpumask_set_cpu(cpu, &cpuid_topo->core_sibling);
8<---
[1]: https://lkml.kernel.org/r/[email protected]
--- kernel/sched/topology.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+)
kernel/sched/topology.c +39 -0
@@ -1880,6 +1880,42 @@ static struct sched_domain *build_sched_domain(struct sched_domain_topology_leve }/* +* Ensure topology masks are sane, i.e. there are no conflicts (overlaps) for +* any two given CPUs at this (non-NUMA) topology level. +*/ +static bool topology_span_sane (struct sched_domain_topology_level *tl, +const struct cpumask *cpu_map,int cpu) +{ +int i; + +/* NUMA levels are allowed to overlap */ +if (tl->flags &SDTL_OVERLAP ) +return true; + +/* +* Non-NUMA levels cannot partially overlap - they must be either +* completely equal or completely disjoint. Otherwise we can end up +* breaking the sched_group lists - i.e. a later get_group() pass +* breaks the linking done for an earlier span. +*/ +for_each_cpu (i, cpu_map) { +if (i == cpu) +continue ; +/* +* We should 'and' all those masks with 'cpu_map' to exactly +* match the topology we're about to build, but that can only +* remove CPUs, which only lessens our ability to detect +* overlaps +*/ +if (!cpumask_equal (tl->mask (cpu), tl->mask (i)) && +cpumask_intersects (tl->mask (cpu), tl->mask (i))) +return false; + } + +return true; +} + +/* * Find the sched_domain_topology_level where all CPU capacities are visible * for all CPUs. */
@@ -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)