title: Windows singly linked list (_SINGLE_LIST_ENTRY)
body: <p>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.</p>
  
  <p>Here's the output from WinDBG:</p>
  
  <pre><code>dt _GENERAL_LOOKASIDE_POOL fffff80002a14800 -b
  ....
  0x000 SingleListHead: _SINGLE_LIST_ENTRY
      +0x000 Next: 0x0000000000220001
  ....
  </code></pre>
  
  <p>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.</p>
  
  <p>Microsoft state: <a href="http://msdn.microsoft.com/en-us/library/windows/hardware/ff563799%28v=vs.85%29.aspx" rel="nofollow">MSDN article</a></p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>I'm 99% sure this list contains some entries, but I don't understand how the value of <code>0x0000000000220001</code> 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.</p>
  
  <p>If anyone could help shine some light on this, I'd appreciate it.</p>
  
  <p>Thanks</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>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.</p>
  
  <p><a href="http://www.mouseos.com/windows/kernel/lookaside.html" rel="nofollow">Lookaside List article</a></p>
  
  <p>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):</p>
  
  <pre><code>lkd&gt; !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&gt; dt _general_lookaside fffff80002a14800 -b
  ntdll!_GENERAL_LOOKASIDE
    +0x000 ListHead         : _SLIST_HEADER
    +0x000 Alignment        : 0x400001
    +0x008 Region           : 0xfffffa80`01e83b11
    +0x000 Header8          : &lt;unnamed-tag&gt;
       +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         : &lt;unnamed-tag&gt;
       +0x000 Depth            : 0y0000000000000001 (0x1)
       +0x000 Sequence         : 0y000000000000000000000000000000000000000001000000 (0x40)
       +0x008 HeaderType       : 0y1
       +0x008 Init             : 0y0
       +0x008 Reserved         : 0y00
       +0x008 NextEntry        : 0y111111111111111111111010100000000000000111101000001110110001 (0xfffffa8001e83b1)
    +0x000 HeaderX64        : &lt;unnamed-tag&gt;
       +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&gt; !slist fffff80002a14800
  SLIST HEADER:
     +0x000 Header16.Sequence          : 40
     +0x000 Header16.Depth            : 1
  
  SLIST CONTENTS:
  fffffa8001e83b10  0000000000000000 0000000000000000 
                    0000000000000404 0000000000000000 
  </code></pre>
  
  <p>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 <code>0x118 (sizeof(_IRP) + sizeof(_IO_STACK_LOCATION))</code></p>
  
  <p>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.</p>