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
 736    if (MemoryArea->Type != MEMORY_AREA_OWNED_BY_ARM3)
 737    {
 738        PEPROCESS CurrentProcess = PsGetCurrentProcess();
 739        PEPROCESS Process = MmGetAddressSpaceOwner(AddressSpace);
 740
 741        if (Process != NULL &&
 742            Process != CurrentProcess)
 743        {
 744           KeAttachProcess(&Process->Pcb);
 745        }
 746
 747        EndAddress = MM_ROUND_UP(MemoryArea->EndingAddress, PAGE_SIZE);
 748        for (Address = (ULONG_PTR)MemoryArea->StartingAddress;
 749             Address < (ULONG_PTR)EndAddress;
 750             Address += PAGE_SIZE)
 751        {
 752           if (MemoryArea->Type == MEMORY_AREA_IO_MAPPING)
 753           {
 754              MmRawDeleteVirtualMapping((PVOID)Address);
 755           }
 756           else
 757           {
 758              BOOLEAN Dirty = FALSE;
 759              SWAPENTRY SwapEntry = 0;
 760              PFN_NUMBER Page = 0;
 761
 762              if (MmIsPageSwapEntry(Process, (PVOID)Address))
 763              {
 764                 MmDeletePageFileMapping(Process, (PVOID)Address, &SwapEntry);
 765              }
 766              else
 767              {
 768                 MmDeleteVirtualMapping(Process, (PVOID)Address, FALSE, &Dirty, &Page);
 769              }
 770              if (FreePage != NULL)
 771              {
 772                 FreePage(FreePageContext, MemoryArea, (PVOID)Address,
 773                          Page, SwapEntry, (BOOLEAN)Dirty);
 774              }
 775           }
 776        }
 777
 778        if (Process != NULL &&
 779            Process != CurrentProcess)
 780        {
 781           KeDetachProcess();
 782        }
 783     }
 784
 785    /* Remove the tree item. */
 786    {
 787       if (MemoryArea->Parent != NULL)
 788       {
 789          if (MemoryArea->Parent->LeftChild == MemoryArea)
 790             ParentReplace = &MemoryArea->Parent->LeftChild;
 791          else
 792             ParentReplace = &MemoryArea->Parent->RightChild;
 793       }
 794       else
 795          ParentReplace = (PMEMORY_AREA*)&AddressSpace->WorkingSetExpansionLinks.Flink;
 796
 797       if (MemoryArea->RightChild == NULL)
 798       {
 799          *ParentReplace = MemoryArea->LeftChild;
 800          if (MemoryArea->LeftChild)
 801             MemoryArea->LeftChild->Parent = MemoryArea->Parent;
 802       }
 803       else
 804       {
 805          if (MemoryArea->RightChild->LeftChild == NULL)
 806          {
 807             MemoryArea->RightChild->LeftChild = MemoryArea->LeftChild;
 808             if (MemoryArea->LeftChild)
 809                MemoryArea->LeftChild->Parent = MemoryArea->RightChild;
 810
 811             *ParentReplace = MemoryArea->RightChild;
 812             MemoryArea->RightChild->Parent = MemoryArea->Parent;
 813          }
 814          else
 815          {
 816             PMEMORY_AREA LowestNode;
 817
 818             LowestNode = MemoryArea->RightChild->LeftChild;
 819             while (LowestNode->LeftChild != NULL)
 820                LowestNode = LowestNode->LeftChild;
 821
 822             LowestNode->Parent->LeftChild = LowestNode->RightChild;
 823             if (LowestNode->RightChild)
 824                LowestNode->RightChild->Parent = LowestNode->Parent;
 825
 826             LowestNode->LeftChild = MemoryArea->LeftChild;
 827             if (MemoryArea->LeftChild)
 828                MemoryArea->LeftChild->Parent = LowestNode;
 829
 830             LowestNode->RightChild = MemoryArea->RightChild;
 831             MemoryArea->RightChild->Parent = LowestNode;
 832
 833             *ParentReplace = LowestNode;
 834             LowestNode->Parent = MemoryArea->Parent;
 835          }
 836       }
 837    }
 838
 839    ExFreePoolWithTag(MemoryArea, TAG_MAREA);
 840
 841    DPRINT("MmFreeMemoryAreaByNode() succeeded\n");
 842
 843    return STATUS_SUCCESS;
 844 }
 845
 846 /**
 847  * @name MmFreeMemoryAreaByPtr
 848  *
 849  * Free an existing memory area given a pointer inside it.
 850  *
 851  * @param AddressSpace
 852  *        Address space to free the area from.
 853  * @param BaseAddress
 854  *        Address in the memory area we're about to free.
 855  * @param FreePage
 856  *        Callback function for each freed page.
 857  * @param FreePageContext
 858  *        Context passed to the callback function.
 859  *
 860  * @return Status
 861  *
 862  * @see MmFreeMemoryArea
 863  *
 864  * @todo Should we require the BaseAddress to be really the starting
 865  *       address of the memory area or is the current relaxed check
 866  *       (BaseAddress can point anywhere in the memory area) acceptable?
 867  *
 868  * @remarks Lock the address space before calling this function.
 869  */
 870
 871 NTSTATUS NTAPI
 872 MmFreeMemoryAreaByPtr(
 873    PMMSUPPORT AddressSpace,
 874    PVOID BaseAddress,
 875    PMM_FREE_PAGE_FUNC FreePage,
 876    PVOID FreePageContext)
 877 {
 878    PMEMORY_AREA MemoryArea;
 879
 880    DPRINT("MmFreeMemoryArea(AddressSpace %p, BaseAddress %p, "
 881           "FreePageContext %p)\n", AddressSpace, BaseAddress,
 882           FreePageContext);
 883
 884    MmVerifyMemoryAreas(AddressSpace);
 885
 886    MemoryArea = MmLocateMemoryAreaByAddress(AddressSpace,
 887                                             BaseAddress);
 888    if (MemoryArea == NULL)
 889    {
 890       KeBugCheck(MEMORY_MANAGEMENT);
 891       return(STATUS_UNSUCCESSFUL);
 892    }
 893
 894    return MmFreeMemoryArea(AddressSpace, MemoryArea, FreePage, FreePageContext);
 895 }
 896
 897 /**
 898  * @name MmCreateMemoryArea
 899  *
 900  * Create a memory area.
 901  *
 902  * @param AddressSpace
 903  *        Address space to create the area in.
 904  * @param Type
 905  *        Type of the memory area.
 906  * @param BaseAddress
 907  *        Base address for the memory area we're about the create. On
 908  *        input it contains either 0 (auto-assign address) or preferred
 909  *        address. On output it contains the starting address of the
 910  *        newly created area.
 911  * @param Length
 912  *        Length of the area to allocate.
 913  * @param Attributes
 914  *        Protection attributes for the memory area.
 915  * @param Result
 916  *        Receives a pointer to the memory area on successful exit.
 917  *
 918  * @return Status
 919  *
 920  * @remarks Lock the address space before calling this function.
 921  */
 922
 923 NTSTATUS NTAPI
 924 MmCreateMemoryArea(PMMSUPPORT AddressSpace,
 925                    ULONG Type,
 926                    PVOID *BaseAddress,
 927                    ULONG_PTR Length,
 928                    ULONG Protect,
 929                    PMEMORY_AREA *Result,
 930                    BOOLEAN FixedAddress,
 931                    ULONG AllocationFlags,
 932                    PHYSICAL_ADDRESS BoundaryAddressMultiple)
 933 {
 934    PVOID EndAddress;
 935    ULONG Granularity;
 936    ULONG tmpLength;
 937    PMEMORY_AREA MemoryArea;
 938
 939    DPRINT("MmCreateMemoryArea(Type %d, BaseAddress %p, "
 940           "*BaseAddress %p, Length %p, AllocationFlags %x, "
 941           "FixedAddress %x, Result %p)\n",
 942           Type, BaseAddress, *BaseAddress, Length, AllocationFlags,
 943           FixedAddress, Result);
 944
 945    MmVerifyMemoryAreas(AddressSpace);
 946
 947    Granularity = (MEMORY_AREA_VIRTUAL_MEMORY == Type ? MM_VIRTMEM_GRANULARITY : PAGE_SIZE);
 948    if ((*BaseAddress) == 0 && !FixedAddress)
 949    {
 950       tmpLength = PAGE_ROUND_UP(Length);
 951       *BaseAddress = MmFindGap(AddressSpace,
 952                                tmpLength,
 953                                Granularity,
 954                                (AllocationFlags & MEM_TOP_DOWN) == MEM_TOP_DOWN);
 955       if ((*BaseAddress) == 0)
 956       {
 957          DPRINT("No suitable gap\n");
 958          return STATUS_NO_MEMORY;
 959       }
 960    }
 961    else
 962    {
 963       tmpLength = Length + ((ULONG_PTR) *BaseAddress
 964                          - (ULONG_PTR) MM_ROUND_DOWN(*BaseAddress, Granularity));
 965       *BaseAddress = MM_ROUND_DOWN(*BaseAddress, Granularity);
 966
 967       if (!MmGetAddressSpaceOwner(AddressSpace) && *BaseAddress < MmSystemRangeStart)
 968       {
 969          return STATUS_ACCESS_VIOLATION;
 970       }
 971
 972       if (MmGetAddressSpaceOwner(AddressSpace) &&
 973           (ULONG_PTR)(*BaseAddress) + tmpLength > (ULONG_PTR)MmSystemRangeStart)
 974       {
 975          return STATUS_ACCESS_VIOLATION;
 976       }
 977
 978       if (BoundaryAddressMultiple.QuadPart != 0)
 979       {
 980          EndAddress = ((char*)(*BaseAddress)) + tmpLength-1;
 981          ASSERT(((ULONG_PTR)*BaseAddress/BoundaryAddressMultiple.QuadPart) == ((DWORD_PTR)EndAddress/BoundaryAddressMultiple.QuadPart));
 982       }
 983
 984       if (MmLocateMemoryAreaByRegion(AddressSpace,
 985                                      *BaseAddress,
 986                                      tmpLength) != NULL)
 987       {
 988          DPRINT("Memory area already occupied\n");
 989          return STATUS_CONFLICTING_ADDRESSES;
 990       }
 991    }
 992
 993     //
 994     // Is this a static memory area?
 995     //
 996     if (Type & MEMORY_AREA_STATIC)
 997     {
 998         //
 999         // Use the static array instead of the pool
1000         //
1001         ASSERT(MiStaticMemoryAreaCount < MI_STATIC_MEMORY_AREAS);
1002         MemoryArea = &MiStaticMemoryAreas[MiStaticMemoryAreaCount++];
1003         Type &= ~MEMORY_AREA_STATIC;
1004     }
1005     else
1006     {
1007         //
1008         // Allocate the memory area from nonpaged pool
1009         //
1010         MemoryArea = ExAllocatePoolWithTag(NonPagedPool,
1011                                            sizeof(MEMORY_AREA),
1012                                            TAG_MAREA);
1013     }
1014
1015     if (!MemoryArea) return STATUS_NO_MEMORY;
1016
1017    RtlZeroMemory(MemoryArea, sizeof(MEMORY_AREA));
1018    MemoryArea->Type = Type;
1019    MemoryArea->StartingAddress = *BaseAddress;
1020    MemoryArea->EndingAddress = (PVOID)((ULONG_PTR)*BaseAddress + tmpLength);
1021    MemoryArea->Protect = Protect;
1022    MemoryArea->Flags = AllocationFlags;
1023    //MemoryArea->LockCount = 0;
1024    MemoryArea->PageOpCount = 0;
1025    MemoryArea->DeleteInProgress = FALSE;
1026
1027    MmInsertMemoryArea(AddressSpace, MemoryArea);
1028
1029    *Result = MemoryArea;
1030
1031    DPRINT("MmCreateMemoryArea() succeeded (%p)\n", *BaseAddress);
1032    return STATUS_SUCCESS;
1033 }
1034
1035 VOID NTAPI
1036 MmMapMemoryArea(PVOID BaseAddress,
1037                 ULONG Length,
1038                 ULONG Consumer,
1039                 ULONG Protection)
1040 {
1041    ULONG i;
1042    NTSTATUS Status;
1043
1044    for (i = 0; i < PAGE_ROUND_UP(Length) / PAGE_SIZE; i++)
1045    {
1046       PFN_NUMBER Page;
1047
1048       Status = MmRequestPageMemoryConsumer(Consumer, TRUE, &Page);
1049       if (!NT_SUCCESS(Status))
1050       {
1051          DPRINT1("Unable to allocate page\n");
1052          KeBugCheck(MEMORY_MANAGEMENT);
1053       }
1054       Status = MmCreateVirtualMapping (NULL,
1055                                        (PVOID)((ULONG_PTR)BaseAddress + (i * PAGE_SIZE)),
1056                                        Protection,
1057                                        &Page,
1058                                        1);
1059       if (!NT_SUCCESS(Status))
1060       {
1061          DPRINT1("Unable to create virtual mapping\n");
1062          KeBugCheck(MEMORY_MANAGEMENT);
1063       }
1064    }
1065 }
1066
1067
1068 VOID NTAPI
1069 MmReleaseMemoryAreaIfDecommitted(PEPROCESS Process,
1070                                  PMMSUPPORT AddressSpace,
1071                                  PVOID BaseAddress)
1072 {
1073    PMEMORY_AREA MemoryArea;
1074    PLIST_ENTRY Entry;
1075    PMM_REGION Region;
1076    BOOLEAN Reserved;
1077
1078    MmVerifyMemoryAreas(AddressSpace);
1079
1080    MemoryArea = MmLocateMemoryAreaByAddress(AddressSpace, BaseAddress);
1081    if (MemoryArea != NULL)
1082    {
1083       Entry = MemoryArea->Data.VirtualMemoryData.RegionListHead.Flink;
1084       Reserved = TRUE;
1085       while (Reserved && Entry != &MemoryArea->Data.VirtualMemoryData.RegionListHead)
1086       {
1087          Region = CONTAINING_RECORD(Entry, MM_REGION, RegionListEntry);
1088          Reserved = (MEM_RESERVE == Region->Type);
1089          Entry = Entry->Flink;
1090       }
1091
1092       if (Reserved)
1093       {
1094          MmFreeVirtualMemory(Process, MemoryArea);
1095       }
1096    }
1097 }
1098
1099 /* EOF */