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.
32 #include "wtf/PartitionAlloc.h"
40 // Two partition pages are used as guard / metadata page so make sure the super
41 // page size is bigger.
42 static_assert(WTF::kPartitionPageSize
* 4 <= WTF::kSuperPageSize
, "ok super page size");
43 static_assert(!(WTF::kSuperPageSize
% WTF::kPartitionPageSize
), "ok super page multiple");
44 // Four system pages gives us room to hack out a still-guard-paged piece
45 // of metadata in the middle of a guard partition page.
46 static_assert(WTF::kSystemPageSize
* 4 <= WTF::kPartitionPageSize
, "ok partition page size");
47 static_assert(!(WTF::kPartitionPageSize
% WTF::kSystemPageSize
), "ok partition page multiple");
48 static_assert(sizeof(WTF::PartitionPage
) <= WTF::kPageMetadataSize
, "PartitionPage should not be too big");
49 static_assert(sizeof(WTF::PartitionBucket
) <= WTF::kPageMetadataSize
, "PartitionBucket should not be too big");
50 static_assert(sizeof(WTF::PartitionSuperPageExtentEntry
) <= WTF::kPageMetadataSize
, "PartitionSuperPageExtentEntry should not be too big");
51 static_assert(WTF::kPageMetadataSize
* WTF::kNumPartitionPagesPerSuperPage
<= WTF::kSystemPageSize
, "page metadata fits in hole");
52 // Check that some of our zanier calculations worked out as expected.
53 static_assert(WTF::kGenericSmallestBucket
== 8, "generic smallest bucket");
54 static_assert(WTF::kGenericMaxBucketed
== 983040, "generic max bucketed");
58 int PartitionRootBase::gInitializedLock
= 0;
59 bool PartitionRootBase::gInitialized
= false;
60 PartitionPage
PartitionRootBase::gSeedPage
;
61 PartitionBucket
PartitionRootBase::gPagedBucket
;
62 void (*PartitionRootBase::gOomHandlingFunction
)() = nullptr;
64 static uint16_t partitionBucketNumSystemPages(size_t size
)
66 // This works out reasonably for the current bucket sizes of the generic
67 // allocator, and the current values of partition page size and constants.
68 // Specifically, we have enough room to always pack the slots perfectly into
69 // some number of system pages. The only waste is the waste associated with
70 // unfaulted pages (i.e. wasted address space).
71 // TODO: we end up using a lot of system pages for very small sizes. For
72 // example, we'll use 12 system pages for slot size 24. The slot size is
73 // so small that the waste would be tiny with just 4, or 1, system pages.
74 // Later, we can investigate whether there are anti-fragmentation benefits
75 // to using fewer system pages.
76 double bestWasteRatio
= 1.0f
;
77 uint16_t bestPages
= 0;
78 if (size
> kMaxSystemPagesPerSlotSpan
* kSystemPageSize
) {
79 ASSERT(!(size
% kSystemPageSize
));
80 return static_cast<uint16_t>(size
/ kSystemPageSize
);
82 ASSERT(size
<= kMaxSystemPagesPerSlotSpan
* kSystemPageSize
);
83 for (uint16_t i
= kNumSystemPagesPerPartitionPage
- 1; i
<= kMaxSystemPagesPerSlotSpan
; ++i
) {
84 size_t pageSize
= kSystemPageSize
* i
;
85 size_t numSlots
= pageSize
/ size
;
86 size_t waste
= pageSize
- (numSlots
* size
);
87 // Leaving a page unfaulted is not free; the page will occupy an empty page table entry.
88 // Make a simple attempt to account for that.
89 size_t numRemainderPages
= i
& (kNumSystemPagesPerPartitionPage
- 1);
90 size_t numUnfaultedPages
= numRemainderPages
? (kNumSystemPagesPerPartitionPage
- numRemainderPages
) : 0;
91 waste
+= sizeof(void*) * numUnfaultedPages
;
92 double wasteRatio
= (double) waste
/ (double) pageSize
;
93 if (wasteRatio
< bestWasteRatio
) {
94 bestWasteRatio
= wasteRatio
;
98 ASSERT(bestPages
> 0);
102 static void partitionAllocBaseInit(PartitionRootBase
* root
)
104 ASSERT(!root
->initialized
);
106 spinLockLock(&PartitionRootBase::gInitializedLock
);
107 if (!PartitionRootBase::gInitialized
) {
108 PartitionRootBase::gInitialized
= true;
109 // We mark the seed page as free to make sure it is skipped by our
110 // logic to find a new active page.
111 PartitionRootBase::gPagedBucket
.activePagesHead
= &PartitionRootGeneric::gSeedPage
;
113 spinLockUnlock(&PartitionRootBase::gInitializedLock
);
115 root
->initialized
= true;
116 root
->totalSizeOfCommittedPages
= 0;
117 root
->totalSizeOfSuperPages
= 0;
118 root
->totalSizeOfDirectMappedPages
= 0;
119 root
->nextSuperPage
= 0;
120 root
->nextPartitionPage
= 0;
121 root
->nextPartitionPageEnd
= 0;
122 root
->firstExtent
= 0;
123 root
->currentExtent
= 0;
124 root
->directMapList
= 0;
126 memset(&root
->globalEmptyPageRing
, '\0', sizeof(root
->globalEmptyPageRing
));
127 root
->globalEmptyPageRingIndex
= 0;
129 // This is a "magic" value so we can test if a root pointer is valid.
130 root
->invertedSelf
= ~reinterpret_cast<uintptr_t>(root
);
133 static void partitionBucketInitBase(PartitionBucket
* bucket
, PartitionRootBase
* root
)
135 bucket
->activePagesHead
= &PartitionRootGeneric::gSeedPage
;
136 bucket
->emptyPagesHead
= 0;
137 bucket
->decommittedPagesHead
= 0;
138 bucket
->numFullPages
= 0;
139 bucket
->numSystemPagesPerSlotSpan
= partitionBucketNumSystemPages(bucket
->slotSize
);
142 void partitionAllocGlobalInit(void (*oomHandlingFunction
)())
144 ASSERT(oomHandlingFunction
);
145 PartitionRootBase::gOomHandlingFunction
= oomHandlingFunction
;
148 void partitionAllocInit(PartitionRoot
* root
, size_t numBuckets
, size_t maxAllocation
)
150 partitionAllocBaseInit(root
);
152 root
->numBuckets
= numBuckets
;
153 root
->maxAllocation
= maxAllocation
;
155 for (i
= 0; i
< root
->numBuckets
; ++i
) {
156 PartitionBucket
* bucket
= &root
->buckets()[i
];
158 bucket
->slotSize
= kAllocationGranularity
;
160 bucket
->slotSize
= i
<< kBucketShift
;
161 partitionBucketInitBase(bucket
, root
);
165 void partitionAllocGenericInit(PartitionRootGeneric
* root
)
167 partitionAllocBaseInit(root
);
171 // Precalculate some shift and mask constants used in the hot path.
172 // Example: malloc(41) == 101001 binary.
173 // Order is 6 (1 << 6-1)==32 is highest bit set.
174 // orderIndex is the next three MSB == 010 == 2.
175 // subOrderIndexMask is a mask for the remaining bits == 11 (masking to 01 for the subOrderIndex).
177 for (order
= 0; order
<= kBitsPerSizet
; ++order
) {
178 size_t orderIndexShift
;
179 if (order
< kGenericNumBucketsPerOrderBits
+ 1)
182 orderIndexShift
= order
- (kGenericNumBucketsPerOrderBits
+ 1);
183 root
->orderIndexShifts
[order
] = orderIndexShift
;
184 size_t subOrderIndexMask
;
185 if (order
== kBitsPerSizet
) {
186 // This avoids invoking undefined behavior for an excessive shift.
187 subOrderIndexMask
= static_cast<size_t>(-1) >> (kGenericNumBucketsPerOrderBits
+ 1);
189 subOrderIndexMask
= ((static_cast<size_t>(1) << order
) - 1) >> (kGenericNumBucketsPerOrderBits
+ 1);
191 root
->orderSubIndexMasks
[order
] = subOrderIndexMask
;
194 // Set up the actual usable buckets first.
195 // Note that typical values (i.e. min allocation size of 8) will result in
196 // pseudo buckets (size==9 etc. or more generally, size is not a multiple
197 // of the smallest allocation granularity).
198 // We avoid them in the bucket lookup map, but we tolerate them to keep the
199 // code simpler and the structures more generic.
201 size_t currentSize
= kGenericSmallestBucket
;
202 size_t currentIncrement
= kGenericSmallestBucket
>> kGenericNumBucketsPerOrderBits
;
203 PartitionBucket
* bucket
= &root
->buckets
[0];
204 for (i
= 0; i
< kGenericNumBucketedOrders
; ++i
) {
205 for (j
= 0; j
< kGenericNumBucketsPerOrder
; ++j
) {
206 bucket
->slotSize
= currentSize
;
207 partitionBucketInitBase(bucket
, root
);
208 // Disable psuedo buckets so that touching them faults.
209 if (currentSize
% kGenericSmallestBucket
)
210 bucket
->activePagesHead
= 0;
211 currentSize
+= currentIncrement
;
214 currentIncrement
<<= 1;
216 ASSERT(currentSize
== 1 << kGenericMaxBucketedOrder
);
217 ASSERT(bucket
== &root
->buckets
[0] + kGenericNumBuckets
);
219 // Then set up the fast size -> bucket lookup table.
220 bucket
= &root
->buckets
[0];
221 PartitionBucket
** bucketPtr
= &root
->bucketLookups
[0];
222 for (order
= 0; order
<= kBitsPerSizet
; ++order
) {
223 for (j
= 0; j
< kGenericNumBucketsPerOrder
; ++j
) {
224 if (order
< kGenericMinBucketedOrder
) {
225 // Use the bucket of the finest granularity for malloc(0) etc.
226 *bucketPtr
++ = &root
->buckets
[0];
227 } else if (order
> kGenericMaxBucketedOrder
) {
228 *bucketPtr
++ = &PartitionRootGeneric::gPagedBucket
;
230 PartitionBucket
* validBucket
= bucket
;
231 // Skip over invalid buckets.
232 while (validBucket
->slotSize
% kGenericSmallestBucket
)
234 *bucketPtr
++ = validBucket
;
239 ASSERT(bucket
== &root
->buckets
[0] + kGenericNumBuckets
);
240 ASSERT(bucketPtr
== &root
->bucketLookups
[0] + ((kBitsPerSizet
+ 1) * kGenericNumBucketsPerOrder
));
241 // And there's one last bucket lookup that will be hit for e.g. malloc(-1),
242 // which tries to overflow to a non-existant order.
243 *bucketPtr
= &PartitionRootGeneric::gPagedBucket
;
246 static bool partitionAllocShutdownBucket(PartitionBucket
* bucket
)
248 // Failure here indicates a memory leak.
249 bool foundLeak
= bucket
->numFullPages
;
250 for (PartitionPage
* page
= bucket
->activePagesHead
; page
; page
= page
->nextPage
)
251 foundLeak
|= (page
->numAllocatedSlots
> 0);
255 static bool partitionAllocBaseShutdown(PartitionRootBase
* root
)
257 ASSERT(root
->initialized
);
258 root
->initialized
= false;
260 // Now that we've examined all partition pages in all buckets, it's safe
261 // to free all our super pages. Since the super page extent entries are
262 // stored in the super pages, we need to be careful not to access them
263 // after we've released the corresponding super page.
264 PartitionSuperPageExtentEntry
* entry
= root
->firstExtent
;
266 PartitionSuperPageExtentEntry
* nextEntry
= entry
->next
;
267 char* superPage
= entry
->superPageBase
;
268 char* superPagesEnd
= entry
->superPagesEnd
;
269 while (superPage
< superPagesEnd
) {
270 freePages(superPage
, kSuperPageSize
);
271 superPage
+= kSuperPageSize
;
275 return root
->directMapList
;
278 bool partitionAllocShutdown(PartitionRoot
* root
)
280 bool foundLeak
= false;
282 for (i
= 0; i
< root
->numBuckets
; ++i
) {
283 PartitionBucket
* bucket
= &root
->buckets()[i
];
284 foundLeak
|= partitionAllocShutdownBucket(bucket
);
286 foundLeak
|= partitionAllocBaseShutdown(root
);
290 bool partitionAllocGenericShutdown(PartitionRootGeneric
* root
)
292 bool foundLeak
= false;
294 for (i
= 0; i
< kGenericNumBuckets
; ++i
) {
295 PartitionBucket
* bucket
= &root
->buckets
[i
];
296 foundLeak
|= partitionAllocShutdownBucket(bucket
);
298 foundLeak
|= partitionAllocBaseShutdown(root
);
303 static NEVER_INLINE
void partitionOutOfMemoryWithLotsOfUncommitedPages()
309 static NEVER_INLINE
void partitionOutOfMemory(const PartitionRootBase
* root
)
312 // Check whether this OOM is due to a lot of super pages that are allocated
313 // but not committed, probably due to http://crbug.com/421387.
314 if (root
->totalSizeOfSuperPages
+ root
->totalSizeOfDirectMappedPages
- root
->totalSizeOfCommittedPages
> kReasonableSizeOfUnusedPages
) {
315 partitionOutOfMemoryWithLotsOfUncommitedPages();
318 if (PartitionRootBase::gOomHandlingFunction
)
319 (*PartitionRootBase::gOomHandlingFunction
)();
323 static NEVER_INLINE
void partitionExcessiveAllocationSize()
328 static NEVER_INLINE
void partitionBucketFull()
333 // partitionPageStateIs*
334 // Note that it's only valid to call these functions on pages found on one of
335 // the page lists. Specifically, you can't call these functions on full pages
336 // that were detached from the active list.
337 static bool ALWAYS_INLINE
partitionPageStateIsActive(const PartitionPage
* page
)
339 ASSERT(page
!= &PartitionRootGeneric::gSeedPage
);
340 ASSERT(!page
->pageOffset
);
341 return (page
->numAllocatedSlots
> 0 && (page
->freelistHead
|| page
->numUnprovisionedSlots
));
344 static bool ALWAYS_INLINE
partitionPageStateIsFull(const PartitionPage
* page
)
346 ASSERT(page
!= &PartitionRootGeneric::gSeedPage
);
347 ASSERT(!page
->pageOffset
);
348 bool ret
= (page
->numAllocatedSlots
== partitionBucketSlots(page
->bucket
));
350 ASSERT(!page
->freelistHead
);
351 ASSERT(!page
->numUnprovisionedSlots
);
356 static bool ALWAYS_INLINE
partitionPageStateIsEmpty(const PartitionPage
* page
)
358 ASSERT(page
!= &PartitionRootGeneric::gSeedPage
);
359 ASSERT(!page
->pageOffset
);
360 return (!page
->numAllocatedSlots
&& page
->freelistHead
);
363 static bool ALWAYS_INLINE
partitionPageStateIsDecommitted(const PartitionPage
* page
)
365 ASSERT(page
!= &PartitionRootGeneric::gSeedPage
);
366 ASSERT(!page
->pageOffset
);
367 bool ret
= (!page
->numAllocatedSlots
&& !page
->freelistHead
);
369 ASSERT(!page
->numUnprovisionedSlots
);
370 ASSERT(page
->emptyCacheIndex
== -1);
375 static void partitionIncreaseCommittedPages(PartitionRootBase
* root
, size_t len
)
377 root
->totalSizeOfCommittedPages
+= len
;
378 ASSERT(root
->totalSizeOfCommittedPages
<= root
->totalSizeOfSuperPages
+ root
->totalSizeOfDirectMappedPages
);
381 static void partitionDecreaseCommittedPages(PartitionRootBase
* root
, size_t len
)
383 root
->totalSizeOfCommittedPages
-= len
;
384 ASSERT(root
->totalSizeOfCommittedPages
<= root
->totalSizeOfSuperPages
+ root
->totalSizeOfDirectMappedPages
);
387 static ALWAYS_INLINE
void partitionDecommitSystemPages(PartitionRootBase
* root
, void* addr
, size_t len
)
389 decommitSystemPages(addr
, len
);
390 partitionDecreaseCommittedPages(root
, len
);
393 static ALWAYS_INLINE
void partitionRecommitSystemPages(PartitionRootBase
* root
, void* addr
, size_t len
)
395 recommitSystemPages(addr
, len
);
396 partitionIncreaseCommittedPages(root
, len
);
399 static ALWAYS_INLINE
void* partitionAllocPartitionPages(PartitionRootBase
* root
, int flags
, uint16_t numPartitionPages
)
401 ASSERT(!(reinterpret_cast<uintptr_t>(root
->nextPartitionPage
) % kPartitionPageSize
));
402 ASSERT(!(reinterpret_cast<uintptr_t>(root
->nextPartitionPageEnd
) % kPartitionPageSize
));
403 ASSERT(numPartitionPages
<= kNumPartitionPagesPerSuperPage
);
404 size_t totalSize
= kPartitionPageSize
* numPartitionPages
;
405 size_t numPartitionPagesLeft
= (root
->nextPartitionPageEnd
- root
->nextPartitionPage
) >> kPartitionPageShift
;
406 if (LIKELY(numPartitionPagesLeft
>= numPartitionPages
)) {
407 // In this case, we can still hand out pages from the current super page
409 char* ret
= root
->nextPartitionPage
;
410 root
->nextPartitionPage
+= totalSize
;
411 partitionIncreaseCommittedPages(root
, totalSize
);
415 // Need a new super page. We want to allocate super pages in a continguous
416 // address region as much as possible. This is important for not causing
417 // page table bloat and not fragmenting address spaces in 32 bit architectures.
418 char* requestedAddress
= root
->nextSuperPage
;
419 char* superPage
= reinterpret_cast<char*>(allocPages(requestedAddress
, kSuperPageSize
, kSuperPageSize
, PageAccessible
));
420 if (UNLIKELY(!superPage
))
423 root
->totalSizeOfSuperPages
+= kSuperPageSize
;
424 partitionIncreaseCommittedPages(root
, totalSize
);
426 root
->nextSuperPage
= superPage
+ kSuperPageSize
;
427 char* ret
= superPage
+ kPartitionPageSize
;
428 root
->nextPartitionPage
= ret
+ totalSize
;
429 root
->nextPartitionPageEnd
= root
->nextSuperPage
- kPartitionPageSize
;
430 // Make the first partition page in the super page a guard page, but leave a
431 // hole in the middle.
432 // This is where we put page metadata and also a tiny amount of extent
434 setSystemPagesInaccessible(superPage
, kSystemPageSize
);
435 setSystemPagesInaccessible(superPage
+ (kSystemPageSize
* 2), kPartitionPageSize
- (kSystemPageSize
* 2));
436 // Also make the last partition page a guard page.
437 setSystemPagesInaccessible(superPage
+ (kSuperPageSize
- kPartitionPageSize
), kPartitionPageSize
);
439 // If we were after a specific address, but didn't get it, assume that
440 // the system chose a lousy address. Here most OS'es have a default
441 // algorithm that isn't randomized. For example, most Linux
442 // distributions will allocate the mapping directly before the last
443 // successful mapping, which is far from random. So we just get fresh
444 // randomness for the next mapping attempt.
445 if (requestedAddress
&& requestedAddress
!= superPage
)
446 root
->nextSuperPage
= 0;
448 // We allocated a new super page so update super page metadata.
449 // First check if this is a new extent or not.
450 PartitionSuperPageExtentEntry
* latestExtent
= reinterpret_cast<PartitionSuperPageExtentEntry
*>(partitionSuperPageToMetadataArea(superPage
));
451 // By storing the root in every extent metadata object, we have a fast way
452 // to go from a pointer within the partition to the root object.
453 latestExtent
->root
= root
;
454 // Most new extents will be part of a larger extent, and these three fields
455 // are unused, but we initialize them to 0 so that we get a clear signal
456 // in case they are accidentally used.
457 latestExtent
->superPageBase
= 0;
458 latestExtent
->superPagesEnd
= 0;
459 latestExtent
->next
= 0;
461 PartitionSuperPageExtentEntry
* currentExtent
= root
->currentExtent
;
462 bool isNewExtent
= (superPage
!= requestedAddress
);
463 if (UNLIKELY(isNewExtent
)) {
464 if (UNLIKELY(!currentExtent
)) {
465 ASSERT(!root
->firstExtent
);
466 root
->firstExtent
= latestExtent
;
468 ASSERT(currentExtent
->superPageBase
);
469 currentExtent
->next
= latestExtent
;
471 root
->currentExtent
= latestExtent
;
472 latestExtent
->superPageBase
= superPage
;
473 latestExtent
->superPagesEnd
= superPage
+ kSuperPageSize
;
475 // We allocated next to an existing extent so just nudge the size up a little.
476 ASSERT(currentExtent
->superPagesEnd
);
477 currentExtent
->superPagesEnd
+= kSuperPageSize
;
478 ASSERT(ret
>= currentExtent
->superPageBase
&& ret
< currentExtent
->superPagesEnd
);
483 static ALWAYS_INLINE
uint16_t partitionBucketPartitionPages(const PartitionBucket
* bucket
)
485 return (bucket
->numSystemPagesPerSlotSpan
+ (kNumSystemPagesPerPartitionPage
- 1)) / kNumSystemPagesPerPartitionPage
;
488 static ALWAYS_INLINE
void partitionPageReset(PartitionPage
* page
)
490 ASSERT(partitionPageStateIsDecommitted(page
));
492 page
->numUnprovisionedSlots
= partitionBucketSlots(page
->bucket
);
493 ASSERT(page
->numUnprovisionedSlots
);
495 page
->nextPage
= nullptr;
498 static ALWAYS_INLINE
void partitionPageSetup(PartitionPage
* page
, PartitionBucket
* bucket
)
500 // The bucket never changes. We set it up once.
501 page
->bucket
= bucket
;
502 page
->emptyCacheIndex
= -1;
504 partitionPageReset(page
);
506 // If this page has just a single slot, do not set up page offsets for any
507 // page metadata other than the first one. This ensures that attempts to
508 // touch invalid page metadata fail.
509 if (page
->numUnprovisionedSlots
== 1)
512 uint16_t numPartitionPages
= partitionBucketPartitionPages(bucket
);
513 char* pageCharPtr
= reinterpret_cast<char*>(page
);
514 for (uint16_t i
= 1; i
< numPartitionPages
; ++i
) {
515 pageCharPtr
+= kPageMetadataSize
;
516 PartitionPage
* secondaryPage
= reinterpret_cast<PartitionPage
*>(pageCharPtr
);
517 secondaryPage
->pageOffset
= i
;
521 static ALWAYS_INLINE
size_t partitionRoundUpToSystemPage(size_t size
)
523 return (size
+ kSystemPageOffsetMask
) & kSystemPageBaseMask
;
526 static ALWAYS_INLINE
size_t partitionRoundDownToSystemPage(size_t size
)
528 return size
& kSystemPageBaseMask
;
531 static ALWAYS_INLINE
char* partitionPageAllocAndFillFreelist(PartitionPage
* page
)
533 ASSERT(page
!= &PartitionRootGeneric::gSeedPage
);
534 uint16_t numSlots
= page
->numUnprovisionedSlots
;
536 PartitionBucket
* bucket
= page
->bucket
;
537 // We should only get here when _every_ slot is either used or unprovisioned.
538 // (The third state is "on the freelist". If we have a non-empty freelist, we should not get here.)
539 ASSERT(numSlots
+ page
->numAllocatedSlots
== partitionBucketSlots(bucket
));
540 // Similarly, make explicitly sure that the freelist is empty.
541 ASSERT(!page
->freelistHead
);
542 ASSERT(page
->numAllocatedSlots
>= 0);
544 size_t size
= bucket
->slotSize
;
545 char* base
= reinterpret_cast<char*>(partitionPageToPointer(page
));
546 char* returnObject
= base
+ (size
* page
->numAllocatedSlots
);
547 char* firstFreelistPointer
= returnObject
+ size
;
548 char* firstFreelistPointerExtent
= firstFreelistPointer
+ sizeof(PartitionFreelistEntry
*);
549 // Our goal is to fault as few system pages as possible. We calculate the
550 // page containing the "end" of the returned slot, and then allow freelist
551 // pointers to be written up to the end of that page.
552 char* subPageLimit
= reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_cast<size_t>(firstFreelistPointer
)));
553 char* slotsLimit
= returnObject
+ (size
* numSlots
);
554 char* freelistLimit
= subPageLimit
;
555 if (UNLIKELY(slotsLimit
< freelistLimit
))
556 freelistLimit
= slotsLimit
;
558 uint16_t numNewFreelistEntries
= 0;
559 if (LIKELY(firstFreelistPointerExtent
<= freelistLimit
)) {
560 // Only consider used space in the slot span. If we consider wasted
561 // space, we may get an off-by-one when a freelist pointer fits in the
562 // wasted space, but a slot does not.
563 // We know we can fit at least one freelist pointer.
564 numNewFreelistEntries
= 1;
565 // Any further entries require space for the whole slot span.
566 numNewFreelistEntries
+= static_cast<uint16_t>((freelistLimit
- firstFreelistPointerExtent
) / size
);
569 // We always return an object slot -- that's the +1 below.
570 // We do not neccessarily create any new freelist entries, because we cross sub page boundaries frequently for large bucket sizes.
571 ASSERT(numNewFreelistEntries
+ 1 <= numSlots
);
572 numSlots
-= (numNewFreelistEntries
+ 1);
573 page
->numUnprovisionedSlots
= numSlots
;
574 page
->numAllocatedSlots
++;
576 if (LIKELY(numNewFreelistEntries
)) {
577 char* freelistPointer
= firstFreelistPointer
;
578 PartitionFreelistEntry
* entry
= reinterpret_cast<PartitionFreelistEntry
*>(freelistPointer
);
579 page
->freelistHead
= entry
;
580 while (--numNewFreelistEntries
) {
581 freelistPointer
+= size
;
582 PartitionFreelistEntry
* nextEntry
= reinterpret_cast<PartitionFreelistEntry
*>(freelistPointer
);
583 entry
->next
= partitionFreelistMask(nextEntry
);
586 entry
->next
= partitionFreelistMask(0);
588 page
->freelistHead
= 0;
593 // This helper function scans a bucket's active page list for a suitable new
595 // When it finds a suitable new active page (one that has free slots and is not
596 // empty), it is set as the new active page. If there is no suitable new
597 // active page, the current active page is set to the seed page.
598 // As potential pages are scanned, they are tidied up according to their state.
599 // Empty pages are swept on to the empty page list, decommitted pages on to the
600 // decommitted page list and full pages are unlinked from any list.
601 static bool partitionSetNewActivePage(PartitionBucket
* bucket
)
603 PartitionPage
* page
= bucket
->activePagesHead
;
604 if (page
== &PartitionRootBase::gSeedPage
)
607 PartitionPage
* nextPage
;
609 for (; page
; page
= nextPage
) {
610 nextPage
= page
->nextPage
;
611 ASSERT(page
->bucket
== bucket
);
612 ASSERT(page
!= bucket
->emptyPagesHead
);
613 ASSERT(page
!= bucket
->decommittedPagesHead
);
615 // Deal with empty and decommitted pages.
616 if (LIKELY(partitionPageStateIsActive(page
))) {
617 // This page is usable because it has freelist entries, or has
618 // unprovisioned slots we can create freelist entries from.
619 bucket
->activePagesHead
= page
;
622 if (LIKELY(partitionPageStateIsEmpty(page
))) {
623 page
->nextPage
= bucket
->emptyPagesHead
;
624 bucket
->emptyPagesHead
= page
;
625 } else if (LIKELY(partitionPageStateIsDecommitted(page
))) {
626 page
->nextPage
= bucket
->decommittedPagesHead
;
627 bucket
->decommittedPagesHead
= page
;
629 ASSERT(partitionPageStateIsFull(page
));
630 // If we get here, we found a full page. Skip over it too, and also
631 // tag it as full (via a negative value). We need it tagged so that
632 // free'ing can tell, and move it back into the active page list.
633 page
->numAllocatedSlots
= -page
->numAllocatedSlots
;
634 ++bucket
->numFullPages
;
635 // numFullPages is a uint16_t for efficient packing so guard against
636 // overflow to be safe.
637 if (UNLIKELY(!bucket
->numFullPages
))
638 partitionBucketFull();
639 // Not necessary but might help stop accidents.
644 bucket
->activePagesHead
= &PartitionRootGeneric::gSeedPage
;
648 static ALWAYS_INLINE PartitionDirectMapExtent
* partitionPageToDirectMapExtent(PartitionPage
* page
)
650 ASSERT(partitionBucketIsDirectMapped(page
->bucket
));
651 return reinterpret_cast<PartitionDirectMapExtent
*>(reinterpret_cast<char*>(page
) + 3 * kPageMetadataSize
);
654 static ALWAYS_INLINE
void partitionPageSetRawSize(PartitionPage
* page
, size_t size
)
656 size_t* rawSizePtr
= partitionPageGetRawSizePtr(page
);
657 if (UNLIKELY(rawSizePtr
!= nullptr))
661 static ALWAYS_INLINE PartitionPage
* partitionDirectMap(PartitionRootBase
* root
, int flags
, size_t rawSize
)
663 size_t size
= partitionDirectMapSize(rawSize
);
665 // Because we need to fake looking like a super page, we need to allocate
666 // a bunch of system pages more than "size":
667 // - The first few system pages are the partition page in which the super
668 // page metadata is stored. We fault just one system page out of a partition
670 // - We add a trailing guard page on 32-bit (on 64-bit we rely on the
671 // massive address space plus randomization instead).
672 size_t mapSize
= size
+ kPartitionPageSize
;
674 mapSize
+= kSystemPageSize
;
676 // Round up to the allocation granularity.
677 mapSize
+= kPageAllocationGranularityOffsetMask
;
678 mapSize
&= kPageAllocationGranularityBaseMask
;
680 // TODO: these pages will be zero-filled. Consider internalizing an
681 // allocZeroed() API so we can avoid a memset() entirely in this case.
682 char* ptr
= reinterpret_cast<char*>(allocPages(0, mapSize
, kSuperPageSize
, PageAccessible
));
686 size_t committedPageSize
= size
+ kSystemPageSize
;
687 root
->totalSizeOfDirectMappedPages
+= committedPageSize
;
688 partitionIncreaseCommittedPages(root
, committedPageSize
);
690 char* slot
= ptr
+ kPartitionPageSize
;
691 setSystemPagesInaccessible(ptr
+ (kSystemPageSize
* 2), kPartitionPageSize
- (kSystemPageSize
* 2));
693 setSystemPagesInaccessible(ptr
, kSystemPageSize
);
694 setSystemPagesInaccessible(slot
+ size
, kSystemPageSize
);
697 PartitionSuperPageExtentEntry
* extent
= reinterpret_cast<PartitionSuperPageExtentEntry
*>(partitionSuperPageToMetadataArea(ptr
));
699 // The new structures are all located inside a fresh system page so they
700 // will all be zeroed out. These ASSERTs are for documentation.
701 ASSERT(!extent
->superPageBase
);
702 ASSERT(!extent
->superPagesEnd
);
703 ASSERT(!extent
->next
);
704 PartitionPage
* page
= partitionPointerToPageNoAlignmentCheck(slot
);
705 PartitionBucket
* bucket
= reinterpret_cast<PartitionBucket
*>(reinterpret_cast<char*>(page
) + (kPageMetadataSize
* 2));
706 ASSERT(!page
->nextPage
);
707 ASSERT(!page
->numAllocatedSlots
);
708 ASSERT(!page
->numUnprovisionedSlots
);
709 ASSERT(!page
->pageOffset
);
710 ASSERT(!page
->emptyCacheIndex
);
711 page
->bucket
= bucket
;
712 page
->freelistHead
= reinterpret_cast<PartitionFreelistEntry
*>(slot
);
713 PartitionFreelistEntry
* nextEntry
= reinterpret_cast<PartitionFreelistEntry
*>(slot
);
714 nextEntry
->next
= partitionFreelistMask(0);
716 ASSERT(!bucket
->activePagesHead
);
717 ASSERT(!bucket
->emptyPagesHead
);
718 ASSERT(!bucket
->decommittedPagesHead
);
719 ASSERT(!bucket
->numSystemPagesPerSlotSpan
);
720 ASSERT(!bucket
->numFullPages
);
721 bucket
->slotSize
= size
;
723 PartitionDirectMapExtent
* mapExtent
= partitionPageToDirectMapExtent(page
);
724 mapExtent
->mapSize
= mapSize
- kPartitionPageSize
- kSystemPageSize
;
725 mapExtent
->bucket
= bucket
;
727 // Maintain the doubly-linked list of all direct mappings.
728 mapExtent
->nextExtent
= root
->directMapList
;
729 if (mapExtent
->nextExtent
)
730 mapExtent
->nextExtent
->prevExtent
= mapExtent
;
731 mapExtent
->prevExtent
= nullptr;
732 root
->directMapList
= mapExtent
;
737 static ALWAYS_INLINE
void partitionDirectUnmap(PartitionPage
* page
)
739 PartitionRootBase
* root
= partitionPageToRoot(page
);
740 const PartitionDirectMapExtent
* extent
= partitionPageToDirectMapExtent(page
);
741 size_t unmapSize
= extent
->mapSize
;
743 // Maintain the doubly-linked list of all direct mappings.
744 if (extent
->prevExtent
) {
745 ASSERT(extent
->prevExtent
->nextExtent
== extent
);
746 extent
->prevExtent
->nextExtent
= extent
->nextExtent
;
748 root
->directMapList
= extent
->nextExtent
;
750 if (extent
->nextExtent
) {
751 ASSERT(extent
->nextExtent
->prevExtent
== extent
);
752 extent
->nextExtent
->prevExtent
= extent
->prevExtent
;
755 // Add on the size of the trailing guard page and preceeding partition
757 unmapSize
+= kPartitionPageSize
+ kSystemPageSize
;
759 size_t uncommittedPageSize
= page
->bucket
->slotSize
+ kSystemPageSize
;
760 partitionDecreaseCommittedPages(root
, uncommittedPageSize
);
761 ASSERT(root
->totalSizeOfDirectMappedPages
>= uncommittedPageSize
);
762 root
->totalSizeOfDirectMappedPages
-= uncommittedPageSize
;
764 ASSERT(!(unmapSize
& kPageAllocationGranularityOffsetMask
));
766 char* ptr
= reinterpret_cast<char*>(partitionPageToPointer(page
));
767 // Account for the mapping starting a partition page before the actual
768 // allocation address.
769 ptr
-= kPartitionPageSize
;
771 freePages(ptr
, unmapSize
);
774 void* partitionAllocSlowPath(PartitionRootBase
* root
, int flags
, size_t size
, PartitionBucket
* bucket
)
776 // The slow path is called when the freelist is empty.
777 ASSERT(!bucket
->activePagesHead
->freelistHead
);
779 PartitionPage
* newPage
= nullptr;
781 // For the partitionAllocGeneric API, we have a bunch of buckets marked
782 // as special cases. We bounce them through to the slow path so that we
783 // can still have a blazing fast hot path due to lack of corner-case
785 bool returnNull
= flags
& PartitionAllocReturnNull
;
786 if (UNLIKELY(partitionBucketIsDirectMapped(bucket
))) {
787 ASSERT(size
> kGenericMaxBucketed
);
788 ASSERT(bucket
== &PartitionRootBase::gPagedBucket
);
789 ASSERT(bucket
->activePagesHead
== &PartitionRootGeneric::gSeedPage
);
790 if (size
> kGenericMaxDirectMapped
) {
793 partitionExcessiveAllocationSize();
795 newPage
= partitionDirectMap(root
, flags
, size
);
796 } else if (LIKELY(partitionSetNewActivePage(bucket
))) {
797 // First, did we find an active page in the active pages list?
798 newPage
= bucket
->activePagesHead
;
799 ASSERT(partitionPageStateIsActive(newPage
));
800 } else if (LIKELY(bucket
->emptyPagesHead
!= nullptr) || LIKELY(bucket
->decommittedPagesHead
!= nullptr)) {
801 // Second, look in our lists of empty and decommitted pages.
802 // Check empty pages first, which are preferred, but beware that an
803 // empty page might have been decommitted.
804 while (LIKELY((newPage
= bucket
->emptyPagesHead
) != nullptr)) {
805 ASSERT(newPage
->bucket
== bucket
);
806 ASSERT(partitionPageStateIsEmpty(newPage
) || partitionPageStateIsDecommitted(newPage
));
807 bucket
->emptyPagesHead
= newPage
->nextPage
;
808 // Accept the empty page unless it got decommitted.
809 if (newPage
->freelistHead
) {
810 newPage
->nextPage
= nullptr;
813 ASSERT(partitionPageStateIsDecommitted(newPage
));
814 newPage
->nextPage
= bucket
->decommittedPagesHead
;
815 bucket
->decommittedPagesHead
= newPage
;
817 if (UNLIKELY(!newPage
) && LIKELY(bucket
->decommittedPagesHead
!= nullptr)) {
818 newPage
= bucket
->decommittedPagesHead
;
819 ASSERT(newPage
->bucket
== bucket
);
820 ASSERT(partitionPageStateIsDecommitted(newPage
));
821 bucket
->decommittedPagesHead
= newPage
->nextPage
;
822 void* addr
= partitionPageToPointer(newPage
);
823 partitionRecommitSystemPages(root
, addr
, partitionBucketBytes(newPage
->bucket
));
824 partitionPageReset(newPage
);
828 // Third. If we get here, we need a brand new page.
829 uint16_t numPartitionPages
= partitionBucketPartitionPages(bucket
);
830 void* rawPages
= partitionAllocPartitionPages(root
, flags
, numPartitionPages
);
831 if (LIKELY(rawPages
!= nullptr)) {
832 newPage
= partitionPointerToPageNoAlignmentCheck(rawPages
);
833 partitionPageSetup(newPage
, bucket
);
837 // Bail if we had a memory allocation failure.
838 if (UNLIKELY(!newPage
)) {
839 ASSERT(bucket
->activePagesHead
== &PartitionRootGeneric::gSeedPage
);
842 partitionOutOfMemory(root
);
845 bucket
= newPage
->bucket
;
846 ASSERT(bucket
!= &PartitionRootBase::gPagedBucket
);
847 bucket
->activePagesHead
= newPage
;
848 partitionPageSetRawSize(newPage
, size
);
850 // If we found an active page with free slots, or an empty page, we have a
851 // usable freelist head.
852 if (LIKELY(newPage
->freelistHead
!= nullptr)) {
853 PartitionFreelistEntry
* entry
= newPage
->freelistHead
;
854 PartitionFreelistEntry
* newHead
= partitionFreelistMask(entry
->next
);
855 newPage
->freelistHead
= newHead
;
856 newPage
->numAllocatedSlots
++;
859 // Otherwise, we need to build the freelist.
860 ASSERT(newPage
->numUnprovisionedSlots
);
861 return partitionPageAllocAndFillFreelist(newPage
);
864 static ALWAYS_INLINE
void partitionDecommitPage(PartitionRootBase
* root
, PartitionPage
* page
)
866 ASSERT(partitionPageStateIsEmpty(page
));
867 ASSERT(!partitionBucketIsDirectMapped(page
->bucket
));
868 void* addr
= partitionPageToPointer(page
);
869 partitionDecommitSystemPages(root
, addr
, partitionBucketBytes(page
->bucket
));
871 // We actually leave the decommitted page in the active list. We'll sweep
872 // it on to the decommitted page list when we next walk the active page
874 // Pulling this trick enables us to use a singly-linked page list for all
875 // cases, which is critical in keeping the page metadata structure down to
877 page
->freelistHead
= 0;
878 page
->numUnprovisionedSlots
= 0;
879 ASSERT(partitionPageStateIsDecommitted(page
));
882 static void partitionDecommitPageIfPossible(PartitionRootBase
* root
, PartitionPage
* page
)
884 ASSERT(page
->emptyCacheIndex
>= 0);
885 ASSERT(static_cast<unsigned>(page
->emptyCacheIndex
) < kMaxFreeableSpans
);
886 ASSERT(page
== root
->globalEmptyPageRing
[page
->emptyCacheIndex
]);
887 page
->emptyCacheIndex
= -1;
888 if (partitionPageStateIsEmpty(page
))
889 partitionDecommitPage(root
, page
);
892 static ALWAYS_INLINE
void partitionRegisterEmptyPage(PartitionPage
* page
)
894 ASSERT(partitionPageStateIsEmpty(page
));
895 PartitionRootBase
* root
= partitionPageToRoot(page
);
897 // If the page is already registered as empty, give it another life.
898 if (page
->emptyCacheIndex
!= -1) {
899 ASSERT(page
->emptyCacheIndex
>= 0);
900 ASSERT(static_cast<unsigned>(page
->emptyCacheIndex
) < kMaxFreeableSpans
);
901 ASSERT(root
->globalEmptyPageRing
[page
->emptyCacheIndex
] == page
);
902 root
->globalEmptyPageRing
[page
->emptyCacheIndex
] = 0;
905 int16_t currentIndex
= root
->globalEmptyPageRingIndex
;
906 PartitionPage
* pageToDecommit
= root
->globalEmptyPageRing
[currentIndex
];
907 // The page might well have been re-activated, filled up, etc. before we get
908 // around to looking at it here.
910 partitionDecommitPageIfPossible(root
, pageToDecommit
);
912 // We put the empty slot span on our global list of "pages that were once
913 // empty". thus providing it a bit of breathing room to get re-used before
914 // we really free it. This improves performance, particularly on Mac OS X
915 // which has subpar memory management performance.
916 root
->globalEmptyPageRing
[currentIndex
] = page
;
917 page
->emptyCacheIndex
= currentIndex
;
919 if (currentIndex
== kMaxFreeableSpans
)
921 root
->globalEmptyPageRingIndex
= currentIndex
;
924 static void partitionDecommitEmptyPages(PartitionRootBase
* root
)
926 for (size_t i
= 0; i
< kMaxFreeableSpans
; ++i
) {
927 PartitionPage
* page
= root
->globalEmptyPageRing
[i
];
929 partitionDecommitPageIfPossible(root
, page
);
930 root
->globalEmptyPageRing
[i
] = nullptr;
934 void partitionFreeSlowPath(PartitionPage
* page
)
936 PartitionBucket
* bucket
= page
->bucket
;
937 ASSERT(page
!= &PartitionRootGeneric::gSeedPage
);
938 if (LIKELY(page
->numAllocatedSlots
== 0)) {
939 // Page became fully unused.
940 if (UNLIKELY(partitionBucketIsDirectMapped(bucket
))) {
941 partitionDirectUnmap(page
);
944 // If it's the current active page, change it. We bounce the page to
945 // the empty list as a force towards defragmentation.
946 if (LIKELY(page
== bucket
->activePagesHead
))
947 (void) partitionSetNewActivePage(bucket
);
948 ASSERT(bucket
->activePagesHead
!= page
);
950 partitionPageSetRawSize(page
, 0);
951 ASSERT(!partitionPageGetRawSize(page
));
953 partitionRegisterEmptyPage(page
);
955 ASSERT(!partitionBucketIsDirectMapped(bucket
));
956 // Ensure that the page is full. That's the only valid case if we
958 ASSERT(page
->numAllocatedSlots
< 0);
959 // A transition of numAllocatedSlots from 0 to -1 is not legal, and
960 // likely indicates a double-free.
961 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(page
->numAllocatedSlots
!= -1);
962 page
->numAllocatedSlots
= -page
->numAllocatedSlots
- 2;
963 ASSERT(page
->numAllocatedSlots
== partitionBucketSlots(bucket
) - 1);
964 // Fully used page became partially used. It must be put back on the
965 // non-full page list. Also make it the current page to increase the
966 // chances of it being filled up again. The old current page will be
968 ASSERT(!page
->nextPage
);
969 if (LIKELY(bucket
->activePagesHead
!= &PartitionRootGeneric::gSeedPage
))
970 page
->nextPage
= bucket
->activePagesHead
;
971 bucket
->activePagesHead
= page
;
972 --bucket
->numFullPages
;
973 // Special case: for a partition page with just a single slot, it may
974 // now be empty and we want to run it through the empty logic.
975 if (UNLIKELY(page
->numAllocatedSlots
== 0))
976 partitionFreeSlowPath(page
);
980 bool partitionReallocDirectMappedInPlace(PartitionRootGeneric
* root
, PartitionPage
* page
, size_t rawSize
)
982 ASSERT(partitionBucketIsDirectMapped(page
->bucket
));
984 rawSize
= partitionCookieSizeAdjustAdd(rawSize
);
986 // Note that the new size might be a bucketed size; this function is called
987 // whenever we're reallocating a direct mapped allocation.
988 size_t newSize
= partitionDirectMapSize(rawSize
);
989 if (newSize
< kGenericMinDirectMappedDownsize
)
992 // bucket->slotSize is the current size of the allocation.
993 size_t currentSize
= page
->bucket
->slotSize
;
994 if (newSize
== currentSize
)
997 char* charPtr
= static_cast<char*>(partitionPageToPointer(page
));
999 if (newSize
< currentSize
) {
1000 size_t mapSize
= partitionPageToDirectMapExtent(page
)->mapSize
;
1002 // Don't reallocate in-place if new size is less than 80 % of the full
1003 // map size, to avoid holding on to too much unused address space.
1004 if ((newSize
/ kSystemPageSize
) * 5 < (mapSize
/ kSystemPageSize
) * 4)
1007 // Shrink by decommitting unneeded pages and making them inaccessible.
1008 size_t decommitSize
= currentSize
- newSize
;
1009 partitionDecommitSystemPages(root
, charPtr
+ newSize
, decommitSize
);
1010 setSystemPagesInaccessible(charPtr
+ newSize
, decommitSize
);
1011 } else if (newSize
<= partitionPageToDirectMapExtent(page
)->mapSize
) {
1012 // Grow within the actually allocated memory. Just need to make the
1013 // pages accessible again.
1014 size_t recommitSize
= newSize
- currentSize
;
1015 bool ret
= setSystemPagesAccessible(charPtr
+ currentSize
, recommitSize
);
1016 RELEASE_ASSERT(ret
);
1017 partitionRecommitSystemPages(root
, charPtr
+ currentSize
, recommitSize
);
1020 memset(charPtr
+ currentSize
, kUninitializedByte
, recommitSize
);
1023 // We can't perform the realloc in-place.
1024 // TODO: support this too when possible.
1029 // Write a new trailing cookie.
1030 partitionCookieWriteValue(charPtr
+ rawSize
- kCookieSize
);
1033 partitionPageSetRawSize(page
, rawSize
);
1034 ASSERT(partitionPageGetRawSize(page
) == rawSize
);
1036 page
->bucket
->slotSize
= newSize
;
1040 void* partitionReallocGeneric(PartitionRootGeneric
* root
, void* ptr
, size_t newSize
)
1042 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
1043 return realloc(ptr
, newSize
);
1046 return partitionAllocGeneric(root
, newSize
);
1047 if (UNLIKELY(!newSize
)) {
1048 partitionFreeGeneric(root
, ptr
);
1052 if (newSize
> kGenericMaxDirectMapped
)
1053 partitionExcessiveAllocationSize();
1055 ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(ptr
)));
1057 PartitionPage
* page
= partitionPointerToPage(partitionCookieFreePointerAdjust(ptr
));
1059 if (UNLIKELY(partitionBucketIsDirectMapped(page
->bucket
))) {
1060 // We may be able to perform the realloc in place by changing the
1061 // accessibility of memory pages and, if reducing the size, decommitting
1063 if (partitionReallocDirectMappedInPlace(root
, page
, newSize
))
1067 size_t actualNewSize
= partitionAllocActualSize(root
, newSize
);
1068 size_t actualOldSize
= partitionAllocGetSize(ptr
);
1070 // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the
1071 // new size is a significant percentage smaller. We could do the same if we
1072 // determine it is a win.
1073 if (actualNewSize
== actualOldSize
) {
1074 // Trying to allocate a block of size newSize would give us a block of
1075 // the same size as the one we've already got, so no point in doing
1080 // This realloc cannot be resized in-place. Sadness.
1081 void* ret
= partitionAllocGeneric(root
, newSize
);
1082 size_t copySize
= actualOldSize
;
1083 if (newSize
< copySize
)
1086 memcpy(ret
, ptr
, copySize
);
1087 partitionFreeGeneric(root
, ptr
);
1092 static size_t partitionPurgePage(PartitionPage
* page
, bool discard
)
1094 const PartitionBucket
* bucket
= page
->bucket
;
1095 size_t slotSize
= bucket
->slotSize
;
1096 if (slotSize
< kSystemPageSize
|| !page
->numAllocatedSlots
)
1099 size_t bucketNumSlots
= partitionBucketSlots(bucket
);
1100 size_t discardableBytes
= 0;
1102 size_t rawSize
= partitionPageGetRawSize(const_cast<PartitionPage
*>(page
));
1104 uint32_t usedBytes
= static_cast<uint32_t>(partitionRoundUpToSystemPage(rawSize
));
1105 discardableBytes
= bucket
->slotSize
- usedBytes
;
1106 if (discardableBytes
&& discard
) {
1107 char* ptr
= reinterpret_cast<char*>(partitionPageToPointer(page
));
1109 discardSystemPages(ptr
, discardableBytes
);
1111 return discardableBytes
;
1114 const size_t maxSlotCount
= (kPartitionPageSize
* kMaxPartitionPagesPerSlotSpan
) / kSystemPageSize
;
1115 ASSERT(bucketNumSlots
<= maxSlotCount
);
1116 ASSERT(page
->numUnprovisionedSlots
< bucketNumSlots
);
1117 size_t numSlots
= bucketNumSlots
- page
->numUnprovisionedSlots
;
1118 char slotUsage
[maxSlotCount
];
1119 size_t lastSlot
= static_cast<size_t>(-1);
1120 memset(slotUsage
, 1, numSlots
);
1121 char* ptr
= reinterpret_cast<char*>(partitionPageToPointer(page
));
1122 PartitionFreelistEntry
* entry
= page
->freelistHead
;
1123 // First, walk the freelist for this page and make a bitmap of which slots
1126 size_t slotIndex
= (reinterpret_cast<char*>(entry
) - ptr
) / slotSize
;
1127 ASSERT(slotIndex
< numSlots
);
1128 slotUsage
[slotIndex
] = 0;
1129 entry
= partitionFreelistMask(entry
->next
);
1130 // If we have a slot where the masked freelist entry is 0, we can
1131 // actually discard that freelist entry because touching a discarded
1132 // page is guaranteed to return original content or 0.
1133 // (Note that this optimization won't fire on big endian machines
1134 // because the masking function is negation.)
1135 if (!partitionFreelistMask(entry
))
1136 lastSlot
= slotIndex
;
1139 // If the slot(s) at the end of the slot span are not in used, we can
1140 // truncate them entirely and rewrite the freelist.
1141 size_t truncatedSlots
= 0;
1142 while (!slotUsage
[numSlots
- 1]) {
1147 // First, do the work of calculating the discardable bytes. Don't actually
1148 // discard anything unless the discard flag was passed in.
1149 char* beginPtr
= nullptr;
1150 char* endPtr
= nullptr;
1151 size_t unprovisionedBytes
= 0;
1152 if (truncatedSlots
) {
1153 beginPtr
= ptr
+ (numSlots
* slotSize
);
1154 endPtr
= beginPtr
+ (slotSize
* truncatedSlots
);
1155 beginPtr
= reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_cast<size_t>(beginPtr
)));
1156 // We round the end pointer here up and not down because we're at the
1157 // end of a slot span, so we "own" all the way up the page boundary.
1158 endPtr
= reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_cast<size_t>(endPtr
)));
1159 ASSERT(endPtr
<= ptr
+ partitionBucketBytes(bucket
));
1160 if (beginPtr
< endPtr
) {
1161 unprovisionedBytes
= endPtr
- beginPtr
;
1162 discardableBytes
+= unprovisionedBytes
;
1165 if (unprovisionedBytes
&& discard
) {
1166 ASSERT(truncatedSlots
> 0);
1167 size_t numNewEntries
= 0;
1168 page
->numUnprovisionedSlots
+= truncatedSlots
;
1169 // Rewrite the freelist.
1170 PartitionFreelistEntry
** entryPtr
= &page
->freelistHead
;
1171 for (size_t slotIndex
= 0; slotIndex
< numSlots
; ++slotIndex
) {
1172 if (slotUsage
[slotIndex
])
1174 PartitionFreelistEntry
* entry
= reinterpret_cast<PartitionFreelistEntry
*>(ptr
+ (slotSize
* slotIndex
));
1175 *entryPtr
= partitionFreelistMask(entry
);
1176 entryPtr
= reinterpret_cast<PartitionFreelistEntry
**>(entry
);
1179 // Terminate the freelist chain.
1180 *entryPtr
= nullptr;
1181 // The freelist head is stored unmasked.
1182 page
->freelistHead
= partitionFreelistMask(page
->freelistHead
);
1183 ASSERT(numNewEntries
== numSlots
- page
->numAllocatedSlots
);
1184 // Discard the memory.
1185 discardSystemPages(beginPtr
, unprovisionedBytes
);
1188 // Next, walk the slots and for any not in use, consider where the system
1189 // page boundaries occur. We can release any system pages back to the
1190 // system as long as we don't interfere with a freelist pointer or an
1192 for (size_t i
= 0; i
< numSlots
; ++i
) {
1195 // The first address we can safely discard is just after the freelist
1196 // pointer. There's one quirk: if the freelist pointer is actually a
1197 // null, we can discard that pointer value too.
1198 char* beginPtr
= ptr
+ (i
* slotSize
);
1199 char* endPtr
= beginPtr
+ slotSize
;
1201 beginPtr
+= sizeof(PartitionFreelistEntry
);
1202 beginPtr
= reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_cast<size_t>(beginPtr
)));
1203 endPtr
= reinterpret_cast<char*>(partitionRoundDownToSystemPage(reinterpret_cast<size_t>(endPtr
)));
1204 if (beginPtr
< endPtr
) {
1205 size_t partialSlotBytes
= endPtr
- beginPtr
;
1206 discardableBytes
+= partialSlotBytes
;
1208 discardSystemPages(beginPtr
, partialSlotBytes
);
1211 return discardableBytes
;
1214 static void partitionPurgeBucket(PartitionBucket
* bucket
)
1216 if (bucket
->activePagesHead
!= &PartitionRootGeneric::gSeedPage
) {
1217 for (PartitionPage
* page
= bucket
->activePagesHead
; page
; page
= page
->nextPage
) {
1218 ASSERT(page
!= &PartitionRootGeneric::gSeedPage
);
1219 (void) partitionPurgePage(page
, true);
1224 void partitionPurgeMemory(PartitionRoot
* root
, int flags
)
1226 if (flags
& PartitionPurgeDecommitEmptyPages
)
1227 partitionDecommitEmptyPages(root
);
1228 // We don't currently do anything for PartitionPurgeDiscardUnusedSystemPages
1229 // here because that flag is only useful for allocations >= system page
1230 // size. We only have allocations that large inside generic partitions
1234 void partitionPurgeMemoryGeneric(PartitionRootGeneric
* root
, int flags
)
1236 spinLockLock(&root
->lock
);
1237 if (flags
& PartitionPurgeDecommitEmptyPages
)
1238 partitionDecommitEmptyPages(root
);
1239 if (flags
& PartitionPurgeDiscardUnusedSystemPages
) {
1240 for (size_t i
= 0; i
< kGenericNumBuckets
; ++i
) {
1241 PartitionBucket
* bucket
= &root
->buckets
[i
];
1242 if (bucket
->slotSize
>= kSystemPageSize
)
1243 partitionPurgeBucket(bucket
);
1246 spinLockUnlock(&root
->lock
);
1249 static void partitionDumpPageStats(PartitionBucketMemoryStats
* statsOut
, const PartitionPage
* page
)
1251 uint16_t bucketNumSlots
= partitionBucketSlots(page
->bucket
);
1253 if (partitionPageStateIsDecommitted(page
)) {
1254 ++statsOut
->numDecommittedPages
;
1258 statsOut
->discardableBytes
+= partitionPurgePage(const_cast<PartitionPage
*>(page
), false);
1260 size_t rawSize
= partitionPageGetRawSize(const_cast<PartitionPage
*>(page
));
1262 statsOut
->activeBytes
+= static_cast<uint32_t>(rawSize
);
1264 statsOut
->activeBytes
+= (page
->numAllocatedSlots
* statsOut
->bucketSlotSize
);
1266 size_t pageBytesResident
= partitionRoundUpToSystemPage((bucketNumSlots
- page
->numUnprovisionedSlots
) * statsOut
->bucketSlotSize
);
1267 statsOut
->residentBytes
+= pageBytesResident
;
1268 if (partitionPageStateIsEmpty(page
)) {
1269 statsOut
->decommittableBytes
+= pageBytesResident
;
1270 ++statsOut
->numEmptyPages
;
1271 } else if (partitionPageStateIsFull(page
)) {
1272 ++statsOut
->numFullPages
;
1274 ASSERT(partitionPageStateIsActive(page
));
1275 ++statsOut
->numActivePages
;
1279 static void partitionDumpBucketStats(PartitionBucketMemoryStats
* statsOut
, const PartitionBucket
* bucket
)
1281 ASSERT(!partitionBucketIsDirectMapped(bucket
));
1282 statsOut
->isValid
= false;
1283 // If the active page list is empty (== &PartitionRootGeneric::gSeedPage),
1284 // the bucket might still need to be reported if it has a list of empty,
1285 // decommitted or full pages.
1286 if (bucket
->activePagesHead
== &PartitionRootGeneric::gSeedPage
&& !bucket
->emptyPagesHead
&& !bucket
->decommittedPagesHead
&& !bucket
->numFullPages
)
1289 memset(statsOut
, '\0', sizeof(*statsOut
));
1290 statsOut
->isValid
= true;
1291 statsOut
->isDirectMap
= false;
1292 statsOut
->numFullPages
= static_cast<size_t>(bucket
->numFullPages
);
1293 statsOut
->bucketSlotSize
= bucket
->slotSize
;
1294 uint16_t bucketNumSlots
= partitionBucketSlots(bucket
);
1295 size_t bucketUsefulStorage
= statsOut
->bucketSlotSize
* bucketNumSlots
;
1296 statsOut
->allocatedPageSize
= partitionBucketBytes(bucket
);
1297 statsOut
->activeBytes
= bucket
->numFullPages
* bucketUsefulStorage
;
1298 statsOut
->residentBytes
= bucket
->numFullPages
* statsOut
->allocatedPageSize
;
1300 for (const PartitionPage
* page
= bucket
->emptyPagesHead
; page
; page
= page
->nextPage
) {
1301 ASSERT(partitionPageStateIsEmpty(page
) || partitionPageStateIsDecommitted(page
));
1302 partitionDumpPageStats(statsOut
, page
);
1304 for (const PartitionPage
* page
= bucket
->decommittedPagesHead
; page
; page
= page
->nextPage
) {
1305 ASSERT(partitionPageStateIsDecommitted(page
));
1306 partitionDumpPageStats(statsOut
, page
);
1309 if (bucket
->activePagesHead
!= &PartitionRootGeneric::gSeedPage
) {
1310 for (const PartitionPage
* page
= bucket
->activePagesHead
; page
; page
= page
->nextPage
) {
1311 ASSERT(page
!= &PartitionRootGeneric::gSeedPage
);
1312 partitionDumpPageStats(statsOut
, page
);
1317 void partitionDumpStatsGeneric(PartitionRootGeneric
* partition
, const char* partitionName
, bool isLightDump
, PartitionStatsDumper
* partitionStatsDumper
)
1319 PartitionBucketMemoryStats bucketStats
[kGenericNumBuckets
];
1320 static const size_t kMaxReportableDirectMaps
= 4096;
1321 uint32_t directMapLengths
[kMaxReportableDirectMaps
];
1322 size_t numDirectMappedAllocations
= 0;
1324 spinLockLock(&partition
->lock
);
1326 for (size_t i
= 0; i
< kGenericNumBuckets
; ++i
) {
1327 const PartitionBucket
* bucket
= &partition
->buckets
[i
];
1328 // Don't report the pseudo buckets that the generic allocator sets up in
1329 // order to preserve a fast size->bucket map (see
1330 // partitionAllocGenericInit for details).
1331 if (!bucket
->activePagesHead
)
1332 bucketStats
[i
].isValid
= false;
1334 partitionDumpBucketStats(&bucketStats
[i
], bucket
);
1337 for (PartitionDirectMapExtent
* extent
= partition
->directMapList
; extent
; extent
= extent
->nextExtent
) {
1338 ASSERT(!extent
->nextExtent
|| extent
->nextExtent
->prevExtent
== extent
);
1339 directMapLengths
[numDirectMappedAllocations
] = extent
->bucket
->slotSize
;
1340 ++numDirectMappedAllocations
;
1341 if (numDirectMappedAllocations
== kMaxReportableDirectMaps
)
1345 spinLockUnlock(&partition
->lock
);
1347 // partitionsDumpBucketStats is called after collecting stats because it
1348 // can try to allocate using PartitionAllocGeneric and it can't obtain the
1350 PartitionMemoryStats partitionStats
= { 0 };
1351 partitionStats
.totalMmappedBytes
= partition
->totalSizeOfSuperPages
+ partition
->totalSizeOfDirectMappedPages
;
1352 partitionStats
.totalCommittedBytes
= partition
->totalSizeOfCommittedPages
;
1353 for (size_t i
= 0; i
< kGenericNumBuckets
; ++i
) {
1354 if (bucketStats
[i
].isValid
) {
1355 partitionStats
.totalResidentBytes
+= bucketStats
[i
].residentBytes
;
1356 partitionStats
.totalActiveBytes
+= bucketStats
[i
].activeBytes
;
1357 partitionStats
.totalDecommittableBytes
+= bucketStats
[i
].decommittableBytes
;
1358 partitionStats
.totalDiscardableBytes
+= bucketStats
[i
].discardableBytes
;
1360 partitionStatsDumper
->partitionsDumpBucketStats(partitionName
, &bucketStats
[i
]);
1364 size_t directMappedAllocationsTotalSize
= 0;
1365 for (size_t i
= 0; i
< numDirectMappedAllocations
; ++i
) {
1366 PartitionBucketMemoryStats stats
;
1367 memset(&stats
, '\0', sizeof(stats
));
1368 stats
.isValid
= true;
1369 stats
.isDirectMap
= true;
1370 stats
.numFullPages
= 1;
1371 uint32_t size
= directMapLengths
[i
];
1372 stats
.allocatedPageSize
= size
;
1373 stats
.bucketSlotSize
= size
;
1374 stats
.activeBytes
= size
;
1375 stats
.residentBytes
= size
;
1376 directMappedAllocationsTotalSize
+= size
;
1377 partitionStatsDumper
->partitionsDumpBucketStats(partitionName
, &stats
);
1379 partitionStats
.totalResidentBytes
+= directMappedAllocationsTotalSize
;
1380 partitionStats
.totalActiveBytes
+= directMappedAllocationsTotalSize
;
1381 partitionStatsDumper
->partitionDumpTotals(partitionName
, &partitionStats
);
1384 void partitionDumpStats(PartitionRoot
* partition
, const char* partitionName
, bool isLightDump
, PartitionStatsDumper
* partitionStatsDumper
)
1386 static const size_t kMaxReportableBuckets
= 4096 / sizeof(void*);
1387 PartitionBucketMemoryStats memoryStats
[kMaxReportableBuckets
];
1388 const size_t partitionNumBuckets
= partition
->numBuckets
;
1389 ASSERT(partitionNumBuckets
<= kMaxReportableBuckets
);
1391 for (size_t i
= 0; i
< partitionNumBuckets
; ++i
)
1392 partitionDumpBucketStats(&memoryStats
[i
], &partition
->buckets()[i
]);
1394 // partitionsDumpBucketStats is called after collecting stats because it
1395 // can use PartitionAlloc to allocate and this can affect the statistics.
1396 PartitionMemoryStats partitionStats
= { 0 };
1397 partitionStats
.totalMmappedBytes
= partition
->totalSizeOfSuperPages
;
1398 partitionStats
.totalCommittedBytes
= partition
->totalSizeOfCommittedPages
;
1399 ASSERT(!partition
->totalSizeOfDirectMappedPages
);
1400 for (size_t i
= 0; i
< partitionNumBuckets
; ++i
) {
1401 if (memoryStats
[i
].isValid
) {
1402 partitionStats
.totalResidentBytes
+= memoryStats
[i
].residentBytes
;
1403 partitionStats
.totalActiveBytes
+= memoryStats
[i
].activeBytes
;
1404 partitionStats
.totalDecommittableBytes
+= memoryStats
[i
].decommittableBytes
;
1405 partitionStats
.totalDiscardableBytes
+= memoryStats
[i
].discardableBytes
;
1407 partitionStatsDumper
->partitionsDumpBucketStats(partitionName
, &memoryStats
[i
]);
1410 partitionStatsDumper
->partitionDumpTotals(partitionName
, &partitionStats
);