Index: third_party/WebKit/Source/wtf/allocator/PartitionAlloc.cpp |
diff --git a/third_party/WebKit/Source/wtf/allocator/PartitionAlloc.cpp b/third_party/WebKit/Source/wtf/allocator/PartitionAlloc.cpp |
deleted file mode 100644 |
index 03978e8dbf71cb00773a73344bef6142a302f255..0000000000000000000000000000000000000000 |
--- a/third_party/WebKit/Source/wtf/allocator/PartitionAlloc.cpp |
+++ /dev/null |
@@ -1,1492 +0,0 @@ |
-/* |
- * 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 |
- * copyright notice, this list of conditions and the following disclaimer |
- * in the documentation and/or other materials provided with the |
- * distribution. |
- * * Neither the name of Google Inc. nor the names of its |
- * contributors may be used to endorse or promote products derived from |
- * this software without specific prior written permission. |
- * |
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
- * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
- */ |
- |
-#include "wtf/allocator/PartitionAlloc.h" |
- |
-#include <string.h> |
- |
-#ifndef NDEBUG |
-#include <stdio.h> |
-#endif |
- |
-// Two partition pages are used as guard / metadata page so make sure the super |
-// page size is bigger. |
-static_assert(WTF::kPartitionPageSize * 4 <= WTF::kSuperPageSize, |
- "ok super page size"); |
-static_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. |
-static_assert(WTF::kSystemPageSize * 4 <= WTF::kPartitionPageSize, |
- "ok partition page size"); |
-static_assert(!(WTF::kPartitionPageSize % WTF::kSystemPageSize), |
- "ok partition page multiple"); |
-static_assert(sizeof(WTF::PartitionPage) <= WTF::kPageMetadataSize, |
- "PartitionPage should not be too big"); |
-static_assert(sizeof(WTF::PartitionBucket) <= WTF::kPageMetadataSize, |
- "PartitionBucket should not be too big"); |
-static_assert(sizeof(WTF::PartitionSuperPageExtentEntry) <= |
- WTF::kPageMetadataSize, |
- "PartitionSuperPageExtentEntry should not be too big"); |
-static_assert(WTF::kPageMetadataSize * WTF::kNumPartitionPagesPerSuperPage <= |
- WTF::kSystemPageSize, |
- "page metadata fits in hole"); |
-// Check that some of our zanier calculations worked out as expected. |
-static_assert(WTF::kGenericSmallestBucket == 8, "generic smallest bucket"); |
-static_assert(WTF::kGenericMaxBucketed == 983040, "generic max bucketed"); |
-static_assert(WTF::kMaxSystemPagesPerSlotSpan < (1 << 8), |
- "System pages per slot span must be less than 128."); |
- |
-namespace WTF { |
- |
-SpinLock PartitionRootBase::gInitializedLock; |
-bool PartitionRootBase::gInitialized = false; |
-PartitionPage PartitionRootBase::gSeedPage; |
-PartitionBucket PartitionRootBase::gPagedBucket; |
-void (*PartitionRootBase::gOomHandlingFunction)() = nullptr; |
-PartitionAllocHooks::AllocationHook* PartitionAllocHooks::m_allocationHook = |
- nullptr; |
-PartitionAllocHooks::FreeHook* PartitionAllocHooks::m_freeHook = nullptr; |
- |
-static uint8_t partitionBucketNumSystemPages(size_t size) { |
- // This works out reasonably for the current bucket sizes of the generic |
- // allocator, and the current values of partition page size and constants. |
- // Specifically, we have enough room to always pack the slots perfectly into |
- // some number of system pages. The only waste is the waste associated with |
- // unfaulted pages (i.e. wasted address space). |
- // TODO: we end up using a lot of system pages for very small sizes. For |
- // example, we'll use 12 system pages for slot size 24. The slot size is |
- // so small that the waste would be tiny with just 4, or 1, system pages. |
- // Later, we can investigate whether there are anti-fragmentation benefits |
- // to using fewer system pages. |
- double bestWasteRatio = 1.0f; |
- uint16_t bestPages = 0; |
- if (size > kMaxSystemPagesPerSlotSpan * kSystemPageSize) { |
- ASSERT(!(size % kSystemPageSize)); |
- bestPages = static_cast<uint16_t>(size / kSystemPageSize); |
- RELEASE_ASSERT(bestPages < (1 << 8)); |
- return static_cast<uint8_t>(bestPages); |
- } |
- ASSERT(size <= kMaxSystemPagesPerSlotSpan * kSystemPageSize); |
- for (uint16_t i = kNumSystemPagesPerPartitionPage - 1; |
- i <= kMaxSystemPagesPerSlotSpan; ++i) { |
- size_t pageSize = kSystemPageSize * i; |
- size_t numSlots = pageSize / size; |
- size_t waste = pageSize - (numSlots * size); |
- // Leaving a page unfaulted is not free; the page will occupy an empty page |
- // table entry. Make a simple attempt to account for that. |
- size_t numRemainderPages = i & (kNumSystemPagesPerPartitionPage - 1); |
- size_t numUnfaultedPages = |
- numRemainderPages |
- ? (kNumSystemPagesPerPartitionPage - numRemainderPages) |
- : 0; |
- waste += sizeof(void*) * numUnfaultedPages; |
- double wasteRatio = (double)waste / (double)pageSize; |
- if (wasteRatio < bestWasteRatio) { |
- bestWasteRatio = wasteRatio; |
- bestPages = i; |
- } |
- } |
- ASSERT(bestPages > 0); |
- RELEASE_ASSERT(bestPages <= kMaxSystemPagesPerSlotSpan); |
- return static_cast<uint8_t>(bestPages); |
-} |
- |
-static void partitionAllocBaseInit(PartitionRootBase* root) { |
- ASSERT(!root->initialized); |
- { |
- SpinLock::Guard guard(PartitionRootBase::gInitializedLock); |
- if (!PartitionRootBase::gInitialized) { |
- PartitionRootBase::gInitialized = true; |
- // We mark the seed page as free to make sure it is skipped by our |
- // logic to find a new active page. |
- PartitionRootBase::gPagedBucket.activePagesHead = |
- &PartitionRootGeneric::gSeedPage; |
- } |
- } |
- |
- root->initialized = true; |
- root->totalSizeOfCommittedPages = 0; |
- root->totalSizeOfSuperPages = 0; |
- root->totalSizeOfDirectMappedPages = 0; |
- root->nextSuperPage = 0; |
- root->nextPartitionPage = 0; |
- root->nextPartitionPageEnd = 0; |
- root->firstExtent = 0; |
- root->currentExtent = 0; |
- root->directMapList = 0; |
- |
- memset(&root->globalEmptyPageRing, '\0', sizeof(root->globalEmptyPageRing)); |
- root->globalEmptyPageRingIndex = 0; |
- |
- // This is a "magic" value so we can test if a root pointer is valid. |
- root->invertedSelf = ~reinterpret_cast<uintptr_t>(root); |
-} |
- |
-static void partitionBucketInitBase(PartitionBucket* bucket, |
- PartitionRootBase* root) { |
- bucket->activePagesHead = &PartitionRootGeneric::gSeedPage; |
- bucket->emptyPagesHead = 0; |
- bucket->decommittedPagesHead = 0; |
- bucket->numFullPages = 0; |
- bucket->numSystemPagesPerSlotSpan = |
- partitionBucketNumSystemPages(bucket->slotSize); |
-} |
- |
-void partitionAllocGlobalInit(void (*oomHandlingFunction)()) { |
- ASSERT(oomHandlingFunction); |
- PartitionRootBase::gOomHandlingFunction = oomHandlingFunction; |
-} |
- |
-void partitionAllocInit(PartitionRoot* root, |
- size_t numBuckets, |
- size_t maxAllocation) { |
- partitionAllocBaseInit(root); |
- |
- root->numBuckets = numBuckets; |
- root->maxAllocation = maxAllocation; |
- size_t i; |
- for (i = 0; i < root->numBuckets; ++i) { |
- PartitionBucket* bucket = &root->buckets()[i]; |
- if (!i) |
- bucket->slotSize = kAllocationGranularity; |
- else |
- bucket->slotSize = i << kBucketShift; |
- partitionBucketInitBase(bucket, root); |
- } |
-} |
- |
-void partitionAllocGenericInit(PartitionRootGeneric* root) { |
- SpinLock::Guard guard(root->lock); |
- |
- partitionAllocBaseInit(root); |
- |
- // Precalculate some shift and mask constants used in the hot path. |
- // Example: malloc(41) == 101001 binary. |
- // Order is 6 (1 << 6-1)==32 is highest bit set. |
- // orderIndex is the next three MSB == 010 == 2. |
- // subOrderIndexMask is a mask for the remaining bits == 11 (masking to 01 for |
- // the subOrderIndex). |
- size_t order; |
- for (order = 0; order <= kBitsPerSizet; ++order) { |
- size_t orderIndexShift; |
- if (order < kGenericNumBucketsPerOrderBits + 1) |
- orderIndexShift = 0; |
- else |
- orderIndexShift = order - (kGenericNumBucketsPerOrderBits + 1); |
- root->orderIndexShifts[order] = orderIndexShift; |
- size_t subOrderIndexMask; |
- if (order == kBitsPerSizet) { |
- // This avoids invoking undefined behavior for an excessive shift. |
- subOrderIndexMask = |
- static_cast<size_t>(-1) >> (kGenericNumBucketsPerOrderBits + 1); |
- } else { |
- subOrderIndexMask = ((static_cast<size_t>(1) << order) - 1) >> |
- (kGenericNumBucketsPerOrderBits + 1); |
- } |
- root->orderSubIndexMasks[order] = subOrderIndexMask; |
- } |
- |
- // Set up the actual usable buckets first. |
- // Note that typical values (i.e. min allocation size of 8) will result in |
- // pseudo buckets (size==9 etc. or more generally, size is not a multiple |
- // of the smallest allocation granularity). |
- // We avoid them in the bucket lookup map, but we tolerate them to keep the |
- // code simpler and the structures more generic. |
- size_t i, j; |
- size_t currentSize = kGenericSmallestBucket; |
- size_t currentIncrement = |
- kGenericSmallestBucket >> kGenericNumBucketsPerOrderBits; |
- PartitionBucket* bucket = &root->buckets[0]; |
- for (i = 0; i < kGenericNumBucketedOrders; ++i) { |
- for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { |
- bucket->slotSize = currentSize; |
- partitionBucketInitBase(bucket, root); |
- // Disable psuedo buckets so that touching them faults. |
- if (currentSize % kGenericSmallestBucket) |
- bucket->activePagesHead = 0; |
- currentSize += currentIncrement; |
- ++bucket; |
- } |
- currentIncrement <<= 1; |
- } |
- ASSERT(currentSize == 1 << kGenericMaxBucketedOrder); |
- ASSERT(bucket == &root->buckets[0] + kGenericNumBuckets); |
- |
- // Then set up the fast size -> bucket lookup table. |
- bucket = &root->buckets[0]; |
- PartitionBucket** bucketPtr = &root->bucketLookups[0]; |
- for (order = 0; order <= kBitsPerSizet; ++order) { |
- for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { |
- if (order < kGenericMinBucketedOrder) { |
- // Use the bucket of the finest granularity for malloc(0) etc. |
- *bucketPtr++ = &root->buckets[0]; |
- } else if (order > kGenericMaxBucketedOrder) { |
- *bucketPtr++ = &PartitionRootGeneric::gPagedBucket; |
- } else { |
- PartitionBucket* validBucket = bucket; |
- // Skip over invalid buckets. |
- while (validBucket->slotSize % kGenericSmallestBucket) |
- validBucket++; |
- *bucketPtr++ = validBucket; |
- bucket++; |
- } |
- } |
- } |
- ASSERT(bucket == &root->buckets[0] + kGenericNumBuckets); |
- ASSERT(bucketPtr == |
- &root->bucketLookups[0] + |
- ((kBitsPerSizet + 1) * kGenericNumBucketsPerOrder)); |
- // And there's one last bucket lookup that will be hit for e.g. malloc(-1), |
- // which tries to overflow to a non-existant order. |
- *bucketPtr = &PartitionRootGeneric::gPagedBucket; |
-} |
- |
-static bool partitionAllocShutdownBucket(PartitionBucket* bucket) { |
- // Failure here indicates a memory leak. |
- bool foundLeak = bucket->numFullPages; |
- for (PartitionPage* page = bucket->activePagesHead; page; |
- page = page->nextPage) |
- foundLeak |= (page->numAllocatedSlots > 0); |
- return foundLeak; |
-} |
- |
-static bool partitionAllocBaseShutdown(PartitionRootBase* root) { |
- ASSERT(root->initialized); |
- root->initialized = false; |
- |
- // Now that we've examined all partition pages in all buckets, it's safe |
- // to free all our super pages. Since the super page extent entries are |
- // stored in the super pages, we need to be careful not to access them |
- // after we've released the corresponding super page. |
- PartitionSuperPageExtentEntry* entry = root->firstExtent; |
- while (entry) { |
- PartitionSuperPageExtentEntry* nextEntry = entry->next; |
- char* superPage = entry->superPageBase; |
- char* superPagesEnd = entry->superPagesEnd; |
- while (superPage < superPagesEnd) { |
- freePages(superPage, kSuperPageSize); |
- superPage += kSuperPageSize; |
- } |
- entry = nextEntry; |
- } |
- return root->directMapList; |
-} |
- |
-bool partitionAllocShutdown(PartitionRoot* root) { |
- bool foundLeak = false; |
- size_t i; |
- for (i = 0; i < root->numBuckets; ++i) { |
- PartitionBucket* bucket = &root->buckets()[i]; |
- foundLeak |= partitionAllocShutdownBucket(bucket); |
- } |
- foundLeak |= partitionAllocBaseShutdown(root); |
- return !foundLeak; |
-} |
- |
-bool partitionAllocGenericShutdown(PartitionRootGeneric* root) { |
- SpinLock::Guard guard(root->lock); |
- bool foundLeak = false; |
- size_t i; |
- for (i = 0; i < kGenericNumBuckets; ++i) { |
- PartitionBucket* bucket = &root->buckets[i]; |
- foundLeak |= partitionAllocShutdownBucket(bucket); |
- } |
- foundLeak |= partitionAllocBaseShutdown(root); |
- return !foundLeak; |
-} |
- |
-#if !CPU(64BIT) |
-static NEVER_INLINE void partitionOutOfMemoryWithLotsOfUncommitedPages() { |
- OOM_CRASH(); |
-} |
-#endif |
- |
-static NEVER_INLINE void partitionOutOfMemory(const PartitionRootBase* root) { |
-#if !CPU(64BIT) |
- // Check whether this OOM is due to a lot of super pages that are allocated |
- // but not committed, probably due to http://crbug.com/421387. |
- if (root->totalSizeOfSuperPages + root->totalSizeOfDirectMappedPages - |
- root->totalSizeOfCommittedPages > |
- kReasonableSizeOfUnusedPages) { |
- partitionOutOfMemoryWithLotsOfUncommitedPages(); |
- } |
-#endif |
- if (PartitionRootBase::gOomHandlingFunction) |
- (*PartitionRootBase::gOomHandlingFunction)(); |
- OOM_CRASH(); |
-} |
- |
-static NEVER_INLINE void partitionExcessiveAllocationSize() { |
- OOM_CRASH(); |
-} |
- |
-static NEVER_INLINE void partitionBucketFull() { |
- OOM_CRASH(); |
-} |
- |
-// partitionPageStateIs* |
-// Note that it's only valid to call these functions on pages found on one of |
-// the page lists. Specifically, you can't call these functions on full pages |
-// that were detached from the active list. |
-static bool ALWAYS_INLINE |
-partitionPageStateIsActive(const PartitionPage* page) { |
- ASSERT(page != &PartitionRootGeneric::gSeedPage); |
- ASSERT(!page->pageOffset); |
- return (page->numAllocatedSlots > 0 && |
- (page->freelistHead || page->numUnprovisionedSlots)); |
-} |
- |
-static bool ALWAYS_INLINE partitionPageStateIsFull(const PartitionPage* page) { |
- ASSERT(page != &PartitionRootGeneric::gSeedPage); |
- ASSERT(!page->pageOffset); |
- bool ret = (page->numAllocatedSlots == partitionBucketSlots(page->bucket)); |
- if (ret) { |
- ASSERT(!page->freelistHead); |
- ASSERT(!page->numUnprovisionedSlots); |
- } |
- return ret; |
-} |
- |
-static bool ALWAYS_INLINE partitionPageStateIsEmpty(const PartitionPage* page) { |
- ASSERT(page != &PartitionRootGeneric::gSeedPage); |
- ASSERT(!page->pageOffset); |
- return (!page->numAllocatedSlots && page->freelistHead); |
-} |
- |
-static bool ALWAYS_INLINE |
-partitionPageStateIsDecommitted(const PartitionPage* page) { |
- ASSERT(page != &PartitionRootGeneric::gSeedPage); |
- ASSERT(!page->pageOffset); |
- bool ret = (!page->numAllocatedSlots && !page->freelistHead); |
- if (ret) { |
- ASSERT(!page->numUnprovisionedSlots); |
- ASSERT(page->emptyCacheIndex == -1); |
- } |
- return ret; |
-} |
- |
-static void partitionIncreaseCommittedPages(PartitionRootBase* root, |
- size_t len) { |
- root->totalSizeOfCommittedPages += len; |
- ASSERT(root->totalSizeOfCommittedPages <= |
- root->totalSizeOfSuperPages + root->totalSizeOfDirectMappedPages); |
-} |
- |
-static void partitionDecreaseCommittedPages(PartitionRootBase* root, |
- size_t len) { |
- root->totalSizeOfCommittedPages -= len; |
- ASSERT(root->totalSizeOfCommittedPages <= |
- root->totalSizeOfSuperPages + root->totalSizeOfDirectMappedPages); |
-} |
- |
-static ALWAYS_INLINE void partitionDecommitSystemPages(PartitionRootBase* root, |
- void* addr, |
- size_t len) { |
- decommitSystemPages(addr, len); |
- partitionDecreaseCommittedPages(root, len); |
-} |
- |
-static ALWAYS_INLINE void partitionRecommitSystemPages(PartitionRootBase* root, |
- void* addr, |
- size_t len) { |
- recommitSystemPages(addr, len); |
- partitionIncreaseCommittedPages(root, len); |
-} |
- |
-static ALWAYS_INLINE void* partitionAllocPartitionPages( |
- PartitionRootBase* root, |
- int flags, |
- uint16_t numPartitionPages) { |
- ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPage) % |
- kPartitionPageSize)); |
- ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPageEnd) % |
- kPartitionPageSize)); |
- ASSERT(numPartitionPages <= kNumPartitionPagesPerSuperPage); |
- size_t totalSize = kPartitionPageSize * numPartitionPages; |
- size_t numPartitionPagesLeft = |
- (root->nextPartitionPageEnd - root->nextPartitionPage) >> |
- kPartitionPageShift; |
- if (LIKELY(numPartitionPagesLeft >= numPartitionPages)) { |
- // In this case, we can still hand out pages from the current super page |
- // allocation. |
- char* ret = root->nextPartitionPage; |
- root->nextPartitionPage += totalSize; |
- partitionIncreaseCommittedPages(root, totalSize); |
- return ret; |
- } |
- |
- // Need a new super page. We want to allocate super pages in a continguous |
- // address region as much as possible. This is important for not causing |
- // page table bloat and not fragmenting address spaces in 32 bit |
- // architectures. |
- char* requestedAddress = root->nextSuperPage; |
- char* superPage = reinterpret_cast<char*>(allocPages( |
- requestedAddress, kSuperPageSize, kSuperPageSize, PageAccessible)); |
- if (UNLIKELY(!superPage)) |
- return 0; |
- |
- root->totalSizeOfSuperPages += kSuperPageSize; |
- partitionIncreaseCommittedPages(root, totalSize); |
- |
- root->nextSuperPage = superPage + kSuperPageSize; |
- char* ret = superPage + kPartitionPageSize; |
- root->nextPartitionPage = ret + totalSize; |
- root->nextPartitionPageEnd = root->nextSuperPage - kPartitionPageSize; |
- // Make the first partition page in the super page a guard page, but leave a |
- // hole in the middle. |
- // This is where we put page metadata and also a tiny amount of extent |
- // metadata. |
- setSystemPagesInaccessible(superPage, kSystemPageSize); |
- setSystemPagesInaccessible(superPage + (kSystemPageSize * 2), |
- kPartitionPageSize - (kSystemPageSize * 2)); |
- // Also make the last partition page a guard page. |
- setSystemPagesInaccessible(superPage + (kSuperPageSize - kPartitionPageSize), |
- kPartitionPageSize); |
- |
- // If we were after a specific address, but didn't get it, assume that |
- // the system chose a lousy address. Here most OS'es have a default |
- // algorithm that isn't randomized. For example, most Linux |
- // distributions will allocate the mapping directly before the last |
- // successful mapping, which is far from random. So we just get fresh |
- // randomness for the next mapping attempt. |
- if (requestedAddress && requestedAddress != superPage) |
- root->nextSuperPage = 0; |
- |
- // We allocated a new super page so update super page metadata. |
- // First check if this is a new extent or not. |
- PartitionSuperPageExtentEntry* latestExtent = |
- reinterpret_cast<PartitionSuperPageExtentEntry*>( |
- partitionSuperPageToMetadataArea(superPage)); |
- // By storing the root in every extent metadata object, we have a fast way |
- // to go from a pointer within the partition to the root object. |
- latestExtent->root = root; |
- // Most new extents will be part of a larger extent, and these three fields |
- // are unused, but we initialize them to 0 so that we get a clear signal |
- // in case they are accidentally used. |
- latestExtent->superPageBase = 0; |
- latestExtent->superPagesEnd = 0; |
- latestExtent->next = 0; |
- |
- PartitionSuperPageExtentEntry* currentExtent = root->currentExtent; |
- bool isNewExtent = (superPage != requestedAddress); |
- if (UNLIKELY(isNewExtent)) { |
- if (UNLIKELY(!currentExtent)) { |
- ASSERT(!root->firstExtent); |
- root->firstExtent = latestExtent; |
- } else { |
- ASSERT(currentExtent->superPageBase); |
- currentExtent->next = latestExtent; |
- } |
- root->currentExtent = latestExtent; |
- latestExtent->superPageBase = superPage; |
- latestExtent->superPagesEnd = superPage + kSuperPageSize; |
- } else { |
- // We allocated next to an existing extent so just nudge the size up a |
- // little. |
- ASSERT(currentExtent->superPagesEnd); |
- currentExtent->superPagesEnd += kSuperPageSize; |
- ASSERT(ret >= currentExtent->superPageBase && |
- ret < currentExtent->superPagesEnd); |
- } |
- return ret; |
-} |
- |
-static ALWAYS_INLINE uint16_t |
-partitionBucketPartitionPages(const PartitionBucket* bucket) { |
- return (bucket->numSystemPagesPerSlotSpan + |
- (kNumSystemPagesPerPartitionPage - 1)) / |
- kNumSystemPagesPerPartitionPage; |
-} |
- |
-static ALWAYS_INLINE void partitionPageReset(PartitionPage* page) { |
- ASSERT(partitionPageStateIsDecommitted(page)); |
- |
- page->numUnprovisionedSlots = partitionBucketSlots(page->bucket); |
- ASSERT(page->numUnprovisionedSlots); |
- |
- page->nextPage = nullptr; |
-} |
- |
-static ALWAYS_INLINE void partitionPageSetup(PartitionPage* page, |
- PartitionBucket* bucket) { |
- // The bucket never changes. We set it up once. |
- page->bucket = bucket; |
- page->emptyCacheIndex = -1; |
- |
- partitionPageReset(page); |
- |
- // If this page has just a single slot, do not set up page offsets for any |
- // page metadata other than the first one. This ensures that attempts to |
- // touch invalid page metadata fail. |
- if (page->numUnprovisionedSlots == 1) |
- return; |
- |
- uint16_t numPartitionPages = partitionBucketPartitionPages(bucket); |
- char* pageCharPtr = reinterpret_cast<char*>(page); |
- for (uint16_t i = 1; i < numPartitionPages; ++i) { |
- pageCharPtr += kPageMetadataSize; |
- PartitionPage* secondaryPage = |
- reinterpret_cast<PartitionPage*>(pageCharPtr); |
- secondaryPage->pageOffset = i; |
- } |
-} |
- |
-static ALWAYS_INLINE char* partitionPageAllocAndFillFreelist( |
- PartitionPage* page) { |
- ASSERT(page != &PartitionRootGeneric::gSeedPage); |
- uint16_t numSlots = page->numUnprovisionedSlots; |
- ASSERT(numSlots); |
- PartitionBucket* bucket = page->bucket; |
- // We should only get here when _every_ slot is either used or unprovisioned. |
- // (The third state is "on the freelist". If we have a non-empty freelist, we |
- // should not get here.) |
- ASSERT(numSlots + page->numAllocatedSlots == partitionBucketSlots(bucket)); |
- // Similarly, make explicitly sure that the freelist is empty. |
- ASSERT(!page->freelistHead); |
- ASSERT(page->numAllocatedSlots >= 0); |
- |
- size_t size = bucket->slotSize; |
- char* base = reinterpret_cast<char*>(partitionPageToPointer(page)); |
- char* returnObject = base + (size * page->numAllocatedSlots); |
- char* firstFreelistPointer = returnObject + size; |
- char* firstFreelistPointerExtent = |
- firstFreelistPointer + sizeof(PartitionFreelistEntry*); |
- // Our goal is to fault as few system pages as possible. We calculate the |
- // page containing the "end" of the returned slot, and then allow freelist |
- // pointers to be written up to the end of that page. |
- char* subPageLimit = reinterpret_cast<char*>( |
- WTF::roundUpToSystemPage(reinterpret_cast<size_t>(firstFreelistPointer))); |
- char* slotsLimit = returnObject + (size * numSlots); |
- char* freelistLimit = subPageLimit; |
- if (UNLIKELY(slotsLimit < freelistLimit)) |
- freelistLimit = slotsLimit; |
- |
- uint16_t numNewFreelistEntries = 0; |
- if (LIKELY(firstFreelistPointerExtent <= freelistLimit)) { |
- // Only consider used space in the slot span. If we consider wasted |
- // space, we may get an off-by-one when a freelist pointer fits in the |
- // wasted space, but a slot does not. |
- // We know we can fit at least one freelist pointer. |
- numNewFreelistEntries = 1; |
- // Any further entries require space for the whole slot span. |
- numNewFreelistEntries += static_cast<uint16_t>( |
- (freelistLimit - firstFreelistPointerExtent) / size); |
- } |
- |
- // We always return an object slot -- that's the +1 below. |
- // We do not neccessarily create any new freelist entries, because we cross |
- // sub page boundaries frequently for large bucket sizes. |
- ASSERT(numNewFreelistEntries + 1 <= numSlots); |
- numSlots -= (numNewFreelistEntries + 1); |
- page->numUnprovisionedSlots = numSlots; |
- page->numAllocatedSlots++; |
- |
- if (LIKELY(numNewFreelistEntries)) { |
- char* freelistPointer = firstFreelistPointer; |
- PartitionFreelistEntry* entry = |
- reinterpret_cast<PartitionFreelistEntry*>(freelistPointer); |
- page->freelistHead = entry; |
- while (--numNewFreelistEntries) { |
- freelistPointer += size; |
- PartitionFreelistEntry* nextEntry = |
- reinterpret_cast<PartitionFreelistEntry*>(freelistPointer); |
- entry->next = partitionFreelistMask(nextEntry); |
- entry = nextEntry; |
- } |
- entry->next = partitionFreelistMask(0); |
- } else { |
- page->freelistHead = 0; |
- } |
- return returnObject; |
-} |
- |
-// This helper function scans a bucket's active page list for a suitable new |
-// active page. |
-// When it finds a suitable new active page (one that has free slots and is not |
-// empty), it is set as the new active page. If there is no suitable new |
-// active page, the current active page is set to the seed page. |
-// As potential pages are scanned, they are tidied up according to their state. |
-// Empty pages are swept on to the empty page list, decommitted pages on to the |
-// decommitted page list and full pages are unlinked from any list. |
-static bool partitionSetNewActivePage(PartitionBucket* bucket) { |
- PartitionPage* page = bucket->activePagesHead; |
- if (page == &PartitionRootBase::gSeedPage) |
- return false; |
- |
- PartitionPage* nextPage; |
- |
- for (; page; page = nextPage) { |
- nextPage = page->nextPage; |
- ASSERT(page->bucket == bucket); |
- ASSERT(page != bucket->emptyPagesHead); |
- ASSERT(page != bucket->decommittedPagesHead); |
- |
- // Deal with empty and decommitted pages. |
- if (LIKELY(partitionPageStateIsActive(page))) { |
- // This page is usable because it has freelist entries, or has |
- // unprovisioned slots we can create freelist entries from. |
- bucket->activePagesHead = page; |
- return true; |
- } |
- if (LIKELY(partitionPageStateIsEmpty(page))) { |
- page->nextPage = bucket->emptyPagesHead; |
- bucket->emptyPagesHead = page; |
- } else if (LIKELY(partitionPageStateIsDecommitted(page))) { |
- page->nextPage = bucket->decommittedPagesHead; |
- bucket->decommittedPagesHead = page; |
- } else { |
- ASSERT(partitionPageStateIsFull(page)); |
- // If we get here, we found a full page. Skip over it too, and also |
- // tag it as full (via a negative value). We need it tagged so that |
- // free'ing can tell, and move it back into the active page list. |
- page->numAllocatedSlots = -page->numAllocatedSlots; |
- ++bucket->numFullPages; |
- // numFullPages is a uint16_t for efficient packing so guard against |
- // overflow to be safe. |
- if (UNLIKELY(!bucket->numFullPages)) |
- partitionBucketFull(); |
- // Not necessary but might help stop accidents. |
- page->nextPage = 0; |
- } |
- } |
- |
- bucket->activePagesHead = &PartitionRootGeneric::gSeedPage; |
- return false; |
-} |
- |
-static ALWAYS_INLINE PartitionDirectMapExtent* partitionPageToDirectMapExtent( |
- PartitionPage* page) { |
- ASSERT(partitionBucketIsDirectMapped(page->bucket)); |
- return reinterpret_cast<PartitionDirectMapExtent*>( |
- reinterpret_cast<char*>(page) + 3 * kPageMetadataSize); |
-} |
- |
-static ALWAYS_INLINE void partitionPageSetRawSize(PartitionPage* page, |
- size_t size) { |
- size_t* rawSizePtr = partitionPageGetRawSizePtr(page); |
- if (UNLIKELY(rawSizePtr != nullptr)) |
- *rawSizePtr = size; |
-} |
- |
-static ALWAYS_INLINE PartitionPage* partitionDirectMap(PartitionRootBase* root, |
- int flags, |
- size_t rawSize) { |
- size_t size = partitionDirectMapSize(rawSize); |
- |
- // 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 on 32-bit (on 64-bit we rely on the |
- // massive address space plus randomization instead). |
- size_t mapSize = size + kPartitionPageSize; |
-#if !CPU(64BIT) |
- mapSize += kSystemPageSize; |
-#endif |
- // Round up to the allocation granularity. |
- mapSize += kPageAllocationGranularityOffsetMask; |
- mapSize &= kPageAllocationGranularityBaseMask; |
- |
- // TODO: these pages will be zero-filled. Consider internalizing an |
- // allocZeroed() API so we can avoid a memset() entirely in this case. |
- char* ptr = reinterpret_cast<char*>( |
- allocPages(0, mapSize, kSuperPageSize, PageAccessible)); |
- if (UNLIKELY(!ptr)) |
- return nullptr; |
- |
- size_t committedPageSize = size + kSystemPageSize; |
- root->totalSizeOfDirectMappedPages += committedPageSize; |
- partitionIncreaseCommittedPages(root, committedPageSize); |
- |
- char* slot = ptr + kPartitionPageSize; |
- setSystemPagesInaccessible(ptr + (kSystemPageSize * 2), |
- kPartitionPageSize - (kSystemPageSize * 2)); |
-#if !CPU(64BIT) |
- setSystemPagesInaccessible(ptr, kSystemPageSize); |
- setSystemPagesInaccessible(slot + size, kSystemPageSize); |
-#endif |
- |
- PartitionSuperPageExtentEntry* extent = |
- reinterpret_cast<PartitionSuperPageExtentEntry*>( |
- partitionSuperPageToMetadataArea(ptr)); |
- extent->root = root; |
- // The new structures are all located inside a fresh system page so they |
- // will all be zeroed out. These ASSERTs are for documentation. |
- ASSERT(!extent->superPageBase); |
- ASSERT(!extent->superPagesEnd); |
- ASSERT(!extent->next); |
- PartitionPage* page = partitionPointerToPageNoAlignmentCheck(slot); |
- PartitionBucket* bucket = reinterpret_cast<PartitionBucket*>( |
- reinterpret_cast<char*>(page) + (kPageMetadataSize * 2)); |
- ASSERT(!page->nextPage); |
- ASSERT(!page->numAllocatedSlots); |
- ASSERT(!page->numUnprovisionedSlots); |
- ASSERT(!page->pageOffset); |
- ASSERT(!page->emptyCacheIndex); |
- page->bucket = bucket; |
- page->freelistHead = reinterpret_cast<PartitionFreelistEntry*>(slot); |
- PartitionFreelistEntry* nextEntry = |
- reinterpret_cast<PartitionFreelistEntry*>(slot); |
- nextEntry->next = partitionFreelistMask(0); |
- |
- ASSERT(!bucket->activePagesHead); |
- ASSERT(!bucket->emptyPagesHead); |
- ASSERT(!bucket->decommittedPagesHead); |
- ASSERT(!bucket->numSystemPagesPerSlotSpan); |
- ASSERT(!bucket->numFullPages); |
- bucket->slotSize = size; |
- |
- PartitionDirectMapExtent* mapExtent = partitionPageToDirectMapExtent(page); |
- mapExtent->mapSize = mapSize - kPartitionPageSize - kSystemPageSize; |
- mapExtent->bucket = bucket; |
- |
- // Maintain the doubly-linked list of all direct mappings. |
- mapExtent->nextExtent = root->directMapList; |
- if (mapExtent->nextExtent) |
- mapExtent->nextExtent->prevExtent = mapExtent; |
- mapExtent->prevExtent = nullptr; |
- root->directMapList = mapExtent; |
- |
- return page; |
-} |
- |
-static ALWAYS_INLINE void partitionDirectUnmap(PartitionPage* page) { |
- PartitionRootBase* root = partitionPageToRoot(page); |
- const PartitionDirectMapExtent* extent = partitionPageToDirectMapExtent(page); |
- size_t unmapSize = extent->mapSize; |
- |
- // Maintain the doubly-linked list of all direct mappings. |
- if (extent->prevExtent) { |
- ASSERT(extent->prevExtent->nextExtent == extent); |
- extent->prevExtent->nextExtent = extent->nextExtent; |
- } else { |
- root->directMapList = extent->nextExtent; |
- } |
- if (extent->nextExtent) { |
- ASSERT(extent->nextExtent->prevExtent == extent); |
- extent->nextExtent->prevExtent = extent->prevExtent; |
- } |
- |
- // Add on the size of the trailing guard page and preceeding partition |
- // page. |
- unmapSize += kPartitionPageSize + kSystemPageSize; |
- |
- size_t uncommittedPageSize = page->bucket->slotSize + kSystemPageSize; |
- partitionDecreaseCommittedPages(root, uncommittedPageSize); |
- ASSERT(root->totalSizeOfDirectMappedPages >= uncommittedPageSize); |
- root->totalSizeOfDirectMappedPages -= uncommittedPageSize; |
- |
- 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) { |
- // The slow path is called when the freelist is empty. |
- ASSERT(!bucket->activePagesHead->freelistHead); |
- |
- PartitionPage* newPage = nullptr; |
- |
- // For the partitionAllocGeneric API, we have a bunch of buckets marked |
- // as special cases. We bounce them through to the slow path so that we |
- // can still have a blazing fast hot path due to lack of corner-case |
- // branches. |
- bool returnNull = flags & PartitionAllocReturnNull; |
- if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) { |
- ASSERT(size > kGenericMaxBucketed); |
- ASSERT(bucket == &PartitionRootBase::gPagedBucket); |
- ASSERT(bucket->activePagesHead == &PartitionRootGeneric::gSeedPage); |
- if (size > kGenericMaxDirectMapped) { |
- if (returnNull) |
- return nullptr; |
- partitionExcessiveAllocationSize(); |
- } |
- newPage = partitionDirectMap(root, flags, size); |
- } else if (LIKELY(partitionSetNewActivePage(bucket))) { |
- // First, did we find an active page in the active pages list? |
- newPage = bucket->activePagesHead; |
- ASSERT(partitionPageStateIsActive(newPage)); |
- } else if (LIKELY(bucket->emptyPagesHead != nullptr) || |
- LIKELY(bucket->decommittedPagesHead != nullptr)) { |
- // Second, look in our lists of empty and decommitted pages. |
- // Check empty pages first, which are preferred, but beware that an |
- // empty page might have been decommitted. |
- while (LIKELY((newPage = bucket->emptyPagesHead) != nullptr)) { |
- ASSERT(newPage->bucket == bucket); |
- ASSERT(partitionPageStateIsEmpty(newPage) || |
- partitionPageStateIsDecommitted(newPage)); |
- bucket->emptyPagesHead = newPage->nextPage; |
- // Accept the empty page unless it got decommitted. |
- if (newPage->freelistHead) { |
- newPage->nextPage = nullptr; |
- break; |
- } |
- ASSERT(partitionPageStateIsDecommitted(newPage)); |
- newPage->nextPage = bucket->decommittedPagesHead; |
- bucket->decommittedPagesHead = newPage; |
- } |
- if (UNLIKELY(!newPage) && LIKELY(bucket->decommittedPagesHead != nullptr)) { |
- newPage = bucket->decommittedPagesHead; |
- ASSERT(newPage->bucket == bucket); |
- ASSERT(partitionPageStateIsDecommitted(newPage)); |
- bucket->decommittedPagesHead = newPage->nextPage; |
- void* addr = partitionPageToPointer(newPage); |
- partitionRecommitSystemPages(root, addr, |
- partitionBucketBytes(newPage->bucket)); |
- partitionPageReset(newPage); |
- } |
- ASSERT(newPage); |
- } else { |
- // Third. If we get here, we need a brand new page. |
- uint16_t numPartitionPages = partitionBucketPartitionPages(bucket); |
- void* rawPages = |
- partitionAllocPartitionPages(root, flags, numPartitionPages); |
- if (LIKELY(rawPages != nullptr)) { |
- newPage = partitionPointerToPageNoAlignmentCheck(rawPages); |
- partitionPageSetup(newPage, bucket); |
- } |
- } |
- |
- // Bail if we had a memory allocation failure. |
- if (UNLIKELY(!newPage)) { |
- ASSERT(bucket->activePagesHead == &PartitionRootGeneric::gSeedPage); |
- if (returnNull) |
- return nullptr; |
- partitionOutOfMemory(root); |
- } |
- |
- bucket = newPage->bucket; |
- ASSERT(bucket != &PartitionRootBase::gPagedBucket); |
- bucket->activePagesHead = newPage; |
- partitionPageSetRawSize(newPage, size); |
- |
- // If we found an active page with free slots, or an empty page, we have a |
- // usable freelist head. |
- if (LIKELY(newPage->freelistHead != nullptr)) { |
- PartitionFreelistEntry* entry = newPage->freelistHead; |
- PartitionFreelistEntry* newHead = partitionFreelistMask(entry->next); |
- newPage->freelistHead = newHead; |
- newPage->numAllocatedSlots++; |
- return entry; |
- } |
- // Otherwise, we need to build the freelist. |
- ASSERT(newPage->numUnprovisionedSlots); |
- return partitionPageAllocAndFillFreelist(newPage); |
-} |
- |
-static ALWAYS_INLINE void partitionDecommitPage(PartitionRootBase* root, |
- PartitionPage* page) { |
- ASSERT(partitionPageStateIsEmpty(page)); |
- ASSERT(!partitionBucketIsDirectMapped(page->bucket)); |
- void* addr = partitionPageToPointer(page); |
- partitionDecommitSystemPages(root, addr, partitionBucketBytes(page->bucket)); |
- |
- // We actually leave the decommitted page in the active list. We'll sweep |
- // it on to the decommitted page list when we next walk the active page |
- // list. |
- // Pulling this trick enables us to use a singly-linked page list for all |
- // cases, which is critical in keeping the page metadata structure down to |
- // 32 bytes in size. |
- page->freelistHead = 0; |
- page->numUnprovisionedSlots = 0; |
- ASSERT(partitionPageStateIsDecommitted(page)); |
-} |
- |
-static void partitionDecommitPageIfPossible(PartitionRootBase* root, |
- PartitionPage* page) { |
- ASSERT(page->emptyCacheIndex >= 0); |
- ASSERT(static_cast<unsigned>(page->emptyCacheIndex) < kMaxFreeableSpans); |
- ASSERT(page == root->globalEmptyPageRing[page->emptyCacheIndex]); |
- page->emptyCacheIndex = -1; |
- if (partitionPageStateIsEmpty(page)) |
- partitionDecommitPage(root, page); |
-} |
- |
-static ALWAYS_INLINE void partitionRegisterEmptyPage(PartitionPage* page) { |
- ASSERT(partitionPageStateIsEmpty(page)); |
- PartitionRootBase* root = partitionPageToRoot(page); |
- |
- // If the page is already registered as empty, give it another life. |
- if (page->emptyCacheIndex != -1) { |
- ASSERT(page->emptyCacheIndex >= 0); |
- ASSERT(static_cast<unsigned>(page->emptyCacheIndex) < kMaxFreeableSpans); |
- ASSERT(root->globalEmptyPageRing[page->emptyCacheIndex] == page); |
- root->globalEmptyPageRing[page->emptyCacheIndex] = 0; |
- } |
- |
- int16_t currentIndex = root->globalEmptyPageRingIndex; |
- PartitionPage* pageToDecommit = root->globalEmptyPageRing[currentIndex]; |
- // The page might well have been re-activated, filled up, etc. before we get |
- // around to looking at it here. |
- if (pageToDecommit) |
- partitionDecommitPageIfPossible(root, pageToDecommit); |
- |
- // We put the empty slot span on our global list of "pages that were once |
- // empty". thus providing it a bit of breathing room to get re-used before |
- // we really free it. This improves performance, particularly on Mac OS X |
- // which has subpar memory management performance. |
- root->globalEmptyPageRing[currentIndex] = page; |
- page->emptyCacheIndex = currentIndex; |
- ++currentIndex; |
- if (currentIndex == kMaxFreeableSpans) |
- currentIndex = 0; |
- root->globalEmptyPageRingIndex = currentIndex; |
-} |
- |
-static void partitionDecommitEmptyPages(PartitionRootBase* root) { |
- for (size_t i = 0; i < kMaxFreeableSpans; ++i) { |
- PartitionPage* page = root->globalEmptyPageRing[i]; |
- if (page) |
- partitionDecommitPageIfPossible(root, page); |
- root->globalEmptyPageRing[i] = nullptr; |
- } |
-} |
- |
-void partitionFreeSlowPath(PartitionPage* page) { |
- PartitionBucket* bucket = page->bucket; |
- ASSERT(page != &PartitionRootGeneric::gSeedPage); |
- if (LIKELY(page->numAllocatedSlots == 0)) { |
- // Page became fully unused. |
- if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) { |
- partitionDirectUnmap(page); |
- return; |
- } |
- // If it's the current active page, change it. We bounce the page to |
- // the empty list as a force towards defragmentation. |
- if (LIKELY(page == bucket->activePagesHead)) |
- (void)partitionSetNewActivePage(bucket); |
- ASSERT(bucket->activePagesHead != page); |
- |
- partitionPageSetRawSize(page, 0); |
- ASSERT(!partitionPageGetRawSize(page)); |
- |
- partitionRegisterEmptyPage(page); |
- } else { |
- ASSERT(!partitionBucketIsDirectMapped(bucket)); |
- // Ensure that the page is full. That's the only valid case if we |
- // arrive here. |
- ASSERT(page->numAllocatedSlots < 0); |
- // A transition of numAllocatedSlots from 0 to -1 is not legal, and |
- // likely indicates a double-free. |
- SECURITY_CHECK(page->numAllocatedSlots != -1); |
- page->numAllocatedSlots = -page->numAllocatedSlots - 2; |
- ASSERT(page->numAllocatedSlots == partitionBucketSlots(bucket) - 1); |
- // Fully used page became partially used. It must be put back on the |
- // non-full page list. Also make it the current page to increase the |
- // chances of it being filled up again. The old current page will be |
- // the next page. |
- ASSERT(!page->nextPage); |
- if (LIKELY(bucket->activePagesHead != &PartitionRootGeneric::gSeedPage)) |
- 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 rawSize) { |
- ASSERT(partitionBucketIsDirectMapped(page->bucket)); |
- |
- rawSize = partitionCookieSizeAdjustAdd(rawSize); |
- |
- // Note that the new size might be a bucketed size; this function is called |
- // whenever we're reallocating a direct mapped allocation. |
- size_t newSize = partitionDirectMapSize(rawSize); |
- if (newSize < kGenericMinDirectMappedDownsize) |
- return false; |
- |
- // 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) { |
- size_t mapSize = partitionPageToDirectMapExtent(page)->mapSize; |
- |
- // Don't reallocate in-place if new size is less than 80 % of the full |
- // map size, to avoid holding on to too much unused address space. |
- if ((newSize / kSystemPageSize) * 5 < (mapSize / kSystemPageSize) * 4) |
- return false; |
- |
- // Shrink by decommitting unneeded pages and making them inaccessible. |
- size_t decommitSize = currentSize - newSize; |
- partitionDecommitSystemPages(root, 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; |
- bool ret = setSystemPagesAccessible(charPtr + currentSize, recommitSize); |
- RELEASE_ASSERT(ret); |
- partitionRecommitSystemPages(root, charPtr + currentSize, recommitSize); |
- |
-#if ENABLE(ASSERT) |
- memset(charPtr + currentSize, kUninitializedByte, recommitSize); |
-#endif |
- } else { |
- // We can't perform the realloc in-place. |
- // TODO: support this too when possible. |
- return false; |
- } |
- |
-#if ENABLE(ASSERT) |
- // Write a new trailing cookie. |
- partitionCookieWriteValue(charPtr + rawSize - kCookieSize); |
-#endif |
- |
- partitionPageSetRawSize(page, rawSize); |
- ASSERT(partitionPageGetRawSize(page) == rawSize); |
- |
- page->bucket->slotSize = newSize; |
- return true; |
-} |
- |
-void* partitionReallocGeneric(PartitionRootGeneric* root, |
- void* ptr, |
- size_t newSize, |
- const char* typeName) { |
-#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
- return realloc(ptr, newSize); |
-#else |
- if (UNLIKELY(!ptr)) |
- return partitionAllocGeneric(root, newSize, typeName); |
- if (UNLIKELY(!newSize)) { |
- partitionFreeGeneric(root, ptr); |
- return 0; |
- } |
- |
- if (newSize > kGenericMaxDirectMapped) |
- partitionExcessiveAllocationSize(); |
- |
- ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(ptr))); |
- |
- PartitionPage* page = |
- partitionPointerToPage(partitionCookieFreePointerAdjust(ptr)); |
- |
- if (UNLIKELY(partitionBucketIsDirectMapped(page->bucket))) { |
- // 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)) { |
- PartitionAllocHooks::reallocHookIfEnabled(ptr, ptr, newSize, typeName); |
- 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. |
- return ptr; |
- } |
- |
- // This realloc cannot be resized in-place. Sadness. |
- void* ret = partitionAllocGeneric(root, newSize, typeName); |
- size_t copySize = actualOldSize; |
- if (newSize < copySize) |
- copySize = newSize; |
- |
- memcpy(ret, ptr, copySize); |
- partitionFreeGeneric(root, ptr); |
- return ret; |
-#endif |
-} |
- |
-static size_t partitionPurgePage(PartitionPage* page, bool discard) { |
- const PartitionBucket* bucket = page->bucket; |
- size_t slotSize = bucket->slotSize; |
- if (slotSize < kSystemPageSize || !page->numAllocatedSlots) |
- return 0; |
- |
- size_t bucketNumSlots = partitionBucketSlots(bucket); |
- size_t discardableBytes = 0; |
- |
- size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page)); |
- if (rawSize) { |
- uint32_t usedBytes = |
- static_cast<uint32_t>(WTF::roundUpToSystemPage(rawSize)); |
- discardableBytes = bucket->slotSize - usedBytes; |
- if (discardableBytes && discard) { |
- char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); |
- ptr += usedBytes; |
- discardSystemPages(ptr, discardableBytes); |
- } |
- return discardableBytes; |
- } |
- |
- const size_t maxSlotCount = |
- (kPartitionPageSize * kMaxPartitionPagesPerSlotSpan) / kSystemPageSize; |
- ASSERT(bucketNumSlots <= maxSlotCount); |
- ASSERT(page->numUnprovisionedSlots < bucketNumSlots); |
- size_t numSlots = bucketNumSlots - page->numUnprovisionedSlots; |
- char slotUsage[maxSlotCount]; |
- size_t lastSlot = static_cast<size_t>(-1); |
- memset(slotUsage, 1, numSlots); |
- char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); |
- PartitionFreelistEntry* entry = page->freelistHead; |
- // First, walk the freelist for this page and make a bitmap of which slots |
- // are not in use. |
- while (entry) { |
- size_t slotIndex = (reinterpret_cast<char*>(entry) - ptr) / slotSize; |
- ASSERT(slotIndex < numSlots); |
- slotUsage[slotIndex] = 0; |
- entry = partitionFreelistMask(entry->next); |
- // If we have a slot where the masked freelist entry is 0, we can |
- // actually discard that freelist entry because touching a discarded |
- // page is guaranteed to return original content or 0. |
- // (Note that this optimization won't fire on big endian machines |
- // because the masking function is negation.) |
- if (!partitionFreelistMask(entry)) |
- lastSlot = slotIndex; |
- } |
- |
- // If the slot(s) at the end of the slot span are not in used, we can |
- // truncate them entirely and rewrite the freelist. |
- size_t truncatedSlots = 0; |
- while (!slotUsage[numSlots - 1]) { |
- truncatedSlots++; |
- numSlots--; |
- ASSERT(numSlots); |
- } |
- // First, do the work of calculating the discardable bytes. Don't actually |
- // discard anything unless the discard flag was passed in. |
- char* beginPtr = nullptr; |
- char* endPtr = nullptr; |
- size_t unprovisionedBytes = 0; |
- if (truncatedSlots) { |
- beginPtr = ptr + (numSlots * slotSize); |
- endPtr = beginPtr + (slotSize * truncatedSlots); |
- beginPtr = reinterpret_cast<char*>( |
- WTF::roundUpToSystemPage(reinterpret_cast<size_t>(beginPtr))); |
- // We round the end pointer here up and not down because we're at the |
- // end of a slot span, so we "own" all the way up the page boundary. |
- endPtr = reinterpret_cast<char*>( |
- WTF::roundUpToSystemPage(reinterpret_cast<size_t>(endPtr))); |
- ASSERT(endPtr <= ptr + partitionBucketBytes(bucket)); |
- if (beginPtr < endPtr) { |
- unprovisionedBytes = endPtr - beginPtr; |
- discardableBytes += unprovisionedBytes; |
- } |
- } |
- if (unprovisionedBytes && discard) { |
- ASSERT(truncatedSlots > 0); |
- size_t numNewEntries = 0; |
- page->numUnprovisionedSlots += static_cast<uint16_t>(truncatedSlots); |
- // Rewrite the freelist. |
- PartitionFreelistEntry** entryPtr = &page->freelistHead; |
- for (size_t slotIndex = 0; slotIndex < numSlots; ++slotIndex) { |
- if (slotUsage[slotIndex]) |
- continue; |
- PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*>( |
- ptr + (slotSize * slotIndex)); |
- *entryPtr = partitionFreelistMask(entry); |
- entryPtr = reinterpret_cast<PartitionFreelistEntry**>(entry); |
- numNewEntries++; |
- } |
- // Terminate the freelist chain. |
- *entryPtr = nullptr; |
- // The freelist head is stored unmasked. |
- page->freelistHead = partitionFreelistMask(page->freelistHead); |
- ASSERT(numNewEntries == numSlots - page->numAllocatedSlots); |
- // Discard the memory. |
- discardSystemPages(beginPtr, unprovisionedBytes); |
- } |
- |
- // Next, walk the slots and for any not in use, consider where the system |
- // page boundaries occur. We can release any system pages back to the |
- // system as long as we don't interfere with a freelist pointer or an |
- // adjacent slot. |
- for (size_t i = 0; i < numSlots; ++i) { |
- if (slotUsage[i]) |
- continue; |
- // The first address we can safely discard is just after the freelist |
- // pointer. There's one quirk: if the freelist pointer is actually a |
- // null, we can discard that pointer value too. |
- char* beginPtr = ptr + (i * slotSize); |
- char* endPtr = beginPtr + slotSize; |
- if (i != lastSlot) |
- beginPtr += sizeof(PartitionFreelistEntry); |
- beginPtr = reinterpret_cast<char*>( |
- WTF::roundUpToSystemPage(reinterpret_cast<size_t>(beginPtr))); |
- endPtr = reinterpret_cast<char*>( |
- WTF::roundDownToSystemPage(reinterpret_cast<size_t>(endPtr))); |
- if (beginPtr < endPtr) { |
- size_t partialSlotBytes = endPtr - beginPtr; |
- discardableBytes += partialSlotBytes; |
- if (discard) |
- discardSystemPages(beginPtr, partialSlotBytes); |
- } |
- } |
- return discardableBytes; |
-} |
- |
-static void partitionPurgeBucket(PartitionBucket* bucket) { |
- if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) { |
- for (PartitionPage* page = bucket->activePagesHead; page; |
- page = page->nextPage) { |
- ASSERT(page != &PartitionRootGeneric::gSeedPage); |
- (void)partitionPurgePage(page, true); |
- } |
- } |
-} |
- |
-void partitionPurgeMemory(PartitionRoot* root, int flags) { |
- if (flags & PartitionPurgeDecommitEmptyPages) |
- partitionDecommitEmptyPages(root); |
- // We don't currently do anything for PartitionPurgeDiscardUnusedSystemPages |
- // here because that flag is only useful for allocations >= system page |
- // size. We only have allocations that large inside generic partitions |
- // at the moment. |
-} |
- |
-void partitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags) { |
- SpinLock::Guard guard(root->lock); |
- if (flags & PartitionPurgeDecommitEmptyPages) |
- partitionDecommitEmptyPages(root); |
- if (flags & PartitionPurgeDiscardUnusedSystemPages) { |
- for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
- PartitionBucket* bucket = &root->buckets[i]; |
- if (bucket->slotSize >= kSystemPageSize) |
- partitionPurgeBucket(bucket); |
- } |
- } |
-} |
- |
-static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, |
- const PartitionPage* page) { |
- uint16_t bucketNumSlots = partitionBucketSlots(page->bucket); |
- |
- if (partitionPageStateIsDecommitted(page)) { |
- ++statsOut->numDecommittedPages; |
- return; |
- } |
- |
- statsOut->discardableBytes += |
- partitionPurgePage(const_cast<PartitionPage*>(page), false); |
- |
- size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page)); |
- if (rawSize) |
- statsOut->activeBytes += static_cast<uint32_t>(rawSize); |
- else |
- statsOut->activeBytes += |
- (page->numAllocatedSlots * statsOut->bucketSlotSize); |
- |
- size_t pageBytesResident = |
- WTF::roundUpToSystemPage((bucketNumSlots - page->numUnprovisionedSlots) * |
- statsOut->bucketSlotSize); |
- statsOut->residentBytes += pageBytesResident; |
- if (partitionPageStateIsEmpty(page)) { |
- statsOut->decommittableBytes += pageBytesResident; |
- ++statsOut->numEmptyPages; |
- } else if (partitionPageStateIsFull(page)) { |
- ++statsOut->numFullPages; |
- } else { |
- ASSERT(partitionPageStateIsActive(page)); |
- ++statsOut->numActivePages; |
- } |
-} |
- |
-static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, |
- const PartitionBucket* bucket) { |
- ASSERT(!partitionBucketIsDirectMapped(bucket)); |
- statsOut->isValid = false; |
- // If the active page list is empty (== &PartitionRootGeneric::gSeedPage), |
- // the bucket might still need to be reported if it has a list of empty, |
- // decommitted or full pages. |
- if (bucket->activePagesHead == &PartitionRootGeneric::gSeedPage && |
- !bucket->emptyPagesHead && !bucket->decommittedPagesHead && |
- !bucket->numFullPages) |
- return; |
- |
- memset(statsOut, '\0', sizeof(*statsOut)); |
- statsOut->isValid = true; |
- statsOut->isDirectMap = false; |
- statsOut->numFullPages = static_cast<size_t>(bucket->numFullPages); |
- statsOut->bucketSlotSize = bucket->slotSize; |
- uint16_t bucketNumSlots = partitionBucketSlots(bucket); |
- size_t bucketUsefulStorage = statsOut->bucketSlotSize * bucketNumSlots; |
- statsOut->allocatedPageSize = partitionBucketBytes(bucket); |
- statsOut->activeBytes = bucket->numFullPages * bucketUsefulStorage; |
- statsOut->residentBytes = bucket->numFullPages * statsOut->allocatedPageSize; |
- |
- for (const PartitionPage* page = bucket->emptyPagesHead; page; |
- page = page->nextPage) { |
- ASSERT(partitionPageStateIsEmpty(page) || |
- partitionPageStateIsDecommitted(page)); |
- partitionDumpPageStats(statsOut, page); |
- } |
- for (const PartitionPage* page = bucket->decommittedPagesHead; page; |
- page = page->nextPage) { |
- ASSERT(partitionPageStateIsDecommitted(page)); |
- partitionDumpPageStats(statsOut, page); |
- } |
- |
- if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) { |
- for (const PartitionPage* page = bucket->activePagesHead; page; |
- page = page->nextPage) { |
- ASSERT(page != &PartitionRootGeneric::gSeedPage); |
- partitionDumpPageStats(statsOut, page); |
- } |
- } |
-} |
- |
-void partitionDumpStatsGeneric(PartitionRootGeneric* partition, |
- const char* partitionName, |
- bool isLightDump, |
- PartitionStatsDumper* partitionStatsDumper) { |
- PartitionBucketMemoryStats bucketStats[kGenericNumBuckets]; |
- static const size_t kMaxReportableDirectMaps = 4096; |
- uint32_t directMapLengths[kMaxReportableDirectMaps]; |
- size_t numDirectMappedAllocations = 0; |
- |
- { |
- SpinLock::Guard guard(partition->lock); |
- |
- for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
- const PartitionBucket* bucket = &partition->buckets[i]; |
- // Don't report the pseudo buckets that the generic allocator sets up in |
- // order to preserve a fast size->bucket map (see |
- // partitionAllocGenericInit for details). |
- if (!bucket->activePagesHead) |
- bucketStats[i].isValid = false; |
- else |
- partitionDumpBucketStats(&bucketStats[i], bucket); |
- } |
- |
- for (PartitionDirectMapExtent* extent = partition->directMapList; extent; |
- extent = extent->nextExtent) { |
- ASSERT(!extent->nextExtent || extent->nextExtent->prevExtent == extent); |
- directMapLengths[numDirectMappedAllocations] = extent->bucket->slotSize; |
- ++numDirectMappedAllocations; |
- if (numDirectMappedAllocations == kMaxReportableDirectMaps) |
- break; |
- } |
- } |
- |
- // partitionsDumpBucketStats is called after collecting stats because it |
- // can try to allocate using PartitionAllocGeneric and it can't obtain the |
- // lock. |
- PartitionMemoryStats partitionStats = {0}; |
- partitionStats.totalMmappedBytes = partition->totalSizeOfSuperPages + |
- partition->totalSizeOfDirectMappedPages; |
- partitionStats.totalCommittedBytes = partition->totalSizeOfCommittedPages; |
- for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
- if (bucketStats[i].isValid) { |
- partitionStats.totalResidentBytes += bucketStats[i].residentBytes; |
- partitionStats.totalActiveBytes += bucketStats[i].activeBytes; |
- partitionStats.totalDecommittableBytes += |
- bucketStats[i].decommittableBytes; |
- partitionStats.totalDiscardableBytes += bucketStats[i].discardableBytes; |
- if (!isLightDump) |
- partitionStatsDumper->partitionsDumpBucketStats(partitionName, |
- &bucketStats[i]); |
- } |
- } |
- |
- size_t directMappedAllocationsTotalSize = 0; |
- for (size_t i = 0; i < numDirectMappedAllocations; ++i) { |
- uint32_t size = directMapLengths[i]; |
- directMappedAllocationsTotalSize += size; |
- if (isLightDump) |
- continue; |
- |
- PartitionBucketMemoryStats stats; |
- memset(&stats, '\0', sizeof(stats)); |
- stats.isValid = true; |
- stats.isDirectMap = true; |
- stats.numFullPages = 1; |
- stats.allocatedPageSize = size; |
- stats.bucketSlotSize = size; |
- stats.activeBytes = size; |
- stats.residentBytes = size; |
- partitionStatsDumper->partitionsDumpBucketStats(partitionName, &stats); |
- } |
- partitionStats.totalResidentBytes += directMappedAllocationsTotalSize; |
- partitionStats.totalActiveBytes += directMappedAllocationsTotalSize; |
- partitionStatsDumper->partitionDumpTotals(partitionName, &partitionStats); |
-} |
- |
-void partitionDumpStats(PartitionRoot* partition, |
- const char* partitionName, |
- bool isLightDump, |
- PartitionStatsDumper* partitionStatsDumper) { |
- static const size_t kMaxReportableBuckets = 4096 / sizeof(void*); |
- PartitionBucketMemoryStats memoryStats[kMaxReportableBuckets]; |
- const size_t partitionNumBuckets = partition->numBuckets; |
- ASSERT(partitionNumBuckets <= kMaxReportableBuckets); |
- |
- for (size_t i = 0; i < partitionNumBuckets; ++i) |
- partitionDumpBucketStats(&memoryStats[i], &partition->buckets()[i]); |
- |
- // partitionsDumpBucketStats is called after collecting stats because it |
- // can use PartitionAlloc to allocate and this can affect the statistics. |
- PartitionMemoryStats partitionStats = {0}; |
- partitionStats.totalMmappedBytes = partition->totalSizeOfSuperPages; |
- partitionStats.totalCommittedBytes = partition->totalSizeOfCommittedPages; |
- ASSERT(!partition->totalSizeOfDirectMappedPages); |
- for (size_t i = 0; i < partitionNumBuckets; ++i) { |
- if (memoryStats[i].isValid) { |
- partitionStats.totalResidentBytes += memoryStats[i].residentBytes; |
- partitionStats.totalActiveBytes += memoryStats[i].activeBytes; |
- partitionStats.totalDecommittableBytes += |
- memoryStats[i].decommittableBytes; |
- partitionStats.totalDiscardableBytes += memoryStats[i].discardableBytes; |
- if (!isLightDump) |
- partitionStatsDumper->partitionsDumpBucketStats(partitionName, |
- &memoryStats[i]); |
- } |
- } |
- partitionStatsDumper->partitionDumpTotals(partitionName, &partitionStats); |
-} |
- |
-} // namespace WTF |