Re: [RFC][PATCH 13/16] sched: Add core wide task selection and scheduling.

Peter Zijlstra
2019-04-02T08:28:29Z

On Tue, Apr 02, 2019 at 02:46:13PM +0800, Aaron Lu wrote:
> On Mon, Feb 18, 2019 at 05:56:33PM +0100, Peter Zijlstra wrote:

> > +static struct task_struct *
> > +pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max)
> > +{
> > + struct task_struct *class_pick, *cookie_pick;
> > + unsigned long cookie = 0UL;
> > +
> > + /*
> > + * We must not rely on rq->core->core_cookie here, because we fail to reset
> > + * rq->core->core_cookie on new picks, such that we can detect if we need
> > + * to do single vs multi rq task selection.
> > + */
> > +
> > + if (max && max->core_cookie) {
> > + WARN_ON_ONCE(rq->core->core_cookie != max->core_cookie);
> > + cookie = max->core_cookie;
> > + }
> > +
> > + class_pick = class->pick_task(rq);
> > + if (!cookie)
> > + return class_pick;
> > +
> > + cookie_pick = sched_core_find(rq, cookie);
> > + if (!class_pick)
> > + return cookie_pick;
> > +
> > + /*
> > + * If class > max && class > cookie, it is the highest priority task on
> > + * the core (so far) and it must be selected, otherwise we must go with
> > + * the cookie pick in order to satisfy the constraint.
> > + */
> > + if (cpu_prio_less(cookie_pick, class_pick) && cpu_prio_less(max, class_pick))
> > + return class_pick;
>
> I have a question about the use of cpu_prio_less(max, class_pick) here
> and core_prio_less(max, p) below in pick_next_task().
>
> Assume cpu_prio_less(max, class_pick) thinks class_pick has higher
> priority and class_pick is returned here. Then in pick_next_task(),
> core_prio_less(max, p) is used to decide if max should be replaced.
> Since core_prio_less(max, p) doesn't compare vruntime, it could return
> fasle for this class_pick and the same max. Then max isn't replaced
> and we could end up scheduling two processes belonging to two different
> cgroups...

> > +
> > + return cookie_pick;
> > +}
> > +
> > +static struct task_struct *
> > +pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> > +{

> > + /*
> > + * If this new candidate is of higher priority than the
> > + * previous; and they're incompatible; we need to wipe
> > + * the slate and start over.
> > + *
> > + * NOTE: this is a linear max-filter and is thus bounded
> > + * in execution time.
> > + */
> > + if (!max || core_prio_less(max, p)) {
>
> This is the place to decide if max should be replaced.

Hummm.... very good spotting that. Yes, I'm afraid you're very much
right about this.

> Perhaps we can test if max is on the same cpu as class_pick and then
> use cpu_prio_less() or core_prio_less() accordingly here, or just
> replace core_prio_less(max, p) with cpu_prio_less(max, p) in
> pick_next_task(). The 2nd obviously breaks the comment of
> core_prio_less() though: /* cannot compare vruntime across CPUs */.

Right, so as the comment states, you cannot directly compare vruntime
across CPUs, doing that is completely buggered.

That also means that the cpu_prio_less(max, class_pick) in pick_task()
is buggered, because there is no saying @max is on this CPU to begin
with.

Changing that to core_prio_less() doesn't fix this though.

> I'm still evaluating, your comments are appreciated.

We could change the above condition to:

if (!max || !cookie_match(max, p))

I suppose. But please double check the thikning.

> > + struct task_struct *old_max = max;
> > +
> > + rq->core->core_cookie = p->core_cookie;
> > + max = p;
> > +
> > + if (old_max && !cookie_match(old_max, p)) {
> > + for_each_cpu(j, smt_mask) {
> > + if (j == i)
> > + continue;
> > +
> > + cpu_rq(j)->core_pick = NULL;
> > + }
> > + goto again;
> > + }
> > + }
> > + }
> > +next_class:;
> > + }

Another approach would be something like the below:

--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -87,7 +87,7 @@ static inline int __task_prio(struct tas
*/

/* real prio, less is less */
-static inline bool __prio_less(struct task_struct *a, struct task_struct *b, bool runtime)
+static inline bool __prio_less(struct task_struct *a, struct task_struct *b, u64 vruntime)
{
int pa = __task_prio(a), pb = __task_prio(b);

@@ -104,21 +104,25 @@ static inline bool __prio_less(struct ta
if (pa == -1) /* dl_prio() doesn't work because of stop_class above */
return !dl_time_before(a->dl.deadline, b->dl.deadline);

- if (pa == MAX_RT_PRIO + MAX_NICE && runtime) /* fair */
- return !((s64)(a->se.vruntime - b->se.vruntime) < 0);
+ if (pa == MAX_RT_PRIO + MAX_NICE) /* fair */
+ return !((s64)(a->se.vruntime - vruntime) < 0);

return false;
}

static inline bool cpu_prio_less(struct task_struct *a, struct task_struct *b)
{
- return __prio_less(a, b, true);
+ return __prio_less(a, b, b->se.vruntime);
}

static inline bool core_prio_less(struct task_struct *a, struct task_struct *b)
{
- /* cannot compare vruntime across CPUs */
- return __prio_less(a, b, false);
+ u64 vruntime = b->se.vruntime;
+
+ vruntime -= task_rq(b)->cfs.min_vruntime;
+ vruntime += task_rq(a)->cfs.min_vruntime
+
+ return __prio_less(a, b, vruntime);
}

static inline bool __sched_core_less(struct task_struct *a, struct task_struct *b)