Line data Source code
1 : #include "fd_clock.h"
2 :
3 : /* Let x denote x-clock observations, y denote y-clock observations and
4 : y_est denote estimates of the y-clock from the x-clock. During a
5 : clock epoch, we use a linear approximation for y_est:
6 :
7 : y_est(now) = y_eff(epoch_start) + m(epoch)*( x(now) - x(epoch_start) )
8 :
9 : Given a short enough epoch, the jointly observed values of x-clock
10 : and y-clock at the epoch start and stop are well approximated as
11 : linearly related:
12 :
13 : x_actual(epoch_end) ~ x_actual(epoch_start) + w_actual(epoch)( y_actual(epoch_end) - y_actual(epoch_start) )
14 :
15 : where w_actual gives the x-tick per y-tick rate between the clocks
16 : during the epoch. Unfortunately, we can't jointly observe the two
17 : clocks infinitely precisely. We assume that:
18 :
19 : x_actual(sample) = x_obs(sample) + delta_x(sample)
20 : y_actual(sample) = y_obs(sample)
21 :
22 : where delta_x(sample) represent the effects of quantization error
23 : (due to finite x-tick size) and synchronization error (due to not
24 : observing x_obs(sample) at the exact time the y_obs(sample) was
25 : observed on the y-clock). That is, we assume:
26 :
27 : x_obs(epoch_end) + delta_x(epoch_end) = x_obs(epoch_start) + delta_x(epoch_start)
28 : + w_actual(epoch)( y_obs(epoch_end) - y_obs(epoch_start) )
29 :
30 : Then w_actual(epoch) = w_obs(epoch) + delta_w(epoch) where:
31 :
32 : x_obs(epoch_end) - x_obs(epoch_start)
33 : w_obs(epoch) = -------------------------------------
34 : y_obs(epoch_end) - y_obs(epoch_start)
35 :
36 : and:
37 :
38 : delta_x(epoch_end) - delta_x(epoch_start)
39 : delta_w(epoch) = -----------------------------------------
40 : y_obs(epoch_end) - y_obs(epoch_start)
41 :
42 : Assuming, quite reasonably, delta_x(sample) all have the same mean
43 : (or, even stronger but still reasonable, are IID), w_obs(epoch) is an
44 : unbiased estimate of w_actual(epoch).
45 :
46 : Since we expect w_actual(epoch) to be nearly constant from epoch to
47 : epoch (i.e. these are clocks), we can use a decaying average filter
48 : to compute an estimate of w(next_epoch) given an estimate for this
49 : epoch w_est(epoch) and w_obs(epoch):
50 :
51 : w_est(next_epoch) = w_est(epoch) + alpha ( w_obs(epoch) - w_est(epoch) )
52 :
53 : Here:
54 :
55 : alpha = 1 / (1 + hist)
56 :
57 : is in [0,1] and hist is non-negative. hist can be thought of as the
58 : number of previous observations to include in the w_est(next_epoch).
59 :
60 : If w_actual is strictly constant from epoch to epoch,
61 : w_est(next_epoch) is an unbiased estimate of w_actual assuming
62 : w_est(epoch) is also an unbiased estimate.
63 :
64 : In practice, we expect w_actual(epoch) to slowly vary from epoch to
65 : epoch. The more epochs we include in the average (i.e. the larger
66 : hist), the more accurate w_est(epoch) will be but the less quickly
67 : w_est(epoch) will adapt to changes in w_actual(epoch).
68 :
69 : Given a reasonably accurate w_est(next_epoch), we want to create a
70 : relationship between the x-clock and y-clock that preserves
71 : monotonicity of y_est from epoch to epoch while having no asymptotic
72 : clock drift between y_est and y_obs.
73 :
74 : To that end, if y_est(epoch_end) is less than or equal to
75 : y_obs(epoch_end), we can correct for all accumulated clock drift
76 : immediately without breaking monotonicity by simply forward stepping
77 : y_eff(next_epoch_start) to y_obs(epoch_end) and using
78 : 1/w_est(next_epoch) directly for m(next_epoch):
79 :
80 : y_eff(next_epoch_start) = y_obs(epoch_end)
81 : m(next_epoch) = 1 / w_est(next_epoch)
82 :
83 : Unfortunately, this can break monotonicity when y_est(epoch_end) is
84 : greater than y_obs(epoch_end). In this case, let frac be the
85 : fraction of this clock drift we want to absorb during the next epoch.
86 : If we know the next clock epoch will be at most epoch_max y-ticks
87 : long, we can reduce m(next_epoch) to absorb the drift:
88 :
89 : y_eff(next_epoch_start) = y_est(epoch_end)
90 :
91 : 1 - beta ( y_est(epoch_end) - y_obs(epoch_end) )
92 : m(next_epoch) = ------------------------------------------------
93 : w_est(next_epoch)
94 :
95 : where:
96 :
97 : beta = frac / epoch_max
98 :
99 : To insure m(next_epoch) is always positive (and thus preserve
100 : monotonicity), we tweak the above into:
101 :
102 : 1
103 : m(next_epoch) = --------------------------------------------------------------------
104 : w_est(next_epoch) ( 1 + beta ( y_est(epoch_end) - y_obs(epoch_end) )
105 :
106 : This is asymptotically identical to the above in the (common case)
107 : limit:
108 :
109 : beta (y_est-y_obs) << 1.
110 :
111 : and asymptotes to zero when:
112 :
113 : beta (y_est-y_obs) >> 1.
114 :
115 : These all be combined into a branchless implementation via:
116 :
117 : x_obs(epoch_end) - x_obs(epoch_start)
118 : w_obs(epoch) = -------------------------------------
119 : y_obs(epoch_end) - y_obs(epoch_start)
120 :
121 : w_est(next_epoch) = w_est(epoch) + alpha ( w_obs(epoch) - w_est(epoch) )
122 :
123 : y_est(epoch_end) = y_eff(epoch_start) + m(epoch) ( x_obs(epoch_end) - x_obs(epoch_start) )
124 :
125 : y_eff(next_epoch_start) = max( y_obs(epoch_end), y_est(epoch_end) )
126 :
127 : 1
128 : m(next_epoch) = ---------------------------------------------------------------------------
129 : w_est(next_epoch) ( 1 + beta ( y_eff(next_epoch_start) - y_obs(epoch_end) )
130 :
131 : This is the basic recalibration update used below. */
132 :
133 : ulong
134 192 : fd_clock_align( void ) {
135 192 : return alignof( fd_clock_shmem_t );
136 192 : }
137 :
138 : ulong
139 72 : fd_clock_footprint( void ) {
140 72 : return sizeof( fd_clock_shmem_t );
141 72 : }
142 :
143 : void *
144 : fd_clock_new( void * shmem,
145 : long recal_avg,
146 : long recal_jit,
147 : double recal_hist,
148 : double recal_frac,
149 : long init_x0,
150 : long init_y0,
151 99 : double init_w ) {
152 99 : fd_clock_shmem_t * shclock = (fd_clock_shmem_t *)shmem;
153 :
154 99 : if( FD_UNLIKELY( !recal_jit ) ) recal_jit = (recal_avg>>7) + (long)!!(recal_avg & 127L); /* ceil( recal_avg / 128 ) */
155 99 : if( FD_UNLIKELY( recal_hist==0. ) ) recal_hist = 3.;
156 99 : if( FD_UNLIKELY( recal_frac==0. ) ) recal_frac = 1.;
157 :
158 99 : if( FD_UNLIKELY( !shclock ) ) {
159 3 : FD_LOG_WARNING(( "NULL shmem" ));
160 3 : return NULL;
161 3 : }
162 :
163 96 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shclock, fd_clock_align() ) ) ) {
164 3 : FD_LOG_WARNING(( "misaligned shmem" ));
165 3 : return NULL;
166 3 : }
167 :
168 93 : if( FD_UNLIKELY( !((1L<=recal_jit) && (recal_jit<=recal_avg) && (recal_avg<=(LONG_MAX-recal_jit))) ) ) {
169 12 : FD_LOG_WARNING(( "bad recal_avg / recal_jit" ));
170 12 : return NULL;
171 12 : }
172 :
173 81 : if( FD_UNLIKELY( !(recal_hist>0.) ) ) {
174 3 : FD_LOG_WARNING(( "bad recal_hist" ));
175 3 : return NULL;
176 3 : }
177 :
178 78 : if( FD_UNLIKELY( !(recal_frac>0.) ) ) {
179 3 : FD_LOG_WARNING(( "bad recal_frac" ));
180 3 : return NULL;
181 3 : }
182 :
183 75 : if( FD_UNLIKELY( !(init_w>0.) ) ) {
184 3 : FD_LOG_WARNING(( "bad w" ));
185 3 : return NULL;
186 3 : }
187 72 : double init_m = 1./init_w;
188 72 : if( FD_UNLIKELY( !((init_m>0.) && (init_m<=DBL_MAX)) ) ) {
189 3 : FD_LOG_WARNING(( "bad w" ));
190 3 : return NULL;
191 3 : }
192 :
193 69 : ulong footprint = fd_clock_footprint();
194 69 : if( FD_UNLIKELY( !footprint ) ) {
195 0 : FD_LOG_WARNING(( "bad footprint" ));
196 0 : return NULL;
197 0 : }
198 :
199 69 : memset( shclock, 0, footprint );
200 :
201 69 : long recal_jit_eff = (long)fd_ulong_pow2_dn( (ulong)recal_jit );
202 69 : long recal_min = recal_avg - recal_jit_eff;
203 69 : ulong recal_mask = 2UL*(ulong)recal_jit_eff - 1UL;
204 :
205 69 : shclock->seq = 0UL;
206 69 : shclock->recal_next = init_y0 + recal_min + (long)(fd_ulong_hash( FD_CLOCK_MAGIC ^ (ulong)init_x0 ) & recal_mask);
207 69 : shclock->err_cnt = 0UL;
208 :
209 69 : shclock->recal_alpha = 1. / (1. + recal_hist);
210 69 : shclock->recal_beta = recal_frac / (double)(recal_avg + recal_jit_eff);
211 69 : shclock->recal_min = recal_min;
212 69 : shclock->recal_mask = recal_mask;
213 :
214 69 : shclock->recal_avg = recal_avg;
215 69 : shclock->recal_jit = recal_jit;
216 69 : shclock->recal_hist = recal_hist;
217 69 : shclock->recal_frac = recal_frac;
218 :
219 69 : shclock->init_x0 = init_x0;
220 69 : shclock->init_y0 = init_y0;
221 69 : shclock->init_w = init_w;
222 :
223 69 : fd_clock_epoch_t * epoch = shclock->epoch;
224 :
225 345 : for( ulong idx=0UL; idx<FD_CLOCK_EPOCH_CNT; idx++ ) {
226 276 : epoch[ idx ].seq0 = 0UL;
227 276 : epoch[ idx ].x0 = init_x0;
228 276 : epoch[ idx ].y0 = init_y0;
229 276 : epoch[ idx ].w = init_w;
230 276 : epoch[ idx ].y0_eff = init_y0;
231 276 : epoch[ idx ].m = init_m;
232 276 : epoch[ idx ].seq1 = 0UL;
233 276 : }
234 :
235 69 : FD_COMPILER_MFENCE();
236 69 : shclock->magic = FD_CLOCK_MAGIC;
237 69 : FD_COMPILER_MFENCE();
238 :
239 69 : return shclock;
240 69 : }
241 :
242 : fd_clock_t *
243 : fd_clock_join( void * _lmem,
244 : void * _shclock,
245 : fd_clock_func_t clock_x,
246 84 : void const * args_x ) {
247 84 : fd_clock_t * clock = (fd_clock_t *)_lmem;
248 84 : fd_clock_shmem_t * shclock = (fd_clock_shmem_t *)_shclock;
249 :
250 84 : if( FD_UNLIKELY( !clock ) ) {
251 3 : FD_LOG_WARNING(( "NULL lmem" ));
252 3 : return NULL;
253 3 : }
254 :
255 81 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)clock, alignof(fd_clock_t) ) ) ) {
256 3 : FD_LOG_WARNING(( "misaligned lmem" ));
257 3 : return NULL;
258 3 : }
259 :
260 78 : if( FD_UNLIKELY( !shclock ) ) {
261 3 : FD_LOG_WARNING(( "NULL shclock" ));
262 3 : return NULL;
263 3 : }
264 :
265 75 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shclock, fd_clock_align() ) ) ) {
266 3 : FD_LOG_WARNING(( "misaligned shclock" ));
267 3 : return NULL;
268 3 : }
269 :
270 72 : if( FD_UNLIKELY( shclock->magic!=FD_CLOCK_MAGIC ) ) {
271 3 : FD_LOG_WARNING(( "bad magic" ));
272 3 : return NULL;
273 3 : }
274 :
275 69 : if( FD_UNLIKELY( !clock_x ) ) {
276 3 : FD_LOG_WARNING(( "NULL clock_x" ));
277 3 : return NULL;
278 3 : }
279 :
280 66 : clock->shclock = shclock;
281 66 : clock->clock_x = clock_x;
282 66 : clock->args_x = args_x;
283 :
284 66 : return clock;
285 69 : }
286 :
287 : void *
288 15 : fd_clock_leave( fd_clock_t * clock ) {
289 :
290 15 : if( FD_UNLIKELY( !clock ) ) {
291 3 : FD_LOG_WARNING(( "NULL clock" ));
292 3 : return NULL;
293 3 : }
294 :
295 12 : return clock;
296 15 : }
297 :
298 : void *
299 21 : fd_clock_delete( void * _shclock ) {
300 21 : fd_clock_shmem_t * shclock = (fd_clock_shmem_t *)_shclock;
301 :
302 21 : if( FD_UNLIKELY( !shclock ) ) {
303 3 : FD_LOG_WARNING(( "NULL shclock" ));
304 3 : return NULL;
305 3 : }
306 :
307 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shclock, fd_clock_align() ) ) ) {
308 3 : FD_LOG_WARNING(( "misaligned shclock" ));
309 3 : return NULL;
310 3 : }
311 :
312 15 : if( FD_UNLIKELY( shclock->magic!=FD_CLOCK_MAGIC ) ) {
313 3 : FD_LOG_WARNING(( "bad magic" ));
314 3 : return NULL;
315 3 : }
316 :
317 12 : FD_COMPILER_MFENCE();
318 12 : shclock->magic = 0UL;
319 12 : FD_COMPILER_MFENCE();
320 :
321 12 : return shclock;
322 15 : }
323 :
324 : long
325 269265 : fd_clock_now( void const * _clock ) {
326 269265 : fd_clock_t const * clock = (fd_clock_t const *)_clock;
327 269265 : fd_clock_shmem_t const * shclock = clock->shclock;
328 269265 : fd_clock_func_t clock_x = clock->clock_x;
329 269265 : void const * args_x = clock->args_x;
330 :
331 269265 : fd_clock_epoch_t epoch[1];
332 269265 : long x_obs;
333 269265 : for(;;) {
334 269265 : ulong seq0 = fd_clock_seq( shclock ); /* likely l1 cache hit */
335 269265 : fd_clock_epoch_read( shclock, seq0, epoch ); /* likely l1 cache hit */
336 269265 : x_obs = clock_x( args_x ); /* after seq0 read, as close to return as possible */
337 269265 : ulong seq1 = fd_clock_seq( shclock ); /* likely l1 cache hit */
338 269265 : if( FD_LIKELY( (seq0==seq1) & (epoch->seq0==seq0) & (epoch->seq1==seq0) ) ) break;
339 0 : FD_SPIN_PAUSE();
340 0 : }
341 269265 : return fd_clock_epoch_y( epoch, x_obs );
342 269265 : }
343 :
344 : int
345 : fd_clock_joint_read( fd_clock_func_t clock_x, void const * args_x,
346 : fd_clock_func_t clock_y, void const * args_y,
347 : long * opt_x,
348 : long * opt_y,
349 1863 : long * opt_dx ) {
350 :
351 1863 : long x[ FD_CLOCK_JOINT_READ_CNT+1UL ];
352 1863 : long y[ FD_CLOCK_JOINT_READ_CNT ];
353 :
354 7452 : for( ulong idx=0UL; idx<FD_CLOCK_JOINT_READ_CNT; idx++ ) {
355 5589 : x[ idx ] = clock_x( args_x );
356 5589 : y[ idx ] = clock_y( args_y );
357 5589 : }
358 :
359 1863 : x[ FD_CLOCK_JOINT_READ_CNT ] = clock_x( args_x );
360 :
361 1863 : ulong best_idx = 0UL;
362 1863 : long best_dx = x[1] - x[0]; if( FD_UNLIKELY( best_dx<0L ) ) return FD_CLOCK_ERR_X;
363 :
364 5574 : for( ulong idx=1UL; idx<FD_CLOCK_JOINT_READ_CNT; idx++ ) {
365 3717 : long dy = y[ idx ] - y[ idx-1UL ]; if( FD_UNLIKELY( dy<0L ) ) return FD_CLOCK_ERR_Y;
366 3714 : long dx = x[ idx+1UL ] - x[ idx ]; if( FD_UNLIKELY( dx<0L ) ) return FD_CLOCK_ERR_X;
367 3714 : best_idx = fd_ulong_if( best_dx<dx, best_idx, idx );
368 3714 : best_dx = fd_long_min( best_dx, dx );
369 3714 : }
370 :
371 1857 : best_dx = (best_dx+1L) >> 1; /* ceil( (x[best_idx+1]-x[best_idx])/2 ) */
372 :
373 1857 : fd_long_store_if( !!opt_x, opt_x, x[ best_idx ] + best_dx );
374 1857 : fd_long_store_if( !!opt_y, opt_y, y[ best_idx ] );
375 1857 : fd_long_store_if( !!opt_dx, opt_dx, best_dx );
376 :
377 1857 : return FD_CLOCK_SUCCESS;
378 1860 : }
379 :
380 : static inline long
381 : fd_clock_next( fd_clock_shmem_t * shclock,
382 : long x0,
383 : long y0,
384 : double w,
385 : long y0_eff,
386 : double m,
387 1782 : int err ) {
388 :
389 1782 : ulong seq = shclock->seq + 1UL;
390 1782 : long recal_next = (y0_eff + shclock->recal_min) + (long)(fd_ulong_hash( FD_CLOCK_MAGIC ^ (ulong)x0 ) & shclock->recal_mask);
391 1782 : ulong err_cnt = shclock->err_cnt + (ulong)!!err;
392 :
393 1782 : fd_clock_epoch_t * epoch = shclock->epoch + (seq & (FD_CLOCK_EPOCH_CNT-1UL));
394 :
395 1782 : FD_COMPILER_MFENCE();
396 1782 : epoch->seq1 = seq; /* Mark entry as unsafe to read */
397 1782 : FD_COMPILER_MFENCE();
398 1782 : epoch->x0 = x0;
399 1782 : epoch->y0 = y0;
400 1782 : epoch->w = w;
401 1782 : epoch->y0_eff = y0_eff;
402 1782 : epoch->m = m;
403 1782 : FD_COMPILER_MFENCE();
404 1782 : epoch->seq0 = seq; /* Mark entry as safe to read */
405 1782 : FD_COMPILER_MFENCE();
406 1782 : shclock->seq = seq;
407 1782 : shclock->recal_next = recal_next;
408 1782 : shclock->err_cnt = err_cnt;
409 1782 : FD_COMPILER_MFENCE();
410 :
411 1782 : return recal_next;
412 1782 : }
413 :
414 : long
415 : fd_clock_recal( fd_clock_t * clock,
416 : long x1,
417 1782 : long y1 ) {
418 :
419 1782 : fd_clock_shmem_t * shclock = clock->shclock;
420 :
421 1782 : fd_clock_epoch_t const * epoch = shclock->epoch + (shclock->seq & (FD_CLOCK_EPOCH_CNT-1UL));
422 :
423 1782 : long x0 = epoch->x0;
424 1782 : long y0 = epoch->y0;
425 1782 : double w0 = epoch->w;
426 1782 : long y0_eff = epoch->y0_eff;
427 1782 : double m0 = epoch->m;
428 :
429 1782 : long dx = x1 - x0;
430 1782 : long dy = y1 - y0;
431 :
432 1782 : double w_obs = ((double)dx) / ((double)dy);
433 :
434 1782 : double w1;
435 1782 : long y1_eff;
436 1782 : double m1;
437 1782 : int err;
438 :
439 : /* FIXME: Consider tighter rate interval? (E.g. 0.9765625 / 1.024) */
440 :
441 1782 : if( FD_UNLIKELY( !((dx>0L) & (dy>0L) & ((0.5*w0)<w_obs) & (w_obs<(2.0*w0))) ) ) {
442 :
443 : /* At this point, the x-clock didn't step forward between recals,
444 : the y-clock didn't step forward between recals, the observed rate
445 : this epoch slowed dramatically and/or the observed rate this
446 : epoch increased dramatically. This is typically a sign that an
447 : operator stepped the x-clock backward (dx<<0), y-clock backward
448 : (dy<<0), x-clock forward (w_obs>>w0) and/or y-clock forward
449 : (w_obs<<w0) by a large amount out-of-band. We start the new
450 : epoch at (x1,y1) with the current epoch's tick rate estimates and
451 : log a recal error. This allows near immediate recovery all
452 : manners of clock jankiness. It also can break monotonicity of
453 : y-clock predictions but there's not a lot of choice given janky
454 : clocks. */
455 :
456 0 : w1 = w0;
457 0 : y1_eff = y1;
458 0 : m1 = 1./w0;
459 0 : err = 1;
460 :
461 1782 : } else {
462 :
463 : /* At this point, x1 / y1 are in the future of the current epoch
464 : start on the x-clock / y-clock and the observed tick rate this
465 : epoch is plausible. We average the observed tick rate with the
466 : current epoch's rate estimate to get the next epoch's rate
467 : estimate.
468 :
469 : To preserve y-clock prediction monotonicity, the effective y1
470 : for the next epoch will be at the later of the observation y1 and
471 : this epoch's estimate for y1 given the obsevration x1.
472 :
473 : If y1_eff == y1 (i.e. we are microstepping the fd_clock forward
474 : to correct immediately and fully an underestimate at the end of
475 : this epoch without breaking monotonicity), we just use 1/w1 for
476 : the y-ticks per x-ticks conversion rate m1 this epoch.
477 :
478 : Otherwise, we can't microstep the fd_clock backward while
479 : ensuring monotonicity on observers. To correct the overestimate
480 : this epoch, we reduce the conversion rate to approximately absorb
481 : recal_frac the overestimate over the coming epoch. The reduction
482 : is such that, asymptotically, the resulting conversion should
483 : always be positive.
484 :
485 : See more detailed derivation above. */
486 :
487 1782 : w1 = w0 + shclock->recal_alpha*(w_obs-w0);
488 1782 : y1_eff = fd_long_max( y1, y0_eff + (long)(0.5 + m0*(double)dx) );
489 1782 : m1 = 1. / (w1 + (shclock->recal_beta*w1)*(double)(y1_eff-y1));
490 1782 : err = 0;
491 :
492 1782 : }
493 :
494 1782 : return fd_clock_next( shclock, x1, y1, w1, y1_eff, m1, err );
495 1782 : }
496 :
497 : long
498 : fd_clock_step( fd_clock_t * clock,
499 : long x0,
500 : long y0,
501 0 : double w ) {
502 0 : return fd_clock_next( clock->shclock, x0, y0, w, y0, 1./w, 0 ); /* FIXME: Consider treating these as a "err" */
503 0 : }
504 :
505 : char const *
506 12 : fd_clock_strerror( int err ) {
507 12 : switch( err ) {
508 3 : case FD_CLOCK_SUCCESS: return "success";
509 3 : case FD_CLOCK_ERR_X: return "x-clock not well-behaved";
510 3 : case FD_CLOCK_ERR_Y: return "y-clock not well-behaved";
511 3 : default: break;
512 12 : }
513 3 : return "unknown";
514 12 : }
|
