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  * PROGRAMMER:   David Welch (welch@cwcom.net)
   7  * UPDATE HISTORY:
   8  *               27/05/98: Created
   9  *               18/08/98: Added a fix from Robert Bergkvist
  10  */
  11
  12 /* INCLUDES ****************************************************************/
  13
  14 #include <ddk/ntddk.h>
  15 #include <internal/mm.h>
  16 #include <internal/mmhal.h>
  17 #include <internal/ntoskrnl.h>
  18
  19 #define NDEBUG
  20 #include <internal/debug.h>
  21
  22 /* TYPES *******************************************************************/
  23
  24 #define MM_PHYSICAL_PAGE_FREE    (0x1)
  25 #define MM_PHYSICAL_PAGE_USED    (0x2)
  26 #define MM_PHYSICAL_PAGE_BIOS    (0x3)
  27
  28 #define MM_PTYPE(x)              ((x) & 0x3)
  29
  30 typedef struct _PHYSICAL_PAGE
  31 {
  32    ULONG Flags;
  33    LIST_ENTRY ListEntry;
  34    ULONG ReferenceCount;
  35    KEVENT Event;
  36    SWAPENTRY SavedSwapEntry;
  37    ULONG LockCount;
  38 } PHYSICAL_PAGE, *PPHYSICAL_PAGE;
  39
  40 /* GLOBALS ****************************************************************/
  41
  42 static PPHYSICAL_PAGE MmPageArray;
  43
  44 static LIST_ENTRY UsedPageListHead;
  45 static KSPIN_LOCK PageListLock;
  46 static LIST_ENTRY FreePageListHead;
  47 static LIST_ENTRY BiosPageListHead;
  48
  49 /* FUNCTIONS *************************************************************/
  50
  51 PVOID
  52 MmGetContinuousPages(ULONG NumberOfBytes,
  53                      PHYSICAL_ADDRESS HighestAcceptableAddress)
  54 {
  55    ULONG NrPages;
  56    ULONG i;
  57    ULONG start;
  58    ULONG length;
  59    KIRQL oldIrql;
  60
  61    NrPages = PAGE_ROUND_UP(NumberOfBytes) / PAGESIZE;
  62
  63    KeAcquireSpinLock(&PageListLock, &oldIrql);
  64
  65    start = -1;
  66    length = 0;
  67    for (i = 0; i < (HighestAcceptableAddress.QuadPart / PAGESIZE); i++)
  68      {
  69         if (MmPageArray[i].Flags & MM_PHYSICAL_PAGE_FREE)
  70           {
  71              if (start == -1)
  72                {
  73                   start = i;
  74                   length = 1;
  75                }
  76              else
  77                {
  78                   length++;
  79                }
  80              if (length == NrPages)
  81                {
  82                   break;
  83                }
  84           }
  85         else if (start != -1)
  86           {
  87              start = -1;
  88           }
  89      }
  90    if (start == -1)
  91      {
  92         KeReleaseSpinLock(&PageListLock, oldIrql);
  93         return(NULL);
  94      }
  95    for (i = start; i < (start + length); i++)
  96      {
  97         RemoveEntryList(&MmPageArray[i].ListEntry);
  98         MmPageArray[i].Flags = MM_PHYSICAL_PAGE_USED;
  99         MmPageArray[i].ReferenceCount = 1;
 100         MmPageArray[i].LockCount = 0;
 101         MmPageArray[i].SavedSwapEntry = 0;
 102         InsertTailList(&UsedPageListHead, &MmPageArray[i].ListEntry);
 103      }
 104    return((PVOID)(start * 4096));
 105 }
 106
 107 PVOID MmInitializePageList(PVOID FirstPhysKernelAddress,
 108                            PVOID LastPhysKernelAddress,
 109                            ULONG MemorySizeInPages,
 110                            ULONG LastKernelAddress)
 111 /*
 112  * FUNCTION: Initializes the page list with all pages free
 113  * except those known to be reserved and those used by the kernel
 114  * ARGUMENTS:
 115  *         PageBuffer = Page sized buffer
 116  *         FirstKernelAddress = First physical address used by the kernel
 117  *         LastKernelAddress = Last physical address used by the kernel
 118  */
 119 {
 120    ULONG i;
 121    ULONG Reserved;
 122    NTSTATUS Status;
 123
 124    DPRINT("MmInitializePageList(FirstPhysKernelAddress %x, "
 125           "LastPhysKernelAddress %x, "
 126           "MemorySizeInPages %x, LastKernelAddress %x)\n",
 127           FirstPhysKernelAddress,
 128           LastPhysKernelAddress,
 129           MemorySizeInPages,
 130           LastKernelAddress);
 131
 132    InitializeListHead(&UsedPageListHead);
 133    KeInitializeSpinLock(&PageListLock);
 134    InitializeListHead(&FreePageListHead);
 135    InitializeListHead(&BiosPageListHead);
 136
 137    Reserved = (MemorySizeInPages * sizeof(PHYSICAL_PAGE)) / PAGESIZE;
 138    MmPageArray = (PHYSICAL_PAGE *)LastKernelAddress;
 139
 140    DPRINT("Reserved %d\n", Reserved);
 141
 142    LastKernelAddress = PAGE_ROUND_UP(LastKernelAddress);
 143    LastKernelAddress = ((ULONG)LastKernelAddress + (Reserved * PAGESIZE));
 144    LastPhysKernelAddress = (PVOID)PAGE_ROUND_UP(LastPhysKernelAddress);
 145    LastPhysKernelAddress = LastPhysKernelAddress + (Reserved * PAGESIZE);
 146
 147    MmStats.NrTotalPages = 0;
 148    MmStats.NrSystemPages = 0;
 149    MmStats.NrUserPages = 0;
 150    MmStats.NrReservedPages = 0;
 151    MmStats.NrFreePages = 0;
 152    MmStats.NrLockedPages = 0;
 153
 154    for (i = 0; i < Reserved; i++)
 155      {
 156         if (!MmIsPagePresent(NULL,
 157                              (PVOID)((ULONG)MmPageArray + (i * PAGESIZE))))
 158           {
 159              Status = MmCreateVirtualMapping(NULL,
 160                                              (PVOID)((ULONG)MmPageArray +
 161                                                      (i * PAGESIZE)),
 162                                              PAGE_READWRITE,
 163                                              (ULONG)(LastPhysKernelAddress
 164                                                      - (i * PAGESIZE)));
 165              if (!NT_SUCCESS(Status))
 166                {
 167                   DbgPrint("Unable to create virtual mapping\n");
 168                   KeBugCheck(0);
 169                }
 170           }
 171      }
 172
 173    i = 1;
 174    if ((ULONG)FirstPhysKernelAddress < 0xa0000)
 175      {
 176         MmStats.NrFreePages += ((ULONG)FirstPhysKernelAddress/PAGESIZE);
 177         for (; i<((ULONG)FirstPhysKernelAddress/PAGESIZE); i++)
 178           {
 179              MmPageArray[i].Flags = MM_PHYSICAL_PAGE_FREE;
 180              MmPageArray[i].ReferenceCount = 0;
 181              KeInitializeEvent(&MmPageArray[i].Event,
 182                                NotificationEvent,
 183                                FALSE);
 184              InsertTailList(&FreePageListHead,
 185                             &MmPageArray[i].ListEntry);
 186           }
 187         MmStats.NrSystemPages +=
 188           ((((ULONG)LastPhysKernelAddress) / PAGESIZE) - i);
 189         for (; i<((ULONG)LastPhysKernelAddress / PAGESIZE); i++)
 190           {
 191              MmPageArray[i].Flags = MM_PHYSICAL_PAGE_USED;
 192              MmPageArray[i].ReferenceCount = 1;
 193              KeInitializeEvent(&MmPageArray[i].Event,
 194                                NotificationEvent,
 195                                FALSE);
 196              InsertTailList(&UsedPageListHead,
 197                             &MmPageArray[i].ListEntry);
 198           }
 199         MmStats.NrFreePages += ((0xa0000/PAGESIZE) - i);
 200         for (; i<(0xa0000/PAGESIZE); i++)
 201           {
 202              MmPageArray[i].Flags = MM_PHYSICAL_PAGE_FREE;
 203              MmPageArray[i].ReferenceCount = 0;
 204              KeInitializeEvent(&MmPageArray[i].Event,
 205                                NotificationEvent,
 206                                FALSE);
 207              InsertTailList(&FreePageListHead,
 208                             &MmPageArray[i].ListEntry);
 209           }
 210         MmStats.NrReservedPages += ((0x100000/PAGESIZE) - i);
 211         for (; i<(0x100000 / PAGESIZE); i++)
 212           {
 213              MmPageArray[i].Flags = MM_PHYSICAL_PAGE_BIOS;
 214              MmPageArray[i].ReferenceCount = 1;
 215              KeInitializeEvent(&MmPageArray[i].Event,
 216                                NotificationEvent,
 217                                FALSE);
 218              InsertTailList(&BiosPageListHead,
 219                             &MmPageArray[i].ListEntry);
 220           }
 221      }
 222    else
 223      {
 224         MmStats.NrFreePages += (0xa0000 / PAGESIZE);
 225         for (; i<(0xa0000 / PAGESIZE); i++)
 226           {
 227              MmPageArray[i].Flags = MM_PHYSICAL_PAGE_FREE;
 228              MmPageArray[i].ReferenceCount = 0;
 229              KeInitializeEvent(&MmPageArray[i].Event,
 230                                NotificationEvent,
 231                                FALSE);
 232              InsertTailList(&FreePageListHead,
 233                             &MmPageArray[i].ListEntry);
 234           }
 235         MmStats.NrReservedPages += (0x60000 / PAGESIZE);
 236         for (; i<(0x100000 / PAGESIZE); i++)
 237           {
 238              MmPageArray[i].Flags = MM_PHYSICAL_PAGE_BIOS;
 239              MmPageArray[i].ReferenceCount = 1;
 240              KeInitializeEvent(&MmPageArray[i].Event,
 241                                NotificationEvent,
 242                                FALSE);
 243              InsertTailList(&BiosPageListHead,
 244                             &MmPageArray[i].ListEntry);
 245           }
 246         MmStats.NrFreePages += (((ULONG)FirstPhysKernelAddress/PAGESIZE) - i);
 247         for (; i<((ULONG)FirstPhysKernelAddress/PAGESIZE); i++)
 248           {
 249              MmPageArray[i].Flags = MM_PHYSICAL_PAGE_FREE;
 250              MmPageArray[i].ReferenceCount = 0;
 251              KeInitializeEvent(&MmPageArray[i].Event,
 252                                NotificationEvent,
 253                                FALSE);
 254              InsertTailList(&FreePageListHead,
 255                             &MmPageArray[i].ListEntry);
 256           }
 257         MmStats.NrSystemPages +=
 258           (((ULONG)LastPhysKernelAddress/PAGESIZE) - i);
 259         for (; i<((ULONG)LastPhysKernelAddress/PAGESIZE); i++)
 260           {
 261              MmPageArray[i].Flags = MM_PHYSICAL_PAGE_USED;
 262              MmPageArray[i].ReferenceCount = 1;
 263              KeInitializeEvent(&MmPageArray[i].Event,
 264                                NotificationEvent,
 265                                FALSE);
 266              InsertTailList(&UsedPageListHead,
 267                             &MmPageArray[i].ListEntry);
 268           }
 269      }
 270
 271    MmStats.NrFreePages += (MemorySizeInPages - i);
 272    for (; i<MemorySizeInPages; i++)
 273      {
 274         MmPageArray[i].Flags = MM_PHYSICAL_PAGE_FREE;
 275         MmPageArray[i].ReferenceCount = 0;
 276         KeInitializeEvent(&MmPageArray[i].Event,
 277                           NotificationEvent,
 278                           FALSE);
 279         InsertTailList(&FreePageListHead,
 280                        &MmPageArray[i].ListEntry);
 281      }
 282    return((PVOID)LastKernelAddress);
 283 }
 284
 285 VOID MmSetFlagsPage(PVOID PhysicalAddress,
 286                     ULONG Flags)
 287 {
 288    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 289    KIRQL oldIrql;
 290
 291    KeAcquireSpinLock(&PageListLock, &oldIrql);
 292    MmPageArray[Start].Flags = Flags;
 293    KeReleaseSpinLock(&PageListLock, oldIrql);
 294 }
 295
 296 ULONG MmGetFlagsPage(PVOID PhysicalAddress)
 297 {
 298    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 299    KIRQL oldIrql;
 300    ULONG Flags;
 301
 302    KeAcquireSpinLock(&PageListLock, &oldIrql);
 303    Flags = MmPageArray[Start].Flags;
 304    KeReleaseSpinLock(&PageListLock, oldIrql);
 305
 306    return(Flags);
 307 }
 308
 309
 310 VOID MmSetSavedSwapEntryPage(PVOID PhysicalAddress,
 311                              SWAPENTRY SavedSwapEntry)
 312 {
 313    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 314    KIRQL oldIrql;
 315
 316    KeAcquireSpinLock(&PageListLock, &oldIrql);
 317    MmPageArray[Start].SavedSwapEntry = SavedSwapEntry;
 318    KeReleaseSpinLock(&PageListLock, oldIrql);
 319 }
 320
 321 SWAPENTRY MmGetSavedSwapEntryPage(PVOID PhysicalAddress)
 322 {
 323    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 324    SWAPENTRY SavedSwapEntry;
 325    KIRQL oldIrql;
 326
 327    KeAcquireSpinLock(&PageListLock, &oldIrql);
 328    SavedSwapEntry = MmPageArray[Start].SavedSwapEntry;
 329    KeReleaseSpinLock(&PageListLock, oldIrql);
 330
 331    return(SavedSwapEntry);
 332 }
 333
 334 VOID MmReferencePage(PVOID PhysicalAddress)
 335 {
 336    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 337    KIRQL oldIrql;
 338
 339    DPRINT("MmReferencePage(PhysicalAddress %x)\n", PhysicalAddress);
 340
 341    if (((ULONG)PhysicalAddress) == 0)
 342      {
 343         KeBugCheck(0);
 344      }
 345
 346    KeAcquireSpinLock(&PageListLock, &oldIrql);
 347
 348    if (MM_PTYPE(MmPageArray[Start].Flags) != MM_PHYSICAL_PAGE_USED)
 349      {
 350         DbgPrint("Referencing non-used page\n");
 351         KeBugCheck(0);
 352      }
 353
 354    MmPageArray[Start].ReferenceCount++;
 355    KeReleaseSpinLock(&PageListLock, oldIrql);
 356 }
 357
 358 VOID MmDereferencePage(PVOID PhysicalAddress)
 359 {
 360    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 361    KIRQL oldIrql;
 362
 363    DPRINT("MmDereferencePage(PhysicalAddress %x)\n", PhysicalAddress);
 364
 365    if (((ULONG)PhysicalAddress) == 0)
 366      {
 367         KeBugCheck(0);
 368      }
 369
 370    KeAcquireSpinLock(&PageListLock, &oldIrql);
 371
 372    if (MM_PTYPE(MmPageArray[Start].Flags) != MM_PHYSICAL_PAGE_USED)
 373      {
 374         DbgPrint("Dereferencing free page\n");
 375         KeBugCheck(0);
 376      }
 377
 378    MmStats.NrFreePages++;
 379    MmStats.NrSystemPages--;
 380
 381    MmPageArray[Start].ReferenceCount--;
 382    if (MmPageArray[Start].ReferenceCount == 0)
 383      {
 384         RemoveEntryList(&MmPageArray[Start].ListEntry);
 385         if (MmPageArray[Start].LockCount > 0)
 386           {
 387              DbgPrint("Freeing locked page\n");
 388              KeBugCheck(0);
 389           }
 390         if (MmPageArray[Start].Flags != MM_PHYSICAL_PAGE_USED)
 391           {
 392              DbgPrint("Freeing page with flags %x\n",
 393                       MmPageArray[Start].Flags);
 394              KeBugCheck(0);
 395           }
 396         MmPageArray[Start].Flags = MM_PHYSICAL_PAGE_FREE;
 397         InsertTailList(&FreePageListHead, &MmPageArray[Start].ListEntry);
 398      }
 399    KeReleaseSpinLock(&PageListLock, oldIrql);
 400 }
 401
 402 ULONG MmGetLockCountPage(PVOID PhysicalAddress)
 403 {
 404    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 405    KIRQL oldIrql;
 406    ULONG LockCount;
 407
 408    DPRINT("MmGetLockCountPage(PhysicalAddress %x)\n", PhysicalAddress);
 409
 410    if (((ULONG)PhysicalAddress) == 0)
 411      {
 412         KeBugCheck(0);
 413      }
 414
 415    KeAcquireSpinLock(&PageListLock, &oldIrql);
 416
 417    if (MM_PTYPE(MmPageArray[Start].Flags) != MM_PHYSICAL_PAGE_USED)
 418      {
 419         DbgPrint("Getting lock count for free page\n");
 420         KeBugCheck(0);
 421      }
 422
 423    LockCount = MmPageArray[Start].LockCount;
 424    KeReleaseSpinLock(&PageListLock, oldIrql);
 425
 426    return(LockCount);
 427 }
 428
 429 VOID MmLockPage(PVOID PhysicalAddress)
 430 {
 431    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 432    KIRQL oldIrql;
 433
 434    DPRINT("MmLockPage(PhysicalAddress %x)\n", PhysicalAddress);
 435
 436    if (((ULONG)PhysicalAddress) == 0)
 437      {
 438         KeBugCheck(0);
 439      }
 440
 441    KeAcquireSpinLock(&PageListLock, &oldIrql);
 442
 443    if (MM_PTYPE(MmPageArray[Start].Flags) != MM_PHYSICAL_PAGE_USED)
 444      {
 445         DbgPrint("Locking free page\n");
 446         KeBugCheck(0);
 447      }
 448
 449    MmPageArray[Start].LockCount++;
 450    KeReleaseSpinLock(&PageListLock, oldIrql);
 451 }
 452
 453 VOID MmUnlockPage(PVOID PhysicalAddress)
 454 {
 455    ULONG Start = (ULONG)PhysicalAddress / PAGESIZE;
 456    KIRQL oldIrql;
 457
 458    DPRINT("MmUnlockPage(PhysicalAddress %x)\n", PhysicalAddress);
 459
 460    if (((ULONG)PhysicalAddress) == 0)
 461      {
 462         KeBugCheck(0);
 463      }
 464
 465    KeAcquireSpinLock(&PageListLock, &oldIrql);
 466
 467    if (MM_PTYPE(MmPageArray[Start].Flags) != MM_PHYSICAL_PAGE_USED)
 468      {
 469         DbgPrint("Unlocking free page\n");
 470         KeBugCheck(0);
 471      }
 472
 473    MmPageArray[Start].LockCount--;
 474    KeReleaseSpinLock(&PageListLock, oldIrql);
 475 }
 476
 477
 478 PVOID
 479 MmAllocPage(SWAPENTRY SavedSwapEntry)
 480 {
 481    ULONG offset;
 482    PLIST_ENTRY ListEntry;
 483    PPHYSICAL_PAGE PageDescriptor;
 484
 485    DPRINT("MmAllocPage()\n");
 486
 487    ListEntry = ExInterlockedRemoveHeadList(&FreePageListHead,
 488                                            &PageListLock);
 489    DPRINT("ListEntry %x\n",ListEntry);
 490    if (ListEntry == NULL)
 491      {
 492         DPRINT("MmAllocPage(): Out of memory\n");
 493         return(NULL);
 494      }
 495    PageDescriptor = CONTAINING_RECORD(ListEntry, PHYSICAL_PAGE, ListEntry);
 496    DPRINT("PageDescriptor %x\n",PageDescriptor);
 497    if (PageDescriptor->Flags != MM_PHYSICAL_PAGE_FREE)
 498      {
 499         DbgPrint("Got non-free page from freelist\n");
 500         KeBugCheck(0);
 501      }
 502    PageDescriptor->Flags = MM_PHYSICAL_PAGE_USED;
 503    PageDescriptor->ReferenceCount = 1;
 504    PageDescriptor->LockCount = 0;
 505    PageDescriptor->SavedSwapEntry = SavedSwapEntry;
 506    ExInterlockedInsertTailList(&UsedPageListHead, ListEntry,
 507                                &PageListLock);
 508
 509    DPRINT("PageDescriptor %x MmPageArray %x\n", PageDescriptor, MmPageArray);
 510    offset = (ULONG)((ULONG)PageDescriptor - (ULONG)MmPageArray);
 511    DPRINT("offset %x\n",offset);
 512    offset = offset / sizeof(PHYSICAL_PAGE) * PAGESIZE;
 513    DPRINT("offset %x\n",offset);
 514
 515    MmStats.NrSystemPages++;
 516    MmStats.NrFreePages--;
 517
 518    DPRINT("MmAllocPage() = %x\n",offset);
 519    return((PVOID)offset);
 520 }
 521
 522 PVOID
 523 MmMustAllocPage(SWAPENTRY SavedSwapEntry)
 524 {
 525    PVOID Page;
 526
 527    Page = MmAllocPage(SavedSwapEntry);
 528    if (Page == NULL)
 529      {
 530         KeBugCheck(0);
 531         return(NULL);
 532      }
 533
 534    return(Page);
 535 }
 536
 537 PVOID
 538 MmAllocPageMaybeSwap(SWAPENTRY SavedSwapEntry)
 539 {
 540    PVOID Page;
 541
 542    Page = MmAllocPage(SavedSwapEntry);
 543    while (Page == NULL)
 544      {
 545         MmWaitForFreePages();
 546         Page = MmAllocPage(SavedSwapEntry);
 547      };
 548    return(Page);
 549 }
 550
 551 NTSTATUS
 552 MmWaitForPage(PVOID PhysicalAddress)
 553 {
 554    NTSTATUS Status;
 555    ULONG Start;
 556
 557    Start = (ULONG)PhysicalAddress / PAGESIZE;
 558    Status = KeWaitForSingleObject(&MmPageArray[Start].Event,
 559                                   UserRequest,
 560                                   KernelMode,
 561                                   FALSE,
 562                                   NULL);
 563    return(Status);
 564 }
 565
 566 VOID
 567 MmClearWaitPage(PVOID PhysicalAddress)
 568 {
 569    ULONG Start;
 570
 571    Start = (ULONG)PhysicalAddress / PAGESIZE;
 572
 573    KeClearEvent(&MmPageArray[Start].Event);
 574 }
 575
 576 VOID
 577 MmSetWaitPage(PVOID PhysicalAddress)
 578 {
 579    ULONG Start;
 580
 581    Start = (ULONG)PhysicalAddress / PAGESIZE;
 582
 583    KeSetEvent(&MmPageArray[Start].Event,
 584               IO_DISK_INCREMENT,
 585               FALSE);
 586 }