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 (at) 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 */ 102 INLINE void 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 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 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 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 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 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
