ntoskrnl/ex/pushlock.c

   1 /*
   2  * COPYRIGHT:       See COPYING in the top level directory
   3  * PROJECT:         ReactOS Kernel
   4  * FILE:            ntoskrnl/ex/pushlock.c
   5  * PURPOSE:         Pushlock and Cache-Aware Pushlock Implementation
   6  * PROGRAMMER:      Alex Ionescu (alex.ionescu@reactos.com)
   7  */
   8
   9 /* INCLUDES *****************************************************************/
  10
  11 #include <ntoskrnl.h>
  12 #define NDEBUG
  13 #include <debug.h>
  14
  15 /* DATA **********************************************************************/
  16
  17 ULONG ExPushLockSpinCount = 0;
  18
  19 #undef EX_PUSH_LOCK
  20 #undef PEX_PUSH_LOCK
  21
  22 /* PRIVATE FUNCTIONS *********************************************************/
  23
  24 #ifdef _WIN64
  25 #define InterlockedAndPointer(ptr,val) InterlockedAnd64((PLONGLONG)ptr,(LONGLONG)val)
  26 #else
  27 #define InterlockedAndPointer(ptr,val) InterlockedAnd((PLONG)ptr,(LONG)val)
  28 #endif
  29
  30 /*++
  31  * @name ExpInitializePushLocks
  32  *
  33  *     The ExpInitializePushLocks routine initialized Pushlock support.
  34  *
  35  * @param None.
  36  *
  37  * @return None.
  38  *
  39  * @remarks The ExpInitializePushLocks routine sets up the spin on SMP machines.
  40  *
  41  *--*/
  42 VOID
  43 NTAPI
  44 INIT_FUNCTION
  45 ExpInitializePushLocks(VOID)
  46 {
  47 #ifdef CONFIG_SMP
  48     /* Initialize an internal 1024-iteration spin for MP CPUs */
  49     if (KeNumberProcessors > 1)
  50         ExPushLockSpinCount = 1024;
  51 #endif
  52 }
  53
  54 /*++
  55  * @name ExfWakePushLock
  56  *
  57  *     The ExfWakePushLock routine wakes a Pushlock that is in the waiting
  58  *     state.
  59  *
  60  * @param PushLock
  61  *        Pointer to a pushlock that is waiting.
  62  *
  63  * @param OldValue
  64  *        Last known value of the pushlock before this routine was called.
  65  *
  66  * @return None.
  67  *
  68  * @remarks This is an internal routine; do not call it manually. Only the system
  69  *          can properly know if the pushlock is ready to be awakened or not.
  70  *          External callers should use ExfTrytoWakePushLock.
  71  *
  72  *--*/
  73 VOID
  74 FASTCALL
  75 ExfWakePushLock(PEX_PUSH_LOCK PushLock,
  76                 EX_PUSH_LOCK OldValue)
  77 {
  78     EX_PUSH_LOCK NewValue;
  79     PEX_PUSH_LOCK_WAIT_BLOCK PreviousWaitBlock, FirstWaitBlock, LastWaitBlock;
  80     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock;
  81     KIRQL OldIrql;
  82
  83     /* Start main wake loop */
  84     for (;;)
  85     {
  86         /* Sanity checks */
  87         ASSERT(!OldValue.MultipleShared);
  88
  89         /* Check if it's locked */
  90         while (OldValue.Locked)
  91         {
  92             /* It's not waking anymore */
  93             NewValue.Value = OldValue.Value &~ EX_PUSH_LOCK_WAKING;
  94
  95             /* Sanity checks */
  96             ASSERT(!NewValue.Waking);
  97             ASSERT(NewValue.Locked);
  98             ASSERT(NewValue.Waiting);
  99
 100             /* Write the New Value */
 101             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 102                                                              NewValue.Ptr,
 103                                                              OldValue.Ptr);
 104             if (NewValue.Value == OldValue.Value) return;
 105
 106             /* Someone changed the value behind our back, update it*/
 107             OldValue = NewValue;
 108         }
 109
 110         /* Save the First Block */
 111         FirstWaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)(OldValue.Value &
 112                           ~EX_PUSH_LOCK_PTR_BITS);
 113         WaitBlock = FirstWaitBlock;
 114
 115         /* Try to find the last block */
 116         while (TRUE)
 117         {
 118             /* Get the last wait block */
 119             LastWaitBlock = WaitBlock->Last;
 120
 121             /* Check if we found it */
 122             if (LastWaitBlock)
 123             {
 124                 /* Use it */
 125                 WaitBlock = LastWaitBlock;
 126                 break;
 127             }
 128
 129             /* Save the previous block */
 130             PreviousWaitBlock = WaitBlock;
 131
 132             /* Move to next block */
 133             WaitBlock = WaitBlock->Next;
 134
 135             /* Save the previous block */
 136             WaitBlock->Previous = PreviousWaitBlock;
 137         }
 138
 139         /* Check if the last Wait Block is not Exclusive or if it's the only one */
 140         PreviousWaitBlock = WaitBlock->Previous;
 141         if (!(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE) ||
 142             !(PreviousWaitBlock))
 143         {
 144             /* Destroy the pushlock */
 145             NewValue.Value = 0;
 146             ASSERT(!NewValue.Waking);
 147
 148             /* Write the New Value */
 149             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 150                                                              NewValue.Ptr,
 151                                                              OldValue.Ptr);
 152             if (NewValue.Value == OldValue.Value) break;
 153
 154             /* Someone changed the value behind our back, update it*/
 155             OldValue = NewValue;
 156         }
 157         else
 158         {
 159             /* Link the wait blocks */
 160             FirstWaitBlock->Last = PreviousWaitBlock;
 161             WaitBlock->Previous = NULL;
 162
 163             /* Sanity checks */
 164             ASSERT(FirstWaitBlock != WaitBlock);
 165             ASSERT(PushLock->Waiting);
 166
 167             /* Remove waking bit from pushlock */
 168             InterlockedAndPointer(&PushLock->Value, ~EX_PUSH_LOCK_WAKING);
 169
 170             /* Leave the loop */
 171             break;
 172         }
 173     }
 174
 175     /* Check if there's a previous block */
 176     OldIrql = DISPATCH_LEVEL;
 177     if (WaitBlock->Previous)
 178     {
 179         /* Raise to Dispatch */
 180         KeRaiseIrql(DISPATCH_LEVEL, &OldIrql);
 181     }
 182
 183     /* Signaling loop */
 184     for (;;)
 185     {
 186         /* Get the previous Wait block */
 187         PreviousWaitBlock = WaitBlock->Previous;
 188
 189         /* Sanity check */
 190         ASSERT(!WaitBlock->Signaled);
 191
 192 #if DBG
 193         /* We are about to get signaled */
 194         WaitBlock->Signaled = TRUE;
 195 #endif
 196
 197         /* Set the Wait Bit in the Wait Block */
 198         if (!InterlockedBitTestAndReset(&WaitBlock->Flags, 1))
 199         {
 200             /* Nobody signaled us, so do it */
 201             KeSignalGateBoostPriority(&WaitBlock->WakeGate);
 202         }
 203
 204         /* Set the wait block and check if there still is one to loop*/
 205         WaitBlock = PreviousWaitBlock;
 206         if (!WaitBlock) break;
 207     }
 208
 209     /* Check if we have to lower back the IRQL */
 210     if (OldIrql != DISPATCH_LEVEL) KeLowerIrql(OldIrql);
 211 }
 212
 213 /*++
 214  * @name ExpOptimizePushLockList
 215  *
 216  *     The ExpOptimizePushLockList routine optimizes the list of waiters
 217  *     associated to a pushlock's wait block.
 218  *
 219  * @param PushLock
 220  *        Pointer to a pushlock whose waiter list needs to be optimized.
 221  *
 222  * @param OldValue
 223  *        Last known value of the pushlock before this routine was called.
 224  *
 225  * @return None.
 226  *
 227  * @remarks At the end of the optimization, the pushlock will also be wakened.
 228  *
 229  *--*/
 230 VOID
 231 FASTCALL
 232 ExpOptimizePushLockList(PEX_PUSH_LOCK PushLock,
 233                         EX_PUSH_LOCK OldValue)
 234 {
 235     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock, PreviousWaitBlock, FirstWaitBlock;
 236     EX_PUSH_LOCK NewValue;
 237
 238     /* Start main loop */
 239     for (;;)
 240     {
 241         /* Check if we've been unlocked */
 242         if (!OldValue.Locked)
 243         {
 244             /* Wake us up and leave */
 245             ExfWakePushLock(PushLock, OldValue);
 246             break;
 247         }
 248
 249         /* Get the wait block */
 250         WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)(OldValue.Value &
 251                                                ~EX_PUSH_LOCK_PTR_BITS);
 252
 253         /* Loop the blocks */
 254         FirstWaitBlock = WaitBlock;
 255         while (TRUE)
 256         {
 257             /* Get the last wait block */
 258             LastWaitBlock = WaitBlock->Last;
 259             if (LastWaitBlock)
 260             {
 261                 /* Set this as the new last block, we're done */
 262                 FirstWaitBlock->Last = LastWaitBlock;
 263                 break;
 264             }
 265
 266             /* Save the block */
 267             PreviousWaitBlock = WaitBlock;
 268
 269             /* Get the next block */
 270             WaitBlock = WaitBlock->Next;
 271
 272             /* Save the previous */
 273             WaitBlock->Previous = PreviousWaitBlock;
 274         }
 275
 276         /* Remove the wake bit */
 277         NewValue.Value = OldValue.Value &~ EX_PUSH_LOCK_WAKING;
 278
 279         /* Sanity checks */
 280         ASSERT(NewValue.Locked);
 281         ASSERT(!NewValue.Waking);
 282
 283         /* Update the value */
 284         NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 285                                                          NewValue.Ptr,
 286                                                          OldValue.Ptr);
 287
 288         /* If we updated correctly, leave */
 289         if (NewValue.Value == OldValue.Value) break;
 290
 291         /* Update value */
 292         OldValue = NewValue;
 293     }
 294 }
 295
 296 /*++
 297  * @name ExTimedWaitForUnblockPushLock
 298  *
 299  *     The ExTimedWaitForUnblockPushLock routine waits for a pushlock
 300  *     to be unblocked, for a specified internal.
 301  *
 302  * @param PushLock
 303  *        Pointer to a pushlock whose waiter list needs to be optimized.
 304  *
 305  * @param WaitBlock
 306  *        Pointer to the pushlock's wait block.
 307  *
 308  * @param Timeout
 309  *        Amount of time to wait for this pushlock to be unblocked.
 310  *
 311  * @return STATUS_SUCCESS is the pushlock is now unblocked, otherwise the error
 312  *         code returned by KeWaitForSingleObject.
 313  *
 314  * @remarks If the wait fails, then a manual unblock is attempted.
 315  *
 316  *--*/
 317 NTSTATUS
 318 FASTCALL
 319 ExTimedWaitForUnblockPushLock(IN PEX_PUSH_LOCK PushLock,
 320                               IN PVOID WaitBlock,
 321                               IN PLARGE_INTEGER Timeout)
 322 {
 323     NTSTATUS Status;
 324
 325     /* Initialize the wait event */
 326     KeInitializeEvent(&((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)->WakeEvent,
 327                       SynchronizationEvent,
 328                       FALSE);
 329
 330 #ifdef CONFIG_SMP
 331     /* Spin on the push lock if necessary */
 332     if (ExPushLockSpinCount)
 333     {
 334         ULONG i = ExPushLockSpinCount;
 335
 336         do
 337         {
 338             /* Check if we got lucky and can leave early */
 339             if (!(*(volatile LONG *)&((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)->Flags & EX_PUSH_LOCK_WAITING))
 340                 return STATUS_SUCCESS;
 341
 342             YieldProcessor();
 343         } while (--i);
 344     }
 345 #endif
 346
 347     /* Now try to remove the wait bit */
 348     if (InterlockedBitTestAndReset(&((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)->Flags,
 349                                    EX_PUSH_LOCK_FLAGS_WAIT_V))
 350     {
 351         /* Nobody removed it already, let's do a full wait */
 352         Status = KeWaitForSingleObject(&((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)->
 353                                        WakeEvent,
 354                                        WrPushLock,
 355                                        KernelMode,
 356                                        FALSE,
 357                                        Timeout);
 358         /* Check if the wait was satisfied */
 359         if (Status != STATUS_SUCCESS)
 360         {
 361             /* Try unblocking the pushlock if it was not */
 362             ExfUnblockPushLock(PushLock, WaitBlock);
 363         }
 364     }
 365     else
 366     {
 367         /* Someone beat us to it, no need to wait */
 368         Status = STATUS_SUCCESS;
 369     }
 370
 371     /* Return status */
 372     return Status;
 373 }
 374
 375 /*++
 376  * @name ExWaitForUnblockPushLock
 377  *
 378  *     The ExWaitForUnblockPushLock routine waits for a pushlock
 379  *     to be unblocked, for a specified internal.
 380  *
 381  * @param PushLock
 382  *        Pointer to a pushlock whose waiter list needs to be optimized.
 383  *
 384  * @param WaitBlock
 385  *        Pointer to the pushlock's wait block.
 386  *
 387  * @return STATUS_SUCCESS is the pushlock is now unblocked, otherwise the error
 388  *         code returned by KeWaitForSingleObject.
 389  *
 390  * @remarks If the wait fails, then a manual unblock is attempted.
 391  *
 392  *--*/
 393 VOID
 394 FASTCALL
 395 ExWaitForUnblockPushLock(IN PEX_PUSH_LOCK PushLock,
 396                          IN PVOID WaitBlock)
 397 {
 398     /* Call the timed function with no timeout */
 399     ExTimedWaitForUnblockPushLock(PushLock, WaitBlock, NULL);
 400 }
 401
 402 /*++
 403  * @name ExBlockPushLock
 404  *
 405  *     The ExBlockPushLock routine blocks a pushlock.
 406  *
 407  * @param PushLock
 408  *        Pointer to a pushlock whose waiter list needs to be optimized.
 409  *
 410  * @param WaitBlock
 411  *        Pointer to the pushlock's wait block.
 412  *
 413  * @return None.
 414  *
 415  * @remarks None.
 416  *
 417  *--*/
 418 VOID
 419 FASTCALL
 420 ExBlockPushLock(PEX_PUSH_LOCK PushLock,
 421                 PVOID pWaitBlock)
 422 {
 423     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock = pWaitBlock;
 424     EX_PUSH_LOCK NewValue, OldValue;
 425
 426     /* Detect invalid wait block alignment */
 427     ASSERT(((ULONG_PTR)pWaitBlock & 0xF) == 0);
 428
 429     /* Set the waiting bit */
 430     WaitBlock->Flags = EX_PUSH_LOCK_FLAGS_WAIT;
 431
 432     /* Get the old value */
 433     OldValue = *PushLock;
 434
 435     /* Start block loop */
 436     for (;;)
 437     {
 438         /* Link the wait blocks */
 439         WaitBlock->Next = OldValue.Ptr;
 440
 441         /* Set the new wait block value */
 442         NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 443                                                          WaitBlock,
 444                                                          OldValue.Ptr);
 445         if (OldValue.Ptr == NewValue.Ptr) break;
 446
 447         /* Try again with the new value */
 448         OldValue = NewValue;
 449     }
 450 }
 451
 452 /* PUBLIC FUNCTIONS **********************************************************/
 453
 454 /*++
 455  * @name ExAcquirePushLockExclusive
 456  * @implemented NT5.1
 457  *
 458  *     The ExAcquirePushLockExclusive macro exclusively acquires a PushLock.
 459  *
 460  * @params PushLock
 461  *         Pointer to the pushlock which is to be acquired.
 462  *
 463  * @return None.
 464  *
 465  * @remarks Callers of ExAcquirePushLockShared must be running at IRQL <= APC_LEVEL.
 466  *          This macro should usually be paired up with KeAcquireCriticalRegion.
 467  *
 468  *--*/
 469 VOID
 470 FASTCALL
 471 ExfAcquirePushLockExclusive(PEX_PUSH_LOCK PushLock)
 472 {
 473     EX_PUSH_LOCK OldValue = *PushLock, NewValue, TempValue;
 474     BOOLEAN NeedWake;
 475     EX_PUSH_LOCK_WAIT_BLOCK Block;
 476     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock = &Block;
 477
 478     /* Start main loop */
 479     for (;;)
 480     {
 481         /* Check if it's unlocked */
 482         if (!OldValue.Locked)
 483         {
 484             /* Lock it */
 485             NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 486             ASSERT(NewValue.Locked);
 487
 488             /* Set the new value */
 489             if (InterlockedCompareExchangePointer(&PushLock->Ptr,
 490                                                   NewValue.Ptr,
 491                                                   OldValue.Ptr) != OldValue.Ptr)
 492             {
 493                 /* Retry */
 494                 OldValue = *PushLock;
 495                 continue;
 496             }
 497
 498             /* Break out of the loop */
 499             break;
 500         }
 501         else
 502         {
 503             /* We'll have to create a Waitblock */
 504             WaitBlock->Flags = EX_PUSH_LOCK_FLAGS_EXCLUSIVE |
 505                                EX_PUSH_LOCK_FLAGS_WAIT;
 506             WaitBlock->Previous = NULL;
 507             NeedWake = FALSE;
 508
 509             /* Check if there is already a waiter */
 510             if (OldValue.Waiting)
 511             {
 512                 /* Nobody is the last waiter yet */
 513                 WaitBlock->Last = NULL;
 514
 515                 /* We are an exclusive waiter */
 516                 WaitBlock->ShareCount = 0;
 517
 518                 /* Set the current Wait Block pointer */
 519                 WaitBlock->Next = (PEX_PUSH_LOCK_WAIT_BLOCK)(
 520                                    OldValue.Value &~ EX_PUSH_LOCK_PTR_BITS);
 521
 522                 /* Point to ours */
 523                 NewValue.Value = (OldValue.Value & EX_PUSH_LOCK_MULTIPLE_SHARED) |
 524                                   EX_PUSH_LOCK_LOCK |
 525                                   EX_PUSH_LOCK_WAKING |
 526                                   EX_PUSH_LOCK_WAITING |
 527                                   (ULONG_PTR)WaitBlock;
 528
 529                 /* Check if the pushlock was already waking */
 530                 if (!OldValue.Waking) NeedWake = TRUE;
 531             }
 532             else
 533             {
 534                 /* We are the first waiter, so loop the wait block */
 535                 WaitBlock->Last = WaitBlock;
 536
 537                 /* Set the share count */
 538                 WaitBlock->ShareCount = (LONG)OldValue.Shared;
 539
 540                 /* Check if someone is sharing this pushlock */
 541                 if (OldValue.Shared > 1)
 542                 {
 543                     /* Point to our wait block */
 544                     NewValue.Value = EX_PUSH_LOCK_MULTIPLE_SHARED |
 545                                      EX_PUSH_LOCK_LOCK |
 546                                      EX_PUSH_LOCK_WAITING |
 547                                      (ULONG_PTR)WaitBlock;
 548                 }
 549                 else
 550                 {
 551                     /* No shared count */
 552                     WaitBlock->ShareCount = 0;
 553
 554                     /* Point to our wait block */
 555                     NewValue.Value = EX_PUSH_LOCK_LOCK |
 556                                      EX_PUSH_LOCK_WAITING |
 557                                      (ULONG_PTR)WaitBlock;
 558                 }
 559             }
 560
 561 #if DBG
 562             /* Setup the Debug Wait Block */
 563             WaitBlock->Signaled = 0;
 564             WaitBlock->OldValue = OldValue;
 565             WaitBlock->NewValue = NewValue;
 566             WaitBlock->PushLock = PushLock;
 567 #endif
 568
 569             /* Sanity check */
 570             ASSERT(NewValue.Waiting);
 571             ASSERT(NewValue.Locked);
 572
 573             /* Write the new value */
 574             TempValue = NewValue;
 575             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 576                                                              NewValue.Ptr,
 577                                                              OldValue.Ptr);
 578             if (NewValue.Value != OldValue.Value)
 579             {
 580                 /* Retry */
 581                 OldValue = *PushLock;
 582                 continue;
 583             }
 584
 585             /* Check if the pushlock needed waking */
 586             if (NeedWake)
 587             {
 588                 /* Scan the Waiters and Wake PushLocks */
 589                 ExpOptimizePushLockList(PushLock, TempValue);
 590             }
 591
 592             /* Set up the Wait Gate */
 593             KeInitializeGate(&WaitBlock->WakeGate);
 594
 595 #ifdef CONFIG_SMP
 596             /* Now spin on the push lock if necessary */
 597             if (ExPushLockSpinCount)
 598             {
 599                 ULONG i = ExPushLockSpinCount;
 600
 601                 do
 602                 {
 603                     if (!(*(volatile LONG *)&WaitBlock->Flags & EX_PUSH_LOCK_WAITING))
 604                         break;
 605
 606                     YieldProcessor();
 607                 } while (--i);
 608             }
 609 #endif
 610
 611             /* Now try to remove the wait bit */
 612             if (InterlockedBitTestAndReset(&WaitBlock->Flags, 1))
 613             {
 614                 /* Nobody removed it already, let's do a full wait */
 615                 KeWaitForGate(&WaitBlock->WakeGate, WrPushLock, KernelMode);
 616                 ASSERT(WaitBlock->Signaled);
 617             }
 618
 619             /* We shouldn't be shared anymore */
 620             ASSERT((WaitBlock->ShareCount == 0));
 621
 622             /* Loop again */
 623             OldValue = NewValue;
 624         }
 625     }
 626 }
 627
 628 /*++
 629  * @name ExAcquirePushLockShared
 630  * @implemented NT5.1
 631  *
 632  *     The ExAcquirePushLockShared routine acquires a shared PushLock.
 633  *
 634  * @params PushLock
 635  *         Pointer to the pushlock which is to be acquired.
 636  *
 637  * @return None.
 638  *
 639  * @remarks Callers of ExAcquirePushLockShared must be running at IRQL <= APC_LEVEL.
 640  *          This macro should usually be paired up with KeAcquireCriticalRegion.
 641  *
 642  *--*/
 643 VOID
 644 FASTCALL
 645 ExfAcquirePushLockShared(PEX_PUSH_LOCK PushLock)
 646 {
 647     EX_PUSH_LOCK OldValue = *PushLock, NewValue;
 648     BOOLEAN NeedWake;
 649     EX_PUSH_LOCK_WAIT_BLOCK Block;
 650     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock = &Block;
 651
 652     /* Start main loop */
 653     for (;;)
 654     {
 655         /* Check if it's unlocked or if it's waiting without any sharers */
 656         if (!(OldValue.Locked) || (!(OldValue.Waiting) && (OldValue.Shared > 0)))
 657         {
 658             /* Check if anyone is waiting on it */
 659             if (!OldValue.Waiting)
 660             {
 661                 /* Increase the share count and lock it */
 662                 NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 663                 NewValue.Shared++;
 664             }
 665             else
 666             {
 667                 /* Simply set the lock bit */
 668                 NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 669             }
 670
 671             /* Sanity check */
 672             ASSERT(NewValue.Locked);
 673
 674             /* Set the new value */
 675             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 676                                                              NewValue.Ptr,
 677                                                              OldValue.Ptr);
 678             if (NewValue.Value != OldValue.Value)
 679             {
 680                 /* Retry */
 681                 OldValue = *PushLock;
 682                 continue;
 683             }
 684
 685             /* Break out of the loop */
 686             break;
 687         }
 688         else
 689         {
 690             /* We'll have to create a Waitblock */
 691             WaitBlock->Flags = EX_PUSH_LOCK_FLAGS_WAIT;
 692             WaitBlock->ShareCount = 0;
 693             NeedWake = FALSE;
 694             WaitBlock->Previous = NULL;
 695
 696             /* Check if there is already a waiter */
 697             if (OldValue.Waiting)
 698             {
 699                 /* Set the current Wait Block pointer */
 700                 WaitBlock->Next = (PEX_PUSH_LOCK_WAIT_BLOCK)(
 701                                    OldValue.Value &~ EX_PUSH_LOCK_PTR_BITS);
 702
 703                 /* Nobody is the last waiter yet */
 704                 WaitBlock->Last = NULL;
 705
 706                 /* Point to ours */
 707                 NewValue.Value = (OldValue.Value & (EX_PUSH_LOCK_MULTIPLE_SHARED |
 708                                                     EX_PUSH_LOCK_LOCK)) |
 709                                   EX_PUSH_LOCK_WAKING |
 710                                   EX_PUSH_LOCK_WAITING |
 711                                   (ULONG_PTR)WaitBlock;
 712
 713                 /* Check if the pushlock was already waking */
 714                 if (!OldValue.Waking) NeedWake = TRUE;
 715             }
 716             else
 717             {
 718                 /* We are the first waiter, so loop the wait block */
 719                 WaitBlock->Last = WaitBlock;
 720
 721                 /* Point to our wait block */
 722                 NewValue.Value = (OldValue.Value & EX_PUSH_LOCK_PTR_BITS) |
 723                                   EX_PUSH_LOCK_WAITING |
 724                                   (ULONG_PTR)WaitBlock;
 725             }
 726
 727             /* Sanity check */
 728             ASSERT(NewValue.Waiting);
 729
 730 #if DBG
 731             /* Setup the Debug Wait Block */
 732             WaitBlock->Signaled = 0;
 733             WaitBlock->OldValue = OldValue;
 734             WaitBlock->NewValue = NewValue;
 735             WaitBlock->PushLock = PushLock;
 736 #endif
 737
 738             /* Write the new value */
 739             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 740                                                              NewValue.Ptr,
 741                                                              OldValue.Ptr);
 742             if (NewValue.Ptr != OldValue.Ptr)
 743             {
 744                 /* Retry */
 745                 OldValue = *PushLock;
 746                 continue;
 747             }
 748
 749             /* Update the value now */
 750             OldValue = NewValue;
 751
 752             /* Check if the pushlock needed waking */
 753             if (NeedWake)
 754             {
 755                 /* Scan the Waiters and Wake PushLocks */
 756                 ExpOptimizePushLockList(PushLock, OldValue);
 757             }
 758
 759             /* Set up the Wait Gate */
 760             KeInitializeGate(&WaitBlock->WakeGate);
 761
 762 #ifdef CONFIG_SMP
 763             /* Now spin on the push lock if necessary */
 764             if (ExPushLockSpinCount)
 765             {
 766                 ULONG i = ExPushLockSpinCount;
 767
 768                 do
 769                 {
 770                     if (!(*(volatile LONG *)&WaitBlock->Flags & EX_PUSH_LOCK_WAITING))
 771                         break;
 772
 773                     YieldProcessor();
 774                 } while (--i);
 775             }
 776 #endif
 777
 778             /* Now try to remove the wait bit */
 779             if (InterlockedBitTestAndReset(&WaitBlock->Flags, 1))
 780             {
 781                 /* Fast-path did not work, we need to do a full wait */
 782                 KeWaitForGate(&WaitBlock->WakeGate, WrPushLock, KernelMode);
 783                 ASSERT(WaitBlock->Signaled);
 784             }
 785
 786             /* We shouldn't be shared anymore */
 787             ASSERT((WaitBlock->ShareCount == 0));
 788         }
 789     }
 790 }
 791
 792 /*++
 793  * @name ExfReleasePushLock
 794  * @implemented NT5.1
 795  *
 796  *     The ExReleasePushLock routine releases a previously acquired PushLock.
 797  *
 798  *
 799  * @params PushLock
 800  *         Pointer to a previously acquired pushlock.
 801  *
 802  * @return None.
 803  *
 804  * @remarks Callers of ExfReleasePushLock must be running at IRQL <= APC_LEVEL.
 805  *          This macro should usually be paired up with KeLeaveCriticalRegion.
 806  *
 807  *--*/
 808 VOID
 809 FASTCALL
 810 ExfReleasePushLock(PEX_PUSH_LOCK PushLock)
 811 {
 812     EX_PUSH_LOCK OldValue = *PushLock, NewValue, WakeValue;
 813     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock;
 814
 815     /* Sanity check */
 816     ASSERT(OldValue.Locked);
 817
 818     /* Start main loop */
 819     while (TRUE)
 820     {
 821         /* Check if someone is waiting on the lock */
 822         if (!OldValue.Waiting)
 823         {
 824             /* Check if it's shared */
 825             if (OldValue.Shared > 1)
 826             {
 827                 /* Write the Old Value but decrease share count */
 828                 NewValue = OldValue;
 829                 NewValue.Shared--;
 830             }
 831             else
 832             {
 833                 /* Simply clear the lock */
 834                 NewValue.Value = 0;
 835             }
 836
 837             /* Write the New Value */
 838             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 839                                                              NewValue.Ptr,
 840                                                              OldValue.Ptr);
 841             if (NewValue.Value == OldValue.Value) return;
 842
 843             /* Did it enter a wait state? */
 844             OldValue = NewValue;
 845         }
 846         else
 847         {
 848             /* Ok, we do know someone is waiting on it. Are there more then one? */
 849             if (OldValue.MultipleShared)
 850             {
 851                 /* Get the wait block */
 852                 WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)(OldValue.Value &
 853                                                        ~EX_PUSH_LOCK_PTR_BITS);
 854
 855                 /* Loop until we find the last wait block */
 856                 while (TRUE)
 857                 {
 858                     /* Get the last wait block */
 859                     LastWaitBlock = WaitBlock->Last;
 860
 861                     /* Did it exist? */
 862                     if (LastWaitBlock)
 863                     {
 864                         /* Choose it */
 865                         WaitBlock = LastWaitBlock;
 866                         break;
 867                     }
 868
 869                     /* Keep searching */
 870                     WaitBlock = WaitBlock->Next;
 871                 }
 872
 873                 /* Make sure the Share Count is above 0 */
 874                 if (WaitBlock->ShareCount > 0)
 875                 {
 876                     /* This shouldn't be an exclusive wait block */
 877                     ASSERT(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE);
 878
 879                     /* Do the decrease and check if the lock isn't shared anymore */
 880                     if (InterlockedDecrement(&WaitBlock->ShareCount) > 0) return;
 881                 }
 882             }
 883
 884             /*
 885              * If nobody was waiting on the block, then we possibly reduced the number
 886              * of times the pushlock was shared, and we unlocked it.
 887              * If someone was waiting, and more then one person is waiting, then we
 888              * reduced the number of times the pushlock is shared in the wait block.
 889              * Therefore, at this point, we can now 'satisfy' the wait.
 890              */
 891             for (;;)
 892             {
 893                 /* Now we need to see if it's waking */
 894                 if (OldValue.Waking)
 895                 {
 896                     /* Remove the lock and multiple shared bits */
 897                     NewValue.Value = OldValue.Value;
 898                     NewValue.MultipleShared = FALSE;
 899                     NewValue.Locked = FALSE;
 900
 901                     /* Sanity check */
 902                     ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
 903
 904                     /* Write the new value */
 905                     NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 906                                                                      NewValue.Ptr,
 907                                                                      OldValue.Ptr);
 908                     if (NewValue.Value == OldValue.Value) return;
 909                 }
 910                 else
 911                 {
 912                     /* Remove the lock and multiple shared bits */
 913                     NewValue.Value = OldValue.Value;
 914                     NewValue.MultipleShared = FALSE;
 915                     NewValue.Locked = FALSE;
 916
 917                     /* It's not already waking, so add the wake bit */
 918                     NewValue.Waking = TRUE;
 919
 920                     /* Sanity check */
 921                     ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
 922
 923                     /* Write the new value */
 924                     WakeValue = NewValue;
 925                     NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 926                                                                      NewValue.Ptr,
 927                                                                      OldValue.Ptr);
 928                     if (NewValue.Value != OldValue.Value) continue;
 929
 930                     /* The write was successful. The pushlock is Unlocked and Waking */
 931                     ExfWakePushLock(PushLock, WakeValue);
 932                     return;
 933                 }
 934             }
 935         }
 936     }
 937 }
 938
 939 /*++
 940  * @name ExfReleasePushLockShared
 941  * @implemented NT5.2
 942  *
 943  *     The ExfReleasePushLockShared macro releases a previously acquired PushLock.
 944  *
 945  * @params PushLock
 946  *         Pointer to a previously acquired pushlock.
 947  *
 948  * @return None.
 949  *
 950  * @remarks Callers of ExReleasePushLockShared must be running at IRQL <= APC_LEVEL.
 951  *          This macro should usually be paired up with KeLeaveCriticalRegion.
 952  *
 953  *--*/
 954 VOID
 955 FASTCALL
 956 ExfReleasePushLockShared(PEX_PUSH_LOCK PushLock)
 957 {
 958     EX_PUSH_LOCK OldValue = *PushLock, NewValue, WakeValue;
 959     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock;
 960
 961     /* Check if someone is waiting on the lock */
 962     while (!OldValue.Waiting)
 963     {
 964         /* Check if it's shared */
 965         if (OldValue.Shared > 1)
 966         {
 967             /* Write the Old Value but decrease share count */
 968             NewValue = OldValue;
 969             NewValue.Shared--;
 970         }
 971         else
 972         {
 973             /* Simply clear the lock */
 974             NewValue.Value = 0;
 975         }
 976
 977         /* Write the New Value */
 978         NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 979                                                          NewValue.Ptr,
 980                                                          OldValue.Ptr);
 981         if (NewValue.Value == OldValue.Value) return;
 982
 983         /* Did it enter a wait state? */
 984         OldValue = NewValue;
 985     }
 986
 987     /* Ok, we do know someone is waiting on it. Are there more then one? */
 988     if (OldValue.MultipleShared)
 989     {
 990         /* Get the wait block */
 991         WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)(OldValue.Value &
 992                                                ~EX_PUSH_LOCK_PTR_BITS);
 993
 994         /* Loop until we find the last wait block */
 995         while (TRUE)
 996         {
 997             /* Get the last wait block */
 998             LastWaitBlock = WaitBlock->Last;
 999
1000             /* Did it exist? */
1001             if (LastWaitBlock)
1002             {
1003                 /* Choose it */
1004                 WaitBlock = LastWaitBlock;
1005                 break;
1006             }
1007
1008             /* Keep searching */
1009             WaitBlock = WaitBlock->Next;
1010         }
1011
1012         /* Sanity checks */
1013         ASSERT(WaitBlock->ShareCount > 0);
1014         ASSERT(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE);
1015
1016         /* Do the decrease and check if the lock isn't shared anymore */
1017         if (InterlockedDecrement(&WaitBlock->ShareCount) > 0) return;
1018     }
1019
1020     /*
1021      * If nobody was waiting on the block, then we possibly reduced the number
1022      * of times the pushlock was shared, and we unlocked it.
1023      * If someone was waiting, and more then one person is waiting, then we
1024      * reduced the number of times the pushlock is shared in the wait block.
1025      * Therefore, at this point, we can now 'satisfy' the wait.
1026      */
1027     for (;;)
1028     {
1029         /* Now we need to see if it's waking */
1030         if (OldValue.Waking)
1031         {
1032             /* Remove the lock and multiple shared bits */
1033             NewValue.Value = OldValue.Value;
1034             NewValue.MultipleShared = FALSE;
1035             NewValue.Locked = FALSE;
1036
1037             /* Sanity check */
1038             ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
1039
1040             /* Write the new value */
1041             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
1042                                                              NewValue.Ptr,
1043                                                              OldValue.Ptr);
1044             if (NewValue.Value == OldValue.Value) return;
1045         }
1046         else
1047         {
1048             /* Remove the lock and multiple shared bits */
1049             NewValue.Value = OldValue.Value;
1050             NewValue.MultipleShared = FALSE;
1051             NewValue.Locked = FALSE;
1052
1053             /* It's not already waking, so add the wake bit */
1054             NewValue.Waking = TRUE;
1055
1056             /* Sanity check */
1057             ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
1058
1059             /* Write the new value */
1060             WakeValue = NewValue;
1061             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
1062                                                              NewValue.Ptr,
1063                                                              OldValue.Ptr);
1064             if (NewValue.Value != OldValue.Value) continue;
1065
1066             /* The write was successful. The pushlock is Unlocked and Waking */
1067             ExfWakePushLock(PushLock, WakeValue);
1068             return;
1069         }
1070     }
1071 }
1072
1073 /*++
1074  * ExfReleasePushLockExclusive
1075  * @implemented NT5.2
1076  *
1077  *     The ExfReleasePushLockExclusive routine releases a previously
1078  *     exclusively acquired PushLock.
1079  *
1080  * @params PushLock
1081  *         Pointer to a previously acquired pushlock.
1082  *
1083  * @return None.
1084  *
1085  * @remarks Callers of ExReleasePushLockExclusive must be running at IRQL <= APC_LEVEL.
1086  *          This macro should usually be paired up with KeLeaveCriticalRegion.
1087  *
1088  *--*/
1089 VOID
1090 FASTCALL
1091 ExfReleasePushLockExclusive(PEX_PUSH_LOCK PushLock)
1092 {
1093     EX_PUSH_LOCK NewValue, WakeValue;
1094     EX_PUSH_LOCK OldValue = *PushLock;
1095
1096     /* Loop until we can change */
1097     for (;;)
1098     {
1099         /* Sanity checks */
1100         ASSERT(OldValue.Locked);
1101         ASSERT(OldValue.Waiting || OldValue.Shared == 0);
1102
1103         /* Check if it's waiting and not yet waking */
1104         if ((OldValue.Waiting) && !(OldValue.Waking))
1105         {
1106             /* Remove the lock bit, and add the wake bit */
1107             NewValue.Value = (OldValue.Value &~ EX_PUSH_LOCK_LOCK) |
1108                               EX_PUSH_LOCK_WAKING;
1109
1110             /* Sanity check */
1111             ASSERT(NewValue.Waking && !NewValue.Locked);
1112
1113             /* Write the New Value. Save our original value for waking */
1114             WakeValue = NewValue;
1115             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
1116                                                              NewValue.Ptr,
1117                                                              OldValue.Ptr);
1118
1119             /* Check if the value changed behind our back */
1120             if (NewValue.Value == OldValue.Value)
1121             {
1122                 /* Wake the Pushlock */
1123                 ExfWakePushLock(PushLock, WakeValue);
1124                 break;
1125             }
1126         }
1127         else
1128         {
1129             /* A simple unlock */
1130             NewValue.Value = OldValue.Value &~ EX_PUSH_LOCK_LOCK;
1131
1132             /* Sanity check */
1133             ASSERT(NewValue.Waking || !NewValue.Waiting);
1134
1135             /* Write the New Value */
1136             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
1137                                                              NewValue.Ptr,
1138                                                              OldValue.Ptr);
1139
1140             /* Check if the value changed behind our back */
1141             if (NewValue.Value == OldValue.Value) break;
1142         }
1143
1144         /* Loop again */
1145         OldValue = NewValue;
1146     }
1147 }
1148
1149 /*++
1150  * @name ExfTryToWakePushLock
1151  * @implemented NT5.2
1152  *
1153  *     The ExfTryToWakePushLock attemps to wake a waiting pushlock.
1154  *
1155  * @param PushLock
1156  *        Pointer to a PushLock which is in the wait state.
1157  *
1158  * @return None.
1159  *
1160  * @remarks The pushlock must be in a wait state and must not be already waking.
1161  *
1162  *--*/
1163 VOID
1164 FASTCALL
1165 ExfTryToWakePushLock(PEX_PUSH_LOCK PushLock)
1166 {
1167     EX_PUSH_LOCK OldValue = *PushLock, NewValue;
1168
1169     /*
1170      * If the Pushlock is not waiting on anything, or if it's already waking up
1171      * and locked, don't do anything
1172      */
1173     if ((OldValue.Waking) || (OldValue.Locked) || !(OldValue.Waiting)) return;
1174
1175     /* Make it Waking */
1176     NewValue = OldValue;
1177     NewValue.Waking = TRUE;
1178
1179     /* Write the New Value */
1180     if (InterlockedCompareExchangePointer(&PushLock->Ptr,
1181                                           NewValue.Ptr,
1182                                           OldValue.Ptr) == OldValue.Ptr)
1183     {
1184         /* Wake the Pushlock */
1185         ExfWakePushLock(PushLock, NewValue);
1186     }
1187 }
1188
1189 /*++
1190  * @name ExfUnblockPushLock
1191  * @implemented NT5.1
1192  *
1193  *     The ExfUnblockPushLock routine unblocks a previously blocked PushLock.
1194  *
1195  * @param PushLock
1196  *        Pointer to a previously blocked PushLock.
1197  *
1198  * @return None.
1199  *
1200  * @remarks Callers of ExfUnblockPushLock can be running at any IRQL.
1201  *
1202  *--*/
1203 VOID
1204 FASTCALL
1205 ExfUnblockPushLock(PEX_PUSH_LOCK PushLock,
1206                    PVOID CurrentWaitBlock)
1207 {
1208     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, NextWaitBlock;
1209     KIRQL OldIrql = DISPATCH_LEVEL;
1210
1211     /* Get the wait block and erase the previous one */
1212     WaitBlock = InterlockedExchangePointer(&PushLock->Ptr, NULL);
1213     if (WaitBlock)
1214     {
1215         /* Check if there is a linked pushlock and raise IRQL appropriately */
1216         if (WaitBlock->Next) KeRaiseIrql(DISPATCH_LEVEL, &OldIrql);
1217
1218         /* Start block loop */
1219         while (WaitBlock)
1220         {
1221             /* Get the next block */
1222             NextWaitBlock = WaitBlock->Next;
1223
1224             /* Remove the wait flag from the Wait block */
1225             if (!InterlockedBitTestAndReset(&WaitBlock->Flags, EX_PUSH_LOCK_FLAGS_WAIT_V))
1226             {
1227                 /* Nobody removed the flag before us, so signal the event */
1228                 KeSetEventBoostPriority(&WaitBlock->WakeEvent, NULL);
1229             }
1230
1231             /* Try the next one */
1232             WaitBlock = NextWaitBlock;
1233         }
1234
1235         /* Lower IRQL if needed */
1236         if (OldIrql != DISPATCH_LEVEL) KeLowerIrql(OldIrql);
1237     }
1238
1239     /* Check if we got a wait block that's pending */
1240     if ((CurrentWaitBlock) &&
1241         (((PEX_PUSH_LOCK_WAIT_BLOCK)CurrentWaitBlock)->Flags &
1242            EX_PUSH_LOCK_FLAGS_WAIT))
1243     {
1244         /* Wait for the pushlock to be unblocked */
1245         ExWaitForUnblockPushLock(PushLock, CurrentWaitBlock);
1246     }
1247 }