Improve partitionAlloc's resistance to fragmentation.

Source/wtf/PartitionAllocTest.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 200 matching lines @@
 }
 
 // Test some finer aspects of internal page transitions.
 TEST(WTF_PartitionAlloc, PageTransitions)
 {
     TestSetup();
     size_t bucketIdx = kTestAllocSize >> WTF::kBucketShift;
     WTF::PartitionBucket* bucket = &allocator.root()->buckets()[bucketIdx];
 
     WTF::PartitionPageHeader* page1 = GetFullPage(kTestAllocSize);
+    EXPECT_EQ(page1, bucket->currPage);
+    EXPECT_EQ(page1, page1->next);
+    EXPECT_EQ(page1, page1->prev);
     WTF::PartitionPageHeader* page2 = GetFullPage(kTestAllocSize);
     EXPECT_EQ(page2, bucket->currPage);
-    EXPECT_EQ(page1, page2->next);
-    EXPECT_EQ(page1, page2->prev);
+    EXPECT_EQ(page2, page2->next);
+    EXPECT_EQ(page2, page2->prev);
+
+    // Bounce page1 back into the non-full list then fill it up again.
+    char* ptr = reinterpret_cast<char*>(page1) + sizeof(WTF::PartitionPageHeader);
+    partitionFree(ptr);
+    (void) partitionAlloc(allocator.root(), kTestAllocSize);
+    EXPECT_EQ(page1, bucket->currPage);
+
     // Allocating another page at this point should cause us to scan over page1
     // (which is both full and NOT our current page), and evict it from the
     // freelist. Older code had a O(n^2) condition due to failure to do this.
     WTF::PartitionPageHeader* page3 = GetFullPage(kTestAllocSize);
     EXPECT_EQ(page3, bucket->currPage);
-    EXPECT_EQ(page2, page3->next);
-    EXPECT_EQ(page3, page2->next);
+    EXPECT_EQ(page3, page3->next);
+    EXPECT_EQ(page3, page3->next);
 
     // Work out a pointer into page2 and free it.
-    char* ptr = reinterpret_cast<char*>(page2) + sizeof(WTF::PartitionPageHeader);
+    ptr = reinterpret_cast<char*>(page2) + sizeof(WTF::PartitionPageHeader);
     partitionFree(ptr);
     // Trying to allocate at this time should cause us to cycle around to page2
     // and find the recently freed slot.
     char* newPtr = reinterpret_cast<char*>(partitionAlloc(allocator.root(), kTestAllocSize));
     EXPECT_EQ(ptr, newPtr);
     EXPECT_EQ(page2, bucket->currPage);
 
     // Work out a pointer into page1 and free it. This should pull the page
     // back into the ring list of available pages.
     ptr = reinterpret_cast<char*>(page1) + sizeof(WTF::PartitionPageHeader);
@@ skipping 217 matching lines @@
     void* ptr3 = partitionAlloc(allocator.root(), bigSize);
     EXPECT_TRUE(ptr3);
     EXPECT_EQ(0, page->freelistHead);
     EXPECT_EQ(3, page->numAllocatedSlots);
 
     void* ptr4 = partitionAlloc(allocator.root(), bigSize);
     EXPECT_TRUE(ptr4);
     WTF::PartitionPageHeader* page2 = reinterpret_cast<WTF::PartitionPageHeader*>(reinterpret_cast<size_t>(ptr4) & WTF::kPartitionPageBaseMask);
     EXPECT_EQ(1, page2->numAllocatedSlots);
 
+    // Churn things a little whilst there's a partial page freelist.
+    partitionFree(ptr);
+    ptr = partitionAlloc(allocator.root(), bigSize);
+    void* ptr5 = partitionAlloc(allocator.root(), bigSize);
+
     partitionFree(ptr);
     partitionFree(ptr2);
     partitionFree(ptr3);
     partitionFree(ptr4);
+    partitionFree(ptr5);
     EXPECT_TRUE(bucket->freePages);
     EXPECT_EQ(page, bucket->freePages->page);
     EXPECT_TRUE(page2->freelistHead);
     EXPECT_EQ(0, page2->numAllocatedSlots);
 
     // And test a couple of sizes that do not cross kSubPartitionPageSize with a single allocation.
     size_t mediumSize = WTF::kSubPartitionPageSize / 2;
     bucketIdx = mediumSize >> WTF::kBucketShift;
     bucket = &allocator.root()->buckets()[bucketIdx];
     EXPECT_EQ(0, bucket->freePages);
@@ skipping 36 matching lines @@
     firstPageSlots = (WTF::kSubPartitionPageSize - sizeof(WTF::PartitionPageHeader)) / verySmallSize;
     EXPECT_EQ(totalSlots - firstPageSlots, page->numUnprovisionedSlots);
 
     partitionFree(ptr);
     EXPECT_TRUE(page->freelistHead);
     EXPECT_EQ(0, page->numAllocatedSlots);
 
     TestShutdown();
 }
 
+// Test some of the fragmentation-resistant properties of the allocator.
+TEST(WTF_PartitionAlloc, PageRefilling)
+{
+    TestSetup();
+    size_t bucketIdx = kTestAllocSize >> WTF::kBucketShift;
+    WTF::PartitionBucket* bucket = &allocator.root()->buckets()[bucketIdx];
+
+    // Grab two full pages and a non-full page.
+    WTF::PartitionPageHeader* page1 = GetFullPage(kTestAllocSize);
+    WTF::PartitionPageHeader* page2 = GetFullPage(kTestAllocSize);
+    void* ptr = partitionAlloc(allocator.root(), kTestAllocSize);
+    EXPECT_TRUE(ptr);
+    EXPECT_NE(page1, bucket->currPage);
+    EXPECT_NE(page2, bucket->currPage);
+    WTF::PartitionPageHeader* page = reinterpret_cast<WTF::PartitionPageHeader*>(reinterpret_cast<size_t>(ptr) & WTF::kPartitionPageBaseMask);
+    EXPECT_EQ(1, page->numAllocatedSlots);
+
+    // Work out a pointer into page2 and free it; and then page1 and free it.
+    char* ptr2 = reinterpret_cast<char*>(page1) + sizeof(WTF::PartitionPageHeader);
+    partitionFree(ptr2);
+    ptr2 = reinterpret_cast<char*>(page2) + sizeof(WTF::PartitionPageHeader);
+    partitionFree(ptr2);
+
+    // If we perform two allocations from the same bucket now, we expect to
+    // refill both the nearly full pages.
+    (void) partitionAlloc(allocator.root(), kTestAllocSize);
+    (void) partitionAlloc(allocator.root(), kTestAllocSize);
+    EXPECT_EQ(1, page->numAllocatedSlots);
+
+    FreeFullPage(page2, kTestAllocSize);
+    FreeFullPage(page1, kTestAllocSize);
+    partitionFree(ptr);
+
+    TestShutdown();
+}
+
 #if OS(POSIX)
 
 // Test correct handling if our mapping collides with another.
 TEST(WTF_PartitionAlloc, MappingCollision)
 {
     TestSetup();
     // The -1 is because the first super page allocated with have its first partition page marked as a guard page.
     size_t numPartitionPagesNeeded = (WTF::kSuperPageSize / WTF::kPartitionPageSize) - 1;
     OwnArrayPtr<WTF::PartitionPageHeader*> firstSuperPagePages = adoptArrayPtr(new WTF::PartitionPageHeader*[numPartitionPagesNeeded]);
     OwnArrayPtr<WTF::PartitionPageHeader*> secondSuperPagePages = adoptArrayPtr(new WTF::PartitionPageHeader*[numPartitionPagesNeeded]);
@@ skipping 41 matching lines @@
     }
 
     TestShutdown();
 }
 
 #endif // OS(POSIX)
 
 } // namespace
 
 #endif // !defined(MEMORY_TOOL_REPLACES_ALLOCATOR)