WinDbg : Parsing Dispatcher Object Queues & the !exqueue Command Extension

WinDbg : Parsing Dispatcher Object Queues & the !exqueue Command Extension

Windows maintains several differ net work queues for different objects. Depending on the priority of the object it is pushed into the respective queue. The !exqueue command can be used to view the different queues and the threads which are part of it.

kd> !exqueue

**** Critical WorkQueue ( Threads: 6/512, Concurrency: 0/1 )

THREAD 83a379e8  Cid 0004.0018  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a37710  Cid 0004.001c  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a37438  Cid 0004.0020  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a37160  Cid 0004.0024  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a25020  Cid 0004.0028  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 84fedd48  Cid 0004.0750  Teb: 00000000 Win32Thread: 00000000 WAIT

**** Delayed WorkQueue ( Threads: 7/512, Concurrency: 0/1 )

THREAD 83a25d48  Cid 0004.002c  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a25a70  Cid 0004.0030  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a25798  Cid 0004.0034  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a254c0  Cid 0004.0038  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a26020  Cid 0004.003c  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a26d48  Cid 0004.0040  Teb: 00000000 Win32Thread: 00000000 WAIT

THREAD 83a26a70  Cid 0004.0044  Teb: 00000000 Win32Thread: 00000000 WAIT

**** HyperCritical WorkQueue ( Threads: 1/512, Concurrency: 0/1 )

THREAD 83a26798  Cid 0004.0048  Teb: 00000000 Win32Thread: 00000000 WAIT

To parse the list of waiting threads on an object, first find the queue type of object (it is easier with that, else use any process in your mind, but then those might not have waiters). 

In this example we are using _EPROCESS but the command !exqueue, shown above, will give a list of all executable queues, and also can be used to chose one such queue with multiple waiters.

NOTE : To run this experiment in a better fashion on process type objects, we should create a process and make another process open a handle on it and wait on it (WaitForSingleObject). An example is the Winlogon process which has multiple waiters if multiple sessions are running.

kd> !process 0 0 lsass.exe

PROCESS 848b0720  SessionId: 0  Cid: 0200    Peb: 7ffd8000  ParentCid: 018c

    DirBase: 1ee780e0  ObjectTable: 8781e0e8  HandleCount: 560.

    Image: lsass.exe

kd> dt nt!_EPROCESS 848b0720  Pcb.Header.

   +0x000 Pcb         : 

      +0x000 Header      : 

         +0x000 Type        : 0x3 ''

         +0x001 TimerControlFlags : 0 ''

         +0x001 Absolute    : 0y0

         +0x001 Coalescable : 0y0

         +0x001 KeepShifting : 0y0

         +0x001 EncodedTolerableDelay : 0y00000 (0)

         +0x001 Abandoned   : 0 ''

         +0x001 Signalling  : 0 ''

         +0x002 ThreadControlFlags : 0x26 '&'

         +0x002 CpuThrottled : 0y0

         +0x002 CycleProfiling : 0y1

         +0x002 CounterProfiling : 0y1

         +0x002 Reserved    : 0y00100 (0x4)

         +0x002 Hand        : 0x26 '&'

         +0x002 Size        : 0x26 '&'

         +0x003 TimerMiscFlags : 0 ''

         +0x003 Index       : 0y0

         +0x003 Processor   : 0y00000 (0)

         +0x003 Inserted    : 0y0

         +0x003 Expired     : 0y0

         +0x003 DebugActive : 0 ''

         +0x003 ActiveDR7   : 0y0

         +0x003 Instrumented : 0y0

         +0x003 Reserved2   : 0y0000

         +0x003 UmsScheduled : 0y0

         +0x003 UmsPrimary  : 0y0

         +0x003 DpcActive   : 0 ''

         +0x000 Lock        : 0n2490371

         +0x004 SignalState : 0n0

         +0x008 WaitListHead : _LIST_ENTRY [ 0x84fda4b0 - 0x83b39d20 ]

Now, the WaitListhead is actually of type KWAIT_BLOCK with the first element as LIST_ENTRY, so...

kd> dt nt!_KWAIT_BLOCK 0x84fda4b0 

   +0x000 WaitListEntry    : _LIST_ENTRY [ 0x83b39d20 - 0x848b0728 ]

   +0x008 Thread           : 0x84f9caf8 _KTHREAD

   +0x00c Object           : 0x848b0720 Void

   +0x010 NextWaitBlock    : 0x84fda4c8 _KWAIT_BLOCK

   +0x014 WaitKey          : 0x10

   +0x016 WaitType         : 0x1 ''

   +0x017 BlockState       : 0x2 ''

To parse the list of threads waiting, we use the inbuilt ability of the dt command to parse lists. To read more about this, please refer to this blog post.

kd> dt nt!_KWAIT_BLOCK 0x84fda4b0 -l WaitlistEntry.Flink -y Thread

WaitlistEntry.Flink at 0x84fda4b0

---------------------------------------------

   +0x000 WaitListEntry :  [ 0x83b39d20 - 0x848b0728 ]

   +0x008 Thread : 0x84f9caf8 _KTHREAD

WaitlistEntry.Flink at 0x83b39d20

---------------------------------------------

   +0x000 WaitListEntry :  [ 0x848b0728 - 0x84fda4b0 ]

   +0x008 Thread : 0x848e5430 _KTHREAD

WinDbg : The Difference Between The Dot (.) & The Arrow (->) In The dt Command

WinDbg : The Difference Between The Dot (.) & The Arrow (->) In The dt Command 

Commands used:

1. dt
2. Pseudo Registers
3. $

We have seen that the dot (.) after the name of a structure member name will make the dt command expand the sub-structure. 

kd> dt nt!_EPROCESS pcb.

   +0x000 Pcb  : 

      +0x000 Header : _DISPATCHER_HEADER

      +0x010 ProfileListHead : _LIST_ENTRY

      +0x018 DirectoryTableBase : Uint4B

<Output Snipped to Save Space>

The same seem to be achieved with the arrow (->) as well.

kd> dt nt!_EPROCESS pcb->*

   +0x000 Pcb   : 

      +0x000 Header : _DISPATCHER_HEADER

      +0x010 ProfileListHead : _LIST_ENTRY

      +0x018 DirectoryTableBase : Uint4B

<Output Snipped to Save Space>

So The question arises what then is the difference, if at all between these. Well, on the first level a single . is equivalent to ->*. The differences arise with multiple levels.

. (dot) will recursively expand structures within structures and can be used like ...... (dot dot dot dot). Four dots in a row will expand till the 4th level nested structure, while -> will deference a pointer and you may need a name for it. 

In the below examples we will be using the pseudo register $Proc. To learn more about pseudo registers, please read this post.

lkd> $nodot

lkd> dt nt!_EPROCESS @$proc -y pc.H

   +0x000 Pcb  :

      +0x000 Header : _DISPATCHER_HEADER

lkd> $single dot

lkd> dt nt!_EPROCESS @$proc -y pc.H.

   +0x000 Pcb   :

      +0x000 Header :

         +0x000 Type  : 0x3 ''

         +0x001 Absolute : 0 ''

         +0x002 Size  : 0x1b ''

         +0x003 Inserted : 0 ''

         +0x004 SignalState : 0n0

         +0x008 WaitListHead : _LIST_ENTRY [ 0x866dd6d0 - 0x866dd6d0 ]

lkd> $single dot is equivalent to ->*

lkd> dt nt!_EPROCESS @$proc -y pc.H->*

   +0x000 Pcb    :

      +0x000 Header :

         +0x000 Type   : 0x3 ''

         +0x001 Absolute : 0 ''

         +0x002 Size   : 0x1b ''

         +0x003 Inserted : 0 ''

         +0x004 SignalState : 0n0

         +0x008 WaitListHead : _LIST_ENTRY [ 0x866dd6d0 - 0x866dd6d0 ]

lkd> $double dot will expand _list_entry

lkd> dt nt!_EPROCESS @$proc -y pc.H..

   +0x000 Pcb    :

      +0x000 Header :

         +0x000 Type   : 0x3 ''

         +0x001 Absolute : 0 ''

         +0x002 Size   : 0x1b ''

         +0x003 Inserted : 0 ''

         +0x004 SignalState : 0n0

         +0x008 WaitListHead :  [ 0x866dd6d0 - 0x866dd6d0 ]

            +0x000 Flink  : 0x866dd6d0 _LIST_ENTRY [ 0x866dd6d0 - 0x866dd6d0 ]

            +0x004 Blink  : 0x866dd6d0 _LIST_ENTRY [ 0x866dd6d0 - 0x866dd6d0 ]

lkd> dt nt!_EPROCESS @$proc -y pc.H->W.

   +0x000 Pcb      :

      +0x000 Header   :

         +0x008 WaitListHead :  [ 0x866dd6d0 - 0x866dd6d0 ]

            +0x000 Flink    : 0x866dd6d0 _LIST_ENTRY [ 0x866dd6d0 - 0x866dd6d0 ]

            +0x004 Blink    : 0x866dd6d0 _LIST_ENTRY [ 0x866dd6d0 - 0x866dd6d0 ]

lkd> dt nt!_EPROCESS @$proc -y pc.H->W->*

   +0x000 Pcb       :

      +0x000 Header    :

         +0x008 WaitListHead :  [ 0x866dd6d0 - 0x866dd6d0 ]

            +0x000 Flink     : 0x866dd6d0 _LIST_ENTRY [ 0x866dd6d0 -

0x866dd6d0 ]

            +0x004 Blink     : 0x866dd6d0 _LIST_ENTRY [ 0x866dd6d0 -

0x866dd6d0 ]

lkd> dt nt!_EPROCESS @$proc -y pc.H->W..

   +0x000 Pcb       :

      +0x000 Header    :

         +0x008 WaitListHead :  [ 0x866dd6d0 - 0x866dd6d0 ]

            +0x000 Flink     :

            +0x004 Blink     :

Cannot find specified field members

WinDbg : An Introduction To Windows Heaps

WinDbg : An Introduction To Windows Heaps 

1. dt
2. dd
3. !process
4. .process
5. $ 

Heaps are used by applications which need to allocate and release memory dynamically. Even though the heap is the most common facility to accommodate dynamic memory allocations, it is not the only way. Several other methods are available:

• Memory can be requested through the C run time (CRT).
• The virtual memory manager or some other private memory manager.

Even though these methods are different, they are tightly coupled internally at the memory manager's level.

When a process starts, the heap manager automatically creates a new heap called the 'default process heap'. Although some processes are known to use the default heap, a very very large number rely on the CRT heap (using malloc/free family of APIs, or the default new/delete family of APIs).

Some processes however also create additional heaps (via HeapCreate(...) ). this method has advantage of isolating different components running in the process. Thus memory leaks can be easier to detect and debug, if we know exactly which heap is leaking. It is indeed good programming practice. Kernel programmers are used to using different tags for allocating memory for different objects, this method described above is the usermode solution to the problem.

The Windows heap manager has two sub components. 

• Front End Allocator.
• Back End Allocator.

The Front End Allocator is an optimization layer for the actual Back End Allocator. Thus, by choosing different front end allocators applications with differnt memory requirements can function appropriately. Example, some programs might expect small bursts of allocations, and thus might prefer to use a low fragmentation front end allocator. 

Windows supplies two different front end allocators:

• Low fragmentation (LF) Front End Allocator.
• Look aside List (LAL) Front End Allocator.

Vista and above use the LF allocator by default, where as all older generations use the LAL allocator. The differences between these allocators re beyond the scope of the current discussion.

If the Front End Allocator is unable to satisfy the allocation requests, then the Back End Allocator takes over. It is made up of free lists. Each list has blocks of specific sizes. Such free blocks are sorted in ascending order of sizes. Again, a more elaborate discussion on how this is managed, or of it's algorithms is beyond the scope of this current article.

Enough theory, lets get into some practicals.

The first step for us is to determine which all heaps are active for a process.

kd> $ Lets use the lsass process as an example.

kd> $ First we need to find it's EPROCESS

kd> !process 0 0 lsass.exe

PROCESS 84cdc860  SessionId: 0  Cid: 0208    Peb: 7ffda000  ParentCid: 018c

    DirBase: 1eed30e0  ObjectTable: 95f00d18  HandleCount: 513.

    Image: lsass.exe

kd> $ Next we need to switch contexts to this process (this is because this session is running from Kernel mode)

kd> .process /p /r 84cdc860  

Implicit process is now 84cdc860

Loading User Symbols

............................................................

kd> $ The Process execution block (_PEB) helps us with finding the active heaps, so lets use dt to find it

kd> dt _PEB @$peb

ntdll!_PEB

   +0x000 InheritedAddressSpace : 0 ''

   +0x001 ReadImageFileExecOptions : 0 ''

   +0x002 BeingDebugged    : 0 ''

   +0x003 BitField         : 0x8 ''

   +0x003 ImageUsesLargePages : 0y0

   +0x003 IsProtectedProcess : 0y0

   +0x003 IsLegacyProcess  : 0y0

   +0x003 IsImageDynamicallyRelocated : 0y1

   +0x003 SkipPatchingUser32Forwarders : 0y0

   +0x003 SpareBits        : 0y000

   +0x004 Mutant           : 0xffffffff Void

   +0x008 ImageBaseAddress : 0x00d90000 Void

   +0x00c Ldr              : 0x77c77880 _PEB_LDR_DATA

   +0x010 ProcessParameters : 0x00330f18 _RTL_USER_PROCESS_PARAMETERS

   +0x014 SubSystemData    : (null) 

   +0x018 ProcessHeap      : 0x00330000 Void

   +0x01c FastPebLock      : 0x77c77380 _RTL_CRITICAL_SECTION

   +0x020 AtlThunkSListPtr : (null) 

   +0x024 IFEOKey          : (null) 

   +0x028 CrossProcessFlags : 0

   +0x028 ProcessInJob     : 0y0

   +0x028 ProcessInitializing : 0y0

   +0x028 ProcessUsingVEH  : 0y0

   +0x028 ProcessUsingVCH  : 0y0

   +0x028 ProcessUsingFTH  : 0y0

   +0x028 ReservedBits0    : 0y000000000000000000000000000 (0)

   +0x02c KernelCallbackTable : 0x7790d568 Void

   +0x02c UserSharedInfoPtr : 0x7790d568 Void

   +0x030 SystemReserved   : [1] 0

   +0x034 AtlThunkSListPtr32 : 0

   +0x038 ApiSetMap        : 0x77de0000 Void

   +0x03c TlsExpansionCounter : 0

   +0x040 TlsBitmap        : 0x77c77260 Void

   +0x044 TlsBitmapBits    : [2] 0x1fffff

   +0x04c ReadOnlySharedMemoryBase : 0x7f6f0000 Void

   +0x050 HotpatchInformation : (null) 

   +0x054 ReadOnlyStaticServerData : 0x7f6f0590  -> (null) 

   +0x058 AnsiCodePageData : 0x7ffb0000 Void

   +0x05c OemCodePageData  : 0x7ffc0224 Void

   +0x060 UnicodeCaseTableData : 0x7ffd0648 Void

   +0x064 NumberOfProcessors : 1

   +0x068 NtGlobalFlag     : 0

   +0x070 CriticalSectionTimeout : _LARGE_INTEGER 0xffffe86d`079b8000

   +0x078 HeapSegmentReserve : 0x100000

   +0x07c HeapSegmentCommit : 0x2000

   +0x080 HeapDeCommitTotalFreeThreshold : 0x10000

   +0x084 HeapDeCommitFreeBlockThreshold : 0x1000

   +0x088 NumberOfHeaps    : 4

   +0x08c MaximumNumberOfHeaps : 0x10

   +0x090 ProcessHeaps     : 0x77c77500  -> 0x00330000 Void

   +0x094 GdiSharedHandleTable : 0x004d0000 Void

   +0x098 ProcessStarterHelper : (null) 

   +0x09c GdiDCAttributeList : 0x14

   +0x0a0 LoaderLock       : 0x77c77340 _RTL_CRITICAL_SECTION

   +0x0a4 OSMajorVersion   : 6

   +0x0a8 OSMinorVersion   : 1

   +0x0ac OSBuildNumber    : 0x1db1

   +0x0ae OSCSDVersion     : 0x100

   +0x0b0 OSPlatformId     : 2

   +0x0b4 ImageSubsystem   : 2

   +0x0b8 ImageSubsystemMajorVersion : 6

   +0x0bc ImageSubsystemMinorVersion : 1

   +0x0c0 ActiveProcessAffinityMask : 1

   +0x0c4 GdiHandleBuffer  : [34] 0

   +0x14c PostProcessInitRoutine : (null) 

   +0x150 TlsExpansionBitmap : 0x77c77268 Void

   +0x154 TlsExpansionBitmapBits : [32] 1

   +0x1d4 SessionId        : 0

   +0x1d8 AppCompatFlags   : _ULARGE_INTEGER 0x0

   +0x1e0 AppCompatFlagsUser : _ULARGE_INTEGER 0x0

   +0x1e8 pShimData        : (null) 

   +0x1ec AppCompatInfo    : (null) 

   +0x1f0 CSDVersion       : _UNICODE_STRING "Service Pack 1"

   +0x1f8 ActivationContextData : 0x00040000 _ACTIVATION_CONTEXT_DATA

   +0x1fc ProcessAssemblyStorageMap : (null) 

   +0x200 SystemDefaultActivationContextData : 0x00030000 _ACTIVATION_CONTEXT_DATA

   +0x204 SystemAssemblyStorageMap : (null) 

   +0x208 MinimumStackCommit : 0

   +0x20c FlsCallback      : 0x0033daa0 _FLS_CALLBACK_INFO

   +0x210 FlsListHead      : _LIST_ENTRY [ 0x347828 - 0x3cb680 ]

   +0x218 FlsBitmap        : 0x77c77270 Void

   +0x21c FlsBitmapBits    : [4] 7

   +0x22c FlsHighIndex     : 2

   +0x230 WerRegistrationData : (null) 

   +0x234 WerShipAssertPtr : (null) 

   +0x238 pContextData     : 0x00050000 Void

   +0x23c pImageHeaderHash : (null) 

   +0x240 TracingFlags     : 0

   +0x240 HeapTracingEnabled : 0y0

   +0x240 CritSecTracingEnabled : 0y0

   +0x240 SpareTracingBits : 0y000000000000000000000000000000 (0)

kd> $ Now lets use dd to see what this address contains

kd> dd 0x77c77500  

77c77500  00330000 00010000 00250000 00d10000

77c77510  00000000 00000000 00000000 00000000

77c77520  00000000 00000000 00000000 00000000

77c77530  00000000 00000000 00000000 00000000

77c77540  00000000 77c77340 77c7ab08 77c77220

77c77550  00000000 00000004 00000000 00000000

77c77560  77c77220 003e3198 00000000 00000000

77c77570  00000000 00000000 00000000 00000000

The Default Process heap pointer is always the first one in this list. Since most applications work with the default heap, we will focus our attention on that.

The _HEAP structure in Windows is used to maintain a heap. So lets typecast this address to it.

kd> dt _HEAP 0x00330000

ntdll!_HEAP

   +0x000 Entry            : _HEAP_ENTRY

   +0x008 SegmentSignature : 0xffeeffee

   +0x00c SegmentFlags     : 0

   +0x010 SegmentListEntry : _LIST_ENTRY [ 0x3300a8 - 0x3300a8 ]

   +0x018 Heap             : 0x00330000 _HEAP

   +0x01c BaseAddress      : 0x00330000 Void

   +0x020 NumberOfPages    : 0x100

   +0x024 FirstEntry       : 0x00330588 _HEAP_ENTRY

   +0x028 LastValidEntry   : 0x00430000 _HEAP_ENTRY

   +0x02c NumberOfUnCommittedPages : 0x47

   +0x030 NumberOfUnCommittedRanges : 1

   +0x034 SegmentAllocatorBackTraceIndex : 0

   +0x036 Reserved         : 0

   +0x038 UCRSegmentList   : _LIST_ENTRY [ 0x3e8ff0 - 0x3e8ff0 ]

   +0x040 Flags            : 2

   +0x044 ForceFlags       : 0

   +0x048 CompatibilityFlags : 0

   +0x04c EncodeFlagMask   : 0x100000

   +0x050 Encoding         : _HEAP_ENTRY

   +0x058 PointerKey       : 0x37d910ba

   +0x05c Interceptor      : 0

   +0x060 VirtualMemoryThreshold : 0xfe00

   +0x064 Signature        : 0xeeffeeff

   +0x068 SegmentReserve   : 0x100000

   +0x06c SegmentCommit    : 0x2000

   +0x070 DeCommitFreeBlockThreshold : 0x800

   +0x074 DeCommitTotalFreeThreshold : 0x2000

   +0x078 TotalFreeSize    : 0xac0

   +0x07c MaximumAllocationSize : 0x7ffdefff

   +0x080 ProcessHeapsListIndex : 1

   +0x082 HeaderValidateLength : 0x138

   +0x084 HeaderValidateCopy : (null) 

   +0x088 NextAvailableTagIndex : 0

   +0x08a MaximumTagIndex  : 0

   +0x08c TagEntries       : (null) 

   +0x090 UCRList          : _LIST_ENTRY [ 0x3e8fe8 - 0x3e8fe8 ]

   +0x098 AlignRound       : 0xf

   +0x09c AlignMask        : 0xfffffff8

   +0x0a0 VirtualAllocdBlocks : _LIST_ENTRY [ 0x3300a0 - 0x3300a0 ]

   +0x0a8 SegmentList      : _LIST_ENTRY [ 0x330010 - 0x330010 ]

   +0x0b0 AllocatorBackTraceIndex : 0

   +0x0b4 NonDedicatedListLength : 0

   +0x0b8 BlocksIndex      : 0x00330150 Void

   +0x0bc UCRIndex         : 0x00330590 Void

   +0x0c0 PseudoTagEntries : (null) 

   +0x0c4 FreeLists        : _LIST_ENTRY [ 0x3db6a8 - 0x3de378 ]

   +0x0cc LockVariable     : 0x00330138 _HEAP_LOCK

   +0x0d0 CommitRoutine    : 0x37d910ba     long  +37d910ba

   +0x0d4 FrontEndHeap     : 0x00336548 Void

   +0x0d8 FrontHeapLockCount : 0

   +0x0da FrontEndHeapType : 0x2 ''

   +0x0dc Counters         : _HEAP_COUNTERS

   +0x130 TuningParameters : _HEAP_TUNING_PARAMETERS

Note: The _HEAP structure might be different for different versions of Windows.

A point to note here is that inside the _PEB there are two fields:

kd> dt _PEB ProcessH*

ntdll!_PEB

   +0x018 ProcessHeap : Ptr32 Void

   +0x090 ProcessHeaps : Ptr32 Ptr32 Void

The ProcessHeaps is an array of pointers to the various heaps for the process. The ProcessHeap on the other hand will always store the address of the default heap of the process.

To browse all heaps in this process, we can use the WinDbg .for command, which is described here.

kd> .for (r $t0 = 0; @$t0 < 0x4; r $t0 = @$t0 + 1){dt _HEAP poi(0x77c77500 + ((@$t0)*4)) - y SegmentSignature}

ntdll!_HEAP
   +0x008 SegmentSignature : 0xffeeffee
ntdll!_HEAP
   +0x008 SegmentSignature : 0xffeeffee
ntdll!_HEAP
   +0x008 SegmentSignature : 0xffeeffee
ntdll!_HEAP
   +0x008 SegmentSignature : 0xffeeffee

We will revisit heaps again for further elaborate discussions and even walking the heaps when we explore heap corruption scenarios.

WinDbg : Walking Windows Linked Lists (LIST_ENTRY)

WinDbg : Walking Windows Linked Lists (LIST_ENTRY)

The Windows implementation of the linked list is slightly different from how we are used to seeing it. Most of us start programming data structures with this simple, yet highly used data structure. We usually define a linked list node as follows: 

typedef struct _Node{

    int       ndata;

    _Node *pNext;

} NODE, *PNODE, **PNODE;

Using such a construct tightly couples the data part of the list to the list implementation. If someone later needs to store a character instead of integer, they have to rewrite the node structure. One way to avoid the problem is to use void pointers. redefining the node structure this way would solve the problem partially.

typedef struct _Node{

    void    *pDataBlob;

    _Node *pNext;

} NODE, *PNODE, **PNODE;

The above construct solves most problems, except that the memory for the data blob will have to be elsewhere, and not part of the node itself. This is not a big problem most of the time, unless one wants to serialize the Node and pass it.

Windows has a slightly different way of implementing linked lists.  Windows defines the entry to the list as:

typedef struct _LIST_ENTRY {

  struct _LIST_ENTRY  *Flink;

  struct _LIST_ENTRY  *Blink;

} LIST_ENTRY, *PLIST_ENTRY;

This is exported in the debugger, and we can use the dt command to view it as well.

kd> dt _LIST_ENTRY

ntdll!_LIST_ENTRY

   +0x000 Flink            : Ptr32 _LIST_ENTRY

   +0x004 Blink            : Ptr32 _LIST_ENTRY

Anyone wanting to use linked lists would then use this structure in the following manner:

typedef struct _MY_DATA_STRUCT{

    void             *pDataBlob;

    LIST_ENTRY   List;

} MY_DATA_STRUCT, *PMY_DATA_STRUCT, **PMY_DATA_STRUCT;

Observe, that the LIST_ENTRY struct is embedded inside the data structure we want the list to be of. It is not a pointer. The idea here is that  a separate pointer be maintained which can be used to traverse from one list entry to another, thus we would land up somewhere in the middle of the data structure, then we use the popular CONTAINING_RECORD macro to find the base of the structure.

Cumbersome? Not really. Depending on where you place the LIST_ENTRY inside your structure, you can use this to your advantage as well.

Assume that instead of defining MY_DATA_STRUCT the way we did, we do it this way:

typedef struct _MY_DATA_STRUCT{

    LIST_ENTRY   List;

    void             *pDataBlob;    

} MY_DATA_STRUCT, *PMY_DATA_STRUCT, **PMY_DATA_STRUCT;

In this scenario, since the LIST_ENTRY is the first member, we do not need to find the beginning of the struct at all, a simple C-style cast of one pointer type to another would make the entire structure accessible.

This article is not intended to teach you how to use LIST_ENTRY, but to help us debug structures which already are using this construct. So, after this very brief introduction to lists, I leave it to you to write a few programs using this data type, if you are not already familiar with it, to make yourself comfortable.

The rest of this article will focus on traversing such lists inside the debugger.

Commands used in this article Are:

1. !process
2. dt

Lets try to walk the list of active processes. For this we need to find the head of this list. It is exported by the NT kernel.

kd> x nt!psacti*

8274af18          nt!PsActiveProcessHead = <no type information>

Great, so we now have the pointer to the head of this list.

kd> dt nt!_LIST_ENTRY 8274af18          

 [ 0x839afcb0 - 0x851d1400 ]

   +0x000 Flink            : 0x839afcb0 _LIST_ENTRY [ 0x8490da80 - 0x8274af18 ]

   +0x004 Blink            : 0x851d1400 _LIST_ENTRY [ 0x8274af18 - 0x846e98c8 ]

Okay, so it has a set of valid pointers. However, we need to find out which data structure in Windows is using this list. That is when we can type cast the pointer to the right data structure. In this case, the kernel _EPROCESS data structure is the one using this list. Lets find out which offset of _EPROCESS has this list.

Note: _EPROCESS is a large data structure, so the following output is snipped off after the first few lines.

kd> dt nt!_EPROCESS

   +0x000 Pcb              : _KPROCESS

   +0x098 ProcessLock      : _EX_PUSH_LOCK

   +0x0a0 CreateTime       : _LARGE_INTEGER

   +0x0a8 ExitTime         : _LARGE_INTEGER

   +0x0b0 RundownProtect   : _EX_RUNDOWN_REF

   +0x0b4 UniqueProcessId  : Ptr32 Void

   +0x0b8 ActiveProcessLinks : _LIST_ENTRY

   +0x0c0 ProcessQuotaUsage : [2] Uint4B

   +0x0c8 ProcessQuotaPeak : [2] Uint4B

   +0x0d0 CommitCharge     : Uint4B

   +0x0d4 QuotaBlock       : Ptr32 _EPROCESS_QUOTA_BLOCK

   +0x0d8 CpuQuotaBlock    : Ptr32 _PS_CPU_QUOTA_BLOCK

   +0x0dc PeakVirtualSize  : Uint4B

   +0x0e0 VirtualSize      : Uint4B

   +0x0e4 SessionProcessLinks : _LIST_ENTRY

<Output Snipped>

Okay, so we found the offset of the LIST_ENTRY we want. this means that for any LIST_ENTRY address, belonging to a list of processes, subtracting 0x0b8 from it would lead us to the beginning of the _EPROCESS structure.

Note: The offset of this member could vary between one Windows flavor to another, even between service packs. So it it critical to know the right offset for the particular debugging session.

Okay, lets try to validate our example with a simple experiment. lets see for the process lsass.exe how this goes.

kd> !process 0 0 lsass.exe

PROCESS 84cdc860  SessionId: 0  Cid: 0208    Peb: 7ffda000  ParentCid: 018c

    DirBase: 1eed30e0  ObjectTable: 95f00d18  HandleCount: 513.

    Image: lsass.exe

kd> dt nt!_EPROCESS 84cdc860  

   +0x000 Pcb              : _KPROCESS

   +0x098 ProcessLock      : _EX_PUSH_LOCK

   +0x0a0 CreateTime       : _LARGE_INTEGER 0x01cf0ae6`f5dbfe68

   +0x0a8 ExitTime         : _LARGE_INTEGER 0x0

   +0x0b0 RundownProtect   : _EX_RUNDOWN_REF

   +0x0b4 UniqueProcessId  : 0x00000208 Void

   +0x0b8 ActiveProcessLinks : _LIST_ENTRY [ 0x849390e8 - 0x84ccb4c0 ]

   +0x0c0 ProcessQuotaUsage : [2] 0x2cdc

   +0x0c8 ProcessQuotaPeak : [2] 0x2cdc

   +0x0d0 CommitCharge     : 0x219

   +0x0d4 QuotaBlock       : 0x8273ecc0 _EPROCESS_QUOTA_BLOCK

   +0x0d8 CpuQuotaBlock    : (null) 

<output snipped>

So we see that for this particular debugging instance, for lsass.exe, the base of the _EPROCESS is at 0x84cdc860. Adding 0xb8 to it gives us 0x84CDC918. So if this is a valid offset inside the _EPROCESS, then subtracting 0xb8 from it should get us the _EPROCESS base address back. this is exactly what we will do with the nt!PsActiveProcessHead pointer and how do we do that? Well, the versatile dt command already supports walking windows lists. here is how it is done.

Find the pointer to the list head for Active Processes.

kd> x nt!psact*

8274af18          nt!PsActiveProcessHead = <no type information>

Then find the Flink entry address for this List_ENTRY

kd> dt nt!_LIST_ENTRY 8274af18

 [ 0x839afcb0 - 0x851d1400 ]

   +0x000 Flink            : 0x839afcb0 _LIST_ENTRY [ 0x8490da80 - 0x8274af18 ]

   +0x004 Blink            : 0x851d1400 _LIST_ENTRY [ 0x8274af18 - 0x846e98c8 ]

Now we typecast the pointer we got to _EPROCESS, but we subtract the correct offset, 0x0b8 first. Then we use the -l switch of the dt command to tell it that we want it to parse a list, via the Flink member of _LIST_ENTRY, where the member variable inside _EPROCESS which is this _LIST_ENTRY type is called ActiveProcessLinks. We also ask it to print out the ImageFilename member inside _EPROCESS so that we can see what all processes are currently active.

 

kd> dt nt!_EPROCESS 0x839afcb0-0x0b8 -l ActiveProcessLinks.Flink -y ImageFileName

ActiveProcessLinks.Flink at 0x839afbf8

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x8490da80 - 0x8274af18 ]

   +0x16c ImageFileName : [15]  "System"

ActiveProcessLinks.Flink at 0x8490d9c8

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x84c3b0e8 - 0x839afcb0 ]

   +0x16c ImageFileName : [15]  "smss.exe"

ActiveProcessLinks.Flink at 0x84c3b030

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x84bf2df8 - 0x8490da80 ]

   +0x16c ImageFileName : [15]  "csrss.exe"

ActiveProcessLinks.Flink at 0x84bf2d40

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x848a7df8 - 0x84c3b0e8 ]

   +0x16c ImageFileName : [15]  "wininit.exe"

ActiveProcessLinks.Flink at 0x848a7d40

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x84c54df8 - 0x84bf2df8 ]

   +0x16c ImageFileName : [15]  "csrss.exe"

ActiveProcessLinks.Flink at 0x84c54d40

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x84ccb4c0 - 0x848a7df8 ]

   +0x16c ImageFileName : [15]  "winlogon.exe"

ActiveProcessLinks.Flink at 0x84ccb408

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x84cdc918 - 0x84c54df8 ]

   +0x16c ImageFileName : [15]  "services.exe"

ActiveProcessLinks.Flink at 0x84cdc860

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x849390e8 - 0x84ccb4c0 ]

   +0x16c ImageFileName : [15]  "lsass.exe"

<Output trimmed>

the list is long, so i trimmed the output. As we see, that one of the process names printed is lsass.exe

ActiveProcessLinks.Flink at 0x84cdc860

---------------------------------------------

   +0x0b8 ActiveProcessLinks :  [ 0x849390e8 - 0x84ccb4c0 ]

   +0x16c ImageFileName : [15]  "lsass.exe"

The address of the ActiveProcessLinks.Flink member is 0x84cdc860. So the address of it's corresponding _EPROCESS would be 0x84cdc860 - 0x0b8 = 0x84CDC860. This is exactly the address we get when we did a !process 0 0 lsass.exe.

kd> !process 0 0 lsass.exe

PROCESS 84cdc860  SessionId: 0  Cid: 0208    Peb: 7ffda000  ParentCid: 018c

    DirBase: 1eed30e0  ObjectTable: 95f00d18  HandleCount: 513.

    Image: lsass.exe

Lists are used extensively inside Windows, and we will use these commands in future blog posts. So I would suggest that you execute these yourselves to familiarize with the concept.