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 #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 { 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 NTAPI 460 RtlpInitializeKeyedEvent(VOID) 461 { 462 ASSERT(CondVarKeyedEventHandle == NULL); 463 NtCreateKeyedEvent(&CondVarKeyedEventHandle, EVENT_ALL_ACCESS, NULL, 0); 464 } 465 466 VOID 467 NTAPI 468 RtlpCloseKeyedEvent(VOID) 469 { 470 ASSERT(CondVarKeyedEventHandle != NULL); 471 NtClose(CondVarKeyedEventHandle); 472 CondVarKeyedEventHandle = NULL; 473 } 474 475 /* EXPORTED FUNCTIONS ********************************************************/ 476 477 VOID 478 NTAPI 479 RtlInitializeConditionVariable(OUT PRTL_CONDITION_VARIABLE ConditionVariable) 480 { 481 ConditionVariable->Ptr = NULL; 482 } 483 484 VOID 485 NTAPI 486 RtlWakeConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable) 487 { 488 InternalWake(ConditionVariable, FALSE); 489 } 490 491 VOID 492 NTAPI 493 RtlWakeAllConditionVariable(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable) 494 { 495 InternalWake(ConditionVariable, TRUE); 496 } 497 498 NTSTATUS 499 NTAPI 500 RtlSleepConditionVariableCS(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, 501 IN OUT PRTL_CRITICAL_SECTION CriticalSection, 502 IN PLARGE_INTEGER TimeOut OPTIONAL) 503 { 504 return InternalSleep(ConditionVariable, 505 CriticalSection, 506 (PRTL_SRWLOCK)NULL, 507 0, 508 TimeOut); 509 } 510 511 NTSTATUS 512 NTAPI 513 RtlSleepConditionVariableSRW(IN OUT PRTL_CONDITION_VARIABLE ConditionVariable, 514 IN OUT PRTL_SRWLOCK SRWLock, 515 IN PLARGE_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 */ 526