WRK: 对后备列表（Lookaside List）的机制分析

　　在Windows下开发内核程序，后备列表（Lookaside List）提供了一个比较简单的提高小块内存分配和申请效率的机制。根据DDK上的描述，后备列表用来进行固定大小内存块的动态申请和释放。并且在很多资料上，（比如KmdTut）在描述后备列表时会提到，Windows每一秒会对后备列表进行一次调整，根据后备列表的使用频度调整其深度。

　　原理

　　后备列表的原理很简单，就是一个控制结构头和一个由相同大小的内存块构成的单链表组成。在控制结构中，记录着当前后备列表的深度和最大深度。在通过ExAllocateFrom(N)PagedLookasideList申请内存的时候，如果单链表不为空，那么就从头部摘出一块返回，否则使用ExAllocatePoolWithTag或者在初始化后备列表时提供的分配函数申请一个内存块返回给用户；在通过ExFreeTo(N)PagedLookasideList释放之前申请的内存块时，如果后备列表当前的深度没有超过最大深度，那么插入到内存块头部，否则使用ExFreePoolWithTag或在初始化后备列表时提供的释放函数释放内存块。

　　由上可以看出，在调整后备列表深度时，只需调整管理结构的最大深度就可以了。事实上，在WRK中就是这么做的。初始化后备列表时，仅仅初始化了管理结构，至于内存块链表里的内存块，都是应用程序释放后加入的。

　　实现

　　先看一下数据结构，由于都是自注释的，就不解释了，反正就算有看不懂的也没涉及。

typedef struct DECLSPEC_CACHEALIGN _GENERAL_LOOKASIDE {

    SLIST_HEADER ListHead;
    USHORT Depth;
    USHORT MaximumDepth;
    ULONG TotalAllocates;
    union {
        ULONG AllocateMisses;
        ULONG AllocateHits;
    };

    ULONG TotalFrees;
    union {
        ULONG FreeMisses;
        ULONG FreeHits;
    };

    POOL_TYPE Type;
    ULONG Tag;
    ULONG Size;
    PALLOCATE_FUNCTION Allocate;
    PFREE_FUNCTION Free;
    LIST_ENTRY ListEntry;
    ULONG LastTotalAllocates;
    union {
        ULONG LastAllocateMisses;
        ULONG LastAllocateHits;
    };

    ULONG Future[2];
} GENERAL_LOOKASIDE, *PGENERAL_LOOKASIDE;

typedef struct _PP_LOOKASIDE_LIST {
    struct _GENERAL_LOOKASIDE *P;
    struct _GENERAL_LOOKASIDE *L;
} PP_LOOKASIDE_LIST, *PPP_LOOKASIDE_LIST;

　　在WRK中，后备列表相关的函数实现位于base\ntos\ex\lookasid.c；GENERAL_LOOKASIDE结构的定义位于base\ntos\inc\ex.h，这里包含了一个后备列表的管理信息；PP_LOOKASIDE_LIST结构定义于base\ntos\inc\ntosdef.h，在PRCB（处理器控制块，Processor Control Block）中用来提高内核内存池处理内存申请和分配的效率。

FORCEINLINE VOID ExpComputeLookasideDepth ( IN PGENERAL_LOOKASIDE Lookaside, IN ULONG Misses, IN ULONG ScanPeriod )

　　调整后备列表深度的函数见上，其大致原理为：

　　如果ExMinimumLookasideDepth为0，则说明使用了Verifier，在这种情况下后备列表将被禁用，其深度将被设置为0；

　　如果ExMinimumLookasideDepth不为0，那么：

if Allocates < (ScanPeriod * MINIMUM_ALLOCATION_THRESHOLD) then
    Depth = min(Depth-10, MINIMUM_ALLOCATION_DEPTH);
else
    Allocates = Lookaside->TotalAllocates – Lookaside->LastTotalAllocates;
    Ratio = Misses * 1000 / Allocates;
    if Ratio < 5 then
        Depth = min(Depth-1, MINIMUM_LOOKASIDE_DEPTH);
    else
        Delta = min(30, Ratio *(MaximumDepth – Depth)/2000 + 5;
        Depth = min(Depth+delta, MaximumDepth);

　　那么，ExpComputeLookasideDepth是如何找到所有的后备列表呢？在base\ntos\ex\lookasid.c定义了四个单链表：ExNPagedLookasideListHead、ExPagedLookasideListHead、ExPoolLookasideListHead和ExSystemLookasideListHead。

　　Ex(N)PagedLookasideListHead用来保存用户定义的后备列表，（此操作在初始化后备列表的管理结构时进行，ExInitialize(N)PagedLookasideList）ExPoolLookasideListHead用来保存PRCB中的PP(N)PagedLookasideList，ExSystemLookasideListHead用来保存PRCB中的PPLookasideList和其它一些后备列表。

　　调整后备列表的操作由Balance Set Manager（base\ntos\ke\balmgr.c）在一个单独的系统进程中调用，它每一秒调用一次ExAdjustLookasideDepth。ExAdjustLookasideDepth按3秒为一个周期，分别对ExPagedLookasideListHead、ExNPagedLookasideListHead和系统后备列表进行调整。系统后备列表不仅包括上文提到的ExPoolLookasideListHead和ExSystemLookasideListHead，还包括在base\ntos\ex\lookasid.c定义的ExpSmall(N)PagedPoolLookasideLists两个链表。

　　调整的算法如前所述，其中比较奇怪的一点是，ExPoolLookasideListHead并未在ExAdjustLookasideDepth被引用，而是直接引用PRCB中的PP(N)PagedLookasideList；另外在PP_LOOKASIDE_LIST结构中有两个GENERAL_LOOKASIDE指针P&L，但却只对PRCB里PP(N)PagedLookasideList中P指向的后备列表进行深度调整。

　　在Kernel Memory Pool中的使用

　　在使用ExAllocatePoolWithTag申请内存时，系统会首先尝试从PRCB中的PP(N)PagedLookasideList。PRCB中的后备列表中保存了大小从0 × 8B到POOL_SMALL_LISTS(32) × 8B的后备列表。在分配内存时，后备列表中的内存块只满足大小符合的要求，否则不予处理。（申请的大小先按8字节对齐）

　　因为在PRCB中使用的每个PP_LOOKASIDE_LIST有两个指针P&L，在申请时将先尝试P指向的GENERAL_LOOKASIDE，失败后再尝试L指向的GENERAL_LOOOKASIDE；如果再失败，则通过正常方式从内存池中申请内存。在释放内存时也是同样。

　　其他的一些说明

　　ExMinimumLookasideDepth是一个全局变量，用来控制后备列表的最小深度，后备列表在初始化时的深度会被设为此值。

　　PRCB中的PP(N)PagedLookasideList在Phase 0使用ExpSmall(N)PagedPoolLookasideLists进行初始化，每一项的P&L都指向同一个GENERAL_LOOKASIDE；在Phase 1的时候，PP(N)PagedLookasideList会被重新初始化，这时P&L将指向两个不同的后备列表。

　　Verifier的介绍请参见Windows Internal一书，本文暂不做说明，留到写Memory Pool一文再做说明。

　　PS. 后备列表的译名来自KmdTut，潘爱民书中的“快查表”和软件调试中的“旁视列表”两个翻译实在太难听了。