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

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

Version: ~ [ linux-5.8-rc4 ] ~ [ linux-5.7.7 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.50 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.131 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.187 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.229 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.229 ] ~ [ 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 parse_callchain_record_opt(const char *arg, struct callchain_param *param)
 29 {
 30         return parse_callchain_record(arg, param);
 31 }
 32 
 33 static int parse_callchain_mode(const char *value)
 34 {
 35         if (!strncmp(value, "graph", strlen(value))) {
 36                 callchain_param.mode = CHAIN_GRAPH_ABS;
 37                 return 0;
 38         }
 39         if (!strncmp(value, "flat", strlen(value))) {
 40                 callchain_param.mode = CHAIN_FLAT;
 41                 return 0;
 42         }
 43         if (!strncmp(value, "fractal", strlen(value))) {
 44                 callchain_param.mode = CHAIN_GRAPH_REL;
 45                 return 0;
 46         }
 47         if (!strncmp(value, "folded", strlen(value))) {
 48                 callchain_param.mode = CHAIN_FOLDED;
 49                 return 0;
 50         }
 51         return -1;
 52 }
 53 
 54 static int parse_callchain_order(const char *value)
 55 {
 56         if (!strncmp(value, "caller", strlen(value))) {
 57                 callchain_param.order = ORDER_CALLER;
 58                 callchain_param.order_set = true;
 59                 return 0;
 60         }
 61         if (!strncmp(value, "callee", strlen(value))) {
 62                 callchain_param.order = ORDER_CALLEE;
 63                 callchain_param.order_set = true;
 64                 return 0;
 65         }
 66         return -1;
 67 }
 68 
 69 static int parse_callchain_sort_key(const char *value)
 70 {
 71         if (!strncmp(value, "function", strlen(value))) {
 72                 callchain_param.key = CCKEY_FUNCTION;
 73                 return 0;
 74         }
 75         if (!strncmp(value, "address", strlen(value))) {
 76                 callchain_param.key = CCKEY_ADDRESS;
 77                 return 0;
 78         }
 79         if (!strncmp(value, "branch", strlen(value))) {
 80                 callchain_param.branch_callstack = 1;
 81                 return 0;
 82         }
 83         return -1;
 84 }
 85 
 86 static int parse_callchain_value(const char *value)
 87 {
 88         if (!strncmp(value, "percent", strlen(value))) {
 89                 callchain_param.value = CCVAL_PERCENT;
 90                 return 0;
 91         }
 92         if (!strncmp(value, "period", strlen(value))) {
 93                 callchain_param.value = CCVAL_PERIOD;
 94                 return 0;
 95         }
 96         if (!strncmp(value, "count", strlen(value))) {
 97                 callchain_param.value = CCVAL_COUNT;
 98                 return 0;
 99         }
100         return -1;
101 }
102 
103 static int
104 __parse_callchain_report_opt(const char *arg, bool allow_record_opt)
105 {
106         char *tok;
107         char *endptr;
108         bool minpcnt_set = false;
109         bool record_opt_set = false;
110         bool try_stack_size = false;
111 
112         symbol_conf.use_callchain = true;
113 
114         if (!arg)
115                 return 0;
116 
117         while ((tok = strtok((char *)arg, ",")) != NULL) {
118                 if (!strncmp(tok, "none", strlen(tok))) {
119                         callchain_param.mode = CHAIN_NONE;
120                         symbol_conf.use_callchain = false;
121                         return 0;
122                 }
123 
124                 if (!parse_callchain_mode(tok) ||
125                     !parse_callchain_order(tok) ||
126                     !parse_callchain_sort_key(tok) ||
127                     !parse_callchain_value(tok)) {
128                         /* parsing ok - move on to the next */
129                         try_stack_size = false;
130                         goto next;
131                 } else if (allow_record_opt && !record_opt_set) {
132                         if (parse_callchain_record(tok, &callchain_param))
133                                 goto try_numbers;
134 
135                         /* assume that number followed by 'dwarf' is stack size */
136                         if (callchain_param.record_mode == CALLCHAIN_DWARF)
137                                 try_stack_size = true;
138 
139                         record_opt_set = true;
140                         goto next;
141                 }
142 
143 try_numbers:
144                 if (try_stack_size) {
145                         unsigned long size = 0;
146 
147                         if (get_stack_size(tok, &size) < 0)
148                                 return -1;
149                         callchain_param.dump_size = size;
150                         try_stack_size = false;
151                 } else if (!minpcnt_set) {
152                         /* try to get the min percent */
153                         callchain_param.min_percent = strtod(tok, &endptr);
154                         if (tok == endptr)
155                                 return -1;
156                         minpcnt_set = true;
157                 } else {
158                         /* try print limit at last */
159                         callchain_param.print_limit = strtoul(tok, &endptr, 0);
160                         if (tok == endptr)
161                                 return -1;
162                 }
163 next:
164                 arg = NULL;
165         }
166 
167         if (callchain_register_param(&callchain_param) < 0) {
168                 pr_err("Can't register callchain params\n");
169                 return -1;
170         }
171         return 0;
172 }
173 
174 int parse_callchain_report_opt(const char *arg)
175 {
176         return __parse_callchain_report_opt(arg, false);
177 }
178 
179 int parse_callchain_top_opt(const char *arg)
180 {
181         return __parse_callchain_report_opt(arg, true);
182 }
183 
184 int perf_callchain_config(const char *var, const char *value)
185 {
186         char *endptr;
187 
188         if (prefixcmp(var, "call-graph."))
189                 return 0;
190         var += sizeof("call-graph.") - 1;
191 
192         if (!strcmp(var, "record-mode"))
193                 return parse_callchain_record_opt(value, &callchain_param);
194 #ifdef HAVE_DWARF_UNWIND_SUPPORT
195         if (!strcmp(var, "dump-size")) {
196                 unsigned long size = 0;
197                 int ret;
198 
199                 ret = get_stack_size(value, &size);
200                 callchain_param.dump_size = size;
201 
202                 return ret;
203         }
204 #endif
205         if (!strcmp(var, "print-type"))
206                 return parse_callchain_mode(value);
207         if (!strcmp(var, "order"))
208                 return parse_callchain_order(value);
209         if (!strcmp(var, "sort-key"))
210                 return parse_callchain_sort_key(value);
211         if (!strcmp(var, "threshold")) {
212                 callchain_param.min_percent = strtod(value, &endptr);
213                 if (value == endptr)
214                         return -1;
215         }
216         if (!strcmp(var, "print-limit")) {
217                 callchain_param.print_limit = strtod(value, &endptr);
218                 if (value == endptr)
219                         return -1;
220         }
221 
222         return 0;
223 }
224 
225 static void
226 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
227                     enum chain_mode mode)
228 {
229         struct rb_node **p = &root->rb_node;
230         struct rb_node *parent = NULL;
231         struct callchain_node *rnode;
232         u64 chain_cumul = callchain_cumul_hits(chain);
233 
234         while (*p) {
235                 u64 rnode_cumul;
236 
237                 parent = *p;
238                 rnode = rb_entry(parent, struct callchain_node, rb_node);
239                 rnode_cumul = callchain_cumul_hits(rnode);
240 
241                 switch (mode) {
242                 case CHAIN_FLAT:
243                 case CHAIN_FOLDED:
244                         if (rnode->hit < chain->hit)
245                                 p = &(*p)->rb_left;
246                         else
247                                 p = &(*p)->rb_right;
248                         break;
249                 case CHAIN_GRAPH_ABS: /* Falldown */
250                 case CHAIN_GRAPH_REL:
251                         if (rnode_cumul < chain_cumul)
252                                 p = &(*p)->rb_left;
253                         else
254                                 p = &(*p)->rb_right;
255                         break;
256                 case CHAIN_NONE:
257                 default:
258                         break;
259                 }
260         }
261 
262         rb_link_node(&chain->rb_node, parent, p);
263         rb_insert_color(&chain->rb_node, root);
264 }
265 
266 static void
267 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
268                   u64 min_hit)
269 {
270         struct rb_node *n;
271         struct callchain_node *child;
272 
273         n = rb_first(&node->rb_root_in);
274         while (n) {
275                 child = rb_entry(n, struct callchain_node, rb_node_in);
276                 n = rb_next(n);
277 
278                 __sort_chain_flat(rb_root, child, min_hit);
279         }
280 
281         if (node->hit && node->hit >= min_hit)
282                 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
283 }
284 
285 /*
286  * Once we get every callchains from the stream, we can now
287  * sort them by hit
288  */
289 static void
290 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
291                 u64 min_hit, struct callchain_param *param __maybe_unused)
292 {
293         *rb_root = RB_ROOT;
294         __sort_chain_flat(rb_root, &root->node, min_hit);
295 }
296 
297 static void __sort_chain_graph_abs(struct callchain_node *node,
298                                    u64 min_hit)
299 {
300         struct rb_node *n;
301         struct callchain_node *child;
302 
303         node->rb_root = RB_ROOT;
304         n = rb_first(&node->rb_root_in);
305 
306         while (n) {
307                 child = rb_entry(n, struct callchain_node, rb_node_in);
308                 n = rb_next(n);
309 
310                 __sort_chain_graph_abs(child, min_hit);
311                 if (callchain_cumul_hits(child) >= min_hit)
312                         rb_insert_callchain(&node->rb_root, child,
313                                             CHAIN_GRAPH_ABS);
314         }
315 }
316 
317 static void
318 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
319                      u64 min_hit, struct callchain_param *param __maybe_unused)
320 {
321         __sort_chain_graph_abs(&chain_root->node, min_hit);
322         rb_root->rb_node = chain_root->node.rb_root.rb_node;
323 }
324 
325 static void __sort_chain_graph_rel(struct callchain_node *node,
326                                    double min_percent)
327 {
328         struct rb_node *n;
329         struct callchain_node *child;
330         u64 min_hit;
331 
332         node->rb_root = RB_ROOT;
333         min_hit = ceil(node->children_hit * min_percent);
334 
335         n = rb_first(&node->rb_root_in);
336         while (n) {
337                 child = rb_entry(n, struct callchain_node, rb_node_in);
338                 n = rb_next(n);
339 
340                 __sort_chain_graph_rel(child, min_percent);
341                 if (callchain_cumul_hits(child) >= min_hit)
342                         rb_insert_callchain(&node->rb_root, child,
343                                             CHAIN_GRAPH_REL);
344         }
345 }
346 
347 static void
348 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
349                      u64 min_hit __maybe_unused, struct callchain_param *param)
350 {
351         __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
352         rb_root->rb_node = chain_root->node.rb_root.rb_node;
353 }
354 
355 int callchain_register_param(struct callchain_param *param)
356 {
357         switch (param->mode) {
358         case CHAIN_GRAPH_ABS:
359                 param->sort = sort_chain_graph_abs;
360                 break;
361         case CHAIN_GRAPH_REL:
362                 param->sort = sort_chain_graph_rel;
363                 break;
364         case CHAIN_FLAT:
365         case CHAIN_FOLDED:
366                 param->sort = sort_chain_flat;
367                 break;
368         case CHAIN_NONE:
369         default:
370                 return -1;
371         }
372         return 0;
373 }
374 
375 /*
376  * Create a child for a parent. If inherit_children, then the new child
377  * will become the new parent of it's parent children
378  */
379 static struct callchain_node *
380 create_child(struct callchain_node *parent, bool inherit_children)
381 {
382         struct callchain_node *new;
383 
384         new = zalloc(sizeof(*new));
385         if (!new) {
386                 perror("not enough memory to create child for code path tree");
387                 return NULL;
388         }
389         new->parent = parent;
390         INIT_LIST_HEAD(&new->val);
391         INIT_LIST_HEAD(&new->parent_val);
392 
393         if (inherit_children) {
394                 struct rb_node *n;
395                 struct callchain_node *child;
396 
397                 new->rb_root_in = parent->rb_root_in;
398                 parent->rb_root_in = RB_ROOT;
399 
400                 n = rb_first(&new->rb_root_in);
401                 while (n) {
402                         child = rb_entry(n, struct callchain_node, rb_node_in);
403                         child->parent = new;
404                         n = rb_next(n);
405                 }
406 
407                 /* make it the first child */
408                 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
409                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
410         }
411 
412         return new;
413 }
414 
415 
416 /*
417  * Fill the node with callchain values
418  */
419 static void
420 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
421 {
422         struct callchain_cursor_node *cursor_node;
423 
424         node->val_nr = cursor->nr - cursor->pos;
425         if (!node->val_nr)
426                 pr_warning("Warning: empty node in callchain tree\n");
427 
428         cursor_node = callchain_cursor_current(cursor);
429 
430         while (cursor_node) {
431                 struct callchain_list *call;
432 
433                 call = zalloc(sizeof(*call));
434                 if (!call) {
435                         perror("not enough memory for the code path tree");
436                         return;
437                 }
438                 call->ip = cursor_node->ip;
439                 call->ms.sym = cursor_node->sym;
440                 call->ms.map = cursor_node->map;
441                 list_add_tail(&call->list, &node->val);
442 
443                 callchain_cursor_advance(cursor);
444                 cursor_node = callchain_cursor_current(cursor);
445         }
446 }
447 
448 static struct callchain_node *
449 add_child(struct callchain_node *parent,
450           struct callchain_cursor *cursor,
451           u64 period)
452 {
453         struct callchain_node *new;
454 
455         new = create_child(parent, false);
456         fill_node(new, cursor);
457 
458         new->children_hit = 0;
459         new->hit = period;
460         new->children_count = 0;
461         new->count = 1;
462         return new;
463 }
464 
465 static s64 match_chain(struct callchain_cursor_node *node,
466                       struct callchain_list *cnode)
467 {
468         struct symbol *sym = node->sym;
469 
470         if (cnode->ms.sym && sym &&
471             callchain_param.key == CCKEY_FUNCTION)
472                 return cnode->ms.sym->start - sym->start;
473         else
474                 return cnode->ip - node->ip;
475 }
476 
477 /*
478  * Split the parent in two parts (a new child is created) and
479  * give a part of its callchain to the created child.
480  * Then create another child to host the given callchain of new branch
481  */
482 static void
483 split_add_child(struct callchain_node *parent,
484                 struct callchain_cursor *cursor,
485                 struct callchain_list *to_split,
486                 u64 idx_parents, u64 idx_local, u64 period)
487 {
488         struct callchain_node *new;
489         struct list_head *old_tail;
490         unsigned int idx_total = idx_parents + idx_local;
491 
492         /* split */
493         new = create_child(parent, true);
494 
495         /* split the callchain and move a part to the new child */
496         old_tail = parent->val.prev;
497         list_del_range(&to_split->list, old_tail);
498         new->val.next = &to_split->list;
499         new->val.prev = old_tail;
500         to_split->list.prev = &new->val;
501         old_tail->next = &new->val;
502 
503         /* split the hits */
504         new->hit = parent->hit;
505         new->children_hit = parent->children_hit;
506         parent->children_hit = callchain_cumul_hits(new);
507         new->val_nr = parent->val_nr - idx_local;
508         parent->val_nr = idx_local;
509         new->count = parent->count;
510         new->children_count = parent->children_count;
511         parent->children_count = callchain_cumul_counts(new);
512 
513         /* create a new child for the new branch if any */
514         if (idx_total < cursor->nr) {
515                 struct callchain_node *first;
516                 struct callchain_list *cnode;
517                 struct callchain_cursor_node *node;
518                 struct rb_node *p, **pp;
519 
520                 parent->hit = 0;
521                 parent->children_hit += period;
522                 parent->count = 0;
523                 parent->children_count += 1;
524 
525                 node = callchain_cursor_current(cursor);
526                 new = add_child(parent, cursor, period);
527 
528                 /*
529                  * This is second child since we moved parent's children
530                  * to new (first) child above.
531                  */
532                 p = parent->rb_root_in.rb_node;
533                 first = rb_entry(p, struct callchain_node, rb_node_in);
534                 cnode = list_first_entry(&first->val, struct callchain_list,
535                                          list);
536 
537                 if (match_chain(node, cnode) < 0)
538                         pp = &p->rb_left;
539                 else
540                         pp = &p->rb_right;
541 
542                 rb_link_node(&new->rb_node_in, p, pp);
543                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
544         } else {
545                 parent->hit = period;
546                 parent->count = 1;
547         }
548 }
549 
550 static int
551 append_chain(struct callchain_node *root,
552              struct callchain_cursor *cursor,
553              u64 period);
554 
555 static void
556 append_chain_children(struct callchain_node *root,
557                       struct callchain_cursor *cursor,
558                       u64 period)
559 {
560         struct callchain_node *rnode;
561         struct callchain_cursor_node *node;
562         struct rb_node **p = &root->rb_root_in.rb_node;
563         struct rb_node *parent = NULL;
564 
565         node = callchain_cursor_current(cursor);
566         if (!node)
567                 return;
568 
569         /* lookup in childrens */
570         while (*p) {
571                 s64 ret;
572 
573                 parent = *p;
574                 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
575 
576                 /* If at least first entry matches, rely to children */
577                 ret = append_chain(rnode, cursor, period);
578                 if (ret == 0)
579                         goto inc_children_hit;
580 
581                 if (ret < 0)
582                         p = &parent->rb_left;
583                 else
584                         p = &parent->rb_right;
585         }
586         /* nothing in children, add to the current node */
587         rnode = add_child(root, cursor, period);
588         rb_link_node(&rnode->rb_node_in, parent, p);
589         rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
590 
591 inc_children_hit:
592         root->children_hit += period;
593         root->children_count++;
594 }
595 
596 static int
597 append_chain(struct callchain_node *root,
598              struct callchain_cursor *cursor,
599              u64 period)
600 {
601         struct callchain_list *cnode;
602         u64 start = cursor->pos;
603         bool found = false;
604         u64 matches;
605         int cmp = 0;
606 
607         /*
608          * Lookup in the current node
609          * If we have a symbol, then compare the start to match
610          * anywhere inside a function, unless function
611          * mode is disabled.
612          */
613         list_for_each_entry(cnode, &root->val, list) {
614                 struct callchain_cursor_node *node;
615 
616                 node = callchain_cursor_current(cursor);
617                 if (!node)
618                         break;
619 
620                 cmp = match_chain(node, cnode);
621                 if (cmp)
622                         break;
623 
624                 found = true;
625 
626                 callchain_cursor_advance(cursor);
627         }
628 
629         /* matches not, relay no the parent */
630         if (!found) {
631                 WARN_ONCE(!cmp, "Chain comparison error\n");
632                 return cmp;
633         }
634 
635         matches = cursor->pos - start;
636 
637         /* we match only a part of the node. Split it and add the new chain */
638         if (matches < root->val_nr) {
639                 split_add_child(root, cursor, cnode, start, matches, period);
640                 return 0;
641         }
642 
643         /* we match 100% of the path, increment the hit */
644         if (matches == root->val_nr && cursor->pos == cursor->nr) {
645                 root->hit += period;
646                 root->count++;
647                 return 0;
648         }
649 
650         /* We match the node and still have a part remaining */
651         append_chain_children(root, cursor, period);
652 
653         return 0;
654 }
655 
656 int callchain_append(struct callchain_root *root,
657                      struct callchain_cursor *cursor,
658                      u64 period)
659 {
660         if (!cursor->nr)
661                 return 0;
662 
663         callchain_cursor_commit(cursor);
664 
665         append_chain_children(&root->node, cursor, period);
666 
667         if (cursor->nr > root->max_depth)
668                 root->max_depth = cursor->nr;
669 
670         return 0;
671 }
672 
673 static int
674 merge_chain_branch(struct callchain_cursor *cursor,
675                    struct callchain_node *dst, struct callchain_node *src)
676 {
677         struct callchain_cursor_node **old_last = cursor->last;
678         struct callchain_node *child;
679         struct callchain_list *list, *next_list;
680         struct rb_node *n;
681         int old_pos = cursor->nr;
682         int err = 0;
683 
684         list_for_each_entry_safe(list, next_list, &src->val, list) {
685                 callchain_cursor_append(cursor, list->ip,
686                                         list->ms.map, list->ms.sym);
687                 list_del(&list->list);
688                 free(list);
689         }
690 
691         if (src->hit) {
692                 callchain_cursor_commit(cursor);
693                 append_chain_children(dst, cursor, src->hit);
694         }
695 
696         n = rb_first(&src->rb_root_in);
697         while (n) {
698                 child = container_of(n, struct callchain_node, rb_node_in);
699                 n = rb_next(n);
700                 rb_erase(&child->rb_node_in, &src->rb_root_in);
701 
702                 err = merge_chain_branch(cursor, dst, child);
703                 if (err)
704                         break;
705 
706                 free(child);
707         }
708 
709         cursor->nr = old_pos;
710         cursor->last = old_last;
711 
712         return err;
713 }
714 
715 int callchain_merge(struct callchain_cursor *cursor,
716                     struct callchain_root *dst, struct callchain_root *src)
717 {
718         return merge_chain_branch(cursor, &dst->node, &src->node);
719 }
720 
721 int callchain_cursor_append(struct callchain_cursor *cursor,
722                             u64 ip, struct map *map, struct symbol *sym)
723 {
724         struct callchain_cursor_node *node = *cursor->last;
725 
726         if (!node) {
727                 node = calloc(1, sizeof(*node));
728                 if (!node)
729                         return -ENOMEM;
730 
731                 *cursor->last = node;
732         }
733 
734         node->ip = ip;
735         node->map = map;
736         node->sym = sym;
737 
738         cursor->nr++;
739 
740         cursor->last = &node->next;
741 
742         return 0;
743 }
744 
745 int sample__resolve_callchain(struct perf_sample *sample, struct symbol **parent,
746                               struct perf_evsel *evsel, struct addr_location *al,
747                               int max_stack)
748 {
749         if (sample->callchain == NULL)
750                 return 0;
751 
752         if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
753             sort__has_parent) {
754                 return thread__resolve_callchain(al->thread, evsel, sample,
755                                                  parent, al, max_stack);
756         }
757         return 0;
758 }
759 
760 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
761 {
762         if (!symbol_conf.use_callchain || sample->callchain == NULL)
763                 return 0;
764         return callchain_append(he->callchain, &callchain_cursor, sample->period);
765 }
766 
767 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
768                         bool hide_unresolved)
769 {
770         al->map = node->map;
771         al->sym = node->sym;
772         if (node->map)
773                 al->addr = node->map->map_ip(node->map, node->ip);
774         else
775                 al->addr = node->ip;
776 
777         if (al->sym == NULL) {
778                 if (hide_unresolved)
779                         return 0;
780                 if (al->map == NULL)
781                         goto out;
782         }
783 
784         if (al->map->groups == &al->machine->kmaps) {
785                 if (machine__is_host(al->machine)) {
786                         al->cpumode = PERF_RECORD_MISC_KERNEL;
787                         al->level = 'k';
788                 } else {
789                         al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
790                         al->level = 'g';
791                 }
792         } else {
793                 if (machine__is_host(al->machine)) {
794                         al->cpumode = PERF_RECORD_MISC_USER;
795                         al->level = '.';
796                 } else if (perf_guest) {
797                         al->cpumode = PERF_RECORD_MISC_GUEST_USER;
798                         al->level = 'u';
799                 } else {
800                         al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
801                         al->level = 'H';
802                 }
803         }
804 
805 out:
806         return 1;
807 }
808 
809 char *callchain_list__sym_name(struct callchain_list *cl,
810                                char *bf, size_t bfsize, bool show_dso)
811 {
812         int printed;
813 
814         if (cl->ms.sym) {
815                 if (callchain_param.key == CCKEY_ADDRESS &&
816                     cl->ms.map && !cl->srcline)
817                         cl->srcline = get_srcline(cl->ms.map->dso,
818                                                   map__rip_2objdump(cl->ms.map,
819                                                                     cl->ip),
820                                                   cl->ms.sym, false);
821                 if (cl->srcline)
822                         printed = scnprintf(bf, bfsize, "%s %s",
823                                         cl->ms.sym->name, cl->srcline);
824                 else
825                         printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
826         } else
827                 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
828 
829         if (show_dso)
830                 scnprintf(bf + printed, bfsize - printed, " %s",
831                           cl->ms.map ?
832                           cl->ms.map->dso->short_name :
833                           "unknown");
834 
835         return bf;
836 }
837 
838 char *callchain_node__scnprintf_value(struct callchain_node *node,
839                                       char *bf, size_t bfsize, u64 total)
840 {
841         double percent = 0.0;
842         u64 period = callchain_cumul_hits(node);
843         unsigned count = callchain_cumul_counts(node);
844 
845         if (callchain_param.mode == CHAIN_FOLDED) {
846                 period = node->hit;
847                 count = node->count;
848         }
849 
850         switch (callchain_param.value) {
851         case CCVAL_PERIOD:
852                 scnprintf(bf, bfsize, "%"PRIu64, period);
853                 break;
854         case CCVAL_COUNT:
855                 scnprintf(bf, bfsize, "%u", count);
856                 break;
857         case CCVAL_PERCENT:
858         default:
859                 if (total)
860                         percent = period * 100.0 / total;
861                 scnprintf(bf, bfsize, "%.2f%%", percent);
862                 break;
863         }
864         return bf;
865 }
866 
867 int callchain_node__fprintf_value(struct callchain_node *node,
868                                  FILE *fp, u64 total)
869 {
870         double percent = 0.0;
871         u64 period = callchain_cumul_hits(node);
872         unsigned count = callchain_cumul_counts(node);
873 
874         if (callchain_param.mode == CHAIN_FOLDED) {
875                 period = node->hit;
876                 count = node->count;
877         }
878 
879         switch (callchain_param.value) {
880         case CCVAL_PERIOD:
881                 return fprintf(fp, "%"PRIu64, period);
882         case CCVAL_COUNT:
883                 return fprintf(fp, "%u", count);
884         case CCVAL_PERCENT:
885         default:
886                 if (total)
887                         percent = period * 100.0 / total;
888                 return percent_color_fprintf(fp, "%.2f%%", percent);
889         }
890         return 0;
891 }
892 
893 static void free_callchain_node(struct callchain_node *node)
894 {
895         struct callchain_list *list, *tmp;
896         struct callchain_node *child;
897         struct rb_node *n;
898 
899         list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
900                 list_del(&list->list);
901                 free(list);
902         }
903 
904         list_for_each_entry_safe(list, tmp, &node->val, list) {
905                 list_del(&list->list);
906                 free(list);
907         }
908 
909         n = rb_first(&node->rb_root_in);
910         while (n) {
911                 child = container_of(n, struct callchain_node, rb_node_in);
912                 n = rb_next(n);
913                 rb_erase(&child->rb_node_in, &node->rb_root_in);
914 
915                 free_callchain_node(child);
916                 free(child);
917         }
918 }
919 
920 void free_callchain(struct callchain_root *root)
921 {
922         if (!symbol_conf.use_callchain)
923                 return;
924 
925         free_callchain_node(&root->node);
926 }
927 
928 static u64 decay_callchain_node(struct callchain_node *node)
929 {
930         struct callchain_node *child;
931         struct rb_node *n;
932         u64 child_hits = 0;
933 
934         n = rb_first(&node->rb_root_in);
935         while (n) {
936                 child = container_of(n, struct callchain_node, rb_node_in);
937 
938                 child_hits += decay_callchain_node(child);
939                 n = rb_next(n);
940         }
941 
942         node->hit = (node->hit * 7) / 8;
943         node->children_hit = child_hits;
944 
945         return node->hit;
946 }
947 
948 void decay_callchain(struct callchain_root *root)
949 {
950         if (!symbol_conf.use_callchain)
951                 return;
952 
953         decay_callchain_node(&root->node);
954 }
955 
956 int callchain_node__make_parent_list(struct callchain_node *node)
957 {
958         struct callchain_node *parent = node->parent;
959         struct callchain_list *chain, *new;
960         LIST_HEAD(head);
961 
962         while (parent) {
963                 list_for_each_entry_reverse(chain, &parent->val, list) {
964                         new = malloc(sizeof(*new));
965                         if (new == NULL)
966                                 goto out;
967                         *new = *chain;
968                         new->has_children = false;
969                         list_add_tail(&new->list, &head);
970                 }
971                 parent = parent->parent;
972         }
973 
974         list_for_each_entry_safe_reverse(chain, new, &head, list)
975                 list_move_tail(&chain->list, &node->parent_val);
976 
977         if (!list_empty(&node->parent_val)) {
978                 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
979                 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
980 
981                 chain = list_first_entry(&node->val, struct callchain_list, list);
982                 chain->has_children = false;
983         }
984         return 0;
985 
986 out:
987         list_for_each_entry_safe(chain, new, &head, list) {
988                 list_del(&chain->list);
989                 free(chain);
990         }
991         return -ENOMEM;
992 }
993 

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