reactos/ntoskrnl/mm/marea.c

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