networkdelta.c revision 330897
1/*- 2 * SPDX-License-Identifier: BSD-3-Clause 3 * 4 * Copyright (c) 1985, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 4. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 */ 31 32#ifndef lint 33#if 0 34static char sccsid[] = "@(#)networkdelta.c 8.1 (Berkeley) 6/6/93"; 35#endif 36static const char rcsid[] = 37 "$FreeBSD: stable/11/usr.sbin/timed/timed/networkdelta.c 330897 2018-03-14 03:19:51Z eadler $"; 38#endif /* not lint */ 39 40#include "globals.h" 41 42static long median(float, float *, long *, long *, unsigned int); 43 44/* 45 * Compute a corrected date. 46 * Compute the median of the reasonable differences. First compute 47 * the median of all authorized differences, and then compute the 48 * median of all differences that are reasonably close to the first 49 * median. 50 * 51 * This differs from the original BSD implementation, which looked for 52 * the largest group of machines with essentially the same date. 53 * That assumed that machines with bad clocks would be uniformly 54 * distributed. Unfortunately, in real life networks, the distribution 55 * of machines is not uniform among models of machines, and the 56 * distribution of errors in clocks tends to be quite consistent 57 * for a given model. In other words, all model VI Supre Servres 58 * from GoFast Inc. tend to have about the same error. 59 * The original BSD implementation would chose the clock of the 60 * most common model, and discard all others. 61 * 62 * Therefore, get best we can do is to try to average over all 63 * of the machines in the network, while discarding "obviously" 64 * bad values. 65 */ 66long 67networkdelta(void) 68{ 69 struct hosttbl *htp; 70 long med; 71 long lodelta, hidelta; 72 long logood, higood; 73 long x[NHOSTS]; 74 long *xp; 75 int numdelta; 76 float eps; 77 78 /* 79 * compute the median of the good values 80 */ 81 med = 0; 82 numdelta = 1; 83 xp = &x[0]; 84 *xp = 0; /* account for ourself */ 85 for (htp = self.l_fwd; htp != &self; htp = htp->l_fwd) { 86 if (htp->good 87 && htp->noanswer == 0 88 && htp->delta != HOSTDOWN) { 89 med += htp->delta; 90 numdelta++; 91 *++xp = htp->delta; 92 } 93 } 94 95 /* 96 * If we are the only trusted time keeper, then do not change our 97 * clock. There may be another time keeping service active. 98 */ 99 if (numdelta == 1) 100 return 0; 101 102 med /= numdelta; 103 eps = med - x[0]; 104 if (trace) 105 fprintf(fd, "median of %d values starting at %ld is about ", 106 numdelta, med); 107 med = median(med, &eps, &x[0], xp+1, VALID_RANGE); 108 109 /* 110 * compute the median of all values near the good median 111 */ 112 hidelta = med + GOOD_RANGE; 113 lodelta = med - GOOD_RANGE; 114 higood = med + VGOOD_RANGE; 115 logood = med - VGOOD_RANGE; 116 xp = &x[0]; 117 htp = &self; 118 do { 119 if (htp->noanswer == 0 120 && htp->delta >= lodelta 121 && htp->delta <= hidelta 122 && (htp->good 123 || (htp->delta >= logood 124 && htp->delta <= higood))) { 125 *xp++ = htp->delta; 126 } 127 } while (&self != (htp = htp->l_fwd)); 128 129 if (xp == &x[0]) { 130 if (trace) 131 fprintf(fd, "nothing close to median %ld\n", med); 132 return med; 133 } 134 135 if (xp == &x[1]) { 136 if (trace) 137 fprintf(fd, "only value near median is %ld\n", x[0]); 138 return x[0]; 139 } 140 141 if (trace) 142 fprintf(fd, "median of %td values starting at %ld is ", 143 xp-&x[0], med); 144 return median(med, &eps, &x[0], xp, 1); 145} 146 147 148/* 149 * compute the median of an array of signed integers, using the idea 150 * in <<Numerical Recipes>>. 151 */ 152static long 153median(float a, float *eps_ptr, long *x, long *xlim, unsigned int gnuf) 154 /* float a; */ /* initial guess for the median */ 155 /* float *eps_ptr; */ /* spacing near the median */ 156 /* long *x, *xlim; */ /* the data */ 157 /* unsigned int gnuf; */ /* good enough estimate */ 158{ 159 long *xptr; 160 float ap = LONG_MAX; /* bounds on the median */ 161 float am = -LONG_MAX; 162 float aa; 163 int npts; /* # of points above & below guess */ 164 float xp; /* closet point above the guess */ 165 float xm; /* closet point below the guess */ 166 float eps; 167 float dum, sum, sumx; 168 int pass; 169#define AMP 1.5 /* smoothing constants */ 170#define AFAC 1.5 171 172 eps = *eps_ptr; 173 if (eps < 1.0) { 174 eps = -eps; 175 if (eps < 1.0) 176 eps = 1.0; 177 } 178 179 for (pass = 1; ; pass++) { /* loop over the data */ 180 sum = 0.0; 181 sumx = 0.0; 182 npts = 0; 183 xp = LONG_MAX; 184 xm = -LONG_MAX; 185 186 for (xptr = x; xptr != xlim; xptr++) { 187 float xx = *xptr; 188 189 dum = xx - a; 190 if (dum != 0.0) { /* avoid dividing by 0 */ 191 if (dum > 0.0) { 192 npts++; 193 if (xx < xp) 194 xp = xx; 195 } else { 196 npts--; 197 if (xx > xm) 198 xm = xx; 199 dum = -dum; 200 } 201 dum = 1.0/(eps + dum); 202 sum += dum; 203 sumx += xx * dum; 204 } 205 } 206 207 if (ap-am < gnuf || sum == 0) { 208 if (trace) 209 fprintf(fd, 210 "%ld in %d passes; early out balance=%d\n", 211 (long)a, pass, npts); 212 return a; /* guess was good enough */ 213 } 214 215 aa = (sumx/sum-a)*AMP; 216 if (npts >= 2) { /* guess was too low */ 217 am = a; 218 aa = xp + max(0.0, aa); 219 if (aa > ap) 220 aa = (a + ap)/2; 221 222 } else if (npts <= -2) { /* guess was two high */ 223 ap = a; 224 aa = xm + min(0.0, aa); 225 if (aa < am) 226 aa = (a + am)/2; 227 228 } else { 229 break; /* got it */ 230 } 231 232 if (a == aa) { 233 if (trace) 234 fprintf(fd, 235 "%ld in %d passes; force out balance=%d\n", 236 (long)a, pass, npts); 237 return a; 238 } 239 eps = AFAC*abs(aa - a); 240 *eps_ptr = eps; 241 a = aa; 242 } 243 244 if (((x - xlim) % 2) != 0) { /* even number of points? */ 245 if (npts == 0) /* yes, return an average */ 246 a = (xp+xm)/2; 247 else if (npts > 0) 248 a = (a+xp)/2; 249 else 250 a = (xm+a)/2; 251 252 } else if (npts != 0) { /* odd number of points */ 253 if (npts > 0) 254 a = xp; 255 else 256 a = xm; 257 } 258 259 if (trace) 260 fprintf(fd, "%ld in %d passes\n", (long)a, pass); 261 return a; 262} 263