Windows驱动之LOOKASIDE LIST详解

如果在Windows驱动开发中，需要用到频繁申请相同大小的内存的话，一般推荐使用LOOKASIDE_LIST，这样可以避免产生内存空洞。那么LOOKASIDE_LIST是怎么样保证不会产生内存空洞的呢？本来详细讨论一个LOOKASIDE_LIST的原理。

本文都是以PAGED_LOOKASIDE_LIST来分析。

1. 初始化

在分析之前，我们看下NPAGED_LOOKASIDE_LIST的具体结构，如下：

typedef struct _GENERAL_LOOKASIDE {
    SLIST_HEADER ListHead;  //内存链表
    USHORT Depth;  //当前内存列表的最大深度
    USHORT MaximumDepth;  //整个look aside运行的最大深度
    ULONG TotalAllocates;   //总共分配了多少次内存
    union {
        ULONG AllocateMisses;  //分配失败的内存，通过Allocate分配
        ULONG AllocateHits;
    };

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

    POOL_TYPE Type;
    ULONG Tag;
    ULONG Size;
    PALLOCATE_FUNCTION Allocate;   //分配函数
    PFREE_FUNCTION Free;  //释放函数sss
    LIST_ENTRY ListEntry;  //ExNPagedLookasideListHead链表
    ULONG LastTotalAllocates;
    union {
        ULONG LastAllocateMisses;
        ULONG LastAllocateHits;
    };

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

typedef struct _NPAGED_LOOKASIDE_LIST {
    GENERAL_LOOKASIDE L;
    KSPIN_LOCK Lock;
} NPAGED_LOOKASIDE_LIST, *PNPAGED_LOOKASIDE_LIST;

初始化函数使用ExInitializeNPagedLookasideList来完成，主要就是用来初始化上面的NPAGED_LOOKASIDE_LIST结构，我们看下这个函数的流程：

VOID
ExInitializeNPagedLookasideList (
    IN PNPAGED_LOOKASIDE_LIST Lookaside,
    IN PALLOCATE_FUNCTION Allocate,
    IN PFREE_FUNCTION Free,
    IN ULONG Flags,
    IN SIZE_T Size,
    IN ULONG Tag,
    IN USHORT Depth
    )
{

    ExInitializeSListHead(&Lookaside->L.ListHead);
    Lookaside->L.Depth = MINIMUM_LOOKASIDE_DEPTH;
    Lookaside->L.MaximumDepth = 256; //Depth;
    Lookaside->L.TotalAllocates = 0;
    Lookaside->L.AllocateMisses = 0;
    Lookaside->L.TotalFrees = 0;
    Lookaside->L.FreeMisses = 0;
    Lookaside->L.Type = NonPagedPool | Flags;
    Lookaside->L.Tag = Tag;
    Lookaside->L.Size = (ULONG)Size;
    if (Allocate == NULL) {
        Lookaside->L.Allocate = ExAllocatePoolWithTag;

    } else {
        Lookaside->L.Allocate = Allocate;
    }

    if (Free == NULL) {
        Lookaside->L.Free = ExFreePool;

    } else {
        Lookaside->L.Free = Free;
    }

    Lookaside->L.LastTotalAllocates = 0;
    Lookaside->L.LastAllocateMisses = 0;
    KeInitializeSpinLock(&Lookaside->Lock);

    ExInterlockedInsertTailList(&ExNPagedLookasideListHead,
                                &Lookaside->L.ListEntry,
                                &ExNPagedLookasideLock);
    return;
}

这里做了两个事情：

初始化一个PNPAGED_LOOKASIDE_LIST结构。
将Lookaside->L.ListEntry插入到全局的look aside 表ExNPagedLookasideListHead中。

2. 内存分配

分配内存的函数为ExAllocateFromNPagedLookasideList,这个函数流程如下：

PVOID
ExAllocateFromNPagedLookasideList(
    IN PNPAGED_LOOKASIDE_LIST Lookaside
    )
{

    PVOID Entry;

    Lookaside->L.TotalAllocates += 1;
    Entry = ExInterlockedPopEntrySList(&Lookaside->L.ListHead, &Lookaside->Lock);
    if (Entry == NULL) {
        Lookaside->L.AllocateMisses += 1;
        Entry = (Lookaside->L.Allocate)(Lookaside->L.Type,
                                        Lookaside->L.Size,
                                        Lookaside->L.Tag);
    }

    return Entry;
}

Lookaside->L.TotalAllocates += 1; 每次分配都增加一次分配次数。
Entry = ExInterlockedPopEntrySList(&Lookaside->L.ListHead, &Lookaside->Lock); 从Lookaside取出一个节点，其实就代表着需要申请的内存。
如果申请失败，那么Lookaside->L.AllocateMisses += 1;增加申请失败的次数。
Entry = (Lookaside->L.Allocate)(Lookaside->L.Type, 调用分配函数分配内存。

从这里看，也就是说look aside是先从预先保留的队列中取出一个内存节点，如果没有预留的内存节点，那么就调用分配函数分配内存。

3. 释放

当不在使用内存的时候，就会释放内存到look aside，那么释放的时候是将内存交给谁了呢？我们看下流程：

VOID
ExFreeToNPagedLookasideList(
    IN PNPAGED_LOOKASIDE_LIST Lookaside,
    IN PVOID Entry
    )
{

    Lookaside->L.TotalFrees += 1;
    if (ExQueryDepthSList(&Lookaside->L.ListHead) >= Lookaside->L.Depth) {
        Lookaside->L.FreeMisses += 1;
        (Lookaside->L.Free)(Entry);

    } else {
        ExInterlockedPushEntrySList(&Lookaside->L.ListHead,
                                    (PSINGLE_LIST_ENTRY)Entry,
                                    &Lookaside->Lock);
    }

    return;
}

Lookaside->L.TotalFrees += 1; 释放次数加1；
ExQueryDepthSList(&Lookaside->L.ListHead) >= Lookaside->L.Depth 判断当前look aside中的内存数目是否大运最大的Depth（初始化的时候是4，也就是说look aside 刚开始只能放4块内存）。
如果已经超出Depth，那么Lookaside->L.FreeMisses += 1;记录失败的数目，并且调用(Lookaside->L.Free)(Entry)释放内存到系统中。
否则，直接调用ExInterlockedPushEntrySList(&Lookaside->L.ListHead将内存插入到look aside中保存。

从上面的分配和释放我们可以看到，look aside能够防止内存空洞主要的原理是在look aside中保存了最大Depth中的内存块数目，如果申请的话，直接从look aside中取出节点；如果释放，也是交给Depth，这样做到不操作真实的内存分配器来减少从Windows堆中分配内存。

但是这我们看到了一个局限性，也就是说，look aside只能分配指定大小的内存。

4. 深度的调整

在Windows中有一个内存平衡线程，会扫描ExNPagedLookasideListHead,根据不同的策略来调整Depth，调整过程如下：

LOGICAL
ExpScanPoolLookasideList (
    IN PLIST_ENTRY ListHead
    )
{

    ULONG Allocates;
    LOGICAL Changes;
    PNPAGED_LOOKASIDE_LIST Lookaside;
    PLIST_ENTRY NextEntry;
    ULONG Misses;

    Changes = FALSE;
    NextEntry = ListHead->Flink;
    while (NextEntry != ListHead) {
        Lookaside = CONTAINING_RECORD(NextEntry,
                                      NPAGED_LOOKASIDE_LIST,
                                      L.ListEntry);

        Allocates = Lookaside->L.TotalAllocates - Lookaside->L.LastTotalAllocates;
        Lookaside->L.LastTotalAllocates = Lookaside->L.TotalAllocates;
        Misses = Allocates - (Lookaside->L.AllocateHits - Lookaside->L.LastAllocateHits);
        Lookaside->L.LastAllocateHits = Lookaside->L.AllocateHits;

        Changes |= ExpComputeLookasideDepth(Allocates,
                                            Misses,
                                            Lookaside->L.MaximumDepth,
                                            &Lookaside->L.Depth);

        NextEntry = NextEntry->Flink;
    }

    return Changes;
}
LOGICAL
ExpComputeLookasideDepth (
    IN ULONG Allocates,
    IN ULONG Misses,
    IN USHORT MaximumDepth,
    IN OUT PUSHORT Depth
    )
{

    LOGICAL Changes;
    ULONG Ratio;
    ULONG Target;

    Changes = FALSE;
    if (Misses >= Allocates) {
        Misses = Allocates;
    }

    if (Allocates == 0) {
        Allocates = 1;
    }

    Ratio = (Misses * 1000) / Allocates;
    Target = *Depth;
    if ((Allocates / ExpAdjustScanPeriod) < MINIMUM_ALLOCATION_THRESHOLD) {
        if (Target > (MINIMUM_LOOKASIDE_DEPTH + 10)) {
            Target -= 10;

        } else {
            Target = MINIMUM_LOOKASIDE_DEPTH;
        }

    } else if (Ratio < 5) {
        if (Target > (MINIMUM_LOOKASIDE_DEPTH + 1)) {
            Target -= 1;

        } else {
            Target = MINIMUM_LOOKASIDE_DEPTH;
        }

    } else {
        Changes = TRUE;
        Target += ((Ratio * MaximumDepth) / (1000 * 2)) + 5;
        if (Target > MaximumDepth) {
            Target = MaximumDepth;
        }
    }

    *Depth = (USHORT)Target;
    return Changes;
}

具体的算法细节不深究，因为没有太大的意义，但是我们可以看到大致的计算原理是通过分配失败次数进行比例计算，然后设置好深度。

5. 总结

从上面分析，我们可以得出来，look aside的内存结构如下：

在这里插入图片描述

我们操作内存的时候，都是优先从look aside中的缓存内存块中操作，减少真实的内存访问，带来两个好处：

增加效率。
减少内存分配次数，降低内存碎片。

但是有一个缺点，就是会增加额外的内存开销。

原文链接：https://blog.csdn.net/xiangbaohui/article/details/104878403