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

TOMOYO Linux Cross Reference
Linux/tools/perf/util/callchain.c

Version: ~ [ linux-5.8-rc3 ] ~ [ linux-5.7.5 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.48 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.129 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.185 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.228 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.228 ] ~ [ 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.85 ] ~ [ 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-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  * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
  3  *
  4  * Handle the callchains from the stream in an ad-hoc radix tree and then
  5  * sort them in an rbtree.
  6  *
  7  * Using a radix for code path provides a fast retrieval and factorizes
  8  * memory use. Also that lets us use the paths in a hierarchical graph view.
  9  *
 10  */
 11 
 12 #include <stdlib.h>
 13 #include <stdio.h>
 14 #include <stdbool.h>
 15 #include <errno.h>
 16 #include <math.h>
 17 
 18 #include "asm/bug.h"
 19 
 20 #include "hist.h"
 21 #include "util.h"
 22 #include "sort.h"
 23 #include "machine.h"
 24 #include "callchain.h"
 25 
 26 __thread struct callchain_cursor callchain_cursor;
 27 
 28 int
 29 parse_callchain_report_opt(const char *arg)
 30 {
 31         char *tok, *tok2;
 32         char *endptr;
 33 
 34         symbol_conf.use_callchain = true;
 35 
 36         if (!arg)
 37                 return 0;
 38 
 39         tok = strtok((char *)arg, ",");
 40         if (!tok)
 41                 return -1;
 42 
 43         /* get the output mode */
 44         if (!strncmp(tok, "graph", strlen(arg))) {
 45                 callchain_param.mode = CHAIN_GRAPH_ABS;
 46 
 47         } else if (!strncmp(tok, "flat", strlen(arg))) {
 48                 callchain_param.mode = CHAIN_FLAT;
 49         } else if (!strncmp(tok, "fractal", strlen(arg))) {
 50                 callchain_param.mode = CHAIN_GRAPH_REL;
 51         } else if (!strncmp(tok, "none", strlen(arg))) {
 52                 callchain_param.mode = CHAIN_NONE;
 53                 symbol_conf.use_callchain = false;
 54                 return 0;
 55         } else {
 56                 return -1;
 57         }
 58 
 59         /* get the min percentage */
 60         tok = strtok(NULL, ",");
 61         if (!tok)
 62                 goto setup;
 63 
 64         callchain_param.min_percent = strtod(tok, &endptr);
 65         if (tok == endptr)
 66                 return -1;
 67 
 68         /* get the print limit */
 69         tok2 = strtok(NULL, ",");
 70         if (!tok2)
 71                 goto setup;
 72 
 73         if (tok2[0] != 'c') {
 74                 callchain_param.print_limit = strtoul(tok2, &endptr, 0);
 75                 tok2 = strtok(NULL, ",");
 76                 if (!tok2)
 77                         goto setup;
 78         }
 79 
 80         /* get the call chain order */
 81         if (!strncmp(tok2, "caller", strlen("caller")))
 82                 callchain_param.order = ORDER_CALLER;
 83         else if (!strncmp(tok2, "callee", strlen("callee")))
 84                 callchain_param.order = ORDER_CALLEE;
 85         else
 86                 return -1;
 87 
 88         /* Get the sort key */
 89         tok2 = strtok(NULL, ",");
 90         if (!tok2)
 91                 goto setup;
 92         if (!strncmp(tok2, "function", strlen("function")))
 93                 callchain_param.key = CCKEY_FUNCTION;
 94         else if (!strncmp(tok2, "address", strlen("address")))
 95                 callchain_param.key = CCKEY_ADDRESS;
 96         else
 97                 return -1;
 98 setup:
 99         if (callchain_register_param(&callchain_param) < 0) {
100                 pr_err("Can't register callchain params\n");
101                 return -1;
102         }
103         return 0;
104 }
105 
106 static void
107 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
108                     enum chain_mode mode)
109 {
110         struct rb_node **p = &root->rb_node;
111         struct rb_node *parent = NULL;
112         struct callchain_node *rnode;
113         u64 chain_cumul = callchain_cumul_hits(chain);
114 
115         while (*p) {
116                 u64 rnode_cumul;
117 
118                 parent = *p;
119                 rnode = rb_entry(parent, struct callchain_node, rb_node);
120                 rnode_cumul = callchain_cumul_hits(rnode);
121 
122                 switch (mode) {
123                 case CHAIN_FLAT:
124                         if (rnode->hit < chain->hit)
125                                 p = &(*p)->rb_left;
126                         else
127                                 p = &(*p)->rb_right;
128                         break;
129                 case CHAIN_GRAPH_ABS: /* Falldown */
130                 case CHAIN_GRAPH_REL:
131                         if (rnode_cumul < chain_cumul)
132                                 p = &(*p)->rb_left;
133                         else
134                                 p = &(*p)->rb_right;
135                         break;
136                 case CHAIN_NONE:
137                 default:
138                         break;
139                 }
140         }
141 
142         rb_link_node(&chain->rb_node, parent, p);
143         rb_insert_color(&chain->rb_node, root);
144 }
145 
146 static void
147 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
148                   u64 min_hit)
149 {
150         struct rb_node *n;
151         struct callchain_node *child;
152 
153         n = rb_first(&node->rb_root_in);
154         while (n) {
155                 child = rb_entry(n, struct callchain_node, rb_node_in);
156                 n = rb_next(n);
157 
158                 __sort_chain_flat(rb_root, child, min_hit);
159         }
160 
161         if (node->hit && node->hit >= min_hit)
162                 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
163 }
164 
165 /*
166  * Once we get every callchains from the stream, we can now
167  * sort them by hit
168  */
169 static void
170 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
171                 u64 min_hit, struct callchain_param *param __maybe_unused)
172 {
173         __sort_chain_flat(rb_root, &root->node, min_hit);
174 }
175 
176 static void __sort_chain_graph_abs(struct callchain_node *node,
177                                    u64 min_hit)
178 {
179         struct rb_node *n;
180         struct callchain_node *child;
181 
182         node->rb_root = RB_ROOT;
183         n = rb_first(&node->rb_root_in);
184 
185         while (n) {
186                 child = rb_entry(n, struct callchain_node, rb_node_in);
187                 n = rb_next(n);
188 
189                 __sort_chain_graph_abs(child, min_hit);
190                 if (callchain_cumul_hits(child) >= min_hit)
191                         rb_insert_callchain(&node->rb_root, child,
192                                             CHAIN_GRAPH_ABS);
193         }
194 }
195 
196 static void
197 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
198                      u64 min_hit, struct callchain_param *param __maybe_unused)
199 {
200         __sort_chain_graph_abs(&chain_root->node, min_hit);
201         rb_root->rb_node = chain_root->node.rb_root.rb_node;
202 }
203 
204 static void __sort_chain_graph_rel(struct callchain_node *node,
205                                    double min_percent)
206 {
207         struct rb_node *n;
208         struct callchain_node *child;
209         u64 min_hit;
210 
211         node->rb_root = RB_ROOT;
212         min_hit = ceil(node->children_hit * min_percent);
213 
214         n = rb_first(&node->rb_root_in);
215         while (n) {
216                 child = rb_entry(n, struct callchain_node, rb_node_in);
217                 n = rb_next(n);
218 
219                 __sort_chain_graph_rel(child, min_percent);
220                 if (callchain_cumul_hits(child) >= min_hit)
221                         rb_insert_callchain(&node->rb_root, child,
222                                             CHAIN_GRAPH_REL);
223         }
224 }
225 
226 static void
227 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
228                      u64 min_hit __maybe_unused, struct callchain_param *param)
229 {
230         __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
231         rb_root->rb_node = chain_root->node.rb_root.rb_node;
232 }
233 
234 int callchain_register_param(struct callchain_param *param)
235 {
236         switch (param->mode) {
237         case CHAIN_GRAPH_ABS:
238                 param->sort = sort_chain_graph_abs;
239                 break;
240         case CHAIN_GRAPH_REL:
241                 param->sort = sort_chain_graph_rel;
242                 break;
243         case CHAIN_FLAT:
244                 param->sort = sort_chain_flat;
245                 break;
246         case CHAIN_NONE:
247         default:
248                 return -1;
249         }
250         return 0;
251 }
252 
253 /*
254  * Create a child for a parent. If inherit_children, then the new child
255  * will become the new parent of it's parent children
256  */
257 static struct callchain_node *
258 create_child(struct callchain_node *parent, bool inherit_children)
259 {
260         struct callchain_node *new;
261 
262         new = zalloc(sizeof(*new));
263         if (!new) {
264                 perror("not enough memory to create child for code path tree");
265                 return NULL;
266         }
267         new->parent = parent;
268         INIT_LIST_HEAD(&new->val);
269 
270         if (inherit_children) {
271                 struct rb_node *n;
272                 struct callchain_node *child;
273 
274                 new->rb_root_in = parent->rb_root_in;
275                 parent->rb_root_in = RB_ROOT;
276 
277                 n = rb_first(&new->rb_root_in);
278                 while (n) {
279                         child = rb_entry(n, struct callchain_node, rb_node_in);
280                         child->parent = new;
281                         n = rb_next(n);
282                 }
283 
284                 /* make it the first child */
285                 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
286                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
287         }
288 
289         return new;
290 }
291 
292 
293 /*
294  * Fill the node with callchain values
295  */
296 static void
297 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
298 {
299         struct callchain_cursor_node *cursor_node;
300 
301         node->val_nr = cursor->nr - cursor->pos;
302         if (!node->val_nr)
303                 pr_warning("Warning: empty node in callchain tree\n");
304 
305         cursor_node = callchain_cursor_current(cursor);
306 
307         while (cursor_node) {
308                 struct callchain_list *call;
309 
310                 call = zalloc(sizeof(*call));
311                 if (!call) {
312                         perror("not enough memory for the code path tree");
313                         return;
314                 }
315                 call->ip = cursor_node->ip;
316                 call->ms.sym = cursor_node->sym;
317                 call->ms.map = cursor_node->map;
318                 list_add_tail(&call->list, &node->val);
319 
320                 callchain_cursor_advance(cursor);
321                 cursor_node = callchain_cursor_current(cursor);
322         }
323 }
324 
325 static struct callchain_node *
326 add_child(struct callchain_node *parent,
327           struct callchain_cursor *cursor,
328           u64 period)
329 {
330         struct callchain_node *new;
331 
332         new = create_child(parent, false);
333         fill_node(new, cursor);
334 
335         new->children_hit = 0;
336         new->hit = period;
337         return new;
338 }
339 
340 static s64 match_chain(struct callchain_cursor_node *node,
341                       struct callchain_list *cnode)
342 {
343         struct symbol *sym = node->sym;
344 
345         if (cnode->ms.sym && sym &&
346             callchain_param.key == CCKEY_FUNCTION)
347                 return cnode->ms.sym->start - sym->start;
348         else
349                 return cnode->ip - node->ip;
350 }
351 
352 /*
353  * Split the parent in two parts (a new child is created) and
354  * give a part of its callchain to the created child.
355  * Then create another child to host the given callchain of new branch
356  */
357 static void
358 split_add_child(struct callchain_node *parent,
359                 struct callchain_cursor *cursor,
360                 struct callchain_list *to_split,
361                 u64 idx_parents, u64 idx_local, u64 period)
362 {
363         struct callchain_node *new;
364         struct list_head *old_tail;
365         unsigned int idx_total = idx_parents + idx_local;
366 
367         /* split */
368         new = create_child(parent, true);
369 
370         /* split the callchain and move a part to the new child */
371         old_tail = parent->val.prev;
372         list_del_range(&to_split->list, old_tail);
373         new->val.next = &to_split->list;
374         new->val.prev = old_tail;
375         to_split->list.prev = &new->val;
376         old_tail->next = &new->val;
377 
378         /* split the hits */
379         new->hit = parent->hit;
380         new->children_hit = parent->children_hit;
381         parent->children_hit = callchain_cumul_hits(new);
382         new->val_nr = parent->val_nr - idx_local;
383         parent->val_nr = idx_local;
384 
385         /* create a new child for the new branch if any */
386         if (idx_total < cursor->nr) {
387                 struct callchain_node *first;
388                 struct callchain_list *cnode;
389                 struct callchain_cursor_node *node;
390                 struct rb_node *p, **pp;
391 
392                 parent->hit = 0;
393                 parent->children_hit += period;
394 
395                 node = callchain_cursor_current(cursor);
396                 new = add_child(parent, cursor, period);
397 
398                 /*
399                  * This is second child since we moved parent's children
400                  * to new (first) child above.
401                  */
402                 p = parent->rb_root_in.rb_node;
403                 first = rb_entry(p, struct callchain_node, rb_node_in);
404                 cnode = list_first_entry(&first->val, struct callchain_list,
405                                          list);
406 
407                 if (match_chain(node, cnode) < 0)
408                         pp = &p->rb_left;
409                 else
410                         pp = &p->rb_right;
411 
412                 rb_link_node(&new->rb_node_in, p, pp);
413                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
414         } else {
415                 parent->hit = period;
416         }
417 }
418 
419 static int
420 append_chain(struct callchain_node *root,
421              struct callchain_cursor *cursor,
422              u64 period);
423 
424 static void
425 append_chain_children(struct callchain_node *root,
426                       struct callchain_cursor *cursor,
427                       u64 period)
428 {
429         struct callchain_node *rnode;
430         struct callchain_cursor_node *node;
431         struct rb_node **p = &root->rb_root_in.rb_node;
432         struct rb_node *parent = NULL;
433 
434         node = callchain_cursor_current(cursor);
435         if (!node)
436                 return;
437 
438         /* lookup in childrens */
439         while (*p) {
440                 s64 ret;
441 
442                 parent = *p;
443                 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
444 
445                 /* If at least first entry matches, rely to children */
446                 ret = append_chain(rnode, cursor, period);
447                 if (ret == 0)
448                         goto inc_children_hit;
449 
450                 if (ret < 0)
451                         p = &parent->rb_left;
452                 else
453                         p = &parent->rb_right;
454         }
455         /* nothing in children, add to the current node */
456         rnode = add_child(root, cursor, period);
457         rb_link_node(&rnode->rb_node_in, parent, p);
458         rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
459 
460 inc_children_hit:
461         root->children_hit += period;
462 }
463 
464 static int
465 append_chain(struct callchain_node *root,
466              struct callchain_cursor *cursor,
467              u64 period)
468 {
469         struct callchain_list *cnode;
470         u64 start = cursor->pos;
471         bool found = false;
472         u64 matches;
473         int cmp = 0;
474 
475         /*
476          * Lookup in the current node
477          * If we have a symbol, then compare the start to match
478          * anywhere inside a function, unless function
479          * mode is disabled.
480          */
481         list_for_each_entry(cnode, &root->val, list) {
482                 struct callchain_cursor_node *node;
483 
484                 node = callchain_cursor_current(cursor);
485                 if (!node)
486                         break;
487 
488                 cmp = match_chain(node, cnode);
489                 if (cmp)
490                         break;
491 
492                 found = true;
493 
494                 callchain_cursor_advance(cursor);
495         }
496 
497         /* matches not, relay no the parent */
498         if (!found) {
499                 WARN_ONCE(!cmp, "Chain comparison error\n");
500                 return cmp;
501         }
502 
503         matches = cursor->pos - start;
504 
505         /* we match only a part of the node. Split it and add the new chain */
506         if (matches < root->val_nr) {
507                 split_add_child(root, cursor, cnode, start, matches, period);
508                 return 0;
509         }
510 
511         /* we match 100% of the path, increment the hit */
512         if (matches == root->val_nr && cursor->pos == cursor->nr) {
513                 root->hit += period;
514                 return 0;
515         }
516 
517         /* We match the node and still have a part remaining */
518         append_chain_children(root, cursor, period);
519 
520         return 0;
521 }
522 
523 int callchain_append(struct callchain_root *root,
524                      struct callchain_cursor *cursor,
525                      u64 period)
526 {
527         if (!cursor->nr)
528                 return 0;
529 
530         callchain_cursor_commit(cursor);
531 
532         append_chain_children(&root->node, cursor, period);
533 
534         if (cursor->nr > root->max_depth)
535                 root->max_depth = cursor->nr;
536 
537         return 0;
538 }
539 
540 static int
541 merge_chain_branch(struct callchain_cursor *cursor,
542                    struct callchain_node *dst, struct callchain_node *src)
543 {
544         struct callchain_cursor_node **old_last = cursor->last;
545         struct callchain_node *child;
546         struct callchain_list *list, *next_list;
547         struct rb_node *n;
548         int old_pos = cursor->nr;
549         int err = 0;
550 
551         list_for_each_entry_safe(list, next_list, &src->val, list) {
552                 callchain_cursor_append(cursor, list->ip,
553                                         list->ms.map, list->ms.sym);
554                 list_del(&list->list);
555                 free(list);
556         }
557 
558         if (src->hit) {
559                 callchain_cursor_commit(cursor);
560                 append_chain_children(dst, cursor, src->hit);
561         }
562 
563         n = rb_first(&src->rb_root_in);
564         while (n) {
565                 child = container_of(n, struct callchain_node, rb_node_in);
566                 n = rb_next(n);
567                 rb_erase(&child->rb_node_in, &src->rb_root_in);
568 
569                 err = merge_chain_branch(cursor, dst, child);
570                 if (err)
571                         break;
572 
573                 free(child);
574         }
575 
576         cursor->nr = old_pos;
577         cursor->last = old_last;
578 
579         return err;
580 }
581 
582 int callchain_merge(struct callchain_cursor *cursor,
583                     struct callchain_root *dst, struct callchain_root *src)
584 {
585         return merge_chain_branch(cursor, &dst->node, &src->node);
586 }
587 
588 int callchain_cursor_append(struct callchain_cursor *cursor,
589                             u64 ip, struct map *map, struct symbol *sym)
590 {
591         struct callchain_cursor_node *node = *cursor->last;
592 
593         if (!node) {
594                 node = calloc(1, sizeof(*node));
595                 if (!node)
596                         return -ENOMEM;
597 
598                 *cursor->last = node;
599         }
600 
601         node->ip = ip;
602         node->map = map;
603         node->sym = sym;
604 
605         cursor->nr++;
606 
607         cursor->last = &node->next;
608 
609         return 0;
610 }
611 
612 int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
613                               struct perf_evsel *evsel, struct addr_location *al,
614                               int max_stack)
615 {
616         if (sample->callchain == NULL)
617                 return 0;
618 
619         if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
620             sort__has_parent) {
621                 return machine__resolve_callchain(al->machine, evsel, al->thread,
622                                                   sample, parent, al, max_stack);
623         }
624         return 0;
625 }
626 
627 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
628 {
629         if (!symbol_conf.use_callchain || sample->callchain == NULL)
630                 return 0;
631         return callchain_append(he->callchain, &callchain_cursor, sample->period);
632 }
633 
634 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
635                         bool hide_unresolved)
636 {
637         al->map = node->map;
638         al->sym = node->sym;
639         if (node->map)
640                 al->addr = node->map->map_ip(node->map, node->ip);
641         else
642                 al->addr = node->ip;
643 
644         if (al->sym == NULL) {
645                 if (hide_unresolved)
646                         return 0;
647                 if (al->map == NULL)
648                         goto out;
649         }
650 
651         if (al->map->groups == &al->machine->kmaps) {
652                 if (machine__is_host(al->machine)) {
653                         al->cpumode = PERF_RECORD_MISC_KERNEL;
654                         al->level = 'k';
655                 } else {
656                         al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
657                         al->level = 'g';
658                 }
659         } else {
660                 if (machine__is_host(al->machine)) {
661                         al->cpumode = PERF_RECORD_MISC_USER;
662                         al->level = '.';
663                 } else if (perf_guest) {
664                         al->cpumode = PERF_RECORD_MISC_GUEST_USER;
665                         al->level = 'u';
666                 } else {
667                         al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
668                         al->level = 'H';
669                 }
670         }
671 
672 out:
673         return 1;
674 }
675 

~ [ 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