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