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