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