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