Add retry logic to partition alloc

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 13 matching lines @@
  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "config.h"
 #include "wtf/PartitionAlloc.h"
 
+#include "wtf/Atomics.h"
+
 #include <string.h>
 
 #ifndef NDEBUG
 #include <stdio.h>
 #endif
 
 // Two partition pages are used as guard / metadata page so make sure the super
 // page size is bigger.
 COMPILE_ASSERT(WTF::kPartitionPageSize * 4 <= WTF::kSuperPageSize, ok_super_page_size);
 COMPILE_ASSERT(!(WTF::kSuperPageSize % WTF::kPartitionPageSize), ok_super_page_multiple);
 // Four system pages gives us room to hack out a still-guard-paged piece
 // of metadata in the middle of a guard partition page.
 COMPILE_ASSERT(WTF::kSystemPageSize * 4 <= WTF::kPartitionPageSize, ok_partition_page_size);
 COMPILE_ASSERT(!(WTF::kPartitionPageSize % WTF::kSystemPageSize), ok_partition_page_multiple);
 COMPILE_ASSERT(sizeof(WTF::PartitionPage) <= WTF::kPageMetadataSize, PartitionPage_not_too_big);
 COMPILE_ASSERT(sizeof(WTF::PartitionBucket) <= WTF::kPageMetadataSize, PartitionBucket_not_too_big);
 COMPILE_ASSERT(sizeof(WTF::PartitionSuperPageExtentEntry) <= WTF::kPageMetadataSize, PartitionSuperPageExtentEntry_not_too_big);
 COMPILE_ASSERT(WTF::kPageMetadataSize * WTF::kNumPartitionPagesPerSuperPage <= WTF::kSystemPageSize, page_metadata_fits_in_hole);
 // Check that some of our zanier calculations worked out as expected.
 COMPILE_ASSERT(WTF::kGenericSmallestBucket == 8, generic_smallest_bucket);
 COMPILE_ASSERT(WTF::kGenericMaxBucketed == 983040, generic_max_bucketed);
 
 namespace WTF {
 
+enum PartitionAllocFlagsInternal {
+    // Flags after to start after all flags in PartitionAllocFlags.
+    PartitionAllocRetry = 1 << 1,
+};
+
 int PartitionRootBase::gInitializedLock = 0;
 bool PartitionRootBase::gInitialized = false;
 PartitionPage PartitionRootBase::gSeedPage;
 PartitionBucket PartitionRootBase::gPagedBucket;
 
 static uint16_t partitionBucketNumSystemPages(size_t size)
 {
     // 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
@@ skipping 226 matching lines @@
     }
     partitionAllocBaseShutdown(root);
     return noLeaks;
 }
 
 static NEVER_INLINE void partitionOutOfMemory()
 {
     IMMEDIATE_CRASH();
 }
 
+static PartitionFreeUpMemoryCallback s_partitionFreeUpMemoryCallback = nullptr;
+static volatile int s_partitionFreeUpMemoryRecusionCount = 0;
+
+void partitionSetFreeUpMemoryCallback(PartitionFreeUpMemoryCallback callback)
+{
+    s_partitionFreeUpMemoryCallback = callback;
+}
+
+static void partitionFreeUpMemory()
+{

[Chris Evans, 2014/11/06 21:45:34]

One more thing. Can we add here a // TODO comment that says we should also take
the opportunity to flush the ring list of unused but still committed pages?

+    if (atomicTestAndSetToOne(&s_partitionFreeUpMemoryRecusionCount))
+        return;
+    if (s_partitionFreeUpMemoryCallback)
+        s_partitionFreeUpMemoryCallback();

[Chris Evans, 2014/11/06 21:43:51]

Ah, so s_partitionFreeUpMemoryCallback() is going to by definition re-enter the
allocator, for example partitionFreeGeneric().

Currently, this won't work -- partitionFreeGeneric() will attempt to take the
lock, which will deadlock because it is already held. We're using a plain old
spinlock and not a recursive lock.

We could drop and then re-acquire the lock but that does make me a little
nervous. It may also be tricky, actually: at this level we don't know what type
of partition we're dealing with (generic, which has locks vs. sized which is
lockless).

I bet the code paths within the callback will be a little complicated. So I
would not be surprised if something tried to allocate memory. Aside from the
deadlock concern above, this would now raise the spectre of re-entering
partitionFreeUpMemory().

If we do proceed with this patch, we might want to define what our exact
re-entrancy expectations are and add some ASSERT()s to make sure the callback
implementation is not being naughty.

+    atomicSetOneToZero(&s_partitionFreeUpMemoryRecusionCount);
+}
+
 static ALWAYS_INLINE void partitionDecommitSystemPages(PartitionRootBase* root, void* addr, size_t len)
 {
     decommitSystemPages(addr, len);
     ASSERT(root->totalSizeOfCommittedPages > len);
     root->totalSizeOfCommittedPages -= len;
 }
 
 static ALWAYS_INLINE void partitionRecommitSystemPages(PartitionRootBase* root, void* addr, size_t len)
 {
     recommitSystemPages(addr, len);
@@ skipping 373 matching lines @@
             goto partitionAllocSlowPathFailed;
         // 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);
 
 partitionAllocSlowPathFailed:
+    if (!(flags & PartitionAllocRetry)) {
+        partitionFreeUpMemory();

[Chris Evans, 2014/11/06 21:43:51]

Nit: I wonder if we want a comment here to say that this is tail re-entrancy and
to be careful not to rely on previously calculated state after this call?

+        void* ptr = partitionAllocSlowPath(root, flags | PartitionAllocRetry, size, bucket);

[Jens Widell, 2014/10/22 11:24:05]

Wouldn't it be better to retry partitionBucketAlloc() instead of
partitionAllocSlowPath()?

By trying partitionAllocSlowPath() you bypass the per-bucket freelist check, and
partitionAllocSlowPath() begins with an assert that that freelist is empty. If
memory has actually been freed, typically the freelist wouldn't be empty.

[Chris Evans, 2014/11/06 21:43:51]

I agree that partitionBucketAlloc() is the correct API to call.

+        if (ptr)
+            return ptr;
+    }
+
     if (returnNull)
         return nullptr;
     partitionOutOfMemory();
     return nullptr;
 }
 
 static ALWAYS_INLINE void partitionFreePage(PartitionRootBase* root, PartitionPage* page)
 {
     ASSERT(page->freelistHead);
     ASSERT(!page->numAllocatedSlots);
@@ skipping 261 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