xref: /freebsd/sys/kern/kern_timeout.c (revision a0e793cbf1951d07fc47a0d9ea389d7dacba5213)
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  * 4. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  *
34  *	From: @(#)kern_clock.c	8.5 (Berkeley) 1/21/94
35  */
36 
37 #include <sys/cdefs.h>
38 __FBSDID("$FreeBSD$");
39 
40 #include "opt_callout_profiling.h"
41 #if defined(__arm__)
42 #include "opt_timer.h"
43 #endif
44 #include "opt_rss.h"
45 
46 #include <sys/param.h>
47 #include <sys/systm.h>
48 #include <sys/bus.h>
49 #include <sys/callout.h>
50 #include <sys/file.h>
51 #include <sys/interrupt.h>
52 #include <sys/kernel.h>
53 #include <sys/ktr.h>
54 #include <sys/lock.h>
55 #include <sys/malloc.h>
56 #include <sys/mutex.h>
57 #include <sys/proc.h>
58 #include <sys/sdt.h>
59 #include <sys/sleepqueue.h>
60 #include <sys/sysctl.h>
61 #include <sys/smp.h>
62 
63 #ifdef SMP
64 #include <machine/cpu.h>
65 #endif
66 
67 #ifndef NO_EVENTTIMERS
68 DPCPU_DECLARE(sbintime_t, hardclocktime);
69 #endif
70 
71 SDT_PROVIDER_DEFINE(callout_execute);
72 SDT_PROBE_DEFINE1(callout_execute, kernel, , callout__start,
73     "struct callout *");
74 SDT_PROBE_DEFINE1(callout_execute, kernel, , callout__end,
75     "struct callout *");
76 
77 #ifdef CALLOUT_PROFILING
78 static int avg_depth;
79 SYSCTL_INT(_debug, OID_AUTO, to_avg_depth, CTLFLAG_RD, &avg_depth, 0,
80     "Average number of items examined per softclock call. Units = 1/1000");
81 static int avg_gcalls;
82 SYSCTL_INT(_debug, OID_AUTO, to_avg_gcalls, CTLFLAG_RD, &avg_gcalls, 0,
83     "Average number of Giant callouts made per softclock call. Units = 1/1000");
84 static int avg_lockcalls;
85 SYSCTL_INT(_debug, OID_AUTO, to_avg_lockcalls, CTLFLAG_RD, &avg_lockcalls, 0,
86     "Average number of lock callouts made per softclock call. Units = 1/1000");
87 static int avg_mpcalls;
88 SYSCTL_INT(_debug, OID_AUTO, to_avg_mpcalls, CTLFLAG_RD, &avg_mpcalls, 0,
89     "Average number of MP callouts made per softclock call. Units = 1/1000");
90 static int avg_depth_dir;
91 SYSCTL_INT(_debug, OID_AUTO, to_avg_depth_dir, CTLFLAG_RD, &avg_depth_dir, 0,
92     "Average number of direct callouts examined per callout_process call. "
93     "Units = 1/1000");
94 static int avg_lockcalls_dir;
95 SYSCTL_INT(_debug, OID_AUTO, to_avg_lockcalls_dir, CTLFLAG_RD,
96     &avg_lockcalls_dir, 0, "Average number of lock direct callouts made per "
97     "callout_process call. Units = 1/1000");
98 static int avg_mpcalls_dir;
99 SYSCTL_INT(_debug, OID_AUTO, to_avg_mpcalls_dir, CTLFLAG_RD, &avg_mpcalls_dir,
100     0, "Average number of MP direct callouts made per callout_process call. "
101     "Units = 1/1000");
102 #endif
103 
104 static int ncallout;
105 SYSCTL_INT(_kern, OID_AUTO, ncallout, CTLFLAG_RDTUN | CTLFLAG_NOFETCH, &ncallout, 0,
106     "Number of entries in callwheel and size of timeout() preallocation");
107 
108 #ifdef	RSS
109 static int pin_default_swi = 1;
110 static int pin_pcpu_swi = 1;
111 #else
112 static int pin_default_swi = 0;
113 static int pin_pcpu_swi = 0;
114 #endif
115 
116 SYSCTL_INT(_kern, OID_AUTO, pin_default_swi, CTLFLAG_RDTUN | CTLFLAG_NOFETCH, &pin_default_swi,
117     0, "Pin the default (non-per-cpu) swi (shared with PCPU 0 swi)");
118 SYSCTL_INT(_kern, OID_AUTO, pin_pcpu_swi, CTLFLAG_RDTUN | CTLFLAG_NOFETCH, &pin_pcpu_swi,
119     0, "Pin the per-CPU swis (except PCPU 0, which is also default");
120 
121 /*
122  * TODO:
123  *	allocate more timeout table slots when table overflows.
124  */
125 u_int callwheelsize, callwheelmask;
126 
127 /*
128  * The callout cpu exec entities represent informations necessary for
129  * describing the state of callouts currently running on the CPU and the ones
130  * necessary for migrating callouts to the new callout cpu. In particular,
131  * the first entry of the array cc_exec_entity holds informations for callout
132  * running in SWI thread context, while the second one holds informations
133  * for callout running directly from hardware interrupt context.
134  * The cached informations are very important for deferring migration when
135  * the migrating callout is already running.
136  */
137 struct cc_exec {
138 	struct callout		*cc_next;
139 	struct callout		*cc_curr;
140 #ifdef SMP
141 	void			(*ce_migration_func)(void *);
142 	void			*ce_migration_arg;
143 	int			ce_migration_cpu;
144 	sbintime_t		ce_migration_time;
145 	sbintime_t		ce_migration_prec;
146 #endif
147 	bool			cc_cancel;
148 	bool			cc_waiting;
149 };
150 
151 /*
152  * There is one struct callout_cpu per cpu, holding all relevant
153  * state for the callout processing thread on the individual CPU.
154  */
155 struct callout_cpu {
156 	struct mtx_padalign	cc_lock;
157 	struct cc_exec 		cc_exec_entity[2];
158 	struct callout		*cc_callout;
159 	struct callout_list	*cc_callwheel;
160 	struct callout_tailq	cc_expireq;
161 	struct callout_slist	cc_callfree;
162 	sbintime_t		cc_firstevent;
163 	sbintime_t		cc_lastscan;
164 	void			*cc_cookie;
165 	u_int			cc_bucket;
166 };
167 
168 #define	cc_exec_curr		cc_exec_entity[0].cc_curr
169 #define	cc_exec_next		cc_exec_entity[0].cc_next
170 #define	cc_exec_cancel		cc_exec_entity[0].cc_cancel
171 #define	cc_exec_waiting		cc_exec_entity[0].cc_waiting
172 #define	cc_exec_curr_dir	cc_exec_entity[1].cc_curr
173 #define	cc_exec_next_dir	cc_exec_entity[1].cc_next
174 #define	cc_exec_cancel_dir	cc_exec_entity[1].cc_cancel
175 #define	cc_exec_waiting_dir	cc_exec_entity[1].cc_waiting
176 
177 #ifdef SMP
178 #define	cc_migration_func	cc_exec_entity[0].ce_migration_func
179 #define	cc_migration_arg	cc_exec_entity[0].ce_migration_arg
180 #define	cc_migration_cpu	cc_exec_entity[0].ce_migration_cpu
181 #define	cc_migration_time	cc_exec_entity[0].ce_migration_time
182 #define	cc_migration_prec	cc_exec_entity[0].ce_migration_prec
183 #define	cc_migration_func_dir	cc_exec_entity[1].ce_migration_func
184 #define	cc_migration_arg_dir	cc_exec_entity[1].ce_migration_arg
185 #define	cc_migration_cpu_dir	cc_exec_entity[1].ce_migration_cpu
186 #define	cc_migration_time_dir	cc_exec_entity[1].ce_migration_time
187 #define	cc_migration_prec_dir	cc_exec_entity[1].ce_migration_prec
188 
189 struct callout_cpu cc_cpu[MAXCPU];
190 #define	CPUBLOCK	MAXCPU
191 #define	CC_CPU(cpu)	(&cc_cpu[(cpu)])
192 #define	CC_SELF()	CC_CPU(PCPU_GET(cpuid))
193 #else
194 struct callout_cpu cc_cpu;
195 #define	CC_CPU(cpu)	&cc_cpu
196 #define	CC_SELF()	&cc_cpu
197 #endif
198 #define	CC_LOCK(cc)	mtx_lock_spin(&(cc)->cc_lock)
199 #define	CC_UNLOCK(cc)	mtx_unlock_spin(&(cc)->cc_lock)
200 #define	CC_LOCK_ASSERT(cc)	mtx_assert(&(cc)->cc_lock, MA_OWNED)
201 
202 static int timeout_cpu;
203 
204 static void	callout_cpu_init(struct callout_cpu *cc);
205 static void	softclock_call_cc(struct callout *c, struct callout_cpu *cc,
206 #ifdef CALLOUT_PROFILING
207 		    int *mpcalls, int *lockcalls, int *gcalls,
208 #endif
209 		    int direct);
210 
211 static MALLOC_DEFINE(M_CALLOUT, "callout", "Callout datastructures");
212 
213 /**
214  * Locked by cc_lock:
215  *   cc_curr         - If a callout is in progress, it is cc_curr.
216  *                     If cc_curr is non-NULL, threads waiting in
217  *                     callout_drain() will be woken up as soon as the
218  *                     relevant callout completes.
219  *   cc_cancel       - Changing to 1 with both callout_lock and cc_lock held
220  *                     guarantees that the current callout will not run.
221  *                     The softclock() function sets this to 0 before it
222  *                     drops callout_lock to acquire c_lock, and it calls
223  *                     the handler only if curr_cancelled is still 0 after
224  *                     cc_lock is successfully acquired.
225  *   cc_waiting      - If a thread is waiting in callout_drain(), then
226  *                     callout_wait is nonzero.  Set only when
227  *                     cc_curr is non-NULL.
228  */
229 
230 /*
231  * Resets the execution entity tied to a specific callout cpu.
232  */
233 static void
234 cc_cce_cleanup(struct callout_cpu *cc, int direct)
235 {
236 
237 	cc->cc_exec_entity[direct].cc_curr = NULL;
238 	cc->cc_exec_entity[direct].cc_next = NULL;
239 	cc->cc_exec_entity[direct].cc_cancel = false;
240 	cc->cc_exec_entity[direct].cc_waiting = false;
241 #ifdef SMP
242 	cc->cc_exec_entity[direct].ce_migration_cpu = CPUBLOCK;
243 	cc->cc_exec_entity[direct].ce_migration_time = 0;
244 	cc->cc_exec_entity[direct].ce_migration_prec = 0;
245 	cc->cc_exec_entity[direct].ce_migration_func = NULL;
246 	cc->cc_exec_entity[direct].ce_migration_arg = NULL;
247 #endif
248 }
249 
250 /*
251  * Checks if migration is requested by a specific callout cpu.
252  */
253 static int
254 cc_cce_migrating(struct callout_cpu *cc, int direct)
255 {
256 
257 #ifdef SMP
258 	return (cc->cc_exec_entity[direct].ce_migration_cpu != CPUBLOCK);
259 #else
260 	return (0);
261 #endif
262 }
263 
264 /*
265  * Kernel low level callwheel initialization
266  * called on cpu0 during kernel startup.
267  */
268 static void
269 callout_callwheel_init(void *dummy)
270 {
271 	struct callout_cpu *cc;
272 
273 	/*
274 	 * Calculate the size of the callout wheel and the preallocated
275 	 * timeout() structures.
276 	 * XXX: Clip callout to result of previous function of maxusers
277 	 * maximum 384.  This is still huge, but acceptable.
278 	 */
279 	ncallout = imin(16 + maxproc + maxfiles, 18508);
280 	TUNABLE_INT_FETCH("kern.ncallout", &ncallout);
281 
282 	/*
283 	 * Calculate callout wheel size, should be next power of two higher
284 	 * than 'ncallout'.
285 	 */
286 	callwheelsize = 1 << fls(ncallout);
287 	callwheelmask = callwheelsize - 1;
288 
289 	/*
290 	 * Fetch whether we're pinning the swi's or not.
291 	 */
292 	TUNABLE_INT_FETCH("kern.pin_default_swi", &pin_default_swi);
293 	TUNABLE_INT_FETCH("kern.pin_pcpu_swi", &pin_pcpu_swi);
294 
295 	/*
296 	 * Only cpu0 handles timeout(9) and receives a preallocation.
297 	 *
298 	 * XXX: Once all timeout(9) consumers are converted this can
299 	 * be removed.
300 	 */
301 	timeout_cpu = PCPU_GET(cpuid);
302 	cc = CC_CPU(timeout_cpu);
303 	cc->cc_callout = malloc(ncallout * sizeof(struct callout),
304 	    M_CALLOUT, M_WAITOK);
305 	callout_cpu_init(cc);
306 }
307 SYSINIT(callwheel_init, SI_SUB_CPU, SI_ORDER_ANY, callout_callwheel_init, NULL);
308 
309 /*
310  * Initialize the per-cpu callout structures.
311  */
312 static void
313 callout_cpu_init(struct callout_cpu *cc)
314 {
315 	struct callout *c;
316 	int i;
317 
318 	mtx_init(&cc->cc_lock, "callout", NULL, MTX_SPIN | MTX_RECURSE);
319 	SLIST_INIT(&cc->cc_callfree);
320 	cc->cc_callwheel = malloc(sizeof(struct callout_list) * callwheelsize,
321 	    M_CALLOUT, M_WAITOK);
322 	for (i = 0; i < callwheelsize; i++)
323 		LIST_INIT(&cc->cc_callwheel[i]);
324 	TAILQ_INIT(&cc->cc_expireq);
325 	cc->cc_firstevent = SBT_MAX;
326 	for (i = 0; i < 2; i++)
327 		cc_cce_cleanup(cc, i);
328 	if (cc->cc_callout == NULL)	/* Only cpu0 handles timeout(9) */
329 		return;
330 	for (i = 0; i < ncallout; i++) {
331 		c = &cc->cc_callout[i];
332 		callout_init(c, 0);
333 		c->c_flags = CALLOUT_LOCAL_ALLOC;
334 		SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle);
335 	}
336 }
337 
338 #ifdef SMP
339 /*
340  * Switches the cpu tied to a specific callout.
341  * The function expects a locked incoming callout cpu and returns with
342  * locked outcoming callout cpu.
343  */
344 static struct callout_cpu *
345 callout_cpu_switch(struct callout *c, struct callout_cpu *cc, int new_cpu)
346 {
347 	struct callout_cpu *new_cc;
348 
349 	MPASS(c != NULL && cc != NULL);
350 	CC_LOCK_ASSERT(cc);
351 
352 	/*
353 	 * Avoid interrupts and preemption firing after the callout cpu
354 	 * is blocked in order to avoid deadlocks as the new thread
355 	 * may be willing to acquire the callout cpu lock.
356 	 */
357 	c->c_cpu = CPUBLOCK;
358 	spinlock_enter();
359 	CC_UNLOCK(cc);
360 	new_cc = CC_CPU(new_cpu);
361 	CC_LOCK(new_cc);
362 	spinlock_exit();
363 	c->c_cpu = new_cpu;
364 	return (new_cc);
365 }
366 #endif
367 
368 /*
369  * Start standard softclock thread.
370  */
371 static void
372 start_softclock(void *dummy)
373 {
374 	struct callout_cpu *cc;
375 	char name[MAXCOMLEN];
376 #ifdef SMP
377 	int cpu;
378 	struct intr_event *ie;
379 #endif
380 
381 	cc = CC_CPU(timeout_cpu);
382 	snprintf(name, sizeof(name), "clock (%d)", timeout_cpu);
383 	if (swi_add(&clk_intr_event, name, softclock, cc, SWI_CLOCK,
384 	    INTR_MPSAFE, &cc->cc_cookie))
385 		panic("died while creating standard software ithreads");
386 	if (pin_default_swi &&
387 	    (intr_event_bind(clk_intr_event, timeout_cpu) != 0)) {
388 		printf("%s: timeout clock couldn't be pinned to cpu %d\n",
389 		    __func__,
390 		    timeout_cpu);
391 	}
392 
393 #ifdef SMP
394 	CPU_FOREACH(cpu) {
395 		if (cpu == timeout_cpu)
396 			continue;
397 		cc = CC_CPU(cpu);
398 		cc->cc_callout = NULL;	/* Only cpu0 handles timeout(9). */
399 		callout_cpu_init(cc);
400 		snprintf(name, sizeof(name), "clock (%d)", cpu);
401 		ie = NULL;
402 		if (swi_add(&ie, name, softclock, cc, SWI_CLOCK,
403 		    INTR_MPSAFE, &cc->cc_cookie))
404 			panic("died while creating standard software ithreads");
405 		if (pin_pcpu_swi && (intr_event_bind(ie, cpu) != 0)) {
406 			printf("%s: per-cpu clock couldn't be pinned to "
407 			    "cpu %d\n",
408 			    __func__,
409 			    cpu);
410 		}
411 	}
412 #endif
413 }
414 SYSINIT(start_softclock, SI_SUB_SOFTINTR, SI_ORDER_FIRST, start_softclock, NULL);
415 
416 #define	CC_HASH_SHIFT	8
417 
418 static inline u_int
419 callout_hash(sbintime_t sbt)
420 {
421 
422 	return (sbt >> (32 - CC_HASH_SHIFT));
423 }
424 
425 static inline u_int
426 callout_get_bucket(sbintime_t sbt)
427 {
428 
429 	return (callout_hash(sbt) & callwheelmask);
430 }
431 
432 void
433 callout_process(sbintime_t now)
434 {
435 	struct callout *tmp, *tmpn;
436 	struct callout_cpu *cc;
437 	struct callout_list *sc;
438 	sbintime_t first, last, max, tmp_max;
439 	uint32_t lookahead;
440 	u_int firstb, lastb, nowb;
441 #ifdef CALLOUT_PROFILING
442 	int depth_dir = 0, mpcalls_dir = 0, lockcalls_dir = 0;
443 #endif
444 
445 	cc = CC_SELF();
446 	mtx_lock_spin_flags(&cc->cc_lock, MTX_QUIET);
447 
448 	/* Compute the buckets of the last scan and present times. */
449 	firstb = callout_hash(cc->cc_lastscan);
450 	cc->cc_lastscan = now;
451 	nowb = callout_hash(now);
452 
453 	/* Compute the last bucket and minimum time of the bucket after it. */
454 	if (nowb == firstb)
455 		lookahead = (SBT_1S / 16);
456 	else if (nowb - firstb == 1)
457 		lookahead = (SBT_1S / 8);
458 	else
459 		lookahead = (SBT_1S / 2);
460 	first = last = now;
461 	first += (lookahead / 2);
462 	last += lookahead;
463 	last &= (0xffffffffffffffffLLU << (32 - CC_HASH_SHIFT));
464 	lastb = callout_hash(last) - 1;
465 	max = last;
466 
467 	/*
468 	 * Check if we wrapped around the entire wheel from the last scan.
469 	 * In case, we need to scan entirely the wheel for pending callouts.
470 	 */
471 	if (lastb - firstb >= callwheelsize) {
472 		lastb = firstb + callwheelsize - 1;
473 		if (nowb - firstb >= callwheelsize)
474 			nowb = lastb;
475 	}
476 
477 	/* Iterate callwheel from firstb to nowb and then up to lastb. */
478 	do {
479 		sc = &cc->cc_callwheel[firstb & callwheelmask];
480 		tmp = LIST_FIRST(sc);
481 		while (tmp != NULL) {
482 			/* Run the callout if present time within allowed. */
483 			if (tmp->c_time <= now) {
484 				/*
485 				 * Consumer told us the callout may be run
486 				 * directly from hardware interrupt context.
487 				 */
488 				if (tmp->c_flags & CALLOUT_DIRECT) {
489 #ifdef CALLOUT_PROFILING
490 					++depth_dir;
491 #endif
492 					cc->cc_exec_next_dir =
493 					    LIST_NEXT(tmp, c_links.le);
494 					cc->cc_bucket = firstb & callwheelmask;
495 					LIST_REMOVE(tmp, c_links.le);
496 					softclock_call_cc(tmp, cc,
497 #ifdef CALLOUT_PROFILING
498 					    &mpcalls_dir, &lockcalls_dir, NULL,
499 #endif
500 					    1);
501 					tmp = cc->cc_exec_next_dir;
502 				} else {
503 					tmpn = LIST_NEXT(tmp, c_links.le);
504 					LIST_REMOVE(tmp, c_links.le);
505 					TAILQ_INSERT_TAIL(&cc->cc_expireq,
506 					    tmp, c_links.tqe);
507 					tmp->c_flags |= CALLOUT_PROCESSED;
508 					tmp = tmpn;
509 				}
510 				continue;
511 			}
512 			/* Skip events from distant future. */
513 			if (tmp->c_time >= max)
514 				goto next;
515 			/*
516 			 * Event minimal time is bigger than present maximal
517 			 * time, so it cannot be aggregated.
518 			 */
519 			if (tmp->c_time > last) {
520 				lastb = nowb;
521 				goto next;
522 			}
523 			/* Update first and last time, respecting this event. */
524 			if (tmp->c_time < first)
525 				first = tmp->c_time;
526 			tmp_max = tmp->c_time + tmp->c_precision;
527 			if (tmp_max < last)
528 				last = tmp_max;
529 next:
530 			tmp = LIST_NEXT(tmp, c_links.le);
531 		}
532 		/* Proceed with the next bucket. */
533 		firstb++;
534 		/*
535 		 * Stop if we looked after present time and found
536 		 * some event we can't execute at now.
537 		 * Stop if we looked far enough into the future.
538 		 */
539 	} while (((int)(firstb - lastb)) <= 0);
540 	cc->cc_firstevent = last;
541 #ifndef NO_EVENTTIMERS
542 	cpu_new_callout(curcpu, last, first);
543 #endif
544 #ifdef CALLOUT_PROFILING
545 	avg_depth_dir += (depth_dir * 1000 - avg_depth_dir) >> 8;
546 	avg_mpcalls_dir += (mpcalls_dir * 1000 - avg_mpcalls_dir) >> 8;
547 	avg_lockcalls_dir += (lockcalls_dir * 1000 - avg_lockcalls_dir) >> 8;
548 #endif
549 	mtx_unlock_spin_flags(&cc->cc_lock, MTX_QUIET);
550 	/*
551 	 * swi_sched acquires the thread lock, so we don't want to call it
552 	 * with cc_lock held; incorrect locking order.
553 	 */
554 	if (!TAILQ_EMPTY(&cc->cc_expireq))
555 		swi_sched(cc->cc_cookie, 0);
556 }
557 
558 static struct callout_cpu *
559 callout_lock(struct callout *c)
560 {
561 	struct callout_cpu *cc;
562 	int cpu;
563 
564 	for (;;) {
565 		cpu = c->c_cpu;
566 #ifdef SMP
567 		if (cpu == CPUBLOCK) {
568 			while (c->c_cpu == CPUBLOCK)
569 				cpu_spinwait();
570 			continue;
571 		}
572 #endif
573 		cc = CC_CPU(cpu);
574 		CC_LOCK(cc);
575 		if (cpu == c->c_cpu)
576 			break;
577 		CC_UNLOCK(cc);
578 	}
579 	return (cc);
580 }
581 
582 static void
583 callout_cc_add(struct callout *c, struct callout_cpu *cc,
584     sbintime_t sbt, sbintime_t precision, void (*func)(void *),
585     void *arg, int cpu, int flags)
586 {
587 	int bucket;
588 
589 	CC_LOCK_ASSERT(cc);
590 	if (sbt < cc->cc_lastscan)
591 		sbt = cc->cc_lastscan;
592 	c->c_arg = arg;
593 	c->c_flags |= (CALLOUT_ACTIVE | CALLOUT_PENDING);
594 	if (flags & C_DIRECT_EXEC)
595 		c->c_flags |= CALLOUT_DIRECT;
596 	c->c_flags &= ~CALLOUT_PROCESSED;
597 	c->c_func = func;
598 	c->c_time = sbt;
599 	c->c_precision = precision;
600 	bucket = callout_get_bucket(c->c_time);
601 	CTR3(KTR_CALLOUT, "precision set for %p: %d.%08x",
602 	    c, (int)(c->c_precision >> 32),
603 	    (u_int)(c->c_precision & 0xffffffff));
604 	LIST_INSERT_HEAD(&cc->cc_callwheel[bucket], c, c_links.le);
605 	if (cc->cc_bucket == bucket)
606 		cc->cc_exec_next_dir = c;
607 #ifndef NO_EVENTTIMERS
608 	/*
609 	 * Inform the eventtimers(4) subsystem there's a new callout
610 	 * that has been inserted, but only if really required.
611 	 */
612 	if (SBT_MAX - c->c_time < c->c_precision)
613 		c->c_precision = SBT_MAX - c->c_time;
614 	sbt = c->c_time + c->c_precision;
615 	if (sbt < cc->cc_firstevent) {
616 		cc->cc_firstevent = sbt;
617 		cpu_new_callout(cpu, sbt, c->c_time);
618 	}
619 #endif
620 }
621 
622 static void
623 callout_cc_del(struct callout *c, struct callout_cpu *cc)
624 {
625 
626 	if ((c->c_flags & CALLOUT_LOCAL_ALLOC) == 0)
627 		return;
628 	c->c_func = NULL;
629 	SLIST_INSERT_HEAD(&cc->cc_callfree, c, c_links.sle);
630 }
631 
632 static void
633 softclock_call_cc(struct callout *c, struct callout_cpu *cc,
634 #ifdef CALLOUT_PROFILING
635     int *mpcalls, int *lockcalls, int *gcalls,
636 #endif
637     int direct)
638 {
639 	struct rm_priotracker tracker;
640 	void (*c_func)(void *);
641 	void *c_arg;
642 	struct lock_class *class;
643 	struct lock_object *c_lock;
644 	uintptr_t lock_status;
645 	int c_flags;
646 #ifdef SMP
647 	struct callout_cpu *new_cc;
648 	void (*new_func)(void *);
649 	void *new_arg;
650 	int flags, new_cpu;
651 	sbintime_t new_prec, new_time;
652 #endif
653 #if defined(DIAGNOSTIC) || defined(CALLOUT_PROFILING)
654 	sbintime_t sbt1, sbt2;
655 	struct timespec ts2;
656 	static sbintime_t maxdt = 2 * SBT_1MS;	/* 2 msec */
657 	static timeout_t *lastfunc;
658 #endif
659 
660 	KASSERT((c->c_flags & (CALLOUT_PENDING | CALLOUT_ACTIVE)) ==
661 	    (CALLOUT_PENDING | CALLOUT_ACTIVE),
662 	    ("softclock_call_cc: pend|act %p %x", c, c->c_flags));
663 	class = (c->c_lock != NULL) ? LOCK_CLASS(c->c_lock) : NULL;
664 	lock_status = 0;
665 	if (c->c_flags & CALLOUT_SHAREDLOCK) {
666 		if (class == &lock_class_rm)
667 			lock_status = (uintptr_t)&tracker;
668 		else
669 			lock_status = 1;
670 	}
671 	c_lock = c->c_lock;
672 	c_func = c->c_func;
673 	c_arg = c->c_arg;
674 	c_flags = c->c_flags;
675 	if (c->c_flags & CALLOUT_LOCAL_ALLOC)
676 		c->c_flags = CALLOUT_LOCAL_ALLOC;
677 	else
678 		c->c_flags &= ~CALLOUT_PENDING;
679 	cc->cc_exec_entity[direct].cc_curr = c;
680 	cc->cc_exec_entity[direct].cc_cancel = false;
681 	CC_UNLOCK(cc);
682 	if (c_lock != NULL) {
683 		class->lc_lock(c_lock, lock_status);
684 		/*
685 		 * The callout may have been cancelled
686 		 * while we switched locks.
687 		 */
688 		if (cc->cc_exec_entity[direct].cc_cancel) {
689 			class->lc_unlock(c_lock);
690 			goto skip;
691 		}
692 		/* The callout cannot be stopped now. */
693 		cc->cc_exec_entity[direct].cc_cancel = true;
694 		if (c_lock == &Giant.lock_object) {
695 #ifdef CALLOUT_PROFILING
696 			(*gcalls)++;
697 #endif
698 			CTR3(KTR_CALLOUT, "callout giant %p func %p arg %p",
699 			    c, c_func, c_arg);
700 		} else {
701 #ifdef CALLOUT_PROFILING
702 			(*lockcalls)++;
703 #endif
704 			CTR3(KTR_CALLOUT, "callout lock %p func %p arg %p",
705 			    c, c_func, c_arg);
706 		}
707 	} else {
708 #ifdef CALLOUT_PROFILING
709 		(*mpcalls)++;
710 #endif
711 		CTR3(KTR_CALLOUT, "callout %p func %p arg %p",
712 		    c, c_func, c_arg);
713 	}
714 #if defined(DIAGNOSTIC) || defined(CALLOUT_PROFILING)
715 	sbt1 = sbinuptime();
716 #endif
717 	THREAD_NO_SLEEPING();
718 	SDT_PROBE(callout_execute, kernel, , callout__start, c, 0, 0, 0, 0);
719 	c_func(c_arg);
720 	SDT_PROBE(callout_execute, kernel, , callout__end, c, 0, 0, 0, 0);
721 	THREAD_SLEEPING_OK();
722 #if defined(DIAGNOSTIC) || defined(CALLOUT_PROFILING)
723 	sbt2 = sbinuptime();
724 	sbt2 -= sbt1;
725 	if (sbt2 > maxdt) {
726 		if (lastfunc != c_func || sbt2 > maxdt * 2) {
727 			ts2 = sbttots(sbt2);
728 			printf(
729 		"Expensive timeout(9) function: %p(%p) %jd.%09ld s\n",
730 			    c_func, c_arg, (intmax_t)ts2.tv_sec, ts2.tv_nsec);
731 		}
732 		maxdt = sbt2;
733 		lastfunc = c_func;
734 	}
735 #endif
736 	CTR1(KTR_CALLOUT, "callout %p finished", c);
737 	if ((c_flags & CALLOUT_RETURNUNLOCKED) == 0)
738 		class->lc_unlock(c_lock);
739 skip:
740 	CC_LOCK(cc);
741 	KASSERT(cc->cc_exec_entity[direct].cc_curr == c, ("mishandled cc_curr"));
742 	cc->cc_exec_entity[direct].cc_curr = NULL;
743 	if (cc->cc_exec_entity[direct].cc_waiting) {
744 		/*
745 		 * There is someone waiting for the
746 		 * callout to complete.
747 		 * If the callout was scheduled for
748 		 * migration just cancel it.
749 		 */
750 		if (cc_cce_migrating(cc, direct)) {
751 			cc_cce_cleanup(cc, direct);
752 
753 			/*
754 			 * It should be assert here that the callout is not
755 			 * destroyed but that is not easy.
756 			 */
757 			c->c_flags &= ~CALLOUT_DFRMIGRATION;
758 		}
759 		cc->cc_exec_entity[direct].cc_waiting = false;
760 		CC_UNLOCK(cc);
761 		wakeup(&cc->cc_exec_entity[direct].cc_waiting);
762 		CC_LOCK(cc);
763 	} else if (cc_cce_migrating(cc, direct)) {
764 		KASSERT((c_flags & CALLOUT_LOCAL_ALLOC) == 0,
765 		    ("Migrating legacy callout %p", c));
766 #ifdef SMP
767 		/*
768 		 * If the callout was scheduled for
769 		 * migration just perform it now.
770 		 */
771 		new_cpu = cc->cc_exec_entity[direct].ce_migration_cpu;
772 		new_time = cc->cc_exec_entity[direct].ce_migration_time;
773 		new_prec = cc->cc_exec_entity[direct].ce_migration_prec;
774 		new_func = cc->cc_exec_entity[direct].ce_migration_func;
775 		new_arg = cc->cc_exec_entity[direct].ce_migration_arg;
776 		cc_cce_cleanup(cc, direct);
777 
778 		/*
779 		 * It should be assert here that the callout is not destroyed
780 		 * but that is not easy.
781 		 *
782 		 * As first thing, handle deferred callout stops.
783 		 */
784 		if ((c->c_flags & CALLOUT_DFRMIGRATION) == 0) {
785 			CTR3(KTR_CALLOUT,
786 			     "deferred cancelled %p func %p arg %p",
787 			     c, new_func, new_arg);
788 			callout_cc_del(c, cc);
789 			return;
790 		}
791 		c->c_flags &= ~CALLOUT_DFRMIGRATION;
792 
793 		new_cc = callout_cpu_switch(c, cc, new_cpu);
794 		flags = (direct) ? C_DIRECT_EXEC : 0;
795 		callout_cc_add(c, new_cc, new_time, new_prec, new_func,
796 		    new_arg, new_cpu, flags);
797 		CC_UNLOCK(new_cc);
798 		CC_LOCK(cc);
799 #else
800 		panic("migration should not happen");
801 #endif
802 	}
803 	/*
804 	 * If the current callout is locally allocated (from
805 	 * timeout(9)) then put it on the freelist.
806 	 *
807 	 * Note: we need to check the cached copy of c_flags because
808 	 * if it was not local, then it's not safe to deref the
809 	 * callout pointer.
810 	 */
811 	KASSERT((c_flags & CALLOUT_LOCAL_ALLOC) == 0 ||
812 	    c->c_flags == CALLOUT_LOCAL_ALLOC,
813 	    ("corrupted callout"));
814 	if (c_flags & CALLOUT_LOCAL_ALLOC)
815 		callout_cc_del(c, cc);
816 }
817 
818 /*
819  * The callout mechanism is based on the work of Adam M. Costello and
820  * George Varghese, published in a technical report entitled "Redesigning
821  * the BSD Callout and Timer Facilities" and modified slightly for inclusion
822  * in FreeBSD by Justin T. Gibbs.  The original work on the data structures
823  * used in this implementation was published by G. Varghese and T. Lauck in
824  * the paper "Hashed and Hierarchical Timing Wheels: Data Structures for
825  * the Efficient Implementation of a Timer Facility" in the Proceedings of
826  * the 11th ACM Annual Symposium on Operating Systems Principles,
827  * Austin, Texas Nov 1987.
828  */
829 
830 /*
831  * Software (low priority) clock interrupt.
832  * Run periodic events from timeout queue.
833  */
834 void
835 softclock(void *arg)
836 {
837 	struct callout_cpu *cc;
838 	struct callout *c;
839 #ifdef CALLOUT_PROFILING
840 	int depth = 0, gcalls = 0, lockcalls = 0, mpcalls = 0;
841 #endif
842 
843 	cc = (struct callout_cpu *)arg;
844 	CC_LOCK(cc);
845 	while ((c = TAILQ_FIRST(&cc->cc_expireq)) != NULL) {
846 		TAILQ_REMOVE(&cc->cc_expireq, c, c_links.tqe);
847 		softclock_call_cc(c, cc,
848 #ifdef CALLOUT_PROFILING
849 		    &mpcalls, &lockcalls, &gcalls,
850 #endif
851 		    0);
852 #ifdef CALLOUT_PROFILING
853 		++depth;
854 #endif
855 	}
856 #ifdef CALLOUT_PROFILING
857 	avg_depth += (depth * 1000 - avg_depth) >> 8;
858 	avg_mpcalls += (mpcalls * 1000 - avg_mpcalls) >> 8;
859 	avg_lockcalls += (lockcalls * 1000 - avg_lockcalls) >> 8;
860 	avg_gcalls += (gcalls * 1000 - avg_gcalls) >> 8;
861 #endif
862 	CC_UNLOCK(cc);
863 }
864 
865 /*
866  * timeout --
867  *	Execute a function after a specified length of time.
868  *
869  * untimeout --
870  *	Cancel previous timeout function call.
871  *
872  * callout_handle_init --
873  *	Initialize a handle so that using it with untimeout is benign.
874  *
875  *	See AT&T BCI Driver Reference Manual for specification.  This
876  *	implementation differs from that one in that although an
877  *	identification value is returned from timeout, the original
878  *	arguments to timeout as well as the identifier are used to
879  *	identify entries for untimeout.
880  */
881 struct callout_handle
882 timeout(timeout_t *ftn, void *arg, int to_ticks)
883 {
884 	struct callout_cpu *cc;
885 	struct callout *new;
886 	struct callout_handle handle;
887 
888 	cc = CC_CPU(timeout_cpu);
889 	CC_LOCK(cc);
890 	/* Fill in the next free callout structure. */
891 	new = SLIST_FIRST(&cc->cc_callfree);
892 	if (new == NULL)
893 		/* XXX Attempt to malloc first */
894 		panic("timeout table full");
895 	SLIST_REMOVE_HEAD(&cc->cc_callfree, c_links.sle);
896 	callout_reset(new, to_ticks, ftn, arg);
897 	handle.callout = new;
898 	CC_UNLOCK(cc);
899 
900 	return (handle);
901 }
902 
903 void
904 untimeout(timeout_t *ftn, void *arg, struct callout_handle handle)
905 {
906 	struct callout_cpu *cc;
907 
908 	/*
909 	 * Check for a handle that was initialized
910 	 * by callout_handle_init, but never used
911 	 * for a real timeout.
912 	 */
913 	if (handle.callout == NULL)
914 		return;
915 
916 	cc = callout_lock(handle.callout);
917 	if (handle.callout->c_func == ftn && handle.callout->c_arg == arg)
918 		callout_stop(handle.callout);
919 	CC_UNLOCK(cc);
920 }
921 
922 void
923 callout_handle_init(struct callout_handle *handle)
924 {
925 	handle->callout = NULL;
926 }
927 
928 /*
929  * New interface; clients allocate their own callout structures.
930  *
931  * callout_reset() - establish or change a timeout
932  * callout_stop() - disestablish a timeout
933  * callout_init() - initialize a callout structure so that it can
934  *	safely be passed to callout_reset() and callout_stop()
935  *
936  * <sys/callout.h> defines three convenience macros:
937  *
938  * callout_active() - returns truth if callout has not been stopped,
939  *	drained, or deactivated since the last time the callout was
940  *	reset.
941  * callout_pending() - returns truth if callout is still waiting for timeout
942  * callout_deactivate() - marks the callout as having been serviced
943  */
944 int
945 callout_reset_sbt_on(struct callout *c, sbintime_t sbt, sbintime_t precision,
946     void (*ftn)(void *), void *arg, int cpu, int flags)
947 {
948 	sbintime_t to_sbt, pr;
949 	struct callout_cpu *cc;
950 	int cancelled, direct;
951 
952 	cancelled = 0;
953 	if (flags & C_ABSOLUTE) {
954 		to_sbt = sbt;
955 	} else {
956 		if ((flags & C_HARDCLOCK) && (sbt < tick_sbt))
957 			sbt = tick_sbt;
958 		if ((flags & C_HARDCLOCK) ||
959 #ifdef NO_EVENTTIMERS
960 		    sbt >= sbt_timethreshold) {
961 			to_sbt = getsbinuptime();
962 
963 			/* Add safety belt for the case of hz > 1000. */
964 			to_sbt += tc_tick_sbt - tick_sbt;
965 #else
966 		    sbt >= sbt_tickthreshold) {
967 			/*
968 			 * Obtain the time of the last hardclock() call on
969 			 * this CPU directly from the kern_clocksource.c.
970 			 * This value is per-CPU, but it is equal for all
971 			 * active ones.
972 			 */
973 #ifdef __LP64__
974 			to_sbt = DPCPU_GET(hardclocktime);
975 #else
976 			spinlock_enter();
977 			to_sbt = DPCPU_GET(hardclocktime);
978 			spinlock_exit();
979 #endif
980 #endif
981 			if ((flags & C_HARDCLOCK) == 0)
982 				to_sbt += tick_sbt;
983 		} else
984 			to_sbt = sbinuptime();
985 		if (SBT_MAX - to_sbt < sbt)
986 			to_sbt = SBT_MAX;
987 		else
988 			to_sbt += sbt;
989 		pr = ((C_PRELGET(flags) < 0) ? sbt >> tc_precexp :
990 		    sbt >> C_PRELGET(flags));
991 		if (pr > precision)
992 			precision = pr;
993 	}
994 	/*
995 	 * Don't allow migration of pre-allocated callouts lest they
996 	 * become unbalanced.
997 	 */
998 	if (c->c_flags & CALLOUT_LOCAL_ALLOC)
999 		cpu = c->c_cpu;
1000 	direct = (c->c_flags & CALLOUT_DIRECT) != 0;
1001 	KASSERT(!direct || c->c_lock == NULL,
1002 	    ("%s: direct callout %p has lock", __func__, c));
1003 	cc = callout_lock(c);
1004 	if (cc->cc_exec_entity[direct].cc_curr == c) {
1005 		/*
1006 		 * We're being asked to reschedule a callout which is
1007 		 * currently in progress.  If there is a lock then we
1008 		 * can cancel the callout if it has not really started.
1009 		 */
1010 		if (c->c_lock != NULL && !cc->cc_exec_entity[direct].cc_cancel)
1011 			cancelled = cc->cc_exec_entity[direct].cc_cancel = true;
1012 		if (cc->cc_exec_entity[direct].cc_waiting) {
1013 			/*
1014 			 * Someone has called callout_drain to kill this
1015 			 * callout.  Don't reschedule.
1016 			 */
1017 			CTR4(KTR_CALLOUT, "%s %p func %p arg %p",
1018 			    cancelled ? "cancelled" : "failed to cancel",
1019 			    c, c->c_func, c->c_arg);
1020 			CC_UNLOCK(cc);
1021 			return (cancelled);
1022 		}
1023 	}
1024 	if (c->c_flags & CALLOUT_PENDING) {
1025 		if ((c->c_flags & CALLOUT_PROCESSED) == 0) {
1026 			if (cc->cc_exec_next_dir == c)
1027 				cc->cc_exec_next_dir = LIST_NEXT(c, c_links.le);
1028 			LIST_REMOVE(c, c_links.le);
1029 		} else
1030 			TAILQ_REMOVE(&cc->cc_expireq, c, c_links.tqe);
1031 		cancelled = 1;
1032 		c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING);
1033 	}
1034 
1035 #ifdef SMP
1036 	/*
1037 	 * If the callout must migrate try to perform it immediately.
1038 	 * If the callout is currently running, just defer the migration
1039 	 * to a more appropriate moment.
1040 	 */
1041 	if (c->c_cpu != cpu) {
1042 		if (cc->cc_exec_entity[direct].cc_curr == c) {
1043 			cc->cc_exec_entity[direct].ce_migration_cpu = cpu;
1044 			cc->cc_exec_entity[direct].ce_migration_time
1045 			    = to_sbt;
1046 			cc->cc_exec_entity[direct].ce_migration_prec
1047 			    = precision;
1048 			cc->cc_exec_entity[direct].ce_migration_func = ftn;
1049 			cc->cc_exec_entity[direct].ce_migration_arg = arg;
1050 			c->c_flags |= CALLOUT_DFRMIGRATION;
1051 			CTR6(KTR_CALLOUT,
1052 		    "migration of %p func %p arg %p in %d.%08x to %u deferred",
1053 			    c, c->c_func, c->c_arg, (int)(to_sbt >> 32),
1054 			    (u_int)(to_sbt & 0xffffffff), cpu);
1055 			CC_UNLOCK(cc);
1056 			return (cancelled);
1057 		}
1058 		cc = callout_cpu_switch(c, cc, cpu);
1059 	}
1060 #endif
1061 
1062 	callout_cc_add(c, cc, to_sbt, precision, ftn, arg, cpu, flags);
1063 	CTR6(KTR_CALLOUT, "%sscheduled %p func %p arg %p in %d.%08x",
1064 	    cancelled ? "re" : "", c, c->c_func, c->c_arg, (int)(to_sbt >> 32),
1065 	    (u_int)(to_sbt & 0xffffffff));
1066 	CC_UNLOCK(cc);
1067 
1068 	return (cancelled);
1069 }
1070 
1071 /*
1072  * Common idioms that can be optimized in the future.
1073  */
1074 int
1075 callout_schedule_on(struct callout *c, int to_ticks, int cpu)
1076 {
1077 	return callout_reset_on(c, to_ticks, c->c_func, c->c_arg, cpu);
1078 }
1079 
1080 int
1081 callout_schedule(struct callout *c, int to_ticks)
1082 {
1083 	return callout_reset_on(c, to_ticks, c->c_func, c->c_arg, c->c_cpu);
1084 }
1085 
1086 int
1087 _callout_stop_safe(struct callout *c, int safe)
1088 {
1089 	struct callout_cpu *cc, *old_cc;
1090 	struct lock_class *class;
1091 	int direct, sq_locked, use_lock;
1092 
1093 	/*
1094 	 * Some old subsystems don't hold Giant while running a callout_stop(),
1095 	 * so just discard this check for the moment.
1096 	 */
1097 	if (!safe && c->c_lock != NULL) {
1098 		if (c->c_lock == &Giant.lock_object)
1099 			use_lock = mtx_owned(&Giant);
1100 		else {
1101 			use_lock = 1;
1102 			class = LOCK_CLASS(c->c_lock);
1103 			class->lc_assert(c->c_lock, LA_XLOCKED);
1104 		}
1105 	} else
1106 		use_lock = 0;
1107 	direct = (c->c_flags & CALLOUT_DIRECT) != 0;
1108 	sq_locked = 0;
1109 	old_cc = NULL;
1110 again:
1111 	cc = callout_lock(c);
1112 
1113 	/*
1114 	 * If the callout was migrating while the callout cpu lock was
1115 	 * dropped,  just drop the sleepqueue lock and check the states
1116 	 * again.
1117 	 */
1118 	if (sq_locked != 0 && cc != old_cc) {
1119 #ifdef SMP
1120 		CC_UNLOCK(cc);
1121 		sleepq_release(&old_cc->cc_exec_entity[direct].cc_waiting);
1122 		sq_locked = 0;
1123 		old_cc = NULL;
1124 		goto again;
1125 #else
1126 		panic("migration should not happen");
1127 #endif
1128 	}
1129 
1130 	/*
1131 	 * If the callout isn't pending, it's not on the queue, so
1132 	 * don't attempt to remove it from the queue.  We can try to
1133 	 * stop it by other means however.
1134 	 */
1135 	if (!(c->c_flags & CALLOUT_PENDING)) {
1136 		c->c_flags &= ~CALLOUT_ACTIVE;
1137 
1138 		/*
1139 		 * If it wasn't on the queue and it isn't the current
1140 		 * callout, then we can't stop it, so just bail.
1141 		 */
1142 		if (cc->cc_exec_entity[direct].cc_curr != c) {
1143 			CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p",
1144 			    c, c->c_func, c->c_arg);
1145 			CC_UNLOCK(cc);
1146 			if (sq_locked)
1147 				sleepq_release(
1148 				    &cc->cc_exec_entity[direct].cc_waiting);
1149 			return (0);
1150 		}
1151 
1152 		if (safe) {
1153 			/*
1154 			 * The current callout is running (or just
1155 			 * about to run) and blocking is allowed, so
1156 			 * just wait for the current invocation to
1157 			 * finish.
1158 			 */
1159 			while (cc->cc_exec_entity[direct].cc_curr == c) {
1160 				/*
1161 				 * Use direct calls to sleepqueue interface
1162 				 * instead of cv/msleep in order to avoid
1163 				 * a LOR between cc_lock and sleepqueue
1164 				 * chain spinlocks.  This piece of code
1165 				 * emulates a msleep_spin() call actually.
1166 				 *
1167 				 * If we already have the sleepqueue chain
1168 				 * locked, then we can safely block.  If we
1169 				 * don't already have it locked, however,
1170 				 * we have to drop the cc_lock to lock
1171 				 * it.  This opens several races, so we
1172 				 * restart at the beginning once we have
1173 				 * both locks.  If nothing has changed, then
1174 				 * we will end up back here with sq_locked
1175 				 * set.
1176 				 */
1177 				if (!sq_locked) {
1178 					CC_UNLOCK(cc);
1179 					sleepq_lock(
1180 					&cc->cc_exec_entity[direct].cc_waiting);
1181 					sq_locked = 1;
1182 					old_cc = cc;
1183 					goto again;
1184 				}
1185 
1186 				/*
1187 				 * Migration could be cancelled here, but
1188 				 * as long as it is still not sure when it
1189 				 * will be packed up, just let softclock()
1190 				 * take care of it.
1191 				 */
1192 				cc->cc_exec_entity[direct].cc_waiting = true;
1193 				DROP_GIANT();
1194 				CC_UNLOCK(cc);
1195 				sleepq_add(
1196 				    &cc->cc_exec_entity[direct].cc_waiting,
1197 				    &cc->cc_lock.lock_object, "codrain",
1198 				    SLEEPQ_SLEEP, 0);
1199 				sleepq_wait(
1200 				    &cc->cc_exec_entity[direct].cc_waiting,
1201 					     0);
1202 				sq_locked = 0;
1203 				old_cc = NULL;
1204 
1205 				/* Reacquire locks previously released. */
1206 				PICKUP_GIANT();
1207 				CC_LOCK(cc);
1208 			}
1209 		} else if (use_lock &&
1210 			    !cc->cc_exec_entity[direct].cc_cancel) {
1211 			/*
1212 			 * The current callout is waiting for its
1213 			 * lock which we hold.  Cancel the callout
1214 			 * and return.  After our caller drops the
1215 			 * lock, the callout will be skipped in
1216 			 * softclock().
1217 			 */
1218 			cc->cc_exec_entity[direct].cc_cancel = true;
1219 			CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p",
1220 			    c, c->c_func, c->c_arg);
1221 			KASSERT(!cc_cce_migrating(cc, direct),
1222 			    ("callout wrongly scheduled for migration"));
1223 			CC_UNLOCK(cc);
1224 			KASSERT(!sq_locked, ("sleepqueue chain locked"));
1225 			return (1);
1226 		} else if ((c->c_flags & CALLOUT_DFRMIGRATION) != 0) {
1227 			c->c_flags &= ~CALLOUT_DFRMIGRATION;
1228 			CTR3(KTR_CALLOUT, "postponing stop %p func %p arg %p",
1229 			    c, c->c_func, c->c_arg);
1230 			CC_UNLOCK(cc);
1231 			return (1);
1232 		}
1233 		CTR3(KTR_CALLOUT, "failed to stop %p func %p arg %p",
1234 		    c, c->c_func, c->c_arg);
1235 		CC_UNLOCK(cc);
1236 		KASSERT(!sq_locked, ("sleepqueue chain still locked"));
1237 		return (0);
1238 	}
1239 	if (sq_locked)
1240 		sleepq_release(&cc->cc_exec_entity[direct].cc_waiting);
1241 
1242 	c->c_flags &= ~(CALLOUT_ACTIVE | CALLOUT_PENDING);
1243 
1244 	CTR3(KTR_CALLOUT, "cancelled %p func %p arg %p",
1245 	    c, c->c_func, c->c_arg);
1246 	if ((c->c_flags & CALLOUT_PROCESSED) == 0) {
1247 		if (cc->cc_exec_next_dir == c)
1248 			cc->cc_exec_next_dir = LIST_NEXT(c, c_links.le);
1249 		LIST_REMOVE(c, c_links.le);
1250 	} else
1251 		TAILQ_REMOVE(&cc->cc_expireq, c, c_links.tqe);
1252 	callout_cc_del(c, cc);
1253 
1254 	CC_UNLOCK(cc);
1255 	return (1);
1256 }
1257 
1258 void
1259 callout_init(struct callout *c, int mpsafe)
1260 {
1261 	bzero(c, sizeof *c);
1262 	if (mpsafe) {
1263 		c->c_lock = NULL;
1264 		c->c_flags = CALLOUT_RETURNUNLOCKED;
1265 	} else {
1266 		c->c_lock = &Giant.lock_object;
1267 		c->c_flags = 0;
1268 	}
1269 	c->c_cpu = timeout_cpu;
1270 }
1271 
1272 void
1273 _callout_init_lock(struct callout *c, struct lock_object *lock, int flags)
1274 {
1275 	bzero(c, sizeof *c);
1276 	c->c_lock = lock;
1277 	KASSERT((flags & ~(CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK)) == 0,
1278 	    ("callout_init_lock: bad flags %d", flags));
1279 	KASSERT(lock != NULL || (flags & CALLOUT_RETURNUNLOCKED) == 0,
1280 	    ("callout_init_lock: CALLOUT_RETURNUNLOCKED with no lock"));
1281 	KASSERT(lock == NULL || !(LOCK_CLASS(lock)->lc_flags &
1282 	    (LC_SPINLOCK | LC_SLEEPABLE)), ("%s: invalid lock class",
1283 	    __func__));
1284 	c->c_flags = flags & (CALLOUT_RETURNUNLOCKED | CALLOUT_SHAREDLOCK);
1285 	c->c_cpu = timeout_cpu;
1286 }
1287 
1288 #ifdef APM_FIXUP_CALLTODO
1289 /*
1290  * Adjust the kernel calltodo timeout list.  This routine is used after
1291  * an APM resume to recalculate the calltodo timer list values with the
1292  * number of hz's we have been sleeping.  The next hardclock() will detect
1293  * that there are fired timers and run softclock() to execute them.
1294  *
1295  * Please note, I have not done an exhaustive analysis of what code this
1296  * might break.  I am motivated to have my select()'s and alarm()'s that
1297  * have expired during suspend firing upon resume so that the applications
1298  * which set the timer can do the maintanence the timer was for as close
1299  * as possible to the originally intended time.  Testing this code for a
1300  * week showed that resuming from a suspend resulted in 22 to 25 timers
1301  * firing, which seemed independant on whether the suspend was 2 hours or
1302  * 2 days.  Your milage may vary.   - Ken Key <key@cs.utk.edu>
1303  */
1304 void
1305 adjust_timeout_calltodo(struct timeval *time_change)
1306 {
1307 	register struct callout *p;
1308 	unsigned long delta_ticks;
1309 
1310 	/*
1311 	 * How many ticks were we asleep?
1312 	 * (stolen from tvtohz()).
1313 	 */
1314 
1315 	/* Don't do anything */
1316 	if (time_change->tv_sec < 0)
1317 		return;
1318 	else if (time_change->tv_sec <= LONG_MAX / 1000000)
1319 		delta_ticks = (time_change->tv_sec * 1000000 +
1320 			       time_change->tv_usec + (tick - 1)) / tick + 1;
1321 	else if (time_change->tv_sec <= LONG_MAX / hz)
1322 		delta_ticks = time_change->tv_sec * hz +
1323 			      (time_change->tv_usec + (tick - 1)) / tick + 1;
1324 	else
1325 		delta_ticks = LONG_MAX;
1326 
1327 	if (delta_ticks > INT_MAX)
1328 		delta_ticks = INT_MAX;
1329 
1330 	/*
1331 	 * Now rip through the timer calltodo list looking for timers
1332 	 * to expire.
1333 	 */
1334 
1335 	/* don't collide with softclock() */
1336 	CC_LOCK(cc);
1337 	for (p = calltodo.c_next; p != NULL; p = p->c_next) {
1338 		p->c_time -= delta_ticks;
1339 
1340 		/* Break if the timer had more time on it than delta_ticks */
1341 		if (p->c_time > 0)
1342 			break;
1343 
1344 		/* take back the ticks the timer didn't use (p->c_time <= 0) */
1345 		delta_ticks = -p->c_time;
1346 	}
1347 	CC_UNLOCK(cc);
1348 
1349 	return;
1350 }
1351 #endif /* APM_FIXUP_CALLTODO */
1352 
1353 static int
1354 flssbt(sbintime_t sbt)
1355 {
1356 
1357 	sbt += (uint64_t)sbt >> 1;
1358 	if (sizeof(long) >= sizeof(sbintime_t))
1359 		return (flsl(sbt));
1360 	if (sbt >= SBT_1S)
1361 		return (flsl(((uint64_t)sbt) >> 32) + 32);
1362 	return (flsl(sbt));
1363 }
1364 
1365 /*
1366  * Dump immediate statistic snapshot of the scheduled callouts.
1367  */
1368 static int
1369 sysctl_kern_callout_stat(SYSCTL_HANDLER_ARGS)
1370 {
1371 	struct callout *tmp;
1372 	struct callout_cpu *cc;
1373 	struct callout_list *sc;
1374 	sbintime_t maxpr, maxt, medpr, medt, now, spr, st, t;
1375 	int ct[64], cpr[64], ccpbk[32];
1376 	int error, val, i, count, tcum, pcum, maxc, c, medc;
1377 #ifdef SMP
1378 	int cpu;
1379 #endif
1380 
1381 	val = 0;
1382 	error = sysctl_handle_int(oidp, &val, 0, req);
1383 	if (error != 0 || req->newptr == NULL)
1384 		return (error);
1385 	count = maxc = 0;
1386 	st = spr = maxt = maxpr = 0;
1387 	bzero(ccpbk, sizeof(ccpbk));
1388 	bzero(ct, sizeof(ct));
1389 	bzero(cpr, sizeof(cpr));
1390 	now = sbinuptime();
1391 #ifdef SMP
1392 	CPU_FOREACH(cpu) {
1393 		cc = CC_CPU(cpu);
1394 #else
1395 		cc = CC_CPU(timeout_cpu);
1396 #endif
1397 		CC_LOCK(cc);
1398 		for (i = 0; i < callwheelsize; i++) {
1399 			sc = &cc->cc_callwheel[i];
1400 			c = 0;
1401 			LIST_FOREACH(tmp, sc, c_links.le) {
1402 				c++;
1403 				t = tmp->c_time - now;
1404 				if (t < 0)
1405 					t = 0;
1406 				st += t / SBT_1US;
1407 				spr += tmp->c_precision / SBT_1US;
1408 				if (t > maxt)
1409 					maxt = t;
1410 				if (tmp->c_precision > maxpr)
1411 					maxpr = tmp->c_precision;
1412 				ct[flssbt(t)]++;
1413 				cpr[flssbt(tmp->c_precision)]++;
1414 			}
1415 			if (c > maxc)
1416 				maxc = c;
1417 			ccpbk[fls(c + c / 2)]++;
1418 			count += c;
1419 		}
1420 		CC_UNLOCK(cc);
1421 #ifdef SMP
1422 	}
1423 #endif
1424 
1425 	for (i = 0, tcum = 0; i < 64 && tcum < count / 2; i++)
1426 		tcum += ct[i];
1427 	medt = (i >= 2) ? (((sbintime_t)1) << (i - 2)) : 0;
1428 	for (i = 0, pcum = 0; i < 64 && pcum < count / 2; i++)
1429 		pcum += cpr[i];
1430 	medpr = (i >= 2) ? (((sbintime_t)1) << (i - 2)) : 0;
1431 	for (i = 0, c = 0; i < 32 && c < count / 2; i++)
1432 		c += ccpbk[i];
1433 	medc = (i >= 2) ? (1 << (i - 2)) : 0;
1434 
1435 	printf("Scheduled callouts statistic snapshot:\n");
1436 	printf("  Callouts: %6d  Buckets: %6d*%-3d  Bucket size: 0.%06ds\n",
1437 	    count, callwheelsize, mp_ncpus, 1000000 >> CC_HASH_SHIFT);
1438 	printf("  C/Bk: med %5d         avg %6d.%06jd  max %6d\n",
1439 	    medc,
1440 	    count / callwheelsize / mp_ncpus,
1441 	    (uint64_t)count * 1000000 / callwheelsize / mp_ncpus % 1000000,
1442 	    maxc);
1443 	printf("  Time: med %5jd.%06jds avg %6jd.%06jds max %6jd.%06jds\n",
1444 	    medt / SBT_1S, (medt & 0xffffffff) * 1000000 >> 32,
1445 	    (st / count) / 1000000, (st / count) % 1000000,
1446 	    maxt / SBT_1S, (maxt & 0xffffffff) * 1000000 >> 32);
1447 	printf("  Prec: med %5jd.%06jds avg %6jd.%06jds max %6jd.%06jds\n",
1448 	    medpr / SBT_1S, (medpr & 0xffffffff) * 1000000 >> 32,
1449 	    (spr / count) / 1000000, (spr / count) % 1000000,
1450 	    maxpr / SBT_1S, (maxpr & 0xffffffff) * 1000000 >> 32);
1451 	printf("  Distribution:       \tbuckets\t   time\t   tcum\t"
1452 	    "   prec\t   pcum\n");
1453 	for (i = 0, tcum = pcum = 0; i < 64; i++) {
1454 		if (ct[i] == 0 && cpr[i] == 0)
1455 			continue;
1456 		t = (i != 0) ? (((sbintime_t)1) << (i - 1)) : 0;
1457 		tcum += ct[i];
1458 		pcum += cpr[i];
1459 		printf("  %10jd.%06jds\t 2**%d\t%7d\t%7d\t%7d\t%7d\n",
1460 		    t / SBT_1S, (t & 0xffffffff) * 1000000 >> 32,
1461 		    i - 1 - (32 - CC_HASH_SHIFT),
1462 		    ct[i], tcum, cpr[i], pcum);
1463 	}
1464 	return (error);
1465 }
1466 SYSCTL_PROC(_kern, OID_AUTO, callout_stat,
1467     CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE,
1468     0, 0, sysctl_kern_callout_stat, "I",
1469     "Dump immediate statistic snapshot of the scheduled callouts");
1470