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

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 101 matching lines @@
     size_t numSlots = (page->bucket->numSystemPagesPerSlotSpan * WTF::kSystemPageSize) / size;
     EXPECT_EQ(numSlots, static_cast<size_t>(abs(page->numAllocatedSlots)));
     char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
     size_t i;
     for (i = 0; i < numSlots; ++i) {
         partitionFree(ptr + kPointerOffset);
         ptr += size;
     }
 }
 
+static void CycleFreeCache(size_t size)
+{
+    size_t realSize = size + kExtraAllocSize;
+    size_t bucketIdx = realSize >> WTF::kBucketShift;
+    WTF::PartitionBucket* bucket = &allocator.root()->buckets()[bucketIdx];
+    ASSERT(!bucket->activePagesHead->numAllocatedSlots);
+
+    for (size_t i = 0; i < WTF::kMaxFreeableSpans; ++i) {
+        void* ptr = partitionAlloc(allocator.root(), size);
+        EXPECT_EQ(1, bucket->activePagesHead->numAllocatedSlots);
+        partitionFree(ptr);
+        EXPECT_EQ(0, bucket->activePagesHead->numAllocatedSlots);
+        EXPECT_NE(-1, bucket->activePagesHead->freeCacheIndex);
+    }
+}
+
 // Check that the most basic of allocate / free pairs work.
 TEST(WTF_PartitionAlloc, Basic)
 {
     TestSetup();
     WTF::PartitionBucket* bucket = &allocator.root()->buckets()[kTestBucketIndex];
     WTF::PartitionPage* seedPage = &WTF::PartitionRootGeneric::gSeedPage;
 
     EXPECT_FALSE(bucket->freePagesHead);
     EXPECT_EQ(seedPage, bucket->activePagesHead);
     EXPECT_EQ(0, bucket->activePagesHead->nextPage);
@@ skipping 89 matching lines @@
     // Allocate a new page, it should pull from the freelist.
     page = GetFullPage(kTestAllocSize);
     EXPECT_FALSE(bucket->freePagesHead);
     EXPECT_EQ(page, bucket->activePagesHead);
 
     FreeFullPage(page);
     FreeFullPage(page2);
     EXPECT_EQ(0, page->numAllocatedSlots);
     EXPECT_EQ(0, page2->numAllocatedSlots);
     EXPECT_EQ(0, page2->numUnprovisionedSlots);
-    EXPECT_EQ(0, page2->freelistHead);
+    EXPECT_NE(-1, page2->freeCacheIndex);
 
     TestShutdown();
 }
 
 // Test some finer aspects of internal page transitions.
 TEST(WTF_PartitionAlloc, PageTransitions)
 {
     TestSetup();
     WTF::PartitionBucket* bucket = &allocator.root()->buckets()[kTestBucketIndex];
 
@@ skipping 64 matching lines @@
     OwnPtr<WTF::PartitionPage*[]> pages = adoptArrayPtr(new WTF::PartitionPage*[numToFillFreeListPage]);
 
     size_t i;
     for (i = 0; i < numToFillFreeListPage; ++i) {
         pages[i] = GetFullPage(kTestAllocSize);
     }
     EXPECT_EQ(pages[numToFillFreeListPage - 1], bucket->activePagesHead);
     for (i = 0; i < numToFillFreeListPage; ++i)
         FreeFullPage(pages[i]);
     EXPECT_EQ(0, bucket->activePagesHead->numAllocatedSlots);
-    EXPECT_EQ(0, bucket->activePagesHead->nextPage->freelistHead);
+    EXPECT_NE(-1, bucket->activePagesHead->nextPage->freeCacheIndex);
     EXPECT_EQ(0, bucket->activePagesHead->nextPage->numAllocatedSlots);
     EXPECT_EQ(0, bucket->activePagesHead->nextPage->numUnprovisionedSlots);
 
     // Allocate / free in a different bucket size so we get control of a
     // different free page list. We need two pages because one will be the last
     // active page and not get freed.
     WTF::PartitionPage* page1 = GetFullPage(kTestAllocSize * 2);
     WTF::PartitionPage* page2 = GetFullPage(kTestAllocSize * 2);
     FreeFullPage(page1);
     FreeFullPage(page2);
 
     // If we re-allocate all kTestAllocSize allocations, we'll pull all the
     // free pages and end up freeing the first page for free page objects.
     // It's getting a bit tricky but a nice re-entrancy is going on:
     // alloc(kTestAllocSize) -> pulls page from free page list ->
     // free(PartitionFreepagelistEntry) -> last entry in page freed ->
     // alloc(PartitionFreepagelistEntry).
     for (i = 0; i < numToFillFreeListPage; ++i) {
         pages[i] = GetFullPage(kTestAllocSize);
     }
     EXPECT_EQ(pages[numToFillFreeListPage - 1], bucket->activePagesHead);
 
     // As part of the final free-up, we'll test another re-entrancy:
     // free(kTestAllocSize) -> last entry in page freed ->
     // alloc(PartitionFreepagelistEntry) -> pulls page from free page list ->
     // free(PartitionFreepagelistEntry)
     for (i = 0; i < numToFillFreeListPage; ++i)
         FreeFullPage(pages[i]);
     EXPECT_EQ(0, bucket->activePagesHead->numAllocatedSlots);
-    EXPECT_EQ(0, bucket->activePagesHead->nextPage->freelistHead);
+    EXPECT_NE(-1, bucket->activePagesHead->nextPage->freeCacheIndex);
     EXPECT_EQ(0, bucket->activePagesHead->nextPage->numAllocatedSlots);
     EXPECT_EQ(0, bucket->activePagesHead->nextPage->numUnprovisionedSlots);
 
     TestShutdown();
 }
 
 // Test a large series of allocations that cross more than one underlying
 // 64KB super page allocation.
 TEST(WTF_PartitionAlloc, MultiPageAllocs)
 {
@@ skipping 127 matching lines @@
     partitionFreeGeneric(genericAllocator.root(), ptr);
 
     // kPartitionPageSize is interesting because it results in just one
     // allocation per page, which tripped up some corner cases.
     size_t size = WTF::kPartitionPageSize - kExtraAllocSize;
     ptr = partitionAllocGeneric(genericAllocator.root(), size);
     EXPECT_TRUE(ptr);
     void* ptr2 = partitionAllocGeneric(genericAllocator.root(), size);
     EXPECT_TRUE(ptr2);
     partitionFreeGeneric(genericAllocator.root(), ptr);
-    // Should have freelisted at this point.
+    // Should be freeable at this point.
     WTF::PartitionPage* page = WTF::partitionPointerToPage(WTF::partitionCookieFreePointerAdjust(ptr));
-#if 0 // Temporarily disabled, see crbug.com/332282
-    EXPECT_TRUE(page->bucket->freePagesHead);
-#endif
+    EXPECT_NE(-1, page->freeCacheIndex);
     partitionFreeGeneric(genericAllocator.root(), ptr2);
 
     size = WTF::kGenericMaxBucketed - kExtraAllocSize;
     ptr = partitionAllocGeneric(genericAllocator.root(), size);
     EXPECT_TRUE(ptr);
     memset(ptr, 'A', size);
     ptr2 = partitionAllocGeneric(genericAllocator.root(), size);
     EXPECT_TRUE(ptr2);
     void* ptr3 = partitionAllocGeneric(genericAllocator.root(), size);
     EXPECT_TRUE(ptr3);
     void* ptr4 = partitionAllocGeneric(genericAllocator.root(), size);
     EXPECT_TRUE(ptr4);
 
     page = WTF::partitionPointerToPage(WTF::partitionCookieFreePointerAdjust(ptr));
     WTF::PartitionPage* page2 = WTF::partitionPointerToPage(WTF::partitionCookieFreePointerAdjust(ptr3));
     EXPECT_NE(page, page2);
 
     partitionFreeGeneric(genericAllocator.root(), ptr);
     partitionFreeGeneric(genericAllocator.root(), ptr3);
     partitionFreeGeneric(genericAllocator.root(), ptr2);
-    // Should have been freed at this point.
-    EXPECT_FALSE(page->freelistHead);
+    // Should be freeable at this point.
+    EXPECT_NE(-1, page->freeCacheIndex);
     EXPECT_EQ(0, page->numAllocatedSlots);
     EXPECT_EQ(0, page->numUnprovisionedSlots);
     void* newPtr = partitionAllocGeneric(genericAllocator.root(), size);
     EXPECT_EQ(ptr3, newPtr);
     newPtr = partitionAllocGeneric(genericAllocator.root(), size);
-    EXPECT_EQ(ptr, newPtr);
+    EXPECT_EQ(ptr2, newPtr);
 #if OS(LINUX) && defined(NDEBUG)
     // On Linux, we have a guarantee that freelisting a page should cause its
     // contents to be nulled out. We check for null here to detect an bug we
     // had where a large slot size was causing us to not properly free all
     // resources back to the system.
     // We only run the check in optimized builds because the debug build
     // writes over the allocated area with an "uninitialized" byte pattern.
     EXPECT_EQ(0, *(reinterpret_cast<char*>(newPtr) + (size - 1)));
 #endif
     partitionFreeGeneric(genericAllocator.root(), newPtr);
@@ skipping 55 matching lines @@
     partitionFree(ptr);
     ptr = partitionAlloc(allocator.root(), bigSize);
     void* ptr6 = partitionAlloc(allocator.root(), bigSize);
 
     partitionFree(ptr);
     partitionFree(ptr2);
     partitionFree(ptr3);
     partitionFree(ptr4);
     partitionFree(ptr5);
     partitionFree(ptr6);
-    EXPECT_TRUE(bucket->freePagesHead);
-    EXPECT_EQ(page, bucket->freePagesHead);
+    EXPECT_NE(-1, page->freeCacheIndex);
+    EXPECT_NE(-1, page2->freeCacheIndex);
     EXPECT_TRUE(page2->freelistHead);
     EXPECT_EQ(0, page2->numAllocatedSlots);
 
     // And test a couple of sizes that do not cross kSystemPageSize with a single allocation.
     size_t mediumSize = (WTF::kSystemPageSize / 2) - kExtraAllocSize;
     bucketIdx = (mediumSize + kExtraAllocSize) >> WTF::kBucketShift;
     bucket = &allocator.root()->buckets()[bucketIdx];
     EXPECT_EQ(0, bucket->freePagesHead);
 
     ptr = partitionAlloc(allocator.root(), mediumSize);
@@ skipping 182 matching lines @@
 
     FreeFullPage(pageInThirdSuperPage);
     for (i = 0; i < numPartitionPagesNeeded; ++i) {
         FreeFullPage(firstSuperPagePages[i]);
         FreeFullPage(secondSuperPagePages[i]);
     }
 
     TestShutdown();
 }
 
+// Tests that pages in the free page cache do get freed as appropriate.
+TEST(WTF_PartitionAlloc, FreeCache)
+{
+    TestSetup();
+
+    size_t bigSize = allocator.root()->maxAllocation - kExtraAllocSize;
+    size_t bucketIdx = (bigSize + kExtraAllocSize) >> WTF::kBucketShift;
+    WTF::PartitionBucket* bucket = &allocator.root()->buckets()[bucketIdx];
+
+    void* ptr = partitionAlloc(allocator.root(), bigSize);
+    EXPECT_TRUE(ptr);
+    WTF::PartitionPage* page = WTF::partitionPointerToPage(WTF::partitionCookieFreePointerAdjust(ptr));
+    EXPECT_EQ(0, bucket->freePagesHead);
+    EXPECT_EQ(1, page->numAllocatedSlots);
+    partitionFree(ptr);
+    EXPECT_EQ(0, page->numAllocatedSlots);
+    EXPECT_NE(-1, page->freeCacheIndex);
+    EXPECT_TRUE(page->freelistHead);
+
+    CycleFreeCache(kTestAllocSize);
+
+    // Flushing the cache should have really freed the unused page.
+    EXPECT_FALSE(page->freelistHead);
+    EXPECT_EQ(-1, page->freeCacheIndex);
+    EXPECT_EQ(0, page->numAllocatedSlots);
+
+    // Check that an allocation works ok whilst in this state (a free'd page
+    // as the active pages head).
+    ptr = partitionAlloc(allocator.root(), bigSize);
+    EXPECT_FALSE(bucket->freePagesHead);
+    partitionFree(ptr);
+
+    // Also check that a page that is bouncing immediately between empty and
+    // used does not get freed.
+    for (size_t i = 0; i < WTF::kMaxFreeableSpans * 2; ++i) {
+        ptr = partitionAlloc(allocator.root(), bigSize);
+        EXPECT_TRUE(page->freelistHead);
+        partitionFree(ptr);
+        EXPECT_TRUE(page->freelistHead);
+    }
+
+    TestShutdown();
+}
+
 // Make sure that malloc(-1) dies.
 // In the past, we had an integer overflow that would alias malloc(-1) to
 // malloc(0), which is not good.
 TEST(WTF_PartitionAllocDeathTest, LargeAllocs)
 {
     TestSetup();
     // Largest alloc.
     EXPECT_DEATH(partitionAllocGeneric(genericAllocator.root(), static_cast<size_t>(-1)), "");
     // And the smallest allocation we expect to die.
     EXPECT_DEATH(partitionAllocGeneric(genericAllocator.root(), static_cast<size_t>(INT_MAX) + 1), "");
@@ skipping 36 matching lines @@
     EXPECT_EQ(32u, WTF::countLeadingZerosSizet(0));
     EXPECT_EQ(31u, WTF::countLeadingZerosSizet(1));
     EXPECT_EQ(1u, WTF::countLeadingZerosSizet(1 << 30));
     EXPECT_EQ(0u, WTF::countLeadingZerosSizet(1 << 31));
 #endif
 }
 
 } // namespace
 
 #endif // !defined(MEMORY_TOOL_REPLACES_ALLOCATOR)