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 PMMADDRESS_NODE
 111 NTAPI
 112 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
 113 {
 114     PMMADDRESS_NODE Parent;
 115
 116     /* Get the left child */
 117     if (RtlLeftChildAvl(Node))
 118     {
 119         /* Get right-most child */
 120         Node = RtlLeftChildAvl(Node);
 121         while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
 122         return Node;
 123     }
 124
 125     Parent = RtlParentAvl(Node);
 126     ASSERT(Parent != NULL);
 127     while (Parent != Node)
 128     {
 129         /* The parent should be a right child, return the real predecessor */
 130         if (RtlIsRightChildAvl(Node))
 131         {
 132             /* Return it unless it's the root */
 133             if (Parent == RtlParentAvl(Parent)) Parent = NULL;
 134             return Parent;
 135         }
 136
 137         /* Keep lopping until we find our parent */
 138         Node = Parent;
 139         Parent = RtlParentAvl(Node);
 140     }
 141
 142     /* Nothing found */
 143     return NULL;
 144 }
 145
 146 NTSTATUS
 147 NTAPI
 148 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
 149                                 IN ULONG_PTR BoundaryAddress,
 150                                 IN ULONG_PTR Alignment,
 151                                 IN PMM_AVL_TABLE Table,
 152                                 OUT PULONG_PTR Base)
 153 {
 154     PMMADDRESS_NODE Node, PreviousNode;
 155     ULONG_PTR CandidateAddress, EndAddress;
 156     ULONG AlignEndVpn, CandidateVpn, BoundaryVpn, LowestVpn, StartVpn, EndVpn;
 157     PFN_NUMBER PageCount;
 158
 159     /* Sanity checks */
 160     ASSERT(BoundaryAddress);
 161     ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
 162
 163     /* Compute page length, make sure the boundary address is valid */
 164     Length = PAGE_ROUND_UP(Length);
 165     if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
 166
 167     /* Compute the highest address to start at */
 168     CandidateAddress = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
 169
 170     /* Check if the table is empty */
 171     if (!Table->NumberGenericTableElements)
 172     {
 173         /* Tree is empty, the candidate address is already the best one */
 174         *Base = CandidateAddress;
 175         return STATUS_SUCCESS;
 176     }
 177
 178     /* Starting from the root, go down until the right-most child */
 179     Node = RtlRightChildAvl(&Table->BalancedRoot);
 180     while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
 181
 182     /* Get the aligned ending address of this VPN */
 183     EndAddress = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
 184                           Alignment);
 185
 186     /* Can we fit the address without overflowing into the node? */
 187     if ((EndAddress < BoundaryAddress) &&
 188         ((BoundaryAddress - EndAddress) > Length))
 189     {
 190         /* There is enough space to add our address */
 191         *Base = ROUND_UP(BoundaryAddress - Length, Alignment);
 192         return STATUS_SUCCESS;
 193     }
 194
 195     PageCount = Length >> PAGE_SHIFT;
 196     CandidateVpn = CandidateAddress >> PAGE_SHIFT;
 197     BoundaryVpn = BoundaryAddress >> PAGE_SHIFT;
 198     LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT;
 199
 200     PreviousNode = MiGetPreviousNode(Node);
 201
 202     StartVpn = Node->StartingVpn;
 203     EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
 204     AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
 205
 206     /* Loop until a gap is found */
 207     for (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          PreviousNode = MiGetPreviousNode(Node),
 212          StartVpn = Node->StartingVpn,
 213          EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
 214          AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
 215          PreviousNode;
 216          Node = PreviousNode,
 217          PreviousNode = MiGetPreviousNode(Node),
 218          StartVpn = Node->StartingVpn,
 219          EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
 220          AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT))
 221     {
 222         /* Can we fit the address without overflowing into the node? */
 223         if ((StartVpn < CandidateVpn) && ((StartVpn - AlignEndVpn) >= PageCount))
 224         {
 225             /* Check if we can get our candidate address */
 226             if ((CandidateVpn > EndVpn) && (BoundaryVpn < StartVpn))
 227             {
 228                 /* Use it */
 229                 *Base = CandidateAddress;
 230                 return STATUS_SUCCESS;
 231             }
 232
 233             /* Otherwise, can we fit it by changing the start address? */
 234             if (StartVpn > AlignEndVpn)
 235             {
 236                 /* It'll fit, compute the new base address for that to work */
 237                 *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
 238                 return STATUS_SUCCESS;
 239             }
 240         }
 241
 242         PreviousNode = MiGetPreviousNode(Node);
 243         StartVpn = Node->StartingVpn;
 244         EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
 245         AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
 246     }
 247
 248     /* See if we could squeeze into the last descriptor */
 249     if ((StartVpn > LowestVpn) && ((StartVpn - LowestVpn) >= PageCount))
 250     {
 251         /* Check if we can try our candidate address */
 252         if (BoundaryVpn < StartVpn)
 253         {
 254             /* Use it */
 255             *Base = CandidateAddress;
 256             return STATUS_SUCCESS;
 257         }
 258
 259         /* Otherwise, change the base address to what's needed to fit in */
 260         *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
 261         return STATUS_SUCCESS;
 262     }
 263
 264     /* No address space left at all */
 265     return STATUS_NO_MEMORY;
 266 }
 267
 268 /* EOF */