File:  [DragonFly] / src / usr.sbin / timed / timed / networkdelta.c
Revision 1.4: download - view: text, annotated - select for diffs
Sat Mar 13 21:08:38 2004 UTC (10 years, 6 months ago) by eirikn
Branches: MAIN
CVS tags: HEAD, DragonFly_Stable, DragonFly_Snap29Sep2004, DragonFly_Snap13Sep2004, DragonFly_RELEASE_2_0_Slip, DragonFly_RELEASE_2_0, DragonFly_RELEASE_1_8_Slip, DragonFly_RELEASE_1_8, DragonFly_RELEASE_1_6_Slip, DragonFly_RELEASE_1_6, DragonFly_RELEASE_1_4_Slip, DragonFly_RELEASE_1_4, DragonFly_RELEASE_1_2_Slip, DragonFly_RELEASE_1_2, DragonFly_RELEASE_1_12_Slip, DragonFly_RELEASE_1_12, DragonFly_RELEASE_1_10_Slip, DragonFly_RELEASE_1_10, DragonFly_Preview, DragonFly_1_0_REL, DragonFly_1_0_RC1, DragonFly_1_0A_REL
 * Remove ``register'' keywords.
 * Convert K&R-style function declarations to ANSI-style.

Submitted by: Chris Pressey <cpressey@catseye.mine.nu>

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