PartitionAlloc: implement discarding for partitionPurgeMemoryGeneric().

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 467 matching lines @@
         PartitionPage* secondaryPage = reinterpret_cast<PartitionPage*>(pageCharPtr);
         secondaryPage->pageOffset = i;
     }
 }
 
 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);
     uint16_t numSlots = page->numUnprovisionedSlots;
     ASSERT(numSlots);
     PartitionBucket* bucket = page->bucket;
     // We should only get here when _every_ slot is either used or unprovisioned.
     // (The third state is "on the freelist". If we have a non-empty freelist, we should not get here.)
     ASSERT(numSlots + page->numAllocatedSlots == partitionBucketSlots(bucket));
     // Similarly, make explicitly sure that the freelist is empty.
@@ skipping 372 matching lines @@
 static void partitionDecommitEmptyPages(PartitionRootBase* root)
 {
     for (size_t i = 0; i < kMaxFreeableSpans; ++i) {
         PartitionPage* page = root->globalEmptyPageRing[i];
         if (page)
             partitionDecommitPageIfPossible(root, page);
         root->globalEmptyPageRing[i] = nullptr;
     }
 }
 
-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;
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
     if (LIKELY(page->numAllocatedSlots == 0)) {
         // Page became fully unused.
         if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) {
             partitionDirectUnmap(page);
             return;
         }
@@ skipping 160 matching lines @@
     size_t copySize = actualOldSize;
     if (newSize < copySize)
         copySize = newSize;
 
     memcpy(ret, ptr, copySize);
     partitionFreeGeneric(root, ptr);
     return ret;
 #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;
+        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 {
-        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;

[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;
     // If the active page list is empty (== &PartitionRootGeneric::gSeedPage),
     // the bucket might still need to be reported if it has an empty page list,
     // or full pages.
     if (bucket->activePagesHead == &PartitionRootGeneric::gSeedPage && !bucket->emptyPagesHead && !bucket->numFullPages)
         return;
 
     memset(statsOut, '\0', sizeof(*statsOut));
     statsOut->isValid = true;
     statsOut->isDirectMap = false;
     statsOut->numFullPages = static_cast<size_t>(bucket->numFullPages);
     statsOut->bucketSlotSize = bucket->slotSize;
     uint16_t bucketNumSlots = partitionBucketSlots(bucket);
     size_t bucketUsefulStorage = statsOut->bucketSlotSize * bucketNumSlots;
     statsOut->allocatedPageSize = partitionBucketBytes(bucket);
     statsOut->activeBytes = bucket->numFullPages * bucketUsefulStorage;
     statsOut->residentBytes = bucket->numFullPages * statsOut->allocatedPageSize;
 
     for (const PartitionPage* page = bucket->emptyPagesHead; page; page = page->nextPage) {
         // Currently, only decommitted pages appear in the empty pages list.
         // This may change.
         ASSERT(page != &PartitionRootGeneric::gSeedPage);
         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;
         ++numDirectMappedAllocations;
         if (numDirectMappedAllocations == kMaxReportableDirectMaps)
             break;
     }
 
     spinLockUnlock(&partition->lock);
 
@@ skipping 20 matching lines @@
 }
 
 void partitionDumpStats(PartitionRoot* partition, const char* partitionName, PartitionStatsDumper* partitionStatsDumper)
 {
     static const size_t kMaxReportableBuckets = 4096 / sizeof(void*);
     PartitionBucketMemoryStats memoryStats[kMaxReportableBuckets];
     const size_t partitionNumBuckets = partition->numBuckets;
     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.
     for (size_t i = 0; i < partitionNumBuckets; ++i) {
         if (memoryStats[i].isValid)
             partitionStatsDumper->partitionsDumpBucketStats(partitionName, &memoryStats[i]);
     }
 }
 
 } // namespace WTF