[patch 1/1] sched: update_curr versus correct cfs_rq in check_preempt_wakeup

[patch 1/1] sched: update_curr versus correct cfs_rq in check_preempt_wakeup

[Paul Turner]

[-- Attachment #1: fix_check_preempt_wakeup.patch --]
[-- Type: text/plain, Size: 838 bytes --]

We update_curr() versus the current entity as the preemption decision is based
on the relative vruntime.  However, update_curr() is not hierarchical and in
the group scheduling case find_matching_se() will have us making the
comparison on a cfs_rq different to the one just updated.

Signed-off-by: Paul Turner <pjt@google.com>
---
 kernel/sched_fair.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Index: tip2/kernel/sched_fair.c
===================================================================
--- tip2.orig/kernel/sched_fair.c
+++ tip2/kernel/sched_fair.c
@@ -1919,8 +1919,8 @@ static void check_preempt_wakeup(struct 
 	if (!sched_feat(WAKEUP_PREEMPT))
 		return;
 
-	update_curr(cfs_rq);
 	find_matching_se(&se, &pse);
+	update_curr(cfs_rq_of(se));
 	BUG_ON(!pse);
 	if (wakeup_preempt_entity(se, pse) == 1) {
 		/*

Re: [patch 1/1] sched: update_curr versus correct cfs_rq in check_preempt_wakeup

[Ingo Molnar]

* Paul Turner <pjt@google.com> wrote:

> We update_curr() versus the current entity as the preemption 
> decision is based on the relative vruntime.  However, update_curr() 
> is not hierarchical and in the group scheduling case 
> find_matching_se() will have us making the comparison on a cfs_rq 
> different to the one just updated.

Would be nice to include more contextual information in the 
changelog: how did you find it, what effect (if any) did you
see from this patch, what effect do you expect others to see
(if any).

Thanks,

	Ingo

Re: [patch 1/1] sched: update_curr versus correct cfs_rq in check_preempt_wakeup

[Peter Zijlstra]

On Sat, 2011-07-02 at 11:08 +0200, Ingo Molnar wrote:
> * Paul Turner <pjt@google.com> wrote:
> 
> > We update_curr() versus the current entity as the preemption 
> > decision is based on the relative vruntime.  However, update_curr() 
> > is not hierarchical and in the group scheduling case 
> > find_matching_se() will have us making the comparison on a cfs_rq 
> > different to the one just updated.
> 
> Would be nice to include more contextual information in the 
> changelog: how did you find it, what effect (if any) did you
> see from this patch, what effect do you expect others to see
> (if any).

Agreed that the Changelog can be improved. From talking to pjt on IRC
though, I think he spotted this by reading through the code.

The effect of not updating the correct se for comparison is that you
compare the new task to old data of the existing task, thereby giving a
slight preference to the old task (its further to the left than it
should be and thus more desirable to run).

That said, I'm not quite sure the patch is correct though, both se and
pse can change in find_match_se(), maybe we should do update_curr() on
every se we traverse in there, or at least the final two.

Re: [patch 1/1] sched: update_curr versus correct cfs_rq in check_preempt_wakeup

[Ingo Molnar]

* Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:

> On Sat, 2011-07-02 at 11:08 +0200, Ingo Molnar wrote:
> > * Paul Turner <pjt@google.com> wrote:
> > 
> > > We update_curr() versus the current entity as the preemption 
> > > decision is based on the relative vruntime.  However, update_curr() 
> > > is not hierarchical and in the group scheduling case 
> > > find_matching_se() will have us making the comparison on a cfs_rq 
> > > different to the one just updated.
> > 
> > Would be nice to include more contextual information in the 
> > changelog: how did you find it, what effect (if any) did you see 
> > from this patch, what effect do you expect others to see (if 
> > any).
> 
> Agreed that the Changelog can be improved. From talking to pjt on 
> IRC though, I think he spotted this by reading through the code.

'code review' is a perfect answer to the 'how did you find it' 
question: when people read the changelog they will know that no 
practical effect has been observed (yet).

Thanks,

	Ingo

Re: [patch 1/1] sched: update_curr versus correct cfs_rq in check_preempt_wakeup

[Paul Turner]

On Sat, Jul 2, 2011 at 3:27 AM, Ingo Molnar <mingo@elte.hu> wrote:
>
> * Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
>
>> On Sat, 2011-07-02 at 11:08 +0200, Ingo Molnar wrote:
>> > * Paul Turner <pjt@google.com> wrote:
>> >
>> > > We update_curr() versus the current entity as the preemption
>> > > decision is based on the relative vruntime.  However, update_curr()
>> > > is not hierarchical and in the group scheduling case
>> > > find_matching_se() will have us making the comparison on a cfs_rq
>> > > different to the one just updated.
>> >
>> > Would be nice to include more contextual information in the
>> > changelog: how did you find it, what effect (if any) did you see
>> > from this patch, what effect do you expect others to see (if
>> > any).
>>
>> Agreed that the Changelog can be improved. From talking to pjt on
>> IRC though, I think he spotted this by reading through the code.
>
> 'code review' is a perfect answer to the 'how did you find it'

Sure, sorry for omitting this -- updated below.

> question: when people read the changelog they will know that no
> practical effect has been observed (yet).

So there should definitely be a measurable practical effect; for the
running task we are potentially leaving up to a tick of execution
unaccounted in deciding whether or not we cross the wakeup_gran to
preempt.

The fact that this drift is bounded above by our vruntime updates
within entity_tick largely masks the negative effects of this.

>
> Thanks,
>
>        Ingo
>


sched: update correct entity's runtime in check_preempt_wakeup()

While looking at check_preempt_wakeup() I realized that we are potentially
updating the wrong entity in the fair-group scheduling case.  In this case
the current task's cfs_rq may not be the same as the one used for the
comparison between the waking task and the existing task's vruntime.

This potentially results in us using a stale vruntime in the pre-emption
decision, providing a small false preference for the previous task.  The
effects of this are bounded since we always perform a hierarchal update on the
tick.

Signed-off-by: Paul Turner <pjt@google.com>

---
 kernel/sched_fair.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Index: tip2/kernel/sched_fair.c
===================================================================
--- tip2.orig/kernel/sched_fair.c
+++ tip2/kernel/sched_fair.c
@@ -1919,8 +1919,8 @@ static void check_preempt_wakeup(struct
        if (!sched_feat(WAKEUP_PREEMPT))
                return;

-       update_curr(cfs_rq);
        find_matching_se(&se, &pse);
+       update_curr(cfs_rq_of(se));
        BUG_ON(!pse);
        if (wakeup_preempt_entity(se, pse) == 1) {

[tip:sched/core] sched: update correct entity's runtime in check_preempt_wakeup()

[tip-bot for Paul Turner]

Commit-ID:  9bbd7374361d9bfc75108c3ad1c1b6db28b1be59
Gitweb:     http://git.kernel.org/tip/9bbd7374361d9bfc75108c3ad1c1b6db28b1be59
Author:     Paul Turner <pjt@google.com>
AuthorDate: Tue, 5 Jul 2011 19:07:21 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Thu, 21 Jul 2011 18:01:43 +0200

sched: update correct entity's runtime in check_preempt_wakeup()

While looking at check_preempt_wakeup() I realized that we are
potentially updating the wrong entity in the fair-group scheduling
case. In this case the current task's cfs_rq may not be the same as
the one used for the comparison between the waking task and the
existing task's vruntime.

This potentially results in us using a stale vruntime in the
pre-emption decision, providing a small false preference for the
previous task. The effects of this are bounded since we always
perform a hierarchal update on the tick.

Signed-off-by: Paul Turner <pjt@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/CAPM31R+2Ke2urUZKao5W92_LupdR4AYEv-EZWiJ3tG=tEes2cw@mail.gmail.com
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/sched_fair.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index e7d67a9..f88720b 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -1919,8 +1919,8 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_
 	if (!sched_feat(WAKEUP_PREEMPT))
 		return;
 
-	update_curr(cfs_rq);
 	find_matching_se(&se, &pse);
+	update_curr(cfs_rq_of(se));
 	BUG_ON(!pse);
 	if (wakeup_preempt_entity(se, pse) == 1) {
 		/*

Re: [patch 1/1] sched: update_curr versus correct cfs_rq in check_preempt_wakeup

[Paul Turner]

On Sat, Jul 2, 2011 at 2:57 AM, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> On Sat, 2011-07-02 at 11:08 +0200, Ingo Molnar wrote:
>> * Paul Turner <pjt@google.com> wrote:
>>
>> > We update_curr() versus the current entity as the preemption
>> > decision is based on the relative vruntime.  However, update_curr()
>> > is not hierarchical and in the group scheduling case
>> > find_matching_se() will have us making the comparison on a cfs_rq
>> > different to the one just updated.
>>
>> Would be nice to include more contextual information in the
>> changelog: how did you find it, what effect (if any) did you
>> see from this patch, what effect do you expect others to see
>> (if any).
>
> Agreed that the Changelog can be improved. From talking to pjt on IRC
> though, I think he spotted this by reading through the code.
>
> The effect of not updating the correct se for comparison is that you
> compare the new task to old data of the existing task, thereby giving a
> slight preference to the old task (its further to the left than it
> should be and thus more desirable to run).
>
> That said, I'm not quite sure the patch is correct though, both se and
> pse can change in find_match_se(), maybe we should do update_curr() on
> every se we traverse in there, or at least the final two.
>

For the pre-emption decision we only need to update on the final
entity reached as the other levels do not factor into the decision
(and will be updated later).

We also don't need to worry about updates versus pse as until we reach
a common parent there can be no current entity for these levels (and
once we reach a common parent we're on the same cfs_rq anyway).


>
>