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 56Turnstiles 57.It 58Semaphores 59.It 60Condition variables 61.It 62Sleep/wakeup 63.It 64Giant 65.It 66Lockmanager locks 67.El 68.Pp 69The primitives interact and have a number of rules regarding how 70they can and can not be combined. There are too many for the average 71human mind and they keep changing. 72(if you disagree, please write replacement text) :-) 73.Pp 74Some of these primitives may be used at the low (interrupt) level and 75some may not. 76.Pp 77There are strict ordering requirements and for some of the types this 78is checked using the 79.Xr witness 4 80code. 81.Pp 82.Ss SPIN Mutexes 83Mutexes are the basic primitive. 84You either hold it or you don't. 85If you don't own it then you just spin, waiting for the holder (on 86another CPU) to release it. 87Hopefully they are doing something fast. 88You can not do anything that deschedules the thread while you 89are holding a SPIN mutex. 90.Ss Sleep Mutexes 91Basically sleep (regular) mutexes will deschedule the thread if the 92mutex can not be acquired. 93As in spin mutexes, you either get it or you don't. 94You may call the 95.Xr sleep 9 96call 97.Fn msleep 98or the new 99.Fn mtx_sleep 100variant. These will atomically drop the mutex and reacquire it 101as part of waking up. 102.Ss Pool Mutexes 103A variant of SLEEP mutexes where the allocation of the mutex is handled 104more by the system. 105.Ss Sx_locks 106Shared/exclusive locks are used to protect data that are read far more often 107than they are written. 108Mutexes are inherently more efficient than shared/exclusive locks, so 109shared/exclusive locks should be used prudently. 110A thread may hold a shared or exclusive lock on an 111.Em sx_lock 112lock while sleeping. 113As a result, an 114.Em sx_lock 115lock may not be acquired while holding a mutex. 116Otherwise, if one thread slept while holding an 117.Em sx_lock 118lock while another thread blocked on the same 119.Em sx_lock 120lock after acquiring a mutex, then the second thread would effectively 121end up sleeping while holding a mutex, which is not allowed. 122.Ss Rw_locks 123Reader/writer locks allow shared access to protected data by multiple threads, 124or exclusive access by a single thread. 125The threads with shared access are known as 126.Em readers 127since they only read the protected data. 128A thread with exclusive access is known as a 129.Em writer 130since it can modify protected data. 131.Pp 132Although reader/writer locks look very similar to 133.Xr sx 9 134locks, their usage pattern is different. 135Reader/writer locks can be treated as mutexes (see 136.Xr mutex 9 ) 137with shared/exclusive semantics. 138Unlike 139.Xr sx 9 , 140an 141.Em rw_lock 142can be locked while holding a non-spin mutex, and an 143.Em rw_lock 144cannot be held while sleeping. 145The 146.Em rw_lock 147locks have priority propagation like mutexes, but priority 148can be propagated only to an exclusive holder. 149This limitation comes from the fact that shared owners 150are anonymous. 151Another important property is that shared holders of 152.Em rw_lock 153can recurse, 154but exclusive locks are not allowed to recurse. 155.Ss Turnstiles 156Turnstiles are used to hold a queue of threads blocked on 157non-sleepable locks. 158Sleepable locks use condition variables to implement their queues. 159Turnstiles differ from a sleep queue in that turnstile queue's 160are assigned to a lock held by an owning thread. 161Thus, when one thread is enqueued onto a turnstile, it can lend its 162priority to the owning thread. 163.Ss Semaphores 164.Ss Condition variables 165Condition variables are used in conjunction with mutexes to wait for 166conditions to occur. 167A thread must hold the mutex before calling the 168.Fn cv_wait* , 169functions. 170When a thread waits on a condition, the mutex 171is atomically released before the thread is blocked, then reacquired 172before the function call returns. 173.Ss Giant 174Giant is a special instance of a sleep lock. 175It has several special characteristics. 176.Bl -enum 177.It 178It is recursive. 179.It 180Drivers can request that Giant be locked around them, but this is 181going away. 182.It 183You can sleep while it has recursed, but other recursive locks cannot. 184.It 185Giant must be locked first. 186.It 187There are places in the kernel that drop Giant and pick it back up 188again. 189Sleep locks will do this before sleeping. 190Parts of the Network or VM code may do this as well, depending on the 191setting of a sysctl. 192This means that you cannot count on Giant keeping other code from 193running if your code sleeps, even if you want it to. 194.El 195.Ss Sleep/wakeup 196The functions 197.Fn tsleep , 198.Fn msleep , 199.Fn msleep_spin , 200.Fn pause , 201.Fn wakeup , 202and 203.Fn wakeup_one 204handle event-based thread blocking. 205If a thread must wait for an external event, it is put to sleep by 206.Fn tsleep , 207.Fn msleep , 208.Fn msleep_spin , 209or 210.Fn pause . 211Threads may also wait using one of the locking primitive sleep routines 212.Xr mtx_sleep 9 , 213.Xr rw_sleep 9 , 214or 215.Xr sx_sleep 9 . 216.Pp 217The parameter 218.Fa chan 219is an arbitrary address that uniquely identifies the event on which 220the thread is being put to sleep. 221All threads sleeping on a single 222.Fa chan 223are woken up later by 224.Fn wakeup , 225often called from inside an interrupt routine, to indicate that the 226resource the thread was blocking on is available now. 227.Pp 228Several of the sleep functions including 229.Fn msleep , 230.Fn msleep_spin , 231and the locking primitive sleep routines specify an additional lock 232parameter. 233The lock will be released before sleeping and reacquired 234before the sleep routine returns. 235If 236.Fa priority 237includes the 238.Dv PDROP 239flag, then the lock will not be reacquired before returning. 240The lock is used to ensure that a condition can be checked atomically, 241and that the current thread can be suspended without missing a 242change to the condition, or an associated wakeup. 243In addition, all of the sleep routines will fully drop the 244.Va Giant 245mutex 246(even if recursed) 247while the thread is suspended and will reacquire the 248.Va Giant 249mutex before the function returns. 250.Pp 251.Ss lockmanager locks 252Largely deprecated. See the 253.Xr lock 9 254page for more information. 255I don't know what the downsides are but I'm sure someone will fill in this part. 256.Sh Usage tables. 257.Ss Interaction table. 258The following table shows what you can and can not do if you hold 259one of the synchronization primitives discussed here: 260(someone who knows what they are talking about should write this table) 261.Bl -column ".Ic xxxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXX" -offset indent 262.It Xo 263.Em "You have: You want:" Ta Spin_mtx Ta Slp_mtx Ta sx_lock Ta rw_lock Ta sleep 264.Xc 265.It Ic SPIN mutex Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no-3 266.It Ic Sleep mutex Ta \&ok Ta \&ok-1 Ta \&no Ta \&ok Ta \&no-3 267.It Ic sx_lock Ta \&ok Ta \&no Ta \&ok-2 Ta \&no Ta \&ok-4 268.It Ic rw_lock Ta \&ok Ta \&ok Ta \&no Ta \&ok-2 Ta \&no-3 269.El 270.Pp 271.Em *1 272Recursion is defined per lock. Lock order is important. 273.Pp 274.Em *2 275readers can recurse though writers can not. Lock order is important. 276.Pp 277.Em *3 278There are calls atomically release this primitive when going to sleep 279and reacquire it on wakeup (e.g. 280.Fn mtx_sleep , 281.Fn rw_sleep 282and 283.Fn msleep_spin 284). 285.Pp 286.Em *4 287Though one can sleep holding an sx lock, one can also use 288.Fn sx_sleep 289which atomically release this primitive when going to sleep and 290reacquire it on wakeup. 291.Ss Context mode table. 292The next table shows what can be used in different contexts. 293At this time this is a rather easy to remember table. 294.Bl -column ".Ic Xxxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXX" -offset indent 295.It Xo 296.Em "Context:" Ta Spin_mtx Ta Slp_mtx Ta sx_lock Ta rw_lock Ta sleep 297.Xc 298.It interrupt: Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no 299.It idle: Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no 300.El 301.Sh SEE ALSO 302.Xr condvar 9 , 303.Xr lock 9 , 304.Xr mtx_pool 9 , 305.Xr rwlock 9 , 306.Xr sema 9 , 307.Xr sleep 9 , 308.Xr sx 9 , 309.Xr LOCK_PROFILING 9 , 310.Xr WITNESS 9 311.Sh HISTORY 312These 313functions appeared in 314.Bsx 4.1 315through 316.Fx 7.0 317