MFC r203122:

Improve descriptions, remove turnstiles (since, from what I understand,
they are only used to implement other synchronization primitives), tweak
formatting.

MFC r203127:

Add description of bounded sleep vs unbounded sleep (aka blocking).  Move
rules into their own section.

MFC r203131:

Cosmetic fixes.

MFC r203759:

Improve description for Giant and mention blocking inside interrupt threads.

MFC r203762:

Start sentences with a new line.

Submitted by:	brueffer

MFC r203825:

Remove list of locking primitives, which is kind of redundant, move
information about witness(9) to the section about interactions, and
expand 'contexts' table.

MFC r203929:

Some rewording and language fixes.

PR:		docs/136918, docs/134074
Submitted by:	Ben Kaduk <kaduk at mit dot edu>, Haven Hash <havenster at gmail dot com>

1 files changed, 163 insertions, 175 deletions

diff --git a/share/man/man9/locking.9 b/share/man/man9/locking.9
index 825eb7f..8457e25 100644
--- a/share/man/man9/locking.9
+++ b/share/man/man9/locking.9
@@ -24,108 +24,52 @@
 .\"
 .\" $FreeBSD$
 .\"
-.Dd March 14, 2007
+.Dd February 15, 2010
 .Dt LOCKING 9
 .Os
 .Sh NAME
 .Nm locking
 .Nd kernel synchronization primitives
-.Sh SYNOPSIS
-All sorts of stuff to go here.
-.Pp
 .Sh DESCRIPTION
 The
 .Em FreeBSD
 kernel is written to run across multiple CPUs and as such requires
 several different synchronization primitives to allow the developers
 to safely access and manipulate the many data types required.
+.Ss Mutexes
+Mutexes (also called "sleep mutexes") are the most commonly used
+synchronization primitive in the kernel.
+Thread acquires (locks) a mutex before accessing data shared with other
+threads (including interrupt threads), and releases (unlocks) it afterwards.
+If the mutex cannot be acquired, the thread requesting it will sleep.
+Mutexes fully support priority propagation.
 .Pp
-These include:
-.Bl -enum
-.It
-Spin Mutexes
-.It
-Sleep Mutexes
-.It
-pool Mutexes
-.It
-Shared-Exclusive locks
-.It
-Reader-Writer locks
-.It
-Read-Mostly locks
-.It
-Turnstiles
-.It
-Semaphores
-.It
-Condition variables
-.It
-Sleep/wakeup
-.It
-Giant
-.It
-Lockmanager locks
-.El
-.Pp
-The primitives interact and have a number of rules regarding how
-they can and can not be combined.
-There are too many for the average
-human mind and they keep changing.
-(if you disagree, please write replacement text)  :-)
-.Pp
-Some of these primitives may be used at the low (interrupt) level and
-some may not.
-.Pp
-There are strict ordering requirements and for some of the types this
-is checked using the
-.Xr witness 4
-code.
+See
+.Xr mutex 9
+for details.
+.Ss Spin mutexes
+Spin mutexes are variation of basic mutexes; the main difference between
+the two is that spin mutexes never sleep - instead, they spin, waiting
+for the thread holding the lock, which runs on another CPU, to release it.
+Differently from ordinary mutex, spin mutexes disable interrupts when acquired.
+Since disabling interrupts is expensive, they are also generally slower.
+Spin mutexes should be used only when neccessary, e.g. to protect data shared
+with interrupt filter code (see
+.Xr bus_setup_intr 9
+for details).
+.Ss Pool mutexes
+With most synchronisaton primitives, such as mutexes, programmer must
+provide a piece of allocated memory to hold the primitive.
+For example, a mutex may be embedded inside the structure it protects.
+Pool mutex is a variant of mutex without this requirement - to lock or unlock
+a pool mutex, one uses address of the structure being protected with it,
+not the mutex itself.
+Pool mutexes are seldom used.
 .Pp
-.Ss SPIN Mutexes
-Mutexes are the basic primitive.
-You either hold it or you don't.
-If you don't own it then you just spin, waiting for the holder (on
-another CPU) to release it.
-Hopefully they are doing something fast.
-You 
-.Em must not
-do anything that deschedules the thread while you
-are holding a SPIN mutex.
-.Ss Mutexes
-Basically (regular) mutexes will deschedule the thread if the
-mutex can not be acquired.
-A non-spin mutex can be considered to be equivalent
-to getting a write lock on an 
-.Em rw_lock
-(see below), and in fact non-spin mutexes and rw_locks may soon become the same thing.
-As in spin mutexes, you either get it or you don't.
-You may only call the
-.Xr sleep 9
-call via
-.Fn msleep
-or the new
-.Fn mtx_sleep
-variant.
-These will atomically drop the mutex and reacquire it
-as part of waking up.
-This is often however a
-.Em BAD
-idea because it generally relies on you having
-such a good knowledge of all the call graph above you
-and what assumptions it is making that there are a lot
-of ways to make hard-to-find mistakes.
-For example you MUST re-test all the assumptions you made before,
-all the way up the call graph to where you got the lock.
-You can not just assume that mtx_sleep can be inserted anywhere.
-If any caller above you has any mutex or
-rwlock, your sleep, will cause a panic.
-If the sleep only happens rarely it may be years before the 
-bad code path is found.
-.Ss Pool Mutexes
-A variant of regular mutexes where the allocation of the mutex is handled
-more by the system.
-.Ss Rw_locks
+See
+.Xr mtx_pool 9
+for details.
+.Ss Reader/writer locks
 Reader/writer locks allow shared access to protected data by multiple threads,
 or exclusive access by a single thread.
 The threads with shared access are known as
@@ -135,23 +79,12 @@ A thread with exclusive access is known as a
 .Em writer
 since it may modify protected data.
 .Pp
-Although reader/writer locks look very similar to
-.Xr sx 9
-(see below) locks, their usage pattern is different.
 Reader/writer locks can be treated as mutexes (see above and
 .Xr mutex 9 )
 with shared/exclusive semantics.
 More specifically, regular mutexes can be 
 considered to be equivalent to a write-lock on an
 .Em rw_lock.
-In the future this may in fact
-become literally the fact.
-An
-.Em rw_lock
-can be locked while holding a regular mutex, but 
-can
-.Em not
-be held while sleeping.
 The
 .Em rw_lock
 locks have priority propagation like mutexes, but priority
@@ -163,54 +96,49 @@ Another important property is that shared holders of
 can recurse, but exclusive locks are not allowed to recurse.
 This ability should not be used lightly and 
 .Em may go away.
-Users of recursion in any locks should be prepared to 
-defend their decision against vigorous criticism.
-.Ss Rm_locks
+.Pp
+See
+.Xr rwlock 9
+for details.
+.Ss Read-mostly locks
 Mostly reader locks are similar to
-.Em Reader/write
-locks but optimized for very infrequent 
-.Em writer
-locking.
-.Em rm_lock
+.Em reader/writer
+locks but optimized for very infrequent write locking.
+.Em Read-mostly
 locks implement full priority propagation by tracking shared owners
-using a lock user supplied
+using a caller-supplied
 .Em tracker
 data structure.
-.Ss Sx_locks
-Shared/exclusive locks are used to protect data that are read far more often
-than they are written.
-Mutexes are inherently more efficient than shared/exclusive locks, so
-shared/exclusive locks should be used prudently.
-The main reason for using an
-.Em sx_lock
-is that a thread may hold a shared or exclusive lock on an
-.Em sx_lock
-lock while sleeping.
-As a consequence of this however, an
-.Em sx_lock
-lock may not be acquired while holding a mutex.
-The reason for this is that, if one thread slept while holding an
-.Em sx_lock
-lock while another thread blocked on the same
-.Em sx_lock
-lock after acquiring a mutex, then the second thread would effectively
-end up sleeping while holding a mutex, which is not allowed.
-The
-.Em sx_lock
-should be considered to be closely related to
+.Pp
+See
+.Xr rmlock 9
+for details.
+.Ss Shared/exclusive locks
+Shared/exclusive locks are similar to reader/writer locks; the main difference
+between them is that shared/exclusive locks may be held during unbounded sleep
+(and may thus perform an unbounded sleep).
+They are inherently less efficient than mutexes, reader/writer locks
+and read-mostly locks.
+They don't support priority propagation.
+They should be considered to be closely related to
 .Xr sleep 9 .
 In fact it could in some cases be 
 considered a conditional sleep.
-.Ss Turnstiles
-Turnstiles are used to hold a queue of threads blocked on
-non-sleepable locks.
-Sleepable locks use condition variables to implement their queues.
-Turnstiles differ from a sleep queue in that turnstile queue's
-are assigned to a lock held by an owning thread.
-Thus, when one thread is enqueued onto a turnstile, it can lend its
-priority to the owning thread.
-If this sounds confusing, we need to describe it better.
-.Ss Semaphores
+.Pp
+See
+.Xr sx 9
+for details.
+.Ss Counting semaphores
+Counting semaphores provide a mechanism for synchronizing access
+to a pool of resources.
+Unlike mutexes, semaphores do not have the concept of an owner,
+so they can be useful in situations where one thread needs
+to acquire a resource, and another thread needs to release it.
+They are largely deprecated.
+.Pp
+See
+.Xr sema 9
+for details.
 .Ss Condition variables
 Condition variables are used in conjunction with mutexes to wait for
 conditions to occur.
@@ -220,24 +148,30 @@ functions.
 When a thread waits on a condition, the mutex
 is atomically released before the thread is blocked, then reacquired
 before the function call returns.
+.Pp
+See
+.Xr condvar 9
+for details.
 .Ss Giant
-Giant is a special instance of a sleep lock.
-It has several special characteristics.
+Giant is an instance of a mutex, with some special characteristics:
 .Bl -enum
 .It
 It is recursive.
 .It
-Drivers can request that Giant be locked around them, but this is
-going away.
-.It
-You can sleep while it has recursed, but other recursive locks cannot.
+Drivers and filesystems can request that Giant be locked around them
+by not marking themselves MPSAFE.
+Note that infrastructure to do this is slowly going away as non-MPSAFE
+drivers either became properly locked or disappear.
 .It
 Giant must be locked first before other locks.
 .It
+It is OK to hold Giant while performing unbounded sleep; in such case,
+Giant will be dropped before sleeping and picked up after wakeup.
+.It
 There are places in the kernel that drop Giant and pick it back up
 again.
 Sleep locks will do this before sleeping.
-Parts of the Network or VM code may do this as well, depending on the
+Parts of the network or VM code may do this as well, depending on the
 setting of a sysctl.
 This means that you cannot count on Giant keeping other code from
 running if your code sleeps, even if you want it to.
@@ -298,26 +232,76 @@ while the thread is suspended and will reacquire the
 .Va Giant
 mutex before the function returns.
 .Pp
-.Ss lockmanager locks
-Largely deprecated.
-See the
+See
+.Xr sleep 9
+for details.
+.Pp
+.Ss Lockmanager locks
+Shared/exclusive locks, used mostly in
+.Xr VFS 9 ,
+in particular as a
+.Xr vnode 9
+lock.
+They have features other lock types don't have, such as sleep timeout,
+writer starvation avoidance, draining, and interlock mutex, but this makes them
+complicated to implement; for this reason, they are deprecated.
+.Pp
+See
 .Xr lock 9
-page for more information.
-I don't know what the downsides are but I'm sure someone will fill in this part.
-.Sh Usage tables.
-.Ss Interaction table.
-The following table shows what you can and can not do if you hold
-one of the synchronization primitives discussed here:
-(someone who knows what they are talking about should write this table)
-.Bl -column ".Ic xxxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXX" -offset indent
+for details.
+.Sh INTERACTIONS
+The primitives interact and have a number of rules regarding how
+they can and can not be combined.
+Many of these rules are checked using the
+.Xr witness 4
+code.
+.Ss Bounded vs. unbounded sleep
+The following primitives perform bounded sleep: mutexes, pool mutexes,
+reader/writer locks and read-mostly locks.
+.Pp
+The following primitives block (perform unbounded sleep): shared/exclusive locks,
+counting semaphores, condition variables, sleep/wakeup and lockmanager locks.
+.Pp
+It is an error to do any operation that could result in any kind of sleep while
+holding spin mutex.
+.Pp
+As a general rule, it is an error to do any operation that could result
+in unbounded sleep while holding any primitive from the 'bounded sleep' group.
+For example, it is an error to try to acquire shared/exclusive lock while
+holding mutex, or to try to allocate memory with M_WAITOK while holding
+read-write lock.
+.Pp
+As a special case, it is possible to call
+.Fn sleep
+or
+.Fn mtx_sleep
+while holding a single mutex.
+It will atomically drop that mutex and reacquire it as part of waking up.
+This is often a bad idea because it generally relies on the programmer having
+good knowledge of all of the call graph above the place where
+.Fn mtx_sleep
+is being called and assumptions the calling code has made.
+Because the lock gets dropped during sleep, one one must re-test all
+the assumptions that were made before, all the way up the call graph to the
+place where the lock was acquired.
+.Pp
+It is an error to do any operation that could result in any kind of sleep when
+running inside an interrupt filter.
+.Pp
+It is an error to do any operation that could result in unbounded sleep when
+running inside an interrupt thread.
+.Ss Interaction table
+The following table shows what you can and can not do while holding
+one of the synchronization primitives discussed:
+.Bl -column ".Ic xxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXX" -offset indent
 .It Xo
-.Em "You have: You want:" Ta Spin_mtx Ta Slp_mtx Ta sx_lock Ta rw_lock Ta rm_lock Ta sleep
+.Em "You have: You want:" Ta spin mtx Ta mutex Ta sx Ta rwlock Ta rmlock Ta sleep
 .Xc
-.It Ic SPIN mutex  Ta \&ok-1 Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no-3
-.It Ic Sleep mutex Ta \&ok Ta \&ok-1 Ta \&no Ta \&ok Ta \&ok Ta \&no-3
-.It Ic sx_lock     Ta \&ok Ta \&ok Ta \&ok-2 Ta \&ok Ta \&ok Ta \&ok-4
-.It Ic rw_lock     Ta \&ok Ta \&ok Ta \&no Ta \&ok-2 Ta \&ok Ta \&no-3
-.It Ic rm_lock     Ta \&ok Ta \&ok Ta \&no Ta \&ok Ta \&ok-2 Ta \&no
+.It spin mtx  Ta \&ok-1 Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no-3
+.It mutex     Ta \&ok Ta \&ok-1 Ta \&no Ta \&ok Ta \&ok Ta \&no-3
+.It sx        Ta \&ok Ta \&ok Ta \&ok-2 Ta \&ok Ta \&ok Ta \&ok-4
+.It rwlock    Ta \&ok Ta \&ok Ta \&no Ta \&ok-2 Ta \&ok Ta \&no-3
+.It rmlock    Ta \&ok Ta \&ok Ta \&no Ta \&ok Ta \&ok-2 Ta \&no
 .El
 .Pp
 .Em *1
@@ -325,11 +309,11 @@ Recursion is defined per lock.
 Lock order is important.
 .Pp
 .Em *2
-readers can recurse though writers can not.
+Readers can recurse though writers can not.
 Lock order is important.
 .Pp
 .Em *3
-There are calls atomically release this primitive when going to sleep
+There are calls that atomically release this primitive when going to sleep
 and reacquire it on wakeup (e.g.
 .Fn mtx_sleep ,
 .Fn rw_sleep
@@ -340,19 +324,22 @@ and
 .Em *4
 Though one can sleep holding an sx lock, one can also use
 .Fn sx_sleep
-which atomically release this primitive when going to sleep and
+which will atomically release this primitive when going to sleep and
 reacquire it on wakeup.
-.Ss Context mode table.
+.Ss Context mode table
 The next table shows what can be used in different contexts.
 At this time this is a rather easy to remember table.
-.Bl -column ".Ic Xxxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXX" -offset indent
+.Bl -column ".Ic Xxxxxxxxxxxxxxxxxxx" ".Xr XXXXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXXX" ".Xr XXXXXX" -offset indent
 .It Xo
-.Em "Context:" Ta Spin_mtx Ta Slp_mtx Ta sx_lock Ta rw_lock Ta rm_lock Ta sleep
+.Em "Context:"  Ta spin mtx Ta mutex Ta sx Ta rwlock Ta rmlock Ta sleep
 .Xc
-.It interrupt:  Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no 
-.It idle:  Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no 
+.It interrupt filter:  Ta \&ok Ta \&no Ta \&no Ta \&no Ta \&no Ta \&no 
+.It ithread:    Ta \&ok Ta \&ok Ta \&no Ta \&ok Ta \&ok Ta \&no 
+.It callout:    Ta \&ok Ta \&ok Ta \&no Ta \&ok Ta \&no Ta \&no 
+.It syscall:    Ta \&ok Ta \&ok Ta \&ok Ta \&ok Ta \&ok Ta \&ok 
 .El
 .Sh SEE ALSO
+.Xr witness 4 ,
 .Xr condvar 9 ,
 .Xr lock 9 ,
 .Xr mtx_pool 9 ,
@@ -362,11 +349,12 @@ At this time this is a rather easy to remember table.
 .Xr sema 9 ,
 .Xr sleep 9 ,
 .Xr sx 9 ,
-.Xr LOCK_PROFILING 9 ,
-.Xr WITNESS 9
+.Xr LOCK_PROFILING 9
 .Sh HISTORY
 These
 functions appeared in
 .Bsx 4.1
 through
 .Fx 7.0
+.Sh BUGS
+There are too many locking primitives to choose from.