Skip to contentSkip to conversation

sched: Make Priority Inheritance POSIX compliant

PATCH In review Thomas Gleixner 5 participants 11 messages Jan 20, 2010 – Jan 22, 2010 Scheduler

lore
Share & tools
lore
#0 lore raw

cover sched: Make Priority Inheritance POSIX compliant

The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series adresses this.

Thanks and Kudos go to Mathias Weber and Carsten Emde for analysis, test cases and initial workaround patches.

Thanks,

tglx

#1 lore raw

PATCH 1/3 sched: Extend enqueue_task to allow head queueing

The ability of enqueueing a task to the head of a SCHED_FIFO priority list is required to fix some violations of POSIX scheduling policy.

Extend the related functions with a "head" argument.

---
 include/linux/sched.h |    3 ++-
 kernel/sched.c        |   13 +++++++------
 kernel/sched_fair.c   |    3 ++-
 kernel/sched_rt.c     |    3 ++-
 4 files changed, 13 insertions(+), 9 deletions(-)
include/linux/sched.h +2 -1
Index: linux-2.6-tip/include/linux/sched.h
===================================================================
@@ -1075,7 +1075,8 @@ struct sched_domain;
 struct sched_class {
 	const struct sched_class *next;
 
-	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
+	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup,
+			      bool head);
 	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
 	void (*yield_task) (struct rq *rq);
 
kernel/sched.c +7 -6
Index: linux-2.6-tip/kernel/sched.c
===================================================================
@@ -1883,13 +1883,14 @@ static void update_avg(u64 *avg, u64 sam
 	*avg += diff >> 3;
 }
 
-static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup)
+static void
+enqueue_task(struct rq *rq, struct task_struct *p, int wakeup, bool head)
 {
 	if (wakeup)
 		p->se.start_runtime = p->se.sum_exec_runtime;
 
 	sched_info_queued(p);
-	p->sched_class->enqueue_task(rq, p, wakeup);
+	p->sched_class->enqueue_task(rq, p, wakeup, head);
 	p->se.on_rq = 1;
 }
 
@@ -1965,7 +1966,7 @@ static void activate_task(struct rq *rq,
 	if (task_contributes_to_load(p))
 		rq->nr_uninterruptible--;
 
-	enqueue_task(rq, p, wakeup);
+	enqueue_task(rq, p, wakeup, false);
 	inc_nr_running(rq);
 }
 
@@ -6065,7 +6066,7 @@ void rt_mutex_setprio(struct task_struct
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (on_rq) {
-		enqueue_task(rq, p, 0);
+		enqueue_task(rq, p, 0, false);
 
 		check_class_changed(rq, p, prev_class, oldprio, running);
 	}
@@ -6109,7 +6110,7 @@ void set_user_nice(struct task_struct *p
 	delta = p->prio - old_prio;
 
 	if (on_rq) {
-		enqueue_task(rq, p, 0);
+		enqueue_task(rq, p, 0, false);
 		/*
 		 * If the task increased its priority or is running and
 		 * lowered its priority, then reschedule its CPU:
@@ -10110,7 +10111,7 @@ void sched_move_task(struct task_struct 
 	if (unlikely(running))
 		tsk->sched_class->set_curr_task(rq);
 	if (on_rq)
-		enqueue_task(rq, tsk, 0);
+		enqueue_task(rq, tsk, 0, false);
 
 	task_rq_unlock(rq, &flags);
 }
kernel/sched_fair.c +2 -1
Index: linux-2.6-tip/kernel/sched_fair.c
===================================================================
@@ -1053,7 +1053,8 @@ static inline void hrtick_update(struct 
  * increased. Here we update the fair scheduling stats and
  * then put the task into the rbtree:
  */
-static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
+static void
+enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup, bool head)
 {
 	struct cfs_rq *cfs_rq;
 	struct sched_entity *se = &p->se;
kernel/sched_rt.c +2 -1
Index: linux-2.6-tip/kernel/sched_rt.c
===================================================================
@@ -878,7 +878,8 @@ static void dequeue_rt_entity(struct sch
 /*
  * Adding/removing a task to/from a priority array:
  */
-static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
+static void
+enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup, bool head)
 {
 	struct sched_rt_entity *rt_se = &p->rt;
 
#2 lore raw

[tip:sched/core] sched: Extend enqueue_task to allow head queueing

Commit-ID:  ea87bb7853168434f4a82426dd1ea8421f9e604d
Gitweb:     http://git.kernel.org/tip/ea87bb7853168434f4a82426dd1ea8421f9e604d
Author:     Thomas Gleixner <[email protected]>
AuthorDate: Wed, 20 Jan 2010 20:58:57 +0000
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Fri, 22 Jan 2010 18:09:59 +0100

sched: Extend enqueue_task to allow head queueing

The ability of enqueueing a task to the head of a SCHED_FIFO priority list is required to fix some violations of POSIX scheduling policy.

Extend the related functions with a "head" argument.

LKML-Reference: <[email protected]>

---
 include/linux/sched.h |    3 ++-
 kernel/sched.c        |   13 +++++++------
 kernel/sched_fair.c   |    3 ++-
 kernel/sched_rt.c     |    3 ++-
 4 files changed, 13 insertions(+), 9 deletions(-)
include/linux/sched.h +2 -1
index 8b07973..b35c0c7 100644
@@ -1067,7 +1067,8 @@ struct sched_domain;
 struct sched_class {
 	const struct sched_class *next;
 
-	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
+	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup,
+			      bool head);
 	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
 	void (*yield_task) (struct rq *rq);
 
kernel/sched.c +7 -6
index 41e76d3..f47560f 100644
@@ -1856,13 +1856,14 @@ static void update_avg(u64 *avg, u64 sample)
 	*avg += diff >> 3;
 }
 
-static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup)
+static void
+enqueue_task(struct rq *rq, struct task_struct *p, int wakeup, bool head)
 {
 	if (wakeup)
 		p->se.start_runtime = p->se.sum_exec_runtime;
 
 	sched_info_queued(p);
-	p->sched_class->enqueue_task(rq, p, wakeup);
+	p->sched_class->enqueue_task(rq, p, wakeup, head);
 	p->se.on_rq = 1;
 }
 
@@ -1892,7 +1893,7 @@ static void activate_task(struct rq *rq, struct task_struct *p, int wakeup)
 	if (task_contributes_to_load(p))
 		rq->nr_uninterruptible--;
 
-	enqueue_task(rq, p, wakeup);
+	enqueue_task(rq, p, wakeup, false);
 	inc_nr_running(rq);
 }
 
@@ -4236,7 +4237,7 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (on_rq) {
-		enqueue_task(rq, p, 0);
+		enqueue_task(rq, p, 0, false);
 
 		check_class_changed(rq, p, prev_class, oldprio, running);
 	}
@@ -4280,7 +4281,7 @@ void set_user_nice(struct task_struct *p, long nice)
 	delta = p->prio - old_prio;
 
 	if (on_rq) {
-		enqueue_task(rq, p, 0);
+		enqueue_task(rq, p, 0, false);
 		/*
 		 * If the task increased its priority or is running and
 		 * lowered its priority, then reschedule its CPU:
@@ -8230,7 +8231,7 @@ void sched_move_task(struct task_struct *tsk)
 	if (unlikely(running))
 		tsk->sched_class->set_curr_task(rq);
 	if (on_rq)
-		enqueue_task(rq, tsk, 0);
+		enqueue_task(rq, tsk, 0, false);
 
 	task_rq_unlock(rq, &flags);
 }
kernel/sched_fair.c +2 -1
index 22231cc..0e7a7af 100644
@@ -1053,7 +1053,8 @@ static inline void hrtick_update(struct rq *rq)
  * increased. Here we update the fair scheduling stats and
  * then put the task into the rbtree:
  */
-static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
+static void
+enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup, bool head)
 {
 	struct cfs_rq *cfs_rq;
 	struct sched_entity *se = &p->se;
kernel/sched_rt.c +2 -1
index 502bb61..38076da 100644
@@ -878,7 +878,8 @@ static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
 /*
  * Adding/removing a task to/from a priority array:
  */
-static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
+static void
+enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup, bool head)
 {
 	struct sched_rt_entity *rt_se = &p->rt;
 
#3 lore raw

PATCH 2/3 sched: Implement head queueing for sched_rt

In reply to Thomas Gleixner

The ability of enqueueing a task to the head of a SCHED_FIFO priority list is required to fix some violations of POSIX scheduling policy.

Implement the functionality in sched_rt.

---
 kernel/sched_rt.c |   19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)
kernel/sched_rt.c +11 -8
Index: linux-2.6-tip/kernel/sched_rt.c
===================================================================
@@ -194,7 +194,7 @@ static inline struct rt_rq *group_rt_rq(
 	return rt_se->my_q;
 }
 
-static void enqueue_rt_entity(struct sched_rt_entity *rt_se);
+static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head);
 static void dequeue_rt_entity(struct sched_rt_entity *rt_se);
 
 static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
@@ -204,7 +204,7 @@ static void sched_rt_rq_enqueue(struct r
 
 	if (rt_rq->rt_nr_running) {
 		if (rt_se && !on_rt_rq(rt_se))
-			enqueue_rt_entity(rt_se);
+			enqueue_rt_entity(rt_se, false);
 		if (rt_rq->highest_prio.curr < curr->prio)
 			resched_task(curr);
 	}
@@ -803,7 +803,7 @@ void dec_rt_tasks(struct sched_rt_entity
 	dec_rt_group(rt_se, rt_rq);
 }
 
-static void __enqueue_rt_entity(struct sched_rt_entity *rt_se)
+static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
 {
 	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
 	struct rt_prio_array *array = &rt_rq->active;
@@ -819,7 +819,10 @@ static void __enqueue_rt_entity(struct s
 	if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
 		return;
 
-	list_add_tail(&rt_se->run_list, queue);
+	if (head)
+		list_add(&rt_se->run_list, queue);
+	else
+		list_add_tail(&rt_se->run_list, queue);
 	__set_bit(rt_se_prio(rt_se), array->bitmap);
 
 	inc_rt_tasks(rt_se, rt_rq);
@@ -856,11 +859,11 @@ static void dequeue_rt_stack(struct sche
 	}
 }
 
-static void enqueue_rt_entity(struct sched_rt_entity *rt_se)
+static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
 {
 	dequeue_rt_stack(rt_se);
 	for_each_sched_rt_entity(rt_se)
-		__enqueue_rt_entity(rt_se);
+		__enqueue_rt_entity(rt_se, head);
 }
 
 static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
@@ -871,7 +874,7 @@ static void dequeue_rt_entity(struct sch
 		struct rt_rq *rt_rq = group_rt_rq(rt_se);
 
 		if (rt_rq && rt_rq->rt_nr_running)
-			__enqueue_rt_entity(rt_se);
+			__enqueue_rt_entity(rt_se, false);
 	}
 }
 
@@ -886,7 +889,7 @@ enqueue_task_rt(struct rq *rq, struct ta
 	if (wakeup)
 		rt_se->timeout = 0;
 
-	enqueue_rt_entity(rt_se);
+	enqueue_rt_entity(rt_se, head);
 
 	if (!task_current(rq, p) && p->rt.nr_cpus_allowed > 1)
 		enqueue_pushable_task(rq, p);
#4 lore raw

[tip:sched/core] sched: Implement head queueing for sched_rt

Commit-ID:  37dad3fce97f01e5149d69de0833d8452c0e862e
Gitweb:     http://git.kernel.org/tip/37dad3fce97f01e5149d69de0833d8452c0e862e
Author:     Thomas Gleixner <[email protected]>
AuthorDate: Wed, 20 Jan 2010 20:59:01 +0000
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Fri, 22 Jan 2010 18:09:59 +0100

sched: Implement head queueing for sched_rt

The ability of enqueueing a task to the head of a SCHED_FIFO priority list is required to fix some violations of POSIX scheduling policy.

Implement the functionality in sched_rt.

LKML-Reference: <[email protected]>

---
 kernel/sched_rt.c |   19 +++++++++++--------
 1 files changed, 11 insertions(+), 8 deletions(-)
kernel/sched_rt.c +11 -8
index 38076da..ca49ceb 100644
@@ -194,7 +194,7 @@ static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
 	return rt_se->my_q;
 }
 
-static void enqueue_rt_entity(struct sched_rt_entity *rt_se);
+static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head);
 static void dequeue_rt_entity(struct sched_rt_entity *rt_se);
 
 static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
@@ -204,7 +204,7 @@ static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
 
 	if (rt_rq->rt_nr_running) {
 		if (rt_se && !on_rt_rq(rt_se))
-			enqueue_rt_entity(rt_se);
+			enqueue_rt_entity(rt_se, false);
 		if (rt_rq->highest_prio.curr < curr->prio)
 			resched_task(curr);
 	}
@@ -803,7 +803,7 @@ void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 	dec_rt_group(rt_se, rt_rq);
 }
 
-static void __enqueue_rt_entity(struct sched_rt_entity *rt_se)
+static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
 {
 	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
 	struct rt_prio_array *array = &rt_rq->active;
@@ -819,7 +819,10 @@ static void __enqueue_rt_entity(struct sched_rt_entity *rt_se)
 	if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
 		return;
 
-	list_add_tail(&rt_se->run_list, queue);
+	if (head)
+		list_add(&rt_se->run_list, queue);
+	else
+		list_add_tail(&rt_se->run_list, queue);
 	__set_bit(rt_se_prio(rt_se), array->bitmap);
 
 	inc_rt_tasks(rt_se, rt_rq);
@@ -856,11 +859,11 @@ static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
 	}
 }
 
-static void enqueue_rt_entity(struct sched_rt_entity *rt_se)
+static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
 {
 	dequeue_rt_stack(rt_se);
 	for_each_sched_rt_entity(rt_se)
-		__enqueue_rt_entity(rt_se);
+		__enqueue_rt_entity(rt_se, head);
 }
 
 static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
@@ -871,7 +874,7 @@ static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
 		struct rt_rq *rt_rq = group_rt_rq(rt_se);
 
 		if (rt_rq && rt_rq->rt_nr_running)
-			__enqueue_rt_entity(rt_se);
+			__enqueue_rt_entity(rt_se, false);
 	}
 }
 
@@ -886,7 +889,7 @@ enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup, bool head)
 	if (wakeup)
 		rt_se->timeout = 0;
 
-	enqueue_rt_entity(rt_se);
+	enqueue_rt_entity(rt_se, head);
 
 	if (!task_current(rq, p) && p->rt.nr_cpus_allowed > 1)
 		enqueue_pushable_task(rq, p);
#5 lore raw

PATCH 3/3 sched: Queue a deboosted task to the head of the RT priority queue

In reply to Thomas Gleixner

rtmutex_set_prio() is used to implement priority inheritance for futexes. When a task is deboosted it gets enqueued at the tail of its RT priority list. This is violating the POSIX scheduling semantics:

rt priority list X contains two runnable tasks A and B

task A runs with priority X and holds mutex M
task C preempts A and is blocked on mutex M

     	 -> task A is boosted to priority of task C (Y)
task A	 unlocks the mutex M and deboosts itself
     	 -> A is dequeued from rt priority list Y
	 -> A is enqueued to the tail of rt priority list X

task C schedules away
task B runs

This is wrong as task A did not schedule away and therefor violates the POSIX scheduling semantics.

Enqueue the task to the head of the priority list instead.

---
 kernel/sched.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched.c +1 -1
Index: linux-2.6-tip/kernel/sched.c
===================================================================
@@ -6066,7 +6066,7 @@ void rt_mutex_setprio(struct task_struct
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (on_rq) {
-		enqueue_task(rq, p, 0, false);
+		enqueue_task(rq, p, 0, oldprio < prio);
 
 		check_class_changed(rq, p, prev_class, oldprio, running);
 	}
#6 lore raw

[tip:sched/core] sched: Queue a deboosted task to the head of the RT prio queue

Commit-ID:  60db48cacb9b253d5607a5ff206112a59cd09e34
Gitweb:     http://git.kernel.org/tip/60db48cacb9b253d5607a5ff206112a59cd09e34
Author:     Thomas Gleixner <[email protected]>
AuthorDate: Wed, 20 Jan 2010 20:59:06 +0000
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Fri, 22 Jan 2010 18:09:59 +0100

sched: Queue a deboosted task to the head of the RT prio queue

rtmutex_set_prio() is used to implement priority inheritance for futexes. When a task is deboosted it gets enqueued at the tail of its RT priority list. This is violating the POSIX scheduling semantics:

rt priority list X contains two runnable tasks A and B

task A runs with priority X and holds mutex M
task C preempts A and is blocked on mutex M

     	 -> task A is boosted to priority of task C (Y)
task A	 unlocks the mutex M and deboosts itself
     	 -> A is dequeued from rt priority list Y
	 -> A is enqueued to the tail of rt priority list X

task C schedules away
task B runs

This is wrong as task A did not schedule away and therefor violates the POSIX scheduling semantics.

Enqueue the task to the head of the priority list instead.

LKML-Reference: <[email protected]>

---
 kernel/sched.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched.c +1 -1
index f47560f..a56ead4 100644
@@ -4237,7 +4237,7 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
 	if (running)
 		p->sched_class->set_curr_task(rq);
 	if (on_rq) {
-		enqueue_task(rq, p, 0, false);
+		enqueue_task(rq, p, 0, oldprio < prio);
 
 		check_class_changed(rq, p, prev_class, oldprio, running);
 	}
maintainer Acked-by on the v1 series
#7 lore raw
In reply to Thomas Gleixner
Quoted 5 lines · Thomas Gleixner

The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series adresses this.

Thanks and Kudos go to Mathias Weber and Carsten Emde for analysis, test cases and initial workaround patches.

These look fine to me,

#8 lore raw
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Thomas Gleixner

The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series adresses this.

Thanks and Kudos go to Mathias Weber and Carsten Emde for analysis, test cases and initial workaround patches.

Oh, that sounds good - would you like to share the test cases for our rt-test suite?

Quoted 11 lines

These look fine to me,

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Tested-by on the v1 series
#9 lore raw
In reply to Thomas Gleixner
Quoted 2 lines · Thomas Gleixner

The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series addresses this.

I can confirm that this patch series fixes the incorrect scheduling behavior as observed in our test case.

Thanks, Thomas!

Tested-by Mathias Weber on the v1 series
#10 lore raw
In reply to Thomas Gleixner
Quoted 2 lines · Thomas Gleixner

The current PI implementation violates POSIX scheduling semantics when a thread is deboosted. The following patch series adresses this.

I did rerun the test case with this patches applied and I can confirm that this fixes the incorrect scheduling behavior in our test case.

Thanks, Thomas and Carsten for your help.