#define JEMALLOC_PROF_C_

#include "jemalloc/internal/jemalloc_preamble.h"

#include "jemalloc/internal/jemalloc_internal_includes.h"

#include "jemalloc/internal/assert.h"

#include "jemalloc/internal/ckh.h"

#include "jemalloc/internal/hash.h"

#include "jemalloc/internal/malloc_io.h"

#include "jemalloc/internal/mutex.h"

#include "jemalloc/internal/emitter.h"

/******************************************************************************/

#ifdef JEMALLOC_PROF_LIBUNWIND

#define UNW_LOCAL_ONLY

#include <libunwind.h>

#endif

#ifdef JEMALLOC_PROF_LIBGCC

/*

 * We have a circular dependency -- jemalloc_internal.h tells us if we should

 * use libgcc's unwinding functionality, but after we've included that, we've

 * already hooked _Unwind_Backtrace.  We'll temporarily disable hooking.

 */

#undef _Unwind_Backtrace

#include <unwind.h>

#define _Unwind_Backtrace JEMALLOC_HOOK(_Unwind_Backtrace, test_hooks_libc_hook)

#endif

/******************************************************************************/

/* Data. */

bool		opt_prof = false;

bool		opt_prof_active = true;

bool		opt_prof_thread_active_init = true;

size_t		opt_lg_prof_sample = LG_PROF_SAMPLE_DEFAULT;

ssize_t		opt_lg_prof_interval = LG_PROF_INTERVAL_DEFAULT;

bool		opt_prof_gdump = false;

bool		opt_prof_final = false;

bool		opt_prof_leak = false;

bool		opt_prof_accum = false;

bool		opt_prof_log = false;

char		opt_prof_prefix[

    /* Minimize memory bloat for non-prof builds. */

#ifdef JEMALLOC_PROF

    PATH_MAX +

#endif

    1];

/*

 * Initialized as opt_prof_active, and accessed via

 * prof_active_[gs]et{_unlocked,}().

 */

bool			prof_active;

static malloc_mutex_t	prof_active_mtx;

/*

 * Initialized as opt_prof_thread_active_init, and accessed via

 * prof_thread_active_init_[gs]et().

 */

static bool		prof_thread_active_init;

static malloc_mutex_t	prof_thread_active_init_mtx;

/*

 * Initialized as opt_prof_gdump, and accessed via

 * prof_gdump_[gs]et{_unlocked,}().

 */

bool			prof_gdump_val;

static malloc_mutex_t	prof_gdump_mtx;

uint64_t	prof_interval = 0;

size_t		lg_prof_sample;

typedef enum prof_logging_state_e prof_logging_state_t;

enum prof_logging_state_e {

	prof_logging_state_stopped,

	prof_logging_state_started,

	prof_logging_state_dumping

};

/*

 * - stopped: log_start never called, or previous log_stop has completed.

 * - started: log_start called, log_stop not called yet. Allocations are logged.

 * - dumping: log_stop called but not finished; samples are not logged anymore.

 */

prof_logging_state_t prof_logging_state = prof_logging_state_stopped;

#ifdef JEMALLOC_JET

static bool prof_log_dummy = false;

#endif

/* Incremented for every log file that is output. */

static uint64_t log_seq = 0;

static char log_filename[

    /* Minimize memory bloat for non-prof builds. */

#ifdef JEMALLOC_PROF

    PATH_MAX +

#endif

    1];

/* Timestamp for most recent call to log_start(). */

static nstime_t log_start_timestamp = NSTIME_ZERO_INITIALIZER;

/* Increment these when adding to the log_bt and log_thr linked lists. */

static size_t log_bt_index = 0;

static size_t log_thr_index = 0;

/* Linked list node definitions. These are only used in prof.c. */

typedef struct prof_bt_node_s prof_bt_node_t;

struct prof_bt_node_s {

	prof_bt_node_t *next;

	size_t index;

	prof_bt_t bt;

	/* Variable size backtrace vector pointed to by bt. */

	void *vec[1];

};

typedef struct prof_thr_node_s prof_thr_node_t;

struct prof_thr_node_s {

	prof_thr_node_t *next;

	size_t index;

	uint64_t thr_uid;

	/* Variable size based on thr_name_sz. */

	char name[1];

};

typedef struct prof_alloc_node_s prof_alloc_node_t;

/* This is output when logging sampled allocations. */

struct prof_alloc_node_s {

	prof_alloc_node_t *next;

	/* Indices into an array of thread data. */

	size_t alloc_thr_ind;

	size_t free_thr_ind;

	/* Indices into an array of backtraces. */

	size_t alloc_bt_ind;

	size_t free_bt_ind;

	uint64_t alloc_time_ns;

	uint64_t free_time_ns;

	size_t usize;

};

/*

 * Created on the first call to prof_log_start and deleted on prof_log_stop.

 * These are the backtraces and threads that have already been logged by an

 * allocation.

 */

static bool log_tables_initialized = false;

static ckh_t log_bt_node_set;

static ckh_t log_thr_node_set;

/* Store linked lists for logged data. */

static prof_bt_node_t *log_bt_first = NULL;

static prof_bt_node_t *log_bt_last = NULL;

static prof_thr_node_t *log_thr_first = NULL;

static prof_thr_node_t *log_thr_last = NULL;

static prof_alloc_node_t *log_alloc_first = NULL;

static prof_alloc_node_t *log_alloc_last = NULL;

/* Protects the prof_logging_state and any log_{...} variable. */

static malloc_mutex_t log_mtx;

/*

 * Table of mutexes that are shared among gctx's.  These are leaf locks, so

 * there is no problem with using them for more than one gctx at the same time.

 * The primary motivation for this sharing though is that gctx's are ephemeral,

 * and destroying mutexes causes complications for systems that allocate when

 * creating/destroying mutexes.

 */

static malloc_mutex_t	*gctx_locks;

static atomic_u_t	cum_gctxs; /* Atomic counter. */

/*

 * Table of mutexes that are shared among tdata's.  No operations require

 * holding multiple tdata locks, so there is no problem with using them for more

 * than one tdata at the same time, even though a gctx lock may be acquired

 * while holding a tdata lock.

 */

static malloc_mutex_t	*tdata_locks;

/*

 * Global hash of (prof_bt_t *)-->(prof_gctx_t *).  This is the master data

 * structure that knows about all backtraces currently captured.

 */

static ckh_t		bt2gctx;

/* Non static to enable profiling. */

malloc_mutex_t		bt2gctx_mtx;

/*

 * Tree of all extant prof_tdata_t structures, regardless of state,

 * {attached,detached,expired}.

 */

static prof_tdata_tree_t	tdatas;

static malloc_mutex_t	tdatas_mtx;

static uint64_t		next_thr_uid;

static malloc_mutex_t	next_thr_uid_mtx;

static malloc_mutex_t	prof_dump_seq_mtx;

static uint64_t		prof_dump_seq;

static uint64_t		prof_dump_iseq;

static uint64_t		prof_dump_mseq;

static uint64_t		prof_dump_useq;

/*

 * This buffer is rather large for stack allocation, so use a single buffer for

 * all profile dumps.

 */

static malloc_mutex_t	prof_dump_mtx;

static char		prof_dump_buf[

    /* Minimize memory bloat for non-prof builds. */

#ifdef JEMALLOC_PROF

    PROF_DUMP_BUFSIZE

#else

    1

#endif

];

static size_t		prof_dump_buf_end;

static int		prof_dump_fd;

/* Do not dump any profiles until bootstrapping is complete. */

static bool		prof_booted = false;

/******************************************************************************/

/*

 * Function prototypes for static functions that are referenced prior to

 * definition.

 */

static bool	prof_tctx_should_destroy(tsdn_t *tsdn, prof_tctx_t *tctx);

static void	prof_tctx_destroy(tsd_t *tsd, prof_tctx_t *tctx);

static bool	prof_tdata_should_destroy(tsdn_t *tsdn, prof_tdata_t *tdata,

    bool even_if_attached);

static void	prof_tdata_destroy(tsd_t *tsd, prof_tdata_t *tdata,

    bool even_if_attached);

static char	*prof_thread_name_alloc(tsdn_t *tsdn, const char *thread_name);

/* Hashtable functions for log_bt_node_set and log_thr_node_set. */

static void prof_thr_node_hash(const void *key, size_t r_hash[2]);

static bool prof_thr_node_keycomp(const void *k1, const void *k2);

static void prof_bt_node_hash(const void *key, size_t r_hash[2]);

static bool prof_bt_node_keycomp(const void *k1, const void *k2);

/******************************************************************************/

/* Red-black trees. */

static int

prof_tctx_comp(const prof_tctx_t *a, const prof_tctx_t *b) {

	uint64_t a_thr_uid = a->thr_uid;

	uint64_t b_thr_uid = b->thr_uid;

	int ret = (a_thr_uid > b_thr_uid) - (a_thr_uid < b_thr_uid);

	if (ret == 0) {

		uint64_t a_thr_discrim = a->thr_discrim;

		uint64_t b_thr_discrim = b->thr_discrim;

		ret = (a_thr_discrim > b_thr_discrim) - (a_thr_discrim <

		    b_thr_discrim);

		if (ret == 0) {

			uint64_t a_tctx_uid = a->tctx_uid;

			uint64_t b_tctx_uid = b->tctx_uid;

			ret = (a_tctx_uid > b_tctx_uid) - (a_tctx_uid <

			    b_tctx_uid);

		}

	}

	return ret;

}

rb_gen(static UNUSED, tctx_tree_, prof_tctx_tree_t, prof_tctx_t,

    tctx_link, prof_tctx_comp)

static int

prof_gctx_comp(const prof_gctx_t *a, const prof_gctx_t *b) {

	unsigned a_len = a->bt.len;

	unsigned b_len = b->bt.len;

	unsigned comp_len = (a_len < b_len) ? a_len : b_len;

	int ret = memcmp(a->bt.vec, b->bt.vec, comp_len * sizeof(void *));

	if (ret == 0) {

		ret = (a_len > b_len) - (a_len < b_len);

	}

	return ret;

}

rb_gen(static UNUSED, gctx_tree_, prof_gctx_tree_t, prof_gctx_t, dump_link,

    prof_gctx_comp)

static int

prof_tdata_comp(const prof_tdata_t *a, const prof_tdata_t *b) {

	int ret;

	uint64_t a_uid = a->thr_uid;

	uint64_t b_uid = b->thr_uid;

	ret = ((a_uid > b_uid) - (a_uid < b_uid));

	if (ret == 0) {

		uint64_t a_discrim = a->thr_discrim;

		uint64_t b_discrim = b->thr_discrim;

		ret = ((a_discrim > b_discrim) - (a_discrim < b_discrim));

	}

	return ret;

}

rb_gen(static UNUSED, tdata_tree_, prof_tdata_tree_t, prof_tdata_t, tdata_link,

    prof_tdata_comp)

/******************************************************************************/

void

prof_alloc_rollback(tsd_t *tsd, prof_tctx_t *tctx, bool updated) {

	prof_tdata_t *tdata;

	cassert(config_prof);

	if (updated) {

		/*

		 * Compute a new sample threshold.  This isn't very important in

		 * practice, because this function is rarely executed, so the

		 * potential for sample bias is minimal except in contrived

		 * programs.

		 */

		tdata = prof_tdata_get(tsd, true);

		if (tdata != NULL) {

			prof_sample_threshold_update(tdata);

		}

	}

	if ((uintptr_t)tctx > (uintptr_t)1U) {

		malloc_mutex_lock(tsd_tsdn(tsd), tctx->tdata->lock);

		tctx->prepared = false;

		if (prof_tctx_should_destroy(tsd_tsdn(tsd), tctx)) {

			prof_tctx_destroy(tsd, tctx);

		} else {

			malloc_mutex_unlock(tsd_tsdn(tsd), tctx->tdata->lock);

		}

	}

}

void

prof_malloc_sample_object(tsdn_t *tsdn, const void *ptr, size_t usize,

    prof_tctx_t *tctx) {

	prof_tctx_set(tsdn, ptr, usize, NULL, tctx);

	/* Get the current time and set this in the extent_t. We'll read this

	 * when free() is called. */

	nstime_t t = NSTIME_ZERO_INITIALIZER;

	nstime_update(&t);

	prof_alloc_time_set(tsdn, ptr, NULL, t);

	malloc_mutex_lock(tsdn, tctx->tdata->lock);

	tctx->cnts.curobjs++;

	tctx->cnts.curbytes += usize;

	if (opt_prof_accum) {

		tctx->cnts.accumobjs++;

		tctx->cnts.accumbytes += usize;

	}

	tctx->prepared = false;

	malloc_mutex_unlock(tsdn, tctx->tdata->lock);

}

static size_t

prof_log_bt_index(tsd_t *tsd, prof_bt_t *bt) {

	assert(prof_logging_state == prof_logging_state_started);

	malloc_mutex_assert_owner(tsd_tsdn(tsd), &log_mtx);

	prof_bt_node_t dummy_node;

	dummy_node.bt = *bt;

	prof_bt_node_t *node;

	/* See if this backtrace is already cached in the table. */

	if (ckh_search(&log_bt_node_set, (void *)(&dummy_node),

	    (void **)(&node), NULL)) {

		size_t sz = offsetof(prof_bt_node_t, vec) +

			        (bt->len * sizeof(void *));

		prof_bt_node_t *new_node = (prof_bt_node_t *)

		    iallocztm(tsd_tsdn(tsd), sz, sz_size2index(sz), false, NULL,

		    true, arena_get(TSDN_NULL, 0, true), true);

		if (log_bt_first == NULL) {

			log_bt_first = new_node;

			log_bt_last = new_node;

		} else {

			log_bt_last->next = new_node;

			log_bt_last = new_node;

		}

		new_node->next = NULL;

		new_node->index = log_bt_index;

		/*

		 * Copy the backtrace: bt is inside a tdata or gctx, which

		 * might die before prof_log_stop is called.

		 */

		new_node->bt.len = bt->len;

		memcpy(new_node->vec, bt->vec, bt->len * sizeof(void *));

		new_node->bt.vec = new_node->vec;

		log_bt_index++;

		ckh_insert(tsd, &log_bt_node_set, (void *)new_node, NULL);

		return new_node->index;

	} else {

		return node->index;

	}

}

static size_t

prof_log_thr_index(tsd_t *tsd, uint64_t thr_uid, const char *name) {

	assert(prof_logging_state == prof_logging_state_started);

	malloc_mutex_assert_owner(tsd_tsdn(tsd), &log_mtx);

	prof_thr_node_t dummy_node;

	dummy_node.thr_uid = thr_uid;

	prof_thr_node_t *node;

	/* See if this thread is already cached in the table. */

	if (ckh_search(&log_thr_node_set, (void *)(&dummy_node),

	    (void **)(&node), NULL)) {

		size_t sz = offsetof(prof_thr_node_t, name) + strlen(name) + 1;

		prof_thr_node_t *new_node = (prof_thr_node_t *)

		    iallocztm(tsd_tsdn(tsd), sz, sz_size2index(sz), false, NULL,

		    true, arena_get(TSDN_NULL, 0, true), true);

		if (log_thr_first == NULL) {

			log_thr_first = new_node;

			log_thr_last = new_node;

		} else {

			log_thr_last->next = new_node;

			log_thr_last = new_node;

		}

		new_node->next = NULL;

		new_node->index = log_thr_index;

		new_node->thr_uid = thr_uid;

		strcpy(new_node->name, name);

		log_thr_index++;

		ckh_insert(tsd, &log_thr_node_set, (void *)new_node, NULL);

		return new_node->index;

	} else {

		return node->index;

	}

}

static void

prof_try_log(tsd_t *tsd, const void *ptr, size_t usize, prof_tctx_t *tctx) {

	malloc_mutex_assert_owner(tsd_tsdn(tsd), tctx->tdata->lock);

	prof_tdata_t *cons_tdata = prof_tdata_get(tsd, false);

	if (cons_tdata == NULL) {

		/*

		 * We decide not to log these allocations. cons_tdata will be

		 * NULL only when the current thread is in a weird state (e.g.

		 * it's being destroyed).

		 */

		return;

	}

	malloc_mutex_lock(tsd_tsdn(tsd), &log_mtx);

	if (prof_logging_state != prof_logging_state_started) {

		goto label_done;

	}

	if (!log_tables_initialized) {

		bool err1 = ckh_new(tsd, &log_bt_node_set, PROF_CKH_MINITEMS,

				prof_bt_node_hash, prof_bt_node_keycomp);

		bool err2 = ckh_new(tsd, &log_thr_node_set, PROF_CKH_MINITEMS,

				prof_thr_node_hash, prof_thr_node_keycomp);

		if (err1 || err2) {

			goto label_done;

		}

		log_tables_initialized = true;

	}

	nstime_t alloc_time = prof_alloc_time_get(tsd_tsdn(tsd), ptr,

			          (alloc_ctx_t *)NULL);

	nstime_t free_time = NSTIME_ZERO_INITIALIZER;

	nstime_update(&free_time);

	size_t sz = sizeof(prof_alloc_node_t);

	prof_alloc_node_t *new_node = (prof_alloc_node_t *)

	    iallocztm(tsd_tsdn(tsd), sz, sz_size2index(sz), false, NULL, true,

	    arena_get(TSDN_NULL, 0, true), true);

	const char *prod_thr_name = (tctx->tdata->thread_name == NULL)?

				        "" : tctx->tdata->thread_name;

	const char *cons_thr_name = prof_thread_name_get(tsd);

	prof_bt_t bt;

	/* Initialize the backtrace, using the buffer in tdata to store it. */

	bt_init(&bt, cons_tdata->vec);

	prof_backtrace(&bt;;

	prof_bt_t *cons_bt = &bt;

	/* We haven't destroyed tctx yet, so gctx should be good to read. */

	prof_bt_t *prod_bt = &tctx->gctx->bt;

	new_node->next = NULL;

	new_node->alloc_thr_ind = prof_log_thr_index(tsd, tctx->tdata->thr_uid,

				      prod_thr_name);

	new_node->free_thr_ind = prof_log_thr_index(tsd, cons_tdata->thr_uid,

				     cons_thr_name);

	new_node->alloc_bt_ind = prof_log_bt_index(tsd, prod_bt);

	new_node->free_bt_ind = prof_log_bt_index(tsd, cons_bt);

	new_node->alloc_time_ns = nstime_ns(&alloc_time);

	new_node->free_time_ns = nstime_ns(&free_time);

	new_node->usize = usize;

	if (log_alloc_first == NULL) {

		log_alloc_first = new_node;

		log_alloc_last = new_node;

	} else {

		log_alloc_last->next = new_node;

		log_alloc_last = new_node;

	}

label_done:

	malloc_mutex_unlock(tsd_tsdn(tsd), &log_mtx);

}

void

prof_free_sampled_object(tsd_t *tsd, const void *ptr, size_t usize,

    prof_tctx_t *tctx) {

	malloc_mutex_lock(tsd_tsdn(tsd), tctx->tdata->lock);

	assert(tctx->cnts.curobjs > 0);

	assert(tctx->cnts.curbytes >= usize);

	tctx->cnts.curobjs--;

	tctx->cnts.curbytes -= usize;

	prof_try_log(tsd, ptr, usize, tctx);

	if (prof_tctx_should_destroy(tsd_tsdn(tsd), tctx)) {

		prof_tctx_destroy(tsd, tctx);

	} else {

		malloc_mutex_unlock(tsd_tsdn(tsd), tctx->tdata->lock);

	}

}

void

bt_init(prof_bt_t *bt, void **vec) {

	cassert(config_prof);

	bt->vec = vec;

	bt->len = 0;

}

static void

prof_enter(tsd_t *tsd, prof_tdata_t *tdata) {

	cassert(config_prof);

	assert(tdata == prof_tdata_get(tsd, false));

	if (tdata != NULL) {

		assert(!tdata->enq);

		tdata->enq = true;

	}

	malloc_mutex_lock(tsd_tsdn(tsd), &bt2gctx_mtx);

}

static void

prof_leave(tsd_t *tsd, prof_tdata_t *tdata) {

	cassert(config_prof);

	assert(tdata == prof_tdata_get(tsd, false));

	malloc_mutex_unlock(tsd_tsdn(tsd), &bt2gctx_mtx);

	if (tdata != NULL) {

		bool idump, gdump;

		assert(tdata->enq);

		tdata->enq = false;

		idump = tdata->enq_idump;

		tdata->enq_idump = false;

		gdump = tdata->enq_gdump;

		tdata->enq_gdump = false;

		if (idump) {

			prof_idump(tsd_tsdn(tsd));

		}

		if (gdump) {

			prof_gdump(tsd_tsdn(tsd));

		}

	}

}

#ifdef JEMALLOC_PROF_LIBUNWIND

void

prof_backtrace(prof_bt_t *bt) {

	int nframes;

	cassert(config_prof);

	assert(bt->len == 0);

	assert(bt->vec != NULL);

	nframes = unw_backtrace(bt->vec, PROF_BT_MAX);

	if (nframes <= 0) {

		return;

	}

	bt->len = nframes;

}

#elif (defined(JEMALLOC_PROF_LIBGCC))

static _Unwind_Reason_Code

prof_unwind_init_callback(struct _Unwind_Context *context, void *arg) {

	cassert(config_prof);

	return _URC_NO_REASON;

}

static _Unwind_Reason_Code

prof_unwind_callback(struct _Unwind_Context *context, void *arg) {

	prof_unwind_data_t *data = (prof_unwind_data_t *)arg;

	void *ip;

	cassert(config_prof);

	ip = (void *)_Unwind_GetIP(context);

	if (ip == NULL) {

		return _URC_END_OF_STACK;

	}

	data->bt->vec[data->bt->len] = ip;

	data->bt->len++;

	if (data->bt->len == data->max) {

		return _URC_END_OF_STACK;

	}

	return _URC_NO_REASON;

}

void

prof_backtrace(prof_bt_t *bt) {

	prof_unwind_data_t data = {bt, PROF_BT_MAX};

	cassert(config_prof);

	_Unwind_Backtrace(prof_unwind_callback, &data);

}

#elif (defined(JEMALLOC_PROF_GCC))

void

prof_backtrace(prof_bt_t *bt) {

#define BT_FRAME(i)							\

	if ((i) < PROF_BT_MAX) {					\

		void *p;						\

		if (__builtin_frame_address(i) == 0) {			\

			return;						\

		}							\

		p = __builtin_return_address(i);			\

		if (p == NULL) {					\

			return;						\

		}							\

		bt->vec[(i)] = p;					\

		bt->len = (i) + 1;					\

	} else {							\

		return;							\

	}

	cassert(config_prof);

	BT_FRAME(0)

	BT_FRAME(1)

	BT_FRAME(2)

	BT_FRAME(3)

	BT_FRAME(4)

	BT_FRAME(5)

	BT_FRAME(6)

	BT_FRAME(7)

	BT_FRAME(8)

	BT_FRAME(9)

	BT_FRAME(10)

	BT_FRAME(11)

	BT_FRAME(12)

	BT_FRAME(13)

	BT_FRAME(14)

	BT_FRAME(15)

	BT_FRAME(16)

	BT_FRAME(17)

	BT_FRAME(18)

	BT_FRAME(19)

	BT_FRAME(20)

	BT_FRAME(21)

	BT_FRAME(22)

	BT_FRAME(23)

	BT_FRAME(24)

	BT_FRAME(25)

	BT_FRAME(26)

	BT_FRAME(27)

	BT_FRAME(28)

	BT_FRAME(29)

	BT_FRAME(30)

	BT_FRAME(31)

	BT_FRAME(32)

	BT_FRAME(33)

	BT_FRAME(34)

	BT_FRAME(35)

	BT_FRAME(36)

	BT_FRAME(37)

	BT_FRAME(38)

	BT_FRAME(39)

	BT_FRAME(40)

	BT_FRAME(41)

	BT_FRAME(42)

	BT_FRAME(43)

	BT_FRAME(44)

	BT_FRAME(45)

	BT_FRAME(46)

	BT_FRAME(47)

	BT_FRAME(48)

	BT_FRAME(49)

	BT_FRAME(50)

	BT_FRAME(51)

	BT_FRAME(52)

	BT_FRAME(53)

	BT_FRAME(54)

	BT_FRAME(55)

	BT_FRAME(56)

	BT_FRAME(57)

	BT_FRAME(58)

	BT_FRAME(59)

	BT_FRAME(60)

	BT_FRAME(61)

	BT_FRAME(62)

	BT_FRAME(63)

	BT_FRAME(64)

	BT_FRAME(65)

	BT_FRAME(66)

	BT_FRAME(67)

	BT_FRAME(68)

	BT_FRAME(69)

	BT_FRAME(70)

	BT_FRAME(71)

	BT_FRAME(72)

	BT_FRAME(73)

	BT_FRAME(74)

	BT_FRAME(75)

	BT_FRAME(76)

	BT_FRAME(77)

	BT_FRAME(78)

	BT_FRAME(79)

	BT_FRAME(80)

	BT_FRAME(81)

	BT_FRAME(82)

	BT_FRAME(83)

	BT_FRAME(84)

	BT_FRAME(85)

	BT_FRAME(86)

	BT_FRAME(87)

	BT_FRAME(88)

	BT_FRAME(89)

	BT_FRAME(90)

	BT_FRAME(91)

	BT_FRAME(92)

	BT_FRAME(93)

	BT_FRAME(94)

	BT_FRAME(95)

	BT_FRAME(96)

	BT_FRAME(97)

	BT_FRAME(98)

	BT_FRAME(99)

	BT_FRAME(100)

	BT_FRAME(101)

	BT_FRAME(102)

	BT_FRAME(103)

	BT_FRAME(104)

	BT_FRAME(105)

	BT_FRAME(106)

	BT_FRAME(107)

	BT_FRAME(108)

	BT_FRAME(109)

	BT_FRAME(110)

	BT_FRAME(111)

	BT_FRAME(112)

	BT_FRAME(113)

	BT_FRAME(114)

	BT_FRAME(115)

	BT_FRAME(116)

	BT_FRAME(117)

	BT_FRAME(118)

	BT_FRAME(119)

	BT_FRAME(120)

	BT_FRAME(121)

	BT_FRAME(122)

	BT_FRAME(123)

	BT_FRAME(124)

	BT_FRAME(125)

	BT_FRAME(126)

	BT_FRAME(127)

#undef BT_FRAME

}

#else

void

prof_backtrace(prof_bt_t *bt) {

	cassert(config_prof);

	not_reached();

}

#endif

static malloc_mutex_t *

prof_gctx_mutex_choose(void) {

	unsigned ngctxs = atomic_fetch_add_u(&cum_gctxs, 1, ATOMIC_RELAXED);

	return &gctx_locks[(ngctxs - 1) % PROF_NCTX_LOCKS];

}

static malloc_mutex_t *

prof_tdata_mutex_choose(uint64_t thr_uid) {

	return &tdata_locks[thr_uid % PROF_NTDATA_LOCKS];

}

static prof_gctx_t *

prof_gctx_create(tsdn_t *tsdn, prof_bt_t *bt) {

	/*

	 * Create a single allocation that has space for vec of length bt->len.

	 */

	size_t size = offsetof(prof_gctx_t, vec) + (bt->len * sizeof(void *));

	prof_gctx_t *gctx = (prof_gctx_t *)iallocztm(tsdn, size,

	    sz_size2index(size), false, NULL, true, arena_get(TSDN_NULL, 0, true),

	    true);

	if (gctx == NULL) {

		return NULL;

	}

	gctx->lock = prof_gctx_mutex_choose();

	/*

	 * Set nlimbo to 1, in order to avoid a race condition with

	 * prof_tctx_destroy()/prof_gctx_try_destroy().

	 */

	gctx->nlimbo = 1;

	tctx_tree_new(&gctx->tctxs);

	/* Duplicate bt. */

	memcpy(gctx->vec, bt->vec, bt->len * sizeof(void *));

	gctx->bt.vec = gctx->vec;

	gctx->bt.len = bt->len;

	return gctx;

}

static void

prof_gctx_try_destroy(tsd_t *tsd, prof_tdata_t *tdata_self, prof_gctx_t *gctx,

    prof_tdata_t *tdata) {

	cassert(config_prof);

	/*

	 * Check that gctx is still unused by any thread cache before destroying

	 * it.  prof_lookup() increments gctx->nlimbo in order to avoid a race

	 * condition with this function, as does prof_tctx_destroy() in order to

	 * avoid a race between the main body of prof_tctx_destroy() and entry

	 * into this function.

	 */

	prof_enter(tsd, tdata_self);

	malloc_mutex_lock(tsd_tsdn(tsd), gctx->lock);

	assert(gctx->nlimbo != 0);

	if (tctx_tree_empty(&gctx->tctxs) && gctx->nlimbo == 1) {

		/* Remove gctx from bt2gctx. */

		if (ckh_remove(tsd, &bt2gctx, &gctx->bt, NULL, NULL)) {

			not_reached();

		}

		prof_leave(tsd, tdata_self);

		/* Destroy gctx. */

		malloc_mutex_unlock(tsd_tsdn(tsd), gctx->lock);

		idalloctm(tsd_tsdn(tsd), gctx, NULL, NULL, true, true);

	} else {

		/*

		 * Compensate for increment in prof_tctx_destroy() or

		 * prof_lookup().

		 */

		gctx->nlimbo--;

		malloc_mutex_unlock(tsd_tsdn(tsd), gctx->lock);

		prof_leave(tsd, tdata_self);

	}

}