Re: [RFC PATCH 08/23] sched/fair: Compute task-class performance scores for load balancing

Ricardo Neri
2022-10-26T03:50:30Z

On Tue, Sep 27, 2022 at 11:15:46AM +0200, Peter Zijlstra wrote:
> On Fri, Sep 09, 2022 at 04:11:50PM -0700, Ricardo Neri wrote:
>
> > +static void compute_ilb_sg_task_class_scores(struct sg_lb_task_class_stats *class_sgs,
> > + struct sg_lb_stats *sgs,
> > + int dst_cpu)
> > +{
> > + int group_score, group_score_without, score_on_dst_cpu;
> > + int busy_cpus = sgs->group_weight - sgs->idle_cpus;
> > +
> > + if (!sched_task_classes_enabled())
> > + return;
> > +
> > + /* No busy CPUs in the group. No tasks to move. */
> > + if (!busy_cpus)
> > + return;
> > +
> > + score_on_dst_cpu = arch_get_task_class_score(class_sgs->p_min_score->class,
> > + dst_cpu);
> > +
> > + /*
> > + * The simpest case. The single busy CPU in the current group will
> > + * become idle after pulling its current task. The destination CPU is
> > + * idle.
> > + */
> > + if (busy_cpus == 1) {
> > + sgs->task_class_score_before = class_sgs->sum_score;
> > + sgs->task_class_score_after = score_on_dst_cpu;
> > + return;
> > + }
> > +
> > + /*
> > + * Now compute the group score with and without the task with the
> > + * lowest score. We assume that the tasks that remain in the group share
> > + * the CPU resources equally.
> > + */
> > + group_score = class_sgs->sum_score / busy_cpus;
> > +
> > + group_score_without = (class_sgs->sum_score - class_sgs->min_score) /
> > + (busy_cpus - 1);
> > +
> > + sgs->task_class_score_after = group_score_without + score_on_dst_cpu;
> > + sgs->task_class_score_before = group_score;
> > +}

(I am sorry Peter, I just found that several emails were sitting on my drafts
directory).

>
> That's just plain broken; also lots of cleanups done...

Thank you very much for your suggestions. They make sense to me. I only
have a comment...

Do you want me to add your Signed-off-by and Co-developed-by tags?

>
> ---
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8405,12 +8405,14 @@ struct sg_lb_stats {
> enum group_type group_type;
> unsigned int group_asym_packing; /* Tasks should be moved to preferred CPU */
> unsigned long group_misfit_task_load; /* A CPU has a task too big for its capacity */
> - long task_class_score_after; /* Prospective task-class score after load balancing */
> - long task_class_score_before; /* Task-class score before load balancing */
> #ifdef CONFIG_NUMA_BALANCING
> unsigned int nr_numa_running;
> unsigned int nr_preferred_running;
> #endif
> +#ifdef CONFIG_SCHED_TASK_CLASSES
> + long task_class_score_after; /* Prospective task-class score after load balancing */
> + long task_class_score_before; /* Task-class score before load balancing */
> +#endif
> };
>
> /*
> @@ -8689,58 +8691,54 @@ group_type group_classify(unsigned int i
> }
>
> struct sg_lb_task_class_stats {
> - /*
> - * Score of the task with lowest score among the current tasks (i.e.,
> - * runqueue::curr) of all runqueues in the scheduling group.
> - */
> - int min_score;
> - /*
> - * Sum of the scores of the current tasks of all runqueues in the
> - * scheduling group.
> - */
> - long sum_score;
> - /* The task with score equal to @min_score */
> - struct task_struct *p_min_score;
> + int min_score; /* Min(rq->curr->score) */
> + int min_class;
> + long sum_score; /* Sum(rq->curr->score) */
> };
>
> #ifdef CONFIG_SCHED_TASK_CLASSES
> -static void init_rq_task_classes_stats(struct sg_lb_task_class_stats *class_sgs)
> +static void init_sg_lb_task_class_stats(struct sg_lb_task_class_stats *sgcs)
> {
> - class_sgs->min_score = INT_MAX;
> - class_sgs->sum_score = 0;
> - class_sgs->p_min_score = NULL;
> + *sgcs = (struct sg_lb_task_class_stats){
> + .min_score = INT_MAX,
> + };
> }
>
> /** Called only if cpu_of(@rq) is not idle and has tasks running. */
> -static void update_rq_task_classes_stats(struct sg_lb_task_class_stats *class_sgs,
> - struct rq *rq)
> +static void update_sg_lb_task_class_stats(struct sg_lb_task_class_stats *sgcs,
> + struct rq *rq)
> {
> - int score;
> + struct task_struct *curr;
> + int class, score;
>
> if (!sched_task_classes_enabled())
> return;
>
> + curr = rcu_dereference(rq->curr);
> + if (!curr || (curr->flags & PF_EXITING) || is_idle_task(curr))
> + return;
> +
> /*
> * TODO: if nr_running > 1 we may want go through all the tasks behind
> * rq->curr.
> */
> - score = arch_get_task_class_score(rq->curr->class, cpu_of(rq));
> -
> - class_sgs->sum_score += score;
> + class = curr->class;
> + score = arch_get_task_class_score(class, cpu_of(rq));
>
> - if (score >= class_sgs->min_score)
> - return;
> + sgcs->sum_score += score;
>
> - class_sgs->min_score = score;
> - class_sgs->p_min_score = rq->curr;
> + if (score < sgcs->min_score) {
> + sgcs->min_score = score;
> + sgcs->min_class = class;
> + }
> }
>
> -static void compute_ilb_sg_task_class_scores(struct sg_lb_task_class_stats *class_sgs,
> - struct sg_lb_stats *sgs,
> - int dst_cpu)
> +static void update_sg_lb_stats_scores(struct sg_lb_task_class_stats *sgcs,
> + struct sg_lb_stats *sgs,
> + int dst_cpu)
> {
> - int group_score, group_score_without, score_on_dst_cpu;
> int busy_cpus = sgs->group_weight - sgs->idle_cpus;
> + long before, after;
>
> if (!sched_task_classes_enabled())
> return;
> @@ -8749,32 +8747,18 @@ static void compute_ilb_sg_task_class_sc
> if (!busy_cpus)
> return;
>
> - score_on_dst_cpu = arch_get_task_class_score(class_sgs->p_min_score->class,
> - dst_cpu);
> + score_on_dst_cpu = arch_get_task_class_score(sgcs->min_class, dst_cpu);
>
> - /*
> - * The simpest case. The single busy CPU in the current group will
> - * become idle after pulling its current task. The destination CPU is
> - * idle.
> - */
> - if (busy_cpus == 1) {
> - sgs->task_class_score_before = class_sgs->sum_score;
> - sgs->task_class_score_after = score_on_dst_cpu;
> - return;
> - }
> + before = sgcs->sum_score
> + after = before - sgcs->min_score + score_on_dst_cpu;

This works when the sched group being evaluated has only one busy CPU
because it will become idle if the destination CPU (which was idle) pulls
the current task.

>
> - /*
> - * Now compute the group score with and without the task with the
> - * lowest score. We assume that the tasks that remain in the group share
> - * the CPU resources equally.
> - */
> - group_score = class_sgs->sum_score / busy_cpus;
> -
> - group_score_without = (class_sgs->sum_score - class_sgs->min_score) /
> - (busy_cpus - 1);
> + if (busy_cpus > 1) {
> + before /= busy_cpus;
> + after /= busy_cpus;

However, I don't think this works when the sched group has more than one
busy CPU. 'before' and 'after' reflect the total throughput score of both
the sched group *and* the destination CPU.

One of the CPUs in the sched group will become idle after the balance.

Also, at this point we have already added score_on_dst_cpu. We are incorrectly
scaling it by the number of busy CPUs in the sched group.

We instead must scale 'after' by busy_cpus - 1 and then add score_on_dst_cpu.

> + }
>
> - sgs->task_class_score_after = group_score_without + score_on_dst_cpu;
> - sgs->task_class_score_before = group_score;
> + sgs->task_class_score_before = before;
> + sgs->task_class_score_after = after;
>

Thanks and BR,
Ricardo
>