xref: /freebsd/share/man/man9/callout.9 (revision efe014e6b177ba1b0d70f7df751f5066d4eafe9b)
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 September 1, 2021
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
244A sleepable read-mostly lock
245.Po
246one initialized with the
247.Dv RM_SLEEPABLE
248flag
249.Pc
250may not be used with
251.Fn callout_init_rm .
252Similarly, other sleepable lock types such as
253.Xr sx 9
254and
255.Xr lockmgr 9
256cannot be used with callouts because sleeping is not permitted in
257the callout subsystem.
258.Pp
259These
260.Fa flags
261may be specified for
262.Fn callout_init_mtx ,
263.Fn callout_init_rm ,
264or
265.Fn callout_init_rw :
266.Bl -tag -width ".Dv CALLOUT_RETURNUNLOCKED"
267.It Dv CALLOUT_RETURNUNLOCKED
268The callout function will release the associated lock itself,
269so the callout subsystem should not attempt to unlock it
270after the callout function returns.
271.It Dv CALLOUT_SHAREDLOCK
272The lock is only acquired in read mode when running the callout handler.
273This flag is ignored by
274.Fn callout_init_mtx .
275.El
276.Pp
277The function
278.Fn callout_stop
279cancels a callout
280.Fa c
281if it is currently pending.
282If the callout is pending and successfully stopped, then
283.Fn callout_stop
284returns a value of one.
285If the callout is not set, or
286has already been serviced, then
287negative one is returned.
288If the callout is currently being serviced and cannot be stopped,
289then zero will be returned.
290If the callout is currently being serviced and cannot be stopped, and at the
291same time a next invocation of the same callout is also scheduled, then
292.Fn callout_stop
293unschedules the next run and returns zero.
294If the callout has an associated lock,
295then that lock must be held when this function is called.
296.Pp
297The function
298.Fn callout_async_drain
299is identical to
300.Fn callout_stop
301with one difference.
302When
303.Fn callout_async_drain
304returns zero it will arrange for the function
305.Fa drain
306to be called using the same argument given to the
307.Fn callout_reset
308function.
309.Fn callout_async_drain
310If the callout has an associated lock,
311then that lock must be held when this function is called.
312Note that when stopping multiple callouts that use the same lock it is possible
313to get multiple return's of zero and multiple calls to the
314.Fa drain
315function, depending upon which CPU's the callouts are running.
316The
317.Fa drain
318function itself is called from the context of the completing callout
319i.e. softclock or hardclock, just like a callout itself.
320.Pp
321The function
322.Fn callout_drain
323is identical to
324.Fn callout_stop
325except that it will wait for the callout
326.Fa c
327to complete if it is already in progress.
328This function MUST NOT be called while holding any
329locks on which the callout might block, or deadlock will result.
330Note that if the callout subsystem has already begun processing this
331callout, then the callout function may be invoked before
332.Fn callout_drain
333returns.
334However, the callout subsystem does guarantee that the callout will be
335fully stopped before
336.Fn callout_drain
337returns.
338.Pp
339The
340.Fn callout_reset
341and
342.Fn callout_schedule
343function families schedule a future function invocation for callout
344.Fa c .
345If
346.Fa c
347already has a pending callout,
348it is cancelled before the new invocation is scheduled.
349These functions return a value of one if a pending callout was cancelled
350and zero if there was no pending callout.
351If the callout has an associated lock,
352then that lock must be held when any of these functions are called.
353.Pp
354The time at which the callout function will be invoked is determined by
355either the
356.Fa ticks
357argument or the
358.Fa sbt ,
359.Fa pr ,
360and
361.Fa flags
362arguments.
363When
364.Fa ticks
365is used,
366the callout is scheduled to execute after
367.Fa ticks Ns No /hz
368seconds.
369Non-positive values of
370.Fa ticks
371are silently converted to the value
372.Sq 1 .
373.Pp
374The
375.Fa sbt ,
376.Fa pr ,
377and
378.Fa flags
379arguments provide more control over the scheduled time including
380support for higher resolution times,
381specifying the precision of the scheduled time,
382and setting an absolute deadline instead of a relative timeout.
383The callout is scheduled to execute in a time window which begins at
384the time specified in
385.Fa sbt
386and extends for the amount of time specified in
387.Fa pr .
388If
389.Fa sbt
390specifies a time in the past,
391the window is adjusted to start at the current time.
392A non-zero value for
393.Fa pr
394allows the callout subsystem to coalesce callouts scheduled close to each
395other into fewer timer interrupts,
396reducing processing overhead and power consumption.
397These
398.Fa flags
399may be specified to adjust the interpretation of
400.Fa sbt
401and
402.Fa pr :
403.Bl -tag -width ".Dv C_DIRECT_EXEC"
404.It Dv C_ABSOLUTE
405Handle the
406.Fa sbt
407argument as an absolute time since boot.
408By default,
409.Fa sbt
410is treated as a relative amount of time,
411similar to
412.Fa ticks .
413.It Dv C_DIRECT_EXEC
414Run the handler directly from hardware interrupt context instead of from the
415softclock thread.
416This reduces latency and overhead, but puts more constraints on the callout
417function.
418Callout functions run in this context may use only spin mutexes for locking
419and should be as small as possible because they run with absolute priority.
420.It Fn C_PREL
421Specifies relative event time precision as binary logarithm of time interval
422divided by acceptable time deviation: 1 -- 1/2, 2 -- 1/4, etc.
423Note that the larger of
424.Fa pr
425or this value is used as the length of the time window.
426Smaller values
427.Pq which result in larger time intervals
428allow the callout subsystem to aggregate more events in one timer interrupt.
429.It Dv C_PRECALC
430The
431.Fa sbt
432argument specifies the absolute time at which the callout should be run,
433and the
434.Fa pr
435argument specifies the requested precision, which will not be
436adjusted during the scheduling process.
437The
438.Fa sbt
439and
440.Fa pr
441values should be calculated by an earlier call to
442.Fn callout_when
443which uses the user-supplied
444.Fa sbt ,
445.Fa pr ,
446and
447.Fa flags
448values.
449.It Dv C_HARDCLOCK
450Align the timeouts to
451.Fn hardclock
452calls if possible.
453.El
454.Pp
455The
456.Fn callout_reset
457functions accept a
458.Fa func
459argument which identifies the function to be called when the time expires.
460It must be a pointer to a function that takes a single
461.Fa void *
462argument.
463Upon invocation,
464.Fa func
465will receive
466.Fa arg
467as its only argument.
468The
469.Fn callout_schedule
470functions reuse the
471.Fa func
472and
473.Fa arg
474arguments from the previous callout.
475Note that one of the
476.Fn callout_reset
477functions must always be called to initialize
478.Fa func
479and
480.Fa arg
481before one of the
482.Fn callout_schedule
483functions can be used.
484.Pp
485The callout subsystem provides a softclock thread for each CPU in the system.
486Callouts are assigned to a single CPU and are executed by the softclock thread
487for that CPU.
488Initially,
489callouts are assigned to CPU 0.
490The
491.Fn callout_reset_on ,
492.Fn callout_reset_sbt_on ,
493.Fn callout_schedule_on
494and
495.Fn callout_schedule_sbt_on
496functions assign the callout to CPU
497.Fa cpu .
498The
499.Fn callout_reset_curcpu ,
500.Fn callout_reset_sbt_curpu ,
501.Fn callout_schedule_curcpu
502and
503.Fn callout_schedule_sbt_curcpu
504functions assign the callout to the current CPU.
505The
506.Fn callout_reset ,
507.Fn callout_reset_sbt ,
508.Fn callout_schedule
509and
510.Fn callout_schedule_sbt
511functions schedule the callout to execute in the softclock thread of the CPU
512to which it is currently assigned.
513.Pp
514Softclock threads are not pinned to their respective CPUs by default.
515The softclock thread for CPU 0 can be pinned to CPU 0 by setting the
516.Va kern.pin_default_swi
517loader tunable to a non-zero value.
518Softclock threads for CPUs other than zero can be pinned to their
519respective CPUs by setting the
520.Va kern.pin_pcpu_swi
521loader tunable to a non-zero value.
522.Pp
523The macros
524.Fn callout_pending ,
525.Fn callout_active
526and
527.Fn callout_deactivate
528provide access to the current state of the callout.
529The
530.Fn callout_pending
531macro checks whether a callout is
532.Em pending ;
533a callout is considered
534.Em pending
535when a timeout has been set but the time has not yet arrived.
536Note that once the timeout time arrives and the callout subsystem
537starts to process this callout,
538.Fn callout_pending
539will return
540.Dv FALSE
541even though the callout function may not have finished
542.Pq or even begun
543executing.
544The
545.Fn callout_active
546macro checks whether a callout is marked as
547.Em active ,
548and the
549.Fn callout_deactivate
550macro clears the callout's
551.Em active
552flag.
553The callout subsystem marks a callout as
554.Em active
555when a timeout is set and it clears the
556.Em active
557flag in
558.Fn callout_stop
559and
560.Fn callout_drain ,
561but it
562.Em does not
563clear it when a callout expires normally via the execution of the
564callout function.
565.Pp
566The
567.Fn callout_when
568function may be used to pre-calculate the absolute time at which the
569timeout should be run and the precision of the scheduled run time
570according to the required time
571.Fa sbt ,
572precision
573.Fa precision ,
574and additional adjustments requested by the
575.Fa flags
576argument.
577Flags accepted by the
578.Fn callout_when
579function are the same as flags for the
580.Fn callout_reset
581function.
582The resulting time is assigned to the variable pointed to by the
583.Fa sbt_res
584argument, and the resulting precision is assigned to
585.Fa *precision_res .
586When passing the results to
587.Fa callout_reset ,
588add the
589.Va C_PRECALC
590flag to
591.Fa flags ,
592to avoid incorrect re-adjustment.
593The function is intended for situations where precise time of the callout
594run should be known in advance, since
595trying to read this time from the callout structure itself after a
596.Fn callout_reset
597call is racy.
598.Ss "Avoiding Race Conditions"
599The callout subsystem invokes callout functions from its own thread
600context.
601Without some kind of synchronization,
602it is possible that a callout
603function will be invoked concurrently with an attempt to stop or reset
604the callout by another thread.
605In particular, since callout functions typically acquire a lock as
606their first action, the callout function may have already been invoked,
607but is blocked waiting for that lock at the time that another thread
608tries to reset or stop the callout.
609.Pp
610There are three main techniques for addressing these
611synchronization concerns.
612The first approach is preferred as it is the simplest:
613.Bl -enum -offset indent
614.It
615Callouts can be associated with a specific lock when they are initialized
616by
617.Fn callout_init_mtx ,
618.Fn callout_init_rm ,
619or
620.Fn callout_init_rw .
621When a callout is associated with a lock,
622the callout subsystem acquires the lock before the callout function is
623invoked.
624This allows the callout subsystem to transparently handle races between
625callout cancellation,
626scheduling,
627and execution.
628Note that the associated lock must be acquired before calling
629.Fn callout_stop
630or one of the
631.Fn callout_reset
632or
633.Fn callout_schedule
634functions to provide this safety.
635.Pp
636A callout initialized via
637.Fn callout_init
638with
639.Fa mpsafe
640set to zero is implicitly associated with the
641.Va Giant
642mutex.
643If
644.Va Giant
645is held when cancelling or rescheduling the callout,
646then its use will prevent races with the callout function.
647.It
648The return value from
649.Fn callout_stop
650.Po
651or the
652.Fn callout_reset
653and
654.Fn callout_schedule
655function families
656.Pc
657indicates whether or not the callout was removed.
658If it is known that the callout was set and the callout function has
659not yet executed, then a return value of
660.Dv FALSE
661indicates that the callout function is about to be called.
662For example:
663.Bd -literal -offset indent
664if (sc->sc_flags & SCFLG_CALLOUT_RUNNING) {
665	if (callout_stop(&sc->sc_callout)) {
666		sc->sc_flags &= ~SCFLG_CALLOUT_RUNNING;
667		/* successfully stopped */
668	} else {
669		/*
670		 * callout has expired and callout
671		 * function is about to be executed
672		 */
673	}
674}
675.Ed
676.It
677The
678.Fn callout_pending ,
679.Fn callout_active
680and
681.Fn callout_deactivate
682macros can be used together to work around the race conditions.
683When a callout's timeout is set, the callout subsystem marks the
684callout as both
685.Em active
686and
687.Em pending .
688When the timeout time arrives, the callout subsystem begins processing
689the callout by first clearing the
690.Em pending
691flag.
692It then invokes the callout function without changing the
693.Em active
694flag, and does not clear the
695.Em active
696flag even after the callout function returns.
697The mechanism described here requires the callout function itself to
698clear the
699.Em active
700flag using the
701.Fn callout_deactivate
702macro.
703The
704.Fn callout_stop
705and
706.Fn callout_drain
707functions always clear both the
708.Em active
709and
710.Em pending
711flags before returning.
712.Pp
713The callout function should first check the
714.Em pending
715flag and return without action if
716.Fn callout_pending
717returns
718.Dv TRUE .
719This indicates that the callout was rescheduled using
720.Fn callout_reset
721just before the callout function was invoked.
722If
723.Fn callout_active
724returns
725.Dv FALSE
726then the callout function should also return without action.
727This indicates that the callout has been stopped.
728Finally, the callout function should call
729.Fn callout_deactivate
730to clear the
731.Em active
732flag.
733For example:
734.Bd -literal -offset indent
735mtx_lock(&sc->sc_mtx);
736if (callout_pending(&sc->sc_callout)) {
737	/* callout was reset */
738	mtx_unlock(&sc->sc_mtx);
739	return;
740}
741if (!callout_active(&sc->sc_callout)) {
742	/* callout was stopped */
743	mtx_unlock(&sc->sc_mtx);
744	return;
745}
746callout_deactivate(&sc->sc_callout);
747/* rest of callout function */
748.Ed
749.Pp
750Together with appropriate synchronization, such as the mutex used above,
751this approach permits the
752.Fn callout_stop
753and
754.Fn callout_reset
755functions to be used at any time without races.
756For example:
757.Bd -literal -offset indent
758mtx_lock(&sc->sc_mtx);
759callout_stop(&sc->sc_callout);
760/* The callout is effectively stopped now. */
761.Ed
762.Pp
763If the callout is still pending then these functions operate normally,
764but if processing of the callout has already begun then the tests in
765the callout function cause it to return without further action.
766Synchronization between the callout function and other code ensures that
767stopping or resetting the callout will never be attempted while the
768callout function is past the
769.Fn callout_deactivate
770call.
771.Pp
772The above technique additionally ensures that the
773.Em active
774flag always reflects whether the callout is effectively enabled or
775disabled.
776If
777.Fn callout_active
778returns false, then the callout is effectively disabled, since even if
779the callout subsystem is actually just about to invoke the callout
780function, the callout function will return without action.
781.El
782.Pp
783There is one final race condition that must be considered when a
784callout is being stopped for the last time.
785In this case it may not be safe to let the callout function itself
786detect that the callout was stopped, since it may need to access
787data objects that have already been destroyed or recycled.
788To ensure that the callout is completely finished, a call to
789.Fn callout_drain
790should be used.
791In particular,
792a callout should always be drained prior to destroying its associated lock
793or releasing the storage for the callout structure.
794.Sh RETURN VALUES
795The
796.Fn callout_active
797macro returns the state of a callout's
798.Em active
799flag.
800.Pp
801The
802.Fn callout_pending
803macro returns the state of a callout's
804.Em pending
805flag.
806.Pp
807The
808.Fn callout_reset
809and
810.Fn callout_schedule
811function families return a value of one if the callout was pending before the new
812function invocation was scheduled.
813.Pp
814The
815.Fn callout_stop
816and
817.Fn callout_drain
818functions return a value of one if the callout was still pending when it was
819called, a zero if the callout could not be stopped and a negative one is it
820was either not running or has already completed.
821.Sh HISTORY
822.Fx
823initially used the long standing
824.Bx
825linked list
826callout mechanism which offered O(n) insertion and removal running time
827but did not generate or require handles for untimeout operations.
828.Pp
829.Fx 3.0
830introduced a new set of timeout and untimeout routines from
831.Nx
832based on the work of
833.An Adam M. Costello
834and
835.An George Varghese ,
836published in a technical report entitled
837.%T "Redesigning the BSD Callout and Timer Facilities"
838and modified for inclusion in
839.Fx
840by
841.An Justin T. Gibbs .
842The original work on the data structures used in that implementation
843was published by
844.An G. Varghese
845and
846.An A. Lauck
847in the paper
848.%T "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility"
849in the
850.%B "Proceedings of the 11th ACM Annual Symposium on Operating Systems Principles" .
851.Pp
852.Fx 3.3
853introduced the first implementations of
854.Fn callout_init ,
855.Fn callout_reset ,
856and
857.Fn callout_stop
858which permitted callers to allocate dedicated storage for callouts.
859This ensured that a callout would always fire unlike
860.Fn timeout
861which would silently fail if it was unable to allocate a callout.
862.Pp
863.Fx 5.0
864permitted callout handlers to be tagged as MPSAFE via
865.Fn callout_init .
866.Pp
867.Fx 5.3
868introduced
869.Fn callout_drain .
870.Pp
871.Fx 6.0
872introduced
873.Fn callout_init_mtx .
874.Pp
875.Fx 8.0
876introduced per-CPU callout wheels,
877.Fn callout_init_rw ,
878and
879.Fn callout_schedule .
880.Pp
881.Fx 9.0
882changed the underlying timer interrupts used to drive callouts to prefer
883one-shot event timers instead of a periodic timer interrupt.
884.Pp
885.Fx 10.0
886switched the callout wheel to support tickless operation.
887These changes introduced
888.Vt sbintime_t
889and the
890.Fn callout_reset_sbt*
891family of functions.
892.Fx 10.0 also added
893.Dv C_DIRECT_EXEC
894and
895.Fn callout_init_rm .
896.Pp
897.Fx 10.2
898introduced the
899.Fn callout_schedule_sbt*
900family of functions.
901.Pp
902.Fx 11.0
903introduced
904.Fn callout_async_drain .
905.Fx 11.1
906introduced
907.Fn callout_when .
908.Fx 13.0
909removed
910.Vt timeout_t ,
911.Fn timeout ,
912and
913.Fn untimeout .
914