[linux-2.6-block.git] / tools / perf / util / thread-stack.c

/*
 * thread-stack.c: Synthesize a thread's stack using call / return events
 * Copyright (c) 2014, Intel Corporation.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms and conditions of the GNU General Public License,
 * version 2, as published by the Free Software Foundation.
 *
 * This program is distributed in the hope it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 */

#include <linux/rbtree.h>
#include <linux/list.h>
#include <errno.h>
#include "thread.h"
#include "event.h"
#include "machine.h"
#include "util.h"
#include "debug.h"
#include "symbol.h"
#include "comm.h"
#include "call-path.h"
#include "thread-stack.h"

#define STACK_GROWTH 2048

/**
 * struct thread_stack_entry - thread stack entry.
 * @ret_addr: return address
 * @timestamp: timestamp (if known)
 * @ref: external reference (e.g. db_id of sample)
 * @branch_count: the branch count when the entry was created
 * @cp: call path
 * @no_call: a 'call' was not seen
 * @trace_end: a 'call' but trace ended
 */
struct thread_stack_entry {
	u64 ret_addr;
	u64 timestamp;
	u64 ref;
	u64 branch_count;
	struct call_path *cp;
	bool no_call;
	bool trace_end;
};

/**
 * struct thread_stack - thread stack constructed from 'call' and 'return'
 *                       branch samples.
 * @stack: array that holds the stack
 * @cnt: number of entries in the stack
 * @sz: current maximum stack size
 * @trace_nr: current trace number
 * @branch_count: running branch count
 * @kernel_start: kernel start address
 * @last_time: last timestamp
 * @crp: call/return processor
 * @comm: current comm
 */
struct thread_stack {
	struct thread_stack_entry *stack;
	size_t cnt;
	size_t sz;
	u64 trace_nr;
	u64 branch_count;
	u64 kernel_start;
	u64 last_time;
	struct call_return_processor *crp;
	struct comm *comm;
};

static int thread_stack__grow(struct thread_stack *ts)
{
	struct thread_stack_entry *new_stack;
	size_t sz, new_sz;

	new_sz = ts->sz + STACK_GROWTH;
	sz = new_sz * sizeof(struct thread_stack_entry);

	new_stack = realloc(ts->stack, sz);
	if (!new_stack)
		return -ENOMEM;

	ts->stack = new_stack;
	ts->sz = new_sz;

	return 0;
}

static struct thread_stack *thread_stack__new(struct thread *thread,
					      struct call_return_processor *crp)
{
	struct thread_stack *ts;

	ts = zalloc(sizeof(struct thread_stack));
	if (!ts)
		return NULL;

	if (thread_stack__grow(ts)) {
		free(ts);
		return NULL;
	}

	if (thread->mg && thread->mg->machine)
		ts->kernel_start = machine__kernel_start(thread->mg->machine);
	else
		ts->kernel_start = 1ULL << 63;
	ts->crp = crp;

	return ts;
}

static int thread_stack__push(struct thread_stack *ts, u64 ret_addr,
			      bool trace_end)
{
	int err = 0;

	if (ts->cnt == ts->sz) {
		err = thread_stack__grow(ts);
		if (err) {
			pr_warning("Out of memory: discarding thread stack\n");
			ts->cnt = 0;
		}
	}

	ts->stack[ts->cnt].trace_end = trace_end;
	ts->stack[ts->cnt++].ret_addr = ret_addr;

	return err;
}

static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr)
{
	size_t i;

	/*
	 * In some cases there may be functions which are not seen to return.
	 * For example when setjmp / longjmp has been used.  Or the perf context
	 * switch in the kernel which doesn't stop and start tracing in exactly
	 * the same code path.  When that happens the return address will be
	 * further down the stack.  If the return address is not found at all,
	 * we assume the opposite (i.e. this is a return for a call that wasn't
	 * seen for some reason) and leave the stack alone.
	 */
	for (i = ts->cnt; i; ) {
		if (ts->stack[--i].ret_addr == ret_addr) {
			ts->cnt = i;
			return;
		}
	}
}

static void thread_stack__pop_trace_end(struct thread_stack *ts)
{
	size_t i;

	for (i = ts->cnt; i; ) {
		if (ts->stack[--i].trace_end)
			ts->cnt = i;
		else
			return;
	}
}

static bool thread_stack__in_kernel(struct thread_stack *ts)
{
	if (!ts->cnt)
		return false;

	return ts->stack[ts->cnt - 1].cp->in_kernel;
}

static int thread_stack__call_return(struct thread *thread,
				     struct thread_stack *ts, size_t idx,
				     u64 timestamp, u64 ref, bool no_return)
{
	struct call_return_processor *crp = ts->crp;
	struct thread_stack_entry *tse;
	struct call_return cr = {
		.thread = thread,
		.comm = ts->comm,
		.db_id = 0,
	};

	tse = &ts->stack[idx];
	cr.cp = tse->cp;
	cr.call_time = tse->timestamp;
	cr.return_time = timestamp;
	cr.branch_count = ts->branch_count - tse->branch_count;
	cr.call_ref = tse->ref;
	cr.return_ref = ref;
	if (tse->no_call)
		cr.flags |= CALL_RETURN_NO_CALL;
	if (no_return)
		cr.flags |= CALL_RETURN_NO_RETURN;

	return crp->process(&cr, crp->data);
}

static int __thread_stack__flush(struct thread *thread, struct thread_stack *ts)
{
	struct call_return_processor *crp = ts->crp;
	int err;

	if (!crp) {
		ts->cnt = 0;
		return 0;
	}

	while (ts->cnt) {
		err = thread_stack__call_return(thread, ts, --ts->cnt,
						ts->last_time, 0, true);
		if (err) {
			pr_err("Error flushing thread stack!\n");
			ts->cnt = 0;
			return err;
		}
	}

	return 0;
}

int thread_stack__flush(struct thread *thread)
{
	if (thread->ts)
		return __thread_stack__flush(thread, thread->ts);

	return 0;
}

int thread_stack__event(struct thread *thread, u32 flags, u64 from_ip,
			u64 to_ip, u16 insn_len, u64 trace_nr)
{
	if (!thread)
		return -EINVAL;

	if (!thread->ts) {
		thread->ts = thread_stack__new(thread, NULL);
		if (!thread->ts) {
			pr_warning("Out of memory: no thread stack\n");
			return -ENOMEM;
		}
		thread->ts->trace_nr = trace_nr;
	}

	/*
	 * When the trace is discontinuous, the trace_nr changes.  In that case
	 * the stack might be completely invalid.  Better to report nothing than
	 * to report something misleading, so flush the stack.
	 */
	if (trace_nr != thread->ts->trace_nr) {
		if (thread->ts->trace_nr)
			__thread_stack__flush(thread, thread->ts);
		thread->ts->trace_nr = trace_nr;
	}

	/* Stop here if thread_stack__process() is in use */
	if (thread->ts->crp)
		return 0;

	if (flags & PERF_IP_FLAG_CALL) {
		u64 ret_addr;

		if (!to_ip)
			return 0;
		ret_addr = from_ip + insn_len;
		if (ret_addr == to_ip)
			return 0; /* Zero-length calls are excluded */
		return thread_stack__push(thread->ts, ret_addr,
					  flags & PERF_IP_FLAG_TRACE_END);
	} else if (flags & PERF_IP_FLAG_TRACE_BEGIN) {
		/*
		 * If the caller did not change the trace number (which would
		 * have flushed the stack) then try to make sense of the stack.
		 * Possibly, tracing began after returning to the current
		 * address, so try to pop that. Also, do not expect a call made
		 * when the trace ended, to return, so pop that.
		 */
		thread_stack__pop(thread->ts, to_ip);
		thread_stack__pop_trace_end(thread->ts);
	} else if ((flags & PERF_IP_FLAG_RETURN) && from_ip) {
		thread_stack__pop(thread->ts, to_ip);
	}

	return 0;
}

void thread_stack__set_trace_nr(struct thread *thread, u64 trace_nr)
{
	if (!thread || !thread->ts)
		return;

	if (trace_nr != thread->ts->trace_nr) {
		if (thread->ts->trace_nr)
			__thread_stack__flush(thread, thread->ts);
		thread->ts->trace_nr = trace_nr;
	}
}

void thread_stack__free(struct thread *thread)
{
	if (thread->ts) {
		__thread_stack__flush(thread, thread->ts);
		zfree(&thread->ts->stack);
		zfree(&thread->ts);
	}
}

static inline u64 callchain_context(u64 ip, u64 kernel_start)
{
	return ip < kernel_start ? PERF_CONTEXT_USER : PERF_CONTEXT_KERNEL;
}

void thread_stack__sample(struct thread *thread, struct ip_callchain *chain,
			  size_t sz, u64 ip, u64 kernel_start)
{
	u64 context = callchain_context(ip, kernel_start);
	u64 last_context;
	size_t i, j;

	if (sz < 2) {
		chain->nr = 0;
		return;
	}

	chain->ips[0] = context;
	chain->ips[1] = ip;

	if (!thread || !thread->ts) {
		chain->nr = 2;
		return;
	}

	last_context = context;

	for (i = 2, j = 1; i < sz && j <= thread->ts->cnt; i++, j++) {
		ip = thread->ts->stack[thread->ts->cnt - j].ret_addr;
		context = callchain_context(ip, kernel_start);
		if (context != last_context) {
			if (i >= sz - 1)
				break;
			chain->ips[i++] = context;
			last_context = context;
		}
		chain->ips[i] = ip;
	}

	chain->nr = i;
}

struct call_return_processor *
call_return_processor__new(int (*process)(struct call_return *cr, void *data),
			   void *data)
{
	struct call_return_processor *crp;

	crp = zalloc(sizeof(struct call_return_processor));
	if (!crp)
		return NULL;
	crp->cpr = call_path_root__new();
	if (!crp->cpr)
		goto out_free;
	crp->process = process;
	crp->data = data;
	return crp;

out_free:
	free(crp);
	return NULL;
}

void call_return_processor__free(struct call_return_processor *crp)
{
	if (crp) {
		call_path_root__free(crp->cpr);
		free(crp);
	}
}

static int thread_stack__push_cp(struct thread_stack *ts, u64 ret_addr,
				 u64 timestamp, u64 ref, struct call_path *cp,
				 bool no_call, bool trace_end)
{
	struct thread_stack_entry *tse;
	int err;

	if (ts->cnt == ts->sz) {
		err = thread_stack__grow(ts);
		if (err)
			return err;
	}

	tse = &ts->stack[ts->cnt++];
	tse->ret_addr = ret_addr;
	tse->timestamp = timestamp;
	tse->ref = ref;
	tse->branch_count = ts->branch_count;
	tse->cp = cp;
	tse->no_call = no_call;
	tse->trace_end = trace_end;

	return 0;
}

static int thread_stack__pop_cp(struct thread *thread, struct thread_stack *ts,
				u64 ret_addr, u64 timestamp, u64 ref,
				struct symbol *sym)
{
	int err;

	if (!ts->cnt)
		return 1;

	if (ts->cnt == 1) {
		struct thread_stack_entry *tse = &ts->stack[0];

		if (tse->cp->sym == sym)
			return thread_stack__call_return(thread, ts, --ts->cnt,
							 timestamp, ref, false);
	}

	if (ts->stack[ts->cnt - 1].ret_addr == ret_addr) {
		return thread_stack__call_return(thread, ts, --ts->cnt,
						 timestamp, ref, false);
	} else {
		size_t i = ts->cnt - 1;

		while (i--) {
			if (ts->stack[i].ret_addr != ret_addr)
				continue;
			i += 1;
			while (ts->cnt > i) {
				err = thread_stack__call_return(thread, ts,
								--ts->cnt,
								timestamp, ref,
								true);
				if (err)
					return err;
			}
			return thread_stack__call_return(thread, ts, --ts->cnt,
							 timestamp, ref, false);
		}
	}

	return 1;
}

static int thread_stack__bottom(struct thread *thread, struct thread_stack *ts,
				struct perf_sample *sample,
				struct addr_location *from_al,
				struct addr_location *to_al, u64 ref)
{
	struct call_path_root *cpr = ts->crp->cpr;
	struct call_path *cp;
	struct symbol *sym;
	u64 ip;

	if (sample->ip) {
		ip = sample->ip;
		sym = from_al->sym;
	} else if (sample->addr) {
		ip = sample->addr;
		sym = to_al->sym;
	} else {
		return 0;
	}

	cp = call_path__findnew(cpr, &cpr->call_path, sym, ip,
				ts->kernel_start);
	if (!cp)
		return -ENOMEM;

	return thread_stack__push_cp(thread->ts, ip, sample->time, ref, cp,
				     true, false);
}

static int thread_stack__no_call_return(struct thread *thread,
					struct thread_stack *ts,
					struct perf_sample *sample,
					struct addr_location *from_al,
					struct addr_location *to_al, u64 ref)
{
	struct call_path_root *cpr = ts->crp->cpr;
	struct call_path *cp, *parent;
	u64 ks = ts->kernel_start;
	int err;

	if (sample->ip >= ks && sample->addr < ks) {
		/* Return to userspace, so pop all kernel addresses */
		while (thread_stack__in_kernel(ts)) {
			err = thread_stack__call_return(thread, ts, --ts->cnt,
							sample->time, ref,
							true);
			if (err)
				return err;
		}

		/* If the stack is empty, push the userspace address */
		if (!ts->cnt) {
			cp = call_path__findnew(cpr, &cpr->call_path,
						to_al->sym, sample->addr,
						ts->kernel_start);
			if (!cp)
				return -ENOMEM;
			return thread_stack__push_cp(ts, 0, sample->time, ref,
						     cp, true, false);
		}
	} else if (thread_stack__in_kernel(ts) && sample->ip < ks) {
		/* Return to userspace, so pop all kernel addresses */
		while (thread_stack__in_kernel(ts)) {
			err = thread_stack__call_return(thread, ts, --ts->cnt,
							sample->time, ref,
							true);
			if (err)
				return err;
		}
	}

	if (ts->cnt)
		parent = ts->stack[ts->cnt - 1].cp;
	else
		parent = &cpr->call_path;

	/* This 'return' had no 'call', so push and pop top of stack */
	cp = call_path__findnew(cpr, parent, from_al->sym, sample->ip,
				ts->kernel_start);
	if (!cp)
		return -ENOMEM;

	err = thread_stack__push_cp(ts, sample->addr, sample->time, ref, cp,
				    true, false);
	if (err)
		return err;

	return thread_stack__pop_cp(thread, ts, sample->addr, sample->time, ref,
				    to_al->sym);
}

static int thread_stack__trace_begin(struct thread *thread,
				     struct thread_stack *ts, u64 timestamp,
				     u64 ref)
{
	struct thread_stack_entry *tse;
	int err;

	if (!ts->cnt)
		return 0;

	/* Pop trace end */
	tse = &ts->stack[ts->cnt - 1];
	if (tse->trace_end) {
		err = thread_stack__call_return(thread, ts, --ts->cnt,
						timestamp, ref, false);
		if (err)
			return err;
	}

	return 0;
}

static int thread_stack__trace_end(struct thread_stack *ts,
				   struct perf_sample *sample, u64 ref)
{
	struct call_path_root *cpr = ts->crp->cpr;
	struct call_path *cp;
	u64 ret_addr;

	/* No point having 'trace end' on the bottom of the stack */
	if (!ts->cnt || (ts->cnt == 1 && ts->stack[0].ref == ref))
		return 0;

	cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, NULL, 0,
				ts->kernel_start);
	if (!cp)
		return -ENOMEM;

	ret_addr = sample->ip + sample->insn_len;

	return thread_stack__push_cp(ts, ret_addr, sample->time, ref, cp,
				     false, true);
}

int thread_stack__process(struct thread *thread, struct comm *comm,
			  struct perf_sample *sample,
			  struct addr_location *from_al,
			  struct addr_location *to_al, u64 ref,
			  struct call_return_processor *crp)
{
	struct thread_stack *ts = thread->ts;
	int err = 0;

	if (ts) {
		if (!ts->crp) {
			/* Supersede thread_stack__event() */
			thread_stack__free(thread);
			thread->ts = thread_stack__new(thread, crp);
			if (!thread->ts)
				return -ENOMEM;
			ts = thread->ts;
			ts->comm = comm;
		}
	} else {
		thread->ts = thread_stack__new(thread, crp);
		if (!thread->ts)
			return -ENOMEM;
		ts = thread->ts;
		ts->comm = comm;
	}

	/* Flush stack on exec */
	if (ts->comm != comm && thread->pid_ == thread->tid) {
		err = __thread_stack__flush(thread, ts);
		if (err)
			return err;
		ts->comm = comm;
	}

	/* If the stack is empty, put the current symbol on the stack */
	if (!ts->cnt) {
		err = thread_stack__bottom(thread, ts, sample, from_al, to_al,
					   ref);
		if (err)
			return err;
	}

	ts->branch_count += 1;
	ts->last_time = sample->time;

	if (sample->flags & PERF_IP_FLAG_CALL) {
		bool trace_end = sample->flags & PERF_IP_FLAG_TRACE_END;
		struct call_path_root *cpr = ts->crp->cpr;
		struct call_path *cp;
		u64 ret_addr;

		if (!sample->ip || !sample->addr)
			return 0;

		ret_addr = sample->ip + sample->insn_len;
		if (ret_addr == sample->addr)
			return 0; /* Zero-length calls are excluded */

		cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp,
					to_al->sym, sample->addr,
					ts->kernel_start);
		if (!cp)
			return -ENOMEM;
		err = thread_stack__push_cp(ts, ret_addr, sample->time, ref,
					    cp, false, trace_end);
	} else if (sample->flags & PERF_IP_FLAG_RETURN) {
		if (!sample->ip || !sample->addr)
			return 0;

		err = thread_stack__pop_cp(thread, ts, sample->addr,
					   sample->time, ref, from_al->sym);
		if (err) {
			if (err < 0)
				return err;
			err = thread_stack__no_call_return(thread, ts, sample,
							   from_al, to_al, ref);
		}
	} else if (sample->flags & PERF_IP_FLAG_TRACE_BEGIN) {
		err = thread_stack__trace_begin(thread, ts, sample->time, ref);
	} else if (sample->flags & PERF_IP_FLAG_TRACE_END) {
		err = thread_stack__trace_end(ts, sample, ref);
	}

	return err;
}

size_t thread_stack__depth(struct thread *thread)
{
	if (!thread->ts)
		return 0;
	return thread->ts->cnt;
}
Commit	Line	Data
00447ccd AH	1	/*
	2	* thread-stack.c: Synthesize a thread's stack using call / return events
	3	* Copyright (c) 2014, Intel Corporation.
	4	*
	5	* This program is free software; you can redistribute it and/or modify it
	6	* under the terms and conditions of the GNU General Public License,
	7	* version 2, as published by the Free Software Foundation.
	8	*
	9	* This program is distributed in the hope it will be useful, but WITHOUT
	10	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	11	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
	12	* more details.
	13	*
	14	*/
	15
92a9e4f7 AH	16	#include <linux/rbtree.h>
92a9e4f7 AH	17	#include <linux/list.h>
a43783ae	18	#include <errno.h>
00447ccd AH	19	#include "thread.h"
00447ccd AH	20	#include "event.h"
92a9e4f7	21	#include "machine.h"
00447ccd AH	22	#include "util.h"
00447ccd AH	23	#include "debug.h"
92a9e4f7 AH	24	#include "symbol.h"
92a9e4f7 AH	25	#include "comm.h"
451db126	26	#include "call-path.h"
00447ccd AH	27	#include "thread-stack.h"
00447ccd AH	28
92a9e4f7 AH	29	#define STACK_GROWTH 2048
	30
	31	/**
	32	* struct thread_stack_entry - thread stack entry.
	33	* @ret_addr: return address
	34	* @timestamp: timestamp (if known)
	35	* @ref: external reference (e.g. db_id of sample)
	36	* @branch_count: the branch count when the entry was created
	37	* @cp: call path
	38	* @no_call: a 'call' was not seen
4d60e5e3	39	* @trace_end: a 'call' but trace ended
92a9e4f7	40	*/
00447ccd AH	41	struct thread_stack_entry {
00447ccd AH	42	u64 ret_addr;
92a9e4f7 AH	43	u64 timestamp;
	44	u64 ref;
	45	u64 branch_count;
	46	struct call_path *cp;
	47	bool no_call;
4d60e5e3	48	bool trace_end;
00447ccd AH	49	};
00447ccd AH	50
92a9e4f7 AH	51	/**
	52	* struct thread_stack - thread stack constructed from 'call' and 'return'
	53	* branch samples.
	54	* @stack: array that holds the stack
	55	* @cnt: number of entries in the stack
	56	* @sz: current maximum stack size
	57	* @trace_nr: current trace number
	58	* @branch_count: running branch count
	59	* @kernel_start: kernel start address
	60	* @last_time: last timestamp
	61	* @crp: call/return processor
	62	* @comm: current comm
	63	*/
00447ccd AH	64	struct thread_stack {
	65	struct thread_stack_entry *stack;
	66	size_t cnt;
	67	size_t sz;
	68	u64 trace_nr;
92a9e4f7 AH	69	u64 branch_count;
	70	u64 kernel_start;
	71	u64 last_time;
	72	struct call_return_processor *crp;
	73	struct comm *comm;
00447ccd AH	74	};
	75
	76	static int thread_stack__grow(struct thread_stack *ts)
	77	{
	78	struct thread_stack_entry *new_stack;
	79	size_t sz, new_sz;
	80
	81	new_sz = ts->sz + STACK_GROWTH;
	82	sz = new_sz * sizeof(struct thread_stack_entry);
	83
	84	new_stack = realloc(ts->stack, sz);
	85	if (!new_stack)
	86	return -ENOMEM;
	87
	88	ts->stack = new_stack;
	89	ts->sz = new_sz;
	90
	91	return 0;
	92	}
	93
92a9e4f7 AH	94	static struct thread_stack thread_stack__new(struct thread thread,
92a9e4f7 AH	95	struct call_return_processor *crp)
00447ccd AH	96	{
	97	struct thread_stack *ts;
	98
	99	ts = zalloc(sizeof(struct thread_stack));
	100	if (!ts)
	101	return NULL;
	102
	103	if (thread_stack__grow(ts)) {
	104	free(ts);
	105	return NULL;
	106	}
	107
92a9e4f7 AH	108	if (thread->mg && thread->mg->machine)
	109	ts->kernel_start = machine__kernel_start(thread->mg->machine);
	110	else
	111	ts->kernel_start = 1ULL << 63;
	112	ts->crp = crp;
	113
00447ccd AH	114	return ts;
	115	}
	116
4d60e5e3 AH	117	static int thread_stack__push(struct thread_stack *ts, u64 ret_addr,
4d60e5e3 AH	118	bool trace_end)
00447ccd AH	119	{
	120	int err = 0;
	121
	122	if (ts->cnt == ts->sz) {
	123	err = thread_stack__grow(ts);
	124	if (err) {
	125	pr_warning("Out of memory: discarding thread stack\n");
	126	ts->cnt = 0;
	127	}
	128	}
	129
4d60e5e3	130	ts->stack[ts->cnt].trace_end = trace_end;
00447ccd AH	131	ts->stack[ts->cnt++].ret_addr = ret_addr;
	132
	133	return err;
	134	}
	135
	136	static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr)
	137	{
	138	size_t i;
	139
	140	/*
	141	* In some cases there may be functions which are not seen to return.
	142	* For example when setjmp / longjmp has been used. Or the perf context
	143	* switch in the kernel which doesn't stop and start tracing in exactly
	144	* the same code path. When that happens the return address will be
	145	* further down the stack. If the return address is not found at all,
	146	* we assume the opposite (i.e. this is a return for a call that wasn't
	147	* seen for some reason) and leave the stack alone.
	148	*/
	149	for (i = ts->cnt; i; ) {
	150	if (ts->stack[--i].ret_addr == ret_addr) {
	151	ts->cnt = i;
	152	return;
	153	}
	154	}
	155	}
	156
4d60e5e3 AH	157	static void thread_stack__pop_trace_end(struct thread_stack *ts)
	158	{
	159	size_t i;
	160
	161	for (i = ts->cnt; i; ) {
	162	if (ts->stack[--i].trace_end)
	163	ts->cnt = i;
	164	else
	165	return;
	166	}
	167	}
	168
92a9e4f7 AH	169	static bool thread_stack__in_kernel(struct thread_stack *ts)
	170	{
	171	if (!ts->cnt)
	172	return false;
	173
	174	return ts->stack[ts->cnt - 1].cp->in_kernel;
	175	}
	176
	177	static int thread_stack__call_return(struct thread *thread,
	178	struct thread_stack *ts, size_t idx,
	179	u64 timestamp, u64 ref, bool no_return)
	180	{
	181	struct call_return_processor *crp = ts->crp;
	182	struct thread_stack_entry *tse;
	183	struct call_return cr = {
	184	.thread = thread,
	185	.comm = ts->comm,
	186	.db_id = 0,
	187	};
	188
	189	tse = &ts->stack[idx];
	190	cr.cp = tse->cp;
	191	cr.call_time = tse->timestamp;
	192	cr.return_time = timestamp;
	193	cr.branch_count = ts->branch_count - tse->branch_count;
	194	cr.call_ref = tse->ref;
	195	cr.return_ref = ref;
	196	if (tse->no_call)
	197	cr.flags \|= CALL_RETURN_NO_CALL;
	198	if (no_return)
	199	cr.flags \|= CALL_RETURN_NO_RETURN;
	200
	201	return crp->process(&cr, crp->data);
	202	}
	203
a5499b37	204	static int __thread_stack__flush(struct thread thread, struct thread_stack ts)
92a9e4f7 AH	205	{
	206	struct call_return_processor *crp = ts->crp;
	207	int err;
	208
	209	if (!crp) {
	210	ts->cnt = 0;
	211	return 0;
	212	}
	213
	214	while (ts->cnt) {
	215	err = thread_stack__call_return(thread, ts, --ts->cnt,
	216	ts->last_time, 0, true);
	217	if (err) {
	218	pr_err("Error flushing thread stack!\n");
	219	ts->cnt = 0;
	220	return err;
	221	}
	222	}
	223
	224	return 0;
	225	}
	226
a5499b37 AH	227	int thread_stack__flush(struct thread *thread)
	228	{
	229	if (thread->ts)
	230	return __thread_stack__flush(thread, thread->ts);
	231
	232	return 0;
	233	}
	234
00447ccd AH	235	int thread_stack__event(struct thread *thread, u32 flags, u64 from_ip,
	236	u64 to_ip, u16 insn_len, u64 trace_nr)
	237	{
	238	if (!thread)
	239	return -EINVAL;
	240
	241	if (!thread->ts) {
92a9e4f7	242	thread->ts = thread_stack__new(thread, NULL);
00447ccd AH	243	if (!thread->ts) {
	244	pr_warning("Out of memory: no thread stack\n");
	245	return -ENOMEM;
	246	}
	247	thread->ts->trace_nr = trace_nr;
	248	}
	249
	250	/*
	251	* When the trace is discontinuous, the trace_nr changes. In that case
	252	* the stack might be completely invalid. Better to report nothing than
92a9e4f7	253	* to report something misleading, so flush the stack.
00447ccd AH	254	*/
00447ccd AH	255	if (trace_nr != thread->ts->trace_nr) {
92a9e4f7	256	if (thread->ts->trace_nr)
a5499b37	257	__thread_stack__flush(thread, thread->ts);
00447ccd	258	thread->ts->trace_nr = trace_nr;
00447ccd AH	259	}
00447ccd AH	260
92a9e4f7 AH	261	/* Stop here if thread_stack__process() is in use */
	262	if (thread->ts->crp)
	263	return 0;
	264
00447ccd AH	265	if (flags & PERF_IP_FLAG_CALL) {
	266	u64 ret_addr;
	267
	268	if (!to_ip)
	269	return 0;
	270	ret_addr = from_ip + insn_len;
	271	if (ret_addr == to_ip)
	272	return 0; /* Zero-length calls are excluded */
4d60e5e3 AH	273	return thread_stack__push(thread->ts, ret_addr,
	274	flags & PERF_IP_FLAG_TRACE_END);
	275	} else if (flags & PERF_IP_FLAG_TRACE_BEGIN) {
	276	/*
	277	* If the caller did not change the trace number (which would
	278	* have flushed the stack) then try to make sense of the stack.
	279	* Possibly, tracing began after returning to the current
	280	* address, so try to pop that. Also, do not expect a call made
	281	* when the trace ended, to return, so pop that.
	282	*/
	283	thread_stack__pop(thread->ts, to_ip);
	284	thread_stack__pop_trace_end(thread->ts);
	285	} else if ((flags & PERF_IP_FLAG_RETURN) && from_ip) {
00447ccd AH	286	thread_stack__pop(thread->ts, to_ip);
	287	}
	288
	289	return 0;
	290	}
	291
92a9e4f7 AH	292	void thread_stack__set_trace_nr(struct thread *thread, u64 trace_nr)
	293	{
	294	if (!thread \|\| !thread->ts)
	295	return;
	296
	297	if (trace_nr != thread->ts->trace_nr) {
	298	if (thread->ts->trace_nr)
a5499b37	299	__thread_stack__flush(thread, thread->ts);
92a9e4f7 AH	300	thread->ts->trace_nr = trace_nr;
	301	}
	302	}
	303
00447ccd AH	304	void thread_stack__free(struct thread *thread)
	305	{
	306	if (thread->ts) {
a5499b37	307	__thread_stack__flush(thread, thread->ts);
00447ccd AH	308	zfree(&thread->ts->stack);
	309	zfree(&thread->ts);
	310	}
	311	}
	312
24248306 AH	313	static inline u64 callchain_context(u64 ip, u64 kernel_start)
	314	{
	315	return ip < kernel_start ? PERF_CONTEXT_USER : PERF_CONTEXT_KERNEL;
	316	}
	317
00447ccd	318	void thread_stack__sample(struct thread thread, struct ip_callchain chain,
24248306	319	size_t sz, u64 ip, u64 kernel_start)
00447ccd	320	{
24248306 AH	321	u64 context = callchain_context(ip, kernel_start);
	322	u64 last_context;
	323	size_t i, j;
00447ccd	324
24248306 AH	325	if (sz < 2) {
	326	chain->nr = 0;
	327	return;
	328	}
00447ccd	329
24248306 AH	330	chain->ips[0] = context;
	331	chain->ips[1] = ip;
	332
	333	if (!thread \|\| !thread->ts) {
	334	chain->nr = 2;
	335	return;
	336	}
	337
	338	last_context = context;
	339
	340	for (i = 2, j = 1; i < sz && j <= thread->ts->cnt; i++, j++) {
	341	ip = thread->ts->stack[thread->ts->cnt - j].ret_addr;
	342	context = callchain_context(ip, kernel_start);
	343	if (context != last_context) {
	344	if (i >= sz - 1)
	345	break;
	346	chain->ips[i++] = context;
	347	last_context = context;
	348	}
	349	chain->ips[i] = ip;
	350	}
00447ccd	351
24248306	352	chain->nr = i;
00447ccd	353	}
92a9e4f7	354
92a9e4f7 AH	355	struct call_return_processor *
	356	call_return_processor__new(int (process)(struct call_return cr, void *data),
	357	void *data)
	358	{
	359	struct call_return_processor *crp;
	360
	361	crp = zalloc(sizeof(struct call_return_processor));
	362	if (!crp)
	363	return NULL;
	364	crp->cpr = call_path_root__new();
	365	if (!crp->cpr)
	366	goto out_free;
	367	crp->process = process;
	368	crp->data = data;
	369	return crp;
	370
	371	out_free:
	372	free(crp);
	373	return NULL;
	374	}
	375
	376	void call_return_processor__free(struct call_return_processor *crp)
	377	{
	378	if (crp) {
	379	call_path_root__free(crp->cpr);
	380	free(crp);
	381	}
	382	}
	383
	384	static int thread_stack__push_cp(struct thread_stack *ts, u64 ret_addr,
	385	u64 timestamp, u64 ref, struct call_path *cp,
2dcde4e1	386	bool no_call, bool trace_end)
92a9e4f7 AH	387	{
	388	struct thread_stack_entry *tse;
	389	int err;
	390
	391	if (ts->cnt == ts->sz) {
	392	err = thread_stack__grow(ts);
	393	if (err)
	394	return err;
	395	}
	396
	397	tse = &ts->stack[ts->cnt++];
	398	tse->ret_addr = ret_addr;
	399	tse->timestamp = timestamp;
	400	tse->ref = ref;
	401	tse->branch_count = ts->branch_count;
	402	tse->cp = cp;
	403	tse->no_call = no_call;
2dcde4e1	404	tse->trace_end = trace_end;
92a9e4f7 AH	405
	406	return 0;
	407	}
	408
	409	static int thread_stack__pop_cp(struct thread thread, struct thread_stack ts,
	410	u64 ret_addr, u64 timestamp, u64 ref,
	411	struct symbol *sym)
	412	{
	413	int err;
	414
	415	if (!ts->cnt)
	416	return 1;
	417
	418	if (ts->cnt == 1) {
	419	struct thread_stack_entry *tse = &ts->stack[0];
	420
	421	if (tse->cp->sym == sym)
	422	return thread_stack__call_return(thread, ts, --ts->cnt,
	423	timestamp, ref, false);
	424	}
	425
	426	if (ts->stack[ts->cnt - 1].ret_addr == ret_addr) {
	427	return thread_stack__call_return(thread, ts, --ts->cnt,
	428	timestamp, ref, false);
	429	} else {
	430	size_t i = ts->cnt - 1;
	431
	432	while (i--) {
	433	if (ts->stack[i].ret_addr != ret_addr)
	434	continue;
	435	i += 1;
	436	while (ts->cnt > i) {
	437	err = thread_stack__call_return(thread, ts,
	438	--ts->cnt,
	439	timestamp, ref,
	440	true);
	441	if (err)
	442	return err;
	443	}
	444	return thread_stack__call_return(thread, ts, --ts->cnt,
	445	timestamp, ref, false);
	446	}
	447	}
	448
	449	return 1;
	450	}
	451
	452	static int thread_stack__bottom(struct thread thread, struct thread_stack ts,
	453	struct perf_sample *sample,
	454	struct addr_location *from_al,
	455	struct addr_location *to_al, u64 ref)
	456	{
	457	struct call_path_root *cpr = ts->crp->cpr;
	458	struct call_path *cp;
	459	struct symbol *sym;
	460	u64 ip;
	461
	462	if (sample->ip) {
	463	ip = sample->ip;
	464	sym = from_al->sym;
	465	} else if (sample->addr) {
	466	ip = sample->addr;
	467	sym = to_al->sym;
	468	} else {
469	return 0;
470	}
471
472	cp = call_path__findnew(cpr, &cpr->call_path, sym, ip,
473	ts->kernel_start);
474	if (!cp)
475	return -ENOMEM;
476
477	return thread_stack__push_cp(thread->ts, ip, sample->time, ref, cp,
2dcde4e1	478	true, false);
92a9e4f7 AH	479	}
	480
	481	static int thread_stack__no_call_return(struct thread *thread,
	482	struct thread_stack *ts,
	483	struct perf_sample *sample,
	484	struct addr_location *from_al,
	485	struct addr_location *to_al, u64 ref)
	486	{
	487	struct call_path_root *cpr = ts->crp->cpr;
	488	struct call_path cp, parent;
	489	u64 ks = ts->kernel_start;
	490	int err;
	491
	492	if (sample->ip >= ks && sample->addr < ks) {
	493	/* Return to userspace, so pop all kernel addresses */
	494	while (thread_stack__in_kernel(ts)) {
	495	err = thread_stack__call_return(thread, ts, --ts->cnt,
	496	sample->time, ref,
	497	true);
	498	if (err)
	499	return err;
	500	}
	501
	502	/* If the stack is empty, push the userspace address */
	503	if (!ts->cnt) {
	504	cp = call_path__findnew(cpr, &cpr->call_path,
	505	to_al->sym, sample->addr,
	506	ts->kernel_start);
	507	if (!cp)
	508	return -ENOMEM;
	509	return thread_stack__push_cp(ts, 0, sample->time, ref,
2dcde4e1	510	cp, true, false);
92a9e4f7 AH	511	}
	512	} else if (thread_stack__in_kernel(ts) && sample->ip < ks) {
	513	/* Return to userspace, so pop all kernel addresses */
	514	while (thread_stack__in_kernel(ts)) {
	515	err = thread_stack__call_return(thread, ts, --ts->cnt,
	516	sample->time, ref,
	517	true);
	518	if (err)
	519	return err;
	520	}
	521	}
	522
	523	if (ts->cnt)
	524	parent = ts->stack[ts->cnt - 1].cp;
	525	else
	526	parent = &cpr->call_path;
	527
	528	/* This 'return' had no 'call', so push and pop top of stack */
	529	cp = call_path__findnew(cpr, parent, from_al->sym, sample->ip,
	530	ts->kernel_start);
	531	if (!cp)
	532	return -ENOMEM;
	533
	534	err = thread_stack__push_cp(ts, sample->addr, sample->time, ref, cp,
2dcde4e1	535	true, false);
92a9e4f7 AH	536	if (err)
	537	return err;
	538
	539	return thread_stack__pop_cp(thread, ts, sample->addr, sample->time, ref,
	540	to_al->sym);
	541	}
	542
	543	static int thread_stack__trace_begin(struct thread *thread,
	544	struct thread_stack *ts, u64 timestamp,
	545	u64 ref)
	546	{
	547	struct thread_stack_entry *tse;
	548	int err;
	549
	550	if (!ts->cnt)
	551	return 0;
	552
	553	/* Pop trace end */
	554	tse = &ts->stack[ts->cnt - 1];
2dcde4e1	555	if (tse->trace_end) {
92a9e4f7 AH	556	err = thread_stack__call_return(thread, ts, --ts->cnt,
	557	timestamp, ref, false);
	558	if (err)
	559	return err;
	560	}
	561
	562	return 0;
	563	}
	564
	565	static int thread_stack__trace_end(struct thread_stack *ts,
	566	struct perf_sample *sample, u64 ref)
	567	{
	568	struct call_path_root *cpr = ts->crp->cpr;
	569	struct call_path *cp;
	570	u64 ret_addr;
	571
	572	/* No point having 'trace end' on the bottom of the stack */
	573	if (!ts->cnt \|\| (ts->cnt == 1 && ts->stack[0].ref == ref))
	574	return 0;
	575
	576	cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, NULL, 0,
	577	ts->kernel_start);
	578	if (!cp)
	579	return -ENOMEM;
	580
	581	ret_addr = sample->ip + sample->insn_len;
	582
	583	return thread_stack__push_cp(ts, ret_addr, sample->time, ref, cp,
2dcde4e1	584	false, true);
92a9e4f7 AH	585	}
	586
	587	int thread_stack__process(struct thread thread, struct comm comm,
	588	struct perf_sample *sample,
	589	struct addr_location *from_al,
	590	struct addr_location *to_al, u64 ref,
	591	struct call_return_processor *crp)
	592	{
	593	struct thread_stack *ts = thread->ts;
	594	int err = 0;
	595
	596	if (ts) {
	597	if (!ts->crp) {
	598	/* Supersede thread_stack__event() */
	599	thread_stack__free(thread);
	600	thread->ts = thread_stack__new(thread, crp);
	601	if (!thread->ts)
	602	return -ENOMEM;
	603	ts = thread->ts;
	604	ts->comm = comm;
	605	}
	606	} else {
	607	thread->ts = thread_stack__new(thread, crp);
	608	if (!thread->ts)
	609	return -ENOMEM;
	610	ts = thread->ts;
	611	ts->comm = comm;
	612	}
	613
	614	/* Flush stack on exec */
	615	if (ts->comm != comm && thread->pid_ == thread->tid) {
a5499b37	616	err = __thread_stack__flush(thread, ts);
92a9e4f7 AH	617	if (err)
	618	return err;
	619	ts->comm = comm;
	620	}
	621
	622	/* If the stack is empty, put the current symbol on the stack */
	623	if (!ts->cnt) {
	624	err = thread_stack__bottom(thread, ts, sample, from_al, to_al,
	625	ref);
	626	if (err)
	627	return err;
	628	}
	629
	630	ts->branch_count += 1;
	631	ts->last_time = sample->time;
	632
	633	if (sample->flags & PERF_IP_FLAG_CALL) {
2dcde4e1	634	bool trace_end = sample->flags & PERF_IP_FLAG_TRACE_END;
92a9e4f7 AH	635	struct call_path_root *cpr = ts->crp->cpr;
	636	struct call_path *cp;
	637	u64 ret_addr;
	638
	639	if (!sample->ip \|\| !sample->addr)
	640	return 0;
	641
	642	ret_addr = sample->ip + sample->insn_len;
	643	if (ret_addr == sample->addr)
	644	return 0; /* Zero-length calls are excluded */
	645
	646	cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp,
	647	to_al->sym, sample->addr,
	648	ts->kernel_start);
	649	if (!cp)
	650	return -ENOMEM;
	651	err = thread_stack__push_cp(ts, ret_addr, sample->time, ref,
2dcde4e1	652	cp, false, trace_end);
92a9e4f7 AH	653	} else if (sample->flags & PERF_IP_FLAG_RETURN) {
	654	if (!sample->ip \|\| !sample->addr)
	655	return 0;
	656
	657	err = thread_stack__pop_cp(thread, ts, sample->addr,
	658	sample->time, ref, from_al->sym);
	659	if (err) {
	660	if (err < 0)
	661	return err;
	662	err = thread_stack__no_call_return(thread, ts, sample,
	663	from_al, to_al, ref);
	664	}
	665	} else if (sample->flags & PERF_IP_FLAG_TRACE_BEGIN) {
	666	err = thread_stack__trace_begin(thread, ts, sample->time, ref);
	667	} else if (sample->flags & PERF_IP_FLAG_TRACE_END) {
	668	err = thread_stack__trace_end(ts, sample, ref);
	669	}
	670
	671	return err;
	672	}
e216708d AH	673
	674	size_t thread_stack__depth(struct thread *thread)
	675	{
	676	if (!thread->ts)
	677	return 0;
	678	return thread->ts->cnt;
	679	}