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

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

Version: ~ [ linux-5.15-rc6 ] ~ [ linux-5.14.14 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.75 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.155 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.213 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.252 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.287 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.289 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ 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 
 52         pr_err("Invalid callchain mode: %s\n", value);
 53         return -1;
 54 }
 55 
 56 static int parse_callchain_order(const char *value)
 57 {
 58         if (!strncmp(value, "caller", strlen(value))) {
 59                 callchain_param.order = ORDER_CALLER;
 60                 callchain_param.order_set = true;
 61                 return 0;
 62         }
 63         if (!strncmp(value, "callee", strlen(value))) {
 64                 callchain_param.order = ORDER_CALLEE;
 65                 callchain_param.order_set = true;
 66                 return 0;
 67         }
 68 
 69         pr_err("Invalid callchain order: %s\n", value);
 70         return -1;
 71 }
 72 
 73 static int parse_callchain_sort_key(const char *value)
 74 {
 75         if (!strncmp(value, "function", strlen(value))) {
 76                 callchain_param.key = CCKEY_FUNCTION;
 77                 return 0;
 78         }
 79         if (!strncmp(value, "address", strlen(value))) {
 80                 callchain_param.key = CCKEY_ADDRESS;
 81                 return 0;
 82         }
 83         if (!strncmp(value, "branch", strlen(value))) {
 84                 callchain_param.branch_callstack = 1;
 85                 return 0;
 86         }
 87 
 88         pr_err("Invalid callchain sort key: %s\n", value);
 89         return -1;
 90 }
 91 
 92 static int parse_callchain_value(const char *value)
 93 {
 94         if (!strncmp(value, "percent", strlen(value))) {
 95                 callchain_param.value = CCVAL_PERCENT;
 96                 return 0;
 97         }
 98         if (!strncmp(value, "period", strlen(value))) {
 99                 callchain_param.value = CCVAL_PERIOD;
100                 return 0;
101         }
102         if (!strncmp(value, "count", strlen(value))) {
103                 callchain_param.value = CCVAL_COUNT;
104                 return 0;
105         }
106 
107         pr_err("Invalid callchain config key: %s\n", value);
108         return -1;
109 }
110 
111 static int
112 __parse_callchain_report_opt(const char *arg, bool allow_record_opt)
113 {
114         char *tok;
115         char *endptr;
116         bool minpcnt_set = false;
117         bool record_opt_set = false;
118         bool try_stack_size = false;
119 
120         callchain_param.enabled = true;
121         symbol_conf.use_callchain = true;
122 
123         if (!arg)
124                 return 0;
125 
126         while ((tok = strtok((char *)arg, ",")) != NULL) {
127                 if (!strncmp(tok, "none", strlen(tok))) {
128                         callchain_param.mode = CHAIN_NONE;
129                         callchain_param.enabled = false;
130                         symbol_conf.use_callchain = false;
131                         return 0;
132                 }
133 
134                 if (!parse_callchain_mode(tok) ||
135                     !parse_callchain_order(tok) ||
136                     !parse_callchain_sort_key(tok) ||
137                     !parse_callchain_value(tok)) {
138                         /* parsing ok - move on to the next */
139                         try_stack_size = false;
140                         goto next;
141                 } else if (allow_record_opt && !record_opt_set) {
142                         if (parse_callchain_record(tok, &callchain_param))
143                                 goto try_numbers;
144 
145                         /* assume that number followed by 'dwarf' is stack size */
146                         if (callchain_param.record_mode == CALLCHAIN_DWARF)
147                                 try_stack_size = true;
148 
149                         record_opt_set = true;
150                         goto next;
151                 }
152 
153 try_numbers:
154                 if (try_stack_size) {
155                         unsigned long size = 0;
156 
157                         if (get_stack_size(tok, &size) < 0)
158                                 return -1;
159                         callchain_param.dump_size = size;
160                         try_stack_size = false;
161                 } else if (!minpcnt_set) {
162                         /* try to get the min percent */
163                         callchain_param.min_percent = strtod(tok, &endptr);
164                         if (tok == endptr)
165                                 return -1;
166                         minpcnt_set = true;
167                 } else {
168                         /* try print limit at last */
169                         callchain_param.print_limit = strtoul(tok, &endptr, 0);
170                         if (tok == endptr)
171                                 return -1;
172                 }
173 next:
174                 arg = NULL;
175         }
176 
177         if (callchain_register_param(&callchain_param) < 0) {
178                 pr_err("Can't register callchain params\n");
179                 return -1;
180         }
181         return 0;
182 }
183 
184 int parse_callchain_report_opt(const char *arg)
185 {
186         return __parse_callchain_report_opt(arg, false);
187 }
188 
189 int parse_callchain_top_opt(const char *arg)
190 {
191         return __parse_callchain_report_opt(arg, true);
192 }
193 
194 int perf_callchain_config(const char *var, const char *value)
195 {
196         char *endptr;
197 
198         if (prefixcmp(var, "call-graph."))
199                 return 0;
200         var += sizeof("call-graph.") - 1;
201 
202         if (!strcmp(var, "record-mode"))
203                 return parse_callchain_record_opt(value, &callchain_param);
204         if (!strcmp(var, "dump-size")) {
205                 unsigned long size = 0;
206                 int ret;
207 
208                 ret = get_stack_size(value, &size);
209                 callchain_param.dump_size = size;
210 
211                 return ret;
212         }
213         if (!strcmp(var, "print-type"))
214                 return parse_callchain_mode(value);
215         if (!strcmp(var, "order"))
216                 return parse_callchain_order(value);
217         if (!strcmp(var, "sort-key"))
218                 return parse_callchain_sort_key(value);
219         if (!strcmp(var, "threshold")) {
220                 callchain_param.min_percent = strtod(value, &endptr);
221                 if (value == endptr) {
222                         pr_err("Invalid callchain threshold: %s\n", value);
223                         return -1;
224                 }
225         }
226         if (!strcmp(var, "print-limit")) {
227                 callchain_param.print_limit = strtod(value, &endptr);
228                 if (value == endptr) {
229                         pr_err("Invalid callchain print limit: %s\n", value);
230                         return -1;
231                 }
232         }
233 
234         return 0;
235 }
236 
237 static void
238 rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
239                     enum chain_mode mode)
240 {
241         struct rb_node **p = &root->rb_node;
242         struct rb_node *parent = NULL;
243         struct callchain_node *rnode;
244         u64 chain_cumul = callchain_cumul_hits(chain);
245 
246         while (*p) {
247                 u64 rnode_cumul;
248 
249                 parent = *p;
250                 rnode = rb_entry(parent, struct callchain_node, rb_node);
251                 rnode_cumul = callchain_cumul_hits(rnode);
252 
253                 switch (mode) {
254                 case CHAIN_FLAT:
255                 case CHAIN_FOLDED:
256                         if (rnode->hit < chain->hit)
257                                 p = &(*p)->rb_left;
258                         else
259                                 p = &(*p)->rb_right;
260                         break;
261                 case CHAIN_GRAPH_ABS: /* Falldown */
262                 case CHAIN_GRAPH_REL:
263                         if (rnode_cumul < chain_cumul)
264                                 p = &(*p)->rb_left;
265                         else
266                                 p = &(*p)->rb_right;
267                         break;
268                 case CHAIN_NONE:
269                 default:
270                         break;
271                 }
272         }
273 
274         rb_link_node(&chain->rb_node, parent, p);
275         rb_insert_color(&chain->rb_node, root);
276 }
277 
278 static void
279 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node,
280                   u64 min_hit)
281 {
282         struct rb_node *n;
283         struct callchain_node *child;
284 
285         n = rb_first(&node->rb_root_in);
286         while (n) {
287                 child = rb_entry(n, struct callchain_node, rb_node_in);
288                 n = rb_next(n);
289 
290                 __sort_chain_flat(rb_root, child, min_hit);
291         }
292 
293         if (node->hit && node->hit >= min_hit)
294                 rb_insert_callchain(rb_root, node, CHAIN_FLAT);
295 }
296 
297 /*
298  * Once we get every callchains from the stream, we can now
299  * sort them by hit
300  */
301 static void
302 sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
303                 u64 min_hit, struct callchain_param *param __maybe_unused)
304 {
305         *rb_root = RB_ROOT;
306         __sort_chain_flat(rb_root, &root->node, min_hit);
307 }
308 
309 static void __sort_chain_graph_abs(struct callchain_node *node,
310                                    u64 min_hit)
311 {
312         struct rb_node *n;
313         struct callchain_node *child;
314 
315         node->rb_root = RB_ROOT;
316         n = rb_first(&node->rb_root_in);
317 
318         while (n) {
319                 child = rb_entry(n, struct callchain_node, rb_node_in);
320                 n = rb_next(n);
321 
322                 __sort_chain_graph_abs(child, min_hit);
323                 if (callchain_cumul_hits(child) >= min_hit)
324                         rb_insert_callchain(&node->rb_root, child,
325                                             CHAIN_GRAPH_ABS);
326         }
327 }
328 
329 static void
330 sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
331                      u64 min_hit, struct callchain_param *param __maybe_unused)
332 {
333         __sort_chain_graph_abs(&chain_root->node, min_hit);
334         rb_root->rb_node = chain_root->node.rb_root.rb_node;
335 }
336 
337 static void __sort_chain_graph_rel(struct callchain_node *node,
338                                    double min_percent)
339 {
340         struct rb_node *n;
341         struct callchain_node *child;
342         u64 min_hit;
343 
344         node->rb_root = RB_ROOT;
345         min_hit = ceil(node->children_hit * min_percent);
346 
347         n = rb_first(&node->rb_root_in);
348         while (n) {
349                 child = rb_entry(n, struct callchain_node, rb_node_in);
350                 n = rb_next(n);
351 
352                 __sort_chain_graph_rel(child, min_percent);
353                 if (callchain_cumul_hits(child) >= min_hit)
354                         rb_insert_callchain(&node->rb_root, child,
355                                             CHAIN_GRAPH_REL);
356         }
357 }
358 
359 static void
360 sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
361                      u64 min_hit __maybe_unused, struct callchain_param *param)
362 {
363         __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
364         rb_root->rb_node = chain_root->node.rb_root.rb_node;
365 }
366 
367 int callchain_register_param(struct callchain_param *param)
368 {
369         switch (param->mode) {
370         case CHAIN_GRAPH_ABS:
371                 param->sort = sort_chain_graph_abs;
372                 break;
373         case CHAIN_GRAPH_REL:
374                 param->sort = sort_chain_graph_rel;
375                 break;
376         case CHAIN_FLAT:
377         case CHAIN_FOLDED:
378                 param->sort = sort_chain_flat;
379                 break;
380         case CHAIN_NONE:
381         default:
382                 return -1;
383         }
384         return 0;
385 }
386 
387 /*
388  * Create a child for a parent. If inherit_children, then the new child
389  * will become the new parent of it's parent children
390  */
391 static struct callchain_node *
392 create_child(struct callchain_node *parent, bool inherit_children)
393 {
394         struct callchain_node *new;
395 
396         new = zalloc(sizeof(*new));
397         if (!new) {
398                 perror("not enough memory to create child for code path tree");
399                 return NULL;
400         }
401         new->parent = parent;
402         INIT_LIST_HEAD(&new->val);
403         INIT_LIST_HEAD(&new->parent_val);
404 
405         if (inherit_children) {
406                 struct rb_node *n;
407                 struct callchain_node *child;
408 
409                 new->rb_root_in = parent->rb_root_in;
410                 parent->rb_root_in = RB_ROOT;
411 
412                 n = rb_first(&new->rb_root_in);
413                 while (n) {
414                         child = rb_entry(n, struct callchain_node, rb_node_in);
415                         child->parent = new;
416                         n = rb_next(n);
417                 }
418 
419                 /* make it the first child */
420                 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node);
421                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
422         }
423 
424         return new;
425 }
426 
427 
428 /*
429  * Fill the node with callchain values
430  */
431 static int
432 fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
433 {
434         struct callchain_cursor_node *cursor_node;
435 
436         node->val_nr = cursor->nr - cursor->pos;
437         if (!node->val_nr)
438                 pr_warning("Warning: empty node in callchain tree\n");
439 
440         cursor_node = callchain_cursor_current(cursor);
441 
442         while (cursor_node) {
443                 struct callchain_list *call;
444 
445                 call = zalloc(sizeof(*call));
446                 if (!call) {
447                         perror("not enough memory for the code path tree");
448                         return -1;
449                 }
450                 call->ip = cursor_node->ip;
451                 call->ms.sym = cursor_node->sym;
452                 call->ms.map = map__get(cursor_node->map);
453 
454                 if (cursor_node->branch) {
455                         call->branch_count = 1;
456 
457                         if (cursor_node->branch_flags.predicted)
458                                 call->predicted_count = 1;
459 
460                         if (cursor_node->branch_flags.abort)
461                                 call->abort_count = 1;
462 
463                         call->cycles_count = cursor_node->branch_flags.cycles;
464                         call->iter_count = cursor_node->nr_loop_iter;
465                         call->samples_count = cursor_node->samples;
466                 }
467 
468                 list_add_tail(&call->list, &node->val);
469 
470                 callchain_cursor_advance(cursor);
471                 cursor_node = callchain_cursor_current(cursor);
472         }
473         return 0;
474 }
475 
476 static struct callchain_node *
477 add_child(struct callchain_node *parent,
478           struct callchain_cursor *cursor,
479           u64 period)
480 {
481         struct callchain_node *new;
482 
483         new = create_child(parent, false);
484         if (new == NULL)
485                 return NULL;
486 
487         if (fill_node(new, cursor) < 0) {
488                 struct callchain_list *call, *tmp;
489 
490                 list_for_each_entry_safe(call, tmp, &new->val, list) {
491                         list_del(&call->list);
492                         map__zput(call->ms.map);
493                         free(call);
494                 }
495                 free(new);
496                 return NULL;
497         }
498 
499         new->children_hit = 0;
500         new->hit = period;
501         new->children_count = 0;
502         new->count = 1;
503         return new;
504 }
505 
506 enum match_result {
507         MATCH_ERROR  = -1,
508         MATCH_EQ,
509         MATCH_LT,
510         MATCH_GT,
511 };
512 
513 static enum match_result match_chain(struct callchain_cursor_node *node,
514                                      struct callchain_list *cnode)
515 {
516         struct symbol *sym = node->sym;
517         u64 left, right;
518 
519         if (cnode->ms.sym && sym &&
520             callchain_param.key == CCKEY_FUNCTION) {
521                 left = cnode->ms.sym->start;
522                 right = sym->start;
523         } else {
524                 left = cnode->ip;
525                 right = node->ip;
526         }
527 
528         if (left == right) {
529                 if (node->branch) {
530                         cnode->branch_count++;
531 
532                         if (node->branch_flags.predicted)
533                                 cnode->predicted_count++;
534 
535                         if (node->branch_flags.abort)
536                                 cnode->abort_count++;
537 
538                         cnode->cycles_count += node->branch_flags.cycles;
539                         cnode->iter_count += node->nr_loop_iter;
540                         cnode->samples_count += node->samples;
541                 }
542 
543                 return MATCH_EQ;
544         }
545 
546         return left > right ? MATCH_GT : MATCH_LT;
547 }
548 
549 /*
550  * Split the parent in two parts (a new child is created) and
551  * give a part of its callchain to the created child.
552  * Then create another child to host the given callchain of new branch
553  */
554 static int
555 split_add_child(struct callchain_node *parent,
556                 struct callchain_cursor *cursor,
557                 struct callchain_list *to_split,
558                 u64 idx_parents, u64 idx_local, u64 period)
559 {
560         struct callchain_node *new;
561         struct list_head *old_tail;
562         unsigned int idx_total = idx_parents + idx_local;
563 
564         /* split */
565         new = create_child(parent, true);
566         if (new == NULL)
567                 return -1;
568 
569         /* split the callchain and move a part to the new child */
570         old_tail = parent->val.prev;
571         list_del_range(&to_split->list, old_tail);
572         new->val.next = &to_split->list;
573         new->val.prev = old_tail;
574         to_split->list.prev = &new->val;
575         old_tail->next = &new->val;
576 
577         /* split the hits */
578         new->hit = parent->hit;
579         new->children_hit = parent->children_hit;
580         parent->children_hit = callchain_cumul_hits(new);
581         new->val_nr = parent->val_nr - idx_local;
582         parent->val_nr = idx_local;
583         new->count = parent->count;
584         new->children_count = parent->children_count;
585         parent->children_count = callchain_cumul_counts(new);
586 
587         /* create a new child for the new branch if any */
588         if (idx_total < cursor->nr) {
589                 struct callchain_node *first;
590                 struct callchain_list *cnode;
591                 struct callchain_cursor_node *node;
592                 struct rb_node *p, **pp;
593 
594                 parent->hit = 0;
595                 parent->children_hit += period;
596                 parent->count = 0;
597                 parent->children_count += 1;
598 
599                 node = callchain_cursor_current(cursor);
600                 new = add_child(parent, cursor, period);
601                 if (new == NULL)
602                         return -1;
603 
604                 /*
605                  * This is second child since we moved parent's children
606                  * to new (first) child above.
607                  */
608                 p = parent->rb_root_in.rb_node;
609                 first = rb_entry(p, struct callchain_node, rb_node_in);
610                 cnode = list_first_entry(&first->val, struct callchain_list,
611                                          list);
612 
613                 if (match_chain(node, cnode) == MATCH_LT)
614                         pp = &p->rb_left;
615                 else
616                         pp = &p->rb_right;
617 
618                 rb_link_node(&new->rb_node_in, p, pp);
619                 rb_insert_color(&new->rb_node_in, &parent->rb_root_in);
620         } else {
621                 parent->hit = period;
622                 parent->count = 1;
623         }
624         return 0;
625 }
626 
627 static enum match_result
628 append_chain(struct callchain_node *root,
629              struct callchain_cursor *cursor,
630              u64 period);
631 
632 static int
633 append_chain_children(struct callchain_node *root,
634                       struct callchain_cursor *cursor,
635                       u64 period)
636 {
637         struct callchain_node *rnode;
638         struct callchain_cursor_node *node;
639         struct rb_node **p = &root->rb_root_in.rb_node;
640         struct rb_node *parent = NULL;
641 
642         node = callchain_cursor_current(cursor);
643         if (!node)
644                 return -1;
645 
646         /* lookup in childrens */
647         while (*p) {
648                 enum match_result ret;
649 
650                 parent = *p;
651                 rnode = rb_entry(parent, struct callchain_node, rb_node_in);
652 
653                 /* If at least first entry matches, rely to children */
654                 ret = append_chain(rnode, cursor, period);
655                 if (ret == MATCH_EQ)
656                         goto inc_children_hit;
657                 if (ret == MATCH_ERROR)
658                         return -1;
659 
660                 if (ret == MATCH_LT)
661                         p = &parent->rb_left;
662                 else
663                         p = &parent->rb_right;
664         }
665         /* nothing in children, add to the current node */
666         rnode = add_child(root, cursor, period);
667         if (rnode == NULL)
668                 return -1;
669 
670         rb_link_node(&rnode->rb_node_in, parent, p);
671         rb_insert_color(&rnode->rb_node_in, &root->rb_root_in);
672 
673 inc_children_hit:
674         root->children_hit += period;
675         root->children_count++;
676         return 0;
677 }
678 
679 static enum match_result
680 append_chain(struct callchain_node *root,
681              struct callchain_cursor *cursor,
682              u64 period)
683 {
684         struct callchain_list *cnode;
685         u64 start = cursor->pos;
686         bool found = false;
687         u64 matches;
688         enum match_result cmp = MATCH_ERROR;
689 
690         /*
691          * Lookup in the current node
692          * If we have a symbol, then compare the start to match
693          * anywhere inside a function, unless function
694          * mode is disabled.
695          */
696         list_for_each_entry(cnode, &root->val, list) {
697                 struct callchain_cursor_node *node;
698 
699                 node = callchain_cursor_current(cursor);
700                 if (!node)
701                         break;
702 
703                 cmp = match_chain(node, cnode);
704                 if (cmp != MATCH_EQ)
705                         break;
706 
707                 found = true;
708 
709                 callchain_cursor_advance(cursor);
710         }
711 
712         /* matches not, relay no the parent */
713         if (!found) {
714                 WARN_ONCE(cmp == MATCH_ERROR, "Chain comparison error\n");
715                 return cmp;
716         }
717 
718         matches = cursor->pos - start;
719 
720         /* we match only a part of the node. Split it and add the new chain */
721         if (matches < root->val_nr) {
722                 if (split_add_child(root, cursor, cnode, start, matches,
723                                     period) < 0)
724                         return MATCH_ERROR;
725 
726                 return MATCH_EQ;
727         }
728 
729         /* we match 100% of the path, increment the hit */
730         if (matches == root->val_nr && cursor->pos == cursor->nr) {
731                 root->hit += period;
732                 root->count++;
733                 return MATCH_EQ;
734         }
735 
736         /* We match the node and still have a part remaining */
737         if (append_chain_children(root, cursor, period) < 0)
738                 return MATCH_ERROR;
739 
740         return MATCH_EQ;
741 }
742 
743 int callchain_append(struct callchain_root *root,
744                      struct callchain_cursor *cursor,
745                      u64 period)
746 {
747         if (!cursor->nr)
748                 return 0;
749 
750         callchain_cursor_commit(cursor);
751 
752         if (append_chain_children(&root->node, cursor, period) < 0)
753                 return -1;
754 
755         if (cursor->nr > root->max_depth)
756                 root->max_depth = cursor->nr;
757 
758         return 0;
759 }
760 
761 static int
762 merge_chain_branch(struct callchain_cursor *cursor,
763                    struct callchain_node *dst, struct callchain_node *src)
764 {
765         struct callchain_cursor_node **old_last = cursor->last;
766         struct callchain_node *child;
767         struct callchain_list *list, *next_list;
768         struct rb_node *n;
769         int old_pos = cursor->nr;
770         int err = 0;
771 
772         list_for_each_entry_safe(list, next_list, &src->val, list) {
773                 callchain_cursor_append(cursor, list->ip,
774                                         list->ms.map, list->ms.sym,
775                                         false, NULL, 0, 0);
776                 list_del(&list->list);
777                 map__zput(list->ms.map);
778                 free(list);
779         }
780 
781         if (src->hit) {
782                 callchain_cursor_commit(cursor);
783                 if (append_chain_children(dst, cursor, src->hit) < 0)
784                         return -1;
785         }
786 
787         n = rb_first(&src->rb_root_in);
788         while (n) {
789                 child = container_of(n, struct callchain_node, rb_node_in);
790                 n = rb_next(n);
791                 rb_erase(&child->rb_node_in, &src->rb_root_in);
792 
793                 err = merge_chain_branch(cursor, dst, child);
794                 if (err)
795                         break;
796 
797                 free(child);
798         }
799 
800         cursor->nr = old_pos;
801         cursor->last = old_last;
802 
803         return err;
804 }
805 
806 int callchain_merge(struct callchain_cursor *cursor,
807                     struct callchain_root *dst, struct callchain_root *src)
808 {
809         return merge_chain_branch(cursor, &dst->node, &src->node);
810 }
811 
812 int callchain_cursor_append(struct callchain_cursor *cursor,
813                             u64 ip, struct map *map, struct symbol *sym,
814                             bool branch, struct branch_flags *flags,
815                             int nr_loop_iter, int samples)
816 {
817         struct callchain_cursor_node *node = *cursor->last;
818 
819         if (!node) {
820                 node = calloc(1, sizeof(*node));
821                 if (!node)
822                         return -ENOMEM;
823 
824                 *cursor->last = node;
825         }
826 
827         node->ip = ip;
828         map__zput(node->map);
829         node->map = map__get(map);
830         node->sym = sym;
831         node->branch = branch;
832         node->nr_loop_iter = nr_loop_iter;
833         node->samples = samples;
834 
835         if (flags)
836                 memcpy(&node->branch_flags, flags,
837                         sizeof(struct branch_flags));
838 
839         cursor->nr++;
840 
841         cursor->last = &node->next;
842 
843         return 0;
844 }
845 
846 int sample__resolve_callchain(struct perf_sample *sample,
847                               struct callchain_cursor *cursor, struct symbol **parent,
848                               struct perf_evsel *evsel, struct addr_location *al,
849                               int max_stack)
850 {
851         if (sample->callchain == NULL)
852                 return 0;
853 
854         if (symbol_conf.use_callchain || symbol_conf.cumulate_callchain ||
855             perf_hpp_list.parent) {
856                 return thread__resolve_callchain(al->thread, cursor, evsel, sample,
857                                                  parent, al, max_stack);
858         }
859         return 0;
860 }
861 
862 int hist_entry__append_callchain(struct hist_entry *he, struct perf_sample *sample)
863 {
864         if (!symbol_conf.use_callchain || sample->callchain == NULL)
865                 return 0;
866         return callchain_append(he->callchain, &callchain_cursor, sample->period);
867 }
868 
869 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node,
870                         bool hide_unresolved)
871 {
872         al->map = node->map;
873         al->sym = node->sym;
874         if (node->map)
875                 al->addr = node->map->map_ip(node->map, node->ip);
876         else
877                 al->addr = node->ip;
878 
879         if (al->sym == NULL) {
880                 if (hide_unresolved)
881                         return 0;
882                 if (al->map == NULL)
883                         goto out;
884         }
885 
886         if (al->map->groups == &al->machine->kmaps) {
887                 if (machine__is_host(al->machine)) {
888                         al->cpumode = PERF_RECORD_MISC_KERNEL;
889                         al->level = 'k';
890                 } else {
891                         al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL;
892                         al->level = 'g';
893                 }
894         } else {
895                 if (machine__is_host(al->machine)) {
896                         al->cpumode = PERF_RECORD_MISC_USER;
897                         al->level = '.';
898                 } else if (perf_guest) {
899                         al->cpumode = PERF_RECORD_MISC_GUEST_USER;
900                         al->level = 'u';
901                 } else {
902                         al->cpumode = PERF_RECORD_MISC_HYPERVISOR;
903                         al->level = 'H';
904                 }
905         }
906 
907 out:
908         return 1;
909 }
910 
911 char *callchain_list__sym_name(struct callchain_list *cl,
912                                char *bf, size_t bfsize, bool show_dso)
913 {
914         int printed;
915 
916         if (cl->ms.sym) {
917                 if (callchain_param.key == CCKEY_ADDRESS &&
918                     cl->ms.map && !cl->srcline)
919                         cl->srcline = get_srcline(cl->ms.map->dso,
920                                                   map__rip_2objdump(cl->ms.map,
921                                                                     cl->ip),
922                                                   cl->ms.sym, false);
923                 if (cl->srcline)
924                         printed = scnprintf(bf, bfsize, "%s %s",
925                                         cl->ms.sym->name, cl->srcline);
926                 else
927                         printed = scnprintf(bf, bfsize, "%s", cl->ms.sym->name);
928         } else
929                 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip);
930 
931         if (show_dso)
932                 scnprintf(bf + printed, bfsize - printed, " %s",
933                           cl->ms.map ?
934                           cl->ms.map->dso->short_name :
935                           "unknown");
936 
937         return bf;
938 }
939 
940 char *callchain_node__scnprintf_value(struct callchain_node *node,
941                                       char *bf, size_t bfsize, u64 total)
942 {
943         double percent = 0.0;
944         u64 period = callchain_cumul_hits(node);
945         unsigned count = callchain_cumul_counts(node);
946 
947         if (callchain_param.mode == CHAIN_FOLDED) {
948                 period = node->hit;
949                 count = node->count;
950         }
951 
952         switch (callchain_param.value) {
953         case CCVAL_PERIOD:
954                 scnprintf(bf, bfsize, "%"PRIu64, period);
955                 break;
956         case CCVAL_COUNT:
957                 scnprintf(bf, bfsize, "%u", count);
958                 break;
959         case CCVAL_PERCENT:
960         default:
961                 if (total)
962                         percent = period * 100.0 / total;
963                 scnprintf(bf, bfsize, "%.2f%%", percent);
964                 break;
965         }
966         return bf;
967 }
968 
969 int callchain_node__fprintf_value(struct callchain_node *node,
970                                  FILE *fp, u64 total)
971 {
972         double percent = 0.0;
973         u64 period = callchain_cumul_hits(node);
974         unsigned count = callchain_cumul_counts(node);
975 
976         if (callchain_param.mode == CHAIN_FOLDED) {
977                 period = node->hit;
978                 count = node->count;
979         }
980 
981         switch (callchain_param.value) {
982         case CCVAL_PERIOD:
983                 return fprintf(fp, "%"PRIu64, period);
984         case CCVAL_COUNT:
985                 return fprintf(fp, "%u", count);
986         case CCVAL_PERCENT:
987         default:
988                 if (total)
989                         percent = period * 100.0 / total;
990                 return percent_color_fprintf(fp, "%.2f%%", percent);
991         }
992         return 0;
993 }
994 
995 static void callchain_counts_value(struct callchain_node *node,
996                                    u64 *branch_count, u64 *predicted_count,
997                                    u64 *abort_count, u64 *cycles_count)
998 {
999         struct callchain_list *clist;
1000 
1001         list_for_each_entry(clist, &node->val, list) {
1002                 if (branch_count)
1003                         *branch_count += clist->branch_count;
1004 
1005                 if (predicted_count)
1006                         *predicted_count += clist->predicted_count;
1007 
1008                 if (abort_count)
1009                         *abort_count += clist->abort_count;
1010 
1011                 if (cycles_count)
1012                         *cycles_count += clist->cycles_count;
1013         }
1014 }
1015 
1016 static int callchain_node_branch_counts_cumul(struct callchain_node *node,
1017                                               u64 *branch_count,
1018                                               u64 *predicted_count,
1019                                               u64 *abort_count,
1020                                               u64 *cycles_count)
1021 {
1022         struct callchain_node *child;
1023         struct rb_node *n;
1024 
1025         n = rb_first(&node->rb_root_in);
1026         while (n) {
1027                 child = rb_entry(n, struct callchain_node, rb_node_in);
1028                 n = rb_next(n);
1029 
1030                 callchain_node_branch_counts_cumul(child, branch_count,
1031                                                    predicted_count,
1032                                                    abort_count,
1033                                                    cycles_count);
1034 
1035                 callchain_counts_value(child, branch_count,
1036                                        predicted_count, abort_count,
1037                                        cycles_count);
1038         }
1039 
1040         return 0;
1041 }
1042 
1043 int callchain_branch_counts(struct callchain_root *root,
1044                             u64 *branch_count, u64 *predicted_count,
1045                             u64 *abort_count, u64 *cycles_count)
1046 {
1047         if (branch_count)
1048                 *branch_count = 0;
1049 
1050         if (predicted_count)
1051                 *predicted_count = 0;
1052 
1053         if (abort_count)
1054                 *abort_count = 0;
1055 
1056         if (cycles_count)
1057                 *cycles_count = 0;
1058 
1059         return callchain_node_branch_counts_cumul(&root->node,
1060                                                   branch_count,
1061                                                   predicted_count,
1062                                                   abort_count,
1063                                                   cycles_count);
1064 }
1065 
1066 static int callchain_counts_printf(FILE *fp, char *bf, int bfsize,
1067                                    u64 branch_count, u64 predicted_count,
1068                                    u64 abort_count, u64 cycles_count,
1069                                    u64 iter_count, u64 samples_count)
1070 {
1071         double predicted_percent = 0.0;
1072         const char *null_str = "";
1073         char iter_str[32];
1074         char *str;
1075         u64 cycles = 0;
1076 
1077         if (branch_count == 0) {
1078                 if (fp)
1079                         return fprintf(fp, " (calltrace)");
1080 
1081                 return scnprintf(bf, bfsize, " (calltrace)");
1082         }
1083 
1084         if (iter_count && samples_count) {
1085                 scnprintf(iter_str, sizeof(iter_str),
1086                          ", iterations:%" PRId64 "",
1087                          iter_count / samples_count);
1088                 str = iter_str;
1089         } else
1090                 str = (char *)null_str;
1091 
1092         predicted_percent = predicted_count * 100.0 / branch_count;
1093         cycles = cycles_count / branch_count;
1094 
1095         if ((predicted_percent >= 100.0) && (abort_count == 0)) {
1096                 if (fp)
1097                         return fprintf(fp, " (cycles:%" PRId64 "%s)",
1098                                        cycles, str);
1099 
1100                 return scnprintf(bf, bfsize, " (cycles:%" PRId64 "%s)",
1101                                  cycles, str);
1102         }
1103 
1104         if ((predicted_percent < 100.0) && (abort_count == 0)) {
1105                 if (fp)
1106                         return fprintf(fp,
1107                                 " (predicted:%.1f%%, cycles:%" PRId64 "%s)",
1108                                 predicted_percent, cycles, str);
1109 
1110                 return scnprintf(bf, bfsize,
1111                         " (predicted:%.1f%%, cycles:%" PRId64 "%s)",
1112                         predicted_percent, cycles, str);
1113         }
1114 
1115         if (fp)
1116                 return fprintf(fp,
1117                 " (predicted:%.1f%%, abort:%" PRId64 ", cycles:%" PRId64 "%s)",
1118                         predicted_percent, abort_count, cycles, str);
1119 
1120         return scnprintf(bf, bfsize,
1121                 " (predicted:%.1f%%, abort:%" PRId64 ", cycles:%" PRId64 "%s)",
1122                 predicted_percent, abort_count, cycles, str);
1123 }
1124 
1125 int callchain_list_counts__printf_value(struct callchain_node *node,
1126                                         struct callchain_list *clist,
1127                                         FILE *fp, char *bf, int bfsize)
1128 {
1129         u64 branch_count, predicted_count;
1130         u64 abort_count, cycles_count;
1131         u64 iter_count = 0, samples_count = 0;
1132 
1133         branch_count = clist->branch_count;
1134         predicted_count = clist->predicted_count;
1135         abort_count = clist->abort_count;
1136         cycles_count = clist->cycles_count;
1137 
1138         if (node) {
1139                 struct callchain_list *call;
1140 
1141                 list_for_each_entry(call, &node->val, list) {
1142                         iter_count += call->iter_count;
1143                         samples_count += call->samples_count;
1144                 }
1145         }
1146 
1147         return callchain_counts_printf(fp, bf, bfsize, branch_count,
1148                                        predicted_count, abort_count,
1149                                        cycles_count, iter_count, samples_count);
1150 }
1151 
1152 static void free_callchain_node(struct callchain_node *node)
1153 {
1154         struct callchain_list *list, *tmp;
1155         struct callchain_node *child;
1156         struct rb_node *n;
1157 
1158         list_for_each_entry_safe(list, tmp, &node->parent_val, list) {
1159                 list_del(&list->list);
1160                 map__zput(list->ms.map);
1161                 free(list);
1162         }
1163 
1164         list_for_each_entry_safe(list, tmp, &node->val, list) {
1165                 list_del(&list->list);
1166                 map__zput(list->ms.map);
1167                 free(list);
1168         }
1169 
1170         n = rb_first(&node->rb_root_in);
1171         while (n) {
1172                 child = container_of(n, struct callchain_node, rb_node_in);
1173                 n = rb_next(n);
1174                 rb_erase(&child->rb_node_in, &node->rb_root_in);
1175 
1176                 free_callchain_node(child);
1177                 free(child);
1178         }
1179 }
1180 
1181 void free_callchain(struct callchain_root *root)
1182 {
1183         if (!symbol_conf.use_callchain)
1184                 return;
1185 
1186         free_callchain_node(&root->node);
1187 }
1188 
1189 static u64 decay_callchain_node(struct callchain_node *node)
1190 {
1191         struct callchain_node *child;
1192         struct rb_node *n;
1193         u64 child_hits = 0;
1194 
1195         n = rb_first(&node->rb_root_in);
1196         while (n) {
1197                 child = container_of(n, struct callchain_node, rb_node_in);
1198 
1199                 child_hits += decay_callchain_node(child);
1200                 n = rb_next(n);
1201         }
1202 
1203         node->hit = (node->hit * 7) / 8;
1204         node->children_hit = child_hits;
1205 
1206         return node->hit;
1207 }
1208 
1209 void decay_callchain(struct callchain_root *root)
1210 {
1211         if (!symbol_conf.use_callchain)
1212                 return;
1213 
1214         decay_callchain_node(&root->node);
1215 }
1216 
1217 int callchain_node__make_parent_list(struct callchain_node *node)
1218 {
1219         struct callchain_node *parent = node->parent;
1220         struct callchain_list *chain, *new;
1221         LIST_HEAD(head);
1222 
1223         while (parent) {
1224                 list_for_each_entry_reverse(chain, &parent->val, list) {
1225                         new = malloc(sizeof(*new));
1226                         if (new == NULL)
1227                                 goto out;
1228                         *new = *chain;
1229                         new->has_children = false;
1230                         map__get(new->ms.map);
1231                         list_add_tail(&new->list, &head);
1232                 }
1233                 parent = parent->parent;
1234         }
1235 
1236         list_for_each_entry_safe_reverse(chain, new, &head, list)
1237                 list_move_tail(&chain->list, &node->parent_val);
1238 
1239         if (!list_empty(&node->parent_val)) {
1240                 chain = list_first_entry(&node->parent_val, struct callchain_list, list);
1241                 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node);
1242 
1243                 chain = list_first_entry(&node->val, struct callchain_list, list);
1244                 chain->has_children = false;
1245         }
1246         return 0;
1247 
1248 out:
1249         list_for_each_entry_safe(chain, new, &head, list) {
1250                 list_del(&chain->list);
1251                 map__zput(chain->ms.map);
1252                 free(chain);
1253         }
1254         return -ENOMEM;
1255 }
1256 
1257 int callchain_cursor__copy(struct callchain_cursor *dst,
1258                            struct callchain_cursor *src)
1259 {
1260         int rc = 0;
1261 
1262         callchain_cursor_reset(dst);
1263         callchain_cursor_commit(src);
1264 
1265         while (true) {
1266                 struct callchain_cursor_node *node;
1267 
1268                 node = callchain_cursor_current(src);
1269                 if (node == NULL)
1270                         break;
1271 
1272                 rc = callchain_cursor_append(dst, node->ip, node->map, node->sym,
1273                                              node->branch, &node->branch_flags,
1274                                              node->nr_loop_iter, node->samples);
1275                 if (rc)
1276                         break;
1277 
1278                 callchain_cursor_advance(src);
1279         }
1280 
1281         return rc;
1282 }
1283 

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