Skip to contentSkip to conversation

Various sched patches -v2

PATCH In review Peter Zijlstra 4 participants 19 messages Jan 28, 2014 – Jan 30, 2014 Scheduler

lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

cover Various sched patches -v2

Here's a set that seems to work properly and hopefully adresses all previously raised issues.

Daniel, I'm sorry, the idle_stamp thing wandered back over to fair.c :-)

I did test the fair bits, including bandwidth (although not very extensively).

I did not test the dl/rt bits, Steve do you have a testcase for that?

author maintainer
#1 lore raw

PATCH 1/9 sched: Remove cpu parameter for idle_balance()

From: Daniel Lezcano <[email protected]>

The cpu parameter passed to idle_balance is not needed as it could be retrieved from the struct rq.

---
 kernel/sched/core.c  |    2 +-
 kernel/sched/fair.c  |    3 ++-
 kernel/sched/sched.h |    2 +-
 3 files changed, 4 insertions(+), 3 deletions(-)
kernel/sched/core.c +1 -1
@@ -2680,7 +2680,7 @@ static void __sched __schedule(void)
 	pre_schedule(rq, prev);
 
 	if (unlikely(!rq->nr_running))
-		idle_balance(cpu, rq);
+		idle_balance(rq);
 
 	put_prev_task(rq, prev);
 	next = pick_next_task(rq);
kernel/sched/fair.c +2 -1
@@ -6359,12 +6359,13 @@ static int load_balance(int this_cpu, st
  * idle_balance is called by schedule() if this_cpu is about to become
  * idle. Attempts to pull tasks from other CPUs.
  */
-void idle_balance(int this_cpu, struct rq *this_rq)
+void idle_balance(struct rq *this_rq)
 {
 	struct sched_domain *sd;
 	int pulled_task = 0;
 	unsigned long next_balance = jiffies + HZ;
 	u64 curr_cost = 0;
+	int this_cpu = this_rq->cpu;
 
 	this_rq->idle_stamp = rq_clock(this_rq);
 
kernel/sched/sched.h +1 -1
@@ -1176,7 +1176,7 @@ extern const struct sched_class idle_sch
 extern void update_group_power(struct sched_domain *sd, int cpu);
 
 extern void trigger_load_balance(struct rq *rq);
-extern void idle_balance(int this_cpu, struct rq *this_rq);
+extern void idle_balance(struct rq *this_rq);
 
 extern void idle_enter_fair(struct rq *this_rq);
 extern void idle_exit_fair(struct rq *this_rq);
author maintainer
#2 lore raw

PATCH 2/9 sched: Fix race in idle_balance()

In reply to Peter Zijlstra

From: Daniel Lezcano <[email protected]>

The scheduler main function 'schedule()' checks if there are no more tasks on the runqueue. Then it checks if a task should be pulled in the current runqueue in idle_balance() assuming it will go to idle otherwise.

But the idle_balance() releases the rq->lock in order to lookup in the sched domains and takes the lock again right after. That opens a window where another cpu may put a task in our runqueue, so we won't go to idle but we have filled the idle_stamp, thinking we will.

This patch closes the window by checking if the runqueue has been modified but without pulling a task after taking the lock again, so we won't go to idle right after in the __schedule() function.

---
 kernel/sched/fair.c |    7 +++++++
 1 file changed, 7 insertions(+)
kernel/sched/fair.c +7 -0
@@ -6417,6 +6417,13 @@ void idle_balance(struct rq *this_rq)
 
 	raw_spin_lock(&this_rq->lock);
 
+	/*
+	 * While browsing the domains, we released the rq lock.
+	 * A task could have be enqueued in the meantime
+	 */
+	if (this_rq->nr_running && !pulled_task)
+		return;
+
 	if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
 		/*
 		 * We are going idle. next_balance may be set based on
author maintainer
#3 lore raw

PATCH 3/9 sched: Move idle_stamp up to the core

In reply to Peter Zijlstra

From: Daniel Lezcano <[email protected]>

The idle_balance modifies the idle_stamp field of the rq, making this information to be shared across core.c and fair.c. As we can know if the cpu is going to idle or not with the previous patch, let's encapsulate the idle_stamp information in core.c by moving it up to the caller. The idle_balance function returns true in case a balancing occured and the cpu won't be idle, false if no balance happened and the cpu is going idle.

---
 kernel/sched/core.c  |   11 +++++++++--
 kernel/sched/fair.c  |   14 ++++++--------
 kernel/sched/sched.h |    2 +-
 3 files changed, 16 insertions(+), 11 deletions(-)
kernel/sched/core.c +9 -2
@@ -2681,8 +2681,15 @@ static void __sched __schedule(void)
 
 	pre_schedule(rq, prev);
 
-	if (unlikely(!rq->nr_running))
-		idle_balance(rq);
+	if (unlikely(!rq->nr_running)) {
+		/*
+		 * We must set idle_stamp _before_ calling idle_balance(), such
+		 * that we measure the duration of idle_balance() as idle time.
+		 */
+		rq->idle_stamp = rq_clock(rq);
+		if (idle_balance(rq))
+			rq->idle_stamp = 0;
+	}
 
 	put_prev_task(rq, prev);
 	next = pick_next_task(rq);
kernel/sched/fair.c +6 -8
@@ -6535,7 +6535,7 @@ static int load_balance(int this_cpu, st
  * idle_balance is called by schedule() if this_cpu is about to become
  * idle. Attempts to pull tasks from other CPUs.
  */
-void idle_balance(struct rq *this_rq)
+int idle_balance(struct rq *this_rq)
 {
 	struct sched_domain *sd;
 	int pulled_task = 0;
@@ -6543,10 +6543,8 @@ void idle_balance(struct rq *this_rq)
 	u64 curr_cost = 0;
 	int this_cpu = this_rq->cpu;
 
-	this_rq->idle_stamp = rq_clock(this_rq);
-
 	if (this_rq->avg_idle < sysctl_sched_migration_cost)
-		return;
+		return 0;
 
 	/*
 	 * Drop the rq->lock, but keep IRQ/preempt disabled.
@@ -6584,10 +6582,8 @@ void idle_balance(struct rq *this_rq)
 		interval = msecs_to_jiffies(sd->balance_interval);
 		if (time_after(next_balance, sd->last_balance + interval))
 			next_balance = sd->last_balance + interval;
-		if (pulled_task) {
-			this_rq->idle_stamp = 0;
+		if (pulled_task)
 			break;
-		}
 	}
 	rcu_read_unlock();
 
@@ -6598,7 +6594,7 @@ void idle_balance(struct rq *this_rq)
 	 * A task could have be enqueued in the meantime
 	 */
 	if (this_rq->nr_running && !pulled_task)
-		return;
+		return 1;
 
 	if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
 		/*
@@ -6610,6 +6606,8 @@ void idle_balance(struct rq *this_rq)
 
 	if (curr_cost > this_rq->max_idle_balance_cost)
 		this_rq->max_idle_balance_cost = curr_cost;
+
+	return pulled_task;
 }
 
 /*
kernel/sched/sched.h +1 -1
@@ -1176,7 +1176,7 @@ extern const struct sched_class idle_sch
 extern void update_group_power(struct sched_domain *sd, int cpu);
 
 extern void trigger_load_balance(struct rq *rq);
-extern void idle_balance(struct rq *this_rq);
+extern int idle_balance(struct rq *this_rq);
 
 extern void idle_enter_fair(struct rq *this_rq);
 extern void idle_exit_fair(struct rq *this_rq);
author maintainer
#4 lore raw

PATCH 4/9 sched/fair: Track cgroup depth

In reply to Peter Zijlstra

Track depth in cgroup tree, this is useful for things like find_matching_se() where you need to get to a common parent of two sched entities.

Keeping the depth avoids having to calculate it on the spot, which saves a number of possible cache-misses.

---
 include/linux/sched.h |    1 +
 kernel/sched/fair.c   |   47 +++++++++++++++++++++--------------------------
 2 files changed, 22 insertions(+), 26 deletions(-)
include/linux/sched.h +1 -0
@@ -1064,6 +1064,7 @@ struct sched_entity {
 #endif
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
+	int			depth;
 	struct sched_entity	*parent;
 	/* rq on which this entity is (to be) queued: */
 	struct cfs_rq		*cfs_rq;
kernel/sched/fair.c +21 -26

109 lines not on this page · raw message

author maintainer
#5 lore raw

PATCH 5/9 sched: Push put_prev_task() into pick_next_task()

In reply to Peter Zijlstra

In order to avoid having to do put/set on a whole cgroup hierarchy when we context switch, push the put into pick_next_task() so that both operations are in the same function. Further changes then allow us to possibly optimize away redundant work.

---
 kernel/sched/core.c      |   21 ++++++++-------------
 kernel/sched/deadline.c  |    4 +++-
 kernel/sched/fair.c      |    5 ++++-
 kernel/sched/idle_task.c |    5 ++++-
 kernel/sched/rt.c        |   26 +++++++++++++++-----------
 kernel/sched/sched.h     |    8 +++++++-
 kernel/sched/stop_task.c |   14 ++++++++------
 7 files changed, 49 insertions(+), 34 deletions(-)
kernel/sched/core.c +8 -13
@@ -2556,18 +2556,11 @@ static inline void schedule_debug(struct
 	schedstat_inc(this_rq(), sched_count);
 }
 
-static void put_prev_task(struct rq *rq, struct task_struct *prev)
-{
-	if (prev->on_rq || rq->skip_clock_update < 0)
-		update_rq_clock(rq);
-	prev->sched_class->put_prev_task(rq, prev);
-}
-
 /*
  * Pick up the highest-prio task:
  */
 static inline struct task_struct *
-pick_next_task(struct rq *rq)
+pick_next_task(struct rq *rq, struct task_struct *prev)
 {
 	const struct sched_class *class;
 	struct task_struct *p;
@@ -2577,13 +2570,13 @@ pick_next_task(struct rq *rq)
 	 * the fair class we can call that function directly:
 	 */
 	if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
-		p = fair_sched_class.pick_next_task(rq);
+		p = fair_sched_class.pick_next_task(rq, prev);
 		if (likely(p))
 			return p;
 	}
 
 	for_each_class(class) {
-		p = class->pick_next_task(rq);
+		p = class->pick_next_task(rq, prev);
 		if (p)
 			return p;
 	}
@@ -2691,8 +2684,10 @@ static void __sched __schedule(void)
 			rq->idle_stamp = 0;
 	}
 
-	put_prev_task(rq, prev);
-	next = pick_next_task(rq);
+	if (prev->on_rq || rq->skip_clock_update < 0)
+		update_rq_clock(rq);
+
+	next = pick_next_task(rq, prev);
 	clear_tsk_need_resched(prev);
 	clear_preempt_need_resched();
 	rq->skip_clock_update = 0;
@@ -4734,7 +4729,7 @@ static void migrate_tasks(unsigned int d
 		if (rq->nr_running == 1)
 			break;
 
-		next = pick_next_task(rq);
+		next = pick_next_task(rq, NULL);
 		BUG_ON(!next);
 		next->sched_class->put_prev_task(rq, next);
 
kernel/sched/deadline.c +3 -1
@@ -989,7 +989,7 @@ static struct sched_dl_entity *pick_next
 	return rb_entry(left, struct sched_dl_entity, rb_node);
 }
 
-struct task_struct *pick_next_task_dl(struct rq *rq)
+struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev)
 {
 	struct sched_dl_entity *dl_se;
 	struct task_struct *p;
@@ -1000,6 +1000,8 @@ struct task_struct *pick_next_task_dl(st
 	if (unlikely(!dl_rq->dl_nr_running))
 		return NULL;
 
+	prev->sched_class->put_prev_task(rq, prev);
+
 	dl_se = pick_next_dl_entity(rq, dl_rq);
 	BUG_ON(!dl_se);
 
kernel/sched/fair.c +4 -1
@@ -4659,7 +4659,8 @@ static void check_preempt_wakeup(struct
 		set_last_buddy(se);
 }
 
-static struct task_struct *pick_next_task_fair(struct rq *rq)
+static struct task_struct *
+pick_next_task_fair(struct rq *rq, struct task_struct *prev)
 {
 	struct task_struct *p;
 	struct cfs_rq *cfs_rq = &rq->cfs;
@@ -4668,6 +4669,8 @@ static struct task_struct *pick_next_tas
 	if (!cfs_rq->nr_running)
 		return NULL;
 
+	prev->sched_class->put_prev_task(rq, prev);
+
 	do {
 		se = pick_next_entity(cfs_rq);
 		set_next_entity(cfs_rq, se);
kernel/sched/idle_task.c +4 -1
@@ -33,8 +33,11 @@ static void check_preempt_curr_idle(stru
 	resched_task(rq->idle);
 }
 
-static struct task_struct *pick_next_task_idle(struct rq *rq)
+static struct task_struct *
+pick_next_task_idle(struct rq *rq, struct task_struct *prev)
 {
+	prev->sched_class->put_prev_task(rq, prev);
+
 	schedstat_inc(rq, sched_goidle);
 #ifdef CONFIG_SMP
 	/* Trigger the post schedule to do an idle_enter for CFS */
kernel/sched/rt.c +15 -11
@@ -1310,15 +1310,7 @@ static struct task_struct *_pick_next_ta
 {
 	struct sched_rt_entity *rt_se;
 	struct task_struct *p;
-	struct rt_rq *rt_rq;
-
-	rt_rq = &rq->rt;
-
-	if (!rt_rq->rt_nr_running)
-		return NULL;
-
-	if (rt_rq_throttled(rt_rq))
-		return NULL;
+	struct rt_rq *rt_rq  = &rq->rt;
 
 	do {
 		rt_se = pick_next_rt_entity(rq, rt_rq);
@@ -1332,9 +1324,21 @@ static struct task_struct *_pick_next_ta
 	return p;
 }
 
-static struct task_struct *pick_next_task_rt(struct rq *rq)
+static struct task_struct *
+pick_next_task_rt(struct rq *rq, struct task_struct *prev)
 {
-	struct task_struct *p = _pick_next_task_rt(rq);
+	struct task_struct *p;
+	struct rt_rq *rt_rq = &rq->rt;
+
+	if (!rt_rq->rt_nr_running)
+		return NULL;
+
+	if (rt_rq_throttled(rt_rq))
+		return NULL;
+
+	prev->sched_class->put_prev_task(rq, prev);
+
+	p = _pick_next_task_rt(rq);
 
 	/* The running task is never eligible for pushing */
 	if (p)
kernel/sched/sched.h +7 -1
@@ -1123,7 +1123,13 @@ struct sched_class {
 
 	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
 
-	struct task_struct * (*pick_next_task) (struct rq *rq);
+	/*
+	 * It is the responsibility of the pick_next_task() method that will
+	 * return the next task to call put_prev_task() on the @prev task or
+	 * something equivalent.
+	 */
+	struct task_struct * (*pick_next_task) (struct rq *rq,
+						struct task_struct *prev);
 	void (*put_prev_task) (struct rq *rq, struct task_struct *p);
 
 #ifdef CONFIG_SMP
kernel/sched/stop_task.c +8 -6
@@ -23,16 +23,18 @@ check_preempt_curr_stop(struct rq *rq, s
 	/* we're never preempted */
 }
 
-static struct task_struct *pick_next_task_stop(struct rq *rq)
+static struct task_struct *
+pick_next_task_stop(struct rq *rq, struct task_struct *prev)
 {
 	struct task_struct *stop = rq->stop;
 
-	if (stop && stop->on_rq) {
-		stop->se.exec_start = rq_clock_task(rq);
-		return stop;
-	}
+	if (!stop || !stop->on_rq)
+		return NULL;
 
-	return NULL;
+	prev->sched_class->put_prev_task(rq, prev);
+	stop->se.exec_start = rq_clock_task(rq);
+
+	return stop;
 }
 
 static void
#6 lore raw

Re: [PATCH 5/9] sched: Push put_prev_task() into pick_next_task()

Quoted 68 lines · Peter Zijlstra

In order to avoid having to do put/set on a whole cgroup hierarchy when we context switch, push the put into pick_next_task() so that both operations are in the same function. Further changes then allow us to possibly optimize away redundant work.

---
 kernel/sched/core.c      |   21 ++++++++-------------
 kernel/sched/deadline.c  |    4 +++-
 kernel/sched/fair.c      |    5 ++++-
 kernel/sched/idle_task.c |    5 ++++-
 kernel/sched/rt.c        |   26 +++++++++++++++-----------
 kernel/sched/sched.h     |    8 +++++++-
 kernel/sched/stop_task.c |   14 ++++++++------
 7 files changed, 49 insertions(+), 34 deletions(-)
kernel/sched/core.c +7 -12
@@ -2556,18 +2556,11 @@ static inline void schedule_debug(struct
 	schedstat_inc(this_rq(), sched_count);
 }
 
-static void put_prev_task(struct rq *rq, struct task_struct *prev)
-{
-	if (prev->on_rq || rq->skip_clock_update < 0)
-		update_rq_clock(rq);
-	prev->sched_class->put_prev_task(rq, prev);
-}
-
 /*
  * Pick up the highest-prio task:
  */
 static inline struct task_struct *
-pick_next_task(struct rq *rq)
+pick_next_task(struct rq *rq, struct task_struct *prev)
 {
 	const struct sched_class *class;
 	struct task_struct *p;
@@ -2577,13 +2570,13 @@ pick_next_task(struct rq *rq)
 	 * the fair class we can call that function directly:
 	 */
 	if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
-		p = fair_sched_class.pick_next_task(rq);
+		p = fair_sched_class.pick_next_task(rq, prev);
 		if (likely(p))
 			return p;
 	}
 
 	for_each_class(class) {
-		p = class->pick_next_task(rq);
+		p = class->pick_next_task(rq, prev);
 		if (p)
 			return p;
 	}
@@ -2691,8 +2684,10 @@ static void __sched __schedule(void)
 			rq->idle_stamp = 0;
 	}
 
-	put_prev_task(rq, prev);
-	next = pick_next_task(rq);
+	if (prev->on_rq || rq->skip_clock_update < 0)
+		update_rq_clock(rq);
+
+	next = pick_next_task(rq, prev);
 	clear_tsk_need_resched(prev);
 	clear_preempt_need_resched();
 	rq->skip_clock_update = 0;

kernel/sched/core.c static void migrate_tasks(unsigned int d · line 4732

Quoted 5 lines
kernel/sched/core.c +1 -1
@@ -4734,7 +4729,7 @@ static void migrate_tasks(unsigned int d
 		if (rq->nr_running == 1)
 			break;
 
-		next = pick_next_task(rq);
+		next = pick_next_task(rq, NULL);

This seems to be incorrect without the if (prev) lines in pick_next_task_foo, since foo_nr_running isn't enough to save us.

Quoted 146 lines
kernel/sched/core.c +0 -0
 		BUG_ON(!next);
 		next->sched_class->put_prev_task(rq, next);
 
kernel/sched/deadline.c +3 -1
@@ -989,7 +989,7 @@ static struct sched_dl_entity *pick_next
 	return rb_entry(left, struct sched_dl_entity, rb_node);
 }
 
-struct task_struct *pick_next_task_dl(struct rq *rq)
+struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev)
 {
 	struct sched_dl_entity *dl_se;
 	struct task_struct *p;
@@ -1000,6 +1000,8 @@ struct task_struct *pick_next_task_dl(st
 	if (unlikely(!dl_rq->dl_nr_running))
 		return NULL;
 
+	prev->sched_class->put_prev_task(rq, prev);
+
 	dl_se = pick_next_dl_entity(rq, dl_rq);
 	BUG_ON(!dl_se);
 
kernel/sched/fair.c +4 -1
@@ -4659,7 +4659,8 @@ static void check_preempt_wakeup(struct
 		set_last_buddy(se);
 }
 
-static struct task_struct *pick_next_task_fair(struct rq *rq)
+static struct task_struct *
+pick_next_task_fair(struct rq *rq, struct task_struct *prev)
 {
 	struct task_struct *p;
 	struct cfs_rq *cfs_rq = &rq->cfs;
@@ -4668,6 +4669,8 @@ static struct task_struct *pick_next_tas
 	if (!cfs_rq->nr_running)
 		return NULL;
 
+	prev->sched_class->put_prev_task(rq, prev);
+
 	do {
 		se = pick_next_entity(cfs_rq);
 		set_next_entity(cfs_rq, se);
kernel/sched/idle_task.c +4 -1
@@ -33,8 +33,11 @@ static void check_preempt_curr_idle(stru
 	resched_task(rq->idle);
 }
 
-static struct task_struct *pick_next_task_idle(struct rq *rq)
+static struct task_struct *
+pick_next_task_idle(struct rq *rq, struct task_struct *prev)
 {
+	prev->sched_class->put_prev_task(rq, prev);
+
 	schedstat_inc(rq, sched_goidle);
 #ifdef CONFIG_SMP
 	/* Trigger the post schedule to do an idle_enter for CFS */
kernel/sched/rt.c +15 -11
@@ -1310,15 +1310,7 @@ static struct task_struct *_pick_next_ta
 {
 	struct sched_rt_entity *rt_se;
 	struct task_struct *p;
-	struct rt_rq *rt_rq;
-
-	rt_rq = &rq->rt;
-
-	if (!rt_rq->rt_nr_running)
-		return NULL;
-
-	if (rt_rq_throttled(rt_rq))
-		return NULL;
+	struct rt_rq *rt_rq  = &rq->rt;
 
 	do {
 		rt_se = pick_next_rt_entity(rq, rt_rq);
@@ -1332,9 +1324,21 @@ static struct task_struct *_pick_next_ta
 	return p;
 }
 
-static struct task_struct *pick_next_task_rt(struct rq *rq)
+static struct task_struct *
+pick_next_task_rt(struct rq *rq, struct task_struct *prev)
 {
-	struct task_struct *p = _pick_next_task_rt(rq);
+	struct task_struct *p;
+	struct rt_rq *rt_rq = &rq->rt;
+
+	if (!rt_rq->rt_nr_running)
+		return NULL;
+
+	if (rt_rq_throttled(rt_rq))
+		return NULL;
+
+	prev->sched_class->put_prev_task(rq, prev);
+
+	p = _pick_next_task_rt(rq);
 
 	/* The running task is never eligible for pushing */
 	if (p)
kernel/sched/sched.h +7 -1
@@ -1123,7 +1123,13 @@ struct sched_class {
 
 	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
 
-	struct task_struct * (*pick_next_task) (struct rq *rq);
+	/*
+	 * It is the responsibility of the pick_next_task() method that will
+	 * return the next task to call put_prev_task() on the @prev task or
+	 * something equivalent.
+	 */
+	struct task_struct * (*pick_next_task) (struct rq *rq,
+						struct task_struct *prev);
 	void (*put_prev_task) (struct rq *rq, struct task_struct *p);
 
 #ifdef CONFIG_SMP
kernel/sched/stop_task.c +8 -6
@@ -23,16 +23,18 @@ check_preempt_curr_stop(struct rq *rq, s
 	/* we're never preempted */
 }
 
-static struct task_struct *pick_next_task_stop(struct rq *rq)
+static struct task_struct *
+pick_next_task_stop(struct rq *rq, struct task_struct *prev)
 {
 	struct task_struct *stop = rq->stop;
 
-	if (stop && stop->on_rq) {
-		stop->se.exec_start = rq_clock_task(rq);
-		return stop;
-	}
+	if (!stop || !stop->on_rq)
+		return NULL;
 
-	return NULL;
+	prev->sched_class->put_prev_task(rq, prev);
+	stop->se.exec_start = rq_clock_task(rq);
+
+	return stop;
 }
 
 static void
author maintainer
#7 lore raw

Re: [PATCH 5/9] sched: Push put_prev_task() into pick_next_task()

Quoted 9 lines · On Tue, Jan 28, 2014 at 10:46:18AM -0800, [email protected] wrote:

kernel/sched/core.c static void migrate_tasks(unsigned int d · line 4732

Quoted 6 lines
kernel/sched/core.c +1 -1
@@ -4734,7 +4729,7 @@ static void migrate_tasks(unsigned int d
 		if (rq->nr_running == 1)
 			break;
 
-		next = pick_next_task(rq);
+		next = pick_next_task(rq, NULL);

This seems to be incorrect without the if (prev) lines in pick_next_task_foo, since foo_nr_running isn't enough to save us.

ARgh, I knew there must've been a reason I had those :/

author maintainer
#8 lore raw

PATCH 6/9 sched/fair: Clean up __clear_buddies_*

In reply to Peter Zijlstra

Slightly easier code flow, no functional changes.

---
 kernel/sched/fair.c |   18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)
kernel/sched/fair.c +9 -9
@@ -2567,10 +2567,10 @@ static void __clear_buddies_last(struct
 {
 	for_each_sched_entity(se) {
 		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-		if (cfs_rq->last == se)
-			cfs_rq->last = NULL;
-		else
+		if (cfs_rq->last != se)
 			break;
+
+		cfs_rq->last = NULL;
 	}
 }
 
@@ -2578,10 +2578,10 @@ static void __clear_buddies_next(struct
 {
 	for_each_sched_entity(se) {
 		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-		if (cfs_rq->next == se)
-			cfs_rq->next = NULL;
-		else
+		if (cfs_rq->next != se)
 			break;
+
+		cfs_rq->next = NULL;
 	}
 }
 
@@ -2589,10 +2589,10 @@ static void __clear_buddies_skip(struct
 {
 	for_each_sched_entity(se) {
 		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-		if (cfs_rq->skip == se)
-			cfs_rq->skip = NULL;
-		else
+		if (cfs_rq->skip != se)
 			break;
+
+		cfs_rq->skip = NULL;
 	}
 }
 
author maintainer
#9 lore raw

PATCH 7/9 sched/fair: Optimize cgroup pick_next_task_fair

In reply to Peter Zijlstra

Since commit 2f36825b1 ("sched: Next buddy hint on sleep and preempt path") it is likely we pick a new task from the same cgroup, doing a put and then set on all intermediate entities is a waste of time, so try to avoid this.

Measured using:

mount nodev /cgroup -t cgroup -o cpu
cd /cgroup
mkdir a; cd a
mkdir b; cd b
mkdir c; cd c
echo $$ > tasks
perf stat --repeat 10 -- taskset 1 perf bench sched pipe

PRE :      4.542422684 seconds time elapsed   ( +-  0.33% )
POST:      4.389409991 seconds time elapsed   ( +-  0.32% )

Which shows a significant improvement of ~3.5%

---
 kernel/sched/fair.c |  122 ++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 110 insertions(+), 12 deletions(-)
kernel/sched/fair.c +110 -12
@@ -2911,17 +2911,36 @@ wakeup_preempt_entity(struct sched_entit
  * 3) pick the "last" process, for cache locality
  * 4) do not run the "skip" process, if something else is available
  */
-static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
+static struct sched_entity *
+pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
 {
-	struct sched_entity *se = __pick_first_entity(cfs_rq);
-	struct sched_entity *left = se;
+	struct sched_entity *left = __pick_first_entity(cfs_rq);
+	struct sched_entity *se;
+
+	/*
+	 * If curr is set we have to see if its left of the leftmost entity
+	 * still in the tree, provided there was anything in the tree at all.
+	 */
+	if (!left || (curr && entity_before(curr, left)))
+		left = curr;
+
+	se = left; /* ideally we run the leftmost entity */
 
 	/*
 	 * Avoid running the skip buddy, if running something else can
 	 * be done without getting too unfair.
 	 */
 	if (cfs_rq->skip == se) {
-		struct sched_entity *second = __pick_next_entity(se);
+		struct sched_entity *second;
+
+		if (se == curr) {
+			second = __pick_first_entity(cfs_rq);
+		} else {
+			second = __pick_next_entity(se);
+			if (!second || (curr && entity_before(curr, second)))
+				second = curr;
+		}
+
 		if (second && wakeup_preempt_entity(second, left) < 1)
 			se = second;
 	}
@@ -2943,7 +2962,7 @@ static struct sched_entity *pick_next_en
 	return se;
 }
 
-static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
+static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
 
 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
 {
@@ -3598,22 +3617,23 @@ static void check_enqueue_throttle(struc
 }
 
 /* conditionally throttle active cfs_rq's from put_prev_entity() */
-static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
+static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
 {
 	if (!cfs_bandwidth_used())
-		return;
+		return false;
 
 	if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0))
-		return;
+		return false;
 
 	/*
 	 * it's possible for a throttled entity to be forced into a running
 	 * state (e.g. set_curr_task), in this case we're finished.
 	 */
 	if (cfs_rq_throttled(cfs_rq))
-		return;
+		return true;
 
 	throttle_cfs_rq(cfs_rq);
+	return true;
 }
 
 static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer)
@@ -3723,7 +3743,7 @@ static inline u64 cfs_rq_clock_task(stru
 }
 
 static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) {}
-static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
+static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq) { return false; }
 static void check_enqueue_throttle(struct cfs_rq *cfs_rq) {}
 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
 
@@ -4662,9 +4682,86 @@ static void check_preempt_wakeup(struct
 static struct task_struct *
 pick_next_task_fair(struct rq *rq, struct task_struct *prev)
 {
-	struct task_struct *p;
 	struct cfs_rq *cfs_rq = &rq->cfs;
 	struct sched_entity *se;
+	struct task_struct *p;
+
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	if (!cfs_rq->nr_running)
+		return NULL;
+
+	if (prev->sched_class != &fair_sched_class)
+		goto simple;
+
+	/*
+	 * Because of the set_next_buddy() in dequeue_task_fair() it is rather
+	 * likely that a next task is from the same cgroup as the current.
+	 *
+	 * Therefore attempt to avoid putting and setting the entire cgroup
+	 * hierarchy, only change the part that actually changes.
+	 */
+
+	do {
+		struct sched_entity *curr = cfs_rq->curr;
+
+		/*
+		 * Since we got here without doing put_prev_entity() we also
+		 * have to consider cfs_rq->curr. If it is still a runnable
+		 * 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;
+
+		/*
+		 * 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);
+	} while (cfs_rq);
+
+	p = task_of(se);
+
+	/*
+	 * Since we haven't yet done put_prev_entity and if the selected task
+	 * is a different task than we started out with, try and touch the
+	 * least amount of cfs_rqs.
+	 */
+	if (prev != p) {
+		struct sched_entity *pse = &prev->se;
+
+		while (!(cfs_rq = is_same_group(se, pse))) {
+			int se_depth = se->depth;
+			int pse_depth = pse->depth;
+
+			if (se_depth <= pse_depth) {
+				put_prev_entity(cfs_rq_of(pse), pse);
+				pse = parent_entity(pse);
+			}
+			if (se_depth >= pse_depth) {
+				set_next_entity(cfs_rq_of(se), se);
+				se = parent_entity(se);
+			}
+		}
+
+		put_prev_entity(cfs_rq, pse);
+		set_next_entity(cfs_rq, se);
+	}
+
+	if (hrtick_enabled(rq))
+		hrtick_start_fair(rq, p);
+
+	return p;
+simple:
+	cfs_rq = &rq->cfs;
+#endif
 
 	if (!cfs_rq->nr_running)
 		return NULL;
@@ -4672,12 +4769,13 @@ pick_next_task_fair(struct rq *rq, struc
 	prev->sched_class->put_prev_task(rq, prev);
 
 	do {
-		se = pick_next_entity(cfs_rq);
+		se = pick_next_entity(cfs_rq, NULL);
 		set_next_entity(cfs_rq, se);
 		cfs_rq = group_cfs_rq(se);
 	} while (cfs_rq);
 
 	p = task_of(se);
+
 	if (hrtick_enabled(rq))
 		hrtick_start_fair(rq, p);
 
maintainer
#10 lore raw

Re: [PATCH 7/9] sched/fair: Optimize cgroup pick_next_task_fair

On 28 January 2014 18:16, Peter Zijlstra <[email protected]> wrote:

[snip]

kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4691

Quoted 13 lines
kernel/sched/fair.c +5 -1
@@ -4662,9 +4682,86 @@ static void check_preempt_wakeup(struct
 static struct task_struct *
 pick_next_task_fair(struct rq *rq, struct task_struct *prev)
 {
-       struct task_struct *p;
        struct cfs_rq *cfs_rq = &rq->cfs;
        struct sched_entity *se;
+       struct task_struct *p;
+
+#ifdef CONFIG_FAIR_GROUP_SCHED
+       if (!cfs_rq->nr_running)
+               return NULL;

Couldn't you move the test above out of the CONFIG_FAIR_GROUP_SCHED and remove the same test that is done after the simple label

Vincent

Quoted 93 lines
kernel/sched/fair.c +75 -1
+
+       if (prev->sched_class != &fair_sched_class)
+               goto simple;
+
+       /*
+        * Because of the set_next_buddy() in dequeue_task_fair() it is rather
+        * likely that a next task is from the same cgroup as the current.
+        *
+        * Therefore attempt to avoid putting and setting the entire cgroup
+        * hierarchy, only change the part that actually changes.
+        */
+
+       do {
+               struct sched_entity *curr = cfs_rq->curr;
+
+               /*
+                * Since we got here without doing put_prev_entity() we also
+                * have to consider cfs_rq->curr. If it is still a runnable
+                * 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;
+
+               /*
+                * 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);
+       } while (cfs_rq);
+
+       p = task_of(se);
+
+       /*
+        * Since we haven't yet done put_prev_entity and if the selected task
+        * is a different task than we started out with, try and touch the
+        * least amount of cfs_rqs.
+        */
+       if (prev != p) {
+               struct sched_entity *pse = &prev->se;
+
+               while (!(cfs_rq = is_same_group(se, pse))) {
+                       int se_depth = se->depth;
+                       int pse_depth = pse->depth;
+
+                       if (se_depth <= pse_depth) {
+                               put_prev_entity(cfs_rq_of(pse), pse);
+                               pse = parent_entity(pse);
+                       }
+                       if (se_depth >= pse_depth) {
+                               set_next_entity(cfs_rq_of(se), se);
+                               se = parent_entity(se);
+                       }
+               }
+
+               put_prev_entity(cfs_rq, pse);
+               set_next_entity(cfs_rq, se);
+       }
+
+       if (hrtick_enabled(rq))
+               hrtick_start_fair(rq, p);
+
+       return p;
+simple:
+       cfs_rq = &rq->cfs;
+#endif
 
        if (!cfs_rq->nr_running)
                return NULL;
@@ -4672,12 +4769,13 @@ pick_next_task_fair(struct rq *rq, struc
        prev->sched_class->put_prev_task(rq, prev);
 
        do {
-               se = pick_next_entity(cfs_rq);
+               se = pick_next_entity(cfs_rq, NULL);
                set_next_entity(cfs_rq, se);
                cfs_rq = group_cfs_rq(se);
        } while (cfs_rq);
 
        p = task_of(se);
+
        if (hrtick_enabled(rq))
                hrtick_start_fair(rq, p);
 
author maintainer
#11 lore raw

Re: [PATCH 7/9] sched/fair: Optimize cgroup pick_next_task_fair

Quoted 5 lines · Vincent Guittot

On 28 January 2014 18:16, Peter Zijlstra <[email protected]> wrote:

[snip]

Quoted 1 line
Quoted 15 lines

kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4691

Quoted 12 lines
kernel/sched/fair.c +5 -1
@@ -4662,9 +4682,86 @@ static void check_preempt_wakeup(struct
 static struct task_struct *
 pick_next_task_fair(struct rq *rq, struct task_struct *prev)
 {
-       struct task_struct *p;
        struct cfs_rq *cfs_rq = &rq->cfs;
        struct sched_entity *se;
+       struct task_struct *p;
+
+#ifdef CONFIG_FAIR_GROUP_SCHED
+       if (!cfs_rq->nr_running)
+               return NULL;

Couldn't you move the test above out of the CONFIG_FAIR_GROUP_SCHED and remove the same test that is done after the simple label

No, we have to check it twice because..

Quoted 26 lines
Quoted 26 lines
kernel/sched/fair.c +25 -0
+
+       if (prev->sched_class != &fair_sched_class)
+               goto simple;
+
+       /*
+        * Because of the set_next_buddy() in dequeue_task_fair() it is rather
+        * likely that a next task is from the same cgroup as the current.
+        *
+        * Therefore attempt to avoid putting and setting the entire cgroup
+        * hierarchy, only change the part that actually changes.
+        */
+
+       do {
+               struct sched_entity *curr = cfs_rq->curr;
+
+               /*
+                * Since we got here without doing put_prev_entity() we also
+                * have to consider cfs_rq->curr. If it is still a runnable
+                * 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;
Quoted 8 lines

kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4724

Quoted 8 lines
kernel/sched/fair.c +8 -0
+
+               /*
+                * 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;

... here if you read the comment above, we could have modified the nr_running.

Quoted 40 lines
Quoted 40 lines
kernel/sched/fair.c +39 -0
+               se = pick_next_entity(cfs_rq, curr);
+               cfs_rq = group_cfs_rq(se);
+       } while (cfs_rq);
+
+       p = task_of(se);
+
+       /*
+        * Since we haven't yet done put_prev_entity and if the selected task
+        * is a different task than we started out with, try and touch the
+        * least amount of cfs_rqs.
+        */
+       if (prev != p) {
+               struct sched_entity *pse = &prev->se;
+
+               while (!(cfs_rq = is_same_group(se, pse))) {
+                       int se_depth = se->depth;
+                       int pse_depth = pse->depth;
+
+                       if (se_depth <= pse_depth) {
+                               put_prev_entity(cfs_rq_of(pse), pse);
+                               pse = parent_entity(pse);
+                       }
+                       if (se_depth >= pse_depth) {
+                               set_next_entity(cfs_rq_of(se), se);
+                               se = parent_entity(se);
+                       }
+               }
+
+               put_prev_entity(cfs_rq, pse);
+               set_next_entity(cfs_rq, se);
+       }
+
+       if (hrtick_enabled(rq))
+               hrtick_start_fair(rq, p);
+
+       return p;
+simple:
+       cfs_rq = &rq->cfs;
+#endif
 
Quoted 2 lines

kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4767

Quoted 2 lines
kernel/sched/fair.c +0 -0
        if (!cfs_rq->nr_running)
                return NULL;

And therefore this test needs to stay.

maintainer
#12 lore raw

Re: [PATCH 7/9] sched/fair: Optimize cgroup pick_next_task_fair

Quoted 52 lines · Peter Zijlstra
Quoted 5 lines · Vincent Guittot

On 28 January 2014 18:16, Peter Zijlstra <[email protected]> wrote:

[snip]

Quoted 1 line
Quoted 15 lines

kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4691

Quoted 12 lines
kernel/sched/fair.c +5 -1
@@ -4662,9 +4682,86 @@ static void check_preempt_wakeup(struct
 static struct task_struct *
 pick_next_task_fair(struct rq *rq, struct task_struct *prev)
 {
-       struct task_struct *p;
        struct cfs_rq *cfs_rq = &rq->cfs;
        struct sched_entity *se;
+       struct task_struct *p;
+
+#ifdef CONFIG_FAIR_GROUP_SCHED
+       if (!cfs_rq->nr_running)
+               return NULL;

Couldn't you move the test above out of the CONFIG_FAIR_GROUP_SCHED and remove the same test that is done after the simple label

No, we have to check it twice because..

Quoted 29 lines
Quoted 29 lines
kernel/sched/fair.c +28 -0
+
+       if (prev->sched_class != &fair_sched_class)
+               goto simple;
+
+       /*
+        * Because of the set_next_buddy() in dequeue_task_fair() it is rather
+        * likely that a next task is from the same cgroup as the current.
+        *
+        * Therefore attempt to avoid putting and setting the entire cgroup
+        * hierarchy, only change the part that actually changes.
+        */
+
+       do {
+               struct sched_entity *curr = cfs_rq->curr;
+
+               /*
+                * Since we got here without doing put_prev_entity() we also
+                * have to consider cfs_rq->curr. If it is still a runnable
+                * 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;
+
+               /*
+                * This call to check_cfs_rq_runtime() will do the throttle and
Quoted 8 lines
Quoted 5 lines

kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4724

Quoted 5 lines
kernel/sched/fair.c +5 -0
+                * 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;

... here if you read the comment above, we could have modified the nr_running.

ok, i missed this point

Quoted 45 lines
Quoted 41 lines
Quoted 41 lines
kernel/sched/fair.c +39 -0
+               se = pick_next_entity(cfs_rq, curr);
+               cfs_rq = group_cfs_rq(se);
+       } while (cfs_rq);
+
+       p = task_of(se);
+
+       /*
+        * Since we haven't yet done put_prev_entity and if the selected task
+        * is a different task than we started out with, try and touch the
+        * least amount of cfs_rqs.
+        */
+       if (prev != p) {
+               struct sched_entity *pse = &prev->se;
+
+               while (!(cfs_rq = is_same_group(se, pse))) {
+                       int se_depth = se->depth;
+                       int pse_depth = pse->depth;
+
+                       if (se_depth <= pse_depth) {
+                               put_prev_entity(cfs_rq_of(pse), pse);
+                               pse = parent_entity(pse);
+                       }
+                       if (se_depth >= pse_depth) {
+                               set_next_entity(cfs_rq_of(se), se);
+                               se = parent_entity(se);
+                       }
+               }
+
+               put_prev_entity(cfs_rq, pse);
+               set_next_entity(cfs_rq, se);
+       }
+
+       if (hrtick_enabled(rq))
+               hrtick_start_fair(rq, p);
+
+       return p;
+simple:
+       cfs_rq = &rq->cfs;
+#endif
 
Quoted 2 lines

kernel/sched/fair.c static void check_preempt_wakeup(struct · line 4767

Quoted 2 lines
kernel/sched/fair.c +0 -0
        if (!cfs_rq->nr_running)
                return NULL;

And therefore this test needs to stay.

author maintainer
#13 lore raw

PATCH 8/9 sched: Clean up idle task SMP logic

In reply to Peter Zijlstra

The idle post_schedule hook is just a vile waste of time, furthermore it appears unneeded, move the idle_enter_fair() call into pick_next_task_idle().

---
 kernel/sched/idle_task.c |    9 +--------
 1 file changed, 1 insertion(+), 8 deletions(-)
kernel/sched/idle_task.c +1 -8
@@ -19,11 +19,6 @@ static void pre_schedule_idle(struct rq
 	idle_exit_fair(rq);
 	rq_last_tick_reset(rq);
 }
-
-static void post_schedule_idle(struct rq *rq)
-{
-	idle_enter_fair(rq);
-}
 #endif /* CONFIG_SMP */
 /*
  * Idle tasks are unconditionally rescheduled:
@@ -40,8 +35,7 @@ pick_next_task_idle(struct rq *rq, struc
 
 	schedstat_inc(rq, sched_goidle);
 #ifdef CONFIG_SMP
-	/* Trigger the post schedule to do an idle_enter for CFS */
-	rq->post_schedule = 1;
+	idle_enter_fair(rq);
 #endif
 	return rq->idle;
 }
@@ -105,7 +99,6 @@ const struct sched_class idle_sched_clas
 #ifdef CONFIG_SMP
 	.select_task_rq		= select_task_rq_idle,
 	.pre_schedule		= pre_schedule_idle,
-	.post_schedule		= post_schedule_idle,
 #endif
 
 	.set_curr_task          = set_curr_task_idle,
maintainer Acked-by on v1 8/9
#14 lore raw

Re: [PATCH 8/9] sched: Clean up idle task SMP logic

Hi Peter,

Vincent

Quoted 48 lines · Peter Zijlstra

The idle post_schedule hook is just a vile waste of time, furthermore it appears unneeded, move the idle_enter_fair() call into pick_next_task_idle().

---
 kernel/sched/idle_task.c |    9 +--------
 1 file changed, 1 insertion(+), 8 deletions(-)
kernel/sched/idle_task.c +1 -8
@@ -19,11 +19,6 @@ static void pre_schedule_idle(struct rq
        idle_exit_fair(rq);
        rq_last_tick_reset(rq);
 }
-
-static void post_schedule_idle(struct rq *rq)
-{
-       idle_enter_fair(rq);
-}
 #endif /* CONFIG_SMP */
 /*
  * Idle tasks are unconditionally rescheduled:
@@ -40,8 +35,7 @@ pick_next_task_idle(struct rq *rq, struc
 
        schedstat_inc(rq, sched_goidle);
 #ifdef CONFIG_SMP
-       /* Trigger the post schedule to do an idle_enter for CFS */
-       rq->post_schedule = 1;
+       idle_enter_fair(rq);
 #endif
        return rq->idle;
 }
@@ -105,7 +99,6 @@ const struct sched_class idle_sched_clas
 #ifdef CONFIG_SMP
        .select_task_rq         = select_task_rq_idle,
        .pre_schedule           = pre_schedule_idle,
-       .post_schedule          = post_schedule_idle,
 #endif
 
        .set_curr_task          = set_curr_task_idle,
author maintainer
#15 lore raw

PATCH 9/9 sched: Push down pre_schedule() and idle_balance()

In reply to Peter Zijlstra

This patch both merged idle_balance() and pre_schedule() and pushes both of them into pick_next_task().

Conceptually pre_schedule() and idle_balance() are rather similar, both are used to pull more work onto the current CPU.

We cannot however first move idle_balance() into pre_schedule_fair() since there is no guarantee the last runnable task is a fair task, and thus we would miss newidle balances.

Similarly, the dl and rt pre_schedule calls must be ran before idle_balance() since their respective tasks have higher priority and it would not do to delay their execution searching for less important tasks first.

However, by noticing that pick_next_tasks() already traverses the sched_class hierarchy in the right order, we can get the right behaviour and do away with both calls.

We must however change the special case optimization to also require that prev is of sched_class_fair, otherwise we can miss doing a dl or rt pull where we needed one.

---
 kernel/sched/core.c      |   26 ++------------------------
 kernel/sched/deadline.c  |   15 +++++++--------
 kernel/sched/fair.c      |   24 ++++++++++++++++++++----
 kernel/sched/idle_task.c |   12 +++++-------
 kernel/sched/rt.c        |   16 ++++++++--------
 kernel/sched/sched.h     |    1 -
 6 files changed, 42 insertions(+), 52 deletions(-)
kernel/sched/core.c +2 -24
@@ -2146,13 +2146,6 @@ static void finish_task_switch(struct rq
 
 #ifdef CONFIG_SMP
 
-/* assumes rq->lock is held */
-static inline void pre_schedule(struct rq *rq, struct task_struct *prev)
-{
-	if (prev->sched_class->pre_schedule)
-		prev->sched_class->pre_schedule(rq, prev);
-}
-
 /* rq->lock is NOT held, but preemption is disabled */
 static inline void post_schedule(struct rq *rq)
 {
@@ -2170,10 +2163,6 @@ static inline void post_schedule(struct
 
 #else
 
-static inline void pre_schedule(struct rq *rq, struct task_struct *p)
-{
-}
-
 static inline void post_schedule(struct rq *rq)
 {
 }
@@ -2569,7 +2558,8 @@ pick_next_task(struct rq *rq, struct tas
 	 * Optimization: we know that if all tasks are in
 	 * the fair class we can call that function directly:
 	 */
-	if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
+	if (likely(prev->sched_class == &fair_sched_class &&
+		   rq->nr_running == rq->cfs.h_nr_running)) {
 		p = fair_sched_class.pick_next_task(rq, prev);
 		if (likely(p))
 			return p;
@@ -2672,18 +2662,6 @@ static void __sched __schedule(void)
 		switch_count = &prev->nvcsw;
 	}
 
-	pre_schedule(rq, prev);
-
-	if (unlikely(!rq->nr_running)) {
-		/*
-		 * We must set idle_stamp _before_ calling idle_balance(), such
-		 * that we measure the duration of idle_balance() as idle time.
-		 */
-		rq->idle_stamp = rq_clock(rq);
-		if (idle_balance(rq))
-			rq->idle_stamp = 0;
-	}
-
 	if (prev->on_rq || rq->skip_clock_update < 0)
 		update_rq_clock(rq);
 
kernel/sched/deadline.c +7 -8
@@ -989,6 +989,8 @@ static struct sched_dl_entity *pick_next
 	return rb_entry(left, struct sched_dl_entity, rb_node);
 }
 
+static int pull_dl_task(struct rq *this_rq);
+
 struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev)
 {
 	struct sched_dl_entity *dl_se;
@@ -997,6 +999,11 @@ struct task_struct *pick_next_task_dl(st
 
 	dl_rq = &rq->dl;
 
+#ifdef CONFIG_SMP
+	if (dl_task(prev))
+		pull_dl_task(rq);
+#endif
+
 	if (unlikely(!dl_rq->dl_nr_running))
 		return NULL;
 
@@ -1427,13 +1434,6 @@ static int pull_dl_task(struct rq *this_
 	return ret;
 }
 
-static void pre_schedule_dl(struct rq *rq, struct task_struct *prev)
-{
-	/* Try to pull other tasks here */
-	if (dl_task(prev))
-		pull_dl_task(rq);
-}
-
 static void post_schedule_dl(struct rq *rq)
 {
 	push_dl_tasks(rq);
@@ -1626,7 +1626,6 @@ const struct sched_class dl_sched_class
 	.set_cpus_allowed       = set_cpus_allowed_dl,
 	.rq_online              = rq_online_dl,
 	.rq_offline             = rq_offline_dl,
-	.pre_schedule		= pre_schedule_dl,
 	.post_schedule		= post_schedule_dl,
 	.task_woken		= task_woken_dl,
 #endif
kernel/sched/fair.c +20 -4
@@ -2581,7 +2581,8 @@ void idle_exit_fair(struct rq *this_rq)
 	update_rq_runnable_avg(this_rq, 0);
 }
 
-#else
+#else /* CONFIG_SMP */
+
 static inline void update_entity_load_avg(struct sched_entity *se,
 					  int update_cfs_rq) {}
 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
@@ -2593,7 +2594,7 @@ static inline void dequeue_entity_load_a
 					   int sleep) {}
 static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
 					      int force_update) {}
-#endif
+#endif /* CONFIG_SMP */
 
 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
@@ -4686,9 +4687,10 @@ pick_next_task_fair(struct rq *rq, struc
 	struct sched_entity *se;
 	struct task_struct *p;
 
+again:
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	if (!cfs_rq->nr_running)
-		return NULL;
+		goto idle;
 
 	if (prev->sched_class != &fair_sched_class)
 		goto simple;
@@ -4764,7 +4766,7 @@ pick_next_task_fair(struct rq *rq, struc
 #endif
 
 	if (!cfs_rq->nr_running)
-		return NULL;
+		goto idle;
 
 	prev->sched_class->put_prev_task(rq, prev);
 
@@ -4780,6 +4782,20 @@ pick_next_task_fair(struct rq *rq, struc
 		hrtick_start_fair(rq, p);
 
 	return p;
+
+idle:
+	idle_exit_fair(rq);
+	/*
+	 * We must set idle_stamp _before_ calling idle_balance(), such that we
+	 * measure the duration of idle_balance() as idle time.
+	 */
+	rq->idle_stamp = rq_clock(rq);
+	if (idle_balance(rq)) { /* drops rq->lock */
+		rq->idle_stamp = 0;
+		goto again;
+	}
+
+	return NULL;
 }
 
 /*
kernel/sched/idle_task.c +5 -7
@@ -13,13 +13,8 @@ select_task_rq_idle(struct task_struct *
 {
 	return task_cpu(p); /* IDLE tasks as never migrated */
 }
-
-static void pre_schedule_idle(struct rq *rq, struct task_struct *prev)
-{
-	idle_exit_fair(rq);
-	rq_last_tick_reset(rq);
-}
 #endif /* CONFIG_SMP */
+
 /*
  * Idle tasks are unconditionally rescheduled:
  */
@@ -55,6 +50,10 @@ dequeue_task_idle(struct rq *rq, struct
 
 static void put_prev_task_idle(struct rq *rq, struct task_struct *prev)
 {
+#ifdef CONFIG_SMP
+	idle_exit_fair(rq);
+	rq_last_tick_reset(rq);
+#endif
 }
 
 static void task_tick_idle(struct rq *rq, struct task_struct *curr, int queued)
@@ -98,7 +97,6 @@ const struct sched_class idle_sched_clas
 
 #ifdef CONFIG_SMP
 	.select_task_rq		= select_task_rq_idle,
-	.pre_schedule		= pre_schedule_idle,
 #endif
 
 	.set_curr_task          = set_curr_task_idle,
kernel/sched/rt.c +8 -8
@@ -1324,12 +1324,20 @@ static struct task_struct *_pick_next_ta
 	return p;
 }
 
+static int pull_rt_task(struct rq *this_rq);
+
 static struct task_struct *
 pick_next_task_rt(struct rq *rq, struct task_struct *prev)
 {
 	struct task_struct *p;
 	struct rt_rq *rt_rq = &rq->rt;
 
+#ifdef CONFIG_SMP
+	/* Try to pull RT tasks here if we lower this rq's prio */
+	if (rq->rt.highest_prio.curr > prev->prio)
+		pull_rt_task(rq);
+#endif
+
 	if (!rt_rq->rt_nr_running)
 		return NULL;
 
@@ -1720,13 +1728,6 @@ static int pull_rt_task(struct rq *this_
 	return ret;
 }
 
-static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
-{
-	/* Try to pull RT tasks here if we lower this rq's prio */
-	if (rq->rt.highest_prio.curr > prev->prio)
-		pull_rt_task(rq);
-}
-
 static void post_schedule_rt(struct rq *rq)
 {
 	push_rt_tasks(rq);
@@ -2003,7 +2004,6 @@ const struct sched_class rt_sched_class
 	.set_cpus_allowed       = set_cpus_allowed_rt,
 	.rq_online              = rq_online_rt,
 	.rq_offline             = rq_offline_rt,
-	.pre_schedule		= pre_schedule_rt,
 	.post_schedule		= post_schedule_rt,
 	.task_woken		= task_woken_rt,
 	.switched_from		= switched_from_rt,
kernel/sched/sched.h +0 -1
@@ -1136,7 +1136,6 @@ struct sched_class {
 	int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
 	void (*migrate_task_rq)(struct task_struct *p, int next_cpu);
 
-	void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
 	void (*post_schedule) (struct rq *this_rq);
 	void (*task_waking) (struct task_struct *task);
 	void (*task_woken) (struct rq *this_rq, struct task_struct *task);
maintainer
#16 lore raw

Re: [PATCH 9/9] sched: Push down pre_schedule() and idle_balance()

Quoted 177 lines · Peter Zijlstra

This patch both merged idle_balance() and pre_schedule() and pushes both of them into pick_next_task().

Conceptually pre_schedule() and idle_balance() are rather similar, both are used to pull more work onto the current CPU.

We cannot however first move idle_balance() into pre_schedule_fair() since there is no guarantee the last runnable task is a fair task, and thus we would miss newidle balances.

Similarly, the dl and rt pre_schedule calls must be ran before idle_balance() since their respective tasks have higher priority and it would not do to delay their execution searching for less important tasks first.

However, by noticing that pick_next_tasks() already traverses the sched_class hierarchy in the right order, we can get the right behaviour and do away with both calls.

We must however change the special case optimization to also require that prev is of sched_class_fair, otherwise we can miss doing a dl or rt pull where we needed one.

---
 kernel/sched/core.c      |   26 ++------------------------
 kernel/sched/deadline.c  |   15 +++++++--------
 kernel/sched/fair.c      |   24 ++++++++++++++++++++----
 kernel/sched/idle_task.c |   12 +++++-------
 kernel/sched/rt.c        |   16 ++++++++--------
 kernel/sched/sched.h     |    1 -
 6 files changed, 42 insertions(+), 52 deletions(-)
kernel/sched/core.c +2 -24
@@ -2146,13 +2146,6 @@ static void finish_task_switch(struct rq
 
 #ifdef CONFIG_SMP
 
-/* assumes rq->lock is held */
-static inline void pre_schedule(struct rq *rq, struct task_struct *prev)
-{
-       if (prev->sched_class->pre_schedule)
-               prev->sched_class->pre_schedule(rq, prev);
-}
-
 /* rq->lock is NOT held, but preemption is disabled */
 static inline void post_schedule(struct rq *rq)
 {
@@ -2170,10 +2163,6 @@ static inline void post_schedule(struct
 
 #else
 
-static inline void pre_schedule(struct rq *rq, struct task_struct *p)
-{
-}
-
 static inline void post_schedule(struct rq *rq)
 {
 }
@@ -2569,7 +2558,8 @@ pick_next_task(struct rq *rq, struct tas
         * Optimization: we know that if all tasks are in
         * the fair class we can call that function directly:
         */
-       if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
+       if (likely(prev->sched_class == &fair_sched_class &&
+                  rq->nr_running == rq->cfs.h_nr_running)) {
                p = fair_sched_class.pick_next_task(rq, prev);
                if (likely(p))
                        return p;
@@ -2672,18 +2662,6 @@ static void __sched __schedule(void)
                switch_count = &prev->nvcsw;
        }
 
-       pre_schedule(rq, prev);
-
-       if (unlikely(!rq->nr_running)) {
-               /*
-                * We must set idle_stamp _before_ calling idle_balance(), such
-                * that we measure the duration of idle_balance() as idle time.
-                */
-               rq->idle_stamp = rq_clock(rq);
-               if (idle_balance(rq))
-                       rq->idle_stamp = 0;
-       }
-
        if (prev->on_rq || rq->skip_clock_update < 0)
                update_rq_clock(rq);
 
kernel/sched/deadline.c +7 -8
@@ -989,6 +989,8 @@ static struct sched_dl_entity *pick_next
        return rb_entry(left, struct sched_dl_entity, rb_node);
 }
 
+static int pull_dl_task(struct rq *this_rq);
+
 struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev)
 {
        struct sched_dl_entity *dl_se;
@@ -997,6 +999,11 @@ struct task_struct *pick_next_task_dl(st
 
        dl_rq = &rq->dl;
 
+#ifdef CONFIG_SMP
+       if (dl_task(prev))
+               pull_dl_task(rq);
+#endif
+
        if (unlikely(!dl_rq->dl_nr_running))
                return NULL;
 
@@ -1427,13 +1434,6 @@ static int pull_dl_task(struct rq *this_
        return ret;
 }
 
-static void pre_schedule_dl(struct rq *rq, struct task_struct *prev)
-{
-       /* Try to pull other tasks here */
-       if (dl_task(prev))
-               pull_dl_task(rq);
-}
-
 static void post_schedule_dl(struct rq *rq)
 {
        push_dl_tasks(rq);
@@ -1626,7 +1626,6 @@ const struct sched_class dl_sched_class
        .set_cpus_allowed       = set_cpus_allowed_dl,
        .rq_online              = rq_online_dl,
        .rq_offline             = rq_offline_dl,
-       .pre_schedule           = pre_schedule_dl,
        .post_schedule          = post_schedule_dl,
        .task_woken             = task_woken_dl,
 #endif
kernel/sched/fair.c +6 -4
@@ -2581,7 +2581,8 @@ void idle_exit_fair(struct rq *this_rq)
        update_rq_runnable_avg(this_rq, 0);
 }
 
-#else
+#else /* CONFIG_SMP */
+
 static inline void update_entity_load_avg(struct sched_entity *se,
                                          int update_cfs_rq) {}
 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
@@ -2593,7 +2594,7 @@ static inline void dequeue_entity_load_a
                                           int sleep) {}
 static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
                                              int force_update) {}
-#endif
+#endif /* CONFIG_SMP */
 
 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
@@ -4686,9 +4687,10 @@ pick_next_task_fair(struct rq *rq, struc
        struct sched_entity *se;
        struct task_struct *p;
 
+again:
 #ifdef CONFIG_FAIR_GROUP_SCHED
        if (!cfs_rq->nr_running)
-               return NULL;
+               goto idle;
 
        if (prev->sched_class != &fair_sched_class)
                goto simple;
@@ -4764,7 +4766,7 @@ pick_next_task_fair(struct rq *rq, struc
 #endif
 
        if (!cfs_rq->nr_running)
-               return NULL;
+               goto idle;
 
        prev->sched_class->put_prev_task(rq, prev);
 

kernel/sched/fair.c pick_next_task_fair(struct rq *rq, struc · line 4787

Quoted 6 lines
kernel/sched/fair.c +3 -0
@@ -4780,6 +4782,20 @@ pick_next_task_fair(struct rq *rq, struc
                hrtick_start_fair(rq, p);
 
        return p;
+
+idle:
+       idle_exit_fair(rq);

It should be idle_enter_fair.

we want to update the statistic with the running time of other classes than CFS.

The use case is:

exit idle
put_prev_task_idle
--> idle_exit_fair (account elapsed idle time) pick_next_task other than fair tasks
switch between "other than fair" tasks
...
no more "other than fair" tasks to schedule pick_next_task_fair
--> no fair task on the rq
--> jump to simple
--> idle_enter_fair (account elapsed running time of other class before trying to pull fair task from other CPUs)
--> idle_balance()
...

Vincent

Quoted 107 lines
kernel/sched/fair.c +11 -0
+       /*
+        * We must set idle_stamp _before_ calling idle_balance(), such that we
+        * measure the duration of idle_balance() as idle time.
+        */
+       rq->idle_stamp = rq_clock(rq);
+       if (idle_balance(rq)) { /* drops rq->lock */
+               rq->idle_stamp = 0;
+               goto again;
+       }
+
+       return NULL;
 }
 
 /*
kernel/sched/idle_task.c +5 -7
@@ -13,13 +13,8 @@ select_task_rq_idle(struct task_struct *
 {
        return task_cpu(p); /* IDLE tasks as never migrated */
 }
-
-static void pre_schedule_idle(struct rq *rq, struct task_struct *prev)
-{
-       idle_exit_fair(rq);
-       rq_last_tick_reset(rq);
-}
 #endif /* CONFIG_SMP */
+
 /*
  * Idle tasks are unconditionally rescheduled:
  */
@@ -55,6 +50,10 @@ dequeue_task_idle(struct rq *rq, struct
 
 static void put_prev_task_idle(struct rq *rq, struct task_struct *prev)
 {
+#ifdef CONFIG_SMP
+       idle_exit_fair(rq);
+       rq_last_tick_reset(rq);
+#endif
 }
 
 static void task_tick_idle(struct rq *rq, struct task_struct *curr, int queued)
@@ -98,7 +97,6 @@ const struct sched_class idle_sched_clas
 
 #ifdef CONFIG_SMP
        .select_task_rq         = select_task_rq_idle,
-       .pre_schedule           = pre_schedule_idle,
 #endif
 
        .set_curr_task          = set_curr_task_idle,
kernel/sched/rt.c +8 -8
@@ -1324,12 +1324,20 @@ static struct task_struct *_pick_next_ta
        return p;
 }
 
+static int pull_rt_task(struct rq *this_rq);
+
 static struct task_struct *
 pick_next_task_rt(struct rq *rq, struct task_struct *prev)
 {
        struct task_struct *p;
        struct rt_rq *rt_rq = &rq->rt;
 
+#ifdef CONFIG_SMP
+       /* Try to pull RT tasks here if we lower this rq's prio */
+       if (rq->rt.highest_prio.curr > prev->prio)
+               pull_rt_task(rq);
+#endif
+
        if (!rt_rq->rt_nr_running)
                return NULL;
 
@@ -1720,13 +1728,6 @@ static int pull_rt_task(struct rq *this_
        return ret;
 }
 
-static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
-{
-       /* Try to pull RT tasks here if we lower this rq's prio */
-       if (rq->rt.highest_prio.curr > prev->prio)
-               pull_rt_task(rq);
-}
-
 static void post_schedule_rt(struct rq *rq)
 {
        push_rt_tasks(rq);
@@ -2003,7 +2004,6 @@ const struct sched_class rt_sched_class
        .set_cpus_allowed       = set_cpus_allowed_rt,
        .rq_online              = rq_online_rt,
        .rq_offline             = rq_offline_rt,
-       .pre_schedule           = pre_schedule_rt,
        .post_schedule          = post_schedule_rt,
        .task_woken             = task_woken_rt,
        .switched_from          = switched_from_rt,
kernel/sched/sched.h +0 -1
@@ -1136,7 +1136,6 @@ struct sched_class {
        int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
        void (*migrate_task_rq)(struct task_struct *p, int next_cpu);
 
-       void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
        void (*post_schedule) (struct rq *this_rq);
        void (*task_waking) (struct task_struct *task);
        void (*task_woken) (struct rq *this_rq, struct task_struct *task);
author maintainer
#17 lore raw

Re: [PATCH 9/9] sched: Push down pre_schedule() and idle_balance()

Quoted 11 lines · Vincent Guittot

kernel/sched/fair.c pick_next_task_fair(struct rq *rq, struc · line 4787

Quoted 2 lines · Peter Zijlstra
kernel/sched/fair.c +2 -0
+idle:
+       idle_exit_fair(rq);

It should be idle_enter_fair.

we want to update the statistic with the running time of other classes than CFS.

The use case is:

Quoted 14 lines

exit idle
put_prev_task_idle
--> idle_exit_fair (account elapsed idle time) pick_next_task other than fair tasks
switch between "other than fair" tasks
...
no more "other than fair" tasks to schedule pick_next_task_fair
--> no fair task on the rq
--> jump to simple
--> idle_enter_fair (account elapsed running time of other class before trying to pull fair task from other CPUs)
--> idle_balance()
...

Right.. terminal confusion on this topic it seems. Fixed it up.

#18 lore raw
In reply to Peter Zijlstra
Quoted 9 lines · On Tue, 28 Jan 2014 18:16:34 +0100 Peter Zijlstra <[email protected]> wrote:

Here's a set that seems to work properly and hopefully adresses all previously raised issues.

Daniel, I'm sorry, the idle_stamp thing wandered back over to fair.c :-)

I did test the fair bits, including bandwidth (although not very extensively).

I did not test the dl/rt bits, Steve do you have a testcase for that?

My sched tests are usually done by running some scheduling tests while recording sched switches and then analyzing it under kernelshark. I don't have many other tests that do pass fail. Hmm, I did have a couple of rt migration tests, but that's it.

I'll take a look at theses tomorrow.

-- Steve