pthreads.zip

/* * ptw32_OLL_lock.c * * Description: * This translation unit implements extended reader/writer 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 the OLL lock (Scalable Reader-Writer Lock): * * OLL locks are queue-based locks similar to the MCS queue lock, where the queue * nodes are local to the thread but where reader threads can enter the critical * section immediately without going through a central guard lock if there are * already readers holding the lock. * * Covered by United States Patent Application 20100241774 (Oracle) */ #include "pthread.h" #include "sched.h" #include "implement.h" /* * C-SNZI support */ typedef union ptw32_oll_counter_t_ ptw32_oll_counter_t; typedef struct ptw32_oll_snziRoot_t_ ptw32_oll_snziRoot_t; typedef struct ptw32_oll_snziNode_t_ ptw32_oll_snziNode_t; typedef union ptw32_oll_snziNodeOrRoot_t_ ptw32_oll_snziNodeOrRoot_t; typedef struct ptw32_oll_queryResult_t_ ptw32_oll_queryResult_t; typedef struct ptw32_oll_ticket_t_ ptw32_oll_ticket_t; typedef struct ptw32_oll_csnzi_t_ ptw32_oll_csnzi_t; enum { ptw32_archWidth = sizeof(size_t)*8, ptw32_oll_countWidth = ptw32_archWidth-2 }; #define PTW32_OLL_MAXREADERS (((size_t)2<<(ptw32_oll_countWidth-1))-1) union ptw32_oll_counter_t_ { size_t word : ptw32_archWidth; struct { /* * This needs to be a single word * * ------------------------------------ * | STATE | ROOT | COUNT (readers) | * ------------------------------------ * 63 / 31 62 / 30 61 / 29 .. 0 */ size_t count : ptw32_oll_countWidth; size_t root : 1; /* ROOT or NODE */ size_t state : 1; /* OPEN or CLOSED (root only) */ } internal; }; struct ptw32_oll_snziRoot_t_ { /* * "counter" must be at same offset in both * ptw32_oll_snziNode_t and ptw32_oll_snziRoot_t */ ptw32_oll_counter_t counter; }; enum { ptw32_oll_snziRoot_open = 0, ptw32_oll_snziRoot_closed = 1 }; enum { ptw32_oll_snzi_root = 0, ptw32_oll_snzi_node = 1 }; /* * Some common SNZI root whole-word states that can be used to set or compare * root words with a single operation. */ ptw32_oll_snziRoot_t ptw32_oll_snziRoot_openAndZero = {.counter.internal.count = 0, .counter.internal.root = ptw32_oll_snzi_root, .counter.internal.state = ptw32_oll_snziRoot_open}; ptw32_oll_snziRoot_t ptw32_oll_snziRoot_closedAndZero = {.counter.internal.count = 0, .counter.internal.root = ptw32_oll_snzi_root, .counter.internal.state = ptw32_oll_snziRoot_closed}; struct ptw32_oll_queryResult_t_ { BOOL nonZero; BOOL open; }; union ptw32_oll_snziNodeOrRoot_t_ { ptw32_oll_snziRoot_t* rootPtr; ptw32_oll_snziNode_t* nodePtr; }; struct ptw32_oll_snziNode_t_ { /* "counter" must be at same offset in both * ptw32_oll_snziNode_t and ptw32_oll_snziRoot_t */ ptw32_oll_counter_t counter; ptw32_oll_snziNodeOrRoot_t parentPtr; }; struct ptw32_oll_ticket_t_ { ptw32_oll_snziNodeOrRoot_t snziNodeOrRoot; }; ptw32_oll_ticket_t ptw32_oll_ticket_null = {NULL}; struct ptw32_oll_csnzi_t_ { ptw32_oll_snziRoot_t proxyRoot; ptw32_oll_snziNode_t leafs[]; }; /* * FOLL lock support */ typedef struct ptw32_foll_node_t_ ptw32_foll_node_t; typedef struct ptw32_foll_local_t_ ptw32_foll_local_t; typedef struct ptw32_foll_rwlock_t_ ptw32_foll_rwlock_t; enum { ptw32_srwl_reader, ptw32_srwl_writer }; enum { ptw32_srwl_free, ptw32_srwl_in_use }; struct ptw32_foll_node_t_ { ptw32_foll_node_t* qNextPtr; ptw32_oll_csnzi_t* csnziPtr; ptw32_foll_node_t* nextPtr; int kind; int allocState; BOOL spin; }; struct ptw32_foll_local_t_ { ptw32_foll_node_t* rNodePtr; // Default read node. Immutable ptw32_foll_node_t* wNodePtr; // Write node. Immutable. ptw32_foll_node_t* departFromPtr; // List node we last arrived at. ptw32_oll_ticket_t ticket; // C-SNZI ticket }; struct ptw32_foll_rwlock_t_ { ptw32_foll_node_t* tailPtr; ptw32_foll_node_t* rNodesPtr; // Head of reader node }; /* * ShouldArriveAtTree() returns true if: * the compare_exchange in Arrive() fails too often under read access; or * ?? * Note that this is measured across all access to * this lock, not just this attempt, so that highly * read-contended locks will use C-SNZI. Lightly * read-contended locks can reduce memory usage and some * processing by using the root directly. */ BOOL ptw32_oll_ShouldArriveAtTree() { return PTW32_FALSE; } size_t ptw32_oll_GetLeafForThread() { return 0; } /* * Only readers call ptw32_oll_Arrive() * * Checks whether the C-SNZI state is OPEN, and if so, * increments the surplus of the C-SNZI by either directly * arriving at the root node, or calling TreeArrive on one * of the leaf nodes. Returns a ticket pointing to the node * that was arrived at. If the state is CLOSED, makes no * change and returns a ticket that contains no pointer. */ ptw32_oll_ticket_t ptw32_oll_Arrive(ptw32_oll_csnzi_t* csnzi) { for (;;) { ptw32_oll_ticket_t ticket; ptw32_oll_snziRoot_t oldProxy = csnzi->proxyRoot; if (oldProxy.counter.internal.state != ptw32_oll_snziRoot_open) { ticket.snziNodeOrRoot.rootPtr = (ptw32_oll_snziRoot_t*)NULL; return ticket; } if (!ptw32_oll_ShouldArriveAtTree()) { ptw32_oll_snziRoot_t newProxy = oldProxy; newProxy.counter.internal.count++; if (PTW32_INTERLOCKED_COMPARE_EXCHANGE_SIZE( (PTW32_INTERLOCKED_SIZEPTR)&csnzi->proxyRoot.counter, (PTW32_INTERLOCKED_SIZE)newProxy.counter.word, (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word) == (PTW32_INTERLOCKED_SIZE)oldProxy.counter.word) { /* Exchange successful */ ticket.snziNodeOrRoot.rootPtr = &csnzi->proxyRoot; return ticket; } } else { ptw32_oll_snziNode_t* leafPtr = &csnzi->leafs[ptw32_oll_GetLeafForThread()]; ticket.snziNodeOrRoot.nodePtr = (ptw32_oll_TreeArrive(leafPtr) ? leafPtr : (ptw32_oll_snziNode_t*)NULL); return ticket; } } } /* * Decrements the C-SNZI surplus. Returns false iff the * resulting state