Re: [RFC PATCH 1/2] sched/fair: introduce new scheduler group type group_parked
From: Tobias Huschle
Date: Mon Dec 09 2024 - 03:18:23 EST
On 05/12/2024 19:04, Shrikanth Hegde wrote:
On 12/4/24 16:51, Tobias Huschle wrote:
A parked CPU is considered to be flagged as unsuitable to process
workload at the moment, but might be become usable anytime. Depending on
the necessity for additional computation power and/or available capacity
of the underlying hardware.
A scheduler group is considered to be parked if it only contains parked
CPUs. A parked scheduler group is considered to be busier than another
if it runs more tasks than the other parked scheduler group.
Indicators whether a CPU should be parked depend on the underlying
hardware and must be considered to be architecture dependent.
Therefore the check whether a CPU is parked is architecture specific.
For architectures not relying on this feature, the check is a NOP.
This is more efficient and non-disruptive compared to CPU hotplug in
environments where such changes can be necessary on a frequent basis.
Signed-off-by: Tobias Huschle <huschle@xxxxxxxxxxxxx>
---
include/linux/sched/topology.h | 20 ++++++
kernel/sched/core.c | 10 ++-
kernel/sched/fair.c | 122 ++++++++++++++++++++++++++-------
3 files changed, 127 insertions(+), 25 deletions(-)
diff --git a/include/linux/sched/topology.h b/include/linux/sched/
topology.h
index 4237daa5ac7a..cfe3c59bc329 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -270,6 +270,26 @@ unsigned long arch_scale_cpu_capacity(int cpu)
}
#endif
+#ifndef arch_cpu_parked
+/**
+ * arch_cpu_parked - Check if a given CPU is currently parked.
+ *
+ * A parked CPU cannot run any kind of workload since underlying
+ * physical CPU should not be used at the moment .
+ *
+ * @cpu: the CPU in question.
+ *
+ * By default assume CPU is not parked
+ *
+ * Return: Parked state of CPU
+ */
+static __always_inline
+unsigned long arch_cpu_parked(int cpu)
bool instead?
+1
+{
+ return false;
+}
+#endif
+
#ifndef arch_scale_hw_pressure
static __always_inline
unsigned long arch_scale_hw_pressure(int cpu)
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 1dee3f5ef940..8f9aeb97c396 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2437,7 +2437,7 @@ static inline bool is_cpu_allowed(struct
task_struct *p, int cpu)
/* Non kernel threads are not allowed during either online or
offline. */
if (!(p->flags & PF_KTHREAD))
- return cpu_active(cpu);
+ return !arch_cpu_parked(cpu) && cpu_active(cpu);
/* KTHREAD_IS_PER_CPU is always allowed. */
if (kthread_is_per_cpu(p))
@@ -2447,6 +2447,10 @@ static inline bool is_cpu_allowed(struct
task_struct *p, int cpu)
if (cpu_dying(cpu))
return false;
+ /* CPU should be avoided at the moment */
+ if (arch_cpu_parked(cpu))
+ return false;
+
/* But are allowed during online. */
return cpu_online(cpu);
}
@@ -3924,6 +3928,10 @@ static inline bool ttwu_queue_cond(struct
task_struct *p, int cpu)
if (task_on_scx(p))
return false;
+ /* The task should not be queued onto a parked CPU. */
+ if (arch_cpu_parked(cpu))
+ return false;
+
When it comes here, likely cpu is not parked since wakeup path has those
checks.
+1
/*
* Do not complicate things with the async wake_list while the
CPU is
* in hotplug state.
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 4283c818bbd1..fa1c19d285de 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7415,6 +7415,9 @@ static int wake_affine(struct sched_domain *sd,
struct task_struct *p,
{
int target = nr_cpumask_bits;
+ if (arch_cpu_parked(target))
+ return prev_cpu;
+
if (sched_feat(WA_IDLE))
target = wake_affine_idle(this_cpu, prev_cpu, sync);
@@ -7454,6 +7457,9 @@ sched_balance_find_dst_group_cpu(struct
sched_group *group, struct task_struct *
for_each_cpu_and(i, sched_group_span(group), p->cpus_ptr) {
struct rq *rq = cpu_rq(i);
+ if (arch_cpu_parked(i))
+ continue;
+
if (!sched_core_cookie_match(rq, p))
continue;
@@ -7546,10 +7552,14 @@ static inline int
sched_balance_find_dst_cpu(struct sched_domain *sd, struct tas
return new_cpu;
}
+static inline bool is_idle_cpu_allowed(int cpu)
+{
+ return !arch_cpu_parked(cpu) && (available_idle_cpu(cpu) ||
sched_idle_cpu(cpu));
+}
How about adding below code, it could simplify the code quite a bit. no?
sched_idle_rq also might need the same check though.
+++ b/kernel/sched/syscalls.c
@@ -214,6 +214,9 @@ int idle_cpu(int cpu)
return 0;
#endif
+ if (arch_cpu_parked(cpu))
+ return 0;
+
return 1;
}
will give that one a go
+
static inline int __select_idle_cpu(int cpu, struct task_struct *p)
{
- if ((available_idle_cpu(cpu) || sched_idle_cpu(cpu)) &&
- sched_cpu_cookie_match(cpu_rq(cpu), p))
+ if (is_idle_cpu_allowed(cpu) &&
sched_cpu_cookie_match(cpu_rq(cpu), p))
return cpu;
return -1;
@@ -7657,7 +7667,7 @@ static int select_idle_smt(struct task_struct
*p, struct sched_domain *sd, int t
*/
if (!cpumask_test_cpu(cpu, sched_domain_span(sd)))
continue;
- if (available_idle_cpu(cpu) || sched_idle_cpu(cpu))
+ if (is_idle_cpu_allowed(cpu))
return cpu;
}
@@ -7779,7 +7789,7 @@ select_idle_capacity(struct task_struct *p,
struct sched_domain *sd, int target)
for_each_cpu_wrap(cpu, cpus, target) {
unsigned long cpu_cap = capacity_of(cpu);
- if (!available_idle_cpu(cpu) && !sched_idle_cpu(cpu))
+ if (!is_idle_cpu_allowed(cpu))
continue;
fits = util_fits_cpu(task_util, util_min, util_max, cpu);
@@ -7850,7 +7860,7 @@ static int select_idle_sibling(struct
task_struct *p, int prev, int target)
*/
lockdep_assert_irqs_disabled();
- if ((available_idle_cpu(target) || sched_idle_cpu(target)) &&
+ if (is_idle_cpu_allowed(target) &&
asym_fits_cpu(task_util, util_min, util_max, target))
return target;
@@ -7858,7 +7868,7 @@ static int select_idle_sibling(struct
task_struct *p, int prev, int target)
* If the previous CPU is cache affine and idle, don't be stupid:
*/
if (prev != target && cpus_share_cache(prev, target) &&
- (available_idle_cpu(prev) || sched_idle_cpu(prev)) &&
+ is_idle_cpu_allowed(prev) &&
asym_fits_cpu(task_util, util_min, util_max, prev)) {
if (!static_branch_unlikely(&sched_cluster_active) ||
@@ -7890,7 +7900,7 @@ static int select_idle_sibling(struct
task_struct *p, int prev, int target)
if (recent_used_cpu != prev &&
recent_used_cpu != target &&
cpus_share_cache(recent_used_cpu, target) &&
- (available_idle_cpu(recent_used_cpu) ||
sched_idle_cpu(recent_used_cpu)) &&
+ is_idle_cpu_allowed(recent_used_cpu) &&
cpumask_test_cpu(recent_used_cpu, p->cpus_ptr) &&
asym_fits_cpu(task_util, util_min, util_max,
recent_used_cpu)) {
@@ -9198,7 +9208,12 @@ enum group_type {
* The CPU is overloaded and can't provide expected CPU cycles
to all
* tasks.
*/
- group_overloaded
+ group_overloaded,
+ /*
+ * The CPU should be avoided as it can't provide expected CPU cycles
+ * even for small amounts of workload.
+ */
+ group_parked
};
enum migration_type {
@@ -9498,7 +9513,7 @@ static int detach_tasks(struct lb_env *env)
* Source run queue has been emptied by another CPU, clear
* LBF_ALL_PINNED flag as we will not test any task.
*/
- if (env->src_rq->nr_running <= 1) {
+ if (env->src_rq->nr_running <= 1 && !arch_cpu_parked(env-
>src_cpu)) {
env->flags &= ~LBF_ALL_PINNED;
return 0;
}
@@ -9511,7 +9526,7 @@ static int detach_tasks(struct lb_env *env)
* We don't want to steal all, otherwise we may be treated
likewise,
* which could at worst lead to a livelock crash.
*/
- if (env->idle && env->src_rq->nr_running <= 1)
+ if (env->idle && env->src_rq->nr_running <= 1 && !
arch_cpu_parked(env->src_cpu))
break;
env->loop++;
@@ -9870,6 +9885,8 @@ struct sg_lb_stats {
unsigned long group_runnable; /* Total runnable time over
the CPUs of the group */
unsigned int sum_nr_running; /* Nr of all tasks running
in the group */
unsigned int sum_h_nr_running; /* Nr of CFS tasks running
in the group */
+ unsigned int sum_nr_parked;
+ unsigned int parked_cpus;
Can you please explain why you need two of these? Is it to identify the
group with most parked cpus? maybe comments is needed.
parked_cpus counts how many CPUs are parked in a scheduler group, which
is used to determine if a scheduler group consists of only parked CPUs.
sum_nr_parked is meant to be the tie-breaker if there are multiple
parked scheduler groups. Mind you, a scheduler group is only considered
parked if all included CPUs are parked.
unsigned int idle_cpus; /* Nr of idle
CPUs in the group */
unsigned int group_weight;
enum group_type group_type;
@@ -10127,6 +10144,9 @@ group_type group_classify(unsigned int
imbalance_pct,
struct sched_group *group,
struct sg_lb_stats *sgs)
{
+ if (sgs->parked_cpus)
+ return group_parked;
+
if (group_is_overloaded(imbalance_pct, sgs))
return group_overloaded;
@@ -10328,10 +10348,15 @@ static inline void update_sg_lb_stats(struct
lb_env *env,
sgs->nr_numa_running += rq->nr_numa_running;
sgs->nr_preferred_running += rq->nr_preferred_running;
#endif
+
+ if (rq->cfs.h_nr_running) {
+ sgs->parked_cpus += arch_cpu_parked(i);
+ sgs->sum_nr_parked += arch_cpu_parked(i) * rq-
>cfs.h_nr_running;
+ }
/*
* No need to call idle_cpu() if nr_running is not 0
*/
- if (!nr_running && idle_cpu(i)) {
+ if (!nr_running && idle_cpu(i) && !arch_cpu_parked(i)) {
sgs->idle_cpus++;
/* Idle cpu can't have misfit task */
continue;
@@ -10355,7 +10380,14 @@ static inline void update_sg_lb_stats(struct
lb_env *env,
sgs->group_capacity = group->sgc->capacity;
- sgs->group_weight = group->group_weight;
+ sgs->group_weight = group->group_weight - sgs->parked_cpus;
+
+ /*
+ * Only a subset of the group is parked, so the group itself has the
+ * capability to potentially pull tasks
+ */
+ if (sgs->parked_cpus < group->group_weight)
+ sgs->parked_cpus = 0;
Say you had a group with 4 cpus and 2 were parked CPUs. Now the
group_weight will be 2 and it will be marked as parked. whereas if 1 CPU
is parked group will not be marked as parked. That seems wrong.
sgs->group_weight = group->group_weight - sgs->parked_cpus;
--> that line would need to go or be moved, my train of thought was,
that parked CPUs should not contribute to the weight of a group
instead mark it as parked and use the parked_cpus number to compare no?
The reasoning behind not marking partially parked groups as parked is
that those groups still have the potential to pull tasks to its
non-parked CPUs. If those partially parked groups get flagged as parked,
the non-parked groups will try to pull tasks, which is not ideal.
Instead, the partially parked group should move all tasks internally to
its non-parked CPUs. Those might then get overloaded and only then, the
other non-parked groups should start pulling.
/* Check if dst CPU is idle and preferred to this group */
if (!local_group && env->idle && sgs->sum_h_nr_running &&
@@ -10422,6 +10454,8 @@ static bool update_sd_pick_busiest(struct
lb_env *env,
*/
switch (sgs->group_type) {
+ case group_parked:
+ return sgs->sum_nr_parked > busiest->sum_nr_parked;
case group_overloaded:
/* Select the overloaded group with highest avg_load. */
return sgs->avg_load > busiest->avg_load;
@@ -10633,6 +10667,9 @@ static inline void
update_sg_wakeup_stats(struct sched_domain *sd,
nr_running = rq->nr_running - local;
sgs->sum_nr_running += nr_running;
+ sgs->parked_cpus += arch_cpu_parked(i);
+ sgs->sum_nr_parked += arch_cpu_parked(i) * rq->cfs.h_nr_running;
+
/*
* No need to call idle_cpu_without() if nr_running is not 0
*/
@@ -10649,7 +10686,14 @@ static inline void
update_sg_wakeup_stats(struct sched_domain *sd,
sgs->group_capacity = group->sgc->capacity;
- sgs->group_weight = group->group_weight;
+ sgs->group_weight = group->group_weight - sgs->parked_cpus;
+
+ /*
+ * Only a subset of the group is parked, so the group itself has the
+ * capability to potentially pull tasks
+ */
+ if (sgs->parked_cpus < group->group_weight)
+ sgs->parked_cpus = 0;
same comment as above.
+1
sgs->group_type = group_classify(sd->imbalance_pct, group, sgs);
@@ -10680,6 +10724,8 @@ static bool update_pick_idlest(struct
sched_group *idlest,
*/
switch (sgs->group_type) {
+ case group_parked:
+ return false;
Why not use the parked_cpus to compare?
It doesn't make much sense to determine whether one parked group might
be more idle that another. Neither of them should pull tasks (iff the
assumption is kept, that only groups that contain only parked CPUs are
considered to be parked.
case group_overloaded:
case group_fully_busy:
/* Select the group with lowest avg_load. */
@@ -10730,7 +10776,7 @@ sched_balance_find_dst_group(struct
sched_domain *sd, struct task_struct *p, int
unsigned long imbalance;
struct sg_lb_stats idlest_sgs = {
.avg_load = UINT_MAX,
- .group_type = group_overloaded,
+ .group_type = group_parked,
};
do {
@@ -10788,6 +10834,8 @@ sched_balance_find_dst_group(struct
sched_domain *sd, struct task_struct *p, int
return idlest;
switch (local_sgs.group_type) {
+ case group_parked:
+ return idlest;
case group_overloaded:
case group_fully_busy:
@@ -11039,6 +11087,12 @@ static inline void calculate_imbalance(struct
lb_env *env, struct sd_lb_stats *s
local = &sds->local_stat;
busiest = &sds->busiest_stat;
+ if (busiest->group_type == group_parked) {
+ env->migration_type = migrate_task;
+ env->imbalance = busiest->sum_nr_parked;
+ return;
+ }
+
if (busiest->group_type == group_misfit_task) {
if (env->sd->flags & SD_ASYM_CPUCAPACITY) {
/* Set imbalance to allow misfit tasks to be balanced. */
@@ -11207,13 +11261,14 @@ static inline void
calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
/*
* Decision matrix according to the local and busiest group type:
*
- * busiest \ local has_spare fully_busy misfit asym imbalanced
overloaded
- * has_spare nr_idle balanced N/A N/A balanced balanced
- * fully_busy nr_idle nr_idle N/A N/A balanced balanced
- * misfit_task force N/A N/A N/A N/A N/A
- * asym_packing force force N/A N/A force force
- * imbalanced force force N/A N/A force force
- * overloaded force force N/A N/A force avg_load
+ * busiest \ local has_spare fully_busy misfit asym imbalanced
overloaded parked
+ * has_spare nr_idle balanced N/A N/A balanced
balanced balanced
+ * fully_busy nr_idle nr_idle N/A N/A balanced
balanced balanced
+ * misfit_task force N/A N/A N/A N/A N/
A N/A
+ * asym_packing force force N/A N/A force
force balanced
+ * imbalanced force force N/A N/A force
force balanced
+ * overloaded force force N/A N/A force
avg_load balanced
+ * parked force force N/A N/A force
force nr_tasks
If i see the code below, if local is parked, it always goes to balanced.
how it is nr_tasks? am i reading this table wrong?
update_sd_lb_stats ends up calling update_sd_pick_busiest which then
compares the number of tasks. But re-reading it I got the comment wrong
as it does not describe how the busiest group is defined but only how
busiest compares to local.
*
* N/A : Not Applicable because already filtered while updating
* statistics.
@@ -11222,6 +11277,8 @@ static inline void calculate_imbalance(struct
lb_env *env, struct sd_lb_stats *s
* avg_load : Only if imbalance is significant enough.
* nr_idle : dst_cpu is not busy and the number of idle CPUs is quite
* different in groups.
+ * nr_task : balancing can go either way depending on the number of
running tasks
+ * per group
*/
/**
@@ -11252,6 +11309,13 @@ static struct sched_group
*sched_balance_find_src_group(struct lb_env *env)
goto out_balanced;
busiest = &sds.busiest_stat;
+ local = &sds.local_stat;
+
+ if (local->group_type == group_parked)
+ goto out_balanced;
+
+ if (busiest->group_type == group_parked)
+ goto force_balance;
/* Misfit tasks should be dealt with regardless of the avg load */
if (busiest->group_type == group_misfit_task)
@@ -11273,7 +11337,6 @@ static struct sched_group
*sched_balance_find_src_group(struct lb_env *env)
if (busiest->group_type == group_imbalanced)
goto force_balance;
- local = &sds.local_stat;
/*
* If the local group is busier than the selected busiest group
* don't try and pull any tasks.
@@ -11386,6 +11449,8 @@ static struct rq
*sched_balance_find_src_rq(struct lb_env *env,
enum fbq_type rt;
rq = cpu_rq(i);
+ if (arch_cpu_parked(i) && rq->cfs.h_nr_running)
+ return rq;
rt = fbq_classify_rq(rq);
/*
@@ -11556,6 +11621,9 @@ static int need_active_balance(struct lb_env
*env)
{
struct sched_domain *sd = env->sd;
+ if (arch_cpu_parked(env->src_cpu) && !idle_cpu(env->src_cpu))
+ return 1;
+
if (asym_active_balance(env))
return 1;
@@ -11589,6 +11657,9 @@ static int should_we_balance(struct lb_env *env)
struct sched_group *sg = env->sd->groups;
int cpu, idle_smt = -1;
+ if (arch_cpu_parked(env->dst_cpu))
+ return 0;
+
/*
* Ensure the balancing environment is consistent; can happen
* when the softirq triggers 'during' hotplug.
@@ -11612,7 +11683,7 @@ static int should_we_balance(struct lb_env *env)
cpumask_copy(swb_cpus, group_balance_mask(sg));
/* Try to find first idle CPU */
for_each_cpu_and(cpu, swb_cpus, env->cpus) {
- if (!idle_cpu(cpu))
+ if (!idle_cpu(cpu) || arch_cpu_parked(cpu))
continue;
/*
@@ -11707,7 +11778,7 @@ static int sched_balance_rq(int this_cpu,
struct rq *this_rq,
ld_moved = 0;
/* Clear this flag as soon as we find a pullable task */
env.flags |= LBF_ALL_PINNED;
- if (busiest->nr_running > 1) {
+ if (busiest->nr_running > 1 || arch_cpu_parked(busiest->cpu)) {
/*
* Attempt to move tasks. If sched_balance_find_src_group
has found
* an imbalance but busiest->nr_running <= 1, the group is
@@ -12721,6 +12792,9 @@ static int sched_balance_newidle(struct rq
*this_rq, struct rq_flags *rf)
update_misfit_status(NULL, this_rq);
+ if (arch_cpu_parked(this_cpu))
+ return 0;
+
/*
* There is a task waiting to run. No need to search for one.
* Return 0; the task will be enqueued when switching to idle.