sched/fair: fix sudden expiration of cfq quota in put_prev_task()

Pick_next_task_fair() must be sure that here is at least one runnable task before calling put_prev_task(), but put_prev_task() can expire last remains of cfs quota and throttle all currently runnable tasks. As a result pick_next_task_fair() cannot find next task and crashes.

This patch leaves 1 in ->runtime_remaining when current assignation expires and tries to refill it right after that. In the worst case task will be scheduled once and throttled at the end of slice.

Signed-off-by Konstantin Khlebnikov <[email protected]>

---
  kernel/sched/fair.c |   19 +++++++++++++------
  1 file changed, 13 insertions(+), 6 deletions(-)

kernel/sched/fair.c +13 -6

index 7ce18f3c097a..91785d077db4 100644
@@ -3447,11 +3447,12 @@ static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
  {
  	struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
 
-	/* if the deadline is ahead of our clock, nothing to do */
-	if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
+	/* nothing to expire */
+	if (cfs_rq->runtime_remaining <= 0)
  		return;
 
-	if (cfs_rq->runtime_remaining < 0)
+	/* if the deadline is ahead of our clock, nothing to do */
+	if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
  		return;
 
  	/*

@@ -3469,8 +3470,14 @@ static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
  		/* extend local deadline, drift is bounded above by 2 ticks */
  		cfs_rq->runtime_expires += TICK_NSEC;
  	} else {
-		/* global deadline is ahead, expiration has passed */
-		cfs_rq->runtime_remaining = 0;
+		/*
+		 * Global deadline is ahead, expiration has passed.
+		 *
+		 * Do not expire runtime completely. Otherwise put_prev_task()
+		 * can throttle all tasks when we already checked nr_running or
+		 * put_prev_entity() can throttle already chosen next entity.
+		 */
+		cfs_rq->runtime_remaining = 1;
  	}
  }
 

@@ -3480,7 +3487,7 @@ static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
  	cfs_rq->runtime_remaining -= delta_exec;
  	expire_cfs_rq_runtime(cfs_rq);
 
-	if (likely(cfs_rq->runtime_remaining > 0))
+	if (likely(cfs_rq->runtime_remaining > 1))
  		return;
 
  	/*

Pick_next_task_fair() must be sure that here is at least one runnable task before calling put_prev_task(), but put_prev_task() can expire last remains of cfs quota and throttle all currently runnable tasks. As a result pick_next_task_fair() cannot find next task and crashes.

This patch leaves 1 in ->runtime_remaining when current assignation expires and tries to refill it right after that. In the worst case task will be scheduled once and throttled at the end of slice.

From f12fa8e981bf1d87cbbc30951bdf27e70c803e25 Mon Sep 17 00:00:00 2001

Quoted 4 lines · Konstantin Khlebnikov

Pick_next_task_fair() must be sure that here is at least one runnable task before calling put_prev_task(), but put_prev_task() can expire last remains of cfs quota and throttle all currently runnable tasks. As a result pick_next_task_fair() cannot find next task and crashes.

Kernel crash looks like this:

<1>[50288.719491] BUG: unable to handle kernel NULL pointer dereference at 0000000000000038
<1>[50288.719538] IP: [<ffffffff81097b8c>] set_next_entity+0x1c/0x80

<4>[50288.720388] Call Trace:
<4>[50288.720402]  [<ffffffff8109ead8>] pick_next_task_fair+0x88/0x5d0
<4>[50288.720479]  [<ffffffff816b5b99>] __schedule+0xf9/0x7d0

Quoted 3 lines

This patch leaves 1 in ->runtime_remaining when current assignation expires and tries to refill it right after that. In the worst case task will be scheduled once and throttled at the end of slice.

If the above set_next_entity() is indeed the simple one, does the below cure things?

---
 kernel/sched/fair.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

kernel/sched/fair.c +0 -0

index fdae26eb7218..df72d61138a8 100644
@@ -5176,12 +5176,11 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev)
 simple:
 	cfs_rq = &rq->cfs;
 #endif

Lemme think a bit more on that.

Quoted 1 line · Peter Zijlstra

Lemme think a bit more on that.

So going by 734ff2a71f9e ("sched/rt: Fix picking RT and DL tasks from empty queue") something like this would be called for.

---
  kernel/sched/fair.c | 15 +++++++++++++++
  1 file changed, 15 insertions(+)

kernel/sched/fair.c +0 -0

index fdae26eb7218..1e47f816c976 100644

kernel/sched/fair.c +4 -0

+			cfs_rq = cfs_rq_of(se);
+			check_cfs_rq_runtime(cfs_rq);
+		}
+	}
  #endif
 
  	if (!cfs_rq->nr_running)

Quoted 10 lines · Peter Zijlstra

Quoted 1 line · Peter Zijlstra

Lemme think a bit more on that.

So going by 734ff2a71f9e ("sched/rt: Fix picking RT and DL tasks from empty queue") something like this would be called for.

---
 kernel/sched/fair.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

kernel/sched/fair.c pick_next_task_fair(struct rq *rq, struct task_struct *prev) · line 5177

Quoted 8 lines

kernel/sched/fair.c +0 -0

index fdae26eb7218..1e47f816c976 100644
@@ -5175,6 +5175,21 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev)
 	return p;
 simple:
 	cfs_rq = &rq->cfs;

We don't need this if prev isn't from fair_sched_class:
first "goto simple" should go directly to "if (!cfs_rq->nr_running)".

Quoted 4 lines

kernel/sched/fair.c +4 -0

+	if (cfs_bandwidth_used()) {
+		/*
+		 * We may dequeue prev's cfs_rq in put_prev_task().
+		 * So, we update time before cfs_rq->nr_running check.

kernel/sched/fair.c pick_next_task_fair(struct rq *rq, struct task_struct *prev) · line 5188

Quoted 6 lines

kernel/sched/fair.c +6 -0

+		 */
+		if (prev->on_rq)
+			update_curr(cfs_rq);
+
+		se = &prev->se;
+		for_each_sched_entity(se) {

Probably update_curr() should be inside loop too?

Quoted 8 lines

kernel/sched/fair.c +4 -0

+			cfs_rq = cfs_rq_of(se);
+			check_cfs_rq_runtime(cfs_rq);
+		}
+	}
 #endif
 
 	if (!cfs_rq->nr_running)

Signature · 1 line

Konstantin

Quoted 9 lines · Konstantin Khlebnikov

Pick_next_task_fair() must be sure that here is at least one runnable task before calling put_prev_task(), but put_prev_task() can expire last remains of cfs quota and throttle all currently runnable tasks. As a result pick_next_task_fair() cannot find next task and crashes.

This patch leaves 1 in ->runtime_remaining when current assignation expires and tries to refill it right after that. In the worst case task will be scheduled once and throttled at the end of slice.

I don't think expire_cfs_rq_runtime is the problem. What I believe happens is this:

/prev/some_task is running, calls schedule() with nr_running == 2. pick_next's first do/while loop does update_curr(/) and picks /next, and the next iteration just sees check_cfs_rq_runtime(/next), and thus does goto simple. However, there is now only /prev/some_task runnable, and it hasn't checked the entire prev hierarchy for throttling, thus leading to the crash.

This would require that check_cfs_rq_runtime(/next) return true despite being on_rq though, which iirc is not supposed to happen (note that we do not call update_curr(/next), and it would do nothing if we did, because /next isn't part of the current thread's hierarchy). However, this /can/ happen if runtime has just been (re)enabled on /next, because tg_set_cfs_bandwidth sets runtime_remaining to 0, not 1.

The idea was that each rq would grab runtime when they were scheduled (pick_next_task_fair didn't ever look at throttling info), so this was fine with the old code, but is a problem now. I think it would be sufficient to just initialize to 1 in tg_set_cfs_bandwidth. The arguably more precise option would be to only check_cfs_rq_runtime if cfs_rq->curr is set, but the code is slightly less pretty.

Could you check this patch to see if it works (or the trivial tg_set_bandwidth runtime_remaining = 1 patch)?

---8<----->8---

From f12fa8e981bf1d87cbbc30951bdf27e70c803e25 Mon Sep 17 00:00:00 2001
From: Ben Segall <[email protected]>
Date: Mon, 6 Apr 2015 15:28:10 -0700
Subject: [PATCH] sched: prevent throttle in early pick_next_task_fair

The first call to check_cfs_rq_runtime in pick_next_task_fair is only supposed to trigger when cfs_rq is still an ancestor of prev. However, it was able to trigger on tgs that had just had bandwidth toggled, because tg_set_cfs_bandwidth set runtime_remaining to 0, and check_cfs_rq_runtime doesn't check the global pool.

Fix this by only calling check_cfs_rq_runtime if we are still in prev's ancestry, as evidenced by cfs_rq->curr.

Reported-by Konstantin Khlebnikov <[email protected]>

Signed-off-by Ben Segall <[email protected]>

---
  kernel/sched/fair.c | 25 ++++++++++++++-----------
  1 file changed, 14 insertions(+), 11 deletions(-)

kernel/sched/fair.c +14 -11

index ee595ef..5cb52e9 100644
@@ -5038,18 +5038,21 @@ again:
  		 * entity, update_curr() will update its vruntime, otherwise
  		 * forget we've ever seen it.
  		 */
-		if (curr && curr->on_rq)
-			update_curr(cfs_rq);
-		else
-			curr = NULL;
+		if (curr) {
+			if (curr->on_rq)
+				update_curr(cfs_rq);
+			else
+				curr = NULL;
 
-		/*
-		 * This call to check_cfs_rq_runtime() will do the throttle and
-		 * dequeue its entity in the parent(s). Therefore the 'simple'
-		 * nr_running test will indeed be correct.
-		 */
-		if (unlikely(check_cfs_rq_runtime(cfs_rq)))
-			goto simple;
+			/*
+			 * This call to check_cfs_rq_runtime() will do the
+			 * throttle and dequeue its entity in the parent(s).
+			 * Therefore the 'simple' nr_running test will indeed
+			 * be correct.
+			 */
+			if (unlikely(check_cfs_rq_runtime(cfs_rq)))
+				goto simple;
+		}
 
  		se = pick_next_entity(cfs_rq, curr);
  		cfs_rq = group_cfs_rq(se);