Skip to contentSkip to conversation

sched/fair: Do not set skip buddy up the sched hierarchy

PATCH Superseded Josh Don 5 participants 14 messages Dec 4, 2019 – Feb 25, 2020 Scheduler

lore
Share & tools
lore

Josh Don

author
#0 lore raw

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

From: Venkatesh Pallipadi <[email protected]>

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.

---
v2: Only clear skip buddy on the current cfs_rq

 kernel/sched/fair.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -7
index 08a233e97a01..0b7a1958ad52 100644
@@ -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;
 }
 
 /*
Signature · 1 line
2.24.0.393.g34dc348eaf-goog
maintainer
#1 lore raw

Hi Josh,

Quoted 10 lines · Josh Don

From: Venkatesh Pallipadi <[email protected]>

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.

Quoted 3 lines

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

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

Quoted 47 lines

---
v2: Only clear skip buddy on the current cfs_rq

 kernel/sched/fair.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -8
index 08a233e97a01..0b7a1958ad52 100644
@@ -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

author
#2 lore raw

Hi Vincent,

Thanks for taking a look.

Quoted 4 lines

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?

Quoted 72 lines · Vincent Guittot

Hi Josh,

Quoted 10 lines · Josh Don

From: Venkatesh Pallipadi <[email protected]>

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.

Quoted 3 lines

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

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

Quoted 47 lines

---
v2: Only clear skip buddy on the current cfs_rq

 kernel/sched/fair.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -8
index 08a233e97a01..0b7a1958ad52 100644
@@ -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

#3 lore raw

On 06.12.19 23:13, Josh Don wrote:

[...]

Quoted 5 lines
Quoted 3 lines · Vincent Guittot

Hi Josh,

Quoted 8 lines
Quoted 8 lines · Josh Don
Quoted 7 lines

From: Venkatesh Pallipadi <[email protected]>

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?

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

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.

[...]

author
#4 lore raw
Quoted 19 lines · Dietmar Eggemann

On 06.12.19 23:13, Josh Don wrote:

[...]

Quoted 5 lines
Quoted 3 lines · Vincent Guittot

Hi Josh,

Quoted 8 lines
Quoted 8 lines · Josh Don
Quoted 7 lines

From: Venkatesh Pallipadi <[email protected]>

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

Quoted 8 lines

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.

#5 lore raw
Quoted 36 lines · Josh Don
Quoted 19 lines · Dietmar Eggemann

On 06.12.19 23:13, Josh Don wrote:

[...]

Quoted 5 lines
Quoted 3 lines · Vincent Guittot

Hi Josh,

Quoted 8 lines
Quoted 8 lines · Josh Don
Quoted 7 lines

From: Venkatesh Pallipadi <[email protected]>

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

Quoted 8 lines

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.

Quoted 12 lines

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.

[...]

author
#6 lore raw

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

author
#7 lore raw

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

From: Venkatesh Pallipadi <[email protected]>

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.

---
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(-)
kernel/sched/fair.c +8 -7
index 08a233e97a01..0056b57d52cb 100644
@@ -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;
 }
 
 /*
Signature · 1 line
2.24.1.735.g03f4e72817-goog
maintainer Reviewed-by on v3 1/1
#8 lore raw
Quoted 8 lines · Josh Don

From: Venkatesh Pallipadi <[email protected]>

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.

Quoted 8 lines

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.

Quoted 46 lines

---
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(-)
kernel/sched/fair.c +8 -8
index 08a233e97a01..0056b57d52cb 100644
@@ -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

author
#9 lore raw

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

Quoted 67 lines · Vincent Guittot
Quoted 8 lines · Josh Don

From: Venkatesh Pallipadi <[email protected]>

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.

Quoted 8 lines

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.

Quoted 46 lines

---
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(-)
kernel/sched/fair.c +8 -8
index 08a233e97a01..0056b57d52cb 100644
@@ -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

maintainer
#10 lore raw
In reply to Josh Don

Hi Josh,

Quoted 5 lines · Josh Don

Hi Vincent,

Thanks for taking a look.

Quoted 7 lines
Quoted 4 lines

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 ?

Quoted 76 lines
Quoted 72 lines · Vincent Guittot

Hi Josh,

Quoted 10 lines · Josh Don

From: Venkatesh Pallipadi <[email protected]>

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.

Quoted 3 lines

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

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

Quoted 47 lines

---
v2: Only clear skip buddy on the current cfs_rq

 kernel/sched/fair.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -8
index 08a233e97a01..0b7a1958ad52 100644
@@ -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

author
#11 lore raw
Quoted 14 lines · Vincent Guittot

Hi Josh,

Quoted 10 lines · Josh Don

Hi Vincent,

Thanks for taking a look.

Quoted 4 lines

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

Quoted 8 lines
Quoted 2 lines

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?

maintainer
#12 lore raw
Quoted 6 lines · Josh Don
Quoted 1 line

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).

#13 lore raw
Quoted 11 lines · Peter Zijlstra
Quoted 6 lines · Josh Don
Quoted 1 line

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?

Quoted 8 lines

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