pthreads-w32-2.9.1-release.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