100447ccdSAdrian Hunter /* 200447ccdSAdrian Hunter * thread-stack.c: Synthesize a thread's stack using call / return events 300447ccdSAdrian Hunter * Copyright (c) 2014, Intel Corporation. 400447ccdSAdrian Hunter * 500447ccdSAdrian Hunter * This program is free software; you can redistribute it and/or modify it 600447ccdSAdrian Hunter * under the terms and conditions of the GNU General Public License, 700447ccdSAdrian Hunter * version 2, as published by the Free Software Foundation. 800447ccdSAdrian Hunter * 900447ccdSAdrian Hunter * This program is distributed in the hope it will be useful, but WITHOUT 1000447ccdSAdrian Hunter * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1100447ccdSAdrian Hunter * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 1200447ccdSAdrian Hunter * more details. 1300447ccdSAdrian Hunter * 1400447ccdSAdrian Hunter */ 1500447ccdSAdrian Hunter 1692a9e4f7SAdrian Hunter #include <linux/rbtree.h> 1792a9e4f7SAdrian Hunter #include <linux/list.h> 18a43783aeSArnaldo Carvalho de Melo #include <errno.h> 1900447ccdSAdrian Hunter #include "thread.h" 2000447ccdSAdrian Hunter #include "event.h" 2192a9e4f7SAdrian Hunter #include "machine.h" 2200447ccdSAdrian Hunter #include "util.h" 2300447ccdSAdrian Hunter #include "debug.h" 2492a9e4f7SAdrian Hunter #include "symbol.h" 2592a9e4f7SAdrian Hunter #include "comm.h" 26451db126SChris Phlipot #include "call-path.h" 2700447ccdSAdrian Hunter #include "thread-stack.h" 2800447ccdSAdrian Hunter 2992a9e4f7SAdrian Hunter #define STACK_GROWTH 2048 3092a9e4f7SAdrian Hunter 3192a9e4f7SAdrian Hunter /** 3292a9e4f7SAdrian Hunter * struct thread_stack_entry - thread stack entry. 3392a9e4f7SAdrian Hunter * @ret_addr: return address 3492a9e4f7SAdrian Hunter * @timestamp: timestamp (if known) 3592a9e4f7SAdrian Hunter * @ref: external reference (e.g. db_id of sample) 3692a9e4f7SAdrian Hunter * @branch_count: the branch count when the entry was created 3792a9e4f7SAdrian Hunter * @cp: call path 3892a9e4f7SAdrian Hunter * @no_call: a 'call' was not seen 3992a9e4f7SAdrian Hunter */ 4092a9e4f7SAdrian Hunter struct thread_stack_entry { 4192a9e4f7SAdrian Hunter u64 ret_addr; 4292a9e4f7SAdrian Hunter u64 timestamp; 4392a9e4f7SAdrian Hunter u64 ref; 4492a9e4f7SAdrian Hunter u64 branch_count; 4592a9e4f7SAdrian Hunter struct call_path *cp; 4692a9e4f7SAdrian Hunter bool no_call; 4792a9e4f7SAdrian Hunter }; 4892a9e4f7SAdrian Hunter 4992a9e4f7SAdrian Hunter /** 5092a9e4f7SAdrian Hunter * struct thread_stack - thread stack constructed from 'call' and 'return' 5192a9e4f7SAdrian Hunter * branch samples. 5292a9e4f7SAdrian Hunter * @stack: array that holds the stack 5392a9e4f7SAdrian Hunter * @cnt: number of entries in the stack 5492a9e4f7SAdrian Hunter * @sz: current maximum stack size 5592a9e4f7SAdrian Hunter * @trace_nr: current trace number 5692a9e4f7SAdrian Hunter * @branch_count: running branch count 5792a9e4f7SAdrian Hunter * @kernel_start: kernel start address 5892a9e4f7SAdrian Hunter * @last_time: last timestamp 5992a9e4f7SAdrian Hunter * @crp: call/return processor 6092a9e4f7SAdrian Hunter * @comm: current comm 6192a9e4f7SAdrian Hunter */ 6200447ccdSAdrian Hunter struct thread_stack { 6300447ccdSAdrian Hunter struct thread_stack_entry *stack; 6400447ccdSAdrian Hunter size_t cnt; 6500447ccdSAdrian Hunter size_t sz; 6600447ccdSAdrian Hunter u64 trace_nr; 6792a9e4f7SAdrian Hunter u64 branch_count; 6892a9e4f7SAdrian Hunter u64 kernel_start; 6992a9e4f7SAdrian Hunter u64 last_time; 7092a9e4f7SAdrian Hunter struct call_return_processor *crp; 7192a9e4f7SAdrian Hunter struct comm *comm; 7200447ccdSAdrian Hunter }; 7300447ccdSAdrian Hunter 7400447ccdSAdrian Hunter static int thread_stack__grow(struct thread_stack *ts) 7500447ccdSAdrian Hunter { 7600447ccdSAdrian Hunter struct thread_stack_entry *new_stack; 7700447ccdSAdrian Hunter size_t sz, new_sz; 7800447ccdSAdrian Hunter 7900447ccdSAdrian Hunter new_sz = ts->sz + STACK_GROWTH; 8000447ccdSAdrian Hunter sz = new_sz * sizeof(struct thread_stack_entry); 8100447ccdSAdrian Hunter 8200447ccdSAdrian Hunter new_stack = realloc(ts->stack, sz); 8300447ccdSAdrian Hunter if (!new_stack) 8400447ccdSAdrian Hunter return -ENOMEM; 8500447ccdSAdrian Hunter 8600447ccdSAdrian Hunter ts->stack = new_stack; 8700447ccdSAdrian Hunter ts->sz = new_sz; 8800447ccdSAdrian Hunter 8900447ccdSAdrian Hunter return 0; 9000447ccdSAdrian Hunter } 9100447ccdSAdrian Hunter 9292a9e4f7SAdrian Hunter static struct thread_stack *thread_stack__new(struct thread *thread, 9392a9e4f7SAdrian Hunter struct call_return_processor *crp) 9400447ccdSAdrian Hunter { 9500447ccdSAdrian Hunter struct thread_stack *ts; 9600447ccdSAdrian Hunter 9700447ccdSAdrian Hunter ts = zalloc(sizeof(struct thread_stack)); 9800447ccdSAdrian Hunter if (!ts) 9900447ccdSAdrian Hunter return NULL; 10000447ccdSAdrian Hunter 10100447ccdSAdrian Hunter if (thread_stack__grow(ts)) { 10200447ccdSAdrian Hunter free(ts); 10300447ccdSAdrian Hunter return NULL; 10400447ccdSAdrian Hunter } 10500447ccdSAdrian Hunter 10692a9e4f7SAdrian Hunter if (thread->mg && thread->mg->machine) 10792a9e4f7SAdrian Hunter ts->kernel_start = machine__kernel_start(thread->mg->machine); 10892a9e4f7SAdrian Hunter else 10992a9e4f7SAdrian Hunter ts->kernel_start = 1ULL << 63; 11092a9e4f7SAdrian Hunter ts->crp = crp; 11192a9e4f7SAdrian Hunter 11200447ccdSAdrian Hunter return ts; 11300447ccdSAdrian Hunter } 11400447ccdSAdrian Hunter 11500447ccdSAdrian Hunter static int thread_stack__push(struct thread_stack *ts, u64 ret_addr) 11600447ccdSAdrian Hunter { 11700447ccdSAdrian Hunter int err = 0; 11800447ccdSAdrian Hunter 11900447ccdSAdrian Hunter if (ts->cnt == ts->sz) { 12000447ccdSAdrian Hunter err = thread_stack__grow(ts); 12100447ccdSAdrian Hunter if (err) { 12200447ccdSAdrian Hunter pr_warning("Out of memory: discarding thread stack\n"); 12300447ccdSAdrian Hunter ts->cnt = 0; 12400447ccdSAdrian Hunter } 12500447ccdSAdrian Hunter } 12600447ccdSAdrian Hunter 12700447ccdSAdrian Hunter ts->stack[ts->cnt++].ret_addr = ret_addr; 12800447ccdSAdrian Hunter 12900447ccdSAdrian Hunter return err; 13000447ccdSAdrian Hunter } 13100447ccdSAdrian Hunter 13200447ccdSAdrian Hunter static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr) 13300447ccdSAdrian Hunter { 13400447ccdSAdrian Hunter size_t i; 13500447ccdSAdrian Hunter 13600447ccdSAdrian Hunter /* 13700447ccdSAdrian Hunter * In some cases there may be functions which are not seen to return. 13800447ccdSAdrian Hunter * For example when setjmp / longjmp has been used. Or the perf context 13900447ccdSAdrian Hunter * switch in the kernel which doesn't stop and start tracing in exactly 14000447ccdSAdrian Hunter * the same code path. When that happens the return address will be 14100447ccdSAdrian Hunter * further down the stack. If the return address is not found at all, 14200447ccdSAdrian Hunter * we assume the opposite (i.e. this is a return for a call that wasn't 14300447ccdSAdrian Hunter * seen for some reason) and leave the stack alone. 14400447ccdSAdrian Hunter */ 14500447ccdSAdrian Hunter for (i = ts->cnt; i; ) { 14600447ccdSAdrian Hunter if (ts->stack[--i].ret_addr == ret_addr) { 14700447ccdSAdrian Hunter ts->cnt = i; 14800447ccdSAdrian Hunter return; 14900447ccdSAdrian Hunter } 15000447ccdSAdrian Hunter } 15100447ccdSAdrian Hunter } 15200447ccdSAdrian Hunter 15392a9e4f7SAdrian Hunter static bool thread_stack__in_kernel(struct thread_stack *ts) 15492a9e4f7SAdrian Hunter { 15592a9e4f7SAdrian Hunter if (!ts->cnt) 15692a9e4f7SAdrian Hunter return false; 15792a9e4f7SAdrian Hunter 15892a9e4f7SAdrian Hunter return ts->stack[ts->cnt - 1].cp->in_kernel; 15992a9e4f7SAdrian Hunter } 16092a9e4f7SAdrian Hunter 16192a9e4f7SAdrian Hunter static int thread_stack__call_return(struct thread *thread, 16292a9e4f7SAdrian Hunter struct thread_stack *ts, size_t idx, 16392a9e4f7SAdrian Hunter u64 timestamp, u64 ref, bool no_return) 16492a9e4f7SAdrian Hunter { 16592a9e4f7SAdrian Hunter struct call_return_processor *crp = ts->crp; 16692a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 16792a9e4f7SAdrian Hunter struct call_return cr = { 16892a9e4f7SAdrian Hunter .thread = thread, 16992a9e4f7SAdrian Hunter .comm = ts->comm, 17092a9e4f7SAdrian Hunter .db_id = 0, 17192a9e4f7SAdrian Hunter }; 17292a9e4f7SAdrian Hunter 17392a9e4f7SAdrian Hunter tse = &ts->stack[idx]; 17492a9e4f7SAdrian Hunter cr.cp = tse->cp; 17592a9e4f7SAdrian Hunter cr.call_time = tse->timestamp; 17692a9e4f7SAdrian Hunter cr.return_time = timestamp; 17792a9e4f7SAdrian Hunter cr.branch_count = ts->branch_count - tse->branch_count; 17892a9e4f7SAdrian Hunter cr.call_ref = tse->ref; 17992a9e4f7SAdrian Hunter cr.return_ref = ref; 18092a9e4f7SAdrian Hunter if (tse->no_call) 18192a9e4f7SAdrian Hunter cr.flags |= CALL_RETURN_NO_CALL; 18292a9e4f7SAdrian Hunter if (no_return) 18392a9e4f7SAdrian Hunter cr.flags |= CALL_RETURN_NO_RETURN; 18492a9e4f7SAdrian Hunter 18592a9e4f7SAdrian Hunter return crp->process(&cr, crp->data); 18692a9e4f7SAdrian Hunter } 18792a9e4f7SAdrian Hunter 188a5499b37SAdrian Hunter static int __thread_stack__flush(struct thread *thread, struct thread_stack *ts) 18992a9e4f7SAdrian Hunter { 19092a9e4f7SAdrian Hunter struct call_return_processor *crp = ts->crp; 19192a9e4f7SAdrian Hunter int err; 19292a9e4f7SAdrian Hunter 19392a9e4f7SAdrian Hunter if (!crp) { 19492a9e4f7SAdrian Hunter ts->cnt = 0; 19592a9e4f7SAdrian Hunter return 0; 19692a9e4f7SAdrian Hunter } 19792a9e4f7SAdrian Hunter 19892a9e4f7SAdrian Hunter while (ts->cnt) { 19992a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 20092a9e4f7SAdrian Hunter ts->last_time, 0, true); 20192a9e4f7SAdrian Hunter if (err) { 20292a9e4f7SAdrian Hunter pr_err("Error flushing thread stack!\n"); 20392a9e4f7SAdrian Hunter ts->cnt = 0; 20492a9e4f7SAdrian Hunter return err; 20592a9e4f7SAdrian Hunter } 20692a9e4f7SAdrian Hunter } 20792a9e4f7SAdrian Hunter 20892a9e4f7SAdrian Hunter return 0; 20992a9e4f7SAdrian Hunter } 21092a9e4f7SAdrian Hunter 211a5499b37SAdrian Hunter int thread_stack__flush(struct thread *thread) 212a5499b37SAdrian Hunter { 213a5499b37SAdrian Hunter if (thread->ts) 214a5499b37SAdrian Hunter return __thread_stack__flush(thread, thread->ts); 215a5499b37SAdrian Hunter 216a5499b37SAdrian Hunter return 0; 217a5499b37SAdrian Hunter } 218a5499b37SAdrian Hunter 21900447ccdSAdrian Hunter int thread_stack__event(struct thread *thread, u32 flags, u64 from_ip, 22000447ccdSAdrian Hunter u64 to_ip, u16 insn_len, u64 trace_nr) 22100447ccdSAdrian Hunter { 22200447ccdSAdrian Hunter if (!thread) 22300447ccdSAdrian Hunter return -EINVAL; 22400447ccdSAdrian Hunter 22500447ccdSAdrian Hunter if (!thread->ts) { 22692a9e4f7SAdrian Hunter thread->ts = thread_stack__new(thread, NULL); 22700447ccdSAdrian Hunter if (!thread->ts) { 22800447ccdSAdrian Hunter pr_warning("Out of memory: no thread stack\n"); 22900447ccdSAdrian Hunter return -ENOMEM; 23000447ccdSAdrian Hunter } 23100447ccdSAdrian Hunter thread->ts->trace_nr = trace_nr; 23200447ccdSAdrian Hunter } 23300447ccdSAdrian Hunter 23400447ccdSAdrian Hunter /* 23500447ccdSAdrian Hunter * When the trace is discontinuous, the trace_nr changes. In that case 23600447ccdSAdrian Hunter * the stack might be completely invalid. Better to report nothing than 23792a9e4f7SAdrian Hunter * to report something misleading, so flush the stack. 23800447ccdSAdrian Hunter */ 23900447ccdSAdrian Hunter if (trace_nr != thread->ts->trace_nr) { 24092a9e4f7SAdrian Hunter if (thread->ts->trace_nr) 241a5499b37SAdrian Hunter __thread_stack__flush(thread, thread->ts); 24200447ccdSAdrian Hunter thread->ts->trace_nr = trace_nr; 24300447ccdSAdrian Hunter } 24400447ccdSAdrian Hunter 24592a9e4f7SAdrian Hunter /* Stop here if thread_stack__process() is in use */ 24692a9e4f7SAdrian Hunter if (thread->ts->crp) 24792a9e4f7SAdrian Hunter return 0; 24892a9e4f7SAdrian Hunter 24900447ccdSAdrian Hunter if (flags & PERF_IP_FLAG_CALL) { 25000447ccdSAdrian Hunter u64 ret_addr; 25100447ccdSAdrian Hunter 25200447ccdSAdrian Hunter if (!to_ip) 25300447ccdSAdrian Hunter return 0; 25400447ccdSAdrian Hunter ret_addr = from_ip + insn_len; 25500447ccdSAdrian Hunter if (ret_addr == to_ip) 25600447ccdSAdrian Hunter return 0; /* Zero-length calls are excluded */ 25700447ccdSAdrian Hunter return thread_stack__push(thread->ts, ret_addr); 25800447ccdSAdrian Hunter } else if (flags & PERF_IP_FLAG_RETURN) { 25900447ccdSAdrian Hunter if (!from_ip) 26000447ccdSAdrian Hunter return 0; 26100447ccdSAdrian Hunter thread_stack__pop(thread->ts, to_ip); 26200447ccdSAdrian Hunter } 26300447ccdSAdrian Hunter 26400447ccdSAdrian Hunter return 0; 26500447ccdSAdrian Hunter } 26600447ccdSAdrian Hunter 26792a9e4f7SAdrian Hunter void thread_stack__set_trace_nr(struct thread *thread, u64 trace_nr) 26892a9e4f7SAdrian Hunter { 26992a9e4f7SAdrian Hunter if (!thread || !thread->ts) 27092a9e4f7SAdrian Hunter return; 27192a9e4f7SAdrian Hunter 27292a9e4f7SAdrian Hunter if (trace_nr != thread->ts->trace_nr) { 27392a9e4f7SAdrian Hunter if (thread->ts->trace_nr) 274a5499b37SAdrian Hunter __thread_stack__flush(thread, thread->ts); 27592a9e4f7SAdrian Hunter thread->ts->trace_nr = trace_nr; 27692a9e4f7SAdrian Hunter } 27792a9e4f7SAdrian Hunter } 27892a9e4f7SAdrian Hunter 27900447ccdSAdrian Hunter void thread_stack__free(struct thread *thread) 28000447ccdSAdrian Hunter { 28100447ccdSAdrian Hunter if (thread->ts) { 282a5499b37SAdrian Hunter __thread_stack__flush(thread, thread->ts); 28300447ccdSAdrian Hunter zfree(&thread->ts->stack); 28400447ccdSAdrian Hunter zfree(&thread->ts); 28500447ccdSAdrian Hunter } 28600447ccdSAdrian Hunter } 28700447ccdSAdrian Hunter 28800447ccdSAdrian Hunter void thread_stack__sample(struct thread *thread, struct ip_callchain *chain, 28900447ccdSAdrian Hunter size_t sz, u64 ip) 29000447ccdSAdrian Hunter { 29100447ccdSAdrian Hunter size_t i; 29200447ccdSAdrian Hunter 29300447ccdSAdrian Hunter if (!thread || !thread->ts) 29400447ccdSAdrian Hunter chain->nr = 1; 29500447ccdSAdrian Hunter else 29600447ccdSAdrian Hunter chain->nr = min(sz, thread->ts->cnt + 1); 29700447ccdSAdrian Hunter 29800447ccdSAdrian Hunter chain->ips[0] = ip; 29900447ccdSAdrian Hunter 30000447ccdSAdrian Hunter for (i = 1; i < chain->nr; i++) 30100447ccdSAdrian Hunter chain->ips[i] = thread->ts->stack[thread->ts->cnt - i].ret_addr; 30200447ccdSAdrian Hunter } 30392a9e4f7SAdrian Hunter 30492a9e4f7SAdrian Hunter struct call_return_processor * 30592a9e4f7SAdrian Hunter call_return_processor__new(int (*process)(struct call_return *cr, void *data), 30692a9e4f7SAdrian Hunter void *data) 30792a9e4f7SAdrian Hunter { 30892a9e4f7SAdrian Hunter struct call_return_processor *crp; 30992a9e4f7SAdrian Hunter 31092a9e4f7SAdrian Hunter crp = zalloc(sizeof(struct call_return_processor)); 31192a9e4f7SAdrian Hunter if (!crp) 31292a9e4f7SAdrian Hunter return NULL; 31392a9e4f7SAdrian Hunter crp->cpr = call_path_root__new(); 31492a9e4f7SAdrian Hunter if (!crp->cpr) 31592a9e4f7SAdrian Hunter goto out_free; 31692a9e4f7SAdrian Hunter crp->process = process; 31792a9e4f7SAdrian Hunter crp->data = data; 31892a9e4f7SAdrian Hunter return crp; 31992a9e4f7SAdrian Hunter 32092a9e4f7SAdrian Hunter out_free: 32192a9e4f7SAdrian Hunter free(crp); 32292a9e4f7SAdrian Hunter return NULL; 32392a9e4f7SAdrian Hunter } 32492a9e4f7SAdrian Hunter 32592a9e4f7SAdrian Hunter void call_return_processor__free(struct call_return_processor *crp) 32692a9e4f7SAdrian Hunter { 32792a9e4f7SAdrian Hunter if (crp) { 32892a9e4f7SAdrian Hunter call_path_root__free(crp->cpr); 32992a9e4f7SAdrian Hunter free(crp); 33092a9e4f7SAdrian Hunter } 33192a9e4f7SAdrian Hunter } 33292a9e4f7SAdrian Hunter 33392a9e4f7SAdrian Hunter static int thread_stack__push_cp(struct thread_stack *ts, u64 ret_addr, 33492a9e4f7SAdrian Hunter u64 timestamp, u64 ref, struct call_path *cp, 33592a9e4f7SAdrian Hunter bool no_call) 33692a9e4f7SAdrian Hunter { 33792a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 33892a9e4f7SAdrian Hunter int err; 33992a9e4f7SAdrian Hunter 34092a9e4f7SAdrian Hunter if (ts->cnt == ts->sz) { 34192a9e4f7SAdrian Hunter err = thread_stack__grow(ts); 34292a9e4f7SAdrian Hunter if (err) 34392a9e4f7SAdrian Hunter return err; 34492a9e4f7SAdrian Hunter } 34592a9e4f7SAdrian Hunter 34692a9e4f7SAdrian Hunter tse = &ts->stack[ts->cnt++]; 34792a9e4f7SAdrian Hunter tse->ret_addr = ret_addr; 34892a9e4f7SAdrian Hunter tse->timestamp = timestamp; 34992a9e4f7SAdrian Hunter tse->ref = ref; 35092a9e4f7SAdrian Hunter tse->branch_count = ts->branch_count; 35192a9e4f7SAdrian Hunter tse->cp = cp; 35292a9e4f7SAdrian Hunter tse->no_call = no_call; 35392a9e4f7SAdrian Hunter 35492a9e4f7SAdrian Hunter return 0; 35592a9e4f7SAdrian Hunter } 35692a9e4f7SAdrian Hunter 35792a9e4f7SAdrian Hunter static int thread_stack__pop_cp(struct thread *thread, struct thread_stack *ts, 35892a9e4f7SAdrian Hunter u64 ret_addr, u64 timestamp, u64 ref, 35992a9e4f7SAdrian Hunter struct symbol *sym) 36092a9e4f7SAdrian Hunter { 36192a9e4f7SAdrian Hunter int err; 36292a9e4f7SAdrian Hunter 36392a9e4f7SAdrian Hunter if (!ts->cnt) 36492a9e4f7SAdrian Hunter return 1; 36592a9e4f7SAdrian Hunter 36692a9e4f7SAdrian Hunter if (ts->cnt == 1) { 36792a9e4f7SAdrian Hunter struct thread_stack_entry *tse = &ts->stack[0]; 36892a9e4f7SAdrian Hunter 36992a9e4f7SAdrian Hunter if (tse->cp->sym == sym) 37092a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 37192a9e4f7SAdrian Hunter timestamp, ref, false); 37292a9e4f7SAdrian Hunter } 37392a9e4f7SAdrian Hunter 37492a9e4f7SAdrian Hunter if (ts->stack[ts->cnt - 1].ret_addr == ret_addr) { 37592a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 37692a9e4f7SAdrian Hunter timestamp, ref, false); 37792a9e4f7SAdrian Hunter } else { 37892a9e4f7SAdrian Hunter size_t i = ts->cnt - 1; 37992a9e4f7SAdrian Hunter 38092a9e4f7SAdrian Hunter while (i--) { 38192a9e4f7SAdrian Hunter if (ts->stack[i].ret_addr != ret_addr) 38292a9e4f7SAdrian Hunter continue; 38392a9e4f7SAdrian Hunter i += 1; 38492a9e4f7SAdrian Hunter while (ts->cnt > i) { 38592a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, 38692a9e4f7SAdrian Hunter --ts->cnt, 38792a9e4f7SAdrian Hunter timestamp, ref, 38892a9e4f7SAdrian Hunter true); 38992a9e4f7SAdrian Hunter if (err) 39092a9e4f7SAdrian Hunter return err; 39192a9e4f7SAdrian Hunter } 39292a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 39392a9e4f7SAdrian Hunter timestamp, ref, false); 39492a9e4f7SAdrian Hunter } 39592a9e4f7SAdrian Hunter } 39692a9e4f7SAdrian Hunter 39792a9e4f7SAdrian Hunter return 1; 39892a9e4f7SAdrian Hunter } 39992a9e4f7SAdrian Hunter 40092a9e4f7SAdrian Hunter static int thread_stack__bottom(struct thread *thread, struct thread_stack *ts, 40192a9e4f7SAdrian Hunter struct perf_sample *sample, 40292a9e4f7SAdrian Hunter struct addr_location *from_al, 40392a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref) 40492a9e4f7SAdrian Hunter { 40592a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 40692a9e4f7SAdrian Hunter struct call_path *cp; 40792a9e4f7SAdrian Hunter struct symbol *sym; 40892a9e4f7SAdrian Hunter u64 ip; 40992a9e4f7SAdrian Hunter 41092a9e4f7SAdrian Hunter if (sample->ip) { 41192a9e4f7SAdrian Hunter ip = sample->ip; 41292a9e4f7SAdrian Hunter sym = from_al->sym; 41392a9e4f7SAdrian Hunter } else if (sample->addr) { 41492a9e4f7SAdrian Hunter ip = sample->addr; 41592a9e4f7SAdrian Hunter sym = to_al->sym; 41692a9e4f7SAdrian Hunter } else { 41792a9e4f7SAdrian Hunter return 0; 41892a9e4f7SAdrian Hunter } 41992a9e4f7SAdrian Hunter 42092a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, &cpr->call_path, sym, ip, 42192a9e4f7SAdrian Hunter ts->kernel_start); 42292a9e4f7SAdrian Hunter if (!cp) 42392a9e4f7SAdrian Hunter return -ENOMEM; 42492a9e4f7SAdrian Hunter 42592a9e4f7SAdrian Hunter return thread_stack__push_cp(thread->ts, ip, sample->time, ref, cp, 42692a9e4f7SAdrian Hunter true); 42792a9e4f7SAdrian Hunter } 42892a9e4f7SAdrian Hunter 42992a9e4f7SAdrian Hunter static int thread_stack__no_call_return(struct thread *thread, 43092a9e4f7SAdrian Hunter struct thread_stack *ts, 43192a9e4f7SAdrian Hunter struct perf_sample *sample, 43292a9e4f7SAdrian Hunter struct addr_location *from_al, 43392a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref) 43492a9e4f7SAdrian Hunter { 43592a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 43692a9e4f7SAdrian Hunter struct call_path *cp, *parent; 43792a9e4f7SAdrian Hunter u64 ks = ts->kernel_start; 43892a9e4f7SAdrian Hunter int err; 43992a9e4f7SAdrian Hunter 44092a9e4f7SAdrian Hunter if (sample->ip >= ks && sample->addr < ks) { 44192a9e4f7SAdrian Hunter /* Return to userspace, so pop all kernel addresses */ 44292a9e4f7SAdrian Hunter while (thread_stack__in_kernel(ts)) { 44392a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 44492a9e4f7SAdrian Hunter sample->time, ref, 44592a9e4f7SAdrian Hunter true); 44692a9e4f7SAdrian Hunter if (err) 44792a9e4f7SAdrian Hunter return err; 44892a9e4f7SAdrian Hunter } 44992a9e4f7SAdrian Hunter 45092a9e4f7SAdrian Hunter /* If the stack is empty, push the userspace address */ 45192a9e4f7SAdrian Hunter if (!ts->cnt) { 45292a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, &cpr->call_path, 45392a9e4f7SAdrian Hunter to_al->sym, sample->addr, 45492a9e4f7SAdrian Hunter ts->kernel_start); 45592a9e4f7SAdrian Hunter if (!cp) 45692a9e4f7SAdrian Hunter return -ENOMEM; 45792a9e4f7SAdrian Hunter return thread_stack__push_cp(ts, 0, sample->time, ref, 45892a9e4f7SAdrian Hunter cp, true); 45992a9e4f7SAdrian Hunter } 46092a9e4f7SAdrian Hunter } else if (thread_stack__in_kernel(ts) && sample->ip < ks) { 46192a9e4f7SAdrian Hunter /* Return to userspace, so pop all kernel addresses */ 46292a9e4f7SAdrian Hunter while (thread_stack__in_kernel(ts)) { 46392a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 46492a9e4f7SAdrian Hunter sample->time, ref, 46592a9e4f7SAdrian Hunter true); 46692a9e4f7SAdrian Hunter if (err) 46792a9e4f7SAdrian Hunter return err; 46892a9e4f7SAdrian Hunter } 46992a9e4f7SAdrian Hunter } 47092a9e4f7SAdrian Hunter 47192a9e4f7SAdrian Hunter if (ts->cnt) 47292a9e4f7SAdrian Hunter parent = ts->stack[ts->cnt - 1].cp; 47392a9e4f7SAdrian Hunter else 47492a9e4f7SAdrian Hunter parent = &cpr->call_path; 47592a9e4f7SAdrian Hunter 47692a9e4f7SAdrian Hunter /* This 'return' had no 'call', so push and pop top of stack */ 47792a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, parent, from_al->sym, sample->ip, 47892a9e4f7SAdrian Hunter ts->kernel_start); 47992a9e4f7SAdrian Hunter if (!cp) 48092a9e4f7SAdrian Hunter return -ENOMEM; 48192a9e4f7SAdrian Hunter 48292a9e4f7SAdrian Hunter err = thread_stack__push_cp(ts, sample->addr, sample->time, ref, cp, 48392a9e4f7SAdrian Hunter true); 48492a9e4f7SAdrian Hunter if (err) 48592a9e4f7SAdrian Hunter return err; 48692a9e4f7SAdrian Hunter 48792a9e4f7SAdrian Hunter return thread_stack__pop_cp(thread, ts, sample->addr, sample->time, ref, 48892a9e4f7SAdrian Hunter to_al->sym); 48992a9e4f7SAdrian Hunter } 49092a9e4f7SAdrian Hunter 49192a9e4f7SAdrian Hunter static int thread_stack__trace_begin(struct thread *thread, 49292a9e4f7SAdrian Hunter struct thread_stack *ts, u64 timestamp, 49392a9e4f7SAdrian Hunter u64 ref) 49492a9e4f7SAdrian Hunter { 49592a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 49692a9e4f7SAdrian Hunter int err; 49792a9e4f7SAdrian Hunter 49892a9e4f7SAdrian Hunter if (!ts->cnt) 49992a9e4f7SAdrian Hunter return 0; 50092a9e4f7SAdrian Hunter 50192a9e4f7SAdrian Hunter /* Pop trace end */ 50292a9e4f7SAdrian Hunter tse = &ts->stack[ts->cnt - 1]; 50392a9e4f7SAdrian Hunter if (tse->cp->sym == NULL && tse->cp->ip == 0) { 50492a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 50592a9e4f7SAdrian Hunter timestamp, ref, false); 50692a9e4f7SAdrian Hunter if (err) 50792a9e4f7SAdrian Hunter return err; 50892a9e4f7SAdrian Hunter } 50992a9e4f7SAdrian Hunter 51092a9e4f7SAdrian Hunter return 0; 51192a9e4f7SAdrian Hunter } 51292a9e4f7SAdrian Hunter 51392a9e4f7SAdrian Hunter static int thread_stack__trace_end(struct thread_stack *ts, 51492a9e4f7SAdrian Hunter struct perf_sample *sample, u64 ref) 51592a9e4f7SAdrian Hunter { 51692a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 51792a9e4f7SAdrian Hunter struct call_path *cp; 51892a9e4f7SAdrian Hunter u64 ret_addr; 51992a9e4f7SAdrian Hunter 52092a9e4f7SAdrian Hunter /* No point having 'trace end' on the bottom of the stack */ 52192a9e4f7SAdrian Hunter if (!ts->cnt || (ts->cnt == 1 && ts->stack[0].ref == ref)) 52292a9e4f7SAdrian Hunter return 0; 52392a9e4f7SAdrian Hunter 52492a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, NULL, 0, 52592a9e4f7SAdrian Hunter ts->kernel_start); 52692a9e4f7SAdrian Hunter if (!cp) 52792a9e4f7SAdrian Hunter return -ENOMEM; 52892a9e4f7SAdrian Hunter 52992a9e4f7SAdrian Hunter ret_addr = sample->ip + sample->insn_len; 53092a9e4f7SAdrian Hunter 53192a9e4f7SAdrian Hunter return thread_stack__push_cp(ts, ret_addr, sample->time, ref, cp, 53292a9e4f7SAdrian Hunter false); 53392a9e4f7SAdrian Hunter } 53492a9e4f7SAdrian Hunter 53592a9e4f7SAdrian Hunter int thread_stack__process(struct thread *thread, struct comm *comm, 53692a9e4f7SAdrian Hunter struct perf_sample *sample, 53792a9e4f7SAdrian Hunter struct addr_location *from_al, 53892a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref, 53992a9e4f7SAdrian Hunter struct call_return_processor *crp) 54092a9e4f7SAdrian Hunter { 54192a9e4f7SAdrian Hunter struct thread_stack *ts = thread->ts; 54292a9e4f7SAdrian Hunter int err = 0; 54392a9e4f7SAdrian Hunter 54492a9e4f7SAdrian Hunter if (ts) { 54592a9e4f7SAdrian Hunter if (!ts->crp) { 54692a9e4f7SAdrian Hunter /* Supersede thread_stack__event() */ 54792a9e4f7SAdrian Hunter thread_stack__free(thread); 54892a9e4f7SAdrian Hunter thread->ts = thread_stack__new(thread, crp); 54992a9e4f7SAdrian Hunter if (!thread->ts) 55092a9e4f7SAdrian Hunter return -ENOMEM; 55192a9e4f7SAdrian Hunter ts = thread->ts; 55292a9e4f7SAdrian Hunter ts->comm = comm; 55392a9e4f7SAdrian Hunter } 55492a9e4f7SAdrian Hunter } else { 55592a9e4f7SAdrian Hunter thread->ts = thread_stack__new(thread, crp); 55692a9e4f7SAdrian Hunter if (!thread->ts) 55792a9e4f7SAdrian Hunter return -ENOMEM; 55892a9e4f7SAdrian Hunter ts = thread->ts; 55992a9e4f7SAdrian Hunter ts->comm = comm; 56092a9e4f7SAdrian Hunter } 56192a9e4f7SAdrian Hunter 56292a9e4f7SAdrian Hunter /* Flush stack on exec */ 56392a9e4f7SAdrian Hunter if (ts->comm != comm && thread->pid_ == thread->tid) { 564a5499b37SAdrian Hunter err = __thread_stack__flush(thread, ts); 56592a9e4f7SAdrian Hunter if (err) 56692a9e4f7SAdrian Hunter return err; 56792a9e4f7SAdrian Hunter ts->comm = comm; 56892a9e4f7SAdrian Hunter } 56992a9e4f7SAdrian Hunter 57092a9e4f7SAdrian Hunter /* If the stack is empty, put the current symbol on the stack */ 57192a9e4f7SAdrian Hunter if (!ts->cnt) { 57292a9e4f7SAdrian Hunter err = thread_stack__bottom(thread, ts, sample, from_al, to_al, 57392a9e4f7SAdrian Hunter ref); 57492a9e4f7SAdrian Hunter if (err) 57592a9e4f7SAdrian Hunter return err; 57692a9e4f7SAdrian Hunter } 57792a9e4f7SAdrian Hunter 57892a9e4f7SAdrian Hunter ts->branch_count += 1; 57992a9e4f7SAdrian Hunter ts->last_time = sample->time; 58092a9e4f7SAdrian Hunter 58192a9e4f7SAdrian Hunter if (sample->flags & PERF_IP_FLAG_CALL) { 58292a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 58392a9e4f7SAdrian Hunter struct call_path *cp; 58492a9e4f7SAdrian Hunter u64 ret_addr; 58592a9e4f7SAdrian Hunter 58692a9e4f7SAdrian Hunter if (!sample->ip || !sample->addr) 58792a9e4f7SAdrian Hunter return 0; 58892a9e4f7SAdrian Hunter 58992a9e4f7SAdrian Hunter ret_addr = sample->ip + sample->insn_len; 59092a9e4f7SAdrian Hunter if (ret_addr == sample->addr) 59192a9e4f7SAdrian Hunter return 0; /* Zero-length calls are excluded */ 59292a9e4f7SAdrian Hunter 59392a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, 59492a9e4f7SAdrian Hunter to_al->sym, sample->addr, 59592a9e4f7SAdrian Hunter ts->kernel_start); 59692a9e4f7SAdrian Hunter if (!cp) 59792a9e4f7SAdrian Hunter return -ENOMEM; 59892a9e4f7SAdrian Hunter err = thread_stack__push_cp(ts, ret_addr, sample->time, ref, 59992a9e4f7SAdrian Hunter cp, false); 60092a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_RETURN) { 60192a9e4f7SAdrian Hunter if (!sample->ip || !sample->addr) 60292a9e4f7SAdrian Hunter return 0; 60392a9e4f7SAdrian Hunter 60492a9e4f7SAdrian Hunter err = thread_stack__pop_cp(thread, ts, sample->addr, 60592a9e4f7SAdrian Hunter sample->time, ref, from_al->sym); 60692a9e4f7SAdrian Hunter if (err) { 60792a9e4f7SAdrian Hunter if (err < 0) 60892a9e4f7SAdrian Hunter return err; 60992a9e4f7SAdrian Hunter err = thread_stack__no_call_return(thread, ts, sample, 61092a9e4f7SAdrian Hunter from_al, to_al, ref); 61192a9e4f7SAdrian Hunter } 61292a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_TRACE_BEGIN) { 61392a9e4f7SAdrian Hunter err = thread_stack__trace_begin(thread, ts, sample->time, ref); 61492a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_TRACE_END) { 61592a9e4f7SAdrian Hunter err = thread_stack__trace_end(ts, sample, ref); 61692a9e4f7SAdrian Hunter } 61792a9e4f7SAdrian Hunter 61892a9e4f7SAdrian Hunter return err; 61992a9e4f7SAdrian Hunter } 620e216708dSAdrian Hunter 621e216708dSAdrian Hunter size_t thread_stack__depth(struct thread *thread) 622e216708dSAdrian Hunter { 623e216708dSAdrian Hunter if (!thread->ts) 624e216708dSAdrian Hunter return 0; 625e216708dSAdrian Hunter return thread->ts->cnt; 626e216708dSAdrian Hunter } 627