/* * Copyright (c) 2011 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@ */ /* auto_impl_utilities.c Implementation Utilities Copyright (c) 2002-2011 Apple Inc. All rights reserved. */ #include "auto_impl_utilities.h" #include "auto_tester.h" #include #include #include #include #include #include #include #if !TARGET_OS_IPHONE # include #else // CrashReporterClient not available on iOS static void CRSetCrashLogMessage(const char *buffer) { } #endif /********* Implementation utilities ************/ vm_address_t auto_get_sp() { return (vm_address_t)__builtin_frame_address(0); } size_t auto_round_page(size_t size) { if (!size) return vm_page_size; return (size + vm_page_size - 1) & ~ (vm_page_size - 1); } /********* Utilities ************/ int auto_ncpus() { static int ncpus = 0; if (ncpus == 0) { int mib[2]; size_t len = sizeof(ncpus); mib[0] = CTL_HW; mib[1] = HW_NCPU; if (sysctl(mib, 2, &ncpus, &len, NULL, 0) != 0) { // sysctl failed. just return 1 and try again next time ncpus = 0; return 1; } } return ncpus; } const char *auto_prelude(void) { static char buf[32] = { 0 }; if (!buf[0]) { snprintf(buf, sizeof(buf), "auto malloc[%d]", getpid()); } return (const char *)buf; } void auto_error(void *azone, const char *msg, const void *ptr) { if (ptr) { malloc_printf("*** %s: error for object %p: %s\n", auto_prelude(), ptr, msg); } else { malloc_printf("*** %s: error: %s\n", auto_prelude(), msg); } #if 0 && DEBUG malloc_printf("*** Sleeping to help debug\n"); sleep(3600); // to help debug #endif } void auto_fatal(const char *format, ...) { static char buffer[512]; va_list args; va_start(args, format); vsnprintf(buffer, sizeof(buffer), format, args); va_end(args); CRSetCrashLogMessage(buffer); malloc_printf("%s", buffer); __builtin_trap(); } /********* Internal allocation ************/ // GrP fixme assumes only one auto zone is ever active in a process __private_extern__ malloc_zone_t *aux_zone = NULL; __private_extern__ void aux_init(void) { if (!aux_zone) { aux_zone = malloc_create_zone(4096, 0); // GrP fixme size? malloc_set_zone_name(aux_zone, "aux_zone"); #if !DEBUG // make it possible to call free() on these blocks while debugging. malloc_zone_unregister(aux_zone); // PCB don't let fork() mess with aux_zone #endif } } /********* Dealing with time ************/ double auto_time_interval(auto_date_t after, auto_date_t before) { #if 0 static double rate = 0.0; if (rate == 0.0) { struct mach_timebase_info info; mach_timebase_info(&info); rate = (double)info.numer / (1.0E9 * (double)info.denom); } return (after - before) * rate; #else return (after - before) / 1.0E6; #endif } malloc_zone_t *auto_debug_zone(void) { static malloc_zone_t *z = NULL; if (!z) { z = malloc_create_zone(4096, 0); malloc_set_zone_name(z, "auto debug"); } return z; } #define CHECK_ADDR(n) \ entry->stack[n] = (vm_address_t)(__builtin_return_address(n + 1) - 4); \ if ((__builtin_frame_address(n + 3) == NULL) || (__builtin_return_address(n + 2) == NULL)) { \ goto done; \ } #define CHECK_ADDR2(n) \ CHECK_ADDR(n) \ CHECK_ADDR(n + 1) #define CHECK_ADDR4(n) \ CHECK_ADDR2(n) \ CHECK_ADDR2(n + 2) #define CHECK_ADDR8(n) \ CHECK_ADDR4(n) \ CHECK_ADDR4(n + 4) #define UNUSED 0xffffffff #define ENTRY_COUNT 32 typedef struct { vm_address_t stack[8]; unsigned int oldCount; // may be UNUSED unsigned int newCount; // oldCount == newCount for new allocations } auto_refcount_history_entry_t; typedef struct { vm_address_t address; int nextEntry; auto_refcount_history_entry_t entries[ENTRY_COUNT]; } auto_refcount_history_t; static auto_refcount_history_t *history_list = NULL; static int history_allocated = 0; static int history_used = 0; static int history_hash(vm_address_t target) { int index = (target >> 2) % history_allocated; while (history_list[index].address != 0 && history_list[index].address != target) { index++; if (index == history_allocated) index = 0; } return index; } static spin_lock_t refcount_stacks_lock; #define auto_refcount_stacks_lock() spin_lock(&refcount_stacks_lock) #define auto_refcount_stacks_unlock() spin_unlock(&refcount_stacks_lock) void auto_record_refcount_stack(auto_zone_t *azone, void *ptr, int delta) { int h, e; vm_address_t addr = (vm_address_t)ptr; auto_refcount_history_t *history = NULL; auto_refcount_history_entry_t *entry; auto_refcount_stacks_lock(); if (history_used >= history_allocated * 3 / 4) { auto_refcount_history_t *old_list = history_list; int old_allocated = history_allocated; history_allocated = old_allocated ? old_allocated * 2 : 10000; history_list = malloc_zone_calloc(auto_debug_zone(), history_allocated, sizeof(*history_list)); // history_used remains unchanged // rehash for (h = 0; h < history_used; h++) { if (old_list[h].address) { history_list[history_hash(old_list[h].address)] = old_list[h]; } } malloc_zone_free(auto_debug_zone(), old_list); } history = &history_list[history_hash(addr)]; if (history->address != addr) { // initialize new location history->address = (vm_address_t)ptr; history->nextEntry = 0; for (e = 0; e < ENTRY_COUNT; e++) { history->entries[e].oldCount = UNUSED; } history_used++; } entry = &history->entries[history->nextEntry++]; if (history->nextEntry == ENTRY_COUNT) history->nextEntry = 0; bzero(entry, sizeof(*entry)); CHECK_ADDR8(0); done: entry->oldCount = auto_zone_retain_count((void *)azone, ptr); entry->newCount = entry->oldCount + delta; auto_refcount_stacks_unlock(); } void auto_print_refcount_stacks(void *ptr) { int e; vm_address_t addr = (vm_address_t)ptr; auto_refcount_history_t *history = NULL; auto_refcount_history_entry_t *entry; auto_refcount_stacks_lock(); history = &history_list[history_hash(addr)]; if (history->address != addr) { malloc_printf("No refcount history for address %p\n", ptr); return; } fprintf(stderr, "\nREFCOUNT HISTORY FOR %p\n\n", ptr); e = history->nextEntry; do { entry = &history->entries[e]; if (entry->oldCount != UNUSED) { int s; if (entry->oldCount == entry->newCount) { fprintf(stderr, "\nrefcount %d (new)\tadecodestack ", entry->newCount); } else { fprintf(stderr, "refcount %d -> %d \tadecodestack ", entry->oldCount, entry->newCount); } for (s = 0; s < 8 && entry->stack[s]; s++) { fprintf(stderr, "%p ", (void *)entry->stack[s]); } fprintf(stderr, "\n"); } e++; if (e == ENTRY_COUNT) e = 0; } while (e != history->nextEntry); auto_refcount_stacks_unlock(); fprintf(stderr, "\ndone\n"); } // // ptr_set utilities // // Pointer sets are used to track the use of allocated objects. // #define PTR_SET_DEPTH 4 #define PTR_SET_GROWTH 333 // Internals struct ptr_set { spin_lock_t lock; unsigned length; // length of set void **members; // closed hash table of pointers void **end; // end + 1 of hash table (faster next pointer) }; static void **ptr_set_find_slot(ptr_set *set, void *ptr); static void ptr_set_grow(ptr_set *set); static inline void **ptr_set_next(ptr_set *set, void **slot) { return ++slot == set->end ? set->members : slot; } // return the next slot (wrap around) static inline intptr_t ptr_set_hash(ptr_set *set, void *ptr) { return (((intptr_t)ptr >> 2) * 2654435761u) % set->length; } // return the hash index of the specified pointer static boolean_t ptr_set_add_no_lock_did_grow(ptr_set *set, void *ptr) { // add a member to the set boolean_t didGrow = false; // current slot void **slot; // don't add NULL entries if (ptr == NULL) return false; // make sure it is 4 byte aligned (or will grow forever) if ((intptr_t)ptr & 0x3) { malloc_printf("*** %s: ptr_set_add(ptr=%p) not pointer aligned\n", auto_prelude(), ptr); return false; } // try and try again while (1) { // find the pointers slot slot = ptr_set_find_slot(set, ptr); // if found escape loop if (slot != NULL) break; // grow the table to make more room for the hash group ptr_set_grow(set); didGrow = true; } // set the slot (may be redundant if the pointer is already in hashtable) *slot = ptr; return didGrow; } static void ptr_set_grow(ptr_set *set) { // Provide more room in the hashtable and rehash the old entries. // current slot void **slot; // capture old hashtable length unsigned old_length = set->length; // capture old members void **old_members = set->members; // capture old end void **old_end = set->end; /// new hashtable length set->length = (old_length + PTR_SET_GROWTH) | 1; // allocate new hashtable set->members = (void **)aux_calloc(set->length, sizeof(void *)); // set end set->end = set->members + set->length; // rehash old entries for (slot = old_members; slot < old_end; slot++) ptr_set_add_no_lock_did_grow(set, *slot); // release old hashtable aux_free(old_members); } static void **ptr_set_find_slot(ptr_set *set, void *ptr) { // find the slot the ptr should reside // current slot void **slot; // depth index unsigned depth; // ptr hash unsigned hash = ptr_set_hash(set, ptr); // iterate for the closed hash depth for (depth = 0, slot = set->members + hash; depth < PTR_SET_DEPTH; depth++, slot = ptr_set_next(set, slot)) { // get the old member in the slot void *old_member = *slot; // return the slot if the slot is empty or already contains the ptr if (old_member == NULL || old_member == ptr) return slot; // otherwise check to see if the entry is a member of the same hash group if (hash != ptr_set_hash(set, old_member)) return NULL; } // not found return NULL; } // Externals __private_extern__ ptr_set *ptr_set_new() { // initialize the pointer set ptr_set *set = aux_malloc(sizeof(ptr_set)); // zero lock set->lock = 0; // set length set->length = PTR_SET_GROWTH; // allocate members set->members = (void **)aux_calloc(PTR_SET_GROWTH, sizeof(void *)); // set end set->end = set->members + PTR_SET_GROWTH; return set; } __private_extern__ void ptr_set_dispose(ptr_set *set) { // release memory allocate by the set aux_free(set->members); aux_free(set); } __private_extern__ void ptr_set_add(ptr_set *set, void *ptr) { spin_lock(&set->lock); ptr_set_add_no_lock_did_grow(set, ptr); spin_unlock(&set->lock); } __private_extern__ int ptr_set_is_member_no_lock(ptr_set *set, void *ptr) { // check to see if the pointer is a member of the set // find the slot void **slot = ptr_set_find_slot(set, ptr); // return true if the slot is found and contains the pointer return (slot != NULL && *slot == ptr); } __private_extern__ int ptr_set_is_member(ptr_set *set, void *ptr) { // check to see if the pointer is a member of the set spin_lock(&set->lock); // find the slot void **slot = ptr_set_find_slot(set, ptr); // return true if the slot is found and contains the pointer boolean_t result = slot != NULL && *slot == ptr; spin_unlock(&set->lock); return result; } __private_extern__ void ptr_set_remove(ptr_set *set, void *ptr) { // remove an entry from the set spin_lock(&set->lock); // find the slot void **slot = ptr_set_find_slot(set, ptr); // if the pointer is found if (slot != NULL && *slot == ptr) { // find out which hash goup it belongs unsigned hash = ptr_set_hash(set, ptr); // next member slot void **next_slot; // searching for other members to fillin gap for (next_slot = ptr_set_next(set, slot); 1; next_slot = ptr_set_next(set, next_slot)) { // get the next candidate void *old_member = *next_slot; // if NULL or not member of the same hash group if (old_member == NULL || hash != ptr_set_hash(set, old_member)) { // NULL out the last slot in the group *slot = NULL; break; } // shift down the slots *slot = *next_slot; slot = next_slot; } } spin_unlock(&set->lock); } struct ptr_map { spin_lock_t lock; unsigned length; // length of set void **members; // closed hash table of pointers void **end; // end + 1 of hash table (faster next pointer) }; static void **ptr_map_find_slot(ptr_map *map, void *ptr); static void ptr_map_grow(ptr_map *map); static inline void **ptr_map_next(ptr_map *map, void **slot) { return ++slot == map->end ? map->members : slot; } // return the next slot (wrap around) static inline intptr_t ptr_map_hash(ptr_map *map, void *ptr) { return (((uintptr_t)ptr >> 4) * 2654435761u) % map->length; } // return the hash index of the specified pointer static boolean_t ptr_map_add_no_lock_did_grow(ptr_map *map, void *ptr, void *value) { // add a member to the map boolean_t didGrow = false; // current slot void **slot; // don't add NULL entries if (ptr == NULL) return false; // make sure it is 16 byte aligned (or will grow forever) if ((intptr_t)ptr & 15) { malloc_printf("*** %s: ptr_map_add(ptr=%p) not object aligned\n", auto_prelude(), ptr); return false; } // try and try again while (1) { // find the pointers slot slot = ptr_map_find_slot(map, ptr); // if found escape loop if (slot != NULL) break; // grow the table to make more room for the hash group ptr_map_grow(map); didGrow = true; } // map the slot (may be redundant if the pointer is already in hashtable) *slot = ptr; *(slot + map->length) = value; return didGrow; } static void ptr_map_grow(ptr_map *map) { // Provide more room in the hashtable and rehash the old entries. // current slot void **slot; // capture old hashtable length unsigned old_length = map->length; // capture old members void **old_members = map->members; // capture old end void **old_end = map->end; /// new hashtable length map->length = (old_length + PTR_SET_GROWTH) | 1; // allocation size size_t size = map->length * sizeof(void *); // allocate & clear new hashtable map->members = (void **)aux_calloc(2, size); // enough room for values, too // set end map->end = map->members + map->length; // rehash old entries for (slot = old_members; slot < old_end; slot++) ptr_map_add_no_lock_did_grow(map, *slot, *(slot+old_length)); // release old hashtable aux_free(old_members); } static void **ptr_map_find_slot(ptr_map *map, void *ptr) { // find the slot the ptr should reside // current slot void **slot; // depth index unsigned depth; // ptr hash unsigned hash = ptr_map_hash(map, ptr); // iterate for the closed hash depth for (depth = 0, slot = map->members + hash; depth < PTR_SET_DEPTH; depth++, slot = ptr_map_next(map, slot)) { // get the old member in the slot void *old_member = *slot; // return the slot if the slot is empty or already contains the ptr if (old_member == NULL || old_member == ptr) return slot; // otherwise check to see if the entry is a member of the same hash group if (hash != ptr_map_hash(map, old_member)) return NULL; } // not found return NULL; } // Externals __private_extern__ ptr_map * ptr_map_new() { // initialize the pointer map ptr_map *map = aux_malloc(sizeof(ptr_map)); // zero lock map->lock = 0; // set length map->length = PTR_SET_GROWTH; // allocation size size_t size = PTR_SET_GROWTH * sizeof(void *); // allocate & clear members map->members = (void **)aux_calloc(2, size); // set end map->end = map->members + PTR_SET_GROWTH; return map; } __private_extern__ void ptr_map_dispose(ptr_map *map) { // release memory allocate by the map aux_free(map->members); aux_free(map); } __private_extern__ void ptr_map_set(ptr_map *map, void *ptr, void *value) { spin_lock(&map->lock); ptr_map_add_no_lock_did_grow(map, ptr, value); spin_unlock(&map->lock); } __private_extern__ void * ptr_map_get(ptr_map *map, void *ptr) { // check to see if the pointer is a member of the set spin_lock(&map->lock); // find the slot void **slot = ptr_map_find_slot(map, ptr); // return true if the slot is found and contains the pointer void *result = (slot != NULL && *slot == ptr) ? *(slot + map->length) : NULL; spin_unlock(&map->lock); return result; } __private_extern__ void *ptr_map_remove(ptr_map *map, void *ptr) { // remove an entry from the map void *result = NULL; spin_lock(&map->lock); // find the slot void **slot = ptr_map_find_slot(map, ptr); // if the pointer is found if (slot != NULL && *slot == ptr) { result = *(slot + map->length); // find out which hash goup it belongs unsigned hash = ptr_map_hash(map, ptr); // next member slot void **next_slot; // searching for other members to fillin gap for (next_slot = ptr_map_next(map, slot); 1; next_slot = ptr_map_next(map, next_slot)) { // get the next candidate void *old_member = *next_slot; // if NULL or not member of the same hash group if (old_member == NULL || hash != ptr_map_hash(map, old_member)) { // NULL out the last slot in the group *slot = NULL; break; } // shift down the slots *slot = *next_slot; *(slot+map->length) = *(next_slot+map->length); slot = next_slot; } } spin_unlock(&map->lock); return result; } /************ Miscellany **************************/ // Watching #define WatchLimit 16 static const void *WatchPoints[WatchLimit]; void auto_zone_watch(const void *ptr) { for (int i = 0; i < WatchLimit; ++i) { if (WatchPoints[i]) { if (WatchPoints[i] == ptr) return; } else { WatchPoints[i] = ptr; return; } } printf("too many watchpoints already, skipping %p\n", ptr); } void auto_zone_watch_free(const void *ptr, watch_block_t block) { for (int i = 0; i < WatchLimit; ++i) { if (WatchPoints[i] == NULL) return; if (WatchPoints[i] == ptr) { block(); while(++i < WatchLimit) WatchPoints[i-1] = WatchPoints[i]; WatchPoints[WatchLimit-1] = NULL; return; } } } void auto_zone_watch_apply(void *ptr, watch_block_t block) { for (int i = 0; i < WatchLimit; ++i) { if (WatchPoints[i] == NULL) return; if (WatchPoints[i] == ptr) { block(); return; } } } __private_extern__ void auto_refcount_underflow_error(void *block) { } __private_extern__ void auto_zone_resurrection_error() { } __private_extern__ void auto_zone_thread_local_error(void) { } __private_extern__ void auto_zone_thread_registration_error() { AUTO_PROBE(auto_probe_unregistered_thread_error()); } __private_extern__ void auto_zone_global_data_memmove_error() { } __private_extern__ void auto_zone_association_error(void *address) { } __private_extern__ void auto_zone_unscanned_store_error(const void *destination, const void *value) { }