xref: /freebsd/share/man/man9/callout.9 (revision c697fb7f)
1.\"	$NetBSD: timeout.9,v 1.2 1996/06/23 22:32:34 pk Exp $
2.\"
3.\" Copyright (c) 1996 The NetBSD Foundation, Inc.
4.\" All rights reserved.
5.\"
6.\" This code is derived from software contributed to The NetBSD Foundation
7.\" by Paul Kranenburg.
8.\"
9.\" Redistribution and use in source and binary forms, with or without
10.\" modification, are permitted provided that the following conditions
11.\" are met:
12.\" 1. Redistributions of source code must retain the above copyright
13.\"    notice, this list of conditions and the following disclaimer.
14.\" 2. Redistributions in binary form must reproduce the above copyright
15.\"    notice, this list of conditions and the following disclaimer in the
16.\"    documentation and/or other materials provided with the distribution.
17.\"
18.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
19.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
20.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
22.\" LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28.\" POSSIBILITY OF SUCH DAMAGE.
29.\"
30.\" $FreeBSD$
31.\"
32.Dd December 13, 2019
33.Dt CALLOUT 9
34.Os
35.Sh NAME
36.Nm callout_active ,
37.Nm callout_deactivate ,
38.Nm callout_async_drain ,
39.Nm callout_drain ,
40.Nm callout_init ,
41.Nm callout_init_mtx ,
42.Nm callout_init_rm ,
43.Nm callout_init_rw ,
44.Nm callout_pending ,
45.Nm callout_reset ,
46.Nm callout_reset_curcpu ,
47.Nm callout_reset_on ,
48.Nm callout_reset_sbt ,
49.Nm callout_reset_sbt_curcpu ,
50.Nm callout_reset_sbt_on ,
51.Nm callout_schedule ,
52.Nm callout_schedule_curcpu ,
53.Nm callout_schedule_on ,
54.Nm callout_schedule_sbt ,
55.Nm callout_schedule_sbt_curcpu ,
56.Nm callout_schedule_sbt_on ,
57.Nm callout_stop ,
58.Nm callout_when
59.Nd execute a function after a specified length of time
60.Sh SYNOPSIS
61.In sys/types.h
62.In sys/callout.h
63.Bd -literal
64typedef void callout_func_t (void *);
65.Ed
66.Ft int
67.Fn callout_active "struct callout *c"
68.Ft void
69.Fn callout_deactivate "struct callout *c"
70.Ft int
71.Fn callout_async_drain "struct callout *c" "callout_func_t *drain"
72.Ft int
73.Fn callout_drain "struct callout *c"
74.Ft void
75.Fn callout_init "struct callout *c" "int mpsafe"
76.Ft void
77.Fn callout_init_mtx "struct callout *c" "struct mtx *mtx" "int flags"
78.Ft void
79.Fn callout_init_rm "struct callout *c" "struct rmlock *rm" "int flags"
80.Ft void
81.Fn callout_init_rw "struct callout *c" "struct rwlock *rw" "int flags"
82.Ft int
83.Fn callout_pending "struct callout *c"
84.Ft int
85.Fo callout_reset
86.Fa "struct callout *c"
87.Fa "int ticks"
88.Fa "callout_func_t *func"
89.Fa "void *arg"
90.Fc
91.Ft int
92.Fo callout_reset_curcpu
93.Fa "struct callout *c"
94.Fa "int ticks"
95.Fa "callout_func_t *func"
96.Fa "void *arg"
97.Fc
98.Ft int
99.Fo callout_reset_on
100.Fa "struct callout *c"
101.Fa "int ticks"
102.Fa "callout_func_t *func"
103.Fa "void *arg"
104.Fa "int cpu"
105.Fc
106.Ft int
107.Fo callout_reset_sbt
108.Fa "struct callout *c"
109.Fa "sbintime_t sbt"
110.Fa "sbintime_t pr"
111.Fa "callout_func_t *func"
112.Fa "void *arg"
113.Fa "int flags"
114.Fc
115.Ft int
116.Fo callout_reset_sbt_curcpu
117.Fa "struct callout *c"
118.Fa "sbintime_t sbt"
119.Fa "sbintime_t pr"
120.Fa "callout_func_t *func"
121.Fa "void *arg"
122.Fa "int flags"
123.Fc
124.Ft int
125.Fo callout_reset_sbt_on
126.Fa "struct callout *c"
127.Fa "sbintime_t sbt"
128.Fa "sbintime_t pr"
129.Fa "callout_func_t *func"
130.Fa "void *arg"
131.Fa "int cpu"
132.Fa "int flags"
133.Fc
134.Ft int
135.Fn callout_schedule "struct callout *c" "int ticks"
136.Ft int
137.Fn callout_schedule_curcpu "struct callout *c" "int ticks"
138.Ft int
139.Fn callout_schedule_on "struct callout *c" "int ticks" "int cpu"
140.Ft int
141.Fo callout_schedule_sbt
142.Fa "struct callout *c"
143.Fa "sbintime_t sbt"
144.Fa "sbintime_t pr"
145.Fa "int flags"
146.Fc
147.Ft int
148.Fo callout_schedule_sbt_curcpu
149.Fa "struct callout *c"
150.Fa "sbintime_t sbt"
151.Fa "sbintime_t pr"
152.Fa "int flags"
153.Fc
154.Ft int
155.Fo callout_schedule_sbt_on
156.Fa "struct callout *c"
157.Fa "sbintime_t sbt"
158.Fa "sbintime_t pr"
159.Fa "int cpu"
160.Fa "int flags"
161.Fc
162.Ft int
163.Fn callout_stop "struct callout *c"
164.Ft sbintime_t
165.Fo callout_when
166.Fa "sbintime_t sbt"
167.Fa "sbintime_t precision"
168.Fa "int flags"
169.Fa "sbintime_t *sbt_res"
170.Fa "sbintime_t *precision_res"
171.Fc
172.Sh DESCRIPTION
173The
174.Nm callout
175API is used to schedule a call to an arbitrary function at a specific
176time in the future.
177Consumers of this API are required to allocate a callout structure
178.Pq struct callout
179for each pending function invocation.
180This structure stores state about the pending function invocation including
181the function to be called and the time at which the function should be invoked.
182Pending function calls can be cancelled or rescheduled to a different time.
183In addition,
184a callout structure may be reused to schedule a new function call after a
185scheduled call is completed.
186.Pp
187Callouts only provide a single-shot mode.
188If a consumer requires a periodic timer,
189it must explicitly reschedule each function call.
190This is normally done by rescheduling the subsequent call within the called
191function.
192.Pp
193Callout functions must not sleep.
194They may not acquire sleepable locks,
195wait on condition variables,
196perform blocking allocation requests,
197or invoke any other action that might sleep.
198.Pp
199Each callout structure must be initialized by
200.Fn callout_init ,
201.Fn callout_init_mtx ,
202.Fn callout_init_rm ,
203or
204.Fn callout_init_rw
205before it is passed to any of the other callout functions.
206The
207.Fn callout_init
208function initializes a callout structure in
209.Fa c
210that is not associated with a specific lock.
211If the
212.Fa mpsafe
213argument is zero,
214the callout structure is not considered to be
215.Dq multi-processor safe ;
216and the Giant lock will be acquired before calling the callout function
217and released when the callout function returns.
218.Pp
219The
220.Fn callout_init_mtx ,
221.Fn callout_init_rm ,
222and
223.Fn callout_init_rw
224functions initialize a callout structure in
225.Fa c
226that is associated with a specific lock.
227The lock is specified by the
228.Fa mtx ,
229.Fa rm ,
230or
231.Fa rw
232parameter.
233The associated lock must be held while stopping or rescheduling the
234callout.
235The callout subsystem acquires the associated lock before calling the
236callout function and releases it after the function returns.
237If the callout was cancelled while the callout subsystem waited for the
238associated lock,
239the callout function is not called,
240and the associated lock is released.
241This ensures that stopping or rescheduling the callout will abort any
242previously scheduled invocation.
243.Pp
244Only regular mutexes may be used with
245.Fn callout_init_mtx ;
246spin mutexes are not supported.
247A sleepable read-mostly lock
248.Po
249one initialized with the
250.Dv RM_SLEEPABLE
251flag
252.Pc
253may not be used with
254.Fn callout_init_rm .
255Similarly, other sleepable lock types such as
256.Xr sx 9
257and
258.Xr lockmgr 9
259cannot be used with callouts because sleeping is not permitted in
260the callout subsystem.
261.Pp
262These
263.Fa flags
264may be specified for
265.Fn callout_init_mtx ,
266.Fn callout_init_rm ,
267or
268.Fn callout_init_rw :
269.Bl -tag -width ".Dv CALLOUT_RETURNUNLOCKED"
270.It Dv CALLOUT_RETURNUNLOCKED
271The callout function will release the associated lock itself,
272so the callout subsystem should not attempt to unlock it
273after the callout function returns.
274.It Dv CALLOUT_SHAREDLOCK
275The lock is only acquired in read mode when running the callout handler.
276This flag is ignored by
277.Fn callout_init_mtx .
278.El
279.Pp
280The function
281.Fn callout_stop
282cancels a callout
283.Fa c
284if it is currently pending.
285If the callout is pending and successfully stopped, then
286.Fn callout_stop
287returns a value of one.
288If the callout is not set, or
289has already been serviced, then
290negative one is returned.
291If the callout is currently being serviced and cannot be stopped,
292then zero will be returned.
293If the callout is currently being serviced and cannot be stopped, and at the
294same time a next invocation of the same callout is also scheduled, then
295.Fn callout_stop
296unschedules the next run and returns zero.
297If the callout has an associated lock,
298then that lock must be held when this function is called.
299.Pp
300The function
301.Fn callout_async_drain
302is identical to
303.Fn callout_stop
304with one difference.
305When
306.Fn callout_async_drain
307returns zero it will arrange for the function
308.Fa drain
309to be called using the same argument given to the
310.Fn callout_reset
311function.
312.Fn callout_async_drain
313If the callout has an associated lock,
314then that lock must be held when this function is called.
315Note that when stopping multiple callouts that use the same lock it is possible
316to get multiple return's of zero and multiple calls to the
317.Fa drain
318function, depending upon which CPU's the callouts are running.
319The
320.Fa drain
321function itself is called from the context of the completing callout
322i.e. softclock or hardclock, just like a callout itself.
323.Pp
324The function
325.Fn callout_drain
326is identical to
327.Fn callout_stop
328except that it will wait for the callout
329.Fa c
330to complete if it is already in progress.
331This function MUST NOT be called while holding any
332locks on which the callout might block, or deadlock will result.
333Note that if the callout subsystem has already begun processing this
334callout, then the callout function may be invoked before
335.Fn callout_drain
336returns.
337However, the callout subsystem does guarantee that the callout will be
338fully stopped before
339.Fn callout_drain
340returns.
341.Pp
342The
343.Fn callout_reset
344and
345.Fn callout_schedule
346function families schedule a future function invocation for callout
347.Fa c .
348If
349.Fa c
350already has a pending callout,
351it is cancelled before the new invocation is scheduled.
352These functions return a value of one if a pending callout was cancelled
353and zero if there was no pending callout.
354If the callout has an associated lock,
355then that lock must be held when any of these functions are called.
356.Pp
357The time at which the callout function will be invoked is determined by
358either the
359.Fa ticks
360argument or the
361.Fa sbt ,
362.Fa pr ,
363and
364.Fa flags
365arguments.
366When
367.Fa ticks
368is used,
369the callout is scheduled to execute after
370.Fa ticks Ns No /hz
371seconds.
372Non-positive values of
373.Fa ticks
374are silently converted to the value
375.Sq 1 .
376.Pp
377The
378.Fa sbt ,
379.Fa pr ,
380and
381.Fa flags
382arguments provide more control over the scheduled time including
383support for higher resolution times,
384specifying the precision of the scheduled time,
385and setting an absolute deadline instead of a relative timeout.
386The callout is scheduled to execute in a time window which begins at
387the time specified in
388.Fa sbt
389and extends for the amount of time specified in
390.Fa pr .
391If
392.Fa sbt
393specifies a time in the past,
394the window is adjusted to start at the current time.
395A non-zero value for
396.Fa pr
397allows the callout subsystem to coalesce callouts scheduled close to each
398other into fewer timer interrupts,
399reducing processing overhead and power consumption.
400These
401.Fa flags
402may be specified to adjust the interpretation of
403.Fa sbt
404and
405.Fa pr :
406.Bl -tag -width ".Dv C_DIRECT_EXEC"
407.It Dv C_ABSOLUTE
408Handle the
409.Fa sbt
410argument as an absolute time since boot.
411By default,
412.Fa sbt
413is treated as a relative amount of time,
414similar to
415.Fa ticks .
416.It Dv C_DIRECT_EXEC
417Run the handler directly from hardware interrupt context instead of from the
418softclock thread.
419This reduces latency and overhead, but puts more constraints on the callout
420function.
421Callout functions run in this context may use only spin mutexes for locking
422and should be as small as possible because they run with absolute priority.
423.It Fn C_PREL
424Specifies relative event time precision as binary logarithm of time interval
425divided by acceptable time deviation: 1 -- 1/2, 2 -- 1/4, etc.
426Note that the larger of
427.Fa pr
428or this value is used as the length of the time window.
429Smaller values
430.Pq which result in larger time intervals
431allow the callout subsystem to aggregate more events in one timer interrupt.
432.It Dv C_PRECALC
433The
434.Fa sbt
435argument specifies the absolute time at which the callout should be run,
436and the
437.Fa pr
438argument specifies the requested precision, which will not be
439adjusted during the scheduling process.
440The
441.Fa sbt
442and
443.Fa pr
444values should be calculated by an earlier call to
445.Fn callout_when
446which uses the user-supplied
447.Fa sbt ,
448.Fa pr ,
449and
450.Fa flags
451values.
452.It Dv C_HARDCLOCK
453Align the timeouts to
454.Fn hardclock
455calls if possible.
456.El
457.Pp
458The
459.Fn callout_reset
460functions accept a
461.Fa func
462argument which identifies the function to be called when the time expires.
463It must be a pointer to a function that takes a single
464.Fa void *
465argument.
466Upon invocation,
467.Fa func
468will receive
469.Fa arg
470as its only argument.
471The
472.Fn callout_schedule
473functions reuse the
474.Fa func
475and
476.Fa arg
477arguments from the previous callout.
478Note that one of the
479.Fn callout_reset
480functions must always be called to initialize
481.Fa func
482and
483.Fa arg
484before one of the
485.Fn callout_schedule
486functions can be used.
487.Pp
488The callout subsystem provides a softclock thread for each CPU in the system.
489Callouts are assigned to a single CPU and are executed by the softclock thread
490for that CPU.
491Initially,
492callouts are assigned to CPU 0.
493The
494.Fn callout_reset_on ,
495.Fn callout_reset_sbt_on ,
496.Fn callout_schedule_on
497and
498.Fn callout_schedule_sbt_on
499functions assign the callout to CPU
500.Fa cpu .
501The
502.Fn callout_reset_curcpu ,
503.Fn callout_reset_sbt_curpu ,
504.Fn callout_schedule_curcpu
505and
506.Fn callout_schedule_sbt_curcpu
507functions assign the callout to the current CPU.
508The
509.Fn callout_reset ,
510.Fn callout_reset_sbt ,
511.Fn callout_schedule
512and
513.Fn callout_schedule_sbt
514functions schedule the callout to execute in the softclock thread of the CPU
515to which it is currently assigned.
516.Pp
517Softclock threads are not pinned to their respective CPUs by default.
518The softclock thread for CPU 0 can be pinned to CPU 0 by setting the
519.Va kern.pin_default_swi
520loader tunable to a non-zero value.
521Softclock threads for CPUs other than zero can be pinned to their
522respective CPUs by setting the
523.Va kern.pin_pcpu_swi
524loader tunable to a non-zero value.
525.Pp
526The macros
527.Fn callout_pending ,
528.Fn callout_active
529and
530.Fn callout_deactivate
531provide access to the current state of the callout.
532The
533.Fn callout_pending
534macro checks whether a callout is
535.Em pending ;
536a callout is considered
537.Em pending
538when a timeout has been set but the time has not yet arrived.
539Note that once the timeout time arrives and the callout subsystem
540starts to process this callout,
541.Fn callout_pending
542will return
543.Dv FALSE
544even though the callout function may not have finished
545.Pq or even begun
546executing.
547The
548.Fn callout_active
549macro checks whether a callout is marked as
550.Em active ,
551and the
552.Fn callout_deactivate
553macro clears the callout's
554.Em active
555flag.
556The callout subsystem marks a callout as
557.Em active
558when a timeout is set and it clears the
559.Em active
560flag in
561.Fn callout_stop
562and
563.Fn callout_drain ,
564but it
565.Em does not
566clear it when a callout expires normally via the execution of the
567callout function.
568.Pp
569The
570.Fn callout_when
571function may be used to pre-calculate the absolute time at which the
572timeout should be run and the precision of the scheduled run time
573according to the required time
574.Fa sbt ,
575precision
576.Fa precision ,
577and additional adjustments requested by the
578.Fa flags
579argument.
580Flags accepted by the
581.Fn callout_when
582function are the same as flags for the
583.Fn callout_reset
584function.
585The resulting time is assigned to the variable pointed to by the
586.Fa sbt_res
587argument, and the resulting precision is assigned to
588.Fa *precision_res .
589When passing the results to
590.Fa callout_reset ,
591add the
592.Va C_PRECALC
593flag to
594.Fa flags ,
595to avoid incorrect re-adjustment.
596The function is intended for situations where precise time of the callout
597run should be known in advance, since
598trying to read this time from the callout structure itself after a
599.Fn callout_reset
600call is racy.
601.Ss "Avoiding Race Conditions"
602The callout subsystem invokes callout functions from its own thread
603context.
604Without some kind of synchronization,
605it is possible that a callout
606function will be invoked concurrently with an attempt to stop or reset
607the callout by another thread.
608In particular, since callout functions typically acquire a lock as
609their first action, the callout function may have already been invoked,
610but is blocked waiting for that lock at the time that another thread
611tries to reset or stop the callout.
612.Pp
613There are three main techniques for addressing these
614synchronization concerns.
615The first approach is preferred as it is the simplest:
616.Bl -enum -offset indent
617.It
618Callouts can be associated with a specific lock when they are initialized
619by
620.Fn callout_init_mtx ,
621.Fn callout_init_rm ,
622or
623.Fn callout_init_rw .
624When a callout is associated with a lock,
625the callout subsystem acquires the lock before the callout function is
626invoked.
627This allows the callout subsystem to transparently handle races between
628callout cancellation,
629scheduling,
630and execution.
631Note that the associated lock must be acquired before calling
632.Fn callout_stop
633or one of the
634.Fn callout_reset
635or
636.Fn callout_schedule
637functions to provide this safety.
638.Pp
639A callout initialized via
640.Fn callout_init
641with
642.Fa mpsafe
643set to zero is implicitly associated with the
644.Va Giant
645mutex.
646If
647.Va Giant
648is held when cancelling or rescheduling the callout,
649then its use will prevent races with the callout function.
650.It
651The return value from
652.Fn callout_stop
653.Po
654or the
655.Fn callout_reset
656and
657.Fn callout_schedule
658function families
659.Pc
660indicates whether or not the callout was removed.
661If it is known that the callout was set and the callout function has
662not yet executed, then a return value of
663.Dv FALSE
664indicates that the callout function is about to be called.
665For example:
666.Bd -literal -offset indent
667if (sc->sc_flags & SCFLG_CALLOUT_RUNNING) {
668	if (callout_stop(&sc->sc_callout)) {
669		sc->sc_flags &= ~SCFLG_CALLOUT_RUNNING;
670		/* successfully stopped */
671	} else {
672		/*
673		 * callout has expired and callout
674		 * function is about to be executed
675		 */
676	}
677}
678.Ed
679.It
680The
681.Fn callout_pending ,
682.Fn callout_active
683and
684.Fn callout_deactivate
685macros can be used together to work around the race conditions.
686When a callout's timeout is set, the callout subsystem marks the
687callout as both
688.Em active
689and
690.Em pending .
691When the timeout time arrives, the callout subsystem begins processing
692the callout by first clearing the
693.Em pending
694flag.
695It then invokes the callout function without changing the
696.Em active
697flag, and does not clear the
698.Em active
699flag even after the callout function returns.
700The mechanism described here requires the callout function itself to
701clear the
702.Em active
703flag using the
704.Fn callout_deactivate
705macro.
706The
707.Fn callout_stop
708and
709.Fn callout_drain
710functions always clear both the
711.Em active
712and
713.Em pending
714flags before returning.
715.Pp
716The callout function should first check the
717.Em pending
718flag and return without action if
719.Fn callout_pending
720returns
721.Dv TRUE .
722This indicates that the callout was rescheduled using
723.Fn callout_reset
724just before the callout function was invoked.
725If
726.Fn callout_active
727returns
728.Dv FALSE
729then the callout function should also return without action.
730This indicates that the callout has been stopped.
731Finally, the callout function should call
732.Fn callout_deactivate
733to clear the
734.Em active
735flag.
736For example:
737.Bd -literal -offset indent
738mtx_lock(&sc->sc_mtx);
739if (callout_pending(&sc->sc_callout)) {
740	/* callout was reset */
741	mtx_unlock(&sc->sc_mtx);
742	return;
743}
744if (!callout_active(&sc->sc_callout)) {
745	/* callout was stopped */
746	mtx_unlock(&sc->sc_mtx);
747	return;
748}
749callout_deactivate(&sc->sc_callout);
750/* rest of callout function */
751.Ed
752.Pp
753Together with appropriate synchronization, such as the mutex used above,
754this approach permits the
755.Fn callout_stop
756and
757.Fn callout_reset
758functions to be used at any time without races.
759For example:
760.Bd -literal -offset indent
761mtx_lock(&sc->sc_mtx);
762callout_stop(&sc->sc_callout);
763/* The callout is effectively stopped now. */
764.Ed
765.Pp
766If the callout is still pending then these functions operate normally,
767but if processing of the callout has already begun then the tests in
768the callout function cause it to return without further action.
769Synchronization between the callout function and other code ensures that
770stopping or resetting the callout will never be attempted while the
771callout function is past the
772.Fn callout_deactivate
773call.
774.Pp
775The above technique additionally ensures that the
776.Em active
777flag always reflects whether the callout is effectively enabled or
778disabled.
779If
780.Fn callout_active
781returns false, then the callout is effectively disabled, since even if
782the callout subsystem is actually just about to invoke the callout
783function, the callout function will return without action.
784.El
785.Pp
786There is one final race condition that must be considered when a
787callout is being stopped for the last time.
788In this case it may not be safe to let the callout function itself
789detect that the callout was stopped, since it may need to access
790data objects that have already been destroyed or recycled.
791To ensure that the callout is completely finished, a call to
792.Fn callout_drain
793should be used.
794In particular,
795a callout should always be drained prior to destroying its associated lock
796or releasing the storage for the callout structure.
797.Sh RETURN VALUES
798The
799.Fn callout_active
800macro returns the state of a callout's
801.Em active
802flag.
803.Pp
804The
805.Fn callout_pending
806macro returns the state of a callout's
807.Em pending
808flag.
809.Pp
810The
811.Fn callout_reset
812and
813.Fn callout_schedule
814function families return a value of one if the callout was pending before the new
815function invocation was scheduled.
816.Pp
817The
818.Fn callout_stop
819and
820.Fn callout_drain
821functions return a value of one if the callout was still pending when it was
822called, a zero if the callout could not be stopped and a negative one is it
823was either not running or has already completed.
824.Sh HISTORY
825.Fx
826initially used the long standing
827.Bx
828linked list
829callout mechanism which offered O(n) insertion and removal running time
830but did not generate or require handles for untimeout operations.
831.Pp
832.Fx 3.0
833introduced a new set of timeout and untimeout routines from
834.Nx
835based on the work of
836.An Adam M. Costello
837and
838.An George Varghese ,
839published in a technical report entitled
840.%T "Redesigning the BSD Callout and Timer Facilities"
841and modified for inclusion in
842.Fx
843by
844.An Justin T. Gibbs .
845The original work on the data structures used in that implementation
846was published by
847.An G. Varghese
848and
849.An A. Lauck
850in the paper
851.%T "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility"
852in the
853.%B "Proceedings of the 11th ACM Annual Symposium on Operating Systems Principles" .
854.Pp
855.Fx 3.3
856introduced the first implementations of
857.Fn callout_init ,
858.Fn callout_reset ,
859and
860.Fn callout_stop
861which permitted callers to allocate dedicated storage for callouts.
862This ensured that a callout would always fire unlike
863.Fn timeout
864which would silently fail if it was unable to allocate a callout.
865.Pp
866.Fx 5.0
867permitted callout handlers to be tagged as MPSAFE via
868.Fn callout_init .
869.Pp
870.Fx 5.3
871introduced
872.Fn callout_drain .
873.Pp
874.Fx 6.0
875introduced
876.Fn callout_init_mtx .
877.Pp
878.Fx 8.0
879introduced per-CPU callout wheels,
880.Fn callout_init_rw ,
881and
882.Fn callout_schedule .
883.Pp
884.Fx 9.0
885changed the underlying timer interrupts used to drive callouts to prefer
886one-shot event timers instead of a periodic timer interrupt.
887.Pp
888.Fx 10.0
889switched the callout wheel to support tickless operation.
890These changes introduced
891.Vt sbintime_t
892and the
893.Fn callout_reset_sbt*
894family of functions.
895.Fx 10.0 also added
896.Dv C_DIRECT_EXEC
897and
898.Fn callout_init_rm .
899.Pp
900.Fx 10.2
901introduced the
902.Fn callout_schedule_sbt*
903family of functions.
904.Pp
905.Fx 11.0
906introduced
907.Fn callout_async_drain .
908.Fx 11.1
909introduced
910.Fn callout_when .
911.Fx 13.0
912removed
913.Vt timeout_t ,
914.Fn timeout ,
915and
916.Fn untimeout .
917