1.\" Copyright (c) 2000-2004 John H. Baldwin <jhb@FreeBSD.org> 2.\" All rights reserved. 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 7.\" 1. Redistributions of source code must retain the above copyright 8.\" notice, this list of conditions and the following disclaimer. 9.\" 2. Redistributions in binary form must reproduce the above copyright 10.\" notice, this list of conditions and the following disclaimer in the 11.\" documentation and/or other materials provided with the distribution. 12.\" 13.\" THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY EXPRESS OR 14.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 15.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 16.\" IN NO EVENT SHALL THE DEVELOPERS BE LIABLE FOR ANY DIRECT, INDIRECT, 17.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 18.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 19.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 20.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 22.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23.\" 24.\" $FreeBSD$ 25.\" 26.Dd February 19, 2013 27.Dt SLEEPQUEUE 9 28.Os 29.Sh NAME 30.Nm init_sleepqueues , 31.Nm sleepq_abort , 32.Nm sleepq_add , 33.Nm sleepq_alloc , 34.Nm sleepq_broadcast , 35.Nm sleepq_calc_signal_retval , 36.Nm sleepq_catch_signals , 37.Nm sleepq_free , 38.Nm sleepq_lock , 39.Nm sleepq_lookup , 40.Nm sleepq_release , 41.Nm sleepq_remove , 42.Nm sleepq_signal , 43.Nm sleepq_set_timeout , 44.Nm sleepq_set_timeout_sbt , 45.Nm sleepq_sleepcnt , 46.Nm sleepq_timedwait , 47.Nm sleepq_timedwait_sig , 48.Nm sleepq_type , 49.Nm sleepq_wait , 50.Nm sleepq_wait_sig 51.Nd manage the queues of sleeping threads 52.Sh SYNOPSIS 53.In sys/param.h 54.In sys/sleepqueue.h 55.Ft void 56.Fn init_sleepqueues "void" 57.Ft int 58.Fn sleepq_abort "struct thread *td" 59.Ft void 60.Fn sleepq_add "void *wchan" "struct lock_object *lock" "const char *wmesg" "int flags" "int queue" 61.Ft struct sleepqueue * 62.Fn sleepq_alloc "void" 63.Ft int 64.Fn sleepq_broadcast "void *wchan" "int flags" "int pri" "int queue" 65.Ft int 66.Fn sleepq_calc_signal_retval "int sig" 67.Ft int 68.Fn sleepq_catch_signals "void *wchan" 69.Ft void 70.Fn sleepq_free "struct sleepqueue *sq" 71.Ft struct sleepqueue * 72.Fn sleepq_lookup "void *wchan" 73.Ft void 74.Fn sleepq_lock "void *wchan" 75.Ft void 76.Fn sleepq_release "void *wchan" 77.Ft void 78.Fn sleepq_remove "struct thread *td" "void *wchan" 79.Ft int 80.Fn sleepq_signal "void *wchan" "int flags" "int pri" "int queue" 81.Ft void 82.Fn sleepq_set_timeout "void *wchan" "int timo" 83.Ft void 84.Fn sleepq_set_timeout_sbt "void *wchan" "sbintime_t sbt" \ 85"sbintime_t pr" "int flags" 86.Ft u_int 87.Fn sleepq_sleepcnt "void *wchan" "int queue" 88.Ft int 89.Fn sleepq_timedwait "void *wchan" 90.Ft int 91.Fn sleepq_timedwait_sig "void *wchan" "int signal_caught" 92.Ft int 93.Fn sleepq_type "void *wchan" 94.Ft void 95.Fn sleepq_wait "void *wchan" 96.Ft int 97.Fn sleepq_wait_sig "void *wchan" 98.Sh DESCRIPTION 99Sleep queues provide a mechanism for suspending execution of a thread until 100some condition is met. 101Each queue is associated with a specific wait channel when it is active, 102and only one queue may be associated with a wait channel at any given point 103in time. 104The implementation of each wait channel splits its sleepqueue into 2 sub-queues 105in order to enable some optimizations on threads' wakeups. 106An active queue holds a list of threads that are blocked on the associated 107wait channel. 108Threads that are not blocked on a wait channel have an associated inactive 109sleep queue. 110When a thread blocks on a wait channel it donates its inactive sleep queue 111to the wait channel. 112When a thread is resumed, 113the wait channel that it was blocked on gives it an inactive sleep queue for 114later use. 115.Pp 116The 117.Fn sleepq_alloc 118function allocates an inactive sleep queue and is used to assign a 119sleep queue to a thread during thread creation. 120The 121.Fn sleepq_free 122function frees the resources associated with an inactive sleep queue and is 123used to free a queue during thread destruction. 124.Pp 125Active sleep queues are stored in a hash table hashed on the addresses pointed 126to by wait channels. 127Each bucket in the hash table contains a sleep queue chain. 128A sleep queue chain contains a spin mutex and a list of sleep queues that hash 129to that specific chain. 130Active sleep queues are protected by their chain's spin mutex. 131The 132.Fn init_sleepqueues 133function initializes the hash table of sleep queue chains. 134.Pp 135The 136.Fn sleepq_lock 137function locks the sleep queue chain associated with wait channel 138.Fa wchan . 139.Pp 140The 141.Fn sleepq_lookup 142returns a pointer to the currently active sleep queue for that wait 143channel associated with 144.Fa wchan 145or 146.Dv NULL 147if there is no active sleep queue associated with 148argument 149.Fa wchan . 150It requires the sleep queue chain associated with 151.Fa wchan 152to have been locked by a prior call to 153.Fn sleepq_lock . 154.Pp 155The 156.Fn sleepq_release 157function unlocks the sleep queue chain associated with 158.Fn wchan 159and is primarily useful when aborting a pending sleep request before one of 160the wait functions is called. 161.Pp 162The 163.Fn sleepq_add 164function places the current thread on the sleep queue associated with the 165wait channel 166.Fa wchan . 167The sleep queue chain associated with argument 168.Fa wchan 169must be locked by a prior call to 170.Fn sleepq_lock 171when this function is called. 172If a lock is specified via the 173.Fa lock 174argument, and if the kernel was compiled with 175.Cd "options INVARIANTS" , 176then the sleep queue code will perform extra checks to ensure that 177the lock is used by all threads sleeping on 178.Fa wchan . 179The 180.Fa wmesg 181parameter should be a short description of 182.Fa wchan . 183The 184.Fa flags 185parameter is a bitmask consisting of the type of sleep queue being slept on 186and zero or more optional flags. 187The 188.Fa queue 189parameter specifies the sub-queue, in which the contending thread will be 190inserted. 191.Pp 192There are currently three types of sleep queues: 193.Pp 194.Bl -tag -width ".Dv SLEEPQ_CONDVAR" -compact 195.It Dv SLEEPQ_CONDVAR 196A sleep queue used to implement condition variables. 197.It Dv SLEEPQ_SLEEP 198A sleep queue used to implement 199.Xr sleep 9 , 200.Xr wakeup 9 201and 202.Xr wakeup_one 9 . 203.It Dv SLEEPQ_PAUSE 204A sleep queue used to implement 205.Xr pause 9 . 206.El 207.Pp 208There are currently two optional flag: 209.Pp 210.Bl -tag -width ".Dv SLEEPQ_INTERRUPTIBLE" -compact 211.It Dv SLEEPQ_INTERRUPTIBLE 212The current thread is entering an interruptible sleep. 213.El 214.Bl -tag -width ".Dv SLEEPQ_STOP_ON_BDRY" -compact 215.It Dv SLEEPQ_STOP_ON_BDRY 216When thread is entering an interruptible sleep, do not stop it upon 217arrival of stop action, like 218.Dv SIGSTOP . 219Wake it up instead. 220.El 221.Pp 222A timeout on the sleep may be specified by calling 223.Fn sleepq_set_timeout 224after 225.Fn sleepq_add . 226The 227.Fa wchan 228parameter should be the same value from the preceding call to 229.Fn sleepq_add , 230and the sleep queue chain associated with 231.Fa wchan 232must have been locked by a prior call to 233.Fn sleepq_lock . 234The 235.Fa timo 236parameter should specify the timeout value in ticks. 237.Pp 238.Fn sleepq_set_timeout_sbt 239function takes 240.Fa sbt 241argument instead of 242.Fa timo . 243It allows to specify relative or absolute wakeup time with higher resolution 244in form of 245.Vt sbintime_t . 246The parameter 247.Fa pr 248allows to specify wanted absolute event precision. 249The parameter 250.Fa flags 251allows to pass additional 252.Fn callout_reset_sbt 253flags. 254.Pp 255The current thread may be marked interruptible by calling 256.Fn sleepq_catch_signals 257with 258.Fa wchan 259set to the wait channel. 260This function returns a signal number if there are any pending signals for 261the current thread and 0 if there is not a pending signal. 262The sleep queue chain associated with argument 263.Fa wchan 264should have been locked by a prior call to 265.Fn sleepq_lock . 266.Pp 267Once the thread is ready to suspend, 268one of the wait functions is called to put the current thread to sleep 269until it is awakened and to context switch to another thread. 270The 271.Fn sleepq_wait 272function is used for non-interruptible sleeps that do not have a timeout. 273The 274.Fn sleepq_timedwait 275function is used for non-interruptible sleeps that have had a timeout set via 276.Fn sleepq_set_timeout . 277The 278.Fn sleepq_wait_sig 279function is used for interruptible sleeps that do not have a timeout. 280The 281.Fn sleepq_timedwait_sig 282function is used for interruptible sleeps that do have a timeout set. 283The 284.Fa wchan 285argument to all of the wait functions is the wait channel being slept 286on. 287The sleep queue chain associated with argument 288.Fa wchan 289needs to have been locked with a prior call to 290.Fn sleepq_lock . 291The 292.Fa signal_caught 293parameter to 294.Fn sleepq_timedwait_sig 295specifies if a previous call to 296.Fn sleepq_catch_signals 297found a pending signal. 298.Pp 299When the thread is resumed, 300the wait functions return a non-zero value if the thread was awakened due to 301an interrupt other than a signal or a timeout. 302If the sleep timed out, then 303.Er EWOULDBLOCK 304is returned. 305If the sleep was interrupted by something other than a signal, 306then some other return value will be returned. 307If zero is returned after resuming from an interruptible sleep, 308then 309.Fn sleepq_calc_signal_retval 310should be called to determine if the sleep was interrupted by a signal. 311If so, 312.Fn sleepq_calc_signal_retval 313returns 314.Er ERESTART 315if the interrupting signal is restartable and 316.Er EINTR 317otherwise. 318If the sleep was not interrupted by a signal, 319.Fn sleepq_calc_signal_retval 320will return 0. 321.Pp 322A sleeping thread is normally resumed by the 323.Fn sleepq_broadcast 324and 325.Fn sleepq_signal 326functions. 327The 328.Fn sleepq_signal 329function awakens the highest priority thread sleeping on a wait channel while 330.Fn sleepq_broadcast 331awakens all of the threads sleeping on a wait channel. 332The 333.Fa wchan 334argument specifics which wait channel to awaken. 335The 336.Fa flags 337argument must match the sleep queue type contained in the 338.Fa flags 339argument passed to 340.Fn sleepq_add 341by the threads sleeping on the wait channel. 342If the 343.Fa pri 344argument does not equal \-1, 345then each thread that is awakened will have its priority raised to 346.Fa pri 347if it has a lower priority. 348The sleep queue chain associated with argument 349.Fa wchan 350must be locked by a prior call to 351.Fn sleepq_lock 352before calling any of these functions. 353The 354.Fa queue 355argument specifies the sub-queue, from which threads need to be woken up. 356.Pp 357A thread in an interruptible sleep can be interrupted by another thread via 358the 359.Fn sleepq_abort 360function. 361The 362.Fa td 363argument specifies the thread to interrupt. 364An individual thread can also be awakened from sleeping on a specific wait 365channel via the 366.Fn sleepq_remove 367function. 368The 369.Fa td 370argument specifies the thread to awaken and the 371.Fa wchan 372argument specifies the wait channel to awaken it from. 373If the thread 374.Fa td 375is not blocked on the wait channel 376.Fa wchan 377then this function will not do anything, 378even if the thread is asleep on a different wait channel. 379This function should only be used if one of the other functions above is not 380sufficient. 381One possible use is waking up a specific thread from a widely shared sleep 382channel. 383.Pp 384The 385.Fn sleepq_sleepcnt 386function offer a simple way to retrieve the number of threads sleeping for 387the specified 388.Fa queue , 389given a 390.Fa wchan . 391.Pp 392The 393.Fn sleepq_type 394function returns the type of 395.Fa wchan 396associated to a sleepqueue. 397.Pp 398The 399.Fn sleepq_abort , 400.Fn sleepq_broadcast , 401and 402.Fn sleepq_signal 403functions all return a boolean value. 404If the return value is true, 405then at least one thread was resumed that is currently swapped out. 406The caller is responsible for awakening the scheduler process so that the 407resumed thread will be swapped back in. 408This is done by calling the 409.Fn kick_proc0 410function after releasing the sleep queue chain lock via a call to 411.Fn sleepq_release . 412.Pp 413The sleep queue interface is currently used to implement the 414.Xr sleep 9 415and 416.Xr condvar 9 417interfaces. 418Almost all other code in the kernel should use one of those interfaces rather 419than manipulating sleep queues directly. 420.Sh SEE ALSO 421.Xr condvar 9 , 422.Xr runqueue 9 , 423.Xr scheduler 9 , 424.Xr sleep 9 , 425.Xr timeout 9 426