先复习一下windows 推锁。
推锁在32位机器上为一个32位整数，64位机器上为一个64位整数。
推锁结构定义：
typedef struct _EX_PUSH_LOCK
{
union
{
ULONG Locked: 1;
ULONG Waiting: 1;
ULONG Waking: 1;
ULONG MultipleShared: 1;
ULONG Shared: 28;
ULONG Value;
PVOID Ptr;
};
} EX_PUSH_LOCK, *PEX_PUSH_LOCK;
//当发生竞争时，EX_PUSH_LOCK(高28位)指向等待块，等待块的类型为EX_PUSH_LOCK_WAIT_BLOCK
typedef struct DECLSPEC_ALIGN(16) _EX_PUSH_LOCK_WAIT_BLOCK {
union {
KGATE WakeGate;
KEVENT WakeEvent;
};
PEX_PUSH_LOCK_WAIT_BLOCK Next;
PEX_PUSH_LOCK_WAIT_BLOCK Last;
PEX_PUSH_LOCK_WAIT_BLOCK Previous;
LONG ShareCount;
LONG Flags;
} DECLSPEC_ALIGN(16) EX_PUSH_LOCK_WAIT_BLOCK;
推锁的最低4位分别位L、W、K和M位。
L位表示推锁以被某个线程锁住。
W位表示有线程正在等待该推锁。W 位如果为0，则高28位表示共享基数;否则，表示一个指向等到块的指针
K位表示一个线程正在唤醒另一个线程。
M位表示在等待块链表的末尾节点记录了共享推锁的线程数，即有竞争情况下共享推锁的所有者数量。
推锁的数据结构示意图：
无竞争情况推锁的4个操作算法：
- 独占获取。推锁是可用的，L=0，W=0，Shared=0,获取以后，推锁状态为L=1，W=0，Shared=0。
- 共享获取。推锁当前是可用的，或已被共享获取但无等待线程，即L=0，W=0，Shared=0，或者L=1，W=0，Shared>0,获取以后，推锁状态为L=1，W=0，Shared=Shared+1。
- 释放独占推锁。已被独占获取，并且无等待线程，所以，L=1，W=0，Shared=0,释放以后，推锁状态为L=0，W=0，Shared=0。
- 释放共享推锁。已被共享获取，并且无等待线程，所以，L=1，W=0,Shared>0,释放以后，推锁状态为W=0，Shared=Shared-1,若Shared为0则L=0，否则L=1。
有竞争情况推锁的4个操作算法：
- 独占获取。推锁已经被获取，如果W=0，则表明这是第一个进入等待的线程，则构造一个等待块，将推锁的Shared 保存到等待块的Share Count中，然后置W=1，退休指向该等待块；如果W=1，则表明已经有线程在等待了，于是构造一个等待块，并插入到等待块链表首。最后线程在等待块中的门对象上等待，直至等待返回。
- 共享方式获取。有两种可能：推锁已经被独占获取，但当前无等待线程(即W=0)，则构造一个等待块，等待块中的ShareCount为0，然后置W=1，推锁指向该等待块；已经有等待线程了，即W=1，则构造一个等待块，并插入到等待块链表首。最后线程在等待块中的门对象上等待，直至等待返回。
- 释放独占推锁。定位到等待块链表末尾节点，若最后一个节点对应于独占方式获取请求，则唤醒该节点对应的线程；否则，唤醒末尾连续的以共享方式获取该推锁的线程。
- 释放共享推锁。定位到等待块末尾节点，递减其ShareCount,若已减为0，则唤醒此等待块代表的等待线程，它必定是一个独占方式的获取方式；若仍大于0，则直接返回。
理解了推锁，看下queuedlock 实现，原理是一样的。
#include#include #include "fastlock.h" #include "phintrnl.h" #include "queuedlock.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( VOID ) { if (!NT_SUCCESS(NtCreateKeyedEvent( &PhQueuedLockKeyedEventHandle, KEYEDEVENT_ALL_ACCESS, NULL, 0 ))) return FALSE; ULONG NumberOfProcessors = 8; if (NumberOfProcessors > 1) PhQueuedLockSpinCount = 4000; else PhQueuedLockSpinCount = 0; return TRUE; } 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( (PVOID *)&QueuedLock->Value, (PVOID)newValue, (PVOID)Value ); *NewValue = newValue; return newValue == Value; } 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; } _May_raise_ 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; } _May_raise_ 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); } } 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( (PVOID *)&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; } } VOID FASTCALL PhpfOptimizeQueuedLockList( _Inout_ PPH_QUEUED_LOCK QueuedLock, _In_ ULONG_PTR Value ) { PhpOptimizeQueuedLockListEx(QueuedLock, Value, FALSE); } 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( (PVOID *)&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( (PVOID *)&QueuedLock->Value, (PVOID)newValue, (PVOID)value )) == value) break; // Someone changed the lock (acquired it or pushed a wait block). value = newValue; } } return waitBlock; } 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; } } 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; } } 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)) { //该锁没有被占有，则直接占有，将QueuedLock->Value标志为设置为PH_QUEUED_LOCK_OWNED // InterlockedCompareExchange是把目标操作数（第1参数所指向的内存中的数）与一个值（第3参数）比较， //如果相等，则用另一个值（第2参数）与目标操作数（第1参数所指向的内存中的数）交换； //InterlockedExchange是不比较直接交换。整个操作过程是锁定内存的，其它处理器不会同时访问内存，从而实现多处理器环境下的线程互斥。 if ((newValue = (ULONG_PTR)_InterlockedCompareExchangePointer( (PVOID *)&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; } } 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( (PVOID *)&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; } } 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 | PH_QUEUED_LOCK_TRAVERSING)) != PH_QUEUED_LOCK_WAITERS) { // 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( (PVOID *)&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( (PVOID *)&QueuedLock->Value, (PVOID)newValue, (PVOID)value )) == value) { PhpfWakeQueuedLock(QueuedLock, currentValue); break; } } value = newValue; } } VOID FASTCALL PhfWakeForReleaseQueuedLock( _Inout_ PPH_QUEUED_LOCK QueuedLock, _In_ ULONG_PTR Value ) { ULONG_PTR newValue; newValue = Value + PH_QUEUED_LOCK_TRAVERSING; if ((ULONG_PTR)_InterlockedCompareExchangePointer( (PVOID *)&QueuedLock->Value, (PVOID)newValue, (PVOID)Value ) == Value) { PhpfWakeQueuedLock(QueuedLock, newValue); } } 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( (PVOID *)&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( (PVOID *)&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( (PVOID *)&QueuedLock->Value, (PVOID)newValue, (PVOID)value )) == value) { PhpfWakeQueuedLock(QueuedLock, currentValue); break; } } value = newValue; } } VOID FASTCALL PhfPulseCondition( _Inout_ PPH_CONDITION Condition ) { if (Condition->Value & PH_QUEUED_LOCK_WAITERS) PhpfWakeQueuedLockEx(Condition, Condition->Value, TRUE, FALSE); } VOID FASTCALL PhfPulseAllCondition( _Inout_ PPH_CONDITION Condition ) { if (Condition->Value & PH_QUEUED_LOCK_WAITERS) PhpfWakeQueuedLockEx(Condition, Condition->Value, TRUE, TRUE); } VOID FASTCALL PhfWaitForCondition( _Inout_ PPH_CONDITION 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; } } } VOID FASTCALL PhfWaitForConditionEx( _Inout_ PPH_CONDITION 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; } } } VOID FASTCALL PhfQueueWakeEvent( _Inout_ PPH_WAKE_EVENT 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( (PVOID *)&WakeEvent->Value, WaitBlock, value )) == value) break; value = newValue; } } VOID FASTCALL PhfSetWakeEvent( _Inout_ PPH_WAKE_EVENT 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((PVOID *)&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); } } NTSTATUS FASTCALL PhfWaitForWakeEvent( _Inout_ PPH_WAKE_EVENT 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; }
