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