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 968