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