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 <mm/ARM3/miarm.h>
  18
  19 /* Include Mm version of AVL support */
  20 #include "miavl.h"
  21 #include <lib/rtl/avlsupp.c>
  22
  23 /* GLOBALS ********************************************************************/
  24
  25 CHAR MmReadWrite[32] =
  26 {
  27     MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED,
  28     MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
  29     MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
  30
  31     MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED,
  32     MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
  33     MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
  34
  35     MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED,
  36     MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
  37     MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
  38
  39     MM_NO_ACCESS_ALLOWED, MM_READ_ONLY_ALLOWED, MM_READ_ONLY_ALLOWED,
  40     MM_READ_ONLY_ALLOWED, MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
  41     MM_READ_WRITE_ALLOWED, MM_READ_WRITE_ALLOWED,
  42 };
  43
  44 /* FUNCTIONS ******************************************************************/
  45
  46 PMMVAD
  47 NTAPI
  48 MiLocateAddress(IN PVOID VirtualAddress)
  49 {
  50     PMMVAD FoundVad;
  51     ULONG_PTR Vpn;
  52     PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
  53     TABLE_SEARCH_RESULT SearchResult;
  54
  55     /* Start with the the hint */
  56     FoundVad = (PMMVAD)Table->NodeHint;
  57     if (!FoundVad) return NULL;
  58
  59     /* Check if this VPN is in the hint, if so, use it */
  60     Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
  61     if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
  62
  63     /* VAD hint didn't work, go look for it */
  64     SearchResult = RtlpFindAvlTableNodeOrParent(Table,
  65                                                 (PVOID)Vpn,
  66                                                 (PMMADDRESS_NODE*)&FoundVad);
  67     if (SearchResult != TableFoundNode) return NULL;
  68
  69     /* We found it, update the hint */
  70     ASSERT(FoundVad != NULL);
  71     ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
  72     Table->NodeHint = FoundVad;
  73     return FoundVad;
  74 }
  75
  76 TABLE_SEARCH_RESULT
  77 NTAPI
  78 MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
  79                           IN ULONG_PTR EndVpn,
  80                           IN PMM_AVL_TABLE Table,
  81                           OUT PMMADDRESS_NODE *NodeOrParent)
  82 {
  83     PMMADDRESS_NODE ParentNode, CurrentNode;
  84
  85     /* If the tree is empty, there is no conflict */
  86     if (Table->NumberGenericTableElements == 0) return TableEmptyTree;
  87
  88     /* Start looping from the root node */
  89     CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
  90     ASSERT(CurrentNode != NULL);
  91     while (CurrentNode)
  92     {
  93         ParentNode = CurrentNode;
  94
  95         /* This address comes after */
  96         if (StartVpn > CurrentNode->EndingVpn)
  97         {
  98             /* Keep searching on the right */
  99             CurrentNode = RtlRightChildAvl(CurrentNode);
 100         }
 101         else if (EndVpn < CurrentNode->StartingVpn)
 102         {
 103             /* This address ends before the node starts, search on the left */
 104             CurrentNode = RtlLeftChildAvl(CurrentNode);
 105         }
 106         else
 107         {
 108             /* This address is part of this node, return it */
 109             *NodeOrParent = ParentNode;
 110             return TableFoundNode;
 111         }
 112     }
 113
 114     /* There is no more child, save the current node as parent */
 115     *NodeOrParent = ParentNode;
 116     if (StartVpn > ParentNode->EndingVpn)
 117     {
 118         return TableInsertAsRight;
 119     }
 120     else
 121     {
 122         return TableInsertAsLeft;
 123     }
 124 }
 125
 126 VOID
 127 NTAPI
 128 MiInsertNode(IN PMM_AVL_TABLE Table,
 129              IN PMMADDRESS_NODE NewNode,
 130              IN PMMADDRESS_NODE Parent,
 131              IN TABLE_SEARCH_RESULT Result)
 132 {
 133     PMMVAD_LONG Vad;
 134
 135     /* Insert it into the tree */
 136     RtlpInsertAvlTreeNode(Table, NewNode, Parent, Result);
 137
 138     /* Now insert an ARM3 MEMORY_AREA for this node, unless the insert was already from the MEMORY_AREA code */
 139     Vad = (PMMVAD_LONG)NewNode;
 140     if (Vad->u.VadFlags.Spare == 0)
 141     {
 142         NTSTATUS Status;
 143         PMEMORY_AREA MemoryArea;
 144         SIZE_T Size;
 145         PEPROCESS Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
 146         PVOID AllocatedBase = (PVOID)(Vad->StartingVpn << PAGE_SHIFT);
 147
 148         Size = ((Vad->EndingVpn + 1) - Vad->StartingVpn) << PAGE_SHIFT;
 149         Status = MmCreateMemoryArea(&Process->Vm,
 150                                     MEMORY_AREA_OWNED_BY_ARM3,
 151                                     &AllocatedBase,
 152                                     Size,
 153                                     PAGE_READWRITE,
 154                                     &MemoryArea,
 155                                     TRUE,
 156                                     0,
 157                                     PAGE_SIZE);
 158         ASSERT(NT_SUCCESS(Status));
 159
 160         /* Check if this is VM VAD */
 161         if (Vad->ControlArea == NULL)
 162         {
 163             /* We store the reactos MEMORY_AREA here */
 164             Vad->FirstPrototypePte = (PMMPTE)MemoryArea;
 165         }
 166         else
 167         {
 168             /* This is a section VAD. Store the MAREA here for now */
 169             ASSERT(Vad->u4.Banked == (PVOID)0xDEADBABE);
 170             Vad->u4.Banked = (PVOID)MemoryArea;
 171         }
 172     }
 173 }
 174
 175 VOID
 176 NTAPI
 177 MiInsertVad(IN PMMVAD Vad,
 178             IN PEPROCESS Process)
 179 {
 180     TABLE_SEARCH_RESULT Result;
 181     PMMADDRESS_NODE Parent = NULL;
 182
 183     /* Validate the VAD and set it as the current hint */
 184     ASSERT(Vad->EndingVpn >= Vad->StartingVpn);
 185     Process->VadRoot.NodeHint = Vad;
 186
 187     /* Find the parent VAD and where this child should be inserted */
 188     Result = RtlpFindAvlTableNodeOrParent(&Process->VadRoot, (PVOID)Vad->StartingVpn, &Parent);
 189     ASSERT(Result != TableFoundNode);
 190     ASSERT((Parent != NULL) || (Result == TableEmptyTree));
 191
 192     /* Do the actual insert operation */
 193     MiLockProcessWorkingSetUnsafe(PsGetCurrentProcess(), PsGetCurrentThread());
 194     MiInsertNode(&Process->VadRoot, (PVOID)Vad, Parent, Result);
 195     MiUnlockProcessWorkingSetUnsafe(PsGetCurrentProcess(), PsGetCurrentThread());
 196 }
 197
 198 NTSTATUS
 199 NTAPI
 200 MiInsertVadEx(
 201     _Inout_ PMMVAD Vad,
 202     _In_ ULONG_PTR *BaseAddress,
 203     _In_ SIZE_T ViewSize,
 204     _In_ ULONG_PTR HighestAddress,
 205     _In_ ULONG_PTR Alignment,
 206     _In_ ULONG AllocationType)
 207 {
 208     ULONG_PTR StartingAddress, EndingAddress;
 209     PEPROCESS CurrentProcess;
 210     PETHREAD CurrentThread;
 211     TABLE_SEARCH_RESULT Result;
 212     PMMADDRESS_NODE Parent;
 213
 214     /* Align the view size to pages */
 215     ViewSize = ALIGN_UP_BY(ViewSize, PAGE_SIZE);
 216
 217     /* Get the current process */
 218     CurrentProcess = PsGetCurrentProcess();
 219
 220     /* Acquire the address creation lock and make sure the process is alive */
 221     KeAcquireGuardedMutex(&CurrentProcess->AddressCreationLock);
 222     if (CurrentProcess->VmDeleted)
 223     {
 224         KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
 225         DPRINT1("The process is dying\n");
 226         return STATUS_PROCESS_IS_TERMINATING;
 227     }
 228
 229     /* Did the caller specify an address? */
 230     if (*BaseAddress == 0)
 231     {
 232         /* Make sure HighestAddress is not too large */
 233         HighestAddress = min(HighestAddress, (ULONG_PTR)MM_HIGHEST_VAD_ADDRESS);
 234
 235         /* Which way should we search? */
 236         if ((AllocationType & MEM_TOP_DOWN) || CurrentProcess->VmTopDown)
 237         {
 238             /* Find an address top-down */
 239             Result = MiFindEmptyAddressRangeDownTree(ViewSize,
 240                                                      HighestAddress,
 241                                                      Alignment,
 242                                                      &CurrentProcess->VadRoot,
 243                                                      &StartingAddress,
 244                                                      &Parent);
 245         }
 246         else
 247         {
 248             /* Find an address bottom-up */
 249             Result = MiFindEmptyAddressRangeInTree(ViewSize,
 250                                                    Alignment,
 251                                                    &CurrentProcess->VadRoot,
 252                                                    &Parent,
 253                                                    &StartingAddress);
 254         }
 255
 256         /* Get the ending address, which is the last piece we need for the VAD */
 257         EndingAddress = StartingAddress + ViewSize - 1;
 258
 259         /* Check if we found a suitable location */
 260         if ((Result == TableFoundNode) || (EndingAddress > HighestAddress))
 261         {
 262             DPRINT1("Not enough free space to insert this VAD node!\n");
 263             KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
 264             return STATUS_NO_MEMORY;
 265         }
 266
 267         ASSERT(StartingAddress != 0);
 268         ASSERT(StartingAddress < (ULONG_PTR)HighestAddress);
 269         ASSERT(EndingAddress > StartingAddress);
 270     }
 271     else
 272     {
 273         /* Calculate the starting and ending address */
 274         StartingAddress = ALIGN_DOWN_BY(*BaseAddress, Alignment);
 275         EndingAddress = StartingAddress + ViewSize - 1;
 276
 277         /* Make sure it doesn't conflict with an existing allocation */
 278         Result = MiCheckForConflictingNode(StartingAddress >> PAGE_SHIFT,
 279                                            EndingAddress >> PAGE_SHIFT,
 280                                            &CurrentProcess->VadRoot,
 281                                            &Parent);
 282         if (Result == TableFoundNode)
 283         {
 284             DPRINT1("Given address conflicts with existing node\n");
 285             KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
 286             return STATUS_CONFLICTING_ADDRESSES;
 287         }
 288     }
 289
 290     /* Now set the VAD address */
 291     Vad->StartingVpn = StartingAddress >> PAGE_SHIFT;
 292     Vad->EndingVpn = EndingAddress >> PAGE_SHIFT;
 293
 294     /* Check if we already need to charge for the pages */
 295     if ((Vad->u.VadFlags.PrivateMemory && Vad->u.VadFlags.MemCommit) ||
 296         (!Vad->u.VadFlags.PrivateMemory &&
 297          (Vad->u.VadFlags.Protection & PAGE_WRITECOPY)))
 298     {
 299         /* Set the commit charge */
 300         Vad->u.VadFlags.CommitCharge = ViewSize / PAGE_SIZE;
 301     }
 302
 303     /* Check if the VAD is to be secured */
 304     if (Vad->u2.VadFlags2.OneSecured)
 305     {
 306         /* This *must* be a long VAD! */
 307         ASSERT(Vad->u2.VadFlags2.LongVad);
 308
 309         /* Yeah this is retarded, I didn't invent it! */
 310         ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn = StartingAddress;
 311         ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn = EndingAddress;
 312     }
 313
 314     /* Lock the working set */
 315     CurrentThread = PsGetCurrentThread();
 316     MiLockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
 317
 318     /* Insert the VAD */
 319     CurrentProcess->VadRoot.NodeHint = Vad;
 320     MiInsertNode(&CurrentProcess->VadRoot, (PVOID)Vad, Parent, Result);
 321
 322     /* Release the working set */
 323     MiUnlockProcessWorkingSetUnsafe(CurrentProcess, CurrentThread);
 324
 325     /* Update the process' virtual size, and peak virtual size */
 326     CurrentProcess->VirtualSize += ViewSize;
 327     if (CurrentProcess->VirtualSize > CurrentProcess->PeakVirtualSize)
 328     {
 329         CurrentProcess->PeakVirtualSize = CurrentProcess->VirtualSize;
 330     }
 331
 332     /* Unlock the address space */
 333     KeReleaseGuardedMutex(&CurrentProcess->AddressCreationLock);
 334
 335     *BaseAddress = StartingAddress;
 336     return STATUS_SUCCESS;
 337 }
 338
 339 VOID
 340 NTAPI
 341 MiInsertBasedSection(IN PSECTION Section)
 342 {
 343     TABLE_SEARCH_RESULT Result;
 344     PMMADDRESS_NODE Parent = NULL;
 345     ASSERT(Section->Address.EndingVpn >= Section->Address.StartingVpn);
 346
 347     /* Find the parent VAD and where this child should be inserted */
 348     Result = RtlpFindAvlTableNodeOrParent(&MmSectionBasedRoot, (PVOID)Section->Address.StartingVpn, &Parent);
 349     ASSERT(Result != TableFoundNode);
 350     ASSERT((Parent != NULL) || (Result == TableEmptyTree));
 351     MiInsertNode(&MmSectionBasedRoot, &Section->Address, Parent, Result);
 352 }
 353
 354 VOID
 355 NTAPI
 356 MiRemoveNode(IN PMMADDRESS_NODE Node,
 357              IN PMM_AVL_TABLE Table)
 358 {
 359     PMMVAD_LONG Vad;
 360
 361     /* Call the AVL code */
 362     RtlpDeleteAvlTreeNode(Table, Node);
 363
 364     /* Decrease element count */
 365     Table->NumberGenericTableElements--;
 366
 367     /* Check if this node was the hint */
 368     if (Table->NodeHint == Node)
 369     {
 370         /* Get a new hint, unless we're empty now, in which case nothing */
 371         if (!Table->NumberGenericTableElements) Table->NodeHint = NULL;
 372         else Table->NodeHint = Table->BalancedRoot.RightChild;
 373     }
 374
 375     /* Free the node from ReactOS view as well */
 376     Vad = (PMMVAD_LONG)Node;
 377     if (Vad->u.VadFlags.Spare == 0)
 378     {
 379         PMEMORY_AREA MemoryArea;
 380         PEPROCESS Process;
 381
 382         /* Check if this is VM VAD */
 383         if (Vad->ControlArea == NULL)
 384         {
 385             /* We store the ReactOS MEMORY_AREA here */
 386             MemoryArea = (PMEMORY_AREA)Vad->FirstPrototypePte;
 387         }
 388         else
 389         {
 390             /* This is a section VAD. We store the ReactOS MEMORY_AREA here */
 391             MemoryArea = (PMEMORY_AREA)Vad->u4.Banked;
 392         }
 393
 394         /* Make sure one actually still exists */
 395         if (MemoryArea)
 396         {
 397             /* Make sure we have not already freed it */
 398             ASSERT(MemoryArea != (PVOID)0xDEADBAB1);
 399
 400             /* Get the process */
 401             Process = CONTAINING_RECORD(Table, EPROCESS, VadRoot);
 402
 403             /* We only create fake memory-areas for ARM3 VADs */
 404             ASSERT(MemoryArea->Type == MEMORY_AREA_OWNED_BY_ARM3);
 405             ASSERT(MemoryArea->Vad == NULL);
 406
 407             /* Free it */
 408             MmFreeMemoryArea(&Process->Vm, MemoryArea, NULL, NULL);
 409
 410             /* Check if this is VM VAD */
 411             if (Vad->ControlArea == NULL)
 412             {
 413                 /* Delete the pointer to it */
 414                 Vad->FirstPrototypePte = (PVOID)0xDEADBAB1;
 415             }
 416             else
 417             {
 418                 /* Delete the pointer to it */
 419                 Vad->u4.Banked = (PVOID)0xDEADBAB1;
 420             }
 421         }
 422     }
 423 }
 424
 425 PMMADDRESS_NODE
 426 NTAPI
 427 MiGetPreviousNode(IN PMMADDRESS_NODE Node)
 428 {
 429     PMMADDRESS_NODE Parent;
 430
 431     /* Get the left child */
 432     if (RtlLeftChildAvl(Node))
 433     {
 434         /* Get right-most child */
 435         Node = RtlLeftChildAvl(Node);
 436         while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
 437         return Node;
 438     }
 439
 440     Parent = RtlParentAvl(Node);
 441     ASSERT(Parent != NULL);
 442     while (Parent != Node)
 443     {
 444         /* The parent should be a right child, return the real predecessor */
 445         if (RtlIsRightChildAvl(Node))
 446         {
 447             /* Return it unless it's the root */
 448             if (Parent == RtlParentAvl(Parent)) Parent = NULL;
 449             return Parent;
 450         }
 451
 452         /* Keep lopping until we find our parent */
 453         Node = Parent;
 454         Parent = RtlParentAvl(Node);
 455     }
 456
 457     /* Nothing found */
 458     return NULL;
 459 }
 460
 461 PMMADDRESS_NODE
 462 NTAPI
 463 MiGetNextNode(IN PMMADDRESS_NODE Node)
 464 {
 465     PMMADDRESS_NODE Parent;
 466
 467     /* Get the right child */
 468     if (RtlRightChildAvl(Node))
 469     {
 470         /* Get left-most child */
 471         Node = RtlRightChildAvl(Node);
 472         while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
 473         return Node;
 474     }
 475
 476     Parent = RtlParentAvl(Node);
 477     ASSERT(Parent != NULL);
 478     while (Parent != Node)
 479     {
 480         /* The parent should be a left child, return the real predecessor */
 481         if (RtlIsLeftChildAvl(Node))
 482         {
 483             /* Return it */
 484             return Parent;
 485         }
 486
 487         /* Keep lopping until we find our parent */
 488         Node = Parent;
 489         Parent = RtlParentAvl(Node);
 490     }
 491
 492     /* Nothing found */
 493     return NULL;
 494 }
 495
 496 TABLE_SEARCH_RESULT
 497 NTAPI
 498 MiFindEmptyAddressRangeInTree(IN SIZE_T Length,
 499                               IN ULONG_PTR Alignment,
 500                               IN PMM_AVL_TABLE Table,
 501                               OUT PMMADDRESS_NODE *PreviousVad,
 502                               OUT PULONG_PTR Base)
 503 {
 504     PMMADDRESS_NODE Node, PreviousNode;
 505     ULONG_PTR PageCount, AlignmentVpn, LowVpn, HighVpn;
 506     ASSERT(Length != 0);
 507
 508     /* Calculate page numbers for the length, alignment, and starting address */
 509     PageCount = BYTES_TO_PAGES(Length);
 510     AlignmentVpn = Alignment >> PAGE_SHIFT;
 511     LowVpn = ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS >> PAGE_SHIFT, AlignmentVpn);
 512
 513     /* Check if the table is empty */
 514     if (Table->NumberGenericTableElements == 0)
 515     {
 516         /* Tree is empty, the candidate address is already the best one */
 517         *Base = LowVpn << PAGE_SHIFT;
 518         return TableEmptyTree;
 519     }
 520
 521     /* Otherwise, follow the leftmost child of the right root node's child */
 522     Node = RtlRightChildAvl(&Table->BalancedRoot);
 523     while (RtlLeftChildAvl(Node)) Node = RtlLeftChildAvl(Node);
 524
 525     /* Start a search to find a gap */
 526     PreviousNode = NULL;
 527     while (Node != NULL)
 528     {
 529         /* Check if the gap below the current node is suitable */
 530         if (Node->StartingVpn >= LowVpn + PageCount)
 531         {
 532             /* There is enough space to add our node */
 533             *Base = LowVpn << PAGE_SHIFT;
 534
 535             /* Can we use the current node as parent? */
 536             if (RtlLeftChildAvl(Node) == NULL)
 537             {
 538                 /* Node has no left child, so use it as parent */
 539                 *PreviousVad = Node;
 540                 return TableInsertAsLeft;
 541             }
 542             else
 543             {
 544                 /* Node has a left child, this means that the previous node is
 545                    the right-most child of it's left child and can be used as
 546                    the parent. In case we use the space before the left-most
 547                    node, it's left child must be NULL. */
 548                 ASSERT(PreviousNode != NULL);
 549                 ASSERT(RtlRightChildAvl(PreviousNode) == NULL);
 550                 *PreviousVad = PreviousNode;
 551                 return TableInsertAsRight;
 552             }
 553         }
 554
 555         /* The next candidate is above the current node */
 556         if (Node->EndingVpn >= LowVpn)
 557             LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
 558
 559         /* Remember the current node and go to the next node */
 560         PreviousNode = Node;
 561         Node = MiGetNextNode(Node);
 562     }
 563
 564     /* We're up to the highest VAD, will this allocation fit above it? */
 565     HighVpn = ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1) / PAGE_SIZE;
 566     if (HighVpn >= LowVpn + PageCount)
 567     {
 568         /* Yes! Use this VAD to store the allocation */
 569         *PreviousVad = PreviousNode;
 570         *Base = LowVpn << PAGE_SHIFT;
 571         return TableInsertAsRight;
 572     }
 573
 574     /* Nyet, there's no free address space for this allocation, so we'll fail */
 575     return TableFoundNode;
 576 }
 577
 578 TABLE_SEARCH_RESULT
 579 NTAPI
 580 MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
 581                                 IN ULONG_PTR BoundaryAddress,
 582                                 IN ULONG_PTR Alignment,
 583                                 IN PMM_AVL_TABLE Table,
 584                                 OUT PULONG_PTR Base,
 585                                 OUT PMMADDRESS_NODE *Parent)
 586 {
 587     PMMADDRESS_NODE Node, OldNode, Child;
 588     ULONG_PTR LowVpn, HighVpn, AlignmentVpn;
 589     PFN_NUMBER PageCount;
 590
 591     /* Sanity checks */
 592     ASSERT(BoundaryAddress);
 593     ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS));
 594     ASSERT((Alignment & (PAGE_SIZE - 1)) == 0);
 595
 596     /* Calculate page numbers for the length and alignment */
 597     Length = ROUND_TO_PAGES(Length);
 598     PageCount = Length >> PAGE_SHIFT;
 599     AlignmentVpn = Alignment / PAGE_SIZE;
 600
 601     /* Check if there is enough space below the boundary */
 602     if ((ALIGN_UP_BY((ULONG_PTR)MM_LOWEST_USER_ADDRESS, Alignment) + Length) >
 603         (BoundaryAddress + 1))
 604     {
 605         return TableFoundNode;
 606     }
 607
 608     /* Check if the table is empty */
 609     if (Table->NumberGenericTableElements == 0)
 610     {
 611         /* Tree is empty, the candidate address is already the best one */
 612         *Base = ALIGN_DOWN_BY(BoundaryAddress + 1 - Length, Alignment);
 613         return TableEmptyTree;
 614     }
 615
 616     /* Calculate the initial upper margin */
 617     HighVpn = (BoundaryAddress + 1) >> PAGE_SHIFT;
 618
 619     /* Starting from the root, follow the right children until we found a node
 620        that ends above the boundary */
 621     Node = RtlRightChildAvl(&Table->BalancedRoot);
 622     while ((Node->EndingVpn < HighVpn) &&
 623            ((Child = RtlRightChildAvl(Node)) != NULL)) Node = Child;
 624
 625     /* Now loop the Vad nodes */
 626     while (Node)
 627     {
 628         /* Calculate the lower margin */
 629         LowVpn = ALIGN_UP_BY(Node->EndingVpn + 1, AlignmentVpn);
 630
 631         /* Check if the current bounds are suitable */
 632         if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
 633         {
 634             /* There is enough space to add our node */
 635             LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, AlignmentVpn);
 636             *Base = LowVpn << PAGE_SHIFT;
 637
 638             /* Can we use the current node as parent? */
 639             if (!RtlRightChildAvl(Node))
 640             {
 641                 /* Node has no right child, so use it as parent */
 642                 *Parent = Node;
 643                 return TableInsertAsRight;
 644             }
 645             else
 646             {
 647                 /* Node has a right child, the node we had before is the most
 648                    left grandchild of that right child, use it as parent. */
 649                 *Parent = OldNode;
 650                 return TableInsertAsLeft;
 651             }
 652         }
 653
 654         /* Update the upper margin if necessary */
 655         if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn;
 656
 657         /* Remember the current node and go to the previous node */
 658         OldNode = Node;
 659         Node = MiGetPreviousNode(Node);
 660     }
 661
 662     /* Check if there's enough space before the lowest Vad */
 663     LowVpn = ALIGN_UP_BY((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) / PAGE_SIZE;
 664     if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount))
 665     {
 666         /* There is enough space to add our address */
 667         LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, Alignment >> PAGE_SHIFT);
 668         *Base = LowVpn << PAGE_SHIFT;
 669         *Parent = OldNode;
 670         return TableInsertAsLeft;
 671     }
 672
 673     /* No address space left at all */
 674     *Base = 0;
 675     *Parent = NULL;
 676     return TableFoundNode;
 677 }
 678
 679 NTSTATUS
 680 NTAPI
 681 MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length,
 682                                      IN ULONG_PTR BoundaryAddress,
 683                                      IN ULONG_PTR Alignment,
 684                                      IN PMM_AVL_TABLE Table,
 685                                      OUT PULONG_PTR Base)
 686 {
 687     PMMADDRESS_NODE Node, LowestNode;
 688     ULONG_PTR LowVpn, BestVpn;
 689
 690     /* Sanity checks */
 691     ASSERT(Table == &MmSectionBasedRoot);
 692     ASSERT(BoundaryAddress);
 693     ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
 694
 695     /* Compute page length, make sure the boundary address is valid */
 696     Length = ROUND_TO_PAGES(Length);
 697     if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
 698
 699     /* Check if the table is empty */
 700     BestVpn = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment);
 701     if (Table->NumberGenericTableElements == 0)
 702     {
 703         /* Tree is empty, the candidate address is already the best one */
 704         *Base = BestVpn;
 705         return STATUS_SUCCESS;
 706     }
 707
 708     /* Go to the right-most node which should be the biggest address */
 709     Node = Table->BalancedRoot.RightChild;
 710     while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
 711
 712     /* Check if we can fit in here */
 713     LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment);
 714     if ((LowVpn < BoundaryAddress) && (Length <= (BoundaryAddress - LowVpn)))
 715     {
 716 #if (NTDDI_VERSION >= NTDDI_VISTA)
 717         /* Return the address. */
 718         *Base = BestVpn;
 719 #else
 720         /* Note: this is a compatibility hack that mimics a bug in the 2k3
 721            kernel. It will can waste up to Alignment bytes of memory above
 722            the allocation. This bug was fixed in Windows Vista */
 723         *Base = ROUND_DOWN(BoundaryAddress - Length, Alignment);
 724 #endif
 725         return STATUS_SUCCESS;
 726     }
 727
 728     /* Now loop the Vad nodes */
 729     do
 730     {
 731         /* Break out if we've reached the last node */
 732         LowestNode = MiGetPreviousNode(Node);
 733         if (!LowestNode) break;
 734
 735         /* Check if this node could contain the requested address */
 736         LowVpn = ROUND_UP(LowestNode->EndingVpn + 1, Alignment);
 737         if ((LowestNode->EndingVpn < BestVpn) &&
 738             (LowVpn < Node->StartingVpn) &&
 739             (Length <= (Node->StartingVpn - LowVpn)))
 740         {
 741             /* Check if we need to take BoundaryAddress into account */
 742             if (BoundaryAddress < Node->StartingVpn)
 743             {
 744                 /* Return the optimal VPN address */
 745                 *Base = BestVpn;
 746                 return STATUS_SUCCESS;
 747             }
 748             else
 749             {
 750                 /* The upper margin is given by the Node's starting address */
 751                 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
 752                 return STATUS_SUCCESS;
 753             }
 754         }
 755
 756         /* Move to the next node */
 757         Node = LowestNode;
 758     } while (TRUE);
 759
 760     /* Check if there's enough space before the lowest Vad */
 761     if ((Node->StartingVpn > (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) &&
 762         ((Node->StartingVpn - (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) >= Length))
 763     {
 764         /* Check if it fits in perfectly */
 765         if (BoundaryAddress < Node->StartingVpn)
 766         {
 767             /* Return the optimal VPN address */
 768             *Base = BestVpn;
 769             return STATUS_SUCCESS;
 770         }
 771
 772         /* Return an aligned base address within this node */
 773         *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment);
 774         return STATUS_SUCCESS;
 775     }
 776
 777     /* No address space left at all */
 778     return STATUS_NO_MEMORY;
 779 }
 780
 781 NTSTATUS
 782 NTAPI
 783 MiCheckSecuredVad(IN PMMVAD Vad,
 784                   IN PVOID Base,
 785                   IN SIZE_T Size,
 786                   IN ULONG ProtectionMask)
 787 {
 788     ULONG_PTR StartAddress, EndAddress;
 789
 790     /* Compute start and end address */
 791     StartAddress = (ULONG_PTR)Base;
 792     EndAddress = StartAddress + Size - 1;
 793
 794     /* Are we deleting/unmapping, or changing? */
 795     if (ProtectionMask < MM_DELETE_CHECK)
 796     {
 797         /* Changing... are we allowed to do so? */
 798         if ((Vad->u.VadFlags.NoChange == 1) &&
 799             (Vad->u2.VadFlags2.SecNoChange == 1) &&
 800             (Vad->u.VadFlags.Protection != ProtectionMask))
 801         {
 802             /* Nope, bail out */
 803             DPRINT1("Trying to mess with a no-change VAD!\n");
 804             return STATUS_INVALID_PAGE_PROTECTION;
 805         }
 806     }
 807     else
 808     {
 809         /* This is allowed */
 810         ProtectionMask = 0;
 811     }
 812
 813     /* ARM3 doesn't support this yet */
 814     ASSERT(Vad->u2.VadFlags2.MultipleSecured == 0);
 815
 816     /* Is this a one-secured VAD, like a TEB or PEB? */
 817     if (Vad->u2.VadFlags2.OneSecured)
 818     {
 819         /* Is this allocation being described by the VAD? */
 820         if ((StartAddress <= ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn) &&
 821             (EndAddress >= ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn))
 822         {
 823             /* Guard page? */
 824             if (ProtectionMask & MM_DECOMMIT)
 825             {
 826                 DPRINT1("Not allowed to change protection on guard page!\n");
 827                 return STATUS_INVALID_PAGE_PROTECTION;
 828             }
 829
 830             /* ARM3 doesn't have read-only VADs yet */
 831             ASSERT(Vad->u2.VadFlags2.ReadOnly == 0);
 832
 833             /* Check if read-write protections are allowed */
 834             if (MmReadWrite[ProtectionMask] < MM_READ_WRITE_ALLOWED)
 835             {
 836                 DPRINT1("Invalid protection mask for RW access!\n");
 837                 return STATUS_INVALID_PAGE_PROTECTION;
 838             }
 839         }
 840     }
 841
 842     /* All good, allow the change */
 843     return STATUS_SUCCESS;
 844 }
 845
 846 /* EOF */
 847