reactos/ntoskrnl/mm/freelist.c

   1 /*
   2  * COPYRIGHT:       See COPYING in the top level directory
   3  * PROJECT:         ReactOS kernel
   4  * FILE:            ntoskrnl/mm/freelist.c
   5  * PURPOSE:         Handle the list of free physical pages
   6  *
   7  * PROGRAMMERS:     David Welch (welch@cwcom.net)
   8  *                  Robert Bergkvist
   9  */
  10
  11 /* INCLUDES ****************************************************************/
  12
  13 #include <ntoskrnl.h>
  14 #define NDEBUG
  15 #include <debug.h>
  16
  17 #if defined (ALLOC_PRAGMA)
  18 #pragma alloc_text(INIT, MmInitializePageList)
  19 #endif
  20
  21 #define MODULE_INVOLVED_IN_ARM3
  22 #include "ARM3/miarm.h"
  23
  24 /* GLOBALS ****************************************************************/
  25
  26 // ReactOS to NT Physical Page Descriptor Entry Legacy Mapping Definitions
  27 #define PHYSICAL_PAGE        MMPFN
  28 #define PPHYSICAL_PAGE       PMMPFN
  29
  30 PPHYSICAL_PAGE MmPfnDatabase;
  31
  32 PFN_NUMBER MmAvailablePages;
  33 PFN_NUMBER MmResidentAvailablePages;
  34 PFN_NUMBER MmResidentAvailableAtInit;
  35
  36 SIZE_T MmTotalCommittedPages;
  37 SIZE_T MmSharedCommit;
  38 SIZE_T MmDriverCommit;
  39 SIZE_T MmProcessCommit;
  40 SIZE_T MmPagedPoolCommit;
  41 SIZE_T MmPeakCommitment;
  42 SIZE_T MmtotalCommitLimitMaximum;
  43
  44 static RTL_BITMAP MiUserPfnBitMap;
  45
  46 /* FUNCTIONS *************************************************************/
  47
  48 VOID
  49 NTAPI
  50 MiInitializeUserPfnBitmap(VOID)
  51 {
  52     PVOID Bitmap;
  53
  54     /* Allocate enough buffer for the PFN bitmap and align it on 32-bits */
  55     Bitmap = ExAllocatePoolWithTag(NonPagedPool,
  56                                    (((MmHighestPhysicalPage + 1) + 31) / 32) * 4,
  57                                    '  mM');
  58     ASSERT(Bitmap);
  59
  60     /* Initialize it and clear all the bits to begin with */
  61     RtlInitializeBitMap(&MiUserPfnBitMap,
  62                         Bitmap,
  63                         (ULONG)MmHighestPhysicalPage + 1);
  64     RtlClearAllBits(&MiUserPfnBitMap);
  65 }
  66
  67 PFN_NUMBER
  68 NTAPI
  69 MmGetLRUFirstUserPage(VOID)
  70 {
  71     ULONG Position;
  72     KIRQL OldIrql;
  73
  74     /* Find the first user page */
  75     OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
  76     Position = RtlFindSetBits(&MiUserPfnBitMap, 1, 0);
  77     KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
  78     if (Position == 0xFFFFFFFF) return 0;
  79
  80     /* Return it */
  81     ASSERT(Position != 0);
  82     ASSERT_IS_ROS_PFN(MiGetPfnEntry(Position));
  83     return Position;
  84 }
  85
  86 VOID
  87 NTAPI
  88 MmInsertLRULastUserPage(PFN_NUMBER Pfn)
  89 {
  90     KIRQL OldIrql;
  91
  92     /* Set the page as a user page */
  93     ASSERT(Pfn != 0);
  94     ASSERT_IS_ROS_PFN(MiGetPfnEntry(Pfn));
  95     OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
  96     RtlSetBit(&MiUserPfnBitMap, (ULONG)Pfn);
  97     KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
  98 }
  99
 100 PFN_NUMBER
 101 NTAPI
 102 MmGetLRUNextUserPage(PFN_NUMBER PreviousPfn)
 103 {
 104     ULONG Position;
 105     KIRQL OldIrql;
 106
 107     /* Find the next user page */
 108     OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 109     Position = RtlFindSetBits(&MiUserPfnBitMap, 1, (ULONG)PreviousPfn + 1);
 110     KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
 111     if (Position == 0xFFFFFFFF) return 0;
 112
 113     /* Return it */
 114     ASSERT(Position != 0);
 115     ASSERT_IS_ROS_PFN(MiGetPfnEntry(Position));
 116     return Position;
 117 }
 118
 119 VOID
 120 NTAPI
 121 MmRemoveLRUUserPage(PFN_NUMBER Page)
 122 {
 123     /* Unset the page as a user page */
 124     ASSERT(Page != 0);
 125     ASSERT_IS_ROS_PFN(MiGetPfnEntry(Page));
 126     RtlClearBit(&MiUserPfnBitMap, (ULONG)Page);
 127 }
 128
 129 BOOLEAN
 130 NTAPI
 131 MiIsPfnFree(IN PMMPFN Pfn1)
 132 {
 133     /* Must be a free or zero page, with no references, linked */
 134     return ((Pfn1->u3.e1.PageLocation <= StandbyPageList) &&
 135             (Pfn1->u1.Flink) &&
 136             (Pfn1->u2.Blink) &&
 137             !(Pfn1->u3.e2.ReferenceCount));
 138 }
 139
 140 BOOLEAN
 141 NTAPI
 142 MiIsPfnInUse(IN PMMPFN Pfn1)
 143 {
 144     /* Standby list or higher, unlinked, and with references */
 145     return !MiIsPfnFree(Pfn1);
 146 }
 147
 148 PMDL
 149 NTAPI
 150 MiAllocatePagesForMdl(IN PHYSICAL_ADDRESS LowAddress,
 151                       IN PHYSICAL_ADDRESS HighAddress,
 152                       IN PHYSICAL_ADDRESS SkipBytes,
 153                       IN SIZE_T TotalBytes,
 154                       IN MI_PFN_CACHE_ATTRIBUTE CacheAttribute,
 155                       IN ULONG MdlFlags)
 156 {
 157     PMDL Mdl;
 158     PFN_NUMBER PageCount, LowPage, HighPage, SkipPages, PagesFound = 0, Page;
 159     PPFN_NUMBER MdlPage, LastMdlPage;
 160     KIRQL OldIrql;
 161     PPHYSICAL_PAGE Pfn1;
 162     INT LookForZeroedPages;
 163     ASSERT(KeGetCurrentIrql() <= APC_LEVEL);
 164
 165     //
 166     // Convert the low address into a PFN
 167     //
 168     LowPage = (PFN_NUMBER)(LowAddress.QuadPart >> PAGE_SHIFT);
 169
 170     //
 171     // Convert, and normalize, the high address into a PFN
 172     //
 173     HighPage = (PFN_NUMBER)(HighAddress.QuadPart >> PAGE_SHIFT);
 174     if (HighPage > MmHighestPhysicalPage) HighPage = MmHighestPhysicalPage;
 175
 176     //
 177     // Validate skipbytes and convert them into pages
 178     //
 179     if (BYTE_OFFSET(SkipBytes.LowPart)) return NULL;
 180     SkipPages = (PFN_NUMBER)(SkipBytes.QuadPart >> PAGE_SHIFT);
 181
 182     /* This isn't supported at all */
 183     if (SkipPages) DPRINT1("WARNING: Caller requesting SkipBytes, MDL might be mismatched\n");
 184
 185     //
 186     // Now compute the number of pages the MDL will cover
 187     //
 188     PageCount = (PFN_NUMBER)ADDRESS_AND_SIZE_TO_SPAN_PAGES(0, TotalBytes);
 189     do
 190     {
 191         //
 192         // Try creating an MDL for these many pages
 193         //
 194         Mdl = MmCreateMdl(NULL, NULL, PageCount << PAGE_SHIFT);
 195         if (Mdl) break;
 196
 197         //
 198         // This function is not required to return the amount of pages requested
 199         // In fact, it can return as little as 1 page, and callers are supposed
 200         // to deal with this scenario. So re-attempt the allocation with less
 201         // pages than before, and see if it worked this time.
 202         //
 203         PageCount -= (PageCount >> 4);
 204     } while (PageCount);
 205
 206     //
 207     // Wow, not even a single page was around!
 208     //
 209     if (!Mdl) return NULL;
 210
 211     //
 212     // This is where the page array starts....
 213     //
 214     MdlPage = (PPFN_NUMBER)(Mdl + 1);
 215
 216     //
 217     // Lock the PFN database
 218     //
 219     OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 220
 221     //
 222     // Are we looking for any pages, without discriminating?
 223     //
 224     if ((LowPage == 0) && (HighPage == MmHighestPhysicalPage))
 225     {
 226         //
 227         // Well then, let's go shopping
 228         //
 229         while (PagesFound < PageCount)
 230         {
 231             /* Grab a page */
 232             MI_SET_USAGE(MI_USAGE_MDL);
 233             MI_SET_PROCESS2("Kernel");
 234             Page = MiRemoveAnyPage(0);
 235             if (Page == 0)
 236             {
 237                 /* This is not good... hopefully we have at least SOME pages */
 238                 ASSERT(PagesFound);
 239                 break;
 240             }
 241
 242             /* Grab the page entry for it */
 243             Pfn1 = MiGetPfnEntry(Page);
 244
 245             //
 246             // Make sure it's really free
 247             //
 248             ASSERT(Pfn1->u3.e2.ReferenceCount == 0);
 249
 250             /* Now setup the page and mark it */
 251             Pfn1->u3.e2.ReferenceCount = 1;
 252             Pfn1->u2.ShareCount = 1;
 253             MI_SET_PFN_DELETED(Pfn1);
 254             Pfn1->u4.PteFrame = 0x1FFEDCB;
 255             Pfn1->u3.e1.StartOfAllocation = 1;
 256             Pfn1->u3.e1.EndOfAllocation = 1;
 257             Pfn1->u4.VerifierAllocation = 0;
 258
 259             //
 260             // Save it into the MDL
 261             //
 262             *MdlPage++ = MiGetPfnEntryIndex(Pfn1);
 263             PagesFound++;
 264         }
 265     }
 266     else
 267     {
 268         //
 269         // You want specific range of pages. We'll do this in two runs
 270         //
 271         for (LookForZeroedPages = 1; LookForZeroedPages >= 0; LookForZeroedPages--)
 272         {
 273             //
 274             // Scan the range you specified
 275             //
 276             for (Page = LowPage; Page < HighPage; Page++)
 277             {
 278                 //
 279                 // Get the PFN entry for this page
 280                 //
 281                 Pfn1 = MiGetPfnEntry(Page);
 282                 ASSERT(Pfn1);
 283
 284                 //
 285                 // Make sure it's free and if this is our first pass, zeroed
 286                 //
 287                 if (MiIsPfnInUse(Pfn1)) continue;
 288                 if ((Pfn1->u3.e1.PageLocation == ZeroedPageList) != LookForZeroedPages) continue;
 289
 290                 /* Remove the page from the free or zero list */
 291                 ASSERT(Pfn1->u3.e1.ReadInProgress == 0);
 292                 MI_SET_USAGE(MI_USAGE_MDL);
 293                 MI_SET_PROCESS2("Kernel");
 294                 MiUnlinkFreeOrZeroedPage(Pfn1);
 295
 296                 //
 297                 // Sanity checks
 298                 //
 299                 ASSERT(Pfn1->u3.e2.ReferenceCount == 0);
 300
 301                 //
 302                 // Now setup the page and mark it
 303                 //
 304                 Pfn1->u3.e2.ReferenceCount = 1;
 305                 Pfn1->u2.ShareCount = 1;
 306                 MI_SET_PFN_DELETED(Pfn1);
 307                 Pfn1->u4.PteFrame = 0x1FFEDCB;
 308                 Pfn1->u3.e1.StartOfAllocation = 1;
 309                 Pfn1->u3.e1.EndOfAllocation = 1;
 310                 Pfn1->u4.VerifierAllocation = 0;
 311
 312                 //
 313                 // Save this page into the MDL
 314                 //
 315                 *MdlPage++ = Page;
 316                 if (++PagesFound == PageCount) break;
 317             }
 318
 319             //
 320             // If the first pass was enough, don't keep going, otherwise, go again
 321             //
 322             if (PagesFound == PageCount) break;
 323         }
 324     }
 325
 326     //
 327     // Now release the PFN count
 328     //
 329     KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
 330
 331     //
 332     // We might've found less pages, but not more ;-)
 333     //
 334     if (PagesFound != PageCount) ASSERT(PagesFound < PageCount);
 335     if (!PagesFound)
 336     {
 337         //
 338         // If we didn' tfind any pages at all, fail
 339         //
 340         DPRINT1("NO MDL PAGES!\n");
 341         ExFreePool(Mdl);
 342         return NULL;
 343     }
 344
 345     //
 346     // Write out how many pages we found
 347     //
 348     Mdl->ByteCount = (ULONG)(PagesFound << PAGE_SHIFT);
 349
 350     //
 351     // Terminate the MDL array if there's certain missing pages
 352     //
 353     if (PagesFound != PageCount) *MdlPage = LIST_HEAD;
 354
 355     //
 356     // Now go back and loop over all the MDL pages
 357     //
 358     MdlPage = (PPFN_NUMBER)(Mdl + 1);
 359     LastMdlPage = MdlPage + PagesFound;
 360     while (MdlPage < LastMdlPage)
 361     {
 362         //
 363         // Check if we've reached the end
 364         //
 365         Page = *MdlPage++;
 366         if (Page == LIST_HEAD) break;
 367
 368         //
 369         // Get the PFN entry for the page and check if we should zero it out
 370         //
 371         Pfn1 = MiGetPfnEntry(Page);
 372         ASSERT(Pfn1);
 373         if (Pfn1->u3.e1.PageLocation != ZeroedPageList) MiZeroPhysicalPage(Page);
 374         Pfn1->u3.e1.PageLocation = ActiveAndValid;
 375     }
 376
 377     //
 378     // We're done, mark the pages as locked
 379     //
 380     Mdl->Process = NULL;
 381     Mdl->MdlFlags |= MDL_PAGES_LOCKED;
 382     return Mdl;
 383 }
 384
 385 VOID
 386 NTAPI
 387 MmSetRmapListHeadPage(PFN_NUMBER Pfn, PMM_RMAP_ENTRY ListHead)
 388 {
 389     KIRQL oldIrql;
 390     PMMPFN Pfn1;
 391
 392     oldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 393     Pfn1 = MiGetPfnEntry(Pfn);
 394     ASSERT(Pfn1);
 395     ASSERT_IS_ROS_PFN(Pfn1);
 396
 397     if (ListHead)
 398     {
 399         /* Should not be trying to insert an RMAP for a non-active page */
 400         ASSERT(MiIsPfnInUse(Pfn1) == TRUE);
 401
 402         /* Set the list head address */
 403         MI_GET_ROS_DATA(Pfn1)->RmapListHead = ListHead;
 404     }
 405     else
 406     {
 407         /* ReactOS semantics dictate the page is STILL active right now */
 408         ASSERT(MiIsPfnInUse(Pfn1) == TRUE);
 409
 410         /* In this case, the RMAP is actually being removed, so clear field */
 411         MI_GET_ROS_DATA(Pfn1)->RmapListHead = NULL;
 412
 413         /* ReactOS semantics will now release the page, which will make it free and enter a colored list */
 414     }
 415
 416     KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
 417 }
 418
 419 PMM_RMAP_ENTRY
 420 NTAPI
 421 MmGetRmapListHeadPage(PFN_NUMBER Pfn)
 422 {
 423     KIRQL oldIrql;
 424     PMM_RMAP_ENTRY ListHead;
 425     PMMPFN Pfn1;
 426
 427     /* Lock PFN database */
 428     oldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 429
 430     /* Get the entry */
 431     Pfn1 = MiGetPfnEntry(Pfn);
 432     ASSERT(Pfn1);
 433     ASSERT_IS_ROS_PFN(Pfn1);
 434
 435     /* Get the list head */
 436     ListHead = MI_GET_ROS_DATA(Pfn1)->RmapListHead;
 437
 438     /* Should not have an RMAP for a non-active page */
 439     ASSERT(MiIsPfnInUse(Pfn1) == TRUE);
 440
 441     /* Release PFN database and return rmap list head */
 442     KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
 443     return ListHead;
 444 }
 445
 446 VOID
 447 NTAPI
 448 MmSetSavedSwapEntryPage(PFN_NUMBER Pfn,  SWAPENTRY SwapEntry)
 449 {
 450    KIRQL oldIrql;
 451    PPHYSICAL_PAGE Page;
 452
 453    Page = MiGetPfnEntry(Pfn);
 454    ASSERT(Page);
 455    ASSERT_IS_ROS_PFN(Page);
 456
 457    oldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 458    MI_GET_ROS_DATA(Page)->SwapEntry = SwapEntry;
 459    KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
 460 }
 461
 462 SWAPENTRY
 463 NTAPI
 464 MmGetSavedSwapEntryPage(PFN_NUMBER Pfn)
 465 {
 466    SWAPENTRY SwapEntry;
 467    KIRQL oldIrql;
 468    PPHYSICAL_PAGE Page;
 469
 470    Page = MiGetPfnEntry(Pfn);
 471    ASSERT(Page);
 472    ASSERT_IS_ROS_PFN(Page);
 473
 474    oldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 475    SwapEntry = MI_GET_ROS_DATA(Page)->SwapEntry;
 476    KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
 477
 478    return(SwapEntry);
 479 }
 480
 481 VOID
 482 NTAPI
 483 MmReferencePage(PFN_NUMBER Pfn)
 484 {
 485    PPHYSICAL_PAGE Page;
 486
 487    DPRINT("MmReferencePage(PysicalAddress %x)\n", Pfn << PAGE_SHIFT);
 488
 489    if (Pfn == 0 || Pfn > MmHighestPhysicalPage)
 490    {
 491       return;
 492    }
 493
 494    Page = MiGetPfnEntry(Pfn);
 495    ASSERT(Page);
 496    ASSERT_IS_ROS_PFN(Page);
 497
 498    Page->u3.e2.ReferenceCount++;
 499 }
 500
 501 ULONG
 502 NTAPI
 503 MmGetReferenceCountPage(PFN_NUMBER Pfn)
 504 {
 505    KIRQL oldIrql;
 506    ULONG RCount;
 507    PPHYSICAL_PAGE Page;
 508
 509    DPRINT("MmGetReferenceCountPage(PhysicalAddress %x)\n", Pfn << PAGE_SHIFT);
 510
 511    oldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
 512    Page = MiGetPfnEntry(Pfn);
 513    ASSERT(Page);
 514    ASSERT_IS_ROS_PFN(Page);
 515
 516    RCount = Page->u3.e2.ReferenceCount;
 517
 518    KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
 519    return(RCount);
 520 }
 521
 522 BOOLEAN
 523 NTAPI
 524 MmIsPageInUse(PFN_NUMBER Pfn)
 525 {
 526     return MiIsPfnInUse(MiGetPfnEntry(Pfn));
 527 }
 528
 529 VOID
 530 NTAPI
 531 MmDereferencePage(PFN_NUMBER Pfn)
 532 {
 533    PPHYSICAL_PAGE Page;
 534    DPRINT("MmDereferencePage(PhysicalAddress %x)\n", Pfn << PAGE_SHIFT);
 535
 536    Page = MiGetPfnEntry(Pfn);
 537    ASSERT(Page);
 538    ASSERT_IS_ROS_PFN(Page);
 539
 540    Page->u3.e2.ReferenceCount--;
 541    if (Page->u3.e2.ReferenceCount == 0)
 542    {
 543         /* Mark the page temporarily as valid, we're going to make it free soon */
 544         Page->u3.e1.PageLocation = ActiveAndValid;
 545
 546         /* It's not a ROS PFN anymore */
 547         Page->u4.AweAllocation = FALSE;
 548         ExFreePool(MI_GET_ROS_DATA(Page));
 549         Page->RosMmData = 0;
 550
 551         /* Bring it back into the free list */
 552         DPRINT("Legacy free: %lx\n", Pfn);
 553         MiInsertPageInFreeList(Pfn);
 554    }
 555 }
 556
 557 PFN_NUMBER
 558 NTAPI
 559 MmAllocPage(ULONG Type)
 560 {
 561    PFN_NUMBER PfnOffset;
 562    PMMPFN Pfn1;
 563
 564    PfnOffset = MiRemoveZeroPage(MI_GET_NEXT_COLOR());
 565
 566    if (!PfnOffset)
 567    {
 568        DPRINT1("MmAllocPage(): Out of memory\n");
 569        return 0;
 570    }
 571
 572    DPRINT("Legacy allocate: %lx\n", PfnOffset);
 573    Pfn1 = MiGetPfnEntry(PfnOffset);
 574    Pfn1->u3.e2.ReferenceCount = 1;
 575    Pfn1->u3.e1.PageLocation = ActiveAndValid;
 576
 577    /* This marks the PFN as a ReactOS PFN */
 578    Pfn1->u4.AweAllocation = TRUE;
 579
 580    /* Allocate the extra ReactOS Data and zero it out */
 581    Pfn1->RosMmData = (LONG)ExAllocatePoolWithTag(NonPagedPool, sizeof(MMROSPFN), 'RsPf');
 582    ASSERT(MI_GET_ROS_DATA(Pfn1) != NULL);
 583    ASSERT_IS_ROS_PFN(Pfn1);
 584    MI_GET_ROS_DATA(Pfn1)->SwapEntry = 0;
 585    MI_GET_ROS_DATA(Pfn1)->RmapListHead = NULL;
 586
 587    return PfnOffset;
 588 }
 589
 590 /* EOF */