[sir_richard] 45616: [NTOS]: Instead of having an LRU linked list of working set pages, we instead have a bitmap. Advantage: Pages are only in a linked list when they are NOT active (free/zeroed, for now). This makes the LIST_ENTRY fields usable when a page is active, so we can store data in there. This will make it easier to sync our PFN format with Windows. Advantage: It's a lot faster to set/clear bits than to do list operations (both still O1 though). Scanning for the bit is a bit slower tha

Author: sir_richard
Date: Fri Feb 19 01:46:35 2010
New Revision: 45616

URL: http://svn.reactos.org/svn/reactos?rev=45616&view=rev
Log:
[NTOS]: Instead of having an LRU linked list of working set pages, we instead have a
bitmap.
    Advantage: Pages are only in a linked list when they are NOT active (free/zeroed, for
now). This makes the LIST_ENTRY fields usable when a page is active, so we can store data
in there. This will make it easier to sync our PFN format with Windows.
    Advantage: It's a lot faster to set/clear bits than to do list operations (both
still O1 though). Scanning for the bit is a bit slower than parsing a list, on the other
hand, so it's a toss.
    Disadvantage: We lose LRU, which in theory makes us cannibalize working sets randomly
instead of by-usage. However, considering the speed of ReactOS paging, and the effects of
canabalizing the WS in the first place, I doubt this is really a problem.
The main point of this is advantage #1 -- making used pages not be on any lists. This will
allow us to almost 100% sync the PFN layouts, which will lead to the eventual negation of
any temporary disavantages.

Modified:
    trunk/reactos/ntoskrnl/mm/balance.c
    trunk/reactos/ntoskrnl/mm/freelist.c
    trunk/reactos/ntoskrnl/mm/mminit.c

Modified: trunk/reactos/ntoskrnl/mm/balance.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/balance.c?rev=…
==============================================================================
--- trunk/reactos/ntoskrnl/mm/balance.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/balance.c [iso-8859-1] Fri Feb 19 01:46:35 2010
@@ -187,11 +187,6 @@
             DPRINT("Succeeded\n");
             Target--;
             (*NrFreedPages)++;
-        }
-        else if (Status == STATUS_PAGEFILE_QUOTA)
-        {
-            MmRemoveLRUUserPage(CurrentPage);
-            MmInsertLRULastUserPage(CurrentPage);
         }
         
         CurrentPage = NextPage;

Modified: trunk/reactos/ntoskrnl/mm/freelist.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/freelist.c?rev…
==============================================================================
--- trunk/reactos/ntoskrnl/mm/freelist.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/freelist.c [iso-8859-1] Fri Feb 19 01:46:35 2010
@@ -74,71 +74,81 @@
 
 /* FUNCTIONS *************************************************************/
 
+static RTL_BITMAP MiUserPfnBitMap;
+
+/* FUNCTIONS *************************************************************/
+
+VOID
+NTAPI
+MiInitializeUserPfnBitmap(VOID)
+{
+    PVOID Bitmap;
+    
+    /* Allocate enough buffer for the PFN bitmap and align it on 32-bits */
+    Bitmap = ExAllocatePoolWithTag(NonPagedPool,
+                                   (((MmHighestPhysicalPage + 1) + 31) / 32) * 4,
+                                   '  mM');
+    ASSERT(Bitmap);
+
+    /* Initialize it and clear all the bits to begin with */
+    RtlInitializeBitMap(&MiUserPfnBitMap,
+                        Bitmap,
+                        MmHighestPhysicalPage + 1);
+    RtlClearAllBits(&MiUserPfnBitMap);
+}
+
 PFN_TYPE
 NTAPI
 MmGetLRUFirstUserPage(VOID)
 {
-   PLIST_ENTRY NextListEntry;
-   PHYSICAL_PAGE* PageDescriptor;
-   KIRQL oldIrql;
-
-   oldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
-   NextListEntry = UserPageListHead.Flink;
-   if (NextListEntry == &UserPageListHead)
-   {
-	  KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
-      return 0;
-   }
-   PageDescriptor = CONTAINING_RECORD(NextListEntry, PHYSICAL_PAGE, ListEntry);
-   KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
-   return PageDescriptor - MmPfnDatabase[0];
+    ULONG Position;
+    KIRQL OldIrql;
+    
+    /* Find the first user page */
+    OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
+    Position = RtlFindSetBits(&MiUserPfnBitMap, 1, 0);
+    KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
+    if (Position == 0xFFFFFFFF) return 0;
+    
+    /* Return it */
+    return Position;
 }
 
 VOID
 NTAPI
 MmInsertLRULastUserPage(PFN_TYPE Pfn)
 {
-   KIRQL oldIrql;
-   PPHYSICAL_PAGE Page;
-
-   oldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
-   Page = MiGetPfnEntry(Pfn);
-//   if (!Page->Consumer != MC_USER) DPRINT1("Page Consumer: %d\n",
Page->Consumer);
-   ASSERT(Page->Consumer == MC_USER);
-   ASSERT(Page->u3.e1.PageLocation = ActiveAndValid);
-   InsertTailList(&UserPageListHead, &Page->ListEntry);
-   KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
+    KIRQL OldIrql;
+
+    /* Set the page as a user page */
+    OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
+    RtlSetBit(&MiUserPfnBitMap, Pfn);
+    KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
 }
 
 PFN_TYPE
 NTAPI
 MmGetLRUNextUserPage(PFN_TYPE PreviousPfn)
 {
-   PLIST_ENTRY NextListEntry;
-   PHYSICAL_PAGE* PageDescriptor;
-   KIRQL oldIrql;
-   PPHYSICAL_PAGE Page;
-
-   oldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
-   Page = MiGetPfnEntry(PreviousPfn);
-   ASSERT(Page->Consumer == MC_USER);
-   ASSERT(Page->u3.e1.PageLocation = ActiveAndValid);
-   NextListEntry = (PLIST_ENTRY)Page->ListEntry.Flink;
-   if (NextListEntry == &UserPageListHead)
-   {
-	  KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
-      return 0;
-   }
-   PageDescriptor = CONTAINING_RECORD(NextListEntry, PHYSICAL_PAGE, ListEntry);
-   KeReleaseQueuedSpinLock(LockQueuePfnLock, oldIrql);
-   return PageDescriptor - MmPfnDatabase[0];
+    ULONG Position;
+    KIRQL OldIrql;
+    
+    /* Find the next user page */
+    OldIrql = KeAcquireQueuedSpinLock(LockQueuePfnLock);
+    Position = RtlFindSetBits(&MiUserPfnBitMap, 1, PreviousPfn + 1);
+    KeReleaseQueuedSpinLock(LockQueuePfnLock, OldIrql);
+    if (Position == 0xFFFFFFFF) return 0;
+    
+    /* Return it */
+    return Position;
 }
 
 VOID
 NTAPI
 MmRemoveLRUUserPage(PFN_TYPE Page)
 {
-   RemoveEntryList(&MiGetPfnEntry(Page)->ListEntry);
+    /* Unset the page as a user page */
+    RtlClearBit(&MiUserPfnBitMap, Page);
 }
 
 BOOLEAN
@@ -907,7 +917,6 @@
    if (Page->u3.e2.ReferenceCount == 0)
    {
       MmAvailablePages++;
-      if (Page->Consumer == MC_USER) RemoveEntryList(&Page->ListEntry);
       Page->u3.e1.PageLocation = FreePageList;
       InsertTailList(&FreeUnzeroedPageListHead,
                      &Page->ListEntry);

Modified: trunk/reactos/ntoskrnl/mm/mminit.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/mminit.c?rev=4…
==============================================================================
--- trunk/reactos/ntoskrnl/mm/mminit.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/mminit.c [iso-8859-1] Fri Feb 19 01:46:35 2010
@@ -349,6 +349,8 @@
     DPRINT1("Total: %08lX (%d MB)\n", TotalPages, (TotalPages * PAGE_SIZE) /
1024 / 1024);
 }
 
+VOID NTAPI MiInitializeUserPfnBitmap(VOID);
+
 BOOLEAN
 NTAPI
 MmInitSystem(IN ULONG Phase,
@@ -397,6 +399,7 @@
         MmInitializePagedPool();
         
         /* Initialize working sets */
+        MiInitializeUserPfnBitmap();
         MmInitializeMemoryConsumer(MC_USER, MmTrimUserMemory);
 
         /* Initialize the user mode image list */