2 * Copyright (c) 2005 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
34 * $DragonFly: src/usr.sbin/dntpd/client.c,v 1.9 2005/04/26 23:50:23 dillon Exp $
45 client_main(struct server_info **info_ary, int count)
47 struct server_info *best_off;
48 struct server_info *best_freq;
53 int calc_offset_correction;
59 * Subtract the interval from poll_sleep and poll the client
62 * Because we do not compensate for offset corrections which are
63 * in progress, we cannot accumulate data for an offset correction
64 * while a prior correction is still being worked through by the
67 calc_offset_correction = !sysntp_offset_correction_is_running();
68 for (i = 0; i < count; ++i)
69 client_poll(info_ary[i], min_sleep_opt, calc_offset_correction);
72 * Find the best client (or synthesize one). A different client
73 * can be chosen for frequency and offset. Note in particular
74 * that offset counters and averaging code gets reset when an
75 * offset correction is made (otherwise the averaging history will
76 * cause later corrections to overshoot).
78 * The regression used to calculate the frequency is a much
79 * longer-term entity and is NOT reset, so it is still possible
80 * for the offset correction code to make minor adjustments to
81 * the frequency if it so desires.
83 * client_check may replace the server_info pointer with a new
88 for (i = 0; i < count; ++i)
89 client_check(&info_ary[i], &best_off, &best_freq);
95 offset = best_off->lin_sumoffset / best_off->lin_countoffset;
96 lin_resetalloffsets(info_ary, count);
97 if (offset < -COURSE_OFFSET_CORRECTION_LIMIT ||
98 offset > COURSE_OFFSET_CORRECTION_LIMIT ||
101 freq = sysntp_correct_course_offset(offset);
104 freq = sysntp_correct_offset(offset);
111 * Frequency correction (throw away minor freq adjusts from the
112 * offset code if we can't do a frequency correction here). Do
113 * not reissue if it hasn't changed from the last issued correction.
116 freq += best_freq->lin_cache_freq;
117 if (last_freq != freq) {
118 sysntp_correct_freq(freq);
124 * This function is responsible for managing the polling mode and
125 * figures out how long we should sleep.
127 for (i = 0; i < count; ++i)
128 client_manage_polling_mode(info_ary[i]);
131 * Polling loop sleep.
133 usleep(min_sleep_opt * 1000000 + random() % 500000);
138 client_poll(server_info_t info, int poll_interval, int calc_offset_correction)
146 * By default we always poll. If the polling interval comes under
147 * active management the poll_sleep will be non-zero.
149 if (info->poll_sleep > poll_interval) {
150 info->poll_sleep -= poll_interval;
153 info->poll_sleep = 0;
155 logdebug(4, "%s: poll, ", info->target);
156 if (udp_ntptimereq(info->fd, &rtv, <v, &lbtv) < 0) {
158 logdebug(4, "no response (%d failures in a row)\n",
160 if (info->poll_failed == POLL_FAIL_RESET) {
161 if (info->lin_count != 0) {
162 logdebug(4, "%s: resetting regression due to failures\n",
171 * Successful query. Update polling info for the polling mode manager.
174 info->poll_failed = 0;
177 * Figure out the offset (the difference between the reported
178 * time and our current time) for linear regression purposes.
180 offset = tv_delta_double(&rtv, <v);
186 if (debug_level >= 4) {
193 strftime(buf, sizeof(buf), "%d-%b-%Y %H:%M:%S", tp);
194 logdebug(4, "%s.%03ld ", buf, rtv.tv_usec / 1000);
196 lin_regress(info, <v, &lbtv, offset, calc_offset_correction);
197 info = info->altinfo;
198 if (info && debug_level >= 4) {
199 logdebug(4, "%*.*s: poll, ",
200 (int)strlen(info->target),
201 (int)strlen(info->target), "(alt)");
207 * Find the best client (or synthesize a fake info structure to return).
208 * We can find separate best clients for offset and frequency.
211 client_check(struct server_info **checkp,
212 struct server_info **best_off,
213 struct server_info **best_freq)
215 struct server_info *check = *checkp;
216 struct server_info *info;
219 * Start an alternate linear regression once our current one
220 * has passed a certain point.
222 if (check->lin_count >= LIN_RESTART / 2 && check->altinfo == NULL) {
223 info = malloc(sizeof(*info));
224 assert(info != NULL);
225 /* note: check->altinfo is NULL as of the bcopy */
226 bcopy(check, info, sizeof(*info));
227 check->altinfo = info;
232 * Replace our current linear regression with the alternate once
233 * the current one has hit its limit (beyond a certain point the
234 * linear regression starts to work against us, preventing us from
235 * reacting to changing conditions).
237 * Report any significant change in the offset or ppm.
239 if (check->lin_count >= LIN_RESTART) {
240 if ((info = check->altinfo) && info->lin_count >= LIN_RESTART / 2) {
243 freq_diff = info->lin_cache_freq - check->lin_cache_freq;
244 logdebug(4, "%s: Switching to alternate, Frequence "
245 "difference is %6.3f ppm\n",
246 info->target, freq_diff * 1.0E+6);
254 * BEST CLIENT FOR FREQUENCY CORRECTION:
256 * 8 samples and a correllation > 0.99, or
257 * 16 samples and a correllation > 0.96
260 if ((check->lin_count >= 8 && fabs(check->lin_cache_corr) >= 0.99) ||
261 (check->lin_count >= 16 && fabs(check->lin_cache_corr) >= 0.96)
264 fabs(check->lin_cache_corr) > fabs(info->lin_cache_corr)
273 * BEST CLIENT FOR OFFSET CORRECTION:
275 * Use the standard-deviation and require at least 4 samples. An
276 * offset correction is valid if the standard deviation is less then
277 * the average offset divided by 4.
280 if (check->lin_countoffset >= 4 &&
281 check->lin_cache_stddev < fabs(check->lin_sumoffset / check->lin_countoffset / 4)) {
283 fabs(check->lin_cache_stddev) < fabs(info->lin_cache_stddev)
292 * Actively manage the polling interval. Note that the poll_* fields are
293 * always transfered to the alternate regression when the check code replaces
294 * the current regression with a new one.
296 * This routine is called from the main loop for each base info structure.
297 * The polling mode applies to all alternates so we do not have to iterate
301 client_manage_polling_mode(struct server_info *info)
304 * If too many query failures occured go into a failure-recovery state.
305 * If we were in startup when we failed, go into the second failure
306 * state so a recovery returns us back to startup mode.
308 if (info->poll_failed >= POLL_FAIL_RESET &&
309 info->poll_mode != POLL_FAILED_1 &&
310 info->poll_mode != POLL_FAILED_2
312 logdebug(2, "%s: polling mode moving to a FAILED state.\n",
314 if (info->poll_mode != POLL_STARTUP)
315 info->poll_mode = POLL_FAILED_1;
317 info->poll_mode = POLL_FAILED_2;
318 info->poll_count = 0;
322 * Standard polling mode progression
324 switch(info->poll_mode) {
326 info->poll_mode = POLL_STARTUP;
327 info->poll_count = 0;
328 logdebug(2, "%s: polling mode INIT->STARTUP.\n", info->target);
331 if (info->poll_count < POLL_STARTUP_MAX) {
332 if (info->poll_sleep == 0)
333 info->poll_sleep = min_sleep_opt;
336 info->poll_mode = POLL_ACQUIRE;
337 info->poll_count = 0;
338 logdebug(2, "%s: polling mode STARTUP->ACQUIRE.\n", info->target);
342 * Acquisition mode using the nominal timeout. We do not shift
343 * to maintainance mode unless the correllation is at least 0.90
345 if (info->poll_count < POLL_ACQUIRE_MAX ||
346 info->lin_count < 8 ||
347 fabs(info->lin_cache_corr) < 0.85
349 if (info->poll_count >= POLL_ACQUIRE_MAX &&
350 info->lin_count == LIN_RESTART - 2
353 "%s: WARNING: Unable to shift this source to "
354 "maintainance mode. Target correllation is aweful.\n",
357 if (info->poll_sleep == 0)
358 info->poll_sleep = nom_sleep_opt;
361 info->poll_mode = POLL_MAINTAIN;
362 info->poll_count = 0;
363 logdebug(2, "%s: polling mode ACQUIRE->MAINTAIN.\n", info->target);
366 if (info->lin_count >= LIN_RESTART / 2 &&
367 fabs(info->lin_cache_corr) < 0.70
370 "%s: polling mode MAINTAIN->ACQUIRE. Unable to maintain\n"
371 "the maintainance mode because the correllation went"
372 " bad!\n", info->target);
373 info->poll_mode = POLL_ACQUIRE;
374 info->poll_count = 0;
377 if (info->poll_sleep == 0)
378 info->poll_sleep = max_sleep_opt;
383 * We have failed recently. If we recover return to the acquisition
386 * poll_count does not increment while we are failed. poll_failed
387 * does increment (but gets zero'd once we recover).
389 if (info->poll_count != 0) {
390 logdebug(2, "%s: polling mode FAILED1->ACQUIRE.\n", info->target);
391 info->poll_mode = POLL_ACQUIRE;
392 /* do not reset poll_count */
395 if (info->poll_failed >= POLL_RECOVERY_RESTART)
396 info->poll_mode = POLL_FAILED_2;
397 if (info->poll_sleep == 0)
398 info->poll_sleep = nom_sleep_opt;
402 * We have been failed for a very long time, or we failed while
403 * in startup. If we recover we have to go back into startup.
405 if (info->poll_count != 0) {
406 logdebug(2, "%s: polling mode FAILED2->STARTUP.\n", info->target);
407 info->poll_mode = POLL_STARTUP;
410 if (info->poll_sleep == 0)
411 info->poll_sleep = nom_sleep_opt;
419 * ltv local time as of when the offset error was calculated between
420 * local time and remote time.
422 * lbtv base time as of when local time was obtained. Used to
423 * calculate the cumulative corrections made to the system's
424 * real time clock so we can de-correct the offset for the
427 * X is the time axis, in seconds.
428 * Y is the uncorrected offset, in seconds.
431 lin_regress(server_info_t info, struct timeval *ltv, struct timeval *lbtv,
432 double offset, int calc_offset_correction)
435 double uncorrected_offset;
438 * De-correcting the offset:
440 * The passed offset is (our_real_time - remote_real_time). To remove
441 * corrections from our_real_time we take the difference in the basetime
442 * (new_base_time - old_base_time) and subtract that from the offset.
443 * That is, if the basetime goesup, the uncorrected offset goes down.
445 if (info->lin_count == 0) {
447 info->lin_btv = *lbtv;
449 uncorrected_offset = offset;
451 time_axis = tv_delta_double(&info->lin_tv, ltv);
452 uncorrected_offset = offset - tv_delta_double(&info->lin_btv, lbtv);
456 * We have to use the uncorrected offset for frequency calculations.
459 info->lin_sumx += time_axis;
460 info->lin_sumx2 += time_axis * time_axis;
461 info->lin_sumy += uncorrected_offset;
462 info->lin_sumy2 += uncorrected_offset * uncorrected_offset;
463 info->lin_sumxy += time_axis * uncorrected_offset;
466 * We have to use the corrected offset for offset calculations.
468 if (calc_offset_correction) {
469 ++info->lin_countoffset;
470 info->lin_sumoffset += offset;
471 info->lin_sumoffset2 += offset * offset;
475 * Calculate various derived values. This gets us slope, y-intercept,
476 * and correllation from the linear regression.
478 if (info->lin_count > 1) {
479 info->lin_cache_slope =
480 (info->lin_count * info->lin_sumxy - info->lin_sumx * info->lin_sumy) /
481 (info->lin_count * info->lin_sumx2 - info->lin_sumx * info->lin_sumx);
483 info->lin_cache_yint =
484 (info->lin_sumy - info->lin_cache_slope * info->lin_sumx) /
487 info->lin_cache_corr =
488 (info->lin_count * info->lin_sumxy - info->lin_sumx * info->lin_sumy) /
489 sqrt((info->lin_count * info->lin_sumx2 -
490 info->lin_sumx * info->lin_sumx) *
491 (info->lin_count * info->lin_sumy2 -
492 info->lin_sumy * info->lin_sumy)
497 * Calculate more derived values. This gets us the standard-deviation
498 * of offsets. The standard deviation approximately means that 68%
499 * of the samples fall within the calculated stddev of the mean.
501 if (info->lin_countoffset > 1) {
502 info->lin_cache_stddev =
503 sqrt((info->lin_sumoffset2 -
504 ((info->lin_sumoffset * info->lin_sumoffset /
505 info->lin_countoffset))) /
506 (info->lin_countoffset - 1.0));
510 * Save the most recent offset, we might use it in the future.
511 * Save the frequency correction (we might scale the slope later so
512 * we have a separate field for the actual frequency correction in
513 * seconds per second).
515 info->lin_cache_offset = offset;
516 info->lin_cache_freq = info->lin_cache_slope;
518 if (debug_level >= 4) {
519 logdebug(4, "iter=%2d time=%7.3f off=%.6f uoff=%.6f",
520 (int)info->lin_count,
521 time_axis, offset, uncorrected_offset);
522 if (info->lin_count > 1) {
523 logdebug(4, " slope %7.6f"
524 " yint %3.2f corr %7.6f freq_ppm %4.2f",
525 info->lin_cache_slope,
526 info->lin_cache_yint,
527 info->lin_cache_corr,
528 info->lin_cache_freq * 1000000.0);
530 if (info->lin_countoffset > 1) {
531 logdebug(4, " stddev %7.6f", info->lin_cache_stddev);
532 } else if (calc_offset_correction == 0) {
533 /* cannot calculate offset correction due to prior correction */
534 logdebug(4, " offset_ignored");
541 * Reset the linear regression data. The info structure will not again be
542 * a candidate for frequency or offset correction until sufficient data
543 * has been accumulated to make a decision.
546 lin_reset(server_info_t info)
557 info->lin_countoffset = 0;
558 info->lin_sumoffset = 0;
559 info->lin_sumoffset2 = 0;
561 info->lin_cache_slope = 0;
562 info->lin_cache_yint = 0;
563 info->lin_cache_corr = 0;
564 info->lin_cache_offset = 0;
565 info->lin_cache_freq = 0;
568 * Destroy any additional alternative regressions.
570 while ((scan = info->altinfo) != NULL) {
571 info->altinfo = scan->altinfo;
577 * Sometimes we want to clean out the offset calculations without
578 * destroying the linear regression used to figure out the frequency
579 * correction. This usually occurs whenever we issue an offset
580 * adjustment to the system, which invalidates any offset data accumulated
584 lin_resetalloffsets(struct server_info **info_ary, int count)
589 for (i = 0; i < count; ++i) {
590 for (info = info_ary[i]; info; info = info->altinfo)
591 lin_resetoffsets(info);
596 lin_resetoffsets(server_info_t info)
598 info->lin_countoffset = 0;
599 info->lin_sumoffset = 0;
600 info->lin_sumoffset2 = 0;