PartitionAlloc: wait just a little while before actually freeing empty pages.

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 43 matching lines @@
 
 namespace WTF {
 
 int PartitionRootBase::gInitializedLock = 0;
 bool PartitionRootBase::gInitialized = false;
 PartitionPage PartitionRootBase::gSeedPage;
 PartitionBucket PartitionRootBase::gPagedBucket;
 
 static size_t partitionBucketNumSystemPages(size_t size)
 {
-    // TODO: Remove this once the more comprehensive solution is landed.
-    // This is a temporary bandaid to fix a Mac performance issue. Mac has poor page
-    // fault performance so we limit the freelist thrash of these popular sizes by
-    // allocating them in bigger slabs.
-    if (size == 16384 || size == 8192 || size == 4096)
-        return kMaxSystemPagesPerSlotSpan;
     // This works out reasonably for the current bucket sizes of the generic
     // allocator, and the current values of partition page size and constants.
     // Specifically, we have enough room to always pack the slots perfectly into
     // some number of system pages. The only waste is the waste associated with
     // unfaulted pages (i.e. wasted address space).
     // TODO: we end up using a lot of system pages for very small sizes. For
     // example, we'll use 12 system pages for slot size 24. The slot size is
     // so small that the waste would be tiny with just 4, or 1, system pages.
     // Later, we can investigate whether there are anti-fragmentation benefits
     // to using fewer system pages.
@@ skipping 33 matching lines @@
     spinLockUnlock(&PartitionRootBase::gInitializedLock);
 
     root->initialized = true;
     root->totalSizeOfSuperPages = 0;
     root->nextSuperPage = 0;
     root->nextPartitionPage = 0;
     root->nextPartitionPageEnd = 0;
     root->firstExtent = 0;
     root->currentExtent = 0;
 
+    root->globalEmptyPageHeadIndex = 0;
+    root->numGlobalEmptyPageEntries = 0;
+
     // This is a "magic" value so we can test if a root pointer is valid.
     root->invertedSelf = ~reinterpret_cast<uintptr_t>(root);
 }
 
 static void partitionBucketInitBase(PartitionBucket* bucket, PartitionRootBase* root)
 {
     bucket->activePagesHead = &PartitionRootGeneric::gSeedPage;
     bucket->freePagesHead = 0;
     bucket->numFullPages = 0;
     bucket->numSystemPagesPerSlotSpan = partitionBucketNumSystemPages(bucket->slotSize);
@@ skipping 254 matching lines @@
 {
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
     page->numAllocatedSlots = 0;
     page->numUnprovisionedSlots = partitionBucketSlots(bucket);
     ASSERT(page->numUnprovisionedSlots);
     page->bucket = bucket;
     page->nextPage = 0;
     // NULLing the freelist is not strictly necessary but it makes an ASSERT in partitionPageFillFreelist simpler.
     page->freelistHead = 0;
     page->pageOffset = 0;
+    page->freeCacheIndex = 0;
     size_t numPartitionPages = partitionBucketPartitionPages(bucket);
     size_t i;
     char* pageCharPtr = reinterpret_cast<char*>(page);
     for (i = 1; i < numPartitionPages; ++i) {
         pageCharPtr += kPageMetadataSize;
         PartitionPage* secondaryPage = reinterpret_cast<PartitionPage*>(pageCharPtr);
         secondaryPage->pageOffset = i;
     }
 }
 
@@ skipping 85 matching lines @@
 
         // Page is usable if it has something on the freelist, or unprovisioned
         // slots that can be turned into a freelist.
         if (LIKELY(page->freelistHead != 0) || LIKELY(page->numUnprovisionedSlots)) {
             bucket->activePagesHead = page;
             return true;
         }
 
         ASSERT(page->numAllocatedSlots >= 0);
         if (LIKELY(page->numAllocatedSlots == 0)) {
+            ASSERT(!page->freeCacheIndex);
             // We hit a free page, so shepherd it on to the free page list.
             page->nextPage = bucket->freePagesHead;
             bucket->freePagesHead = page;
         } else {
             // If we get here, we found a full page. Skip over it too, and also
             // tag it as full (via a negative value). We need it tagged so that
             // free'ing can tell, and move it back into the active page list.
             ASSERT(page->numAllocatedSlots == static_cast<int>(partitionBucketSlots(bucket)));
             page->numAllocatedSlots = -page->numAllocatedSlots;
             ++bucket->numFullPages;
@@ skipping 41 matching lines @@
         return partitionPageAllocAndFillFreelist(newPage);
     }
 
     // Second, look in our list of freed but reserved pages.
     PartitionPage* newPage = bucket->freePagesHead;
     if (LIKELY(newPage != 0)) {
         ASSERT(newPage != &PartitionRootGeneric::gSeedPage);
         ASSERT(!newPage->freelistHead);
         ASSERT(!newPage->numAllocatedSlots);
         ASSERT(!newPage->numUnprovisionedSlots);
+        ASSERT(!newPage->freeCacheIndex);
         bucket->freePagesHead = newPage->nextPage;
     } else {
         // Third. If we get here, we need a brand new page.
         size_t numPartitionPages = partitionBucketPartitionPages(bucket);
         void* rawNewPage = partitionAllocPartitionPages(root, numPartitionPages);
         // Skip the alignment check because it depends on page->bucket, which is not yet set.
         newPage = partitionPointerToPageNoAlignmentCheck(rawNewPage);
     }
 
     partitionPageReset(newPage, bucket);
     bucket->activePagesHead = newPage;
     return partitionPageAllocAndFillFreelist(newPage);
 }
 
 static ALWAYS_INLINE void partitionFreePage(PartitionPage* page)
 {
     ASSERT(page->freelistHead);
     ASSERT(!page->numAllocatedSlots);
     partitionUnusePage(page);
     // We actually leave the freed page in the active list. We'll sweep it on
     // to the free page list when we next walk the active page list. Pulling
     // this trick enables us to use a singly-linked page list for all cases,
     // which is critical in keeping the page metadata structure down to 32
     // bytes in size.
     page->freelistHead = 0;
     page->numUnprovisionedSlots = 0;
 }
 
+static ALWAYS_INLINE void partitionRegisterEmptyPage(PartitionPage* page)
+{
+    PartitionRootBase* root = partitionPageToRoot(page);
+    // If the page is already registered as empty, give it another life.
+    if (page->freeCacheIndex) {
+        ASSERT(page->freeCacheIndex <= kMaxFreeableSpans);
+        ASSERT(root->globalEmptyPageRing[page->freeCacheIndex - 1] == page);
+        root->globalEmptyPageRing[page->freeCacheIndex - 1] = 0;
+    }
+
+    ASSERT(root->numGlobalEmptyPageEntries <= kMaxFreeableSpans);
+    if (root->numGlobalEmptyPageEntries == kMaxFreeableSpans) {
+        // Too many freeable pages in the system, must handle one.
+        PartitionPage* pageToFree = root->globalEmptyPageRing[root->globalEmptyPageHeadIndex];
+        // The page might well have been re-activated, filled up, etc. before we
+        // get around to looking at it here.
+        ASSERT(pageToFree != &PartitionRootBase::gSeedPage);
+        ASSERT(!pageToFree || pageToFree == root->globalEmptyPageRing[pageToFree->freeCacheIndex - 1]);
+        --root->numGlobalEmptyPageEntries;
+        ++root->globalEmptyPageHeadIndex;
+        if (root->globalEmptyPageHeadIndex == kMaxFreeableSpans)
+            root->globalEmptyPageHeadIndex = 0;
+        if (pageToFree) {
+            if (!pageToFree->numAllocatedSlots && pageToFree->freelistHead) {
+                // The page is still empty, and not freed, so _really_ free it.
+                partitionFreePage(pageToFree);
+            }
+            pageToFree->freeCacheIndex = 0;
+        }
+    }
+
+    // We put the empty slot span on our global list of "pages that were once
+    // empty". thus providing it a bit of breathing room to get re-used before
+    // we really free it. This improves performance, particularly on Mac OS X
+    // which has subpar memory management performance.
+    size_t tailIndex = root->globalEmptyPageHeadIndex + root->numGlobalEmptyPageEntries;
+    if (tailIndex >= kMaxFreeableSpans)
+        tailIndex -= kMaxFreeableSpans;

[Tom Sepez, 2014/01/14 22:17:10]

nit: assert that it's in range after subtracting.

+    root->globalEmptyPageRing[tailIndex] = page;
+    ++root->numGlobalEmptyPageEntries;
+    page->freeCacheIndex = tailIndex + 1;
+}
+
 void partitionFreeSlowPath(PartitionPage* page)
 {
     PartitionBucket* bucket = page->bucket;
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
     ASSERT(bucket->activePagesHead != &PartitionRootGeneric::gSeedPage);
     if (LIKELY(page->numAllocatedSlots == 0)) {
         // Page became fully unused.
-        // If it's the current page, change it!
+        // If it's the current page, attempt to change it. We'd prefer to leave
+        // the page empty as a gentle force towards defragmentation.
         if (LIKELY(page == bucket->activePagesHead)) {
-            // Change active page, rejecting the current page as a candidate.
-            if (!partitionSetNewActivePage(bucket, false)) {
-                // We do not free the last active page in a bucket.
-                // To do so is a serious performance issue as we can get into
-                // a repeating state change between 0 and 1 objects of a given
-                // size allocated; and each state change incurs either a system
-                // call or a page fault, or more.
-                ASSERT(!page->nextPage);
-                return;
+            if (partitionSetNewActivePage(bucket, false)) {
+                ASSERT(bucket->activePagesHead != page);
+                // Link the empty page back in after the new current page, to
+                // avoid losing a reference to it.
+                // TODO: consider walking the list to link the empty page after
+                // all non-empty pages?
+                PartitionPage* currentPage = bucket->activePagesHead;
+                page->nextPage = currentPage->nextPage;
+                currentPage->nextPage = page;
             }
-            // Link the to-be-freed page back in after the new current page, to
-            // avoid losing a reference to it.
-            PartitionPage* currentPage = bucket->activePagesHead;
-            page->nextPage = currentPage->nextPage;
-            currentPage->nextPage = page;
         }
-        partitionFreePage(page);
+        partitionRegisterEmptyPage(page);
     } else {
         // Ensure that the page is full. That's the only valid case if we
         // arrive here.
         ASSERT(page->numAllocatedSlots < 0);
         page->numAllocatedSlots = -page->numAllocatedSlots - 2;
         ASSERT(page->numAllocatedSlots == static_cast<int>(partitionBucketSlots(bucket) - 1));
         // Fully used page became partially used. It must be put back on the
         // non-full page list. Also make it the current page to increase the
         // chances of it being filled up again. The old current page will be
         // the next page.
         page->nextPage = bucket->activePagesHead;
         bucket->activePagesHead = page;
         --bucket->numFullPages;
         // Special case: for a partition page with just a single slot, it may
         // now be empty and we want to run it through the empty logic.
         if (UNLIKELY(page->numAllocatedSlots == 0))
             partitionFreeSlowPath(page);
-        // Note: there's an opportunity here to look to see if the old active
-        // page is now freeable.
     }
 }
 
 void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newSize)
 {
 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
     return realloc(ptr, newSize);
 #else
     // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the
     // new size is a significant percentage smaller. We could do the same if we
@@ skipping 122 matching lines @@
     printf("total live: %zu bytes\n", totalLive);
     printf("total resident: %zu bytes\n", totalResident);
     printf("total freeable: %zu bytes\n", totalFreeable);
     fflush(stdout);
 }
 
 #endif // !NDEBUG
 
 } // namespace WTF