~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/perf/util/thread-stack.c

Version: ~ [ linux-5.3-rc5 ] ~ [ linux-5.2.9 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.67 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.139 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.189 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.189 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.72 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 "thread.h"
 19 #include "event.h"
 20 #include "machine.h"
 21 #include "util.h"
 22 #include "debug.h"
 23 #include "symbol.h"
 24 #include "comm.h"
 25 #include "call-path.h"
 26 #include "thread-stack.h"
 27 
 28 #define STACK_GROWTH 2048
 29 
 30 /**
 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
 36  * @cp: call path
 37  * @no_call: a 'call' was not seen
 38  */
 39 struct thread_stack_entry {
 40         u64 ret_addr;
 41         u64 timestamp;
 42         u64 ref;
 43         u64 branch_count;
 44         struct call_path *cp;
 45         bool no_call;
 46 };
 47 
 48 /**
 49  * struct thread_stack - thread stack constructed from 'call' and 'return'
 50  *                       branch samples.
 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
 59  * @comm: current comm
 60  */
 61 struct thread_stack {
 62         struct thread_stack_entry *stack;
 63         size_t cnt;
 64         size_t sz;
 65         u64 trace_nr;
 66         u64 branch_count;
 67         u64 kernel_start;
 68         u64 last_time;
 69         struct call_return_processor *crp;
 70         struct comm *comm;
 71 };
 72 
 73 static int thread_stack__grow(struct thread_stack *ts)
 74 {
 75         struct thread_stack_entry *new_stack;
 76         size_t sz, new_sz;
 77 
 78         new_sz = ts->sz + STACK_GROWTH;
 79         sz = new_sz * sizeof(struct thread_stack_entry);
 80 
 81         new_stack = realloc(ts->stack, sz);
 82         if (!new_stack)
 83                 return -ENOMEM;
 84 
 85         ts->stack = new_stack;
 86         ts->sz = new_sz;
 87 
 88         return 0;
 89 }
 90 
 91 static struct thread_stack *thread_stack__new(struct thread *thread,
 92                                               struct call_return_processor *crp)
 93 {
 94         struct thread_stack *ts;
 95 
 96         ts = zalloc(sizeof(struct thread_stack));
 97         if (!ts)
 98                 return NULL;
 99 
100         if (thread_stack__grow(ts)) {
101                 free(ts);
102                 return NULL;
103         }
104 
105         if (thread->mg && thread->mg->machine)
106                 ts->kernel_start = machine__kernel_start(thread->mg->machine);
107         else
108                 ts->kernel_start = 1ULL << 63;
109         ts->crp = crp;
110 
111         return ts;
112 }
113 
114 static int thread_stack__push(struct thread_stack *ts, u64 ret_addr)
115 {
116         int err = 0;
117 
118         if (ts->cnt == ts->sz) {
119                 err = thread_stack__grow(ts);
120                 if (err) {
121                         pr_warning("Out of memory: discarding thread stack\n");
122                         ts->cnt = 0;
123                 }
124         }
125 
126         ts->stack[ts->cnt++].ret_addr = ret_addr;
127 
128         return err;
129 }
130 
131 static void thread_stack__pop(struct thread_stack *ts, u64 ret_addr)
132 {
133         size_t i;
134 
135         /*
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.
143          */
144         for (i = ts->cnt; i; ) {
145                 if (ts->stack[--i].ret_addr == ret_addr) {
146                         ts->cnt = i;
147                         return;
148                 }
149         }
150 }
151 
152 static bool thread_stack__in_kernel(struct thread_stack *ts)
153 {
154         if (!ts->cnt)
155                 return false;
156 
157         return ts->stack[ts->cnt - 1].cp->in_kernel;
158 }
159 
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)
163 {
164         struct call_return_processor *crp = ts->crp;
165         struct thread_stack_entry *tse;
166         struct call_return cr = {
167                 .thread = thread,
168                 .comm = ts->comm,
169                 .db_id = 0,
170         };
171 
172         tse = &ts->stack[idx];
173         cr.cp = tse->cp;
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;
178         cr.return_ref = ref;
179         if (tse->no_call)
180                 cr.flags |= CALL_RETURN_NO_CALL;
181         if (no_return)
182                 cr.flags |= CALL_RETURN_NO_RETURN;
183 
184         return crp->process(&cr, crp->data);
185 }
186 
187 static int __thread_stack__flush(struct thread *thread, struct thread_stack *ts)
188 {
189         struct call_return_processor *crp = ts->crp;
190         int err;
191 
192         if (!crp) {
193                 ts->cnt = 0;
194                 return 0;
195         }
196 
197         while (ts->cnt) {
198                 err = thread_stack__call_return(thread, ts, --ts->cnt,
199                                                 ts->last_time, 0, true);
200                 if (err) {
201                         pr_err("Error flushing thread stack!\n");
202                         ts->cnt = 0;
203                         return err;
204                 }
205         }
206 
207         return 0;
208 }
209 
210 int thread_stack__flush(struct thread *thread)
211 {
212         if (thread->ts)
213                 return __thread_stack__flush(thread, thread->ts);
214 
215         return 0;
216 }
217 
218 int thread_stack__event(struct thread *thread, u32 flags, u64 from_ip,
219                         u64 to_ip, u16 insn_len, u64 trace_nr)
220 {
221         if (!thread)
222                 return -EINVAL;
223 
224         if (!thread->ts) {
225                 thread->ts = thread_stack__new(thread, NULL);
226                 if (!thread->ts) {
227                         pr_warning("Out of memory: no thread stack\n");
228                         return -ENOMEM;
229                 }
230                 thread->ts->trace_nr = trace_nr;
231         }
232 
233         /*
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.
237          */
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;
242         }
243 
244         /* Stop here if thread_stack__process() is in use */
245         if (thread->ts->crp)
246                 return 0;
247 
248         if (flags & PERF_IP_FLAG_CALL) {
249                 u64 ret_addr;
250 
251                 if (!to_ip)
252                         return 0;
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) {
258                 if (!from_ip)
259                         return 0;
260                 thread_stack__pop(thread->ts, to_ip);
261         }
262 
263         return 0;
264 }
265 
266 void thread_stack__set_trace_nr(struct thread *thread, u64 trace_nr)
267 {
268         if (!thread || !thread->ts)
269                 return;
270 
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;
275         }
276 }
277 
278 void thread_stack__free(struct thread *thread)
279 {
280         if (thread->ts) {
281                 __thread_stack__flush(thread, thread->ts);
282                 zfree(&thread->ts->stack);
283                 zfree(&thread->ts);
284         }
285 }
286 
287 void thread_stack__sample(struct thread *thread, struct ip_callchain *chain,
288                           size_t sz, u64 ip)
289 {
290         size_t i;
291 
292         if (!thread || !thread->ts)
293                 chain->nr = 1;
294         else
295                 chain->nr = min(sz, thread->ts->cnt + 1);
296 
297         chain->ips[0] = ip;
298 
299         for (i = 1; i < chain->nr; i++)
300                 chain->ips[i] = thread->ts->stack[thread->ts->cnt - i].ret_addr;
301 }
302 
303 struct call_return_processor *
304 call_return_processor__new(int (*process)(struct call_return *cr, void *data),
305                            void *data)
306 {
307         struct call_return_processor *crp;
308 
309         crp = zalloc(sizeof(struct call_return_processor));
310         if (!crp)
311                 return NULL;
312         crp->cpr = call_path_root__new();
313         if (!crp->cpr)
314                 goto out_free;
315         crp->process = process;
316         crp->data = data;
317         return crp;
318 
319 out_free:
320         free(crp);
321         return NULL;
322 }
323 
324 void call_return_processor__free(struct call_return_processor *crp)
325 {
326         if (crp) {
327                 call_path_root__free(crp->cpr);
328                 free(crp);
329         }
330 }
331 
332 static int thread_stack__push_cp(struct thread_stack *ts, u64 ret_addr,
333                                  u64 timestamp, u64 ref, struct call_path *cp,
334                                  bool no_call)
335 {
336         struct thread_stack_entry *tse;
337         int err;
338 
339         if (ts->cnt == ts->sz) {
340                 err = thread_stack__grow(ts);
341                 if (err)
342                         return err;
343         }
344 
345         tse = &ts->stack[ts->cnt++];
346         tse->ret_addr = ret_addr;
347         tse->timestamp = timestamp;
348         tse->ref = ref;
349         tse->branch_count = ts->branch_count;
350         tse->cp = cp;
351         tse->no_call = no_call;
352 
353         return 0;
354 }
355 
356 static int thread_stack__pop_cp(struct thread *thread, struct thread_stack *ts,
357                                 u64 ret_addr, u64 timestamp, u64 ref,
358                                 struct symbol *sym)
359 {
360         int err;
361 
362         if (!ts->cnt)
363                 return 1;
364 
365         if (ts->cnt == 1) {
366                 struct thread_stack_entry *tse = &ts->stack[0];
367 
368                 if (tse->cp->sym == sym)
369                         return thread_stack__call_return(thread, ts, --ts->cnt,
370                                                          timestamp, ref, false);
371         }
372 
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);
376         } else {
377                 size_t i = ts->cnt - 1;
378 
379                 while (i--) {
380                         if (ts->stack[i].ret_addr != ret_addr)
381                                 continue;
382                         i += 1;
383                         while (ts->cnt > i) {
384                                 err = thread_stack__call_return(thread, ts,
385                                                                 --ts->cnt,
386                                                                 timestamp, ref,
387                                                                 true);
388                                 if (err)
389                                         return err;
390                         }
391                         return thread_stack__call_return(thread, ts, --ts->cnt,
392                                                          timestamp, ref, false);
393                 }
394         }
395 
396         return 1;
397 }
398 
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)
403 {
404         struct call_path_root *cpr = ts->crp->cpr;
405         struct call_path *cp;
406         struct symbol *sym;
407         u64 ip;
408 
409         if (sample->ip) {
410                 ip = sample->ip;
411                 sym = from_al->sym;
412         } else if (sample->addr) {
413                 ip = sample->addr;
414                 sym = to_al->sym;
415         } else {
416                 return 0;
417         }
418 
419         cp = call_path__findnew(cpr, &cpr->call_path, sym, ip,
420                                 ts->kernel_start);
421         if (!cp)
422                 return -ENOMEM;
423 
424         return thread_stack__push_cp(thread->ts, ip, sample->time, ref, cp,
425                                      true);
426 }
427 
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)
433 {
434         struct call_path_root *cpr = ts->crp->cpr;
435         struct call_path *cp, *parent;
436         u64 ks = ts->kernel_start;
437         int err;
438 
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,
443                                                         sample->time, ref,
444                                                         true);
445                         if (err)
446                                 return err;
447                 }
448 
449                 /* If the stack is empty, push the userspace address */
450                 if (!ts->cnt) {
451                         cp = call_path__findnew(cpr, &cpr->call_path,
452                                                 to_al->sym, sample->addr,
453                                                 ts->kernel_start);
454                         if (!cp)
455                                 return -ENOMEM;
456                         return thread_stack__push_cp(ts, 0, sample->time, ref,
457                                                      cp, true);
458                 }
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,
463                                                         sample->time, ref,
464                                                         true);
465                         if (err)
466                                 return err;
467                 }
468         }
469 
470         if (ts->cnt)
471                 parent = ts->stack[ts->cnt - 1].cp;
472         else
473                 parent = &cpr->call_path;
474 
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,
477                                 ts->kernel_start);
478         if (!cp)
479                 return -ENOMEM;
480 
481         err = thread_stack__push_cp(ts, sample->addr, sample->time, ref, cp,
482                                     true);
483         if (err)
484                 return err;
485 
486         return thread_stack__pop_cp(thread, ts, sample->addr, sample->time, ref,
487                                     to_al->sym);
488 }
489 
490 static int thread_stack__trace_begin(struct thread *thread,
491                                      struct thread_stack *ts, u64 timestamp,
492                                      u64 ref)
493 {
494         struct thread_stack_entry *tse;
495         int err;
496 
497         if (!ts->cnt)
498                 return 0;
499 
500         /* Pop trace end */
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);
505                 if (err)
506                         return err;
507         }
508 
509         return 0;
510 }
511 
512 static int thread_stack__trace_end(struct thread_stack *ts,
513                                    struct perf_sample *sample, u64 ref)
514 {
515         struct call_path_root *cpr = ts->crp->cpr;
516         struct call_path *cp;
517         u64 ret_addr;
518 
519         /* No point having 'trace end' on the bottom of the stack */
520         if (!ts->cnt || (ts->cnt == 1 && ts->stack[0].ref == ref))
521                 return 0;
522 
523         cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp, NULL, 0,
524                                 ts->kernel_start);
525         if (!cp)
526                 return -ENOMEM;
527 
528         ret_addr = sample->ip + sample->insn_len;
529 
530         return thread_stack__push_cp(ts, ret_addr, sample->time, ref, cp,
531                                      false);
532 }
533 
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)
539 {
540         struct thread_stack *ts = thread->ts;
541         int err = 0;
542 
543         if (ts) {
544                 if (!ts->crp) {
545                         /* Supersede thread_stack__event() */
546                         thread_stack__free(thread);
547                         thread->ts = thread_stack__new(thread, crp);
548                         if (!thread->ts)
549                                 return -ENOMEM;
550                         ts = thread->ts;
551                         ts->comm = comm;
552                 }
553         } else {
554                 thread->ts = thread_stack__new(thread, crp);
555                 if (!thread->ts)
556                         return -ENOMEM;
557                 ts = thread->ts;
558                 ts->comm = comm;
559         }
560 
561         /* Flush stack on exec */
562         if (ts->comm != comm && thread->pid_ == thread->tid) {
563                 err = __thread_stack__flush(thread, ts);
564                 if (err)
565                         return err;
566                 ts->comm = comm;
567         }
568 
569         /* If the stack is empty, put the current symbol on the stack */
570         if (!ts->cnt) {
571                 err = thread_stack__bottom(thread, ts, sample, from_al, to_al,
572                                            ref);
573                 if (err)
574                         return err;
575         }
576 
577         ts->branch_count += 1;
578         ts->last_time = sample->time;
579 
580         if (sample->flags & PERF_IP_FLAG_CALL) {
581                 struct call_path_root *cpr = ts->crp->cpr;
582                 struct call_path *cp;
583                 u64 ret_addr;
584 
585                 if (!sample->ip || !sample->addr)
586                         return 0;
587 
588                 ret_addr = sample->ip + sample->insn_len;
589                 if (ret_addr == sample->addr)
590                         return 0; /* Zero-length calls are excluded */
591 
592                 cp = call_path__findnew(cpr, ts->stack[ts->cnt - 1].cp,
593                                         to_al->sym, sample->addr,
594                                         ts->kernel_start);
595                 if (!cp)
596                         return -ENOMEM;
597                 err = thread_stack__push_cp(ts, ret_addr, sample->time, ref,
598                                             cp, false);
599         } else if (sample->flags & PERF_IP_FLAG_RETURN) {
600                 if (!sample->ip || !sample->addr)
601                         return 0;
602 
603                 err = thread_stack__pop_cp(thread, ts, sample->addr,
604                                            sample->time, ref, from_al->sym);
605                 if (err) {
606                         if (err < 0)
607                                 return err;
608                         err = thread_stack__no_call_return(thread, ts, sample,
609                                                            from_al, to_al, ref);
610                 }
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);
615         }
616 
617         return err;
618 }
619 
620 size_t thread_stack__depth(struct thread *thread)
621 {
622         if (!thread->ts)
623                 return 0;
624         return thread->ts->cnt;
625 }
626 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp