.. mode: -*- rst -*-

The lock module
===============

:Tag: design.mps.lock
:Author: David Moore
:Date: 1995-11-21
:Status: incomplete design
:Revision: $Id: //info.ravenbrook.com/project/mps/version/1.114/design/lock.txt#1 $
:Copyright: See `Copyright and License`_.
:Index terms: pair: locking; design


Purpose
-------

_`.purpose`: Support the locking needs of the thread-safe design. In
particular:

- recursive locks;
- binary locks;
- recursive "global" lock that need not be allocated or initialized by
  the client;
- binary "global" lock that need not be allocated or initialized by
  the client.

_`.context`: The MPS has to be able to operate in a multi-threaded
environment. The thread-safe design (design.mps.thread-safety)
requires client-allocatable binary locks, a global binary lock and a
global recursive lock. An interface to client-allocatable recursive
locks is also present to support any potential use, because of
historic requirements, and because the implementation will presumably
be necessary anyway for the global recursive lock.


Background
----------

_`.need`: In an environment where multiple threads are accessing
shared data. The threads which access data which is shared with other
threads need to cooperate with those threads to maintain consistency.
Locks provide a simple mechanism for doing this.

_`.ownership`: A lock is an object which may be "owned" by a single
thread at a time. By claiming ownership of a lock before executing
some piece of code a thread can guarantee that no other thread owns
the lock during execution of that code. If some other thread holds a
claim on a lock, the thread trying to claim the lock will suspend
until the lock is released by the owning thread.

_`.data`: A simple way of using this behaviour is to associate a lock
with a shared data structure. By claiming that lock around accesses to
the data, a consistent view of the structure can be seen by the
accessing thread. More generally any set of operations which are
required to be mutually exclusive may be performed so by using locks.


Overview
--------

_`.adt`: There is an abstract datatype ``Lock`` which points to a
locking structure ``LockStruct``. This structure is opaque to any
client, although an interface is provided to supply the size of the
structure for any client wishing to make a new lock. The lock is not
allocated by the module as allocation itself may require locking.
``LockStruct`` is implementation specific.

_`.simple-lock`: There are facilities for claiming and releasing
locks. ``Lock`` is used for both binary and recursive locking.

_`.global-locks`: "Global" locks are so called because they are used
to protect data in a global location (such as a global variable). The
lock module provides two global locks; one recursive and one binary.
There are facilities for claiming and releasing both of these locks.
These global locks have the advantage that they need not be allocated
or atomically initialized by the client, so they may be used for
locking the initialization of the allocator itself. The binary global
lock is intended to protect mutable data, possibly in conjunction with
other local locking strategies. The recursive global lock is intended
to protect static read-only data during one-off initialization. See
design.mps.thread-safety.

_`.deadlock`: This module does not provide any deadlock protection.
Clients are responsible for avoiding deadlock by using traditional
strategies such as ordering of locks. (See
design.mps.thread-safety.deadlock.)

_`.single-thread`: In the single-threaded configuration, locks are not
needed and the claim/release interfaces defined to be no-ops.


Detailed design
---------------

_`.interface`: The interface comprises the following functions:

``size_t LockSize(void)``

Return the size of a ``LockStruct`` for allocation purposes.

``void LockInit(Lock lock)``

After initialisation the lock is not owned by any thread. 

``void LockFinish(Lock lock)``

Before finalisation the lock must not beowned by any thread.

``void LockClaim(Lock lock)``

Claims ownership of a lock that was previously not held by current
thread.

``void LockReleaseMPM(Lock lock)``

Releases ownership of a lock that is currently owned.

``void LockClaimRecursive(Lock lock)``

Remembers the previous state of the lock with respect to the current
thread and claims the lock (if not already held).

``void LockReleaseRecursive(Lock lock)``

Testores the previous state of the lock stored by corresponding
``LockClaimRecursive()`` call.

``void LockClaimGlobal(void)``

Claims ownership of the binary global lock which was previously not
held by current thread.

``void LockReleaseGlobal(void)``

Releases ownership of the binary global lock that is currently owned.

``void LockClaimGlobalRecursive(void)``

Remembers the previous state of the recursive global lock with respect
to the current thread and claims the lock (if not already held).

``void LockReleaseGlobalRecursive(void)``

Restores the previous state of the recursive global lock stored by
corresponding ``LockClaimGlobalRecursive()`` call.

_`.impl.recursive`: For recursive claims, the list of previous states
can be simply implemented by keeping a count of the number of claims
made by the current thread so far. In multi-threaded implementation
below this is handled by the operating system. A count is still kept
and used to check correctness.

_`.impl.global`: The binary and recursive global locks may actually be
implemented using the same mechanism as normal locks.

_`.impl.ansi`: Single-Threaded Generic Implementation:

- single-thread;
- no need for locking;
- locking structure contains count;
- provides checking in debug version;
- otherwise does nothing except keep count of claims.

_`.impl.win32`: Win32 Implementation:

- supports Win32's threads;
- uses Critical Sections [ref?];
- locking structure contains a Critical Section;
- both recursive and non-recursive calls use same Windows function;
- also performs checking.

_`.impl.linux`: LinuxThreads Implementation (possibly suitable for all
PThreads implementations):

- supports LinuxThreads threads, which are an implementation of
  PThreads (see `<http://pauillac.inria.fr/~xleroy/linuxthreads/>`_);
- locking structure contains a mutex, initialized to check for
  recursive locking;
- locking structure contains a count of the number of active claims;
- non-recursive locking calls ``pthread_mutex_lock()`` and expects success;
- recursive locking calls ``pthread_mutex_lock()`` and expects either
  success or ``EDEADLK`` (indicating a recursive claim);
- also performs checking.

Document History
----------------

- 1995-11-21 David Moore. Incomplete design.

- 2002-06-07 RB_ Converted from MMInfo database design document.

- 2013-04-14 GDR_ Converted to reStructuredText.

.. _RB: http://www.ravenbrook.com/consultants/rb/
.. _GDR: http://www.ravenbrook.com/consultants/gdr/


Copyright and License
---------------------

Copyright © 2013-2014 Ravenbrook Limited. All rights reserved.
<http://www.ravenbrook.com/>. This is an open source license. Contact
Ravenbrook for commercial licensing options.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

#. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.

#. 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.

#. Redistributions in any form must be accompanied by information on how
   to obtain complete source code for this software and any
   accompanying software that uses this software.  The source code must
   either be included in the distribution or be available for no more than
   the cost of distribution plus a nominal fee, and must be freely
   redistributable under reasonable conditions.  For an executable file,
   complete source code means the source code for all modules it contains.
   It does not include source code for modules or files that typically
   accompany the major components of the operating system on which the
   executable file runs.

**This software is provided by the copyright holders and contributors
"as is" and any express or implied warranties, including, but not
limited to, the implied warranties of merchantability, fitness for a
particular purpose, or non-infringement, are disclaimed.  In no event
shall the copyright holders and 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.**