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 459 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 371 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
 }
 
+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);
 
     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;
     }
 }
 
 static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, const PartitionBucket* bucket)
 {
     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.
@@ skipping 25 matching lines @@
         for (const PartitionPage* page = bucket->activePagesHead; page; page = page->nextPage) {
             ASSERT(page != &PartitionRootGeneric::gSeedPage);
             partitionDumpPageStats(statsOut, page);
         }
     }
 }
 
 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
         // order to preserve a fast size->bucket map (see
         // partitionAllocGenericInit for details).
         if (!bucket->activePagesHead)
             bucketStats[i].isValid = false;
         else
             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;
         ++numDirectMappedAllocations;
         if (numDirectMappedAllocations == kMaxReportableDirectMaps)
             break;
     }
 
     spinLockUnlock(&partition->lock);
 
@@ skipping 32 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