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)(ULONG_PTR)0xDEADBABEDEADBABEULL); 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)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL); 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)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL; 419 } 420 else 421 { 422 /* Delete the pointer to it */ 423 Vad->u4.Banked = (PVOID)(ULONG_PTR)0xDEADBAB1DEADBAB1ULL; 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 = NULL, 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. This means we must have already 674 moved one node left from the right-most node we started 675 with, thus we already have an OldNode! */ 676 ASSERT(OldNode != NULL); 677 678 /* The node we had before is the most left grandchild of 679 that right child, use it as parent. */ 680 ASSERT(RtlLeftChildAvl(OldNode) == NULL); 681 *Parent = OldNode; 682 return TableInsertAsLeft; 683 } 684 } 685 686 /* Update the upper margin if necessary */ 687 if (Node->StartingVpn < HighVpn) HighVpn = Node->StartingVpn; 688 689 /* Remember the current node and go to the previous node */ 690 OldNode = Node; 691 Node = MiGetPreviousNode(Node); 692 } 693 694 /* Check if there's enough space before the lowest Vad */ 695 LowVpn = ALIGN_UP_BY((ULONG_PTR)MI_LOWEST_VAD_ADDRESS, Alignment) / PAGE_SIZE; 696 if ((HighVpn > LowVpn) && ((HighVpn - LowVpn) >= PageCount)) 697 { 698 /* There is enough space to add our address */ 699 LowVpn = ALIGN_DOWN_BY(HighVpn - PageCount, Alignment >> PAGE_SHIFT); 700 *Base = LowVpn << PAGE_SHIFT; 701 *Parent = OldNode; 702 return TableInsertAsLeft; 703 } 704 705 /* No address space left at all */ 706 *Base = 0; 707 *Parent = NULL; 708 return TableFoundNode; 709 } 710 711 NTSTATUS 712 NTAPI 713 MiFindEmptyAddressRangeDownBasedTree(IN SIZE_T Length, 714 IN ULONG_PTR BoundaryAddress, 715 IN ULONG_PTR Alignment, 716 IN PMM_AVL_TABLE Table, 717 OUT PULONG_PTR Base) 718 { 719 PMMADDRESS_NODE Node, LowestNode; 720 ULONG_PTR LowVpn, BestVpn; 721 722 /* Sanity checks */ 723 ASSERT(Table == &MmSectionBasedRoot); 724 ASSERT(BoundaryAddress); 725 ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1)); 726 727 /* Compute page length, make sure the boundary address is valid */ 728 Length = ROUND_TO_PAGES(Length); 729 if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY; 730 731 /* Check if the table is empty */ 732 BestVpn = ROUND_DOWN(BoundaryAddress + 1 - Length, Alignment); 733 if (Table->NumberGenericTableElements == 0) 734 { 735 /* Tree is empty, the candidate address is already the best one */ 736 *Base = BestVpn; 737 return STATUS_SUCCESS; 738 } 739 740 /* Go to the right-most node which should be the biggest address */ 741 Node = Table->BalancedRoot.RightChild; 742 while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node); 743 744 /* Check if we can fit in here */ 745 LowVpn = ROUND_UP(Node->EndingVpn + 1, Alignment); 746 if ((LowVpn < BoundaryAddress) && (Length <= (BoundaryAddress - LowVpn))) 747 { 748 #if (NTDDI_VERSION >= NTDDI_VISTA) 749 /* Return the address. */ 750 *Base = BestVpn; 751 #else 752 /* Note: this is a compatibility hack that mimics a bug in the 2k3 753 kernel. It will can waste up to Alignment bytes of memory above 754 the allocation. This bug was fixed in Windows Vista */ 755 *Base = ROUND_DOWN(BoundaryAddress - Length, Alignment); 756 #endif 757 return STATUS_SUCCESS; 758 } 759 760 /* Now loop the Vad nodes */ 761 do 762 { 763 /* Break out if we've reached the last node */ 764 LowestNode = MiGetPreviousNode(Node); 765 if (!LowestNode) break; 766 767 /* Check if this node could contain the requested address */ 768 LowVpn = ROUND_UP(LowestNode->EndingVpn + 1, Alignment); 769 if ((LowestNode->EndingVpn < BestVpn) && 770 (LowVpn < Node->StartingVpn) && 771 (Length <= (Node->StartingVpn - LowVpn))) 772 { 773 /* Check if we need to take BoundaryAddress into account */ 774 if (BoundaryAddress < Node->StartingVpn) 775 { 776 /* Return the optimal VPN address */ 777 *Base = BestVpn; 778 return STATUS_SUCCESS; 779 } 780 else 781 { 782 /* The upper margin is given by the Node's starting address */ 783 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment); 784 return STATUS_SUCCESS; 785 } 786 } 787 788 /* Move to the next node */ 789 Node = LowestNode; 790 } while (TRUE); 791 792 /* Check if there's enough space before the lowest Vad */ 793 if ((Node->StartingVpn > (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) && 794 ((Node->StartingVpn - (ULONG_PTR)MI_LOWEST_VAD_ADDRESS) >= Length)) 795 { 796 /* Check if it fits in perfectly */ 797 if (BoundaryAddress < Node->StartingVpn) 798 { 799 /* Return the optimal VPN address */ 800 *Base = BestVpn; 801 return STATUS_SUCCESS; 802 } 803 804 /* Return an aligned base address within this node */ 805 *Base = ROUND_DOWN(Node->StartingVpn - Length, Alignment); 806 return STATUS_SUCCESS; 807 } 808 809 /* No address space left at all */ 810 return STATUS_NO_MEMORY; 811 } 812 813 NTSTATUS 814 NTAPI 815 MiCheckSecuredVad(IN PMMVAD Vad, 816 IN PVOID Base, 817 IN SIZE_T Size, 818 IN ULONG ProtectionMask) 819 { 820 ULONG_PTR StartAddress, EndAddress; 821 822 /* Compute start and end address */ 823 StartAddress = (ULONG_PTR)Base; 824 EndAddress = StartAddress + Size - 1; 825 826 /* Are we deleting/unmapping, or changing? */ 827 if (ProtectionMask < MM_DELETE_CHECK) 828 { 829 /* Changing... are we allowed to do so? */ 830 if ((Vad->u.VadFlags.NoChange == 1) && 831 (Vad->u2.VadFlags2.SecNoChange == 1) && 832 (Vad->u.VadFlags.Protection != ProtectionMask)) 833 { 834 /* Nope, bail out */ 835 DPRINT1("Trying to mess with a no-change VAD!\n"); 836 return STATUS_INVALID_PAGE_PROTECTION; 837 } 838 } 839 else 840 { 841 /* This is allowed */ 842 ProtectionMask = 0; 843 } 844 845 /* ARM3 doesn't support this yet */ 846 ASSERT(Vad->u2.VadFlags2.MultipleSecured == 0); 847 848 /* Is this a one-secured VAD, like a TEB or PEB? */ 849 if (Vad->u2.VadFlags2.OneSecured) 850 { 851 /* Is this allocation being described by the VAD? */ 852 if ((StartAddress <= ((PMMVAD_LONG)Vad)->u3.Secured.EndVpn) && 853 (EndAddress >= ((PMMVAD_LONG)Vad)->u3.Secured.StartVpn)) 854 { 855 /* Guard page? */ 856 if (ProtectionMask & MM_DECOMMIT) 857 { 858 DPRINT1("Not allowed to change protection on guard page!\n"); 859 return STATUS_INVALID_PAGE_PROTECTION; 860 } 861 862 /* ARM3 doesn't have read-only VADs yet */ 863 ASSERT(Vad->u2.VadFlags2.ReadOnly == 0); 864 865 /* Check if read-write protections are allowed */ 866 if (MmReadWrite[ProtectionMask] < MM_READ_WRITE_ALLOWED) 867 { 868 DPRINT1("Invalid protection mask for RW access!\n"); 869 return STATUS_INVALID_PAGE_PROTECTION; 870 } 871 } 872 } 873 874 /* All good, allow the change */ 875 return STATUS_SUCCESS; 876 } 877 878 /* EOF */ 879 880