From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754794Ab2BPXUp (ORCPT ); Thu, 16 Feb 2012 18:20:45 -0500 Received: from casper.infradead.org ([85.118.1.10]:39050 "EHLO casper.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752810Ab2BPXUo convert rfc822-to-8bit (ORCPT ); Thu, 16 Feb 2012 18:20:44 -0500 Message-ID: <1329434437.2293.259.camel@twins> Subject: Re: [RFC][PATCH] sched: Optimize cgroup pick_next_task_fair From: Peter Zijlstra To: Paul Turner Cc: Venkatesh Pallipadi , Ingo Molnar , Mike Galbraith , LKML Date: Fri, 17 Feb 2012 00:20:37 +0100 In-Reply-To: <1328936700.2476.17.camel@laptop> References: <1328936700.2476.17.camel@laptop> Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT X-Mailer: Evolution 3.2.2- Mime-Version: 1.0 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sat, 2012-02-11 at 06:05 +0100, Peter Zijlstra wrote: > 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 Here's one that actually boots.. --- --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1117,7 +1117,8 @@ 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); + 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 @@ -1210,6 +1211,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; --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -3119,7 +3119,7 @@ static void put_prev_task(struct rq *rq, * 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; @@ -3129,13 +3129,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; } @@ -3196,8 +3196,9 @@ static void __sched __schedule(void) if (unlikely(!rq->nr_running)) idle_balance(cpu, rq); - 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); rq->skip_clock_update = 0; @@ -5101,7 +5102,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); --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -294,13 +294,13 @@ static inline void list_del_leaf_cfs_rq( list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list) /* Do the two (enqueued) entities belong to the same group ? */ -static inline int +static inline struct cfs_rq * is_same_group(struct sched_entity *se, struct sched_entity *pse) { if (se->cfs_rq == pse->cfs_rq) - return 1; + return se->cfs_rq; - return 0; + return NULL; } static inline struct sched_entity *parent_entity(struct sched_entity *se) @@ -308,17 +308,6 @@ static inline struct sched_entity *paren return se->parent; } -/* return depth at which a sched entity is present in the hierarchy */ -static inline int depth_se(struct sched_entity *se) -{ - int depth = 0; - - for_each_sched_entity(se) - depth++; - - return depth; -} - static void find_matching_se(struct sched_entity **se, struct sched_entity **pse) { @@ -332,8 +321,8 @@ find_matching_se(struct sched_entity **s */ /* First walk up until both entities are at same depth */ - se_depth = depth_se(*se); - pse_depth = depth_se(*pse); + se_depth = (*se)->depth; + pse_depth = (*pse)->depth; while (se_depth > pse_depth) { se_depth--; @@ -398,10 +387,10 @@ static inline void list_del_leaf_cfs_rq( #define for_each_leaf_cfs_rq(rq, cfs_rq) \ for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL) -static inline int +static inline struct cfs_rq * is_same_group(struct sched_entity *se, struct sched_entity *pse) { - return 1; + return cfs_rq_of(se); /* always the same rq */ } static inline struct sched_entity *parent_entity(struct sched_entity *se) @@ -1136,10 +1125,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; } } @@ -1147,10 +1136,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; } } @@ -1158,10 +1147,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; } } @@ -2993,22 +2982,52 @@ 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; - struct sched_entity *se; + struct sched_entity *se, *pse; if (!cfs_rq->nr_running) return NULL; + if (prev && (prev->sched_class != &fair_sched_class || + cfs_rq->nr_running == 1)) { + prev->sched_class->put_prev_task(rq, prev); + prev = NULL; + } + do { se = pick_next_entity(cfs_rq); - set_next_entity(cfs_rq, se); + if (!prev) + set_next_entity(cfs_rq, se); cfs_rq = group_cfs_rq(se); } while (cfs_rq); p = task_of(se); + + if (prev) { + 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); @@ -5360,6 +5379,8 @@ void init_cfs_rq(struct cfs_rq *cfs_rq) #ifdef CONFIG_FAIR_GROUP_SCHED static void task_move_group_fair(struct task_struct *p, int on_rq) { + struct sched_entity *se = &p->se; + /* * If the task was not on the rq at the time of this cgroup movement * it must have been asleep, sleeping tasks keep their ->vruntime @@ -5385,14 +5406,16 @@ static void task_move_group_fair(struct * To prevent boost or penalty in the new cfs_rq caused by delta * min_vruntime between the two cfs_rqs, we skip vruntime adjustment. */ - if (!on_rq && (!p->se.sum_exec_runtime || p->state == TASK_WAKING)) + if (!on_rq && (!se->sum_exec_runtime || p->state == TASK_WAKING)) on_rq = 1; if (!on_rq) - p->se.vruntime -= cfs_rq_of(&p->se)->min_vruntime; + se->vruntime -= cfs_rq_of(se)->min_vruntime; set_task_rq(p, task_cpu(p)); + if (se->parent) + se->depth = se->parent->depth + 1; if (!on_rq) - p->se.vruntime += cfs_rq_of(&p->se)->min_vruntime; + se->vruntime += cfs_rq_of(se)->min_vruntime; } void free_fair_sched_group(struct task_group *tg) @@ -5490,10 +5513,13 @@ void init_tg_cfs_entry(struct task_group if (!se) return; - if (!parent) + if (!parent) { se->cfs_rq = &rq->cfs; - else + se->depth = 0; + } else { se->cfs_rq = parent->my_q; + se->depth = parent->depth + 1; + } se->my_q = cfs_rq; update_load_set(&se->load, 0); --- a/kernel/sched/idle_task.c +++ b/kernel/sched/idle_task.c @@ -22,8 +22,12 @@ 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) { + if (prev) + prev->sched_class->put_prev_task(rq, prev); + schedstat_inc(rq, sched_goidle); calc_load_account_idle(rq); return rq->idle; --- a/kernel/sched/rt.c +++ b/kernel/sched/rt.c @@ -1321,15 +1321,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); @@ -1343,9 +1335,22 @@ 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; + + 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) --- a/kernel/sched/stop_task.c +++ b/kernel/sched/stop_task.c @@ -23,12 +23,17 @@ 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) + if (stop && stop->on_rq) { + if (prev) + prev->sched_class->put_prev_task(rq, prev); + return stop; + } return NULL; }