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