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