PartitionAlloc: support in-place resize of directly mapped allocation

Source/wtf/PartitionAlloc.cpp

Index: Source/wtf/PartitionAlloc.cpp
diff --git a/Source/wtf/PartitionAlloc.cpp b/Source/wtf/PartitionAlloc.cpp
index e62a9a66235e23719cd2c5eb30ae29ed76cfdc52..01c8144e7e483a4a472d7095897a8d3dc8342ee4 100644
--- a/Source/wtf/PartitionAlloc.cpp
+++ b/Source/wtf/PartitionAlloc.cpp
@@ -524,6 +524,29 @@ static ALWAYS_INLINE bool partitionSetNewActivePage(PartitionPage* page)
     return false;
 }
 
+static ALWAYS_INLINE size_t partitionDirectMapAvailableSize(PartitionPage* page)

[Chris Evans, 2014/03/05 07:57:04]

This function seems a bit complicated, or at least large. Ideally we can do
without it and fetch the size directly as a struct member, possibly as I
describe below in a comment inside partitionDirectMap.

+{
+    // Return the size of the mapping, *not* including space where meta-data is
+    // stored, and *not* including one trailing inaccessible system page; IOW
+    // the size of the area available for the actual allocation. Some of the
+    // pages at the end of this memory range may have been decommitted and made
+    // inaccessible by a partitionReallocGeneric() call.
+    //
+    // The value of bucket->slotSize is size of the current allocation.
+
+    PartitionBucket* bucket = page->bucket;
+
+    ASSERT(partitionBucketIsDirectMapped(bucket));
+    ASSERT(bucket != &PartitionRootBase::gPagedBucket);
+
+    char* ptr = static_cast<char*>(partitionPageToPointer(page));
+    char* endPtr = reinterpret_cast<char*>(bucket->freePagesHead) - kSystemPageSize;
+
+    size_t size = endPtr - ptr;
+    ASSERT(bucket->slotSize <= size);
+    return size;
+}
+
 static ALWAYS_INLINE void* partitionDirectMap(PartitionRootBase* root, int flags, size_t size)
 {
     size = partitionDirectMapSize(size);
@@ -576,22 +599,25 @@ static ALWAYS_INLINE void* partitionDirectMap(PartitionRootBase* root, int flags
     page->freeCacheIndex = 0;
 
     bucket->activePagesHead = 0;
-    bucket->freePagesHead = 0;
+    bucket->freePagesHead = reinterpret_cast<PartitionPage*>(ptr + mapSize);

[Chris Evans, 2014/03/05 07:57:04]

I'm not a huge fan of this.

For each direct mapping, we have a whole system page in which to put metadata
about the mapping, and it's not very full yet :-)

It looks like we need a new piece of metadata to describe the available
contiguous mapping size, which is different from the bucket->slotsize.

So how about some "struct PartitionDirectMapExtent"? Initially it can just store
the mapping size (not include guard pages etc.) and we'd set it to the same as
bucket->slotSize to start with.

We can store it at
reinterpret_cast<PartitionBucket*>(reinterpret_cast<char*>(page) +
kPageMetadataSize * 2)

When pulling this trick, we might also want to add a new COMPILER_ASSERT that
the size of PartitionBucket is also <= kPageMetadataSize

[Jens Widell, 2014/03/05 08:11:43]

I certainly wasn't either. :-)
Yeah, I'll do that instead.

     bucket->slotSize = size;
     bucket->numSystemPagesPerSlotSpan = 0;
     bucket->numFullPages = 0;
 
+    ASSERT(size <= partitionDirectMapAvailableSize(page));
+
     return ret;
 }
 
 static ALWAYS_INLINE void partitionDirectUnmap(PartitionPage* page)
 {
-    size_t unmapSize = page->bucket->slotSize;
+    size_t unmapSize = partitionDirectMapAvailableSize(page);
+
     // 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
@@ -763,6 +789,51 @@ void partitionFreeSlowPath(PartitionPage* page)
     }
 }
 
+bool partitionReallocDirectMappedInPlace(PartitionRootGeneric* root, void* ptr, size_t newSize)
+{
+    newSize = partitionCookieSizeAdjustAdd(newSize);
+    ASSERT(partitionDirectMapSize(newSize) == newSize);

[Chris Evans, 2014/03/05 07:57:04]

I think we also need newSize to be a multiple of kSystemPageSize here; might as
well ASSERT it?

[Jens Widell, 2014/03/05 08:11:43]

The value returned by partitionDirectMapSize(size) is effectively simply 'size'
rounded up to a system page size. A more explicit assert could serve as better
code documentation, though.

+
+    char* realPtr = static_cast<char*>(partitionCookieFreePointerAdjust(ptr));
+    PartitionPage* page = partitionPointerToPage(realPtr);
+    PartitionBucket* bucket = page->bucket;
+
+    // bucket->slotSize is the current size of the allocation.
+    // bucket->freePagesHead points to the first system page beyond what we
+    // first allocated; we can grow the allocation up to that point.
+
+    ASSERT(partitionBucketIsDirectMapped(bucket));
+    ASSERT(newSize != bucket->slotSize);
+
+    if (newSize < bucket->slotSize) {
+        // Shrink by decommitting unneeded pages and making them inaccessible.
+        // TODO: maybe refuse if the new size is too much smaller?
+        size_t decommitSize = bucket->slotSize - newSize;
+        decommitSystemPages(realPtr + newSize, decommitSize);
+        setSystemPagesInaccessible(realPtr + newSize, decommitSize);
+    } else if (newSize <= partitionDirectMapAvailableSize(page)) {
+        // Grow within the actually allocated memory. Just need to make the
+        // pages accessible again.
+        size_t recommitSize = newSize - bucket->slotSize;
+        setSystemPagesAccessible(realPtr + bucket->slotSize, recommitSize);
+
+#ifndef NDEBUG
+        memset(realPtr + bucket->slotSize, kUninitializedByte, recommitSize);
+#endif
+    } else {
+        // We can't perform the realloc in-place.

[Chris Evans, 2014/03/05 07:57:04]

I think we can fill in this branch in the future (probably not this CL, it's
complicated). Unfortunately, I think this is the branch which is most important,
particularly if we ever wired Vector and HashTable to realloc().

It's complicated mainly because of the Windows API for mapping pages :-(

+        return false;
+    }
+
+#ifndef NDEBUG
+    // Write a new trailing cookie.
+    partitionCookieWriteValue(realPtr + newSize - kCookieSize);
+#endif
+
+    bucket->slotSize = newSize;
+    return true;
+}
+
 void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newSize)
 {
 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
@@ -787,11 +858,17 @@ void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newS
         // 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;
     }
 
+    if (partitionSizeIsDirectMapped(actualOldSize) && partitionSizeIsDirectMapped(actualNewSize)) {

[Chris Evans, 2014/03/05 07:57:04]

I actually think we might want to relax the second condition. For example, using
current tuning values, let's say we:
- Alloc 1MB (this will be direct mapped)
- realloc to 500KB (will get pushed into a super page allocation)

I don't think that's what we'd want in this case as it results in a copy. A
sensible threshold is probably something like 128KB. (The worry of making the
threshold too low is that the 4KB metadata page becomes too large as a
percentage of waste.)

[Jens Widell, 2014/03/05 08:11:43]

The reason I didn't do that was to avoid having an allocation that is too small
to be a direct map but still is one, which could confuse some condition
somewhere else. But we should of course use partitionBucketIsDirectMapped() and
not the size of the allocation to determine that anyway, so it's probably not a
problem in practice.

I'll change it.

+        // 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, ptr, actualNewSize))
+            return ptr;
+    }
+
     // This realloc cannot be resized in-place. Sadness.
     void* ret = partitionAllocGeneric(root, newSize);
     size_t copySize = actualOldSize;