diff options
Diffstat (limited to 'third_party/base/allocator/partition_allocator/partition_alloc.h')
| -rw-r--r-- | third_party/base/allocator/partition_allocator/partition_alloc.h | 794 |
1 files changed, 170 insertions, 624 deletions
diff --git a/third_party/base/allocator/partition_allocator/partition_alloc.h b/third_party/base/allocator/partition_allocator/partition_alloc.h index 69fba97d62..a80755c510 100644 --- a/third_party/base/allocator/partition_allocator/partition_alloc.h +++ b/third_party/base/allocator/partition_allocator/partition_alloc.h @@ -2,12 +2,13 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -#ifndef BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H -#define BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H +#ifndef THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H_ +#define THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H_ // DESCRIPTION -// partitionAlloc() / PartitionAllocGeneric() and PartitionFree() / -// PartitionFreeGeneric() are approximately analagous to malloc() and free(). +// PartitionRoot::Alloc() / PartitionRootGeneric::Alloc() and PartitionFree() / +// PartitionRootGeneric::Free() are approximately analagous to malloc() and +// free(). // // The main difference is that a PartitionRoot / PartitionRootGeneric object // must be supplied to these functions, representing a specific "heap partition" @@ -23,14 +24,14 @@ // PartitionRoot is really just a header adjacent to other data areas provided // by the allocator class. // -// The partitionAlloc() variant of the API has the following caveats: +// The PartitionRoot::Alloc() variant of the API has the following caveats: // - Allocations and frees against a single partition must be single threaded. // - Allocations must not exceed a max size, chosen at compile-time via a // templated parameter to PartitionAllocator. // - Allocation sizes must be aligned to the system pointer size. // - Allocations are bucketed exactly according to size. // -// And for PartitionAllocGeneric(): +// And for PartitionRootGeneric::Alloc(): // - Multi-threaded use against a single partition is ok; locking is handled. // - Allocations of any arbitrary size can be handled (subject to a limit of // INT_MAX bytes for security reasons). @@ -64,10 +65,17 @@ #include "build/build_config.h" #include "third_party/base/allocator/partition_allocator/page_allocator.h" +#include "third_party/base/allocator/partition_allocator/partition_alloc_constants.h" +#include "third_party/base/allocator/partition_allocator/partition_bucket.h" +#include "third_party/base/allocator/partition_allocator/partition_cookie.h" +#include "third_party/base/allocator/partition_allocator/partition_page.h" +#include "third_party/base/allocator/partition_allocator/partition_root_base.h" #include "third_party/base/allocator/partition_allocator/spin_lock.h" +#include "third_party/base/base_export.h" #include "third_party/base/bits.h" #include "third_party/base/compiler_specific.h" #include "third_party/base/logging.h" +#include "third_party/base/stl_util.h" #include "third_party/base/sys_byteorder.h" #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) @@ -77,289 +85,83 @@ namespace pdfium { namespace base { -// Allocation granularity of sizeof(void*) bytes. -static const size_t kAllocationGranularity = sizeof(void*); -static const size_t kAllocationGranularityMask = kAllocationGranularity - 1; -static const size_t kBucketShift = (kAllocationGranularity == 8) ? 3 : 2; - -// Underlying partition storage pages are a power-of-two size. It is typical -// for a partition page to be based on multiple system pages. Most references to -// "page" refer to partition pages. -// We also have the concept of "super pages" -- these are the underlying system -// allocations we make. Super pages contain multiple partition pages inside them -// and include space for a small amount of metadata per partition page. -// Inside super pages, we store "slot spans". A slot span is a continguous range -// of one or more partition pages that stores allocations of the same size. -// Slot span sizes are adjusted depending on the allocation size, to make sure -// the packing does not lead to unused (wasted) space at the end of the last -// system page of the span. For our current max slot span size of 64k and other -// constant values, we pack _all_ PartitionAllocGeneric() sizes perfectly up -// against the end of a system page. -#if defined(_MIPS_ARCH_LOONGSON) -static const size_t kPartitionPageShift = 16; // 64KB -#else -static const size_t kPartitionPageShift = 14; // 16KB -#endif -static const size_t kPartitionPageSize = 1 << kPartitionPageShift; -static const size_t kPartitionPageOffsetMask = kPartitionPageSize - 1; -static const size_t kPartitionPageBaseMask = ~kPartitionPageOffsetMask; -static const size_t kMaxPartitionPagesPerSlotSpan = 4; - -// To avoid fragmentation via never-used freelist entries, we hand out partition -// freelist sections gradually, in units of the dominant system page size. -// What we're actually doing is avoiding filling the full partition page (16 KB) -// with freelist pointers right away. Writing freelist pointers will fault and -// dirty a private page, which is very wasteful if we never actually store -// objects there. -static const size_t kNumSystemPagesPerPartitionPage = - kPartitionPageSize / kSystemPageSize; -static const size_t kMaxSystemPagesPerSlotSpan = - kNumSystemPagesPerPartitionPage * kMaxPartitionPagesPerSlotSpan; - -// We reserve virtual address space in 2MB chunks (aligned to 2MB as well). -// These chunks are called "super pages". We do this so that we can store -// metadata in the first few pages of each 2MB aligned section. This leads to -// a very fast free(). We specifically choose 2MB because this virtual address -// block represents a full but single PTE allocation on ARM, ia32 and x64. -// -// The layout of the super page is as follows. The sizes below are the same -// for 32 bit and 64 bit. -// -// | Guard page (4KB) | -// | Metadata page (4KB) | -// | Guard pages (8KB) | -// | Slot span | -// | Slot span | -// | ... | -// | Slot span | -// | Guard page (4KB) | -// -// - Each slot span is a contiguous range of one or more PartitionPages. -// - The metadata page has the following format. Note that the PartitionPage -// that is not at the head of a slot span is "unused". In other words, -// the metadata for the slot span is stored only in the first PartitionPage -// of the slot span. Metadata accesses to other PartitionPages are -// redirected to the first PartitionPage. -// -// | SuperPageExtentEntry (32B) | -// | PartitionPage of slot span 1 (32B, used) | -// | PartitionPage of slot span 1 (32B, unused) | -// | PartitionPage of slot span 1 (32B, unused) | -// | PartitionPage of slot span 2 (32B, used) | -// | PartitionPage of slot span 3 (32B, used) | -// | ... | -// | PartitionPage of slot span N (32B, unused) | -// -// A direct mapped page has a similar layout to fake it looking like a super -// page: -// -// | Guard page (4KB) | -// | Metadata page (4KB) | -// | Guard pages (8KB) | -// | Direct mapped object | -// | Guard page (4KB) | -// -// - The metadata page has the following layout: -// -// | SuperPageExtentEntry (32B) | -// | PartitionPage (32B) | -// | PartitionBucket (32B) | -// | PartitionDirectMapExtent (8B) | -static const size_t kSuperPageShift = 21; // 2MB -static const size_t kSuperPageSize = 1 << kSuperPageShift; -static const size_t kSuperPageOffsetMask = kSuperPageSize - 1; -static const size_t kSuperPageBaseMask = ~kSuperPageOffsetMask; -static const size_t kNumPartitionPagesPerSuperPage = - kSuperPageSize / kPartitionPageSize; - -static const size_t kPageMetadataShift = 5; // 32 bytes per partition page. -static const size_t kPageMetadataSize = 1 << kPageMetadataShift; - -// The following kGeneric* constants apply to the generic variants of the API. -// The "order" of an allocation is closely related to the power-of-two size of -// the allocation. More precisely, the order is the bit index of the -// most-significant-bit in the allocation size, where the bit numbers starts -// at index 1 for the least-significant-bit. -// In terms of allocation sizes, order 0 covers 0, order 1 covers 1, order 2 -// covers 2->3, order 3 covers 4->7, order 4 covers 8->15. -static const size_t kGenericMinBucketedOrder = 4; // 8 bytes. -static const size_t kGenericMaxBucketedOrder = - 20; // Largest bucketed order is 1<<(20-1) (storing 512KB -> almost 1MB) -static const size_t kGenericNumBucketedOrders = - (kGenericMaxBucketedOrder - kGenericMinBucketedOrder) + 1; -// Eight buckets per order (for the higher orders), e.g. order 8 is 128, 144, -// 160, ..., 240: -static const size_t kGenericNumBucketsPerOrderBits = 3; -static const size_t kGenericNumBucketsPerOrder = - 1 << kGenericNumBucketsPerOrderBits; -static const size_t kGenericNumBuckets = - kGenericNumBucketedOrders * kGenericNumBucketsPerOrder; -static const size_t kGenericSmallestBucket = 1 - << (kGenericMinBucketedOrder - 1); -static const size_t kGenericMaxBucketSpacing = - 1 << ((kGenericMaxBucketedOrder - 1) - kGenericNumBucketsPerOrderBits); -static const size_t kGenericMaxBucketed = - (1 << (kGenericMaxBucketedOrder - 1)) + - ((kGenericNumBucketsPerOrder - 1) * kGenericMaxBucketSpacing); -static const size_t kGenericMinDirectMappedDownsize = - kGenericMaxBucketed + - 1; // Limit when downsizing a direct mapping using realloc(). -static const size_t kGenericMaxDirectMapped = INT_MAX - kSystemPageSize; -static const size_t kBitsPerSizeT = sizeof(void*) * CHAR_BIT; - -// Constants for the memory reclaim logic. -static const size_t kMaxFreeableSpans = 16; - -// If the total size in bytes of allocated but not committed pages exceeds this -// value (probably it is a "out of virtual address space" crash), -// a special crash stack trace is generated at |partitionOutOfMemory|. -// This is to distinguish "out of virtual address space" from -// "out of physical memory" in crash reports. -static const size_t kReasonableSizeOfUnusedPages = 1024 * 1024 * 1024; // 1GiB - -#if DCHECK_IS_ON() -// These two byte values match tcmalloc. -static const unsigned char kUninitializedByte = 0xAB; -static const unsigned char kFreedByte = 0xCD; -static const size_t kCookieSize = - 16; // Handles alignment up to XMM instructions on Intel. -static const unsigned char kCookieValue[kCookieSize] = { - 0xDE, 0xAD, 0xBE, 0xEF, 0xCA, 0xFE, 0xD0, 0x0D, - 0x13, 0x37, 0xF0, 0x05, 0xBA, 0x11, 0xAB, 0x1E}; -#endif - -struct PartitionBucket; -struct PartitionRootBase; - -struct PartitionFreelistEntry { - PartitionFreelistEntry* next; -}; - -// Some notes on page states. A page can be in one of four major states: -// 1) Active. -// 2) Full. -// 3) Empty. -// 4) Decommitted. -// An active page has available free slots. A full page has no free slots. An -// empty page has no free slots, and a decommitted page is an empty page that -// had its backing memory released back to the system. -// There are two linked lists tracking the pages. The "active page" list is an -// approximation of a list of active pages. It is an approximation because -// full, empty and decommitted pages may briefly be present in the list until -// we next do a scan over it. -// The "empty page" list is an accurate list of pages which are either empty -// or decommitted. -// -// The significant page transitions are: -// - free() will detect when a full page has a slot free()'d and immediately -// return the page to the head of the active list. -// - free() will detect when a page is fully emptied. It _may_ add it to the -// empty list or it _may_ leave it on the active list until a future list scan. -// - malloc() _may_ scan the active page list in order to fulfil the request. -// If it does this, full, empty and decommitted pages encountered will be -// booted out of the active list. If there are no suitable active pages found, -// an empty or decommitted page (if one exists) will be pulled from the empty -// list on to the active list. -struct PartitionPage { - PartitionFreelistEntry* freelist_head; - PartitionPage* next_page; - PartitionBucket* bucket; - // Deliberately signed, 0 for empty or decommitted page, -n for full pages: - int16_t num_allocated_slots; - uint16_t num_unprovisioned_slots; - uint16_t page_offset; - int16_t empty_cache_index; // -1 if not in the empty cache. -}; - -struct PartitionBucket { - PartitionPage* active_pages_head; // Accessed most in hot path => goes first. - PartitionPage* empty_pages_head; - PartitionPage* decommitted_pages_head; - uint32_t slot_size; - unsigned num_system_pages_per_slot_span : 8; - unsigned num_full_pages : 24; -}; +class PartitionStatsDumper; -// An "extent" is a span of consecutive superpages. We link to the partition's -// next extent (if there is one) at the very start of a superpage's metadata -// area. -struct PartitionSuperPageExtentEntry { - PartitionRootBase* root; - char* super_page_base; - char* super_pages_end; - PartitionSuperPageExtentEntry* next; -}; - -struct PartitionDirectMapExtent { - PartitionDirectMapExtent* next_extent; - PartitionDirectMapExtent* prev_extent; - PartitionBucket* bucket; - size_t map_size; // Mapped size, not including guard pages and meta-data. -}; - -struct BASE_EXPORT PartitionRootBase { - size_t total_size_of_committed_pages; - size_t total_size_of_super_pages; - size_t total_size_of_direct_mapped_pages; - // Invariant: total_size_of_committed_pages <= - // total_size_of_super_pages + - // total_size_of_direct_mapped_pages. - unsigned num_buckets; - unsigned max_allocation; - bool initialized; - char* next_super_page; - char* next_partition_page; - char* next_partition_page_end; - PartitionSuperPageExtentEntry* current_extent; - PartitionSuperPageExtentEntry* first_extent; - PartitionDirectMapExtent* direct_map_list; - PartitionPage* global_empty_page_ring[kMaxFreeableSpans]; - int16_t global_empty_page_ring_index; - uintptr_t inverted_self; - - static subtle::SpinLock gInitializedLock; - static bool gInitialized; - // gSeedPage is used as a sentinel to indicate that there is no page - // in the active page list. We can use nullptr, but in that case we need - // to add a null-check branch to the hot allocation path. We want to avoid - // that. - static PartitionPage gSeedPage; - static PartitionBucket gPagedBucket; - // gOomHandlingFunction is invoked when ParitionAlloc hits OutOfMemory. - static void (*gOomHandlingFunction)(); +enum PartitionPurgeFlags { + // Decommitting the ring list of empty pages is reasonably fast. + PartitionPurgeDecommitEmptyPages = 1 << 0, + // Discarding unused system pages is slower, because it involves walking all + // freelists in all active partition pages of all buckets >= system page + // size. It often frees a similar amount of memory to decommitting the empty + // pages, though. + PartitionPurgeDiscardUnusedSystemPages = 1 << 1, }; // Never instantiate a PartitionRoot directly, instead use PartitionAlloc. -struct PartitionRoot : public PartitionRootBase { +struct BASE_EXPORT PartitionRoot : public internal::PartitionRootBase { + PartitionRoot(); + ~PartitionRoot() override; + // This references the buckets OFF the edge of this struct. All uses of + // PartitionRoot must have the bucket array come right after. + // // The PartitionAlloc templated class ensures the following is correct. - ALWAYS_INLINE PartitionBucket* buckets() { - return reinterpret_cast<PartitionBucket*>(this + 1); + ALWAYS_INLINE internal::PartitionBucket* buckets() { + return reinterpret_cast<internal::PartitionBucket*>(this + 1); } - ALWAYS_INLINE const PartitionBucket* buckets() const { - return reinterpret_cast<const PartitionBucket*>(this + 1); + ALWAYS_INLINE const internal::PartitionBucket* buckets() const { + return reinterpret_cast<const internal::PartitionBucket*>(this + 1); } + + void Init(size_t num_buckets, size_t max_allocation); + + ALWAYS_INLINE void* Alloc(size_t size, const char* type_name); + ALWAYS_INLINE void* AllocFlags(int flags, size_t size, const char* type_name); + + void PurgeMemory(int flags); + + void DumpStats(const char* partition_name, + bool is_light_dump, + PartitionStatsDumper* dumper); }; // Never instantiate a PartitionRootGeneric directly, instead use // PartitionAllocatorGeneric. -struct PartitionRootGeneric : public PartitionRootBase { +struct BASE_EXPORT PartitionRootGeneric : public internal::PartitionRootBase { + PartitionRootGeneric(); + ~PartitionRootGeneric() override; subtle::SpinLock lock; // Some pre-computed constants. - size_t order_index_shifts[kBitsPerSizeT + 1]; - size_t order_sub_index_masks[kBitsPerSizeT + 1]; + size_t order_index_shifts[kBitsPerSizeT + 1] = {}; + size_t order_sub_index_masks[kBitsPerSizeT + 1] = {}; // The bucket lookup table lets us map a size_t to a bucket quickly. // The trailing +1 caters for the overflow case for very large allocation // sizes. It is one flat array instead of a 2D array because in the 2D // world, we'd need to index array[blah][max+1] which risks undefined // behavior. - PartitionBucket* - bucket_lookups[((kBitsPerSizeT + 1) * kGenericNumBucketsPerOrder) + 1]; - PartitionBucket buckets[kGenericNumBuckets]; -}; + internal::PartitionBucket* + bucket_lookups[((kBitsPerSizeT + 1) * kGenericNumBucketsPerOrder) + 1] = + {}; + internal::PartitionBucket buckets[kGenericNumBuckets] = {}; + + // Public API. + void Init(); + + ALWAYS_INLINE void* Alloc(size_t size, const char* type_name); + ALWAYS_INLINE void* AllocFlags(int flags, size_t size, const char* type_name); + ALWAYS_INLINE void Free(void* ptr); -// Flags for PartitionAllocGenericFlags. -enum PartitionAllocFlags { - PartitionAllocReturnNull = 1 << 0, + NOINLINE void* Realloc(void* ptr, size_t new_size, const char* type_name); + // Overload that may return nullptr if reallocation isn't possible. In this + // case, |ptr| remains valid. + NOINLINE void* TryRealloc(void* ptr, size_t new_size, const char* type_name); + + ALWAYS_INLINE size_t ActualSize(size_t size); + + void PurgeMemory(int flags); + + void DumpStats(const char* partition_name, + bool is_light_dump, + PartitionStatsDumper* partition_stats_dumper); }; // Struct used to retrieve total memory usage of a partition. Used by @@ -409,58 +211,24 @@ class BASE_EXPORT PartitionStatsDumper { }; BASE_EXPORT void PartitionAllocGlobalInit(void (*oom_handling_function)()); -BASE_EXPORT void PartitionAllocInit(PartitionRoot*, - size_t num_buckets, - size_t max_allocation); -BASE_EXPORT void PartitionAllocGenericInit(PartitionRootGeneric*); - -enum PartitionPurgeFlags { - // Decommitting the ring list of empty pages is reasonably fast. - PartitionPurgeDecommitEmptyPages = 1 << 0, - // Discarding unused system pages is slower, because it involves walking all - // freelists in all active partition pages of all buckets >= system page - // size. It often frees a similar amount of memory to decommitting the empty - // pages, though. - PartitionPurgeDiscardUnusedSystemPages = 1 << 1, -}; - -BASE_EXPORT void PartitionPurgeMemory(PartitionRoot*, int); -BASE_EXPORT void PartitionPurgeMemoryGeneric(PartitionRootGeneric*, int); - -BASE_EXPORT NOINLINE void* PartitionAllocSlowPath(PartitionRootBase*, - int, - size_t, - PartitionBucket*); -BASE_EXPORT NOINLINE void PartitionFreeSlowPath(PartitionPage*); -BASE_EXPORT NOINLINE void* PartitionReallocGenericFlags( - PartitionRootGeneric* root, - int flags, - void* ptr, - size_t new_size, - const char* type_name); -BASE_EXPORT NOINLINE void* PartitionReallocGeneric(PartitionRootGeneric* root, - void* ptr, - size_t new_size, - const char* type_name); - -BASE_EXPORT void PartitionDumpStats(PartitionRoot*, - const char* partition_name, - bool is_light_dump, - PartitionStatsDumper*); -BASE_EXPORT void PartitionDumpStatsGeneric(PartitionRootGeneric*, - const char* partition_name, - bool is_light_dump, - PartitionStatsDumper*); class BASE_EXPORT PartitionAllocHooks { public: typedef void AllocationHook(void* address, size_t, const char* type_name); typedef void FreeHook(void* address); + // To unhook, call Set*Hook with nullptr. static void SetAllocationHook(AllocationHook* hook) { + // Chained allocation hooks are not supported. Registering a non-null + // hook when a non-null hook is already registered indicates somebody is + // trying to overwrite a hook. + CHECK(!hook || !allocation_hook_); allocation_hook_ = hook; } - static void SetFreeHook(FreeHook* hook) { free_hook_ = hook; } + static void SetFreeHook(FreeHook* hook) { + CHECK(!hook || !free_hook_); + free_hook_ = hook; + } static void AllocationHookIfEnabled(void* address, size_t size, @@ -496,282 +264,69 @@ class BASE_EXPORT PartitionAllocHooks { static FreeHook* free_hook_; }; -ALWAYS_INLINE PartitionFreelistEntry* PartitionFreelistMask( - PartitionFreelistEntry* ptr) { -// We use bswap on little endian as a fast mask for two reasons: -// 1) If an object is freed and its vtable used where the attacker doesn't -// get the chance to run allocations between the free and use, the vtable -// dereference is likely to fault. -// 2) If the attacker has a linear buffer overflow and elects to try and -// corrupt a freelist pointer, partial pointer overwrite attacks are -// thwarted. -// For big endian, similar guarantees are arrived at with a negation. -#if defined(ARCH_CPU_BIG_ENDIAN) - uintptr_t masked = ~reinterpret_cast<uintptr_t>(ptr); -#else - uintptr_t masked = ByteSwapUintPtrT(reinterpret_cast<uintptr_t>(ptr)); -#endif - return reinterpret_cast<PartitionFreelistEntry*>(masked); -} - -ALWAYS_INLINE size_t PartitionCookieSizeAdjustAdd(size_t size) { -#if DCHECK_IS_ON() - // Add space for cookies, checking for integer overflow. TODO(palmer): - // Investigate the performance and code size implications of using - // CheckedNumeric throughout PA. - DCHECK(size + (2 * kCookieSize) > size); - size += 2 * kCookieSize; -#endif - return size; -} - -ALWAYS_INLINE size_t PartitionCookieSizeAdjustSubtract(size_t size) { -#if DCHECK_IS_ON() - // Remove space for cookies. - DCHECK(size >= 2 * kCookieSize); - size -= 2 * kCookieSize; -#endif - return size; -} - -ALWAYS_INLINE void* PartitionCookieFreePointerAdjust(void* ptr) { -#if DCHECK_IS_ON() - // The value given to the application is actually just after the cookie. - ptr = static_cast<char*>(ptr) - kCookieSize; -#endif - return ptr; -} - -ALWAYS_INLINE void PartitionCookieWriteValue(void* ptr) { -#if DCHECK_IS_ON() - auto* cookie_ptr = reinterpret_cast<unsigned char*>(ptr); - for (size_t i = 0; i < kCookieSize; ++i, ++cookie_ptr) - *cookie_ptr = kCookieValue[i]; -#endif -} - -ALWAYS_INLINE void PartitionCookieCheckValue(void* ptr) { -#if DCHECK_IS_ON() - auto* cookie_ptr = reinterpret_cast<unsigned char*>(ptr); - for (size_t i = 0; i < kCookieSize; ++i, ++cookie_ptr) - DCHECK(*cookie_ptr == kCookieValue[i]); -#endif -} - -ALWAYS_INLINE char* PartitionSuperPageToMetadataArea(char* ptr) { - auto pointer_as_uint = reinterpret_cast<uintptr_t>(ptr); - DCHECK(!(pointer_as_uint & kSuperPageOffsetMask)); - // The metadata area is exactly one system page (the guard page) into the - // super page. - return reinterpret_cast<char*>(pointer_as_uint + kSystemPageSize); -} - -ALWAYS_INLINE PartitionPage* PartitionPointerToPageNoAlignmentCheck(void* ptr) { - auto pointer_as_uint = reinterpret_cast<uintptr_t>(ptr); - auto* super_page_ptr = - reinterpret_cast<char*>(pointer_as_uint & kSuperPageBaseMask); - uintptr_t partition_page_index = - (pointer_as_uint & kSuperPageOffsetMask) >> kPartitionPageShift; - // Index 0 is invalid because it is the metadata and guard area and - // the last index is invalid because it is a guard page. - DCHECK(partition_page_index); - DCHECK(partition_page_index < kNumPartitionPagesPerSuperPage - 1); - auto* page = reinterpret_cast<PartitionPage*>( - PartitionSuperPageToMetadataArea(super_page_ptr) + - (partition_page_index << kPageMetadataShift)); - // Partition pages in the same slot span can share the same page object. - // Adjust for that. - size_t delta = page->page_offset << kPageMetadataShift; - page = - reinterpret_cast<PartitionPage*>(reinterpret_cast<char*>(page) - delta); - return page; -} - -ALWAYS_INLINE void* PartitionPageToPointer(const PartitionPage* page) { - auto pointer_as_uint = reinterpret_cast<uintptr_t>(page); - uintptr_t super_page_offset = (pointer_as_uint & kSuperPageOffsetMask); - DCHECK(super_page_offset > kSystemPageSize); - DCHECK(super_page_offset < kSystemPageSize + (kNumPartitionPagesPerSuperPage * - kPageMetadataSize)); - uintptr_t partition_page_index = - (super_page_offset - kSystemPageSize) >> kPageMetadataShift; - // Index 0 is invalid because it is the metadata area and the last index is - // invalid because it is a guard page. - DCHECK(partition_page_index); - DCHECK(partition_page_index < kNumPartitionPagesPerSuperPage - 1); - uintptr_t super_page_base = (pointer_as_uint & kSuperPageBaseMask); - auto* ret = reinterpret_cast<void*>( - super_page_base + (partition_page_index << kPartitionPageShift)); - return ret; -} - -ALWAYS_INLINE PartitionPage* PartitionPointerToPage(void* ptr) { - PartitionPage* page = PartitionPointerToPageNoAlignmentCheck(ptr); - // Checks that the pointer is a multiple of bucket size. - DCHECK(!((reinterpret_cast<uintptr_t>(ptr) - - reinterpret_cast<uintptr_t>(PartitionPageToPointer(page))) % - page->bucket->slot_size)); - return page; -} - -ALWAYS_INLINE bool PartitionBucketIsDirectMapped( - const PartitionBucket* bucket) { - return !bucket->num_system_pages_per_slot_span; -} - -ALWAYS_INLINE size_t PartitionBucketBytes(const PartitionBucket* bucket) { - return bucket->num_system_pages_per_slot_span * kSystemPageSize; -} - -ALWAYS_INLINE uint16_t PartitionBucketSlots(const PartitionBucket* bucket) { - return static_cast<uint16_t>(PartitionBucketBytes(bucket) / - bucket->slot_size); -} - -ALWAYS_INLINE size_t* PartitionPageGetRawSizePtr(PartitionPage* page) { - // For single-slot buckets which span more than one partition page, we - // have some spare metadata space to store the raw allocation size. We - // can use this to report better statistics. - PartitionBucket* bucket = page->bucket; - if (bucket->slot_size <= kMaxSystemPagesPerSlotSpan * kSystemPageSize) - return nullptr; - - DCHECK((bucket->slot_size % kSystemPageSize) == 0); - DCHECK(PartitionBucketIsDirectMapped(bucket) || - PartitionBucketSlots(bucket) == 1); - page++; - return reinterpret_cast<size_t*>(&page->freelist_head); -} - -ALWAYS_INLINE size_t PartitionPageGetRawSize(PartitionPage* page) { - size_t* raw_size_ptr = PartitionPageGetRawSizePtr(page); - if (UNLIKELY(raw_size_ptr != nullptr)) - return *raw_size_ptr; - return 0; -} - -ALWAYS_INLINE PartitionRootBase* PartitionPageToRoot(PartitionPage* page) { - auto* extent_entry = reinterpret_cast<PartitionSuperPageExtentEntry*>( - reinterpret_cast<uintptr_t>(page) & kSystemPageBaseMask); - return extent_entry->root; -} - -ALWAYS_INLINE bool PartitionPointerIsValid(void* ptr) { - PartitionPage* page = PartitionPointerToPage(ptr); - PartitionRootBase* root = PartitionPageToRoot(page); - return root->inverted_self == ~reinterpret_cast<uintptr_t>(root); -} - -ALWAYS_INLINE void* PartitionBucketAlloc(PartitionRootBase* root, - int flags, - size_t size, - PartitionBucket* bucket) { - PartitionPage* page = bucket->active_pages_head; - // Check that this page is neither full nor freed. - DCHECK(page->num_allocated_slots >= 0); - void* ret = page->freelist_head; - if (LIKELY(ret)) { - // If these asserts fire, you probably corrupted memory. - DCHECK(PartitionPointerIsValid(ret)); - // All large allocations must go through the slow path to correctly - // update the size metadata. - DCHECK(PartitionPageGetRawSize(page) == 0); - PartitionFreelistEntry* new_head = - PartitionFreelistMask(static_cast<PartitionFreelistEntry*>(ret)->next); - page->freelist_head = new_head; - page->num_allocated_slots++; - } else { - ret = PartitionAllocSlowPath(root, flags, size, bucket); - DCHECK(!ret || PartitionPointerIsValid(ret)); - } -#if DCHECK_IS_ON() - if (!ret) - return nullptr; - // Fill the uninitialized pattern, and write the cookies. - page = PartitionPointerToPage(ret); - size_t slot_size = page->bucket->slot_size; - size_t raw_size = PartitionPageGetRawSize(page); - if (raw_size) { - DCHECK(raw_size == size); - slot_size = raw_size; - } - size_t no_cookie_size = PartitionCookieSizeAdjustSubtract(slot_size); - auto* char_ret = static_cast<char*>(ret); - // The value given to the application is actually just after the cookie. - ret = char_ret + kCookieSize; - memset(ret, kUninitializedByte, no_cookie_size); - PartitionCookieWriteValue(char_ret); - PartitionCookieWriteValue(char_ret + kCookieSize + no_cookie_size); -#endif - return ret; +ALWAYS_INLINE void* PartitionRoot::Alloc(size_t size, const char* type_name) { + return AllocFlags(0, size, type_name); } -ALWAYS_INLINE void* PartitionAlloc(PartitionRoot* root, - size_t size, - const char* type_name) { +ALWAYS_INLINE void* PartitionRoot::AllocFlags(int flags, + size_t size, + const char* type_name) { #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) void* result = malloc(size); CHECK(result); return result; #else size_t requested_size = size; - size = PartitionCookieSizeAdjustAdd(size); - DCHECK(root->initialized); + size = internal::PartitionCookieSizeAdjustAdd(size); + DCHECK(this->initialized); size_t index = size >> kBucketShift; - DCHECK(index < root->num_buckets); + DCHECK(index < this->num_buckets); DCHECK(size == index << kBucketShift); - PartitionBucket* bucket = &root->buckets()[index]; - void* result = PartitionBucketAlloc(root, 0, size, bucket); + internal::PartitionBucket* bucket = &this->buckets()[index]; + void* result = AllocFromBucket(bucket, flags, size); PartitionAllocHooks::AllocationHookIfEnabled(result, requested_size, type_name); return result; #endif // defined(MEMORY_TOOL_REPLACES_ALLOCATOR) } -ALWAYS_INLINE void PartitionFreeWithPage(void* ptr, PartitionPage* page) { -// If these asserts fire, you probably corrupted memory. -#if DCHECK_IS_ON() - size_t slot_size = page->bucket->slot_size; - size_t raw_size = PartitionPageGetRawSize(page); - if (raw_size) - slot_size = raw_size; - PartitionCookieCheckValue(ptr); - PartitionCookieCheckValue(reinterpret_cast<char*>(ptr) + slot_size - - kCookieSize); - memset(ptr, kFreedByte, slot_size); +ALWAYS_INLINE bool PartitionAllocSupportsGetSize() { +#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) + return false; +#else + return true; #endif - DCHECK(page->num_allocated_slots); - PartitionFreelistEntry* freelist_head = page->freelist_head; - DCHECK(!freelist_head || PartitionPointerIsValid(freelist_head)); - CHECK(ptr != freelist_head); // Catches an immediate double free. - // Look for double free one level deeper in debug. - DCHECK(!freelist_head || ptr != PartitionFreelistMask(freelist_head->next)); - auto* entry = static_cast<PartitionFreelistEntry*>(ptr); - entry->next = PartitionFreelistMask(freelist_head); - page->freelist_head = entry; - --page->num_allocated_slots; - if (UNLIKELY(page->num_allocated_slots <= 0)) { - PartitionFreeSlowPath(page); - } else { - // All single-slot allocations must go through the slow path to - // correctly update the size metadata. - DCHECK(PartitionPageGetRawSize(page) == 0); - } +} + +ALWAYS_INLINE size_t PartitionAllocGetSize(void* ptr) { + // No need to lock here. Only |ptr| being freed by another thread could + // cause trouble, and the caller is responsible for that not happening. + DCHECK(PartitionAllocSupportsGetSize()); + ptr = internal::PartitionCookieFreePointerAdjust(ptr); + internal::PartitionPage* page = internal::PartitionPage::FromPointer(ptr); + // TODO(palmer): See if we can afford to make this a CHECK. + DCHECK(internal::PartitionRootBase::IsValidPage(page)); + size_t size = page->bucket->slot_size; + return internal::PartitionCookieSizeAdjustSubtract(size); } ALWAYS_INLINE void PartitionFree(void* ptr) { #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) free(ptr); #else - PartitionAllocHooks::FreeHookIfEnabled(ptr); - ptr = PartitionCookieFreePointerAdjust(ptr); - DCHECK(PartitionPointerIsValid(ptr)); - PartitionPage* page = PartitionPointerToPage(ptr); - PartitionFreeWithPage(ptr, page); + void* original_ptr = ptr; + // TODO(palmer): Check ptr alignment before continuing. Shall we do the check + // inside PartitionCookieFreePointerAdjust? + PartitionAllocHooks::FreeHookIfEnabled(original_ptr); + ptr = internal::PartitionCookieFreePointerAdjust(ptr); + internal::PartitionPage* page = internal::PartitionPage::FromPointer(ptr); + // TODO(palmer): See if we can afford to make this a CHECK. + DCHECK(internal::PartitionRootBase::IsValidPage(page)); + page->Free(ptr); #endif } -ALWAYS_INLINE PartitionBucket* PartitionGenericSizeToBucket( +ALWAYS_INLINE internal::PartitionBucket* PartitionGenericSizeToBucket( PartitionRootGeneric* root, size_t size) { size_t order = kBitsPerSizeT - bits::CountLeadingZeroBitsSizeT(size); @@ -780,9 +335,10 @@ ALWAYS_INLINE PartitionBucket* PartitionGenericSizeToBucket( (kGenericNumBucketsPerOrder - 1); // And if the remaining bits are non-zero we must bump the bucket up. size_t sub_order_index = size & root->order_sub_index_masks[order]; - PartitionBucket* bucket = + internal::PartitionBucket* bucket = root->bucket_lookups[(order << kGenericNumBucketsPerOrderBits) + order_index + !!sub_order_index]; + CHECK(bucket); DCHECK(!bucket->slot_size || bucket->slot_size >= size); DCHECK(!(bucket->slot_size % kGenericSmallestBucket)); return bucket; @@ -792,119 +348,109 @@ ALWAYS_INLINE void* PartitionAllocGenericFlags(PartitionRootGeneric* root, int flags, size_t size, const char* type_name) { + DCHECK(flags < PartitionAllocLastFlag << 1); + #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) - void* result = malloc(size); + const bool zero_fill = flags & PartitionAllocZeroFill; + void* result = zero_fill ? calloc(1, size) : malloc(size); CHECK(result || flags & PartitionAllocReturnNull); return result; #else DCHECK(root->initialized); size_t requested_size = size; - size = PartitionCookieSizeAdjustAdd(size); - PartitionBucket* bucket = PartitionGenericSizeToBucket(root, size); + size = internal::PartitionCookieSizeAdjustAdd(size); + internal::PartitionBucket* bucket = PartitionGenericSizeToBucket(root, size); void* ret = nullptr; { subtle::SpinLock::Guard guard(root->lock); - ret = PartitionBucketAlloc(root, flags, size, bucket); + ret = root->AllocFromBucket(bucket, flags, size); } PartitionAllocHooks::AllocationHookIfEnabled(ret, requested_size, type_name); + return ret; #endif } -ALWAYS_INLINE void* PartitionAllocGeneric(PartitionRootGeneric* root, - size_t size, - const char* type_name) { - return PartitionAllocGenericFlags(root, 0, size, type_name); +ALWAYS_INLINE void* PartitionRootGeneric::Alloc(size_t size, + const char* type_name) { + return PartitionAllocGenericFlags(this, 0, size, type_name); } -ALWAYS_INLINE void PartitionFreeGeneric(PartitionRootGeneric* root, void* ptr) { +ALWAYS_INLINE void* PartitionRootGeneric::AllocFlags(int flags, + size_t size, + const char* type_name) { + return PartitionAllocGenericFlags(this, flags, size, type_name); +} + +ALWAYS_INLINE void PartitionRootGeneric::Free(void* ptr) { #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) free(ptr); #else - DCHECK(root->initialized); + DCHECK(this->initialized); if (UNLIKELY(!ptr)) return; PartitionAllocHooks::FreeHookIfEnabled(ptr); - ptr = PartitionCookieFreePointerAdjust(ptr); - DCHECK(PartitionPointerIsValid(ptr)); - PartitionPage* page = PartitionPointerToPage(ptr); + ptr = internal::PartitionCookieFreePointerAdjust(ptr); + internal::PartitionPage* page = internal::PartitionPage::FromPointer(ptr); + // TODO(palmer): See if we can afford to make this a CHECK. + DCHECK(IsValidPage(page)); { - subtle::SpinLock::Guard guard(root->lock); - PartitionFreeWithPage(ptr, page); + subtle::SpinLock::Guard guard(this->lock); + page->Free(ptr); } #endif } -ALWAYS_INLINE size_t PartitionDirectMapSize(size_t size) { - // Caller must check that the size is not above the kGenericMaxDirectMapped - // limit before calling. This also guards against integer overflow in the - // calculation here. - DCHECK(size <= kGenericMaxDirectMapped); - return (size + kSystemPageOffsetMask) & kSystemPageBaseMask; -} +BASE_EXPORT void* PartitionReallocGenericFlags(PartitionRootGeneric* root, + int flags, + void* ptr, + size_t new_size, + const char* type_name); -ALWAYS_INLINE size_t PartitionAllocActualSize(PartitionRootGeneric* root, - size_t size) { +ALWAYS_INLINE size_t PartitionRootGeneric::ActualSize(size_t size) { #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) return size; #else - DCHECK(root->initialized); - size = PartitionCookieSizeAdjustAdd(size); - PartitionBucket* bucket = PartitionGenericSizeToBucket(root, size); - if (LIKELY(!PartitionBucketIsDirectMapped(bucket))) { + DCHECK(this->initialized); + size = internal::PartitionCookieSizeAdjustAdd(size); + internal::PartitionBucket* bucket = PartitionGenericSizeToBucket(this, size); + if (LIKELY(!bucket->is_direct_mapped())) { size = bucket->slot_size; } else if (size > kGenericMaxDirectMapped) { // Too large to allocate => return the size unchanged. } else { - DCHECK(bucket == &PartitionRootBase::gPagedBucket); - size = PartitionDirectMapSize(size); + size = internal::PartitionBucket::get_direct_map_size(size); } - return PartitionCookieSizeAdjustSubtract(size); + return internal::PartitionCookieSizeAdjustSubtract(size); #endif } -ALWAYS_INLINE bool PartitionAllocSupportsGetSize() { -#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) - return false; -#else - return true; -#endif -} - -ALWAYS_INLINE size_t PartitionAllocGetSize(void* ptr) { - // No need to lock here. Only |ptr| being freed by another thread could - // cause trouble, and the caller is responsible for that not happening. - DCHECK(PartitionAllocSupportsGetSize()); - ptr = PartitionCookieFreePointerAdjust(ptr); - DCHECK(PartitionPointerIsValid(ptr)); - PartitionPage* page = PartitionPointerToPage(ptr); - size_t size = page->bucket->slot_size; - return PartitionCookieSizeAdjustSubtract(size); -} - -// N (or more accurately, N - sizeof(void*)) represents the largest size in -// bytes that will be handled by a SizeSpecificPartitionAllocator. -// Attempts to partitionAlloc() more than this amount will fail. template <size_t N> class SizeSpecificPartitionAllocator { public: + SizeSpecificPartitionAllocator() { + memset(actual_buckets_, 0, + sizeof(internal::PartitionBucket) * pdfium::size(actual_buckets_)); + } + ~SizeSpecificPartitionAllocator() = default; static const size_t kMaxAllocation = N - kAllocationGranularity; static const size_t kNumBuckets = N / kAllocationGranularity; - void init() { - PartitionAllocInit(&partition_root_, kNumBuckets, kMaxAllocation); - } + void init() { partition_root_.Init(kNumBuckets, kMaxAllocation); } ALWAYS_INLINE PartitionRoot* root() { return &partition_root_; } private: PartitionRoot partition_root_; - PartitionBucket actual_buckets_[kNumBuckets]; + internal::PartitionBucket actual_buckets_[kNumBuckets]; }; -class PartitionAllocatorGeneric { +class BASE_EXPORT PartitionAllocatorGeneric { public: - void init() { PartitionAllocGenericInit(&partition_root_); } + PartitionAllocatorGeneric(); + ~PartitionAllocatorGeneric(); + + void init() { partition_root_.Init(); } ALWAYS_INLINE PartitionRootGeneric* root() { return &partition_root_; } private: @@ -914,4 +460,4 @@ class PartitionAllocatorGeneric { } // namespace base } // namespace pdfium -#endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H +#endif // THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H_ |