[3f334b]: ptw32_MCS_lock.c Maximize Restore History

Download this file

ptw32_MCS_lock.c    276 lines (255 with data), 8.9 kB

  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
/*
* ptw32_MCS_lock.c
*
* Description:
* This translation unit implements queue-based locks.
*
* --------------------------------------------------------------------------
*
* Pthreads-win32 - POSIX Threads Library for Win32
* Copyright(C) 1998 John E. Bossom
* Copyright(C) 1999,2005 Pthreads-win32 contributors
*
* Contact Email: rpj@callisto.canberra.edu.au
*
* The current list of contributors is contained
* in the file CONTRIBUTORS included with the source
* code distribution. The list can also be seen at the
* following World Wide Web location:
* http://sources.redhat.com/pthreads-win32/contributors.html
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library in the file COPYING.LIB;
* if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
*/
/*
* About MCS locks:
*
* MCS locks are queue-based locks, where the queue nodes are local to the
* thread. The 'lock' is nothing more than a global pointer that points to
* the last node in the queue, or is NULL if the queue is empty.
*
* Originally designed for use as spin locks requiring no kernel resources
* for synchronisation or blocking, the implementation below has adapted
* the MCS spin lock for use as a general mutex that will suspend threads
* when there is lock contention.
*
* Because the queue nodes are thread-local, most of the memory read/write
* operations required to add or remove nodes from the queue do not trigger
* cache-coherence updates.
*
* Like 'named' mutexes, MCS locks consume system resources transiently -
* they are able to acquire and free resources automatically - but MCS
* locks do not require any unique 'name' to identify the lock to all
* threads using it.
*
* Usage of MCS locks:
*
* - you need a global ptw32_mcs_lock_t instance initialised to 0 or NULL.
* - you need a local thread-scope ptw32_mcs_local_node_t instance, which
* may serve several different locks but you need at least one node for
* every lock held concurrently by a thread.
*
* E.g.:
*
* ptw32_mcs_lock_t lock1 = 0;
* ptw32_mcs_lock_t lock2 = 0;
*
* void *mythread(void *arg)
* {
* ptw32_mcs_local_node_t node;
*
* ptw32_mcs_acquire (&lock1, &node);
* ptw32_mcs_lock_release (&node);
*
* ptw32_mcs_lock_acquire (&lock2, &node);
* ptw32_mcs_lock_release (&node);
* {
* ptw32_mcs_local_node_t nodex;
*
* ptw32_mcs_lock_acquire (&lock1, &node);
* ptw32_mcs_lock_acquire (&lock2, &nodex);
*
* ptw32_mcs_lock_release (&nodex);
* ptw32_mcs_lock_release (&node);
* }
* return (void *)0;
* }
*/
#include "pthread.h"
#include "sched.h"
#include "implement.h"
/*
* ptw32_mcs_flag_set -- notify another thread about an event.
*
* Set event if an event handle has been stored in the flag, and
* set flag to -1 otherwise. Note that -1 cannot be a valid handle value.
*/
INLINE void
ptw32_mcs_flag_set (LONG * flag)
{
HANDLE e = (HANDLE)(PTW32_INTERLOCKED_VALUE)PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_PTR)flag,
(PTW32_INTERLOCKED_VALUE)-1,
(PTW32_INTERLOCKED_VALUE)0);
if ((HANDLE)0 != e)
{
/* another thread has already stored an event handle in the flag */
SetEvent(e);
}
}
/*
* ptw32_mcs_flag_set -- wait for notification from another.
*
* Store an event handle in the flag and wait on it if the flag has not been
* set, and proceed without creating an event otherwise.
*/
INLINE void
ptw32_mcs_flag_wait (LONG * flag)
{
if (0 == PTW32_INTERLOCKED_EXCHANGE_ADD((PTW32_INTERLOCKED_PTR)flag, (PTW32_INTERLOCKED_VALUE)0)) /* MBR fence */
{
/* the flag is not set. create event. */
HANDLE e = CreateEvent(NULL, PTW32_FALSE, PTW32_FALSE, NULL);
if (0 == PTW32_INTERLOCKED_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_PTR)flag,
(PTW32_INTERLOCKED_VALUE)e,
(PTW32_INTERLOCKED_VALUE)0))
{
/* stored handle in the flag. wait on it now. */
WaitForSingleObject(e, INFINITE);
}
CloseHandle(e);
}
}
/*
* ptw32_mcs_lock_acquire -- acquire an MCS lock.
*
* See:
* J. M. Mellor-Crummey and M. L. Scott.
* Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
* ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
*/
#if defined(PTW32_BUILD_INLINED)
INLINE
#endif /* PTW32_BUILD_INLINED */
void
ptw32_mcs_lock_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node)
{
ptw32_mcs_local_node_t *pred;
node->lock = lock;
node->nextFlag = 0;
node->readyFlag = 0;
node->next = 0; /* initially, no successor */
/* queue for the lock */
pred = (ptw32_mcs_local_node_t *)PTW32_INTERLOCKED_EXCHANGE_PTR((PVOID volatile *)lock,
(PVOID) node);
if (0 != pred)
{
/* the lock was not free. link behind predecessor. */
pred->next = node;
ptw32_mcs_flag_set(&pred->nextFlag);
ptw32_mcs_flag_wait(&node->readyFlag);
}
}
/*
* ptw32_mcs_lock_release -- release an MCS lock.
*
* See:
* J. M. Mellor-Crummey and M. L. Scott.
* Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
* ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
*/
#if defined(PTW32_BUILD_INLINED)
INLINE
#endif /* PTW32_BUILD_INLINED */
void
ptw32_mcs_lock_release (ptw32_mcs_local_node_t * node)
{
ptw32_mcs_lock_t *lock = node->lock;
ptw32_mcs_local_node_t *next = (ptw32_mcs_local_node_t *)(size_t)
PTW32_INTERLOCKED_EXCHANGE_ADD((PTW32_INTERLOCKED_PTR)&node->next, (PTW32_INTERLOCKED_VALUE)0); /* MBR fence */
if (0 == next)
{
/* no known successor */
if (node == (ptw32_mcs_local_node_t *)
PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PVOID volatile *)lock,
(PVOID)0,
(PVOID)node))
{
/* no successor, lock is free now */
return;
}
/* wait for successor */
ptw32_mcs_flag_wait(&node->nextFlag);
next = (ptw32_mcs_local_node_t *)(size_t)
PTW32_INTERLOCKED_EXCHANGE_ADD((PTW32_INTERLOCKED_PTR)&node->next, (PTW32_INTERLOCKED_VALUE)0); /* MBR fence */
}
/* pass the lock */
ptw32_mcs_flag_set(&next->readyFlag);
}
/*
* ptw32_mcs_lock_try_acquire
*/
#if defined(PTW32_BUILD_INLINED)
INLINE
#endif /* PTW32_BUILD_INLINED */
int
ptw32_mcs_lock_try_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node)
{
node->lock = lock;
node->nextFlag = 0;
node->readyFlag = 0;
node->next = 0; /* initially, no successor */
return ((PVOID)PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PVOID volatile *)lock,
(PVOID)node,
(PVOID)0)
== (PVOID)0) ? 0 : EBUSY;
}
/*
* ptw32_mcs_node_transfer -- move an MCS lock local node, usually from thread
* space to, for example, global space so that another thread can release
* the lock on behalf of the current lock owner.
*
* Example: used in pthread_barrier_wait where we want the last thread out of
* the barrier to release the lock owned by the last thread to enter the barrier
* (the one that releases all threads but not necessarily the last to leave).
*
* Should only be called by the thread that has the lock.
*/
#if defined(PTW32_BUILD_INLINED)
INLINE
#endif /* PTW32_BUILD_INLINED */
void
ptw32_mcs_node_transfer (ptw32_mcs_local_node_t * new_node, ptw32_mcs_local_node_t * old_node)
{
new_node->lock = old_node->lock;
new_node->nextFlag = 0; /* Not needed - used only in initial Acquire */
new_node->readyFlag = 0; /* Not needed - we were waiting on this */
new_node->next = 0;
if ((ptw32_mcs_local_node_t *)PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PVOID volatile *)new_node->lock,
(PVOID)new_node,
(PVOID)old_node)
!= old_node)
{
/*
* A successor has queued after us, so wait for them to link to us
*/
while (old_node->next == 0)
{
sched_yield();
}
new_node->next = old_node->next;
}
}