sched: Fix PI handling vs sched_setscheduler()

PATCH In review Peter Zijlstra 2 participants 5 messages Jan 19, 2016 – Jan 20, 2016 Scheduler

lore

Share & tools

lore

Peter Zijlstra

author maintainer

2016-01-19 11:19 UTC #0 lore raw

PATCH 1/1 sched: Fix PI handling vs sched_setscheduler()

Andrea Parri reported:

Quoted 27 lines

I found that the following scenario (with CONFIG_RT_GROUP_SCHED=y) is not handled correctly:

    T1 (prio = 20)
       lock(rtmutex);

    T2 (prio = 20)
       blocks on rtmutex  (rt_nr_boosted = 0 on T1's rq)

    T1 (prio = 20)
       sys_set_scheduler(prio = 0)
          [new_effective_prio == oldprio]
          T1 prio = 20    (rt_nr_boosted = 0 on T1's rq)

The last step is incorrect as T1 is now boosted (c.f., rt_se_boosted()); in particular, if we continue with

   T1 (prio = 20)
      unlock(rtmutex)
         wakeup(T2)
         adjust_prio(T1)
            [prio != rt_mutex_getprio(T1)]
	    dequeue(T1)
	       rt_nr_boosted = (unsigned long)(-1)
	       ...
            T1 prio = 0

Quoted 8 lines

then we end up leaving rt_nr_boosted in an "inconsistent" state.
The simple program attached could reproduce the previous scenario; note that, as a consequence of the presence of this state, the "assertion"
    WARN_ON(!rt_nr_running && rt_nr_boosted)
from dec_rt_group() may trigger.

Hmm, so normally we dequeue/enqueue tasks in sched_setscheduler(), which would ensure the accounting stays correct. However in the early PI path we fail to do so.

So this was introduced by c365c292d0590, which fixed another problem exactly because that dequeue/enqueue, joy.

Fix this by teaching rt about DEQUEUE_SAVE/ENQUEUE_RESTORE and have it preserve runqueue location with that option. This requires decoupling the on_rt_rq() state from being on the list.

In order to allow for explicit movement during the SAVE/RESTORE, introduce {DE,EN}QUEUE_MOVE. We still must use SAVE/RESTORE in these cases to preserve other invariants.

Respecting the SAVE/RESTORE flags also has the (nice) side-effect that things like sys_nice()/sys_sched_setaffinity() also do not reorder FIFO tasks (whereas they used to before this patch).

Cc [email protected]

Cc Steven Rostedt <[email protected]>

Cc Juri Lelli <[email protected]>

Reported-by Andrea Parri <[email protected]>

Tested-by Andrea Parri <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 include/linux/sched.h |    2 +
 kernel/sched/core.c   |   35 ++++++++++----------
 kernel/sched/rt.c     |   86 ++++++++++++++++++++++++++++++++++----------------
 kernel/sched/sched.h  |   31 +++++++++++++-----
 4 files changed, 104 insertions(+), 50 deletions(-)

include/linux/sched.h +2 -0

@@ -1287,6 +1287,8 @@ struct sched_rt_entity {
 	unsigned long timeout;
 	unsigned long watchdog_stamp;
 	unsigned int time_slice;
+	unsigned short on_rq;
+	unsigned short on_list;
 
 	struct sched_rt_entity *back;
 #ifdef CONFIG_RT_GROUP_SCHED

kernel/sched/core.c +18 ~~-17~~

@@ -3466,7 +3466,7 @@ EXPORT_SYMBOL(default_wake_function);
  */
 void rt_mutex_setprio(struct task_struct *p, int prio)
 {
-	int oldprio, queued, running, enqueue_flag = ENQUEUE_RESTORE;
+	int oldprio, queued, running, queue_flag = DEQUEUE_SAVE | DEQUEUE_MOVE;
 	struct rq *rq;
 	const struct sched_class *prev_class;

@@ -3494,11 +3494,15 @@ void rt_mutex_setprio(struct task_struct
 
 	trace_sched_pi_setprio(p, prio);
 	oldprio = p->prio;
+
+	if (oldprio == prio)
+		queue_flag &= ~DEQUEUE_MOVE;
+
 	prev_class = p->sched_class;
 	queued = task_on_rq_queued(p);
 	running = task_current(rq, p);
 	if (queued)
-		dequeue_task(rq, p, DEQUEUE_SAVE);
+		dequeue_task(rq, p, queue_flag);
 	if (running)
 		put_prev_task(rq, p);

@@ -3516,7 +3520,7 @@ void rt_mutex_setprio(struct task_struct
 		if (!dl_prio(p->normal_prio) ||
 		    (pi_task && dl_entity_preempt(&pi_task->dl, &p->dl))) {
 			p->dl.dl_boosted = 1;
-			enqueue_flag |= ENQUEUE_REPLENISH;
+			queue_flag |= ENQUEUE_REPLENISH;
 		} else
 			p->dl.dl_boosted = 0;
 		p->sched_class = &dl_sched_class;

@@ -3524,7 +3528,7 @@ void rt_mutex_setprio(struct task_struct
 		if (dl_prio(oldprio))
 			p->dl.dl_boosted = 0;
 		if (oldprio < prio)
-			enqueue_flag |= ENQUEUE_HEAD;
+			queue_flag |= ENQUEUE_HEAD;
 		p->sched_class = &rt_sched_class;
 	} else {
 		if (dl_prio(oldprio))

@@ -3539,7 +3543,7 @@ void rt_mutex_setprio(struct task_struct
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (queued)
-		enqueue_task(rq, p, enqueue_flag);
+		enqueue_task(rq, p, queue_flag);
 
 	check_class_changed(rq, p, prev_class, oldprio);
 out_unlock:

@@ -3895,6 +3899,7 @@ static int __sched_setscheduler(struct t
 	const struct sched_class *prev_class;
 	struct rq *rq;
 	int reset_on_fork;
+	int queue_flags = DEQUEUE_SAVE | DEQUEUE_MOVE;
 
 	/* may grab non-irq protected spin_locks */
 	BUG_ON(in_interrupt());

@@ -4077,17 +4082,14 @@ static int __sched_setscheduler(struct t
 		 * itself.
 		 */
 		new_effective_prio = rt_mutex_get_effective_prio(p, newprio);
-		if (new_effective_prio == oldprio) {
-			__setscheduler_params(p, attr);
-			task_rq_unlock(rq, p, &flags);
-			return 0;
-		}
+		if (new_effective_prio == oldprio)
+			queue_flags &= ~DEQUEUE_MOVE;
 	}
 
 	queued = task_on_rq_queued(p);
 	running = task_current(rq, p);
 	if (queued)
-		dequeue_task(rq, p, DEQUEUE_SAVE);
+		dequeue_task(rq, p, queue_flags);
 	if (running)
 		put_prev_task(rq, p);

@@ -4097,15 +4099,14 @@ static int __sched_setscheduler(struct t
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (queued) {
-		int enqueue_flags = ENQUEUE_RESTORE;
 		/*
 		 * We enqueue to tail when the priority of a task is
 		 * increased (user space view).
 		 */
-		if (oldprio <= p->prio)
-			enqueue_flags |= ENQUEUE_HEAD;
+		if (oldprio < p->prio)
+			queue_flags |= ENQUEUE_HEAD;
 
-		enqueue_task(rq, p, enqueue_flags);
+		enqueue_task(rq, p, queue_flags);
 	}
 
 	check_class_changed(rq, p, prev_class, oldprio);

@@ -7890,7 +7891,7 @@ void sched_move_task(struct task_struct
 	queued = task_on_rq_queued(tsk);
 
 	if (queued)
-		dequeue_task(rq, tsk, DEQUEUE_SAVE);
+		dequeue_task(rq, tsk, DEQUEUE_SAVE | DEQUEUE_MOVE);
 	if (unlikely(running))
 		put_prev_task(rq, tsk);

@@ -7914,7 +7915,7 @@ void sched_move_task(struct task_struct
 	if (unlikely(running))
 		tsk->sched_class->set_curr_task(rq);
 	if (queued)
-		enqueue_task(rq, tsk, ENQUEUE_RESTORE);
+		enqueue_task(rq, tsk, ENQUEUE_RESTORE | ENQUEUE_MOVE);
 
 	task_rq_unlock(rq, tsk, &flags);
 }

kernel/sched/rt.c +60 ~~-26~~

174 lines not on this page · raw message

kernel/sched/sched.h +24 -7

@@ -1130,18 +1130,35 @@ static inline void finish_lock_switch(st
 extern const int sched_prio_to_weight[40];
 extern const u32 sched_prio_to_wmult[40];
 
+/*
+ * {de,en}queue flags:
+ *
+ * SAVE/RESTORE - an otherwise spurious dequeue/enqueue, done to ensure tasks
+ *                are in a known state which allows modification. Such pairs
+ *                should preserve as much state as possible.
+ *
+ * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
+ *        in the runqueue.
+ *
+ * ENQUEUE_HEAD - place at front of runqueue (tail if not specificed)
+ *
+ */
+
+#define DEQUEUE_SLEEP		0x01
+#define DEQUEUE_SAVE		0x02 /* matches ENQUEUE_RESTORE */
+#define DEQUEUE_MOVE		0x04 /* matches ENQUEUE_MOVE */
+
 #define ENQUEUE_WAKEUP		0x01
-#define ENQUEUE_HEAD		0x02
+#define ENQUEUE_RESTORE		0x02
+#define ENQUEUE_MOVE		0x04
+
+#define ENQUEUE_HEAD		0x08
+#define ENQUEUE_REPLENISH	0x10
 #ifdef CONFIG_SMP
-#define ENQUEUE_WAKING		0x04	/* sched_class::task_waking was called */
+#define ENQUEUE_WAKING		0x20	/* sched_class::task_waking was called */
 #else
 #define ENQUEUE_WAKING		0x00
 #endif
-#define ENQUEUE_REPLENISH	0x08
-#define ENQUEUE_RESTORE	0x10
-
-#define DEQUEUE_SLEEP		0x01
-#define DEQUEUE_SAVE		0x02
 
 #define RETRY_TASK		((void *)-1UL)

Juri Lelli

2016-01-20 10:08 UTC #1 lore raw

Hi,

On 19/01/16 12:18, Peter Zijlstra wrote:

[...]

kernel/sched/core.c static int __sched_setscheduler(struct t · line 4107

Quoted 13 lines

kernel/sched/core.c +2 -3

@@ -4097,15 +4099,14 @@ static int __sched_setscheduler(struct t
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (queued) {
-		int enqueue_flags = ENQUEUE_RESTORE;
 		/*
 		 * We enqueue to tail when the priority of a task is
 		 * increased (user space view).
 		 */
-		if (oldprio <= p->prio)
-			enqueue_flags |= ENQUEUE_HEAD;
+		if (oldprio < p->prio)
+			queue_flags |= ENQUEUE_HEAD;

Was this condition broken before or it needs to be changed now with this patch?

[...]

Quoted 9 lines

kernel/sched/sched.h +3 -0

@@ -1130,18 +1130,35 @@ static inline void finish_lock_switch(st
 extern const int sched_prio_to_weight[40];
 extern const u32 sched_prio_to_wmult[40];
 
+/*
+ * {de,en}queue flags:
+ *

kernel/sched/sched.h static inline void finish_lock_switch(st · line 1145

Quoted 10 lines

kernel/sched/sched.h +10 -0

+ * SAVE/RESTORE - an otherwise spurious dequeue/enqueue, done to ensure tasks
+ *                are in a known state which allows modification. Such pairs
+ *                should preserve as much state as possible.
+ *
+ * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
+ *        in the runqueue.
+ *
+ * ENQUEUE_HEAD - place at front of runqueue (tail if not specificed)
+ *
+ */

Do we want to document all the flags while we are at it? :)

Best,

- Juri

Quoted 27 lines

kernel/sched/sched.h +11 -7

+
+#define DEQUEUE_SLEEP		0x01
+#define DEQUEUE_SAVE		0x02 /* matches ENQUEUE_RESTORE */
+#define DEQUEUE_MOVE		0x04 /* matches ENQUEUE_MOVE */
+
 #define ENQUEUE_WAKEUP		0x01
-#define ENQUEUE_HEAD		0x02
+#define ENQUEUE_RESTORE		0x02
+#define ENQUEUE_MOVE		0x04
+
+#define ENQUEUE_HEAD		0x08
+#define ENQUEUE_REPLENISH	0x10
 #ifdef CONFIG_SMP
-#define ENQUEUE_WAKING		0x04	/* sched_class::task_waking was called */
+#define ENQUEUE_WAKING		0x20	/* sched_class::task_waking was called */
 #else
 #define ENQUEUE_WAKING		0x00
 #endif
-#define ENQUEUE_REPLENISH	0x08
-#define ENQUEUE_RESTORE	0x10
-
-#define DEQUEUE_SLEEP		0x01
-#define DEQUEUE_SAVE		0x02
 
 #define RETRY_TASK		((void *)-1UL)

Peter Zijlstra

author maintainer

2016-01-20 10:24 UTC #2 lore raw

Quoted 6 lines · Juri Lelli

Hi,
On 19/01/16 12:18, Peter Zijlstra wrote:
[...]

Quoted 16 lines

Review static int __sched_setscheduler(struct t · line 4107

Quoted 13 lines

(quoted diff) +2 -3

@@ -4097,15 +4099,14 @@ static int __sched_setscheduler(struct t
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (queued) {
-		int enqueue_flags = ENQUEUE_RESTORE;
 		/*
 		 * We enqueue to tail when the priority of a task is
 		 * increased (user space view).
 		 */
-		if (oldprio <= p->prio)
-			enqueue_flags |= ENQUEUE_HEAD;
+		if (oldprio < p->prio)
+			queue_flags |= ENQUEUE_HEAD;

Was this condition broken before or it needs to be changed now with this patch?

I could not see how we could get there before, seeing how the == case is handled above.

Quoted 6 lines

kernel/sched/sched.h +0 -0

@@ -1130,18 +1130,35 @@ static inline void finish_lock_switch(st
 extern const int sched_prio_to_weight[40];
 extern const u32 sched_prio_to_wmult[40];

Quoted 15 lines

kernel/sched/sched.h static inline void finish_lock_switch(st · line 1145

Quoted 13 lines

kernel/sched/sched.h +13 -0

+/*
+ * {de,en}queue flags:
+ *
+ * SAVE/RESTORE - an otherwise spurious dequeue/enqueue, done to ensure tasks
+ *                are in a known state which allows modification. Such pairs
+ *                should preserve as much state as possible.
+ *
+ * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
+ *        in the runqueue.
+ *
+ * ENQUEUE_HEAD - place at front of runqueue (tail if not specificed)
+ *
+ */

Do we want to document all the flags while we are at it? :)

Probably.. does the below work? I think I bailed on replenish because I could not come up with a coherent short description, does the below make any sense?

kernel/sched/sched.h +3 -1

@@ -1140,7 +1140,9 @@ extern const u32 sched_prio_to_wmult[40]
  * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
  *        in the runqueue.
  *
- * ENQUEUE_HEAD - place at front of runqueue (tail if not specificed)
+ * ENQUEUE_HEAD      - place at front of runqueue (tail if not specificed)
+ * ENQUEUE_REPLENISH - push the CBS slot forward
+ * ENQUEUE_WAKING    - sched_class::task_waking was called
  *
  */

Juri Lelli

2016-01-20 10:33 UTC #3 lore raw

Quoted 57 lines · Peter Zijlstra

Quoted 6 lines · Juri Lelli
Hi,
On 19/01/16 12:18, Peter Zijlstra wrote:
[...]
Quoted 16 lines
Review static int __sched_setscheduler(struct t · line 4107
Quoted 13 lines
(quoted diff) +2 -3
@@ -4097,15 +4099,14 @@ static int __sched_setscheduler(struct t
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (queued) {
-		int enqueue_flags = ENQUEUE_RESTORE;
 		/*
 		 * We enqueue to tail when the priority of a task is
 		 * increased (user space view).
 		 */
-		if (oldprio <= p->prio)
-			enqueue_flags |= ENQUEUE_HEAD;
+		if (oldprio < p->prio)
+			queue_flags |= ENQUEUE_HEAD;
Was this condition broken before or it needs to be changed now with this patch?
I could not see how we could get there before, seeing how the == case is handled above.
Quoted 6 lines
Quoted 6 lines
kernel/sched/sched.h +0 -0
@@ -1130,18 +1130,35 @@ static inline void finish_lock_switch(st
 extern const int sched_prio_to_weight[40];
 extern const u32 sched_prio_to_wmult[40];
 
Quoted 15 lines
kernel/sched/sched.h static inline void finish_lock_switch(st · line 1145
Quoted 13 lines
kernel/sched/sched.h +13 -0
+/*
+ * {de,en}queue flags:
+ *
+ * SAVE/RESTORE - an otherwise spurious dequeue/enqueue, done to ensure tasks
+ *                are in a known state which allows modification. Such pairs
+ *                should preserve as much state as possible.
+ *
+ * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
+ *        in the runqueue.
+ *
+ * ENQUEUE_HEAD - place at front of runqueue (tail if not specificed)
+ *
+ */
Do we want to document all the flags while we are at it? :)
Probably.. does the below work? I think I bailed on replenish because I could not come up with a coherent short description, does the below make any sense?

kernel/sched/sched.h extern const u32 sched_prio_to_wmult[40] · line 1144

Quoted 6 lines

kernel/sched/sched.h +2 -1

@@ -1140,7 +1140,9 @@ extern const u32 sched_prio_to_wmult[40]
  * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
  *        in the runqueue.
  *
- * ENQUEUE_HEAD - place at front of runqueue (tail if not specificed)
+ * ENQUEUE_HEAD      - place at front of runqueue (tail if not specificed)
+ * ENQUEUE_REPLENISH - push the CBS slot forward

* ENQUEUE_REPLENISH - CBS (replenish runtime and postpone deadline)

Maybe? :)

Quoted 5 lines

kernel/sched/sched.h +1 -0

+ * ENQUEUE_WAKING    - sched_class::task_waking was called
  *
  */

Peter Zijlstra

author maintainer

2016-01-20 11:19 UTC #4 lore raw

Quoted 7 lines · Juri Lelli

Quoted 1 line · Peter Zijlstra
+ * ENQUEUE_REPLENISH - push the CBS slot forward
* ENQUEUE_REPLENISH - CBS (replenish runtime and postpone deadline)
Maybe? :)

Done, thanks!