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);
 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, void* ptr, 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 < kGenericMinDirectMapped)
+        return false;
+
+    PartitionPage* page = partitionPointerToPage(ptr);

[Chris Evans, 2014/03/06 05:55:13]

Pass in page instead of ptr to this function to avoid this small piece of work.

+    PartitionBucket* bucket = page->bucket;
+
+    ASSERT(partitionBucketIsDirectMapped(bucket));
+
+    // bucket->slotSize is the current size of the allocation.
+    if (newSize == bucket->slotSize)

[Chris Evans, 2014/03/06 05:55:13]

This check looks duplicated with a check in the parent function. Can we remove
this check by re-ordering the parent function slightly? We could even ASSERT
that this is then _not_ equal.

[Jens Widell, 2014/03/06 06:03:04]

If you mean the actualOldSize/actualNewSize comparison in the parent function, I
actually reordered and introduced this check in the latest version of the patch.
The values in the comparison in the parent function are rounded to bucket sizes
(when below gGenericMaxBucketed) which doesn't really make sense if we're
downsizing a direct mapping.

+        return true;
+
+    char* charPtr = static_cast<char*>(ptr);
+
+    if (newSize < bucket->slotSize) {
+        // Shrink by decommitting unneeded pages and making them inaccessible.
+        size_t decommitSize = bucket->slotSize - 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 - bucket->slotSize;
+        setSystemPagesAccessible(charPtr + bucket->slotSize, recommitSize);
+
+#ifndef NDEBUG
+        memset(charPtr + bucket->slotSize, 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
+
+    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 <= INT_MAX - kSystemPageSize);

[Chris Evans, 2014/03/06 05:55:13]

The RHS is just kGenericMaxDirectMapped, I think.

+
     ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(ptr)));
 
+    void* realPtr = partitionCookieFreePointerAdjust(ptr);
+    PartitionPage* page = partitionPointerToPage(realPtr);
+
+    if (partitionBucketIsDirectMapped(page->bucket)) {

[Chris Evans, 2014/03/06 05:55:13]

Might as well wrap that condition in an UNLIKELY ?

+        // 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, realPtr, newSize))

[Chris Evans, 2014/03/06 05:55:13]

Pass in the page and not the pointer to do a little less work.

+            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