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 <debug.h>
  47
  48 MEMORY_AREA MiStaticMemoryAreas[MI_STATIC_MEMORY_AREAS];
  49 ULONG MiStaticMemoryAreaCount;
  50
  51 /* FUNCTIONS *****************************************************************/
  52
  53 /**
  54  * @name MmIterateFirstNode
  55  *
  56  * @param Node
  57  *        Head node of the MEMORY_AREA tree.
  58  *
  59  * @return The leftmost MEMORY_AREA node (ie. the one with lowest
  60  *         address)
  61  */
  62
  63 static PMEMORY_AREA MmIterateFirstNode(PMEMORY_AREA Node)
  64 {
  65    while (Node->LeftChild != NULL)
  66       Node = Node->LeftChild;
  67
  68    return Node;
  69 }
  70
  71 /**
  72  * @name MmIterateNextNode
  73  *
  74  * @param Node
  75  *        Current node in the tree.
  76  *
  77  * @return Next node in the tree (sorted by address).
  78  */
  79
  80 static PMEMORY_AREA MmIterateNextNode(PMEMORY_AREA Node)
  81 {
  82    if (Node->RightChild != NULL)
  83    {
  84       Node = Node->RightChild;
  85       while (Node->LeftChild != NULL)
  86          Node = Node->LeftChild;
  87    }
  88    else
  89    {
  90       PMEMORY_AREA TempNode = NULL;
  91
  92       do
  93       {
  94          /* Check if we're at the end of tree. */
  95          if (Node->Parent == NULL)
  96             return NULL;
  97
  98          TempNode = Node;
  99          Node = Node->Parent;
 100       }
 101       while (TempNode == Node->RightChild);
 102    }
 103    return Node;
 104 }
 105
 106 /**
 107  * @name MmIterateLastNode
 108  *
 109  * @param Node
 110  *        Head node of the MEMORY_AREA tree.
 111  *
 112  * @return The rightmost MEMORY_AREA node (ie. the one with highest
 113  *         address)
 114  */
 115
 116 static PMEMORY_AREA MmIterateLastNode(PMEMORY_AREA Node)
 117 {
 118    while (Node->RightChild != NULL)
 119       Node = Node->RightChild;
 120
 121    return Node;
 122 }
 123
 124 /**
 125  * @name MmIteratePreviousNode
 126  *
 127  * @param Node
 128  *        Current node in the tree.
 129  *
 130  * @return Previous node in the tree (sorted by address).
 131  */
 132
 133 static PMEMORY_AREA MmIteratePrevNode(PMEMORY_AREA Node)
 134 {
 135    if (Node->LeftChild != NULL)
 136    {
 137       Node = Node->LeftChild;
 138       while (Node->RightChild != NULL)
 139          Node = Node->RightChild;
 140    }
 141    else
 142    {
 143       PMEMORY_AREA TempNode = NULL;
 144
 145       do
 146       {
 147          /* Check if we're at the end of tree. */
 148          if (Node->Parent == NULL)
 149             return NULL;
 150
 151          TempNode = Node;
 152          Node = Node->Parent;
 153       }
 154       while (TempNode == Node->LeftChild);
 155    }
 156    return Node;
 157 }
 158
 159 PMEMORY_AREA NTAPI
 160 MmLocateMemoryAreaByAddress(
 161    PMMSUPPORT AddressSpace,
 162    PVOID Address)
 163 {
 164    PMEMORY_AREA Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 165
 166    DPRINT("MmLocateMemoryAreaByAddress(AddressSpace %p, Address %p)\n",
 167            AddressSpace, Address);
 168
 169    while (Node != NULL)
 170    {
 171       if (Address < Node->StartingAddress)
 172          Node = Node->LeftChild;
 173       else if (Address >= Node->EndingAddress)
 174          Node = Node->RightChild;
 175       else
 176       {
 177          DPRINT("MmLocateMemoryAreaByAddress(%p): %p [%p - %p]\n",
 178                 Address, Node, Node->StartingAddress, Node->EndingAddress);
 179          return Node;
 180       }
 181    }
 182
 183    DPRINT("MmLocateMemoryAreaByAddress(%p): 0\n", Address);
 184    return NULL;
 185 }
 186
 187 PMEMORY_AREA NTAPI
 188 MmLocateMemoryAreaByRegion(
 189    PMMSUPPORT AddressSpace,
 190    PVOID Address,
 191    ULONG_PTR Length)
 192 {
 193    PMEMORY_AREA Node;
 194    PVOID Extent = (PVOID)((ULONG_PTR)Address + Length);
 195
 196    /* Special case for empty tree. */
 197    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 198       return NULL;
 199
 200    /* Traverse the tree from left to right. */
 201    for (Node = MmIterateFirstNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 202         Node != NULL;
 203         Node = MmIterateNextNode(Node))
 204    {
 205       if (Node->StartingAddress >= Address &&
 206           Node->StartingAddress < Extent)
 207       {
 208          DPRINT("MmLocateMemoryAreaByRegion(%p - %p): %p - %p\n",
 209                 Address, (ULONG_PTR)Address + Length, Node->StartingAddress,
 210                 Node->EndingAddress);
 211          return Node;
 212       }
 213       if (Node->EndingAddress > Address &&
 214           Node->EndingAddress < Extent)
 215       {
 216          DPRINT("MmLocateMemoryAreaByRegion(%p - %p): %p - %p\n",
 217                 Address, (ULONG_PTR)Address + Length, Node->StartingAddress,
 218                 Node->EndingAddress);
 219          return Node;
 220       }
 221       if (Node->StartingAddress <= Address &&
 222           Node->EndingAddress >= Extent)
 223       {
 224          DPRINT("MmLocateMemoryAreaByRegion(%p - %p): %p - %p\n",
 225                 Address, (ULONG_PTR)Address + Length, Node->StartingAddress,
 226                 Node->EndingAddress);
 227          return Node;
 228       }
 229       if (Node->StartingAddress >= Extent)
 230       {
 231          DPRINT("Finished MmLocateMemoryAreaByRegion() = NULL\n");
 232          return NULL;
 233       }
 234    }
 235
 236    return NULL;
 237 }
 238
 239 /**
 240  * @name MmCompressHelper
 241  *
 242  * This is helper of MmRebalanceTree. Performs a compression transformation
 243  * count times, starting at root.
 244  */
 245
 246 static VOID
 247 MmCompressHelper(
 248    PMMSUPPORT AddressSpace,
 249    ULONG Count)
 250 {
 251    PMEMORY_AREA Root = NULL;
 252    PMEMORY_AREA Red = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 253    PMEMORY_AREA Black = Red->LeftChild;
 254
 255    while (Count--)
 256    {
 257       if (Root)
 258          Root->LeftChild = Black;
 259       else
 260          AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)Black;
 261       Black->Parent = Root;
 262       Red->LeftChild = Black->RightChild;
 263       if (Black->RightChild)
 264          Black->RightChild->Parent = Red;
 265       Black->RightChild = Red;
 266       Red->Parent = Black;
 267       Root = Black;
 268
 269       if (Count)
 270       {
 271          Red = Root->LeftChild;
 272          Black = Red->LeftChild;
 273       }
 274    }
 275 }
 276
 277 /**
 278  * @name MmRebalanceTree
 279  *
 280  * Rebalance a memory area tree using the Tree->Vine->Balanced Tree
 281  * method described in libavl documentation in chapter 4.12.
 282  * (http://www.stanford.edu/~blp/avl/libavl.html/)
 283  */
 284
 285 static VOID
 286 MmRebalanceTree(
 287    PMMSUPPORT AddressSpace)
 288 {
 289    PMEMORY_AREA PreviousNode;
 290    PMEMORY_AREA CurrentNode;
 291    PMEMORY_AREA TempNode;
 292    ULONG NodeCount = 0;
 293    ULONG Vine;   /* Number of nodes in main vine. */
 294    ULONG Leaves; /* Nodes in incomplete bottom level, if any. */
 295    INT Height;   /* Height of produced balanced tree. */
 296
 297    /* Transform the tree into Vine. */
 298
 299    PreviousNode = NULL;
 300    CurrentNode = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 301    while (CurrentNode != NULL)
 302    {
 303       if (CurrentNode->RightChild == NULL)
 304       {
 305          PreviousNode = CurrentNode;
 306          CurrentNode = CurrentNode->LeftChild;
 307          NodeCount++;
 308       }
 309       else
 310       {
 311          TempNode = CurrentNode->RightChild;
 312
 313          CurrentNode->RightChild = TempNode->LeftChild;
 314          if (TempNode->LeftChild)
 315             TempNode->LeftChild->Parent = CurrentNode;
 316
 317          TempNode->LeftChild = CurrentNode;
 318          CurrentNode->Parent = TempNode;
 319
 320          CurrentNode = TempNode;
 321
 322          if (PreviousNode != NULL)
 323             PreviousNode->LeftChild = TempNode;
 324          else
 325             AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)TempNode;
 326          TempNode->Parent = PreviousNode;
 327       }
 328    }
 329
 330    /* Transform Vine back into a balanced tree. */
 331
 332    Leaves = NodeCount + 1;
 333    for (;;)
 334    {
 335       ULONG Next = Leaves & (Leaves - 1);
 336       if (Next == 0)
 337          break;
 338       Leaves = Next;
 339    }
 340    Leaves = NodeCount + 1 - Leaves;
 341
 342    MmCompressHelper(AddressSpace, Leaves);
 343
 344    Vine = NodeCount - Leaves;
 345    Height = 1 + (Leaves > 0);
 346    while (Vine > 1)
 347    {
 348       MmCompressHelper(AddressSpace, Vine / 2);
 349       Vine /= 2;
 350       Height++;
 351    }
 352 }
 353
 354 VOID
 355 NTAPI
 356 MiInsertVad(IN PMMVAD Vad,
 357 IN PEPROCESS Process);
 358
 359 ULONG
 360 NTAPI
 361 MiMakeProtectionMask(
 362     IN ULONG Protect
 363 );
 364
 365 static VOID
 366 MmInsertMemoryArea(
 367    PMMSUPPORT AddressSpace,
 368    PMEMORY_AREA marea)
 369 {
 370    PMEMORY_AREA Node;
 371    PMEMORY_AREA PreviousNode;
 372    ULONG Depth = 0;
 373
 374    /* Build a lame VAD if this is a user-space allocation */
 375    if ((marea->EndingAddress < MmSystemRangeStart) && (marea->Type != MEMORY_AREA_OWNED_BY_ARM3))
 376    {
 377        PMMVAD Vad;
 378
 379        ASSERT(marea->Type == MEMORY_AREA_VIRTUAL_MEMORY || marea->Type == MEMORY_AREA_SECTION_VIEW);
 380        Vad = ExAllocatePoolWithTag(NonPagedPool, sizeof(MMVAD), 'Fake');
 381        ASSERT(Vad);
 382        RtlZeroMemory(Vad, sizeof(MMVAD));
 383        Vad->StartingVpn = PAGE_ROUND_DOWN(marea->StartingAddress) >> PAGE_SHIFT;
 384        /*
 385         * For some strange reason, it is perfectly valid to create a MAREA from 0x1000 to... 0x1000.
 386         * In a normal OS/Memory Manager, this would be retarded, but ReactOS allows this (how it works
 387         * I don't even want to know).
 388         */
 389         if (marea->EndingAddress != marea->StartingAddress)
 390         {
 391             Vad->EndingVpn = PAGE_ROUND_DOWN((ULONG_PTR)marea->EndingAddress - 1) >> PAGE_SHIFT;
 392         }
 393         else
 394         {
 395             Vad->EndingVpn = Vad->StartingVpn;
 396         }
 397        Vad->u.VadFlags.Spare = 1;
 398        Vad->u.VadFlags.PrivateMemory = 1;
 399        Vad->u.VadFlags.Protection = MiMakeProtectionMask(marea->Protect);
 400        MiInsertVad(Vad, MmGetAddressSpaceOwner(AddressSpace));
 401        marea->Vad = Vad;
 402    }
 403    else
 404    {
 405        marea->Vad = NULL;
 406    }
 407
 408    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 409    {
 410       AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)marea;
 411       marea->LeftChild = marea->RightChild = marea->Parent = NULL;
 412       return;
 413    }
 414
 415    Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 416    do
 417    {
 418       DPRINT("marea->EndingAddress: %p Node->StartingAddress: %p\n",
 419              marea->EndingAddress, Node->StartingAddress);
 420       DPRINT("marea->StartingAddress: %p Node->EndingAddress: %p\n",
 421              marea->StartingAddress, Node->EndingAddress);
 422       ASSERT(marea->EndingAddress <= Node->StartingAddress ||
 423              marea->StartingAddress >= Node->EndingAddress);
 424       ASSERT(marea->StartingAddress != Node->StartingAddress);
 425
 426       PreviousNode = Node;
 427
 428       if (marea->StartingAddress < Node->StartingAddress)
 429          Node = Node->LeftChild;
 430       else
 431          Node = Node->RightChild;
 432
 433       if (Node)
 434       {
 435          Depth++;
 436          if (Depth == 22)
 437          {
 438             MmRebalanceTree(AddressSpace);
 439             PreviousNode = Node->Parent;
 440          }
 441       }
 442    }
 443    while (Node != NULL);
 444
 445    marea->LeftChild = marea->RightChild = NULL;
 446    marea->Parent = PreviousNode;
 447    if (marea->StartingAddress < PreviousNode->StartingAddress)
 448       PreviousNode->LeftChild = marea;
 449    else
 450       PreviousNode->RightChild = marea;
 451 }
 452
 453 static PVOID
 454 MmFindGapBottomUp(
 455    PMMSUPPORT AddressSpace,
 456    ULONG_PTR Length,
 457    ULONG_PTR Granularity)
 458 {
 459    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 460    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 461                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 462    PVOID AlignedAddress;
 463    PMEMORY_AREA Node;
 464    PMEMORY_AREA FirstNode;
 465    PMEMORY_AREA PreviousNode;
 466
 467    DPRINT("LowestAddress: %p HighestAddress: %p\n",
 468           LowestAddress, HighestAddress);
 469
 470    AlignedAddress = MM_ROUND_UP(LowestAddress, Granularity);
 471
 472    /* Special case for empty tree. */
 473    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 474    {
 475       if ((ULONG_PTR)HighestAddress - (ULONG_PTR)AlignedAddress >= Length)
 476       {
 477          DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 478          return AlignedAddress;
 479       }
 480       DPRINT("MmFindGapBottomUp: 0\n");
 481       return 0;
 482    }
 483
 484    /* Go to the node with lowest address in the tree. */
 485    FirstNode = Node = MmIterateFirstNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 486
 487    /* Traverse the tree from left to right. */
 488    PreviousNode = Node;
 489    for (;;)
 490    {
 491       Node = MmIterateNextNode(Node);
 492       if (Node == NULL)
 493          break;
 494
 495       AlignedAddress = MM_ROUND_UP(PreviousNode->EndingAddress, Granularity);
 496       if (Node->StartingAddress > AlignedAddress &&
 497           (ULONG_PTR)Node->StartingAddress - (ULONG_PTR)AlignedAddress >= Length)
 498       {
 499          DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 500          return AlignedAddress;
 501       }
 502
 503       PreviousNode = Node;
 504    }
 505
 506    /* Check if there is enough space after the last memory area. */
 507    AlignedAddress = MM_ROUND_UP(PreviousNode->EndingAddress, Granularity);
 508    if ((ULONG_PTR)HighestAddress > (ULONG_PTR)AlignedAddress &&
 509        (ULONG_PTR)HighestAddress - (ULONG_PTR)AlignedAddress >= Length)
 510    {
 511       DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 512       return AlignedAddress;
 513    }
 514
 515    /* Check if there is enough space before the first memory area. */
 516    AlignedAddress = MM_ROUND_UP(LowestAddress, Granularity);
 517    if (FirstNode->StartingAddress > AlignedAddress &&
 518        (ULONG_PTR)FirstNode->StartingAddress - (ULONG_PTR)AlignedAddress >= Length)
 519    {
 520       DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 521       return AlignedAddress;
 522    }
 523
 524    DPRINT("MmFindGapBottomUp: 0\n");
 525    return 0;
 526 }
 527
 528
 529 static PVOID
 530 MmFindGapTopDown(
 531    PMMSUPPORT AddressSpace,
 532    ULONG_PTR Length,
 533    ULONG_PTR Granularity)
 534 {
 535    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 536    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 537                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 538    PVOID AlignedAddress;
 539    PMEMORY_AREA Node;
 540    PMEMORY_AREA PreviousNode;
 541
 542    DPRINT("LowestAddress: %p HighestAddress: %p\n",
 543           LowestAddress, HighestAddress);
 544
 545    AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)HighestAddress - Length + 1, Granularity);
 546
 547    /* Check for overflow. */
 548    if (AlignedAddress > HighestAddress)
 549       return NULL;
 550
 551    /* Special case for empty tree. */
 552    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 553    {
 554       if (AlignedAddress >= LowestAddress)
 555       {
 556          DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 557          return AlignedAddress;
 558       }
 559       DPRINT("MmFindGapTopDown: 0\n");
 560       return 0;
 561    }
 562
 563    /* Go to the node with highest address in the tree. */
 564    Node = MmIterateLastNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 565
 566    /* Check if there is enough space after the last memory area. */
 567    if (Node->EndingAddress <= AlignedAddress)
 568    {
 569       DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 570       return AlignedAddress;
 571    }
 572
 573    /* Traverse the tree from left to right. */
 574    PreviousNode = Node;
 575    for (;;)
 576    {
 577       Node = MmIteratePrevNode(Node);
 578       if (Node == NULL)
 579          break;
 580
 581       AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)PreviousNode->StartingAddress - Length + 1, Granularity);
 582
 583       /* Check for overflow. */
 584       if (AlignedAddress > PreviousNode->StartingAddress)
 585          return NULL;
 586
 587       if (Node->EndingAddress <= AlignedAddress)
 588       {
 589          DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 590          return AlignedAddress;
 591       }
 592
 593       PreviousNode = Node;
 594    }
 595
 596    AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)PreviousNode->StartingAddress - Length + 1, Granularity);
 597
 598    /* Check for overflow. */
 599    if (AlignedAddress > PreviousNode->StartingAddress)
 600       return NULL;
 601
 602    if (AlignedAddress >= LowestAddress)
 603    {
 604       DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 605       return AlignedAddress;
 606    }
 607
 608    DPRINT("MmFindGapTopDown: 0\n");
 609    return 0;
 610 }
 611
 612
 613 PVOID NTAPI
 614 MmFindGap(
 615    PMMSUPPORT AddressSpace,
 616    ULONG_PTR Length,
 617    ULONG_PTR Granularity,
 618    BOOLEAN TopDown)
 619 {
 620    if (TopDown)
 621       return MmFindGapTopDown(AddressSpace, Length, Granularity);
 622
 623    return MmFindGapBottomUp(AddressSpace, Length, Granularity);
 624 }
 625
 626 ULONG_PTR NTAPI
 627 MmFindGapAtAddress(
 628    PMMSUPPORT AddressSpace,
 629    PVOID Address)
 630 {
 631    PMEMORY_AREA Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 632    PMEMORY_AREA RightNeighbour = NULL;
 633    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 634    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 635                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 636
 637    Address = MM_ROUND_DOWN(Address, PAGE_SIZE);
 638
 639    if (LowestAddress < MmSystemRangeStart)
 640    {
 641       if (Address >= MmSystemRangeStart)
 642       {
 643          return 0;
 644       }
 645    }
 646    else
 647    {
 648       if (Address < LowestAddress)
 649       {
 650          return 0;
 651       }
 652    }
 653
 654    while (Node != NULL)
 655    {
 656       if (Address < Node->StartingAddress)
 657       {
 658          RightNeighbour = Node;
 659          Node = Node->LeftChild;
 660       }
 661       else if (Address >= Node->EndingAddress)
 662       {
 663          Node = Node->RightChild;
 664       }
 665       else
 666       {
 667          DPRINT("MmFindGapAtAddress: 0\n");
 668          return 0;
 669       }
 670    }
 671
 672    if (RightNeighbour)
 673    {
 674       DPRINT("MmFindGapAtAddress: %p [%p]\n", Address,
 675              (ULONG_PTR)RightNeighbour->StartingAddress - (ULONG_PTR)Address);
 676       return (ULONG_PTR)RightNeighbour->StartingAddress - (ULONG_PTR)Address;
 677    }
 678    else
 679    {
 680       DPRINT("MmFindGapAtAddress: %p [%p]\n", Address,
 681              (ULONG_PTR)HighestAddress - (ULONG_PTR)Address);
 682       return (ULONG_PTR)HighestAddress - (ULONG_PTR)Address;
 683    }
 684 }
 685
 686 VOID
 687 NTAPI
 688 MiRemoveNode(IN PMMADDRESS_NODE Node,
 689 IN PMM_AVL_TABLE Table);
 690
 691 /**
 692  * @name MmFreeMemoryArea
 693  *
 694  * Free an existing memory area.
 695  *
 696  * @param AddressSpace
 697  *        Address space to free the area from.
 698  * @param MemoryArea
 699  *        Memory area we're about to free.
 700  * @param FreePage
 701  *        Callback function for each freed page.
 702  * @param FreePageContext
 703  *        Context passed to the callback function.
 704  *
 705  * @return Status
 706  *
 707  * @remarks Lock the address space before calling this function.
 708  */
 709
 710 NTSTATUS NTAPI
 711 MmFreeMemoryArea(
 712    PMMSUPPORT AddressSpace,
 713    PMEMORY_AREA MemoryArea,
 714    PMM_FREE_PAGE_FUNC FreePage,
 715    PVOID FreePageContext)
 716 {
 717    PMEMORY_AREA *ParentReplace;
 718    ULONG_PTR Address;
 719    PVOID EndAddress;
 720
 721    if (MemoryArea->Type != MEMORY_AREA_OWNED_BY_ARM3)
 722    {
 723        PEPROCESS CurrentProcess = PsGetCurrentProcess();
 724        PEPROCESS Process = MmGetAddressSpaceOwner(AddressSpace);
 725
 726        if (Process != NULL &&
 727            Process != CurrentProcess)
 728        {
 729           KeAttachProcess(&Process->Pcb);
 730        }
 731
 732        EndAddress = MM_ROUND_UP(MemoryArea->EndingAddress, PAGE_SIZE);
 733        for (Address = (ULONG_PTR)MemoryArea->StartingAddress;
 734             Address < (ULONG_PTR)EndAddress;
 735             Address += PAGE_SIZE)
 736        {
 737              BOOLEAN Dirty = FALSE;
 738              SWAPENTRY SwapEntry = 0;
 739              PFN_NUMBER Page = 0;
 740
 741              if (MmIsPageSwapEntry(Process, (PVOID)Address))
 742              {
 743                 MmDeletePageFileMapping(Process, (PVOID)Address, &SwapEntry);
 744              }
 745              else
 746              {
 747                 MmDeleteVirtualMapping(Process, (PVOID)Address, FALSE, &Dirty, &Page);
 748              }
 749              if (FreePage != NULL)
 750              {
 751                 FreePage(FreePageContext, MemoryArea, (PVOID)Address,
 752                          Page, SwapEntry, (BOOLEAN)Dirty);
 753              }
 754        }
 755
 756        if (Process != NULL &&
 757            Process != CurrentProcess)
 758        {
 759           KeDetachProcess();
 760        }
 761
 762        if (MemoryArea->Vad)
 763        {
 764            ASSERT(MemoryArea->EndingAddress < MmSystemRangeStart);
 765            ASSERT(MemoryArea->Type == MEMORY_AREA_VIRTUAL_MEMORY || MemoryArea->Type == MEMORY_AREA_SECTION_VIEW);
 766
 767            /* MmCleanProcessAddressSpace might have removed it (and this would be MmDeleteProcessAdressSpace) */
 768            ASSERT(((PMMVAD)MemoryArea->Vad)->u.VadFlags.Spare != 0);
 769            if (((PMMVAD)MemoryArea->Vad)->u.VadFlags.Spare == 1)
 770            {
 771                MiRemoveNode(MemoryArea->Vad, &Process->VadRoot);
 772            }
 773
 774            ExFreePool(MemoryArea->Vad);
 775            MemoryArea->Vad = NULL;
 776        }
 777     }
 778
 779    /* Remove the tree item. */
 780    {
 781       if (MemoryArea->Parent != NULL)
 782       {
 783          if (MemoryArea->Parent->LeftChild == MemoryArea)
 784             ParentReplace = &MemoryArea->Parent->LeftChild;
 785          else
 786             ParentReplace = &MemoryArea->Parent->RightChild;
 787       }
 788       else
 789          ParentReplace = (PMEMORY_AREA*)&AddressSpace->WorkingSetExpansionLinks.Flink;
 790
 791       if (MemoryArea->RightChild == NULL)
 792       {
 793          *ParentReplace = MemoryArea->LeftChild;
 794          if (MemoryArea->LeftChild)
 795             MemoryArea->LeftChild->Parent = MemoryArea->Parent;
 796       }
 797       else
 798       {
 799          if (MemoryArea->RightChild->LeftChild == NULL)
 800          {
 801             MemoryArea->RightChild->LeftChild = MemoryArea->LeftChild;
 802             if (MemoryArea->LeftChild)
 803                MemoryArea->LeftChild->Parent = MemoryArea->RightChild;
 804
 805             *ParentReplace = MemoryArea->RightChild;
 806             MemoryArea->RightChild->Parent = MemoryArea->Parent;
 807          }
 808          else
 809          {
 810             PMEMORY_AREA LowestNode;
 811
 812             LowestNode = MemoryArea->RightChild->LeftChild;
 813             while (LowestNode->LeftChild != NULL)
 814                LowestNode = LowestNode->LeftChild;
 815
 816             LowestNode->Parent->LeftChild = LowestNode->RightChild;
 817             if (LowestNode->RightChild)
 818                LowestNode->RightChild->Parent = LowestNode->Parent;
 819
 820             LowestNode->LeftChild = MemoryArea->LeftChild;
 821             if (MemoryArea->LeftChild)
 822                MemoryArea->LeftChild->Parent = LowestNode;
 823
 824             LowestNode->RightChild = MemoryArea->RightChild;
 825             MemoryArea->RightChild->Parent = LowestNode;
 826
 827             *ParentReplace = LowestNode;
 828             LowestNode->Parent = MemoryArea->Parent;
 829          }
 830       }
 831    }
 832
 833    ExFreePoolWithTag(MemoryArea, TAG_MAREA);
 834
 835    DPRINT("MmFreeMemoryAreaByNode() succeeded\n");
 836
 837    return STATUS_SUCCESS;
 838 }
 839
 840 /**
 841  * @name MmCreateMemoryArea
 842  *
 843  * Create a memory area.
 844  *
 845  * @param AddressSpace
 846  *        Address space to create the area in.
 847  * @param Type
 848  *        Type of the memory area.
 849  * @param BaseAddress
 850  *        Base address for the memory area we're about the create. On
 851  *        input it contains either 0 (auto-assign address) or preferred
 852  *        address. On output it contains the starting address of the
 853  *        newly created area.
 854  * @param Length
 855  *        Length of the area to allocate.
 856  * @param Attributes
 857  *        Protection attributes for the memory area.
 858  * @param Result
 859  *        Receives a pointer to the memory area on successful exit.
 860  *
 861  * @return Status
 862  *
 863  * @remarks Lock the address space before calling this function.
 864  */
 865
 866 NTSTATUS NTAPI
 867 MmCreateMemoryArea(PMMSUPPORT AddressSpace,
 868                    ULONG Type,
 869                    PVOID *BaseAddress,
 870                    ULONG_PTR Length,
 871                    ULONG Protect,
 872                    PMEMORY_AREA *Result,
 873                    BOOLEAN FixedAddress,
 874                    ULONG AllocationFlags,
 875                    PHYSICAL_ADDRESS BoundaryAddressMultiple)
 876 {
 877    PVOID EndAddress;
 878    ULONG Granularity;
 879    ULONG tmpLength;
 880    PMEMORY_AREA MemoryArea;
 881
 882    DPRINT("MmCreateMemoryArea(Type %d, BaseAddress %p, "
 883           "*BaseAddress %p, Length %p, AllocationFlags %x, "
 884           "FixedAddress %x, Result %p)\n",
 885           Type, BaseAddress, *BaseAddress, Length, AllocationFlags,
 886           FixedAddress, Result);
 887
 888    Granularity = (MEMORY_AREA_VIRTUAL_MEMORY == Type ? MM_VIRTMEM_GRANULARITY : PAGE_SIZE);
 889    if ((*BaseAddress) == 0 && !FixedAddress)
 890    {
 891       tmpLength = PAGE_ROUND_UP(Length);
 892       *BaseAddress = MmFindGap(AddressSpace,
 893                                tmpLength,
 894                                Granularity,
 895                                (AllocationFlags & MEM_TOP_DOWN) == MEM_TOP_DOWN);
 896       if ((*BaseAddress) == 0)
 897       {
 898          DPRINT("No suitable gap\n");
 899          return STATUS_NO_MEMORY;
 900       }
 901    }
 902    else
 903    {
 904       tmpLength = Length + ((ULONG_PTR) *BaseAddress
 905                          - (ULONG_PTR) MM_ROUND_DOWN(*BaseAddress, Granularity));
 906       *BaseAddress = MM_ROUND_DOWN(*BaseAddress, Granularity);
 907
 908       if (!MmGetAddressSpaceOwner(AddressSpace) && *BaseAddress < MmSystemRangeStart)
 909       {
 910          return STATUS_ACCESS_VIOLATION;
 911       }
 912
 913       if (MmGetAddressSpaceOwner(AddressSpace) &&
 914           (ULONG_PTR)(*BaseAddress) + tmpLength > (ULONG_PTR)MmSystemRangeStart)
 915       {
 916          return STATUS_ACCESS_VIOLATION;
 917       }
 918
 919       if (BoundaryAddressMultiple.QuadPart != 0)
 920       {
 921          EndAddress = ((char*)(*BaseAddress)) + tmpLength-1;
 922          ASSERT(((ULONG_PTR)*BaseAddress/BoundaryAddressMultiple.QuadPart) == ((DWORD_PTR)EndAddress/BoundaryAddressMultiple.QuadPart));
 923       }
 924
 925       if (MmLocateMemoryAreaByRegion(AddressSpace,
 926                                      *BaseAddress,
 927                                      tmpLength) != NULL)
 928       {
 929          DPRINT("Memory area already occupied\n");
 930          return STATUS_CONFLICTING_ADDRESSES;
 931       }
 932    }
 933
 934     //
 935     // Is this a static memory area?
 936     //
 937     if (Type & MEMORY_AREA_STATIC)
 938     {
 939         //
 940         // Use the static array instead of the pool
 941         //
 942         ASSERT(MiStaticMemoryAreaCount < MI_STATIC_MEMORY_AREAS);
 943         MemoryArea = &MiStaticMemoryAreas[MiStaticMemoryAreaCount++];
 944         Type &= ~MEMORY_AREA_STATIC;
 945     }
 946     else
 947     {
 948         //
 949         // Allocate the memory area from nonpaged pool
 950         //
 951         MemoryArea = ExAllocatePoolWithTag(NonPagedPool,
 952                                            sizeof(MEMORY_AREA),
 953                                            TAG_MAREA);
 954     }
 955
 956     if (!MemoryArea) return STATUS_NO_MEMORY;
 957
 958    RtlZeroMemory(MemoryArea, sizeof(MEMORY_AREA));
 959    MemoryArea->Type = Type;
 960    MemoryArea->StartingAddress = *BaseAddress;
 961    MemoryArea->EndingAddress = (PVOID)((ULONG_PTR)*BaseAddress + tmpLength);
 962    MemoryArea->Protect = Protect;
 963    MemoryArea->Flags = AllocationFlags;
 964    //MemoryArea->LockCount = 0;
 965    MemoryArea->PageOpCount = 0;
 966    MemoryArea->DeleteInProgress = FALSE;
 967
 968    MmInsertMemoryArea(AddressSpace, MemoryArea);
 969
 970    *Result = MemoryArea;
 971
 972    DPRINT("MmCreateMemoryArea() succeeded (%p)\n", *BaseAddress);
 973    return STATUS_SUCCESS;
 974 }
 975
 976 VOID NTAPI
 977 MmMapMemoryArea(PVOID BaseAddress,
 978                 ULONG Length,
 979                 ULONG Consumer,
 980                 ULONG Protection)
 981 {
 982    ULONG i;
 983    NTSTATUS Status;
 984
 985    for (i = 0; i < PAGE_ROUND_UP(Length) / PAGE_SIZE; i++)
 986    {
 987       PFN_NUMBER Page;
 988
 989       Status = MmRequestPageMemoryConsumer(Consumer, TRUE, &Page);
 990       if (!NT_SUCCESS(Status))
 991       {
 992          DPRINT1("Unable to allocate page\n");
 993          KeBugCheck(MEMORY_MANAGEMENT);
 994       }
 995       Status = MmCreateVirtualMapping (NULL,
 996                                        (PVOID)((ULONG_PTR)BaseAddress + (i * PAGE_SIZE)),
 997                                        Protection,
 998                                        &Page,
 999                                        1);
1000       if (!NT_SUCCESS(Status))
1001       {
1002          DPRINT1("Unable to create virtual mapping\n");
1003          KeBugCheck(MEMORY_MANAGEMENT);
1004       }
1005    }
1006 }
1007
1008 NTSTATUS
1009 NTAPI
1010 MmDeleteProcessAddressSpace(PEPROCESS Process)
1011 {
1012    PVOID Address;
1013    PMEMORY_AREA MemoryArea;
1014
1015    DPRINT("MmDeleteProcessAddressSpace(Process %x (%s))\n", Process,
1016           Process->ImageFileName);
1017
1018    RemoveEntryList(&Process->MmProcessLinks);
1019
1020    MmLockAddressSpace(&Process->Vm);
1021
1022    while ((MemoryArea = (PMEMORY_AREA)Process->Vm.WorkingSetExpansionLinks.Flink) != NULL)
1023    {
1024       switch (MemoryArea->Type)
1025       {
1026          case MEMORY_AREA_SECTION_VIEW:
1027              Address = (PVOID)MemoryArea->StartingAddress;
1028              MmUnlockAddressSpace(&Process->Vm);
1029              MmUnmapViewOfSection(Process, Address);
1030              MmLockAddressSpace(&Process->Vm);
1031              break;
1032
1033          case MEMORY_AREA_VIRTUAL_MEMORY:
1034              MmFreeVirtualMemory(Process, MemoryArea);
1035              break;
1036
1037          case MEMORY_AREA_OWNED_BY_ARM3:
1038              MmFreeMemoryArea(&Process->Vm,
1039                               MemoryArea,
1040                               NULL,
1041                               NULL);
1042              break;
1043
1044          default:
1045             KeBugCheck(MEMORY_MANAGEMENT);
1046       }
1047    }
1048
1049    MmUnlockAddressSpace(&Process->Vm);
1050
1051    DPRINT("Finished MmReleaseMmInfo()\n");
1052    return(STATUS_SUCCESS);
1053 }
1054
1055 /* EOF */