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 (AlignedAddress >= LowestAddress)
 497       {
 498           if (Node->StartingAddress > AlignedAddress &&
 499               (ULONG_PTR)Node->StartingAddress - (ULONG_PTR)AlignedAddress >= Length)
 500           {
 501              DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 502              ASSERT(AlignedAddress >= LowestAddress);
 503              return AlignedAddress;
 504           }
 505       }
 506       PreviousNode = Node;
 507    }
 508
 509    /* Check if there is enough space after the last memory area. */
 510    AlignedAddress = MM_ROUND_UP(PreviousNode->EndingAddress, Granularity);
 511    if ((ULONG_PTR)HighestAddress > (ULONG_PTR)AlignedAddress &&
 512        (ULONG_PTR)HighestAddress - (ULONG_PTR)AlignedAddress >= Length)
 513    {
 514       DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 515       ASSERT(AlignedAddress >= LowestAddress);
 516       return AlignedAddress;
 517    }
 518
 519    /* Check if there is enough space before the first memory area. */
 520    AlignedAddress = MM_ROUND_UP(LowestAddress, Granularity);
 521    if (FirstNode->StartingAddress > AlignedAddress &&
 522        (ULONG_PTR)FirstNode->StartingAddress - (ULONG_PTR)AlignedAddress >= Length)
 523    {
 524       DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 525       ASSERT(AlignedAddress >= LowestAddress);
 526       return AlignedAddress;
 527    }
 528
 529    DPRINT("MmFindGapBottomUp: 0\n");
 530    return 0;
 531 }
 532
 533
 534 static PVOID
 535 MmFindGapTopDown(
 536    PMMSUPPORT AddressSpace,
 537    ULONG_PTR Length,
 538    ULONG_PTR Granularity)
 539 {
 540    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 541    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 542                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 543    PVOID AlignedAddress;
 544    PMEMORY_AREA Node;
 545    PMEMORY_AREA PreviousNode;
 546
 547    DPRINT("LowestAddress: %p HighestAddress: %p\n",
 548           LowestAddress, HighestAddress);
 549
 550    AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)HighestAddress - Length + 1, Granularity);
 551
 552    /* Check for overflow. */
 553    if (AlignedAddress > HighestAddress)
 554       return NULL;
 555
 556    /* Special case for empty tree. */
 557    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 558    {
 559       if (AlignedAddress >= LowestAddress)
 560       {
 561          DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 562          return AlignedAddress;
 563       }
 564       DPRINT("MmFindGapTopDown: 0\n");
 565       return 0;
 566    }
 567
 568    /* Go to the node with highest address in the tree. */
 569    Node = MmIterateLastNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 570
 571    /* Check if there is enough space after the last memory area. */
 572    if (Node->EndingAddress <= AlignedAddress)
 573    {
 574       DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 575       return AlignedAddress;
 576    }
 577
 578    /* Traverse the tree from left to right. */
 579    PreviousNode = Node;
 580    for (;;)
 581    {
 582       Node = MmIteratePrevNode(Node);
 583       if (Node == NULL)
 584          break;
 585
 586       AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)PreviousNode->StartingAddress - Length + 1, Granularity);
 587
 588       /* Check for overflow. */
 589       if (AlignedAddress > PreviousNode->StartingAddress)
 590          return NULL;
 591
 592       if (Node->EndingAddress <= AlignedAddress)
 593       {
 594          DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 595          return AlignedAddress;
 596       }
 597
 598       PreviousNode = Node;
 599    }
 600
 601    AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)PreviousNode->StartingAddress - Length + 1, Granularity);
 602
 603    /* Check for overflow. */
 604    if (AlignedAddress > PreviousNode->StartingAddress)
 605       return NULL;
 606
 607    if (AlignedAddress >= LowestAddress)
 608    {
 609       DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 610       return AlignedAddress;
 611    }
 612
 613    DPRINT("MmFindGapTopDown: 0\n");
 614    return 0;
 615 }
 616
 617
 618 PVOID NTAPI
 619 MmFindGap(
 620    PMMSUPPORT AddressSpace,
 621    ULONG_PTR Length,
 622    ULONG_PTR Granularity,
 623    BOOLEAN TopDown)
 624 {
 625    if (TopDown)
 626       return MmFindGapTopDown(AddressSpace, Length, Granularity);
 627
 628    return MmFindGapBottomUp(AddressSpace, Length, Granularity);
 629 }
 630
 631 ULONG_PTR NTAPI
 632 MmFindGapAtAddress(
 633    PMMSUPPORT AddressSpace,
 634    PVOID Address)
 635 {
 636    PMEMORY_AREA Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 637    PMEMORY_AREA RightNeighbour = NULL;
 638    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 639    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 640                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 641
 642    Address = MM_ROUND_DOWN(Address, PAGE_SIZE);
 643
 644    if (LowestAddress < MmSystemRangeStart)
 645    {
 646       if (Address >= MmSystemRangeStart)
 647       {
 648          return 0;
 649       }
 650    }
 651    else
 652    {
 653       if (Address < LowestAddress)
 654       {
 655          return 0;
 656       }
 657    }
 658
 659    while (Node != NULL)
 660    {
 661       if (Address < Node->StartingAddress)
 662       {
 663          RightNeighbour = Node;
 664          Node = Node->LeftChild;
 665       }
 666       else if (Address >= Node->EndingAddress)
 667       {
 668          Node = Node->RightChild;
 669       }
 670       else
 671       {
 672          DPRINT("MmFindGapAtAddress: 0\n");
 673          return 0;
 674       }
 675    }
 676
 677    if (RightNeighbour)
 678    {
 679       DPRINT("MmFindGapAtAddress: %p [%p]\n", Address,
 680              (ULONG_PTR)RightNeighbour->StartingAddress - (ULONG_PTR)Address);
 681       return (ULONG_PTR)RightNeighbour->StartingAddress - (ULONG_PTR)Address;
 682    }
 683    else
 684    {
 685       DPRINT("MmFindGapAtAddress: %p [%p]\n", Address,
 686              (ULONG_PTR)HighestAddress - (ULONG_PTR)Address);
 687       return (ULONG_PTR)HighestAddress - (ULONG_PTR)Address;
 688    }
 689 }
 690
 691 VOID
 692 NTAPI
 693 MiRemoveNode(IN PMMADDRESS_NODE Node,
 694 IN PMM_AVL_TABLE Table);
 695
 696 /**
 697  * @name MmFreeMemoryArea
 698  *
 699  * Free an existing memory area.
 700  *
 701  * @param AddressSpace
 702  *        Address space to free the area from.
 703  * @param MemoryArea
 704  *        Memory area we're about to free.
 705  * @param FreePage
 706  *        Callback function for each freed page.
 707  * @param FreePageContext
 708  *        Context passed to the callback function.
 709  *
 710  * @return Status
 711  *
 712  * @remarks Lock the address space before calling this function.
 713  */
 714
 715 NTSTATUS NTAPI
 716 MmFreeMemoryArea(
 717    PMMSUPPORT AddressSpace,
 718    PMEMORY_AREA MemoryArea,
 719    PMM_FREE_PAGE_FUNC FreePage,
 720    PVOID FreePageContext)
 721 {
 722    PMEMORY_AREA *ParentReplace;
 723    ULONG_PTR Address;
 724    PVOID EndAddress;
 725
 726    if (MemoryArea->Type != MEMORY_AREA_OWNED_BY_ARM3)
 727    {
 728        PEPROCESS CurrentProcess = PsGetCurrentProcess();
 729        PEPROCESS Process = MmGetAddressSpaceOwner(AddressSpace);
 730
 731        if (Process != NULL &&
 732            Process != CurrentProcess)
 733        {
 734           KeAttachProcess(&Process->Pcb);
 735        }
 736
 737        EndAddress = MM_ROUND_UP(MemoryArea->EndingAddress, PAGE_SIZE);
 738        for (Address = (ULONG_PTR)MemoryArea->StartingAddress;
 739             Address < (ULONG_PTR)EndAddress;
 740             Address += PAGE_SIZE)
 741        {
 742              BOOLEAN Dirty = FALSE;
 743              SWAPENTRY SwapEntry = 0;
 744              PFN_NUMBER Page = 0;
 745
 746              if (MmIsPageSwapEntry(Process, (PVOID)Address))
 747              {
 748                 MmDeletePageFileMapping(Process, (PVOID)Address, &SwapEntry);
 749              }
 750              else
 751              {
 752                 MmDeleteVirtualMapping(Process, (PVOID)Address, FALSE, &Dirty, &Page);
 753              }
 754              if (FreePage != NULL)
 755              {
 756                 FreePage(FreePageContext, MemoryArea, (PVOID)Address,
 757                          Page, SwapEntry, (BOOLEAN)Dirty);
 758              }
 759        }
 760
 761        if (Process != NULL &&
 762            Process != CurrentProcess)
 763        {
 764           KeDetachProcess();
 765        }
 766
 767        if (MemoryArea->Vad)
 768        {
 769            ASSERT(MemoryArea->EndingAddress < MmSystemRangeStart);
 770            ASSERT(MemoryArea->Type == MEMORY_AREA_VIRTUAL_MEMORY || MemoryArea->Type == MEMORY_AREA_SECTION_VIEW);
 771
 772            /* MmCleanProcessAddressSpace might have removed it (and this would be MmDeleteProcessAdressSpace) */
 773            ASSERT(((PMMVAD)MemoryArea->Vad)->u.VadFlags.Spare != 0);
 774            if (((PMMVAD)MemoryArea->Vad)->u.VadFlags.Spare == 1)
 775            {
 776                MiRemoveNode(MemoryArea->Vad, &Process->VadRoot);
 777            }
 778
 779            ExFreePool(MemoryArea->Vad);
 780            MemoryArea->Vad = NULL;
 781        }
 782     }
 783
 784    /* Remove the tree item. */
 785    {
 786       if (MemoryArea->Parent != NULL)
 787       {
 788          if (MemoryArea->Parent->LeftChild == MemoryArea)
 789             ParentReplace = &MemoryArea->Parent->LeftChild;
 790          else
 791             ParentReplace = &MemoryArea->Parent->RightChild;
 792       }
 793       else
 794          ParentReplace = (PMEMORY_AREA*)&AddressSpace->WorkingSetExpansionLinks.Flink;
 795
 796       if (MemoryArea->RightChild == NULL)
 797       {
 798          *ParentReplace = MemoryArea->LeftChild;
 799          if (MemoryArea->LeftChild)
 800             MemoryArea->LeftChild->Parent = MemoryArea->Parent;
 801       }
 802       else
 803       {
 804          if (MemoryArea->RightChild->LeftChild == NULL)
 805          {
 806             MemoryArea->RightChild->LeftChild = MemoryArea->LeftChild;
 807             if (MemoryArea->LeftChild)
 808                MemoryArea->LeftChild->Parent = MemoryArea->RightChild;
 809
 810             *ParentReplace = MemoryArea->RightChild;
 811             MemoryArea->RightChild->Parent = MemoryArea->Parent;
 812          }
 813          else
 814          {
 815             PMEMORY_AREA LowestNode;
 816
 817             LowestNode = MemoryArea->RightChild->LeftChild;
 818             while (LowestNode->LeftChild != NULL)
 819                LowestNode = LowestNode->LeftChild;
 820
 821             LowestNode->Parent->LeftChild = LowestNode->RightChild;
 822             if (LowestNode->RightChild)
 823                LowestNode->RightChild->Parent = LowestNode->Parent;
 824
 825             LowestNode->LeftChild = MemoryArea->LeftChild;
 826             if (MemoryArea->LeftChild)
 827                MemoryArea->LeftChild->Parent = LowestNode;
 828
 829             LowestNode->RightChild = MemoryArea->RightChild;
 830             MemoryArea->RightChild->Parent = LowestNode;
 831
 832             *ParentReplace = LowestNode;
 833             LowestNode->Parent = MemoryArea->Parent;
 834          }
 835       }
 836    }
 837
 838    ExFreePoolWithTag(MemoryArea, TAG_MAREA);
 839
 840    DPRINT("MmFreeMemoryAreaByNode() succeeded\n");
 841
 842    return STATUS_SUCCESS;
 843 }
 844
 845 /**
 846  * @name MmCreateMemoryArea
 847  *
 848  * Create a memory area.
 849  *
 850  * @param AddressSpace
 851  *        Address space to create the area in.
 852  * @param Type
 853  *        Type of the memory area.
 854  * @param BaseAddress
 855  *        Base address for the memory area we're about the create. On
 856  *        input it contains either 0 (auto-assign address) or preferred
 857  *        address. On output it contains the starting address of the
 858  *        newly created area.
 859  * @param Length
 860  *        Length of the area to allocate.
 861  * @param Attributes
 862  *        Protection attributes for the memory area.
 863  * @param Result
 864  *        Receives a pointer to the memory area on successful exit.
 865  *
 866  * @return Status
 867  *
 868  * @remarks Lock the address space before calling this function.
 869  */
 870
 871 NTSTATUS NTAPI
 872 MmCreateMemoryArea(PMMSUPPORT AddressSpace,
 873                    ULONG Type,
 874                    PVOID *BaseAddress,
 875                    ULONG_PTR Length,
 876                    ULONG Protect,
 877                    PMEMORY_AREA *Result,
 878                    BOOLEAN FixedAddress,
 879                    ULONG AllocationFlags,
 880                    PHYSICAL_ADDRESS BoundaryAddressMultiple)
 881 {
 882    PVOID EndAddress;
 883    ULONG Granularity;
 884    ULONG tmpLength;
 885    PMEMORY_AREA MemoryArea;
 886
 887    DPRINT("MmCreateMemoryArea(Type %d, BaseAddress %p, "
 888           "*BaseAddress %p, Length %p, AllocationFlags %x, "
 889           "FixedAddress %x, Result %p)\n",
 890           Type, BaseAddress, *BaseAddress, Length, AllocationFlags,
 891           FixedAddress, Result);
 892
 893    Granularity = (MEMORY_AREA_VIRTUAL_MEMORY == Type ? MM_VIRTMEM_GRANULARITY : PAGE_SIZE);
 894    if ((*BaseAddress) == 0 && !FixedAddress)
 895    {
 896       tmpLength = PAGE_ROUND_UP(Length);
 897       *BaseAddress = MmFindGap(AddressSpace,
 898                                tmpLength,
 899                                Granularity,
 900                                (AllocationFlags & MEM_TOP_DOWN) == MEM_TOP_DOWN);
 901       if ((*BaseAddress) == 0)
 902       {
 903          DPRINT("No suitable gap\n");
 904          return STATUS_NO_MEMORY;
 905       }
 906    }
 907    else
 908    {
 909       tmpLength = Length + ((ULONG_PTR) *BaseAddress
 910                          - (ULONG_PTR) MM_ROUND_DOWN(*BaseAddress, Granularity));
 911       *BaseAddress = MM_ROUND_DOWN(*BaseAddress, Granularity);
 912
 913       if (!MmGetAddressSpaceOwner(AddressSpace) && *BaseAddress < MmSystemRangeStart)
 914       {
 915          return STATUS_ACCESS_VIOLATION;
 916       }
 917
 918       if (MmGetAddressSpaceOwner(AddressSpace) &&
 919           (ULONG_PTR)(*BaseAddress) + tmpLength > (ULONG_PTR)MmSystemRangeStart)
 920       {
 921          return STATUS_ACCESS_VIOLATION;
 922       }
 923
 924       if (BoundaryAddressMultiple.QuadPart != 0)
 925       {
 926          EndAddress = ((char*)(*BaseAddress)) + tmpLength-1;
 927          ASSERT(((ULONG_PTR)*BaseAddress/BoundaryAddressMultiple.QuadPart) == ((DWORD_PTR)EndAddress/BoundaryAddressMultiple.QuadPart));
 928       }
 929
 930       if (MmLocateMemoryAreaByRegion(AddressSpace,
 931                                      *BaseAddress,
 932                                      tmpLength) != NULL)
 933       {
 934          DPRINT("Memory area already occupied\n");
 935          return STATUS_CONFLICTING_ADDRESSES;
 936       }
 937    }
 938
 939     //
 940     // Is this a static memory area?
 941     //
 942     if (Type & MEMORY_AREA_STATIC)
 943     {
 944         //
 945         // Use the static array instead of the pool
 946         //
 947         ASSERT(MiStaticMemoryAreaCount < MI_STATIC_MEMORY_AREAS);
 948         MemoryArea = &MiStaticMemoryAreas[MiStaticMemoryAreaCount++];
 949         Type &= ~MEMORY_AREA_STATIC;
 950     }
 951     else
 952     {
 953         //
 954         // Allocate the memory area from nonpaged pool
 955         //
 956         MemoryArea = ExAllocatePoolWithTag(NonPagedPool,
 957                                            sizeof(MEMORY_AREA),
 958                                            TAG_MAREA);
 959     }
 960
 961     if (!MemoryArea) return STATUS_NO_MEMORY;
 962
 963    RtlZeroMemory(MemoryArea, sizeof(MEMORY_AREA));
 964    MemoryArea->Type = Type;
 965    MemoryArea->StartingAddress = *BaseAddress;
 966    MemoryArea->EndingAddress = (PVOID)((ULONG_PTR)*BaseAddress + tmpLength);
 967    MemoryArea->Protect = Protect;
 968    MemoryArea->Flags = AllocationFlags;
 969    //MemoryArea->LockCount = 0;
 970    MemoryArea->PageOpCount = 0;
 971    MemoryArea->DeleteInProgress = FALSE;
 972
 973    MmInsertMemoryArea(AddressSpace, MemoryArea);
 974
 975    *Result = MemoryArea;
 976
 977    DPRINT("MmCreateMemoryArea() succeeded (%p)\n", *BaseAddress);
 978    return STATUS_SUCCESS;
 979 }
 980
 981 VOID NTAPI
 982 MmMapMemoryArea(PVOID BaseAddress,
 983                 ULONG Length,
 984                 ULONG Consumer,
 985                 ULONG Protection)
 986 {
 987    ULONG i;
 988    NTSTATUS Status;
 989
 990    for (i = 0; i < PAGE_ROUND_UP(Length) / PAGE_SIZE; i++)
 991    {
 992       PFN_NUMBER Page;
 993
 994       Status = MmRequestPageMemoryConsumer(Consumer, TRUE, &Page);
 995       if (!NT_SUCCESS(Status))
 996       {
 997          DPRINT1("Unable to allocate page\n");
 998          KeBugCheck(MEMORY_MANAGEMENT);
 999       }
1000       Status = MmCreateVirtualMapping (NULL,
1001                                        (PVOID)((ULONG_PTR)BaseAddress + (i * PAGE_SIZE)),
1002                                        Protection,
1003                                        &Page,
1004                                        1);
1005       if (!NT_SUCCESS(Status))
1006       {
1007          DPRINT1("Unable to create virtual mapping\n");
1008          KeBugCheck(MEMORY_MANAGEMENT);
1009       }
1010    }
1011 }
1012
1013 NTSTATUS
1014 NTAPI
1015 MmDeleteProcessAddressSpace(PEPROCESS Process)
1016 {
1017    PVOID Address;
1018    PMEMORY_AREA MemoryArea;
1019
1020    DPRINT("MmDeleteProcessAddressSpace(Process %x (%s))\n", Process,
1021           Process->ImageFileName);
1022
1023    RemoveEntryList(&Process->MmProcessLinks);
1024
1025    MmLockAddressSpace(&Process->Vm);
1026
1027    while ((MemoryArea = (PMEMORY_AREA)Process->Vm.WorkingSetExpansionLinks.Flink) != NULL)
1028    {
1029       switch (MemoryArea->Type)
1030       {
1031          case MEMORY_AREA_SECTION_VIEW:
1032              Address = (PVOID)MemoryArea->StartingAddress;
1033              MmUnlockAddressSpace(&Process->Vm);
1034              MmUnmapViewOfSection(Process, Address);
1035              MmLockAddressSpace(&Process->Vm);
1036              break;
1037
1038          case MEMORY_AREA_VIRTUAL_MEMORY:
1039              MmFreeVirtualMemory(Process, MemoryArea);
1040              break;
1041
1042          case MEMORY_AREA_OWNED_BY_ARM3:
1043              MmFreeMemoryArea(&Process->Vm,
1044                               MemoryArea,
1045                               NULL,
1046                               NULL);
1047              break;
1048
1049          default:
1050             KeBugCheck(MEMORY_MANAGEMENT);
1051       }
1052    }
1053
1054    MmUnlockAddressSpace(&Process->Vm);
1055
1056    DPRINT("Finished MmReleaseMmInfo()\n");
1057    return(STATUS_SUCCESS);
1058 }
1059
1060 /* EOF */