PartitionAlloc: support in-place resize of directly mapped allocation

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 29 matching lines @@
 // 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::PartitionSuperPageExtentEntry) <= WTF::kPageMetadataSize, PartitionSuperPageExtentEntry_not_too_big);
+COMPILE_ASSERT(sizeof(WTF::PartitionBucket) <= WTF::kPageMetadataSize, PartitionBucket_not_too_big);

[Chris Evans, 2014/03/06 06:30:20]

Nit: maybe put this directly under PartitionPa ge_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 {
 
 int PartitionRootBase::gInitializedLock = 0;
 bool PartitionRootBase::gInitialized = false;
 PartitionPage PartitionRootBase::gSeedPage;
@@ skipping 457 matching lines @@
             RELEASE_ASSERT(bucket->numFullPages);
             // Not necessary but might help stop accidents.
             page->nextPage = 0;
         }
     }
 
     bucket->activePagesHead = 0;
     return false;
 }
 
+struct PartitionDirectMapExtent {
+    size_t mapSize; // Mapped size, not including guard pages and meta-data.
+};
+
+static ALWAYS_INLINE PartitionDirectMapExtent* partitionPageToDirectMapExtent(PartitionPage* page)
+{
+    ASSERT(partitionBucketIsDirectMapped(page->bucket));
+    return reinterpret_cast<PartitionDirectMapExtent*>(reinterpret_cast<char*>(page) + 2 * kPageMetadataSize);
+}
+
 static ALWAYS_INLINE void* partitionDirectMap(PartitionRootBase* root, int flags, size_t size)
 {
     size = partitionDirectMapSize(size);
 
     // Because we need to fake looking like a super page, We need to allocate
     // a bunch of system pages more than "size":
     // - The first few system pages are the partition page in which the super
     // page metadata is stored. We fault just one system page out of a partition
     // page sized clump.
     // - We add a trailing guard page.
@@ skipping 37 matching lines @@
     page->numUnprovisionedSlots = 0;
     page->pageOffset = 0;
     page->freeCacheIndex = 0;
 
     bucket->activePagesHead = 0;
     bucket->freePagesHead = 0;
     bucket->slotSize = size;
     bucket->numSystemPagesPerSlotSpan = 0;
     bucket->numFullPages = 0;
 
+    PartitionDirectMapExtent* mapExtent = partitionPageToDirectMapExtent(page);
+    mapExtent->mapSize = mapSize - kPartitionPageSize - kSystemPageSize;
+
     return ret;
 }
 
 static ALWAYS_INLINE void partitionDirectUnmap(PartitionPage* page)
 {
-    size_t unmapSize = page->bucket->slotSize;
+    size_t unmapSize = partitionPageToDirectMapExtent(page)->mapSize;
+
     // Add on the size of the trailing guard page and preceeding partition
-    // page, then round up to allocation granularity.
+    // page.
     unmapSize += kPartitionPageSize + kSystemPageSize;
-    unmapSize += kPageAllocationGranularityOffsetMask;
-    unmapSize &= kPageAllocationGranularityBaseMask;
+
+    ASSERT(!(unmapSize & kPageAllocationGranularityOffsetMask));
 
     char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
     // Account for the mapping starting a partition page before the actual
     // allocation address.
     ptr -= kPartitionPageSize;
 
     freePages(ptr, unmapSize);
 }
 
 void* partitionAllocSlowPath(PartitionRootBase* root, int flags, size_t size, PartitionBucket* bucket)
@@ skipping 151 matching lines @@
         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);
     }
 }
 
+bool partitionReallocDirectMappedInPlace(PartitionRootGeneric* root, PartitionPage* page, size_t newSize)
+{
+    newSize = partitionCookieSizeAdjustAdd(newSize);
+
+    // Note that the new size might be a bucketed size; this function is called
+    // whenever we're reallocating a direct mapped allocation.
+    newSize = partitionDirectMapSize(newSize);
+    if (newSize < kGenericMinDirectMappedDownsize)
+        return false;
+
+    ASSERT(partitionBucketIsDirectMapped(page->bucket));

[Chris Evans, 2014/03/06 06:30:20]

Nit: maybe put the ASSERT at the top of the function, so it always executes
regardless of the above branch. I think it's an invariant.

+
+    // bucket->slotSize is the current size of the allocation.
+    size_t currentSize = page->bucket->slotSize;
+    if (newSize == currentSize)
+        return true;
+
+    char* charPtr = static_cast<char*>(partitionPageToPointer(page));
+
+    if (newSize < currentSize) {
+        // Shrink by decommitting unneeded pages and making them inaccessible.
+        size_t decommitSize = currentSize - newSize;
+        decommitSystemPages(charPtr + newSize, decommitSize);
+        setSystemPagesInaccessible(charPtr + newSize, decommitSize);
+    } else if (newSize <= partitionPageToDirectMapExtent(page)->mapSize) {
+        // Grow within the actually allocated memory. Just need to make the
+        // pages accessible again.
+        size_t recommitSize = newSize - currentSize;
+        setSystemPagesAccessible(charPtr + currentSize, recommitSize);
+
+#ifndef NDEBUG
+        memset(charPtr + currentSize, kUninitializedByte, recommitSize);
+#endif
+    } else {
+        // We can't perform the realloc in-place.
+        // TODO: support this too when possible.
+        return false;
+    }
+
+#ifndef NDEBUG
+    // Write a new trailing cookie.
+    partitionCookieWriteValue(charPtr + newSize - kCookieSize);
+#endif
+
+    page->bucket->slotSize = newSize;
+    return true;
+}
+
 void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newSize)
 {
 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
     return realloc(ptr, newSize);
 #else
     if (UNLIKELY(!ptr))
         return partitionAllocGeneric(root, newSize);
     if (UNLIKELY(!newSize)) {
         partitionFreeGeneric(root, ptr);
         return 0;
     }
 
+    RELEASE_ASSERT(newSize <= kGenericMaxDirectMapped);
+
     ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(ptr)));
 
+    PartitionPage* page = partitionPointerToPage(partitionCookieFreePointerAdjust(ptr));
+
+    if (partitionBucketIsDirectMapped(page->bucket)) {

[Chris Evans, 2014/03/06 06:31:23]

Nit: could add UNLIKELY around this condition, as suggested in previous
iteration of feedback.

+        // We may be able to perform the realloc in place by changing the
+        // accessibility of memory pages and, if reducing the size, decommitting
+        // them.
+        if (partitionReallocDirectMappedInPlace(root, page, newSize))
+            return ptr;
+    }
+
     size_t actualNewSize = partitionAllocActualSize(root, newSize);
     size_t actualOldSize = partitionAllocGetSize(ptr);
 
     // 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
     // determine it is a win.
     if (actualNewSize == actualOldSize) {
         // Trying to allocate a block of size newSize would give us a block of
         // the same size as the one we've already got, so no point in doing
         // anything here.
-        // TODO: for an upsize or downsize on a direct mapped allocation, we
-        // should really try and resize it in-place.
         return ptr;
     }
 
     // This realloc cannot be resized in-place. Sadness.
     void* ret = partitionAllocGeneric(root, newSize);
     size_t copySize = actualOldSize;
     if (newSize < copySize)
         copySize = newSize;
 
     memcpy(ret, ptr, copySize);
@@ skipping 53 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