usr.sbin/timed/timed/networkdelta.c

   1 /*-
   2  * Copyright (c) 1985, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by the University of
  16  *      California, Berkeley and its contributors.
  17  * 4. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  * @(#)networkdelta.c   8.1 (Berkeley) 6/6/93
  34  * $FreeBSD: src/usr.sbin/timed/timed/networkdelta.c,v 1.3.2.1 2000/07/01 01:28:10 ps Exp $
  35  * $DragonFly: src/usr.sbin/timed/timed/networkdelta.c,v 1.4 2004/03/13 21:08:38 eirikn Exp $
  36  */
  37
  38 #include "globals.h"
  39
  40 static long median(float, float *, long *, long *, unsigned int);
  41
  42 /*
  43  * Compute a corrected date.
  44  *      Compute the median of the reasonable differences.  First compute
  45  *      the median of all authorized differences, and then compute the
  46  *      median of all differences that are reasonably close to the first
  47  *      median.
  48  *
  49  * This differs from the original BSD implementation, which looked for
  50  *      the largest group of machines with essentially the same date.
  51  *      That assumed that machines with bad clocks would be uniformly
  52  *      distributed.  Unfortunately, in real life networks, the distribution
  53  *      of machines is not uniform among models of machines, and the
  54  *      distribution of errors in clocks tends to be quite consistent
  55  *      for a given model.  In other words, all model VI Supre Servres
  56  *      from GoFast Inc. tend to have about the same error.
  57  *      The original BSD implementation would chose the clock of the
  58  *      most common model, and discard all others.
  59  *
  60  *      Therefore, get best we can do is to try to average over all
  61  *      of the machines in the network, while discarding "obviously"
  62  *      bad values.
  63  */
  64 long
  65 networkdelta(void)
  66 {
  67         struct hosttbl *htp;
  68         long med;
  69         long lodelta, hidelta;
  70         long logood, higood;
  71         long x[NHOSTS];
  72         long *xp;
  73         int numdelta;
  74         float eps;
  75
  76         /*
  77          * compute the median of the good values
  78          */
  79         med = 0;
  80         numdelta = 1;
  81         xp = &x[0];
  82         *xp = 0;                        /* account for ourself */
  83         for (htp = self.l_fwd; htp != &self; htp = htp->l_fwd) {
  84                 if (htp->good
  85                     && htp->noanswer == 0
  86                     && htp->delta != HOSTDOWN) {
  87                         med += htp->delta;
  88                         numdelta++;
  89                         *++xp = htp->delta;
  90                 }
  91         }
  92
  93         /*
  94          * If we are the only trusted time keeper, then do not change our
  95          * clock.  There may be another time keeping service active.
  96          */
  97         if (numdelta == 1)
  98                 return 0;
  99
 100         med /= numdelta;
 101         eps = med - x[0];
 102         if (trace)
 103                 fprintf(fd, "median of %d values starting at %ld is about ",
 104                         numdelta, med);
 105         med = median(med, &eps, &x[0], xp+1, VALID_RANGE);
 106
 107         /*
 108          * compute the median of all values near the good median
 109          */
 110         hidelta = med + GOOD_RANGE;
 111         lodelta = med - GOOD_RANGE;
 112         higood = med + VGOOD_RANGE;
 113         logood = med - VGOOD_RANGE;
 114         xp = &x[0];
 115         htp = &self;
 116         do {
 117                 if (htp->noanswer == 0
 118                     && htp->delta >= lodelta
 119                     && htp->delta <= hidelta
 120                     && (htp->good
 121                         || (htp->delta >= logood
 122                             && htp->delta <= higood))) {
 123                         *xp++ = htp->delta;
 124                 }
 125         } while (&self != (htp = htp->l_fwd));
 126
 127         if (xp == &x[0]) {
 128                 if (trace)
 129                         fprintf(fd, "nothing close to median %ld\n", med);
 130                 return med;
 131         }
 132
 133         if (xp == &x[1]) {
 134                 if (trace)
 135                         fprintf(fd, "only value near median is %ld\n", x[0]);
 136                 return x[0];
 137         }
 138
 139         if (trace)
 140                 fprintf(fd, "median of %d values starting at %ld is ",
 141                         xp-&x[0], med);
 142         return median(med, &eps, &x[0], xp, 1);
 143 }
 144
 145
 146 /*
 147  * compute the median of an array of signed integers, using the idea
 148  *      in <<Numerical Recipes>>.
 149  */
 150 static long
 151 median(float a,                         /* initial guess for the median */
 152        float *eps_ptr,                  /* spacing near the median */
 153        long *x, long *xlim,             /* the data */
 154        unsigned int gnuf)               /* good enough estimate */
 155 {
 156         long *xptr;
 157         float ap = LONG_MAX;            /* bounds on the median */
 158         float am = -LONG_MAX;
 159         float aa;
 160         int npts;                       /* # of points above & below guess */
 161         float xp;                       /* closet point above the guess */
 162         float xm;                       /* closet point below the guess */
 163         float eps;
 164         float dum, sum, sumx;
 165         int pass;
 166 #define AMP     1.5                     /* smoothing constants */
 167 #define AFAC    1.5
 168
 169         eps = *eps_ptr;
 170         if (eps < 1.0) {
 171                 eps = -eps;
 172                 if (eps < 1.0)
 173                         eps = 1.0;
 174         }
 175
 176         for (pass = 1; ; pass++) {      /* loop over the data */
 177                 sum = 0.0;
 178                 sumx = 0.0;
 179                 npts = 0;
 180                 xp = LONG_MAX;
 181                 xm = -LONG_MAX;
 182
 183                 for (xptr = x; xptr != xlim; xptr++) {
 184                         float xx = *xptr;
 185
 186                         dum = xx - a;
 187                         if (dum != 0.0) {       /* avoid dividing by 0 */
 188                                 if (dum > 0.0) {
 189                                         npts++;
 190                                         if (xx < xp)
 191                                                 xp = xx;
 192                                 } else {
 193                                         npts--;
 194                                         if (xx > xm)
 195                                                 xm = xx;
 196                                         dum = -dum;
 197                                 }
 198                                 dum = 1.0/(eps + dum);
 199                                 sum += dum;
 200                                 sumx += xx * dum;
 201                         }
 202                 }
 203
 204                 if (ap-am < gnuf || sum == 0) {
 205                         if (trace)
 206                                 fprintf(fd,
 207                                    "%ld in %d passes; early out balance=%d\n",
 208                                         (long)a, pass, npts);
 209                         return a;       /* guess was good enough */
 210                 }
 211
 212                 aa = (sumx/sum-a)*AMP;
 213                 if (npts >= 2) {        /* guess was too low */
 214                         am = a;
 215                         aa = xp + max(0.0, aa);
 216                         if (aa > ap)
 217                                 aa = (a + ap)/2;
 218
 219                 } else if (npts <= -2) {  /* guess was two high */
 220                         ap = a;
 221                         aa = xm + min(0.0, aa);
 222                         if (aa < am)
 223                                 aa = (a + am)/2;
 224
 225                 } else {
 226                         break;          /* got it */
 227                 }
 228
 229                 if (a == aa) {
 230                         if (trace)
 231                                 fprintf(fd,
 232                                   "%ld in %d passes; force out balance=%d\n",
 233                                         (long)a, pass, npts);
 234                         return a;
 235                 }
 236                 eps = AFAC*abs(aa - a);
 237                 *eps_ptr = eps;
 238                 a = aa;
 239         }
 240
 241         if (((x - xlim) % 2) != 0) {    /* even number of points? */
 242                 if (npts == 0)          /* yes, return an average */
 243                         a = (xp+xm)/2;
 244                 else if (npts > 0)
 245                         a =  (a+xp)/2;
 246                 else
 247                         a = (xm+a)/2;
 248
 249         } else  if (npts != 0) {        /* odd number of points */
 250                 if (npts > 0)
 251                         a = xp;
 252                 else
 253                         a = xm;
 254         }
 255
 256         if (trace)
 257                 fprintf(fd, "%ld in %d passes\n", (long)a, pass);
 258         return a;
 259 }