Windows singly linked list (_SINGLE_LIST_ENTRY)

问题:

I'm just doing some debugging on a Windows 7 crash dump, and I've come across a singly-linked list that I'm not able to fully understand.

Here's the output from WinDBG:

dt _GENERAL_LOOKASIDE_POOL fffff80002a14800 -b
....
0x000 SingleListHead: _SINGLE_LIST_ENTRY
    +0x000 Next: 0x0000000000220001
....

From what I've been reading, it seems that each singly linked list begins with a list head, which contains a pointer to the first element in the list, or null if the list is empty.

Microsoft state: MSDN article

For a SINGLE_LIST_ENTRY that serves as a list entry, the Next member points to the next entry in the list, or NULL if there is no next entry in the list. For a SINGLE_LIST_ENTRY that serves as the list header, the Next member points to the first entry in the list, or NULL if the list is empty.

I'm 99% sure this list contains some entries, but I don't understand how the value of 0x0000000000220001 is supposed to be pointing to anything. This value certainly doesn't resolve to a valid page mapping, so I can only assume it's some kind of offset. However, I'm not sure.

If anyone could help shine some light on this, I'd appreciate it.

Thanks

UPDATE

I've just found a document (translated from Chinese) that seems to explain the structure a little more. If anyone could offer some input on it, I'd appreciate it.

Lookaside List article

What I'm actually looking at is a lookaside list that Windows should be using for the allocation of IRPs, here's the full output from WinDBG (values changed from original question):

lkd> !lookaside iopsmallirplookasidelist

Lookaside "" @ fffff80002a14800 "Irps"
Type     =     0000 NonPagedPool
Current Depth  =        0   Max Depth  =        4
Size           =      280   Max Alloc  =     1120
AllocateMisses =      127   FreeMisses =       26
TotalAllocates =      190   TotalFrees =       90
Hit Rate       =       33%  Hit Rate   =       71%

lkd> dt _general_lookaside fffff80002a14800 -b
ntdll!_GENERAL_LOOKASIDE
  +0x000 ListHead         : _SLIST_HEADER
  +0x000 Alignment        : 0x400001
  +0x008 Region           : 0xfffffa80`01e83b11
  +0x000 Header8          : <unnamed-tag>
     +0x000 Depth            : 0y0000000000000001 (0x1)
     +0x000 Sequence         : 0y001000000 (0x40)
     +0x000 NextEntry        : 0y000000000000000000000000000000000000000 (0)
     +0x008 HeaderType       : 0y1
     +0x008 Init             : 0y0
     +0x008 Reserved         : 0y11111111111111111101010000000000000011110100000111011000100       (0x7fffea0007a0ec4)
     +0x008 Region           : 0y111
  +0x000 Header16         : <unnamed-tag>
     +0x000 Depth            : 0y0000000000000001 (0x1)
     +0x000 Sequence         : 0y000000000000000000000000000000000000000001000000 (0x40)
     +0x008 HeaderType       : 0y1
     +0x008 Init             : 0y0
     +0x008 Reserved         : 0y00
     +0x008 NextEntry        : 0y111111111111111111111010100000000000000111101000001110110001 (0xfffffa8001e83b1)
  +0x000 HeaderX64        : <unnamed-tag>
     +0x000 Depth            : 0y0000000000000001 (0x1)
     +0x000 Sequence         : 0y000000000000000000000000000000000000000001000000 (0x40)
     +0x008 HeaderType       : 0y1
     +0x008 Reserved         : 0y000
     +0x008 NextEntry        : 0y111111111111111111111010100000000000000111101000001110110001 (0xfffffa8001e83b1)
  +0x000 SingleListHead   : _SINGLE_LIST_ENTRY
      +0x000 Next             : 0x00000000`00400001 
  +0x010 Depth            : 4
  +0x012 MaximumDepth     : 0x20
  +0x014 TotalAllocates   : 0xbe
  +0x018 AllocateMisses   : 0x7f
  +0x018 AllocateHits     : 0x7f
  +0x01c TotalFrees       : 0x5a
  +0x020 FreeMisses       : 0x1a
  +0x020 FreeHits         : 0x1a
  +0x024 Type             : 0 ( NonPagedPool )
  +0x028 Tag              : 0x73707249
  +0x02c Size             : 0x118
  +0x030 AllocateEx       : 0xfffff800`029c30e0 
  +0x030 Allocate         : 0xfffff800`029c30e0 
  +0x038 FreeEx           : 0xfffff800`029c30d0 
  +0x038 Free             : 0xfffff800`029c30d0 
  +0x040 ListEntry        : _LIST_ENTRY [ 0xfffff800`02a147c0 - 0xfffff800`02a148c0 ]
     +0x000 Flink            : 0xfffff800`02a147c0 
     +0x008 Blink            : 0xfffff800`02a148c0 
  +0x050 LastTotalAllocates : 0xbe
  +0x054 LastAllocateMisses : 0x7f
  +0x054 LastAllocateHits : 0x7f
  +0x058 Future           : 
   [00] 0
   [01] 0

lkd> !slist fffff80002a14800
SLIST HEADER:
   +0x000 Header16.Sequence          : 40
   +0x000 Header16.Depth            : 1

SLIST CONTENTS:
fffffa8001e83b10  0000000000000000 0000000000000000 
                  0000000000000404 0000000000000000 

Sorry if some of the formatting is lost. Essentially, this should be a lookaside list that contains a list of chunks that are all of the same size 0x118 (sizeof(_IRP) + sizeof(_IO_STACK_LOCATION))

However I'm not entirely sure how the list is actually put together, I'm not sure if this should be a singly linked list of memory chunks, or if I'm reading all of it incorrectly.

回答1:

In case of small irp list with win7x86rtm:

lkd> !lookaside iopsmallirplookasidelist 
Lookaside "" @ 82d5ffc0 "Irps"
....
lkd> dt _SINGLE_LIST_ENTRY 82d5ffc0 
nt!_SINGLE_LIST_ENTRY
   +0x000 Next             : 0x86737e30 _SINGLE_LIST_ENTRY
....
lkd> !pool 0x86737e30 
Pool page 86737e30 region is Nonpaged pool
*86737e28 size:   a0 previous size:   48  (Allocated) *Irp 
        Pooltag Irp  : Io, IRP packets

The size of memory chank is a0 bytes

lkd> ?? sizeof(_pool_header)+sizeof(_single_list_entry)+sizeof(_irp)+sizeof(_io_stack_location)
unsigned int 0xa0

which include pool header, pointer, irp, stack location

Minor update:

Author Tarjei Mandt aka @kernelpool

In _GENERAL_LOOKASIDE structure, SingleListHead.Next points to the first free pool chunk on the singly-linked lookaside list. The size of the lookaside list is limited by the value of Depth, periodically adjusted by the balance set manager according to the number of hits and misses on the lookaside list. Hence, a frequently used lookaside list will have a larger Depth value than an infrequently used list. The intial Depth is 4 nt!ExMinimumLookasideDepth, with maximum being MaximumDepth (256)...more

回答2:

SINGLE_LIST_ENTRY implements intrusive linked-lists. Look for struct list_head which offers similar functionnality within the linux kernel.

As for the .Next member, it really is a pointer to a SINGLE_LIST_ENTRY that is most likely embedded inside another struct.