Initial checkin for rmlock (read mostly lock) a multi reader single writer

lock optimized for almost exclusive reader access. (see also rmlock.9)

TODO:
    Convert to per cpu variables linkerset as soon as it is available.
    Optimize UP (single processor)  case.

1 files changed, 185 insertions, 0 deletions

diff --git a/share/man/man9/rmlock.9 b/share/man/man9/rmlock.9
new file mode 100644
index 0000000..c088f64
--- /dev/null
+++ b/share/man/man9/rmlock.9
@@ -0,0 +1,185 @@
+.\" Copyright (c) 2007 Stephan Uphoff <ups@FreeBSD.org>
+.\" Copyright (c) 2006 Gleb Smirnoff <glebius@FreeBSD.org>
+.\" All rights reserved.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.\" $FreeBSD$
+.\"
+.\" Based on rwlock.9 man page
+
+.Dd August 22, 2007
+.Dt RMLOCK 9
+.Os
+.Sh NAME
+.Nm rmlock ,
+.Nm rm_init ,
+.Nm rm_destroy ,
+.Nm rm_rlock ,
+.Nm rm_wlock ,
+.Nm rm_runlock ,
+.Nm rm_wunlock ,
+.Nm RM_SYSINIT
+.Nd mostly read lock - a kernel reader/writer lock optimized for mostly read access patterns
+.Sh SYNOPSIS
+.In sys/param.h
+.In sys/lock.h
+.In sys/rmlock.h
+.Ft void
+.Fn rm_init "struct rmlock *rm" "const char *name" "int opts"
+.Ft void
+.Fn rm_destroy "struct rmlock *rm"
+.Ft void
+.Fn rm_rlock "struct rmlock *rm"  "struct rm_priotracker* tracker"
+.Ft void
+.Fn rm_wlock "struct rmlock *rm"
+.Ft void
+.Fn rm_runlock "struct rmlock *rm" "struct rm_priotracker* tracker"
+.Ft void
+.Fn rm_wunlock "struct rmlock *rm"
+.Ft int
+
+.In sys/kernel.h
+.Fn RM_SYSINIT "name" "struct rmlock *rm" "const char *desc" "int opts"
+.Sh DESCRIPTION
+Mostly reader 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
+.Em readers
+since they only read the protected data.
+A thread with exclusive access is known as a
+.Em writer
+since it can modify protected data.
+.Pp
+Read mostly locks are designed to be efficient for locks allmost exclusively used as reader
+locks and as such should be used for protecting data that rarely changes.
+Acquiring an exclusive lock after the lock had been locked for shared access is an expensive operation.   
+.Pp
+Although reader/writer locks look very similar to
+.Xr sx 9
+locks, their usage pattern is different.
+Reader/writer locks can be treated as mutexes (see
+.Xr mutex 9 )
+with shared/exclusive semantics.
+Unlike
+.Xr sx 9 ,
+an
+.Nm
+can be locked while holding a non-spin mutex, and an
+.Nm
+cannot be held while sleeping.
+The
+.Nm
+locks have full priority propagation like mutexes. The rm_priotracker structure argument supplied
+in rmrlock and rmrunlock is used to keep track of the read owner(s).
+Another important property is that shared holders of
+.Nm
+can recurse if the lock has been initialized with the LO_RECURSABLE option,
+however exclusive locks are not allowed to recurse.
+.Ss Macros and Functions
+.Bl -tag -width indent
+.It Fn rm_init "struct rmlock *rm" "const char *name" "int opts"
+Initialize structure located at
+.Fa rm
+as mostly reader lock, described by name
+.Fa name .
+Optioally allowing readers to recurse by setting LO_RECURSABLE in
+.Fa opts
+The name description is used solely for debugging purposes.
+This function must be called before any other operations
+on the lock.
+.It Fn rm_rlock "struct rmlock *rm"  "struct rm_priotracker* tracker"
+Lock
+.Fa rm
+as a reader. Using
+.Fa tracker
+to track read owners of a lock for priority propagation.
+This data structure is only used internally by rmlock and must persist
+until rm_runlock has been called. This data structure can be allocated on the stack since
+rmlocks cannot be held while sleeping.
+If any thread holds this lock exclusively, the current thread blocks,
+and its priority is propagated to the exclusive holder.
+If the lock was initialized with the LO_RECURSABLE option the
+.Fn rm_rlock
+function can be called when the thread has already acquired reader
+access on
+.Fa rm .
+This is called
+.Dq "recursing on a lock" .
+.It Fn rm_wlock "struct rmlock *rm"
+Lock
+.Fa rm
+as a writer.
+If there are any shared owners of the lock, the current thread blocks.
+The
+.Fn rm_wlock
+function cannot be called recursively.
+.It Fn rm_runlock "struct rmlock *rm"  "struct rm_priotracker* tracker"
+This function releases a shared lock previously acquired by
+.Fn rm_rlock .
+The
+.Fa tracker
+argument must match the 
+.Fa tracker 
+argument used for acquiring the shared lock 
+.It Fn rm_wunlock "struct rmlock *rm"
+This function releases an exclusive lock previously acquired by
+.Fn rm_wlock .
+.It Fn rm_destroy "struct rmlock *rm"
+This functions destroys a lock previously initialized with
+.Fn rm_init .
+The
+.Fa rm
+lock must be unlocked.
+.El
+.El
+.Sh SEE ALSO
+.Xr locking 9 ,
+.Xr mutex 9 ,
+.Xr panic 9 ,
+.Xr rwlock 9,
+.Xr sema 9 ,
+.Xr sx 9
+.Sh HISTORY
+These
+functions appeared in
+.Fx 7.0 .
+.Sh AUTHORS
+.An -nosplit
+The
+.Nm
+facility was written by
+.An "Stephan Uphoff" .
+This manual page was written by
+.An "Gleb Smirnoff"
+for rwlock and modifed to reflect rmlock by
+.An "Stephan Uphoff" .
+.Sh BUGS
+.Dv Uniprocessor Systems Optimization:
+rmlock is not currently optimized for single processor systems
+
+.Dv Number of rmlocks in the system:
+The rmlock implementation uses a single per cpu list shared by all rmlocks in the system.
+If rmlocks become popular, hashing to multiple per cpu queues may be needed to speed up
+the writer lock process. 
+
+.Dv condvar: The rm lock can currently not be used as a lock argument for condition variable wait functions.