MM 学习笔记 02miavl.h AVL 树与初始化流程一、miavl.h — VAD 节点的 AVL 树算法文件ntoskrnl/mm/ARM3/miavl.h1.1 设计目的为虚拟地址描述符VAD提供专用的 AVL 树算法实现。与 RTL 通用 AVL 相比MM 版本通过内联比较直接访问StartingVpn/EndingVpn字段避免了回调函数开销。1.2 类型映射#definePRTL_AVL_TABLEPMM_AVL_TABLE// AVL 表#definePRTL_BALANCED_LINKSPMMADDRESS_NODE// 树节点1.3 函数重命名避免符号冲突MM 名称功能MiFindAvlTableNodeOrParent查找节点或其父节点MiPromoteAvlTreeNodeAVL 树旋转提升MiRebalanceAvlTreeNodeAVL 树重新平衡MiInsertAvlTreeNode插入节点MiDeleteAvlTreeNode删除节点1.4 比较函数MiAvlCompareRoutine(Table,Buffer,UserData){CurrentNodeUserData-sizeof(RTL_BALANCED_LINKS);// 回溯到节点起始StartingVpn(ULONG_PTR)Buffer;// 要查找的地址if(StartingVpnCurrentNode-StartingVpn)returnGenericLessThan;if(StartingVpnCurrentNode-EndingVpn)returnGenericEqual;// 含于区间elsereturnGenericGreaterThan;}关键点比较的是地址是否落在节点描述的虚拟地址区间内而非简单的大小比较。1.5 内联函数// 设置父指针保留低2位的平衡因子MiSetParent(Node,Parent):Node-u1.ParentParent|(Node-u1.Balance0x3)// 设置平衡因子仅低2位MiSetBalance(Node,Balance):Node-u1.BalanceBalance// 获取父指针屏蔽低2位的平衡因子MiParentAvl(Node):(PRTL_BALANCED_LINKS)(Node-u1.Parent~0x3)// 获取平衡因子MiBalance(Node):(SCHAR)(Node-u1.Balance)空间优化技巧父指针和平衡因子共用同一个指针字段。由于指针至少 4 字节对齐低 2 位恒为 0可用于存储平衡因子。1.6 配套结构定义在sdk/include/ndk/mmtypes.h// AVL 树表typedefstruct_MM_AVL_TABLE{MMADDRESS_NODE BalancedRoot;// 根节点ULONG_PTR DepthOfTree:5;// 树深度ULONG_PTR Unused:3;ULONG_PTR NumberGenericTableElements:56;// 节点总数PVOID NodeHint;// 节点提示加速查找PVOID NodeFreeHint;// 空闲节点提示}MM_AVL_TABLE;// AVL 树节点typedefstruct_MMADDRESS_NODE{union{LONG_PTR Balance:2;struct_MMADDRESS_NODE*Parent;}u1;struct_MMADDRESS_NODE*LeftChild;struct_MMADDRESS_NODE*RightChild;ULONG_PTR StartingVpn;// 起始 VPN虚拟页号ULONG_PTR EndingVpn;// 结束 VPN}MMADDRESS_NODE;二、ARM3/mminit.c — 内存管理器初始化文件ntoskrnl/mm/ARM3/mminit.c2.1 非分页池大小算法ULONG MmMaximumNonPagedPoolPercent0;// 0 自动计算SIZE_T MmSizeOfNonPagedPoolInBytes0;// 实际大小字节SIZE_T MmMaximumNonPagedPoolInBytes0;// 最大限制SIZE_T MmMinimumNonPagedPoolSize256*1024;// 最小值 256KBSIZE_T MmDefaultMaximumNonPagedPool1*1024*1024;// 默认最大值 1MBSIZE_T MmMinAdditionNonPagedPoolPerMb32*1024;// 每 MB 内存增加的池大小SIZE_T MmMaxAdditionNonPagedPoolPerMb400*1024;// 最大增量计算逻辑注释中的解释非分页池总量 固定基础值 基于物理内存的动态增量如果MmMaximumNonPagedPoolPercent为 0根据物理内存大小自动计算MmMinimumNonPagedPoolSize256KB保证最小可用量2.2 Phase0 初始化由MmArmInitSystem(0, ...)调用MiScanMemoryDescriptors() └─ 从 LoaderBlock-MemoryDescriptorList 遍历所有内存描述符 识别可用 RAM、XIP ROM、坏块、固件保留区 MiComputeColorInformation() MiInitializeColorTables() └─ 计算 L2 Cache 颜色数CacheLineSize / PAGE_SIZE 初始化颜色表使页面分配时考虑缓存颜色对齐 MiBuildPfnDatabase() └─ 计算 PFN 数据库所需空间物理页数 × sizeof(MMPFN) 在非分页池中预留空间 MiMapPfnDatabase() └─ 将 PFN 数据库映射到系统虚拟地址空间 MiInitializeSystemPtes() MiReserveSystemPtes() └─ 初始化系统 PTE 空间各种池类型的 PTE 范围 MiBuildPagedPool() └─ 为分页池构建页表映射 MiInitializeNonPagedPool() └─ 初始化非分页池描述符和底层页面 MiInitializeMemoryEvents() └─ 初始化低内存/高内存通知事件 MiAdjustWorkingSetManagerParameters() └─ 调整工作集管理器参数最小工作集大小等2.3 Phase1 初始化由MmArmInitSystem(1, ...)调用MiInitializeLoadedModuleList() └─ 从 LoaderBlock 读取已加载模块链表初始化 PsLoadedModuleList MiReloadBootLoadedDrivers() └─ 重新处理引导加载的驱动修复导入表 MiBuildImportsForBootDrivers() └─ 构建引导驱动的导入表解析 MiInitializeLargePageSupport() └─ 初始化大页面分配的数据结构 MiInitializeSpecialPool() └─ 初始化 Driver Verifier 特殊池 MmInitBsmThread() └─ 启动后台交换元数据Bsm线程2.4 架构相关的MiInitMachineDependent()x86ARM3/i386/init.c// 定义 x86 模板 PTEMMPTE ValidKernelPde{{0x1A3}};// Valid Accessed Dirty Write GlobalMMPTE ValidKernelPte{{0x1A3}};MMPTE ValidKernelPdeLocal{{0x163}};// 不含 Global 位SMP 本地MMPTE ValidKernelPteLocal{{0x163}};MMPTE DemandZeroPde{{0x1A2}};// 不含 Dirty 位请求零页amd64mm/amd64/init.c// 定义 amd64 模板 PTE64位 构建 PFN 数据库遍历四级页表// PML4 → PDPT → PD → PT 逐层初始化// 构建非分页池、系统 PTE 空间、会话空间布局三、根目录 mminit.c旧版 MM文件ntoskrnl/mm/mminit.c旧版 MM 的初始化入口是MmInitSystem负责初始化MmKernelAddressSpace创建系统内存区域MiInitSystemMemoryAreas创建 ARM3 静态内存区域MiCreateArm3StaticMemoryArea初始化Mm64BitPhysicalAddress、MmDisablePagingExecutive等全局标志现今被 ARM3 的MmArmInitSystem在 Phase1 中回调。四、关键理解两阶段初始化Phase0 建立最基本的内存管理结构PFN DB、系统 PTE、池此时系统尚不能处理缺页异常Phase1 完善加载器、大页面、调试等设施。AVL 树优化MM 版本的 AVL 树通过内联比较和父指针/平衡因子共用字段比通用 RTL AVL 更高效、更节省空间。模板 PTEValidKernelPte/DemandZeroPte等模板 PTE 在初始化时预定义好标志位后续分配页面时直接使用避免了重复设置硬件标志。非分页池大小256KB 起的非分页池 每 MB 物理内存 32KB 的增量保证系统既有足够的非分页内存又不会过度预占。