Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(223)

Side by Side Diff: third_party/WebKit/Source/wtf/PartitionAlloc.cpp

Issue 1436153002: Apply clang-format with Chromium-style without column limit. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Created 5 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/wtf/PartitionAlloc.h ('k') | third_party/WebKit/Source/wtf/PartitionAllocTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698