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> 1800447ccdSAdrian Hunter #include "thread.h" 1900447ccdSAdrian Hunter #include "event.h" 2092a9e4f7SAdrian Hunter #include "machine.h" 2100447ccdSAdrian Hunter #include "util.h" 2200447ccdSAdrian Hunter #include "debug.h" 2392a9e4f7SAdrian Hunter #include "symbol.h" 2492a9e4f7SAdrian Hunter #include "comm.h" 2500447ccdSAdrian Hunter #include "thread-stack.h" 2600447ccdSAdrian Hunter 2792a9e4f7SAdrian Hunter #define CALL_PATH_BLOCK_SHIFT 8 2892a9e4f7SAdrian Hunter #define CALL_PATH_BLOCK_SIZE (1 << CALL_PATH_BLOCK_SHIFT) 2992a9e4f7SAdrian Hunter #define CALL_PATH_BLOCK_MASK (CALL_PATH_BLOCK_SIZE - 1) 3000447ccdSAdrian Hunter 3192a9e4f7SAdrian Hunter struct call_path_block { 3292a9e4f7SAdrian Hunter struct call_path cp[CALL_PATH_BLOCK_SIZE]; 3392a9e4f7SAdrian Hunter struct list_head node; 3400447ccdSAdrian Hunter }; 3500447ccdSAdrian Hunter 3692a9e4f7SAdrian Hunter /** 3792a9e4f7SAdrian Hunter * struct call_path_root - root of all call paths. 3892a9e4f7SAdrian Hunter * @call_path: root call path 3992a9e4f7SAdrian Hunter * @blocks: list of blocks to store call paths 4092a9e4f7SAdrian Hunter * @next: next free space 4192a9e4f7SAdrian Hunter * @sz: number of spaces 4292a9e4f7SAdrian Hunter */ 4392a9e4f7SAdrian Hunter struct call_path_root { 4492a9e4f7SAdrian Hunter struct call_path call_path; 4592a9e4f7SAdrian Hunter struct list_head blocks; 4692a9e4f7SAdrian Hunter size_t next; 4792a9e4f7SAdrian Hunter size_t sz; 4892a9e4f7SAdrian Hunter }; 4992a9e4f7SAdrian Hunter 5092a9e4f7SAdrian Hunter /** 5192a9e4f7SAdrian Hunter * struct call_return_processor - provides a call-back to consume call-return 5292a9e4f7SAdrian Hunter * information. 5392a9e4f7SAdrian Hunter * @cpr: call path root 5492a9e4f7SAdrian Hunter * @process: call-back that accepts call/return information 5592a9e4f7SAdrian Hunter * @data: anonymous data for call-back 5692a9e4f7SAdrian Hunter */ 5792a9e4f7SAdrian Hunter struct call_return_processor { 5892a9e4f7SAdrian Hunter struct call_path_root *cpr; 5992a9e4f7SAdrian Hunter int (*process)(struct call_return *cr, void *data); 6092a9e4f7SAdrian Hunter void *data; 6192a9e4f7SAdrian Hunter }; 6292a9e4f7SAdrian Hunter 6392a9e4f7SAdrian Hunter #define STACK_GROWTH 2048 6492a9e4f7SAdrian Hunter 6592a9e4f7SAdrian Hunter /** 6692a9e4f7SAdrian Hunter * struct thread_stack_entry - thread stack entry. 6792a9e4f7SAdrian Hunter * @ret_addr: return address 6892a9e4f7SAdrian Hunter * @timestamp: timestamp (if known) 6992a9e4f7SAdrian Hunter * @ref: external reference (e.g. db_id of sample) 7092a9e4f7SAdrian Hunter * @branch_count: the branch count when the entry was created 7192a9e4f7SAdrian Hunter * @cp: call path 7292a9e4f7SAdrian Hunter * @no_call: a 'call' was not seen 7392a9e4f7SAdrian Hunter */ 7492a9e4f7SAdrian Hunter struct thread_stack_entry { 7592a9e4f7SAdrian Hunter u64 ret_addr; 7692a9e4f7SAdrian Hunter u64 timestamp; 7792a9e4f7SAdrian Hunter u64 ref; 7892a9e4f7SAdrian Hunter u64 branch_count; 7992a9e4f7SAdrian Hunter struct call_path *cp; 8092a9e4f7SAdrian Hunter bool no_call; 8192a9e4f7SAdrian Hunter }; 8292a9e4f7SAdrian Hunter 8392a9e4f7SAdrian Hunter /** 8492a9e4f7SAdrian Hunter * struct thread_stack - thread stack constructed from 'call' and 'return' 8592a9e4f7SAdrian Hunter * branch samples. 8692a9e4f7SAdrian Hunter * @stack: array that holds the stack 8792a9e4f7SAdrian Hunter * @cnt: number of entries in the stack 8892a9e4f7SAdrian Hunter * @sz: current maximum stack size 8992a9e4f7SAdrian Hunter * @trace_nr: current trace number 9092a9e4f7SAdrian Hunter * @branch_count: running branch count 9192a9e4f7SAdrian Hunter * @kernel_start: kernel start address 9292a9e4f7SAdrian Hunter * @last_time: last timestamp 9392a9e4f7SAdrian Hunter * @crp: call/return processor 9492a9e4f7SAdrian Hunter * @comm: current comm 9592a9e4f7SAdrian Hunter */ 9600447ccdSAdrian Hunter struct thread_stack { 9700447ccdSAdrian Hunter struct thread_stack_entry *stack; 9800447ccdSAdrian Hunter size_t cnt; 9900447ccdSAdrian Hunter size_t sz; 10000447ccdSAdrian Hunter u64 trace_nr; 10192a9e4f7SAdrian Hunter u64 branch_count; 10292a9e4f7SAdrian Hunter u64 kernel_start; 10392a9e4f7SAdrian Hunter u64 last_time; 10492a9e4f7SAdrian Hunter struct call_return_processor *crp; 10592a9e4f7SAdrian Hunter struct comm *comm; 10600447ccdSAdrian Hunter }; 10700447ccdSAdrian Hunter 10800447ccdSAdrian Hunter static int thread_stack__grow(struct thread_stack *ts) 10900447ccdSAdrian Hunter { 11000447ccdSAdrian Hunter struct thread_stack_entry *new_stack; 11100447ccdSAdrian Hunter size_t sz, new_sz; 11200447ccdSAdrian Hunter 11300447ccdSAdrian Hunter new_sz = ts->sz + STACK_GROWTH; 11400447ccdSAdrian Hunter sz = new_sz * sizeof(struct thread_stack_entry); 11500447ccdSAdrian Hunter 11600447ccdSAdrian Hunter new_stack = realloc(ts->stack, sz); 11700447ccdSAdrian Hunter if (!new_stack) 11800447ccdSAdrian Hunter return -ENOMEM; 11900447ccdSAdrian Hunter 12000447ccdSAdrian Hunter ts->stack = new_stack; 12100447ccdSAdrian Hunter ts->sz = new_sz; 12200447ccdSAdrian Hunter 12300447ccdSAdrian Hunter return 0; 12400447ccdSAdrian Hunter } 12500447ccdSAdrian Hunter 12692a9e4f7SAdrian Hunter static struct thread_stack *thread_stack__new(struct thread *thread, 12792a9e4f7SAdrian Hunter struct call_return_processor *crp) 12800447ccdSAdrian Hunter { 12900447ccdSAdrian Hunter struct thread_stack *ts; 13000447ccdSAdrian Hunter 13100447ccdSAdrian Hunter ts = zalloc(sizeof(struct thread_stack)); 13200447ccdSAdrian Hunter if (!ts) 13300447ccdSAdrian Hunter return NULL; 13400447ccdSAdrian Hunter 13500447ccdSAdrian Hunter if (thread_stack__grow(ts)) { 13600447ccdSAdrian Hunter free(ts); 13700447ccdSAdrian Hunter return NULL; 13800447ccdSAdrian Hunter } 13900447ccdSAdrian Hunter 14092a9e4f7SAdrian Hunter if (thread->mg && thread->mg->machine) 14192a9e4f7SAdrian Hunter ts->kernel_start = machine__kernel_start(thread->mg->machine); 14292a9e4f7SAdrian Hunter else 14392a9e4f7SAdrian Hunter ts->kernel_start = 1ULL << 63; 14492a9e4f7SAdrian Hunter ts->crp = crp; 14592a9e4f7SAdrian Hunter 14600447ccdSAdrian Hunter return ts; 14700447ccdSAdrian Hunter } 14800447ccdSAdrian Hunter 14900447ccdSAdrian Hunter static int thread_stack__push(struct thread_stack *ts, u64 ret_addr) 15000447ccdSAdrian Hunter { 15100447ccdSAdrian Hunter int err = 0; 15200447ccdSAdrian Hunter 15300447ccdSAdrian Hunter if (ts->cnt == ts->sz) { 15400447ccdSAdrian Hunter err = thread_stack__grow(ts); 15500447ccdSAdrian Hunter if (err) { 15600447ccdSAdrian Hunter pr_warning("Out of memory: discarding thread stack\n"); 15700447ccdSAdrian Hunter ts->cnt = 0; 15800447ccdSAdrian Hunter } 15900447ccdSAdrian Hunter } 16000447ccdSAdrian Hunter 16100447ccdSAdrian Hunter ts->stack[ts->cnt++].ret_addr = ret_addr; 16200447ccdSAdrian Hunter 16300447ccdSAdrian Hunter return err; 16400447ccdSAdrian Hunter } 16500447ccdSAdrian Hunter 16600447ccdSAdrian Hunter static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr) 16700447ccdSAdrian Hunter { 16800447ccdSAdrian Hunter size_t i; 16900447ccdSAdrian Hunter 17000447ccdSAdrian Hunter /* 17100447ccdSAdrian Hunter * In some cases there may be functions which are not seen to return. 17200447ccdSAdrian Hunter * For example when setjmp / longjmp has been used. Or the perf context 17300447ccdSAdrian Hunter * switch in the kernel which doesn't stop and start tracing in exactly 17400447ccdSAdrian Hunter * the same code path. When that happens the return address will be 17500447ccdSAdrian Hunter * further down the stack. If the return address is not found at all, 17600447ccdSAdrian Hunter * we assume the opposite (i.e. this is a return for a call that wasn't 17700447ccdSAdrian Hunter * seen for some reason) and leave the stack alone. 17800447ccdSAdrian Hunter */ 17900447ccdSAdrian Hunter for (i = ts->cnt; i; ) { 18000447ccdSAdrian Hunter if (ts->stack[--i].ret_addr == ret_addr) { 18100447ccdSAdrian Hunter ts->cnt = i; 18200447ccdSAdrian Hunter return; 18300447ccdSAdrian Hunter } 18400447ccdSAdrian Hunter } 18500447ccdSAdrian Hunter } 18600447ccdSAdrian Hunter 18792a9e4f7SAdrian Hunter static bool thread_stack__in_kernel(struct thread_stack *ts) 18892a9e4f7SAdrian Hunter { 18992a9e4f7SAdrian Hunter if (!ts->cnt) 19092a9e4f7SAdrian Hunter return false; 19192a9e4f7SAdrian Hunter 19292a9e4f7SAdrian Hunter return ts->stack[ts->cnt - 1].cp->in_kernel; 19392a9e4f7SAdrian Hunter } 19492a9e4f7SAdrian Hunter 19592a9e4f7SAdrian Hunter static int thread_stack__call_return(struct thread *thread, 19692a9e4f7SAdrian Hunter struct thread_stack *ts, size_t idx, 19792a9e4f7SAdrian Hunter u64 timestamp, u64 ref, bool no_return) 19892a9e4f7SAdrian Hunter { 19992a9e4f7SAdrian Hunter struct call_return_processor *crp = ts->crp; 20092a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 20192a9e4f7SAdrian Hunter struct call_return cr = { 20292a9e4f7SAdrian Hunter .thread = thread, 20392a9e4f7SAdrian Hunter .comm = ts->comm, 20492a9e4f7SAdrian Hunter .db_id = 0, 20592a9e4f7SAdrian Hunter }; 20692a9e4f7SAdrian Hunter 20792a9e4f7SAdrian Hunter tse = &ts->stack[idx]; 20892a9e4f7SAdrian Hunter cr.cp = tse->cp; 20992a9e4f7SAdrian Hunter cr.call_time = tse->timestamp; 21092a9e4f7SAdrian Hunter cr.return_time = timestamp; 21192a9e4f7SAdrian Hunter cr.branch_count = ts->branch_count - tse->branch_count; 21292a9e4f7SAdrian Hunter cr.call_ref = tse->ref; 21392a9e4f7SAdrian Hunter cr.return_ref = ref; 21492a9e4f7SAdrian Hunter if (tse->no_call) 21592a9e4f7SAdrian Hunter cr.flags |= CALL_RETURN_NO_CALL; 21692a9e4f7SAdrian Hunter if (no_return) 21792a9e4f7SAdrian Hunter cr.flags |= CALL_RETURN_NO_RETURN; 21892a9e4f7SAdrian Hunter 21992a9e4f7SAdrian Hunter return crp->process(&cr, crp->data); 22092a9e4f7SAdrian Hunter } 22192a9e4f7SAdrian Hunter 22292a9e4f7SAdrian Hunter static int thread_stack__flush(struct thread *thread, struct thread_stack *ts) 22392a9e4f7SAdrian Hunter { 22492a9e4f7SAdrian Hunter struct call_return_processor *crp = ts->crp; 22592a9e4f7SAdrian Hunter int err; 22692a9e4f7SAdrian Hunter 22792a9e4f7SAdrian Hunter if (!crp) { 22892a9e4f7SAdrian Hunter ts->cnt = 0; 22992a9e4f7SAdrian Hunter return 0; 23092a9e4f7SAdrian Hunter } 23192a9e4f7SAdrian Hunter 23292a9e4f7SAdrian Hunter while (ts->cnt) { 23392a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 23492a9e4f7SAdrian Hunter ts->last_time, 0, true); 23592a9e4f7SAdrian Hunter if (err) { 23692a9e4f7SAdrian Hunter pr_err("Error flushing thread stack!\n"); 23792a9e4f7SAdrian Hunter ts->cnt = 0; 23892a9e4f7SAdrian Hunter return err; 23992a9e4f7SAdrian Hunter } 24092a9e4f7SAdrian Hunter } 24192a9e4f7SAdrian Hunter 24292a9e4f7SAdrian Hunter return 0; 24392a9e4f7SAdrian Hunter } 24492a9e4f7SAdrian Hunter 24500447ccdSAdrian Hunter int thread_stack__event(struct thread *thread, u32 flags, u64 from_ip, 24600447ccdSAdrian Hunter u64 to_ip, u16 insn_len, u64 trace_nr) 24700447ccdSAdrian Hunter { 24800447ccdSAdrian Hunter if (!thread) 24900447ccdSAdrian Hunter return -EINVAL; 25000447ccdSAdrian Hunter 25100447ccdSAdrian Hunter if (!thread->ts) { 25292a9e4f7SAdrian Hunter thread->ts = thread_stack__new(thread, NULL); 25300447ccdSAdrian Hunter if (!thread->ts) { 25400447ccdSAdrian Hunter pr_warning("Out of memory: no thread stack\n"); 25500447ccdSAdrian Hunter return -ENOMEM; 25600447ccdSAdrian Hunter } 25700447ccdSAdrian Hunter thread->ts->trace_nr = trace_nr; 25800447ccdSAdrian Hunter } 25900447ccdSAdrian Hunter 26000447ccdSAdrian Hunter /* 26100447ccdSAdrian Hunter * When the trace is discontinuous, the trace_nr changes. In that case 26200447ccdSAdrian Hunter * the stack might be completely invalid. Better to report nothing than 26392a9e4f7SAdrian Hunter * to report something misleading, so flush the stack. 26400447ccdSAdrian Hunter */ 26500447ccdSAdrian Hunter if (trace_nr != thread->ts->trace_nr) { 26692a9e4f7SAdrian Hunter if (thread->ts->trace_nr) 26792a9e4f7SAdrian Hunter thread_stack__flush(thread, thread->ts); 26800447ccdSAdrian Hunter thread->ts->trace_nr = trace_nr; 26900447ccdSAdrian Hunter } 27000447ccdSAdrian Hunter 27192a9e4f7SAdrian Hunter /* Stop here if thread_stack__process() is in use */ 27292a9e4f7SAdrian Hunter if (thread->ts->crp) 27392a9e4f7SAdrian Hunter return 0; 27492a9e4f7SAdrian Hunter 27500447ccdSAdrian Hunter if (flags & PERF_IP_FLAG_CALL) { 27600447ccdSAdrian Hunter u64 ret_addr; 27700447ccdSAdrian Hunter 27800447ccdSAdrian Hunter if (!to_ip) 27900447ccdSAdrian Hunter return 0; 28000447ccdSAdrian Hunter ret_addr = from_ip + insn_len; 28100447ccdSAdrian Hunter if (ret_addr == to_ip) 28200447ccdSAdrian Hunter return 0; /* Zero-length calls are excluded */ 28300447ccdSAdrian Hunter return thread_stack__push(thread->ts, ret_addr); 28400447ccdSAdrian Hunter } else if (flags & PERF_IP_FLAG_RETURN) { 28500447ccdSAdrian Hunter if (!from_ip) 28600447ccdSAdrian Hunter return 0; 28700447ccdSAdrian Hunter thread_stack__pop(thread->ts, to_ip); 28800447ccdSAdrian Hunter } 28900447ccdSAdrian Hunter 29000447ccdSAdrian Hunter return 0; 29100447ccdSAdrian Hunter } 29200447ccdSAdrian Hunter 29392a9e4f7SAdrian Hunter void thread_stack__set_trace_nr(struct thread *thread, u64 trace_nr) 29492a9e4f7SAdrian Hunter { 29592a9e4f7SAdrian Hunter if (!thread || !thread->ts) 29692a9e4f7SAdrian Hunter return; 29792a9e4f7SAdrian Hunter 29892a9e4f7SAdrian Hunter if (trace_nr != thread->ts->trace_nr) { 29992a9e4f7SAdrian Hunter if (thread->ts->trace_nr) 30092a9e4f7SAdrian Hunter thread_stack__flush(thread, thread->ts); 30192a9e4f7SAdrian Hunter thread->ts->trace_nr = trace_nr; 30292a9e4f7SAdrian Hunter } 30392a9e4f7SAdrian Hunter } 30492a9e4f7SAdrian Hunter 30500447ccdSAdrian Hunter void thread_stack__free(struct thread *thread) 30600447ccdSAdrian Hunter { 30700447ccdSAdrian Hunter if (thread->ts) { 30892a9e4f7SAdrian Hunter thread_stack__flush(thread, thread->ts); 30900447ccdSAdrian Hunter zfree(&thread->ts->stack); 31000447ccdSAdrian Hunter zfree(&thread->ts); 31100447ccdSAdrian Hunter } 31200447ccdSAdrian Hunter } 31300447ccdSAdrian Hunter 31400447ccdSAdrian Hunter void thread_stack__sample(struct thread *thread, struct ip_callchain *chain, 31500447ccdSAdrian Hunter size_t sz, u64 ip) 31600447ccdSAdrian Hunter { 31700447ccdSAdrian Hunter size_t i; 31800447ccdSAdrian Hunter 31900447ccdSAdrian Hunter if (!thread || !thread->ts) 32000447ccdSAdrian Hunter chain->nr = 1; 32100447ccdSAdrian Hunter else 32200447ccdSAdrian Hunter chain->nr = min(sz, thread->ts->cnt + 1); 32300447ccdSAdrian Hunter 32400447ccdSAdrian Hunter chain->ips[0] = ip; 32500447ccdSAdrian Hunter 32600447ccdSAdrian Hunter for (i = 1; i < chain->nr; i++) 32700447ccdSAdrian Hunter chain->ips[i] = thread->ts->stack[thread->ts->cnt - i].ret_addr; 32800447ccdSAdrian Hunter } 32992a9e4f7SAdrian Hunter 33092a9e4f7SAdrian Hunter static void call_path__init(struct call_path *cp, struct call_path *parent, 33192a9e4f7SAdrian Hunter struct symbol *sym, u64 ip, bool in_kernel) 33292a9e4f7SAdrian Hunter { 33392a9e4f7SAdrian Hunter cp->parent = parent; 33492a9e4f7SAdrian Hunter cp->sym = sym; 33592a9e4f7SAdrian Hunter cp->ip = sym ? 0 : ip; 33692a9e4f7SAdrian Hunter cp->db_id = 0; 33792a9e4f7SAdrian Hunter cp->in_kernel = in_kernel; 33892a9e4f7SAdrian Hunter RB_CLEAR_NODE(&cp->rb_node); 33992a9e4f7SAdrian Hunter cp->children = RB_ROOT; 34092a9e4f7SAdrian Hunter } 34192a9e4f7SAdrian Hunter 34292a9e4f7SAdrian Hunter static struct call_path_root *call_path_root__new(void) 34392a9e4f7SAdrian Hunter { 34492a9e4f7SAdrian Hunter struct call_path_root *cpr; 34592a9e4f7SAdrian Hunter 34692a9e4f7SAdrian Hunter cpr = zalloc(sizeof(struct call_path_root)); 34792a9e4f7SAdrian Hunter if (!cpr) 34892a9e4f7SAdrian Hunter return NULL; 34992a9e4f7SAdrian Hunter call_path__init(&cpr->call_path, NULL, NULL, 0, false); 35092a9e4f7SAdrian Hunter INIT_LIST_HEAD(&cpr->blocks); 35192a9e4f7SAdrian Hunter return cpr; 35292a9e4f7SAdrian Hunter } 35392a9e4f7SAdrian Hunter 35492a9e4f7SAdrian Hunter static void call_path_root__free(struct call_path_root *cpr) 35592a9e4f7SAdrian Hunter { 35692a9e4f7SAdrian Hunter struct call_path_block *pos, *n; 35792a9e4f7SAdrian Hunter 35892a9e4f7SAdrian Hunter list_for_each_entry_safe(pos, n, &cpr->blocks, node) { 35992a9e4f7SAdrian Hunter list_del(&pos->node); 36092a9e4f7SAdrian Hunter free(pos); 36192a9e4f7SAdrian Hunter } 36292a9e4f7SAdrian Hunter free(cpr); 36392a9e4f7SAdrian Hunter } 36492a9e4f7SAdrian Hunter 36592a9e4f7SAdrian Hunter static struct call_path *call_path__new(struct call_path_root *cpr, 36692a9e4f7SAdrian Hunter struct call_path *parent, 36792a9e4f7SAdrian Hunter struct symbol *sym, u64 ip, 36892a9e4f7SAdrian Hunter bool in_kernel) 36992a9e4f7SAdrian Hunter { 37092a9e4f7SAdrian Hunter struct call_path_block *cpb; 37192a9e4f7SAdrian Hunter struct call_path *cp; 37292a9e4f7SAdrian Hunter size_t n; 37392a9e4f7SAdrian Hunter 37492a9e4f7SAdrian Hunter if (cpr->next < cpr->sz) { 37592a9e4f7SAdrian Hunter cpb = list_last_entry(&cpr->blocks, struct call_path_block, 37692a9e4f7SAdrian Hunter node); 37792a9e4f7SAdrian Hunter } else { 37892a9e4f7SAdrian Hunter cpb = zalloc(sizeof(struct call_path_block)); 37992a9e4f7SAdrian Hunter if (!cpb) 38092a9e4f7SAdrian Hunter return NULL; 38192a9e4f7SAdrian Hunter list_add_tail(&cpb->node, &cpr->blocks); 38292a9e4f7SAdrian Hunter cpr->sz += CALL_PATH_BLOCK_SIZE; 38392a9e4f7SAdrian Hunter } 38492a9e4f7SAdrian Hunter 38592a9e4f7SAdrian Hunter n = cpr->next++ & CALL_PATH_BLOCK_MASK; 38692a9e4f7SAdrian Hunter cp = &cpb->cp[n]; 38792a9e4f7SAdrian Hunter 38892a9e4f7SAdrian Hunter call_path__init(cp, parent, sym, ip, in_kernel); 38992a9e4f7SAdrian Hunter 39092a9e4f7SAdrian Hunter return cp; 39192a9e4f7SAdrian Hunter } 39292a9e4f7SAdrian Hunter 39392a9e4f7SAdrian Hunter static struct call_path *call_path__findnew(struct call_path_root *cpr, 39492a9e4f7SAdrian Hunter struct call_path *parent, 39592a9e4f7SAdrian Hunter struct symbol *sym, u64 ip, u64 ks) 39692a9e4f7SAdrian Hunter { 39792a9e4f7SAdrian Hunter struct rb_node **p; 39892a9e4f7SAdrian Hunter struct rb_node *node_parent = NULL; 39992a9e4f7SAdrian Hunter struct call_path *cp; 40092a9e4f7SAdrian Hunter bool in_kernel = ip >= ks; 40192a9e4f7SAdrian Hunter 40292a9e4f7SAdrian Hunter if (sym) 40392a9e4f7SAdrian Hunter ip = 0; 40492a9e4f7SAdrian Hunter 40592a9e4f7SAdrian Hunter if (!parent) 40692a9e4f7SAdrian Hunter return call_path__new(cpr, parent, sym, ip, in_kernel); 40792a9e4f7SAdrian Hunter 40892a9e4f7SAdrian Hunter p = &parent->children.rb_node; 40992a9e4f7SAdrian Hunter while (*p != NULL) { 41092a9e4f7SAdrian Hunter node_parent = *p; 41192a9e4f7SAdrian Hunter cp = rb_entry(node_parent, struct call_path, rb_node); 41292a9e4f7SAdrian Hunter 41392a9e4f7SAdrian Hunter if (cp->sym == sym && cp->ip == ip) 41492a9e4f7SAdrian Hunter return cp; 41592a9e4f7SAdrian Hunter 41692a9e4f7SAdrian Hunter if (sym < cp->sym || (sym == cp->sym && ip < cp->ip)) 41792a9e4f7SAdrian Hunter p = &(*p)->rb_left; 41892a9e4f7SAdrian Hunter else 41992a9e4f7SAdrian Hunter p = &(*p)->rb_right; 42092a9e4f7SAdrian Hunter } 42192a9e4f7SAdrian Hunter 42292a9e4f7SAdrian Hunter cp = call_path__new(cpr, parent, sym, ip, in_kernel); 42392a9e4f7SAdrian Hunter if (!cp) 42492a9e4f7SAdrian Hunter return NULL; 42592a9e4f7SAdrian Hunter 42692a9e4f7SAdrian Hunter rb_link_node(&cp->rb_node, node_parent, p); 42792a9e4f7SAdrian Hunter rb_insert_color(&cp->rb_node, &parent->children); 42892a9e4f7SAdrian Hunter 42992a9e4f7SAdrian Hunter return cp; 43092a9e4f7SAdrian Hunter } 43192a9e4f7SAdrian Hunter 43292a9e4f7SAdrian Hunter struct call_return_processor * 43392a9e4f7SAdrian Hunter call_return_processor__new(int (*process)(struct call_return *cr, void *data), 43492a9e4f7SAdrian Hunter void *data) 43592a9e4f7SAdrian Hunter { 43692a9e4f7SAdrian Hunter struct call_return_processor *crp; 43792a9e4f7SAdrian Hunter 43892a9e4f7SAdrian Hunter crp = zalloc(sizeof(struct call_return_processor)); 43992a9e4f7SAdrian Hunter if (!crp) 44092a9e4f7SAdrian Hunter return NULL; 44192a9e4f7SAdrian Hunter crp->cpr = call_path_root__new(); 44292a9e4f7SAdrian Hunter if (!crp->cpr) 44392a9e4f7SAdrian Hunter goto out_free; 44492a9e4f7SAdrian Hunter crp->process = process; 44592a9e4f7SAdrian Hunter crp->data = data; 44692a9e4f7SAdrian Hunter return crp; 44792a9e4f7SAdrian Hunter 44892a9e4f7SAdrian Hunter out_free: 44992a9e4f7SAdrian Hunter free(crp); 45092a9e4f7SAdrian Hunter return NULL; 45192a9e4f7SAdrian Hunter } 45292a9e4f7SAdrian Hunter 45392a9e4f7SAdrian Hunter void call_return_processor__free(struct call_return_processor *crp) 45492a9e4f7SAdrian Hunter { 45592a9e4f7SAdrian Hunter if (crp) { 45692a9e4f7SAdrian Hunter call_path_root__free(crp->cpr); 45792a9e4f7SAdrian Hunter free(crp); 45892a9e4f7SAdrian Hunter } 45992a9e4f7SAdrian Hunter } 46092a9e4f7SAdrian Hunter 46192a9e4f7SAdrian Hunter static int thread_stack__push_cp(struct thread_stack *ts, u64 ret_addr, 46292a9e4f7SAdrian Hunter u64 timestamp, u64 ref, struct call_path *cp, 46392a9e4f7SAdrian Hunter bool no_call) 46492a9e4f7SAdrian Hunter { 46592a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 46692a9e4f7SAdrian Hunter int err; 46792a9e4f7SAdrian Hunter 46892a9e4f7SAdrian Hunter if (ts->cnt == ts->sz) { 46992a9e4f7SAdrian Hunter err = thread_stack__grow(ts); 47092a9e4f7SAdrian Hunter if (err) 47192a9e4f7SAdrian Hunter return err; 47292a9e4f7SAdrian Hunter } 47392a9e4f7SAdrian Hunter 47492a9e4f7SAdrian Hunter tse = &ts->stack[ts->cnt++]; 47592a9e4f7SAdrian Hunter tse->ret_addr = ret_addr; 47692a9e4f7SAdrian Hunter tse->timestamp = timestamp; 47792a9e4f7SAdrian Hunter tse->ref = ref; 47892a9e4f7SAdrian Hunter tse->branch_count = ts->branch_count; 47992a9e4f7SAdrian Hunter tse->cp = cp; 48092a9e4f7SAdrian Hunter tse->no_call = no_call; 48192a9e4f7SAdrian Hunter 48292a9e4f7SAdrian Hunter return 0; 48392a9e4f7SAdrian Hunter } 48492a9e4f7SAdrian Hunter 48592a9e4f7SAdrian Hunter static int thread_stack__pop_cp(struct thread *thread, struct thread_stack *ts, 48692a9e4f7SAdrian Hunter u64 ret_addr, u64 timestamp, u64 ref, 48792a9e4f7SAdrian Hunter struct symbol *sym) 48892a9e4f7SAdrian Hunter { 48992a9e4f7SAdrian Hunter int err; 49092a9e4f7SAdrian Hunter 49192a9e4f7SAdrian Hunter if (!ts->cnt) 49292a9e4f7SAdrian Hunter return 1; 49392a9e4f7SAdrian Hunter 49492a9e4f7SAdrian Hunter if (ts->cnt == 1) { 49592a9e4f7SAdrian Hunter struct thread_stack_entry *tse = &ts->stack[0]; 49692a9e4f7SAdrian Hunter 49792a9e4f7SAdrian Hunter if (tse->cp->sym == sym) 49892a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 49992a9e4f7SAdrian Hunter timestamp, ref, false); 50092a9e4f7SAdrian Hunter } 50192a9e4f7SAdrian Hunter 50292a9e4f7SAdrian Hunter if (ts->stack[ts->cnt - 1].ret_addr == ret_addr) { 50392a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 50492a9e4f7SAdrian Hunter timestamp, ref, false); 50592a9e4f7SAdrian Hunter } else { 50692a9e4f7SAdrian Hunter size_t i = ts->cnt - 1; 50792a9e4f7SAdrian Hunter 50892a9e4f7SAdrian Hunter while (i--) { 50992a9e4f7SAdrian Hunter if (ts->stack[i].ret_addr != ret_addr) 51092a9e4f7SAdrian Hunter continue; 51192a9e4f7SAdrian Hunter i += 1; 51292a9e4f7SAdrian Hunter while (ts->cnt > i) { 51392a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, 51492a9e4f7SAdrian Hunter --ts->cnt, 51592a9e4f7SAdrian Hunter timestamp, ref, 51692a9e4f7SAdrian Hunter true); 51792a9e4f7SAdrian Hunter if (err) 51892a9e4f7SAdrian Hunter return err; 51992a9e4f7SAdrian Hunter } 52092a9e4f7SAdrian Hunter return thread_stack__call_return(thread, ts, --ts->cnt, 52192a9e4f7SAdrian Hunter timestamp, ref, false); 52292a9e4f7SAdrian Hunter } 52392a9e4f7SAdrian Hunter } 52492a9e4f7SAdrian Hunter 52592a9e4f7SAdrian Hunter return 1; 52692a9e4f7SAdrian Hunter } 52792a9e4f7SAdrian Hunter 52892a9e4f7SAdrian Hunter static int thread_stack__bottom(struct thread *thread, struct thread_stack *ts, 52992a9e4f7SAdrian Hunter struct perf_sample *sample, 53092a9e4f7SAdrian Hunter struct addr_location *from_al, 53192a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref) 53292a9e4f7SAdrian Hunter { 53392a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 53492a9e4f7SAdrian Hunter struct call_path *cp; 53592a9e4f7SAdrian Hunter struct symbol *sym; 53692a9e4f7SAdrian Hunter u64 ip; 53792a9e4f7SAdrian Hunter 53892a9e4f7SAdrian Hunter if (sample->ip) { 53992a9e4f7SAdrian Hunter ip = sample->ip; 54092a9e4f7SAdrian Hunter sym = from_al->sym; 54192a9e4f7SAdrian Hunter } else if (sample->addr) { 54292a9e4f7SAdrian Hunter ip = sample->addr; 54392a9e4f7SAdrian Hunter sym = to_al->sym; 54492a9e4f7SAdrian Hunter } else { 54592a9e4f7SAdrian Hunter return 0; 54692a9e4f7SAdrian Hunter } 54792a9e4f7SAdrian Hunter 54892a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, &cpr->call_path, sym, ip, 54992a9e4f7SAdrian Hunter ts->kernel_start); 55092a9e4f7SAdrian Hunter if (!cp) 55192a9e4f7SAdrian Hunter return -ENOMEM; 55292a9e4f7SAdrian Hunter 55392a9e4f7SAdrian Hunter return thread_stack__push_cp(thread->ts, ip, sample->time, ref, cp, 55492a9e4f7SAdrian Hunter true); 55592a9e4f7SAdrian Hunter } 55692a9e4f7SAdrian Hunter 55792a9e4f7SAdrian Hunter static int thread_stack__no_call_return(struct thread *thread, 55892a9e4f7SAdrian Hunter struct thread_stack *ts, 55992a9e4f7SAdrian Hunter struct perf_sample *sample, 56092a9e4f7SAdrian Hunter struct addr_location *from_al, 56192a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref) 56292a9e4f7SAdrian Hunter { 56392a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 56492a9e4f7SAdrian Hunter struct call_path *cp, *parent; 56592a9e4f7SAdrian Hunter u64 ks = ts->kernel_start; 56692a9e4f7SAdrian Hunter int err; 56792a9e4f7SAdrian Hunter 56892a9e4f7SAdrian Hunter if (sample->ip >= ks && sample->addr < ks) { 56992a9e4f7SAdrian Hunter /* Return to userspace, so pop all kernel addresses */ 57092a9e4f7SAdrian Hunter while (thread_stack__in_kernel(ts)) { 57192a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 57292a9e4f7SAdrian Hunter sample->time, ref, 57392a9e4f7SAdrian Hunter true); 57492a9e4f7SAdrian Hunter if (err) 57592a9e4f7SAdrian Hunter return err; 57692a9e4f7SAdrian Hunter } 57792a9e4f7SAdrian Hunter 57892a9e4f7SAdrian Hunter /* If the stack is empty, push the userspace address */ 57992a9e4f7SAdrian Hunter if (!ts->cnt) { 58092a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, &cpr->call_path, 58192a9e4f7SAdrian Hunter to_al->sym, sample->addr, 58292a9e4f7SAdrian Hunter ts->kernel_start); 58392a9e4f7SAdrian Hunter if (!cp) 58492a9e4f7SAdrian Hunter return -ENOMEM; 58592a9e4f7SAdrian Hunter return thread_stack__push_cp(ts, 0, sample->time, ref, 58692a9e4f7SAdrian Hunter cp, true); 58792a9e4f7SAdrian Hunter } 58892a9e4f7SAdrian Hunter } else if (thread_stack__in_kernel(ts) && sample->ip < ks) { 58992a9e4f7SAdrian Hunter /* Return to userspace, so pop all kernel addresses */ 59092a9e4f7SAdrian Hunter while (thread_stack__in_kernel(ts)) { 59192a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 59292a9e4f7SAdrian Hunter sample->time, ref, 59392a9e4f7SAdrian Hunter true); 59492a9e4f7SAdrian Hunter if (err) 59592a9e4f7SAdrian Hunter return err; 59692a9e4f7SAdrian Hunter } 59792a9e4f7SAdrian Hunter } 59892a9e4f7SAdrian Hunter 59992a9e4f7SAdrian Hunter if (ts->cnt) 60092a9e4f7SAdrian Hunter parent = ts->stack[ts->cnt - 1].cp; 60192a9e4f7SAdrian Hunter else 60292a9e4f7SAdrian Hunter parent = &cpr->call_path; 60392a9e4f7SAdrian Hunter 60492a9e4f7SAdrian Hunter /* This 'return' had no 'call', so push and pop top of stack */ 60592a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, parent, from_al->sym, sample->ip, 60692a9e4f7SAdrian Hunter ts->kernel_start); 60792a9e4f7SAdrian Hunter if (!cp) 60892a9e4f7SAdrian Hunter return -ENOMEM; 60992a9e4f7SAdrian Hunter 61092a9e4f7SAdrian Hunter err = thread_stack__push_cp(ts, sample->addr, sample->time, ref, cp, 61192a9e4f7SAdrian Hunter true); 61292a9e4f7SAdrian Hunter if (err) 61392a9e4f7SAdrian Hunter return err; 61492a9e4f7SAdrian Hunter 61592a9e4f7SAdrian Hunter return thread_stack__pop_cp(thread, ts, sample->addr, sample->time, ref, 61692a9e4f7SAdrian Hunter to_al->sym); 61792a9e4f7SAdrian Hunter } 61892a9e4f7SAdrian Hunter 61992a9e4f7SAdrian Hunter static int thread_stack__trace_begin(struct thread *thread, 62092a9e4f7SAdrian Hunter struct thread_stack *ts, u64 timestamp, 62192a9e4f7SAdrian Hunter u64 ref) 62292a9e4f7SAdrian Hunter { 62392a9e4f7SAdrian Hunter struct thread_stack_entry *tse; 62492a9e4f7SAdrian Hunter int err; 62592a9e4f7SAdrian Hunter 62692a9e4f7SAdrian Hunter if (!ts->cnt) 62792a9e4f7SAdrian Hunter return 0; 62892a9e4f7SAdrian Hunter 62992a9e4f7SAdrian Hunter /* Pop trace end */ 63092a9e4f7SAdrian Hunter tse = &ts->stack[ts->cnt - 1]; 63192a9e4f7SAdrian Hunter if (tse->cp->sym == NULL && tse->cp->ip == 0) { 63292a9e4f7SAdrian Hunter err = thread_stack__call_return(thread, ts, --ts->cnt, 63392a9e4f7SAdrian Hunter timestamp, ref, false); 63492a9e4f7SAdrian Hunter if (err) 63592a9e4f7SAdrian Hunter return err; 63692a9e4f7SAdrian Hunter } 63792a9e4f7SAdrian Hunter 63892a9e4f7SAdrian Hunter return 0; 63992a9e4f7SAdrian Hunter } 64092a9e4f7SAdrian Hunter 64192a9e4f7SAdrian Hunter static int thread_stack__trace_end(struct thread_stack *ts, 64292a9e4f7SAdrian Hunter struct perf_sample *sample, u64 ref) 64392a9e4f7SAdrian Hunter { 64492a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 64592a9e4f7SAdrian Hunter struct call_path *cp; 64692a9e4f7SAdrian Hunter u64 ret_addr; 64792a9e4f7SAdrian Hunter 64892a9e4f7SAdrian Hunter /* No point having 'trace end' on the bottom of the stack */ 64992a9e4f7SAdrian Hunter if (!ts->cnt || (ts->cnt == 1 && ts->stack[0].ref == ref)) 65092a9e4f7SAdrian Hunter return 0; 65192a9e4f7SAdrian Hunter 65292a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, NULL, 0, 65392a9e4f7SAdrian Hunter ts->kernel_start); 65492a9e4f7SAdrian Hunter if (!cp) 65592a9e4f7SAdrian Hunter return -ENOMEM; 65692a9e4f7SAdrian Hunter 65792a9e4f7SAdrian Hunter ret_addr = sample->ip + sample->insn_len; 65892a9e4f7SAdrian Hunter 65992a9e4f7SAdrian Hunter return thread_stack__push_cp(ts, ret_addr, sample->time, ref, cp, 66092a9e4f7SAdrian Hunter false); 66192a9e4f7SAdrian Hunter } 66292a9e4f7SAdrian Hunter 66392a9e4f7SAdrian Hunter int thread_stack__process(struct thread *thread, struct comm *comm, 66492a9e4f7SAdrian Hunter struct perf_sample *sample, 66592a9e4f7SAdrian Hunter struct addr_location *from_al, 66692a9e4f7SAdrian Hunter struct addr_location *to_al, u64 ref, 66792a9e4f7SAdrian Hunter struct call_return_processor *crp) 66892a9e4f7SAdrian Hunter { 66992a9e4f7SAdrian Hunter struct thread_stack *ts = thread->ts; 67092a9e4f7SAdrian Hunter int err = 0; 67192a9e4f7SAdrian Hunter 67292a9e4f7SAdrian Hunter if (ts) { 67392a9e4f7SAdrian Hunter if (!ts->crp) { 67492a9e4f7SAdrian Hunter /* Supersede thread_stack__event() */ 67592a9e4f7SAdrian Hunter thread_stack__free(thread); 67692a9e4f7SAdrian Hunter thread->ts = thread_stack__new(thread, crp); 67792a9e4f7SAdrian Hunter if (!thread->ts) 67892a9e4f7SAdrian Hunter return -ENOMEM; 67992a9e4f7SAdrian Hunter ts = thread->ts; 68092a9e4f7SAdrian Hunter ts->comm = comm; 68192a9e4f7SAdrian Hunter } 68292a9e4f7SAdrian Hunter } else { 68392a9e4f7SAdrian Hunter thread->ts = thread_stack__new(thread, crp); 68492a9e4f7SAdrian Hunter if (!thread->ts) 68592a9e4f7SAdrian Hunter return -ENOMEM; 68692a9e4f7SAdrian Hunter ts = thread->ts; 68792a9e4f7SAdrian Hunter ts->comm = comm; 68892a9e4f7SAdrian Hunter } 68992a9e4f7SAdrian Hunter 69092a9e4f7SAdrian Hunter /* Flush stack on exec */ 69192a9e4f7SAdrian Hunter if (ts->comm != comm && thread->pid_ == thread->tid) { 69292a9e4f7SAdrian Hunter err = thread_stack__flush(thread, ts); 69392a9e4f7SAdrian Hunter if (err) 69492a9e4f7SAdrian Hunter return err; 69592a9e4f7SAdrian Hunter ts->comm = comm; 69692a9e4f7SAdrian Hunter } 69792a9e4f7SAdrian Hunter 69892a9e4f7SAdrian Hunter /* If the stack is empty, put the current symbol on the stack */ 69992a9e4f7SAdrian Hunter if (!ts->cnt) { 70092a9e4f7SAdrian Hunter err = thread_stack__bottom(thread, ts, sample, from_al, to_al, 70192a9e4f7SAdrian Hunter ref); 70292a9e4f7SAdrian Hunter if (err) 70392a9e4f7SAdrian Hunter return err; 70492a9e4f7SAdrian Hunter } 70592a9e4f7SAdrian Hunter 70692a9e4f7SAdrian Hunter ts->branch_count += 1; 70792a9e4f7SAdrian Hunter ts->last_time = sample->time; 70892a9e4f7SAdrian Hunter 70992a9e4f7SAdrian Hunter if (sample->flags & PERF_IP_FLAG_CALL) { 71092a9e4f7SAdrian Hunter struct call_path_root *cpr = ts->crp->cpr; 71192a9e4f7SAdrian Hunter struct call_path *cp; 71292a9e4f7SAdrian Hunter u64 ret_addr; 71392a9e4f7SAdrian Hunter 71492a9e4f7SAdrian Hunter if (!sample->ip || !sample->addr) 71592a9e4f7SAdrian Hunter return 0; 71692a9e4f7SAdrian Hunter 71792a9e4f7SAdrian Hunter ret_addr = sample->ip + sample->insn_len; 71892a9e4f7SAdrian Hunter if (ret_addr == sample->addr) 71992a9e4f7SAdrian Hunter return 0; /* Zero-length calls are excluded */ 72092a9e4f7SAdrian Hunter 72192a9e4f7SAdrian Hunter cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, 72292a9e4f7SAdrian Hunter to_al->sym, sample->addr, 72392a9e4f7SAdrian Hunter ts->kernel_start); 72492a9e4f7SAdrian Hunter if (!cp) 72592a9e4f7SAdrian Hunter return -ENOMEM; 72692a9e4f7SAdrian Hunter err = thread_stack__push_cp(ts, ret_addr, sample->time, ref, 72792a9e4f7SAdrian Hunter cp, false); 72892a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_RETURN) { 72992a9e4f7SAdrian Hunter if (!sample->ip || !sample->addr) 73092a9e4f7SAdrian Hunter return 0; 73192a9e4f7SAdrian Hunter 73292a9e4f7SAdrian Hunter err = thread_stack__pop_cp(thread, ts, sample->addr, 73392a9e4f7SAdrian Hunter sample->time, ref, from_al->sym); 73492a9e4f7SAdrian Hunter if (err) { 73592a9e4f7SAdrian Hunter if (err < 0) 73692a9e4f7SAdrian Hunter return err; 73792a9e4f7SAdrian Hunter err = thread_stack__no_call_return(thread, ts, sample, 73892a9e4f7SAdrian Hunter from_al, to_al, ref); 73992a9e4f7SAdrian Hunter } 74092a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_TRACE_BEGIN) { 74192a9e4f7SAdrian Hunter err = thread_stack__trace_begin(thread, ts, sample->time, ref); 74292a9e4f7SAdrian Hunter } else if (sample->flags & PERF_IP_FLAG_TRACE_END) { 74392a9e4f7SAdrian Hunter err = thread_stack__trace_end(ts, sample, ref); 74492a9e4f7SAdrian Hunter } 74592a9e4f7SAdrian Hunter 74692a9e4f7SAdrian Hunter return err; 74792a9e4f7SAdrian Hunter } 748