[PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Josh Don]

From: Venkatesh Pallipadi <venki@google.com>

Setting skip buddy all the way up the hierarchy does not play well
with intra-cgroup yield. One typical usecase of yield is when a
thread in a cgroup wants to yield CPU to another thread within the
same cgroup. For such a case, setting the skip buddy all the way up
the hierarchy is counter-productive, as that results in CPU being
yielded to a task in some other cgroup.

So, limit the skip effect only to the task requesting it.

Signed-off-by: Josh Don <joshdon@google.com>
---
v2: Only clear skip buddy on the current cfs_rq

 kernel/sched/fair.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 08a233e97a01..0b7a1958ad52 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4051,13 +4051,10 @@ static void __clear_buddies_next(struct sched_entity *se)
 
 static void __clear_buddies_skip(struct sched_entity *se)
 {
-	for_each_sched_entity(se) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-		if (cfs_rq->skip != se)
-			break;
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
+	if (cfs_rq->skip == se)
 		cfs_rq->skip = NULL;
-	}
 }
 
 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
@@ -6552,8 +6549,15 @@ static void set_next_buddy(struct sched_entity *se)
 
 static void set_skip_buddy(struct sched_entity *se)
 {
-	for_each_sched_entity(se)
-		cfs_rq_of(se)->skip = se;
+	/*
+	 * One typical usecase of yield is when a thread in a cgroup
+	 * wants to yield CPU to another thread within the same cgroup.
+	 * For such a case, setting the skip buddy all the way up the
+	 * hierarchy is counter-productive, as that results in CPU being
+	 * yielded to a task in some other cgroup. So, only set skip
+	 * for the task requesting it.
+	 */
+	cfs_rq_of(se)->skip = se;
 }
 
 /*
-- 
2.24.0.393.g34dc348eaf-goog

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Vincent Guittot]

Hi Josh,

On Wed, 4 Dec 2019 at 21:06, Josh Don <joshdon@google.com> wrote:
>
> From: Venkatesh Pallipadi <venki@google.com>
>
> Setting skip buddy all the way up the hierarchy does not play well
> with intra-cgroup yield. One typical usecase of yield is when a
> thread in a cgroup wants to yield CPU to another thread within the
> same cgroup. For such a case, setting the skip buddy all the way up
> the hierarchy is counter-productive, as that results in CPU being
> yielded to a task in some other cgroup.
>
> So, limit the skip effect only to the task requesting it.
>
> Signed-off-by: Josh Don <joshdon@google.com>

There is a mismatch between the author Venkatesh Pallipadi and the
signoff Josh Don
If Venkatesh is the original author and you have then done some
modifications, your both signed-off should be there

Apart from that, the change makes sense to me

> ---
> v2: Only clear skip buddy on the current cfs_rq
>
>  kernel/sched/fair.c | 18 +++++++++++-------
>  1 file changed, 11 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 08a233e97a01..0b7a1958ad52 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4051,13 +4051,10 @@ static void __clear_buddies_next(struct sched_entity *se)
>
>  static void __clear_buddies_skip(struct sched_entity *se)
>  {
> -       for_each_sched_entity(se) {
> -               struct cfs_rq *cfs_rq = cfs_rq_of(se);
> -               if (cfs_rq->skip != se)
> -                       break;
> +       struct cfs_rq *cfs_rq = cfs_rq_of(se);
>
> +       if (cfs_rq->skip == se)
>                 cfs_rq->skip = NULL;
> -       }
>  }
>
>  static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
> @@ -6552,8 +6549,15 @@ static void set_next_buddy(struct sched_entity *se)
>
>  static void set_skip_buddy(struct sched_entity *se)
>  {
> -       for_each_sched_entity(se)
> -               cfs_rq_of(se)->skip = se;
> +       /*
> +        * One typical usecase of yield is when a thread in a cgroup
> +        * wants to yield CPU to another thread within the same cgroup.
> +        * For such a case, setting the skip buddy all the way up the
> +        * hierarchy is counter-productive, as that results in CPU being
> +        * yielded to a task in some other cgroup. So, only set skip
> +        * for the task requesting it.
> +        */
> +       cfs_rq_of(se)->skip = se;
>  }
>
>  /*
> --
> 2.24.0.393.g34dc348eaf-goog
>

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Josh Don]

Hi Vincent,

Thanks for taking a look.

> There is a mismatch between the author Venkatesh Pallipadi and the
> signoff Josh Don
> If Venkatesh is the original author and you have then done some
> modifications, your both signed-off should be there

Venkatesh no longer works at Google, so I don't have a way to get in
touch with him.  Is my signed-off insufficient for this case?


On Thu, Dec 5, 2019 at 11:57 PM Vincent Guittot
<vincent.guittot@linaro.org> wrote:
>
> Hi Josh,
>
> On Wed, 4 Dec 2019 at 21:06, Josh Don <joshdon@google.com> wrote:
> >
> > From: Venkatesh Pallipadi <venki@google.com>
> >
> > Setting skip buddy all the way up the hierarchy does not play well
> > with intra-cgroup yield. One typical usecase of yield is when a
> > thread in a cgroup wants to yield CPU to another thread within the
> > same cgroup. For such a case, setting the skip buddy all the way up
> > the hierarchy is counter-productive, as that results in CPU being
> > yielded to a task in some other cgroup.
> >
> > So, limit the skip effect only to the task requesting it.
> >
> > Signed-off-by: Josh Don <joshdon@google.com>
>
> There is a mismatch between the author Venkatesh Pallipadi and the
> signoff Josh Don
> If Venkatesh is the original author and you have then done some
> modifications, your both signed-off should be there
>
> Apart from that, the change makes sense to me
>
> > ---
> > v2: Only clear skip buddy on the current cfs_rq
> >
> >  kernel/sched/fair.c | 18 +++++++++++-------
> >  1 file changed, 11 insertions(+), 7 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 08a233e97a01..0b7a1958ad52 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -4051,13 +4051,10 @@ static void __clear_buddies_next(struct sched_entity *se)
> >
> >  static void __clear_buddies_skip(struct sched_entity *se)
> >  {
> > -       for_each_sched_entity(se) {
> > -               struct cfs_rq *cfs_rq = cfs_rq_of(se);
> > -               if (cfs_rq->skip != se)
> > -                       break;
> > +       struct cfs_rq *cfs_rq = cfs_rq_of(se);
> >
> > +       if (cfs_rq->skip == se)
> >                 cfs_rq->skip = NULL;
> > -       }
> >  }
> >
> >  static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
> > @@ -6552,8 +6549,15 @@ static void set_next_buddy(struct sched_entity *se)
> >
> >  static void set_skip_buddy(struct sched_entity *se)
> >  {
> > -       for_each_sched_entity(se)
> > -               cfs_rq_of(se)->skip = se;
> > +       /*
> > +        * One typical usecase of yield is when a thread in a cgroup
> > +        * wants to yield CPU to another thread within the same cgroup.
> > +        * For such a case, setting the skip buddy all the way up the
> > +        * hierarchy is counter-productive, as that results in CPU being
> > +        * yielded to a task in some other cgroup. So, only set skip
> > +        * for the task requesting it.
> > +        */
> > +       cfs_rq_of(se)->skip = se;
> >  }
> >
> >  /*
> > --
> > 2.24.0.393.g34dc348eaf-goog
> >

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Dietmar Eggemann]

On 06.12.19 23:13, Josh Don wrote:

[...]

> On Thu, Dec 5, 2019 at 11:57 PM Vincent Guittot
> <vincent.guittot@linaro.org> wrote:
>>
>> Hi Josh,
>>
>> On Wed, 4 Dec 2019 at 21:06, Josh Don <joshdon@google.com> wrote:
>>>
>>> From: Venkatesh Pallipadi <venki@google.com>
>>>
>>> Setting skip buddy all the way up the hierarchy does not play well
>>> with intra-cgroup yield. One typical usecase of yield is when a
>>> thread in a cgroup wants to yield CPU to another thread within the
>>> same cgroup. For such a case, setting the skip buddy all the way up

But with yield_task{_fair}() you have no way to control which other task
gets accelerated. The other task in the taskgroup (cgroup) could be even
on another CPU.

It's not like yield_to_task_fair() which uses next buddy to accelerate
another task p.

What's this typical usecase?

>>> the hierarchy is counter-productive, as that results in CPU being
>>> yielded to a task in some other cgroup.
>>>
>>> So, limit the skip effect only to the task requesting it.

[...]

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Vincent Guittot]

Hi Josh,

On Fri, 6 Dec 2019 at 23:13, Josh Don <joshdon@google.com> wrote:
>
> Hi Vincent,
>
> Thanks for taking a look.
>
> > There is a mismatch between the author Venkatesh Pallipadi and the
> > signoff Josh Don
> > If Venkatesh is the original author and you have then done some
> > modifications, your both signed-off should be there
>
> Venkatesh no longer works at Google, so I don't have a way to get in
> touch with him.  Is my signed-off insufficient for this case?

Maybe you can add a Co-developed-by tag to reflect your additional changes
I guess that as long as you agree with the DCO, it's ok :
https://www.kernel.org/doc/html/v5.4/process/submitting-patches.html#sign-your-work-the-developer-s-certificate-of-origin

Ingo, Peter, what do you think ?


>
>
> On Thu, Dec 5, 2019 at 11:57 PM Vincent Guittot
> <vincent.guittot@linaro.org> wrote:
> >
> > Hi Josh,
> >
> > On Wed, 4 Dec 2019 at 21:06, Josh Don <joshdon@google.com> wrote:
> > >
> > > From: Venkatesh Pallipadi <venki@google.com>
> > >
> > > Setting skip buddy all the way up the hierarchy does not play well
> > > with intra-cgroup yield. One typical usecase of yield is when a
> > > thread in a cgroup wants to yield CPU to another thread within the
> > > same cgroup. For such a case, setting the skip buddy all the way up
> > > the hierarchy is counter-productive, as that results in CPU being
> > > yielded to a task in some other cgroup.
> > >
> > > So, limit the skip effect only to the task requesting it.
> > >
> > > Signed-off-by: Josh Don <joshdon@google.com>
> >
> > There is a mismatch between the author Venkatesh Pallipadi and the
> > signoff Josh Don
> > If Venkatesh is the original author and you have then done some
> > modifications, your both signed-off should be there
> >
> > Apart from that, the change makes sense to me
> >
> > > ---
> > > v2: Only clear skip buddy on the current cfs_rq
> > >
> > >  kernel/sched/fair.c | 18 +++++++++++-------
> > >  1 file changed, 11 insertions(+), 7 deletions(-)
> > >
> > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > > index 08a233e97a01..0b7a1958ad52 100644
> > > --- a/kernel/sched/fair.c
> > > +++ b/kernel/sched/fair.c
> > > @@ -4051,13 +4051,10 @@ static void __clear_buddies_next(struct sched_entity *se)
> > >
> > >  static void __clear_buddies_skip(struct sched_entity *se)
> > >  {
> > > -       for_each_sched_entity(se) {
> > > -               struct cfs_rq *cfs_rq = cfs_rq_of(se);
> > > -               if (cfs_rq->skip != se)
> > > -                       break;
> > > +       struct cfs_rq *cfs_rq = cfs_rq_of(se);
> > >
> > > +       if (cfs_rq->skip == se)
> > >                 cfs_rq->skip = NULL;
> > > -       }
> > >  }
> > >
> > >  static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
> > > @@ -6552,8 +6549,15 @@ static void set_next_buddy(struct sched_entity *se)
> > >
> > >  static void set_skip_buddy(struct sched_entity *se)
> > >  {
> > > -       for_each_sched_entity(se)
> > > -               cfs_rq_of(se)->skip = se;
> > > +       /*
> > > +        * One typical usecase of yield is when a thread in a cgroup
> > > +        * wants to yield CPU to another thread within the same cgroup.
> > > +        * For such a case, setting the skip buddy all the way up the
> > > +        * hierarchy is counter-productive, as that results in CPU being
> > > +        * yielded to a task in some other cgroup. So, only set skip
> > > +        * for the task requesting it.
> > > +        */
> > > +       cfs_rq_of(se)->skip = se;
> > >  }
> > >
> > >  /*
> > > --
> > > 2.24.0.393.g34dc348eaf-goog
> > >

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Josh Don]

On Mon, Dec 9, 2019 at 1:19 AM Dietmar Eggemann
<dietmar.eggemann@arm.com> wrote:
>
> On 06.12.19 23:13, Josh Don wrote:
>
> [...]
>
> > On Thu, Dec 5, 2019 at 11:57 PM Vincent Guittot
> > <vincent.guittot@linaro.org> wrote:
> >>
> >> Hi Josh,
> >>
> >> On Wed, 4 Dec 2019 at 21:06, Josh Don <joshdon@google.com> wrote:
> >>>
> >>> From: Venkatesh Pallipadi <venki@google.com>
> >>>
> >>> Setting skip buddy all the way up the hierarchy does not play well
> >>> with intra-cgroup yield. One typical usecase of yield is when a
> >>> thread in a cgroup wants to yield CPU to another thread within the
> >>> same cgroup. For such a case, setting the skip buddy all the way up
>
> But with yield_task{_fair}() you have no way to control which other task
> gets accelerated. The other task in the taskgroup (cgroup) could be even
> on another CPU.
>
> It's not like yield_to_task_fair() which uses next buddy to accelerate
> another task p.
>
> What's this typical usecase?

The semantics for yield_task under CFS are not well-defined.  With our
CFS hierarchy, we cannot easily just push a yielded task to the end of
a runqueue.  And, we don't want to play games with artificially
increasing vruntime, as this results in potentially high latency for a
yielded task to get back on CPU.

I'd interpret a task that calls yield as saying "I can run, but try to
run something else."  I'd agree that this patch is imperfect in
achieving this, but I think it is better than the current
implementation (or at least, less broken).  Currently, a side-effect
of calling yield is that all other tasks in the same hierarchy get
skipped as well.  This is almost certainly not what the user
expects/wants.  It is true that if a yielded task has no other tasks
in its cgroup on the same CPU, we will potentially end up just picking
the yielded task again.  But this should be OK; a yielded task should
be able to continue making forward progress.  Any yielded task that
calls yield again is likely implementing a busy loop, which is an
improper use of yield anyway.

I also played around with the idea of setting the skip buddy up the
hierarchy up to the point where cfs_rq->nr_running > 1, but this is
racy with enqueue, and in general raises questions about whether an
enqueued task should try to clear skip buddies.

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Josh Don]

On Thu, Dec 12, 2019 at 12:05 AM Vincent Guittot
<vincent.guittot@linaro.org> wrote:
>
> Hi Josh,
>
> On Fri, 6 Dec 2019 at 23:13, Josh Don <joshdon@google.com> wrote:
> >
> > Hi Vincent,
> >
> > Thanks for taking a look.
> >
> > > There is a mismatch between the author Venkatesh Pallipadi and the
> > > signoff Josh Don
> > > If Venkatesh is the original author and you have then done some
> > > modifications, your both signed-off should be there
> >
> > Venkatesh no longer works at Google, so I don't have a way to get in
> > touch with him.  Is my signed-off insufficient for this case?
>
> Maybe you can add a Co-developed-by tag to reflect your additional changes
> I guess that as long as you agree with the DCO, it's ok :
> https://www.kernel.org/doc/html/v5.4/process/submitting-patches.html#sign-your-work-the-developer-s-certificate-of-origin
>
> Ingo, Peter, what do you think ?

I could add the Co-developed-by tag if that would be sufficient here.
As a side note, I'm also looking at upstreaming our other sched
fixes/patches, and some of these have the same issue with respect to
the original author.  How would you prefer I handle these in general?

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Peter Zijlstra]

On Tue, Dec 17, 2019 at 11:58:28AM -0800, Josh Don wrote:
> > Ingo, Peter, what do you think ?
> 
> I could add the Co-developed-by tag if that would be sufficient here.
> As a side note, I'm also looking at upstreaming our other sched
> fixes/patches, and some of these have the same issue with respect to
> the original author.  How would you prefer I handle these in general?

These internal patches that you have, don't they have a SoB on from the
original author?

Ingo, Greg, how do we handle patches where the original Author has
vanished/left etc and no SoB is present?

Now, in this case we know Venki was with Google in the US, and the US
allows/has copyright assignment to employers and therefore any old SoB
from a Google person should probably be sufficient, but that argument
doesn't work in general (Germany for example doesn't allow copyright
assignment/transfer).

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Greg Kroah-Hartman]

On Tue, Dec 17, 2019 at 09:42:44PM +0100, Peter Zijlstra wrote:
> On Tue, Dec 17, 2019 at 11:58:28AM -0800, Josh Don wrote:
> > > Ingo, Peter, what do you think ?
> > 
> > I could add the Co-developed-by tag if that would be sufficient here.
> > As a side note, I'm also looking at upstreaming our other sched
> > fixes/patches, and some of these have the same issue with respect to
> > the original author.  How would you prefer I handle these in general?
> 
> These internal patches that you have, don't they have a SoB on from the
> original author?
> 
> Ingo, Greg, how do we handle patches where the original Author has
> vanished/left etc and no SoB is present?
> 
> Now, in this case we know Venki was with Google in the US, and the US
> allows/has copyright assignment to employers and therefore any old SoB
> from a Google person should probably be sufficient, but that argument
> doesn't work in general (Germany for example doesn't allow copyright
> assignment/transfer).

Most Google kernel work is "work for hire" from what I have heard.

But the copyright of the patch really doesn't matter if the patch is
under the GPLv2 (obviously here), then anyone can send it in and put
their s-o-b on it.  The fact that it's someone from the same company is
good enough to let us know who to track down and kick if something
breaks with the patch, which is all we really need :)

hope this helps,

greg k-h

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Dietmar Eggemann]

On 12/12/2019 23:19, Josh Don wrote:
> On Mon, Dec 9, 2019 at 1:19 AM Dietmar Eggemann
> <dietmar.eggemann@arm.com> wrote:
>>
>> On 06.12.19 23:13, Josh Don wrote:
>>
>> [...]
>>
>>> On Thu, Dec 5, 2019 at 11:57 PM Vincent Guittot
>>> <vincent.guittot@linaro.org> wrote:
>>>>
>>>> Hi Josh,
>>>>
>>>> On Wed, 4 Dec 2019 at 21:06, Josh Don <joshdon@google.com> wrote:
>>>>>
>>>>> From: Venkatesh Pallipadi <venki@google.com>
>>>>>
>>>>> Setting skip buddy all the way up the hierarchy does not play well
>>>>> with intra-cgroup yield. One typical usecase of yield is when a
>>>>> thread in a cgroup wants to yield CPU to another thread within the
>>>>> same cgroup. For such a case, setting the skip buddy all the way up
>>
>> But with yield_task{_fair}() you have no way to control which other task
>> gets accelerated. The other task in the taskgroup (cgroup) could be even
>> on another CPU.
>>
>> It's not like yield_to_task_fair() which uses next buddy to accelerate
>> another task p.
>>
>> What's this typical usecase?
> 
> The semantics for yield_task under CFS are not well-defined.  With our
> CFS hierarchy, we cannot easily just push a yielded task to the end of
> a runqueue.  And, we don't want to play games with artificially
> increasing vruntime, as this results in potentially high latency for a
> yielded task to get back on CPU.
> 
> I'd interpret a task that calls yield as saying "I can run, but try to
> run something else."  I'd agree that this patch is imperfect in
> achieving this, but I think it is better than the current
> implementation (or at least, less broken).  Currently, a side-effect
> of calling yield is that all other tasks in the same hierarchy get
> skipped as well.  This is almost certainly not what the user
> expects/wants.  It is true that if a yielded task has no other tasks
> in its cgroup on the same CPU, we will potentially end up just picking
> the yielded task again.  But this should be OK; a yielded task should
> be able to continue making forward progress.  Any yielded task that
> calls yield again is likely implementing a busy loop, which is an
> improper use of yield anyway.

I see the issue you want to address.

But isn't then the comment in the patch "... a thread in a cgroup wants
to yield CPU to another thread within the same cgroup ..." misleading?

IMHO, a task can't yield to another task. It can only relinquish the CPU.

Someone could argue that in the current implementation, the task which
calls yield acts on behalf of all the tasks in its taskgroup hierarchy.
But this can have issues as you pointed out.

[...]

Re: [PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Josh Don]

Agreed; I'll modify the comment to better reflect the intention here.
Thanks for taking a look!

[PATCH v3] sched/fair: Do not set skip buddy up the sched hierarchy

[Josh Don]

From: Venkatesh Pallipadi <venki@google.com>

Setting the skip buddy up the hierarchy effectively means that a thread
calling yield will also end up skipping the other tasks in its hierarchy
as well. However, a yielding thread shouldn't end up causing this
behavior on behalf of its entire hierarchy.

For typical uses of yield, setting the skip buddy up the hierarchy is
counter-productive, as that results in CPU being yielded to a task in
some other cgroup.

So, limit the skip effect only to the task requesting it.

Co-developed-by: Josh Don <joshdon@google.com>
Signed-off-by: Josh Don <joshdon@google.com>
---
v2: Only clear skip buddy on the current cfs_rq

v3: Modify comment describing the justification for this change.

 kernel/sched/fair.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 08a233e97a01..0056b57d52cb 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4051,13 +4051,10 @@ static void __clear_buddies_next(struct sched_entity *se)
 
 static void __clear_buddies_skip(struct sched_entity *se)
 {
-	for_each_sched_entity(se) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-		if (cfs_rq->skip != se)
-			break;
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
+	if (cfs_rq->skip == se)
 		cfs_rq->skip = NULL;
-	}
 }
 
 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
@@ -6552,8 +6549,12 @@ static void set_next_buddy(struct sched_entity *se)
 
 static void set_skip_buddy(struct sched_entity *se)
 {
-	for_each_sched_entity(se)
-		cfs_rq_of(se)->skip = se;
+	/*
+	 * Only set the skip buddy for the task requesting it. Setting the skip
+	 * buddy up the hierarchy would result in skipping all other tasks in
+	 * the hierarchy as well.
+	 */
+	cfs_rq_of(se)->skip = se;
 }
 
 /*
-- 
2.24.1.735.g03f4e72817-goog

Re: [PATCH v3] sched/fair: Do not set skip buddy up the sched hierarchy

[Vincent Guittot]

On Thu, 19 Dec 2019 at 01:14, Josh Don <joshdon@google.com> wrote:
>
> From: Venkatesh Pallipadi <venki@google.com>
>
> Setting the skip buddy up the hierarchy effectively means that a thread
> calling yield will also end up skipping the other tasks in its hierarchy
> as well. However, a yielding thread shouldn't end up causing this
> behavior on behalf of its entire hierarchy.
>
> For typical uses of yield, setting the skip buddy up the hierarchy is
> counter-productive, as that results in CPU being yielded to a task in
> some other cgroup.
>
> So, limit the skip effect only to the task requesting it.
>
> Co-developed-by: Josh Don <joshdon@google.com>
> Signed-off-by: Josh Don <joshdon@google.com>

Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>

> ---
> v2: Only clear skip buddy on the current cfs_rq
>
> v3: Modify comment describing the justification for this change.
>
>  kernel/sched/fair.c | 15 ++++++++-------
>  1 file changed, 8 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 08a233e97a01..0056b57d52cb 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4051,13 +4051,10 @@ static void __clear_buddies_next(struct sched_entity *se)
>
>  static void __clear_buddies_skip(struct sched_entity *se)
>  {
> -       for_each_sched_entity(se) {
> -               struct cfs_rq *cfs_rq = cfs_rq_of(se);
> -               if (cfs_rq->skip != se)
> -                       break;
> +       struct cfs_rq *cfs_rq = cfs_rq_of(se);
>
> +       if (cfs_rq->skip == se)
>                 cfs_rq->skip = NULL;
> -       }
>  }
>
>  static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
> @@ -6552,8 +6549,12 @@ static void set_next_buddy(struct sched_entity *se)
>
>  static void set_skip_buddy(struct sched_entity *se)
>  {
> -       for_each_sched_entity(se)
> -               cfs_rq_of(se)->skip = se;
> +       /*
> +        * Only set the skip buddy for the task requesting it. Setting the skip
> +        * buddy up the hierarchy would result in skipping all other tasks in
> +        * the hierarchy as well.
> +        */
> +       cfs_rq_of(se)->skip = se;
>  }
>
>  /*
> --
> 2.24.1.735.g03f4e72817-goog
>

Re: [PATCH v3] sched/fair: Do not set skip buddy up the sched hierarchy

[Josh Don]

Bumping in case this fell through the cracks of the patch queue

On Thu, Dec 26, 2019 at 7:05 AM Vincent Guittot
<vincent.guittot@linaro.org> wrote:
>
> On Thu, 19 Dec 2019 at 01:14, Josh Don <joshdon@google.com> wrote:
> >
> > From: Venkatesh Pallipadi <venki@google.com>
> >
> > Setting the skip buddy up the hierarchy effectively means that a thread
> > calling yield will also end up skipping the other tasks in its hierarchy
> > as well. However, a yielding thread shouldn't end up causing this
> > behavior on behalf of its entire hierarchy.
> >
> > For typical uses of yield, setting the skip buddy up the hierarchy is
> > counter-productive, as that results in CPU being yielded to a task in
> > some other cgroup.
> >
> > So, limit the skip effect only to the task requesting it.
> >
> > Co-developed-by: Josh Don <joshdon@google.com>
> > Signed-off-by: Josh Don <joshdon@google.com>
>
> Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>
>
> > ---
> > v2: Only clear skip buddy on the current cfs_rq
> >
> > v3: Modify comment describing the justification for this change.
> >
> >  kernel/sched/fair.c | 15 ++++++++-------
> >  1 file changed, 8 insertions(+), 7 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 08a233e97a01..0056b57d52cb 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -4051,13 +4051,10 @@ static void __clear_buddies_next(struct sched_entity *se)
> >
> >  static void __clear_buddies_skip(struct sched_entity *se)
> >  {
> > -       for_each_sched_entity(se) {
> > -               struct cfs_rq *cfs_rq = cfs_rq_of(se);
> > -               if (cfs_rq->skip != se)
> > -                       break;
> > +       struct cfs_rq *cfs_rq = cfs_rq_of(se);
> >
> > +       if (cfs_rq->skip == se)
> >                 cfs_rq->skip = NULL;
> > -       }
> >  }
> >
> >  static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
> > @@ -6552,8 +6549,12 @@ static void set_next_buddy(struct sched_entity *se)
> >
> >  static void set_skip_buddy(struct sched_entity *se)
> >  {
> > -       for_each_sched_entity(se)
> > -               cfs_rq_of(se)->skip = se;
> > +       /*
> > +        * Only set the skip buddy for the task requesting it. Setting the skip
> > +        * buddy up the hierarchy would result in skipping all other tasks in
> > +        * the hierarchy as well.
> > +        */
> > +       cfs_rq_of(se)->skip = se;
> >  }
> >
> >  /*
> > --
> > 2.24.1.735.g03f4e72817-goog
> >

[PATCH v2] sched/fair: Do not set skip buddy up the sched hierarchy

[Josh Don]

From: Venkatesh Pallipadi <venki@google.com>

Setting skip buddy all the way up the hierarchy does not play well
with intra-cgroup yield. One typical usecase of yield is when a
thread in a cgroup wants to yield CPU to another thread within the
same cgroup. For such a case, setting the skip buddy all the way up
the hierarchy is counter-productive, as that results in CPU being
yielded to a task in some other cgroup.

So, limit the skip effect only to the task requesting it.

Signed-off-by: Josh Don <joshdon@google.com>
---
Changelog since v1:
- As an optimization, skip clearing the skip buddy up the hierarchy
- Due to the above, it makes sense to inline __clear_buddies_skip; while
  we're at it, inline the other __clear_buddies* functions as well.

 kernel/sched/fair.c | 27 +++++++++++++++------------
 1 file changed, 15 insertions(+), 12 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 682a754ea3e1..dbac30e3cc08 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4010,7 +4010,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 	}
 }
 
-static void __clear_buddies_last(struct sched_entity *se)
+static inline void __clear_buddies_last(struct sched_entity *se)
 {
 	for_each_sched_entity(se) {
 		struct cfs_rq *cfs_rq = cfs_rq_of(se);
@@ -4021,7 +4021,7 @@ static void __clear_buddies_last(struct sched_entity *se)
 	}
 }
 
-static void __clear_buddies_next(struct sched_entity *se)
+static inline void __clear_buddies_next(struct sched_entity *se)
 {
 	for_each_sched_entity(se) {
 		struct cfs_rq *cfs_rq = cfs_rq_of(se);
@@ -4032,15 +4032,12 @@ static void __clear_buddies_next(struct sched_entity *se)
 	}
 }
 
-static void __clear_buddies_skip(struct sched_entity *se)
+static inline void __clear_buddies_skip(struct sched_entity *se)
 {
-	for_each_sched_entity(se) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-		if (cfs_rq->skip != se)
-			break;
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
+	if (cfs_rq->skip == se)
 		cfs_rq->skip = NULL;
-	}
 }
 
 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
@@ -4051,8 +4048,7 @@ static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
 	if (cfs_rq->next == se)
 		__clear_buddies_next(se);
 
-	if (cfs_rq->skip == se)
-		__clear_buddies_skip(se);
+	__clear_buddies_skip(se);
 }
 
 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
@@ -6647,8 +6643,15 @@ static void set_next_buddy(struct sched_entity *se)
 
 static void set_skip_buddy(struct sched_entity *se)
 {
-	for_each_sched_entity(se)
-		cfs_rq_of(se)->skip = se;
+	/*
+	 * One typical usecase of yield is when a thread in a cgroup
+	 * wants to yield CPU to another thread within the same cgroup.
+	 * For such a case, setting the skip buddy all the way up the
+	 * hierarchy is counter-productive, as that results in CPU being
+	 * yielded to a task in some other cgroup. So, only set skip
+	 * for the task requesting it.
+	 */
+	cfs_rq_of(se)->skip = se;
 }
 
 /*
-- 
2.24.0.rc1.363.gb1bccd3e3d-goog