PartitionAlloc: make PartitionPurgeDiscardUnusedSystemPages discard more.

Source/wtf/PartitionAlloc.cpp

Index: Source/wtf/PartitionAlloc.cpp
diff --git a/Source/wtf/PartitionAlloc.cpp b/Source/wtf/PartitionAlloc.cpp
index 9c0b7bb88a08789eb243594cf87ae9d5bc2820b7..131a5fb537c0998b787a8d96ee392ccbaa334d3d 100644
--- a/Source/wtf/PartitionAlloc.cpp
+++ b/Source/wtf/PartitionAlloc.cpp
@@ -1061,10 +1061,11 @@ void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newS
 #endif
 }
 
-static size_t partitionPurgePage(const PartitionPage* page, bool discard)
+static size_t partitionPurgePage(PartitionPage* page, bool discard)
 {
     const PartitionBucket* bucket = page->bucket;
-    if (bucket->slotSize < kSystemPageSize || !page->numAllocatedSlots)
+    size_t slotSize = bucket->slotSize;
+    if (slotSize < kSystemPageSize || !page->numAllocatedSlots)
         return 0;
 
     size_t bucketNumSlots = partitionBucketSlots(bucket);
@@ -1084,6 +1085,8 @@ static size_t partitionPurgePage(const PartitionPage* page, bool discard)
 
     const size_t maxSlotCount = (kPartitionPageSize * kMaxPartitionPagesPerSlotSpan) / kSystemPageSize;
     ASSERT(bucketNumSlots <= maxSlotCount);
+    ASSERT(page->numUnprovisionedSlots < bucketNumSlots);
+    size_t numSlots = bucketNumSlots - page->numUnprovisionedSlots;
     char slotUsage[maxSlotCount];
     size_t lastSlot = -1;
     memset(slotUsage, 1, sizeof(slotUsage));

[haraken, 2015/06/24 01:10:16]

  memset(slotUsage, 1, sizeof(numSlots));

might be better (although it won't affect correctness).

@@ -1092,8 +1095,8 @@ static size_t partitionPurgePage(const PartitionPage* page, bool discard)
     // First, walk the freelist for this page and make a bitmap of which slots
     // are not in use.
     while (entry) {
-        size_t slotIndex = (reinterpret_cast<char*>(entry) - ptr) / bucket->slotSize;
-        ASSERT(slotIndex < bucketNumSlots);
+        size_t slotIndex = (reinterpret_cast<char*>(entry) - ptr) / slotSize;
+        ASSERT(slotIndex < numSlots);
         slotUsage[slotIndex] = 0;
         entry = partitionFreelistMask(entry->next);
         // If we have a slot where the masked freelist entry is 0, we can
@@ -1104,21 +1107,70 @@ static size_t partitionPurgePage(const PartitionPage* page, bool discard)
         if (!partitionFreelistMask(entry))
             lastSlot = slotIndex;
     }
+
+    // If the slot(s) at the end of the slot span are not in used, we can
+    // truncate them entirely and rewrite the freelist.
+    size_t truncatedSlots = 0;
+    while (!slotUsage[numSlots - 1]) {
+        truncatedSlots++;
+        numSlots--;
+        ASSERT(numSlots);
+    }
+    // First, do the work of calculating the discardable bytes. Don't actually
+    // discard anything unless the discard flag was passed in.
+    char* beginPtr;
+    char* endPtr;
+    size_t unprovisionedBytes = 0;
+    if (truncatedSlots) {
+        beginPtr = ptr + (numSlots * slotSize);
+        endPtr = beginPtr + slotSize;

[haraken, 2015/06/24 01:10:16]

Shouldn't this be:

  endPtr = beginPtr + slotSize * truncatedSlots

?

+        beginPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_cast<size_t>(beginPtr)));
+        endPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_cast<size_t>(endPtr)));

[haraken, 2015/06/24 01:10:16]

Maybe worth having a comment why this is partitionRound*Up*ToSystemPage, not
partitionRound*Down*ToSystemPage.

Also shall we add an ASSERT to verify that endptr is within the page's slot
span?

+        if (beginPtr < endPtr) {
+            unprovisionedBytes = endPtr - beginPtr;
+            discardableBytes += unprovisionedBytes;
+        }
+    }
+    if (truncatedSlots && discard) {
+        size_t numNewEntries = 0;
+        page->numUnprovisionedSlots += truncatedSlots;

[haraken, 2015/06/24 01:10:16]

Shall we add:

  ASSERT(page->numUnprovisionedSlots + page->numAllocatedSlots ==
bucketNumSlots);

?

+        // Rewrite the freelist.
+        PartitionFreelistEntry** entryPtr = &page->freelistHead;
+        bool wroteHead = false;
+        entry = page->freelistHead;
+        while (entry) {

[haraken, 2015/06/24 01:10:16]

A more straightforward way would be just to scan all the slots in the page and
rebuild the freelist.

for (size_t slotIndex = 0; slotIndex < numSlots; slotIndex++) {
  if (!slotUsage[slotIndex]) {
    // add this slot to the freelist.
  }
}

+            size_t slotIndex = (reinterpret_cast<char*>(entry) - ptr) / slotSize;
+            if (slotIndex < numSlots) {
+                if (!wroteHead) {
+                    *entryPtr = entry;
+                    wroteHead = true;
+                } else {
+                    *entryPtr = partitionFreelistMask(entry);
+                }
+                entryPtr = reinterpret_cast<PartitionFreelistEntry**>(entry);
+                numNewEntries++;
+            }
+            entry = partitionFreelistMask(entry->next);
+        }
+        *entryPtr = nullptr;
+        ASSERT(numNewEntries == numSlots - page->numAllocatedSlots);
+
+        // Discard the memory.
+        discardSystemPages(beginPtr, unprovisionedBytes);
+    }
+
     // Next, walk the slots and for any not in use, consider where the system
     // page boundaries occur. We can release any system pages back to the
     // system as long as we don't interfere with a freelist pointer or an
     // adjacent slot.
-    // TODO(cevans): I think we can "truncate" the page, i.e. increase the
-    // value of page->numUnprovisionedSlots and rewrite(!) the freelist, if
-    // we find that to be a win too.
-    for (size_t i = 0; i < bucketNumSlots; ++i) {
+    for (size_t i = 0; i < numSlots; ++i) {
         if (slotUsage[i])
             continue;
         // The first address we can safely discard is just after the freelist
         // pointer. There's one quirk: if the freelist pointer is actually a
         // null, we can discard that pointer value too.
-        char* beginPtr = ptr + (i * bucket->slotSize);
-        char* endPtr = beginPtr + bucket->slotSize;
+        char* beginPtr = ptr + (i * slotSize);
+        char* endPtr = beginPtr + slotSize;
         if (i != lastSlot)
             beginPtr += sizeof(PartitionFreelistEntry);
         beginPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_cast<size_t>(beginPtr)));
@@ -1133,10 +1185,10 @@ static size_t partitionPurgePage(const PartitionPage* page, bool discard)
     return discardableBytes;
 }
 
-static void partitionPurgeBucket(const PartitionBucket* bucket)
+static void partitionPurgeBucket(PartitionBucket* bucket)
 {
     if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) {
-        for (const PartitionPage* page = bucket->activePagesHead; page; page = page->nextPage) {
+        for (PartitionPage* page = bucket->activePagesHead; page; page = page->nextPage) {
             ASSERT(page != &PartitionRootGeneric::gSeedPage);
             (void) partitionPurgePage(page, true);
         }
@@ -1160,7 +1212,7 @@ void partitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags)
         partitionDecommitEmptyPages(root);
     if (flags & PartitionPurgeDiscardUnusedSystemPages) {
         for (size_t i = 0; i < kGenericNumBuckets; ++i) {
-            const PartitionBucket* bucket = &root->buckets[i];
+            PartitionBucket* bucket = &root->buckets[i];
             if (bucket->slotSize >= kSystemPageSize)
                 partitionPurgeBucket(bucket);
         }
@@ -1177,7 +1229,7 @@ static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, const P
         return;
     }
 
-    statsOut->discardableBytes += partitionPurgePage(page, false);
+    statsOut->discardableBytes += partitionPurgePage(const_cast<PartitionPage*>(page), false);
 
     size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page));
     if (rawSize)