networkdelta.c revision 360338
1255570Strasz/*- 2255570Strasz * Copyright (c) 1985, 1993 3255570Strasz * The Regents of the University of California. All rights reserved. 4255570Strasz * 5255570Strasz * Redistribution and use in source and binary forms, with or without 6255570Strasz * modification, are permitted provided that the following conditions 7255570Strasz * are met: 8255570Strasz * 1. Redistributions of source code must retain the above copyright 9255570Strasz * notice, this list of conditions and the following disclaimer. 10255570Strasz * 2. Redistributions in binary form must reproduce the above copyright 11255570Strasz * notice, this list of conditions and the following disclaimer in the 12255570Strasz * documentation and/or other materials provided with the distribution. 13255570Strasz * 4. Neither the name of the University nor the names of its contributors 14255570Strasz * may be used to endorse or promote products derived from this software 15255570Strasz * without specific prior written permission. 16255570Strasz * 17255570Strasz * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18255570Strasz * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19255570Strasz * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20255570Strasz * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21255570Strasz * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22255570Strasz * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23255570Strasz * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24255570Strasz * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25255570Strasz * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26255570Strasz * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27255570Strasz * SUCH DAMAGE. 28255570Strasz */ 29255570Strasz 30255570Strasz#ifndef lint 31255570Strasz#if 0 32255570Straszstatic char sccsid[] = "@(#)networkdelta.c 8.1 (Berkeley) 6/6/93"; 33255570Strasz#endif 34255570Straszstatic const char rcsid[] = 35255570Strasz "$FreeBSD: stable/10/usr.sbin/timed/timed/networkdelta.c 360338 2020-04-26 15:50:32Z dim $"; 36255570Strasz#endif /* not lint */ 37270888Strasz 38270888Strasz#include "globals.h" 39270888Strasz 40316253Sngiestatic long median(float, float *, long *, long *, unsigned int); 41316253Sngie 42316253Sngie/* 43255570Strasz * Compute a corrected date. 44255570Strasz * Compute the median of the reasonable differences. First compute 45255570Strasz * the median of all authorized differences, and then compute the 46255570Strasz * median of all differences that are reasonably close to the first 47316253Sngie * median. 48255570Strasz * 49255570Strasz * This differs from the original BSD implementation, which looked for 50255570Strasz * the largest group of machines with essentially the same date. 51255570Strasz * That assumed that machines with bad clocks would be uniformly 52255570Strasz * distributed. Unfortunately, in real life networks, the distribution 53255570Strasz * of machines is not uniform among models of machines, and the 54255570Strasz * distribution of errors in clocks tends to be quite consistent 55255570Strasz * for a given model. In other words, all model VI Supre Servres 56255570Strasz * from GoFast Inc. tend to have about the same error. 57255570Strasz * The original BSD implementation would chose the clock of the 58255570Strasz * most common model, and discard all others. 59255570Strasz * 60255570Strasz * Therefore, get best we can do is to try to average over all 61255570Strasz * of the machines in the network, while discarding "obviously" 62255570Strasz * bad values. 63255570Strasz */ 64255570Straszlong 65255570Strasznetworkdelta(void) 66255570Strasz{ 67265507Strasz struct hosttbl *htp; 68265507Strasz long med; 69255570Strasz long lodelta, hidelta; 70255570Strasz long logood, higood; 71255570Strasz long x[NHOSTS]; 72255570Strasz long *xp; 73265507Strasz int numdelta; 74255570Strasz float eps; 75255570Strasz 76255570Strasz /* 77255570Strasz * compute the median of the good values 78255570Strasz */ 79255570Strasz med = 0; 80255570Strasz numdelta = 1; 81255570Strasz xp = &x[0]; 82255570Strasz *xp = 0; /* account for ourself */ 83255665Strasz for (htp = self.l_fwd; htp != &self; htp = htp->l_fwd) { 84255570Strasz if (htp->good 85255570Strasz && htp->noanswer == 0 86255570Strasz && htp->delta != HOSTDOWN) { 87255570Strasz med += htp->delta; 88255570Strasz numdelta++; 89255570Strasz *++xp = htp->delta; 90255570Strasz } 91255570Strasz } 92255570Strasz 93255570Strasz /* 94255570Strasz * If we are the only trusted time keeper, then do not change our 95255570Strasz * clock. There may be another time keeping service active. 96255570Strasz */ 97255570Strasz if (numdelta == 1) 98255570Strasz return 0; 99255570Strasz 100255570Strasz med /= numdelta; 101255570Strasz eps = med - x[0]; 102255570Strasz if (trace) 103255570Strasz fprintf(fd, "median of %d values starting at %ld is about ", 104255570Strasz numdelta, med); 105274870Strasz med = median(med, &eps, &x[0], xp+1, VALID_RANGE); 106255570Strasz 107255570Strasz /* 108255570Strasz * compute the median of all values near the good median 109255570Strasz */ 110288810Smav hidelta = med + GOOD_RANGE; 111255570Strasz lodelta = med - GOOD_RANGE; 112255570Strasz higood = med + VGOOD_RANGE; 113255570Strasz logood = med - VGOOD_RANGE; 114255570Strasz xp = &x[0]; 115279002Smav htp = &self; 116255570Strasz do { 117255570Strasz if (htp->noanswer == 0 118255570Strasz && htp->delta >= lodelta 119255570Strasz && htp->delta <= hidelta 120268682Smav && (htp->good 121268682Smav || (htp->delta >= logood 122288785Smav && htp->delta <= higood))) { 123279055Smav *xp++ = htp->delta; 124284908Smav } 125284908Smav } while (&self != (htp = htp->l_fwd)); 126279006Smav 127268682Smav if (xp == &x[0]) { 128268682Smav if (trace) 129279006Smav fprintf(fd, "nothing close to median %ld\n", med); 130268682Smav return med; 131268682Smav } 132268682Smav 133268682Smav if (xp == &x[1]) { 134255570Strasz if (trace) 135255570Strasz fprintf(fd, "only value near median is %ld\n", x[0]); 136255570Strasz return x[0]; 137255570Strasz } 138268682Smav 139268682Smav if (trace) 140268682Smav fprintf(fd, "median of %td values starting at %ld is ", 141255570Strasz xp-&x[0], med); 142255570Strasz return median(med, &eps, &x[0], xp, 1); 143255570Strasz} 144255570Strasz 145255570Strasz 146255570Strasz/* 147255570Strasz * compute the median of an array of signed integers, using the idea 148255570Strasz * in <<Numerical Recipes>>. 149255570Strasz */ 150255570Straszstatic long 151255570Straszmedian(float a, float *eps_ptr, long *x, long *xlim, unsigned int gnuf) 152255570Strasz /* float a; */ /* initial guess for the median */ 153255570Strasz /* float *eps_ptr; */ /* spacing near the median */ 154255570Strasz /* long *x, *xlim; */ /* the data */ 155256189Strasz /* unsigned int gnuf; */ /* good enough estimate */ 156255570Strasz{ 157255570Strasz long *xptr; 158255570Strasz float ap = (float)LONG_MAX; /* bounds on the median */ 159255570Strasz float am = -(float)LONG_MAX; 160255570Strasz float aa; 161255570Strasz int npts; /* # of points above & below guess */ 162255570Strasz float xp; /* closet point above the guess */ 163255570Strasz float xm; /* closet point below the guess */ 164255570Strasz float eps; 165255570Strasz float dum, sum, sumx; 166255570Strasz int pass; 167255570Strasz#define AMP 1.5 /* smoothing constants */ 168255570Strasz#define AFAC 1.5 169255570Strasz 170255570Strasz eps = *eps_ptr; 171255570Strasz if (eps < 1.0) { 172255570Strasz eps = -eps; 173255570Strasz if (eps < 1.0) 174255570Strasz eps = 1.0; 175255570Strasz } 176255570Strasz 177255570Strasz for (pass = 1; ; pass++) { /* loop over the data */ 178255570Strasz sum = 0.0; 179255570Strasz sumx = 0.0; 180255570Strasz npts = 0; 181255570Strasz xp = (float)LONG_MAX; 182255570Strasz xm = -(float)LONG_MAX; 183255570Strasz 184255570Strasz for (xptr = x; xptr != xlim; xptr++) { 185255570Strasz float xx = *xptr; 186255570Strasz 187255570Strasz dum = xx - a; 188255570Strasz if (dum != 0.0) { /* avoid dividing by 0 */ 189255570Strasz if (dum > 0.0) { 190255570Strasz npts++; 191255570Strasz if (xx < xp) 192255570Strasz xp = xx; 193255570Strasz } else { 194255570Strasz npts--; 195255570Strasz if (xx > xm) 196255570Strasz xm = xx; 197255570Strasz dum = -dum; 198255570Strasz } 199255570Strasz dum = 1.0/(eps + dum); 200255570Strasz sum += dum; 201255570Strasz sumx += xx * dum; 202255570Strasz } 203255570Strasz } 204255570Strasz 205255570Strasz if (ap-am < gnuf || sum == 0) { 206255570Strasz if (trace) 207255570Strasz fprintf(fd, 208255570Strasz "%ld in %d passes; early out balance=%d\n", 209255570Strasz (long)a, pass, npts); 210255570Strasz return a; /* guess was good enough */ 211255570Strasz } 212255570Strasz 213255570Strasz aa = (sumx/sum-a)*AMP; 214255570Strasz if (npts >= 2) { /* guess was too low */ 215255570Strasz am = a; 216255570Strasz aa = xp + max(0.0, aa); 217255570Strasz if (aa > ap) 218255570Strasz aa = (a + ap)/2; 219255570Strasz 220255570Strasz } else if (npts <= -2) { /* guess was two high */ 221255570Strasz ap = a; 222255570Strasz aa = xm + min(0.0, aa); 223255570Strasz if (aa < am) 224288810Smav aa = (a + am)/2; 225288810Smav 226255570Strasz } else { 227255570Strasz break; /* got it */ 228255570Strasz } 229255570Strasz 230255570Strasz if (a == aa) { 231255570Strasz if (trace) 232255570Strasz fprintf(fd, 233255570Strasz "%ld in %d passes; force out balance=%d\n", 234255570Strasz (long)a, pass, npts); 235255570Strasz return a; 236279002Smav } 237279002Smav eps = AFAC*abs(aa - a); 238255570Strasz *eps_ptr = eps; 239255570Strasz a = aa; 240255570Strasz } 241255570Strasz 242274870Strasz if (((x - xlim) % 2) != 0) { /* even number of points? */ 243255570Strasz if (npts == 0) /* yes, return an average */ 244255570Strasz a = (xp+xm)/2; 245255570Strasz else if (npts > 0) 246255570Strasz a = (a+xp)/2; 247255570Strasz else 248255570Strasz a = (xm+a)/2; 249255570Strasz 250255570Strasz } else if (npts != 0) { /* odd number of points */ 251255570Strasz if (npts > 0) 252255570Strasz a = xp; 253255570Strasz else 254255570Strasz a = xm; 255255570Strasz } 256255570Strasz 257255570Strasz if (trace) 258255570Strasz fprintf(fd, "%ld in %d passes\n", (long)a, pass); 259255570Strasz return a; 260255570Strasz} 261255570Strasz