xref: /netbsd-src/sys/kern/kern_clock.c (revision da5f4674a3fc214be3572d358b66af40ab9401e7)
1 /*	$NetBSD: kern_clock.c,v 1.87 2003/08/07 16:31:42 agc Exp $	*/
2 
3 /*-
4  * Copyright (c) 2000 The NetBSD Foundation, Inc.
5  * All rights reserved.
6  *
7  * This code is derived from software contributed to The NetBSD Foundation
8  * by Jason R. Thorpe of the Numerical Aerospace Simulation Facility,
9  * NASA Ames Research Center.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions and the following disclaimer.
16  * 2. Redistributions in binary form must reproduce the above copyright
17  *    notice, this list of conditions and the following disclaimer in the
18  *    documentation and/or other materials provided with the distribution.
19  * 3. All advertising materials mentioning features or use of this software
20  *    must display the following acknowledgement:
21  *	This product includes software developed by the NetBSD
22  *	Foundation, Inc. and its contributors.
23  * 4. Neither the name of The NetBSD Foundation nor the names of its
24  *    contributors may be used to endorse or promote products derived
25  *    from this software without specific prior written permission.
26  *
27  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
28  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
29  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
30  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
31  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
32  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
33  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
34  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
35  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
36  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
37  * POSSIBILITY OF SUCH DAMAGE.
38  */
39 
40 /*-
41  * Copyright (c) 1982, 1986, 1991, 1993
42  *	The Regents of the University of California.  All rights reserved.
43  * (c) UNIX System Laboratories, Inc.
44  * All or some portions of this file are derived from material licensed
45  * to the University of California by American Telephone and Telegraph
46  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
47  * the permission of UNIX System Laboratories, Inc.
48  *
49  * Redistribution and use in source and binary forms, with or without
50  * modification, are permitted provided that the following conditions
51  * are met:
52  * 1. Redistributions of source code must retain the above copyright
53  *    notice, this list of conditions and the following disclaimer.
54  * 2. Redistributions in binary form must reproduce the above copyright
55  *    notice, this list of conditions and the following disclaimer in the
56  *    documentation and/or other materials provided with the distribution.
57  * 3. Neither the name of the University nor the names of its contributors
58  *    may be used to endorse or promote products derived from this software
59  *    without specific prior written permission.
60  *
61  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
62  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
63  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
64  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
65  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
66  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
67  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
68  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
69  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
70  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
71  * SUCH DAMAGE.
72  *
73  *	@(#)kern_clock.c	8.5 (Berkeley) 1/21/94
74  */
75 
76 #include <sys/cdefs.h>
77 __KERNEL_RCSID(0, "$NetBSD: kern_clock.c,v 1.87 2003/08/07 16:31:42 agc Exp $");
78 
79 #include "opt_ntp.h"
80 #include "opt_multiprocessor.h"
81 #include "opt_perfctrs.h"
82 
83 #include <sys/param.h>
84 #include <sys/systm.h>
85 #include <sys/callout.h>
86 #include <sys/kernel.h>
87 #include <sys/proc.h>
88 #include <sys/resourcevar.h>
89 #include <sys/signalvar.h>
90 #include <sys/sysctl.h>
91 #include <sys/timex.h>
92 #include <sys/sched.h>
93 #include <sys/time.h>
94 
95 #include <machine/cpu.h>
96 #ifdef __HAVE_GENERIC_SOFT_INTERRUPTS
97 #include <machine/intr.h>
98 #endif
99 
100 #ifdef GPROF
101 #include <sys/gmon.h>
102 #endif
103 
104 /*
105  * Clock handling routines.
106  *
107  * This code is written to operate with two timers that run independently of
108  * each other.  The main clock, running hz times per second, is used to keep
109  * track of real time.  The second timer handles kernel and user profiling,
110  * and does resource use estimation.  If the second timer is programmable,
111  * it is randomized to avoid aliasing between the two clocks.  For example,
112  * the randomization prevents an adversary from always giving up the cpu
113  * just before its quantum expires.  Otherwise, it would never accumulate
114  * cpu ticks.  The mean frequency of the second timer is stathz.
115  *
116  * If no second timer exists, stathz will be zero; in this case we drive
117  * profiling and statistics off the main clock.  This WILL NOT be accurate;
118  * do not do it unless absolutely necessary.
119  *
120  * The statistics clock may (or may not) be run at a higher rate while
121  * profiling.  This profile clock runs at profhz.  We require that profhz
122  * be an integral multiple of stathz.
123  *
124  * If the statistics clock is running fast, it must be divided by the ratio
125  * profhz/stathz for statistics.  (For profiling, every tick counts.)
126  */
127 
128 #ifdef NTP	/* NTP phase-locked loop in kernel */
129 /*
130  * Phase/frequency-lock loop (PLL/FLL) definitions
131  *
132  * The following variables are read and set by the ntp_adjtime() system
133  * call.
134  *
135  * time_state shows the state of the system clock, with values defined
136  * in the timex.h header file.
137  *
138  * time_status shows the status of the system clock, with bits defined
139  * in the timex.h header file.
140  *
141  * time_offset is used by the PLL/FLL to adjust the system time in small
142  * increments.
143  *
144  * time_constant determines the bandwidth or "stiffness" of the PLL.
145  *
146  * time_tolerance determines maximum frequency error or tolerance of the
147  * CPU clock oscillator and is a property of the architecture; however,
148  * in principle it could change as result of the presence of external
149  * discipline signals, for instance.
150  *
151  * time_precision is usually equal to the kernel tick variable; however,
152  * in cases where a precision clock counter or external clock is
153  * available, the resolution can be much less than this and depend on
154  * whether the external clock is working or not.
155  *
156  * time_maxerror is initialized by a ntp_adjtime() call and increased by
157  * the kernel once each second to reflect the maximum error bound
158  * growth.
159  *
160  * time_esterror is set and read by the ntp_adjtime() call, but
161  * otherwise not used by the kernel.
162  */
163 int time_state = TIME_OK;	/* clock state */
164 int time_status = STA_UNSYNC;	/* clock status bits */
165 long time_offset = 0;		/* time offset (us) */
166 long time_constant = 0;		/* pll time constant */
167 long time_tolerance = MAXFREQ;	/* frequency tolerance (scaled ppm) */
168 long time_precision = 1;	/* clock precision (us) */
169 long time_maxerror = MAXPHASE;	/* maximum error (us) */
170 long time_esterror = MAXPHASE;	/* estimated error (us) */
171 
172 /*
173  * The following variables establish the state of the PLL/FLL and the
174  * residual time and frequency offset of the local clock. The scale
175  * factors are defined in the timex.h header file.
176  *
177  * time_phase and time_freq are the phase increment and the frequency
178  * increment, respectively, of the kernel time variable.
179  *
180  * time_freq is set via ntp_adjtime() from a value stored in a file when
181  * the synchronization daemon is first started. Its value is retrieved
182  * via ntp_adjtime() and written to the file about once per hour by the
183  * daemon.
184  *
185  * time_adj is the adjustment added to the value of tick at each timer
186  * interrupt and is recomputed from time_phase and time_freq at each
187  * seconds rollover.
188  *
189  * time_reftime is the second's portion of the system time at the last
190  * call to ntp_adjtime(). It is used to adjust the time_freq variable
191  * and to increase the time_maxerror as the time since last update
192  * increases.
193  */
194 long time_phase = 0;		/* phase offset (scaled us) */
195 long time_freq = 0;		/* frequency offset (scaled ppm) */
196 long time_adj = 0;		/* tick adjust (scaled 1 / hz) */
197 long time_reftime = 0;		/* time at last adjustment (s) */
198 
199 #ifdef PPS_SYNC
200 /*
201  * The following variables are used only if the kernel PPS discipline
202  * code is configured (PPS_SYNC). The scale factors are defined in the
203  * timex.h header file.
204  *
205  * pps_time contains the time at each calibration interval, as read by
206  * microtime(). pps_count counts the seconds of the calibration
207  * interval, the duration of which is nominally pps_shift in powers of
208  * two.
209  *
210  * pps_offset is the time offset produced by the time median filter
211  * pps_tf[], while pps_jitter is the dispersion (jitter) measured by
212  * this filter.
213  *
214  * pps_freq is the frequency offset produced by the frequency median
215  * filter pps_ff[], while pps_stabil is the dispersion (wander) measured
216  * by this filter.
217  *
218  * pps_usec is latched from a high resolution counter or external clock
219  * at pps_time. Here we want the hardware counter contents only, not the
220  * contents plus the time_tv.usec as usual.
221  *
222  * pps_valid counts the number of seconds since the last PPS update. It
223  * is used as a watchdog timer to disable the PPS discipline should the
224  * PPS signal be lost.
225  *
226  * pps_glitch counts the number of seconds since the beginning of an
227  * offset burst more than tick/2 from current nominal offset. It is used
228  * mainly to suppress error bursts due to priority conflicts between the
229  * PPS interrupt and timer interrupt.
230  *
231  * pps_intcnt counts the calibration intervals for use in the interval-
232  * adaptation algorithm. It's just too complicated for words.
233  */
234 struct timeval pps_time;	/* kernel time at last interval */
235 long pps_tf[] = {0, 0, 0};	/* pps time offset median filter (us) */
236 long pps_offset = 0;		/* pps time offset (us) */
237 long pps_jitter = MAXTIME;	/* time dispersion (jitter) (us) */
238 long pps_ff[] = {0, 0, 0};	/* pps frequency offset median filter */
239 long pps_freq = 0;		/* frequency offset (scaled ppm) */
240 long pps_stabil = MAXFREQ;	/* frequency dispersion (scaled ppm) */
241 long pps_usec = 0;		/* microsec counter at last interval */
242 long pps_valid = PPS_VALID;	/* pps signal watchdog counter */
243 int pps_glitch = 0;		/* pps signal glitch counter */
244 int pps_count = 0;		/* calibration interval counter (s) */
245 int pps_shift = PPS_SHIFT;	/* interval duration (s) (shift) */
246 int pps_intcnt = 0;		/* intervals at current duration */
247 
248 /*
249  * PPS signal quality monitors
250  *
251  * pps_jitcnt counts the seconds that have been discarded because the
252  * jitter measured by the time median filter exceeds the limit MAXTIME
253  * (100 us).
254  *
255  * pps_calcnt counts the frequency calibration intervals, which are
256  * variable from 4 s to 256 s.
257  *
258  * pps_errcnt counts the calibration intervals which have been discarded
259  * because the wander exceeds the limit MAXFREQ (100 ppm) or where the
260  * calibration interval jitter exceeds two ticks.
261  *
262  * pps_stbcnt counts the calibration intervals that have been discarded
263  * because the frequency wander exceeds the limit MAXFREQ / 4 (25 us).
264  */
265 long pps_jitcnt = 0;		/* jitter limit exceeded */
266 long pps_calcnt = 0;		/* calibration intervals */
267 long pps_errcnt = 0;		/* calibration errors */
268 long pps_stbcnt = 0;		/* stability limit exceeded */
269 #endif /* PPS_SYNC */
270 
271 #ifdef EXT_CLOCK
272 /*
273  * External clock definitions
274  *
275  * The following definitions and declarations are used only if an
276  * external clock is configured on the system.
277  */
278 #define CLOCK_INTERVAL 30	/* CPU clock update interval (s) */
279 
280 /*
281  * The clock_count variable is set to CLOCK_INTERVAL at each PPS
282  * interrupt and decremented once each second.
283  */
284 int clock_count = 0;		/* CPU clock counter */
285 
286 #ifdef HIGHBALL
287 /*
288  * The clock_offset and clock_cpu variables are used by the HIGHBALL
289  * interface. The clock_offset variable defines the offset between
290  * system time and the HIGBALL counters. The clock_cpu variable contains
291  * the offset between the system clock and the HIGHBALL clock for use in
292  * disciplining the kernel time variable.
293  */
294 extern struct timeval clock_offset; /* Highball clock offset */
295 long clock_cpu = 0;		/* CPU clock adjust */
296 #endif /* HIGHBALL */
297 #endif /* EXT_CLOCK */
298 #endif /* NTP */
299 
300 
301 /*
302  * Bump a timeval by a small number of usec's.
303  */
304 #define BUMPTIME(t, usec) { \
305 	volatile struct timeval *tp = (t); \
306 	long us; \
307  \
308 	tp->tv_usec = us = tp->tv_usec + (usec); \
309 	if (us >= 1000000) { \
310 		tp->tv_usec = us - 1000000; \
311 		tp->tv_sec++; \
312 	} \
313 }
314 
315 int	stathz;
316 int	profhz;
317 int	profsrc;
318 int	schedhz;
319 int	profprocs;
320 int	hardclock_ticks;
321 static int psdiv;			/* prof => stat divider */
322 int	psratio;			/* ratio: prof / stat */
323 int	tickfix, tickfixinterval;	/* used if tick not really integral */
324 #ifndef NTP
325 static int tickfixcnt;			/* accumulated fractional error */
326 #else
327 int	fixtick;			/* used by NTP for same */
328 int	shifthz;
329 #endif
330 
331 /*
332  * We might want ldd to load the both words from time at once.
333  * To succeed we need to be quadword aligned.
334  * The sparc already does that, and that it has worked so far is a fluke.
335  */
336 volatile struct	timeval time  __attribute__((__aligned__(__alignof__(quad_t))));
337 volatile struct	timeval mono_time;
338 
339 void	*softclock_si;
340 
341 /*
342  * Initialize clock frequencies and start both clocks running.
343  */
344 void
345 initclocks(void)
346 {
347 	int i;
348 
349 #ifdef __HAVE_GENERIC_SOFT_INTERRUPTS
350 	softclock_si = softintr_establish(IPL_SOFTCLOCK, softclock, NULL);
351 	if (softclock_si == NULL)
352 		panic("initclocks: unable to register softclock intr");
353 #endif
354 
355 	/*
356 	 * Set divisors to 1 (normal case) and let the machine-specific
357 	 * code do its bit.
358 	 */
359 	psdiv = 1;
360 	cpu_initclocks();
361 
362 	/*
363 	 * Compute profhz/stathz/rrticks, and fix profhz if needed.
364 	 */
365 	i = stathz ? stathz : hz;
366 	if (profhz == 0)
367 		profhz = i;
368 	psratio = profhz / i;
369 	rrticks = hz / 10;
370 
371 #ifdef NTP
372 	switch (hz) {
373 	case 1:
374 		shifthz = SHIFT_SCALE - 0;
375 		break;
376 	case 2:
377 		shifthz = SHIFT_SCALE - 1;
378 		break;
379 	case 4:
380 		shifthz = SHIFT_SCALE - 2;
381 		break;
382 	case 8:
383 		shifthz = SHIFT_SCALE - 3;
384 		break;
385 	case 16:
386 		shifthz = SHIFT_SCALE - 4;
387 		break;
388 	case 32:
389 		shifthz = SHIFT_SCALE - 5;
390 		break;
391 	case 60:
392 	case 64:
393 		shifthz = SHIFT_SCALE - 6;
394 		break;
395 	case 96:
396 	case 100:
397 	case 128:
398 		shifthz = SHIFT_SCALE - 7;
399 		break;
400 	case 256:
401 		shifthz = SHIFT_SCALE - 8;
402 		break;
403 	case 512:
404 		shifthz = SHIFT_SCALE - 9;
405 		break;
406 	case 1000:
407 	case 1024:
408 		shifthz = SHIFT_SCALE - 10;
409 		break;
410 	case 1200:
411 	case 2048:
412 		shifthz = SHIFT_SCALE - 11;
413 		break;
414 	case 4096:
415 		shifthz = SHIFT_SCALE - 12;
416 		break;
417 	case 8192:
418 		shifthz = SHIFT_SCALE - 13;
419 		break;
420 	case 16384:
421 		shifthz = SHIFT_SCALE - 14;
422 		break;
423 	case 32768:
424 		shifthz = SHIFT_SCALE - 15;
425 		break;
426 	case 65536:
427 		shifthz = SHIFT_SCALE - 16;
428 		break;
429 	default:
430 		panic("weird hz");
431 	}
432 	if (fixtick == 0) {
433 		/*
434 		 * Give MD code a chance to set this to a better
435 		 * value; but, if it doesn't, we should.
436 		 */
437 		fixtick = (1000000 - (hz*tick));
438 	}
439 #endif
440 }
441 
442 /*
443  * The real-time timer, interrupting hz times per second.
444  */
445 void
446 hardclock(struct clockframe *frame)
447 {
448 	struct lwp *l;
449 	struct proc *p;
450 	int delta;
451 	extern int tickdelta;
452 	extern long timedelta;
453 	struct cpu_info *ci = curcpu();
454 	struct ptimer *pt;
455 #ifdef NTP
456 	int time_update;
457 	int ltemp;
458 #endif
459 
460 	l = curlwp;
461 	if (l) {
462 		p = l->l_proc;
463 		/*
464 		 * Run current process's virtual and profile time, as needed.
465 		 */
466 		if (CLKF_USERMODE(frame) && p->p_timers &&
467 		    (pt = LIST_FIRST(&p->p_timers->pts_virtual)) != NULL)
468 			if (itimerdecr(pt, tick) == 0)
469 				itimerfire(pt);
470 		if (p->p_timers &&
471 		    (pt = LIST_FIRST(&p->p_timers->pts_prof)) != NULL)
472 			if (itimerdecr(pt, tick) == 0)
473 				itimerfire(pt);
474 	}
475 
476 	/*
477 	 * If no separate statistics clock is available, run it from here.
478 	 */
479 	if (stathz == 0)
480 		statclock(frame);
481 	if ((--ci->ci_schedstate.spc_rrticks) <= 0)
482 		roundrobin(ci);
483 
484 #if defined(MULTIPROCESSOR)
485 	/*
486 	 * If we are not the primary CPU, we're not allowed to do
487 	 * any more work.
488 	 */
489 	if (CPU_IS_PRIMARY(ci) == 0)
490 		return;
491 #endif
492 
493 	/*
494 	 * Increment the time-of-day.  The increment is normally just
495 	 * ``tick''.  If the machine is one which has a clock frequency
496 	 * such that ``hz'' would not divide the second evenly into
497 	 * milliseconds, a periodic adjustment must be applied.  Finally,
498 	 * if we are still adjusting the time (see adjtime()),
499 	 * ``tickdelta'' may also be added in.
500 	 */
501 	hardclock_ticks++;
502 	delta = tick;
503 
504 #ifndef NTP
505 	if (tickfix) {
506 		tickfixcnt += tickfix;
507 		if (tickfixcnt >= tickfixinterval) {
508 			delta++;
509 			tickfixcnt -= tickfixinterval;
510 		}
511 	}
512 #endif /* !NTP */
513 	/* Imprecise 4bsd adjtime() handling */
514 	if (timedelta != 0) {
515 		delta += tickdelta;
516 		timedelta -= tickdelta;
517 	}
518 
519 #ifdef notyet
520 	microset();
521 #endif
522 
523 #ifndef NTP
524 	BUMPTIME(&time, delta);		/* XXX Now done using NTP code below */
525 #endif
526 	BUMPTIME(&mono_time, delta);
527 
528 #ifdef NTP
529 	time_update = delta;
530 
531 	/*
532 	 * Compute the phase adjustment. If the low-order bits
533 	 * (time_phase) of the update overflow, bump the high-order bits
534 	 * (time_update).
535 	 */
536 	time_phase += time_adj;
537 	if (time_phase <= -FINEUSEC) {
538 		ltemp = -time_phase >> SHIFT_SCALE;
539 		time_phase += ltemp << SHIFT_SCALE;
540 		time_update -= ltemp;
541 	} else if (time_phase >= FINEUSEC) {
542 		ltemp = time_phase >> SHIFT_SCALE;
543 		time_phase -= ltemp << SHIFT_SCALE;
544 		time_update += ltemp;
545 	}
546 
547 #ifdef HIGHBALL
548 	/*
549 	 * If the HIGHBALL board is installed, we need to adjust the
550 	 * external clock offset in order to close the hardware feedback
551 	 * loop. This will adjust the external clock phase and frequency
552 	 * in small amounts. The additional phase noise and frequency
553 	 * wander this causes should be minimal. We also need to
554 	 * discipline the kernel time variable, since the PLL is used to
555 	 * discipline the external clock. If the Highball board is not
556 	 * present, we discipline kernel time with the PLL as usual. We
557 	 * assume that the external clock phase adjustment (time_update)
558 	 * and kernel phase adjustment (clock_cpu) are less than the
559 	 * value of tick.
560 	 */
561 	clock_offset.tv_usec += time_update;
562 	if (clock_offset.tv_usec >= 1000000) {
563 		clock_offset.tv_sec++;
564 		clock_offset.tv_usec -= 1000000;
565 	}
566 	if (clock_offset.tv_usec < 0) {
567 		clock_offset.tv_sec--;
568 		clock_offset.tv_usec += 1000000;
569 	}
570 	time.tv_usec += clock_cpu;
571 	clock_cpu = 0;
572 #else
573 	time.tv_usec += time_update;
574 #endif /* HIGHBALL */
575 
576 	/*
577 	 * On rollover of the second the phase adjustment to be used for
578 	 * the next second is calculated. Also, the maximum error is
579 	 * increased by the tolerance. If the PPS frequency discipline
580 	 * code is present, the phase is increased to compensate for the
581 	 * CPU clock oscillator frequency error.
582 	 *
583  	 * On a 32-bit machine and given parameters in the timex.h
584 	 * header file, the maximum phase adjustment is +-512 ms and
585 	 * maximum frequency offset is a tad less than) +-512 ppm. On a
586 	 * 64-bit machine, you shouldn't need to ask.
587 	 */
588 	if (time.tv_usec >= 1000000) {
589 		time.tv_usec -= 1000000;
590 		time.tv_sec++;
591 		time_maxerror += time_tolerance >> SHIFT_USEC;
592 
593 		/*
594 		 * Leap second processing. If in leap-insert state at
595 		 * the end of the day, the system clock is set back one
596 		 * second; if in leap-delete state, the system clock is
597 		 * set ahead one second. The microtime() routine or
598 		 * external clock driver will insure that reported time
599 		 * is always monotonic. The ugly divides should be
600 		 * replaced.
601 		 */
602 		switch (time_state) {
603 		case TIME_OK:
604 			if (time_status & STA_INS)
605 				time_state = TIME_INS;
606 			else if (time_status & STA_DEL)
607 				time_state = TIME_DEL;
608 			break;
609 
610 		case TIME_INS:
611 			if (time.tv_sec % 86400 == 0) {
612 				time.tv_sec--;
613 				time_state = TIME_OOP;
614 			}
615 			break;
616 
617 		case TIME_DEL:
618 			if ((time.tv_sec + 1) % 86400 == 0) {
619 				time.tv_sec++;
620 				time_state = TIME_WAIT;
621 			}
622 			break;
623 
624 		case TIME_OOP:
625 			time_state = TIME_WAIT;
626 			break;
627 
628 		case TIME_WAIT:
629 			if (!(time_status & (STA_INS | STA_DEL)))
630 				time_state = TIME_OK;
631 			break;
632 		}
633 
634 		/*
635 		 * Compute the phase adjustment for the next second. In
636 		 * PLL mode, the offset is reduced by a fixed factor
637 		 * times the time constant. In FLL mode the offset is
638 		 * used directly. In either mode, the maximum phase
639 		 * adjustment for each second is clamped so as to spread
640 		 * the adjustment over not more than the number of
641 		 * seconds between updates.
642 		 */
643 		if (time_offset < 0) {
644 			ltemp = -time_offset;
645 			if (!(time_status & STA_FLL))
646 				ltemp >>= SHIFT_KG + time_constant;
647 			if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
648 				ltemp = (MAXPHASE / MINSEC) <<
649 				    SHIFT_UPDATE;
650 			time_offset += ltemp;
651 			time_adj = -ltemp << (shifthz - SHIFT_UPDATE);
652 		} else if (time_offset > 0) {
653 			ltemp = time_offset;
654 			if (!(time_status & STA_FLL))
655 				ltemp >>= SHIFT_KG + time_constant;
656 			if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
657 				ltemp = (MAXPHASE / MINSEC) <<
658 				    SHIFT_UPDATE;
659 			time_offset -= ltemp;
660 			time_adj = ltemp << (shifthz - SHIFT_UPDATE);
661 		} else
662 			time_adj = 0;
663 
664 		/*
665 		 * Compute the frequency estimate and additional phase
666 		 * adjustment due to frequency error for the next
667 		 * second. When the PPS signal is engaged, gnaw on the
668 		 * watchdog counter and update the frequency computed by
669 		 * the pll and the PPS signal.
670 		 */
671 #ifdef PPS_SYNC
672 		pps_valid++;
673 		if (pps_valid == PPS_VALID) {
674 			pps_jitter = MAXTIME;
675 			pps_stabil = MAXFREQ;
676 			time_status &= ~(STA_PPSSIGNAL | STA_PPSJITTER |
677 			    STA_PPSWANDER | STA_PPSERROR);
678 		}
679 		ltemp = time_freq + pps_freq;
680 #else
681 		ltemp = time_freq;
682 #endif /* PPS_SYNC */
683 
684 		if (ltemp < 0)
685 			time_adj -= -ltemp >> (SHIFT_USEC - shifthz);
686 		else
687 			time_adj += ltemp >> (SHIFT_USEC - shifthz);
688 		time_adj += (long)fixtick << shifthz;
689 
690 		/*
691 		 * When the CPU clock oscillator frequency is not a
692 		 * power of 2 in Hz, shifthz is only an approximate
693 		 * scale factor.
694 		 *
695 		 * To determine the adjustment, you can do the following:
696 		 *   bc -q
697 		 *   scale=24
698 		 *   obase=2
699 		 *   idealhz/realhz
700 		 * where `idealhz' is the next higher power of 2, and `realhz'
701 		 * is the actual value.  You may need to factor this result
702 		 * into a sequence of 2 multipliers to get better precision.
703 		 *
704 		 * Likewise, the error can be calculated with (e.g. for 100Hz):
705 		 *   bc -q
706 		 *   scale=24
707 		 *   ((1+2^-2+2^-5)*(1-2^-10)*realhz-idealhz)/idealhz
708 		 * (and then multiply by 1000000 to get ppm).
709 		 */
710 		switch (hz) {
711 		case 60:
712 			/* A factor of 1.000100010001 gives about 15ppm
713 			   error. */
714 			if (time_adj < 0) {
715 				time_adj -= (-time_adj >> 4);
716 				time_adj -= (-time_adj >> 8);
717 			} else {
718 				time_adj += (time_adj >> 4);
719 				time_adj += (time_adj >> 8);
720 			}
721 			break;
722 
723 		case 96:
724 			/* A factor of 1.0101010101 gives about 244ppm error. */
725 			if (time_adj < 0) {
726 				time_adj -= (-time_adj >> 2);
727 				time_adj -= (-time_adj >> 4) + (-time_adj >> 8);
728 			} else {
729 				time_adj += (time_adj >> 2);
730 				time_adj += (time_adj >> 4) + (time_adj >> 8);
731 			}
732 			break;
733 
734 		case 100:
735 			/* A factor of 1.010001111010111 gives about 1ppm
736 			   error. */
737 			if (time_adj < 0) {
738 				time_adj -= (-time_adj >> 2) + (-time_adj >> 5);
739 				time_adj += (-time_adj >> 10);
740 			} else {
741 				time_adj += (time_adj >> 2) + (time_adj >> 5);
742 				time_adj -= (time_adj >> 10);
743 			}
744 			break;
745 
746 		case 1000:
747 			/* A factor of 1.000001100010100001 gives about 50ppm
748 			   error. */
749 			if (time_adj < 0) {
750 				time_adj -= (-time_adj >> 6) + (-time_adj >> 11);
751 				time_adj -= (-time_adj >> 7);
752 			} else {
753 				time_adj += (time_adj >> 6) + (time_adj >> 11);
754 				time_adj += (time_adj >> 7);
755 			}
756 			break;
757 
758 		case 1200:
759 			/* A factor of 1.1011010011100001 gives about 64ppm
760 			   error. */
761 			if (time_adj < 0) {
762 				time_adj -= (-time_adj >> 1) + (-time_adj >> 6);
763 				time_adj -= (-time_adj >> 3) + (-time_adj >> 10);
764 			} else {
765 				time_adj += (time_adj >> 1) + (time_adj >> 6);
766 				time_adj += (time_adj >> 3) + (time_adj >> 10);
767 			}
768 			break;
769 		}
770 
771 #ifdef EXT_CLOCK
772 		/*
773 		 * If an external clock is present, it is necessary to
774 		 * discipline the kernel time variable anyway, since not
775 		 * all system components use the microtime() interface.
776 		 * Here, the time offset between the external clock and
777 		 * kernel time variable is computed every so often.
778 		 */
779 		clock_count++;
780 		if (clock_count > CLOCK_INTERVAL) {
781 			clock_count = 0;
782 			microtime(&clock_ext);
783 			delta.tv_sec = clock_ext.tv_sec - time.tv_sec;
784 			delta.tv_usec = clock_ext.tv_usec -
785 			    time.tv_usec;
786 			if (delta.tv_usec < 0)
787 				delta.tv_sec--;
788 			if (delta.tv_usec >= 500000) {
789 				delta.tv_usec -= 1000000;
790 				delta.tv_sec++;
791 			}
792 			if (delta.tv_usec < -500000) {
793 				delta.tv_usec += 1000000;
794 				delta.tv_sec--;
795 			}
796 			if (delta.tv_sec > 0 || (delta.tv_sec == 0 &&
797 			    delta.tv_usec > MAXPHASE) ||
798 			    delta.tv_sec < -1 || (delta.tv_sec == -1 &&
799 			    delta.tv_usec < -MAXPHASE)) {
800 				time = clock_ext;
801 				delta.tv_sec = 0;
802 				delta.tv_usec = 0;
803 			}
804 #ifdef HIGHBALL
805 			clock_cpu = delta.tv_usec;
806 #else /* HIGHBALL */
807 			hardupdate(delta.tv_usec);
808 #endif /* HIGHBALL */
809 		}
810 #endif /* EXT_CLOCK */
811 	}
812 
813 #endif /* NTP */
814 
815 	/*
816 	 * Update real-time timeout queue.
817 	 * Process callouts at a very low cpu priority, so we don't keep the
818 	 * relatively high clock interrupt priority any longer than necessary.
819 	 */
820 	if (callout_hardclock()) {
821 		if (CLKF_BASEPRI(frame)) {
822 			/*
823 			 * Save the overhead of a software interrupt;
824 			 * it will happen as soon as we return, so do
825 			 * it now.
826 			 */
827 			spllowersoftclock();
828 			KERNEL_LOCK(LK_CANRECURSE|LK_EXCLUSIVE);
829 			softclock(NULL);
830 			KERNEL_UNLOCK();
831 		} else {
832 #ifdef __HAVE_GENERIC_SOFT_INTERRUPTS
833 			softintr_schedule(softclock_si);
834 #else
835 			setsoftclock();
836 #endif
837 		}
838 	}
839 }
840 
841 /*
842  * Compute number of hz until specified time.  Used to compute second
843  * argument to callout_reset() from an absolute time.
844  */
845 int
846 hzto(struct timeval *tv)
847 {
848 	unsigned long ticks;
849 	long sec, usec;
850 	int s;
851 
852 	/*
853 	 * If the number of usecs in the whole seconds part of the time
854 	 * difference fits in a long, then the total number of usecs will
855 	 * fit in an unsigned long.  Compute the total and convert it to
856 	 * ticks, rounding up and adding 1 to allow for the current tick
857 	 * to expire.  Rounding also depends on unsigned long arithmetic
858 	 * to avoid overflow.
859 	 *
860 	 * Otherwise, if the number of ticks in the whole seconds part of
861 	 * the time difference fits in a long, then convert the parts to
862 	 * ticks separately and add, using similar rounding methods and
863 	 * overflow avoidance.  This method would work in the previous
864 	 * case, but it is slightly slower and assume that hz is integral.
865 	 *
866 	 * Otherwise, round the time difference down to the maximum
867 	 * representable value.
868 	 *
869 	 * If ints are 32-bit, then the maximum value for any timeout in
870 	 * 10ms ticks is 248 days.
871 	 */
872 	s = splclock();
873 	sec = tv->tv_sec - time.tv_sec;
874 	usec = tv->tv_usec - time.tv_usec;
875 	splx(s);
876 
877 	if (usec < 0) {
878 		sec--;
879 		usec += 1000000;
880 	}
881 
882 	if (sec < 0 || (sec == 0 && usec <= 0)) {
883 		/*
884 		 * Would expire now or in the past.  Return 0 ticks.
885 		 * This is different from the legacy hzto() interface,
886 		 * and callers need to check for it.
887 		 */
888 		ticks = 0;
889 	} else if (sec <= (LONG_MAX / 1000000))
890 		ticks = (((sec * 1000000) + (unsigned long)usec + (tick - 1))
891 		    / tick) + 1;
892 	else if (sec <= (LONG_MAX / hz))
893 		ticks = (sec * hz) +
894 		    (((unsigned long)usec + (tick - 1)) / tick) + 1;
895 	else
896 		ticks = LONG_MAX;
897 
898 	if (ticks > INT_MAX)
899 		ticks = INT_MAX;
900 
901 	return ((int)ticks);
902 }
903 
904 /*
905  * Start profiling on a process.
906  *
907  * Kernel profiling passes proc0 which never exits and hence
908  * keeps the profile clock running constantly.
909  */
910 void
911 startprofclock(struct proc *p)
912 {
913 
914 	if ((p->p_flag & P_PROFIL) == 0) {
915 		p->p_flag |= P_PROFIL;
916 		/*
917 		 * This is only necessary if using the clock as the
918 		 * profiling source.
919 		 */
920 		if (++profprocs == 1 && stathz != 0)
921 			psdiv = psratio;
922 	}
923 }
924 
925 /*
926  * Stop profiling on a process.
927  */
928 void
929 stopprofclock(struct proc *p)
930 {
931 
932 	if (p->p_flag & P_PROFIL) {
933 		p->p_flag &= ~P_PROFIL;
934 		/*
935 		 * This is only necessary if using the clock as the
936 		 * profiling source.
937 		 */
938 		if (--profprocs == 0 && stathz != 0)
939 			psdiv = 1;
940 	}
941 }
942 
943 #if defined(PERFCTRS)
944 /*
945  * Independent profiling "tick" in case we're using a separate
946  * clock or profiling event source.  Currently, that's just
947  * performance counters--hence the wrapper.
948  */
949 void
950 proftick(struct clockframe *frame)
951 {
952 #ifdef GPROF
953         struct gmonparam *g;
954         intptr_t i;
955 #endif
956 	struct proc *p;
957 
958 	p = curproc;
959 	if (CLKF_USERMODE(frame)) {
960 		if (p->p_flag & P_PROFIL)
961 			addupc_intr(p, CLKF_PC(frame));
962 	} else {
963 #ifdef GPROF
964 		g = &_gmonparam;
965 		if (g->state == GMON_PROF_ON) {
966 			i = CLKF_PC(frame) - g->lowpc;
967 			if (i < g->textsize) {
968 				i /= HISTFRACTION * sizeof(*g->kcount);
969 				g->kcount[i]++;
970 			}
971 		}
972 #endif
973 #ifdef PROC_PC
974                 if (p && p->p_flag & P_PROFIL)
975                         addupc_intr(p, PROC_PC(p));
976 #endif
977 	}
978 }
979 #endif
980 
981 /*
982  * Statistics clock.  Grab profile sample, and if divider reaches 0,
983  * do process and kernel statistics.
984  */
985 void
986 statclock(struct clockframe *frame)
987 {
988 #ifdef GPROF
989 	struct gmonparam *g;
990 	intptr_t i;
991 #endif
992 	struct cpu_info *ci = curcpu();
993 	struct schedstate_percpu *spc = &ci->ci_schedstate;
994 	struct lwp *l;
995 	struct proc *p;
996 
997 	/*
998 	 * Notice changes in divisor frequency, and adjust clock
999 	 * frequency accordingly.
1000 	 */
1001 	if (spc->spc_psdiv != psdiv) {
1002 		spc->spc_psdiv = psdiv;
1003 		spc->spc_pscnt = psdiv;
1004 		if (psdiv == 1) {
1005 			setstatclockrate(stathz);
1006 		} else {
1007 			setstatclockrate(profhz);
1008 		}
1009 	}
1010 	l = curlwp;
1011 	p = (l ? l->l_proc : 0);
1012 	if (CLKF_USERMODE(frame)) {
1013 		if (p->p_flag & P_PROFIL && profsrc == PROFSRC_CLOCK)
1014 			addupc_intr(p, CLKF_PC(frame));
1015 		if (--spc->spc_pscnt > 0)
1016 			return;
1017 		/*
1018 		 * Came from user mode; CPU was in user state.
1019 		 * If this process is being profiled record the tick.
1020 		 */
1021 		p->p_uticks++;
1022 		if (p->p_nice > NZERO)
1023 			spc->spc_cp_time[CP_NICE]++;
1024 		else
1025 			spc->spc_cp_time[CP_USER]++;
1026 	} else {
1027 #ifdef GPROF
1028 		/*
1029 		 * Kernel statistics are just like addupc_intr, only easier.
1030 		 */
1031 		g = &_gmonparam;
1032 		if (profsrc == PROFSRC_CLOCK && g->state == GMON_PROF_ON) {
1033 			i = CLKF_PC(frame) - g->lowpc;
1034 			if (i < g->textsize) {
1035 				i /= HISTFRACTION * sizeof(*g->kcount);
1036 				g->kcount[i]++;
1037 			}
1038 		}
1039 #endif
1040 #ifdef LWP_PC
1041 		if (p && profsrc == PROFSRC_CLOCK && p->p_flag & P_PROFIL)
1042 			addupc_intr(p, LWP_PC(l));
1043 #endif
1044 		if (--spc->spc_pscnt > 0)
1045 			return;
1046 		/*
1047 		 * Came from kernel mode, so we were:
1048 		 * - handling an interrupt,
1049 		 * - doing syscall or trap work on behalf of the current
1050 		 *   user process, or
1051 		 * - spinning in the idle loop.
1052 		 * Whichever it is, charge the time as appropriate.
1053 		 * Note that we charge interrupts to the current process,
1054 		 * regardless of whether they are ``for'' that process,
1055 		 * so that we know how much of its real time was spent
1056 		 * in ``non-process'' (i.e., interrupt) work.
1057 		 */
1058 		if (CLKF_INTR(frame)) {
1059 			if (p != NULL)
1060 				p->p_iticks++;
1061 			spc->spc_cp_time[CP_INTR]++;
1062 		} else if (p != NULL) {
1063 			p->p_sticks++;
1064 			spc->spc_cp_time[CP_SYS]++;
1065 		} else
1066 			spc->spc_cp_time[CP_IDLE]++;
1067 	}
1068 	spc->spc_pscnt = psdiv;
1069 
1070 	if (l != NULL) {
1071 		++p->p_cpticks;
1072 		/*
1073 		 * If no separate schedclock is provided, call it here
1074 		 * at ~~12-25 Hz, ~~16 Hz is best
1075 		 */
1076 		if (schedhz == 0)
1077 			if ((++ci->ci_schedstate.spc_schedticks & 3) == 0)
1078 				schedclock(l);
1079 	}
1080 }
1081 
1082 
1083 #ifdef NTP	/* NTP phase-locked loop in kernel */
1084 
1085 /*
1086  * hardupdate() - local clock update
1087  *
1088  * This routine is called by ntp_adjtime() to update the local clock
1089  * phase and frequency. The implementation is of an adaptive-parameter,
1090  * hybrid phase/frequency-lock loop (PLL/FLL). The routine computes new
1091  * time and frequency offset estimates for each call. If the kernel PPS
1092  * discipline code is configured (PPS_SYNC), the PPS signal itself
1093  * determines the new time offset, instead of the calling argument.
1094  * Presumably, calls to ntp_adjtime() occur only when the caller
1095  * believes the local clock is valid within some bound (+-128 ms with
1096  * NTP). If the caller's time is far different than the PPS time, an
1097  * argument will ensue, and it's not clear who will lose.
1098  *
1099  * For uncompensated quartz crystal oscillatores and nominal update
1100  * intervals less than 1024 s, operation should be in phase-lock mode
1101  * (STA_FLL = 0), where the loop is disciplined to phase. For update
1102  * intervals greater than thiss, operation should be in frequency-lock
1103  * mode (STA_FLL = 1), where the loop is disciplined to frequency.
1104  *
1105  * Note: splclock() is in effect.
1106  */
1107 void
1108 hardupdate(long offset)
1109 {
1110 	long ltemp, mtemp;
1111 
1112 	if (!(time_status & STA_PLL) && !(time_status & STA_PPSTIME))
1113 		return;
1114 	ltemp = offset;
1115 #ifdef PPS_SYNC
1116 	if (time_status & STA_PPSTIME && time_status & STA_PPSSIGNAL)
1117 		ltemp = pps_offset;
1118 #endif /* PPS_SYNC */
1119 
1120 	/*
1121 	 * Scale the phase adjustment and clamp to the operating range.
1122 	 */
1123 	if (ltemp > MAXPHASE)
1124 		time_offset = MAXPHASE << SHIFT_UPDATE;
1125 	else if (ltemp < -MAXPHASE)
1126 		time_offset = -(MAXPHASE << SHIFT_UPDATE);
1127 	else
1128 		time_offset = ltemp << SHIFT_UPDATE;
1129 
1130 	/*
1131 	 * Select whether the frequency is to be controlled and in which
1132 	 * mode (PLL or FLL). Clamp to the operating range. Ugly
1133 	 * multiply/divide should be replaced someday.
1134 	 */
1135 	if (time_status & STA_FREQHOLD || time_reftime == 0)
1136 		time_reftime = time.tv_sec;
1137 	mtemp = time.tv_sec - time_reftime;
1138 	time_reftime = time.tv_sec;
1139 	if (time_status & STA_FLL) {
1140 		if (mtemp >= MINSEC) {
1141 			ltemp = ((time_offset / mtemp) << (SHIFT_USEC -
1142 			    SHIFT_UPDATE));
1143 			if (ltemp < 0)
1144 				time_freq -= -ltemp >> SHIFT_KH;
1145 			else
1146 				time_freq += ltemp >> SHIFT_KH;
1147 		}
1148 	} else {
1149 		if (mtemp < MAXSEC) {
1150 			ltemp *= mtemp;
1151 			if (ltemp < 0)
1152 				time_freq -= -ltemp >> (time_constant +
1153 				    time_constant + SHIFT_KF -
1154 				    SHIFT_USEC);
1155 			else
1156 				time_freq += ltemp >> (time_constant +
1157 				    time_constant + SHIFT_KF -
1158 				    SHIFT_USEC);
1159 		}
1160 	}
1161 	if (time_freq > time_tolerance)
1162 		time_freq = time_tolerance;
1163 	else if (time_freq < -time_tolerance)
1164 		time_freq = -time_tolerance;
1165 }
1166 
1167 #ifdef PPS_SYNC
1168 /*
1169  * hardpps() - discipline CPU clock oscillator to external PPS signal
1170  *
1171  * This routine is called at each PPS interrupt in order to discipline
1172  * the CPU clock oscillator to the PPS signal. It measures the PPS phase
1173  * and leaves it in a handy spot for the hardclock() routine. It
1174  * integrates successive PPS phase differences and calculates the
1175  * frequency offset. This is used in hardclock() to discipline the CPU
1176  * clock oscillator so that intrinsic frequency error is cancelled out.
1177  * The code requires the caller to capture the time and hardware counter
1178  * value at the on-time PPS signal transition.
1179  *
1180  * Note that, on some Unix systems, this routine runs at an interrupt
1181  * priority level higher than the timer interrupt routine hardclock().
1182  * Therefore, the variables used are distinct from the hardclock()
1183  * variables, except for certain exceptions: The PPS frequency pps_freq
1184  * and phase pps_offset variables are determined by this routine and
1185  * updated atomically. The time_tolerance variable can be considered a
1186  * constant, since it is infrequently changed, and then only when the
1187  * PPS signal is disabled. The watchdog counter pps_valid is updated
1188  * once per second by hardclock() and is atomically cleared in this
1189  * routine.
1190  */
1191 void
1192 hardpps(struct timeval *tvp,		/* time at PPS */
1193 	long usec			/* hardware counter at PPS */)
1194 {
1195 	long u_usec, v_usec, bigtick;
1196 	long cal_sec, cal_usec;
1197 
1198 	/*
1199 	 * An occasional glitch can be produced when the PPS interrupt
1200 	 * occurs in the hardclock() routine before the time variable is
1201 	 * updated. Here the offset is discarded when the difference
1202 	 * between it and the last one is greater than tick/2, but not
1203 	 * if the interval since the first discard exceeds 30 s.
1204 	 */
1205 	time_status |= STA_PPSSIGNAL;
1206 	time_status &= ~(STA_PPSJITTER | STA_PPSWANDER | STA_PPSERROR);
1207 	pps_valid = 0;
1208 	u_usec = -tvp->tv_usec;
1209 	if (u_usec < -500000)
1210 		u_usec += 1000000;
1211 	v_usec = pps_offset - u_usec;
1212 	if (v_usec < 0)
1213 		v_usec = -v_usec;
1214 	if (v_usec > (tick >> 1)) {
1215 		if (pps_glitch > MAXGLITCH) {
1216 			pps_glitch = 0;
1217 			pps_tf[2] = u_usec;
1218 			pps_tf[1] = u_usec;
1219 		} else {
1220 			pps_glitch++;
1221 			u_usec = pps_offset;
1222 		}
1223 	} else
1224 		pps_glitch = 0;
1225 
1226 	/*
1227 	 * A three-stage median filter is used to help deglitch the pps
1228 	 * time. The median sample becomes the time offset estimate; the
1229 	 * difference between the other two samples becomes the time
1230 	 * dispersion (jitter) estimate.
1231 	 */
1232 	pps_tf[2] = pps_tf[1];
1233 	pps_tf[1] = pps_tf[0];
1234 	pps_tf[0] = u_usec;
1235 	if (pps_tf[0] > pps_tf[1]) {
1236 		if (pps_tf[1] > pps_tf[2]) {
1237 			pps_offset = pps_tf[1];		/* 0 1 2 */
1238 			v_usec = pps_tf[0] - pps_tf[2];
1239 		} else if (pps_tf[2] > pps_tf[0]) {
1240 			pps_offset = pps_tf[0];		/* 2 0 1 */
1241 			v_usec = pps_tf[2] - pps_tf[1];
1242 		} else {
1243 			pps_offset = pps_tf[2];		/* 0 2 1 */
1244 			v_usec = pps_tf[0] - pps_tf[1];
1245 		}
1246 	} else {
1247 		if (pps_tf[1] < pps_tf[2]) {
1248 			pps_offset = pps_tf[1];		/* 2 1 0 */
1249 			v_usec = pps_tf[2] - pps_tf[0];
1250 		} else  if (pps_tf[2] < pps_tf[0]) {
1251 			pps_offset = pps_tf[0];		/* 1 0 2 */
1252 			v_usec = pps_tf[1] - pps_tf[2];
1253 		} else {
1254 			pps_offset = pps_tf[2];		/* 1 2 0 */
1255 			v_usec = pps_tf[1] - pps_tf[0];
1256 		}
1257 	}
1258 	if (v_usec > MAXTIME)
1259 		pps_jitcnt++;
1260 	v_usec = (v_usec << PPS_AVG) - pps_jitter;
1261 	if (v_usec < 0)
1262 		pps_jitter -= -v_usec >> PPS_AVG;
1263 	else
1264 		pps_jitter += v_usec >> PPS_AVG;
1265 	if (pps_jitter > (MAXTIME >> 1))
1266 		time_status |= STA_PPSJITTER;
1267 
1268 	/*
1269 	 * During the calibration interval adjust the starting time when
1270 	 * the tick overflows. At the end of the interval compute the
1271 	 * duration of the interval and the difference of the hardware
1272 	 * counters at the beginning and end of the interval. This code
1273 	 * is deliciously complicated by the fact valid differences may
1274 	 * exceed the value of tick when using long calibration
1275 	 * intervals and small ticks. Note that the counter can be
1276 	 * greater than tick if caught at just the wrong instant, but
1277 	 * the values returned and used here are correct.
1278 	 */
1279 	bigtick = (long)tick << SHIFT_USEC;
1280 	pps_usec -= pps_freq;
1281 	if (pps_usec >= bigtick)
1282 		pps_usec -= bigtick;
1283 	if (pps_usec < 0)
1284 		pps_usec += bigtick;
1285 	pps_time.tv_sec++;
1286 	pps_count++;
1287 	if (pps_count < (1 << pps_shift))
1288 		return;
1289 	pps_count = 0;
1290 	pps_calcnt++;
1291 	u_usec = usec << SHIFT_USEC;
1292 	v_usec = pps_usec - u_usec;
1293 	if (v_usec >= bigtick >> 1)
1294 		v_usec -= bigtick;
1295 	if (v_usec < -(bigtick >> 1))
1296 		v_usec += bigtick;
1297 	if (v_usec < 0)
1298 		v_usec = -(-v_usec >> pps_shift);
1299 	else
1300 		v_usec = v_usec >> pps_shift;
1301 	pps_usec = u_usec;
1302 	cal_sec = tvp->tv_sec;
1303 	cal_usec = tvp->tv_usec;
1304 	cal_sec -= pps_time.tv_sec;
1305 	cal_usec -= pps_time.tv_usec;
1306 	if (cal_usec < 0) {
1307 		cal_usec += 1000000;
1308 		cal_sec--;
1309 	}
1310 	pps_time = *tvp;
1311 
1312 	/*
1313 	 * Check for lost interrupts, noise, excessive jitter and
1314 	 * excessive frequency error. The number of timer ticks during
1315 	 * the interval may vary +-1 tick. Add to this a margin of one
1316 	 * tick for the PPS signal jitter and maximum frequency
1317 	 * deviation. If the limits are exceeded, the calibration
1318 	 * interval is reset to the minimum and we start over.
1319 	 */
1320 	u_usec = (long)tick << 1;
1321 	if (!((cal_sec == -1 && cal_usec > (1000000 - u_usec))
1322 	    || (cal_sec == 0 && cal_usec < u_usec))
1323 	    || v_usec > time_tolerance || v_usec < -time_tolerance) {
1324 		pps_errcnt++;
1325 		pps_shift = PPS_SHIFT;
1326 		pps_intcnt = 0;
1327 		time_status |= STA_PPSERROR;
1328 		return;
1329 	}
1330 
1331 	/*
1332 	 * A three-stage median filter is used to help deglitch the pps
1333 	 * frequency. The median sample becomes the frequency offset
1334 	 * estimate; the difference between the other two samples
1335 	 * becomes the frequency dispersion (stability) estimate.
1336 	 */
1337 	pps_ff[2] = pps_ff[1];
1338 	pps_ff[1] = pps_ff[0];
1339 	pps_ff[0] = v_usec;
1340 	if (pps_ff[0] > pps_ff[1]) {
1341 		if (pps_ff[1] > pps_ff[2]) {
1342 			u_usec = pps_ff[1];		/* 0 1 2 */
1343 			v_usec = pps_ff[0] - pps_ff[2];
1344 		} else if (pps_ff[2] > pps_ff[0]) {
1345 			u_usec = pps_ff[0];		/* 2 0 1 */
1346 			v_usec = pps_ff[2] - pps_ff[1];
1347 		} else {
1348 			u_usec = pps_ff[2];		/* 0 2 1 */
1349 			v_usec = pps_ff[0] - pps_ff[1];
1350 		}
1351 	} else {
1352 		if (pps_ff[1] < pps_ff[2]) {
1353 			u_usec = pps_ff[1];		/* 2 1 0 */
1354 			v_usec = pps_ff[2] - pps_ff[0];
1355 		} else  if (pps_ff[2] < pps_ff[0]) {
1356 			u_usec = pps_ff[0];		/* 1 0 2 */
1357 			v_usec = pps_ff[1] - pps_ff[2];
1358 		} else {
1359 			u_usec = pps_ff[2];		/* 1 2 0 */
1360 			v_usec = pps_ff[1] - pps_ff[0];
1361 		}
1362 	}
1363 
1364 	/*
1365 	 * Here the frequency dispersion (stability) is updated. If it
1366 	 * is less than one-fourth the maximum (MAXFREQ), the frequency
1367 	 * offset is updated as well, but clamped to the tolerance. It
1368 	 * will be processed later by the hardclock() routine.
1369 	 */
1370 	v_usec = (v_usec >> 1) - pps_stabil;
1371 	if (v_usec < 0)
1372 		pps_stabil -= -v_usec >> PPS_AVG;
1373 	else
1374 		pps_stabil += v_usec >> PPS_AVG;
1375 	if (pps_stabil > MAXFREQ >> 2) {
1376 		pps_stbcnt++;
1377 		time_status |= STA_PPSWANDER;
1378 		return;
1379 	}
1380 	if (time_status & STA_PPSFREQ) {
1381 		if (u_usec < 0) {
1382 			pps_freq -= -u_usec >> PPS_AVG;
1383 			if (pps_freq < -time_tolerance)
1384 				pps_freq = -time_tolerance;
1385 			u_usec = -u_usec;
1386 		} else {
1387 			pps_freq += u_usec >> PPS_AVG;
1388 			if (pps_freq > time_tolerance)
1389 				pps_freq = time_tolerance;
1390 		}
1391 	}
1392 
1393 	/*
1394 	 * Here the calibration interval is adjusted. If the maximum
1395 	 * time difference is greater than tick / 4, reduce the interval
1396 	 * by half. If this is not the case for four consecutive
1397 	 * intervals, double the interval.
1398 	 */
1399 	if (u_usec << pps_shift > bigtick >> 2) {
1400 		pps_intcnt = 0;
1401 		if (pps_shift > PPS_SHIFT)
1402 			pps_shift--;
1403 	} else if (pps_intcnt >= 4) {
1404 		pps_intcnt = 0;
1405 		if (pps_shift < PPS_SHIFTMAX)
1406 			pps_shift++;
1407 	} else
1408 		pps_intcnt++;
1409 }
1410 #endif /* PPS_SYNC */
1411 #endif /* NTP  */
1412 
1413 /*
1414  * Return information about system clocks.
1415  */
1416 int
1417 sysctl_clockrate(void *where, size_t *sizep)
1418 {
1419 	struct clockinfo clkinfo;
1420 
1421 	/*
1422 	 * Construct clockinfo structure.
1423 	 */
1424 	clkinfo.tick = tick;
1425 	clkinfo.tickadj = tickadj;
1426 	clkinfo.hz = hz;
1427 	clkinfo.profhz = profhz;
1428 	clkinfo.stathz = stathz ? stathz : hz;
1429 	return (sysctl_rdstruct(where, sizep, NULL, &clkinfo, sizeof(clkinfo)));
1430 }
1431