kern_timeout.c revision 173760
11541Srgrimes/*-
21541Srgrimes * Copyright (c) 1982, 1986, 1991, 1993
31541Srgrimes *	The Regents of the University of California.  All rights reserved.
41541Srgrimes * (c) UNIX System Laboratories, Inc.
51541Srgrimes * All or some portions of this file are derived from material licensed
61541Srgrimes * to the University of California by American Telephone and Telegraph
71541Srgrimes * Co. or Unix System Laboratories, Inc. and are reproduced herein with
81541Srgrimes * the permission of UNIX System Laboratories, Inc.
91541Srgrimes *
101541Srgrimes * Redistribution and use in source and binary forms, with or without
111541Srgrimes * modification, are permitted provided that the following conditions
121541Srgrimes * are met:
131541Srgrimes * 1. Redistributions of source code must retain the above copyright
141541Srgrimes *    notice, this list of conditions and the following disclaimer.
151541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright
161541Srgrimes *    notice, this list of conditions and the following disclaimer in the
171541Srgrimes *    documentation and/or other materials provided with the distribution.
181541Srgrimes * 4. Neither the name of the University nor the names of its contributors
191541Srgrimes *    may be used to endorse or promote products derived from this software
201541Srgrimes *    without specific prior written permission.
211541Srgrimes *
221541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
231541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
241541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
251541Srgrimes * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
261541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
271541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
281541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
291541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
301541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
311541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
321541Srgrimes * SUCH DAMAGE.
331541Srgrimes *
3444510Swollman *	From: @(#)kern_clock.c	8.5 (Berkeley) 1/21/94
351541Srgrimes */
361541Srgrimes
37116182Sobrien#include <sys/cdefs.h>
38116182Sobrien__FBSDID("$FreeBSD: head/sys/kern/kern_timeout.c 173760 2007-11-20 00:37:45Z attilio $");
39116182Sobrien
401541Srgrimes#include <sys/param.h>
411541Srgrimes#include <sys/systm.h>
4233392Sphk#include <sys/callout.h>
43127969Scperciva#include <sys/condvar.h>
441541Srgrimes#include <sys/kernel.h>
45133229Srwatson#include <sys/ktr.h>
4674914Sjhb#include <sys/lock.h>
4768840Sjhb#include <sys/mutex.h>
48150188Sjhb#include <sys/proc.h>
49171053Sattilio#include <sys/sleepqueue.h>
50115810Sphk#include <sys/sysctl.h>
511541Srgrimes
52115810Sphkstatic int avg_depth;
53115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_depth, CTLFLAG_RD, &avg_depth, 0,
54115810Sphk    "Average number of items examined per softclock call. Units = 1/1000");
55115810Sphkstatic int avg_gcalls;
56115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_gcalls, CTLFLAG_RD, &avg_gcalls, 0,
57115810Sphk    "Average number of Giant callouts made per softclock call. Units = 1/1000");
58173760Sattiliostatic int avg_lockcalls;
59173760SattilioSYSCTL_INT(_debug, OID_AUTO, to_avg_lockcalls, CTLFLAG_RD, &avg_lockcalls, 0,
60173760Sattilio    "Average number of lock callouts made per softclock call. Units = 1/1000");
61115810Sphkstatic int avg_mpcalls;
62115810SphkSYSCTL_INT(_debug, OID_AUTO, to_avg_mpcalls, CTLFLAG_RD, &avg_mpcalls, 0,
63115810Sphk    "Average number of MP callouts made per softclock call. Units = 1/1000");
6433392Sphk/*
6533392Sphk * TODO:
6633392Sphk *	allocate more timeout table slots when table overflows.
6733392Sphk */
6833392Sphk
6933392Sphk/* Exported to machdep.c and/or kern_clock.c.  */
7029680Sgibbsstruct callout *callout;
7129680Sgibbsstruct callout_list callfree;
7229680Sgibbsint callwheelsize, callwheelbits, callwheelmask;
7329680Sgibbsstruct callout_tailq *callwheel;
7433392Sphkint softticks;			/* Like ticks, but for softclock(). */
75116606Sphkstruct mtx callout_lock;
762112Swollman
7729680Sgibbsstatic struct callout *nextsoftcheck;	/* Next callout to be checked. */
78128024Scperciva
79139831Scperciva/**
80127969Scperciva * Locked by callout_lock:
81127969Scperciva *   curr_callout    - If a callout is in progress, it is curr_callout.
82155957Sjhb *                     If curr_callout is non-NULL, threads waiting in
83155957Sjhb *                     callout_drain() will be woken up as soon as the
84127969Scperciva *                     relevant callout completes.
85173760Sattilio *   curr_cancelled  - Changing to 1 with both callout_lock and c_lock held
86141428Siedowse *                     guarantees that the current callout will not run.
87141428Siedowse *                     The softclock() function sets this to 0 before it
88173760Sattilio *                     drops callout_lock to acquire c_lock, and it calls
89155957Sjhb *                     the handler only if curr_cancelled is still 0 after
90173760Sattilio *                     c_lock is successfully acquired.
91155957Sjhb *   callout_wait    - If a thread is waiting in callout_drain(), then
92155957Sjhb *                     callout_wait is nonzero.  Set only when
93128024Scperciva *                     curr_callout is non-NULL.
94127969Scperciva */
95127969Scpercivastatic struct callout *curr_callout;
96141428Siedowsestatic int curr_cancelled;
97155957Sjhbstatic int callout_wait;
98128024Scperciva
991541Srgrimes/*
10082127Sdillon * kern_timeout_callwheel_alloc() - kernel low level callwheel initialization
10182127Sdillon *
10282127Sdillon *	This code is called very early in the kernel initialization sequence,
10382127Sdillon *	and may be called more then once.
10482127Sdillon */
10582127Sdilloncaddr_t
10682127Sdillonkern_timeout_callwheel_alloc(caddr_t v)
10782127Sdillon{
10882127Sdillon	/*
10982127Sdillon	 * Calculate callout wheel size
11082127Sdillon	 */
11182127Sdillon	for (callwheelsize = 1, callwheelbits = 0;
11282127Sdillon	     callwheelsize < ncallout;
11382127Sdillon	     callwheelsize <<= 1, ++callwheelbits)
11482127Sdillon		;
11582127Sdillon	callwheelmask = callwheelsize - 1;
11682127Sdillon
11782127Sdillon	callout = (struct callout *)v;
11882127Sdillon	v = (caddr_t)(callout + ncallout);
11982127Sdillon	callwheel = (struct callout_tailq *)v;
12082127Sdillon	v = (caddr_t)(callwheel + callwheelsize);
12182127Sdillon	return(v);
12282127Sdillon}
12382127Sdillon
12482127Sdillon/*
12582127Sdillon * kern_timeout_callwheel_init() - initialize previously reserved callwheel
12682127Sdillon *				   space.
12782127Sdillon *
12882127Sdillon *	This code is called just once, after the space reserved for the
12982127Sdillon *	callout wheel has been finalized.
13082127Sdillon */
13182127Sdillonvoid
13282127Sdillonkern_timeout_callwheel_init(void)
13382127Sdillon{
13482127Sdillon	int i;
13582127Sdillon
13682127Sdillon	SLIST_INIT(&callfree);
13782127Sdillon	for (i = 0; i < ncallout; i++) {
13882127Sdillon		callout_init(&callout[i], 0);
13982127Sdillon		callout[i].c_flags = CALLOUT_LOCAL_ALLOC;
14082127Sdillon		SLIST_INSERT_HEAD(&callfree, &callout[i], c_links.sle);
14182127Sdillon	}
14282127Sdillon	for (i = 0; i < callwheelsize; i++) {
14382127Sdillon		TAILQ_INIT(&callwheel[i]);
14482127Sdillon	}
14593818Sjhb	mtx_init(&callout_lock, "callout", NULL, MTX_SPIN | MTX_RECURSE);
14682127Sdillon}
14782127Sdillon
14882127Sdillon/*
14929680Sgibbs * The callout mechanism is based on the work of Adam M. Costello and
15029680Sgibbs * George Varghese, published in a technical report entitled "Redesigning
15129680Sgibbs * the BSD Callout and Timer Facilities" and modified slightly for inclusion
15229680Sgibbs * in FreeBSD by Justin T. Gibbs.  The original work on the data structures
153128630Shmp * used in this implementation was published by G. Varghese and T. Lauck in
15429680Sgibbs * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for
15529680Sgibbs * the Efficient Implementation of a Timer Facility" in the Proceedings of
15629680Sgibbs * the 11th ACM Annual Symposium on Operating Systems Principles,
15729680Sgibbs * Austin, Texas Nov 1987.
15829680Sgibbs */
15932388Sphk
16029680Sgibbs/*
1611541Srgrimes * Software (low priority) clock interrupt.
1621541Srgrimes * Run periodic events from timeout queue.
1631541Srgrimes */
1641541Srgrimesvoid
16567551Sjhbsoftclock(void *dummy)
1661541Srgrimes{
167102936Sphk	struct callout *c;
168102936Sphk	struct callout_tailq *bucket;
169102936Sphk	int curticks;
170102936Sphk	int steps;	/* #steps since we last allowed interrupts */
171115810Sphk	int depth;
172115810Sphk	int mpcalls;
173173760Sattilio	int lockcalls;
174115810Sphk	int gcalls;
175122585Smckusick#ifdef DIAGNOSTIC
176122585Smckusick	struct bintime bt1, bt2;
177122585Smckusick	struct timespec ts2;
178122585Smckusick	static uint64_t maxdt = 36893488147419102LL;	/* 2 msec */
179123254Sphk	static timeout_t *lastfunc;
180122585Smckusick#endif
1811541Srgrimes
18233392Sphk#ifndef MAX_SOFTCLOCK_STEPS
18333392Sphk#define MAX_SOFTCLOCK_STEPS 100 /* Maximum allowed value of steps. */
18433392Sphk#endif /* MAX_SOFTCLOCK_STEPS */
18529680Sgibbs
186115810Sphk	mpcalls = 0;
187173760Sattilio	lockcalls = 0;
188115810Sphk	gcalls = 0;
189115810Sphk	depth = 0;
19029680Sgibbs	steps = 0;
19172200Sbmilekic	mtx_lock_spin(&callout_lock);
19229680Sgibbs	while (softticks != ticks) {
19329805Sgibbs		softticks++;
19429805Sgibbs		/*
19529805Sgibbs		 * softticks may be modified by hard clock, so cache
19629805Sgibbs		 * it while we work on a given bucket.
19729805Sgibbs		 */
19829805Sgibbs		curticks = softticks;
19929805Sgibbs		bucket = &callwheel[curticks & callwheelmask];
20029805Sgibbs		c = TAILQ_FIRST(bucket);
20129680Sgibbs		while (c) {
202115810Sphk			depth++;
20329805Sgibbs			if (c->c_time != curticks) {
20429680Sgibbs				c = TAILQ_NEXT(c, c_links.tqe);
20529680Sgibbs				++steps;
20629680Sgibbs				if (steps >= MAX_SOFTCLOCK_STEPS) {
20729680Sgibbs					nextsoftcheck = c;
20829805Sgibbs					/* Give interrupts a chance. */
20972200Sbmilekic					mtx_unlock_spin(&callout_lock);
21081370Sjhb					;	/* nothing */
21172200Sbmilekic					mtx_lock_spin(&callout_lock);
21229680Sgibbs					c = nextsoftcheck;
21329680Sgibbs					steps = 0;
21429680Sgibbs				}
21529680Sgibbs			} else {
21629680Sgibbs				void (*c_func)(void *);
21729680Sgibbs				void *c_arg;
218173760Sattilio				struct lock_class *class;
219173760Sattilio				int c_flags, sharedlock;
22029680Sgibbs
22129680Sgibbs				nextsoftcheck = TAILQ_NEXT(c, c_links.tqe);
22229805Sgibbs				TAILQ_REMOVE(bucket, c, c_links.tqe);
223173760Sattilio				class = (c->c_lock != NULL) ?
224173760Sattilio				    LOCK_CLASS(c->c_lock) : NULL;
225173760Sattilio				sharedlock = (c->c_flags & CALLOUT_SHAREDLOCK) ?
226173760Sattilio				    0 : 1;
22729680Sgibbs				c_func = c->c_func;
22829680Sgibbs				c_arg = c->c_arg;
22968889Sjake				c_flags = c->c_flags;
23044510Swollman				if (c->c_flags & CALLOUT_LOCAL_ALLOC) {
231140489Scperciva					c->c_func = NULL;
23244510Swollman					c->c_flags = CALLOUT_LOCAL_ALLOC;
23344510Swollman					SLIST_INSERT_HEAD(&callfree, c,
23444510Swollman							  c_links.sle);
235141674Siedowse					curr_callout = NULL;
23644510Swollman				} else {
23744510Swollman					c->c_flags =
23850673Sjlemon					    (c->c_flags & ~CALLOUT_PENDING);
239141674Siedowse					curr_callout = c;
24044510Swollman				}
241141428Siedowse				curr_cancelled = 0;
24272200Sbmilekic				mtx_unlock_spin(&callout_lock);
243173760Sattilio				if (class != NULL) {
244173760Sattilio					class->lc_lock(c->c_lock, sharedlock);
245141428Siedowse					/*
246141428Siedowse					 * The callout may have been cancelled
247141428Siedowse					 * while we switched locks.
248141428Siedowse					 */
249141428Siedowse					if (curr_cancelled) {
250173760Sattilio						class->lc_unlock(c->c_lock);
251155957Sjhb						goto skip;
252141428Siedowse					}
253141428Siedowse					/* The callout cannot be stopped now. */
254141428Siedowse					curr_cancelled = 1;
255141428Siedowse
256173760Sattilio					if (c->c_lock == &Giant.lock_object) {
257141428Siedowse						gcalls++;
258163246Sglebius						CTR3(KTR_CALLOUT,
259163246Sglebius						    "callout %p func %p arg %p",
260163246Sglebius						    c, c_func, c_arg);
261141428Siedowse					} else {
262173760Sattilio						lockcalls++;
263173760Sattilio						CTR3(KTR_CALLOUT, "callout lock"
264163246Sglebius						    " %p func %p arg %p",
265163246Sglebius						    c, c_func, c_arg);
266141428Siedowse					}
267115810Sphk				} else {
268115810Sphk					mpcalls++;
269163246Sglebius					CTR3(KTR_CALLOUT,
270163246Sglebius					    "callout mpsafe %p func %p arg %p",
271163246Sglebius					    c, c_func, c_arg);
272115810Sphk				}
273122585Smckusick#ifdef DIAGNOSTIC
274122585Smckusick				binuptime(&bt1);
275122585Smckusick#endif
276150187Sjhb				THREAD_NO_SLEEPING();
27729680Sgibbs				c_func(c_arg);
278150187Sjhb				THREAD_SLEEPING_OK();
279122585Smckusick#ifdef DIAGNOSTIC
280122585Smckusick				binuptime(&bt2);
281122585Smckusick				bintime_sub(&bt2, &bt1);
282122585Smckusick				if (bt2.frac > maxdt) {
283123254Sphk					if (lastfunc != c_func ||
284123254Sphk					    bt2.frac > maxdt * 2) {
285123254Sphk						bintime2timespec(&bt2, &ts2);
286123254Sphk						printf(
287123254Sphk			"Expensive timeout(9) function: %p(%p) %jd.%09ld s\n",
288123254Sphk						    c_func, c_arg,
289123254Sphk						    (intmax_t)ts2.tv_sec,
290123254Sphk						    ts2.tv_nsec);
291123254Sphk					}
292122585Smckusick					maxdt = bt2.frac;
293123254Sphk					lastfunc = c_func;
294122585Smckusick				}
295122585Smckusick#endif
296141428Siedowse				if ((c_flags & CALLOUT_RETURNUNLOCKED) == 0)
297173760Sattilio					class->lc_unlock(c->c_lock);
298155957Sjhb			skip:
29972200Sbmilekic				mtx_lock_spin(&callout_lock);
300127969Scperciva				curr_callout = NULL;
301155957Sjhb				if (callout_wait) {
302127969Scperciva					/*
303155957Sjhb					 * There is someone waiting
304127969Scperciva					 * for the callout to complete.
305127969Scperciva					 */
306171053Sattilio					callout_wait = 0;
307171053Sattilio					mtx_unlock_spin(&callout_lock);
308155957Sjhb					wakeup(&callout_wait);
309171053Sattilio					mtx_lock_spin(&callout_lock);
310128024Scperciva				}
31129680Sgibbs				steps = 0;
31229680Sgibbs				c = nextsoftcheck;
31329680Sgibbs			}
31429680Sgibbs		}
3151541Srgrimes	}
316115810Sphk	avg_depth += (depth * 1000 - avg_depth) >> 8;
317115810Sphk	avg_mpcalls += (mpcalls * 1000 - avg_mpcalls) >> 8;
318173760Sattilio	avg_lockcalls += (lockcalls * 1000 - avg_lockcalls) >> 8;
319115810Sphk	avg_gcalls += (gcalls * 1000 - avg_gcalls) >> 8;
32029680Sgibbs	nextsoftcheck = NULL;
32172200Sbmilekic	mtx_unlock_spin(&callout_lock);
3221541Srgrimes}
3231541Srgrimes
3241541Srgrimes/*
3251541Srgrimes * timeout --
3261541Srgrimes *	Execute a function after a specified length of time.
3271541Srgrimes *
3281541Srgrimes * untimeout --
3291541Srgrimes *	Cancel previous timeout function call.
3301541Srgrimes *
33129680Sgibbs * callout_handle_init --
33229680Sgibbs *	Initialize a handle so that using it with untimeout is benign.
33329680Sgibbs *
3341541Srgrimes *	See AT&T BCI Driver Reference Manual for specification.  This
33529680Sgibbs *	implementation differs from that one in that although an
33629680Sgibbs *	identification value is returned from timeout, the original
33729680Sgibbs *	arguments to timeout as well as the identifier are used to
33829680Sgibbs *	identify entries for untimeout.
3391541Srgrimes */
34029680Sgibbsstruct callout_handle
34129680Sgibbstimeout(ftn, arg, to_ticks)
34233824Sbde	timeout_t *ftn;
3431541Srgrimes	void *arg;
34469147Sjlemon	int to_ticks;
3451541Srgrimes{
34629680Sgibbs	struct callout *new;
34729680Sgibbs	struct callout_handle handle;
3481541Srgrimes
34972200Sbmilekic	mtx_lock_spin(&callout_lock);
3501541Srgrimes
3511541Srgrimes	/* Fill in the next free callout structure. */
35229680Sgibbs	new = SLIST_FIRST(&callfree);
35329680Sgibbs	if (new == NULL)
35429680Sgibbs		/* XXX Attempt to malloc first */
3551541Srgrimes		panic("timeout table full");
35629680Sgibbs	SLIST_REMOVE_HEAD(&callfree, c_links.sle);
35744510Swollman
35844510Swollman	callout_reset(new, to_ticks, ftn, arg);
3591541Srgrimes
36044510Swollman	handle.callout = new;
36172200Sbmilekic	mtx_unlock_spin(&callout_lock);
36229680Sgibbs	return (handle);
3631541Srgrimes}
3641541Srgrimes
3651541Srgrimesvoid
36629680Sgibbsuntimeout(ftn, arg, handle)
36733824Sbde	timeout_t *ftn;
3681541Srgrimes	void *arg;
36929680Sgibbs	struct callout_handle handle;
3701541Srgrimes{
3711541Srgrimes
37229680Sgibbs	/*
37329680Sgibbs	 * Check for a handle that was initialized
37429680Sgibbs	 * by callout_handle_init, but never used
37529680Sgibbs	 * for a real timeout.
37629680Sgibbs	 */
37729680Sgibbs	if (handle.callout == NULL)
37829680Sgibbs		return;
37929680Sgibbs
38072200Sbmilekic	mtx_lock_spin(&callout_lock);
38144510Swollman	if (handle.callout->c_func == ftn && handle.callout->c_arg == arg)
38244510Swollman		callout_stop(handle.callout);
38372200Sbmilekic	mtx_unlock_spin(&callout_lock);
3841541Srgrimes}
3851541Srgrimes
38624101Sbdevoid
38729680Sgibbscallout_handle_init(struct callout_handle *handle)
38829680Sgibbs{
38929680Sgibbs	handle->callout = NULL;
39029680Sgibbs}
39129680Sgibbs
39244510Swollman/*
39344510Swollman * New interface; clients allocate their own callout structures.
39444510Swollman *
39544510Swollman * callout_reset() - establish or change a timeout
39644510Swollman * callout_stop() - disestablish a timeout
39744510Swollman * callout_init() - initialize a callout structure so that it can
39844510Swollman *	safely be passed to callout_reset() and callout_stop()
39944510Swollman *
40050673Sjlemon * <sys/callout.h> defines three convenience macros:
40144510Swollman *
402140487Scperciva * callout_active() - returns truth if callout has not been stopped,
403140487Scperciva *	drained, or deactivated since the last time the callout was
404140487Scperciva *	reset.
40550673Sjlemon * callout_pending() - returns truth if callout is still waiting for timeout
40650673Sjlemon * callout_deactivate() - marks the callout as having been serviced
40744510Swollman */
408149879Sglebiusint
40969147Sjlemoncallout_reset(c, to_ticks, ftn, arg)
41044510Swollman	struct	callout *c;
41144510Swollman	int	to_ticks;
41292723Salfred	void	(*ftn)(void *);
41344510Swollman	void	*arg;
41444510Swollman{
415149879Sglebius	int cancelled = 0;
41644510Swollman
41772200Sbmilekic	mtx_lock_spin(&callout_lock);
418141428Siedowse	if (c == curr_callout) {
419127969Scperciva		/*
420127969Scperciva		 * We're being asked to reschedule a callout which is
421173760Sattilio		 * currently in progress.  If there is a lock then we
422141428Siedowse		 * can cancel the callout if it has not really started.
423127969Scperciva		 */
424173760Sattilio		if (c->c_lock != NULL && !curr_cancelled)
425149879Sglebius			cancelled = curr_cancelled = 1;
426155957Sjhb		if (callout_wait) {
427141428Siedowse			/*
428141428Siedowse			 * Someone has called callout_drain to kill this
429141428Siedowse			 * callout.  Don't reschedule.
430141428Siedowse			 */
431163246Sglebius			CTR4(KTR_CALLOUT, "%s %p func %p arg %p",
432163246Sglebius			    cancelled ? "cancelled" : "failed to cancel",
433163246Sglebius			    c, c->c_func, c->c_arg);
434141428Siedowse			mtx_unlock_spin(&callout_lock);
435149879Sglebius			return (cancelled);
436141428Siedowse		}
437128024Scperciva	}
438133190Scperciva	if (c->c_flags & CALLOUT_PENDING) {
439133190Scperciva		if (nextsoftcheck == c) {
440133190Scperciva			nextsoftcheck = TAILQ_NEXT(c, c_links.tqe);
441133190Scperciva		}
442133190Scperciva		TAILQ_REMOVE(&callwheel[c->c_time & callwheelmask], c,
443133190Scperciva		    c_links.tqe);
44444510Swollman
445149879Sglebius		cancelled = 1;
446149879Sglebius
447133190Scperciva		/*
448133190Scperciva		 * Part of the normal "stop a pending callout" process
449133190Scperciva		 * is to clear the CALLOUT_ACTIVE and CALLOUT_PENDING
450133190Scperciva		 * flags.  We're not going to bother doing that here,
451133190Scperciva		 * because we're going to be setting those flags ten lines
452133190Scperciva		 * after this point, and we're holding callout_lock
453133190Scperciva		 * between now and then.
454133190Scperciva		 */
455133190Scperciva	}
456133190Scperciva
45744510Swollman	/*
45881370Sjhb	 * We could unlock callout_lock here and lock it again before the
45981370Sjhb	 * TAILQ_INSERT_TAIL, but there's no point since doing this setup
46081370Sjhb	 * doesn't take much time.
46144510Swollman	 */
46244510Swollman	if (to_ticks <= 0)
46344510Swollman		to_ticks = 1;
46444510Swollman
46544510Swollman	c->c_arg = arg;
46669147Sjlemon	c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING);
46744510Swollman	c->c_func = ftn;
46844510Swollman	c->c_time = ticks + to_ticks;
46944510Swollman	TAILQ_INSERT_TAIL(&callwheel[c->c_time & callwheelmask],
47044510Swollman			  c, c_links.tqe);
471163246Sglebius	CTR5(KTR_CALLOUT, "%sscheduled %p func %p arg %p in %d",
472163246Sglebius	    cancelled ? "re" : "", c, c->c_func, c->c_arg, to_ticks);
47372200Sbmilekic	mtx_unlock_spin(&callout_lock);
474149879Sglebius
475149879Sglebius	return (cancelled);
47644510Swollman}
47744510Swollman
47881481Sjhbint
479127969Scperciva_callout_stop_safe(c, safe)
480127969Scperciva	struct	callout *c;
481127969Scperciva	int	safe;
482127969Scperciva{
483173760Sattilio	struct lock_class *class;
484173760Sattilio	int use_lock, sq_locked;
485127969Scperciva
486173760Sattilio	/*
487173760Sattilio	 * Some old subsystems don't hold Giant while running a callout_stop(),
488173760Sattilio	 * so just discard this check for the moment.
489173760Sattilio	 */
490173760Sattilio	if (!safe && c->c_lock != NULL) {
491173760Sattilio		if (c->c_lock == &Giant.lock_object)
492173760Sattilio			use_lock = mtx_owned(&Giant);
493173760Sattilio		else {
494173760Sattilio			use_lock = 1;
495173760Sattilio			class = LOCK_CLASS(c->c_lock);
496173760Sattilio			class->lc_assert(c->c_lock, LA_XLOCKED);
497173760Sattilio		}
498173760Sattilio	} else
499173760Sattilio		use_lock = 0;
500141428Siedowse
501172025Sjhb	sq_locked = 0;
502172025Sjhbagain:
50372200Sbmilekic	mtx_lock_spin(&callout_lock);
50444510Swollman	/*
505155957Sjhb	 * If the callout isn't pending, it's not on the queue, so
506155957Sjhb	 * don't attempt to remove it from the queue.  We can try to
507155957Sjhb	 * stop it by other means however.
50844510Swollman	 */
50944510Swollman	if (!(c->c_flags & CALLOUT_PENDING)) {
51050673Sjlemon		c->c_flags &= ~CALLOUT_ACTIVE;
511155957Sjhb
512155957Sjhb		/*
513155957Sjhb		 * If it wasn't on the queue and it isn't the current
514155957Sjhb		 * callout, then we can't stop it, so just bail.
515155957Sjhb		 */
516141428Siedowse		if (c != curr_callout) {
517163246Sglebius			CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p",
518163246Sglebius			    c, c->c_func, c->c_arg);
519141428Siedowse			mtx_unlock_spin(&callout_lock);
520172025Sjhb			if (sq_locked)
521172025Sjhb				sleepq_release(&callout_wait);
522141428Siedowse			return (0);
523141428Siedowse		}
524155957Sjhb
525141428Siedowse		if (safe) {
526127969Scperciva			/*
527155957Sjhb			 * The current callout is running (or just
528155957Sjhb			 * about to run) and blocking is allowed, so
529155957Sjhb			 * just wait for the current invocation to
530155957Sjhb			 * finish.
531127969Scperciva			 */
532155957Sjhb			while (c == curr_callout) {
533171053Sattilio
534171053Sattilio				/*
535171053Sattilio				 * Use direct calls to sleepqueue interface
536171053Sattilio				 * instead of cv/msleep in order to avoid
537171053Sattilio				 * a LOR between callout_lock and sleepqueue
538171053Sattilio				 * chain spinlocks.  This piece of code
539171053Sattilio				 * emulates a msleep_spin() call actually.
540172025Sjhb				 *
541172025Sjhb				 * If we already have the sleepqueue chain
542172025Sjhb				 * locked, then we can safely block.  If we
543172025Sjhb				 * don't already have it locked, however,
544172025Sjhb				 * we have to drop the callout_lock to lock
545172025Sjhb				 * it.  This opens several races, so we
546172025Sjhb				 * restart at the beginning once we have
547172025Sjhb				 * both locks.  If nothing has changed, then
548172025Sjhb				 * we will end up back here with sq_locked
549172025Sjhb				 * set.
550171053Sattilio				 */
551172025Sjhb				if (!sq_locked) {
552172025Sjhb					mtx_unlock_spin(&callout_lock);
553172025Sjhb					sleepq_lock(&callout_wait);
554172025Sjhb					sq_locked = 1;
555172025Sjhb					goto again;
556172025Sjhb				}
557171053Sattilio
558155957Sjhb				callout_wait = 1;
559171053Sattilio				DROP_GIANT();
560171053Sattilio				mtx_unlock_spin(&callout_lock);
561171053Sattilio				sleepq_add(&callout_wait,
562171053Sattilio				    &callout_lock.lock_object, "codrain",
563171053Sattilio				    SLEEPQ_SLEEP, 0);
564171053Sattilio				sleepq_wait(&callout_wait);
565172025Sjhb				sq_locked = 0;
566171053Sattilio
567171053Sattilio				/* Reacquire locks previously released. */
568171053Sattilio				PICKUP_GIANT();
569171053Sattilio				mtx_lock_spin(&callout_lock);
570155957Sjhb			}
571173760Sattilio		} else if (use_lock && !curr_cancelled) {
572155957Sjhb			/*
573173760Sattilio			 * The current callout is waiting for its
574173760Sattilio			 * lock which we hold.  Cancel the callout
575155957Sjhb			 * and return.  After our caller drops the
576173760Sattilio			 * lock, the callout will be skipped in
577155957Sjhb			 * softclock().
578155957Sjhb			 */
579141428Siedowse			curr_cancelled = 1;
580163246Sglebius			CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p",
581163246Sglebius			    c, c->c_func, c->c_arg);
582141428Siedowse			mtx_unlock_spin(&callout_lock);
583172025Sjhb			KASSERT(!sq_locked, ("sleepqueue chain locked"));
584141428Siedowse			return (1);
585155957Sjhb		}
586163246Sglebius		CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p",
587163246Sglebius		    c, c->c_func, c->c_arg);
588155957Sjhb		mtx_unlock_spin(&callout_lock);
589172025Sjhb		KASSERT(!sq_locked, ("sleepqueue chain still locked"));
59081481Sjhb		return (0);
59144510Swollman	}
592172025Sjhb	if (sq_locked)
593172025Sjhb		sleepq_release(&callout_wait);
594172025Sjhb
59550673Sjlemon	c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING);
59644510Swollman
59744510Swollman	if (nextsoftcheck == c) {
59844510Swollman		nextsoftcheck = TAILQ_NEXT(c, c_links.tqe);
59944510Swollman	}
60044510Swollman	TAILQ_REMOVE(&callwheel[c->c_time & callwheelmask], c, c_links.tqe);
60144510Swollman
602163246Sglebius	CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p",
603163246Sglebius	    c, c->c_func, c->c_arg);
604163246Sglebius
60544510Swollman	if (c->c_flags & CALLOUT_LOCAL_ALLOC) {
606140492Scperciva		c->c_func = NULL;
60744510Swollman		SLIST_INSERT_HEAD(&callfree, c, c_links.sle);
60844510Swollman	}
60972200Sbmilekic	mtx_unlock_spin(&callout_lock);
61081481Sjhb	return (1);
61144510Swollman}
61244510Swollman
61344510Swollmanvoid
61469147Sjlemoncallout_init(c, mpsafe)
61544510Swollman	struct	callout *c;
61669147Sjlemon	int mpsafe;
61744510Swollman{
61844527Swollman	bzero(c, sizeof *c);
619141428Siedowse	if (mpsafe) {
620173760Sattilio		c->c_lock = NULL;
621141428Siedowse		c->c_flags = CALLOUT_RETURNUNLOCKED;
622141428Siedowse	} else {
623173760Sattilio		c->c_lock = &Giant.lock_object;
624141428Siedowse		c->c_flags = 0;
625141428Siedowse	}
62644510Swollman}
62744510Swollman
628141428Siedowsevoid
629173760Sattilio_callout_init_lock(c, lock, flags)
630141428Siedowse	struct	callout *c;
631173760Sattilio	struct	lock_object *lock;
632141428Siedowse	int flags;
633141428Siedowse{
634141428Siedowse	bzero(c, sizeof *c);
635173760Sattilio	c->c_lock = lock;
636173760Sattilio	KASSERT((flags & ~(CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK)) == 0,
637173760Sattilio	    ("callout_init_lock: bad flags %d", flags));
638173760Sattilio	KASSERT(lock != NULL || (flags & CALLOUT_RETURNUNLOCKED) == 0,
639173760Sattilio	    ("callout_init_lock: CALLOUT_RETURNUNLOCKED with no lock"));
640173760Sattilio	KASSERT(lock == NULL || LOCK_CLASS(lock) == &lock_class_mtx_sleep ||
641173760Sattilio	    LOCK_CLASS(lock) == &lock_class_rw, ("%s: invalid lock class",
642173760Sattilio	    __func__));
643173760Sattilio	c->c_flags = flags & (CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK);
644141428Siedowse}
645141428Siedowse
64631950Snate#ifdef APM_FIXUP_CALLTODO
64731950Snate/*
64831950Snate * Adjust the kernel calltodo timeout list.  This routine is used after
64931950Snate * an APM resume to recalculate the calltodo timer list values with the
65031950Snate * number of hz's we have been sleeping.  The next hardclock() will detect
65131950Snate * that there are fired timers and run softclock() to execute them.
65231950Snate *
65331950Snate * Please note, I have not done an exhaustive analysis of what code this
65431950Snate * might break.  I am motivated to have my select()'s and alarm()'s that
65531950Snate * have expired during suspend firing upon resume so that the applications
65631950Snate * which set the timer can do the maintanence the timer was for as close
65731950Snate * as possible to the originally intended time.  Testing this code for a
65831950Snate * week showed that resuming from a suspend resulted in 22 to 25 timers
65931950Snate * firing, which seemed independant on whether the suspend was 2 hours or
66031950Snate * 2 days.  Your milage may vary.   - Ken Key <key@cs.utk.edu>
66131950Snate */
66231950Snatevoid
66331950Snateadjust_timeout_calltodo(time_change)
66431950Snate    struct timeval *time_change;
66531950Snate{
66631950Snate	register struct callout *p;
66731950Snate	unsigned long delta_ticks;
66831950Snate
66931950Snate	/*
67031950Snate	 * How many ticks were we asleep?
67136127Sbde	 * (stolen from tvtohz()).
67231950Snate	 */
67331950Snate
67431950Snate	/* Don't do anything */
67531950Snate	if (time_change->tv_sec < 0)
67631950Snate		return;
67731950Snate	else if (time_change->tv_sec <= LONG_MAX / 1000000)
67831950Snate		delta_ticks = (time_change->tv_sec * 1000000 +
67931950Snate			       time_change->tv_usec + (tick - 1)) / tick + 1;
68031950Snate	else if (time_change->tv_sec <= LONG_MAX / hz)
68131950Snate		delta_ticks = time_change->tv_sec * hz +
68231950Snate			      (time_change->tv_usec + (tick - 1)) / tick + 1;
68331950Snate	else
68431950Snate		delta_ticks = LONG_MAX;
68531950Snate
68631950Snate	if (delta_ticks > INT_MAX)
68731950Snate		delta_ticks = INT_MAX;
68831950Snate
68931950Snate	/*
69031950Snate	 * Now rip through the timer calltodo list looking for timers
69131950Snate	 * to expire.
69231950Snate	 */
69331950Snate
69431950Snate	/* don't collide with softclock() */
69572200Sbmilekic	mtx_lock_spin(&callout_lock);
69631950Snate	for (p = calltodo.c_next; p != NULL; p = p->c_next) {
69731950Snate		p->c_time -= delta_ticks;
69831950Snate
69931950Snate		/* Break if the timer had more time on it than delta_ticks */
70031950Snate		if (p->c_time > 0)
70131950Snate			break;
70231950Snate
70331950Snate		/* take back the ticks the timer didn't use (p->c_time <= 0) */
70431950Snate		delta_ticks = -p->c_time;
70531950Snate	}
70672200Sbmilekic	mtx_unlock_spin(&callout_lock);
70731950Snate
70831950Snate	return;
70931950Snate}
71031950Snate#endif /* APM_FIXUP_CALLTODO */
711