timed.tproj/timed.tproj/networkdelta.c

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