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.
17 .\" 3. All advertising materials mentioning features or use of this software
18 .\" must display the following acknowledgement:
19 .\" This product includes software developed by the NetBSD
20 .\" Foundation, Inc. and its contributors.
21 .\" 4. Neither the name of The NetBSD Foundation nor the names of its
22 .\" contributors may be used to endorse or promote products derived
23 .\" from this software without specific prior written permission.
25 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
26 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
27 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 .\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
29 .\" LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 .\" POSSIBILITY OF SUCH DAMAGE.
45 .Nm callout_handle_init ,
47 .Nm callout_init_mtx ,
53 .Nm callout_deactivate
54 .Nd execute a function after a specified length of time
60 typedef void timeout_t (void *);
62 .Ft struct callout_handle
63 .Fn timeout "timeout_t *func" "void *arg" "int ticks"
65 .Fn callout_handle_init "struct callout_handle *handle"
68 struct callout_handle handle = CALLOUT_HANDLE_INITIALIZER(&handle)
71 .Fn untimeout "timeout_t *func" "void *arg" "struct callout_handle handle"
73 .Fn callout_init "struct callout *c" "int mpsafe"
75 .Fn callout_init_mtx "struct callout *c" "struct mtx *mtx" "int flags"
77 .Fn callout_stop "struct callout *c"
79 .Fn callout_drain "struct callout *c"
81 .Fn callout_reset "struct callout *c" "int ticks" "timeout_t *func" "void *arg"
83 .Fn callout_pending "struct callout *c"
85 .Fn callout_active "struct callout *c"
86 .Fn callout_deactivate "struct callout *c"
90 schedules a call to the function given by the argument
95 Non-positive values of
97 are silently converted to the value
100 should be a pointer to a function that takes a
107 as its only argument.
108 The return value from
111 .Ft struct callout_handle
112 which can be used in conjunction with the
114 function to request that a scheduled timeout be canceled.
117 call is the old style and new code should use the
122 .Fn callout_handle_init
123 can be used to initialize a handle to a state which will cause
124 any calls to untimeout with that handle to return with no side
127 Assigning a callout handle the value of
128 .Fn CALLOUT_HANDLE_INITIALIZER
129 performs the same function as
130 .Fn callout_handle_init
131 and is provided for use on statically declared or global callout handles.
135 cancels the timeout associated with
141 arguments to validate the handle.
142 If the handle does not correspond to a timeout with
149 must be initialized by a previous call to
151 .Fn callout_handle_init ,
152 or assigned the value of
153 .Fn CALLOUT_HANDLE_INITIALIZER "&handle"
154 before being passed to
156 The behavior of calling untimeout without a previously initialized handle
160 call is the old style and new code should use the
164 As handles are recycled by the system, it is possible (although unlikely)
165 that a handle from one invocation of
167 may match the handle of another invocation of
169 if both calls used the same function pointer and argument, and the first
170 timeout is expired or canceled before the second call.
171 The timeout facility offers O(1) running time for
175 Timeouts are executed from
180 Thus they are protected from re-entrancy.
184 .Fn callout_init_mtx ,
189 are low-level routines for clients who wish to allocate their own
194 initializes a callout so it can be passed to
199 without any side effects.
203 the callout structure is not considered to be
204 .Dq multi-processor safe ;
206 the Giant lock will be acquired before calling the callout function,
207 and released when the callout function returns.
211 function may be used as an alternative to
215 specifies a mutex that is to be acquired by the callout subsystem
216 before calling the callout function, and released when the callout
221 .Bl -tag -width CALLOUT_RETURNUNLOCKED
222 .It Dv CALLOUT_RETURNUNLOCKED
223 The callout function will release
225 itself, so the callout subsystem should not attempt to unlock it
226 after the callout function returns.
231 cancels a callout if it is currently pending.
232 If the callout is pending, then
234 will return a non-zero value.
235 If the callout is not set, has already been serviced or is currently
236 being serviced, then zero will be returned.
237 If the callout has an associated mutex, then that mutex must be
238 held when this function is called.
244 except that it will wait for the callout to be completed if it is
246 This function MUST NOT be called while holding any
247 locks on which the callout might block, or deadlock will result.
248 Note that if the callout subsystem has already begun processing this
249 callout, then the callout function may be invoked during the execution of
251 However, the callout subsystem does guarantee that the callout will be
258 first performs the equivalent of
260 to disestablish the callout, and then establishes a new callout in the
263 If the callout has an associated mutex, then that mutex must be
264 held when this function is called.
267 .Fn callout_pending ,
270 .Fn callout_deactivate
271 provide access to the current state of the callout.
272 Careful use of these macros can avoid many of the race conditions
273 that are inherent in asynchronous timer facilities; see
274 .Sx "Avoiding Race Conditions"
275 below for further details.
278 macro checks whether a callout is
280 a callout is considered
282 when a timeout has been set but the time has not yet arrived.
283 Note that once the timeout time arrives and the callout subsystem
284 starts to process this callout,
288 even though the callout function may not have finished (or even begun)
292 macro checks whether a callout is marked as
295 .Fn callout_deactivate
296 macro clears the callout's
299 The callout subsystem marks a callout as
301 when a timeout is set and it clears the
309 clear it when a callout expires normally via the execution of the
311 .Ss "Avoiding Race Conditions"
312 The callout subsystem invokes callout functions from its own timer
314 Without some kind of synchronization it is possible that a callout
315 function will be invoked concurrently with an attempt to stop or reset
316 the callout by another thread.
317 In particular, since callout functions typically acquire a mutex as
318 their first action, the callout function may have already been invoked,
319 but be blocked waiting for that mutex at the time that another thread
320 tries to reset or stop the callout.
322 The callout subsystem provides a number of mechanisms to address these
323 synchronization concerns:
324 .Bl -enum -offset indent
326 If the callout has an associated mutex that was specified using the
328 function (or implicitly specified as the
336 then this mutex is used to avoid the race conditions.
337 The associated mutex must be acquired by the caller before calling
341 and it is guaranteed that the callout will be correctly stopped
342 or reset as expected.
343 Note that it is still necessary to use
345 before destroying the callout or its associated mutex.
347 The return value from
349 indicates whether or not the callout was removed.
350 If it is known that the callout was set and the callout function has
351 not yet executed, then a return value of
353 indicates that the callout function is about to be called.
355 .Bd -literal -offset indent
356 if (sc->sc_flags & SCFLG_CALLOUT_RUNNING) {
357 if (callout_stop(&sc->sc_callout)) {
358 sc->sc_flags &= ~SCFLG_CALLOUT_RUNNING;
359 /* successfully stopped */
362 * callout has expired and callout
363 * function is about to be executed
369 Note that there is no equivalent mechanism to determine whether or not
374 .Fn callout_pending ,
377 .Fn callout_deactivate
378 macros can be used together to work around the race conditions.
379 When a callout's timeout is set, the callout subsystem marks the
384 When the timeout time arrives, the callout subsystem begins processing
385 the callout by first clearing the
388 It then invokes the callout function without changing the
390 flag, and does not clear the
392 flag even after the callout function returns.
393 The mechanism described here requires the callout function itself to
397 .Fn callout_deactivate
403 functions always clear both the
407 flags before returning.
409 The callout function should first check the
411 flag and return without action if
415 This indicates that the callout was rescheduled using
417 just before the callout function was invoked.
422 then the callout function should also return without action.
423 This indicates that the callout has been stopped.
424 Finally, the callout function should call
425 .Fn callout_deactivate
430 .Bd -literal -offset indent
431 mtx_lock(&sc->sc_mtx);
432 if (callout_pending(&sc->sc_callout)) {
433 /* callout was reset */
434 mtx_unlock(&sc->sc_mtx);
437 if (!callout_active(&sc->sc_callout)) {
438 /* callout was stopped */
439 mtx_unlock(&sc->sc_mtx);
442 callout_deactivate(&sc->sc_callout);
443 /* rest of callout function */
446 Together with appropriate synchronization, such as the mutex used above,
447 this approach permits the
451 functions to be used at any time without races.
453 .Bd -literal -offset indent
454 mtx_lock(&sc->sc_mtx);
455 callout_stop(&sc->sc_callout);
456 /* The callout is effectively stopped now. */
459 If the callout is still pending then these functions operate normally,
460 but if processing of the callout has already begun then the tests in
461 the callout function cause it to return without further action.
462 Synchronization between the callout function and other code ensures that
463 stopping or resetting the callout will never be attempted while the
464 callout function is past the
465 .Fn callout_deactivate
468 The above technique additionally ensures that the
470 flag always reflects whether the callout is effectively enabled or
474 returns false, then the callout is effectively disabled, since even if
475 the callout subsystem is actually just about to invoke the callout
476 function, the callout function will return without action.
479 There is one final race condition that must be considered when a
480 callout is being stopped for the last time.
481 In this case it may not be safe to let the callout function itself
482 detect that the callout was stopped, since it may need to access
483 data objects that have already been destroyed or recycled.
484 To ensure that the callout is completely finished, a call to
491 .Ft struct callout_handle
492 that can be passed to
498 functions return non-zero if the callout was still pending when it was
499 called or zero otherwise.
501 The current timeout and untimeout routines are based on the work of
504 .An George Varghese ,
505 published in a technical report entitled
506 .%T "Redesigning the BSD Callout and Timer Facilities"
507 and modified slightly for inclusion in
510 .An Justin T. Gibbs .
511 The original work on the data structures used in this implementation
517 .%T "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility"
519 .%B "Proceedings of the 11th ACM Annual Symposium on Operating Systems Principles" .
520 The current implementation replaces the long standing
523 callout mechanism which offered O(n) insertion and removal running time
524 but did not generate or require handles for untimeout operations.