1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
.. highlight:: none


.. index::
   pair: locking; design

.. _design-lock:


Lock module
===========

.. mps:prefix:: design.mps.lock


Introduction
------------

:mps:tag:`intro` This is the design of the lock module.

:mps:tag:`readership` Any MPS developer; anyone porting the MPS to a new
platform.


Background
----------

:mps:tag:`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.

:mps:tag:`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.

:mps:tag:`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
------------

:mps:tag:`req.thread-safety` Support the locking needs of
design.mps.thread-safety_.

.. _design.mps.thread-safety: thread-safety.html

:mps:tag:`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.)

:mps:tag:`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.)

:mps:tag:`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 :c:func:`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.)

:mps:tag:`req.global` Provide *global* locks: that is locks that need not be
allocated or initialized by the user.

:mps:tag:`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.html#design.mps.thread-safety.sol.global.mutable

:mps:tag:`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.html#design.mps.thread-safety.sol.global.once

:mps:tag:`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.html#design.mps.thread-safety.sol.deadlock


Interface
---------

.. c:type:: 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 :c:func:`LockSize()` to determine the size.

.. c:function:: size_t LockSize(void)

Return the size of a :c:type:`LockStruct` for allocation purposes.

.. c:function:: 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.

.. c:function:: void LockFinish(Lock lock)

Finish the lock. The lock must not be owned by any thread.

.. c:function:: 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.

.. c:function:: void LockRelease(Lock lock)

Releases ownership of a lock that is currently owned.

.. c:function:: 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).

.. c:function:: void LockReleaseRecursive(Lock lock)

Restores the previous state of the lock remembered by the
corresponding :c:func:`LockClaimRecursive()` call.

.. c:function:: 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 :mps:ref:`.req.held`).

.. c:function:: 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 :c:func:`fork()`.
See design.mps.thread-safety.sol.fork.lock_.

.. _design.mps.thread-safety.sol.fork.lock: thread-safety.html#design.mps.thread-safety.sol.fork.lock

.. c:function:: void LockClaimGlobal(void)

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

.. c:function:: void LockReleaseGlobal(void)

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

.. c:function:: 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).

.. c:function:: void LockReleaseGlobalRecursive(void)

Restores the previous state of the recursive global lock remembered by
the corresponding :c:func:`LockClaimGlobalRecursive()` call.

.. c:function:: void LockSetup(void)

One-time initialization function, intended for calling
:c:func:`pthread_atfork()` on the appropriate platforms: see design.mps.thread-safety.sol.fork.lock_.


Implementation
--------------

:mps:tag:`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.

:mps:tag:`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

:mps:tag:`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.)

:mps:tag:`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.

:mps:tag:`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.

:mps:tag:`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 :c:func:`pthread_mutex_lock()` and expects
  success;
- recursive locking calls :c:func:`pthread_mutex_lock()` and expects either
  success or :c:macro:`EDEADLK` (indicating a recursive claim);
- also performs checking.


Example
-------

:mps:tag:`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);
    }

:mps:tag:`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. */
    }

:mps:tag:`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";
   <https://docs.microsoft.com/en-gb/windows/desktop/Sync/critical-section-objects>

.. [POSIXThreads]
   The Open Group;
   "The Single UNIX Specification, Version 2---Threads";
   <https://pubs.opengroup.org/onlinepubs/7990989775/xsh/threads.html>