perf_counter tools: Prepare a small callchain framework
[firefly-linux-kernel-4.4.55.git] / tools / perf / builtin-report.c
1 /*
2  * builtin-report.c
3  *
4  * Builtin report command: Analyze the perf.data input file,
5  * look up and read DSOs and symbol information and display
6  * a histogram of results, along various sorting keys.
7  */
8 #include "builtin.h"
9
10 #include "util/util.h"
11
12 #include "util/color.h"
13 #include "util/list.h"
14 #include "util/cache.h"
15 #include "util/rbtree.h"
16 #include "util/symbol.h"
17 #include "util/string.h"
18
19 #include "perf.h"
20 #include "util/header.h"
21
22 #include "util/parse-options.h"
23 #include "util/parse-events.h"
24
25 #define SHOW_KERNEL     1
26 #define SHOW_USER       2
27 #define SHOW_HV         4
28
29 static char             const *input_name = "perf.data";
30 static char             *vmlinux = NULL;
31
32 static char             default_sort_order[] = "comm,dso";
33 static char             *sort_order = default_sort_order;
34
35 static int              input;
36 static int              show_mask = SHOW_KERNEL | SHOW_USER | SHOW_HV;
37
38 static int              dump_trace = 0;
39 #define dprintf(x...)   do { if (dump_trace) printf(x); } while (0)
40 #define cdprintf(x...)  do { if (dump_trace) color_fprintf(stdout, color, x); } while (0)
41
42 static int              verbose;
43 #define eprintf(x...)   do { if (verbose) fprintf(stderr, x); } while (0)
44
45 static int              full_paths;
46
47 static unsigned long    page_size;
48 static unsigned long    mmap_window = 32;
49
50 static char             default_parent_pattern[] = "^sys_|^do_page_fault";
51 static char             *parent_pattern = default_parent_pattern;
52 static regex_t          parent_regex;
53
54 static int              exclude_other = 1;
55
56 static u64              sample_type;
57
58 struct ip_event {
59         struct perf_event_header header;
60         u64 ip;
61         u32 pid, tid;
62         unsigned char __more_data[];
63 };
64
65 struct mmap_event {
66         struct perf_event_header header;
67         u32 pid, tid;
68         u64 start;
69         u64 len;
70         u64 pgoff;
71         char filename[PATH_MAX];
72 };
73
74 struct comm_event {
75         struct perf_event_header header;
76         u32 pid, tid;
77         char comm[16];
78 };
79
80 struct fork_event {
81         struct perf_event_header header;
82         u32 pid, ppid;
83 };
84
85 struct period_event {
86         struct perf_event_header header;
87         u64 time;
88         u64 id;
89         u64 sample_period;
90 };
91
92 struct lost_event {
93         struct perf_event_header header;
94         u64 id;
95         u64 lost;
96 };
97
98 struct read_event {
99         struct perf_event_header header;
100         u32 pid,tid;
101         u64 value;
102         u64 format[3];
103 };
104
105 typedef union event_union {
106         struct perf_event_header        header;
107         struct ip_event                 ip;
108         struct mmap_event               mmap;
109         struct comm_event               comm;
110         struct fork_event               fork;
111         struct period_event             period;
112         struct lost_event               lost;
113         struct read_event               read;
114 } event_t;
115
116 static LIST_HEAD(dsos);
117 static struct dso *kernel_dso;
118 static struct dso *vdso;
119
120 static void dsos__add(struct dso *dso)
121 {
122         list_add_tail(&dso->node, &dsos);
123 }
124
125 static struct dso *dsos__find(const char *name)
126 {
127         struct dso *pos;
128
129         list_for_each_entry(pos, &dsos, node)
130                 if (strcmp(pos->name, name) == 0)
131                         return pos;
132         return NULL;
133 }
134
135 static struct dso *dsos__findnew(const char *name)
136 {
137         struct dso *dso = dsos__find(name);
138         int nr;
139
140         if (dso)
141                 return dso;
142
143         dso = dso__new(name, 0);
144         if (!dso)
145                 goto out_delete_dso;
146
147         nr = dso__load(dso, NULL, verbose);
148         if (nr < 0) {
149                 eprintf("Failed to open: %s\n", name);
150                 goto out_delete_dso;
151         }
152         if (!nr)
153                 eprintf("No symbols found in: %s, maybe install a debug package?\n", name);
154
155         dsos__add(dso);
156
157         return dso;
158
159 out_delete_dso:
160         dso__delete(dso);
161         return NULL;
162 }
163
164 static void dsos__fprintf(FILE *fp)
165 {
166         struct dso *pos;
167
168         list_for_each_entry(pos, &dsos, node)
169                 dso__fprintf(pos, fp);
170 }
171
172 static struct symbol *vdso__find_symbol(struct dso *dso, u64 ip)
173 {
174         return dso__find_symbol(kernel_dso, ip);
175 }
176
177 static int load_kernel(void)
178 {
179         int err;
180
181         kernel_dso = dso__new("[kernel]", 0);
182         if (!kernel_dso)
183                 return -1;
184
185         err = dso__load_kernel(kernel_dso, vmlinux, NULL, verbose);
186         if (err) {
187                 dso__delete(kernel_dso);
188                 kernel_dso = NULL;
189         } else
190                 dsos__add(kernel_dso);
191
192         vdso = dso__new("[vdso]", 0);
193         if (!vdso)
194                 return -1;
195
196         vdso->find_symbol = vdso__find_symbol;
197
198         dsos__add(vdso);
199
200         return err;
201 }
202
203 static char __cwd[PATH_MAX];
204 static char *cwd = __cwd;
205 static int cwdlen;
206
207 static int strcommon(const char *pathname)
208 {
209         int n = 0;
210
211         while (pathname[n] == cwd[n] && n < cwdlen)
212                 ++n;
213
214         return n;
215 }
216
217 struct map {
218         struct list_head node;
219         u64      start;
220         u64      end;
221         u64      pgoff;
222         u64      (*map_ip)(struct map *, u64);
223         struct dso       *dso;
224 };
225
226 static u64 map__map_ip(struct map *map, u64 ip)
227 {
228         return ip - map->start + map->pgoff;
229 }
230
231 static u64 vdso__map_ip(struct map *map, u64 ip)
232 {
233         return ip;
234 }
235
236 static inline int is_anon_memory(const char *filename)
237 {
238      return strcmp(filename, "//anon") == 0;
239 }
240
241 static struct map *map__new(struct mmap_event *event)
242 {
243         struct map *self = malloc(sizeof(*self));
244
245         if (self != NULL) {
246                 const char *filename = event->filename;
247                 char newfilename[PATH_MAX];
248                 int anon;
249
250                 if (cwd) {
251                         int n = strcommon(filename);
252
253                         if (n == cwdlen) {
254                                 snprintf(newfilename, sizeof(newfilename),
255                                          ".%s", filename + n);
256                                 filename = newfilename;
257                         }
258                 }
259
260                 anon = is_anon_memory(filename);
261
262                 if (anon) {
263                         snprintf(newfilename, sizeof(newfilename), "/tmp/perf-%d.map", event->pid);
264                         filename = newfilename;
265                 }
266
267                 self->start = event->start;
268                 self->end   = event->start + event->len;
269                 self->pgoff = event->pgoff;
270
271                 self->dso = dsos__findnew(filename);
272                 if (self->dso == NULL)
273                         goto out_delete;
274
275                 if (self->dso == vdso || anon)
276                         self->map_ip = vdso__map_ip;
277                 else
278                         self->map_ip = map__map_ip;
279         }
280         return self;
281 out_delete:
282         free(self);
283         return NULL;
284 }
285
286 static struct map *map__clone(struct map *self)
287 {
288         struct map *map = malloc(sizeof(*self));
289
290         if (!map)
291                 return NULL;
292
293         memcpy(map, self, sizeof(*self));
294
295         return map;
296 }
297
298 static int map__overlap(struct map *l, struct map *r)
299 {
300         if (l->start > r->start) {
301                 struct map *t = l;
302                 l = r;
303                 r = t;
304         }
305
306         if (l->end > r->start)
307                 return 1;
308
309         return 0;
310 }
311
312 static size_t map__fprintf(struct map *self, FILE *fp)
313 {
314         return fprintf(fp, " %Lx-%Lx %Lx %s\n",
315                        self->start, self->end, self->pgoff, self->dso->name);
316 }
317
318
319 struct thread {
320         struct rb_node   rb_node;
321         struct list_head maps;
322         pid_t            pid;
323         char             *comm;
324 };
325
326 static struct thread *thread__new(pid_t pid)
327 {
328         struct thread *self = malloc(sizeof(*self));
329
330         if (self != NULL) {
331                 self->pid = pid;
332                 self->comm = malloc(32);
333                 if (self->comm)
334                         snprintf(self->comm, 32, ":%d", self->pid);
335                 INIT_LIST_HEAD(&self->maps);
336         }
337
338         return self;
339 }
340
341 static int thread__set_comm(struct thread *self, const char *comm)
342 {
343         if (self->comm)
344                 free(self->comm);
345         self->comm = strdup(comm);
346         return self->comm ? 0 : -ENOMEM;
347 }
348
349 static size_t thread__fprintf(struct thread *self, FILE *fp)
350 {
351         struct map *pos;
352         size_t ret = fprintf(fp, "Thread %d %s\n", self->pid, self->comm);
353
354         list_for_each_entry(pos, &self->maps, node)
355                 ret += map__fprintf(pos, fp);
356
357         return ret;
358 }
359
360
361 static struct rb_root threads;
362 static struct thread *last_match;
363
364 static struct thread *threads__findnew(pid_t pid)
365 {
366         struct rb_node **p = &threads.rb_node;
367         struct rb_node *parent = NULL;
368         struct thread *th;
369
370         /*
371          * Font-end cache - PID lookups come in blocks,
372          * so most of the time we dont have to look up
373          * the full rbtree:
374          */
375         if (last_match && last_match->pid == pid)
376                 return last_match;
377
378         while (*p != NULL) {
379                 parent = *p;
380                 th = rb_entry(parent, struct thread, rb_node);
381
382                 if (th->pid == pid) {
383                         last_match = th;
384                         return th;
385                 }
386
387                 if (pid < th->pid)
388                         p = &(*p)->rb_left;
389                 else
390                         p = &(*p)->rb_right;
391         }
392
393         th = thread__new(pid);
394         if (th != NULL) {
395                 rb_link_node(&th->rb_node, parent, p);
396                 rb_insert_color(&th->rb_node, &threads);
397                 last_match = th;
398         }
399
400         return th;
401 }
402
403 static void thread__insert_map(struct thread *self, struct map *map)
404 {
405         struct map *pos, *tmp;
406
407         list_for_each_entry_safe(pos, tmp, &self->maps, node) {
408                 if (map__overlap(pos, map)) {
409                         if (verbose >= 2) {
410                                 printf("overlapping maps:\n");
411                                 map__fprintf(map, stdout);
412                                 map__fprintf(pos, stdout);
413                         }
414
415                         if (map->start <= pos->start && map->end > pos->start)
416                                 pos->start = map->end;
417
418                         if (map->end >= pos->end && map->start < pos->end)
419                                 pos->end = map->start;
420
421                         if (verbose >= 2) {
422                                 printf("after collision:\n");
423                                 map__fprintf(pos, stdout);
424                         }
425
426                         if (pos->start >= pos->end) {
427                                 list_del_init(&pos->node);
428                                 free(pos);
429                         }
430                 }
431         }
432
433         list_add_tail(&map->node, &self->maps);
434 }
435
436 static int thread__fork(struct thread *self, struct thread *parent)
437 {
438         struct map *map;
439
440         if (self->comm)
441                 free(self->comm);
442         self->comm = strdup(parent->comm);
443         if (!self->comm)
444                 return -ENOMEM;
445
446         list_for_each_entry(map, &parent->maps, node) {
447                 struct map *new = map__clone(map);
448                 if (!new)
449                         return -ENOMEM;
450                 thread__insert_map(self, new);
451         }
452
453         return 0;
454 }
455
456 static struct map *thread__find_map(struct thread *self, u64 ip)
457 {
458         struct map *pos;
459
460         if (self == NULL)
461                 return NULL;
462
463         list_for_each_entry(pos, &self->maps, node)
464                 if (ip >= pos->start && ip <= pos->end)
465                         return pos;
466
467         return NULL;
468 }
469
470 static size_t threads__fprintf(FILE *fp)
471 {
472         size_t ret = 0;
473         struct rb_node *nd;
474
475         for (nd = rb_first(&threads); nd; nd = rb_next(nd)) {
476                 struct thread *pos = rb_entry(nd, struct thread, rb_node);
477
478                 ret += thread__fprintf(pos, fp);
479         }
480
481         return ret;
482 }
483
484 /*
485  * histogram, sorted on item, collects counts
486  */
487
488 static struct rb_root hist;
489
490 struct hist_entry {
491         struct rb_node   rb_node;
492
493         struct thread    *thread;
494         struct map       *map;
495         struct dso       *dso;
496         struct symbol    *sym;
497         struct symbol    *parent;
498         u64              ip;
499         char             level;
500
501         u64              count;
502 };
503
504 /*
505  * configurable sorting bits
506  */
507
508 struct sort_entry {
509         struct list_head list;
510
511         char *header;
512
513         int64_t (*cmp)(struct hist_entry *, struct hist_entry *);
514         int64_t (*collapse)(struct hist_entry *, struct hist_entry *);
515         size_t  (*print)(FILE *fp, struct hist_entry *);
516 };
517
518 static int64_t cmp_null(void *l, void *r)
519 {
520         if (!l && !r)
521                 return 0;
522         else if (!l)
523                 return -1;
524         else
525                 return 1;
526 }
527
528 /* --sort pid */
529
530 static int64_t
531 sort__thread_cmp(struct hist_entry *left, struct hist_entry *right)
532 {
533         return right->thread->pid - left->thread->pid;
534 }
535
536 static size_t
537 sort__thread_print(FILE *fp, struct hist_entry *self)
538 {
539         return fprintf(fp, "%16s:%5d", self->thread->comm ?: "", self->thread->pid);
540 }
541
542 static struct sort_entry sort_thread = {
543         .header = "         Command:  Pid",
544         .cmp    = sort__thread_cmp,
545         .print  = sort__thread_print,
546 };
547
548 /* --sort comm */
549
550 static int64_t
551 sort__comm_cmp(struct hist_entry *left, struct hist_entry *right)
552 {
553         return right->thread->pid - left->thread->pid;
554 }
555
556 static int64_t
557 sort__comm_collapse(struct hist_entry *left, struct hist_entry *right)
558 {
559         char *comm_l = left->thread->comm;
560         char *comm_r = right->thread->comm;
561
562         if (!comm_l || !comm_r)
563                 return cmp_null(comm_l, comm_r);
564
565         return strcmp(comm_l, comm_r);
566 }
567
568 static size_t
569 sort__comm_print(FILE *fp, struct hist_entry *self)
570 {
571         return fprintf(fp, "%16s", self->thread->comm);
572 }
573
574 static struct sort_entry sort_comm = {
575         .header         = "         Command",
576         .cmp            = sort__comm_cmp,
577         .collapse       = sort__comm_collapse,
578         .print          = sort__comm_print,
579 };
580
581 /* --sort dso */
582
583 static int64_t
584 sort__dso_cmp(struct hist_entry *left, struct hist_entry *right)
585 {
586         struct dso *dso_l = left->dso;
587         struct dso *dso_r = right->dso;
588
589         if (!dso_l || !dso_r)
590                 return cmp_null(dso_l, dso_r);
591
592         return strcmp(dso_l->name, dso_r->name);
593 }
594
595 static size_t
596 sort__dso_print(FILE *fp, struct hist_entry *self)
597 {
598         if (self->dso)
599                 return fprintf(fp, "%-25s", self->dso->name);
600
601         return fprintf(fp, "%016llx         ", (u64)self->ip);
602 }
603
604 static struct sort_entry sort_dso = {
605         .header = "Shared Object            ",
606         .cmp    = sort__dso_cmp,
607         .print  = sort__dso_print,
608 };
609
610 /* --sort symbol */
611
612 static int64_t
613 sort__sym_cmp(struct hist_entry *left, struct hist_entry *right)
614 {
615         u64 ip_l, ip_r;
616
617         if (left->sym == right->sym)
618                 return 0;
619
620         ip_l = left->sym ? left->sym->start : left->ip;
621         ip_r = right->sym ? right->sym->start : right->ip;
622
623         return (int64_t)(ip_r - ip_l);
624 }
625
626 static size_t
627 sort__sym_print(FILE *fp, struct hist_entry *self)
628 {
629         size_t ret = 0;
630
631         if (verbose)
632                 ret += fprintf(fp, "%#018llx  ", (u64)self->ip);
633
634         if (self->sym) {
635                 ret += fprintf(fp, "[%c] %s",
636                         self->dso == kernel_dso ? 'k' : '.', self->sym->name);
637         } else {
638                 ret += fprintf(fp, "%#016llx", (u64)self->ip);
639         }
640
641         return ret;
642 }
643
644 static struct sort_entry sort_sym = {
645         .header = "Symbol",
646         .cmp    = sort__sym_cmp,
647         .print  = sort__sym_print,
648 };
649
650 /* --sort parent */
651
652 static int64_t
653 sort__parent_cmp(struct hist_entry *left, struct hist_entry *right)
654 {
655         struct symbol *sym_l = left->parent;
656         struct symbol *sym_r = right->parent;
657
658         if (!sym_l || !sym_r)
659                 return cmp_null(sym_l, sym_r);
660
661         return strcmp(sym_l->name, sym_r->name);
662 }
663
664 static size_t
665 sort__parent_print(FILE *fp, struct hist_entry *self)
666 {
667         size_t ret = 0;
668
669         ret += fprintf(fp, "%-20s", self->parent ? self->parent->name : "[other]");
670
671         return ret;
672 }
673
674 static struct sort_entry sort_parent = {
675         .header = "Parent symbol       ",
676         .cmp    = sort__parent_cmp,
677         .print  = sort__parent_print,
678 };
679
680 static int sort__need_collapse = 0;
681 static int sort__has_parent = 0;
682
683 struct sort_dimension {
684         char                    *name;
685         struct sort_entry       *entry;
686         int                     taken;
687 };
688
689 static struct sort_dimension sort_dimensions[] = {
690         { .name = "pid",        .entry = &sort_thread,  },
691         { .name = "comm",       .entry = &sort_comm,    },
692         { .name = "dso",        .entry = &sort_dso,     },
693         { .name = "symbol",     .entry = &sort_sym,     },
694         { .name = "parent",     .entry = &sort_parent,  },
695 };
696
697 static LIST_HEAD(hist_entry__sort_list);
698
699 static int sort_dimension__add(char *tok)
700 {
701         int i;
702
703         for (i = 0; i < ARRAY_SIZE(sort_dimensions); i++) {
704                 struct sort_dimension *sd = &sort_dimensions[i];
705
706                 if (sd->taken)
707                         continue;
708
709                 if (strncasecmp(tok, sd->name, strlen(tok)))
710                         continue;
711
712                 if (sd->entry->collapse)
713                         sort__need_collapse = 1;
714
715                 if (sd->entry == &sort_parent) {
716                         int ret = regcomp(&parent_regex, parent_pattern, REG_EXTENDED);
717                         if (ret) {
718                                 char err[BUFSIZ];
719
720                                 regerror(ret, &parent_regex, err, sizeof(err));
721                                 fprintf(stderr, "Invalid regex: %s\n%s",
722                                         parent_pattern, err);
723                                 exit(-1);
724                         }
725                         sort__has_parent = 1;
726                 }
727
728                 list_add_tail(&sd->entry->list, &hist_entry__sort_list);
729                 sd->taken = 1;
730
731                 return 0;
732         }
733
734         return -ESRCH;
735 }
736
737 static int64_t
738 hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
739 {
740         struct sort_entry *se;
741         int64_t cmp = 0;
742
743         list_for_each_entry(se, &hist_entry__sort_list, list) {
744                 cmp = se->cmp(left, right);
745                 if (cmp)
746                         break;
747         }
748
749         return cmp;
750 }
751
752 static int64_t
753 hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
754 {
755         struct sort_entry *se;
756         int64_t cmp = 0;
757
758         list_for_each_entry(se, &hist_entry__sort_list, list) {
759                 int64_t (*f)(struct hist_entry *, struct hist_entry *);
760
761                 f = se->collapse ?: se->cmp;
762
763                 cmp = f(left, right);
764                 if (cmp)
765                         break;
766         }
767
768         return cmp;
769 }
770
771 static size_t
772 hist_entry__fprintf(FILE *fp, struct hist_entry *self, u64 total_samples)
773 {
774         struct sort_entry *se;
775         size_t ret;
776
777         if (exclude_other && !self->parent)
778                 return 0;
779
780         if (total_samples) {
781                 double percent = self->count * 100.0 / total_samples;
782                 char *color = PERF_COLOR_NORMAL;
783
784                 /*
785                  * We color high-overhead entries in red, mid-overhead
786                  * entries in green - and keep the low overhead places
787                  * normal:
788                  */
789                 if (percent >= 5.0) {
790                         color = PERF_COLOR_RED;
791                 } else {
792                         if (percent >= 0.5)
793                                 color = PERF_COLOR_GREEN;
794                 }
795
796                 ret = color_fprintf(fp, color, "   %6.2f%%",
797                                 (self->count * 100.0) / total_samples);
798         } else
799                 ret = fprintf(fp, "%12Ld ", self->count);
800
801         list_for_each_entry(se, &hist_entry__sort_list, list) {
802                 if (exclude_other && (se == &sort_parent))
803                         continue;
804
805                 fprintf(fp, "  ");
806                 ret += se->print(fp, self);
807         }
808
809         ret += fprintf(fp, "\n");
810
811         return ret;
812 }
813
814 /*
815  *
816  */
817
818 static struct symbol *
819 resolve_symbol(struct thread *thread, struct map **mapp,
820                struct dso **dsop, u64 *ipp)
821 {
822         struct dso *dso = dsop ? *dsop : NULL;
823         struct map *map = mapp ? *mapp : NULL;
824         u64 ip = *ipp;
825
826         if (!thread)
827                 return NULL;
828
829         if (dso)
830                 goto got_dso;
831
832         if (map)
833                 goto got_map;
834
835         map = thread__find_map(thread, ip);
836         if (map != NULL) {
837                 if (mapp)
838                         *mapp = map;
839 got_map:
840                 ip = map->map_ip(map, ip);
841
842                 dso = map->dso;
843         } else {
844                 /*
845                  * If this is outside of all known maps,
846                  * and is a negative address, try to look it
847                  * up in the kernel dso, as it might be a
848                  * vsyscall (which executes in user-mode):
849                  */
850                 if ((long long)ip < 0)
851                 dso = kernel_dso;
852         }
853         dprintf(" ...... dso: %s\n", dso ? dso->name : "<not found>");
854         dprintf(" ...... map: %Lx -> %Lx\n", *ipp, ip);
855         *ipp  = ip;
856
857         if (dsop)
858                 *dsop = dso;
859
860         if (!dso)
861                 return NULL;
862 got_dso:
863         return dso->find_symbol(dso, ip);
864 }
865
866 static int call__match(struct symbol *sym)
867 {
868         if (sym->name && !regexec(&parent_regex, sym->name, 0, NULL, 0))
869                 return 1;
870
871         return 0;
872 }
873
874 /*
875  * collect histogram counts
876  */
877
878 static int
879 hist_entry__add(struct thread *thread, struct map *map, struct dso *dso,
880                 struct symbol *sym, u64 ip, struct ip_callchain *chain,
881                 char level, u64 count)
882 {
883         struct rb_node **p = &hist.rb_node;
884         struct rb_node *parent = NULL;
885         struct hist_entry *he;
886         struct hist_entry entry = {
887                 .thread = thread,
888                 .map    = map,
889                 .dso    = dso,
890                 .sym    = sym,
891                 .ip     = ip,
892                 .level  = level,
893                 .count  = count,
894                 .parent = NULL,
895         };
896         int cmp;
897
898         if (sort__has_parent && chain) {
899                 u64 context = PERF_CONTEXT_MAX;
900                 int i;
901
902                 for (i = 0; i < chain->nr; i++) {
903                         u64 ip = chain->ips[i];
904                         struct dso *dso = NULL;
905                         struct symbol *sym;
906
907                         if (ip >= PERF_CONTEXT_MAX) {
908                                 context = ip;
909                                 continue;
910                         }
911
912                         switch (context) {
913                         case PERF_CONTEXT_KERNEL:
914                                 dso = kernel_dso;
915                                 break;
916                         default:
917                                 break;
918                         }
919
920                         sym = resolve_symbol(thread, NULL, &dso, &ip);
921
922                         if (sym && call__match(sym)) {
923                                 entry.parent = sym;
924                                 break;
925                         }
926                 }
927         }
928
929         while (*p != NULL) {
930                 parent = *p;
931                 he = rb_entry(parent, struct hist_entry, rb_node);
932
933                 cmp = hist_entry__cmp(&entry, he);
934
935                 if (!cmp) {
936                         he->count += count;
937                         return 0;
938                 }
939
940                 if (cmp < 0)
941                         p = &(*p)->rb_left;
942                 else
943                         p = &(*p)->rb_right;
944         }
945
946         he = malloc(sizeof(*he));
947         if (!he)
948                 return -ENOMEM;
949         *he = entry;
950         rb_link_node(&he->rb_node, parent, p);
951         rb_insert_color(&he->rb_node, &hist);
952
953         return 0;
954 }
955
956 static void hist_entry__free(struct hist_entry *he)
957 {
958         free(he);
959 }
960
961 /*
962  * collapse the histogram
963  */
964
965 static struct rb_root collapse_hists;
966
967 static void collapse__insert_entry(struct hist_entry *he)
968 {
969         struct rb_node **p = &collapse_hists.rb_node;
970         struct rb_node *parent = NULL;
971         struct hist_entry *iter;
972         int64_t cmp;
973
974         while (*p != NULL) {
975                 parent = *p;
976                 iter = rb_entry(parent, struct hist_entry, rb_node);
977
978                 cmp = hist_entry__collapse(iter, he);
979
980                 if (!cmp) {
981                         iter->count += he->count;
982                         hist_entry__free(he);
983                         return;
984                 }
985
986                 if (cmp < 0)
987                         p = &(*p)->rb_left;
988                 else
989                         p = &(*p)->rb_right;
990         }
991
992         rb_link_node(&he->rb_node, parent, p);
993         rb_insert_color(&he->rb_node, &collapse_hists);
994 }
995
996 static void collapse__resort(void)
997 {
998         struct rb_node *next;
999         struct hist_entry *n;
1000
1001         if (!sort__need_collapse)
1002                 return;
1003
1004         next = rb_first(&hist);
1005         while (next) {
1006                 n = rb_entry(next, struct hist_entry, rb_node);
1007                 next = rb_next(&n->rb_node);
1008
1009                 rb_erase(&n->rb_node, &hist);
1010                 collapse__insert_entry(n);
1011         }
1012 }
1013
1014 /*
1015  * reverse the map, sort on count.
1016  */
1017
1018 static struct rb_root output_hists;
1019
1020 static void output__insert_entry(struct hist_entry *he)
1021 {
1022         struct rb_node **p = &output_hists.rb_node;
1023         struct rb_node *parent = NULL;
1024         struct hist_entry *iter;
1025
1026         while (*p != NULL) {
1027                 parent = *p;
1028                 iter = rb_entry(parent, struct hist_entry, rb_node);
1029
1030                 if (he->count > iter->count)
1031                         p = &(*p)->rb_left;
1032                 else
1033                         p = &(*p)->rb_right;
1034         }
1035
1036         rb_link_node(&he->rb_node, parent, p);
1037         rb_insert_color(&he->rb_node, &output_hists);
1038 }
1039
1040 static void output__resort(void)
1041 {
1042         struct rb_node *next;
1043         struct hist_entry *n;
1044         struct rb_root *tree = &hist;
1045
1046         if (sort__need_collapse)
1047                 tree = &collapse_hists;
1048
1049         next = rb_first(tree);
1050
1051         while (next) {
1052                 n = rb_entry(next, struct hist_entry, rb_node);
1053                 next = rb_next(&n->rb_node);
1054
1055                 rb_erase(&n->rb_node, tree);
1056                 output__insert_entry(n);
1057         }
1058 }
1059
1060 static size_t output__fprintf(FILE *fp, u64 total_samples)
1061 {
1062         struct hist_entry *pos;
1063         struct sort_entry *se;
1064         struct rb_node *nd;
1065         size_t ret = 0;
1066
1067         fprintf(fp, "\n");
1068         fprintf(fp, "#\n");
1069         fprintf(fp, "# (%Ld samples)\n", (u64)total_samples);
1070         fprintf(fp, "#\n");
1071
1072         fprintf(fp, "# Overhead");
1073         list_for_each_entry(se, &hist_entry__sort_list, list) {
1074                 if (exclude_other && (se == &sort_parent))
1075                         continue;
1076                 fprintf(fp, "  %s", se->header);
1077         }
1078         fprintf(fp, "\n");
1079
1080         fprintf(fp, "# ........");
1081         list_for_each_entry(se, &hist_entry__sort_list, list) {
1082                 int i;
1083
1084                 if (exclude_other && (se == &sort_parent))
1085                         continue;
1086
1087                 fprintf(fp, "  ");
1088                 for (i = 0; i < strlen(se->header); i++)
1089                         fprintf(fp, ".");
1090         }
1091         fprintf(fp, "\n");
1092
1093         fprintf(fp, "#\n");
1094
1095         for (nd = rb_first(&output_hists); nd; nd = rb_next(nd)) {
1096                 pos = rb_entry(nd, struct hist_entry, rb_node);
1097                 ret += hist_entry__fprintf(fp, pos, total_samples);
1098         }
1099
1100         if (sort_order == default_sort_order &&
1101                         parent_pattern == default_parent_pattern) {
1102                 fprintf(fp, "#\n");
1103                 fprintf(fp, "# (For more details, try: perf report --sort comm,dso,symbol)\n");
1104                 fprintf(fp, "#\n");
1105         }
1106         fprintf(fp, "\n");
1107
1108         return ret;
1109 }
1110
1111 static void register_idle_thread(void)
1112 {
1113         struct thread *thread = threads__findnew(0);
1114
1115         if (thread == NULL ||
1116                         thread__set_comm(thread, "[idle]")) {
1117                 fprintf(stderr, "problem inserting idle task.\n");
1118                 exit(-1);
1119         }
1120 }
1121
1122 static unsigned long total = 0,
1123                      total_mmap = 0,
1124                      total_comm = 0,
1125                      total_fork = 0,
1126                      total_unknown = 0,
1127                      total_lost = 0;
1128
1129 static int validate_chain(struct ip_callchain *chain, event_t *event)
1130 {
1131         unsigned int chain_size;
1132
1133         chain_size = event->header.size;
1134         chain_size -= (unsigned long)&event->ip.__more_data - (unsigned long)event;
1135
1136         if (chain->nr*sizeof(u64) > chain_size)
1137                 return -1;
1138
1139         return 0;
1140 }
1141
1142 static int
1143 process_sample_event(event_t *event, unsigned long offset, unsigned long head)
1144 {
1145         char level;
1146         int show = 0;
1147         struct dso *dso = NULL;
1148         struct thread *thread = threads__findnew(event->ip.pid);
1149         u64 ip = event->ip.ip;
1150         u64 period = 1;
1151         struct map *map = NULL;
1152         void *more_data = event->ip.__more_data;
1153         struct ip_callchain *chain = NULL;
1154
1155         if (sample_type & PERF_SAMPLE_PERIOD) {
1156                 period = *(u64 *)more_data;
1157                 more_data += sizeof(u64);
1158         }
1159
1160         dprintf("%p [%p]: PERF_EVENT_SAMPLE (IP, %d): %d: %p period: %Ld\n",
1161                 (void *)(offset + head),
1162                 (void *)(long)(event->header.size),
1163                 event->header.misc,
1164                 event->ip.pid,
1165                 (void *)(long)ip,
1166                 (long long)period);
1167
1168         if (sample_type & PERF_SAMPLE_CALLCHAIN) {
1169                 int i;
1170
1171                 chain = (void *)more_data;
1172
1173                 dprintf("... chain: nr:%Lu\n", chain->nr);
1174
1175                 if (validate_chain(chain, event) < 0) {
1176                         eprintf("call-chain problem with event, skipping it.\n");
1177                         return 0;
1178                 }
1179
1180                 if (dump_trace) {
1181                         for (i = 0; i < chain->nr; i++)
1182                                 dprintf("..... %2d: %016Lx\n", i, chain->ips[i]);
1183                 }
1184         }
1185
1186         dprintf(" ... thread: %s:%d\n", thread->comm, thread->pid);
1187
1188         if (thread == NULL) {
1189                 eprintf("problem processing %d event, skipping it.\n",
1190                         event->header.type);
1191                 return -1;
1192         }
1193
1194         if (event->header.misc & PERF_EVENT_MISC_KERNEL) {
1195                 show = SHOW_KERNEL;
1196                 level = 'k';
1197
1198                 dso = kernel_dso;
1199
1200                 dprintf(" ...... dso: %s\n", dso->name);
1201
1202         } else if (event->header.misc & PERF_EVENT_MISC_USER) {
1203
1204                 show = SHOW_USER;
1205                 level = '.';
1206
1207         } else {
1208                 show = SHOW_HV;
1209                 level = 'H';
1210                 dprintf(" ...... dso: [hypervisor]\n");
1211         }
1212
1213         if (show & show_mask) {
1214                 struct symbol *sym = resolve_symbol(thread, &map, &dso, &ip);
1215
1216                 if (hist_entry__add(thread, map, dso, sym, ip, chain, level, period)) {
1217                         eprintf("problem incrementing symbol count, skipping event\n");
1218                         return -1;
1219                 }
1220         }
1221         total += period;
1222
1223         return 0;
1224 }
1225
1226 static int
1227 process_mmap_event(event_t *event, unsigned long offset, unsigned long head)
1228 {
1229         struct thread *thread = threads__findnew(event->mmap.pid);
1230         struct map *map = map__new(&event->mmap);
1231
1232         dprintf("%p [%p]: PERF_EVENT_MMAP %d: [%p(%p) @ %p]: %s\n",
1233                 (void *)(offset + head),
1234                 (void *)(long)(event->header.size),
1235                 event->mmap.pid,
1236                 (void *)(long)event->mmap.start,
1237                 (void *)(long)event->mmap.len,
1238                 (void *)(long)event->mmap.pgoff,
1239                 event->mmap.filename);
1240
1241         if (thread == NULL || map == NULL) {
1242                 dprintf("problem processing PERF_EVENT_MMAP, skipping event.\n");
1243                 return 0;
1244         }
1245
1246         thread__insert_map(thread, map);
1247         total_mmap++;
1248
1249         return 0;
1250 }
1251
1252 static int
1253 process_comm_event(event_t *event, unsigned long offset, unsigned long head)
1254 {
1255         struct thread *thread = threads__findnew(event->comm.pid);
1256
1257         dprintf("%p [%p]: PERF_EVENT_COMM: %s:%d\n",
1258                 (void *)(offset + head),
1259                 (void *)(long)(event->header.size),
1260                 event->comm.comm, event->comm.pid);
1261
1262         if (thread == NULL ||
1263             thread__set_comm(thread, event->comm.comm)) {
1264                 dprintf("problem processing PERF_EVENT_COMM, skipping event.\n");
1265                 return -1;
1266         }
1267         total_comm++;
1268
1269         return 0;
1270 }
1271
1272 static int
1273 process_fork_event(event_t *event, unsigned long offset, unsigned long head)
1274 {
1275         struct thread *thread = threads__findnew(event->fork.pid);
1276         struct thread *parent = threads__findnew(event->fork.ppid);
1277
1278         dprintf("%p [%p]: PERF_EVENT_FORK: %d:%d\n",
1279                 (void *)(offset + head),
1280                 (void *)(long)(event->header.size),
1281                 event->fork.pid, event->fork.ppid);
1282
1283         if (!thread || !parent || thread__fork(thread, parent)) {
1284                 dprintf("problem processing PERF_EVENT_FORK, skipping event.\n");
1285                 return -1;
1286         }
1287         total_fork++;
1288
1289         return 0;
1290 }
1291
1292 static int
1293 process_period_event(event_t *event, unsigned long offset, unsigned long head)
1294 {
1295         dprintf("%p [%p]: PERF_EVENT_PERIOD: time:%Ld, id:%Ld: period:%Ld\n",
1296                 (void *)(offset + head),
1297                 (void *)(long)(event->header.size),
1298                 event->period.time,
1299                 event->period.id,
1300                 event->period.sample_period);
1301
1302         return 0;
1303 }
1304
1305 static int
1306 process_lost_event(event_t *event, unsigned long offset, unsigned long head)
1307 {
1308         dprintf("%p [%p]: PERF_EVENT_LOST: id:%Ld: lost:%Ld\n",
1309                 (void *)(offset + head),
1310                 (void *)(long)(event->header.size),
1311                 event->lost.id,
1312                 event->lost.lost);
1313
1314         total_lost += event->lost.lost;
1315
1316         return 0;
1317 }
1318
1319 static void trace_event(event_t *event)
1320 {
1321         unsigned char *raw_event = (void *)event;
1322         char *color = PERF_COLOR_BLUE;
1323         int i, j;
1324
1325         if (!dump_trace)
1326                 return;
1327
1328         dprintf(".");
1329         cdprintf("\n. ... raw event: size %d bytes\n", event->header.size);
1330
1331         for (i = 0; i < event->header.size; i++) {
1332                 if ((i & 15) == 0) {
1333                         dprintf(".");
1334                         cdprintf("  %04x: ", i);
1335                 }
1336
1337                 cdprintf(" %02x", raw_event[i]);
1338
1339                 if (((i & 15) == 15) || i == event->header.size-1) {
1340                         cdprintf("  ");
1341                         for (j = 0; j < 15-(i & 15); j++)
1342                                 cdprintf("   ");
1343                         for (j = 0; j < (i & 15); j++) {
1344                                 if (isprint(raw_event[i-15+j]))
1345                                         cdprintf("%c", raw_event[i-15+j]);
1346                                 else
1347                                         cdprintf(".");
1348                         }
1349                         cdprintf("\n");
1350                 }
1351         }
1352         dprintf(".\n");
1353 }
1354
1355 static int
1356 process_read_event(event_t *event, unsigned long offset, unsigned long head)
1357 {
1358         dprintf("%p [%p]: PERF_EVENT_READ: %d %d %Lu\n",
1359                         (void *)(offset + head),
1360                         (void *)(long)(event->header.size),
1361                         event->read.pid,
1362                         event->read.tid,
1363                         event->read.value);
1364
1365         return 0;
1366 }
1367
1368 static int
1369 process_event(event_t *event, unsigned long offset, unsigned long head)
1370 {
1371         trace_event(event);
1372
1373         switch (event->header.type) {
1374         case PERF_EVENT_SAMPLE:
1375                 return process_sample_event(event, offset, head);
1376
1377         case PERF_EVENT_MMAP:
1378                 return process_mmap_event(event, offset, head);
1379
1380         case PERF_EVENT_COMM:
1381                 return process_comm_event(event, offset, head);
1382
1383         case PERF_EVENT_FORK:
1384                 return process_fork_event(event, offset, head);
1385
1386         case PERF_EVENT_PERIOD:
1387                 return process_period_event(event, offset, head);
1388
1389         case PERF_EVENT_LOST:
1390                 return process_lost_event(event, offset, head);
1391
1392         case PERF_EVENT_READ:
1393                 return process_read_event(event, offset, head);
1394
1395         /*
1396          * We dont process them right now but they are fine:
1397          */
1398
1399         case PERF_EVENT_THROTTLE:
1400         case PERF_EVENT_UNTHROTTLE:
1401                 return 0;
1402
1403         default:
1404                 return -1;
1405         }
1406
1407         return 0;
1408 }
1409
1410 static struct perf_header       *header;
1411
1412 static u64 perf_header__sample_type(void)
1413 {
1414         u64 sample_type = 0;
1415         int i;
1416
1417         for (i = 0; i < header->attrs; i++) {
1418                 struct perf_header_attr *attr = header->attr[i];
1419
1420                 if (!sample_type)
1421                         sample_type = attr->attr.sample_type;
1422                 else if (sample_type != attr->attr.sample_type)
1423                         die("non matching sample_type");
1424         }
1425
1426         return sample_type;
1427 }
1428
1429 static int __cmd_report(void)
1430 {
1431         int ret, rc = EXIT_FAILURE;
1432         unsigned long offset = 0;
1433         unsigned long head, shift;
1434         struct stat stat;
1435         event_t *event;
1436         uint32_t size;
1437         char *buf;
1438
1439         register_idle_thread();
1440
1441         input = open(input_name, O_RDONLY);
1442         if (input < 0) {
1443                 fprintf(stderr, " failed to open file: %s", input_name);
1444                 if (!strcmp(input_name, "perf.data"))
1445                         fprintf(stderr, "  (try 'perf record' first)");
1446                 fprintf(stderr, "\n");
1447                 exit(-1);
1448         }
1449
1450         ret = fstat(input, &stat);
1451         if (ret < 0) {
1452                 perror("failed to stat file");
1453                 exit(-1);
1454         }
1455
1456         if (!stat.st_size) {
1457                 fprintf(stderr, "zero-sized file, nothing to do!\n");
1458                 exit(0);
1459         }
1460
1461         header = perf_header__read(input);
1462         head = header->data_offset;
1463
1464         sample_type = perf_header__sample_type();
1465
1466         if (sort__has_parent && !(sample_type & PERF_SAMPLE_CALLCHAIN)) {
1467                 fprintf(stderr, "selected --sort parent, but no callchain data\n");
1468                 exit(-1);
1469         }
1470
1471         if (load_kernel() < 0) {
1472                 perror("failed to load kernel symbols");
1473                 return EXIT_FAILURE;
1474         }
1475
1476         if (!full_paths) {
1477                 if (getcwd(__cwd, sizeof(__cwd)) == NULL) {
1478                         perror("failed to get the current directory");
1479                         return EXIT_FAILURE;
1480                 }
1481                 cwdlen = strlen(cwd);
1482         } else {
1483                 cwd = NULL;
1484                 cwdlen = 0;
1485         }
1486
1487         shift = page_size * (head / page_size);
1488         offset += shift;
1489         head -= shift;
1490
1491 remap:
1492         buf = (char *)mmap(NULL, page_size * mmap_window, PROT_READ,
1493                            MAP_SHARED, input, offset);
1494         if (buf == MAP_FAILED) {
1495                 perror("failed to mmap file");
1496                 exit(-1);
1497         }
1498
1499 more:
1500         event = (event_t *)(buf + head);
1501
1502         size = event->header.size;
1503         if (!size)
1504                 size = 8;
1505
1506         if (head + event->header.size >= page_size * mmap_window) {
1507                 int ret;
1508
1509                 shift = page_size * (head / page_size);
1510
1511                 ret = munmap(buf, page_size * mmap_window);
1512                 assert(ret == 0);
1513
1514                 offset += shift;
1515                 head -= shift;
1516                 goto remap;
1517         }
1518
1519         size = event->header.size;
1520
1521         dprintf("\n%p [%p]: event: %d\n",
1522                         (void *)(offset + head),
1523                         (void *)(long)event->header.size,
1524                         event->header.type);
1525
1526         if (!size || process_event(event, offset, head) < 0) {
1527
1528                 dprintf("%p [%p]: skipping unknown header type: %d\n",
1529                         (void *)(offset + head),
1530                         (void *)(long)(event->header.size),
1531                         event->header.type);
1532
1533                 total_unknown++;
1534
1535                 /*
1536                  * assume we lost track of the stream, check alignment, and
1537                  * increment a single u64 in the hope to catch on again 'soon'.
1538                  */
1539
1540                 if (unlikely(head & 7))
1541                         head &= ~7ULL;
1542
1543                 size = 8;
1544         }
1545
1546         head += size;
1547
1548         if (offset + head >= header->data_offset + header->data_size)
1549                 goto done;
1550
1551         if (offset + head < stat.st_size)
1552                 goto more;
1553
1554 done:
1555         rc = EXIT_SUCCESS;
1556         close(input);
1557
1558         dprintf("      IP events: %10ld\n", total);
1559         dprintf("    mmap events: %10ld\n", total_mmap);
1560         dprintf("    comm events: %10ld\n", total_comm);
1561         dprintf("    fork events: %10ld\n", total_fork);
1562         dprintf("    lost events: %10ld\n", total_lost);
1563         dprintf(" unknown events: %10ld\n", total_unknown);
1564
1565         if (dump_trace)
1566                 return 0;
1567
1568         if (verbose >= 3)
1569                 threads__fprintf(stdout);
1570
1571         if (verbose >= 2)
1572                 dsos__fprintf(stdout);
1573
1574         collapse__resort();
1575         output__resort();
1576         output__fprintf(stdout, total);
1577
1578         return rc;
1579 }
1580
1581 static const char * const report_usage[] = {
1582         "perf report [<options>] <command>",
1583         NULL
1584 };
1585
1586 static const struct option options[] = {
1587         OPT_STRING('i', "input", &input_name, "file",
1588                     "input file name"),
1589         OPT_BOOLEAN('v', "verbose", &verbose,
1590                     "be more verbose (show symbol address, etc)"),
1591         OPT_BOOLEAN('D', "dump-raw-trace", &dump_trace,
1592                     "dump raw trace in ASCII"),
1593         OPT_STRING('k', "vmlinux", &vmlinux, "file", "vmlinux pathname"),
1594         OPT_STRING('s', "sort", &sort_order, "key[,key2...]",
1595                    "sort by key(s): pid, comm, dso, symbol, parent"),
1596         OPT_BOOLEAN('P', "full-paths", &full_paths,
1597                     "Don't shorten the pathnames taking into account the cwd"),
1598         OPT_STRING('p', "parent", &parent_pattern, "regex",
1599                    "regex filter to identify parent, see: '--sort parent'"),
1600         OPT_BOOLEAN('x', "exclude-other", &exclude_other,
1601                     "Only display entries with parent-match"),
1602         OPT_END()
1603 };
1604
1605 static void setup_sorting(void)
1606 {
1607         char *tmp, *tok, *str = strdup(sort_order);
1608
1609         for (tok = strtok_r(str, ", ", &tmp);
1610                         tok; tok = strtok_r(NULL, ", ", &tmp)) {
1611                 if (sort_dimension__add(tok) < 0) {
1612                         error("Unknown --sort key: `%s'", tok);
1613                         usage_with_options(report_usage, options);
1614                 }
1615         }
1616
1617         free(str);
1618 }
1619
1620 int cmd_report(int argc, const char **argv, const char *prefix)
1621 {
1622         symbol__init();
1623
1624         page_size = getpagesize();
1625
1626         argc = parse_options(argc, argv, options, report_usage, 0);
1627
1628         setup_sorting();
1629
1630         if (parent_pattern != default_parent_pattern)
1631                 sort_dimension__add("parent");
1632         else
1633                 exclude_other = 0;
1634
1635         /*
1636          * Any (unrecognized) arguments left?
1637          */
1638         if (argc)
1639                 usage_with_options(report_usage, options);
1640
1641         setup_pager();
1642
1643         return __cmd_report();
1644 }