[tkreuzer] 55397: [NTOSKRNL] - Rewrite MmFindGapBottomUp and MmFindGapTopDown, the old versions were broken and were first checking the address range after the first memory area and only used the a...

Author: tkreuzer
Date: Fri Feb  3 20:59:35 2012
New Revision: 55397

URL: http://svn.reactos.org/svn/reactos?rev=55397&view=rev
Log:
[NTOSKRNL]
- Rewrite MmFindGapBottomUp and MmFindGapTopDown, the old versions were broken and were first checking the address range after the first memory area and only used the area below (above) the first memory are when nothing free was found.
- Fix an ASSERT, that gets triggered now that the memory areas are created at the "right" locations
- Create a memory are for the boot loaded images, which previously could be overwritten happily by new memory areas, which was only prevented by the brokenness of the code
- Fix a few memory regions so that they are correct for amd64 builds as well

Modified:
    trunk/reactos/ntoskrnl/ex/init.c
    trunk/reactos/ntoskrnl/include/internal/i386/mm.h
    trunk/reactos/ntoskrnl/mm/marea.c
    trunk/reactos/ntoskrnl/mm/mminit.c

Modified: trunk/reactos/ntoskrnl/ex/init.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/ex/init.c?rev=5539...
==============================================================================
--- trunk/reactos/ntoskrnl/ex/init.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/ex/init.c [iso-8859-1] Fri Feb  3 20:59:35 2012
@@ -331,7 +331,7 @@
     }

/* Copy the codepage data in its new location. */
-    ASSERT(SectionBase > MmSystemRangeStart);
+    ASSERT(SectionBase >= MmSystemRangeStart);
     RtlCopyMemory(SectionBase, ExpNlsTableBase, ExpNlsTableSize);

/* Free the previously allocated buffer and set the new location */

Modified: trunk/reactos/ntoskrnl/include/internal/i386/mm.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/include/internal/i...
==============================================================================
--- trunk/reactos/ntoskrnl/include/internal/i386/mm.h [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/include/internal/i386/mm.h [iso-8859-1] Fri Feb  3 20:59:35 2012
@@ -30,6 +30,7 @@
 #define PDE_TOP     0xC0300FFF
 #define PTE_TOP     0xC03FFFFF
 #define HYPER_SPACE 0xC0400000
+#define HYPER_SPACE_END 0xC07FFFFF

#define PTE_PER_PAGE 0x400

Modified: trunk/reactos/ntoskrnl/mm/marea.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/marea.c?rev=553...
==============================================================================
--- trunk/reactos/ntoskrnl/mm/marea.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/marea.c [iso-8859-1] Fri Feb  3 20:59:35 2012
@@ -456,78 +456,68 @@
    ULONG_PTR Length,
    ULONG_PTR Granularity)
 {
-   PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
-   PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
-                            MmHighestUserAddress : (PVOID)MAXULONG_PTR;
-   PVOID AlignedAddress;
-   PMEMORY_AREA Node;
-   PMEMORY_AREA FirstNode;
-   PMEMORY_AREA PreviousNode;
-
-   DPRINT("LowestAddress: %p HighestAddress: %p\n",
-          LowestAddress, HighestAddress);
-
-   AlignedAddress = MM_ROUND_UP(LowestAddress, Granularity);
-
-   /* Special case for empty tree. */
-   if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
-   {
-      if ((ULONG_PTR)HighestAddress - (ULONG_PTR)AlignedAddress >= Length)
-      {
-         DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
-         return AlignedAddress;
-      }
-      DPRINT("MmFindGapBottomUp: 0\n");
-      return 0;
-   }
-
-   /* Go to the node with lowest address in the tree. */
-   FirstNode = Node = MmIterateFirstNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
-
-   /* Traverse the tree from left to right. */
-   PreviousNode = Node;
-   for (;;)
-   {
-      Node = MmIterateNextNode(Node);
-      if (Node == NULL)
-         break;
-
-      AlignedAddress = MM_ROUND_UP(PreviousNode->EndingAddress, Granularity);
-      if (AlignedAddress >= LowestAddress)
-      {
-          if (Node->StartingAddress > AlignedAddress &&
-              (ULONG_PTR)Node->StartingAddress - (ULONG_PTR)AlignedAddress >= Length)
-          {
-             DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
-             ASSERT(AlignedAddress >= LowestAddress);
-             return AlignedAddress;
-          }
-      }
-      PreviousNode = Node;
-   }
-
-   /* Check if there is enough space after the last memory area. */
-   AlignedAddress = MM_ROUND_UP(PreviousNode->EndingAddress, Granularity);
-   if ((ULONG_PTR)HighestAddress > (ULONG_PTR)AlignedAddress &&
-       (ULONG_PTR)HighestAddress - (ULONG_PTR)AlignedAddress >= Length)
-   {
-      DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
-      ASSERT(AlignedAddress >= LowestAddress);
-      return AlignedAddress;
-   }
-
-   /* Check if there is enough space before the first memory area. */
-   AlignedAddress = MM_ROUND_UP(LowestAddress, Granularity);
-   if (FirstNode->StartingAddress > AlignedAddress &&
-       (ULONG_PTR)FirstNode->StartingAddress - (ULONG_PTR)AlignedAddress >= Length)
-   {
-      DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
-      ASSERT(AlignedAddress >= LowestAddress);
-      return AlignedAddress;
-   }
-
-   DPRINT("MmFindGapBottomUp: 0\n");
-   return 0;
+    ULONG_PTR LowestAddress, HighestAddress, Candidate;
+    PMEMORY_AREA Root, Node;
+
+    /* Get the margins of the address space */
+    if (MmGetAddressSpaceOwner(AddressSpace) != NULL)
+    {
+        LowestAddress = MM_LOWEST_USER_ADDRESS;
+        HighestAddress = (ULONG_PTR)MmHighestUserAddress;
+    }
+    else
+    {
+        LowestAddress = (ULONG_PTR)MmSystemRangeStart;
+        HighestAddress = MAXULONG_PTR;
+    }
+
+    /* Start with the lowest address */
+    Candidate = LowestAddress;
+
+    /* Check for overflow */
+    if ((Candidate + Length) < Candidate) return NULL;
+
+    /* Get the root of the address space tree */
+    Root = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
+
+    /* Go to the node with lowest address in the tree. */
+    Node = Root ? MmIterateFirstNode(Root) : NULL;
+    while (Node && ((ULONG_PTR)Node->EndingAddress < LowestAddress))
+    {
+        Node = MmIterateNextNode(Node);
+    }
+
+    /* Traverse the tree from low to high addresses */
+    while (Node && ((ULONG_PTR)Node->EndingAddress < HighestAddress))
+    {
+        /* Check if the memory area fits before the current node */
+        if ((ULONG_PTR)Node->StartingAddress >= (Candidate + Length))
+        {
+            DPRINT("MmFindGapBottomUp: %p\n", Candidate);
+            ASSERT(Candidate >= LowestAddress);
+            return (PVOID)Candidate;
+        }
+
+        /* Calculate next possible adress above this node */
+        Candidate = ALIGN_UP_BY((ULONG_PTR)Node->EndingAddress, Granularity);
+
+        /* Check for overflow */
+        if ((Candidate + Length) < (ULONG_PTR)Node->EndingAddress) return NULL;
+
+        /* Go to the next higher node */
+        Node = MmIterateNextNode(Node);
+    }
+
+    /* Check if there is enough space after the last memory area. */
+    if ((Candidate + Length) <= HighestAddress)
+    {
+        DPRINT("MmFindGapBottomUp: %p\n", Candidate);
+        ASSERT(Candidate >= LowestAddress);
+        return (PVOID)Candidate;
+    }
+
+    DPRINT("MmFindGapBottomUp: 0\n");
+    return NULL;
 }

@@ -537,81 +527,68 @@
    ULONG_PTR Length,
    ULONG_PTR Granularity)
 {
-   PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
-   PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
-                          (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
-   PVOID AlignedAddress;
-   PMEMORY_AREA Node;
-   PMEMORY_AREA PreviousNode;
-
-   DPRINT("LowestAddress: %p HighestAddress: %p\n",
-          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->WorkingSetExpansionLinks.Flink == NULL)
-   {
-      if (AlignedAddress >= 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((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
-
-   /* 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 >= LowestAddress)
-   {
-      DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
-      return AlignedAddress;
-   }
-
-   DPRINT("MmFindGapTopDown: 0\n");
-   return 0;
+    ULONG_PTR LowestAddress, HighestAddress, Candidate;
+    PMEMORY_AREA Root, Node;
+
+    /* Get the margins of the address space */
+    if (MmGetAddressSpaceOwner(AddressSpace) != NULL)
+    {
+        LowestAddress = (ULONG_PTR)MM_LOWEST_USER_ADDRESS;
+        HighestAddress = (ULONG_PTR)MmHighestUserAddress;
+    }
+    else
+    {
+        LowestAddress = (ULONG_PTR)MmSystemRangeStart;
+        HighestAddress = MAXULONG_PTR;
+    }
+
+    /* Calculate the highest candidate */
+    Candidate = ALIGN_DOWN_BY(HighestAddress + 1 - Length, Granularity);
+
+    /* Check for overflow. */
+    if (Candidate > HighestAddress) return NULL;
+
+    /* Get the root of the address space tree */
+    Root = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
+
+    /* Go to the node with highest address in the tree. */
+    Node = Root ? MmIterateLastNode(Root) : NULL;
+    while (Node && ((ULONG_PTR)Node->StartingAddress > HighestAddress))
+    {
+        Node = MmIteratePrevNode(Node);
+    }
+
+    /* Traverse the tree from high to low addresses */
+    while (Node && ((ULONG_PTR)Node->StartingAddress > LowestAddress))
+    {
+        /* Check if the memory area fits after the current node */
+        if ((ULONG_PTR)Node->EndingAddress <= Candidate)
+        {
+            DPRINT("MmFindGapTopDown: %p\n", Candidate);
+            return (PVOID)Candidate;
+        }
+
+        /* Calculate next possible adress below this node */
+        Candidate = ALIGN_DOWN_BY((ULONG_PTR)Node->StartingAddress - Length,
+                                  Granularity);
+
+        /* Check for overflow. */
+        if (Candidate > (ULONG_PTR)Node->StartingAddress)
+            return NULL;
+
+        /* Go to the next lower node */
+        Node = MmIteratePrevNode(Node);
+    }
+
+    /* Check if the last candidate is inside the given range */
+    if (Candidate >= LowestAddress)
+    {
+        DPRINT("MmFindGapTopDown: %p\n", Candidate);
+        return (PVOID)Candidate;
+    }
+
+    DPRINT("MmFindGapTopDown: 0\n");
+    return NULL;
 }

@@ -887,7 +864,7 @@
    ULONG_PTR tmpLength;
    PMEMORY_AREA MemoryArea;

-   DPRINT("MmCreateMemoryArea(Type %d, BaseAddress %p, "
+   DPRINT("MmCreateMemoryArea(Type 0x%lx, BaseAddress %p, "
           "*BaseAddress %p, Length %p, AllocationFlags %x, "
           "FixedAddress %x, Result %p)\n",
           Type, BaseAddress, *BaseAddress, Length, AllocationFlags,
@@ -922,6 +899,7 @@
       if (MmGetAddressSpaceOwner(AddressSpace) &&
           (ULONG_PTR)(*BaseAddress) + tmpLength > (ULONG_PTR)MmSystemRangeStart)
       {
+         DPRINT("Memory area for user mode address space exceeds MmSystemRangeStart\n");
          return STATUS_ACCESS_VIOLATION;
       }

@@ -1026,8 +1004,9 @@
    DPRINT("MmDeleteProcessAddressSpace(Process %x (%s))\n", Process,
           Process->ImageFileName);

+#ifndef _M_AMD64
    RemoveEntryList(&Process->MmProcessLinks);
-
+#endif
    MmLockAddressSpace(&Process->Vm);

while ((MemoryArea = (PMEMORY_AREA)Process->Vm.WorkingSetExpansionLinks.Flink) != NULL)

Modified: trunk/reactos/ntoskrnl/mm/mminit.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/mminit.c?rev=55...
==============================================================================
--- trunk/reactos/ntoskrnl/mm/mminit.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/mminit.c [iso-8859-1] Fri Feb  3 20:59:35 2012
@@ -1,4 +1,4 @@
-/*
+/*
  * PROJECT:         ReactOS Kernel
  * LICENSE:         GPL - See COPYING in the top level directory
  * FILE:            ntoskrnl/mm/mminit.c
@@ -45,13 +45,28 @@
     BoundaryAddressMultiple.QuadPart = 0;

//
+    // Create the memory area to define the loader mappings
+    //
+    BaseAddress = (PVOID)KSEG0_BASE;
+    Status = MmCreateMemoryArea(MmGetKernelAddressSpace(),
+                                MEMORY_AREA_OWNED_BY_ARM3 | MEMORY_AREA_STATIC,
+                                &BaseAddress,
+                                MmBootImageSize,
+                                PAGE_EXECUTE_READWRITE,
+                                &MArea,
+                                TRUE,
+                                0,
+                                BoundaryAddressMultiple);
+    ASSERT(Status == STATUS_SUCCESS);
+
+    //
     // Create the memory area to define the PTE base
     //
     BaseAddress = (PVOID)PTE_BASE;
     Status = MmCreateMemoryArea(MmGetKernelAddressSpace(),
                                 MEMORY_AREA_OWNED_BY_ARM3 | MEMORY_AREA_STATIC,
                                 &BaseAddress,
-                                4 * 1024 * 1024,
+                                PTE_TOP - PTE_BASE + 1,
                                 PAGE_READWRITE,
                                 &MArea,
                                 TRUE,
@@ -66,7 +81,7 @@
     Status = MmCreateMemoryArea(MmGetKernelAddressSpace(),
                                 MEMORY_AREA_OWNED_BY_ARM3 | MEMORY_AREA_STATIC,
                                 &BaseAddress,
-                                4 * 1024 * 1024,
+                                HYPER_SPACE_END - HYPER_SPACE + 1,
                                 PAGE_READWRITE,
                                 &MArea,
                                 TRUE,
@@ -165,7 +180,7 @@
                                 0,
                                 BoundaryAddressMultiple);
     ASSERT(Status == STATUS_SUCCESS);
-
+#ifndef _M_AMD64
     //
     // Next, the KPCR
     //
@@ -180,7 +195,7 @@
                                 0,
                                 BoundaryAddressMultiple);
     ASSERT(Status == STATUS_SUCCESS);
-
+#endif
     //
     // Now the KUSER_SHARED_DATA
     //
@@ -238,8 +253,8 @@
     // Print the memory layout
     //
     DPRINT1("          0x%p - 0x%p\t%s\n",
-            MmSystemRangeStart,
-            (ULONG_PTR)MmSystemRangeStart + MmBootImageSize,
+            KSEG0_BASE,
+            (ULONG_PTR)KSEG0_BASE + MmBootImageSize,
             "Boot Loaded Image");
     DPRINT1("          0x%p - 0x%p\t%s\n",
             MmPfnDatabase,
@@ -258,13 +273,13 @@
             MiSessionSpaceEnd,
             "Session Space");
     DPRINT1("          0x%p - 0x%p\t%s\n",
-            PTE_BASE, PDE_BASE,
+            PTE_BASE, PTE_TOP,
             "Page Tables");
     DPRINT1("          0x%p - 0x%p\t%s\n",
-            PDE_BASE, HYPER_SPACE,
+            PDE_BASE, PDE_TOP,
             "Page Directories");
     DPRINT1("          0x%p - 0x%p\t%s\n",
-            HYPER_SPACE, HYPER_SPACE + (4 * 1024 * 1024),
+            HYPER_SPACE, HYPER_SPACE_END,
             "Hyperspace");
     DPRINT1("          0x%p - 0x%p\t%s\n",
             MmPagedPoolStart,