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:
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.
No comments:
Post a Comment