15267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)/* 25267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * Copyright (C) 2013 Google Inc. All rights reserved. 35267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * 45267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * modification, are permitted provided that the following conditions are 65267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * met: 75267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * 85267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * * Redistributions of source code must retain the above copyright 95267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * * Redistributions in binary form must reproduce the above 115267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer 125267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * in the documentation and/or other materials provided with the 135267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * distribution. 145267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * * Neither the name of Google Inc. nor the names of its 155267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * contributors may be used to endorse or promote products derived from 165267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * this software without specific prior written permission. 175267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * 185267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) */ 305267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 315267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#include "config.h" 325267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#include "wtf/PartitionAlloc.h" 335267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 341e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include <string.h> 355267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 365267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#ifndef NDEBUG 375267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#include <stdio.h> 385267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#endif 395267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 40a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// Two partition pages are used as guard / metadata page so make sure the super 41a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// page size is bigger. 42a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)COMPILE_ASSERT(WTF::kPartitionPageSize * 4 <= WTF::kSuperPageSize, ok_super_page_size); 43a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)COMPILE_ASSERT(!(WTF::kSuperPageSize % WTF::kPartitionPageSize), ok_super_page_multiple); 44a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// Four system pages gives us room to hack out a still-guard-paged piece 45a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// of metadata in the middle of a guard partition page. 46a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)COMPILE_ASSERT(WTF::kSystemPageSize * 4 <= WTF::kPartitionPageSize, ok_partition_page_size); 47a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)COMPILE_ASSERT(!(WTF::kPartitionPageSize % WTF::kSystemPageSize), ok_partition_page_multiple); 48a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)COMPILE_ASSERT(sizeof(WTF::PartitionPage) <= WTF::kPageMetadataSize, PartitionPage_not_too_big); 49d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)COMPILE_ASSERT(sizeof(WTF::PartitionBucket) <= WTF::kPageMetadataSize, PartitionBucket_not_too_big); 50a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)COMPILE_ASSERT(sizeof(WTF::PartitionSuperPageExtentEntry) <= WTF::kPageMetadataSize, PartitionSuperPageExtentEntry_not_too_big); 51a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)COMPILE_ASSERT(WTF::kPageMetadataSize * WTF::kNumPartitionPagesPerSuperPage <= WTF::kSystemPageSize, page_metadata_fits_in_hole); 5209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Check that some of our zanier calculations worked out as expected. 5309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)COMPILE_ASSERT(WTF::kGenericSmallestBucket == 8, generic_smallest_bucket); 5409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)COMPILE_ASSERT(WTF::kGenericMaxBucketed == 983040, generic_max_bucketed); 55521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) 565267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)namespace WTF { 575267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 5809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)int PartitionRootBase::gInitializedLock = 0; 5909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)bool PartitionRootBase::gInitialized = false; 6009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)PartitionPage PartitionRootBase::gSeedPage; 6109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)PartitionBucket PartitionRootBase::gPagedBucket; 6209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 6309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static size_t partitionBucketNumSystemPages(size_t size) 64f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles){ 6509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // This works out reasonably for the current bucket sizes of the generic 6609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // allocator, and the current values of partition page size and constants. 6709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Specifically, we have enough room to always pack the slots perfectly into 6809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // some number of system pages. The only waste is the waste associated with 6909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // unfaulted pages (i.e. wasted address space). 7009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // TODO: we end up using a lot of system pages for very small sizes. For 7109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // example, we'll use 12 system pages for slot size 24. The slot size is 7209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // so small that the waste would be tiny with just 4, or 1, system pages. 7309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Later, we can investigate whether there are anti-fragmentation benefits 7409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // to using fewer system pages. 75f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) double bestWasteRatio = 1.0f; 76f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) size_t bestPages = 0; 7709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (size > kMaxSystemPagesPerSlotSpan * kSystemPageSize) { 7809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!(size % kSystemPageSize)); 7909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return size / kSystemPageSize; 8009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 8109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(size <= kMaxSystemPagesPerSlotSpan * kSystemPageSize); 8209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (size_t i = kNumSystemPagesPerPartitionPage - 1; i <= kMaxSystemPagesPerSlotSpan; ++i) { 83a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) size_t pageSize = kSystemPageSize * i; 84a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) size_t numSlots = pageSize / size; 85f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) size_t waste = pageSize - (numSlots * size); 8609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Leaving a page unfaulted is not free; the page will occupy an empty page table entry. 87f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) // Make a simple attempt to account for that. 8809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t numRemainderPages = i & (kNumSystemPagesPerPartitionPage - 1); 8909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t numUnfaultedPages = numRemainderPages ? (kNumSystemPagesPerPartitionPage - numRemainderPages) : 0; 9009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) waste += sizeof(void*) * numUnfaultedPages; 91f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) double wasteRatio = (double) waste / (double) pageSize; 92f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) if (wasteRatio < bestWasteRatio) { 93f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) bestWasteRatio = wasteRatio; 94f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) bestPages = i; 95f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) } 96f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) } 97f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) ASSERT(bestPages > 0); 9809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return bestPages; 99f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)} 100f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) 10109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static void parititonAllocBaseInit(PartitionRootBase* root) 1025267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 103521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) ASSERT(!root->initialized); 10409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 10509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) spinLockLock(&PartitionRootBase::gInitializedLock); 10609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!PartitionRootBase::gInitialized) { 10709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionRootBase::gInitialized = true; 10809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // We mark the seed page as free to make sure it is skipped by our 10909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // logic to find a new active page. 11009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionRootBase::gPagedBucket.activePagesHead = &PartitionRootGeneric::gSeedPage; 11109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 11209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) spinLockUnlock(&PartitionRootBase::gInitializedLock); 11309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 114521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) root->initialized = true; 1155d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) root->totalSizeOfCommittedPages = 0; 1161e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) root->totalSizeOfSuperPages = 0; 11709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->nextSuperPage = 0; 11809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->nextPartitionPage = 0; 11909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->nextPartitionPageEnd = 0; 12009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->firstExtent = 0; 12109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->currentExtent = 0; 12209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 12309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) memset(&root->globalEmptyPageRing, '\0', sizeof(root->globalEmptyPageRing)); 12409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->globalEmptyPageRingIndex = 0; 12509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 12609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // This is a "magic" value so we can test if a root pointer is valid. 12709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->invertedSelf = ~reinterpret_cast<uintptr_t>(root); 12809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 12909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 13009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static void partitionBucketInitBase(PartitionBucket* bucket, PartitionRootBase* root) 13109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 13209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->activePagesHead = &PartitionRootGeneric::gSeedPage; 13309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->freePagesHead = 0; 13409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->numFullPages = 0; 13509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->numSystemPagesPerSlotSpan = partitionBucketNumSystemPages(bucket->slotSize); 13609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 13709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 13809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void partitionAllocInit(PartitionRoot* root, size_t numBuckets, size_t maxAllocation) 13909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 14009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) parititonAllocBaseInit(root); 14109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 1428abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) root->numBuckets = numBuckets; 1438abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) root->maxAllocation = maxAllocation; 1445267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) size_t i; 1458abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) for (i = 0; i < root->numBuckets; ++i) { 1468abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) PartitionBucket* bucket = &root->buckets()[i]; 14709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!i) 14809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->slotSize = kAllocationGranularity; 14909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) else 15009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->slotSize = i << kBucketShift; 15109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionBucketInitBase(bucket, root); 1525267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 15309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 154521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) 15509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void partitionAllocGenericInit(PartitionRootGeneric* root) 15609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 15709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) parititonAllocBaseInit(root); 15809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 15909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->lock = 0; 16009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 16109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Precalculate some shift and mask constants used in the hot path. 16209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Example: malloc(41) == 101001 binary. 16309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Order is 6 (1 << 6-1)==32 is highest bit set. 16409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // orderIndex is the next three MSB == 010 == 2. 16509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // subOrderIndexMask is a mask for the remaining bits == 11 (masking to 01 for the subOrderIndex). 16609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t order; 16709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (order = 0; order <= kBitsPerSizet; ++order) { 16809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t orderIndexShift; 16909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (order < kGenericNumBucketsPerOrderBits + 1) 17009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) orderIndexShift = 0; 17109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) else 17209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) orderIndexShift = order - (kGenericNumBucketsPerOrderBits + 1); 17309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->orderIndexShifts[order] = orderIndexShift; 17409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t subOrderIndexMask; 17509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (order == kBitsPerSizet) { 17609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // This avoids invoking undefined behavior for an excessive shift. 17709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) subOrderIndexMask = static_cast<size_t>(-1) >> (kGenericNumBucketsPerOrderBits + 1); 17809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } else { 17909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) subOrderIndexMask = ((1 << order) - 1) >> (kGenericNumBucketsPerOrderBits + 1); 18009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 18109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->orderSubIndexMasks[order] = subOrderIndexMask; 18209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 18309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 18409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Set up the actual usable buckets first. 18509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Note that typical values (i.e. min allocation size of 8) will result in 18609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // invalid buckets (size==9 etc. or more generally, size is not a multiple 18709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // of the smallest allocation granularity). 18809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // We avoid them in the bucket lookup map, but we tolerate them to keep the 18909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // code simpler and the structures more generic. 19009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t i, j; 19109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t currentSize = kGenericSmallestBucket; 19209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t currentIncrement = kGenericSmallestBucket >> kGenericNumBucketsPerOrderBits; 19309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket* bucket = &root->buckets[0]; 19409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (i = 0; i < kGenericNumBucketedOrders; ++i) { 19509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { 19609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->slotSize = currentSize; 19709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionBucketInitBase(bucket, root); 19809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Disable invalid buckets so that touching them faults. 19909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (currentSize % kGenericSmallestBucket) 20009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->activePagesHead = 0; 20109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) currentSize += currentIncrement; 20209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ++bucket; 20309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 20409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) currentIncrement <<= 1; 20509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 20609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(currentSize == 1 << kGenericMaxBucketedOrder); 20709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(bucket == &root->buckets[0] + (kGenericNumBucketedOrders * kGenericNumBucketsPerOrder)); 20809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 20909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Then set up the fast size -> bucket lookup table. 21009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket = &root->buckets[0]; 21109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket** bucketPtr = &root->bucketLookups[0]; 21209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (order = 0; order <= kBitsPerSizet; ++order) { 21309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { 21409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (order < kGenericMinBucketedOrder) { 21509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Use the bucket of finest granularity for malloc(0) etc. 21609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) *bucketPtr++ = &root->buckets[0]; 21709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } else if (order > kGenericMaxBucketedOrder) { 21809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) *bucketPtr++ = &PartitionRootGeneric::gPagedBucket; 21909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } else { 22009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket* validBucket = bucket; 22109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Skip over invalid buckets. 22209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) while (validBucket->slotSize % kGenericSmallestBucket) 22309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) validBucket++; 22409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) *bucketPtr++ = validBucket; 22509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket++; 22609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 22709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 22809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 22909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(bucket == &root->buckets[0] + (kGenericNumBucketedOrders * kGenericNumBucketsPerOrder)); 23009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(bucketPtr == &root->bucketLookups[0] + ((kBitsPerSizet + 1) * kGenericNumBucketsPerOrder)); 23109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // And there's one last bucket lookup that will be hit for e.g. malloc(-1), 23209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // which tries to overflow to a non-existant order. 23309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) *bucketPtr = &PartitionRootGeneric::gPagedBucket; 2345267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 2355267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 2361e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)static bool partitionAllocShutdownBucket(PartitionBucket* bucket) 2375267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 2385267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) // Failure here indicates a memory leak. 239591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch bool noLeaks = !bucket->numFullPages; 240a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionPage* page = bucket->activePagesHead; 24109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) while (page) { 242591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch if (page->numAllocatedSlots) 243591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch noLeaks = false; 24409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page = page->nextPage; 24509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 246591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 247591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch return noLeaks; 2485267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 2495267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 25009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static void partitionAllocBaseShutdown(PartitionRootBase* root) 2515267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 252521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) ASSERT(root->initialized); 253521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) root->initialized = false; 2541e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 255521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) // Now that we've examined all partition pages in all buckets, it's safe 2561e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // to free all our super pages. We first collect the super page pointers 2571e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // on the stack because some of them are themselves store in super pages. 2581e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) char* superPages[kMaxPartitionSize / kSuperPageSize]; 2591e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t numSuperPages = 0; 26009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionSuperPageExtentEntry* entry = root->firstExtent; 2611e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) while (entry) { 2621e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) char* superPage = entry->superPageBase; 2631e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) while (superPage != entry->superPagesEnd) { 2641e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) superPages[numSuperPages] = superPage; 2651e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) numSuperPages++; 2661e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) superPage += kSuperPageSize; 2671e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 2681e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) entry = entry->next; 2691e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 2701e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) ASSERT(numSuperPages == root->totalSizeOfSuperPages / kSuperPageSize); 27109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (size_t i = 0; i < numSuperPages; ++i) 272a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) freePages(superPages[i], kSuperPageSize); 27309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 27409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 27509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)bool partitionAllocShutdown(PartitionRoot* root) 27609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 27709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool noLeaks = true; 27809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t i; 27909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (i = 0; i < root->numBuckets; ++i) { 28009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket* bucket = &root->buckets()[i]; 28109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!partitionAllocShutdownBucket(bucket)) 28209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) noLeaks = false; 283a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) } 284591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 28509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionAllocBaseShutdown(root); 28609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return noLeaks; 28709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 28809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 28909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)bool partitionAllocGenericShutdown(PartitionRootGeneric* root) 29009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 29109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool noLeaks = true; 29209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t i; 29309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (i = 0; i < kGenericNumBucketedOrders * kGenericNumBucketsPerOrder; ++i) { 29409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket* bucket = &root->buckets[i]; 29509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!partitionAllocShutdownBucket(bucket)) 29609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) noLeaks = false; 29709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 29809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionAllocBaseShutdown(root); 299591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch return noLeaks; 3005267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 3015267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 3026f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochstatic NEVER_INLINE void partitionOutOfMemory() 3036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 3046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch IMMEDIATE_CRASH(); 3056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 3066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3076f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochstatic NEVER_INLINE void partitionFull() 3086f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 3096f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch IMMEDIATE_CRASH(); 3106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 3116f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3125d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)static ALWAYS_INLINE void partitionDecommitSystemPages(PartitionRootBase* root, void* addr, size_t len) 3135d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles){ 3145d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) decommitSystemPages(addr, len); 3155d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) ASSERT(root->totalSizeOfCommittedPages > len); 3165d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) root->totalSizeOfCommittedPages -= len; 3175d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)} 3185d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) 3195d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)static ALWAYS_INLINE void partitionRecommitSystemPages(PartitionRootBase* root, void* addr, size_t len) 3205d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles){ 3215d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) recommitSystemPages(addr, len); 3225d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) root->totalSizeOfCommittedPages += len; 3235d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)} 3245d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) 325f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)static ALWAYS_INLINE void* partitionAllocPartitionPages(PartitionRootBase* root, int flags, size_t numPartitionPages) 3265267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 32709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPage) % kPartitionPageSize)); 32809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPageEnd) % kPartitionPageSize)); 32909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) RELEASE_ASSERT(numPartitionPages <= kNumPartitionPagesPerSuperPage); 33009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t totalSize = kPartitionPageSize * numPartitionPages; 3315d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) root->totalSizeOfCommittedPages += totalSize; 33209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t numPartitionPagesLeft = (root->nextPartitionPageEnd - root->nextPartitionPage) >> kPartitionPageShift; 33309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (LIKELY(numPartitionPagesLeft >= numPartitionPages)) { 33409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // In this case, we can still hand out pages from the current super page 33509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // allocation. 3361e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) char* ret = root->nextPartitionPage; 33709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->nextPartitionPage += totalSize; 338a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) return ret; 3391e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 3401e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3411e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Need a new super page. 3421e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) root->totalSizeOfSuperPages += kSuperPageSize; 3436f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (root->totalSizeOfSuperPages > kMaxPartitionSize) 3446f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch partitionFull(); 345a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) char* requestedAddress = root->nextSuperPage; 346a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) char* superPage = reinterpret_cast<char*>(allocPages(requestedAddress, kSuperPageSize, kSuperPageSize)); 347f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) if (UNLIKELY(!superPage)) { 348f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) if (flags & PartitionAllocReturnNull) 349f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) return 0; 3506f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch partitionOutOfMemory(); 351f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) } 352a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) root->nextSuperPage = superPage + kSuperPageSize; 353a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) char* ret = superPage + kPartitionPageSize; 35409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->nextPartitionPage = ret + totalSize; 355a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) root->nextPartitionPageEnd = root->nextSuperPage - kPartitionPageSize; 35609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Make the first partition page in the super page a guard page, but leave a 35709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // hole in the middle. 358a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // This is where we put page metadata and also a tiny amount of extent 359a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // metadata. 360a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) setSystemPagesInaccessible(superPage, kSystemPageSize); 361a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) setSystemPagesInaccessible(superPage + (kSystemPageSize * 2), kPartitionPageSize - (kSystemPageSize * 2)); 362a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // Also make the last partition page a guard page. 363a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) setSystemPagesInaccessible(superPage + (kSuperPageSize - kPartitionPageSize), kPartitionPageSize); 364a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 365a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // If we were after a specific address, but didn't get it, assume that 366a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // the system chose a lousy address and re-randomize the next 367a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // allocation. 368a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) if (requestedAddress && requestedAddress != superPage) 369a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) root->nextSuperPage = 0; 3701e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3711e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // We allocated a new super page so update super page metadata. 3721e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // First check if this is a new extent or not. 37309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionSuperPageExtentEntry* latestExtent = reinterpret_cast<PartitionSuperPageExtentEntry*>(partitionSuperPageToMetadataArea(superPage)); 3741e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) PartitionSuperPageExtentEntry* currentExtent = root->currentExtent; 375a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) bool isNewExtent = (superPage != requestedAddress); 376a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) if (UNLIKELY(isNewExtent)) { 37709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) latestExtent->next = 0; 37809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (UNLIKELY(!currentExtent)) { 37909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->firstExtent = latestExtent; 38009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } else { 38109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(currentExtent->superPageBase); 38209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) currentExtent->next = latestExtent; 383521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) } 38409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->currentExtent = latestExtent; 38509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) currentExtent = latestExtent; 3861e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) currentExtent->superPageBase = superPage; 3871e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) currentExtent->superPagesEnd = superPage + kSuperPageSize; 3881e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else { 3891e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // We allocated next to an existing extent so just nudge the size up a little. 3901e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) currentExtent->superPagesEnd += kSuperPageSize; 3911e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) ASSERT(ret >= currentExtent->superPageBase && ret < currentExtent->superPagesEnd); 392521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) } 39309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // By storing the root in every extent metadata object, we have a fast way 39409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // to go from a pointer within the partition to the root object. 39509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) latestExtent->root = root; 3961e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 397a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) return ret; 3985267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 3995267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 4005d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)static ALWAYS_INLINE void partitionUnusePage(PartitionRootBase* root, PartitionPage* page) 4015267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 40209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->bucket->numSystemPagesPerSlotSpan); 403a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) void* addr = partitionPageToPointer(page); 4045d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) partitionDecommitSystemPages(root, addr, page->bucket->numSystemPagesPerSlotSpan * kSystemPageSize); 4055267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 4065267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 4075267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)static ALWAYS_INLINE size_t partitionBucketSlots(const PartitionBucket* bucket) 4085267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 40909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return (bucket->numSystemPagesPerSlotSpan * kSystemPageSize) / bucket->slotSize; 41009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 41109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 41209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static ALWAYS_INLINE size_t partitionBucketPartitionPages(const PartitionBucket* bucket) 41309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 41409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return (bucket->numSystemPagesPerSlotSpan + (kNumSystemPagesPerPartitionPage - 1)) / kNumSystemPagesPerPartitionPage; 4155267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 4165267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 417a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static ALWAYS_INLINE void partitionPageReset(PartitionPage* page, PartitionBucket* bucket) 4185267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 41909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page != &PartitionRootGeneric::gSeedPage); 42006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) page->numAllocatedSlots = 0; 42106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) page->numUnprovisionedSlots = partitionBucketSlots(bucket); 42209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->numUnprovisionedSlots); 4235267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) page->bucket = bucket; 42409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->nextPage = 0; 42506f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) // NULLing the freelist is not strictly necessary but it makes an ASSERT in partitionPageFillFreelist simpler. 42609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freelistHead = 0; 42709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->pageOffset = 0; 42809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freeCacheIndex = -1; 42909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t numPartitionPages = partitionBucketPartitionPages(bucket); 43009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t i; 43109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* pageCharPtr = reinterpret_cast<char*>(page); 43209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (i = 1; i < numPartitionPages; ++i) { 43309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) pageCharPtr += kPageMetadataSize; 43409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* secondaryPage = reinterpret_cast<PartitionPage*>(pageCharPtr); 43509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) secondaryPage->pageOffset = i; 43609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 43706f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)} 43806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) 439a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static ALWAYS_INLINE char* partitionPageAllocAndFillFreelist(PartitionPage* page) 44006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles){ 44109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page != &PartitionRootGeneric::gSeedPage); 44206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) size_t numSlots = page->numUnprovisionedSlots; 44306f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) ASSERT(numSlots); 44406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) PartitionBucket* bucket = page->bucket; 44506f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) // We should only get here when _every_ slot is either used or unprovisioned. 44606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) // (The third state is "on the freelist". If we have a non-empty freelist, we should not get here.) 44706f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) ASSERT(numSlots + page->numAllocatedSlots == partitionBucketSlots(bucket)); 44806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) // Similarly, make explicitly sure that the freelist is empty. 44909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!page->freelistHead); 45009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->numAllocatedSlots >= 0); 45106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) 45209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t size = bucket->slotSize; 453a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) char* base = reinterpret_cast<char*>(partitionPageToPointer(page)); 454a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) char* returnObject = base + (size * page->numAllocatedSlots); 45509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* firstFreelistPointer = returnObject + size; 45609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* firstFreelistPointerExtent = firstFreelistPointer + sizeof(PartitionFreelistEntry*); 45709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Our goal is to fault as few system pages as possible. We calculate the 45809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // page containing the "end" of the returned slot, and then allow freelist 45909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // pointers to be written up to the end of that page. 46009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* subPageLimit = reinterpret_cast<char*>((reinterpret_cast<uintptr_t>(firstFreelistPointer) + kSystemPageOffsetMask) & kSystemPageBaseMask); 46109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* slotsLimit = returnObject + (size * page->numUnprovisionedSlots); 46209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* freelistLimit = subPageLimit; 46309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (UNLIKELY(slotsLimit < freelistLimit)) 46409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) freelistLimit = slotsLimit; 46506f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) 46606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) size_t numNewFreelistEntries = 0; 46709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (LIKELY(firstFreelistPointerExtent <= freelistLimit)) { 46809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Only consider used space in the slot span. If we consider wasted 46909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // space, we may get an off-by-one when a freelist pointer fits in the 47009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // wasted space, but a slot does not. 47109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // We know we can fit at least one freelist pointer. 47209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) numNewFreelistEntries = 1; 47309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Any further entries require space for the whole slot span. 47409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) numNewFreelistEntries += (freelistLimit - firstFreelistPointerExtent) / size; 47509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 47606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) 47706f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) // We always return an object slot -- that's the +1 below. 47806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) // We do not neccessarily create any new freelist entries, because we cross sub page boundaries frequently for large bucket sizes. 47909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(numNewFreelistEntries + 1 <= numSlots); 48006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) numSlots -= (numNewFreelistEntries + 1); 48106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) page->numUnprovisionedSlots = numSlots; 48206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) page->numAllocatedSlots++; 48306f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) 48406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) if (LIKELY(numNewFreelistEntries)) { 48509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* freelistPointer = firstFreelistPointer; 48609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*>(freelistPointer); 48709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freelistHead = entry; 48806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) while (--numNewFreelistEntries) { 48909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) freelistPointer += size; 49009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionFreelistEntry* nextEntry = reinterpret_cast<PartitionFreelistEntry*>(freelistPointer); 49106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) entry->next = partitionFreelistMask(nextEntry); 49206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) entry = nextEntry; 49306f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) } 49406f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) entry->next = partitionFreelistMask(0); 49506f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) } else { 49609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freelistHead = 0; 4975267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 49806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) return returnObject; 4995267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 5005267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 501a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// This helper function scans the active page list for a suitable new active 502d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)// page, starting at the passed in page. 50309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// When it finds a suitable new active page (one that has free slots), it is 50409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// set as the new active page and true is returned. If there is no suitable new 505d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)// active page, false is returned and the current active page is set to null. 506d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)// As potential pages are scanned, they are tidied up according to their state. 507d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)// Freed pages are swept on to the free page list and full pages are unlinked 508d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)// from any list. 509d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)static ALWAYS_INLINE bool partitionSetNewActivePage(PartitionPage* page) 5105267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 51109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (page == &PartitionRootBase::gSeedPage) { 51209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!page->nextPage); 51309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return false; 51409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 51509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 51609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* nextPage = 0; 517d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) PartitionBucket* bucket = page->bucket; 518d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 51909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (; page; page = nextPage) { 52009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) nextPage = page->nextPage; 521d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(page->bucket == bucket); 52209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page != bucket->freePagesHead); 52309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!bucket->freePagesHead || page != bucket->freePagesHead->nextPage); 5245267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 525a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // Page is usable if it has something on the freelist, or unprovisioned 526a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // slots that can be turned into a freelist. 52709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (LIKELY(page->freelistHead != 0) || LIKELY(page->numUnprovisionedSlots)) { 52809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->activePagesHead = page; 52909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return true; 53009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 53109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 53209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->numAllocatedSlots >= 0); 53309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (LIKELY(page->numAllocatedSlots == 0)) { 53409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->freeCacheIndex == -1); 53509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // We hit a free page, so shepherd it on to the free page list. 53609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->nextPage = bucket->freePagesHead; 53709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->freePagesHead = page; 53809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } else { 53909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // If we get here, we found a full page. Skip over it too, and also 54009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // tag it as full (via a negative value). We need it tagged so that 54109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // free'ing can tell, and move it back into the active page list. 54209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->numAllocatedSlots == static_cast<int>(partitionBucketSlots(bucket))); 54309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->numAllocatedSlots = -page->numAllocatedSlots; 54409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ++bucket->numFullPages; 54509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // numFullPages is a uint16_t for efficient packing so guard against 54609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // overflow to be safe. 54709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) RELEASE_ASSERT(bucket->numFullPages); 54809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Not necessary but might help stop accidents. 54909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->nextPage = 0; 55009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 551a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) } 552a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 553d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) bucket->activePagesHead = 0; 55409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return false; 5555267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 5565267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 557d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)struct PartitionDirectMapExtent { 558d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t mapSize; // Mapped size, not including guard pages and meta-data. 559d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)}; 560d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 561d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)static ALWAYS_INLINE PartitionDirectMapExtent* partitionPageToDirectMapExtent(PartitionPage* page) 562d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 563d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(partitionBucketIsDirectMapped(page->bucket)); 564d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return reinterpret_cast<PartitionDirectMapExtent*>(reinterpret_cast<char*>(page) + 2 * kPageMetadataSize); 565d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 566d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 56709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static ALWAYS_INLINE void* partitionDirectMap(PartitionRootBase* root, int flags, size_t size) 5685267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 569d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size = partitionDirectMapSize(size); 570d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 57109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Because we need to fake looking like a super page, We need to allocate 57209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // a bunch of system pages more than "size": 57309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // - The first few system pages are the partition page in which the super 57409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // page metadata is stored. We fault just one system page out of a partition 57509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // page sized clump. 57609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // - We add a trailing guard page. 57709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t mapSize = size + kPartitionPageSize + kSystemPageSize; 57809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Round up to the allocation granularity. 57909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) mapSize += kPageAllocationGranularityOffsetMask; 58009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) mapSize &= kPageAllocationGranularityBaseMask; 58109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 58209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // TODO: we may want to let the operating system place these allocations 58309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // where it pleases. On 32-bit, this might limit address space 58409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // fragmentation and on 64-bit, this might have useful savings for TLB 58509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // and page table overhead. 58609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // TODO: if upsizing realloc()s are common on large sizes, we could 58709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // consider over-allocating address space on 64-bit, "just in case". 58809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // TODO: consider pre-populating page tables (e.g. MAP_POPULATE on Linux, 58909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // MADV_WILLNEED on POSIX). 59009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // TODO: these pages will be zero-filled. Consider internalizing an 59109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // allocZeroed() API so we can avoid a memset() entirely in this case. 59209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* ptr = reinterpret_cast<char*>(allocPages(0, mapSize, kSuperPageSize)); 59309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!ptr) { 59409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (flags & PartitionAllocReturnNull) 59509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return 0; 5966f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch partitionOutOfMemory(); 59709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 59809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* ret = ptr + kPartitionPageSize; 59909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // TODO: due to all the guard paging, this arrangement creates 4 mappings. 60009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // We could get it down to three by using read-only for the metadata page, 60109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // or perhaps two by leaving out the trailing guard page on 64-bit. 60209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setSystemPagesInaccessible(ptr, kSystemPageSize); 60309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setSystemPagesInaccessible(ptr + (kSystemPageSize * 2), kPartitionPageSize - (kSystemPageSize * 2)); 60409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) setSystemPagesInaccessible(ret + size, kSystemPageSize); 60509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 60609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionSuperPageExtentEntry* extent = reinterpret_cast<PartitionSuperPageExtentEntry*>(partitionSuperPageToMetadataArea(ptr)); 60709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) extent->root = root; 60809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* page = partitionPointerToPageNoAlignmentCheck(ret); 60909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket* bucket = reinterpret_cast<PartitionBucket*>(reinterpret_cast<char*>(page) + kPageMetadataSize); 61009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freelistHead = 0; 61109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->nextPage = 0; 61209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->bucket = bucket; 61309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->numAllocatedSlots = 1; 61409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->numUnprovisionedSlots = 0; 61509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->pageOffset = 0; 61609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freeCacheIndex = 0; 61709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 61809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->activePagesHead = 0; 61909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->freePagesHead = 0; 62009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->slotSize = size; 62109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->numSystemPagesPerSlotSpan = 0; 62209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->numFullPages = 0; 62309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 624d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) PartitionDirectMapExtent* mapExtent = partitionPageToDirectMapExtent(page); 625d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) mapExtent->mapSize = mapSize - kPartitionPageSize - kSystemPageSize; 626d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 62709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return ret; 628a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)} 6295267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 63009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static ALWAYS_INLINE void partitionDirectUnmap(PartitionPage* page) 631a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles){ 632d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t unmapSize = partitionPageToDirectMapExtent(page)->mapSize; 633d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 63409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Add on the size of the trailing guard page and preceeding partition 635d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // page. 63609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) unmapSize += kPartitionPageSize + kSystemPageSize; 637d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 638d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(!(unmapSize & kPageAllocationGranularityOffsetMask)); 63909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 64009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); 64109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Account for the mapping starting a partition page before the actual 64209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // allocation address. 64309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ptr -= kPartitionPageSize; 64409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 64509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) freePages(ptr, unmapSize); 6465267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 6475267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 64809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void* partitionAllocSlowPath(PartitionRootBase* root, int flags, size_t size, PartitionBucket* bucket) 6495267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 65006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) // The slow path is called when the freelist is empty. 65109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!bucket->activePagesHead->freelistHead); 65209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 65309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // For the partitionAllocGeneric API, we have a bunch of buckets marked 65409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // as special cases. We bounce them through to the slow path so that we 65509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // can still have a blazing fast hot path due to lack of corner-case 65609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // branches. 65709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool returnNull = flags & PartitionAllocReturnNull; 658d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) { 65909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(size > kGenericMaxBucketed); 66009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(bucket == &PartitionRootBase::gPagedBucket); 661d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (size > kGenericMaxDirectMapped) { 66209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (returnNull) 66309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return 0; 66409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) RELEASE_ASSERT(false); 66509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 66609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return partitionDirectMap(root, flags, size); 66709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 668a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 669a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // First, look for a usable page in the existing active pages list. 67009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Change active page, accepting the current page as a candidate. 671d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (LIKELY(partitionSetNewActivePage(bucket->activePagesHead))) { 67209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* newPage = bucket->activePagesHead; 67309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (LIKELY(newPage->freelistHead != 0)) { 67409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionFreelistEntry* ret = newPage->freelistHead; 67509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) newPage->freelistHead = partitionFreelistMask(ret->next); 67609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) newPage->numAllocatedSlots++; 6775267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) return ret; 6785267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 67909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(newPage->numUnprovisionedSlots); 68009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return partitionPageAllocAndFillFreelist(newPage); 6811e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 6821e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 683a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // Second, look in our list of freed but reserved pages. 684a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionPage* newPage = bucket->freePagesHead; 685a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) if (LIKELY(newPage != 0)) { 68609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(newPage != &PartitionRootGeneric::gSeedPage); 68709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!newPage->freelistHead); 68809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!newPage->numAllocatedSlots); 68909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!newPage->numUnprovisionedSlots); 69009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(newPage->freeCacheIndex == -1); 69109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bucket->freePagesHead = newPage->nextPage; 692d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) void* addr = partitionPageToPointer(newPage); 6935d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) partitionRecommitSystemPages(root, addr, newPage->bucket->numSystemPagesPerSlotSpan * kSystemPageSize); 6945267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } else { 695a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // Third. If we get here, we need a brand new page. 69609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t numPartitionPages = partitionBucketPartitionPages(bucket); 697f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) void* rawNewPage = partitionAllocPartitionPages(root, flags, numPartitionPages); 698f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) if (UNLIKELY(!rawNewPage)) { 699f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) ASSERT(returnNull); 700f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) return 0; 701f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) } 70209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Skip the alignment check because it depends on page->bucket, which is not yet set. 703a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) newPage = partitionPointerToPageNoAlignmentCheck(rawNewPage); 7045267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 7055267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 70606f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) partitionPageReset(newPage, bucket); 707a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) bucket->activePagesHead = newPage; 708a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) return partitionPageAllocAndFillFreelist(newPage); 7095267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 7105267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 7115d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)static ALWAYS_INLINE void partitionFreePage(PartitionRootBase* root, PartitionPage* page) 71209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 71309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->freelistHead); 71409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!page->numAllocatedSlots); 7155d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) partitionUnusePage(root, page); 71609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // We actually leave the freed page in the active list. We'll sweep it on 71709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // to the free page list when we next walk the active page list. Pulling 71809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // this trick enables us to use a singly-linked page list for all cases, 71909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // which is critical in keeping the page metadata structure down to 32 72009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // bytes in size. 72109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freelistHead = 0; 72209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->numUnprovisionedSlots = 0; 72309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 72409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 72509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static ALWAYS_INLINE void partitionRegisterEmptyPage(PartitionPage* page) 72609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 72709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionRootBase* root = partitionPageToRoot(page); 7285d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) 72909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // If the page is already registered as empty, give it another life. 73009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (page->freeCacheIndex != -1) { 73109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->freeCacheIndex >= 0); 73209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(static_cast<unsigned>(page->freeCacheIndex) < kMaxFreeableSpans); 73309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(root->globalEmptyPageRing[page->freeCacheIndex] == page); 73409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->globalEmptyPageRing[page->freeCacheIndex] = 0; 73509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 73609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 73709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t currentIndex = root->globalEmptyPageRingIndex; 73809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* pageToFree = root->globalEmptyPageRing[currentIndex]; 73909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // The page might well have been re-activated, filled up, etc. before we get 74009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // around to looking at it here. 74109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (pageToFree) { 74209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(pageToFree != &PartitionRootBase::gSeedPage); 74309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(pageToFree->freeCacheIndex >= 0); 74409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(static_cast<unsigned>(pageToFree->freeCacheIndex) < kMaxFreeableSpans); 74509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(pageToFree == root->globalEmptyPageRing[pageToFree->freeCacheIndex]); 74609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!pageToFree->numAllocatedSlots && pageToFree->freelistHead) { 74709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // The page is still empty, and not freed, so _really_ free it. 7485d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) partitionFreePage(root, pageToFree); 74909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 75009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) pageToFree->freeCacheIndex = -1; 75109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 75209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 75309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // We put the empty slot span on our global list of "pages that were once 75409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // empty". thus providing it a bit of breathing room to get re-used before 75509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // we really free it. This improves performance, particularly on Mac OS X 75609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // which has subpar memory management performance. 75709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->globalEmptyPageRing[currentIndex] = page; 75809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freeCacheIndex = currentIndex; 75909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ++currentIndex; 76009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (currentIndex == kMaxFreeableSpans) 76109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) currentIndex = 0; 76209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) root->globalEmptyPageRingIndex = currentIndex; 76309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 76409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 765a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)void partitionFreeSlowPath(PartitionPage* page) 7665267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 7675267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) PartitionBucket* bucket = page->bucket; 76809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page != &PartitionRootGeneric::gSeedPage); 76909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(bucket->activePagesHead != &PartitionRootGeneric::gSeedPage); 7705267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) if (LIKELY(page->numAllocatedSlots == 0)) { 7715267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) // Page became fully unused. 772d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) { 77309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionDirectUnmap(page); 77409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return; 77509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 7765d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) // If it's the current active page, attempt to change it. We'd prefer to leave 77709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // the page empty as a gentle force towards defragmentation. 778d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (LIKELY(page == bucket->activePagesHead) && page->nextPage) { 779d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (partitionSetNewActivePage(page->nextPage)) { 78009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(bucket->activePagesHead != page); 78109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Link the empty page back in after the new current page, to 78209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // avoid losing a reference to it. 78309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // TODO: consider walking the list to link the empty page after 78409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // all non-empty pages? 78509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* currentPage = bucket->activePagesHead; 78609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->nextPage = currentPage->nextPage; 78709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) currentPage->nextPage = page; 788d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } else { 789d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) bucket->activePagesHead = page; 790d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) page->nextPage = 0; 791a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) } 7921e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 79309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionRegisterEmptyPage(page); 7945267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } else { 7951e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Ensure that the page is full. That's the only valid case if we 7961e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // arrive here. 7971e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) ASSERT(page->numAllocatedSlots < 0); 79809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // A transition of numAllocatedSlots from 0 to -1 is not legal, and 79909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // likely indicates a double-free. 80009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) RELEASE_ASSERT(page->numAllocatedSlots != -1); 80109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->numAllocatedSlots = -page->numAllocatedSlots - 2; 80209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->numAllocatedSlots == static_cast<int>(partitionBucketSlots(bucket) - 1)); 8035267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) // Fully used page became partially used. It must be put back on the 8041e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // non-full page list. Also make it the current page to increase the 8051e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // chances of it being filled up again. The old current page will be 8061e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // the next page. 80709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->nextPage = bucket->activePagesHead; 808a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) bucket->activePagesHead = page; 8095267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) --bucket->numFullPages; 81009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Special case: for a partition page with just a single slot, it may 81109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // now be empty and we want to run it through the empty logic. 81209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (UNLIKELY(page->numAllocatedSlots == 0)) 81309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionFreeSlowPath(page); 8145267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 8155267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 8165267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 817d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)bool partitionReallocDirectMappedInPlace(PartitionRootGeneric* root, PartitionPage* page, size_t newSize) 818d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 819d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(partitionBucketIsDirectMapped(page->bucket)); 820d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 821d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) newSize = partitionCookieSizeAdjustAdd(newSize); 822d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 823d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Note that the new size might be a bucketed size; this function is called 824d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // whenever we're reallocating a direct mapped allocation. 825d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) newSize = partitionDirectMapSize(newSize); 826d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (newSize < kGenericMinDirectMappedDownsize) 827d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return false; 828d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 829d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // bucket->slotSize is the current size of the allocation. 830d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t currentSize = page->bucket->slotSize; 831d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (newSize == currentSize) 832d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return true; 833d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 834d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) char* charPtr = static_cast<char*>(partitionPageToPointer(page)); 835d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 836d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (newSize < currentSize) { 837f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu size_t mapSize = partitionPageToDirectMapExtent(page)->mapSize; 838f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu 839f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu // Don't reallocate in-place if new size is less than 80 % of the full 840f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu // map size, to avoid holding on to too much unused address space. 841f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu if ((newSize / kSystemPageSize) * 5 < (mapSize / kSystemPageSize) * 4) 842f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu return false; 843f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu 844d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Shrink by decommitting unneeded pages and making them inaccessible. 845d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t decommitSize = currentSize - newSize; 8465d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) partitionDecommitSystemPages(root, charPtr + newSize, decommitSize); 847d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) setSystemPagesInaccessible(charPtr + newSize, decommitSize); 848d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } else if (newSize <= partitionPageToDirectMapExtent(page)->mapSize) { 849d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Grow within the actually allocated memory. Just need to make the 850d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // pages accessible again. 851d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t recommitSize = newSize - currentSize; 852d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) setSystemPagesAccessible(charPtr + currentSize, recommitSize); 8535d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) partitionRecommitSystemPages(root, charPtr + currentSize, recommitSize); 854d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 855d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#ifndef NDEBUG 856d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) memset(charPtr + currentSize, kUninitializedByte, recommitSize); 857d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#endif 858d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } else { 859d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // We can't perform the realloc in-place. 860d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // TODO: support this too when possible. 861d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return false; 862d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 863d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 864d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#ifndef NDEBUG 865d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Write a new trailing cookie. 866d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) partitionCookieWriteValue(charPtr + newSize - kCookieSize); 867d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#endif 868d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 869d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) page->bucket->slotSize = newSize; 870d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return true; 871d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 872d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 87309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newSize) 8741fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch{ 8751fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 8761fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch return realloc(ptr, newSize); 8771fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#else 87809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (UNLIKELY(!ptr)) 87909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return partitionAllocGeneric(root, newSize); 88009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (UNLIKELY(!newSize)) { 88109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionFreeGeneric(root, ptr); 88209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return 0; 8831e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 8841e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 885d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) RELEASE_ASSERT(newSize <= kGenericMaxDirectMapped); 886d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 887d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(ptr))); 888d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 889d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) PartitionPage* page = partitionPointerToPage(partitionCookieFreePointerAdjust(ptr)); 890d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 891d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (UNLIKELY(partitionBucketIsDirectMapped(page->bucket))) { 892d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // We may be able to perform the realloc in place by changing the 893d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // accessibility of memory pages and, if reducing the size, decommitting 894d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // them. 895d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (partitionReallocDirectMappedInPlace(root, page, newSize)) 896d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return ptr; 897d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 898d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 899d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t actualNewSize = partitionAllocActualSize(root, newSize); 900d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t actualOldSize = partitionAllocGetSize(ptr); 901d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 90209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the 90309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // new size is a significant percentage smaller. We could do the same if we 90409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // determine it is a win. 905d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (actualNewSize == actualOldSize) { 906d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Trying to allocate a block of size newSize would give us a block of 907d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // the same size as the one we've already got, so no point in doing 908d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // anything here. 9091fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch return ptr; 910d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 91109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 9121fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch // This realloc cannot be resized in-place. Sadness. 9131fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch void* ret = partitionAllocGeneric(root, newSize); 914d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t copySize = actualOldSize; 91519cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) if (newSize < copySize) 9161fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch copySize = newSize; 91709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 9181fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch memcpy(ret, ptr, copySize); 9191e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) partitionFreeGeneric(root, ptr); 9201fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch return ret; 9211fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#endif 9221fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch} 9231fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch 9245267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#ifndef NDEBUG 9255267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 9265267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)void partitionDumpStats(const PartitionRoot& root) 9275267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 9285267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) size_t i; 92906f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) size_t totalLive = 0; 93006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) size_t totalResident = 0; 93106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) size_t totalFreeable = 0; 9328abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) for (i = 0; i < root.numBuckets; ++i) { 9338abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) const PartitionBucket& bucket = root.buckets()[i]; 93409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (bucket.activePagesHead == &PartitionRootGeneric::gSeedPage && !bucket.freePagesHead && !bucket.numFullPages) { 9351e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Empty bucket with no freelist or full pages. Skip reporting it. 9365267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) continue; 9375267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 9385267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) size_t numFreePages = 0; 939a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionPage* freePages = bucket.freePagesHead; 9405267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) while (freePages) { 9415267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) ++numFreePages; 94209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) freePages = freePages->nextPage; 9435267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 94409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t bucketSlotSize = bucket.slotSize; 9455267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) size_t bucketNumSlots = partitionBucketSlots(&bucket); 9461e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t bucketUsefulStorage = bucketSlotSize * bucketNumSlots; 94709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t bucketPageSize = bucket.numSystemPagesPerSlotSpan * kSystemPageSize; 94809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t bucketWaste = bucketPageSize - bucketUsefulStorage; 9491e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t numActiveBytes = bucket.numFullPages * bucketUsefulStorage; 95009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t numResidentBytes = bucket.numFullPages * bucketPageSize; 9511e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t numFreeableBytes = 0; 95206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) size_t numActivePages = 0; 953a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) const PartitionPage* page = bucket.activePagesHead; 954d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) while (page) { 955d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) ASSERT(page != &PartitionRootGeneric::gSeedPage); 956d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) // A page may be on the active list but freed and not yet swept. 957d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) if (!page->freelistHead && !page->numUnprovisionedSlots && !page->numAllocatedSlots) { 958d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) ++numFreePages; 959d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) } else { 9605267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) ++numActivePages; 9615267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) numActiveBytes += (page->numAllocatedSlots * bucketSlotSize); 962a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) size_t pageBytesResident = (bucketNumSlots - page->numUnprovisionedSlots) * bucketSlotSize; 963a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // Round up to system page size. 964a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) pageBytesResident = (pageBytesResident + kSystemPageOffsetMask) & kSystemPageBaseMask; 96506f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) numResidentBytes += pageBytesResident; 9661e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (!page->numAllocatedSlots) 9671e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) numFreeableBytes += pageBytesResident; 9685267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 96909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page = page->nextPage; 970d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) } 97106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) totalLive += numActiveBytes; 97206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) totalResident += numResidentBytes; 9731e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) totalFreeable += numFreeableBytes; 97409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) printf("bucket size %zu (pageSize %zu waste %zu): %zu alloc/%zu commit/%zu freeable bytes, %zu/%zu/%zu full/active/free pages\n", bucketSlotSize, bucketPageSize, bucketWaste, numActiveBytes, numResidentBytes, numFreeableBytes, static_cast<size_t>(bucket.numFullPages), numActivePages, numFreePages); 9755267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 97651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) printf("total live: %zu bytes\n", totalLive); 97751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) printf("total resident: %zu bytes\n", totalResident); 97851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) printf("total freeable: %zu bytes\n", totalFreeable); 97906f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) fflush(stdout); 9805267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 98106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) 9825267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#endif // !NDEBUG 9835267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 9845267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} // namespace WTF 9855267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 986