''

21 files changed, 327 insertions, 161 deletions

diff --git a/ANNOUNCE b/ANNOUNCE
index ceb0fe8..7c37f32 100644
--- a/ANNOUNCE
+++ b/ANNOUNCE
@@ -1,4 +1,4 @@
-	     PTHREADS-WIN32 RELEASE 2.6.0 (2005-05-19)
+	     PTHREADS-WIN32 RELEASE 2.7.0 (2005-06-04)
 	     -----------------------------------------
 	 Web Site: http://sources.redhat.com/pthreads-win32/
 	FTP Site: ftp://sources.redhat.com/pub/pthreads-win32
diff --git a/Bmakefile b/Bmakefile
index 6752b67..66707bf 100644
--- a/Bmakefile
+++ b/Bmakefile
@@ -102,6 +102,7 @@ MISC_SRCS	= \
 		pthread_self.c \
 		pthread_setconcurrency.c \
 		ptw32_calloc.c \
+		ptw32_MCS_lock.c \
 		ptw32_new.c \
 		w32_CancelableWait.c
 
diff --git a/CONTRIBUTORS b/CONTRIBUTORS
index a8838e8..e5b7325 100644
--- a/CONTRIBUTORS
+++ b/CONTRIBUTORS
@@ -76,6 +76,8 @@ Alexander Terekhov	TEREKHOV at de dot ibm dot com
 					enhancements to semaphores;
 					enhancements to mutexes;
 					new mutex implementation in 'futex' style;
+					suggested a robust implementation of pthread_once
+					similar to that implemented by V.Kliathcko;
 					system clock change handling re CV timeouts;
 					bug fixes.
 Thomas Pfaff		tpfaff at gmx dot net
@@ -122,5 +124,6 @@ Gottlob Frege		gottlobfrege at  gmail dot com
 					re-implemented pthread_once (version 2)
 					(pthread_once cancellation added by rpj).
 Vladimir Kliatchko	vladimir at kliatchko dot com
-					improvements to pthread_once (version 2)
-
+					reimplemented pthread_once with the same form
+					as described by A.Terekhov (later version 2);
+					implementation of MCS (Mellor-Crummey/Scott) locks.
diff --git a/ChangeLog b/ChangeLog
index 845cd8d..b69c039 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,26 @@
+2005-05-13  Ross Johnson  <ross at callisto.canberra.edu.au>
+
+	* pthread_kill.c (pthread_kill): Remove check for Win32 thread
+	priority (to confirm HANDLE validity). Useless since thread HANDLEs
+	a not recycle-unique.
+
+2005-05-30  Vladimir Kliatchko  <vladimir at kliatchko.com>
+
+	* pthread_once.c: Re-implement using an MCS queue-based lock. The form
+	of pthread_once is as proposed by Alexander Terekhov (see entry of
+	2005-03-13). The MCS lock implementation does not require a unique
+	'name' to identify the lock between threads. Attempts to get the Event
+	or Semaphore based versions of pthread_once to a satisfactory level
+	of robustness have thus far failed. The last problem (avoiding races
+	involving non recycle-unique Win32 HANDLEs) was giving everyone
+	grey hair trying to solve it.
+
+	* ptw32_MCS_lock.c: New MCS queue-based lock implementation. These
+	locks are efficient: they have very low overhead in the uncontended case;
+	are efficient in contention and minimise cache-coherence updates in
+	managing the user level FIFO queue; do not require an ABI change in the
+	library.
+
 2005-05-27  Alexander Gottwald <alexander.gottwald at s1999.tu-chemnitz.de>
 
 	* pthread.h: Some things, like HANDLE, were only defined if
@@ -20,8 +43,6 @@
 	built with:
 	make CC=i586-mingw32msvc-gcc RC=i586-mingw32msvc-windres \
 	RANLIB=i586-mingw32msvc-ranlib clean GC-static
-	* ptw32_relmillisecs.c (ptw32_relmillisecs): Remove INLINE qualifier
-	macro to link the GCE library.
 
 2005-05-13  Ross Johnson  <ross at callisto.canberra.edu.au>
 
diff --git a/GNUmakefile b/GNUmakefile
index 992251d..6f41a1d 100644
--- a/GNUmakefile
+++ b/GNUmakefile
@@ -213,6 +213,7 @@ SMALL_STATIC_OBJS	= \
 		pthread_timechange_handler_np.o \
 		ptw32_is_attr.o \
 		ptw32_cond_check_need_init.o \
+		ptw32_MCS_lock.o \
 		ptw32_mutex_check_need_init.o \
 		ptw32_processInitialize.o \
 		ptw32_processTerminate.o \
@@ -320,6 +321,7 @@ MISC_SRCS	= \
 		pthread_self.c \
 		pthread_setconcurrency.c \
 		ptw32_calloc.c \
+		ptw32_MCS_lock.c \
 		ptw32_new.c \
 		ptw32_reuse.c \
 		w32_CancelableWait.c
@@ -501,7 +503,7 @@ tests:
 	$(CC) -E -o $@ $(CFLAGS) $^
 
 %.s: %.c
-	$(CC) -c $(CFLAGS) -Wa,-ahl $^ > $@
+	$(CC) -c $(CFLAGS) -DPTW32_BUILD_INLINED -Wa,-ahl $^ > $@
 
 %.o: %.rc
 	$(RC) $(RCFLAGS) $(CLEANUP) -o $@ $<
diff --git a/Makefile b/Makefile
index 43ed3f7..162a08e 100644
--- a/Makefile
+++ b/Makefile
@@ -175,6 +175,7 @@ SMALL_STATIC_OBJS	= \
 		ptw32_mutex_check_need_init.obj \
 		ptw32_semwait.obj \
 		ptw32_relmillisecs.obj \
+		ptw32_MCS_lock.obj \
 		sched_get_priority_max.obj \
 		sched_get_priority_min.obj \
 		sched_setscheduler.obj \
@@ -259,6 +260,7 @@ MISC_SRCS	= \
 		pthread_self.c \
 		pthread_setconcurrency.c \
 		ptw32_calloc.c \
+		ptw32_MCS_lock.c \
 		ptw32_new.c \
 		ptw32_reuse.c \
 		ptw32_relmillisecs.c \
diff --git a/NEWS b/NEWS
index 5d8aa0d..6dd8caf 100644
--- a/NEWS
+++ b/NEWS
@@ -1,15 +1,13 @@
 RELEASE 2.7.0
 -------------
-(in CVS)
+(2005-06-04)
 
 General
 -------
-Improvements to pthread_once remove priority boosting and other
-complexity to improve robustness and efficiency.
-- Vladimir Kliatchko
-
-All other bug fixes and new features in this release have been
-back-ported in release 1.11.0.
+All new features in this release have been back-ported in release 1.11.0,
+including the incorporation of MCS locks in pthread_once, however, versions
+1 and 2 remain incompatible even though they are now identical in
+performance and functionality.
 
 Testing and verification
 ------------------------
@@ -17,6 +15,19 @@ This release has been tested (passed the test suite) on both uni-processor
 and multi-processor systems.
 - Tim Theisen
 
+Bug fixes
+---------
+Pthread_once has been re-implemented to remove priority boosting and other
+complexity to improve robustness. Races for Win32 handles that are not
+recycle-unique have been removed. The general form of pthread_once is now
+the same as that suggested earlier by Alexander Terekhov, but instead of the
+'named mutex', a queue-based lock has been implemented which has the required
+properties of dynamic self initialisation and destruction. This lock is also
+efficient. The ABI is unaffected in as much as the size of pthread_once_t has
+not changed and PTHREAD_ONCE_INIT has not changed, however, applications that
+peek inside pthread_once_t, which is supposed to be opaque, will break.
+- Vladimir Kliatchko
+
 New features
 ------------
 * Support for Mingw cross development tools added to GNUmakefile.
diff --git a/implement.h b/implement.h
index 670d948..3d96483 100644
--- a/implement.h
+++ b/implement.h
@@ -324,16 +324,21 @@ struct pthread_rwlockattr_t_
   int pshared;
 };
 
-enum ptw32_once_state {
-  PTW32_ONCE_INIT      = 0x0,
-  PTW32_ONCE_STARTED   = 0x1,
-  PTW32_ONCE_DONE      = 0x2
+/*
+ * MCS lock queue node - see ptw32_MCS_lock.c
+ */
+struct ptw32_mcs_node_t_
+{
+  struct ptw32_mcs_node_t_ **lock;        /* ptr to tail of queue */
+  struct ptw32_mcs_node_t_  *next;        /* ptr to successor in queue */
+  LONG                       readyFlag;   /* set after lock is released by
+                                             predecessor */
+  LONG                       nextFlag;    /* set after 'next' ptr is set by
+                                             successor */
 };
 
-typedef struct {
-  pthread_cond_t cond;
-  pthread_mutex_t mtx;
-} ptw32_once_control_t;
+typedef struct ptw32_mcs_node_t_   ptw32_mcs_local_node_t;
+typedef struct ptw32_mcs_node_t_  *ptw32_mcs_lock_t;
 
 
 struct ThreadKeyAssoc
@@ -612,6 +617,10 @@ extern "C"
 
   DWORD ptw32_relmillisecs (const struct timespec * abstime);
 
+  void ptw32_mcs_lock_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node);
+
+  void ptw32_mcs_lock_release (ptw32_mcs_local_node_t * node);
+
 #ifdef NEED_FTIME
   void ptw32_timespec_to_filetime (const struct timespec *ts, FILETIME * ft);
   void ptw32_filetime_to_timespec (const FILETIME * ft, struct timespec *ts);
diff --git a/manual/pthread_once.html b/manual/pthread_once.html
index ed91c20..856fb86 100644
--- a/manual/pthread_once.html
+++ b/manual/pthread_once.html
@@ -5,7 +5,7 @@
 	<TITLE>PTHREAD_ONCE(3) manual page</TITLE>
 	<META NAME="GENERATOR" CONTENT="OpenOffice.org 1.1.3  (Linux)">
 	<META NAME="CREATED" CONTENT="20050505;322600">
-	<META NAME="CHANGED" CONTENT="20050528;574400">
+	<META NAME="CHANGED" CONTENT="20050603;463100">
 	<!-- manual page source format generated by PolyglotMan v3.2, -->
 	<!-- available at http://polyglotman.sourceforge.net/ -->
 </HEAD>
@@ -39,13 +39,9 @@ nothing.
 </P>
 <H2><A HREF="#toc3" NAME="sect3">Cancellation</A></H2>
 <P>While <B>pthread_once</B> is not a cancellation point,
-<I>init_routine</I> can be. The required effect on <I>once_control</I>
-of a cancellation inside the <I>init_routine</I> is to leave it as if
-<B>pthread_once</B> had not been called.</P>
-<P>If the <I>init_routine</I> is cancelled and there are threads
-waiting on the once_control then <B>Pthreads-w32</B> wakes one of
-them so that it can re-compete along with any newly arriving threads
-in the re-running of <I>init_routine</I>.</P>
+<I>init_routine</I> can be. The effect on <I>once_control</I> of a
+cancellation inside the <I>init_routine</I> is to leave it as if
+<B>pthread_once</B> had not been called by the cancelled thread.</P>
 <H2><A HREF="#toc4" NAME="sect4">Return Value</A></H2>
 <P STYLE="text-decoration: none"><FONT COLOR="#000000"><B>pthread_once</B>
 returns 0 on success, or an error code on failure.</FONT></P>
diff --git a/private.c b/private.c
index 51b5707..7e311b1 100644
--- a/private.c
+++ b/private.c
@@ -41,6 +41,7 @@
 /* Must be first to define HAVE_INLINABLE_INTERLOCKED_CMPXCHG */
 #include "ptw32_InterlockedCompareExchange.c"
 
+#include "ptw32_MCS_lock.c"
 #include "ptw32_is_attr.c"
 #include "ptw32_processInitialize.c"
 #include "ptw32_processTerminate.c"
diff --git a/pthread.h b/pthread.h
index 00b81fe..eddbb53 100644
--- a/pthread.h
+++ b/pthread.h
@@ -652,14 +652,14 @@ enum {
  * ====================
  * ====================
  */
-#define PTHREAD_ONCE_INIT       { 0, 0, 0, 0}
+#define PTHREAD_ONCE_INIT       { PTW32_FALSE, 0, 0, 0}
 
 struct pthread_once_t_
 {
-  int          state;        /* indicates if user function has been executed */
-  int          reserved;
-  int          numSemaphoreUsers;
-  HANDLE       semaphore;
+  int          done;        /* indicates if user function has been executed */
+  void *       lock;
+  int          reserved1;
+  int          reserved2;
 };
 
 
diff --git a/pthread_kill.c b/pthread_kill.c
index 5a795dd..7de3fe2 100644
--- a/pthread_kill.c
+++ b/pthread_kill.c
@@ -82,8 +82,7 @@ pthread_kill (pthread_t thread, int sig)
 
   if (NULL == tp
       || thread.x != tp->ptHandle.x
-      || NULL == tp->threadH
-      || THREAD_PRIORITY_ERROR_RETURN == GetThreadPriority (tp->threadH))
+      || NULL == tp->threadH)
     {
       result = ESRCH;
     }
diff --git a/pthread_once.c b/pthread_once.c
index 39ddcce..aa09d99 100644
--- a/pthread_once.c
+++ b/pthread_once.c
@@ -39,147 +39,48 @@
 
 
 static void PTW32_CDECL
-ptw32_once_init_routine_cleanup(void * arg)
+ptw32_once_on_init_cancel (void * arg)
 {
-  pthread_once_t * once_control = (pthread_once_t *) arg;
-
-  (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state, (LONG)PTW32_ONCE_INIT);
-
-  if (InterlockedExchangeAdd((LPLONG)&once_control->semaphore, 0L)) /* MBR fence */
-    {
-      ReleaseSemaphore(once_control->semaphore, 1, NULL);
-    }
+  /* when the initting thread is cancelled we have to release the lock */
+  ptw32_mcs_local_node_t *node = (ptw32_mcs_local_node_t *)arg;
+  ptw32_mcs_lock_release(node);
 }
 
 int
 pthread_once (pthread_once_t * once_control, void (*init_routine) (void))
-     /*
-      * ------------------------------------------------------
-      * DOCPUBLIC
-      *      If any thread in a process  with  a  once_control  parameter
-      *      makes  a  call to pthread_once(), the first call will summon
-      *      the init_routine(), but  subsequent  calls  will  not. The
-      *      once_control  parameter  determines  whether  the associated
-      *      initialization routine has been called.  The  init_routine()
-      *      is complete upon return of pthread_once().
-      *      This function guarantees that one and only one thread
-      *      executes the initialization routine, init_routine when
-      *      access is controlled by the pthread_once_t control
-      *      key.
-      *
-      *      pthread_once() is not a cancelation point, but the init_routine
-      *      can be. If it's cancelled then the effect on the once_control is
-      *      as if pthread_once had never been entered.
-      *
-      *
-      * PARAMETERS
-      *      once_control
-      *              pointer to an instance of pthread_once_t
-      *
-      *      init_routine
-      *              pointer to an initialization routine
-      *
-      *
-      * DESCRIPTION
-      *      See above.
-      *
-      * RESULTS
-      *              0               success,
-      *              EINVAL          once_control or init_routine is NULL
-      *
-      * ------------------------------------------------------
-      */
 {
-  int result;
-  int state;
-  HANDLE sema;
-
   if (once_control == NULL || init_routine == NULL)
     {
-      result = EINVAL;
-      goto FAIL0;
+      return EINVAL;
     }
-  else
+  
+  if (!InterlockedExchangeAdd((LPLONG)&once_control->done, 0)) /* MBR fence */
     {
-      result = 0;
-    }
+      ptw32_mcs_local_node_t node;
 
-  while ((state =
-	  PTW32_INTERLOCKED_COMPARE_EXCHANGE((PTW32_INTERLOCKED_LPLONG)&once_control->state,
-					     (PTW32_INTERLOCKED_LONG)PTW32_ONCE_STARTED,
-					     (PTW32_INTERLOCKED_LONG)PTW32_ONCE_INIT))
-	 != PTW32_ONCE_DONE)
-    {
-      if (PTW32_ONCE_INIT == state)
-        {
+      ptw32_mcs_lock_acquire((ptw32_mcs_lock_t *)&once_control->lock, &node);
+
+      if (!InterlockedExchangeAdd((LPLONG)&once_control->done, 0L))
+	{
 
 #ifdef _MSC_VER
 #pragma inline_depth(0)
 #endif
 
-          pthread_cleanup_push(ptw32_once_init_routine_cleanup, (void *) once_control);
-          (*init_routine)();
-          pthread_cleanup_pop(0);
+	  pthread_cleanup_push(ptw32_once_on_init_cancel, (void *)&node);
+	  (*init_routine)();
+	  pthread_cleanup_pop(0);
 
 #ifdef _MSC_VER
 #pragma inline_depth()
 #endif
 
-          (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->state, 
-                                            (LONG)PTW32_ONCE_DONE);
-
-          /*
-           * we didn't create the semaphore.
-           * it is only there if there is someone waiting.
-           */
-          if (InterlockedExchangeAdd((LPLONG)&once_control->semaphore, 0L)) /* MBR fence */
-            {
-              ReleaseSemaphore(once_control->semaphore, 
-                               once_control->numSemaphoreUsers, NULL);
-            }
-        }
-      else
-        {
-          InterlockedIncrement((LPLONG)&once_control->numSemaphoreUsers);
-
-          if (!InterlockedExchangeAdd((LPLONG)&once_control->semaphore, 0L)) /* MBR fence */
-            {
-              sema = CreateSemaphore(NULL, 0, INT_MAX, NULL);
+	  (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->done, (LONG)PTW32_TRUE);
+	}
 
-              if (PTW32_INTERLOCKED_COMPARE_EXCHANGE((PTW32_INTERLOCKED_LPLONG)&once_control->semaphore,
-						     (PTW32_INTERLOCKED_LONG)sema,
-						     (PTW32_INTERLOCKED_LONG)0))
-                {
-                  CloseHandle(sema);
-                }
-            }
-
-          /*
-           * Check 'state' again in case the initting thread has finished or
-	   * cancelled and left before seeing that there was a semaphore.
-           */
-          if (InterlockedExchangeAdd((LPLONG)&once_control->state, 0L) == PTW32_ONCE_STARTED)
-            {
-              WaitForSingleObject(once_control->semaphore, INFINITE);
-            }
-
-          if (0 == InterlockedDecrement((LPLONG)&once_control->numSemaphoreUsers))
-            {
-              /* we were last */
-              if ((sema =
-		   (HANDLE) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->semaphore, (LONG)0)))
-                {
-                  CloseHandle(sema);
-                }
-            }
-        }
+	ptw32_mcs_lock_release(&node);
     }
 
-  /*
-   * ------------
-   * Failure Code
-   * ------------
-   */
-FAIL0:
-  return (result);
-}                               /* pthread_once */
+  return 0;
+
+}				/* pthread_once */
diff --git a/ptw32_MCS_lock.c b/ptw32_MCS_lock.c
new file mode 100644
index 0000000..478a059
--- /dev/null
+++ b/ptw32_MCS_lock.c
@@ -0,0 +1,210 @@
+/*
+ * 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 recourses transiently -
+ * they are able to acquire and free recourses 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((LPLONG)lock,
+						              (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, 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);
+}
diff --git a/ptw32_relmillisecs.c b/ptw32_relmillisecs.c
index 7031148..f3e7b76 100644
--- a/ptw32_relmillisecs.c
+++ b/ptw32_relmillisecs.c
@@ -44,7 +44,7 @@
 #endif
 
 
-DWORD
+INLINE DWORD
 ptw32_relmillisecs (const struct timespec * abstime)
 {
   const int64_t NANOSEC_PER_MILLISEC = 1000000;
diff --git a/tests/Bmakefile b/tests/Bmakefile
index b56c18f..c1c5805 100644
--- a/tests/Bmakefile
+++ b/tests/Bmakefile
@@ -91,7 +91,8 @@ PASSES=   loadfree.pass \
 	  mutex6s.pass  mutex6es.pass  mutex6rs.pass  \
 	  mutex7.pass  mutex7n.pass  mutex7e.pass  mutex7r.pass  \
 	  mutex8.pass  mutex8n.pass  mutex8e.pass  mutex8r.pass  \
-	  count1.pass  once1.pass  once2.pass  once3.pass  once4.pass  \
+	  count1.pass  \
+	  once1.pass  once2.pass  once3.pass  once4.pass  \
 	  self2.pass  \
 	  cancel1.pass  cancel2.pass  \
 	  semaphore4.pass  semaphore4t.pass  \
diff --git a/tests/ChangeLog b/tests/ChangeLog
index 9b00fa3..b3784e4 100644
--- a/tests/ChangeLog
+++ b/tests/ChangeLog
@@ -1,3 +1,8 @@
+2005-06-02  Ross Johnson  <rpj@callisto.canberra.edu.au>
+
+	* mcs1.c: New test for MCS queue-based locks.
+	* mcs2.c: Likewise.
+
 2005-05-18  Ross Johnson  <rpj@callisto.canberra.edu.au>
 
 	* reuse2.c (main): Must use a read with memory barrier semantics
diff --git a/tests/GNUmakefile b/tests/GNUmakefile
index fb28a53..31a514e 100644
--- a/tests/GNUmakefile
+++ b/tests/GNUmakefile
@@ -86,7 +86,8 @@ TESTS	= sizes loadfree \
 	  mutex4 mutex6 mutex6n mutex6e mutex6r \
 	  mutex6s mutex6es mutex6rs \
 	  mutex7 mutex7n mutex7e mutex7r mutex8 mutex8n mutex8e mutex8r \
-	  count1 once1 once2 once3 once4 self2 \
+	  count1 \
+	  once1 once2 once3 once4 self2 \
 	  cancel1 cancel2 \
 	  semaphore4 semaphore4t \
 	  barrier1 barrier2 barrier3 barrier4 barrier5 \
diff --git a/tests/Makefile b/tests/Makefile
index 6dc222e..a1af003 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -95,7 +95,8 @@ PASSES= sizes.pass  loadfree.pass \
 	  mutex6s.pass  mutex6es.pass  mutex6rs.pass  \
 	  mutex7.pass  mutex7n.pass  mutex7e.pass  mutex7r.pass  \
 	  mutex8.pass  mutex8n.pass  mutex8e.pass  mutex8r.pass  \
-	  count1.pass  once1.pass  once2.pass  once3.pass  once4.pass  \
+	  count1.pass  \
+	  once1.pass  once2.pass  once3.pass  once4.pass  \
 	  self2.pass  \
 	  cancel1.pass  cancel2.pass  \
 	  semaphore4.pass  semaphore4t.pass  \
diff --git a/tests/Wmakefile b/tests/Wmakefile
index fa11dc5..06a755c 100644
--- a/tests/Wmakefile
+++ b/tests/Wmakefile
@@ -91,7 +91,8 @@ PASSES	= sizes.pass  loadfree.pass &
 	  mutex6s.pass  mutex6es.pass  mutex6rs.pass  &
 	  mutex7.pass  mutex7n.pass  mutex7e.pass  mutex7r.pass  &
 	  mutex8.pass  mutex8n.pass  mutex8e.pass  mutex8r.pass  &
-	  count1.pass  once1.pass  once2.pass  once3.pass  once4.pass  tsd1.pass  &
+	  count1.pass  &
+	  once1.pass  once2.pass  once3.pass  once4.pass  tsd1.pass  &
 	  self2.pass  &
 	  cancel1.pass  cancel2.pass  &
 	  semaphore4.pass semaphore4t.pass  &
diff --git a/tests/sizes.c b/tests/sizes.c
index 6c077ad..73c7261 100644
--- a/tests/sizes.c
+++ b/tests/sizes.c
@@ -24,6 +24,7 @@ main()
   printf("%30s %4d\n", "pthread_rwlockattr_t_", sizeof(struct pthread_rwlockattr_t_));
   printf("%30s %4d\n", "pthread_once_t_", sizeof(struct pthread_once_t_));
   printf("%30s %4d\n", "ptw32_cleanup_t", sizeof(struct ptw32_cleanup_t));
+  printf("%30s %4d\n", "ptw32_mcs_node_t_", sizeof(struct ptw32_mcs_node_t_));
   printf("%30s %4d\n", "sched_param", sizeof(struct sched_param));
   printf("-------------------------------\n");