reactos/ntoskrnl/mm/marea.c

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