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 May 25, 2012
  28 .Dt LOCKING 9
  29 .Os
  30 .Sh NAME
  31 .Nm locking
  32 .Nd kernel synchronization primitives
  33 .Sh DESCRIPTION
  34 The
  35 .Em FreeBSD
  36 kernel is written to run across multiple CPUs and as such requires
  37 several different synchronization primitives to allow the developers
  38 to safely access and manipulate the many data types required.
  39 .Ss Mutexes
  40 Mutexes (also called "sleep mutexes") are the most commonly used
  41 synchronization primitive in the kernel.
  42 Thread acquires (locks) a mutex before accessing data shared with other
  43 threads (including interrupt threads), and releases (unlocks) it afterwards.
  44 If the mutex cannot be acquired, the thread requesting it will sleep.
  45 Mutexes fully support priority propagation.
  46 .Pp
  47 See
  48 .Xr mutex 9
  49 for details.
  50 .Ss Spin mutexes
  51 Spin mutexes are variation of basic mutexes; the main difference between
  52 the two is that spin mutexes never sleep - instead, they spin, waiting
  53 for the thread holding the lock, which runs on another CPU, to release it.
  54 Differently from ordinary mutex, spin mutexes disable interrupts when acquired.
  55 Since disabling interrupts is expensive, they are also generally slower.
  56 Spin mutexes should be used only when necessary, e.g. to protect data shared
  57 with interrupt filter code (see
  58 .Xr bus_setup_intr 9
  59 for details).
  60 .Ss Pool mutexes
  61 With most synchronization primitives, such as mutexes, programmer must
  62 provide a piece of allocated memory to hold the primitive.
  63 For example, a mutex may be embedded inside the structure it protects.
  64 Pool mutex is a variant of mutex without this requirement - to lock or unlock
  65 a pool mutex, one uses address of the structure being protected with it,
  66 not the mutex itself.
  67 Pool mutexes are seldom used.
  68 .Pp
  69 See
  70 .Xr mtx_pool 9
  71 for details.
  72 .Ss Reader/writer locks
  73 Reader/writer locks allow shared access to protected data by multiple threads,
  74 or exclusive access by a single thread.
  75 The threads with shared access are known as
  76 .Em readers
  77 since they should only read the protected data.
  78 A thread with exclusive access is known as a
  79 .Em writer
  80 since it may modify protected data.
  81 .Pp
  82 Reader/writer locks can be treated as mutexes (see above and
  83 .Xr mutex 9 )
  84 with shared/exclusive semantics.
  85 More specifically, regular mutexes can be
  86 considered to be equivalent to a write-lock on an
  87 .Em rw_lock.
  88 The
  89 .Em rw_lock
  90 locks have priority propagation like mutexes, but priority
  91 can be propagated only to an exclusive holder.
  92 This limitation comes from the fact that shared owners
  93 are anonymous.
  94 Another important property is that shared holders of
  95 .Em rw_lock
  96 can recurse, but exclusive locks are not allowed to recurse.
  97 This ability should not be used lightly and
  98 .Em may go away.
  99 .Pp
 100 See
 101 .Xr rwlock 9
 102 for details.
 103 .Ss Read-mostly locks
 104 Mostly reader locks are similar to
 105 .Em reader/writer
 106 locks but optimized for very infrequent write locking.
 107 .Em Read-mostly
 108 locks implement full priority propagation by tracking shared owners
 109 using a caller-supplied
 110 .Em tracker
 111 data structure.
 112 .Pp
 113 See
 114 .Xr rmlock 9
 115 for details.
 116 .Ss Shared/exclusive locks
 117 Shared/exclusive locks are similar to reader/writer locks; the main difference
 118 between them is that shared/exclusive locks may be held during unbounded sleep
 119 (and may thus perform an unbounded sleep).
 120 They are inherently less efficient than mutexes, reader/writer locks
 121 and read-mostly locks.
 122 They don't support priority propagation.
 123 They should be considered to be closely related to
 124 .Xr sleep 9 .
 125 In fact it could in some cases be
 126 considered a conditional sleep.
 127 .Pp
 128 See
 129 .Xr sx 9
 130 for details.
 131 .Ss Counting semaphores
 132 Counting semaphores provide a mechanism for synchronizing access
 133 to a pool of resources.
 134 Unlike mutexes, semaphores do not have the concept of an owner,
 135 so they can be useful in situations where one thread needs
 136 to acquire a resource, and another thread needs to release it.
 137 They are largely deprecated.
 138 .Pp
 139 See
 140 .Xr sema 9
 141 for details.
 142 .Ss Condition variables
 143 Condition variables are used in conjunction with mutexes to wait for
 144 conditions to occur.
 145 A thread must hold the mutex before calling the
 146 .Fn cv_wait* ,
 147 functions.
 148 When a thread waits on a condition, the mutex
 149 is atomically released before the thread is blocked, then reacquired
 150 before the function call returns.
 151 .Pp
 152 See
 153 .Xr condvar 9
 154 for details.
 155 .Ss Giant
 156 Giant is an instance of a mutex, with some special characteristics:
 157 .Bl -enum
 158 .It
 159 It is recursive.
 160 .It
 161 Drivers and filesystems can request that Giant be locked around them
 162 by not marking themselves MPSAFE.
 163 Note that infrastructure to do this is slowly going away as non-MPSAFE
 164 drivers either became properly locked or disappear.
 165 .It
 166 Giant must be locked first before other locks.
 167 .It
 168 It is OK to hold Giant while performing unbounded sleep; in such case,
 169 Giant will be dropped before sleeping and picked up after wakeup.
 170 .It
 171 There are places in the kernel that drop Giant and pick it back up
 172 again.
 173 Sleep locks will do this before sleeping.
 174 Parts of the network or VM code may do this as well, depending on the
 175 setting of a sysctl.
 176 This means that you cannot count on Giant keeping other code from
 177 running if your code sleeps, even if you want it to.
 178 .El
 179 .Ss Sleep/wakeup
 180 The functions
 181 .Fn tsleep ,
 182 .Fn msleep ,
 183 .Fn msleep_spin ,
 184 .Fn pause ,
 185 .Fn wakeup ,
 186 and
 187 .Fn wakeup_one
 188 handle event-based thread blocking.
 189 If a thread must wait for an external event, it is put to sleep by
 190 .Fn tsleep ,
 191 .Fn msleep ,
 192 .Fn msleep_spin ,
 193 or
 194 .Fn pause .
 195 Threads may also wait using one of the locking primitive sleep routines
 196 .Xr mtx_sleep 9 ,
 197 .Xr rw_sleep 9 ,
 198 or
 199 .Xr sx_sleep 9 .
 200 .Pp
 201 The parameter
 202 .Fa chan
 203 is an arbitrary address that uniquely identifies the event on which
 204 the thread is being put to sleep.
 205 All threads sleeping on a single
 206 .Fa chan
 207 are woken up later by
 208 .Fn wakeup ,
 209 often called from inside an interrupt routine, to indicate that the
 210 resource the thread was blocking on is available now.
 211 .Pp
 212 Several of the sleep functions including
 213 .Fn msleep ,
 214 .Fn msleep_spin ,
 215 and the locking primitive sleep routines specify an additional lock
 216 parameter.
 217 The lock will be released before sleeping and reacquired
 218 before the sleep routine returns.
 219 If
 220 .Fa priority
 221 includes the
 222 .Dv PDROP
 223 flag, then the lock will not be reacquired before returning.
 224 The lock is used to ensure that a condition can be checked atomically,
 225 and that the current thread can be suspended without missing a
 226 change to the condition, or an associated wakeup.
 227 In addition, all of the sleep routines will fully drop the
 228 .Va Giant
 229 mutex
 230 (even if recursed)
 231 while the thread is suspended and will reacquire the
 232 .Va Giant
 233 mutex before the function returns.
 234 .Pp
 235 See
 236 .Xr sleep 9
 237 for details.
 238 .Pp
 239 .Ss Lockmanager locks
 240 Shared/exclusive locks, used mostly in
 241 .Xr VFS 9 ,
 242 in particular as a
 243 .Xr vnode 9
 244 lock.
 245 They have features other lock types don't have, such as sleep timeout,
 246 writer starvation avoidance, draining, and interlock mutex, but this makes them
 247 complicated to implement; for this reason, they are deprecated.
 248 .Pp
 249 See
 250 .Xr lock 9
 251 for details.
 252 .Sh INTERACTIONS
 253 The primitives interact and have a number of rules regarding how
 254 they can and can not be combined.
 255 Many of these rules are checked using the
 256 .Xr witness 4
 257 code.
 258 .Ss Bounded vs. unbounded sleep
 259 The following primitives perform bounded sleep: mutexes, pool mutexes,
 260 reader/writer locks and read-mostly locks.
 261 .Pp
 262 The following primitives block (perform unbounded sleep): shared/exclusive locks,
 263 counting semaphores, condition variables, sleep/wakeup and lockmanager locks.
 264 .Pp
 265 It is an error to do any operation that could result in any kind of sleep while
 266 holding spin mutex.
 267 .Pp
 268 As a general rule, it is an error to do any operation that could result
 269 in unbounded sleep while holding any primitive from the 'bounded sleep' group.
 270 For example, it is an error to try to acquire shared/exclusive lock while
 271 holding mutex, or to try to allocate memory with M_WAITOK while holding
 272 read-write lock.
 273 .Pp
 274 As a special case, it is possible to call
 275 .Fn sleep
 276 or
 277 .Fn mtx_sleep
 278 while holding a single mutex.
 279 It will atomically drop that mutex and reacquire it as part of waking up.
 280 This is often a bad idea because it generally relies on the programmer having
 281 good knowledge of all of the call graph above the place where
 282 .Fn mtx_sleep
 283 is being called and assumptions the calling code has made.
 284 Because the lock gets dropped during sleep, one must re-test all
 285 the assumptions that were made before, all the way up the call graph to the
 286 place where the lock was acquired.
 287 .Pp
 288 It is an error to do any operation that could result in any kind of sleep when
 289 running inside an interrupt filter.
 290 .Pp
 291 It is an error to do any operation that could result in unbounded sleep when
 292 running inside an interrupt thread.
 293 .Ss Interaction table
 294 The following table shows what you can and can not do while holding
 295 one of the synchronization primitives discussed:
 296 .Bl -column ".Ic xxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXX" -offset indent
 297 .It Xo
 298 .Em "You have: You want:" Ta spin mtx Ta mutex Ta sx Ta rwlock Ta rmlock Ta sleep
 299 .Xc
 300 .It spin mtx  Ta \&ok-1 Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no-3
 301 .It mutex     Ta \&ok Ta \&ok-1 Ta \&no Ta \&ok Ta \&ok Ta \&no-3
 302 .It sx        Ta \&ok Ta \&ok Ta \&ok-2 Ta \&ok Ta \&ok Ta \&ok-4
 303 .It rwlock    Ta \&ok Ta \&ok Ta \&no Ta \&ok-2 Ta \&ok Ta \&no-3
 304 .It rmlock    Ta \&ok Ta \&ok Ta \&no-5 Ta \&ok Ta \&ok-2 Ta \&no-5
 305 .El
 306 .Pp
 307 .Em *1
 308 Recursion is defined per lock.
 309 Lock order is important.
 310 .Pp
 311 .Em *2
 312 Readers can recurse though writers can not.
 313 Lock order is important.
 314 .Pp
 315 .Em *3
 316 There are calls that atomically release this primitive when going to sleep
 317 and reacquire it on wakeup (e.g.
 318 .Fn mtx_sleep ,
 319 .Fn rw_sleep
 320 and
 321 .Fn msleep_spin ) .
 322 .Pp
 323 .Em *4
 324 Though one can sleep holding an sx lock, one can also use
 325 .Fn sx_sleep
 326 which will atomically release this primitive when going to sleep and
 327 reacquire it on wakeup.
 328 .Pp
 329 .Em *5
 330 .Em Read-mostly
 331 locks can be initialized to support sleeping while holding a write lock.
 332 See
 333 .Xr rmlock 9
 334 for details.
 335 .Ss Context mode table
 336 The next table shows what can be used in different contexts.
 337 At this time this is a rather easy to remember table.
 338 .Bl -column ".Ic Xxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXX" -offset indent
 339 .It Xo
 340 .Em "Context:"  Ta spin mtx Ta mutex Ta sx Ta rwlock Ta rmlock Ta sleep
 341 .Xc
 342 .It interrupt filter:  Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no
 343 .It interrupt thread:  Ta \&ok Ta \&ok Ta \&no Ta \&ok Ta \&ok Ta \&no
 344 .It callout:    Ta \&ok Ta \&ok Ta \&no Ta \&ok Ta \&no Ta \&no
 345 .It syscall:    Ta \&ok Ta \&ok Ta \&ok Ta \&ok Ta \&ok Ta \&ok
 346 .El
 347 .Sh SEE ALSO
 348 .Xr witness 4 ,
 349 .Xr condvar 9 ,
 350 .Xr lock 9 ,
 351 .Xr mtx_pool 9 ,
 352 .Xr mutex 9 ,
 353 .Xr rmlock 9 ,
 354 .Xr rwlock 9 ,
 355 .Xr sema 9 ,
 356 .Xr sleep 9 ,
 357 .Xr sx 9 ,
 358 .Xr BUS_SETUP_INTR 9 ,
 359 .Xr LOCK_PROFILING 9
 360 .Sh HISTORY
 361 These
 362 functions appeared in
 363 .Bsx 4.1
 364 through
 365 .Fx 7.0 .
 366 .Sh BUGS
 367 There are too many locking primitives to choose from.