| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Thu, 3 Nov 2022 17:20:22 +0800
From: Song Zhang <zhangsong34@...wei.com>
To: Vincent Guittot <vincent.guittot@...aro.org>
CC: <mingo@...hat.com>, <peterz@...radead.org>,
<juri.lelli@...hat.com>, <mcgrof@...nel.org>,
<keescook@...omium.org>, <yzaikin@...gle.com>,
<dietmar.eggemann@....com>, <rostedt@...dmis.org>,
<bsegall@...gle.com>, <mgorman@...e.de>, <bristot@...hat.com>,
<vschneid@...hat.com>, <linux-kernel@...r.kernel.org>,
<linux-fsdevel@...r.kernel.org>
Subject: Re: [PATCH] sched/fair: Introduce priority load balance for CFS
On 2022/11/3 16:33, Vincent Guittot wrote:
> On Thu, 3 Nov 2022 at 04:01, Song Zhang <zhangsong34@...wei.com> wrote:
>>
>> Thanks for your reply!
>>
>> On 2022/11/3 2:01, Vincent Guittot wrote:
>>> On Wed, 2 Nov 2022 at 04:54, Song Zhang <zhangsong34@...wei.com> wrote:
>>>>
>>>
>>> This really looks like a v3 of
>>> https://lore.kernel.org/all/20220810015636.3865248-1-zhangsong34@huawei.com/
>>>
>>> Please keep versioning.
>>>
>>>> Add a new sysctl interface:
>>>> /proc/sys/kernel/sched_prio_load_balance_enabled
>>>
>>> We don't want to add more sysctl knobs for the scheduler, we even
>>> removed some. Knob usually means that you want to fix your use case
>>> but the solution doesn't make sense for all cases.
>>>
>>
>> OK, I will remove this knobs later.
>>
>>>>
>>>> 0: default behavior
>>>> 1: enable priority load balance for CFS
>>>>
>>>> For co-location with idle and non-idle tasks, when CFS do load balance,
>>>> it is reasonable to prefer migrating non-idle tasks and migrating idle
>>>> tasks lastly. This will reduce the interference by SCHED_IDLE tasks
>>>> as much as possible.
>>>
>>> I don't agree that it's always the best choice to migrate a non-idle task 1st.
>>>
>>> CPU0 has 1 non idle task and CPU1 has 1 non idle task and hundreds of
>>> idle task and there is an imbalance between the 2 CPUS: migrating the
>>> non idle task from CPU1 to CPU0 is not the best choice
>>>
>>
>> If the non idle task on CPU1 is running or cache hot, it cannot be
>> migrated and idle tasks can also be migrated from CPU1 to CPU0. So I
>> think it does not matter.
>
> What I mean is that migrating non idle tasks first is not a universal
> win and not always what we want.
>
But migrating online tasks first is mostly a trade-off that
non-idle(Latency Sensitive) tasks can obtain more CPU time and minimize
the interference caused by IDLE tasks. I think this makes sense in most
cases, or you can point out what else I need to think about it ?
Best regards.
>>
>>>>
>>>> Testcase:
>>>> - Spawn large number of idle(SCHED_IDLE) tasks occupy CPUs
>>>
>>> What do you mean by a large number ?
>>>
>>>> - Let non-idle tasks compete with idle tasks for CPU time.
>>>>
>>>> Using schbench to test non-idle tasks latency:
>>>> $ ./schbench -m 1 -t 10 -r 30 -R 200
>>>
>>> How many CPUs do you have ?
>>>
>>
>> OK, some details may not be mentioned.
>> My virtual machine has 8 CPUs running with a schbench process and 5000
>> idle tasks. The idle task is a while dead loop process below:
>
> How can you care about latency when you start 10 workers on 8 vCPUs
> with 5000 non idle threads ?
>
No no no... spawn 5000 idle(SCHED_IDLE) processes not 5000 non-idle
threads, and with 10 non-idle schbench workers on 8 vCPUs.
>>
>> $ cat idle_process.c
>> int main()
>> {
>> int i = 0;
>> while(1) {
>> usleep(500);
>> for(i = 0; i < 1000000; i++);
>> }
>> }
>>
>> You can compile and spawn 5000 idle(SCHED_IDLE) tasks occupying 8 CPUs
>> and execute schbench command to test it.
>>
>>>>
>>>> Test result:
>>>> 1.Default behavior
>>>> Latency percentiles (usec) runtime 30 (s) (4562 total samples)
>>>> 50.0th: 62528 (2281 samples)
>>>> 75.0th: 623616 (1141 samples)
>>>> 90.0th: 764928 (687 samples)
>>>> 95.0th: 824320 (225 samples)
>>>> *99.0th: 920576 (183 samples)
>>>> 99.5th: 953344 (23 samples)
>>>> 99.9th: 1008640 (18 samples)
>>>> min=9, max=1074466
>>>>
>>>> 2.Enable priority load balance
>>>> Latency percentiles (usec) runtime 30 (s) (4391 total samples)
>>>> 50.0th: 22624 (2204 samples)
>>>> 75.0th: 48832 (1092 samples)
>>>> 90.0th: 85376 (657 samples)
>>>> 95.0th: 113280 (220 samples)
>>>> *99.0th: 182528 (175 samples)
>>>> 99.5th: 206592 (22 samples)
>>>> 99.9th: 290304 (17 samples)
>>>> min=6, max=351815
>>>>
>>>> From percentile details, we see the benefit of priority load balance
>>>> that 95% of non-idle tasks latencies stays no more than 113ms, while
>>>
>>> But even 113ms seems quite a large number if there is anything else
>>> but 10 schbench workers and a bunch of idle threads that are running.
>>>
>>>> non-idle tasks latencies has got almost 50% over 600ms if priority
>>>> load balance not enabled.
>>>
>>> Als have you considered enabling sched_feature LB_MIN ?
>>>
>>
>> I have tried to echo LB_MIN > /sys/kernel/debug/sched/features, but this
>> feature seems make no sense.
>>
>>>>
>>>> Signed-off-by: Song Zhang <zhangsong34@...wei.com>
>>>> ---
>>>> include/linux/sched/sysctl.h | 4 +++
>>>> init/Kconfig | 10 ++++++
>>>> kernel/sched/core.c | 3 ++
>>>> kernel/sched/fair.c | 61 +++++++++++++++++++++++++++++++++++-
>>>> kernel/sched/sched.h | 3 ++
>>>> kernel/sysctl.c | 11 +++++++
>>>> 6 files changed, 91 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/include/linux/sched/sysctl.h b/include/linux/sched/sysctl.h
>>>> index 303ee7dd0c7e..9b3673269ecc 100644
>>>> --- a/include/linux/sched/sysctl.h
>>>> +++ b/include/linux/sched/sysctl.h
>>>> @@ -32,6 +32,10 @@ extern unsigned int sysctl_numa_balancing_promote_rate_limit;
>>>> #define sysctl_numa_balancing_mode 0
>>>> #endif
>>>>
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> +extern unsigned int sysctl_sched_prio_load_balance_enabled;
>>>> +#endif
>>>> +
>>>> int sysctl_numa_balancing(struct ctl_table *table, int write, void *buffer,
>>>> size_t *lenp, loff_t *ppos);
>>>>
>>>> diff --git a/init/Kconfig b/init/Kconfig
>>>> index 694f7c160c9c..b0dfe6701218 100644
>>>> --- a/init/Kconfig
>>>> +++ b/init/Kconfig
>>>> @@ -1026,6 +1026,16 @@ config CFS_BANDWIDTH
>>>> restriction.
>>>> See Documentation/scheduler/sched-bwc.rst for more information.
>>>>
>>>> +config SCHED_PRIO_LB
>>>> + bool "Priority load balance for CFS"
>>>> + depends on SMP
>>>> + default n
>>>> + help
>>>> + This feature enable CFS priority load balance to reduce
>>>> + non-idle tasks latency interferenced by SCHED_IDLE tasks.
>>>> + It prefer migrating non-idle tasks firstly and
>>>> + migrating SCHED_IDLE tasks lastly.
>>>> +
>>>> config RT_GROUP_SCHED
>>>> bool "Group scheduling for SCHED_RR/FIFO"
>>>> depends on CGROUP_SCHED
>>>> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
>>>> index 5800b0623ff3..9be35431fdd5 100644
>>>> --- a/kernel/sched/core.c
>>>> +++ b/kernel/sched/core.c
>>>> @@ -9731,6 +9731,9 @@ void __init sched_init(void)
>>>> rq->max_idle_balance_cost = sysctl_sched_migration_cost;
>>>>
>>>> INIT_LIST_HEAD(&rq->cfs_tasks);
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + INIT_LIST_HEAD(&rq->cfs_idle_tasks);
>>>> +#endif
>>>>
>>>> rq_attach_root(rq, &def_root_domain);
>>>> #ifdef CONFIG_NO_HZ_COMMON
>>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>>> index e4a0b8bd941c..bdeb04324f0c 100644
>>>> --- a/kernel/sched/fair.c
>>>> +++ b/kernel/sched/fair.c
>>>> @@ -139,6 +139,10 @@ static int __init setup_sched_thermal_decay_shift(char *str)
>>>> }
>>>> __setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift);
>>>>
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> +unsigned int sysctl_sched_prio_load_balance_enabled;
>>>> +#endif
>>>> +
>>>> #ifdef CONFIG_SMP
>>>> /*
>>>> * For asym packing, by default the lower numbered CPU has higher priority.
>>>> @@ -3199,6 +3203,21 @@ static inline void update_scan_period(struct task_struct *p, int new_cpu)
>>>>
>>>> #endif /* CONFIG_NUMA_BALANCING */
>>>>
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> +static void
>>>> +adjust_rq_cfs_tasks(
>>>> + void (*list_op)(struct list_head *, struct list_head *),
>>>> + struct rq *rq,
>>>> + struct sched_entity *se)
>>>> +{
>>>> + if (sysctl_sched_prio_load_balance_enabled &&
>>>> + task_has_idle_policy(task_of(se)))
>>>> + (*list_op)(&se->group_node, &rq->cfs_idle_tasks);
>>>> + else
>>>> + (*list_op)(&se->group_node, &rq->cfs_tasks);
>>>> +}
>>>> +#endif
>>>> +
>>>> static void
>>>> account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
>>>> {
>>>> @@ -3208,7 +3227,11 @@ account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
>>>> struct rq *rq = rq_of(cfs_rq);
>>>>
>>>> account_numa_enqueue(rq, task_of(se));
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + adjust_rq_cfs_tasks(list_add, rq, se);
>>>> +#else
>>>> list_add(&se->group_node, &rq->cfs_tasks);
>>>> +#endif
>>>> }
>>>> #endif
>>>> cfs_rq->nr_running++;
>>>> @@ -7631,7 +7654,11 @@ done: __maybe_unused;
>>>> * the list, so our cfs_tasks list becomes MRU
>>>> * one.
>>>> */
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + adjust_rq_cfs_tasks(list_move, rq, &p->se);
>>>> +#else
>>>> list_move(&p->se.group_node, &rq->cfs_tasks);
>>>> +#endif
>>>> #endif
>>>>
>>>> if (hrtick_enabled_fair(rq))
>>>> @@ -8156,11 +8183,18 @@ static void detach_task(struct task_struct *p, struct lb_env *env)
>>>> static struct task_struct *detach_one_task(struct lb_env *env)
>>>> {
>>>> struct task_struct *p;
>>>> + struct list_head *tasks = &env->src_rq->cfs_tasks;
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + bool has_detach_idle_tasks = false;
>>>> +#endif
>>>>
>>>> lockdep_assert_rq_held(env->src_rq);
>>>>
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> +again:
>>>> +#endif
>>>> list_for_each_entry_reverse(p,
>>>> - &env->src_rq->cfs_tasks, se.group_node) {
>>>> + tasks, se.group_node) {
>>>> if (!can_migrate_task(p, env))
>>>> continue;
>>>>
>>>> @@ -8175,6 +8209,13 @@ static struct task_struct *detach_one_task(struct lb_env *env)
>>>> schedstat_inc(env->sd->lb_gained[env->idle]);
>>>> return p;
>>>> }
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + if (sysctl_sched_prio_load_balance_enabled && !has_detach_idle_tasks) {
>>>> + has_detach_idle_tasks = true;
>>>> + tasks = &env->src_rq->cfs_idle_tasks;
>>>> + goto again;
>>>> + }
>>>> +#endif
>>>> return NULL;
>>>> }
>>>>
>>>> @@ -8190,6 +8231,9 @@ static int detach_tasks(struct lb_env *env)
>>>> unsigned long util, load;
>>>> struct task_struct *p;
>>>> int detached = 0;
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + bool has_detach_idle_tasks = false;
>>>> +#endif
>>>>
>>>> lockdep_assert_rq_held(env->src_rq);
>>>>
>>>> @@ -8205,6 +8249,9 @@ static int detach_tasks(struct lb_env *env)
>>>> if (env->imbalance <= 0)
>>>> return 0;
>>>>
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> +again:
>>>> +#endif
>>>> while (!list_empty(tasks)) {
>>>> /*
>>>> * We don't want to steal all, otherwise we may be treated likewise,
>>>> @@ -8310,6 +8357,14 @@ static int detach_tasks(struct lb_env *env)
>>>> list_move(&p->se.group_node, tasks);
>>>> }
>>>>
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + if (sysctl_sched_prio_load_balance_enabled &&
>>>> + !has_detach_idle_tasks && env->imbalance > 0) {
>>>> + has_detach_idle_tasks = true;
>>>> + tasks = &env->src_rq->cfs_idle_tasks;
>>>> + goto again;
>>>> + }
>>>> +#endif
>>>> /*
>>>> * Right now, this is one of only two places we collect this stat
>>>> * so we can safely collect detach_one_task() stats here rather
>>>> @@ -11814,7 +11869,11 @@ static void set_next_task_fair(struct rq *rq, struct task_struct *p, bool first)
>>>> * Move the next running task to the front of the list, so our
>>>> * cfs_tasks list becomes MRU one.
>>>> */
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + adjust_rq_cfs_tasks(list_move, rq, se);
>>>> +#else
>>>> list_move(&se->group_node, &rq->cfs_tasks);
>>>> +#endif
>>>> }
>>>> #endif
>>>>
>>>> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
>>>> index 1644242ecd11..1b831c05ba30 100644
>>>> --- a/kernel/sched/sched.h
>>>> +++ b/kernel/sched/sched.h
>>>> @@ -1053,6 +1053,9 @@ struct rq {
>>>> int online;
>>>>
>>>> struct list_head cfs_tasks;
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + struct list_head cfs_idle_tasks;
>>>> +#endif
>>>>
>>>> struct sched_avg avg_rt;
>>>> struct sched_avg avg_dl;
>>>> diff --git a/kernel/sysctl.c b/kernel/sysctl.c
>>>> index 188c305aeb8b..5fc0f9ffb675 100644
>>>> --- a/kernel/sysctl.c
>>>> +++ b/kernel/sysctl.c
>>>> @@ -2090,6 +2090,17 @@ static struct ctl_table kern_table[] = {
>>>> .extra1 = SYSCTL_ONE,
>>>> .extra2 = SYSCTL_INT_MAX,
>>>> },
>>>> +#endif
>>>> +#ifdef CONFIG_SCHED_PRIO_LB
>>>> + {
>>>> + .procname = "sched_prio_load_balance_enabled",
>>>> + .data = &sysctl_sched_prio_load_balance_enabled,
>>>> + .maxlen = sizeof(unsigned int),
>>>> + .mode = 0644,
>>>> + .proc_handler = proc_dointvec_minmax,
>>>> + .extra1 = SYSCTL_ZERO,
>>>> + .extra2 = SYSCTL_ONE,
>>>> + },
>>>> #endif
>>>> { }
>>>> };
>>>> --
>>>> 2.27.0
>>>>
>>> .
> .
Powered by blists - more mailing lists