Using WinDBG to Explore Round Robin Thread Context Switch for Win32 Kernel

Background:

We explored the ReactOS code for HalpClockInterrupt to get an idea of what may be involved when the kernel handles process scheduling and timer interrupts.  Now that we know the general framework of the scheduling algorithm, we are going to debug into the actual Windows XP kernel using WinDBG to view the assembly code for it and draw parallels between the assembly and the ReactOS code.

Purpose:

The purpose of this article is to more closely analyze the round robing context switch algorithm of the Win32 kernel code and determine what the initial quantum value given for a thread is. The value of a thread's quantum indicates how long the thread will run before a context switch occurs and a new thread gets scheduled.

Steps:

1. Boot up WinDBG in kernel debug mode and the Windows XP image to debug

2. Get the address of HalpClockInterrupt (!idt -a)

3. Set a hardware breakpoint at the address (ba e1 806d4d50) then continue execution until the breakpoint is hit (NOTE: your address may differ)

Command breakdown: 

b - set a breakpoint

a - hardware break point

e1 - when one byte of the address is executed

4. Now we will step through the assembly of HalpClockInterrupt as well as some of the other functions called from it while comparing the assembly to the ReactOS code

The code in the above picture creates a new stack frame for HalpClockInterrupt

5. 

Corresponds to the following code from ReactOS

6.  There is plenty of assembly code that does not seem to correspond to any code listed in ReactOS's implementation of HalpClockInterrupt. For now, we will bypass this assembly.

7. Now we can see that KeUpdateSystemTime is called from HalpClockInterrupt with its corresponding parameters.

HalpClockInterrupt

Corresponding assembly

8. The following ReactOS code checks to see if the timer has expired by comparing it to the one stored in KiTimerTableListHead which is a struct

HalpClockInterrupt

KiCheckForTimerExpiration

Corresponding assembly

9. Now the kernel code is checking to see if the debugger is enabled

KeUpdateSystemTime

In this case, the assembly does not go into the body of the if statement.

corresponding assembly

10. The next chunk of assembly skips into the end of an if body in KeUpdateSystemTime, but the main part to look at is the call to KeUpdateRunTime. This is where the quantum value of a thread is read and a context switch occurs.

KeUpdateSystemTime

Corresponding assembly code (partially)

11. Let us explore KeUpdateRunTime.

Corresponding assembly when KeUPdateRunTime is called

12. After stepping through various lines of assembly, we will come across a section that appears to resemble a piece of the KeUpdateRunTime code that is trying to determine if the thread is in an ISR. An ISR is an interrupt service routine, which is responsible for doing whatever is necessary to stop an interrupt.

KeUpdateRunTime

Assembly code

13. Following that, ReactOS code checks to see if the DPC queue is large enough. DPC (deferred procedure call) is an OS mechanism that permits high priority tasks to run ahead of low priority, but required tasks. Each deferred task is appended to a queue to be run later. In the case of the ReactOS code, it checks to see if the queue has become too large and if so, executed one of the deferred tasks.

KeUpdateRunTime

Associated assembly

14. After several more step throughs, we come across an assembly line that subtracts 3 from an offset of EBX.  I believe this memory address to be the quantum of the thread based off the code in ReactOS. When the quantum reaches 0, it will perform a context switch and a new thread will be executed.

assembly

KeUpdateRunTIme

15. If you click CLOCK_QUANTUM_DECREMENT, you will come across a file called types.c that has the following definition.

CLOCK_QUANTUM_DECREMENT is defined to have a value of 3 which corresponds to the value subtracted from that particular memory address in the previous step. The max quantum of a thread is set to 0x7F which is 127. Since, a thread has a max quantum of 127 and has 3 subtracted from it for every other tick, (127/3)*2 = 84 which is how many ticks a thread runs for.

16. Now lets find the frequency of the clock. It has the possibility of being one of two clocks, APIC or PIC. If you do a quick Google search, you may come across this page. The description of APIC Periodic Mode,  is very similar to the code we have seen in ReactOS and the corresponding assembly where the timer keeps a count and decrements it until it reaches 0. When it reaches 0, it performs a context switch and reinitializes the count.

17. HalpInitializeClock is a ReactOS function in timer.c. From this file we can see that timer frequency is 1 MHz with an interval of 10 milliseconds.

timer.c

Conclusion:

We discovered what the max quantum of a thread is (127) and each thread is allocated 84 ticks. The frequency of the APIC timer is 1 MHz so the total run time for a thread is 84/10000 = 0.0084 seconds = 8.4 milliseconds per thread.

Total Time: 10 hours