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