.. mode: -*- rst -*- Lock module =========== :Tag: design.mps.lock :Author: David Moore :Date: 1995-11-21 :Status: complete design :Revision: $Id: //info.ravenbrook.com/project/mps/master/design/lock.txt#22 $ :Copyright: See `Copyright and License`_. :Index terms: pair: locking; design Introduction ------------ _`.intro`: This is the design of the lock module. _`.readership`: Any MPS developer; anyone porting the MPS to a new platform. Background ---------- _`.need`: In an environment where multiple threads are accessing shared data, threads need to cooperate 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. Requirements ------------ _`.req.thread-safety`: Support the locking needs of design.mps.thread-safety_. .. _design.mps.thread-safety: thread-safety _`.req.binary`: Provide *binary* locks: that is, locks that can be claimed, and until released, other attempts to claim them block. (This is needed to implement the arena lock.) _`.req.recursive`: Provide *recursive* locks: that is, locks that can be claimed again by the thread currently holding them, without blocking or deadlocking. (This is needed to implement the global recursive lock.) _`.req.held`: Provide a means to test if a lock is held. (This is needed for debugging a dynamic function table callback on Windows on x86-64. See ``mps_arena_busy()`` for a detailed description of this use case. Note that in this use case the program is running single-threaded and so there is no need for this feature to be thread-safe.) _`.req.global`: Provide *global* locks: that is locks that need not be allocated or initialized by the user. _`.req.global.binary`: Provide a global binary lock. (This is required to protect the data structure allowing multiple arenas to coordinate handling of protection faults: see design.mps.thread-safety.sol.global.mutable_.) .. _design.mps.thread-safety.sol.global.mutable: thread-safety#.sol.global.mutable _`.req.global.recursive`: Provide a global recursive lock. (This is required to protect protocol class initialization: see design.mps.thread-safety.sol.global.once_.) .. _design.mps.thread-safety.sol.global.once: thread-safety#.sol.global.once _`.req.deadlock.not`: There is no requirement to provide protection against deadlock. (Clients are able to avoid deadlock using traditional strategies such as ordering of locks; see design.mps.thread-safety.sol.deadlock_.) .. _design.mps.thread-safety.sol.deadlock: thread-safety#.sol.deadlock Interface --------- ``typedef LockStruct *Lock`` An opaque type representing a lock. Clients that needs to allocate space for a lock should dynamically allocate space for the structure, calling ``LockSize()`` to determine the size. ``size_t LockSize(void)`` Return the size of a ``LockStruct`` for allocation purposes. ``void LockInit(Lock lock)`` Initialize the lock. This must be called before any use of the lock. After initialization, the lock is not owned by any thread. ``void LockFinish(Lock lock)`` Finish the lock. The lock must not be owned by any thread. ``void LockClaim(Lock lock)`` Wait, if necessary, until the lock is not owned by any thread. Then claim ownership of the lock by the current thread. ``void LockRelease(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)`` Restores the previous state of the lock remembered by the corresponding ``LockClaimRecursive()`` call. ``Bool LockIsHeld(Lock lock)`` Return true if the lock is held by any thread, false otherwise. Note that this function need not be thread-safe (see `.req.held`_). ``void LockInitGlobal(void)`` Initialize (or re-initialize) the global locks. This should only be called in the following circumstances: the first time either of the global locks is claimed; and in the child process after a ``fork()``. See design.mps.thread-safety.sol.fork.lock_. .. _design.mps.thread-safety.sol.fork.lock: thread-safety#.sol.fork.lock ``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 remembered by the corresponding ``LockClaimGlobalRecursive()`` call. ``void LockSetup(void)`` One-time initialization function, intended for calling ``pthread_atfork()`` on the appropriate platforms: see design.mps.thread-safety.sol.fork.lock_. Implementation -------------- _`.impl.recursive`: For recursive claims, the list of previous states can be implemented by keeping a count of the number of claims made by the current thread so far. In the multi-threaded implementations this is handled by the operating system interface, but a count is still kept and used to check correctness. _`.impl.recursive.limit`: The implementation imposes a limit on the number of recursive claims (see issue.lock-claim-limit_). On Windows, the critical section object contains the field ``LONG RecursionCount``. In typical POSIX Threads implementations, ``pthread_mutex_t`` uses an ``int`` for the count of recursive claims. .. _issue.lock-claim-limit: https://info.ravenbrook.com/project/mps/import/2001-09-27/mminfo/issue/lock-claim-limit _`.impl.global`: The binary and recursive global locks are typically implemented using the same mechanism as normal locks. (But an operating system-specific mechanism is used, if possible, to ensure that the global locks are initialized just once.) _`.impl.an`: Single-threaded generic implementation ``lockan.c``: - single-threaded; - no need for locking; - locking structure contains count; - provides checking in debug version; - otherwise does nothing except keep count of claims. _`.impl.w3`: Windows implementation ``lockw3.c``: - supports Windows threads; - uses critical section objects [cso]_; - locking structure contains a critical section object; - recursive and non-recursive calls use the same Windows function; - also performs checking. _`.impl.ix`: POSIX implementation ``lockix.c``: - supports [POSIXThreads]_; - 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. Example ------- _`.example.init`: An example of allocating and initializing a lock:: #include "lock.h" static Lock lock; void init() { mps_addr_t p; if (mps_alloc(&p, pool, LockSize()) != MPS_RES_OK) exit(1); lock = p; LockInit(lock); } _`.example.binary`: An example of using a binary lock:: void binaryUse() { /* lock must not be owned by this thread, or else this deadlocks. */ LockClaim(lock); /* lock is now owned by this thread. */ /* cannot call binaryUse() at this point. */ /* only one thread at a time may be at this point. */ LockRelease(lock); /* lock not owned by this thread. */ } _`.example.recursive`: An example of using a recursive lock:: void recursiveUse() { /* lock may or may not already be owned by this thread. */ LockClaimRecursive(lock); /* lock is now owned by this thread. */ /* cannot call binaryUse() at this point. */ /* can call recursiveUse() at this point. */ /* only one thread at a time may be at this point. */ LockReleaseRecursive(lock); /* lock is still owned by this thread if it was before. */ } References ---------- .. [cso] Microsoft Developer Network; "Critical Section Objects"; .. [POSIXThreads] The Open Group; "The Single UNIX Specification, Version 2---Threads"; 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. - 2014-10-21 GDR_ Brought up to date. - 2018-06-14 GDR_ Added ``LockInitGlobal()``. .. _RB: https://www.ravenbrook.com/consultants/rb/ .. _GDR: https://www.ravenbrook.com/consultants/gdr/ Copyright and License --------------------- Copyright © 2013–2020 `Ravenbrook Limited `_. 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 COPYRIGHT HOLDERS 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 COPYRIGHT HOLDER 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.