/*
* 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
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
pthreads Windows版 32位+64位 (459个子文件)
libpthreadGC2.a 91KB
libpthreadGCE2.a 91KB
libpthreadGC2.a 91KB
ANNOUNCE 14KB
ANNOUNCE 14KB
builddmc.bat 440B
install.bat 76B
README.BENCHTESTS 2KB
Bmakefile 11KB
Bmakefile 6KB
README.Borland 3KB
README.Borland 3KB
BUGS 6KB
BUGS 6KB
ptw32_OLL_lock.c 21KB
pthread_cond_wait.c 17KB
pthread_mutex_timedlock.c 10KB
benchtest2.c 10KB
pthread_mutex_lock.c 9KB
ptw32_MCS_lock.c 9KB
eyal1.c 9KB
ptw32_threadStart.c 9KB
create.c 8KB
benchtest1.c 8KB
pthread_cond_destroy.c 8KB
alertdrv.c 8KB
stress1.c 7KB
benchlib.c 7KB
pthread_win32_attach_detach_np.c 7KB
ptw32_callUserDestroyRoutines.c 7KB
robust4.c 7KB
pthread_cond_signal.c 7KB
pthread_mutex_consistent.c 7KB
sem_timedwait.c 7KB
benchtest3.c 6KB
sched_get_priority_min.c 6KB
sched_get_priority_max.c 6KB
condvar9.c 6KB
exception1.c 6KB
benchtest4.c 6KB
condvar8.c 6KB
condvar7.c 6KB
cancel2.c 6KB
once4.c 6KB
pthread_mutex_unlock.c 6KB
cleanup1.c 5KB
pthread_mutexattr_settype.c 5KB
condvar6.c 5KB
cancel8.c 5KB
pthread_cancel.c 5KB
condvar3_1.c 5KB
tsd2.c 5KB
cancel9.c 5KB
signal.c 5KB
sem_wait.c 5KB
cancel7.c 5KB
tsd1.c 5KB
condvar3_2.c 5KB
inherit1.c 5KB
cleanup0.c 5KB
rwlock8.c 5KB
cleanup.c 5KB
pthread_delay_np.c 5KB
priority2.c 5KB
cleanup3.c 5KB
cancel3.c 5KB
exit5.c 5KB
rwlock7.c 5KB
priority1.c 5KB
robust3.c 5KB
cleanup2.c 5KB
cancel5.c 5KB
cancel4.c 5KB
pthread_mutexattr_setrobust.c 5KB
sem_destroy.c 5KB
ptw32_throw.c 5KB
robust1.c 5KB
exit4.c 5KB
pthread_mutexattr_getrobust.c 5KB
QueueUserAPCEx.c 5KB
ptw32_reuse.c 5KB
robust2.c 5KB
sem_init.c 5KB
w32_CancelableWait.c 5KB
pthread_join.c 5KB
benchtest5.c 5KB
pthread_mutex_trylock.c 5KB
pthread_setspecific.c 5KB
cancel1.c 5KB
QueueUserAPCEx.c 5KB
exception3.c 4KB
cancel6d.c 4KB
cancel6a.c 4KB
condvar4.c 4KB
pthread_detach.c 4KB
pthread_cond_init.c 4KB
condvar5.c 4KB
pthread_self.c 4KB
once3.c 4KB
reuse2.c 4KB
共 459 条
- 1
- 2
- 3
- 4
- 5
资源评论
Ango_Cango
- 粉丝: 72
- 资源: 57
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功