networkdelta.c revision 267654
190075Sobrien/*- 2169689Skan * Copyright (c) 1985, 1993 3169689Skan * The Regents of the University of California. All rights reserved. 4169689Skan * 590075Sobrien * Redistribution and use in source and binary forms, with or without 690075Sobrien * modification, are permitted provided that the following conditions 7132718Skan * are met: 890075Sobrien * 1. Redistributions of source code must retain the above copyright 9132718Skan * notice, this list of conditions and the following disclaimer. 10132718Skan * 2. Redistributions in binary form must reproduce the above copyright 11132718Skan * notice, this list of conditions and the following disclaimer in the 12132718Skan * documentation and/or other materials provided with the distribution. 1390075Sobrien * 4. Neither the name of the University nor the names of its contributors 14132718Skan * may be used to endorse or promote products derived from this software 15132718Skan * without specific prior written permission. 16132718Skan * 17132718Skan * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 1890075Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19132718Skan * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20132718Skan * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21169689Skan * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22169689Skan * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2390075Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2490075Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2590075Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26132718Skan * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27132718Skan * SUCH DAMAGE. 2890075Sobrien */ 2990075Sobrien 3090075Sobrien#ifndef lint 3190075Sobrien#if 0 3290075Sobrienstatic char sccsid[] = "@(#)networkdelta.c 8.1 (Berkeley) 6/6/93"; 3390075Sobrien#endif 3490075Sobrienstatic const char rcsid[] = 3590075Sobrien "$FreeBSD: releng/9.3/usr.sbin/timed/timed/networkdelta.c 229247 2012-01-01 23:49:11Z dim $"; 3690075Sobrien#endif /* not lint */ 3790075Sobrien 3890075Sobrien#include "globals.h" 3990075Sobrien 4090075Sobrienstatic long median(float, float *, long *, long *, unsigned int); 4190075Sobrien 4290075Sobrien/* 4390075Sobrien * Compute a corrected date. 4490075Sobrien * Compute the median of the reasonable differences. First compute 4590075Sobrien * the median of all authorized differences, and then compute the 4690075Sobrien * median of all differences that are reasonably close to the first 4790075Sobrien * median. 4890075Sobrien * 4990075Sobrien * This differs from the original BSD implementation, which looked for 5090075Sobrien * the largest group of machines with essentially the same date. 5190075Sobrien * That assumed that machines with bad clocks would be uniformly 5290075Sobrien * distributed. Unfortunately, in real life networks, the distribution 5390075Sobrien * of machines is not uniform among models of machines, and the 54132718Skan * distribution of errors in clocks tends to be quite consistent 55132718Skan * for a given model. In other words, all model VI Supre Servres 56169689Skan * from GoFast Inc. tend to have about the same error. 57169689Skan * The original BSD implementation would chose the clock of the 58169689Skan * most common model, and discard all others. 59169689Skan * 60132718Skan * Therefore, get best we can do is to try to average over all 61132718Skan * of the machines in the network, while discarding "obviously" 62132718Skan * bad values. 63169689Skan */ 64169689Skanlong 65169689Skannetworkdelta() 6690075Sobrien{ 6790075Sobrien struct hosttbl *htp; 6890075Sobrien long med; 6990075Sobrien long lodelta, hidelta; 7090075Sobrien long logood, higood; 7190075Sobrien long x[NHOSTS]; 7290075Sobrien long *xp; 7390075Sobrien int numdelta; 74132718Skan float eps; 75132718Skan 76132718Skan /* 77132718Skan * compute the median of the good values 78132718Skan */ 79132718Skan med = 0; 80132718Skan numdelta = 1; 81132718Skan xp = &x[0]; 82132718Skan *xp = 0; /* account for ourself */ 83132718Skan for (htp = self.l_fwd; htp != &self; htp = htp->l_fwd) { 84169689Skan if (htp->good 85169689Skan && htp->noanswer == 0 86132718Skan && htp->delta != HOSTDOWN) { 87132718Skan med += htp->delta; 88132718Skan numdelta++; 89132718Skan *++xp = htp->delta; 90132718Skan } 91132718Skan } 92132718Skan 93132718Skan /* 94132718Skan * If we are the only trusted time keeper, then do not change our 95132718Skan * clock. There may be another time keeping service active. 96132718Skan */ 97132718Skan if (numdelta == 1) 98132718Skan return 0; 99132718Skan 100132718Skan med /= numdelta; 101132718Skan eps = med - x[0]; 102132718Skan if (trace) 103132718Skan fprintf(fd, "median of %d values starting at %ld is about ", 104132718Skan numdelta, med); 105132718Skan med = median(med, &eps, &x[0], xp+1, VALID_RANGE); 106132718Skan 107132718Skan /* 108132718Skan * compute the median of all values near the good median 109132718Skan */ 110132718Skan hidelta = med + GOOD_RANGE; 111132718Skan lodelta = med - GOOD_RANGE; 112132718Skan higood = med + VGOOD_RANGE; 113132718Skan logood = med - VGOOD_RANGE; 114169689Skan xp = &x[0]; 115169689Skan htp = &self; 116169689Skan do { 117169689Skan if (htp->noanswer == 0 118169689Skan && htp->delta >= lodelta 119169689Skan && htp->delta <= hidelta 120169689Skan && (htp->good 121169689Skan || (htp->delta >= logood 122169689Skan && htp->delta <= higood))) { 123169689Skan *xp++ = htp->delta; 124169689Skan } 125169689Skan } while (&self != (htp = htp->l_fwd)); 126169689Skan 127169689Skan if (xp == &x[0]) { 128169689Skan if (trace) 129169689Skan fprintf(fd, "nothing close to median %ld\n", med); 130169689Skan return med; 13190075Sobrien } 13290075Sobrien 13390075Sobrien if (xp == &x[1]) { 13490075Sobrien if (trace) 13590075Sobrien fprintf(fd, "only value near median is %ld\n", x[0]); 13690075Sobrien return x[0]; 13790075Sobrien } 13890075Sobrien 13990075Sobrien if (trace) 14090075Sobrien fprintf(fd, "median of %td values starting at %ld is ", 14190075Sobrien xp-&x[0], med); 142132718Skan return median(med, &eps, &x[0], xp, 1); 143132718Skan} 144132718Skan 145132718Skan 146132718Skan/* 147132718Skan * compute the median of an array of signed integers, using the idea 148132718Skan * in <<Numerical Recipes>>. 149132718Skan */ 150132718Skanstatic long 151132718Skanmedian(float a, float *eps_ptr, long *x, long *xlim, unsigned int gnuf) 152132718Skan /* float a; */ /* initial guess for the median */ 153132718Skan /* float *eps_ptr; */ /* spacing near the median */ 154132718Skan /* long *x, *xlim; */ /* the data */ 155132718Skan /* unsigned int gnuf; */ /* good enough estimate */ 156169689Skan{ 157169689Skan long *xptr; 158169689Skan float ap = LONG_MAX; /* bounds on the median */ 159169689Skan float am = -LONG_MAX; 16090075Sobrien float aa; 16190075Sobrien int npts; /* # of points above & below guess */ 162169689Skan float xp; /* closet point above the guess */ 163169689Skan float xm; /* closet point below the guess */ 164169689Skan float eps; 165169689Skan float dum, sum, sumx; 16690075Sobrien int pass; 16790075Sobrien#define AMP 1.5 /* smoothing constants */ 168117395Skan#define AFAC 1.5 169117395Skan 170117395Skan eps = *eps_ptr; 171132718Skan if (eps < 1.0) { 172132718Skan eps = -eps; 173132718Skan if (eps < 1.0) 174169689Skan eps = 1.0; 175169689Skan } 176132718Skan 177117395Skan for (pass = 1; ; pass++) { /* loop over the data */ 178132718Skan sum = 0.0; 17990075Sobrien sumx = 0.0; 18090075Sobrien npts = 0; 18190075Sobrien xp = LONG_MAX; 18290075Sobrien xm = -LONG_MAX; 18390075Sobrien 18490075Sobrien for (xptr = x; xptr != xlim; xptr++) { 18590075Sobrien float xx = *xptr; 18690075Sobrien 18790075Sobrien dum = xx - a; 18890075Sobrien if (dum != 0.0) { /* avoid dividing by 0 */ 18990075Sobrien if (dum > 0.0) { 19090075Sobrien npts++; 191132718Skan if (xx < xp) 19290075Sobrien xp = xx; 19390075Sobrien } else { 19490075Sobrien npts--; 19590075Sobrien if (xx > xm) 19690075Sobrien xm = xx; 19790075Sobrien dum = -dum; 19890075Sobrien } 19990075Sobrien dum = 1.0/(eps + dum); 20090075Sobrien sum += dum; 20190075Sobrien sumx += xx * dum; 20290075Sobrien } 203132718Skan } 204132718Skan 205132718Skan if (ap-am < gnuf || sum == 0) { 206132718Skan if (trace) 20790075Sobrien fprintf(fd, 20890075Sobrien "%ld in %d passes; early out balance=%d\n", 20990075Sobrien (long)a, pass, npts); 210169689Skan return a; /* guess was good enough */ 211169689Skan } 21290075Sobrien 21390075Sobrien aa = (sumx/sum-a)*AMP; 21490075Sobrien if (npts >= 2) { /* guess was too low */ 21590075Sobrien am = a; 21690075Sobrien aa = xp + max(0.0, aa); 21790075Sobrien if (aa > ap) 218169689Skan aa = (a + ap)/2; 219169689Skan 220132718Skan } else if (npts <= -2) { /* guess was two high */ 221169689Skan ap = a; 222146895Skan aa = xm + min(0.0, aa); 223169689Skan if (aa < am) 224169689Skan aa = (a + am)/2; 225146895Skan 226117395Skan } else { 227117395Skan break; /* got it */ 228117395Skan } 229117395Skan 230117395Skan if (a == aa) { 231117395Skan if (trace) 232117395Skan fprintf(fd, 233117395Skan "%ld in %d passes; force out balance=%d\n", 23490075Sobrien (long)a, pass, npts); 23590075Sobrien return a; 23690075Sobrien } 23790075Sobrien eps = AFAC*abs(aa - a); 238169689Skan *eps_ptr = eps; 239169689Skan a = aa; 240169689Skan } 241169689Skan 242169689Skan if (((x - xlim) % 2) != 0) { /* even number of points? */ 24390075Sobrien if (npts == 0) /* yes, return an average */ 244132718Skan a = (xp+xm)/2; 245132718Skan else if (npts > 0) 246132718Skan a = (a+xp)/2; 247132718Skan else 248169689Skan a = (xm+a)/2; 249169689Skan 250169689Skan } else if (npts != 0) { /* odd number of points */ 251169689Skan if (npts > 0) 252169689Skan a = xp; 253169689Skan else 254169689Skan a = xm; 255169689Skan } 256169689Skan 257169689Skan if (trace) 258169689Skan fprintf(fd, "%ld in %d passes\n", (long)a, pass); 259169689Skan return a; 260117395Skan} 261117395Skan