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 ".Dv 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 there was already a pending callout and it was rescheduled, then
265 will return a non-zero value.
266 If the callout has an associated mutex, then that mutex must be
267 held when this function is called.
270 .Fn callout_pending ,
273 .Fn callout_deactivate
274 provide access to the current state of the callout.
275 Careful use of these macros can avoid many of the race conditions
276 that are inherent in asynchronous timer facilities; see
277 .Sx "Avoiding Race Conditions"
278 below for further details.
281 macro checks whether a callout is
283 a callout is considered
285 when a timeout has been set but the time has not yet arrived.
286 Note that once the timeout time arrives and the callout subsystem
287 starts to process this callout,
291 even though the callout function may not have finished (or even begun)
295 macro checks whether a callout is marked as
298 .Fn callout_deactivate
299 macro clears the callout's
302 The callout subsystem marks a callout as
304 when a timeout is set and it clears the
312 clear it when a callout expires normally via the execution of the
314 .Ss "Avoiding Race Conditions"
315 The callout subsystem invokes callout functions from its own timer
317 Without some kind of synchronization it is possible that a callout
318 function will be invoked concurrently with an attempt to stop or reset
319 the callout by another thread.
320 In particular, since callout functions typically acquire a mutex as
321 their first action, the callout function may have already been invoked,
322 but be blocked waiting for that mutex at the time that another thread
323 tries to reset or stop the callout.
325 The callout subsystem provides a number of mechanisms to address these
326 synchronization concerns:
327 .Bl -enum -offset indent
329 If the callout has an associated mutex that was specified using the
331 function (or implicitly specified as the
339 then this mutex is used to avoid the race conditions.
340 The associated mutex must be acquired by the caller before calling
344 and it is guaranteed that the callout will be correctly stopped
345 or reset as expected.
346 Note that it is still necessary to use
348 before destroying the callout or its associated mutex.
350 The return value from
354 indicates whether or not the callout was removed.
355 If it is known that the callout was set and the callout function has
356 not yet executed, then a return value of
358 indicates that the callout function is about to be called.
360 .Bd -literal -offset indent
361 if (sc->sc_flags & SCFLG_CALLOUT_RUNNING) {
362 if (callout_stop(&sc->sc_callout)) {
363 sc->sc_flags &= ~SCFLG_CALLOUT_RUNNING;
364 /* successfully stopped */
367 * callout has expired and callout
368 * function is about to be executed
376 .Fn callout_pending ,
379 .Fn callout_deactivate
380 macros can be used together to work around the race conditions.
381 When a callout's timeout is set, the callout subsystem marks the
386 When the timeout time arrives, the callout subsystem begins processing
387 the callout by first clearing the
390 It then invokes the callout function without changing the
392 flag, and does not clear the
394 flag even after the callout function returns.
395 The mechanism described here requires the callout function itself to
399 .Fn callout_deactivate
405 functions always clear both the
409 flags before returning.
411 The callout function should first check the
413 flag and return without action if
417 This indicates that the callout was rescheduled using
419 just before the callout function was invoked.
424 then the callout function should also return without action.
425 This indicates that the callout has been stopped.
426 Finally, the callout function should call
427 .Fn callout_deactivate
432 .Bd -literal -offset indent
433 mtx_lock(&sc->sc_mtx);
434 if (callout_pending(&sc->sc_callout)) {
435 /* callout was reset */
436 mtx_unlock(&sc->sc_mtx);
439 if (!callout_active(&sc->sc_callout)) {
440 /* callout was stopped */
441 mtx_unlock(&sc->sc_mtx);
444 callout_deactivate(&sc->sc_callout);
445 /* rest of callout function */
448 Together with appropriate synchronization, such as the mutex used above,
449 this approach permits the
453 functions to be used at any time without races.
455 .Bd -literal -offset indent
456 mtx_lock(&sc->sc_mtx);
457 callout_stop(&sc->sc_callout);
458 /* The callout is effectively stopped now. */
461 If the callout is still pending then these functions operate normally,
462 but if processing of the callout has already begun then the tests in
463 the callout function cause it to return without further action.
464 Synchronization between the callout function and other code ensures that
465 stopping or resetting the callout will never be attempted while the
466 callout function is past the
467 .Fn callout_deactivate
470 The above technique additionally ensures that the
472 flag always reflects whether the callout is effectively enabled or
476 returns false, then the callout is effectively disabled, since even if
477 the callout subsystem is actually just about to invoke the callout
478 function, the callout function will return without action.
481 There is one final race condition that must be considered when a
482 callout is being stopped for the last time.
483 In this case it may not be safe to let the callout function itself
484 detect that the callout was stopped, since it may need to access
485 data objects that have already been destroyed or recycled.
486 To ensure that the callout is completely finished, a call to
493 .Ft struct callout_handle
494 that can be passed to
500 functions return non-zero if the callout was still pending when it was
501 called or zero otherwise.
503 The current timeout and untimeout routines are based on the work of
506 .An George Varghese ,
507 published in a technical report entitled
508 .%T "Redesigning the BSD Callout and Timer Facilities"
509 and modified slightly for inclusion in
512 .An Justin T. Gibbs .
513 The original work on the data structures used in this implementation
519 .%T "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility"
521 .%B "Proceedings of the 11th ACM Annual Symposium on Operating Systems Principles" .
522 The current implementation replaces the long standing
525 callout mechanism which offered O(n) insertion and removal running time
526 but did not generate or require handles for untimeout operations.