Windows单链表(_SINGLE_LIST_ENTRY)

我只是在Windows 7崩溃转储中进行一些debugging,并且遇到了一个单链表,我无法完全理解。

这是WinDBG的输出:

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

从我一直在读的内容看来,每个单链表似乎都以一个列表头开始,它包含一个指向列表中第一个元素的指针,如果列表为空,则为空。

微软声明: MSDN文章

对于用作列表条目的SINGLE_LIST_ENTRY,Next成员指向列表中的下一个条目,如果列表中没有下一个条目,则为NULL。 对于作为列表头的SINGLE_LIST_ENTRY,Next成员指向列表中的第一个条目,如果列表为空,则指向NULL。

我99%确定这个列表包含一些条目,但我不明白如何值0x0000000000220001应该指向任何东西。 这个值当然不能parsing为有效的页面映射,所以我只能假设它是某种偏移量。 但是,我不确定。

如果有人能够帮助我们发现这一点,我会很感激的。

谢谢

UPDATE

我刚刚find一个文件(翻译成中文),似乎更多地解释了这个结构。 如果有人可以提供一些意见,我会很感激。

旁视清单文章

我实际上看到的是Windows应该用来分配IRP的后备列表,下面是WinDBG的全部输出(值从原来的问题改变了):

 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 

很抱歉,如果一些格式丢失。 本质上,这应该是一个lookaside列表,其中包含所有大小相同的大小的0x118 (sizeof(_IRP) + sizeof(_IO_STACK_LOCATION))

然而,我不完全确定这个列表是如何放在一起的,我不确定这是否应该是一个单独的内存块的列表,或者如果我不正确地阅读所有的列表。

Solutions Collecting From Web of "Windows单链表(_SINGLE_LIST_ENTRY)"

如果win7x86rtm的irp列表很小:

 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 

内存chank的大小是一个0字节

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

其中包括池头,指针,irp,堆栈位置

次要更新

作者Tarjei Mandt又名@kernelpool

_GENERAL_LOOKASIDE结构中,SingleListHead.Next指向单链接后备列表上的第一个空闲池块。 旁视列表的大小受深度值的限制,由平衡集管理器根据旁视列表中的命中和未命中数量进行定期调整。 因此,经常使用的后备列表将具有比不常使用的列表更大的深度值。 初始深度为4 nt!ExMinimumLookasideDepth ,最大为MaximumDepth (256)… 更多

SINGLE_LIST_ENTRY实现侵入式链接列表。 在linux内核中寻找提供类似功能的struct list_head

至于.Next成员,它确实是一个指向一个SINGLE_LIST_ENTRY的指针,它最有可能嵌入在另一个struct