1.\" Copyright (c) 2007 Julian Elischer (julian - 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND 14.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 17.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 18.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 19.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 20.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 21.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 22.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 23.\" SUCH DAMAGE. 24.\" 25.\" $FreeBSD$ 26.\" 27.Dd March 14, 2007 28.Dt LOCKING 9 29.Os 30.Sh NAME 31.Nm locking 32.Nd kernel synchronization primitives 33.Sh SYNOPSIS 34All sorts of stuff to go here. 35.Pp 36.Sh DESCRIPTION 37The 38.Em FreeBSD 39kernel is written to run across multiple CPUs and as such requires 40several different synchronization primitives to allow the developers 41to safely access and manipulate the many data types required. 42.Pp 43These include: 44.Bl -enum 45.It 46Spin Mutexes 47.It 48Sleep Mutexes 49.It 50pool Mutexes 51.It 52Shared-Exclusive locks 53.It 54Reader-Writer locks 55.It 56Read-Mostly locks 57.It 58Turnstiles 59.It 60Semaphores 61.It 62Condition variables 63.It 64Sleep/wakeup 65.It 66Giant 67.It 68Lockmanager locks 69.El 70.Pp 71The primitives interact and have a number of rules regarding how 72they can and can not be combined. 73There are too many for the average 74human mind and they keep changing. 75(if you disagree, please write replacement text) :-) 76.Pp 77Some of these primitives may be used at the low (interrupt) level and 78some may not. 79.Pp 80There are strict ordering requirements and for some of the types this 81is checked using the 82.Xr witness 4 83code. 84.Pp 85.Ss SPIN Mutexes 86Mutexes are the basic primitive. 87You either hold it or you don't. 88If you don't own it then you just spin, waiting for the holder (on 89another CPU) to release it. 90Hopefully they are doing something fast. 91You 92.Em must not 93do anything that deschedules the thread while you 94are holding a SPIN mutex. 95.Ss Mutexes 96Basically (regular) mutexes will deschedule the thread if the 97mutex can not be acquired. 98A non-spin mutex can be considered to be equivalent 99to getting a write lock on an 100.Em rw_lock 101(see below), and in fact non-spin mutexes and rw_locks may soon become the same thing. 102As in spin mutexes, you either get it or you don't. 103You may only call the 104.Xr sleep 9 105call via 106.Fn msleep 107or the new 108.Fn mtx_sleep 109variant. 110These will atomically drop the mutex and reacquire it 111as part of waking up. 112This is often however a 113.Em BAD 114idea because it generally relies on you having 115such a good knowledge of all the call graph above you 116and what assumptions it is making that there are a lot 117of ways to make hard-to-find mistakes. 118For example you MUST re-test all the assumptions you made before, 119all the way up the call graph to where you got the lock. 120You can not just assume that mtx_sleep can be inserted anywhere. 121If any caller above you has any mutex or 122rwlock, your sleep, will cause a panic. 123If the sleep only happens rarely it may be years before the 124bad code path is found. 125.Ss Pool Mutexes 126A variant of regular mutexes where the allocation of the mutex is handled 127more by the system. 128.Ss Rw_locks 129Reader/writer locks allow shared access to protected data by multiple threads, 130or exclusive access by a single thread. 131The threads with shared access are known as 132.Em readers 133since they should only read the protected data. 134A thread with exclusive access is known as a 135.Em writer 136since it may modify protected data. 137.Pp 138Although reader/writer locks look very similar to 139.Xr sx 9 140(see below) locks, their usage pattern is different. 141Reader/writer locks can be treated as mutexes (see above and 142.Xr mutex 9 ) 143with shared/exclusive semantics. 144More specifically, regular mutexes can be 145considered to be equivalent to a write-lock on an 146.Em rw_lock. 147In the future this may in fact 148become literally the fact. 149An 150.Em rw_lock 151can be locked while holding a regular mutex, but 152can 153.Em not 154be held while sleeping. 155The 156.Em rw_lock 157locks have priority propagation like mutexes, but priority 158can be propagated only to an exclusive holder. 159This limitation comes from the fact that shared owners 160are anonymous. 161Another important property is that shared holders of 162.Em rw_lock 163can recurse, but exclusive locks are not allowed to recurse. 164This ability should not be used lightly and 165.Em may go away. 166Users of recursion in any locks should be prepared to 167defend their decision against vigorous criticism. 168.Ss Rm_locks 169Mostly reader locks are similar to 170.Em Reader/write 171locks but optimized for very infrequent 172.Em writer 173locking. 174.Em rm_lock 175locks implement full priority propagation by tracking shared owners 176using a lock user supplied 177.Em tracker 178data structure. 179.Ss Sx_locks 180Shared/exclusive locks are used to protect data that are read far more often 181than they are written. 182Mutexes are inherently more efficient than shared/exclusive locks, so 183shared/exclusive locks should be used prudently. 184The main reason for using an 185.Em sx_lock 186is that a thread may hold a shared or exclusive lock on an 187.Em sx_lock 188lock while sleeping. 189As a consequence of this however, an 190.Em sx_lock 191lock may not be acquired while holding a mutex. 192The reason for this is that, if one thread slept while holding an 193.Em sx_lock 194lock while another thread blocked on the same 195.Em sx_lock 196lock after acquiring a mutex, then the second thread would effectively 197end up sleeping while holding a mutex, which is not allowed. 198The 199.Em sx_lock 200should be considered to be closely related to 201.Xr sleep 9 . 202In fact it could in some cases be 203considered a conditional sleep. 204.Ss Turnstiles 205Turnstiles are used to hold a queue of threads blocked on 206non-sleepable locks. 207Sleepable locks use condition variables to implement their queues. 208Turnstiles differ from a sleep queue in that turnstile queue's 209are assigned to a lock held by an owning thread. 210Thus, when one thread is enqueued onto a turnstile, it can lend its 211priority to the owning thread. 212If this sounds confusing, we need to describe it better. 213.Ss Semaphores 214.Ss Condition variables 215Condition variables are used in conjunction with mutexes to wait for 216conditions to occur. 217A thread must hold the mutex before calling the 218.Fn cv_wait* , 219functions. 220When a thread waits on a condition, the mutex 221is atomically released before the thread is blocked, then reacquired 222before the function call returns. 223.Ss Giant 224Giant is a special instance of a sleep lock. 225It has several special characteristics. 226.Bl -enum 227.It 228It is recursive. 229.It 230Drivers can request that Giant be locked around them, but this is 231going away. 232.It 233You can sleep while it has recursed, but other recursive locks cannot. 234.It 235Giant must be locked first before other locks. 236.It 237There are places in the kernel that drop Giant and pick it back up 238again. 239Sleep locks will do this before sleeping. 240Parts of the Network or VM code may do this as well, depending on the 241setting of a sysctl. 242This means that you cannot count on Giant keeping other code from 243running if your code sleeps, even if you want it to. 244.El 245.Ss Sleep/wakeup 246The functions 247.Fn tsleep , 248.Fn msleep , 249.Fn msleep_spin , 250.Fn pause , 251.Fn wakeup , 252and 253.Fn wakeup_one 254handle event-based thread blocking. 255If a thread must wait for an external event, it is put to sleep by 256.Fn tsleep , 257.Fn msleep , 258.Fn msleep_spin , 259or 260.Fn pause . 261Threads may also wait using one of the locking primitive sleep routines 262.Xr mtx_sleep 9 , 263.Xr rw_sleep 9 , 264or 265.Xr sx_sleep 9 . 266.Pp 267The parameter 268.Fa chan 269is an arbitrary address that uniquely identifies the event on which 270the thread is being put to sleep. 271All threads sleeping on a single 272.Fa chan 273are woken up later by 274.Fn wakeup , 275often called from inside an interrupt routine, to indicate that the 276resource the thread was blocking on is available now. 277.Pp 278Several of the sleep functions including 279.Fn msleep , 280.Fn msleep_spin , 281and the locking primitive sleep routines specify an additional lock 282parameter. 283The lock will be released before sleeping and reacquired 284before the sleep routine returns. 285If 286.Fa priority 287includes the 288.Dv PDROP 289flag, then the lock will not be reacquired before returning. 290The lock is used to ensure that a condition can be checked atomically, 291and that the current thread can be suspended without missing a 292change to the condition, or an associated wakeup. 293In addition, all of the sleep routines will fully drop the 294.Va Giant 295mutex 296(even if recursed) 297while the thread is suspended and will reacquire the 298.Va Giant 299mutex before the function returns. 300.Pp 301.Ss lockmanager locks 302Largely deprecated. 303See the 304.Xr lock 9 305page for more information. 306I don't know what the downsides are but I'm sure someone will fill in this part. 307.Sh Usage tables. 308.Ss Interaction table. 309The following table shows what you can and can not do if you hold 310one of the synchronization primitives discussed here: 311(someone who knows what they are talking about should write this table) 312.Bl -column ".Ic xxxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXX" -offset indent 313.It Xo 314.Em "You have: You want:" Ta Spin_mtx Ta Slp_mtx Ta sx_lock Ta rw_lock Ta rm_lock Ta sleep 315.Xc 316.It Ic SPIN mutex Ta \&ok-1 Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no-3 317.It Ic Sleep mutex Ta \&ok Ta \&ok-1 Ta \&no Ta \&ok Ta \&ok Ta \&no-3 318.It Ic sx_lock Ta \&ok Ta \&ok Ta \&ok-2 Ta \&ok Ta \&ok Ta \&ok-4 319.It Ic rw_lock Ta \&ok Ta \&ok Ta \&no Ta \&ok-2 Ta \&ok Ta \&no-3 320.It Ic rm_lock Ta \&ok Ta \&ok Ta \&no Ta \&ok Ta \&ok-2 Ta \&no 321.El 322.Pp 323.Em *1 324Recursion is defined per lock. 325Lock order is important. 326.Pp 327.Em *2 328readers can recurse though writers can not. 329Lock order is important. 330.Pp 331.Em *3 332There are calls atomically release this primitive when going to sleep 333and reacquire it on wakeup (e.g. 334.Fn mtx_sleep , 335.Fn rw_sleep 336and 337.Fn msleep_spin 338). 339.Pp 340.Em *4 341Though one can sleep holding an sx lock, one can also use 342.Fn sx_sleep 343which atomically release this primitive when going to sleep and 344reacquire it on wakeup. 345.Ss Context mode table. 346The next table shows what can be used in different contexts. 347At this time this is a rather easy to remember table. 348.Bl -column ".Ic Xxxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXX" -offset indent 349.It Xo 350.Em "Context:" Ta Spin_mtx Ta Slp_mtx Ta sx_lock Ta rw_lock Ta rm_lock Ta sleep 351.Xc 352.It interrupt: Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no 353.It idle: Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no 354.El 355.Sh SEE ALSO 356.Xr condvar 9 , 357.Xr lock 9 , 358.Xr mtx_pool 9 , 359.Xr mutex 9 , 360.Xr rmlock 9 , 361.Xr rwlock 9 , 362.Xr sema 9 , 363.Xr sleep 9 , 364.Xr sx 9 , 365.Xr LOCK_PROFILING 9 , 366.Xr WITNESS 9 367.Sh HISTORY 368These 369functions appeared in 370.Bsx 4.1 371through 372.Fx 7.0 373