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