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.Dd March 26, 2019 31.Dt TIMEOUT 9 32.Os 33.Sh NAME 34.Nm callout_active , 35.Nm callout_deactivate , 36.Nm callout_drain , 37.Nm callout_init , 38.Nm callout_init_mp , 39.Nm callout_init_lk , 40.Nm callout_pending , 41.Nm callout_reset , 42.Nm callout_reset_bycpu , 43.Nm callout_stop , 44.Nm callout_stop_async , 45.Nm callout_cancel , 46.Nm callout_terminate 47.Nd execute a function after a specified length of time 48.Sh SYNOPSIS 49.In sys/types.h 50.In sys/systm.h 51.In sys/callout.h 52.Bd -literal 53typedef void timeout_t (void *); 54.Ed 55.Ft int 56.Fn callout_active "struct callout *c" 57.Ft void 58.Fn callout_deactivate "struct callout *c" 59.Ft int 60.Fn callout_drain "struct callout *c" 61.Ft void 62.Fn callout_init "struct callout *c" "int mpsafe" 63.Ft void 64.Fn callout_init_lk "struct callout *c" "struct lock *lk" 65.Ft int 66.Fn callout_pending "struct callout *c" 67.Ft void 68.Fn callout_reset "struct callout *c" "int ticks" "timeout_t *func" "void *arg" 69.Ft void 70.Fo callout_reset_bycpu 71.Fa "struct callout *c" 72.Fa "int ticks" 73.Fa "timeout_t *func" 74.Fa "void *arg" 75.Fa "int cpuid" 76.Fc 77.Ft int 78.Fn callout_stop "struct callout *c" 79.Ft int 80.Fn callout_stop_async "struct callout *c" 81.Ft int 82.Fn callout_cancel "struct callout *c" 83.Ft void 84.Fn callout_terminate "struct callout *c" 85.Sh DESCRIPTION 86The 87.Nm callout 88API is used to schedule a call to an arbitrary function at a specific 89time in the future. 90Consumers of this API are required to allocate a callout structure 91.Pq struct callout 92for each pending function invocation. 93This structure stores state about the pending function invocation including 94the function to be called and the time at which the function should be invoked. 95Pending function calls can be cancelled or rescheduled to a different time. 96In addition, 97a callout structure may be reused to schedule a new function call after a 98scheduled call is completed. 99.Pp 100Callouts only provide a single-shot mode. 101If a consumer requires a periodic timer, 102it must explicitly reschedule each function call. 103This is normally done by rescheduling the subsequent call within the called 104function. 105.Pp 106In 107.Fx 108callout functions must not sleep. 109They may not acquire sleepable locks, 110wait on condition variables, 111perform blocking allocation requests, 112or invoke any other action that might sleep. 113In 114.Dx 115all callout functions are executed from a common kernel thread on the 116target cpu and may block as long as deadlocks are avoided. But generally 117speaking, callout functions should run in as short a time as possible 118as they can add lag to other unrelated callouts. 119.Pp 120Each callout structure must be initialized by 121.Fn callout_init , 122.Fn callout_init_mp , 123or 124.Fn callout_init_lk 125before it is passed to any of the other callout functions. 126The 127.Fn callout_init 128and 129.Fn callout_init_mp 130functions initialize a callout structure in 131.Fa c 132that is not associated with a specific lock. 133The former will hold the mp_lock across callback. However, it is deprecated 134and should not be used in new code. 135.Fn callout_init_mp 136should be used for any new code. 137.Pp 138The 139.Fn callout_init_lk 140function initialize a callout structure in 141.Fa c 142that is associated with a specific lock. 143In 144.Fx 145the associated lock should be held while stopping or rescheduling the 146callout. 147In 148.Dx 149the same is true, but is not a requirement. 150.Pp 151The callout subsystem acquires the associated lock before calling the 152callout function and releases it after the function returns. 153If the callout was cancelled while the callout subsystem waited for the 154associated lock, 155the callout function is not called, 156and the associated lock is released. 157This ensures that stopping or rescheduling the callout will abort any 158previously scheduled invocation. 159.Pp 160The function 161.Fn callout_stop 162cancels a callout 163.Fa c 164if it is currently pending. 165If the callout is pending and successfully stopped, then 166.Fn callout_stop 167returns a value of one. 168In 169.Fx 170if the callout is not set, or 171has already been serviced, then 172negative one is returned. 173In 174.Dx 175if the callout is not set, or 176has already been serviced, then 177zero is returned. 178If the callout is currently being serviced and cannot be stopped, 179then zero will be returned. 180If the callout is currently being serviced and cannot be stopped, and at the 181same time a next invocation of the same callout is also scheduled, then 182.Fn callout_stop 183unschedules the next run and returns zero. 184In 185.Fx 186if the callout has an associated lock, 187then that lock must be held when this function is called. 188In 189.Dx 190if the callout has an associated lock, 191then that lock should be held when this function is called 192to avoid races, but does not have to be. 193.Pp 194In 195.Dx 196the stop operation is guaranteed to be synchronous if the callout 197was initialized with 198.Fn callout_init_lk . 199.Pp 200The function 201.Fn callout_stop_async 202is identical to 203.Fn callout_stop 204but does not block and allows the STOP operation to be asynchronous, 205meaning that the callout structure may still be relevant after the 206function returns. This situation can occur if the callback was 207in-progress at the time the stop was issued. 208.Pp 209The function 210.Fn callout_cancel 211synchronously cancels a callout and returns a value similar to that 212of 213.Fn callout_stop . 214.Fn callout_cancel 215overrides all other operations while it is in-progress. 216.Pp 217The function 218.Fn callout_terminate 219synchronously cancels a callout and informs the system that the 220callout structure will no longer be referenced. This function will 221clear the initialization flag and any further use of the callout structure 222will panic the system until it is next initialized. The callout structure 223can be safely freed after this function returns, assuming other program 224references to it have been removed. 225.Pp 226The function 227.Fn callout_drain 228is identical to 229.Fn callout_stop 230except that it will wait for the callout 231.Fa c 232to complete if it is already in progress. 233This function MUST NOT be called while holding any 234locks on which the callout might block, or deadlock will result. 235Note that if the callout subsystem has already begun processing this 236callout, then the callout function may be invoked before 237.Fn callout_drain 238returns. 239However, the callout subsystem does guarantee that the callout will be 240fully stopped before 241.Fn callout_drain 242returns. 243.Pp 244The 245.Fn callout_reset 246function schedules a future function invocation for callout 247.Fa c . 248If 249.Fa c 250already has a pending callout, 251it is cancelled before the new invocation is scheduled. 252In 253.Fx 254these functions return a value of one if a pending callout was cancelled 255and zero if there was no pending callout. 256If the callout has an associated lock, 257then that lock must be held when any of these functions are called. 258In 259.Dx 260these functions return void. 261If the callout has an associated lock, 262then that lock should generally be held when any of these functions are 263called, but the API will work either way. 264If a callout is already in-progress, this function's parameters will be 265applied when the in-progress callback returns, if not overridden from 266within the callback. 267.Pp 268The time at which the callout function will be invoked is determined by 269the 270.Fa ticks 271argument. 272The callout is scheduled to execute after 273.Fa ticks Ns No /hz 274seconds. 275Non-positive values of 276.Fa ticks 277are silently converted to the value 278.Sq 1 . 279.Pp 280The 281.Fn callout_reset_bycpu 282function schedules the callout to occur on the target cpu. The 283normal 284.Fn callout_reset 285function schedules the callout to occur on the current cpu. 286The 287.Fn callout_reset 288functions accept a 289.Fa func 290argument which identifies the function to be called when the time expires. 291It must be a pointer to a function that takes a single 292.Fa void * 293argument. 294Upon invocation, 295.Fa func 296will receive 297.Fa arg 298as its only argument. 299.Pp 300The callout subsystem provides a softclock thread for each CPU in the system. 301Callouts are assigned to a single CPU and are executed by the softclock thread 302for that CPU. 303The callouts are assigned to the current cpu or to a specific cpu 304depending on the call. 305.Pp 306The macros 307.Fn callout_pending , 308.Fn callout_active 309and 310.Fn callout_deactivate 311provide access to the current state of the callout. 312The 313.Fn callout_pending 314macro checks whether a callout is 315.Em pending ; 316a callout is considered 317.Em pending 318when a timeout has been set but the time has not yet arrived. 319Note that once the timeout time arrives and the callout subsystem 320starts to process this callout, 321.Fn callout_pending 322will return 323.Dv FALSE 324even though the callout function may not have finished 325.Pq or even begun 326executing. 327The 328.Fn callout_active 329macro checks whether a callout is marked as 330.Em active , 331and the 332.Fn callout_deactivate 333macro clears the callout's 334.Em active 335flag. 336The callout subsystem marks a callout as 337.Em active 338when a timeout is set and it clears the 339.Em active 340flag in 341.Fn callout_stop 342and 343.Fn callout_drain , 344but it 345.Em does not 346clear it when a callout expires normally via the execution of the 347callout function. 348.Pp 349There are three main techniques for addressing these 350synchronization concerns. 351The first approach is preferred as it is the simplest: 352.Bl -enum -offset indent 353.It 354Callouts can be associated with a specific lock when they are initialized 355by 356.Fn callout_init_lk 357When a callout is associated with a lock, 358the callout subsystem acquires the lock before the callout function is 359invoked. 360This allows the callout subsystem to transparently handle races between 361callout cancellation, 362scheduling, 363and execution. 364Note that the associated lock must be acquired before calling 365.Fn callout_stop 366or 367.Fn callout_reset 368functions to provide this safety. 369.It 370The 371.Fn callout_pending , 372.Fn callout_active 373and 374.Fn callout_deactivate 375macros can be used together to work around the race conditions, 376but the interpretation of these calls can be confusing and it 377is recommended that a different, caller-specific method be used to 378determine whether a race condition is present. 379.Pp 380When a callout's timeout is set, the callout subsystem marks the 381callout as both 382.Em active 383and 384.Em pending . 385When the timeout time arrives, the callout subsystem begins processing 386the callout by first clearing the 387.Em pending 388flag. 389It then invokes the callout function without changing the 390.Em active 391flag, and does not clear the 392.Em active 393flag even after the callout function returns. 394The mechanism described here requires the callout function itself to 395clear the 396.Em active 397flag using the 398.Fn callout_deactivate 399macro. 400The 401.Fn callout_stop 402and 403.Fn callout_drain 404functions always clear both the 405.Em active 406and 407.Em pending 408flags before returning. 409.Pp 410The callout function should first check the 411.Em pending 412flag and return without action if 413.Fn callout_pending 414returns 415.Dv TRUE . 416This indicates that the callout was rescheduled using 417.Fn callout_reset 418just before the callout function was invoked. 419If 420.Fn callout_active 421returns 422.Dv FALSE 423then the callout function should also return without action. 424This indicates that the callout has been stopped. 425Finally, the callout function should call 426.Fn callout_deactivate 427to clear the 428.Em active 429flag. 430For example: 431.Bd -literal -offset indent 432lockmgr(&sc->sc_lock, LK_EXCLUSIVE); 433if (callout_pending(&sc->sc_callout)) { 434 /* callout was reset */ 435 lockmgr(&sc->sc_lock, LK_RELEASE); 436 return; 437} 438if (!callout_active(&sc->sc_callout)) { 439 /* callout was stopped */ 440 lockmgr(&sc->sc_lock, LK_RELEASE); 441 return; 442} 443callout_deactivate(&sc->sc_callout); 444/* rest of callout function */ 445.Ed 446.Pp 447Together with appropriate synchronization, such as the lock used above, 448this approach permits the 449.Fn callout_stop 450and 451.Fn callout_reset 452functions to be used at any time without races. 453For example: 454.Bd -literal -offset indent 455lockmgr(&sc->sc_mtx, LK_EXCLUSIVE); 456callout_stop(&sc->sc_callout); 457/* The callout is effectively stopped now. */ 458.Ed 459.Pp 460If the callout is still pending then these functions operate normally, 461but if processing of the callout has already begun then the tests in 462the callout function cause it to return without further action. 463Synchronization between the callout function and other code ensures that 464stopping or resetting the callout will never be attempted while the 465callout function is past the 466.Fn callout_deactivate 467call. 468.Pp 469The above technique additionally ensures that the 470.Em active 471flag always reflects whether the callout is effectively enabled or 472disabled. 473If 474.Fn callout_active 475returns false, then the callout is effectively disabled, since even if 476the callout subsystem is actually just about to invoke the callout 477function, the callout function will return without action. 478.El 479.Pp 480There is one final race condition that must be considered when a 481callout is being stopped for the last time. 482In this case it may not be safe to let the callout function itself 483detect that the callout was stopped, since it may need to access 484data objects that have already been destroyed or recycled. 485To ensure that the callout is completely inactive, a call to 486.Fn callout_cancel 487or 488.Fn callout_terminate 489should be used. 490.Sh RETURN VALUES 491The 492.Fn callout_active 493macro returns the state of a callout's 494.Em active 495flag. 496.Pp 497The 498.Fn callout_pending 499macro returns the state of a callout's 500.Em pending 501flag. 502.Pp 503The 504.Fn callout_stop 505and 506.Fn callout_drain 507functions return a value of one if the callout was removed by the 508function, or zero if the callout could not be stopped or was not running 509in the first place. 510.Sh HISTORY 511The original work on the data structures used in this implementation 512was published by 513.An G. Varghese 514and 515.An A. Lauck 516in the paper 517.%T "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility" 518in the 519.%B "Proceedings of the 11th ACM Annual Symposium on Operating Systems Principles" . 520The current implementation replaces the long standing 521.Bx 522linked list 523callout mechanism which offered O(n) insertion and removal running time 524but did not generate or require handles for untimeout operations. 525.Pp 526In 527.Dx 528the entire API was reformulated by Matthew Dillon for optimal SMP 529operation, uses much larger rings, and is capable of queueing one 530operation concurrent with an in-progress callback without blocking. 531