[PATCH v4 0/3] Rework CPU capacity asymmetry detection

[PATCH v4 0/3] Rework CPU capacity asymmetry detection

[Beata Michalska]

As of now, the asym_cpu_capacity_level will try to locate the lowest
topology level where the highest available CPU capacity is being
visible to all CPUs. This works perfectly fine for most of existing
asymmetric designs out there, though for some possible and completely
valid setups, combining different cpu microarchitectures within
clusters, this might not be the best approach, resulting in pointing
at a level, at which some of the domains might not see any asymmetry
at all. This could be problematic for misfit migration and/or energy
aware placement. And as such, for affected platforms it might result
in custom changes to wake-up and CPU selection paths.

As mentioned in the previous version, based on the available sources out there,
one of the potentially affected (by original approach) platforms might be
Exynos 9820/990 with it's 'sliced' LLC(SLC) divided between the two custom (big)
cores and the remaining A75/A55 cores, which seems to be reflected in the
made available dt entries for those platforms.

The following patches rework how the asymmetric detection is being
carried out, allowing pinning the asymmetric topology level to the lowest one,
where full range of CPU capacities is visible to all CPUs within given
sched domain. The asym_cpu_capacity_level will also keep track of those
levels where any scope of asymmetry is being observed, to denote
corresponding sched domains with the SD_ASYM_CPUCAPACITY flag
and to enable misfit migration for those.

In order to distinguish the sched domains with partial vs full range
of CPU capacity asymmetry, new sched domain flag has been introduced:
SD_ASYM_CPUCAPACITY_FULL.

The overall idea of changing the asymmetry detection has been suggested
by Valentin Schneider <valentin.schneider@arm.com>

Verified on (mostly):
    - QEMU (version 4.2.1) with variants of possible asymmetric topologies
	- machine: virt
	- modifying the device-tree 'cpus' node for virt machine:

	qemu-system-aarch64 -kernel $KERNEL_IMG
	    -drive format=qcow2,file=$IMAGE
	    -append 'root=/dev/vda earlycon console=ttyAMA0 sched_debug
	     sched_verbose loglevel=15 kmemleak=on' -m 2G  --nographic
	    -cpu cortex-a57 -machine virt -smp cores=8
	    -machine dumpdtb=$CUSTOM_DTB.dtb

	$KERNEL_PATH/scripts/dtc/dtc -I dtb -O dts $CUSTOM_DTB.dts >
	$CUSTOM_DTB.dtb

	(modify the dts)

	$KERNEL_PATH/scripts/dtc/dtc -I dts -O dtb $CUSTOM_DTB.dts >
	$CUSTOM_DTB.dtb

	qemu-system-aarch64 -kernel $KERNEL_IMG
	    -drive format=qcow2,file=$IMAGE
	    -append 'root=/dev/vda earlycon console=ttyAMA0 sched_debug
	     sched_verbose loglevel=15 kmemleak=on' -m 2G  --nographic
	    -cpu cortex-a57 -machine virt -smp cores=8
	    -machine dtb=$CUSTOM_DTB.dtb


v4:
 - Based on Peter's idea, reworking asym detection to use per-cpu
   capacity list to serve as base for determining the asym scope
v3:
 - Additional style/doc fixes
v2:
 - Fixed style issues
 - Reworked accessing the cached topology data as suggested by Valentin

Beata Michalska (3):
  sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag
  sched/topology: Rework CPU capacity asymmetry detection
  sched/doc: Update the CPU capacity asymmetry bits

 Documentation/scheduler/sched-capacity.rst |   6 +-
 Documentation/scheduler/sched-energy.rst   |   2 +-
 include/linux/sched/sd_flags.h             |  10 +++
 kernel/sched/topology.c                    | 131 ++++++++++++++++++-----------
 4 files changed, 96 insertions(+), 53 deletions(-)

--
2.7.4

[PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Beata Michalska]

Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
topology flag, to distinguish between shed_domains where any CPU
capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
a full range of CPU capacities is visible to all domain members
(SD_ASYM_CPUCAPACITY_FULL).

With the distinction between full and partial CPU capacity asymmetry,
brought in by the newly introduced flag, the scope of the original
SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
behaviour when one is detected on a given sched domain, allowing
misfit migrations within sched domains that do not observe full range
of CPU capacities but still do have members with different capacity
values. It loses though it's meaning when it comes to the lowest CPU
asymmetry sched_domain level per-cpu pointer, which is to be now
denoted by SD_ASYM_CPUCAPACITY_FULL flag.

Signed-off-by: Beata Michalska <beata.michalska@arm.com>
Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
---
 include/linux/sched/sd_flags.h | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
index 34b21e9..57bde66 100644
--- a/include/linux/sched/sd_flags.h
+++ b/include/linux/sched/sd_flags.h
@@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
 SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
 
 /*
+ * Domain members have different CPU capacities spanning all unique CPU
+ * capacity values.
+ *
+ * SHARED_PARENT: Set from the topmost domain down to the first domain where
+ *		  all available CPU capacities are visible
+ * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
+ */
+SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
+
+/*
  * Domain members share CPU capacity (i.e. SMT)
  *
  * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
-- 
2.7.4

[PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Beata Michalska]

Currently the CPU capacity asymmetry detection, performed through
asym_cpu_capacity_level, tries to identify the lowest topology level
at which the highest CPU capacity is being observed, not necessarily
finding the level at which all possible capacity values are visible
to all CPUs, which might be bit problematic for some possible/valid
asymmetric topologies i.e.:

DIE      [                                ]
MC       [                       ][       ]

CPU       [0] [1] [2] [3] [4] [5]  [6] [7]
Capacity  |.....| |.....| |.....|  |.....|
	     L	     M       B        B

Where:
 arch_scale_cpu_capacity(L) = 512
 arch_scale_cpu_capacity(M) = 871
 arch_scale_cpu_capacity(B) = 1024

In this particular case, the asymmetric topology level will point
at MC, as all possible CPU masks for that level do cover the CPU
with the highest capacity. It will work just fine for the first
cluster, not so much for the second one though (consider the
find_energy_efficient_cpu which might end up attempting the energy
aware wake-up for a domain that does not see any asymmetry at all)

Rework the way the capacity asymmetry levels are being detected,
allowing to point to the lowest topology level (for a given CPU), where
full range of available CPU capacities is visible to all CPUs within given
domain. As a result, the per-cpu sd_asym_cpucapacity might differ across
the domains. This will have an impact on EAS wake-up placement in a way
that it might see different rage of CPUs to be considered, depending on
the given current and target CPUs.

Additionally, those levels, where any range of asymmetry (not
necessarily full) is being detected will get identified as well.
The selected asymmetric topology level will be denoted by
SD_ASYM_CPUCAPACITY_FULL sched domain flag whereas the 'sub-levels'
would receive the already used SD_ASYM_CPUCAPACITY flag. This allows
maintaining the current behaviour for asymmetric topologies, with
misfit migration operating correctly on lower levels, if applicable,
as any asymmetry is enough to trigger the misfit migration.
The logic there relies on the SD_ASYM_CPUCAPACITY flag and does not
relate to the full asymmetry level denoted by the sd_asym_cpucapacity
pointer.

Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Beata Michalska <beata.michalska@arm.com>
---
 kernel/sched/topology.c | 129 +++++++++++++++++++++++++++++-------------------
 1 file changed, 79 insertions(+), 50 deletions(-)

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 55a0a24..81957f7 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -675,7 +675,7 @@ static void update_top_cache_domain(int cpu)
 	sd = highest_flag_domain(cpu, SD_ASYM_PACKING);
 	rcu_assign_pointer(per_cpu(sd_asym_packing, cpu), sd);
 
-	sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY);
+	sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY_FULL);
 	rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
 }
 
@@ -1989,66 +1989,96 @@ static bool topology_span_sane(struct sched_domain_topology_level *tl,
 
 	return true;
 }
-
+/**
+ * Asym capacity bits
+ */
+struct asym_cap_data {
+	struct list_head link;
+	unsigned long    capacity;
+	struct cpumask   *cpu_mask;
+};
 /*
- * Find the sched_domain_topology_level where all CPU capacities are visible
- * for all CPUs.
+ * Set of available CPUs grouped by their corresponding capacities
+ * Each list entry contains a CPU mask reflecting CPUs that share the same
+ * capacity.
+ * The lifespan of data is unlimited.
  */
-static struct sched_domain_topology_level
-*asym_cpu_capacity_level(const struct cpumask *cpu_map)
-{
-	int i, j, asym_level = 0;
-	bool asym = false;
-	struct sched_domain_topology_level *tl, *asym_tl = NULL;
-	unsigned long cap;
+static LIST_HEAD(asym_cap_list);
 
-	/* Is there any asymmetry? */
-	cap = arch_scale_cpu_capacity(cpumask_first(cpu_map));
-
-	for_each_cpu(i, cpu_map) {
-		if (arch_scale_cpu_capacity(i) != cap) {
-			asym = true;
-			break;
-		}
+/*
+ * Verify whether given CPU at a given topology level belongs to a sched domain
+ * that does span CPUs with different capacities.
+ * Provides sd_flags reflecting the asymmetry scope.
+ */
+static inline int
+asym_cpu_capacity_classify(struct sched_domain_topology_level *tl, int cpu)
+{
+	int sd_asym_flags = SD_ASYM_CPUCAPACITY | SD_ASYM_CPUCAPACITY_FULL;
+	const struct cpumask *tl_mask = tl->mask(cpu);
+	struct asym_cap_data *entry;
+	int asym_cap_count = 0;
+
+	if (list_is_singular(&asym_cap_list))
+		goto leave;
+
+	list_for_each_entry(entry, &asym_cap_list, link) {
+		if (cpumask_intersects(tl_mask, entry->cpu_mask))
+			++asym_cap_count;
+		else
+			sd_asym_flags &= ~SD_ASYM_CPUCAPACITY_FULL;
 	}
+	WARN_ON_ONCE(!asym_cap_count);
+leave:
+	return asym_cap_count > 1 ? sd_asym_flags : 0;
+}
 
-	if (!asym)
-		return NULL;
 
-	/*
-	 * Examine topology from all CPU's point of views to detect the lowest
-	 * sched_domain_topology_level where a highest capacity CPU is visible
-	 * to everyone.
-	 */
-	for_each_cpu(i, cpu_map) {
-		unsigned long max_capacity = arch_scale_cpu_capacity(i);
-		int tl_id = 0;
+/*
+ * Build-up/update list of CPUs grouped by their capacities
+ */
+static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
+{
+	struct asym_cap_data *entry, *next;
+	int cpu;
 
-		for_each_sd_topology(tl) {
-			if (tl_id < asym_level)
-				goto next_level;
+	if (!list_empty(&asym_cap_list))
+		list_for_each_entry(entry, &asym_cap_list, link)
+			cpumask_clear(entry->cpu_mask);
 
-			for_each_cpu_and(j, tl->mask(i), cpu_map) {
-				unsigned long capacity;
+	entry = list_first_entry_or_null(&asym_cap_list,
+			struct asym_cap_data, link);
 
-				capacity = arch_scale_cpu_capacity(j);
+	for_each_cpu(cpu, cpu_map) {
+		unsigned long capacity = arch_scale_cpu_capacity(cpu);
 
-				if (capacity <= max_capacity)
-					continue;
+		if (entry && capacity == entry->capacity)
+			goto next;
 
-				max_capacity = capacity;
-				asym_level = tl_id;
-				asym_tl = tl;
-			}
-next_level:
-			tl_id++;
+		list_for_each_entry(entry, &asym_cap_list, link)
+			if (capacity == entry->capacity)
+				goto next;
+
+		entry = kzalloc(sizeof(*entry) + cpumask_size(), GFP_KERNEL);
+		if (entry) {
+			entry->capacity = capacity;
+			entry->cpu_mask = (struct cpumask *)((char *)entry +
+					   sizeof(*entry));
+			list_add(&entry->link, &asym_cap_list);
 		}
+		WARN_ONCE(!entry,
+		    "Failed to allocate memory for capacity asymmetry detection\n");
+next:
+		__cpumask_set_cpu(cpu, entry->cpu_mask);
 	}
 
-	return asym_tl;
+	list_for_each_entry_safe(entry, next, &asym_cap_list, link) {
+		if (cpumask_empty(entry->cpu_mask)) {
+			list_del(&entry->link);
+			kfree(entry);
+		}
+	}
 }
 
-
 /*
  * Build sched domains for a given set of CPUs and attach the sched domains
  * to the individual CPUs
@@ -2061,7 +2091,6 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 	struct s_data d;
 	struct rq *rq = NULL;
 	int i, ret = -ENOMEM;
-	struct sched_domain_topology_level *tl_asym;
 	bool has_asym = false;
 
 	if (WARN_ON(cpumask_empty(cpu_map)))
@@ -2071,7 +2100,7 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 	if (alloc_state != sa_rootdomain)
 		goto error;
 
-	tl_asym = asym_cpu_capacity_level(cpu_map);
+	asym_cpu_capacity_scan(cpu_map);
 
 	/* Set up domains for CPUs specified by the cpu_map: */
 	for_each_cpu(i, cpu_map) {
@@ -2080,9 +2109,9 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 
 		sd = NULL;
 		for_each_sd_topology(tl) {
-			if (tl == tl_asym) {
-				dflags |= SD_ASYM_CPUCAPACITY;
-				has_asym = true;
+			if (!(dflags & SD_ASYM_CPUCAPACITY_FULL)) {
+				dflags |= asym_cpu_capacity_classify(tl, i);
+				has_asym = dflags & SD_ASYM_CPUCAPACITY;
 			}
 
 			if (WARN_ON(!topology_span_sane(tl, cpu_map, i)))
-- 
2.7.4

[PATCH v4 3/3] sched/doc: Update the CPU capacity asymmetry bits

[Beata Michalska]

Update the documentation bits referring to capacity aware scheduling
with regards to newly introduced SD_ASYM_CPUCAPACITY_FULL sched_domain
flag.

Signed-off-by: Beata Michalska <beata.michalska@arm.com>
Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
---
 Documentation/scheduler/sched-capacity.rst | 6 ++++--
 Documentation/scheduler/sched-energy.rst   | 2 +-
 2 files changed, 5 insertions(+), 3 deletions(-)

diff --git a/Documentation/scheduler/sched-capacity.rst b/Documentation/scheduler/sched-capacity.rst
index 9b7cbe4..805f85f 100644
--- a/Documentation/scheduler/sched-capacity.rst
+++ b/Documentation/scheduler/sched-capacity.rst
@@ -284,8 +284,10 @@ whether the system exhibits asymmetric CPU capacities. Should that be the
 case:
 
 - The sched_asym_cpucapacity static key will be enabled.
-- The SD_ASYM_CPUCAPACITY flag will be set at the lowest sched_domain level that
-  spans all unique CPU capacity values.
+- The SD_ASYM_CPUCAPACITY_FULL flag will be set at the lowest sched_domain
+  level that spans all unique CPU capacity values.
+- The SD_ASYM_CPUCAPACITY flag will be set for any sched_domain that spans
+  CPUs with any range of asymmetry.
 
 The sched_asym_cpucapacity static key is intended to guard sections of code that
 cater to asymmetric CPU capacity systems. Do note however that said key is
diff --git a/Documentation/scheduler/sched-energy.rst b/Documentation/scheduler/sched-energy.rst
index afe02d3..8fbce5e 100644
--- a/Documentation/scheduler/sched-energy.rst
+++ b/Documentation/scheduler/sched-energy.rst
@@ -328,7 +328,7 @@ section lists these dependencies and provides hints as to how they can be met.
 
 As mentioned in the introduction, EAS is only supported on platforms with
 asymmetric CPU topologies for now. This requirement is checked at run-time by
-looking for the presence of the SD_ASYM_CPUCAPACITY flag when the scheduling
+looking for the presence of the SD_ASYM_CPUCAPACITY_FULL flag when the scheduling
 domains are built.
 
 See Documentation/scheduler/sched-capacity.rst for requirements to be met for this
-- 
2.7.4

Re: [PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Valentin Schneider]

On 17/05/21 09:23, Beata Michalska wrote:
> Currently the CPU capacity asymmetry detection, performed through
> asym_cpu_capacity_level, tries to identify the lowest topology level
> at which the highest CPU capacity is being observed, not necessarily
> finding the level at which all possible capacity values are visible
> to all CPUs, which might be bit problematic for some possible/valid
> asymmetric topologies i.e.:
>
> DIE      [                                ]
> MC       [                       ][       ]
>
> CPU       [0] [1] [2] [3] [4] [5]  [6] [7]
> Capacity  |.....| |.....| |.....|  |.....|
>            L	     M       B        B
>
> Where:
>  arch_scale_cpu_capacity(L) = 512
>  arch_scale_cpu_capacity(M) = 871
>  arch_scale_cpu_capacity(B) = 1024
>
> In this particular case, the asymmetric topology level will point
> at MC, as all possible CPU masks for that level do cover the CPU
> with the highest capacity. It will work just fine for the first
> cluster, not so much for the second one though (consider the
> find_energy_efficient_cpu which might end up attempting the energy
> aware wake-up for a domain that does not see any asymmetry at all)
>
> Rework the way the capacity asymmetry levels are being detected,
> allowing to point to the lowest topology level (for a given CPU), where
> full range of available CPU capacities is visible to all CPUs within given
> domain. As a result, the per-cpu sd_asym_cpucapacity might differ across
> the domains. This will have an impact on EAS wake-up placement in a way
> that it might see different rage of CPUs to be considered, depending on
> the given current and target CPUs.
>
> Additionally, those levels, where any range of asymmetry (not
> necessarily full) is being detected will get identified as well.
> The selected asymmetric topology level will be denoted by
> SD_ASYM_CPUCAPACITY_FULL sched domain flag whereas the 'sub-levels'
> would receive the already used SD_ASYM_CPUCAPACITY flag. This allows
> maintaining the current behaviour for asymmetric topologies, with
> misfit migration operating correctly on lower levels, if applicable,
> as any asymmetry is enough to trigger the misfit migration.
> The logic there relies on the SD_ASYM_CPUCAPACITY flag and does not
> relate to the full asymmetry level denoted by the sd_asym_cpucapacity
> pointer.
>
> Suggested-by: Peter Zijlstra <peterz@infradead.org>
> Signed-off-by: Beata Michalska <beata.michalska@arm.com>

That does look quite simpler :-)

A lesson for me as a reviewer here is to resist biting into the nitty
gritty code details and spend more time on a first conceptual / high level
review pass. It's not the first time I'm guilty of it, so I do need to work
on that.

> ---
>  kernel/sched/topology.c | 129 +++++++++++++++++++++++++++++-------------------
>  1 file changed, 79 insertions(+), 50 deletions(-)
>
> diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
> index 55a0a24..81957f7 100644
> --- a/kernel/sched/topology.c
> +++ b/kernel/sched/topology.c
> @@ -675,7 +675,7 @@ static void update_top_cache_domain(int cpu)
>       sd = highest_flag_domain(cpu, SD_ASYM_PACKING);
>       rcu_assign_pointer(per_cpu(sd_asym_packing, cpu), sd);
>
> -	sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY);
> +	sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY_FULL);
>       rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
>  }
>
> @@ -1989,66 +1989,96 @@ static bool topology_span_sane(struct sched_domain_topology_level *tl,
>
>       return true;
>  }
> -
> +/**
> + * Asym capacity bits

Nit: Dietmar would have us phrase this "Asymmetric CPU capacity bits".

> + */
> +struct asym_cap_data {
> +	struct list_head link;
> +	unsigned long    capacity;
> +	struct cpumask   *cpu_mask;
> +};

> +/*
> + * Verify whether given CPU at a given topology level belongs to a sched domain
> + * that does span CPUs with different capacities.
> + * Provides sd_flags reflecting the asymmetry scope.
> + */
> +static inline int
> +asym_cpu_capacity_classify(struct sched_domain_topology_level *tl, int cpu)
> +{
> +	int sd_asym_flags = SD_ASYM_CPUCAPACITY | SD_ASYM_CPUCAPACITY_FULL;
> +	const struct cpumask *tl_mask = tl->mask(cpu);
> +	struct asym_cap_data *entry;
> +	int asym_cap_count = 0;
> +
> +	if (list_is_singular(&asym_cap_list))
> +		goto leave;
> +
> +	list_for_each_entry(entry, &asym_cap_list, link) {
> +		if (cpumask_intersects(tl_mask, entry->cpu_mask))
> +			++asym_cap_count;

Ah, this is using tl->mask() which *isn't* masked by the root_domain's
cpu_map...

See comment below on the scan; long story short we could issue this *after*
build_sched_domain() so we can directly use sched_domain_span(sd) which
*is* masked by the cpu_map. This kind of removes the need for that dflags
param, but then we're already sidestepping it for SD_OVERLAP.

EDIT: nope, we have a check against SD_ASYM_CPUCAPACITY in sd_init()... I
guess we could issue asym_cpu_capacity_classify() in sd_init() itself?

> +/*
> + * Build-up/update list of CPUs grouped by their capacities
> + */
> +static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
> +{
> +	struct asym_cap_data *entry, *next;
> +	int cpu;
>
> -		for_each_sd_topology(tl) {
> -			if (tl_id < asym_level)
> -				goto next_level;
> +	if (!list_empty(&asym_cap_list))
> +		list_for_each_entry(entry, &asym_cap_list, link)
> +			cpumask_clear(entry->cpu_mask);
>

The topology isn't going to change between domain rebuilds, so why
recompute the masks? The sched_domain spans are already masked by cpu_map,
so no need to do this masking twice. I'm thinking this scan should be done
once against the cpu_possible_mask - kinda like sched_init_numa() done once
against the possible nodes.

Ideally I'd see this as an __init function, unfortunately we need that to
happen after cpufreq drivers have been loaded (in case all CPUs have same
µarch but some can reach higher frequencies, which would yield asymmetry),
and some of those can be built as modules :/

> +		entry = kzalloc(sizeof(*entry) + cpumask_size(), GFP_KERNEL);
> +		if (entry) {
> +			entry->capacity = capacity;
> +			entry->cpu_mask = (struct cpumask *)((char *)entry +
> +					   sizeof(*entry));
> +			list_add(&entry->link, &asym_cap_list);
>               }
> +		WARN_ONCE(!entry,
> +		    "Failed to allocate memory for capacity asymmetry detection\n");
> +next:
> +		__cpumask_set_cpu(cpu, entry->cpu_mask);

That looks like a NULL deref if the above WARN is hit.

Re: [PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Beata Michalska]

On Mon, May 17, 2021 at 01:04:25PM +0100, Valentin Schneider wrote:
> On 17/05/21 09:23, Beata Michalska wrote:
> > Currently the CPU capacity asymmetry detection, performed through
> > asym_cpu_capacity_level, tries to identify the lowest topology level
> > at which the highest CPU capacity is being observed, not necessarily
> > finding the level at which all possible capacity values are visible
> > to all CPUs, which might be bit problematic for some possible/valid
> > asymmetric topologies i.e.:
> >
> > DIE      [                                ]
> > MC       [                       ][       ]
> >
> > CPU       [0] [1] [2] [3] [4] [5]  [6] [7]
> > Capacity  |.....| |.....| |.....|  |.....|
> >            L	     M       B        B
> >
> > Where:
> >  arch_scale_cpu_capacity(L) = 512
> >  arch_scale_cpu_capacity(M) = 871
> >  arch_scale_cpu_capacity(B) = 1024
> >
> > In this particular case, the asymmetric topology level will point
> > at MC, as all possible CPU masks for that level do cover the CPU
> > with the highest capacity. It will work just fine for the first
> > cluster, not so much for the second one though (consider the
> > find_energy_efficient_cpu which might end up attempting the energy
> > aware wake-up for a domain that does not see any asymmetry at all)
> >
> > Rework the way the capacity asymmetry levels are being detected,
> > allowing to point to the lowest topology level (for a given CPU), where
> > full range of available CPU capacities is visible to all CPUs within given
> > domain. As a result, the per-cpu sd_asym_cpucapacity might differ across
> > the domains. This will have an impact on EAS wake-up placement in a way
> > that it might see different rage of CPUs to be considered, depending on
> > the given current and target CPUs.
> >
> > Additionally, those levels, where any range of asymmetry (not
> > necessarily full) is being detected will get identified as well.
> > The selected asymmetric topology level will be denoted by
> > SD_ASYM_CPUCAPACITY_FULL sched domain flag whereas the 'sub-levels'
> > would receive the already used SD_ASYM_CPUCAPACITY flag. This allows
> > maintaining the current behaviour for asymmetric topologies, with
> > misfit migration operating correctly on lower levels, if applicable,
> > as any asymmetry is enough to trigger the misfit migration.
> > The logic there relies on the SD_ASYM_CPUCAPACITY flag and does not
> > relate to the full asymmetry level denoted by the sd_asym_cpucapacity
> > pointer.
> >
> > Suggested-by: Peter Zijlstra <peterz@infradead.org>
> > Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> 
> That does look quite simpler :-)
> 
> A lesson for me as a reviewer here is to resist biting into the nitty
> gritty code details and spend more time on a first conceptual / high level
> review pass. It's not the first time I'm guilty of it, so I do need to work
> on that.
> 
> > ---
> >  kernel/sched/topology.c | 129 +++++++++++++++++++++++++++++-------------------
> >  1 file changed, 79 insertions(+), 50 deletions(-)
> >
> > diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
> > index 55a0a24..81957f7 100644
> > --- a/kernel/sched/topology.c
> > +++ b/kernel/sched/topology.c
> > @@ -675,7 +675,7 @@ static void update_top_cache_domain(int cpu)
> >       sd = highest_flag_domain(cpu, SD_ASYM_PACKING);
> >       rcu_assign_pointer(per_cpu(sd_asym_packing, cpu), sd);
> >
> > -	sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY);
> > +	sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY_FULL);
> >       rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
> >  }
> >
> > @@ -1989,66 +1989,96 @@ static bool topology_span_sane(struct sched_domain_topology_level *tl,
> >
> >       return true;
> >  }
> > -
> > +/**
> > + * Asym capacity bits
> 
> Nit: Dietmar would have us phrase this "Asymmetric CPU capacity bits".
> 
> > + */
> > +struct asym_cap_data {
> > +	struct list_head link;
> > +	unsigned long    capacity;
> > +	struct cpumask   *cpu_mask;
> > +};
> 
> > +/*
> > + * Verify whether given CPU at a given topology level belongs to a sched domain
> > + * that does span CPUs with different capacities.
> > + * Provides sd_flags reflecting the asymmetry scope.
> > + */
> > +static inline int
> > +asym_cpu_capacity_classify(struct sched_domain_topology_level *tl, int cpu)
> > +{
> > +	int sd_asym_flags = SD_ASYM_CPUCAPACITY | SD_ASYM_CPUCAPACITY_FULL;
> > +	const struct cpumask *tl_mask = tl->mask(cpu);
> > +	struct asym_cap_data *entry;
> > +	int asym_cap_count = 0;
> > +
> > +	if (list_is_singular(&asym_cap_list))
> > +		goto leave;
> > +
> > +	list_for_each_entry(entry, &asym_cap_list, link) {
> > +		if (cpumask_intersects(tl_mask, entry->cpu_mask))
> > +			++asym_cap_count;
> 
> Ah, this is using tl->mask() which *isn't* masked by the root_domain's
> cpu_map...
> 
> See comment below on the scan; long story short we could issue this *after*
> build_sched_domain() so we can directly use sched_domain_span(sd) which
> *is* masked by the cpu_map. This kind of removes the need for that dflags
> param, but then we're already sidestepping it for SD_OVERLAP.
> 
> EDIT: nope, we have a check against SD_ASYM_CPUCAPACITY in sd_init()... I
> guess we could issue asym_cpu_capacity_classify() in sd_init() itself?
> 
Yeah, sd_init does rely on the SD_ASYM_CPUCAPACITY flag being available,
if needed. The tl->mask isn't masked out but the per-capacity masks are.
Should be enough for the intersection check.
> > +/*
> > + * Build-up/update list of CPUs grouped by their capacities
> > + */
> > +static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
> > +{
> > +	struct asym_cap_data *entry, *next;
> > +	int cpu;
> >
> > -		for_each_sd_topology(tl) {
> > -			if (tl_id < asym_level)
> > -				goto next_level;
> > +	if (!list_empty(&asym_cap_list))
> > +		list_for_each_entry(entry, &asym_cap_list, link)
> > +			cpumask_clear(entry->cpu_mask);
> >
> 
> The topology isn't going to change between domain rebuilds, so why
> recompute the masks? The sched_domain spans are already masked by cpu_map,
> so no need to do this masking twice. I'm thinking this scan should be done
> once against the cpu_possible_mask - kinda like sched_init_numa() done once
> against the possible nodes.
> 
This is currently done, as what you have mentioned earlier, the tl->mask
may contain CPUs that are not 'available'. So it makes sure that the masks
kept on  the list are representing only those CPUs that are online.
And it is also needed case all CPUs of given capacity go offline - not to to
lose the full asymmetry that might change because of that ( empty masks are
being removed from the list).
I could change that and use the CPU mask that represents the online CPUs as
a checkpoint but then it also means additional tracking which items on the
list are actually available at a given point of time.
So if the CPUs masks on the list are to be set once (as you are suggesting)
than it needs additional logic to count the number of available capacities
to decide whether there is a full asymmetry or not.

> Ideally I'd see this as an __init function, unfortunately we need that to
> happen after cpufreq drivers have been loaded (in case all CPUs have same
> µarch but some can reach higher frequencies, which would yield asymmetry),
> and some of those can be built as modules :/
>
Yeah, this is the tricky bit: and one of the reasons the capacity masks are
being cleared.
> > +		entry = kzalloc(sizeof(*entry) + cpumask_size(), GFP_KERNEL);
> > +		if (entry) {
> > +			entry->capacity = capacity;
> > +			entry->cpu_mask = (struct cpumask *)((char *)entry +
> > +					   sizeof(*entry));
> > +			list_add(&entry->link, &asym_cap_list);
> >               }
> > +		WARN_ONCE(!entry,
> > +		    "Failed to allocate memory for capacity asymmetry detection\n");
> > +next:
> > +		__cpumask_set_cpu(cpu, entry->cpu_mask);
> 
> That looks like a NULL deref if the above WARN is hit.
Nah, indeed!

---
BR
B.

Re: [PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Valentin Schneider]

On 17/05/21 14:18, Beata Michalska wrote:
> On Mon, May 17, 2021 at 01:04:25PM +0100, Valentin Schneider wrote:
>> On 17/05/21 09:23, Beata Michalska wrote:
>> > +static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
>> > +{
>> > +	struct asym_cap_data *entry, *next;
>> > +	int cpu;
>> >
>> > -		for_each_sd_topology(tl) {
>> > -			if (tl_id < asym_level)
>> > -				goto next_level;
>> > +	if (!list_empty(&asym_cap_list))
>> > +		list_for_each_entry(entry, &asym_cap_list, link)
>> > +			cpumask_clear(entry->cpu_mask);
>> >
>>
>> The topology isn't going to change between domain rebuilds, so why
>> recompute the masks? The sched_domain spans are already masked by cpu_map,
>> so no need to do this masking twice. I'm thinking this scan should be done
>> once against the cpu_possible_mask - kinda like sched_init_numa() done once
>> against the possible nodes.
>>
> This is currently done, as what you have mentioned earlier, the tl->mask
> may contain CPUs that are not 'available'. So it makes sure that the masks
> kept on  the list are representing only those CPUs that are online.
> And it is also needed case all CPUs of given capacity go offline - not to to
> lose the full asymmetry that might change because of that ( empty masks are
> being removed from the list).
>
> I could change that and use the CPU mask that represents the online CPUs as
> a checkpoint but then it also means additional tracking which items on the
> list are actually available at a given point of time.
> So if the CPUs masks on the list are to be set once (as you are suggesting)
> than it needs additional logic to count the number of available capacities
> to decide whether there is a full asymmetry or not.
>

That should be doable by counting non-empty intersections between each
entry->cpumask and the cpu_online_mask in _classify().

That said I'm afraid cpufreq module loading forces us to dynamically update
those masks, as you've done. The first domain build could see asymmetry
without cpufreq loaded, and a later one with cpufreq loaded would need an
update. Conversely, as much of a fringe case as it is, we'd have to cope
with the cpufreq module being unloaded later on...

:(

Re: [PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Vincent Guittot]

On Mon, 17 May 2021 at 10:24, Beata Michalska <beata.michalska@arm.com> wrote:
>
> Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
> topology flag, to distinguish between shed_domains where any CPU
> capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
> a full range of CPU capacities is visible to all domain members
> (SD_ASYM_CPUCAPACITY_FULL).

I'm not sure about what you want to detect:

Is it a sched_domain level with a full range of cpu capacity, i.e.
with at least 1 min capacity and 1 max capacity ?
or do you want to get at least 1 cpu of each capacity ?


>
> With the distinction between full and partial CPU capacity asymmetry,
> brought in by the newly introduced flag, the scope of the original
> SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
> behaviour when one is detected on a given sched domain, allowing
> misfit migrations within sched domains that do not observe full range
> of CPU capacities but still do have members with different capacity
> values. It loses though it's meaning when it comes to the lowest CPU
> asymmetry sched_domain level per-cpu pointer, which is to be now
> denoted by SD_ASYM_CPUCAPACITY_FULL flag.
>
> Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> ---
>  include/linux/sched/sd_flags.h | 10 ++++++++++
>  1 file changed, 10 insertions(+)
>
> diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
> index 34b21e9..57bde66 100644
> --- a/include/linux/sched/sd_flags.h
> +++ b/include/linux/sched/sd_flags.h
> @@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
>  SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
>
>  /*
> + * Domain members have different CPU capacities spanning all unique CPU
> + * capacity values.
> + *
> + * SHARED_PARENT: Set from the topmost domain down to the first domain where
> + *               all available CPU capacities are visible
> + * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
> + */
> +SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> +
> +/*
>   * Domain members share CPU capacity (i.e. SMT)
>   *
>   * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
> --
> 2.7.4
>

Re: [PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Beata Michalska]

On Tue, May 18, 2021 at 03:39:27PM +0200, Vincent Guittot wrote:
> On Mon, 17 May 2021 at 10:24, Beata Michalska <beata.michalska@arm.com> wrote:
> >
> > Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
> > topology flag, to distinguish between shed_domains where any CPU
> > capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
> > a full range of CPU capacities is visible to all domain members
> > (SD_ASYM_CPUCAPACITY_FULL).
> 
> I'm not sure about what you want to detect:
> 
> Is it a sched_domain level with a full range of cpu capacity, i.e.
> with at least 1 min capacity and 1 max capacity ?
> or do you want to get at least 1 cpu of each capacity ?
That would be at least one CPU of each available capacity within given domain,
so full -set- of available capacities within a domain.

---
BR
B.
> 
> 
> >
> > With the distinction between full and partial CPU capacity asymmetry,
> > brought in by the newly introduced flag, the scope of the original
> > SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
> > behaviour when one is detected on a given sched domain, allowing
> > misfit migrations within sched domains that do not observe full range
> > of CPU capacities but still do have members with different capacity
> > values. It loses though it's meaning when it comes to the lowest CPU
> > asymmetry sched_domain level per-cpu pointer, which is to be now
> > denoted by SD_ASYM_CPUCAPACITY_FULL flag.
> >
> > Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> > Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> > ---
> >  include/linux/sched/sd_flags.h | 10 ++++++++++
> >  1 file changed, 10 insertions(+)
> >
> > diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
> > index 34b21e9..57bde66 100644
> > --- a/include/linux/sched/sd_flags.h
> > +++ b/include/linux/sched/sd_flags.h
> > @@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
> >  SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> >
> >  /*
> > + * Domain members have different CPU capacities spanning all unique CPU
> > + * capacity values.
> > + *
> > + * SHARED_PARENT: Set from the topmost domain down to the first domain where
> > + *               all available CPU capacities are visible
> > + * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
> > + */
> > +SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > +
> > +/*
> >   * Domain members share CPU capacity (i.e. SMT)
> >   *
> >   * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
> > --
> > 2.7.4
> >

Re: [PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Beata Michalska]

On Mon, May 17, 2021 at 04:06:05PM +0100, Valentin Schneider wrote:
> On 17/05/21 14:18, Beata Michalska wrote:
> > On Mon, May 17, 2021 at 01:04:25PM +0100, Valentin Schneider wrote:
> >> On 17/05/21 09:23, Beata Michalska wrote:
> >> > +static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
> >> > +{
> >> > +	struct asym_cap_data *entry, *next;
> >> > +	int cpu;
> >> >
> >> > -		for_each_sd_topology(tl) {
> >> > -			if (tl_id < asym_level)
> >> > -				goto next_level;
> >> > +	if (!list_empty(&asym_cap_list))
> >> > +		list_for_each_entry(entry, &asym_cap_list, link)
> >> > +			cpumask_clear(entry->cpu_mask);
> >> >
> >>
> >> The topology isn't going to change between domain rebuilds, so why
> >> recompute the masks? The sched_domain spans are already masked by cpu_map,
> >> so no need to do this masking twice. I'm thinking this scan should be done
> >> once against the cpu_possible_mask - kinda like sched_init_numa() done once
> >> against the possible nodes.
> >>
> > This is currently done, as what you have mentioned earlier, the tl->mask
> > may contain CPUs that are not 'available'. So it makes sure that the masks
> > kept on  the list are representing only those CPUs that are online.
> > And it is also needed case all CPUs of given capacity go offline - not to to
> > lose the full asymmetry that might change because of that ( empty masks are
> > being removed from the list).
> >
> > I could change that and use the CPU mask that represents the online CPUs as
> > a checkpoint but then it also means additional tracking which items on the
> > list are actually available at a given point of time.
> > So if the CPUs masks on the list are to be set once (as you are suggesting)
> > than it needs additional logic to count the number of available capacities
> > to decide whether there is a full asymmetry or not.
> >
> 
> That should be doable by counting non-empty intersections between each
> entry->cpumask and the cpu_online_mask in _classify().
> 
> That said I'm afraid cpufreq module loading forces us to dynamically update
> those masks, as you've done. The first domain build could see asymmetry
> without cpufreq loaded, and a later one with cpufreq loaded would need an
> update. Conversely, as much of a fringe case as it is, we'd have to cope
> with the cpufreq module being unloaded later on...
> 
> :(
So it got me thinking that maybe we could actually make it more
'update-on-demand' and use the cpufreq policy notifier to trigger the update.
I could try to draft smth generic enough to make it ... relatively easy to adapt
to different archs case needed.
Any thoughts ?

---
BR
B.

Re: [PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Vincent Guittot]

On Tue, 18 May 2021 at 16:27, Beata Michalska <beata.michalska@arm.com> wrote:
>
> On Tue, May 18, 2021 at 03:39:27PM +0200, Vincent Guittot wrote:
> > On Mon, 17 May 2021 at 10:24, Beata Michalska <beata.michalska@arm.com> wrote:
> > >
> > > Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
> > > topology flag, to distinguish between shed_domains where any CPU
> > > capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
> > > a full range of CPU capacities is visible to all domain members
> > > (SD_ASYM_CPUCAPACITY_FULL).
> >
> > I'm not sure about what you want to detect:
> >
> > Is it a sched_domain level with a full range of cpu capacity, i.e.
> > with at least 1 min capacity and 1 max capacity ?
> > or do you want to get at least 1 cpu of each capacity ?
> That would be at least one CPU of each available capacity within given domain,
> so full -set- of available capacities within a domain.

Would be good to add the precision.

Although I'm not sure if that's the best policy compared to only
getting the range which would be far simpler to implement.
Do you have some topology example ?






>
> ---
> BR
> B.
> >
> >
> > >
> > > With the distinction between full and partial CPU capacity asymmetry,
> > > brought in by the newly introduced flag, the scope of the original
> > > SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
> > > behaviour when one is detected on a given sched domain, allowing
> > > misfit migrations within sched domains that do not observe full range
> > > of CPU capacities but still do have members with different capacity
> > > values. It loses though it's meaning when it comes to the lowest CPU
> > > asymmetry sched_domain level per-cpu pointer, which is to be now
> > > denoted by SD_ASYM_CPUCAPACITY_FULL flag.
> > >
> > > Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> > > Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> > > ---
> > >  include/linux/sched/sd_flags.h | 10 ++++++++++
> > >  1 file changed, 10 insertions(+)
> > >
> > > diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
> > > index 34b21e9..57bde66 100644
> > > --- a/include/linux/sched/sd_flags.h
> > > +++ b/include/linux/sched/sd_flags.h
> > > @@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
> > >  SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > >
> > >  /*
> > > + * Domain members have different CPU capacities spanning all unique CPU
> > > + * capacity values.
> > > + *
> > > + * SHARED_PARENT: Set from the topmost domain down to the first domain where
> > > + *               all available CPU capacities are visible
> > > + * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
> > > + */
> > > +SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > +
> > > +/*
> > >   * Domain members share CPU capacity (i.e. SMT)
> > >   *
> > >   * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
> > > --
> > > 2.7.4
> > >

Re: [PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Beata Michalska]

On Tue, May 18, 2021 at 04:53:09PM +0200, Vincent Guittot wrote:
> On Tue, 18 May 2021 at 16:27, Beata Michalska <beata.michalska@arm.com> wrote:
> >
> > On Tue, May 18, 2021 at 03:39:27PM +0200, Vincent Guittot wrote:
> > > On Mon, 17 May 2021 at 10:24, Beata Michalska <beata.michalska@arm.com> wrote:
> > > >
> > > > Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
> > > > topology flag, to distinguish between shed_domains where any CPU
> > > > capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
> > > > a full range of CPU capacities is visible to all domain members
> > > > (SD_ASYM_CPUCAPACITY_FULL).
> > >
> > > I'm not sure about what you want to detect:
> > >
> > > Is it a sched_domain level with a full range of cpu capacity, i.e.
> > > with at least 1 min capacity and 1 max capacity ?
> > > or do you want to get at least 1 cpu of each capacity ?
> > That would be at least one CPU of each available capacity within given domain,
> > so full -set- of available capacities within a domain.
> 
> Would be good to add the precision.
Will do.
> 
> Although I'm not sure if that's the best policy compared to only
> getting the range which would be far simpler to implement.
> Do you have some topology example ?

An example from second patch from the series:

DIE      [                                ]
MC       [                       ][       ]

CPU       [0] [1] [2] [3] [4] [5]  [6] [7]
Capacity  |.....| |.....| |.....|  |.....|
	     L	     M       B        B

Where:
 arch_scale_cpu_capacity(L) = 512
 arch_scale_cpu_capacity(M) = 871
 arch_scale_cpu_capacity(B) = 1024

which could also look like:

DIE      [                                        ]
MC       [                       ][               ]

CPU       [0] [1] [2] [3] [4] [5]  [6] [7] [8] [9]
Capacity  |.....| |.....| |.....|  |.....| |.....|
	     L	     M       B        L       B

Considering only range would mean loosing the 2 (M) CPUs out of sight
for feec in some cases.

---
BR.
B
> 
> 
> 
> 
> 
> 
> >
> > ---
> > BR
> > B.
> > >
> > >
> > > >
> > > > With the distinction between full and partial CPU capacity asymmetry,
> > > > brought in by the newly introduced flag, the scope of the original
> > > > SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
> > > > behaviour when one is detected on a given sched domain, allowing
> > > > misfit migrations within sched domains that do not observe full range
> > > > of CPU capacities but still do have members with different capacity
> > > > values. It loses though it's meaning when it comes to the lowest CPU
> > > > asymmetry sched_domain level per-cpu pointer, which is to be now
> > > > denoted by SD_ASYM_CPUCAPACITY_FULL flag.
> > > >
> > > > Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> > > > Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> > > > ---
> > > >  include/linux/sched/sd_flags.h | 10 ++++++++++
> > > >  1 file changed, 10 insertions(+)
> > > >
> > > > diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
> > > > index 34b21e9..57bde66 100644
> > > > --- a/include/linux/sched/sd_flags.h
> > > > +++ b/include/linux/sched/sd_flags.h
> > > > @@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
> > > >  SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > >
> > > >  /*
> > > > + * Domain members have different CPU capacities spanning all unique CPU
> > > > + * capacity values.
> > > > + *
> > > > + * SHARED_PARENT: Set from the topmost domain down to the first domain where
> > > > + *               all available CPU capacities are visible
> > > > + * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
> > > > + */
> > > > +SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > +
> > > > +/*
> > > >   * Domain members share CPU capacity (i.e. SMT)
> > > >   *
> > > >   * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
> > > > --
> > > > 2.7.4
> > > >

Re: [PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Vincent Guittot]

On Tue, 18 May 2021 at 17:09, Beata Michalska <beata.michalska@arm.com> wrote:
>
> On Tue, May 18, 2021 at 04:53:09PM +0200, Vincent Guittot wrote:
> > On Tue, 18 May 2021 at 16:27, Beata Michalska <beata.michalska@arm.com> wrote:
> > >
> > > On Tue, May 18, 2021 at 03:39:27PM +0200, Vincent Guittot wrote:
> > > > On Mon, 17 May 2021 at 10:24, Beata Michalska <beata.michalska@arm.com> wrote:
> > > > >
> > > > > Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
> > > > > topology flag, to distinguish between shed_domains where any CPU
> > > > > capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
> > > > > a full range of CPU capacities is visible to all domain members
> > > > > (SD_ASYM_CPUCAPACITY_FULL).
> > > >
> > > > I'm not sure about what you want to detect:
> > > >
> > > > Is it a sched_domain level with a full range of cpu capacity, i.e.
> > > > with at least 1 min capacity and 1 max capacity ?
> > > > or do you want to get at least 1 cpu of each capacity ?
> > > That would be at least one CPU of each available capacity within given domain,
> > > so full -set- of available capacities within a domain.
> >
> > Would be good to add the precision.
> Will do.
> >
> > Although I'm not sure if that's the best policy compared to only
> > getting the range which would be far simpler to implement.
> > Do you have some topology example ?
>
> An example from second patch from the series:
>
> DIE      [                                ]
> MC       [                       ][       ]
>
> CPU       [0] [1] [2] [3] [4] [5]  [6] [7]
> Capacity  |.....| |.....| |.....|  |.....|
>              L       M       B        B

The one above , which is described in your patchset, works with the range policy

>
> Where:
>  arch_scale_cpu_capacity(L) = 512
>  arch_scale_cpu_capacity(M) = 871
>  arch_scale_cpu_capacity(B) = 1024
>
> which could also look like:
>
> DIE      [                                        ]
> MC       [                       ][               ]
>
> CPU       [0] [1] [2] [3] [4] [5]  [6] [7] [8] [9]
> Capacity  |.....| |.....| |.....|  |.....| |.....|
>              L       M       B        L       B

I know that that HW guys can come with crazy idea but they would
probably add M  instead of L with B in the 2nd cluster as a boost of
performance at the cost of powering up another "cluster" in which case
the range policy works as well

>
> Considering only range would mean loosing the 2 (M) CPUs out of sight
> for feec in some cases.

Is it realistic ? Considering all the code and complexity added by
patch 2, will we really use it at the end ?

Regards,
Vincent
>
> ---
> BR.
> B
> >
> >
> >
> >
> >
> >
> > >
> > > ---
> > > BR
> > > B.
> > > >
> > > >
> > > > >
> > > > > With the distinction between full and partial CPU capacity asymmetry,
> > > > > brought in by the newly introduced flag, the scope of the original
> > > > > SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
> > > > > behaviour when one is detected on a given sched domain, allowing
> > > > > misfit migrations within sched domains that do not observe full range
> > > > > of CPU capacities but still do have members with different capacity
> > > > > values. It loses though it's meaning when it comes to the lowest CPU
> > > > > asymmetry sched_domain level per-cpu pointer, which is to be now
> > > > > denoted by SD_ASYM_CPUCAPACITY_FULL flag.
> > > > >
> > > > > Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> > > > > Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> > > > > ---
> > > > >  include/linux/sched/sd_flags.h | 10 ++++++++++
> > > > >  1 file changed, 10 insertions(+)
> > > > >
> > > > > diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
> > > > > index 34b21e9..57bde66 100644
> > > > > --- a/include/linux/sched/sd_flags.h
> > > > > +++ b/include/linux/sched/sd_flags.h
> > > > > @@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
> > > > >  SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > >
> > > > >  /*
> > > > > + * Domain members have different CPU capacities spanning all unique CPU
> > > > > + * capacity values.
> > > > > + *
> > > > > + * SHARED_PARENT: Set from the topmost domain down to the first domain where
> > > > > + *               all available CPU capacities are visible
> > > > > + * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
> > > > > + */
> > > > > +SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > > +
> > > > > +/*
> > > > >   * Domain members share CPU capacity (i.e. SMT)
> > > > >   *
> > > > >   * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
> > > > > --
> > > > > 2.7.4
> > > > >

Re: [PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Beata Michalska]

On Tue, May 18, 2021 at 05:28:11PM +0200, Vincent Guittot wrote:
> On Tue, 18 May 2021 at 17:09, Beata Michalska <beata.michalska@arm.com> wrote:
> >
> > On Tue, May 18, 2021 at 04:53:09PM +0200, Vincent Guittot wrote:
> > > On Tue, 18 May 2021 at 16:27, Beata Michalska <beata.michalska@arm.com> wrote:
> > > >
> > > > On Tue, May 18, 2021 at 03:39:27PM +0200, Vincent Guittot wrote:
> > > > > On Mon, 17 May 2021 at 10:24, Beata Michalska <beata.michalska@arm.com> wrote:
> > > > > >
> > > > > > Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
> > > > > > topology flag, to distinguish between shed_domains where any CPU
> > > > > > capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
> > > > > > a full range of CPU capacities is visible to all domain members
> > > > > > (SD_ASYM_CPUCAPACITY_FULL).
> > > > >
> > > > > I'm not sure about what you want to detect:
> > > > >
> > > > > Is it a sched_domain level with a full range of cpu capacity, i.e.
> > > > > with at least 1 min capacity and 1 max capacity ?
> > > > > or do you want to get at least 1 cpu of each capacity ?
> > > > That would be at least one CPU of each available capacity within given domain,
> > > > so full -set- of available capacities within a domain.
> > >
> > > Would be good to add the precision.
> > Will do.
> > >
> > > Although I'm not sure if that's the best policy compared to only
> > > getting the range which would be far simpler to implement.
> > > Do you have some topology example ?
> >
> > An example from second patch from the series:
> >
> > DIE      [                                ]
> > MC       [                       ][       ]
> >
> > CPU       [0] [1] [2] [3] [4] [5]  [6] [7]
> > Capacity  |.....| |.....| |.....|  |.....|
> >              L       M       B        B
> 
> The one above , which is described in your patchset, works with the range policy
Yeap, but that is just a variation of all the possibilities....
> 
> >
> > Where:
> >  arch_scale_cpu_capacity(L) = 512
> >  arch_scale_cpu_capacity(M) = 871
> >  arch_scale_cpu_capacity(B) = 1024
> >
> > which could also look like:
> >
> > DIE      [                                        ]
> > MC       [                       ][               ]
> >
> > CPU       [0] [1] [2] [3] [4] [5]  [6] [7] [8] [9]
> > Capacity  |.....| |.....| |.....|  |.....| |.....|
> >              L       M       B        L       B
> 
> I know that that HW guys can come with crazy idea but they would
> probably add M  instead of L with B in the 2nd cluster as a boost of
> performance at the cost of powering up another "cluster" in which case
> the range policy works as well
> 
> >
> > Considering only range would mean loosing the 2 (M) CPUs out of sight
> > for feec in some cases.
> 
> Is it realistic ? Considering all the code and complexity added by
> patch 2, will we really use it at the end ?
> 
I do completely agree that the first approach was slightly .... blown out of
proportions, but with Peter's idea, the complexity has dropped significantly.
With the range being considered we are back to per domain tracking of available
capacities (min/max), plus additional cycles on comparing capacities.
Unless I fail to see the simplicity of that approach ?

---
BR
B.
> Regards,
> Vincent
> >
> > ---
> > BR.
> > B
> > >
> > >
> > >
> > >
> > >
> > >
> > > >
> > > > ---
> > > > BR
> > > > B.
> > > > >
> > > > >
> > > > > >
> > > > > > With the distinction between full and partial CPU capacity asymmetry,
> > > > > > brought in by the newly introduced flag, the scope of the original
> > > > > > SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
> > > > > > behaviour when one is detected on a given sched domain, allowing
> > > > > > misfit migrations within sched domains that do not observe full range
> > > > > > of CPU capacities but still do have members with different capacity
> > > > > > values. It loses though it's meaning when it comes to the lowest CPU
> > > > > > asymmetry sched_domain level per-cpu pointer, which is to be now
> > > > > > denoted by SD_ASYM_CPUCAPACITY_FULL flag.
> > > > > >
> > > > > > Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> > > > > > Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> > > > > > ---
> > > > > >  include/linux/sched/sd_flags.h | 10 ++++++++++
> > > > > >  1 file changed, 10 insertions(+)
> > > > > >
> > > > > > diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
> > > > > > index 34b21e9..57bde66 100644
> > > > > > --- a/include/linux/sched/sd_flags.h
> > > > > > +++ b/include/linux/sched/sd_flags.h
> > > > > > @@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
> > > > > >  SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > > >
> > > > > >  /*
> > > > > > + * Domain members have different CPU capacities spanning all unique CPU
> > > > > > + * capacity values.
> > > > > > + *
> > > > > > + * SHARED_PARENT: Set from the topmost domain down to the first domain where
> > > > > > + *               all available CPU capacities are visible
> > > > > > + * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
> > > > > > + */
> > > > > > +SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > > > +
> > > > > > +/*
> > > > > >   * Domain members share CPU capacity (i.e. SMT)
> > > > > >   *
> > > > > >   * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
> > > > > > --
> > > > > > 2.7.4
> > > > > >

Re: [PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Valentin Schneider]

On 18/05/21 15:40, Beata Michalska wrote:
> On Mon, May 17, 2021 at 04:06:05PM +0100, Valentin Schneider wrote:
>> On 17/05/21 14:18, Beata Michalska wrote:
>> > On Mon, May 17, 2021 at 01:04:25PM +0100, Valentin Schneider wrote:
>> >> On 17/05/21 09:23, Beata Michalska wrote:
>> >> > +static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
>> >> > +{
>> >> > +	struct asym_cap_data *entry, *next;
>> >> > +	int cpu;
>> >> >
>> >> > -		for_each_sd_topology(tl) {
>> >> > -			if (tl_id < asym_level)
>> >> > -				goto next_level;
>> >> > +	if (!list_empty(&asym_cap_list))
>> >> > +		list_for_each_entry(entry, &asym_cap_list, link)
>> >> > +			cpumask_clear(entry->cpu_mask);
>> >> >
>> >>
>> >> The topology isn't going to change between domain rebuilds, so why
>> >> recompute the masks? The sched_domain spans are already masked by cpu_map,
>> >> so no need to do this masking twice. I'm thinking this scan should be done
>> >> once against the cpu_possible_mask - kinda like sched_init_numa() done once
>> >> against the possible nodes.
>> >>
>> > This is currently done, as what you have mentioned earlier, the tl->mask
>> > may contain CPUs that are not 'available'. So it makes sure that the masks
>> > kept on  the list are representing only those CPUs that are online.
>> > And it is also needed case all CPUs of given capacity go offline - not to to
>> > lose the full asymmetry that might change because of that ( empty masks are
>> > being removed from the list).
>> >
>> > I could change that and use the CPU mask that represents the online CPUs as
>> > a checkpoint but then it also means additional tracking which items on the
>> > list are actually available at a given point of time.
>> > So if the CPUs masks on the list are to be set once (as you are suggesting)
>> > than it needs additional logic to count the number of available capacities
>> > to decide whether there is a full asymmetry or not.
>> >
>>
>> That should be doable by counting non-empty intersections between each
>> entry->cpumask and the cpu_online_mask in _classify().
>>
>> That said I'm afraid cpufreq module loading forces us to dynamically update
>> those masks, as you've done. The first domain build could see asymmetry
>> without cpufreq loaded, and a later one with cpufreq loaded would need an
>> update. Conversely, as much of a fringe case as it is, we'd have to cope
>> with the cpufreq module being unloaded later on...
>>
>> :(
> So it got me thinking that maybe we could actually make it more
> 'update-on-demand' and use the cpufreq policy notifier to trigger the update.
> I could try to draft smth generic enough to make it ... relatively easy to adapt
> to different archs case needed.
> Any thoughts ?
>

The cpufreq policy notifier rebuild is currently an arch_topology.c
specificity, and perhaps we can consider this as our standing policy: if an
arch needs a topology rebuild upon X event (which isn't hotplug), it is
responsible for triggering it itself.

There's those sched_energy_update / arch_update_cpu_topology() bools that
are used to tweak the rebuild behaviour, perhaps you could gate the
capacity maps rebuild behind arch_update_cpu_topology()?

That way you could build those maps based on a cpu_possible_mask iterator,
and only rebuild them when the arch requests it (arch_topology already does
that with the cpufreq notifier). How does it sound?

> ---
> BR
> B.

Re: [PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Vincent Guittot]

On Tue, 18 May 2021 at 17:48, Beata Michalska <beata.michalska@arm.com> wrote:
>
> On Tue, May 18, 2021 at 05:28:11PM +0200, Vincent Guittot wrote:
> > On Tue, 18 May 2021 at 17:09, Beata Michalska <beata.michalska@arm.com> wrote:
> > >
> > > On Tue, May 18, 2021 at 04:53:09PM +0200, Vincent Guittot wrote:
> > > > On Tue, 18 May 2021 at 16:27, Beata Michalska <beata.michalska@arm.com> wrote:
> > > > >
> > > > > On Tue, May 18, 2021 at 03:39:27PM +0200, Vincent Guittot wrote:
> > > > > > On Mon, 17 May 2021 at 10:24, Beata Michalska <beata.michalska@arm.com> wrote:
> > > > > > >
> > > > > > > Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
> > > > > > > topology flag, to distinguish between shed_domains where any CPU
> > > > > > > capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
> > > > > > > a full range of CPU capacities is visible to all domain members
> > > > > > > (SD_ASYM_CPUCAPACITY_FULL).
> > > > > >
> > > > > > I'm not sure about what you want to detect:
> > > > > >
> > > > > > Is it a sched_domain level with a full range of cpu capacity, i.e.
> > > > > > with at least 1 min capacity and 1 max capacity ?
> > > > > > or do you want to get at least 1 cpu of each capacity ?
> > > > > That would be at least one CPU of each available capacity within given domain,
> > > > > so full -set- of available capacities within a domain.
> > > >
> > > > Would be good to add the precision.
> > > Will do.
> > > >
> > > > Although I'm not sure if that's the best policy compared to only
> > > > getting the range which would be far simpler to implement.
> > > > Do you have some topology example ?
> > >
> > > An example from second patch from the series:
> > >
> > > DIE      [                                ]
> > > MC       [                       ][       ]
> > >
> > > CPU       [0] [1] [2] [3] [4] [5]  [6] [7]
> > > Capacity  |.....| |.....| |.....|  |.....|
> > >              L       M       B        B
> >
> > The one above , which is described in your patchset, works with the range policy
> Yeap, but that is just a variation of all the possibilities....
> >
> > >
> > > Where:
> > >  arch_scale_cpu_capacity(L) = 512
> > >  arch_scale_cpu_capacity(M) = 871
> > >  arch_scale_cpu_capacity(B) = 1024
> > >
> > > which could also look like:
> > >
> > > DIE      [                                        ]
> > > MC       [                       ][               ]
> > >
> > > CPU       [0] [1] [2] [3] [4] [5]  [6] [7] [8] [9]
> > > Capacity  |.....| |.....| |.....|  |.....| |.....|
> > >              L       M       B        L       B
> >
> > I know that that HW guys can come with crazy idea but they would
> > probably add M  instead of L with B in the 2nd cluster as a boost of
> > performance at the cost of powering up another "cluster" in which case
> > the range policy works as well
> >
> > >
> > > Considering only range would mean loosing the 2 (M) CPUs out of sight
> > > for feec in some cases.
> >
> > Is it realistic ? Considering all the code and complexity added by
> > patch 2, will we really use it at the end ?
> >
> I do completely agree that the first approach was slightly .... blown out of
> proportions, but with Peter's idea, the complexity has dropped significantly.
> With the range being considered we are back to per domain tracking of available
> capacities (min/max), plus additional cycles on comparing capacities.
> Unless I fail to see the simplicity of that approach ?

With the range, you just have to keep track of one cpumask for min
capacity and 1 for max capacity (considering that the absolute max
capacity/1024 might not be in the cpumap) instead of tracking all
capacity and manipulating/updating a dynamic link list. Then as soon
as you have 1 cpu of both masks then you are done. As a 1st glance
this seems to be simpler to do.

>
> ---
> BR
> B.
> > Regards,
> > Vincent
> > >
> > > ---
> > > BR.
> > > B
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > >
> > > > > ---
> > > > > BR
> > > > > B.
> > > > > >
> > > > > >
> > > > > > >
> > > > > > > With the distinction between full and partial CPU capacity asymmetry,
> > > > > > > brought in by the newly introduced flag, the scope of the original
> > > > > > > SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
> > > > > > > behaviour when one is detected on a given sched domain, allowing
> > > > > > > misfit migrations within sched domains that do not observe full range
> > > > > > > of CPU capacities but still do have members with different capacity
> > > > > > > values. It loses though it's meaning when it comes to the lowest CPU
> > > > > > > asymmetry sched_domain level per-cpu pointer, which is to be now
> > > > > > > denoted by SD_ASYM_CPUCAPACITY_FULL flag.
> > > > > > >
> > > > > > > Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> > > > > > > Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> > > > > > > ---
> > > > > > >  include/linux/sched/sd_flags.h | 10 ++++++++++
> > > > > > >  1 file changed, 10 insertions(+)
> > > > > > >
> > > > > > > diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
> > > > > > > index 34b21e9..57bde66 100644
> > > > > > > --- a/include/linux/sched/sd_flags.h
> > > > > > > +++ b/include/linux/sched/sd_flags.h
> > > > > > > @@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
> > > > > > >  SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > > > >
> > > > > > >  /*
> > > > > > > + * Domain members have different CPU capacities spanning all unique CPU
> > > > > > > + * capacity values.
> > > > > > > + *
> > > > > > > + * SHARED_PARENT: Set from the topmost domain down to the first domain where
> > > > > > > + *               all available CPU capacities are visible
> > > > > > > + * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
> > > > > > > + */
> > > > > > > +SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > > > > +
> > > > > > > +/*
> > > > > > >   * Domain members share CPU capacity (i.e. SMT)
> > > > > > >   *
> > > > > > >   * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
> > > > > > > --
> > > > > > > 2.7.4
> > > > > > >

Re: [PATCH v4 1/3] sched/core: Introduce SD_ASYM_CPUCAPACITY_FULL sched_domain flag

[Beata Michalska]

On Tue, May 18, 2021 at 05:56:20PM +0200, Vincent Guittot wrote:
> On Tue, 18 May 2021 at 17:48, Beata Michalska <beata.michalska@arm.com> wrote:
> >
> > On Tue, May 18, 2021 at 05:28:11PM +0200, Vincent Guittot wrote:
> > > On Tue, 18 May 2021 at 17:09, Beata Michalska <beata.michalska@arm.com> wrote:
> > > >
> > > > On Tue, May 18, 2021 at 04:53:09PM +0200, Vincent Guittot wrote:
> > > > > On Tue, 18 May 2021 at 16:27, Beata Michalska <beata.michalska@arm.com> wrote:
> > > > > >
> > > > > > On Tue, May 18, 2021 at 03:39:27PM +0200, Vincent Guittot wrote:
> > > > > > > On Mon, 17 May 2021 at 10:24, Beata Michalska <beata.michalska@arm.com> wrote:
> > > > > > > >
> > > > > > > > Introducing new, complementary to SD_ASYM_CPUCAPACITY, sched_domain
> > > > > > > > topology flag, to distinguish between shed_domains where any CPU
> > > > > > > > capacity asymmetry is detected (SD_ASYM_CPUCAPACITY) and ones where
> > > > > > > > a full range of CPU capacities is visible to all domain members
> > > > > > > > (SD_ASYM_CPUCAPACITY_FULL).
> > > > > > >
> > > > > > > I'm not sure about what you want to detect:
> > > > > > >
> > > > > > > Is it a sched_domain level with a full range of cpu capacity, i.e.
> > > > > > > with at least 1 min capacity and 1 max capacity ?
> > > > > > > or do you want to get at least 1 cpu of each capacity ?
> > > > > > That would be at least one CPU of each available capacity within given domain,
> > > > > > so full -set- of available capacities within a domain.
> > > > >
> > > > > Would be good to add the precision.
> > > > Will do.
> > > > >
> > > > > Although I'm not sure if that's the best policy compared to only
> > > > > getting the range which would be far simpler to implement.
> > > > > Do you have some topology example ?
> > > >
> > > > An example from second patch from the series:
> > > >
> > > > DIE      [                                ]
> > > > MC       [                       ][       ]
> > > >
> > > > CPU       [0] [1] [2] [3] [4] [5]  [6] [7]
> > > > Capacity  |.....| |.....| |.....|  |.....|
> > > >              L       M       B        B
> > >
> > > The one above , which is described in your patchset, works with the range policy
> > Yeap, but that is just a variation of all the possibilities....
> > >
> > > >
> > > > Where:
> > > >  arch_scale_cpu_capacity(L) = 512
> > > >  arch_scale_cpu_capacity(M) = 871
> > > >  arch_scale_cpu_capacity(B) = 1024
> > > >
> > > > which could also look like:
> > > >
> > > > DIE      [                                        ]
> > > > MC       [                       ][               ]
> > > >
> > > > CPU       [0] [1] [2] [3] [4] [5]  [6] [7] [8] [9]
> > > > Capacity  |.....| |.....| |.....|  |.....| |.....|
> > > >              L       M       B        L       B
> > >
> > > I know that that HW guys can come with crazy idea but they would
> > > probably add M  instead of L with B in the 2nd cluster as a boost of
> > > performance at the cost of powering up another "cluster" in which case
> > > the range policy works as well
> > >
> > > >
> > > > Considering only range would mean loosing the 2 (M) CPUs out of sight
> > > > for feec in some cases.
> > >
> > > Is it realistic ? Considering all the code and complexity added by
> > > patch 2, will we really use it at the end ?
> > >
> > I do completely agree that the first approach was slightly .... blown out of
> > proportions, but with Peter's idea, the complexity has dropped significantly.
> > With the range being considered we are back to per domain tracking of available
> > capacities (min/max), plus additional cycles on comparing capacities.
> > Unless I fail to see the simplicity of that approach ?
> 
> With the range, you just have to keep track of one cpumask for min
> capacity and 1 for max capacity (considering that the absolute max
> capacity/1024 might not be in the cpumap) instead of tracking all
> capacity and manipulating/updating a dynamic link list. Then as soon
> as you have 1 cpu of both masks then you are done. As a 1st glance
> this seems to be simpler to do.
>
You would still have to go through all the capacities to find min/max:
so it's either going through all available CPUs twice, or tracking capacities
during the single go-through run. Those masks would also have to be updated to
cover hotplug events when one of the two  might become obsolete.
There is an option being considered to drop updating the list upon every
rebuild of sched domains and that would simplify things even further.
I do not see any big gain with changing the approach, especially that current
one covers all of the cases.
The idea though is a good one so thank you for that.


---
BR
B.

> >
> > ---
> > BR
> > B.
> > > Regards,
> > > Vincent
> > > >
> > > > ---
> > > > BR.
> > > > B
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > >
> > > > > > ---
> > > > > > BR
> > > > > > B.
> > > > > > >
> > > > > > >
> > > > > > > >
> > > > > > > > With the distinction between full and partial CPU capacity asymmetry,
> > > > > > > > brought in by the newly introduced flag, the scope of the original
> > > > > > > > SD_ASYM_CPUCAPACITY flag gets shifted, still maintaining the existing
> > > > > > > > behaviour when one is detected on a given sched domain, allowing
> > > > > > > > misfit migrations within sched domains that do not observe full range
> > > > > > > > of CPU capacities but still do have members with different capacity
> > > > > > > > values. It loses though it's meaning when it comes to the lowest CPU
> > > > > > > > asymmetry sched_domain level per-cpu pointer, which is to be now
> > > > > > > > denoted by SD_ASYM_CPUCAPACITY_FULL flag.
> > > > > > > >
> > > > > > > > Signed-off-by: Beata Michalska <beata.michalska@arm.com>
> > > > > > > > Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
> > > > > > > > ---
> > > > > > > >  include/linux/sched/sd_flags.h | 10 ++++++++++
> > > > > > > >  1 file changed, 10 insertions(+)
> > > > > > > >
> > > > > > > > diff --git a/include/linux/sched/sd_flags.h b/include/linux/sched/sd_flags.h
> > > > > > > > index 34b21e9..57bde66 100644
> > > > > > > > --- a/include/linux/sched/sd_flags.h
> > > > > > > > +++ b/include/linux/sched/sd_flags.h
> > > > > > > > @@ -91,6 +91,16 @@ SD_FLAG(SD_WAKE_AFFINE, SDF_SHARED_CHILD)
> > > > > > > >  SD_FLAG(SD_ASYM_CPUCAPACITY, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > > > > >
> > > > > > > >  /*
> > > > > > > > + * Domain members have different CPU capacities spanning all unique CPU
> > > > > > > > + * capacity values.
> > > > > > > > + *
> > > > > > > > + * SHARED_PARENT: Set from the topmost domain down to the first domain where
> > > > > > > > + *               all available CPU capacities are visible
> > > > > > > > + * NEEDS_GROUPS: Per-CPU capacity is asymmetric between groups.
> > > > > > > > + */
> > > > > > > > +SD_FLAG(SD_ASYM_CPUCAPACITY_FULL, SDF_SHARED_PARENT | SDF_NEEDS_GROUPS)
> > > > > > > > +
> > > > > > > > +/*
> > > > > > > >   * Domain members share CPU capacity (i.e. SMT)
> > > > > > > >   *
> > > > > > > >   * SHARED_CHILD: Set from the base domain up until spanned CPUs no longer share
> > > > > > > > --
> > > > > > > > 2.7.4
> > > > > > > >

Re: [PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Beata Michalska]

On Tue, May 18, 2021 at 04:53:54PM +0100, Valentin Schneider wrote:
> On 18/05/21 15:40, Beata Michalska wrote:
> > On Mon, May 17, 2021 at 04:06:05PM +0100, Valentin Schneider wrote:
> >> On 17/05/21 14:18, Beata Michalska wrote:
> >> > On Mon, May 17, 2021 at 01:04:25PM +0100, Valentin Schneider wrote:
> >> >> On 17/05/21 09:23, Beata Michalska wrote:
> >> >> > +static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
> >> >> > +{
> >> >> > +	struct asym_cap_data *entry, *next;
> >> >> > +	int cpu;
> >> >> >
> >> >> > -		for_each_sd_topology(tl) {
> >> >> > -			if (tl_id < asym_level)
> >> >> > -				goto next_level;
> >> >> > +	if (!list_empty(&asym_cap_list))
> >> >> > +		list_for_each_entry(entry, &asym_cap_list, link)
> >> >> > +			cpumask_clear(entry->cpu_mask);
> >> >> >
> >> >>
> >> >> The topology isn't going to change between domain rebuilds, so why
> >> >> recompute the masks? The sched_domain spans are already masked by cpu_map,
> >> >> so no need to do this masking twice. I'm thinking this scan should be done
> >> >> once against the cpu_possible_mask - kinda like sched_init_numa() done once
> >> >> against the possible nodes.
> >> >>
> >> > This is currently done, as what you have mentioned earlier, the tl->mask
> >> > may contain CPUs that are not 'available'. So it makes sure that the masks
> >> > kept on  the list are representing only those CPUs that are online.
> >> > And it is also needed case all CPUs of given capacity go offline - not to to
> >> > lose the full asymmetry that might change because of that ( empty masks are
> >> > being removed from the list).
> >> >
> >> > I could change that and use the CPU mask that represents the online CPUs as
> >> > a checkpoint but then it also means additional tracking which items on the
> >> > list are actually available at a given point of time.
> >> > So if the CPUs masks on the list are to be set once (as you are suggesting)
> >> > than it needs additional logic to count the number of available capacities
> >> > to decide whether there is a full asymmetry or not.
> >> >
> >>
> >> That should be doable by counting non-empty intersections between each
> >> entry->cpumask and the cpu_online_mask in _classify().
> >>
> >> That said I'm afraid cpufreq module loading forces us to dynamically update
> >> those masks, as you've done. The first domain build could see asymmetry
> >> without cpufreq loaded, and a later one with cpufreq loaded would need an
> >> update. Conversely, as much of a fringe case as it is, we'd have to cope
> >> with the cpufreq module being unloaded later on...
> >>
> >> :(
> > So it got me thinking that maybe we could actually make it more
> > 'update-on-demand' and use the cpufreq policy notifier to trigger the update.
> > I could try to draft smth generic enough to make it ... relatively easy to adapt
> > to different archs case needed.
> > Any thoughts ?
> >
> 
> The cpufreq policy notifier rebuild is currently an arch_topology.c
> specificity, and perhaps we can consider this as our standing policy: if an
> arch needs a topology rebuild upon X event (which isn't hotplug), it is
> responsible for triggering it itself.
> 
> There's those sched_energy_update / arch_update_cpu_topology() bools that
> are used to tweak the rebuild behaviour, perhaps you could gate the
> capacity maps rebuild behind arch_update_cpu_topology()?
> 
> That way you could build those maps based on a cpu_possible_mask iterator,
> and only rebuild them when the arch requests it (arch_topology already does
> that with the cpufreq notifier). How does it sound?
>
That sounds reasonable/doable. Will see how that plays out.
Thanks.

---
BR
B.
> > ---
> > BR
> > B.

Re: [PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Peter Zijlstra]

Mostly style nits, since I read you're already looking at reworking this
due to other feedback, do with it what you like.

On Mon, May 17, 2021 at 09:23:50AM +0100, Beata Michalska wrote:
> @@ -1989,66 +1989,96 @@ static bool topology_span_sane(struct sched_domain_topology_level *tl,
>  
>  	return true;
>  }

+ whitespace

> +/**
> + * Asym capacity bits
> + */
> +struct asym_cap_data {
> +	struct list_head link;
> +	unsigned long    capacity;
> +	struct cpumask   *cpu_mask;
> +};

+ whitespace

>  /*
> + * Set of available CPUs grouped by their corresponding capacities
> + * Each list entry contains a CPU mask reflecting CPUs that share the same
> + * capacity.
> + * The lifespan of data is unlimited.
>   */
> +static LIST_HEAD(asym_cap_list);
>  
> +/*
> + * Verify whether given CPU at a given topology level belongs to a sched domain
> + * that does span CPUs with different capacities.
> + * Provides sd_flags reflecting the asymmetry scope.
> + */
> +static inline int
> +asym_cpu_capacity_classify(struct sched_domain_topology_level *tl, int cpu)
> +{
> +	int sd_asym_flags = SD_ASYM_CPUCAPACITY | SD_ASYM_CPUCAPACITY_FULL;
> +	const struct cpumask *tl_mask = tl->mask(cpu);
> +	struct asym_cap_data *entry;
> +	int asym_cap_count = 0;
> +
> +	if (list_is_singular(&asym_cap_list))
> +		goto leave;
> +
> +	list_for_each_entry(entry, &asym_cap_list, link) {
> +		if (cpumask_intersects(tl_mask, entry->cpu_mask))
> +			++asym_cap_count;
> +		else
> +			sd_asym_flags &= ~SD_ASYM_CPUCAPACITY_FULL;
>  	}
> +	WARN_ON_ONCE(!asym_cap_count);
> +leave:
> +	return asym_cap_count > 1 ? sd_asym_flags : 0;
> +}
>  
>  

- whitespace

> +/*
> + * Build-up/update list of CPUs grouped by their capacities
> + */
> +static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
> +{
> +	struct asym_cap_data *entry, *next;
> +	int cpu;
>  
> +	if (!list_empty(&asym_cap_list))
> +		list_for_each_entry(entry, &asym_cap_list, link)
> +			cpumask_clear(entry->cpu_mask);

two nits:

 - the if() needs { } because while what follows is strictly a single
   statement, it is multi-line, so coding style requires { }.

 - the if() is strictly superfluous, if the list is empty the
   list_for_each_entry() iteration already doesn't do anything.

>  
> +	entry = list_first_entry_or_null(&asym_cap_list,
> +			struct asym_cap_data, link);

Please align line-breaks at the most nested (, vim can help you do this
with: set cino=(0:0, if you're using that other editor, I'm sure you can
convince it to align properly too :-)

>  
> +	for_each_cpu(cpu, cpu_map) {
> +		unsigned long capacity = arch_scale_cpu_capacity(cpu);
>  
> +		if (entry && capacity == entry->capacity)
> +			goto next;
>  
> +		list_for_each_entry(entry, &asym_cap_list, link)
> +			if (capacity == entry->capacity)
> +				goto next;

{ } again

> +
> +		entry = kzalloc(sizeof(*entry) + cpumask_size(), GFP_KERNEL);
> +		if (entry) {
> +			entry->capacity = capacity;
> +			entry->cpu_mask = (struct cpumask *)((char *)entry +
> +					   sizeof(*entry));

alignment again

> +			list_add(&entry->link, &asym_cap_list);
>  		}
> +		WARN_ONCE(!entry,
> +		    "Failed to allocate memory for capacity asymmetry detection\n");

alignment again

(also, eeew, if this lives, perhaps a find_asym_data(capacity) helper
might make it better:

		if (!entry || entry->capacity != capacity)
			entry = find_asym_data(capacity);
)

> +next:
> +		__cpumask_set_cpu(cpu, entry->cpu_mask);
>  	}
>  
> +	list_for_each_entry_safe(entry, next, &asym_cap_list, link) {
> +		if (cpumask_empty(entry->cpu_mask)) {
> +			list_del(&entry->link);
> +			kfree(entry);
> +		}
> +	}

See, this has { }

>  }

Re: [PATCH v4 2/3] sched/topology: Rework CPU capacity asymmetry detection

[Beata Michalska]

On Wed, May 19, 2021 at 01:30:05PM +0200, Peter Zijlstra wrote:
> 
> Mostly style nits, since I read you're already looking at reworking this
> due to other feedback, do with it what you like.
>
Will apply your remarks on whatever ends up in the new version, which should be
most of it. To be out soon.

Thank You

---
BR
B.
> On Mon, May 17, 2021 at 09:23:50AM +0100, Beata Michalska wrote:
> > @@ -1989,66 +1989,96 @@ static bool topology_span_sane(struct sched_domain_topology_level *tl,
> >  
> >  	return true;
> >  }
> 
> + whitespace
> 
> > +/**
> > + * Asym capacity bits
> > + */
> > +struct asym_cap_data {
> > +	struct list_head link;
> > +	unsigned long    capacity;
> > +	struct cpumask   *cpu_mask;
> > +};
> 
> + whitespace
> 
> >  /*
> > + * Set of available CPUs grouped by their corresponding capacities
> > + * Each list entry contains a CPU mask reflecting CPUs that share the same
> > + * capacity.
> > + * The lifespan of data is unlimited.
> >   */
> > +static LIST_HEAD(asym_cap_list);
> >  
> > +/*
> > + * Verify whether given CPU at a given topology level belongs to a sched domain
> > + * that does span CPUs with different capacities.
> > + * Provides sd_flags reflecting the asymmetry scope.
> > + */
> > +static inline int
> > +asym_cpu_capacity_classify(struct sched_domain_topology_level *tl, int cpu)
> > +{
> > +	int sd_asym_flags = SD_ASYM_CPUCAPACITY | SD_ASYM_CPUCAPACITY_FULL;
> > +	const struct cpumask *tl_mask = tl->mask(cpu);
> > +	struct asym_cap_data *entry;
> > +	int asym_cap_count = 0;
> > +
> > +	if (list_is_singular(&asym_cap_list))
> > +		goto leave;
> > +
> > +	list_for_each_entry(entry, &asym_cap_list, link) {
> > +		if (cpumask_intersects(tl_mask, entry->cpu_mask))
> > +			++asym_cap_count;
> > +		else
> > +			sd_asym_flags &= ~SD_ASYM_CPUCAPACITY_FULL;
> >  	}
> > +	WARN_ON_ONCE(!asym_cap_count);
> > +leave:
> > +	return asym_cap_count > 1 ? sd_asym_flags : 0;
> > +}
> >  
> >  
> 
> - whitespace
> 
> > +/*
> > + * Build-up/update list of CPUs grouped by their capacities
> > + */
> > +static void asym_cpu_capacity_scan(const struct cpumask *cpu_map)
> > +{
> > +	struct asym_cap_data *entry, *next;
> > +	int cpu;
> >  
> > +	if (!list_empty(&asym_cap_list))
> > +		list_for_each_entry(entry, &asym_cap_list, link)
> > +			cpumask_clear(entry->cpu_mask);
> 
> two nits:
> 
>  - the if() needs { } because while what follows is strictly a single
>    statement, it is multi-line, so coding style requires { }.
> 
>  - the if() is strictly superfluous, if the list is empty the
>    list_for_each_entry() iteration already doesn't do anything.
> 
> >  
> > +	entry = list_first_entry_or_null(&asym_cap_list,
> > +			struct asym_cap_data, link);
> 
> Please align line-breaks at the most nested (, vim can help you do this
> with: set cino=(0:0, if you're using that other editor, I'm sure you can
> convince it to align properly too :-)
> 
> >  
> > +	for_each_cpu(cpu, cpu_map) {
> > +		unsigned long capacity = arch_scale_cpu_capacity(cpu);
> >  
> > +		if (entry && capacity == entry->capacity)
> > +			goto next;
> >  
> > +		list_for_each_entry(entry, &asym_cap_list, link)
> > +			if (capacity == entry->capacity)
> > +				goto next;
> 
> { } again
> 
> > +
> > +		entry = kzalloc(sizeof(*entry) + cpumask_size(), GFP_KERNEL);
> > +		if (entry) {
> > +			entry->capacity = capacity;
> > +			entry->cpu_mask = (struct cpumask *)((char *)entry +
> > +					   sizeof(*entry));
> 
> alignment again
> 
> > +			list_add(&entry->link, &asym_cap_list);
> >  		}
> > +		WARN_ONCE(!entry,
> > +		    "Failed to allocate memory for capacity asymmetry detection\n");
> 
> alignment again
> 
> (also, eeew, if this lives, perhaps a find_asym_data(capacity) helper
> might make it better:
> 
> 		if (!entry || entry->capacity != capacity)
> 			entry = find_asym_data(capacity);
> )
> 
> > +next:
> > +		__cpumask_set_cpu(cpu, entry->cpu_mask);
> >  	}
> >  
> > +	list_for_each_entry_safe(entry, next, &asym_cap_list, link) {
> > +		if (cpumask_empty(entry->cpu_mask)) {
> > +			list_del(&entry->link);
> > +			kfree(entry);
> > +		}
> > +	}
> 
> See, this has { }
> 
> >  }