1 /*
2 * ptw32_MCS_lock.c
3 *
4 * Description:
5 * This translation unit implements queue-based locks.
6 *
7 * --------------------------------------------------------------------------
8 *
9 * Pthreads-win32 - POSIX Threads Library for Win32
10 * Copyright(C) 1998 John E. Bossom
11 * Copyright(C) 1999,2005 Pthreads-win32 contributors
12 *
13 * Contact Email: rpj@callisto.canberra.edu.au
14 *
15 * The current list of contributors is contained
16 * in the file CONTRIBUTORS included with the source
17 * code distribution. The list can also be seen at the
18 * following World Wide Web location:
19 * http://sources.redhat.com/pthreads-win32/contributors.html
20 *
21 * This library is free software; you can redistribute it and/or
22 * modify it under the terms of the GNU Lesser General Public
23 * License as published by the Free Software Foundation; either
24 * version 2 of the License, or (at your option) any later version.
25 *
26 * This library is distributed in the hope that it will be useful,
27 * but WITHOUT ANY WARRANTY; without even the implied warranty of
28 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
29 * Lesser General Public License for more details.
30 *
31 * You should have received a copy of the GNU Lesser General Public
32 * License along with this library in the file COPYING.LIB;
33 * if not, write to the Free Software Foundation, Inc.,
34 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
35 */
36
37 /*
38 * About MCS locks:
39 *
40 * MCS locks are queue-based locks, where the queue nodes are local to the
41 * thread. The 'lock' is nothing more than a global pointer that points to
42 * the last node in the queue, or is NULL if the queue is empty.
43 *
44 * Originally designed for use as spin locks requiring no kernel resources
45 * for synchronisation or blocking, the implementation below has adapted
46 * the MCS spin lock for use as a general mutex that will suspend threads
47 * when there is lock contention.
48 *
49 * Because the queue nodes are thread-local, most of the memory read/write
50 * operations required to add or remove nodes from the queue do not trigger
51 * cache-coherence updates.
52 *
53 * Like 'named' mutexes, MCS locks consume system resources transiently -
54 * they are able to acquire and free resources automatically - but MCS
55 * locks do not require any unique 'name' to identify the lock to all
56 * threads using it.
57 *
58 * Usage of MCS locks:
59 *
60 * - you need a global ptw32_mcs_lock_t instance initialised to 0 or NULL.
61 * - you need a local thread-scope ptw32_mcs_local_node_t instance, which
62 * may serve several different locks but you need at least one node for
63 * every lock held concurrently by a thread.
64 *
65 * E.g.:
66 *
67 * ptw32_mcs_lock_t lock1 = 0;
68 * ptw32_mcs_lock_t lock2 = 0;
69 *
70 * void *mythread(void *arg)
71 * {
72 * ptw32_mcs_local_node_t node;
73 *
74 * ptw32_mcs_acquire (&lock1, &node);
75 * ptw32_mcs_lock_release (&node);
76 *
77 * ptw32_mcs_lock_acquire (&lock2, &node);
78 * ptw32_mcs_lock_release (&node);
79 * {
80 * ptw32_mcs_local_node_t nodex;
81 *
82 * ptw32_mcs_lock_acquire (&lock1, &node);
83 * ptw32_mcs_lock_acquire (&lock2, &nodex);
84 *
85 * ptw32_mcs_lock_release (&nodex);
86 * ptw32_mcs_lock_release (&node);
87 * }
88 * return (void *)0;
89 * }
90 */
91
92 #include "pthread.h"
93 #include "sched.h"
94 #include "implement.h"
95
96 /*
97 * ptw32_mcs_flag_set -- notify another thread about an event.
98 *
99 * Set event if an event handle has been stored in the flag, and
100 * set flag to -1 otherwise. Note that -1 cannot be a valid handle value.
101 */
102 INLINE void
ptw32_mcs_flag_set(HANDLE * flag)103 ptw32_mcs_flag_set (HANDLE * flag)
104 {
105 HANDLE e = (HANDLE)(PTW32_INTERLOCKED_SIZE)PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
106 (PTW32_INTERLOCKED_SIZEPTR)flag,
107 (PTW32_INTERLOCKED_SIZE)-1,
108 (PTW32_INTERLOCKED_SIZE)0);
109 if ((HANDLE)0 != e)
110 {
111 /* another thread has already stored an event handle in the flag */
112 SetEvent(e);
113 }
114 }
115
116 /*
117 * ptw32_mcs_flag_set -- wait for notification from another.
118 *
119 * Store an event handle in the flag and wait on it if the flag has not been
120 * set, and proceed without creating an event otherwise.
121 */
122 INLINE void
ptw32_mcs_flag_wait(HANDLE * flag)123 ptw32_mcs_flag_wait (HANDLE * flag)
124 {
125 if ((PTW32_INTERLOCKED_LONG)0 ==
126 PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)flag,
127 (PTW32_INTERLOCKED_SIZE)0)) /* MBR fence */
128 {
129 /* the flag is not set. create event. */
130
131 HANDLE e = CreateEvent(NULL, PTW32_FALSE, PTW32_FALSE, NULL);
132
133 if ((PTW32_INTERLOCKED_SIZE)0 == PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
134 (PTW32_INTERLOCKED_SIZEPTR)flag,
135 (PTW32_INTERLOCKED_SIZE)e,
136 (PTW32_INTERLOCKED_SIZE)0))
137 {
138 /* stored handle in the flag. wait on it now. */
139 WaitForSingleObject(e, INFINITE);
140 }
141
142 CloseHandle(e);
143 }
144 }
145
146 /*
147 * ptw32_mcs_lock_acquire -- acquire an MCS lock.
148 *
149 * See:
150 * J. M. Mellor-Crummey and M. L. Scott.
151 * Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
152 * ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
153 */
154 #if defined(PTW32_BUILD_INLINED)
155 INLINE
156 #endif /* PTW32_BUILD_INLINED */
157 void
ptw32_mcs_lock_acquire(ptw32_mcs_lock_t * lock,ptw32_mcs_local_node_t * node)158 ptw32_mcs_lock_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node)
159 {
160 ptw32_mcs_local_node_t *pred;
161
162 node->lock = lock;
163 node->nextFlag = 0;
164 node->readyFlag = 0;
165 node->next = 0; /* initially, no successor */
166
167 /* queue for the lock */
168 pred = (ptw32_mcs_local_node_t *)PTW32_INTERLOCKED_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock,
169 (PTW32_INTERLOCKED_PVOID)node);
170
171 if (0 != pred)
172 {
173 /* the lock was not free. link behind predecessor. */
174 pred->next = node;
175 ptw32_mcs_flag_set(&pred->nextFlag);
176 ptw32_mcs_flag_wait(&node->readyFlag);
177 }
178 }
179
180 /*
181 * ptw32_mcs_lock_release -- release an MCS lock.
182 *
183 * See:
184 * J. M. Mellor-Crummey and M. L. Scott.
185 * Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
186 * ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
187 */
188 #if defined(PTW32_BUILD_INLINED)
189 INLINE
190 #endif /* PTW32_BUILD_INLINED */
191 void
ptw32_mcs_lock_release(ptw32_mcs_local_node_t * node)192 ptw32_mcs_lock_release (ptw32_mcs_local_node_t * node)
193 {
194 ptw32_mcs_lock_t *lock = node->lock;
195 ptw32_mcs_local_node_t *next =
196 (ptw32_mcs_local_node_t *)
197 PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)&node->next, (PTW32_INTERLOCKED_SIZE)0); /* MBR fence */
198
199 if (0 == next)
200 {
201 /* no known successor */
202
203 if (node == (ptw32_mcs_local_node_t *)
204 PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock,
205 (PTW32_INTERLOCKED_PVOID)0,
206 (PTW32_INTERLOCKED_PVOID)node))
207 {
208 /* no successor, lock is free now */
209 return;
210 }
211
212 /* A successor has started enqueueing behind us so wait for them to link to us */
213 ptw32_mcs_flag_wait(&node->nextFlag);
214 next = (ptw32_mcs_local_node_t *)
215 PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)&node->next, (PTW32_INTERLOCKED_SIZE)0); /* MBR fence */
216 }
217
218 /* pass the lock */
219 ptw32_mcs_flag_set(&next->readyFlag);
220 }
221
222 /*
223 * ptw32_mcs_lock_try_acquire
224 */
225 #if defined(PTW32_BUILD_INLINED)
226 INLINE
227 #endif /* PTW32_BUILD_INLINED */
228 int
ptw32_mcs_lock_try_acquire(ptw32_mcs_lock_t * lock,ptw32_mcs_local_node_t * node)229 ptw32_mcs_lock_try_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node)
230 {
231 node->lock = lock;
232 node->nextFlag = 0;
233 node->readyFlag = 0;
234 node->next = 0; /* initially, no successor */
235
236 return ((PTW32_INTERLOCKED_PVOID)PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock,
237 (PTW32_INTERLOCKED_PVOID)node,
238 (PTW32_INTERLOCKED_PVOID)0)
239 == (PTW32_INTERLOCKED_PVOID)0) ? 0 : EBUSY;
240 }
241
242 /*
243 * ptw32_mcs_node_transfer -- move an MCS lock local node, usually from thread
244 * space to, for example, global space so that another thread can release
245 * the lock on behalf of the current lock owner.
246 *
247 * Example: used in pthread_barrier_wait where we want the last thread out of
248 * the barrier to release the lock owned by the last thread to enter the barrier
249 * (the one that releases all threads but not necessarily the last to leave).
250 *
251 * Should only be called by the thread that has the lock.
252 */
253 #if defined(PTW32_BUILD_INLINED)
254 INLINE
255 #endif /* PTW32_BUILD_INLINED */
256 void
ptw32_mcs_node_transfer(ptw32_mcs_local_node_t * new_node,ptw32_mcs_local_node_t * old_node)257 ptw32_mcs_node_transfer (ptw32_mcs_local_node_t * new_node, ptw32_mcs_local_node_t * old_node)
258 {
259 new_node->lock = old_node->lock;
260 new_node->nextFlag = 0; /* Not needed - used only in initial Acquire */
261 new_node->readyFlag = 0; /* Not needed - we were waiting on this */
262 new_node->next = 0;
263
264 if ((ptw32_mcs_local_node_t *)PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)new_node->lock,
265 (PTW32_INTERLOCKED_PVOID)new_node,
266 (PTW32_INTERLOCKED_PVOID)old_node)
267 != old_node)
268 {
269 /*
270 * A successor has queued after us, so wait for them to link to us
271 */
272 while (old_node->next == 0)
273 {
274 sched_yield();
275 }
276 new_node->next = old_node->next;
277 }
278 }
279