reactos/ntoskrnl/mm/marea.c

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