ReactOS  0.4.14-dev-368-gfa26425
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 INIT_FUNCTION
43 VOID
44 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 */
177  if (WaitBlock->Previous)
178  {
179  /* Raise to Dispatch */
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 */
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 */
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 */
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 */
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
#define InterlockedAndPointer(ptr, val)
Definition: pushlock.c:27
EX_PUSH_LOCK_WAIT_BLOCK
Definition: extypes.h:501
#define IN
Definition: typedefs.h:38
#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
ULONG_PTR MultipleShared
Definition: extypes.h:462
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
LONG NTSTATUS
Definition: precomp.h:26
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:63
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
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp: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
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
#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
#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:714
#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
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
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
static ULONG Timeout
Definition: ping.c:61
#define KeInitializeEvent(pEvt, foo, foo2)
Definition: env_spec_w32.h:477
VOID FASTCALL KeSignalGateBoostPriority(PKGATE Gate)
INIT_FUNCTION VOID NTAPI ExpInitializePushLocks(VOID)
Definition: pushlock.c:45
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 FASTCALL KeInitializeGate(PKGATE Gate)
return STATUS_SUCCESS
Definition: btrfs.c:2938
ULONG ExPushLockSpinCount
Definition: pushlock.c:17
ULONG_PTR Locked
Definition: extypes.h:459
VOID FASTCALL ExfTryToWakePushLock(PEX_PUSH_LOCK PushLock)
Definition: pushlock.c:1165