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 *      59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 */
102INLINE void
103ptw32_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 */
122INLINE void
123ptw32_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)
155INLINE
156#endif /* PTW32_BUILD_INLINED */
157void
158ptw32_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)
189INLINE
190#endif /* PTW32_BUILD_INLINED */
191void
192ptw32_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)
226INLINE
227#endif /* PTW32_BUILD_INLINED */
228int
229ptw32_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)
254INLINE
255#endif /* PTW32_BUILD_INLINED */
256void
257ptw32_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