Google Git
Sign in
chromium / chromium / src / d2a38acd7c8f91971cd83a4dae1343ddb7a21496 / . / third_party / WebKit / Source / wtf / allocator / PartitionAlloc.cpp
blob: 03978e8dbf71cb00773a73344bef6142a302f255 [file] [log] [blame]
/*
* 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