1 /* 2 * Copyright (C) 2013 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #ifndef WTF_PartitionAlloc_h 32 #define WTF_PartitionAlloc_h 33 34 // DESCRIPTION 35 // partitionAlloc() and partitionFree() are approximately analagous 36 // to malloc() and free(). 37 // The main difference is that a PartitionRoot object must be supplied to 38 // partitionAlloc(), representing a specific "heap partition" that will 39 // be used to satisfy the allocation. Different partitions are guaranteed to 40 // exist in separate address spaces, including being separate from the main 41 // system heap. If the contained objects are all freed, physical memory is 42 // returned to the system but the address space remains reserved. 43 // 44 // Allocations and frees against a single partition must be single threaded. 45 // Allocations must not exceed a max size, typically 4088 bytes at this time. 46 // Allocation sizes must be aligned to the system pointer size. 47 // The separate APIs partitionAllocGeneric and partitionFreeGeneric are 48 // provided, and they do not have the above three restrictions. In return, you 49 // take a small performance hit and are also obliged to keep track of 50 // allocation sizes, and pass them to partitionFreeGeneric. 51 // 52 // This allocator is designed to be extremely fast, thanks to the following 53 // properties and design: 54 // - Just a single (reasonably predicatable) branch in the hot / fast path for 55 // both allocating and (significantly) freeing. 56 // - A minimal number of operations in the hot / fast path, with the slow paths 57 // in separate functions, leading to the possibility of inlining. 58 // - Each partition page (which is usually multiple physical pages) has a header 59 // structure which allows fast mapping of free() address to an underlying 60 // bucket. 61 // - Supports a lock-free API for fast performance in single-threaded cases. 62 // - The freelist for a given bucket is split across a number of partition 63 // pages, enabling various simple tricks to try and minimize fragmentation. 64 // - Fine-grained bucket sizes leading to less waste and better packing. 65 // 66 // The following security properties are provided at this time: 67 // - Linear overflows cannot corrupt into the partition. 68 // - Linear overflows cannot corrupt out of the partition. 69 // - Freed pages will only be re-used within the partition. 70 // - Freed pages will only hold same-sized objects when re-used. 71 // - Dereference of freelist pointer will fault. 72 // 73 // The following security properties could be investigated in the future: 74 // - No double-free detection (tcmalloc has some but it may be only a detection 75 // and not a defense). 76 // - No randomness in freelist pointers. 77 // - Per-object bucketing (instead of per-size) is mostly available at the API, 78 // but not used yet. 79 // - No randomness of freelist entries or bucket position. 80 // - No specific protection against corruption of page header metadata. 81 82 #include "wtf/Assertions.h" 83 #include "wtf/FastMalloc.h" 84 #include "wtf/SpinLock.h" 85 86 #include <stdlib.h> 87 88 namespace WTF { 89 90 // Allocation granularity of sizeof(void*) bytes. 91 static const size_t kAllocationGranularity = sizeof(void*); 92 static const size_t kAllocationGranularityMask = kAllocationGranularity - 1; 93 static const size_t kBucketShift = (kAllocationGranularity == 8) ? 3 : 2; 94 // Supports allocations up to 4088 (one bucket is used for metadata). 95 static const size_t kMaxAllocationOrder = 12; 96 static const size_t kMaxAllocation = (1 << kMaxAllocationOrder) - kAllocationGranularity; 97 static const size_t kNumBuckets = (1 << kMaxAllocationOrder) / (1 << kBucketShift); 98 // Underlying partition storage pages are a power-of-two size. It is typical 99 // for a partition page to be based on multiple system pages. We rarely deal 100 // with system pages. Most references to "page" refer to partition pages. We 101 // do also have the concept of "super pages" -- these are the underlying 102 // system allocations we make. Super pages can typically fit multiple 103 // partition pages inside them. See PageAllocator.h for more details on 104 // super pages. 105 static const size_t kPartitionPageSize = 1 << 14; // 16KB 106 static const size_t kPartitionPageOffsetMask = kPartitionPageSize - 1; 107 static const size_t kPartitionPageBaseMask = ~kPartitionPageOffsetMask; 108 // Special bucket id for free page metadata. 109 static const size_t kFreePageBucket = 0; 110 111 struct PartitionRoot; 112 struct PartitionBucket; 113 114 struct PartitionFreelistEntry { 115 PartitionFreelistEntry* next; 116 }; 117 118 struct PartitionPageHeader { 119 int numAllocatedSlots; // Deliberately signed. 120 PartitionBucket* bucket; 121 PartitionFreelistEntry* freelistHead; 122 PartitionPageHeader* next; 123 PartitionPageHeader* prev; 124 }; 125 126 struct PartitionFreepagelistEntry { 127 PartitionPageHeader* page; 128 PartitionFreepagelistEntry* next; 129 }; 130 131 struct PartitionBucket { 132 PartitionRoot* root; 133 PartitionPageHeader* currPage; 134 PartitionFreepagelistEntry* freePages; 135 size_t numFullPages; 136 }; 137 138 struct PartitionRoot { 139 int lock; 140 PartitionPageHeader seedPage; 141 PartitionBucket seedBucket; 142 PartitionBucket buckets[kNumBuckets]; 143 char* nextSuperPage; 144 char* nextPartitionPage; 145 char* nextPartitionPageEnd; 146 bool initialized; 147 }; 148 149 WTF_EXPORT void partitionAllocInit(PartitionRoot*); 150 WTF_EXPORT bool partitionAllocShutdown(PartitionRoot*); 151 152 WTF_EXPORT NEVER_INLINE void* partitionAllocSlowPath(PartitionBucket*); 153 WTF_EXPORT NEVER_INLINE void partitionFreeSlowPath(PartitionPageHeader*); 154 WTF_EXPORT NEVER_INLINE void* partitionReallocGeneric(PartitionRoot*, void*, size_t, size_t); 155 156 ALWAYS_INLINE PartitionFreelistEntry* partitionFreelistMask(PartitionFreelistEntry* ptr) 157 { 158 // For now, use a simple / fast mask that guarantees an invalid pointer in 159 // case it gets used as a vtable pointer. 160 // The one attack we're fully mitigating is where an object is freed and its 161 // vtable used where the attacker doesn't get the chance to run allocations 162 // between the free and use. 163 // We're deliberately not trying to defend against OOB reads or writes. 164 uintptr_t masked = ~reinterpret_cast<uintptr_t>(ptr); 165 return reinterpret_cast<PartitionFreelistEntry*>(masked); 166 } 167 168 ALWAYS_INLINE size_t partitionBucketSize(const PartitionBucket* bucket) 169 { 170 PartitionRoot* root = bucket->root; 171 size_t index = bucket - &root->buckets[0]; 172 size_t size; 173 if (UNLIKELY(index == kFreePageBucket)) 174 size = sizeof(PartitionFreepagelistEntry); 175 else 176 size = index << kBucketShift; 177 return size; 178 } 179 180 ALWAYS_INLINE void* partitionBucketAlloc(PartitionBucket* bucket) 181 { 182 PartitionPageHeader* page = bucket->currPage; 183 PartitionFreelistEntry* ret = page->freelistHead; 184 if (LIKELY(ret != 0)) { 185 page->freelistHead = partitionFreelistMask(ret->next); 186 page->numAllocatedSlots++; 187 return ret; 188 } 189 return partitionAllocSlowPath(bucket); 190 } 191 192 ALWAYS_INLINE void* partitionAlloc(PartitionRoot* root, size_t size) 193 { 194 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 195 return malloc(size); 196 #else 197 size_t index = size >> kBucketShift; 198 ASSERT(index < kNumBuckets); 199 ASSERT(size == index << kBucketShift); 200 PartitionBucket* bucket = &root->buckets[index]; 201 return partitionBucketAlloc(bucket); 202 #endif 203 } 204 205 ALWAYS_INLINE PartitionPageHeader* partitionPointerToPage(void* ptr) 206 { 207 uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(ptr); 208 // Checks that the pointer is after the page header. You can't free the 209 // page header! 210 ASSERT((pointerAsUint & kPartitionPageOffsetMask) >= sizeof(PartitionPageHeader)); 211 PartitionPageHeader* page = reinterpret_cast<PartitionPageHeader*>(pointerAsUint & kPartitionPageBaseMask); 212 // Checks that the pointer is a multiple of bucket size. 213 ASSERT(!(((pointerAsUint & kPartitionPageOffsetMask) - sizeof(PartitionPageHeader)) % partitionBucketSize(page->bucket))); 214 return page; 215 } 216 217 ALWAYS_INLINE void partitionFreeWithPage(void* ptr, PartitionPageHeader* page) 218 { 219 PartitionFreelistEntry* entry = static_cast<PartitionFreelistEntry*>(ptr); 220 entry->next = partitionFreelistMask(page->freelistHead); 221 page->freelistHead = entry; 222 --page->numAllocatedSlots; 223 if (UNLIKELY(page->numAllocatedSlots <= 0)) 224 partitionFreeSlowPath(page); 225 } 226 227 ALWAYS_INLINE void partitionFree(void* ptr) 228 { 229 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 230 free(ptr); 231 #else 232 PartitionPageHeader* page = partitionPointerToPage(ptr); 233 partitionFreeWithPage(ptr, page); 234 #endif 235 } 236 237 ALWAYS_INLINE size_t partitionAllocRoundup(size_t size) 238 { 239 return (size + kAllocationGranularityMask) & ~kAllocationGranularityMask; 240 } 241 242 ALWAYS_INLINE void* partitionAllocGeneric(PartitionRoot* root, size_t size) 243 { 244 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 245 return malloc(size); 246 #else 247 if (LIKELY(size <= kMaxAllocation)) { 248 size = partitionAllocRoundup(size); 249 spinLockLock(&root->lock); 250 void* ret = partitionAlloc(root, size); 251 spinLockUnlock(&root->lock); 252 return ret; 253 } 254 return WTF::fastMalloc(size); 255 #endif 256 } 257 258 ALWAYS_INLINE void partitionFreeGeneric(void* ptr, size_t size) 259 { 260 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 261 free(ptr); 262 #else 263 if (LIKELY(size <= kMaxAllocation)) { 264 PartitionPageHeader* page = partitionPointerToPage(ptr); 265 PartitionRoot* root = page->bucket->root; 266 spinLockLock(&root->lock); 267 partitionFreeWithPage(ptr, page); 268 spinLockUnlock(&root->lock); 269 return; 270 } 271 return WTF::fastFree(ptr); 272 #endif 273 } 274 275 } // namespace WTF 276 277 using WTF::PartitionRoot; 278 using WTF::partitionAllocInit; 279 using WTF::partitionAllocShutdown; 280 using WTF::partitionAlloc; 281 using WTF::partitionFree; 282 using WTF::partitionAllocGeneric; 283 using WTF::partitionFreeGeneric; 284 using WTF::partitionReallocGeneric; 285 286 #endif // WTF_PartitionAlloc_h 287
