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 394d60e5e3SAdrian Hunter * @trace_end: a 'call' but trace ended 4092a9e4f7SAdrian Hunter */ 4192a9e4f7SAdrian Hunter struct thread_stack_entry { 4292a9e4f7SAdrian Hunter u64 ret_addr; 4392a9e4f7SAdrian Hunter u64 timestamp; 4492a9e4f7SAdrian Hunter u64 ref; 4592a9e4f7SAdrian Hunter u64 branch_count; 4692a9e4f7SAdrian Hunter struct call_path *cp; 4792a9e4f7SAdrian Hunter bool no_call; 484d60e5e3SAdrian Hunter bool trace_end; 4992a9e4f7SAdrian Hunter }; 5092a9e4f7SAdrian Hunter 5192a9e4f7SAdrian Hunter /** 5292a9e4f7SAdrian Hunter * struct thread_stack - thread stack constructed from 'call' and 'return' 5392a9e4f7SAdrian Hunter * branch samples. 5492a9e4f7SAdrian Hunter * @stack: array that holds the stack 5592a9e4f7SAdrian Hunter * @cnt: number of entries in the stack 5692a9e4f7SAdrian Hunter * @sz: current maximum stack size 5792a9e4f7SAdrian Hunter * @trace_nr: current trace number 5892a9e4f7SAdrian Hunter * @branch_count: running branch count 5992a9e4f7SAdrian Hunter * @kernel_start: kernel start address 6092a9e4f7SAdrian Hunter * @last_time: last timestamp 6192a9e4f7SAdrian Hunter * @crp: call/return processor 6292a9e4f7SAdrian Hunter * @comm: current comm 63f6060ac6SAdrian Hunter * @arr_sz: size of array if this is the first element of an array 6492a9e4f7SAdrian Hunter */ 6500447ccdSAdrian Hunter struct thread_stack { 6600447ccdSAdrian Hunter struct thread_stack_entry *stack; 6700447ccdSAdrian Hunter size_t cnt; 6800447ccdSAdrian Hunter size_t sz; 6900447ccdSAdrian Hunter u64 trace_nr; 7092a9e4f7SAdrian Hunter u64 branch_count; 7192a9e4f7SAdrian Hunter u64 kernel_start; 7292a9e4f7SAdrian Hunter u64 last_time; 7392a9e4f7SAdrian Hunter struct call_return_processor *crp; 7492a9e4f7SAdrian Hunter struct comm *comm; 75f6060ac6SAdrian Hunter unsigned int arr_sz; 7600447ccdSAdrian Hunter }; 7700447ccdSAdrian Hunter 7800447ccdSAdrian Hunter static int thread_stack__grow(struct thread_stack *ts) 7900447ccdSAdrian Hunter { 8000447ccdSAdrian Hunter struct thread_stack_entry *new_stack; 8100447ccdSAdrian Hunter size_t sz, new_sz; 8200447ccdSAdrian Hunter 8300447ccdSAdrian Hunter new_sz = ts->sz + STACK_GROWTH; 8400447ccdSAdrian Hunter sz = new_sz * sizeof(struct thread_stack_entry); 8500447ccdSAdrian Hunter 8600447ccdSAdrian Hunter new_stack = realloc(ts->stack, sz); 8700447ccdSAdrian Hunter if (!new_stack) 8800447ccdSAdrian Hunter return -ENOMEM; 8900447ccdSAdrian Hunter 9000447ccdSAdrian Hunter ts->stack = new_stack; 9100447ccdSAdrian Hunter ts->sz = new_sz; 9200447ccdSAdrian Hunter 9300447ccdSAdrian Hunter return 0; 9400447ccdSAdrian Hunter } 9500447ccdSAdrian Hunter 962e9e8688SAdrian Hunter static int thread_stack__init(struct thread_stack *ts, struct thread *thread, 972e9e8688SAdrian Hunter struct call_return_processor *crp) 982e9e8688SAdrian Hunter { 992e9e8688SAdrian Hunter int err; 1002e9e8688SAdrian Hunter 1012e9e8688SAdrian Hunter err = thread_stack__grow(ts); 1022e9e8688SAdrian Hunter if (err) 1032e9e8688SAdrian Hunter return err; 1042e9e8688SAdrian Hunter 1052e9e8688SAdrian Hunter if (thread->mg && thread->mg->machine) 1062e9e8688SAdrian Hunter ts->kernel_start = machine__kernel_start(thread->mg->machine); 1072e9e8688SAdrian Hunter else 1082e9e8688SAdrian Hunter ts->kernel_start = 1ULL << 63; 1092e9e8688SAdrian Hunter ts->crp = crp; 1102e9e8688SAdrian Hunter 1112e9e8688SAdrian Hunter return 0; 1122e9e8688SAdrian Hunter } 1132e9e8688SAdrian Hunter 11492a9e4f7SAdrian Hunter static struct thread_stack *thread_stack__new(struct thread *thread, 11592a9e4f7SAdrian Hunter struct call_return_processor *crp) 11600447ccdSAdrian Hunter { 117139f42f3SAdrian Hunter struct thread_stack *ts = thread->ts, *new_ts; 118139f42f3SAdrian Hunter unsigned int old_sz = ts ? ts->arr_sz : 0; 119139f42f3SAdrian Hunter unsigned int new_sz = 1; 12000447ccdSAdrian Hunter 121139f42f3SAdrian Hunter if (!ts || new_sz > old_sz) { 122139f42f3SAdrian Hunter new_ts = calloc(new_sz, sizeof(*ts)); 123139f42f3SAdrian Hunter if (!new_ts) 12400447ccdSAdrian Hunter return NULL; 125139f42f3SAdrian Hunter if (ts) 126139f42f3SAdrian Hunter memcpy(new_ts, ts, old_sz * sizeof(*ts)); 127139f42f3SAdrian Hunter new_ts->arr_sz = new_sz; 128139f42f3SAdrian Hunter zfree(&thread->ts); 129139f42f3SAdrian Hunter thread->ts = new_ts; 130139f42f3SAdrian Hunter ts = new_ts; 13100447ccdSAdrian Hunter } 13200447ccdSAdrian Hunter 133139f42f3SAdrian Hunter if (!ts->stack && 134139f42f3SAdrian Hunter thread_stack__init(ts, thread, crp)) 135139f42f3SAdrian Hunter return NULL; 136bd8e68acSAdrian Hunter 13700447ccdSAdrian Hunter return ts; 13800447ccdSAdrian Hunter } 13900447ccdSAdrian Hunter 140bd8e68acSAdrian Hunter static inline struct thread_stack *thread__stack(struct thread *thread) 141bd8e68acSAdrian Hunter { 142bd8e68acSAdrian Hunter return thread ? thread->ts : NULL; 143bd8e68acSAdrian Hunter } 144bd8e68acSAdrian Hunter 1454d60e5e3SAdrian Hunter static int thread_stack__push(struct thread_stack *ts, u64 ret_addr, 1464d60e5e3SAdrian Hunter bool trace_end) 14700447ccdSAdrian Hunter { 14800447ccdSAdrian Hunter int err = 0; 14900447ccdSAdrian Hunter 15000447ccdSAdrian Hunter if (ts->cnt == ts->sz) { 15100447ccdSAdrian Hunter err = thread_stack__grow(ts); 15200447ccdSAdrian Hunter if (err) { 15300447ccdSAdrian Hunter pr_warning("Out of memory: discarding thread stack\n"); 15400447ccdSAdrian Hunter ts->cnt = 0; 15500447ccdSAdrian Hunter } 15600447ccdSAdrian Hunter } 15700447ccdSAdrian Hunter 1584d60e5e3SAdrian Hunter ts->stack[ts->cnt].trace_end = trace_end; 15900447ccdSAdrian Hunter ts->stack[ts->cnt++].ret_addr = ret_addr; 16000447ccdSAdrian Hunter 16100447ccdSAdrian Hunter return err; 16200447ccdSAdrian Hunter } 16300447ccdSAdrian Hunter 16400447ccdSAdrian Hunter static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr) 16500447ccdSAdrian Hunter { 16600447ccdSAdrian Hunter size_t i; 16700447ccdSAdrian Hunter 16800447ccdSAdrian Hunter /* 16900447ccdSAdrian Hunter * In some cases there may be functions which are not seen to return. 17000447ccdSAdrian Hunter * For example when setjmp / longjmp has been used. Or the perf context 17100447ccdSAdrian Hunter * switch in the kernel which doesn't stop and start tracing in exactly 17200447ccdSAdrian Hunter * the same code path. When that happens the return address will be 17300447ccdSAdrian Hunter * further down the stack. If the return address is not found at all, 17400447ccdSAdrian Hunter * we assume the opposite (i.e. this is a return for a call that wasn't 17500447ccdSAdrian Hunter * seen for some reason) and leave the stack alone. 17600447ccdSAdrian Hunter */ 17700447ccdSAdrian Hunter for (i = ts->cnt; i; ) { 17800447ccdSAdrian Hunter if (ts->stack[--i].ret_addr == ret_addr) { 17900447ccdSAdrian Hunter ts->cnt = i; 18000447ccdSAdrian Hunter return; 18100447ccdSAdrian Hunter } 18200447ccdSAdrian Hunter } 18300447ccdSAdrian Hunter } 18400447ccdSAdrian Hunter 1854d60e5e3SAdrian Hunter static void thread_stack__pop_trace_end(struct thread_stack *ts) 1864d60e5e3SAdrian Hunter { 1874d60e5e3SAdrian Hunter size_t i; 1884d60e5e3SAdrian Hunter 1894d60e5e3SAdrian Hunter for (i = ts->cnt; i; ) { 1904d60e5e3SAdrian Hunter if (ts->stack[--i].trace_end) 1914d60e5e3SAdrian Hunter ts->cnt = i; 1924d60e5e3SAdrian Hunter else 1934d60e5e3SAdrian Hunter return; 1944d60e5e3SAdrian Hunter } 1954d60e5e3SAdrian Hunter } 1964d60e5e3SAdrian Hunter 19792a9e4f7SAdrian Hunter static bool thread_stack__in_kernel(struct thread_stack *ts) 19892a9e4f7SAdrian Hunter { 19992a9e4f7SAdrian Hunter if (!ts->cnt) 20092a9e4f7SAdrian Hunter return false; 20192a9e4f7SAdrian Hunter 20292a9e4f7SAdrian Hunter return ts->stack[ts->cnt - 1].cp->in_kernel; 20392a9e4f7SAdrian Hunter } 20492a9e4f7SAdrian Hunter 20592a9e4f7SAdrian Hunter static int thread_stack__call_return(struct thread *thread, 20692a9e4f7SAdrian Hunter struct thread_stack *ts, size_t idx, 20792a9e4f7SAdrian Hunter u64 timestamp, u64 ref, bool no_return) 20892a9e4f7SAdrian Hunter { 20992a9e4f7SAdrian Hunter struct call_return_processor *crp = ts->crp; 21092a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 21192a9e4f7SAdrian Hunter struct call_return cr = { 21292a9e4f7SAdrian Hunter .thread = thread, 21392a9e4f7SAdrian Hunter .comm = ts->comm, 21492a9e4f7SAdrian Hunter .db_id = 0, 21592a9e4f7SAdrian Hunter }; 21692a9e4f7SAdrian Hunter 21792a9e4f7SAdrian Hunter tse = &ts->stack[idx]; 21892a9e4f7SAdrian Hunter cr.cp = tse->cp; 21992a9e4f7SAdrian Hunter cr.call_time = tse->timestamp; 22092a9e4f7SAdrian Hunter cr.return_time = timestamp; 22192a9e4f7SAdrian Hunter cr.branch_count = ts->branch_count - tse->branch_count; 22292a9e4f7SAdrian Hunter cr.call_ref = tse->ref; 22392a9e4f7SAdrian Hunter cr.return_ref = ref; 22492a9e4f7SAdrian Hunter if (tse->no_call) 22592a9e4f7SAdrian Hunter cr.flags |= CALL_RETURN_NO_CALL; 22692a9e4f7SAdrian Hunter if (no_return) 22792a9e4f7SAdrian Hunter cr.flags |= CALL_RETURN_NO_RETURN; 22892a9e4f7SAdrian Hunter 22992a9e4f7SAdrian Hunter return crp->process(&cr, crp->data); 23092a9e4f7SAdrian Hunter } 23192a9e4f7SAdrian Hunter 232a5499b37SAdrian Hunter static int __thread_stack__flush(struct thread *thread, struct thread_stack *ts) 23392a9e4f7SAdrian Hunter { 23492a9e4f7SAdrian Hunter struct call_return_processor *crp = ts->crp; 23592a9e4f7SAdrian Hunter int err; 23692a9e4f7SAdrian Hunter 23792a9e4f7SAdrian Hunter if (!crp) { 23892a9e4f7SAdrian Hunter ts->cnt = 0; 23992a9e4f7SAdrian Hunter return 0; 24092a9e4f7SAdrian Hunter } 24192a9e4f7SAdrian Hunter 24292a9e4f7SAdrian Hunter while (ts->cnt) { 24392a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 24492a9e4f7SAdrian Hunter ts->last_time, 0, true); 24592a9e4f7SAdrian Hunter if (err) { 24692a9e4f7SAdrian Hunter pr_err("Error flushing thread stack!\n"); 24792a9e4f7SAdrian Hunter ts->cnt = 0; 24892a9e4f7SAdrian Hunter return err; 24992a9e4f7SAdrian Hunter } 25092a9e4f7SAdrian Hunter } 25192a9e4f7SAdrian Hunter 25292a9e4f7SAdrian Hunter return 0; 25392a9e4f7SAdrian Hunter } 25492a9e4f7SAdrian Hunter 255a5499b37SAdrian Hunter int thread_stack__flush(struct thread *thread) 256a5499b37SAdrian Hunter { 257bd8e68acSAdrian Hunter struct thread_stack *ts = thread->ts; 258f6060ac6SAdrian Hunter unsigned int pos; 259f6060ac6SAdrian Hunter int err = 0; 260bd8e68acSAdrian Hunter 261f6060ac6SAdrian Hunter if (ts) { 262f6060ac6SAdrian Hunter for (pos = 0; pos < ts->arr_sz; pos++) { 263f6060ac6SAdrian Hunter int ret = __thread_stack__flush(thread, ts + pos); 264a5499b37SAdrian Hunter 265f6060ac6SAdrian Hunter if (ret) 266f6060ac6SAdrian Hunter err = ret; 267f6060ac6SAdrian Hunter } 268f6060ac6SAdrian Hunter } 269f6060ac6SAdrian Hunter 270f6060ac6SAdrian Hunter return err; 271a5499b37SAdrian Hunter } 272a5499b37SAdrian Hunter 27300447ccdSAdrian Hunter int thread_stack__event(struct thread *thread, u32 flags, u64 from_ip, 27400447ccdSAdrian Hunter u64 to_ip, u16 insn_len, u64 trace_nr) 27500447ccdSAdrian Hunter { 276bd8e68acSAdrian Hunter struct thread_stack *ts = thread__stack(thread); 277bd8e68acSAdrian Hunter 27800447ccdSAdrian Hunter if (!thread) 27900447ccdSAdrian Hunter return -EINVAL; 28000447ccdSAdrian Hunter 281bd8e68acSAdrian Hunter if (!ts) { 282bd8e68acSAdrian Hunter ts = thread_stack__new(thread, NULL); 283bd8e68acSAdrian Hunter if (!ts) { 28400447ccdSAdrian Hunter pr_warning("Out of memory: no thread stack\n"); 28500447ccdSAdrian Hunter return -ENOMEM; 28600447ccdSAdrian Hunter } 287bd8e68acSAdrian Hunter ts->trace_nr = trace_nr; 28800447ccdSAdrian Hunter } 28900447ccdSAdrian Hunter 29000447ccdSAdrian Hunter /* 29100447ccdSAdrian Hunter * When the trace is discontinuous, the trace_nr changes. In that case 29200447ccdSAdrian Hunter * the stack might be completely invalid. Better to report nothing than 29392a9e4f7SAdrian Hunter * to report something misleading, so flush the stack. 29400447ccdSAdrian Hunter */ 295bd8e68acSAdrian Hunter if (trace_nr != ts->trace_nr) { 296bd8e68acSAdrian Hunter if (ts->trace_nr) 297bd8e68acSAdrian Hunter __thread_stack__flush(thread, ts); 298bd8e68acSAdrian Hunter ts->trace_nr = trace_nr; 29900447ccdSAdrian Hunter } 30000447ccdSAdrian Hunter 30192a9e4f7SAdrian Hunter /* Stop here if thread_stack__process() is in use */ 302bd8e68acSAdrian Hunter if (ts->crp) 30392a9e4f7SAdrian Hunter return 0; 30492a9e4f7SAdrian Hunter 30500447ccdSAdrian Hunter if (flags & PERF_IP_FLAG_CALL) { 30600447ccdSAdrian Hunter u64 ret_addr; 30700447ccdSAdrian Hunter 30800447ccdSAdrian Hunter if (!to_ip) 30900447ccdSAdrian Hunter return 0; 31000447ccdSAdrian Hunter ret_addr = from_ip + insn_len; 31100447ccdSAdrian Hunter if (ret_addr == to_ip) 31200447ccdSAdrian Hunter return 0; /* Zero-length calls are excluded */ 313bd8e68acSAdrian Hunter return thread_stack__push(ts, ret_addr, 3144d60e5e3SAdrian Hunter flags & PERF_IP_FLAG_TRACE_END); 3154d60e5e3SAdrian Hunter } else if (flags & PERF_IP_FLAG_TRACE_BEGIN) { 3164d60e5e3SAdrian Hunter /* 3174d60e5e3SAdrian Hunter * If the caller did not change the trace number (which would 3184d60e5e3SAdrian Hunter * have flushed the stack) then try to make sense of the stack. 3194d60e5e3SAdrian Hunter * Possibly, tracing began after returning to the current 3204d60e5e3SAdrian Hunter * address, so try to pop that. Also, do not expect a call made 3214d60e5e3SAdrian Hunter * when the trace ended, to return, so pop that. 3224d60e5e3SAdrian Hunter */ 323bd8e68acSAdrian Hunter thread_stack__pop(ts, to_ip); 324bd8e68acSAdrian Hunter thread_stack__pop_trace_end(ts); 3254d60e5e3SAdrian Hunter } else if ((flags & PERF_IP_FLAG_RETURN) && from_ip) { 326bd8e68acSAdrian Hunter thread_stack__pop(ts, to_ip); 32700447ccdSAdrian Hunter } 32800447ccdSAdrian Hunter 32900447ccdSAdrian Hunter return 0; 33000447ccdSAdrian Hunter } 33100447ccdSAdrian Hunter 33292a9e4f7SAdrian Hunter void thread_stack__set_trace_nr(struct thread *thread, u64 trace_nr) 33392a9e4f7SAdrian Hunter { 334bd8e68acSAdrian Hunter struct thread_stack *ts = thread__stack(thread); 335bd8e68acSAdrian Hunter 336bd8e68acSAdrian Hunter if (!ts) 33792a9e4f7SAdrian Hunter return; 33892a9e4f7SAdrian Hunter 339bd8e68acSAdrian Hunter if (trace_nr != ts->trace_nr) { 340bd8e68acSAdrian Hunter if (ts->trace_nr) 341bd8e68acSAdrian Hunter __thread_stack__flush(thread, ts); 342bd8e68acSAdrian Hunter ts->trace_nr = trace_nr; 34392a9e4f7SAdrian Hunter } 34492a9e4f7SAdrian Hunter } 34592a9e4f7SAdrian Hunter 346f6060ac6SAdrian Hunter static void __thread_stack__free(struct thread *thread, struct thread_stack *ts) 347f6060ac6SAdrian Hunter { 348f6060ac6SAdrian Hunter __thread_stack__flush(thread, ts); 349f6060ac6SAdrian Hunter zfree(&ts->stack); 350f6060ac6SAdrian Hunter } 351f6060ac6SAdrian Hunter 352f6060ac6SAdrian Hunter static void thread_stack__reset(struct thread *thread, struct thread_stack *ts) 353f6060ac6SAdrian Hunter { 354f6060ac6SAdrian Hunter unsigned int arr_sz = ts->arr_sz; 355f6060ac6SAdrian Hunter 356f6060ac6SAdrian Hunter __thread_stack__free(thread, ts); 357f6060ac6SAdrian Hunter memset(ts, 0, sizeof(*ts)); 358f6060ac6SAdrian Hunter ts->arr_sz = arr_sz; 359f6060ac6SAdrian Hunter } 360f6060ac6SAdrian Hunter 36100447ccdSAdrian Hunter void thread_stack__free(struct thread *thread) 36200447ccdSAdrian Hunter { 363bd8e68acSAdrian Hunter struct thread_stack *ts = thread->ts; 364f6060ac6SAdrian Hunter unsigned int pos; 365bd8e68acSAdrian Hunter 366bd8e68acSAdrian Hunter if (ts) { 367f6060ac6SAdrian Hunter for (pos = 0; pos < ts->arr_sz; pos++) 368f6060ac6SAdrian Hunter __thread_stack__free(thread, ts + pos); 36900447ccdSAdrian Hunter zfree(&thread->ts); 37000447ccdSAdrian Hunter } 37100447ccdSAdrian Hunter } 37200447ccdSAdrian Hunter 37324248306SAdrian Hunter static inline u64 callchain_context(u64 ip, u64 kernel_start) 37400447ccdSAdrian Hunter { 37524248306SAdrian Hunter return ip < kernel_start ? PERF_CONTEXT_USER : PERF_CONTEXT_KERNEL; 37624248306SAdrian Hunter } 37700447ccdSAdrian Hunter 37824248306SAdrian Hunter void thread_stack__sample(struct thread *thread, struct ip_callchain *chain, 37924248306SAdrian Hunter size_t sz, u64 ip, u64 kernel_start) 38024248306SAdrian Hunter { 381bd8e68acSAdrian Hunter struct thread_stack *ts = thread__stack(thread); 38224248306SAdrian Hunter u64 context = callchain_context(ip, kernel_start); 38324248306SAdrian Hunter u64 last_context; 38424248306SAdrian Hunter size_t i, j; 38500447ccdSAdrian Hunter 38624248306SAdrian Hunter if (sz < 2) { 38724248306SAdrian Hunter chain->nr = 0; 38824248306SAdrian Hunter return; 38924248306SAdrian Hunter } 39000447ccdSAdrian Hunter 39124248306SAdrian Hunter chain->ips[0] = context; 39224248306SAdrian Hunter chain->ips[1] = ip; 39324248306SAdrian Hunter 394bd8e68acSAdrian Hunter if (!ts) { 39524248306SAdrian Hunter chain->nr = 2; 39624248306SAdrian Hunter return; 39724248306SAdrian Hunter } 39824248306SAdrian Hunter 39924248306SAdrian Hunter last_context = context; 40024248306SAdrian Hunter 401bd8e68acSAdrian Hunter for (i = 2, j = 1; i < sz && j <= ts->cnt; i++, j++) { 402bd8e68acSAdrian Hunter ip = ts->stack[ts->cnt - j].ret_addr; 40324248306SAdrian Hunter context = callchain_context(ip, kernel_start); 40424248306SAdrian Hunter if (context != last_context) { 40524248306SAdrian Hunter if (i >= sz - 1) 40624248306SAdrian Hunter break; 40724248306SAdrian Hunter chain->ips[i++] = context; 40824248306SAdrian Hunter last_context = context; 40924248306SAdrian Hunter } 41024248306SAdrian Hunter chain->ips[i] = ip; 41124248306SAdrian Hunter } 41224248306SAdrian Hunter 41324248306SAdrian Hunter chain->nr = i; 41400447ccdSAdrian Hunter } 41592a9e4f7SAdrian Hunter 41692a9e4f7SAdrian Hunter struct call_return_processor * 41792a9e4f7SAdrian Hunter call_return_processor__new(int (*process)(struct call_return *cr, void *data), 41892a9e4f7SAdrian Hunter void *data) 41992a9e4f7SAdrian Hunter { 42092a9e4f7SAdrian Hunter struct call_return_processor *crp; 42192a9e4f7SAdrian Hunter 42292a9e4f7SAdrian Hunter crp = zalloc(sizeof(struct call_return_processor)); 42392a9e4f7SAdrian Hunter if (!crp) 42492a9e4f7SAdrian Hunter return NULL; 42592a9e4f7SAdrian Hunter crp->cpr = call_path_root__new(); 42692a9e4f7SAdrian Hunter if (!crp->cpr) 42792a9e4f7SAdrian Hunter goto out_free; 42892a9e4f7SAdrian Hunter crp->process = process; 42992a9e4f7SAdrian Hunter crp->data = data; 43092a9e4f7SAdrian Hunter return crp; 43192a9e4f7SAdrian Hunter 43292a9e4f7SAdrian Hunter out_free: 43392a9e4f7SAdrian Hunter free(crp); 43492a9e4f7SAdrian Hunter return NULL; 43592a9e4f7SAdrian Hunter } 43692a9e4f7SAdrian Hunter 43792a9e4f7SAdrian Hunter void call_return_processor__free(struct call_return_processor *crp) 43892a9e4f7SAdrian Hunter { 43992a9e4f7SAdrian Hunter if (crp) { 44092a9e4f7SAdrian Hunter call_path_root__free(crp->cpr); 44192a9e4f7SAdrian Hunter free(crp); 44292a9e4f7SAdrian Hunter } 44392a9e4f7SAdrian Hunter } 44492a9e4f7SAdrian Hunter 44592a9e4f7SAdrian Hunter static int thread_stack__push_cp(struct thread_stack *ts, u64 ret_addr, 44692a9e4f7SAdrian Hunter u64 timestamp, u64 ref, struct call_path *cp, 4472dcde4e1SAdrian Hunter bool no_call, bool trace_end) 44892a9e4f7SAdrian Hunter { 44992a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 45092a9e4f7SAdrian Hunter int err; 45192a9e4f7SAdrian Hunter 45292a9e4f7SAdrian Hunter if (ts->cnt == ts->sz) { 45392a9e4f7SAdrian Hunter err = thread_stack__grow(ts); 45492a9e4f7SAdrian Hunter if (err) 45592a9e4f7SAdrian Hunter return err; 45692a9e4f7SAdrian Hunter } 45792a9e4f7SAdrian Hunter 45892a9e4f7SAdrian Hunter tse = &ts->stack[ts->cnt++]; 45992a9e4f7SAdrian Hunter tse->ret_addr = ret_addr; 46092a9e4f7SAdrian Hunter tse->timestamp = timestamp; 46192a9e4f7SAdrian Hunter tse->ref = ref; 46292a9e4f7SAdrian Hunter tse->branch_count = ts->branch_count; 46392a9e4f7SAdrian Hunter tse->cp = cp; 46492a9e4f7SAdrian Hunter tse->no_call = no_call; 4652dcde4e1SAdrian Hunter tse->trace_end = trace_end; 46692a9e4f7SAdrian Hunter 46792a9e4f7SAdrian Hunter return 0; 46892a9e4f7SAdrian Hunter } 46992a9e4f7SAdrian Hunter 47092a9e4f7SAdrian Hunter static int thread_stack__pop_cp(struct thread *thread, struct thread_stack *ts, 47192a9e4f7SAdrian Hunter u64 ret_addr, u64 timestamp, u64 ref, 47292a9e4f7SAdrian Hunter struct symbol *sym) 47392a9e4f7SAdrian Hunter { 47492a9e4f7SAdrian Hunter int err; 47592a9e4f7SAdrian Hunter 47692a9e4f7SAdrian Hunter if (!ts->cnt) 47792a9e4f7SAdrian Hunter return 1; 47892a9e4f7SAdrian Hunter 47992a9e4f7SAdrian Hunter if (ts->cnt == 1) { 48092a9e4f7SAdrian Hunter struct thread_stack_entry *tse = &ts->stack[0]; 48192a9e4f7SAdrian Hunter 48292a9e4f7SAdrian Hunter if (tse->cp->sym == sym) 48392a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 48492a9e4f7SAdrian Hunter timestamp, ref, false); 48592a9e4f7SAdrian Hunter } 48692a9e4f7SAdrian Hunter 48792a9e4f7SAdrian Hunter if (ts->stack[ts->cnt - 1].ret_addr == ret_addr) { 48892a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 48992a9e4f7SAdrian Hunter timestamp, ref, false); 49092a9e4f7SAdrian Hunter } else { 49192a9e4f7SAdrian Hunter size_t i = ts->cnt - 1; 49292a9e4f7SAdrian Hunter 49392a9e4f7SAdrian Hunter while (i--) { 49492a9e4f7SAdrian Hunter if (ts->stack[i].ret_addr != ret_addr) 49592a9e4f7SAdrian Hunter continue; 49692a9e4f7SAdrian Hunter i += 1; 49792a9e4f7SAdrian Hunter while (ts->cnt > i) { 49892a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, 49992a9e4f7SAdrian Hunter --ts->cnt, 50092a9e4f7SAdrian Hunter timestamp, ref, 50192a9e4f7SAdrian Hunter true); 50292a9e4f7SAdrian Hunter if (err) 50392a9e4f7SAdrian Hunter return err; 50492a9e4f7SAdrian Hunter } 50592a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 50692a9e4f7SAdrian Hunter timestamp, ref, false); 50792a9e4f7SAdrian Hunter } 50892a9e4f7SAdrian Hunter } 50992a9e4f7SAdrian Hunter 51092a9e4f7SAdrian Hunter return 1; 51192a9e4f7SAdrian Hunter } 51292a9e4f7SAdrian Hunter 513e0b89511SAdrian Hunter static int thread_stack__bottom(struct thread_stack *ts, 51492a9e4f7SAdrian Hunter struct perf_sample *sample, 51592a9e4f7SAdrian Hunter struct addr_location *from_al, 51692a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref) 51792a9e4f7SAdrian Hunter { 51892a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 51992a9e4f7SAdrian Hunter struct call_path *cp; 52092a9e4f7SAdrian Hunter struct symbol *sym; 52192a9e4f7SAdrian Hunter u64 ip; 52292a9e4f7SAdrian Hunter 52392a9e4f7SAdrian Hunter if (sample->ip) { 52492a9e4f7SAdrian Hunter ip = sample->ip; 52592a9e4f7SAdrian Hunter sym = from_al->sym; 52692a9e4f7SAdrian Hunter } else if (sample->addr) { 52792a9e4f7SAdrian Hunter ip = sample->addr; 52892a9e4f7SAdrian Hunter sym = to_al->sym; 52992a9e4f7SAdrian Hunter } else { 53092a9e4f7SAdrian Hunter return 0; 53192a9e4f7SAdrian Hunter } 53292a9e4f7SAdrian Hunter 53392a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, &cpr->call_path, sym, ip, 53492a9e4f7SAdrian Hunter ts->kernel_start); 53592a9e4f7SAdrian Hunter if (!cp) 53692a9e4f7SAdrian Hunter return -ENOMEM; 53792a9e4f7SAdrian Hunter 538e0b89511SAdrian Hunter return thread_stack__push_cp(ts, ip, sample->time, ref, cp, 5392dcde4e1SAdrian Hunter true, false); 54092a9e4f7SAdrian Hunter } 54192a9e4f7SAdrian Hunter 54292a9e4f7SAdrian Hunter static int thread_stack__no_call_return(struct thread *thread, 54392a9e4f7SAdrian Hunter struct thread_stack *ts, 54492a9e4f7SAdrian Hunter struct perf_sample *sample, 54592a9e4f7SAdrian Hunter struct addr_location *from_al, 54692a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref) 54792a9e4f7SAdrian Hunter { 54892a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 54992a9e4f7SAdrian Hunter struct call_path *cp, *parent; 55092a9e4f7SAdrian Hunter u64 ks = ts->kernel_start; 55192a9e4f7SAdrian Hunter int err; 55292a9e4f7SAdrian Hunter 55392a9e4f7SAdrian Hunter if (sample->ip >= ks && sample->addr < ks) { 55492a9e4f7SAdrian Hunter /* Return to userspace, so pop all kernel addresses */ 55592a9e4f7SAdrian Hunter while (thread_stack__in_kernel(ts)) { 55692a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 55792a9e4f7SAdrian Hunter sample->time, ref, 55892a9e4f7SAdrian Hunter true); 55992a9e4f7SAdrian Hunter if (err) 56092a9e4f7SAdrian Hunter return err; 56192a9e4f7SAdrian Hunter } 56292a9e4f7SAdrian Hunter 56392a9e4f7SAdrian Hunter /* If the stack is empty, push the userspace address */ 56492a9e4f7SAdrian Hunter if (!ts->cnt) { 56592a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, &cpr->call_path, 56692a9e4f7SAdrian Hunter to_al->sym, sample->addr, 56792a9e4f7SAdrian Hunter ts->kernel_start); 56892a9e4f7SAdrian Hunter if (!cp) 56992a9e4f7SAdrian Hunter return -ENOMEM; 57092a9e4f7SAdrian Hunter return thread_stack__push_cp(ts, 0, sample->time, ref, 5712dcde4e1SAdrian Hunter cp, true, false); 57292a9e4f7SAdrian Hunter } 57392a9e4f7SAdrian Hunter } else if (thread_stack__in_kernel(ts) && sample->ip < ks) { 57492a9e4f7SAdrian Hunter /* Return to userspace, so pop all kernel addresses */ 57592a9e4f7SAdrian Hunter while (thread_stack__in_kernel(ts)) { 57692a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 57792a9e4f7SAdrian Hunter sample->time, ref, 57892a9e4f7SAdrian Hunter true); 57992a9e4f7SAdrian Hunter if (err) 58092a9e4f7SAdrian Hunter return err; 58192a9e4f7SAdrian Hunter } 58292a9e4f7SAdrian Hunter } 58392a9e4f7SAdrian Hunter 58492a9e4f7SAdrian Hunter if (ts->cnt) 58592a9e4f7SAdrian Hunter parent = ts->stack[ts->cnt - 1].cp; 58692a9e4f7SAdrian Hunter else 58792a9e4f7SAdrian Hunter parent = &cpr->call_path; 58892a9e4f7SAdrian Hunter 58992a9e4f7SAdrian Hunter /* This 'return' had no 'call', so push and pop top of stack */ 59092a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, parent, from_al->sym, sample->ip, 59192a9e4f7SAdrian Hunter ts->kernel_start); 59292a9e4f7SAdrian Hunter if (!cp) 59392a9e4f7SAdrian Hunter return -ENOMEM; 59492a9e4f7SAdrian Hunter 59592a9e4f7SAdrian Hunter err = thread_stack__push_cp(ts, sample->addr, sample->time, ref, cp, 5962dcde4e1SAdrian Hunter true, false); 59792a9e4f7SAdrian Hunter if (err) 59892a9e4f7SAdrian Hunter return err; 59992a9e4f7SAdrian Hunter 60092a9e4f7SAdrian Hunter return thread_stack__pop_cp(thread, ts, sample->addr, sample->time, ref, 60192a9e4f7SAdrian Hunter to_al->sym); 60292a9e4f7SAdrian Hunter } 60392a9e4f7SAdrian Hunter 60492a9e4f7SAdrian Hunter static int thread_stack__trace_begin(struct thread *thread, 60592a9e4f7SAdrian Hunter struct thread_stack *ts, u64 timestamp, 60692a9e4f7SAdrian Hunter u64 ref) 60792a9e4f7SAdrian Hunter { 60892a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 60992a9e4f7SAdrian Hunter int err; 61092a9e4f7SAdrian Hunter 61192a9e4f7SAdrian Hunter if (!ts->cnt) 61292a9e4f7SAdrian Hunter return 0; 61392a9e4f7SAdrian Hunter 61492a9e4f7SAdrian Hunter /* Pop trace end */ 61592a9e4f7SAdrian Hunter tse = &ts->stack[ts->cnt - 1]; 6162dcde4e1SAdrian Hunter if (tse->trace_end) { 61792a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 61892a9e4f7SAdrian Hunter timestamp, ref, false); 61992a9e4f7SAdrian Hunter if (err) 62092a9e4f7SAdrian Hunter return err; 62192a9e4f7SAdrian Hunter } 62292a9e4f7SAdrian Hunter 62392a9e4f7SAdrian Hunter return 0; 62492a9e4f7SAdrian Hunter } 62592a9e4f7SAdrian Hunter 62692a9e4f7SAdrian Hunter static int thread_stack__trace_end(struct thread_stack *ts, 62792a9e4f7SAdrian Hunter struct perf_sample *sample, u64 ref) 62892a9e4f7SAdrian Hunter { 62992a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 63092a9e4f7SAdrian Hunter struct call_path *cp; 63192a9e4f7SAdrian Hunter u64 ret_addr; 63292a9e4f7SAdrian Hunter 63392a9e4f7SAdrian Hunter /* No point having 'trace end' on the bottom of the stack */ 63492a9e4f7SAdrian Hunter if (!ts->cnt || (ts->cnt == 1 && ts->stack[0].ref == ref)) 63592a9e4f7SAdrian Hunter return 0; 63692a9e4f7SAdrian Hunter 63792a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, NULL, 0, 63892a9e4f7SAdrian Hunter ts->kernel_start); 63992a9e4f7SAdrian Hunter if (!cp) 64092a9e4f7SAdrian Hunter return -ENOMEM; 64192a9e4f7SAdrian Hunter 64292a9e4f7SAdrian Hunter ret_addr = sample->ip + sample->insn_len; 64392a9e4f7SAdrian Hunter 64492a9e4f7SAdrian Hunter return thread_stack__push_cp(ts, ret_addr, sample->time, ref, cp, 6452dcde4e1SAdrian Hunter false, true); 64692a9e4f7SAdrian Hunter } 64792a9e4f7SAdrian Hunter 64892a9e4f7SAdrian Hunter int thread_stack__process(struct thread *thread, struct comm *comm, 64992a9e4f7SAdrian Hunter struct perf_sample *sample, 65092a9e4f7SAdrian Hunter struct addr_location *from_al, 65192a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref, 65292a9e4f7SAdrian Hunter struct call_return_processor *crp) 65392a9e4f7SAdrian Hunter { 654bd8e68acSAdrian Hunter struct thread_stack *ts = thread__stack(thread); 65592a9e4f7SAdrian Hunter int err = 0; 65692a9e4f7SAdrian Hunter 65703b32cb2SAdrian Hunter if (ts && !ts->crp) { 65892a9e4f7SAdrian Hunter /* Supersede thread_stack__event() */ 659f6060ac6SAdrian Hunter thread_stack__reset(thread, ts); 66003b32cb2SAdrian Hunter ts = NULL; 66192a9e4f7SAdrian Hunter } 66203b32cb2SAdrian Hunter 66303b32cb2SAdrian Hunter if (!ts) { 664bd8e68acSAdrian Hunter ts = thread_stack__new(thread, crp); 665bd8e68acSAdrian Hunter if (!ts) 66692a9e4f7SAdrian Hunter return -ENOMEM; 66792a9e4f7SAdrian Hunter ts->comm = comm; 66892a9e4f7SAdrian Hunter } 66992a9e4f7SAdrian Hunter 67092a9e4f7SAdrian Hunter /* Flush stack on exec */ 67192a9e4f7SAdrian Hunter if (ts->comm != comm && thread->pid_ == thread->tid) { 672a5499b37SAdrian Hunter err = __thread_stack__flush(thread, ts); 67392a9e4f7SAdrian Hunter if (err) 67492a9e4f7SAdrian Hunter return err; 67592a9e4f7SAdrian Hunter ts->comm = comm; 67692a9e4f7SAdrian Hunter } 67792a9e4f7SAdrian Hunter 67892a9e4f7SAdrian Hunter /* If the stack is empty, put the current symbol on the stack */ 67992a9e4f7SAdrian Hunter if (!ts->cnt) { 680e0b89511SAdrian Hunter err = thread_stack__bottom(ts, sample, from_al, to_al, ref); 68192a9e4f7SAdrian Hunter if (err) 68292a9e4f7SAdrian Hunter return err; 68392a9e4f7SAdrian Hunter } 68492a9e4f7SAdrian Hunter 68592a9e4f7SAdrian Hunter ts->branch_count += 1; 68692a9e4f7SAdrian Hunter ts->last_time = sample->time; 68792a9e4f7SAdrian Hunter 68892a9e4f7SAdrian Hunter if (sample->flags & PERF_IP_FLAG_CALL) { 6892dcde4e1SAdrian Hunter bool trace_end = sample->flags & PERF_IP_FLAG_TRACE_END; 69092a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 69192a9e4f7SAdrian Hunter struct call_path *cp; 69292a9e4f7SAdrian Hunter u64 ret_addr; 69392a9e4f7SAdrian Hunter 69492a9e4f7SAdrian Hunter if (!sample->ip || !sample->addr) 69592a9e4f7SAdrian Hunter return 0; 69692a9e4f7SAdrian Hunter 69792a9e4f7SAdrian Hunter ret_addr = sample->ip + sample->insn_len; 69892a9e4f7SAdrian Hunter if (ret_addr == sample->addr) 69992a9e4f7SAdrian Hunter return 0; /* Zero-length calls are excluded */ 70092a9e4f7SAdrian Hunter 70192a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, 70292a9e4f7SAdrian Hunter to_al->sym, sample->addr, 70392a9e4f7SAdrian Hunter ts->kernel_start); 70492a9e4f7SAdrian Hunter if (!cp) 70592a9e4f7SAdrian Hunter return -ENOMEM; 70692a9e4f7SAdrian Hunter err = thread_stack__push_cp(ts, ret_addr, sample->time, ref, 7072dcde4e1SAdrian Hunter cp, false, trace_end); 70892a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_RETURN) { 70992a9e4f7SAdrian Hunter if (!sample->ip || !sample->addr) 71092a9e4f7SAdrian Hunter return 0; 71192a9e4f7SAdrian Hunter 71292a9e4f7SAdrian Hunter err = thread_stack__pop_cp(thread, ts, sample->addr, 71392a9e4f7SAdrian Hunter sample->time, ref, from_al->sym); 71492a9e4f7SAdrian Hunter if (err) { 71592a9e4f7SAdrian Hunter if (err < 0) 71692a9e4f7SAdrian Hunter return err; 71792a9e4f7SAdrian Hunter err = thread_stack__no_call_return(thread, ts, sample, 71892a9e4f7SAdrian Hunter from_al, to_al, ref); 71992a9e4f7SAdrian Hunter } 72092a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_TRACE_BEGIN) { 72192a9e4f7SAdrian Hunter err = thread_stack__trace_begin(thread, ts, sample->time, ref); 72292a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_TRACE_END) { 72392a9e4f7SAdrian Hunter err = thread_stack__trace_end(ts, sample, ref); 72492a9e4f7SAdrian Hunter } 72592a9e4f7SAdrian Hunter 72692a9e4f7SAdrian Hunter return err; 72792a9e4f7SAdrian Hunter } 728e216708dSAdrian Hunter 729e216708dSAdrian Hunter size_t thread_stack__depth(struct thread *thread) 730e216708dSAdrian Hunter { 731bd8e68acSAdrian Hunter struct thread_stack *ts = thread__stack(thread); 732bd8e68acSAdrian Hunter 733bd8e68acSAdrian Hunter if (!ts) 734e216708dSAdrian Hunter return 0; 735bd8e68acSAdrian Hunter return ts->cnt; 736e216708dSAdrian Hunter } 737