1/* 2 * Copyright (c) 1999, 2000, 2002-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24/* Bertrand from vmutils -> CF -> System */ 25 26#include "malloc.h" 27#include "malloc_printf.h" 28#include "malloc_internal.h" 29#include "stack_logging.h" 30 31#include <stdio.h> 32#include <stdlib.h> 33#include <libkern/OSAtomic.h> 34#include <mach/mach.h> 35#include <mach/vm_statistics.h> 36#include <os/tsd.h> 37#include <TargetConditionals.h> 38 39#include <CrashReporterClient.h> 40 41extern void thread_stack_pcs(vm_address_t *, unsigned, unsigned *); 42 43static inline void *allocate_pages(unsigned) __attribute__((always_inline)); 44static inline void *allocate_pages(unsigned bytes) { 45 void *address; 46 if (vm_allocate(mach_task_self(), (vm_address_t *)&address, bytes, 47 VM_MAKE_TAG(VM_MEMORY_ANALYSIS_TOOL)| TRUE)) { 48 malloc_printf("*** out of memory while stack logging\n"); 49 CRSetCrashLogMessage("*** out of memory while stack logging\n"); 50 abort(); 51 } 52 return (void *)address; 53} 54 55static inline void deallocate_pages(void *, unsigned) __attribute__((always_inline)); 56static inline void deallocate_pages(void *ptr, unsigned bytes) { 57 vm_deallocate(mach_task_self(), (vm_address_t)ptr, bytes); 58} 59 60static inline void copy_pages(const void *, void *, unsigned) __attribute__((always_inline)); 61static inline void copy_pages(const void *source, void *dest, unsigned bytes) { 62 if (vm_copy(mach_task_self(), (vm_address_t)source, bytes, (vm_address_t)dest)) memmove(dest, source, bytes); 63} 64 65/*************** Uniquing stack ***********/ 66 67#define MAX_COLLIDE 8 68 69#define MAX_NUM_PC 512 70 71static int enter_pair_in_table(unsigned *table, unsigned numPages, unsigned *uniquedParent, unsigned thisPC) { 72 // uniquedParent is in-out; return 1 is collisions max not exceeded 73 unsigned base = numPages * vm_page_size / (sizeof(int)*2*2); 74 unsigned hash = base + (((*uniquedParent) << 4) ^ (thisPC >> 2)) % (base - 1); // modulo odd number for hashing 75 unsigned collisions = MAX_COLLIDE; 76 while (collisions--) { 77 unsigned *head = table + hash*2; 78 if (! head[0] && !head[1]) { 79 /* end of chain; store this entry! */ 80 /* Note that we need to test for both head[0] and head[1] as (0, -1) is a valid entry */ 81 head[0] = thisPC; 82 head[1] = *uniquedParent; 83 *uniquedParent = hash; 84 return 1; 85 } 86 if ((head[0] == thisPC) && (head[1] == *uniquedParent)) { 87 /* we found the proper entry, the value for the pair is the entry offset */ 88 *uniquedParent = hash; 89 return 1; 90 } 91 hash++; 92 if (hash == base*2) hash = base; 93 } 94 return 0; 95} 96 97static unsigned 98stack_logging_get_unique_stack(unsigned **table, unsigned *table_num_pages, unsigned *stack_entries, unsigned count, unsigned num_hot_to_skip) { 99 unsigned uniquedParent = (unsigned)-1; 100 // we skip the warmest entries that are an artefact of the code 101 while (num_hot_to_skip--) { 102 if (count > 0) { stack_entries++; count--; } 103 } 104 while (count--) { 105 unsigned thisPC = stack_entries[count]; 106 while (!enter_pair_in_table(*table, *table_num_pages, &uniquedParent, thisPC)) { 107 unsigned *newTable; 108 unsigned oldBytes = (*table_num_pages) * vm_page_size; 109 newTable = allocate_pages(oldBytes*2); 110 copy_pages(*table, newTable, oldBytes); 111 deallocate_pages(*table, oldBytes); 112 *table_num_pages *= 2; 113 *table = newTable; 114 } 115 } 116 return uniquedParent; 117} 118 119/*************** Logging stack and arguments ***********/ 120 121stack_logging_record_list_t *stack_logging_the_record_list = NULL; 122 123int stack_logging_enable_logging = 0; 124int stack_logging_dontcompact = 0; 125int stack_logging_finished_init = 0; 126int stack_logging_postponed = 0; 127 128static _malloc_lock_s stack_logging_spin_lock = _MALLOC_LOCK_INIT; 129 130static stack_logging_record_list_t *GrowLogRecords(stack_logging_record_list_t *records, unsigned desiredNumRecords) { 131 stack_logging_record_list_t *new_records; 132 unsigned old_size = records->overall_num_bytes; 133 if (desiredNumRecords*sizeof(stack_logging_record_t)+sizeof(stack_logging_record_list_t) < records->overall_num_bytes) return records; 134 records->overall_num_bytes += records->overall_num_bytes + vm_page_size; // in order to always get an even number of pages 135 new_records = allocate_pages(records->overall_num_bytes); 136 copy_pages(records, new_records, old_size); 137 deallocate_pages(records, old_size); 138 return new_records; 139} 140 141static void prepare_to_log_stack(void) { 142 if (!stack_logging_the_record_list) { 143 unsigned totalSize = 4 * vm_page_size; 144 stack_logging_the_record_list = allocate_pages(totalSize); 145 memset(stack_logging_the_record_list, 0, sizeof(stack_logging_record_list_t)); 146 stack_logging_the_record_list->overall_num_bytes = totalSize; 147 stack_logging_the_record_list->uniquing_table_num_pages = 128; 148 stack_logging_the_record_list->uniquing_table = allocate_pages(stack_logging_the_record_list->uniquing_table_num_pages * vm_page_size); 149 } 150} 151 152void stack_logging_log_stack(unsigned type, unsigned arg1, unsigned arg2, unsigned arg3, unsigned result, unsigned num_hot_to_skip) { 153 stack_logging_record_t *rec; 154 if (!stack_logging_enable_logging) return; 155 // printf("stack_logging_log_stack 0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result); 156 if (type & stack_logging_flag_zone) { 157 // just process it now and be done with it! 158 arg1 = arg2; arg2 = arg3; arg3 = 0; type &= ~stack_logging_flag_zone; 159 } 160 if (type == (stack_logging_type_dealloc|stack_logging_type_alloc)) { 161 if (arg1 == result) return; // realloc had no effect, skipping 162 if (!arg1) { 163 // realloc(NULL, size) same as malloc(size) 164 type = stack_logging_type_alloc; arg1 = arg2; arg2 = arg3; arg3 = 0; 165 } else { 166 // realloc(arg1, arg2) -> result is same as free(arg1); malloc(arg2) -> result 167 stack_logging_log_stack(stack_logging_type_dealloc, arg1, 0, 0, 0, num_hot_to_skip+1); 168 stack_logging_log_stack(stack_logging_type_alloc, arg2, 0, 0, result, num_hot_to_skip+1); 169 return; 170 } 171 } 172 if (type == stack_logging_type_dealloc) { 173 // simple free 174 if (!arg1) return; // free(nil) 175 } 176 prepare_to_log_stack(); 177 _malloc_lock_lock(&stack_logging_spin_lock); 178 stack_logging_the_record_list = GrowLogRecords(stack_logging_the_record_list, stack_logging_the_record_list->num_records + 1); 179 rec = stack_logging_the_record_list->records + stack_logging_the_record_list->num_records; 180 // We take care of the common case of alloc-dealloc 181 if (!stack_logging_dontcompact && stack_logging_the_record_list->num_records && (type == stack_logging_type_dealloc) && arg1 && ((rec-1)->type == stack_logging_type_alloc) && (arg1 == STACK_LOGGING_DISGUISE((rec-1)->address))) { 182 stack_logging_the_record_list->num_records--; 183 // printf("Erased previous record in alloc-dealloc sequence\n"); 184 } else { 185 unsigned stack_entries[MAX_NUM_PC]; 186 unsigned count = 0; 187 rec->type = type; 188 if (type == stack_logging_type_dealloc) { 189 rec->argument = 0; 190 rec->address = STACK_LOGGING_DISGUISE(arg1); // we disguise the address 191 } else if (type == stack_logging_type_alloc) { 192 rec->argument = arg1; 193 rec->address = STACK_LOGGING_DISGUISE(result); // we disguise the address 194 } else { 195 rec->argument = arg2; 196 rec->address = STACK_LOGGING_DISGUISE(arg1); // we disguise the address 197 } 198 // printf("Before getting samples 0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result); 199 thread_stack_pcs((vm_address_t *)stack_entries, MAX_NUM_PC - 1, &count); 200 // We put at the bottom of the stack a marker that denotes the thread (+1 for good measure...) 201 stack_entries[count++] = (int)(uintptr_t)_os_tsd_get_direct(__TSD_THREAD_SELF) + 1; 202 /* now let's unique the sample */ 203 // printf("Uniquing 0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result); 204 rec->uniqued_stack = stack_logging_get_unique_stack(&stack_logging_the_record_list->uniquing_table, &stack_logging_the_record_list->uniquing_table_num_pages, stack_entries, count, num_hot_to_skip+2); // we additionally skip the warmest 2 entries that are an artefact of the code 205 stack_logging_the_record_list->num_records++; 206 } 207 _malloc_lock_unlock(&stack_logging_spin_lock); 208} 209 210static kern_return_t default_reader(task_t task, vm_address_t address, vm_size_t size, void **ptr) { 211 *ptr = (void *)address; 212 return 0; 213} 214 215static kern_return_t get_remote_records(task_t task, memory_reader_t reader, stack_logging_record_list_t **records) { 216 // sets records 217 vm_address_t *remote_records_address_ref; 218 kern_return_t err; 219 *records = NULL; 220 err = reader(task, (vm_address_t)&stack_logging_the_record_list, sizeof(vm_address_t), (void **)&remote_records_address_ref); 221 if (err) return err; 222 if (!*remote_records_address_ref) { 223 // printf("stack_logging: no stack record\n"); 224 return 0; 225 } 226 // printf("stack_logging: stack records at %p\n", (void *)(*remote_records_address_ref)); 227 // printf("stack_logging: reading %d bytes\n", sizeof(stack_logging_record_list_t)); 228 err = reader(task, *remote_records_address_ref, sizeof(stack_logging_record_list_t), (void **)records); // get the list head 229 if (err) return err; 230 // printf("stack_logging: overall num bytes = %d\n", records->overall_num_bytes); 231 return reader(task, *remote_records_address_ref, (*records)->overall_num_bytes, (void **)records); 232} 233 234kern_return_t stack_logging_get_frames(task_t task, memory_reader_t reader, vm_address_t address, vm_address_t *stack_frames_buffer, unsigned max_stack_frames, unsigned *num_frames) { 235 stack_logging_record_list_t *records; 236 kern_return_t err; 237 unsigned index; 238 unsigned disguised = STACK_LOGGING_DISGUISE(address); 239 if (!reader) reader = default_reader; 240 *num_frames = 0; 241 err = get_remote_records(task, reader, &records); 242 if (err || !records) return err; 243 // printf("stack_logging: %d records\n", records->num_records); 244 index = 0; 245 while (index < records->num_records) { 246 stack_logging_record_t *record = records->records + index; 247 if (record->address == disguised) { 248 return stack_logging_frames_for_uniqued_stack(task, reader, record->uniqued_stack, stack_frames_buffer, max_stack_frames, num_frames); 249 } 250 index++; 251 } 252 fprintf(stderr, "*** stack_logging: no record found for %p\n", (void *)address); 253 return 0; 254} 255 256kern_return_t stack_logging_enumerate_records(task_t task, memory_reader_t reader, vm_address_t address, void enumerator(stack_logging_record_t, void *), void *context) { 257 stack_logging_record_list_t *records; 258 kern_return_t err; 259 unsigned index; 260 unsigned disguised = STACK_LOGGING_DISGUISE(address); 261 if (!reader) reader = default_reader; 262 err = get_remote_records(task, reader, &records); 263 if (err || !records) return err; 264 // printf("stack_logging: %d records\n", records->num_records); 265 index = 0; 266 while (index < records->num_records) { 267 stack_logging_record_t *record = records->records + index; 268 if (!address || (record->address == disguised)) enumerator(*record, context); 269 index++; 270 } 271 return 0; 272} 273 274kern_return_t stack_logging_frames_for_uniqued_stack(task_t task, memory_reader_t reader, unsigned uniqued_stack, vm_address_t *stack_frames_buffer, unsigned max_stack_frames, unsigned *num_frames) { 275 stack_logging_record_list_t *records; 276 unsigned *uniquing_table; 277 kern_return_t err; 278 if (!reader) reader = default_reader; 279 *num_frames = 0; 280 err = get_remote_records(task, reader, &records); 281 if (err || !records) return err; 282 err = reader(task, (vm_address_t)records->uniquing_table, records->uniquing_table_num_pages * vm_page_size, (void **)&uniquing_table); 283 if (err) return err; 284 while (max_stack_frames && (uniqued_stack != -1)) { 285 unsigned thisPC; 286 if ((uniqued_stack * 2 + 1) * sizeof(unsigned) >= records->uniquing_table_num_pages * vm_page_size) { 287 fprintf(stderr, "*** stack_logging: Invalid uniqued stack 0x%x", uniqued_stack); 288 break; 289 } 290 thisPC = uniquing_table[uniqued_stack * 2]; 291 uniqued_stack = uniquing_table[uniqued_stack * 2 + 1]; 292 if (!thisPC && !uniqued_stack) { 293 // Invalid entry 294 fprintf(stderr, "*** stack_logging: Invalid entry 0x%x", thisPC); 295 break; 296 } 297 stack_frames_buffer[0] = thisPC; 298 stack_frames_buffer++; 299 (*num_frames)++; 300 max_stack_frames--; 301 } 302 return 0; 303} 304 305/* vim: set noet:ts=4:sw=4:cindent: */ 306