Commit | Line | Data |
---|---|---|
984263bc MD |
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. | |
1de703da MD |
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 $ | |
320b887a | 35 | * $DragonFly: src/usr.sbin/timed/timed/networkdelta.c,v 1.4 2004/03/13 21:08:38 eirikn Exp $ |
984263bc | 36 | */ |
984263bc MD |
37 | |
38 | #include "globals.h" | |
39 | ||
2d8a3be7 | 40 | static long median(float, float *, long *, long *, unsigned int); |
984263bc MD |
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 | |
320b887a | 65 | networkdelta(void) |
984263bc MD |
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) | |
e11cf02d | 140 | fprintf(fd, "median of %td values starting at %ld is ", |
984263bc MD |
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 | |
320b887a EN |
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 */ | |
984263bc MD |
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 | } |