100th Blog Post - Thanks for the Support

This blog has really grown, especially during this month, it's been late nights after the pub and work and even college, just staying up and trying to write as much information as possible (whilst being concise and to the point), since I have so many ideas and topics I would like to write about.

Anyway, I hope you enjoy reading my blog so far, and I hope it's helped you understand debugging a little more, and turn that at first glance alien language of memory addresses and WinDbg commands into something more understandable.

Thanks for the support, and please keep reading my blog, and leave a comment or two, if I've made a mistake somewhere or you would like to have a certain topic added.

Kernel Stacks, User Stacks, DPC Stacks and Interrupt Stacks

Okay, in my last blog post we discussed the theory of stacks in general, mostly referring to user stacks. In this blog post, I'm going to explain the different kinds of stacks available to the operating system.

A thread consists of a user stack and a kernel stack. Firstly, we'll talk about user stacks, since these are more simple, and we've focused on these more in the last blog post.

User Stacks

We know when a thread is created, the Memory Manager reserves about 1MB of memory to the stack. We should also know that the stack isn't committed straight away, that is, the stack grows when local variables and function calls are created or called within the program. Only around 64KB of memory is initially committed to the stack. When the stack grows, and touches the Guard Page it expands, and part of the reserved region of the stack is committed to the stack. This should be a simple remainder of stacks discussed in my last blog post. Remember that user stacks will not shrink back like kernel stacks.

We can gather the stack reserved and stack committed sizes with the !dh extension, when specifying the name of a module. User stacks are only used to storage user-mode information.

Kernel Stacks

The Kernel Stack is used to store kernel-mode related information, and can only be accessed if given the privilege by the kernel, otherwise this is a protected data structure. A kernel stack is usually much smaller size, with about 12KB for the stack and 16KB if you count the size of the Guard Page, since it's excepted to have much less recursive function calls (which can cause stack overflows) and better management of local variables. Again, kernel stacks are allocated from virtual memory, and although quite uncommon can be paged out onto the disk. The stacks which are paged out, tend to be inactive stacks.

Kernel Stacks can also grow and strink in size unlike User Stacks due to a size limitation. Another oddity with kernel stacks, is that they can move in both directions essentially. When data has been removed from the stack, then the stack moves upwards, and when data is added to the stack, the stack is able to move downwards in memory.

DPC Stacks

This is assigned to a per-processor basis, and this stack is used when DPCs are executed. DPC stacks are also used to separate kernel code from DPC code, and a switch may be performed to the DPC stack when the kernel stack doesn't have enough space.

The DPC Stack can be found within the _KPRCB data structure, and the DPC Queue can be found with the !pcr extension.

Interrupt Stack

Interrupt stacks are associated on a per processor basis like DPC stacks, and are only used while the kernel is currently using that particular CPU. When a interrupt (external) happens, this can be I/O from the mouse and keyboard, then the kernel switches to the the interrupt stack, since it saves creating more space on the kernel stack with the associated thread.

Interrupt Stacks are also used to load new known good stacks from the Interrupt Stack Table (IST) when serious exceptions occur like a NMI. There is currently 7 IST entries per a CPU, and the IST uses the TSS to point to these good stacks.

References

linux - kernel stack and user space stack 

Using the Kernel Stack (Windows Drivers)

The NT Insider: Common Topics - Deferred Procedure Call Details

DPCs execute on their own call stack (x86 edition)

x86 and x64 Kernel Stacks 

Intel Developers Manual - Section 6.2

Stack Expansion

Basic Concepts:

The title could probably be called Stack Expansion or Stack Growth, depending upon how you like to name it. A thread stack is used to store information such as function parameters, function return addresses and local variables. It is allocated from virtual memory. A stack isn't committed fully straight away, instead portions of virtual memory are committed when needed, and the rest of the virtual memory allocated to the stack is reserved. Stacks have certain limits, and this how stack overflows are caused. A stack begins to use virtual memory outside of the reserved region.

 When a stack begins to grow or expand, then it will access the Guard Page. Once the Guard Page has been accessed, then the amount of committed memory to stack will grow. The diagram illustrates this point. Notice how the Reserved level of memory has reduced in size? 

 KeExpandKernelStackAndCalloutEx and KeExpandKernelStackAndCallout can be used to expand a stack. Check the WDK documentation or MSDN for more information.

Stacks typically follow the LIFO (Last In - First Out) queue algorithm. You may notice pop and push Assembly instructions being used too, push is used to insert data onto the stack, whereas, pop is used to remove data from the stack. For instance, a creation of local variable; this variable is added to the stack with a push instruction, and when the local variable is destroyed, then the pop instruction is used. Stacks do not decrease in size afterwards, once expanded they will remain that size or expand with growth.

Stack Overflows and Stack Underflows:

A stack overflow is when the stack pointer references memory outside of the reserved region, whereas, a stack underflow is when the stack pointer moves beyond the originating address of the stack.



References:

6.1 Stack Limit Checking


Pushing the Limits of Windows: Processes and Threads

Stack (abstract data type) - Wikipedia

Thread Quantum, Thread Priority Boosting and Processor Affinity

This blog post for a continuation of thread scheduling as discussed in my previous blog post, although in this blog post I'm going to explain the concept of Quantum and Boosts. These both are deciding factors for thread scheduling.

Thread Quantum

A thread quantum is the amount of time a thread is allowed to execute for, before Windows interrupts the thread and lets a different thread of the same priority level run and execute. A thread can run for another quantum, if there are no other threads at that priority level.

A thread quantum is around 2 clock intervals, and is governed by the HAL. We can check the length (in milliseconds) of a clock interval with the ClockRes program.

Threads do not run based upon clock intervals, this is translated into a the number of clock cycles in a quantum, and is stored inside the variable called KiCyclesPerQuantum. Threads run for a Target Quantum which is the the number of clock cycles passed before the thread should stop executing. The Target Quantum or Quantum Target can be found in the _KTHREAD data structure in the QuantumTarget field as seen here:

The Quantum Reset value can only be found in the same data structure. This value is used for creating new threads within the same process.

This is measured in Quantum Units, which is a third of a clock tick. A process windows which is brought to the foreground, is given a Quantum Boost, the threads within the process have their quantum targets tripled for obvious reasons.

Thread Priority Boosting

 There are six different reasons, the Kernel will increase the (boost) priority of threads. Boosts can never exceed the dynamic priority range and enter the real-time priority range. For example, a thread with a current priority of 15 will remain at 15 if it is boosted.

• I/O Operation Completion
• Executive Events and Semaphores
• Executive Resources (wait was too long)
• Foreground process threads complete a wait
• Windowing activity for a GUI thread
• CPU Starvation 

I/O Boosting:

• Boost is always applied to the current thread priority level (never base priority)

• Boost lasts for one quantum, and the priority level reduces by one for each quantum, until the base priority of that thread is met. 

Events and Semaphores Boosts:

•  Thread base priority is boosted by 1
• Thread will run at the higher priority level until the quantum ends, and then will decay (reduce by 1 each quantum) until the base priority is meet.
• Special boosts are applied to special event functions (NtSetEventBoostPriority and KeSetEventBoostPriority), or gate objects. A special boost increases the thread priority one above, the thread priority of the thread setting the event object. This only applies if the thread priority of the woken thread is below 13.

Executive Resources:

Boosts here are slightly more in depth than the other mechanisms being discussed, due to the higher risks of CPU Starvation and Deadlocks.

A thread waiting upon a executive resource, will perform a wait in 5 second intervals, this prevents CPU Starvation and Deadlocks.If the thread is still waiting, then a boost may be applied to the owner thread.

• The base priority of the owner thread is increased to 14.
• Boost is only set, if the base priority isn't already 14 and the owner thread has a lower priority than the waiting thread.
• Quantum is reset, so the thread is able to run at a boosted priority for a entire quantum, instead of the remaining quantum. The same decay rules apply here.

Depending upon if the executive resource is exclusive or shared, the owner thread will be boosted and then the other threads will be boosted. In a shared situation, the exclusive owner thread will be boosted first, and then all the shared owner threads will be boosted.

Foreground Boosts:

The current thread priority is boosted by the value of the PsPrioritySeparation.

GUI Thread Boosts:

The current priority level will be boosted by 2, when the thread calls KeSetEvent and completes a wait.

CPU Starvation:

The Balance Set Manager is used to scan the ready queues for any threads which haven't ran for 4 seconds. The Balance Set Manager check every second. If any threads haven't ran for the given time, then the Balance Set Manager boosts the current priority level to 15 (of 10 threads); if there were any remaining threads which needed boosting, then it will boost these threads on it's next scan. The Balance Set Manager also only scans 16 threads eligible for priority boost at a time, to ensure this process is quick and doesn't cause further delays. If there were 20 ready threads, then the Balance Set Manager will scan the remaining 4 on it's next scan.

Processor Affinity

The affinity mask is which processor a thread is allowed to run on, and is inherited from the process affinity. At first, the affinity mask is set to all the available processors, and the thread is able to run on any processor of it's choosing. However, this can be changed, with the SetThreadAffinityMask function (set for individual thread) and the the SetProcessAffinityMask (set for all threads for a process).

 Here, the affinity mask is set to 3, even though my system only has two processors, therefore I assume that if the affinity mask number is set to a non-existent processor number, then the affinity mask is set to all available processors.

Here the same concept stands, the Affinity Mask seems to be set to 6. Unless, the Group is the affinity mask for the thread, which would make more sense since the thread is currently running on processor 0.

Thread Scheduling and Priority Levels

The next few posts, or maybe this post if it doesn't get too large, will concern the matter of thread scheduling and priority levels. It will support perfectly the topic of interrupts and synchronization mechanisms which I've explained in the past.

Priority Levels

Each thread has it's own priority level and thread state. There are currently 32 different thread priority levels, which range from 0 to 32. The higher the priority, the more likely it is to run before any lower priority threads. You will need to also consider the concept of a Quantum, a Quantum is the amount of time a thread is allowed to run, before a thread of the same priority is scheduled to run. This system prevents errors like hangs and deadlocks. Remember higher priority threads can still interrupt lower priority threads, they take no consideration of a thread's quantum.

The priority levels we are most interested in, are the variable or dynamic levels (1-15), since these are mapped for the use by the Windows API.  The Windows API has 5 different priority classes: High (11 to 15), Above Normal (8 to 12), Normal (6 to 10), Below Normal (4 to 8) and Idle (2 to 6).

A process has a base priority level, which sets the starting priority of a thread, which in turn has base and current priority. The current priority decides if it can preempt another thread of a lower priority. Remember that when a thread is interrupted, a context switch is formed.

If we open Process Explorer, and then view the Threads tab of the Properties form of a process, then we can see the Base Priority, Dynamic Priority and Ideal Processor for a thread. Here, the Base Priority is 8, the Base Priority for non-system processes is always the middle (median) of a Win32 API priority class. The Dynamic Priority is the current priority of the thread, and the Ideal Processor is the processor number in which the thread would like to run on.

Although I haven't marked in it in the screenshot, we can see the Thread State which is Waiting.

IRQL Levels and Thread Priorities are also mapped together, typically the thread priority levels are between IRQL Level 0 and Level 1. This is stop threads from having higher priority over device interrupts and thread dispatching mechanisms. 

Thread States

There are 9 different thread states. The thread state of a thread can be found in Process Explorer, like in the above example, or it can also be found in WinDbg with the !thread extension.

 We can see that the thread is currently Running, this means the thread is currently executing code. The kind of function calls are evident within the call stack of the thread. Let's explain the other thread states, and how we can investigate these thread states in the WinDbg.

Ready: These threads are waiting and ready to execute, only these waiting threads are considered suitable to run by the dispatcher. We can view all the threads in the Ready state with the !ready extension.

Currently, there are no threads in the Ready state, however, if there were threads in the Ready state, they would be organized by processor number and then decreasing thread priority level. There are a few flags you can use with this extension, but I will not mention those here. Check the WinDbg documentation.

Deferred Ready:

Similar to ready, but the threads have been scheduled to run on a specific processor.

Standby:

A thread has been scheduled to run next on a specific processor. Only one thread per processor can exist in this state, and these types of threads can be preempted by higher priority threads.

Running:

As explained before, these are threads which are currently executing code. We can view the currently Running threads with the !running extension. The -ti flags have been added, since i adds idle processors and t adds a call stack for each thread.

The 16 characters highlighted in blue, indicate if the thread currently has any queued spinlocks (explained previously). O indicates that the processor is currently holding a queued spinlock, whereas, W indicates the processor is waiting to obtain a queued spinlock. This same information can be found in the _KPRCB data structure in the LockQueue field.

Waiting: A thread is in a wait state, which can be for a few different reasons: waiting upon a object for synchronization, I/O and paging or a subsystem has placed the thread into a wait state.

Gate Waiting: A thread is waiting upon a Gate dispatcher object (explained previously).

Transition: The thread is in the ready state, but it's kernel stack isn't currently in memory (it's paged out). A kernel stack is essentially the same as a user stack, but it has access to privileged areas of memory. There is a few pages of a stack in the Intel Manual in Chapter 6 Section 2.

Terminated: A thread has finished executing, the ETHREAD data structure from this point (non-paged pool), may or may not be deallocated depending upon the Object Manager's policy for this.

Initialised: A thread is being created (internal use only).

xrstor Instruction - Access Violations and General Protection Faults

I've seen this instruction cause problems quite frequently in the past, but I was still very new debugging then, and didn't know exactly what it was.

The instruction isn't easy to find with a Google search, you'll have to download the Intel Developer's Manual, if you haven't done so, then there is a copy available on my SkyDrive.

By looking at the parameters, we can see the type of exception which has happened is a Access Violation and the address of the instruction which caused the exception points to the xrstor instruction.

This is also a x64 operating system, and thereby will have a x64 processor. We can see this in the dump file with the vertarget command.

Now. let's dump the context switch and the exception.

The call stack didn't reveal to me, apart from exception handling routines. The raw stack did in fact reveal a AMD/ATI graphics card driver.

 Okay, we now have a possible candidate of why the instruction may have been used incorrectly. However, I haven't got to the point of why or how the instruction could have possibly caused the exception.

Reading through the Intel documentation, there a few reasons why the instruction can cause a General Protection Fault (read from Page 1631), but I'm going to keep this blog post to the point and show my theory of what happened.

Firstly, the xrstor instruction is used to restore a processor from a certain state, the four main processor states are from C0 to C3.

• C0 - Normal operating state
• C1 - Halt, the processor isn't executing any instructions, the privileged HLT instruction can be used to halt the processor and force it to wait for the next interrupt. The Core clock is also off here.
• C2 - Stop Clock, this is a form of standby state, whereby the processor may take longer to wake. Core and Bus clocks are off.
• C3 - Deep Sleep, clock generator is off. There is further variations of these sleep states for certain processors.

There is also processor extended states, but you will need to check the Intel documentation for this. I haven't personally checked, but Chapter 14, Section 2 seems to be the most relevant. The state information is read from a memory address specified. In this case, I believe it's the rcx register.

So, my main assumption is the memory address was not aligned to a 64-byte boundary (applies to 64-bit and 32-bit modes), leading to a access violation. 

References:

Processors - Deep and Deeper Sleep States 

Windows Data Alignment - x86 and x64

Data Alignment - Straighten Up and Fly Right

ACPI - Wikipedia


 

Debugging Stop 0x7A - KERNEL_DATA_INPAGE_ERROR

Overview:

This bugcheck largely concerns the storage stack and the hard-drive or file system. I'm going to explain the aspects of the storage stack and the file system, and also a particular error message which a user has just had. I'm also currently downloading a 'real situation' Kernel Memory dump which is hopefully a Stop 0x7A, so this post may be edited later too.

With these kind of bugchecks, you'll be lucky to have a dump file saved as a result of the nature of the problem. I'm just going to explain how it's caused and some of the methods we can be used to troubleshoot the problem. Generally, this bugcheck is caused by a serious virus infection or failing HDD/SSD and/or a corrupted filesystem.

In a single sentence, the kernel wasn't able to page data from the page file stored on the hard-drive back into physical memory, as a result of a problem with the storage stack. 

Storage Stack:

 The above diagram illustrates how the storage stack looks and what it consists of, note that storage stack is a layer of drivers. The Partition Manager and Volume Manager both have drivers related to them, which are partmgr.sys and volmgr.sys.

Let's speak about the different types of driver, we have in the lower half of the storage stack, and whereby the problem is most likely to arise from:

• Class: These types of drivers conform to the standards set by Windows, and and help implement I/O processing for a particular type of device, in this case it supports I/O processing for hard disks. The Class driver can support a wide range of different manufacturers. Disk.sys is a example of a Class driver.
• Port: This drivers are written by Microsoft since the driver documentation for these, this is not freely available, therefore you will not find any of the routines used by these drivers on any official Microsoft sites. The I/O Request here is specific to that type of port. Ataport.sys is a example here. Port drivers are more a .DLL, since they provide support functions for Miniport developers, in order to avoid bugs and to allow to focus on more of the hardware logic.
• Miniport: These drivers are produced by third-party developers, and use the functions provided by the Port driver. These drivers help send the I/O Request to a specific port or adapter.

 A problem can happen anywhere on the storage stack, which leads to the bugcheck we're speaking about in this blog post. However, in order to work out where the problem with the storage stack had happened, we need to gather some more information. Parameter 2 is of greatest interest, since it provides a I/O error, these can be found on the MSDN page for Stop 0x7A.

Master File Table:

The user reported a message indicating that the MFT was corrupt and couldn't be read. This leads me to believe the problem found in the storage stack is related to the file system. Let's investigate further into what is the purpose of the MFT and it's general structure.

The Master File Table maintains and tracks all the files on our hard disks, including itself. It maintains information about the file attributes, file size, date of creation and even data content. The MFT grows in size as more entries (and files are created), however, bear in mind that this space is not deallocated from the MFT, instead the old MFT entries are left empty and can be reused. Each volume has a MFT, and the space which is allocated for the MFT by the System is called the MFT Zone.

References:

NTFS Master File Table (MFT) 

Master File Table (Windows)

NTFS - Wikipedia