reactos/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.PrivateMemory = 1;
 403        Vad->u.VadFlags.Protection = MiMakeProtectionMask(marea->Protect);
 404
 405        /* Insert the VAD */
 406        MiInsertVad(Vad, Process);
 407        marea->Vad = Vad;
 408    }
 409    else
 410    {
 411        marea->Vad = NULL;
 412    }
 413
 414    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 415    {
 416       AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)marea;
 417       marea->LeftChild = marea->RightChild = marea->Parent = NULL;
 418       return;
 419    }
 420
 421    Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 422    do
 423    {
 424       DPRINT("marea->EndingAddress: %p Node->StartingAddress: %p\n",
 425              marea->EndingAddress, Node->StartingAddress);
 426       DPRINT("marea->StartingAddress: %p Node->EndingAddress: %p\n",
 427              marea->StartingAddress, Node->EndingAddress);
 428       ASSERT(marea->EndingAddress <= Node->StartingAddress ||
 429              marea->StartingAddress >= Node->EndingAddress);
 430       ASSERT(marea->StartingAddress != Node->StartingAddress);
 431
 432       PreviousNode = Node;
 433
 434       if (marea->StartingAddress < Node->StartingAddress)
 435          Node = Node->LeftChild;
 436       else
 437          Node = Node->RightChild;
 438
 439       if (Node)
 440       {
 441          Depth++;
 442          if (Depth == 22)
 443          {
 444             MmRebalanceTree(AddressSpace);
 445             PreviousNode = Node->Parent;
 446          }
 447       }
 448    }
 449    while (Node != NULL);
 450
 451    marea->LeftChild = marea->RightChild = NULL;
 452    marea->Parent = PreviousNode;
 453    if (marea->StartingAddress < PreviousNode->StartingAddress)
 454       PreviousNode->LeftChild = marea;
 455    else
 456       PreviousNode->RightChild = marea;
 457 }
 458
 459 static PVOID
 460 MmFindGapBottomUp(
 461    PMMSUPPORT AddressSpace,
 462    ULONG_PTR Length,
 463    ULONG_PTR Granularity)
 464 {
 465     ULONG_PTR LowestAddress, HighestAddress, Candidate;
 466     PMEMORY_AREA Root, Node;
 467
 468     /* Get the margins of the address space */
 469     if (MmGetAddressSpaceOwner(AddressSpace) != NULL)
 470     {
 471         LowestAddress = (ULONG_PTR)MM_LOWEST_USER_ADDRESS;
 472         HighestAddress = (ULONG_PTR)MmHighestUserAddress;
 473     }
 474     else
 475     {
 476         LowestAddress = (ULONG_PTR)MmSystemRangeStart;
 477         HighestAddress = MAXULONG_PTR;
 478     }
 479
 480     /* Start with the lowest address */
 481     Candidate = LowestAddress;
 482
 483     /* Check for overflow */
 484     if ((Candidate + Length) < Candidate) return NULL;
 485
 486     /* Get the root of the address space tree */
 487     Root = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 488
 489     /* Go to the node with lowest address in the tree. */
 490     Node = Root ? MmIterateFirstNode(Root) : NULL;
 491     while (Node && ((ULONG_PTR)Node->EndingAddress < LowestAddress))
 492     {
 493         Node = MmIterateNextNode(Node);
 494     }
 495
 496     /* Traverse the tree from low to high addresses */
 497     while (Node && ((ULONG_PTR)Node->EndingAddress < HighestAddress))
 498     {
 499         /* Check if the memory area fits before the current node */
 500         if ((ULONG_PTR)Node->StartingAddress >= (Candidate + Length))
 501         {
 502             DPRINT("MmFindGapBottomUp: %p\n", Candidate);
 503             ASSERT(Candidate >= LowestAddress);
 504             return (PVOID)Candidate;
 505         }
 506
 507         /* Calculate next possible adress above this node */
 508         Candidate = ALIGN_UP_BY((ULONG_PTR)Node->EndingAddress, Granularity);
 509
 510         /* Check for overflow */
 511         if ((Candidate + Length) < (ULONG_PTR)Node->EndingAddress) return NULL;
 512
 513         /* Go to the next higher node */
 514         Node = MmIterateNextNode(Node);
 515     }
 516
 517     /* Check if there is enough space after the last memory area. */
 518     if ((Candidate + Length) <= HighestAddress)
 519     {
 520         DPRINT("MmFindGapBottomUp: %p\n", Candidate);
 521         ASSERT(Candidate >= LowestAddress);
 522         return (PVOID)Candidate;
 523     }
 524
 525     DPRINT("MmFindGapBottomUp: 0\n");
 526     return NULL;
 527 }
 528
 529
 530 static PVOID
 531 MmFindGapTopDown(
 532    PMMSUPPORT AddressSpace,
 533    ULONG_PTR Length,
 534    ULONG_PTR Granularity)
 535 {
 536     ULONG_PTR LowestAddress, HighestAddress, Candidate;
 537     PMEMORY_AREA Root, Node;
 538
 539     /* Get the margins of the address space */
 540     if (MmGetAddressSpaceOwner(AddressSpace) != NULL)
 541     {
 542         LowestAddress = (ULONG_PTR)MM_LOWEST_USER_ADDRESS;
 543         HighestAddress = (ULONG_PTR)MmHighestUserAddress;
 544     }
 545     else
 546     {
 547         LowestAddress = (ULONG_PTR)MmSystemRangeStart;
 548         HighestAddress = MAXULONG_PTR;
 549     }
 550
 551     /* Calculate the highest candidate */
 552     Candidate = ALIGN_DOWN_BY(HighestAddress + 1 - Length, Granularity);
 553
 554     /* Check for overflow. */
 555     if (Candidate > HighestAddress) return NULL;
 556
 557     /* Get the root of the address space tree */
 558     Root = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 559
 560     /* Go to the node with highest address in the tree. */
 561     Node = Root ? MmIterateLastNode(Root) : NULL;
 562     while (Node && ((ULONG_PTR)Node->StartingAddress > HighestAddress))
 563     {
 564         Node = MmIteratePrevNode(Node);
 565     }
 566
 567     /* Traverse the tree from high to low addresses */
 568     while (Node && ((ULONG_PTR)Node->StartingAddress > LowestAddress))
 569     {
 570         /* Check if the memory area fits after the current node */
 571         if ((ULONG_PTR)Node->EndingAddress <= Candidate)
 572         {
 573             DPRINT("MmFindGapTopDown: %p\n", Candidate);
 574             return (PVOID)Candidate;
 575         }
 576
 577         /* Calculate next possible adress below this node */
 578         Candidate = ALIGN_DOWN_BY((ULONG_PTR)Node->StartingAddress - Length,
 579                                   Granularity);
 580
 581         /* Check for overflow. */
 582         if (Candidate > (ULONG_PTR)Node->StartingAddress)
 583             return NULL;
 584
 585         /* Go to the next lower node */
 586         Node = MmIteratePrevNode(Node);
 587     }
 588
 589     /* Check if the last candidate is inside the given range */
 590     if (Candidate >= LowestAddress)
 591     {
 592         DPRINT("MmFindGapTopDown: %p\n", Candidate);
 593         return (PVOID)Candidate;
 594     }
 595
 596     DPRINT("MmFindGapTopDown: 0\n");
 597     return NULL;
 598 }
 599
 600
 601 PVOID NTAPI
 602 MmFindGap(
 603    PMMSUPPORT AddressSpace,
 604    ULONG_PTR Length,
 605    ULONG_PTR Granularity,
 606    BOOLEAN TopDown)
 607 {
 608    if (TopDown)
 609       return MmFindGapTopDown(AddressSpace, Length, Granularity);
 610
 611    return MmFindGapBottomUp(AddressSpace, Length, Granularity);
 612 }
 613
 614 ULONG_PTR NTAPI
 615 MmFindGapAtAddress(
 616    PMMSUPPORT AddressSpace,
 617    PVOID Address)
 618 {
 619    PMEMORY_AREA Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 620    PMEMORY_AREA RightNeighbour = NULL;
 621    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 622    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 623                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 624
 625    Address = MM_ROUND_DOWN(Address, PAGE_SIZE);
 626
 627    if (LowestAddress < MmSystemRangeStart)
 628    {
 629       if (Address >= MmSystemRangeStart)
 630       {
 631          return 0;
 632       }
 633    }
 634    else
 635    {
 636       if (Address < LowestAddress)
 637       {
 638          return 0;
 639       }
 640    }
 641
 642    while (Node != NULL)
 643    {
 644       if (Address < Node->StartingAddress)
 645       {
 646          RightNeighbour = Node;
 647          Node = Node->LeftChild;
 648       }
 649       else if (Address >= Node->EndingAddress)
 650       {
 651          Node = Node->RightChild;
 652       }
 653       else
 654       {
 655          DPRINT("MmFindGapAtAddress: 0\n");
 656          return 0;
 657       }
 658    }
 659
 660    if (RightNeighbour)
 661    {
 662       DPRINT("MmFindGapAtAddress: %p [%p]\n", Address,
 663              (ULONG_PTR)RightNeighbour->StartingAddress - (ULONG_PTR)Address);
 664       return (ULONG_PTR)RightNeighbour->StartingAddress - (ULONG_PTR)Address;
 665    }
 666    else
 667    {
 668       DPRINT("MmFindGapAtAddress: %p [%p]\n", Address,
 669              (ULONG_PTR)HighestAddress - (ULONG_PTR)Address);
 670       return (ULONG_PTR)HighestAddress - (ULONG_PTR)Address;
 671    }
 672 }
 673
 674 VOID
 675 NTAPI
 676 MiRemoveNode(IN PMMADDRESS_NODE Node,
 677 IN PMM_AVL_TABLE Table);
 678
 679 #if DBG
 680
 681 static
 682 VOID
 683 MiRosCheckMemoryAreasRecursive(
 684    PMEMORY_AREA Node)
 685 {
 686     /* Check if the allocation is ok */
 687     ExpCheckPoolAllocation(Node, NonPagedPool, 'ERAM');
 688
 689     /* Check some fields */
 690     ASSERT(Node->Magic == 'erAM');
 691     ASSERT(PAGE_ALIGN(Node->StartingAddress) == Node->StartingAddress);
 692     ASSERT(Node->EndingAddress != NULL);
 693     ASSERT(PAGE_ALIGN(Node->EndingAddress) == Node->EndingAddress);
 694     ASSERT((ULONG_PTR)Node->StartingAddress < (ULONG_PTR)Node->EndingAddress);
 695     ASSERT((Node->Type == 0) ||
 696            (Node->Type == MEMORY_AREA_CACHE) ||
 697           // (Node->Type == MEMORY_AREA_CACHE_SEGMENT) ||
 698            (Node->Type == MEMORY_AREA_SECTION_VIEW) ||
 699            (Node->Type == MEMORY_AREA_OWNED_BY_ARM3) ||
 700            (Node->Type == (MEMORY_AREA_OWNED_BY_ARM3 | MEMORY_AREA_STATIC)));
 701
 702     /* Recursively check children */
 703     if (Node->LeftChild != NULL)
 704         MiRosCheckMemoryAreasRecursive(Node->LeftChild);
 705     if (Node->RightChild != NULL)
 706         MiRosCheckMemoryAreasRecursive(Node->RightChild);
 707 }
 708
 709 VOID
 710 NTAPI
 711 MiRosCheckMemoryAreas(
 712    PMMSUPPORT AddressSpace)
 713 {
 714     PMEMORY_AREA RootNode;
 715     PEPROCESS AddressSpaceOwner;
 716     BOOLEAN NeedReleaseLock;
 717
 718     NeedReleaseLock = FALSE;
 719
 720     /* Get the address space owner */
 721     AddressSpaceOwner = CONTAINING_RECORD(AddressSpace, EPROCESS, Vm);
 722
 723     /* Check if we already own the address space lock */
 724     if (AddressSpaceOwner->AddressCreationLock.Owner != KeGetCurrentThread())
 725     {
 726         /* We must own it! */
 727         MmLockAddressSpace(AddressSpace);
 728         NeedReleaseLock = TRUE;
 729     }
 730
 731     /* Check all memory areas */
 732     RootNode = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 733     MiRosCheckMemoryAreasRecursive(RootNode);
 734
 735     /* Release the lock, if we acquired it */
 736     if (NeedReleaseLock)
 737     {
 738         MmUnlockAddressSpace(AddressSpace);
 739     }
 740 }
 741
 742 extern KGUARDED_MUTEX PspActiveProcessMutex;
 743
 744 VOID
 745 NTAPI
 746 MiCheckAllProcessMemoryAreas(VOID)
 747 {
 748     PEPROCESS Process;
 749     PLIST_ENTRY Entry;
 750
 751     /* Acquire the Active Process Lock */
 752     KeAcquireGuardedMutex(&PspActiveProcessMutex);
 753
 754     /* Loop the process list */
 755     Entry = PsActiveProcessHead.Flink;
 756     while (Entry != &PsActiveProcessHead)
 757     {
 758         /* Get the process */
 759         Process = CONTAINING_RECORD(Entry, EPROCESS, ActiveProcessLinks);
 760
 761         /* Check memory areas */
 762         MiRosCheckMemoryAreas(&Process->Vm);
 763
 764         Entry = Entry->Flink;
 765     }
 766
 767     /* Release the lock */
 768     KeReleaseGuardedMutex(&PspActiveProcessMutex);
 769 }
 770
 771 #endif
 772
 773 /**
 774  * @name MmFreeMemoryArea
 775  *
 776  * Free an existing memory area.
 777  *
 778  * @param AddressSpace
 779  *        Address space to free the area from.
 780  * @param MemoryArea
 781  *        Memory area we're about to free.
 782  * @param FreePage
 783  *        Callback function for each freed page.
 784  * @param FreePageContext
 785  *        Context passed to the callback function.
 786  *
 787  * @return Status
 788  *
 789  * @remarks Lock the address space before calling this function.
 790  */
 791 VOID
 792 NTAPI
 793 MiDeletePte(IN PMMPTE PointerPte,
 794             IN PVOID VirtualAddress,
 795             IN PEPROCESS CurrentProcess,
 796             IN PMMPTE PrototypePte);
 797
 798 NTSTATUS NTAPI
 799 MmFreeMemoryArea(
 800    PMMSUPPORT AddressSpace,
 801    PMEMORY_AREA MemoryArea,
 802    PMM_FREE_PAGE_FUNC FreePage,
 803    PVOID FreePageContext)
 804 {
 805    PMEMORY_AREA *ParentReplace;
 806    ULONG_PTR Address;
 807    PVOID EndAddress;
 808
 809    /* Make sure we own the address space lock! */
 810    ASSERT(CONTAINING_RECORD(AddressSpace, EPROCESS, Vm)->AddressCreationLock.Owner == KeGetCurrentThread());
 811
 812     /* Check magic */
 813     ASSERT(MemoryArea->Magic == 'erAM');
 814
 815    if (MemoryArea->Type != MEMORY_AREA_OWNED_BY_ARM3)
 816    {
 817        PEPROCESS CurrentProcess = PsGetCurrentProcess();
 818        PEPROCESS Process = MmGetAddressSpaceOwner(AddressSpace);
 819
 820        if (Process != NULL &&
 821            Process != CurrentProcess)
 822        {
 823           KeAttachProcess(&Process->Pcb);
 824        }
 825
 826        EndAddress = MM_ROUND_UP(MemoryArea->EndingAddress, PAGE_SIZE);
 827        for (Address = (ULONG_PTR)MemoryArea->StartingAddress;
 828             Address < (ULONG_PTR)EndAddress;
 829             Address += PAGE_SIZE)
 830        {
 831              BOOLEAN Dirty = FALSE;
 832              SWAPENTRY SwapEntry = 0;
 833              PFN_NUMBER Page = 0;
 834
 835              if (MmIsPageSwapEntry(Process, (PVOID)Address))
 836              {
 837                 MmDeletePageFileMapping(Process, (PVOID)Address, &SwapEntry);
 838              }
 839              else
 840              {
 841                 MmDeleteVirtualMapping(Process, (PVOID)Address, FALSE, &Dirty, &Page);
 842              }
 843              if (FreePage != NULL)
 844              {
 845                 FreePage(FreePageContext, MemoryArea, (PVOID)Address,
 846                          Page, SwapEntry, (BOOLEAN)Dirty);
 847              }
 848 #if (_MI_PAGING_LEVELS == 2)
 849             /* Remove page table reference */
 850             ASSERT(KeGetCurrentIrql() <= APC_LEVEL);
 851             if ((SwapEntry || Page) && ((PVOID)Address < MmSystemRangeStart))
 852             {
 853                 ASSERT(AddressSpace != MmGetKernelAddressSpace());
 854                 if (MiQueryPageTableReferences((PVOID)Address) == 0)
 855                 {
 856                     /* No PTE relies on this PDE. Release it */
 857                     KIRQL OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 858                     PMMPDE PointerPde = MiAddressToPde(Address);
 859                     ASSERT(PointerPde->u.Hard.Valid == 1);
 860                     MiDeletePte(PointerPde, MiPdeToPte(PointerPde), Process, NULL);
 861                     ASSERT(PointerPde->u.Hard.Valid == 0);
 862                     KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
 863                 }
 864             }
 865 #endif
 866        }
 867
 868        if (Process != NULL &&
 869            Process != CurrentProcess)
 870        {
 871           KeDetachProcess();
 872        }
 873
 874        if (MemoryArea->Vad)
 875        {
 876            ASSERT(MemoryArea->EndingAddress < MmSystemRangeStart);
 877            ASSERT(MemoryArea->Type == MEMORY_AREA_SECTION_VIEW || MemoryArea->Type == MEMORY_AREA_CACHE);
 878
 879            /* MmCleanProcessAddressSpace might have removed it (and this would be MmDeleteProcessAdressSpace) */
 880            ASSERT(((PMMVAD)MemoryArea->Vad)->u.VadFlags.Spare != 0);
 881            if (((PMMVAD)MemoryArea->Vad)->u.VadFlags.Spare == 1)
 882            {
 883                MiRemoveNode(MemoryArea->Vad, &Process->VadRoot);
 884            }
 885
 886            ExFreePoolWithTag(MemoryArea->Vad, TAG_MVAD);
 887            MemoryArea->Vad = NULL;
 888        }
 889     }
 890
 891    /* Remove the tree item. */
 892    {
 893       if (MemoryArea->Parent != NULL)
 894       {
 895          if (MemoryArea->Parent->LeftChild == MemoryArea)
 896             ParentReplace = &MemoryArea->Parent->LeftChild;
 897          else
 898             ParentReplace = &MemoryArea->Parent->RightChild;
 899       }
 900       else
 901          ParentReplace = (PMEMORY_AREA*)&AddressSpace->WorkingSetExpansionLinks.Flink;
 902
 903       if (MemoryArea->RightChild == NULL)
 904       {
 905          *ParentReplace = MemoryArea->LeftChild;
 906          if (MemoryArea->LeftChild)
 907             MemoryArea->LeftChild->Parent = MemoryArea->Parent;
 908       }
 909       else
 910       {
 911          if (MemoryArea->RightChild->LeftChild == NULL)
 912          {
 913             MemoryArea->RightChild->LeftChild = MemoryArea->LeftChild;
 914             if (MemoryArea->LeftChild)
 915                MemoryArea->LeftChild->Parent = MemoryArea->RightChild;
 916
 917             *ParentReplace = MemoryArea->RightChild;
 918             MemoryArea->RightChild->Parent = MemoryArea->Parent;
 919          }
 920          else
 921          {
 922             PMEMORY_AREA LowestNode;
 923
 924             LowestNode = MemoryArea->RightChild->LeftChild;
 925             while (LowestNode->LeftChild != NULL)
 926                LowestNode = LowestNode->LeftChild;
 927
 928             LowestNode->Parent->LeftChild = LowestNode->RightChild;
 929             if (LowestNode->RightChild)
 930                LowestNode->RightChild->Parent = LowestNode->Parent;
 931
 932             LowestNode->LeftChild = MemoryArea->LeftChild;
 933             if (MemoryArea->LeftChild)
 934                MemoryArea->LeftChild->Parent = LowestNode;
 935
 936             LowestNode->RightChild = MemoryArea->RightChild;
 937             MemoryArea->RightChild->Parent = LowestNode;
 938
 939             *ParentReplace = LowestNode;
 940             LowestNode->Parent = MemoryArea->Parent;
 941          }
 942       }
 943    }
 944
 945    ExFreePoolWithTag(MemoryArea, TAG_MAREA);
 946
 947    DPRINT("MmFreeMemoryAreaByNode() succeeded\n");
 948
 949    return STATUS_SUCCESS;
 950 }
 951
 952 /**
 953  * @name MmCreateMemoryArea
 954  *
 955  * Create a memory area.
 956  *
 957  * @param AddressSpace
 958  *        Address space to create the area in.
 959  * @param Type
 960  *        Type of the memory area.
 961  * @param BaseAddress
 962  *        Base address for the memory area we're about the create. On
 963  *        input it contains either 0 (auto-assign address) or preferred
 964  *        address. On output it contains the starting address of the
 965  *        newly created area.
 966  * @param Length
 967  *        Length of the area to allocate.
 968  * @param Attributes
 969  *        Protection attributes for the memory area.
 970  * @param Result
 971  *        Receives a pointer to the memory area on successful exit.
 972  *
 973  * @return Status
 974  *
 975  * @remarks Lock the address space before calling this function.
 976  */
 977
 978 NTSTATUS NTAPI
 979 MmCreateMemoryArea(PMMSUPPORT AddressSpace,
 980                    ULONG Type,
 981                    PVOID *BaseAddress,
 982                    ULONG_PTR Length,
 983                    ULONG Protect,
 984                    PMEMORY_AREA *Result,
 985                    BOOLEAN FixedAddress,
 986                    ULONG AllocationFlags,
 987                    ULONG Granularity)
 988 {
 989    ULONG_PTR tmpLength;
 990    PMEMORY_AREA MemoryArea;
 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, Granularity);
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       tmpLength = Length + ((ULONG_PTR) *BaseAddress
1014                          - (ULONG_PTR) MM_ROUND_DOWN(*BaseAddress, Granularity));
1015       tmpLength = (ULONG_PTR)MM_ROUND_UP(tmpLength, Granularity);
1016       *BaseAddress = MM_ROUND_DOWN(*BaseAddress, Granularity);
1017
1018       if (!MmGetAddressSpaceOwner(AddressSpace) && *BaseAddress < MmSystemRangeStart)
1019       {
1020          return STATUS_ACCESS_VIOLATION;
1021       }
1022
1023       if (MmGetAddressSpaceOwner(AddressSpace) &&
1024           (ULONG_PTR)(*BaseAddress) + tmpLength > (ULONG_PTR)MmSystemRangeStart)
1025       {
1026          DPRINT("Memory area for user mode address space exceeds MmSystemRangeStart\n");
1027          return STATUS_ACCESS_VIOLATION;
1028       }
1029
1030       if (MmLocateMemoryAreaByRegion(AddressSpace,
1031                                      *BaseAddress,
1032                                      tmpLength) != NULL)
1033       {
1034          DPRINT("Memory area already occupied\n");
1035          return STATUS_CONFLICTING_ADDRESSES;
1036       }
1037    }
1038
1039     //
1040     // Is this a static memory area?
1041     //
1042     if (Type & MEMORY_AREA_STATIC)
1043     {
1044         //
1045         // Use the static array instead of the pool
1046         //
1047         ASSERT(MiStaticMemoryAreaCount < MI_STATIC_MEMORY_AREAS);
1048         MemoryArea = &MiStaticMemoryAreas[MiStaticMemoryAreaCount++];
1049         Type &= ~MEMORY_AREA_STATIC;
1050     }
1051     else
1052     {
1053         //
1054         // Allocate the memory area from nonpaged pool
1055         //
1056         MemoryArea = ExAllocatePoolWithTag(NonPagedPool,
1057                                            sizeof(MEMORY_AREA),
1058                                            TAG_MAREA);
1059     }
1060
1061    if (!MemoryArea)
1062    {
1063       DPRINT1("Not enough memory.\n");
1064       return STATUS_NO_MEMORY;
1065    }
1066
1067    RtlZeroMemory(MemoryArea, sizeof(MEMORY_AREA));
1068    MemoryArea->Type = Type;
1069    MemoryArea->StartingAddress = *BaseAddress;
1070    MemoryArea->EndingAddress = (PVOID)((ULONG_PTR)*BaseAddress + tmpLength);
1071    MemoryArea->Protect = Protect;
1072    MemoryArea->Flags = AllocationFlags;
1073    //MemoryArea->LockCount = 0;
1074    MemoryArea->Magic = 'erAM';
1075    MemoryArea->DeleteInProgress = FALSE;
1076
1077    MmInsertMemoryArea(AddressSpace, MemoryArea);
1078
1079    *Result = MemoryArea;
1080
1081    DPRINT("MmCreateMemoryArea() succeeded (%p)\n", *BaseAddress);
1082    return STATUS_SUCCESS;
1083 }
1084
1085 VOID NTAPI
1086 MmMapMemoryArea(PVOID BaseAddress,
1087                 SIZE_T Length,
1088                 ULONG Consumer,
1089                 ULONG Protection)
1090 {
1091    ULONG i;
1092    NTSTATUS Status;
1093
1094    ASSERT(((ULONG_PTR)BaseAddress % PAGE_SIZE) == 0);
1095
1096    for (i = 0; i < PAGE_ROUND_UP(Length) / PAGE_SIZE; i++)
1097    {
1098       PFN_NUMBER Page;
1099
1100       Status = MmRequestPageMemoryConsumer(Consumer, TRUE, &Page);
1101       if (!NT_SUCCESS(Status))
1102       {
1103          DPRINT1("Unable to allocate page\n");
1104          KeBugCheck(MEMORY_MANAGEMENT);
1105       }
1106       Status = MmCreateVirtualMapping (NULL,
1107                                        (PVOID)((ULONG_PTR)BaseAddress + (i * PAGE_SIZE)),
1108                                        Protection,
1109                                        &Page,
1110                                        1);
1111       if (!NT_SUCCESS(Status))
1112       {
1113          DPRINT1("Unable to create virtual mapping\n");
1114          KeBugCheck(MEMORY_MANAGEMENT);
1115       }
1116    }
1117 }
1118
1119 VOID
1120 NTAPI
1121 MmDeleteProcessAddressSpace2(IN PEPROCESS Process);
1122
1123 NTSTATUS
1124 NTAPI
1125 MmDeleteProcessAddressSpace(PEPROCESS Process)
1126 {
1127    PVOID Address;
1128    PMEMORY_AREA MemoryArea;
1129
1130    DPRINT("MmDeleteProcessAddressSpace(Process %p (%s))\n", Process,
1131           Process->ImageFileName);
1132
1133 #ifndef _M_AMD64
1134    RemoveEntryList(&Process->MmProcessLinks);
1135 #endif
1136    MmLockAddressSpace(&Process->Vm);
1137
1138    while ((MemoryArea = (PMEMORY_AREA)Process->Vm.WorkingSetExpansionLinks.Flink) != NULL)
1139    {
1140       switch (MemoryArea->Type)
1141       {
1142          case MEMORY_AREA_SECTION_VIEW:
1143              Address = (PVOID)MemoryArea->StartingAddress;
1144              MmUnlockAddressSpace(&Process->Vm);
1145              MmUnmapViewOfSection(Process, Address);
1146              MmLockAddressSpace(&Process->Vm);
1147              break;
1148
1149          case MEMORY_AREA_CACHE:
1150              Address = (PVOID)MemoryArea->StartingAddress;
1151              MmUnlockAddressSpace(&Process->Vm);
1152              MmUnmapViewOfCacheSegment(&Process->Vm, Address);
1153              MmLockAddressSpace(&Process->Vm);
1154              break;
1155
1156          case MEMORY_AREA_OWNED_BY_ARM3:
1157              MmFreeMemoryArea(&Process->Vm,
1158                               MemoryArea,
1159                               NULL,
1160                               NULL);
1161              break;
1162
1163          default:
1164             KeBugCheck(MEMORY_MANAGEMENT);
1165       }
1166    }
1167
1168 #if (_MI_PAGING_LEVELS == 2)
1169     {
1170         KIRQL OldIrql;
1171         PMMPDE pointerPde;
1172         /* Attach to Process */
1173         KeAttachProcess(&Process->Pcb);
1174
1175         /* Acquire PFN lock */
1176         OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
1177
1178         for (Address = MI_LOWEST_VAD_ADDRESS;
1179              Address < MM_HIGHEST_VAD_ADDRESS;
1180              Address =(PVOID)((ULONG_PTR)Address + (PAGE_SIZE * PTE_COUNT)))
1181         {
1182             /* At this point all references should be dead */
1183             if (MiQueryPageTableReferences(Address) != 0)
1184             {
1185                 DPRINT1("Process %p, Address %p, UsedPageTableEntries %lu\n",
1186                         Process,
1187                         Address,
1188                         MiQueryPageTableReferences(Address));
1189                 ASSERT(MiQueryPageTableReferences(Address) == 0);
1190             }
1191             pointerPde = MiAddressToPde(Address);
1192             /* Unlike in ARM3, we don't necesarrily free the PDE page as soon as reference reaches 0,
1193              * so we must clean up a bit when process closes */
1194             if (pointerPde->u.Hard.Valid)
1195                 MiDeletePte(pointerPde, MiPdeToPte(pointerPde), Process, NULL);
1196             ASSERT(pointerPde->u.Hard.Valid == 0);
1197         }
1198         /* Release lock */
1199         KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
1200
1201         /* Detach */
1202         KeDetachProcess();
1203     }
1204 #endif
1205
1206    MmUnlockAddressSpace(&Process->Vm);
1207
1208    DPRINT("Finished MmReleaseMmInfo()\n");
1209    MmDeleteProcessAddressSpace2(Process);
1210    return(STATUS_SUCCESS);
1211 }
1212
1213 /* EOF */