sched: Optimize cgroup pick_next_task_fair

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.

XXX check put_prev_task()'s update_rq_clock() magic..

Compile tested only.. inspired by pjt's fast switch stories.

Not-quite-signed-off-by Peter Zijlstra <[email protected]>

Quoted 4 lines · 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.

Good idea, we need to lose some weight.

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.

XXX check put_prev_task()'s update_rq_clock() magic..

Compile tested only.. inspired by pjt's fast switch stories.

Not-quite-signed-off-by Peter Zijlstra <[email protected]>

Commit-ID:  606dba2e289446600a0b68422ed2019af5355c12
Gitweb:     http://git.kernel.org/tip/606dba2e289446600a0b68422ed2019af5355c12
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Sat, 11 Feb 2012 06:05:00 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Mon, 10 Feb 2014 16:17:13 +0100

sched: Push put_prev_task() into pick_next_task()

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.

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

Link http://lkml.kernel.org/r/1328936700.2476.17.camel@laptop open here

Signed-off-by Ingo Molnar <[email protected]>

---
 kernel/sched/core.c      | 21 ++++++++------------- kernel/sched/deadline.c  |  5 ++++- kernel/sched/fair.c      |  6 +++++- kernel/sched/idle_task.c |  6 +++++- kernel/sched/rt.c        | 27 ++++++++++++++++----------- kernel/sched/sched.h     |  8 +++++++- kernel/sched/stop_task.c | 16 ++++++++++------

 7 files changed, 55 insertions(+), 34 deletions(-)

kernel/sched/core.c +0 -7

index 417cf65..dedb5f0 100644
@@ -2579,18 +2579,11 @@ static inline void schedule_debug(struct task_struct *prev)
          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 *

kernel/sched/core.c +1 -1

-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;

kernel/sched/core.c +6 -4

@@ -2600,13 +2593,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;
          }

@@ -2714,8 +2707,10 @@ need_resched:
                          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 +0 -0

                  BUG_ON(!next);
                  next->sched_class->put_prev_task(rq, next);
 

kernel/sched/deadline.c +4 -1

index b5700bc..50797d5 100644
@@ -990,7 +990,7 @@ static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
          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;

@@ -1001,6 +1001,9 @@ struct task_struct *pick_next_task_dl(struct rq *rq)
          if (unlikely(!dl_rq->dl_nr_running))
                  return NULL;
 
+ if (prev)
+ 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 +5 -1

index 748a7ac..c4bb0ac 100644
@@ -4655,7 +4655,8 @@ preempt:
                  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;

@@ -4664,6 +4665,9 @@ static struct task_struct *pick_next_task_fair(struct rq *rq)
          if (!cfs_rq->nr_running)
                  return NULL;
 
+ if (prev)
+ 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 +5 -1

index 516c3d9..e5c922a 100644
@@ -33,8 +33,12 @@ static void check_preempt_curr_idle(struct rq *rq, struct task_struct *p, int fl
          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)
  {
+ if (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 +16 -11

index a2740b7..a15ca1c 100644
@@ -1310,15 +1310,7 @@ static struct task_struct *_pick_next_task_rt(struct rq *rq)
  {
          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,22 @@ static struct task_struct *_pick_next_task_rt(struct rq *rq)
          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;
+
+ if (prev)
+ 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

index bb89991..c534cf4 100644
@@ -1105,7 +1105,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 +10 -6

index fdb6bb0..a4147c9 100644
@@ -23,16 +23,20 @@ check_preempt_curr_stop(struct rq *rq, struct task_struct *p, int flags)
          /* 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;
+ if (prev)
+ prev->sched_class->put_prev_task(rq, prev);
+
+ stop->se.exec_start = rq_clock_task(rq);
+
+ return stop;
  }
 

 static void
--
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/

kernel/sched/core.c static void migrate_tasks(unsigned int dead_cpu) · line 4746

Quoted 6 lines

kernel/sched/core.c +1 -1

@@ -4748,7 +4743,7 @@ static void migrate_tasks(unsigned int dead_cpu)
                  if (rq->nr_running == 1)
                          break;
 
- next = pick_next_task(rq);
+ next = pick_next_task(rq, NULL);

pick_next_task() firstly checks for prev->sched_class, doesn't it ???

The same for pick_next_task_rt().

Review static void migrate_tasks(unsigned int dead_cpu) · line 4746

Quoted 6 lines

(quoted diff) +1 -1

@@ -4748,7 +4743,7 @@ static void migrate_tasks(unsigned int dead_cpu)
                  if (rq->nr_running == 1)
                          break;
 
- next = pick_next_task(rq);
+ next = pick_next_task(rq, NULL);

pick_next_task() firstly checks for prev->sched_class, doesn't it ???

The same for pick_next_task_rt().

kernel/sched/rt.c:1347 pick_next_task_rt() warn: variable dereferenced before check 'prev' (see line 1338) kernel/sched/deadline.c:1011 pick_next_task_dl() warn: variable dereferenced before check 'prev' (see line 1005)

Quoted 5 lines

Quoted 5 lines

 @@ -4748,7 +4743,7 @@ static void migrate_tasks(unsigned int dead_cpu) if (rq->nr_running == 1)
                          break;

Quoted 5 lines

Quoted 2 lines

 - next = pick_next_task(rq);
 + next = pick_next_task(rq, NULL);

 pick_next_task() firstly checks for prev->sched_class, doesn't it ???

 The same for pick_next_task_rt().

OK, how about something like this?

---
Subject: sched: Fix hotplug task migration
From: Peter Zijlstra <[email protected]>
Date: Wed, 12 Feb 2014 10:49:30 +0100

Dan Carpenter reported:

Quoted 2 lines

 kernel/sched/rt.c:1347 pick_next_task_rt() warn: variable dereferenced before check 'prev' (see line 1338) kernel/sched/deadline.c:1011 pick_next_task_dl() warn: variable dereferenced before check 'prev' (see line 1005)

Kirill also spotted that migrate_tasks() will have an instant NULL deref because pick_next_task() will immediately deref prev.

Instead of fixing all the corner cases because migrate_tasks() can pass in a NULL prev task in the unlikely case of hot-un-plug, provide a fake task such that we can remove all the NULL checks from the far more common paths.

A further problem; not previously spotted; is that because we pushed pre_schedule() and idle_balance() into pick_next_task() we now need to avoid those getting called and pulling more tasks on our dying CPU.

We avoid pull_{dl,rt}_task() by setting fake_task.prio to MAX_PRIO+1. We also note that since we call pick_next_task() exactly the amount of times we have runnable tasks present, we should never land in idle_balance().

Fixes 38033c37faab ("sched: Push down pre_schedule() and idle_balance()")

Cc Steven Rostedt <[email protected]>

Cc Juri Lelli <[email protected]>

Cc Ingo Molnar <[email protected]>

Reported-by Kirill Tkhai <[email protected]>

Reported-by Dan Carpenter <[email protected]>

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

Link http://lkml.kernel.org/r/[email protected] open here

---
 kernel/sched/core.c      |   18 +++++++++++++++++- kernel/sched/deadline.c  |    3 +-- kernel/sched/fair.c      |    5 ++--- kernel/sched/idle_task.c |    3 +-- kernel/sched/rt.c        |    3 +-- kernel/sched/stop_task.c |    3 +--

 6 files changed, 23 insertions(+), 12 deletions(-)

kernel/sched/core.c +17 -1

@@ -4681,6 +4681,22 @@ static void calc_load_migrate(struct rq
                  atomic_long_add(delta, &calc_load_tasks);
  }
 
+static void put_prev_task_fake(struct rq *rq, struct task_struct *prev)
+{
+}
+
+static const struct sched_class fake_sched_class = {
+ .put_prev_task = put_prev_task_fake,
+};
+
+static struct task_struct fake_task = {
+ /*
+ * Avoid pull_{rt,dl}_task()
+ */
+ .prio = MAX_PRIO + 1,
+ .sched_class = &fake_sched_class,
+};
+
  /*
   * Migrate all tasks from the rq, sleeping tasks will be migrated by
   * try_to_wake_up()->select_task_rq().

@@ -4721,7 +4737,7 @@ static void migrate_tasks(unsigned int d
                  if (rq->nr_running == 1)
                          break;
 
- next = pick_next_task(rq, NULL);
+ next = pick_next_task(rq, &fake_task);
                  BUG_ON(!next);
                  next->sched_class->put_prev_task(rq, next);
 

kernel/sched/deadline.c +1 -2

@@ -1008,8 +1008,7 @@ struct task_struct *pick_next_task_dl(st
          if (unlikely(!dl_rq->dl_nr_running))
                  return NULL;
 
- if (prev)
- prev->sched_class->put_prev_task(rq, prev);
+ 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 +2 -3

@@ -4690,7 +4690,7 @@ pick_next_task_fair(struct rq *rq, struc
          if (!cfs_rq->nr_running)
                  goto idle;
 
- if (!prev || prev->sched_class != &fair_sched_class)
+ if (prev->sched_class != &fair_sched_class)
                  goto simple;
 
          /*

@@ -4766,8 +4766,7 @@ pick_next_task_fair(struct rq *rq, struc
          if (!cfs_rq->nr_running)
                  goto idle;
 
- if (prev)
- prev->sched_class->put_prev_task(rq, prev);
+ prev->sched_class->put_prev_task(rq, prev);
 
          do {
                  se = pick_next_entity(cfs_rq, NULL);

kernel/sched/idle_task.c +0 -0

@@ -26,8 +26,7 @@ static void check_preempt_curr_idle(stru

 static struct task_struct * pick_next_task_idle(struct rq *rq, struct task_struct *prev) {
- if (prev)
- prev->sched_class->put_prev_task(rq, prev);
+ prev->sched_class->put_prev_task(rq, prev);

         schedstat_inc(rq, sched_goidle);
 #ifdef CONFIG_SMP

kernel/sched/rt.c +1 -2

@@ -1344,8 +1344,7 @@ pick_next_task_rt(struct rq *rq, struct
          if (rt_rq_throttled(rt_rq))
                  return NULL;
 
- if (prev)
- prev->sched_class->put_prev_task(rq, prev);
+ prev->sched_class->put_prev_task(rq, prev);
 
          p = _pick_next_task_rt(rq);
 

kernel/sched/stop_task.c +1 -2

@@ -31,8 +31,7 @@ pick_next_task_stop(struct rq *rq, struc
          if (!stop || !stop->on_rq)
                  return NULL;
 
- if (prev)
- prev->sched_class->put_prev_task(rq, prev);
+ prev->sched_class->put_prev_task(rq, prev);
 
          stop->se.exec_start = rq_clock_task(rq);

Maybe pack prev->sched_class->put_prev_task() into inline function?