Author: fireball Date: Tue Apr 1 13:14:01 2008 New Revision: 32809
URL: http://svn.reactos.org/svn/reactos?rev=32809&view=rev Log: - Use C define for the bit in the wait block flags that we set to specify waiting, instead of a hardcoded "1". - Fix broken code when trying to find the last wait block in several parts of the pushlock code. - Fix broken algorithm in the optimization of the pushlock waiter list. - The wake event for the pushlock should be a synchronization event, not a notification event. - Fix broken algorithm during the release of a pushlock (in shared cases). - Fix broken code during "try to wake pushlock". - Remove DbgPrints from inlined pushlock code during contention. - Thanks to Alex for noticing these bugs and providing advice on the fixes. This fixes lots of race issues in the handle table implementation.
Modified: trunk/reactos/include/ndk/extypes.h trunk/reactos/ntoskrnl/ex/pushlock.c (contents, props changed) trunk/reactos/ntoskrnl/include/internal/ex.h
Modified: trunk/reactos/include/ndk/extypes.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/include/ndk/extypes.h?rev=3... ============================================================================== --- trunk/reactos/include/ndk/extypes.h [iso-8859-1] (original) +++ trunk/reactos/include/ndk/extypes.h [iso-8859-1] Tue Apr 1 13:14:01 2008 @@ -147,6 +147,7 @@ // Pushlock Wait Block Flags // #define EX_PUSH_LOCK_FLAGS_EXCLUSIVE 1 +#define EX_PUSH_LOCK_FLAGS_WAIT_V 1 #define EX_PUSH_LOCK_FLAGS_WAIT 2
//
Modified: trunk/reactos/ntoskrnl/ex/pushlock.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/ex/pushlock.c?rev=... ============================================================================== --- trunk/reactos/ntoskrnl/ex/pushlock.c [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/ex/pushlock.c [iso-8859-1] Tue Apr 1 13:14:01 2008 @@ -65,7 +65,7 @@ EX_PUSH_LOCK OldValue) { EX_PUSH_LOCK NewValue; - PEX_PUSH_LOCK_WAIT_BLOCK PreviousWaitBlock, FirstWaitBlock, NextWaitBlock; + PEX_PUSH_LOCK_WAIT_BLOCK PreviousWaitBlock, FirstWaitBlock, LastWaitBlock; PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock; KIRQL OldIrql;
@@ -99,23 +99,30 @@ /* Save the First Block */ FirstWaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr & ~EX_PUSH_LOCK_PTR_BITS); - NextWaitBlock = FirstWaitBlock; - WaitBlock = NextWaitBlock->Last; - - /* Try to find a wait block */ - while (!WaitBlock) - { + WaitBlock = FirstWaitBlock; + + /* Try to find the last block */ + while (TRUE) + { + /* Get the last wait block */ + LastWaitBlock = WaitBlock->Last; + + /* Check if we found it */ + if (LastWaitBlock) + { + /* Use it */ + WaitBlock = LastWaitBlock; + break; + } + /* Save the previous block */ - PreviousWaitBlock = NextWaitBlock; + PreviousWaitBlock = WaitBlock;
/* Move to next block */ - NextWaitBlock = NextWaitBlock->Next; + WaitBlock = WaitBlock->Next;
/* Save the previous block */ - NextWaitBlock->Previous = PreviousWaitBlock; - - /* Move to the next one */ - WaitBlock = NextWaitBlock->Last; + WaitBlock->Previous = PreviousWaitBlock; }
/* Check if the last Wait Block is not Exclusive or if it's the only one */ @@ -211,58 +218,65 @@ ExpOptimizePushLockList(PEX_PUSH_LOCK PushLock, EX_PUSH_LOCK OldValue) { - PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock, PreviousWaitBlock; + PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock, PreviousWaitBlock, FirstWaitBlock; EX_PUSH_LOCK NewValue;
- /* Check if the pushlock is locked */ - if (OldValue.Locked) - { - /* Start main loop */ - for (;;) - { - /* Get the wait block */ - WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr & - ~EX_PUSH_LOCK_PTR_BITS); - - /* Loop the blocks */ + /* Start main loop */ + for (;;) + { + /* Check if we've been unlocked */ + if (!OldValue.Locked) + { + /* Wake us up and leave */ + ExfWakePushLock(PushLock, OldValue); + break; + } + + /* Get the wait block */ + WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr & + ~EX_PUSH_LOCK_PTR_BITS); + + /* Loop the blocks */ + FirstWaitBlock = WaitBlock; + while (TRUE) + { + /* Get the last wait block */ LastWaitBlock = WaitBlock->Last; - while (!LastWaitBlock) - { - /* Save the block */ - PreviousWaitBlock = WaitBlock; - - /* Get the next block */ - WaitBlock = WaitBlock->Next; - - /* Save the previous */ - WaitBlock->Previous = PreviousWaitBlock; - - /* Move to the next */ - LastWaitBlock = WaitBlock->Last; - } - - /* Remove the wake bit */ - NewValue.Value = OldValue.Value &~ EX_PUSH_LOCK_WAKING; - - /* Sanity checks */ - ASSERT(NewValue.Locked); - ASSERT(!NewValue.Waking); - - /* Update the value */ - NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, - NewValue.Ptr, - OldValue.Ptr); - - /* If we updated correctly, leave */ - if (NewValue.Value == OldValue.Value) return; - - /* If the value is now locked, loop again */ - if (NewValue.Locked) continue; - } - } - - /* Wake the push lock */ - ExfWakePushLock(PushLock, OldValue); + if (LastWaitBlock) + { + /* Set this as the new last block, we're done */ + FirstWaitBlock->Last = LastWaitBlock; + break; + } + + /* Save the block */ + PreviousWaitBlock = WaitBlock; + + /* Get the next block */ + WaitBlock = WaitBlock->Next; + + /* Save the previous */ + WaitBlock->Previous = PreviousWaitBlock; + } + + /* Remove the wake bit */ + NewValue.Value = OldValue.Value &~ EX_PUSH_LOCK_WAKING; + + /* Sanity checks */ + ASSERT(NewValue.Locked); + ASSERT(!NewValue.Waking); + + /* Update the value */ + NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, + NewValue.Ptr, + OldValue.Ptr); + + /* If we updated correctly, leave */ + if (NewValue.Value == OldValue.Value) break; + + /* Update value */ + OldValue = NewValue; + } }
/*++ @@ -297,7 +311,7 @@
/* Initialize the wait event */ KeInitializeEvent(&((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)->WakeEvent, - NotificationEvent, + SynchronizationEvent, FALSE);
/* Spin on the push lock if necessary */ @@ -320,7 +334,7 @@
/* Now try to remove the wait bit */ if (InterlockedBitTestAndReset(&((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)->Flags, - 1)) + EX_PUSH_LOCK_FLAGS_WAIT_V)) { /* Nobody removed it already, let's do a full wait */ Status = KeWaitForSingleObject(&((PEX_PUSH_LOCK_WAIT_BLOCK)WaitBlock)-> @@ -766,18 +780,17 @@ FASTCALL ExfReleasePushLock(PEX_PUSH_LOCK PushLock) { - EX_PUSH_LOCK OldValue = *PushLock; - EX_PUSH_LOCK NewValue; - PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock; + EX_PUSH_LOCK OldValue = *PushLock, NewValue, WakeValue; + PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock;
/* Sanity check */ ASSERT(OldValue.Locked); - - /* Check if someone is waiting on the lock */ - if (!OldValue.Waiting) - { - /* Nobody is waiting on it, so we'll try a quick release */ - for (;;) + + /* Start main loop */ + while (TRUE) + { + /* Check if someone is waiting on the lock */ + if (!OldValue.Waiting) { /* Check if it's shared */ if (OldValue.Shared > 1) @@ -800,28 +813,179 @@
/* Did it enter a wait state? */ OldValue = NewValue; - if (NewValue.Waiting) break; - } + } + else + { + /* Ok, we do know someone is waiting on it. Are there more then one? */ + if (OldValue.MultipleShared) + { + /* Get the wait block */ + WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr & + ~EX_PUSH_LOCK_PTR_BITS); + + /* Loop until we find the last wait block */ + while (TRUE) + { + /* Get the last wait block */ + LastWaitBlock = WaitBlock->Last; + + /* Did it exist? */ + if (LastWaitBlock) + { + /* Choose it */ + WaitBlock = LastWaitBlock; + break; + } + + /* Keep searching */ + WaitBlock = WaitBlock->Next; + } + + /* Make sure the Share Count is above 0 */ + if (WaitBlock->ShareCount > 0) + { + /* This shouldn't be an exclusive wait block */ + ASSERT(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE); + + /* Do the decrease and check if the lock isn't shared anymore */ + if (InterlockedDecrement(&WaitBlock->ShareCount) > 0) return; + } + } + + /* + * If nobody was waiting on the block, then we possibly reduced the number + * of times the pushlock was shared, and we unlocked it. + * If someone was waiting, and more then one person is waiting, then we + * reduced the number of times the pushlock is shared in the wait block. + * Therefore, at this point, we can now 'satisfy' the wait. + */ + for (;;) + { + /* Now we need to see if it's waking */ + if (OldValue.Waking) + { + /* Remove the lock and multiple shared bits */ + NewValue.Value = OldValue.Value; + NewValue.MultipleShared = FALSE; + NewValue.Locked = FALSE; + + /* Sanity check */ + ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared); + + /* Write the new value */ + NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, + NewValue.Ptr, + OldValue.Ptr); + if (NewValue.Value == OldValue.Value) return; + } + else + { + /* Remove the lock and multiple shared bits */ + NewValue.Value = OldValue.Value; + NewValue.MultipleShared = FALSE; + NewValue.Locked = FALSE; + + /* It's not already waking, so add the wake bit */ + NewValue.Waking = TRUE; + + /* Sanity check */ + ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared); + + /* Write the new value */ + WakeValue = NewValue; + NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, + NewValue.Ptr, + OldValue.Ptr); + if (NewValue.Value != OldValue.Value) continue; + + /* The write was successful. The pushlock is Unlocked and Waking */ + ExfWakePushLock(PushLock, WakeValue); + return; + } + } + } + } +} + +/*++ + * @name ExfReleasePushLockShared + * @implemented NT5.2 + * + * The ExfReleasePushLockShared macro releases a previously acquired PushLock. + * + * @params PushLock + * Pointer to a previously acquired pushlock. + * + * @return None. + * + * @remarks Callers of ExReleasePushLockShared must be running at IRQL <= APC_LEVEL. + * This macro should usually be paired up with KeLeaveCriticalRegion. + * + *--*/ +VOID +FASTCALL +ExfReleasePushLockShared(PEX_PUSH_LOCK PushLock) +{ + EX_PUSH_LOCK OldValue = *PushLock, NewValue, WakeValue; + PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock, LastWaitBlock; + + /* Check if someone is waiting on the lock */ + while (!OldValue.Waiting) + { + /* Check if it's shared */ + if (OldValue.Shared > 1) + { + /* Write the Old Value but decrease share count */ + NewValue = OldValue; + NewValue.Shared--; + } + else + { + /* Simply clear the lock */ + NewValue.Value = 0; + } + + /* Write the New Value */ + NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, + NewValue.Ptr, + OldValue.Ptr); + if (NewValue.Value == OldValue.Value) return; + + /* Did it enter a wait state? */ + OldValue = NewValue; }
/* Ok, we do know someone is waiting on it. Are there more then one? */ if (OldValue.MultipleShared) { - /* Find the last Wait Block */ - for (WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr & - ~EX_PUSH_LOCK_PTR_BITS); - !WaitBlock->Last; - WaitBlock = WaitBlock->Next); - - /* Make sure the Share Count is above 0 */ - if (WaitBlock->ShareCount > 0) - { - /* This shouldn't be an exclusive wait block */ - ASSERT(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE); - - /* Do the decrease and check if the lock isn't shared anymore */ - if (InterlockedDecrement(&WaitBlock->ShareCount) > 0) return; - } + /* Get the wait block */ + WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr & + ~EX_PUSH_LOCK_PTR_BITS); + + /* Loop until we find the last wait block */ + while (TRUE) + { + /* Get the last wait block */ + LastWaitBlock = WaitBlock->Last; + + /* Did it exist? */ + if (LastWaitBlock) + { + /* Choose it */ + WaitBlock = LastWaitBlock; + break; + } + + /* Keep searching */ + WaitBlock = WaitBlock->Next; + } + + /* Sanity checks */ + ASSERT(WaitBlock->ShareCount > 0); + ASSERT(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE); + + /* Do the decrease and check if the lock isn't shared anymore */ + if (InterlockedDecrement(&WaitBlock->ShareCount) > 0) return; }
/* @@ -864,131 +1028,14 @@ ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared);
/* Write the new value */ + WakeValue = NewValue; NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, NewValue.Ptr, OldValue.Ptr); if (NewValue.Value != OldValue.Value) continue;
/* The write was successful. The pushlock is Unlocked and Waking */ - ExfWakePushLock(PushLock, NewValue); - return; - } - } -} - -/*++ - * @name ExfReleasePushLockShared - * @implemented NT5.2 - * - * The ExfReleasePushLockShared macro releases a previously acquired PushLock. - * - * @params PushLock - * Pointer to a previously acquired pushlock. - * - * @return None. - * - * @remarks Callers of ExReleasePushLockShared must be running at IRQL <= APC_LEVEL. - * This macro should usually be paired up with KeLeaveCriticalRegion. - * - *--*/ -VOID -FASTCALL -ExfReleasePushLockShared(PEX_PUSH_LOCK PushLock) -{ - EX_PUSH_LOCK OldValue = *PushLock; - EX_PUSH_LOCK NewValue; - PEX_PUSH_LOCK_WAIT_BLOCK WaitBlock; - - /* Check if someone is waiting on the lock */ - while (!OldValue.Waiting) - { - /* Check if it's shared */ - if (OldValue.Shared > 1) - { - /* Write the Old Value but decrease share count */ - NewValue = OldValue; - NewValue.Shared--; - } - else - { - /* Simply clear the lock */ - NewValue.Value = 0; - } - - /* Write the New Value */ - NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, - NewValue.Ptr, - OldValue.Ptr); - if (NewValue.Value == OldValue.Value) return; - - /* Did it enter a wait state? */ - OldValue = NewValue; - } - - /* Ok, we do know someone is waiting on it. Are there more then one? */ - if (OldValue.MultipleShared) - { - /* Find the last Wait Block */ - for (WaitBlock = (PEX_PUSH_LOCK_WAIT_BLOCK)((ULONG_PTR)OldValue.Ptr & - ~EX_PUSH_LOCK_PTR_BITS); - !WaitBlock->Last; - WaitBlock = WaitBlock->Next); - - /* Sanity checks */ - ASSERT(WaitBlock->ShareCount > 0); - ASSERT(WaitBlock->Flags & EX_PUSH_LOCK_FLAGS_EXCLUSIVE); - - /* Do the decrease and check if the lock isn't shared anymore */ - if (InterlockedDecrement(&WaitBlock->ShareCount) > 0) return; - } - - /* - * If nobody was waiting on the block, then we possibly reduced the number - * of times the pushlock was shared, and we unlocked it. - * If someone was waiting, and more then one person is waiting, then we - * reduced the number of times the pushlock is shared in the wait block. - * Therefore, at this point, we can now 'satisfy' the wait. - */ - for (;;) - { - /* Now we need to see if it's waking */ - if (OldValue.Waking) - { - /* Remove the lock and multiple shared bits */ - NewValue.Value = OldValue.Value; - NewValue.MultipleShared = FALSE; - NewValue.Locked = FALSE; - - /* Sanity check */ - ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared); - - /* Write the new value */ - NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, - NewValue.Ptr, - OldValue.Ptr); - if (NewValue.Value == OldValue.Value) return; - } - else - { - /* Remove the lock and multiple shared bits */ - NewValue.Value = OldValue.Value; - NewValue.MultipleShared = FALSE; - NewValue.Locked = FALSE; - - /* It's not already waking, so add the wake bit */ - NewValue.Waking = TRUE; - - /* Sanity check */ - ASSERT(NewValue.Waking && !NewValue.Locked && !NewValue.MultipleShared); - - /* Write the new value */ - NewValue.Ptr = InterlockedCompareExchangePointer(PushLock, - NewValue.Ptr, - OldValue.Ptr); - if (NewValue.Value != OldValue.Value) continue; - - /* The write was successful. The pushlock is Unlocked and Waking */ - ExfWakePushLock(PushLock, NewValue); + ExfWakePushLock(PushLock, WakeValue); return; } } @@ -1094,21 +1141,19 @@ * If the Pushlock is not waiting on anything, or if it's already waking up * and locked, don't do anything */ - if (!(OldValue.Value == (EX_PUSH_LOCK_WAKING | EX_PUSH_LOCK_LOCK)) && - (OldValue.Waiting)) - { - /* Make it Waking */ - NewValue = OldValue; - NewValue.Waking = TRUE; - - /* Write the New Value */ - if (InterlockedCompareExchangePointer(PushLock, - NewValue.Ptr, - OldValue.Ptr) == OldValue.Ptr) - { - /* Wake the Pushlock */ - ExfWakePushLock(PushLock, NewValue); - } + if ((OldValue.Waking) || (OldValue.Locked) || !(OldValue.Waiting)) return; + + /* Make it Waking */ + NewValue = OldValue; + NewValue.Waking = TRUE; + + /* Write the New Value */ + if (InterlockedCompareExchangePointer(PushLock, + NewValue.Ptr, + OldValue.Ptr) == OldValue.Ptr) + { + /* Wake the Pushlock */ + ExfWakePushLock(PushLock, NewValue); } }
@@ -1142,20 +1187,20 @@ if (WaitBlock->Next) KeRaiseIrql(DISPATCH_LEVEL, &OldIrql);
/* Start block loop */ - for (;;) + while (WaitBlock) { /* Get the next block */ NextWaitBlock = WaitBlock->Next;
/* Remove the wait flag from the Wait block */ - if (InterlockedBitTestAndReset(&WaitBlock->Flags, 1)) + if (!InterlockedBitTestAndReset(&WaitBlock->Flags, EX_PUSH_LOCK_FLAGS_WAIT_V)) { /* Nobody removed the flag before us, so signal the event */ KeSetEventBoostPriority(&WaitBlock->WakeEvent, NULL); }
- /* Check if there was a next block */ - if (!NextWaitBlock) break; + /* Try the next one */ + WaitBlock = NextWaitBlock; }
/* Lower IRQL if needed */
Propchange: trunk/reactos/ntoskrnl/ex/pushlock.c ------------------------------------------------------------------------------ --- svn:needs-lock (original) +++ svn:needs-lock (removed) @@ -1,1 +1,0 @@ -*
Modified: trunk/reactos/ntoskrnl/include/internal/ex.h URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/include/internal/e... ============================================================================== --- trunk/reactos/ntoskrnl/include/internal/ex.h [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/include/internal/ex.h [iso-8859-1] Tue Apr 1 13:14:01 2008 @@ -26,6 +26,7 @@ extern ULONG NtGlobalFlag; extern ULONG ExpInitializationPhase; extern ULONG ExpAltTimeZoneBias; +extern LIST_ENTRY ExSystemLookasideListHead;
typedef struct _EXHANDLE { @@ -711,7 +712,6 @@ if (InterlockedBitTestAndSet((PLONG)PushLock, EX_PUSH_LOCK_LOCK_V)) { /* Someone changed it, use the slow path */ - // DbgPrint("%s - Contention!\n", __FUNCTION__); ExfAcquirePushLockExclusive(PushLock); }
@@ -750,6 +750,7 @@ }
/* Got acquired */ + ASSERT (PushLock->Locked); return TRUE; }
@@ -783,7 +784,6 @@ if (ExpChangePushlock(PushLock, NewValue.Ptr, 0)) { /* Someone changed it, use the slow path */ - // DbgPrint("%s - Contention!\n", __FUNCTION__); ExfAcquirePushLockShared(PushLock); }
@@ -897,7 +897,6 @@ if (ExpChangePushlock(PushLock, 0, OldValue.Ptr) != OldValue.Ptr) { /* There are still other people waiting on it */ - DbgPrint("%s - Contention!\n", __FUNCTION__); ExfReleasePushLockShared(PushLock); } } @@ -945,7 +944,6 @@ if ((OldValue.Waiting) && !(OldValue.Waking)) { /* Wake it up */ - DbgPrint("%s - Contention!\n", __FUNCTION__); ExfTryToWakePushLock(PushLock); } } @@ -997,7 +995,6 @@ OldValue.Ptr)) { /* We have waiters, use the long path */ - // DbgPrint("%s - Contention!\n", __FUNCTION__); ExfReleasePushLock(PushLock); } }