PartitionAlloc: make PartitionPurgeDiscardUnusedSystemPages discard more.

Source/wtf/PartitionAlloc.cpp

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 1043 matching lines @@
     size_t copySize = actualOldSize;
     if (newSize < copySize)
         copySize = newSize;
 
     memcpy(ret, ptr, copySize);
     partitionFreeGeneric(root, ptr);
     return ret;
 #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);
     size_t discardableBytes = 0;
 
     size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page));
     if (rawSize) {
         uint32_t usedBytes = static_cast<uint32_t>(partitionRoundUpToSystemPage(rawSize));
         discardableBytes = bucket->slotSize - usedBytes;
         if (discardableBytes && discard) {
             char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
             ptr += usedBytes;
             discardSystemPages(ptr, discardableBytes);
         }
         return discardableBytes;
     }
 
     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).

     char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
     PartitionFreelistEntry* entry = page->freelistHead;
     // 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
         // actually discard that freelist entry because touching a discarded
         // page is guaranteed to return original content or 0.
         // (Note that this optimization won't fire on big endian machines
         // because the masking function is negation.)
         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)));
         endPtr = reinterpret_cast<char*>(partitionRoundDownToSystemPage(reinterpret_cast<size_t>(endPtr)));
         if (beginPtr < endPtr) {
             size_t partialSlotBytes = endPtr - beginPtr;
             discardableBytes += partialSlotBytes;
             if (discard)
                 discardSystemPages(beginPtr, partialSlotBytes);
         }
     }
     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);
         }
     }
 }
 
 void partitionPurgeMemory(PartitionRoot* root, int flags)
 {
     if (flags & PartitionPurgeDecommitEmptyPages)
         partitionDecommitEmptyPages(root);
     // We don't currently do anything for PartitionPurgeDiscardUnusedSystemPages
     // here because that flag is only useful for allocations >= system page
     // size. We only have allocations that large inside generic partitions
     // at the moment.
 }
 
 void partitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags)
 {
     spinLockLock(&root->lock);
     if (flags & PartitionPurgeDecommitEmptyPages)
         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);
         }
     }
     spinLockUnlock(&root->lock);
 }
 
 static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, const PartitionPage* page)
 {
     uint16_t bucketNumSlots = partitionBucketSlots(page->bucket);
 
     if (partitionPageStateIsDecommitted(page)) {
         ++statsOut->numDecommittedPages;
         return;
     }
 
-    statsOut->discardableBytes += partitionPurgePage(page, false);
+    statsOut->discardableBytes += partitionPurgePage(const_cast<PartitionPage*>(page), false);
 
     size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page));
     if (rawSize)
         statsOut->activeBytes += static_cast<uint32_t>(rawSize);
     else
         statsOut->activeBytes += (page->numAllocatedSlots * statsOut->bucketSlotSize);
 
     size_t pageBytesResident = partitionRoundUpToSystemPage((bucketNumSlots - page->numUnprovisionedSlots) * statsOut->bucketSlotSize);
     statsOut->residentBytes += pageBytesResident;
     if (partitionPageStateIsEmpty(page)) {
@@ skipping 110 matching lines @@
     // partitionsDumpBucketStats is called after collecting stats because it
     // can use PartitionAlloc to allocate and this can affect the statistics.
     for (size_t i = 0; i < partitionNumBuckets; ++i) {
         if (memoryStats[i].isValid)
             partitionStatsDumper->partitionsDumpBucketStats(partitionName, &memoryStats[i]);
     }
 }
 
 } // namespace WTF