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 // PartitonRoot 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 // Maximum size of a partition's mappings. 2046MB. Note that the total amount of
119 // bytes allocatable at the API will be smaller. This is because things like
120 // guard pages, metadata, page headers and wasted space come out of the total.
121 // The 2GB is not necessarily contiguous in virtual address space.
122 static const size_t kMaxPartitionSize = 2046u * 1024u * 1024u;
124 // Allocation granularity of sizeof(void*) bytes.
125 static const size_t kAllocationGranularity = sizeof(void*);
126 static const size_t kAllocationGranularityMask = kAllocationGranularity - 1;
127 static const size_t kBucketShift = (kAllocationGranularity == 8) ? 3 : 2;
129 // Underlying partition storage pages are a power-of-two size. It is typical
130 // for a partition page to be based on multiple system pages. Most references to
131 // "page" refer to partition pages.
132 // We also have the concept of "super pages" -- these are the underlying system // allocations we make. Super pages contain multiple partition pages inside them
133 // and include space for a small amount of metadata per partition page.
134 // Inside super pages, we store "slot spans". A slot span is a continguous range
135 // of one or more partition pages that stores allocations of the same size.
136 // Slot span sizes are adjusted depending on the allocation size, to make sure
137 // the packing does not lead to unused (wasted) space at the end of the last
138 // system page of the span. For our current max slot span size of 64k and other
139 // constant values, we pack _all_ partitionAllocGeneric() sizes perfectly up
140 // against the end of a system page.
141 static const size_t kPartitionPageShift = 14; // 16KB
142 static const size_t kPartitionPageSize = 1 << kPartitionPageShift;
143 static const size_t kPartitionPageOffsetMask = kPartitionPageSize - 1;
144 static const size_t kPartitionPageBaseMask = ~kPartitionPageOffsetMask;
145 static const size_t kMaxPartitionPagesPerSlotSpan = 4;
147 // To avoid fragmentation via never-used freelist entries, we hand out partition
148 // freelist sections gradually, in units of the dominant system page size.
149 // What we're actually doing is avoiding filling the full partition page
150 // (typically 16KB) will freelist pointers right away. Writing freelist
151 // pointers will fault and dirty a private page, which is very wasteful if we
152 // never actually store objects there.
153 static const size_t kNumSystemPagesPerPartitionPage = kPartitionPageSize / kSystemPageSize;
154 static const size_t kMaxSystemPagesPerSlotSpan = kNumSystemPagesPerPartitionPage * kMaxPartitionPagesPerSlotSpan;
156 // We reserve virtual address space in 2MB chunks (aligned to 2MB as well).
157 // These chunks are called "super pages". We do this so that we can store
158 // metadata in the first few pages of each 2MB aligned section. This leads to
159 // a very fast free(). We specifically choose 2MB because this virtual address
160 // block represents a full but single PTE allocation on ARM, ia32 and x64.
161 static const size_t kSuperPageShift = 21; // 2MB
162 static const size_t kSuperPageSize = 1 << kSuperPageShift;
163 static const size_t kSuperPageOffsetMask = kSuperPageSize - 1;
164 static const size_t kSuperPageBaseMask = ~kSuperPageOffsetMask;
165 static const size_t kNumPartitionPagesPerSuperPage = kSuperPageSize / kPartitionPageSize;
167 static const size_t kPageMetadataShift = 5; // 32 bytes per partition page.
168 static const size_t kPageMetadataSize = 1 << kPageMetadataShift;
170 // The following kGeneric* constants apply to the generic variants of the API.
171 // The "order" of an allocation is closely related to the power-of-two size of
172 // the allocation. More precisely, the order is the bit index of the
173 // most-significant-bit in the allocation size, where the bit numbers starts
174 // at index 1 for the least-significant-bit.
175 // In terms of allocation sizes, order 0 covers 0, order 1 covers 1, order 2
176 // covers 2->3, order 3 covers 4->7, order 4 covers 8->15.
177 static const size_t kGenericMinBucketedOrder = 4; // 8 bytes.
178 static const size_t kGenericMaxBucketedOrder = 20; // Largest bucketed order is 1<<(20-1) (storing 512KB -> almost 1MB)
179 static const size_t kGenericNumBucketedOrders = (kGenericMaxBucketedOrder - kGenericMinBucketedOrder) + 1;
180 static const size_t kGenericNumBucketsPerOrderBits = 3; // Eight buckets per order (for the higher orders), e.g. order 8 is 128, 144, 160, ..., 240
181 static const size_t kGenericNumBucketsPerOrder = 1 << kGenericNumBucketsPerOrderBits;
182 static const size_t kGenericSmallestBucket = 1 << (kGenericMinBucketedOrder - 1);
183 static const size_t kGenericMaxBucketSpacing = 1 << ((kGenericMaxBucketedOrder - 1) - kGenericNumBucketsPerOrderBits);
184 static const size_t kGenericMaxBucketed = (1 << (kGenericMaxBucketedOrder - 1)) + ((kGenericNumBucketsPerOrder - 1) * kGenericMaxBucketSpacing);
185 static const size_t kBitsPerSizet = sizeof(void*) * CHAR_BIT;
187 // Constants for the memory reclaim logic.
188 static const size_t kMaxFreeableSpans = 16;
191 // These two byte values match tcmalloc.
192 static const unsigned char kUninitializedByte = 0xAB;
193 static const unsigned char kFreedByte = 0xCD;
194 static const uint32_t kCookieValue = 0xDEADBEEFu;
195 static const size_t kCookieSize = 16; // Handles alignment up to XMM instructions on Intel.
198 struct PartitionBucket;
199 struct PartitionRootBase;
201 struct PartitionFreelistEntry {
202 PartitionFreelistEntry* next;
205 // Some notes on page states. A page can be in one of three major states:
209 // An active page has available free slots. A full page has no free slots. A
210 // free page has had its backing memory released back to the system.
211 // There are two linked lists tracking the pages. The "active page" list is an
212 // approximation of a list of active pages. It is an approximation because both
213 // free and full pages may briefly be present in the list until we next do a
214 // scan over it. The "free page" list is an accurate list of pages which have
215 // been returned back to the system.
216 // The significant page transitions are:
217 // - free() will detect when a full page has a slot free()'d and immediately
218 // return the page to the head of the active list.
219 // - free() will detect when a page is fully emptied. It _may_ add it to the
220 // free list and it _may_ leave it on the active list until a future list scan.
221 // - malloc() _may_ scan the active page list in order to fulfil the request.
222 // If it does this, full and free pages encountered will be booted out of the
223 // active list. If there are no suitable active pages found, a free page (if one
224 // exists) will be pulled from the free list on to the active list.
225 struct PartitionPage {
226 PartitionFreelistEntry* freelistHead;
227 PartitionPage* nextPage;
228 PartitionBucket* bucket;
229 int16_t numAllocatedSlots; // Deliberately signed, -1 for free page, -n for full pages.
230 uint16_t numUnprovisionedSlots;
232 int16_t freeCacheIndex; // -1 if not in the free cache.
235 struct PartitionBucket {
236 PartitionPage* activePagesHead; // Accessed most in hot path => goes first.
237 PartitionPage* freePagesHead;
239 uint16_t numSystemPagesPerSlotSpan;
240 uint16_t numFullPages;
243 // An "extent" is a span of consecutive superpages. We link to the partition's
244 // next extent (if there is one) at the very start of a superpage's metadata
246 struct PartitionSuperPageExtentEntry {
247 PartitionRootBase* root;
250 PartitionSuperPageExtentEntry* next;
253 struct WTF_EXPORT PartitionRootBase {
254 size_t totalSizeOfSuperPages;
256 unsigned maxAllocation;
259 char* nextPartitionPage;
260 char* nextPartitionPageEnd;
261 PartitionSuperPageExtentEntry* currentExtent;
262 PartitionSuperPageExtentEntry* firstExtent;
263 PartitionPage* globalEmptyPageRing[kMaxFreeableSpans];
264 size_t globalEmptyPageRingIndex;
265 uintptr_t invertedSelf;
267 static int gInitializedLock;
268 static bool gInitialized;
269 static PartitionPage gSeedPage;
270 static PartitionBucket gPagedBucket;
273 // Never instantiate a PartitionRoot directly, instead use PartitionAlloc.
274 struct PartitionRoot : public PartitionRootBase {
275 // The PartitionAlloc templated class ensures the following is correct.
276 ALWAYS_INLINE PartitionBucket* buckets() { return reinterpret_cast<PartitionBucket*>(this + 1); }
277 ALWAYS_INLINE const PartitionBucket* buckets() const { return reinterpret_cast<const PartitionBucket*>(this + 1); }
280 // Never instantiate a PartitionRootGeneric directly, instead use PartitionAllocatorGeneric.
281 struct PartitionRootGeneric : public PartitionRootBase {
283 // Some pre-computed constants.
284 size_t orderIndexShifts[kBitsPerSizet + 1];
285 size_t orderSubIndexMasks[kBitsPerSizet + 1];
286 // The bucket lookup table lets us map a size_t to a bucket quickly.
287 // The trailing +1 caters for the overflow case for very large allocation sizes.
288 // It is one flat array instead of a 2D array because in the 2D world, we'd
289 // need to index array[blah][max+1] which risks undefined behavior.
290 PartitionBucket* bucketLookups[((kBitsPerSizet + 1) * kGenericNumBucketsPerOrder) + 1];
291 PartitionBucket buckets[kGenericNumBucketedOrders * kGenericNumBucketsPerOrder];
294 // Flags for partitionAllocGenericFlags.
295 enum PartitionAllocFlags {
296 PartitionAllocReturnNull = 1 << 0,
299 WTF_EXPORT void partitionAllocInit(PartitionRoot*, size_t numBuckets, size_t maxAllocation);
300 WTF_EXPORT bool partitionAllocShutdown(PartitionRoot*);
301 WTF_EXPORT void partitionAllocGenericInit(PartitionRootGeneric*);
302 WTF_EXPORT bool partitionAllocGenericShutdown(PartitionRootGeneric*);
304 WTF_EXPORT NEVER_INLINE void* partitionAllocSlowPath(PartitionRootBase*, int, size_t, PartitionBucket*);
305 WTF_EXPORT NEVER_INLINE void partitionFreeSlowPath(PartitionPage*);
306 WTF_EXPORT NEVER_INLINE void* partitionReallocGeneric(PartitionRootGeneric*, void*, size_t);
308 ALWAYS_INLINE PartitionFreelistEntry* partitionFreelistMask(PartitionFreelistEntry* ptr)
310 // We use bswap on little endian as a fast mask for two reasons:
311 // 1) If an object is freed and its vtable used where the attacker doesn't
312 // get the chance to run allocations between the free and use, the vtable
313 // dereference is likely to fault.
314 // 2) If the attacker has a linear buffer overflow and elects to try and
315 // corrupt a freelist pointer, partial pointer overwrite attacks are
317 // For big endian, similar guarantees are arrived at with a negation.
319 uintptr_t masked = ~reinterpret_cast<uintptr_t>(ptr);
321 uintptr_t masked = bswapuintptrt(reinterpret_cast<uintptr_t>(ptr));
323 return reinterpret_cast<PartitionFreelistEntry*>(masked);
326 ALWAYS_INLINE size_t partitionCookieSizeAdjustAdd(size_t size)
329 // Add space for cookies, checking for integer overflow.
330 ASSERT(size + (2 * kCookieSize) > size);
331 size += 2 * kCookieSize;
336 ALWAYS_INLINE size_t partitionCookieSizeAdjustSubtract(size_t size)
339 // Remove space for cookies.
340 ASSERT(size >= 2 * kCookieSize);
341 size -= 2 * kCookieSize;
346 ALWAYS_INLINE void* partitionCookieFreePointerAdjust(void* ptr)
349 // The value given to the application is actually just after the cookie.
350 ptr = static_cast<char*>(ptr) - kCookieSize;
355 ALWAYS_INLINE void partitionCookieWriteValue(void* ptr)
358 uint32_t* cookiePtr = reinterpret_cast<uint32_t*>(ptr);
359 for (size_t i = 0; i < kCookieSize / sizeof(kCookieValue); ++i, ++cookiePtr)
360 *cookiePtr = kCookieValue;
364 ALWAYS_INLINE void partitionCookieCheckValue(void* ptr)
367 uint32_t* cookiePtr = reinterpret_cast<uint32_t*>(ptr);
368 for (size_t i = 0; i < kCookieSize / sizeof(kCookieValue); ++i, ++cookiePtr)
369 ASSERT(*cookiePtr == kCookieValue);
373 ALWAYS_INLINE char* partitionSuperPageToMetadataArea(char* ptr)
375 uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(ptr);
376 ASSERT(!(pointerAsUint & kSuperPageOffsetMask));
377 // The metadata area is exactly one system page (the guard page) into the
379 return reinterpret_cast<char*>(pointerAsUint + kSystemPageSize);
382 ALWAYS_INLINE PartitionPage* partitionPointerToPageNoAlignmentCheck(void* ptr)
384 uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(ptr);
385 char* superPagePtr = reinterpret_cast<char*>(pointerAsUint & kSuperPageBaseMask);
386 uintptr_t partitionPageIndex = (pointerAsUint & kSuperPageOffsetMask) >> kPartitionPageShift;
387 // Index 0 is invalid because it is the metadata area and the last index is invalid because it is a guard page.
388 ASSERT(partitionPageIndex);
389 ASSERT(partitionPageIndex < kNumPartitionPagesPerSuperPage - 1);
390 PartitionPage* page = reinterpret_cast<PartitionPage*>(partitionSuperPageToMetadataArea(superPagePtr) + (partitionPageIndex << kPageMetadataShift));
391 // Many partition pages can share the same page object. Adjust for that.
392 size_t delta = page->pageOffset << kPageMetadataShift;
393 page = reinterpret_cast<PartitionPage*>(reinterpret_cast<char*>(page) - delta);
397 ALWAYS_INLINE void* partitionPageToPointer(PartitionPage* page)
399 uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(page);
400 uintptr_t superPageOffset = (pointerAsUint & kSuperPageOffsetMask);
401 ASSERT(superPageOffset > kSystemPageSize);
402 ASSERT(superPageOffset < kSystemPageSize + (kNumPartitionPagesPerSuperPage * kPageMetadataSize));
403 uintptr_t partitionPageIndex = (superPageOffset - kSystemPageSize) >> kPageMetadataShift;
404 // Index 0 is invalid because it is the metadata area and the last index is invalid because it is a guard page.
405 ASSERT(partitionPageIndex);
406 ASSERT(partitionPageIndex < kNumPartitionPagesPerSuperPage - 1);
407 uintptr_t superPageBase = (pointerAsUint & kSuperPageBaseMask);
408 void* ret = reinterpret_cast<void*>(superPageBase + (partitionPageIndex << kPartitionPageShift));
412 ALWAYS_INLINE PartitionPage* partitionPointerToPage(void* ptr)
414 PartitionPage* page = partitionPointerToPageNoAlignmentCheck(ptr);
415 // Checks that the pointer is a multiple of bucket size.
416 ASSERT(!((reinterpret_cast<uintptr_t>(ptr) - reinterpret_cast<uintptr_t>(partitionPageToPointer(page))) % page->bucket->slotSize));
420 ALWAYS_INLINE PartitionRootBase* partitionPageToRoot(PartitionPage* page)
422 PartitionSuperPageExtentEntry* extentEntry = reinterpret_cast<PartitionSuperPageExtentEntry*>(reinterpret_cast<uintptr_t>(page) & kSystemPageBaseMask);
423 return extentEntry->root;
426 ALWAYS_INLINE bool partitionPointerIsValid(void* ptr)
428 PartitionPage* page = partitionPointerToPage(ptr);
429 PartitionRootBase* root = partitionPageToRoot(page);
430 return root->invertedSelf == ~reinterpret_cast<uintptr_t>(root);
433 ALWAYS_INLINE void* partitionBucketAlloc(PartitionRootBase* root, int flags, size_t size, PartitionBucket* bucket)
435 PartitionPage* page = bucket->activePagesHead;
436 ASSERT(page->numAllocatedSlots >= 0);
437 void* ret = page->freelistHead;
438 if (LIKELY(ret != 0)) {
439 // If these asserts fire, you probably corrupted memory.
440 ASSERT(partitionPointerIsValid(ret));
441 PartitionFreelistEntry* newHead = partitionFreelistMask(static_cast<PartitionFreelistEntry*>(ret)->next);
442 page->freelistHead = newHead;
443 ASSERT(!ret || partitionPointerIsValid(ret));
444 page->numAllocatedSlots++;
446 ret = partitionAllocSlowPath(root, flags, size, bucket);
451 // Fill the uninitialized pattern. and write the cookies.
452 page = partitionPointerToPage(ret);
453 size_t bucketSize = page->bucket->slotSize;
454 memset(ret, kUninitializedByte, bucketSize);
455 partitionCookieWriteValue(ret);
456 partitionCookieWriteValue(reinterpret_cast<char*>(ret) + bucketSize - kCookieSize);
457 // The value given to the application is actually just after the cookie.
458 ret = static_cast<char*>(ret) + kCookieSize;
463 ALWAYS_INLINE void* partitionAlloc(PartitionRoot* root, size_t size)
465 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
466 void* result = malloc(size);
467 RELEASE_ASSERT(result);
470 size = partitionCookieSizeAdjustAdd(size);
471 ASSERT(root->initialized);
472 size_t index = size >> kBucketShift;
473 ASSERT(index < root->numBuckets);
474 ASSERT(size == index << kBucketShift);
475 PartitionBucket* bucket = &root->buckets()[index];
476 return partitionBucketAlloc(root, 0, size, bucket);
477 #endif // defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
480 ALWAYS_INLINE void partitionFreeWithPage(void* ptr, PartitionPage* page)
482 // If these asserts fire, you probably corrupted memory.
484 size_t bucketSize = page->bucket->slotSize;
485 partitionCookieCheckValue(ptr);
486 partitionCookieCheckValue(reinterpret_cast<char*>(ptr) + bucketSize - kCookieSize);
487 memset(ptr, kFreedByte, bucketSize);
489 ASSERT(page->numAllocatedSlots);
490 PartitionFreelistEntry* freelistHead = page->freelistHead;
491 ASSERT(!freelistHead || partitionPointerIsValid(freelistHead));
492 RELEASE_ASSERT(ptr != freelistHead); // Catches an immediate double free.
493 ASSERT(!freelistHead || ptr != partitionFreelistMask(freelistHead->next)); // Look for double free one level deeper in debug.
494 PartitionFreelistEntry* entry = static_cast<PartitionFreelistEntry*>(ptr);
495 entry->next = partitionFreelistMask(freelistHead);
496 page->freelistHead = entry;
497 --page->numAllocatedSlots;
498 if (UNLIKELY(page->numAllocatedSlots <= 0))
499 partitionFreeSlowPath(page);
502 ALWAYS_INLINE void partitionFree(void* ptr)
504 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
507 ptr = partitionCookieFreePointerAdjust(ptr);
508 ASSERT(partitionPointerIsValid(ptr));
509 PartitionPage* page = partitionPointerToPage(ptr);
510 partitionFreeWithPage(ptr, page);
514 ALWAYS_INLINE PartitionBucket* partitionGenericSizeToBucket(PartitionRootGeneric* root, size_t size)
516 size_t order = kBitsPerSizet - countLeadingZerosSizet(size);
517 // The order index is simply the next few bits after the most significant bit.
518 size_t orderIndex = (size >> root->orderIndexShifts[order]) & (kGenericNumBucketsPerOrder - 1);
519 // And if the remaining bits are non-zero we must bump the bucket up.
520 size_t subOrderIndex = size & root->orderSubIndexMasks[order];
521 PartitionBucket* bucket = root->bucketLookups[(order << kGenericNumBucketsPerOrderBits) + orderIndex + !!subOrderIndex];
522 ASSERT(!bucket->slotSize || bucket->slotSize >= size);
523 ASSERT(!(bucket->slotSize % kGenericSmallestBucket));
527 ALWAYS_INLINE void* partitionAllocGenericFlags(PartitionRootGeneric* root, int flags, size_t size)
529 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
530 void* result = malloc(size);
531 RELEASE_ASSERT(result);
534 ASSERT(root->initialized);
535 size = partitionCookieSizeAdjustAdd(size);
536 PartitionBucket* bucket = partitionGenericSizeToBucket(root, size);
537 spinLockLock(&root->lock);
538 void* ret = partitionBucketAlloc(root, flags, size, bucket);
539 spinLockUnlock(&root->lock);
544 ALWAYS_INLINE void* partitionAllocGeneric(PartitionRootGeneric* root, size_t size)
546 return partitionAllocGenericFlags(root, 0, size);
549 ALWAYS_INLINE void partitionFreeGeneric(PartitionRootGeneric* root, void* ptr)
551 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
554 ASSERT(root->initialized);
559 ptr = partitionCookieFreePointerAdjust(ptr);
560 ASSERT(partitionPointerIsValid(ptr));
561 PartitionPage* page = partitionPointerToPage(ptr);
562 spinLockLock(&root->lock);
563 partitionFreeWithPage(ptr, page);
564 spinLockUnlock(&root->lock);
568 // N (or more accurately, N - sizeof(void*)) represents the largest size in
569 // bytes that will be handled by a SizeSpecificPartitionAllocator.
570 // Attempts to partitionAlloc() more than this amount will fail.
572 class SizeSpecificPartitionAllocator {
574 static const size_t kMaxAllocation = N - kAllocationGranularity;
575 static const size_t kNumBuckets = N / kAllocationGranularity;
576 void init() { partitionAllocInit(&m_partitionRoot, kNumBuckets, kMaxAllocation); }
577 bool shutdown() { return partitionAllocShutdown(&m_partitionRoot); }
578 ALWAYS_INLINE PartitionRoot* root() { return &m_partitionRoot; }
580 PartitionRoot m_partitionRoot;
581 PartitionBucket m_actualBuckets[kNumBuckets];
584 class PartitionAllocatorGeneric {
586 void init() { partitionAllocGenericInit(&m_partitionRoot); }
587 bool shutdown() { return partitionAllocGenericShutdown(&m_partitionRoot); }
588 ALWAYS_INLINE PartitionRootGeneric* root() { return &m_partitionRoot; }
590 PartitionRootGeneric m_partitionRoot;
595 using WTF::SizeSpecificPartitionAllocator;
596 using WTF::PartitionAllocatorGeneric;
597 using WTF::PartitionRoot;
598 using WTF::partitionAllocInit;
599 using WTF::partitionAllocShutdown;
600 using WTF::partitionAlloc;
601 using WTF::partitionFree;
602 using WTF::partitionAllocGeneric;
603 using WTF::partitionFreeGeneric;
604 using WTF::partitionReallocGeneric;
606 #endif // WTF_PartitionAlloc_h