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 ,
40 .Nm callout_handle_init ,
42 .Nm callout_init_mtx ,
47 .Nm callout_reset_curcpu ,
48 .Nm callout_reset_on ,
49 .Nm callout_reset_sbt ,
50 .Nm callout_reset_sbt_curcpu ,
51 .Nm callout_reset_sbt_on ,
52 .Nm callout_schedule ,
53 .Nm callout_schedule_curcpu ,
54 .Nm callout_schedule_on ,
55 .Nm callout_schedule_sbt ,
56 .Nm callout_schedule_sbt_curcpu ,
57 .Nm callout_schedule_sbt_on ,
60 .Nd execute a function after a specified length of time
65 typedef void callout_func_t (void *);
68 .Fn callout_active "struct callout *c"
70 .Fn callout_deactivate "struct callout *c"
72 .Fn callout_async_drain "struct callout *c" "callout_func_t *drain"
74 .Fn callout_drain "struct callout *c"
76 .Fn callout_handle_init "struct callout_handle *handle"
78 struct callout_handle handle = CALLOUT_HANDLE_INITIALIZER(&handle);
81 .Fn callout_init "struct callout *c" "int mpsafe"
83 .Fn callout_init_mtx "struct callout *c" "struct mtx *mtx" "int flags"
85 .Fn callout_init_rm "struct callout *c" "struct rmlock *rm" "int flags"
87 .Fn callout_init_rw "struct callout *c" "struct rwlock *rw" "int flags"
89 .Fn callout_pending "struct callout *c"
92 .Fa "struct callout *c"
94 .Fa "callout_func_t *func"
98 .Fo callout_reset_curcpu
99 .Fa "struct callout *c"
101 .Fa "callout_func_t *func"
106 .Fa "struct callout *c"
108 .Fa "callout_func_t *func"
113 .Fo callout_reset_sbt
114 .Fa "struct callout *c"
117 .Fa "callout_func_t *func"
122 .Fo callout_reset_sbt_curcpu
123 .Fa "struct callout *c"
126 .Fa "callout_func_t *func"
131 .Fo callout_reset_sbt_on
132 .Fa "struct callout *c"
135 .Fa "callout_func_t *func"
141 .Fn callout_schedule "struct callout *c" "int ticks"
143 .Fn callout_schedule_curcpu "struct callout *c" "int ticks"
145 .Fn callout_schedule_on "struct callout *c" "int ticks" "int cpu"
147 .Fo callout_schedule_sbt
148 .Fa "struct callout *c"
154 .Fo callout_schedule_sbt_curcpu
155 .Fa "struct callout *c"
161 .Fo callout_schedule_sbt_on
162 .Fa "struct callout *c"
169 .Fn callout_stop "struct callout *c"
173 .Fa "sbintime_t precision"
175 .Fa "sbintime_t *sbt_res"
176 .Fa "sbintime_t *precision_res"
181 API is used to schedule a call to an arbitrary function at a specific
183 Consumers of this API are required to allocate a callout structure
185 for each pending function invocation.
186 This structure stores state about the pending function invocation including
187 the function to be called and the time at which the function should be invoked.
188 Pending function calls can be cancelled or rescheduled to a different time.
190 a callout structure may be reused to schedule a new function call after a
191 scheduled call is completed.
193 Callouts only provide a single-shot mode.
194 If a consumer requires a periodic timer,
195 it must explicitly reschedule each function call.
196 This is normally done by rescheduling the subsequent call within the called
199 Callout functions must not sleep.
200 They may not acquire sleepable locks,
201 wait on condition variables,
202 perform blocking allocation requests,
203 or invoke any other action that might sleep.
205 Each callout structure must be initialized by
207 .Fn callout_init_mtx ,
208 .Fn callout_init_rm ,
211 before it is passed to any of the other callout functions.
214 function initializes a callout structure in
216 that is not associated with a specific lock.
220 the callout structure is not considered to be
221 .Dq multi-processor safe ;
222 and the Giant lock will be acquired before calling the callout function
223 and released when the callout function returns.
226 .Fn callout_init_mtx ,
227 .Fn callout_init_rm ,
230 functions initialize a callout structure in
232 that is associated with a specific lock.
233 The lock is specified by the
239 The associated lock must be held while stopping or rescheduling the
241 The callout subsystem acquires the associated lock before calling the
242 callout function and releases it after the function returns.
243 If the callout was cancelled while the callout subsystem waited for the
245 the callout function is not called,
246 and the associated lock is released.
247 This ensures that stopping or rescheduling the callout will abort any
248 previously scheduled invocation.
250 Only regular mutexes may be used with
251 .Fn callout_init_mtx ;
252 spin mutexes are not supported.
253 A sleepable read-mostly lock
255 one initialized with the
260 .Fn callout_init_rm .
261 Similarly, other sleepable lock types such as
265 cannot be used with callouts because sleeping is not permitted in
266 the callout subsystem.
271 .Fn callout_init_mtx ,
272 .Fn callout_init_rm ,
274 .Fn callout_init_rw :
275 .Bl -tag -width ".Dv CALLOUT_RETURNUNLOCKED"
276 .It Dv CALLOUT_RETURNUNLOCKED
277 The callout function will release the associated lock itself,
278 so the callout subsystem should not attempt to unlock it
279 after the callout function returns.
280 .It Dv CALLOUT_SHAREDLOCK
281 The lock is only acquired in read mode when running the callout handler.
282 This flag is ignored by
283 .Fn callout_init_mtx .
290 if it is currently pending.
291 If the callout is pending and successfully stopped, then
293 returns a value of one.
294 If the callout is not set, or
295 has already been serviced, then
296 negative one is returned.
297 If the callout is currently being serviced and cannot be stopped,
298 then zero will be returned.
299 If the callout is currently being serviced and cannot be stopped, and at the
300 same time a next invocation of the same callout is also scheduled, then
302 unschedules the next run and returns zero.
303 If the callout has an associated lock,
304 then that lock must be held when this function is called.
307 .Fn callout_async_drain
312 .Fn callout_async_drain
313 returns zero it will arrange for the function
315 to be called using the same argument given to the
318 .Fn callout_async_drain
319 If the callout has an associated lock,
320 then that lock must be held when this function is called.
321 Note that when stopping multiple callouts that use the same lock it is possible
322 to get multiple return's of zero and multiple calls to the
324 function, depending upon which CPU's the callouts are running.
327 function itself is called from the context of the completing callout
328 i.e. softclock or hardclock, just like a callout itself.
334 except that it will wait for the callout
336 to complete if it is already in progress.
337 This function MUST NOT be called while holding any
338 locks on which the callout might block, or deadlock will result.
339 Note that if the callout subsystem has already begun processing this
340 callout, then the callout function may be invoked before
343 However, the callout subsystem does guarantee that the callout will be
352 function families schedule a future function invocation for callout
356 already has a pending callout,
357 it is cancelled before the new invocation is scheduled.
358 These functions return a value of one if a pending callout was cancelled
359 and zero if there was no pending callout.
360 If the callout has an associated lock,
361 then that lock must be held when any of these functions are called.
363 The time at which the callout function will be invoked is determined by
375 the callout is scheduled to execute after
378 Non-positive values of
380 are silently converted to the value
388 arguments provide more control over the scheduled time including
389 support for higher resolution times,
390 specifying the precision of the scheduled time,
391 and setting an absolute deadline instead of a relative timeout.
392 The callout is scheduled to execute in a time window which begins at
393 the time specified in
395 and extends for the amount of time specified in
399 specifies a time in the past,
400 the window is adjusted to start at the current time.
403 allows the callout subsystem to coalesce callouts scheduled close to each
404 other into fewer timer interrupts,
405 reducing processing overhead and power consumption.
408 may be specified to adjust the interpretation of
412 .Bl -tag -width ".Dv C_DIRECT_EXEC"
416 argument as an absolute time since boot.
419 is treated as a relative amount of time,
423 Run the handler directly from hardware interrupt context instead of from the
425 This reduces latency and overhead, but puts more constraints on the callout
427 Callout functions run in this context may use only spin mutexes for locking
428 and should be as small as possible because they run with absolute priority.
430 Specifies relative event time precision as binary logarithm of time interval
431 divided by acceptable time deviation: 1 -- 1/2, 2 -- 1/4, etc.
432 Note that the larger of
434 or this value is used as the length of the time window.
436 .Pq which result in larger time intervals
437 allow the callout subsystem to aggregate more events in one timer interrupt.
441 argument specifies the absolute time at which the callout should be run,
444 argument specifies the requested precision, which will not be
445 adjusted during the scheduling process.
450 values should be calculated by an earlier call to
452 which uses the user-supplied
459 Align the timeouts to
468 argument which identifies the function to be called when the time expires.
469 It must be a pointer to a function that takes a single
476 as its only argument.
483 arguments from the previous callout.
486 functions must always be called to initialize
492 functions can be used.
494 The callout subsystem provides a softclock thread for each CPU in the system.
495 Callouts are assigned to a single CPU and are executed by the softclock thread
498 callouts are assigned to CPU 0.
500 .Fn callout_reset_on ,
501 .Fn callout_reset_sbt_on ,
502 .Fn callout_schedule_on
504 .Fn callout_schedule_sbt_on
505 functions assign the callout to CPU
508 .Fn callout_reset_curcpu ,
509 .Fn callout_reset_sbt_curpu ,
510 .Fn callout_schedule_curcpu
512 .Fn callout_schedule_sbt_curcpu
513 functions assign the callout to the current CPU.
516 .Fn callout_reset_sbt ,
519 .Fn callout_schedule_sbt
520 functions schedule the callout to execute in the softclock thread of the CPU
521 to which it is currently assigned.
523 Softclock threads are not pinned to their respective CPUs by default.
524 The softclock thread for CPU 0 can be pinned to CPU 0 by setting the
525 .Va kern.pin_default_swi
526 loader tunable to a non-zero value.
527 Softclock threads for CPUs other than zero can be pinned to their
528 respective CPUs by setting the
529 .Va kern.pin_pcpu_swi
530 loader tunable to a non-zero value.
533 .Fn callout_pending ,
536 .Fn callout_deactivate
537 provide access to the current state of the callout.
540 macro checks whether a callout is
542 a callout is considered
544 when a timeout has been set but the time has not yet arrived.
545 Note that once the timeout time arrives and the callout subsystem
546 starts to process this callout,
550 even though the callout function may not have finished
555 macro checks whether a callout is marked as
558 .Fn callout_deactivate
559 macro clears the callout's
562 The callout subsystem marks a callout as
564 when a timeout is set and it clears the
572 clear it when a callout expires normally via the execution of the
577 function may be used to pre-calculate the absolute time at which the
578 timeout should be run and the precision of the scheduled run time
579 according to the required time
583 and additional adjustments requested by the
586 Flags accepted by the
588 function are the same as flags for the
591 The resulting time is assigned to the variable pointed to by the
593 argument, and the resulting precision is assigned to
595 When passing the results to
601 to avoid incorrect re-adjustment.
602 The function is intended for situations where precise time of the callout
603 run should be known in advance, since
604 trying to read this time from the callout structure itself after a
607 .Ss "Avoiding Race Conditions"
608 The callout subsystem invokes callout functions from its own thread
610 Without some kind of synchronization,
611 it is possible that a callout
612 function will be invoked concurrently with an attempt to stop or reset
613 the callout by another thread.
614 In particular, since callout functions typically acquire a lock as
615 their first action, the callout function may have already been invoked,
616 but is blocked waiting for that lock at the time that another thread
617 tries to reset or stop the callout.
619 There are three main techniques for addressing these
620 synchronization concerns.
621 The first approach is preferred as it is the simplest:
622 .Bl -enum -offset indent
624 Callouts can be associated with a specific lock when they are initialized
626 .Fn callout_init_mtx ,
627 .Fn callout_init_rm ,
629 .Fn callout_init_rw .
630 When a callout is associated with a lock,
631 the callout subsystem acquires the lock before the callout function is
633 This allows the callout subsystem to transparently handle races between
634 callout cancellation,
637 Note that the associated lock must be acquired before calling
643 functions to provide this safety.
645 A callout initialized via
649 set to zero is implicitly associated with the
654 is held when cancelling or rescheduling the callout,
655 then its use will prevent races with the callout function.
657 The return value from
666 indicates whether or not the callout was removed.
667 If it is known that the callout was set and the callout function has
668 not yet executed, then a return value of
670 indicates that the callout function is about to be called.
672 .Bd -literal -offset indent
673 if (sc->sc_flags & SCFLG_CALLOUT_RUNNING) {
674 if (callout_stop(&sc->sc_callout)) {
675 sc->sc_flags &= ~SCFLG_CALLOUT_RUNNING;
676 /* successfully stopped */
679 * callout has expired and callout
680 * function is about to be executed
687 .Fn callout_pending ,
690 .Fn callout_deactivate
691 macros can be used together to work around the race conditions.
692 When a callout's timeout is set, the callout subsystem marks the
697 When the timeout time arrives, the callout subsystem begins processing
698 the callout by first clearing the
701 It then invokes the callout function without changing the
703 flag, and does not clear the
705 flag even after the callout function returns.
706 The mechanism described here requires the callout function itself to
710 .Fn callout_deactivate
716 functions always clear both the
720 flags before returning.
722 The callout function should first check the
724 flag and return without action if
728 This indicates that the callout was rescheduled using
730 just before the callout function was invoked.
735 then the callout function should also return without action.
736 This indicates that the callout has been stopped.
737 Finally, the callout function should call
738 .Fn callout_deactivate
743 .Bd -literal -offset indent
744 mtx_lock(&sc->sc_mtx);
745 if (callout_pending(&sc->sc_callout)) {
746 /* callout was reset */
747 mtx_unlock(&sc->sc_mtx);
750 if (!callout_active(&sc->sc_callout)) {
751 /* callout was stopped */
752 mtx_unlock(&sc->sc_mtx);
755 callout_deactivate(&sc->sc_callout);
756 /* rest of callout function */
759 Together with appropriate synchronization, such as the mutex used above,
760 this approach permits the
764 functions to be used at any time without races.
766 .Bd -literal -offset indent
767 mtx_lock(&sc->sc_mtx);
768 callout_stop(&sc->sc_callout);
769 /* The callout is effectively stopped now. */
772 If the callout is still pending then these functions operate normally,
773 but if processing of the callout has already begun then the tests in
774 the callout function cause it to return without further action.
775 Synchronization between the callout function and other code ensures that
776 stopping or resetting the callout will never be attempted while the
777 callout function is past the
778 .Fn callout_deactivate
781 The above technique additionally ensures that the
783 flag always reflects whether the callout is effectively enabled or
787 returns false, then the callout is effectively disabled, since even if
788 the callout subsystem is actually just about to invoke the callout
789 function, the callout function will return without action.
792 There is one final race condition that must be considered when a
793 callout is being stopped for the last time.
794 In this case it may not be safe to let the callout function itself
795 detect that the callout was stopped, since it may need to access
796 data objects that have already been destroyed or recycled.
797 To ensure that the callout is completely finished, a call to
801 a callout should always be drained prior to destroying its associated lock
802 or releasing the storage for the callout structure.
806 macro returns the state of a callout's
812 macro returns the state of a callout's
820 function families return a value of one if the callout was pending before the new
821 function invocation was scheduled.
827 functions return a value of one if the callout was still pending when it was
828 called, a zero if the callout could not be stopped and a negative one is it
829 was either not running or has already completed.
832 initially used the long standing
835 callout mechanism which offered O(n) insertion and removal running time
836 but did not generate or require handles for untimeout operations.
839 introduced a new set of timeout and untimeout routines from
844 .An George Varghese ,
845 published in a technical report entitled
846 .%T "Redesigning the BSD Callout and Timer Facilities"
847 and modified for inclusion in
850 .An Justin T. Gibbs .
851 The original work on the data structures used in that implementation
857 .%T "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility"
859 .%B "Proceedings of the 11th ACM Annual Symposium on Operating Systems Principles" .
862 introduced the first implementations of
867 which permitted callers to allocate dedicated storage for callouts.
868 This ensured that a callout would always fire unlike
870 which would silently fail if it was unable to allocate a callout.
873 permitted callout handlers to be tagged as MPSAFE via
882 .Fn callout_init_mtx .
885 introduced per-CPU callout wheels,
886 .Fn callout_init_rw ,
888 .Fn callout_schedule .
891 changed the underlying timer interrupts used to drive callouts to prefer
892 one-shot event timers instead of a periodic timer interrupt.
895 switched the callout wheel to support tickless operation.
896 These changes introduced
899 .Fn callout_reset_sbt*
904 .Fn callout_init_rm .
908 .Fn callout_schedule_sbt*
913 .Fn callout_async_drain .