share/man/man9/locking.9

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