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.3 2005/04/24 06:24:42 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;
  48     double freq;
  49     double offset;
  50     int i;
  51
  52     for (;;) {
  53         /*
  54          * Poll clients and accumulate data
  55          */
  56         for (i = 0; i < count; ++i)
  57             client_poll(info_ary[i]);
  58
  59         /*
  60          * Find the best client (or synthesize one).  If we find one
  61          * then program the frequency correction and offset.
  62          *
  63          * client_check may replace the server_info pointer with a new
  64          * one.
  65          */
  66         best = NULL;
  67         for (i = 0; i < count; ++i)
  68             best = client_check(&info_ary[i], best);
  69         if (best) {
  70             offset = best->lin_sumoffset / best->lin_count;
  71             freq = sysntp_correct_offset(offset);
  72             sysntp_correct_freq(best->lin_cache_freq + freq);
  73         }
  74         if (debug_sleep)
  75             usleep(debug_sleep * 1000000 + random() % 100000);
  76         else
  77             usleep(60 * 1000000 + random() % 100000);
  78     }
  79 }
  80
  81 void
  82 client_poll(server_info_t info)
  83 {
  84     struct timeval rtv;
  85     struct timeval ltv;
  86     struct timeval lbtv;
  87     double offset;
  88
  89     if (debug_opt) {
  90         fprintf(stderr, "%s: poll, ", info->target);
  91         fflush(stderr);
  92     }
  93     if (udp_ntptimereq(info->fd, &rtv, &ltv, &lbtv) < 0) {
  94         if (debug_opt)
  95             fprintf(stderr, "no response\n");
  96         return;
  97     }
  98
  99     /*
 100      * Figure out the offset (the difference between the reported
 101      * time and our current time) for linear regression purposes.
 102      */
 103     offset = tv_delta_micro(&rtv, &ltv) / 1000000.0;
 104
 105     while (info) {
 106         /*
 107          * Linear regression
 108          */
 109         if (debug_opt) {
 110             struct tm *tp;
 111             char buf[64];
 112             time_t t;
 113
 114             t = rtv.tv_sec;
 115             tp = localtime(&t);
 116             strftime(buf, sizeof(buf), "%d-%b-%Y %H:%M:%S", tp);
 117             fprintf(stderr, "%s.%03ld ",
 118                     buf, rtv.tv_usec / 1000);
 119         }
 120         lin_regress(info, &ltv, &lbtv, offset);
 121         info = info->altinfo;
 122         if (info && debug_opt) {
 123             fprintf(stderr, "%*.*s: poll, ",
 124                 (int)strlen(info->target),
 125                 (int)strlen(info->target),
 126                 "(alt)");
 127             fflush(stderr);
 128         }
 129     }
 130 }
 131
 132 /*
 133  * Find the best client (or synthesize a fake info structure to return)
 134  */
 135 struct server_info *
 136 client_check(struct server_info **checkp, struct server_info *best)
 137 {
 138     struct server_info *check = *checkp;
 139     struct server_info *info;
 140
 141     /*
 142      * Start an alternate linear regression once our current one
 143      * has passed a certain point.
 144      */
 145     if (check->lin_count >= LIN_RESTART / 2 && check->altinfo == NULL) {
 146         info = malloc(sizeof(*info));
 147         assert(info != NULL);
 148         bcopy(check, info, sizeof(*info));
 149         check->altinfo = info;
 150         lin_reset(info);
 151     }
 152
 153     /*
 154      * Replace our current linear regression with the alternate once
 155      * the current one has hit its limit (beyond a certain point the
 156      * linear regression starts to work against us, preventing us from
 157      * reacting to changing conditions).
 158      *
 159      * Report any significant change in the offset or ppm.
 160      */
 161     if (check->lin_count >= LIN_RESTART) {
 162         if ((info = check->altinfo) && info->lin_count >= LIN_RESTART / 2) {
 163             double freq_diff;
 164
 165             if (debug_opt) {
 166                 freq_diff = info->lin_cache_freq - check->lin_cache_freq;
 167                 printf("%s: Switching to alternate, Frequence difference is %6.3f ppm\n",
 168                         info->target, freq_diff * 1.0E+6);
 169             }
 170             *checkp = info;
 171             free(check);
 172             check = info;
 173         }
 174     }
 175
 176     /*
 177      * Required for selection:
 178      *
 179      *  8 samples and a correllation > 0.99, or
 180      * 16 samples and a correllation > 0.96
 181      */
 182     if ((check->lin_count >= 8 && fabs(check->lin_cache_corr) >= 0.99) ||
 183         (check->lin_count >= 16 && fabs(check->lin_cache_corr) >= 0.96)
 184     ) {
 185         if (best == NULL ||
 186             fabs(check->lin_cache_corr) > fabs(best->lin_cache_corr)) {
 187                 best = check;
 188         }
 189
 190     }
 191     return(best);
 192 }
 193
 194 /*
 195  * Linear regression.
 196  *
 197  *      ltv     local time as of when the offset error was calculated between
 198  *              local time and remote time.
 199  *
 200  *      lbtv    base time as of when local time was obtained.  Used to
 201  *              calculate the cumulative corrections made to the system's
 202  *              real time clock so we can de-correct the offset for the
 203  *              linear regression.
 204  *
 205  * X is the time axis, in seconds.
 206  * Y is the uncorrected offset, in seconds.
 207  */
 208 void
 209 lin_regress(server_info_t info, struct timeval *ltv, struct timeval *lbtv,
 210             double offset)
 211 {
 212     double time_axis;
 213     double uncorrected_offset;
 214
 215     if (info->lin_count == 0) {
 216         info->lin_tv = *ltv;
 217         info->lin_btv = *lbtv;
 218         time_axis = 0;
 219         uncorrected_offset = offset;
 220     } else {
 221         time_axis = tv_delta_micro(&info->lin_tv, ltv) / 1000000.0;
 222         uncorrected_offset = offset -
 223                         tv_delta_micro(&info->lin_btv, lbtv) / 1000000.0;
 224     }
 225     ++info->lin_count;
 226     info->lin_sumx += time_axis;
 227     info->lin_sumx2 += time_axis * time_axis;
 228     info->lin_sumy += uncorrected_offset;
 229     info->lin_sumy2 += uncorrected_offset * uncorrected_offset;
 230     info->lin_sumxy += time_axis * uncorrected_offset;
 231     info->lin_sumoffset += uncorrected_offset;
 232
 233     /*
 234      * Calculate various derived values (from statistics).
 235      */
 236
 237     if (info->lin_count > 1) {
 238         info->lin_cache_slope =
 239          (info->lin_count * info->lin_sumxy - info->lin_sumx * info->lin_sumy) /
 240          (info->lin_count * info->lin_sumx2 - info->lin_sumx * info->lin_sumx);
 241
 242         info->lin_cache_yint =
 243          (info->lin_sumy - info->lin_cache_slope * info->lin_sumx) /
 244          (info->lin_count);
 245
 246         info->lin_cache_corr =
 247          (info->lin_count * info->lin_sumxy - info->lin_sumx * info->lin_sumy) /
 248          sqrt((info->lin_count * info->lin_sumx2 -
 249                       info->lin_sumx * info->lin_sumx) *
 250              (info->lin_count * info->lin_sumy2 -
 251                       info->lin_sumy * info->lin_sumy)
 252          );
 253     }
 254
 255     /*
 256      * Calculate the offset and frequency correction
 257      */
 258     info->lin_cache_offset = offset;
 259     info->lin_cache_freq = info->lin_cache_slope;
 260
 261     if (debug_opt) {
 262         fprintf(stderr, "iter=%2d time=%7.3f off=%.6f uoff=%.6f",
 263             (int)info->lin_count,
 264             time_axis, offset, uncorrected_offset);
 265         if (info->lin_count > 1) {
 266             fprintf(stderr, " slope %7.6f"
 267                             " yint %3.2f corr %7.6f freq_ppm %4.2f",
 268                 info->lin_cache_slope,
 269                 info->lin_cache_yint,
 270                 info->lin_cache_corr,
 271                 info->lin_cache_freq * 1000000.0);
 272         }
 273         fprintf(stderr, "\n");
 274     }
 275 }
 276
 277 void
 278 lin_reset(server_info_t info)
 279 {
 280     info->lin_count = 0;
 281     info->lin_sumx = 0;
 282     info->lin_sumy = 0;
 283     info->lin_sumxy = 0;
 284     info->lin_sumx2 = 0;
 285     info->lin_sumy2 = 0;
 286     info->lin_sumoffset = 0;
 287
 288     info->lin_cache_slope = 0;
 289     info->lin_cache_yint = 0;
 290     info->lin_cache_corr = 0;
 291     info->lin_cache_offset = 0;
 292     info->lin_cache_freq = 0;
 293 }
 294