1/* 2 * Copyright (c) 2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_APACHE_LICENSE_HEADER_START@ 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * @APPLE_APACHE_LICENSE_HEADER_END@ 19 */ 20/* 21 Zone.cpp 22 Garbage Collected Heap 23 Copyright (c) 2004-2011 Apple Inc. All rights reserved. 24 */ 25 26#include "Admin.h" 27#include "Bitmap.h" 28#include "BlockIterator.h" 29#include "Configuration.h" 30#include "Definitions.h" 31#include "Environment.h" 32#include "Large.h" 33#include "Locks.h" 34#include "Range.h" 35#include "Region.h" 36#include "Statistics.h" 37#include "Subzone.h" 38#include "Thread.h" 39#include "WriteBarrierIterator.h" 40#include "ThreadLocalCollector.h" 41#include "Zone.h" 42 43#include "auto_weak.h" 44#include "auto_trace.h" 45#include "auto_dtrace.h" 46 47#include <mach-o/dyld.h> 48#include <mach-o/ldsyms.h> 49#include <mach-o/dyld_priv.h> 50#include <sys/mman.h> 51#include <Block.h> 52#include <dispatch/private.h> 53 54struct auto_zone_cursor { 55 auto_zone_t *zone; 56 size_t garbage_count; 57 void **garbage; 58 volatile unsigned index; 59 size_t block_count; 60 size_t byte_count; 61}; 62 63 64namespace Auto { 65 66#if defined(DEBUG) 67#warning DEBUG is set 68#endif 69 70 class ResourceTracker : public AuxAllocated { 71 boolean_t (^_should_collect)(void); 72 public: 73 ResourceTracker *_next; 74 ResourceTracker *_prev; 75 char _description[0]; 76 77 ResourceTracker(const char *description, boolean_t (^test)(void), ResourceTracker *next) : _should_collect(Block_copy(test)), _next(next), _prev(NULL) { 78 strcpy(_description, description); 79 if (_next) 80 _next->_prev = this; 81 }; 82 83 static ResourceTracker *create_resource_tracker(const char *description, boolean_t (^test)(void), ResourceTracker *next) { 84 ResourceTracker *tracker = new(strlen(description)+1) ResourceTracker(description, test, next); 85 return tracker; 86 } 87 88 ~ResourceTracker() { Block_release(_should_collect); } 89 90 const char *description() { return _description; } 91 92 boolean_t probe() { return _should_collect(); } 93 94 void unlink() { 95 if (_next) 96 _next->_prev = _prev; 97 if (_prev) 98 _prev->_next = _next; 99 } 100 }; 101 102 103 // 104 // Shared information 105 // 106 Zone *Zone::_first_zone = NULL; 107 volatile int32_t Zone::_zone_count = 0; 108 109 // 110 // setup_shared 111 // 112 // Initialize information used by all zones. 113 // 114 void Zone::setup_shared() { 115 // initialize the environment 116 Environment::initialize(); 117 118 // if auxiliary malloc zone hasn't been allocated, use the default zone. 119 if (!aux_zone && !Zone::zone()) { 120 aux_zone = malloc_default_zone(); 121 } 122 } 123 124 pthread_key_t Zone::allocate_thread_key() { 125 pthread_key_t key = __sync_fetch_and_add(&_zone_count, 1) + __PTK_FRAMEWORK_GC_KEY0; 126 if (key <= __PTK_FRAMEWORK_GC_KEY9) 127 return key; 128 return 0; 129 } 130 131 // 132 // Constructor 133 // 134 Zone::Zone(pthread_key_t thread_registration_key) 135 : _registered_threads_key(thread_registration_key) 136 { 137 ASSERTION(page_size == vm_page_size); 138 139 // check to see if global information initialized 140 static dispatch_once_t is_auto_initialized = 0; 141 dispatch_once(&is_auto_initialized, ^{ setup_shared(); }); 142 143 // zone is at the beginning of data 144 void *next = displace(this, admin_offset()); 145 146 // initialize basic zone information 147 _registered_threads = NULL; 148 pthread_key_init_np(_registered_threads_key, destroy_registered_thread); 149 150 // <rdar://problem/6456504>: Set up the registered threads mutex to be recursive, so that scan_registered_threads() 151 // can reenter the mutex even when block_collector() has been called during heap monitoring. 152 pthread_mutexattr_t mutex_attr; 153 pthread_mutexattr_init(&mutex_attr); 154 pthread_mutexattr_settype(&mutex_attr, PTHREAD_MUTEX_RECURSIVE); 155 pthread_mutex_init(&_registered_threads_mutex, &mutex_attr); 156 pthread_mutex_init(&_roots_lock, &mutex_attr); 157 pthread_mutexattr_destroy(&mutex_attr); 158 pthread_rwlock_init(&_associations_lock, NULL); 159 pthread_mutex_init(&_mark_bits_mutex, NULL); 160 161 _enlivening_enabled = false; 162 _enlivening_complete = false; 163 164 // initialize subzone tracking bit map 165 _in_subzone.initialize(subzone_quantum_max, next); 166 next = displace(next, Bitmap::bytes_needed(subzone_quantum_max)); 167 168 // initialize large block tracking bit map 169 _in_large.initialize(allocate_quantum_large_max, next); 170 next = displace(next, Bitmap::bytes_needed(allocate_quantum_large_max)); 171 172#if UseArena 173 // initialize arena of large block & region tracking bit map 174 _large_bits.initialize(allocate_quantum_large_max, next); 175 _large_bits_lock = 0; 176 next = displace(next, Bitmap::bytes_needed(allocate_quantum_large_max)); 177 178 _arena = allocate_memory(1ul << arena_size_log2, 1ul << arena_size_log2); 179 if (!_arena) { 180 auto_fatal("can't allocate arena for GC\n"); 181 } 182 183 _large_start = NULL; 184 // set the coverage to everything. We probably don't need to use at all w/arenas 185 _coverage.set_range(_arena, 1ul << arena_size_log2); 186#else 187 // set up the coverage range 188 _coverage.set_range((void *)~0, (void *)0); 189#endif 190 191 _partition.initialize(this); 192 193 // initialize the large list 194 _large_list = NULL; 195 _large_lock = 0; 196 197 // initialize roots hash set. 198 _datasegments_lock = 0; 199 _zombies_lock = 0; 200 201 // initialize regions list 202 _region_list = NULL; 203 _region_lock = 0; 204 _coverage_lock = 0; 205 206 // initialize flags 207 _repair_write_barrier = false; 208 209 _state = idle; 210 211 _allocation_counter = 0; 212 213 _collection_checking_enabled = 0; 214 215 // prime the first region 216 allocate_region(); 217 218 if (_first_zone == NULL) 219 _first_zone = this; 220 221 pthread_mutex_init(&_worker_lock, NULL); 222 pthread_cond_init(&_worker_cond, NULL); 223 _has_work = false; 224 _worker_func = NULL; 225 _worker_arg = NULL; 226 _worker_count = 0; 227 _average_collection_time = 100000; // 100 ms. Seed with a large value to discourage collection at startup. 228 _sleeping_workers = 0; 229 _stats.idle_timer().start(); 230 231 pthread_mutex_init(&_compaction_lock, NULL); 232 233 // need to wait for NMOS. 234 _compaction_disabled = true; 235 236 _collection_queue = NULL; 237 _zone_init_predicate = 0; 238 239#if TARGET_IPHONE_SIMULATOR 240# warning no TLV support on iOS simulator 241#else 242 // listen for changes to thread-local storage 243 244 dyld_register_tlv_state_change_handler(dyld_tlv_state_allocated, 245 ^(enum dyld_tlv_states state, const dyld_tlv_info *info) 246 { 247 if (this->current_thread()) { 248 this->add_datasegment(info->tlv_addr, info->tlv_size); 249 } 250 }); 251 252 dyld_register_tlv_state_change_handler(dyld_tlv_state_deallocated, 253 ^(enum dyld_tlv_states state, const dyld_tlv_info *info) 254 { 255 if (this->current_thread()) { 256 this->remove_datasegment(info->tlv_addr, info->tlv_size); 257 } 258 }); 259#endif 260 } 261 262 263 // 264 // Destructor 265 // 266 Zone::~Zone() { 267 // release memory used by large 268 for (Large *large = _large_list; large; ) { 269 Large *next = large->next(); 270 large->deallocate(this); 271 large = next; 272 } 273 274 // release memory used by regions 275 for (Region *region = _region_list; region != NULL; region = region->next()) { 276 Region *next = region->next(); 277 delete region; 278 region = next; 279 } 280 _region_list = NULL; 281 282 // we don't have a clean way to tear down registered threads and give up our tsd key 283 // for now require that they already be unregistered 284 if (_registered_threads != NULL) 285 auto_error(this, "~Zone(): registered threads list not empty", NULL); 286 } 287 288 289 // 290 // memory allocation from within arena 291 // 292#if UseArena 293 // low half of arena in one region, top half used for large allocations 294 void *Zone::arena_allocate_large(usword_t size) { 295 size = align2(size, allocate_quantum_large_log2); 296 usword_t nbits = size >> allocate_quantum_large_log2; 297 // look through our arena for free space on this alignment 298 usword_t start = 0; 299 // someday... track _first_free 300 // compute quanta end point as (arena size) - (space reserved for subzones) converted to quanta 301 usword_t end = ((1ul << arena_size_log2) - ((uintptr_t)_large_start - (uintptr_t)_arena)) >> allocate_quantum_large_log2; 302 if (nbits > (end - start)) { 303 return NULL; 304 } 305 end -= nbits; // can't find anything that big past this point :-) 306 SpinLock lock(&_large_bits_lock); 307 while (start <= end) { 308 // actually, find last clear bit. If 0, we have an allocation, otherwise we have a new start XXX 309 if (_large_bits.bits_are_clear(start, nbits)) { 310 _large_bits.set_bits(start, nbits); 311 void *address = displace(_large_start, start << allocate_quantum_large_log2); 312 commit_memory(address, size); 313 return address; 314 } 315 start += 1; 316 } 317 // out of memory 318 return NULL; 319 320 } 321 322 void *Zone::arena_allocate_region(usword_t newsize) { 323 // only one region when using arena 324 if (_large_start) return NULL; 325 326 // newsize includes room for bitmaps. Just for sanity make sure it is large quantum aligned. 327 usword_t roundedsize = (newsize + subzone_quantum - 1) & ~(subzone_quantum-1); 328 _large_start = displace(_arena, roundedsize); 329 return _arena; 330 } 331 332 // 333 // raw memory deallocation 334 // 335 void Zone::arena_deallocate(void *address, size_t size) { 336 size = align2(size, allocate_quantum_large_log2); 337 usword_t nbits = size >> allocate_quantum_large_log2; 338 usword_t start = ((char *)address - (char *)_large_start) >> allocate_quantum_large_log2; 339 SpinLock lock(&_large_bits_lock); 340 _large_bits.clear_bits(start, nbits); 341 uncommit_memory(address, size); 342 //if (address < _first_free) _first_free = address; 343 } 344#else 345 // on 32-bit, goes directly to system (the entire address space is our arena) 346 void *Zone::arena_allocate_large(usword_t size) { 347 return allocate_memory(size, allocate_quantum_large, VM_MEMORY_MALLOC_LARGE); 348 } 349 350 void Zone::arena_deallocate(void *address, size_t size) { 351 deallocate_memory(address, size); 352 } 353#endif 354 355 356 // 357 // allocate_region 358 // 359 // Allocate and initialize a new region of subzones 360 // returns new (or existing) region, or NULL on true region allocation failure 361 // 362 Region *Zone::allocate_region() { 363 SpinLock lock(&_region_lock); 364 365 Region *r = _region_list; 366 while (r) { 367 if (r->subzones_remaining() != 0) 368 return r; // another thread allocated a region 369 r = r->next(); 370 } 371 372 // allocate new region 373 Region *region = Region::new_region(this); 374 375 // if allocated 376 if (region) { 377 378 { 379 SpinLock lock(&_coverage_lock); 380 381 // update coverage range 382 _coverage.expand_range(*region); 383 } 384 385 // keep region list sorted to aid in sorting free subzone blocks 386 if (_region_list == NULL || region->address() < _region_list->address()) { 387 // add to front of list 388 region->set_next(_region_list); 389 _region_list = region; 390 } else { 391 // insert the new region in the appropriate spot 392 Region *r = _region_list; 393 while (r->next() != NULL && r->next()->address() < region->address()) { 394 r = r->next(); 395 } 396 region->set_next(r->next()); 397 r->set_next(region); 398 } 399 } 400 return region; 401 } 402 403 404 405 // 406 // allocate_large 407 // 408 // Allocates a large block from the universal pool (directly from vm_memory.) 409 // 410 void *Zone::allocate_large(Thread &thread, usword_t &size, const usword_t layout, bool clear, bool refcount_is_one) { 411 Large *large = Large::allocate(this, size, layout, refcount_is_one); 412 void *address; 413 414 { 415 SpinLock lock(&_large_lock); 416 417 // Enlivening barrier needs to wrap allocation, setting _in_large bitmap, and adding to large list. 418 // Updating _in_large must be done under the enlivening lock because the collector needs _in_large 419 // to be updated in order to repend the block during enlivening. 420 ConditionBarrier barrier(thread.needs_enlivening()); 421 if (large) { 422 address = large->address(); 423 424 // mark in large bit map 425 _in_large.set_bit(Large::quantum_index(address)); 426 427 if (barrier) LargeBlockRef(large).enliven(); 428 429 // add to large list 430 large->add(_large_list); 431 } else { 432 return NULL; 433 } 434 } 435 436 // get info 437 size = large->size(); // reset size to be that of actual allocation 438 add_blocks_and_bytes(1, size); 439 440#if UseArena 441 // <rdar://problem/6150518> explicitly clear only in 64-bit, if requested, or the block is scanned. 442 if (clear || !(layout & AUTO_UNSCANNED)) { 443 bzero(address, size); 444 } 445#endif 446 447 // expand coverage of zone 448 { 449 SpinLock lock(&_coverage_lock); 450 Range large_range(address, size); 451 _coverage.expand_range(large_range); 452 } 453 454 adjust_allocation_counter(size); 455 456 return address; 457 } 458 459 460 // 461 // deallocate_large 462 // 463 // Release memory allocated for a large block. 464 // 465 void Zone::deallocate_large(Large *large, void *block) { 466 SpinLock lock(&_large_lock); 467 deallocate_large_internal(large, block); 468 } 469 470 void Zone::deallocate_large_internal(Large *large, void *block) { 471 // remove from large list 472 large->remove(_large_list); 473 474 // clear in large bit map 475 _in_large.clear_bit(Large::quantum_index(block)); 476 477 // release memory for the large block 478 large->deallocate(this); 479 } 480 481 static inline bool locked(spin_lock_t *lock) { 482 TrySpinLock attempt(lock); 483 return !attempt; 484 } 485 486 static inline bool locked(pthread_mutex_t *lock) { 487 TryMutex attempt(lock); 488 return !attempt; 489 } 490 491 static inline bool locked(pthread_rwlock_t *lock) { 492 TryWriteLock attempt(lock); 493 return !attempt; 494 } 495 496 bool Zone::is_locked() { 497 // TRY every lock. If any of them is held, we're considered locked. 498 bool result = (_partition.locked() || locked(&weak_refs_table_lock) || locked(&_large_lock) || 499 locked(&_roots_lock) || locked(&_datasegments_lock) || locked(&_zombies_lock) || 500 locked(&_region_lock) || locked(&_coverage_lock) || 501 locked(&_associations_lock) || 502#if UseArena 503 locked(&_large_bits_lock) || 504#endif 505 locked(&_registered_threads_mutex) || 506 _has_work /* to avoid deadlock, consider zone locked if it would recruit worker threads */); 507 if (!result) { 508 // check the current registered thread's enlivening queue, to see if it is locked. 509 Thread *thread = current_thread(); 510 if (thread != NULL) { 511 LockedBoolean &needs_enlivening = thread->needs_enlivening(); 512 if (locked(&needs_enlivening.lock)) 513 return true; 514 } 515 // walk all of the regions, ensure none of them are locked, which happens when adding a new subxzone. 516 for (Region *region = _region_list; region != NULL; region = region->next()) { 517 if (locked(region->subzone_lock())) { 518 return true; 519 } 520 } 521 } 522 return result; 523 } 524 525 // 526 // add_subzone 527 // 528 // find (or create) a region that can (and does) add a subzone to this admin 529 // 530 bool Zone::add_subzone(Admin *admin) { 531 // allocate_region won't actually allocate if not necessary 532 Region *r = allocate_region(); 533 return (r && r->add_subzone(admin)); 534 } 535 536 inline void clear_block(void *block, const size_t size) { 537 void **end = (void **)displace(block, size); 538 switch (size >> pointer_size_log2) { 539 case 12: end[-12] = NULL; 540 case 11: end[-11] = NULL; 541 case 10: end[-10] = NULL; 542 case 9: end[-9] = NULL; 543 case 8: end[-8] = NULL; 544 case 7: end[-7] = NULL; 545 case 6: end[-6] = NULL; 546 case 5: end[-5] = NULL; 547 case 4: end[-4] = NULL; 548 case 3: end[-3] = NULL; 549 case 2: end[-2] = NULL; 550 case 1: end[-1] = NULL; 551 case 0: break; 552 default: 553 bzero(block, size); 554 break; 555 } 556 } 557 558 // 559 // block_allocate 560 // 561 // Allocate a block of memory from the zone. layout indicates whether the block is an 562 // object or not and whether it is scanned or not. 563 // 564 void *Zone::block_allocate(Thread &thread, const size_t size, const usword_t layout, bool clear, bool refcount_is_one) { 565 void *block; 566 usword_t allocated_size = size; 567 568 // make sure we allocate at least one byte 569 if (!allocated_size) allocated_size = 1; 570 571 // try thread cache first since first N sizes dominate all other allocations 572 if (allocated_size < allocate_quantum_large) { 573 Admin &admin = _partition.admin(allocated_size, layout, refcount_is_one); 574 bool is_local = false; 575 if (allocated_size <= (allocate_quantum_small * max_cached_small_multiple)) { 576 // On a Core 2 Duo in 32-bit mode the pthread_specific takes about 60 microseconds 577 // The spinlock that it usually avoids takes about 400 microseconds 578 // The total average allocation time is now down to 960 microseconds, so the lock is phenominally expensive 579 // see if we've crossed the current thread's local block allocation threshold. if so, kick off a TLC to try to recirculate some blocks. 580 const bool cannotFinalizeNow = false; 581 if (ThreadLocalCollector::should_collect(this, thread, cannotFinalizeNow)) { 582 ThreadLocalCollector tlc(this, (void*)auto_get_sp(), thread); 583 tlc.collect(cannotFinalizeNow); 584 } 585 do { 586 block = admin.thread_cache_allocate(thread, allocated_size, layout, refcount_is_one, is_local); 587 } while (!block && add_subzone(&admin)); 588 } else { 589 do { 590 block = admin.find_allocation(thread, allocated_size, layout, refcount_is_one, is_local); 591 } while (!block && add_subzone(&admin)); 592 } 593#ifdef MEASURE_TLC_STATS 594 if (is_local) { 595 _stats.add_local_allocations(1); 596 } else { 597 _stats.add_global_allocations(1); 598 } 599#endif 600 if (block && !is_local) { 601 adjust_allocation_counter(allocated_size); // locals are counted when they escape, larges are counted in allocate_large() 602 } 603 } else { 604 // allocate more directly (32 bit: from vm, 64 bit: from top of arena) 605 block = allocate_large(thread, allocated_size, layout, clear, refcount_is_one); 606 // <rdar://problem/6150518> large blocks always come back fully cleared, either by VM itself, or by a bzero() in allocate_large(). 607 clear = false; 608 } 609 610 // if we could not allocate memory then we return here 611 if (block == NULL) return NULL; 612 613 if (should_collect()) { 614 // must not trigger thread local collection here 615 auto_zone_collect((auto_zone_t *)this, AUTO_ZONE_COLLECT_RATIO_COLLECTION|AUTO_ZONE_COLLECT_COALESCE); 616 } 617 618 // clear the block if requested. 619 if (clear) clear_block(block, allocated_size); 620 621 if (refcount_is_one) 622 GARBAGE_COLLECTION_AUTO_REFCOUNT_ONE_ALLOCATION(allocated_size); 623 624#if RECORD_REFCOUNT_STACKS 625 if (AUTO_RECORD_REFCOUNT_STACKS) { 626 auto_record_refcount_stack(this, ptr, 0); 627 } 628#endif 629 return block; 630 } 631 632 unsigned Zone::batch_allocate(Thread &thread, size_t size, const usword_t layout, bool clear, bool refcount_is_one, void **results, unsigned num_requested) { 633 usword_t allocated_size = size; 634 unsigned count = 0; 635 636 // make sure we allocate at least one byte 637 if (!allocated_size) allocated_size = 1; 638 639 if (allocated_size < allocate_quantum_large) { 640 Admin &admin = _partition.admin(allocated_size, layout, refcount_is_one); 641 count = admin.batch_allocate(thread, allocated_size, layout, refcount_is_one, clear, results, num_requested); 642 } else { 643 // we don't do bulk allocation of large 644 } 645 646 // if we could not allocate memory then we return here 647 if (count == 0) return 0; 648 649 adjust_allocation_counter(allocated_size * count); 650 651 if (should_collect()) { 652 // must not trigger thread local collection here 653 auto_zone_collect((auto_zone_t *)this, AUTO_ZONE_COLLECT_RATIO_COLLECTION|AUTO_ZONE_COLLECT_COALESCE); 654 } 655 656 if (count && refcount_is_one && GARBAGE_COLLECTION_AUTO_REFCOUNT_ONE_ALLOCATION_ENABLED()) { 657 for (unsigned i=0; i<count; i++) 658 GARBAGE_COLLECTION_AUTO_REFCOUNT_ONE_ALLOCATION(allocated_size); 659 } 660 661 return count; 662 } 663 664 // 665 // block_deallocate 666 // 667 // Release a block of memory from the zone, lazily while scanning. 668 // Called exclusively from malloc_zone_free() which means that we can assume 669 // that the memory has refcount 1. NSDeallcoateObject knows this and sends us 670 // scanned items which we can't immediately reclaim if we are indeed scanning them 671 // since we don't want the scanner to see an object at one instant and then have the 672 // memory (or isa reference) go crazy on us. 673 // 674 void Zone::block_deallocate(SubzoneBlockRef block) { 675 // BlockRef FIXME: optimize me 676 void *address = block.address(); 677 Subzone *subzone = block.subzone(); 678 usword_t q = block.q(); 679 680 // explicitly deallocated blocks must have no associations. 681 erase_associations(address); 682 683 SpinLock adminLock(subzone->admin()->lock()); 684 // XXX could build single operation to update side data once instead of two operations here 685 block.dec_refcount_no_lock(); 686 int layout = subzone->layout(q); 687 if (layout & AUTO_OBJECT) 688 erase_weak(address); 689 // enlivening_enabled only changes while admin lock held 690 // it indicates that a collection is in progress. 691 // Other scanners though - gdb/dump are vulnerable if they don't also hold the admin locks. 692 // They can't properly iterate via the admin if we're coalescing. 693 if (((layout & AUTO_UNSCANNED) == AUTO_UNSCANNED) && !_enlivening_enabled) { 694 int64_t block_size = subzone->size(q); 695 subzone->admin()->deallocate_no_lock(subzone, q, address); // ignore object -finalize work 696 add_blocks_and_bytes(-1, -block_size); 697 } 698 else { 699 // Inhibit finalization for NSDeallocateObject()'d objects. 700 // Let collector find this next round when scanner can't be looking at it 701 // Lose "Scanned" & possibly "Object" 702 // XXX we could chain these and make all scanners process them 703 subzone->set_layout(q, AUTO_MEMORY_UNSCANNED); 704 } 705 } 706 void Zone::block_deallocate(LargeBlockRef block) { 707 // BlockRef FIXME: optimize me 708 void *address = block.address(); 709 Large *large = block.large(); 710 int layout = large->layout(); 711 if (layout & AUTO_OBJECT) 712 erase_weak(address); 713 large->set_layout(AUTO_MEMORY_UNSCANNED); 714 // use the dispatch queue to deallocate the block "immediately" 715 // note that we keep a refcount on block so it won't also be found by the collector 716 if (_collection_queue) { 717 Zone *zone = this; 718 dispatch_async(_collection_queue, ^{ zone->deallocate_large(large, address); }); 719 } 720 } 721 722 // 723 // block_start_large 724 // 725 // Return the start of a large block. 726 // 727 Large *Zone::block_start_large(void *address) { 728 // Note that coverage is updated *after* a large is allocated. It may be possible for this test to fail on a large in the process of being allocated. 729 if (_coverage.in_range(address)) { 730 usword_t q = Large::quantum_index(address); 731 if (!_in_large.bit(q)) { 732 q = _in_large.previous_set(q); 733 if (q == not_found) return NULL; 734 } 735 736 // this could crash if another thread deallocates explicitly, but that's a bug we can't prevent 737#if UseArena 738 Large *large = Large::quantum_large(q, _arena); 739#else 740 Large *large = Large::quantum_large(q, (void *)0); 741#endif 742 if (!large->range().in_range(address)) return NULL; 743 744 return large; 745 } 746 747 return NULL; 748 } 749 750 751 // 752 // block_start 753 // 754 // Return the base block address of an arbitrary address. 755 // Broken down because of high frequency of use. 756 // 757 void *Zone::block_start(void *address) { 758 if (in_subzone_memory(address)) { 759 Subzone *subzone = Subzone::subzone(address); 760 usword_t q; 761 // one of the few subzone entries that guards for bad addresses 762 return subzone->block_start(address, q); 763 } else { 764 Large *large = block_start_large(address); 765 return large ? large->address() : NULL; 766 } 767 } 768 769 770 // 771 // block_layout 772 // 773 // Return the layout of a specified block. 774 // 775 usword_t Zone::block_layout(void *block) { 776 if (in_subzone_memory(block)) { 777 Subzone *subzone = Subzone::subzone(block); 778 usword_t q; 779 if (!subzone->block_is_start(block, &q)) return AUTO_TYPE_UNKNOWN; // might have a pointer to a bogus location in a subzone 780 return subzone->layout(q); 781 } else if (block_is_start_large(block)) { 782 Large *large = Large::large(block); 783 return large->layout(); 784 } 785 786 return AUTO_TYPE_UNKNOWN; 787 } 788 789 790 // 791 // block_set_layout 792 // 793 // Set the layout of a block. 794 // 795 // BlockRef FIXME: retire? 796 void Zone::block_set_layout(void *block, const usword_t layout) { 797 if (in_subzone_memory(block)) { 798 Subzone *subzone = Subzone::subzone(block); 799 usword_t q; 800 if (!subzone->block_is_start(block, &q)) return; // might have a pointer to a bogus location in a subzone 801 SpinLock lock(subzone->admin()->lock()); 802 subzone->set_layout(q, layout); 803 } else if (block_is_start_large(block)) { 804 Large *large = Large::large(block); 805 large->set_layout(layout); 806 } 807 } 808 809 810 // 811 // set_associative_ref 812 // 813 // Creates an association between a given block, a unique pointer-sized key, and a pointer value. 814 // 815 void Zone::set_associative_ref(void *block, void *key, void *value) { 816 if (value) { 817 // the thread local collector doesn't know how to track associative references 818 // Doesn't want to, either, since that would require taking the assoc lock on dealloc 819 Thread &thread = registered_thread(); 820 thread.block_escaped(value); 821 thread.block_escaped(block); 822 823 // Creating associations must enliven objects that may become garbage otherwise. 824 UnconditionalBarrier barrier(thread.needs_enlivening()); 825 WriteLock lock(&_associations_lock); 826 AssociationsHashMap::iterator i = _associations.find(block); 827 ObjectAssociationMap* refs = (i != _associations.end() ? i->second : NULL); 828 if (refs == NULL) { 829 refs = new ObjectAssociationMap(); 830 _associations[block] = refs; 831 } 832 (*refs)[key] = value; 833 if (barrier) thread.enliven_block(value); 834 } else { 835 // setting the association to NULL breaks the association. 836 WriteLock lock(&_associations_lock); 837 AssociationsHashMap::iterator i = _associations.find(block); 838 if (i != _associations.end()) { 839 ObjectAssociationMap *refs = i->second; 840 ObjectAssociationMap::iterator j = refs->find(key); 841 if (j != refs->end()) { 842 refs->erase(j); 843 } 844 } 845 } 846 } 847 848 // 849 // get_associative_ref 850 // 851 // Returns the associated pointer value for a given block and key. 852 // 853 void *Zone::get_associative_ref(void *block, void *key) { 854 ReadLock lock(&_associations_lock); 855 AssociationsHashMap::iterator i = _associations.find(block); 856 if (i != _associations.end()) { 857 ObjectAssociationMap *refs = i->second; 858 ObjectAssociationMap::iterator j = refs->find(key); 859 if (j != refs->end()) return j->second; 860 } 861 return NULL; 862 } 863 864 // 865 // get_associative_hash 866 // 867 // Returns the associated (random) hash value for a given block. 868 // 869 size_t Zone::get_associative_hash(void *block) { 870 { 871 ReadLock lock(&_associations_lock); 872 PtrSizeHashMap::iterator i = _hashes.find(block); 873 if (i != _hashes.end()) return i->second; 874 } 875 { 876 // the thread local collector doesn't know how to track associative hashes. 877 // Doesn't want to, either, since that would require taking the assoc lock on dealloc 878 Thread &thread = registered_thread(); 879 thread.block_escaped(block); 880 881 WriteLock lock(&_associations_lock); 882 PtrSizeHashMap::iterator i = _hashes.find(block); 883 if (i != _hashes.end()) return i->second; 884 return (_hashes[block] = random()); 885 } 886 } 887 888 // 889 // erase_associations_internal 890 // 891 // Assuming association lock held, do the dissassociation dance 892 // 893 inline void Zone::erase_associations_internal(void *block) { 894 AssociationsHashMap::iterator i = _associations.find(block); 895 if (i != _associations.end()) { 896 ObjectAssociationMap *refs = i->second; 897 _associations.erase(i); 898 delete refs; 899 } 900 PtrSizeHashMap::iterator h = _hashes.find(block); 901 if (h != _hashes.end()) { 902 _hashes.erase(h); 903 } 904 } 905 906 // 907 // erase_assocations 908 // 909 // Removes all associations for a given block. Used to 910 // clear associations for explicitly deallocated blocks. 911 // When the collector frees blocks, it uses a different code 912 // path, to minimize locking overhead. See free_garbage(). 913 // 914 void Zone::erase_associations(void *block) { 915 WriteLock lock(&_associations_lock); 916 erase_associations_internal(block); 917 } 918 919 void Zone::erase_associations_in_range(const Range &r) { 920 // <rdar://problem/6463922> When a bundle gets unloaded, search the associations table for keys within this range and remove them. 921 WriteLock lock(&_associations_lock); 922 PtrVector associationsToRemove; 923 for (AssociationsHashMap::iterator i = _associations.begin(); i != _associations.end(); i++) { 924 if (r.in_range(i->first)) associationsToRemove.push_back(i->first); 925 } 926 for (PtrVector::iterator i = associationsToRemove.begin(); i != associationsToRemove.end(); i++) { 927 erase_associations_internal(*i); 928 } 929 } 930 931 // 932 // visit_associations_for_key 933 // 934 // Produces all associations for a given unique key. 935 // 936 void Zone::visit_associations_for_key(void *key, boolean_t (^visitor) (void *object, void *value)) { 937 ReadLock lock(&_associations_lock); 938 for (AssociationsHashMap::iterator i = _associations.begin(); i != _associations.end(); i++) { 939 ObjectAssociationMap *refs = i->second; 940 ObjectAssociationMap::iterator j = refs->find(key); 941 if (j != refs->end()) { 942 if (!visitor(i->first, j->second)) 943 return; 944 } 945 } 946 } 947 948 // 949 // sort_free_lists 950 // 951 // Rebuilds all the admin free lists from subzone side data. Requires that the caller hold the SubzonePartition locked. 952 // The newly rebuilt free lists will be sorted. 953 // 954 void Zone::sort_free_lists() { 955 _partition.for_each(^(Admin &admin){ 956 admin.reset_free_list(); 957 }); 958 959 SpinLock lock(&_region_lock); 960 for (Region *region = _region_list; region != NULL; region = region->next()) { 961 // iterate through the subzones 962 SubzoneRangeIterator iterator(region->subzone_range()); 963 while (Subzone *subzone = iterator.next()) { 964 // get the number of quantum in the subzone 965 usword_t n = subzone->allocation_count(); 966 Admin *admin = subzone->admin(); 967 for (usword_t q = 0; q < n; q = subzone->next_quantum(q)) { 968 if (subzone->is_free(q)) { 969 void *address = subzone->quantum_address(q); 970 FreeListNode *node = new(address) FreeListNode(); 971 admin->append_node(node); 972 } 973 } 974 } 975 } 976 } 977 978 // 979 // set_write_barrier_range 980 // 981 // Set a range of write barrier bytes to the specified mark value. 982 // 983 bool Zone::set_write_barrier_range(void *destination, const usword_t size) { 984 // First, mark the card(s) associated with the destination. 985 if (in_subzone_memory(destination)) { 986 // find the subzone 987 Subzone *subzone = Subzone::subzone(destination); 988 989 // mark the write barrier 990 subzone->write_barrier().mark_cards(destination, size); 991 return true; 992 } else if (Large *large = block_start_large(destination)) { 993 // mark the write barrier 994 if (large->is_scanned()) large->write_barrier().mark_cards(destination, size); 995 return true; 996 } 997 return false; 998 } 999 1000 1001 // 1002 // set_write_barrier 1003 // 1004 // Set the write barrier byte corresponding to the specified address. 1005 // 1006 bool Zone::set_write_barrier(void *address) { 1007 if (in_subzone_memory(address)) { 1008 // find the subzone 1009 Subzone *subzone = Subzone::subzone(address); 1010 1011 // mark the write barrier 1012 subzone->write_barrier().mark_card(address); 1013 return true; 1014 } 1015 else if (Large *large = block_start_large(address)) { 1016 // mark the write barrier 1017 if (large->is_scanned()) large->write_barrier().mark_card(address); 1018 return true; 1019 } 1020 return false; 1021 } 1022 1023 struct mark_write_barriers_untouched_visitor { 1024 usword_t _count; 1025 1026 mark_write_barriers_untouched_visitor() : _count(0) {} 1027 1028 // visitor function 1029 inline bool visit(Zone *zone, WriteBarrier &wb) { 1030 // clear the write barrier 1031 _count += wb.mark_cards_untouched(); 1032 // always continue 1033 return true; 1034 } 1035 }; 1036 void Zone::mark_write_barriers_untouched() { 1037 mark_write_barriers_untouched_visitor visitor; 1038 visitWriteBarriers(this, visitor); 1039 } 1040 1041 // 1042 // clear_untouched_write_barriers 1043 // 1044 // iterate through all the write barriers and clear marks. 1045 // 1046 struct clear_untouched_write_barriers_visitor { 1047 usword_t _count; 1048 1049 clear_untouched_write_barriers_visitor() : _count(0) {} 1050 1051 // visitor function 1052 inline bool visit(Zone *zone, WriteBarrier &wb) { 1053 // clear the untouched cards. 1054 _count += wb.clear_untouched_cards(); 1055 1056 // always continue 1057 return true; 1058 } 1059 }; 1060 void Zone::clear_untouched_write_barriers() { 1061 // this must be done while the _enlivening_lock is held, to keep stragglers from missing writes. 1062 clear_untouched_write_barriers_visitor visitor; 1063 visitWriteBarriers(this, visitor); 1064 } 1065 1066 1067 // 1068 // clear_all_write_barriers 1069 // 1070 // iterate through all the write barriers and clear marks. 1071 // 1072 struct clear_all_write_barriers_visitor { 1073 // visitor function 1074 inline bool visit(Zone *zone, WriteBarrier &wb) { 1075 // clear the write barrier 1076 wb.clear(); 1077 1078 // always continue 1079 return true; 1080 } 1081 }; 1082 void Zone::clear_all_write_barriers() { 1083 // this is done while the _enlivening_lock is held, to keep stragglers from missing writes. 1084 // set up the visitor 1085 clear_all_write_barriers_visitor visitor; 1086 visitWriteBarriers(this, visitor); 1087 } 1088 1089 // 1090 // reset_all_marks 1091 // 1092 // Clears the mark flags on all blocks 1093 // 1094 void Zone::reset_all_marks() { 1095 for (Region *region = _region_list; region != NULL; region = region->next()) { 1096 region->clear_marks(); 1097 } 1098 1099 // this is called from collect_end() so should be safe. 1100 SpinLock lock(&_large_lock); 1101 for (Large *large = _large_list; large != NULL; large = large->next()) { 1102 large->clear_mark(); 1103 } 1104 } 1105 1106 1107 // 1108 // reset_all_pinned 1109 // 1110 // Clears the pinned bits on all blocks 1111 // 1112 void Zone::reset_all_pinned() { 1113 for (Region *region = _region_list; region != NULL; region = region->next()) { 1114 region->pinned().clear(); 1115 } 1116 } 1117 1118 1119 // 1120 // malloc_statistics 1121 // rummage around and tot up the requisite numbers 1122 // 1123 void Zone::malloc_statistics(malloc_statistics_t *stats) { 1124 stats->blocks_in_use = _stats.count(); 1125 stats->size_in_use = _stats.size(); 1126 stats->max_size_in_use = stats->size_allocated = 0; 1127 { 1128 SpinLock lock(&_large_lock); 1129 Large *l = _large_list; 1130 while (l) { 1131 stats->max_size_in_use += l->size(); 1132 stats->size_allocated += l->vm_size(); 1133 l = l->next(); 1134 } 1135 } 1136 1137 { 1138 SubzonePartition::Lock lock(_partition); 1139 for (Region *region = region_list(); region != NULL; region = region->next()) { 1140 // iterate through the subzones 1141 SubzoneRangeIterator iterator(region->subzone_range()); 1142 for (Subzone *sz = iterator.next(); sz != NULL; sz = iterator.next()) { 1143 size_t bytes_per_quantum = (1L<<sz->quantum_log2()); 1144 stats->max_size_in_use += sz->allocation_count() * bytes_per_quantum; 1145 stats->size_allocated += sz->allocation_limit() * bytes_per_quantum; 1146 } 1147 } 1148 } 1149 } 1150 1151 // 1152 // set_needs_enlivening 1153 // 1154 // Informs the write-barrier that blocks need repending. 1155 // 1156 void Zone::set_needs_enlivening() { 1157 close_locks(); 1158 1159 Mutex lock(&_registered_threads_mutex); 1160 _enlivening_enabled = true; 1161 for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { 1162 LockedBoolean &needs_enlivening = thread->needs_enlivening(); 1163 assert(needs_enlivening.state == false); 1164 SpinLock lock(&needs_enlivening.lock); 1165 needs_enlivening.state = true; 1166 } 1167 1168 open_locks(); 1169 } 1170 1171 // 1172 // enlivening_barrier 1173 // 1174 // Used by collectors to synchronize with concurrent mutators. 1175 // 1176 void Zone::enlivening_barrier() { 1177 // Thread Local Enlivening. 1178 // TODO: we could optimize this to allow threads to enter during one pass, and then do another pass fully locked down. 1179 Mutex lock(&_registered_threads_mutex); 1180 for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { 1181 LockedBoolean &needs_enlivening = thread->needs_enlivening(); 1182 spin_lock(&needs_enlivening.lock); 1183 } 1184 _enlivening_complete = true; 1185 } 1186 1187 1188 // 1189 // clear_needs_enlivening 1190 // 1191 // Write barriers no longer need to repend blocks. 1192 // Assumes all thread enlivening locks are held, and that _registered_threads_mutex is held. 1193 // All of those locks are released. 1194 // 1195 void Zone::clear_needs_enlivening() { 1196 Mutex lock(&_registered_threads_mutex); 1197 _enlivening_enabled = false; 1198 _enlivening_complete = false; 1199 for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { 1200 LockedBoolean &needs_enlivening = thread->needs_enlivening(); 1201 assert(needs_enlivening.state && needs_enlivening.lock != 0); 1202 needs_enlivening.state = false; 1203 spin_unlock(&needs_enlivening.lock); 1204 } 1205 } 1206 1207 // 1208 // block_collector 1209 // 1210 // Called by the monitor to prevent collections. 1211 // 1212 bool Zone::block_collector() { 1213 // Since gdb calls the root/reference tracer with all threads suspended, must 1214 // be very careful not to deadlock. 1215 if (pthread_mutex_trylock(&_mark_bits_mutex) != 0) 1216 return false; 1217 if (pthread_mutex_trylock(&_registered_threads_mutex) != 0) { 1218 pthread_mutex_unlock(&_mark_bits_mutex); 1219 return false; 1220 } 1221 return true; 1222 } 1223 1224 1225 // 1226 // unblock_collector 1227 // 1228 // Called by the monitor to enable collections. 1229 // 1230 void Zone::unblock_collector() { 1231 pthread_mutex_unlock(&_registered_threads_mutex); 1232 pthread_mutex_unlock(&_mark_bits_mutex); 1233 } 1234 1235 1236 // 1237 // collect_begin 1238 // 1239 // Indicate the beginning of the collection period. 1240 // 1241 void Zone::collect_begin() { 1242 usword_t allocated = _allocation_counter; 1243 adjust_allocation_counter(-allocated); 1244 auto_atomic_add(allocated, &_triggered_threshold); 1245 _garbage_list.commit(); 1246 } 1247 1248 1249 // 1250 // collect 1251 // 1252 // Performs the collection process. 1253 // 1254 void Zone::collect(bool is_partial, void *current_stack_bottom, CollectionTimer &timer) { 1255 1256 GARBAGE_COLLECTION_COLLECTION_PHASE_BEGIN((auto_zone_t*)this, AUTO_TRACE_SCANNING_PHASE); 1257 1258 1259 // inform mutators that they need to add objects to the enlivening queue while scanning. 1260 // we lock around the rising edge to coordinate with eager block deallocation. 1261 // Grab all other locks that use ConditionBarrier on the enlivening_lock, then grab the enlivening_lock 1262 // and mark it. This ordering guarantees that the the code using the ConditionBarrier can read the condition 1263 // without locking since they each have already acquired a lock necessary to change the needs_enlivening state. 1264 // All locks are released after setting needs_enlivening. 1265 set_needs_enlivening(); 1266 1267 // <rdar://problem/5495573> reserve all of the mark bits for exclusive use by the collector. 1268 pthread_mutex_lock(&_mark_bits_mutex); 1269 1270 // scan the heap. 1271 // recycle unused Thread objects. 1272 recycle_threads(); 1273 1274 if (is_partial) collect_partial(current_stack_bottom, timer); 1275 else collect_full(current_stack_bottom, timer); 1276 1277 GARBAGE_COLLECTION_COLLECTION_PHASE_END((auto_zone_t*)this, AUTO_TRACE_SCANNING_PHASE, _stats.blocks_scanned(), _stats.bytes_scanned()); 1278 1279 scavenge_blocks(); 1280 1281 // if weak references are present, threads will still be suspended, resume them after clearing weak references. 1282 auto_weak_callback_block_t *callbacks = NULL; 1283 if (has_weak_references()) { 1284 GARBAGE_COLLECTION_COLLECTION_PHASE_BEGIN((auto_zone_t*)this, AUTO_TRACE_WEAK_REFERENCE_PHASE); 1285 uintptr_t weak_referents, weak_references; 1286 callbacks = weak_clear_references(this, _garbage_list.count(), (vm_address_t *)_garbage_list.buffer(), &weak_referents, &weak_references); 1287 GARBAGE_COLLECTION_COLLECTION_PHASE_END((auto_zone_t*)this, AUTO_TRACE_WEAK_REFERENCE_PHASE, (uint64_t)weak_referents, (uint64_t)(weak_references * sizeof(void*))); 1288 } 1289 1290 // Write-Barrier Repair. 1291 if (!is_partial) { 1292 if (!_repair_write_barrier) { 1293 // after running a full collection, tell the next generational collection to repair the write barrier cards. 1294 _repair_write_barrier = true; 1295 mark_write_barriers_untouched(); 1296 } 1297 } else if (_repair_write_barrier) { 1298 // first generational after a full, clear all cards that are known to not have intergenerational pointers. 1299 clear_untouched_write_barriers(); 1300 _repair_write_barrier = false; 1301 } 1302 1303 // notify mutators that they no longer need to enliven objects. 1304 // No locks are acquired since enlivening lock is already held and all code that uses ConditionBarrier 1305 // is blocking on the enlivening_lock already. 1306 clear_needs_enlivening(); 1307 1308 // garbage list has been computed, can now clear the marks. 1309 reset_all_marks(); 1310 1311 // mark bits can now be reused elsewhere. 1312 pthread_mutex_unlock(&_mark_bits_mutex); 1313 1314 // release any unused pages 1315 // release_pages(); 1316 weak_call_callbacks(callbacks); 1317 1318 if (!is_partial) 1319 purge_free_space(); 1320 } 1321 1322 1323 // 1324 // collect_end 1325 // 1326 // Indicate the end of the collection period. 1327 // 1328 void Zone::collect_end(CollectionTimer &timer, size_t bytes_collected) { 1329 usword_t triggered = _triggered_threshold; 1330 auto_atomic_add(-triggered, &_triggered_threshold); 1331 1332 _average_collection_time = (_average_collection_time * 7 + timer.total_time().microseconds()) >> 3; 1333 _garbage_list.uncommit(); 1334 } 1335 1336 // 1337 // purge_free_space 1338 // 1339 // Called in response to memory pressure to relinquish pages. 1340 // 1341 usword_t Zone::purge_free_space() { 1342 SubzonePartition::Lock lock(_partition); 1343 usword_t bytes_purged = _partition.purge_free_space_no_lock(); 1344 return bytes_purged; 1345 } 1346 1347 1348 // 1349 // scavenge_blocks 1350 // 1351 // Constructs a list of all garbage blocks. 1352 // 1353 // Also ages non-garbage blocks, so we can do this while 1354 // the enlivening lock is held. This prevents a possible race 1355 // with mutators that adjust reference counts. <rdar://4801771> 1356 // 1357 struct scavenge_blocks_visitor { 1358 PointerList& _list; // accumulating list 1359 size_t &_large_count; 1360 1361 // Constructor 1362 scavenge_blocks_visitor(PointerList& list, size_t &large_count) : _list(list), _large_count(large_count) {} 1363 1364 inline bool visit(Zone *zone, Subzone *subzone, usword_t q) { 1365 if (subzone->is_thread_local(q)) return true; 1366 1367 // always age blocks, to distinguish garbage blocks from blocks allocated during finalization [4843956]. 1368 if (subzone->is_new(q)) subzone->mature(q); 1369 1370 // add unmarked blocks to the garbage list. 1371 if (!subzone->is_marked(q)) { 1372 subzone->mark_global_garbage(q); 1373 _list.add(subzone->quantum_address(q)); 1374 } 1375 1376 // always continue 1377 return true; 1378 } 1379 1380 inline bool visit(Zone *zone, Large *large) { 1381 // always age blocks, to distinguish garbage blocks from blocks allocated during finalization [4843956]. 1382 if (large->is_new()) large->mature(); 1383 1384 // add unmarked blocks to the garbage list. 1385 if (!large->is_marked()) { 1386 large->mark_garbage(); 1387 _list.add(large->address()); 1388 ++_large_count; 1389 } 1390 1391 // always continue 1392 return true; 1393 } 1394 }; 1395 1396 1397 void Zone::scavenge_blocks() { 1398 _garbage_list.clear_count(); 1399 _large_garbage_count = 0; 1400 1401 // set up the block scanvenger visitor 1402 scavenge_blocks_visitor visitor(_garbage_list, _large_garbage_count); 1403 1404 // iterate through all the blocks 1405 visitAllocatedBlocks(this, visitor); 1406#ifdef MEASURE_TLC_STATS 1407 _stats.add_global_collected(_garbage_list.count() - _large_garbage_count); 1408#endif 1409 } 1410 1411 1412 void Zone::recycle_threads() { 1413 Thread *unbound_threads = NULL; 1414 { 1415 Mutex lock(&_registered_threads_mutex); 1416 Thread::scavenge_threads(&_registered_threads, &unbound_threads); 1417 } 1418 while (unbound_threads != NULL) { 1419 Thread *next = unbound_threads->next(); 1420 delete unbound_threads; 1421 unbound_threads = next; 1422 } 1423 } 1424 1425 static void foreach_block_do(auto_zone_cursor_t cursor, void (*op) (void *ptr, void *data), void *data) { 1426 Zone *azone = (Auto::Zone *)cursor->zone; 1427 while (cursor->index < cursor->garbage_count) { 1428 void *ptr = (void *)cursor->garbage[cursor->index++]; 1429 auto_memory_type_t type = auto_zone_get_layout_type((auto_zone_t *)azone, ptr); 1430 if (type & AUTO_OBJECT) { 1431#if DEBUG 1432 if (ptr == WatchPoint) { 1433 malloc_printf("auto_zone invalidating watchpoint: %p\n", WatchPoint); 1434 } 1435#endif 1436 op(ptr, data); 1437 cursor->block_count++; 1438 cursor->byte_count += auto_zone_size((auto_zone_t *)azone, ptr); 1439 } 1440 } 1441 } 1442 1443 1444 1445 // 1446 // invalidate_garbage 1447 // 1448 void Zone::invalidate_garbage(const size_t garbage_count, void *garbage[]) { 1449#if DEBUG 1450 // when debugging, sanity check the garbage list in various ways. 1451 for (size_t index = 0; index < garbage_count; index++) { 1452 void *ptr = (void *)garbage[index]; 1453 auto_block_info_sieve<AUTO_BLOCK_INFO_REFCOUNT> block_info(this, ptr); 1454 if (block_info.refcount() > 0) 1455 malloc_printf("invalidate_garbage: garbage ptr = %p, has non-zero refcount = %d\n", ptr, block_info.refcount()); 1456 } 1457#endif 1458 struct auto_zone_cursor cursor = { (auto_zone_t *)this, garbage_count, garbage, 0, 0, 0 }; 1459 if (control.batch_invalidate) { 1460 control.batch_invalidate((auto_zone_t *)this, foreach_block_do, &cursor, sizeof(cursor)); 1461 } 1462 } 1463 1464 void Zone::handle_overretained_garbage(void *block, int rc, auto_memory_type_t layout) { 1465 char *name; 1466 if (is_object(layout)) { 1467 if (control.name_for_address) { 1468 name = control.name_for_address((auto_zone_t *)this, (vm_address_t)block, 0); 1469 } else { 1470 name = (char *)"object"; 1471 } 1472 } else { 1473 name = (char *)"non-object"; 1474 } 1475 malloc_printf("garbage block %p(%s) was over-retained during finalization, refcount = %d\n" 1476 "This could be an unbalanced CFRetain(), or CFRetain() balanced with -release.\n" 1477 "Break on auto_zone_resurrection_error() to debug.\n", block, name, rc); 1478 auto_zone_resurrection_error(); 1479 if (Auto::Environment::resurrection_is_fatal) { 1480 auto_fatal("fatal resurrection error for garbage block %p(%s): over-retained during finalization, refcount = %d", block, name, rc); 1481 } 1482 if (is_object(layout) && control.name_for_address) free(name); 1483 } 1484 1485 size_t Zone::free_garbage(const size_t subzone_garbage_count, void *subzone_garbage[], 1486 const size_t large_garbage_count, void *large_garbage[], 1487 size_t &blocks_freed, size_t &bytes_freed) { 1488 1489 blocks_freed = bytes_freed = 0; 1490 1491 if (collection_checking_enabled()) { 1492 clear_garbage_checking_count(subzone_garbage, subzone_garbage_count); 1493 clear_garbage_checking_count(large_garbage, large_garbage_count); 1494 } 1495 1496 size_t subzone_overretained_count = 0; 1497 size_t large_overretained_count = 0; 1498 { 1499 WriteLock lock(associations_lock()); 1500 if (subzone_garbage_count) { 1501 SubzonePartition::Lock lock(_partition); 1502 for (size_t index = 0; index < subzone_garbage_count; index++) { 1503 void *block = subzone_garbage[index]; 1504 Subzone *subzone = Subzone::subzone(block); 1505 usword_t q = subzone->quantum_index_unchecked(block); 1506 // we only care if it is nonzero, so don't need to check the overflow table 1507 if (!subzone->has_refcount(q)) { 1508 if ((subzone->layout(q) & AUTO_OBJECT)) erase_weak(block); 1509 blocks_freed++; 1510 bytes_freed += subzone->size(q); 1511 if (malloc_logger) malloc_logger(MALLOC_LOG_TYPE_DEALLOCATE | MALLOC_LOG_TYPE_HAS_ZONE, uintptr_t(zone), uintptr_t(block), 0, 0, 0); 1512 erase_associations_internal(block); 1513 subzone->admin()->deallocate_no_lock(subzone, q, block); 1514 } else if (is_zombie(block)) { 1515 SubzoneBlockRef ref(subzone, q); 1516 zombify_internal(ref); 1517 } else { 1518 // reuse the buffer to keep track of overretained blocks 1519 subzone_garbage[subzone_overretained_count++] = block; 1520 } 1521 } 1522 } 1523 1524 if (large_garbage_count) { 1525 SpinLock largeLock(&_large_lock); 1526 for (size_t index = 0; index < large_garbage_count; index++) { 1527 void *block = large_garbage[index]; 1528 Large *large = Large::large(block); 1529 int rc = large->refcount(); 1530 if (rc == 0) { 1531 if (large->layout() & AUTO_OBJECT) erase_weak(block); 1532 blocks_freed++; 1533 bytes_freed += large->size(); 1534 if (malloc_logger) malloc_logger(MALLOC_LOG_TYPE_DEALLOCATE | MALLOC_LOG_TYPE_HAS_ZONE, uintptr_t(zone), uintptr_t(block), 0, 0, 0); 1535 erase_associations_internal(block); 1536 deallocate_large_internal(large, block); 1537 } else if (is_zombie(block)) { 1538 LargeBlockRef ref(large); 1539 zombify_internal(ref); 1540 } else { 1541 // reuse the buffer to keep track of overretained blocks 1542 large_garbage[large_overretained_count++] = large; 1543 } 1544 } 1545 } 1546 } 1547 1548 for (size_t index = 0; index < subzone_overretained_count; index++) { 1549 SubzoneBlockRef ref(subzone_garbage[index]); 1550 handle_overretained_garbage(ref); 1551 } 1552 for (size_t index = 0; index < large_overretained_count; index++) { 1553 LargeBlockRef ref((Large *)large_garbage[index]); 1554 handle_overretained_garbage(ref); 1555 } 1556 1557 add_blocks_and_bytes(-(int64_t)blocks_freed, -(int64_t)bytes_freed); 1558 return bytes_freed; 1559 } 1560 1561 // Dispatch threads store their dispatch_queue_t in thread local storage using __PTK_LIBDISPATCH_KEY0. 1562 inline bool is_dispatch_thread() { 1563 return _pthread_getspecific_direct(__PTK_LIBDISPATCH_KEY0) != NULL && !pthread_main_np(); 1564 } 1565 1566 // 1567 // register_thread 1568 // 1569 // Add the current thread as a thread to be scanned during gc. 1570 // 1571 Thread &Zone::register_thread() { 1572 // if thread is not registered yet 1573 Thread *thread = current_thread(); 1574 if (thread == NULL) { 1575 // be a good citizen, and try to free some recycled threads before allocating more. 1576 // recycle_threads(); 1577 1578 // construct a new Thread 1579 thread = new Thread(this); 1580 1581 // is this a dispatch thread? 1582 if (_compaction_timer && is_dispatch_thread()) { 1583 if (_compaction_pending) { 1584 // when compaction timer has fired, it sets the next timer to forever from now. 1585 if (_compaction_next_time != DISPATCH_TIME_FOREVER) 1586 dispatch_source_set_timer(_compaction_timer, DISPATCH_TIME_FOREVER, 0, 0); 1587 _compaction_pending = false; 1588 } 1589 } 1590 1591 // add thread to linked list of registered threads 1592 Mutex lock(&_registered_threads_mutex); 1593 thread->set_next(_registered_threads); 1594 LockedBoolean &needs_enlivening = thread->needs_enlivening(); 1595 needs_enlivening.state = _enlivening_enabled; 1596 _registered_threads = thread; 1597 if (_enlivening_complete) 1598 spin_lock(&needs_enlivening.lock); 1599 1600#if ! TARGET_IPHONE_SIMULATOR 1601 // add any existing __thread storage to the root set 1602 dyld_enumerate_tlv_storage( 1603 ^(enum dyld_tlv_states state, const dyld_tlv_info *info) 1604 { 1605 this->add_datasegment(info->tlv_addr, info->tlv_size); 1606 }); 1607#endif 1608 } 1609 pthread_setspecific(_registered_threads_key, thread); 1610 return *thread; 1611 } 1612 1613 1614 // 1615 // unregister_thread 1616 // 1617 void Zone::unregister_thread() { 1618 } 1619 1620 // 1621 // destroy_registered_thread 1622 // 1623 // Pthread key destructor. The collector has a critical dependency on the ordering of pthread destructors. 1624 // This destructor must run after any other code which might possibly call into the collector. 1625 // We have arranged with pthreads to have our well known key destructor called after any dynamic keys and 1626 // any static (Apple internal) keys that might call into the collector (Foundation, CF). On the last iteration 1627 // (PTHREAD_DESTRUCTOR_ITERATIONS) we unregister the thread. 1628 // Note that this implementation is non-portable due to our agreement with pthreads. 1629 // 1630 void Zone::destroy_registered_thread(void *key_value) { 1631 if (key_value != INVALID_THREAD_KEY_VALUE) { 1632 Thread *thread = (Thread *)key_value; 1633 Zone *zone = thread->zone(); 1634 pthread_key_t thread_key = zone->_registered_threads_key; 1635 if (thread->increment_tsd_count() == PTHREAD_DESTRUCTOR_ITERATIONS) { 1636 // <rdar://problem/6514886>: Deleting the thread object while the collector is 1637 // enumerating the list is probably not worth the extra effort here. The collector 1638 // will scavenge the list, and eventually recycle thread objects, during the next collection. 1639 thread->unbind(); 1640 // Set the value to a token that marks the thread as unregistered. 1641 // If this thread calls into the collector again (tries to look up a Thread instance) then we define it as a fatal error. 1642 key_value = INVALID_THREAD_KEY_VALUE; 1643 } 1644 pthread_setspecific(thread_key, key_value); 1645 } 1646 } 1647 1648 // These accessors provide a way to enumerate the registered threads safely but without holding 1649 // the registered threads mutex. Threads are prevented from exiting by holding each thread's 1650 // spin lock while its stack is scanned. The lock is always acquired and released while 1651 // the registered threads mutex is locked, to ensure the integrity of the list. Since newly 1652 // registered threads are always added to the beginning of the list, the enumeration won't include 1653 // newly registered threads. The enlivening phase of the collector takes care of that. 1654 1655 inline Thread *Zone::firstScannableThread() { 1656 Mutex lock(&_registered_threads_mutex); 1657 for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { 1658 if (thread->lockForScanning()) return thread; 1659 } 1660 return NULL; 1661 } 1662 1663 inline Thread *Zone::nextScannableThread(Thread *thread) { 1664 Mutex lock(&_registered_threads_mutex); 1665 thread->unlockForScanning(); 1666 for (thread = thread->next(); thread != NULL; thread = thread->next()) { 1667 if (thread->lockForScanning()) return thread; 1668 } 1669 return NULL; 1670 } 1671 1672 // 1673 // scan_registered_threads 1674 // 1675 // Safely enumerates registered threads during stack scanning. 1676 // 1677 void Zone::scan_registered_threads(thread_visitor_t visitor) { 1678 for (Thread *thread = firstScannableThread(); thread != NULL; thread = nextScannableThread(thread)) { 1679 // visitor is guaranteed to only see threads locked for scanning. 1680 visitor(thread); 1681 } 1682 } 1683 1684#ifndef __BLOCKS__ 1685 class Zone_thread_visitor_helper : public Zone::thread_visitor { 1686 void (*_visitor) (Thread *, void *); 1687 void *_arg; 1688 public: 1689 Zone_thread_visitor_helper(void (*visitor) (Thread *, void *), void *arg) : _visitor(visitor), _arg(arg) {} 1690 virtual void operator () (Thread *thread) { _visitor(thread, _arg); } 1691 }; 1692#endif 1693 1694 void Zone::scan_registered_threads(void (*visitor) (Thread *, void *), void *arg) { 1695#ifdef __BLOCKS__ 1696 scan_registered_threads(^(Thread *thread) { visitor(thread, arg); }); 1697#else 1698 Zone_thread_visitor_helper helper(visitor, arg); 1699 scan_registered_threads(helper); 1700#endif 1701 } 1702 1703 // 1704 // suspend_all_registered_threads 1705 // 1706 // Suspend all registered threads. Provided for heap snapshots. 1707 // Acquires the registered threads mutex so that no new threads can enter the system. 1708 // 1709 void Zone::suspend_all_registered_threads() { 1710 pthread_mutex_lock(&_registered_threads_mutex); 1711 for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { 1712 thread->suspend(); 1713 } 1714 } 1715 1716 1717 // 1718 // resume_all_registered_threads 1719 // 1720 // Resumes all suspended registered threads. Provided for heap snapshots. 1721 // Relinquishes the registered threads mutex. 1722 // 1723 void Zone::resume_all_registered_threads() { 1724 for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { 1725 thread->resume(); 1726 } 1727 pthread_mutex_unlock(&_registered_threads_mutex); 1728 } 1729 1730 1731 // 1732 // worker_thread_loop 1733 // 1734 // Helper function for recruit_worker_threads() used to get worker threads from dispatch_apply_f. 1735 // 1736 void Zone::worker_thread_loop(void *context, size_t step) { 1737 Zone *zone = (Zone *)context; 1738 zone->do_volunteer_for_work(true, true); 1739 } 1740 1741 1742 // 1743 // recruit_worker_threads 1744 // 1745 // Registers func as a work function. Threads will be recruited to call func repeatedly until it returns false. 1746 // func should perform a chunk of work and then return true if more work remains or false if all work is done. 1747 // The calling thread becomes a worker and does not return until all work is complete. 1748 // 1749 void Zone::perform_work_with_helper_threads(boolean_t (*work)(void *arg, boolean_t is_dedicated, boolean_t work_to_completion), void *arg) { 1750 pthread_mutex_lock(&_worker_lock); 1751 assert(_worker_count == 0); 1752 assert(_worker_func == NULL); 1753 assert(_worker_arg == NULL); 1754 1755 _worker_arg = arg; 1756 _worker_func = work; 1757 _has_work = true; 1758 pthread_mutex_unlock(&_worker_lock); 1759 1760 // This thread becomes a worker thread until all work is done. 1761 dispatch_queue_t q = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, DISPATCH_QUEUE_OVERCOMMIT); 1762 dispatch_apply_f((auto_ncpus()+1)/2, q, this, worker_thread_loop); 1763 1764 // ensure that all worker threads have exited before we return 1765 pthread_mutex_lock(&_worker_lock); 1766 while (_worker_count != 0) { 1767 pthread_cond_wait(&_worker_cond, &_worker_lock); 1768 } 1769 _has_work = false; 1770 _worker_arg = NULL; 1771 _worker_func = NULL; 1772 pthread_mutex_unlock(&_worker_lock); 1773 } 1774 1775 1776 // 1777 // do_volunteer_for_work 1778 // 1779 // Helper function for volunteer_for_work(). This actually calls the work function. 1780 // If work_to_completion is true then the function loops until there is no more work. 1781 // If work_to_completion is false then the work function is called once. 1782 // 1783 boolean_t Zone::do_volunteer_for_work(boolean_t is_dedicated, boolean_t work_to_completion) { 1784 boolean_t more_work = false; 1785 1786 // Test if worker thread recruiting is enabled. This test is unsynchronized, so we might miss sometimes for true volunteeer threads. 1787 pthread_mutex_lock(&_worker_lock); 1788 if (_has_work && (_worker_count < (size_t)auto_ncpus())) { 1789 _worker_count++; 1790 worker_print("starting (dedicated = %s, work_to_completion = %s)\n", is_dedicated ? "true" : "false", work_to_completion ? "true" : "false"); 1791 do { 1792 pthread_mutex_unlock(&_worker_lock); 1793 more_work = _worker_func(_worker_arg, is_dedicated, work_to_completion); 1794 pthread_mutex_lock(&_worker_lock); 1795 1796 if (more_work) { 1797 // if there might be more work wake up any sleeping threads 1798 if (_sleeping_workers > 0) { 1799 pthread_cond_broadcast(&_worker_cond); 1800 } 1801 } else { 1802 if (work_to_completion) { 1803 if ((_sleeping_workers + 1) < _worker_count) { 1804 _sleeping_workers++; 1805 pthread_cond_wait(&_worker_cond, &_worker_lock); 1806 _sleeping_workers--; 1807 more_work = _has_work; 1808 } 1809 } 1810 } 1811 } while (more_work && work_to_completion); 1812 worker_print("exiting (dedicated = %s, work_to_completion = %s)\n", is_dedicated ? "true" : "false", work_to_completion ? "true" : "false"); 1813 1814 // when a work_to_completion thread exits the loop we know all the work is done 1815 if (work_to_completion && _has_work) { 1816 // this will cause all sleeping worker threads to fall out of the loop 1817 _has_work = false; 1818 } 1819 _worker_count--; 1820 if (_worker_count == _sleeping_workers) { 1821 pthread_cond_broadcast(&_worker_cond); 1822 } 1823 } 1824 pthread_mutex_unlock(&_worker_lock); 1825 return more_work; 1826 } 1827 1828 1829 void Zone::register_resource_tracker(const char *description, boolean_t (^should_collect)(void)) 1830 { 1831 Mutex lock(&_resource_tracker_lock); 1832 ResourceTracker *tracker = ResourceTracker::create_resource_tracker(description, should_collect, _resource_tracker_list); 1833 _resource_tracker_list = tracker; 1834 } 1835 1836 void Zone::unregister_resource_tracker(const char *description) 1837 { 1838 Mutex lock(&_resource_tracker_lock); 1839 ResourceTracker *tracker = _resource_tracker_list; 1840 while (tracker && strcmp(tracker->description(), description)) 1841 tracker = tracker->_next; 1842 if (tracker) { 1843 if (tracker == _resource_tracker_list) 1844 _resource_tracker_list = tracker->_next; 1845 tracker->unlink(); 1846 delete tracker; 1847 } 1848 } 1849 1850 boolean_t Zone::resource_tracker_wants_collection() { 1851 bool collect = false; 1852 Mutex lock(&_resource_tracker_lock); 1853 if (_resource_tracker_list) { 1854 ResourceTracker *tracker = _resource_tracker_list; 1855 while (tracker && !tracker->probe()) 1856 tracker = tracker->_next; 1857 if (tracker) { 1858 if (control.log & AUTO_LOG_COLLECTIONS) { 1859 malloc_printf("triggering collection due to external resource tracker: %s\n", tracker->description()); 1860 } 1861 collect = true; 1862 } 1863 } 1864 return collect; 1865 } 1866 1867 boolean_t Zone::should_collect() { 1868 boolean_t collect = false; 1869 1870 volatile int64_t *last_should_collect_time = _stats.last_should_collect_time(); 1871 int64_t start = *last_should_collect_time; 1872 WallClockTimeDataSource wallTime; 1873 int64_t current_time = wallTime.current_time(); 1874 1875 // Don't examine the statistics too often. Every 10ms is sufficient. */ 1876 if ((wallTime.microseconds_duration(start, current_time) > 10 * 1000 /* 10 ms */) && 1877 OSAtomicCompareAndSwap64(start, current_time, last_should_collect_time)) { 1878 1879 // only try to collect if there has been recent allocation activity 1880 if (_allocation_counter > control.collection_threshold) { 1881 1882 /* 1883 This algrithm aims to have the collector running with a particular duty cycle (x% of the time). 1884 The collector tracks how long collections take, and the time to wait is computed from the duty cycle. 1885 total time = run time + idle time 1886 And we want x% duty cycle, so 1887 run time = total time * x% 1888 Solving for the desired idle time between collections gives: 1889 idle time = run time * (1/x - 1) 1890 */ 1891 WallClockTimer &idle_timer = _stats.idle_timer(); 1892 uint64_t elapsed = idle_timer.elapsed_microseconds(); 1893 if (elapsed > 10 * USEC_PER_SEC) { 1894 // it's been a long time since the last collection, so ignore duty cycle and collect (safety net) 1895 collect = true; 1896 } else { 1897 double target_duty_cycle = Environment::default_duty_cycle; 1898 uint64_t target_idle_time = ((double)_average_collection_time / target_duty_cycle) * (1.0 - target_duty_cycle); 1899 1900 // collect if long enough since last collection 1901 collect = elapsed > target_idle_time; 1902 } 1903 } 1904 if (!collect) { 1905 collect = resource_tracker_wants_collection(); 1906 } 1907 } 1908 return collect; 1909 } 1910 1911 // 1912 // print_all_blocks 1913 // 1914 // Prints all allocated blocks. 1915 // 1916 struct print_all_blocks_visitor { 1917 Region *_last_region; // previous region visited 1918 Subzone *_last_subzone; // previous admin visited 1919 bool _is_large; 1920 1921 // Constructor 1922 print_all_blocks_visitor() : _last_region(NULL), _is_large(false) {} 1923 1924 // visitor function 1925 inline bool visit(Zone *zone, Subzone *subzone, usword_t q) { 1926 // if transitioning then print appropriate banner 1927 if (_last_region != subzone->region()) { 1928 _last_region = subzone->region(); 1929 malloc_printf("Region [%p..%p]\n", _last_region->address(), _last_region->end()); 1930 } 1931 1932 void *block = subzone->quantum_address(q); 1933 if (subzone->is_start(q)) { 1934 zone->print_block(SubzoneBlockRef(subzone, q), ""); 1935 } else { 1936 FreeListNode *node = (FreeListNode *)block; 1937 malloc_printf(" %p(%6d) ### free\n", block, node->size()); 1938 } 1939 1940 // always continue 1941 return true; 1942 } 1943 1944 inline bool visit(Zone *zone, Large *large) { 1945 if (!_is_large) { 1946 malloc_printf("Large Blocks\n"); 1947 _is_large = true; 1948 } 1949 1950 zone->print_block(LargeBlockRef(large), ""); 1951 1952 // always continue 1953 return true; 1954 } 1955 }; 1956 void Zone::print_all_blocks() { 1957 SpinLock lock(&_region_lock); 1958 print_all_blocks_visitor visitor; 1959 visitAllBlocks(this, visitor); 1960 } 1961 1962 1963 // 1964 // print block 1965 // 1966 // Print the details of a block 1967 // 1968 template <class BlockRef> void Zone::print_block(BlockRef block, const char *tag) { 1969 char *name = NULL; 1970 if (block.is_object()) { 1971 if (control.name_for_address) { 1972 name = control.name_for_address((auto_zone_t *)this, (vm_address_t)block.address(), 0); 1973 } 1974 } 1975 char desc[64]; 1976 block.get_description(desc, sizeof(desc)); 1977 1978 malloc_printf("%s%p(%6d) %s %s %s %s rc(%d) %s %s\n", 1979 tag, block.address(), (unsigned)block.size(), 1980 block.is_scanned() ? "scn" : " ", 1981 block.is_object() ? "obj" : "mem", 1982 block.is_new() ? "new" : " ", 1983 block.is_marked() ? "mark" : " ", 1984 block.refcount(), 1985 desc, 1986 name ? name : ""); 1987 if (name) free(name); 1988 } 1989 1990}; 1991 1992 1993