Re: [RFC PATCH v2 00/17] Core scheduling v2

[Julien Desfossez <jdesfossez@digitalocean.com>]

On 29-Apr-2019 11:53:21 AM, Aaron Lu wrote:
> On Tue, Apr 23, 2019 at 06:45:27PM +0000, Vineeth Remanan Pillai wrote:
> > >> - Processes with different tags can still share the core
> > 
> > > I may have missed something... Could you explain this statement?
> > 
> > > This, to me, is the whole point of the patch series. If it's not
> > > doing this then ... what?
> > 
> > What I meant was, the patch needs some more work to be accurate.
> > There are some race conditions where the core violation can still
> > happen. In our testing, we saw around 1 to 5% of the time being
> > shared with incompatible processes. One example of this happening
> > is as follows(let cpu 0 and 1 be siblings):
> > - cpu 0 selects a process with a cookie
> > - cpu 1 selects a higher priority process without cookie
> > - Selection process restarts for cpu 0 and it might select a
> >   process with cookie but with lesser priority.
> > - Since it is lesser priority, the logic in pick_next_task
> >   doesn't compare again for the cookie(trusts pick_task) and
> >   proceeds.
> > 
> > This is one of the scenarios that we saw from traces, but there
> > might be other race conditions as well. Fix seems a little
> > involved and We are working on that.
> 
> This is what I have used to make sure no two unmatched tasks being
> scheduled on the same core: (on top of v1, I thinks it's easier to just
> show the diff instead of commenting on various places of the patches :-)

We imported this fix in v2 and made some small changes and optimizations
(with and without Peter’s fix from https://lkml.org/lkml/2019/4/26/658)
and in both cases, the performance problem where the core can end up
idle with tasks in its runqueues came back.

This is pretty easy to reproduce with a multi-file disk write benchmark.

Here is the patch based on your changes applied on v2 (on top of Peter’s
fix):

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 07f3f0c..e09fa25 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3653,6 +3653,13 @@ static inline bool cookie_match(struct task_struct *a, struct task_struct *b)
 }
 
 // XXX fairness/fwd progress conditions
+/*
+ * Returns
+ * - NULL if there is no runnable task for this class.
+ * - the highest priority task for this runqueue if it matches
+ *   rq->core->core_cookie or its priority is greater than max.
+ * - Else returns idle_task.
+ */
 static struct task_struct *
 pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *max)
 {
@@ -3660,19 +3667,36 @@ pick_task(struct rq *rq, const struct sched_class *class, struct task_struct *ma
 	unsigned long cookie = rq->core->core_cookie;
 
 	class_pick = class->pick_task(rq);
-	if (!cookie)
+	if (!class_pick)
+		return NULL;
+
+	if (!cookie) {
+		/*
+		 * If class_pick is tagged, return it only if it has
+		 * higher priority than max.
+		 */
+		if (max && class_pick->core_cookie &&
+		    core_prio_less(class_pick, max))
+			return idle_sched_class.pick_task(rq);
+
+		return class_pick;
+	}
+
+	/*
+	 * If there is a cooke match here, return early.
+	 */
+	if (class_pick->core_cookie == 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) && core_prio_less(max, class_pick))
+	if (cpu_prio_less(cookie_pick, class_pick) &&
+	    (!max || core_prio_less(max, class_pick)))
 		return class_pick;
 
 	return cookie_pick;
@@ -3742,8 +3766,16 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 
 		rq_i->core_pick = NULL;
 
-		if (i != cpu)
+		if (i != cpu) {
 			update_rq_clock(rq_i);
+
+			/*
+			 * If a sibling is idle, we can initiate an
+			 * unconstrained pick.
+			 */
+			if (is_idle_task(rq_i->curr) && prev_cookie)
+				prev_cookie = 0UL;
+		}
 	}
 
 	/*
@@ -3820,12 +3852,14 @@ 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.
+			 * the slate and start over. pick_task makes sure that
+			 * p's priority is more than max if it doesn't match
+			 * max's cookie.
 			 *
 			 * NOTE: this is a linear max-filter and is thus bounded
 			 * in execution time.
 			 */
-			if (!max || core_prio_less(max, p)) {
+			if (!max || !cookie_match(max, p)) {
 				struct task_struct *old_max = max;
 
 				rq->core->core_cookie = p->core_cookie;
@@ -3833,7 +3867,7 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 
 				trace_printk("max: %s/%d %lx\n", max->comm, max->pid, max->core_cookie);
 
-				if (old_max && !cookie_match(old_max, p)) {
+				if (old_max) {
 					for_each_cpu(j, smt_mask) {
 						if (j == i)
 							continue;
@@ -3879,6 +3913,23 @@ next_class:;
 
 	trace_printk("picked: %s/%d %lx\n", next->comm, next->pid, next->core_cookie);
 
+	/* make sure we didn't break L1TF */
+	for_each_cpu(i, smt_mask) {
+		struct rq *rq_i = cpu_rq(i);
+		if (i == cpu)
+			continue;
+
+		if (likely(cookie_match(next, rq_i->core_pick)))
+			continue;
+
+		trace_printk("[%d]: cookie mismatch. %s/%d/0x%lx/0x%lx\n",
+			     rq_i->cpu, rq_i->core_pick->comm,
+			     rq_i->core_pick->pid,
+			     rq_i->core_pick->core_cookie,
+			     rq_i->core->core_cookie);
+		WARN_ON_ONCE(1);
+	}
+
 done:
 	set_next_task(rq, next);
 	return next;