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
|
/*
* 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 recourses transiently -
* they are able to acquire and free recourses 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_release (&node);
*
* ptw32_mcs_acquire (&lock2, &node);
* ptw32_mcs_release (&node);
* {
* ptw32_mcs_local_node_t nodex;
*
* ptw32_mcs_acquire (&lock1, &node);
* ptw32_mcs_acquire (&lock2, &nodex);
*
* ptw32_mcs_release (&nodex);
* ptw32_mcs_release (&node);
* }
* return (void *)0;
* }
*/
#include "implement.h"
#include "pthread.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_COMPARE_EXCHANGE(
(PTW32_INTERLOCKED_LPLONG)flag,
(PTW32_INTERLOCKED_LONG)-1,
(PTW32_INTERLOCKED_LONG)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 == InterlockedExchangeAdd((LPLONG)flag, 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_LPLONG)flag,
(PTW32_INTERLOCKED_LONG)e,
(PTW32_INTERLOCKED_LONG)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.
*/
INLINE 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((LPLONG)lock,
(LONG)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.
*/
INLINE 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 *)
InterlockedExchangeAdd((LPLONG)&node->next, 0); /* MBR fence */
if (0 == next)
{
/* no known successor */
if (node == (ptw32_mcs_local_node_t *)
PTW32_INTERLOCKED_COMPARE_EXCHANGE((PTW32_INTERLOCKED_LPLONG)lock,
(PTW32_INTERLOCKED_LONG)0,
(PTW32_INTERLOCKED_LONG)node))
{
/* no successor, lock is free now */
return;
}
/* wait for successor */
ptw32_mcs_flag_wait(&node->nextFlag);
next = (ptw32_mcs_local_node_t *)
InterlockedExchangeAdd((LPLONG)&node->next, 0); /* MBR fence */
}
/* pass the lock */
ptw32_mcs_flag_set(&next->readyFlag);
}
|
