MM 学习笔记 02：miavl.h AVL 树与初始化流程

MM 学习笔记 02：miavl.h AVL 树与初始化流程

一、miavl.h — VAD 节点的 AVL 树算法

文件：ntoskrnl/mm/ARM3/miavl.h

1.1 设计目的

为虚拟地址描述符（VAD）提供专用的 AVL 树算法实现。与 RTL 通用 AVL 相比，MM 版本通过内联比较（直接访问StartingVpn/EndingVpn字段）避免了回调函数开销。

1.2 类型映射

#definePRTL_AVL_TABLEPMM_AVL_TABLE// AVL 表#definePRTL_BALANCED_LINKSPMMADDRESS_NODE// 树节点

1.3 函数重命名（避免符号冲突）

1.4 比较函数

MiAvlCompareRoutine(Table,Buffer,UserData){CurrentNode=UserData-sizeof(RTL_BALANCED_LINKS);// 回溯到节点起始StartingVpn=(ULONG_PTR)Buffer;// 要查找的地址if(StartingVpn<CurrentNode->StartingVpn)returnGenericLessThan;if(StartingVpn<=CurrentNode->EndingVpn)returnGenericEqual;// 含于区间elsereturnGenericGreaterThan;}

关键点：比较的是"地址是否落在节点描述的虚拟地址区间内"，而非简单的大小比较。

1.5 内联函数

// 设置父指针（保留低2位的平衡因子）MiSetParent(Node,Parent):Node->u1.Parent=Parent|(Node->u1.Balance&0x3)// 设置平衡因子（仅低2位）MiSetBalance(Node,Balance):Node->u1.Balance=Balance// 获取父指针（屏蔽低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.c

2.1 非分页池大小算法

ULONG MmMaximumNonPagedPoolPercent=0;// 0 = 自动计算SIZE_T MmSizeOfNonPagedPoolInBytes=0;// 实际大小（字节）SIZE_T MmMaximumNonPagedPoolInBytes=0;// 最大限制SIZE_T MmMinimumNonPagedPoolSize=256*1024;// 最小值 256KBSIZE_T MmDefaultMaximumNonPagedPool=1*1024*1024;// 默认最大值 1MBSIZE_T MmMinAdditionNonPagedPoolPerMb=32*1024;// 每 MB 内存增加的池大小SIZE_T MmMaxAdditionNonPagedPoolPerMb=400*1024;// 最大增量

计算逻辑（注释中的解释）：

• 非分页池总量 = 固定基础值 + 基于物理内存的动态增量
• 如果MmMaximumNonPagedPoolPercent为 0，根据物理内存大小自动计算
• MmMinimumNonPagedPoolSize（256KB）保证最小可用量

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()

x86（ARM3/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 位（请求零页）

amd64（mm/amd64/init.c）：

// 定义 amd64 模板 PTE（64位）+ 构建 PFN 数据库遍历四级页表// PML4 → PDPT → PD → PT 逐层初始化// 构建非分页池、系统 PTE 空间、会话空间布局

三、根目录 mminit.c（旧版 MM）

文件：ntoskrnl/mm/mminit.c

旧版 MM 的初始化入口是MmInitSystem，负责：

• 初始化MmKernelAddressSpace
• 创建系统内存区域（MiInitSystemMemoryAreas）
• 创建 ARM3 静态内存区域（MiCreateArm3StaticMemoryArea）
• 初始化Mm64BitPhysicalAddress、MmDisablePagingExecutive等全局标志

现今被 ARM3 的MmArmInitSystem在 Phase1 中回调。

四、关键理解

1. 两阶段初始化：Phase0 建立最基本的内存管理结构（PFN DB、系统 PTE、池），此时系统尚不能处理缺页异常；Phase1 完善加载器、大页面、调试等设施。

2. AVL 树优化：MM 版本的 AVL 树通过内联比较和父指针/平衡因子共用字段，比通用 RTL AVL 更高效、更节省空间。

3. 模板 PTE：ValidKernelPte/DemandZeroPte等模板 PTE 在初始化时预定义好标志位，后续分配页面时直接使用，避免了重复设置硬件标志。

4. 非分页池大小：256KB 起的非分页池 + 每 MB 物理内存 32KB 的增量，保证系统既有足够的非分页内存，又不会过度预占。