| /* |
| * 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 |