Improve partitionAlloc's resistance to fragmentation.

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/PageAllocator.h"
 #include <string.h>
 
 #ifndef NDEBUG
 #include <stdio.h>
 #endif
 
 // A super page is at least 4 partition pages in order to make re-entrancy considerations simpler in partitionAllocPage().
 COMPILE_ASSERT(WTF::kPartitionPageSize * 4 <= WTF::kSuperPageSize, ok_partition_page_size);
 COMPILE_ASSERT(!(WTF::kSuperPageSize % WTF::kPartitionPageSize), ok_partition_page_multiple);
 COMPILE_ASSERT(!(WTF::kPartitionPageSize % WTF::kSubPartitionPageSize), ok_sub_partition_page_multiple);
@@ skipping 233 matching lines @@
 
 static ALWAYS_INLINE void partitionUnlinkPage(PartitionPageHeader* page)
 {
     ASSERT(page->prev->next == page);
     ASSERT(page->next->prev == page);
 
     page->next->prev = page->prev;
     page->prev->next = page->next;
 }
 
-static ALWAYS_INLINE void partitionLinkPage(PartitionPageHeader* newPage, PartitionPageHeader* prevPage)
+static ALWAYS_INLINE void partitionLinkPageBefore(PartitionPageHeader* newPage, PartitionPageHeader* nextPage)
 {
-    ASSERT(prevPage->prev->next == prevPage);
-    ASSERT(prevPage->next->prev == prevPage);
+    ASSERT(nextPage->prev->next == nextPage);
+    ASSERT(nextPage->next->prev == nextPage);
 
-    newPage->prev = prevPage;
-    newPage->next = prevPage->next;
+    newPage->next = nextPage;
+    newPage->prev = nextPage->prev;
 
-    prevPage->next->prev = newPage;
-    prevPage->next = newPage;
+    nextPage->prev->next = newPage;
+    nextPage->prev = newPage;
 }
 
 void* partitionAllocSlowPath(PartitionBucket* bucket)
 {
     // The slow path is called when the freelist is empty.
     PartitionPageHeader* page = bucket->currPage;
     PartitionPageHeader* next = page->next;
     ASSERT(page == &bucket->root->seedPage || (page->bucket == bucket && next->bucket == bucket));
 
-    // First, see if the partition page still has capacity and if so, fill out
-    // the freelist a little more.
+    // First, see if the current partition page still has capacity and if so,
+    // fill out the freelist a little more.
     if (LIKELY(page->numUnprovisionedSlots))
         return partitionPageAllocAndFillFreelist(page);
 
     // Second, look for a page in our linked ring list of non-full pages.
     while (LIKELY(next != page)) {
         ASSERT(next->bucket == bucket);
         ASSERT(next->next->prev == next);
         ASSERT(next->prev->next == next);
         ASSERT(next != &bucket->root->seedPage);
         if (LIKELY(next->freelistHead != 0)) {
             bucket->currPage = next;
             PartitionFreelistEntry* ret = next->freelistHead;
             next->freelistHead = partitionFreelistMask(ret->next);
             next->numAllocatedSlots++;
             return ret;
         }
+        if (LIKELY(next->numUnprovisionedSlots)) {
+            bucket->currPage = next;
+            return partitionPageAllocAndFillFreelist(next);
+        }
         // Pull this page out of the non-full page list, since it has no free
         // slots.
         // This tags the page as full so that free'ing can tell, and move
         // the page back into the non-full page list when appropriate.
         ASSERT(next->numAllocatedSlots == partitionBucketSlots(bucket));
         next->numAllocatedSlots = -next->numAllocatedSlots;
         partitionUnlinkPage(next);
         ++bucket->numFullPages;
 
         next = next->next;
     }
 
-    // Second, look in our list of freed but reserved pages.
+    // After we've considered and rejected every partition page in the list,
+    // we should by definition have a single self-linked page left. We will
+    // replace this single page with the new page we choose.
+    ASSERT(page == page->next);
+    ASSERT(page == page->prev);
+    ASSERT(page == &bucket->root->seedPage || page->numAllocatedSlots == partitionBucketSlots(bucket));
+    if (LIKELY(page != &bucket->root->seedPage)) {
+        page->numAllocatedSlots = -page->numAllocatedSlots;
+        ++bucket->numFullPages;
+    }
+
+    // Third, look in our list of freed but reserved pages.
     PartitionPageHeader* newPage;
     PartitionFreepagelistEntry* pagelist = bucket->freePages;
     if (LIKELY(pagelist != 0)) {
         newPage = pagelist->page;
         bucket->freePages = pagelist->next;
         partitionFree(pagelist);
         ASSERT(page != &bucket->root->seedPage);
-        partitionLinkPage(newPage, page);
     } else {
-        // Third. If we get here, we need a brand new page.
+        // Fourth. If we get here, we need a brand new page.
         newPage = partitionAllocPage(bucket->root);
-        if (UNLIKELY(page == &bucket->root->seedPage)) {
-            // If this is the first page allocation to this bucket, then
-            // fully replace the seed page. This avoids pointlessly iterating
-            // over it.
-            newPage->prev = newPage;
-            newPage->next = newPage;
-        } else {
-            partitionLinkPage(newPage, page);
-        }
     }
 
+    newPage->prev = newPage;
+    newPage->next = newPage;
     bucket->currPage = newPage;
     partitionPageReset(newPage, bucket);
     return partitionPageAllocAndFillFreelist(newPage);
 }
 
 void partitionFreeSlowPath(PartitionPageHeader* page)
 {
     PartitionBucket* bucket = page->bucket;
     if (LIKELY(page->numAllocatedSlots == 0)) {
         // Page became fully unused.
-        // If it's the current page, leave it be so that we don't bounce a page
-        // onto the free page list and immediately back out again.
-        if (LIKELY(page == bucket->currPage))
-            return;
+        // If it's the current page, change it!
+        if (LIKELY(page == bucket->currPage)) {
+            if (UNLIKELY(page->next == page)) {
+                // For now, we do not free the last partition page in a bucket.
+                return;
+            }
+            bucket->currPage = page->next;
+        }
 
         partitionUnlinkPage(page);
         partitionUnusePage(page);
         PartitionFreepagelistEntry* entry = static_cast<PartitionFreepagelistEntry*>(partitionBucketAlloc(&bucket->root->buckets()[kInternalMetadataBucket]));
         entry->page = page;
         entry->next = bucket->freePages;
         bucket->freePages = entry;
     } else {
         // Fully used page became partially used. It must be put back on the
-        // non-full page list.
-        partitionLinkPage(page, bucket->currPage);
+        // 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.
+        partitionLinkPageBefore(page, bucket->currPage);
+        bucket->currPage = page;
         page->numAllocatedSlots = -page->numAllocatedSlots - 2;
         ASSERT(page->numAllocatedSlots == partitionBucketSlots(bucket) - 1);
         --bucket->numFullPages;
     }
 }
 
 void* partitionReallocGeneric(PartitionRoot* root, void* ptr, size_t newSize)
 {
 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
     return realloc(ptr, newSize);
@@ skipping 77 matching lines @@
     printf("total live: %ld bytes\n", totalLive);
     printf("total resident: %ld bytes\n", totalResident);
     printf("total freeable: %ld bytes\n", totalFreeable);
     fflush(stdout);
 }
 
 #endif // !NDEBUG
 
 } // namespace WTF