| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2013 Google Inc. All rights reserved. | 2 * Copyright (C) 2013 Google Inc. All rights reserved. |
| 3 * | 3 * |
| 4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
| 5 * modification, are permitted provided that the following conditions are | 5 * modification, are permitted provided that the following conditions are |
| 6 * met: | 6 * met: |
| 7 * | 7 * |
| 8 * * Redistributions of source code must retain the above copyright | 8 * * Redistributions of source code must retain the above copyright |
| 9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
| 10 * * Redistributions in binary form must reproduce the above | 10 * * Redistributions in binary form must reproduce the above |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 56 namespace WTF { | 56 namespace WTF { |
| 57 | 57 |
| 58 int PartitionRootBase::gInitializedLock = 0; | 58 int PartitionRootBase::gInitializedLock = 0; |
| 59 bool PartitionRootBase::gInitialized = false; | 59 bool PartitionRootBase::gInitialized = false; |
| 60 PartitionPage PartitionRootBase::gSeedPage; | 60 PartitionPage PartitionRootBase::gSeedPage; |
| 61 PartitionBucket PartitionRootBase::gPagedBucket; | 61 PartitionBucket PartitionRootBase::gPagedBucket; |
| 62 void (*PartitionRootBase::gOomHandlingFunction)() = nullptr; | 62 void (*PartitionRootBase::gOomHandlingFunction)() = nullptr; |
| 63 PartitionAllocHooks::AllocationHook* PartitionAllocHooks::m_allocationHook = nul
lptr; | 63 PartitionAllocHooks::AllocationHook* PartitionAllocHooks::m_allocationHook = nul
lptr; |
| 64 PartitionAllocHooks::FreeHook* PartitionAllocHooks::m_freeHook = nullptr; | 64 PartitionAllocHooks::FreeHook* PartitionAllocHooks::m_freeHook = nullptr; |
| 65 | 65 |
| 66 static uint16_t partitionBucketNumSystemPages(size_t size) | 66 static uint16_t partitionBucketNumSystemPages(size_t size) { |
| 67 { | 67 // This works out reasonably for the current bucket sizes of the generic |
| 68 // This works out reasonably for the current bucket sizes of the generic | 68 // allocator, and the current values of partition page size and constants. |
| 69 // allocator, and the current values of partition page size and constants. | 69 // Specifically, we have enough room to always pack the slots perfectly into |
| 70 // Specifically, we have enough room to always pack the slots perfectly into | 70 // some number of system pages. The only waste is the waste associated with |
| 71 // some number of system pages. The only waste is the waste associated with | 71 // unfaulted pages (i.e. wasted address space). |
| 72 // unfaulted pages (i.e. wasted address space). | 72 // TODO: we end up using a lot of system pages for very small sizes. For |
| 73 // TODO: we end up using a lot of system pages for very small sizes. For | 73 // example, we'll use 12 system pages for slot size 24. The slot size is |
| 74 // example, we'll use 12 system pages for slot size 24. The slot size is | 74 // so small that the waste would be tiny with just 4, or 1, system pages. |
| 75 // so small that the waste would be tiny with just 4, or 1, system pages. | 75 // Later, we can investigate whether there are anti-fragmentation benefits |
| 76 // Later, we can investigate whether there are anti-fragmentation benefits | 76 // to using fewer system pages. |
| 77 // to using fewer system pages. | 77 double bestWasteRatio = 1.0f; |
| 78 double bestWasteRatio = 1.0f; | 78 uint16_t bestPages = 0; |
| 79 uint16_t bestPages = 0; | 79 if (size > kMaxSystemPagesPerSlotSpan * kSystemPageSize) { |
| 80 if (size > kMaxSystemPagesPerSlotSpan * kSystemPageSize) { | 80 ASSERT(!(size % kSystemPageSize)); |
| 81 ASSERT(!(size % kSystemPageSize)); | 81 return static_cast<uint16_t>(size / kSystemPageSize); |
| 82 return static_cast<uint16_t>(size / kSystemPageSize); | 82 } |
| 83 } | 83 ASSERT(size <= kMaxSystemPagesPerSlotSpan * kSystemPageSize); |
| 84 ASSERT(size <= kMaxSystemPagesPerSlotSpan * kSystemPageSize); | 84 for (uint16_t i = kNumSystemPagesPerPartitionPage - 1; i <= kMaxSystemPagesPer
SlotSpan; ++i) { |
| 85 for (uint16_t i = kNumSystemPagesPerPartitionPage - 1; i <= kMaxSystemPagesP
erSlotSpan; ++i) { | 85 size_t pageSize = kSystemPageSize * i; |
| 86 size_t pageSize = kSystemPageSize * i; | 86 size_t numSlots = pageSize / size; |
| 87 size_t numSlots = pageSize / size; | 87 size_t waste = pageSize - (numSlots * size); |
| 88 size_t waste = pageSize - (numSlots * size); | 88 // Leaving a page unfaulted is not free; the page will occupy an empty page
table entry. |
| 89 // Leaving a page unfaulted is not free; the page will occupy an empty p
age table entry. | 89 // Make a simple attempt to account for that. |
| 90 // Make a simple attempt to account for that. | 90 size_t numRemainderPages = i & (kNumSystemPagesPerPartitionPage - 1); |
| 91 size_t numRemainderPages = i & (kNumSystemPagesPerPartitionPage - 1); | 91 size_t numUnfaultedPages = numRemainderPages ? (kNumSystemPagesPerPartitionP
age - numRemainderPages) : 0; |
| 92 size_t numUnfaultedPages = numRemainderPages ? (kNumSystemPagesPerPartit
ionPage - numRemainderPages) : 0; | 92 waste += sizeof(void*) * numUnfaultedPages; |
| 93 waste += sizeof(void*) * numUnfaultedPages; | 93 double wasteRatio = (double)waste / (double)pageSize; |
| 94 double wasteRatio = (double) waste / (double) pageSize; | 94 if (wasteRatio < bestWasteRatio) { |
| 95 if (wasteRatio < bestWasteRatio) { | 95 bestWasteRatio = wasteRatio; |
| 96 bestWasteRatio = wasteRatio; | 96 bestPages = i; |
| 97 bestPages = i; | 97 } |
| 98 } | 98 } |
| 99 } | 99 ASSERT(bestPages > 0); |
| 100 ASSERT(bestPages > 0); | 100 return bestPages; |
| 101 return bestPages; | 101 } |
| 102 } | 102 |
| 103 | 103 static void partitionAllocBaseInit(PartitionRootBase* root) { |
| 104 static void partitionAllocBaseInit(PartitionRootBase* root) | 104 ASSERT(!root->initialized); |
| 105 { | 105 |
| 106 ASSERT(!root->initialized); | 106 spinLockLock(&PartitionRootBase::gInitializedLock); |
| 107 | 107 if (!PartitionRootBase::gInitialized) { |
| 108 spinLockLock(&PartitionRootBase::gInitializedLock); | 108 PartitionRootBase::gInitialized = true; |
| 109 if (!PartitionRootBase::gInitialized) { | 109 // We mark the seed page as free to make sure it is skipped by our |
| 110 PartitionRootBase::gInitialized = true; | 110 // logic to find a new active page. |
| 111 // We mark the seed page as free to make sure it is skipped by our | 111 PartitionRootBase::gPagedBucket.activePagesHead = &PartitionRootGeneric::gSe
edPage; |
| 112 // logic to find a new active page. | 112 } |
| 113 PartitionRootBase::gPagedBucket.activePagesHead = &PartitionRootGeneric:
:gSeedPage; | 113 spinLockUnlock(&PartitionRootBase::gInitializedLock); |
| 114 } | 114 |
| 115 spinLockUnlock(&PartitionRootBase::gInitializedLock); | 115 root->initialized = true; |
| 116 | 116 root->totalSizeOfCommittedPages = 0; |
| 117 root->initialized = true; | 117 root->totalSizeOfSuperPages = 0; |
| 118 root->totalSizeOfCommittedPages = 0; | 118 root->totalSizeOfDirectMappedPages = 0; |
| 119 root->totalSizeOfSuperPages = 0; | 119 root->nextSuperPage = 0; |
| 120 root->totalSizeOfDirectMappedPages = 0; | 120 root->nextPartitionPage = 0; |
| 121 root->nextSuperPage = 0; | 121 root->nextPartitionPageEnd = 0; |
| 122 root->nextPartitionPage = 0; | 122 root->firstExtent = 0; |
| 123 root->nextPartitionPageEnd = 0; | 123 root->currentExtent = 0; |
| 124 root->firstExtent = 0; | 124 root->directMapList = 0; |
| 125 root->currentExtent = 0; | 125 |
| 126 root->directMapList = 0; | 126 memset(&root->globalEmptyPageRing, '\0', sizeof(root->globalEmptyPageRing)); |
| 127 | 127 root->globalEmptyPageRingIndex = 0; |
| 128 memset(&root->globalEmptyPageRing, '\0', sizeof(root->globalEmptyPageRing)); | 128 |
| 129 root->globalEmptyPageRingIndex = 0; | 129 // This is a "magic" value so we can test if a root pointer is valid. |
| 130 | 130 root->invertedSelf = ~reinterpret_cast<uintptr_t>(root); |
| 131 // This is a "magic" value so we can test if a root pointer is valid. | 131 } |
| 132 root->invertedSelf = ~reinterpret_cast<uintptr_t>(root); | 132 |
| 133 } | 133 static void partitionBucketInitBase(PartitionBucket* bucket, PartitionRootBase*
root) { |
| 134 | 134 bucket->activePagesHead = &PartitionRootGeneric::gSeedPage; |
| 135 static void partitionBucketInitBase(PartitionBucket* bucket, PartitionRootBase*
root) | 135 bucket->emptyPagesHead = 0; |
| 136 { | 136 bucket->decommittedPagesHead = 0; |
| 137 bucket->activePagesHead = &PartitionRootGeneric::gSeedPage; | 137 bucket->numFullPages = 0; |
| 138 bucket->emptyPagesHead = 0; | 138 bucket->numSystemPagesPerSlotSpan = partitionBucketNumSystemPages(bucket->slot
Size); |
| 139 bucket->decommittedPagesHead = 0; | 139 } |
| 140 bucket->numFullPages = 0; | 140 |
| 141 bucket->numSystemPagesPerSlotSpan = partitionBucketNumSystemPages(bucket->sl
otSize); | 141 void partitionAllocGlobalInit(void (*oomHandlingFunction)()) { |
| 142 } | 142 ASSERT(oomHandlingFunction); |
| 143 | 143 PartitionRootBase::gOomHandlingFunction = oomHandlingFunction; |
| 144 void partitionAllocGlobalInit(void (*oomHandlingFunction)()) | 144 } |
| 145 { | 145 |
| 146 ASSERT(oomHandlingFunction); | 146 void partitionAllocInit(PartitionRoot* root, size_t numBuckets, size_t maxAlloca
tion) { |
| 147 PartitionRootBase::gOomHandlingFunction = oomHandlingFunction; | 147 partitionAllocBaseInit(root); |
| 148 } | 148 |
| 149 | 149 root->numBuckets = numBuckets; |
| 150 void partitionAllocInit(PartitionRoot* root, size_t numBuckets, size_t maxAlloca
tion) | 150 root->maxAllocation = maxAllocation; |
| 151 { | 151 size_t i; |
| 152 partitionAllocBaseInit(root); | 152 for (i = 0; i < root->numBuckets; ++i) { |
| 153 | 153 PartitionBucket* bucket = &root->buckets()[i]; |
| 154 root->numBuckets = numBuckets; | 154 if (!i) |
| 155 root->maxAllocation = maxAllocation; | 155 bucket->slotSize = kAllocationGranularity; |
| 156 size_t i; | 156 else |
| 157 for (i = 0; i < root->numBuckets; ++i) { | 157 bucket->slotSize = i << kBucketShift; |
| 158 PartitionBucket* bucket = &root->buckets()[i]; | 158 partitionBucketInitBase(bucket, root); |
| 159 if (!i) | 159 } |
| 160 bucket->slotSize = kAllocationGranularity; | 160 } |
| 161 else | 161 |
| 162 bucket->slotSize = i << kBucketShift; | 162 void partitionAllocGenericInit(PartitionRootGeneric* root) { |
| 163 partitionBucketInitBase(bucket, root); | 163 partitionAllocBaseInit(root); |
| 164 } | 164 |
| 165 } | 165 root->lock = 0; |
| 166 | 166 |
| 167 void partitionAllocGenericInit(PartitionRootGeneric* root) | 167 // Precalculate some shift and mask constants used in the hot path. |
| 168 { | 168 // Example: malloc(41) == 101001 binary. |
| 169 partitionAllocBaseInit(root); | 169 // Order is 6 (1 << 6-1)==32 is highest bit set. |
| 170 | 170 // orderIndex is the next three MSB == 010 == 2. |
| 171 root->lock = 0; | 171 // subOrderIndexMask is a mask for the remaining bits == 11 (masking to 01 for
the subOrderIndex). |
| 172 | 172 size_t order; |
| 173 // Precalculate some shift and mask constants used in the hot path. | 173 for (order = 0; order <= kBitsPerSizet; ++order) { |
| 174 // Example: malloc(41) == 101001 binary. | 174 size_t orderIndexShift; |
| 175 // Order is 6 (1 << 6-1)==32 is highest bit set. | 175 if (order < kGenericNumBucketsPerOrderBits + 1) |
| 176 // orderIndex is the next three MSB == 010 == 2. | 176 orderIndexShift = 0; |
| 177 // subOrderIndexMask is a mask for the remaining bits == 11 (masking to 01 f
or the subOrderIndex). | 177 else |
| 178 size_t order; | 178 orderIndexShift = order - (kGenericNumBucketsPerOrderBits + 1); |
| 179 for (order = 0; order <= kBitsPerSizet; ++order) { | 179 root->orderIndexShifts[order] = orderIndexShift; |
| 180 size_t orderIndexShift; | 180 size_t subOrderIndexMask; |
| 181 if (order < kGenericNumBucketsPerOrderBits + 1) | 181 if (order == kBitsPerSizet) { |
| 182 orderIndexShift = 0; | 182 // This avoids invoking undefined behavior for an excessive shift. |
| 183 else | 183 subOrderIndexMask = static_cast<size_t>(-1) >> (kGenericNumBucketsPerOrder
Bits + 1); |
| 184 orderIndexShift = order - (kGenericNumBucketsPerOrderBits + 1); | 184 } else { |
| 185 root->orderIndexShifts[order] = orderIndexShift; | 185 subOrderIndexMask = ((static_cast<size_t>(1) << order) - 1) >> (kGenericNu
mBucketsPerOrderBits + 1); |
| 186 size_t subOrderIndexMask; | 186 } |
| 187 if (order == kBitsPerSizet) { | 187 root->orderSubIndexMasks[order] = subOrderIndexMask; |
| 188 // This avoids invoking undefined behavior for an excessive shift. | 188 } |
| 189 subOrderIndexMask = static_cast<size_t>(-1) >> (kGenericNumBucketsPe
rOrderBits + 1); | 189 |
| 190 } else { | 190 // Set up the actual usable buckets first. |
| 191 subOrderIndexMask = ((static_cast<size_t>(1) << order) - 1) >> (kGen
ericNumBucketsPerOrderBits + 1); | 191 // Note that typical values (i.e. min allocation size of 8) will result in |
| 192 } | 192 // pseudo buckets (size==9 etc. or more generally, size is not a multiple |
| 193 root->orderSubIndexMasks[order] = subOrderIndexMask; | 193 // of the smallest allocation granularity). |
| 194 } | 194 // We avoid them in the bucket lookup map, but we tolerate them to keep the |
| 195 | 195 // code simpler and the structures more generic. |
| 196 // Set up the actual usable buckets first. | 196 size_t i, j; |
| 197 // Note that typical values (i.e. min allocation size of 8) will result in | 197 size_t currentSize = kGenericSmallestBucket; |
| 198 // pseudo buckets (size==9 etc. or more generally, size is not a multiple | 198 size_t currentIncrement = kGenericSmallestBucket >> kGenericNumBucketsPerOrder
Bits; |
| 199 // of the smallest allocation granularity). | 199 PartitionBucket* bucket = &root->buckets[0]; |
| 200 // We avoid them in the bucket lookup map, but we tolerate them to keep the | 200 for (i = 0; i < kGenericNumBucketedOrders; ++i) { |
| 201 // code simpler and the structures more generic. | 201 for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { |
| 202 size_t i, j; | 202 bucket->slotSize = currentSize; |
| 203 size_t currentSize = kGenericSmallestBucket; | 203 partitionBucketInitBase(bucket, root); |
| 204 size_t currentIncrement = kGenericSmallestBucket >> kGenericNumBucketsPerOrd
erBits; | 204 // Disable psuedo buckets so that touching them faults. |
| 205 PartitionBucket* bucket = &root->buckets[0]; | 205 if (currentSize % kGenericSmallestBucket) |
| 206 for (i = 0; i < kGenericNumBucketedOrders; ++i) { | 206 bucket->activePagesHead = 0; |
| 207 for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { | 207 currentSize += currentIncrement; |
| 208 bucket->slotSize = currentSize; | 208 ++bucket; |
| 209 partitionBucketInitBase(bucket, root); | 209 } |
| 210 // Disable psuedo buckets so that touching them faults. | 210 currentIncrement <<= 1; |
| 211 if (currentSize % kGenericSmallestBucket) | 211 } |
| 212 bucket->activePagesHead = 0; | 212 ASSERT(currentSize == 1 << kGenericMaxBucketedOrder); |
| 213 currentSize += currentIncrement; | 213 ASSERT(bucket == &root->buckets[0] + kGenericNumBuckets); |
| 214 ++bucket; | 214 |
| 215 } | 215 // Then set up the fast size -> bucket lookup table. |
| 216 currentIncrement <<= 1; | 216 bucket = &root->buckets[0]; |
| 217 } | 217 PartitionBucket** bucketPtr = &root->bucketLookups[0]; |
| 218 ASSERT(currentSize == 1 << kGenericMaxBucketedOrder); | 218 for (order = 0; order <= kBitsPerSizet; ++order) { |
| 219 ASSERT(bucket == &root->buckets[0] + kGenericNumBuckets); | 219 for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { |
| 220 | 220 if (order < kGenericMinBucketedOrder) { |
| 221 // Then set up the fast size -> bucket lookup table. | 221 // Use the bucket of the finest granularity for malloc(0) etc. |
| 222 bucket = &root->buckets[0]; | 222 *bucketPtr++ = &root->buckets[0]; |
| 223 PartitionBucket** bucketPtr = &root->bucketLookups[0]; | 223 } else if (order > kGenericMaxBucketedOrder) { |
| 224 for (order = 0; order <= kBitsPerSizet; ++order) { | 224 *bucketPtr++ = &PartitionRootGeneric::gPagedBucket; |
| 225 for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { | 225 } else { |
| 226 if (order < kGenericMinBucketedOrder) { | 226 PartitionBucket* validBucket = bucket; |
| 227 // Use the bucket of the finest granularity for malloc(0) etc. | 227 // Skip over invalid buckets. |
| 228 *bucketPtr++ = &root->buckets[0]; | 228 while (validBucket->slotSize % kGenericSmallestBucket) |
| 229 } else if (order > kGenericMaxBucketedOrder) { | 229 validBucket++; |
| 230 *bucketPtr++ = &PartitionRootGeneric::gPagedBucket; | 230 *bucketPtr++ = validBucket; |
| 231 } else { | 231 bucket++; |
| 232 PartitionBucket* validBucket = bucket; | 232 } |
| 233 // Skip over invalid buckets. | 233 } |
| 234 while (validBucket->slotSize % kGenericSmallestBucket) | 234 } |
| 235 validBucket++; | 235 ASSERT(bucket == &root->buckets[0] + kGenericNumBuckets); |
| 236 *bucketPtr++ = validBucket; | 236 ASSERT(bucketPtr == &root->bucketLookups[0] + ((kBitsPerSizet + 1) * kGenericN
umBucketsPerOrder)); |
| 237 bucket++; | 237 // And there's one last bucket lookup that will be hit for e.g. malloc(-1), |
| 238 } | 238 // which tries to overflow to a non-existant order. |
| 239 } | 239 *bucketPtr = &PartitionRootGeneric::gPagedBucket; |
| 240 } | 240 } |
| 241 ASSERT(bucket == &root->buckets[0] + kGenericNumBuckets); | 241 |
| 242 ASSERT(bucketPtr == &root->bucketLookups[0] + ((kBitsPerSizet + 1) * kGeneri
cNumBucketsPerOrder)); | 242 static bool partitionAllocShutdownBucket(PartitionBucket* bucket) { |
| 243 // And there's one last bucket lookup that will be hit for e.g. malloc(-1), | 243 // Failure here indicates a memory leak. |
| 244 // which tries to overflow to a non-existant order. | 244 bool foundLeak = bucket->numFullPages; |
| 245 *bucketPtr = &PartitionRootGeneric::gPagedBucket; | 245 for (PartitionPage* page = bucket->activePagesHead; page; page = page->nextPag
e) |
| 246 } | 246 foundLeak |= (page->numAllocatedSlots > 0); |
| 247 | 247 return foundLeak; |
| 248 static bool partitionAllocShutdownBucket(PartitionBucket* bucket) | 248 } |
| 249 { | 249 |
| 250 // Failure here indicates a memory leak. | 250 static bool partitionAllocBaseShutdown(PartitionRootBase* root) { |
| 251 bool foundLeak = bucket->numFullPages; | 251 ASSERT(root->initialized); |
| 252 for (PartitionPage* page = bucket->activePagesHead; page; page = page->nextP
age) | 252 root->initialized = false; |
| 253 foundLeak |= (page->numAllocatedSlots > 0); | 253 |
| 254 return foundLeak; | 254 // Now that we've examined all partition pages in all buckets, it's safe |
| 255 } | 255 // to free all our super pages. Since the super page extent entries are |
| 256 | 256 // stored in the super pages, we need to be careful not to access them |
| 257 static bool partitionAllocBaseShutdown(PartitionRootBase* root) | 257 // after we've released the corresponding super page. |
| 258 { | 258 PartitionSuperPageExtentEntry* entry = root->firstExtent; |
| 259 ASSERT(root->initialized); | 259 while (entry) { |
| 260 root->initialized = false; | 260 PartitionSuperPageExtentEntry* nextEntry = entry->next; |
| 261 | 261 char* superPage = entry->superPageBase; |
| 262 // Now that we've examined all partition pages in all buckets, it's safe | 262 char* superPagesEnd = entry->superPagesEnd; |
| 263 // to free all our super pages. Since the super page extent entries are | 263 while (superPage < superPagesEnd) { |
| 264 // stored in the super pages, we need to be careful not to access them | 264 freePages(superPage, kSuperPageSize); |
| 265 // after we've released the corresponding super page. | 265 superPage += kSuperPageSize; |
| 266 PartitionSuperPageExtentEntry* entry = root->firstExtent; | 266 } |
| 267 while (entry) { | 267 entry = nextEntry; |
| 268 PartitionSuperPageExtentEntry* nextEntry = entry->next; | 268 } |
| 269 char* superPage = entry->superPageBase; | 269 return root->directMapList; |
| 270 char* superPagesEnd = entry->superPagesEnd; | 270 } |
| 271 while (superPage < superPagesEnd) { | 271 |
| 272 freePages(superPage, kSuperPageSize); | 272 bool partitionAllocShutdown(PartitionRoot* root) { |
| 273 superPage += kSuperPageSize; | 273 bool foundLeak = false; |
| 274 } | 274 size_t i; |
| 275 entry = nextEntry; | 275 for (i = 0; i < root->numBuckets; ++i) { |
| 276 } | 276 PartitionBucket* bucket = &root->buckets()[i]; |
| 277 return root->directMapList; | 277 foundLeak |= partitionAllocShutdownBucket(bucket); |
| 278 } | 278 } |
| 279 | 279 foundLeak |= partitionAllocBaseShutdown(root); |
| 280 bool partitionAllocShutdown(PartitionRoot* root) | 280 return !foundLeak; |
| 281 { | 281 } |
| 282 bool foundLeak = false; | 282 |
| 283 size_t i; | 283 bool partitionAllocGenericShutdown(PartitionRootGeneric* root) { |
| 284 for (i = 0; i < root->numBuckets; ++i) { | 284 bool foundLeak = false; |
| 285 PartitionBucket* bucket = &root->buckets()[i]; | 285 size_t i; |
| 286 foundLeak |= partitionAllocShutdownBucket(bucket); | 286 for (i = 0; i < kGenericNumBuckets; ++i) { |
| 287 } | 287 PartitionBucket* bucket = &root->buckets[i]; |
| 288 foundLeak |= partitionAllocBaseShutdown(root); | 288 foundLeak |= partitionAllocShutdownBucket(bucket); |
| 289 return !foundLeak; | 289 } |
| 290 } | 290 foundLeak |= partitionAllocBaseShutdown(root); |
| 291 | 291 return !foundLeak; |
| 292 bool partitionAllocGenericShutdown(PartitionRootGeneric* root) | |
| 293 { | |
| 294 bool foundLeak = false; | |
| 295 size_t i; | |
| 296 for (i = 0; i < kGenericNumBuckets; ++i) { | |
| 297 PartitionBucket* bucket = &root->buckets[i]; | |
| 298 foundLeak |= partitionAllocShutdownBucket(bucket); | |
| 299 } | |
| 300 foundLeak |= partitionAllocBaseShutdown(root); | |
| 301 return !foundLeak; | |
| 302 } | 292 } |
| 303 | 293 |
| 304 #if !CPU(64BIT) | 294 #if !CPU(64BIT) |
| 305 static NEVER_INLINE void partitionOutOfMemoryWithLotsOfUncommitedPages() | 295 static NEVER_INLINE void partitionOutOfMemoryWithLotsOfUncommitedPages() { |
| 306 { | 296 IMMEDIATE_CRASH(); |
| 307 IMMEDIATE_CRASH(); | |
| 308 } | 297 } |
| 309 #endif | 298 #endif |
| 310 | 299 |
| 311 static NEVER_INLINE void partitionOutOfMemory(const PartitionRootBase* root) | 300 static NEVER_INLINE void partitionOutOfMemory(const PartitionRootBase* root) { |
| 312 { | |
| 313 #if !CPU(64BIT) | 301 #if !CPU(64BIT) |
| 314 // Check whether this OOM is due to a lot of super pages that are allocated | 302 // Check whether this OOM is due to a lot of super pages that are allocated |
| 315 // but not committed, probably due to http://crbug.com/421387. | 303 // but not committed, probably due to http://crbug.com/421387. |
| 316 if (root->totalSizeOfSuperPages + root->totalSizeOfDirectMappedPages - root-
>totalSizeOfCommittedPages > kReasonableSizeOfUnusedPages) { | 304 if (root->totalSizeOfSuperPages + root->totalSizeOfDirectMappedPages - root->t
otalSizeOfCommittedPages > kReasonableSizeOfUnusedPages) { |
| 317 partitionOutOfMemoryWithLotsOfUncommitedPages(); | 305 partitionOutOfMemoryWithLotsOfUncommitedPages(); |
| 318 } | 306 } |
| 319 #endif | 307 #endif |
| 320 if (PartitionRootBase::gOomHandlingFunction) | 308 if (PartitionRootBase::gOomHandlingFunction) |
| 321 (*PartitionRootBase::gOomHandlingFunction)(); | 309 (*PartitionRootBase::gOomHandlingFunction)(); |
| 322 IMMEDIATE_CRASH(); | 310 IMMEDIATE_CRASH(); |
| 323 } | 311 } |
| 324 | 312 |
| 325 static NEVER_INLINE void partitionExcessiveAllocationSize() | 313 static NEVER_INLINE void partitionExcessiveAllocationSize() { |
| 326 { | 314 IMMEDIATE_CRASH(); |
| 327 IMMEDIATE_CRASH(); | 315 } |
| 328 } | 316 |
| 329 | 317 static NEVER_INLINE void partitionBucketFull() { |
| 330 static NEVER_INLINE void partitionBucketFull() | 318 IMMEDIATE_CRASH(); |
| 331 { | |
| 332 IMMEDIATE_CRASH(); | |
| 333 } | 319 } |
| 334 | 320 |
| 335 // partitionPageStateIs* | 321 // partitionPageStateIs* |
| 336 // Note that it's only valid to call these functions on pages found on one of | 322 // Note that it's only valid to call these functions on pages found on one of |
| 337 // the page lists. Specifically, you can't call these functions on full pages | 323 // the page lists. Specifically, you can't call these functions on full pages |
| 338 // that were detached from the active list. | 324 // that were detached from the active list. |
| 339 static bool ALWAYS_INLINE partitionPageStateIsActive(const PartitionPage* page) | 325 static bool ALWAYS_INLINE partitionPageStateIsActive(const PartitionPage* page)
{ |
| 340 { | 326 ASSERT(page != &PartitionRootGeneric::gSeedPage); |
| 341 ASSERT(page != &PartitionRootGeneric::gSeedPage); | 327 ASSERT(!page->pageOffset); |
| 342 ASSERT(!page->pageOffset); | 328 return (page->numAllocatedSlots > 0 && (page->freelistHead || page->numUnprovi
sionedSlots)); |
| 343 return (page->numAllocatedSlots > 0 && (page->freelistHead || page->numUnpro
visionedSlots)); | 329 } |
| 344 } | 330 |
| 345 | 331 static bool ALWAYS_INLINE partitionPageStateIsFull(const PartitionPage* page) { |
| 346 static bool ALWAYS_INLINE partitionPageStateIsFull(const PartitionPage* page) | 332 ASSERT(page != &PartitionRootGeneric::gSeedPage); |
| 347 { | 333 ASSERT(!page->pageOffset); |
| 348 ASSERT(page != &PartitionRootGeneric::gSeedPage); | 334 bool ret = (page->numAllocatedSlots == partitionBucketSlots(page->bucket)); |
| 349 ASSERT(!page->pageOffset); | 335 if (ret) { |
| 350 bool ret = (page->numAllocatedSlots == partitionBucketSlots(page->bucket)); | 336 ASSERT(!page->freelistHead); |
| 351 if (ret) { | 337 ASSERT(!page->numUnprovisionedSlots); |
| 352 ASSERT(!page->freelistHead); | 338 } |
| 353 ASSERT(!page->numUnprovisionedSlots); | 339 return ret; |
| 354 } | 340 } |
| 341 |
| 342 static bool ALWAYS_INLINE partitionPageStateIsEmpty(const PartitionPage* page) { |
| 343 ASSERT(page != &PartitionRootGeneric::gSeedPage); |
| 344 ASSERT(!page->pageOffset); |
| 345 return (!page->numAllocatedSlots && page->freelistHead); |
| 346 } |
| 347 |
| 348 static bool ALWAYS_INLINE partitionPageStateIsDecommitted(const PartitionPage* p
age) { |
| 349 ASSERT(page != &PartitionRootGeneric::gSeedPage); |
| 350 ASSERT(!page->pageOffset); |
| 351 bool ret = (!page->numAllocatedSlots && !page->freelistHead); |
| 352 if (ret) { |
| 353 ASSERT(!page->numUnprovisionedSlots); |
| 354 ASSERT(page->emptyCacheIndex == -1); |
| 355 } |
| 356 return ret; |
| 357 } |
| 358 |
| 359 static void partitionIncreaseCommittedPages(PartitionRootBase* root, size_t len)
{ |
| 360 root->totalSizeOfCommittedPages += len; |
| 361 ASSERT(root->totalSizeOfCommittedPages <= root->totalSizeOfSuperPages + root->
totalSizeOfDirectMappedPages); |
| 362 } |
| 363 |
| 364 static void partitionDecreaseCommittedPages(PartitionRootBase* root, size_t len)
{ |
| 365 root->totalSizeOfCommittedPages -= len; |
| 366 ASSERT(root->totalSizeOfCommittedPages <= root->totalSizeOfSuperPages + root->
totalSizeOfDirectMappedPages); |
| 367 } |
| 368 |
| 369 static ALWAYS_INLINE void partitionDecommitSystemPages(PartitionRootBase* root,
void* addr, size_t len) { |
| 370 decommitSystemPages(addr, len); |
| 371 partitionDecreaseCommittedPages(root, len); |
| 372 } |
| 373 |
| 374 static ALWAYS_INLINE void partitionRecommitSystemPages(PartitionRootBase* root,
void* addr, size_t len) { |
| 375 recommitSystemPages(addr, len); |
| 376 partitionIncreaseCommittedPages(root, len); |
| 377 } |
| 378 |
| 379 static ALWAYS_INLINE void* partitionAllocPartitionPages(PartitionRootBase* root,
int flags, uint16_t numPartitionPages) { |
| 380 ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPage) % kPartitionPage
Size)); |
| 381 ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPageEnd) % kPartitionP
ageSize)); |
| 382 ASSERT(numPartitionPages <= kNumPartitionPagesPerSuperPage); |
| 383 size_t totalSize = kPartitionPageSize * numPartitionPages; |
| 384 size_t numPartitionPagesLeft = (root->nextPartitionPageEnd - root->nextPartiti
onPage) >> kPartitionPageShift; |
| 385 if (LIKELY(numPartitionPagesLeft >= numPartitionPages)) { |
| 386 // In this case, we can still hand out pages from the current super page |
| 387 // allocation. |
| 388 char* ret = root->nextPartitionPage; |
| 389 root->nextPartitionPage += totalSize; |
| 390 partitionIncreaseCommittedPages(root, totalSize); |
| 355 return ret; | 391 return ret; |
| 356 } | 392 } |
| 357 | 393 |
| 358 static bool ALWAYS_INLINE partitionPageStateIsEmpty(const PartitionPage* page) | 394 // Need a new super page. We want to allocate super pages in a continguous |
| 359 { | 395 // address region as much as possible. This is important for not causing |
| 360 ASSERT(page != &PartitionRootGeneric::gSeedPage); | 396 // page table bloat and not fragmenting address spaces in 32 bit architectures
. |
| 361 ASSERT(!page->pageOffset); | 397 char* requestedAddress = root->nextSuperPage; |
| 362 return (!page->numAllocatedSlots && page->freelistHead); | 398 char* superPage = reinterpret_cast<char*>(allocPages(requestedAddress, kSuperP
ageSize, kSuperPageSize, PageAccessible)); |
| 363 } | 399 if (UNLIKELY(!superPage)) |
| 364 | 400 return 0; |
| 365 static bool ALWAYS_INLINE partitionPageStateIsDecommitted(const PartitionPage* p
age) | 401 |
| 366 { | 402 root->totalSizeOfSuperPages += kSuperPageSize; |
| 367 ASSERT(page != &PartitionRootGeneric::gSeedPage); | 403 partitionIncreaseCommittedPages(root, totalSize); |
| 368 ASSERT(!page->pageOffset); | 404 |
| 369 bool ret = (!page->numAllocatedSlots && !page->freelistHead); | 405 root->nextSuperPage = superPage + kSuperPageSize; |
| 370 if (ret) { | 406 char* ret = superPage + kPartitionPageSize; |
| 371 ASSERT(!page->numUnprovisionedSlots); | 407 root->nextPartitionPage = ret + totalSize; |
| 372 ASSERT(page->emptyCacheIndex == -1); | 408 root->nextPartitionPageEnd = root->nextSuperPage - kPartitionPageSize; |
| 373 } | 409 // Make the first partition page in the super page a guard page, but leave a |
| 374 return ret; | 410 // hole in the middle. |
| 375 } | 411 // This is where we put page metadata and also a tiny amount of extent |
| 376 | 412 // metadata. |
| 377 static void partitionIncreaseCommittedPages(PartitionRootBase* root, size_t len) | 413 setSystemPagesInaccessible(superPage, kSystemPageSize); |
| 378 { | 414 setSystemPagesInaccessible(superPage + (kSystemPageSize * 2), kPartitionPageSi
ze - (kSystemPageSize * 2)); |
| 379 root->totalSizeOfCommittedPages += len; | 415 // Also make the last partition page a guard page. |
| 380 ASSERT(root->totalSizeOfCommittedPages <= root->totalSizeOfSuperPages + root
->totalSizeOfDirectMappedPages); | 416 setSystemPagesInaccessible(superPage + (kSuperPageSize - kPartitionPageSize),
kPartitionPageSize); |
| 381 } | 417 |
| 382 | 418 // If we were after a specific address, but didn't get it, assume that |
| 383 static void partitionDecreaseCommittedPages(PartitionRootBase* root, size_t len) | 419 // the system chose a lousy address. Here most OS'es have a default |
| 384 { | 420 // algorithm that isn't randomized. For example, most Linux |
| 385 root->totalSizeOfCommittedPages -= len; | 421 // distributions will allocate the mapping directly before the last |
| 386 ASSERT(root->totalSizeOfCommittedPages <= root->totalSizeOfSuperPages + root
->totalSizeOfDirectMappedPages); | 422 // successful mapping, which is far from random. So we just get fresh |
| 387 } | 423 // randomness for the next mapping attempt. |
| 388 | 424 if (requestedAddress && requestedAddress != superPage) |
| 389 static ALWAYS_INLINE void partitionDecommitSystemPages(PartitionRootBase* root,
void* addr, size_t len) | 425 root->nextSuperPage = 0; |
| 390 { | 426 |
| 391 decommitSystemPages(addr, len); | 427 // We allocated a new super page so update super page metadata. |
| 392 partitionDecreaseCommittedPages(root, len); | 428 // First check if this is a new extent or not. |
| 393 } | 429 PartitionSuperPageExtentEntry* latestExtent = reinterpret_cast<PartitionSuperP
ageExtentEntry*>(partitionSuperPageToMetadataArea(superPage)); |
| 394 | 430 // By storing the root in every extent metadata object, we have a fast way |
| 395 static ALWAYS_INLINE void partitionRecommitSystemPages(PartitionRootBase* root,
void* addr, size_t len) | 431 // to go from a pointer within the partition to the root object. |
| 396 { | 432 latestExtent->root = root; |
| 397 recommitSystemPages(addr, len); | 433 // Most new extents will be part of a larger extent, and these three fields |
| 398 partitionIncreaseCommittedPages(root, len); | 434 // are unused, but we initialize them to 0 so that we get a clear signal |
| 399 } | 435 // in case they are accidentally used. |
| 400 | 436 latestExtent->superPageBase = 0; |
| 401 static ALWAYS_INLINE void* partitionAllocPartitionPages(PartitionRootBase* root,
int flags, uint16_t numPartitionPages) | 437 latestExtent->superPagesEnd = 0; |
| 402 { | 438 latestExtent->next = 0; |
| 403 ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPage) % kPartitionPa
geSize)); | 439 |
| 404 ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPageEnd) % kPartitio
nPageSize)); | 440 PartitionSuperPageExtentEntry* currentExtent = root->currentExtent; |
| 405 ASSERT(numPartitionPages <= kNumPartitionPagesPerSuperPage); | 441 bool isNewExtent = (superPage != requestedAddress); |
| 406 size_t totalSize = kPartitionPageSize * numPartitionPages; | 442 if (UNLIKELY(isNewExtent)) { |
| 407 size_t numPartitionPagesLeft = (root->nextPartitionPageEnd - root->nextParti
tionPage) >> kPartitionPageShift; | 443 if (UNLIKELY(!currentExtent)) { |
| 408 if (LIKELY(numPartitionPagesLeft >= numPartitionPages)) { | 444 ASSERT(!root->firstExtent); |
| 409 // In this case, we can still hand out pages from the current super page | 445 root->firstExtent = latestExtent; |
| 410 // allocation. | |
| 411 char* ret = root->nextPartitionPage; | |
| 412 root->nextPartitionPage += totalSize; | |
| 413 partitionIncreaseCommittedPages(root, totalSize); | |
| 414 return ret; | |
| 415 } | |
| 416 | |
| 417 // Need a new super page. We want to allocate super pages in a continguous | |
| 418 // address region as much as possible. This is important for not causing | |
| 419 // page table bloat and not fragmenting address spaces in 32 bit architectur
es. | |
| 420 char* requestedAddress = root->nextSuperPage; | |
| 421 char* superPage = reinterpret_cast<char*>(allocPages(requestedAddress, kSupe
rPageSize, kSuperPageSize, PageAccessible)); | |
| 422 if (UNLIKELY(!superPage)) | |
| 423 return 0; | |
| 424 | |
| 425 root->totalSizeOfSuperPages += kSuperPageSize; | |
| 426 partitionIncreaseCommittedPages(root, totalSize); | |
| 427 | |
| 428 root->nextSuperPage = superPage + kSuperPageSize; | |
| 429 char* ret = superPage + kPartitionPageSize; | |
| 430 root->nextPartitionPage = ret + totalSize; | |
| 431 root->nextPartitionPageEnd = root->nextSuperPage - kPartitionPageSize; | |
| 432 // Make the first partition page in the super page a guard page, but leave a | |
| 433 // hole in the middle. | |
| 434 // This is where we put page metadata and also a tiny amount of extent | |
| 435 // metadata. | |
| 436 setSystemPagesInaccessible(superPage, kSystemPageSize); | |
| 437 setSystemPagesInaccessible(superPage + (kSystemPageSize * 2), kPartitionPage
Size - (kSystemPageSize * 2)); | |
| 438 // Also make the last partition page a guard page. | |
| 439 setSystemPagesInaccessible(superPage + (kSuperPageSize - kPartitionPageSize)
, kPartitionPageSize); | |
| 440 | |
| 441 // If we were after a specific address, but didn't get it, assume that | |
| 442 // the system chose a lousy address. Here most OS'es have a default | |
| 443 // algorithm that isn't randomized. For example, most Linux | |
| 444 // distributions will allocate the mapping directly before the last | |
| 445 // successful mapping, which is far from random. So we just get fresh | |
| 446 // randomness for the next mapping attempt. | |
| 447 if (requestedAddress && requestedAddress != superPage) | |
| 448 root->nextSuperPage = 0; | |
| 449 | |
| 450 // We allocated a new super page so update super page metadata. | |
| 451 // First check if this is a new extent or not. | |
| 452 PartitionSuperPageExtentEntry* latestExtent = reinterpret_cast<PartitionSupe
rPageExtentEntry*>(partitionSuperPageToMetadataArea(superPage)); | |
| 453 // By storing the root in every extent metadata object, we have a fast way | |
| 454 // to go from a pointer within the partition to the root object. | |
| 455 latestExtent->root = root; | |
| 456 // Most new extents will be part of a larger extent, and these three fields | |
| 457 // are unused, but we initialize them to 0 so that we get a clear signal | |
| 458 // in case they are accidentally used. | |
| 459 latestExtent->superPageBase = 0; | |
| 460 latestExtent->superPagesEnd = 0; | |
| 461 latestExtent->next = 0; | |
| 462 | |
| 463 PartitionSuperPageExtentEntry* currentExtent = root->currentExtent; | |
| 464 bool isNewExtent = (superPage != requestedAddress); | |
| 465 if (UNLIKELY(isNewExtent)) { | |
| 466 if (UNLIKELY(!currentExtent)) { | |
| 467 ASSERT(!root->firstExtent); | |
| 468 root->firstExtent = latestExtent; | |
| 469 } else { | |
| 470 ASSERT(currentExtent->superPageBase); | |
| 471 currentExtent->next = latestExtent; | |
| 472 } | |
| 473 root->currentExtent = latestExtent; | |
| 474 latestExtent->superPageBase = superPage; | |
| 475 latestExtent->superPagesEnd = superPage + kSuperPageSize; | |
| 476 } else { | 446 } else { |
| 477 // We allocated next to an existing extent so just nudge the size up a l
ittle. | 447 ASSERT(currentExtent->superPageBase); |
| 478 ASSERT(currentExtent->superPagesEnd); | 448 currentExtent->next = latestExtent; |
| 479 currentExtent->superPagesEnd += kSuperPageSize; | 449 } |
| 480 ASSERT(ret >= currentExtent->superPageBase && ret < currentExtent->super
PagesEnd); | 450 root->currentExtent = latestExtent; |
| 481 } | 451 latestExtent->superPageBase = superPage; |
| 482 return ret; | 452 latestExtent->superPagesEnd = superPage + kSuperPageSize; |
| 483 } | 453 } else { |
| 484 | 454 // We allocated next to an existing extent so just nudge the size up a littl
e. |
| 485 static ALWAYS_INLINE uint16_t partitionBucketPartitionPages(const PartitionBucke
t* bucket) | 455 ASSERT(currentExtent->superPagesEnd); |
| 486 { | 456 currentExtent->superPagesEnd += kSuperPageSize; |
| 487 return (bucket->numSystemPagesPerSlotSpan + (kNumSystemPagesPerPartitionPage
- 1)) / kNumSystemPagesPerPartitionPage; | 457 ASSERT(ret >= currentExtent->superPageBase && ret < currentExtent->superPage
sEnd); |
| 488 } | 458 } |
| 489 | 459 return ret; |
| 490 static ALWAYS_INLINE void partitionPageReset(PartitionPage* page) | 460 } |
| 491 { | 461 |
| 492 ASSERT(partitionPageStateIsDecommitted(page)); | 462 static ALWAYS_INLINE uint16_t partitionBucketPartitionPages(const PartitionBucke
t* bucket) { |
| 493 | 463 return (bucket->numSystemPagesPerSlotSpan + (kNumSystemPagesPerPartitionPage -
1)) / kNumSystemPagesPerPartitionPage; |
| 494 page->numUnprovisionedSlots = partitionBucketSlots(page->bucket); | 464 } |
| 495 ASSERT(page->numUnprovisionedSlots); | 465 |
| 496 | 466 static ALWAYS_INLINE void partitionPageReset(PartitionPage* page) { |
| 497 page->nextPage = nullptr; | 467 ASSERT(partitionPageStateIsDecommitted(page)); |
| 498 } | 468 |
| 499 | 469 page->numUnprovisionedSlots = partitionBucketSlots(page->bucket); |
| 500 static ALWAYS_INLINE void partitionPageSetup(PartitionPage* page, PartitionBucke
t* bucket) | 470 ASSERT(page->numUnprovisionedSlots); |
| 501 { | 471 |
| 502 // The bucket never changes. We set it up once. | 472 page->nextPage = nullptr; |
| 503 page->bucket = bucket; | 473 } |
| 504 page->emptyCacheIndex = -1; | 474 |
| 505 | 475 static ALWAYS_INLINE void partitionPageSetup(PartitionPage* page, PartitionBucke
t* bucket) { |
| 506 partitionPageReset(page); | 476 // The bucket never changes. We set it up once. |
| 507 | 477 page->bucket = bucket; |
| 508 // If this page has just a single slot, do not set up page offsets for any | 478 page->emptyCacheIndex = -1; |
| 509 // page metadata other than the first one. This ensures that attempts to | 479 |
| 510 // touch invalid page metadata fail. | 480 partitionPageReset(page); |
| 511 if (page->numUnprovisionedSlots == 1) | 481 |
| 512 return; | 482 // If this page has just a single slot, do not set up page offsets for any |
| 513 | 483 // page metadata other than the first one. This ensures that attempts to |
| 514 uint16_t numPartitionPages = partitionBucketPartitionPages(bucket); | 484 // touch invalid page metadata fail. |
| 515 char* pageCharPtr = reinterpret_cast<char*>(page); | 485 if (page->numUnprovisionedSlots == 1) |
| 516 for (uint16_t i = 1; i < numPartitionPages; ++i) { | 486 return; |
| 517 pageCharPtr += kPageMetadataSize; | 487 |
| 518 PartitionPage* secondaryPage = reinterpret_cast<PartitionPage*>(pageChar
Ptr); | 488 uint16_t numPartitionPages = partitionBucketPartitionPages(bucket); |
| 519 secondaryPage->pageOffset = i; | 489 char* pageCharPtr = reinterpret_cast<char*>(page); |
| 520 } | 490 for (uint16_t i = 1; i < numPartitionPages; ++i) { |
| 521 } | 491 pageCharPtr += kPageMetadataSize; |
| 522 | 492 PartitionPage* secondaryPage = reinterpret_cast<PartitionPage*>(pageCharPtr)
; |
| 523 static ALWAYS_INLINE size_t partitionRoundUpToSystemPage(size_t size) | 493 secondaryPage->pageOffset = i; |
| 524 { | 494 } |
| 525 return (size + kSystemPageOffsetMask) & kSystemPageBaseMask; | 495 } |
| 526 } | 496 |
| 527 | 497 static ALWAYS_INLINE size_t partitionRoundUpToSystemPage(size_t size) { |
| 528 static ALWAYS_INLINE size_t partitionRoundDownToSystemPage(size_t size) | 498 return (size + kSystemPageOffsetMask) & kSystemPageBaseMask; |
| 529 { | 499 } |
| 530 return size & kSystemPageBaseMask; | 500 |
| 531 } | 501 static ALWAYS_INLINE size_t partitionRoundDownToSystemPage(size_t size) { |
| 532 | 502 return size & kSystemPageBaseMask; |
| 533 static ALWAYS_INLINE char* partitionPageAllocAndFillFreelist(PartitionPage* page
) | 503 } |
| 534 { | 504 |
| 535 ASSERT(page != &PartitionRootGeneric::gSeedPage); | 505 static ALWAYS_INLINE char* partitionPageAllocAndFillFreelist(PartitionPage* page
) { |
| 536 uint16_t numSlots = page->numUnprovisionedSlots; | 506 ASSERT(page != &PartitionRootGeneric::gSeedPage); |
| 537 ASSERT(numSlots); | 507 uint16_t numSlots = page->numUnprovisionedSlots; |
| 538 PartitionBucket* bucket = page->bucket; | 508 ASSERT(numSlots); |
| 539 // We should only get here when _every_ slot is either used or unprovisioned
. | 509 PartitionBucket* bucket = page->bucket; |
| 540 // (The third state is "on the freelist". If we have a non-empty freelist, w
e should not get here.) | 510 // We should only get here when _every_ slot is either used or unprovisioned. |
| 541 ASSERT(numSlots + page->numAllocatedSlots == partitionBucketSlots(bucket)); | 511 // (The third state is "on the freelist". If we have a non-empty freelist, we
should not get here.) |
| 542 // Similarly, make explicitly sure that the freelist is empty. | 512 ASSERT(numSlots + page->numAllocatedSlots == partitionBucketSlots(bucket)); |
| 543 ASSERT(!page->freelistHead); | 513 // Similarly, make explicitly sure that the freelist is empty. |
| 544 ASSERT(page->numAllocatedSlots >= 0); | 514 ASSERT(!page->freelistHead); |
| 545 | 515 ASSERT(page->numAllocatedSlots >= 0); |
| 546 size_t size = bucket->slotSize; | 516 |
| 547 char* base = reinterpret_cast<char*>(partitionPageToPointer(page)); | 517 size_t size = bucket->slotSize; |
| 548 char* returnObject = base + (size * page->numAllocatedSlots); | 518 char* base = reinterpret_cast<char*>(partitionPageToPointer(page)); |
| 549 char* firstFreelistPointer = returnObject + size; | 519 char* returnObject = base + (size * page->numAllocatedSlots); |
| 550 char* firstFreelistPointerExtent = firstFreelistPointer + sizeof(PartitionFr
eelistEntry*); | 520 char* firstFreelistPointer = returnObject + size; |
| 551 // Our goal is to fault as few system pages as possible. We calculate the | 521 char* firstFreelistPointerExtent = firstFreelistPointer + sizeof(PartitionFree
listEntry*); |
| 552 // page containing the "end" of the returned slot, and then allow freelist | 522 // Our goal is to fault as few system pages as possible. We calculate the |
| 553 // pointers to be written up to the end of that page. | 523 // page containing the "end" of the returned slot, and then allow freelist |
| 554 char* subPageLimit = reinterpret_cast<char*>(partitionRoundUpToSystemPage(re
interpret_cast<size_t>(firstFreelistPointer))); | 524 // pointers to be written up to the end of that page. |
| 555 char* slotsLimit = returnObject + (size * numSlots); | 525 char* subPageLimit = reinterpret_cast<char*>(partitionRoundUpToSystemPage(rein
terpret_cast<size_t>(firstFreelistPointer))); |
| 556 char* freelistLimit = subPageLimit; | 526 char* slotsLimit = returnObject + (size * numSlots); |
| 557 if (UNLIKELY(slotsLimit < freelistLimit)) | 527 char* freelistLimit = subPageLimit; |
| 558 freelistLimit = slotsLimit; | 528 if (UNLIKELY(slotsLimit < freelistLimit)) |
| 559 | 529 freelistLimit = slotsLimit; |
| 560 uint16_t numNewFreelistEntries = 0; | 530 |
| 561 if (LIKELY(firstFreelistPointerExtent <= freelistLimit)) { | 531 uint16_t numNewFreelistEntries = 0; |
| 562 // Only consider used space in the slot span. If we consider wasted | 532 if (LIKELY(firstFreelistPointerExtent <= freelistLimit)) { |
| 563 // space, we may get an off-by-one when a freelist pointer fits in the | 533 // Only consider used space in the slot span. If we consider wasted |
| 564 // wasted space, but a slot does not. | 534 // space, we may get an off-by-one when a freelist pointer fits in the |
| 565 // We know we can fit at least one freelist pointer. | 535 // wasted space, but a slot does not. |
| 566 numNewFreelistEntries = 1; | 536 // We know we can fit at least one freelist pointer. |
| 567 // Any further entries require space for the whole slot span. | 537 numNewFreelistEntries = 1; |
| 568 numNewFreelistEntries += static_cast<uint16_t>((freelistLimit - firstFre
elistPointerExtent) / size); | 538 // Any further entries require space for the whole slot span. |
| 569 } | 539 numNewFreelistEntries += static_cast<uint16_t>((freelistLimit - firstFreelis
tPointerExtent) / size); |
| 570 | 540 } |
| 571 // We always return an object slot -- that's the +1 below. | 541 |
| 572 // We do not neccessarily create any new freelist entries, because we cross
sub page boundaries frequently for large bucket sizes. | 542 // We always return an object slot -- that's the +1 below. |
| 573 ASSERT(numNewFreelistEntries + 1 <= numSlots); | 543 // We do not neccessarily create any new freelist entries, because we cross su
b page boundaries frequently for large bucket sizes. |
| 574 numSlots -= (numNewFreelistEntries + 1); | 544 ASSERT(numNewFreelistEntries + 1 <= numSlots); |
| 575 page->numUnprovisionedSlots = numSlots; | 545 numSlots -= (numNewFreelistEntries + 1); |
| 576 page->numAllocatedSlots++; | 546 page->numUnprovisionedSlots = numSlots; |
| 577 | 547 page->numAllocatedSlots++; |
| 578 if (LIKELY(numNewFreelistEntries)) { | 548 |
| 579 char* freelistPointer = firstFreelistPointer; | 549 if (LIKELY(numNewFreelistEntries)) { |
| 580 PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*
>(freelistPointer); | 550 char* freelistPointer = firstFreelistPointer; |
| 581 page->freelistHead = entry; | 551 PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*>(fr
eelistPointer); |
| 582 while (--numNewFreelistEntries) { | 552 page->freelistHead = entry; |
| 583 freelistPointer += size; | 553 while (--numNewFreelistEntries) { |
| 584 PartitionFreelistEntry* nextEntry = reinterpret_cast<PartitionFreeli
stEntry*>(freelistPointer); | 554 freelistPointer += size; |
| 585 entry->next = partitionFreelistMask(nextEntry); | 555 PartitionFreelistEntry* nextEntry = reinterpret_cast<PartitionFreelistEntr
y*>(freelistPointer); |
| 586 entry = nextEntry; | 556 entry->next = partitionFreelistMask(nextEntry); |
| 587 } | 557 entry = nextEntry; |
| 588 entry->next = partitionFreelistMask(0); | 558 } |
| 589 } else { | 559 entry->next = partitionFreelistMask(0); |
| 590 page->freelistHead = 0; | 560 } else { |
| 591 } | 561 page->freelistHead = 0; |
| 592 return returnObject; | 562 } |
| 563 return returnObject; |
| 593 } | 564 } |
| 594 | 565 |
| 595 // This helper function scans a bucket's active page list for a suitable new | 566 // This helper function scans a bucket's active page list for a suitable new |
| 596 // active page. | 567 // active page. |
| 597 // When it finds a suitable new active page (one that has free slots and is not | 568 // When it finds a suitable new active page (one that has free slots and is not |
| 598 // empty), it is set as the new active page. If there is no suitable new | 569 // empty), it is set as the new active page. If there is no suitable new |
| 599 // active page, the current active page is set to the seed page. | 570 // active page, the current active page is set to the seed page. |
| 600 // As potential pages are scanned, they are tidied up according to their state. | 571 // As potential pages are scanned, they are tidied up according to their state. |
| 601 // Empty pages are swept on to the empty page list, decommitted pages on to the | 572 // Empty pages are swept on to the empty page list, decommitted pages on to the |
| 602 // decommitted page list and full pages are unlinked from any list. | 573 // decommitted page list and full pages are unlinked from any list. |
| 603 static bool partitionSetNewActivePage(PartitionBucket* bucket) | 574 static bool partitionSetNewActivePage(PartitionBucket* bucket) { |
| 604 { | 575 PartitionPage* page = bucket->activePagesHead; |
| 605 PartitionPage* page = bucket->activePagesHead; | 576 if (page == &PartitionRootBase::gSeedPage) |
| 606 if (page == &PartitionRootBase::gSeedPage) | |
| 607 return false; | |
| 608 | |
| 609 PartitionPage* nextPage; | |
| 610 | |
| 611 for (; page; page = nextPage) { | |
| 612 nextPage = page->nextPage; | |
| 613 ASSERT(page->bucket == bucket); | |
| 614 ASSERT(page != bucket->emptyPagesHead); | |
| 615 ASSERT(page != bucket->decommittedPagesHead); | |
| 616 | |
| 617 // Deal with empty and decommitted pages. | |
| 618 if (LIKELY(partitionPageStateIsActive(page))) { | |
| 619 // This page is usable because it has freelist entries, or has | |
| 620 // unprovisioned slots we can create freelist entries from. | |
| 621 bucket->activePagesHead = page; | |
| 622 return true; | |
| 623 } | |
| 624 if (LIKELY(partitionPageStateIsEmpty(page))) { | |
| 625 page->nextPage = bucket->emptyPagesHead; | |
| 626 bucket->emptyPagesHead = page; | |
| 627 } else if (LIKELY(partitionPageStateIsDecommitted(page))) { | |
| 628 page->nextPage = bucket->decommittedPagesHead; | |
| 629 bucket->decommittedPagesHead = page; | |
| 630 } else { | |
| 631 ASSERT(partitionPageStateIsFull(page)); | |
| 632 // If we get here, we found a full page. Skip over it too, and also | |
| 633 // tag it as full (via a negative value). We need it tagged so that | |
| 634 // free'ing can tell, and move it back into the active page list. | |
| 635 page->numAllocatedSlots = -page->numAllocatedSlots; | |
| 636 ++bucket->numFullPages; | |
| 637 // numFullPages is a uint16_t for efficient packing so guard against | |
| 638 // overflow to be safe. | |
| 639 if (UNLIKELY(!bucket->numFullPages)) | |
| 640 partitionBucketFull(); | |
| 641 // Not necessary but might help stop accidents. | |
| 642 page->nextPage = 0; | |
| 643 } | |
| 644 } | |
| 645 | |
| 646 bucket->activePagesHead = &PartitionRootGeneric::gSeedPage; | |
| 647 return false; | 577 return false; |
| 648 } | 578 |
| 649 | 579 PartitionPage* nextPage; |
| 650 static ALWAYS_INLINE PartitionDirectMapExtent* partitionPageToDirectMapExtent(Pa
rtitionPage* page) | 580 |
| 651 { | 581 for (; page; page = nextPage) { |
| 652 ASSERT(partitionBucketIsDirectMapped(page->bucket)); | 582 nextPage = page->nextPage; |
| 653 return reinterpret_cast<PartitionDirectMapExtent*>(reinterpret_cast<char*>(p
age) + 3 * kPageMetadataSize); | 583 ASSERT(page->bucket == bucket); |
| 654 } | 584 ASSERT(page != bucket->emptyPagesHead); |
| 655 | 585 ASSERT(page != bucket->decommittedPagesHead); |
| 656 static ALWAYS_INLINE void partitionPageSetRawSize(PartitionPage* page, size_t si
ze) | 586 |
| 657 { | 587 // Deal with empty and decommitted pages. |
| 658 size_t* rawSizePtr = partitionPageGetRawSizePtr(page); | 588 if (LIKELY(partitionPageStateIsActive(page))) { |
| 659 if (UNLIKELY(rawSizePtr != nullptr)) | 589 // This page is usable because it has freelist entries, or has |
| 660 *rawSizePtr = size; | 590 // unprovisioned slots we can create freelist entries from. |
| 661 } | 591 bucket->activePagesHead = page; |
| 662 | 592 return true; |
| 663 static ALWAYS_INLINE PartitionPage* partitionDirectMap(PartitionRootBase* root,
int flags, size_t rawSize) | 593 } |
| 664 { | 594 if (LIKELY(partitionPageStateIsEmpty(page))) { |
| 665 size_t size = partitionDirectMapSize(rawSize); | 595 page->nextPage = bucket->emptyPagesHead; |
| 666 | 596 bucket->emptyPagesHead = page; |
| 667 // Because we need to fake looking like a super page, we need to allocate | 597 } else if (LIKELY(partitionPageStateIsDecommitted(page))) { |
| 668 // a bunch of system pages more than "size": | 598 page->nextPage = bucket->decommittedPagesHead; |
| 669 // - The first few system pages are the partition page in which the super | 599 bucket->decommittedPagesHead = page; |
| 670 // page metadata is stored. We fault just one system page out of a partition | 600 } else { |
| 671 // page sized clump. | 601 ASSERT(partitionPageStateIsFull(page)); |
| 672 // - We add a trailing guard page on 32-bit (on 64-bit we rely on the | 602 // If we get here, we found a full page. Skip over it too, and also |
| 673 // massive address space plus randomization instead). | 603 // tag it as full (via a negative value). We need it tagged so that |
| 674 size_t mapSize = size + kPartitionPageSize; | 604 // free'ing can tell, and move it back into the active page list. |
| 605 page->numAllocatedSlots = -page->numAllocatedSlots; |
| 606 ++bucket->numFullPages; |
| 607 // numFullPages is a uint16_t for efficient packing so guard against |
| 608 // overflow to be safe. |
| 609 if (UNLIKELY(!bucket->numFullPages)) |
| 610 partitionBucketFull(); |
| 611 // Not necessary but might help stop accidents. |
| 612 page->nextPage = 0; |
| 613 } |
| 614 } |
| 615 |
| 616 bucket->activePagesHead = &PartitionRootGeneric::gSeedPage; |
| 617 return false; |
| 618 } |
| 619 |
| 620 static ALWAYS_INLINE PartitionDirectMapExtent* partitionPageToDirectMapExtent(Pa
rtitionPage* page) { |
| 621 ASSERT(partitionBucketIsDirectMapped(page->bucket)); |
| 622 return reinterpret_cast<PartitionDirectMapExtent*>(reinterpret_cast<char*>(pag
e) + 3 * kPageMetadataSize); |
| 623 } |
| 624 |
| 625 static ALWAYS_INLINE void partitionPageSetRawSize(PartitionPage* page, size_t si
ze) { |
| 626 size_t* rawSizePtr = partitionPageGetRawSizePtr(page); |
| 627 if (UNLIKELY(rawSizePtr != nullptr)) |
| 628 *rawSizePtr = size; |
| 629 } |
| 630 |
| 631 static ALWAYS_INLINE PartitionPage* partitionDirectMap(PartitionRootBase* root,
int flags, size_t rawSize) { |
| 632 size_t size = partitionDirectMapSize(rawSize); |
| 633 |
| 634 // Because we need to fake looking like a super page, we need to allocate |
| 635 // a bunch of system pages more than "size": |
| 636 // - The first few system pages are the partition page in which the super |
| 637 // page metadata is stored. We fault just one system page out of a partition |
| 638 // page sized clump. |
| 639 // - We add a trailing guard page on 32-bit (on 64-bit we rely on the |
| 640 // massive address space plus randomization instead). |
| 641 size_t mapSize = size + kPartitionPageSize; |
| 675 #if !CPU(64BIT) | 642 #if !CPU(64BIT) |
| 676 mapSize += kSystemPageSize; | 643 mapSize += kSystemPageSize; |
| 677 #endif | 644 #endif |
| 678 // Round up to the allocation granularity. | 645 // Round up to the allocation granularity. |
| 679 mapSize += kPageAllocationGranularityOffsetMask; | 646 mapSize += kPageAllocationGranularityOffsetMask; |
| 680 mapSize &= kPageAllocationGranularityBaseMask; | 647 mapSize &= kPageAllocationGranularityBaseMask; |
| 681 | 648 |
| 682 // TODO: these pages will be zero-filled. Consider internalizing an | 649 // TODO: these pages will be zero-filled. Consider internalizing an |
| 683 // allocZeroed() API so we can avoid a memset() entirely in this case. | 650 // allocZeroed() API so we can avoid a memset() entirely in this case. |
| 684 char* ptr = reinterpret_cast<char*>(allocPages(0, mapSize, kSuperPageSize, P
ageAccessible)); | 651 char* ptr = reinterpret_cast<char*>(allocPages(0, mapSize, kSuperPageSize, Pag
eAccessible)); |
| 685 if (UNLIKELY(!ptr)) | 652 if (UNLIKELY(!ptr)) |
| 653 return nullptr; |
| 654 |
| 655 size_t committedPageSize = size + kSystemPageSize; |
| 656 root->totalSizeOfDirectMappedPages += committedPageSize; |
| 657 partitionIncreaseCommittedPages(root, committedPageSize); |
| 658 |
| 659 char* slot = ptr + kPartitionPageSize; |
| 660 setSystemPagesInaccessible(ptr + (kSystemPageSize * 2), kPartitionPageSize - (
kSystemPageSize * 2)); |
| 661 #if !CPU(64BIT) |
| 662 setSystemPagesInaccessible(ptr, kSystemPageSize); |
| 663 setSystemPagesInaccessible(slot + size, kSystemPageSize); |
| 664 #endif |
| 665 |
| 666 PartitionSuperPageExtentEntry* extent = reinterpret_cast<PartitionSuperPageExt
entEntry*>(partitionSuperPageToMetadataArea(ptr)); |
| 667 extent->root = root; |
| 668 // The new structures are all located inside a fresh system page so they |
| 669 // will all be zeroed out. These ASSERTs are for documentation. |
| 670 ASSERT(!extent->superPageBase); |
| 671 ASSERT(!extent->superPagesEnd); |
| 672 ASSERT(!extent->next); |
| 673 PartitionPage* page = partitionPointerToPageNoAlignmentCheck(slot); |
| 674 PartitionBucket* bucket = reinterpret_cast<PartitionBucket*>(reinterpret_cast<
char*>(page) + (kPageMetadataSize * 2)); |
| 675 ASSERT(!page->nextPage); |
| 676 ASSERT(!page->numAllocatedSlots); |
| 677 ASSERT(!page->numUnprovisionedSlots); |
| 678 ASSERT(!page->pageOffset); |
| 679 ASSERT(!page->emptyCacheIndex); |
| 680 page->bucket = bucket; |
| 681 page->freelistHead = reinterpret_cast<PartitionFreelistEntry*>(slot); |
| 682 PartitionFreelistEntry* nextEntry = reinterpret_cast<PartitionFreelistEntry*>(
slot); |
| 683 nextEntry->next = partitionFreelistMask(0); |
| 684 |
| 685 ASSERT(!bucket->activePagesHead); |
| 686 ASSERT(!bucket->emptyPagesHead); |
| 687 ASSERT(!bucket->decommittedPagesHead); |
| 688 ASSERT(!bucket->numSystemPagesPerSlotSpan); |
| 689 ASSERT(!bucket->numFullPages); |
| 690 bucket->slotSize = size; |
| 691 |
| 692 PartitionDirectMapExtent* mapExtent = partitionPageToDirectMapExtent(page); |
| 693 mapExtent->mapSize = mapSize - kPartitionPageSize - kSystemPageSize; |
| 694 mapExtent->bucket = bucket; |
| 695 |
| 696 // Maintain the doubly-linked list of all direct mappings. |
| 697 mapExtent->nextExtent = root->directMapList; |
| 698 if (mapExtent->nextExtent) |
| 699 mapExtent->nextExtent->prevExtent = mapExtent; |
| 700 mapExtent->prevExtent = nullptr; |
| 701 root->directMapList = mapExtent; |
| 702 |
| 703 return page; |
| 704 } |
| 705 |
| 706 static ALWAYS_INLINE void partitionDirectUnmap(PartitionPage* page) { |
| 707 PartitionRootBase* root = partitionPageToRoot(page); |
| 708 const PartitionDirectMapExtent* extent = partitionPageToDirectMapExtent(page); |
| 709 size_t unmapSize = extent->mapSize; |
| 710 |
| 711 // Maintain the doubly-linked list of all direct mappings. |
| 712 if (extent->prevExtent) { |
| 713 ASSERT(extent->prevExtent->nextExtent == extent); |
| 714 extent->prevExtent->nextExtent = extent->nextExtent; |
| 715 } else { |
| 716 root->directMapList = extent->nextExtent; |
| 717 } |
| 718 if (extent->nextExtent) { |
| 719 ASSERT(extent->nextExtent->prevExtent == extent); |
| 720 extent->nextExtent->prevExtent = extent->prevExtent; |
| 721 } |
| 722 |
| 723 // Add on the size of the trailing guard page and preceeding partition |
| 724 // page. |
| 725 unmapSize += kPartitionPageSize + kSystemPageSize; |
| 726 |
| 727 size_t uncommittedPageSize = page->bucket->slotSize + kSystemPageSize; |
| 728 partitionDecreaseCommittedPages(root, uncommittedPageSize); |
| 729 ASSERT(root->totalSizeOfDirectMappedPages >= uncommittedPageSize); |
| 730 root->totalSizeOfDirectMappedPages -= uncommittedPageSize; |
| 731 |
| 732 ASSERT(!(unmapSize & kPageAllocationGranularityOffsetMask)); |
| 733 |
| 734 char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); |
| 735 // Account for the mapping starting a partition page before the actual |
| 736 // allocation address. |
| 737 ptr -= kPartitionPageSize; |
| 738 |
| 739 freePages(ptr, unmapSize); |
| 740 } |
| 741 |
| 742 void* partitionAllocSlowPath(PartitionRootBase* root, int flags, size_t size, Pa
rtitionBucket* bucket) { |
| 743 // The slow path is called when the freelist is empty. |
| 744 ASSERT(!bucket->activePagesHead->freelistHead); |
| 745 |
| 746 PartitionPage* newPage = nullptr; |
| 747 |
| 748 // For the partitionAllocGeneric API, we have a bunch of buckets marked |
| 749 // as special cases. We bounce them through to the slow path so that we |
| 750 // can still have a blazing fast hot path due to lack of corner-case |
| 751 // branches. |
| 752 bool returnNull = flags & PartitionAllocReturnNull; |
| 753 if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) { |
| 754 ASSERT(size > kGenericMaxBucketed); |
| 755 ASSERT(bucket == &PartitionRootBase::gPagedBucket); |
| 756 ASSERT(bucket->activePagesHead == &PartitionRootGeneric::gSeedPage); |
| 757 if (size > kGenericMaxDirectMapped) { |
| 758 if (returnNull) |
| 686 return nullptr; | 759 return nullptr; |
| 687 | 760 partitionExcessiveAllocationSize(); |
| 688 size_t committedPageSize = size + kSystemPageSize; | 761 } |
| 689 root->totalSizeOfDirectMappedPages += committedPageSize; | 762 newPage = partitionDirectMap(root, flags, size); |
| 690 partitionIncreaseCommittedPages(root, committedPageSize); | 763 } else if (LIKELY(partitionSetNewActivePage(bucket))) { |
| 691 | 764 // First, did we find an active page in the active pages list? |
| 692 char* slot = ptr + kPartitionPageSize; | 765 newPage = bucket->activePagesHead; |
| 693 setSystemPagesInaccessible(ptr + (kSystemPageSize * 2), kPartitionPageSize -
(kSystemPageSize * 2)); | 766 ASSERT(partitionPageStateIsActive(newPage)); |
| 694 #if !CPU(64BIT) | 767 } else if (LIKELY(bucket->emptyPagesHead != nullptr) || LIKELY(bucket->decommi
ttedPagesHead != nullptr)) { |
| 695 setSystemPagesInaccessible(ptr, kSystemPageSize); | 768 // Second, look in our lists of empty and decommitted pages. |
| 696 setSystemPagesInaccessible(slot + size, kSystemPageSize); | 769 // Check empty pages first, which are preferred, but beware that an |
| 697 #endif | 770 // empty page might have been decommitted. |
| 698 | 771 while (LIKELY((newPage = bucket->emptyPagesHead) != nullptr)) { |
| 699 PartitionSuperPageExtentEntry* extent = reinterpret_cast<PartitionSuperPageE
xtentEntry*>(partitionSuperPageToMetadataArea(ptr)); | 772 ASSERT(newPage->bucket == bucket); |
| 700 extent->root = root; | 773 ASSERT(partitionPageStateIsEmpty(newPage) || partitionPageStateIsDecommitt
ed(newPage)); |
| 701 // The new structures are all located inside a fresh system page so they | 774 bucket->emptyPagesHead = newPage->nextPage; |
| 702 // will all be zeroed out. These ASSERTs are for documentation. | 775 // Accept the empty page unless it got decommitted. |
| 703 ASSERT(!extent->superPageBase); | 776 if (newPage->freelistHead) { |
| 704 ASSERT(!extent->superPagesEnd); | 777 newPage->nextPage = nullptr; |
| 705 ASSERT(!extent->next); | 778 break; |
| 706 PartitionPage* page = partitionPointerToPageNoAlignmentCheck(slot); | 779 } |
| 707 PartitionBucket* bucket = reinterpret_cast<PartitionBucket*>(reinterpret_cas
t<char*>(page) + (kPageMetadataSize * 2)); | 780 ASSERT(partitionPageStateIsDecommitted(newPage)); |
| 708 ASSERT(!page->nextPage); | 781 newPage->nextPage = bucket->decommittedPagesHead; |
| 709 ASSERT(!page->numAllocatedSlots); | 782 bucket->decommittedPagesHead = newPage; |
| 710 ASSERT(!page->numUnprovisionedSlots); | 783 } |
| 711 ASSERT(!page->pageOffset); | 784 if (UNLIKELY(!newPage) && LIKELY(bucket->decommittedPagesHead != nullptr)) { |
| 712 ASSERT(!page->emptyCacheIndex); | 785 newPage = bucket->decommittedPagesHead; |
| 713 page->bucket = bucket; | 786 ASSERT(newPage->bucket == bucket); |
| 714 page->freelistHead = reinterpret_cast<PartitionFreelistEntry*>(slot); | 787 ASSERT(partitionPageStateIsDecommitted(newPage)); |
| 715 PartitionFreelistEntry* nextEntry = reinterpret_cast<PartitionFreelistEntry*
>(slot); | 788 bucket->decommittedPagesHead = newPage->nextPage; |
| 716 nextEntry->next = partitionFreelistMask(0); | 789 void* addr = partitionPageToPointer(newPage); |
| 717 | 790 partitionRecommitSystemPages(root, addr, partitionBucketBytes(newPage->buc
ket)); |
| 718 ASSERT(!bucket->activePagesHead); | 791 partitionPageReset(newPage); |
| 719 ASSERT(!bucket->emptyPagesHead); | 792 } |
| 720 ASSERT(!bucket->decommittedPagesHead); | 793 ASSERT(newPage); |
| 721 ASSERT(!bucket->numSystemPagesPerSlotSpan); | 794 } else { |
| 722 ASSERT(!bucket->numFullPages); | 795 // Third. If we get here, we need a brand new page. |
| 723 bucket->slotSize = size; | 796 uint16_t numPartitionPages = partitionBucketPartitionPages(bucket); |
| 724 | 797 void* rawPages = partitionAllocPartitionPages(root, flags, numPartitionPages
); |
| 725 PartitionDirectMapExtent* mapExtent = partitionPageToDirectMapExtent(page); | 798 if (LIKELY(rawPages != nullptr)) { |
| 726 mapExtent->mapSize = mapSize - kPartitionPageSize - kSystemPageSize; | 799 newPage = partitionPointerToPageNoAlignmentCheck(rawPages); |
| 727 mapExtent->bucket = bucket; | 800 partitionPageSetup(newPage, bucket); |
| 728 | 801 } |
| 729 // Maintain the doubly-linked list of all direct mappings. | 802 } |
| 730 mapExtent->nextExtent = root->directMapList; | 803 |
| 731 if (mapExtent->nextExtent) | 804 // Bail if we had a memory allocation failure. |
| 732 mapExtent->nextExtent->prevExtent = mapExtent; | 805 if (UNLIKELY(!newPage)) { |
| 733 mapExtent->prevExtent = nullptr; | 806 ASSERT(bucket->activePagesHead == &PartitionRootGeneric::gSeedPage); |
| 734 root->directMapList = mapExtent; | 807 if (returnNull) |
| 735 | 808 return nullptr; |
| 736 return page; | 809 partitionOutOfMemory(root); |
| 737 } | 810 } |
| 738 | 811 |
| 739 static ALWAYS_INLINE void partitionDirectUnmap(PartitionPage* page) | 812 bucket = newPage->bucket; |
| 740 { | 813 ASSERT(bucket != &PartitionRootBase::gPagedBucket); |
| 741 PartitionRootBase* root = partitionPageToRoot(page); | 814 bucket->activePagesHead = newPage; |
| 742 const PartitionDirectMapExtent* extent = partitionPageToDirectMapExtent(page
); | 815 partitionPageSetRawSize(newPage, size); |
| 743 size_t unmapSize = extent->mapSize; | 816 |
| 744 | 817 // If we found an active page with free slots, or an empty page, we have a |
| 745 // Maintain the doubly-linked list of all direct mappings. | 818 // usable freelist head. |
| 746 if (extent->prevExtent) { | 819 if (LIKELY(newPage->freelistHead != nullptr)) { |
| 747 ASSERT(extent->prevExtent->nextExtent == extent); | 820 PartitionFreelistEntry* entry = newPage->freelistHead; |
| 748 extent->prevExtent->nextExtent = extent->nextExtent; | 821 PartitionFreelistEntry* newHead = partitionFreelistMask(entry->next); |
| 749 } else { | 822 newPage->freelistHead = newHead; |
| 750 root->directMapList = extent->nextExtent; | 823 newPage->numAllocatedSlots++; |
| 751 } | 824 return entry; |
| 752 if (extent->nextExtent) { | 825 } |
| 753 ASSERT(extent->nextExtent->prevExtent == extent); | 826 // Otherwise, we need to build the freelist. |
| 754 extent->nextExtent->prevExtent = extent->prevExtent; | 827 ASSERT(newPage->numUnprovisionedSlots); |
| 755 } | 828 return partitionPageAllocAndFillFreelist(newPage); |
| 756 | 829 } |
| 757 // Add on the size of the trailing guard page and preceeding partition | 830 |
| 758 // page. | 831 static ALWAYS_INLINE void partitionDecommitPage(PartitionRootBase* root, Partiti
onPage* page) { |
| 759 unmapSize += kPartitionPageSize + kSystemPageSize; | 832 ASSERT(partitionPageStateIsEmpty(page)); |
| 760 | 833 ASSERT(!partitionBucketIsDirectMapped(page->bucket)); |
| 761 size_t uncommittedPageSize = page->bucket->slotSize + kSystemPageSize; | 834 void* addr = partitionPageToPointer(page); |
| 762 partitionDecreaseCommittedPages(root, uncommittedPageSize); | 835 partitionDecommitSystemPages(root, addr, partitionBucketBytes(page->bucket)); |
| 763 ASSERT(root->totalSizeOfDirectMappedPages >= uncommittedPageSize); | 836 |
| 764 root->totalSizeOfDirectMappedPages -= uncommittedPageSize; | 837 // We actually leave the decommitted page in the active list. We'll sweep |
| 765 | 838 // it on to the decommitted page list when we next walk the active page |
| 766 ASSERT(!(unmapSize & kPageAllocationGranularityOffsetMask)); | 839 // list. |
| 767 | 840 // Pulling this trick enables us to use a singly-linked page list for all |
| 768 char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); | 841 // cases, which is critical in keeping the page metadata structure down to |
| 769 // Account for the mapping starting a partition page before the actual | 842 // 32 bytes in size. |
| 770 // allocation address. | 843 page->freelistHead = 0; |
| 771 ptr -= kPartitionPageSize; | 844 page->numUnprovisionedSlots = 0; |
| 772 | 845 ASSERT(partitionPageStateIsDecommitted(page)); |
| 773 freePages(ptr, unmapSize); | 846 } |
| 774 } | 847 |
| 775 | 848 static void partitionDecommitPageIfPossible(PartitionRootBase* root, PartitionPa
ge* page) { |
| 776 void* partitionAllocSlowPath(PartitionRootBase* root, int flags, size_t size, Pa
rtitionBucket* bucket) | 849 ASSERT(page->emptyCacheIndex >= 0); |
| 777 { | 850 ASSERT(static_cast<unsigned>(page->emptyCacheIndex) < kMaxFreeableSpans); |
| 778 // The slow path is called when the freelist is empty. | 851 ASSERT(page == root->globalEmptyPageRing[page->emptyCacheIndex]); |
| 779 ASSERT(!bucket->activePagesHead->freelistHead); | 852 page->emptyCacheIndex = -1; |
| 780 | 853 if (partitionPageStateIsEmpty(page)) |
| 781 PartitionPage* newPage = nullptr; | 854 partitionDecommitPage(root, page); |
| 782 | 855 } |
| 783 // For the partitionAllocGeneric API, we have a bunch of buckets marked | 856 |
| 784 // as special cases. We bounce them through to the slow path so that we | 857 static ALWAYS_INLINE void partitionRegisterEmptyPage(PartitionPage* page) { |
| 785 // can still have a blazing fast hot path due to lack of corner-case | 858 ASSERT(partitionPageStateIsEmpty(page)); |
| 786 // branches. | 859 PartitionRootBase* root = partitionPageToRoot(page); |
| 787 bool returnNull = flags & PartitionAllocReturnNull; | 860 |
| 788 if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) { | 861 // If the page is already registered as empty, give it another life. |
| 789 ASSERT(size > kGenericMaxBucketed); | 862 if (page->emptyCacheIndex != -1) { |
| 790 ASSERT(bucket == &PartitionRootBase::gPagedBucket); | |
| 791 ASSERT(bucket->activePagesHead == &PartitionRootGeneric::gSeedPage); | |
| 792 if (size > kGenericMaxDirectMapped) { | |
| 793 if (returnNull) | |
| 794 return nullptr; | |
| 795 partitionExcessiveAllocationSize(); | |
| 796 } | |
| 797 newPage = partitionDirectMap(root, flags, size); | |
| 798 } else if (LIKELY(partitionSetNewActivePage(bucket))) { | |
| 799 // First, did we find an active page in the active pages list? | |
| 800 newPage = bucket->activePagesHead; | |
| 801 ASSERT(partitionPageStateIsActive(newPage)); | |
| 802 } else if (LIKELY(bucket->emptyPagesHead != nullptr) || LIKELY(bucket->decom
mittedPagesHead != nullptr)) { | |
| 803 // Second, look in our lists of empty and decommitted pages. | |
| 804 // Check empty pages first, which are preferred, but beware that an | |
| 805 // empty page might have been decommitted. | |
| 806 while (LIKELY((newPage = bucket->emptyPagesHead) != nullptr)) { | |
| 807 ASSERT(newPage->bucket == bucket); | |
| 808 ASSERT(partitionPageStateIsEmpty(newPage) || partitionPageStateIsDec
ommitted(newPage)); | |
| 809 bucket->emptyPagesHead = newPage->nextPage; | |
| 810 // Accept the empty page unless it got decommitted. | |
| 811 if (newPage->freelistHead) { | |
| 812 newPage->nextPage = nullptr; | |
| 813 break; | |
| 814 } | |
| 815 ASSERT(partitionPageStateIsDecommitted(newPage)); | |
| 816 newPage->nextPage = bucket->decommittedPagesHead; | |
| 817 bucket->decommittedPagesHead = newPage; | |
| 818 } | |
| 819 if (UNLIKELY(!newPage) && LIKELY(bucket->decommittedPagesHead != nullptr
)) { | |
| 820 newPage = bucket->decommittedPagesHead; | |
| 821 ASSERT(newPage->bucket == bucket); | |
| 822 ASSERT(partitionPageStateIsDecommitted(newPage)); | |
| 823 bucket->decommittedPagesHead = newPage->nextPage; | |
| 824 void* addr = partitionPageToPointer(newPage); | |
| 825 partitionRecommitSystemPages(root, addr, partitionBucketBytes(newPag
e->bucket)); | |
| 826 partitionPageReset(newPage); | |
| 827 } | |
| 828 ASSERT(newPage); | |
| 829 } else { | |
| 830 // Third. If we get here, we need a brand new page. | |
| 831 uint16_t numPartitionPages = partitionBucketPartitionPages(bucket); | |
| 832 void* rawPages = partitionAllocPartitionPages(root, flags, numPartitionP
ages); | |
| 833 if (LIKELY(rawPages != nullptr)) { | |
| 834 newPage = partitionPointerToPageNoAlignmentCheck(rawPages); | |
| 835 partitionPageSetup(newPage, bucket); | |
| 836 } | |
| 837 } | |
| 838 | |
| 839 // Bail if we had a memory allocation failure. | |
| 840 if (UNLIKELY(!newPage)) { | |
| 841 ASSERT(bucket->activePagesHead == &PartitionRootGeneric::gSeedPage); | |
| 842 if (returnNull) | |
| 843 return nullptr; | |
| 844 partitionOutOfMemory(root); | |
| 845 } | |
| 846 | |
| 847 bucket = newPage->bucket; | |
| 848 ASSERT(bucket != &PartitionRootBase::gPagedBucket); | |
| 849 bucket->activePagesHead = newPage; | |
| 850 partitionPageSetRawSize(newPage, size); | |
| 851 | |
| 852 // If we found an active page with free slots, or an empty page, we have a | |
| 853 // usable freelist head. | |
| 854 if (LIKELY(newPage->freelistHead != nullptr)) { | |
| 855 PartitionFreelistEntry* entry = newPage->freelistHead; | |
| 856 PartitionFreelistEntry* newHead = partitionFreelistMask(entry->next); | |
| 857 newPage->freelistHead = newHead; | |
| 858 newPage->numAllocatedSlots++; | |
| 859 return entry; | |
| 860 } | |
| 861 // Otherwise, we need to build the freelist. | |
| 862 ASSERT(newPage->numUnprovisionedSlots); | |
| 863 return partitionPageAllocAndFillFreelist(newPage); | |
| 864 } | |
| 865 | |
| 866 static ALWAYS_INLINE void partitionDecommitPage(PartitionRootBase* root, Partiti
onPage* page) | |
| 867 { | |
| 868 ASSERT(partitionPageStateIsEmpty(page)); | |
| 869 ASSERT(!partitionBucketIsDirectMapped(page->bucket)); | |
| 870 void* addr = partitionPageToPointer(page); | |
| 871 partitionDecommitSystemPages(root, addr, partitionBucketBytes(page->bucket))
; | |
| 872 | |
| 873 // We actually leave the decommitted page in the active list. We'll sweep | |
| 874 // it on to the decommitted page list when we next walk the active page | |
| 875 // list. | |
| 876 // Pulling this trick enables us to use a singly-linked page list for all | |
| 877 // cases, which is critical in keeping the page metadata structure down to | |
| 878 // 32 bytes in size. | |
| 879 page->freelistHead = 0; | |
| 880 page->numUnprovisionedSlots = 0; | |
| 881 ASSERT(partitionPageStateIsDecommitted(page)); | |
| 882 } | |
| 883 | |
| 884 static void partitionDecommitPageIfPossible(PartitionRootBase* root, PartitionPa
ge* page) | |
| 885 { | |
| 886 ASSERT(page->emptyCacheIndex >= 0); | 863 ASSERT(page->emptyCacheIndex >= 0); |
| 887 ASSERT(static_cast<unsigned>(page->emptyCacheIndex) < kMaxFreeableSpans); | 864 ASSERT(static_cast<unsigned>(page->emptyCacheIndex) < kMaxFreeableSpans); |
| 888 ASSERT(page == root->globalEmptyPageRing[page->emptyCacheIndex]); | 865 ASSERT(root->globalEmptyPageRing[page->emptyCacheIndex] == page); |
| 889 page->emptyCacheIndex = -1; | 866 root->globalEmptyPageRing[page->emptyCacheIndex] = 0; |
| 890 if (partitionPageStateIsEmpty(page)) | 867 } |
| 891 partitionDecommitPage(root, page); | 868 |
| 892 } | 869 int16_t currentIndex = root->globalEmptyPageRingIndex; |
| 893 | 870 PartitionPage* pageToDecommit = root->globalEmptyPageRing[currentIndex]; |
| 894 static ALWAYS_INLINE void partitionRegisterEmptyPage(PartitionPage* page) | 871 // The page might well have been re-activated, filled up, etc. before we get |
| 895 { | 872 // around to looking at it here. |
| 896 ASSERT(partitionPageStateIsEmpty(page)); | 873 if (pageToDecommit) |
| 897 PartitionRootBase* root = partitionPageToRoot(page); | 874 partitionDecommitPageIfPossible(root, pageToDecommit); |
| 898 | 875 |
| 899 // If the page is already registered as empty, give it another life. | 876 // We put the empty slot span on our global list of "pages that were once |
| 900 if (page->emptyCacheIndex != -1) { | 877 // empty". thus providing it a bit of breathing room to get re-used before |
| 901 ASSERT(page->emptyCacheIndex >= 0); | 878 // we really free it. This improves performance, particularly on Mac OS X |
| 902 ASSERT(static_cast<unsigned>(page->emptyCacheIndex) < kMaxFreeableSpans)
; | 879 // which has subpar memory management performance. |
| 903 ASSERT(root->globalEmptyPageRing[page->emptyCacheIndex] == page); | 880 root->globalEmptyPageRing[currentIndex] = page; |
| 904 root->globalEmptyPageRing[page->emptyCacheIndex] = 0; | 881 page->emptyCacheIndex = currentIndex; |
| 905 } | 882 ++currentIndex; |
| 906 | 883 if (currentIndex == kMaxFreeableSpans) |
| 907 int16_t currentIndex = root->globalEmptyPageRingIndex; | 884 currentIndex = 0; |
| 908 PartitionPage* pageToDecommit = root->globalEmptyPageRing[currentIndex]; | 885 root->globalEmptyPageRingIndex = currentIndex; |
| 909 // The page might well have been re-activated, filled up, etc. before we get | 886 } |
| 910 // around to looking at it here. | 887 |
| 911 if (pageToDecommit) | 888 static void partitionDecommitEmptyPages(PartitionRootBase* root) { |
| 912 partitionDecommitPageIfPossible(root, pageToDecommit); | 889 for (size_t i = 0; i < kMaxFreeableSpans; ++i) { |
| 913 | 890 PartitionPage* page = root->globalEmptyPageRing[i]; |
| 914 // We put the empty slot span on our global list of "pages that were once | 891 if (page) |
| 915 // empty". thus providing it a bit of breathing room to get re-used before | 892 partitionDecommitPageIfPossible(root, page); |
| 916 // we really free it. This improves performance, particularly on Mac OS X | 893 root->globalEmptyPageRing[i] = nullptr; |
| 917 // which has subpar memory management performance. | 894 } |
| 918 root->globalEmptyPageRing[currentIndex] = page; | 895 } |
| 919 page->emptyCacheIndex = currentIndex; | 896 |
| 920 ++currentIndex; | 897 void partitionFreeSlowPath(PartitionPage* page) { |
| 921 if (currentIndex == kMaxFreeableSpans) | 898 PartitionBucket* bucket = page->bucket; |
| 922 currentIndex = 0; | 899 ASSERT(page != &PartitionRootGeneric::gSeedPage); |
| 923 root->globalEmptyPageRingIndex = currentIndex; | 900 if (LIKELY(page->numAllocatedSlots == 0)) { |
| 924 } | 901 // Page became fully unused. |
| 925 | 902 if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) { |
| 926 static void partitionDecommitEmptyPages(PartitionRootBase* root) | 903 partitionDirectUnmap(page); |
| 927 { | 904 return; |
| 928 for (size_t i = 0; i < kMaxFreeableSpans; ++i) { | 905 } |
| 929 PartitionPage* page = root->globalEmptyPageRing[i]; | 906 // If it's the current active page, change it. We bounce the page to |
| 930 if (page) | 907 // the empty list as a force towards defragmentation. |
| 931 partitionDecommitPageIfPossible(root, page); | 908 if (LIKELY(page == bucket->activePagesHead)) |
| 932 root->globalEmptyPageRing[i] = nullptr; | 909 (void)partitionSetNewActivePage(bucket); |
| 933 } | 910 ASSERT(bucket->activePagesHead != page); |
| 934 } | 911 |
| 935 | 912 partitionPageSetRawSize(page, 0); |
| 936 void partitionFreeSlowPath(PartitionPage* page) | 913 ASSERT(!partitionPageGetRawSize(page)); |
| 937 { | 914 |
| 938 PartitionBucket* bucket = page->bucket; | 915 partitionRegisterEmptyPage(page); |
| 939 ASSERT(page != &PartitionRootGeneric::gSeedPage); | 916 } else { |
| 940 if (LIKELY(page->numAllocatedSlots == 0)) { | 917 ASSERT(!partitionBucketIsDirectMapped(bucket)); |
| 941 // Page became fully unused. | 918 // Ensure that the page is full. That's the only valid case if we |
| 942 if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) { | 919 // arrive here. |
| 943 partitionDirectUnmap(page); | 920 ASSERT(page->numAllocatedSlots < 0); |
| 944 return; | 921 // A transition of numAllocatedSlots from 0 to -1 is not legal, and |
| 945 } | 922 // likely indicates a double-free. |
| 946 // If it's the current active page, change it. We bounce the page to | 923 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(page->numAllocatedSlots != -1); |
| 947 // the empty list as a force towards defragmentation. | 924 page->numAllocatedSlots = -page->numAllocatedSlots - 2; |
| 948 if (LIKELY(page == bucket->activePagesHead)) | 925 ASSERT(page->numAllocatedSlots == partitionBucketSlots(bucket) - 1); |
| 949 (void) partitionSetNewActivePage(bucket); | 926 // Fully used page became partially used. It must be put back on the |
| 950 ASSERT(bucket->activePagesHead != page); | 927 // non-full page list. Also make it the current page to increase the |
| 951 | 928 // chances of it being filled up again. The old current page will be |
| 952 partitionPageSetRawSize(page, 0); | 929 // the next page. |
| 953 ASSERT(!partitionPageGetRawSize(page)); | 930 ASSERT(!page->nextPage); |
| 954 | 931 if (LIKELY(bucket->activePagesHead != &PartitionRootGeneric::gSeedPage)) |
| 955 partitionRegisterEmptyPage(page); | 932 page->nextPage = bucket->activePagesHead; |
| 956 } else { | 933 bucket->activePagesHead = page; |
| 957 ASSERT(!partitionBucketIsDirectMapped(bucket)); | 934 --bucket->numFullPages; |
| 958 // Ensure that the page is full. That's the only valid case if we | 935 // Special case: for a partition page with just a single slot, it may |
| 959 // arrive here. | 936 // now be empty and we want to run it through the empty logic. |
| 960 ASSERT(page->numAllocatedSlots < 0); | 937 if (UNLIKELY(page->numAllocatedSlots == 0)) |
| 961 // A transition of numAllocatedSlots from 0 to -1 is not legal, and | 938 partitionFreeSlowPath(page); |
| 962 // likely indicates a double-free. | 939 } |
| 963 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(page->numAllocatedSlots != -1); | 940 } |
| 964 page->numAllocatedSlots = -page->numAllocatedSlots - 2; | 941 |
| 965 ASSERT(page->numAllocatedSlots == partitionBucketSlots(bucket) - 1); | 942 bool partitionReallocDirectMappedInPlace(PartitionRootGeneric* root, PartitionPa
ge* page, size_t rawSize) { |
| 966 // Fully used page became partially used. It must be put back on the | 943 ASSERT(partitionBucketIsDirectMapped(page->bucket)); |
| 967 // non-full page list. Also make it the current page to increase the | 944 |
| 968 // chances of it being filled up again. The old current page will be | 945 rawSize = partitionCookieSizeAdjustAdd(rawSize); |
| 969 // the next page. | 946 |
| 970 ASSERT(!page->nextPage); | 947 // Note that the new size might be a bucketed size; this function is called |
| 971 if (LIKELY(bucket->activePagesHead != &PartitionRootGeneric::gSeedPage)) | 948 // whenever we're reallocating a direct mapped allocation. |
| 972 page->nextPage = bucket->activePagesHead; | 949 size_t newSize = partitionDirectMapSize(rawSize); |
| 973 bucket->activePagesHead = page; | 950 if (newSize < kGenericMinDirectMappedDownsize) |
| 974 --bucket->numFullPages; | 951 return false; |
| 975 // Special case: for a partition page with just a single slot, it may | 952 |
| 976 // now be empty and we want to run it through the empty logic. | 953 // bucket->slotSize is the current size of the allocation. |
| 977 if (UNLIKELY(page->numAllocatedSlots == 0)) | 954 size_t currentSize = page->bucket->slotSize; |
| 978 partitionFreeSlowPath(page); | 955 if (newSize == currentSize) |
| 979 } | 956 return true; |
| 980 } | 957 |
| 981 | 958 char* charPtr = static_cast<char*>(partitionPageToPointer(page)); |
| 982 bool partitionReallocDirectMappedInPlace(PartitionRootGeneric* root, PartitionPa
ge* page, size_t rawSize) | 959 |
| 983 { | 960 if (newSize < currentSize) { |
| 984 ASSERT(partitionBucketIsDirectMapped(page->bucket)); | 961 size_t mapSize = partitionPageToDirectMapExtent(page)->mapSize; |
| 985 | 962 |
| 986 rawSize = partitionCookieSizeAdjustAdd(rawSize); | 963 // Don't reallocate in-place if new size is less than 80 % of the full |
| 987 | 964 // map size, to avoid holding on to too much unused address space. |
| 988 // Note that the new size might be a bucketed size; this function is called | 965 if ((newSize / kSystemPageSize) * 5 < (mapSize / kSystemPageSize) * 4) |
| 989 // whenever we're reallocating a direct mapped allocation. | 966 return false; |
| 990 size_t newSize = partitionDirectMapSize(rawSize); | 967 |
| 991 if (newSize < kGenericMinDirectMappedDownsize) | 968 // Shrink by decommitting unneeded pages and making them inaccessible. |
| 992 return false; | 969 size_t decommitSize = currentSize - newSize; |
| 993 | 970 partitionDecommitSystemPages(root, charPtr + newSize, decommitSize); |
| 994 // bucket->slotSize is the current size of the allocation. | 971 setSystemPagesInaccessible(charPtr + newSize, decommitSize); |
| 995 size_t currentSize = page->bucket->slotSize; | 972 } else if (newSize <= partitionPageToDirectMapExtent(page)->mapSize) { |
| 996 if (newSize == currentSize) | 973 // Grow within the actually allocated memory. Just need to make the |
| 997 return true; | 974 // pages accessible again. |
| 998 | 975 size_t recommitSize = newSize - currentSize; |
| 999 char* charPtr = static_cast<char*>(partitionPageToPointer(page)); | 976 bool ret = setSystemPagesAccessible(charPtr + currentSize, recommitSize); |
| 1000 | 977 RELEASE_ASSERT(ret); |
| 1001 if (newSize < currentSize) { | 978 partitionRecommitSystemPages(root, charPtr + currentSize, recommitSize); |
| 1002 size_t mapSize = partitionPageToDirectMapExtent(page)->mapSize; | |
| 1003 | |
| 1004 // Don't reallocate in-place if new size is less than 80 % of the full | |
| 1005 // map size, to avoid holding on to too much unused address space. | |
| 1006 if ((newSize / kSystemPageSize) * 5 < (mapSize / kSystemPageSize) * 4) | |
| 1007 return false; | |
| 1008 | |
| 1009 // Shrink by decommitting unneeded pages and making them inaccessible. | |
| 1010 size_t decommitSize = currentSize - newSize; | |
| 1011 partitionDecommitSystemPages(root, charPtr + newSize, decommitSize); | |
| 1012 setSystemPagesInaccessible(charPtr + newSize, decommitSize); | |
| 1013 } else if (newSize <= partitionPageToDirectMapExtent(page)->mapSize) { | |
| 1014 // Grow within the actually allocated memory. Just need to make the | |
| 1015 // pages accessible again. | |
| 1016 size_t recommitSize = newSize - currentSize; | |
| 1017 bool ret = setSystemPagesAccessible(charPtr + currentSize, recommitSize)
; | |
| 1018 RELEASE_ASSERT(ret); | |
| 1019 partitionRecommitSystemPages(root, charPtr + currentSize, recommitSize); | |
| 1020 | 979 |
| 1021 #if ENABLE(ASSERT) | 980 #if ENABLE(ASSERT) |
| 1022 memset(charPtr + currentSize, kUninitializedByte, recommitSize); | 981 memset(charPtr + currentSize, kUninitializedByte, recommitSize); |
| 1023 #endif | 982 #endif |
| 1024 } else { | 983 } else { |
| 1025 // We can't perform the realloc in-place. | 984 // We can't perform the realloc in-place. |
| 1026 // TODO: support this too when possible. | 985 // TODO: support this too when possible. |
| 1027 return false; | 986 return false; |
| 1028 } | 987 } |
| 1029 | 988 |
| 1030 #if ENABLE(ASSERT) | 989 #if ENABLE(ASSERT) |
| 1031 // Write a new trailing cookie. | 990 // Write a new trailing cookie. |
| 1032 partitionCookieWriteValue(charPtr + rawSize - kCookieSize); | 991 partitionCookieWriteValue(charPtr + rawSize - kCookieSize); |
| 1033 #endif | 992 #endif |
| 1034 | 993 |
| 1035 partitionPageSetRawSize(page, rawSize); | 994 partitionPageSetRawSize(page, rawSize); |
| 1036 ASSERT(partitionPageGetRawSize(page) == rawSize); | 995 ASSERT(partitionPageGetRawSize(page) == rawSize); |
| 1037 | 996 |
| 1038 page->bucket->slotSize = newSize; | 997 page->bucket->slotSize = newSize; |
| 1039 return true; | 998 return true; |
| 1040 } | 999 } |
| 1041 | 1000 |
| 1042 void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newS
ize) | 1001 void* partitionReallocGeneric(PartitionRootGeneric* root, void* ptr, size_t newS
ize) { |
| 1043 { | |
| 1044 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) | 1002 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) |
| 1045 return realloc(ptr, newSize); | 1003 return realloc(ptr, newSize); |
| 1046 #else | 1004 #else |
| 1047 if (UNLIKELY(!ptr)) | 1005 if (UNLIKELY(!ptr)) |
| 1048 return partitionAllocGeneric(root, newSize); | 1006 return partitionAllocGeneric(root, newSize); |
| 1049 if (UNLIKELY(!newSize)) { | 1007 if (UNLIKELY(!newSize)) { |
| 1050 partitionFreeGeneric(root, ptr); | |
| 1051 return 0; | |
| 1052 } | |
| 1053 | |
| 1054 if (newSize > kGenericMaxDirectMapped) | |
| 1055 partitionExcessiveAllocationSize(); | |
| 1056 | |
| 1057 ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(ptr))); | |
| 1058 | |
| 1059 PartitionPage* page = partitionPointerToPage(partitionCookieFreePointerAdjus
t(ptr)); | |
| 1060 | |
| 1061 if (UNLIKELY(partitionBucketIsDirectMapped(page->bucket))) { | |
| 1062 // We may be able to perform the realloc in place by changing the | |
| 1063 // accessibility of memory pages and, if reducing the size, decommitting | |
| 1064 // them. | |
| 1065 if (partitionReallocDirectMappedInPlace(root, page, newSize)) { | |
| 1066 PartitionAllocHooks::reallocHookIfEnabled(ptr, ptr, newSize); | |
| 1067 return ptr; | |
| 1068 } | |
| 1069 } | |
| 1070 | |
| 1071 size_t actualNewSize = partitionAllocActualSize(root, newSize); | |
| 1072 size_t actualOldSize = partitionAllocGetSize(ptr); | |
| 1073 | |
| 1074 // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the | |
| 1075 // new size is a significant percentage smaller. We could do the same if we | |
| 1076 // determine it is a win. | |
| 1077 if (actualNewSize == actualOldSize) { | |
| 1078 // Trying to allocate a block of size newSize would give us a block of | |
| 1079 // the same size as the one we've already got, so no point in doing | |
| 1080 // anything here. | |
| 1081 return ptr; | |
| 1082 } | |
| 1083 | |
| 1084 // This realloc cannot be resized in-place. Sadness. | |
| 1085 void* ret = partitionAllocGeneric(root, newSize); | |
| 1086 size_t copySize = actualOldSize; | |
| 1087 if (newSize < copySize) | |
| 1088 copySize = newSize; | |
| 1089 | |
| 1090 memcpy(ret, ptr, copySize); | |
| 1091 partitionFreeGeneric(root, ptr); | 1008 partitionFreeGeneric(root, ptr); |
| 1092 return ret; | 1009 return 0; |
| 1010 } |
| 1011 |
| 1012 if (newSize > kGenericMaxDirectMapped) |
| 1013 partitionExcessiveAllocationSize(); |
| 1014 |
| 1015 ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(ptr))); |
| 1016 |
| 1017 PartitionPage* page = partitionPointerToPage(partitionCookieFreePointerAdjust(
ptr)); |
| 1018 |
| 1019 if (UNLIKELY(partitionBucketIsDirectMapped(page->bucket))) { |
| 1020 // We may be able to perform the realloc in place by changing the |
| 1021 // accessibility of memory pages and, if reducing the size, decommitting |
| 1022 // them. |
| 1023 if (partitionReallocDirectMappedInPlace(root, page, newSize)) { |
| 1024 PartitionAllocHooks::reallocHookIfEnabled(ptr, ptr, newSize); |
| 1025 return ptr; |
| 1026 } |
| 1027 } |
| 1028 |
| 1029 size_t actualNewSize = partitionAllocActualSize(root, newSize); |
| 1030 size_t actualOldSize = partitionAllocGetSize(ptr); |
| 1031 |
| 1032 // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the |
| 1033 // new size is a significant percentage smaller. We could do the same if we |
| 1034 // determine it is a win. |
| 1035 if (actualNewSize == actualOldSize) { |
| 1036 // Trying to allocate a block of size newSize would give us a block of |
| 1037 // the same size as the one we've already got, so no point in doing |
| 1038 // anything here. |
| 1039 return ptr; |
| 1040 } |
| 1041 |
| 1042 // This realloc cannot be resized in-place. Sadness. |
| 1043 void* ret = partitionAllocGeneric(root, newSize); |
| 1044 size_t copySize = actualOldSize; |
| 1045 if (newSize < copySize) |
| 1046 copySize = newSize; |
| 1047 |
| 1048 memcpy(ret, ptr, copySize); |
| 1049 partitionFreeGeneric(root, ptr); |
| 1050 return ret; |
| 1093 #endif | 1051 #endif |
| 1094 } | 1052 } |
| 1095 | 1053 |
| 1096 static size_t partitionPurgePage(PartitionPage* page, bool discard) | 1054 static size_t partitionPurgePage(PartitionPage* page, bool discard) { |
| 1097 { | 1055 const PartitionBucket* bucket = page->bucket; |
| 1098 const PartitionBucket* bucket = page->bucket; | 1056 size_t slotSize = bucket->slotSize; |
| 1099 size_t slotSize = bucket->slotSize; | 1057 if (slotSize < kSystemPageSize || !page->numAllocatedSlots) |
| 1100 if (slotSize < kSystemPageSize || !page->numAllocatedSlots) | 1058 return 0; |
| 1101 return 0; | 1059 |
| 1102 | 1060 size_t bucketNumSlots = partitionBucketSlots(bucket); |
| 1103 size_t bucketNumSlots = partitionBucketSlots(bucket); | 1061 size_t discardableBytes = 0; |
| 1104 size_t discardableBytes = 0; | 1062 |
| 1105 | 1063 size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page)); |
| 1106 size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page)); | 1064 if (rawSize) { |
| 1107 if (rawSize) { | 1065 uint32_t usedBytes = static_cast<uint32_t>(partitionRoundUpToSystemPage(rawS
ize)); |
| 1108 uint32_t usedBytes = static_cast<uint32_t>(partitionRoundUpToSystemPage(
rawSize)); | 1066 discardableBytes = bucket->slotSize - usedBytes; |
| 1109 discardableBytes = bucket->slotSize - usedBytes; | 1067 if (discardableBytes && discard) { |
| 1110 if (discardableBytes && discard) { | 1068 char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); |
| 1111 char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); | 1069 ptr += usedBytes; |
| 1112 ptr += usedBytes; | 1070 discardSystemPages(ptr, discardableBytes); |
| 1113 discardSystemPages(ptr, discardableBytes); | |
| 1114 } | |
| 1115 return discardableBytes; | |
| 1116 } | |
| 1117 | |
| 1118 const size_t maxSlotCount = (kPartitionPageSize * kMaxPartitionPagesPerSlotS
pan) / kSystemPageSize; | |
| 1119 ASSERT(bucketNumSlots <= maxSlotCount); | |
| 1120 ASSERT(page->numUnprovisionedSlots < bucketNumSlots); | |
| 1121 size_t numSlots = bucketNumSlots - page->numUnprovisionedSlots; | |
| 1122 char slotUsage[maxSlotCount]; | |
| 1123 size_t lastSlot = static_cast<size_t>(-1); | |
| 1124 memset(slotUsage, 1, numSlots); | |
| 1125 char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); | |
| 1126 PartitionFreelistEntry* entry = page->freelistHead; | |
| 1127 // First, walk the freelist for this page and make a bitmap of which slots | |
| 1128 // are not in use. | |
| 1129 while (entry) { | |
| 1130 size_t slotIndex = (reinterpret_cast<char*>(entry) - ptr) / slotSize; | |
| 1131 ASSERT(slotIndex < numSlots); | |
| 1132 slotUsage[slotIndex] = 0; | |
| 1133 entry = partitionFreelistMask(entry->next); | |
| 1134 // If we have a slot where the masked freelist entry is 0, we can | |
| 1135 // actually discard that freelist entry because touching a discarded | |
| 1136 // page is guaranteed to return original content or 0. | |
| 1137 // (Note that this optimization won't fire on big endian machines | |
| 1138 // because the masking function is negation.) | |
| 1139 if (!partitionFreelistMask(entry)) | |
| 1140 lastSlot = slotIndex; | |
| 1141 } | |
| 1142 | |
| 1143 // If the slot(s) at the end of the slot span are not in used, we can | |
| 1144 // truncate them entirely and rewrite the freelist. | |
| 1145 size_t truncatedSlots = 0; | |
| 1146 while (!slotUsage[numSlots - 1]) { | |
| 1147 truncatedSlots++; | |
| 1148 numSlots--; | |
| 1149 ASSERT(numSlots); | |
| 1150 } | |
| 1151 // First, do the work of calculating the discardable bytes. Don't actually | |
| 1152 // discard anything unless the discard flag was passed in. | |
| 1153 char* beginPtr = nullptr; | |
| 1154 char* endPtr = nullptr; | |
| 1155 size_t unprovisionedBytes = 0; | |
| 1156 if (truncatedSlots) { | |
| 1157 beginPtr = ptr + (numSlots * slotSize); | |
| 1158 endPtr = beginPtr + (slotSize * truncatedSlots); | |
| 1159 beginPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterp
ret_cast<size_t>(beginPtr))); | |
| 1160 // We round the end pointer here up and not down because we're at the | |
| 1161 // end of a slot span, so we "own" all the way up the page boundary. | |
| 1162 endPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpre
t_cast<size_t>(endPtr))); | |
| 1163 ASSERT(endPtr <= ptr + partitionBucketBytes(bucket)); | |
| 1164 if (beginPtr < endPtr) { | |
| 1165 unprovisionedBytes = endPtr - beginPtr; | |
| 1166 discardableBytes += unprovisionedBytes; | |
| 1167 } | |
| 1168 } | |
| 1169 if (unprovisionedBytes && discard) { | |
| 1170 ASSERT(truncatedSlots > 0); | |
| 1171 size_t numNewEntries = 0; | |
| 1172 page->numUnprovisionedSlots += truncatedSlots; | |
| 1173 // Rewrite the freelist. | |
| 1174 PartitionFreelistEntry** entryPtr = &page->freelistHead; | |
| 1175 for (size_t slotIndex = 0; slotIndex < numSlots; ++slotIndex) { | |
| 1176 if (slotUsage[slotIndex]) | |
| 1177 continue; | |
| 1178 PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEn
try*>(ptr + (slotSize * slotIndex)); | |
| 1179 *entryPtr = partitionFreelistMask(entry); | |
| 1180 entryPtr = reinterpret_cast<PartitionFreelistEntry**>(entry); | |
| 1181 numNewEntries++; | |
| 1182 } | |
| 1183 // Terminate the freelist chain. | |
| 1184 *entryPtr = nullptr; | |
| 1185 // The freelist head is stored unmasked. | |
| 1186 page->freelistHead = partitionFreelistMask(page->freelistHead); | |
| 1187 ASSERT(numNewEntries == numSlots - page->numAllocatedSlots); | |
| 1188 // Discard the memory. | |
| 1189 discardSystemPages(beginPtr, unprovisionedBytes); | |
| 1190 } | |
| 1191 | |
| 1192 // Next, walk the slots and for any not in use, consider where the system | |
| 1193 // page boundaries occur. We can release any system pages back to the | |
| 1194 // system as long as we don't interfere with a freelist pointer or an | |
| 1195 // adjacent slot. | |
| 1196 for (size_t i = 0; i < numSlots; ++i) { | |
| 1197 if (slotUsage[i]) | |
| 1198 continue; | |
| 1199 // The first address we can safely discard is just after the freelist | |
| 1200 // pointer. There's one quirk: if the freelist pointer is actually a | |
| 1201 // null, we can discard that pointer value too. | |
| 1202 char* beginPtr = ptr + (i * slotSize); | |
| 1203 char* endPtr = beginPtr + slotSize; | |
| 1204 if (i != lastSlot) | |
| 1205 beginPtr += sizeof(PartitionFreelistEntry); | |
| 1206 beginPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterp
ret_cast<size_t>(beginPtr))); | |
| 1207 endPtr = reinterpret_cast<char*>(partitionRoundDownToSystemPage(reinterp
ret_cast<size_t>(endPtr))); | |
| 1208 if (beginPtr < endPtr) { | |
| 1209 size_t partialSlotBytes = endPtr - beginPtr; | |
| 1210 discardableBytes += partialSlotBytes; | |
| 1211 if (discard) | |
| 1212 discardSystemPages(beginPtr, partialSlotBytes); | |
| 1213 } | |
| 1214 } | 1071 } |
| 1215 return discardableBytes; | 1072 return discardableBytes; |
| 1216 } | 1073 } |
| 1217 | 1074 |
| 1218 static void partitionPurgeBucket(PartitionBucket* bucket) | 1075 const size_t maxSlotCount = (kPartitionPageSize * kMaxPartitionPagesPerSlotSpa
n) / kSystemPageSize; |
| 1219 { | 1076 ASSERT(bucketNumSlots <= maxSlotCount); |
| 1220 if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) { | 1077 ASSERT(page->numUnprovisionedSlots < bucketNumSlots); |
| 1221 for (PartitionPage* page = bucket->activePagesHead; page; page = page->n
extPage) { | 1078 size_t numSlots = bucketNumSlots - page->numUnprovisionedSlots; |
| 1222 ASSERT(page != &PartitionRootGeneric::gSeedPage); | 1079 char slotUsage[maxSlotCount]; |
| 1223 (void) partitionPurgePage(page, true); | 1080 size_t lastSlot = static_cast<size_t>(-1); |
| 1224 } | 1081 memset(slotUsage, 1, numSlots); |
| 1225 } | 1082 char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page)); |
| 1226 } | 1083 PartitionFreelistEntry* entry = page->freelistHead; |
| 1227 | 1084 // First, walk the freelist for this page and make a bitmap of which slots |
| 1228 void partitionPurgeMemory(PartitionRoot* root, int flags) | 1085 // are not in use. |
| 1229 { | 1086 while (entry) { |
| 1230 if (flags & PartitionPurgeDecommitEmptyPages) | 1087 size_t slotIndex = (reinterpret_cast<char*>(entry) - ptr) / slotSize; |
| 1231 partitionDecommitEmptyPages(root); | 1088 ASSERT(slotIndex < numSlots); |
| 1232 // We don't currently do anything for PartitionPurgeDiscardUnusedSystemPages | 1089 slotUsage[slotIndex] = 0; |
| 1233 // here because that flag is only useful for allocations >= system page | 1090 entry = partitionFreelistMask(entry->next); |
| 1234 // size. We only have allocations that large inside generic partitions | 1091 // If we have a slot where the masked freelist entry is 0, we can |
| 1235 // at the moment. | 1092 // actually discard that freelist entry because touching a discarded |
| 1236 } | 1093 // page is guaranteed to return original content or 0. |
| 1237 | 1094 // (Note that this optimization won't fire on big endian machines |
| 1238 void partitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags) | 1095 // because the masking function is negation.) |
| 1239 { | 1096 if (!partitionFreelistMask(entry)) |
| 1240 spinLockLock(&root->lock); | 1097 lastSlot = slotIndex; |
| 1241 if (flags & PartitionPurgeDecommitEmptyPages) | 1098 } |
| 1242 partitionDecommitEmptyPages(root); | 1099 |
| 1243 if (flags & PartitionPurgeDiscardUnusedSystemPages) { | 1100 // If the slot(s) at the end of the slot span are not in used, we can |
| 1244 for (size_t i = 0; i < kGenericNumBuckets; ++i) { | 1101 // truncate them entirely and rewrite the freelist. |
| 1245 PartitionBucket* bucket = &root->buckets[i]; | 1102 size_t truncatedSlots = 0; |
| 1246 if (bucket->slotSize >= kSystemPageSize) | 1103 while (!slotUsage[numSlots - 1]) { |
| 1247 partitionPurgeBucket(bucket); | 1104 truncatedSlots++; |
| 1248 } | 1105 numSlots--; |
| 1249 } | 1106 ASSERT(numSlots); |
| 1250 spinLockUnlock(&root->lock); | 1107 } |
| 1251 } | 1108 // First, do the work of calculating the discardable bytes. Don't actually |
| 1252 | 1109 // discard anything unless the discard flag was passed in. |
| 1253 static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, const P
artitionPage* page) | 1110 char* beginPtr = nullptr; |
| 1254 { | 1111 char* endPtr = nullptr; |
| 1255 uint16_t bucketNumSlots = partitionBucketSlots(page->bucket); | 1112 size_t unprovisionedBytes = 0; |
| 1256 | 1113 if (truncatedSlots) { |
| 1257 if (partitionPageStateIsDecommitted(page)) { | 1114 beginPtr = ptr + (numSlots * slotSize); |
| 1258 ++statsOut->numDecommittedPages; | 1115 endPtr = beginPtr + (slotSize * truncatedSlots); |
| 1259 return; | 1116 beginPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_
cast<size_t>(beginPtr))); |
| 1260 } | 1117 // We round the end pointer here up and not down because we're at the |
| 1261 | 1118 // end of a slot span, so we "own" all the way up the page boundary. |
| 1262 statsOut->discardableBytes += partitionPurgePage(const_cast<PartitionPage*>(
page), false); | 1119 endPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_ca
st<size_t>(endPtr))); |
| 1263 | 1120 ASSERT(endPtr <= ptr + partitionBucketBytes(bucket)); |
| 1264 size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page)); | 1121 if (beginPtr < endPtr) { |
| 1265 if (rawSize) | 1122 unprovisionedBytes = endPtr - beginPtr; |
| 1266 statsOut->activeBytes += static_cast<uint32_t>(rawSize); | 1123 discardableBytes += unprovisionedBytes; |
| 1124 } |
| 1125 } |
| 1126 if (unprovisionedBytes && discard) { |
| 1127 ASSERT(truncatedSlots > 0); |
| 1128 size_t numNewEntries = 0; |
| 1129 page->numUnprovisionedSlots += truncatedSlots; |
| 1130 // Rewrite the freelist. |
| 1131 PartitionFreelistEntry** entryPtr = &page->freelistHead; |
| 1132 for (size_t slotIndex = 0; slotIndex < numSlots; ++slotIndex) { |
| 1133 if (slotUsage[slotIndex]) |
| 1134 continue; |
| 1135 PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*>(
ptr + (slotSize * slotIndex)); |
| 1136 *entryPtr = partitionFreelistMask(entry); |
| 1137 entryPtr = reinterpret_cast<PartitionFreelistEntry**>(entry); |
| 1138 numNewEntries++; |
| 1139 } |
| 1140 // Terminate the freelist chain. |
| 1141 *entryPtr = nullptr; |
| 1142 // The freelist head is stored unmasked. |
| 1143 page->freelistHead = partitionFreelistMask(page->freelistHead); |
| 1144 ASSERT(numNewEntries == numSlots - page->numAllocatedSlots); |
| 1145 // Discard the memory. |
| 1146 discardSystemPages(beginPtr, unprovisionedBytes); |
| 1147 } |
| 1148 |
| 1149 // Next, walk the slots and for any not in use, consider where the system |
| 1150 // page boundaries occur. We can release any system pages back to the |
| 1151 // system as long as we don't interfere with a freelist pointer or an |
| 1152 // adjacent slot. |
| 1153 for (size_t i = 0; i < numSlots; ++i) { |
| 1154 if (slotUsage[i]) |
| 1155 continue; |
| 1156 // The first address we can safely discard is just after the freelist |
| 1157 // pointer. There's one quirk: if the freelist pointer is actually a |
| 1158 // null, we can discard that pointer value too. |
| 1159 char* beginPtr = ptr + (i * slotSize); |
| 1160 char* endPtr = beginPtr + slotSize; |
| 1161 if (i != lastSlot) |
| 1162 beginPtr += sizeof(PartitionFreelistEntry); |
| 1163 beginPtr = reinterpret_cast<char*>(partitionRoundUpToSystemPage(reinterpret_
cast<size_t>(beginPtr))); |
| 1164 endPtr = reinterpret_cast<char*>(partitionRoundDownToSystemPage(reinterpret_
cast<size_t>(endPtr))); |
| 1165 if (beginPtr < endPtr) { |
| 1166 size_t partialSlotBytes = endPtr - beginPtr; |
| 1167 discardableBytes += partialSlotBytes; |
| 1168 if (discard) |
| 1169 discardSystemPages(beginPtr, partialSlotBytes); |
| 1170 } |
| 1171 } |
| 1172 return discardableBytes; |
| 1173 } |
| 1174 |
| 1175 static void partitionPurgeBucket(PartitionBucket* bucket) { |
| 1176 if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) { |
| 1177 for (PartitionPage* page = bucket->activePagesHead; page; page = page->nextP
age) { |
| 1178 ASSERT(page != &PartitionRootGeneric::gSeedPage); |
| 1179 (void)partitionPurgePage(page, true); |
| 1180 } |
| 1181 } |
| 1182 } |
| 1183 |
| 1184 void partitionPurgeMemory(PartitionRoot* root, int flags) { |
| 1185 if (flags & PartitionPurgeDecommitEmptyPages) |
| 1186 partitionDecommitEmptyPages(root); |
| 1187 // We don't currently do anything for PartitionPurgeDiscardUnusedSystemPages |
| 1188 // here because that flag is only useful for allocations >= system page |
| 1189 // size. We only have allocations that large inside generic partitions |
| 1190 // at the moment. |
| 1191 } |
| 1192 |
| 1193 void partitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags) { |
| 1194 spinLockLock(&root->lock); |
| 1195 if (flags & PartitionPurgeDecommitEmptyPages) |
| 1196 partitionDecommitEmptyPages(root); |
| 1197 if (flags & PartitionPurgeDiscardUnusedSystemPages) { |
| 1198 for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
| 1199 PartitionBucket* bucket = &root->buckets[i]; |
| 1200 if (bucket->slotSize >= kSystemPageSize) |
| 1201 partitionPurgeBucket(bucket); |
| 1202 } |
| 1203 } |
| 1204 spinLockUnlock(&root->lock); |
| 1205 } |
| 1206 |
| 1207 static void partitionDumpPageStats(PartitionBucketMemoryStats* statsOut, const P
artitionPage* page) { |
| 1208 uint16_t bucketNumSlots = partitionBucketSlots(page->bucket); |
| 1209 |
| 1210 if (partitionPageStateIsDecommitted(page)) { |
| 1211 ++statsOut->numDecommittedPages; |
| 1212 return; |
| 1213 } |
| 1214 |
| 1215 statsOut->discardableBytes += partitionPurgePage(const_cast<PartitionPage*>(pa
ge), false); |
| 1216 |
| 1217 size_t rawSize = partitionPageGetRawSize(const_cast<PartitionPage*>(page)); |
| 1218 if (rawSize) |
| 1219 statsOut->activeBytes += static_cast<uint32_t>(rawSize); |
| 1220 else |
| 1221 statsOut->activeBytes += (page->numAllocatedSlots * statsOut->bucketSlotSize
); |
| 1222 |
| 1223 size_t pageBytesResident = partitionRoundUpToSystemPage((bucketNumSlots - page
->numUnprovisionedSlots) * statsOut->bucketSlotSize); |
| 1224 statsOut->residentBytes += pageBytesResident; |
| 1225 if (partitionPageStateIsEmpty(page)) { |
| 1226 statsOut->decommittableBytes += pageBytesResident; |
| 1227 ++statsOut->numEmptyPages; |
| 1228 } else if (partitionPageStateIsFull(page)) { |
| 1229 ++statsOut->numFullPages; |
| 1230 } else { |
| 1231 ASSERT(partitionPageStateIsActive(page)); |
| 1232 ++statsOut->numActivePages; |
| 1233 } |
| 1234 } |
| 1235 |
| 1236 static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, const
PartitionBucket* bucket) { |
| 1237 ASSERT(!partitionBucketIsDirectMapped(bucket)); |
| 1238 statsOut->isValid = false; |
| 1239 // If the active page list is empty (== &PartitionRootGeneric::gSeedPage), |
| 1240 // the bucket might still need to be reported if it has a list of empty, |
| 1241 // decommitted or full pages. |
| 1242 if (bucket->activePagesHead == &PartitionRootGeneric::gSeedPage && !bucket->em
ptyPagesHead && !bucket->decommittedPagesHead && !bucket->numFullPages) |
| 1243 return; |
| 1244 |
| 1245 memset(statsOut, '\0', sizeof(*statsOut)); |
| 1246 statsOut->isValid = true; |
| 1247 statsOut->isDirectMap = false; |
| 1248 statsOut->numFullPages = static_cast<size_t>(bucket->numFullPages); |
| 1249 statsOut->bucketSlotSize = bucket->slotSize; |
| 1250 uint16_t bucketNumSlots = partitionBucketSlots(bucket); |
| 1251 size_t bucketUsefulStorage = statsOut->bucketSlotSize * bucketNumSlots; |
| 1252 statsOut->allocatedPageSize = partitionBucketBytes(bucket); |
| 1253 statsOut->activeBytes = bucket->numFullPages * bucketUsefulStorage; |
| 1254 statsOut->residentBytes = bucket->numFullPages * statsOut->allocatedPageSize; |
| 1255 |
| 1256 for (const PartitionPage* page = bucket->emptyPagesHead; page; page = page->ne
xtPage) { |
| 1257 ASSERT(partitionPageStateIsEmpty(page) || partitionPageStateIsDecommitted(pa
ge)); |
| 1258 partitionDumpPageStats(statsOut, page); |
| 1259 } |
| 1260 for (const PartitionPage* page = bucket->decommittedPagesHead; page; page = pa
ge->nextPage) { |
| 1261 ASSERT(partitionPageStateIsDecommitted(page)); |
| 1262 partitionDumpPageStats(statsOut, page); |
| 1263 } |
| 1264 |
| 1265 if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) { |
| 1266 for (const PartitionPage* page = bucket->activePagesHead; page; page = page-
>nextPage) { |
| 1267 ASSERT(page != &PartitionRootGeneric::gSeedPage); |
| 1268 partitionDumpPageStats(statsOut, page); |
| 1269 } |
| 1270 } |
| 1271 } |
| 1272 |
| 1273 void partitionDumpStatsGeneric(PartitionRootGeneric* partition, const char* part
itionName, bool isLightDump, PartitionStatsDumper* partitionStatsDumper) { |
| 1274 PartitionBucketMemoryStats bucketStats[kGenericNumBuckets]; |
| 1275 static const size_t kMaxReportableDirectMaps = 4096; |
| 1276 uint32_t directMapLengths[kMaxReportableDirectMaps]; |
| 1277 size_t numDirectMappedAllocations = 0; |
| 1278 |
| 1279 spinLockLock(&partition->lock); |
| 1280 |
| 1281 for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
| 1282 const PartitionBucket* bucket = &partition->buckets[i]; |
| 1283 // Don't report the pseudo buckets that the generic allocator sets up in |
| 1284 // order to preserve a fast size->bucket map (see |
| 1285 // partitionAllocGenericInit for details). |
| 1286 if (!bucket->activePagesHead) |
| 1287 bucketStats[i].isValid = false; |
| 1267 else | 1288 else |
| 1268 statsOut->activeBytes += (page->numAllocatedSlots * statsOut->bucketSlot
Size); | 1289 partitionDumpBucketStats(&bucketStats[i], bucket); |
| 1269 | 1290 } |
| 1270 size_t pageBytesResident = partitionRoundUpToSystemPage((bucketNumSlots - pa
ge->numUnprovisionedSlots) * statsOut->bucketSlotSize); | 1291 |
| 1271 statsOut->residentBytes += pageBytesResident; | 1292 for (PartitionDirectMapExtent* extent = partition->directMapList; extent; exte
nt = extent->nextExtent) { |
| 1272 if (partitionPageStateIsEmpty(page)) { | 1293 ASSERT(!extent->nextExtent || extent->nextExtent->prevExtent == extent); |
| 1273 statsOut->decommittableBytes += pageBytesResident; | 1294 directMapLengths[numDirectMappedAllocations] = extent->bucket->slotSize; |
| 1274 ++statsOut->numEmptyPages; | 1295 ++numDirectMappedAllocations; |
| 1275 } else if (partitionPageStateIsFull(page)) { | 1296 if (numDirectMappedAllocations == kMaxReportableDirectMaps) |
| 1276 ++statsOut->numFullPages; | 1297 break; |
| 1277 } else { | 1298 } |
| 1278 ASSERT(partitionPageStateIsActive(page)); | 1299 |
| 1279 ++statsOut->numActivePages; | 1300 spinLockUnlock(&partition->lock); |
| 1280 } | 1301 |
| 1281 } | 1302 // partitionsDumpBucketStats is called after collecting stats because it |
| 1282 | 1303 // can try to allocate using PartitionAllocGeneric and it can't obtain the |
| 1283 static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, const
PartitionBucket* bucket) | 1304 // lock. |
| 1284 { | 1305 PartitionMemoryStats partitionStats = {0}; |
| 1285 ASSERT(!partitionBucketIsDirectMapped(bucket)); | 1306 partitionStats.totalMmappedBytes = partition->totalSizeOfSuperPages + partitio
n->totalSizeOfDirectMappedPages; |
| 1286 statsOut->isValid = false; | 1307 partitionStats.totalCommittedBytes = partition->totalSizeOfCommittedPages; |
| 1287 // If the active page list is empty (== &PartitionRootGeneric::gSeedPage), | 1308 for (size_t i = 0; i < kGenericNumBuckets; ++i) { |
| 1288 // the bucket might still need to be reported if it has a list of empty, | 1309 if (bucketStats[i].isValid) { |
| 1289 // decommitted or full pages. | 1310 partitionStats.totalResidentBytes += bucketStats[i].residentBytes; |
| 1290 if (bucket->activePagesHead == &PartitionRootGeneric::gSeedPage && !bucket->
emptyPagesHead && !bucket->decommittedPagesHead && !bucket->numFullPages) | 1311 partitionStats.totalActiveBytes += bucketStats[i].activeBytes; |
| 1291 return; | 1312 partitionStats.totalDecommittableBytes += bucketStats[i].decommittableByte
s; |
| 1292 | 1313 partitionStats.totalDiscardableBytes += bucketStats[i].discardableBytes; |
| 1293 memset(statsOut, '\0', sizeof(*statsOut)); | 1314 if (!isLightDump) |
| 1294 statsOut->isValid = true; | 1315 partitionStatsDumper->partitionsDumpBucketStats(partitionName, &bucketSt
ats[i]); |
| 1295 statsOut->isDirectMap = false; | 1316 } |
| 1296 statsOut->numFullPages = static_cast<size_t>(bucket->numFullPages); | 1317 } |
| 1297 statsOut->bucketSlotSize = bucket->slotSize; | 1318 |
| 1298 uint16_t bucketNumSlots = partitionBucketSlots(bucket); | 1319 size_t directMappedAllocationsTotalSize = 0; |
| 1299 size_t bucketUsefulStorage = statsOut->bucketSlotSize * bucketNumSlots; | 1320 for (size_t i = 0; i < numDirectMappedAllocations; ++i) { |
| 1300 statsOut->allocatedPageSize = partitionBucketBytes(bucket); | 1321 PartitionBucketMemoryStats stats; |
| 1301 statsOut->activeBytes = bucket->numFullPages * bucketUsefulStorage; | 1322 memset(&stats, '\0', sizeof(stats)); |
| 1302 statsOut->residentBytes = bucket->numFullPages * statsOut->allocatedPageSize
; | 1323 stats.isValid = true; |
| 1303 | 1324 stats.isDirectMap = true; |
| 1304 for (const PartitionPage* page = bucket->emptyPagesHead; page; page = page->
nextPage) { | 1325 stats.numFullPages = 1; |
| 1305 ASSERT(partitionPageStateIsEmpty(page) || partitionPageStateIsDecommitte
d(page)); | 1326 uint32_t size = directMapLengths[i]; |
| 1306 partitionDumpPageStats(statsOut, page); | 1327 stats.allocatedPageSize = size; |
| 1307 } | 1328 stats.bucketSlotSize = size; |
| 1308 for (const PartitionPage* page = bucket->decommittedPagesHead; page; page =
page->nextPage) { | 1329 stats.activeBytes = size; |
| 1309 ASSERT(partitionPageStateIsDecommitted(page)); | 1330 stats.residentBytes = size; |
| 1310 partitionDumpPageStats(statsOut, page); | 1331 directMappedAllocationsTotalSize += size; |
| 1311 } | 1332 partitionStatsDumper->partitionsDumpBucketStats(partitionName, &stats); |
| 1312 | 1333 } |
| 1313 if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) { | 1334 partitionStats.totalResidentBytes += directMappedAllocationsTotalSize; |
| 1314 for (const PartitionPage* page = bucket->activePagesHead; page; page = p
age->nextPage) { | 1335 partitionStats.totalActiveBytes += directMappedAllocationsTotalSize; |
| 1315 ASSERT(page != &PartitionRootGeneric::gSeedPage); | 1336 partitionStatsDumper->partitionDumpTotals(partitionName, &partitionStats); |
| 1316 partitionDumpPageStats(statsOut, page); | 1337 } |
| 1317 } | 1338 |
| 1318 } | 1339 void partitionDumpStats(PartitionRoot* partition, const char* partitionName, boo
l isLightDump, PartitionStatsDumper* partitionStatsDumper) { |
| 1319 } | 1340 static const size_t kMaxReportableBuckets = 4096 / sizeof(void*); |
| 1320 | 1341 PartitionBucketMemoryStats memoryStats[kMaxReportableBuckets]; |
| 1321 void partitionDumpStatsGeneric(PartitionRootGeneric* partition, const char* part
itionName, bool isLightDump, PartitionStatsDumper* partitionStatsDumper) | 1342 const size_t partitionNumBuckets = partition->numBuckets; |
| 1322 { | 1343 ASSERT(partitionNumBuckets <= kMaxReportableBuckets); |
| 1323 PartitionBucketMemoryStats bucketStats[kGenericNumBuckets]; | 1344 |
| 1324 static const size_t kMaxReportableDirectMaps = 4096; | 1345 for (size_t i = 0; i < partitionNumBuckets; ++i) |
| 1325 uint32_t directMapLengths[kMaxReportableDirectMaps]; | 1346 partitionDumpBucketStats(&memoryStats[i], &partition->buckets()[i]); |
| 1326 size_t numDirectMappedAllocations = 0; | 1347 |
| 1327 | 1348 // partitionsDumpBucketStats is called after collecting stats because it |
| 1328 spinLockLock(&partition->lock); | 1349 // can use PartitionAlloc to allocate and this can affect the statistics. |
| 1329 | 1350 PartitionMemoryStats partitionStats = {0}; |
| 1330 for (size_t i = 0; i < kGenericNumBuckets; ++i) { | 1351 partitionStats.totalMmappedBytes = partition->totalSizeOfSuperPages; |
| 1331 const PartitionBucket* bucket = &partition->buckets[i]; | 1352 partitionStats.totalCommittedBytes = partition->totalSizeOfCommittedPages; |
| 1332 // Don't report the pseudo buckets that the generic allocator sets up in | 1353 ASSERT(!partition->totalSizeOfDirectMappedPages); |
| 1333 // order to preserve a fast size->bucket map (see | 1354 for (size_t i = 0; i < partitionNumBuckets; ++i) { |
| 1334 // partitionAllocGenericInit for details). | 1355 if (memoryStats[i].isValid) { |
| 1335 if (!bucket->activePagesHead) | 1356 partitionStats.totalResidentBytes += memoryStats[i].residentBytes; |
| 1336 bucketStats[i].isValid = false; | 1357 partitionStats.totalActiveBytes += memoryStats[i].activeBytes; |
| 1337 else | 1358 partitionStats.totalDecommittableBytes += memoryStats[i].decommittableByte
s; |
| 1338 partitionDumpBucketStats(&bucketStats[i], bucket); | 1359 partitionStats.totalDiscardableBytes += memoryStats[i].discardableBytes; |
| 1339 } | 1360 if (!isLightDump) |
| 1340 | 1361 partitionStatsDumper->partitionsDumpBucketStats(partitionName, &memorySt
ats[i]); |
| 1341 for (PartitionDirectMapExtent* extent = partition->directMapList; extent; ex
tent = extent->nextExtent) { | 1362 } |
| 1342 ASSERT(!extent->nextExtent || extent->nextExtent->prevExtent == extent); | 1363 } |
| 1343 directMapLengths[numDirectMappedAllocations] = extent->bucket->slotSize; | 1364 partitionStatsDumper->partitionDumpTotals(partitionName, &partitionStats); |
| 1344 ++numDirectMappedAllocations; | 1365 } |
| 1345 if (numDirectMappedAllocations == kMaxReportableDirectMaps) | 1366 |
| 1346 break; | 1367 } // namespace WTF |
| 1347 } | |
| 1348 | |
| 1349 spinLockUnlock(&partition->lock); | |
| 1350 | |
| 1351 // partitionsDumpBucketStats is called after collecting stats because it | |
| 1352 // can try to allocate using PartitionAllocGeneric and it can't obtain the | |
| 1353 // lock. | |
| 1354 PartitionMemoryStats partitionStats = { 0 }; | |
| 1355 partitionStats.totalMmappedBytes = partition->totalSizeOfSuperPages + partit
ion->totalSizeOfDirectMappedPages; | |
| 1356 partitionStats.totalCommittedBytes = partition->totalSizeOfCommittedPages; | |
| 1357 for (size_t i = 0; i < kGenericNumBuckets; ++i) { | |
| 1358 if (bucketStats[i].isValid) { | |
| 1359 partitionStats.totalResidentBytes += bucketStats[i].residentBytes; | |
| 1360 partitionStats.totalActiveBytes += bucketStats[i].activeBytes; | |
| 1361 partitionStats.totalDecommittableBytes += bucketStats[i].decommittab
leBytes; | |
| 1362 partitionStats.totalDiscardableBytes += bucketStats[i].discardableBy
tes; | |
| 1363 if (!isLightDump) | |
| 1364 partitionStatsDumper->partitionsDumpBucketStats(partitionName, &
bucketStats[i]); | |
| 1365 } | |
| 1366 } | |
| 1367 | |
| 1368 size_t directMappedAllocationsTotalSize = 0; | |
| 1369 for (size_t i = 0; i < numDirectMappedAllocations; ++i) { | |
| 1370 PartitionBucketMemoryStats stats; | |
| 1371 memset(&stats, '\0', sizeof(stats)); | |
| 1372 stats.isValid = true; | |
| 1373 stats.isDirectMap = true; | |
| 1374 stats.numFullPages = 1; | |
| 1375 uint32_t size = directMapLengths[i]; | |
| 1376 stats.allocatedPageSize = size; | |
| 1377 stats.bucketSlotSize = size; | |
| 1378 stats.activeBytes = size; | |
| 1379 stats.residentBytes = size; | |
| 1380 directMappedAllocationsTotalSize += size; | |
| 1381 partitionStatsDumper->partitionsDumpBucketStats(partitionName, &stats); | |
| 1382 } | |
| 1383 partitionStats.totalResidentBytes += directMappedAllocationsTotalSize; | |
| 1384 partitionStats.totalActiveBytes += directMappedAllocationsTotalSize; | |
| 1385 partitionStatsDumper->partitionDumpTotals(partitionName, &partitionStats); | |
| 1386 } | |
| 1387 | |
| 1388 void partitionDumpStats(PartitionRoot* partition, const char* partitionName, boo
l isLightDump, PartitionStatsDumper* partitionStatsDumper) | |
| 1389 { | |
| 1390 static const size_t kMaxReportableBuckets = 4096 / sizeof(void*); | |
| 1391 PartitionBucketMemoryStats memoryStats[kMaxReportableBuckets]; | |
| 1392 const size_t partitionNumBuckets = partition->numBuckets; | |
| 1393 ASSERT(partitionNumBuckets <= kMaxReportableBuckets); | |
| 1394 | |
| 1395 for (size_t i = 0; i < partitionNumBuckets; ++i) | |
| 1396 partitionDumpBucketStats(&memoryStats[i], &partition->buckets()[i]); | |
| 1397 | |
| 1398 // partitionsDumpBucketStats is called after collecting stats because it | |
| 1399 // can use PartitionAlloc to allocate and this can affect the statistics. | |
| 1400 PartitionMemoryStats partitionStats = { 0 }; | |
| 1401 partitionStats.totalMmappedBytes = partition->totalSizeOfSuperPages; | |
| 1402 partitionStats.totalCommittedBytes = partition->totalSizeOfCommittedPages; | |
| 1403 ASSERT(!partition->totalSizeOfDirectMappedPages); | |
| 1404 for (size_t i = 0; i < partitionNumBuckets; ++i) { | |
| 1405 if (memoryStats[i].isValid) { | |
| 1406 partitionStats.totalResidentBytes += memoryStats[i].residentBytes; | |
| 1407 partitionStats.totalActiveBytes += memoryStats[i].activeBytes; | |
| 1408 partitionStats.totalDecommittableBytes += memoryStats[i].decommittab
leBytes; | |
| 1409 partitionStats.totalDiscardableBytes += memoryStats[i].discardableBy
tes; | |
| 1410 if (!isLightDump) | |
| 1411 partitionStatsDumper->partitionsDumpBucketStats(partitionName, &
memoryStats[i]); | |
| 1412 } | |
| 1413 } | |
| 1414 partitionStatsDumper->partitionDumpTotals(partitionName, &partitionStats); | |
| 1415 } | |
| 1416 | |
| 1417 } // namespace WTF | |
| 1418 | |
| OLD | NEW |