[apple/libc.git] / gen / stack_logging.c

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

/*	Bertrand from vmutils -> CF -> System */

#import "stack_logging.h"

#import <libc.h>
#import <pthread.h>
#import <mach/mach.h>
#include <mach/vm_statistics.h>

extern void spin_lock(int *);

static inline void *allocate_pages(unsigned bytes) {
    void *address;
    if (vm_allocate(mach_task_self(), (vm_address_t *)&address, bytes, 
                    VM_MAKE_TAG(VM_MEMORY_ANALYSIS_TOOL)| TRUE)) {
	address = 0;
    } 
    return (void *)address;
}

static inline void deallocate_pages(void *ptr, unsigned bytes) {
    vm_deallocate(mach_task_self(), (vm_address_t)ptr, bytes);
}

static inline void copy_pages(const void *source, void *dest, unsigned bytes) {
    if (vm_copy(mach_task_self(), (vm_address_t)source, bytes, (vm_address_t)dest)) memmove(dest, source, bytes);
}

/***************	Recording stack		***********/

static void *first_frame_address(void) {
#if 0
    return __builtin_frame_address(1);
#elif defined(__ppc__)
    void *addr;
#warning __builtin_frame_address IS BROKEN IN BEAKER: RADAR #2340421
    __asm__ volatile("mr %0, r1" : "=r" (addr));
    return addr;
#else
#warning first_frame_address WILL NOT BE FUNCTIONAL ON THIS ARCHITECTURE
    return NULL;
#endif
}

static void *next_frame_address(void *addr) {
    void *ret;
#if defined(__MACH__) && defined(__i386__)
    __asm__ volatile("movl (%1),%0" : "=r" (ret) : "r" (addr));
#elif defined(__MACH__) && defined(__ppc__)
    __asm__ volatile("lwz %0,0x0(%1)" : "=r" (ret) : "b" (addr));
#elif defined(__hpux__)
    __asm__ volatile("ldw 0x0(%1),%0" : "=r" (ret) : "r" (addr));
#elif defined(__svr4__)
    __asm__ volatile("ta 0x3");
    __asm__ volatile("ld [%1 + 56],%0" : "=r" (ret) : "r" (addr));
#else
#error Unknown architecture
#endif
    return ret;
}

#if defined(__i386__) || defined (__m68k__)
#define FP_LINK_OFFSET 1
#elif defined(__ppc__)
#define FP_LINK_OFFSET 2
#elif defined(__hppa__)
#define FP_LINK_OFFSET -5
#elif defined(__sparc__)
#define FP_LINK_OFFSET 14
#else
#error  ********** Unimplemented architecture
#endif

void thread_stack_pcs(vm_address_t *buffer, unsigned max, unsigned *nb) {
    void *addr;
    addr = first_frame_address();
    *nb = 0;
    while ((addr >= (void *)0x800) && (max--)) {
        vm_address_t	fp_link = (vm_address_t)(((unsigned *)addr)+FP_LINK_OFFSET);
        void	*addr2;
        buffer[*nb] = *((vm_address_t *)fp_link);
        (*nb)++;
        addr2 = next_frame_address(addr);
#if defined(__ppc__)
        if ((unsigned)addr2 <= (unsigned)addr) break; // catch bozo frames
#endif
        addr = addr2;
    }
}

/***************	Uniquing stack		***********/

#define MAX_COLLIDE	8

#define MAX_NUM_PC	512

static int enter_pair_in_table(unsigned *table, unsigned numPages, unsigned *uniquedParent, unsigned thisPC) {
    // uniquedParent is in-out; return 1 is collisions max not exceeded
    unsigned	base = numPages * vm_page_size / (sizeof(int)*2*2);
    unsigned	hash = base + (((*uniquedParent) << 4) ^ (thisPC >> 2)) % (base - 1); // modulo odd number for hashing
    unsigned	collisions = MAX_COLLIDE;
    while (collisions--) {
        unsigned	*head = table + hash*2;
        if (! head[0] && !head[1]) {
            /* end of chain; store this entry! */
            /* Note that we need to test for both head[0] and head[1] as (0, -1) is a valid entry */
            head[0] = thisPC;
            head[1] = *uniquedParent;
            *uniquedParent = hash;
            return 1;
        }
        if ((head[0] == thisPC) && (head[1] == *uniquedParent)) {
            /* we found the proper entry, the value for the pair is the entry offset */
            *uniquedParent = hash;
            return 1;
        }
        hash++;
        if (hash == base*2) hash = base;
    }
    return 0;
}

unsigned stack_logging_get_unique_stack(unsigned **table, unsigned *table_num_pages, unsigned *stack_entries, unsigned count, unsigned num_hot_to_skip) {
    unsigned	uniquedParent = (unsigned)-1;
    // we skip the warmest entries that are an artefact of the code
    while (num_hot_to_skip--) {
        if (count > 0) { stack_entries++; count--; }
    }
    while (count--) {
        unsigned	thisPC = stack_entries[count];
        while (!enter_pair_in_table(*table, *table_num_pages, &uniquedParent, thisPC)) {
            unsigned	*newTable;
            unsigned	oldBytes = (*table_num_pages) * vm_page_size;
            newTable = allocate_pages(oldBytes*2);
            copy_pages(*table, newTable, oldBytes);
            deallocate_pages(*table, oldBytes);
            *table_num_pages *= 2;
            *table = newTable;
        }
    }
    return uniquedParent;
}

/***************	Logging stack and arguments		***********/

stack_logging_record_list_t *stack_logging_the_record_list = NULL;

int stack_logging_enable_logging = 0;

int stack_logging_dontcompact = 0;

static stack_logging_record_list_t *GrowLogRecords(stack_logging_record_list_t *records, unsigned desiredNumRecords) {
    stack_logging_record_list_t	*new_records;
    unsigned	old_size = records->overall_num_bytes;
    if (desiredNumRecords*sizeof(stack_logging_record_t)+sizeof(stack_logging_record_list_t) < records->overall_num_bytes) return records;
    records->overall_num_bytes += records->overall_num_bytes + vm_page_size; // in order to always get an even number of pages
    new_records = allocate_pages(records->overall_num_bytes);
    copy_pages(records, new_records, old_size);
    deallocate_pages(records, old_size);
    return new_records;
}

static void prepare_to_log_stack(void) {
    if (!stack_logging_the_record_list) {
        unsigned	totalSize = 4 * vm_page_size;
        stack_logging_the_record_list = allocate_pages(totalSize);
        memset(stack_logging_the_record_list, 0, sizeof(stack_logging_record_list_t));
        stack_logging_the_record_list->overall_num_bytes = totalSize;
        stack_logging_the_record_list->uniquing_table_num_pages = 128;
        stack_logging_the_record_list->uniquing_table = allocate_pages(stack_logging_the_record_list->uniquing_table_num_pages * vm_page_size);
    }
}

void stack_logging_log_stack(unsigned type, unsigned arg1, unsigned arg2, unsigned arg3, unsigned result, unsigned num_hot_to_skip) {
    stack_logging_record_t	*rec;
    if (!stack_logging_enable_logging) return;
    // printf("stack_logging_log_stack 0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result);
    if (type & stack_logging_flag_zone) {
        // just process it now and be done with it!
        arg1 = arg2; arg2 = arg3; arg3 = 0; type &= ~stack_logging_flag_zone;
    }
    if (type & stack_logging_flag_calloc) {
        // just process it now and be done with it!
        arg1 *= arg2; arg2 = arg3; arg3 = 0; type &= ~stack_logging_flag_calloc;
    }
    if (type & stack_logging_flag_object) {
        unsigned	*class = (unsigned *)arg1;
        arg1 = arg2 + class[5]; // corresponds to the instance_size field
        arg2 = 0; arg3 = 0; type = stack_logging_type_alloc;
    }
    if (type & stack_logging_flag_cleared) {
        type &= ~stack_logging_flag_cleared;
    }
    if (type & stack_logging_flag_handle) {
        if (stack_logging_type_alloc) {
            if (!result) return;
            stack_logging_log_stack(stack_logging_type_alloc, 0, 0, 0, result, num_hot_to_skip+1);
            stack_logging_log_stack(stack_logging_type_alloc, arg1, 0, 0, *((int *)result), num_hot_to_skip+1);
            return;
        }
        if (stack_logging_type_dealloc) {
            if (!arg1) return;
            stack_logging_log_stack(stack_logging_type_dealloc, *((int *)arg1), 0, 0, 0, num_hot_to_skip+1);
            stack_logging_log_stack(stack_logging_type_dealloc, arg1, 0, 0, 0, num_hot_to_skip+1);
            return;
        }
        printf("*** Unknown logging type: 0x%x\n", type);
    }
    if (type == stack_logging_flag_set_handle_size) {
        if (!arg1) return;
        // Thanks to a horrible hack, arg3 contains the prvious handle value
        if (arg3 == *((int *)arg1)) return;
        stack_logging_log_stack(stack_logging_type_dealloc, arg3, 0, 0, 0, num_hot_to_skip+1);
        stack_logging_log_stack(stack_logging_type_alloc, arg2, 0, 0, *((int *)arg1), num_hot_to_skip+1);
        return;
    }            
    if (type == (stack_logging_type_dealloc|stack_logging_type_alloc)) {
        if (arg1 == result) return; // realloc had no effect, skipping
        if (!arg1) {
            // realloc(NULL, size) same as malloc(size)
            type = stack_logging_type_alloc; arg1 = arg2; arg2 = arg3; arg3 = 0;
	} else {
            // realloc(arg1, arg2) -> result is same as free(arg1); malloc(arg2) -> result
            stack_logging_log_stack(stack_logging_type_dealloc, arg1, 0, 0, 0, num_hot_to_skip+1);
            stack_logging_log_stack(stack_logging_type_alloc, arg2, 0, 0, result, num_hot_to_skip+1);
            return;
        }
    }
    if (type == stack_logging_type_dealloc) {
        // simple free
        if (!arg1) return; // free(nil)
    }
    prepare_to_log_stack();
    spin_lock(&stack_logging_the_record_list->lock);
    stack_logging_enable_logging = 0;
    stack_logging_the_record_list = GrowLogRecords(stack_logging_the_record_list, stack_logging_the_record_list->num_records + 1);
    rec = stack_logging_the_record_list->records + stack_logging_the_record_list->num_records;
    // We take care of the common case of alloc-dealloc
    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))) {
        stack_logging_the_record_list->num_records--;
        // printf("Erased previous record in alloc-dealloc sequence\n");
    } else {
        unsigned	stack_entries[MAX_NUM_PC];
        unsigned	count = 0;
        rec->type = type;
        if (type == stack_logging_type_dealloc) {
            rec->argument = 0;
            rec->address = STACK_LOGGING_DISGUISE(arg1); // we disguise the address
        } else if (type == stack_logging_type_alloc) {
            rec->argument = arg1;
            rec->address = STACK_LOGGING_DISGUISE(result); // we disguise the address
        } else {
            rec->argument = arg2;
            rec->address = STACK_LOGGING_DISGUISE(arg1); // we disguise the address
        }
	// printf("Before getting samples  0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result);
        thread_stack_pcs(stack_entries, MAX_NUM_PC - 1, &count);
        // We put at the bottom of the stack a marker that denotes the thread (+1 for good measure...)
        stack_entries[count++] = (int)pthread_self() + 1;
        /* now let's unique the sample */    
        // printf("Uniquing 0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result);
        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
        stack_logging_the_record_list->num_records++;
    }
    stack_logging_enable_logging = 1;
    stack_logging_the_record_list->lock = 0;
}

static kern_return_t default_reader(task_t task, vm_address_t address, vm_size_t size, void **ptr) {
    *ptr = (void *)address;
    return 0;
}

static kern_return_t get_remote_records(task_t task, memory_reader_t reader, stack_logging_record_list_t **records) {
    // sets records
    vm_address_t	*remote_records_address_ref;
    kern_return_t	err;
    *records = NULL;
    err = reader(task, (vm_address_t)&stack_logging_the_record_list, sizeof(vm_address_t), (void **)&remote_records_address_ref);
    if (err) return err;
    if (!*remote_records_address_ref) {
        // printf("stack_logging: no stack record\n");
        return 0;
    }
    // printf("stack_logging: stack records at %p\n", (void *)(*remote_records_address_ref));
    // printf("stack_logging: reading %d bytes\n", sizeof(stack_logging_record_list_t));
    err = reader(task, *remote_records_address_ref, sizeof(stack_logging_record_list_t), (void **)records); // get the list head
    if (err) return err;
    // printf("stack_logging: overall num bytes = %d\n", records->overall_num_bytes);
    return reader(task, *remote_records_address_ref, (*records)->overall_num_bytes, (void **)records);
}

kern_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) {
    stack_logging_record_list_t	*records;
    kern_return_t	err;
    unsigned		index;
    unsigned		disguised = STACK_LOGGING_DISGUISE(address);
    if (!reader) reader = default_reader;
    *num_frames = 0;
    err = get_remote_records(task, reader, &records);
    if (err || !records) return err;
    // printf("stack_logging: %d records\n", records->num_records);
    index = 0;
    while (index < records->num_records) {
        stack_logging_record_t	*record = records->records + index;
        if (record->address == disguised) {
	    return stack_logging_frames_for_uniqued_stack(task, reader, record->uniqued_stack, stack_frames_buffer, max_stack_frames, num_frames);
        }
	index++;
    }
    fprintf(stderr, "*** stack_logging: no record found for 0x%x\n", address);
    return 0;
}

kern_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) {
    stack_logging_record_list_t	*records;
    kern_return_t	err;
    unsigned		index;
    unsigned		disguised = STACK_LOGGING_DISGUISE(address);
    if (!reader) reader = default_reader;
    err = get_remote_records(task, reader, &records);
    if (err || !records) return err;
    // printf("stack_logging: %d records\n", records->num_records);
    index = 0;
    while (index < records->num_records) {
        stack_logging_record_t	*record = records->records + index;
        if (!address || (record->address == disguised)) enumerator(*record, context);
	index++;
    }
    return 0;
}

kern_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) {
    stack_logging_record_list_t	*records;
    unsigned		*uniquing_table;
    kern_return_t	err;
    if (!reader) reader = default_reader;
    *num_frames = 0;
    err = get_remote_records(task, reader, &records);
    if (err || !records) return err;
    err = reader(task, (vm_address_t)records->uniquing_table, records->uniquing_table_num_pages * vm_page_size, (void **)&uniquing_table);
    if (err) return err;
    while (max_stack_frames && (uniqued_stack != -1)) {
	unsigned	thisPC;
	if ((uniqued_stack * 2 + 1) * sizeof(unsigned) >= records->uniquing_table_num_pages * vm_page_size) {
	    fprintf(stderr, "*** stack_logging: Invalid uniqued stack 0x%x", uniqued_stack);
	    break;
	}
	thisPC = uniquing_table[uniqued_stack * 2];
	uniqued_stack = uniquing_table[uniqued_stack * 2 + 1];
	if (!thisPC && !uniqued_stack) {
	    // Invalid entry
	    fprintf(stderr, "*** stack_logging: Invalid entry 0x%x", thisPC);
	    break;
	}
	stack_frames_buffer[0] = thisPC;
	stack_frames_buffer++;
	(*num_frames)++;
	max_stack_frames--;
    }
    return 0;
}
Commit	Line	Data
e9ce8d39 A	1	/*
	2	* Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
734aad71	6	* Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
e9ce8d39	7	*
734aad71 A	8	* This file contains Original Code and/or Modifications of Original Code
	9	* as defined in and that are subject to the Apple Public Source License
	10	* Version 2.0 (the 'License'). You may not use this file except in
	11	* compliance with the License. Please obtain a copy of the License at
	12	* http://www.opensource.apple.com/apsl/ and read it before using this
	13	* file.
	14	*
	15	* The Original Code and all software distributed under the License are
	16	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
e9ce8d39 A	17	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
e9ce8d39 A	18	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
734aad71 A	19	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	20	* Please see the License for the specific language governing rights and
	21	* limitations under the License.
e9ce8d39 A	22	*
	23	* @APPLE_LICENSE_HEADER_END@
	24	*/
	25
	26	/* Bertrand from vmutils -> CF -> System */
	27
	28	#import "stack_logging.h"
	29
	30	#import <libc.h>
	31	#import <pthread.h>
	32	#import <mach/mach.h>
	33	#include <mach/vm_statistics.h>
	34
	35	extern void spin_lock(int *);
	36
	37	static inline void *allocate_pages(unsigned bytes) {
	38	void *address;
	39	if (vm_allocate(mach_task_self(), (vm_address_t *)&address, bytes,
	40	VM_MAKE_TAG(VM_MEMORY_ANALYSIS_TOOL)\| TRUE)) {
	41	address = 0;
	42	}
	43	return (void *)address;
	44	}
	45
	46	static inline void deallocate_pages(void *ptr, unsigned bytes) {
	47	vm_deallocate(mach_task_self(), (vm_address_t)ptr, bytes);
	48	}
	49
	50	static inline void copy_pages(const void source, void dest, unsigned bytes) {
	51	if (vm_copy(mach_task_self(), (vm_address_t)source, bytes, (vm_address_t)dest)) memmove(dest, source, bytes);
	52	}
	53
	54	/************* Recording stack *********/
	55
	56	static void *first_frame_address(void) {
	57	#if 0
	58	return __builtin_frame_address(1);
	59	#elif defined(__ppc__)
	60	void *addr;
	61	#warning __builtin_frame_address IS BROKEN IN BEAKER: RADAR #2340421
	62	__asm__ volatile("mr %0, r1" : "=r" (addr));
	63	return addr;
	64	#else
	65	#warning first_frame_address WILL NOT BE FUNCTIONAL ON THIS ARCHITECTURE
	66	return NULL;
	67	#endif
	68	}
	69
	70	static void next_frame_address(void addr) {
	71	void *ret;
	72	#if defined(__MACH__) && defined(__i386__)
	73	__asm__ volatile("movl (%1),%0" : "=r" (ret) : "r" (addr));
	74	#elif defined(__MACH__) && defined(__ppc__)
5b2abdfb	75	__asm__ volatile("lwz %0,0x0(%1)" : "=r" (ret) : "b" (addr));
e9ce8d39 A	76	#elif defined(__hpux__)
	77	__asm__ volatile("ldw 0x0(%1),%0" : "=r" (ret) : "r" (addr));
	78	#elif defined(__svr4__)
	79	__asm__ volatile("ta 0x3");
	80	__asm__ volatile("ld [%1 + 56],%0" : "=r" (ret) : "r" (addr));
	81	#else
	82	#error Unknown architecture
	83	#endif
	84	return ret;
	85	}
	86
	87	#if defined(__i386__) \|\| defined (__m68k__)
	88	#define FP_LINK_OFFSET 1
	89	#elif defined(__ppc__)
	90	#define FP_LINK_OFFSET 2
	91	#elif defined(__hppa__)
	92	#define FP_LINK_OFFSET -5
	93	#elif defined(__sparc__)
	94	#define FP_LINK_OFFSET 14
	95	#else
	96	#error ********** Unimplemented architecture
	97	#endif
	98
	99	void thread_stack_pcs(vm_address_t buffer, unsigned max, unsigned nb) {
	100	void *addr;
	101	addr = first_frame_address();
	102	*nb = 0;
	103	while ((addr >= (void *)0x800) && (max--)) {
	104	vm_address_t fp_link = (vm_address_t)(((unsigned *)addr)+FP_LINK_OFFSET);
	105	void *addr2;
	106	buffer[nb] = ((vm_address_t *)fp_link);
	107	(*nb)++;
	108	addr2 = next_frame_address(addr);
	109	#if defined(__ppc__)
	110	if ((unsigned)addr2 <= (unsigned)addr) break; // catch bozo frames
	111	#endif
	112	addr = addr2;
	113	}
	114	}
	115
	116	/************* Uniquing stack *********/
	117
	118	#define MAX_COLLIDE 8
	119
	120	#define MAX_NUM_PC 512
	121
	122	static int enter_pair_in_table(unsigned table, unsigned numPages, unsigned uniquedParent, unsigned thisPC) {
	123	// uniquedParent is in-out; return 1 is collisions max not exceeded
	124	unsigned base = numPages * vm_page_size / (sizeof(int)22);
	125	unsigned hash = base + (((*uniquedParent) << 4) ^ (thisPC >> 2)) % (base - 1); // modulo odd number for hashing
	126	unsigned collisions = MAX_COLLIDE;
	127	while (collisions--) {
	128	unsigned head = table + hash2;
	129	if (! head[0] && !head[1]) {
	130	/* end of chain; store this entry! */
	131	/* Note that we need to test for both head[0] and head[1] as (0, -1) is a valid entry */
	132	head[0] = thisPC;
	133	head[1] = *uniquedParent;
	134	*uniquedParent = hash;
	135	return 1;
	136	}
	137	if ((head[0] == thisPC) && (head[1] == *uniquedParent)) {
	138	/* we found the proper entry, the value for the pair is the entry offset */
	139	*uniquedParent = hash;
140	return 1;
141	}
142	hash++;
143	if (hash == base*2) hash = base;
144	}
145	return 0;
146	}
147
148	unsigned stack_logging_get_unique_stack(unsigned *table, unsigned table_num_pages, unsigned *stack_entries, unsigned count, unsigned num_hot_to_skip) {
149	unsigned uniquedParent = (unsigned)-1;
150	// we skip the warmest entries that are an artefact of the code
151	while (num_hot_to_skip--) {
152	if (count > 0) { stack_entries++; count--; }
153	}
154	while (count--) {
155	unsigned thisPC = stack_entries[count];
156	while (!enter_pair_in_table(table, table_num_pages, &uniquedParent, thisPC)) {
157	unsigned *newTable;
158	unsigned oldBytes = (table_num_pages) vm_page_size;
159	newTable = allocate_pages(oldBytes*2);
160	copy_pages(*table, newTable, oldBytes);
161	deallocate_pages(*table, oldBytes);
162	table_num_pages = 2;
163	*table = newTable;
164	}
165	}
166	return uniquedParent;
167	}
168
169	/************* Logging stack and arguments *********/
170
171	stack_logging_record_list_t *stack_logging_the_record_list = NULL;
172
173	int stack_logging_enable_logging = 0;
174
175	int stack_logging_dontcompact = 0;
176
177	static stack_logging_record_list_t GrowLogRecords(stack_logging_record_list_t records, unsigned desiredNumRecords) {
178	stack_logging_record_list_t *new_records;
179	unsigned old_size = records->overall_num_bytes;
180	if (desiredNumRecords*sizeof(stack_logging_record_t)+sizeof(stack_logging_record_list_t) < records->overall_num_bytes) return records;
181	records->overall_num_bytes += records->overall_num_bytes + vm_page_size; // in order to always get an even number of pages
182	new_records = allocate_pages(records->overall_num_bytes);
183	copy_pages(records, new_records, old_size);
184	deallocate_pages(records, old_size);
185	return new_records;
186	}
187
188	static void prepare_to_log_stack(void) {
189	if (!stack_logging_the_record_list) {
190	unsigned totalSize = 4 * vm_page_size;
191	stack_logging_the_record_list = allocate_pages(totalSize);
192	memset(stack_logging_the_record_list, 0, sizeof(stack_logging_record_list_t));
193	stack_logging_the_record_list->overall_num_bytes = totalSize;
194	stack_logging_the_record_list->uniquing_table_num_pages = 128;
195	stack_logging_the_record_list->uniquing_table = allocate_pages(stack_logging_the_record_list->uniquing_table_num_pages * vm_page_size);
196	}
197	}
198
199	void stack_logging_log_stack(unsigned type, unsigned arg1, unsigned arg2, unsigned arg3, unsigned result, unsigned num_hot_to_skip) {
200	stack_logging_record_t *rec;
201	if (!stack_logging_enable_logging) return;
202	// printf("stack_logging_log_stack 0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result);
203	if (type & stack_logging_flag_zone) {
204	// just process it now and be done with it!
205	arg1 = arg2; arg2 = arg3; arg3 = 0; type &= ~stack_logging_flag_zone;
206	}
207	if (type & stack_logging_flag_calloc) {
208	// just process it now and be done with it!
209	arg1 *= arg2; arg2 = arg3; arg3 = 0; type &= ~stack_logging_flag_calloc;
210	}
211	if (type & stack_logging_flag_object) {
212	unsigned class = (unsigned )arg1;
213	arg1 = arg2 + class[5]; // corresponds to the instance_size field
214	arg2 = 0; arg3 = 0; type = stack_logging_type_alloc;
215	}
216	if (type & stack_logging_flag_cleared) {
217	type &= ~stack_logging_flag_cleared;
218	}
219	if (type & stack_logging_flag_handle) {
220	if (stack_logging_type_alloc) {
221	if (!result) return;
222	stack_logging_log_stack(stack_logging_type_alloc, 0, 0, 0, result, num_hot_to_skip+1);
223	stack_logging_log_stack(stack_logging_type_alloc, arg1, 0, 0, ((int )result), num_hot_to_skip+1);
224	return;
225	}
226	if (stack_logging_type_dealloc) {
227	if (!arg1) return;
228	stack_logging_log_stack(stack_logging_type_dealloc, ((int )arg1), 0, 0, 0, num_hot_to_skip+1);
229	stack_logging_log_stack(stack_logging_type_dealloc, arg1, 0, 0, 0, num_hot_to_skip+1);
230	return;
231	}
232	printf("*** Unknown logging type: 0x%x\n", type);
233	}
234	if (type == stack_logging_flag_set_handle_size) {
235	if (!arg1) return;
236	// Thanks to a horrible hack, arg3 contains the prvious handle value
237	if (arg3 == ((int )arg1)) return;
238	stack_logging_log_stack(stack_logging_type_dealloc, arg3, 0, 0, 0, num_hot_to_skip+1);
239	stack_logging_log_stack(stack_logging_type_alloc, arg2, 0, 0, ((int )arg1), num_hot_to_skip+1);
240	return;
241	}
242	if (type == (stack_logging_type_dealloc\|stack_logging_type_alloc)) {
243	if (arg1 == result) return; // realloc had no effect, skipping
244	if (!arg1) {
245	// realloc(NULL, size) same as malloc(size)
246	type = stack_logging_type_alloc; arg1 = arg2; arg2 = arg3; arg3 = 0;
247	} else {
248	// realloc(arg1, arg2) -> result is same as free(arg1); malloc(arg2) -> result
249	stack_logging_log_stack(stack_logging_type_dealloc, arg1, 0, 0, 0, num_hot_to_skip+1);
250	stack_logging_log_stack(stack_logging_type_alloc, arg2, 0, 0, result, num_hot_to_skip+1);
251	return;
252	}
253	}
254	if (type == stack_logging_type_dealloc) {
255	// simple free
256	if (!arg1) return; // free(nil)
257	}
258	prepare_to_log_stack();
259	spin_lock(&stack_logging_the_record_list->lock);
260	stack_logging_enable_logging = 0;
261	stack_logging_the_record_list = GrowLogRecords(stack_logging_the_record_list, stack_logging_the_record_list->num_records + 1);
262	rec = stack_logging_the_record_list->records + stack_logging_the_record_list->num_records;
263	// We take care of the common case of alloc-dealloc
264	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))) {
265	stack_logging_the_record_list->num_records--;
266	// printf("Erased previous record in alloc-dealloc sequence\n");
267	} else {
268	unsigned stack_entries[MAX_NUM_PC];
269	unsigned count = 0;
270	rec->type = type;
271	if (type == stack_logging_type_dealloc) {
272	rec->argument = 0;
273	rec->address = STACK_LOGGING_DISGUISE(arg1); // we disguise the address
274	} else if (type == stack_logging_type_alloc) {
275	rec->argument = arg1;
276	rec->address = STACK_LOGGING_DISGUISE(result); // we disguise the address
277	} else {
278	rec->argument = arg2;
279	rec->address = STACK_LOGGING_DISGUISE(arg1); // we disguise the address
280	}
281	// printf("Before getting samples 0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result);
282	thread_stack_pcs(stack_entries, MAX_NUM_PC - 1, &count);
283	// We put at the bottom of the stack a marker that denotes the thread (+1 for good measure...)
284	stack_entries[count++] = (int)pthread_self() + 1;
285	/* now let's unique the sample */
286	// printf("Uniquing 0x%x 0x%x 0x%x 0x%x -> 0x%x\n", type, arg1, arg2, arg3, result);
287	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
288	stack_logging_the_record_list->num_records++;
289	}
290	stack_logging_enable_logging = 1;
291	stack_logging_the_record_list->lock = 0;
292	}
293
294	static kern_return_t default_reader(task_t task, vm_address_t address, vm_size_t size, void **ptr) {
295	ptr = (void )address;
296	return 0;
297	}
298
299	static kern_return_t get_remote_records(task_t task, memory_reader_t reader, stack_logging_record_list_t **records) {
300	// sets records
301	vm_address_t *remote_records_address_ref;
302	kern_return_t err;
303	*records = NULL;
304	err = reader(task, (vm_address_t)&stack_logging_the_record_list, sizeof(vm_address_t), (void **)&remote_records_address_ref);
305	if (err) return err;
306	if (!*remote_records_address_ref) {
307	// printf("stack_logging: no stack record\n");
308	return 0;
309	}
310	// printf("stack_logging: stack records at %p\n", (void )(remote_records_address_ref));
311	// printf("stack_logging: reading %d bytes\n", sizeof(stack_logging_record_list_t));
312	err = reader(task, remote_records_address_ref, sizeof(stack_logging_record_list_t), (void *)records); // get the list head
313	if (err) return err;
314	// printf("stack_logging: overall num bytes = %d\n", records->overall_num_bytes);
315	return reader(task, remote_records_address_ref, (records)->overall_num_bytes, (void **)records);
316	}
317
318	kern_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) {
319	stack_logging_record_list_t *records;
320	kern_return_t err;
321	unsigned index;
322	unsigned disguised = STACK_LOGGING_DISGUISE(address);
323	if (!reader) reader = default_reader;
324	*num_frames = 0;
325	err = get_remote_records(task, reader, &records);
326	if (err \|\| !records) return err;
327	// printf("stack_logging: %d records\n", records->num_records);
328	index = 0;
329	while (index < records->num_records) {
330	stack_logging_record_t *record = records->records + index;
331	if (record->address == disguised) {
332	return stack_logging_frames_for_uniqued_stack(task, reader, record->uniqued_stack, stack_frames_buffer, max_stack_frames, num_frames);
333	}
334	index++;
335	}
336	fprintf(stderr, "*** stack_logging: no record found for 0x%x\n", address);
337	return 0;
338	}
339
340	kern_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) {
341	stack_logging_record_list_t *records;
342	kern_return_t err;
343	unsigned index;
344	unsigned disguised = STACK_LOGGING_DISGUISE(address);
345	if (!reader) reader = default_reader;
346	err = get_remote_records(task, reader, &records);
347	if (err \|\| !records) return err;
348	// printf("stack_logging: %d records\n", records->num_records);
349	index = 0;
350	while (index < records->num_records) {
351	stack_logging_record_t *record = records->records + index;
352	if (!address \|\| (record->address == disguised)) enumerator(*record, context);
353	index++;
354	}
355	return 0;
356	}
357
358	kern_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) {
359	stack_logging_record_list_t *records;
360	unsigned *uniquing_table;
361	kern_return_t err;
362	if (!reader) reader = default_reader;
363	*num_frames = 0;
364	err = get_remote_records(task, reader, &records);
365	if (err \|\| !records) return err;
366	err = reader(task, (vm_address_t)records->uniquing_table, records->uniquing_table_num_pages * vm_page_size, (void **)&uniquing_table);
367	if (err) return err;
368	while (max_stack_frames && (uniqued_stack != -1)) {
369	unsigned thisPC;
370	if ((uniqued_stack * 2 + 1) * sizeof(unsigned) >= records->uniquing_table_num_pages * vm_page_size) {
371	fprintf(stderr, "*** stack_logging: Invalid uniqued stack 0x%x", uniqued_stack);
372	break;
373	}
374	thisPC = uniquing_table[uniqued_stack * 2];
375	uniqued_stack = uniquing_table[uniqued_stack * 2 + 1];
376	if (!thisPC && !uniqued_stack) {
377	// Invalid entry
378	fprintf(stderr, "*** stack_logging: Invalid entry 0x%x", thisPC);
379	break;
380	}
381	stack_frames_buffer[0] = thisPC;
382	stack_frames_buffer++;
383	(*num_frames)++;
384	max_stack_frames--;
385	}
386	return 0;
387	}