1 .\" $NetBSD: timeout.9,v 1.2 1996/06/23 22:32:34 pk Exp $
3 .\" Copyright (c) 1996 The NetBSD Foundation, Inc.
4 .\" All rights reserved.
6 .\" This code is derived from software contributed to The NetBSD Foundation
7 .\" by Paul Kranenburg.
9 .\" Redistribution and use in source and binary forms, with or without
10 .\" modification, are permitted provided that the following conditions
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.
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.
37 .Nm callout_deactivate ,
38 .Nm callout_async_drain ,
41 .Nm callout_init_mtx ,
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 ,
59 .Nd execute a function after a specified length of time
64 typedef void callout_func_t (void *);
67 .Fn callout_active "struct callout *c"
69 .Fn callout_deactivate "struct callout *c"
71 .Fn callout_async_drain "struct callout *c" "callout_func_t *drain"
73 .Fn callout_drain "struct callout *c"
75 .Fn callout_init "struct callout *c" "int mpsafe"
77 .Fn callout_init_mtx "struct callout *c" "struct mtx *mtx" "int flags"
79 .Fn callout_init_rm "struct callout *c" "struct rmlock *rm" "int flags"
81 .Fn callout_init_rw "struct callout *c" "struct rwlock *rw" "int flags"
83 .Fn callout_pending "struct callout *c"
86 .Fa "struct callout *c"
88 .Fa "callout_func_t *func"
92 .Fo callout_reset_curcpu
93 .Fa "struct callout *c"
95 .Fa "callout_func_t *func"
100 .Fa "struct callout *c"
102 .Fa "callout_func_t *func"
107 .Fo callout_reset_sbt
108 .Fa "struct callout *c"
111 .Fa "callout_func_t *func"
116 .Fo callout_reset_sbt_curcpu
117 .Fa "struct callout *c"
120 .Fa "callout_func_t *func"
125 .Fo callout_reset_sbt_on
126 .Fa "struct callout *c"
129 .Fa "callout_func_t *func"
135 .Fn callout_schedule "struct callout *c" "int ticks"
137 .Fn callout_schedule_curcpu "struct callout *c" "int ticks"
139 .Fn callout_schedule_on "struct callout *c" "int ticks" "int cpu"
141 .Fo callout_schedule_sbt
142 .Fa "struct callout *c"
148 .Fo callout_schedule_sbt_curcpu
149 .Fa "struct callout *c"
155 .Fo callout_schedule_sbt_on
156 .Fa "struct callout *c"
163 .Fn callout_stop "struct callout *c"
167 .Fa "sbintime_t precision"
169 .Fa "sbintime_t *sbt_res"
170 .Fa "sbintime_t *precision_res"
175 API is used to schedule a call to an arbitrary function at a specific
177 Consumers of this API are required to allocate a callout structure
179 for each pending function invocation.
180 This structure stores state about the pending function invocation including
181 the function to be called and the time at which the function should be invoked.
182 Pending function calls can be cancelled or rescheduled to a different time.
184 a callout structure may be reused to schedule a new function call after a
185 scheduled call is completed.
187 Callouts only provide a single-shot mode.
188 If a consumer requires a periodic timer,
189 it must explicitly reschedule each function call.
190 This is normally done by rescheduling the subsequent call within the called
193 Callout functions must not sleep.
194 They may not acquire sleepable locks,
195 wait on condition variables,
196 perform blocking allocation requests,
197 or invoke any other action that might sleep.
199 Each callout structure must be initialized by
201 .Fn callout_init_mtx ,
202 .Fn callout_init_rm ,
205 before it is passed to any of the other callout functions.
208 function initializes a callout structure in
210 that is not associated with a specific lock.
214 the callout structure is not considered to be
215 .Dq multi-processor safe ;
216 and the Giant lock will be acquired before calling the callout function
217 and released when the callout function returns.
220 .Fn callout_init_mtx ,
221 .Fn callout_init_rm ,
224 functions initialize a callout structure in
226 that is associated with a specific lock.
227 The lock is specified by the
233 The associated lock must be held while stopping or rescheduling the
235 The callout subsystem acquires the associated lock before calling the
236 callout function and releases it after the function returns.
237 If the callout was cancelled while the callout subsystem waited for the
239 the callout function is not called,
240 and the associated lock is released.
241 This ensures that stopping or rescheduling the callout will abort any
242 previously scheduled invocation.
244 Only regular mutexes may be used with
245 .Fn callout_init_mtx ;
246 spin mutexes are not supported.
247 A sleepable read-mostly lock
249 one initialized with the
254 .Fn callout_init_rm .
255 Similarly, other sleepable lock types such as
259 cannot be used with callouts because sleeping is not permitted in
260 the callout subsystem.
265 .Fn callout_init_mtx ,
266 .Fn callout_init_rm ,
268 .Fn callout_init_rw :
269 .Bl -tag -width ".Dv CALLOUT_RETURNUNLOCKED"
270 .It Dv CALLOUT_RETURNUNLOCKED
271 The callout function will release the associated lock itself,
272 so the callout subsystem should not attempt to unlock it
273 after the callout function returns.
274 .It Dv CALLOUT_SHAREDLOCK
275 The lock is only acquired in read mode when running the callout handler.
276 This flag is ignored by
277 .Fn callout_init_mtx .
284 if it is currently pending.
285 If the callout is pending and successfully stopped, then
287 returns a value of one.
288 If the callout is not set, or
289 has already been serviced, then
290 negative one is returned.
291 If the callout is currently being serviced and cannot be stopped,
292 then zero will be returned.
293 If the callout is currently being serviced and cannot be stopped, and at the
294 same time a next invocation of the same callout is also scheduled, then
296 unschedules the next run and returns zero.
297 If the callout has an associated lock,
298 then that lock must be held when this function is called.
301 .Fn callout_async_drain
306 .Fn callout_async_drain
307 returns zero it will arrange for the function
309 to be called using the same argument given to the
312 .Fn callout_async_drain
313 If the callout has an associated lock,
314 then that lock must be held when this function is called.
315 Note that when stopping multiple callouts that use the same lock it is possible
316 to get multiple return's of zero and multiple calls to the
318 function, depending upon which CPU's the callouts are running.
321 function itself is called from the context of the completing callout
322 i.e. softclock or hardclock, just like a callout itself.
328 except that it will wait for the callout
330 to complete if it is already in progress.
331 This function MUST NOT be called while holding any
332 locks on which the callout might block, or deadlock will result.
333 Note that if the callout subsystem has already begun processing this
334 callout, then the callout function may be invoked before
337 However, the callout subsystem does guarantee that the callout will be
346 function families schedule a future function invocation for callout
350 already has a pending callout,
351 it is cancelled before the new invocation is scheduled.
352 These functions return a value of one if a pending callout was cancelled
353 and zero if there was no pending callout.
354 If the callout has an associated lock,
355 then that lock must be held when any of these functions are called.
357 The time at which the callout function will be invoked is determined by
369 the callout is scheduled to execute after
372 Non-positive values of
374 are silently converted to the value
382 arguments provide more control over the scheduled time including
383 support for higher resolution times,
384 specifying the precision of the scheduled time,
385 and setting an absolute deadline instead of a relative timeout.
386 The callout is scheduled to execute in a time window which begins at
387 the time specified in
389 and extends for the amount of time specified in
393 specifies a time in the past,
394 the window is adjusted to start at the current time.
397 allows the callout subsystem to coalesce callouts scheduled close to each
398 other into fewer timer interrupts,
399 reducing processing overhead and power consumption.
402 may be specified to adjust the interpretation of
406 .Bl -tag -width ".Dv C_DIRECT_EXEC"
410 argument as an absolute time since boot.
413 is treated as a relative amount of time,
417 Run the handler directly from hardware interrupt context instead of from the
419 This reduces latency and overhead, but puts more constraints on the callout
421 Callout functions run in this context may use only spin mutexes for locking
422 and should be as small as possible because they run with absolute priority.
424 Specifies relative event time precision as binary logarithm of time interval
425 divided by acceptable time deviation: 1 -- 1/2, 2 -- 1/4, etc.
426 Note that the larger of
428 or this value is used as the length of the time window.
430 .Pq which result in larger time intervals
431 allow the callout subsystem to aggregate more events in one timer interrupt.
435 argument specifies the absolute time at which the callout should be run,
438 argument specifies the requested precision, which will not be
439 adjusted during the scheduling process.
444 values should be calculated by an earlier call to
446 which uses the user-supplied
453 Align the timeouts to
462 argument which identifies the function to be called when the time expires.
463 It must be a pointer to a function that takes a single
470 as its only argument.
477 arguments from the previous callout.
480 functions must always be called to initialize
486 functions can be used.
488 The callout subsystem provides a softclock thread for each CPU in the system.
489 Callouts are assigned to a single CPU and are executed by the softclock thread
492 callouts are assigned to CPU 0.
494 .Fn callout_reset_on ,
495 .Fn callout_reset_sbt_on ,
496 .Fn callout_schedule_on
498 .Fn callout_schedule_sbt_on
499 functions assign the callout to CPU
502 .Fn callout_reset_curcpu ,
503 .Fn callout_reset_sbt_curpu ,
504 .Fn callout_schedule_curcpu
506 .Fn callout_schedule_sbt_curcpu
507 functions assign the callout to the current CPU.
510 .Fn callout_reset_sbt ,
513 .Fn callout_schedule_sbt
514 functions schedule the callout to execute in the softclock thread of the CPU
515 to which it is currently assigned.
517 Softclock threads are not pinned to their respective CPUs by default.
518 The softclock thread for CPU 0 can be pinned to CPU 0 by setting the
519 .Va kern.pin_default_swi
520 loader tunable to a non-zero value.
521 Softclock threads for CPUs other than zero can be pinned to their
522 respective CPUs by setting the
523 .Va kern.pin_pcpu_swi
524 loader tunable to a non-zero value.
527 .Fn callout_pending ,
530 .Fn callout_deactivate
531 provide access to the current state of the callout.
534 macro checks whether a callout is
536 a callout is considered
538 when a timeout has been set but the time has not yet arrived.
539 Note that once the timeout time arrives and the callout subsystem
540 starts to process this callout,
544 even though the callout function may not have finished
549 macro checks whether a callout is marked as
552 .Fn callout_deactivate
553 macro clears the callout's
556 The callout subsystem marks a callout as
558 when a timeout is set and it clears the
566 clear it when a callout expires normally via the execution of the
571 function may be used to pre-calculate the absolute time at which the
572 timeout should be run and the precision of the scheduled run time
573 according to the required time
577 and additional adjustments requested by the
580 Flags accepted by the
582 function are the same as flags for the
585 The resulting time is assigned to the variable pointed to by the
587 argument, and the resulting precision is assigned to
589 When passing the results to
595 to avoid incorrect re-adjustment.
596 The function is intended for situations where precise time of the callout
597 run should be known in advance, since
598 trying to read this time from the callout structure itself after a
601 .Ss "Avoiding Race Conditions"
602 The callout subsystem invokes callout functions from its own thread
604 Without some kind of synchronization,
605 it is possible that a callout
606 function will be invoked concurrently with an attempt to stop or reset
607 the callout by another thread.
608 In particular, since callout functions typically acquire a lock as
609 their first action, the callout function may have already been invoked,
610 but is blocked waiting for that lock at the time that another thread
611 tries to reset or stop the callout.
613 There are three main techniques for addressing these
614 synchronization concerns.
615 The first approach is preferred as it is the simplest:
616 .Bl -enum -offset indent
618 Callouts can be associated with a specific lock when they are initialized
620 .Fn callout_init_mtx ,
621 .Fn callout_init_rm ,
623 .Fn callout_init_rw .
624 When a callout is associated with a lock,
625 the callout subsystem acquires the lock before the callout function is
627 This allows the callout subsystem to transparently handle races between
628 callout cancellation,
631 Note that the associated lock must be acquired before calling
637 functions to provide this safety.
639 A callout initialized via
643 set to zero is implicitly associated with the
648 is held when cancelling or rescheduling the callout,
649 then its use will prevent races with the callout function.
651 The return value from
660 indicates whether or not the callout was removed.
661 If it is known that the callout was set and the callout function has
662 not yet executed, then a return value of
664 indicates that the callout function is about to be called.
666 .Bd -literal -offset indent
667 if (sc->sc_flags & SCFLG_CALLOUT_RUNNING) {
668 if (callout_stop(&sc->sc_callout)) {
669 sc->sc_flags &= ~SCFLG_CALLOUT_RUNNING;
670 /* successfully stopped */
673 * callout has expired and callout
674 * function is about to be executed
681 .Fn callout_pending ,
684 .Fn callout_deactivate
685 macros can be used together to work around the race conditions.
686 When a callout's timeout is set, the callout subsystem marks the
691 When the timeout time arrives, the callout subsystem begins processing
692 the callout by first clearing the
695 It then invokes the callout function without changing the
697 flag, and does not clear the
699 flag even after the callout function returns.
700 The mechanism described here requires the callout function itself to
704 .Fn callout_deactivate
710 functions always clear both the
714 flags before returning.
716 The callout function should first check the
718 flag and return without action if
722 This indicates that the callout was rescheduled using
724 just before the callout function was invoked.
729 then the callout function should also return without action.
730 This indicates that the callout has been stopped.
731 Finally, the callout function should call
732 .Fn callout_deactivate
737 .Bd -literal -offset indent
738 mtx_lock(&sc->sc_mtx);
739 if (callout_pending(&sc->sc_callout)) {
740 /* callout was reset */
741 mtx_unlock(&sc->sc_mtx);
744 if (!callout_active(&sc->sc_callout)) {
745 /* callout was stopped */
746 mtx_unlock(&sc->sc_mtx);
749 callout_deactivate(&sc->sc_callout);
750 /* rest of callout function */
753 Together with appropriate synchronization, such as the mutex used above,
754 this approach permits the
758 functions to be used at any time without races.
760 .Bd -literal -offset indent
761 mtx_lock(&sc->sc_mtx);
762 callout_stop(&sc->sc_callout);
763 /* The callout is effectively stopped now. */
766 If the callout is still pending then these functions operate normally,
767 but if processing of the callout has already begun then the tests in
768 the callout function cause it to return without further action.
769 Synchronization between the callout function and other code ensures that
770 stopping or resetting the callout will never be attempted while the
771 callout function is past the
772 .Fn callout_deactivate
775 The above technique additionally ensures that the
777 flag always reflects whether the callout is effectively enabled or
781 returns false, then the callout is effectively disabled, since even if
782 the callout subsystem is actually just about to invoke the callout
783 function, the callout function will return without action.
786 There is one final race condition that must be considered when a
787 callout is being stopped for the last time.
788 In this case it may not be safe to let the callout function itself
789 detect that the callout was stopped, since it may need to access
790 data objects that have already been destroyed or recycled.
791 To ensure that the callout is completely finished, a call to
795 a callout should always be drained prior to destroying its associated lock
796 or releasing the storage for the callout structure.
800 macro returns the state of a callout's
806 macro returns the state of a callout's
814 function families return a value of one if the callout was pending before the new
815 function invocation was scheduled.
821 functions return a value of one if the callout was still pending when it was
822 called, a zero if the callout could not be stopped and a negative one is it
823 was either not running or has already completed.
826 initially used the long standing
829 callout mechanism which offered O(n) insertion and removal running time
830 but did not generate or require handles for untimeout operations.
833 introduced a new set of timeout and untimeout routines from
838 .An George Varghese ,
839 published in a technical report entitled
840 .%T "Redesigning the BSD Callout and Timer Facilities"
841 and modified for inclusion in
844 .An Justin T. Gibbs .
845 The original work on the data structures used in that implementation
851 .%T "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility"
853 .%B "Proceedings of the 11th ACM Annual Symposium on Operating Systems Principles" .
856 introduced the first implementations of
861 which permitted callers to allocate dedicated storage for callouts.
862 This ensured that a callout would always fire unlike
864 which would silently fail if it was unable to allocate a callout.
867 permitted callout handlers to be tagged as MPSAFE via
876 .Fn callout_init_mtx .
879 introduced per-CPU callout wheels,
880 .Fn callout_init_rw ,
882 .Fn callout_schedule .
885 changed the underlying timer interrupts used to drive callouts to prefer
886 one-shot event timers instead of a periodic timer interrupt.
889 switched the callout wheel to support tickless operation.
890 These changes introduced
893 .Fn callout_reset_sbt*
898 .Fn callout_init_rm .
902 .Fn callout_schedule_sbt*
907 .Fn callout_async_drain .