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