PartitionAlloc: implement discarding for partitionPurgeMemoryGeneric().

Source/wtf/PartitionAlloc.cpp

Index: Source/wtf/PartitionAlloc.cpp
diff --git a/Source/wtf/PartitionAlloc.cpp b/Source/wtf/PartitionAlloc.cpp
index 33d7b0d597a9406d91ef61dac6c21de814c6611d..a636429bc300e7c21ba28474ef1cb8b12904b1f9 100644
--- a/Source/wtf/PartitionAlloc.cpp
+++ b/Source/wtf/PartitionAlloc.cpp
@@ -485,6 +485,11 @@ static ALWAYS_INLINE size_t partitionRoundUpToSystemPage(size_t size)
     return (size + kSystemPageOffsetMask) & kSystemPageBaseMask;
 }
 
+static ALWAYS_INLINE size_t partitionRoundDownToSystemPage(size_t size)
+{
+    return size & kSystemPageBaseMask;
+}
+
 static ALWAYS_INLINE char* partitionPageAllocAndFillFreelist(PartitionPage* page)
 {
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
@@ -877,20 +882,6 @@ static void partitionDecommitEmptyPages(PartitionRootBase* root)
     }
 }
 
-void partitionPurgeMemory(PartitionRoot* root, int flags)
-{
-    if (flags & PartitionPurgeDecommitEmptyPages)
-        partitionDecommitEmptyPages(root);
-}
-
-void partitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags)
-{
-    spinLockLock(&root->lock);
-    if (flags & PartitionPurgeDecommitEmptyPages)
-        partitionDecommitEmptyPages(root);
-    spinLockUnlock(&root->lock);
-}
-
 void partitionFreeSlowPath(PartitionPage* page)
 {
     PartitionBucket* bucket = page->bucket;
@@ -1071,35 +1062,97 @@ void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newS
 #endif
 }
 
-static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, const PartitionPage* page)
+static void partitionPageWalk(PartitionBucketMemoryStats* statsOut, const PartitionPage* page, bool discardMemory)

[haraken, 2015/06/22 03:36:58]

Maybe you can return the discardableBytes from this method. Then this method
doesn't need to take the statsOut parameter. (See my comment below for why I
want to do this.)

+{
+    const PartitionBucket* bucket = page->bucket;
+    if (bucket->slotSize < kSystemPageSize)
+        return;
+
+    size_t bucketNumSlots = partitionBucketSlots(bucket);
+    char slotUsage[(kPartitionPageSize * kMaxPartitionPagesPerSlotSpan) / kSystemPageSize];
+    size_t lastSlot = -1;
+    memset(slotUsage, 1, sizeof(slotUsage));
+    char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
+    PartitionFreelistEntry* fl = page->freelistHead;
+    // First, walk the freelist for this page and make a bitmap of which slots
+    // are not in use.
+    while (fl) {
+        size_t slotIndex = (reinterpret_cast<char*>(fl) - ptr) / bucket->slotSize;
+        ASSERT(slotIndex < bucketNumSlots);
+        slotUsage[slotIndex] = 0;
+        fl = partitionFreelistMask(fl->next);
+        if (!fl && !partitionFreelistMask(fl))
+            lastSlot = slotIndex;
+    }
+    // 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) {
+        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;
+        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 discardable = endPtr - beginPtr;
+            statsOut->discardableBytes += discardable;
+            if (discardMemory)
+                discardSystemPages(beginPtr, discardable);
+        }
+    }
+}
+
+static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, const PartitionPage* page, bool discardMemory)
 {
     uint16_t bucketNumSlots = partitionBucketSlots(page->bucket);
 
     if (!page->freelistHead && page->numAllocatedSlots == 0) {
         ASSERT(!page->numUnprovisionedSlots);
         ++statsOut->numDecommittedPages;
-    } else {
-        size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page));
-        if (rawSize)
-            statsOut->activeBytes += static_cast<uint32_t>(partitionRoundUpToSystemPage(rawSize));
-        else
-            statsOut->activeBytes += (page->numAllocatedSlots * statsOut->bucketSlotSize);
-        size_t pageBytesResident = (bucketNumSlots - page->numUnprovisionedSlots) * statsOut->bucketSlotSize;
-        // Round up to system page size.
-        size_t pageBytesResidentRounded = partitionRoundUpToSystemPage(pageBytesResident);
-        statsOut->residentBytes += pageBytesResidentRounded;
-        if (!page->numAllocatedSlots) {
-            statsOut->decommittableBytes += pageBytesResidentRounded;
-            ++statsOut->numEmptyPages;
-        } else if (page->numAllocatedSlots == bucketNumSlots) {
-            ++statsOut->numFullPages;
-        } else {
-            ++statsOut->numActivePages;
+        return;
+    }
+
+    size_t pageBytesResident = partitionRoundUpToSystemPage((bucketNumSlots - page->numUnprovisionedSlots) * statsOut->bucketSlotSize);
+
+    size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page));
+    if (rawSize) {
+        uint32_t activeBytes = static_cast<uint32_t>(partitionRoundUpToSystemPage(rawSize));
+        statsOut->activeBytes += activeBytes;
+        if (activeBytes < pageBytesResident) {
+            ASSERT(((pageBytesResident - activeBytes) % kSystemPageSize) == 0);

[haraken, 2015/06/22 03:36:58]

Just help me understand: How is it guaranteed that activeBytes is a multiple of
kSystemPageSize?

+            size_t discardable = pageBytesResident - activeBytes;
+            char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
+            ptr += activeBytes;
+            statsOut->discardableBytes += discardable;
+            if (discardMemory)
+                discardSystemPages(ptr, discardable);

[haraken, 2015/06/22 03:36:58]

I'm a bit afraid that if we have a bug in the discarding algorithm, we will end
up with hitting a crash that is hard to investigate. In ASSERT builds, how about
zapping the discarded memory instead of really discarding the memory? (We can do
this in a follow-up.)

         }
+    } else {
+        statsOut->activeBytes += (page->numAllocatedSlots * statsOut->bucketSlotSize);
+    }
+    statsOut->residentBytes += pageBytesResident;
+    if (!page->numAllocatedSlots) {
+        statsOut->decommittableBytes += pageBytesResident;
+        ++statsOut->numEmptyPages;

[haraken, 2015/06/22 03:36:58]

Shall we call discardSystemPages here? Given that we call partitionPageWalk and
discard memory of active pages, it would make more sense to discard memory of
empty pages as well.

+    } else if (page->numAllocatedSlots == bucketNumSlots) {
+        ++statsOut->numFullPages;
+    } else {
+        ++statsOut->numActivePages;
+        partitionPageWalk(statsOut, page, discardMemory);
     }
 }
 
-static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, const PartitionBucket* bucket)
+static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, const PartitionBucket* bucket, bool discardMemory)
 {
     ASSERT(!partitionBucketIsDirectMapped(bucket));
     statsOut->isValid = false;
@@ -1127,35 +1180,60 @@ static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, const
         ASSERT(!page->freelistHead);
         ASSERT(!page->numAllocatedSlots);
         ASSERT(!page->numUnprovisionedSlots);
-        partitionDumpPageStats(statsOut, page);
+        partitionDumpPageStats(statsOut, page, discardMemory);
     }
 
     if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) {
         for (const PartitionPage* page = bucket->activePagesHead; page; page = page->nextPage) {
             ASSERT(page != &PartitionRootGeneric::gSeedPage);
-            partitionDumpPageStats(statsOut, page);
+            partitionDumpPageStats(statsOut, page, discardMemory);
         }
     }
 }
 
-void partitionDumpStatsGeneric(PartitionRootGeneric* partition, const char* partitionName, PartitionStatsDumper* partitionStatsDumper)
+static void partitionGenericBucketWalk(PartitionBucketMemoryStats* statsOut, PartitionRootGeneric* partition, bool discardMemory)
 {
-    PartitionBucketMemoryStats bucketStats[kGenericNumBuckets];
-    spinLockLock(&partition->lock);
     for (size_t i = 0; i < kGenericNumBuckets; ++i) {
         const PartitionBucket* bucket = &partition->buckets[i];
         // Don't report the pseudo buckets that the generic allocator sets up in
         // order to preserve a fast size->bucket map (see
         // partitionAllocGenericInit for details).
         if (!bucket->activePagesHead)
-            bucketStats[i].isValid = false;
+            statsOut[i].isValid = false;
         else
-            partitionDumpBucketStats(&bucketStats[i], bucket);
+            partitionDumpBucketStats(&statsOut[i], bucket, discardMemory);
+    }
+}
+
+void partitionPurgeMemory(PartitionRoot* root, int flags)
+{
+    if (flags & PartitionPurgeDecommitEmptyPages)
+        partitionDecommitEmptyPages(root);

[haraken, 2015/06/22 03:36:59]

The reason you don't call partitionGenericBucketWalk in partitionPurgeMemory is
that those partitions don't have a bucket larger than 4096 byte? (Maybe worth a
comment.)

+}
+
+void partitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags)
+{
+    spinLockLock(&root->lock);
+    if (flags & PartitionPurgeDecommitEmptyPages)
+        partitionDecommitEmptyPages(root);
+    if (flags & PartitionPurgeDiscardUnusedSystemPages) {
+        PartitionBucketMemoryStats bucketStats[kGenericNumBuckets];

[haraken, 2015/06/22 03:36:58]

It is redundant to prepare an array of dummy bucketStats that won't be used.
Also conceptually, I'd prefer separating stats code from actual code. I guess
you shared the stats code with the actual code to avoid code duplication, but at
a first glance, it seems that we can split the two code without introducing too
much duplication. What do you think?

+        partitionGenericBucketWalk(bucketStats, root, true);

[haraken, 2015/06/22 03:36:58]

Or you can pass a nullptr to statsOut and remove the discardMemory flag. We can
discard memory if statsOut==nullptr.

(But I'd prefer splitting the stats code from the actual code.)

     }
+    spinLockUnlock(&root->lock);
+}
 
+void partitionDumpStatsGeneric(PartitionRootGeneric* partition, const char* partitionName, PartitionStatsDumper* partitionStatsDumper)
+{
+    PartitionBucketMemoryStats bucketStats[kGenericNumBuckets];
     static const size_t kMaxReportableDirectMaps = 4096;
     uint32_t directMapLengths[kMaxReportableDirectMaps];
     size_t numDirectMappedAllocations = 0;
+
+    spinLockLock(&partition->lock);
+
+    partitionGenericBucketWalk(bucketStats, partition, false);
+
     for (PartitionDirectMapExtent* extent = partition->directMapList; extent; extent = extent->nextExtent) {
         ASSERT(!extent->nextExtent || extent->nextExtent->prevExtent == extent);
         directMapLengths[numDirectMappedAllocations] = extent->bucket->slotSize;
@@ -1196,7 +1274,7 @@ void partitionDumpStats(PartitionRoot* partition, const char* partitionName, Par
     ASSERT(partitionNumBuckets <= kMaxReportableBuckets);
 
     for (size_t i = 0; i < partitionNumBuckets; ++i)
-        partitionDumpBucketStats(&memoryStats[i], &partition->buckets()[i]);
+        partitionDumpBucketStats(&memoryStats[i], &partition->buckets()[i], false);
 
     // partitionsDumpBucketStats is called after collecting stats because it
     // can use PartitionAlloc to allocate and this can affect the statistics.