Windows单链表(_SINGLE_LIST_ENTRY) [英] Windows singly linked list (_SINGLE_LIST_ENTRY)
问题描述
我只是在Windows 7故障转储上进行一些调试，并且遇到了一个单链列表，我无法完全理解它.
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.
这是WinDBG的输出:
Here's the output from WinDBG:
dt _GENERAL_LOOKASIDE_POOL fffff80002a14800 -b
....
0x000 SingleListHead: _SINGLE_LIST_ENTRY
+0x000 Next: 0x0000000000220001
....
从我一直在阅读的内容来看，似乎每个单链接的列表都以一个列表头开始，该列表头包含一个指向列表中第一个元素的指针；如果列表为空，则为null.
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状态: MSDN文章
Microsoft state: MSDN article
对于用作列表条目的SINGLE_LIST_ENTRY，Next成员指向列表中的下一个条目；如果没有下一个条目，则为NULL列表中的条目.对于用作列表的SINGLE_LIST_ENTRY标头，则Next成员指向列表中的第一个条目，或者为NULL如果列表为空.
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.
我有99％的把握确定此列表包含一些条目，但是我不明白 0x0000000000220001 的值应该如何指向任何内容.这个值当然不能解析为有效的页面映射，因此我只能假定它是某种偏移量.但是，我不确定.
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.
谢谢
更新
我刚刚找到了一个文档(翻译成中文)，它似乎对结构有了更多的解释.如果有人可以提供一些意见，我将不胜感激.
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.
我实际上正在查看的是Windows应该用于分配IRP的后备列表，这是WinDBG的完整输出(值从原始问题更改):
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
对不起，如果某些格式丢失.本质上，这应该是一个后备列表，其中包含大小均相同的块列表 0x118(sizeof(_IRP)+ sizeof(_IO_STACK_LOCATION))
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.
推荐答案
如果Win7x86rtm的IRP列表较小:
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
内存块的大小为a0字节
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
其中包括池头，指针，irp，堆栈位置
which include pool header, pointer, irp, stack location
次要更新:
作者Tarjei Mandt aka @kernelpool
Author Tarjei Mandt aka @kernelpool
在 _GENERAL_LOOKASIDE 结构中，SingleListHead.Next指向单链接后备列表上的第一个空闲池块.后备列表的大小受Depth值的限制，该值由余额集管理器根据后备列表上的命中次数和未命中次数定期进行调整.因此，经常使用的后备列表将比不经常使用的列表具有更大的深度值.初始深度为4 nt！ExMinimumLookasideDepth ，最大值为 MaximumDepth (256)...
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
这篇关于Windows单链表(_SINGLE_LIST_ENTRY)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
