2 * Copyright (c) 1985, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
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 $
40 static long median(float, float *, long *, long *, unsigned int);
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
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.
60 * Therefore, get best we can do is to try to average over all
61 * of the machines in the network, while discarding "obviously"
69 long lodelta
, hidelta
;
77 * compute the median of the good values
82 *xp
= 0; /* account for ourself */
83 for (htp
= self
.l_fwd
; htp
!= &self
; htp
= htp
->l_fwd
) {
86 && htp
->delta
!= HOSTDOWN
) {
94 * If we are the only trusted time keeper, then do not change our
95 * clock. There may be another time keeping service active.
103 fprintf(fd
, "median of %d values starting at %ld is about ",
105 med
= median(med
, &eps
, &x
[0], xp
+1, VALID_RANGE
);
108 * compute the median of all values near the good median
110 hidelta
= med
+ GOOD_RANGE
;
111 lodelta
= med
- GOOD_RANGE
;
112 higood
= med
+ VGOOD_RANGE
;
113 logood
= med
- VGOOD_RANGE
;
117 if (htp
->noanswer
== 0
118 && htp
->delta
>= lodelta
119 && htp
->delta
<= hidelta
121 || (htp
->delta
>= logood
122 && htp
->delta
<= higood
))) {
125 } while (&self
!= (htp
= htp
->l_fwd
));
129 fprintf(fd
, "nothing close to median %ld\n", med
);
135 fprintf(fd
, "only value near median is %ld\n", x
[0]);
140 fprintf(fd
, "median of %td values starting at %ld is ",
142 return median(med
, &eps
, &x
[0], xp
, 1);
147 * compute the median of an array of signed integers, using the idea
148 * in <<Numerical Recipes>>.
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 */
157 float ap
= LONG_MAX
; /* bounds on the median */
158 float am
= -LONG_MAX
;
160 int npts
; /* # of points above & below guess */
161 float xp
; /* closet point above the guess */
162 float xm
; /* closet point below the guess */
164 float dum
, sum
, sumx
;
166 #define AMP 1.5 /* smoothing constants */
176 for (pass
= 1; ; pass
++) { /* loop over the data */
183 for (xptr
= x
; xptr
!= xlim
; xptr
++) {
187 if (dum
!= 0.0) { /* avoid dividing by 0 */
198 dum
= 1.0/(eps
+ dum
);
204 if (ap
-am
< gnuf
|| sum
== 0) {
207 "%ld in %d passes; early out balance=%d\n",
208 (long)a
, pass
, npts
);
209 return a
; /* guess was good enough */
212 aa
= (sumx
/sum
-a
)*AMP
;
213 if (npts
>= 2) { /* guess was too low */
215 aa
= xp
+ max(0.0, aa
);
219 } else if (npts
<= -2) { /* guess was two high */
221 aa
= xm
+ min(0.0, aa
);
232 "%ld in %d passes; force out balance=%d\n",
233 (long)a
, pass
, npts
);
236 eps
= AFAC
*abs(aa
- a
);
241 if (((x
- xlim
) % 2) != 0) { /* even number of points? */
242 if (npts
== 0) /* yes, return an average */
249 } else if (npts
!= 0) { /* odd number of points */
257 fprintf(fd
, "%ld in %d passes\n", (long)a
, pass
);