Delphi研究之驱动开发篇（五）--使用后备列表
作 者: mickeylan
时 间: 2008-02-03,11:24
链 接: http://bbs.pediy.com/showthread.php?t=59265
上篇教程我们介绍了驱动开发中如何使用系统内存堆，这一节让我们看看后备列表的使用。堆管理器管理着系统和用户堆，它把堆空间分为相同尺寸的块(block)。堆管理器会根据堆分配请求，去选择一个合适尺寸的未使用的块。显然，这个过程需要点时间。如果你需要固定尺寸的内存块，但是你事先并不知道它的大小和使用频率，这样的话为了性能的原因，你还是使用后备列表（Lookaside Lists）吧，后备列表是只有内核模式才有的。
后备列表和系统内存池的主要的区别是什么呢？后备列表只可以分配固定大小的事先定义尺寸的内存块。后备列表会快很多，因为它不需要去搜索可用的未分配的内存。
当你刚接触后备列表，你需要解决的问题不是怎么创建后备列表，而是管理你要分配的内存块。
具体来说，你把你要使用和释放的内存存贮在哪里? 怎么存贮？这不是个简单的问题，因为你不知道块的数量。有三种结构来解决这个问题：
◎ 单向链表(Singly linked list)
◎ S-list排序的单向链表（S-list, sequenced singly-linked list） (单向链表的改进)
◎ 双向链表（Doubly linked list）
我们将只接触双向链表，因为它最通用。
如果你是第一次接触后备列表和双向链表这些概念，你会觉得下面的代码有点复杂，但实际上它们是非常简单的。
后备列表（lookaside list）和双向链表（Doubly linked list）的英文名称都有一个"list"，但是它们是完全不同的。后备列表是一组事先分配的相同尺寸的内存块。这些块有些在使用，有些没被使用。当有内存分配请求的时候，系统会遍历这个列表寻找最近的未分配的块。如果未分配的块找到了，分配请求就很快被满足了。否则系统必须从分页或不分页内存池去分配。根据列表中分配行为发生的频率，系统会自动调整未分配块的数量来满足分配请求，分配的频率越高，会有越多的块被存储在后备列表中。后备列表如果总是不被使用，也会自动减少空间大小。
双向链表是数据组织的一种形式。可以很方便地把同类结构连接在一起，并且很容易遍历。双向链表被系统广泛地使用来处理内部结构。
我想了半天，也没有找到一个适合的简单的例子。所以下面这个驱动程序好像意义不大。但是可以帮助你理解相关的概念，还有双向链表。
这里也没有提供驱动控制程序。你可以使用KmdKit4D 包中的KmdManager 或者类似的工具，还可以使用DebugView或SoftICE 控制台来查看调试信息。
代码:unit LookasideList;
inte易做图ce
uses
nt_status, ntoskrnl, macros;
function _DriverEntry(pDriverObject: PDRIVER_OBJECT;
pusRegistryPath: PUNICODE_STRING): NTSTATUS; stdcall;
implementation
type
PSOME_STRUCTURE = ^SOME_STRUCTURE;
SOME_STRUCTURE = record
SomeField1: DWORD;
SomeField2: DWORD;
{ . . .} {这里放入一些别的字段}
ListEntry: LIST_ENTRY; {主角^_^，可以放在结构的开始}
{放在这里是为了演示的需要}
{ . . .} {这里放入一些别的字段}
SomeFieldX: DWORD;
end;
var
g_pPagedLookasideList: PPAGED_LOOKASIDE_LIST;
g_ListHead: LIST_ENTRY;
g_dwIndex: DWORD;
dwCnt: DWORD;
procedure AddEntry;
var
pEntry: PSOME_STRUCTURE;
begin
{从后备列表中分配内存块}
pEntry := ExAllocateFromPagedLookasideList(g_pPagedLookasideList);
if pEntry <> nil then
begin
DbgPrint(LookasideList: + Memory block allocated from lookaside list at address %08X#13#10, pEntry);
{初始化分配到的内存}
memset(pEntry, 0, sizeof(SOME_STRUCTURE));
{一个节点可以添加到链表的头部、尾部或者其他地方，视个人喜好了}
{本例添加到表头}
InsertHeadList(@g_ListHead, @pEntry^.ListEntry);
{使用SomeField1保存表项的索引. 这是为了让我们能看见它在工作.}
inc(g_dwIndex);
pEntry^.SomeField1 := g_dwIndex;
DbgPrint(LookasideList: + Entry #%d added#13#10, pEntry^.SomeField1);
end else
begin
DbgPrint(LookasideList: Very bad. Couldnt allocate from lookaside list#13#10);
end;
end;
procedure RemoveEntry;
var
pEntry, pTemp: pointer;
ss: SOME_STRUCTURE;
offs: DWORD;
begin
if IsListEmpty(@g_ListHead) <> TRUE then
begin
{删除表项也一样，可以从头、尾或者其他地方删除,}
{这里我们还是从头部开始删除.}
{计算offs是因为RemoveHeadList返回的是SOME_STRUCTURE.ListEntry的地址}
{offs就是SOME_STRUCTURE.ListEntry到结构开始处的偏移量}
offs := DWORD(@ss.ListEntry) - DWORD(@ss);
{这里pEntry ==> SOME_STRUCTURE.ListEntry}
{我们需要得到指向包含这个ListEntry的SOMT_STRUCTURE结构的指针}
{以便释放内存，用pEntry - offs即可得到结构的指针.}
pEntry := RemoveHeadList(@g_ListHead);
{pTemp ==> SOME_STRUCTURE，这里一定要弄明白}
pTemp := pointer(DWORD(pEntry) - offs);
DbgPrint(LookasideList: - Entry #%d removed#13#10,
PSOME_STRUCTURE(pTemp)^.SomeField1);
{向后备列表归还不用的内存}
ExFreeToPagedLookasideList(g_pPagedLookasideList, pTemp);
DbgPrint(LookasideList: - Memory block at address %08X returned to lookaside list#13#10, pTemp);
end else
begin
&n
补充：软件开发 , Delphi ,
