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

[Peter Zijlstra <peterz@infradead.org>]

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)