驱动开发学习笔记(3-8)–Four-F的驱动开发教程-后备列表

在这里下载本文的源代码

7. 后备列表

本篇翻译:songsong <http://www.songsong.org>
源代位置:KmdKit\examples\basic\MemoryWorks\LookasideList

我回来了,对门的那个白人MM听说我是黑客(其实长得黑而已)对我特崇拜,差点要以身相许,幸亏咱意志坚定……
好了,我们开始最后一节了,你能读完并理解,你就是高手了……

7.1 后备列表

堆管理器管理着系统和用户堆,它把堆空间分为相同尺寸的块(block)。堆管理器会根据堆分配请求,去选择一个合适尺寸的未使用的块。显然,这个过程需要点时间。如果你需要固定尺寸的内存块,但是你事先并不知道它的大小和使用频率,这样的话为了性能的原因,你还是使用后备列表(Lookaside Lists)吧,后备列表是只有内核模式才有的。
后备列表和系统内存池的主要的区别是什么呢?后备列表只可以分配固定大小的事先定义尺寸的内存块。后备列表会快很多,因为它不需要去搜索可用的未分配的内存。
当你刚接触后备列表,你需要解决的问题不是怎么创建后备列表,而是管理你要分配的内存块。
具体来说,你把你要使用和释放的内存存贮在哪里? 怎么存贮?这不是个简单的问题,因为你不知道块的数量。有三种结构来解决这个问题:
◎ 单向链表(Singly linked list)
◎ S-list排序的单向链表(S-list, sequenced singly-linked list) (单向链表的改进)
◎ 双向链表(Doubly linked list)

我们将只接触双向链表,因为它最通用。
如果你是第一次接触后备列表和双向链表这些概念,你会觉得下面的代码有点复杂,但实际上它们是非常简单的。
后备列表(lookaside list)和双向链表(Doubly linked list)的英文名称都有一个”list”,但是它们是完全不同的。后备列表是一组事先分配的相同尺寸的内存块。这些块有些在使用,有些没被使用。当有内存分配请求的时候,系统会遍历这个列表寻找最近的未分配的块。如果未分配的块找到了,分配请求就很快被满足了。否则系统必须从分页或不分页内存池去分配。根据列表中分配行为发生的频率,系统会自动调整未分配块的数量来满足分配请求,分配的频率越高,会有越多的块被存储在后备列表中。后备列表如果总是不被使用,也会自动减少空间大小。
双向链表是数据组织的一种形式。可以很方便地把同类结构连接在一起,并且很容易遍历。双向链表被系统广泛地使用来处理内部结构。

7.2 后备列表驱动程序源代码

我想了半天,也没有找到一个适合的简单的例子。所以下面这个驱动程序好像意义不大。但是可以帮助你理解相关的概念,还有双向链表。
这里也没有提供驱动控制程序。你可以使用KmdKit 包中的KmdManager 或者类似的工具,还可以使用DebugView ( http://www.sysinternals.com ) 或 SoftICE 控制台来查看调试信息。

;@echo off
;goto make

;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
;  LookasideList - Merely allocates and releases some fixed-size blocks of memory.
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.486
.model flat, stdcall
option casemap:none
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
;                                 I N C L U D E   F I L E S
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
include \masm32\include\w2k\ntstatus.inc
include \masm32\include\w2k\ntddk.inc
include \masm32\include\w2k\ntoskrnl.inc
includelib \masm32\lib\w2k\ntoskrnl.lib
include \masm32\Macros\Strings.mac
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
;                                  S T R U C T U R E S
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
SOME_STRUCTURE STRUCT
    SomeField1    DWORD        ?
    SomeField2    DWORD        ?
    ; . . .                          ; Any other fields come here
    ListEntry    LIST_ENTRY    <>    ; For tracking memory blocks.
                                     ; It can be the first member but
                                     ; to place it into is more common solution.
    ; . . .                          ; Any other fields come here
    SomeFieldX    DWORD        ?
SOME_STRUCTURE ENDS
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
;                          U N I N I T I A L I Z E D  D A T
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.data?
g_pPagedLookasideList    PPAGED_LOOKASIDE_LIST    ?
g_ListHead               LIST_ENTRY               <>
g_dwIndex                DWORD                    ?
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
;                                         C O D E
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.code
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
;                                         AddEntry
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
AddEntry proc uses esi

    invoke ExAllocateFromPagedLookasideList, g_pPagedLookasideList
    .if eax != NULL
        mov esi, eax
        invoke DbgPrint, \
               $CTA0("LookasideList: + Memory block allocated from lookaside list at address %08X\n"), esi

        invoke memset, esi, 0, sizeof SOME_STRUCTURE

        assume esi:ptr SOME_STRUCTURE
        lea eax, g_ListHead
        lea ecx, [esi].ListEntry
        InsertHeadList eax, ecx

        inc g_dwIndex
        mov eax, g_dwIndex
        mov [esi].SomeField1, eax

        invoke DbgPrint, $CTA0("LookasideList: + Entry #%d added\n"), [esi].SomeField1
        assume esi:nothing
    .else
        invoke DbgPrint, $CTA0("LookasideList: Very bad. Couldn't allocate from lookaside list\n")
    .endif
    ret

AddEntry endp
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
;                                       RemoveEntry
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
RemoveEntry proc uses esi

    IsListEmpty addr g_ListHead
    .if eax != TRUE

        lea eax, g_ListHead
        RemoveHeadList eax
        sub eax, SOME_STRUCTURE.ListEntry
        mov esi, eax
        invoke DbgPrint, $CTA0("LookasideList: - Entry #%d removed\n"), \
                            (SOME_STRUCTURE PTR [esi]).SomeField1
        invoke ExFreeToPagedLookasideList, g_pPagedLookasideList, esi
        invoke DbgPrint, \
            $CTA0("LookasideList: - Memory block at address %08X returned to lookaside list\n"), esi
    .else
        invoke DbgPrint, \
            $CTA0("LookasideList: An attempt was made to remove entry from empty lookaside list\n")
    .endif

    ret

RemoveEntry endp
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
;                                       DriverEntry
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
DriverEntry proc uses ebx pDriverObject:PDRIVER_OBJECT, pusRegistryPath:PUNICODE_STRING

    invoke DbgPrint, $CTA0("\nLookasideList: Entering DriverEntry\n")
    invoke ExAllocatePool, NonPagedPool, sizeof PAGED_LOOKASIDE_LIST
    .if eax != NULL
        mov g_pPagedLookasideList, eax

        invoke DbgPrint, \
        $CTA0("LookasideList: Nonpaged memory for lookaside list allocated at address %08X\n"), \
        g_pPagedLookasideList
        invoke ExInitializePagedLookasideList, g_pPagedLookasideList, NULL, NULL, \
                                               0, sizeof SOME_STRUCTURE, 'msaW', 0
        invoke DbgPrint, $CTA0("LookasideList: Lookaside list initialized\n")
        lea eax, g_ListHead
        InitializeListHead eax
        invoke DbgPrint, $CTA0("LookasideList: Doubly linked list head initialized\n")
        invoke DbgPrint, $CTA0("\nLookasideList: Start to allocate/free from/to lookaside list\n")
        and g_dwIndex, 0
        xor ebx, ebx
        .while ebx < 5
            invoke AddEntry
            invoke AddEntry

            invoke RemoveEntry
            inc ebx
        .endw
        invoke DbgPrint, $CTA0("\nLookasideList: Free the rest to lookaside list\n")
        .while TRUE
            invoke RemoveEntry
            lea eax, g_ListHead
            IsListEmpty eax
            .if eax == TRUE
                invoke DbgPrint, $CTA0("LookasideList: Doubly linked list is empty\n\n")
                .break
            .endif
        .endw
        invoke ExDeletePagedLookasideList, g_pPagedLookasideList
        invoke DbgPrint, $CTA0("LookasideList: Lookaside list deleted\n")
        invoke ExFreePool, g_pPagedLookasideList
        invoke DbgPrint, \
        $CTA0("LookasideList: Nonpaged memory for lookaside list at address %08X released\n"), \
        g_pPagedLookasideList
    .else
        invoke DbgPrint, \
 		$CTA0("LookasideList: Couldn't allocate nonpaged memory for lookaside list control structure")
    .endif
    invoke DbgPrint, $CTA0("LookasideList: Leaving DriverEntry\n")
    mov eax, STATUS_DEVICE_CONFIGURATION_ERROR
    ret

DriverEntry endp
;:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
end DriverEntry

:make
set drv=LookasideList
\masm32\bin\ml /nologo /c /coff %drv%.bat
\masm32\bin\link /nologo /driver /base:0x10000 /align:32 /out:%drv%.sys /subsystem:native %drv%.obj
del %drv%.obj
echo.
pause

7.3 使用后备列表

invoke ExAllocatePool, NonPagedPool, sizeof PAGED_LOOKASIDE_LIST
.if eax != NULL
        mov g_pPagedLookasideList, eax

我们分配PAGED_LOOKASIDE_LIST结构的非分页内存,这个结构用于管理后备列表,并把指针保存在变量g_pPagedLookasideList中。注意:后备列表自身是可以分页的。例如,我们获取的内存可能被页出(page out)。文档关于这一点写的很清楚。

        invoke ExInitializePagedLookasideList, g_pPagedLookasideList, NULL, NULL, \
                                                0, sizeof SOME_STRUCTURE, 'msaW', 0

ExInitializePagedLookasideList函数初始化我们上一步分配的PAGED_LOOKASIDE_LIST结构。这样后备列表就可以使用了。
注意,在初始化时候,我们并没有指定我们需要多少块。那么系统怎么知道要准确地分配多少内存呢?实际上,内存如果事先没有分配,后备列表就不可能比常用的系统内存池要快了。问题就在于:开始的时候,系统分配只一点内存块(数量由系统来定义)。于是当我们开始从后备列表分配内存的时候,我们将获得这些预分配内存块的指针。每秒钟,系统都会调用ExAdjustLookasideDepth来调整所有的系统后备列表。调整的时候发现空闲的未分配块减少,系统就会分配新的内存块。这些额外分配的块的数量来自于后备列表的负载情况,例如:分配频率。系统会尽量调整让后备列表更有效。
如果我们在调整时间内就耗尽了预分配内存块,系统就使用系统内存池,直到下一次调整。需要理解的一个重要问题是:如果内存分配速度太高,那么跟内存池分配方式比,就没有性能的优势了。你可以使用MS Kernel Debugger的命令”!lookaside”,评估你的后备列表的效率。

kd> !lookaside ed374840

Lookaside "" @ ed374840 "Regm"
    Type     =     0001 PagedPool
    Current Depth  =        2   Max Depth  =        4
    Size           =     1024   Max Alloc  =     4096
    AllocateMisses =        4   FreeMisses =        0
    TotalAllocates =  1319722   TotalFrees =  1319720
    Hit Rate       =       99%  Hit Rate   =      100%

我们来看看一个工具RegMon ( http://www.sysinternals.com ) 后备列表的使用效率吧。 当你看到效率到达100%的时候,这表示有大量(一百万以上)的alloc/free操作。原因是RegMon没有长时间地保留分配的块。

lea eax, g_ListHead
InitializeListHead eax
我们可以调用InitializeListHead这个宏来双向链表的头。现在LIST_ENTRY的两个域都包含了到结构自身的指针。这说明了双向链表是空的(见图7.1中的1)。

图7.1 这个图帮你清楚地理解双向链表是怎么运行的。

and g_dwIndex, 0

这个全局变量仅用来在后备列表分配的SOME_STRUCTURE结构里放些内容,然后在调试信息里输出值来。

        xor ebx, ebx
        .while ebx < 5
            invoke AddEntry
            invoke AddEntry
            invoke RemoveEntry
            inc ebx
        .endw

循环5次。每次增加两个条目,删除一个条目。每个条目代表了某个结构。所有分配的结构都使用双向链表互相链接在一起。
这个循环模拟了后备列表的随机分配过程。我们可以假设是为了保存一些数据而进行分配内存工作。如写一个驱动程序来截取某系统设备的调用(如截取ZwOpenKey)时将截取的信息保存到分配的内存中,这时的内存分配动作就是类似的。

        .while TRUE
            invoke RemoveEntry
            lea eax, g_ListHead
            IsListEmpty eax
            .if eax == TRUE
                .break
            .endif
        .endw

现在我们有了一些用双向链表链接起来的后备列表条目分配块。我们假设我们又不需要他们了……
我们在一个无限循环里调用RemoveEntry函数。RemoveEntry从双向链表头删除一个条目,并释放回后备列表。这个循环一直运行,直到双向链表成空。可以使用IsListEmpty宏来检查这个状态。IsListEmpty检查双向链表头(LIST_ENTRY structure)的两个域是不是都指向链表头自己。
这时,我们又回到了执行完InitializeListHead宏的状态了(参见图7.1的1)。

invoke ExDeletePagedLookasideList, g_pPagedLookasideList

由于我们使用双向链表来管理后备列表的分配,当双向链表为空的时候,所有后备列表分配的条目都被归还。现在我就可以调用ExDeletePagedLookasideList来删除后备列表。这就释放了所有剩余的后备列表条目,然后删除了系统范围的活动的后备列表。

invoke ExFreePool, g_pPagedLookasideList

ExFreePool 释放了为PAGED_LOOKASIDE_LIST结构分配的不分页内存。如果你忘记了事先调用ExDeletePagedLookasideList,你将会看见BSOD, 因为一秒左右,系统就会调整丢失的后备列表。

mov eax, STATUS_DEVICE_CONFIGURATION_ERROR
ret

由于我们释放了所有分配的资源,我们就可以卸载驱动程序了。
以上内容很简单,尤其如果你学过《数据结构》这门课,或者以前接触过链表和队列这类概念的话。

7.4 AddEntry 函数

当我们需要一个新的内存块的时候我们调用AddEntry。它会从后备列表分配一个新的条目,并增加到双向链表。

    invoke ExAllocateFromPagedLookasideList, g_pPagedLookasideList
    .if eax != NULL
        mov esi, eax

我们调用ExAllocateFromPagedLookasideList就可以获得新的内存块指针,并保存在esi中。注意:我们没有告诉系统块的尺寸,因为尺寸在调用ExInitializePagedLookasideList就被定义–等于SOME_STRUCTURE的尺寸。

invoke memset, esi, 0, sizeof SOME_STRUCTURE

把内存块置零。这一步也许不需要。

assume esi:ptr SOME_STRUCTURE

现在我们有了一个新的SOME_STRUCTURE实例。我们就可以把它链到我们的双向链表了。在AddEntry第一次运行之前,双向链表还是空的。

lea eax, g_ListHead
lea ecx, [esi].ListEntry
InsertHeadList eax, ecx

图7.1的2描述了在第一个InsertHeadList宏调用后的状态。注意InsertHeadList宏的第二个参数,它不是SOME_STRUCTURE的地址,而是它的ListEntry域的地址。例如:InsertHeadList宏接收了这两个LIST_ENTRY 结构的地址,第一个是双向链表的头,第二个是我们需要链到这个双向链表的结构成员。InsertHeadList 链接这个新结构到双向链表的头(看图7.1的3的右边)。你可以使用InsertTailList宏链接到尾部。
如果你是往双向链表里第一次加条目,两个宏都产生同样的结果。以后就会象图7.1的2反映的那样了。
如果当时双向链表不是空的话,InsertHeadList宏就会在头部和条目右边之间分开双向链表,然后把新条目放在中间(见图7.1的3)如果在尾部,也可以用InsertTailList,效果一样。
现在一切都很清楚了吧。

inc g_dwIndex
mov eax, g_dwIndex
mov [esi].SomeField1, eax

我们在SomeField1保存新创建的表目的编号。你在DbgView中可以清楚地看到这些结构被增加和删除的顺序。

7.5 RemoveEntry函数

RemoveEntry 函数和AddEntry相反。它把条目从双向链表头中解除链接,然后归还到后备列表。

IsListEmpty addr g_ListHead
.if eax != TRUE

确定双向链表是空的。

lea eax, g_ListHead
RemoveHeadList eax

RemoveHeadList 把条目从双向链表中解除链接。你应该已经猜到RemoveTailList宏在尾部的时候可以做同样的事情了。而RemoveEntryList可以删除任何条目(当然包括尾部了)。
这时,被解除的条目就独立存在了,双向链表把随后其余的条目链接在一起。

sub eax, SOME_STRUCTURE.ListEntry
mov esi, eax

注意这里:RemoveTailList/RemoveHeadList/RemoveEntryList返回了一个指针,这个指针指向了链表的头部或尾部或中间的条目(嵌入的LIST_ENTRY 结构),却不会指向解除链接的SOME_STRUCTURE结构自身。这些宏不知道LIST_ENTRY在结构中的确切位置,也没有办法知道。这全靠你去计算ListEntry域在SOME_STRUCTURE里的偏移,来获得指向自身结构的指针了(DDK中的CONTAINING_RECORD宏做这个事情)。

invoke ExFreeToPagedLookasideList, g_pPagedLookasideList, esi

ExFreeToPagedLookasideList 将这个条目归还到后备列表或分页内存池。

全文结束,很荣幸有机会和罗大哥合作翻译此文。感谢大家读完此文,如果您发现有翻译错误,请来email(songsongorg@hotmail.com)指正–songsong

(另:本篇教程英文版的部分就到这里了,但是俄文版的后面还有好几篇,可惜大家都不懂俄文了,有没有懂俄文的自告奋勇翻译一番呢~~~~俄文原文见http://www.wasm.ru/)

原文链接:http://211.90.241.130:22366/view.asp?file=326

☆版权☆

* 网站名称:obaby@mars
* 网址:https://oba.by/
* 个性:https://oba.by/
* 本文标题: 《驱动开发学习笔记(3-8)–Four-F的驱动开发教程-后备列表》
* 本文链接:https://zhongxiaojie.com/2009/09/295
* 短链接:https://oba.by/?p=295
* 转载文章请标明文章来源,原文标题以及原文链接。请遵从 《署名-非商业性使用-相同方式共享 2.5 中国大陆 (CC BY-NC-SA 2.5 CN) 》许可协议。


You may also like

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注