/* * Copyright (c) 2009 Apple Inc. All rights reserved. * * @APPLE_APACHE_LICENSE_HEADER_START@ * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * * @APPLE_APACHE_LICENSE_HEADER_END@ */ /* AutoZone.cpp Copyright (c) 2004-2010 Apple Inc. All rights reserved. */ #include "AutoAdmin.h" #include "AutoBitmap.h" #include "AutoBlockIterator.h" #include "AutoCollector.h" #include "AutoConfiguration.h" #include "AutoDefs.h" #include "AutoEnvironment.h" #include "AutoLarge.h" #include "AutoLock.h" #include "AutoRange.h" #include "AutoRegion.h" #include "AutoStatistics.h" #include "AutoSubzone.h" #include "AutoMemoryScanner.h" #include "AutoThread.h" #include "AutoWriteBarrierIterator.h" #include "AutoThreadLocalCollector.h" #include "AutoZone.h" #include "auto_weak.h" #include "auto_trace.h" #include "auto_dtrace.h" #include #include #include struct auto_zone_cursor { auto_zone_t *zone; size_t garbage_count; const vm_address_t *garbage; volatile unsigned index; size_t block_count; size_t byte_count; }; namespace Auto { #if defined(DEBUG) #warning DEBUG is set #endif // // Shared information // Zone *Zone::_first_zone = NULL; volatile int32_t Zone::_zone_count = 0; // // setup_shared // // Initialize information used by all zones. // void Zone::setup_shared() { // initialize the environment Environment::initialize(); // if auxiliary malloc zone hasn't been allocated, use the default zone. if (!aux_zone && !Zone::zone()) { aux_zone = malloc_default_zone(); } } pthread_key_t Zone::allocate_thread_key() { pthread_key_t key = __sync_fetch_and_add(&_zone_count, 1) + __PTK_FRAMEWORK_GC_KEY0; if (key <= __PTK_FRAMEWORK_GC_KEY9) return key; return 0; } // // Constructor // Zone::Zone(pthread_key_t thread_registration_key) : _registered_threads_key(thread_registration_key), _page_allocator(_stats), _garbage_list(_page_allocator) { ASSERTION(page_size == vm_page_size); // Force non-lazy symbol binding for libauto and below, // to prevent deadlocks in dyld while we stop threads. // This is deprecated API yet no new way to do this yet (Oct08), rdar unknown NSLookupSymbolInImage((const mach_header*)&_mh_dylib_header, "___", NSLOOKUPSYMBOLINIMAGE_OPTION_BIND_FULLY); // check to see if global information initialized static dispatch_once_t is_auto_initialized = 0; dispatch_once(&is_auto_initialized, ^{ setup_shared(); }); // zone is at the beginning of data void *next = displace(this, admin_offset()); // initialize basic zone information _registered_threads = NULL; pthread_key_init_np(_registered_threads_key, destroy_registered_thread); // : Set up the registered threads mutex to be recursive, so that scan_registered_threads() // can reenter the mutex even when block_collector() has been called during heap monitoring. pthread_mutexattr_t mutex_attr; pthread_mutexattr_init(&mutex_attr); pthread_mutexattr_settype(&mutex_attr, PTHREAD_MUTEX_RECURSIVE); pthread_mutex_init(&_registered_threads_mutex, &mutex_attr); pthread_mutexattr_destroy(&mutex_attr); pthread_mutex_init(&_mark_bits_mutex, NULL); _enlivening_enabled = false; _enlivening_complete = false; // initialize subzone tracking bit map _in_subzone.initialize(subzone_quantum_max, next); next = displace(next, Bitmap::bytes_needed(subzone_quantum_max)); // initialize large block tracking bit map _in_large.initialize(allocate_quantum_large_max, next); next = displace(next, Bitmap::bytes_needed(allocate_quantum_large_max)); #if UseArena // initialize arena of large block & region tracking bit map _large_bits.initialize(allocate_quantum_large_max, next); _large_bits_lock = 0; next = displace(next, Bitmap::bytes_needed(allocate_quantum_large_max)); _arena = allocate_memory(1ul << arena_size_log2, 1ul << arena_size_log2); if (!_arena) { auto_fatal("can't allocate arena for GC\n"); } _large_start = NULL; // set the coverage to everything. We probably don't need to use at all w/arenas _coverage.set_range(_arena, 1ul << arena_size_log2); #else // set up the coverage range _coverage.set_range((void *)~0, (void *)0); #endif _small_admin.initialize(this, allocate_quantum_small_log2); _medium_admin.initialize(this, allocate_quantum_medium_log2); // initialize the large list _large_list = NULL; _large_lock = 0; // initialize roots hash set. _roots_lock = 0; _datasegments_lock = 0; _zombies_lock = 0; // initialize regions list _region_list = NULL; _region_lock = 0; _retains_lock = 0; _coverage_lock = 0; // initialize flags _repair_write_barrier = false; #if GLOBAL_ENLIVENING_QUEUE _needs_enlivening.state = false; _needs_enlivening.lock = 0; #endif _state = idle; // initialize statistics _stats.reset(); usword_t data_size = bytes_needed(); _stats.add_admin(data_size); _allocation_threshold = 0; // prime the first region allocate_region(); if (_first_zone == NULL) _first_zone = this; } // // Destructor // Zone::~Zone() { // release memory used by large for (Large *large = _large_list; large; ) { Large *next = large->next(); large->deallocate(this); large = next; } // release memory used by regions for (Region *region = _region_list; region != NULL; region = region->next()) { Region *next = region->next(); delete region; region = next; } _region_list = NULL; // we don't have a clean way to tear down registered threads and give up our tsd key // for now require that they already be unregistered if (_registered_threads != NULL) auto_error(this, "~Zone(): registered threads list not empty\n", NULL); } // // memory allocation from within arena // #if UseArena // low half of arena in one region, top half used for large allocations void *Zone::arena_allocate_large(usword_t size) { usword_t seeksize = (size + allocate_quantum_large - 1) & ~(allocate_quantum_large-1); usword_t nbits = seeksize >> allocate_quantum_large_log2; // look through our arena for free space on this alignment usword_t start = 0; // someday... track _first_free usword_t end = ((1ul << arena_size_log2) - ((uintptr_t)_large_start - (uintptr_t)_arena)) >> allocate_quantum_large_log2; if (nbits > (end - start)) { return NULL; } end -= nbits; // can't find anything that big past this point :-) SpinLock lock(&_large_bits_lock); while (start <= end) { // actually, find last clear bit. If 0, we have an allocation, otherwise we have a new start XXX if (_large_bits.bits_are_clear(start, nbits)) { _large_bits.set_bits(start, nbits); void *address = displace(_large_start, start << allocate_quantum_large_log2); madvise(address, seeksize, MADV_FREE_REUSE); return address; } start += 1; } // out of memory return NULL; } void *Zone::arena_allocate_region(usword_t newsize) { // only one region when using arena if (_large_start) return NULL; // newsize includes room for bitmaps. Just for sanity make sure it is large quantum aligned. usword_t roundedsize = (newsize + subzone_quantum - 1) & ~(subzone_quantum-1); _large_start = displace(_arena, roundedsize); return _arena; } // // raw memory deallocation // void Zone::arena_deallocate(void *address, size_t size) { usword_t seeksize = (size + allocate_quantum_large - 1) & ~(allocate_quantum_large-1); usword_t nbits = seeksize >> allocate_quantum_large_log2; usword_t start = ((char *)address - (char *)_large_start) >> allocate_quantum_large_log2; SpinLock lock(&_large_bits_lock); _large_bits.clear_bits(start, nbits); madvise(address, seeksize, MADV_FREE_REUSABLE); //if (address < _first_free) _first_free = address; } #else // on 32-bit, goes directly to system (the entire address space is our arena) void *Zone::arena_allocate_large(usword_t size) { return allocate_memory(size, allocate_quantum_large, VM_MEMORY_MALLOC_LARGE); } void Zone::arena_deallocate(void *address, size_t size) { deallocate_memory(address, size); } #endif // // allocate_region // // Allocate and initialize a new region of subzones // returns new (or existing) region, or NULL on true region allocation failure // Region *Zone::allocate_region() { SpinLock lock(&_region_lock); if (_region_list && _region_list->subzones_remaining() != 0) return _region_list; // another thread helped us out // allocate new region Region *region = Region::new_region(this); // if allocated if (region) { { SpinLock lock(&_coverage_lock); // update coverage range _coverage.expand_range(*region); } // add to front of list region->set_next(_region_list); _region_list = region; // set up scan stack if (!_scan_stack.is_allocated()) { _scan_stack.set_range(region->scan_space()); } } return region; } // // allocate_large // // Allocates a large block from the universal pool (directly from vm_memory.) // void *Zone::allocate_large(Thread &thread, usword_t &size, const unsigned layout, bool clear, bool refcount_is_one) { Large *large = Large::allocate(this, size, layout, refcount_is_one); void *address; { SpinLock lock(&_large_lock); // Enlivening barrier needs to wrap allocation, setting _in_large bitmap, and adding to large list. // Updating _in_large must be done under the enlivening lock because the collector needs _in_large // to be updated in order to repend the block during enlivening. EnliveningHelper barrier(thread); if (large) { address = large->address(); // mark in large bit map _in_large.set_bit(Large::quantum_index(address)); if (barrier) barrier.enliven_block(address); // add to large list large->add(_large_list); } else { return NULL; } } // get info size = large->size(); // reset size to be that of actual allocation #if UseArena // explicitly clear only in 64-bit, if requested, or the block is scanned. if (clear || !(layout & AUTO_UNSCANNED)) { bzero(address, size); } #endif // expand coverage of zone { SpinLock lock(&_coverage_lock); Range large_range(address, size); _coverage.expand_range(large_range); } // update statistics _stats.add_count(1); _stats.add_size(size); _stats.add_dirty(size); _stats.add_allocated(size); adjust_threshold_counter(size); return address; } // // deallocate_large // // Release memory allocated for a large block. // void Zone::deallocate_large(void *block) { // locate large admin information. Large *large = Large::large(block); // update statistics usword_t size = large->size(); _stats.add_count(-1); _stats.add_size(-size); // bytes in use _stats.add_allocated(-size); // vm required for bytes in use (100%) _stats.add_dirty(-size); // dirty bytes required for bytes in use (100%) // remove from large list SpinLock lock(&_large_lock); large->remove(_large_list); // clear in large bit map _in_large.clear_bit(Large::quantum_index(block)); // release memory for the large block large->deallocate(this); } static inline bool locked(spin_lock_t *lock) { TrySpinLock attempt(lock); return !attempt; } static inline bool locked(pthread_mutex_t *lock) { TryMutex attempt(lock); return !attempt; } bool Zone::is_locked() { // TRY every lock. If any of them is held, we're considered locked. bool result = (locked(_small_admin.lock()) || locked(_medium_admin.lock()) || locked(&weak_refs_table_lock) || locked(&_large_lock) || locked(&_roots_lock) || locked(&_datasegments_lock) || locked(&_zombies_lock) || locked(&_region_lock) || locked(&_retains_lock) || locked(&_coverage_lock) || locked(&_associations_lock) || #if UseArena locked(&_large_bits_lock) || #endif locked(&_registered_threads_mutex)); if (!result) { // check the current registered thread's enlivening queue, to see if it is locked. Thread *thread = current_thread(); if (thread != NULL) { LockedBoolean &needs_enlivening = thread->needs_enlivening(); if (locked(&needs_enlivening.lock)) return true; } // walk all of the regions, ensure none of them are locked, which happens when adding a new subxzone. for (Region *region = _region_list; region != NULL; region = region->next()) { if (locked(region->subzone_lock())) { return true; } } } return result; } // // add_subzone // // find (or create) a region that can (and does) add a subzone to this admin // bool Zone::add_subzone(Admin *admin) { control.will_grow((auto_zone_t *)this, AUTO_HEAP_SUBZONE_EXHAUSTED); if (!_region_list->add_subzone(admin)) { control.will_grow((auto_zone_t *)this, AUTO_HEAP_REGION_EXHAUSTED); // although we don't hold the region lock between these checks, its okay // since allocate_region won't actually allocate if not necessary if (allocate_region() == NULL) return false; } return true; } // // block_allocate // // Allocate a block of memory from the zone. layout indicates whether the block is an // object or not and whether it is scanned or not. // void *Zone::block_allocate(Thread &thread, const size_t size, const unsigned layout, bool clear, bool refcount_is_one) { void *block; usword_t allocated_size = size; bool did_grow = false, is_large = false; // make sure we allocate at least one byte if (!allocated_size) allocated_size = 1; // try thread cache first since first N sizes dominate all other allocations if (allocated_size <= (allocate_quantum_small * max_cached_small_multiple)) { // On a Core 2 Duo in 32-bit mode the pthread_specific takes about 60 microseconds // The spinlock that it usually avoids takes about 400 microseconds // The total average allocation time is now down to 960 microseconds, so the lock is phenominally expensive // 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. const bool cannotFinalizeNow = false; if (ThreadLocalCollector::should_collect(this, thread, cannotFinalizeNow)) { ThreadLocalCollector tlc(this, (void*)auto_get_sp(), thread); tlc.collect(cannotFinalizeNow); } do { block = _small_admin.thread_cache_allocate(thread, allocated_size, layout, refcount_is_one, did_grow); } while (!block && add_subzone(&_small_admin)); } else if (allocated_size < allocate_quantum_medium) { // use small admin do { block = _small_admin.find_allocation(thread, allocated_size, layout, refcount_is_one, did_grow); } while (!block && add_subzone(&_small_admin)); } else if (allocated_size < allocate_quantum_large) { // use medium admin do { block = _medium_admin.find_allocation(thread, allocated_size, layout, refcount_is_one, did_grow); } while (!block && add_subzone(&_medium_admin)); } else { // allocate more directly (32 bit: from vm, 64 bit: from top of arena) block = allocate_large(thread, allocated_size, layout, clear, refcount_is_one); is_large = true; } // if we could not allocate memory then we return here if (block == NULL) return NULL; // update statistics for non-cache allocation _stats.add_count(1); _stats.add_size(allocated_size); adjust_threshold_counter(allocated_size); if (threshold_reached() && multithreaded) { auto_collect((auto_zone_t *)this, AUTO_COLLECT_RATIO_COLLECTION, NULL); // rdar:... Don't trip the thread local collector... } if (did_grow) { control.will_grow((auto_zone_t *)this, AUTO_HEAP_HOLES_EXHAUSTED); } // large blocks always come back fully cleared, either by VM itself, or by a bzero() in allocate_large(). if (is_large) return block; // initialize block if (clear) { void **end = (void **)displace(block, allocated_size); switch (allocated_size/sizeof(void *)) { case 12: end[-12] = NULL; case 11: end[-11] = NULL; case 10: end[-10] = NULL; case 9: end[-9] = NULL; case 8: end[-8] = NULL; case 7: end[-7] = NULL; case 6: end[-6] = NULL; case 5: end[-5] = NULL; case 4: end[-4] = NULL; case 3: end[-3] = NULL; case 2: end[-2] = NULL; case 1: end[-1] = NULL; case 0: break; default: bzero(block, allocated_size); break; } } #if RECORD_REFCOUNT_STACKS if (AUTO_RECORD_REFCOUNT_STACKS) { auto_record_refcount_stack(this, ptr, 0); } #endif #if LOG_TIMINGS size_t allocated = _stats.size(); if ((allocated & ~(LOG_ALLOCATION_THRESHOLD-1)) != ((allocated - size) & ~(LOG_ALLOCATION_THRESHOLD-1))) log_allocation_threshold(auto_date_now(), _stats.size(), _stats.allocated()); #endif return block; } // // block_deallocate // // Release a block of memory from the zone, lazily while scanning. // Called exclusively from malloc_zone_free() which means that we can assume // that the memory has refcount 1. NSDeallcoateObject knows this and sends us // scanned items which we can't immediately reclaim if we are indeed scanning them // since we don't want the scanner to see an object at one instant and then have the // memory (or isa reference) go crazy on us. // void Zone::block_deallocate(void *block) { // explicitly deallocated blocks must have no associations. erase_associations(block); if (in_subzone_memory(block)) { // TODO: we could handle ALL block freeing this way, instead of swapping the semantics of deallocate_large(). Subzone *subzone = Subzone::subzone(block); if (!subzone->block_is_start(block)) return; // might be a bogus address SpinLock adminLock(subzone->admin()->lock()); // XXX could build single operation to update side data once instead of two operations here dec_refcount_small_medium(subzone, block); int layout = subzone->layout(block); if (layout & AUTO_OBJECT) erase_weak(block); // enlivening_enabled only changes while admin lock held // it indicates that a collection is in progress. // Other scanners though - gdb/dump are vulnerable if they don't also hold the admin locks. // They can't properly iterate via the admin if we're coalescing. if (((layout & AUTO_UNSCANNED) == AUTO_UNSCANNED) && !_enlivening_enabled) { subzone->admin()->deallocate_no_lock(block); // ignore object -finalize work } else { // Inhibit finalization for NSDeallocateObject()'d objects. // Let collector find this next round when scanner can't be looking at it // Lose "Scanned" & possibly "Object" // XXX we could chain these and make all scanners process them subzone->set_layout(block, AUTO_MEMORY_UNSCANNED); } } else if (in_large_memory(block) && Large::is_start(block)) { Large *large = Large::large(block); int layout = large->layout(); if (layout & AUTO_OBJECT) erase_weak(block); large->set_layout(AUTO_MEMORY_UNSCANNED); #if USE_DISPATCH_QUEUE // use the dispatch queue to deallocate the block "immediately" // note that we keep a refcount on block so it won't also be found by the collector if (collection_queue) { Zone *zone = this; dispatch_async(collection_queue, ^{ zone->deallocate_large(block); }); } #else block_decrement_refcount(block); #endif } else { error("Deallocating a non-block", block); } } // // block_start_large // // Return the start of a large block. // void *Zone::block_start_large(void *address) { // 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. if (_coverage.in_range(address)) { SpinLock lock(&_large_lock); // guard against concurrent deallocation. usword_t q = Large::quantum_index(address); if (!_in_large.bit(q)) { q = _in_large.previous_set(q); if (q == not_found) return NULL; } // this could crash if another thread deallocates explicitly, but that's a bug we can't prevent #if UseArena Large *large = Large::quantum_large(q, _arena); #else Large *large = Large::quantum_large(q, (void *)0); #endif if (!large->range().in_range(address)) return NULL; return large->address(); } return NULL; } // // block_start // // Return the base block address of an arbitrary address. // Broken down because of high frequency of use. // void *Zone::block_start(void *address) { if (in_subzone_memory(address)) { Subzone *subzone = Subzone::subzone(address); // one of the few subzone entries that guards for bad addresses return subzone->block_start(address); } else { return block_start_large(address); } } // // block_size // // Return the size of a specified block. // usword_t Zone::block_size(void *block) { if (in_subzone_memory(block)) { Subzone *subzone = Subzone::subzone(block); if (subzone->block_is_start(block)) return subzone->size(block); } else if (in_large_memory(block) && Large::is_start(block)) { return Large::size(block); } return 0; } // // block_layout // // Return the layout of a specified block. // int Zone::block_layout(void *block) { if (in_subzone_memory(block)) { Subzone *subzone = Subzone::subzone(block); if (!subzone->block_is_start(block)) return AUTO_TYPE_UNKNOWN; // might have a pointer to a bogus location in a subzone return subzone->layout(block); } else if (in_large_memory(block) && Large::is_start(block)) { return Large::layout(block); } return AUTO_TYPE_UNKNOWN; } // // block_set_layout // // Set the layout of a block. // void Zone::block_set_layout(void *block, int layout) { if (in_subzone_memory(block)) { Subzone *subzone = Subzone::subzone(block); if (!subzone->block_is_start(block)) return; // might have a pointer to a bogus location in a subzone SpinLock lock(subzone->admin()->lock()); subzone->set_layout(block, layout); } else if (in_large_memory(block) && Large::is_start(block)) { Large::set_layout(block, layout); } } // // get_refcount_small_medium // // Return the refcount of a small/medium block. // int Zone::get_refcount_small_medium(Subzone *subzone, void *block) { int refcount = subzone->refcount(block); if (refcount == 3) { // non-zero reference count, check the overflow table. SpinLock lock(&_retains_lock); PtrIntHashMap::iterator retain_iter = _retains.find(block); if (retain_iter != _retains.end() && retain_iter->first == block) { refcount = retain_iter->second; } } return refcount; } // // inc_refcount_small_medium // // Increments the refcount of a small/medium block, returning the new value. // Requires subzone->admin()->lock() to be held, to protect side data. // int Zone::inc_refcount_small_medium(Subzone *subzone, void *block) { usword_t q = subzone->quantum_index(block); int refcount = subzone->refcount(q); if (refcount == 3) { // non-trivial reference count, check the overflow table. SpinLock lock(&_retains_lock); PtrIntHashMap::iterator retain_iter = _retains.find(block); if (retain_iter != _retains.end() && retain_iter->first == block) { refcount = ++retain_iter->second; } else { // transition from 3 -> 4 refcount = (_retains[block] = 4); } } else { // transition from 0 -> 1, 1 -> 2, 2 -> 3 if (refcount == 0) { Thread &thread = registered_thread(); thread.block_escaped(this, subzone, block); } subzone->incr_refcount(q); ++refcount; } return refcount; } // // dec_refcount_small_medium // // Decrements the refcount of a small/medium block, returning the new value. // Requires subzone->admin()->lock() to be held, to protect side data. // int Zone::dec_refcount_small_medium(Subzone *subzone, void *block) { usword_t q = subzone->quantum_index(block); int refcount = subzone->refcount(q); if (refcount == 3) { // non-trivial reference count, check the overflow table. SpinLock lock(&_retains_lock); PtrIntHashMap::iterator retain_iter = _retains.find(block); if (retain_iter != _retains.end() && retain_iter->first == block) { if (--retain_iter->second == 3) { // transition from 4 -> 3 _retains.erase(retain_iter); return 3; } else { return retain_iter->second; } } else { // transition from 3 -> 2 subzone->decr_refcount(q); return 2; } } else if (refcount > 0) { subzone->decr_refcount(q); return refcount - 1; } // underflow. malloc_printf("reference count underflow for %p, break on auto_refcount_underflow_error to debug.\n", block); auto_refcount_underflow_error(block); return -1; } // // block_refcount // // Returns the reference count of the specified block, or zero. // int Zone::block_refcount(void *block) { if (in_subzone_memory(block)) { Subzone *subzone = Subzone::subzone(block); if (!subzone->block_is_start(block)) return 0; // might have a pointer to a bogus location in a subzone return get_refcount_small_medium(Subzone::subzone(block), block); } else if (in_large_memory(block) && Large::is_start(block)) { SpinLock lock(&_large_lock); return Large::refcount(block); } return 0; } #if 0 void Zone::testRefcounting(void *block) { for (int j = 0; j < 7; ++j) { printf("\nloop start refcount is %d for %p\n", block_refcount(block), block); for (int i = 0; i < 5; ++i) { block_increment_refcount(block); printf("after increment, it now has refcount %d\n", block_refcount(block)); } for (int i = 0; i < 5; ++i) { block_decrement_refcount(block); printf("after decrement, it now has refcount %d\n", block_refcount(block)); } for (int i = 0; i < 5; ++i) { block_increment_refcount(block); printf("after increment, it now has refcount %d\n", block_refcount(block)); } for (int i = 0; i < 5; ++i) { block_decrement_refcount(block); printf("after decrement, it now has refcount %d\n", block_refcount(block)); } printf("maturing block...\n"); Subzone::subzone(block)->mature(block); } } #endif // // block_increment_refcount // // Increment the reference count of the specified block. // int Zone::block_increment_refcount(void *block) { int refcount = 0; if (in_subzone_memory(block)) { Subzone *subzone = Subzone::subzone(block); if (!subzone->block_is_start(block)) return 0; // might have a pointer to a bogus location in a subzone SpinLock lock(subzone->admin()->lock()); refcount = inc_refcount_small_medium(subzone, block); // 0->1 transition. Must read _needs_enlivening while inside allocation lock. // Otherwise might miss transition and then collector might have passed over this block while refcount was 0. if (refcount == 1) { EnliveningHelper barrier(registered_thread()); if (barrier && !block_is_marked(block)) barrier.enliven_block(block); } } else if (in_large_memory(block) && Large::is_start(block)) { SpinLock lock(&_large_lock); refcount = Large::refcount(block) + 1; Large::set_refcount(block, refcount); if (refcount == 1) { EnliveningHelper barrier(registered_thread()); if (barrier && !block_is_marked(block)) barrier.enliven_block(block); } } return refcount; } // // block_decrement_refcount // // Decrement the reference count of the specified block. // int Zone::block_decrement_refcount(void *block) { if (in_subzone_memory(block)) { Subzone *subzone = Subzone::subzone(block); if (!subzone->block_is_start(block)) return 0; // might have a pointer to a bogus location in a subzone SpinLock lock(subzone->admin()->lock()); return dec_refcount_small_medium(subzone, block); } else if (in_large_memory(block) && Large::is_start(block)) { SpinLock lock(&_large_lock); int refcount = Large::refcount(block); if (refcount <= 0) { malloc_printf("reference count underflow for %p, break on auto_refcount_underflow_error to debug\n", block); auto_refcount_underflow_error(block); } else { refcount = refcount - 1; Large::set_refcount(block, refcount); } return refcount; } return 0; } void Zone::block_refcount_and_layout(void *block, int *refcount, int *layout) { if (in_subzone_memory(block)) { Subzone *subzone = Subzone::subzone(block); if (!subzone->block_is_start(block)) return; // might have a pointer to a bogus location in a subzone SpinLock lock(subzone->admin()->lock()); *refcount = get_refcount_small_medium(subzone, block); *layout = subzone->layout(block); } else if (in_large_memory(block) && Large::is_start(block)) { SpinLock lock(&_large_lock); Large *large = Large::large(block); *refcount = large->refcount(); *layout = large->layout(); } } // // set_associative_ref // // Creates an association between a given block, a unique pointer-sized key, and a pointer value. // void Zone::set_associative_ref(void *block, void *key, void *value) { if (value) { // the thread local collector doesn't know how to track associative references // Doesn't want to, either, since that would require taking the assoc lock on dealloc Thread &thread = registered_thread(); thread.block_escaped(this, NULL, value); thread.block_escaped(this, NULL, block); // Creating associations must enliven objects that may become garbage otherwise. EnliveningHelper barrier(thread); SpinLock lock(&_associations_lock); AssocationsHashMap::iterator i = _associations.find(block); ObjectAssocationHashMap* refs = (i != _associations.end() ? i->second : NULL); if (refs == NULL) { refs = new ObjectAssocationHashMap(); _associations[block] = refs; } (*refs)[key] = value; if (barrier) barrier.enliven_block(value); } else { // setting the association to NULL breaks the association. SpinLock lock(&_associations_lock); AssocationsHashMap::iterator i = _associations.find(block); if (i != _associations.end()) { ObjectAssocationHashMap *refs = i->second; ObjectAssocationHashMap::iterator j = refs->find(key); if (j != refs->end()) { refs->erase(j); } } } } // // get_associative_ref // // Returns the associated pointer value for a given block and key. // void *Zone::get_associative_ref(void *block, void *key) { SpinLock lock(&_associations_lock); AssocationsHashMap::iterator i = _associations.find(block); if (i != _associations.end()) { ObjectAssocationHashMap *refs = i->second; ObjectAssocationHashMap::iterator j = refs->find(key); if (j != refs->end()) return j->second; } return NULL; } // // erase_associations_internal // // Assuming association lock held, do the dissassociation dance // inline void Zone::erase_associations_internal(void *block) { AssocationsHashMap::iterator i = _associations.find(block); if (i != _associations.end()) { ObjectAssocationHashMap *refs = i->second; _associations.erase(i); delete refs; } } // // erase_assocations // // Removes all associations for a given block. Used to // clear associations for explicitly deallocated blocks. // When the collector frees blocks, it uses a different code // path, to minimize locking overhead. See free_garbage(). // void Zone::erase_associations(void *block) { SpinLock lock(&_associations_lock); erase_associations_internal(block); } // // scan_associations // // Iteratively visits all associatively referenced objects. Only one pass over the // associations table is necessary, as the set_pending() method is sensitive to whether // associations are being scanned, and when blocks are newly marked, associations are also // recursively pended. // void Zone::scan_associations(MemoryScanner &scanner) { // Prevent other threads from breaking existing associations. We already own the enlivening lock. SpinLock lock(&_associations_lock); // tell set_pending() to recursively pend associative references. _scanning_associations = true; // consider associative references. these are only reachable if their primary block is. for (AssocationsHashMap::iterator i = _associations.begin(); i != _associations.end(); i++) { void *address = i->first; if (associations_should_be_marked(address)) { ObjectAssocationHashMap *refs = i->second; for (ObjectAssocationHashMap::iterator j = refs->begin(); j != refs->end(); j++) { scanner.associate_block((void**)address, j->first, j->second); } } } // scan through all pending blocks until there are no new pending scanner.scan_pending_until_done(); _scanning_associations = false; } void Zone::pend_associations(void *block, MemoryScanner &scanner) { AssocationsHashMap::iterator i = _associations.find(block); if (i != _associations.end()) { ObjectAssocationHashMap *refs = i->second; for (ObjectAssocationHashMap::iterator j = refs->begin(); j != refs->end(); j++) { scanner.associate_block((void**)block, j->first, j->second); } } } void Zone::erase_associations_in_range(const Range &r) { // When a bundle gets unloaded, search the associations table for keys within this range and remove them. SpinLock lock(&_associations_lock); PtrVector associationsToRemove; for (AssocationsHashMap::iterator i = _associations.begin(); i != _associations.end(); i++) { if (r.in_range(i->first)) associationsToRemove.push_back(i->first); } for (PtrVector::iterator i = associationsToRemove.begin(); i != associationsToRemove.end(); i++) { erase_associations_internal(*i); } } // // set_write_barrier // // Set the write barrier byte corresponding to the specified address. // If scanning is going on then the value is marked pending. // bool Zone::set_write_barrier(Thread &thread, void *address, void *value) { if (in_subzone_memory(address)) { // find the subzone Subzone *subzone = Subzone::subzone(address); thread.track_local_assignment(this, address, value); EnliveningHelper barrier(thread); if (barrier && !block_is_marked(value)) barrier.enliven_block(value); *(void **)address = value; // rdar://5512883 // mark the write barrier subzone->write_barrier().mark_card(address); return true; } else if (thread.is_stack_address(address)) { *(void **)address = value; return true; } else if (void *block = block_start_large(address)) { // get the large block Large *large = Large::large(block); EnliveningHelper barrier(thread); if (barrier && !block_is_marked(value)) barrier.enliven_block(value); *(void **)address = value; // rdar://5512883 thread.block_escaped(this, NULL, value); // mark the write barrier if (large->is_scanned()) large->write_barrier().mark_card(address); return true; } thread.block_escaped(this, NULL, value); return false; } // // set_write_barrier_range // // Set a range of write barrier bytes to the specified mark value. // bool Zone::set_write_barrier_range(void *destination, const usword_t size) { // First, mark the card(s) associated with the destination. if (in_subzone_memory(destination)) { // find the subzone Subzone *subzone = Subzone::subzone(destination); // mark the write barrier subzone->write_barrier().mark_cards(destination, size); return true; } else if (void *block = block_start_large(destination)) { Large *large = Large::large(block); // mark the write barrier if (large->is_scanned()) large->write_barrier().mark_cards(destination, size); return true; } return false; } // // set_write_barrier // // Set the write barrier byte corresponding to the specified address. // bool Zone::set_write_barrier(void *address) { if (in_subzone_memory(address)) { // find the subzone Subzone *subzone = Subzone::subzone(address); // mark the write barrier subzone->write_barrier().mark_card(address); return true; } else if (void *block = block_start_large(address)) { // get the large block Large *large = Large::large(block); // mark the write barrier if (large->is_scanned()) large->write_barrier().mark_card(address); return true; } return false; } struct mark_write_barriers_untouched_visitor { usword_t _count; mark_write_barriers_untouched_visitor() : _count(0) {} // visitor function inline bool visit(Zone *zone, WriteBarrier &wb) { // clear the write barrier _count += wb.mark_cards_untouched(); // always continue return true; } }; void Zone::mark_write_barriers_untouched() { mark_write_barriers_untouched_visitor visitor; visitWriteBarriers(this, visitor); } // // clear_untouched_write_barriers // // iterate through all the write barriers and clear marks. // struct clear_untouched_write_barriers_visitor { usword_t _count; clear_untouched_write_barriers_visitor() : _count(0) {} // visitor function inline bool visit(Zone *zone, WriteBarrier &wb) { // clear the untouched cards. _count += wb.clear_untouched_cards(); // always continue return true; } }; void Zone::clear_untouched_write_barriers() { // this must be done while the _enlivening_lock is held, to keep stragglers from missing writes. clear_untouched_write_barriers_visitor visitor; visitWriteBarriers(this, visitor); } // // clear_all_write_barriers // // iterate through all the write barriers and clear marks. // struct clear_all_write_barriers_visitor { // visitor function inline bool visit(Zone *zone, WriteBarrier &wb) { // clear the write barrier wb.clear(); // always continue return true; } }; void Zone::clear_all_write_barriers() { // this is done while the _enlivening_lock is held, to keep stragglers from missing writes. // set up the visitor clear_all_write_barriers_visitor visitor; visitWriteBarriers(this, visitor); } // // reset_all_marks // // Clears the mark flags on all blocks // struct reset_all_marks_visitor { inline bool visit(Zone *zone, Subzone *subzone, usword_t q, void *block) { // clear block's new flag subzone->clear_mark(q); // always continue return true; } inline bool visit(Zone *zone, Large *large, void *block) { // clear block's new flag large->clear_mark(); // always continue return true; } }; void Zone::reset_all_marks() { #if 1 // XXX_PCB: marks are now in their own separate BitMaps, so just clear their live ranges. for (Region *region = _region_list; region != NULL; region = region->next()) { region->clear_all_marks(); } // this is called from collect_end() so should be safe. SpinLock lock(&_large_lock); for (Large *large = _large_list; large != NULL; large = large->next()) { large->clear_mark(); } #else // set up all marks visitor reset_all_marks_visitor visitor; // set up iterator BlockIterator iterator(this, visitor); // visit all the admins iterator.visit(); #endif } // // reset_all_marks_and_pending // // Clears the mark and ending flags on all blocks // struct reset_all_marks_and_pending_visitor { inline bool visit(Zone *zone, Subzone *subzone, usword_t q) { // clear block's mark & pending flags subzone->clear_mark(q); subzone->clear_pending(q); // always continue return true; } inline bool visit(Zone *zone, Large *large) { // clear block's mark & pending flags large->clear_mark(); large->clear_pending(); // always continue return true; } }; void Zone::reset_all_marks_and_pending() { // NOTE: the enlivening lock must be held here, which should keep the region and large lists stable. // NOTE: marks are now in their own separate BitMaps, so just clear their live ranges. for (Region *region = _region_list; region != NULL; region = region->next()) { region->clear_all_marks(); region->clear_all_pending(); } SpinLock lock(&_large_lock); for (Large *large = _large_list; large != NULL; large = large->next()) { large->clear_mark(); large->clear_pending(); } } // // statistics // // Returns the statistics for this zone. // struct statistics_visitor { Statistics &_stats; Region *_last_region; Subzone *_last_subzone; statistics_visitor(Statistics &stats) : _stats(stats) , _last_region(NULL) , _last_subzone(NULL) {} inline bool visit(Zone *zone, Subzone *subzone, usword_t q) { // assumes that subzones are iterated linearly across all regions if (_last_region != subzone->region()) { _last_region = subzone->region(); _stats.add_admin(Region::bytes_needed()); } if (_last_subzone != subzone) { _last_subzone = subzone; _stats.add_admin(subzone_write_barrier_max); _stats.add_allocated(subzone->allocation_size()); _stats.add_dirty(subzone->allocation_size()); } _stats.add_count(1); _stats.add_size(subzone->size(q)); return true; } inline bool visit(Zone *zone, Large *large) { _stats.add_admin(large->vm_size() - large->size()); _stats.add_count(1); _stats.add_size(large->size()); return true; } }; void Zone::statistics(Statistics &stats) { statistics_visitor visitor(stats); visitAllocatedBlocks(this, visitor); } // // malloc_statistics // rummage around and tot up the requisite numbers // void Zone::malloc_statistics(malloc_statistics_t *stats) { stats->blocks_in_use = 0; stats->size_in_use = 0; stats->max_size_in_use = 0; stats->size_allocated = 0; { SpinLock lock(&_large_lock); Large *l = _large_list; while (l) { stats->blocks_in_use++; stats->size_in_use += l->vm_size(); stats->max_size_in_use += l->vm_size(); stats->size_allocated += l->vm_size(); l = l->next(); } } { SpinLock lock(&_region_lock); Region *r = _region_list; while (r) { r->malloc_statistics(stats); r = r->next(); } } } // // set_needs_enlivening // // Informs the write-barrier that blocks need repending. // void Zone::set_needs_enlivening() { close_locks(); Mutex lock(&_registered_threads_mutex); _enlivening_enabled = true; for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { LockedBoolean &needs_enlivening = thread->needs_enlivening(); assert(needs_enlivening.state == false); SpinLock lock(&needs_enlivening.lock); needs_enlivening.state = true; } open_locks(); } class scan_barrier_visitor { MemoryScanner &_scanner; public: scan_barrier_visitor(MemoryScanner &scanner) : _scanner(scanner) {} void visitPointerChunk(void **pointers, void **limit) { while (pointers < limit) { _scanner.repend(*pointers++); } } }; // // enlivening_barrier // // Used by collectors to synchronize with concurrent mutators. // void Zone::enlivening_barrier(MemoryScanner &scanner) { // write barriers should no longer repend blocks // NOTE: this assumes NO THREADS ARE SUSPENDED at this point. // NOTE: we exit scanning with all thread-local enlivening locks and thread list mutex held, and the thread list mutex, so that // no new threads can enter the system, until this round of scanning completes. scan_barrier_visitor visitor(scanner); // Thread Local Enlivening Queues. // TODO: we could optimize this to allow threads to enter during one pass, and then do another pass fully locked down. // TODO: move this into Zone::scan_barrier(), to preserve the lock ownership. pthread_mutex_lock(&_registered_threads_mutex); for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { EnliveningQueue &enlivening_queue = thread->enlivening_queue(); LockedBoolean &needs_enlivening = enlivening_queue.needs_enlivening(); spin_lock(&needs_enlivening.lock); visitPointerChunks(enlivening_queue.chunks(), enlivening_queue.count(), visitor); enlivening_queue.reset(); } _enlivening_complete = true; } // // clear_needs_enlivening // // Write barriers no longer need to repend blocks. // Assumes all thread enlivening locks are held, and that _registered_threads_mutex is held. // All of those locks are released. // void Zone::clear_needs_enlivening() { _enlivening_enabled = false; _enlivening_complete = false; for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { LockedBoolean &needs_enlivening = thread->needs_enlivening(); assert(needs_enlivening.state && (!__is_threaded || needs_enlivening.lock != 0)); needs_enlivening.state = false; spin_unlock(&needs_enlivening.lock); } // this balances the final pthread_mutex_lock() in enlivening_barrier(). pthread_mutex_unlock(&_registered_threads_mutex); } // // block_collector // // Called by the monitor to prevent collections. // bool Zone::block_collector() { // Since gdb calls the root/reference tracer with all threads suspended, must // be very careful not to deadlock. if (pthread_mutex_trylock(&_mark_bits_mutex) != 0) return false; if (pthread_mutex_trylock(&_registered_threads_mutex) != 0) { pthread_mutex_unlock(&_mark_bits_mutex); return false; } return true; } // // unblock_collector // // Called by the monitor to enable collections. // void Zone::unblock_collector() { pthread_mutex_unlock(&_registered_threads_mutex); pthread_mutex_unlock(&_mark_bits_mutex); } // // collect // // Performs the collection process. // void Zone::collect(bool is_partial, void *current_stack_bottom, auto_date_t *enliveningBegin) { GARBAGE_COLLECTION_COLLECTION_PHASE_BEGIN((auto_zone_t*)this, AUTO_TRACE_SCANNING_PHASE); // inform mutators that they need to add objects to the enlivening queue while scanning. // we lock around the rising edge to coordinate with eager block deallocation. // Grab all other locks that use ConditionBarrier on the enlivening_lock, then grab the enlivening_lock // and mark it. This ordering guarantees that the the code using the ConditionBarrier can read the condition // without locking since they each have already acquired a lock necessary to change the needs_enlivening state. // All locks are released after setting needs_enlivening. set_needs_enlivening(); // construct collector Collector collector(this, current_stack_bottom, is_partial); // reserve all of the mark bits for exclusive use by the collector. pthread_mutex_lock(&_mark_bits_mutex); // run collector in scan stack mode collector.collect(false); // check if stack overflow occurred if (_scan_stack.is_overflow()) { _stats.increment_stack_overflow_count(); // let go of the thread list mutex and per-thread _enlivening_locks, which were acquired by Collector::scan_barrier(). clear_needs_enlivening(); // Don't deadlock with concurrent allocation/reference counting of large blocks. reset_all_marks_and_pending(); set_needs_enlivening(); // try again using pending bits collector.collect(true); } _scan_stack.reset(); GARBAGE_COLLECTION_COLLECTION_PHASE_END((auto_zone_t*)this, AUTO_TRACE_SCANNING_PHASE, (uint64_t)collector.blocks_scanned(), (uint64_t)collector.bytes_scanned()); auto_weak_callback_block_t *callbacks = NULL; // update stats - XXX_PCB only count completed collections. *enliveningBegin = collector.scan_end; _stats.increment_gc_count(is_partial); // XXX_PCB VMAddressList uses aux_malloc(), which could deadlock if some other thread holds the stack logging spinlock. // XXX_PCB this issue is being tracked in . _garbage_list.clear_count(); scavenge_blocks(); // if weak references are present, threads will still be suspended, resume them after clearing weak references. if (has_weak_references()) { GARBAGE_COLLECTION_COLLECTION_PHASE_BEGIN((auto_zone_t*)this, AUTO_TRACE_WEAK_REFERENCE_PHASE); uintptr_t weak_referents, weak_references; callbacks = weak_clear_references(this, _garbage_list.count(), (vm_address_t *)_garbage_list.buffer(), &weak_referents, &weak_references); GARBAGE_COLLECTION_COLLECTION_PHASE_END((auto_zone_t*)this, AUTO_TRACE_WEAK_REFERENCE_PHASE, (uint64_t)weak_referents, (uint64_t)(weak_references * sizeof(void*))); } // Write-Barrier Repair. if (!is_partial) { if (!_repair_write_barrier) { // after running a full collection, tell the next generational collection to repair the write barrier cards. _repair_write_barrier = true; mark_write_barriers_untouched(); } } else if (_repair_write_barrier) { // first generational after a full, clear all cards that are known to not have intergenerational pointers. clear_untouched_write_barriers(); _repair_write_barrier = false; } // notify mutators that they no longer need to enliven objects. // No locks are acquired since enlivening lock is already held and all code that uses ConditionBarrier // is blocking on the enlivening_lock already. clear_needs_enlivening(); // garbage list has been computed, can now clear the marks. reset_all_marks(); // mark bits can now be reused elsewhere. pthread_mutex_unlock(&_mark_bits_mutex); // recycle unused Thread objects. recycle_threads(); // release any unused pages // release_pages(); weak_call_callbacks(callbacks); // malloc_printf("Zone::collect(): partial_gc_count = %ld, full_gc_count = %ld, aborted_gc_count = %ld\n", // _stats.partial_gc_count(), _stats.full_gc_count(), _stats.aborted_gc_count()); // malloc_printf("collector.stack_scanned() = %u\n", collector.stack_scanned()); if (Environment::print_stats) { malloc_printf("cnt=%d, sz=%d, max=%d, al=%d, admin=%d\n", _stats.count(), _stats.size(), _stats.dirty_size(), _stats.allocated(), _stats.admin_size()); } } // // scavenge_blocks // // Constructs a list of all garbage blocks. // // Also ages non-garbage blocks, so we can do this while // the enlivening lock is held. This prevents a possible race // with mutators that adjust reference counts. // struct scavenge_blocks_visitor { PointerList& _list; // accumulating list // Constructor scavenge_blocks_visitor(PointerList& list) : _list(list) {} inline bool visit(Zone *zone, Subzone *subzone, usword_t q) { if (subzone->is_thread_local(q)) return true; // always age blocks, to distinguish garbage blocks from blocks allocated during finalization [4843956]. if (subzone->is_new(q)) subzone->mature(q); // add unmarked blocks to the garbage list. if (!subzone->is_marked(q)) { subzone->mark_global_garbage(q); _list.add(subzone->quantum_address(q)); } // always continue return true; } inline bool visit(Zone *zone, Large *large) { // always age blocks, to distinguish garbage blocks from blocks allocated during finalization [4843956]. if (large->is_new()) large->mature(); // add unmarked blocks to the garbage list. if (!large->is_marked()) { large->mark_garbage(); _list.add(large->address()); } // always continue return true; } }; void Zone::scavenge_blocks() { // set up the block scanvenger visitor scavenge_blocks_visitor visitor(_garbage_list); // iterate through all the blocks visitAllocatedBlocks(this, visitor); } void Zone::recycle_threads() { Thread *unbound_threads = NULL; { Mutex lock(&_registered_threads_mutex); Thread::scavenge_threads(&_registered_threads, &unbound_threads); } while (unbound_threads != NULL) { Thread *next = unbound_threads->next(); delete unbound_threads; unbound_threads = next; } } static void foreach_block_do(auto_zone_cursor_t cursor, void (*op) (void *ptr, void *data), void *data) { Zone *azone = (Auto::Zone *)cursor->zone; while (cursor->index < cursor->garbage_count) { void *ptr = (void *)cursor->garbage[cursor->index++]; auto_memory_type_t type = auto_zone_get_layout_type((auto_zone_t *)azone, ptr); if (type & AUTO_OBJECT) { #if DEBUG if (ptr == WatchPoint) { malloc_printf("auto_zone invalidating watchpoint: %p\n", WatchPoint); } #endif op(ptr, data); cursor->block_count++; cursor->byte_count += azone->block_size(ptr); } } } // // invalidate_garbage // void Zone::invalidate_garbage(const size_t garbage_count, const vm_address_t *garbage) { #if DEBUG // when debugging, sanity check the garbage list in various ways. for (size_t index = 0; index < garbage_count; index++) { void *ptr = (void *)garbage[index]; int rc = block_refcount(ptr); if (rc > 0) malloc_printf("invalidate_garbage: garbage ptr = %p, has non-zero refcount = %d\n", ptr, rc); } #endif struct auto_zone_cursor cursor = { (auto_zone_t *)this, garbage_count, garbage, 0, 0, 0 }; if (control.batch_invalidate) { control.batch_invalidate((auto_zone_t *)this, foreach_block_do, &cursor, sizeof(cursor)); } } static inline void zombify(Auto::Zone *azone, void *ptr) { if ((azone->block_layout(ptr) & AUTO_OBJECT)) azone->erase_weak(ptr); // callback to morph the object into a zombie. if (azone->control.resurrect) azone->control.resurrect((auto_zone_t*)azone, ptr); azone->block_set_layout(ptr, AUTO_OBJECT_UNSCANNED); } void Zone::handle_overretained_garbage(void *block, int rc) { char *name; auto_memory_type_t layout = block_layout(block); if ((layout & AUTO_OBJECT) == AUTO_OBJECT) { if (control.name_for_address) { name = control.name_for_address((auto_zone_t *)this, (vm_address_t)block, 0); } else { name = (char *)"object"; } } else { name = (char *)"non-object"; } malloc_printf("garbage block %p(%s) was over-retained during finalization, refcount = %d\n" "This could be an unbalanced CFRetain(), or CFRetain() balanced with -release.\n" "Break on auto_zone_resurrection_error() to debug.\n", block, name, rc); auto_zone_resurrection_error(); if (Auto::Environment::resurrection_is_fatal) { auto_fatal("fatal resurrection error for garbage block %p(%s): over-retained during finalization, refcount = %d", block, name, rc); } if (((layout & AUTO_OBJECT) == AUTO_OBJECT) && control.name_for_address) free(name); } size_t Zone::free_garbage(boolean_t generational, const size_t garbage_count, vm_address_t *garbage, size_t &blocks_freed, size_t &bytes_freed) { size_t index; SpinLock lock(associations_lock()); blocks_freed = bytes_freed = 0; for (index = 0; index < garbage_count; index++) { void *ptr = (void *)garbage[index]; int rc = block_refcount(ptr); if (rc == 0) { if ((block_layout(ptr) & AUTO_OBJECT)) erase_weak(ptr); blocks_freed++; bytes_freed += block_size(ptr); if (malloc_logger) malloc_logger(MALLOC_LOG_TYPE_DEALLOCATE | MALLOC_LOG_TYPE_HAS_ZONE, uintptr_t(zone), uintptr_t(ptr), 0, 0, 0); erase_associations_internal(ptr); if (in_subzone_memory(ptr)) { Subzone::subzone(ptr)->admin()->deallocate(ptr); } else if (in_large_memory(ptr)) { deallocate_large(ptr); } else { error("Deallocating a non-block", ptr); } } else if (is_zombie(ptr)) { zombify(this, ptr); block_decrement_refcount(ptr); } else { handle_overretained_garbage(ptr, rc); } } return bytes_freed; } // // register_thread // // Add the current thread as a thread to be scanned during gc. // Thread &Zone::register_thread() { // if thread is not registered yet Thread *thread = current_thread(); if (thread == NULL) { // be a good citizen, and try to free some recycled threads before allocating more. // recycle_threads(); // construct a new Thread thread = new Thread(this); // add thread to linked list of registered threads Mutex lock(&_registered_threads_mutex); thread->set_next(_registered_threads); thread->needs_enlivening().state = _enlivening_enabled; _registered_threads = thread; } pthread_setspecific(_registered_threads_key, thread); return *thread; } // // unregister_thread // // Deprecated. // void Zone::unregister_thread() { return; } // // destroy_registered_thread // // Pthread key destructor. The collector has a critical dependency on the ordering of pthread destructors. // This destructor must run after any other code which might possibly call into the collector. // We have arranged with pthreads to have our well known key destructor called after any dynamic keys and // any static (Apple internal) keys that might call into the collector (Foundation, CF). On the last iteration // (PTHREAD_DESTRUCTOR_ITERATIONS) we unregister the thread. // Note that this implementation is non-portable due to our agreement with pthreads. // void Zone::destroy_registered_thread(void *key_value) { if (key_value != INVALID_THREAD_KEY_VALUE) { Thread *thread = (Thread *)key_value; Zone *zone = thread->zone(); pthread_key_t thread_key = zone->_registered_threads_key; if (thread->increment_tsd_count() == PTHREAD_DESTRUCTOR_ITERATIONS) { // : Deleting the thread object while the collector is // enumerating the list is probably not worth the extra effort here. The collector // will scavenge the list, and eventually recycle thread objects, during the next collection. thread->unbind(); // Set the value to a token that marks the thread as unregistered. // If this thread calls into the collector again (tries to look up a Thread instance) then we define it as a fatal error. key_value = INVALID_THREAD_KEY_VALUE; } pthread_setspecific(thread_key, key_value); } } // These accessors provide a way to enumerate the registered threads safely but without holding // the registered threads mutex. Threads are prevented from exiting by holding each thread's // spin lock while its stack is scanned. The lock is always acquired and released while // the registered threads mutex is locked, to ensure the integrity of the list. Since newly // registered threads are always added to the beginning of the list, the enumeration won't include // newly registered threads. The enlivening phase of the collector takes care of that. inline Thread *Zone::firstScannableThread() { Mutex lock(&_registered_threads_mutex); for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { if (thread->lockForScanning()) return thread; } return NULL; } inline Thread *Zone::nextScannableThread(Thread *thread) { Mutex lock(&_registered_threads_mutex); thread->unlockForScanning(); for (thread = thread->next(); thread != NULL; thread = thread->next()) { if (thread->lockForScanning()) return thread; } return NULL; } // // scan_registered_threads // // Safely enumerates registered threads during stack scanning. // void Zone::scan_registered_threads(thread_scanner_t scanner) { for (Thread *thread = firstScannableThread(); thread != NULL; thread = nextScannableThread(thread)) { // scanner is guaranteed to only see threads locked for scanning. scanner(thread); } } // // suspend_all_registered_threads // // Suspend all registered threads. Provided for heap snapshots. // Acquires the registered threads mutex so that no new threads can enter the system. // void Zone::suspend_all_registered_threads() { pthread_mutex_lock(&_registered_threads_mutex); for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { thread->suspend(); } } // // resume_all_registered_threads // // Resumes all suspended registered threads. Provided for heap snapshots. // Relinquishes the registered threads mutex. // void Zone::resume_all_registered_threads() { for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) { thread->resume(); } pthread_mutex_unlock(&_registered_threads_mutex); } // // print_all_blocks // // Prints all allocated blocks. // struct print_all_blocks_visitor { Region *_last_region; // previous region visited Subzone *_last_subzone; // previous admin visited bool _is_large; // Constructor print_all_blocks_visitor() : _last_region(NULL), _is_large(false) {} // visitor function inline bool visit(Zone *zone, Subzone *subzone, usword_t q) { // if transitioning then print appropriate banner if (_last_region != subzone->region()) { _last_region = subzone->region(); malloc_printf("Region [%p..%p]\n", _last_region->address(), _last_region->end()); } void *block = subzone->quantum_address(q); if (subzone->is_start(q)) { zone->print_block(block); } else { FreeListNode *node = (FreeListNode *)block; malloc_printf(" %p(%6d) ### free\n", block, node->size()); } // always continue return true; } inline bool visit(Zone *zone, Large *large) { if (!_is_large) { malloc_printf("Large Blocks\n"); _is_large = true; } zone->print_block(large->address()); // always continue return true; } }; void Zone::print_all_blocks() { SpinLock lock(&_region_lock); print_all_blocks_visitor visitor; visitAllBlocks(this, visitor); } // // print block // // Print the details of a block // void Zone::print_block(void *block) { print_block(block, ""); } void Zone::print_block(void *block, const char *tag) { block = block_start(block); if (!block) malloc_printf("%s%p is not a block", tag, block); if (block) { if (in_subzone_memory(block)) { Subzone *subzone = Subzone::subzone(block); usword_t q = subzone->quantum_index(block); int rc = block_refcount(block); int layout = subzone->layout(q); bool is_unscanned = (layout & AUTO_UNSCANNED) != 0; bool is_object = (layout & AUTO_OBJECT) != 0; bool is_new = subzone->is_new(q); bool is_marked = subzone->is_marked(q); bool is_pending = false; char *class_name = (char *)""; if (is_object) { void *isa = *(void **)block; if (isa) class_name = *(char **)displace(isa, 8); } malloc_printf("%s%p(%6d) %s %s %s %s %s rc(%d) q(%u) subzone(%p) %s\n", tag, block, (unsigned)subzone->size(q), is_unscanned ? " " : "scn", is_object ? "obj" : "mem", is_new ? "new" : " ", is_marked ? "mark" : " ", is_pending ? "pend" : " ", rc, q, subzone, class_name); } else if (in_large_memory(block) && Large::is_start(block)) { Large *large = Large::large(block); int rc = block_refcount(block); int layout = large->layout(); bool is_unscanned = (layout & AUTO_UNSCANNED) != 0; bool is_object = (layout & AUTO_OBJECT) != 0; bool is_new = large->is_new(); bool is_marked = large->is_marked(); bool is_pending = false; char *class_name = (char *)""; if (is_object) { void *isa = *(void **)block; if (isa) class_name = *(char **)displace(isa, 8); // XXX 64 bit WRONG } malloc_printf("%s%p(%6d) %s %s %s %s %s rc(%d) %s\n", tag, block, (unsigned)large->size(), is_unscanned ? " " : "scn", is_object ? "obj" : "mem", is_new ? "new" : " ", is_marked ? "mark" : " ", is_pending ? "pend" : " ", rc, class_name); } return; } malloc_printf("%s%p is not a block", tag, block); } };