ReactOS  0.4.14-dev-614-gbfd8a84
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 
28 typedef struct _COND_VAR_WAIT_ENTRY
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 
69 BOOLEAN *
71 {
72  return (BOOLEAN *)&Entry->ListRemovalHandled;
73 }
74 
75 static
78  IN PCOND_VAR_WAIT_ENTRY InsertEntry OPTIONAL,
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. */
111  YieldProcessor();
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 
188 static
189 VOID
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 
257 static
258 VOID
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 
352 VOID
353 NTAPI
355 VOID
356 NTAPI
358 VOID
359 NTAPI
361 VOID
362 NTAPI
364 
365 static
366 NTSTATUS
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  {
399  RtlReleaseSRWLockShared(SRWLock);
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  {
446  RtlAcquireSRWLockShared(SRWLock);
447  }
448  }
449  else
450  {
452  }
453 
454  /* Return whatever NtWaitForKeyedEvent returned. */
455  return Status;
456 }
457 
458 VOID
460 {
463 }
464 
465 VOID
467 {
471 }
472 
473 /* EXPORTED FUNCTIONS ********************************************************/
474 
475 VOID
476 NTAPI
478 {
479  ConditionVariable->Ptr = NULL;
480 }
481 
482 VOID
483 NTAPI
485 {
486  InternalWake(ConditionVariable, FALSE);
487 }
488 
489 VOID
490 NTAPI
492 {
493  InternalWake(ConditionVariable, TRUE);
494 }
495 
496 NTSTATUS
497 NTAPI
500  IN const LARGE_INTEGER * TimeOut OPTIONAL)
501 {
502  return InternalSleep(ConditionVariable,
505  0,
506  TimeOut);
507 }
508 
509 NTSTATUS
510 NTAPI
512  IN OUT PRTL_SRWLOCK SRWLock,
513  IN const LARGE_INTEGER * TimeOut OPTIONAL,
514  IN ULONG Flags)
515 {
516  return InternalSleep(ConditionVariable,
518  SRWLock,
519  Flags,
520  TimeOut);
521 }
522 
523 /* EOF */
struct _LIST_ENTRY * PLIST_ENTRY
VOID NTAPI RtlWakeConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable)
Definition: condvar.c:484
#define IN
Definition: typedefs.h:38
static VOID InternalWake(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN BOOLEAN ReleaseAll)
Definition: condvar.c:259
#define CONTAINING_COND_VAR_WAIT_ENTRY(address, field)
Definition: condvar.c:37
#define TRUE
Definition: types.h:120
NTSTATUS NTAPI RtlSleepConditionVariableCS(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN OUT PRTL_CRITICAL_SECTION CriticalSection, IN const LARGE_INTEGER *TimeOut OPTIONAL)
Definition: condvar.c:498
struct _COND_VAR_WAIT_ENTRY * PCOND_VAR_WAIT_ENTRY
struct _COND_VAR_WAIT_ENTRY COND_VAR_WAIT_ENTRY
PVOID WaitKey
Definition: condvar.c:33
struct _Entry Entry
Definition: kefuncs.h:640
NTSYSAPI NTSTATUS WINAPI NtWaitForKeyedEvent(HANDLE, const void *, BOOLEAN, const LARGE_INTEGER *)
VOID RtlpCloseKeyedEvent(VOID)
Definition: condvar.c:466
LONG NTSTATUS
Definition: precomp.h:26
VOID RtlpInitializeKeyedEvent(VOID)
Definition: condvar.c:459
NTSYSAPI NTSTATUS NTAPI RtlEnterCriticalSection(_In_ PRTL_CRITICAL_SECTION CriticalSection)
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
#define InsertTailList(ListHead, Entry)
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
#define STATUS_INVALID_HANDLE
Definition: ntstatus.h:231
VOID NTAPI RtlAcquireSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock)
Definition: srw.c:323
uint32_t ULONG_PTR
Definition: typedefs.h:63
FORCEINLINE BOOLEAN RemoveEntryList(_In_ PLIST_ENTRY Entry)
Definition: rtlfuncs.h:105
FORCEINLINE VOID YieldProcessor(VOID)
Definition: ke.h:32
BOOLEAN ListRemovalHandled
Definition: condvar.c:34
VOID NTAPI RtlReleaseSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock)
Definition: srw.c:524
_Must_inspect_result_ _In_ ULONG Flags
Definition: wsk.h:170
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
NTSYSAPI NTSTATUS NTAPI RtlLeaveCriticalSection(_In_ PRTL_CRITICAL_SECTION CriticalSection)
#define EVENT_ALL_ACCESS
Definition: isotest.c:82
CRITICAL_SECTION CriticalSection
Definition: iprtprio.c:40
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
VOID NTAPI RtlAcquireSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock)
Definition: srw.c:589
#define FORCEINLINE
Definition: ntbasedef.h:221
#define COND_VAR_LOCKED_FLAG
Definition: condvar.c:24
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
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
#define for
Definition: utility.h:88
NTSTATUS NTAPI NtClose(IN HANDLE Handle)
Definition: obhandle.c:3399
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
#define RTL_CONDITION_VARIABLE_LOCKMODE_SHARED
Definition: winnt_old.h:2550
FORCEINLINE ULONG_PTR InternalCmpXChgCondVarAcq(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN ULONG_PTR Exchange, IN ULONG_PTR Comperand)
Definition: condvar.c:48
Definition: condvar.c:28
Definition: typedefs.h:117
FORCEINLINE ULONG_PTR InternalCmpXChgCondVarRel(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, IN ULONG_PTR Exchange, IN ULONG_PTR Comperand)
Definition: condvar.c:59
LIST_ENTRY ListEntry
Definition: condvar.c:32
#define COND_VAR_ADDRESS_MASK
Definition: condvar.c:26
Status
Definition: gdiplustypes.h:24
static ULONG Timeout
Definition: ping.c:61
static HANDLE CondVarKeyedEventHandle
Definition: condvar.c:42
#define InterlockedCompareExchangePointerAcquire
Definition: interlocked.h:130
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
NTSYSAPI NTSTATUS WINAPI NtReleaseKeyedEvent(HANDLE, const void *, BOOLEAN, const LARGE_INTEGER *)
#define InterlockedCompareExchangePointerRelease
Definition: interlocked.h:131
VOID NTAPI RtlWakeAllConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable)
Definition: condvar.c:491
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
#define OUT
Definition: typedefs.h:39
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
FORCEINLINE BOOLEAN * InternalGetListRemovalHandledFlag(IN PCOND_VAR_WAIT_ENTRY Entry)
Definition: condvar.c:70
#define ULONG_PTR
Definition: config.h:101
NTSYSAPI NTSTATUS WINAPI NtCreateKeyedEvent(HANDLE *, ACCESS_MASK, const OBJECT_ATTRIBUTES *, ULONG)
VOID NTAPI RtlReleaseSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock)
Definition: srw.c:708
VOID NTAPI RtlInitializeConditionVariable(OUT PRTL_CONDITION_VARIABLE ConditionVariable)
Definition: condvar.c:477
#define CONST
Definition: pedump.c:81
base of all file and directory entries
Definition: entries.h:82
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:511
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68