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