Capacity awareness for SCHED_DEADLINE
Dietmar Eggemann
reviewerv2 cover Capacity awareness for SCHED_DEADLINE
The SCHED_DEADLINE (DL) admission control does not work correctly on heterogeneous (asymmetric CPU capacity) systems such as Arm big.LITTLE or DynamIQ.
Let's fix this by explicitly considering CPU capacity in DL admission control and task migration.
The DL sched class now attempts to avoid missing task deadlines due to smaller CPU (CPU capacity < 1024) not being capable enough to finish a task in time. It does so by trying to place a task so that its CPU capacity scaled deadline is not smaller than its runtime.
This patch-set only supports capacity awareness in idle scenarios (cpudl::free_cpus not empty). Capacity awareness for non-idle cases should be added in a later series.
Changes v1 [1] -> v2:
Discussion about capacity awareness in idle and non-idle scenarios indicated that the current patch-set only supports the former.
Per-patch changes:
(1) Use rq->cpu_capacity_orig or capacity_orig_of() instead of
arch_scale_cpu_capacity() [patch 1,6/6]
(2) Optimize dl_bw_cpus(), i.e. return weight of rd->span if rd->span &sube cpu_active_mask [patch 2/6]
(3) Replace rd_capacity() with dl_bw_capacity(). [patch 3/6]
Changes RFC [2] -> v1:
Only use static values for CPU bandwidth (sched_dl_entity::dl_runtime, ::dl_deadline) and CPU capacity (arch_scale_cpu_capacity()) to fix DL admission control.
Dynamic values for CPU bandwidth (sched_dl_entity::runtime, ::deadline) and CPU capacity (capacity_of()) are considered to be more related to energy trade-off calculations which could be later introduced using the Energy Model.
Since the design of the DL and RT sched classes are very similar, the implementation follows the overall design of RT capacity awareness (commit 804d402fb6f6 ("sched/rt: Make RT capacity-aware")).
Per-patch changes:
(1) Store CPU capacity sum in the root domain during
build_sched_domains() [patch 1/4]
(2) Adjust to RT capacity awareness design [patch 3/4]
(3) Remove CPU capacity aware placement in switched_to_dl() (dl_migrate callback) [RFC patch 3/6]
Balance callbacks (push, pull) run only in schedule_tail() __schedule(), rt_mutex_setprio() or __sched_setscheduler(). DL throttling leads to a call to __dequeue_task_dl() which is not a full task dequeue. The task is still enqueued and only removed from the rq.
So a queue_balance_callback() call in update_curr_dl()-> __dequeue_task_dl() will not be followed by a balance_callback() call in one of the 4 functions mentioned above.
(4) Remove 'dynamic CPU bandwidth' consideration and only support 'static CPU bandwidth' (ratio between sched_dl_entity::dl_runtime and ::dl_deadline) [RFC patch 4/6]
(5) Remove modification to migration logic which tried to schedule small tasks on LITTLE CPUs [RFC patch 6/6]
[1] https://lore.kernel.org/r/[email protected]
[2] https://lore.kernel.org/r/[email protected]
The following rt-app testcase tailored to Arm64 Hikey960:
root@h960:~# cat /sys/devices/system/cpu/cpu*/cpu_capacity 462 462 462 462 1024 1024 1024 1024
shows the expected behavior.
According to the following condition in dl_task_fits_capacity()
cap_scale(dl_deadline, arch_scale_cpu_capacity(cpu)) >= dl_runtime
thread0-[0-3] are placed on a big CPUs whereas thread1-[0-3] run on a LITTLE CPU respectively.
...
"tasks" : {
"thread0" : {
"policy" : "SCHED_DEADLINE",
"instance" : 4,
"timer" : { "ref" : "unique0", "period" : 16000, "mode" : "absolute" }, "run" : 10000,
"dl-runtime" : 11000,
"dl-period" : 16000,
"dl-deadline" : 16000
},
"thread1" : {
"policy" : "SCHED_DEADLINE",
"instance" : 4,
"delay" : 1000,
"timer" : { "ref" : "unique1", "period" : 16000, "mode" : "absolute" }, "run" : 5500,
"dl-runtime" : 6500
"dl-period" : 16000,
"dl-deadline" : 16000
}
...
Tests were run with Performance CPUfreq governor so that the Schedutil CPUfreq governor DL threads (sugov:[0,4]), necessary on a slow-switching platform like Hikey960, do not interfere with the rt-app test tasks. Using Schedutil would require to lower the number of tasks to 3 instances each.
Dietmar Eggemann (3):
sched/topology: Store root domain CPU capacity sum sched/deadline: Optimize dl_bw_cpus() sched/deadline: Add dl_bw_capacity()
Luca Abeni (3):
sched/deadline: Improve admission control for asymmetric CPU
capacities
sched/deadline: Make DL capacity-aware sched/deadline: Implement fallback mechanism for !fit case
kernel/sched/cpudeadline.c | 23 +++++++++++ kernel/sched/deadline.c | 80 +++++++++++++++++++++++++++++--------- kernel/sched/sched.h | 22 +++++++++-- kernel/sched/topology.c | 15 +++++-- 4 files changed, 115 insertions(+), 25 deletions(-)
Signature · 1 line
2.17.1
Dietmar Eggemann
reviewerPATCH v2 1/6 sched/topology: Store root domain CPU capacity sum
Add sum of (original) CPU capacity of all member CPUs to root domain.
This is needed for capacity-aware SCHED_DEADLINE admission control.
--- kernel/sched/sched.h | 1 + kernel/sched/topology.c | 15 +++++++++++---- 2 files changed, 12 insertions(+), 4 deletions(-)
kernel/sched/sched.h +1 -0
@@ -803,6 +803,7 @@ struct root_domain {cpumask_var_t rto_mask;struct cpupri cpupri; +unsigned long sum_cpu_capacity;unsigned long max_cpu_capacity;/*
kernel/sched/topology.c +11 -4
@@ -2052,12 +2052,18 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att/* Attach the domains */ rcu_read_lock ();for_each_cpu (i, cpu_map) { +unsigned long cap; + rq =cpu_rq (i); sd = *per_cpu_ptr (d.sd, i); + cap = rq->cpu_capacity_orig;/* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */ -if (rq->cpu_capacity_orig >READ_ONCE (d.rd->max_cpu_capacity)) -WRITE_ONCE (d.rd->max_cpu_capacity, rq->cpu_capacity_orig); +if (cap >READ_ONCE (d.rd->max_cpu_capacity)) +WRITE_ONCE (d.rd->max_cpu_capacity, cap); + +WRITE_ONCE (d.rd->sum_cpu_capacity, +READ_ONCE (d.rd->sum_cpu_capacity) + cap);cpu_attach_domain (sd, d.rd, i); }
@@ -2067,8 +2073,9 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attstatic_branch_inc_cpuslocked (&sched_asym_cpucapacity);if (rq && sched_debug_enabled) { -pr_info ("root domain span: %*pbl (max cpu_capacity = %lu)\n" , -cpumask_pr_args (cpu_map), rq->rd->max_cpu_capacity); +pr_info ("root domain span: %*pbl (capacity = %lu max cpu_capacity = %lu)\n" , +cpumask_pr_args (cpu_map), rq->rd->sum_cpu_capacity, + rq->rd->max_cpu_capacity); } ret =0 ;
Signature · 1 line
2.17.1
Dietmar Eggemann
reviewerPATCH v2 2/6 sched/deadline: Optimize dl_bw_cpus()
In reply to Dietmar EggemannReturn the weight of the rd (root domain) span in case it is a subset of the cpu_active_mask.
Continue to compute the number of CPUs over rd span and cpu_active_mask when in hotplug.
--- kernel/sched/deadline.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-)
kernel/sched/deadline.c +7 -1
@@ -54,10 +54,16 @@ static inline struct dl_bw *dl_bw_of(int i)static inline int dl_bw_cpus (int i) {struct root_domain *rd =cpu_rq (i)->rd; -int cpus =0 ; +int cpus;RCU_LOCKDEP_WARN (!rcu_read_lock_sched_held (),"sched RCU must be held" ); + +if (cpumask_subset (rd->span, cpu_active_mask)) +return cpumask_weight (rd->span); + + cpus =0 ; +for_each_cpu_and (i, rd->span, cpu_active_mask) cpus++;
Signature · 1 line
2.17.1
Re: [PATCH v2 2/6] sched/deadline: Optimize dl_bw_cpus()
Quoted 18 lines · Dietmar Eggemann
Return the weight of the rd (root domain) span in case it is a subset of the
cpu_active_mask.Continue to compute the number of CPUs over rd span and
cpu_active_maskwhen in hotplug.Signed-off-by Dietmar Eggemann <[email protected]>--- kernel/sched/deadline.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-)kernel/sched/deadline.c +0
-0@@ -54,10 +54,16 @@ static inline struct dl_bw *dl_bw_of(int i)static inline int dl_bw_cpus (int i) {
kernel/sched/deadline.c static inline struct dl_bw *dl_bw_of(int i) · line 64
Quoted 10 lines
kernel/sched/deadline.c +5
-1struct root_domain *rd =cpu_rq (i)->rd; -int cpus =0 ; +int cpus;RCU_LOCKDEP_WARN (!rcu_read_lock_sched_held (),"sched RCU must be held" ); + +if (cpumask_subset (rd->span, cpu_active_mask)) +return cpumask_weight (rd->span); +
Looks good to me. This is a nice optimization.
kernel/sched/deadline.c static inline struct dl_bw *dl_bw_of(int i) · line 69
Quoted 5 lines
kernel/sched/deadline.c +2
-0+ cpus =0 ; +for_each_cpu_and (i, rd->span, cpu_active_mask) cpus++;
Do you know why this check is in place? Is it only to cover the case of cpuset_cpu_inactive()->dl_cpu_busy()?
Thanks,
Pavan
Quoted 3 lines
Signature · 1 line
2.17.1
Signature · 2 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc. Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Dietmar Eggemann
reviewerRe: [PATCH v2 2/6] sched/deadline: Optimize dl_bw_cpus()
Quoted 1 line · Pavan Kondeti
On Mon, Apr 27, 2020 at 10:37:05AM +0200, Dietmar Eggemann wrote:
[..]
Quoted 20 lines
Quoted 7 lines
kernel/sched/deadline.c +0
-0@@ -54,10 +54,16 @@ static inline struct dl_bw *dl_bw_of(int i)static inline int dl_bw_cpus (int i) {kernel/sched/deadline.c static inline struct dl_bw *dl_bw_of(int i) · line 64
Quoted 10 lines
kernel/sched/deadline.c +5
-1struct root_domain *rd =cpu_rq (i)->rd; -int cpus =0 ; +int cpus;RCU_LOCKDEP_WARN (!rcu_read_lock_sched_held (),"sched RCU must be held" ); + +if (cpumask_subset (rd->span, cpu_active_mask)) +return cpumask_weight (rd->span); +Looks good to me. This is a nice optimization.
Quoted 7 lines
kernel/sched/deadline.c static inline struct dl_bw *dl_bw_of(int i) · line 69
Quoted 5 lines
kernel/sched/deadline.c +2
-0+ cpus =0 ; +for_each_cpu_and (i, rd->span, cpu_active_mask) cpus++;Do you know why this check is in place? Is it only to cover the case of cpuset_cpu_inactive()->dl_cpu_busy()?
It should cover:
(1) Preventing CPU hp when DL detects a possible overflow w/o the CPU:
sched_cpu_deactivate() -> cpuset_cpu_inactive() -> dl_cpu_busy() -> dl_bw_cpus() [now replaced by dl_bw_capacity()].
(2) DL Admission Control in CPU HP:
__sched_setscheduler() -> sched_dl_overflow() -> dl_bw_cpus()
[now + -> dl_bw_capacity()](3) In create/destroy exclusive cpusets scenarios (comment in set_cpus_allowed_dl(), although I wasn't able to provoke this so far:
do_set_cpus_allowed() -> p->sched_class->set_cpus_allowed() was never called when I ran a DL testcase and create/destroy exclusive cpusets at the same time?
Dietmar Eggemann
reviewerPATCH v2 3/6 sched/deadline: Add dl_bw_capacity()
In reply to Dietmar EggemannCapacity-aware SCHED_DEADLINE admission control needs rd (root domain) CPU capacity sum.
The design of this function follows that of dl_bw_cpus().
That is, return the rd CPU capacity sum in case the rd span a subset of the cpu_active_mask.
Compute the CPU capacity sum over rd span and cpu_active_mask when in hotplug.
--- kernel/sched/deadline.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+)
kernel/sched/deadline.c +24 -0
@@ -69,6 +69,25 @@ static inline int dl_bw_cpus(int i) return cpus; } + +static inline unsigned long dl_bw_capacity (int i) +{ +struct root_domain *rd =cpu_rq (i)->rd; +unsigned long cap; + +RCU_LOCKDEP_WARN (!rcu_read_lock_sched_held (), +"sched RCU must be held" ); + +if (cpumask_subset (rd->span, cpu_active_mask)) +return rd->sum_cpu_capacity; + + cap =0 ; + +for_each_cpu_and (i, rd->span, cpu_active_mask) + cap +=capacity_orig_of (i); + +return cap; +}#else static inline struct dl_bw *dl_bw_of (int i) {
@@ -79,6 +98,11 @@ static inline int dl_bw_cpus(int i) {return 1 ; } + +static inline unsigned long dl_bw_capacity (int i) +{ +return SCHED_CAPACITY_SCALE ; +}#endif static inline
Signature · 1 line
2.17.1
Dietmar Eggemann
reviewerRe: [PATCH v2 3/6] sched/deadline: Add dl_bw_capacity()
On 27/04/2020 10:37, Dietmar Eggemann wrote:
[...]
Quoted 17 lines
kernel/sched/deadline.c +9
-0@@ -69,6 +69,25 @@ static inline int dl_bw_cpus(int i)return cpus; } + +static inline unsigned long dl_bw_capacity (int i) +{ +struct root_domain *rd =cpu_rq (i)->rd; +unsigned long cap; + +RCU_LOCKDEP_WARN (!rcu_read_lock_sched_held (), +"sched RCU must be held" ); +
kernel/sched/deadline.c static inline int dl_bw_cpus(int i) · line 90
Quoted 10 lines
kernel/sched/deadline.c +10
-0+if (cpumask_subset (rd->span, cpu_active_mask)) +return rd->sum_cpu_capacity; + + cap =0 ; + +for_each_cpu_and (i, rd->span, cpu_active_mask) + cap +=capacity_orig_of (i); + +return cap; +}
There is an issue w/ excl. cpusets and cpuset.sched_load_balance=0. The latter is needed to demonstrate the problem since DL task affinity can't be altered.
A CPU in such a cpuset has its rq attached to def_root_domain which does not have its 'sum_cpu_capacity' properly set.
root@juno:~# bash root@juno:~# ps -eo comm,pid,class | grep bash bash 1661 TS bash 2040 TS bash 2176 TS <--
root@juno:~# echo 2176 > /sys/fs/cgroup/cpuset/B/tasks
root@juno:~# chrt -d --sched-runtime 8000 --sched-period 16000 -p 0 2176 chrt: failed to set pid 2176's policy: Device or resource busy
...sched_dl_overflow: [bash 2176] task_cpu=4 cpus_ptr=2,4-5dl_bw_capacity() CPU4 dflt_rd->sum_cpu_capacity=0 <-- !!! dflt_rd->span=2,4-5 cpu_active_mask=0-5
...
OTHA, rd->span is properly set due to 'cpumask_clear_cpu(rq->cpu, old_rd->span) and cpumask_set_cpu(rq->cpu, rd->span)' in rq_attach_root().
It's not possible to treat 'rd->sum_cpu_capacity' like 'rd->span' since the former changes between sched domain teardown/bringup w/ asymmetric CPU capacity.
What could be done is to return 'dl_bw_cpus(i) << SCHED_CAPACITY_SHIFT' w/ symmetric CPU capacity (of 1024) and to loop over rd->span otherwise. Latter includes symmetric cpusets w/ only little CPUs.
---8<---
kernel/sched/deadline.c +12 -8
@@ -70,24 +70,28 @@ static inline int dl_bw_cpus(int i) return cpus; } -static inline unsigned long dl_bw_capacity (int i) -{ +static inline unsigned long __dl_bw_capacity (int i) {struct root_domain *rd =cpu_rq (i)->rd; -unsigned long cap; +unsigned long cap =0 ;RCU_LOCKDEP_WARN (!rcu_read_lock_sched_held (),"sched RCU must be held" ); -if (cpumask_subset (rd->span, cpu_active_mask)) -return rd->sum_cpu_capacity; - - cap =0 ; -for_each_cpu_and (i, rd->span, cpu_active_mask) cap +=capacity_orig_of (i);return cap; } + +static inline unsigned long dl_bw_capacity (int i) +{ +if (!static_branch_unlikely (&sched_asym_cpucapacity) && +capacity_orig_of (i) ==SCHED_CAPACITY_SCALE ) { +return dl_bw_cpus (i) <<SCHED_CAPACITY_SHIFT ; + }else { +return __dl_bw_capacity (i); + } +}#else static inline struct dl_bw *dl_bw_of (int i) {
Signature · 1 line
2.17.1
Juri Lelli
maintainerRe: [PATCH v2 3/6] sched/deadline: Add dl_bw_capacity()
Quoted 36 lines · Dietmar Eggemann
On 27/04/2020 10:37, Dietmar Eggemann wrote:
[...]
Quoted 17 lines
kernel/sched/deadline.c +9
-0@@ -69,6 +69,25 @@ static inline int dl_bw_cpus(int i)return cpus; } + +static inline unsigned long dl_bw_capacity (int i) +{ +struct root_domain *rd =cpu_rq (i)->rd; +unsigned long cap; + +RCU_LOCKDEP_WARN (!rcu_read_lock_sched_held (), +"sched RCU must be held" ); +kernel/sched/deadline.c static inline int dl_bw_cpus(int i) · line 90
Quoted 10 lines
kernel/sched/deadline.c +10
-0+if (cpumask_subset (rd->span, cpu_active_mask)) +return rd->sum_cpu_capacity; + + cap =0 ; + +for_each_cpu_and (i, rd->span, cpu_active_mask) + cap +=capacity_orig_of (i); + +return cap; +}There is an issue w/ excl. cpusets and cpuset.sched_load_balance=0. The latter is needed to demonstrate the problem since DL task affinity can't be altered.
Quoted 2 lines
A CPU in such a cpuset has its rq attached to
def_root_domainwhich does not have its 'sum_cpu_capacity' properly set.
Hummm, but if sched_load_balance is disabled it means that we've now got a subset of CPUs which (from a DL AC pow) are partitioned. So, I'd tend to say that we actually want to check new tasks bw requirement against the available bandwidth of the particular CPU they happen to be running (and will continue to run) when setscheduler is called.
If then load balance is enabled again, AC check we did above should still be valid for all tasks admitted in the meantime, no?
Dietmar Eggemann
reviewerRe: [PATCH v2 3/6] sched/deadline: Add dl_bw_capacity()
Quoted 2 lines · Juri Lelli
Quoted 1 line · Dietmar Eggemann
On 27/04/2020 10:37, Dietmar Eggemann wrote:
[...]
Quoted 9 lines
Quoted 6 lines
There is an issue w/ excl. cpusets and cpuset.sched_load_balance=0. The latter is needed to demonstrate the problem since DL task affinity can't be altered.
A CPU in such a cpuset has its rq attached to
def_root_domainwhich does not have its 'sum_cpu_capacity' properly set.Hummm, but if
sched_load_balanceis disabled it means that we've now got a subset of CPUs which (from a DL AC pow) are partitioned. So, I'd tend
Yes, the CPUs of the cpuset w/ cpuset.sched_load_balance=0 (cpuset B in the example).
Quoted 3 lines
to say that we actually want to check new tasks bw requirement against the available bandwidth of the particular CPU they happen to be running (and will continue to run) when setscheduler is called.
By 'available bandwidth of the particular CPU' you refer to '\Sum_{cpu_rq(i)->rd->span} CPU capacity', right?
This is what this fix tries to achieve. Regardless whether cpu_rq(i)->rd is a 'real' rd or the def_root_domain, dl_bw_capacity() will now always return '\Sum_{cpu_rq(i)->rd->span} CPU capacity'
Quoted 2 lines
If then load balance is enabled again, AC check we did above should still be valid for all tasks admitted in the meantime, no?
Example (w/ this fix) on Juno [L b b L L L], capacity_orig_of(L)=446 :
mkdir /sys/fs/cgroup/cpuset/A
echo 0 > /sys/fs/cgroup/cpuset/A/cpuset.mems echo 1 > /sys/fs/cgroup/cpuset/A/cpuset.cpu_exclusive echo 0-2 > /sys/fs/cgroup/cpuset/A/cpuset.cpus
mkdir /sys/fs/cgroup/cpuset/B
echo 0 > /sys/fs/cgroup/cpuset/B/cpuset.mems echo 1 > /sys/fs/cgroup/cpuset/B/cpuset.cpu_exclusive echo 3-5 > /sys/fs/cgroup/cpuset/B/cpuset.cpus
echo 0 > /sys/fs/cgroup/cpuset/B/cpuset.sched_load_balance echo 0 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balance
echo $$ > /sys/fs/cgroup/cpuset/B/tasks
chrt -d --sched-runtime 8000 --sched-period 16000 -p 0 $$
...
[ 144.920102] __dl_bw_capacity CPU3 rd->span=3-5 return 1338 [ 144.925607] sched_dl_overflow: [bash 1999] task_cpu(p)=3 cap=1338 cpus_ptr=3-5 [ 144.932841] __dl_bw_capacity CPU3 rd->span=3-5 return 1338
...
echo 1 > /sys/fs/cgroup/cpuset/B/cpuset.sched_load_balance
echo $$ > /sys/fs/cgroup/cpuset/B/tasks
chrt -d --sched-runtime 8000 --sched-period 16000 -p 0 $$
...
[ 254.367982] __dl_bw_capacity CPU5 rd->span=3-5 return 1338 [ 254.373487] sched_dl_overflow: [bash 2052] task_cpu(p)=5 cap=1338 cpus_ptr=3-5 [ 254.380721] __dl_bw_capacity CPU5 rd->span=3-5 return 1338
...
Regardless of 'B/cpuset.sched_load_balance' '\Sum_{cpu_rq(i)->rd->span} CPU capacity' stays 1338 (3*446)
So IMHO, DL AC check stays intact.
Juri Lelli
maintainerRe: [PATCH v2 3/6] sched/deadline: Add dl_bw_capacity()
Quoted 19 lines · Dietmar Eggemann
Quoted 2 lines · Juri Lelli
Quoted 1 line · Dietmar Eggemann
On 27/04/2020 10:37, Dietmar Eggemann wrote:
[...]
Quoted 9 lines
Quoted 6 lines
There is an issue w/ excl. cpusets and cpuset.sched_load_balance=0. The latter is needed to demonstrate the problem since DL task affinity can't be altered.
A CPU in such a cpuset has its rq attached to
def_root_domainwhich does not have its 'sum_cpu_capacity' properly set.Hummm, but if
sched_load_balanceis disabled it means that we've now got a subset of CPUs which (from a DL AC pow) are partitioned. So, I'd tendYes, the CPUs of the cpuset w/ cpuset.sched_load_balance=0 (cpuset B in the example).
Quoted 6 lines
Quoted 3 lines
to say that we actually want to check new tasks bw requirement against the available bandwidth of the particular CPU they happen to be running (and will continue to run) when setscheduler is called.
By 'available bandwidth of the particular CPU' you refer to '\Sum_{cpu_rq(i)->rd->span} CPU capacity', right?
No. I was referring to the single CPU capacity. The capacity of the CPU where a task is running when setscheduler is called for it (and DL AC performed). See below, maybe more clear why I wondered about this case..
Quoted 22 lines
This is what this fix tries to achieve. Regardless whether cpu_rq(i)->rd is a 'real' rd or the
def_root_domain,dl_bw_capacity()will now always return '\Sum_{cpu_rq(i)->rd->span} CPU capacity'Quoted 2 lines
If then load balance is enabled again, AC check we did above should still be valid for all tasks admitted in the meantime, no?
Example (w/ this fix) on Juno [L b b L L L], capacity_orig_of(L)=446 :
mkdir
/sys/fs/cgroup/cpuset/A
echo 0 >/sys/fs/cgroup/cpuset/A/cpuset.memsecho 1 >/sys/fs/cgroup/cpuset/A/cpuset.cpu_exclusiveecho 0-2 >/sys/fs/cgroup/cpuset/A/cpuset.cpusmkdir
/sys/fs/cgroup/cpuset/B
echo 0 >/sys/fs/cgroup/cpuset/B/cpuset.memsecho 1 >/sys/fs/cgroup/cpuset/B/cpuset.cpu_exclusiveecho 3-5 >/sys/fs/cgroup/cpuset/B/cpuset.cpusecho 0 >
/sys/fs/cgroup/cpuset/B/cpuset.sched_load_balanceecho 0 >/sys/fs/cgroup/cpuset/cpuset.sched_load_balance
Quoted 6 lines
echo $$ >
/sys/fs/cgroup/cpuset/B/tasks
chrt -d --sched-runtime 8000 --sched-period 16000 -p 0 $$...
[ 144.920102] __dl_bw_capacity CPU3 rd->span=3-5 return 1338 [ 144.925607] sched_dl_overflow: [bash 1999] task_cpu(p)=3 cap=1338 cpus_ptr=3-5
So, here you are checking new task bw against 1338 which is 3*L capacity. However, since load balance is disabled at this point for 3-5, once admitted the task will only be able to run on CPU 3. Now, if more tasks on CPU 3 are admitted the same way (up to 1338) I believe they will start to experience deadline misses because only 446 will be actually available to them until load balance is enabled below and they are then free to migrate to CPUs 4 and 5.
Does it makes sense?
Quoted 19 lines
[ 144.932841] __dl_bw_capacity CPU3 rd->span=3-5 return 1338...
echo 1 >
/sys/fs/cgroup/cpuset/B/cpuset.sched_load_balanceecho $$ >
/sys/fs/cgroup/cpuset/B/tasks
chrt -d --sched-runtime 8000 --sched-period 16000 -p 0 $$...
[ 254.367982] __dl_bw_capacity CPU5 rd->span=3-5 return 1338 [ 254.373487] sched_dl_overflow: [bash 2052] task_cpu(p)=5 cap=1338 cpus_ptr=3-5 [ 254.380721] __dl_bw_capacity CPU5 rd->span=3-5 return 1338...
Regardless of 'B/cpuset.sched_load_balance' '\Sum_{cpu_rq(i)->rd->span} CPU capacity' stays 1338 (3*446)
So IMHO, DL AC check stays intact.
Dietmar Eggemann
reviewerRe: [PATCH v2 3/6] sched/deadline: Add dl_bw_capacity()
Quoted 4 lines · Juri Lelli
Quoted 3 lines · Dietmar Eggemann
Quoted 2 lines · Juri Lelli
Quoted 1 line · Dietmar Eggemann
On 27/04/2020 10:37, Dietmar Eggemann wrote:
[...]
Quoted 10 lines
Quoted 6 lines
Quoted 3 lines
to say that we actually want to check new tasks bw requirement against the available bandwidth of the particular CPU they happen to be running (and will continue to run) when setscheduler is called.
By 'available bandwidth of the particular CPU' you refer to '\Sum_{cpu_rq(i)->rd->span} CPU capacity', right?
No. I was referring to the single CPU capacity. The capacity of the CPU where a task is running when setscheduler is called for it (and DL AC performed). See below, maybe more clear why I wondered about this case..
OK, got it! I was just confused since I don't think that this patch introduced the issue.
Before the patch 'int cpus = dl_bw_cpus(task_cpu(p))' was used which returns the number of cpus on the (default) rd (n). So for a single CPU (1024) we use n*1024.
I wonder if a fix for that should be part of this patch-set?
[...]
Quoted 12 lines
Quoted 3 lines
...
[ 144.920102] __dl_bw_capacity CPU3 rd->span=3-5 return 1338 [ 144.925607] sched_dl_overflow: [bash 1999] task_cpu(p)=3 cap=1338 cpus_ptr=3-5So, here you are checking new task bw against 1338 which is 3*L capacity. However, since load balance is disabled at this point for 3-5, once admitted the task will only be able to run on CPU 3. Now, if more tasks on CPU 3 are admitted the same way (up to 1338) I believe they will start to experience deadline misses because only 446 will be actually available to them until load balance is enabled below and they are then free to migrate to CPUs 4 and 5.
Quoted 1 line
Does it makes sense?
Yes, it does.
So my first idea was to only consider the CPU (i.e. its CPU capacity) in case we detect 'cpu_rq(cpu)->rd == def_root_domain'?
In case I re-enable load-balancing on cpuset '/', we can't make a task in cpuset 'B' DL since we hit this in __sched_setscheduler():
4931 /*
4932 * Don't allow tasks with an affinity mask smaller than
4933 * the entire root_domain to become SCHED_DEADLINE.
...
4935 */
4936 if (!cpumask_subset(span, p->cpus_ptr) || ...
root@juno:~# echo 1 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balance root@juno:~# echo $$ > /sys/fs/cgroup/cpuset/B/tasks root@juno:~# chrt -d --sched-runtime 8000 --sched-period 16000 -p 0 $$ chrt: failed to set pid 2316's policy: Operation not permitted
So this task has to leave 'B' first I assume.
[...]
Juri Lelli
maintainerRe: [PATCH v2 3/6] sched/deadline: Add dl_bw_capacity()
Quoted 19 lines · Dietmar Eggemann
Quoted 4 lines · Juri Lelli
Quoted 3 lines · Dietmar Eggemann
Quoted 2 lines · Juri Lelli
Quoted 1 line · Dietmar Eggemann
On 27/04/2020 10:37, Dietmar Eggemann wrote:
[...]
Quoted 10 lines
Quoted 6 lines
Quoted 3 lines
to say that we actually want to check new tasks bw requirement against the available bandwidth of the particular CPU they happen to be running (and will continue to run) when setscheduler is called.
By 'available bandwidth of the particular CPU' you refer to '\Sum_{cpu_rq(i)->rd->span} CPU capacity', right?
No. I was referring to the single CPU capacity. The capacity of the CPU where a task is running when setscheduler is called for it (and DL AC performed). See below, maybe more clear why I wondered about this case..
Quoted 8 lines
OK, got it! I was just confused since I don't think that this patch introduced the issue.
Before the patch 'int cpus = dl_bw_cpus(task_cpu(p))' was used which returns the number of cpus on the (default) rd (n). So for a single CPU (1024) we use n*1024.
I wonder if a fix for that should be part of this patch-set?
Not really, I guess. As you said, the issue was there already. We can fix both situations with a subsequent patch. I just realized that we have a problem by reviewing this set, but not this set job to fix it.
While you are at changing this part, it might be good to put a comment (XXX fix this, or something) about the issue, so that we don't forget.
Quoted 31 lines
[...]
Quoted 12 lines
Quoted 3 lines
...
[ 144.920102] __dl_bw_capacity CPU3 rd->span=3-5 return 1338 [ 144.925607] sched_dl_overflow: [bash 1999] task_cpu(p)=3 cap=1338 cpus_ptr=3-5So, here you are checking new task bw against 1338 which is 3*L capacity. However, since load balance is disabled at this point for 3-5, once admitted the task will only be able to run on CPU 3. Now, if more tasks on CPU 3 are admitted the same way (up to 1338) I believe they will start to experience deadline misses because only 446 will be actually available to them until load balance is enabled below and they are then free to migrate to CPUs 4 and 5.
Quoted 1 line
Does it makes sense?
Yes, it does.
So my first idea was to only consider the CPU (i.e. its CPU capacity) in case we detect 'cpu_rq(cpu)->rd ==
def_root_domain'?In case I re-enable load-balancing on cpuset '/', we can't make a task in cpuset 'B' DL since we hit this in
__sched_setscheduler():4931 /*
4932 * Don't allow tasks with an affinity mask smaller than
4933 * the entireroot_domainto becomeSCHED_DEADLINE.
...
4935 */
4936 if (!cpumask_subset(span,p->cpus_ptr) || ...
Quoted 6 lines
root@juno:~# echo 1 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balance root@juno:~# echo $$ > /sys/fs/cgroup/cpuset/B/tasks root@juno:~# chrt -d --sched-runtime 8000 --sched-period 16000 -p 0 $$ chrt: failed to set pid 2316's policy: Operation not permittedSo this task has to leave 'B' first I assume.
Right, because the span is back to contain all cpus (load balancing enabled at root level), but tasks in 'B' still have affinity set to a subset of them.
Dietmar Eggemann
reviewerPATCH v2 4/6 sched/deadline: Improve admission control for asymmetric CPU capacities
In reply to Dietmar EggemannFrom: Luca Abeni <[email protected]>
The current SCHED_DEADLINE (DL) admission control ensures that
sum of reserved CPU bandwidth < x * M
where
x = /proc/sys/kernel/sched_rt_{runtime,period}_us M = # CPUs in root domain.
DL admission control works well for homogeneous systems where the capacity of all CPUs are equal (1024). I.e. bounded tardiness for DL and non-starvation of non-DL tasks is guaranteed.
But on heterogeneous systems where capacity of CPUs are different it could fail by over-allocating CPU time on smaller capacity CPUs.
On an Arm big.LITTLE/DynamIQ system DL tasks can easily starve other tasks making it unusable.
Fix this by explicitly considering the CPU capacity in the DL admission test by replacing M with the root domain CPU capacity sum.
--- kernel/sched/deadline.c | 30 +++++++++++++++++------------- kernel/sched/sched.h | 6 +++--- 2 files changed, 20 insertions(+), 16 deletions(-)
kernel/sched/deadline.c +17 -13
@@ -2581,11 +2581,12 @@ void sched_dl_do_global(void)int sched_dl_overflow (struct task_struct *p,int policy,const struct sched_attr *attr) { -struct dl_bw *dl_b =dl_bw_of (task_cpu (p));u64 period = attr->sched_period ?: attr->sched_deadline;u64 runtime = attr->sched_runtime;u64 new_bw =dl_policy (policy) ?to_ratio (period, runtime) :0 ; -int cpus, err =-1 ; +int cpus, err =-1 , cpu =task_cpu (p); +struct dl_bw *dl_b =dl_bw_of (cpu); +unsigned long cap;if (attr->sched_flags &SCHED_FLAG_SUGOV )return 0 ;
@@ -2600,15 +2601,17 @@ int sched_dl_overflow(struct task_struct *p, int policy,* allocated bandwidth of the container. */ raw_spin_lock (&dl_b->lock); - cpus =dl_bw_cpus (task_cpu (p)); + cpus =dl_bw_cpus (cpu); + cap =dl_bw_capacity (cpu); +if (dl_policy (policy) && !task_has_dl_policy (p) && - !__dl_overflow (dl_b, cpus,0 , new_bw)) { + !__dl_overflow (dl_b, cap,0 , new_bw)) {if (hrtimer_active (&p->dl.inactive_timer))__dl_sub (dl_b, p->dl.dl_bw, cpus);__dl_add (dl_b, new_bw, cpus); err =0 ; }else if (dl_policy (policy) &&task_has_dl_policy (p) && - !__dl_overflow (dl_b, cpus, p->dl.dl_bw, new_bw)) { + !__dl_overflow (dl_b, cap, p->dl.dl_bw, new_bw)) {/* * XXX this is slightly incorrect: when the task * utilization decreases, we should delay the total
@@ -2744,19 +2747,19 @@ bool dl_param_changed(struct task_struct *p, const struct sched_attr *attr)#ifdef CONFIG_SMP int dl_task_can_attach (struct task_struct *p,const struct cpumask *cs_cpus_allowed) { +unsigned long flags, cap;unsigned int dest_cpu;struct dl_bw *dl_b;bool overflow; -int cpus, ret; -unsigned long flags; +int ret; dest_cpu =cpumask_any_and (cpu_active_mask, cs_cpus_allowed);rcu_read_lock_sched (); dl_b =dl_bw_of (dest_cpu);raw_spin_lock_irqsave (&dl_b->lock, flags); - cpus =dl_bw_cpus (dest_cpu); - overflow =__dl_overflow (dl_b, cpus,0 , p->dl.dl_bw); + cap =dl_bw_capacity (dest_cpu); + overflow =__dl_overflow (dl_b, cap,0 , p->dl.dl_bw);if (overflow) { ret = -EBUSY ; }else {
@@ -2766,6 +2769,8 @@ int dl_task_can_attach(struct task_struct *p, const struct cpumask *cs_cpus_allo* We will free resources in the source root_domain * later on (see set_cpus_allowed_dl()). */ +int cpus =dl_bw_cpus (dest_cpu); +__dl_add (dl_b, p->dl.dl_bw, cpus); ret =0 ; }
@@ -2798,16 +2803,15 @@ int dl_cpuset_cpumask_can_shrink(const struct cpumask *cur,bool dl_cpu_busy (unsigned int cpu) { -unsigned long flags; +unsigned long flags, cap;struct dl_bw *dl_b;bool overflow; -int cpus;rcu_read_lock_sched (); dl_b =dl_bw_of (cpu);raw_spin_lock_irqsave (&dl_b->lock, flags); - cpus =dl_bw_cpus (cpu); - overflow =__dl_overflow (dl_b, cpus,0 ,0 ); + cap =dl_bw_capacity (cpu); + overflow =__dl_overflow (dl_b, cap,0 ,0 );raw_spin_unlock_irqrestore (&dl_b->lock, flags);rcu_read_unlock_sched ();
kernel/sched/sched.h +3 -3
@@ -310,11 +310,11 @@ void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus)__dl_update (dl_b, -((s32 )tsk_bw / cpus)); } -static inline -bool __dl_overflow (struct dl_bw *dl_b,int cpus,u64 old_bw,u64 new_bw) +static inline bool __dl_overflow (struct dl_bw *dl_b,unsigned long cap, +u64 old_bw,u64 new_bw) {return dl_b->bw !=-1 && - dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw; +cap_scale (dl_b->bw, cap) < dl_b->total_bw - old_bw + new_bw; }extern void init_dl_bw (struct dl_bw *dl_b);
Signature · 1 line
2.17.1
Dietmar Eggemann
reviewerPATCH v2 5/6 sched/deadline: Make DL capacity-aware
In reply to Dietmar EggemannFrom: Luca Abeni <[email protected]>
The current SCHED_DEADLINE (DL) scheduler uses a global EDF scheduling algorithm w/o considering CPU capacity or task utilization. This works well on homogeneous systems where DL tasks are guaranteed to have a bounded tardiness but presents issues on heterogeneous systems.
A DL task can migrate to a CPU which does not have enough CPU capacity to correctly serve the task (e.g. a task w/ 70ms runtime and 100ms period on a CPU w/ 512 capacity).
Add the DL fitness function dl_task_fits_capacity() for DL admission control on heterogeneous systems. A task fits onto a CPU if:
CPU original capacity / 1024 >= task runtime / task deadline
Use this function on heterogeneous systems to try to find a CPU which meets this criterion during task wakeup, push and offline migration.
On homogeneous systems the original behavior of the DL admission control should be retained.
--- kernel/sched/cpudeadline.c | 14 +++++++++++++- kernel/sched/deadline.c | 18 ++++++++++++++---- kernel/sched/sched.h | 15 +++++++++++++++ 3 files changed, 42 insertions(+), 5 deletions(-)
kernel/sched/cpudeadline.c +13 -1
@@ -121,7 +121,19 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,if (later_mask &&cpumask_and (later_mask, cp->free_cpus, p->cpus_ptr)) { -return 1 ; +int cpu; + +if (!static_branch_unlikely (&sched_asym_cpucapacity)) +return 1 ; + +/* Ensure the capacity of the CPUs fits the task. */ +for_each_cpu (cpu, later_mask) { +if (!dl_task_fits_capacity (p, cpu)) +cpumask_clear_cpu (cpu, later_mask); + } + +if (!cpumask_empty (later_mask)) +return 1 ; }else {int best_cpu =cpudl_maximum (cp);
kernel/sched/deadline.c +14 -4
@@ -1634,6 +1634,7 @@ static int select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) { struct task_struct *curr; +bool select_rq;struct rq *rq;if (sd_flag !=SD_BALANCE_WAKE )
@@ -1653,10 +1654,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq =unlikely (dl_task (curr)) && + (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ; + +/* +* Take the capacity of the CPU into account to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu); + +if (select_rq) {int target =find_later_rq (p); if (target != -1 &&
kernel/sched/sched.h +15 -0
@@ -317,6 +317,21 @@ static inline bool __dl_overflow(struct dl_bw *dl_b, unsigned long cap,cap_scale (dl_b->bw, cap) < dl_b->total_bw - old_bw + new_bw; } +/* +* Verify the fitness of task @p to run on @cpu taking into account the +* CPU original capacity and the runtime/deadline ratio of the task. +* +* The function will return true if the CPU original capacity of the +* @cpu scaled by SCHED_CAPACITY_SCALE >= runtime/deadline ratio of the +* task and false otherwise. +*/ +static inline bool dl_task_fits_capacity (struct task_struct *p,int cpu) +{ +unsigned long cap =arch_scale_cpu_capacity (cpu); + +return cap_scale (p->dl.dl_deadline, cap) >= p->dl.dl_runtime; +} +extern void init_dl_bw (struct dl_bw *dl_b);extern int sched_dl_global_validate (void );extern void sched_dl_do_global (void );
Signature · 1 line
2.17.1
Re: [PATCH v2 5/6] sched/deadline: Make DL capacity-aware
Quoted 80 lines · Dietmar Eggemann
From: Luca Abeni <[email protected]>
The current
SCHED_DEADLINE(DL) scheduler uses a global EDF scheduling algorithm w/o considering CPU capacity or task utilization. This works well on homogeneous systems where DL tasks are guaranteed to have a bounded tardiness but presents issues on heterogeneous systems.A DL task can migrate to a CPU which does not have enough CPU capacity to correctly serve the task (e.g. a task w/ 70ms runtime and 100ms period on a CPU w/ 512 capacity).
Add the DL fitness function
dl_task_fits_capacity()for DL admission control on heterogeneous systems. A task fits onto a CPU if:CPU original capacity / 1024 >= task runtime / task deadline
Use this function on heterogeneous systems to try to find a CPU which meets this criterion during task wakeup, push and offline migration.
On homogeneous systems the original behavior of the DL admission control should be retained.
Signed-off-by Luca Abeni <[email protected]>Signed-off-by Dietmar Eggemann <[email protected]>--- kernel/sched/cpudeadline.c | 14 +++++++++++++- kernel/sched/deadline.c | 18 ++++++++++++++---- kernel/sched/sched.h | 15 +++++++++++++++ 3 files changed, 42 insertions(+), 5 deletions(-)kernel/sched/cpudeadline.c +13
-1@@ -121,7 +121,19 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,if (later_mask &&cpumask_and (later_mask, cp->free_cpus, p->cpus_ptr)) { -return 1 ; +int cpu; + +if (!static_branch_unlikely (&sched_asym_cpucapacity)) +return 1 ; + +/* Ensure the capacity of the CPUs fits the task. */ +for_each_cpu (cpu, later_mask) { +if (!dl_task_fits_capacity (p, cpu)) +cpumask_clear_cpu (cpu, later_mask); + } + +if (!cpumask_empty (later_mask)) +return 1 ; }else {int best_cpu =cpudl_maximum (cp);kernel/sched/deadline.c +5
-4@@ -1634,6 +1634,7 @@ static int select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) { struct task_struct *curr; +bool select_rq;struct rq *rq;if (sd_flag !=SD_BALANCE_WAKE )@@ -1653,10 +1654,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq =unlikely (dl_task (curr)) && + (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ;
kernel/sched/deadline.c select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) · line 1670
Quoted 10 lines
kernel/sched/deadline.c +9
-0+ +/* +* Take the capacity of the CPU into account to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu); + +if (select_rq) {int target =find_later_rq (p);
I see that find_later_rq() checks if the previous CPU is part of later_mask and returns it immediately. So we don't migrate the task in the case where there previous CPU can't fit the task and there are no idle CPUs on which the task can fit. LGTM.
Quoted 15 lines
kernel/sched/deadline.c +0
-0if (target != -1 &&kernel/sched/sched.h +5
-0@@ -317,6 +317,21 @@ static inline bool __dl_overflow(struct dl_bw *dl_b, unsigned long cap,cap_scale (dl_b->bw, cap) < dl_b->total_bw - old_bw + new_bw; } +/* +* Verify the fitness of task @p to run on @cpu taking into account the +* CPU original capacity and the runtime/deadline ratio of the task. +* +* The function will return true if the CPU original capacity of the
kernel/sched/sched.h static inline bool __dl_overflow(struct dl_bw *dl_b, unsigned long cap, · line 334
Quoted 10 lines
kernel/sched/sched.h +10
-0+* @cpu scaled by SCHED_CAPACITY_SCALE >= runtime/deadline ratio of the +* task and false otherwise. +*/ +static inline bool dl_task_fits_capacity (struct task_struct *p,int cpu) +{ +unsigned long cap =arch_scale_cpu_capacity (cpu); + +return cap_scale (p->dl.dl_deadline, cap) >= p->dl.dl_runtime; +} +
This is same as
return p->dl.dl_bw >> (BW_SHIFT - SCHED_CAPACITY_SHIFT) <= cap
Correct? If yes, would it be better to use this?
Thanks,
Pavan
Signature · 2 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc. Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Dietmar Eggemann
reviewerRe: [PATCH v2 5/6] sched/deadline: Make DL capacity-aware
Quoted 2 lines · Pavan Kondeti
Quoted 1 line · Dietmar Eggemann
From: Luca Abeni <[email protected]>
[...]
Quoted 19 lines
Quoted 19 lines
kernel/sched/deadline.c +11
-4@@ -1653,10 +1654,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq =unlikely (dl_task (curr)) && + (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ; + +/* +* Take the capacity of the CPU into account to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu);
Quoted 8 lines
kernel/sched/deadline.c select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) · line 1670
Quoted 3 lines
kernel/sched/deadline.c +2
-0+ +if (select_rq) {int target =find_later_rq (p);I see that
find_later_rq()checks if the previous CPU is part oflater_maskand returns it immediately. So we don't migrate the task in the case where there previous CPU can't fit the task and there are no idle CPUs on which the task can fit. LGTM.
Hope I understand you here. I don't think that [patch 6/6] provides this already.
In case 'later_mask' has no fitting CPUs, 'max_cpu' is set in the otherwise empty 'later_mask'. But 'max_cpu' is not necessary task_cpu(p).
Example on Juno [L b b L L L] with thread0-0 (big task)
cpudl_find [thread0-0 2117] orig later_mask=0,3-4 later_mask=0
find_later_rq [thread0-0 2117] task_cpu=2 later_mask=0
A tweak could be added favor task_cpu(p) in case it is amongst the CPUs with the maximum capacity in cpudl_find() for the !fit case.
[...]
Quoted 18 lines
Quoted 5 lines
kernel/sched/sched.h +5
-0+/* +* Verify the fitness of task @p to run on @cpu taking into account the +* CPU original capacity and the runtime/deadline ratio of the task. +* +* The function will return true if the CPU original capacity of the kernel/sched/sched.h static inline bool __dl_overflow(struct dl_bw *dl_b, unsigned long cap, · line 334
Quoted 10 lines
kernel/sched/sched.h +10
-0+* @cpu scaled by SCHED_CAPACITY_SCALE >= runtime/deadline ratio of the +* task and false otherwise. +*/ +static inline bool dl_task_fits_capacity (struct task_struct *p,int cpu) +{ +unsigned long cap =arch_scale_cpu_capacity (cpu); + +return cap_scale (p->dl.dl_deadline, cap) >= p->dl.dl_runtime; +} +This is same as
Quoted 3 lines
return
p->dl.dl_bw>> (BW_SHIFT-SCHED_CAPACITY_SHIFT) <= capCorrect? If yes, would it be better to use this?
We could use sched_dl_entity::dl_density (dl_runtime / dl_deadline) but then I would have to export BW_SHIFT.
Re: [PATCH v2 5/6] sched/deadline: Make DL capacity-aware
Quoted 40 lines · Dietmar Eggemann
Quoted 2 lines · Pavan Kondeti
Quoted 1 line · Dietmar Eggemann
From: Luca Abeni <[email protected]>
[...]
Quoted 19 lines
Quoted 19 lines
kernel/sched/deadline.c +11
-4@@ -1653,10 +1654,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq =unlikely (dl_task (curr)) && + (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ; + +/* +* Take the capacity of the CPU into account to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu);Quoted 8 lines
kernel/sched/deadline.c select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) · line 1670
Quoted 3 lines
kernel/sched/deadline.c +2
-0+ +if (select_rq) {int target =find_later_rq (p);I see that
find_later_rq()checks if the previous CPU is part oflater_maskand returns it immediately. So we don't migrate the task in the case where there previous CPU can't fit the task and there are no idle CPUs on which the task can fit. LGTM.Hope I understand you here. I don't think that [patch 6/6] provides this already.
In case '
later_mask' has no fitting CPUs, 'max_cpu' is set in the otherwise empty 'later_mask'. But 'max_cpu' is not necessarytask_cpu(p).
Quoted 8 lines
Example on Juno [L b b L L L] with thread0-0 (big task)
cpudl_find [thread0-0 2117] orig later_mask=0,3-4 later_mask=0
find_later_rq[thread0-0 2117] task_cpu=2 later_mask=0A tweak could be added favor
task_cpu(p)in case it is amongst the CPUs with the maximum capacity incpudl_find()for the !fit case.
You are right. max_cpu can be other than task_cpu(p) in which case we migrate the task though it won't fit on the new CPU. While introducing capacity awareness in RT, Quais made the below change to avoid the migration. We can do something similar here also.
commit b28bc1e002c2 (sched/rt: Re-instate old behavior in select_task_rq_rt())
Quoted 20 lines
[...]
Quoted 18 lines
Quoted 5 lines
kernel/sched/sched.h +5
-0+/* +* Verify the fitness of task @p to run on @cpu taking into account the +* CPU original capacity and the runtime/deadline ratio of the task. +* +* The function will return true if the CPU original capacity of the kernel/sched/sched.h static inline bool __dl_overflow(struct dl_bw *dl_b, unsigned long cap, · line 334
Quoted 10 lines
kernel/sched/sched.h +10
-0+* @cpu scaled by SCHED_CAPACITY_SCALE >= runtime/deadline ratio of the +* task and false otherwise. +*/ +static inline bool dl_task_fits_capacity (struct task_struct *p,int cpu) +{ +unsigned long cap =arch_scale_cpu_capacity (cpu); + +return cap_scale (p->dl.dl_deadline, cap) >= p->dl.dl_runtime; +} +This is same as
Quoted 6 lines
Quoted 3 lines
return
p->dl.dl_bw>> (BW_SHIFT-SCHED_CAPACITY_SHIFT) <= capCorrect? If yes, would it be better to use this?
We could use
sched_dl_entity::dl_density(dl_runtime/dl_deadline) but then I would have to exportBW_SHIFT.
Yeah, I meant dl_denstity not dl_bw. Thanks for correcting me. I see that BW_SHIFT is defined in kernel/sched/sched.h
Thanks,
Pavan
Signature · 2 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc. Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Dietmar Eggemann
reviewerRe: [PATCH v2 5/6] sched/deadline: Make DL capacity-aware
Quoted 50 lines · Pavan Kondeti
Quoted 40 lines · Dietmar Eggemann
Quoted 2 lines · Pavan Kondeti
Quoted 1 line · Dietmar Eggemann
From: Luca Abeni <[email protected]>
[...]
Quoted 19 lines
Quoted 19 lines
kernel/sched/deadline.c +11
-4@@ -1653,10 +1654,19 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)* other hand, if it has a shorter deadline, we * try to make it stay here, it might be important. */ -if (unlikely (dl_task (curr)) && - (curr->nr_cpus_allowed <2 || - !dl_entity_preempt (&p->dl, &curr->dl)) && - (p->nr_cpus_allowed >1 )) { + select_rq =unlikely (dl_task (curr)) && + (curr->nr_cpus_allowed <2 || + !dl_entity_preempt (&p->dl, &curr->dl)) && + p->nr_cpus_allowed >1 ; + +/* +* Take the capacity of the CPU into account to +* ensure it fits the requirement of the task. +*/ +if (static_branch_unlikely (&sched_asym_cpucapacity)) + select_rq |= !dl_task_fits_capacity (p, cpu);Quoted 8 lines
kernel/sched/deadline.c select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) · line 1670
Quoted 3 lines
kernel/sched/deadline.c +2
-0+ +if (select_rq) {int target =find_later_rq (p);I see that
find_later_rq()checks if the previous CPU is part oflater_maskand returns it immediately. So we don't migrate the task in the case where there previous CPU can't fit the task and there are no idle CPUs on which the task can fit. LGTM.Hope I understand you here. I don't think that [patch 6/6] provides this already.
In case '
later_mask' has no fitting CPUs, 'max_cpu' is set in the otherwise empty 'later_mask'. But 'max_cpu' is not necessarytask_cpu(p).Quoted 8 lines
Example on Juno [L b b L L L] with thread0-0 (big task)
cpudl_find [thread0-0 2117] orig later_mask=0,3-4 later_mask=0
find_later_rq[thread0-0 2117] task_cpu=2 later_mask=0A tweak could be added favor
task_cpu(p)in case it is amongst the CPUs with the maximum capacity incpudl_find()for the !fit case.
Quoted 6 lines
You are right.
max_cpucan be other thantask_cpu(p)in which case we migrate the task though it won't fit on the new CPU. While introducing capacity awareness in RT, Quais made the below change to avoid the migration. We can do something similar here also.commit
b28bc1e002c2(sched/rt: Re-instate old behavior inselect_task_rq_rt())
I'm not sure something like this is necessary here.
With DL capacity awareness we reduce the later_mask returned by cpudl_find() in find_later_rq() to those idle CPUs which can handle p or in case there is none to (the/a) 'non-fitting CPU w/ max capacity'.
We just have to favor task_cpu(p) in [patch 6/6] in case it is part of the initial later_mask and among these 'non-fitting CPUs w/ max capacity'.
This will make sure that it gets chosen so find_later_rq() returns it before the 'for_each_domain()' loop.
And I guess we still want to migrate if there is a non-fitting CPU w/ a higher CPU capacity than task_cpu() (tri-gear).
@@ -137,7 +137,8 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
cap = capacity_orig_of(cpu);
- if (cap > max_cap) {
+ if (cap > max_cap ||
+ (cpu == task_cpu(p) && cap == max_cap)) {
max_cap = cap;
max_cpu = cpu;In case task_cpu() is not part of later_cpu, the 'max CPU capacity CPU' is returned as 'best_cpu'.
[...]
Dietmar Eggemann
reviewerPATCH v2 6/6 sched/deadline: Implement fallback mechanism for !fit case
In reply to Dietmar EggemannFrom: Luca Abeni <[email protected]>
When a task has a runtime that cannot be served within the scheduling deadline by any of the idle CPU (later_mask) the task is doomed to miss its deadline.
This can happen since the SCHED_DEADLINE admission control guarantees only bounded tardiness and not the hard respect of all deadlines. In this case try to select the idle CPU with the largest CPU capacity to minimize tardiness.
--- kernel/sched/cpudeadline.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-)
kernel/sched/cpudeadline.c +15 -4
@@ -121,19 +121,30 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,if (later_mask &&cpumask_and (later_mask, cp->free_cpus, p->cpus_ptr)) { -int cpu; +unsigned long cap, max_cap =0 ; +int cpu, max_cpu =-1 ;if (!static_branch_unlikely (&sched_asym_cpucapacity))return 1 ;/* Ensure the capacity of the CPUs fits the task. */ for_each_cpu (cpu, later_mask) { -if (!dl_task_fits_capacity (p, cpu)) +if (!dl_task_fits_capacity (p, cpu)) {cpumask_clear_cpu (cpu, later_mask); + + cap =capacity_orig_of (cpu); + +if (cap > max_cap) { + max_cap = cap; + max_cpu = cpu; + } + } } -if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask); + +return 1 ; }else {int best_cpu =cpudl_maximum (cp);
Signature · 1 line
2.17.1
Juri Lelli
maintainerRe: [PATCH v2 6/6] sched/deadline: Implement fallback mechanism for !fit case
Hi,
Quoted 41 lines · Dietmar Eggemann
From: Luca Abeni <[email protected]>
When a task has a runtime that cannot be served within the scheduling deadline by any of the idle CPU (
later_mask) the task is doomed to miss its deadline.This can happen since the
SCHED_DEADLINEadmission control guarantees only bounded tardiness and not the hard respect of all deadlines. In this case try to select the idle CPU with the largest CPU capacity to minimize tardiness.Signed-off-by Luca Abeni <[email protected]>Signed-off-by Dietmar Eggemann <[email protected]>--- kernel/sched/cpudeadline.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-)kernel/sched/cpudeadline.c +7
-2@@ -121,19 +121,30 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,if (later_mask &&cpumask_and (later_mask, cp->free_cpus, p->cpus_ptr)) { -int cpu; +unsigned long cap, max_cap =0 ; +int cpu, max_cpu =-1 ;if (!static_branch_unlikely (&sched_asym_cpucapacity))return 1 ;/* Ensure the capacity of the CPUs fits the task. */ for_each_cpu (cpu, later_mask) { -if (!dl_task_fits_capacity (p, cpu)) +if (!dl_task_fits_capacity (p, cpu)) {cpumask_clear_cpu (cpu, later_mask); + + cap =capacity_orig_of (cpu); + +if (cap > max_cap) {
kernel/sched/cpudeadline.c int cpudl_find(struct cpudl *cp, struct task_struct *p, · line 145
Quoted 10 lines
kernel/sched/cpudeadline.c +6
-2+ max_cap = cap; + max_cpu = cpu; + } + } } -if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask);
Think we touched upon this during v1 review, but I'm (still?) wondering if we can do a little better, still considering only free cpus.
Can't we get into a situation that some of the (once free) big cpus have been occupied by small tasks and now a big task enters the system and it only finds small cpus available, were it could have fit into bigs if small tasks were put onto small cpus?
I.e., shouldn't we always try to best fit among free cpus?
Thanks,
Juri
Re: [PATCH v2 6/6] sched/deadline: Implement fallback mechanism for !fit case
Hi Juri,
Quoted 16 lines · On Mon, 27 Apr 2020 15:34:38 +0200 Juri Lelli <[email protected]> wrote:
Hi,
Quoted 13 lines · Dietmar Eggemann
From: Luca Abeni <[email protected]>
When a task has a runtime that cannot be served within the scheduling deadline by any of the idle CPU (
later_mask) the task is doomed to miss its deadline.This can happen since the
SCHED_DEADLINEadmission control guarantees only bounded tardiness and not the hard respect of all deadlines. In this case try to select the idle CPU with the largest CPU capacity to minimize tardiness.Signed-off-by Luca Abeni <[email protected]>Signed-off-by Dietmar Eggemann <[email protected]>
[...]
Quoted 9 lines
kernel/sched/cpudeadline.c int cpudl_find(struct cpudl *cp, struct task_struct *p, · line 145
Quoted 4 lines
kernel/sched/cpudeadline.c +2
-2-if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask);Think we touched upon this during v1 review, but I'm (still?) wondering if we can do a little better, still considering only free cpus.
Quoted 6 lines
Can't we get into a situation that some of the (once free) big cpus have been occupied by small tasks and now a big task enters the system and it only finds small cpus available, were it could have fit into bigs if small tasks were put onto small cpus?
I.e., shouldn't we always try to best fit among free cpus?
Yes; there was an additional patch that tried schedule each task on the slowest core where it can fit, to address this issue.
But I think it will go in a second round of patches.
Luca
Dietmar Eggemann
reviewerRe: [PATCH v2 6/6] sched/deadline: Implement fallback mechanism for !fit case
Quoted 36 lines · luca abeni
Hi Juri,
Quoted 16 lines · On Mon, 27 Apr 2020 15:34:38 +0200 Juri Lelli <[email protected]> wrote:
Hi,
Quoted 13 lines · Dietmar Eggemann
From: Luca Abeni <[email protected]>
When a task has a runtime that cannot be served within the scheduling deadline by any of the idle CPU (
later_mask) the task is doomed to miss its deadline.This can happen since the
SCHED_DEADLINEadmission control guarantees only bounded tardiness and not the hard respect of all deadlines. In this case try to select the idle CPU with the largest CPU capacity to minimize tardiness.Signed-off-by Luca Abeni <[email protected]>Signed-off-by Dietmar Eggemann <[email protected]>[...]
Quoted 14 lines
kernel/sched/cpudeadline.c int cpudl_find(struct cpudl *cp, struct task_struct *p, · line 145
Quoted 4 lines
kernel/sched/cpudeadline.c +2
-2-if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask);Think we touched upon this during v1 review, but I'm (still?) wondering if we can do a little better, still considering only free cpus.
Can't we get into a situation that some of the (once free) big cpus have been occupied by small tasks and now a big task enters the system and it only finds small cpus available, were it could have fit into bigs if small tasks were put onto small cpus?
Quoted 5 lines
Quoted 1 line
I.e., shouldn't we always try to best fit among free cpus?
Yes; there was an additional patch that tried schedule each task on the slowest core where it can fit, to address this issue.
But I think it will go in a second round of patches.
Yes, we can run into this situation in DL, but also in CFS or RT.
IMHO, this patch is aligned with the Capacity Awareness implementation in CFS and RT.
Capacity Awareness so far is 'find a CPU which fits the requirement of the task (Req)'. It's not (yet) find the best CPU.
CFS - select_idle_capacity() -> task_fits_capacity()
Req: util(p) * 1.25 < capacity_of(cpu)
RT - select_task_rq_rt(), cpupri_find_fitness() ->
rt_task_fits_capacity()
Req: uclamp_eff_value(p) <= capacity_orig_of(cpu)
DL - select_task_rq_dl(), cpudl_find() -> dl_task_fits_capacity()
Req: dl_runtime(p)/dl_deadline(p) * 1024 <= capacity_orig_of(cpu)
There has to be an "idle" (from the viewpoint of the task) CPU available with a fitting capacity. Otherwise a fallback mechanism applies.
CFS - best capacity handling in select_idle_capacity().
RT - Non-fitting lowest mask
DL - This patch
You did spot the rt-app 'delay' for the small tasks in the test case ;-)
Re: [PATCH v2 6/6] sched/deadline: Implement fallback mechanism for !fit case
Quoted 37 lines · Dietmar Eggemann
Quoted 36 lines · luca abeni
Hi Juri,
Quoted 16 lines · On Mon, 27 Apr 2020 15:34:38 +0200 Juri Lelli <[email protected]> wrote:
Hi,
Quoted 13 lines · Dietmar Eggemann
From: Luca Abeni <[email protected]>
When a task has a runtime that cannot be served within the scheduling deadline by any of the idle CPU (
later_mask) the task is doomed to miss its deadline.This can happen since the
SCHED_DEADLINEadmission control guarantees only bounded tardiness and not the hard respect of all deadlines. In this case try to select the idle CPU with the largest CPU capacity to minimize tardiness.Signed-off-by Luca Abeni <[email protected]>Signed-off-by Dietmar Eggemann <[email protected]>[...]
Quoted 14 lines
kernel/sched/cpudeadline.c int cpudl_find(struct cpudl *cp, struct task_struct *p, · line 145
Quoted 4 lines
kernel/sched/cpudeadline.c +2
-2-if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask);Think we touched upon this during v1 review, but I'm (still?) wondering if we can do a little better, still considering only free cpus.
Can't we get into a situation that some of the (once free) big cpus have been occupied by small tasks and now a big task enters the system and it only finds small cpus available, were it could have fit into bigs if small tasks were put onto small cpus?
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
I.e., shouldn't we always try to best fit among free cpus?
Yes; there was an additional patch that tried schedule each task on the slowest core where it can fit, to address this issue.
But I think it will go in a second round of patches.Yes, we can run into this situation in DL, but also in CFS or RT.
In CFS case, the misfit task handling in load balancer should help pulling the BIG task running on the little CPUs. I get your point that we can run into the same scenario with other scheduling class tasks.
Quoted 23 lines
IMHO, this patch is aligned with the Capacity Awareness implementation in CFS and RT.
Capacity Awareness so far is 'find a CPU which fits the requirement of the task (Req)'. It's not (yet) find the best CPU.
CFS -
select_idle_capacity()->task_fits_capacity()Req: util(p) * 1.25 < capacity_of(cpu)RT -
select_task_rq_rt(),cpupri_find_fitness()->
rt_task_fits_capacity()Req:
uclamp_eff_value(p)<=capacity_orig_of(cpu)DL -
select_task_rq_dl(),cpudl_find()->dl_task_fits_capacity()Req: dl_runtime(p)/dl_deadline(p) * 1024 <= capacity_orig_of(cpu)There has to be an "idle" (from the viewpoint of the task) CPU available with a fitting capacity. Otherwise a fallback mechanism applies.
Quoted 7 lines
CFS - best capacity handling in
select_idle_capacity().RT - Non-fitting lowest mask
DL - This patch
You did spot the rt-app 'delay' for the small tasks in the test case ;-)
Thanks for the hint. It was not clear to me why 1 msec delay is given for the small tasks in the rt-app json description in the cover letter. I get it now :-)
Thanks,
Pavan
Signature · 2 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc. Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Dietmar Eggemann
reviewerRe: [PATCH v2 6/6] sched/deadline: Implement fallback mechanism for !fit case
Quoted 2 lines · Pavan Kondeti
Quoted 1 line · Dietmar Eggemann
On 27/04/2020 16:17, luca abeni wrote:
[...]
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
On Mon, 27 Apr 2020 15:34:38 +0200
Juri Lelli <[email protected]> wrote:
[...]
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines · Dietmar Eggemann
Quoted 1 line
From: Luca Abeni <[email protected]>
[...]
Quoted 20 lines
Quoted 20 lines
Quoted 19 lines
Quoted 9 lines
kernel/sched/cpudeadline.c int cpudl_find(struct cpudl *cp, struct task_struct *p, · line 145
Quoted 4 lines
kernel/sched/cpudeadline.c +2
-2-if (!cpumask_empty (later_mask)) -return 1 ; +if (cpumask_empty (later_mask)) +cpumask_set_cpu (max_cpu, later_mask);Think we touched upon this during v1 review, but I'm (still?) wondering if we can do a little better, still considering only free cpus.
Quoted 6 lines
Can't we get into a situation that some of the (once free) big cpus have been occupied by small tasks and now a big task enters the system and it only finds small cpus available, were it could have fit into bigs if small tasks were put onto small cpus?
I.e., shouldn't we always try to best fit among free cpus?
Yes; there was an additional patch that tried schedule each task on the slowest core where it can fit, to address this issue.
But I think it will go in a second round of patches.
Quoted 5 lines
Quoted 2 lines
Yes, we can run into this situation in DL, but also in CFS or RT.
In CFS case, the misfit task handling in load balancer should help pulling the BIG task running on the little CPUs. I get your point that we can run into the same scenario with other scheduling class tasks.
Yes, the CPU stopper (i.e. CFS's active load balance) can help here. IMHO, using the CPU stopper in RT/DL for moving the running task (next to using best fit rather than just fit CPU) is considered future work. AFAICS, push/pull is not designed for migration of running tasks.
[...]
Quoted 5 lines
Quoted 1 line
You did spot the rt-app 'delay' for the small tasks in the test case ;-)
Thanks for the hint. It was not clear to me why 1 msec delay is given for the small tasks in the rt-app json description in the cover letter. I get it now :-)
So far Capacity awareness in RT/DL means that as long as there are CPUs available which fit the task, use one of them. This is already beneficial for a lot of use cases on CPU asymmetric systems since it offers more predictable behavior.
I'll add a note to the cover letter in the next version about the reason of the rt-app 'delay'.