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