[fireball] 37132: - Refactor timer code to share more macros (see http://www.dcl.hpi.uni-potsdam.de/research/WRK/?p=32). - Implement expiring timers when the user changes the system time. Previously these timers would never expire if the time was set past their expiration points. - Fix a bug in KiInsertTreeTimer where, if a timer expired while we inserted it, we kept its Inserted state to TRUE. - Fix a bug where, when changing the system time, the modifications were not done in the correct order

Author: fireball
Date: Sat Nov  1 10:33:05 2008
New Revision: 37132

URL: http://svn.reactos.org/svn/reactos?rev=37132&view=rev
Log:
- Refactor timer code to share more macros (see
http://www.dcl.hpi.uni-potsdam.de/research/WRK/?p=32).
- Implement expiring timers when the user changes the system time. Previously these timers
would never expire if the time was set past their expiration points.
- Fix a bug in KiInsertTreeTimer where, if a timer expired while we inserted it, we kept
its Inserted state to TRUE.
- Fix a bug where, when changing the system time, the modifications were not done in the
correct order, possibly resulting in a race condition happening if someone else was
checking the time simultaneously.
- Tested with winetest kernel32 timer.
- Thanks to Alex and Stefan.

Modified:
    trunk/reactos/ntoskrnl/include/internal/ke.h
    trunk/reactos/ntoskrnl/include/internal/ke_x.h
    trunk/reactos/ntoskrnl/ke/clock.c
    trunk/reactos/ntoskrnl/ke/dpc.c
    trunk/reactos/ntoskrnl/ke/timerobj.c

Modified: trunk/reactos/ntoskrnl/include/internal/ke.h
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/include/internal/…
==============================================================================
--- trunk/reactos/ntoskrnl/include/internal/ke.h [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/include/internal/ke.h [iso-8859-1] Sat Nov  1 10:33:05 2008
@@ -286,6 +286,13 @@
     IN ULONG Hand
 );
 
+VOID
+FASTCALL
+KiTimerListExpire(
+    IN PLIST_ENTRY ExpiredListHead,
+    IN KIRQL OldIrql
+);
+
 BOOLEAN
 FASTCALL
 KiInsertTreeTimer(

Modified: trunk/reactos/ntoskrnl/include/internal/ke_x.h
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/include/internal/…
==============================================================================
--- trunk/reactos/ntoskrnl/include/internal/ke_x.h [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/include/internal/ke_x.h [iso-8859-1] Sat Nov  1 10:33:05 2008
@@ -1100,6 +1100,37 @@
 }
 
 //
+// Called from KiCompleteTimer, KiInsertTreeTimer, KeSetSystemTime
+// to remove timer entries
+// See Windows HPI blog for more information.
+VOID
+FORCEINLINE
+KiRemoveEntryTimer(IN PKTIMER Timer)
+{
+    ULONG Hand;
+    PKTIMER_TABLE_ENTRY TableEntry;
+    
+    /* Remove the timer from the timer list and check if it's empty */
+    Hand = Timer->Header.Hand;
+    if (RemoveEntryList(&Timer->TimerListEntry))
+    {
+        /* Get the respective timer table entry */
+        TableEntry = &KiTimerTableListHead[Hand];
+        if (&TableEntry->Entry == TableEntry->Entry.Flink)
+        {
+            /* Set the entry to an infinite absolute time */
+            TableEntry->Time.HighPart = 0xFFFFFFFF;
+        }
+    }
+
+    /* Clear the list entries on dbg builds so we can tell the timer is gone */
+#if DBG
+    Timer->TimerListEntry.Flink = NULL;
+    Timer->TimerListEntry.Blink = NULL;
+#endif
+}
+
+//
 // Called by Wait and Queue code to insert a timer for dispatching.
 // Also called by KeSetTimerEx to insert a timer from the caller.
 //
@@ -1125,6 +1156,57 @@
         /* Do nothing, just release the lock */
         KiReleaseTimerLock(LockQueue);
     }
+}
+
+//
+// Called by KeSetTimerEx and KiInsertTreeTimer to calculate Due Time
+// See the Windows HPI Blog for more information
+//
+BOOLEAN
+FORCEINLINE
+KiComputeDueTime(IN PKTIMER Timer,
+                 IN LARGE_INTEGER DueTime,
+                 OUT PULONG Hand)
+{
+    LARGE_INTEGER InterruptTime, SystemTime, DifferenceTime;
+    
+    /* Convert to relative time if needed */
+    Timer->Header.Absolute = FALSE;
+    if (DueTime.HighPart >= 0)
+    {
+        /* Get System Time */
+        KeQuerySystemTime(&SystemTime);
+        
+        /* Do the conversion */
+        DifferenceTime.QuadPart = SystemTime.QuadPart - DueTime.QuadPart;
+        
+        /* Make sure it hasn't already expired */
+        Timer->Header.Absolute = TRUE;
+        if (DifferenceTime.HighPart >= 0)
+        {
+            /* Cancel everything */
+            Timer->Header.SignalState = TRUE;
+            Timer->Header.Hand = 0;
+            Timer->DueTime.QuadPart = 0;
+            *Hand = 0;
+            return FALSE;
+        }
+        
+        /* Set the time as Absolute */
+        DueTime = DifferenceTime;
+    }
+    
+    /* Get the Interrupt Time */
+    InterruptTime.QuadPart = KeQueryInterruptTime();
+    
+    /* Recalculate due time */
+    Timer->DueTime.QuadPart = InterruptTime.QuadPart - DueTime.QuadPart;
+    
+    /* Get the handle */
+    *Hand = KiComputeTimerTableIndex(Timer->DueTime.QuadPart);
+    Timer->Header.Hand = (UCHAR)*Hand;
+    Timer->Header.Inserted = TRUE;
+    return TRUE;
 }
 
 //

Modified: trunk/reactos/ntoskrnl/ke/clock.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/ke/clock.c?rev=37…
==============================================================================
--- trunk/reactos/ntoskrnl/ke/clock.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/ke/clock.c [iso-8859-1] Sat Nov  1 10:33:05 2008
@@ -40,7 +40,6 @@
     PKSPIN_LOCK_QUEUE LockQueue;
     LIST_ENTRY TempList, TempList2;
     ULONG Hand, i;
-    PKTIMER_TABLE_ENTRY TimerEntry;
 
     /* Sanity checks */
     ASSERT((NewTime->HighPart & 0xF0000000) == 0);
@@ -57,10 +56,10 @@
     /* Query the system time now */
     KeQuerySystemTime(OldTime);
 
-    /* Set the new system time */
+    /* Set the new system time (ordering of these operations is critical) */
+    SharedUserData->SystemTime.High2Time = NewTime->HighPart;
     SharedUserData->SystemTime.LowPart = NewTime->LowPart;
     SharedUserData->SystemTime.High1Time = NewTime->HighPart;
-    SharedUserData->SystemTime.High2Time = NewTime->HighPart;
 
     /* Check if this was for the HAL and set the RTC time */
     if (HalTime) ExCmosClockIsSane = HalSetRealTimeClock(&TimeFields);
@@ -98,16 +97,7 @@
             if (Timer->Header.Absolute)
             {
                 /* Remove it from the timer list */
-                if (RemoveEntryList(&Timer->TimerListEntry))
-                {
-                    /* Get the entry and check if it's empty */
-                    TimerEntry = &KiTimerTableListHead[Timer->Header.Hand];
-                    if (IsListEmpty(&TimerEntry->Entry))
-                    {
-                        /* Clear the time then */
-                        TimerEntry->Time.HighPart = 0xFFFFFFFF;
-                    }
-                }
+                KiRemoveEntryTimer(Timer);
 
                 /* Insert it into our temporary list */
                 InsertTailList(&TempList, &Timer->TimerListEntry);
@@ -138,16 +128,7 @@
         if (KiInsertTimerTable(Timer, Hand))
         {
             /* Remove it from the timer list */
-            if (RemoveEntryList(&Timer->TimerListEntry))
-            {
-                /* Get the entry and check if it's empty */
-                TimerEntry = &KiTimerTableListHead[Timer->Header.Hand];
-                if (IsListEmpty(&TimerEntry->Entry))
-                {
-                    /* Clear the time then */
-                    TimerEntry->Time.HighPart = 0xFFFFFFFF;
-                }
-            }
+            KiRemoveEntryTimer(Timer);
 
             /* Insert it into our temporary list */
             InsertTailList(&TempList2, &Timer->TimerListEntry);
@@ -157,8 +138,8 @@
         KiReleaseTimerLock(LockQueue);
     }
 
-    /* FIXME: Process expired timers! */
-    KiReleaseDispatcherLock(OldIrql);
+    /* Process expired timers. This releases the dispatcher lock. */
+    KiTimerListExpire(&TempList2, OldIrql);
 
     /* Revert affinity */
     KeRevertToUserAffinityThread();

Modified: trunk/reactos/ntoskrnl/ke/dpc.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/ke/dpc.c?rev=3713…
==============================================================================
--- trunk/reactos/ntoskrnl/ke/dpc.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/ke/dpc.c [iso-8859-1] Sat Nov  1 10:33:05 2008
@@ -86,7 +86,6 @@
     LONG Limit, Index, i;
     ULONG Timers, ActiveTimers, DpcCalls;
     PLIST_ENTRY ListHead, NextEntry;
-    PKTIMER_TABLE_ENTRY TimerEntry;
     KIRQL OldIrql;
     PKTIMER Timer;
     PKDPC TimerDpc;
@@ -147,16 +146,7 @@
             {
                 /* It's expired, remove it */
                 ActiveTimers--;
-                if (RemoveEntryList(&Timer->TimerListEntry))
-                {
-                    /* Get the entry and check if it's empty */
-                    TimerEntry = &KiTimerTableListHead[Timer->Header.Hand];
-                    if (IsListEmpty(&TimerEntry->Entry))
-                    {
-                        /* Clear the time then */
-                        TimerEntry->Time.HighPart = 0xFFFFFFFF;
-                    }
-                }
+                KiRemoveEntryTimer(Timer);
 
                 /* Make it non-inserted, unlock it, and signal it */
                 Timer->Header.Inserted = FALSE;
@@ -192,6 +182,7 @@
                 }
 
                 /* Check if we have a DPC */
+#ifndef CONFIG_SMP
                 if (TimerDpc)
                 {
                     /* Setup the DPC Entry */
@@ -199,7 +190,11 @@
                     DpcEntry[DpcCalls].Routine = TimerDpc->DeferredRoutine;
                     DpcEntry[DpcCalls].Context = TimerDpc->DeferredContext;
                     DpcCalls++;
+                    ASSERT(DpcCalls < MAX_TIMER_DPCS);
                 }
+#else
+#error MP Case: Need to check the DPC target CPU so see if we can piggyback          
+#endif
 
                 /* Check if we're done processing */
                 if (!(ActiveTimers) || !(Timers))
@@ -295,6 +290,108 @@
 
         /* Lower IRQL if we need to */
         if (OldIrql != DISPATCH_LEVEL) KeLowerIrql(OldIrql);
+    }
+    else
+    {
+        /* Unlock the dispatcher */
+        KiReleaseDispatcherLock(OldIrql);
+    }
+}
+
+VOID
+FASTCALL
+KiTimerListExpire(IN PLIST_ENTRY ExpiredListHead,
+                  IN KIRQL OldIrql)
+{
+    ULARGE_INTEGER SystemTime;
+    LARGE_INTEGER Interval;
+    LONG i;
+    ULONG DpcCalls = 0;
+    PKTIMER Timer;
+    PKDPC TimerDpc;
+    ULONG Period;
+    DPC_QUEUE_ENTRY DpcEntry[MAX_TIMER_DPCS];
+    
+    /* Query system */
+    KeQuerySystemTime((PLARGE_INTEGER)&SystemTime);
+    
+    /* Loop expired list */
+    while (ExpiredListHead->Flink != ExpiredListHead)
+    {
+        /* Get the current timer */
+        Timer = CONTAINING_RECORD(ExpiredListHead->Flink, KTIMER, TimerListEntry);
+        
+        /* Remove it */
+        RemoveEntryList(&Timer->TimerListEntry);
+        
+        /* Not inserted */
+        Timer->Header.Inserted = FALSE;
+        
+        /* Signal it */
+        Timer->Header.SignalState = 1;
+        
+        /* Get the DPC and period */
+        TimerDpc = Timer->Dpc;
+        Period = Timer->Period;
+        
+        /* Check if there's any waiters */
+        if (!IsListEmpty(&Timer->Header.WaitListHead))
+        {
+            /* Check the type of event */
+            if (Timer->Header.Type == TimerNotificationObject)
+            {
+                /* Unwait the thread */
+                KxUnwaitThread(&Timer->Header, IO_NO_INCREMENT);
+            }
+            else
+            {
+                /* Otherwise unwait the thread and signal the timer */
+                KxUnwaitThreadForEvent((PKEVENT)Timer, IO_NO_INCREMENT);
+            }
+        }
+        
+        /* Check if we have a period */
+        if (Period)
+        {
+            /* Calculate the interval and insert the timer */
+            Interval.QuadPart = Int32x32To64(Period, -10000);
+            while (!KiInsertTreeTimer(Timer, Interval));
+        }
+                
+        /* Check if we have a DPC */
+#ifndef CONFIG_SMP
+        if (TimerDpc)
+        {
+            /* Setup the DPC Entry */
+            DpcEntry[DpcCalls].Dpc = TimerDpc;
+            DpcEntry[DpcCalls].Routine = TimerDpc->DeferredRoutine;
+            DpcEntry[DpcCalls].Context = TimerDpc->DeferredContext;
+            DpcCalls++;
+            ASSERT(DpcCalls < MAX_TIMER_DPCS);
+        }
+#else
+#error MP Case: Need to check the DPC target CPU so see if we can piggyback          
+#endif
+    }
+    
+    /* Check if we still have DPC entries */
+    if (DpcCalls)
+    {
+        /* Release the dispatcher while doing DPCs */
+        KiReleaseDispatcherLock(DISPATCH_LEVEL);
+        
+        /* Start looping all DPC Entries */
+        for (i = 0; DpcCalls; DpcCalls--, i++)
+        {
+            /* Call the DPC */
+            DpcEntry[i].Routine(DpcEntry[i].Dpc,
+                                DpcEntry[i].Context,
+                                UlongToPtr(SystemTime.LowPart),
+                                UlongToPtr(SystemTime.HighPart));
+        }
+        
+        /* Lower IRQL */
+        KeLowerIrql(OldIrql);
     }
     else
     {

Modified: trunk/reactos/ntoskrnl/ke/timerobj.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/ke/timerobj.c?rev…
==============================================================================
--- trunk/reactos/ntoskrnl/ke/timerobj.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/ke/timerobj.c [iso-8859-1] Sat Nov  1 10:33:05 2008
@@ -29,71 +29,29 @@
     BOOLEAN Inserted = FALSE;
     ULONG Hand = 0;
     PKSPIN_LOCK_QUEUE LockQueue;
-    LONGLONG DueTime;
-    LARGE_INTEGER InterruptTime, SystemTime, DifferenceTime;
-    PKTIMER_TABLE_ENTRY TimerEntry;
-
     DPRINT("KiInsertTreeTimer(): Timer %p, Interval: %I64d\n", Timer,
Interval.QuadPart);
 
-    /* Convert to relative time if needed */
-    Timer->Header.Absolute = FALSE;
-    if (Interval.HighPart >= 0)
-    {
-        /* Get System Time */
-        KeQuerySystemTime(&SystemTime);
-
-        /* Do the conversion */
-        DifferenceTime.QuadPart = SystemTime.QuadPart - Interval.QuadPart;
-
-        /* Make sure it hasn't already expired */
-        Timer->Header.Absolute = TRUE;
-        if (DifferenceTime.HighPart >= 0)
+    /* Setup the timer's due time */
+    if (KiComputeDueTime(Timer, Interval, &Hand))
+    {
+        /* Acquire the lock */
+        LockQueue = KiAcquireTimerLock(Hand);
+
+        /* Insert the timer */
+        if (KiInsertTimerTable(Timer, Hand))
         {
-            /* Cancel everything */
-            Timer->Header.SignalState = TRUE;
-            Timer->Header.Hand = 0;
-            Timer->DueTime.QuadPart = 0;
-            return FALSE;
+            /* It was already there, remove it */
+            KiRemoveEntryTimer(Timer);
+            Timer->Header.Inserted = FALSE;
         }
-
-        /* Set the time as Absolute */
-        Interval = DifferenceTime;
-    }
-
-    /* Get the Interrupt Time */
-    InterruptTime.QuadPart = KeQueryInterruptTime();
-
-    /* Recalculate due time */
-    DueTime = InterruptTime.QuadPart - Interval.QuadPart;
-    Timer->DueTime.QuadPart = DueTime;
-
-    /* Get the handle */
-    Hand = KiComputeTimerTableIndex(DueTime);
-    Timer->Header.Hand = (UCHAR)Hand;
-    Timer->Header.Inserted = TRUE;
-
-    /* Acquire the lock */
-    LockQueue = KiAcquireTimerLock(Hand);
-
-    /* Insert the timer */
-    if (KiInsertTimerTable(Timer, Hand))
-    {
-        /* It was already there, remove it */
-        if (RemoveEntryList(&Timer->TimerListEntry))
+        else
         {
-            /* Get the entry and check if it's empty */
-            TimerEntry = &KiTimerTableListHead[Hand];
-            if (IsListEmpty(&TimerEntry->Entry))
-            {
-                /* Clear the time then */
-                TimerEntry->Time.HighPart = 0xFFFFFFFF;
-            }
+            /* Otherwise, we're now inserted */
+            Inserted = TRUE;
         }
-    }
-    else
-    {
-        /* Otherwise, we're now inserted */
-        Inserted = TRUE;
+        
+        /* Release the lock */
+        KiReleaseTimerLock(LockQueue);
     }
 
     /* Release the lock and return insert status */
@@ -110,7 +68,6 @@
     BOOLEAN Expired = FALSE;
     PLIST_ENTRY ListHead, NextEntry;
     PKTIMER CurrentTimer;
-
     DPRINT("KiInsertTimerTable(): Timer %p, Hand: %d\n", Timer, Hand);
 
     /* Check if the period is zero */
@@ -160,7 +117,6 @@
     PKDPC Dpc = Timer->Dpc;
     ULONG Period = Timer->Period;
     LARGE_INTEGER Interval, SystemTime;
-
     DPRINT("KiSignalTimer(): Timer %p\n", Timer);
 
     /* Set default values */
@@ -212,22 +168,11 @@
                 IN PKSPIN_LOCK_QUEUE LockQueue)
 {
     LIST_ENTRY ListHead;
-    PKTIMER_TABLE_ENTRY TimerEntry;
     BOOLEAN RequestInterrupt = FALSE;
-
     DPRINT("KiCompleteTimer(): Timer %p, LockQueue: %p\n", Timer, LockQueue);
 
     /* Remove it from the timer list */
-    if (RemoveEntryList(&Timer->TimerListEntry))
-    {
-        /* Get the entry and check if it's empty */
-        TimerEntry = &KiTimerTableListHead[Timer->Header.Hand];
-        if (IsListEmpty(&TimerEntry->Entry))
-        {
-            /* Clear the time then */
-            TimerEntry->Time.HighPart = 0xFFFFFFFF;
-        }
-    }
+    KiRemoveEntryTimer(Timer);
 
     /* Link the timer list to our stack */
     ListHead.Flink = &Timer->TimerListEntry;
@@ -264,7 +209,6 @@
     BOOLEAN Inserted;
     ASSERT_TIMER(Timer);
     ASSERT(KeGetCurrentIrql() <= DISPATCH_LEVEL);
-
     DPRINT("KeCancelTimer(): Timer %p\n", Timer);
 
     /* Lock the Database and Raise IRQL */
@@ -301,7 +245,8 @@
                     IN TIMER_TYPE Type)
 {
     DPRINT("KeInitializeTimerEx(): Timer %p, Type %s\n",
-        Timer, (Type == NotificationTimer) ? "NotificationTimer" :
"SynchronizationTimer");
+            Timer, (Type == NotificationTimer) ?
+           "NotificationTimer" : "SynchronizationTimer");
 
     /* Initialize the Dispatch Header */
     KeInitializeDispatcherHeader(&Timer->Header,
@@ -352,13 +297,11 @@
     KIRQL OldIrql;
     BOOLEAN Inserted;
     ULONG Hand = 0;
-    LARGE_INTEGER InterruptTime, SystemTime, DifferenceTime;
     BOOLEAN RequestInterrupt = FALSE;
     ASSERT_TIMER(Timer);
     ASSERT(KeGetCurrentIrql() <= DISPATCH_LEVEL);
-
     DPRINT("KeSetTimerEx(): Timer %p, DueTime %I64d, Period %d, Dpc %p\n",
-        Timer, DueTime.QuadPart, Period, Dpc);
+           Timer, DueTime.QuadPart, Period, Dpc);
 
     /* Lock the Database and Raise IRQL */
     OldIrql = KiAcquireDispatcherLock();
@@ -370,59 +313,24 @@
     /* Set Default Timer Data */
     Timer->Dpc = Dpc;
     Timer->Period = Period;
-
-    /* Convert to relative time if needed */
-    Timer->Header.Absolute = FALSE;
-    if (DueTime.HighPart >= 0)
-    {
-        /* Get System Time */
-        KeQuerySystemTime(&SystemTime);
-
-        /* Do the conversion */
-        DifferenceTime.QuadPart = SystemTime.QuadPart - DueTime.QuadPart;
-
-        /* Make sure it hasn't already expired */
-        Timer->Header.Absolute = TRUE;
-        if (DifferenceTime.HighPart >= 0)
-        {
-            /* Cancel everything */
-            Timer->Header.SignalState = TRUE;
-            Timer->Header.Hand = 0;
-            Timer->DueTime.QuadPart = 0;
-
-            /* Signal the timer */
-            RequestInterrupt = KiSignalTimer(Timer);
-
-            /* Release the dispatcher lock */
-            KiReleaseDispatcherLockFromDpcLevel();
-
-            /* Check if we need to do an interrupt */
-            if (RequestInterrupt) HalRequestSoftwareInterrupt(DISPATCH_LEVEL);
-
-            /* Exit the dispatcher and return the old state */
-            KiExitDispatcher(OldIrql);
-            return Inserted;
-        }
-
-        /* Set the time as Absolute */
-        DueTime = DifferenceTime;
-    }
-
-    /* Get the Interrupt Time */
-    InterruptTime.QuadPart = KeQueryInterruptTime();
-
-    /* Recalculate due time */
-    Timer->DueTime.QuadPart = InterruptTime.QuadPart - DueTime.QuadPart;
-
-    /* Get the handle */
-    Hand = KiComputeTimerTableIndex(Timer->DueTime.QuadPart);
-    Timer->Header.Hand = (UCHAR)Hand;
-    Timer->Header.Inserted = TRUE;
-
-    /* Insert the timer */
-    Timer->Header.SignalState = FALSE;
-    KxInsertTimer(Timer, Hand);
-
+    if (!KiComputeDueTime(Timer, DueTime, &Hand))
+    {
+        /* Signal the timer */
+        RequestInterrupt = KiSignalTimer(Timer);
+        
+        /* Release the dispatcher lock */
+        KiReleaseDispatcherLockFromDpcLevel();
+        
+        /* Check if we need to do an interrupt */
+        if (RequestInterrupt) HalRequestSoftwareInterrupt(DISPATCH_LEVEL);        
+    }
+    else
+    {
+        /* Insert the timer */
+        Timer->Header.SignalState = FALSE;
+        KxInsertTimer(Timer, Hand);        
+    }
+    
     /* Exit the dispatcher */
     KiExitDispatcher(OldIrql);