/*
* 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 "pthread.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 (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);
}