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 "third_party/base/allocator/partition_allocator/oom.h" 10 #include "third_party/base/allocator/partition_allocator/spin_lock.h" 11 #include "third_party/base/compiler_specific.h" 12 13 // Two partition pages are used as guard / metadata page so make sure the super 14 // page size is bigger. 15 static_assert(pdfium::base::kPartitionPageSize * 4 <= 16 pdfium::base::kSuperPageSize, 17 "ok super page size"); 18 static_assert(!(pdfium::base::kSuperPageSize % 19 pdfium::base::kPartitionPageSize), 20 "ok super page multiple"); 21 // Four system pages gives us room to hack out a still-guard-paged piece 22 // of metadata in the middle of a guard partition page. 23 static_assert(pdfium::base::kSystemPageSize * 4 <= 24 pdfium::base::kPartitionPageSize, 25 "ok partition page size"); 26 static_assert(!(pdfium::base::kPartitionPageSize % 27 pdfium::base::kSystemPageSize), 28 "ok partition page multiple"); 29 static_assert(sizeof(pdfium::base::PartitionPage) <= 30 pdfium::base::kPageMetadataSize, 31 "PartitionPage should not be too big"); 32 static_assert(sizeof(pdfium::base::PartitionBucket) <= 33 pdfium::base::kPageMetadataSize, 34 "PartitionBucket should not be too big"); 35 static_assert(sizeof(pdfium::base::PartitionSuperPageExtentEntry) <= 36 pdfium::base::kPageMetadataSize, 37 "PartitionSuperPageExtentEntry should not be too big"); 38 static_assert(pdfium::base::kPageMetadataSize * 39 pdfium::base::kNumPartitionPagesPerSuperPage <= 40 pdfium::base::kSystemPageSize, 41 "page metadata fits in hole"); 42 // Check that some of our zanier calculations worked out as expected. 43 static_assert(pdfium::base::kGenericSmallestBucket == 8, 44 "generic smallest bucket"); 45 static_assert(pdfium::base::kGenericMaxBucketed == 983040, 46 "generic max bucketed"); 47 static_assert(pdfium::base::kMaxSystemPagesPerSlotSpan < (1 << 8), 48 "System pages per slot span must be less than 128."); 49 50 namespace pdfium { 51 namespace base { 52 53 subtle::SpinLock PartitionRootBase::gInitializedLock; 54 bool PartitionRootBase::gInitialized = false; 55 PartitionPage PartitionRootBase::gSeedPage; 56 PartitionBucket PartitionRootBase::gPagedBucket; 57 void (*PartitionRootBase::gOomHandlingFunction)() = nullptr; 58 PartitionAllocHooks::AllocationHook* PartitionAllocHooks::allocation_hook_ = 59 nullptr; 60 PartitionAllocHooks::FreeHook* PartitionAllocHooks::free_hook_ = nullptr; 61 62 static uint8_t PartitionBucketNumSystemPages(size_t size) { 63 // This works out reasonably for the current bucket sizes of the generic 64 // allocator, and the current values of partition page size and constants. 65 // Specifically, we have enough room to always pack the slots perfectly into 66 // some number of system pages. The only waste is the waste associated with 67 // unfaulted pages (i.e. wasted address space). 68 // TODO: we end up using a lot of system pages for very small sizes. For 69 // example, we'll use 12 system pages for slot size 24. The slot size is 70 // so small that the waste would be tiny with just 4, or 1, system pages. 71 // Later, we can investigate whether there are anti-fragmentation benefits 72 // to using fewer system pages. 73 double best_waste_ratio = 1.0f; 74 uint16_t best_pages = 0; 75 if (size > kMaxSystemPagesPerSlotSpan * kSystemPageSize) { 76 DCHECK(!(size % kSystemPageSize)); 77 best_pages = static_cast<uint16_t>(size / kSystemPageSize); 78 CHECK(best_pages < (1 << 8)); 79 return static_cast<uint8_t>(best_pages); 80 } 81 DCHECK(size <= kMaxSystemPagesPerSlotSpan * kSystemPageSize); 82 for (uint16_t i = kNumSystemPagesPerPartitionPage - 1; 83 i <= kMaxSystemPagesPerSlotSpan; ++i) { 84 size_t page_size = kSystemPageSize * i; 85 size_t num_slots = page_size / size; 86 size_t waste = page_size - (num_slots * size); 87 // Leaving a page unfaulted is not free; the page will occupy an empty page 88 // table entry. Make a simple attempt to account for that. 89 size_t num_remainder_pages = i & (kNumSystemPagesPerPartitionPage - 1); 90 size_t num_unfaulted_pages = 91 num_remainder_pages 92 ? (kNumSystemPagesPerPartitionPage - num_remainder_pages) 93 : 0; 94 waste += sizeof(void*) * num_unfaulted_pages; 95 double waste_ratio = (double)waste / (double)page_size; 96 if (waste_ratio < best_waste_ratio) { 97 best_waste_ratio = waste_ratio; 98 best_pages = i; 99 } 100 } 101 DCHECK(best_pages > 0); 102 CHECK(best_pages <= kMaxSystemPagesPerSlotSpan); 103 return static_cast<uint8_t>(best_pages); 104 } 105 106 static void PartitionAllocBaseInit(PartitionRootBase* root) { 107 DCHECK(!root->initialized); 108 { 109 subtle::SpinLock::Guard guard(PartitionRootBase::gInitializedLock); 110 if (!PartitionRootBase::gInitialized) { 111 PartitionRootBase::gInitialized = true; 112 // We mark the seed page as free to make sure it is skipped by our 113 // logic to find a new active page. 114 PartitionRootBase::gPagedBucket.active_pages_head = 115 &PartitionRootGeneric::gSeedPage; 116 } 117 } 118 119 root->initialized = true; 120 root->total_size_of_committed_pages = 0; 121 root->total_size_of_super_pages = 0; 122 root->total_size_of_direct_mapped_pages = 0; 123 root->next_super_page = 0; 124 root->next_partition_page = 0; 125 root->next_partition_page_end = 0; 126 root->first_extent = 0; 127 root->current_extent = 0; 128 root->direct_map_list = 0; 129 130 memset(&root->global_empty_page_ring, '\0', 131 sizeof(root->global_empty_page_ring)); 132 root->global_empty_page_ring_index = 0; 133 134 // This is a "magic" value so we can test if a root pointer is valid. 135 root->inverted_self = ~reinterpret_cast<uintptr_t>(root); 136 } 137 138 static void PartitionBucketInitBase(PartitionBucket* bucket, 139 PartitionRootBase* root) { 140 bucket->active_pages_head = &PartitionRootGeneric::gSeedPage; 141 bucket->empty_pages_head = 0; 142 bucket->decommitted_pages_head = 0; 143 bucket->num_full_pages = 0; 144 bucket->num_system_pages_per_slot_span = 145 PartitionBucketNumSystemPages(bucket->slot_size); 146 } 147 148 void PartitionAllocGlobalInit(void (*oom_handling_function)()) { 149 DCHECK(oom_handling_function); 150 PartitionRootBase::gOomHandlingFunction = oom_handling_function; 151 } 152 153 void PartitionAllocInit(PartitionRoot* root, 154 size_t num_buckets, 155 size_t max_allocation) { 156 PartitionAllocBaseInit(root); 157 158 root->num_buckets = num_buckets; 159 root->max_allocation = max_allocation; 160 size_t i; 161 for (i = 0; i < root->num_buckets; ++i) { 162 PartitionBucket* bucket = &root->buckets()[i]; 163 if (!i) 164 bucket->slot_size = kAllocationGranularity; 165 else 166 bucket->slot_size = i << kBucketShift; 167 PartitionBucketInitBase(bucket, root); 168 } 169 } 170 171 void PartitionAllocGenericInit(PartitionRootGeneric* root) { 172 subtle::SpinLock::Guard guard(root->lock); 173 174 PartitionAllocBaseInit(root); 175 176 // Precalculate some shift and mask constants used in the hot path. 177 // Example: malloc(41) == 101001 binary. 178 // Order is 6 (1 << 6-1) == 32 is highest bit set. 179 // order_index is the next three MSB == 010 == 2. 180 // sub_order_index_mask is a mask for the remaining bits == 11 (masking to 01 181 // for 182 // the sub_order_index). 183 size_t order; 184 for (order = 0; order <= kBitsPerSizeT; ++order) { 185 size_t order_index_shift; 186 if (order < kGenericNumBucketsPerOrderBits + 1) 187 order_index_shift = 0; 188 else 189 order_index_shift = order - (kGenericNumBucketsPerOrderBits + 1); 190 root->order_index_shifts[order] = order_index_shift; 191 size_t sub_order_index_mask; 192 if (order == kBitsPerSizeT) { 193 // This avoids invoking undefined behavior for an excessive shift. 194 sub_order_index_mask = 195 static_cast<size_t>(-1) >> (kGenericNumBucketsPerOrderBits + 1); 196 } else { 197 sub_order_index_mask = ((static_cast<size_t>(1) << order) - 1) >> 198 (kGenericNumBucketsPerOrderBits + 1); 199 } 200 root->order_sub_index_masks[order] = sub_order_index_mask; 201 } 202 203 // Set up the actual usable buckets first. 204 // Note that typical values (i.e. min allocation size of 8) will result in 205 // pseudo buckets (size==9 etc. or more generally, size is not a multiple 206 // of the smallest allocation granularity). 207 // We avoid them in the bucket lookup map, but we tolerate them to keep the 208 // code simpler and the structures more generic. 209 size_t i, j; 210 size_t current_size = kGenericSmallestBucket; 211 size_t currentIncrement = 212 kGenericSmallestBucket >> kGenericNumBucketsPerOrderBits; 213 PartitionBucket* bucket = &root->buckets[0]; 214 for (i = 0; i < kGenericNumBucketedOrders; ++i) { 215 for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { 216 bucket->slot_size = current_size; 217 PartitionBucketInitBase(bucket, root); 218 // Disable psuedo buckets so that touching them faults. 219 if (current_size % kGenericSmallestBucket) 220 bucket->active_pages_head = 0; 221 current_size += currentIncrement; 222 ++bucket; 223 } 224 currentIncrement <<= 1; 225 } 226 DCHECK(current_size == 1 << kGenericMaxBucketedOrder); 227 DCHECK(bucket == &root->buckets[0] + kGenericNumBuckets); 228 229 // Then set up the fast size -> bucket lookup table. 230 bucket = &root->buckets[0]; 231 PartitionBucket** bucketPtr = &root->bucket_lookups[0]; 232 for (order = 0; order <= kBitsPerSizeT; ++order) { 233 for (j = 0; j < kGenericNumBucketsPerOrder; ++j) { 234 if (order < kGenericMinBucketedOrder) { 235 // Use the bucket of the finest granularity for malloc(0) etc. 236 *bucketPtr++ = &root->buckets[0]; 237 } else if (order > kGenericMaxBucketedOrder) { 238 *bucketPtr++ = &PartitionRootGeneric::gPagedBucket; 239 } else { 240 PartitionBucket* validBucket = bucket; 241 // Skip over invalid buckets. 242 while (validBucket->slot_size % kGenericSmallestBucket) 243 validBucket++; 244 *bucketPtr++ = validBucket; 245 bucket++; 246 } 247 } 248 } 249 DCHECK(bucket == &root->buckets[0] + kGenericNumBuckets); 250 DCHECK(bucketPtr == 251 &root->bucket_lookups[0] + 252 ((kBitsPerSizeT + 1) * kGenericNumBucketsPerOrder)); 253 // And there's one last bucket lookup that will be hit for e.g. malloc(-1), 254 // which tries to overflow to a non-existant order. 255 *bucketPtr = &PartitionRootGeneric::gPagedBucket; 256 } 257 258 #if !defined(ARCH_CPU_64_BITS) 259 static NOINLINE void PartitionOutOfMemoryWithLotsOfUncommitedPages() { 260 OOM_CRASH(); 261 } 262 #endif 263 264 static NOINLINE void PartitionOutOfMemory(const PartitionRootBase* root) { 265 #if !defined(ARCH_CPU_64_BITS) 266 // Check whether this OOM is due to a lot of super pages that are allocated 267 // but not committed, probably due to http://crbug.com/421387. 268 if (root->total_size_of_super_pages + 269 root->total_size_of_direct_mapped_pages - 270 root->total_size_of_committed_pages > 271 kReasonableSizeOfUnusedPages) { 272 PartitionOutOfMemoryWithLotsOfUncommitedPages(); 273 } 274 #endif 275 if (PartitionRootBase::gOomHandlingFunction) 276 (*PartitionRootBase::gOomHandlingFunction)(); 277 OOM_CRASH(); 278 } 279 280 static NOINLINE void PartitionExcessiveAllocationSize() { 281 OOM_CRASH(); 282 } 283 284 static NOINLINE void PartitionBucketFull() { 285 OOM_CRASH(); 286 } 287 288 // partitionPageStateIs* 289 // Note that it's only valid to call these functions on pages found on one of 290 // the page lists. Specifically, you can't call these functions on full pages 291 // that were detached from the active list. 292 static bool ALWAYS_INLINE 293 PartitionPageStateIsActive(const PartitionPage* page) { 294 DCHECK(page != &PartitionRootGeneric::gSeedPage); 295 DCHECK(!page->page_offset); 296 return (page->num_allocated_slots > 0 && 297 (page->freelist_head || page->num_unprovisioned_slots)); 298 } 299 300 static bool ALWAYS_INLINE PartitionPageStateIsFull(const PartitionPage* page) { 301 DCHECK(page != &PartitionRootGeneric::gSeedPage); 302 DCHECK(!page->page_offset); 303 bool ret = (page->num_allocated_slots == PartitionBucketSlots(page->bucket)); 304 if (ret) { 305 DCHECK(!page->freelist_head); 306 DCHECK(!page->num_unprovisioned_slots); 307 } 308 return ret; 309 } 310 311 static bool ALWAYS_INLINE PartitionPageStateIsEmpty(const PartitionPage* page) { 312 DCHECK(page != &PartitionRootGeneric::gSeedPage); 313 DCHECK(!page->page_offset); 314 return (!page->num_allocated_slots && page->freelist_head); 315 } 316 317 static bool ALWAYS_INLINE 318 PartitionPageStateIsDecommitted(const PartitionPage* page) { 319 DCHECK(page != &PartitionRootGeneric::gSeedPage); 320 DCHECK(!page->page_offset); 321 bool ret = (!page->num_allocated_slots && !page->freelist_head); 322 if (ret) { 323 DCHECK(!page->num_unprovisioned_slots); 324 DCHECK(page->empty_cache_index == -1); 325 } 326 return ret; 327 } 328 329 static void PartitionIncreaseCommittedPages(PartitionRootBase* root, 330 size_t len) { 331 root->total_size_of_committed_pages += len; 332 DCHECK(root->total_size_of_committed_pages <= 333 root->total_size_of_super_pages + 334 root->total_size_of_direct_mapped_pages); 335 } 336 337 static void PartitionDecreaseCommittedPages(PartitionRootBase* root, 338 size_t len) { 339 root->total_size_of_committed_pages -= len; 340 DCHECK(root->total_size_of_committed_pages <= 341 root->total_size_of_super_pages + 342 root->total_size_of_direct_mapped_pages); 343 } 344 345 static ALWAYS_INLINE void PartitionDecommitSystemPages(PartitionRootBase* root, 346 void* address, 347 size_t length) { 348 DecommitSystemPages(address, length); 349 PartitionDecreaseCommittedPages(root, length); 350 } 351 352 static ALWAYS_INLINE void PartitionRecommitSystemPages(PartitionRootBase* root, 353 void* address, 354 size_t length) { 355 RecommitSystemPages(address, length); 356 PartitionIncreaseCommittedPages(root, length); 357 } 358 359 static ALWAYS_INLINE void* PartitionAllocPartitionPages( 360 PartitionRootBase* root, 361 int flags, 362 uint16_t num_partition_pages) { 363 DCHECK(!(reinterpret_cast<uintptr_t>(root->next_partition_page) % 364 kPartitionPageSize)); 365 DCHECK(!(reinterpret_cast<uintptr_t>(root->next_partition_page_end) % 366 kPartitionPageSize)); 367 DCHECK(num_partition_pages <= kNumPartitionPagesPerSuperPage); 368 size_t total_size = kPartitionPageSize * num_partition_pages; 369 size_t num_partition_pages_left = 370 (root->next_partition_page_end - root->next_partition_page) >> 371 kPartitionPageShift; 372 if (LIKELY(num_partition_pages_left >= num_partition_pages)) { 373 // In this case, we can still hand out pages from the current super page 374 // allocation. 375 char* ret = root->next_partition_page; 376 root->next_partition_page += total_size; 377 PartitionIncreaseCommittedPages(root, total_size); 378 return ret; 379 } 380 381 // Need a new super page. We want to allocate super pages in a continguous 382 // address region as much as possible. This is important for not causing 383 // page table bloat and not fragmenting address spaces in 32 bit 384 // architectures. 385 char* requestedAddress = root->next_super_page; 386 char* super_page = reinterpret_cast<char*>(AllocPages( 387 requestedAddress, kSuperPageSize, kSuperPageSize, PageAccessible)); 388 if (UNLIKELY(!super_page)) 389 return 0; 390 391 root->total_size_of_super_pages += kSuperPageSize; 392 PartitionIncreaseCommittedPages(root, total_size); 393 394 root->next_super_page = super_page + kSuperPageSize; 395 char* ret = super_page + kPartitionPageSize; 396 root->next_partition_page = ret + total_size; 397 root->next_partition_page_end = root->next_super_page - kPartitionPageSize; 398 // Make the first partition page in the super page a guard page, but leave a 399 // hole in the middle. 400 // This is where we put page metadata and also a tiny amount of extent 401 // metadata. 402 SetSystemPagesInaccessible(super_page, kSystemPageSize); 403 SetSystemPagesInaccessible(super_page + (kSystemPageSize * 2), 404 kPartitionPageSize - (kSystemPageSize * 2)); 405 // Also make the last partition page a guard page. 406 SetSystemPagesInaccessible(super_page + (kSuperPageSize - kPartitionPageSize), 407 kPartitionPageSize); 408 409 // If we were after a specific address, but didn't get it, assume that 410 // the system chose a lousy address. Here most OS'es have a default 411 // algorithm that isn't randomized. For example, most Linux 412 // distributions will allocate the mapping directly before the last 413 // successful mapping, which is far from random. So we just get fresh 414 // randomness for the next mapping attempt. 415 if (requestedAddress && requestedAddress != super_page) 416 root->next_super_page = 0; 417 418 // We allocated a new super page so update super page metadata. 419 // First check if this is a new extent or not. 420 PartitionSuperPageExtentEntry* latest_extent = 421 reinterpret_cast<PartitionSuperPageExtentEntry*>( 422 PartitionSuperPageToMetadataArea(super_page)); 423 // By storing the root in every extent metadata object, we have a fast way 424 // to go from a pointer within the partition to the root object. 425 latest_extent->root = root; 426 // Most new extents will be part of a larger extent, and these three fields 427 // are unused, but we initialize them to 0 so that we get a clear signal 428 // in case they are accidentally used. 429 latest_extent->super_page_base = 0; 430 latest_extent->super_pages_end = 0; 431 latest_extent->next = 0; 432 433 PartitionSuperPageExtentEntry* current_extent = root->current_extent; 434 bool isNewExtent = (super_page != requestedAddress); 435 if (UNLIKELY(isNewExtent)) { 436 if (UNLIKELY(!current_extent)) { 437 DCHECK(!root->first_extent); 438 root->first_extent = latest_extent; 439 } else { 440 DCHECK(current_extent->super_page_base); 441 current_extent->next = latest_extent; 442 } 443 root->current_extent = latest_extent; 444 latest_extent->super_page_base = super_page; 445 latest_extent->super_pages_end = super_page + kSuperPageSize; 446 } else { 447 // We allocated next to an existing extent so just nudge the size up a 448 // little. 449 DCHECK(current_extent->super_pages_end); 450 current_extent->super_pages_end += kSuperPageSize; 451 DCHECK(ret >= current_extent->super_page_base && 452 ret < current_extent->super_pages_end); 453 } 454 return ret; 455 } 456 457 static ALWAYS_INLINE uint16_t 458 PartitionBucketPartitionPages(const PartitionBucket* bucket) { 459 return (bucket->num_system_pages_per_slot_span + 460 (kNumSystemPagesPerPartitionPage - 1)) / 461 kNumSystemPagesPerPartitionPage; 462 } 463 464 static ALWAYS_INLINE void PartitionPageReset(PartitionPage* page) { 465 DCHECK(PartitionPageStateIsDecommitted(page)); 466 467 page->num_unprovisioned_slots = PartitionBucketSlots(page->bucket); 468 DCHECK(page->num_unprovisioned_slots); 469 470 page->next_page = nullptr; 471 } 472 473 static ALWAYS_INLINE void PartitionPageSetup(PartitionPage* page, 474 PartitionBucket* bucket) { 475 // The bucket never changes. We set it up once. 476 page->bucket = bucket; 477 page->empty_cache_index = -1; 478 479 PartitionPageReset(page); 480 481 // If this page has just a single slot, do not set up page offsets for any 482 // page metadata other than the first one. This ensures that attempts to 483 // touch invalid page metadata fail. 484 if (page->num_unprovisioned_slots == 1) 485 return; 486 487 uint16_t num_partition_pages = PartitionBucketPartitionPages(bucket); 488 char* page_char_ptr = reinterpret_cast<char*>(page); 489 for (uint16_t i = 1; i < num_partition_pages; ++i) { 490 page_char_ptr += kPageMetadataSize; 491 PartitionPage* secondary_page = 492 reinterpret_cast<PartitionPage*>(page_char_ptr); 493 secondary_page->page_offset = i; 494 } 495 } 496 497 static ALWAYS_INLINE char* PartitionPageAllocAndFillFreelist( 498 PartitionPage* page) { 499 DCHECK(page != &PartitionRootGeneric::gSeedPage); 500 uint16_t num_slots = page->num_unprovisioned_slots; 501 DCHECK(num_slots); 502 PartitionBucket* bucket = page->bucket; 503 // We should only get here when _every_ slot is either used or unprovisioned. 504 // (The third state is "on the freelist". If we have a non-empty freelist, we 505 // should not get here.) 506 DCHECK(num_slots + page->num_allocated_slots == PartitionBucketSlots(bucket)); 507 // Similarly, make explicitly sure that the freelist is empty. 508 DCHECK(!page->freelist_head); 509 DCHECK(page->num_allocated_slots >= 0); 510 511 size_t size = bucket->slot_size; 512 char* base = reinterpret_cast<char*>(PartitionPageToPointer(page)); 513 char* return_object = base + (size * page->num_allocated_slots); 514 char* firstFreelistPointer = return_object + size; 515 char* firstFreelistPointerExtent = 516 firstFreelistPointer + sizeof(PartitionFreelistEntry*); 517 // Our goal is to fault as few system pages as possible. We calculate the 518 // page containing the "end" of the returned slot, and then allow freelist 519 // pointers to be written up to the end of that page. 520 char* sub_page_limit = reinterpret_cast<char*>( 521 RoundUpToSystemPage(reinterpret_cast<size_t>(firstFreelistPointer))); 522 char* slots_limit = return_object + (size * num_slots); 523 char* freelist_limit = sub_page_limit; 524 if (UNLIKELY(slots_limit < freelist_limit)) 525 freelist_limit = slots_limit; 526 527 uint16_t num_new_freelist_entries = 0; 528 if (LIKELY(firstFreelistPointerExtent <= freelist_limit)) { 529 // Only consider used space in the slot span. If we consider wasted 530 // space, we may get an off-by-one when a freelist pointer fits in the 531 // wasted space, but a slot does not. 532 // We know we can fit at least one freelist pointer. 533 num_new_freelist_entries = 1; 534 // Any further entries require space for the whole slot span. 535 num_new_freelist_entries += static_cast<uint16_t>( 536 (freelist_limit - firstFreelistPointerExtent) / size); 537 } 538 539 // We always return an object slot -- that's the +1 below. 540 // We do not neccessarily create any new freelist entries, because we cross 541 // sub page boundaries frequently for large bucket sizes. 542 DCHECK(num_new_freelist_entries + 1 <= num_slots); 543 num_slots -= (num_new_freelist_entries + 1); 544 page->num_unprovisioned_slots = num_slots; 545 page->num_allocated_slots++; 546 547 if (LIKELY(num_new_freelist_entries)) { 548 char* freelist_pointer = firstFreelistPointer; 549 PartitionFreelistEntry* entry = 550 reinterpret_cast<PartitionFreelistEntry*>(freelist_pointer); 551 page->freelist_head = entry; 552 while (--num_new_freelist_entries) { 553 freelist_pointer += size; 554 PartitionFreelistEntry* next_entry = 555 reinterpret_cast<PartitionFreelistEntry*>(freelist_pointer); 556 entry->next = PartitionFreelistMask(next_entry); 557 entry = next_entry; 558 } 559 entry->next = PartitionFreelistMask(0); 560 } else { 561 page->freelist_head = 0; 562 } 563 return return_object; 564 } 565 566 // This helper function scans a bucket's active page list for a suitable new 567 // active page. 568 // When it finds a suitable new active page (one that has free slots and is not 569 // empty), it is set as the new active page. If there is no suitable new 570 // active page, the current active page is set to the seed page. 571 // As potential pages are scanned, they are tidied up according to their state. 572 // Empty pages are swept on to the empty page list, decommitted pages on to the 573 // decommitted page list and full pages are unlinked from any list. 574 static bool PartitionSetNewActivePage(PartitionBucket* bucket) { 575 PartitionPage* page = bucket->active_pages_head; 576 if (page == &PartitionRootBase::gSeedPage) 577 return false; 578 579 PartitionPage* next_page; 580 581 for (; page; page = next_page) { 582 next_page = page->next_page; 583 DCHECK(page->bucket == bucket); 584 DCHECK(page != bucket->empty_pages_head); 585 DCHECK(page != bucket->decommitted_pages_head); 586 587 // Deal with empty and decommitted pages. 588 if (LIKELY(PartitionPageStateIsActive(page))) { 589 // This page is usable because it has freelist entries, or has 590 // unprovisioned slots we can create freelist entries from. 591 bucket->active_pages_head = page; 592 return true; 593 } 594 if (LIKELY(PartitionPageStateIsEmpty(page))) { 595 page->next_page = bucket->empty_pages_head; 596 bucket->empty_pages_head = page; 597 } else if (LIKELY(PartitionPageStateIsDecommitted(page))) { 598 page->next_page = bucket->decommitted_pages_head; 599 bucket->decommitted_pages_head = page; 600 } else { 601 DCHECK(PartitionPageStateIsFull(page)); 602 // If we get here, we found a full page. Skip over it too, and also 603 // tag it as full (via a negative value). We need it tagged so that 604 // free'ing can tell, and move it back into the active page list. 605 page->num_allocated_slots = -page->num_allocated_slots; 606 ++bucket->num_full_pages; 607 // num_full_pages is a uint16_t for efficient packing so guard against 608 // overflow to be safe. 609 if (UNLIKELY(!bucket->num_full_pages)) 610 PartitionBucketFull(); 611 // Not necessary but might help stop accidents. 612 page->next_page = 0; 613 } 614 } 615 616 bucket->active_pages_head = &PartitionRootGeneric::gSeedPage; 617 return false; 618 } 619 620 static ALWAYS_INLINE PartitionDirectMapExtent* partitionPageToDirectMapExtent( 621 PartitionPage* page) { 622 DCHECK(PartitionBucketIsDirectMapped(page->bucket)); 623 return reinterpret_cast<PartitionDirectMapExtent*>( 624 reinterpret_cast<char*>(page) + 3 * kPageMetadataSize); 625 } 626 627 static ALWAYS_INLINE void PartitionPageSetRawSize(PartitionPage* page, 628 size_t size) { 629 size_t* raw_size_ptr = PartitionPageGetRawSizePtr(page); 630 if (UNLIKELY(raw_size_ptr != nullptr)) 631 *raw_size_ptr = size; 632 } 633 634 static ALWAYS_INLINE PartitionPage* PartitionDirectMap(PartitionRootBase* root, 635 int flags, 636 size_t raw_size) { 637 size_t size = PartitionDirectMapSize(raw_size); 638 639 // Because we need to fake looking like a super page, we need to allocate 640 // a bunch of system pages more than "size": 641 // - The first few system pages are the partition page in which the super 642 // page metadata is stored. We fault just one system page out of a partition 643 // page sized clump. 644 // - We add a trailing guard page on 32-bit (on 64-bit we rely on the 645 // massive address space plus randomization instead). 646 size_t map_size = size + kPartitionPageSize; 647 #if !defined(ARCH_CPU_64_BITS) 648 map_size += kSystemPageSize; 649 #endif 650 // Round up to the allocation granularity. 651 map_size += kPageAllocationGranularityOffsetMask; 652 map_size &= kPageAllocationGranularityBaseMask; 653 654 // TODO: these pages will be zero-filled. Consider internalizing an 655 // allocZeroed() API so we can avoid a memset() entirely in this case. 656 char* ptr = reinterpret_cast<char*>( 657 AllocPages(0, map_size, kSuperPageSize, PageAccessible)); 658 if (UNLIKELY(!ptr)) 659 return nullptr; 660 661 size_t committed_page_size = size + kSystemPageSize; 662 root->total_size_of_direct_mapped_pages += committed_page_size; 663 PartitionIncreaseCommittedPages(root, committed_page_size); 664 665 char* slot = ptr + kPartitionPageSize; 666 SetSystemPagesInaccessible(ptr + (kSystemPageSize * 2), 667 kPartitionPageSize - (kSystemPageSize * 2)); 668 #if !defined(ARCH_CPU_64_BITS) 669 SetSystemPagesInaccessible(ptr, kSystemPageSize); 670 SetSystemPagesInaccessible(slot + size, kSystemPageSize); 671 #endif 672 673 PartitionSuperPageExtentEntry* extent = 674 reinterpret_cast<PartitionSuperPageExtentEntry*>( 675 PartitionSuperPageToMetadataArea(ptr)); 676 extent->root = root; 677 // The new structures are all located inside a fresh system page so they 678 // will all be zeroed out. These DCHECKs are for documentation. 679 DCHECK(!extent->super_page_base); 680 DCHECK(!extent->super_pages_end); 681 DCHECK(!extent->next); 682 PartitionPage* page = PartitionPointerToPageNoAlignmentCheck(slot); 683 PartitionBucket* bucket = reinterpret_cast<PartitionBucket*>( 684 reinterpret_cast<char*>(page) + (kPageMetadataSize * 2)); 685 DCHECK(!page->next_page); 686 DCHECK(!page->num_allocated_slots); 687 DCHECK(!page->num_unprovisioned_slots); 688 DCHECK(!page->page_offset); 689 DCHECK(!page->empty_cache_index); 690 page->bucket = bucket; 691 page->freelist_head = reinterpret_cast<PartitionFreelistEntry*>(slot); 692 PartitionFreelistEntry* next_entry = 693 reinterpret_cast<PartitionFreelistEntry*>(slot); 694 next_entry->next = PartitionFreelistMask(0); 695 696 DCHECK(!bucket->active_pages_head); 697 DCHECK(!bucket->empty_pages_head); 698 DCHECK(!bucket->decommitted_pages_head); 699 DCHECK(!bucket->num_system_pages_per_slot_span); 700 DCHECK(!bucket->num_full_pages); 701 bucket->slot_size = size; 702 703 PartitionDirectMapExtent* map_extent = partitionPageToDirectMapExtent(page); 704 map_extent->map_size = map_size - kPartitionPageSize - kSystemPageSize; 705 map_extent->bucket = bucket; 706 707 // Maintain the doubly-linked list of all direct mappings. 708 map_extent->next_extent = root->direct_map_list; 709 if (map_extent->next_extent) 710 map_extent->next_extent->prev_extent = map_extent; 711 map_extent->prev_extent = nullptr; 712 root->direct_map_list = map_extent; 713 714 return page; 715 } 716 717 static ALWAYS_INLINE void PartitionDirectUnmap(PartitionPage* page) { 718 PartitionRootBase* root = PartitionPageToRoot(page); 719 const PartitionDirectMapExtent* extent = partitionPageToDirectMapExtent(page); 720 size_t unmap_size = extent->map_size; 721 722 // Maintain the doubly-linked list of all direct mappings. 723 if (extent->prev_extent) { 724 DCHECK(extent->prev_extent->next_extent == extent); 725 extent->prev_extent->next_extent = extent->next_extent; 726 } else { 727 root->direct_map_list = extent->next_extent; 728 } 729 if (extent->next_extent) { 730 DCHECK(extent->next_extent->prev_extent == extent); 731 extent->next_extent->prev_extent = extent->prev_extent; 732 } 733 734 // Add on the size of the trailing guard page and preceeding partition 735 // page. 736 unmap_size += kPartitionPageSize + kSystemPageSize; 737 738 size_t uncommitted_page_size = page->bucket->slot_size + kSystemPageSize; 739 PartitionDecreaseCommittedPages(root, uncommitted_page_size); 740 DCHECK(root->total_size_of_direct_mapped_pages >= uncommitted_page_size); 741 root->total_size_of_direct_mapped_pages -= uncommitted_page_size; 742 743 DCHECK(!(unmap_size & kPageAllocationGranularityOffsetMask)); 744 745 char* ptr = reinterpret_cast<char*>(PartitionPageToPointer(page)); 746 // Account for the mapping starting a partition page before the actual 747 // allocation address. 748 ptr -= kPartitionPageSize; 749 750 FreePages(ptr, unmap_size); 751 } 752 753 void* PartitionAllocSlowPath(PartitionRootBase* root, 754 int flags, 755 size_t size, 756 PartitionBucket* bucket) { 757 // The slow path is called when the freelist is empty. 758 DCHECK(!bucket->active_pages_head->freelist_head); 759 760 PartitionPage* new_page = nullptr; 761 762 // For the PartitionAllocGeneric API, we have a bunch of buckets marked 763 // as special cases. We bounce them through to the slow path so that we 764 // can still have a blazing fast hot path due to lack of corner-case 765 // branches. 766 bool returnNull = flags & PartitionAllocReturnNull; 767 if (UNLIKELY(PartitionBucketIsDirectMapped(bucket))) { 768 DCHECK(size > kGenericMaxBucketed); 769 DCHECK(bucket == &PartitionRootBase::gPagedBucket); 770 DCHECK(bucket->active_pages_head == &PartitionRootGeneric::gSeedPage); 771 if (size > kGenericMaxDirectMapped) { 772 if (returnNull) 773 return nullptr; 774 PartitionExcessiveAllocationSize(); 775 } 776 new_page = PartitionDirectMap(root, flags, size); 777 } else if (LIKELY(PartitionSetNewActivePage(bucket))) { 778 // First, did we find an active page in the active pages list? 779 new_page = bucket->active_pages_head; 780 DCHECK(PartitionPageStateIsActive(new_page)); 781 } else if (LIKELY(bucket->empty_pages_head != nullptr) || 782 LIKELY(bucket->decommitted_pages_head != nullptr)) { 783 // Second, look in our lists of empty and decommitted pages. 784 // Check empty pages first, which are preferred, but beware that an 785 // empty page might have been decommitted. 786 while (LIKELY((new_page = bucket->empty_pages_head) != nullptr)) { 787 DCHECK(new_page->bucket == bucket); 788 DCHECK(PartitionPageStateIsEmpty(new_page) || 789 PartitionPageStateIsDecommitted(new_page)); 790 bucket->empty_pages_head = new_page->next_page; 791 // Accept the empty page unless it got decommitted. 792 if (new_page->freelist_head) { 793 new_page->next_page = nullptr; 794 break; 795 } 796 DCHECK(PartitionPageStateIsDecommitted(new_page)); 797 new_page->next_page = bucket->decommitted_pages_head; 798 bucket->decommitted_pages_head = new_page; 799 } 800 if (UNLIKELY(!new_page) && 801 LIKELY(bucket->decommitted_pages_head != nullptr)) { 802 new_page = bucket->decommitted_pages_head; 803 DCHECK(new_page->bucket == bucket); 804 DCHECK(PartitionPageStateIsDecommitted(new_page)); 805 bucket->decommitted_pages_head = new_page->next_page; 806 void* addr = PartitionPageToPointer(new_page); 807 PartitionRecommitSystemPages(root, addr, 808 PartitionBucketBytes(new_page->bucket)); 809 PartitionPageReset(new_page); 810 } 811 DCHECK(new_page); 812 } else { 813 // Third. If we get here, we need a brand new page. 814 uint16_t num_partition_pages = PartitionBucketPartitionPages(bucket); 815 void* rawPages = 816 PartitionAllocPartitionPages(root, flags, num_partition_pages); 817 if (LIKELY(rawPages != nullptr)) { 818 new_page = PartitionPointerToPageNoAlignmentCheck(rawPages); 819 PartitionPageSetup(new_page, bucket); 820 } 821 } 822 823 // Bail if we had a memory allocation failure. 824 if (UNLIKELY(!new_page)) { 825 DCHECK(bucket->active_pages_head == &PartitionRootGeneric::gSeedPage); 826 if (returnNull) 827 return nullptr; 828 PartitionOutOfMemory(root); 829 } 830 831 bucket = new_page->bucket; 832 DCHECK(bucket != &PartitionRootBase::gPagedBucket); 833 bucket->active_pages_head = new_page; 834 PartitionPageSetRawSize(new_page, size); 835 836 // If we found an active page with free slots, or an empty page, we have a 837 // usable freelist head. 838 if (LIKELY(new_page->freelist_head != nullptr)) { 839 PartitionFreelistEntry* entry = new_page->freelist_head; 840 PartitionFreelistEntry* new_head = PartitionFreelistMask(entry->next); 841 new_page->freelist_head = new_head; 842 new_page->num_allocated_slots++; 843 return entry; 844 } 845 // Otherwise, we need to build the freelist. 846 DCHECK(new_page->num_unprovisioned_slots); 847 return PartitionPageAllocAndFillFreelist(new_page); 848 } 849 850 static ALWAYS_INLINE void PartitionDecommitPage(PartitionRootBase* root, 851 PartitionPage* page) { 852 DCHECK(PartitionPageStateIsEmpty(page)); 853 DCHECK(!PartitionBucketIsDirectMapped(page->bucket)); 854 void* addr = PartitionPageToPointer(page); 855 PartitionDecommitSystemPages(root, addr, PartitionBucketBytes(page->bucket)); 856 857 // We actually leave the decommitted page in the active list. We'll sweep 858 // it on to the decommitted page list when we next walk the active page 859 // list. 860 // Pulling this trick enables us to use a singly-linked page list for all 861 // cases, which is critical in keeping the page metadata structure down to 862 // 32 bytes in size. 863 page->freelist_head = 0; 864 page->num_unprovisioned_slots = 0; 865 DCHECK(PartitionPageStateIsDecommitted(page)); 866 } 867 868 static void PartitionDecommitPageIfPossible(PartitionRootBase* root, 869 PartitionPage* page) { 870 DCHECK(page->empty_cache_index >= 0); 871 DCHECK(static_cast<unsigned>(page->empty_cache_index) < kMaxFreeableSpans); 872 DCHECK(page == root->global_empty_page_ring[page->empty_cache_index]); 873 page->empty_cache_index = -1; 874 if (PartitionPageStateIsEmpty(page)) 875 PartitionDecommitPage(root, page); 876 } 877 878 static ALWAYS_INLINE void PartitionRegisterEmptyPage(PartitionPage* page) { 879 DCHECK(PartitionPageStateIsEmpty(page)); 880 PartitionRootBase* root = PartitionPageToRoot(page); 881 882 // If the page is already registered as empty, give it another life. 883 if (page->empty_cache_index != -1) { 884 DCHECK(page->empty_cache_index >= 0); 885 DCHECK(static_cast<unsigned>(page->empty_cache_index) < kMaxFreeableSpans); 886 DCHECK(root->global_empty_page_ring[page->empty_cache_index] == page); 887 root->global_empty_page_ring[page->empty_cache_index] = 0; 888 } 889 890 int16_t current_index = root->global_empty_page_ring_index; 891 PartitionPage* pageToDecommit = root->global_empty_page_ring[current_index]; 892 // The page might well have been re-activated, filled up, etc. before we get 893 // around to looking at it here. 894 if (pageToDecommit) 895 PartitionDecommitPageIfPossible(root, pageToDecommit); 896 897 // We put the empty slot span on our global list of "pages that were once 898 // empty". thus providing it a bit of breathing room to get re-used before 899 // we really free it. This improves performance, particularly on Mac OS X 900 // which has subpar memory management performance. 901 root->global_empty_page_ring[current_index] = page; 902 page->empty_cache_index = current_index; 903 ++current_index; 904 if (current_index == kMaxFreeableSpans) 905 current_index = 0; 906 root->global_empty_page_ring_index = current_index; 907 } 908 909 static void PartitionDecommitEmptyPages(PartitionRootBase* root) { 910 for (size_t i = 0; i < kMaxFreeableSpans; ++i) { 911 PartitionPage* page = root->global_empty_page_ring[i]; 912 if (page) 913 PartitionDecommitPageIfPossible(root, page); 914 root->global_empty_page_ring[i] = nullptr; 915 } 916 } 917 918 void PartitionFreeSlowPath(PartitionPage* page) { 919 PartitionBucket* bucket = page->bucket; 920 DCHECK(page != &PartitionRootGeneric::gSeedPage); 921 if (LIKELY(page->num_allocated_slots == 0)) { 922 // Page became fully unused. 923 if (UNLIKELY(PartitionBucketIsDirectMapped(bucket))) { 924 PartitionDirectUnmap(page); 925 return; 926 } 927 // If it's the current active page, change it. We bounce the page to 928 // the empty list as a force towards defragmentation. 929 if (LIKELY(page == bucket->active_pages_head)) 930 (void)PartitionSetNewActivePage(bucket); 931 DCHECK(bucket->active_pages_head != page); 932 933 PartitionPageSetRawSize(page, 0); 934 DCHECK(!PartitionPageGetRawSize(page)); 935 936 PartitionRegisterEmptyPage(page); 937 } else { 938 DCHECK(!PartitionBucketIsDirectMapped(bucket)); 939 // Ensure that the page is full. That's the only valid case if we 940 // arrive here. 941 DCHECK(page->num_allocated_slots < 0); 942 // A transition of num_allocated_slots from 0 to -1 is not legal, and 943 // likely indicates a double-free. 944 CHECK(page->num_allocated_slots != -1); 945 page->num_allocated_slots = -page->num_allocated_slots - 2; 946 DCHECK(page->num_allocated_slots == PartitionBucketSlots(bucket) - 1); 947 // Fully used page became partially used. It must be put back on the 948 // non-full page list. Also make it the current page to increase the 949 // chances of it being filled up again. The old current page will be 950 // the next page. 951 DCHECK(!page->next_page); 952 if (LIKELY(bucket->active_pages_head != &PartitionRootGeneric::gSeedPage)) 953 page->next_page = bucket->active_pages_head; 954 bucket->active_pages_head = page; 955 --bucket->num_full_pages; 956 // Special case: for a partition page with just a single slot, it may 957 // now be empty and we want to run it through the empty logic. 958 if (UNLIKELY(page->num_allocated_slots == 0)) 959 PartitionFreeSlowPath(page); 960 } 961 } 962 963 bool partitionReallocDirectMappedInPlace(PartitionRootGeneric* root, 964 PartitionPage* page, 965 size_t raw_size) { 966 DCHECK(PartitionBucketIsDirectMapped(page->bucket)); 967 968 raw_size = PartitionCookieSizeAdjustAdd(raw_size); 969 970 // Note that the new size might be a bucketed size; this function is called 971 // whenever we're reallocating a direct mapped allocation. 972 size_t new_size = PartitionDirectMapSize(raw_size); 973 if (new_size < kGenericMinDirectMappedDownsize) 974 return false; 975 976 // bucket->slot_size is the current size of the allocation. 977 size_t current_size = page->bucket->slot_size; 978 if (new_size == current_size) 979 return true; 980 981 char* char_ptr = static_cast<char*>(PartitionPageToPointer(page)); 982 983 if (new_size < current_size) { 984 size_t map_size = partitionPageToDirectMapExtent(page)->map_size; 985 986 // Don't reallocate in-place if new size is less than 80 % of the full 987 // map size, to avoid holding on to too much unused address space. 988 if ((new_size / kSystemPageSize) * 5 < (map_size / kSystemPageSize) * 4) 989 return false; 990 991 // Shrink by decommitting unneeded pages and making them inaccessible. 992 size_t decommitSize = current_size - new_size; 993 PartitionDecommitSystemPages(root, char_ptr + new_size, decommitSize); 994 SetSystemPagesInaccessible(char_ptr + new_size, decommitSize); 995 } else if (new_size <= partitionPageToDirectMapExtent(page)->map_size) { 996 // Grow within the actually allocated memory. Just need to make the 997 // pages accessible again. 998 size_t recommit_size = new_size - current_size; 999 bool ret = SetSystemPagesAccessible(char_ptr + current_size, recommit_size); 1000 CHECK(ret); 1001 PartitionRecommitSystemPages(root, char_ptr + current_size, recommit_size); 1002 1003 #if DCHECK_IS_ON() 1004 memset(char_ptr + current_size, kUninitializedByte, recommit_size); 1005 #endif 1006 } else { 1007 // We can't perform the realloc in-place. 1008 // TODO: support this too when possible. 1009 return false; 1010 } 1011 1012 #if DCHECK_IS_ON() 1013 // Write a new trailing cookie. 1014 PartitionCookieWriteValue(char_ptr + raw_size - kCookieSize); 1015 #endif 1016 1017 PartitionPageSetRawSize(page, raw_size); 1018 DCHECK(PartitionPageGetRawSize(page) == raw_size); 1019 1020 page->bucket->slot_size = new_size; 1021 return true; 1022 } 1023 1024 void* PartitionReallocGeneric(PartitionRootGeneric* root, 1025 void* ptr, 1026 size_t new_size, 1027 const char* type_name) { 1028 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 1029 return realloc(ptr, new_size); 1030 #else 1031 if (UNLIKELY(!ptr)) 1032 return PartitionAllocGeneric(root, new_size, type_name); 1033 if (UNLIKELY(!new_size)) { 1034 PartitionFreeGeneric(root, ptr); 1035 return 0; 1036 } 1037 1038 if (new_size > kGenericMaxDirectMapped) 1039 PartitionExcessiveAllocationSize(); 1040 1041 DCHECK(PartitionPointerIsValid(PartitionCookieFreePointerAdjust(ptr))); 1042 1043 PartitionPage* page = 1044 PartitionPointerToPage(PartitionCookieFreePointerAdjust(ptr)); 1045 1046 if (UNLIKELY(PartitionBucketIsDirectMapped(page->bucket))) { 1047 // We may be able to perform the realloc in place by changing the 1048 // accessibility of memory pages and, if reducing the size, decommitting 1049 // them. 1050 if (partitionReallocDirectMappedInPlace(root, page, new_size)) { 1051 PartitionAllocHooks::ReallocHookIfEnabled(ptr, ptr, new_size, type_name); 1052 return ptr; 1053 } 1054 } 1055 1056 size_t actual_new_size = PartitionAllocActualSize(root, new_size); 1057 size_t actual_old_size = PartitionAllocGetSize(ptr); 1058 1059 // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the 1060 // new size is a significant percentage smaller. We could do the same if we 1061 // determine it is a win. 1062 if (actual_new_size == actual_old_size) { 1063 // Trying to allocate a block of size new_size would give us a block of 1064 // the same size as the one we've already got, so re-use the allocation 1065 // after updating statistics (and cookies, if present). 1066 PartitionPageSetRawSize(page, PartitionCookieSizeAdjustAdd(new_size)); 1067 #if DCHECK_IS_ON() 1068 // Write a new trailing cookie when it is possible to keep track of 1069 // |new_size| via the raw size pointer. 1070 if (PartitionPageGetRawSizePtr(page)) 1071 PartitionCookieWriteValue(static_cast<char*>(ptr) + new_size); 1072 #endif 1073 return ptr; 1074 } 1075 1076 // This realloc cannot be resized in-place. Sadness. 1077 void* ret = PartitionAllocGeneric(root, new_size, type_name); 1078 size_t copy_size = actual_old_size; 1079 if (new_size < copy_size) 1080 copy_size = new_size; 1081 1082 memcpy(ret, ptr, copy_size); 1083 PartitionFreeGeneric(root, ptr); 1084 return ret; 1085 #endif 1086 } 1087 1088 static size_t PartitionPurgePage(PartitionPage* page, bool discard) { 1089 const PartitionBucket* bucket = page->bucket; 1090 size_t slot_size = bucket->slot_size; 1091 if (slot_size < kSystemPageSize || !page->num_allocated_slots) 1092 return 0; 1093 1094 size_t bucket_num_slots = PartitionBucketSlots(bucket); 1095 size_t discardable_bytes = 0; 1096 1097 size_t raw_size = PartitionPageGetRawSize(const_cast<PartitionPage*>(page)); 1098 if (raw_size) { 1099 uint32_t usedBytes = static_cast<uint32_t>(RoundUpToSystemPage(raw_size)); 1100 discardable_bytes = bucket->slot_size - usedBytes; 1101 if (discardable_bytes && discard) { 1102 char* ptr = reinterpret_cast<char*>(PartitionPageToPointer(page)); 1103 ptr += usedBytes; 1104 DiscardSystemPages(ptr, discardable_bytes); 1105 } 1106 return discardable_bytes; 1107 } 1108 1109 const size_t max_slot_count = 1110 (kPartitionPageSize * kMaxPartitionPagesPerSlotSpan) / kSystemPageSize; 1111 DCHECK(bucket_num_slots <= max_slot_count); 1112 DCHECK(page->num_unprovisioned_slots < bucket_num_slots); 1113 size_t num_slots = bucket_num_slots - page->num_unprovisioned_slots; 1114 char slot_usage[max_slot_count]; 1115 size_t last_slot = static_cast<size_t>(-1); 1116 memset(slot_usage, 1, num_slots); 1117 char* ptr = reinterpret_cast<char*>(PartitionPageToPointer(page)); 1118 PartitionFreelistEntry* entry = page->freelist_head; 1119 // First, walk the freelist for this page and make a bitmap of which slots 1120 // are not in use. 1121 while (entry) { 1122 size_t slotIndex = (reinterpret_cast<char*>(entry) - ptr) / slot_size; 1123 DCHECK(slotIndex < num_slots); 1124 slot_usage[slotIndex] = 0; 1125 entry = PartitionFreelistMask(entry->next); 1126 // If we have a slot where the masked freelist entry is 0, we can 1127 // actually discard that freelist entry because touching a discarded 1128 // page is guaranteed to return original content or 0. 1129 // (Note that this optimization won't fire on big endian machines 1130 // because the masking function is negation.) 1131 if (!PartitionFreelistMask(entry)) 1132 last_slot = slotIndex; 1133 } 1134 1135 // If the slot(s) at the end of the slot span are not in used, we can 1136 // truncate them entirely and rewrite the freelist. 1137 size_t truncated_slots = 0; 1138 while (!slot_usage[num_slots - 1]) { 1139 truncated_slots++; 1140 num_slots--; 1141 DCHECK(num_slots); 1142 } 1143 // First, do the work of calculating the discardable bytes. Don't actually 1144 // discard anything unless the discard flag was passed in. 1145 char* begin_ptr = nullptr; 1146 char* end_ptr = nullptr; 1147 size_t unprovisioned_bytes = 0; 1148 if (truncated_slots) { 1149 begin_ptr = ptr + (num_slots * slot_size); 1150 end_ptr = begin_ptr + (slot_size * truncated_slots); 1151 begin_ptr = reinterpret_cast<char*>( 1152 RoundUpToSystemPage(reinterpret_cast<size_t>(begin_ptr))); 1153 // We round the end pointer here up and not down because we're at the 1154 // end of a slot span, so we "own" all the way up the page boundary. 1155 end_ptr = reinterpret_cast<char*>( 1156 RoundUpToSystemPage(reinterpret_cast<size_t>(end_ptr))); 1157 DCHECK(end_ptr <= ptr + PartitionBucketBytes(bucket)); 1158 if (begin_ptr < end_ptr) { 1159 unprovisioned_bytes = end_ptr - begin_ptr; 1160 discardable_bytes += unprovisioned_bytes; 1161 } 1162 } 1163 if (unprovisioned_bytes && discard) { 1164 DCHECK(truncated_slots > 0); 1165 size_t num_new_entries = 0; 1166 page->num_unprovisioned_slots += static_cast<uint16_t>(truncated_slots); 1167 // Rewrite the freelist. 1168 PartitionFreelistEntry** entry_ptr = &page->freelist_head; 1169 for (size_t slotIndex = 0; slotIndex < num_slots; ++slotIndex) { 1170 if (slot_usage[slotIndex]) 1171 continue; 1172 PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*>( 1173 ptr + (slot_size * slotIndex)); 1174 *entry_ptr = PartitionFreelistMask(entry); 1175 entry_ptr = reinterpret_cast<PartitionFreelistEntry**>(entry); 1176 num_new_entries++; 1177 } 1178 // Terminate the freelist chain. 1179 *entry_ptr = nullptr; 1180 // The freelist head is stored unmasked. 1181 page->freelist_head = PartitionFreelistMask(page->freelist_head); 1182 DCHECK(num_new_entries == num_slots - page->num_allocated_slots); 1183 // Discard the memory. 1184 DiscardSystemPages(begin_ptr, unprovisioned_bytes); 1185 } 1186 1187 // Next, walk the slots and for any not in use, consider where the system 1188 // page boundaries occur. We can release any system pages back to the 1189 // system as long as we don't interfere with a freelist pointer or an 1190 // adjacent slot. 1191 for (size_t i = 0; i < num_slots; ++i) { 1192 if (slot_usage[i]) 1193 continue; 1194 // The first address we can safely discard is just after the freelist 1195 // pointer. There's one quirk: if the freelist pointer is actually a 1196 // null, we can discard that pointer value too. 1197 char* begin_ptr = ptr + (i * slot_size); 1198 char* end_ptr = begin_ptr + slot_size; 1199 if (i != last_slot) 1200 begin_ptr += sizeof(PartitionFreelistEntry); 1201 begin_ptr = reinterpret_cast<char*>( 1202 RoundUpToSystemPage(reinterpret_cast<size_t>(begin_ptr))); 1203 end_ptr = reinterpret_cast<char*>( 1204 RoundDownToSystemPage(reinterpret_cast<size_t>(end_ptr))); 1205 if (begin_ptr < end_ptr) { 1206 size_t partial_slot_bytes = end_ptr - begin_ptr; 1207 discardable_bytes += partial_slot_bytes; 1208 if (discard) 1209 DiscardSystemPages(begin_ptr, partial_slot_bytes); 1210 } 1211 } 1212 return discardable_bytes; 1213 } 1214 1215 static void PartitionPurgeBucket(PartitionBucket* bucket) { 1216 if (bucket->active_pages_head != &PartitionRootGeneric::gSeedPage) { 1217 for (PartitionPage* page = bucket->active_pages_head; page; 1218 page = page->next_page) { 1219 DCHECK(page != &PartitionRootGeneric::gSeedPage); 1220 (void)PartitionPurgePage(page, true); 1221 } 1222 } 1223 } 1224 1225 void PartitionPurgeMemory(PartitionRoot* root, int flags) { 1226 if (flags & PartitionPurgeDecommitEmptyPages) 1227 PartitionDecommitEmptyPages(root); 1228 // We don't currently do anything for PartitionPurgeDiscardUnusedSystemPages 1229 // here because that flag is only useful for allocations >= system page 1230 // size. We only have allocations that large inside generic partitions 1231 // at the moment. 1232 } 1233 1234 void PartitionPurgeMemoryGeneric(PartitionRootGeneric* root, int flags) { 1235 subtle::SpinLock::Guard guard(root->lock); 1236 if (flags & PartitionPurgeDecommitEmptyPages) 1237 PartitionDecommitEmptyPages(root); 1238 if (flags & PartitionPurgeDiscardUnusedSystemPages) { 1239 for (size_t i = 0; i < kGenericNumBuckets; ++i) { 1240 PartitionBucket* bucket = &root->buckets[i]; 1241 if (bucket->slot_size >= kSystemPageSize) 1242 PartitionPurgeBucket(bucket); 1243 } 1244 } 1245 } 1246 1247 static void PartitionDumpPageStats(PartitionBucketMemoryStats* stats_out, 1248 const PartitionPage* page) { 1249 uint16_t bucket_num_slots = PartitionBucketSlots(page->bucket); 1250 1251 if (PartitionPageStateIsDecommitted(page)) { 1252 ++stats_out->num_decommitted_pages; 1253 return; 1254 } 1255 1256 stats_out->discardable_bytes += 1257 PartitionPurgePage(const_cast<PartitionPage*>(page), false); 1258 1259 size_t raw_size = PartitionPageGetRawSize(const_cast<PartitionPage*>(page)); 1260 if (raw_size) 1261 stats_out->active_bytes += static_cast<uint32_t>(raw_size); 1262 else 1263 stats_out->active_bytes += 1264 (page->num_allocated_slots * stats_out->bucket_slot_size); 1265 1266 size_t page_bytes_resident = 1267 RoundUpToSystemPage((bucket_num_slots - page->num_unprovisioned_slots) * 1268 stats_out->bucket_slot_size); 1269 stats_out->resident_bytes += page_bytes_resident; 1270 if (PartitionPageStateIsEmpty(page)) { 1271 stats_out->decommittable_bytes += page_bytes_resident; 1272 ++stats_out->num_empty_pages; 1273 } else if (PartitionPageStateIsFull(page)) { 1274 ++stats_out->num_full_pages; 1275 } else { 1276 DCHECK(PartitionPageStateIsActive(page)); 1277 ++stats_out->num_active_pages; 1278 } 1279 } 1280 1281 static void PartitionDumpBucketStats(PartitionBucketMemoryStats* stats_out, 1282 const PartitionBucket* bucket) { 1283 DCHECK(!PartitionBucketIsDirectMapped(bucket)); 1284 stats_out->is_valid = false; 1285 // If the active page list is empty (== &PartitionRootGeneric::gSeedPage), 1286 // the bucket might still need to be reported if it has a list of empty, 1287 // decommitted or full pages. 1288 if (bucket->active_pages_head == &PartitionRootGeneric::gSeedPage && 1289 !bucket->empty_pages_head && !bucket->decommitted_pages_head && 1290 !bucket->num_full_pages) 1291 return; 1292 1293 memset(stats_out, '\0', sizeof(*stats_out)); 1294 stats_out->is_valid = true; 1295 stats_out->is_direct_map = false; 1296 stats_out->num_full_pages = static_cast<size_t>(bucket->num_full_pages); 1297 stats_out->bucket_slot_size = bucket->slot_size; 1298 uint16_t bucket_num_slots = PartitionBucketSlots(bucket); 1299 size_t bucket_useful_storage = stats_out->bucket_slot_size * bucket_num_slots; 1300 stats_out->allocated_page_size = PartitionBucketBytes(bucket); 1301 stats_out->active_bytes = bucket->num_full_pages * bucket_useful_storage; 1302 stats_out->resident_bytes = 1303 bucket->num_full_pages * stats_out->allocated_page_size; 1304 1305 for (const PartitionPage* page = bucket->empty_pages_head; page; 1306 page = page->next_page) { 1307 DCHECK(PartitionPageStateIsEmpty(page) || 1308 PartitionPageStateIsDecommitted(page)); 1309 PartitionDumpPageStats(stats_out, page); 1310 } 1311 for (const PartitionPage* page = bucket->decommitted_pages_head; page; 1312 page = page->next_page) { 1313 DCHECK(PartitionPageStateIsDecommitted(page)); 1314 PartitionDumpPageStats(stats_out, page); 1315 } 1316 1317 if (bucket->active_pages_head != &PartitionRootGeneric::gSeedPage) { 1318 for (const PartitionPage* page = bucket->active_pages_head; page; 1319 page = page->next_page) { 1320 DCHECK(page != &PartitionRootGeneric::gSeedPage); 1321 PartitionDumpPageStats(stats_out, page); 1322 } 1323 } 1324 } 1325 1326 void PartitionDumpStatsGeneric(PartitionRootGeneric* partition, 1327 const char* partition_name, 1328 bool is_light_dump, 1329 PartitionStatsDumper* dumper) { 1330 PartitionMemoryStats stats = {0}; 1331 stats.total_mmapped_bytes = partition->total_size_of_super_pages + 1332 partition->total_size_of_direct_mapped_pages; 1333 stats.total_committed_bytes = partition->total_size_of_committed_pages; 1334 1335 size_t direct_mapped_allocations_total_size = 0; 1336 1337 static const size_t kMaxReportableDirectMaps = 4096; 1338 1339 // Allocate on the heap rather than on the stack to avoid stack overflow 1340 // skirmishes (on Windows, in particular). 1341 std::unique_ptr<uint32_t[]> direct_map_lengths = nullptr; 1342 if (!is_light_dump) { 1343 direct_map_lengths = 1344 std::unique_ptr<uint32_t[]>(new uint32_t[kMaxReportableDirectMaps]); 1345 } 1346 1347 PartitionBucketMemoryStats bucket_stats[kGenericNumBuckets]; 1348 size_t num_direct_mapped_allocations = 0; 1349 { 1350 subtle::SpinLock::Guard guard(partition->lock); 1351 1352 for (size_t i = 0; i < kGenericNumBuckets; ++i) { 1353 const PartitionBucket* bucket = &partition->buckets[i]; 1354 // Don't report the pseudo buckets that the generic allocator sets up in 1355 // order to preserve a fast size->bucket map (see 1356 // PartitionAllocGenericInit for details). 1357 if (!bucket->active_pages_head) 1358 bucket_stats[i].is_valid = false; 1359 else 1360 PartitionDumpBucketStats(&bucket_stats[i], bucket); 1361 if (bucket_stats[i].is_valid) { 1362 stats.total_resident_bytes += bucket_stats[i].resident_bytes; 1363 stats.total_active_bytes += bucket_stats[i].active_bytes; 1364 stats.total_decommittable_bytes += bucket_stats[i].decommittable_bytes; 1365 stats.total_discardable_bytes += bucket_stats[i].discardable_bytes; 1366 } 1367 } 1368 1369 for (PartitionDirectMapExtent *extent = partition->direct_map_list; 1370 extent && num_direct_mapped_allocations < kMaxReportableDirectMaps; 1371 extent = extent->next_extent, ++num_direct_mapped_allocations) { 1372 DCHECK(!extent->next_extent || 1373 extent->next_extent->prev_extent == extent); 1374 size_t slot_size = extent->bucket->slot_size; 1375 direct_mapped_allocations_total_size += slot_size; 1376 if (is_light_dump) 1377 continue; 1378 direct_map_lengths[num_direct_mapped_allocations] = slot_size; 1379 } 1380 } 1381 1382 if (!is_light_dump) { 1383 // Call |PartitionsDumpBucketStats| after collecting stats because it can 1384 // try to allocate using |PartitionAllocGeneric| and it can't obtain the 1385 // lock. 1386 for (size_t i = 0; i < kGenericNumBuckets; ++i) { 1387 if (bucket_stats[i].is_valid) 1388 dumper->PartitionsDumpBucketStats(partition_name, &bucket_stats[i]); 1389 } 1390 1391 for (size_t i = 0; i < num_direct_mapped_allocations; ++i) { 1392 uint32_t size = direct_map_lengths[i]; 1393 1394 PartitionBucketMemoryStats stats; 1395 memset(&stats, '\0', sizeof(stats)); 1396 stats.is_valid = true; 1397 stats.is_direct_map = true; 1398 stats.num_full_pages = 1; 1399 stats.allocated_page_size = size; 1400 stats.bucket_slot_size = size; 1401 stats.active_bytes = size; 1402 stats.resident_bytes = size; 1403 dumper->PartitionsDumpBucketStats(partition_name, &stats); 1404 } 1405 } 1406 1407 stats.total_resident_bytes += direct_mapped_allocations_total_size; 1408 stats.total_active_bytes += direct_mapped_allocations_total_size; 1409 dumper->PartitionDumpTotals(partition_name, &stats); 1410 } 1411 1412 void PartitionDumpStats(PartitionRoot* partition, 1413 const char* partition_name, 1414 bool is_light_dump, 1415 PartitionStatsDumper* dumper) { 1416 static const size_t kMaxReportableBuckets = 4096 / sizeof(void*); 1417 PartitionBucketMemoryStats memory_stats[kMaxReportableBuckets]; 1418 const size_t partitionNumBuckets = partition->num_buckets; 1419 DCHECK(partitionNumBuckets <= kMaxReportableBuckets); 1420 1421 for (size_t i = 0; i < partitionNumBuckets; ++i) 1422 PartitionDumpBucketStats(&memory_stats[i], &partition->buckets()[i]); 1423 1424 // PartitionsDumpBucketStats is called after collecting stats because it 1425 // can use PartitionAlloc to allocate and this can affect the statistics. 1426 PartitionMemoryStats stats = {0}; 1427 stats.total_mmapped_bytes = partition->total_size_of_super_pages; 1428 stats.total_committed_bytes = partition->total_size_of_committed_pages; 1429 DCHECK(!partition->total_size_of_direct_mapped_pages); 1430 for (size_t i = 0; i < partitionNumBuckets; ++i) { 1431 if (memory_stats[i].is_valid) { 1432 stats.total_resident_bytes += memory_stats[i].resident_bytes; 1433 stats.total_active_bytes += memory_stats[i].active_bytes; 1434 stats.total_decommittable_bytes += memory_stats[i].decommittable_bytes; 1435 stats.total_discardable_bytes += memory_stats[i].discardable_bytes; 1436 if (!is_light_dump) 1437 dumper->PartitionsDumpBucketStats(partition_name, &memory_stats[i]); 1438 } 1439 } 1440 dumper->PartitionDumpTotals(partition_name, &stats); 1441 } 1442 1443 } // namespace base 1444 } // namespace pdfium 1445