diff options
Diffstat (limited to 'pthreads/ptw32_MCS_lock.c')
| -rw-r--r-- | pthreads/ptw32_MCS_lock.c | 541 |
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; + } +} |