Introduce timekeeper latch synchronization
RFC PATCH 1/1 Introduce timekeeper latch synchronization
* Peter Zijlstra ([email protected]) wrote:
[...]
Quoted 6 lines
Yep, that's good. I suppose if there's multiple use sites we can jump through another few hoops to get rid of the specific struct foo assumptions by storing
sizeof()whatever we do use and playing pointer math games.But for now with the time stuff as only user this looks ok.
OK! Here is the full implementation of the idea against Linux timekeeper, ntp, and PPS. It appears that ntp and PPS were relying on the timekeeper seqlock too. And guess what, after booting my laptop with this kernel there still no smoke coming out of it after a good 5 minutes of testing. ;-)
Comments are welcome.
The patch applies on top of v3.11 + John Stultz's timekeeper fix "timekeeping: Fix HRTICK related deadlock from ntp lock changes"
No-way-I'm-signing-this-off-without-proper-testing
--- include/linux/timekeeper_internal.h | 161 ++++++++++ kernel/time/ntp.c | 544 ++++++++++++++++-------------------- kernel/time/ntp_internal.h | 16 - kernel/time/timekeeping.c | 359 +++++++++++++---------- 4 files changed, 621 insertions(+), 459 deletions(-)
include/linux/timekeeper_internal.h +161 -0
@@ -10,6 +10,85 @@#include <linux/jiffies.h> #include <linux/time.h> +#ifdef CONFIG_NTP_PPS +/* +* The following variables are used when a pulse-per-second (PPS) signal +* is available. They establish the engineering parameters of the clock +* discipline loop when controlled by the PPS signal. +*/ +struct timekeeper_pps { +int valid;/* signal watchdog counter */ +long tf[3 ];/* phase median filter */ +long jitter;/* current jitter (ns) */ +struct timespec fbase;/* beginning of the last freq interval */ +int shift;/* current interval duration (s) (shift) */ +int intcnt;/* interval counter */ +s64 freq;/* frequency offset (scaled ns/s) */ +long stabil;/* current stability (scaled ns/s) */ + +/* +* PPS signal quality monitors +*/ +long calcnt;/* calibration intervals */ +long jitcnt;/* jitter limit exceeded */ +long stbcnt;/* stability limit exceeded */ +long errcnt;/* calibration errors */ +}; +#else /* !CONFIG_NTP_PPS */ +struct timekeeper_pps { +}; +#endif /* !CONFIG_NTP_PPS */ + +/* structure holding internal NTP timekeeping values. */ +struct timekeeper_ntp { +/* USER_HZ period (usecs): */ +unsigned long tick_usec; + +/* SHIFTED_HZ period (nsecs): */ +unsigned long tick_nsec; + +u64 tick_length; +u64 tick_length_base; + +/* phase-lock loop variables */ + +/* +* clock synchronization status +* +* (TIME_ERROR prevents overwriting the CMOS clock) +*/ +int time_state; + +/* clock status bits: */ +int time_status; + +/* time adjustment (nsecs): */ +s64 time_offset; + +/* pll time constant: */ +long time_constant; + +/* maximum error (usecs): */ +long time_maxerror; + +/* estimated error (usecs): */ +long time_esterror; + +/* frequency offset (scaled nsecs/secs): */ +s64 time_freq; + +/* time at last adjustment (secs): */ +long time_reftime; + +long time_adjust; + +/* constant (boot-param configurable) NTP tick adjustment (upscaled) */ +s64 ntp_tick_adj; + +/* PPS variables */ +struct timekeeper_pps pps; +}; +/* Structure holding internal timekeeping values. */ struct timekeeper {/* Current clocksource used for timekeeping. */
@@ -69,8 +148,88 @@ struct timekeeper {/* Offset clock monotonic -> clock tai */ ktime_t offs_tai; +/* NTP variables */ +struct timekeeper_ntp ntp; }; +struct latch_timekeeper { +unsigned long head, tail; +struct timekeeper data[2 ]; +}; + +extern struct latch_timekeeper latch_timekeeper; +extern raw_spinlock_t timekeeper_lock; + +/** +* timekeeper_write_begin - begin timekeeper update. +* +" @lt: struct latch_timekeeper to update. +* @prev: pointer to previous element (output parameter). +* @next: pointer to next element (output parameter). +* +* The area pointed to by "next" should be considered uninitialized. +* The caller needs to have exclusive update access to struct latch_timekeeper. +*/ +static inline +void timekeeper_write_begin (struct latch_timekeeper *lt, +const struct timekeeper **prev, +struct timekeeper **next) +{ + lt->head++; +smp_wmb ();/* Store head before storing into next entry */ + *prev = <->data[lt->tail &1 ]; + *next = <->data[lt->head &1 ]; +} + +/** +* timekeeper_write_end - end timekeeper update. +* +" @lt: struct latch_timekeeper. +* +* The caller needs to have exclusive update access to struct latch_timekeeper. +*/ +static inline +void timekeeper_write_end (struct latch_timekeeper *lt) +{ +smp_wmb ();/* Store into next entry before storing into tail */ + lt->tail++; +} + +/** +* timekeeper_read_begin - begin timekeeper read. +* +" @lt: struct latch_timekeeper to read. +* @tail: pointer to unsigned long containing tail position (output). +*/ +static inline +struct timekeeper *timekeeper_read_begin (struct latch_timekeeper *lt, +unsigned long *tail) +{ +unsigned long ret; + + ret =ACCESS_ONCE (lt->tail); +smp_rmb ();/* Load tail before loading entry */ + *tail = ret; +return <->data[ret &1 ]; +} + +/** +* timekeeper_read_retry - end timekeeper read, trigger retry if needed. +* +" @lt: struct latch_timekeeper read. +* @tail: tail position returned as output by timekeeper_read_begin(). +* +* If timekeeper_read_retry() returns nonzero, the content of the read should +* be considered invalid, and the read should be performed again to +* reattempt reading coherent data, starting with timekeeper_read_begin(). +*/ +static inline +int timekeeper_read_retry (struct latch_timekeeper *lt,unsigned long tail) +{ +smp_rmb ();/* Load entry before loading head */ +return (ACCESS_ONCE (lt->head) - tail >=2 ); +} +static inline struct timespec tk_xtime (struct timekeeper *tk) {struct timespec ts;
@@ -110,4 +269,6 @@ static inline void update_vsyscall_tz(void) }#endif +extern struct timekeeper *timekeeper_get_init (void ); +#endif /* _LINUX_TIMEKEEPER_INTERNAL_H */
kernel/time/ntp.c +245 -299
994 lines not on this page · raw message
kernel/time/ntp_internal.h +10 -6
@@ -1,12 +1,16 @@#ifndef _LINUX_NTP_INTERNAL_H#define _LINUX_NTP_INTERNAL_H -extern void ntp_init (void ); -extern void ntp_clear (void ); +struct timekeeper_ntp ; + +extern void ntp_init (struct timekeeper_ntp *ntp); +extern void ntp_clear (struct timekeeper_ntp *ntp);/* Returns how long ticks are at present, in ns / 2^NTP_SCALE_SHIFT. */ -extern u64 ntp_tick_length (void ); -extern int second_overflow (unsigned long secs); +extern u64 ntp_tick_length (struct timekeeper_ntp *ntp); +extern int second_overflow (struct timekeeper_ntp *ntp,unsigned long secs);extern int ntp_validate_timex (struct timex *); -extern int __do_adjtimex (struct timex *,struct timespec *,s32 *); -extern void __hardpps (const struct timespec *,const struct timespec *); +extern int __do_adjtimex (struct timekeeper_ntp *ntp,struct timex *, +struct timespec *,s32 *); +extern void __hardpps (struct timekeeper_ntp *ntp,const struct timespec *, +const struct timespec *);#endif /* _LINUX_NTP_INTERNAL_H */
kernel/time/timekeeping.c +205 -154
847 lines not on this page · raw message
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 7 lines · Mathieu Desnoyers
OK! Here is the full implementation of the idea against Linux timekeeper, ntp, and PPS. It appears that ntp and PPS were relying on the timekeeper seqlock too. And guess what, after booting my laptop with this kernel there still no smoke coming out of it after a good 5 minutes of testing. ;-)
Comments are welcome.
I think that moving stuff into structures is a worthwhile change on its own, but I'll leave John and Thomas to decide on all that.
The latch thing does make the update side slightly more expensive due to having to do that copy every time, but ideally that wouldn't happen all that often.
* Mathieu Desnoyers ([email protected]) wrote:
[...]
Quoted 3 lines
kernel/time/timekeeping.c +0
-0@@ -1362,29 +1398,31 @@ static inline void old_vsyscall_fixup(struct timekeeper *tk)static void update_wall_time (void ) {
[...]
kernel/time/timekeeping.c static void update_wall_time(void) · line 1438
Quoted 12 lines
kernel/time/timekeeping.c +0
-12-/* -* Update the real timekeeper. -* -* We could avoid this memcpy by switching pointers, but that -* requires changes to all other timekeeper usage sites as -* well, i.e. move the timekeeper pointer getter into the -* spinlocked/seqcount protected sections. And we trade this -* memcpy under the timekeeper_seq against one before we start -* updating. -*/ -memcpy (real_tk, tk,sizeof (*tk)); -timekeeping_update (real_tk, action);
This line above appears to be important ;-) Let's see if my screensaver stops misbehaving if I put it back. I will of course send a v2 after some more testing.
By the way, if there are some standard test-bench for timekeeping, I'd be very interested to hear about them.
Thanks!
Mathieu
Quoted 5 lines
kernel/time/timekeeping.c +1
-1-write_seqcount_end (&timekeeper_seq); out: +timekeeper_write_end (&latch_timekeeper);raw_spin_unlock_irqrestore (&timekeeper_lock, flags); }
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 2 lines · Mathieu Desnoyers
By the way, if there are some standard test-bench for timekeeping, I'd be very interested to hear about them.
I've got a git repo of tests that I use for basic sanity checks here:
https://github.com/johnstultz-work/timetests.git
thanks
-john
Quoted 5 lines · * John Stultz ([email protected]) wrote:
Quoted 2 lines · Mathieu Desnoyers
By the way, if there are some standard test-bench for timekeeping, I'd be very interested to hear about them.
I've got a git repo of tests that I use for basic sanity checks here:
https://github.com/johnstultz-work/timetests.git
Thanks for the pointer! It looks like I'm currently breaking CLOCK_MONOTONIC_RAW. My thoughts are that struct clocksource read vs updates are relying on the timekeeper seqlock for synchronization. Therefore, I might have to apply the latch scheme to struct clocksource too.
Thoughts ?
Thanks,
Mathieu
Quoted 4 lines
thanks
-john
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 9 lines · Mathieu Desnoyers
* Peter Zijlstra ([email protected]) wrote:
[...]Quoted 6 lines
Yep, that's good. I suppose if there's multiple use sites we can jump through another few hoops to get rid of the specific struct foo assumptions by storing
sizeof()whatever we do use and playing pointer math games.But for now with the time stuff as only user this looks ok.
Quoted 7 lines
OK! Here is the full implementation of the idea against Linux timekeeper, ntp, and PPS. It appears that ntp and PPS were relying on the timekeeper seqlock too. And guess what, after booting my laptop with this kernel there still no smoke coming out of it after a good 5 minutes of testing. ;-)
Comments are welcome.
First of all this needs to be split into several patches.
Quoted 1 line
static void
update_wall_time(void)
...
Quoted 5 lines
kernel/time/timekeeping.c +0
-3-write_seqcount_begin (&timekeeper_seq);/* Update clock->cycle_last with the new value */ clock->cycle_last = tk->cycle_last; -/* -* Update the real timekeeper.
kernel/time/timekeeping.c static void update_wall_time(void) · line 1438
Quoted 10 lines
kernel/time/timekeeping.c +0
-10-* -* We could avoid this memcpy by switching pointers, but that -* requires changes to all other timekeeper usage sites as -* well, i.e. move the timekeeper pointer getter into the -* spinlocked/seqcount protected sections. And we trade this -* memcpy under the timekeeper_seq against one before we start -* updating. -*/ -memcpy (real_tk, tk,sizeof (*tk)); -timekeeping_update (real_tk, action);
So you're dropping the timekeeping_update() call here. I wonder how this works.
Review
Quoted 2 lines
(quoted diff) +2
-0+ timekeeper_write_begin(&latch_timekeeper, &prev, &tk); + *tk = *prev;
Do we really need to do the copy on all call sites, instead of doing it in timekeeper_write_begin() ?
Thanks,
tglx
Quoted 9 lines · Thomas Gleixner
Quoted 8 lines · Mathieu Desnoyers
* Peter Zijlstra ([email protected]) wrote:
[...]Quoted 6 lines
Yep, that's good. I suppose if there's multiple use sites we can jump through another few hoops to get rid of the specific struct foo assumptions by storing
sizeof()whatever we do use and playing pointer math games.But for now with the time stuff as only user this looks ok.
Quoted 8 lines
Quoted 7 lines
OK! Here is the full implementation of the idea against Linux timekeeper, ntp, and PPS. It appears that ntp and PPS were relying on the timekeeper seqlock too. And guess what, after booting my laptop with this kernel there still no smoke coming out of it after a good 5 minutes of testing. ;-)
Comments are welcome.
First of all this needs to be split into several patches.
How about:
- three patches refactoring data structures into objects (no synchronization changes whatsoever). timekeeper, ntp and pps each done in separate patches,
- one patch to introduce the new synchronization scheme along with the usage site changes. This patch would include the removal of the shadow_timekeeper variable, which is made pointless by the introduction of this mixed-rcu-seqcount synchronization scheme.
is that enough, or you see a more fine-grained breakdown ?
Quoted 12 lines
Quoted 2 lines
static void
update_wall_time(void)...
Quoted 9 lines
kernel/time/timekeeping.c +0
-7-write_seqcount_begin (&timekeeper_seq);/* Update clock->cycle_last with the new value */ clock->cycle_last = tk->cycle_last; -/* -* Update the real timekeeper. -* -* We could avoid this memcpy by switching pointers, but that -* requires changes to all other timekeeper usage sites as -* well, i.e. move the timekeeper pointer getter into the
Quoted 8 lines
kernel/time/timekeeping.c static void update_wall_time(void) · line 1438
Quoted 6 lines
kernel/time/timekeeping.c +0
-6-* spinlocked/seqcount protected sections. And we trade this -* memcpy under the timekeeper_seq against one before we start -* updating. -*/ -memcpy (real_tk, tk,sizeof (*tk)); -timekeeping_update (real_tk, action);So you're dropping the
timekeeping_update()call here. I wonder how this works.
It doesn't :-)
There appears to be a couple of side-effects related to removal of the call to timekeeping_update(). On the positive side, I now have much more free time on my hands. However, people seem to complain that I arrive late to meetings for some reasons ;-)
Quoted 5 lines
Review
Quoted 3 lines
(quoted diff) +2
-0+ timekeeper_write_begin(&latch_timekeeper, &prev, &tk); + *tk = *prev;Do we really need to do the copy on all call sites, instead of doing it in
timekeeper_write_begin()?
Since we're indeed doing the copy on all call sites, I think it would be good to move it into timekeeper_write_begin() as you suggest.
Initially, I kept the copy in the caller in case we could do without the copy in some cases (in case the caller would overwrite the entire structure without caring about prior content). But since we need to copy timekeeper, ntp and pps structures, I doubt this is realistic. So let's move this copy into timekeeper_write_begin().
Thanks !
Mathieu
Quoted 4 lines
Thanks,
tglx
Quoted 27 lines · Mathieu Desnoyers
Quoted 9 lines · Thomas Gleixner
Quoted 8 lines · Mathieu Desnoyers
* Peter Zijlstra ([email protected]) wrote:
[...]Quoted 6 lines
Yep, that's good. I suppose if there's multiple use sites we can jump through another few hoops to get rid of the specific struct foo assumptions by storing
sizeof()whatever we do use and playing pointer math games.But for now with the time stuff as only user this looks ok.
Quoted 8 lines
Quoted 7 lines
OK! Here is the full implementation of the idea against Linux timekeeper, ntp, and PPS. It appears that ntp and PPS were relying on the timekeeper seqlock too. And guess what, after booting my laptop with this kernel there still no smoke coming out of it after a good 5 minutes of testing. ;-)
Comments are welcome.
First of all this needs to be split into several patches.
How about:
- three patches refactoring data structures into objects (no synchronization changes whatsoever). timekeeper, ntp and pps each done in separate patches,
- one patch to introduce the new synchronization scheme along with the usage site changes. This patch would include the removal of theshadow_timekeepervariable, which is made pointless by the introduction of this mixed-rcu-seqcount synchronization scheme.
Quoted 1 line
is that enough, or you see a more fine-grained breakdown ?
I think that would be a good start (btw, sorry, doing some prep for Plumbers next week, and haven't had a chance to do a detailed review of the design here - when I asked for ideas I didn't expect folks to start sending code the next day! ;).
Another thing to consider to possibly avoid the extra costs that Peter mentioned is partitioning the timekeeper structure up a little bit as well, as there are some values that are basically only used at update time vs the values we use at read time. I suspect we can trim down the amount of duplicated data. This is similar to what we do w/ vdso update.
For instance, to read the time we probably need:
The base calculation for CLOCK_REALTIME:
struct clocksource *clock;
u32 mult;
u32 shift;
cycle_t cycle_last;
u64 xtime_sec;
u64 xtime_nsec;Along with the various offsets from CLOCK_REALTIME:
struct timespec wall_to_monotonic;
ktime_t offs_real;
struct timespec total_sleep_time;
ktime_t offs_boot;
s32 tai_offset;
ktime_t offs_tai;
struct timespec raw_time;Can be separate from the internal accounting details used at update time to adjust the above:
cycle_t cycle_interval;
u64 xtime_interval;
s64 xtime_remainder;
u32 raw_interval;
s64 ntp_error;
u32 ntp_error_shift;thanks
-john
Quoted 60 lines · * John Stultz ([email protected]) wrote:
Quoted 27 lines · Mathieu Desnoyers
Quoted 9 lines · Thomas Gleixner
Quoted 8 lines · Mathieu Desnoyers
* Peter Zijlstra ([email protected]) wrote:
[...]Quoted 6 lines
Yep, that's good. I suppose if there's multiple use sites we can jump through another few hoops to get rid of the specific struct foo assumptions by storing
sizeof()whatever we do use and playing pointer math games.But for now with the time stuff as only user this looks ok.
Quoted 8 lines
Quoted 7 lines
OK! Here is the full implementation of the idea against Linux timekeeper, ntp, and PPS. It appears that ntp and PPS were relying on the timekeeper seqlock too. And guess what, after booting my laptop with this kernel there still no smoke coming out of it after a good 5 minutes of testing. ;-)
Comments are welcome.
First of all this needs to be split into several patches.
How about:
- three patches refactoring data structures into objects (no synchronization changes whatsoever). timekeeper, ntp and pps each done in separate patches,
- one patch to introduce the new synchronization scheme along with the usage site changes. This patch would include the removal of theshadow_timekeepervariable, which is made pointless by the introduction of this mixed-rcu-seqcount synchronization scheme.Quoted 1 line
is that enough, or you see a more fine-grained breakdown ?
I think that would be a good start (btw, sorry, doing some prep for Plumbers next week, and haven't had a chance to do a detailed review of the design here - when I asked for ideas I didn't expect folks to start sending code the next day! ;).
Another thing to consider to possibly avoid the extra costs that Peter mentioned is partitioning the timekeeper structure up a little bit as well, as there are some values that are basically only used at update time vs the values we use at read time. I suspect we can trim down the amount of duplicated data. This is similar to what we do w/ vdso update.
For instance, to read the time we probably need:
The base calculation for
CLOCK_REALTIME:struct clocksource *clock; u32 mult; u32 shift; cycle_t cycle_last; u64 xtime_sec; u64 xtime_nsec;Along with the various offsets from
CLOCK_REALTIME:struct timespec wall_to_monotonic; ktime_t offs_real; struct timespec total_sleep_time; ktime_t offs_boot; s32 tai_offset; ktime_t offs_tai; struct timespec raw_time;
Quoted 8 lines
Can be separate from the internal accounting details used at update time to adjust the above:
cycle_t cycle_interval; u64 xtime_interval; s64 xtime_remainder; u32 raw_interval; s64 ntp_error; u32 ntp_error_shift;
This looks to me like interesting optimisation work that should be considered after the following question is answered: does the added update-side cost actually matter that much ?
Thanks,
Mathieu
Quoted 4 lines
thanks
-john
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 4 lines · Mathieu Desnoyers
This looks to me like interesting optimisation work that should be considered after the following question is answered: does the added update-side cost actually matter that much ?
Yea, fair enough. We can measure the cost first.
thanks
-john