Introduction

Lately, I dusted off the marvelous ‘Practical Reverse Engineering’ book by Bruce Dang & Co. which made me realize it would be useful to structure notes along each chapter’s exercises. Could be a valuable reference for the future, especially anything related to Chapter 3 (Windows Kernel) onwards. I decided to focus on one of the most basic and still very widespread data structure in kernel land: linked lists.

The most used type in the Windows Kernel is the Circular doubly-linked list, so we are going to focus only on this kind.

As per book definition, a doubly-linked list is a:

A list whose entries are linked together with two pointers, one pointing to the next entry (Flink) and one pointing to the previous entry (Blink).

They appear in form of WDK headers, and so you’ll never find them at as pure assembly functions from a debugger point of view as they are inserted inline by the compiler. Thus, it is important to recognize their assembly patterns since they are outside any call, jmp or ret logic.

Linked lists definitions can be typically found along with many others at C:\Program Files (x86)\Windows Kits\10\Include\[SDK_version]\shared\ntdef.h

List Entry is the building block of any linked list data structure.

  typedef struct _LIST_ENTRY {
     struct _LIST_ENTRY *Flink;
     struct _LIST_ENTRY *Blink;
  } LIST_ENTRY, *PLIST_ENTRY;

Before moving to the first part of the exercises' solutions, let’s have an overview of the main routines dealing with linked-list operations.

InitializeListHead

Lists must be initialized with InitializeListHead before usage. This function simply sets the Flink and Blink fields to point to the list head.

  VOID InitializeListHead(PLIST_ENTRY ListHead) {
      ListHead->Flink = ListHead->Blink = ListHead;
      return;
}

In assembly form, this would translate to three instructions: one to retrieve ListHead and two to fill out the Flink and Blink pointers.

x86

lea eax, [esi+2Ch] ; saves ListHead pointer into eax
mov [eax+4], eax   ; makes ListHead->Blink points to ListHead
mov [eax], eax     ; makes ListHead->Flink points to ListHead

x64

lea r11, [rbx+48h] ; saves ListHead pointer into r11
mov [r11+8], r11   ; makes ListHead->Blink points to ListHead
mov [r11], r11     ; makes ListHead->Flink points to ListHead

It is worth noting that offset +0 and +4/8 from the base register are pointing to Flink and Blink respectively.

InsertHeadList

Element insertion is done via either InsertHeadList or InsertTailList, depending on where we want to insert the new entry.

VOID InsertHeadList(PLIST_ENTRY ListHead, PLIST_ENTRY Entry) {
    PLIST_ENTRY Flink;
    Flink = ListHead->Flink;
    Entry->Flink = Flink;
    Entry->Blink = ListHead;
    Flink->Blink = Entry;
    ListHead->Flink = Entry;
    return;
}

EBX/RDI point to ListHead and ECX/RAX point to Entry.

x86

mov     edx, [ebx].  ; saves old ListHead->Flink into edx (as Flink new variable)
mov     [ecx], edx   ; saves ListHead into Entry->Flink
mov     [ecx+4], ebx ; saves ListHead into Entry->Blink
mov     [edx+4], ecx ; saves Entry into Entry-Blink
mov     [ebx], ecx   ; saves Entry into ListHead->Flink

x64

mov     rcx, [rdi]   ; saves old ListHead->Flink into rcx (as Flink new variable)
mov     [rax+8], rdi ; saves ListHead into Entry->Blink
mov     [rax], rcx   ; saves ListHead->Flink into Entry->Flink
mov     [rcx+8], rax ; saves Entry into Entry-Blink
mov     [rdi], rax   ; saves Entry into ListHead->Flink

InsertTailList

VOID InsertTailList(PLIST_ENTRY ListHead, PLIST_ENTRY Entry) {
    PLIST_ENTRY Blink;
    Blink = ListHead->Blink;
    Entry->Flink = ListHead;
    Entry->Blink = Blink;
    Blink->Flink = Entry;
    ListHead->Blink = Entry;
    return;
}

Here instead, EBX/RDI point to ListHead and EAX/RAX point to Entry.

x86

mov     ecx, [ebx+4] ; saves old ListHead->Blink into ecx
mov     [eax], ebx   ; saves ListHead into Entry->Flink
mov     [eax+4], ecx ; load old ListHead->Blink into Entry->Blink
mov     [ecx], eax   ; saves Entry into ListHead->Flink
mov     [ebx+4], eax ; saves Entry into ListHead->Blink

x64

mov     rcx, [rdi+8] ; saves old ListHead->Blink into rcx
mov     [rax], rdi   ; saves ListHead into Entry->Flink
mov     [rax+8], rcx ; load old ListHead->Blink into Entry->Blink
mov     [rcx], rax   ; saves Entry into ListHead->Flink
mov     [rdi+8], rax ; saves Entry into ListHead->Blink

IsListEmpty

Before deleting any entry via either RemoveHeadList, RemoveTailList, or RemoveEntryList a check is done through isListEmpty to verify if the list is not already empty.

BOOLEAN IsListEmpty(PLIST_ENTRY ListHead) {
    return (BOOLEAN)(ListHead->Flink == ListHead);

x86

mov eax, [esi]       ; loads ListHead’s Flink into eax
cmp eax, esi         ; compare it with the ListHead itself

x64

mov rax, [rbx]       ; loads ListHead’s Flink into rax
cmp rax, rbx         ; compare it with the ListHead itself

RemoveHeadList

PLIST_ENTRY RemoveHeadList(PLIST_ENTRY ListHead) {
    PLIST_ENTRY Flink;
    PLIST_ENTRY Entry;
    Entry = ListHead->Flink;
    Flink = Entry->Flink;
    ListHead->Flink = Flink;
    Flink->Blink = ListHead;
    return Entry;
}

x86

mov eax, [esi]       ; saves ListHead->Flink into eax
mov ecx, [eax]       ; saves Entry->Flink into ecx
mov [esi], ecx       ; makes ListHead->Flink point to NextEntry->Flink
mov [ecx+4], esi     ; makes NextEntry->Blink ListHead point to ListHead

x64

mov rax, [rbx]       ; saves ListHead->Flink into rax
mov rcx, [rax]       ; saves Entry->Flink into rcx
mov [rbx], rcx       ; makes ListHead->Flink point to NextEntry->Flink
mov [rcx+8], rbx     ; makes NextEntry->Blink ListHead point to ListHead

RemoveTailList

PLIST_ENTRY RemoveTailList(PLIST_ENTRY ListHead) {
    PLIST_ENTRY Blink;
    PLIST_ENTRY Entry;
    Entry = ListHead->Blink;
    Blink = Entry->Blink;
    ListHead->Blink = Blink;
    Blink->Flink = ListHead;
    return Entry;

x86

mov  ebx, [edi+4]    ; saves ListHead->Blink into ebx (Entry)
mov  eax, [ebx+4]    ; saves Entry->Blink into eax (Blink)
mov  [edi+4], eax    ; makes ListHead->Blink point to NextEntry->Blink
mov  [eax], edi      ; makes NextEntry->Flink ListHead point to ListHead

x64

mov  rsi, [rdi+8]    ; saves ListHead->Blink into ebx (Entry)
mov  rax, [rsi+8]    ; saves Entry->Blink into eax (Blink)
mov  [rdi+8], rax    ; makes ListHead->Blink point to NextEntry->Blink
mov  [rax], rdi      ; makes NextEntry->Flink ListHead point to ListHead

RemoveEntryList

BOOLEAN RemoveEntryList(PLIST_ENTRY Entry){
    PLIST_ENTRY Blink;
    PLIST_ENTRY Flink;
    Flink = Entry->Flink;
    Blink = Entry->Blink;
    Blink->Flink = Flink;
    Flink->Blink = Blink;
    return (BOOLEAN)(Flink == Blink);

x86

mov  edx, [ecx]      ; saves Entry->Flink
mov  eax, [ecx+4]    ; saves Entry->Blink
mov  [eax], edx      ; makes previous entry point to next one
mov  [edx+4], eax    ; makes next entry point to previous one

x64

mov  rdx, [rcx]      ; same as above
mov  rax, [rcx+8]
mov  [rax], rdx
mov  [rdx+8], rax

Finally, the following macro is used to obtain the actual value of the content of a list entry. As per MSDN

The CONTAINING_RECORD macro returns the base address of an instance of a structure given the type of the structure and the address of a field within the containing structure.

#define CONTAINING_RECORD(address, type, field) ((type *)( \
                                                  (PCHAR)(address) - \
                                                  (ULONG_PTR)(&((type *)0)->field)))

Solutions Chapter 3 - page 123

Problem:

On Windows 8 x64, the following kernel functions have InitalizeListHead inlined at least once:

CcAllocateInitializeMbcb
CmpInitCallbacks
ExCreateCallback
ExpInitSystemPhase0
ExpInitSystemPhase1
ExpTimerInitialization
InitBootProcessor
IoCreateDevice
IoInitializeIrp
KeInitThread
KeInitializeMutex
KeInitializeProcess
KeInitializeTimerEx
KeInitializeTimerTable
KiInitializeProcessor
KiInitializeThread
MiInitializeLoadedModuleList
MiInitializePrefetchHead
PspAllocateProcess
PspAllocateThread

Instead of Windows 8 x64 we are going to inspect these functions in the latest Win10 build 12004 - 19041.685.

CcAllocateInitializeMbcb

This function comes from the Cache Manager (Cc) component.

mov     eax,2FBh
mov     word ptr [rbx],ax
lea     rcx,[rbx+10h]
lea     rax,[rbx+30h]
mov     qword ptr [rax],rcx
mov     qword ptr [rax+8],rcx
mov     qword ptr [rcx],rax
mov     qword ptr [rcx+8],rax

Before initializing the linked list, the functions first call ExAllocatePoolWithTag and the allocated memory is saved in rbx.

fffff801`2570ed2e e8fd226a00      call    nt!ExAllocatePoolWithTag (fffff801`25db1030)
fffff801`2570ed33 488bd8          mov     rbx,rax

It then sets NodeTypeCode field in the MBCB to 2FB which is actually telling the cache manager that we are dealing with a CACHE_NTC_MBCB type.

0: kd> dt nt!_MBCB
   +0x000 NodeTypeCode     : Int2B
   +0x002 NodeIsInZone     : Int2B
   +0x004 PagesToWrite     : Uint4B
   +0x008 DirtyPages       : Uint4B
   +0x00c Reserved         : Uint4B
   +0x010 BitmapRanges     : _LIST_ENTRY
   +0x020 ResumeWritePage  : Int8B
   +0x028 MostRecentlyDirtiedPage : Int8B
   +0x030 BitmapRange1     : _BITMAP_RANGE
   +0x060 BitmapRange2     : _BITMAP_RANGE
   +0x090 BitmapRange3     : _BITMAP_RANGE

Offsets 0x10 and 0x30 tell that we are dealing with the first of BitmapRanges entry.

CmpInitCallbacks

nt!CmpInitCallbacks:
sub     rsp,28h ; negligible
xor     ecx,ecx ; negligible
lea     rax,[nt!CallbackListHead (fffff801`260482e0)]
mov     dword ptr [nt!CmpCallBackCount (fffff801`260508f0)],ecx
lea     rdx,[nt!`string' (fffff801`2540e9e8)]
mov     qword ptr [nt!CmpCallbackListLock (fffff801`260482d8)],rcx
mov     qword ptr [nt!CmpContextListLock (fffff801`260482f0)],rcx
mov     qword ptr [nt!CallbackListDeleteEvent (fffff801`260482f8)],rcx

The list initialization is done via lea rax,[nt!CallbackListHead].

4: kd> x nt!CallBackListHead
fffff801`260482e0 nt!CallbackListHead = <no type information>

We can validate that is in fact a LIST_ENTRY by double checking against the ERESOURCE structure.

4: kd> dt nt!_ERESOURCE  fffff801`260482e0
   +0x000 SystemResourcesList : _LIST_ENTRY [ 0xffff8b09`84c05960 - 0xffff8b09`8bbd1e70 ]
   +0x010 OwnerTable       : (null) 
   +0x018 ActiveCount      : 0n0
   +0x01a Flag             : 0
   +0x01a ReservedLowFlags : 0 ''
   +0x01b WaiterPriority   : 0 ''
   +0x020 SharedWaiters    : 0x01d6d4a5`ceb5a831 Void
   +0x028 ExclusiveWaiters : (null) 
   +0x030 OwnerEntry       : _OWNER_ENTRY
   +0x040 ActiveEntries    : 0
   +0x044 ContentionCount  : 0
   +0x048 NumberOfSharedWaiters : 0
   +0x04c NumberOfExclusiveWaiters : 0
   +0x050 Reserved2        : (null) 
   +0x058 Address          : (null) 
   +0x058 CreatorBackTraceIndex : 0
   +0x060 SpinLock         : 0

ExCreateCallback

Here’s the inlined InitializeListHead

mov  qword ptr [rax+8],rbx
mov  qword ptr [rax+18h],rsi
mov  qword ptr [rax+20h],rdi

ExpInitSystemPhase0

This function has been fully restructured on this Windows10 version and has no InitializeListHead inlined

ExpInitSystemPhase1

This function has been fully restructured on this Windows10 version and has no InitializeListHead inlined

ExpTimerInitialization

This function has been fully restructured on this Windows10 version and has no InitializeListHead inlined

InitBootProcessor

This function has been fully restructured on this Windows10 version and has no InitializeListHead inlined

IoCreateDevice

Here is the inlined InitializeListHead

 lea     rax,[rbx+50h]
 mov     qword ptr [rax+8],rax
 mov     qword ptr [rax],rax

at rbx we have a pointer to DeviceObject whose +50h offset is a Queue of KDEVICE_QUEUE type. At 0x8 from where we have indeed a LIST_ENTRY .

nt!IoCreateDevice+0x258:
fffff804`75702698 48894008        mov     qword ptr [rax+8],rax

3: kd> dt nt!_KDEVICE_QUEUE @rax
   +0x000 Type             : 0n0
   +0x002 Size             : 0n0
   +0x008 DeviceListHead   : _LIST_ENTRY [ 0x00000000`00000000 - 0x00000000`00000000 ]
   +0x018 Lock             : 0
   +0x020 Busy             : 0 ''
   +0x020 Reserved         : 0y00000000 (0)
   +0x020 Hint             : 0y00000000000000000000000000000000000000000000000000000000 (0)

IoInitializeIrp

Here the inlined routine:

lea     rax,[rbx+20h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

at 0x20 of the IRP we have a ThreadListEntry struct.

1: kd> dt _IRP @rbx
nt!_IRP
   +0x000 Type             : 0n6
   +0x002 Size             : 0x6b8
   +0x004 AllocationProcessorNumber : 0
   +0x006 Reserved         : 0
   +0x008 MdlAddress       : (null) 
   +0x010 Flags            : 0
   +0x018 AssociatedIrp    : <anonymous-tag>
   +0x020 ThreadListEntry  : _LIST_ENTRY [ 0x00000000`00000000 - 0x00000000`00000000 ]
   +0x030 IoStatus         : _IO_STATUS_BLOCK
   +0x040 RequestorMode    : 0 ''
   +0x041 PendingReturned  : 0 ''
   +0x042 StackCount       : 21 ''
   +0x043 CurrentLocation  : 22 ''
   +0x044 Cancel           : 0 ''
   +0x045 CancelIrql       : 0 ''
   +0x046 ApcEnvironment   : 0 ''
   +0x047 AllocationFlags  : 0 ''
   +0x048 UserIosb         : (null) 
   +0x050 UserEvent        : (null) 
   +0x058 Overlay          : <anonymous-tag>
   +0x068 CancelRoutine    : (null) 
   +0x070 UserBuffer       : (null) 
   +0x078 Tail             : <anonymous-tag>

which is naturally of LIST_ENTRY type.

1: kd> dx -id 0,0,ffff89884d7e32c0 -r1 (*((ntkrnlmp!_LIST_ENTRY *)0xffff89884cadc8c0))
(*((ntkrnlmp!_LIST_ENTRY *)0xffff89884cadc8c0))                 [Type: _LIST_ENTRY]
    [+0x000] Flink            : 0x0 [Type: _LIST_ENTRY *]
    [+0x008] Blink            : 0x0 [Type: _LIST_ENTRY *]

KeInitThread

This routine is responsible for the KTHREAD initialization, so it’s wise to start inspecting this structure in the first place and highlight the LIST_ENTRY sub-members.

0: kd> dt _KTHREAD -b
nt!_KTHREAD
   +0x000 Header           : _DISPATCHER_HEADER
    [...]
      +0x008 WaitListHead     : _LIST_ENTRY
         +0x000 Flink            : Ptr64 
         +0x008 Blink            : Ptr64 
    [...]
   +0x098 ApcState         : _KAPC_STATE
      +0x000 ApcListHead      : _LIST_ENTRY
         +0x000 Flink            : Ptr64 
         +0x008 Blink            : Ptr64 
    [...]
   +0x0d8 WaitListEntry    : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64 
    [...]
         +0x008 WaitListHead     : _LIST_ENTRY
            +0x000 Flink            : Ptr64 
            +0x008 Blink            : Ptr64 
    [...]      
      +0x020 TimerListEntry   : _LIST_ENTRY
         +0x000 Flink            : Ptr64 
         +0x008 Blink            : Ptr64 
    [...]
   +0x140 WaitBlock        : _KWAIT_BLOCK
      +0x000 WaitListEntry    : _LIST_ENTRY
         +0x000 Flink            : Ptr64 
         +0x008 Blink            : Ptr64 
    [...]
   +0x208 QueueListEntry   : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64 
    [...]
   +0x258 SavedApcState    : _KAPC_STATE
      +0x000 ApcListHead      : _LIST_ENTRY
         +0x000 Flink            : Ptr64 
         +0x008 Blink            : Ptr64 
    [...]
   +0x288 SchedulerApc     : _KAPC
      +0x000 Type             : UChar
      +0x001 SpareByte0       : UChar
      +0x002 Size             : UChar
      +0x003 SpareByte1       : UChar
      +0x004 SpareLong0       : Uint4B
      +0x008 Thread           : Ptr64 
      +0x010 ApcListEntry     : _LIST_ENTRY
         +0x000 Flink            : Ptr64 
         +0x008 Blink            : Ptr64 
    [...]
   +0x2dc UserTime         : Uint4B
   +0x2e0 SuspendEvent     : _KEVENT
         +0x008 WaitListHead     : _LIST_ENTRY
            +0x000 Flink            : Ptr64 
            +0x008 Blink            : Ptr64 
    [...]
   +0x2f8 ThreadListEntry  : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64 
    [...]
   +0x308 MutantListHead   : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64 
    [...]
   +0x370 GlobalForegroundListEntry : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64 
    [...]
   +0x3f0 GlobalUpdateVpThreadPriorityListEntry : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64

The first occurrence of InitializeListHead is:

lea     rax,[rcx+8]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

rcx points to KTHREAD, so this is initializing a WaitListHead LIST_ENTRY.

The second one is setting up MutantListHead:

lea     rax,[rcx+308h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

The third is related to ApcState

lea     rax,[rdi+98h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

and the last one is initializing the struct at offset 0x10 (0xA8) from ApcState which is the second entry of the list.

lea     rax,[rdi+0A8h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

Let’s verify it: rdi holds a pointer to the ApcState structure and at offset 0 we have the ApcListHead

kd> dt nt!_KAPC_STATE @rdi
   +0x000 ApcListHead      : [2] _LIST_ENTRY [ 0x00000000`00200000 - 0xffff8988`4c6e4088 ]
   +0x020 Process          : (null) 
   +0x028 InProgressFlags  : 0 ''
   +0x028 KernelApcInProgress : 0y0
   +0x028 SpecialApcInProgress : 0y0
   +0x029 KernelApcPending : 0 ''
   +0x02a UserApcPendingAll : 0 ''
   +0x02a SpecialUserApcPending : 0y0
   +0x02a UserApcPending   : 0y0

kd> dx -id 0,0,ffff89884d071080 -r1 (*((ntkrnlmp!_LIST_ENTRY (*)[2])0xffff89884c6e4080))
(*((ntkrnlmp!_LIST_ENTRY (*)[2])0xffff89884c6e4080))                 [Type: _LIST_ENTRY [2]]
    [0]              [Type: _LIST_ENTRY]
    [1]              [Type: _LIST_ENTRY]

kd> dx -id 0,0,ffff89884d071080 -r1 (*((ntkrnlmp!_LIST_ENTRY *)0xffff89884c6e4090))
(*((ntkrnlmp!_LIST_ENTRY *)0xffff89884c6e4090))                 [Type: _LIST_ENTRY]
    [+0x000] Flink            : 0xffff89884c6e4088 [Type: _LIST_ENTRY *]
    [+0x008] Blink            : 0x0 [Type: _LIST_ENTRY *]

The second entry 0xffff89884c6e4090 is exactly at 0x10 from the ListHead 0xffff89884c6e4080.

KeInitializeMutex

This routine is just a wrapper to KiInitializeMutant

0: kd> uf KeInitializeMutex
nt!KeInitializeMutex:
sub     rsp,28h
mov     r8b,1
xor     edx,edx
call    nt!KiInitializeMutant (fffff804`752debe8)
add     rsp,28h
ret

So if we examine the latter we can just spot a single inlined InitializeListHead.

lea     rax,[rbx+8]
mov     rsi,qword ptr [rsp+58h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

Which is referencing an offset +8 to a KMUTANT struct. If we place a breakpoint and analyze the structure against rbx we can notice:

kd> dt nt!_KMUTANT @rbx
   +0x000 Header           : _DISPATCHER_HEADER
   +0x018 MutantListEntry  : _LIST_ENTRY [ 0x00000000`00000000 - 0x00000000`00000000 ]
   +0x028 OwnerThread      : (null) 
   +0x030 MutantFlags      : 0 ''
   +0x030 Abandoned        : 0y0
   +0x030 Spare1           : 0y0000000 (0)
   +0x030 Abandoned2       : 0y0
   +0x030 AbEnabled        : 0y0
   +0x030 Spare2           : 0y000000 (0)
   +0x031 ApcDisable       : 0 ''


kd> dx -id 0,0,ffff89884bebd080 -r1 (*((ntkrnlmp!_DISPATCHER_HEADER *)0xffff89884c4d2c40))
(*((ntkrnlmp!_DISPATCHER_HEADER *)0xffff89884c4d2c40))                 [Type: _DISPATCHER_HEADER]
[...]
    [+0x008] WaitListHead     [Type: _LIST_ENTRY]

kd> dx -id 0,0,ffff89884bebd080 -r1 (*((ntkrnlmp!_LIST_ENTRY *)0xffff89884c4d2c48))

(*((ntkrnlmp!_LIST_ENTRY *)0xffff89884c4d2c48))                 [Type: _LIST_ENTRY]
    [+0x000] Flink            : 0xffff89884c4d2c48 [Type: _LIST_ENTRY *]
    [+0x008] Blink            : 0xffff89884c4d2c48 [Type: _LIST_ENTRY *]

Which belongs to a WaitListHead LIST_ENTRY structure.

KeInitializeProcess

The first initialization can be found here:

lea     rax,[rcx+8]
[...]
mov     qword ptr [rax+8],rax
[...]
mov     qword ptr [rax],rax

rcx points to KPROCESS structure as it’s the first argument.

KeInitializeProcess(
  IN  PRKPROCESS Process,
  IN  KPRIORITY BasePriority,
  IN  KAFFINITY Affinity,
  IN  ULONG DirectoryTableBase[2],
  IN  BOOLEAN Enable
  );

And at offset +8 we can see WaitListHead as part of the header of type DISPATCHER HEADER

nt!_KPROCESS
   +0x000 Header           : _DISPATCHER_HEADER
[...]
      +0x008 WaitListHead     : _LIST_ENTRY [ 0x00000000`00000000 - 0x00000000`00000000 ]
         +0x000 Flink            : (null) 
         +0x008 Blink            : (null) 

2: kd> dx -id 0,0,ffff89884b6db080 -r1 (*((ntkrnlmp!_LIST_ENTRY *)0xffff8988521a6200))
(*((ntkrnlmp!_LIST_ENTRY *)0xffff8988521a6200))                 [Type: _LIST_ENTRY]
    [+0x000] Flink            : 0x0 [Type: _LIST_ENTRY *]
    [+0x008] Blink            : 0x0 [Type: _LIST_ENTRY *]

Next we can see three initialization in one go:

lea     rax,[rbx+18h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax
lea     rax,[rbx+158h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax
lea     rax,[rbx+30h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

rbx is still pointing to the same KPROCESS as it has been moved from rcx earlier in the routine.

The first item accessed is a ProfileListHead, then ReadyListHead and lastly ThreadListHead

2: kd> dt _KPROCESS -b
nt!_KPROCESS
   +0x000 Header           : _DISPATCHER_HEADER
   [...]
   +0x018 ProfileListHead  : _LIST_ENTRY
   [...]
   +0x030 ThreadListHead   : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64 
    [...]
   +0x158 ReadyListHead    : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64

KeInitializeTimerEx

This is a brief one and has only one inlined list initialization.

lea     rax,[rcx+8]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

The first parameter is referencing a KTIMER struct which has a WaitListHead at offset +8

0: kd> dt _KTIMER -b
nt!_KTIMER
   +0x000 Header           : _DISPATCHER_HEADER
[...]
   +0x008 WaitListHead     : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64

KeInitializeTimerTable

Here’s the only inlined entry:

nt!KeInitializeTimerTable+0x9c:
lea     rax,[rbx+3B48h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

This function looks like unused as the symbol for KiTimerTableListHead is missing.

KiInitializeProcessor

This function has been fully restructured on this Windows10 version and has no InitializeListHead inlined

KiInitializeThread

This function has been fully restructured on this Windows10 version and has no InitializeListHead inlined It might have been replaced by KiInitializeIdleThread and KiInitializeContextThread

KiInitializeIdleThread (extra)

We can see that we have two inlined in a row.

lea     rax,[rbx+560h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax
lea     rax,[rbx+570h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

This one is not documented so, given the context, we have to guess that rbx is pointing to a ETHREAD structure/ If so, offset 560 and 570 point to BoostList and DeboostList respectively.

+0x560 BoostList        : _LIST_ENTRY
   +0x000 Flink            : Ptr64 
   +0x008 Blink            : Ptr64 
+0x570 DeboostList      : _LIST_ENTRY
   +0x000 Flink            : Ptr64 
   +0x008 Blink            : Ptr64

KiInitializeContextThread (extra)

mov     rax,qword ptr [rsp+30h]
mov     qword ptr [rbx],rax
mov     rax,qword ptr [rsp+38h]
mov     qword ptr [rbx+8],rax

rsp+38 points to a KSTART_ROUTINE, while rsp+30 to a StartContext.

MiInitializeLoadedModuleList

This function has been fully restructured on this Windows10 version and has no InitializeListHead inlined

MiInitializePrefetchHead

This function is missing on this Windows10 version

PspAllocateProcess

This one has three inlined at once. Also undocumented, but since we are dealing with processes, we can affirm with almost certainty that the one we are facing it’s a EPROCESS structure.

lea     rax,[r15+5E0h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax
lea     rax,[r15+8A0h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax
lea     rax,[r15+990h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

And indeed these offsets are matching types of LIST ENTRY

0: kd> dt _EPROCESS -b
ntdll!_EPROCESS
   +0x000 Pcb              : _KPROCESS
    [...]
   +0x5e0 ThreadListHead   : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64 
    [...]
   +0x8a0 SvmProcessDeviceListHead : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64 
    [...]
   +0x990 VirtualTimerListHead : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64

PspAllocateThread

We have six inlined initialization in a row.

lea     rax,[rsi+438h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

lea     rax,[rsi+560h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

lea     rax,[rsi+570h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

lea     rax,[rsi+5C8h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

lea     rax,[rsi+4B0h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

lea     rax,[rsi+468h]
mov     qword ptr [rax+8],rax
mov     qword ptr [rax],rax

Again, given the context, we can infer it’s an ETHREAD structure

+0x438 KeyedWaitChain   : _LIST_ENTRY
   +0x000 Flink            : Ptr64 
   +0x008 Blink            : Ptr64 
[...] 
+0x468 ActiveTimerListHead : _LIST_ENTRY
   +0x000 Flink            : Ptr64 
   +0x008 Blink            : Ptr64 
[...]
+0x4b0 IrpList          : _LIST_ENTRY
   +0x000 Flink            : Ptr64 
   +0x008 Blink            : Ptr64 
[...]
+0x560 BoostList        : _LIST_ENTRY
   +0x000 Flink            : Ptr64 
   +0x008 Blink            : Ptr64 
[...]
+0x570 DeboostList      : _LIST_ENTRY
   +0x000 Flink            : Ptr64 
   +0x008 Blink            : Ptr64 
[...]
+0x5c8 PropertySet      : _PS_PROPERTY_SET
   +0x000 ListHead         : _LIST_ENTRY
      +0x000 Flink            : Ptr64 
      +0x008 Blink            : Ptr64

Linked List in the Kernel: ‘Practical Reverse Engineering’ solutions - Part 1

Introduction

InitializeListHead

InsertHeadList

InsertTailList

IsListEmpty

RemoveHeadList

RemoveTailList

RemoveEntryList

Solutions Chapter 3 - page 123

CcAllocateInitializeMbcb

CmpInitCallbacks

ExCreateCallback

ExpInitSystemPhase0

ExpInitSystemPhase1

ExpTimerInitialization

InitBootProcessor

IoCreateDevice

IoInitializeIrp

KeInitThread

KeInitializeMutex

KeInitializeProcess

KeInitializeTimerEx

KeInitializeTimerTable

KiInitializeProcessor

KiInitializeThread

KiInitializeIdleThread (extra)

KiInitializeContextThread (extra)

MiInitializeLoadedModuleList

MiInitializePrefetchHead

PspAllocateProcess

PspAllocateThread