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