''

17 files changed, 290 insertions, 220 deletions

diff --git a/ANNOUNCE b/ANNOUNCE
index d9f79aa..21beb7b 100644
--- a/ANNOUNCE
+++ b/ANNOUNCE
@@ -1,4 +1,4 @@
-	     PTHREADS-WIN32 RELEASE 1.10.0 (2005-05-19)
+	     PTHREADS-WIN32 RELEASE 1.11.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 608269e..097fafa 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
 
@@ -211,8 +212,8 @@ TSD_SRCS	= \
 all: clean $(DLLS)
 
 realclean: clean
-	if exist *.dll del *.dll
-	if exist *.lib del *.lib
+	if exist pthread*.dll del pthread*.dll
+	if exist pthread*.lib del pthread*.lib
 	if exist *.stamp del *.stamp
 
 clean:
diff --git a/ChangeLog b/ChangeLog
index ee36470..26a6415 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,23 @@
+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. Removes the global mutex
+	and global condvar used to manage cancellation of the once_init routine.
+
+	* 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
@@ -11,8 +31,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 a8d3639..df40b8f 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 bad1b71..05501ea 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 bf301e9..e1255be 100644
--- a/NEWS
+++ b/NEWS
@@ -1,14 +1,19 @@
 RELEASE 1.11.0
 -------------
-(in CVS)
+(2005-06-04)
 
 General
 -------
+Pthread_once has been re-implemented using the same MCS lock implementation
+as version 2.7.0. The size of pthread_once_t has not changed and the
+initialisation values in PTHREAD_ONCE_INIT have not changed. However,
+applications that peek inside pthread_once_t, which is meant to be opaque,
+will break. Versions 1 and 2 remain incompatible even though they are
+now identical in performance and functionality.
+
 This release is a back-port of the bug fixes and new features in release
 2.7.0. To date, version 1 releases remain fully functionally equivalent to
-version 2 releases, including all bug fixes and enhanced compliance. The
-difference is that the version 1 pthread_once routine may be significantly
-less efficient in some situations.
+version 2 releases, including all bug fixes and improved compliance.
 
 Testing and verification
 ------------------------
diff --git a/global.c b/global.c
index 8c92a18..2b55422 100644
--- a/global.c
+++ b/global.c
@@ -107,15 +107,6 @@ CRITICAL_SECTION ptw32_spinlock_test_init_lock;
  */
 CRITICAL_SECTION ptw32_cond_list_lock;
 
-/*
- * Global condition variable and mutex for once_control management.
- */
-ptw32_once_control_t ptw32_once_control =
-  {
-    PTHREAD_COND_INITIALIZER,
-    PTHREAD_MUTEX_INITIALIZER
-  };
-
 #ifdef _UWIN
 /*
  * Keep a count of the number of threads.
diff --git a/implement.h b/implement.h
index 2e883a8..3d96483 100644
--- a/implement.h
+++ b/implement.h
@@ -92,7 +92,7 @@ typedef VOID (APIENTRY *PAPCFUNC)(DWORD dwParam);
 
 #if defined(__MINGW32__)
 #include <stdint.h>
-#elif defined(__BORLANDC__) || defined(__WATCOMC__)
+#elif defined(__BORLANDC__)
 #define int64_t ULONGLONG
 #else
 #define int64_t _int64
@@ -325,23 +325,20 @@ struct pthread_rwlockattr_t_
 };
 
 /*
- * Values stored in once_control->done.
- * 'done' use to be just true or false, but we can add cancellability
- * of the init_routine by re-using 'done' to store multiple flags
- * without changing the ABI. Previously, the initial value of 'done'
- * was FALSE (0), and the new initial value is still zero (0).
+ * MCS lock queue node - see ptw32_MCS_lock.c
  */
-enum {
-  PTW32_ONCE_CLEAR = 0x0,
-  PTW32_ONCE_DONE = 0x1,
-  PTW32_ONCE_CANCELLED = 0x2
+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 */
 };
 
-/* Global cond+mutex for once_control management */
-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
@@ -546,7 +543,6 @@ extern CRITICAL_SECTION ptw32_cond_list_lock;
 extern CRITICAL_SECTION ptw32_cond_test_init_lock;
 extern CRITICAL_SECTION ptw32_rwlock_test_init_lock;
 extern CRITICAL_SECTION ptw32_spinlock_test_init_lock;
-extern ptw32_once_control_t ptw32_once_control;
 
 #ifdef _UWIN
 extern int pthread_count;
@@ -621,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 1497c38..f901459 100644
--- a/pthread.h
+++ b/pthread.h
@@ -656,8 +656,8 @@ enum {
 
 struct pthread_once_t_
 {
-  volatile int done;        /* indicates if user function has been executed or cancelled  */
-  int          started;
+  void * lock;
+  int    done;   /* indicates if user function has been executed or cancelled  */
 };
 
 
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 62b412c..efcfd0f 100644
--- a/pthread_once.c
+++ b/pthread_once.c
@@ -38,204 +38,49 @@
 #include "implement.h"
 
 
-static void
-ptw32_once_init_routine_cleanup(void * arg)
+static void PTW32_CDECL
+ptw32_once_on_init_cancel (void * arg)
 {
-  pthread_once_t * once_control = (pthread_once_t *) arg;
-
-  (void) pthread_mutex_lock(&ptw32_once_control.mtx);
-  once_control->done = PTW32_ONCE_CANCELLED;
-  (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->started, -1L);
-  /*
-   * Wake everyone up.
-   *
-   * Holding the mutex during the broadcast prevents threads being left
-   * behind waiting.
-   */
-  (void) pthread_cond_broadcast(&ptw32_once_control.cond);
-  (void) pthread_mutex_unlock(&ptw32_once_control.mtx);
+  /* 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;
-  LONG state;
-  pthread_t self;
-  HANDLE w32Thread = 0;
-
   if (once_control == NULL || init_routine == NULL)
     {
-
-      result = EINVAL;
-      goto FAIL0;
-
-    }
-  else
-    {
-      result = 0;
+      return EINVAL;
     }
-
-  /*
-   * Use a single global cond+mutex to manage access to all once_control objects.
-   * Unlike a global mutex on it's own, the global cond+mutex allows faster
-   * once_controls to overtake slower ones. Spurious wakeups may occur, but
-   * can be tolerated.
-   *
-   * Since this is being introduced as a bug fix, the global cond+mtx also avoids
-   * a change in the ABI, maintaining backwards compatibility.
-   *
-   * To maintain a separate mutex for each once_control object requires either
-   * cleaning up the mutex (difficult to synchronise reliably), or leaving it
-   * around forever. Since we can't make assumptions about how an application might
-   * employ pthread_once objects, the later is considered to be unacceptable.
-   *
-   * once_control->done is now a multipurpose flag. It indicates either that
-   * the init_routine has been completed, or the thread running it has been cancelled.
-   *
-   * Priority boosting is used to ensure that the init_routine thread is not
-   * starved, by higher priority threads inside the while loop, before it can
-   * clear the cancelled flag. The init_routine will be run at the thread's
-   * normal base priority. Note that priority boosting is momentary, independent
-   * for each once_control, and occurs only AFTER an init_routine cancellation.
-   */
-
-  while (!((state = InterlockedExchangeAdd((LPLONG)&once_control->done, 0L)) /* Full mem barrier read */
-	   & PTW32_ONCE_DONE))
+  
+  if (InterlockedExchangeAdd((LPLONG)&once_control->done, 0L)) /* MBR fence */
     {
-      /*
-       * Keep a per thread record of the cancelled state for speed. If the
-       * once_control state changes before we've finished with our local copy
-       * then no harm is done - in fact, we need it to complete the full priority
-       * boost transaction.
-       */
-      LONG cancelled = (state & PTW32_ONCE_CANCELLED);
+      ptw32_mcs_local_node_t node;
 
-      if (cancelled)
-	{
-	  /* Boost priority momentarily */
-	  if (!w32Thread)
-	    {
-	      self = pthread_self();
-	      w32Thread = ((ptw32_thread_t *)self.p)->threadH;
-	    }
-	  /* Prevent pthread_setschedparam() changing our priority while we're boosted. */
-	  (void) pthread_mutex_lock(&((ptw32_thread_t *)self.p)->threadLock);
-	  SetThreadPriority(w32Thread, THREAD_PRIORITY_HIGHEST);
-	}
+      ptw32_mcs_lock_acquire((ptw32_mcs_lock_t *)&once_control->lock, &node);
 
-      if (PTW32_INTERLOCKED_EXCHANGE((LPLONG) &once_control->started, 0L) == -1)
+      if (InterlockedExchangeAdd((LPLONG)&once_control->done, 0L))
 	{
-	  if (cancelled)
-	    {
-	      /* Reset cancelled state */
-	      (void) pthread_mutex_lock(&ptw32_once_control.mtx);
-	      once_control->done = PTW32_ONCE_CLEAR;
-	      (void) pthread_mutex_unlock(&ptw32_once_control.mtx);
-
-	      /*
-	       * Restore priority - any priority changes since the thread was created
-	       * will be applied only if they were made via POSIX (i.e. pthread_setschedparam).
-	       */
-	      SetThreadPriority(w32Thread, ((ptw32_thread_t *)self.p)->sched_priority);
-	      (void) pthread_mutex_unlock(&((ptw32_thread_t *)self.p)->threadLock);
-	    }
 
 #ifdef _MSC_VER
 #pragma inline_depth(0)
 #endif
 
-	  pthread_cleanup_push(ptw32_once_init_routine_cleanup, (void*) once_control);
-	  (*init_routine) ();
+	  pthread_cleanup_push(ptw32_once_on_init_cancel, (void *)&node);
+	  (*init_routine)();
 	  pthread_cleanup_pop(0);
 
 #ifdef _MSC_VER
 #pragma inline_depth()
 #endif
 
-	  /*
-	   * Holding the mutex during the broadcast prevents threads being left
-	   * behind waiting.
-	   */
-	  (void) pthread_mutex_lock(&ptw32_once_control.mtx);
-	  once_control->done = PTW32_ONCE_DONE;
-	  (void) pthread_cond_broadcast(&ptw32_once_control.cond);
-	  (void) pthread_mutex_unlock(&ptw32_once_control.mtx);
+	  (void) PTW32_INTERLOCKED_EXCHANGE((LPLONG)&once_control->done, 0L);
 	}
-      else
-	{
-	  int oldCancelState;
-
-	  if (cancelled)
-	    {
-	      /*
-	       * Restore priority - any priority changes since the thread was created
-	       * will be applied only if they were made via POSIX (i.e. pthread_setschedparam).
-	       */
-	      SetThreadPriority(w32Thread, ((ptw32_thread_t *)self.p)->sched_priority);
-	      (void) pthread_mutex_unlock(&((ptw32_thread_t *)self.p)->threadLock);
-	    }
 
-	  pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &oldCancelState);
-	  (void) pthread_mutex_lock(&ptw32_once_control.mtx);
-	  while (!once_control->done /* Neither DONE nor CANCELLED */
-		 || (!(once_control->done & PTW32_ONCE_DONE)
-		     && cancelled) /* Stop after one init_routine re-contest */)
-	    {
-	      cancelled = 0;
-	      (void) pthread_cond_wait(&ptw32_once_control.cond, &ptw32_once_control.mtx);
-	    }
-	  (void) pthread_mutex_unlock(&ptw32_once_control.mtx);
-	  pthread_setcancelstate(oldCancelState, NULL);
-	}
+	ptw32_mcs_lock_release(&node);
     }
 
-  /*
-   * Fall through Intentionally
-   */
-
-  /*
-   * ------------
-   * Failure Code
-   * ------------
-   */
-FAIL0:
-  return (result);
+  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_processTerminate.c b/ptw32_processTerminate.c
index f80b99b..d2dfa7a 100644
--- a/ptw32_processTerminate.c
+++ b/ptw32_processTerminate.c
@@ -101,7 +101,6 @@ ptw32_processTerminate (void)
       /* 
        * Destroy the global locks and other objects.
        */
-      DeleteCriticalSection (&ptw32_once_event_lock);
       DeleteCriticalSection (&ptw32_spinlock_test_init_lock);
       DeleteCriticalSection (&ptw32_rwlock_test_init_lock);
       DeleteCriticalSection (&ptw32_cond_test_init_lock);
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/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");