2 * Copyright (C) 2013 Google Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
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
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.
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.
31 #ifndef WTF_PartitionAlloc_h
32 #define WTF_PartitionAlloc_h
35 // partitionAlloc() / partitionAllocGeneric() and partitionFree() /
36 // partitionFreeGeneric() are approximately analagous to malloc() and free().
38 // The main difference is that a PartitionRoot / PartitionRootGeneric object
39 // must be supplied to these functions, representing a specific "heap partition"
40 // that will be used to satisfy the allocation. Different partitions are
41 // guaranteed to exist in separate address spaces, including being separate from
42 // the main system heap. If the contained objects are all freed, physical memory
43 // is returned to the system but the address space remains reserved.
45 // THE ONLY LEGITIMATE WAY TO OBTAIN A PartitionRoot IS THROUGH THE
46 // SizeSpecificPartitionAllocator / PartitionAllocatorGeneric classes. To
47 // minimize the instruction count to the fullest extent possible, the
48 // PartitionRoot is really just a header adjacent to other data areas provided
49 // by the allocator class.
51 // The partitionAlloc() variant of the API has the following caveats:
52 // - Allocations and frees against a single partition must be single threaded.
53 // - Allocations must not exceed a max size, chosen at compile-time via a
54 // templated parameter to PartitionAllocator.
55 // - Allocation sizes must be aligned to the system pointer size.
56 // - Allocations are bucketed exactly according to size.
58 // And for partitionAllocGeneric():
59 // - Multi-threaded use against a single partition is ok; locking is handled.
60 // - Allocations of any arbitrary size can be handled (subject to a limit of
61 // INT_MAX bytes for security reasons).
62 // - Bucketing is by approximate size, for example an allocation of 4000 bytes
63 // might be placed into a 4096-byte bucket. Bucket sizes are chosen to try and
64 // keep worst-case waste to ~10%.
66 // The allocators are designed to be extremely fast, thanks to the following
67 // properties and design:
68 // - Just a single (reasonably predicatable) branch in the hot / fast path for
69 // both allocating and (significantly) freeing.
70 // - A minimal number of operations in the hot / fast path, with the slow paths
71 // in separate functions, leading to the possibility of inlining.
72 // - Each partition page (which is usually multiple physical pages) has a
73 // metadata structure which allows fast mapping of free() address to an
75 // - Supports a lock-free API for fast performance in single-threaded cases.
76 // - The freelist for a given bucket is split across a number of partition
77 // pages, enabling various simple tricks to try and minimize fragmentation.
78 // - Fine-grained bucket sizes leading to less waste and better packing.
80 // The following security properties are provided at this time:
81 // - Linear overflows cannot corrupt into the partition.
82 // - Linear overflows cannot corrupt out of the partition.
83 // - Freed pages will only be re-used within the partition.
84 // (exception: large allocations > ~1MB)
85 // - Freed pages will only hold same-sized objects when re-used.
86 // - Dereference of freelist pointer should fault.
87 // - Out-of-line main metadata: linear over or underflow cannot corrupt it.
88 // - Partial pointer overwrite of freelist pointer should fault.
89 // - Rudimentary double-free detection.
90 // - Large allocations (> ~1MB) are guard-paged at the beginning and end.
92 // The following security properties could be investigated in the future:
93 // - Per-object bucketing (instead of per-size) is mostly available at the API,
95 // - No randomness of freelist entries or bucket position.
96 // - Better checking for wild pointers in free().
97 // - Better freelist masking function to guarantee fault on 32-bit.
99 #include "wtf/Assertions.h"
100 #include "wtf/BitwiseOperations.h"
101 #include "wtf/ByteSwap.h"
103 #include "wtf/PageAllocator.h"
104 #include "wtf/SpinLock.h"
108 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
118 // Allocation granularity of sizeof(void*) bytes.
119 static const size_t kAllocationGranularity
= sizeof(void*);
120 static const size_t kAllocationGranularityMask
= kAllocationGranularity
- 1;
121 static const size_t kBucketShift
= (kAllocationGranularity
== 8) ? 3 : 2;
123 // Underlying partition storage pages are a power-of-two size. It is typical
124 // for a partition page to be based on multiple system pages. Most references to
125 // "page" refer to partition pages.
126 // We also have the concept of "super pages" -- these are the underlying system
127 // allocations we make. Super pages contain multiple partition pages inside them
128 // and include space for a small amount of metadata per partition page.
129 // Inside super pages, we store "slot spans". A slot span is a continguous range
130 // of one or more partition pages that stores allocations of the same size.
131 // Slot span sizes are adjusted depending on the allocation size, to make sure
132 // the packing does not lead to unused (wasted) space at the end of the last
133 // system page of the span. For our current max slot span size of 64k and other
134 // constant values, we pack _all_ partitionAllocGeneric() sizes perfectly up
135 // against the end of a system page.
136 static const size_t kPartitionPageShift
= 14; // 16KB
137 static const size_t kPartitionPageSize
= 1 << kPartitionPageShift
;
138 static const size_t kPartitionPageOffsetMask
= kPartitionPageSize
- 1;
139 static const size_t kPartitionPageBaseMask
= ~kPartitionPageOffsetMask
;
140 static const size_t kMaxPartitionPagesPerSlotSpan
= 4;
142 // To avoid fragmentation via never-used freelist entries, we hand out partition
143 // freelist sections gradually, in units of the dominant system page size.
144 // What we're actually doing is avoiding filling the full partition page (16 KB)
145 // with freelist pointers right away. Writing freelist pointers will fault and
146 // dirty a private page, which is very wasteful if we never actually store
148 static const size_t kNumSystemPagesPerPartitionPage
= kPartitionPageSize
/ kSystemPageSize
;
149 static const size_t kMaxSystemPagesPerSlotSpan
= kNumSystemPagesPerPartitionPage
* kMaxPartitionPagesPerSlotSpan
;
151 // We reserve virtual address space in 2MB chunks (aligned to 2MB as well).
152 // These chunks are called "super pages". We do this so that we can store
153 // metadata in the first few pages of each 2MB aligned section. This leads to
154 // a very fast free(). We specifically choose 2MB because this virtual address
155 // block represents a full but single PTE allocation on ARM, ia32 and x64.
157 // The layout of the super page is as follows. The sizes below are the same
158 // for 32 bit and 64 bit.
160 // | Guard page (4KB) | Metadata page (4KB) | Guard pages (8KB) | Slot span | Slot span | ... | Slot span | Guard page (4KB) |
162 // - Each slot span is a contiguous range of one or more PartitionPages.
163 // - The metadata page has the following format. Note that the PartitionPage
164 // that is not at the head of a slot span is "unused". In other words,
165 // the metadata for the slot span is stored only in the first PartitionPage
166 // of the slot span. Metadata accesses to other PartitionPages are
167 // redirected to the first PartitionPage.
169 // | 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) |
171 // A direct mapped page has a similar layout to fake it looking like a super page:
173 // | Guard page (4KB) | Metadata page (4KB) | Guard pages (8KB) | Direct mapped object | Guard page (4KB) |
175 // - The metadata page has the following layout:
177 // | SuperPageExtentEntry (32B) | PartitionPage (32B) | PartitionBucket (32B) | PartitionDirectMapExtent (8B) |
178 static const size_t kSuperPageShift
= 21; // 2MB
179 static const size_t kSuperPageSize
= 1 << kSuperPageShift
;
180 static const size_t kSuperPageOffsetMask
= kSuperPageSize
- 1;
181 static const size_t kSuperPageBaseMask
= ~kSuperPageOffsetMask
;
182 static const size_t kNumPartitionPagesPerSuperPage
= kSuperPageSize
/ kPartitionPageSize
;
184 static const size_t kPageMetadataShift
= 5; // 32 bytes per partition page.
185 static const size_t kPageMetadataSize
= 1 << kPageMetadataShift
;
187 // The following kGeneric* constants apply to the generic variants of the API.
188 // The "order" of an allocation is closely related to the power-of-two size of
189 // the allocation. More precisely, the order is the bit index of the
190 // most-significant-bit in the allocation size, where the bit numbers starts
191 // at index 1 for the least-significant-bit.
192 // In terms of allocation sizes, order 0 covers 0, order 1 covers 1, order 2
193 // covers 2->3, order 3 covers 4->7, order 4 covers 8->15.
194 static const size_t kGenericMinBucketedOrder
= 4; // 8 bytes.
195 static const size_t kGenericMaxBucketedOrder
= 20; // Largest bucketed order is 1<<(20-1) (storing 512KB -> almost 1MB)
196 static const size_t kGenericNumBucketedOrders
= (kGenericMaxBucketedOrder
- kGenericMinBucketedOrder
) + 1;
197 static const size_t kGenericNumBucketsPerOrderBits
= 3; // Eight buckets per order (for the higher orders), e.g. order 8 is 128, 144, 160, ..., 240
198 static const size_t kGenericNumBucketsPerOrder
= 1 << kGenericNumBucketsPerOrderBits
;
199 static const size_t kGenericNumBuckets
= kGenericNumBucketedOrders
* kGenericNumBucketsPerOrder
;
200 static const size_t kGenericSmallestBucket
= 1 << (kGenericMinBucketedOrder
- 1);
201 static const size_t kGenericMaxBucketSpacing
= 1 << ((kGenericMaxBucketedOrder
- 1) - kGenericNumBucketsPerOrderBits
);
202 static const size_t kGenericMaxBucketed
= (1 << (kGenericMaxBucketedOrder
- 1)) + ((kGenericNumBucketsPerOrder
- 1) * kGenericMaxBucketSpacing
);
203 static const size_t kGenericMinDirectMappedDownsize
= kGenericMaxBucketed
+ 1; // Limit when downsizing a direct mapping using realloc().
204 static const size_t kGenericMaxDirectMapped
= INT_MAX
- kSystemPageSize
;
205 static const size_t kBitsPerSizet
= sizeof(void*) * CHAR_BIT
;
207 // Constants for the memory reclaim logic.
208 static const size_t kMaxFreeableSpans
= 16;
210 // If the total size in bytes of allocated but not committed pages exceeds this
211 // value (probably it is a "out of virtual address space" crash),
212 // a special crash stack trace is generated at |partitionOutOfMemory|.
213 // This is to distinguish "out of virtual address space" from
214 // "out of physical memory" in crash reports.
215 static const size_t kReasonableSizeOfUnusedPages
= 1024 * 1024 * 1024; // 1GiB
218 // These two byte values match tcmalloc.
219 static const unsigned char kUninitializedByte
= 0xAB;
220 static const unsigned char kFreedByte
= 0xCD;
221 static const size_t kCookieSize
= 16; // Handles alignment up to XMM instructions on Intel.
222 static const unsigned char kCookieValue
[kCookieSize
] = { 0xDE, 0xAD, 0xBE, 0xEF, 0xCA, 0xFE, 0xD0, 0x0D, 0x13, 0x37, 0xF0, 0x05, 0xBA, 0x11, 0xAB, 0x1E };
225 struct PartitionBucket
;
226 struct PartitionRootBase
;
228 struct PartitionFreelistEntry
{
229 PartitionFreelistEntry
* next
;
232 // Some notes on page states. A page can be in one of four major states:
237 // An active page has available free slots. A full page has no free slots. An
238 // empty page has no free slots, and a decommitted page is an empty page that
239 // had its backing memory released back to the system.
240 // There are two linked lists tracking the pages. The "active page" list is an
241 // approximation of a list of active pages. It is an approximation because
242 // full, empty and decommitted pages may briefly be present in the list until
243 // we next do a scan over it.
244 // The "empty page" list is an accurate list of pages which are either empty
247 // The significant page transitions are:
248 // - free() will detect when a full page has a slot free()'d and immediately
249 // return the page to the head of the active list.
250 // - free() will detect when a page is fully emptied. It _may_ add it to the
251 // empty list or it _may_ leave it on the active list until a future list scan.
252 // - malloc() _may_ scan the active page list in order to fulfil the request.
253 // If it does this, full, empty and decommitted pages encountered will be
254 // booted out of the active list. If there are no suitable active pages found,
255 // an empty or decommitted page (if one exists) will be pulled from the empty
256 // list on to the active list.
257 struct PartitionPage
{
258 PartitionFreelistEntry
* freelistHead
;
259 PartitionPage
* nextPage
;
260 PartitionBucket
* bucket
;
261 int16_t numAllocatedSlots
; // Deliberately signed, 0 for empty or decommitted page, -n for full pages.
262 uint16_t numUnprovisionedSlots
;
264 int16_t emptyCacheIndex
; // -1 if not in the empty cache.
267 struct PartitionBucket
{
268 PartitionPage
* activePagesHead
; // Accessed most in hot path => goes first.
269 PartitionPage
* emptyPagesHead
;
270 PartitionPage
* decommittedPagesHead
;
272 uint16_t numSystemPagesPerSlotSpan
;
273 uint16_t numFullPages
;
276 // An "extent" is a span of consecutive superpages. We link to the partition's
277 // next extent (if there is one) at the very start of a superpage's metadata
279 struct PartitionSuperPageExtentEntry
{
280 PartitionRootBase
* root
;
283 PartitionSuperPageExtentEntry
* next
;
286 struct PartitionDirectMapExtent
{
287 PartitionDirectMapExtent
* nextExtent
;
288 PartitionDirectMapExtent
* prevExtent
;
289 PartitionBucket
* bucket
;
290 size_t mapSize
; // Mapped size, not including guard pages and meta-data.
293 struct WTF_EXPORT PartitionRootBase
{
294 size_t totalSizeOfCommittedPages
;
295 size_t totalSizeOfSuperPages
;
296 size_t totalSizeOfDirectMappedPages
;
297 // Invariant: totalSizeOfCommittedPages <= totalSizeOfSuperPages + totalSizeOfDirectMappedPages.
299 unsigned maxAllocation
;
302 char* nextPartitionPage
;
303 char* nextPartitionPageEnd
;
304 PartitionSuperPageExtentEntry
* currentExtent
;
305 PartitionSuperPageExtentEntry
* firstExtent
;
306 PartitionDirectMapExtent
* directMapList
;
307 PartitionPage
* globalEmptyPageRing
[kMaxFreeableSpans
];
308 int16_t globalEmptyPageRingIndex
;
309 uintptr_t invertedSelf
;
311 static int gInitializedLock
;
312 static bool gInitialized
;
313 // gSeedPage is used as a sentinel to indicate that there is no page
314 // in the active page list. We can use nullptr, but in that case we need
315 // to add a null-check branch to the hot allocation path. We want to avoid
317 static PartitionPage gSeedPage
;
318 static PartitionBucket gPagedBucket
;
319 // gOomHandlingFunction is invoked when ParitionAlloc hits OutOfMemory.
320 static void (*gOomHandlingFunction
)();
323 // Never instantiate a PartitionRoot directly, instead use PartitionAlloc.
324 struct PartitionRoot
: public PartitionRootBase
{
325 // The PartitionAlloc templated class ensures the following is correct.
326 ALWAYS_INLINE PartitionBucket
* buckets() { return reinterpret_cast<PartitionBucket
*>(this + 1); }
327 ALWAYS_INLINE
const PartitionBucket
* buckets() const { return reinterpret_cast<const PartitionBucket
*>(this + 1); }
330 // Never instantiate a PartitionRootGeneric directly, instead use PartitionAllocatorGeneric.
331 struct PartitionRootGeneric
: public PartitionRootBase
{
333 // Some pre-computed constants.
334 size_t orderIndexShifts
[kBitsPerSizet
+ 1];
335 size_t orderSubIndexMasks
[kBitsPerSizet
+ 1];
336 // The bucket lookup table lets us map a size_t to a bucket quickly.
337 // The trailing +1 caters for the overflow case for very large allocation sizes.
338 // It is one flat array instead of a 2D array because in the 2D world, we'd
339 // need to index array[blah][max+1] which risks undefined behavior.
340 PartitionBucket
* bucketLookups
[((kBitsPerSizet
+ 1) * kGenericNumBucketsPerOrder
) + 1];
341 PartitionBucket buckets
[kGenericNumBuckets
];
344 // Flags for partitionAllocGenericFlags.
345 enum PartitionAllocFlags
{
346 PartitionAllocReturnNull
= 1 << 0,
349 // Struct used to retrieve total memory usage of a partition. Used by
350 // PartitionStatsDumper implementation.
351 struct PartitionMemoryStats
{
352 size_t totalMmappedBytes
; // Total bytes mmaped from the system.
353 size_t totalCommittedBytes
; // Total size of commmitted pages.
354 size_t totalResidentBytes
; // Total bytes provisioned by the partition.
355 size_t totalActiveBytes
; // Total active bytes in the partition.
356 size_t totalDecommittableBytes
; // Total bytes that could be decommitted.
357 size_t totalDiscardableBytes
; // Total bytes that could be discarded.
360 // Struct used to retrieve memory statistics about a partition bucket. Used by
361 // PartitionStatsDumper implementation.
362 struct PartitionBucketMemoryStats
{
363 bool isValid
; // Used to check if the stats is valid.
364 bool isDirectMap
; // True if this is a direct mapping; size will not be unique.
365 uint32_t bucketSlotSize
; // The size of the slot in bytes.
366 uint32_t allocatedPageSize
; // Total size the partition page allocated from the system.
367 uint32_t activeBytes
; // Total active bytes used in the bucket.
368 uint32_t residentBytes
; // Total bytes provisioned in the bucket.
369 uint32_t decommittableBytes
; // Total bytes that could be decommitted.
370 uint32_t discardableBytes
; // Total bytes that could be discarded.
371 uint32_t numFullPages
; // Number of pages with all slots allocated.
372 uint32_t numActivePages
; // Number of pages that have at least one provisioned slot.
373 uint32_t numEmptyPages
; // Number of pages that are empty but not decommitted.
374 uint32_t numDecommittedPages
; // Number of pages that are empty and decommitted.
377 // Interface that is passed to partitionDumpStats and
378 // partitionDumpStatsGeneric for using the memory statistics.
379 class WTF_EXPORT PartitionStatsDumper
{
381 // Called to dump total memory used by partition, once per partition.
382 virtual void partitionDumpTotals(const char* partitionName
, const PartitionMemoryStats
*) = 0;
384 // Called to dump stats about buckets, for each bucket.
385 virtual void partitionsDumpBucketStats(const char* partitionName
, const PartitionBucketMemoryStats
*) = 0;
388 WTF_EXPORT
void partitionAllocGlobalInit(void (*oomHandlingFunction
)());
389 WTF_EXPORT
void partitionAllocInit(PartitionRoot
*, size_t numBuckets
, size_t maxAllocation
);
390 WTF_EXPORT
bool partitionAllocShutdown(PartitionRoot
*);
391 WTF_EXPORT
void partitionAllocGenericInit(PartitionRootGeneric
*);
392 WTF_EXPORT
bool partitionAllocGenericShutdown(PartitionRootGeneric
*);
394 enum PartitionPurgeFlags
{
395 // Decommitting the ring list of empty pages is reasonably fast.
396 PartitionPurgeDecommitEmptyPages
= 1 << 0,
397 // Discarding unused system pages is slower, because it involves walking all
398 // freelists in all active partition pages of all buckets >= system page
399 // size. It often frees a similar amount of memory to decommitting the empty
401 PartitionPurgeDiscardUnusedSystemPages
= 1 << 1,
404 WTF_EXPORT
void partitionPurgeMemory(PartitionRoot
*, int);
405 WTF_EXPORT
void partitionPurgeMemoryGeneric(PartitionRootGeneric
*, int);
407 WTF_EXPORT NEVER_INLINE
void* partitionAllocSlowPath(PartitionRootBase
*, int, size_t, PartitionBucket
*);
408 WTF_EXPORT NEVER_INLINE
void partitionFreeSlowPath(PartitionPage
*);
409 WTF_EXPORT NEVER_INLINE
void* partitionReallocGeneric(PartitionRootGeneric
*, void*, size_t);
411 WTF_EXPORT
void partitionDumpStats(PartitionRoot
*, const char* partitionName
, bool isLightDump
, PartitionStatsDumper
*);
412 WTF_EXPORT
void partitionDumpStatsGeneric(PartitionRootGeneric
*, const char* partitionName
, bool isLightDump
, PartitionStatsDumper
*);
414 ALWAYS_INLINE PartitionFreelistEntry
* partitionFreelistMask(PartitionFreelistEntry
* ptr
)
416 // We use bswap on little endian as a fast mask for two reasons:
417 // 1) If an object is freed and its vtable used where the attacker doesn't
418 // get the chance to run allocations between the free and use, the vtable
419 // dereference is likely to fault.
420 // 2) If the attacker has a linear buffer overflow and elects to try and
421 // corrupt a freelist pointer, partial pointer overwrite attacks are
423 // For big endian, similar guarantees are arrived at with a negation.
425 uintptr_t masked
= ~reinterpret_cast<uintptr_t>(ptr
);
427 uintptr_t masked
= bswapuintptrt(reinterpret_cast<uintptr_t>(ptr
));
429 return reinterpret_cast<PartitionFreelistEntry
*>(masked
);
432 ALWAYS_INLINE
size_t partitionCookieSizeAdjustAdd(size_t size
)
435 // Add space for cookies, checking for integer overflow.
436 ASSERT(size
+ (2 * kCookieSize
) > size
);
437 size
+= 2 * kCookieSize
;
442 ALWAYS_INLINE
size_t partitionCookieSizeAdjustSubtract(size_t size
)
445 // Remove space for cookies.
446 ASSERT(size
>= 2 * kCookieSize
);
447 size
-= 2 * kCookieSize
;
452 ALWAYS_INLINE
void* partitionCookieFreePointerAdjust(void* ptr
)
455 // The value given to the application is actually just after the cookie.
456 ptr
= static_cast<char*>(ptr
) - kCookieSize
;
461 ALWAYS_INLINE
void partitionCookieWriteValue(void* ptr
)
464 unsigned char* cookiePtr
= reinterpret_cast<unsigned char*>(ptr
);
465 for (size_t i
= 0; i
< kCookieSize
; ++i
, ++cookiePtr
)
466 *cookiePtr
= kCookieValue
[i
];
470 ALWAYS_INLINE
void partitionCookieCheckValue(void* ptr
)
473 unsigned char* cookiePtr
= reinterpret_cast<unsigned char*>(ptr
);
474 for (size_t i
= 0; i
< kCookieSize
; ++i
, ++cookiePtr
)
475 ASSERT(*cookiePtr
== kCookieValue
[i
]);
479 ALWAYS_INLINE
char* partitionSuperPageToMetadataArea(char* ptr
)
481 uintptr_t pointerAsUint
= reinterpret_cast<uintptr_t>(ptr
);
482 ASSERT(!(pointerAsUint
& kSuperPageOffsetMask
));
483 // The metadata area is exactly one system page (the guard page) into the
485 return reinterpret_cast<char*>(pointerAsUint
+ kSystemPageSize
);
488 ALWAYS_INLINE PartitionPage
* partitionPointerToPageNoAlignmentCheck(void* ptr
)
490 uintptr_t pointerAsUint
= reinterpret_cast<uintptr_t>(ptr
);
491 char* superPagePtr
= reinterpret_cast<char*>(pointerAsUint
& kSuperPageBaseMask
);
492 uintptr_t partitionPageIndex
= (pointerAsUint
& kSuperPageOffsetMask
) >> kPartitionPageShift
;
493 // Index 0 is invalid because it is the metadata and guard area and
494 // the last index is invalid because it is a guard page.
495 ASSERT(partitionPageIndex
);
496 ASSERT(partitionPageIndex
< kNumPartitionPagesPerSuperPage
- 1);
497 PartitionPage
* page
= reinterpret_cast<PartitionPage
*>(partitionSuperPageToMetadataArea(superPagePtr
) + (partitionPageIndex
<< kPageMetadataShift
));
498 // Partition pages in the same slot span can share the same page object. Adjust for that.
499 size_t delta
= page
->pageOffset
<< kPageMetadataShift
;
500 page
= reinterpret_cast<PartitionPage
*>(reinterpret_cast<char*>(page
) - delta
);
504 ALWAYS_INLINE
void* partitionPageToPointer(const PartitionPage
* page
)
506 uintptr_t pointerAsUint
= reinterpret_cast<uintptr_t>(page
);
507 uintptr_t superPageOffset
= (pointerAsUint
& kSuperPageOffsetMask
);
508 ASSERT(superPageOffset
> kSystemPageSize
);
509 ASSERT(superPageOffset
< kSystemPageSize
+ (kNumPartitionPagesPerSuperPage
* kPageMetadataSize
));
510 uintptr_t partitionPageIndex
= (superPageOffset
- kSystemPageSize
) >> kPageMetadataShift
;
511 // Index 0 is invalid because it is the metadata area and the last index is invalid because it is a guard page.
512 ASSERT(partitionPageIndex
);
513 ASSERT(partitionPageIndex
< kNumPartitionPagesPerSuperPage
- 1);
514 uintptr_t superPageBase
= (pointerAsUint
& kSuperPageBaseMask
);
515 void* ret
= reinterpret_cast<void*>(superPageBase
+ (partitionPageIndex
<< kPartitionPageShift
));
519 ALWAYS_INLINE PartitionPage
* partitionPointerToPage(void* ptr
)
521 PartitionPage
* page
= partitionPointerToPageNoAlignmentCheck(ptr
);
522 // Checks that the pointer is a multiple of bucket size.
523 ASSERT(!((reinterpret_cast<uintptr_t>(ptr
) - reinterpret_cast<uintptr_t>(partitionPageToPointer(page
))) % page
->bucket
->slotSize
));
527 ALWAYS_INLINE
bool partitionBucketIsDirectMapped(const PartitionBucket
* bucket
)
529 return !bucket
->numSystemPagesPerSlotSpan
;
532 ALWAYS_INLINE
size_t partitionBucketBytes(const PartitionBucket
* bucket
)
534 return bucket
->numSystemPagesPerSlotSpan
* kSystemPageSize
;
537 ALWAYS_INLINE
uint16_t partitionBucketSlots(const PartitionBucket
* bucket
)
539 return static_cast<uint16_t>(partitionBucketBytes(bucket
) / bucket
->slotSize
);
542 ALWAYS_INLINE
size_t* partitionPageGetRawSizePtr(PartitionPage
* page
)
544 // For single-slot buckets which span more than one partition page, we
545 // have some spare metadata space to store the raw allocation size. We
546 // can use this to report better statistics.
547 PartitionBucket
* bucket
= page
->bucket
;
548 if (bucket
->slotSize
<= kMaxSystemPagesPerSlotSpan
* kSystemPageSize
)
551 ASSERT((bucket
->slotSize
% kSystemPageSize
) == 0);
552 ASSERT(partitionBucketIsDirectMapped(bucket
) || partitionBucketSlots(bucket
) == 1);
554 return reinterpret_cast<size_t*>(&page
->freelistHead
);
557 ALWAYS_INLINE
size_t partitionPageGetRawSize(PartitionPage
* page
)
559 size_t* rawSizePtr
= partitionPageGetRawSizePtr(page
);
560 if (UNLIKELY(rawSizePtr
!= nullptr))
565 ALWAYS_INLINE PartitionRootBase
* partitionPageToRoot(PartitionPage
* page
)
567 PartitionSuperPageExtentEntry
* extentEntry
= reinterpret_cast<PartitionSuperPageExtentEntry
*>(reinterpret_cast<uintptr_t>(page
) & kSystemPageBaseMask
);
568 return extentEntry
->root
;
571 ALWAYS_INLINE
bool partitionPointerIsValid(void* ptr
)
573 PartitionPage
* page
= partitionPointerToPage(ptr
);
574 PartitionRootBase
* root
= partitionPageToRoot(page
);
575 return root
->invertedSelf
== ~reinterpret_cast<uintptr_t>(root
);
578 ALWAYS_INLINE
void* partitionBucketAlloc(PartitionRootBase
* root
, int flags
, size_t size
, PartitionBucket
* bucket
)
580 PartitionPage
* page
= bucket
->activePagesHead
;
581 // Check that this page is neither full nor freed.
582 ASSERT(page
->numAllocatedSlots
>= 0);
583 void* ret
= page
->freelistHead
;
584 if (LIKELY(ret
!= 0)) {
585 // If these asserts fire, you probably corrupted memory.
586 ASSERT(partitionPointerIsValid(ret
));
587 // All large allocations must go through the slow path to correctly
588 // update the size metadata.
589 ASSERT(partitionPageGetRawSize(page
) == 0);
590 PartitionFreelistEntry
* newHead
= partitionFreelistMask(static_cast<PartitionFreelistEntry
*>(ret
)->next
);
591 page
->freelistHead
= newHead
;
592 page
->numAllocatedSlots
++;
594 ret
= partitionAllocSlowPath(root
, flags
, size
, bucket
);
595 ASSERT(!ret
|| partitionPointerIsValid(ret
));
600 // Fill the uninitialized pattern, and write the cookies.
601 page
= partitionPointerToPage(ret
);
602 size_t slotSize
= page
->bucket
->slotSize
;
603 size_t rawSize
= partitionPageGetRawSize(page
);
605 ASSERT(rawSize
== size
);
608 size_t noCookieSize
= partitionCookieSizeAdjustSubtract(slotSize
);
609 char* charRet
= static_cast<char*>(ret
);
610 // The value given to the application is actually just after the cookie.
611 ret
= charRet
+ kCookieSize
;
612 memset(ret
, kUninitializedByte
, noCookieSize
);
613 partitionCookieWriteValue(charRet
);
614 partitionCookieWriteValue(charRet
+ kCookieSize
+ noCookieSize
);
619 ALWAYS_INLINE
void* partitionAlloc(PartitionRoot
* root
, size_t size
)
621 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
622 void* result
= malloc(size
);
623 RELEASE_ASSERT(result
);
626 size
= partitionCookieSizeAdjustAdd(size
);
627 ASSERT(root
->initialized
);
628 size_t index
= size
>> kBucketShift
;
629 ASSERT(index
< root
->numBuckets
);
630 ASSERT(size
== index
<< kBucketShift
);
631 PartitionBucket
* bucket
= &root
->buckets()[index
];
632 return partitionBucketAlloc(root
, 0, size
, bucket
);
633 #endif // defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
636 ALWAYS_INLINE
void partitionFreeWithPage(void* ptr
, PartitionPage
* page
)
638 // If these asserts fire, you probably corrupted memory.
640 size_t slotSize
= page
->bucket
->slotSize
;
641 size_t rawSize
= partitionPageGetRawSize(page
);
644 partitionCookieCheckValue(ptr
);
645 partitionCookieCheckValue(reinterpret_cast<char*>(ptr
) + slotSize
- kCookieSize
);
646 memset(ptr
, kFreedByte
, slotSize
);
648 ASSERT(page
->numAllocatedSlots
);
649 PartitionFreelistEntry
* freelistHead
= page
->freelistHead
;
650 ASSERT(!freelistHead
|| partitionPointerIsValid(freelistHead
));
651 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(ptr
!= freelistHead
); // Catches an immediate double free.
652 ASSERT_WITH_SECURITY_IMPLICATION(!freelistHead
|| ptr
!= partitionFreelistMask(freelistHead
->next
)); // Look for double free one level deeper in debug.
653 PartitionFreelistEntry
* entry
= static_cast<PartitionFreelistEntry
*>(ptr
);
654 entry
->next
= partitionFreelistMask(freelistHead
);
655 page
->freelistHead
= entry
;
656 --page
->numAllocatedSlots
;
657 if (UNLIKELY(page
->numAllocatedSlots
<= 0)) {
658 partitionFreeSlowPath(page
);
660 // All single-slot allocations must go through the slow path to
661 // correctly update the size metadata.
662 ASSERT(partitionPageGetRawSize(page
) == 0);
666 ALWAYS_INLINE
void partitionFree(void* ptr
)
668 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
671 ptr
= partitionCookieFreePointerAdjust(ptr
);
672 ASSERT(partitionPointerIsValid(ptr
));
673 PartitionPage
* page
= partitionPointerToPage(ptr
);
674 partitionFreeWithPage(ptr
, page
);
678 ALWAYS_INLINE PartitionBucket
* partitionGenericSizeToBucket(PartitionRootGeneric
* root
, size_t size
)
680 size_t order
= kBitsPerSizet
- countLeadingZerosSizet(size
);
681 // The order index is simply the next few bits after the most significant bit.
682 size_t orderIndex
= (size
>> root
->orderIndexShifts
[order
]) & (kGenericNumBucketsPerOrder
- 1);
683 // And if the remaining bits are non-zero we must bump the bucket up.
684 size_t subOrderIndex
= size
& root
->orderSubIndexMasks
[order
];
685 PartitionBucket
* bucket
= root
->bucketLookups
[(order
<< kGenericNumBucketsPerOrderBits
) + orderIndex
+ !!subOrderIndex
];
686 ASSERT(!bucket
->slotSize
|| bucket
->slotSize
>= size
);
687 ASSERT(!(bucket
->slotSize
% kGenericSmallestBucket
));
691 ALWAYS_INLINE
void* partitionAllocGenericFlags(PartitionRootGeneric
* root
, int flags
, size_t size
)
693 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
694 void* result
= malloc(size
);
695 RELEASE_ASSERT(result
);
698 ASSERT(root
->initialized
);
699 size
= partitionCookieSizeAdjustAdd(size
);
700 PartitionBucket
* bucket
= partitionGenericSizeToBucket(root
, size
);
701 spinLockLock(&root
->lock
);
702 void* ret
= partitionBucketAlloc(root
, flags
, size
, bucket
);
703 spinLockUnlock(&root
->lock
);
708 ALWAYS_INLINE
void* partitionAllocGeneric(PartitionRootGeneric
* root
, size_t size
)
710 return partitionAllocGenericFlags(root
, 0, size
);
713 ALWAYS_INLINE
void partitionFreeGeneric(PartitionRootGeneric
* root
, void* ptr
)
715 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
718 ASSERT(root
->initialized
);
723 ptr
= partitionCookieFreePointerAdjust(ptr
);
724 ASSERT(partitionPointerIsValid(ptr
));
725 PartitionPage
* page
= partitionPointerToPage(ptr
);
726 spinLockLock(&root
->lock
);
727 partitionFreeWithPage(ptr
, page
);
728 spinLockUnlock(&root
->lock
);
732 ALWAYS_INLINE
size_t partitionDirectMapSize(size_t size
)
734 // Caller must check that the size is not above the kGenericMaxDirectMapped
735 // limit before calling. This also guards against integer overflow in the
737 ASSERT(size
<= kGenericMaxDirectMapped
);
738 return (size
+ kSystemPageOffsetMask
) & kSystemPageBaseMask
;
741 ALWAYS_INLINE
size_t partitionAllocActualSize(PartitionRootGeneric
* root
, size_t size
)
743 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
746 ASSERT(root
->initialized
);
747 size
= partitionCookieSizeAdjustAdd(size
);
748 PartitionBucket
* bucket
= partitionGenericSizeToBucket(root
, size
);
749 if (LIKELY(!partitionBucketIsDirectMapped(bucket
))) {
750 size
= bucket
->slotSize
;
751 } else if (size
> kGenericMaxDirectMapped
) {
752 // Too large to allocate => return the size unchanged.
754 ASSERT(bucket
== &PartitionRootBase::gPagedBucket
);
755 size
= partitionDirectMapSize(size
);
757 return partitionCookieSizeAdjustSubtract(size
);
761 ALWAYS_INLINE
bool partitionAllocSupportsGetSize()
763 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
770 ALWAYS_INLINE
size_t partitionAllocGetSize(void* ptr
)
772 // No need to lock here. Only 'ptr' being freed by another thread could
773 // cause trouble, and the caller is responsible for that not happening.
774 ASSERT(partitionAllocSupportsGetSize());
775 ptr
= partitionCookieFreePointerAdjust(ptr
);
776 ASSERT(partitionPointerIsValid(ptr
));
777 PartitionPage
* page
= partitionPointerToPage(ptr
);
778 size_t size
= page
->bucket
->slotSize
;
779 return partitionCookieSizeAdjustSubtract(size
);
782 // N (or more accurately, N - sizeof(void*)) represents the largest size in
783 // bytes that will be handled by a SizeSpecificPartitionAllocator.
784 // Attempts to partitionAlloc() more than this amount will fail.
786 class SizeSpecificPartitionAllocator
{
788 static const size_t kMaxAllocation
= N
- kAllocationGranularity
;
789 static const size_t kNumBuckets
= N
/ kAllocationGranularity
;
790 void init() { partitionAllocInit(&m_partitionRoot
, kNumBuckets
, kMaxAllocation
); }
791 bool shutdown() { return partitionAllocShutdown(&m_partitionRoot
); }
792 ALWAYS_INLINE PartitionRoot
* root() { return &m_partitionRoot
; }
794 PartitionRoot m_partitionRoot
;
795 PartitionBucket m_actualBuckets
[kNumBuckets
];
798 class PartitionAllocatorGeneric
{
800 void init() { partitionAllocGenericInit(&m_partitionRoot
); }
801 bool shutdown() { return partitionAllocGenericShutdown(&m_partitionRoot
); }
802 ALWAYS_INLINE PartitionRootGeneric
* root() { return &m_partitionRoot
; }
804 PartitionRootGeneric m_partitionRoot
;
809 using WTF::SizeSpecificPartitionAllocator
;
810 using WTF::PartitionAllocatorGeneric
;
811 using WTF::PartitionRoot
;
812 using WTF::partitionAllocInit
;
813 using WTF::partitionAllocShutdown
;
814 using WTF::partitionAlloc
;
815 using WTF::partitionFree
;
816 using WTF::partitionAllocGeneric
;
817 using WTF::partitionFreeGeneric
;
818 using WTF::partitionReallocGeneric
;
819 using WTF::partitionAllocActualSize
;
820 using WTF::partitionAllocSupportsGetSize
;
821 using WTF::partitionAllocGetSize
;
823 #endif // WTF_PartitionAlloc_h