Add a global synchronization point for pvclock
in [Kernel]
|
Prev: Sound not transferred to docking station after resume from StR
Next: Process-shared futexes on hugepages puts the kernel in an infinite loop in 2.6.32.11; is this fixed now?
From: Marcelo Tosatti on 16 Apr 2010 16:30 On Thu, Apr 15, 2010 at 02:37:24PM -0400, Glauber Costa wrote: > In recent stress tests, it was found that pvclock-based systems > could seriously warp in smp systems. Using ingo's time-warp-test.c, > I could trigger a scenario as bad as 1.5mi warps a minute in some systems. > (to be fair, it wasn't that bad in most of them). Investigating further, I > found out that such warps were caused by the very offset-based calculation > pvclock is based on. > > This happens even on some machines that report constant_tsc in its tsc flags, > specially on multi-socket ones. > > Two reads of the same kernel timestamp at approx the same time, will likely > have tsc timestamped in different occasions too. This means the delta we > calculate is unpredictable at best, and can probably be smaller in a cpu > that is legitimately reading clock in a forward ocasion. > > Some adjustments on the host could make this window less likely to happen, > but still, it pretty much poses as an intrinsic problem of the mechanism. > > A while ago, I though about using a shared variable anyway, to hold clock > last state, but gave up due to the high contention locking was likely > to introduce, possibly rendering the thing useless on big machines. I argue, > however, that locking is not necessary. > > We do a read-and-return sequence in pvclock, and between read and return, > the global value can have changed. However, it can only have changed > by means of an addition of a positive value. So if we detected that our > clock timestamp is less than the current global, we know that we need to > return a higher one, even though it is not exactly the one we compared to. > > OTOH, if we detect we're greater than the current time source, we atomically > replace the value with our new readings. This do causes contention on big > boxes (but big here means *BIG*), but it seems like a good trade off, since > it provide us with a time source guaranteed to be stable wrt time warps. > > After this patch is applied, I don't see a single warp in time during 5 days > of execution, in any of the machines I saw them before. > > Signed-off-by: Glauber Costa <glommer(a)redhat.com> > CC: Jeremy Fitzhardinge <jeremy(a)goop.org> > CC: Avi Kivity <avi(a)redhat.com> > CC: Marcelo Tosatti <mtosatti(a)redhat.com> > CC: Zachary Amsden <zamsden(a)redhat.com> > --- > arch/x86/kernel/pvclock.c | 23 +++++++++++++++++++++++ > 1 files changed, 23 insertions(+), 0 deletions(-) > > diff --git a/arch/x86/kernel/pvclock.c b/arch/x86/kernel/pvclock.c > index 03801f2..b7de0e6 100644 > --- a/arch/x86/kernel/pvclock.c > +++ b/arch/x86/kernel/pvclock.c > @@ -109,11 +109,14 @@ unsigned long pvclock_tsc_khz(struct pvclock_vcpu_time_info *src) > return pv_tsc_khz; > } > > +static u64 last_value = 0; > + __cacheline_aligned_in_smp to avoid other data from sharing the cacheline. > cycle_t pvclock_clocksource_read(struct pvclock_vcpu_time_info *src) > { > struct pvclock_shadow_time shadow; > unsigned version; > cycle_t ret, offset; > + u64 last; > > do { > version = pvclock_get_time_values(&shadow, src); > @@ -123,6 +126,26 @@ cycle_t pvclock_clocksource_read(struct pvclock_vcpu_time_info *src) > barrier(); > } while (version != src->version); > > + /* > + * Assumption here is that last_value, a global accumulator, always goes > + * forward. If we are less than that, we should not be much smaller. > + * We assume there is an error marging we're inside, and then the correction > + * does not sacrifice accuracy. > + * > + * For reads: global may have changed between test and return, > + * but this means someone else updated poked the clock at a later time. > + * We just need to make sure we are not seeing a backwards event. > + * > + * For updates: last_value = ret is not enough, since two vcpus could be > + * updating at the same time, and one of them could be slightly behind, > + * making the assumption that last_value always go forward fail to hold. > + */ > + do { > + last = last_value; > + if (ret < last) > + return last; > + } while (unlikely(cmpxchg64(&last_value, last, ret) != ret)); > + Don't you need to handle wrap-around? -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Jeremy Fitzhardinge on 16 Apr 2010 16:40 On 04/15/2010 11:37 AM, Glauber Costa wrote: > In recent stress tests, it was found that pvclock-based systems > could seriously warp in smp systems. Using ingo's time-warp-test.c, > I could trigger a scenario as bad as 1.5mi warps a minute in some systems. > Is that "1.5 million"? > (to be fair, it wasn't that bad in most of them). Investigating further, I > found out that such warps were caused by the very offset-based calculation > pvclock is based on. > Is the problem that the tscs are starting out of sync, or that they're drifting relative to each other over time? Do the problems become worse the longer the uptime? How large are the offsets we're talking about here? > This happens even on some machines that report constant_tsc in its tsc flags, > specially on multi-socket ones. > > Two reads of the same kernel timestamp at approx the same time, will likely > have tsc timestamped in different occasions too. This means the delta we > calculate is unpredictable at best, and can probably be smaller in a cpu > that is legitimately reading clock in a forward ocasion. > > Some adjustments on the host could make this window less likely to happen, > but still, it pretty much poses as an intrinsic problem of the mechanism. > > A while ago, I though about using a shared variable anyway, to hold clock > last state, but gave up due to the high contention locking was likely > to introduce, possibly rendering the thing useless on big machines. I argue, > however, that locking is not necessary. > > We do a read-and-return sequence in pvclock, and between read and return, > the global value can have changed. However, it can only have changed > by means of an addition of a positive value. So if we detected that our > clock timestamp is less than the current global, we know that we need to > return a higher one, even though it is not exactly the one we compared to. > > OTOH, if we detect we're greater than the current time source, we atomically > replace the value with our new readings. This do causes contention on big > boxes (but big here means *BIG*), but it seems like a good trade off, since > it provide us with a time source guaranteed to be stable wrt time warps. > > After this patch is applied, I don't see a single warp in time during 5 days > of execution, in any of the machines I saw them before. > > Signed-off-by: Glauber Costa <glommer(a)redhat.com> > CC: Jeremy Fitzhardinge <jeremy(a)goop.org> > CC: Avi Kivity <avi(a)redhat.com> > CC: Marcelo Tosatti <mtosatti(a)redhat.com> > CC: Zachary Amsden <zamsden(a)redhat.com> > --- > arch/x86/kernel/pvclock.c | 23 +++++++++++++++++++++++ > 1 files changed, 23 insertions(+), 0 deletions(-) > > diff --git a/arch/x86/kernel/pvclock.c b/arch/x86/kernel/pvclock.c > index 03801f2..b7de0e6 100644 > --- a/arch/x86/kernel/pvclock.c > +++ b/arch/x86/kernel/pvclock.c > @@ -109,11 +109,14 @@ unsigned long pvclock_tsc_khz(struct pvclock_vcpu_time_info *src) > return pv_tsc_khz; > } > > +static u64 last_value = 0; > + > cycle_t pvclock_clocksource_read(struct pvclock_vcpu_time_info *src) > { > struct pvclock_shadow_time shadow; > unsigned version; > cycle_t ret, offset; > + u64 last; > > do { > version = pvclock_get_time_values(&shadow, src); > @@ -123,6 +126,26 @@ cycle_t pvclock_clocksource_read(struct pvclock_vcpu_time_info *src) > barrier(); > } while (version != src->version); > > + /* > + * Assumption here is that last_value, a global accumulator, always goes > + * forward. If we are less than that, we should not be much smaller. > + * We assume there is an error marging we're inside, and then the correction > + * does not sacrifice accuracy. > + * > + * For reads: global may have changed between test and return, > + * but this means someone else updated poked the clock at a later time. > + * We just need to make sure we are not seeing a backwards event. > + * > + * For updates: last_value = ret is not enough, since two vcpus could be > + * updating at the same time, and one of them could be slightly behind, > + * making the assumption that last_value always go forward fail to hold. > + */ > + do { > + last = last_value; > Does this need a barrier() to prevent the compiler from re-reading last_value for the subsequent lines? Otherwise "(ret < last)" and "return last" could execute with different values for "last". > + if (ret < last) > + return last; > + } while (unlikely(cmpxchg64(&last_value, last, ret) != ret)); > So if CPU A's tsc is, say, 50us behind CPU B's, then it will return a static time (from last_time) for 50us until its tsc catched up - or if CPU A happens to update last_time to give it a kick? Is it worth trying to update CPU A's tsc offset at the same time? J -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Zachary Amsden on 16 Apr 2010 17:10 On 04/16/2010 10:36 AM, Jeremy Fitzhardinge wrote: > On 04/15/2010 11:37 AM, Glauber Costa wrote: > >> In recent stress tests, it was found that pvclock-based systems >> could seriously warp in smp systems. Using ingo's time-warp-test.c, >> I could trigger a scenario as bad as 1.5mi warps a minute in some systems. >> >> > Is that "1.5 million"? > > >> (to be fair, it wasn't that bad in most of them). Investigating further, I >> found out that such warps were caused by the very offset-based calculation >> pvclock is based on. >> >> > Is the problem that the tscs are starting out of sync, or that they're > drifting relative to each other over time? Do the problems become worse > the longer the uptime? How large are the offsets we're talking about here? > This is one source of the problem, but the same thing happens at many levels... tsc may start out of sync, drift between sockets, be badly re-calibrated by the BIOS, etc... the issue persists even if the TSCs are perfectly in sync - the measurement of them is not. So reading TSC == 100,000 units at time A and then waiting 10 units, one may read TSC == 100,010 +/- 5 units because the code stream is not perfectly serialized - nor can it be. There will always be some amount of error unless running in perfect lock-step, which only happens in a simulator. This inherent measurement error can cause apparent time to go backwards when measured simultaneously across multiple CPUs, or when re-calibrating against an external clocksource. Combined with other factors as above, it can be of sufficient magnitude to be noticed. KVM clock is particularly exposed to the problem because the TSC is measured and recalibrated for each virtual CPU whenever there is a physical CPU switch, so micro-adjustments forwards and backwards may occur during the recalibration - and appear as a real backwards time warp to the guest. I have some patches to fix that issue, but the SMP problem remains to be fixed - and is addressed quite thoroughly by this patch. Zach -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Avi Kivity on 17 Apr 2010 14:50 On 04/15/2010 09:37 PM, Glauber Costa wrote: > In recent stress tests, it was found that pvclock-based systems > could seriously warp in smp systems. Using ingo's time-warp-test.c, > I could trigger a scenario as bad as 1.5mi warps a minute in some systems. > (to be fair, it wasn't that bad in most of them). Investigating further, I > found out that such warps were caused by the very offset-based calculation > pvclock is based on. > > This happens even on some machines that report constant_tsc in its tsc flags, > specially on multi-socket ones. > > Two reads of the same kernel timestamp at approx the same time, will likely > have tsc timestamped in different occasions too. This means the delta we > calculate is unpredictable at best, and can probably be smaller in a cpu > that is legitimately reading clock in a forward ocasion. > > Some adjustments on the host could make this window less likely to happen, > but still, it pretty much poses as an intrinsic problem of the mechanism. > > A while ago, I though about using a shared variable anyway, to hold clock > last state, but gave up due to the high contention locking was likely > to introduce, possibly rendering the thing useless on big machines. I argue, > however, that locking is not necessary. > > We do a read-and-return sequence in pvclock, and between read and return, > the global value can have changed. However, it can only have changed > by means of an addition of a positive value. So if we detected that our > clock timestamp is less than the current global, we know that we need to > return a higher one, even though it is not exactly the one we compared to. > > OTOH, if we detect we're greater than the current time source, we atomically > replace the value with our new readings. This do causes contention on big > boxes (but big here means *BIG*), but it seems like a good trade off, since > it provide us with a time source guaranteed to be stable wrt time warps. > > After this patch is applied, I don't see a single warp in time during 5 days > of execution, in any of the machines I saw them before. > > Please define a cpuid bit that makes this optional. When we eventually enable it in the future, it will allow a wider range of guests to enjoy it. > > +static u64 last_value = 0; > Needs to be atomic64_t. > + > cycle_t pvclock_clocksource_read(struct pvclock_vcpu_time_info *src) > { > struct pvclock_shadow_time shadow; > unsigned version; > cycle_t ret, offset; > + u64 last; > > > + do { > + last = last_value; > Otherwise, this assignment can see a partial update. > + if (ret< last) > + return last; > + } while (unlikely(cmpxchg64(&last_value, last, ret) != ret)); > + > return ret; > } > > -- Do not meddle in the internals of kernels, for they are subtle and quick to panic. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Avi Kivity on 17 Apr 2010 15:00
On 04/17/2010 09:48 PM, Avi Kivity wrote: > >> >> +static u64 last_value = 0; > > Needs to be atomic64_t. > >> + >> cycle_t pvclock_clocksource_read(struct pvclock_vcpu_time_info *src) >> { >> struct pvclock_shadow_time shadow; >> unsigned version; >> cycle_t ret, offset; >> + u64 last; >> >> >> + do { >> + last = last_value; > > Otherwise, this assignment can see a partial update. On a 32-bit guest, that is. -- Do not meddle in the internals of kernels, for they are subtle and quick to panic. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |