1 /*- 2 * Copyright (c) 1985, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 */ 7 8 #ifndef lint 9 static char sccsid[] = "@(#)networkdelta.c 8.1 (Berkeley) 06/06/93"; 10 #endif /* not lint */ 11 12 #ifdef sgi 13 #ident "$Revision: 1.4 $" 14 #endif 15 16 #include "globals.h" 17 18 static long median __P((float, float *, long *, long *, unsigned int)); 19 20 /* 21 * Compute a corrected date. 22 * Compute the median of the reasonable differences. First compute 23 * the median of all authorized differences, and then compute the 24 * median of all differences that are reasonably close to the first 25 * median. 26 * 27 * This differs from the original BSD implementation, which looked for 28 * the largest group of machines with essentially the same date. 29 * That assumed that machines with bad clocks would be uniformly 30 * distributed. Unfortunately, in real life networks, the distribution 31 * of machines is not uniform among models of machines, and the 32 * distribution of errors in clocks tends to be quite consistent 33 * for a given model. In other words, all model VI Supre Servres 34 * from GoFast Inc. tend to have about the same error. 35 * The original BSD implementation would chose the clock of the 36 * most common model, and discard all others. 37 * 38 * Therefore, get best we can do is to try to average over all 39 * of the machines in the network, while discarding "obviously" 40 * bad values. 41 */ 42 long 43 networkdelta() 44 { 45 struct hosttbl *htp; 46 long med; 47 long lodelta, hidelta; 48 long logood, higood; 49 long x[NHOSTS]; 50 long *xp; 51 int numdelta; 52 float eps; 53 54 /* 55 * compute the median of the good values 56 */ 57 med = 0; 58 numdelta = 1; 59 xp = &x[0]; 60 *xp = 0; /* account for ourself */ 61 for (htp = self.l_fwd; htp != &self; htp = htp->l_fwd) { 62 if (htp->good 63 && htp->noanswer == 0 64 && htp->delta != HOSTDOWN) { 65 med += htp->delta; 66 numdelta++; 67 *++xp = htp->delta; 68 } 69 } 70 71 /* 72 * If we are the only trusted time keeper, then do not change our 73 * clock. There may be another time keeping service active. 74 */ 75 if (numdelta == 1) 76 return 0; 77 78 med /= numdelta; 79 eps = med - x[0]; 80 if (trace) 81 fprintf(fd, "median of %d values starting at %ld is about ", 82 numdelta, med); 83 med = median(med, &eps, &x[0], xp+1, VALID_RANGE); 84 85 /* 86 * compute the median of all values near the good median 87 */ 88 hidelta = med + GOOD_RANGE; 89 lodelta = med - GOOD_RANGE; 90 higood = med + VGOOD_RANGE; 91 logood = med - VGOOD_RANGE; 92 xp = &x[0]; 93 htp = &self; 94 do { 95 if (htp->noanswer == 0 96 && htp->delta >= lodelta 97 && htp->delta <= hidelta 98 && (htp->good 99 || (htp->delta >= logood 100 && htp->delta <= higood))) { 101 *xp++ = htp->delta; 102 } 103 } while (&self != (htp = htp->l_fwd)); 104 105 if (xp == &x[0]) { 106 if (trace) 107 fprintf(fd, "nothing close to median %ld\n", med); 108 return med; 109 } 110 111 if (xp == &x[1]) { 112 if (trace) 113 fprintf(fd, "only value near median is %ld\n", x[0]); 114 return x[0]; 115 } 116 117 if (trace) 118 fprintf(fd, "median of %d values starting at %ld is ", 119 xp-&x[0], med); 120 return median(med, &eps, &x[0], xp, 1); 121 } 122 123 124 /* 125 * compute the median of an array of signed integers, using the idea 126 * in <<Numerical Recipes>>. 127 */ 128 static long 129 median(a, eps_ptr, x, xlim, gnuf) 130 float a; /* initial guess for the median */ 131 float *eps_ptr; /* spacing near the median */ 132 long *x, *xlim; /* the data */ 133 unsigned int gnuf; /* good enough estimate */ 134 { 135 long *xptr; 136 float ap = LONG_MAX; /* bounds on the median */ 137 float am = -LONG_MAX; 138 float aa; 139 int npts; /* # of points above & below guess */ 140 float xp; /* closet point above the guess */ 141 float xm; /* closet point below the guess */ 142 float eps; 143 float dum, sum, sumx; 144 int pass; 145 #define AMP 1.5 /* smoothing constants */ 146 #define AFAC 1.5 147 148 eps = *eps_ptr; 149 if (eps < 1.0) { 150 eps = -eps; 151 if (eps < 1.0) 152 eps = 1.0; 153 } 154 155 for (pass = 1; ; pass++) { /* loop over the data */ 156 sum = 0.0; 157 sumx = 0.0; 158 npts = 0; 159 xp = LONG_MAX; 160 xm = -LONG_MAX; 161 162 for (xptr = x; xptr != xlim; xptr++) { 163 float xx = *xptr; 164 165 dum = xx - a; 166 if (dum != 0.0) { /* avoid dividing by 0 */ 167 if (dum > 0.0) { 168 npts++; 169 if (xx < xp) 170 xp = xx; 171 } else { 172 npts--; 173 if (xx > xm) 174 xm = xx; 175 dum = -dum; 176 } 177 dum = 1.0/(eps + dum); 178 sum += dum; 179 sumx += xx * dum; 180 } 181 } 182 183 if (ap-am < gnuf || sum == 0) { 184 if (trace) 185 fprintf(fd, 186 "%ld in %d passes; early out balance=%d\n", 187 (long)a, pass, npts); 188 return a; /* guess was good enough */ 189 } 190 191 aa = (sumx/sum-a)*AMP; 192 if (npts >= 2) { /* guess was too low */ 193 am = a; 194 aa = xp + max(0.0, aa);; 195 if (aa > ap) 196 aa = (a + ap)/2; 197 198 } else if (npts <= -2) { /* guess was two high */ 199 ap = a; 200 aa = xm + min(0.0, aa);; 201 if (aa < am) 202 aa = (a + am)/2; 203 204 } else { 205 break; /* got it */ 206 } 207 208 if (a == aa) { 209 if (trace) 210 fprintf(fd, 211 "%ld in %d passes; force out balance=%d\n", 212 (long)a, pass, npts); 213 return a; 214 } 215 eps = AFAC*abs(aa - a); 216 *eps_ptr = eps; 217 a = aa; 218 } 219 220 if (((x - xlim) % 2) != 0) { /* even number of points? */ 221 if (npts == 0) /* yes, return an average */ 222 a = (xp+xm)/2; 223 else if (npts > 0) 224 a = (a+xp)/2; 225 else 226 a = (xm+a)/2; 227 228 } else if (npts != 0) { /* odd number of points */ 229 if (npts > 0) 230 a = xp; 231 else 232 a = xm; 233 } 234 235 if (trace) 236 fprintf(fd, "%ld in %d passes\n", (long)a, pass); 237 return a; 238 } 239