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
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:   Fri, 4 Nov 2022 10:05:50 +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 17:22, Vincent Guittot wrote:
> On Thu, 3 Nov 2022 at 10:20, Song Zhang <zhangsong34@...wei.com> wrote:
>>
>>
>>
>> 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.
> 
> yes spawn 5000 idle tasks but my point remains the same
> 

But I really don't understand what you are most focused on, and what 
else should I do.

>>
>>>>
>>>> $ 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