15267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)/* 25267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * Copyright (C) 2013 Google Inc. All rights reserved. 35267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * 45267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * modification, are permitted provided that the following conditions are 65267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * met: 75267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * 85267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * * Redistributions of source code must retain the above copyright 95267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * * Redistributions in binary form must reproduce the above 115267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer 125267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * in the documentation and/or other materials provided with the 135267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * distribution. 145267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * * Neither the name of Google Inc. nor the names of its 155267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * contributors may be used to endorse or promote products derived from 165267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * this software without specific prior written permission. 175267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * 185267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) */ 305267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 315267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#ifndef WTF_PartitionAlloc_h 325267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#define WTF_PartitionAlloc_h 335267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 345267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// DESCRIPTION 3509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// partitionAlloc() / partitionAllocGeneric() and partitionFree() / 3609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// partitionFreeGeneric() are approximately analagous to malloc() and free(). 378abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)// 3809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// The main difference is that a PartitionRoot / PartitionRootGeneric object 3909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// must be supplied to these functions, representing a specific "heap partition" 4009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// that will be used to satisfy the allocation. Different partitions are 4109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// guaranteed to exist in separate address spaces, including being separate from 4209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// the main system heap. If the contained objects are all freed, physical memory 4309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// is returned to the system but the address space remains reserved. 445267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// 458abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)// THE ONLY LEGITIMATE WAY TO OBTAIN A PartitionRoot IS THROUGH THE 4609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// SizeSpecificPartitionAllocator / PartitionAllocatorGeneric classes. To 4709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// minimize the instruction count to the fullest extent possible, the 4809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// PartitonRoot is really just a header adjacent to other data areas provided 4909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// by the allocator class. 508abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)// 5109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// The partitionAlloc() variant of the API has the following caveats: 5209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Allocations and frees against a single partition must be single threaded. 5309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Allocations must not exceed a max size, chosen at compile-time via a 5409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// templated parameter to PartitionAllocator. 5509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Allocation sizes must be aligned to the system pointer size. 5609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Allocations are bucketed exactly according to size. 575267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// 5809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// And for partitionAllocGeneric(): 5909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Multi-threaded use against a single partition is ok; locking is handled. 6009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Allocations of any arbitrary size can be handled (subject to a limit of 6109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// INT_MAX bytes for security reasons). 6209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Bucketing is by approximate size, for example an allocation of 4000 bytes 6309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// might be placed into a 4096-byte bucket. Bucket sizes are chosen to try and 6409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// keep worst-case waste to ~10%. 6509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// 6609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// The allocators are designed to be extremely fast, thanks to the following 675267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// properties and design: 685267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - Just a single (reasonably predicatable) branch in the hot / fast path for 695267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// both allocating and (significantly) freeing. 705267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - A minimal number of operations in the hot / fast path, with the slow paths 715267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// in separate functions, leading to the possibility of inlining. 7209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Each partition page (which is usually multiple physical pages) has a 7309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// metadata structure which allows fast mapping of free() address to an 7409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// underlying bucket. 751fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch// - Supports a lock-free API for fast performance in single-threaded cases. 76521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles)// - The freelist for a given bucket is split across a number of partition 77521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles)// pages, enabling various simple tricks to try and minimize fragmentation. 785267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - Fine-grained bucket sizes leading to less waste and better packing. 795267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// 805267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// The following security properties are provided at this time: 815267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - Linear overflows cannot corrupt into the partition. 825267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - Linear overflows cannot corrupt out of the partition. 835267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - Freed pages will only be re-used within the partition. 8409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// (exception: large allocations > ~1MB) 855267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - Freed pages will only hold same-sized objects when re-used. 86bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)// - Dereference of freelist pointer should fault. 87a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// - Out-of-line main metadata: linear over or underflow cannot corrupt it. 88bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)// - Partial pointer overwrite of freelist pointer should fault. 89bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)// - Rudimentary double-free detection. 9009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// - Large allocations (> ~1MB) are guard-paged at the beginning and end. 915267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// 925267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// The following security properties could be investigated in the future: 935267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - Per-object bucketing (instead of per-size) is mostly available at the API, 945267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// but not used yet. 955267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// - No randomness of freelist entries or bucket position. 96a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// - Better checking for wild pointers in free(). 97f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)// - Better freelist masking function to guarantee fault on 32-bit. 985267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 995267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#include "wtf/Assertions.h" 10009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include "wtf/BitwiseOperations.h" 101bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)#include "wtf/ByteSwap.h" 102bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)#include "wtf/CPU.h" 1031e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "wtf/PageAllocator.h" 1041fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#include "wtf/SpinLock.h" 1055267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 10609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include <limits.h> 10709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 108c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 1095267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#include <stdlib.h> 110c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles)#endif 1115267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 112197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 113f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#include <string.h> 114f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#endif 115f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) 1165267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)namespace WTF { 1175267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 118a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// Maximum size of a partition's mappings. 2046MB. Note that the total amount of 1191e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)// bytes allocatable at the API will be smaller. This is because things like 1201e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)// guard pages, metadata, page headers and wasted space come out of the total. 121a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// The 2GB is not necessarily contiguous in virtual address space. 122a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kMaxPartitionSize = 2046u * 1024u * 1024u; 12309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 1245267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)// Allocation granularity of sizeof(void*) bytes. 1251fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdochstatic const size_t kAllocationGranularity = sizeof(void*); 1261fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdochstatic const size_t kAllocationGranularityMask = kAllocationGranularity - 1; 1271fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdochstatic const size_t kBucketShift = (kAllocationGranularity == 8) ? 3 : 2; 12809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 129521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles)// Underlying partition storage pages are a power-of-two size. It is typical 13009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// for a partition page to be based on multiple system pages. Most references to 13109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// "page" refer to partition pages. 132d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)// We also have the concept of "super pages" -- these are the underlying system 133d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)// allocations we make. Super pages contain multiple partition pages inside them 13409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// and include space for a small amount of metadata per partition page. 13509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Inside super pages, we store "slot spans". A slot span is a continguous range 13609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// of one or more partition pages that stores allocations of the same size. 13709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Slot span sizes are adjusted depending on the allocation size, to make sure 13809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// the packing does not lead to unused (wasted) space at the end of the last 13909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// system page of the span. For our current max slot span size of 64k and other 14009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// constant values, we pack _all_ partitionAllocGeneric() sizes perfectly up 14109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// against the end of a system page. 142a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kPartitionPageShift = 14; // 16KB 143a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kPartitionPageSize = 1 << kPartitionPageShift; 144521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles)static const size_t kPartitionPageOffsetMask = kPartitionPageSize - 1; 145521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles)static const size_t kPartitionPageBaseMask = ~kPartitionPageOffsetMask; 14609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kMaxPartitionPagesPerSlotSpan = 4; 14709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 14806f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)// To avoid fragmentation via never-used freelist entries, we hand out partition 149a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// freelist sections gradually, in units of the dominant system page size. 15006f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)// What we're actually doing is avoiding filling the full partition page 15106f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)// (typically 16KB) will freelist pointers right away. Writing freelist 15206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)// pointers will fault and dirty a private page, which is very wasteful if we 15306f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles)// never actually store objects there. 154a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kNumSystemPagesPerPartitionPage = kPartitionPageSize / kSystemPageSize; 15509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kMaxSystemPagesPerSlotSpan = kNumSystemPagesPerPartitionPage * kMaxPartitionPagesPerSlotSpan; 156a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 157a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// We reserve virtual address space in 2MB chunks (aligned to 2MB as well). 158a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// These chunks are called "super pages". We do this so that we can store 159a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// metadata in the first few pages of each 2MB aligned section. This leads to 160a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// a very fast free(). We specifically choose 2MB because this virtual address 161a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// block represents a full but single PTE allocation on ARM, ia32 and x64. 162a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kSuperPageShift = 21; // 2MB 163a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kSuperPageSize = 1 << kSuperPageShift; 164a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kSuperPageOffsetMask = kSuperPageSize - 1; 165a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kSuperPageBaseMask = ~kSuperPageOffsetMask; 166a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kNumPartitionPagesPerSuperPage = kSuperPageSize / kPartitionPageSize; 167a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 168a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kPageMetadataShift = 5; // 32 bytes per partition page. 169a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)static const size_t kPageMetadataSize = 1 << kPageMetadataShift; 1705267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 17109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// The following kGeneric* constants apply to the generic variants of the API. 17209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// The "order" of an allocation is closely related to the power-of-two size of 17309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// the allocation. More precisely, the order is the bit index of the 17409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// most-significant-bit in the allocation size, where the bit numbers starts 17509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// at index 1 for the least-significant-bit. 17609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// In terms of allocation sizes, order 0 covers 0, order 1 covers 1, order 2 17709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// covers 2->3, order 3 covers 4->7, order 4 covers 8->15. 17809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kGenericMinBucketedOrder = 4; // 8 bytes. 17909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kGenericMaxBucketedOrder = 20; // Largest bucketed order is 1<<(20-1) (storing 512KB -> almost 1MB) 18009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kGenericNumBucketedOrders = (kGenericMaxBucketedOrder - kGenericMinBucketedOrder) + 1; 18109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kGenericNumBucketsPerOrderBits = 3; // Eight buckets per order (for the higher orders), e.g. order 8 is 128, 144, 160, ..., 240 18209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kGenericNumBucketsPerOrder = 1 << kGenericNumBucketsPerOrderBits; 18309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kGenericSmallestBucket = 1 << (kGenericMinBucketedOrder - 1); 18409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kGenericMaxBucketSpacing = 1 << ((kGenericMaxBucketedOrder - 1) - kGenericNumBucketsPerOrderBits); 18509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kGenericMaxBucketed = (1 << (kGenericMaxBucketedOrder - 1)) + ((kGenericNumBucketsPerOrder - 1) * kGenericMaxBucketSpacing); 186f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liustatic const size_t kGenericMinDirectMappedDownsize = kGenericMaxBucketed + 1; // Limit when downsizing a direct mapping using realloc(). 187d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)static const size_t kGenericMaxDirectMapped = INT_MAX - kSystemPageSize; 18809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kBitsPerSizet = sizeof(void*) * CHAR_BIT; 18909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 19009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Constants for the memory reclaim logic. 19109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kMaxFreeableSpans = 16; 19209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 193197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 194f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)// These two byte values match tcmalloc. 195f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)static const unsigned char kUninitializedByte = 0xAB; 196f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)static const unsigned char kFreedByte = 0xCD; 19709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const uint32_t kCookieValue = 0xDEADBEEFu; 19809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static const size_t kCookieSize = 16; // Handles alignment up to XMM instructions on Intel. 199f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#endif 200f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) 2015267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)struct PartitionBucket; 20209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)struct PartitionRootBase; 2035267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 2045267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)struct PartitionFreelistEntry { 2055267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) PartitionFreelistEntry* next; 2065267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)}; 2075267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 208a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// Some notes on page states. A page can be in one of three major states: 209a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// 1) Active. 210a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// 2) Full. 211a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// 3) Free. 212a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// An active page has available free slots. A full page has no free slots. A 213a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// free page has had its backing memory released back to the system. 214a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// There are two linked lists tracking the pages. The "active page" list is an 215a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// approximation of a list of active pages. It is an approximation because both 216a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// free and full pages may briefly be present in the list until we next do a 217a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// scan over it. The "free page" list is an accurate list of pages which have 218a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// been returned back to the system. 219a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// The significant page transitions are: 220a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// - free() will detect when a full page has a slot free()'d and immediately 221a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// return the page to the head of the active list. 222a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// - free() will detect when a page is fully emptied. It _may_ add it to the 223a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// free list and it _may_ leave it on the active list until a future list scan. 224a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// - malloc() _may_ scan the active page list in order to fulfil the request. 225a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// If it does this, full and free pages encountered will be booted out of the 226a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// active list. If there are no suitable active pages found, a free page (if one 227a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// exists) will be pulled from the free list on to the active list. 228a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)struct PartitionPage { 22909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionFreelistEntry* freelistHead; 23009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* nextPage; 2315267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) PartitionBucket* bucket; 23209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) int16_t numAllocatedSlots; // Deliberately signed, -1 for free page, -n for full pages. 23309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) uint16_t numUnprovisionedSlots; 23409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) uint16_t pageOffset; 23509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) int16_t freeCacheIndex; // -1 if not in the free cache. 2365267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)}; 2375267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 2385267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)struct PartitionBucket { 239a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionPage* activePagesHead; // Accessed most in hot path => goes first. 240a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionPage* freePagesHead; 24109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) uint32_t slotSize; 24209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) uint16_t numSystemPagesPerSlotSpan; 24309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) uint16_t numFullPages; 2445267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)}; 2455267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 246a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// An "extent" is a span of consecutive superpages. We link to the partition's 247a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// next extent (if there is one) at the very start of a superpage's metadata 248a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)// area. 2491e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)struct PartitionSuperPageExtentEntry { 25009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionRootBase* root; 2511e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) char* superPageBase; 2521e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) char* superPagesEnd; 2531e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) PartitionSuperPageExtentEntry* next; 2541e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)}; 2551e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 25609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)struct WTF_EXPORT PartitionRootBase { 2575d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) size_t totalSizeOfCommittedPages; 2581e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t totalSizeOfSuperPages; 2598abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) unsigned numBuckets; 2608abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) unsigned maxAllocation; 2618abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) bool initialized; 262521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) char* nextSuperPage; 263521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) char* nextPartitionPage; 264521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) char* nextPartitionPageEnd; 2651e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) PartitionSuperPageExtentEntry* currentExtent; 26609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionSuperPageExtentEntry* firstExtent; 26709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* globalEmptyPageRing[kMaxFreeableSpans]; 26809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t globalEmptyPageRingIndex; 26909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) uintptr_t invertedSelf; 27009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 27109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) static int gInitializedLock; 27209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) static bool gInitialized; 27309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) static PartitionPage gSeedPage; 27409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) static PartitionBucket gPagedBucket; 27509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}; 2768abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 27709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Never instantiate a PartitionRoot directly, instead use PartitionAlloc. 27809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)struct PartitionRoot : public PartitionRootBase { 2798abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) // The PartitionAlloc templated class ensures the following is correct. 2808abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) ALWAYS_INLINE PartitionBucket* buckets() { return reinterpret_cast<PartitionBucket*>(this + 1); } 2818abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) ALWAYS_INLINE const PartitionBucket* buckets() const { return reinterpret_cast<const PartitionBucket*>(this + 1); } 2825267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)}; 2835267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 28409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Never instantiate a PartitionRootGeneric directly, instead use PartitionAllocatorGeneric. 28509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)struct PartitionRootGeneric : public PartitionRootBase { 28609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) int lock; 28709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Some pre-computed constants. 28809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t orderIndexShifts[kBitsPerSizet + 1]; 28909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t orderSubIndexMasks[kBitsPerSizet + 1]; 29009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // The bucket lookup table lets us map a size_t to a bucket quickly. 29109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // The trailing +1 caters for the overflow case for very large allocation sizes. 29209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // It is one flat array instead of a 2D array because in the 2D world, we'd 29309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // need to index array[blah][max+1] which risks undefined behavior. 29409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket* bucketLookups[((kBitsPerSizet + 1) * kGenericNumBucketsPerOrder) + 1]; 29509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket buckets[kGenericNumBucketedOrders * kGenericNumBucketsPerOrder]; 296a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)}; 297a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 29809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Flags for partitionAllocGenericFlags. 29909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)enum PartitionAllocFlags { 30009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionAllocReturnNull = 1 << 0, 301a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)}; 302a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 30309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)WTF_EXPORT void partitionAllocInit(PartitionRoot*, size_t numBuckets, size_t maxAllocation); 30409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)WTF_EXPORT bool partitionAllocShutdown(PartitionRoot*); 30509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)WTF_EXPORT void partitionAllocGenericInit(PartitionRootGeneric*); 30609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)WTF_EXPORT bool partitionAllocGenericShutdown(PartitionRootGeneric*); 30709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 30809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)WTF_EXPORT NEVER_INLINE void* partitionAllocSlowPath(PartitionRootBase*, int, size_t, PartitionBucket*); 30909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)WTF_EXPORT NEVER_INLINE void partitionFreeSlowPath(PartitionPage*); 31009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)WTF_EXPORT NEVER_INLINE void* partitionReallocGeneric(PartitionRootGeneric*, void*, size_t); 311a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 312d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)#ifndef NDEBUG 313d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)WTF_EXPORT void partitionDumpStats(const PartitionRoot&); 314d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)#endif 315d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) 3165267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)ALWAYS_INLINE PartitionFreelistEntry* partitionFreelistMask(PartitionFreelistEntry* ptr) 3175267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 318bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // We use bswap on little endian as a fast mask for two reasons: 319bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // 1) If an object is freed and its vtable used where the attacker doesn't 320bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // get the chance to run allocations between the free and use, the vtable 321bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // dereference is likely to fault. 322bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // 2) If the attacker has a linear buffer overflow and elects to try and 323bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // corrupt a freelist pointer, partial pointer overwrite attacks are 324bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // thwarted. 325bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // For big endian, similar guarantees are arrived at with a negation. 326bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)#if CPU(BIG_ENDIAN) 3275267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) uintptr_t masked = ~reinterpret_cast<uintptr_t>(ptr); 328bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)#else 329bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) uintptr_t masked = bswapuintptrt(reinterpret_cast<uintptr_t>(ptr)); 330bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)#endif 3315267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) return reinterpret_cast<PartitionFreelistEntry*>(masked); 3325267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 3335267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 33419cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)ALWAYS_INLINE size_t partitionCookieSizeAdjustAdd(size_t size) 335f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles){ 336197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 33709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Add space for cookies, checking for integer overflow. 33809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(size + (2 * kCookieSize) > size); 33909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size += 2 * kCookieSize; 340f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#endif 341f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) return size; 342f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)} 343f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) 34419cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)ALWAYS_INLINE size_t partitionCookieSizeAdjustSubtract(size_t size) 34519cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles){ 346197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 34719cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) // Remove space for cookies. 34809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(size >= 2 * kCookieSize); 34909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size -= 2 * kCookieSize; 35019cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)#endif 35119cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) return size; 35219cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles)} 35319cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) 354f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)ALWAYS_INLINE void* partitionCookieFreePointerAdjust(void* ptr) 355f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles){ 356197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 357f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) // The value given to the application is actually just after the cookie. 35809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ptr = static_cast<char*>(ptr) - kCookieSize; 359f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#endif 360f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) return ptr; 361f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)} 362f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) 36309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE void partitionCookieWriteValue(void* ptr) 3645267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 365197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 36609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) uint32_t* cookiePtr = reinterpret_cast<uint32_t*>(ptr); 36709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (size_t i = 0; i < kCookieSize / sizeof(kCookieValue); ++i, ++cookiePtr) 36809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) *cookiePtr = kCookieValue; 36909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif 37009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 37109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 37209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE void partitionCookieCheckValue(void* ptr) 37309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 374197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 37509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) uint32_t* cookiePtr = reinterpret_cast<uint32_t*>(ptr); 37609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) for (size_t i = 0; i < kCookieSize / sizeof(kCookieValue); ++i, ++cookiePtr) 37709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(*cookiePtr == kCookieValue); 37809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif 3795267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 3805267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 381a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)ALWAYS_INLINE char* partitionSuperPageToMetadataArea(char* ptr) 382a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles){ 383a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(ptr); 384a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) ASSERT(!(pointerAsUint & kSuperPageOffsetMask)); 385a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // The metadata area is exactly one system page (the guard page) into the 386a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // super page. 387a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) return reinterpret_cast<char*>(pointerAsUint + kSystemPageSize); 388a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)} 389a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 390a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)ALWAYS_INLINE PartitionPage* partitionPointerToPageNoAlignmentCheck(void* ptr) 391bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles){ 392bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(ptr); 393a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) char* superPagePtr = reinterpret_cast<char*>(pointerAsUint & kSuperPageBaseMask); 394a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) uintptr_t partitionPageIndex = (pointerAsUint & kSuperPageOffsetMask) >> kPartitionPageShift; 395a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // Index 0 is invalid because it is the metadata area and the last index is invalid because it is a guard page. 396a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) ASSERT(partitionPageIndex); 397a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) ASSERT(partitionPageIndex < kNumPartitionPagesPerSuperPage - 1); 398a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionPage* page = reinterpret_cast<PartitionPage*>(partitionSuperPageToMetadataArea(superPagePtr) + (partitionPageIndex << kPageMetadataShift)); 39909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Many partition pages can share the same page object. Adjust for that. 40009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t delta = page->pageOffset << kPageMetadataShift; 40109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page = reinterpret_cast<PartitionPage*>(reinterpret_cast<char*>(page) - delta); 402bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) return page; 403bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)} 404bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 405a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)ALWAYS_INLINE void* partitionPageToPointer(PartitionPage* page) 406a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles){ 407a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(page); 408a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) uintptr_t superPageOffset = (pointerAsUint & kSuperPageOffsetMask); 409a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) ASSERT(superPageOffset > kSystemPageSize); 410a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) ASSERT(superPageOffset < kSystemPageSize + (kNumPartitionPagesPerSuperPage * kPageMetadataSize)); 411a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) uintptr_t partitionPageIndex = (superPageOffset - kSystemPageSize) >> kPageMetadataShift; 412a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) // Index 0 is invalid because it is the metadata area and the last index is invalid because it is a guard page. 413a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) ASSERT(partitionPageIndex); 414a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) ASSERT(partitionPageIndex < kNumPartitionPagesPerSuperPage - 1); 415a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) uintptr_t superPageBase = (pointerAsUint & kSuperPageBaseMask); 416a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) void* ret = reinterpret_cast<void*>(superPageBase + (partitionPageIndex << kPartitionPageShift)); 417a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) return ret; 418a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)} 419a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 42009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE PartitionPage* partitionPointerToPage(void* ptr) 421a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles){ 42209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* page = partitionPointerToPageNoAlignmentCheck(ptr); 42309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // Checks that the pointer is a multiple of bucket size. 42409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!((reinterpret_cast<uintptr_t>(ptr) - reinterpret_cast<uintptr_t>(partitionPageToPointer(page))) % page->bucket->slotSize)); 42509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return page; 426a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)} 427a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 42809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE PartitionRootBase* partitionPageToRoot(PartitionPage* page) 429a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles){ 43009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionSuperPageExtentEntry* extentEntry = reinterpret_cast<PartitionSuperPageExtentEntry*>(reinterpret_cast<uintptr_t>(page) & kSystemPageBaseMask); 43109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return extentEntry->root; 432a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)} 433a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 43409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE bool partitionPointerIsValid(void* ptr) 435bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles){ 43609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* page = partitionPointerToPage(ptr); 43709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionRootBase* root = partitionPageToRoot(page); 43809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return root->invertedSelf == ~reinterpret_cast<uintptr_t>(root); 439bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)} 440bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 44109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE void* partitionBucketAlloc(PartitionRootBase* root, int flags, size_t size, PartitionBucket* bucket) 4425267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 443a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionPage* page = bucket->activePagesHead; 44409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->numAllocatedSlots >= 0); 44509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void* ret = page->freelistHead; 4465267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) if (LIKELY(ret != 0)) { 447bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // If these asserts fire, you probably corrupted memory. 44809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(partitionPointerIsValid(ret)); 449a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionFreelistEntry* newHead = partitionFreelistMask(static_cast<PartitionFreelistEntry*>(ret)->next); 45009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freelistHead = newHead; 45109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!ret || partitionPointerIsValid(ret)); 4525267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) page->numAllocatedSlots++; 453f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) } else { 45409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ret = partitionAllocSlowPath(root, flags, size, bucket); 4555267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) } 456197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 45709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (!ret) 45809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return 0; 459f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) // Fill the uninitialized pattern. and write the cookies. 46009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page = partitionPointerToPage(ret); 46109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t bucketSize = page->bucket->slotSize; 462f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) memset(ret, kUninitializedByte, bucketSize); 46309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionCookieWriteValue(ret); 46409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionCookieWriteValue(reinterpret_cast<char*>(ret) + bucketSize - kCookieSize); 465f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) // The value given to the application is actually just after the cookie. 46609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ret = static_cast<char*>(ret) + kCookieSize; 467f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#endif 468f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) return ret; 4695267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 4705267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 4715267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)ALWAYS_INLINE void* partitionAlloc(PartitionRoot* root, size_t size) 4725267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles){ 473591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 474c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles) void* result = malloc(size); 475c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles) RELEASE_ASSERT(result); 476c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles) return result; 4775267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#else 47819cde67944066db31e633d9e386f2aa9bf9fadb3Torne (Richard Coles) size = partitionCookieSizeAdjustAdd(size); 47906f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) ASSERT(root->initialized); 4803c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch size_t index = size >> kBucketShift; 4818abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) ASSERT(index < root->numBuckets); 4823c9e4aeaee9f9b0a9a814da07bcb33319c7ea363Ben Murdoch ASSERT(size == index << kBucketShift); 4838abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) PartitionBucket* bucket = &root->buckets()[index]; 48409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return partitionBucketAlloc(root, 0, size, bucket); 485f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#endif // defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 4865267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 4875267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 488a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)ALWAYS_INLINE void partitionFreeWithPage(void* ptr, PartitionPage* page) 4891fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch{ 490bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // If these asserts fire, you probably corrupted memory. 491197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 49209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t bucketSize = page->bucket->slotSize; 49309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionCookieCheckValue(ptr); 49409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionCookieCheckValue(reinterpret_cast<char*>(ptr) + bucketSize - kCookieSize); 495f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) memset(ptr, kFreedByte, bucketSize); 496f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles)#endif 49709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(page->numAllocatedSlots); 49809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionFreelistEntry* freelistHead = page->freelistHead; 49909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!freelistHead || partitionPointerIsValid(freelistHead)); 50009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) RELEASE_ASSERT(ptr != freelistHead); // Catches an immediate double free. 50109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!freelistHead || ptr != partitionFreelistMask(freelistHead->next)); // Look for double free one level deeper in debug. 5025267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) PartitionFreelistEntry* entry = static_cast<PartitionFreelistEntry*>(ptr); 50309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) entry->next = partitionFreelistMask(freelistHead); 50409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) page->freelistHead = entry; 5055267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) --page->numAllocatedSlots; 5065267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) if (UNLIKELY(page->numAllocatedSlots <= 0)) 5075267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) partitionFreeSlowPath(page); 5081fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch} 5091fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch 5101fad5ca6c42d689812b66fc493992aa6d747a6fbBen MurdochALWAYS_INLINE void partitionFree(void* ptr) 5111fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch{ 5121fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 5131fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch free(ptr); 5141fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#else 515f79f16f17ddc4f842d7b7a38603e280e94be826aTorne (Richard Coles) ptr = partitionCookieFreePointerAdjust(ptr); 51609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(partitionPointerIsValid(ptr)); 517a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) PartitionPage* page = partitionPointerToPage(ptr); 5181fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch partitionFreeWithPage(ptr, page); 5191fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#endif 5201fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch} 5211fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch 52209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE PartitionBucket* partitionGenericSizeToBucket(PartitionRootGeneric* root, size_t size) 52309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 52409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t order = kBitsPerSizet - countLeadingZerosSizet(size); 52509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // The order index is simply the next few bits after the most significant bit. 52609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t orderIndex = (size >> root->orderIndexShifts[order]) & (kGenericNumBucketsPerOrder - 1); 52709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) // And if the remaining bits are non-zero we must bump the bucket up. 52809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size_t subOrderIndex = size & root->orderSubIndexMasks[order]; 52909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket* bucket = root->bucketLookups[(order << kGenericNumBucketsPerOrderBits) + orderIndex + !!subOrderIndex]; 53009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!bucket->slotSize || bucket->slotSize >= size); 53109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(!(bucket->slotSize % kGenericSmallestBucket)); 53209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return bucket; 53309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 53409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 53509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE void* partitionAllocGenericFlags(PartitionRootGeneric* root, int flags, size_t size) 5361fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch{ 5371fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 538c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles) void* result = malloc(size); 539c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles) RELEASE_ASSERT(result); 540c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles) return result; 5411fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#else 54206f816c7c76bc45a15e452ade8a34e8af077693eTorne (Richard Coles) ASSERT(root->initialized); 54309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) size = partitionCookieSizeAdjustAdd(size); 54409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionBucket* bucket = partitionGenericSizeToBucket(root, size); 54509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) spinLockLock(&root->lock); 54609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void* ret = partitionBucketAlloc(root, flags, size, bucket); 54709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) spinLockUnlock(&root->lock); 54809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return ret; 5491fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#endif 5501fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch} 5511fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch 55209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE void* partitionAllocGeneric(PartitionRootGeneric* root, size_t size) 55309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 55409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return partitionAllocGenericFlags(root, 0, size); 55509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 55609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 55709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ALWAYS_INLINE void partitionFreeGeneric(PartitionRootGeneric* root, void* ptr) 5581fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch{ 5591fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 5601fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch free(ptr); 5611fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch#else 562bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) ASSERT(root->initialized); 56309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 56409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) if (UNLIKELY(!ptr)) 5651fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdoch return; 56609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 56709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ptr = partitionCookieFreePointerAdjust(ptr); 56809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ASSERT(partitionPointerIsValid(ptr)); 56909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionPage* page = partitionPointerToPage(ptr); 57009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) spinLockLock(&root->lock); 57109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) partitionFreeWithPage(ptr, page); 57209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) spinLockUnlock(&root->lock); 5735267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#endif 5745267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} 5755267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 576d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)ALWAYS_INLINE bool partitionBucketIsDirectMapped(PartitionBucket* bucket) 577d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 578d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return !bucket->numSystemPagesPerSlotSpan; 579d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 580d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 581d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)ALWAYS_INLINE size_t partitionDirectMapSize(size_t size) 582d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 583d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Caller must check that the size is not above the kGenericMaxDirectMapped 584d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // limit before calling. This also guards against integer overflow in the 585d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // calculation here. 586d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(size <= kGenericMaxDirectMapped); 587d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return (size + kSystemPageOffsetMask) & kSystemPageBaseMask; 588d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 589d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 590d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)ALWAYS_INLINE size_t partitionAllocActualSize(PartitionRootGeneric* root, size_t size) 591d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 592d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 593d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return size; 594d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#else 595d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(root->initialized); 596d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size = partitionCookieSizeAdjustAdd(size); 597d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) PartitionBucket* bucket = partitionGenericSizeToBucket(root, size); 598d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) if (LIKELY(!partitionBucketIsDirectMapped(bucket))) { 599d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size = bucket->slotSize; 600d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } else if (size > kGenericMaxDirectMapped) { 601d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // Too large to allocate => return the size unchanged. 602d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } else { 603d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(bucket == &PartitionRootBase::gPagedBucket); 604d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size = partitionDirectMapSize(size); 605d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 606d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return partitionCookieSizeAdjustSubtract(size); 607d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#endif 608d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 609d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 610d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)ALWAYS_INLINE bool partitionAllocSupportsGetSize() 611d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 612d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 613d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return false; 614d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#else 615d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return true; 616d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#endif 617d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 618d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 619d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)ALWAYS_INLINE size_t partitionAllocGetSize(void* ptr) 620d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 621d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // No need to lock here. Only 'ptr' being freed by another thread could 622d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) // cause trouble, and the caller is responsible for that not happening. 623d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(partitionAllocSupportsGetSize()); 624d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ptr = partitionCookieFreePointerAdjust(ptr); 625d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(partitionPointerIsValid(ptr)); 626d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) PartitionPage* page = partitionPointerToPage(ptr); 627d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t size = page->bucket->slotSize; 628d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return partitionCookieSizeAdjustSubtract(size); 629d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 630d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 6318abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)// N (or more accurately, N - sizeof(void*)) represents the largest size in 63209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// bytes that will be handled by a SizeSpecificPartitionAllocator. 63309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Attempts to partitionAlloc() more than this amount will fail. 6348abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)template <size_t N> 63509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class SizeSpecificPartitionAllocator { 6368abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)public: 6378abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) static const size_t kMaxAllocation = N - kAllocationGranularity; 6388abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) static const size_t kNumBuckets = N / kAllocationGranularity; 6398abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) void init() { partitionAllocInit(&m_partitionRoot, kNumBuckets, kMaxAllocation); } 6408abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) bool shutdown() { return partitionAllocShutdown(&m_partitionRoot); } 6418abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) ALWAYS_INLINE PartitionRoot* root() { return &m_partitionRoot; } 6428abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)private: 6438abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) PartitionRoot m_partitionRoot; 6448abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) PartitionBucket m_actualBuckets[kNumBuckets]; 6458abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)}; 6468abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 64709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class PartitionAllocatorGeneric { 64809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)public: 64909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) void init() { partitionAllocGenericInit(&m_partitionRoot); } 65009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) bool shutdown() { return partitionAllocGenericShutdown(&m_partitionRoot); } 65109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) ALWAYS_INLINE PartitionRootGeneric* root() { return &m_partitionRoot; } 65209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)private: 65309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) PartitionRootGeneric m_partitionRoot; 65409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}; 65509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 6565267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)} // namespace WTF 6575267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 65809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)using WTF::SizeSpecificPartitionAllocator; 65909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)using WTF::PartitionAllocatorGeneric; 6605267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)using WTF::PartitionRoot; 6615267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)using WTF::partitionAllocInit; 6625267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)using WTF::partitionAllocShutdown; 6635267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)using WTF::partitionAlloc; 6645267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)using WTF::partitionFree; 6651fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdochusing WTF::partitionAllocGeneric; 6661fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdochusing WTF::partitionFreeGeneric; 6671fad5ca6c42d689812b66fc493992aa6d747a6fbBen Murdochusing WTF::partitionReallocGeneric; 668d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)using WTF::partitionAllocActualSize; 669d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)using WTF::partitionAllocSupportsGetSize; 670d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)using WTF::partitionAllocGetSize; 6715267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 6725267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles)#endif // WTF_PartitionAlloc_h 673