Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526/* * COPYRIGHT: See COPYING in the top level directory * PROJECT: ReactOS system libraries * PURPOSE: Condition Variable Routines * PROGRAMMERS: Thomas Weidenmueller <w3seek@reactos.com> * Stephan A. R�ger */
/* NOTE: This functionality can be optimized for releasing single threads or for releasing all waiting threads at once. This implementation is optimized for releasing a single thread at a time. It wakes up sleeping threads in FIFO order. */
/* INCLUDES ******************************************************************/
#include <rtl_vista.h>
#define NDEBUG#include <debug.h>
/* INTERNAL TYPES ************************************************************/
#define COND_VAR_UNUSED_FLAG ((ULONG_PTR)1)#define COND_VAR_LOCKED_FLAG ((ULONG_PTR)2)#define COND_VAR_FLAGS_MASK ((ULONG_PTR)3)#define COND_VAR_ADDRESS_MASK (~COND_VAR_FLAGS_MASK)
typedef struct _COND_VAR_WAIT_ENTRY{ /* ListEntry must have an alignment of at least 32-bits, since we want COND_VAR_ADDRESS_MASK to cover all of the address. */ LIST_ENTRY ListEntry; PVOID WaitKey; BOOLEAN ListRemovalHandled;} COND_VAR_WAIT_ENTRY, * PCOND_VAR_WAIT_ENTRY;
#define CONTAINING_COND_VAR_WAIT_ENTRY(address, field) \ CONTAINING_RECORD(address, COND_VAR_WAIT_ENTRY, field)
/* GLOBALS *******************************************************************/
static HANDLE CondVarKeyedEventHandle = NULL;
/* INTERNAL FUNCTIONS ********************************************************/
FORCEINLINEULONG_PTRInternalCmpXChgCondVarAcq(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN ULONG_PTR Exchange, IN ULONG_PTR Comperand){ return (ULONG_PTR)InterlockedCompareExchangePointerAcquire(&ConditionVariable->Ptr, (PVOID)Exchange, (PVOID)Comperand);}
FORCEINLINEULONG_PTRInternalCmpXChgCondVarRel(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN ULONG_PTR Exchange, IN ULONG_PTR Comperand){ return (ULONG_PTR)InterlockedCompareExchangePointerRelease(&ConditionVariable->Ptr, (PVOID)Exchange, (PVOID)Comperand);}
FORCEINLINEBOOLEAN *InternalGetListRemovalHandledFlag(IN PCOND_VAR_WAIT_ENTRY Entry){ return (BOOLEAN *)&Entry->ListRemovalHandled;}
staticPCOND_VAR_WAIT_ENTRYInternalLockCondVar(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN PCOND_VAR_WAIT_ENTRY InsertEntry OPTIONAL, IN BOOLEAN * AbortIfLocked OPTIONAL){ /* InsertEntry and AbortIfLocked may be NULL on entry. This routine will return NULL if the lock was not acquired. Otherwise it has successfully acquired the lock and the return value is a valid reference to the list head associated with ConditionVariable. The caller must in this case call InternalUnlockCondVar later in order to unlock the condition variable.
If InsertEntry is NULL and there are no entries on the list, this routine will not acquire the lock and return NULL. If InsertEntry is not NULL this routine ensures that InsertEntry will be on the list when it returns successfully.
If the lock is owned by another thread and AbortIfLocked is NULL, this routine will block until it acquires the lock. If AbortIfLocked is not NULL and the lock is owned by another thread, this routine will periodically check if *AbortIfLocked is nonzero and if so, will return NULL instead of continuing the wait. */
ULONG_PTR OldVal = (ULONG_PTR)ConditionVariable->Ptr;
for (;;) { ULONG_PTR NewVal, LockRes; PLIST_ENTRY OldListHead;
if (OldVal & COND_VAR_LOCKED_FLAG) { /* The locked flag is set, indicating someone else currently holds the lock. We'll spin until this flag becomes clear or we're asked to abort. */ YieldProcessor();
if ((AbortIfLocked != NULL) && *AbortIfLocked) { /* The caller wants us to abort in this case. */ return NULL; }
/* Refresh OldVal and try again. */ OldVal = *(ULONG_PTR *)&ConditionVariable->Ptr; continue; }
/* Retrieve the list head currently associated with the condition variable. */ OldListHead = (PLIST_ENTRY)(OldVal & COND_VAR_ADDRESS_MASK); if (InsertEntry == NULL) { /* The caller doesn't want to put any entry on the list. */ if (OldListHead == NULL) { /* The list is empty, so there is nothing to lock. */ return NULL; }
/* The list isn't empty. In this case we need to preserve all of OldVal. */ NewVal = OldVal; } else { /* Let InsertEntry be the new list head. Preserve only the bits inside the COND_VAR_FLAGS_MASK range. */ NewVal = ((OldVal & COND_VAR_FLAGS_MASK) | (ULONG_PTR)&InsertEntry->ListEntry); }
/* Set the flag that indicates someone is holding the lock and try to update the condition variable thread-safe. */ NewVal |= COND_VAR_LOCKED_FLAG; LockRes = InternalCmpXChgCondVarAcq(ConditionVariable, NewVal, OldVal); if (LockRes == OldVal) { /* We successfully updated ConditionVariable the way we wanted and now hold the lock. */ if (InsertEntry == NULL) { /* We know that OldVal contains a valid address in this case. */ ASSERT(OldListHead != NULL); return CONTAINING_COND_VAR_WAIT_ENTRY(OldListHead, ListEntry); }
/* InsertEntry is not on the list yet, so add it. In any case InsertEntry will be the new list head. */ if (OldListHead == NULL) { /* List was empty before. */ InitializeListHead(&InsertEntry->ListEntry); } else { /* Make InsertEntry the last entry of the old list. As InsertEntry will take the role as new list head, OldListHead will become the second entry (InsertEntry->Flink) on the new list. */ InsertTailList(OldListHead, &InsertEntry->ListEntry); }
return InsertEntry; }
/* We didn't manage to update ConditionVariable, so try again. */ OldVal = LockRes; }}
staticVOIDInternalUnlockCondVar(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN PCOND_VAR_WAIT_ENTRY RemoveEntry OPTIONAL){ /* This routine assumes that the lock is being held on entry. RemoveEntry may be NULL. If it is not NULL, this routine assumes that RemoveEntry is on the list and will remove it before releasing the lock. */ ULONG_PTR OldVal = (ULONG_PTR)ConditionVariable->Ptr; PLIST_ENTRY NewHeadEntry;
ASSERT((OldVal & COND_VAR_LOCKED_FLAG) && (OldVal & COND_VAR_ADDRESS_MASK));
NewHeadEntry = (PLIST_ENTRY)(OldVal & COND_VAR_ADDRESS_MASK); if (RemoveEntry != NULL) { /* We have to drop RemoveEntry from the list. */ if (&RemoveEntry->ListEntry == NewHeadEntry) { /* RemoveEntry is the list head. */ if (!IsListEmpty(NewHeadEntry)) { /* The second entry in the list will become the new list head. It's from the thread that arrived right before the owner of RemoveEntry. */ NewHeadEntry = NewHeadEntry->Flink; RemoveEntryList(&RemoveEntry->ListEntry); } else { /* The list will be empty, so discard the list. */ NewHeadEntry = NULL; } } else { /* RemoveEntry is not the list head. The current list head will remain. */ RemoveEntryList(&RemoveEntry->ListEntry); }
/* Indicate to the owner of RemoveEntry that the entry was removed from the list. RemoveEntry may not be touched from here on. We don't use volatile semantics here since the cache will anyway be flushed soon when we update ConditionVariable. */ RemoveEntry->ListRemovalHandled = TRUE; }
/* Now unlock thread-safe, while preserving any flags within the COND_VAR_FLAGS_MASK range except for COND_VAR_LOCKED_FLAG. */ for (;;) { ULONG_PTR NewVal = ((OldVal & (COND_VAR_FLAGS_MASK ^ COND_VAR_LOCKED_FLAG)) | (ULONG_PTR)NewHeadEntry); ULONG_PTR LockRes = InternalCmpXChgCondVarRel(ConditionVariable, NewVal, OldVal); if (LockRes == OldVal) { /* We unlocked. */ break; }
/* Try again. */ OldVal = LockRes; }}
staticVOIDInternalWake(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN BOOLEAN ReleaseAll){ /* If ReleaseAll is zero on entry, one thread at most will be woken. Otherwise all waiting threads are woken. Wakeups happen in FIFO order. */ PCOND_VAR_WAIT_ENTRY CONST HeadEntry = InternalLockCondVar(ConditionVariable, NULL, NULL); PCOND_VAR_WAIT_ENTRY Entry; PCOND_VAR_WAIT_ENTRY NextEntry; LARGE_INTEGER Timeout; PCOND_VAR_WAIT_ENTRY RemoveOnUnlockEntry;
ASSERT(CondVarKeyedEventHandle != NULL);
if (HeadEntry == NULL) { /* There is noone there to wake up. In this case do nothing and return immediately. We don't stockpile releases. */ return; }
Timeout.QuadPart = 0; RemoveOnUnlockEntry = NULL;
/* Release sleeping threads. We will iterate from the last entry on the list to the first. Note that the loop condition is always true for the initial test. */ for (Entry = CONTAINING_COND_VAR_WAIT_ENTRY(HeadEntry->ListEntry.Blink, ListEntry); Entry != NULL; Entry = NextEntry) { NTSTATUS Status;
if (HeadEntry == Entry) { /* After the current entry we've iterated through the entire list in backward direction. Then exit.*/ NextEntry = NULL; } else { /* Store away the next reference right now, since we may not touch Entry anymore at the end of the block. */ NextEntry = CONTAINING_COND_VAR_WAIT_ENTRY(Entry->ListEntry.Blink, ListEntry); }
/* Wake the thread associated with this event. We will immediately return if we failed (zero timeout). */ Status = NtReleaseKeyedEvent(CondVarKeyedEventHandle, &Entry->WaitKey, FALSE, &Timeout);
if (!NT_SUCCESS(Status)) { /* We failed to wake a thread. We'll keep trying. */ ASSERT(STATUS_INVALID_HANDLE != Status); continue; }
/* We've woken a thread and will make sure this thread is removed from the list. */ if (HeadEntry == Entry) { /* This is the list head. We can't remove it as easily as other entries and will pass it to the unlock routine later (we will exit the loop after this round anyway). */ RemoveOnUnlockEntry = HeadEntry; } else { /* We can remove the entry right away. */ RemoveEntryList(&Entry->ListEntry);
/* Now tell the woken thread that removal from the list was already taken care of here so that this thread can resume its normal operation more quickly. We may not touch Entry after signaling this, since it may lie in invalid memory from there on. */ *InternalGetListRemovalHandledFlag(Entry) = TRUE; }
if (!ReleaseAll) { /* We've successfully woken one thread as the caller demanded. */ break; } }
InternalUnlockCondVar(ConditionVariable, RemoveOnUnlockEntry);}
VOIDNTAPIRtlAcquireSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock);VOIDNTAPIRtlAcquireSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock);VOIDNTAPIRtlReleaseSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock);VOIDNTAPIRtlReleaseSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock);
staticNTSTATUSInternalSleep(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN OUT PRTL_CRITICAL_SECTION CriticalSection OPTIONAL, IN OUT PRTL_SRWLOCK SRWLock OPTIONAL, IN ULONG SRWFlags, IN const LARGE_INTEGER * TimeOut OPTIONAL){ /* Either CriticalSection or SRWLock must be NULL, but not both. These caller provided lock must be held on entry and will be held again on return. */
COND_VAR_WAIT_ENTRY OwnEntry; NTSTATUS Status;
ASSERT(CondVarKeyedEventHandle != NULL); ASSERT((CriticalSection == NULL) != (SRWLock == NULL));
RtlZeroMemory(&OwnEntry, sizeof(OwnEntry));
/* Put OwnEntry on the list. */ InternalLockCondVar(ConditionVariable, &OwnEntry, NULL); InternalUnlockCondVar(ConditionVariable, NULL);
/* We can now drop the caller provided lock as a preparation for going to sleep. */ if (CriticalSection == NULL) { if (0 == (RTL_CONDITION_VARIABLE_LOCKMODE_SHARED & SRWFlags)) { RtlReleaseSRWLockExclusive(SRWLock); } else { RtlReleaseSRWLockShared(SRWLock); } } else { RtlLeaveCriticalSection(CriticalSection); }
/* Now sleep using the caller provided timeout. */ Status = NtWaitForKeyedEvent(CondVarKeyedEventHandle, &OwnEntry.WaitKey, FALSE, (PLARGE_INTEGER)TimeOut);
ASSERT(STATUS_INVALID_HANDLE != Status);
if (!*InternalGetListRemovalHandledFlag(&OwnEntry)) { /* Remove OwnEntry from the list again, since it still seems to be on the list. We will know for sure once we've acquired the lock. */ if (InternalLockCondVar(ConditionVariable, NULL, InternalGetListRemovalHandledFlag(&OwnEntry))) { /* Unlock and potentially remove OwnEntry. Self-removal is usually only necessary when a timeout occurred. */ InternalUnlockCondVar(ConditionVariable, !OwnEntry.ListRemovalHandled ? &OwnEntry : NULL); } }
#ifdef _DEBUG /* Clear OwnEntry to aid in detecting bugs. */ RtlZeroMemory(&OwnEntry, sizeof(OwnEntry));#endif
/* Reacquire the caller provided lock, as we are about to return. */ if (CriticalSection == NULL) { if (0 == (RTL_CONDITION_VARIABLE_LOCKMODE_SHARED & SRWFlags)) { RtlAcquireSRWLockExclusive(SRWLock); } else { RtlAcquireSRWLockShared(SRWLock); } } else { RtlEnterCriticalSection(CriticalSection); }
/* Return whatever NtWaitForKeyedEvent returned. */ return Status;}
VOIDNTAPIRtlpInitializeKeyedEvent(VOID){ ASSERT(CondVarKeyedEventHandle == NULL); NtCreateKeyedEvent(&CondVarKeyedEventHandle, EVENT_ALL_ACCESS, NULL, 0);}
VOIDNTAPIRtlpCloseKeyedEvent(VOID){ ASSERT(CondVarKeyedEventHandle != NULL); NtClose(CondVarKeyedEventHandle); CondVarKeyedEventHandle = NULL;}
/* EXPORTED FUNCTIONS ********************************************************/
VOIDNTAPIRtlInitializeConditionVariable(OUT PRTL_CONDITION_VARIABLE ConditionVariable){ ConditionVariable->Ptr = NULL;}
VOIDNTAPIRtlWakeConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable){ InternalWake(ConditionVariable, FALSE);}
VOIDNTAPIRtlWakeAllConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable){ InternalWake(ConditionVariable, TRUE);}
NTSTATUSNTAPIRtlSleepConditionVariableCS(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN OUT PRTL_CRITICAL_SECTION CriticalSection, IN PLARGE_INTEGER TimeOut OPTIONAL){ return InternalSleep(ConditionVariable, CriticalSection, (PRTL_SRWLOCK)NULL, 0, TimeOut);}
NTSTATUSNTAPIRtlSleepConditionVariableSRW(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN OUT PRTL_SRWLOCK SRWLock, IN PLARGE_INTEGER TimeOut OPTIONAL, IN ULONG Flags){ return InternalSleep(ConditionVariable, (PRTL_CRITICAL_SECTION)NULL, SRWLock, Flags, TimeOut);}
/* EOF */