2 * thread-stack.c: Synthesize a thread's stack using call / return events
3 * Copyright (c) 2014, Intel Corporation.
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms and conditions of the GNU General Public License,
7 * version 2, as published by the Free Software Foundation.
9 * This program is distributed in the hope it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
16 #include <linux/rbtree.h>
17 #include <linux/list.h>
25 #include "call-path.h"
26 #include "thread-stack.h"
28 #define STACK_GROWTH 2048
31 * struct thread_stack_entry - thread stack entry.
32 * @ret_addr: return address
33 * @timestamp: timestamp (if known)
34 * @ref: external reference (e.g. db_id of sample)
35 * @branch_count: the branch count when the entry was created
37 * @no_call: a 'call' was not seen
39 struct thread_stack_entry
{
49 * struct thread_stack - thread stack constructed from 'call' and 'return'
51 * @stack: array that holds the stack
52 * @cnt: number of entries in the stack
53 * @sz: current maximum stack size
54 * @trace_nr: current trace number
55 * @branch_count: running branch count
56 * @kernel_start: kernel start address
57 * @last_time: last timestamp
58 * @crp: call/return processor
62 struct thread_stack_entry
*stack
;
69 struct call_return_processor
*crp
;
73 static int thread_stack__grow(struct thread_stack
*ts
)
75 struct thread_stack_entry
*new_stack
;
78 new_sz
= ts
->sz
+ STACK_GROWTH
;
79 sz
= new_sz
* sizeof(struct thread_stack_entry
);
81 new_stack
= realloc(ts
->stack
, sz
);
85 ts
->stack
= new_stack
;
91 static struct thread_stack
*thread_stack__new(struct thread
*thread
,
92 struct call_return_processor
*crp
)
94 struct thread_stack
*ts
;
96 ts
= zalloc(sizeof(struct thread_stack
));
100 if (thread_stack__grow(ts
)) {
105 if (thread
->mg
&& thread
->mg
->machine
)
106 ts
->kernel_start
= machine__kernel_start(thread
->mg
->machine
);
108 ts
->kernel_start
= 1ULL << 63;
114 static int thread_stack__push(struct thread_stack
*ts
, u64 ret_addr
)
118 if (ts
->cnt
== ts
->sz
) {
119 err
= thread_stack__grow(ts
);
121 pr_warning("Out of memory: discarding thread stack\n");
126 ts
->stack
[ts
->cnt
++].ret_addr
= ret_addr
;
131 static void thread_stack__pop(struct thread_stack
*ts
, u64 ret_addr
)
136 * In some cases there may be functions which are not seen to return.
137 * For example when setjmp / longjmp has been used. Or the perf context
138 * switch in the kernel which doesn't stop and start tracing in exactly
139 * the same code path. When that happens the return address will be
140 * further down the stack. If the return address is not found at all,
141 * we assume the opposite (i.e. this is a return for a call that wasn't
142 * seen for some reason) and leave the stack alone.
144 for (i
= ts
->cnt
; i
; ) {
145 if (ts
->stack
[--i
].ret_addr
== ret_addr
) {
152 static bool thread_stack__in_kernel(struct thread_stack
*ts
)
157 return ts
->stack
[ts
->cnt
- 1].cp
->in_kernel
;
160 static int thread_stack__call_return(struct thread
*thread
,
161 struct thread_stack
*ts
, size_t idx
,
162 u64 timestamp
, u64 ref
, bool no_return
)
164 struct call_return_processor
*crp
= ts
->crp
;
165 struct thread_stack_entry
*tse
;
166 struct call_return cr
= {
172 tse
= &ts
->stack
[idx
];
174 cr
.call_time
= tse
->timestamp
;
175 cr
.return_time
= timestamp
;
176 cr
.branch_count
= ts
->branch_count
- tse
->branch_count
;
177 cr
.call_ref
= tse
->ref
;
180 cr
.flags
|= CALL_RETURN_NO_CALL
;
182 cr
.flags
|= CALL_RETURN_NO_RETURN
;
184 return crp
->process(&cr
, crp
->data
);
187 static int __thread_stack__flush(struct thread
*thread
, struct thread_stack
*ts
)
189 struct call_return_processor
*crp
= ts
->crp
;
198 err
= thread_stack__call_return(thread
, ts
, --ts
->cnt
,
199 ts
->last_time
, 0, true);
201 pr_err("Error flushing thread stack!\n");
210 int thread_stack__flush(struct thread
*thread
)
213 return __thread_stack__flush(thread
, thread
->ts
);
218 int thread_stack__event(struct thread
*thread
, u32 flags
, u64 from_ip
,
219 u64 to_ip
, u16 insn_len
, u64 trace_nr
)
225 thread
->ts
= thread_stack__new(thread
, NULL
);
227 pr_warning("Out of memory: no thread stack\n");
230 thread
->ts
->trace_nr
= trace_nr
;
234 * When the trace is discontinuous, the trace_nr changes. In that case
235 * the stack might be completely invalid. Better to report nothing than
236 * to report something misleading, so flush the stack.
238 if (trace_nr
!= thread
->ts
->trace_nr
) {
239 if (thread
->ts
->trace_nr
)
240 __thread_stack__flush(thread
, thread
->ts
);
241 thread
->ts
->trace_nr
= trace_nr
;
244 /* Stop here if thread_stack__process() is in use */
248 if (flags
& PERF_IP_FLAG_CALL
) {
253 ret_addr
= from_ip
+ insn_len
;
254 if (ret_addr
== to_ip
)
255 return 0; /* Zero-length calls are excluded */
256 return thread_stack__push(thread
->ts
, ret_addr
);
257 } else if (flags
& PERF_IP_FLAG_RETURN
) {
260 thread_stack__pop(thread
->ts
, to_ip
);
266 void thread_stack__set_trace_nr(struct thread
*thread
, u64 trace_nr
)
268 if (!thread
|| !thread
->ts
)
271 if (trace_nr
!= thread
->ts
->trace_nr
) {
272 if (thread
->ts
->trace_nr
)
273 __thread_stack__flush(thread
, thread
->ts
);
274 thread
->ts
->trace_nr
= trace_nr
;
278 void thread_stack__free(struct thread
*thread
)
281 __thread_stack__flush(thread
, thread
->ts
);
282 zfree(&thread
->ts
->stack
);
287 void thread_stack__sample(struct thread
*thread
, struct ip_callchain
*chain
,
292 if (!thread
|| !thread
->ts
)
295 chain
->nr
= min(sz
, thread
->ts
->cnt
+ 1);
299 for (i
= 1; i
< chain
->nr
; i
++)
300 chain
->ips
[i
] = thread
->ts
->stack
[thread
->ts
->cnt
- i
].ret_addr
;
303 struct call_return_processor
*
304 call_return_processor__new(int (*process
)(struct call_return
*cr
, void *data
),
307 struct call_return_processor
*crp
;
309 crp
= zalloc(sizeof(struct call_return_processor
));
312 crp
->cpr
= call_path_root__new();
315 crp
->process
= process
;
324 void call_return_processor__free(struct call_return_processor
*crp
)
327 call_path_root__free(crp
->cpr
);
332 static int thread_stack__push_cp(struct thread_stack
*ts
, u64 ret_addr
,
333 u64 timestamp
, u64 ref
, struct call_path
*cp
,
336 struct thread_stack_entry
*tse
;
339 if (ts
->cnt
== ts
->sz
) {
340 err
= thread_stack__grow(ts
);
345 tse
= &ts
->stack
[ts
->cnt
++];
346 tse
->ret_addr
= ret_addr
;
347 tse
->timestamp
= timestamp
;
349 tse
->branch_count
= ts
->branch_count
;
351 tse
->no_call
= no_call
;
356 static int thread_stack__pop_cp(struct thread
*thread
, struct thread_stack
*ts
,
357 u64 ret_addr
, u64 timestamp
, u64 ref
,
366 struct thread_stack_entry
*tse
= &ts
->stack
[0];
368 if (tse
->cp
->sym
== sym
)
369 return thread_stack__call_return(thread
, ts
, --ts
->cnt
,
370 timestamp
, ref
, false);
373 if (ts
->stack
[ts
->cnt
- 1].ret_addr
== ret_addr
) {
374 return thread_stack__call_return(thread
, ts
, --ts
->cnt
,
375 timestamp
, ref
, false);
377 size_t i
= ts
->cnt
- 1;
380 if (ts
->stack
[i
].ret_addr
!= ret_addr
)
383 while (ts
->cnt
> i
) {
384 err
= thread_stack__call_return(thread
, ts
,
391 return thread_stack__call_return(thread
, ts
, --ts
->cnt
,
392 timestamp
, ref
, false);
399 static int thread_stack__bottom(struct thread
*thread
, struct thread_stack
*ts
,
400 struct perf_sample
*sample
,
401 struct addr_location
*from_al
,
402 struct addr_location
*to_al
, u64 ref
)
404 struct call_path_root
*cpr
= ts
->crp
->cpr
;
405 struct call_path
*cp
;
412 } else if (sample
->addr
) {
419 cp
= call_path__findnew(cpr
, &cpr
->call_path
, sym
, ip
,
424 return thread_stack__push_cp(thread
->ts
, ip
, sample
->time
, ref
, cp
,
428 static int thread_stack__no_call_return(struct thread
*thread
,
429 struct thread_stack
*ts
,
430 struct perf_sample
*sample
,
431 struct addr_location
*from_al
,
432 struct addr_location
*to_al
, u64 ref
)
434 struct call_path_root
*cpr
= ts
->crp
->cpr
;
435 struct call_path
*cp
, *parent
;
436 u64 ks
= ts
->kernel_start
;
439 if (sample
->ip
>= ks
&& sample
->addr
< ks
) {
440 /* Return to userspace, so pop all kernel addresses */
441 while (thread_stack__in_kernel(ts
)) {
442 err
= thread_stack__call_return(thread
, ts
, --ts
->cnt
,
449 /* If the stack is empty, push the userspace address */
451 cp
= call_path__findnew(cpr
, &cpr
->call_path
,
452 to_al
->sym
, sample
->addr
,
456 return thread_stack__push_cp(ts
, 0, sample
->time
, ref
,
459 } else if (thread_stack__in_kernel(ts
) && sample
->ip
< ks
) {
460 /* Return to userspace, so pop all kernel addresses */
461 while (thread_stack__in_kernel(ts
)) {
462 err
= thread_stack__call_return(thread
, ts
, --ts
->cnt
,
471 parent
= ts
->stack
[ts
->cnt
- 1].cp
;
473 parent
= &cpr
->call_path
;
475 /* This 'return' had no 'call', so push and pop top of stack */
476 cp
= call_path__findnew(cpr
, parent
, from_al
->sym
, sample
->ip
,
481 err
= thread_stack__push_cp(ts
, sample
->addr
, sample
->time
, ref
, cp
,
486 return thread_stack__pop_cp(thread
, ts
, sample
->addr
, sample
->time
, ref
,
490 static int thread_stack__trace_begin(struct thread
*thread
,
491 struct thread_stack
*ts
, u64 timestamp
,
494 struct thread_stack_entry
*tse
;
501 tse
= &ts
->stack
[ts
->cnt
- 1];
502 if (tse
->cp
->sym
== NULL
&& tse
->cp
->ip
== 0) {
503 err
= thread_stack__call_return(thread
, ts
, --ts
->cnt
,
504 timestamp
, ref
, false);
512 static int thread_stack__trace_end(struct thread_stack
*ts
,
513 struct perf_sample
*sample
, u64 ref
)
515 struct call_path_root
*cpr
= ts
->crp
->cpr
;
516 struct call_path
*cp
;
519 /* No point having 'trace end' on the bottom of the stack */
520 if (!ts
->cnt
|| (ts
->cnt
== 1 && ts
->stack
[0].ref
== ref
))
523 cp
= call_path__findnew(cpr
, ts
->stack
[ts
->cnt
- 1].cp
, NULL
, 0,
528 ret_addr
= sample
->ip
+ sample
->insn_len
;
530 return thread_stack__push_cp(ts
, ret_addr
, sample
->time
, ref
, cp
,
534 int thread_stack__process(struct thread
*thread
, struct comm
*comm
,
535 struct perf_sample
*sample
,
536 struct addr_location
*from_al
,
537 struct addr_location
*to_al
, u64 ref
,
538 struct call_return_processor
*crp
)
540 struct thread_stack
*ts
= thread
->ts
;
545 /* Supersede thread_stack__event() */
546 thread_stack__free(thread
);
547 thread
->ts
= thread_stack__new(thread
, crp
);
554 thread
->ts
= thread_stack__new(thread
, crp
);
561 /* Flush stack on exec */
562 if (ts
->comm
!= comm
&& thread
->pid_
== thread
->tid
) {
563 err
= __thread_stack__flush(thread
, ts
);
569 /* If the stack is empty, put the current symbol on the stack */
571 err
= thread_stack__bottom(thread
, ts
, sample
, from_al
, to_al
,
577 ts
->branch_count
+= 1;
578 ts
->last_time
= sample
->time
;
580 if (sample
->flags
& PERF_IP_FLAG_CALL
) {
581 struct call_path_root
*cpr
= ts
->crp
->cpr
;
582 struct call_path
*cp
;
585 if (!sample
->ip
|| !sample
->addr
)
588 ret_addr
= sample
->ip
+ sample
->insn_len
;
589 if (ret_addr
== sample
->addr
)
590 return 0; /* Zero-length calls are excluded */
592 cp
= call_path__findnew(cpr
, ts
->stack
[ts
->cnt
- 1].cp
,
593 to_al
->sym
, sample
->addr
,
597 err
= thread_stack__push_cp(ts
, ret_addr
, sample
->time
, ref
,
599 } else if (sample
->flags
& PERF_IP_FLAG_RETURN
) {
600 if (!sample
->ip
|| !sample
->addr
)
603 err
= thread_stack__pop_cp(thread
, ts
, sample
->addr
,
604 sample
->time
, ref
, from_al
->sym
);
608 err
= thread_stack__no_call_return(thread
, ts
, sample
,
609 from_al
, to_al
, ref
);
611 } else if (sample
->flags
& PERF_IP_FLAG_TRACE_BEGIN
) {
612 err
= thread_stack__trace_begin(thread
, ts
, sample
->time
, ref
);
613 } else if (sample
->flags
& PERF_IP_FLAG_TRACE_END
) {
614 err
= thread_stack__trace_end(ts
, sample
, ref
);
This page took 0.064672 seconds and 5 git commands to generate.