15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_MCS_lock.c 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Description: 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * This translation unit implements queue-based locks. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * -------------------------------------------------------------------------- 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Pthreads-win32 - POSIX Threads Library for Win32 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright(C) 1998 John E. Bossom 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright(C) 1999,2005 Pthreads-win32 contributors 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Contact Email: rpj@callisto.canberra.edu.au 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The current list of contributors is contained 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * in the file CONTRIBUTORS included with the source 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * code distribution. The list can also be seen at the 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * following World Wide Web location: 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * http://sources.redhat.com/pthreads-win32/contributors.html 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * This library is free software; you can redistribute it and/or 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * modify it under the terms of the GNU Lesser General Public 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * License as published by the Free Software Foundation; either 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * version 2 of the License, or (at your option) any later version. 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * This library is distributed in the hope that it will be useful, 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * but WITHOUT ANY WARRANTY; without even the implied warranty of 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Lesser General Public License for more details. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * You should have received a copy of the GNU Lesser General Public 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * License along with this library in the file COPYING.LIB; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * if not, write to the Free Software Foundation, Inc., 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * About MCS locks: 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * MCS locks are queue-based locks, where the queue nodes are local to the 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * thread. The 'lock' is nothing more than a global pointer that points to 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the last node in the queue, or is NULL if the queue is empty. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Originally designed for use as spin locks requiring no kernel resources 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * for synchronisation or blocking, the implementation below has adapted 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the MCS spin lock for use as a general mutex that will suspend threads 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * when there is lock contention. 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Because the queue nodes are thread-local, most of the memory read/write 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * operations required to add or remove nodes from the queue do not trigger 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * cache-coherence updates. 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Like 'named' mutexes, MCS locks consume system resources transiently - 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * they are able to acquire and free resources automatically - but MCS 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * locks do not require any unique 'name' to identify the lock to all 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * threads using it. 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Usage of MCS locks: 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - you need a global ptw32_mcs_lock_t instance initialised to 0 or NULL. 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - you need a local thread-scope ptw32_mcs_local_node_t instance, which 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * may serve several different locks but you need at least one node for 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * every lock held concurrently by a thread. 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * E.g.: 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_t lock1 = 0; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_t lock2 = 0; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * void *mythread(void *arg) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_local_node_t node; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_acquire (&lock1, &node); 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_release (&node); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_acquire (&lock2, &node); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_release (&node); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * { 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_local_node_t nodex; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_acquire (&lock1, &node); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_acquire (&lock2, &nodex); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_release (&nodex); 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_release (&node); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * } 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * return (void *)0; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * } 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "pthread.h" 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sched.h" 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "implement.h" 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_flag_set -- notify another thread about an event. 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Set event if an event handle has been stored in the flag, and 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * set flag to -1 otherwise. Note that -1 cannot be a valid handle value. 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)INLINE void 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ptw32_mcs_flag_set (HANDLE * flag) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HANDLE e = (HANDLE)(PTW32_INTERLOCKED_SIZE)PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE( 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_SIZEPTR)flag, 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_SIZE)-1, 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_SIZE)0); 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((HANDLE)0 != e) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* another thread has already stored an event handle in the flag */ 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SetEvent(e); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_flag_set -- wait for notification from another. 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Store an event handle in the flag and wait on it if the flag has not been 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * set, and proceed without creating an event otherwise. 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)INLINE void 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ptw32_mcs_flag_wait (HANDLE * flag) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((PTW32_INTERLOCKED_LONG)0 == 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)flag, 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_SIZE)0)) /* MBR fence */ 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* the flag is not set. create event. */ 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HANDLE e = CreateEvent(NULL, PTW32_FALSE, PTW32_FALSE, NULL); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((PTW32_INTERLOCKED_SIZE)0 == PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE( 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_SIZEPTR)flag, 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_SIZE)e, 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_SIZE)0)) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* stored handle in the flag. wait on it now. */ 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WaitForSingleObject(e, INFINITE); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CloseHandle(e); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_acquire -- acquire an MCS lock. 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * See: 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * J. M. Mellor-Crummey and M. L. Scott. 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991. 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(PTW32_BUILD_INLINED) 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)INLINE 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* PTW32_BUILD_INLINED */ 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ptw32_mcs_lock_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptw32_mcs_local_node_t *pred; 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node->lock = lock; 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node->nextFlag = 0; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node->readyFlag = 0; 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node->next = 0; /* initially, no successor */ 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* queue for the lock */ 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred = (ptw32_mcs_local_node_t *)PTW32_INTERLOCKED_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock, 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_PVOID)node); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (0 != pred) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* the lock was not free. link behind predecessor. */ 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred->next = node; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptw32_mcs_flag_set(&pred->nextFlag); 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptw32_mcs_flag_wait(&node->readyFlag); 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_release -- release an MCS lock. 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * See: 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * J. M. Mellor-Crummey and M. L. Scott. 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991. 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(PTW32_BUILD_INLINED) 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)INLINE 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* PTW32_BUILD_INLINED */ 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ptw32_mcs_lock_release (ptw32_mcs_local_node_t * node) 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptw32_mcs_lock_t *lock = node->lock; 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptw32_mcs_local_node_t *next = 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (ptw32_mcs_local_node_t *) 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)&node->next, (PTW32_INTERLOCKED_SIZE)0); /* MBR fence */ 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (0 == next) 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* no known successor */ 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (node == (ptw32_mcs_local_node_t *) 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock, 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_PVOID)0, 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_PVOID)node)) 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* no successor, lock is free now */ 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* A successor has started enqueueing behind us so wait for them to link to us */ 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptw32_mcs_flag_wait(&node->nextFlag); 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next = (ptw32_mcs_local_node_t *) 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PTW32_INTERLOCKED_EXCHANGE_ADD_SIZE((PTW32_INTERLOCKED_SIZEPTR)&node->next, (PTW32_INTERLOCKED_SIZE)0); /* MBR fence */ 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* pass the lock */ 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptw32_mcs_flag_set(&next->readyFlag); 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_lock_try_acquire 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(PTW32_BUILD_INLINED) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)INLINE 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* PTW32_BUILD_INLINED */ 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ptw32_mcs_lock_try_acquire (ptw32_mcs_lock_t * lock, ptw32_mcs_local_node_t * node) 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node->lock = lock; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node->nextFlag = 0; 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node->readyFlag = 0; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node->next = 0; /* initially, no successor */ 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ((PTW32_INTERLOCKED_PVOID)PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)lock, 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_PVOID)node, 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_PVOID)0) 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) == (PTW32_INTERLOCKED_PVOID)0) ? 0 : EBUSY; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ptw32_mcs_node_transfer -- move an MCS lock local node, usually from thread 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * space to, for example, global space so that another thread can release 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the lock on behalf of the current lock owner. 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Example: used in pthread_barrier_wait where we want the last thread out of 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the barrier to release the lock owned by the last thread to enter the barrier 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * (the one that releases all threads but not necessarily the last to leave). 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Should only be called by the thread that has the lock. 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(PTW32_BUILD_INLINED) 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)INLINE 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* PTW32_BUILD_INLINED */ 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ptw32_mcs_node_transfer (ptw32_mcs_local_node_t * new_node, ptw32_mcs_local_node_t * old_node) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_node->lock = old_node->lock; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_node->nextFlag = 0; /* Not needed - used only in initial Acquire */ 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_node->readyFlag = 0; /* Not needed - we were waiting on this */ 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_node->next = 0; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((ptw32_mcs_local_node_t *)PTW32_INTERLOCKED_COMPARE_EXCHANGE_PTR((PTW32_INTERLOCKED_PVOID_PTR)new_node->lock, 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_PVOID)new_node, 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (PTW32_INTERLOCKED_PVOID)old_node) 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) != old_node) 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * A successor has queued after us, so wait for them to link to us 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (old_node->next == 0) 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sched_yield(); 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_node->next = old_node->next; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 279