11553Srgrimes/*- 21553Srgrimes * Copyright (c) 1985, 1993 31553Srgrimes * The Regents of the University of California. All rights reserved. 41553Srgrimes * 51553Srgrimes * Redistribution and use in source and binary forms, with or without 61553Srgrimes * modification, are permitted provided that the following conditions 71553Srgrimes * are met: 81553Srgrimes * 1. Redistributions of source code must retain the above copyright 91553Srgrimes * notice, this list of conditions and the following disclaimer. 101553Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111553Srgrimes * notice, this list of conditions and the following disclaimer in the 121553Srgrimes * documentation and/or other materials provided with the distribution. 131553Srgrimes * 4. Neither the name of the University nor the names of its contributors 141553Srgrimes * may be used to endorse or promote products derived from this software 151553Srgrimes * without specific prior written permission. 161553Srgrimes * 171553Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181553Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191553Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201553Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211553Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221553Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231553Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241553Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251553Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261553Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271553Srgrimes * SUCH DAMAGE. 281553Srgrimes */ 291553Srgrimes 301553Srgrimes#ifndef lint 3130642Scharnier#if 0 321553Srgrimesstatic char sccsid[] = "@(#)networkdelta.c 8.1 (Berkeley) 6/6/93"; 3330642Scharnier#endif 3430642Scharnierstatic const char rcsid[] = 3550479Speter "$FreeBSD$"; 361553Srgrimes#endif /* not lint */ 371553Srgrimes 381553Srgrimes#include "globals.h" 391553Srgrimes 40173412Skevlostatic long median(float, float *, long *, long *, unsigned int); 411553Srgrimes 421553Srgrimes/* 431553Srgrimes * Compute a corrected date. 441553Srgrimes * Compute the median of the reasonable differences. First compute 451553Srgrimes * the median of all authorized differences, and then compute the 461553Srgrimes * median of all differences that are reasonably close to the first 471553Srgrimes * median. 481553Srgrimes * 491553Srgrimes * This differs from the original BSD implementation, which looked for 501553Srgrimes * the largest group of machines with essentially the same date. 511553Srgrimes * That assumed that machines with bad clocks would be uniformly 521553Srgrimes * distributed. Unfortunately, in real life networks, the distribution 531553Srgrimes * of machines is not uniform among models of machines, and the 541553Srgrimes * distribution of errors in clocks tends to be quite consistent 551553Srgrimes * for a given model. In other words, all model VI Supre Servres 561553Srgrimes * from GoFast Inc. tend to have about the same error. 571553Srgrimes * The original BSD implementation would chose the clock of the 581553Srgrimes * most common model, and discard all others. 591553Srgrimes * 601553Srgrimes * Therefore, get best we can do is to try to average over all 611553Srgrimes * of the machines in the network, while discarding "obviously" 621553Srgrimes * bad values. 631553Srgrimes */ 641553Srgrimeslong 651553Srgrimesnetworkdelta() 661553Srgrimes{ 671553Srgrimes struct hosttbl *htp; 681553Srgrimes long med; 691553Srgrimes long lodelta, hidelta; 701553Srgrimes long logood, higood; 711553Srgrimes long x[NHOSTS]; 721553Srgrimes long *xp; 731553Srgrimes int numdelta; 741553Srgrimes float eps; 751553Srgrimes 761553Srgrimes /* 771553Srgrimes * compute the median of the good values 781553Srgrimes */ 791553Srgrimes med = 0; 801553Srgrimes numdelta = 1; 811553Srgrimes xp = &x[0]; 821553Srgrimes *xp = 0; /* account for ourself */ 831553Srgrimes for (htp = self.l_fwd; htp != &self; htp = htp->l_fwd) { 841553Srgrimes if (htp->good 851553Srgrimes && htp->noanswer == 0 861553Srgrimes && htp->delta != HOSTDOWN) { 871553Srgrimes med += htp->delta; 881553Srgrimes numdelta++; 891553Srgrimes *++xp = htp->delta; 901553Srgrimes } 911553Srgrimes } 921553Srgrimes 931553Srgrimes /* 941553Srgrimes * If we are the only trusted time keeper, then do not change our 951553Srgrimes * clock. There may be another time keeping service active. 961553Srgrimes */ 971553Srgrimes if (numdelta == 1) 981553Srgrimes return 0; 991553Srgrimes 1001553Srgrimes med /= numdelta; 1011553Srgrimes eps = med - x[0]; 1021553Srgrimes if (trace) 1031553Srgrimes fprintf(fd, "median of %d values starting at %ld is about ", 1041553Srgrimes numdelta, med); 1051553Srgrimes med = median(med, &eps, &x[0], xp+1, VALID_RANGE); 1061553Srgrimes 1071553Srgrimes /* 1081553Srgrimes * compute the median of all values near the good median 1091553Srgrimes */ 1101553Srgrimes hidelta = med + GOOD_RANGE; 1111553Srgrimes lodelta = med - GOOD_RANGE; 1121553Srgrimes higood = med + VGOOD_RANGE; 1131553Srgrimes logood = med - VGOOD_RANGE; 1141553Srgrimes xp = &x[0]; 1151553Srgrimes htp = &self; 1161553Srgrimes do { 1171553Srgrimes if (htp->noanswer == 0 1181553Srgrimes && htp->delta >= lodelta 1191553Srgrimes && htp->delta <= hidelta 1201553Srgrimes && (htp->good 1211553Srgrimes || (htp->delta >= logood 1221553Srgrimes && htp->delta <= higood))) { 1231553Srgrimes *xp++ = htp->delta; 1241553Srgrimes } 1251553Srgrimes } while (&self != (htp = htp->l_fwd)); 1261553Srgrimes 1271553Srgrimes if (xp == &x[0]) { 1281553Srgrimes if (trace) 1291553Srgrimes fprintf(fd, "nothing close to median %ld\n", med); 1301553Srgrimes return med; 1311553Srgrimes } 1321553Srgrimes 1331553Srgrimes if (xp == &x[1]) { 1341553Srgrimes if (trace) 1351553Srgrimes fprintf(fd, "only value near median is %ld\n", x[0]); 1361553Srgrimes return x[0]; 1371553Srgrimes } 1381553Srgrimes 1391553Srgrimes if (trace) 140229247Sdim fprintf(fd, "median of %td values starting at %ld is ", 1411553Srgrimes xp-&x[0], med); 1421553Srgrimes return median(med, &eps, &x[0], xp, 1); 1431553Srgrimes} 1441553Srgrimes 1451553Srgrimes 1461553Srgrimes/* 1471553Srgrimes * compute the median of an array of signed integers, using the idea 1481553Srgrimes * in <<Numerical Recipes>>. 1491553Srgrimes */ 1501553Srgrimesstatic long 151189090Sedmedian(float a, float *eps_ptr, long *x, long *xlim, unsigned int gnuf) 152189090Sed /* float a; */ /* initial guess for the median */ 153189090Sed /* float *eps_ptr; */ /* spacing near the median */ 154189090Sed /* long *x, *xlim; */ /* the data */ 155189090Sed /* unsigned int gnuf; */ /* good enough estimate */ 1561553Srgrimes{ 1571553Srgrimes long *xptr; 1581553Srgrimes float ap = LONG_MAX; /* bounds on the median */ 1591553Srgrimes float am = -LONG_MAX; 1601553Srgrimes float aa; 1611553Srgrimes int npts; /* # of points above & below guess */ 1621553Srgrimes float xp; /* closet point above the guess */ 1631553Srgrimes float xm; /* closet point below the guess */ 1641553Srgrimes float eps; 1651553Srgrimes float dum, sum, sumx; 1661553Srgrimes int pass; 1671553Srgrimes#define AMP 1.5 /* smoothing constants */ 1681553Srgrimes#define AFAC 1.5 1691553Srgrimes 1701553Srgrimes eps = *eps_ptr; 1711553Srgrimes if (eps < 1.0) { 1721553Srgrimes eps = -eps; 1731553Srgrimes if (eps < 1.0) 1741553Srgrimes eps = 1.0; 1751553Srgrimes } 1761553Srgrimes 1771553Srgrimes for (pass = 1; ; pass++) { /* loop over the data */ 1781553Srgrimes sum = 0.0; 1791553Srgrimes sumx = 0.0; 1801553Srgrimes npts = 0; 1811553Srgrimes xp = LONG_MAX; 1821553Srgrimes xm = -LONG_MAX; 1831553Srgrimes 1841553Srgrimes for (xptr = x; xptr != xlim; xptr++) { 1851553Srgrimes float xx = *xptr; 1861553Srgrimes 1871553Srgrimes dum = xx - a; 1881553Srgrimes if (dum != 0.0) { /* avoid dividing by 0 */ 1891553Srgrimes if (dum > 0.0) { 1901553Srgrimes npts++; 1911553Srgrimes if (xx < xp) 1921553Srgrimes xp = xx; 1931553Srgrimes } else { 1941553Srgrimes npts--; 1951553Srgrimes if (xx > xm) 1961553Srgrimes xm = xx; 1971553Srgrimes dum = -dum; 1981553Srgrimes } 1991553Srgrimes dum = 1.0/(eps + dum); 2001553Srgrimes sum += dum; 2011553Srgrimes sumx += xx * dum; 2021553Srgrimes } 2031553Srgrimes } 2041553Srgrimes 2051553Srgrimes if (ap-am < gnuf || sum == 0) { 2061553Srgrimes if (trace) 2071553Srgrimes fprintf(fd, 2081553Srgrimes "%ld in %d passes; early out balance=%d\n", 2091553Srgrimes (long)a, pass, npts); 2101553Srgrimes return a; /* guess was good enough */ 2111553Srgrimes } 2121553Srgrimes 2131553Srgrimes aa = (sumx/sum-a)*AMP; 2141553Srgrimes if (npts >= 2) { /* guess was too low */ 2151553Srgrimes am = a; 21660699Skris aa = xp + max(0.0, aa); 2171553Srgrimes if (aa > ap) 2181553Srgrimes aa = (a + ap)/2; 2191553Srgrimes 2201553Srgrimes } else if (npts <= -2) { /* guess was two high */ 2211553Srgrimes ap = a; 22260699Skris aa = xm + min(0.0, aa); 2231553Srgrimes if (aa < am) 2241553Srgrimes aa = (a + am)/2; 2251553Srgrimes 2261553Srgrimes } else { 2271553Srgrimes break; /* got it */ 2281553Srgrimes } 2291553Srgrimes 2301553Srgrimes if (a == aa) { 2311553Srgrimes if (trace) 2321553Srgrimes fprintf(fd, 2331553Srgrimes "%ld in %d passes; force out balance=%d\n", 2341553Srgrimes (long)a, pass, npts); 2351553Srgrimes return a; 2361553Srgrimes } 2371553Srgrimes eps = AFAC*abs(aa - a); 2381553Srgrimes *eps_ptr = eps; 2391553Srgrimes a = aa; 2401553Srgrimes } 2411553Srgrimes 2421553Srgrimes if (((x - xlim) % 2) != 0) { /* even number of points? */ 2431553Srgrimes if (npts == 0) /* yes, return an average */ 2441553Srgrimes a = (xp+xm)/2; 2451553Srgrimes else if (npts > 0) 2461553Srgrimes a = (a+xp)/2; 2471553Srgrimes else 2481553Srgrimes a = (xm+a)/2; 2491553Srgrimes 2501553Srgrimes } else if (npts != 0) { /* odd number of points */ 2511553Srgrimes if (npts > 0) 2521553Srgrimes a = xp; 2531553Srgrimes else 2541553Srgrimes a = xm; 2551553Srgrimes } 2561553Srgrimes 2571553Srgrimes if (trace) 2581553Srgrimes fprintf(fd, "%ld in %d passes\n", (long)a, pass); 2591553Srgrimes return a; 2601553Srgrimes} 261