.\"	$NetBSD: timeout.9,v 1.2 1996/06/23 22:32:34 pk Exp $
.\"
.\" Copyright (c) 1996 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
.\" by Paul Kranenburg.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
.\" LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
.Dd April 15, 2022
.Dt CALLOUT 9
.Os
.Sh NAME
.Nm callout_active ,
.Nm callout_deactivate ,
.Nm callout_drain ,
.Nm callout_init ,
.Nm callout_init_mp ,
.Nm callout_init_lk ,
.Nm callout_pending ,
.Nm callout_reset ,
.Nm callout_reset_bycpu ,
.Nm callout_stop ,
.Nm callout_stop_async ,
.Nm callout_cancel ,
.Nm callout_terminate
.Nd execute a function after a specified length of time
.Sh SYNOPSIS
.In sys/types.h
.In sys/systm.h
.In sys/callout.h
.Bd -literal
typedef void timeout_t (void *);
.Ed
.Ft int
.Fn callout_active "struct callout *c"
.Ft void
.Fn callout_deactivate "struct callout *c"
.Ft int
.Fn callout_drain "struct callout *c"
.Ft void
.Fn callout_init "struct callout *c"
.Ft void
.Fn callout_init_mp "struct callout *c"
.Ft void
.Fn callout_init_lk "struct callout *c" "struct lock *lk"
.Ft int
.Fn callout_pending "struct callout *c"
.Ft void
.Fn callout_reset "struct callout *c" "int ticks" "timeout_t *func" "void *arg"
.Ft void
.Fo callout_reset_bycpu
.Fa "struct callout *c"
.Fa "int ticks"
.Fa "timeout_t *func"
.Fa "void *arg"
.Fa "int cpuid"
.Fc
.Ft int
.Fn callout_stop "struct callout *c"
.Ft int
.Fn callout_stop_async "struct callout *c"
.Ft int
.Fn callout_cancel "struct callout *c"
.Ft void
.Fn callout_terminate "struct callout *c"
.Sh DESCRIPTION
The
.Nm callout
API is used to schedule a call to an arbitrary function at a specific
time in the future.
Consumers of this API are required to allocate a callout structure
.Pq struct callout
for each pending function invocation.
This structure stores state about the pending function invocation including
the function to be called and the time at which the function should be invoked.
Pending function calls can be cancelled or rescheduled to a different time.
In addition,
a callout structure may be reused to schedule a new function call after a
scheduled call is completed.
.Pp
Callouts only provide a single-shot mode.
If a consumer requires a periodic timer,
it must explicitly reschedule each function call.
This is normally done by rescheduling the subsequent call within the called
function.
.Pp
In
.Fx
callout functions must not sleep.
They may not acquire sleepable locks,
wait on condition variables,
perform blocking allocation requests,
or invoke any other action that might sleep.
In
.Dx
all callout functions are executed from a common kernel thread on the
target CPU and may block as long as deadlocks are avoided.
But generally speaking,
callout functions should run in as short a time as possible
as they can add lag to other unrelated callouts.
.Pp
Each callout structure must be initialized by
.Fn callout_init ,
.Fn callout_init_mp ,
or
.Fn callout_init_lk
before it is passed to any of the other callout functions.
The
.Fn callout_init
and
.Fn callout_init_mp
functions initialize a callout structure in
.Fa c
that is not associated with a specific lock.
The former will hold the mplock across callback.
However, it is deprecated
and should not be used in new code.
.Fn callout_init_mp
should be used for any new code.
.Pp
The
.Fn callout_init_lk
function initialize a callout structure in
.Fa c
that is associated with a specific lock.
In
.Fx
the associated lock should be held while stopping or rescheduling the
callout.
In
.Dx
the same is true, but is not a requirement.
.Pp
The callout subsystem acquires the associated lock before calling the
callout function and releases it after the function returns.
If the callout was cancelled while the callout subsystem waited for the
associated lock,
the callout function is not called,
and the associated lock is released.
This ensures that stopping or rescheduling the callout will abort any
previously scheduled invocation.
.Pp
The function
.Fn callout_stop
cancels a callout
.Fa c
if it is currently pending.
If the callout is pending and successfully stopped, then
.Fn callout_stop
returns a value of one.
In
.Fx
if the callout is not set, or
has already been serviced, then
negative one is returned.
In
.Dx
if the callout is not set, or
has already been serviced, then
zero is returned.
If the callout is currently being serviced and cannot be stopped,
then zero will be returned.
If the callout is currently being serviced and cannot be stopped, and at the
same time a next invocation of the same callout is also scheduled, then
.Fn callout_stop
unschedules the next run and returns zero.
In
.Fx
if the callout has an associated lock,
then that lock must be held when this function is called.
In
.Dx
if the callout has an associated lock,
then that lock should be held when this function is called
to avoid races, but does not have to be.
.Pp
In
.Dx
the stop operation is guaranteed to be synchronous if the callout
was initialized with
.Fn callout_init_lk .
.Pp
The function
.Fn callout_stop_async
is identical to
.Fn callout_stop
but does not block and allows the STOP operation to be asynchronous,
meaning that the callout structure may still be relevant after the
function returns.
This situation can occur if the callback was
in-progress at the time the stop was issued.
.Pp
The function
.Fn callout_cancel
synchronously cancels a callout and returns a value similar to that
of
.Fn callout_stop .
.Fn callout_cancel
overrides all other operations while it is in-progress.
.Pp
The function
.Fn callout_terminate
synchronously cancels a callout and informs the system that the
callout structure will no longer be referenced.
This function will clear the initialization flag and any further use of
the callout structure will panic the system until it is next initialized.
The callout structure can be safely freed after this function returns,
assuming other program references to it have been removed.
.Pp
The function
.Fn callout_drain
is identical to
.Fn callout_stop
except that it will wait for the callout
.Fa c
to complete if it is already in progress.
This function MUST NOT be called while holding any
locks on which the callout might block, or deadlock will result.
Note that if the callout subsystem has already begun processing this
callout, then the callout function may be invoked before
.Fn callout_drain
returns.
However, the callout subsystem does guarantee that the callout will be
fully stopped before
.Fn callout_drain
returns.
.Pp
The
.Fn callout_reset
function schedules a future function invocation for callout
.Fa c .
If
.Fa c
already has a pending callout,
it is cancelled before the new invocation is scheduled.
In
.Fx
this function returns a value of one if a pending callout was cancelled
and zero if there was no pending callout.
If the callout has an associated lock,
then that lock must be held when any of these functions are called.
In
.Dx
this function returns void.
If the callout has an associated lock,
then that lock should generally be held when any of these functions are
called, but the API will work either way.
If a callout is already in-progress, this function's parameters will be
applied when the in-progress callback returns, if not overridden from
within the callback.
.Pp
The time at which the callout function will be invoked is determined by
the
.Fa ticks
argument.
The callout is scheduled to execute after
.Fa ticks Ns No /hz
seconds.
Non-positive values of
.Fa ticks
are silently converted to the value
.Sq 1 .
.Pp
The
.Fn callout_reset_bycpu
function schedules the callout to occur on the target CPU.
The normal
.Fn callout_reset
function schedules the callout to occur on the current CPU.
These functions accept a
.Fa func
argument which identifies the function to be called when the time expires.
It must be a pointer to a function that takes a single
.Fa void *
argument.
Upon invocation,
.Fa func
will receive
.Fa arg
as its only argument.
.Pp
The callout subsystem provides a softclock thread for each CPU in the system.
Callouts are assigned to a single CPU and are executed by the softclock thread
for that CPU.
The callouts are assigned to the current CPU or to a specific CPU
depending on the call.
.Pp
The
.Fn callout_pending ,
.Fn callout_active
and
.Fn callout_deactivate
functions provide access to the current state of the callout.
The
.Fn callout_pending
function checks whether a callout is
.Em pending ;
a callout is considered
.Em pending
when a timeout has been set but the time has not yet arrived.
Note that once the timeout time arrives and the callout subsystem
starts to process this callout,
.Fn callout_pending
will return
.Dv FALSE
even though the callout function may not have finished
.Pq or even begun
executing.
The
.Fn callout_active
function checks whether a callout is marked as
.Em active ,
and the
.Fn callout_deactivate
function clears the callout's
.Em active
flag.
The callout subsystem marks a callout as
.Em active
when a timeout is set and it clears the
.Em active
flag in
.Fn callout_stop
and
.Fn callout_drain ,
but it
.Em does not
clear it when a callout expires normally via the execution of the
callout function.
.Pp
There are two main techniques for addressing these
synchronization concerns.
The first approach is preferred as it is the simplest:
.Bl -enum -offset indent
.It
Callouts can be associated with a specific lock when they are initialized
by
.Fn callout_init_lk
When a callout is associated with a lock,
the callout subsystem acquires the lock before the callout function is
invoked.
This allows the callout subsystem to transparently handle races between
callout cancellation,
scheduling,
and execution.
Note that the associated lock must be acquired before calling
.Fn callout_stop
or
.Fn callout_reset
functions to provide this safety.
.It
The
.Fn callout_pending ,
.Fn callout_active
and
.Fn callout_deactivate
functions can be used together to work around the race conditions,
but the interpretation of these calls can be confusing and it
is recommended that a different, caller-specific method be used to
determine whether a race condition is present.
.Pp
When a callout's timeout is set, the callout subsystem marks the
callout as both
.Em active
and
.Em pending .
When the timeout time arrives, the callout subsystem begins processing
the callout by first clearing the
.Em pending
flag.
It then invokes the callout function without changing the
.Em active
flag, and does not clear the
.Em active
flag even after the callout function returns.
The mechanism described here requires the callout function itself to
clear the
.Em active
flag using
.Fn callout_deactivate .
The
.Fn callout_stop
and
.Fn callout_drain
functions always clear both the
.Em active
and
.Em pending
flags before returning.
.Pp
The callout function should first check the
.Em pending
flag and return without action if
.Fn callout_pending
returns
.Dv TRUE .
This indicates that the callout was rescheduled using
.Fn callout_reset
just before the callout function was invoked.
If
.Fn callout_active
returns
.Dv FALSE
then the callout function should also return without action.
This indicates that the callout has been stopped.
Finally, the callout function should call
.Fn callout_deactivate
to clear the
.Em active
flag.
For example:
.Bd -literal -offset indent
lockmgr(&sc->sc_lock, LK_EXCLUSIVE);
if (callout_pending(&sc->sc_callout)) {
	/* callout was reset */
	lockmgr(&sc->sc_lock, LK_RELEASE);
	return;
}
if (!callout_active(&sc->sc_callout)) {
	/* callout was stopped */
	lockmgr(&sc->sc_lock, LK_RELEASE);
	return;
}
callout_deactivate(&sc->sc_callout);
/* rest of callout function */
.Ed
.Pp
Together with appropriate synchronization, such as the lock used above,
this approach permits the
.Fn callout_stop
and
.Fn callout_reset
functions to be used at any time without races.
For example:
.Bd -literal -offset indent
lockmgr(&sc->sc_mtx, LK_EXCLUSIVE);
callout_stop(&sc->sc_callout);
/* The callout is effectively stopped now. */
.Ed
.Pp
If the callout is still pending then these functions operate normally,
but if processing of the callout has already begun then the tests in
the callout function cause it to return without further action.
Synchronization between the callout function and other code ensures that
stopping or resetting the callout will never be attempted while the
callout function is past the
.Fn callout_deactivate
call.
.Pp
The above technique additionally ensures that the
.Em active
flag always reflects whether the callout is effectively enabled or
disabled.
If
.Fn callout_active
returns false, then the callout is effectively disabled, since even if
the callout subsystem is actually just about to invoke the callout
function, the callout function will return without action.
.El
.Pp
There is one final race condition that must be considered when a
callout is being stopped for the last time.
In this case it may not be safe to let the callout function itself
detect that the callout was stopped, since it may need to access
data objects that have already been destroyed or recycled.
To ensure that the callout is completely inactive, a call to
.Fn callout_cancel
or
.Fn callout_terminate
should be used.
.Sh RETURN VALUES
The
.Fn callout_active
function returns the state of a callout's
.Em active
flag.
.Pp
The
.Fn callout_pending
function returns the state of a callout's
.Em pending
flag.
.Pp
The
.Fn callout_cancel ,
.Fn callout_stop
and
.Fn callout_drain
functions return a value of one if the callout was removed by the
function, or zero if the callout could not be stopped or was not running
in the first place.
.Sh HISTORY
The original work on the data structures used in this implementation
was published by
.An G. Varghese
and
.An A. Lauck
in the paper
.%T "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility"
in the
.%B "Proceedings of the 11th ACM Annual Symposium on Operating Systems Principles" .
The current implementation replaces the long standing
.Bx
linked list
callout mechanism which offered O(n) insertion and removal running time
but did not generate or require handles for untimeout operations.
.Pp
In
.Dx
the entire API was reformulated by Matthew Dillon for optimal SMP
operation, uses much larger rings, and is capable of queuing one
operation concurrent with an in-progress callback without blocking.