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