| // Copyright (c) 2013 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "third_party/base/allocator/partition_allocator/partition_alloc.h" |
| |
| #include <string.h> |
| |
| #include "third_party/base/allocator/partition_allocator/oom.h" |
| #include "third_party/base/allocator/partition_allocator/spin_lock.h" |
| #include "third_party/base/compiler_specific.h" |
| |
| // Two partition pages are used as guard / metadata page so make sure the super |
| // page size is bigger. |
| static_assert(pdfium::base::kPartitionPageSize * 4 <= |
| pdfium::base::kSuperPageSize, |
| "ok super page size"); |
| static_assert(!(pdfium::base::kSuperPageSize % |
| pdfium::base::kPartitionPageSize), |
| "ok super page multiple"); |
| // Four system pages gives us room to hack out a still-guard-paged piece |
| // of metadata in the middle of a guard partition page. |
| static_assert(pdfium::base::kSystemPageSize * 4 <= |
| pdfium::base::kPartitionPageSize, |
| "ok partition page size"); |
| static_assert(!(pdfium::base::kPartitionPageSize % |
| pdfium::base::kSystemPageSize), |
| "ok partition page multiple"); |
| static_assert(sizeof(pdfium::base::PartitionPage) <= |
| pdfium::base::kPageMetadataSize, |
| "PartitionPage should not be too big"); |
| static_assert(sizeof(pdfium::base::PartitionBucket) <= |
| pdfium::base::kPageMetadataSize, |
| "PartitionBucket should not be too big"); |
| static_assert(sizeof(pdfium::base::PartitionSuperPageExtentEntry) <= |
| pdfium::base::kPageMetadataSize, |
| "PartitionSuperPageExtentEntry should not be too big"); |
| static_assert(pdfium::base::kPageMetadataSize * |
| pdfium::base::kNumPartitionPagesPerSuperPage <= |
| pdfium::base::kSystemPageSize, |
| "page metadata fits in hole"); |
| // Check that some of our zanier calculations worked out as expected. |
| static_assert(pdfium::base::kGenericSmallestBucket == 8, |
| "generic smallest bucket"); |
| static_assert(pdfium::base::kGenericMaxBucketed == 983040, |
| "generic max bucketed"); |
| static_assert(pdfium::base::kMaxSystemPagesPerSlotSpan < (1 << 8), |
| "System pages per slot span must be less than 128."); |
| |
| namespace pdfium { |
| namespace base { |
| |
| subtle::SpinLock PartitionRootBase::gInitializedLock; |
| bool PartitionRootBase::gInitialized = false; |
| PartitionPage PartitionRootBase::gSeedPage; |
| PartitionBucket PartitionRootBase::gPagedBucket; |
| void (*PartitionRootBase::gOomHandlingFunction)() = nullptr; |
| PartitionAllocHooks::AllocationHook* PartitionAllocHooks::allocation_hook_ = |
| nullptr; |
| PartitionAllocHooks::FreeHook* PartitionAllocHooks::free_hook_ = nullptr; |
| |
| static uint8_t PartitionBucketNumSystemPages(size_t size) { |
| // This works out reasonably for the current bucket sizes of the generic |
| // allocator, and the current values of partition page size and constants. |
| // Specifically, we have enough room to always pack the slots perfectly into |
| // some number of system pages. The only waste is the waste associated with |
| // unfaulted pages (i.e. wasted address space). |
| // TODO: we end up using a lot of system pages for very small sizes. For |
| // example, we'll use 12 system pages for slot size 24. The slot size is |
| // so small that the waste would be tiny with just 4, or 1, system pages. |
| // Later, we can investigate whether there are anti-fragmentation benefits |
| // to using fewer system pages. |
| double best_waste_ratio = 1.0f; |
| uint16_t best_pages = 0; |
| if (size > kMaxSystemPagesPerSlotSpan * kSystemPageSize) { |
| DCHECK(!(size % kSystemPageSize)); |
| best_pages = static_cast<uint16_t>(size / kSystemPageSize); |
| CHECK(best_pages < (1 << 8)); |
| return static_cast<uint8_t>(best_pages); |
| } |
| DCHECK(size <= kMaxSystemPagesPerSlotSpan * kSystemPageSize); |
| for (uint16_t i = kNumSystemPagesPerPartitionPage - 1; |
| i <= kMaxSystemPagesPerSlotSpan; ++i) { |
| size_t page_size = kSystemPageSize * i; |
| size_t num_slots = page_size / size; |
| size_t waste = page_size - (num_slots * size); |
| // Leaving a page unfaulted is not free; the page will occupy an empty page |
| // table entry. Make a simple attempt to account for that. |
| size_t num_remainder_pages = i & (kNumSystemPagesPerPartitionPage - 1); |
| size_t num_unfaulted_pages = |
| num_remainder_pages |
| ? (kNumSystemPagesPerPartitionPage - num_remainder_pages) |
| : 0; |
| waste += sizeof(void*) * num_unfaulted_pages; |
| double waste_ratio = (double)waste / (double)page_size; |
| if (waste_ratio < best_waste_ratio) { |
| best_waste_ratio = waste_ratio; |
| best_pages = i; |
| } |
| } |
| DCHECK(best_pages > 0); |
| CHECK(best_pages <= kMaxSystemPagesPerSlotSpan); |
| return static_cast<uint8_t>(best_pages); |
| } |
| |
| static void PartitionAllocBaseInit(PartitionRootBase* root) { |
| DCHECK(!root->initialized); |
| { |
| subtle::SpinLock::Guard guard(PartitionRootBase::gInitializedLock); |
| if (!PartitionRootBase::gInitialized) { |
| PartitionRootBase::gInitialized = true; |
| // We mark the seed page as free to make sure it is skipped by our |
| // logic to find a new active page. |
| PartitionRootBase::gPagedBucket.active_pages_head = |
| &PartitionRootGeneric::gSeedPage; |
| } |
| } |
| |
| root->initialized = true; |
| root->total_size_of_committed_pages = 0; |
| root->total_size_of_super_pages = 0; |
| root->total_size_of_direct_mapped_pages = 0; |
| root->next_super_page = 0; |
| root->next_partition_page = 0; |
| root->next_partition_page_end = 0; |
| root->first_extent = 0; |
| root->current_extent = 0; |
| root->direct_map_list = 0; |
| |
| memset(&root->global_empty_page_ring, '\0', |
| sizeof(root->global_empty_page_ring)); |
| root->global_empty_page_ring_index = 0; |
| |
| // This is a "magic" value so we can test if a root pointer is valid. |
| root->inverted_self = ~reinterpret_cast<uintptr_t>(root); |
| } |
| |
| static void PartitionBucketInitBase(PartitionBucket* bucket, |
| PartitionRootBase* root) { |
| bucket->active_pages_head = &PartitionRootGeneric::gSeedPage; |
| bucket->empty_pages_head = 0; |
| bucket->decommitted_pages_head = 0; |
| bucket->num_full_pages = 0; |
| bucket->num_system_pages_per_slot_span = |
| PartitionBucketNumSystemPages(bucket->slot_size); |
| } |
| |
| void PartitionAllocGlobalInit(void (*oom_handling_function)()) { |
| DCHECK(oom_handling_function); |
| PartitionRootBase::gOomHandlingFunction = oom_handling_function; |
| } |
| |
| void PartitionAllocInit(PartitionRoot* root, |
| size_t num_buckets, |
| size_t max_allocation) { |
| PartitionAllocBaseInit(root); |
| |
| root->num_buckets = num_buckets; |
| root->max_allocation = max_allocation; |
| size_t i; |
| for (i = 0; i < root->num_buckets; ++i) { |
| PartitionBucket* bucket = &root->buckets()[i]; |
| if (!i) |
| bucket->slot_size = kAllocationGranularity; |
| else |
| bucket->slot_size = i << kBucketShift; |
| PartitionBucketInitBase(bucket, root); |
| } |
| } |
| |
| void PartitionAllocGenericInit(PartitionRootGeneric* root) { |
| subtle::SpinLock::Guard guard(root->lock); |
| |
| PartitionAllocBaseInit(root); |
| |
| // Precalculate some shift and mask constants used in the hot path. |
| // Example: malloc(41) == 101001 binary. |
| // Order is 6 (1 << 6-1) == 32 is highest bit set. |
| // order_index is the next three MSB == 010 == 2. |
| // sub_order_index_mask is a mask for the remaining bits == 11 (masking to 01 |
| // for |
| // the sub_order_index). |
| size_t order; |
| for (order = 0; order <= kBitsPerSizeT; ++order) { |
| size_t order_index_shift; |
| if (order < kGenericNumBucketsPerOrderBits + 1) |
| order_index_shift = 0; |
| else |
| order_index_shift = order - (kGenericNumBucketsPerOrderBits + 1); |
| root->order_index_shifts[order] = order_index_shift; |
| size_t sub_order_index_mask; |
| if (order == kBitsPerSizeT) { |
| // This avoids invoking undefined behavior for an excessive shift. |
| sub_order_index_mask = |
| static_cast<size_t>(-1) >> (kGenericNumBucketsPerOrderBits + 1); |
| } else { |
| sub_order_index_mask = ((static_cast<size_t>(1) << order) - 1) >> |
| (kGenericNumBucketsPerOrderBits + 1); |
| } |
| root->order_sub_index_masks[order] = sub_order_index_mask; |
| } |
| |
| // Set up the actual usable buckets first. |
| // Note that typical values (i.e. min allocation size of 8) will result in |
| // pseudo buckets (size==9 etc. or more generally, size is not a multiple |
| // of the smallest allocation granularity). |
| // We avoid them in the bucket lookup map, but we tolerate them to keep the |
| // code simpler and the structures more generic. |
| size_t i, j; |
| size_t current_size = kGenericSmallestBucket; |
| size_t currentIncrement = |
| kGenericSmallestBucket >> kGenericNumBucketsPerOrderBits; |
| PartitionBucket* bucket = &root->buckets[0]; |
| for (i = 0; i < kGenericNumBucketedOrders; ++i) { |
| for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { |
| bucket->slot_size = current_size; |
| PartitionBucketInitBase(bucket, root); |
| // Disable psuedo buckets so that touching them faults. |
| if (current_size % kGenericSmallestBucket) |
| bucket->active_pages_head = 0; |
| current_size += currentIncrement; |
| ++bucket; |
| } |
| currentIncrement <<= 1; |
| } |
| DCHECK(current_size == 1 << kGenericMaxBucketedOrder); |
| DCHECK(bucket == &root->buckets[0] + kGenericNumBuckets); |
| |
| // Then set up the fast size -> bucket lookup table. |
| bucket = &root->buckets[0]; |
| PartitionBucket** bucketPtr = &root->bucket_lookups[0]; |
| for (order = 0; order <= kBitsPerSizeT; ++order) { |
| for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { |
| if (order < kGenericMinBucketedOrder) { |
| // Use the bucket of the finest granularity for malloc(0) etc. |
| *bucketPtr++ = &root->buckets[0]; |
| } else if (order > kGenericMaxBucketedOrder) { |
| *bucketPtr++ = &PartitionRootGeneric::gPagedBucket; |
| } else { |
| PartitionBucket* validBucket = bucket; |
| // Skip over invalid buckets. |
| while (validBucket->slot_size % kGenericSmallestBucket) |
| validBucket++; |
| *bucketPtr++ = validBucket; |
| bucket++; |
| } |
| } |
| } |
| DCHECK(bucket == &root->buckets[0] + kGenericNumBuckets); |
| DCHECK(bucketPtr == |
| &root->bucket_lookups[0] + |
| ((kBitsPerSizeT + 1) * kGenericNumBucketsPerOrder)); |
| // And there's one last bucket lookup that will be hit for e.g. malloc(-1), |
| // which tries to overflow to a non-existant order. |
| *bucketPtr = &PartitionRootGeneric::gPagedBucket; |
| } |
| |
| #if !defined(ARCH_CPU_64_BITS) |
| static NOINLINE void PartitionOutOfMemoryWithLotsOfUncommitedPages() { |
| OOM_CRASH(); |
| } |
| #endif |
| |
| static NOINLINE void PartitionOutOfMemory(const PartitionRootBase* root) { |
| #if !defined(ARCH_CPU_64_BITS) |
| // Check whether this OOM is due to a lot of super pages that are allocated |
| // but not committed, probably due to http://crbug.com/421387. |
| if (root->total_size_of_super_pages + |
| root->total_size_of_direct_mapped_pages - |
| root->total_size_of_committed_pages > |
| kReasonableSizeOfUnusedPages) { |
| PartitionOutOfMemoryWithLotsOfUncommitedPages(); |
| } |
| #endif |
| if (PartitionRootBase::gOomHandlingFunction) |
| (*PartitionRootBase::gOomHandlingFunction)(); |
| OOM_CRASH(); |
| } |
| |
| static NOINLINE void PartitionExcessiveAllocationSize() { |
| OOM_CRASH(); |
| } |
| |
| static NOINLINE void PartitionBucketFull() { |
| OOM_CRASH(); |
| } |
| |
| // partitionPageStateIs* |
| // Note that it's only valid to call these functions on pages found on one of |
| // the page lists. Specifically, you can't call these functions on full pages |
| // that were detached from the active list. |
| static bool ALWAYS_INLINE |
| PartitionPageStateIsActive(const PartitionPage* page) { |
| DCHECK(page != &PartitionRootGeneric::gSeedPage); |
| DCHECK(!page->page_offset); |
| return (page->num_allocated_slots > 0 && |
| (page->freelist_head || page->num_unprovisioned_slots)); |
| } |
| |
| static bool ALWAYS_INLINE PartitionPageStateIsFull(const PartitionPage* page) { |
| DCHECK(page != &PartitionRootGeneric::gSeedPage); |
| DCHECK(!page->page_offset); |
| bool ret = (page->num_allocated_slots == PartitionBucketSlots(page->bucket)); |
| if (ret) { |
| DCHECK(!page->freelist_head); |
| DCHECK(!page->num_unprovisioned_slots); |
| } |
| return ret; |
| } |
| |
| static bool ALWAYS_INLINE PartitionPageStateIsEmpty(const PartitionPage* page) { |
| DCHECK(page != &PartitionRootGeneric::gSeedPage); |
| DCHECK(!page->page_offset); |
| return (!page->num_allocated_slots && page->freelist_head); |
| } |
| |
| static bool ALWAYS_INLINE |
| PartitionPageStateIsDecommitted(const PartitionPage* page) { |
| DCHECK(page != &PartitionRootGeneric::gSeedPage); |
| DCHECK(!page->page_offset); |
| bool ret = (!page->num_allocated_slots && !page->freelist_head); |
| if (ret) { |
| DCHECK(!page->num_unprovisioned_slots); |
| DCHECK(page->empty_cache_index == -1); |
| } |
| return ret; |
| } |
| |
| static void PartitionIncreaseCommittedPages(PartitionRootBase* root, |
| size_t len) { |
| root->total_size_of_committed_pages += len; |
| DCHECK(root->total_size_of_committed_pages <= |
| root->total_size_of_super_pages + |
| root->total_size_of_direct_mapped_pages); |
| } |
| |
| static void PartitionDecreaseCommittedPages(PartitionRootBase* root, |
| size_t len) { |
| root->total_size_of_committed_pages -= len; |
| DCHECK(root->total_size_of_committed_pages <= |
| root->total_size_of_super_pages + |
| root->total_size_of_direct_mapped_pages); |
| } |
| |
| static ALWAYS_INLINE void PartitionDecommitSystemPages(PartitionRootBase* root, |
| void* address, |
| size_t length) { |
| DecommitSystemPages(address, length); |
| PartitionDecreaseCommittedPages(root, length); |
| } |
| |
| static ALWAYS_INLINE void PartitionRecommitSystemPages(PartitionRootBase* root, |
| void* address, |
| size_t length) { |
| RecommitSystemPages(address, length); |
| PartitionIncreaseCommittedPages(root, length); |
| } |
| |
| static ALWAYS_INLINE void* PartitionAllocPartitionPages( |
| PartitionRootBase* root, |
| int flags, |
| uint16_t num_partition_pages) { |
| DCHECK(!(reinterpret_cast<uintptr_t>(root->next_partition_page) % |
| kPartitionPageSize)); |
| DCHECK(!(reinterpret_cast<uintptr_t>(root->next_partition_page_end) % |
| kPartitionPageSize)); |
| DCHECK(num_partition_pages <= kNumPartitionPagesPerSuperPage); |
| size_t total_size = kPartitionPageSize * num_partition_pages; |
| size_t num_partition_pages_left = |
| (root->next_partition_page_end - root->next_partition_page) >> |
| kPartitionPageShift; |
| if (LIKELY(num_partition_pages_left >= num_partition_pages)) { |
| // In this case, we can still hand out pages from the current super page |
| // allocation. |
| char* ret = root->next_partition_page; |
| root->next_partition_page += total_size; |
| PartitionIncreaseCommittedPages(root, total_size); |
| return ret; |
| } |
| |
| // Need a new super page. We want to allocate super pages in a continguous |
| // address region as much as possible. This is important for not causing |
| // page table bloat and not fragmenting address spaces in 32 bit |
| // architectures. |
| char* requestedAddress = root->next_super_page; |
| char* super_page = reinterpret_cast<char*>(AllocPages( |
| requestedAddress, kSuperPageSize, kSuperPageSize, PageAccessible)); |
| if (UNLIKELY(!super_page)) |
| return 0; |
| |
| root->total_size_of_super_pages += kSuperPageSize; |
| PartitionIncreaseCommittedPages(root, total_size); |
| |
| root->next_super_page = super_page + kSuperPageSize; |
| char* ret = super_page + kPartitionPageSize; |
| root->next_partition_page = ret + total_size; |
| root->next_partition_page_end = root->next_super_page - kPartitionPageSize; |
| // Make the first partition page in the super page a guard page, but leave a |
| // hole in the middle. |
| // This is where we put page metadata and also a tiny amount of extent |
| // metadata. |
| SetSystemPagesInaccessible(super_page, kSystemPageSize); |
| SetSystemPagesInaccessible(super_page + (kSystemPageSize * 2), |
| kPartitionPageSize - (kSystemPageSize * 2)); |
| // Also make the last partition page a guard page. |
| SetSystemPagesInaccessible(super_page + (kSuperPageSize - kPartitionPageSize), |
| kPartitionPageSize); |
| |
| // If we were after a specific address, but didn't get it, assume that |
| // the system chose a lousy address. Here most OS'es have a default |
| // algorithm that isn't randomized. For example, most Linux |
| // distributions will allocate the mapping directly before the last |
| // successful mapping, which is far from random. So we just get fresh |
| // randomness for the next mapping attempt. |
| if (requestedAddress && requestedAddress != super_page) |
| root->next_super_page = 0; |
| |
| // We allocated a new super page so update super page metadata. |
| // First check if this is a new extent or not. |
| PartitionSuperPageExtentEntry* latest_extent = |
| reinterpret_cast<PartitionSuperPageExtentEntry*>( |
| PartitionSuperPageToMetadataArea(super_page)); |
| // By storing the root in every extent metadata object, we have a fast way |
| // to go from a pointer within the partition to the root object. |
| latest_extent->root = root; |
| // Most new extents will be part of a larger extent, and these three fields |
| // are unused, but we initialize them to 0 so that we get a clear signal |
| // in case they are accidentally used. |
| latest_extent->super_page_base = 0; |
| latest_extent->super_pages_end = 0; |
| latest_extent->next = 0; |
| |
| PartitionSuperPageExtentEntry* current_extent = root->current_extent; |
| bool isNewExtent = (super_page != requestedAddress); |
| if (UNLIKELY(isNewExtent)) { |
| if (UNLIKELY(!current_extent)) { |
| DCHECK(!root->first_extent); |
| root->first_extent = latest_extent; |
| } else { |
| DCHECK(current_extent->super_page_base); |
| current_extent->next = latest_extent; |
| } |
| root->current_extent = latest_extent; |
| latest_extent->super_page_base = super_page; |
| latest_extent->super_pages_end = super_page + kSuperPageSize; |
| } else { |
| // We allocated next to an existing extent so just nudge the size up a |
| // little. |
| DCHECK(current_extent->super_pages_end); |
| current_extent->super_pages_end += kSuperPageSize; |
| DCHECK(ret >= current_extent->super_page_base && |
| ret < current_extent->super_pages_end); |
| } |
| return ret; |
| } |
| |
| static ALWAYS_INLINE uint16_t |
| PartitionBucketPartitionPages(const PartitionBucket* bucket) { |
| return (bucket->num_system_pages_per_slot_span + |
| (kNumSystemPagesPerPartitionPage - 1)) / |
| kNumSystemPagesPerPartitionPage; |
| } |
| |
| static ALWAYS_INLINE void PartitionPageReset(PartitionPage* page) { |
| DCHECK(PartitionPageStateIsDecommitted(page)); |
| |
| page->num_unprovisioned_slots = PartitionBucketSlots(page->bucket); |
| DCHECK(page->num_unprovisioned_slots); |
| |
| page->next_page = nullptr; |
| } |
| |
| static ALWAYS_INLINE void PartitionPageSetup(PartitionPage* page, |
| PartitionBucket* bucket) { |
| // The bucket never changes. We set it up once. |
| page->bucket = bucket; |
| page->empty_cache_index = -1; |
| |
| PartitionPageReset(page); |
| |
| // If this page has just a single slot, do not set up page offsets for any |
| // page metadata other than the first one. This ensures that attempts to |
| // touch invalid page metadata fail. |
| if (page->num_unprovisioned_slots == 1) |
| return; |
| |
| uint16_t num_partition_pages = PartitionBucketPartitionPages(bucket); |
| char* page_char_ptr = reinterpret_cast<char*>(page); |
| for (uint16_t i = 1; i < num_partition_pages; ++i) { |
| page_char_ptr += kPageMetadataSize; |
| PartitionPage* secondary_page = |
| reinterpret_cast<PartitionPage*>(page_char_ptr); |
| secondary_page->page_offset = i; |
| } |
| } |
| |
| static ALWAYS_INLINE char* PartitionPageAllocAndFillFreelist( |
| PartitionPage* page) { |
| DCHECK(page != &PartitionRootGeneric::gSeedPage); |
| uint16_t num_slots = page->num_unprovisioned_slots; |
| DCHECK(num_slots); |
| PartitionBucket* bucket = page->bucket; |
| // We should only get here when _every_ slot is either used or unprovisioned. |
| // (The third state is "on the freelist". If we have a non-empty freelist, we |
| // should not get here.) |
| DCHECK(num_slots + page->num_allocated_slots == PartitionBucketSlots(bucket)); |
| // Similarly, make explicitly sure that the freelist is empty. |
| DCHECK(!page->freelist_head); |
| DCHECK(page->num_allocated_slots >= 0); |
| |
| size_t size = bucket->slot_size; |
| char* base = reinterpret_cast<char*>(PartitionPageToPointer(page)); |
| char* return_object = base + (size * page->num_allocated_slots); |
| char* firstFreelistPointer = return_object + size; |
| char* firstFreelistPointerExtent = |
| firstFreelistPointer + sizeof(PartitionFreelistEntry*); |
| // Our goal is to fault as few system pages as possible. We calculate the |
| // page containing the "end" of the returned slot, and then allow freelist |
| // pointers to be written up to the end of that page. |
| char* sub_page_limit = reinterpret_cast<char*>( |
| RoundUpToSystemPage(reinterpret_cast<size_t>(firstFreelistPointer))); |
| char* slots_limit = return_object + (size * num_slots); |
| char* freelist_limit = sub_page_limit; |
| if (UNLIKELY(slots_limit < freelist_limit)) |
| freelist_limit = slots_limit; |
| |
| uint16_t num_new_freelist_entries = 0; |
| if (LIKELY(firstFreelistPointerExtent <= freelist_limit)) { |
| // Only consider used space in the slot span. If we consider wasted |
| // space, we may get an off-by-one when a freelist pointer fits in the |
| // wasted space, but a slot does not. |
| // We know we can fit at least one freelist pointer. |
| num_new_freelist_entries = 1; |
| // Any further entries require space for the whole slot span. |
| num_new_freelist_entries += static_cast<uint16_t>( |
| (freelist_limit - firstFreelistPointerExtent) / size); |
| } |
| |
| // We always return an object slot -- that's the +1 below. |
| // We do not neccessarily create any new freelist entries, because we cross |
| // sub page boundaries frequently for large bucket sizes. |
| DCHECK(num_new_freelist_entries + 1 <= num_slots); |
| num_slots -= (num_new_freelist_entries + 1); |
| page->num_unprovisioned_slots = num_slots; |
| page->num_allocated_slots++; |
| |
| if (LIKELY(num_new_freelist_entries)) { |
| char* freelist_pointer = firstFreelistPointer; |
| PartitionFreelistEntry* entry = |
| reinterpret_cast<PartitionFreelistEntry*>(freelist_pointer); |
| page->freelist_head = entry; |
| while (--num_new_freelist_entries) { |
| freelist_pointer += size; |
| PartitionFreelistEntry* next_entry = |
| reinterpret_cast<PartitionFreelistEntry*>(freelist_pointer); |
| entry->next = PartitionFreelistMask(next_entry); |
| entry = next_entry; |
| } |
| entry->next = PartitionFreelistMask(0); |
| } else { |
| page->freelist_head = 0; |
| } |
| return return_object; |
| } |
| |
| // This helper function scans a bucket's active page list for a suitable new |
| // active page. |
| // When it finds a suitable new active page (one that has free slots and is not |
| // empty), it is set as the new active page. If there is no suitable new |
| // active page, the current active page is set to the seed page. |
| // As potential pages are scanned, they are tidied up according to their state. |
| // Empty pages are swept on to the empty page list, decommitted pages on to the |
| // decommitted page list and full pages are unlinked from any list. |
| static bool PartitionSetNewActivePage(PartitionBucket* bucket) { |
| PartitionPage* page = bucket->active_pages_head; |
| if (page == &PartitionRootBase::gSeedPage) |
| return false; |
| |
| PartitionPage* next_page; |
| |
| for (; page; page = next_page) { |
| next_page = page->next_page; |
| DCHECK(page->bucket == bucket); |
| DCHECK(page != bucket->empty_pages_head); |
| DCHECK(page != bucket->decommitted_pages_head); |
| |
| // Deal with empty and decommitted pages. |
| if (LIKELY(PartitionPageStateIsActive(page))) { |
| // This page is usable because it has freelist entries, or has |
| // unprovisioned slots we can create freelist entries from. |
| bucket->active_pages_head = page; |
| return true; |
| } |
| if (LIKELY(PartitionPageStateIsEmpty(page))) { |
| page->next_page = bucket->empty_pages_head; |
| bucket->empty_pages_head = page; |
| } else if (LIKELY(PartitionPageStateIsDecommitted(page))) { |
| page->next_page = bucket->decommitted_pages_head; |
| bucket->decommitted_pages_head = page; |
| } else { |
| DCHECK(PartitionPageStateIsFull(page)); |
| // If we get here, we found a full page. Skip over it too, and also |
| // tag it as full (via a negative value). We need it tagged so that |
| // free'ing can tell, and move it back into the active page list. |
| page->num_allocated_slots = -page->num_allocated_slots; |
| ++bucket->num_full_pages; |
| // num_full_pages is a uint16_t for efficient packing so guard against |
| // overflow to be safe. |
| if (UNLIKELY(!bucket->num_full_pages)) |
| PartitionBucketFull(); |
| // Not necessary but might help stop accidents. |
| page->next_page = 0; |
| } |
| } |
| |
| bucket->active_pages_head = &PartitionRootGeneric::gSeedPage; |
| return false; |
| } |
| |
| static ALWAYS_INLINE PartitionDirectMapExtent* partitionPageToDirectMapExtent( |
| PartitionPage* page) { |
| DCHECK(PartitionBucketIsDirectMapped(page->bucket)); |
| return reinterpret_cast<PartitionDirectMapExtent*>( |
| reinterpret_cast<char*>(page) + 3 * kPageMetadataSize); |
| } |
| |
| static ALWAYS_INLINE void PartitionPageSetRawSize(PartitionPage* page, |
| size_t size) { |
| size_t* raw_size_ptr = PartitionPageGetRawSizePtr(page); |
| if (UNLIKELY(raw_size_ptr != nullptr)) |
| *raw_size_ptr = size; |
| } |
| |
| static ALWAYS_INLINE PartitionPage* PartitionDirectMap(PartitionRootBase* root, |
| int flags, |
| size_t raw_size) { |
| size_t size = PartitionDirectMapSize(raw_size); |
| |
| // Because we need to fake looking like a super page, we need to allocate |
| // a bunch of system pages more than "size": |
| // - The first few system pages are the partition page in which the super |
| // page metadata is stored. We fault just one system page out of a partition |
| // page sized clump. |
| // - We add a trailing guard page on 32-bit (on 64-bit we rely on the |
| // massive address space plus randomization instead). |
| size_t map_size = size + kPartitionPageSize; |
| #if !defined(ARCH_CPU_64_BITS) |
| map_size += kSystemPageSize; |
| #endif |
| // Round up to the allocation granularity. |
| map_size += kPageAllocationGranularityOffsetMask; |
| map_size &= kPageAllocationGranularityBaseMask; |
| |
| // TODO: these pages will be zero-filled. Consider internalizing an |
| // allocZeroed() API so we can avoid a memset() entirely in this case. |
| char* ptr = reinterpret_cast<char*>( |
| AllocPages(0, map_size, kSuperPageSize, PageAccessible)); |
| if (UNLIKELY(!ptr)) |
| return nullptr; |
| |
| size_t committed_page_size = size + kSystemPageSize; |
| root->total_size_of_direct_mapped_pages += committed_page_size; |
| PartitionIncreaseCommittedPages(root, committed_page_size); |
| |
| char* slot = ptr + kPartitionPageSize; |
| SetSystemPagesInaccessible(ptr + (kSystemPageSize * 2), |
| kPartitionPageSize - (kSystemPageSize * 2)); |
| #if !defined(ARCH_CPU_64_BITS) |
| SetSystemPagesInaccessible(ptr, kSystemPageSize); |
| SetSystemPagesInaccessible(slot + size, kSystemPageSize); |
| #endif |
| |
| PartitionSuperPageExtentEntry* extent = |
| reinterpret_cast<PartitionSuperPageExtentEntry*>( |
| PartitionSuperPageToMetadataArea(ptr)); |
| extent->root = root; |
| // The new structures are all located inside a fresh system page so they |
| // will all be zeroed out. These DCHECKs are for documentation. |
| DCHECK(!extent->super_page_base); |
| DCHECK(!extent->super_pages_end); |
| DCHECK(!extent->next); |
| PartitionPage* page = PartitionPointerToPageNoAlignmentCheck(slot); |
| PartitionBucket* bucket = reinterpret_cast<PartitionBucket*>( |
| reinterpret_cast<char*>(page) + (kPageMetadataSize * 2)); |
| DCHECK(!page->next_page); |
| DCHECK(!page->num_allocated_slots); |
| DCHECK(!page->num_unprovisioned_slots); |
| DCHECK(!page->page_offset); |
| DCHECK(!page->empty_cache_index); |
| page->bucket = bucket; |
| page->freelist_head = reinterpret_cast<PartitionFreelistEntry*>(slot); |
| PartitionFreelistEntry* next_entry = |
| reinterpret_cast<PartitionFreelistEntry*>(slot); |
| next_entry->next = PartitionFreelistMask(0); |
| |
| DCHECK(!bucket->active_pages_head); |
| DCHECK(!bucket->empty_pages_head); |
| DCHECK(!bucket->decommitted_pages_head); |
| DCHECK(!bucket->num_system_pages_per_slot_span); |
| DCHECK(!bucket->num_full_pages); |
| bucket->slot_size = size; |
| |
| PartitionDirectMapExtent* map_extent = partitionPageToDirectMapExtent(page); |
| map_extent->map_size = map_size - kPartitionPageSize - kSystemPageSize; |
| map_extent->bucket = bucket; |
| |
| // Maintain the doubly-linked list of all direct mappings. |
| map_extent->next_extent = root->direct_map_list; |
| if (map_extent->next_extent) |
| map_extent->next_extent->prev_extent = map_extent; |
| map_extent->prev_extent = nullptr; |
| root->direct_map_list = map_extent; |
| |
| return page; |
| } |
| |
| static ALWAYS_INLINE void PartitionDirectUnmap(PartitionPage* page) { |
| PartitionRootBase* root = PartitionPageToRoot(page); |
| const PartitionDirectMapExtent* extent = partitionPageToDirectMapExtent(page); |
| size_t unmap_size = extent->map_size; |
| |
| // Maintain the doubly-linked list of all direct mappings. |
| if (extent->prev_extent) { |
| DCHECK(extent->prev_extent->next_extent == extent); |
| extent->prev_extent->next_extent = extent->next_extent; |
| } else { |
| root->direct_map_list = extent->next_extent; |
| } |
| if (extent->next_extent) { |
| DCHECK(extent->next_extent->prev_extent == extent); |
| extent->next_extent->prev_extent = extent->prev_extent; |
| } |
| |
| // Add on the size of the trailing guard page and preceeding partition |
| // page. |
| unmap_size += kPartitionPageSize + kSystemPageSize; |
| |
| size_t uncommitted_page_size = page->bucket->slot_size + kSystemPageSize; |
| PartitionDecreaseCommittedPages(root, uncommitted_page_size); |
| DCHECK(root->total_size_of_direct_mapped_pages >= uncommitted_page_size); |
| root->total_size_of_direct_mapped_pages -= uncommitted_page_size; |
| |
| DCHECK(!(unmap_size & kPageAllocationGranularityOffsetMask)); |
| |
| char* ptr = reinterpret_cast<char*>(PartitionPageToPointer(page)); |
| // Account for the mapping starting a partition page before the actual |
| // allocation address. |
| ptr -= kPartitionPageSize; |
| |
| FreePages(ptr, unmap_size); |
| } |
| |
| void* PartitionAllocSlowPath(PartitionRootBase* root, |
| int flags, |
| size_t size, |
| PartitionBucket* bucket) { |
| // The slow path is called when the freelist is empty. |
| DCHECK(!bucket->active_pages_head->freelist_head); |
| |
| PartitionPage* new_page = nullptr; |
| |
| // For the PartitionAllocGeneric API, we have a bunch of buckets marked |
| // as special cases. We bounce them through to the slow path so that we |
| // can still have a blazing fast hot path due to lack of corner-case |
| // branches. |
| bool returnNull = flags & PartitionAllocReturnNull; |
| if (UNLIKELY(PartitionBucketIsDirectMapped(bucket))) { |
| DCHECK(size > kGenericMaxBucketed); |
| DCHECK(bucket == &PartitionRootBase::gPagedBucket); |
| DCHECK(bucket->active_pages_head == &PartitionRootGeneric::gSeedPage); |
| if (size > kGenericMaxDirectMapped) { |
| if (returnNull) |
| return nullptr; |
| PartitionExcessiveAllocationSize(); |
| } |
| new_page = PartitionDirectMap(root, flags, size); |
| } else if (LIKELY(PartitionSetNewActivePage(bucket))) { |
| // First, did we find an active page in the active pages list? |
| new_page = bucket->active_pages_head; |
| DCHECK(PartitionPageStateIsActive(new_page)); |
| } else if (LIKELY(bucket->empty_pages_head != nullptr) || |
| LIKELY(bucket->decommitted_pages_head != nullptr)) { |
| // Second, look in our lists of empty and decommitted pages. |
| // Check empty pages first, which are preferred, but beware that an |
| // empty page might have been decommitted. |
| while (LIKELY((new_page = bucket->empty_pages_head) != nullptr)) { |
| DCHECK(new_page->bucket == bucket); |
| DCHECK(PartitionPageStateIsEmpty(new_page) || |
| PartitionPageStateIsDecommitted(new_page)); |
| bucket->empty_pages_head = new_page->next_page; |
| // Accept the empty page unless it got decommitted. |
| if (new_page->freelist_head) { |
| new_page->next_page = nullptr; |
| break; |
| } |
| DCHECK(PartitionPageStateIsDecommitted(new_page)); |
| new_page->next_page = bucket->decommitted_pages_head; |
| bucket->decommitted_pages_head = new_page; |
| } |
| if (UNLIKELY(!new_page) && |
| LIKELY(bucket->decommitted_pages_head != nullptr)) { |
| new_page = bucket->decommitted_pages_head; |
| DCHECK(new_page->bucket == bucket); |
| DCHECK(PartitionPageStateIsDecommitted(new_page)); |
| bucket->decommitted_pages_head = new_page->next_page; |
| void* addr = PartitionPageToPointer(new_page); |
| PartitionRecommitSystemPages(root, addr, |
| PartitionBucketBytes(new_page->bucket)); |
| PartitionPageReset(new_page); |
| } |
| DCHECK(new_page); |
| } else { |
| // Third. If we get here, we need a brand new page. |
| uint16_t num_partition_pages = PartitionBucketPartitionPages(bucket); |
| void* rawPages = |
| PartitionAllocPartitionPages(root, flags, num_partition_pages); |
| if (LIKELY(rawPages != nullptr)) { |
| new_page = PartitionPointerToPageNoAlignmentCheck(rawPages); |
| PartitionPageSetup(new_page, bucket); |
| } |
| } |
| |
| // Bail if we had a memory allocation failure. |
| if (UNLIKELY(!new_page)) { |
| DCHECK(bucket->active_pages_head == &PartitionRootGeneric::gSeedPage); |
| if (returnNull) |
| return nullptr; |
| PartitionOutOfMemory(root); |
| } |
| |
| bucket = new_page->bucket; |
| DCHECK(bucket != &PartitionRootBase::gPagedBucket); |
| bucket->active_pages_head = new_page; |
| PartitionPageSetRawSize(new_page, size); |
| |
| // If we found an active page with free slots, or an empty page, we have a |
| // usable freelist head. |
| if (LIKELY(new_page->freelist_head != nullptr)) { |
| PartitionFreelistEntry* entry = new_page->freelist_head; |
| PartitionFreelistEntry* new_head = PartitionFreelistMask(entry->next); |
| new_page->freelist_head = new_head; |
| new_page->num_allocated_slots++; |
| return entry; |
| } |
| // Otherwise, we need to build the freelist. |
| DCHECK(new_page->num_unprovisioned_slots); |
| return PartitionPageAllocAndFillFreelist(new_page); |
| } |
| |
| static ALWAYS_INLINE void PartitionDecommitPage(PartitionRootBase* root, |
| PartitionPage* page) { |
| DCHECK(PartitionPageStateIsEmpty(page)); |
| DCHECK(!PartitionBucketIsDirectMapped(page->bucket)); |
| void* addr = PartitionPageToPointer(page); |
| PartitionDecommitSystemPages(root, addr, PartitionBucketBytes(page->bucket)); |
| |
| // We actually leave the decommitted page in the active list. We'll sweep |
| // it on to the decommitted page list when we next walk the active page |
| // list. |
| // Pulling this trick enables us to use a singly-linked page list for all |
| // cases, which is critical in keeping the page metadata structure down to |
| // 32 bytes in size. |
| page->freelist_head = 0; |
| page->num_unprovisioned_slots = 0; |
| DCHECK(PartitionPageStateIsDecommitted(page)); |
| } |
| |
| static void PartitionDecommitPageIfPossible(PartitionRootBase* root, |
| PartitionPage* page) { |
| DCHECK(page->empty_cache_index >= 0); |
| DCHECK(static_cast<unsigned>(page->empty_cache_index) < kMaxFreeableSpans); |
| DCHECK(page == root->global_empty_page_ring[page->empty_cache_index]); |
| page->empty_cache_index = -1; |
| if (PartitionPageStateIsEmpty(page)) |
| PartitionDecommitPage(root, page); |
| } |
| |
| static ALWAYS_INLINE void PartitionRegisterEmptyPage(PartitionPage* page) { |
| DCHECK(PartitionPageStateIsEmpty(page)); |
| PartitionRootBase* root = PartitionPageToRoot(page); |
| |
| // If the page is already registered as empty, give it another life. |
| if (page->empty_cache_index != -1) { |
| DCHECK(page->empty_cache_index >= 0); |
| DCHECK(static_cast<unsigned>(page->empty_cache_index) < kMaxFreeableSpans); |
| DCHECK(root->global_empty_page_ring[page->empty_cache_index] == page); |
| root->global_empty_page_ring[page->empty_cache_index] = 0; |
| } |
| |
| int16_t current_index = root->global_empty_page_ring_index; |
| PartitionPage* pageToDecommit = root->global_empty_page_ring[current_index]; |
| // The page might well have been re-activated, filled up, etc. before we get |
| // around to looking at it here. |
| if (pageToDecommit) |
| PartitionDecommitPageIfPossible(root, pageToDecommit); |
| |
| // We put the empty slot span on our global list of "pages that were once |
| // empty". thus providing it a bit of breathing room to get re-used before |
| // we really free it. This improves performance, particularly on Mac OS X |
| // which has subpar memory management performance. |
| root->global_empty_page_ring[current_index] = page; |
| page->empty_cache_index = current_index; |
| ++current_index; |
| if (current_index == kMaxFreeableSpans) |
| current_index = 0; |
| root->global_empty_page_ring_index = current_index; |
| } |
| |
| static void PartitionDecommitEmptyPages(PartitionRootBase* root) { |
| for (size_t i = 0; i < kMaxFreeableSpans; ++i) { |
| PartitionPage* page = root->global_empty_page_ring[i]; |
| if (page) |
| PartitionDecommitPageIfPossible(root, page); |
| root->global_empty_page_ring[i] = nullptr; |
| } |
| } |
| |
| void PartitionFreeSlowPath(PartitionPage* page) { |
| PartitionBucket* bucket = page->bucket; |
| DCHECK(page != &PartitionRootGeneric::gSeedPage); |
| if (LIKELY(page->num_allocated_slots == 0)) { |
| // Page became fully unused. |
| if (UNLIKELY(PartitionBucketIsDirectMapped(bucket))) { |
| PartitionDirectUnmap(page); |
| return; |
| } |
| // If it's the current active page, change it. We bounce the page to |
| // the empty list as a force towards defragmentation. |
| if (LIKELY(page == bucket->active_pages_head)) |
| (void)PartitionSetNewActivePage(bucket); |
| DCHECK(bucket->active_pages_head != page); |
| |
| PartitionPageSetRawSize(page, 0); |
| DCHECK(!PartitionPageGetRawSize(page)); |
| |
| PartitionRegisterEmptyPage(page); |
| } else { |
| DCHECK(!PartitionBucketIsDirectMapped(bucket)); |
| // Ensure that the page is full. That's the only valid case if we |
| // arrive here. |
| DCHECK(page->num_allocated_slots < 0); |
| // A transition of num_allocated_slots from 0 to -1 is not legal, and |
| // likely indicates a double-free. |
| CHECK(page->num_allocated_slots != -1); |
| page->num_allocated_slots = -page->num_allocated_slots - 2; |
| DCHECK(page->num_allocated_slots == PartitionBucketSlots(bucket) - 1); |
| // Fully used page became partially used. It must be put back on the |
| // non-full page list. Also make it the current page to increase the |
| // chances of it being filled up again. The old current page will be |
| // the next page. |
| DCHECK(!page->next_page); |
| if (LIKELY(bucket->active_pages_head != &PartitionRootGeneric::gSeedPage)) |
| page->next_page = bucket->active_pages_head; |
| bucket->active_pages_head = page; |
| --bucket->num_full_pages; |
| // Special case: for a partition page with just a single slot, it may |
| // now be empty and we want to run it through the empty logic. |
| if (UNLIKELY(page->num_allocated_slots == 0)) |
| PartitionFreeSlowPath(page); |
| } |
| } |
| |
| bool partitionReallocDirectMappedInPlace(PartitionRootGeneric* root, |
| PartitionPage* page, |
| size_t raw_size) { |
| DCHECK(PartitionBucketIsDirectMapped(page->bucket)); |
| |
| raw_size = PartitionCookieSizeAdjustAdd(raw_size); |
| |
| // Note that the new size might be a bucketed size; this function is called |
| // whenever we're reallocating a direct mapped allocation. |
| size_t new_size = PartitionDirectMapSize(raw_size); |
| if (new_size < kGenericMinDirectMappedDownsize) |
| return false; |
| |
| // bucket->slot_size is the current size of the allocation. |
| size_t current_size = page->bucket->slot_size; |
| if (new_size == current_size) |
| return true; |
| |
| char* char_ptr = static_cast<char*>(PartitionPageToPointer(page)); |
| |
| if (new_size < current_size) { |
| size_t map_size = partitionPageToDirectMapExtent(page)->map_size; |
| |
| // Don't reallocate in-place if new size is less than 80 % of the full |
| // map size, to avoid holding on to too much unused address space. |
| if ((new_size / kSystemPageSize) * 5 < (map_size / kSystemPageSize) * 4) |
| return false; |
| |
| // Shrink by decommitting unneeded pages and making them inaccessible. |
| size_t decommitSize = current_size - new_size; |
| PartitionDecommitSystemPages(root, char_ptr + new_size, decommitSize); |
| SetSystemPagesInaccessible(char_ptr + new_size, decommitSize); |
| } else if (new_size <= partitionPageToDirectMapExtent(page)->map_size) { |
| // Grow within the actually allocated memory. Just need to make the |
| // pages accessible again. |
| size_t recommit_size = new_size - current_size; |
| bool ret = SetSystemPagesAccessible(char_ptr + current_size, recommit_size); |
| CHECK(ret); |
| PartitionRecommitSystemPages(root, char_ptr + current_size, recommit_size); |
| |
| #if DCHECK_IS_ON() |
| memset(char_ptr + current_size, kUninitializedByte, recommit_size); |
| #endif |
| } else { |
| // We can't perform the realloc in-place. |
| // TODO: support this too when possible. |
| return false; |
| } |
| |
| #if DCHECK_IS_ON() |
| // Write a new trailing cookie. |
| PartitionCookieWriteValue(char_ptr + raw_size - kCookieSize); |
| #endif |
| |
| PartitionPageSetRawSize(page, raw_size); |
| DCHECK(PartitionPageGetRawSize(page) == raw_size); |
| |
| page->bucket->slot_size = new_size; |
| return true; |
| } |
| |
| void* PartitionReallocGenericFlags(PartitionRootGeneric* root, |
| int flags, |
| void* ptr, |
| size_t new_size, |
| const char* type_name) { |
| #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
| void* result = realloc(ptr, new_size); |
| CHECK(result || flags & PartitionAllocReturnNull); |
| return result; |
| #else |
| if (UNLIKELY(!ptr)) |
| return PartitionAllocGenericFlags(root, flags, new_size, type_name); |
| if (UNLIKELY(!new_size)) { |
| PartitionFreeGeneric(root, ptr); |
| return nullptr; |
| } |
| |
| if (new_size > kGenericMaxDirectMapped) { |
| if (flags & PartitionAllocReturnNull) |
| return nullptr; |
| else |
| PartitionExcessiveAllocationSize(); |
| } |
| |
| DCHECK(PartitionPointerIsValid(PartitionCookieFreePointerAdjust(ptr))); |
| |
| PartitionPage* page = |
| PartitionPointerToPage(PartitionCookieFreePointerAdjust(ptr)); |
| |
| if (UNLIKELY(PartitionBucketIsDirectMapped(page->bucket))) { |
| // We may be able to perform the realloc in place by changing the |
| // accessibility of memory pages and, if reducing the size, decommitting |
| // them. |
| if (partitionReallocDirectMappedInPlace(root, page, new_size)) { |
| PartitionAllocHooks::ReallocHookIfEnabled(ptr, ptr, new_size, type_name); |
| return ptr; |
| } |
| } |
| |
| size_t actual_new_size = PartitionAllocActualSize(root, new_size); |
| size_t actual_old_size = PartitionAllocGetSize(ptr); |
| |
| // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the |
| // new size is a significant percentage smaller. We could do the same if we |
| // determine it is a win. |
| if (actual_new_size == actual_old_size) { |
| // Trying to allocate a block of size new_size would give us a block of |
| // the same size as the one we've already got, so re-use the allocation |
| // after updating statistics (and cookies, if present). |
| PartitionPageSetRawSize(page, PartitionCookieSizeAdjustAdd(new_size)); |
| #if DCHECK_IS_ON() |
| // Write a new trailing cookie when it is possible to keep track of |
| // |new_size| via the raw size pointer. |
| if (PartitionPageGetRawSizePtr(page)) |
| PartitionCookieWriteValue(static_cast<char*>(ptr) + new_size); |
| #endif // DCHECK_IS_ON() |
| return ptr; |
| } |
| |
| // This realloc cannot be resized in-place. Sadness. |
| void* ret = PartitionAllocGenericFlags(root, flags, new_size, type_name); |
| if (!ret) { |
| if (flags & PartitionAllocReturnNull) |
| return nullptr; |
| else |
| PartitionExcessiveAllocationSize(); |
| } |
| |
| size_t copy_size = actual_old_size; |
| if (new_size < copy_size) |
| copy_size = new_size; |
| |
| memcpy(ret, ptr, copy_size); |
| PartitionFreeGeneric(root, ptr); |
| return ret; |
| #endif // defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
| } |
| |
| void* PartitionReallocGeneric(PartitionRootGeneric* root, |
| void* ptr, |
| size_t new_size, |
| const char* type_name) { |
| return PartitionReallocGenericFlags(root, 0, ptr, new_size, type_name); |
| } |
| |
| static size_t PartitionPurgePage(PartitionPage* page, bool discard) { |
| const PartitionBucket* bucket = page->bucket; |
| size_t slot_size = bucket->slot_size; |
| if (slot_size < kSystemPageSize || !page->num_allocated_slots) |
| return 0; |
| |
| size_t bucket_num_slots = PartitionBucketSlots(bucket); |
| size_t discardable_bytes = 0; |
| |
| size_t raw_size = PartitionPageGetRawSize(const_cast<PartitionPage*>(page)); |
| if (raw_size) { |
| uint32_t usedBytes = static_cast<uint32_t>(RoundUpToSystemPage(raw_size)); |
| discardable_bytes = bucket->slot_size - usedBytes; |
| if (discardable_bytes && discard) { |
| char* ptr = reinterpret_cast<char*>(PartitionPageToPointer(page)); |
| ptr += usedBytes; |
| DiscardSystemPages(ptr, discardable_bytes); |
| } |
| return discardable_bytes; |
| } |
| |
| const size_t max_slot_count = |
| (kPartitionPageSize * kMaxPartitionPagesPerSlotSpan) / kSystemPageSize; |
| DCHECK(bucket_num_slots <= max_slot_count); |
| DCHECK(page->num_unprovisioned_slots < bucket_num_slots); |
| size_t num_slots = bucket_num_slots - page->num_unprovisioned_slots; |
| char slot_usage[max_slot_count]; |
| size_t last_slot = static_cast<size_t>(-1); |
| memset(slot_usage, 1, num_slots); |
| char* ptr = reinterpret_cast<char*>(PartitionPageToPointer(page)); |
| PartitionFreelistEntry* entry = page->freelist_head; |
| // First, walk the freelist for this page and make a bitmap of which slots |
| // are not in use. |
| while (entry) { |
| size_t slotIndex = (reinterpret_cast<char*>(entry) - ptr) / slot_size; |
| DCHECK(slotIndex < num_slots); |
| slot_usage[slotIndex] = 0; |
| entry = PartitionFreelistMask(entry->next); |
| // If we have a slot where the masked freelist entry is 0, we can |
| // actually discard that freelist entry because touching a discarded |
| // page is guaranteed to return original content or 0. |
| // (Note that this optimization won't fire on big endian machines |
| // because the masking function is negation.) |
| if (!PartitionFreelistMask(entry)) |
| last_slot = slotIndex; |
| } |
| |
| // If the slot(s) at the end of the slot span are not in used, we can |
| // truncate them entirely and rewrite the freelist. |
| size_t truncated_slots = 0; |
| while (!slot_usage[num_slots - 1]) { |
| truncated_slots++; |
| num_slots--; |
| DCHECK(num_slots); |
| } |
| // First, do the work of calculating the discardable bytes. Don't actually |
| // discard anything unless the discard flag was passed in. |
| char* begin_ptr = nullptr; |
| char* end_ptr = nullptr; |
| size_t unprovisioned_bytes = 0; |
| if (truncated_slots) { |
| begin_ptr = ptr + (num_slots * slot_size); |
| end_ptr = begin_ptr + (slot_size * truncated_slots); |
| begin_ptr = reinterpret_cast<char*>( |
| RoundUpToSystemPage(reinterpret_cast<size_t>(begin_ptr))); |
| // We round the end pointer here up and not down because we're at the |
| // end of a slot span, so we "own" all the way up the page boundary. |
| end_ptr = reinterpret_cast<char*>( |
| RoundUpToSystemPage(reinterpret_cast<size_t>(end_ptr))); |
| DCHECK(end_ptr <= ptr + PartitionBucketBytes(bucket)); |
| if (begin_ptr < end_ptr) { |
| unprovisioned_bytes = end_ptr - begin_ptr; |
| discardable_bytes += unprovisioned_bytes; |
| } |
| } |
| if (unprovisioned_bytes && discard) { |
| DCHECK(truncated_slots > 0); |
| size_t num_new_entries = 0; |
| page->num_unprovisioned_slots += static_cast<uint16_t>(truncated_slots); |
| // Rewrite the freelist. |
| PartitionFreelistEntry** entry_ptr = &page->freelist_head; |
| for (size_t slotIndex = 0; slotIndex < num_slots; ++slotIndex) { |
| if (slot_usage[slotIndex]) |
| continue; |
| PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*>( |
| ptr + (slot_size * slotIndex)); |
| *entry_ptr = PartitionFreelistMask(entry); |
| entry_ptr = reinterpret_cast<PartitionFreelistEntry**>(entry); |
| num_new_entries++; |
| } |
| // Terminate the freelist chain. |
| *entry_ptr = nullptr; |
| // The freelist head is stored unmasked. |
| page->freelist_head = PartitionFreelistMask(page->freelist_head); |
| DCHECK(num_new_entries == num_slots - page->num_allocated_slots); |
| // Discard the memory. |
| DiscardSystemPages(begin_ptr, unprovisioned_bytes); |
| } |
| |
| // Next, walk the slots and for any not in use, consider where the system |
| // page boundaries occur. We can release any system pages back to the |
| // system as long as we don't interfere with a freelist pointer or an |
| // adjacent slot. |
| for (size_t i = 0; i < num_slots; ++i) { |
| if (slot_usage[i]) |
| continue; |
| // The first address we can safely discard is just after the freelist |
| // pointer. There's one quirk: if the freelist pointer is actually a |
| // null, we can discard that pointer value too. |
| char* begin_ptr = ptr + (i * slot_size); |
| char* end_ptr = begin_ptr + slot_size; |
| if (i != last_slot) |
| begin_ptr += sizeof(PartitionFreelistEntry); |
| begin_ptr = reinterpret_cast<char*>( |
| RoundUpToSystemPage(reinterpret_cast<size_t>(begin_ptr))); |
| end_ptr = reinterpret_cast<char*>( |
| RoundDownToSystemPage(reinterpret_cast<size_t>(end_ptr))); |
| if (begin_ptr < end_ptr) { |
| size_t partial_slot_bytes = end_ptr - begin_ptr; |
| discardable_bytes += partial_slot_bytes; |
| if (discard) |
| DiscardSystemPages(begin_ptr, partial_slot_bytes); |
| } |
| } |
| return discardable_bytes; |
| } |
| |
| static void PartitionPurgeBucket(PartitionBucket* bucket) { |
| if (bucket->active_pages_head != &PartitionRootGeneric::gSeedPage) { |
| for (PartitionPage* page = bucket->active_pages_head; page; |
| page = page->next_page) { |
| DCHECK(page != &PartitionRootGeneric::gSeedPage); |
| (void)PartitionPurgePage(page, true); |
| } |
| } |
| } |
| |
| void PartitionPurgeMemory(PartitionRoot* root, int flags) { |
| if (flags & PartitionPurgeDecommitEmptyPages) |
| PartitionDecommitEmptyPages(root); |
| // We don't currently do anything for PartitionPurgeDiscardUnusedSystemPages |
| // here because that flag is only useful for allocations >= system page |
| // size. We only have allocations that large inside generic partitions |
| // at the moment. |
| } |
| |
| void PartitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags) { |
| subtle::SpinLock::Guard guard(root->lock); |
| if (flags & PartitionPurgeDecommitEmptyPages) |
| PartitionDecommitEmptyPages(root); |
| if (flags & PartitionPurgeDiscardUnusedSystemPages) { |
| for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
| PartitionBucket* bucket = &root->buckets[i]; |
| if (bucket->slot_size >= kSystemPageSize) |
| PartitionPurgeBucket(bucket); |
| } |
| } |
| } |
| |
| static void PartitionDumpPageStats(PartitionBucketMemoryStats* stats_out, |
| const PartitionPage* page) { |
| uint16_t bucket_num_slots = PartitionBucketSlots(page->bucket); |
| |
| if (PartitionPageStateIsDecommitted(page)) { |
| ++stats_out->num_decommitted_pages; |
| return; |
| } |
| |
| stats_out->discardable_bytes += |
| PartitionPurgePage(const_cast<PartitionPage*>(page), false); |
| |
| size_t raw_size = PartitionPageGetRawSize(const_cast<PartitionPage*>(page)); |
| if (raw_size) |
| stats_out->active_bytes += static_cast<uint32_t>(raw_size); |
| else |
| stats_out->active_bytes += |
| (page->num_allocated_slots * stats_out->bucket_slot_size); |
| |
| size_t page_bytes_resident = |
| RoundUpToSystemPage((bucket_num_slots - page->num_unprovisioned_slots) * |
| stats_out->bucket_slot_size); |
| stats_out->resident_bytes += page_bytes_resident; |
| if (PartitionPageStateIsEmpty(page)) { |
| stats_out->decommittable_bytes += page_bytes_resident; |
| ++stats_out->num_empty_pages; |
| } else if (PartitionPageStateIsFull(page)) { |
| ++stats_out->num_full_pages; |
| } else { |
| DCHECK(PartitionPageStateIsActive(page)); |
| ++stats_out->num_active_pages; |
| } |
| } |
| |
| static void PartitionDumpBucketStats(PartitionBucketMemoryStats* stats_out, |
| const PartitionBucket* bucket) { |
| DCHECK(!PartitionBucketIsDirectMapped(bucket)); |
| stats_out->is_valid = false; |
| // If the active page list is empty (== &PartitionRootGeneric::gSeedPage), |
| // the bucket might still need to be reported if it has a list of empty, |
| // decommitted or full pages. |
| if (bucket->active_pages_head == &PartitionRootGeneric::gSeedPage && |
| !bucket->empty_pages_head && !bucket->decommitted_pages_head && |
| !bucket->num_full_pages) |
| return; |
| |
| memset(stats_out, '\0', sizeof(*stats_out)); |
| stats_out->is_valid = true; |
| stats_out->is_direct_map = false; |
| stats_out->num_full_pages = static_cast<size_t>(bucket->num_full_pages); |
| stats_out->bucket_slot_size = bucket->slot_size; |
| uint16_t bucket_num_slots = PartitionBucketSlots(bucket); |
| size_t bucket_useful_storage = stats_out->bucket_slot_size * bucket_num_slots; |
| stats_out->allocated_page_size = PartitionBucketBytes(bucket); |
| stats_out->active_bytes = bucket->num_full_pages * bucket_useful_storage; |
| stats_out->resident_bytes = |
| bucket->num_full_pages * stats_out->allocated_page_size; |
| |
| for (const PartitionPage* page = bucket->empty_pages_head; page; |
| page = page->next_page) { |
| DCHECK(PartitionPageStateIsEmpty(page) || |
| PartitionPageStateIsDecommitted(page)); |
| PartitionDumpPageStats(stats_out, page); |
| } |
| for (const PartitionPage* page = bucket->decommitted_pages_head; page; |
| page = page->next_page) { |
| DCHECK(PartitionPageStateIsDecommitted(page)); |
| PartitionDumpPageStats(stats_out, page); |
| } |
| |
| if (bucket->active_pages_head != &PartitionRootGeneric::gSeedPage) { |
| for (const PartitionPage* page = bucket->active_pages_head; page; |
| page = page->next_page) { |
| DCHECK(page != &PartitionRootGeneric::gSeedPage); |
| PartitionDumpPageStats(stats_out, page); |
| } |
| } |
| } |
| |
| void PartitionDumpStatsGeneric(PartitionRootGeneric* partition, |
| const char* partition_name, |
| bool is_light_dump, |
| PartitionStatsDumper* dumper) { |
| PartitionMemoryStats stats = {0}; |
| stats.total_mmapped_bytes = partition->total_size_of_super_pages + |
| partition->total_size_of_direct_mapped_pages; |
| stats.total_committed_bytes = partition->total_size_of_committed_pages; |
| |
| size_t direct_mapped_allocations_total_size = 0; |
| |
| static const size_t kMaxReportableDirectMaps = 4096; |
| |
| // Allocate on the heap rather than on the stack to avoid stack overflow |
| // skirmishes (on Windows, in particular). |
| std::unique_ptr<uint32_t[]> direct_map_lengths = nullptr; |
| if (!is_light_dump) { |
| direct_map_lengths = |
| std::unique_ptr<uint32_t[]>(new uint32_t[kMaxReportableDirectMaps]); |
| } |
| |
| PartitionBucketMemoryStats bucket_stats[kGenericNumBuckets]; |
| size_t num_direct_mapped_allocations = 0; |
| { |
| subtle::SpinLock::Guard guard(partition->lock); |
| |
| for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
| const PartitionBucket* bucket = &partition->buckets[i]; |
| // Don't report the pseudo buckets that the generic allocator sets up in |
| // order to preserve a fast size->bucket map (see |
| // PartitionAllocGenericInit for details). |
| if (!bucket->active_pages_head) |
| bucket_stats[i].is_valid = false; |
| else |
| PartitionDumpBucketStats(&bucket_stats[i], bucket); |
| if (bucket_stats[i].is_valid) { |
| stats.total_resident_bytes += bucket_stats[i].resident_bytes; |
| stats.total_active_bytes += bucket_stats[i].active_bytes; |
| stats.total_decommittable_bytes += bucket_stats[i].decommittable_bytes; |
| stats.total_discardable_bytes += bucket_stats[i].discardable_bytes; |
| } |
| } |
| |
| for (PartitionDirectMapExtent *extent = partition->direct_map_list; |
| extent && num_direct_mapped_allocations < kMaxReportableDirectMaps; |
| extent = extent->next_extent, ++num_direct_mapped_allocations) { |
| DCHECK(!extent->next_extent || |
| extent->next_extent->prev_extent == extent); |
| size_t slot_size = extent->bucket->slot_size; |
| direct_mapped_allocations_total_size += slot_size; |
| if (is_light_dump) |
| continue; |
| direct_map_lengths[num_direct_mapped_allocations] = slot_size; |
| } |
| } |
| |
| if (!is_light_dump) { |
| // Call |PartitionsDumpBucketStats| after collecting stats because it can |
| // try to allocate using |PartitionAllocGeneric| and it can't obtain the |
| // lock. |
| for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
| if (bucket_stats[i].is_valid) |
| dumper->PartitionsDumpBucketStats(partition_name, &bucket_stats[i]); |
| } |
| |
| for (size_t i = 0; i < num_direct_mapped_allocations; ++i) { |
| uint32_t size = direct_map_lengths[i]; |
| |
| PartitionBucketMemoryStats stats; |
| memset(&stats, '\0', sizeof(stats)); |
| stats.is_valid = true; |
| stats.is_direct_map = true; |
| stats.num_full_pages = 1; |
| stats.allocated_page_size = size; |
| stats.bucket_slot_size = size; |
| stats.active_bytes = size; |
| stats.resident_bytes = size; |
| dumper->PartitionsDumpBucketStats(partition_name, &stats); |
| } |
| } |
| |
| stats.total_resident_bytes += direct_mapped_allocations_total_size; |
| stats.total_active_bytes += direct_mapped_allocations_total_size; |
| dumper->PartitionDumpTotals(partition_name, &stats); |
| } |
| |
| void PartitionDumpStats(PartitionRoot* partition, |
| const char* partition_name, |
| bool is_light_dump, |
| PartitionStatsDumper* dumper) { |
| static const size_t kMaxReportableBuckets = 4096 / sizeof(void*); |
| PartitionBucketMemoryStats memory_stats[kMaxReportableBuckets]; |
| const size_t partitionNumBuckets = partition->num_buckets; |
| DCHECK(partitionNumBuckets <= kMaxReportableBuckets); |
| |
| for (size_t i = 0; i < partitionNumBuckets; ++i) |
| PartitionDumpBucketStats(&memory_stats[i], &partition->buckets()[i]); |
| |
| // PartitionsDumpBucketStats is called after collecting stats because it |
| // can use PartitionAlloc to allocate and this can affect the statistics. |
| PartitionMemoryStats stats = {0}; |
| stats.total_mmapped_bytes = partition->total_size_of_super_pages; |
| stats.total_committed_bytes = partition->total_size_of_committed_pages; |
| DCHECK(!partition->total_size_of_direct_mapped_pages); |
| for (size_t i = 0; i < partitionNumBuckets; ++i) { |
| if (memory_stats[i].is_valid) { |
| stats.total_resident_bytes += memory_stats[i].resident_bytes; |
| stats.total_active_bytes += memory_stats[i].active_bytes; |
| stats.total_decommittable_bytes += memory_stats[i].decommittable_bytes; |
| stats.total_discardable_bytes += memory_stats[i].discardable_bytes; |
| if (!is_light_dump) |
| dumper->PartitionsDumpBucketStats(partition_name, &memory_stats[i]); |
| } |
| } |
| dumper->PartitionDumpTotals(partition_name, &stats); |
| } |
| |
| } // namespace base |
| } // namespace pdfium |