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