ReactOS 0.4.15-dev-8138-g1e75ea8
condvar.c
Go to the documentation of this file.
1/*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS system libraries
4 * PURPOSE: Condition Variable Routines
5 * PROGRAMMERS: Thomas Weidenmueller <w3seek@reactos.com>
6 * Stephan A. R�ger
7 */
8
9/* NOTE: This functionality can be optimized for releasing single
10 threads or for releasing all waiting threads at once. This
11 implementation is optimized for releasing a single thread at a time.
12 It wakes up sleeping threads in FIFO order. */
13
14/* INCLUDES ******************************************************************/
15
16#include <rtl_vista.h>
17
18#define NDEBUG
19#include <debug.h>
20
21/* INTERNAL TYPES ************************************************************/
22
23#define COND_VAR_UNUSED_FLAG ((ULONG_PTR)1)
24#define COND_VAR_LOCKED_FLAG ((ULONG_PTR)2)
25#define COND_VAR_FLAGS_MASK ((ULONG_PTR)3)
26#define COND_VAR_ADDRESS_MASK (~COND_VAR_FLAGS_MASK)
27
29{
30 /* ListEntry must have an alignment of at least 32-bits, since we
31 want COND_VAR_ADDRESS_MASK to cover all of the address. */
36
37#define CONTAINING_COND_VAR_WAIT_ENTRY(address, field) \
38 CONTAINING_RECORD(address, COND_VAR_WAIT_ENTRY, field)
39
40/* GLOBALS *******************************************************************/
41
43
44/* INTERNAL FUNCTIONS ********************************************************/
45
49 IN ULONG_PTR Exchange,
50 IN ULONG_PTR Comperand)
51{
52 return (ULONG_PTR)InterlockedCompareExchangePointerAcquire(&ConditionVariable->Ptr,
53 (PVOID)Exchange,
54 (PVOID)Comperand);
55}
56
60 IN ULONG_PTR Exchange,
61 IN ULONG_PTR Comperand)
62{
63 return (ULONG_PTR)InterlockedCompareExchangePointerRelease(&ConditionVariable->Ptr,
64 (PVOID)Exchange,
65 (PVOID)Comperand);
66}
67
69BOOLEAN *
71{
72 return (BOOLEAN *)&Entry->ListRemovalHandled;
73}
74
75static
79 IN BOOLEAN * AbortIfLocked OPTIONAL)
80{
81 /* InsertEntry and AbortIfLocked may be NULL on entry. This routine
82 will return NULL if the lock was not acquired. Otherwise it has
83 successfully acquired the lock and the return value is a valid
84 reference to the list head associated with ConditionVariable.
85 The caller must in this case call InternalUnlockCondVar later
86 in order to unlock the condition variable.
87
88 If InsertEntry is NULL and there are no entries on the list, this
89 routine will not acquire the lock and return NULL. If InsertEntry
90 is not NULL this routine ensures that InsertEntry will be on the
91 list when it returns successfully.
92
93 If the lock is owned by another thread and AbortIfLocked is NULL,
94 this routine will block until it acquires the lock. If AbortIfLocked
95 is not NULL and the lock is owned by another thread, this routine
96 will periodically check if *AbortIfLocked is nonzero and if so, will
97 return NULL instead of continuing the wait. */
98
99 ULONG_PTR OldVal = (ULONG_PTR)ConditionVariable->Ptr;
100
101 for (;;)
102 {
103 ULONG_PTR NewVal, LockRes;
104 PLIST_ENTRY OldListHead;
105
106 if (OldVal & COND_VAR_LOCKED_FLAG)
107 {
108 /* The locked flag is set, indicating someone else currently
109 holds the lock. We'll spin until this flag becomes
110 clear or we're asked to abort. */
112
113 if ((AbortIfLocked != NULL) && *AbortIfLocked)
114 {
115 /* The caller wants us to abort in this case. */
116 return NULL;
117 }
118
119 /* Refresh OldVal and try again. */
120 OldVal = *(ULONG_PTR *)&ConditionVariable->Ptr;
121 continue;
122 }
123
124 /* Retrieve the list head currently associated with the
125 condition variable. */
126 OldListHead = (PLIST_ENTRY)(OldVal & COND_VAR_ADDRESS_MASK);
127 if (InsertEntry == NULL)
128 {
129 /* The caller doesn't want to put any entry on the list. */
130 if (OldListHead == NULL)
131 {
132 /* The list is empty, so there is nothing to lock. */
133 return NULL;
134 }
135
136 /* The list isn't empty. In this case we need to preserve
137 all of OldVal. */
138 NewVal = OldVal;
139 }
140 else
141 {
142 /* Let InsertEntry be the new list head. Preserve only the
143 bits inside the COND_VAR_FLAGS_MASK range. */
144 NewVal = ((OldVal & COND_VAR_FLAGS_MASK) |
145 (ULONG_PTR)&InsertEntry->ListEntry);
146 }
147
148 /* Set the flag that indicates someone is holding the lock and
149 try to update the condition variable thread-safe. */
150 NewVal |= COND_VAR_LOCKED_FLAG;
151 LockRes = InternalCmpXChgCondVarAcq(ConditionVariable, NewVal, OldVal);
152 if (LockRes == OldVal)
153 {
154 /* We successfully updated ConditionVariable the way we
155 wanted and now hold the lock. */
156 if (InsertEntry == NULL)
157 {
158 /* We know that OldVal contains a valid address in
159 this case. */
160 ASSERT(OldListHead != NULL);
161 return CONTAINING_COND_VAR_WAIT_ENTRY(OldListHead, ListEntry);
162 }
163
164 /* InsertEntry is not on the list yet, so add it. In any
165 case InsertEntry will be the new list head. */
166 if (OldListHead == NULL)
167 {
168 /* List was empty before. */
169 InitializeListHead(&InsertEntry->ListEntry);
170 }
171 else
172 {
173 /* Make InsertEntry the last entry of the old list.
174 As InsertEntry will take the role as new list head,
175 OldListHead will become the second entry (InsertEntry->Flink)
176 on the new list. */
177 InsertTailList(OldListHead, &InsertEntry->ListEntry);
178 }
179
180 return InsertEntry;
181 }
182
183 /* We didn't manage to update ConditionVariable, so try again. */
184 OldVal = LockRes;
185 }
186}
187
188static
189VOID
191 IN PCOND_VAR_WAIT_ENTRY RemoveEntry OPTIONAL)
192{
193 /* This routine assumes that the lock is being held on entry.
194 RemoveEntry may be NULL. If it is not NULL, this routine
195 assumes that RemoveEntry is on the list and will remove it
196 before releasing the lock. */
197 ULONG_PTR OldVal = (ULONG_PTR)ConditionVariable->Ptr;
198 PLIST_ENTRY NewHeadEntry;
199
200 ASSERT((OldVal & COND_VAR_LOCKED_FLAG) &&
201 (OldVal & COND_VAR_ADDRESS_MASK));
202
203 NewHeadEntry = (PLIST_ENTRY)(OldVal & COND_VAR_ADDRESS_MASK);
204 if (RemoveEntry != NULL)
205 {
206 /* We have to drop RemoveEntry from the list. */
207 if (&RemoveEntry->ListEntry == NewHeadEntry)
208 {
209 /* RemoveEntry is the list head. */
210 if (!IsListEmpty(NewHeadEntry))
211 {
212 /* The second entry in the list will become the new
213 list head. It's from the thread that arrived
214 right before the owner of RemoveEntry. */
215 NewHeadEntry = NewHeadEntry->Flink;
216 RemoveEntryList(&RemoveEntry->ListEntry);
217 }
218 else
219 {
220 /* The list will be empty, so discard the list. */
221 NewHeadEntry = NULL;
222 }
223 }
224 else
225 {
226 /* RemoveEntry is not the list head. The current list head
227 will remain. */
228 RemoveEntryList(&RemoveEntry->ListEntry);
229 }
230
231 /* Indicate to the owner of RemoveEntry that the entry
232 was removed from the list. RemoveEntry may not be touched
233 from here on. We don't use volatile semantics here since
234 the cache will anyway be flushed soon when we update
235 ConditionVariable. */
236 RemoveEntry->ListRemovalHandled = TRUE;
237 }
238
239 /* Now unlock thread-safe, while preserving any flags within the
240 COND_VAR_FLAGS_MASK range except for COND_VAR_LOCKED_FLAG. */
241 for (;;)
242 {
243 ULONG_PTR NewVal = ((OldVal & (COND_VAR_FLAGS_MASK ^ COND_VAR_LOCKED_FLAG)) |
244 (ULONG_PTR)NewHeadEntry);
245 ULONG_PTR LockRes = InternalCmpXChgCondVarRel(ConditionVariable, NewVal, OldVal);
246 if (LockRes == OldVal)
247 {
248 /* We unlocked. */
249 break;
250 }
251
252 /* Try again. */
253 OldVal = LockRes;
254 }
255}
256
257static
258VOID
260 IN BOOLEAN ReleaseAll)
261{
262 /* If ReleaseAll is zero on entry, one thread at most will be woken.
263 Otherwise all waiting threads are woken. Wakeups happen in FIFO
264 order. */
265 PCOND_VAR_WAIT_ENTRY CONST HeadEntry = InternalLockCondVar(ConditionVariable, NULL, NULL);
267 PCOND_VAR_WAIT_ENTRY NextEntry;
269 PCOND_VAR_WAIT_ENTRY RemoveOnUnlockEntry;
270
272
273 if (HeadEntry == NULL)
274 {
275 /* There is noone there to wake up. In this case do nothing
276 and return immediately. We don't stockpile releases. */
277 return;
278 }
279
280 Timeout.QuadPart = 0;
281 RemoveOnUnlockEntry = NULL;
282
283 /* Release sleeping threads. We will iterate from the last entry on
284 the list to the first. Note that the loop condition is always
285 true for the initial test. */
286 for (Entry = CONTAINING_COND_VAR_WAIT_ENTRY(HeadEntry->ListEntry.Blink, ListEntry);
287 Entry != NULL;
288 Entry = NextEntry)
289 {
291
292 if (HeadEntry == Entry)
293 {
294 /* After the current entry we've iterated through the
295 entire list in backward direction. Then exit.*/
296 NextEntry = NULL;
297 }
298 else
299 {
300 /* Store away the next reference right now, since we may
301 not touch Entry anymore at the end of the block. */
302 NextEntry = CONTAINING_COND_VAR_WAIT_ENTRY(Entry->ListEntry.Blink, ListEntry);
303 }
304
305 /* Wake the thread associated with this event. We will
306 immediately return if we failed (zero timeout). */
308 &Entry->WaitKey,
309 FALSE,
310 &Timeout);
311
312 if (!NT_SUCCESS(Status))
313 {
314 /* We failed to wake a thread. We'll keep trying. */
316 continue;
317 }
318
319 /* We've woken a thread and will make sure this thread
320 is removed from the list. */
321 if (HeadEntry == Entry)
322 {
323 /* This is the list head. We can't remove it as easily as
324 other entries and will pass it to the unlock routine
325 later (we will exit the loop after this round anyway). */
326 RemoveOnUnlockEntry = HeadEntry;
327 }
328 else
329 {
330 /* We can remove the entry right away. */
331 RemoveEntryList(&Entry->ListEntry);
332
333 /* Now tell the woken thread that removal from the list was
334 already taken care of here so that this thread can resume
335 its normal operation more quickly. We may not touch
336 Entry after signaling this, since it may lie in invalid
337 memory from there on. */
339 }
340
341 if (!ReleaseAll)
342 {
343 /* We've successfully woken one thread as the caller
344 demanded. */
345 break;
346 }
347 }
348
349 InternalUnlockCondVar(ConditionVariable, RemoveOnUnlockEntry);
350}
351
352VOID
353NTAPI
355VOID
356NTAPI
358VOID
359NTAPI
361VOID
362NTAPI
364
365static
369 IN OUT PRTL_SRWLOCK SRWLock OPTIONAL,
370 IN ULONG SRWFlags,
371 IN const LARGE_INTEGER * TimeOut OPTIONAL)
372{
373 /* Either CriticalSection or SRWLock must be NULL, but not both.
374 These caller provided lock must be held on entry and will be
375 held again on return. */
376
377 COND_VAR_WAIT_ENTRY OwnEntry;
379
381 ASSERT((CriticalSection == NULL) != (SRWLock == NULL));
382
383 RtlZeroMemory(&OwnEntry, sizeof(OwnEntry));
384
385 /* Put OwnEntry on the list. */
386 InternalLockCondVar(ConditionVariable, &OwnEntry, NULL);
387 InternalUnlockCondVar(ConditionVariable, NULL);
388
389 /* We can now drop the caller provided lock as a preparation for
390 going to sleep. */
391 if (CriticalSection == NULL)
392 {
393 if (0 == (RTL_CONDITION_VARIABLE_LOCKMODE_SHARED & SRWFlags))
394 {
396 }
397 else
398 {
400 }
401 }
402 else
403 {
405 }
406
407 /* Now sleep using the caller provided timeout. */
409 &OwnEntry.WaitKey,
410 FALSE,
411 (PLARGE_INTEGER)TimeOut);
412
414
415 if (!*InternalGetListRemovalHandledFlag(&OwnEntry))
416 {
417 /* Remove OwnEntry from the list again, since it still seems to
418 be on the list. We will know for sure once we've acquired
419 the lock. */
420 if (InternalLockCondVar(ConditionVariable,
421 NULL,
423 {
424 /* Unlock and potentially remove OwnEntry. Self-removal is
425 usually only necessary when a timeout occurred. */
426 InternalUnlockCondVar(ConditionVariable,
427 !OwnEntry.ListRemovalHandled ?
428 &OwnEntry : NULL);
429 }
430 }
431
432#ifdef _DEBUG
433 /* Clear OwnEntry to aid in detecting bugs. */
434 RtlZeroMemory(&OwnEntry, sizeof(OwnEntry));
435#endif
436
437 /* Reacquire the caller provided lock, as we are about to return. */
438 if (CriticalSection == NULL)
439 {
440 if (0 == (RTL_CONDITION_VARIABLE_LOCKMODE_SHARED & SRWFlags))
441 {
443 }
444 else
445 {
447 }
448 }
449 else
450 {
452 }
453
454 /* Return whatever NtWaitForKeyedEvent returned. */
455 return Status;
456}
457
458VOID
459NTAPI
461{
464}
465
466VOID
467NTAPI
469{
473}
474
475/* EXPORTED FUNCTIONS ********************************************************/
476
477VOID
478NTAPI
480{
481 ConditionVariable->Ptr = NULL;
482}
483
484VOID
485NTAPI
487{
488 InternalWake(ConditionVariable, FALSE);
489}
490
491VOID
492NTAPI
494{
495 InternalWake(ConditionVariable, TRUE);
496}
497
499NTAPI
502 IN const LARGE_INTEGER * TimeOut OPTIONAL)
503{
504 return InternalSleep(ConditionVariable,
507 0,
508 TimeOut);
509}
510
512NTAPI
514 IN OUT PRTL_SRWLOCK SRWLock,
515 IN const LARGE_INTEGER * TimeOut OPTIONAL,
516 IN ULONG Flags)
517{
518 return InternalSleep(ConditionVariable,
520 SRWLock,
521 Flags,
522 TimeOut);
523}
524
525/* EOF */
unsigned char BOOLEAN
LONG NTSTATUS
Definition: precomp.h:26
static VOID InternalWake(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN BOOLEAN ReleaseAll)
Definition: condvar.c:259
static VOID InternalUnlockCondVar(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN PCOND_VAR_WAIT_ENTRY RemoveEntry OPTIONAL)
Definition: condvar.c:190
#define COND_VAR_FLAGS_MASK
Definition: condvar.c:25
NTSTATUS NTAPI RtlSleepConditionVariableCS(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN OUT PRTL_CRITICAL_SECTION CriticalSection, IN const LARGE_INTEGER *TimeOut OPTIONAL)
Definition: condvar.c:500
FORCEINLINE ULONG_PTR InternalCmpXChgCondVarAcq(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN ULONG_PTR Exchange, IN ULONG_PTR Comperand)
Definition: condvar.c:48
FORCEINLINE ULONG_PTR InternalCmpXChgCondVarRel(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN ULONG_PTR Exchange, IN ULONG_PTR Comperand)
Definition: condvar.c:59
static NTSTATUS InternalSleep(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)
Definition: condvar.c:367
VOID NTAPI RtlReleaseSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock)
Definition: srw.c:710
VOID NTAPI RtlInitializeConditionVariable(OUT PRTL_CONDITION_VARIABLE ConditionVariable)
Definition: condvar.c:479
static HANDLE CondVarKeyedEventHandle
Definition: condvar.c:42
struct _COND_VAR_WAIT_ENTRY COND_VAR_WAIT_ENTRY
NTSTATUS NTAPI RtlSleepConditionVariableSRW(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN OUT PRTL_SRWLOCK SRWLock, IN const LARGE_INTEGER *TimeOut OPTIONAL, IN ULONG Flags)
Definition: condvar.c:513
#define COND_VAR_ADDRESS_MASK
Definition: condvar.c:26
#define CONTAINING_COND_VAR_WAIT_ENTRY(address, field)
Definition: condvar.c:37
VOID NTAPI RtlAcquireSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock)
Definition: srw.c:591
VOID NTAPI RtlWakeAllConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable)
Definition: condvar.c:493
#define COND_VAR_LOCKED_FLAG
Definition: condvar.c:24
static PCOND_VAR_WAIT_ENTRY InternalLockCondVar(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN PCOND_VAR_WAIT_ENTRY InsertEntry OPTIONAL, IN BOOLEAN *AbortIfLocked OPTIONAL)
Definition: condvar.c:77
VOID NTAPI RtlpCloseKeyedEvent(VOID)
Definition: condvar.c:468
VOID NTAPI RtlWakeConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable)
Definition: condvar.c:486
VOID NTAPI RtlReleaseSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock)
Definition: srw.c:526
VOID NTAPI RtlAcquireSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock)
Definition: srw.c:325
FORCEINLINE BOOLEAN * InternalGetListRemovalHandledFlag(IN PCOND_VAR_WAIT_ENTRY Entry)
Definition: condvar.c:70
VOID NTAPI RtlpInitializeKeyedEvent(VOID)
Definition: condvar.c:460
struct _COND_VAR_WAIT_ENTRY * PCOND_VAR_WAIT_ENTRY
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define ULONG_PTR
Definition: config.h:101
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986
#define InsertTailList(ListHead, Entry)
#define IsListEmpty(ListHead)
Definition: env_spec_w32.h:954
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
Status
Definition: gdiplustypes.h:25
NTSYSAPI NTSTATUS WINAPI NtCreateKeyedEvent(HANDLE *, ACCESS_MASK, const OBJECT_ATTRIBUTES *, ULONG)
NTSYSAPI NTSTATUS WINAPI NtWaitForKeyedEvent(HANDLE, const void *, BOOLEAN, const LARGE_INTEGER *)
NTSYSAPI NTSTATUS WINAPI NtReleaseKeyedEvent(HANDLE, const void *, BOOLEAN, const LARGE_INTEGER *)
#define InterlockedCompareExchangePointerRelease
Definition: interlocked.h:131
#define InterlockedCompareExchangePointerAcquire
Definition: interlocked.h:130
CRITICAL_SECTION CriticalSection
Definition: iprtprio.c:40
#define EVENT_ALL_ACCESS
Definition: isotest.c:82
#define ASSERT(a)
Definition: mode.c:44
#define for
Definition: utility.h:88
NTSYSAPI NTSTATUS NTAPI RtlEnterCriticalSection(_In_ PRTL_CRITICAL_SECTION CriticalSection)
NTSYSAPI NTSTATUS NTAPI RtlLeaveCriticalSection(_In_ PRTL_CRITICAL_SECTION CriticalSection)
NTSTATUS NTAPI NtClose(IN HANDLE Handle)
Definition: obhandle.c:3402
#define STATUS_INVALID_HANDLE
Definition: ntstatus.h:245
#define CONST
Definition: pedump.c:81
static ULONG Timeout
Definition: ping.c:61
#define YieldProcessor
Definition: ke.h:48
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68
base of all file and directory entries
Definition: entries.h:83
Definition: condvar.c:29
BOOLEAN ListRemovalHandled
Definition: condvar.c:34
LIST_ENTRY ListEntry
Definition: condvar.c:32
PVOID WaitKey
Definition: condvar.c:33
Definition: typedefs.h:120
struct _LIST_ENTRY * PLIST_ENTRY
#define NTAPI
Definition: typedefs.h:36
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
uint32_t ULONG_PTR
Definition: typedefs.h:65
#define IN
Definition: typedefs.h:39
uint32_t ULONG
Definition: typedefs.h:59
#define OUT
Definition: typedefs.h:40
#define FORCEINLINE
Definition: wdftypes.h:67
#define RTL_CONDITION_VARIABLE_LOCKMODE_SHARED
Definition: winnt_old.h:2754
_Must_inspect_result_ _In_ ULONG Flags
Definition: wsk.h:170