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 ExBlockPushLock
 346  *
 347  *     The ExBlockPushLock routine blocks a pushlock.
 348  *
 349  * @param PushLock
 350  *        Pointer to a pushlock whose waiter list needs to be optimized.
 351  *
 352  * @param WaitBlock
 353  *        Pointer to the pushlock's wait block.
 354  *
 355  * @return None.
 356  *
 357  * @remarks None.
 358  *
 359  *--*/
 360 VOID
 361 FASTCALL
 362 ExBlockPushLock(PEX_PUSH_LOCK PushLock,
 363                 PVOID WaitBlock)
 364 {
 365     PVOID NewValue, OldValue;
 366
 367     /* Set the waiting bit */
 368     ((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)->Flags |= EX_PUSH_LOCK_FLAGS_WAIT;
 369
 370     /* Link the wait blocks */
 371     ((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)->Next = PushLock->Ptr;
 372
 373     /* Try to set this one as the wait block now */
 374     NewValue = PushLock->Ptr;
 375     for (;;)
 376     {
 377         /* Set the new wait block value */
 378         OldValue = InterlockedCompareExchangePointer(&PushLock->Ptr,
 379                                                      WaitBlock,
 380                                                      NewValue);
 381         if (OldValue == NewValue) break;
 382         NewValue = OldValue;
 383     }
 384 }
 385
 386 /* PUBLIC FUNCTIONS **********************************************************/
 387
 388 /*++
 389  * @name ExAcquirePushLockExclusive
 390  * @implemented NT5.1
 391  *
 392  *     The ExAcquirePushLockExclusive macro exclusively acquires a PushLock.
 393  *
 394  * @params PushLock
 395  *         Pointer to the pushlock which is to be acquired.
 396  *
 397  * @return None.
 398  *
 399  * @remarks Callers of ExAcquirePushLockShared must be running at IRQL <= APC_LEVEL.
 400  *          This macro should usually be paired up with KeAcquireCriticalRegion.
 401  *
 402  *--*/
 403 VOID
 404 FASTCALL
 405 ExfAcquirePushLockExclusive(PEX_PUSH_LOCK PushLock)
 406 {
 407     EX_PUSH_LOCK_WAIT_BLOCK WaitBlock;
 408     EX_PUSH_LOCK OldValue = *PushLock, NewValue, TempValue;
 409     BOOLEAN NeedWake;
 410     ULONG i;
 411
 412     /* Start main loop */
 413     for (;;)
 414     {
 415         /* Check if it's unlocked */
 416         if (!OldValue.Locked)
 417         {
 418             /* Lock it */
 419             NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 420             ASSERT(NewValue.Locked);
 421
 422             /* Set the new value */
 423             if (InterlockedCompareExchangePointer(PushLock,
 424                                                   NewValue.Ptr,
 425                                                   OldValue.Ptr) != OldValue.Ptr)
 426             {
 427                 /* Retry */
 428                 OldValue = *PushLock;
 429                 continue;
 430             }
 431
 432             /* Break out of the loop */
 433             break;
 434         }
 435         else
 436         {
 437             /* We'll have to create a Waitblock */
 438             WaitBlock.Flags = EX_PUSH_LOCK_FLAGS_EXCLUSIVE |
 439                               EX_PUSH_LOCK_FLAGS_WAIT;
 440             WaitBlock.Previous = NULL;
 441             NeedWake = FALSE;
 442
 443             /* Check if there is already a waiter */
 444             if (OldValue.Waiting)
 445             {
 446                 /* Nobody is the last waiter yet */
 447                 WaitBlock.Last = NULL;
 448
 449                 /* We are an exclusive waiter */
 450                 WaitBlock.ShareCount = 0;
 451
 452                 /* Set the current Wait Block pointer */
 453                 WaitBlock.Next = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)
 454                                   OldValue.Ptr &~ EX_PUSH_LOCK_PTR_BITS);
 455
 456                 /* Point to ours */
 457                 NewValue.Value = (OldValue.Value & EX_PUSH_LOCK_MULTIPLE_SHARED) |
 458                                  EX_PUSH_LOCK_LOCK |
 459                                  EX_PUSH_LOCK_WAKING |
 460                                  EX_PUSH_LOCK_WAITING |
 461                                  PtrToUlong(&WaitBlock);
 462
 463                 /* Check if the pushlock was already waking */
 464                 if (OldValue.Waking) NeedWake = TRUE;
 465             }
 466             else
 467             {
 468                 /* We are the first waiter, so loop the wait block */
 469                 WaitBlock.Last = &WaitBlock;
 470
 471                 /* Set the share count */
 472                 WaitBlock.ShareCount = OldValue.Shared;
 473
 474                 /* Check if someone is sharing this pushlock */
 475                 if (OldValue.Shared > 1)
 476                 {
 477                     /* Point to our wait block */
 478                     NewValue.Value = EX_PUSH_LOCK_MULTIPLE_SHARED |
 479                                      EX_PUSH_LOCK_LOCK |
 480                                      EX_PUSH_LOCK_WAITING |
 481                                      PtrToUlong(&WaitBlock);
 482                 }
 483                 else
 484                 {
 485                     /* No shared count */
 486                     WaitBlock.ShareCount = 0;
 487
 488                     /* Point to our wait block */
 489                     NewValue.Value = EX_PUSH_LOCK_LOCK |
 490                                      EX_PUSH_LOCK_WAITING |
 491                                      PtrToUlong(&WaitBlock);
 492                 }
 493             }
 494
 495 #if DBG
 496             /* Setup the Debug Wait Block */
 497             WaitBlock.Signaled = 0;
 498             WaitBlock.OldValue = OldValue;
 499             WaitBlock.NewValue = NewValue;
 500             WaitBlock.PushLock = PushLock;
 501 #endif
 502
 503             /* Sanity check */
 504             ASSERT(NewValue.Waiting);
 505             ASSERT(NewValue.Locked);
 506
 507             /* Write the new value */
 508             TempValue = NewValue;
 509             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
 510                                                              NewValue.Ptr,
 511                                                              OldValue.Ptr);
 512             if (NewValue.Value != OldValue.Value)
 513             {
 514                 /* Retry */
 515                 OldValue = *PushLock;
 516                 continue;
 517             }
 518
 519             /* Check if the pushlock needed waking */
 520             if (NeedWake)
 521             {
 522                 /* Scan the Waiters and Wake PushLocks */
 523                 ExpOptimizePushLockList(PushLock, TempValue);
 524             }
 525
 526             /* Set up the Wait Gate */
 527             KeInitializeGate(&WaitBlock.WakeGate);
 528
 529             /* Now spin on the push lock if necessary */
 530             i = ExPushLockSpinCount;
 531             if ((i) && (WaitBlock.Flags & EX_PUSH_LOCK_WAITING))
 532             {
 533                 /* Spin */
 534                 while (--i) YieldProcessor();
 535             }
 536
 537             /* Now try to remove the wait bit */
 538             if (InterlockedBitTestAndReset(&WaitBlock.Flags, 1))
 539             {
 540                 /* Nobody removed it already, let's do a full wait */
 541                 KeWaitForGate(&WaitBlock.WakeGate, WrPushLock, KernelMode);
 542                 ASSERT(WaitBlock.Signaled);
 543             }
 544
 545             /* We shouldn't be shared anymore */
 546             ASSERT((WaitBlock.ShareCount == 0));
 547
 548             /* Loop again */
 549             OldValue = NewValue;
 550         }
 551     }
 552 }
 553
 554 /*++
 555  * @name ExAcquirePushLockExclusive
 556  * @implemented NT5.1
 557  *
 558  *     The ExAcquirePushLockShared macro acquires a shared PushLock.
 559  *
 560  * @params PushLock
 561  *         Pointer to the pushlock which is to be acquired.
 562  *
 563  * @return None.
 564  *
 565  * @remarks Callers of ExAcquirePushLockShared must be running at IRQL <= APC_LEVEL.
 566  *          This macro should usually be paired up with KeAcquireCriticalRegion.
 567  *
 568  *--*/
 569 VOID
 570 FASTCALL
 571 ExfAcquirePushLockShared(PEX_PUSH_LOCK PushLock)
 572 {
 573     EX_PUSH_LOCK_WAIT_BLOCK WaitBlock;
 574     EX_PUSH_LOCK OldValue = *PushLock, NewValue;
 575     BOOLEAN NeedWake;
 576     ULONG i;
 577
 578     /* Start main loop */
 579     for (;;)
 580     {
 581         /* Check if it's unlocked or if it's waiting without any sharers */
 582         if (!(OldValue.Locked) || (OldValue.Waiting && OldValue.Shared == 0))
 583         {
 584             /* Check if anyone is waiting on it */
 585             if (!OldValue.Waiting)
 586             {
 587                 /* Increase the share count and lock it */
 588                 NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 589                 NewValue.Shared++;
 590             }
 591             else
 592             {
 593                 /* Simply set the lock bit */
 594                 NewValue.Value = OldValue.Value | EX_PUSH_LOCK_LOCK;
 595             }
 596
 597             /* Sanity check */
 598             ASSERT(NewValue.Locked);
 599
 600             /* Set the new value */
 601             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
 602                                                              NewValue.Ptr,
 603                                                              OldValue.Ptr);
 604             if (NewValue.Value != OldValue.Value)
 605             {
 606                 /* Retry */
 607                 OldValue = NewValue;
 608                 continue;
 609             }
 610
 611             /* Break out of the loop */
 612             break;
 613         }
 614         else
 615         {
 616             /* We'll have to create a Waitblock */
 617             WaitBlock.Flags = EX_PUSH_LOCK_FLAGS_WAIT;
 618             WaitBlock.ShareCount = 0;
 619             NeedWake = FALSE;
 620             WaitBlock.Previous = NULL;
 621
 622             /* Check if there is already a waiter */
 623             if (OldValue.Waiting)
 624             {
 625                 /* Set the current Wait Block pointer */
 626                 WaitBlock.Next = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)
 627                                  OldValue.Ptr &~ EX_PUSH_LOCK_PTR_BITS);
 628
 629                 /* Nobody is the last waiter yet */
 630                 WaitBlock.Last = NULL;
 631
 632                 /* Point to ours */
 633                 NewValue.Value = (OldValue.Value & (EX_PUSH_LOCK_MULTIPLE_SHARED |
 634                                                     EX_PUSH_LOCK_LOCK)) |
 635                                   EX_PUSH_LOCK_WAKING |
 636                                   EX_PUSH_LOCK_WAITING |
 637                                   PtrToUlong(&WaitBlock);
 638
 639                 /* Check if the pushlock was already waking */
 640                 if (OldValue.Waking) NeedWake = TRUE;
 641             }
 642             else
 643             {
 644                 /* We are the first waiter, so loop the wait block */
 645                 WaitBlock.Last = &WaitBlock;
 646
 647                 /* Point to our wait block */
 648                 NewValue.Value = (OldValue.Value & (EX_PUSH_LOCK_MULTIPLE_SHARED |
 649                                                     EX_PUSH_LOCK_WAKING)) |
 650                                   EX_PUSH_LOCK_WAITING |
 651                                   PtrToUlong(&WaitBlock);
 652             }
 653
 654             /* Sanity check */
 655             ASSERT(NewValue.Waiting);
 656
 657 #if DBG
 658             /* Setup the Debug Wait Block */
 659             WaitBlock.Signaled = 0;
 660             WaitBlock.OldValue = OldValue;
 661             WaitBlock.NewValue = NewValue;
 662             WaitBlock.PushLock = PushLock;
 663 #endif
 664
 665             /* Write the new value */
 666             if (InterlockedCompareExchangePointer(PushLock,
 667                                                   NewValue.Ptr,
 668                                                   OldValue.Ptr) != OldValue.Ptr)
 669             {
 670                 /* Retry */
 671                 OldValue = NewValue;
 672                 continue;
 673             }
 674
 675             /* Update the value now */
 676             OldValue = NewValue;
 677
 678             /* Check if the pushlock needed waking */
 679             if (NeedWake)
 680             {
 681                 /* Scan the Waiters and Wake PushLocks */
 682                 ExpOptimizePushLockList(PushLock, OldValue);
 683             }
 684
 685             /* Set up the Wait Gate */
 686             KeInitializeGate(&WaitBlock.WakeGate);
 687
 688             /* Now spin on the push lock if necessary */
 689             i = ExPushLockSpinCount;
 690             if ((i) && (WaitBlock.Flags & EX_PUSH_LOCK_WAITING))
 691             {
 692                 /* Spin */
 693                 while (--i) YieldProcessor();
 694             }
 695
 696             /* Now try to remove the wait bit */
 697             if (InterlockedBitTestAndReset(&WaitBlock.Flags, 1))
 698             {
 699                 /* Fast-path did not work, we need to do a full wait */
 700                 KeWaitForGate(&WaitBlock.WakeGate, WrPushLock, KernelMode);
 701                 ASSERT(WaitBlock.Signaled);
 702             }
 703
 704             /* We shouldn't be shared anymore */
 705             ASSERT((WaitBlock.ShareCount == 0));
 706         }
 707     }
 708 }
 709
 710 /*++
 711  * @name ExfReleasePushLock
 712  * @implemented NT5.1
 713  *
 714  *     The ExReleasePushLockExclusive routine releases a previously
 715  *     exclusively acquired PushLock.
 716  *
 717  * @params PushLock
 718  *         Pointer to a previously acquired pushlock.
 719  *
 720  * @return None.
 721  *
 722  * @remarks Callers of ExReleasePushLockExclusive must be running at IRQL <= APC_LEVEL.
 723  *          This macro should usually be paired up with KeLeaveCriticalRegion.
 724  *
 725  *--*/
 726 VOID
 727 FASTCALL
 728 ExfReleasePushLock(PEX_PUSH_LOCK PushLock)
 729 {
 730     EX_PUSH_LOCK OldValue = *PushLock;
 731     EX_PUSH_LOCK NewValue;
 732     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock;
 733
 734     /* Sanity check */
 735     ASSERT(OldValue.Locked);
 736
 737     /* Check if someone is waiting on the lock */
 738     if (!OldValue.Waiting)
 739     {
 740         /* Nobody is waiting on it, so we'll try a quick release */
 741         for (;;)
 742         {
 743             /* Check if it's shared */
 744             if (OldValue.Shared > 1)
 745             {
 746                 /* Write the Old Value but decrease share count */
 747                 NewValue = OldValue;
 748                 NewValue.Shared--;
 749             }
 750             else
 751             {
 752                 /* Simply clear the lock */
 753                 NewValue.Value = 0;
 754             }
 755
 756             /* Write the New Value */
 757             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
 758                                                              NewValue.Ptr,
 759                                                              OldValue.Ptr);
 760             if (NewValue.Value == OldValue.Value)
 761             {
 762                 /* No waiters left, we're done */
 763                 goto quit;
 764             }
 765
 766             /* Did it enter a wait state? */
 767             OldValue = NewValue;
 768             if (NewValue.Waiting) break;
 769         }
 770     }
 771
 772     /* Ok, we do know someone is waiting on it. Are there more then one? */
 773     if (OldValue.MultipleShared)
 774     {
 775         /* Find the last Wait Block */
 776         for (WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr &
 777                                                     ~EX_PUSH_LOCK_PTR_BITS);
 778              WaitBlock->Last;
 779              WaitBlock = WaitBlock->Next);
 780
 781         /* Make sure the Share Count is above 0 */
 782         if (WaitBlock->ShareCount)
 783         {
 784             /* This shouldn't be an exclusive wait block */
 785             ASSERT(WaitBlock->Flags&EX_PUSH_LOCK_FLAGS_EXCLUSIVE);
 786
 787             /* Do the decrease and check if the lock isn't shared anymore */
 788             if (InterlockedExchangeAdd(&WaitBlock->ShareCount, -1))
 789             {
 790                 /* Someone is still holding the lock */
 791                 goto quit;
 792             }
 793         }
 794     }
 795
 796     /*
 797      * If nobody was waiting on the block, then we possibly reduced the number
 798      * of times the pushlock was shared, and we unlocked it.
 799      * If someone was waiting, and more then one person is waiting, then we
 800      * reduced the number of times the pushlock is shared in the wait block.
 801      * Therefore, at this point, we can now 'satisfy' the wait.
 802      */
 803     for (;;)
 804     {
 805         /* Now we need to see if it's waking */
 806         if (OldValue.Waking)
 807         {
 808             /* Remove the lock and multiple shared bits */
 809             NewValue.Value = OldValue.Value;
 810             NewValue.MultipleShared = FALSE;
 811             NewValue.Locked = FALSE;
 812
 813             /* Sanity check */
 814             ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
 815
 816             /* Write the new value */
 817             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
 818                                                              NewValue.Ptr,
 819                                                              OldValue.Ptr);
 820             if (NewValue.Value == OldValue.Value) break;
 821
 822             /* The value changed, try the unlock again */
 823             continue;
 824         }
 825         else
 826         {
 827             /* Remove the lock and multiple shared bits */
 828             NewValue.Value = OldValue.Value;
 829             NewValue.MultipleShared = FALSE;
 830             NewValue.Locked = FALSE;
 831
 832             /* It's not already waking, so add the wake bit */
 833             NewValue.Waking = TRUE;
 834
 835             /* Sanity check */
 836             ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
 837
 838             /* Write the new value */
 839             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
 840                                                              NewValue.Ptr,
 841                                                              OldValue.Ptr);
 842             if (NewValue.Value != OldValue.Value) continue;
 843
 844             /* The write was successful. The pushlock is Unlocked and Waking */
 845             ExfWakePushLock(PushLock, NewValue);
 846             break;
 847         }
 848     }
 849 quit:
 850     /* Done! */
 851     return;
 852 }
 853
 854 /*++
 855  * @name ExfReleasePushLockShared
 856  * @implemented NT5.2
 857  *
 858  *     The ExfReleasePushLockShared macro releases a previously acquired PushLock.
 859  *
 860  * @params PushLock
 861  *         Pointer to a previously acquired pushlock.
 862  *
 863  * @return None.
 864  *
 865  * @remarks Callers of ExReleasePushLockShared must be running at IRQL <= APC_LEVEL.
 866  *          This macro should usually be paired up with KeLeaveCriticalRegion.
 867  *
 868  *--*/
 869 VOID
 870 FASTCALL
 871 ExfReleasePushLockShared(PEX_PUSH_LOCK PushLock)
 872 {
 873     EX_PUSH_LOCK OldValue = *PushLock;
 874     EX_PUSH_LOCK NewValue;
 875     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock;
 876
 877     /* Check if someone is waiting on the lock */
 878     if (!OldValue.Waiting)
 879     {
 880         /* Nobody is waiting on it, so we'll try a quick release */
 881         for (;;)
 882         {
 883             /* Check if it's shared */
 884             if (OldValue.Shared > 1)
 885             {
 886                 /* Write the Old Value but decrease share count */
 887                 NewValue = OldValue;
 888                 NewValue.Shared--;
 889             }
 890             else
 891             {
 892                 /* Simply clear the lock */
 893                 NewValue.Value = 0;
 894             }
 895
 896             /* Write the New Value */
 897             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
 898                                                              NewValue.Ptr,
 899                                                              OldValue.Ptr);
 900             if (NewValue.Value == OldValue.Value)
 901             {
 902                 /* No waiters left, we're done */
 903                 goto quit;
 904             }
 905
 906             /* Did it enter a wait state? */
 907             OldValue = NewValue;
 908             if (NewValue.Waiting) break;
 909         }
 910     }
 911
 912     /* Ok, we do know someone is waiting on it. Are there more then one? */
 913     if (OldValue.MultipleShared)
 914     {
 915         /* Find the last Wait Block */
 916         for (WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr &
 917                                                     ~EX_PUSH_LOCK_PTR_BITS);
 918              WaitBlock->Last;
 919              WaitBlock = WaitBlock->Next);
 920
 921         /* Sanity checks */
 922         ASSERT(WaitBlock->ShareCount > 0);
 923         ASSERT(WaitBlock->Flags&EX_PUSH_LOCK_FLAGS_EXCLUSIVE);
 924
 925         /* Do the decrease and check if the lock isn't shared anymore */
 926         if (InterlockedExchangeAdd(&WaitBlock->ShareCount, -1)) goto quit;
 927     }
 928
 929     /*
 930      * If nobody was waiting on the block, then we possibly reduced the number
 931      * of times the pushlock was shared, and we unlocked it.
 932      * If someone was waiting, and more then one person is waiting, then we
 933      * reduced the number of times the pushlock is shared in the wait block.
 934      * Therefore, at this point, we can now 'satisfy' the wait.
 935      */
 936     for (;;)
 937     {
 938         /* Now we need to see if it's waking */
 939         if (OldValue.Waking)
 940         {
 941             /* Remove the lock and multiple shared bits */
 942             NewValue.Value = OldValue.Value;
 943             NewValue.MultipleShared = FALSE;
 944             NewValue.Locked = FALSE;
 945
 946             /* Sanity check */
 947             ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
 948
 949             /* Write the new value */
 950             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
 951                                                              NewValue.Ptr,
 952                                                              OldValue.Ptr);
 953             if (NewValue.Value == OldValue.Value) break;
 954
 955             /* The value changed, try the unlock again */
 956             continue;
 957         }
 958         else
 959         {
 960             /* Remove the lock and multiple shared bits */
 961             NewValue.Value = OldValue.Value;
 962             NewValue.MultipleShared = FALSE;
 963             NewValue.Locked = FALSE;
 964
 965             /* It's not already waking, so add the wake bit */
 966             NewValue.Waking = TRUE;
 967
 968             /* Sanity check */
 969             ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
 970
 971             /* Write the new value */
 972             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
 973                                                              NewValue.Ptr,
 974                                                              OldValue.Ptr);
 975             if (NewValue.Value != OldValue.Value) continue;
 976
 977             /* The write was successful. The pushlock is Unlocked and Waking */
 978             ExfWakePushLock(PushLock, NewValue);
 979             break;
 980         }
 981     }
 982 quit:
 983     /* Done! */
 984     return;
 985 }
 986
 987 /*++
 988  * ExfReleasePushLockExclusive
 989  * @implemented NT5.2
 990  *
 991  *     The ExfReleasePushLockExclusive routine releases a previously
 992  *     exclusively acquired PushLock.
 993  *
 994  * @params PushLock
 995  *         Pointer to a previously acquired pushlock.
 996  *
 997  * @return None.
 998  *
 999  * @remarks Callers of ExReleasePushLockExclusive must be running at IRQL <= APC_LEVEL.
1000  *          This macro should usually be paired up with KeLeaveCriticalRegion.
1001  *
1002  *--*/
1003 VOID
1004 FASTCALL
1005 ExfReleasePushLockExclusive(PEX_PUSH_LOCK PushLock)
1006 {
1007     EX_PUSH_LOCK NewValue;
1008     EX_PUSH_LOCK OldValue = *PushLock;
1009
1010     /* Loop until we can change */
1011     for (;;)
1012     {
1013         /* Sanity checks */
1014         ASSERT(OldValue.Locked);
1015         ASSERT(OldValue.Waiting || OldValue.Shared == 0);
1016
1017         /* Check if it's waiting and not yet waking */
1018         if ((OldValue.Waiting) && !(OldValue.Waking))
1019         {
1020             /* Remove the lock bit, and add the wake bit */
1021             NewValue.Value = (OldValue.Value &~ EX_PUSH_LOCK_LOCK) |
1022                               EX_PUSH_LOCK_WAKING;
1023
1024             /* Sanity check */
1025             ASSERT(NewValue.Waking && !NewValue.Locked);
1026
1027             /* Write the New Value */
1028             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
1029                                                              NewValue.Ptr,
1030                                                              OldValue.Ptr);
1031
1032             /* Check if the value changed behind our back */
1033             if (NewValue.Value != OldValue.Value)
1034             {
1035                 /* Loop again */
1036                 OldValue = NewValue;
1037                 continue;
1038             }
1039
1040             /* Wake the Pushlock */
1041             ExfWakePushLock(PushLock, NewValue);
1042             break;
1043         }
1044         else
1045         {
1046             /* A simple unlock */
1047             NewValue.Value = OldValue.Value &~ EX_PUSH_LOCK_LOCK;
1048
1049             /* Sanity check */
1050             ASSERT(NewValue.Waking && !NewValue.Waiting);
1051
1052             /* Write the New Value */
1053             NewValue.Ptr = InterlockedCompareExchangePointer(PushLock,
1054                                                              NewValue.Ptr,
1055                                                              OldValue.Ptr);
1056
1057             /* Check if the value changed behind our back */
1058             if (NewValue.Value == OldValue.Value) break;
1059
1060             /* Loop again */
1061             OldValue = NewValue;
1062         }
1063     }
1064 }
1065
1066 /*++
1067  * @name ExfTryToWakePushLock
1068  * @implemented NT5.2
1069  *
1070  *     The ExfTryToWakePushLock attemps to wake a waiting pushlock.
1071  *
1072  * @param PushLock
1073  *        Pointer to a PushLock which is in the wait state.
1074  *
1075  * @return None.
1076  *
1077  * @remarks The pushlock must be in a wait state and must not be already waking.
1078  *
1079  *--*/
1080 VOID
1081 FASTCALL
1082 ExfTryToWakePushLock(PEX_PUSH_LOCK PushLock)
1083 {
1084     EX_PUSH_LOCK OldValue = *PushLock, NewValue;
1085
1086     /*
1087      * If the Pushlock is not waiting on anything, or if it's already waking up
1088      * and locked, don't do anything
1089      */
1090     if (!(OldValue.Value == (EX_PUSH_LOCK_WAKING | EX_PUSH_LOCK_LOCK)) &&
1091         (OldValue.Waiting))
1092     {
1093         /* Make it Waking */
1094         NewValue = OldValue;
1095         NewValue.Waking = TRUE;
1096
1097         /* Write the New Value */
1098         if (InterlockedCompareExchangePointer(PushLock,
1099                                               NewValue.Ptr,
1100                                               OldValue.Ptr) == OldValue.Ptr)
1101         {
1102             /* Wake the Pushlock */
1103             ExfWakePushLock(PushLock, NewValue);
1104         }
1105     }
1106 }
1107
1108 /*++
1109  * @name ExfUnblockPushLock
1110  * @implemented NT5.1
1111  *
1112  *     The ExfUnblockPushLock routine unblocks a previously blocked PushLock.
1113  *
1114  * @param PushLock
1115  *        Pointer to a previously blocked PushLock.
1116  *
1117  * @return None.
1118  *
1119  * @remarks Callers of ExfUnblockPushLock can be running at any IRQL.
1120  *
1121  *--*/
1122 VOID
1123 FASTCALL
1124 ExfUnblockPushLock(PEX_PUSH_LOCK PushLock,
1125                    PVOID CurrentWaitBlock)
1126 {
1127     PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, NextWaitBlock;
1128     KIRQL OldIrql = DISPATCH_LEVEL;
1129
1130     /* Get the wait block and erase the previous one */
1131     WaitBlock = InterlockedExchangePointer(PushLock->Ptr, 0);
1132     if (WaitBlock)
1133     {
1134         /* Check if there is a linked pushlock and raise IRQL appropriately */
1135         if (WaitBlock->Next) KeRaiseIrql(DISPATCH_LEVEL, &OldIrql);
1136
1137         /* Start block loop */
1138         for (;;)
1139         {
1140             /* Get the next block */
1141             NextWaitBlock = WaitBlock->Next;
1142
1143             /* Remove the wait flag from the Wait block */
1144             if (InterlockedBitTestAndReset(&WaitBlock->Flags, 1))
1145             {
1146                 /* Nobody removed the flag before us, so signal the event */
1147                 KeSetEventBoostPriority(&WaitBlock->WakeEvent, IO_NO_INCREMENT);
1148             }
1149
1150             /* Check if there was a next block */
1151             if (!NextWaitBlock) break;
1152         }
1153
1154         /* Lower IRQL if needed */
1155         if (OldIrql != DISPATCH_LEVEL) KeLowerIrql(OldIrql);
1156     }
1157
1158     /* Check if we got a wait block that's pending */
1159     if ((CurrentWaitBlock) &&
1160         (((PEX_PUSH_LOCK_WAIT_BLOCK)CurrentWaitBlock)->Flags &
1161            EX_PUSH_LOCK_FLAGS_WAIT))
1162     {
1163         /* Wait for the pushlock to be unblocked */
1164         ExTimedWaitForUnblockPushLock(PushLock, CurrentWaitBlock, NULL);
1165     }
1166 }