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     DEFINE_WAIT_BLOCK(WaitBlock);
 476
 477     /* Start main loop */
 478     for (;;)
 479     {
 480         /* Check if it's unlocked */
 481         if (!OldValue.Locked)
 482         {
 483             /* Lock it */
 484             NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 485             ASSERT(NewValue.Locked);
 486
 487             /* Set the new value */
 488             if (InterlockedCompareExchangePointer(&PushLock->Ptr,
 489                                                   NewValue.Ptr,
 490                                                   OldValue.Ptr) != OldValue.Ptr)
 491             {
 492                 /* Retry */
 493                 OldValue = *PushLock;
 494                 continue;
 495             }
 496
 497             /* Break out of the loop */
 498             break;
 499         }
 500         else
 501         {
 502             /* We'll have to create a Waitblock */
 503             WaitBlock->Flags = EX_PUSH_LOCK_FLAGS_EXCLUSIVE |
 504                                EX_PUSH_LOCK_FLAGS_WAIT;
 505             WaitBlock->Previous = NULL;
 506             NeedWake = FALSE;
 507
 508             /* Check if there is already a waiter */
 509             if (OldValue.Waiting)
 510             {
 511                 /* Nobody is the last waiter yet */
 512                 WaitBlock->Last = NULL;
 513
 514                 /* We are an exclusive waiter */
 515                 WaitBlock->ShareCount = 0;
 516
 517                 /* Set the current Wait Block pointer */
 518                 WaitBlock->Next = (PEX_PUSH_LOCK_WAIT_BLOCK)(
 519                                    OldValue.Value &~ EX_PUSH_LOCK_PTR_BITS);
 520
 521                 /* Point to ours */
 522                 NewValue.Value = (OldValue.Value & EX_PUSH_LOCK_MULTIPLE_SHARED) |
 523                                   EX_PUSH_LOCK_LOCK |
 524                                   EX_PUSH_LOCK_WAKING |
 525                                   EX_PUSH_LOCK_WAITING |
 526                                   (ULONG_PTR)WaitBlock;
 527
 528                 /* Check if the pushlock was already waking */
 529                 if (!OldValue.Waking) NeedWake = TRUE;
 530             }
 531             else
 532             {
 533                 /* We are the first waiter, so loop the wait block */
 534                 WaitBlock->Last = WaitBlock;
 535
 536                 /* Set the share count */
 537                 WaitBlock->ShareCount = (LONG)OldValue.Shared;
 538
 539                 /* Check if someone is sharing this pushlock */
 540                 if (OldValue.Shared > 1)
 541                 {
 542                     /* Point to our wait block */
 543                     NewValue.Value = EX_PUSH_LOCK_MULTIPLE_SHARED |
 544                                      EX_PUSH_LOCK_LOCK |
 545                                      EX_PUSH_LOCK_WAITING |
 546                                      (ULONG_PTR)WaitBlock;
 547                 }
 548                 else
 549                 {
 550                     /* No shared count */
 551                     WaitBlock->ShareCount = 0;
 552
 553                     /* Point to our wait block */
 554                     NewValue.Value = EX_PUSH_LOCK_LOCK |
 555                                      EX_PUSH_LOCK_WAITING |
 556                                      (ULONG_PTR)WaitBlock;
 557                 }
 558             }
 559
 560 #if DBG
 561             /* Setup the Debug Wait Block */
 562             WaitBlock->Signaled = 0;
 563             WaitBlock->OldValue = OldValue;
 564             WaitBlock->NewValue = NewValue;
 565             WaitBlock->PushLock = PushLock;
 566 #endif
 567
 568             /* Sanity check */
 569             ASSERT(NewValue.Waiting);
 570             ASSERT(NewValue.Locked);
 571
 572             /* Write the new value */
 573             TempValue = NewValue;
 574             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 575                                                              NewValue.Ptr,
 576                                                              OldValue.Ptr);
 577             if (NewValue.Value != OldValue.Value)
 578             {
 579                 /* Retry */
 580                 OldValue = *PushLock;
 581                 continue;
 582             }
 583
 584             /* Check if the pushlock needed waking */
 585             if (NeedWake)
 586             {
 587                 /* Scan the Waiters and Wake PushLocks */
 588                 ExpOptimizePushLockList(PushLock, TempValue);
 589             }
 590
 591             /* Set up the Wait Gate */
 592             KeInitializeGate(&WaitBlock->WakeGate);
 593
 594 #ifdef CONFIG_SMP
 595             /* Now spin on the push lock if necessary */
 596             if (ExPushLockSpinCount)
 597             {
 598                 ULONG i = ExPushLockSpinCount;
 599
 600                 do
 601                 {
 602                     if (!(*(volatile LONG *)&WaitBlock->Flags & EX_PUSH_LOCK_WAITING))
 603                         break;
 604
 605                     YieldProcessor();
 606                 } while (--i);
 607             }
 608 #endif
 609
 610             /* Now try to remove the wait bit */
 611             if (InterlockedBitTestAndReset(&WaitBlock->Flags, 1))
 612             {
 613                 /* Nobody removed it already, let's do a full wait */
 614                 KeWaitForGate(&WaitBlock->WakeGate, WrPushLock, KernelMode);
 615                 ASSERT(WaitBlock->Signaled);
 616             }
 617
 618             /* We shouldn't be shared anymore */
 619             ASSERT((WaitBlock->ShareCount == 0));
 620
 621             /* Loop again */
 622             OldValue = NewValue;
 623         }
 624     }
 625 }
 626
 627 /*++
 628  * @name ExAcquirePushLockShared
 629  * @implemented NT5.1
 630  *
 631  *     The ExAcquirePushLockShared routine acquires a shared PushLock.
 632  *
 633  * @params PushLock
 634  *         Pointer to the pushlock which is to be acquired.
 635  *
 636  * @return None.
 637  *
 638  * @remarks Callers of ExAcquirePushLockShared must be running at IRQL <= APC_LEVEL.
 639  *          This macro should usually be paired up with KeAcquireCriticalRegion.
 640  *
 641  *--*/
 642 VOID
 643 FASTCALL
 644 ExfAcquirePushLockShared(PEX_PUSH_LOCK PushLock)
 645 {
 646     EX_PUSH_LOCK OldValue = *PushLock, NewValue;
 647     BOOLEAN NeedWake;
 648     DEFINE_WAIT_BLOCK(WaitBlock);
 649
 650     /* Start main loop */
 651     for (;;)
 652     {
 653         /* Check if it's unlocked or if it's waiting without any sharers */
 654         if (!(OldValue.Locked) || (!(OldValue.Waiting) && (OldValue.Shared > 0)))
 655         {
 656             /* Check if anyone is waiting on it */
 657             if (!OldValue.Waiting)
 658             {
 659                 /* Increase the share count and lock it */
 660                 NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 661                 NewValue.Shared++;
 662             }
 663             else
 664             {
 665                 /* Simply set the lock bit */
 666                 NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 667             }
 668
 669             /* Sanity check */
 670             ASSERT(NewValue.Locked);
 671
 672             /* Set the new value */
 673             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 674                                                              NewValue.Ptr,
 675                                                              OldValue.Ptr);
 676             if (NewValue.Value != OldValue.Value)
 677             {
 678                 /* Retry */
 679                 OldValue = *PushLock;
 680                 continue;
 681             }
 682
 683             /* Break out of the loop */
 684             break;
 685         }
 686         else
 687         {
 688             /* We'll have to create a Waitblock */
 689             WaitBlock->Flags = EX_PUSH_LOCK_FLAGS_WAIT;
 690             WaitBlock->ShareCount = 0;
 691             NeedWake = FALSE;
 692             WaitBlock->Previous = NULL;
 693
 694             /* Check if there is already a waiter */
 695             if (OldValue.Waiting)
 696             {
 697                 /* Set the current Wait Block pointer */
 698                 WaitBlock->Next = (PEX_PUSH_LOCK_WAIT_BLOCK)(
 699                                    OldValue.Value &~ EX_PUSH_LOCK_PTR_BITS);
 700
 701                 /* Nobody is the last waiter yet */
 702                 WaitBlock->Last = NULL;
 703
 704                 /* Point to ours */
 705                 NewValue.Value = (OldValue.Value & (EX_PUSH_LOCK_MULTIPLE_SHARED |
 706                                                     EX_PUSH_LOCK_LOCK)) |
 707                                   EX_PUSH_LOCK_WAKING |
 708                                   EX_PUSH_LOCK_WAITING |
 709                                   (ULONG_PTR)WaitBlock;
 710
 711                 /* Check if the pushlock was already waking */
 712                 if (!OldValue.Waking) NeedWake = TRUE;
 713             }
 714             else
 715             {
 716                 /* We are the first waiter, so loop the wait block */
 717                 WaitBlock->Last = WaitBlock;
 718
 719                 /* Point to our wait block */
 720                 NewValue.Value = (OldValue.Value & EX_PUSH_LOCK_PTR_BITS) |
 721                                   EX_PUSH_LOCK_WAITING |
 722                                   (ULONG_PTR)WaitBlock;
 723             }
 724
 725             /* Sanity check */
 726             ASSERT(NewValue.Waiting);
 727
 728 #if DBG
 729             /* Setup the Debug Wait Block */
 730             WaitBlock->Signaled = 0;
 731             WaitBlock->OldValue = OldValue;
 732             WaitBlock->NewValue = NewValue;
 733             WaitBlock->PushLock = PushLock;
 734 #endif
 735
 736             /* Write the new value */
 737             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 738                                                              NewValue.Ptr,
 739                                                              OldValue.Ptr);
 740             if (NewValue.Ptr != OldValue.Ptr)
 741             {
 742                 /* Retry */
 743                 OldValue = *PushLock;
 744                 continue;
 745             }
 746
 747             /* Update the value now */
 748             OldValue = NewValue;
 749
 750             /* Check if the pushlock needed waking */
 751             if (NeedWake)
 752             {
 753                 /* Scan the Waiters and Wake PushLocks */
 754                 ExpOptimizePushLockList(PushLock, OldValue);
 755             }
 756
 757             /* Set up the Wait Gate */
 758             KeInitializeGate(&WaitBlock->WakeGate);
 759
 760 #ifdef CONFIG_SMP
 761             /* Now spin on the push lock if necessary */
 762             if (ExPushLockSpinCount)
 763             {
 764                 ULONG i = ExPushLockSpinCount;
 765
 766                 do
 767                 {
 768                     if (!(*(volatile LONG *)&WaitBlock->Flags & EX_PUSH_LOCK_WAITING))
 769                         break;
 770
 771                     YieldProcessor();
 772                 } while (--i);
 773             }
 774 #endif
 775
 776             /* Now try to remove the wait bit */
 777             if (InterlockedBitTestAndReset(&WaitBlock->Flags, 1))
 778             {
 779                 /* Fast-path did not work, we need to do a full wait */
 780                 KeWaitForGate(&WaitBlock->WakeGate, WrPushLock, KernelMode);
 781                 ASSERT(WaitBlock->Signaled);
 782             }
 783
 784             /* We shouldn't be shared anymore */
 785             ASSERT((WaitBlock->ShareCount == 0));
 786         }
 787     }
 788 }
 789
 790 /*++
 791  * @name ExfReleasePushLock
 792  * @implemented NT5.1
 793  *
 794  *     The ExReleasePushLock routine releases a previously acquired PushLock.
 795  *
 796  *
 797  * @params PushLock
 798  *         Pointer to a previously acquired pushlock.
 799  *
 800  * @return None.
 801  *
 802  * @remarks Callers of ExfReleasePushLock must be running at IRQL <= APC_LEVEL.
 803  *          This macro should usually be paired up with KeLeaveCriticalRegion.
 804  *
 805  *--*/
 806 VOID
 807 FASTCALL
 808 ExfReleasePushLock(PEX_PUSH_LOCK PushLock)
 809 {
 810     EX_PUSH_LOCK OldValue = *PushLock, NewValue, WakeValue;
 811     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock;
 812
 813     /* Sanity check */
 814     ASSERT(OldValue.Locked);
 815
 816     /* Start main loop */
 817     while (TRUE)
 818     {
 819         /* Check if someone is waiting on the lock */
 820         if (!OldValue.Waiting)
 821         {
 822             /* Check if it's shared */
 823             if (OldValue.Shared > 1)
 824             {
 825                 /* Write the Old Value but decrease share count */
 826                 NewValue = OldValue;
 827                 NewValue.Shared--;
 828             }
 829             else
 830             {
 831                 /* Simply clear the lock */
 832                 NewValue.Value = 0;
 833             }
 834
 835             /* Write the New Value */
 836             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 837                                                              NewValue.Ptr,
 838                                                              OldValue.Ptr);
 839             if (NewValue.Value == OldValue.Value) return;
 840
 841             /* Did it enter a wait state? */
 842             OldValue = NewValue;
 843         }
 844         else
 845         {
 846             /* Ok, we do know someone is waiting on it. Are there more then one? */
 847             if (OldValue.MultipleShared)
 848             {
 849                 /* Get the wait block */
 850                 WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)(OldValue.Value &
 851                                                        ~EX_PUSH_LOCK_PTR_BITS);
 852
 853                 /* Loop until we find the last wait block */
 854                 while (TRUE)
 855                 {
 856                     /* Get the last wait block */
 857                     LastWaitBlock = WaitBlock->Last;
 858
 859                     /* Did it exist? */
 860                     if (LastWaitBlock)
 861                     {
 862                         /* Choose it */
 863                         WaitBlock = LastWaitBlock;
 864                         break;
 865                     }
 866
 867                     /* Keep searching */
 868                     WaitBlock = WaitBlock->Next;
 869                 }
 870
 871                 /* Make sure the Share Count is above 0 */
 872                 if (WaitBlock->ShareCount > 0)
 873                 {
 874                     /* This shouldn't be an exclusive wait block */
 875                     ASSERT(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE);
 876
 877                     /* Do the decrease and check if the lock isn't shared anymore */
 878                     if (InterlockedDecrement(&WaitBlock->ShareCount) > 0) return;
 879                 }
 880             }
 881
 882             /*
 883              * If nobody was waiting on the block, then we possibly reduced the number
 884              * of times the pushlock was shared, and we unlocked it.
 885              * If someone was waiting, and more then one person is waiting, then we
 886              * reduced the number of times the pushlock is shared in the wait block.
 887              * Therefore, at this point, we can now 'satisfy' the wait.
 888              */
 889             for (;;)
 890             {
 891                 /* Now we need to see if it's waking */
 892                 if (OldValue.Waking)
 893                 {
 894                     /* Remove the lock and multiple shared bits */
 895                     NewValue.Value = OldValue.Value;
 896                     NewValue.MultipleShared = FALSE;
 897                     NewValue.Locked = FALSE;
 898
 899                     /* Sanity check */
 900                     ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
 901
 902                     /* Write the new value */
 903                     NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 904                                                                      NewValue.Ptr,
 905                                                                      OldValue.Ptr);
 906                     if (NewValue.Value == OldValue.Value) return;
 907                 }
 908                 else
 909                 {
 910                     /* Remove the lock and multiple shared bits */
 911                     NewValue.Value = OldValue.Value;
 912                     NewValue.MultipleShared = FALSE;
 913                     NewValue.Locked = FALSE;
 914
 915                     /* It's not already waking, so add the wake bit */
 916                     NewValue.Waking = TRUE;
 917
 918                     /* Sanity check */
 919                     ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
 920
 921                     /* Write the new value */
 922                     WakeValue = NewValue;
 923                     NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 924                                                                      NewValue.Ptr,
 925                                                                      OldValue.Ptr);
 926                     if (NewValue.Value != OldValue.Value) continue;
 927
 928                     /* The write was successful. The pushlock is Unlocked and Waking */
 929                     ExfWakePushLock(PushLock, WakeValue);
 930                     return;
 931                 }
 932             }
 933         }
 934     }
 935 }
 936
 937 /*++
 938  * @name ExfReleasePushLockShared
 939  * @implemented NT5.2
 940  *
 941  *     The ExfReleasePushLockShared macro releases a previously acquired PushLock.
 942  *
 943  * @params PushLock
 944  *         Pointer to a previously acquired pushlock.
 945  *
 946  * @return None.
 947  *
 948  * @remarks Callers of ExReleasePushLockShared must be running at IRQL <= APC_LEVEL.
 949  *          This macro should usually be paired up with KeLeaveCriticalRegion.
 950  *
 951  *--*/
 952 VOID
 953 FASTCALL
 954 ExfReleasePushLockShared(PEX_PUSH_LOCK PushLock)
 955 {
 956     EX_PUSH_LOCK OldValue = *PushLock, NewValue, WakeValue;
 957     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock;
 958
 959     /* Check if someone is waiting on the lock */
 960     while (!OldValue.Waiting)
 961     {
 962         /* Check if it's shared */
 963         if (OldValue.Shared > 1)
 964         {
 965             /* Write the Old Value but decrease share count */
 966             NewValue = OldValue;
 967             NewValue.Shared--;
 968         }
 969         else
 970         {
 971             /* Simply clear the lock */
 972             NewValue.Value = 0;
 973         }
 974
 975         /* Write the New Value */
 976         NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
 977                                                          NewValue.Ptr,
 978                                                          OldValue.Ptr);
 979         if (NewValue.Value == OldValue.Value) return;
 980
 981         /* Did it enter a wait state? */
 982         OldValue = NewValue;
 983     }
 984
 985     /* Ok, we do know someone is waiting on it. Are there more then one? */
 986     if (OldValue.MultipleShared)
 987     {
 988         /* Get the wait block */
 989         WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)(OldValue.Value &
 990                                                ~EX_PUSH_LOCK_PTR_BITS);
 991
 992         /* Loop until we find the last wait block */
 993         while (TRUE)
 994         {
 995             /* Get the last wait block */
 996             LastWaitBlock = WaitBlock->Last;
 997
 998             /* Did it exist? */
 999             if (LastWaitBlock)
1000             {
1001                 /* Choose it */
1002                 WaitBlock = LastWaitBlock;
1003                 break;
1004             }
1005
1006             /* Keep searching */
1007             WaitBlock = WaitBlock->Next;
1008         }
1009
1010         /* Sanity checks */
1011         ASSERT(WaitBlock->ShareCount > 0);
1012         ASSERT(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE);
1013
1014         /* Do the decrease and check if the lock isn't shared anymore */
1015         if (InterlockedDecrement(&WaitBlock->ShareCount) > 0) return;
1016     }
1017
1018     /*
1019      * If nobody was waiting on the block, then we possibly reduced the number
1020      * of times the pushlock was shared, and we unlocked it.
1021      * If someone was waiting, and more then one person is waiting, then we
1022      * reduced the number of times the pushlock is shared in the wait block.
1023      * Therefore, at this point, we can now 'satisfy' the wait.
1024      */
1025     for (;;)
1026     {
1027         /* Now we need to see if it's waking */
1028         if (OldValue.Waking)
1029         {
1030             /* Remove the lock and multiple shared bits */
1031             NewValue.Value = OldValue.Value;
1032             NewValue.MultipleShared = FALSE;
1033             NewValue.Locked = FALSE;
1034
1035             /* Sanity check */
1036             ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
1037
1038             /* Write the new value */
1039             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
1040                                                              NewValue.Ptr,
1041                                                              OldValue.Ptr);
1042             if (NewValue.Value == OldValue.Value) return;
1043         }
1044         else
1045         {
1046             /* Remove the lock and multiple shared bits */
1047             NewValue.Value = OldValue.Value;
1048             NewValue.MultipleShared = FALSE;
1049             NewValue.Locked = FALSE;
1050
1051             /* It's not already waking, so add the wake bit */
1052             NewValue.Waking = TRUE;
1053
1054             /* Sanity check */
1055             ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
1056
1057             /* Write the new value */
1058             WakeValue = NewValue;
1059             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
1060                                                              NewValue.Ptr,
1061                                                              OldValue.Ptr);
1062             if (NewValue.Value != OldValue.Value) continue;
1063
1064             /* The write was successful. The pushlock is Unlocked and Waking */
1065             ExfWakePushLock(PushLock, WakeValue);
1066             return;
1067         }
1068     }
1069 }
1070
1071 /*++
1072  * ExfReleasePushLockExclusive
1073  * @implemented NT5.2
1074  *
1075  *     The ExfReleasePushLockExclusive routine releases a previously
1076  *     exclusively acquired PushLock.
1077  *
1078  * @params PushLock
1079  *         Pointer to a previously acquired pushlock.
1080  *
1081  * @return None.
1082  *
1083  * @remarks Callers of ExReleasePushLockExclusive must be running at IRQL <= APC_LEVEL.
1084  *          This macro should usually be paired up with KeLeaveCriticalRegion.
1085  *
1086  *--*/
1087 VOID
1088 FASTCALL
1089 ExfReleasePushLockExclusive(PEX_PUSH_LOCK PushLock)
1090 {
1091     EX_PUSH_LOCK NewValue, WakeValue;
1092     EX_PUSH_LOCK OldValue = *PushLock;
1093
1094     /* Loop until we can change */
1095     for (;;)
1096     {
1097         /* Sanity checks */
1098         ASSERT(OldValue.Locked);
1099         ASSERT(OldValue.Waiting || OldValue.Shared == 0);
1100
1101         /* Check if it's waiting and not yet waking */
1102         if ((OldValue.Waiting) && !(OldValue.Waking))
1103         {
1104             /* Remove the lock bit, and add the wake bit */
1105             NewValue.Value = (OldValue.Value &~ EX_PUSH_LOCK_LOCK) |
1106                               EX_PUSH_LOCK_WAKING;
1107
1108             /* Sanity check */
1109             ASSERT(NewValue.Waking && !NewValue.Locked);
1110
1111             /* Write the New Value. Save our original value for waking */
1112             WakeValue = NewValue;
1113             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
1114                                                              NewValue.Ptr,
1115                                                              OldValue.Ptr);
1116
1117             /* Check if the value changed behind our back */
1118             if (NewValue.Value == OldValue.Value)
1119             {
1120                 /* Wake the Pushlock */
1121                 ExfWakePushLock(PushLock, WakeValue);
1122                 break;
1123             }
1124         }
1125         else
1126         {
1127             /* A simple unlock */
1128             NewValue.Value = OldValue.Value &~ EX_PUSH_LOCK_LOCK;
1129
1130             /* Sanity check */
1131             ASSERT(NewValue.Waking && !NewValue.Waiting);
1132
1133             /* Write the New Value */
1134             NewValue.Ptr = InterlockedCompareExchangePointer(&PushLock->Ptr,
1135                                                              NewValue.Ptr,
1136                                                              OldValue.Ptr);
1137
1138             /* Check if the value changed behind our back */
1139             if (NewValue.Value == OldValue.Value) break;
1140         }
1141
1142         /* Loop again */
1143         OldValue = NewValue;
1144     }
1145 }
1146
1147 /*++
1148  * @name ExfTryToWakePushLock
1149  * @implemented NT5.2
1150  *
1151  *     The ExfTryToWakePushLock attemps to wake a waiting pushlock.
1152  *
1153  * @param PushLock
1154  *        Pointer to a PushLock which is in the wait state.
1155  *
1156  * @return None.
1157  *
1158  * @remarks The pushlock must be in a wait state and must not be already waking.
1159  *
1160  *--*/
1161 VOID
1162 FASTCALL
1163 ExfTryToWakePushLock(PEX_PUSH_LOCK PushLock)
1164 {
1165     EX_PUSH_LOCK OldValue = *PushLock, NewValue;
1166
1167     /*
1168      * If the Pushlock is not waiting on anything, or if it's already waking up
1169      * and locked, don't do anything
1170      */
1171     if ((OldValue.Waking) || (OldValue.Locked) || !(OldValue.Waiting)) return;
1172
1173     /* Make it Waking */
1174     NewValue = OldValue;
1175     NewValue.Waking = TRUE;
1176
1177     /* Write the New Value */
1178     if (InterlockedCompareExchangePointer(&PushLock->Ptr,
1179                                           NewValue.Ptr,
1180                                           OldValue.Ptr) == OldValue.Ptr)
1181     {
1182         /* Wake the Pushlock */
1183         ExfWakePushLock(PushLock, NewValue);
1184     }
1185 }
1186
1187 /*++
1188  * @name ExfUnblockPushLock
1189  * @implemented NT5.1
1190  *
1191  *     The ExfUnblockPushLock routine unblocks a previously blocked PushLock.
1192  *
1193  * @param PushLock
1194  *        Pointer to a previously blocked PushLock.
1195  *
1196  * @return None.
1197  *
1198  * @remarks Callers of ExfUnblockPushLock can be running at any IRQL.
1199  *
1200  *--*/
1201 VOID
1202 FASTCALL
1203 ExfUnblockPushLock(PEX_PUSH_LOCK PushLock,
1204                    PVOID CurrentWaitBlock)
1205 {
1206     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, NextWaitBlock;
1207     KIRQL OldIrql = DISPATCH_LEVEL;
1208
1209     /* Get the wait block and erase the previous one */
1210     WaitBlock = InterlockedExchangePointer(&PushLock->Ptr, NULL);
1211     if (WaitBlock)
1212     {
1213         /* Check if there is a linked pushlock and raise IRQL appropriately */
1214         if (WaitBlock->Next) KeRaiseIrql(DISPATCH_LEVEL, &OldIrql);
1215
1216         /* Start block loop */
1217         while (WaitBlock)
1218         {
1219             /* Get the next block */
1220             NextWaitBlock = WaitBlock->Next;
1221
1222             /* Remove the wait flag from the Wait block */
1223             if (!InterlockedBitTestAndReset(&WaitBlock->Flags, EX_PUSH_LOCK_FLAGS_WAIT_V))
1224             {
1225                 /* Nobody removed the flag before us, so signal the event */
1226                 KeSetEventBoostPriority(&WaitBlock->WakeEvent, NULL);
1227             }
1228
1229             /* Try the next one */
1230             WaitBlock = NextWaitBlock;
1231         }
1232
1233         /* Lower IRQL if needed */
1234         if (OldIrql != DISPATCH_LEVEL) KeLowerIrql(OldIrql);
1235     }
1236
1237     /* Check if we got a wait block that's pending */
1238     if ((CurrentWaitBlock) &&
1239         (((PEX_PUSH_LOCK_WAIT_BLOCK)CurrentWaitBlock)->Flags &
1240            EX_PUSH_LOCK_FLAGS_WAIT))
1241     {
1242         /* Wait for the pushlock to be unblocked */
1243         ExWaitForUnblockPushLock(PushLock, CurrentWaitBlock);
1244     }
1245 }