首页 > WinDriver > WD-非/换页内存池管理算法(WRK)
2015四月12

WD-非/换页内存池管理算法(WRK)

[隐藏]

换页内存池和非换页内存池是提供给系统内核模块和设备驱动程序使用的。在换页内存池中分配的内存有可能在物理内存紧缺的情况下被换出到外存中;而非换

页内存池中分配的内存总是处于物理内存中。

在换页内存池中分配的内存有可能在物理内存紧缺的情况下被换出到外存中;而非换页内存池中分配的内存总是处于物理内存中。为了实现这两种内存池,Windows使用了层内存管理。下层是基于页面的内存管理,仅限于执行体内部使用;上层建立在下层的内存管理功能基础之上,对外提供各种粒度的内存服务。两层的结构如下图所示(这里不考虑会话空间的内存管理)。

  

1.非换页内存池管理算法

MiInitMachineDependent函数调用了MiInitializeNonPagedPool和MiInitializeNonPagedPoolThresholds函数来初始化非换页内存池的管理信息。

1
2
3
4
5
6
    //
    // Non-paged pages now exist, build the pool structures.
    //
 
    MiInitializeNonPagedPool ();
    MiInitializeNonPagedPoolThresholds ();

MiInitializeNonPagedPool的主要任务是初始化用于管理内存池的一些全局变量,尤其是用于存放空闲页面链表头的MmNonPagedPoolFreeListHead数组

1
2
3
4
5
6
7
    //
    // Initialize the list heads for free pages.
    //
 
    for (Index = 0; Index < MI_MAX_FREE_LIST_HEADS; Index += 1) {
        InitializeListHead (&MmNonPagedPoolFreeListHead[Index]);
    }
#define MI_MAX_FREE_LIST_HEADS  4
LIST_ENTRY MmNonPagedPoolFreeListHead[MI_MAX_FREE_LIST_HEADS];

从对MmNonPagedPoolFreeListHead的引用可知它的每一项都是一个MMFREE_POOL_ENTRY结构,其定义如下:

//
// System PTE structures.
//

typedef struct _MMFREE_POOL_ENTRY {
    LIST_ENTRY List;        // maintained free&chk, 1st entry only
    PFN_NUMBER Size;        // maintained free&chk, 1st entry only
    ULONG Signature;        // maintained chk only, all entries
    struct _MMFREE_POOL_ENTRY *Owner; // maintained free&chk, all entries
} MMFREE_POOL_ENTRY, *PMMFREE_POOL_ENTRY;

在初始化状态下,整个非换页池空间,即从MmNonPagedPoolStart开始,一共有MmSizeOfNonPagedPoolInBytes 大小的内存,所有的页面均加入第一个页面所在的MMFREE_POOL_ENTRY项。 MmNonPagedPoolFreeListHead数组在默认情况下包括MI_MAX_FREE_LIST_HEADS(4)项:

第一个数组项包含所有单个空闲页面的MMFREE_POOL_ENTRY项。
第二个数组项包含所有2个空闲页面的MMFREE_POOL_ENTRY项。
第三个数组项包含所有3个空闲页面的MMFREE_POOL_ENTRY项。
第四个数组项包含所有大于等于 4个空闲页面的MMFREE_POOL_ENTRY项,在初始情况下,只有一个MMFREE_POOL_ENTRY项加入到第四个数组项链表中。

然后,MiInitializeNonPagedPool函数确定非换页内存池的起始和结束物理页面帧MiStartOfInitialPoolFrame和 MiEndOfInitialPoolFrame,最后,为非换页内存池扩展区建立起系统PTE。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    //
    // Initialize the first nonpaged pool PFN.
    //
 
    if (MI_IS_PHYSICAL_ADDRESS(MmNonPagedPoolStart)) {
        PageFrameIndex = MI_CONVERT_PHYSICAL_TO_PFN (MmNonPagedPoolStart);
    }
    else {
        PointerPte = MiGetPteAddress(MmNonPagedPoolStart);
        ASSERT (PointerPte->u.Hard.Valid == 1);
        PageFrameIndex = MI_GET_PAGE_FRAME_FROM_PTE (PointerPte);
    }
    MiStartOfInitialPoolFrame = PageFrameIndex;        // 起始物理页面帧
 
    //
    // Set the last nonpaged pool PFN so coalescing on free doesn't go
    // past the end of the initial pool.
    //
 
    MmNonPagedPoolEnd0 = (PVOID)((ULONG_PTR)MmNonPagedPoolStart + MmSizeOfNonPagedPoolInBytes);
    EndOfInitialPool = (PVOID)((ULONG_PTR)MmNonPagedPoolStart + MmSizeOfNonPagedPoolInBytes - 1);
 
    if (MI_IS_PHYSICAL_ADDRESS(EndOfInitialPool)) {
        PageFrameIndex = MI_CONVERT_PHYSICAL_TO_PFN (EndOfInitialPool);
    }
    else {
        PointerPte = MiGetPteAddress(EndOfInitialPool);
        ASSERT (PointerPte->u.Hard.Valid == 1);
        PageFrameIndex = MI_GET_PAGE_FRAME_FROM_PTE (PointerPte);
    }
    MiEndOfInitialPoolFrame = PageFrameIndex;// 结束物理页面帧
    ....
    MiInitializeSystemPtes (PointerPte, Size, NonPagedPoolExpansion);// 系统PTE

一旦非换页内存池的结构已建立,接下来系统代码可以通过 MiAllocatePoolPages 和MiFreePoolPages函数来申请和归还页面。

非换页内存池有两部分:地址范围 MmNonPagedPoolStart 与 MmNonPagedPoolEnd0之间的部分是基本内存池,其中所有的页面都已经分配了物理页面;地址范围

MmNonPagedPoolExpansionStart与MmNonPagedPoolEnd之间的部分是扩展区,只有当基本区无法满足内存申请需求时才会分配真正的物理页面。由于非换页内存池的空闲页面已经被映射到物理页面,所以,Windows充分利用这些页面自身的内存来构建起一组空闲页面链表,换句话说,每个页面都是一个MMFREE_POOL_ENTRY结构,如图所示。MiInitializeNonPagedPool函数已经把数组MmNonPagedPoolFreeListHead初始化成只包含一个完整的空闲内存块,该内存块包括所有的非换页页面。

1.png

如前所述,在非换页内存池的结构中,每个空闲链表中的每个节点包含 1、2、3、4 或4个以上的页面,在同一个节点上的页面其虚拟地址空间是连续的。

第一个页面的List域构成了链表结构,Size域指明了这个节点所包含的页面数量,Owner域指向自己,后续页面的List和Size域没有使用,但Owner域很重要,它指向第一个面。 

  

1.1.MiAllocatePoolPages分配内存

当MiAllocatePoolPages函数从非换页内存池中分配页面时,它根据指定的大小值,换算成对应的页面数,即局部变量SizeInPages

 #define BYTES_TO_PAGES(Size)  (((Size) >> PAGE_SHIFT) + (((Size) & (PAGE_SIZE - 1)) != 0))
 SizeInPages = BYTES_TO_PAGES (SizeInBytes);

然后从MmNonPagedPoolFreeListHead数组中找到适当的空闲链表开始搜索:

        Index = SizeInPages - 1; 
        if (Index >= MI_MAX_FREE_LIST_HEADS) {// 大于等于4,那就从MmNonPagedPoolFreeListHead[3]开始搜索
            Index = MI_MAX_FREE_LIST_HEADS - 1;
        }

直至找到一个节点拥有这么多的页面,将该节点从链表中移除出来。如果该节点除了满足客户所要求的页面数SizeInPages以外,还有剩余的页面,那么,该节点后端部分的 SizeInPages个页面将作为结果返回给客户,前端部分剩余的那些页面被当做一个新的空闲链表节点加入到适当的空闲链表中。这些页面的首页面中的Size域需要调整,后续的页面皆指向首页面,无须任何改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
ListHead = &MmNonPagedPoolFreeListHead[Index];
LastListHead = &MmNonPagedPoolFreeListHead[MI_MAX_FREE_LIST_HEADS];
OldIrql = KeAcquireQueuedSpinLock (LockQueueMmNonPagedPoolLock);
  do {
            Entry = ListHead->Flink;
            while (Entry != ListHead) 
          {
             // 解保护 
             if (MmProtectFreedNonPagedPool == TRUE) 
                {
                    MiUnProtectFreeNonPagedPool ((PVOID)Entry, 0);
                }
             // 切换到MMFREE_POOL_ENTRY头
             FreePageInfo = CONTAINING_RECORD(Entry, MMFREE_POOL_ENTRY,List);
             ASSERT (FreePageInfo->Signature == MM_FREE_POOL_SIGNATURE);
            if (FreePageInfo->Size >= SizeInPages) 
            { // 可分配页面大于需求的页面
                FreePageInfo->Size -= SizeInPages;   // 移除需求的页面
                BaseVa = (PVOID)((PCHAR)FreePageInfo + (FreePageInfo->Size << PAGE_SHIFT));//余下页面的基地址
                if (MmProtectFreedNonPagedPool == FALSE) 
                {
                     RemoveEntryList (&FreePageInfo->List);//将该节点从链表中移除出来
                }
               else 
               {
                    MiProtectedPoolRemoveEntryList (&FreePageInfo->List);
               }
               if (FreePageInfo->Size != 0)// 还有多余的页面
               {
                    // 判断应该加入哪个链表中
                    Index = (ULONG)(FreePageInfo->Size - 1);
                    if (Index >= MI_MAX_FREE_LIST_HEADS) 
                    {
                        Index = MI_MAX_FREE_LIST_HEADS - 1;
                    }
                    // 加入新链表中
                   if (MmProtectFreedNonPagedPool == FALSE)
                    {
                        InsertTailList (&MmNonPagedPoolFreeListHead[Index], &FreePageInfo->List);
                    }
                    else
                     {
                       MiProtectedPoolInsertList (&MmNonPagedPoolFreeListHead[Index], &FreePageInfo->List, FALSE);
                       MiProtectFreeNonPagedPool ((PVOID)FreePageInfo,(ULONG)FreePageInfo->Size);
                     }
               }
 
               // 调整余下页的数目
               MmNumberOfFreeNonPagedPool -= SizeInPages;
               ASSERT ((LONG)MmNumberOfFreeNonPagedPool >= 0);

对于已经确定的SizeInPages个页面,MiAllocatePoolPages函数分别找到其起始页面和结束页面在PFN数据库中的记录,并设置它们的StartOfAllocation和 EndOfAllocation位,因此,一次有效的页面分配也会在PFN数据库中留下痕迹。如果在空闲链表数组中搜索不到满足条件的空闲节点,则 MiAllocatePoolPages函数试图扩展非换页内存池,并满足所要求的页面数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
        //
        // No more entries on the list, expand nonpaged pool if
        // possible to satisfy this request.
        //
        // If pool is starting to run low then free some page cache up now.
        // While this can never guarantee pool allocations will succeed,
        // it does give allocators a better chance.
        //
 
        FreePoolInPages = MmMaximumNonPagedPoolInPages - MmAllocatedNonPagedPool;
        if (FreePoolInPages < (3 * 1024 * 1024) / PAGE_SIZE) {
            MmPreemptiveTrims[MmPreemptForNonPaged] += 1;
            MiTrimSegmentCache ();
        }

非换页内存池中的页面回收是通过MiFreePoolPages函数来完成的,对于一个给定的起始地址StartingAddress,找到它的PTE,并提取出页帧编号,从而定位到PFN数据库中起始页面的PFN项。凡是通过MiAllocatePoolPages函数分配得到的连续页面,其首页面的PFN项的StartOfAllocation位必定是1,沿着此PFN项进行搜索,可以找到结束页面,其PFN项的EndOfAllocation位为1。

  

2.换页内存池管理算法

非换页内存池的空闲页面链表的做法不适合于换页内存池,因为换页内存池中的空闲页面并不保证有对应的物理页面,而且,仅仅出于管理的原因而为换页内存池中的空闲页面分配物理页面,并不符合换页内存池的设计意图。换页内存池有两个,一个是系统全局范围的,另一个是会话空间中的。它们在系统地址空间中的起始地址分别对应于全局变量MmPagedPoolStart和MiSessionPoolStart.换页内存池有一个数据结构来描述其页面分配状态,定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//
// Pool bit maps and other related structures.
//
 
typedef struct _MM_PAGED_POOL_INFO {
 
    PRTL_BITMAP PagedPoolAllocationMap;
    PRTL_BITMAP 
    ;
    PMMPTE FirstPteForPagedPool;
    PMMPTE LastPteForPagedPool;
    PMMPTE NextPdeForPagedPoolExpansion;
    ULONG PagedPoolHint;
    SIZE_T PagedPoolCommit;
    SIZE_T AllocatedPagedPool;
 
} MM_PAGED_POOL_INFO, *PMM_PAGED_POOL_INF

其中,系统全局换页内存池由全局变量MmPagedPoolInfo来定义;会话换页内存池则通过会话空间中的成员变量来定义,即全局变量MmSessionSpace中的 PagedPoolInfo成员。

其中,系统全局换页内存池由全局变量 MmPagedPoolInfo 来定义;会话换页内存池则通过会话空间中的成员变量来定义,即全局变量 MmSessionSpace 中的 PagedPoolInfo成员。

换页内存池中的页面是通过位图来管理的,一个页面的分配与否,是由该页面所对应的位来表达的。

1.PagedPoolAllocationMap域是基本的位图,用于指明每一个页面的分配状态;

2.EndOfPagedPoolBitmap域也是一个位图,标明了每个页面是否为一次内存申请的最后一个页面。

3.FirstPteForPagedPool和LastPteForPagedPool域规定了内存池的地址范围.

4.NextPdeForPagedPoolExpansion域定义了换页内存池的下次扩展位置.

5.PagedPoolCommit域记录了换页内存池中有多少个页面已经分到了内存(已提交,未必对应有物理页面)而AllocatedPagedPool域记录了换页内存池已分配了多少页面.

6.PagedPoolHint域指示了在分配页面时的起始搜索位置.

全局变量MmSizeOfPagedPoolInBytes和MmSizeOfPagedPoolInPages记录了系统换页内存池的大小,最大不超过系统地址空间中划给换页内存池的范围,即MmNonPagedSystemStart-MmPagedPoolStart,MmPagedPoolStart和MmPagedPoolEnd分别记录了换页池的起始地址和结束地址。

因此,MmPagedPoolInfo结构中的FirstPteForPagedPool和LastPteForPagedPool域可根据 MmPagedPoolStart和MmPagedPoolEnd的值直接导出,

 PointerPte = MiGetPteAddress (MmPagedPoolStart);
 MmPagedPoolInfo.FirstPteForPagedPool = PointerPte;
 MmPagedPoolInfo.LastPteForPagedPool = MiGetPteAddress(MmPagedPoolEnd);

MiBuildPagedPool函数分配好换页内存池地址范围的第一个页表,即起始地址的页目录项(PDE)所指的页表,MmPagedPoolInfo的NextPdeForPagedPoolExpansion域值为接下来的页表地址,即换页内存池地址范围的第二个页表的虚拟地址。然后调用MiCreateBitMap函数创建一个位图,位图的大小等于页面的数量,位图本身的内存是从非换页内存池中分配的。

由于第一个页表中的PTE是有效的,所以位图中最前面的1024 位(一个页表所能容纳PTE的数量)清零,其余的位被置位,这表明前1024个页面是空闲的。这样,MmPagedPoolInfo的PagedPoolAllocationMap域已经初始化;结束页面位图,即EndOfPagedPoolBitmap成员,也依次创建,所有的位全清零,因为尚未任何有效的页面分配。

同样,换页的页面分配也是由MiAllocatePoolPages来执行的:

1.判断是系统换页内存池还是会话空间的换页内存池.

 if ((PoolType & SESSION_POOL_MASK) == 0) {

2.调用RtlFindClearBitsAndSet在PagedPoolInfo->PagedPoolAllocationMap 位图中搜索指定数量的连续零位,即换页内存池中对应的连续空闲页面.

    StartPosition = RtlFindClearBitsAndSet (
                               PagedPoolInfo->PagedPoolAllocationMap,//位图
                               (ULONG)SizeInPages,//连续大小
                               PagedPoolInfo->PagedPoolHint);//起始搜索们

3.如果未能找到这么多连续零位,则设法扩展换页内存池,使内存池的NextPdeForPagedPoolExpansion成员往后移,当然不能越过换页内存池结束地址的PDE.

换页内存池经过扩展以后,再调用RtlFindClearBitsAndSet函数搜索满足要求的连续零位。

非换页内存池的页面分配,其起始和结束页面直接被标记在PFN数据库的对应PFN项中,对于换页内存池,这种做法行不通,因为换页内存池中的页面可能会被换出到外存中,所以根本就不存在对应的PFN项。因此,为了记录一次页面分配的起始和结束位置,MM_PAGED_POOL_INFO包含一个并行的位图,专门记录每次页面分配的结束页面。结合这样两个位图,当回收页面时,只需给出起始地址,就可以验证该地址的正确性,如果此地址前面的那个页面尚未被分配,则此地址可以认为是一次页面分配的起始处;如果前面的那个页面已被分配,而且结束页面位图并未表明它是一次页面分配的结束页面,则参数StartingAddress中给出的起始地址是错误的,碰到这种情况,系统会崩溃.

   EndPosition = StartPosition + (ULONG)SizeInPages - 1;
   RtlSetBit (PagedPoolInfo->EndOfPagedPoolBitmap, EndPosition);

4.对于PagedPoolAllocationMap中的位,置位表明所对应的页面是不可用的,零位表明是可用的。系统换页内存池初始时,第一个PDE所指的页表已分配,所以该页表中的PTE所对应的页面(1024 个)已经可以使用了。因而,在位图中,前 1 024 位为零位,其余皆为置位状态。随着换页内存池被扩展,即NextPdeForPagedPoolExpansion不断后移,零位出现的位置也开始后移。但是,NextPdeForPagedPoolExpansion 后面对应的位一定是置位的。因

此,对于PagedPoolAllocationMap中的位,零位表示空闲页面,处于待分配状态;置位表示可能已被分配,或者尚未扩展到该页面,而MiFreePoolPages 函数

做的事情是把连续的置位变成零位。EndOfPagedPoolBitmap 位图初始时,所有的位皆为零位。每次分配页面时,最后一个分配的页面所对应的位被置位;MiFreePoolPages 函数依据此位图来判断传进来的起始地址的合法性,并且把从该地址开始的已分配连续页面中的最后一个页面所对应的位清零。

   while (!MI_CHECK_BIT (BitMap, i)) {
        i += 1;
    }

   

3.执行体内存池的管理算法

换页内存池和非换页内存池是 Windows 操作系统提供的基本动态内存管理手段,它以页面为基本粒度来管理系统中划定的地址范围。显然,页面粒度对于一般的代码逻辑而言太大了.所以上层采用执行体内存池管理算法.

执行体内存池对象是由数据结构POOL_DESCRIPTOR来描述的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//
// Define pool descriptor structure.
//
 
typedef struct _POOL_DESCRIPTOR {
    POOL_TYPE PoolType;
    ULONG PoolIndex;
    ULONG RunningAllocs;
    ULONG RunningDeAllocs;
    ULONG TotalPages;
    ULONG TotalBigPages;
    ULONG Threshold;
    PVOID LockAddress;
    PVOID PendingFrees;
    LONG PendingFreeDepth;
    SIZE_T TotalBytes;
    SIZE_T Spare0;
    LIST_ENTRY ListHeads[POOL_LIST_HEADS];
} POOL_DESCRIPTOR, *PPOOL_DESCRIPTOR;

WRK用一组称为快查表(lookaside list)的空闲内存块链表分别记录了各种大小的待分配内存。当一个内存池需要更多内存时,它可以向对应的系统内存池申请更多的页面。而当内存释放时,则让待释放的内存与相邻的内存块尽可能地合并,以形成更大的空闲内存块,如果构成一个完整的页面,则将页面交还给系统内存池。对于需要一个页面或以上的内存申请,执行体内存池直接向系统内存池申请足够的页面并交给客户;对于小于一个页面大小的内存申请,执行体内存池使用快查表来管理小粒度的内存块。

ExAllocatePoolWithTag函数检查内存池内部的快查表,以期找到合适大小的空闲内存块,若未能找到满足条件的内存块,则向系统内存池申请一个新的页面,把页面的一部分返回给客户,剩下的加入适当大小的快查表中。

最小的内存块是8个字节,POOL_HEADER的大小也是8个字节,所以,POOL_BUDDY_MAX 的值是4096-16=4080,而 POOL_LIST_HEADS的值是512,POOL_DESCRIPTOR 中的快查表包含 512 项(实际使用 510 项),分别对应于 8、16、24……4 072和4 080大小的空闲内存块。若客户申请大于4 080而小于4 096的内存块,则直接使用整个页面,因为剩下的空间不足以容纳最小内存块(8字节)加上管理开销(8字节)。下图显示了执行体内存池的管理结构。

1456736086376140.png

ExFreePoolWithTag函数对于小内存块的释放,每个处理器有两个缓存链表,位于KPRCB结构的PPPagedLookasideList 和PPNPagedLookasideList 成员中,分别对应于换页内存池和非换页内存池的缓存链表。阈值 POOL_SMALL_LISTS 指明了只有小于等于32×8 大小的内存块才使用缓存链表。因此,在 ExAllocatePoolWithTag 函数中,当申请一个小内存块时,如果在当前处理器的缓存链表中能找到对应大小的内存块,则直接从缓存链表中摘除一个内存块,快速地返回给客户。对应地,在ExFreePoolWithTag函数中,如果当前处理器的缓存链表尚未达到预定的深度,则将待释放的内存块插入到相应的缓存链表。接下来,将当前内存块与后面的空闲内存块或者前面的空闲内存块合并在一起,构成更大的空闲内存块,从而减少内存池中的小碎片。

合并的前提条件是,当前待释放的内存块前面或后面的内存块恰好也是空闲的,这可以依据内存块的POOL_HEADER中的 PoolType 的值是否为0来确定。如果合并以后的内存块是一个完整的页面,则将空闲页面归还给系统内存池,这也是通过调用 MiFreePoolPages 函数来完成的。否则,将新的内存块(可能已经合并了其相邻的内存块)插入到适当的快查表中。

 

文章作者:hgy413
本文地址:http://hgy413.com/2979.html
版权所有 © 转载时必须以链接形式注明作者和原始出处!

本文目前尚无任何评论.

发表评论