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 #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 PMM_AVL_TABLE Table,
  96              IN PMMADDRESS_NODE NewNode,
  97              IN PMMADDRESS_NODE Parent,
  98              IN TABLE_SEARCH_RESULT Result)
  99 {
 100     PMMVAD Vad;
 101
 102     /* Insert it into the tree */
 103     RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
 104
 105     /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
 106     Vad = (PMMVAD)NewNode;
 107     if (Vad->u.VadFlags.Spare == 0)
 108     {
 109         NTSTATUS Status;
 110         PMEMORY_AREA MemoryArea;
 111         PHYSICAL_ADDRESS BoundaryAddressMultiple;
 112         SIZE_T Size;
 113         PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
 114         PVOID AllocatedBase = (PVOID)(Vad->StartingVpn << PAGE_SHIFT);
 115         BoundaryAddressMultiple.QuadPart = 0;
 116         Size = ((Vad->EndingVpn + 1) - Vad->StartingVpn) << PAGE_SHIFT;
 117         Status = MmCreateMemoryArea(&Process->Vm,
 118                                     MEMORY_AREA_OWNED_BY_ARM3,
 119                                     &AllocatedBase,
 120                                     Size,
 121                                     PAGE_READWRITE,
 122                                     &MemoryArea,
 123                                     TRUE,
 124                                     0,
 125                                     BoundaryAddressMultiple);
 126         ASSERT(NT_SUCCESS(Status));
 127
 128         /* Check if this is VM VAD */
 129         if (Vad->ControlArea == NULL)
 130         {
 131             /* We store the reactos MEMORY_AREA here */
 132             DPRINT("Storing %p in %p\n", MemoryArea, Vad);
 133             Vad->FirstPrototypePte = (PMMPTE)MemoryArea;
 134         }
 135         else
 136         {
 137             /* This is a section VAD. Store the MAREA here for now */
 138             DPRINT("Storing %p in %p\n", MemoryArea, Vad);
 139             Vad->ControlArea->WaitingForDeletion = (PVOID)MemoryArea;
 140         }
 141     }
 142 }
 143
 144 VOID
 145 NTAPI
 146 MiInsertVad(IN PMMVAD Vad,
 147             IN PEPROCESS Process)
 148 {
 149     TABLE_SEARCH_RESULT Result;
 150     PMMADDRESS_NODE Parent = NULL;
 151
 152     /* Validate the VAD and set it as the current hint */
 153     ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
 154     Process->VadRoot.NodeHint = Vad;
 155
 156     /* Find the parent VAD and where this child should be inserted */
 157     Result = RtlpFindAvlTableNodeOrParent(&Process->VadRoot, (PVOID)Vad->StartingVpn, &Parent);
 158     ASSERT(Result != TableFoundNode);
 159     ASSERT((Parent != NULL) || (Result == TableEmptyTree));
 160
 161     /* Do the actual insert operation */
 162     MiInsertNode(&Process->VadRoot, (PVOID)Vad, Parent, Result);
 163 }
 164
 165 VOID
 166 NTAPI
 167 MiRemoveNode(IN PMMADDRESS_NODE Node,
 168              IN PMM_AVL_TABLE Table)
 169 {
 170     PMMVAD Vad;
 171
 172     /* Call the AVL code */
 173     RtlpDeleteAvlTreeNode(Table, Node);
 174
 175     /* Decrease element count */
 176     Table->NumberGenericTableElements--;
 177
 178     /* Check if this node was the hint */
 179     if (Table->NodeHint == Node)
 180     {
 181         /* Get a new hint, unless we're empty now, in which case nothing */
 182         if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
 183         else Table->NodeHint = Table->BalancedRoot.RightChild;
 184     }
 185
 186     /* Free the node from ReactOS view as well */
 187     Vad = (PMMVAD)Node;
 188     if (Vad->u.VadFlags.Spare == 0)
 189     {
 190         PMEMORY_AREA MemoryArea;
 191         PEPROCESS Process;
 192
 193         /* Check if this is VM VAD */
 194         if (Vad->ControlArea == NULL)
 195         {
 196             /* We store the ReactOS MEMORY_AREA here */
 197             MemoryArea = (PMEMORY_AREA)Vad->FirstPrototypePte;
 198         }
 199         else
 200         {
 201             /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
 202             MemoryArea = (PMEMORY_AREA)Vad->ControlArea->WaitingForDeletion;
 203         }
 204
 205         /* Make sure one actually still exists */
 206         if (MemoryArea)
 207         {
 208             /* Get the process */
 209             Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
 210
 211             /* We only create fake memory-areas for ARM3 VADs */
 212             ASSERT(MemoryArea->Type == MEMORY_AREA_OWNED_BY_ARM3);
 213             ASSERT(MemoryArea->Vad == NULL);
 214
 215             /* Free it */
 216             MmFreeMemoryArea(&Process->Vm, MemoryArea, NULL, NULL);
 217         }
 218     }
 219 }
 220
 221 PMMADDRESS_NODE
 222 NTAPI
 223 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
 224 {
 225     PMMADDRESS_NODE Parent;
 226
 227     /* Get the left child */
 228     if (RtlLeftChildAvl(Node))
 229     {
 230         /* Get right-most child */
 231         Node = RtlLeftChildAvl(Node);
 232         while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
 233         return Node;
 234     }
 235
 236     Parent = RtlParentAvl(Node);
 237     ASSERT(Parent != NULL);
 238     while (Parent != Node)
 239     {
 240         /* The parent should be a right child, return the real predecessor */
 241         if (RtlIsRightChildAvl(Node))
 242         {
 243             /* Return it unless it's the root */
 244             if (Parent == RtlParentAvl(Parent)) Parent = NULL;
 245             return Parent;
 246         }
 247
 248         /* Keep lopping until we find our parent */
 249         Node = Parent;
 250         Parent = RtlParentAvl(Node);
 251     }
 252
 253     /* Nothing found */
 254     return NULL;
 255 }
 256
 257 PMMADDRESS_NODE
 258 NTAPI
 259 MiGetNextNode(IN PMMADDRESS_NODE Node)
 260 {
 261     PMMADDRESS_NODE Parent;
 262
 263     /* Get the right child */
 264     if (RtlRightChildAvl(Node))
 265     {
 266         /* Get left-most child */
 267         Node = RtlRightChildAvl(Node);
 268         while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
 269         return Node;
 270     }
 271
 272     Parent = RtlParentAvl(Node);
 273     ASSERT(Parent != NULL);
 274     while (Parent != Node)
 275     {
 276         /* The parent should be a left child, return the real predecessor */
 277         if (RtlIsLeftChildAvl(Node))
 278         {
 279             /* Return it */
 280             return Parent;
 281         }
 282
 283         /* Keep lopping until we find our parent */
 284         Node = Parent;
 285         Parent = RtlParentAvl(Node);
 286     }
 287
 288     /* Nothing found */
 289     return NULL;
 290 }
 291
 292 NTSTATUS
 293 NTAPI
 294 MiFindEmptyAddressRangeInTree(IN SIZE_T Length,
 295                               IN ULONG_PTR Alignment,
 296                               IN PMM_AVL_TABLE Table,
 297                               OUT PMMADDRESS_NODE *PreviousVad,
 298                               OUT PULONG_PTR Base)
 299 {
 300     PMMADDRESS_NODE Node;
 301     PMMADDRESS_NODE NextNode;
 302     ULONG_PTR StartingVpn, HighestVpn, AlignmentVpn, LengthVpn, LowVpn;
 303     ASSERT(Length != 0);
 304
 305     /* Precompute page numbers for the length, alignment, and starting address */
 306     LengthVpn = (Length + (PAGE_SIZE - 1)) >> PAGE_SHIFT;
 307     AlignmentVpn = Alignment >> PAGE_SHIFT;
 308     StartingVpn = ROUND_UP((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT,
 309                            AlignmentVpn);
 310
 311     /* Check if the table is free, so the lowest possible address is available */
 312     if (!Table->NumberGenericTableElements) goto FoundAtBottom;
 313
 314     /* Otherwise, follow the leftmost child of the right root node's child */
 315     Node = RtlRightChildAvl(&Table->BalancedRoot);
 316     while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
 317
 318     /* This is the node for the remaining gap at the bottom, can it be used? */
 319     if ((Node->StartingVpn > StartingVpn) &&
 320         (LengthVpn < Node->StartingVpn - StartingVpn))
 321     {
 322 FoundAtBottom:
 323         /* Use this VAD to store the allocation */
 324         *PreviousVad = NULL;
 325         *Base = StartingVpn << PAGE_SHIFT;
 326         return STATUS_SUCCESS;
 327     }
 328
 329     /* Otherwise, we start a search to find a gap */
 330     while (TRUE)
 331     {
 332         /* The last aligned page number in this entry */
 333         LowVpn = ROUND_UP(Node->EndingVpn + 1, AlignmentVpn);
 334
 335         /* Keep going as long as there's still a next node */
 336         NextNode = MiGetNextNode(Node);
 337         if (!NextNode) break;
 338
 339         /* Can this allocation fit in this node? */
 340         if ((LengthVpn <= (NextNode->StartingVpn - LowVpn)) &&
 341             (NextNode->StartingVpn > LowVpn))
 342         {
 343 Found:
 344             /* Yes! Use this VAD to store the allocation */
 345             *PreviousVad = Node;
 346             *Base = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
 347                              Alignment);
 348             return STATUS_SUCCESS;
 349         }
 350
 351         /* Try the next node */
 352         Node = NextNode;
 353     }
 354
 355     /* We're down to the last (top) VAD, will this allocation fit inside it? */
 356     HighestVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) >> PAGE_SHIFT;
 357     if ((HighestVpn > LowVpn) && (LengthVpn <= HighestVpn - LowVpn)) goto Found;
 358
 359     /* Nyet, there's no free address space for this allocation, so we'll fail */
 360     return STATUS_NO_MEMORY;
 361 }
 362
 363 TABLE_SEARCH_RESULT
 364 NTAPI
 365 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
 366                                 IN ULONG_PTR BoundaryAddress,
 367                                 IN ULONG_PTR Alignment,
 368                                 IN PMM_AVL_TABLE Table,
 369                                 OUT PULONG_PTR Base,
 370                                 OUT PMMADDRESS_NODE *Parent)
 371 {
 372     PMMADDRESS_NODE Node, LowestNode, Child;
 373     ULONG_PTR LowVpn, HighVpn;
 374     PFN_NUMBER PageCount;
 375
 376     /* Sanity checks */
 377     ASSERT(BoundaryAddress);
 378     ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
 379
 380     /* Compute page length, make sure the boundary address is valid */
 381     Length = ROUND_TO_PAGES(Length);
 382     PageCount = Length >> PAGE_SHIFT;
 383     if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
 384
 385     /* Check if the table is empty */
 386     if (Table->NumberGenericTableElements == 0)
 387     {
 388         /* Tree is empty, the candidate address is already the best one */
 389         *Base = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
 390         return TableEmptyTree;
 391     }
 392
 393     /* Calculate the initial upper margin */
 394     HighVpn = BoundaryAddress >> PAGE_SHIFT;
 395
 396     /* Starting from the root, go down until the right-most child
 397      * which is just behind the boundary*/
 398     LowestNode = Node = RtlRightChildAvl(&Table->BalancedRoot);
 399     while (((Child = RtlRightChildAvl(Node)) != 0 )
 400             && (Node->EndingVpn < HighVpn )) Node = Child;
 401
 402     /* Now loop the Vad nodes */
 403     while (Node)
 404     {
 405         /* Keep track of the lowest node */
 406         LowestNode = Node;
 407
 408         /* Calculate the lower margin */
 409         LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment >> PAGE_SHIFT);
 410
 411         /* Check if the current bounds are suitable */
 412         if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
 413         {
 414             /* There is enough space to add our node */
 415             LowVpn = HighVpn - PageCount;
 416             *Base = LowVpn << PAGE_SHIFT;
 417
 418             /* Can we use the current node as parent? */
 419             Child = RtlRightChildAvl(Node);
 420             if (!Child)
 421             {
 422                 /* Node has no right child, so use it as parent */
 423                 *Parent = Node;
 424                 return TableInsertAsRight;
 425             }
 426             else
 427             {
 428                 /* Node has a right child, find most left grand child */
 429                 Node = Child;
 430                 while ((Child = RtlLeftChildAvl(Node))) Node = Child;
 431                 *Parent = Node;
 432                 return TableInsertAsLeft;
 433             }
 434         }
 435
 436         /* Update the upper margin if neccessary */
 437         if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
 438
 439         /* Go to the next lower node */
 440         Node = MiGetPreviousNode(Node);
 441     }
 442
 443     /* Check if there's enough space before the lowest Vad */
 444     LowVpn = ROUND_UP((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) >> PAGE_SHIFT;
 445     if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
 446     {
 447         /* There is enough space to add our address */
 448         LowVpn = HighVpn - PageCount;
 449         *Base = LowVpn << PAGE_SHIFT;
 450         *Parent = LowestNode;
 451         return TableInsertAsLeft;
 452     }
 453
 454     /* No address space left at all */
 455     *Base = 0;
 456     *Parent = NULL;
 457     return TableFoundNode;
 458 }
 459
 460 /* EOF */