Implement a variable polling rate capability.
[dragonfly.git] / usr.sbin / dntpd / client.c
1 /*
2  * Copyright (c) 2005 The DragonFly Project.  All rights reserved.
3  * 
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
6  * 
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  * 
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  * 
34  * $DragonFly: src/usr.sbin/dntpd/client.c,v 1.5 2005/04/24 23:09:32 dillon Exp $
35  */
36
37 #include "defs.h"
38
39 void
40 client_init(void)
41 {
42 }
43
44 int
45 client_main(struct server_info **info_ary, int count)
46 {
47     struct server_info *best_off;
48     struct server_info *best_freq;
49     double freq;
50     double offset;
51     int i;
52
53     for (;;) {
54         /*
55          * Subtract the interval from poll_sleep and poll the client
56          * if it reaches 0.
57          */
58         for (i = 0; i < count; ++i)
59             client_poll(info_ary[i], min_sleep_opt);
60
61         /*
62          * Find the best client (or synthesize one).  A different client
63          * can be chosen for frequency and offset.  Note in particular 
64          * that offset counters and averaging code gets reset when an
65          * offset correction is made (otherwise the averaging history will
66          * cause later corrections to overshoot).  
67          * 
68          * The regression used to calculate the frequency is a much 
69          * longer-term entity and is NOT reset, so it is still possible
70          * for the offset correction code to make minor adjustments to
71          * the frequency if it so desires.
72          *
73          * client_check may replace the server_info pointer with a new
74          * one.
75          */
76         best_off = NULL;
77         best_freq = NULL;
78         for (i = 0; i < count; ++i)
79             client_check(&info_ary[i], &best_off, &best_freq);
80
81         /*
82          * Offset correction.
83          *
84          * XXX it might not be a good idea to issue an offset correction if
85          * a prior offset correction is still in progress as this will skew
86          * the offset calculation.  XXX either figure out how to correct the
87          * skew or do not issue a correction.
88          */
89         if (best_off) {
90             offset = best_off->lin_sumoffset / best_off->lin_countoffset;
91             lin_resetalloffsets(info_ary, count);
92             freq = sysntp_correct_offset(offset);
93         } else {
94             freq = 0.0;
95         }
96
97         /*
98          * Frequency correction (throw away minor freq adjusts from the
99          * offset code if we can't do a frequency correction here).
100          */
101         if (best_freq) {
102             sysntp_correct_freq(best_freq->lin_cache_freq + freq);
103         }
104
105         /*
106          * This function is responsible for managing the polling mode and
107          * figures out how long we should sleep.
108          */
109         for (i = 0; i < count; ++i)
110             client_manage_polling_mode(info_ary[i]);
111
112         /*
113          * Polling loop sleep.
114          */
115         usleep(min_sleep_opt * 1000000 + random() % 500000);
116     }
117 }
118
119 void
120 client_poll(server_info_t info, int poll_interval)
121 {
122     struct timeval rtv;
123     struct timeval ltv;
124     struct timeval lbtv;
125     double offset;
126
127     /*
128      * By default we always poll.  If the polling interval comes under
129      * active management the poll_sleep will be non-zero.
130      */
131     if (info->poll_sleep > poll_interval) {
132         info->poll_sleep -= poll_interval;
133         return;
134     }
135     info->poll_sleep = 0;
136
137     if (debug_opt) {
138         fprintf(stderr, "%s: poll, ", info->target);
139         fflush(stderr);
140     }
141     if (udp_ntptimereq(info->fd, &rtv, &ltv, &lbtv) < 0) {
142         ++info->poll_failed;
143         if (debug_opt) {
144             fprintf(stderr, "no response (%d failures in a row)\n", 
145                     info->poll_failed);
146         }
147         if (info->poll_failed == POLL_FAIL_RESET) {
148             if (debug_opt && info->lin_count != 0) {
149                 fprintf(stderr, "%s: resetting regression due to failures\n", 
150                         info->target);
151             }
152             lin_reset(info);
153         }
154         return;
155     }
156
157     /*
158      * Successful query.  Update polling info for the polling mode manager.
159      */
160     ++info->poll_count;
161     info->poll_failed = 0;
162
163     /*
164      * Figure out the offset (the difference between the reported
165      * time and our current time) for linear regression purposes.
166      */
167     offset = tv_delta_double(&rtv, &ltv);
168
169     while (info) {
170         /*
171          * Linear regression
172          */
173         if (debug_opt) {
174             struct tm *tp;
175             char buf[64];
176             time_t t;
177
178             t = rtv.tv_sec;
179             tp = localtime(&t);
180             strftime(buf, sizeof(buf), "%d-%b-%Y %H:%M:%S", tp);
181             fprintf(stderr, "%s.%03ld ", 
182                     buf, rtv.tv_usec / 1000);
183         }
184         lin_regress(info, &ltv, &lbtv, offset);
185         info = info->altinfo;
186         if (info && debug_opt) {
187             fprintf(stderr, "%*.*s: poll, ", 
188                 (int)strlen(info->target), 
189                 (int)strlen(info->target),
190                 "(alt)");
191             fflush(stderr);
192         }
193     }
194 }
195
196 /*
197  * Find the best client (or synthesize a fake info structure to return).
198  * We can find separate best clients for offset and frequency.
199  */
200 void
201 client_check(struct server_info **checkp, 
202              struct server_info **best_off,
203              struct server_info **best_freq)
204 {
205     struct server_info *check = *checkp;
206     struct server_info *info;
207
208     /*
209      * Start an alternate linear regression once our current one
210      * has passed a certain point.
211      */
212     if (check->lin_count >= LIN_RESTART / 2 && check->altinfo == NULL) {
213         info = malloc(sizeof(*info));
214         assert(info != NULL);
215         /* note: check->altinfo is NULL as of the bcopy */
216         bcopy(check, info, sizeof(*info));
217         check->altinfo = info;
218         lin_reset(info);
219     }
220
221     /*
222      * Replace our current linear regression with the alternate once
223      * the current one has hit its limit (beyond a certain point the
224      * linear regression starts to work against us, preventing us from
225      * reacting to changing conditions).
226      *
227      * Report any significant change in the offset or ppm.
228      */
229     if (check->lin_count >= LIN_RESTART) {
230         if ((info = check->altinfo) && info->lin_count >= LIN_RESTART / 2) {
231             double freq_diff;
232
233             if (debug_opt) {
234                 freq_diff = info->lin_cache_freq - check->lin_cache_freq;
235                 printf("%s: Switching to alternate, Frequence difference is %6.3f ppm\n",
236                         info->target, freq_diff * 1.0E+6);
237             }
238             *checkp = info;
239             free(check);
240             check = info;
241         }
242     }
243
244     /*
245      * BEST CLIENT FOR FREQUENCY CORRECTION:
246      *
247      *  8 samples and a correllation > 0.99, or
248      * 16 samples and a correllation > 0.96
249      */
250     info = *best_freq;
251     if ((check->lin_count >= 8 && fabs(check->lin_cache_corr) >= 0.99) ||
252         (check->lin_count >= 16 && fabs(check->lin_cache_corr) >= 0.96)
253     ) {
254         if (info == NULL || 
255             fabs(check->lin_cache_corr) > fabs(info->lin_cache_corr)
256         ) {
257             info = check;
258             *best_freq = info;
259         }
260
261     }
262
263     /*
264      * BEST CLIENT FOR OFFSET CORRECTION:
265      *
266      * Use the standard-deviation and require at least 4 samples.  An
267      * offset correction is valid if the standard deviation is less then
268      * the average offset divided by 4.
269      */
270     info = *best_off;
271     if (check->lin_countoffset >= 4 && 
272         check->lin_cache_stddev < fabs(check->lin_sumoffset / check->lin_countoffset / 4)) {
273         if (info == NULL || 
274             fabs(check->lin_cache_stddev) < fabs(info->lin_cache_stddev)
275         ) {
276             info = check;
277             *best_off = info;
278         }
279     }
280 }
281
282 /*
283  * Actively manage the polling interval.  Note that the poll_* fields are
284  * always transfered to the alternate regression when the check code replaces
285  * the current regression with a new one.
286  *
287  * This routine is called from the main loop for each base info structure.
288  * The polling mode applies to all alternates so we do not have to iterate
289  * through the alt's.
290  */
291 void
292 client_manage_polling_mode(struct server_info *info)
293 {
294     /*
295      * If too many query failures occured go into a failure-recovery state.
296      * If we were in startup when we failed, go into the second failure
297      * state so a recovery returns us back to startup mode.
298      */
299     if (info->poll_failed >= POLL_FAIL_RESET && 
300         info->poll_mode != POLL_FAILED_1 &&
301         info->poll_mode != POLL_FAILED_2
302     ) {
303         if (debug_opt)
304             fprintf(stderr, "%s: polling mode moving to a FAILED state.\n",
305                     info->target);
306         if (info->poll_mode != POLL_STARTUP)
307             info->poll_mode = POLL_FAILED_1;
308         else
309             info->poll_mode = POLL_FAILED_2;
310         info->poll_count = 0;
311     }
312
313     /*
314      * Standard polling mode progression
315      */
316     switch(info->poll_mode) {
317     case POLL_FIXED:
318         info->poll_mode = POLL_STARTUP;
319         info->poll_count = 0;
320         if (debug_opt)
321             fprintf(stderr, "%s: polling mode INIT->STARTUP.\n", info->target);
322         /* fall through */
323     case POLL_STARTUP:
324         if (info->poll_count < POLL_STARTUP_MAX) {
325             if (info->poll_sleep == 0)
326                 info->poll_sleep = min_sleep_opt;
327             break;
328         }
329         info->poll_mode = POLL_ACQUIRE;
330         info->poll_count = 0;
331         if (debug_opt) {
332             fprintf(stderr, "%s: polling mode STARTUP->ACQUIRE.\n",
333                     info->target);
334         }
335         /* fall through */
336     case POLL_ACQUIRE:
337         /*
338          * Acquisition mode using the nominal timeout.  We do not shift
339          * to maintainance mode unless the correllation is at least 0.90
340          */
341         if (info->poll_count < POLL_ACQUIRE_MAX ||
342             info->lin_count < 8 ||
343             fabs(info->lin_cache_corr) < 0.85
344         ) {
345             if (debug_opt && 
346                 info->poll_count >= POLL_ACQUIRE_MAX && 
347                 info->lin_count == LIN_RESTART - 2
348             ) {
349                 fprintf(stderr, 
350                     "%s: WARNING: Unable to shift this source to maintainance\n"
351                     "mode.  Target correllation is aweful.\n", info->target);
352             }
353             if (info->poll_sleep == 0)
354                 info->poll_sleep = nom_sleep_opt;
355             break;
356         }
357         info->poll_mode = POLL_MAINTAIN;
358         info->poll_count = 0;
359         if (debug_opt) {
360             fprintf(stderr, "%s: polling mode ACQUIRE->MAINTAIN.\n",
361                     info->target);
362         }
363         /* fall through */
364     case POLL_MAINTAIN:
365         if (info->lin_count >= LIN_RESTART / 2 && 
366             fabs(info->lin_cache_corr) < 0.70
367         ) {
368             if (debug_opt) {
369                 fprintf(stderr, 
370                     "%s: polling mode MAINTAIN->ACQUIRE.  Unable to maintain\n"
371                     "the maintainance mode because the correllation went"
372                     " bad!\n", info->target);
373             }
374             info->poll_mode = POLL_ACQUIRE;
375             info->poll_count = 0;
376             break;
377         }
378         if (info->poll_sleep == 0)
379             info->poll_sleep = max_sleep_opt;
380         /* do nothing */
381         break;
382     case POLL_FAILED_1:
383         /*
384          * We have failed recently. If we recover return to the acquisition
385          * state.
386          *
387          * poll_count does not increment while we are failed.  poll_failed
388          * does increment (but gets zero'd once we recover).
389          */
390         if (info->poll_count != 0) {
391             fprintf(stderr, "%s: polling mode FAILED1->ACQUIRE.\n",
392                     info->target);
393             info->poll_mode = POLL_ACQUIRE;
394             /* do not reset poll_count */
395             break;
396         }
397         if (info->poll_failed >= POLL_RECOVERY_RESTART)
398             info->poll_mode = POLL_FAILED_2;
399         if (info->poll_sleep == 0)
400             info->poll_sleep = nom_sleep_opt;
401         break;
402     case POLL_FAILED_2:
403         /*
404          * We have been failed for a very long time, or we failed while
405          * in startup.  If we recover we have to go back into startup.
406          */
407         if (info->poll_count != 0) {
408             fprintf(stderr, "%s: polling mode FAILED2->STARTUP.\n",
409                     info->target);
410             info->poll_mode = POLL_STARTUP;
411             break;
412         }
413         if (info->poll_sleep == 0)
414             info->poll_sleep = nom_sleep_opt;
415         break;
416     }
417 }
418
419 /*
420  * Linear regression.
421  *
422  *      ltv     local time as of when the offset error was calculated between
423  *              local time and remote time.
424  *
425  *      lbtv    base time as of when local time was obtained.  Used to
426  *              calculate the cumulative corrections made to the system's
427  *              real time clock so we can de-correct the offset for the
428  *              linear regression.
429  *
430  * X is the time axis, in seconds.
431  * Y is the uncorrected offset, in seconds.
432  */
433 void
434 lin_regress(server_info_t info, struct timeval *ltv, struct timeval *lbtv,
435             double offset)
436 {
437     double time_axis;
438     double uncorrected_offset;
439
440     /*
441      * De-correcting the offset:
442      *
443      *  The passed offset is (our_real_time - remote_real_time).  To remove
444      *  corrections from our_real_time we take the difference in the basetime
445      *  (new_base_time - old_base_time) and subtract that from the offset.
446      *  That is, if the basetime goesup, the uncorrected offset goes down.
447      */
448     if (info->lin_count == 0) {
449         info->lin_tv = *ltv;
450         info->lin_btv = *lbtv;
451         time_axis = 0;
452         uncorrected_offset = offset;
453     } else {
454         time_axis = tv_delta_double(&info->lin_tv, ltv);
455         uncorrected_offset = offset - tv_delta_double(&info->lin_btv, lbtv);
456     }
457
458     /*
459      * We have to use the uncorrected offset for frequency calculations.
460      */
461     ++info->lin_count;
462     info->lin_sumx += time_axis;
463     info->lin_sumx2 += time_axis * time_axis;
464     info->lin_sumy += uncorrected_offset;
465     info->lin_sumy2 += uncorrected_offset * uncorrected_offset;
466     info->lin_sumxy += time_axis * uncorrected_offset;
467
468     /*
469      * We have to use the corrected offset for offset calculations.
470      */
471     ++info->lin_countoffset;
472     info->lin_sumoffset += offset;
473     info->lin_sumoffset2 += offset * offset;
474
475     /*
476      * Calculate various derived values.   This gets us slope, y-intercept,
477      * and correllation from the linear regression.
478      */
479     if (info->lin_count > 1) {
480         info->lin_cache_slope = 
481          (info->lin_count * info->lin_sumxy - info->lin_sumx * info->lin_sumy) /
482          (info->lin_count * info->lin_sumx2 - info->lin_sumx * info->lin_sumx);
483
484         info->lin_cache_yint = 
485          (info->lin_sumy - info->lin_cache_slope * info->lin_sumx) /
486          (info->lin_count);
487
488         info->lin_cache_corr =
489          (info->lin_count * info->lin_sumxy - info->lin_sumx * info->lin_sumy) /
490          sqrt((info->lin_count * info->lin_sumx2 - 
491                       info->lin_sumx * info->lin_sumx) *
492              (info->lin_count * info->lin_sumy2 - 
493                       info->lin_sumy * info->lin_sumy)
494          );
495     }
496
497     /*
498      * Calculate more derived values.  This gets us the standard-deviation
499      * of offsets.  The standard deviation approximately means that 68%
500      * of the samples fall within the calculated stddev of the mean.
501      */
502     if (info->lin_countoffset > 1) {
503          info->lin_cache_stddev = 
504              sqrt((info->lin_sumoffset2 - 
505                  ((info->lin_sumoffset * info->lin_sumoffset / 
506                    info->lin_countoffset))) /
507                  (info->lin_countoffset - 1.0));
508     }
509
510     /*
511      * Save the most recent offset, we might use it in the future.
512      * Save the frequency correction (we might scale the slope later so
513      * we have a separate field for the actual frequency correction in
514      * seconds per second).
515      */
516     info->lin_cache_offset = offset;
517     info->lin_cache_freq = info->lin_cache_slope;
518
519     if (debug_opt) {
520         fprintf(stderr, "iter=%2d time=%7.3f off=%.6f uoff=%.6f",
521             (int)info->lin_count,
522             time_axis, offset, uncorrected_offset);
523         if (info->lin_count > 1) {
524             fprintf(stderr, " slope %7.6f"
525                             " yint %3.2f corr %7.6f freq_ppm %4.2f", 
526                 info->lin_cache_slope,
527                 info->lin_cache_yint,
528                 info->lin_cache_corr,
529                 info->lin_cache_freq * 1000000.0);
530         }
531         if (info->lin_countoffset > 1) {
532             fprintf(stderr, " stddev %7.6f", info->lin_cache_stddev);
533         }
534         fprintf(stderr, "\n");
535     }
536 }
537
538 /*
539  * Reset the linear regression data.  The info structure will not again be
540  * a candidate for frequency or offset correction until sufficient data
541  * has been accumulated to make a decision.
542  */
543 void
544 lin_reset(server_info_t info)
545 {
546     server_info_t scan;
547
548     info->lin_count = 0;
549     info->lin_sumx = 0;
550     info->lin_sumy = 0;
551     info->lin_sumxy = 0;
552     info->lin_sumx2 = 0;
553     info->lin_sumy2 = 0;
554
555     info->lin_countoffset = 0;
556     info->lin_sumoffset = 0;
557     info->lin_sumoffset2 = 0;
558
559     info->lin_cache_slope = 0;
560     info->lin_cache_yint = 0;
561     info->lin_cache_corr = 0;
562     info->lin_cache_offset = 0;
563     info->lin_cache_freq = 0;
564
565     /*
566      * Destroy any additional alternative regressions.
567      */
568     while ((scan = info->altinfo) != NULL) {
569         info->altinfo = scan->altinfo;
570         free(scan);
571     }
572 }
573
574 /*
575  * Sometimes we want to clean out the offset calculations without
576  * destroying the linear regression used to figure out the frequency
577  * correction.  This usually occurs whenever we issue an offset
578  * adjustment to the system, which invalidates any offset data accumulated
579  * up to that point.
580  */
581 void
582 lin_resetalloffsets(struct server_info **info_ary, int count)
583 {
584     server_info_t info;
585     int i;
586
587     for (i = 0; i < count; ++i) {
588         for (info = info_ary[i]; info; info = info->altinfo)
589             lin_resetoffsets(info);
590     }
591 }
592
593 void
594 lin_resetoffsets(server_info_t info)
595 {
596     info->lin_countoffset = 0;
597     info->lin_sumoffset = 0;
598     info->lin_sumoffset2 = 0;
599 }
600