mm学习笔记_04VAD树算法与地址空间分配基于 ReactOS ARM3 MM 源码ntoskrnl/mm/ARM3/vadnode.c1. vadnode.c 概述文件位置d:\reactos\ntoskrnl\mm\ARM3\vadnode.c职责实现 VADVirtual Address Descriptor虚拟地址描述符的 AVL 树算法包括VAD 节点的查找、插入、删除空闲地址范围的搜索Bottom-Up 和 Top-Down基于地址的 Section 管理核心数据结构——MM_AVL_TABLEtypedefstruct_MM_AVL_TABLE{MMADDRESS_NODE BalancedRoot;// AVL 树根节点内含右孩子为真正的根ULONG_PTR NumberGenericTableElements;// 树中节点数PVOID NodeHint;// 节点查找优化提示最近访问的 VADULONG DepthOfTree;// 树深度UCHAR Unused;// 用于区分用户VAD树和内核内存区域}MM_AVL_TABLE;重要每个进程的EPROCESS中包含一个VadRoot类型为MM_AVL_TABLE即该进程所有 VAD 的 AVL 树。2. 三种 VAD 结构2.1 MMVAD_SHORT32 字节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 MMVAD36 字节在MMVAD_SHORT基础上增加typedefstruct_MMVAD{MMVAD_SHORT Core;union{PVOID Pointer;PVOID ControlArea;// 控制区指针Section 映射时使用}u2;PMMPTE FirstPrototypePte;// 第一个原型 PTEPMMPTE LastContiguousPte;// 最后一个连续 PTEPVOID DeleteStack;// 调试用}MMVAD;2.3 MMVAD_LONG44 字节在MMVAD基础上增加typedefstruct_MMVAD_LONG{MMVAD Core;union{struct{ULONG_PTR StartVpn;// 安全区域的起始 VPNULONG_PTR EndVpn;// 安全区域的结束 VPN}Secured;ULONG_PTR LongFlags;}u3;}MMVAD_LONG;三者关系MMVAD_SHORT32B基础 VAD用于普通私有内存 │ ▼ MMVAD36B增加 ControlArea 和 FirstPrototypePte用于 Section 映射 │ ▼ MMVAD_LONG44B增加 Secured 区域用于 TEB/PEB 等安全 VAD判断宏// 是否为长 VADVad-u2.VadFlags2.LongVad3. MiLocateVad——查找算法hint 优化文件vadnode.c:114功能在 VAD AVL 树中查找包含指定虚拟地址的 VAD 节点。查找流程Hint 优化先从Table-NodeHint检查如果目标地址落在 hint VAD 范围内直接返回O(1) 最速路径AVL 树搜索调用RtlpFindAvlTableNodeOrParent在 AVL 树中查找更新 Hint找到后将结果设为新的 hint加速后续查找PMMVAD NTAPIMiLocateVad(IN PMM_AVL_TABLE Table,IN PVOID VirtualAddress){// Step 1: 尝试 hintFoundVad(PMMVAD)Table-NodeHint;if(FoundVad){Vpn(ULONG_PTR)VirtualAddressPAGE_SHIFT;if((VpnFoundVad-StartingVpn)(VpnFoundVad-EndingVpn))returnFoundVad;// Hint 命中}// Step 2: AVL 树搜索SearchResultRtlpFindAvlTableNodeOrParent(Table,(PVOID)Vpn,FoundVad);if(SearchResult!TableFoundNode)returnNULL;// Step 3: 更新 hint无锁更新hint 只读不保证一致性Table-NodeHintFoundVad;returnFoundVad;}配套函数// 直接在当前进程中查找PMMVAD NTAPIMiLocateAddress(IN PVOID VirtualAddress){returnMiLocateVad(PsGetCurrentProcess()-VadRoot,VirtualAddress);}MiCheckForConflictingNodevadnode.c:155遍历 AVL 树检查指定区间[StartVpn, EndVpn]是否与现有 VAD 冲突返回TableFoundNode冲突/TableInsertAsLeft插入左侧/TableInsertAsRight插入右侧4. MiInsertVad / MiRemoveNode——插入与删除4.1 MiInsertVad文件vadnode.c:222VOID NTAPIMiInsertVad(IN PMMVAD Vad,IN PMM_AVL_TABLE VadRoot){// 1. 设为新的 hintVadRoot-NodeHintVad;// 2. 查找插入位置确保不冲突ResultRtlpFindAvlTableNodeOrParent(VadRoot,(PVOID)Vad-StartingVpn,Parent);ASSERT(Result!TableFoundNode);// 不应冲突// 3. AVL 树插入MiInsertNode(VadRoot,(PVOID)Vad,Parent,Result);}4.2 MiInsertVadEx——增强版插入文件vadnode.c:245这是NtAllocateVirtualMemory调用的主要插入函数支持地址自动选择流程如果*BaseAddress 0未指定基址根据MEM_TOP_DOWN或VmTopDown决定搜索方向MiFindEmptyAddressRangeInTreeBottom-Up或MiFindEmptyAddressRangeDownTreeTop-Down如果指定了基址用MiCheckForConflictingNode验证地址是否可用设置 VAD 的StartingVpn和EndingVpn如果PrivateMemory MemCommit或!PrivateMemory PAGE_WRITECOPY设置CommitCharge锁定工作集 → 插入 AVL 树 → 解锁更新进程的VirtualSize和PeakVirtualSizeNTSTATUS NTAPIMiInsertVadEx(IN OUT PMMVAD Vad,IN ULONG_PTR*BaseAddress,...){ViewSizeALIGN_UP_BY(ViewSize,PAGE_SIZE);KeAcquireGuardedMutex(CurrentProcess-AddressCreationLock);if(CurrentProcess-VmDeleted)returnSTATUS_PROCESS_IS_TERMINATING;if(*BaseAddress0){// 选择搜索方向if((AllocationTypeMEM_TOP_DOWN)||CurrentProcess-VmTopDown)ResultMiFindEmptyAddressRangeDownTree(...);elseResultMiFindEmptyAddressRangeInTree(...);// 检查结果if(ResultTableFoundNode||EndingAddressHighestAddress)returnSTATUS_NO_MEMORY;}else{// 验证给定地址ResultMiCheckForConflictingNode(...);if(ResultTableFoundNode)returnSTATUS_CONFLICTING_ADDRESSES;}Vad-StartingVpnStartingAddressPAGE_SHIFT;Vad-EndingVpnEndingAddressPAGE_SHIFT;// 插入 AVL 树MiLockProcessWorkingSetUnsafe(CurrentProcess,CurrentThread);MiInsertNode(CurrentProcess-VadRoot,(PVOID)Vad,Parent,Result);MiUnlockProcessWorkingSetUnsafe(CurrentProcess,CurrentThread);CurrentProcess-VirtualSizeViewSize;KeReleaseGuardedMutex(CurrentProcess-AddressCreationLock);returnSTATUS_SUCCESS;}4.3 MiRemoveNode文件vadnode.c:403VOID NTAPIMiRemoveNode(IN PMMADDRESS_NODE Node,IN PMM_AVL_TABLE Table){// 调用 RTL AVL 树删除RtlpDeleteAvlTreeNode(Table,Node);Table-NumberGenericTableElements--;// 如果被删除的节点是 hint更新 hintif(Table-NodeHintNode){if(!Table-NumberGenericTableElements)Table-NodeHintNULL;elseTable-NodeHintTable-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){PageCountBYTES_TO_PAGES(Length);AlignmentVpnAlignmentPAGE_SHIFT;LowVpnALIGN_UP_BY(MM_LOWEST_USER_ADDRESSPAGE_SHIFT,AlignmentVpn);if(Table-NumberGenericTableElements0){*BaseLowVpnPAGE_SHIFT;returnTableEmptyTree;}// 取最左节点NodeRtlRightChildAvl(Table-BalancedRoot);while(RtlLeftChildAvl(Node))NodeRtlLeftChildAvl(Node);PreviousNodeNULL;while(Node){if(Node-StartingVpnLowVpnPageCount){*BaseLowVpnPAGE_SHIFT;// 确定父节点方向return(RtlLeftChildAvl(Node)NULL)?TableInsertAsLeft:TableInsertAsRight;}if(Node-EndingVpnLowVpn)LowVpnALIGN_UP_BY(Node-EndingVpn1,AlignmentVpn);PreviousNodeNode;NodeMiGetNextNode(Node);}// 检查最高地址之上是否有空间HighestVpn(MM_HIGHEST_VAD_ADDRESS1)/PAGE_SIZE;if(HighestVpnLowVpnPageCount){*BaseLowVpnPAGE_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(BoundaryAddress1)PAGE_SHIFT;// 从根开始找到结束地址 HighVpn 的最右节点NodeRtlRightChildAvl(Table-BalancedRoot);while((Node-EndingVpnHighVpn)((ChildRtlRightChildAvl(Node))))NodeChild;// 反向遍历while(Node){LowVpnALIGN_UP_BY(Node-EndingVpn1,AlignmentVpn);if((HighVpnLowVpn)((HighVpn-LowVpn)PageCount)){LowVpnALIGN_DOWN_BY(HighVpn-PageCount,AlignmentVpn);*BaseLowVpnPAGE_SHIFT;return...;}if(Node-StartingVpnHighVpn)HighVpnNode-StartingVpn;OldNodeNode;NodeMiGetPreviousNode(Node);}// 检查最低 VAD 之下LowVpnALIGN_UP_BY(MI_LOWEST_VAD_ADDRESS,Alignment)/PAGE_SIZE;if((HighVpnLowVpn)((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);ResultRtlpFindAvlTableNodeOrParent(MmSectionBasedRoot,(PVOID)Section-Address.StartingVpn,Parent);MiInsertNode(MmSectionBasedRoot,Section-Address,Parent,Result);}配套函数MiFindEmptyAddressRangeDownBasedTreevadnode.c:711在MmSectionBasedRoot中从高地址向低地址搜索空闲范围模拟 Windows 2003 的 bug当NTDDI_VERSION NTDDI_VISTA时可能浪费最多 Alignment 字节附录AVL 树辅助函数函数行号功能MiGetPreviousNode423获取 AVL 树中前一个节点中序前驱MiGetNextNode459获取 AVL 树中后一个节点中序后继MiInsertNode207底层 AVL 树节点插入MiRemoveNode403底层 AVL 树节点删除MiCheckSecuredVad813检查 Secured VAD 的权限修改是否合法MiLocateAddress147在当前进程中按虚拟地址查找 VADMmReadWrite2532 字节权限表按保护码查允许的访问类型