native_client_sdk/src/libraries/third_party/pthreads-win32/ptw32_MCS_lock.c

   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  */
 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 }