reactos/dll/win32/ntdll_vista/condvar.c

   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. */
  32     LIST_ENTRY ListEntry;
  33     PVOID WaitKey;
  34     BOOLEAN ListRemovalHandled;
  35 } COND_VAR_WAIT_ENTRY, * PCOND_VAR_WAIT_ENTRY;
  36
  37 #define CONTAINING_COND_VAR_WAIT_ENTRY(address, field) \
  38     CONTAINING_RECORD(address, COND_VAR_WAIT_ENTRY, field)
  39
  40 /* GLOBALS *******************************************************************/
  41
  42 static HANDLE CondVarKeyedEventHandle = NULL;
  43
  44 /* INTERNAL FUNCTIONS ********************************************************/
  45
  46 FORCEINLINE
  47 ULONG_PTR
  48 InternalCmpXChgCondVarAcq(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable,
  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
  57 FORCEINLINE
  58 ULONG_PTR
  59 InternalCmpXChgCondVarRel(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable,
  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
  68 FORCEINLINE
  69 BOOLEAN *
  70 InternalGetListRemovalHandledFlag(IN PCOND_VAR_WAIT_ENTRY Entry)
  71 {
  72     return (BOOLEAN *)&Entry->ListRemovalHandled;
  73 }
  74
  75 static
  76 PCOND_VAR_WAIT_ENTRY
  77 InternalLockCondVar(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable,
  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
 190 InternalUnlockCondVar(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable,
 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
 259 InternalWake(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable,
 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);
 266     PCOND_VAR_WAIT_ENTRY Entry;
 267     PCOND_VAR_WAIT_ENTRY NextEntry;
 268     LARGE_INTEGER Timeout;
 269     PCOND_VAR_WAIT_ENTRY RemoveOnUnlockEntry;
 270
 271     ASSERT(CondVarKeyedEventHandle != NULL);
 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     {
 290         NTSTATUS Status;
 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). */
 307         Status = NtReleaseKeyedEvent(CondVarKeyedEventHandle,
 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. */
 315             ASSERT(STATUS_INVALID_HANDLE != Status);
 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. */
 338             *InternalGetListRemovalHandledFlag(Entry) = TRUE;
 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
 354 RtlAcquireSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock);
 355 VOID
 356 NTAPI
 357 RtlAcquireSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock);
 358 VOID
 359 NTAPI
 360 RtlReleaseSRWLockExclusive(IN OUT PRTL_SRWLOCK SRWLock);
 361 VOID
 362 NTAPI
 363 RtlReleaseSRWLockShared(IN OUT PRTL_SRWLOCK SRWLock);
 364
 365 static
 366 NTSTATUS
 367 InternalSleep(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable,
 368               IN OUT PRTL_CRITICAL_SECTION CriticalSection OPTIONAL,
 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;
 378     NTSTATUS Status;
 379
 380     ASSERT(CondVarKeyedEventHandle != NULL);
 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         {
 395             RtlReleaseSRWLockExclusive(SRWLock);
 396         }
 397         else
 398         {
 399             RtlReleaseSRWLockShared(SRWLock);
 400         }
 401     }
 402     else
 403     {
 404         RtlLeaveCriticalSection(CriticalSection);
 405     }
 406
 407     /* Now sleep using the caller provided timeout. */
 408     Status = NtWaitForKeyedEvent(CondVarKeyedEventHandle,
 409                                  &OwnEntry.WaitKey,
 410                                  FALSE,
 411                                  (PLARGE_INTEGER)TimeOut);
 412
 413     ASSERT(STATUS_INVALID_HANDLE != Status);
 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,
 422                                 InternalGetListRemovalHandledFlag(&OwnEntry)))
 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 #if _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         {
 442             RtlAcquireSRWLockExclusive(SRWLock);
 443         }
 444         else
 445         {
 446             RtlAcquireSRWLockShared(SRWLock);
 447         }
 448     }
 449     else
 450     {
 451         RtlEnterCriticalSection(CriticalSection);
 452     }
 453
 454     /* Return whatever NtWaitForKeyedEvent returned. */
 455     return Status;
 456 }
 457
 458 VOID
 459 RtlpInitializeKeyedEvent(VOID)
 460 {
 461     ASSERT(CondVarKeyedEventHandle == NULL);
 462     NtCreateKeyedEvent(&CondVarKeyedEventHandle, EVENT_ALL_ACCESS, NULL, 0);
 463 }
 464
 465 VOID
 466 RtlpCloseKeyedEvent(VOID)
 467 {
 468     ASSERT(CondVarKeyedEventHandle != NULL);
 469     NtClose(CondVarKeyedEventHandle);
 470     CondVarKeyedEventHandle = NULL;
 471 }
 472
 473 /* EXPORTED FUNCTIONS ********************************************************/
 474
 475 VOID
 476 NTAPI
 477 RtlInitializeConditionVariable(OUT PRTL_CONDITION_VARIABLE ConditionVariable)
 478 {
 479     ConditionVariable->Ptr = NULL;
 480 }
 481
 482 VOID
 483 NTAPI
 484 RtlWakeConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable)
 485 {
 486     InternalWake(ConditionVariable, FALSE);
 487 }
 488
 489 VOID
 490 NTAPI
 491 RtlWakeAllConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable)
 492 {
 493     InternalWake(ConditionVariable, TRUE);
 494 }
 495
 496 NTSYSAPI
 497 NTSTATUS
 498 NTAPI
 499 RtlSleepConditionVariableCS(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable,
 500                             IN OUT PRTL_CRITICAL_SECTION CriticalSection,
 501                             IN const LARGE_INTEGER * TimeOut OPTIONAL)
 502 {
 503     return InternalSleep(ConditionVariable,
 504                          CriticalSection,
 505                          (PRTL_SRWLOCK)NULL,
 506                          0,
 507                          TimeOut);
 508 }
 509
 510 NTSYSAPI
 511 NTSTATUS
 512 NTAPI
 513 RtlSleepConditionVariableSRW(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable,
 514                              IN OUT PRTL_SRWLOCK SRWLock,
 515                              IN const LARGE_INTEGER * TimeOut OPTIONAL,
 516                              IN ULONG Flags)
 517 {
 518     return InternalSleep(ConditionVariable,
 519                          (PRTL_CRITICAL_SECTION)NULL,
 520                          SRWLock,
 521                          Flags,
 522                          TimeOut);
 523 }
 524
 525 /* EOF */