Created
April 21, 2011 06:16
-
-
Save thinkhy/933838 to your computer and use it in GitHub Desktop.
queuelock的实现,来源于processHacker工程
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Process Hacker - | |
* queued lock | |
* | |
* Copyright (C) 2010-2011 wj32 | |
* | |
* This file is part of Process Hacker. | |
* | |
* Process Hacker is free software; you can redistribute it and/or modify | |
* it under the terms of the GNU General Public License as published by | |
* the Free Software Foundation, either version 3 of the License, or | |
* (at your option) any later version. | |
* | |
* Process Hacker 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 General Public License for more details. | |
* | |
* You should have received a copy of the GNU General Public License | |
* along with Process Hacker. If not, see <http://www.gnu.org/licenses/>. | |
*/ | |
/* | |
* Queued lock, a.k.a. push lock (kernel-mode) or slim reader-writer lock | |
* (user-mode). | |
* | |
* The queued lock is: | |
* * Around 10% faster than the fast lock. | |
* * Only the size of a pointer. | |
* * Low on resource usage (no additional kernel objects are | |
* created for blocking). | |
* | |
* The usual flags are used for contention-free | |
* acquire/release. When there is contention, stack-based | |
* wait blocks are chained. The first wait block contains | |
* the shared owners count which is decremented by | |
* shared releasers. | |
* | |
* Naturally these wait blocks would be chained | |
* in FILO order, but list optimization is done for two purposes: | |
* * Finding the last wait block (where the shared owners | |
* count is stored). This is implemented by the Last pointer. | |
* * Unblocking the wait blocks in FIFO order. This is | |
* implemented by the Previous pointer. | |
* | |
* The optimization is incremental - each optimization run | |
* will stop at the first optimized wait block. Any needed | |
* optimization is completed just before waking waiters. | |
* | |
* The waiters list/chain has the following restrictions: | |
* * At any time wait blocks may be pushed onto the list. | |
* * While waking waiters, the list may not be traversed | |
* nor optimized. | |
* * When there are multiple shared owners, shared releasers | |
* may traverse the list (to find the last wait block). | |
* This is not an issue because waiters wouldn't be woken | |
* until there are no more shared owners. | |
* * List optimization may be done at any time except for | |
* when someone else is waking waiters. This is controlled | |
* by the traversing bit. | |
* | |
* The traversing bit has the following rules: | |
* * The list may be optimized only after the traversing bit | |
* is set, checking that it wasn't set already. | |
* If it was set, it would indicate that someone else is | |
* optimizing the list or waking waiters. | |
* * Before waking waiters the traversing bit must be set. | |
* If it was set already, just clear the owned bit. | |
* * If during list optimization the owned bit is detected | |
* to be cleared, the function begins waking waiters. This | |
* is because the owned bit is cleared when a releaser | |
* fails to set the traversing bit. | |
* | |
* Blocking is implemented through a process-wide keyed event. | |
* A spin count is also used before blocking on the keyed | |
* event. | |
* | |
* Queued locks can act as condition variables, with | |
* wait, pulse and pulse all support. Waiters are released | |
* in FIFO order. | |
* | |
* Queued locks can act as wake events. These are designed | |
* for tiny one-bit locks which share a single event to block | |
* on. Spurious wake-ups are a part of normal operation. | |
*/ | |
#include <phbase.h> | |
#include <phintrnl.h> | |
VOID FASTCALL PhpfOptimizeQueuedLockList( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value | |
); | |
VOID FASTCALL PhpfWakeQueuedLock( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value | |
); | |
VOID FASTCALL PhpfWakeQueuedLockEx( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value, | |
__in BOOLEAN IgnoreOwned, | |
__in BOOLEAN WakeAll | |
); | |
static HANDLE PhQueuedLockKeyedEventHandle; | |
static ULONG PhQueuedLockSpinCount = 2000; | |
BOOLEAN PhQueuedLockInitialization() | |
{ | |
if (!NT_SUCCESS(NtCreateKeyedEvent( | |
&PhQueuedLockKeyedEventHandle, | |
KEYEDEVENT_ALL_ACCESS, | |
NULL, | |
0 | |
))) | |
return FALSE; | |
if ((ULONG)PhSystemBasicInformation.NumberOfProcessors > 1) | |
PhQueuedLockSpinCount = 4000; | |
else | |
PhQueuedLockSpinCount = 0; | |
return TRUE; | |
} | |
/** | |
* Pushes a wait block onto a queued lock's waiters list. | |
* | |
* \param QueuedLock A queued lock. | |
* \param Value The current value of the queued lock. | |
* \param Exclusive Whether the wait block is in exclusive | |
* mode. | |
* \param WaitBlock A variable which receives the resulting | |
* wait block structure. | |
* \param Optimize A variable which receives a boolean | |
* indicating whether to optimize the waiters list. | |
* \param NewValue The old value of the queued lock. This | |
* value is useful only if the function returns FALSE. | |
* \param CurrentValue The new value of the queued lock. This | |
* value is useful only if the function returns TRUE. | |
* | |
* \return TRUE if the wait block was pushed onto the waiters | |
* list, otherwise FALSE. | |
* | |
* \remarks | |
* \li The function assumes the following flags are set: | |
* \ref PH_QUEUED_LOCK_OWNED. | |
* \li Do not move the wait block location after this | |
* function is called. | |
* \li The \a Optimize boolean is a hint to call | |
* PhpfOptimizeQueuedLockList() if the function succeeds. It is | |
* recommended, but not essential that this occurs. | |
* \li Call PhpBlockOnQueuedWaitBlock() to wait for the wait | |
* block to be unblocked. | |
*/ | |
FORCEINLINE BOOLEAN PhpPushQueuedWaitBlock( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value, | |
__in BOOLEAN Exclusive, | |
__out PPH_QUEUED_WAIT_BLOCK WaitBlock, | |
__out PBOOLEAN Optimize, | |
__out PULONG_PTR NewValue, | |
__out PULONG_PTR CurrentValue | |
) | |
{ | |
ULONG_PTR newValue; | |
BOOLEAN optimize; | |
WaitBlock->Previous = NULL; // set later by optimization | |
optimize = FALSE; | |
if (Exclusive) | |
WaitBlock->Flags = PH_QUEUED_WAITER_EXCLUSIVE | PH_QUEUED_WAITER_SPINNING; | |
else | |
WaitBlock->Flags = PH_QUEUED_WAITER_SPINNING; | |
if (Value & PH_QUEUED_LOCK_WAITERS) | |
{ | |
// We're not the first waiter. | |
WaitBlock->Last = NULL; // set later by optimization | |
WaitBlock->Next = PhGetQueuedLockWaitBlock(Value); | |
WaitBlock->SharedOwners = 0; | |
// Push our wait block onto the list. | |
// Set the traversing bit because we'll be optimizing the list. | |
newValue = ((ULONG_PTR)WaitBlock) | (Value & PH_QUEUED_LOCK_FLAGS) | | |
PH_QUEUED_LOCK_TRAVERSING; | |
if (!(Value & PH_QUEUED_LOCK_TRAVERSING)) | |
optimize = TRUE; | |
} | |
else | |
{ | |
// We're the first waiter. | |
WaitBlock->Last = WaitBlock; // indicate that this is the last wait block | |
if (Exclusive) | |
{ | |
// We're the first waiter. Save the shared owners count. | |
WaitBlock->SharedOwners = (ULONG)PhGetQueuedLockSharedOwners(Value); | |
if (WaitBlock->SharedOwners > 1) | |
{ | |
newValue = ((ULONG_PTR)WaitBlock) | PH_QUEUED_LOCK_OWNED | | |
PH_QUEUED_LOCK_WAITERS | PH_QUEUED_LOCK_MULTIPLE_SHARED; | |
} | |
else | |
{ | |
newValue = ((ULONG_PTR)WaitBlock) | PH_QUEUED_LOCK_OWNED | | |
PH_QUEUED_LOCK_WAITERS; | |
} | |
} | |
else | |
{ | |
// We're waiting in shared mode, which means there can't | |
// be any shared owners (otherwise we would've acquired | |
// the lock already). | |
WaitBlock->SharedOwners = 0; | |
newValue = ((ULONG_PTR)WaitBlock) | PH_QUEUED_LOCK_OWNED | | |
PH_QUEUED_LOCK_WAITERS; | |
} | |
} | |
*Optimize = optimize; | |
*CurrentValue = newValue; | |
newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)Value | |
); | |
*NewValue = newValue; | |
return newValue == Value; | |
} | |
/** | |
* Finds the last wait block in the waiters list. | |
* | |
* \param Value The current value of the queued lock. | |
* | |
* \return A pointer to the last wait block. | |
* | |
* \remarks The function assumes the following flags are set: | |
* \ref PH_QUEUED_LOCK_WAITERS, | |
* \ref PH_QUEUED_LOCK_MULTIPLE_SHARED or | |
* \ref PH_QUEUED_LOCK_TRAVERSING. | |
*/ | |
FORCEINLINE PPH_QUEUED_WAIT_BLOCK PhpFindLastQueuedWaitBlock( | |
__in ULONG_PTR Value | |
) | |
{ | |
PPH_QUEUED_WAIT_BLOCK waitBlock; | |
PPH_QUEUED_WAIT_BLOCK lastWaitBlock; | |
waitBlock = PhGetQueuedLockWaitBlock(Value); | |
// Traverse the list until we find the last wait block. | |
// The Last pointer should be set by list optimization, | |
// allowing us to skip all, if not most of the wait blocks. | |
while (TRUE) | |
{ | |
lastWaitBlock = waitBlock->Last; | |
if (lastWaitBlock) | |
{ | |
// Follow the Last pointer. This can mean two | |
// things: the pointer was set by list optimization, | |
// or this wait block is actually the last wait block | |
// (set when it was pushed onto the list). | |
waitBlock = lastWaitBlock; | |
break; | |
} | |
waitBlock = waitBlock->Next; | |
} | |
return waitBlock; | |
} | |
/** | |
* Waits for a wait block to be unblocked. | |
* | |
* \param WaitBlock A wait block. | |
* \param Spin TRUE to spin, FALSE to block immediately. | |
* \param Timeout A timeout value. | |
*/ | |
__mayRaise FORCEINLINE NTSTATUS PhpBlockOnQueuedWaitBlock( | |
__inout PPH_QUEUED_WAIT_BLOCK WaitBlock, | |
__in BOOLEAN Spin, | |
__in_opt PLARGE_INTEGER Timeout | |
) | |
{ | |
NTSTATUS status; | |
ULONG i; | |
if (Spin) | |
{ | |
PHLIB_INC_STATISTIC(QlBlockSpins); | |
for (i = PhQueuedLockSpinCount; i != 0; i--) | |
{ | |
if (!(*(volatile ULONG *)&WaitBlock->Flags & PH_QUEUED_WAITER_SPINNING)) | |
return STATUS_SUCCESS; | |
YieldProcessor(); | |
} | |
} | |
if (_interlockedbittestandreset((PLONG)&WaitBlock->Flags, PH_QUEUED_WAITER_SPINNING_SHIFT)) | |
{ | |
PHLIB_INC_STATISTIC(QlBlockWaits); | |
status = NtWaitForKeyedEvent( | |
PhQueuedLockKeyedEventHandle, | |
WaitBlock, | |
FALSE, | |
Timeout | |
); | |
// If an error occurred (timeout is not an error), raise an exception | |
// as it is nearly impossible to recover from this situation. | |
if (!NT_SUCCESS(status)) | |
PhRaiseStatus(status); | |
} | |
else | |
{ | |
status = STATUS_SUCCESS; | |
} | |
return status; | |
} | |
/** | |
* Unblocks a wait block. | |
* | |
* \param WaitBlock A wait block. | |
* | |
* \remarks The wait block is in an undefined state after it is | |
* unblocked. Do not attempt to read any values from it. All relevant | |
* information should be saved before unblocking the wait block. | |
*/ | |
__mayRaise FORCEINLINE VOID PhpUnblockQueuedWaitBlock( | |
__inout PPH_QUEUED_WAIT_BLOCK WaitBlock | |
) | |
{ | |
NTSTATUS status; | |
if (!_interlockedbittestandreset((PLONG)&WaitBlock->Flags, PH_QUEUED_WAITER_SPINNING_SHIFT)) | |
{ | |
if (!NT_SUCCESS(status = NtReleaseKeyedEvent( | |
PhQueuedLockKeyedEventHandle, | |
WaitBlock, | |
FALSE, | |
NULL | |
))) | |
PhRaiseStatus(status); | |
} | |
} | |
/** | |
* Optimizes a queued lock waiters list. | |
* | |
* \param QueuedLock A queued lock. | |
* \param Value The current value of the queued lock. | |
* \param IgnoreOwned TRUE to ignore lock state, FALSE | |
* to conduct normal checks. | |
* | |
* \remarks The function assumes the following flags are set: | |
* \ref PH_QUEUED_LOCK_WAITERS, \ref PH_QUEUED_LOCK_TRAVERSING. | |
*/ | |
FORCEINLINE VOID PhpOptimizeQueuedLockListEx( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value, | |
__in BOOLEAN IgnoreOwned | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR newValue; | |
PPH_QUEUED_WAIT_BLOCK waitBlock; | |
PPH_QUEUED_WAIT_BLOCK firstWaitBlock; | |
PPH_QUEUED_WAIT_BLOCK lastWaitBlock; | |
PPH_QUEUED_WAIT_BLOCK previousWaitBlock; | |
value = Value; | |
while (TRUE) | |
{ | |
assert(value & PH_QUEUED_LOCK_TRAVERSING); | |
if (!IgnoreOwned && !(value & PH_QUEUED_LOCK_OWNED)) | |
{ | |
// Someone has requested that we wake waiters. | |
PhpfWakeQueuedLock(QueuedLock, value); | |
break; | |
} | |
// Perform the optimization. | |
waitBlock = PhGetQueuedLockWaitBlock(value); | |
firstWaitBlock = waitBlock; | |
while (TRUE) | |
{ | |
lastWaitBlock = waitBlock->Last; | |
if (lastWaitBlock) | |
{ | |
// Save a pointer to the last wait block in | |
// the first wait block and stop optimizing. | |
// | |
// We don't need to continue setting Previous | |
// pointers because the last optimization run | |
// would have set them already. | |
firstWaitBlock->Last = lastWaitBlock; | |
break; | |
} | |
previousWaitBlock = waitBlock; | |
waitBlock = waitBlock->Next; | |
waitBlock->Previous = previousWaitBlock; | |
} | |
// Try to clear the traversing bit. | |
newValue = value - PH_QUEUED_LOCK_TRAVERSING; | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
break; | |
// Either someone pushed a wait block onto the list | |
// or someone released ownership. In either case we | |
// need to go back. | |
value = newValue; | |
} | |
} | |
/** | |
* Optimizes a queued lock waiters list. | |
* | |
* \param QueuedLock A queued lock. | |
* \param Value The current value of the queued lock. | |
* | |
* \remarks The function assumes the following flags are set: | |
* \ref PH_QUEUED_LOCK_WAITERS, \ref PH_QUEUED_LOCK_TRAVERSING. | |
*/ | |
VOID FASTCALL PhpfOptimizeQueuedLockList( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value | |
) | |
{ | |
PhpOptimizeQueuedLockListEx(QueuedLock, Value, FALSE); | |
} | |
/** | |
* Dequeues the appropriate number of wait blocks in | |
* a queued lock. | |
* | |
* \param QueuedLock A queued lock. | |
* \param Value The current value of the queued lock. | |
* \param IgnoreOwned TRUE to ignore lock state, FALSE | |
* to conduct normal checks. | |
* \param WakeAll TRUE to remove all wait blocks, FALSE | |
* to decide based on the wait block type. | |
*/ | |
FORCEINLINE PPH_QUEUED_WAIT_BLOCK PhpPrepareToWakeQueuedLock( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value, | |
__in BOOLEAN IgnoreOwned, | |
__in BOOLEAN WakeAll | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR newValue; | |
PPH_QUEUED_WAIT_BLOCK waitBlock; | |
PPH_QUEUED_WAIT_BLOCK firstWaitBlock; | |
PPH_QUEUED_WAIT_BLOCK lastWaitBlock; | |
PPH_QUEUED_WAIT_BLOCK previousWaitBlock; | |
value = Value; | |
while (TRUE) | |
{ | |
// If there are multiple shared owners, no one is going | |
// to wake waiters since the lock would still be owned. | |
// Also if there are multiple shared owners they may be | |
// traversing the list. While that is safe when | |
// done concurrently with list optimization, we may be | |
// removing and waking waiters. | |
assert(!(value & PH_QUEUED_LOCK_MULTIPLE_SHARED)); | |
assert(IgnoreOwned || (value & PH_QUEUED_LOCK_TRAVERSING)); | |
// There's no point in waking a waiter if the lock | |
// is owned. Clear the traversing bit. | |
while (!IgnoreOwned && (value & PH_QUEUED_LOCK_OWNED)) | |
{ | |
newValue = value - PH_QUEUED_LOCK_TRAVERSING; | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
return NULL; | |
value = newValue; | |
} | |
// Finish up any needed optimization (setting the | |
// Previous pointers) while finding the last wait | |
// block. | |
waitBlock = PhGetQueuedLockWaitBlock(value); | |
firstWaitBlock = waitBlock; | |
while (TRUE) | |
{ | |
lastWaitBlock = waitBlock->Last; | |
if (lastWaitBlock) | |
{ | |
waitBlock = lastWaitBlock; | |
break; | |
} | |
previousWaitBlock = waitBlock; | |
waitBlock = waitBlock->Next; | |
waitBlock->Previous = previousWaitBlock; | |
} | |
// Unlink the relevant wait blocks and clear the | |
// traversing bit before we wake waiters. | |
if ( | |
!WakeAll && | |
(waitBlock->Flags & PH_QUEUED_WAITER_EXCLUSIVE) && | |
(previousWaitBlock = waitBlock->Previous) | |
) | |
{ | |
// We have an exclusive waiter and there are | |
// multiple waiters. | |
// We'll only be waking this waiter. | |
// Unlink the wait block from the list. | |
// Although other wait blocks may have their | |
// Last pointers set to this wait block, | |
// the algorithm to find the last wait block | |
// will stop here. Likewise the Next pointers | |
// are never followed beyond this point, so | |
// we don't need to clear those. | |
firstWaitBlock->Last = previousWaitBlock; | |
// Make sure we only wake this waiter. | |
waitBlock->Previous = NULL; | |
if (!IgnoreOwned) | |
{ | |
// Clear the traversing bit. | |
_InterlockedExchangeAddPointer((PLONG_PTR)&QueuedLock->Value, -(LONG_PTR)PH_QUEUED_LOCK_TRAVERSING); | |
} | |
break; | |
} | |
else | |
{ | |
// We're waking an exclusive waiter and there | |
// is only one waiter, or we are waking | |
// a shared waiter and possibly others. | |
newValue = 0; | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
break; | |
// Someone changed the lock (acquired it or | |
// pushed a wait block). | |
value = newValue; | |
} | |
} | |
return waitBlock; | |
} | |
/** | |
* Wakes waiters in a queued lock. | |
* | |
* \param QueuedLock A queued lock. | |
* \param Value The current value of the queued lock. | |
* | |
* \remarks The function assumes the following flags are set: | |
* \ref PH_QUEUED_LOCK_WAITERS, \ref PH_QUEUED_LOCK_TRAVERSING. | |
* The function assumes the following flags are not set: | |
* \ref PH_QUEUED_LOCK_MULTIPLE_SHARED. | |
*/ | |
VOID FASTCALL PhpfWakeQueuedLock( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value | |
) | |
{ | |
PPH_QUEUED_WAIT_BLOCK waitBlock; | |
PPH_QUEUED_WAIT_BLOCK previousWaitBlock; | |
waitBlock = PhpPrepareToWakeQueuedLock(QueuedLock, Value, FALSE, FALSE); | |
// Wake waiters. | |
while (waitBlock) | |
{ | |
previousWaitBlock = waitBlock->Previous; | |
PhpUnblockQueuedWaitBlock(waitBlock); | |
waitBlock = previousWaitBlock; | |
} | |
} | |
/** | |
* Wakes waiters in a queued lock. | |
* | |
* \param QueuedLock A queued lock. | |
* \param Value The current value of the queued lock. | |
* \param IgnoreOwned TRUE to ignore lock state, FALSE | |
* to conduct normal checks. | |
* \param WakeAll TRUE to wake all waiters, FALSE to | |
* decide based on the wait block type. | |
* | |
* \remarks The function assumes the following flags are set: | |
* \ref PH_QUEUED_LOCK_WAITERS, \ref PH_QUEUED_LOCK_TRAVERSING. | |
* The function assumes the following flags are not set: | |
* \ref PH_QUEUED_LOCK_MULTIPLE_SHARED. | |
*/ | |
VOID FASTCALL PhpfWakeQueuedLockEx( | |
__inout PPH_QUEUED_LOCK QueuedLock, | |
__in ULONG_PTR Value, | |
__in BOOLEAN IgnoreOwned, | |
__in BOOLEAN WakeAll | |
) | |
{ | |
PPH_QUEUED_WAIT_BLOCK waitBlock; | |
PPH_QUEUED_WAIT_BLOCK previousWaitBlock; | |
waitBlock = PhpPrepareToWakeQueuedLock(QueuedLock, Value, IgnoreOwned, WakeAll); | |
// Wake waiters. | |
while (waitBlock) | |
{ | |
previousWaitBlock = waitBlock->Previous; | |
PhpUnblockQueuedWaitBlock(waitBlock); | |
waitBlock = previousWaitBlock; | |
} | |
} | |
/** | |
* Acquires a queued lock in exclusive mode. | |
* | |
* \param QueuedLock A queued lock. | |
*/ | |
VOID FASTCALL PhfAcquireQueuedLockExclusive( | |
__inout PPH_QUEUED_LOCK QueuedLock | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR newValue; | |
ULONG_PTR currentValue; | |
BOOLEAN optimize; | |
PH_QUEUED_WAIT_BLOCK waitBlock; | |
value = QueuedLock->Value; | |
while (TRUE) | |
{ | |
if (!(value & PH_QUEUED_LOCK_OWNED)) | |
{ | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)(value + PH_QUEUED_LOCK_OWNED), | |
(PVOID)value | |
)) == value) | |
break; | |
} | |
else | |
{ | |
if (PhpPushQueuedWaitBlock( | |
QueuedLock, | |
value, | |
TRUE, | |
&waitBlock, | |
&optimize, | |
&newValue, | |
¤tValue | |
)) | |
{ | |
if (optimize) | |
PhpfOptimizeQueuedLockList(QueuedLock, currentValue); | |
PHLIB_INC_STATISTIC(QlAcquireExclusiveBlocks); | |
PhpBlockOnQueuedWaitBlock(&waitBlock, TRUE, NULL); | |
} | |
} | |
value = newValue; | |
} | |
} | |
/** | |
* Acquires a queued lock in shared mode. | |
* | |
* \param QueuedLock A queued lock. | |
*/ | |
VOID FASTCALL PhfAcquireQueuedLockShared( | |
__inout PPH_QUEUED_LOCK QueuedLock | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR newValue; | |
ULONG_PTR currentValue; | |
BOOLEAN optimize; | |
PH_QUEUED_WAIT_BLOCK waitBlock; | |
value = QueuedLock->Value; | |
while (TRUE) | |
{ | |
// We can't acquire if there are waiters for two reasons: | |
// | |
// We want to prioritize exclusive acquires over shared acquires. | |
// There's currently no fast, safe way of finding the last wait | |
// block and incrementing the shared owners count here. | |
if ( | |
!(value & PH_QUEUED_LOCK_WAITERS) && | |
(!(value & PH_QUEUED_LOCK_OWNED) || (PhGetQueuedLockSharedOwners(value) > 0)) | |
) | |
{ | |
newValue = (value + PH_QUEUED_LOCK_SHARED_INC) | PH_QUEUED_LOCK_OWNED; | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
break; | |
} | |
else | |
{ | |
if (PhpPushQueuedWaitBlock( | |
QueuedLock, | |
value, | |
FALSE, | |
&waitBlock, | |
&optimize, | |
&newValue, | |
¤tValue | |
)) | |
{ | |
if (optimize) | |
PhpfOptimizeQueuedLockList(QueuedLock, currentValue); | |
PHLIB_INC_STATISTIC(QlAcquireSharedBlocks); | |
PhpBlockOnQueuedWaitBlock(&waitBlock, TRUE, NULL); | |
} | |
} | |
value = newValue; | |
} | |
} | |
/** | |
* Releases a queued lock in exclusive mode. | |
* | |
* \param QueuedLock A queued lock. | |
*/ | |
VOID FASTCALL PhfReleaseQueuedLockExclusive( | |
__inout PPH_QUEUED_LOCK QueuedLock | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR newValue; | |
ULONG_PTR currentValue; | |
value = QueuedLock->Value; | |
while (TRUE) | |
{ | |
assert(value & PH_QUEUED_LOCK_OWNED); | |
assert((value & PH_QUEUED_LOCK_WAITERS) || (PhGetQueuedLockSharedOwners(value) == 0)); | |
if (!(value & PH_QUEUED_LOCK_WAITERS) || (value & PH_QUEUED_LOCK_TRAVERSING)) | |
{ | |
// There are no waiters or someone is traversing the list. | |
// | |
// If there are no waiters, we're simply releasing ownership. | |
// If someone is traversing the list, clearing the owned bit | |
// is a signal for them to wake waiters. | |
newValue = value - PH_QUEUED_LOCK_OWNED; | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
break; | |
} | |
else | |
{ | |
// We need to wake waiters and no one is traversing the list. | |
// Try to set the traversing bit and wake waiters. | |
newValue = value - PH_QUEUED_LOCK_OWNED + PH_QUEUED_LOCK_TRAVERSING; | |
currentValue = newValue; | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
{ | |
PhpfWakeQueuedLock(QueuedLock, currentValue); | |
break; | |
} | |
} | |
value = newValue; | |
} | |
} | |
/** | |
* Releases a queued lock in shared mode. | |
* | |
* \param QueuedLock A queued lock. | |
*/ | |
VOID FASTCALL PhfReleaseQueuedLockShared( | |
__inout PPH_QUEUED_LOCK QueuedLock | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR newValue; | |
ULONG_PTR currentValue; | |
PPH_QUEUED_WAIT_BLOCK waitBlock; | |
value = QueuedLock->Value; | |
while (!(value & PH_QUEUED_LOCK_WAITERS)) | |
{ | |
assert(value & PH_QUEUED_LOCK_OWNED); | |
assert((value & PH_QUEUED_LOCK_WAITERS) || (PhGetQueuedLockSharedOwners(value) > 0)); | |
if (PhGetQueuedLockSharedOwners(value) > 1) | |
newValue = value - PH_QUEUED_LOCK_SHARED_INC; | |
else | |
newValue = 0; | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
return; | |
value = newValue; | |
} | |
if (value & PH_QUEUED_LOCK_MULTIPLE_SHARED) | |
{ | |
// Unfortunately we have to find the last wait block and | |
// decrement the shared owners count. | |
waitBlock = PhpFindLastQueuedWaitBlock(value); | |
if ((ULONG)_InterlockedDecrement((PLONG)&waitBlock->SharedOwners) > 0) | |
return; | |
} | |
while (TRUE) | |
{ | |
if (value & PH_QUEUED_LOCK_TRAVERSING) | |
{ | |
newValue = value & ~(PH_QUEUED_LOCK_OWNED | PH_QUEUED_LOCK_MULTIPLE_SHARED); | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
break; | |
} | |
else | |
{ | |
newValue = (value & ~(PH_QUEUED_LOCK_OWNED | PH_QUEUED_LOCK_MULTIPLE_SHARED)) | | |
PH_QUEUED_LOCK_TRAVERSING; | |
currentValue = newValue; | |
if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
)) == value) | |
{ | |
PhpfWakeQueuedLock(QueuedLock, currentValue); | |
break; | |
} | |
} | |
value = newValue; | |
} | |
} | |
/** | |
* Wakes waiters in a queued lock, making no assumptions | |
* about the state of the lock. | |
* | |
* \param QueuedLock A queued lock. | |
*/ | |
VOID FASTCALL PhfTryWakeQueuedLock( | |
__inout PPH_QUEUED_LOCK QueuedLock | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR newValue; | |
value = QueuedLock->Value; | |
if ( | |
!(value & PH_QUEUED_LOCK_WAITERS) || | |
(value & PH_QUEUED_LOCK_TRAVERSING) || | |
(value & PH_QUEUED_LOCK_OWNED) | |
) | |
return; | |
newValue = value + PH_QUEUED_LOCK_TRAVERSING; | |
if ((ULONG_PTR)_InterlockedCompareExchangePointer( | |
(PPVOID)&QueuedLock->Value, | |
(PVOID)newValue, | |
(PVOID)value | |
) == value) | |
{ | |
PhpfWakeQueuedLock(QueuedLock, newValue); | |
} | |
} | |
/** | |
* Wakes one thread sleeping on a condition variable. | |
* | |
* \param Condition A condition variable. | |
* | |
* \remarks The associated lock must be acquired before calling | |
* the function. | |
*/ | |
VOID FASTCALL PhfPulseCondition( | |
__inout PPH_QUEUED_LOCK Condition | |
) | |
{ | |
if (Condition->Value & PH_QUEUED_LOCK_WAITERS) | |
PhpfWakeQueuedLockEx(Condition, Condition->Value, TRUE, FALSE); | |
} | |
/** | |
* Wakes all threads sleeping on a condition variable. | |
* | |
* \param Condition A condition variable. | |
* | |
* \remarks The associated lock must be acquired before calling | |
* the function. | |
*/ | |
VOID FASTCALL PhfPulseAllCondition( | |
__inout PPH_QUEUED_LOCK Condition | |
) | |
{ | |
if (Condition->Value & PH_QUEUED_LOCK_WAITERS) | |
PhpfWakeQueuedLockEx(Condition, Condition->Value, TRUE, TRUE); | |
} | |
/** | |
* Sleeps on a condition variable. | |
* | |
* \param Condition A condition variable. | |
* \param Lock A queued lock to release/acquire in exclusive mode. | |
* \param Timeout Not implemented. | |
* | |
* \remarks The associated lock must be acquired before calling | |
* the function. | |
*/ | |
VOID FASTCALL PhfWaitForCondition( | |
__inout PPH_QUEUED_LOCK Condition, | |
__inout PPH_QUEUED_LOCK Lock, | |
__in_opt PLARGE_INTEGER Timeout | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR currentValue; | |
PH_QUEUED_WAIT_BLOCK waitBlock; | |
BOOLEAN optimize; | |
value = Condition->Value; | |
while (TRUE) | |
{ | |
if (PhpPushQueuedWaitBlock( | |
Condition, | |
value, | |
TRUE, | |
&waitBlock, | |
&optimize, | |
&value, | |
¤tValue | |
)) | |
{ | |
if (optimize) | |
{ | |
PhpOptimizeQueuedLockListEx(Condition, currentValue, TRUE); | |
} | |
PhReleaseQueuedLockExclusive(Lock); | |
PhpBlockOnQueuedWaitBlock(&waitBlock, FALSE, NULL); | |
// Don't use the inline variant; it is extremely likely | |
// that the lock is still owned. | |
PhfAcquireQueuedLockExclusive(Lock); | |
break; | |
} | |
} | |
} | |
/** | |
* Sleeps on a condition variable. | |
* | |
* \param Condition A condition variable. | |
* \param Lock A pointer to a lock. | |
* \param Flags A combination of flags controlling the operation. | |
* \param Timeout Not implemented. | |
*/ | |
VOID FASTCALL PhfWaitForConditionEx( | |
__inout PPH_QUEUED_LOCK Condition, | |
__inout PVOID Lock, | |
__in ULONG Flags, | |
__in_opt PLARGE_INTEGER Timeout | |
) | |
{ | |
ULONG_PTR value; | |
ULONG_PTR currentValue; | |
PH_QUEUED_WAIT_BLOCK waitBlock; | |
BOOLEAN optimize; | |
value = Condition->Value; | |
while (TRUE) | |
{ | |
if (PhpPushQueuedWaitBlock( | |
Condition, | |
value, | |
TRUE, | |
&waitBlock, | |
&optimize, | |
&value, | |
¤tValue | |
)) | |
{ | |
if (optimize) | |
{ | |
PhpOptimizeQueuedLockListEx(Condition, currentValue, TRUE); | |
} | |
switch (Flags & PH_CONDITION_WAIT_LOCK_TYPE_MASK) | |
{ | |
case PH_CONDITION_WAIT_QUEUED_LOCK: | |
if (!(Flags & PH_CONDITION_WAIT_SHARED)) | |
PhReleaseQueuedLockExclusive((PPH_QUEUED_LOCK)Lock); | |
else | |
PhReleaseQueuedLockShared((PPH_QUEUED_LOCK)Lock); | |
break; | |
case PH_CONDITION_WAIT_CRITICAL_SECTION: | |
RtlLeaveCriticalSection((PRTL_CRITICAL_SECTION)Lock); | |
break; | |
case PH_CONDITION_WAIT_FAST_LOCK: | |
if (!(Flags & PH_CONDITION_WAIT_SHARED)) | |
PhReleaseFastLockExclusive((PPH_FAST_LOCK)Lock); | |
else | |
PhReleaseFastLockShared((PPH_FAST_LOCK)Lock); | |
break; | |
} | |
if (!(Flags & PH_CONDITION_WAIT_SPIN)) | |
{ | |
PhpBlockOnQueuedWaitBlock(&waitBlock, FALSE, NULL); | |
} | |
else | |
{ | |
PhpBlockOnQueuedWaitBlock(&waitBlock, TRUE, NULL); | |
} | |
switch (Flags & PH_CONDITION_WAIT_LOCK_TYPE_MASK) | |
{ | |
case PH_CONDITION_WAIT_QUEUED_LOCK: | |
if (!(Flags & PH_CONDITION_WAIT_SHARED)) | |
PhfAcquireQueuedLockExclusive((PPH_QUEUED_LOCK)Lock); | |
else | |
PhfAcquireQueuedLockShared((PPH_QUEUED_LOCK)Lock); | |
break; | |
case PH_CONDITION_WAIT_CRITICAL_SECTION: | |
RtlEnterCriticalSection((PRTL_CRITICAL_SECTION)Lock); | |
break; | |
case PH_CONDITION_WAIT_FAST_LOCK: | |
if (!(Flags & PH_CONDITION_WAIT_SHARED)) | |
PhAcquireFastLockExclusive((PPH_FAST_LOCK)Lock); | |
else | |
PhAcquireFastLockShared((PPH_FAST_LOCK)Lock); | |
break; | |
} | |
break; | |
} | |
} | |
} | |
/** | |
* Queues a wait block to a wake event. | |
* | |
* \param WakeEvent A wake event. | |
* \param WaitBlock A wait block. | |
* | |
* \remarks If you later determine that the wait should | |
* not occur, you must call PhfSetWakeEvent() to dequeue | |
* the wait block. | |
*/ | |
VOID FASTCALL PhfQueueWakeEvent( | |
__inout PPH_QUEUED_LOCK WakeEvent, | |
__out PPH_QUEUED_WAIT_BLOCK WaitBlock | |
) | |
{ | |
PPH_QUEUED_WAIT_BLOCK value; | |
PPH_QUEUED_WAIT_BLOCK newValue; | |
WaitBlock->Flags = PH_QUEUED_WAITER_SPINNING; | |
value = (PPH_QUEUED_WAIT_BLOCK)WakeEvent->Value; | |
while (TRUE) | |
{ | |
WaitBlock->Next = value; | |
if ((newValue = _InterlockedCompareExchangePointer( | |
(PPVOID)&WakeEvent->Value, | |
WaitBlock, | |
value | |
)) == value) | |
break; | |
value = newValue; | |
} | |
} | |
/** | |
* Sets a wake event, unblocking all queued wait blocks. | |
* | |
* \param WakeEvent A wake event. | |
* \param WaitBlock A wait block for a cancelled wait, otherwise | |
* NULL. | |
*/ | |
VOID FASTCALL PhfSetWakeEvent( | |
__inout PPH_QUEUED_LOCK WakeEvent, | |
__inout_opt PPH_QUEUED_WAIT_BLOCK WaitBlock | |
) | |
{ | |
PPH_QUEUED_WAIT_BLOCK waitBlock; | |
PPH_QUEUED_WAIT_BLOCK nextWaitBlock; | |
// Pop all waiters and unblock them. | |
waitBlock = _InterlockedExchangePointer((PPVOID)&WakeEvent->Value, NULL); | |
while (waitBlock) | |
{ | |
nextWaitBlock = waitBlock->Next; | |
PhpUnblockQueuedWaitBlock(waitBlock); | |
waitBlock = nextWaitBlock; | |
} | |
if (WaitBlock) | |
{ | |
// We're cancelling a wait; the thread called this function instead | |
// of PhfWaitForWakeEvent. This will remove all waiters from | |
// the list. However, we may not have popped and unblocked the | |
// cancelled wait block ourselves. Another thread may have popped all | |
// waiters but not unblocked them yet at this point: | |
// | |
// 1. This thread: calls PhfQueueWakeEvent. | |
// 2. This thread: code determines that the wait should be cancelled. | |
// 3. Other thread: calls PhfSetWakeEvent and pops our wait block off. | |
// It hasn't unblocked any wait blocks yet. | |
// 4. This thread: calls PhfSetWakeEvent. Since all wait blocks have | |
// been popped, we don't do anything. The caller function exits, | |
// making our wait block invalid. | |
// 5. Other thread: tries to unblock our wait block. Anything could | |
// happen, since our caller already returned. | |
// | |
// The solution is to (always) wait for an unblock. Note that the check below | |
// for the spinning flag is not required, but it is a small optimization. | |
// If the wait block has been unblocked (i.e. the spinning flag is cleared), | |
// then there's no danger. | |
if (WaitBlock->Flags & PH_QUEUED_WAITER_SPINNING) | |
PhpBlockOnQueuedWaitBlock(WaitBlock, FALSE, NULL); | |
} | |
} | |
/** | |
* Waits for a wake event to be set. | |
* | |
* \param WakeEvent A wake event. | |
* \param WaitBlock A wait block previously queued to | |
* the wake event using PhfQueueWakeEvent(). | |
* \param Spin TRUE to spin on the wake event before blocking, | |
* FALSE to block immediately. | |
* \param Timeout A timeout value. | |
* | |
* \remarks Wake events are subject to spurious wakeups. You | |
* should call this function in a loop which checks a | |
* predicate. | |
*/ | |
NTSTATUS FASTCALL PhfWaitForWakeEvent( | |
__inout PPH_QUEUED_LOCK WakeEvent, | |
__inout PPH_QUEUED_WAIT_BLOCK WaitBlock, | |
__in BOOLEAN Spin, | |
__in_opt PLARGE_INTEGER Timeout | |
) | |
{ | |
NTSTATUS status; | |
status = PhpBlockOnQueuedWaitBlock(WaitBlock, Spin, Timeout); | |
if (status != STATUS_SUCCESS) | |
{ | |
// Probably a timeout. There's no way of unlinking | |
// the wait block safely, so just wake everyone. | |
PhSetWakeEvent(WakeEvent, WaitBlock); | |
} | |
return status; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment