下面接着来分析EiAllocatePool函数，这个函数要传入使用者内存类型、内存大小、内存标记和调用者地址。
@H_301_8@#001 static PVOID NTAPI @H_301_8@#002 EiAllocatePool(POOL_TYPE PoolType, @H_301_8@#003 ULONG NumberOfBytes, @H_301_8@#004 ULONG Tag, @H_301_8@#005 PVOID Caller) @H_301_8@#006 { @H_301_8@#007 PVOID Block; @H_301_8@ @H_301_8@获取标记。 @H_301_8@#008 PCHAR TagChars = (PCHAR)&Tag; @H_301_8@#009 @H_301_8@ @H_301_8@检查标记是否等于0. @H_301_8@#010 if (Tag == 0) @H_301_8@#011 KeBugCheckEx(BAD_POOL_CALLER,0x9b,PoolType,NumberOfBytes,(ULONG_PTR)Caller); @H_301_8@ @H_301_8@检查标记是否等于BIG。 @H_301_8@#012 if (Tag == TAG('B','I','G',0)) @H_301_8@#013 KeBugCheckEx(BAD_POOL_CALLER,0x9c,(ULONG_PTR)Caller); @H_301_8@#014 @H_301_8@#015 #define IS_LETTER_OR_DIGIT(c) (((c) >= 'a' && (c) <= 'z') || ((c) >= 'A' && (c) <= 'Z') || ((c) >= '0' && (c) <= '9')) @H_301_8@#016 if (!IS_LETTER_OR_DIGIT(TagChars[0]) && @H_301_8@#017 !IS_LETTER_OR_DIGIT(TagChars[1]) && @H_301_8@#018 !IS_LETTER_OR_DIGIT(TagChars[2]) && @H_301_8@#019 !IS_LETTER_OR_DIGIT(TagChars[3])) @H_301_8@#020 KeBugCheckEx(BAD_POOL_CALLER,0x9d,Tag,(ULONG_PTR)Caller); @H_301_8@#021 @H_301_8@#022 /* FIXME: Handle SESSION_POOL_MASK,VERIFIER_POOL_MASK,QUOTA_POOL_MASK */ @H_301_8@ @H_301_8@根据标志类型来决定分配什么样内存，比如0，2，4，6，8等等就是非分页内存，1，3，5，7等等就是分页内存。 @H_301_8@#023 if (PoolType & PAGED_POOL_MASK) @H_301_8@#024 { @H_301_8@ @H_301_8@这里判断是否可以分配分页内存，当前的请求中断级别大于APC_LEVEL级别时，就不能使用分页内存，否则会出错。 @H_301_8@#025 if (KeGetCurrentIrql() > APC_LEVEL) @H_301_8@#026 KeBugCheckEx(BAD_POOL_CALLER,0x08,KeGetCurrentIrql(),Tag); @H_301_8@ @H_301_8@这里分配分页内存。 @H_301_8@#027 Block = ExAllocatePagedPoolWithTag(PoolType,Tag); @H_301_8@#028 } @H_301_8@#029 else @H_301_8@#030 { @H_301_8@ @H_301_8@这里判断是否可以分配非分页内存，如果请求中断级别大于DISPATCH_LEVEL，就不能分配非分页内存。 @H_301_8@#031 if (KeGetCurrentIrql() > DISPATCH_LEVEL) @H_301_8@#032 KeBugCheckEx(BAD_POOL_CALLER,Tag); @H_301_8@ @H_301_8@这里分配非分页内存。 @H_301_8@#033 Block = ExAllocateNonPagedPoolWithTag(PoolType,Caller); @H_301_8@#034 } @H_301_8@#035 @H_301_8@ @H_301_8@这里判断一定分配内存，但又分配不成功时，就会出错提示。 @H_301_8@#036 if ((PoolType & MUST_SUCCEED_POOL_MASK) && !Block) @H_301_8@#037 KeBugCheckEx(BAD_POOL_CALLER,0x9a,Tag); @H_301_8@#038 return Block; @H_301_8@#039 } @H_301_8@#040 @H_301_8@ @H_301_8@通过上面的函数检查，就可以分配分页内存和非分页内存，下面来关注非分页内存的实现函数，其实非分页内存是使用平衡二叉树（AVL树）来实现的。因此先来看看什么是AVL树。在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文《An algorithm for the organization of information》中发表了它。 @H_301_8@节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
