Hi,
I recently used the WRK sources to figure out some details about Windows timer management, when I recognized the following comment in file base\ntos\inc\ntosdef.h on lines 618 thru 624:
Code Snippet
00618 //
00619 // Define timer table size.
00620 //
00621 // N.B. The size of the timer table must be less than or equal to 256 and a
00622 // power of 2 in size.
00623
00624 #define TIMER_TABLE_SIZE 512
Obviously, the definition of TIMER_TABLE_SIZE is inconsistent with the comment and it spent me some hours to find out that this might lead to a bug. I will briefly present my findings here, a more detailed version is available here.
When Windows inserts a timer object in its corresponding timer table entry, it stores the index of this entry in the timer's DISPATCHER_HEADER structure, i.e. DISPATCHER_HEADER::Hand. The index is calculated with the formula: Hand = (Due time / Maximum time) % TIMER_TABLE_SIZE. That means, Hand can be in range between 0 and 511. In function KeComputeDueTime() (see base\ntos\ke\ki.h), this index is cast into a UCHAR value, so index might overflow, because in a UCHAR you can only encode values between 0 and 255!
Code Snippet
01219 *Hand = KiComputeTimerTableIndex
(DueTime
);
01220 Timer->Header.
Hand =
(UCHAR
)*Hand;
01221 Timer->Header.
Inserted =
TRUE;
01222 return TRUE;
This cast becomes a problem when Windows removes the timer from its timer list (KiRemoveEntryTimer in base\ntos\ke\ki.h):
Code Snippet
01968 ULONG Hand;
01969 PKTIMER_TABLE_ENTRY TableEntry;
01970
01971 //
01972 // Remove the timer from the timer table. If the timer table list is
01973 // empty, then set the respective timer table due time to an infinite
01974 // absolute time.
01975 //
01976 // N.B. It is the responsibility of the caller to set the timer inserted
01977 // state.
01978 //
01979
01980 Hand = Timer->Header.Hand;
01981 if (RemoveEntryList(&Timer->TimerListEntry) != FALSE) {
01982 TableEntry = &KiTimerTableListHead[Hand];
01983 if (&TableEntry->Entry == TableEntry->Entry.Flink) {
01984 TableEntry->Time.HighPart = 0xffffffff;
01985 }
01986 }
In the code snippet above, Header.Hand is used to identify the timer table entry. If the timer list gets empty, the due time must be set to an infinite absolute due time. Unfortunately, if Hand was originally, let's say, 257, Hand in the above code is actually 1 (257 % 256)! So, Windows checks whether the timer list KiTimerTableListHead[1] is empty, although it should have checked KiTimerTableListHead[257]. If KiTimerTablerListHead[1] is not empty, the Time field in KiTimerTableListHead[257] keeps its old value, i.e., an absolute due time in the past.
Now refer to KeUpdateSystemTime() in base\ntos\ke\arch\clockint.asm. The following code is used to determine, whether a timer has expired:
Code Snippet
00212 ; 00213 ; Check to determine if a timer has expired. 00214 ; (edi:esi) = KiInterruptTime 00215 ; (eax) = bucket 00216 ; (ebx) = KeTickCount.LowPart 00217 ; 00218 00219 kust10:
and eax,TIMER_TABLE_SIZE
-1 ; isolate current hand value 00220 shl eax,
4 ; compute timer entry offset 00221 cmp esi,
[eax]+_KiTimerTableListHead+TtTime
+4 ; compare high due time 00222 jb kustxx
; if below, timer has not expired 00223 ja short kust15
; if above, timer has expired 00224 cmp edi,
[eax]+_KiTimerTableListHead+TtTime
; compare low due time 00225 jb kustxx
; if below, timer has not expired 00226 kust15:
; 00227
As the Time field remains a valid but past due time, this code results in enqueuing a DPC routine to handle expired timers, although the timer list is empty!
Another critical routine is KiRemoveTreeTimer() (see base\ntos\ke\ki.h). This function does the same like KiRemoveEntryTimer, but additionaly, it also acquires the timer list lock. Again, the 8-bit wide Hand field is used to identify the lock of the timer list. When there was an overflow in Hand, the wrong list lock is acquired which might lead to corrupt timer list.
So, would you agree this is a bug or did I simply just overlook an important detail?
Regards,
Alexander
