[tkreuzer] 48606: [NTOSKRNL] - Rewrite MiFindEmptyAddressRangeDownTree. The old implementation's "most awesome loop" duplicated both the initialization and the interation steps. It was also overcom...

Author: tkreuzer
Date: Mon Aug 23 03:00:03 2010
New Revision: 48606

URL: http://svn.reactos.org/svn/reactos?rev=48606&view=rev
Log:
[NTOSKRNL]
- Rewrite MiFindEmptyAddressRangeDownTree. The old implementation's "most awesome loop" duplicated both the initialization and the interation steps. It was also overcomplicated. The new implementation additionally returns the parent for the following table insertion, so this doesnt need to be done in an extra search. The return value is changed from NTSTATUS to TABLE_SEARCH_RESULT
- Modify MiInsertNode to accept a parent and TABLE_SEARCH_RESULT instead of searching for a free location.
- Modify MiCreatePebOrTeb to make use of the new features
- Handle failed allocation of the PEB/TEB
- Fixes a failed assertion that Olaf got
- I tested this code quite some time and no problems were found

Modified:
    trunk/reactos/ntoskrnl/mm/ARM3/miarm.h
    trunk/reactos/ntoskrnl/mm/ARM3/procsup.c
    trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c

Modified: trunk/reactos/ntoskrnl/mm/ARM3/miarm.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/miarm.h?re...
==============================================================================
--- trunk/reactos/ntoskrnl/mm/ARM3/miarm.h [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/ARM3/miarm.h [iso-8859-1] Mon Aug 23 03:00:03 2010
@@ -1050,21 +1050,24 @@
     IN PMM_AVL_TABLE Table
 );

-NTSTATUS
+TABLE_SEARCH_RESULT
 NTAPI
 MiFindEmptyAddressRangeDownTree(
     IN SIZE_T Length,
     IN ULONG_PTR BoundaryAddress,
     IN ULONG_PTR Alignment,
     IN PMM_AVL_TABLE Table,
-    OUT PULONG_PTR Base
+    OUT PULONG_PTR Base,
+    OUT PMMADDRESS_NODE *Parent
 );

VOID
 NTAPI
 MiInsertNode(
+    IN PMM_AVL_TABLE Table,
     IN PMMADDRESS_NODE NewNode,
-    IN PMM_AVL_TABLE Table
+    PMMADDRESS_NODE Parent,
+    TABLE_SEARCH_RESULT Result
 );

VOID

Modified: trunk/reactos/ntoskrnl/mm/ARM3/procsup.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/procsup.c?...
==============================================================================
--- trunk/reactos/ntoskrnl/mm/ARM3/procsup.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/ARM3/procsup.c [iso-8859-1] Mon Aug 23 03:00:03 2010
@@ -55,6 +55,8 @@
     ULONG RandomCoeff;
     ULONG_PTR StartAddress, EndAddress;
     LARGE_INTEGER CurrentTime;
+    TABLE_SEARCH_RESULT Result = TableFoundNode;
+    PMMADDRESS_NODE Parent;

/* Allocate a VAD */
     Vad = ExAllocatePoolWithTag(NonPagedPool, sizeof(MMVAD_LONG), 'ldaV');
@@ -93,26 +95,29 @@
         StartAddress -= RandomCoeff;
         EndAddress = StartAddress + ROUND_TO_PAGES(Size) - 1;

-        /* See if this VA range can be obtained */
-        if (!MiCheckForConflictingNode(StartAddress >> PAGE_SHIFT,
-                                       EndAddress >> PAGE_SHIFT,
-                                       &Process->VadRoot))
-        {
-            /* No conflict, use this address */
-            *Base = StartAddress;
-            goto AfterFound;
-        }
-    }
-    
-    /* For TEBs, or if a PEB location couldn't be found, scan the VAD root */
-    Status = MiFindEmptyAddressRangeDownTree(ROUND_TO_PAGES(Size),
-                                             (ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1,
-                                             PAGE_SIZE,
-                                             &Process->VadRoot,
-                                             Base);
-    ASSERT(NT_SUCCESS(Status));
-    
-AfterFound:
+        /* Try to find something below the random upper margin */
+        Result = MiFindEmptyAddressRangeDownTree(ROUND_TO_PAGES(Size),
+                                                 EndAddress,
+                                                 PAGE_SIZE,
+                                                 &Process->VadRoot,
+                                                 Base,
+                                                 &Parent);
+    }
+
+    /* Check for success. TableFoundNode means nothing free. */
+    if (Result == TableFoundNode)
+    {
+        /* For TEBs, or if a PEB location couldn't be found, scan the VAD root */
+        Result = MiFindEmptyAddressRangeDownTree(ROUND_TO_PAGES(Size),
+                                                 (ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1,
+                                                 PAGE_SIZE,
+                                                 &Process->VadRoot,
+                                                 Base,
+                                                 &Parent);
+        /* Bail out, if still nothing free was found */
+        if (Result == TableFoundNode) return STATUS_NO_MEMORY;
+    }
+    
     /* Validate that it came from the VAD ranges */
     ASSERT(*Base >= (ULONG_PTR)MI_LOWEST_VAD_ADDRESS);

@@ -132,8 +137,8 @@
     /* Insert the VAD */
     ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
     Process->VadRoot.NodeHint = Vad;
-    MiInsertNode((PVOID)Vad, &Process->VadRoot);
-    
+    MiInsertNode(&Process->VadRoot, (PVOID)Vad, Parent, Result);
+
     /* Release the working set */
     MiUnlockProcessWorkingSet(Process, Thread);

Modified: trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c?...
==============================================================================
--- trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c [iso-8859-1] Mon Aug 23 03:00:03 2010
@@ -4,6 +4,7 @@
  * FILE:            ntoskrnl/mm/ARM3/vadnode.c
  * PURPOSE:         ARM Memory Manager VAD Node Algorithms
  * PROGRAMMERS:     ReactOS Portable Systems Group
+ *                  Timo Kreuzer ([e-mail])
  */

/* INCLUDES *******************************************************************/
@@ -92,19 +93,14 @@

VOID
 NTAPI
-MiInsertNode(IN PMMADDRESS_NODE NewNode,
-             IN PMM_AVL_TABLE Table)
-{
-    PMMADDRESS_NODE NodeOrParent = NULL;
-    TABLE_SEARCH_RESULT Result;
-
-    /* Find the node's parent, and where to insert this node */
-    Result = RtlpFindAvlTableNodeOrParent(Table,
-                                          (PVOID)NewNode->StartingVpn,
-                                          &NodeOrParent);
-    
+MiInsertNode(
+    IN PMM_AVL_TABLE Table,
+    IN PMMADDRESS_NODE NewNode,
+    PMMADDRESS_NODE Parent,
+    TABLE_SEARCH_RESULT Result)
+{
     /* Insert it into the tree */
-    RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, Result);
+    RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
 }

VOID
@@ -155,17 +151,18 @@
     return NULL;
 }

-NTSTATUS
-NTAPI
-MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
-                                IN ULONG_PTR BoundaryAddress,
-                                IN ULONG_PTR Alignment,
-                                IN PMM_AVL_TABLE Table,
-                                OUT PULONG_PTR Base)
-{
-    PMMADDRESS_NODE Node, PreviousNode;
-    ULONG_PTR CandidateAddress, EndAddress;
-    ULONG AlignEndVpn, CandidateVpn, BoundaryVpn, LowestVpn, StartVpn, EndVpn;
+TABLE_SEARCH_RESULT
+NTAPI
+MiFindEmptyAddressRangeDownTree(
+    IN SIZE_T Length,
+    IN ULONG_PTR BoundaryAddress,
+    IN ULONG_PTR Alignment,
+    IN PMM_AVL_TABLE Table,
+    OUT PULONG_PTR Base,
+    OUT PMMADDRESS_NODE *Parent)
+{
+    PMMADDRESS_NODE Node, LowestNode, Child;
+    ULONG LowVpn, HighVpn;
     PFN_NUMBER PageCount;

/* Sanity checks */
@@ -174,107 +171,82 @@

/* Compute page length, make sure the boundary address is valid */
     Length = PAGE_ROUND_UP(Length);
+    PageCount = Length >> PAGE_SHIFT;
     if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
-    
-    /* Compute the highest address to start at */
-    CandidateAddress = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);

/* Check if the table is empty */
-    if (!Table->NumberGenericTableElements)
+    if (Table->NumberGenericTableElements == 0)
     {
         /* Tree is empty, the candidate address is already the best one */
-        *Base = CandidateAddress;
-        return STATUS_SUCCESS;
-    }
-
-    /* Starting from the root, go down until the right-most child */
-    Node = RtlRightChildAvl(&Table->BalancedRoot);
-    while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
-
-    /* Get the aligned ending address of this VPN */
-    EndAddress = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
-                          Alignment);
-
-    /* Can we fit the address without overflowing into the node? */
-    if ((EndAddress < BoundaryAddress) &&
-        ((BoundaryAddress - EndAddress) > Length))
+        *Base = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment);
+        return TableEmptyTree;
+    }
+
+    /* Calculate the initial upper margin */
+    HighVpn = BoundaryAddress >> PAGE_SHIFT;
+
+    /* Starting from the root, go down until the right-most child, 
+       trying to stay below the boundary. */
+    LowestNode = Node = RtlRightChildAvl(&Table->BalancedRoot);
+    while ( (Child = RtlRightChildAvl(Node)) && 
+             Child->EndingVpn < HighVpn ) Node = Child;
+
+    /* Now loop the Vad nodes */
+    while (Node)
+    {
+        /* Keep track of the lowest node */
+        LowestNode = Node;
+
+        /* Calculate the lower margin */
+        LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment >> PAGE_SHIFT);
+
+        /* Check if the current bounds are suitable */
+        if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
+        {
+            /* There is enough space to add our node */
+            LowVpn = HighVpn - PageCount;
+            *Base = LowVpn << PAGE_SHIFT;
+
+            /* Can we use the current node as parent? */
+            Child = RtlRightChildAvl(Node);
+            if (!Child)
+            {
+                /* Node has no right child, so use it as parent */
+                *Parent = Node;
+                return TableInsertAsRight;
+            }
+            else
+            {
+                /* Node has a right child, find most left grand child */
+                Node = Child;
+                while ((Child = RtlLeftChildAvl(Node))) Node = Child;
+                *Parent = Node;
+                return TableInsertAsLeft;
+            }
+        }
+
+        /* Update the upper margin if neccessary */
+        if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
+
+        /* Go to the next lower node */
+        Node = MiGetPreviousNode(Node);
+    }
+
+    /* Check if there's enough space before the lowest Vad */
+    LowVpn = ROUND_UP((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) >> PAGE_SHIFT;
+    if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
     {
         /* There is enough space to add our address */
-        *Base = ROUND_UP(BoundaryAddress - Length, Alignment);
-        return STATUS_SUCCESS;
-    }
-    
-    PageCount = Length >> PAGE_SHIFT;
-    CandidateVpn = CandidateAddress >> PAGE_SHIFT;
-    BoundaryVpn = BoundaryAddress >> PAGE_SHIFT;
-    LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT;
-         
-    PreviousNode = MiGetPreviousNode(Node);
-         
-    StartVpn = Node->StartingVpn;
-    EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
-    AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
-         
-    /* Loop until a gap is found */
-    for (PageCount = Length >> PAGE_SHIFT,
-         CandidateVpn = CandidateAddress >> PAGE_SHIFT,
-         BoundaryVpn = BoundaryAddress >> PAGE_SHIFT,
-         LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT,
-         PreviousNode = MiGetPreviousNode(Node),
-         StartVpn = Node->StartingVpn,
-         EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
-         AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
-         PreviousNode;
-         Node = PreviousNode,
-         PreviousNode = MiGetPreviousNode(Node),
-         StartVpn = Node->StartingVpn,
-         EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
-         AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT))
-    {
-        /* Can we fit the address without overflowing into the node? */
-        if ((StartVpn < CandidateVpn) && ((StartVpn - AlignEndVpn) >= PageCount))
-        {
-            /* Check if we can get our candidate address */
-            if ((CandidateVpn > EndVpn) && (BoundaryVpn < StartVpn))
-            {
-                /* Use it */
-                *Base = CandidateAddress;
-                return STATUS_SUCCESS;
-            }
-            
-            /* Otherwise, can we fit it by changing the start address? */
-            if (StartVpn > AlignEndVpn)
-            {
-                /* It'll fit, compute the new base address for that to work */
-                *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
-                return STATUS_SUCCESS;
-            }
-        }
-        
-        PreviousNode = MiGetPreviousNode(Node);
-        StartVpn = Node->StartingVpn;
-        EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
-        AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
-    }
-
-    /* See if we could squeeze into the last descriptor */
-    if ((StartVpn > LowestVpn) && ((StartVpn - LowestVpn) >= PageCount))
-    {
-        /* Check if we can try our candidate address */
-        if (BoundaryVpn < StartVpn)
-        {
-            /* Use it */
-            *Base = CandidateAddress;
-            return STATUS_SUCCESS;
-        }
-
-        /* Otherwise, change the base address to what's needed to fit in */
-        *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
-        return STATUS_SUCCESS;
-    }
-        
+        LowVpn = HighVpn - PageCount;
+        *Base = LowVpn << PAGE_SHIFT;
+        *Parent = LowestNode;
+        return TableInsertAsLeft;
+    }
+
     /* No address space left at all */
-    return STATUS_NO_MEMORY;
+    *Base = 0;
+    *Parent = NULL;
+    return TableFoundNode;
 }

/* EOF */