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 September 22, 2014 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_free , 36.Nm sleepq_lock , 37.Nm sleepq_lookup , 38.Nm sleepq_release , 39.Nm sleepq_remove , 40.Nm sleepq_signal , 41.Nm sleepq_set_timeout , 42.Nm sleepq_set_timeout_sbt , 43.Nm sleepq_sleepcnt , 44.Nm sleepq_timedwait , 45.Nm sleepq_timedwait_sig , 46.Nm sleepq_type , 47.Nm sleepq_wait , 48.Nm sleepq_wait_sig 49.Nd manage the queues of sleeping threads 50.Sh SYNOPSIS 51.In sys/param.h 52.In sys/sleepqueue.h 53.Ft void 54.Fn init_sleepqueues "void" 55.Ft int 56.Fn sleepq_abort "struct thread *td" 57.Ft void 58.Fn sleepq_add "void *wchan" "struct lock_object *lock" "const char *wmesg" "int flags" "int queue" 59.Ft struct sleepqueue * 60.Fn sleepq_alloc "void" 61.Ft int 62.Fn sleepq_broadcast "void *wchan" "int flags" "int pri" "int queue" 63.Ft void 64.Fn sleepq_free "struct sleepqueue *sq" 65.Ft struct sleepqueue * 66.Fn sleepq_lookup "void *wchan" 67.Ft void 68.Fn sleepq_lock "void *wchan" 69.Ft void 70.Fn sleepq_release "void *wchan" 71.Ft void 72.Fn sleepq_remove "struct thread *td" "void *wchan" 73.Ft int 74.Fn sleepq_signal "void *wchan" "int flags" "int pri" "int queue" 75.Ft void 76.Fn sleepq_set_timeout "void *wchan" "int timo" 77.Ft void 78.Fn sleepq_set_timeout_sbt "void *wchan" "sbintime_t sbt" \ 79"sbintime_t pr" "int flags" 80.Ft u_int 81.Fn sleepq_sleepcnt "void *wchan" "int queue" 82.Ft int 83.Fn sleepq_timedwait "void *wchan" "int pri" 84.Ft int 85.Fn sleepq_timedwait_sig "void *wchan" "int pri" 86.Ft int 87.Fn sleepq_type "void *wchan" 88.Ft void 89.Fn sleepq_wait "void *wchan" "int pri" 90.Ft int 91.Fn sleepq_wait_sig "void *wchan" "int pri" 92.Sh DESCRIPTION 93Sleep queues provide a mechanism for suspending execution of a thread until 94some condition is met. 95Each queue is associated with a specific wait channel when it is active, 96and only one queue may be associated with a wait channel at any given point 97in time. 98The implementation of each wait channel splits its sleepqueue into 2 sub-queues 99in order to enable some optimizations on threads' wakeups. 100An active queue holds a list of threads that are blocked on the associated 101wait channel. 102Threads that are not blocked on a wait channel have an associated inactive 103sleep queue. 104When a thread blocks on a wait channel it donates its inactive sleep queue 105to the wait channel. 106When a thread is resumed, 107the wait channel that it was blocked on gives it an inactive sleep queue for 108later use. 109.Pp 110The 111.Fn sleepq_alloc 112function allocates an inactive sleep queue and is used to assign a 113sleep queue to a thread during thread creation. 114The 115.Fn sleepq_free 116function frees the resources associated with an inactive sleep queue and is 117used to free a queue during thread destruction. 118.Pp 119Active sleep queues are stored in a hash table hashed on the addresses pointed 120to by wait channels. 121Each bucket in the hash table contains a sleep queue chain. 122A sleep queue chain contains a spin mutex and a list of sleep queues that hash 123to that specific chain. 124Active sleep queues are protected by their chain's spin mutex. 125The 126.Fn init_sleepqueues 127function initializes the hash table of sleep queue chains. 128.Pp 129The 130.Fn sleepq_lock 131function locks the sleep queue chain associated with wait channel 132.Fa wchan . 133.Pp 134The 135.Fn sleepq_lookup 136returns a pointer to the currently active sleep queue for that wait 137channel associated with 138.Fa wchan 139or 140.Dv NULL 141if there is no active sleep queue associated with 142argument 143.Fa wchan . 144It requires the sleep queue chain associated with 145.Fa wchan 146to have been locked by a prior call to 147.Fn sleepq_lock . 148.Pp 149The 150.Fn sleepq_release 151function unlocks the sleep queue chain associated with 152.Fn wchan 153and is primarily useful when aborting a pending sleep request before one of 154the wait functions is called. 155.Pp 156The 157.Fn sleepq_add 158function places the current thread on the sleep queue associated with the 159wait channel 160.Fa wchan . 161The sleep queue chain associated with argument 162.Fa wchan 163must be locked by a prior call to 164.Fn sleepq_lock 165when this function is called. 166If a lock is specified via the 167.Fa lock 168argument, and if the kernel was compiled with 169.Cd "options INVARIANTS" , 170then the sleep queue code will perform extra checks to ensure that 171the lock is used by all threads sleeping on 172.Fa wchan . 173The 174.Fa wmesg 175parameter should be a short description of 176.Fa wchan . 177The 178.Fa flags 179parameter is a bitmask consisting of the type of sleep queue being slept on 180and zero or more optional flags. 181The 182.Fa queue 183parameter specifies the sub-queue, in which the contending thread will be 184inserted. 185.Pp 186There are currently three types of sleep queues: 187.Pp 188.Bl -tag -width ".Dv SLEEPQ_CONDVAR" -compact 189.It Dv SLEEPQ_CONDVAR 190A sleep queue used to implement condition variables. 191.It Dv SLEEPQ_SLEEP 192A sleep queue used to implement 193.Xr sleep 9 , 194.Xr wakeup 9 195and 196.Xr wakeup_one 9 . 197.It Dv SLEEPQ_PAUSE 198A sleep queue used to implement 199.Xr pause 9 . 200.El 201.Pp 202There are currently two optional flag: 203.Pp 204.Bl -tag -width ".Dv SLEEPQ_INTERRUPTIBLE" -compact 205.It Dv SLEEPQ_INTERRUPTIBLE 206The current thread is entering an interruptible sleep. 207.El 208.Bl -tag -width ".Dv SLEEPQ_STOP_ON_BDRY" -compact 209.It Dv SLEEPQ_STOP_ON_BDRY 210When thread is entering an interruptible sleep, do not stop it upon 211arrival of stop action, like 212.Dv SIGSTOP . 213Wake it up instead. 214.El 215.Pp 216A timeout on the sleep may be specified by calling 217.Fn sleepq_set_timeout 218after 219.Fn sleepq_add . 220The 221.Fa wchan 222parameter should be the same value from the preceding call to 223.Fn sleepq_add , 224and the sleep queue chain associated with 225.Fa wchan 226must have been locked by a prior call to 227.Fn sleepq_lock . 228The 229.Fa timo 230parameter should specify the timeout value in ticks. 231.Pp 232.Fn sleepq_set_timeout_sbt 233function takes 234.Fa sbt 235argument instead of 236.Fa timo . 237It allows to specify relative or absolute wakeup time with higher resolution 238in form of 239.Vt sbintime_t . 240The parameter 241.Fa pr 242allows to specify wanted absolute event precision. 243The parameter 244.Fa flags 245allows to pass additional 246.Fn callout_reset_sbt 247flags. 248.Pp 249Once the thread is ready to suspend, 250one of the wait functions is called to put the current thread to sleep 251until it is awakened and to context switch to another thread. 252The 253.Fn sleepq_wait 254function is used for non-interruptible sleeps that do not have a timeout. 255The 256.Fn sleepq_timedwait 257function is used for non-interruptible sleeps that have had a timeout set via 258.Fn sleepq_set_timeout . 259The 260.Fn sleepq_wait_sig 261function is used for interruptible sleeps that do not have a timeout. 262The 263.Fn sleepq_timedwait_sig 264function is used for interruptible sleeps that do have a timeout set. 265The 266.Fa wchan 267argument to all of the wait functions is the wait channel being slept 268on. 269The sleep queue chain associated with argument 270.Fa wchan 271needs to have been locked with a prior call to 272.Fn sleepq_lock . 273The 274.Fa pri 275argument is used to set the priority of the thread when it is awakened. 276If it is set to zero, the thread's priority is left alone. 277.Pp 278When the thread is resumed, 279the wait functions return a non-zero value if the thread was awakened due to 280an interrupt other than a signal or a timeout. 281If the sleep timed out, then 282.Er EWOULDBLOCK 283is returned. 284If the sleep was interrupted by something other than a signal, 285then some other return value will be returned. 286.Pp 287A sleeping thread is normally resumed by the 288.Fn sleepq_broadcast 289and 290.Fn sleepq_signal 291functions. 292The 293.Fn sleepq_signal 294function awakens the highest priority thread sleeping on a wait channel while 295.Fn sleepq_broadcast 296awakens all of the threads sleeping on a wait channel. 297The 298.Fa wchan 299argument specifics which wait channel to awaken. 300The 301.Fa flags 302argument must match the sleep queue type contained in the 303.Fa flags 304argument passed to 305.Fn sleepq_add 306by the threads sleeping on the wait channel. 307If the 308.Fa pri 309argument does not equal \-1, 310then each thread that is awakened will have its priority raised to 311.Fa pri 312if it has a lower priority. 313The sleep queue chain associated with argument 314.Fa wchan 315must be locked by a prior call to 316.Fn sleepq_lock 317before calling any of these functions. 318The 319.Fa queue 320argument specifies the sub-queue, from which threads need to be woken up. 321.Pp 322A thread in an interruptible sleep can be interrupted by another thread via 323the 324.Fn sleepq_abort 325function. 326The 327.Fa td 328argument specifies the thread to interrupt. 329An individual thread can also be awakened from sleeping on a specific wait 330channel via the 331.Fn sleepq_remove 332function. 333The 334.Fa td 335argument specifies the thread to awaken and the 336.Fa wchan 337argument specifies the wait channel to awaken it from. 338If the thread 339.Fa td 340is not blocked on the wait channel 341.Fa wchan 342then this function will not do anything, 343even if the thread is asleep on a different wait channel. 344This function should only be used if one of the other functions above is not 345sufficient. 346One possible use is waking up a specific thread from a widely shared sleep 347channel. 348.Pp 349The 350.Fn sleepq_sleepcnt 351function offer a simple way to retrieve the number of threads sleeping for 352the specified 353.Fa queue , 354given a 355.Fa wchan . 356.Pp 357The 358.Fn sleepq_type 359function returns the type of 360.Fa wchan 361associated to a sleepqueue. 362.Pp 363The 364.Fn sleepq_abort , 365.Fn sleepq_broadcast , 366and 367.Fn sleepq_signal 368functions all return a boolean value. 369If the return value is true, 370then at least one thread was resumed that is currently swapped out. 371The caller is responsible for awakening the scheduler process so that the 372resumed thread will be swapped back in. 373This is done by calling the 374.Fn kick_proc0 375function after releasing the sleep queue chain lock via a call to 376.Fn sleepq_release . 377.Pp 378The sleep queue interface is currently used to implement the 379.Xr sleep 9 380and 381.Xr condvar 9 382interfaces. 383Almost all other code in the kernel should use one of those interfaces rather 384than manipulating sleep queues directly. 385.Sh SEE ALSO 386.Xr condvar 9 , 387.Xr runqueue 9 , 388.Xr scheduler 9 , 389.Xr sleep 9 , 390.Xr timeout 9 391