ntoskrnl/mm/ARM3/vadnode.c

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         BSD - See COPYING.ARM in the top level directory
   4  * FILE:            ntoskrnl/mm/ARM3/vadnode.c
   5  * PURPOSE:         ARM Memory Manager VAD Node Algorithms
   6  * PROGRAMMERS:     ReactOS Portable Systems Group
   7  *                  Timo Kreuzer (timo.kreuzer@reactos.org)
   8  */
   9
  10 /* INCLUDES *******************************************************************/
  11
  12 #include <ntoskrnl.h>
  13 #define NDEBUG
  14 #include <debug.h>
  15
  16 #line 15 "ARM³::VADNODE"
  17 #define MODULE_INVOLVED_IN_ARM3
  18 #include "../ARM3/miarm.h"
  19
  20 /* Include Mm version of AVL support */
  21 #include "../ARM3/miavl.h"
  22 #include "../../../lib/rtl/avlsupp.c"
  23
  24 /* FUNCTIONS ******************************************************************/
  25
  26 PMMVAD
  27 NTAPI
  28 MiLocateAddress(IN PVOID VirtualAddress)
  29 {
  30     PMMVAD FoundVad;
  31     ULONG_PTR Vpn;
  32     PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
  33     TABLE_SEARCH_RESULT SearchResult;
  34
  35     /* Start with the the hint */
  36     FoundVad = (PMMVAD)Table->NodeHint;
  37     if (!FoundVad) return NULL;
  38
  39     /* Check if this VPN is in the hint, if so, use it */
  40     Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
  41     if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
  42
  43     /* VAD hint didn't work, go look for it */
  44     SearchResult = RtlpFindAvlTableNodeOrParent(Table,
  45                                                 (PVOID)Vpn,
  46                                                 (PMMADDRESS_NODE*)&FoundVad);
  47     if (SearchResult != TableFoundNode) return NULL;
  48
  49     /* We found it, update the hint */
  50     ASSERT(FoundVad != NULL);
  51     ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
  52     Table->NodeHint = FoundVad;
  53     return FoundVad;
  54 }
  55
  56 PMMADDRESS_NODE
  57 NTAPI
  58 MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
  59                           IN ULONG_PTR EndVpn,
  60                           IN PMM_AVL_TABLE Table)
  61 {
  62     PMMADDRESS_NODE CurrentNode;
  63
  64     /* If the tree is empty, there is no conflict */
  65     if (!Table->NumberGenericTableElements) return NULL;
  66
  67     /* Start looping from the right */
  68     CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
  69     ASSERT(CurrentNode != NULL);
  70     while (CurrentNode)
  71     {
  72         /* This address comes after */
  73         if (StartVpn > CurrentNode->EndingVpn)
  74         {
  75             /* Keep searching on the right */
  76             CurrentNode = RtlRightChildAvl(CurrentNode);
  77         }
  78         else if (EndVpn < CurrentNode->StartingVpn)
  79         {
  80             /* This address ends before the node starts, search on the left */
  81             CurrentNode = RtlLeftChildAvl(CurrentNode);
  82         }
  83         else
  84         {
  85             /* This address is part of this node, return it */
  86             break;
  87         }
  88     }
  89
  90     /* Return either the conflicting node, or no node at all */
  91     return CurrentNode;
  92 }
  93
  94 VOID
  95 NTAPI
  96 MiInsertNode(
  97     IN PMM_AVL_TABLE Table,
  98     IN PMMADDRESS_NODE NewNode,
  99     PMMADDRESS_NODE Parent,
 100     TABLE_SEARCH_RESULT Result)
 101 {
 102     /* Insert it into the tree */
 103     RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
 104 }
 105
 106 VOID
 107 NTAPI
 108 MiRemoveNode(IN PMMADDRESS_NODE Node,
 109              IN PMM_AVL_TABLE Table)
 110 {
 111     DPRINT("Removing address node: %lx %lx\n", Node->StartingVpn, Node->EndingVpn);
 112
 113     /* Call the AVL code */
 114     RtlpDeleteAvlTreeNode(Table, Node);
 115
 116     /* Decrease element count */
 117     Table->NumberGenericTableElements--;
 118
 119     /* Check if this node was the hint */
 120     if (Table->NodeHint == Node)
 121     {
 122         /* Get a new hint, unless we're empty now, in which case nothing */
 123         if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
 124         else Table->NodeHint = Table->BalancedRoot.RightChild;
 125     }
 126 }
 127
 128 PMMADDRESS_NODE
 129 NTAPI
 130 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
 131 {
 132     PMMADDRESS_NODE Parent;
 133
 134     /* Get the left child */
 135     if (RtlLeftChildAvl(Node))
 136     {
 137         /* Get right-most child */
 138         Node = RtlLeftChildAvl(Node);
 139         while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
 140         return Node;
 141     }
 142
 143     Parent = RtlParentAvl(Node);
 144     ASSERT(Parent != NULL);
 145     while (Parent != Node)
 146     {
 147         /* The parent should be a right child, return the real predecessor */
 148         if (RtlIsRightChildAvl(Node))
 149         {
 150             /* Return it unless it's the root */
 151             if (Parent == RtlParentAvl(Parent)) Parent = NULL;
 152             return Parent;
 153         }
 154
 155         /* Keep lopping until we find our parent */
 156         Node = Parent;
 157         Parent = RtlParentAvl(Node);
 158     }
 159
 160     /* Nothing found */
 161     return NULL;
 162 }
 163
 164 TABLE_SEARCH_RESULT
 165 NTAPI
 166 MiFindEmptyAddressRangeDownTree(
 167     IN SIZE_T Length,
 168     IN ULONG_PTR BoundaryAddress,
 169     IN ULONG_PTR Alignment,
 170     IN PMM_AVL_TABLE Table,
 171     OUT PULONG_PTR Base,
 172     OUT PMMADDRESS_NODE *Parent)
 173 {
 174     PMMADDRESS_NODE Node, LowestNode, Child;
 175     ULONG LowVpn, HighVpn;
 176     PFN_NUMBER PageCount;
 177
 178     /* Sanity checks */
 179     ASSERT(BoundaryAddress);
 180     ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
 181
 182     /* Compute page length, make sure the boundary address is valid */
 183     Length = PAGE_ROUND_UP(Length);
 184     PageCount = Length >> PAGE_SHIFT;
 185     if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
 186
 187     /* Check if the table is empty */
 188     if (Table->NumberGenericTableElements == 0)
 189     {
 190         /* Tree is empty, the candidate address is already the best one */
 191         *Base = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment);
 192         return TableEmptyTree;
 193     }
 194
 195     /* Calculate the initial upper margin */
 196     HighVpn = BoundaryAddress >> PAGE_SHIFT;
 197
 198     /* Starting from the root, go down until the right-most child,
 199        trying to stay below the boundary. */
 200     LowestNode = Node = RtlRightChildAvl(&Table->BalancedRoot);
 201     while ( (Child = RtlRightChildAvl(Node)) &&
 202              Child->EndingVpn < HighVpn ) Node = Child;
 203
 204     /* Now loop the Vad nodes */
 205     while (Node)
 206     {
 207         /* Keep track of the lowest node */
 208         LowestNode = Node;
 209
 210         /* Calculate the lower margin */
 211         LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment >> PAGE_SHIFT);
 212
 213         /* Check if the current bounds are suitable */
 214         if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
 215         {
 216             /* There is enough space to add our node */
 217             LowVpn = HighVpn - PageCount;
 218             *Base = LowVpn << PAGE_SHIFT;
 219
 220             /* Can we use the current node as parent? */
 221             Child = RtlRightChildAvl(Node);
 222             if (!Child)
 223             {
 224                 /* Node has no right child, so use it as parent */
 225                 *Parent = Node;
 226                 return TableInsertAsRight;
 227             }
 228             else
 229             {
 230                 /* Node has a right child, find most left grand child */
 231                 Node = Child;
 232                 while ((Child = RtlLeftChildAvl(Node))) Node = Child;
 233                 *Parent = Node;
 234                 return TableInsertAsLeft;
 235             }
 236         }
 237
 238         /* Update the upper margin if neccessary */
 239         if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
 240
 241         /* Go to the next lower node */
 242         Node = MiGetPreviousNode(Node);
 243     }
 244
 245     /* Check if there's enough space before the lowest Vad */
 246     LowVpn = ROUND_UP((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) >> PAGE_SHIFT;
 247     if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
 248     {
 249         /* There is enough space to add our address */
 250         LowVpn = HighVpn - PageCount;
 251         *Base = LowVpn << PAGE_SHIFT;
 252         *Parent = LowestNode;
 253         return TableInsertAsLeft;
 254     }
 255
 256     /* No address space left at all */
 257     *Base = 0;
 258     *Parent = NULL;
 259     return TableFoundNode;
 260 }
 261
 262 /* EOF */