Exploration of Windows CPU Scheduling Algorithm by Kernel Debugging using WinDBG

Background:

When an OS snapshot is loaded into the Qemu emulator for analysis, it takes an increasing amount of time for the snapshot to load based on how long ago it is taken. In order to fix this problem within Qemu, it is vital to understand how the Windows XP kernel handles process scheduling and timer interrupts.

Purpose:

To understand the Windows kernel code for process scheduling and handling timer interrupts.

Steps:

1. Start WinDBG on your machine and start kernel debug (File --> Kernel Debug --> OK)

Make sure your COM settings match those in the picture

2. Start your Windows XP virtual machine and WinDBG should display something similar to the following picture

******************
NOTE: If you see something similar to the below picture, follow these steps from Microsoft:

Using the Microsoft Symbol Server with WinDbg

To use the Symbol Server Web site from within WinDbg, follow these steps:

1. Start the Windows Debugger (WinDbg.exe).
2. On the File menu, click Symbol File Path.
3. In the Symbol path box, type the following command:
   SRV*your local folder for symbols*http://msdl.microsoft.com/download/symbols
   where your local folder for symbols is the folder in which you copy your local symbol cache. The debug symbols are downloaded to this location.
   
   Note You can point to any local path or share that your computer can reach; it does not have to be a location on the computer's hard disk.

Alternatively, you can also use the .sympath command at a command prompt to set the symbol path.

After the symbols are downloaded, each time after you use WinDBG you will need to click on File --> Symbol File Path then paste (or browse) the path where the symbols were downloaded to and press OK before you start to debug your Windows virtual machine

******************

3. Lets send an interrupt to the target machine (Windows XP virtual machine) so that we will be able to analyze some of the current system conditions (Debug --> Break)

And WinDBG should display something similar to the following:

The box circled in yellow is where we can input WinDBG commands

4. Type the WinDBG command "!idt -a" which will display all the interrupts

5. Once all the interrupts are displayed, lets search for one that may handle any timer interrupts

HalpClockInterrupt handles timer interrupts and process scheduling

6. Now that we have seen what interrupts are currently active on the system and found the one related to timer interrupts, let us review the C code for it.

We are going to use ReactOS to look at the code for HalpClockInterrupt. This is an open source site that has code derived from the Windows NT architecture.

As you can see, the code for HalpClockInterrupt clears the interrupt, and updates the kernel's system time. Lets take a closer look at each line of the function:

NOTE: if you go to the site yourself, you will be able to click on the links to see where certain functions/macros are defined and given values

Line 1 (33): ASSERT(KeGetCurrentIrql() == CLOCK2_LEVEL);

• CLOCK2_LEVEL:
• Defined: armddk.h
• Type: Macro
• Value: 28
•  Meaning: Not known at this time
• KeGetCurrentIrql():
• Defined: keytypes.h
• Type: Macro (function)
• Value: PCR->Irql
• Functionality:
• Gets the current Irql (Interrupt ReQuest Level) for the kernel
• PCR (process control region) is a macro that contains an address (KIPOPCRADDRESS = 0xffdff000)
• Irql is of type PKIRQL which is a pointer to an unsigned char which helps specify a kernel type
• PCR->Irql gets the interrupt request level of the current process
• ASSERT():
• Defined: mode.c
• Type: Macro (function)
• Parameter: an unsigned char type defined as a GLboolean
• Functionality:
• Gets the value of the result from the passed in conditional statement
•  Line Summary:
• Used to help clear the interrupt and gives ASSERT a value based on the above conditional statement

Line 2 (34): WRITE_REGISTER_ULONG(TIMER0_INT_CLEAR, 1);

• TIMER0_INT_CLEAR:
• Defined: sp804.h
• Type: Macro
• Value: TIMER_BASE(0) + 0x0C
• Meaning:
• Sets (clears) the clock value by passing a 0 to TIMER_BASE and then adds 0x0C (12) to the result of TIMER_BASE which is an address (0x101E2000)
• WRITE_REGISTER_ULONG(r, v):
• Defined: bootvid.c
• Type: Macro (function)
• Parameters: GLboolean r, GLboolean v
• Functionality:
• Sets the value of r equal to value of v (1)
• Line Summary:
• Used to help clear the interrupt and set the value of a register

·    

Line 3 (41): KeUpdateSystemTime(KeGetCurrentThread()->TrapFrame, HalpCurrentTimeIncrement,CLOCK2_LEVEL);

• KeGetCurrentThread()->TrapFrame:
• Defined: hal.h
• Type: Macro
• Value: _KeGetCurrentThread (macro function that grabs the current thread)
• Meaning:
• Obtains the thread currently being executed and its associated trap frame
• HalpCurrentTimeIncrement:
• Defined: timer.c
• Type: ULONG (variable)
• Value:  Not known at this time
• Meaning: Not known at this time
• CLOCK2_LEVEL:
• Defined: armddk.h
• Type: Macro
• Value: 28
• Meaning: Not known at this time
• KeUpdateSystemTime():
• Defined: time.c
• Type: Function
• Parameters: trap frame (PKTRAP_FRAME), Increment (ULONG), OldIrql (KIRQL)
• Functionality:
• Updates the system time
• Checks to see if the current tick is being skipped and if so marks it so that it gets handled next time
• Updates the interrupt timer and global time keeping data
• Checks to see if the timer expired
• Updates all tick data if the current tick is a full tick and less than or equal o the old tick
• KeUpdateRunTime(IN PKTRAP_FRAME TrapFrame, IN KIRQL Irql)
• Called within KeUpdateSystemTime()
• Defined: time.c
• Type: Function
• Parameters: PKTRAP_FRAME, KIRQL
• Functionality:
• Obtains the current running thread and PRCB (process region control block) 
• The PRCB is a struct that contains information about the processor
• Checks if the processor is skipping this current tick
•  If the tick is being skipped, the function will return
• Increases the interrupt count
• Checks to see if the process is in user mode or kernel mode
• If the process came from user mode, it increases the process’s user time which increments how much time the current process has spent in user mode
• If the process did not come from user mode (it came from kernel mode)
• Increments the amount of time it spent in kernel mode
• Increments the process’s interrupt time, kernel time, or DPC time (the amount of time the process has been on the Deferred Procedure Call queue) based on the value of DISPATCH_LEVEL (which is a macro defined in ksx.template.h) when being compared to the passed in value for IRQL
• DPC is part of the Windows OS that allows high priority tasks to defer lower priority, but still required, tasks for later execution
• Updates the DPC rates
• Checks to see if the DPC queue is large enough
• Adjusts the maximum depth of the DPC queue
• Decrements the thread quantum (Thread->Quantum)
• Thread Quantum is a global variable that keeps track of how long the current process has left before the CPU jumps to the next process
• When the thread quantum reaches 0, the CPU has to perform a context switch to another process
• Checks to see if a context switch needs to occur
• If a context switch occurs:
• Sets the value of Prcb->QuantumEnd to 1 (true)
• Calls the function HalRequestSoftwareInterrupt and passes the DISPATCH_LEVEL to it
• HalRequestSoftwareInterrupt(KIRQL Irql)
• Called within KeUpdateRunTime()
• Defined: pic.c
• Type: Function
• Parameters: KIRQL (the interrupt request level)
• Functionality:
• forces a software interrupt by overwriting the value of a register
• Line Summary:
• Obtains the current process and updates the internal structures in order to trigger a context switch

Summary:

The HalpClockInterrupt function updates the systems kernel level clock and clears previous interrupts and registers. It also alerts the CPU to when a context switch needs to occur based on the value of the process's thread quantum. Once the quantum is given a value of 0, a context switch occurs and the CPU will execute a different process. 

Total Hours: 8