Skip to contentSkip to conversation

sched: Don't try to catch up excess steal time.

PATCH Applied Suleiman Souhlal 6 participants 8 messages Nov 18, 2024 – Dec 2, 2024

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH v3 1/1 sched: Don't try to catch up excess steal time.

When steal time exceeds the measured delta when updating clock_task, we currently try to catch up the excess in future updates. However, this results in inaccurate run times for the future things using clock_task, in some situations, as they end up getting additional steal time that did not actually happen.
This is because there is a window between reading the elapsed time in update_rq_clock() and sampling the steal time in update_rq_clock_task(). If the VCPU gets preempted between those two points, any additional steal time is accounted to the outgoing task even though the calculated delta did not actually contain any of that "stolen" time. When this race happens, we can end up with steal time that exceeds the calculated delta, and the previous code would try to catch up that excess steal time in future clock updates, which is given to the next, incoming task, even though it did not actually have any time stolen.

This behavior is particularly bad when steal time can be very long, which we've seen when trying to extend steal time to contain the duration that the host was suspended [0]. When this happens, clock_task stays frozen, during which the running task stays running for the whole duration, since its run time doesn't increase.
However the race can happen even under normal operation.

Ideally we would read the elapsed cpu time and the steal time atomically, to prevent this race from happening in the first place, but doing so is non-trivial.

Since the time between those two points isn't otherwise accounted anywhere, neither to the outgoing task nor the incoming task (because the "end of outgoing task" and "start of incoming task" timestamps are the same), I would argue that the right thing to do is to simply drop any excess steal time, in order to prevent these issues.

[0] https://lore.kernel.org/kvm/[email protected]/

---
v3:
- Reword commit message.
- Revert back to v1 code, since it's more understandable.

v2: https://lore.kernel.org/lkml/[email protected]
- Slightly changed to simply moving one line up instead of adding new variable.

v1: https://lore.kernel.org/lkml/[email protected]

---
 kernel/sched/core.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/core.c +4 -2
index a1c353a62c56..13f70316ef39 100644
@@ -766,13 +766,15 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 #endif
 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
 	if (static_key_false((&paravirt_steal_rq_enabled))) {
-		steal = paravirt_steal_clock(cpu_of(rq));
+		u64 prev_steal;
+
+		steal = prev_steal = paravirt_steal_clock(cpu_of(rq));
 		steal -= rq->prev_steal_time_rq;
 
 		if (unlikely(steal > delta))
 			steal = delta;
 
-		rq->prev_steal_time_rq += steal;
+		rq->prev_steal_time_rq = prev_steal;
 		delta -= steal;
 	}
 #endif
Signature · 1 line
2.47.0.338.g60cca15819-goog
maintainer
#1 lore raw
Quoted 32 lines · Suleiman Souhlal

When steal time exceeds the measured delta when updating clock_task, we currently try to catch up the excess in future updates. However, this results in inaccurate run times for the future things using clock_task, in some situations, as they end up getting additional steal time that did not actually happen.
This is because there is a window between reading the elapsed time in update_rq_clock() and sampling the steal time in update_rq_clock_task(). If the VCPU gets preempted between those two points, any additional steal time is accounted to the outgoing task even though the calculated delta did not actually contain any of that "stolen" time. When this race happens, we can end up with steal time that exceeds the calculated delta, and the previous code would try to catch up that excess steal time in future clock updates, which is given to the next, incoming task, even though it did not actually have any time stolen.

This behavior is particularly bad when steal time can be very long, which we've seen when trying to extend steal time to contain the duration that the host was suspended [0]. When this happens, clock_task stays frozen, during which the running task stays running for the whole duration, since its run time doesn't increase.
However the race can happen even under normal operation.

Ideally we would read the elapsed cpu time and the steal time atomically, to prevent this race from happening in the first place, but doing so is non-trivial.

Since the time between those two points isn't otherwise accounted anywhere, neither to the outgoing task nor the incoming task (because the "end of outgoing task" and "start of incoming task" timestamps are the same), I would argue that the right thing to do is to simply drop any excess steal time, in order to prevent these issues.

Quoted 3 lines

[0] https://lore.kernel.org/kvm/[email protected]/

Right.. uhm.. I don't particularly care much either way. Are other people with virt clue okay with this?

Quoted 29 lines
---
 kernel/sched/core.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/core.c +4 -2
index a1c353a62c56..13f70316ef39 100644
@@ -766,13 +766,15 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 #endif
 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
 	if (static_key_false((&paravirt_steal_rq_enabled))) {
-		steal = paravirt_steal_clock(cpu_of(rq));
+		u64 prev_steal;
+
+		steal = prev_steal = paravirt_steal_clock(cpu_of(rq));
 		steal -= rq->prev_steal_time_rq;
 
 		if (unlikely(steal > delta))
 			steal = delta;
 
-		rq->prev_steal_time_rq += steal;
+		rq->prev_steal_time_rq = prev_steal;
 		delta -= steal;
 	}
 #endif
Signature · 1 line
2.47.0.338.g60cca15819-goog
#2 lore raw
Quoted 33 lines · Peter Zijlstra
Quoted 32 lines · Suleiman Souhlal

When steal time exceeds the measured delta when updating clock_task, we currently try to catch up the excess in future updates. However, this results in inaccurate run times for the future things using clock_task, in some situations, as they end up getting additional steal time that did not actually happen.
This is because there is a window between reading the elapsed time in update_rq_clock() and sampling the steal time in update_rq_clock_task(). If the VCPU gets preempted between those two points, any additional steal time is accounted to the outgoing task even though the calculated delta did not actually contain any of that "stolen" time. When this race happens, we can end up with steal time that exceeds the calculated delta, and the previous code would try to catch up that excess steal time in future clock updates, which is given to the next, incoming task, even though it did not actually have any time stolen.

This behavior is particularly bad when steal time can be very long, which we've seen when trying to extend steal time to contain the duration that the host was suspended [0]. When this happens, clock_task stays frozen, during which the running task stays running for the whole duration, since its run time doesn't increase.
However the race can happen even under normal operation.

Ideally we would read the elapsed cpu time and the steal time atomically, to prevent this race from happening in the first place, but doing so is non-trivial.

Since the time between those two points isn't otherwise accounted anywhere, neither to the outgoing task nor the incoming task (because the "end of outgoing task" and "start of incoming task" timestamps are the same), I would argue that the right thing to do is to simply drop any excess steal time, in order to prevent these issues.

Quoted 6 lines
Quoted 3 lines

[0] https://lore.kernel.org/kvm/[email protected]/

Right.. uhm.. I don't particularly care much either way. Are other people with virt clue okay with this?

I'm slightly dubious because now we may systemically lose accounted steal time where before it was all at least accounted *somewhere*, and we might reasonably have expected the slight inaccuracies to balance out over time.

But this *does* fix the main problem I was seeing, that the kernel will currently just keep attributing steal time to processes *forever* if a buggy hypervisor lets it step backwards. So I can live with it.

#3 lore raw
In reply to Suleiman Souhlal
Quoted 55 lines · On Mon, 18 Nov 2024 13:37:45 +0900 Suleiman Souhlal <[email protected]> wrote:

When steal time exceeds the measured delta when updating clock_task, we currently try to catch up the excess in future updates. However, this results in inaccurate run times for the future things using clock_task, in some situations, as they end up getting additional steal time that did not actually happen.
This is because there is a window between reading the elapsed time in update_rq_clock() and sampling the steal time in update_rq_clock_task(). If the VCPU gets preempted between those two points, any additional steal time is accounted to the outgoing task even though the calculated delta did not actually contain any of that "stolen" time. When this race happens, we can end up with steal time that exceeds the calculated delta, and the previous code would try to catch up that excess steal time in future clock updates, which is given to the next, incoming task, even though it did not actually have any time stolen.

This behavior is particularly bad when steal time can be very long, which we've seen when trying to extend steal time to contain the duration that the host was suspended [0]. When this happens, clock_task stays frozen, during which the running task stays running for the whole duration, since its run time doesn't increase.
However the race can happen even under normal operation.

Ideally we would read the elapsed cpu time and the steal time atomically, to prevent this race from happening in the first place, but doing so is non-trivial.

Since the time between those two points isn't otherwise accounted anywhere, neither to the outgoing task nor the incoming task (because the "end of outgoing task" and "start of incoming task" timestamps are the same), I would argue that the right thing to do is to simply drop any excess steal time, in order to prevent these issues.

[0] https://lore.kernel.org/kvm/[email protected]/

---
v3:
- Reword commit message.
- Revert back to v1 code, since it's more understandable.

v2: https://lore.kernel.org/lkml/[email protected]
- Slightly changed to simply moving one line up instead of adding new variable.

v1: https://lore.kernel.org/lkml/[email protected]

---
 kernel/sched/core.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/core.c +0 -0
index a1c353a62c56..13f70316ef39 100644
@@ -766,13 +766,15 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 #endif

kernel/sched/core.c static void update_rq_clock_task(struct rq *rq, s64 delta) · line 775

Quoted 10 lines
kernel/sched/core.c +3 -1
 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
 	if (static_key_false((&paravirt_steal_rq_enabled))) {
-		steal = paravirt_steal_clock(cpu_of(rq));
+		u64 prev_steal;
+
+		steal = prev_steal = paravirt_steal_clock(cpu_of(rq));
 		steal -= rq->prev_steal_time_rq;
 
 		if (unlikely(steal > delta))
 			steal = delta;

So is the problem just the above if statement? That is, delta is already calculated, but if we get interrupted by the host before steal is calculated and the time then becomes greater than delta, the time difference between delta and steal gets pushed off to the next task, right?

-- Steve

Quoted 6 lines
kernel/sched/core.c +1 -1
-		rq->prev_steal_time_rq += steal;
+		rq->prev_steal_time_rq = prev_steal;
 		delta -= steal;
 	}
 #endif
#4 lore raw
Quoted 67 lines · Steven Rostedt
Quoted 63 lines · On Mon, 18 Nov 2024 13:37:45 +0900 Suleiman Souhlal <[email protected]> wrote:

When steal time exceeds the measured delta when updating clock_task, we currently try to catch up the excess in future updates. However, this results in inaccurate run times for the future things using clock_task, in some situations, as they end up getting additional steal time that did not actually happen.
This is because there is a window between reading the elapsed time in update_rq_clock() and sampling the steal time in update_rq_clock_task(). If the VCPU gets preempted between those two points, any additional steal time is accounted to the outgoing task even though the calculated delta did not actually contain any of that "stolen" time. When this race happens, we can end up with steal time that exceeds the calculated delta, and the previous code would try to catch up that excess steal time in future clock updates, which is given to the next, incoming task, even though it did not actually have any time stolen.

This behavior is particularly bad when steal time can be very long, which we've seen when trying to extend steal time to contain the duration that the host was suspended [0]. When this happens, clock_task stays frozen, during which the running task stays running for the whole duration, since its run time doesn't increase.
However the race can happen even under normal operation.

Ideally we would read the elapsed cpu time and the steal time atomically, to prevent this race from happening in the first place, but doing so is non-trivial.

Since the time between those two points isn't otherwise accounted anywhere, neither to the outgoing task nor the incoming task (because the "end of outgoing task" and "start of incoming task" timestamps are the same), I would argue that the right thing to do is to simply drop any excess steal time, in order to prevent these issues.

[0] https://lore.kernel.org/kvm/[email protected]/

---
v3:
- Reword commit message.
- Revert back to v1 code, since it's more understandable.

v2: https://lore.kernel.org/lkml/[email protected]
- Slightly changed to simply moving one line up instead of adding new variable.

v1: https://lore.kernel.org/lkml/[email protected]

---
 kernel/sched/core.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/core.c +3 -1
index a1c353a62c56..13f70316ef39 100644
@@ -766,13 +766,15 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 #endif
 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
      if (static_key_false((&paravirt_steal_rq_enabled))) {
-             steal = paravirt_steal_clock(cpu_of(rq));
+             u64 prev_steal;
+
+             steal = prev_steal = paravirt_steal_clock(cpu_of(rq));
              steal -= rq->prev_steal_time_rq;
 
Quoted 7 lines

kernel/sched/core.c static void update_rq_clock_task(struct rq *rq, s64 delta) · line 775

Quoted 2 lines
kernel/sched/core.c +0 -0
              if (unlikely(steal > delta))
                      steal = delta;

So is the problem just the above if statement? That is, delta is already calculated, but if we get interrupted by the host before steal is calculated and the time then becomes greater than delta, the time difference between delta and steal gets pushed off to the next task, right?

Pretty much.. the steal being capped to delta means the rest of the steal is pushed off to the future. Instead he discards the remaining steal after this patch.

Thanks

Joel

#5 lore raw
Quoted 19 lines · On Tue, 19 Nov 2024 09:10:41 +0900 Joel Fernandes <[email protected]> wrote:
Quoted 11 lines
Quoted 11 lines

+++ b/kernel/sched/core.c

kernel/sched/core.c +3 -1
@@ -766,13 +766,15 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 #endif
 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
      if (static_key_false((&paravirt_steal_rq_enabled))) {
-             steal = paravirt_steal_clock(cpu_of(rq));
+             u64 prev_steal;
+
+             steal = prev_steal = paravirt_steal_clock(cpu_of(rq));
              steal -= rq->prev_steal_time_rq;
 
Quoted 7 lines

kernel/sched/core.c static void update_rq_clock_task(struct rq *rq, s64 delta) · line 775

Quoted 2 lines
kernel/sched/core.c +0 -0
              if (unlikely(steal > delta))
                      steal = delta;  

So is the problem just the above if statement? That is, delta is already calculated, but if we get interrupted by the host before steal is calculated and the time then becomes greater than delta, the time difference between delta and steal gets pushed off to the next task, right?

Quoted 3 lines

Pretty much.. the steal being capped to delta means the rest of the steal is pushed off to the future. Instead he discards the remaining steal after this patch.

Thanks for confirming. I just wanted to make sure I understand as the initial change log went into a lot of detail where I sorta got lost ;-)

-- Steve

#6 lore raw
Quoted 23 lines · Steven Rostedt
Quoted 19 lines · On Tue, 19 Nov 2024 09:10:41 +0900 Joel Fernandes <[email protected]> wrote:
Quoted 18 lines

kernel/sched/core.c static void update_rq_clock_task(struct rq *rq, s64 delta) · line 775

Quoted 13 lines

+++ b/kernel/sched/core.c

kernel/sched/core.c +3 -1
@@ -766,13 +766,15 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 #endif
 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
      if (static_key_false((&paravirt_steal_rq_enabled))) {
-             steal = paravirt_steal_clock(cpu_of(rq));
+             u64 prev_steal;
+
+             steal = prev_steal = paravirt_steal_clock(cpu_of(rq));
              steal -= rq->prev_steal_time_rq;
 
              if (unlikely(steal > delta))
                      steal = delta;

So is the problem just the above if statement? That is, delta is already calculated, but if we get interrupted by the host before steal is calculated and the time then becomes greater than delta, the time difference between delta and steal gets pushed off to the next task, right?

Quoted 6 lines
Quoted 3 lines

Pretty much.. the steal being capped to delta means the rest of the steal is pushed off to the future. Instead he discards the remaining steal after this patch.

Thanks for confirming. I just wanted to make sure I understand as the initial change log went into a lot of detail where I sorta got lost ;-)

No problem!! Glad we're on the same page about the change.

thanks,

- Joel

#7 lore raw
In reply to Suleiman Souhlal
The following commit has been merged into the sched/core branch of tip:

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     108ad0999085df2366dd9ef437573955cb3f5586
Gitweb:        https://git.kernel.org/tip/108ad0999085df2366dd9ef437573955cb3f5586
Author:        Suleiman Souhlal <[email protected]>
AuthorDate:    Mon, 18 Nov 2024 13:37:45 +09:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Mon, 02 Dec 2024 12:01:30 +01:00

sched: Don't try to catch up excess steal time.

When steal time exceeds the measured delta when updating clock_task, we currently try to catch up the excess in future updates. However, this results in inaccurate run times for the future things using clock_task, in some situations, as they end up getting additional steal time that did not actually happen.
This is because there is a window between reading the elapsed time in update_rq_clock() and sampling the steal time in update_rq_clock_task(). If the VCPU gets preempted between those two points, any additional steal time is accounted to the outgoing task even though the calculated delta did not actually contain any of that "stolen" time. When this race happens, we can end up with steal time that exceeds the calculated delta, and the previous code would try to catch up that excess steal time in future clock updates, which is given to the next, incoming task, even though it did not actually have any time stolen.

This behavior is particularly bad when steal time can be very long, which we've seen when trying to extend steal time to contain the duration that the host was suspended [0]. When this happens, clock_task stays frozen, during which the running task stays running for the whole duration, since its run time doesn't increase.
However the race can happen even under normal operation.

Ideally we would read the elapsed cpu time and the steal time atomically, to prevent this race from happening in the first place, but doing so is non-trivial.

Since the time between those two points isn't otherwise accounted anywhere, neither to the outgoing task nor the incoming task (because the "end of outgoing task" and "start of incoming task" timestamps are the same), I would argue that the right thing to do is to simply drop any excess steal time, in order to prevent these issues.

[0] https://lore.kernel.org/kvm/[email protected]/

---
 kernel/sched/core.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/core.c +4 -2
index c6d8232..4ffaef8 100644
@@ -766,13 +766,15 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 #endif
 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
 	if (static_key_false((&paravirt_steal_rq_enabled))) {
-		steal = paravirt_steal_clock(cpu_of(rq));
+		u64 prev_steal;
+
+		steal = prev_steal = paravirt_steal_clock(cpu_of(rq));
 		steal -= rq->prev_steal_time_rq;
 
 		if (unlikely(steal > delta))
 			steal = delta;
 
-		rq->prev_steal_time_rq += steal;
+		rq->prev_steal_time_rq = prev_steal;
 		delta -= steal;
 	}
 #endif