summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ANNOUNCE2
-rw-r--r--Bmakefile1
-rw-r--r--CONTRIBUTORS7
-rw-r--r--ChangeLog25
-rw-r--r--GNUmakefile4
-rw-r--r--Makefile2
-rw-r--r--NEWS25
-rw-r--r--implement.h25
-rw-r--r--manual/pthread_once.html12
-rw-r--r--private.c1
-rw-r--r--pthread.h10
-rw-r--r--pthread_kill.c3
-rw-r--r--pthread_once.c141
-rw-r--r--ptw32_MCS_lock.c210
-rw-r--r--ptw32_relmillisecs.c2
-rw-r--r--tests/Bmakefile3
-rw-r--r--tests/ChangeLog5
-rw-r--r--tests/GNUmakefile3
-rw-r--r--tests/Makefile3
-rw-r--r--tests/Wmakefile3
-rw-r--r--tests/sizes.c1
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");