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 2f36cf6e0e37dfd177ea5ecd17949171c6e78dcc..198c09d421025a0c7b320af0794b8c55560f4a0e 100644
--- a/Source/wtf/PartitionAlloc.cpp
+++ b/Source/wtf/PartitionAlloc.cpp
@@ -477,6 +477,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);
@@ -868,20 +873,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;
@@ -1062,6 +1053,106 @@ void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newS
 #endif
 }
 
+void partitionPurgeMemory(PartitionRoot* root, int flags)

[haraken, 2015/06/22 09:22:00]

I'd move this to just before partitionPurgeMemoryGeneric.

+{
+    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.
+}
+
+static size_t partitionPurgePage(const PartitionPage* page, bool discard)
+{
+    const PartitionBucket* bucket = page->bucket;
+    if (bucket->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;

[haraken, 2015/06/22 09:22:00]

Is it guaranteed that bucket->slotSize is a multiple of the system page size?

+        if (discardableBytes && discard) {
+            char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
+            ptr += usedBytes;
+            discardSystemPages(ptr, discardableBytes);

[haraken, 2015/06/22 09:22:00]

For a single-slot allocation, we're committing the "trailing" system pages when
we allocated the page, and then discarding the "trailing" system pages here.
This looks a bit redundant. Can we avoid committing the "trailing" system pages
from the beginning?

(We can do this in a follow-up.)

+        }
+        return discardableBytes;
+    }
+
+    char slotUsage[(kPartitionPageSize * kMaxPartitionPagesPerSlotSpan) / kSystemPageSize];

[haraken, 2015/06/22 09:22:00]

size_t maxSlotCount = (kPartitionPageSize * kMaxPartitionPagesPerSlotSpan) /
kSystemPageSize;
char slotUsage[maxSlotCount];

... and then add ASSERT(slotIndex < maxSlotCount) when accessing the slotUsage
array.

+    size_t lastSlot = -1;
+    memset(slotUsage, 1, sizeof(slotUsage));
+    char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
+    PartitionFreelistEntry* fl = page->freelistHead;

[haraken, 2015/06/22 09:22:00]

fl => entry or freelist

+    // 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))

[haraken, 2015/06/22 09:22:00]

Is it possible that this condition becomes true? I guess fl and
partitionFreelistMask(fl) don't become 0 at the same time.

To avoid the complexity, I might prefer just dropping the lastSlot optimization
:)

+            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 partialSlotBytes = endPtr - beginPtr;
+            discardableBytes += partialSlotBytes;
+            if (discard)
+                discardSystemPages(beginPtr, partialSlotBytes);
+        }
+    }
+    return discardableBytes;
+}
+
+static void partitionPurgeBucket(const PartitionBucket* bucket)
+{
+    if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) {
+        for (const PartitionPage* page = bucket->activePagesHead; page; page = page->nextPage) {
+            ASSERT(page != &PartitionRootGeneric::gSeedPage);
+            (void) partitionPurgePage(page, true);

[haraken, 2015/06/22 09:22:00]

Nit: (void) won't be needed.

+        }
+    }
+}
+
+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];
+            if (bucket->slotSize >= kSystemPageSize)
+                partitionPurgeBucket(bucket);
+        }
+    }
+    spinLockUnlock(&root->lock);
+}
+
 static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, const PartitionPage* page)
 {
     uint16_t bucketNumSlots = partitionBucketSlots(page->bucket);
@@ -1069,24 +1160,28 @@ static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, const P
     if (!page->freelistHead && page->numAllocatedSlots == 0) {
         ASSERT(!page->numUnprovisionedSlots);
         ++statsOut->numDecommittedPages;
+        return;
+    }
+
+    statsOut->discardableBytes += partitionPurgePage(page, false);
+
+    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;
     } 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;
-        }
+        statsOut->activeBytes += (page->numAllocatedSlots * statsOut->bucketSlotSize);
+    }
+    statsOut->residentBytes += pageBytesResident;
+    if (!page->numAllocatedSlots) {
+        statsOut->decommittableBytes += pageBytesResident;
+        ++statsOut->numEmptyPages;
+    } else if (page->numAllocatedSlots == bucketNumSlots) {
+        ++statsOut->numFullPages;
+    } else {
+        ++statsOut->numActivePages;
     }
 }
 
@@ -1132,7 +1227,12 @@ static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, const
 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);
+
     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
@@ -1144,9 +1244,6 @@ void partitionDumpStatsGeneric(PartitionRootGeneric* partition, const char* part
             partitionDumpBucketStats(&bucketStats[i], bucket);
     }
 
-    static const size_t kMaxReportableDirectMaps = 4096;
-    uint32_t directMapLengths[kMaxReportableDirectMaps];
-    size_t numDirectMappedAllocations = 0;
     for (PartitionDirectMapExtent* extent = partition->directMapList; extent; extent = extent->nextExtent) {
         ASSERT(!extent->nextExtent || extent->nextExtent->prevExtent == extent);
         directMapLengths[numDirectMappedAllocations] = extent->bucket->slotSize;