1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "third_party/base/allocator/partition_allocator/partition_alloc.h"
6
7 #include <string.h>
8
9 #include <memory>
10 #include <type_traits>
11
12 #include "third_party/base/allocator/partition_allocator/partition_direct_map_extent.h"
13 #include "third_party/base/allocator/partition_allocator/partition_oom.h"
14 #include "third_party/base/allocator/partition_allocator/partition_page.h"
15 #include "third_party/base/allocator/partition_allocator/spin_lock.h"
16
17 namespace pdfium {
18 namespace base {
19
20 // Two partition pages are used as guard / metadata page so make sure the super
21 // page size is bigger.
22 static_assert(kPartitionPageSize * 4 <= kSuperPageSize, "ok super page size");
23 static_assert(!(kSuperPageSize % kPartitionPageSize), "ok super page multiple");
24 // Four system pages gives us room to hack out a still-guard-paged piece
25 // of metadata in the middle of a guard partition page.
26 static_assert(kSystemPageSize * 4 <= kPartitionPageSize,
27 "ok partition page size");
28 static_assert(!(kPartitionPageSize % kSystemPageSize),
29 "ok partition page multiple");
30 static_assert(sizeof(internal::PartitionPage) <= kPageMetadataSize,
31 "PartitionPage should not be too big");
32 static_assert(sizeof(internal::PartitionBucket) <= kPageMetadataSize,
33 "PartitionBucket should not be too big");
34 static_assert(sizeof(internal::PartitionSuperPageExtentEntry) <=
35 kPageMetadataSize,
36 "PartitionSuperPageExtentEntry should not be too big");
37 static_assert(kPageMetadataSize * kNumPartitionPagesPerSuperPage <=
38 kSystemPageSize,
39 "page metadata fits in hole");
40 // Limit to prevent callers accidentally overflowing an int size.
41 static_assert(kGenericMaxDirectMapped <=
42 (1UL << 31) + kPageAllocationGranularity,
43 "maximum direct mapped allocation");
44 // Check that some of our zanier calculations worked out as expected.
45 static_assert(kGenericSmallestBucket == 8, "generic smallest bucket");
46 static_assert(kGenericMaxBucketed == 983040, "generic max bucketed");
47 static_assert(kMaxSystemPagesPerSlotSpan < (1 << 8),
48 "System pages per slot span must be less than 128.");
49
50 internal::PartitionRootBase::PartitionRootBase() = default;
51 internal::PartitionRootBase::~PartitionRootBase() = default;
52 PartitionRoot::PartitionRoot() = default;
53 PartitionRoot::~PartitionRoot() = default;
54 PartitionRootGeneric::PartitionRootGeneric() = default;
55 PartitionRootGeneric::~PartitionRootGeneric() = default;
56 PartitionAllocatorGeneric::PartitionAllocatorGeneric() = default;
57 PartitionAllocatorGeneric::~PartitionAllocatorGeneric() = default;
58
GetLock()59 subtle::SpinLock* GetLock() {
60 static subtle::SpinLock* s_initialized_lock = nullptr;
61 if (!s_initialized_lock)
62 s_initialized_lock = new subtle::SpinLock();
63 return s_initialized_lock;
64 }
65
66 static bool g_initialized = false;
67
68 void (*internal::PartitionRootBase::gOomHandlingFunction)() = nullptr;
69 std::atomic<bool> PartitionAllocHooks::hooks_enabled_(false);
70 subtle::SpinLock PartitionAllocHooks::set_hooks_lock_;
71 std::atomic<PartitionAllocHooks::AllocationObserverHook*>
72 PartitionAllocHooks::allocation_observer_hook_(nullptr);
73 std::atomic<PartitionAllocHooks::FreeObserverHook*>
74 PartitionAllocHooks::free_observer_hook_(nullptr);
75 std::atomic<PartitionAllocHooks::AllocationOverrideHook*>
76 PartitionAllocHooks::allocation_override_hook_(nullptr);
77 std::atomic<PartitionAllocHooks::FreeOverrideHook*>
78 PartitionAllocHooks::free_override_hook_(nullptr);
79 std::atomic<PartitionAllocHooks::ReallocOverrideHook*>
80 PartitionAllocHooks::realloc_override_hook_(nullptr);
81
SetObserverHooks(AllocationObserverHook * alloc_hook,FreeObserverHook * free_hook)82 void PartitionAllocHooks::SetObserverHooks(AllocationObserverHook* alloc_hook,
83 FreeObserverHook* free_hook) {
84 subtle::SpinLock::Guard guard(set_hooks_lock_);
85
86 // Chained hooks are not supported. Registering a non-null hook when a
87 // non-null hook is already registered indicates somebody is trying to
88 // overwrite a hook.
89 CHECK((!allocation_observer_hook_ && !free_observer_hook_) ||
90 (!alloc_hook && !free_hook));
91 allocation_observer_hook_ = alloc_hook;
92 free_observer_hook_ = free_hook;
93
94 hooks_enabled_ = allocation_observer_hook_ || allocation_override_hook_;
95 }
96
SetOverrideHooks(AllocationOverrideHook * alloc_hook,FreeOverrideHook * free_hook,ReallocOverrideHook realloc_hook)97 void PartitionAllocHooks::SetOverrideHooks(AllocationOverrideHook* alloc_hook,
98 FreeOverrideHook* free_hook,
99 ReallocOverrideHook realloc_hook) {
100 subtle::SpinLock::Guard guard(set_hooks_lock_);
101
102 CHECK((!allocation_override_hook_ && !free_override_hook_ &&
103 !realloc_override_hook_) ||
104 (!alloc_hook && !free_hook && !realloc_hook));
105 allocation_override_hook_ = alloc_hook;
106 free_override_hook_ = free_hook;
107 realloc_override_hook_ = realloc_hook;
108
109 hooks_enabled_ = allocation_observer_hook_ || allocation_override_hook_;
110 }
111
AllocationObserverHookIfEnabled(void * address,size_t size,const char * type_name)112 void PartitionAllocHooks::AllocationObserverHookIfEnabled(
113 void* address,
114 size_t size,
115 const char* type_name) {
116 if (AllocationObserverHook* hook =
117 allocation_observer_hook_.load(std::memory_order_relaxed)) {
118 hook(address, size, type_name);
119 }
120 }
121
AllocationOverrideHookIfEnabled(void ** out,int flags,size_t size,const char * type_name)122 bool PartitionAllocHooks::AllocationOverrideHookIfEnabled(
123 void** out,
124 int flags,
125 size_t size,
126 const char* type_name) {
127 if (AllocationOverrideHook* hook =
128 allocation_override_hook_.load(std::memory_order_relaxed)) {
129 return hook(out, flags, size, type_name);
130 }
131 return false;
132 }
133
FreeObserverHookIfEnabled(void * address)134 void PartitionAllocHooks::FreeObserverHookIfEnabled(void* address) {
135 if (FreeObserverHook* hook =
136 free_observer_hook_.load(std::memory_order_relaxed)) {
137 hook(address);
138 }
139 }
140
FreeOverrideHookIfEnabled(void * address)141 bool PartitionAllocHooks::FreeOverrideHookIfEnabled(void* address) {
142 if (FreeOverrideHook* hook =
143 free_override_hook_.load(std::memory_order_relaxed)) {
144 return hook(address);
145 }
146 return false;
147 }
148
ReallocObserverHookIfEnabled(void * old_address,void * new_address,size_t size,const char * type_name)149 void PartitionAllocHooks::ReallocObserverHookIfEnabled(void* old_address,
150 void* new_address,
151 size_t size,
152 const char* type_name) {
153 // Report a reallocation as a free followed by an allocation.
154 AllocationObserverHook* allocation_hook =
155 allocation_observer_hook_.load(std::memory_order_relaxed);
156 FreeObserverHook* free_hook =
157 free_observer_hook_.load(std::memory_order_relaxed);
158 if (allocation_hook && free_hook) {
159 free_hook(old_address);
160 allocation_hook(new_address, size, type_name);
161 }
162 }
ReallocOverrideHookIfEnabled(size_t * out,void * address)163 bool PartitionAllocHooks::ReallocOverrideHookIfEnabled(size_t* out,
164 void* address) {
165 if (ReallocOverrideHook* hook =
166 realloc_override_hook_.load(std::memory_order_relaxed)) {
167 return hook(out, address);
168 }
169 return false;
170 }
171
PartitionAllocBaseInit(internal::PartitionRootBase * root)172 static void PartitionAllocBaseInit(internal::PartitionRootBase* root) {
173 DCHECK(!root->initialized);
174 {
175 subtle::SpinLock::Guard guard(*GetLock());
176 if (!g_initialized) {
177 g_initialized = true;
178 // We mark the sentinel bucket/page as free to make sure it is skipped by
179 // our logic to find a new active page.
180 internal::PartitionBucket::get_sentinel_bucket()->active_pages_head =
181 internal::PartitionPage::get_sentinel_page();
182 }
183 }
184
185 root->initialized = true;
186
187 // This is a "magic" value so we can test if a root pointer is valid.
188 root->inverted_self = ~reinterpret_cast<uintptr_t>(root);
189 }
190
PartitionAllocGlobalInit(void (* oom_handling_function)())191 void PartitionAllocGlobalInit(void (*oom_handling_function)()) {
192 DCHECK(oom_handling_function);
193 internal::PartitionRootBase::gOomHandlingFunction = oom_handling_function;
194 }
195
Init(size_t bucket_count,size_t maximum_allocation)196 void PartitionRoot::Init(size_t bucket_count, size_t maximum_allocation) {
197 PartitionAllocBaseInit(this);
198
199 num_buckets = bucket_count;
200 max_allocation = maximum_allocation;
201 for (size_t i = 0; i < num_buckets; ++i) {
202 internal::PartitionBucket& bucket = buckets()[i];
203 bucket.Init(i == 0 ? kAllocationGranularity : (i << kBucketShift));
204 }
205 }
206
Init()207 void PartitionRootGeneric::Init() {
208 subtle::SpinLock::Guard guard(lock);
209
210 PartitionAllocBaseInit(this);
211
212 // Precalculate some shift and mask constants used in the hot path.
213 // Example: malloc(41) == 101001 binary.
214 // Order is 6 (1 << 6-1) == 32 is highest bit set.
215 // order_index is the next three MSB == 010 == 2.
216 // sub_order_index_mask is a mask for the remaining bits == 11 (masking to 01
217 // for
218 // the sub_order_index).
219 size_t order;
220 for (order = 0; order <= kBitsPerSizeT; ++order) {
221 size_t order_index_shift;
222 if (order < kGenericNumBucketsPerOrderBits + 1)
223 order_index_shift = 0;
224 else
225 order_index_shift = order - (kGenericNumBucketsPerOrderBits + 1);
226 order_index_shifts[order] = order_index_shift;
227 size_t sub_order_index_mask;
228 if (order == kBitsPerSizeT) {
229 // This avoids invoking undefined behavior for an excessive shift.
230 sub_order_index_mask =
231 static_cast<size_t>(-1) >> (kGenericNumBucketsPerOrderBits + 1);
232 } else {
233 sub_order_index_mask = ((static_cast<size_t>(1) << order) - 1) >>
234 (kGenericNumBucketsPerOrderBits + 1);
235 }
236 order_sub_index_masks[order] = sub_order_index_mask;
237 }
238
239 // Set up the actual usable buckets first.
240 // Note that typical values (i.e. min allocation size of 8) will result in
241 // pseudo buckets (size==9 etc. or more generally, size is not a multiple
242 // of the smallest allocation granularity).
243 // We avoid them in the bucket lookup map, but we tolerate them to keep the
244 // code simpler and the structures more generic.
245 size_t i, j;
246 size_t current_size = kGenericSmallestBucket;
247 size_t current_increment =
248 kGenericSmallestBucket >> kGenericNumBucketsPerOrderBits;
249 internal::PartitionBucket* bucket = &buckets[0];
250 for (i = 0; i < kGenericNumBucketedOrders; ++i) {
251 for (j = 0; j < kGenericNumBucketsPerOrder; ++j) {
252 bucket->Init(current_size);
253 // Disable psuedo buckets so that touching them faults.
254 if (current_size % kGenericSmallestBucket)
255 bucket->active_pages_head = nullptr;
256 current_size += current_increment;
257 ++bucket;
258 }
259 current_increment <<= 1;
260 }
261 DCHECK(current_size == 1 << kGenericMaxBucketedOrder);
262 DCHECK(bucket == &buckets[0] + kGenericNumBuckets);
263
264 // Then set up the fast size -> bucket lookup table.
265 bucket = &buckets[0];
266 internal::PartitionBucket** bucket_ptr = &bucket_lookups[0];
267 for (order = 0; order <= kBitsPerSizeT; ++order) {
268 for (j = 0; j < kGenericNumBucketsPerOrder; ++j) {
269 if (order < kGenericMinBucketedOrder) {
270 // Use the bucket of the finest granularity for malloc(0) etc.
271 *bucket_ptr++ = &buckets[0];
272 } else if (order > kGenericMaxBucketedOrder) {
273 *bucket_ptr++ = internal::PartitionBucket::get_sentinel_bucket();
274 } else {
275 internal::PartitionBucket* valid_bucket = bucket;
276 // Skip over invalid buckets.
277 while (valid_bucket->slot_size % kGenericSmallestBucket)
278 valid_bucket++;
279 *bucket_ptr++ = valid_bucket;
280 bucket++;
281 }
282 }
283 }
284 DCHECK(bucket == &buckets[0] + kGenericNumBuckets);
285 DCHECK(bucket_ptr == &bucket_lookups[0] +
286 ((kBitsPerSizeT + 1) * kGenericNumBucketsPerOrder));
287 // And there's one last bucket lookup that will be hit for e.g. malloc(-1),
288 // which tries to overflow to a non-existant order.
289 *bucket_ptr = internal::PartitionBucket::get_sentinel_bucket();
290 }
291
PartitionReallocDirectMappedInPlace(PartitionRootGeneric * root,internal::PartitionPage * page,size_t raw_size)292 bool PartitionReallocDirectMappedInPlace(PartitionRootGeneric* root,
293 internal::PartitionPage* page,
294 size_t raw_size) {
295 DCHECK(page->bucket->is_direct_mapped());
296
297 raw_size = internal::PartitionCookieSizeAdjustAdd(raw_size);
298
299 // Note that the new size might be a bucketed size; this function is called
300 // whenever we're reallocating a direct mapped allocation.
301 size_t new_size = internal::PartitionBucket::get_direct_map_size(raw_size);
302 if (new_size < kGenericMinDirectMappedDownsize)
303 return false;
304
305 // bucket->slot_size is the current size of the allocation.
306 size_t current_size = page->bucket->slot_size;
307 char* char_ptr = static_cast<char*>(internal::PartitionPage::ToPointer(page));
308 if (new_size == current_size) {
309 // No need to move any memory around, but update size and cookie below.
310 } else if (new_size < current_size) {
311 size_t map_size =
312 internal::PartitionDirectMapExtent::FromPage(page)->map_size;
313
314 // Don't reallocate in-place if new size is less than 80 % of the full
315 // map size, to avoid holding on to too much unused address space.
316 if ((new_size / kSystemPageSize) * 5 < (map_size / kSystemPageSize) * 4)
317 return false;
318
319 // Shrink by decommitting unneeded pages and making them inaccessible.
320 size_t decommit_size = current_size - new_size;
321 root->DecommitSystemPages(char_ptr + new_size, decommit_size);
322 SetSystemPagesAccess(char_ptr + new_size, decommit_size, PageInaccessible);
323 } else if (new_size <=
324 internal::PartitionDirectMapExtent::FromPage(page)->map_size) {
325 // Grow within the actually allocated memory. Just need to make the
326 // pages accessible again.
327 size_t recommit_size = new_size - current_size;
328 SetSystemPagesAccess(char_ptr + current_size, recommit_size, PageReadWrite);
329 root->RecommitSystemPages(char_ptr + current_size, recommit_size);
330
331 #if DCHECK_IS_ON()
332 memset(char_ptr + current_size, kUninitializedByte, recommit_size);
333 #endif
334 } else {
335 // We can't perform the realloc in-place.
336 // TODO: support this too when possible.
337 return false;
338 }
339
340 #if DCHECK_IS_ON()
341 // Write a new trailing cookie.
342 internal::PartitionCookieWriteValue(char_ptr + raw_size -
343 internal::kCookieSize);
344 #endif
345
346 page->set_raw_size(raw_size);
347 DCHECK(page->get_raw_size() == raw_size);
348
349 page->bucket->slot_size = new_size;
350 return true;
351 }
352
PartitionReallocGenericFlags(PartitionRootGeneric * root,int flags,void * ptr,size_t new_size,const char * type_name)353 void* PartitionReallocGenericFlags(PartitionRootGeneric* root,
354 int flags,
355 void* ptr,
356 size_t new_size,
357 const char* type_name) {
358 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
359 CHECK_MAX_SIZE_OR_RETURN_NULLPTR(new_size, flags);
360 void* result = realloc(ptr, new_size);
361 CHECK(result || flags & PartitionAllocReturnNull);
362 return result;
363 #else
364 if (UNLIKELY(!ptr))
365 return PartitionAllocGenericFlags(root, flags, new_size, type_name);
366 if (UNLIKELY(!new_size)) {
367 root->Free(ptr);
368 return nullptr;
369 }
370
371 if (new_size > kGenericMaxDirectMapped) {
372 if (flags & PartitionAllocReturnNull)
373 return nullptr;
374 internal::PartitionExcessiveAllocationSize();
375 }
376
377 const bool hooks_enabled = PartitionAllocHooks::AreHooksEnabled();
378 bool overridden = false;
379 size_t actual_old_size;
380 if (UNLIKELY(hooks_enabled)) {
381 overridden = PartitionAllocHooks::ReallocOverrideHookIfEnabled(
382 &actual_old_size, ptr);
383 }
384 if (LIKELY(!overridden)) {
385 internal::PartitionPage* page = internal::PartitionPage::FromPointer(
386 internal::PartitionCookieFreePointerAdjust(ptr));
387 // TODO(palmer): See if we can afford to make this a CHECK.
388 DCHECK(root->IsValidPage(page));
389
390 if (UNLIKELY(page->bucket->is_direct_mapped())) {
391 // We may be able to perform the realloc in place by changing the
392 // accessibility of memory pages and, if reducing the size, decommitting
393 // them.
394 if (PartitionReallocDirectMappedInPlace(root, page, new_size)) {
395 if (UNLIKELY(hooks_enabled)) {
396 PartitionAllocHooks::ReallocObserverHookIfEnabled(ptr, ptr, new_size,
397 type_name);
398 }
399 return ptr;
400 }
401 }
402
403 const size_t actual_new_size = root->ActualSize(new_size);
404 actual_old_size = PartitionAllocGetSize(ptr);
405
406 // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the
407 // new size is a significant percentage smaller. We could do the same if we
408 // determine it is a win.
409 if (actual_new_size == actual_old_size) {
410 // Trying to allocate a block of size |new_size| would give us a block of
411 // the same size as the one we've already got, so re-use the allocation
412 // after updating statistics (and cookies, if present).
413 page->set_raw_size(internal::PartitionCookieSizeAdjustAdd(new_size));
414 #if DCHECK_IS_ON()
415 // Write a new trailing cookie when it is possible to keep track of
416 // |new_size| via the raw size pointer.
417 if (page->get_raw_size_ptr())
418 internal::PartitionCookieWriteValue(static_cast<char*>(ptr) + new_size);
419 #endif
420 return ptr;
421 }
422 }
423
424 // This realloc cannot be resized in-place. Sadness.
425 void* ret = PartitionAllocGenericFlags(root, flags, new_size, type_name);
426 if (!ret) {
427 if (flags & PartitionAllocReturnNull)
428 return nullptr;
429 internal::PartitionExcessiveAllocationSize();
430 }
431
432 size_t copy_size = actual_old_size;
433 if (new_size < copy_size)
434 copy_size = new_size;
435
436 memcpy(ret, ptr, copy_size);
437 root->Free(ptr);
438 return ret;
439 #endif
440 }
441
Realloc(void * ptr,size_t new_size,const char * type_name)442 void* PartitionRootGeneric::Realloc(void* ptr,
443 size_t new_size,
444 const char* type_name) {
445 return PartitionReallocGenericFlags(this, 0, ptr, new_size, type_name);
446 }
447
TryRealloc(void * ptr,size_t new_size,const char * type_name)448 void* PartitionRootGeneric::TryRealloc(void* ptr,
449 size_t new_size,
450 const char* type_name) {
451 return PartitionReallocGenericFlags(this, PartitionAllocReturnNull, ptr,
452 new_size, type_name);
453 }
454
PartitionPurgePage(internal::PartitionPage * page,bool discard)455 static size_t PartitionPurgePage(internal::PartitionPage* page, bool discard) {
456 const internal::PartitionBucket* bucket = page->bucket;
457 size_t slot_size = bucket->slot_size;
458 if (slot_size < kSystemPageSize || !page->num_allocated_slots)
459 return 0;
460
461 size_t bucket_num_slots = bucket->get_slots_per_span();
462 size_t discardable_bytes = 0;
463
464 size_t raw_size = page->get_raw_size();
465 if (raw_size) {
466 uint32_t used_bytes = static_cast<uint32_t>(RoundUpToSystemPage(raw_size));
467 discardable_bytes = bucket->slot_size - used_bytes;
468 if (discardable_bytes && discard) {
469 char* ptr =
470 reinterpret_cast<char*>(internal::PartitionPage::ToPointer(page));
471 ptr += used_bytes;
472 DiscardSystemPages(ptr, discardable_bytes);
473 }
474 return discardable_bytes;
475 }
476
477 constexpr size_t kMaxSlotCount =
478 (kPartitionPageSize * kMaxPartitionPagesPerSlotSpan) / kSystemPageSize;
479 DCHECK(bucket_num_slots <= kMaxSlotCount);
480 DCHECK(page->num_unprovisioned_slots < bucket_num_slots);
481 size_t num_slots = bucket_num_slots - page->num_unprovisioned_slots;
482 char slot_usage[kMaxSlotCount];
483 #if !defined(OS_WIN)
484 // The last freelist entry should not be discarded when using OS_WIN.
485 // DiscardVirtualMemory makes the contents of discarded memory undefined.
486 size_t last_slot = static_cast<size_t>(-1);
487 #endif
488 memset(slot_usage, 1, num_slots);
489 char* ptr = reinterpret_cast<char*>(internal::PartitionPage::ToPointer(page));
490 // First, walk the freelist for this page and make a bitmap of which slots
491 // are not in use.
492 for (internal::PartitionFreelistEntry* entry = page->freelist_head; entry;
493 /**/) {
494 size_t slot_index = (reinterpret_cast<char*>(entry) - ptr) / slot_size;
495 DCHECK(slot_index < num_slots);
496 slot_usage[slot_index] = 0;
497 entry = internal::EncodedPartitionFreelistEntry::Decode(entry->next);
498 #if !defined(OS_WIN)
499 // If we have a slot where the masked freelist entry is 0, we can actually
500 // discard that freelist entry because touching a discarded page is
501 // guaranteed to return original content or 0. (Note that this optimization
502 // won't fire on big-endian machines because the masking function is
503 // negation.)
504 if (!internal::PartitionFreelistEntry::Encode(entry))
505 last_slot = slot_index;
506 #endif
507 }
508
509 // If the slot(s) at the end of the slot span are not in used, we can truncate
510 // them entirely and rewrite the freelist.
511 size_t truncated_slots = 0;
512 while (!slot_usage[num_slots - 1]) {
513 truncated_slots++;
514 num_slots--;
515 DCHECK(num_slots);
516 }
517 // First, do the work of calculating the discardable bytes. Don't actually
518 // discard anything unless the discard flag was passed in.
519 if (truncated_slots) {
520 size_t unprovisioned_bytes = 0;
521 char* begin_ptr = ptr + (num_slots * slot_size);
522 char* end_ptr = begin_ptr + (slot_size * truncated_slots);
523 begin_ptr = reinterpret_cast<char*>(
524 RoundUpToSystemPage(reinterpret_cast<size_t>(begin_ptr)));
525 // We round the end pointer here up and not down because we're at the end of
526 // a slot span, so we "own" all the way up the page boundary.
527 end_ptr = reinterpret_cast<char*>(
528 RoundUpToSystemPage(reinterpret_cast<size_t>(end_ptr)));
529 DCHECK(end_ptr <= ptr + bucket->get_bytes_per_span());
530 if (begin_ptr < end_ptr) {
531 unprovisioned_bytes = end_ptr - begin_ptr;
532 discardable_bytes += unprovisioned_bytes;
533 }
534 if (unprovisioned_bytes && discard) {
535 DCHECK(truncated_slots > 0);
536 size_t num_new_entries = 0;
537 page->num_unprovisioned_slots += static_cast<uint16_t>(truncated_slots);
538
539 // Rewrite the freelist.
540 internal::PartitionFreelistEntry* head = nullptr;
541 internal::PartitionFreelistEntry* back = head;
542 for (size_t slot_index = 0; slot_index < num_slots; ++slot_index) {
543 if (slot_usage[slot_index])
544 continue;
545
546 auto* entry = reinterpret_cast<internal::PartitionFreelistEntry*>(
547 ptr + (slot_size * slot_index));
548 if (!head) {
549 head = entry;
550 back = entry;
551 } else {
552 back->next = internal::PartitionFreelistEntry::Encode(entry);
553 back = entry;
554 }
555 num_new_entries++;
556 #if !defined(OS_WIN)
557 last_slot = slot_index;
558 #endif
559 }
560
561 page->freelist_head = head;
562 if (back)
563 back->next = internal::PartitionFreelistEntry::Encode(nullptr);
564
565 DCHECK(num_new_entries == num_slots - page->num_allocated_slots);
566 // Discard the memory.
567 DiscardSystemPages(begin_ptr, unprovisioned_bytes);
568 }
569 }
570
571 // Next, walk the slots and for any not in use, consider where the system page
572 // boundaries occur. We can release any system pages back to the system as
573 // long as we don't interfere with a freelist pointer or an adjacent slot.
574 for (size_t i = 0; i < num_slots; ++i) {
575 if (slot_usage[i])
576 continue;
577 // The first address we can safely discard is just after the freelist
578 // pointer. There's one quirk: if the freelist pointer is actually NULL, we
579 // can discard that pointer value too.
580 char* begin_ptr = ptr + (i * slot_size);
581 char* end_ptr = begin_ptr + slot_size;
582 #if !defined(OS_WIN)
583 if (i != last_slot)
584 begin_ptr += sizeof(internal::PartitionFreelistEntry);
585 #else
586 begin_ptr += sizeof(internal::PartitionFreelistEntry);
587 #endif
588 begin_ptr = reinterpret_cast<char*>(
589 RoundUpToSystemPage(reinterpret_cast<size_t>(begin_ptr)));
590 end_ptr = reinterpret_cast<char*>(
591 RoundDownToSystemPage(reinterpret_cast<size_t>(end_ptr)));
592 if (begin_ptr < end_ptr) {
593 size_t partial_slot_bytes = end_ptr - begin_ptr;
594 discardable_bytes += partial_slot_bytes;
595 if (discard)
596 DiscardSystemPages(begin_ptr, partial_slot_bytes);
597 }
598 }
599 return discardable_bytes;
600 }
601
PartitionPurgeBucket(internal::PartitionBucket * bucket)602 static void PartitionPurgeBucket(internal::PartitionBucket* bucket) {
603 if (bucket->active_pages_head !=
604 internal::PartitionPage::get_sentinel_page()) {
605 for (internal::PartitionPage* page = bucket->active_pages_head; page;
606 page = page->next_page) {
607 DCHECK(page != internal::PartitionPage::get_sentinel_page());
608 PartitionPurgePage(page, true);
609 }
610 }
611 }
612
PurgeMemory(int flags)613 void PartitionRoot::PurgeMemory(int flags) {
614 if (flags & PartitionPurgeDecommitEmptyPages)
615 DecommitEmptyPages();
616 // We don't currently do anything for PartitionPurgeDiscardUnusedSystemPages
617 // here because that flag is only useful for allocations >= system page size.
618 // We only have allocations that large inside generic partitions at the
619 // moment.
620 }
621
PurgeMemory(int flags)622 void PartitionRootGeneric::PurgeMemory(int flags) {
623 subtle::SpinLock::Guard guard(lock);
624 if (flags & PartitionPurgeDecommitEmptyPages)
625 DecommitEmptyPages();
626 if (flags & PartitionPurgeDiscardUnusedSystemPages) {
627 for (size_t i = 0; i < kGenericNumBuckets; ++i) {
628 internal::PartitionBucket* bucket = &buckets[i];
629 if (bucket->slot_size >= kSystemPageSize)
630 PartitionPurgeBucket(bucket);
631 }
632 }
633 }
634
PartitionDumpPageStats(PartitionBucketMemoryStats * stats_out,internal::PartitionPage * page)635 static void PartitionDumpPageStats(PartitionBucketMemoryStats* stats_out,
636 internal::PartitionPage* page) {
637 uint16_t bucket_num_slots = page->bucket->get_slots_per_span();
638
639 if (page->is_decommitted()) {
640 ++stats_out->num_decommitted_pages;
641 return;
642 }
643
644 stats_out->discardable_bytes += PartitionPurgePage(page, false);
645
646 size_t raw_size = page->get_raw_size();
647 if (raw_size) {
648 stats_out->active_bytes += static_cast<uint32_t>(raw_size);
649 } else {
650 stats_out->active_bytes +=
651 (page->num_allocated_slots * stats_out->bucket_slot_size);
652 }
653
654 size_t page_bytes_resident =
655 RoundUpToSystemPage((bucket_num_slots - page->num_unprovisioned_slots) *
656 stats_out->bucket_slot_size);
657 stats_out->resident_bytes += page_bytes_resident;
658 if (page->is_empty()) {
659 stats_out->decommittable_bytes += page_bytes_resident;
660 ++stats_out->num_empty_pages;
661 } else if (page->is_full()) {
662 ++stats_out->num_full_pages;
663 } else {
664 DCHECK(page->is_active());
665 ++stats_out->num_active_pages;
666 }
667 }
668
PartitionDumpBucketStats(PartitionBucketMemoryStats * stats_out,const internal::PartitionBucket * bucket)669 static void PartitionDumpBucketStats(PartitionBucketMemoryStats* stats_out,
670 const internal::PartitionBucket* bucket) {
671 DCHECK(!bucket->is_direct_mapped());
672 stats_out->is_valid = false;
673 // If the active page list is empty (==
674 // internal::PartitionPage::get_sentinel_page()), the bucket might still need
675 // to be reported if it has a list of empty, decommitted or full pages.
676 if (bucket->active_pages_head ==
677 internal::PartitionPage::get_sentinel_page() &&
678 !bucket->empty_pages_head && !bucket->decommitted_pages_head &&
679 !bucket->num_full_pages)
680 return;
681
682 memset(stats_out, '\0', sizeof(*stats_out));
683 stats_out->is_valid = true;
684 stats_out->is_direct_map = false;
685 stats_out->num_full_pages = static_cast<size_t>(bucket->num_full_pages);
686 stats_out->bucket_slot_size = bucket->slot_size;
687 uint16_t bucket_num_slots = bucket->get_slots_per_span();
688 size_t bucket_useful_storage = stats_out->bucket_slot_size * bucket_num_slots;
689 stats_out->allocated_page_size = bucket->get_bytes_per_span();
690 stats_out->active_bytes = bucket->num_full_pages * bucket_useful_storage;
691 stats_out->resident_bytes =
692 bucket->num_full_pages * stats_out->allocated_page_size;
693
694 for (internal::PartitionPage* page = bucket->empty_pages_head; page;
695 page = page->next_page) {
696 DCHECK(page->is_empty() || page->is_decommitted());
697 PartitionDumpPageStats(stats_out, page);
698 }
699 for (internal::PartitionPage* page = bucket->decommitted_pages_head; page;
700 page = page->next_page) {
701 DCHECK(page->is_decommitted());
702 PartitionDumpPageStats(stats_out, page);
703 }
704
705 if (bucket->active_pages_head !=
706 internal::PartitionPage::get_sentinel_page()) {
707 for (internal::PartitionPage* page = bucket->active_pages_head; page;
708 page = page->next_page) {
709 DCHECK(page != internal::PartitionPage::get_sentinel_page());
710 PartitionDumpPageStats(stats_out, page);
711 }
712 }
713 }
714
DumpStats(const char * partition_name,bool is_light_dump,PartitionStatsDumper * dumper)715 void PartitionRootGeneric::DumpStats(const char* partition_name,
716 bool is_light_dump,
717 PartitionStatsDumper* dumper) {
718 PartitionMemoryStats stats = {0};
719 stats.total_mmapped_bytes =
720 total_size_of_super_pages + total_size_of_direct_mapped_pages;
721 stats.total_committed_bytes = total_size_of_committed_pages;
722
723 size_t direct_mapped_allocations_total_size = 0;
724
725 static const size_t kMaxReportableDirectMaps = 4096;
726
727 // Allocate on the heap rather than on the stack to avoid stack overflow
728 // skirmishes (on Windows, in particular).
729 std::unique_ptr<uint32_t[]> direct_map_lengths = nullptr;
730 if (!is_light_dump) {
731 direct_map_lengths =
732 std::unique_ptr<uint32_t[]>(new uint32_t[kMaxReportableDirectMaps]);
733 }
734
735 PartitionBucketMemoryStats bucket_stats[kGenericNumBuckets];
736 size_t num_direct_mapped_allocations = 0;
737 {
738 subtle::SpinLock::Guard guard(lock);
739
740 for (size_t i = 0; i < kGenericNumBuckets; ++i) {
741 const internal::PartitionBucket* bucket = &buckets[i];
742 // Don't report the pseudo buckets that the generic allocator sets up in
743 // order to preserve a fast size->bucket map (see
744 // PartitionRootGeneric::Init() for details).
745 if (!bucket->active_pages_head)
746 bucket_stats[i].is_valid = false;
747 else
748 PartitionDumpBucketStats(&bucket_stats[i], bucket);
749 if (bucket_stats[i].is_valid) {
750 stats.total_resident_bytes += bucket_stats[i].resident_bytes;
751 stats.total_active_bytes += bucket_stats[i].active_bytes;
752 stats.total_decommittable_bytes += bucket_stats[i].decommittable_bytes;
753 stats.total_discardable_bytes += bucket_stats[i].discardable_bytes;
754 }
755 }
756
757 for (internal::PartitionDirectMapExtent* extent = direct_map_list;
758 extent && num_direct_mapped_allocations < kMaxReportableDirectMaps;
759 extent = extent->next_extent, ++num_direct_mapped_allocations) {
760 DCHECK(!extent->next_extent ||
761 extent->next_extent->prev_extent == extent);
762 size_t slot_size = extent->bucket->slot_size;
763 direct_mapped_allocations_total_size += slot_size;
764 if (is_light_dump)
765 continue;
766 direct_map_lengths[num_direct_mapped_allocations] = slot_size;
767 }
768 }
769
770 if (!is_light_dump) {
771 // Call |PartitionsDumpBucketStats| after collecting stats because it can
772 // try to allocate using |PartitionRootGeneric::Alloc()| and it can't
773 // obtain the lock.
774 for (size_t i = 0; i < kGenericNumBuckets; ++i) {
775 if (bucket_stats[i].is_valid)
776 dumper->PartitionsDumpBucketStats(partition_name, &bucket_stats[i]);
777 }
778
779 for (size_t i = 0; i < num_direct_mapped_allocations; ++i) {
780 uint32_t size = direct_map_lengths[i];
781
782 PartitionBucketMemoryStats mapped_stats = {};
783 mapped_stats.is_valid = true;
784 mapped_stats.is_direct_map = true;
785 mapped_stats.num_full_pages = 1;
786 mapped_stats.allocated_page_size = size;
787 mapped_stats.bucket_slot_size = size;
788 mapped_stats.active_bytes = size;
789 mapped_stats.resident_bytes = size;
790 dumper->PartitionsDumpBucketStats(partition_name, &mapped_stats);
791 }
792 }
793
794 stats.total_resident_bytes += direct_mapped_allocations_total_size;
795 stats.total_active_bytes += direct_mapped_allocations_total_size;
796 dumper->PartitionDumpTotals(partition_name, &stats);
797 }
798
DumpStats(const char * partition_name,bool is_light_dump,PartitionStatsDumper * dumper)799 void PartitionRoot::DumpStats(const char* partition_name,
800 bool is_light_dump,
801 PartitionStatsDumper* dumper) {
802 PartitionMemoryStats stats = {0};
803 stats.total_mmapped_bytes = total_size_of_super_pages;
804 stats.total_committed_bytes = total_size_of_committed_pages;
805 DCHECK(!total_size_of_direct_mapped_pages);
806
807 static constexpr size_t kMaxReportableBuckets = 4096 / sizeof(void*);
808 std::unique_ptr<PartitionBucketMemoryStats[]> memory_stats;
809 if (!is_light_dump) {
810 memory_stats = std::unique_ptr<PartitionBucketMemoryStats[]>(
811 new PartitionBucketMemoryStats[kMaxReportableBuckets]);
812 }
813
814 const size_t partition_num_buckets = num_buckets;
815 DCHECK(partition_num_buckets <= kMaxReportableBuckets);
816
817 for (size_t i = 0; i < partition_num_buckets; ++i) {
818 PartitionBucketMemoryStats bucket_stats = {0};
819 PartitionDumpBucketStats(&bucket_stats, &buckets()[i]);
820 if (bucket_stats.is_valid) {
821 stats.total_resident_bytes += bucket_stats.resident_bytes;
822 stats.total_active_bytes += bucket_stats.active_bytes;
823 stats.total_decommittable_bytes += bucket_stats.decommittable_bytes;
824 stats.total_discardable_bytes += bucket_stats.discardable_bytes;
825 }
826 if (!is_light_dump) {
827 if (bucket_stats.is_valid)
828 memory_stats[i] = bucket_stats;
829 else
830 memory_stats[i].is_valid = false;
831 }
832 }
833 if (!is_light_dump) {
834 // PartitionsDumpBucketStats is called after collecting stats because it
835 // can use PartitionRoot::Alloc() to allocate and this can affect the
836 // statistics.
837 for (size_t i = 0; i < partition_num_buckets; ++i) {
838 if (memory_stats[i].is_valid)
839 dumper->PartitionsDumpBucketStats(partition_name, &memory_stats[i]);
840 }
841 }
842 dumper->PartitionDumpTotals(partition_name, &stats);
843 }
844
845 } // namespace base
846 } // namespace pdfium
847