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