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