cvs version of pthreads

1 files changed, 278 insertions, 263 deletions

diff --git a/pthreads/ptw32_MCS_lock.c b/pthreads/ptw32_MCS_lock.c
index 270c31e9c..d69cf80eb 100644
--- a/pthreads/ptw32_MCS_lock.c
+++ b/pthreads/ptw32_MCS_lock.c
@@ -1,263 +1,278 @@
-/*

- * 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 resources transiently -

- * they are able to acquire and free resources 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((PTW32_INTERLOCKED_LPLONG)lock,

-						              (PTW32_INTERLOCKED_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,

-                           (LONG)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);

-}

-

-/*

-  * ptw32_mcs_lock_try_acquire

- */

-INLINE int

-ptw32_mcs_lock_try_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node)

-{

-  node->lock = lock;

-  node->nextFlag = 0;

-  node->readyFlag = 0;

-  node->next = 0; /* initially, no successor */

-

-  return ((PTW32_INTERLOCKED_LPLONG)PTW32_INTERLOCKED_COMPARE_EXCHANGE(

-                                      (PTW32_INTERLOCKED_LPLONG)lock,

-                                      (PTW32_INTERLOCKED_LONG)node,

-                                      (PTW32_INTERLOCKED_LONG)0)

-               == (PTW32_INTERLOCKED_LPLONG)0) ? 0 : EBUSY;

-}

-

-/*

- * ptw32_mcs_node_substitute -- move an MCS lock local node, usually from thread

- * space to, for example, global space so that another thread can release

- * the lock on behalf of the current lock owner.

- *

- * Example: used in pthread_barrier_wait where we want the last thread out of

- * the barrier to release the lock owned by the last thread to enter the barrier

- * (the one that releases all threads but not necessarily the last to leave).

- *

- * Should only be called by the thread that has the lock.

- */

-INLINE void

-ptw32_mcs_node_substitute (ptw32_mcs_local_node_t * new_node, ptw32_mcs_local_node_t * old_node)

-{

-  new_node->lock = old_node->lock;

-  new_node->nextFlag = 0; /* Not needed - used only in initial Acquire */

-  new_node->readyFlag = 0; /* Not needed - we were waiting on this */

-  new_node->next = 0;

-

-  if ((ptw32_mcs_local_node_t *)PTW32_INTERLOCKED_COMPARE_EXCHANGE((PTW32_INTERLOCKED_LPLONG)new_node->lock,

-                                                                   (PTW32_INTERLOCKED_LONG)new_node,

-                                                                   (PTW32_INTERLOCKED_LONG)old_node) != old_node)

-    {

-      /*

-       * A successor has queued after us, so wait for them to link to us

-       */

-      while (old_node->next == 0)

-        {

-          Sleep(0);

-        }

-      new_node->next = old_node->next;

-    }

-}

+/*
+ * 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 resources transiently -
+ * they are able to acquire and free resources 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_lock_release (&node);
+ *
+ *   ptw32_mcs_lock_acquire (&lock2, &node);
+ *   ptw32_mcs_lock_release (&node);
+ *   {
+ *      ptw32_mcs_local_node_t nodex;
+ *
+ *      ptw32_mcs_lock_acquire (&lock1, &node);
+ *      ptw32_mcs_lock_acquire (&lock2, &nodex);
+ *
+ *      ptw32_mcs_lock_release (&nodex);
+ *      ptw32_mcs_lock_release (&node);
+ *   }
+ *   return (void *)0;
+ * }
+ */
+
+#include "pthread.h"
+#include "sched.h"
+#include "implement.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 (HANDLE * flag)
+{
+  HANDLE e = (HANDLE)(PTW32_INTERLOCKED_SIZE)PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
+						(PTW32_INTERLOCKED_SIZEPTR)flag,
+						(PTW32_INTERLOCKED_SIZE)-1,
+						(PTW32_INTERLOCKED_SIZE)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 (HANDLE * flag)
+{
+  if ((PTW32_INTERLOCKED_LONG)0 ==
+        PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)flag,
+                                            (PTW32_INTERLOCKED_SIZE)0)) /* MBR fence */
+    {
+      /* the flag is not set. create event. */
+
+      HANDLE e = CreateEvent(NULL, PTW32_FALSE, PTW32_FALSE, NULL);
+
+      if ((PTW32_INTERLOCKED_SIZE)0 == PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE(
+			                  (PTW32_INTERLOCKED_SIZEPTR)flag,
+			                  (PTW32_INTERLOCKED_SIZE)e,
+			                  (PTW32_INTERLOCKED_SIZE)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.
+ */
+#if defined(PTW32_BUILD_INLINED)
+INLINE 
+#endif /* PTW32_BUILD_INLINED */
+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_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock,
+								  (PTW32_INTERLOCKED_PVOID)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.
+ */
+#if defined(PTW32_BUILD_INLINED)
+INLINE 
+#endif /* PTW32_BUILD_INLINED */
+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 *)
+      PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)&node->next, (PTW32_INTERLOCKED_SIZE)0); /* MBR fence */
+
+  if (0 == next)
+    {
+      /* no known successor */
+
+      if (node == (ptw32_mcs_local_node_t *)
+	  PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock,
+						 (PTW32_INTERLOCKED_PVOID)0,
+						 (PTW32_INTERLOCKED_PVOID)node))
+	{
+	  /* no successor, lock is free now */
+	  return;
+	}
+  
+      /* wait for successor */
+      ptw32_mcs_flag_wait(&node->nextFlag);
+      next = (ptw32_mcs_local_node_t *)
+	PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)&node->next, (PTW32_INTERLOCKED_SIZE)0); /* MBR fence */
+    }
+
+  /* pass the lock */
+  ptw32_mcs_flag_set(&next->readyFlag);
+}
+
+/*
+  * ptw32_mcs_lock_try_acquire
+ */
+#if defined(PTW32_BUILD_INLINED)
+INLINE 
+#endif /* PTW32_BUILD_INLINED */
+int 
+ptw32_mcs_lock_try_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node)
+{
+  node->lock = lock;
+  node->nextFlag = 0;
+  node->readyFlag = 0;
+  node->next = 0; /* initially, no successor */
+
+  return ((PTW32_INTERLOCKED_PVOID)PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock,
+                                                        (PTW32_INTERLOCKED_PVOID)node,
+                                                        (PTW32_INTERLOCKED_PVOID)0)
+                                 == (PTW32_INTERLOCKED_PVOID)0) ? 0 : EBUSY;
+}
+
+/*
+ * ptw32_mcs_node_transfer -- move an MCS lock local node, usually from thread
+ * space to, for example, global space so that another thread can release
+ * the lock on behalf of the current lock owner.
+ *
+ * Example: used in pthread_barrier_wait where we want the last thread out of
+ * the barrier to release the lock owned by the last thread to enter the barrier
+ * (the one that releases all threads but not necessarily the last to leave).
+ *
+ * Should only be called by the thread that has the lock.
+ */
+#if defined(PTW32_BUILD_INLINED)
+INLINE 
+#endif /* PTW32_BUILD_INLINED */
+void 
+ptw32_mcs_node_transfer (ptw32_mcs_local_node_t * new_node, ptw32_mcs_local_node_t * old_node)
+{
+  new_node->lock = old_node->lock;
+  new_node->nextFlag = 0; /* Not needed - used only in initial Acquire */
+  new_node->readyFlag = 0; /* Not needed - we were waiting on this */
+  new_node->next = 0;
+
+  if ((ptw32_mcs_local_node_t *)PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)new_node->lock,
+                                                                       (PTW32_INTERLOCKED_PVOID)new_node,
+                                                                       (PTW32_INTERLOCKED_PVOID)old_node)
+       != old_node)
+    {
+      /*
+       * A successor has queued after us, so wait for them to link to us
+       */
+      while (old_node->next == 0)
+        {
+          sched_yield();
+        }
+      new_node->next = old_node->next;
+    }
+}