reactos/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  */
   8
   9 /* INCLUDES *******************************************************************/
  10
  11 #include <ntoskrnl.h>
  12 #define NDEBUG
  13 #include <debug.h>
  14
  15 #line 15 "ARM³::VADNODE"
  16 #define MODULE_INVOLVED_IN_ARM3
  17 #include "../ARM3/miarm.h"
  18
  19 /* Include Mm version of AVL support */
  20 #include "../ARM3/miavl.h"
  21 #include "../../../lib/rtl/avlsupp.c"
  22
  23 /* FUNCTIONS ******************************************************************/
  24
  25 PMMVAD
  26 NTAPI
  27 MiLocateAddress(IN PVOID VirtualAddress)
  28 {
  29     PMMVAD FoundVad;
  30     ULONG_PTR Vpn;
  31     PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
  32     TABLE_SEARCH_RESULT SearchResult;
  33
  34     /* Start with the the hint */
  35     FoundVad = (PMMVAD)Table->NodeHint;
  36     if (!FoundVad) return NULL;
  37
  38     /* Check if this VPN is in the hint, if so, use it */
  39     Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
  40     if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
  41
  42     /* VAD hint didn't work, go look for it */
  43     SearchResult = RtlpFindAvlTableNodeOrParent(Table,
  44                                                 (PVOID)Vpn,
  45                                                 (PMMADDRESS_NODE*)&FoundVad);
  46     if (SearchResult != TableFoundNode) return NULL;
  47
  48     /* We found it, update the hint */
  49     ASSERT(FoundVad != NULL);
  50     ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
  51     Table->NodeHint = FoundVad;
  52     return FoundVad;
  53 }
  54
  55 PMMADDRESS_NODE
  56 NTAPI
  57 MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
  58                           IN ULONG_PTR EndVpn,
  59                           IN PMM_AVL_TABLE Table)
  60 {
  61     PMMADDRESS_NODE CurrentNode;
  62
  63     /* If the tree is empty, there is no conflict */
  64     if (!Table->NumberGenericTableElements) return NULL;
  65
  66     /* Start looping from the right */
  67     CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
  68     ASSERT(CurrentNode != NULL);
  69     while (CurrentNode)
  70     {
  71         /* This address comes after */
  72         if (StartVpn > CurrentNode->EndingVpn)
  73         {
  74             /* Keep searching on the right */
  75             CurrentNode = RtlRightChildAvl(CurrentNode);
  76         }
  77         else if (EndVpn < CurrentNode->StartingVpn)
  78         {
  79             /* This address ends before the node starts, search on the left */
  80             CurrentNode = RtlLeftChildAvl(CurrentNode);
  81         }
  82         else
  83         {
  84             /* This address is part of this node, return it */
  85             break;
  86         }
  87     }
  88
  89     /* Return either the conflicting node, or no node at all */
  90     return CurrentNode;
  91 }
  92
  93 VOID
  94 NTAPI
  95 MiInsertNode(IN PMMADDRESS_NODE NewNode,
  96              IN PMM_AVL_TABLE Table)
  97 {
  98     PMMADDRESS_NODE NodeOrParent = NULL;
  99     TABLE_SEARCH_RESULT Result;
 100
 101     /* Find the node's parent, and where to insert this node */
 102     Result = RtlpFindAvlTableNodeOrParent(Table,
 103                                           (PVOID)NewNode->StartingVpn,
 104                                           &NodeOrParent);
 105
 106     /* Insert it into the tree */
 107     RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, Result);
 108 }
 109
 110 VOID
 111 NTAPI
 112 MiRemoveNode(IN PMMADDRESS_NODE Node,
 113              IN PMM_AVL_TABLE Table)
 114 {
 115     /* Call the AVL code */
 116     RtlpDeleteAvlTreeNode(Table, Node);
 117
 118     /* Decrease element count */
 119     Table->NumberGenericTableElements--;
 120 }
 121
 122 PMMADDRESS_NODE
 123 NTAPI
 124 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
 125 {
 126     PMMADDRESS_NODE Parent;
 127
 128     /* Get the left child */
 129     if (RtlLeftChildAvl(Node))
 130     {
 131         /* Get right-most child */
 132         Node = RtlLeftChildAvl(Node);
 133         while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
 134         return Node;
 135     }
 136
 137     Parent = RtlParentAvl(Node);
 138     ASSERT(Parent != NULL);
 139     while (Parent != Node)
 140     {
 141         /* The parent should be a right child, return the real predecessor */
 142         if (RtlIsRightChildAvl(Node))
 143         {
 144             /* Return it unless it's the root */
 145             if (Parent == RtlParentAvl(Parent)) Parent = NULL;
 146             return Parent;
 147         }
 148
 149         /* Keep lopping until we find our parent */
 150         Node = Parent;
 151         Parent = RtlParentAvl(Node);
 152     }
 153
 154     /* Nothing found */
 155     return NULL;
 156 }
 157
 158 NTSTATUS
 159 NTAPI
 160 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
 161                                 IN ULONG_PTR BoundaryAddress,
 162                                 IN ULONG_PTR Alignment,
 163                                 IN PMM_AVL_TABLE Table,
 164                                 OUT PULONG_PTR Base)
 165 {
 166     PMMADDRESS_NODE Node, PreviousNode;
 167     ULONG_PTR CandidateAddress, EndAddress;
 168     ULONG AlignEndVpn, CandidateVpn, BoundaryVpn, LowestVpn, StartVpn, EndVpn;
 169     PFN_NUMBER PageCount;
 170
 171     /* Sanity checks */
 172     ASSERT(BoundaryAddress);
 173     ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
 174
 175     /* Compute page length, make sure the boundary address is valid */
 176     Length = PAGE_ROUND_UP(Length);
 177     if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
 178
 179     /* Compute the highest address to start at */
 180     CandidateAddress = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
 181
 182     /* Check if the table is empty */
 183     if (!Table->NumberGenericTableElements)
 184     {
 185         /* Tree is empty, the candidate address is already the best one */
 186         *Base = CandidateAddress;
 187         return STATUS_SUCCESS;
 188     }
 189
 190     /* Starting from the root, go down until the right-most child */
 191     Node = RtlRightChildAvl(&Table->BalancedRoot);
 192     while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
 193
 194     /* Get the aligned ending address of this VPN */
 195     EndAddress = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
 196                           Alignment);
 197
 198     /* Can we fit the address without overflowing into the node? */
 199     if ((EndAddress < BoundaryAddress) &&
 200         ((BoundaryAddress - EndAddress) > Length))
 201     {
 202         /* There is enough space to add our address */
 203         *Base = ROUND_UP(BoundaryAddress - Length, Alignment);
 204         return STATUS_SUCCESS;
 205     }
 206
 207     PageCount = Length >> PAGE_SHIFT;
 208     CandidateVpn = CandidateAddress >> PAGE_SHIFT;
 209     BoundaryVpn = BoundaryAddress >> PAGE_SHIFT;
 210     LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT;
 211
 212     PreviousNode = MiGetPreviousNode(Node);
 213
 214     StartVpn = Node->StartingVpn;
 215     EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
 216     AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
 217
 218     /* Loop until a gap is found */
 219     for (PageCount = Length >> PAGE_SHIFT,
 220          CandidateVpn = CandidateAddress >> PAGE_SHIFT,
 221          BoundaryVpn = BoundaryAddress >> PAGE_SHIFT,
 222          LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT,
 223          PreviousNode = MiGetPreviousNode(Node),
 224          StartVpn = Node->StartingVpn,
 225          EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
 226          AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
 227          PreviousNode;
 228          Node = PreviousNode,
 229          PreviousNode = MiGetPreviousNode(Node),
 230          StartVpn = Node->StartingVpn,
 231          EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
 232          AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT))
 233     {
 234         /* Can we fit the address without overflowing into the node? */
 235         if ((StartVpn < CandidateVpn) && ((StartVpn - AlignEndVpn) >= PageCount))
 236         {
 237             /* Check if we can get our candidate address */
 238             if ((CandidateVpn > EndVpn) && (BoundaryVpn < StartVpn))
 239             {
 240                 /* Use it */
 241                 *Base = CandidateAddress;
 242                 return STATUS_SUCCESS;
 243             }
 244
 245             /* Otherwise, can we fit it by changing the start address? */
 246             if (StartVpn > AlignEndVpn)
 247             {
 248                 /* It'll fit, compute the new base address for that to work */
 249                 *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
 250                 return STATUS_SUCCESS;
 251             }
 252         }
 253
 254         PreviousNode = MiGetPreviousNode(Node);
 255         StartVpn = Node->StartingVpn;
 256         EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
 257         AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
 258     }
 259
 260     /* See if we could squeeze into the last descriptor */
 261     if ((StartVpn > LowestVpn) && ((StartVpn - LowestVpn) >= PageCount))
 262     {
 263         /* Check if we can try our candidate address */
 264         if (BoundaryVpn < StartVpn)
 265         {
 266             /* Use it */
 267             *Base = CandidateAddress;
 268             return STATUS_SUCCESS;
 269         }
 270
 271         /* Otherwise, change the base address to what's needed to fit in */
 272         *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
 273         return STATUS_SUCCESS;
 274     }
 275
 276     /* No address space left at all */
 277     return STATUS_NO_MEMORY;
 278 }
 279
 280 /* EOF */