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 506 matching lines @@
             RELEASE_ASSERT(bucket->numFullPages);
             // Not necessary but might help stop accidents.
             page->nextPage = 0;
         }
     }
 
     bucket->activePagesHead = 0;
     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);
 
     // 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 32 matching lines @@
     PartitionBucket* bucket = reinterpret_cast<PartitionBucket*>(reinterpret_cast<char*>(page) + kPageMetadataSize);
     page->freelistHead = 0;
     page->nextPage = 0;
     page->bucket = bucket;
     page->numAllocatedSlots = 1;
     page->numUnprovisionedSlots = 0;
     page->pageOffset = 0;
     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
     // 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);
+    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)
     return realloc(ptr, newSize);
 #else
     if (UNLIKELY(!ptr))
         return partitionAllocGeneric(root, newSize);
     if (UNLIKELY(!newSize)) {
         partitionFreeGeneric(root, ptr);
         return 0;
     }

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

Can we just put a no nonsense RELEASE_ASSERT here?
e.g. RELEASE_ASSERT(newSize <= INT_MAX - kSystemPageSize)
Should prevent all future possible accidents in this area :)

 
     ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(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;
     }
 
+    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;
     if (newSize < copySize)
         copySize = newSize;
 
     memcpy(ret, ptr, copySize);
     partitionFreeGeneric(root, ptr);
     return ret;
 #endif
@@ skipping 50 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