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