ntoskrnl/mm/marea.c

   1 /*
   2  * Copyright (C) 1998-2005 ReactOS Team (and the authors from the programmers section)
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  17  *
  18  *
  19  * PROJECT:         ReactOS kernel
  20  * FILE:            ntoskrnl/mm/marea.c
  21  * PURPOSE:         Implements memory areas
  22  *
  23  * PROGRAMMERS:     Rex Jolliff
  24  *                  David Welch
  25  *                  Eric Kohl
  26  *                  Philip Susi
  27  *                  Casper Hornstrup
  28  *                  Eric Kohl
  29  *                  Ge van Geldorp
  30  *                  Royce Mitchell III
  31  *                  Aleksey Bragin
  32  *                  Jason Filby
  33  *                  Thomas Weidenmueller
  34  *                  Gunnar Andre' Dalsnes
  35  *                  Mike Nordell
  36  *                  Alex Ionescu
  37  *                  Filip Navara
  38  *                  Herve Poussineau
  39  *                  Steven Edwards
  40  */
  41
  42 /* INCLUDES *****************************************************************/
  43
  44 #include <ntoskrnl.h>
  45 #define NDEBUG
  46 #include <debug.h>
  47
  48 MEMORY_AREA MiStaticMemoryAreas[MI_STATIC_MEMORY_AREAS];
  49 ULONG MiStaticMemoryAreaCount;
  50
  51 /* #define VALIDATE_MEMORY_AREAS */
  52
  53 /* FUNCTIONS *****************************************************************/
  54
  55 /**
  56  * @name MmIterateFirstNode
  57  *
  58  * @param Node
  59  *        Head node of the MEMORY_AREA tree.
  60  *
  61  * @return The leftmost MEMORY_AREA node (ie. the one with lowest
  62  *         address)
  63  */
  64
  65 static PMEMORY_AREA MmIterateFirstNode(PMEMORY_AREA Node)
  66 {
  67    while (Node->LeftChild != NULL)
  68       Node = Node->LeftChild;
  69
  70    return Node;
  71 }
  72
  73 /**
  74  * @name MmIterateNextNode
  75  *
  76  * @param Node
  77  *        Current node in the tree.
  78  *
  79  * @return Next node in the tree (sorted by address).
  80  */
  81
  82 static PMEMORY_AREA MmIterateNextNode(PMEMORY_AREA Node)
  83 {
  84    if (Node->RightChild != NULL)
  85    {
  86       Node = Node->RightChild;
  87       while (Node->LeftChild != NULL)
  88          Node = Node->LeftChild;
  89    }
  90    else
  91    {
  92       PMEMORY_AREA TempNode = NULL;
  93
  94       do
  95       {
  96          /* Check if we're at the end of tree. */
  97          if (Node->Parent == NULL)
  98             return NULL;
  99
 100          TempNode = Node;
 101          Node = Node->Parent;
 102       }
 103       while (TempNode == Node->RightChild);
 104    }
 105    return Node;
 106 }
 107
 108 /**
 109  * @name MmIterateLastNode
 110  *
 111  * @param Node
 112  *        Head node of the MEMORY_AREA tree.
 113  *
 114  * @return The rightmost MEMORY_AREA node (ie. the one with highest
 115  *         address)
 116  */
 117
 118 static PMEMORY_AREA MmIterateLastNode(PMEMORY_AREA Node)
 119 {
 120    while (Node->RightChild != NULL)
 121       Node = Node->RightChild;
 122
 123    return Node;
 124 }
 125
 126 /**
 127  * @name MmIteratePreviousNode
 128  *
 129  * @param Node
 130  *        Current node in the tree.
 131  *
 132  * @return Previous node in the tree (sorted by address).
 133  */
 134
 135 static PMEMORY_AREA MmIteratePrevNode(PMEMORY_AREA Node)
 136 {
 137    if (Node->LeftChild != NULL)
 138    {
 139       Node = Node->LeftChild;
 140       while (Node->RightChild != NULL)
 141          Node = Node->RightChild;
 142    }
 143    else
 144    {
 145       PMEMORY_AREA TempNode = NULL;
 146
 147       do
 148       {
 149          /* Check if we're at the end of tree. */
 150          if (Node->Parent == NULL)
 151             return NULL;
 152
 153          TempNode = Node;
 154          Node = Node->Parent;
 155       }
 156       while (TempNode == Node->LeftChild);
 157    }
 158    return Node;
 159 }
 160
 161 #ifdef VALIDATE_MEMORY_AREAS
 162 static VOID MmVerifyMemoryAreas(PMMSUPPORT AddressSpace)
 163 {
 164    PMEMORY_AREA Node;
 165
 166    ASSERT(AddressSpace != NULL);
 167
 168    /* Special case for empty tree. */
 169    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 170       return;
 171
 172    /* Traverse the tree from left to right. */
 173    for (Node = MmIterateFirstNode(AddressSpace->WorkingSetExpansionLinks.Flink);
 174         Node != NULL;
 175         Node = MmIterateNextNode(Node))
 176    {
 177       /* FiN: The starting address can be NULL if someone explicitely asks
 178        * for NULL address. */
 179       ASSERT(Node->StartingAddress == NULL);
 180       ASSERT(Node->EndingAddress >= Node->StartingAddress);
 181    }
 182 }
 183 #else
 184 #define MmVerifyMemoryAreas(x)
 185 #endif
 186
 187 VOID NTAPI
 188 MmDumpMemoryAreas(PMMSUPPORT AddressSpace)
 189 {
 190    PMEMORY_AREA Node;
 191
 192    DbgPrint("MmDumpMemoryAreas()\n");
 193
 194    /* Special case for empty tree. */
 195    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 196       return;
 197
 198    /* Traverse the tree from left to right. */
 199    for (Node = MmIterateFirstNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 200         Node != NULL;
 201         Node = MmIterateNextNode(Node))
 202    {
 203       DbgPrint("Start %p End %p Protect %x Flags %x\n",
 204                Node->StartingAddress, Node->EndingAddress,
 205                Node->Protect, Node->Flags);
 206    }
 207
 208    DbgPrint("Finished MmDumpMemoryAreas()\n");
 209 }
 210
 211 PMEMORY_AREA NTAPI
 212 MmLocateMemoryAreaByAddress(
 213    PMMSUPPORT AddressSpace,
 214    PVOID Address)
 215 {
 216    PMEMORY_AREA Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 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 NTAPI
 242 MmLocateMemoryAreaByRegion(
 243    PMMSUPPORT 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->WorkingSetExpansionLinks.Flink == NULL)
 254       return NULL;
 255
 256    /* Traverse the tree from left to right. */
 257    for (Node = MmIterateFirstNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 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    PMMSUPPORT AddressSpace,
 305    ULONG Count)
 306 {
 307    PMEMORY_AREA Root = NULL;
 308    PMEMORY_AREA Red = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 309    PMEMORY_AREA Black = Red->LeftChild;
 310
 311    while (Count--)
 312    {
 313       if (Root)
 314          Root->LeftChild = Black;
 315       else
 316          AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)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    PMMSUPPORT 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 = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 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->WorkingSetExpansionLinks.Flink = (PVOID)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    PMMSUPPORT 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->WorkingSetExpansionLinks.Flink == NULL)
 422    {
 423       AddressSpace->WorkingSetExpansionLinks.Flink = (PVOID)marea;
 424       marea->LeftChild = marea->RightChild = marea->Parent = NULL;
 425       return;
 426    }
 427
 428    Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 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    PMMSUPPORT AddressSpace,
 469    ULONG_PTR Length,
 470    ULONG_PTR Granularity)
 471 {
 472    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 473    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 474                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 475    PVOID AlignedAddress;
 476    PMEMORY_AREA Node;
 477    PMEMORY_AREA FirstNode;
 478    PMEMORY_AREA PreviousNode;
 479
 480    MmVerifyMemoryAreas(AddressSpace);
 481
 482    DPRINT("LowestAddress: %p HighestAddress: %p\n",
 483           LowestAddress, HighestAddress);
 484
 485    AlignedAddress = MM_ROUND_UP(LowestAddress, Granularity);
 486
 487    /* Special case for empty tree. */
 488    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 489    {
 490       if ((ULONG_PTR)HighestAddress - (ULONG_PTR)AlignedAddress >= Length)
 491       {
 492          DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 493          return AlignedAddress;
 494       }
 495       DPRINT("MmFindGapBottomUp: 0\n");
 496       return 0;
 497    }
 498
 499    /* Go to the node with lowest address in the tree. */
 500    FirstNode = Node = MmIterateFirstNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 501
 502    /* Traverse the tree from left to right. */
 503    PreviousNode = Node;
 504    for (;;)
 505    {
 506       Node = MmIterateNextNode(Node);
 507       if (Node == NULL)
 508          break;
 509
 510       AlignedAddress = MM_ROUND_UP(PreviousNode->EndingAddress, Granularity);
 511       if (Node->StartingAddress > AlignedAddress &&
 512           (ULONG_PTR)Node->StartingAddress - (ULONG_PTR)AlignedAddress >= Length)
 513       {
 514          DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 515          return AlignedAddress;
 516       }
 517
 518       PreviousNode = Node;
 519    }
 520
 521    /* Check if there is enough space after the last memory area. */
 522    AlignedAddress = MM_ROUND_UP(PreviousNode->EndingAddress, Granularity);
 523    if ((ULONG_PTR)HighestAddress > (ULONG_PTR)AlignedAddress &&
 524        (ULONG_PTR)HighestAddress - (ULONG_PTR)AlignedAddress >= Length)
 525    {
 526       DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 527       return AlignedAddress;
 528    }
 529
 530    /* Check if there is enough space before the first memory area. */
 531    AlignedAddress = MM_ROUND_UP(LowestAddress, Granularity);
 532    if (FirstNode->StartingAddress > AlignedAddress &&
 533        (ULONG_PTR)FirstNode->StartingAddress - (ULONG_PTR)AlignedAddress >= Length)
 534    {
 535       DPRINT("MmFindGapBottomUp: %p\n", AlignedAddress);
 536       return AlignedAddress;
 537    }
 538
 539    DPRINT("MmFindGapBottomUp: 0\n");
 540    return 0;
 541 }
 542
 543
 544 static PVOID
 545 MmFindGapTopDown(
 546    PMMSUPPORT AddressSpace,
 547    ULONG_PTR Length,
 548    ULONG_PTR Granularity)
 549 {
 550    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 551    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 552                           (PVOID)((ULONG_PTR)MmSystemRangeStart - 1) : (PVOID)MAXULONG_PTR;
 553    PVOID AlignedAddress;
 554    PMEMORY_AREA Node;
 555    PMEMORY_AREA PreviousNode;
 556
 557    MmVerifyMemoryAreas(AddressSpace);
 558
 559    DPRINT("LowestAddress: %p HighestAddress: %p\n",
 560           LowestAddress, HighestAddress);
 561
 562    AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)HighestAddress - Length + 1, Granularity);
 563
 564    /* Check for overflow. */
 565    if (AlignedAddress > HighestAddress)
 566       return NULL;
 567
 568    /* Special case for empty tree. */
 569    if (AddressSpace->WorkingSetExpansionLinks.Flink == NULL)
 570    {
 571       if (AlignedAddress >= LowestAddress)
 572       {
 573          DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 574          return AlignedAddress;
 575       }
 576       DPRINT("MmFindGapTopDown: 0\n");
 577       return 0;
 578    }
 579
 580    /* Go to the node with highest address in the tree. */
 581    Node = MmIterateLastNode((PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink);
 582
 583    /* Check if there is enough space after the last memory area. */
 584    if (Node->EndingAddress <= AlignedAddress)
 585    {
 586       DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 587       return AlignedAddress;
 588    }
 589
 590    /* Traverse the tree from left to right. */
 591    PreviousNode = Node;
 592    for (;;)
 593    {
 594       Node = MmIteratePrevNode(Node);
 595       if (Node == NULL)
 596          break;
 597
 598       AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)PreviousNode->StartingAddress - Length + 1, Granularity);
 599
 600       /* Check for overflow. */
 601       if (AlignedAddress > PreviousNode->StartingAddress)
 602          return NULL;
 603
 604       if (Node->EndingAddress <= AlignedAddress)
 605       {
 606          DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 607          return AlignedAddress;
 608       }
 609
 610       PreviousNode = Node;
 611    }
 612
 613    AlignedAddress = MM_ROUND_DOWN((ULONG_PTR)PreviousNode->StartingAddress - Length + 1, Granularity);
 614
 615    /* Check for overflow. */
 616    if (AlignedAddress > PreviousNode->StartingAddress)
 617       return NULL;
 618
 619    if (AlignedAddress >= LowestAddress)
 620    {
 621       DPRINT("MmFindGapTopDown: %p\n", AlignedAddress);
 622       return AlignedAddress;
 623    }
 624
 625    DPRINT("MmFindGapTopDown: 0\n");
 626    return 0;
 627 }
 628
 629
 630 PVOID NTAPI
 631 MmFindGap(
 632    PMMSUPPORT AddressSpace,
 633    ULONG_PTR Length,
 634    ULONG_PTR Granularity,
 635    BOOLEAN TopDown)
 636 {
 637    if (TopDown)
 638       return MmFindGapTopDown(AddressSpace, Length, Granularity);
 639
 640    return MmFindGapBottomUp(AddressSpace, Length, Granularity);
 641 }
 642
 643 ULONG_PTR NTAPI
 644 MmFindGapAtAddress(
 645    PMMSUPPORT AddressSpace,
 646    PVOID Address)
 647 {
 648    PMEMORY_AREA Node = (PMEMORY_AREA)AddressSpace->WorkingSetExpansionLinks.Flink;
 649    PMEMORY_AREA RightNeighbour = NULL;
 650    PVOID LowestAddress  = MmGetAddressSpaceOwner(AddressSpace) ? MM_LOWEST_USER_ADDRESS : MmSystemRangeStart;
 651    PVOID HighestAddress = MmGetAddressSpaceOwner(AddressSpace) ?
 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 (LowestAddress < MmSystemRangeStart)
 659    {
 660       if (Address >= MmSystemRangeStart)
 661       {
 662          return 0;
 663       }
 664    }
 665    else
 666    {
 667       if (Address < 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 /**
 707  * @name MmFreeMemoryArea
 708  *
 709  * Free an existing memory area.
 710  *
 711  * @param AddressSpace
 712  *        Address space to free the area from.
 713  * @param MemoryArea
 714  *        Memory area we're about to free.
 715  * @param FreePage
 716  *        Callback function for each freed page.
 717  * @param FreePageContext
 718  *        Context passed to the callback function.
 719  *
 720  * @return Status
 721  *
 722  * @remarks Lock the address space before calling this function.
 723  */
 724
 725 NTSTATUS NTAPI
 726 MmFreeMemoryArea(
 727    PMMSUPPORT AddressSpace,
 728    PMEMORY_AREA MemoryArea,
 729    PMM_FREE_PAGE_FUNC FreePage,
 730    PVOID FreePageContext)
 731 {
 732    PMEMORY_AREA *ParentReplace;
 733    ULONG_PTR Address;
 734    PVOID EndAddress;
 735    PEPROCESS CurrentProcess = PsGetCurrentProcess();
 736    PEPROCESS Process = MmGetAddressSpaceOwner(AddressSpace);
 737
 738    if (Process != NULL &&
 739        Process != CurrentProcess)
 740    {
 741       KeAttachProcess(&Process->Pcb);
 742    }
 743
 744    EndAddress = MM_ROUND_UP(MemoryArea->EndingAddress, PAGE_SIZE);
 745    for (Address = (ULONG_PTR)MemoryArea->StartingAddress;
 746         Address < (ULONG_PTR)EndAddress;
 747         Address += PAGE_SIZE)
 748    {
 749       if (MemoryArea->Type == MEMORY_AREA_IO_MAPPING)
 750       {
 751          MmRawDeleteVirtualMapping((PVOID)Address);
 752       }
 753       else
 754       {
 755          BOOLEAN Dirty = FALSE;
 756          SWAPENTRY SwapEntry = 0;
 757          PFN_TYPE Page = 0;
 758
 759          if (MmIsPageSwapEntry(Process, (PVOID)Address))
 760          {
 761             MmDeletePageFileMapping(Process, (PVOID)Address, &SwapEntry);
 762          }
 763          else
 764          {
 765             MmDeleteVirtualMapping(Process, (PVOID)Address, FALSE, &Dirty, &Page);
 766          }
 767          if (FreePage != NULL)
 768          {
 769             FreePage(FreePageContext, MemoryArea, (PVOID)Address,
 770                      Page, SwapEntry, (BOOLEAN)Dirty);
 771          }
 772       }
 773    }
 774
 775    if (Process != NULL &&
 776        Process != CurrentProcess)
 777    {
 778       KeDetachProcess();
 779    }
 780
 781    /* Remove the tree item. */
 782    {
 783       if (MemoryArea->Parent != NULL)
 784       {
 785          if (MemoryArea->Parent->LeftChild == MemoryArea)
 786             ParentReplace = &MemoryArea->Parent->LeftChild;
 787          else
 788             ParentReplace = &MemoryArea->Parent->RightChild;
 789       }
 790       else
 791          ParentReplace = (PMEMORY_AREA*)&AddressSpace->WorkingSetExpansionLinks.Flink;
 792
 793       if (MemoryArea->RightChild == NULL)
 794       {
 795          *ParentReplace = MemoryArea->LeftChild;
 796          if (MemoryArea->LeftChild)
 797             MemoryArea->LeftChild->Parent = MemoryArea->Parent;
 798       }
 799       else
 800       {
 801          if (MemoryArea->RightChild->LeftChild == NULL)
 802          {
 803             MemoryArea->RightChild->LeftChild = MemoryArea->LeftChild;
 804             if (MemoryArea->LeftChild)
 805                MemoryArea->LeftChild->Parent = MemoryArea->RightChild;
 806
 807             *ParentReplace = MemoryArea->RightChild;
 808             MemoryArea->RightChild->Parent = MemoryArea->Parent;
 809          }
 810          else
 811          {
 812             PMEMORY_AREA LowestNode;
 813
 814             LowestNode = MemoryArea->RightChild->LeftChild;
 815             while (LowestNode->LeftChild != NULL)
 816                LowestNode = LowestNode->LeftChild;
 817
 818             LowestNode->Parent->LeftChild = LowestNode->RightChild;
 819             if (LowestNode->RightChild)
 820                LowestNode->RightChild->Parent = LowestNode->Parent;
 821
 822             LowestNode->LeftChild = MemoryArea->LeftChild;
 823             if (MemoryArea->LeftChild)
 824                MemoryArea->LeftChild->Parent = LowestNode;
 825
 826             LowestNode->RightChild = MemoryArea->RightChild;
 827             MemoryArea->RightChild->Parent = LowestNode;
 828
 829             *ParentReplace = LowestNode;
 830             LowestNode->Parent = MemoryArea->Parent;
 831          }
 832       }
 833    }
 834
 835    ExFreePoolWithTag(MemoryArea, TAG_MAREA);
 836
 837    DPRINT("MmFreeMemoryAreaByNode() succeeded\n");
 838
 839    return STATUS_SUCCESS;
 840 }
 841
 842 /**
 843  * @name MmFreeMemoryAreaByPtr
 844  *
 845  * Free an existing memory area given a pointer inside it.
 846  *
 847  * @param AddressSpace
 848  *        Address space to free the area from.
 849  * @param BaseAddress
 850  *        Address in the memory area we're about to free.
 851  * @param FreePage
 852  *        Callback function for each freed page.
 853  * @param FreePageContext
 854  *        Context passed to the callback function.
 855  *
 856  * @return Status
 857  *
 858  * @see MmFreeMemoryArea
 859  *
 860  * @todo Should we require the BaseAddress to be really the starting
 861  *       address of the memory area or is the current relaxed check
 862  *       (BaseAddress can point anywhere in the memory area) acceptable?
 863  *
 864  * @remarks Lock the address space before calling this function.
 865  */
 866
 867 NTSTATUS NTAPI
 868 MmFreeMemoryAreaByPtr(
 869    PMMSUPPORT AddressSpace,
 870    PVOID BaseAddress,
 871    PMM_FREE_PAGE_FUNC FreePage,
 872    PVOID FreePageContext)
 873 {
 874    PMEMORY_AREA MemoryArea;
 875
 876    DPRINT("MmFreeMemoryArea(AddressSpace %p, BaseAddress %p, "
 877           "FreePageContext %p)\n", AddressSpace, BaseAddress,
 878           FreePageContext);
 879
 880    MmVerifyMemoryAreas(AddressSpace);
 881
 882    MemoryArea = MmLocateMemoryAreaByAddress(AddressSpace,
 883                                             BaseAddress);
 884    if (MemoryArea == NULL)
 885    {
 886       KeBugCheck(MEMORY_MANAGEMENT);
 887       return(STATUS_UNSUCCESSFUL);
 888    }
 889
 890    return MmFreeMemoryArea(AddressSpace, MemoryArea, FreePage, FreePageContext);
 891 }
 892
 893 /**
 894  * @name MmCreateMemoryArea
 895  *
 896  * Create a memory area.
 897  *
 898  * @param AddressSpace
 899  *        Address space to create the area in.
 900  * @param Type
 901  *        Type of the memory area.
 902  * @param BaseAddress
 903  *        Base address for the memory area we're about the create. On
 904  *        input it contains either 0 (auto-assign address) or preferred
 905  *        address. On output it contains the starting address of the
 906  *        newly created area.
 907  * @param Length
 908  *        Length of the area to allocate.
 909  * @param Attributes
 910  *        Protection attributes for the memory area.
 911  * @param Result
 912  *        Receives a pointer to the memory area on successful exit.
 913  *
 914  * @return Status
 915  *
 916  * @remarks Lock the address space before calling this function.
 917  */
 918
 919 NTSTATUS NTAPI
 920 MmCreateMemoryArea(PMMSUPPORT AddressSpace,
 921                    ULONG Type,
 922                    PVOID *BaseAddress,
 923                    ULONG_PTR Length,
 924                    ULONG Protect,
 925                    PMEMORY_AREA *Result,
 926                    BOOLEAN FixedAddress,
 927                    ULONG AllocationFlags,
 928                    PHYSICAL_ADDRESS BoundaryAddressMultiple)
 929 {
 930    PVOID EndAddress;
 931    ULONG Granularity;
 932    ULONG tmpLength;
 933    PMEMORY_AREA MemoryArea;
 934
 935    DPRINT("MmCreateMemoryArea(Type %d, BaseAddress %p, "
 936           "*BaseAddress %p, Length %p, AllocationFlags %x, "
 937           "FixedAddress %x, Result %p)\n",
 938           Type, BaseAddress, *BaseAddress, Length, AllocationFlags,
 939           FixedAddress, Result);
 940
 941    MmVerifyMemoryAreas(AddressSpace);
 942
 943    Granularity = (MEMORY_AREA_VIRTUAL_MEMORY == Type ? MM_VIRTMEM_GRANULARITY : PAGE_SIZE);
 944    if ((*BaseAddress) == 0 && !FixedAddress)
 945    {
 946       tmpLength = PAGE_ROUND_UP(Length);
 947       *BaseAddress = MmFindGap(AddressSpace,
 948                                tmpLength,
 949                                Granularity,
 950                                (AllocationFlags & MEM_TOP_DOWN) == MEM_TOP_DOWN);
 951       if ((*BaseAddress) == 0)
 952       {
 953          DPRINT("No suitable gap\n");
 954          return STATUS_NO_MEMORY;
 955       }
 956    }
 957    else
 958    {
 959       tmpLength = Length + ((ULONG_PTR) *BaseAddress
 960                          - (ULONG_PTR) MM_ROUND_DOWN(*BaseAddress, Granularity));
 961       *BaseAddress = MM_ROUND_DOWN(*BaseAddress, Granularity);
 962
 963       if (!MmGetAddressSpaceOwner(AddressSpace) && *BaseAddress < MmSystemRangeStart)
 964       {
 965          return STATUS_ACCESS_VIOLATION;
 966       }
 967
 968       if (MmGetAddressSpaceOwner(AddressSpace) &&
 969           (ULONG_PTR)(*BaseAddress) + tmpLength > (ULONG_PTR)MmSystemRangeStart)
 970       {
 971          return STATUS_ACCESS_VIOLATION;
 972       }
 973
 974       if (BoundaryAddressMultiple.QuadPart != 0)
 975       {
 976          EndAddress = ((char*)(*BaseAddress)) + tmpLength-1;
 977          ASSERT(((ULONG_PTR)*BaseAddress/BoundaryAddressMultiple.QuadPart) == ((DWORD_PTR)EndAddress/BoundaryAddressMultiple.QuadPart));
 978       }
 979
 980       if (MmLocateMemoryAreaByRegion(AddressSpace,
 981                                      *BaseAddress,
 982                                      tmpLength) != NULL)
 983       {
 984          DPRINT("Memory area already occupied\n");
 985          return STATUS_CONFLICTING_ADDRESSES;
 986       }
 987    }
 988
 989     //
 990     // Is this a static memory area?
 991     //
 992     if (Type & MEMORY_AREA_STATIC)
 993     {
 994         //
 995         // Use the static array instead of the pool
 996         //
 997         ASSERT(MiStaticMemoryAreaCount < MI_STATIC_MEMORY_AREAS);
 998         MemoryArea = &MiStaticMemoryAreas[MiStaticMemoryAreaCount++];
 999         Type &= ~MEMORY_AREA_STATIC;
1000     }
1001     else
1002     {
1003         //
1004         // Allocate the memory area from nonpaged pool
1005         //
1006         MemoryArea = ExAllocatePoolWithTag(NonPagedPool,
1007                                            sizeof(MEMORY_AREA),
1008                                            TAG_MAREA);
1009     }
1010
1011     if (!MemoryArea) return STATUS_NO_MEMORY;
1012
1013    RtlZeroMemory(MemoryArea, sizeof(MEMORY_AREA));
1014    MemoryArea->Type = Type;
1015    MemoryArea->StartingAddress = *BaseAddress;
1016    MemoryArea->EndingAddress = (PVOID)((ULONG_PTR)*BaseAddress + tmpLength);
1017    MemoryArea->Protect = Protect;
1018    MemoryArea->Flags = AllocationFlags;
1019    //MemoryArea->LockCount = 0;
1020    MemoryArea->PageOpCount = 0;
1021    MemoryArea->DeleteInProgress = FALSE;
1022
1023    MmInsertMemoryArea(AddressSpace, MemoryArea);
1024
1025    *Result = MemoryArea;
1026
1027    DPRINT("MmCreateMemoryArea() succeeded (%p)\n", *BaseAddress);
1028    return STATUS_SUCCESS;
1029 }
1030
1031 VOID NTAPI
1032 MmMapMemoryArea(PVOID BaseAddress,
1033                 ULONG Length,
1034                 ULONG Consumer,
1035                 ULONG Protection)
1036 {
1037    ULONG i;
1038    NTSTATUS Status;
1039
1040    for (i = 0; i < PAGE_ROUND_UP(Length) / PAGE_SIZE; i++)
1041    {
1042       PFN_TYPE Page;
1043
1044       Status = MmRequestPageMemoryConsumer(Consumer, TRUE, &Page);
1045       if (!NT_SUCCESS(Status))
1046       {
1047          DPRINT1("Unable to allocate page\n");
1048          KeBugCheck(MEMORY_MANAGEMENT);
1049       }
1050       Status = MmCreateVirtualMapping (NULL,
1051                                        (PVOID)((ULONG_PTR)BaseAddress + (i * PAGE_SIZE)),
1052                                        Protection,
1053                                        &Page,
1054                                        1);
1055       if (!NT_SUCCESS(Status))
1056       {
1057          DPRINT1("Unable to create virtual mapping\n");
1058          KeBugCheck(MEMORY_MANAGEMENT);
1059       }
1060    }
1061 }
1062
1063
1064 VOID NTAPI
1065 MmReleaseMemoryAreaIfDecommitted(PEPROCESS Process,
1066                                  PMMSUPPORT AddressSpace,
1067                                  PVOID BaseAddress)
1068 {
1069    PMEMORY_AREA MemoryArea;
1070    PLIST_ENTRY Entry;
1071    PMM_REGION Region;
1072    BOOLEAN Reserved;
1073
1074    MmVerifyMemoryAreas(AddressSpace);
1075
1076    MemoryArea = MmLocateMemoryAreaByAddress(AddressSpace, BaseAddress);
1077    if (MemoryArea != NULL)
1078    {
1079       Entry = MemoryArea->Data.VirtualMemoryData.RegionListHead.Flink;
1080       Reserved = TRUE;
1081       while (Reserved && Entry != &MemoryArea->Data.VirtualMemoryData.RegionListHead)
1082       {
1083          Region = CONTAINING_RECORD(Entry, MM_REGION, RegionListEntry);
1084          Reserved = (MEM_RESERVE == Region->Type);
1085          Entry = Entry->Flink;
1086       }
1087
1088       if (Reserved)
1089       {
1090          MmFreeVirtualMemory(Process, MemoryArea);
1091       }
1092    }
1093 }
1094
1095 /* EOF */