ntoskrnl/mm/marea.c

   1 /*
   2  * Copyright (C) 1998-2005 ReactOS Team (and the authors from the programmers section)
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  17  *
  18  *
  19  * PROJECT:         ReactOS kernel
  20  * FILE:            ntoskrnl/mm/marea.c
  21  * PURPOSE:         Implements memory areas
  22  *
  23  * PROGRAMMERS:     Rex Jolliff
  24  *                  David Welch
  25  *                  Eric Kohl
  26  *                  Philip Susi
  27  *                  Casper Hornstrup
  28  *                  Eric Kohl
  29  *                  Ge van Geldorp
  30  *                  Royce Mitchell III
  31  *                  Aleksey Bragin
  32  *                  Jason Filby
  33  *                  Thomas Weidenmueller
  34  *                  Gunnar Andre' Dalsnes
  35  *                  Mike Nordell
  36  *                  Alex Ionescu
  37  *                  Filip Navara
  38  *                  Herve Poussineau
  39  *                  Steven Edwards
  40  */
  41
  42 /* INCLUDES *****************************************************************/
  43
  44 #include <ntoskrnl.h>
  45 #define NDEBUG
  46 #include "../cache/section/newmm.h"
  47 #include <debug.h>
  48
  49 #include "ARM3/miarm.h"
  50
  51 MEMORY_AREA MiStaticMemoryAreas[MI_STATIC_MEMORY_AREAS];
  52 ULONG MiStaticMemoryAreaCount;
  53
  54 /* FUNCTIONS *****************************************************************/
  55
  56 /**
  57  * @name MmIterateFirstNode
  58  *
  59  * @param Node
  60  *        Head node of the MEMORY_AREA tree.
  61  *
  62  * @return The leftmost MEMORY_AREA node (ie. the one with lowest
  63  *         address)
  64  */
  65
  66 static PMEMORY_AREA MmIterateFirstNode(PMEMORY_AREA Node)
  67 {
  68    while (Node->LeftChild != NULL)
  69       Node = Node->LeftChild;
  70
  71    return Node;
  72 }
  73
  74 /**
  75  * @name MmIterateNextNode
  76  *
  77  * @param Node
  78  *        Current node in the tree.
  79  *
  80  * @return Next node in the tree (sorted by address).
  81  */
  82
  83 static PMEMORY_AREA MmIterateNextNode(PMEMORY_AREA Node)
  84 {
  85    if (Node->RightChild != NULL)
  86    {
  87       Node = Node->RightChild;
  88       while (Node->LeftChild != NULL)
  89          Node = Node->LeftChild;
  90    }
  91    else
  92    {
  93       PMEMORY_AREA TempNode = NULL;
  94
  95       do
  96       {
  97          /* Check if we're at the end of tree. */
  98          if (Node->Parent == NULL)
  99             return NULL;
 100
 101          TempNode = Node;
 102          Node = Node->Parent;
 103       }
 104       while (TempNode == Node->RightChild);
 105    }
 106    return Node;
 107 }
 108
 109 /**
 110  * @name MmIterateLastNode
 111  *
 112  * @param Node
 113  *        Head node of the MEMORY_AREA tree.
 114  *
 115  * @return The rightmost MEMORY_AREA node (ie. the one with highest
 116  *         address)
 117  */
 118
 119 static PMEMORY_AREA MmIterateLastNode(PMEMORY_AREA Node)
 120 {
 121    while (Node->RightChild != NULL)
 122       Node = Node->RightChild;
 123
 124    return Node;
 125 }
 126
 127 /**
 128  * @name MmIteratePreviousNode
 129  *
 130  * @param Node
 131  *        Current node in the tree.
 132  *
 133  * @return Previous node in the tree (sorted by address).
 134  */
 135
 136 static PMEMORY_AREA MmIteratePrevNode(PMEMORY_AREA Node)
 137 {
 138    if (Node->LeftChild != NULL)
 139    {
 140       Node = Node->LeftChild;
 141       while (Node->RightChild != NULL)
 142          Node = Node->RightChild;
 143    }
 144    else
 145    {
 146       PMEMORY_AREA TempNode = NULL;
 147
 148       do
 149       {
 150          /* Check if we're at the end of tree. */
 151          if (Node->Parent == NULL)
 152             return NULL;
 153
 154          TempNode = Node;
 155          Node = Node->Parent;
 156       }
 157       while (TempNode == Node->LeftChild);
 158    }
 159    return Node;
 160 }
 161
 162 PMEMORY_AREA NTAPI
 163 MmLocateMemoryAreaByAddress(
 164    PMMSUPPORT AddressSpace,
 165    PVOID Address)
 166 {
 167    PMEMORY_AREA Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 168
 169    DPRINT("MmLocateMemoryAreaByAddress(AddressSpace %p, Address %p)\n",
 170            AddressSpace, Address);
 171
 172    while (Node != NULL)
 173    {
 174       if (Address < Node->StartingAddress)
 175          Node = Node->LeftChild;
 176       else if (Address >= Node->EndingAddress)
 177          Node = Node->RightChild;
 178       else
 179       {
 180          DPRINT("MmLocateMemoryAreaByAddress(%p): %p [%p - %p]\n",
 181                 Address, Node, Node->StartingAddress, Node->EndingAddress);
 182          return Node;
 183       }
 184    }
 185
 186    DPRINT("MmLocateMemoryAreaByAddress(%p): 0\n", Address);
 187    return NULL;
 188 }
 189
 190 PMEMORY_AREA NTAPI
 191 MmLocateMemoryAreaByRegion(
 192    PMMSUPPORT AddressSpace,
 193    PVOID Address,
 194    ULONG_PTR Length)
 195 {
 196    PMEMORY_AREA Node;
 197    PVOID Extent = (PVOID)((ULONG_PTR)Address + Length);
 198
 199    /* Special case for empty tree. */
 200    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 201       return NULL;
 202
 203    /* Traverse the tree from left to right. */
 204    for (Node = MmIterateFirstNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 205         Node != NULL;
 206         Node = MmIterateNextNode(Node))
 207    {
 208       if (Node->StartingAddress >= Address &&
 209           Node->StartingAddress < Extent)
 210       {
 211          DPRINT("MmLocateMemoryAreaByRegion(%p - %p): %p - %p\n",
 212                 Address, (ULONG_PTR)Address + Length, Node->StartingAddress,
 213                 Node->EndingAddress);
 214          return Node;
 215       }
 216       if (Node->EndingAddress > Address &&
 217           Node->EndingAddress < Extent)
 218       {
 219          DPRINT("MmLocateMemoryAreaByRegion(%p - %p): %p - %p\n",
 220                 Address, (ULONG_PTR)Address + Length, Node->StartingAddress,
 221                 Node->EndingAddress);
 222          return Node;
 223       }
 224       if (Node->StartingAddress <= Address &&
 225           Node->EndingAddress >= Extent)
 226       {
 227          DPRINT("MmLocateMemoryAreaByRegion(%p - %p): %p - %p\n",
 228                 Address, (ULONG_PTR)Address + Length, Node->StartingAddress,
 229                 Node->EndingAddress);
 230          return Node;
 231       }
 232       if (Node->StartingAddress >= Extent)
 233       {
 234          DPRINT("Finished MmLocateMemoryAreaByRegion() = NULL\n");
 235          return NULL;
 236       }
 237    }
 238
 239    return NULL;
 240 }
 241
 242 /**
 243  * @name MmCompressHelper
 244  *
 245  * This is helper of MmRebalanceTree. Performs a compression transformation
 246  * count times, starting at root.
 247  */
 248
 249 static VOID
 250 MmCompressHelper(
 251    PMMSUPPORT AddressSpace,
 252    ULONG Count)
 253 {
 254    PMEMORY_AREA Root = NULL;
 255    PMEMORY_AREA Red = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 256    PMEMORY_AREA Black = Red->LeftChild;
 257
 258    while (Count--)
 259    {
 260       if (Root)
 261          Root->LeftChild = Black;
 262       else
 263          AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)Black;
 264       Black->Parent = Root;
 265       Red->LeftChild = Black->RightChild;
 266       if (Black->RightChild)
 267          Black->RightChild->Parent = Red;
 268       Black->RightChild = Red;
 269       Red->Parent = Black;
 270       Root = Black;
 271
 272       if (Count)
 273       {
 274          Red = Root->LeftChild;
 275          Black = Red->LeftChild;
 276       }
 277    }
 278 }
 279
 280 /**
 281  * @name MmRebalanceTree
 282  *
 283  * Rebalance a memory area tree using the Tree->Vine->Balanced Tree
 284  * method described in libavl documentation in chapter 4.12.
 285  * (http://www.stanford.edu/~blp/avl/libavl.html/)
 286  */
 287
 288 static VOID
 289 MmRebalanceTree(
 290    PMMSUPPORT AddressSpace)
 291 {
 292    PMEMORY_AREA PreviousNode;
 293    PMEMORY_AREA CurrentNode;
 294    PMEMORY_AREA TempNode;
 295    ULONG NodeCount = 0;
 296    ULONG Vine;   /* Number of nodes in main vine. */
 297    ULONG Leaves; /* Nodes in incomplete bottom level, if any. */
 298    INT Height;   /* Height of produced balanced tree. */
 299
 300    /* Transform the tree into Vine. */
 301
 302    PreviousNode = NULL;
 303    CurrentNode = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 304    while (CurrentNode != NULL)
 305    {
 306       if (CurrentNode->RightChild == NULL)
 307       {
 308          PreviousNode = CurrentNode;
 309          CurrentNode = CurrentNode->LeftChild;
 310          NodeCount++;
 311       }
 312       else
 313       {
 314          TempNode = CurrentNode->RightChild;
 315
 316          CurrentNode->RightChild = TempNode->LeftChild;
 317          if (TempNode->LeftChild)
 318             TempNode->LeftChild->Parent = CurrentNode;
 319
 320          TempNode->LeftChild = CurrentNode;
 321          CurrentNode->Parent = TempNode;
 322
 323          CurrentNode = TempNode;
 324
 325          if (PreviousNode != NULL)
 326             PreviousNode->LeftChild = TempNode;
 327          else
 328             AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)TempNode;
 329          TempNode->Parent = PreviousNode;
 330       }
 331    }
 332
 333    /* Transform Vine back into a balanced tree. */
 334
 335    Leaves = NodeCount + 1;
 336    for (;;)
 337    {
 338       ULONG Next = Leaves & (Leaves - 1);
 339       if (Next == 0)
 340          break;
 341       Leaves = Next;
 342    }
 343    Leaves = NodeCount + 1 - Leaves;
 344
 345    MmCompressHelper(AddressSpace, Leaves);
 346
 347    Vine = NodeCount - Leaves;
 348    Height = 1 + (Leaves > 0);
 349    while (Vine > 1)
 350    {
 351       MmCompressHelper(AddressSpace, Vine / 2);
 352       Vine /= 2;
 353       Height++;
 354    }
 355 }
 356
 357 VOID
 358 NTAPI
 359 MiInsertVad(IN PMMVAD Vad,
 360 IN PEPROCESS Process);
 361
 362 ULONG
 363 NTAPI
 364 MiMakeProtectionMask(
 365     IN ULONG Protect
 366 );
 367
 368 static VOID
 369 MmInsertMemoryArea(
 370    PMMSUPPORT AddressSpace,
 371    PMEMORY_AREA marea)
 372 {
 373    PMEMORY_AREA Node;
 374    PMEMORY_AREA PreviousNode;
 375    ULONG Depth = 0;
 376    PEPROCESS Process = MmGetAddressSpaceOwner(AddressSpace);
 377
 378    /* Build a lame VAD if this is a user-space allocation */
 379    if ((marea->EndingAddress < MmSystemRangeStart) && (marea->Type != MEMORY_AREA_OWNED_BY_ARM3))
 380    {
 381        PMMVAD Vad;
 382
 383        ASSERT(marea->Type == MEMORY_AREA_SECTION_VIEW || marea->Type == MEMORY_AREA_CACHE);
 384        Vad = ExAllocatePoolWithTag(NonPagedPool, sizeof(MMVAD), TAG_MVAD);
 385        ASSERT(Vad);
 386        RtlZeroMemory(Vad, sizeof(MMVAD));
 387        Vad->StartingVpn = PAGE_ROUND_DOWN(marea->StartingAddress) >> PAGE_SHIFT;
 388        /*
 389         * For some strange reason, it is perfectly valid to create a MAREA from 0x1000 to... 0x1000.
 390         * In a normal OS/Memory Manager, this would be retarded, but ReactOS allows this (how it works
 391         * I don't even want to know).
 392         */
 393         if (marea->EndingAddress != marea->StartingAddress)
 394         {
 395             Vad->EndingVpn = PAGE_ROUND_DOWN((ULONG_PTR)marea->EndingAddress - 1) >> PAGE_SHIFT;
 396         }
 397         else
 398         {
 399             Vad->EndingVpn = Vad->StartingVpn;
 400         }
 401        Vad->u.VadFlags.Spare = 1;
 402        Vad->u.VadFlags.Protection = MiMakeProtectionMask(marea->Protect);
 403
 404        /* Insert the VAD */
 405        MiInsertVad(Vad, Process);
 406        marea->Vad = Vad;
 407    }
 408    else
 409    {
 410        marea->Vad = NULL;
 411    }
 412
 413    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 414    {
 415       AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)marea;
 416       marea->LeftChild = marea->RightChild = marea->Parent = NULL;
 417       return;
 418    }
 419
 420    Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 421    do
 422    {
 423       DPRINT("marea->EndingAddress: %p Node->StartingAddress: %p\n",
 424              marea->EndingAddress, Node->StartingAddress);
 425       DPRINT("marea->StartingAddress: %p Node->EndingAddress: %p\n",
 426              marea->StartingAddress, Node->EndingAddress);
 427       ASSERT(marea->EndingAddress <= Node->StartingAddress ||
 428              marea->StartingAddress >= Node->EndingAddress);
 429       ASSERT(marea->StartingAddress != Node->StartingAddress);
 430
 431       PreviousNode = Node;
 432
 433       if (marea->StartingAddress < Node->StartingAddress)
 434          Node = Node->LeftChild;
 435       else
 436          Node = Node->RightChild;
 437
 438       if (Node)
 439       {
 440          Depth++;
 441          if (Depth == 22)
 442          {
 443             MmRebalanceTree(AddressSpace);
 444             PreviousNode = Node->Parent;
 445          }
 446       }
 447    }
 448    while (Node != NULL);
 449
 450    marea->LeftChild = marea->RightChild = NULL;
 451    marea->Parent = PreviousNode;
 452    if (marea->StartingAddress < PreviousNode->StartingAddress)
 453       PreviousNode->LeftChild = marea;
 454    else
 455       PreviousNode->RightChild = marea;
 456 }
 457
 458 static PVOID
 459 MmFindGapBottomUp(
 460    PMMSUPPORT AddressSpace,
 461    ULONG_PTR Length,
 462    ULONG_PTR Granularity)
 463 {
 464     ULONG_PTR LowestAddress, HighestAddress, Candidate;
 465     PMEMORY_AREA Root, Node;
 466
 467     /* Get the margins of the address space */
 468     if (MmGetAddressSpaceOwner(AddressSpace) != NULL)
 469     {
 470         LowestAddress = (ULONG_PTR)MM_LOWEST_USER_ADDRESS;
 471         HighestAddress = (ULONG_PTR)MmHighestUserAddress;
 472     }
 473     else
 474     {
 475         LowestAddress = (ULONG_PTR)MmSystemRangeStart;
 476         HighestAddress = MAXULONG_PTR;
 477     }
 478
 479     /* Start with the lowest address */
 480     Candidate = LowestAddress;
 481
 482     /* Check for overflow */
 483     if ((Candidate + Length) < Candidate) return NULL;
 484
 485     /* Get the root of the address space tree */
 486     Root = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 487
 488     /* Go to the node with lowest address in the tree. */
 489     Node = Root ? MmIterateFirstNode(Root) : NULL;
 490     while (Node && ((ULONG_PTR)Node->EndingAddress < LowestAddress))
 491     {
 492         Node = MmIterateNextNode(Node);
 493     }
 494
 495     /* Traverse the tree from low to high addresses */
 496     while (Node && ((ULONG_PTR)Node->EndingAddress < HighestAddress))
 497     {
 498         /* Check if the memory area fits before the current node */
 499         if ((ULONG_PTR)Node->StartingAddress >= (Candidate + Length))
 500         {
 501             DPRINT("MmFindGapBottomUp: %p\n", Candidate);
 502             ASSERT(Candidate >= LowestAddress);
 503             return (PVOID)Candidate;
 504         }
 505
 506         /* Calculate next possible adress above this node */
 507         Candidate = ALIGN_UP_BY((ULONG_PTR)Node->EndingAddress, Granularity);
 508
 509         /* Check for overflow */
 510         if ((Candidate + Length) < (ULONG_PTR)Node->EndingAddress) return NULL;
 511
 512         /* Go to the next higher node */
 513         Node = MmIterateNextNode(Node);
 514     }
 515
 516     /* Check if there is enough space after the last memory area. */
 517     if ((Candidate + Length) <= HighestAddress)
 518     {
 519         DPRINT("MmFindGapBottomUp: %p\n", Candidate);
 520         ASSERT(Candidate >= LowestAddress);
 521         return (PVOID)Candidate;
 522     }
 523
 524     DPRINT("MmFindGapBottomUp: 0\n");
 525     return NULL;
 526 }
 527
 528
 529 static PVOID
 530 MmFindGapTopDown(
 531    PMMSUPPORT AddressSpace,
 532    ULONG_PTR Length,
 533    ULONG_PTR Granularity)
 534 {
 535     ULONG_PTR LowestAddress, HighestAddress, Candidate;
 536     PMEMORY_AREA Root, Node;
 537
 538     /* Get the margins of the address space */
 539     if (MmGetAddressSpaceOwner(AddressSpace) != NULL)
 540     {
 541         LowestAddress = (ULONG_PTR)MM_LOWEST_USER_ADDRESS;
 542         HighestAddress = (ULONG_PTR)MmHighestUserAddress;
 543     }
 544     else
 545     {
 546         LowestAddress = (ULONG_PTR)MmSystemRangeStart;
 547         HighestAddress = MAXULONG_PTR;
 548     }
 549
 550     /* Calculate the highest candidate */
 551     Candidate = ALIGN_DOWN_BY(HighestAddress + 1 - Length, Granularity);
 552
 553     /* Check for overflow. */
 554     if (Candidate > HighestAddress) return NULL;
 555
 556     /* Get the root of the address space tree */
 557     Root = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 558
 559     /* Go to the node with highest address in the tree. */
 560     Node = Root ? MmIterateLastNode(Root) : NULL;
 561     while (Node && ((ULONG_PTR)Node->StartingAddress > HighestAddress))
 562     {
 563         Node = MmIteratePrevNode(Node);
 564     }
 565
 566     /* Traverse the tree from high to low addresses */
 567     while (Node && ((ULONG_PTR)Node->StartingAddress > LowestAddress))
 568     {
 569         /* Check if the memory area fits after the current node */
 570         if ((ULONG_PTR)Node->EndingAddress <= Candidate)
 571         {
 572             DPRINT("MmFindGapTopDown: %p\n", Candidate);
 573             return (PVOID)Candidate;
 574         }
 575
 576         /* Calculate next possible adress below this node */
 577         Candidate = ALIGN_DOWN_BY((ULONG_PTR)Node->StartingAddress - Length,
 578                                   Granularity);
 579
 580         /* Check for overflow. */
 581         if (Candidate > (ULONG_PTR)Node->StartingAddress)
 582             return NULL;
 583
 584         /* Go to the next lower node */
 585         Node = MmIteratePrevNode(Node);
 586     }
 587
 588     /* Check if the last candidate is inside the given range */
 589     if (Candidate >= LowestAddress)
 590     {
 591         DPRINT("MmFindGapTopDown: %p\n", Candidate);
 592         return (PVOID)Candidate;
 593     }
 594
 595     DPRINT("MmFindGapTopDown: 0\n");
 596     return NULL;
 597 }
 598
 599
 600 PVOID NTAPI
 601 MmFindGap(
 602    PMMSUPPORT AddressSpace,
 603    ULONG_PTR Length,
 604    ULONG_PTR Granularity,
 605    BOOLEAN TopDown)
 606 {
 607    if (TopDown)
 608       return MmFindGapTopDown(AddressSpace, Length, Granularity);
 609
 610    return MmFindGapBottomUp(AddressSpace, Length, Granularity);
 611 }
 612
 613 ULONG_PTR NTAPI
 614 MmFindGapAtAddress(
 615    PMMSUPPORT AddressSpace,
 616    PVOID Address)
 617 {
 618    PMEMORY_AREA Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 619    PMEMORY_AREA RightNeighbour = NULL;
 620    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 621    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 622                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 623
 624    Address = MM_ROUND_DOWN(Address, PAGE_SIZE);
 625
 626    if (LowestAddress < MmSystemRangeStart)
 627    {
 628       if (Address >= MmSystemRangeStart)
 629       {
 630          return 0;
 631       }
 632    }
 633    else
 634    {
 635       if (Address < LowestAddress)
 636       {
 637          return 0;
 638       }
 639    }
 640
 641    while (Node != NULL)
 642    {
 643       if (Address < Node->StartingAddress)
 644       {
 645          RightNeighbour = Node;
 646          Node = Node->LeftChild;
 647       }
 648       else if (Address >= Node->EndingAddress)
 649       {
 650          Node = Node->RightChild;
 651       }
 652       else
 653       {
 654          DPRINT("MmFindGapAtAddress: 0\n");
 655          return 0;
 656       }
 657    }
 658
 659    if (RightNeighbour)
 660    {
 661       DPRINT("MmFindGapAtAddress: %p [%p]\n", Address,
 662              (ULONG_PTR)RightNeighbour->StartingAddress - (ULONG_PTR)Address);
 663       return (ULONG_PTR)RightNeighbour->StartingAddress - (ULONG_PTR)Address;
 664    }
 665    else
 666    {
 667       DPRINT("MmFindGapAtAddress: %p [%p]\n", Address,
 668              (ULONG_PTR)HighestAddress - (ULONG_PTR)Address);
 669       return (ULONG_PTR)HighestAddress - (ULONG_PTR)Address;
 670    }
 671 }
 672
 673 VOID
 674 NTAPI
 675 MiRemoveNode(IN PMMADDRESS_NODE Node,
 676 IN PMM_AVL_TABLE Table);
 677
 678 #if DBG
 679
 680 static
 681 VOID
 682 MiRosCheckMemoryAreasRecursive(
 683    PMEMORY_AREA Node)
 684 {
 685     /* Check if the allocation is ok */
 686     ExpCheckPoolAllocation(Node, NonPagedPool, 'ERAM');
 687
 688     /* Check some fields */
 689     ASSERT(Node->Magic == 'erAM');
 690     ASSERT(PAGE_ALIGN(Node->StartingAddress) == Node->StartingAddress);
 691     ASSERT(Node->EndingAddress != NULL);
 692     ASSERT(PAGE_ALIGN(Node->EndingAddress) == Node->EndingAddress);
 693     ASSERT((ULONG_PTR)Node->StartingAddress < (ULONG_PTR)Node->EndingAddress);
 694     ASSERT((Node->Type == 0) ||
 695            (Node->Type == MEMORY_AREA_CACHE) ||
 696           // (Node->Type == MEMORY_AREA_CACHE_SEGMENT) ||
 697            (Node->Type == MEMORY_AREA_SECTION_VIEW) ||
 698            (Node->Type == MEMORY_AREA_OWNED_BY_ARM3) ||
 699            (Node->Type == (MEMORY_AREA_OWNED_BY_ARM3 | MEMORY_AREA_STATIC)));
 700
 701     /* Recursively check children */
 702     if (Node->LeftChild != NULL)
 703         MiRosCheckMemoryAreasRecursive(Node->LeftChild);
 704     if (Node->RightChild != NULL)
 705         MiRosCheckMemoryAreasRecursive(Node->RightChild);
 706 }
 707
 708 VOID
 709 NTAPI
 710 MiRosCheckMemoryAreas(
 711    PMMSUPPORT AddressSpace)
 712 {
 713     PMEMORY_AREA RootNode;
 714     PEPROCESS AddressSpaceOwner;
 715     BOOLEAN NeedReleaseLock;
 716
 717     NeedReleaseLock = FALSE;
 718
 719     /* Get the address space owner */
 720     AddressSpaceOwner = CONTAINING_RECORD(AddressSpace, EPROCESS, Vm);
 721
 722     /* Check if we already own the address space lock */
 723     if (AddressSpaceOwner->AddressCreationLock.Owner != KeGetCurrentThread())
 724     {
 725         /* We must own it! */
 726         MmLockAddressSpace(AddressSpace);
 727         NeedReleaseLock = TRUE;
 728     }
 729
 730     /* Check all memory areas */
 731     RootNode = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 732     MiRosCheckMemoryAreasRecursive(RootNode);
 733
 734     /* Release the lock, if we acquired it */
 735     if (NeedReleaseLock)
 736     {
 737         MmUnlockAddressSpace(AddressSpace);
 738     }
 739 }
 740
 741 extern KGUARDED_MUTEX PspActiveProcessMutex;
 742
 743 VOID
 744 NTAPI
 745 MiCheckAllProcessMemoryAreas(VOID)
 746 {
 747     PEPROCESS Process;
 748     PLIST_ENTRY Entry;
 749
 750     /* Acquire the Active Process Lock */
 751     KeAcquireGuardedMutex(&PspActiveProcessMutex);
 752
 753     /* Loop the process list */
 754     Entry = PsActiveProcessHead.Flink;
 755     while (Entry != &PsActiveProcessHead)
 756     {
 757         /* Get the process */
 758         Process = CONTAINING_RECORD(Entry, EPROCESS, ActiveProcessLinks);
 759
 760         /* Check memory areas */
 761         MiRosCheckMemoryAreas(&Process->Vm);
 762
 763         Entry = Entry->Flink;
 764     }
 765
 766     /* Release the lock */
 767     KeReleaseGuardedMutex(&PspActiveProcessMutex);
 768 }
 769
 770 #endif
 771
 772 /**
 773  * @name MmFreeMemoryArea
 774  *
 775  * Free an existing memory area.
 776  *
 777  * @param AddressSpace
 778  *        Address space to free the area from.
 779  * @param MemoryArea
 780  *        Memory area we're about to free.
 781  * @param FreePage
 782  *        Callback function for each freed page.
 783  * @param FreePageContext
 784  *        Context passed to the callback function.
 785  *
 786  * @return Status
 787  *
 788  * @remarks Lock the address space before calling this function.
 789  */
 790 VOID
 791 NTAPI
 792 MiDeletePte(IN PMMPTE PointerPte,
 793             IN PVOID VirtualAddress,
 794             IN PEPROCESS CurrentProcess,
 795             IN PMMPTE PrototypePte);
 796
 797 NTSTATUS NTAPI
 798 MmFreeMemoryArea(
 799    PMMSUPPORT AddressSpace,
 800    PMEMORY_AREA MemoryArea,
 801    PMM_FREE_PAGE_FUNC FreePage,
 802    PVOID FreePageContext)
 803 {
 804    PMEMORY_AREA *ParentReplace;
 805    ULONG_PTR Address;
 806    PVOID EndAddress;
 807
 808    /* Make sure we own the address space lock! */
 809    ASSERT(CONTAINING_RECORD(AddressSpace, EPROCESS, Vm)->AddressCreationLock.Owner == KeGetCurrentThread());
 810
 811     /* Check magic */
 812     ASSERT(MemoryArea->Magic == 'erAM');
 813
 814    if (MemoryArea->Type != MEMORY_AREA_OWNED_BY_ARM3)
 815    {
 816        PEPROCESS CurrentProcess = PsGetCurrentProcess();
 817        PEPROCESS Process = MmGetAddressSpaceOwner(AddressSpace);
 818
 819        if (Process != NULL &&
 820            Process != CurrentProcess)
 821        {
 822           KeAttachProcess(&Process->Pcb);
 823        }
 824
 825        EndAddress = MM_ROUND_UP(MemoryArea->EndingAddress, PAGE_SIZE);
 826        for (Address = (ULONG_PTR)MemoryArea->StartingAddress;
 827             Address < (ULONG_PTR)EndAddress;
 828             Address += PAGE_SIZE)
 829        {
 830              BOOLEAN Dirty = FALSE;
 831              SWAPENTRY SwapEntry = 0;
 832              PFN_NUMBER Page = 0;
 833
 834              if (MmIsPageSwapEntry(Process, (PVOID)Address))
 835              {
 836                 MmDeletePageFileMapping(Process, (PVOID)Address, &SwapEntry);
 837              }
 838              else
 839              {
 840                 MmDeleteVirtualMapping(Process, (PVOID)Address, FALSE, &Dirty, &Page);
 841              }
 842              if (FreePage != NULL)
 843              {
 844                 FreePage(FreePageContext, MemoryArea, (PVOID)Address,
 845                          Page, SwapEntry, (BOOLEAN)Dirty);
 846              }
 847 #if (_MI_PAGING_LEVELS == 2)
 848             /* Remove page table reference */
 849             ASSERT(KeGetCurrentIrql() <= APC_LEVEL);
 850             if ((SwapEntry || Page) && ((PVOID)Address < MmSystemRangeStart))
 851             {
 852                 ASSERT(AddressSpace != MmGetKernelAddressSpace());
 853                 if (MiQueryPageTableReferences((PVOID)Address) == 0)
 854                 {
 855                     /* No PTE relies on this PDE. Release it */
 856                     KIRQL OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 857                     PMMPDE PointerPde = MiAddressToPde(Address);
 858                     ASSERT(PointerPde->u.Hard.Valid == 1);
 859                     MiDeletePte(PointerPde, MiPdeToPte(PointerPde), Process, NULL);
 860                     ASSERT(PointerPde->u.Hard.Valid == 0);
 861                     KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
 862                 }
 863             }
 864 #endif
 865        }
 866
 867        if (Process != NULL &&
 868            Process != CurrentProcess)
 869        {
 870           KeDetachProcess();
 871        }
 872
 873        if (MemoryArea->Vad)
 874        {
 875            ASSERT(MemoryArea->EndingAddress < MmSystemRangeStart);
 876            ASSERT(MemoryArea->Type == MEMORY_AREA_SECTION_VIEW || MemoryArea->Type == MEMORY_AREA_CACHE);
 877
 878            /* MmCleanProcessAddressSpace might have removed it (and this would be MmDeleteProcessAdressSpace) */
 879            ASSERT(((PMMVAD)MemoryArea->Vad)->u.VadFlags.Spare != 0);
 880            if (((PMMVAD)MemoryArea->Vad)->u.VadFlags.Spare == 1)
 881            {
 882                MiRemoveNode(MemoryArea->Vad, &Process->VadRoot);
 883            }
 884
 885            ExFreePoolWithTag(MemoryArea->Vad, TAG_MVAD);
 886            MemoryArea->Vad = NULL;
 887        }
 888     }
 889
 890    /* Remove the tree item. */
 891    {
 892       if (MemoryArea->Parent != NULL)
 893       {
 894          if (MemoryArea->Parent->LeftChild == MemoryArea)
 895             ParentReplace = &MemoryArea->Parent->LeftChild;
 896          else
 897             ParentReplace = &MemoryArea->Parent->RightChild;
 898       }
 899       else
 900          ParentReplace = (PMEMORY_AREA*)&AddressSpace->WorkingSetExpansionLinks.Flink;
 901
 902       if (MemoryArea->RightChild == NULL)
 903       {
 904          *ParentReplace = MemoryArea->LeftChild;
 905          if (MemoryArea->LeftChild)
 906             MemoryArea->LeftChild->Parent = MemoryArea->Parent;
 907       }
 908       else
 909       {
 910          if (MemoryArea->RightChild->LeftChild == NULL)
 911          {
 912             MemoryArea->RightChild->LeftChild = MemoryArea->LeftChild;
 913             if (MemoryArea->LeftChild)
 914                MemoryArea->LeftChild->Parent = MemoryArea->RightChild;
 915
 916             *ParentReplace = MemoryArea->RightChild;
 917             MemoryArea->RightChild->Parent = MemoryArea->Parent;
 918          }
 919          else
 920          {
 921             PMEMORY_AREA LowestNode;
 922
 923             LowestNode = MemoryArea->RightChild->LeftChild;
 924             while (LowestNode->LeftChild != NULL)
 925                LowestNode = LowestNode->LeftChild;
 926
 927             LowestNode->Parent->LeftChild = LowestNode->RightChild;
 928             if (LowestNode->RightChild)
 929                LowestNode->RightChild->Parent = LowestNode->Parent;
 930
 931             LowestNode->LeftChild = MemoryArea->LeftChild;
 932             if (MemoryArea->LeftChild)
 933                MemoryArea->LeftChild->Parent = LowestNode;
 934
 935             LowestNode->RightChild = MemoryArea->RightChild;
 936             MemoryArea->RightChild->Parent = LowestNode;
 937
 938             *ParentReplace = LowestNode;
 939             LowestNode->Parent = MemoryArea->Parent;
 940          }
 941       }
 942    }
 943
 944    ExFreePoolWithTag(MemoryArea, TAG_MAREA);
 945
 946    DPRINT("MmFreeMemoryAreaByNode() succeeded\n");
 947
 948    return STATUS_SUCCESS;
 949 }
 950
 951 /**
 952  * @name MmCreateMemoryArea
 953  *
 954  * Create a memory area.
 955  *
 956  * @param AddressSpace
 957  *        Address space to create the area in.
 958  * @param Type
 959  *        Type of the memory area.
 960  * @param BaseAddress
 961  *        Base address for the memory area we're about the create. On
 962  *        input it contains either 0 (auto-assign address) or preferred
 963  *        address. On output it contains the starting address of the
 964  *        newly created area.
 965  * @param Length
 966  *        Length of the area to allocate.
 967  * @param Attributes
 968  *        Protection attributes for the memory area.
 969  * @param Result
 970  *        Receives a pointer to the memory area on successful exit.
 971  *
 972  * @return Status
 973  *
 974  * @remarks Lock the address space before calling this function.
 975  */
 976
 977 NTSTATUS NTAPI
 978 MmCreateMemoryArea(PMMSUPPORT AddressSpace,
 979                    ULONG Type,
 980                    PVOID *BaseAddress,
 981                    ULONG_PTR Length,
 982                    ULONG Protect,
 983                    PMEMORY_AREA *Result,
 984                    BOOLEAN FixedAddress,
 985                    ULONG AllocationFlags,
 986                    ULONG Granularity)
 987 {
 988    ULONG_PTR tmpLength;
 989    PMEMORY_AREA MemoryArea;
 990    ULONG_PTR EndingAddress;
 991
 992    DPRINT("MmCreateMemoryArea(Type 0x%lx, BaseAddress %p, "
 993           "*BaseAddress %p, Length %p, AllocationFlags %x, "
 994           "FixedAddress %x, Result %p)\n",
 995           Type, BaseAddress, *BaseAddress, Length, AllocationFlags,
 996           FixedAddress, Result);
 997
 998    if ((*BaseAddress) == 0 && !FixedAddress)
 999    {
1000       tmpLength = (ULONG_PTR)MM_ROUND_UP(Length, PAGE_SIZE);
1001       *BaseAddress = MmFindGap(AddressSpace,
1002                                tmpLength,
1003                                Granularity,
1004                                (AllocationFlags & MEM_TOP_DOWN) == MEM_TOP_DOWN);
1005       if ((*BaseAddress) == 0)
1006       {
1007          DPRINT("No suitable gap\n");
1008          return STATUS_NO_MEMORY;
1009       }
1010    }
1011    else
1012    {
1013       EndingAddress = ((ULONG_PTR)*BaseAddress + Length - 1) | (PAGE_SIZE - 1);
1014       *BaseAddress = ALIGN_DOWN_POINTER_BY(*BaseAddress, Granularity);
1015       tmpLength = EndingAddress + 1 - (ULONG_PTR)*BaseAddress;
1016
1017       if (!MmGetAddressSpaceOwner(AddressSpace) && *BaseAddress < MmSystemRangeStart)
1018       {
1019          return STATUS_ACCESS_VIOLATION;
1020       }
1021
1022       if (MmGetAddressSpaceOwner(AddressSpace) &&
1023           (ULONG_PTR)(*BaseAddress) + tmpLength > (ULONG_PTR)MmSystemRangeStart)
1024       {
1025          DPRINT("Memory area for user mode address space exceeds MmSystemRangeStart\n");
1026          return STATUS_ACCESS_VIOLATION;
1027       }
1028
1029       if (MmLocateMemoryAreaByRegion(AddressSpace,
1030                                      *BaseAddress,
1031                                      tmpLength) != NULL)
1032       {
1033          DPRINT("Memory area already occupied\n");
1034          return STATUS_CONFLICTING_ADDRESSES;
1035       }
1036    }
1037
1038     //
1039     // Is this a static memory area?
1040     //
1041     if (Type & MEMORY_AREA_STATIC)
1042     {
1043         //
1044         // Use the static array instead of the pool
1045         //
1046         ASSERT(MiStaticMemoryAreaCount < MI_STATIC_MEMORY_AREAS);
1047         MemoryArea = &MiStaticMemoryAreas[MiStaticMemoryAreaCount++];
1048         Type &= ~MEMORY_AREA_STATIC;
1049     }
1050     else
1051     {
1052         //
1053         // Allocate the memory area from nonpaged pool
1054         //
1055         MemoryArea = ExAllocatePoolWithTag(NonPagedPool,
1056                                            sizeof(MEMORY_AREA),
1057                                            TAG_MAREA);
1058     }
1059
1060    if (!MemoryArea)
1061    {
1062       DPRINT1("Not enough memory.\n");
1063       return STATUS_NO_MEMORY;
1064    }
1065
1066    RtlZeroMemory(MemoryArea, sizeof(MEMORY_AREA));
1067    MemoryArea->Type = Type;
1068    MemoryArea->StartingAddress = *BaseAddress;
1069    MemoryArea->EndingAddress = (PVOID)((ULONG_PTR)*BaseAddress + tmpLength);
1070    MemoryArea->Protect = Protect;
1071    MemoryArea->Flags = AllocationFlags;
1072    //MemoryArea->LockCount = 0;
1073    MemoryArea->Magic = 'erAM';
1074    MemoryArea->DeleteInProgress = FALSE;
1075
1076    MmInsertMemoryArea(AddressSpace, MemoryArea);
1077
1078    *Result = MemoryArea;
1079
1080    DPRINT("MmCreateMemoryArea() succeeded (%p)\n", *BaseAddress);
1081    return STATUS_SUCCESS;
1082 }
1083
1084 VOID NTAPI
1085 MmMapMemoryArea(PVOID BaseAddress,
1086                 SIZE_T Length,
1087                 ULONG Consumer,
1088                 ULONG Protection)
1089 {
1090    ULONG i;
1091    NTSTATUS Status;
1092
1093    ASSERT(((ULONG_PTR)BaseAddress % PAGE_SIZE) == 0);
1094
1095    for (i = 0; i < PAGE_ROUND_UP(Length) / PAGE_SIZE; i++)
1096    {
1097       PFN_NUMBER Page;
1098
1099       Status = MmRequestPageMemoryConsumer(Consumer, TRUE, &Page);
1100       if (!NT_SUCCESS(Status))
1101       {
1102          DPRINT1("Unable to allocate page\n");
1103          KeBugCheck(MEMORY_MANAGEMENT);
1104       }
1105       Status = MmCreateVirtualMapping (NULL,
1106                                        (PVOID)((ULONG_PTR)BaseAddress + (i * PAGE_SIZE)),
1107                                        Protection,
1108                                        &Page,
1109                                        1);
1110       if (!NT_SUCCESS(Status))
1111       {
1112          DPRINT1("Unable to create virtual mapping\n");
1113          KeBugCheck(MEMORY_MANAGEMENT);
1114       }
1115    }
1116 }
1117
1118 VOID
1119 NTAPI
1120 MmDeleteProcessAddressSpace2(IN PEPROCESS Process);
1121
1122 NTSTATUS
1123 NTAPI
1124 MmDeleteProcessAddressSpace(PEPROCESS Process)
1125 {
1126    PVOID Address;
1127    PMEMORY_AREA MemoryArea;
1128
1129    DPRINT("MmDeleteProcessAddressSpace(Process %p (%s))\n", Process,
1130           Process->ImageFileName);
1131
1132 #ifndef _M_AMD64
1133    RemoveEntryList(&Process->MmProcessLinks);
1134 #endif
1135    MmLockAddressSpace(&Process->Vm);
1136
1137    while ((MemoryArea = (PMEMORY_AREA)Process->Vm.WorkingSetExpansionLinks.Flink) != NULL)
1138    {
1139       switch (MemoryArea->Type)
1140       {
1141          case MEMORY_AREA_SECTION_VIEW:
1142              Address = (PVOID)MemoryArea->StartingAddress;
1143              MmUnlockAddressSpace(&Process->Vm);
1144              MmUnmapViewOfSection(Process, Address);
1145              MmLockAddressSpace(&Process->Vm);
1146              break;
1147
1148          case MEMORY_AREA_CACHE:
1149              Address = (PVOID)MemoryArea->StartingAddress;
1150              MmUnlockAddressSpace(&Process->Vm);
1151              MmUnmapViewOfCacheSegment(&Process->Vm, Address);
1152              MmLockAddressSpace(&Process->Vm);
1153              break;
1154
1155          case MEMORY_AREA_OWNED_BY_ARM3:
1156              MmFreeMemoryArea(&Process->Vm,
1157                               MemoryArea,
1158                               NULL,
1159                               NULL);
1160              break;
1161
1162          default:
1163             KeBugCheck(MEMORY_MANAGEMENT);
1164       }
1165    }
1166
1167 #if (_MI_PAGING_LEVELS == 2)
1168     {
1169         KIRQL OldIrql;
1170         PMMPDE pointerPde;
1171         /* Attach to Process */
1172         KeAttachProcess(&Process->Pcb);
1173
1174         /* Acquire PFN lock */
1175         OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
1176
1177         for (Address = MI_LOWEST_VAD_ADDRESS;
1178              Address < MM_HIGHEST_VAD_ADDRESS;
1179              Address =(PVOID)((ULONG_PTR)Address + (PAGE_SIZE * PTE_COUNT)))
1180         {
1181             /* At this point all references should be dead */
1182             if (MiQueryPageTableReferences(Address) != 0)
1183             {
1184                 DPRINT1("Process %p, Address %p, UsedPageTableEntries %lu\n",
1185                         Process,
1186                         Address,
1187                         MiQueryPageTableReferences(Address));
1188                 ASSERT(MiQueryPageTableReferences(Address) == 0);
1189             }
1190             pointerPde = MiAddressToPde(Address);
1191             /* Unlike in ARM3, we don't necesarrily free the PDE page as soon as reference reaches 0,
1192              * so we must clean up a bit when process closes */
1193             if (pointerPde->u.Hard.Valid)
1194                 MiDeletePte(pointerPde, MiPdeToPte(pointerPde), Process, NULL);
1195             ASSERT(pointerPde->u.Hard.Valid == 0);
1196         }
1197         /* Release lock */
1198         KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
1199
1200         /* Detach */
1201         KeDetachProcess();
1202     }
1203 #endif
1204
1205    MmUnlockAddressSpace(&Process->Vm);
1206
1207    DPRINT("Finished MmDeleteProcessAddressSpace()\n");
1208    MmDeleteProcessAddressSpace2(Process);
1209    return(STATUS_SUCCESS);
1210 }
1211
1212 /* EOF */