kern_timeout.c revision 32391 
1/*-
2 * Copyright (c) 1982, 1986, 1991, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 * (c) UNIX System Laboratories, Inc.
5 * All or some portions of this file are derived from material licensed
6 * to the University of California by American Telephone and Telegraph
7 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
8 * the permission of UNIX System Laboratories, Inc.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 *    must display the following acknowledgement:
20 *	This product includes software developed by the University of
21 *	California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 *    may be used to endorse or promote products derived from this software
24 *    without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 *
38 *	@(#)kern_clock.c	8.5 (Berkeley) 1/21/94
39 * $Id: kern_timeout.c,v 1.49 1998/01/10 13:16:26 phk Exp $
40 */
41
42/* Portions of this software are covered by the following: */
43/******************************************************************************
44 *                                                                            *
45 * Copyright (c) David L. Mills 1993, 1994                                    *
46 *                                                                            *
47 * Permission to use, copy, modify, and distribute this software and its      *
48 * documentation for any purpose and without fee is hereby granted, provided  *
49 * that the above copyright notice appears in all copies and that both the    *
50 * copyright notice and this permission notice appear in supporting           *
51 * documentation, and that the name University of Delaware not be used in     *
52 * advertising or publicity pertaining to distribution of the software        *
53 * without specific, written prior permission.  The University of Delaware    *
54 * makes no representations about the suitability this software for any       *
55 * purpose.  It is provided "as is" without express or implied warranty.      *
56 *                                                                            *
57 *****************************************************************************/
58
59#include <sys/param.h>
60#include <sys/systm.h>
61#include <sys/dkstat.h>
62#include <sys/callout.h>
63#include <sys/kernel.h>
64#include <sys/proc.h>
65#include <sys/resourcevar.h>
66#include <sys/signalvar.h>
67#include <sys/timex.h>
68#include <vm/vm.h>
69#include <sys/lock.h>
70#include <vm/pmap.h>
71#include <vm/vm_map.h>
72#include <sys/sysctl.h>
73
74#include <machine/cpu.h>
75#define CLOCK_HAIR		/* XXX */
76#include <machine/clock.h>
77#include <machine/limits.h>
78
79/* Exported to machdep.c. */
80struct callout *callout;
81struct callout_list callfree;
82int callwheelsize, callwheelbits, callwheelmask;
83struct callout_tailq *callwheel;
84
85static int softticks;			/* Like ticks, but for softclock(). */
86static struct callout *nextsoftcheck;	/* Next callout to be checked. */
87
88/*
89 * The callout mechanism is based on the work of Adam M. Costello and
90 * George Varghese, published in a technical report entitled "Redesigning
91 * the BSD Callout and Timer Facilities" and modified slightly for inclusion
92 * in FreeBSD by Justin T. Gibbs.  The original work on the data structures
93 * used in this implementation was published by G.Varghese and A. Lauck in
94 * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for
95 * the Efficient Implementation of a Timer Facility" in the Proceedings of
96 * the 11th ACM Annual Symposium on Operating Systems Principles,
97 * Austin, Texas Nov 1987.
98 */
99
100/*
101 * Software (low priority) clock interrupt.
102 * Run periodic events from timeout queue.
103 */
104
105#ifndef MAX_SOFTCLOCK_STEPS
106#define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */
107#endif /* MAX_SOFTCLOCK_STEPS */
108
109/*ARGSUSED*/
110void
111softclock()
112{
113	register struct callout *c;
114	register struct callout_tailq *bucket;
115	register int s;
116	register int curticks;
117	register int steps;	/*
118				 * Number of steps taken since
119				 * we last allowed interrupts.
120				 */
121
122	if (TAILQ_FIRST(&callwheel[ticks & callwheelmask]) == NULL) {
123		softticks++;
124		return;
125	}
126
127	(void)splsoftclock();
128
129	steps = 0;
130	s = splhigh();
131	while (softticks != ticks) {
132		softticks++;
133		/*
134		 * softticks may be modified by hard clock, so cache
135		 * it while we work on a given bucket.
136		 */
137		curticks = softticks;
138		bucket = &callwheel[curticks & callwheelmask];
139		c = TAILQ_FIRST(bucket);
140		while (c) {
141			if (c->c_time != curticks) {
142				c = TAILQ_NEXT(c, c_links.tqe);
143				++steps;
144				if (steps >= MAX_SOFTCLOCK_STEPS) {
145					nextsoftcheck = c;
146					/* Give interrupts a chance. */
147					splx(s);
148					s = splhigh();
149					c = nextsoftcheck;
150					steps = 0;
151				}
152			} else {
153				void (*c_func)(void *);
154				void *c_arg;
155
156				nextsoftcheck = TAILQ_NEXT(c, c_links.tqe);
157				TAILQ_REMOVE(bucket, c, c_links.tqe);
158				c_func = c->c_func;
159				c_arg = c->c_arg;
160				c->c_func = NULL;
161				SLIST_INSERT_HEAD(&callfree, c, c_links.sle);
162				splx(s);
163				c_func(c_arg);
164				s = splhigh();
165				steps = 0;
166				c = nextsoftcheck;
167			}
168		}
169	}
170	nextsoftcheck = NULL;
171	splx(s);
172}
173
174/*
175 * timeout --
176 *	Execute a function after a specified length of time.
177 *
178 * untimeout --
179 *	Cancel previous timeout function call.
180 *
181 * callout_handle_init --
182 *	Initialize a handle so that using it with untimeout is benign.
183 *
184 *	See AT&T BCI Driver Reference Manual for specification.  This
185 *	implementation differs from that one in that although an
186 *	identification value is returned from timeout, the original
187 *	arguments to timeout as well as the identifier are used to
188 *	identify entries for untimeout.
189 */
190struct callout_handle
191timeout(ftn, arg, to_ticks)
192	timeout_t ftn;
193	void *arg;
194	register int to_ticks;
195{
196	int s;
197	struct callout *new;
198	struct callout_handle handle;
199
200	if (to_ticks <= 0)
201		to_ticks = 1;
202
203	/* Lock out the clock. */
204	s = splhigh();
205
206	/* Fill in the next free callout structure. */
207	new = SLIST_FIRST(&callfree);
208	if (new == NULL)
209		/* XXX Attempt to malloc first */
210		panic("timeout table full");
211
212	SLIST_REMOVE_HEAD(&callfree, c_links.sle);
213	new->c_arg = arg;
214	new->c_func = ftn;
215	new->c_time = ticks + to_ticks;
216	TAILQ_INSERT_TAIL(&callwheel[new->c_time & callwheelmask],
217			  new, c_links.tqe);
218
219	splx(s);
220	handle.callout = new;
221	return (handle);
222}
223
224void
225untimeout(ftn, arg, handle)
226	timeout_t ftn;
227	void *arg;
228	struct callout_handle handle;
229{
230	register int s;
231
232	/*
233	 * Check for a handle that was initialized
234	 * by callout_handle_init, but never used
235	 * for a real timeout.
236	 */
237	if (handle.callout == NULL)
238		return;
239
240	s = splhigh();
241	if ((handle.callout->c_func == ftn)
242	 && (handle.callout->c_arg == arg)) {
243		if (nextsoftcheck == handle.callout) {
244			nextsoftcheck = TAILQ_NEXT(handle.callout, c_links.tqe);
245		}
246		TAILQ_REMOVE(&callwheel[handle.callout->c_time & callwheelmask],
247			     handle.callout, c_links.tqe);
248		handle.callout->c_func = NULL;
249		SLIST_INSERT_HEAD(&callfree, handle.callout, c_links.sle);
250	}
251	splx(s);
252}
253
254void
255callout_handle_init(struct callout_handle *handle)
256{
257	handle->callout = NULL;
258}
259
260#ifdef APM_FIXUP_CALLTODO
261/*
262 * Adjust the kernel calltodo timeout list.  This routine is used after
263 * an APM resume to recalculate the calltodo timer list values with the
264 * number of hz's we have been sleeping.  The next hardclock() will detect
265 * that there are fired timers and run softclock() to execute them.
266 *
267 * Please note, I have not done an exhaustive analysis of what code this
268 * might break.  I am motivated to have my select()'s and alarm()'s that
269 * have expired during suspend firing upon resume so that the applications
270 * which set the timer can do the maintanence the timer was for as close
271 * as possible to the originally intended time.  Testing this code for a
272 * week showed that resuming from a suspend resulted in 22 to 25 timers
273 * firing, which seemed independant on whether the suspend was 2 hours or
274 * 2 days.  Your milage may vary.   - Ken Key <key@cs.utk.edu>
275 */
276void
277adjust_timeout_calltodo(time_change)
278    struct timeval *time_change;
279{
280	register struct callout *p;
281	unsigned long delta_ticks;
282	int s;
283
284	/*
285	 * How many ticks were we asleep?
286	 * (stolen from hzto()).
287	 */
288
289	/* Don't do anything */
290	if (time_change->tv_sec < 0)
291		return;
292	else if (time_change->tv_sec <= LONG_MAX / 1000000)
293		delta_ticks = (time_change->tv_sec * 1000000 +
294			       time_change->tv_usec + (tick - 1)) / tick + 1;
295	else if (time_change->tv_sec <= LONG_MAX / hz)
296		delta_ticks = time_change->tv_sec * hz +
297			      (time_change->tv_usec + (tick - 1)) / tick + 1;
298	else
299		delta_ticks = LONG_MAX;
300
301	if (delta_ticks > INT_MAX)
302		delta_ticks = INT_MAX;
303
304	/*
305	 * Now rip through the timer calltodo list looking for timers
306	 * to expire.
307	 */
308
309	/* don't collide with softclock() */
310	s = splhigh();
311	for (p = calltodo.c_next; p != NULL; p = p->c_next) {
312		p->c_time -= delta_ticks;
313
314		/* Break if the timer had more time on it than delta_ticks */
315		if (p->c_time > 0)
316			break;
317
318		/* take back the ticks the timer didn't use (p->c_time <= 0) */
319		delta_ticks = -p->c_time;
320	}
321	splx(s);
322
323	return;
324}
325#endif /* APM_FIXUP_CALLTODO */
326