ReactOS系统中搜索给定长度的空间地址区间中的二叉树

搜索给定长度的空间地址区间

//搜索给定长度的空间地址区间
MmFindGap
MmFindGapTopDown

PVOID
NTAPI
MmFindGap(PMADDRESS_SPACE AddressSpace,ULONG_PTR Length,ULONG_PTR Granularity,BOOLEAN TopDown
);

PMADDRESS_SPACE AddressSpace,//该进程用户空间
ULONG_PTR Length,//寻找的空间间隔大小
ULONG_PTR Granularity,//粒度位，表明空间起点的对齐要求，注意是起点地址
ULONG_PTR TopDown);

MmFindGapTopDown

//搜索给定长度的空间地址区间 
static PVOID
MmFindGapTopDown(PMADDRESS_SPACE AddressSpace,ULONG_PTR Length,ULONG_PTR Granularity)
{PVOID HighestAddress = AddressSpace->LowestAddress < MmSystemRangeStart ?(PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;PVOID AlignedAddress;PMEMORY_AREA Node;PMEMORY_AREA PreviousNode;MmVerifyMemoryAreas(AddressSpace);DPRINT("LowestAddress: %p HighestAddress: %p\n",AddressSpace->LowestAddress, HighestAddress);AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)HighestAddress - Length + 1, Granularity);/* Check for overflow. */if (AlignedAddress > HighestAddress)return NULL;/* Special case for empty tree. */if (AddressSpace->MemoryAreaRoot == NULL){if (AlignedAddress >= (PVOID)AddressSpace->LowestAddress){DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);return AlignedAddress;}DPRINT("MmFindGapTopDown: 0\n");return 0;}/* Go to the node with highest address in the tree. */Node = MmIterateLastNode(AddressSpace->MemoryAreaRoot);/* Check if there is enough space after the last memory area. */if (Node->EndingAddress <= AlignedAddress){DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);return AlignedAddress;}/* Traverse the tree from left to right. */PreviousNode = Node;for (;;){Node = MmIteratePrevNode(Node);if (Node == NULL)break;AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)PreviousNode->StartingAddress - Length + 1, Granularity);/* Check for overflow. */if (AlignedAddress > PreviousNode->StartingAddress)return NULL;if (Node->EndingAddress <= AlignedAddress){DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);return AlignedAddress;}PreviousNode = Node;}AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)PreviousNode->StartingAddress - Length + 1, Granularity);/* Check for overflow. */if (AlignedAddress > PreviousNode->StartingAddress)return NULL;if (AlignedAddress >= (PVOID)AddressSpace->LowestAddress){DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);return AlignedAddress;}DPRINT("MmFindGapTopDown: 0\n");return 0;
}

方便上面代码的阅读，我们看一下，下面的宏定义

#define MM_ROUND_DOWN(x,s)                  \((PVOID)(((ULONG_PTR)(x)) & ~((ULONG_PTR)(s)-1)))
c