Index: third_party/WebKit/Source/wtf/allocator/PartitionAlloc.h |
diff --git a/third_party/WebKit/Source/wtf/allocator/PartitionAlloc.h b/third_party/WebKit/Source/wtf/allocator/PartitionAlloc.h |
deleted file mode 100644 |
index aa3c0bbc527ebd92a65eecf29dd0b9a32db54f69..0000000000000000000000000000000000000000 |
--- a/third_party/WebKit/Source/wtf/allocator/PartitionAlloc.h |
+++ /dev/null |
@@ -1,957 +0,0 @@ |
-/* |
- * Copyright (C) 2013 Google Inc. All rights reserved. |
- * |
- * Redistribution and use in source and binary forms, with or without |
- * modification, are permitted provided that the following conditions are |
- * met: |
- * |
- * * Redistributions of source code must retain the above copyright |
- * notice, this list of conditions and the following disclaimer. |
- * * Redistributions in binary form must reproduce the above |
- * copyright notice, this list of conditions and the following disclaimer |
- * in the documentation and/or other materials provided with the |
- * distribution. |
- * * Neither the name of Google Inc. nor the names of its |
- * contributors may be used to endorse or promote products derived from |
- * this software without specific prior written permission. |
- * |
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
- * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
- */ |
- |
-#ifndef WTF_PartitionAlloc_h |
-#define WTF_PartitionAlloc_h |
- |
-// DESCRIPTION |
-// partitionAlloc() / partitionAllocGeneric() and partitionFree() / |
-// partitionFreeGeneric() 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" |
-// that will be used to satisfy the allocation. Different partitions are |
-// guaranteed to exist in separate address spaces, including being separate from |
-// the main system heap. If the contained objects are all freed, physical memory |
-// is returned to the system but the address space remains reserved. |
-// See PartitionAlloc.md for other security properties PartitionAlloc provides. |
-// |
-// THE ONLY LEGITIMATE WAY TO OBTAIN A PartitionRoot IS THROUGH THE |
-// SizeSpecificPartitionAllocator / PartitionAllocatorGeneric classes. To |
-// minimize the instruction count to the fullest extent possible, the |
-// 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: |
-// - 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(): |
-// - 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). |
-// - Bucketing is by approximate size, for example an allocation of 4000 bytes |
-// might be placed into a 4096-byte bucket. Bucket sizes are chosen to try and |
-// keep worst-case waste to ~10%. |
-// |
-// The allocators are designed to be extremely fast, thanks to the following |
-// properties and design: |
-// - Just two single (reasonably predicatable) branches in the hot / fast path |
-// for both allocating and (significantly) freeing. |
-// - A minimal number of operations in the hot / fast path, with the slow paths |
-// in separate functions, leading to the possibility of inlining. |
-// - Each partition page (which is usually multiple physical pages) has a |
-// metadata structure which allows fast mapping of free() address to an |
-// underlying bucket. |
-// - Supports a lock-free API for fast performance in single-threaded cases. |
-// - The freelist for a given bucket is split across a number of partition |
-// pages, enabling various simple tricks to try and minimize fragmentation. |
-// - Fine-grained bucket sizes leading to less waste and better packing. |
-// |
-// The following security properties could be investigated in the future: |
-// - Per-object bucketing (instead of per-size) is mostly available at the API, |
-// but not used yet. |
-// - No randomness of freelist entries or bucket position. |
-// - Better checking for wild pointers in free(). |
-// - Better freelist masking function to guarantee fault on 32-bit. |
- |
-#include "wtf/Assertions.h" |
-#include "wtf/BitwiseOperations.h" |
-#include "wtf/ByteSwap.h" |
-#include "wtf/CPU.h" |
-#include "wtf/SpinLock.h" |
-#include "wtf/TypeTraits.h" |
-#include "wtf/allocator/PageAllocator.h" |
- |
-#include <limits.h> |
- |
-#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
-#include <stdlib.h> |
-#endif |
- |
-#if ENABLE(ASSERT) |
-#include <string.h> |
-#endif |
- |
-namespace WTF { |
- |
-// 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. |
-static const size_t kPartitionPageShift = 14; // 16KB |
-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 ENABLE(ASSERT) |
-// 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* freelistHead; |
- PartitionPage* nextPage; |
- PartitionBucket* bucket; |
- // Deliberately signed, 0 for empty or decommitted page, -n for full pages: |
- int16_t numAllocatedSlots; |
- uint16_t numUnprovisionedSlots; |
- uint16_t pageOffset; |
- int16_t emptyCacheIndex; // -1 if not in the empty cache. |
-}; |
- |
-struct PartitionBucket { |
- PartitionPage* activePagesHead; // Accessed most in hot path => goes first. |
- PartitionPage* emptyPagesHead; |
- PartitionPage* decommittedPagesHead; |
- uint32_t slotSize; |
- unsigned numSystemPagesPerSlotSpan : 8; |
- unsigned numFullPages : 24; |
-}; |
- |
-// 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* superPageBase; |
- char* superPagesEnd; |
- PartitionSuperPageExtentEntry* next; |
-}; |
- |
-struct PartitionDirectMapExtent { |
- PartitionDirectMapExtent* nextExtent; |
- PartitionDirectMapExtent* prevExtent; |
- PartitionBucket* bucket; |
- size_t mapSize; // Mapped size, not including guard pages and meta-data. |
-}; |
- |
-struct WTF_EXPORT PartitionRootBase { |
- size_t totalSizeOfCommittedPages; |
- size_t totalSizeOfSuperPages; |
- size_t totalSizeOfDirectMappedPages; |
- // Invariant: totalSizeOfCommittedPages <= |
- // totalSizeOfSuperPages + totalSizeOfDirectMappedPages. |
- unsigned numBuckets; |
- unsigned maxAllocation; |
- bool initialized; |
- char* nextSuperPage; |
- char* nextPartitionPage; |
- char* nextPartitionPageEnd; |
- PartitionSuperPageExtentEntry* currentExtent; |
- PartitionSuperPageExtentEntry* firstExtent; |
- PartitionDirectMapExtent* directMapList; |
- PartitionPage* globalEmptyPageRing[kMaxFreeableSpans]; |
- int16_t globalEmptyPageRingIndex; |
- uintptr_t invertedSelf; |
- |
- static 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)(); |
-}; |
- |
-// Never instantiate a PartitionRoot directly, instead use PartitionAlloc. |
-struct PartitionRoot : public PartitionRootBase { |
- // The PartitionAlloc templated class ensures the following is correct. |
- ALWAYS_INLINE PartitionBucket* buckets() { |
- return reinterpret_cast<PartitionBucket*>(this + 1); |
- } |
- ALWAYS_INLINE const PartitionBucket* buckets() const { |
- return reinterpret_cast<const PartitionBucket*>(this + 1); |
- } |
-}; |
- |
-// Never instantiate a PartitionRootGeneric directly, instead use |
-// PartitionAllocatorGeneric. |
-struct PartitionRootGeneric : public PartitionRootBase { |
- SpinLock lock; |
- // Some pre-computed constants. |
- size_t orderIndexShifts[kBitsPerSizet + 1]; |
- size_t orderSubIndexMasks[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* |
- bucketLookups[((kBitsPerSizet + 1) * kGenericNumBucketsPerOrder) + 1]; |
- PartitionBucket buckets[kGenericNumBuckets]; |
-}; |
- |
-// Flags for partitionAllocGenericFlags. |
-enum PartitionAllocFlags { |
- PartitionAllocReturnNull = 1 << 0, |
-}; |
- |
-// Struct used to retrieve total memory usage of a partition. Used by |
-// PartitionStatsDumper implementation. |
-struct PartitionMemoryStats { |
- size_t totalMmappedBytes; // Total bytes mmaped from the system. |
- size_t totalCommittedBytes; // Total size of commmitted pages. |
- size_t totalResidentBytes; // Total bytes provisioned by the partition. |
- size_t totalActiveBytes; // Total active bytes in the partition. |
- size_t totalDecommittableBytes; // Total bytes that could be decommitted. |
- size_t totalDiscardableBytes; // Total bytes that could be discarded. |
-}; |
- |
-// Struct used to retrieve memory statistics about a partition bucket. Used by |
-// PartitionStatsDumper implementation. |
-struct PartitionBucketMemoryStats { |
- bool isValid; // Used to check if the stats is valid. |
- bool isDirectMap; // True if this is a direct mapping; size will not be |
- // unique. |
- uint32_t bucketSlotSize; // The size of the slot in bytes. |
- uint32_t allocatedPageSize; // Total size the partition page allocated from |
- // the system. |
- uint32_t activeBytes; // Total active bytes used in the bucket. |
- uint32_t residentBytes; // Total bytes provisioned in the bucket. |
- uint32_t decommittableBytes; // Total bytes that could be decommitted. |
- uint32_t discardableBytes; // Total bytes that could be discarded. |
- uint32_t numFullPages; // Number of pages with all slots allocated. |
- uint32_t numActivePages; // Number of pages that have at least one |
- // provisioned slot. |
- uint32_t numEmptyPages; // Number of pages that are empty |
- // but not decommitted. |
- uint32_t numDecommittedPages; // Number of pages that are empty |
- // and decommitted. |
-}; |
- |
-// Interface that is passed to partitionDumpStats and |
-// partitionDumpStatsGeneric for using the memory statistics. |
-class WTF_EXPORT PartitionStatsDumper { |
- public: |
- // Called to dump total memory used by partition, once per partition. |
- virtual void partitionDumpTotals(const char* partitionName, |
- const PartitionMemoryStats*) = 0; |
- |
- // Called to dump stats about buckets, for each bucket. |
- virtual void partitionsDumpBucketStats(const char* partitionName, |
- const PartitionBucketMemoryStats*) = 0; |
-}; |
- |
-WTF_EXPORT void partitionAllocGlobalInit(void (*oomHandlingFunction)()); |
-WTF_EXPORT void partitionAllocInit(PartitionRoot*, |
- size_t numBuckets, |
- size_t maxAllocation); |
-WTF_EXPORT bool partitionAllocShutdown(PartitionRoot*); |
-WTF_EXPORT void partitionAllocGenericInit(PartitionRootGeneric*); |
-WTF_EXPORT bool partitionAllocGenericShutdown(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, |
-}; |
- |
-WTF_EXPORT void partitionPurgeMemory(PartitionRoot*, int); |
-WTF_EXPORT void partitionPurgeMemoryGeneric(PartitionRootGeneric*, int); |
- |
-WTF_EXPORT NEVER_INLINE void* partitionAllocSlowPath(PartitionRootBase*, |
- int, |
- size_t, |
- PartitionBucket*); |
-WTF_EXPORT NEVER_INLINE void partitionFreeSlowPath(PartitionPage*); |
-WTF_EXPORT NEVER_INLINE void* partitionReallocGeneric(PartitionRootGeneric*, |
- void*, |
- size_t, |
- const char* typeName); |
- |
-WTF_EXPORT void partitionDumpStats(PartitionRoot*, |
- const char* partitionName, |
- bool isLightDump, |
- PartitionStatsDumper*); |
-WTF_EXPORT void partitionDumpStatsGeneric(PartitionRootGeneric*, |
- const char* partitionName, |
- bool isLightDump, |
- PartitionStatsDumper*); |
- |
-class WTF_EXPORT PartitionAllocHooks { |
- public: |
- typedef void AllocationHook(void* address, size_t, const char* typeName); |
- typedef void FreeHook(void* address); |
- |
- static void setAllocationHook(AllocationHook* hook) { |
- m_allocationHook = hook; |
- } |
- static void setFreeHook(FreeHook* hook) { m_freeHook = hook; } |
- |
- static void allocationHookIfEnabled(void* address, |
- size_t size, |
- const char* typeName) { |
- AllocationHook* allocationHook = m_allocationHook; |
- if (UNLIKELY(allocationHook != nullptr)) |
- allocationHook(address, size, typeName); |
- } |
- |
- static void freeHookIfEnabled(void* address) { |
- FreeHook* freeHook = m_freeHook; |
- if (UNLIKELY(freeHook != nullptr)) |
- freeHook(address); |
- } |
- |
- static void reallocHookIfEnabled(void* oldAddress, |
- void* newAddress, |
- size_t size, |
- const char* typeName) { |
- // Report a reallocation as a free followed by an allocation. |
- AllocationHook* allocationHook = m_allocationHook; |
- FreeHook* freeHook = m_freeHook; |
- if (UNLIKELY(allocationHook && freeHook)) { |
- freeHook(oldAddress); |
- allocationHook(newAddress, size, typeName); |
- } |
- } |
- |
- private: |
- // Pointers to hook functions that PartitionAlloc will call on allocation and |
- // free if the pointers are non-null. |
- static AllocationHook* m_allocationHook; |
- static FreeHook* m_freeHook; |
-}; |
- |
-// In official builds, do not include type info string literals to avoid |
-// bloating the binary. |
-#if defined(OFFICIAL_BUILD) |
-#define WTF_HEAP_PROFILER_TYPE_NAME(T) nullptr |
-#else |
-#define WTF_HEAP_PROFILER_TYPE_NAME(T) ::WTF::getStringWithTypeName<T>() |
-#endif |
- |
-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 CPU(BIG_ENDIAN) |
- uintptr_t masked = ~reinterpret_cast<uintptr_t>(ptr); |
-#else |
- uintptr_t masked = bswapuintptrt(reinterpret_cast<uintptr_t>(ptr)); |
-#endif |
- return reinterpret_cast<PartitionFreelistEntry*>(masked); |
-} |
- |
-ALWAYS_INLINE size_t partitionCookieSizeAdjustAdd(size_t size) { |
-#if ENABLE(ASSERT) |
- // Add space for cookies, checking for integer overflow. |
- ASSERT(size + (2 * kCookieSize) > size); |
- size += 2 * kCookieSize; |
-#endif |
- return size; |
-} |
- |
-ALWAYS_INLINE size_t partitionCookieSizeAdjustSubtract(size_t size) { |
-#if ENABLE(ASSERT) |
- // Remove space for cookies. |
- ASSERT(size >= 2 * kCookieSize); |
- size -= 2 * kCookieSize; |
-#endif |
- return size; |
-} |
- |
-ALWAYS_INLINE void* partitionCookieFreePointerAdjust(void* ptr) { |
-#if ENABLE(ASSERT) |
- // 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 ENABLE(ASSERT) |
- unsigned char* cookiePtr = reinterpret_cast<unsigned char*>(ptr); |
- for (size_t i = 0; i < kCookieSize; ++i, ++cookiePtr) |
- *cookiePtr = kCookieValue[i]; |
-#endif |
-} |
- |
-ALWAYS_INLINE void partitionCookieCheckValue(void* ptr) { |
-#if ENABLE(ASSERT) |
- unsigned char* cookiePtr = reinterpret_cast<unsigned char*>(ptr); |
- for (size_t i = 0; i < kCookieSize; ++i, ++cookiePtr) |
- ASSERT(*cookiePtr == kCookieValue[i]); |
-#endif |
-} |
- |
-ALWAYS_INLINE char* partitionSuperPageToMetadataArea(char* ptr) { |
- uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(ptr); |
- ASSERT(!(pointerAsUint & kSuperPageOffsetMask)); |
- // The metadata area is exactly one system page (the guard page) into the |
- // super page. |
- return reinterpret_cast<char*>(pointerAsUint + kSystemPageSize); |
-} |
- |
-ALWAYS_INLINE PartitionPage* partitionPointerToPageNoAlignmentCheck(void* ptr) { |
- uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(ptr); |
- char* superPagePtr = |
- reinterpret_cast<char*>(pointerAsUint & kSuperPageBaseMask); |
- uintptr_t partitionPageIndex = |
- (pointerAsUint & 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. |
- ASSERT(partitionPageIndex); |
- ASSERT(partitionPageIndex < kNumPartitionPagesPerSuperPage - 1); |
- PartitionPage* page = reinterpret_cast<PartitionPage*>( |
- partitionSuperPageToMetadataArea(superPagePtr) + |
- (partitionPageIndex << kPageMetadataShift)); |
- // Partition pages in the same slot span can share the same page object. |
- // Adjust for that. |
- size_t delta = page->pageOffset << kPageMetadataShift; |
- page = |
- reinterpret_cast<PartitionPage*>(reinterpret_cast<char*>(page) - delta); |
- return page; |
-} |
- |
-ALWAYS_INLINE void* partitionPageToPointer(const PartitionPage* page) { |
- uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(page); |
- uintptr_t superPageOffset = (pointerAsUint & kSuperPageOffsetMask); |
- ASSERT(superPageOffset > kSystemPageSize); |
- ASSERT(superPageOffset < kSystemPageSize + (kNumPartitionPagesPerSuperPage * |
- kPageMetadataSize)); |
- uintptr_t partitionPageIndex = |
- (superPageOffset - kSystemPageSize) >> kPageMetadataShift; |
- // Index 0 is invalid because it is the metadata area and the last index is |
- // invalid because it is a guard page. |
- ASSERT(partitionPageIndex); |
- ASSERT(partitionPageIndex < kNumPartitionPagesPerSuperPage - 1); |
- uintptr_t superPageBase = (pointerAsUint & kSuperPageBaseMask); |
- void* ret = reinterpret_cast<void*>( |
- superPageBase + (partitionPageIndex << kPartitionPageShift)); |
- return ret; |
-} |
- |
-ALWAYS_INLINE PartitionPage* partitionPointerToPage(void* ptr) { |
- PartitionPage* page = partitionPointerToPageNoAlignmentCheck(ptr); |
- // Checks that the pointer is a multiple of bucket size. |
- ASSERT(!((reinterpret_cast<uintptr_t>(ptr) - |
- reinterpret_cast<uintptr_t>(partitionPageToPointer(page))) % |
- page->bucket->slotSize)); |
- return page; |
-} |
- |
-ALWAYS_INLINE bool partitionBucketIsDirectMapped( |
- const PartitionBucket* bucket) { |
- return !bucket->numSystemPagesPerSlotSpan; |
-} |
- |
-ALWAYS_INLINE size_t partitionBucketBytes(const PartitionBucket* bucket) { |
- return bucket->numSystemPagesPerSlotSpan * kSystemPageSize; |
-} |
- |
-ALWAYS_INLINE uint16_t partitionBucketSlots(const PartitionBucket* bucket) { |
- return static_cast<uint16_t>(partitionBucketBytes(bucket) / bucket->slotSize); |
-} |
- |
-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->slotSize <= kMaxSystemPagesPerSlotSpan * kSystemPageSize) |
- return nullptr; |
- |
- ASSERT((bucket->slotSize % kSystemPageSize) == 0); |
- ASSERT(partitionBucketIsDirectMapped(bucket) || |
- partitionBucketSlots(bucket) == 1); |
- page++; |
- return reinterpret_cast<size_t*>(&page->freelistHead); |
-} |
- |
-ALWAYS_INLINE size_t partitionPageGetRawSize(PartitionPage* page) { |
- size_t* rawSizePtr = partitionPageGetRawSizePtr(page); |
- if (UNLIKELY(rawSizePtr != nullptr)) |
- return *rawSizePtr; |
- return 0; |
-} |
- |
-ALWAYS_INLINE PartitionRootBase* partitionPageToRoot(PartitionPage* page) { |
- PartitionSuperPageExtentEntry* extentEntry = |
- reinterpret_cast<PartitionSuperPageExtentEntry*>( |
- reinterpret_cast<uintptr_t>(page) & kSystemPageBaseMask); |
- return extentEntry->root; |
-} |
- |
-ALWAYS_INLINE bool partitionPointerIsValid(void* ptr) { |
- PartitionPage* page = partitionPointerToPage(ptr); |
- PartitionRootBase* root = partitionPageToRoot(page); |
- return root->invertedSelf == ~reinterpret_cast<uintptr_t>(root); |
-} |
- |
-ALWAYS_INLINE void* partitionBucketAlloc(PartitionRootBase* root, |
- int flags, |
- size_t size, |
- PartitionBucket* bucket) { |
- PartitionPage* page = bucket->activePagesHead; |
- // Check that this page is neither full nor freed. |
- ASSERT(page->numAllocatedSlots >= 0); |
- void* ret = page->freelistHead; |
- if (LIKELY(ret != 0)) { |
- // If these asserts fire, you probably corrupted memory. |
- ASSERT(partitionPointerIsValid(ret)); |
- // All large allocations must go through the slow path to correctly |
- // update the size metadata. |
- ASSERT(partitionPageGetRawSize(page) == 0); |
- PartitionFreelistEntry* newHead = |
- partitionFreelistMask(static_cast<PartitionFreelistEntry*>(ret)->next); |
- page->freelistHead = newHead; |
- page->numAllocatedSlots++; |
- } else { |
- ret = partitionAllocSlowPath(root, flags, size, bucket); |
- ASSERT(!ret || partitionPointerIsValid(ret)); |
- } |
-#if ENABLE(ASSERT) |
- if (!ret) |
- return 0; |
- // Fill the uninitialized pattern, and write the cookies. |
- page = partitionPointerToPage(ret); |
- size_t slotSize = page->bucket->slotSize; |
- size_t rawSize = partitionPageGetRawSize(page); |
- if (rawSize) { |
- ASSERT(rawSize == size); |
- slotSize = rawSize; |
- } |
- size_t noCookieSize = partitionCookieSizeAdjustSubtract(slotSize); |
- char* charRet = static_cast<char*>(ret); |
- // The value given to the application is actually just after the cookie. |
- ret = charRet + kCookieSize; |
- memset(ret, kUninitializedByte, noCookieSize); |
- partitionCookieWriteValue(charRet); |
- partitionCookieWriteValue(charRet + kCookieSize + noCookieSize); |
-#endif |
- return ret; |
-} |
- |
-ALWAYS_INLINE void* partitionAlloc(PartitionRoot* root, |
- size_t size, |
- const char* typeName) { |
-#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
- void* result = malloc(size); |
- RELEASE_ASSERT(result); |
- return result; |
-#else |
- size_t requestedSize = size; |
- size = partitionCookieSizeAdjustAdd(size); |
- ASSERT(root->initialized); |
- size_t index = size >> kBucketShift; |
- ASSERT(index < root->numBuckets); |
- ASSERT(size == index << kBucketShift); |
- PartitionBucket* bucket = &root->buckets()[index]; |
- void* result = partitionBucketAlloc(root, 0, size, bucket); |
- PartitionAllocHooks::allocationHookIfEnabled(result, requestedSize, typeName); |
- 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 ENABLE(ASSERT) |
- size_t slotSize = page->bucket->slotSize; |
- size_t rawSize = partitionPageGetRawSize(page); |
- if (rawSize) |
- slotSize = rawSize; |
- partitionCookieCheckValue(ptr); |
- partitionCookieCheckValue(reinterpret_cast<char*>(ptr) + slotSize - |
- kCookieSize); |
- memset(ptr, kFreedByte, slotSize); |
-#endif |
- ASSERT(page->numAllocatedSlots); |
- PartitionFreelistEntry* freelistHead = page->freelistHead; |
- ASSERT(!freelistHead || partitionPointerIsValid(freelistHead)); |
- SECURITY_CHECK(ptr != freelistHead); // Catches an immediate double free. |
- // Look for double free one level deeper in debug. |
- SECURITY_DCHECK(!freelistHead || |
- ptr != partitionFreelistMask(freelistHead->next)); |
- PartitionFreelistEntry* entry = static_cast<PartitionFreelistEntry*>(ptr); |
- entry->next = partitionFreelistMask(freelistHead); |
- page->freelistHead = entry; |
- --page->numAllocatedSlots; |
- if (UNLIKELY(page->numAllocatedSlots <= 0)) { |
- partitionFreeSlowPath(page); |
- } else { |
- // All single-slot allocations must go through the slow path to |
- // correctly update the size metadata. |
- ASSERT(partitionPageGetRawSize(page) == 0); |
- } |
-} |
- |
-ALWAYS_INLINE void partitionFree(void* ptr) { |
-#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
- free(ptr); |
-#else |
- PartitionAllocHooks::freeHookIfEnabled(ptr); |
- ptr = partitionCookieFreePointerAdjust(ptr); |
- ASSERT(partitionPointerIsValid(ptr)); |
- PartitionPage* page = partitionPointerToPage(ptr); |
- partitionFreeWithPage(ptr, page); |
-#endif |
-} |
- |
-ALWAYS_INLINE PartitionBucket* partitionGenericSizeToBucket( |
- PartitionRootGeneric* root, |
- size_t size) { |
- size_t order = kBitsPerSizet - CountLeadingZeroBitsSizeT(size); |
- // The order index is simply the next few bits after the most significant bit. |
- size_t orderIndex = (size >> root->orderIndexShifts[order]) & |
- (kGenericNumBucketsPerOrder - 1); |
- // And if the remaining bits are non-zero we must bump the bucket up. |
- size_t subOrderIndex = size & root->orderSubIndexMasks[order]; |
- PartitionBucket* bucket = |
- root->bucketLookups[(order << kGenericNumBucketsPerOrderBits) + |
- orderIndex + !!subOrderIndex]; |
- ASSERT(!bucket->slotSize || bucket->slotSize >= size); |
- ASSERT(!(bucket->slotSize % kGenericSmallestBucket)); |
- return bucket; |
-} |
- |
-ALWAYS_INLINE void* partitionAllocGenericFlags(PartitionRootGeneric* root, |
- int flags, |
- size_t size, |
- const char* typeName) { |
-#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
- void* result = malloc(size); |
- RELEASE_ASSERT(result || flags & PartitionAllocReturnNull); |
- return result; |
-#else |
- ASSERT(root->initialized); |
- size_t requestedSize = size; |
- size = partitionCookieSizeAdjustAdd(size); |
- PartitionBucket* bucket = partitionGenericSizeToBucket(root, size); |
- void* ret = nullptr; |
- { |
- SpinLock::Guard guard(root->lock); |
- ret = partitionBucketAlloc(root, flags, size, bucket); |
- } |
- PartitionAllocHooks::allocationHookIfEnabled(ret, requestedSize, typeName); |
- return ret; |
-#endif |
-} |
- |
-ALWAYS_INLINE void* partitionAllocGeneric(PartitionRootGeneric* root, |
- size_t size, |
- const char* typeName) { |
- return partitionAllocGenericFlags(root, 0, size, typeName); |
-} |
- |
-ALWAYS_INLINE void partitionFreeGeneric(PartitionRootGeneric* root, void* ptr) { |
-#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
- free(ptr); |
-#else |
- ASSERT(root->initialized); |
- |
- if (UNLIKELY(!ptr)) |
- return; |
- |
- PartitionAllocHooks::freeHookIfEnabled(ptr); |
- ptr = partitionCookieFreePointerAdjust(ptr); |
- ASSERT(partitionPointerIsValid(ptr)); |
- PartitionPage* page = partitionPointerToPage(ptr); |
- { |
- SpinLock::Guard guard(root->lock); |
- partitionFreeWithPage(ptr, page); |
- } |
-#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. |
- ASSERT(size <= kGenericMaxDirectMapped); |
- return (size + kSystemPageOffsetMask) & kSystemPageBaseMask; |
-} |
- |
-ALWAYS_INLINE size_t partitionAllocActualSize(PartitionRootGeneric* root, |
- size_t size) { |
-#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
- return size; |
-#else |
- ASSERT(root->initialized); |
- size = partitionCookieSizeAdjustAdd(size); |
- PartitionBucket* bucket = partitionGenericSizeToBucket(root, size); |
- if (LIKELY(!partitionBucketIsDirectMapped(bucket))) { |
- size = bucket->slotSize; |
- } else if (size > kGenericMaxDirectMapped) { |
- // Too large to allocate => return the size unchanged. |
- } else { |
- ASSERT(bucket == &PartitionRootBase::gPagedBucket); |
- size = partitionDirectMapSize(size); |
- } |
- return 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. |
- ASSERT(partitionAllocSupportsGetSize()); |
- ptr = partitionCookieFreePointerAdjust(ptr); |
- ASSERT(partitionPointerIsValid(ptr)); |
- PartitionPage* page = partitionPointerToPage(ptr); |
- size_t size = page->bucket->slotSize; |
- 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: |
- static const size_t kMaxAllocation = N - kAllocationGranularity; |
- static const size_t kNumBuckets = N / kAllocationGranularity; |
- void init() { |
- partitionAllocInit(&m_partitionRoot, kNumBuckets, kMaxAllocation); |
- } |
- bool shutdown() { return partitionAllocShutdown(&m_partitionRoot); } |
- ALWAYS_INLINE PartitionRoot* root() { return &m_partitionRoot; } |
- |
- private: |
- PartitionRoot m_partitionRoot; |
- PartitionBucket m_actualBuckets[kNumBuckets]; |
-}; |
- |
-class PartitionAllocatorGeneric { |
- public: |
- void init() { partitionAllocGenericInit(&m_partitionRoot); } |
- bool shutdown() { return partitionAllocGenericShutdown(&m_partitionRoot); } |
- ALWAYS_INLINE PartitionRootGeneric* root() { return &m_partitionRoot; } |
- |
- private: |
- PartitionRootGeneric m_partitionRoot; |
-}; |
- |
-} // namespace WTF |
- |
-using WTF::SizeSpecificPartitionAllocator; |
-using WTF::PartitionAllocatorGeneric; |
-using WTF::PartitionRoot; |
-using WTF::partitionAllocInit; |
-using WTF::partitionAllocShutdown; |
-using WTF::partitionAlloc; |
-using WTF::partitionFree; |
-using WTF::partitionAllocGeneric; |
-using WTF::partitionFreeGeneric; |
-using WTF::partitionReallocGeneric; |
-using WTF::partitionAllocActualSize; |
-using WTF::partitionAllocSupportsGetSize; |
-using WTF::partitionAllocGetSize; |
- |
-#endif // WTF_PartitionAlloc_h |