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