mm学习笔记_04：VAD树算法与地址空间分配

基于 ReactOS ARM3 MM 源码（ntoskrnl/mm/ARM3/vadnode.c）

1. vadnode.c 概述

文件位置：d:\reactos\ntoskrnl\mm\ARM3\vadnode.c

职责：实现 VAD（Virtual Address Descriptor，虚拟地址描述符）的 AVL 树算法，包括：

• VAD 节点的查找、插入、删除
• 空闲地址范围的搜索（Bottom-Up 和 Top-Down）
• 基于地址的 Section 管理

核心数据结构——MM_AVL_TABLE：

typedefstruct_MM_AVL_TABLE{MMADDRESS_NODE BalancedRoot;// AVL 树根节点（内含右孩子为真正的根）ULONG_PTR NumberGenericTableElements;// 树中节点数PVOID NodeHint;// 节点查找优化提示（最近访问的 VAD）ULONG DepthOfTree;// 树深度UCHAR Unused;// 用于区分用户VAD树和内核内存区域}MM_AVL_TABLE;

重要：每个进程的EPROCESS中包含一个VadRoot（类型为MM_AVL_TABLE），即该进程所有 VAD 的 AVL 树。

2. 三种 VAD 结构

2.1 MMVAD_SHORT（32 字节）

typedefstruct_MMVAD_SHORT{MMADDRESS_NODE VadNode;// AVL 树节点（含 StartingVpn, EndingVpn, 左右子指针, 父指针, 平衡因子）ULONG_PTR NumberGenericTableElements;// 已映射的页数MMVAD_FLAGS VadFlags;// 16 位标志（PrivateMemory, MemCommit, Protection, VadType 等）MMVAD_FLAGS2 VadFlags2;// 更多标志（LongVad, OneSecured 等）PMMADDRESS_NODE*NextVad;// 未使用}MMVAD_SHORT;

2.2 MMVAD（36 字节）

在MMVAD_SHORT基础上增加：

typedefstruct_MMVAD{MMVAD_SHORT Core;union{PVOID Pointer;PVOID ControlArea;// 控制区指针（Section 映射时使用）}u2;PMMPTE FirstPrototypePte;// 第一个原型 PTEPMMPTE LastContiguousPte;// 最后一个连续 PTEPVOID DeleteStack;// 调试用}MMVAD;

2.3 MMVAD_LONG（44+ 字节）

在MMVAD基础上增加：

typedefstruct_MMVAD_LONG{MMVAD Core;union{struct{ULONG_PTR StartVpn;// 安全区域的起始 VPNULONG_PTR EndVpn;// 安全区域的结束 VPN}Secured;ULONG_PTR LongFlags;}u3;}MMVAD_LONG;

三者关系：

MMVAD_SHORT（32B）：基础 VAD，用于普通私有内存 │ ▼ MMVAD（36B）：增加 ControlArea 和 FirstPrototypePte，用于 Section 映射 │ ▼ MMVAD_LONG（44B+）：增加 Secured 区域，用于 TEB/PEB 等安全 VAD

判断宏：

// 是否为长 VADVad->u2.VadFlags2.LongVad

3. MiLocateVad——查找算法（hint 优化）

文件：vadnode.c:114

功能：在 VAD AVL 树中查找包含指定虚拟地址的 VAD 节点。

查找流程：

1. Hint 优化：先从Table->NodeHint检查，如果目标地址落在 hint VAD 范围内直接返回（O(1) 最速路径）
2. AVL 树搜索：调用RtlpFindAvlTableNodeOrParent在 AVL 树中查找
3. 更新 Hint：找到后将结果设为新的 hint，加速后续查找

PMMVAD NTAPIMiLocateVad(IN PMM_AVL_TABLE Table,IN PVOID VirtualAddress){// Step 1: 尝试 hintFoundVad=(PMMVAD)Table->NodeHint;if(FoundVad){Vpn=(ULONG_PTR)VirtualAddress>>PAGE_SHIFT;if((Vpn>=FoundVad->StartingVpn)&&(Vpn<=FoundVad->EndingVpn))returnFoundVad;// Hint 命中！}// Step 2: AVL 树搜索SearchResult=RtlpFindAvlTableNodeOrParent(Table,(PVOID)Vpn,&FoundVad);if(SearchResult!=TableFoundNode)returnNULL;// Step 3: 更新 hint（无锁更新，hint 只读不保证一致性）Table->NodeHint=FoundVad;returnFoundVad;}

配套函数：

// 直接在当前进程中查找PMMVAD NTAPIMiLocateAddress(IN PVOID VirtualAddress){returnMiLocateVad(&PsGetCurrentProcess()->VadRoot,VirtualAddress);}

MiCheckForConflictingNode（vadnode.c:155）：

• 遍历 AVL 树检查指定区间[StartVpn, EndVpn]是否与现有 VAD 冲突
• 返回TableFoundNode（冲突）/TableInsertAsLeft（插入左侧）/TableInsertAsRight（插入右侧）

4. MiInsertVad / MiRemoveNode——插入与删除

4.1 MiInsertVad

文件：vadnode.c:222

VOID NTAPIMiInsertVad(IN PMMVAD Vad,IN PMM_AVL_TABLE VadRoot){// 1. 设为新的 hintVadRoot->NodeHint=Vad;// 2. 查找插入位置（确保不冲突）Result=RtlpFindAvlTableNodeOrParent(VadRoot,(PVOID)Vad->StartingVpn,&Parent);ASSERT(Result!=TableFoundNode);// 不应冲突// 3. AVL 树插入MiInsertNode(VadRoot,(PVOID)Vad,Parent,Result);}

4.2 MiInsertVadEx——增强版插入

文件：vadnode.c:245

这是NtAllocateVirtualMemory调用的主要插入函数，支持地址自动选择：

流程：

1. 如果*BaseAddress == 0（未指定基址）：
   • 根据MEM_TOP_DOWN或VmTopDown决定搜索方向
   • MiFindEmptyAddressRangeInTree（Bottom-Up）或MiFindEmptyAddressRangeDownTree（Top-Down）
2. 如果指定了基址：
   • 用MiCheckForConflictingNode验证地址是否可用
3. 设置 VAD 的StartingVpn和EndingVpn
4. 如果PrivateMemory && MemCommit或!PrivateMemory && PAGE_WRITECOPY，设置CommitCharge
5. 锁定工作集 → 插入 AVL 树 → 解锁
6. 更新进程的VirtualSize和PeakVirtualSize

NTSTATUS NTAPIMiInsertVadEx(IN OUT PMMVAD Vad,IN ULONG_PTR*BaseAddress,...){ViewSize=ALIGN_UP_BY(ViewSize,PAGE_SIZE);KeAcquireGuardedMutex(&CurrentProcess->AddressCreationLock);if(CurrentProcess->VmDeleted)returnSTATUS_PROCESS_IS_TERMINATING;if(*BaseAddress==0){// 选择搜索方向if((AllocationType&MEM_TOP_DOWN)||CurrentProcess->VmTopDown)Result=MiFindEmptyAddressRangeDownTree(...);elseResult=MiFindEmptyAddressRangeInTree(...);// 检查结果if(Result==TableFoundNode||EndingAddress>HighestAddress)returnSTATUS_NO_MEMORY;}else{// 验证给定地址Result=MiCheckForConflictingNode(...);if(Result==TableFoundNode)returnSTATUS_CONFLICTING_ADDRESSES;}Vad->StartingVpn=StartingAddress>>PAGE_SHIFT;Vad->EndingVpn=EndingAddress>>PAGE_SHIFT;// 插入 AVL 树MiLockProcessWorkingSetUnsafe(CurrentProcess,CurrentThread);MiInsertNode(&CurrentProcess->VadRoot,(PVOID)Vad,Parent,Result);MiUnlockProcessWorkingSetUnsafe(CurrentProcess,CurrentThread);CurrentProcess->VirtualSize+=ViewSize;KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);returnSTATUS_SUCCESS;}

4.3 MiRemoveNode

文件：vadnode.c:403

VOID NTAPIMiRemoveNode(IN PMMADDRESS_NODE Node,IN PMM_AVL_TABLE Table){// 调用 RTL AVL 树删除RtlpDeleteAvlTreeNode(Table,Node);Table->NumberGenericTableElements--;// 如果被删除的节点是 hint，更新 hintif(Table->NodeHint==Node){if(!Table->NumberGenericTableElements)Table->NodeHint=NULL;elseTable->NodeHint=Table->BalancedRoot.RightChild;}}

5. MiFindEmptyAddressRangeInTree——Bottom-Up 搜索

文件：vadnode.c:494

功能：从低地址向高地址搜索，找到第一个足够大的空闲地址范围。用于MEM_BOTTOM_UP分配（默认）。

搜索算法：

1. 计算起始 VPN (LowVpn)，从 MM_LOWEST_USER_ADDRESS 开始 2. 如果 AVL 树为空，直接返回低位地址 3. 取最左节点（最小地址的 VAD） 4. 遍历所有 VAD 节点（从小到大）： a. 检查当前节点起始地址与 LowVpn 之间是否有足够间隙 b. 如果有间隙且足够大 → 返回该地址 c. 否则将 LowVpn 移到当前节点结束地址 + 1 d. 继续下一个节点 5. 如果遍历完所有 VAD 还没有，检查最高地址之前是否有足够空间

地址空间（低位 → 高位）： ┌──────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │ VAD1 │ │ VAD2 │ │ VAD3 │ │ VAD4 │ └──────┘ └──────────┘ └──────────┘ └──────────┘ ↑ ↑ │ └─ 找到空闲区域！ └─ LowVpn 起始搜索位置

TABLE_SEARCH_RESULT NTAPIMiFindEmptyAddressRangeInTree(SIZE_T Length,ULONG_PTR Alignment,PMM_AVL_TABLE Table,OUT PMMADDRESS_NODE*PreviousVad,OUT PULONG_PTR Base){PageCount=BYTES_TO_PAGES(Length);AlignmentVpn=Alignment>>PAGE_SHIFT;LowVpn=ALIGN_UP_BY(MM_LOWEST_USER_ADDRESS>>PAGE_SHIFT,AlignmentVpn);if(Table->NumberGenericTableElements==0){*Base=LowVpn<<PAGE_SHIFT;returnTableEmptyTree;}// 取最左节点Node=RtlRightChildAvl(&Table->BalancedRoot);while(RtlLeftChildAvl(Node))Node=RtlLeftChildAvl(Node);PreviousNode=NULL;while(Node){if(Node->StartingVpn>=LowVpn+PageCount){*Base=LowVpn<<PAGE_SHIFT;// 确定父节点方向return(RtlLeftChildAvl(Node)==NULL)?TableInsertAsLeft:TableInsertAsRight;}if(Node->EndingVpn>=LowVpn)LowVpn=ALIGN_UP_BY(Node->EndingVpn+1,AlignmentVpn);PreviousNode=Node;Node=MiGetNextNode(Node);}// 检查最高地址之上是否有空间HighestVpn=(MM_HIGHEST_VAD_ADDRESS+1)/PAGE_SIZE;if(HighestVpn>=LowVpn+PageCount){*Base=LowVpn<<PAGE_SHIFT;returnTableInsertAsRight;}returnTableFoundNode;// 无足够空间}

6. MiFindEmptyAddressRangeDownTree——Top-Down 搜索

文件：vadnode.c:591

功能：从指定边界地址向低地址搜索，找到第一个足够大的空闲地址范围。用于MEM_TOP_DOWN分配。

搜索算法：

1. 计算最高边界 HighVpn = (BoundaryAddress + 1) >> PAGE_SHIFT 2. 如果 AVL 树为空，直接返回 BoundaryAddress - Length 对齐后地址 3. 从根节点开始，沿右孩子找到结束地址 >= HighVpn 的节点 4. 从该节点开始，逐个向前遍历（MiGetPreviousNode）： a. 计算当前节点结束地址之上的空间大小 b. 如果空间足够 → 从高地址向下分配 c. 否则更新 HighVpn 为当前节点起始地址 d. 继续前一个节点 5. 如果遍历完还没有，检查最低 VAD 之下的空间

地址空间（低位 → 高位）： ┌──────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │ VAD1 │ │ VAD2 │ │ VAD3 │ │ VAD4 │ └──────┘ └──────────┘ └──────────┘ └──────────┘ ↑ ↑ │ └─ BoundaryAddress └─ 找到空闲区域（从高地址向下取）

TABLE_SEARCH_RESULT NTAPIMiFindEmptyAddressRangeDownTree(SIZE_T Length,ULONG_PTR BoundaryAddress,ULONG_PTR Alignment,PMM_AVL_TABLE Table,OUT PULONG_PTR Base,OUT PMMADDRESS_NODE*Parent){HighVpn=(BoundaryAddress+1)>>PAGE_SHIFT;// 从根开始，找到结束地址 >= HighVpn 的最右节点Node=RtlRightChildAvl(&Table->BalancedRoot);while((Node->EndingVpn<HighVpn)&&((Child=RtlRightChildAvl(Node))))Node=Child;// 反向遍历while(Node){LowVpn=ALIGN_UP_BY(Node->EndingVpn+1,AlignmentVpn);if((HighVpn>LowVpn)&&((HighVpn-LowVpn)>=PageCount)){LowVpn=ALIGN_DOWN_BY(HighVpn-PageCount,AlignmentVpn);*Base=LowVpn<<PAGE_SHIFT;return...;}if(Node->StartingVpn<HighVpn)HighVpn=Node->StartingVpn;OldNode=Node;Node=MiGetPreviousNode(Node);}// 检查最低 VAD 之下LowVpn=ALIGN_UP_BY(MI_LOWEST_VAD_ADDRESS,Alignment)/PAGE_SIZE;if((HighVpn>LowVpn)&&((HighVpn-LowVpn)>=PageCount)){...}returnTableFoundNode;}

7. MiInsertBasedSection——基于地址的 Section 管理

文件：vadnode.c:386

用途：管理全局的MmSectionBasedRootAVL 树，记录已映射 Section 在地址空间中的位置。

特点：

• 使用全局表MmSectionBasedRoot（非进程私有）
• 插入时以Section->Address为节点，以StartingVpn为键
• 通过MmSectionBasedMutex保护并发访问

// MmSectionBasedRoot 是全局变量，不是每个进程一个externMM_AVL_TABLE MmSectionBasedRoot;VOID NTAPIMiInsertBasedSection(IN PSECTION Section){ASSERT_LOCKED_FOR_WRITE(&MmSectionBasedRoot);Result=RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot,(PVOID)Section->Address.StartingVpn,&Parent);MiInsertNode(&MmSectionBasedRoot,&Section->Address,Parent,Result);}

配套函数MiFindEmptyAddressRangeDownBasedTree（vadnode.c:711）：

• 在MmSectionBasedRoot中从高地址向低地址搜索空闲范围
• 模拟 Windows 2003 的 bug（当NTDDI_VERSION < NTDDI_VISTA时可能浪费最多 Alignment 字节）

附录：AVL 树辅助函数