| /* |
| * Copyright (C) 2013 Google Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are |
| * met: |
| * |
| * * Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * * Redistributions in binary form must reproduce the above |
| * copyright notice, this list of conditions and the following disclaimer |
| * in the documentation and/or other materials provided with the |
| * distribution. |
| * * Neither the name of Google Inc. nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include "wtf/PartitionAlloc.h" |
| |
| #include "wtf/PageAllocator.h" |
| #include "wtf/Vector.h" |
| |
| #ifndef NDEBUG |
| #include <stdio.h> |
| #endif |
| |
| COMPILE_ASSERT(WTF::kPartitionPageSize < WTF::kSuperPageSize, ok_partition_page_size); |
| |
| namespace WTF { |
| |
| void partitionAllocInit(PartitionRoot* root) |
| { |
| ASSERT(!root->initialized); |
| root->initialized = true; |
| root->lock = 0; |
| size_t i; |
| for (i = 0; i < kNumBuckets; ++i) { |
| PartitionBucket* bucket = &root->buckets[i]; |
| bucket->root = root; |
| bucket->currPage = &root->seedPage; |
| bucket->freePages = 0; |
| bucket->numFullPages = 0; |
| } |
| |
| root->nextSuperPage = 0; |
| root->nextPartitionPage = 0; |
| root->nextPartitionPageEnd = 0; |
| root->seedPage.numAllocatedSlots = 0; |
| root->seedPage.bucket = &root->seedBucket; |
| root->seedPage.freelistHead = 0; |
| root->seedPage.next = &root->seedPage; |
| root->seedPage.prev = &root->seedPage; |
| |
| root->seedBucket.root = root; |
| root->seedBucket.currPage = 0; |
| root->seedBucket.freePages = 0; |
| root->seedBucket.numFullPages = 0; |
| } |
| |
| static ALWAYS_INLINE void partitionFreeSuperPage(PartitionPageHeader* page) |
| { |
| freeSuperPages(page, kSuperPageSize); |
| } |
| |
| static void partitionCollectIfSuperPage(PartitionPageHeader* partitionPage, Vector<PartitionPageHeader*>* superPages) |
| { |
| PartitionPageHeader* superPage = reinterpret_cast<PartitionPageHeader*>(reinterpret_cast<uintptr_t>(partitionPage) & kSuperPageBaseMask); |
| uintptr_t superPageOffset = reinterpret_cast<uintptr_t>(partitionPage) & kSuperPageOffsetMask; |
| // If this partition page is at the start of a super page, note it so we can |
| // free all the distinct super pages. |
| if (!superPageOffset) |
| superPages->append(superPage); |
| } |
| |
| static bool partitionAllocShutdownBucket(PartitionBucket* bucket, Vector<PartitionPageHeader*>* superPages) |
| { |
| // Failure here indicates a memory leak. |
| bool noLeaks = !bucket->numFullPages; |
| PartitionFreepagelistEntry* entry = bucket->freePages; |
| while (entry) { |
| PartitionFreepagelistEntry* next = entry->next; |
| partitionCollectIfSuperPage(entry->page, superPages); |
| partitionFree(entry); |
| entry = next; |
| } |
| PartitionPageHeader* page = bucket->currPage; |
| do { |
| if (page->numAllocatedSlots) |
| noLeaks = false; |
| PartitionPageHeader* next = page->next; |
| if (page != &bucket->root->seedPage) |
| partitionCollectIfSuperPage(page, superPages); |
| page = next; |
| } while (page != bucket->currPage); |
| |
| return noLeaks; |
| } |
| |
| bool partitionAllocShutdown(PartitionRoot* root) |
| { |
| bool noLeaks = true; |
| ASSERT(root->initialized); |
| root->initialized = false; |
| // As we iterate through all the partition pages, we keep a list of all the |
| // distinct super pages that we have seen. This is so that we can free all |
| // the super pages correctly. A super page must be freed all at once -- it |
| // is not permissible to free a super page by freeing all its component |
| // partition pages. |
| // Note that we cannot free a super page upon discovering it, because a |
| // single super page will likely contain partition pages from multiple |
| // different buckets. |
| Vector<PartitionPageHeader*> superPages; |
| size_t i; |
| // First, free the non-freepage buckets. Freeing the free pages in these |
| // buckets will depend on the freepage bucket. |
| for (i = 0; i < kNumBuckets; ++i) { |
| if (i != kFreePageBucket) { |
| PartitionBucket* bucket = &root->buckets[i]; |
| if (!partitionAllocShutdownBucket(bucket, &superPages)) |
| noLeaks = false; |
| } |
| } |
| // Finally, free the freepage bucket. |
| (void) partitionAllocShutdownBucket(&root->buckets[kFreePageBucket], &superPages); |
| // Now that we've examined all partition pages in all buckets, it's safe |
| // to free all our super pages. |
| for (Vector<PartitionPageHeader*>::iterator it = superPages.begin(); it != superPages.end(); ++it) |
| partitionFreeSuperPage(*it); |
| |
| return noLeaks; |
| } |
| |
| static ALWAYS_INLINE PartitionPageHeader* partitionAllocPage(PartitionRoot* root) |
| { |
| char* ret = 0; |
| if (LIKELY(root->nextPartitionPage != 0)) { |
| // In this case, we can still hand out pages from a previous |
| // super page allocation. |
| ret = root->nextPartitionPage; |
| root->nextPartitionPage += kPartitionPageSize; |
| if (UNLIKELY(root->nextPartitionPage == root->nextPartitionPageEnd)) { |
| // We ran out, need to get more pages next time. |
| root->nextPartitionPage = 0; |
| root->nextPartitionPageEnd = 0; |
| } |
| } else { |
| // Need a new super page. |
| // We need to put a guard page in front if either: |
| // a) This is the first super page allocation. |
| // b) The super page did not end up at our suggested address. |
| bool needsGuard = false; |
| if (!root->nextSuperPage) { |
| needsGuard = true; |
| root->nextSuperPage = getRandomSuperPageBase(); |
| } |
| ret = reinterpret_cast<char*>(allocSuperPages(root->nextSuperPage, kSuperPageSize)); |
| if (ret != root->nextSuperPage) { |
| needsGuard = true; |
| // Re-randomize the base location for next time just in case the |
| // underlying operating system picks lousy locations for mappings. |
| root->nextSuperPage = 0; |
| } else { |
| root->nextSuperPage = ret + kSuperPageSize; |
| } |
| root->nextPartitionPageEnd = ret + kSuperPageSize; |
| if (needsGuard) { |
| setSystemPagesInaccessible(ret, kPartitionPageSize); |
| ret += kPartitionPageSize; |
| } |
| root->nextPartitionPage = ret + kPartitionPageSize; |
| } |
| return reinterpret_cast<PartitionPageHeader*>(ret); |
| } |
| |
| static ALWAYS_INLINE void partitionUnusePage(PartitionPageHeader* page) |
| { |
| decommitSystemPages(page, kPartitionPageSize); |
| } |
| |
| static ALWAYS_INLINE size_t partitionBucketSlots(const PartitionBucket* bucket) |
| { |
| ASSERT(!(sizeof(PartitionPageHeader) % sizeof(void*))); |
| return (kPartitionPageSize - sizeof(PartitionPageHeader)) / partitionBucketSize(bucket); |
| } |
| |
| static ALWAYS_INLINE void partitionPageInit(PartitionPageHeader* page, PartitionBucket* bucket) |
| { |
| page->numAllocatedSlots = 1; |
| page->bucket = bucket; |
| size_t size = partitionBucketSize(bucket); |
| size_t numSlots = partitionBucketSlots(bucket); |
| RELEASE_ASSERT(numSlots > 1); |
| page->freelistHead = reinterpret_cast<PartitionFreelistEntry*>((reinterpret_cast<char*>(page) + sizeof(PartitionPageHeader) + size)); |
| PartitionFreelistEntry* freelist = page->freelistHead; |
| // Account for the slot we've handed out right away as a return value. |
| --numSlots; |
| // This loop sets up the initial chain of freelist pointers in the new page. |
| while (--numSlots) { |
| PartitionFreelistEntry* next = reinterpret_cast<PartitionFreelistEntry*>(reinterpret_cast<char*>(freelist) + size); |
| freelist->next = partitionFreelistMask(next); |
| freelist = next; |
| } |
| freelist->next = partitionFreelistMask(0); |
| } |
| |
| static ALWAYS_INLINE void partitionUnlinkPage(PartitionPageHeader* page) |
| { |
| ASSERT(page->prev->next == page); |
| ASSERT(page->next->prev == page); |
| |
| page->next->prev = page->prev; |
| page->prev->next = page->next; |
| } |
| |
| static ALWAYS_INLINE void partitionLinkPage(PartitionPageHeader* newPage, PartitionPageHeader* prevPage) |
| { |
| ASSERT(prevPage->prev->next == prevPage); |
| ASSERT(prevPage->next->prev == prevPage); |
| |
| newPage->prev = prevPage; |
| newPage->next = prevPage->next; |
| |
| prevPage->next->prev = newPage; |
| prevPage->next = newPage; |
| } |
| |
| void* partitionAllocSlowPath(PartitionBucket* bucket) |
| { |
| // Slow path. First look for a page in our linked ring list of non-full |
| // pages. |
| PartitionPageHeader* page = bucket->currPage; |
| PartitionPageHeader* next = page->next; |
| ASSERT(page == &bucket->root->seedPage || (page->bucket == bucket && next->bucket == bucket)); |
| |
| while (LIKELY(next != page)) { |
| ASSERT(next->bucket == bucket); |
| ASSERT(next->next->prev == next); |
| ASSERT(next->prev->next == next); |
| ASSERT(next != &bucket->root->seedPage); |
| if (LIKELY(next->freelistHead != 0)) { |
| bucket->currPage = next; |
| PartitionFreelistEntry* ret = next->freelistHead; |
| next->freelistHead = partitionFreelistMask(ret->next); |
| next->numAllocatedSlots++; |
| return ret; |
| } |
| // Pull this page out of the non-full page list, since it has no free |
| // slots. |
| // This tags the page as full so that free'ing can tell, and move |
| // the page back into the non-full page list when appropriate. |
| ASSERT(next->numAllocatedSlots == partitionBucketSlots(bucket)); |
| next->numAllocatedSlots = -next->numAllocatedSlots; |
| partitionUnlinkPage(next); |
| ++bucket->numFullPages; |
| |
| next = next->next; |
| } |
| |
| // Second, look in our list of freed but reserved pages. |
| PartitionPageHeader* newPage; |
| PartitionFreepagelistEntry* pagelist = bucket->freePages; |
| if (LIKELY(pagelist != 0)) { |
| newPage = pagelist->page; |
| bucket->freePages = pagelist->next; |
| partitionFree(pagelist); |
| ASSERT(page != &bucket->root->seedPage); |
| partitionLinkPage(newPage, page); |
| } else { |
| // Third. If we get here, we need a brand new page. |
| newPage = partitionAllocPage(bucket->root); |
| if (UNLIKELY(page == &bucket->root->seedPage)) { |
| // If this is the first page allocation to this bucket, then |
| // fully replace the seed page. This avoids pointlessly iterating |
| // over it. |
| newPage->prev = newPage; |
| newPage->next = newPage; |
| } else { |
| partitionLinkPage(newPage, page); |
| } |
| } |
| partitionPageInit(newPage, bucket); |
| bucket->currPage = newPage; |
| |
| return reinterpret_cast<char*>(newPage) + sizeof(PartitionPageHeader); |
| } |
| |
| void partitionFreeSlowPath(PartitionPageHeader* page) |
| { |
| PartitionBucket* bucket = page->bucket; |
| if (LIKELY(page->numAllocatedSlots == 0)) { |
| // Page became fully unused. |
| // If it's the current page, leave it be so that we don't bounce a page |
| // onto the free page list and immediately back out again. |
| if (LIKELY(page == bucket->currPage)) |
| return; |
| |
| partitionUnlinkPage(page); |
| partitionUnusePage(page); |
| PartitionFreepagelistEntry* entry = static_cast<PartitionFreepagelistEntry*>(partitionBucketAlloc(&bucket->root->buckets[kFreePageBucket])); |
| entry->page = page; |
| entry->next = bucket->freePages; |
| bucket->freePages = entry; |
| } else { |
| // Fully used page became partially used. It must be put back on the |
| // non-full page list. |
| partitionLinkPage(page, bucket->currPage); |
| page->numAllocatedSlots = -page->numAllocatedSlots - 2; |
| ASSERT(page->numAllocatedSlots == partitionBucketSlots(bucket) - 1); |
| --bucket->numFullPages; |
| } |
| } |
| |
| void* partitionReallocGeneric(PartitionRoot* root, void* ptr, size_t oldSize, size_t newSize) |
| { |
| #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
| return realloc(ptr, newSize); |
| #else |
| size_t oldIndex = partitionAllocRoundup(oldSize) >> kBucketShift; |
| if (oldIndex > kNumBuckets) |
| oldIndex = kNumBuckets; |
| size_t newIndex = partitionAllocRoundup(newSize) >> kBucketShift; |
| if (newIndex > kNumBuckets) |
| newIndex = kNumBuckets; |
| |
| if (oldIndex == newIndex) { |
| // Same bucket. But kNumBuckets indicates the fastMalloc "bucket" so in |
| // that case we're not done; we have to forward to fastRealloc. |
| if (oldIndex == kNumBuckets) |
| return WTF::fastRealloc(ptr, newSize); |
| return ptr; |
| } |
| // This realloc cannot be resized in-place. Sadness. |
| void* ret = partitionAllocGeneric(root, newSize); |
| size_t copySize = oldSize; |
| if (newSize < oldSize) |
| copySize = newSize; |
| memcpy(ret, ptr, copySize); |
| partitionFreeGeneric(ptr, oldSize); |
| return ret; |
| #endif |
| } |
| |
| #ifndef NDEBUG |
| |
| void partitionDumpStats(const PartitionRoot& root) |
| { |
| size_t i; |
| for (i = 0; i < kNumBuckets; ++i) { |
| const PartitionBucket& bucket = root.buckets[i]; |
| if (bucket.currPage == &bucket.root->seedPage && !bucket.freePages) { |
| // Empty bucket with no freelist pages. Skip reporting it. |
| continue; |
| } |
| size_t numFreePages = 0; |
| const PartitionFreepagelistEntry* freePages = bucket.freePages; |
| while (freePages) { |
| ++numFreePages; |
| freePages = freePages->next; |
| } |
| size_t bucketSlotSize = partitionBucketSize(&bucket); |
| size_t bucketNumSlots = partitionBucketSlots(&bucket); |
| size_t numActivePages = bucket.numFullPages; |
| size_t numActiveBytes = numActivePages * bucketSlotSize * bucketNumSlots; |
| const PartitionPageHeader* page = bucket.currPage; |
| do { |
| if (page != &bucket.root->seedPage) { |
| ++numActivePages; |
| numActiveBytes += (page->numAllocatedSlots * bucketSlotSize); |
| } |
| page = page->next; |
| } while (page != bucket.currPage); |
| printf("bucket size %ld: %ld/%ld bytes, %ld free pages\n", bucketSlotSize, numActiveBytes, numActivePages * kPartitionPageSize, numFreePages); |
| } |
| } |
| #endif // !NDEBUG |
| |
| } // namespace WTF |
| |