A sleep queue is a structure that holds the list of threads asleep on a wait channel. Each thread that is not asleep on a wait channel carries a sleep queue structure around with it. When a thread blocks on a wait channel, it donates its sleep queue structure to that wait channel. Sleep queues associated with a wait channel are stored in a hash table.
The sleep queue hash table holds sleep queues for wait channels that have at least one blocked thread. Each entry in the hash table is called a sleepqueue chain. The chain contains a linked list of sleep queues and a spin mutex. The spin mutex protects the list of sleep queues as well as the contents of the sleep queue structures on the list. Only one sleep queue is associated with a given wait channel. If multiple threads block on a wait channel than the sleep queues associated with all but the first thread are stored on a list of free sleep queues in the master sleep queue. When a thread is removed from the sleep queue it is given one of the sleep queue structures from the master queue's free list if it is not the only thread asleep on the queue. The last thread is given the master sleep queue when it is resumed. Since threads may be removed from the sleep queue in a different order than they are added, a thread may depart from a sleep queue with a different sleep queue structure than the one it arrived with.
The sleepq_lock function locks the spin mutex of
the sleep queue chain that maps to a specific wait channel. The sleepq_lookup function looks in the hash table for the
master sleep queue associated with a given wait channel. If no master sleep queue is
found, it returns NULL. The sleepq_release function unlocks the spin mutex associated
with a given wait channel.
A thread is added to a sleep queue via the sleepq_add. This function accepts the wait channel, a
pointer to the mutex that protects the wait channel, a wait message description
string, and a mask of flags. The sleep queue chain should be locked via sleepq_lock before this function is called. If no mutex
protects the wait channel (or it is protected by Giant), then the mutex pointer
argument should be NULL. The flags argument contains a
type field that indicates the kind of sleep queue that the thread is being
added to and a flag to indicate if the sleep is interruptible (SLEEPQ_INTERRUPTIBLE). Currently there are only two types of
sleep queues: traditional sleep queues managed via the msleep and wakeup functions
(SLEEPQ_MSLEEP) and condition variable sleep queues
(SLEEPQ_CONDVAR). The sleep queue type and lock
pointer argument are used solely for internal assertion checking. Code that calls
sleepq_add should explicitly unlock any interlock
protecting the wait channel after the associated sleepqueue chain has been locked
via sleepq_lock and before blocking on the sleep
queue via one of the waiting functions.
A timeout for a sleep is set by invoking sleepq_set_timeout. The function accepts the wait channel
and the timeout time as a relative tick count as its arguments. If a sleep should be
interrupted by arriving signals, the sleepq_catch_signals function should be called as well. This
function accepts the wait channel as its only parameter. If there is already a
signal pending for this thread, then sleepq_catch_signals will return a signal number; otherwise,
it will return 0.
Once a thread has been added to a sleep queue, it blocks using one of the sleepq_wait functions. There are four wait functions
depending on whether or not the caller wishes to use a timeout or have the sleep
aborted by caught signals or an interrupt from the userland thread scheduler.
The sleepq_wait function simply waits until the
current thread is explicitly resumed by one of the wakeup functions. The sleepq_timedwait function waits until either the thread is
explicitly resumed or the timeout set by an earlier call to sleepq_set_timeout expires. The sleepq_wait_sig function waits until either the thread is
explicitly resumed or its sleep is aborted. The sleepq_timedwait_sig function waits until either the thread
is explicitly resumed, the timeout set by an earlier call to sleepq_set_timeout expires, or the thread's sleep is
aborted. All of the wait functions accept the wait channel as their first parameter.
In addition, the sleepq_timedwait_sig function
accepts a second boolean parameter to indicate if the earlier call to sleepq_catch_signals found a pending signal.
If the thread is explicitly resumed or is aborted by a signal, then a value of
zero is returned by the wait function to indicate a successful sleep. If the thread
is resumed by either a timeout or an interrupt from the userland thread
scheduler then an appropriate errno value is returned instead. Note that since
sleepq_wait can only return 0 it does not return
anything and the caller should assume a successful sleep. Also, if a thread's sleep
times out and is aborted simultaneously then sleepq_timedwait_sig will return an error indicating that a
timeout occurred. If an error value of 0 is returned and either sleepq_wait_sig or sleepq_timedwait_sig was used to block, then the function
sleepq_calc_signal_retval should be called to
check for any pending signals and calculate an appropriate return value if any are
found. The signal number returned by the earlier call to sleepq_catch_signals should be passed as the sole argument
to sleepq_calc_signal_retval.
Threads asleep on a wait channel are explicitly resumed by the sleepq_broadcast and sleepq_signal functions. Both functions accept the wait
channel from which to resume threads, a priority to raise resumed threads to, and a
flags argument to indicate which type of sleep queue is being resumed. The
priority argument is treated as a minimum priority. If a thread being resumed
already has a higher priority (numerically lower) than the priority argument then
its priority is not adjusted. The flags argument is used for internal
assertions to ensure that sleep queues are not being treated as the wrong type. For
example, the condition variable functions should not resume threads on a traditional
sleep queue. The sleepq_broadcast function
resumes all threads that are blocked on the specified wait channel while sleepq_signal only resumes the highest priority thread
blocked on the wait channel. The sleep queue chain should first be locked via the
sleepq_lock function before calling these
functions.
A sleeping thread may have its sleep interrupted by calling the sleepq_abort function. This function must be called with
sched_lock held and the thread must be queued on a
sleep queue. A thread may also be removed from a specific sleep queue via the
sleepq_remove function. This function accepts
both a thread and a wait channel as an argument and only awakens the thread if it is
on the sleep queue for the specified wait channel. If the thread is not on a sleep
queue or it is on a sleep queue for a different wait channel, then this
function does nothing.
- Compare/contrast with sleep queues.
- Lookup/wait/release. - Describe TDF_TSNOBLOCK race.
- Priority propagation.
- Should we require mutexes to be owned for mtx_destroy() since we can not safely assert that they are unowned by anyone else otherwise?
- Use a critical section...
- Describe the races with contested mutexes
- Why it is safe to read mtx_lock of a contested mutex when holding the turnstile chain lock.