Lines Matching +full:child +full:- +full:node
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (C) 2009-2011, Frederic Weisbecker <[email protected]>
5 * Handle the callchains from the stream in an ad-hoc radix tree and then
53 * -e cycles/call-graph=dwarf/
61 /* Used for thread-local struct callchain_cursor. */
87 return -1; in parse_callchain_mode()
102 return -1; in parse_callchain_order()
123 return -1; in parse_callchain_sort_key()
140 return -1; in parse_callchain_value()
166 return -1; in get_stack_size()
196 /* parsing ok - move on to the next */ in __parse_callchain_report_opt()
216 return -1; in __parse_callchain_report_opt()
223 return -1; in __parse_callchain_report_opt()
229 return -1; in __parse_callchain_report_opt()
237 return -1; in __parse_callchain_report_opt()
256 int ret = -1; in parse_callchain_record()
261 return -ENOMEM; in parse_callchain_record()
272 param->record_mode = CALLCHAIN_FP; in parse_callchain_record()
280 param->max_stack = size; in parse_callchain_record()
289 param->record_mode = CALLCHAIN_DWARF; in parse_callchain_record()
290 param->dump_size = default_stack_dump_size; in parse_callchain_record()
298 param->dump_size = size; in parse_callchain_record()
302 param->record_mode = CALLCHAIN_LBR; in parse_callchain_record()
306 "needed for --call-graph lbr\n"); in parse_callchain_record()
309 pr_err("callchain: Unknown --call-graph option " in parse_callchain_record()
324 if (!strstarts(var, "call-graph.")) in perf_callchain_config()
326 var += sizeof("call-graph.") - 1; in perf_callchain_config()
328 if (!strcmp(var, "record-mode")) in perf_callchain_config()
330 if (!strcmp(var, "dump-size")) { in perf_callchain_config()
339 if (!strcmp(var, "print-type")){ in perf_callchain_config()
342 if (ret == -1) in perf_callchain_config()
349 if (ret == -1) in perf_callchain_config()
353 if (!strcmp(var, "sort-key")){ in perf_callchain_config()
356 if (ret == -1) in perf_callchain_config()
364 return -1; in perf_callchain_config()
367 if (!strcmp(var, "print-limit")) { in perf_callchain_config()
371 return -1; in perf_callchain_config()
382 struct rb_node **p = &root->rb_node; in rb_insert_callchain()
397 if (rnode->hit < chain->hit) in rb_insert_callchain()
398 p = &(*p)->rb_left; in rb_insert_callchain()
400 p = &(*p)->rb_right; in rb_insert_callchain()
405 p = &(*p)->rb_left; in rb_insert_callchain()
407 p = &(*p)->rb_right; in rb_insert_callchain()
415 rb_link_node(&chain->rb_node, parent, p); in rb_insert_callchain()
416 rb_insert_color(&chain->rb_node, root); in rb_insert_callchain()
420 __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, in __sort_chain_flat() argument
424 struct callchain_node *child; in __sort_chain_flat() local
426 n = rb_first(&node->rb_root_in); in __sort_chain_flat()
428 child = rb_entry(n, struct callchain_node, rb_node_in); in __sort_chain_flat()
431 __sort_chain_flat(rb_root, child, min_hit); in __sort_chain_flat()
434 if (node->hit && node->hit >= min_hit) in __sort_chain_flat()
435 rb_insert_callchain(rb_root, node, CHAIN_FLAT); in __sort_chain_flat()
447 __sort_chain_flat(rb_root, &root->node, min_hit); in sort_chain_flat()
450 static void __sort_chain_graph_abs(struct callchain_node *node, in __sort_chain_graph_abs() argument
454 struct callchain_node *child; in __sort_chain_graph_abs() local
456 node->rb_root = RB_ROOT; in __sort_chain_graph_abs()
457 n = rb_first(&node->rb_root_in); in __sort_chain_graph_abs()
460 child = rb_entry(n, struct callchain_node, rb_node_in); in __sort_chain_graph_abs()
463 __sort_chain_graph_abs(child, min_hit); in __sort_chain_graph_abs()
464 if (callchain_cumul_hits(child) >= min_hit) in __sort_chain_graph_abs()
465 rb_insert_callchain(&node->rb_root, child, in __sort_chain_graph_abs()
474 __sort_chain_graph_abs(&chain_root->node, min_hit); in sort_chain_graph_abs()
475 rb_root->rb_node = chain_root->node.rb_root.rb_node; in sort_chain_graph_abs()
478 static void __sort_chain_graph_rel(struct callchain_node *node, in __sort_chain_graph_rel() argument
482 struct callchain_node *child; in __sort_chain_graph_rel() local
485 node->rb_root = RB_ROOT; in __sort_chain_graph_rel()
486 min_hit = ceil(node->children_hit * min_percent); in __sort_chain_graph_rel()
488 n = rb_first(&node->rb_root_in); in __sort_chain_graph_rel()
490 child = rb_entry(n, struct callchain_node, rb_node_in); in __sort_chain_graph_rel()
493 __sort_chain_graph_rel(child, min_percent); in __sort_chain_graph_rel()
494 if (callchain_cumul_hits(child) >= min_hit) in __sort_chain_graph_rel()
495 rb_insert_callchain(&node->rb_root, child, in __sort_chain_graph_rel()
504 __sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0); in sort_chain_graph_rel()
505 rb_root->rb_node = chain_root->node.rb_root.rb_node; in sort_chain_graph_rel()
510 switch (param->mode) { in callchain_register_param()
512 param->sort = sort_chain_graph_abs; in callchain_register_param()
515 param->sort = sort_chain_graph_rel; in callchain_register_param()
519 param->sort = sort_chain_flat; in callchain_register_param()
523 return -1; in callchain_register_param()
529 * Create a child for a parent. If inherit_children, then the new child
539 perror("not enough memory to create child for code path tree"); in create_child()
542 new->parent = parent; in create_child()
543 INIT_LIST_HEAD(&new->val); in create_child()
544 INIT_LIST_HEAD(&new->parent_val); in create_child()
548 struct callchain_node *child; in create_child() local
550 new->rb_root_in = parent->rb_root_in; in create_child()
551 parent->rb_root_in = RB_ROOT; in create_child()
553 n = rb_first(&new->rb_root_in); in create_child()
555 child = rb_entry(n, struct callchain_node, rb_node_in); in create_child()
556 child->parent = new; in create_child()
560 /* make it the first child */ in create_child()
561 rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); in create_child()
562 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); in create_child()
570 * Fill the node with callchain values
573 fill_node(struct callchain_node *node, struct callchain_cursor *cursor) in fill_node() argument
577 node->val_nr = cursor->nr - cursor->pos; in fill_node()
578 if (!node->val_nr) in fill_node()
579 pr_warning("Warning: empty node in callchain tree\n"); in fill_node()
589 return -ENOMEM; in fill_node()
591 call->ip = cursor_node->ip; in fill_node()
592 call->ms = cursor_node->ms; in fill_node()
593 call->ms.map = map__get(call->ms.map); in fill_node()
594 call->ms.maps = maps__get(call->ms.maps); in fill_node()
595 call->srcline = cursor_node->srcline; in fill_node()
597 if (cursor_node->branch) { in fill_node()
598 call->branch_count = 1; in fill_node()
600 if (cursor_node->branch_from) { in fill_node()
605 if (!call->brtype_stat) { in fill_node()
606 call->brtype_stat = zalloc(sizeof(*call->brtype_stat)); in fill_node()
607 if (!call->brtype_stat) { in fill_node()
609 zfree(&call->brtype_stat); in fill_node()
610 return -ENOMEM; in fill_node()
613 call->brtype_stat->branch_to = true; in fill_node()
615 if (cursor_node->branch_flags.predicted) in fill_node()
616 call->predicted_count = 1; in fill_node()
618 if (cursor_node->branch_flags.abort) in fill_node()
619 call->abort_count = 1; in fill_node()
621 branch_type_count(call->brtype_stat, in fill_node()
622 &cursor_node->branch_flags, in fill_node()
623 cursor_node->branch_from, in fill_node()
624 cursor_node->ip); in fill_node()
629 if (call->brtype_stat && call->brtype_stat->branch_to) in fill_node()
630 call->brtype_stat->branch_to = false; in fill_node()
631 call->cycles_count = in fill_node()
632 cursor_node->branch_flags.cycles; in fill_node()
633 call->iter_count = cursor_node->nr_loop_iter; in fill_node()
634 call->iter_cycles = cursor_node->iter_cycles; in fill_node()
638 list_add_tail(&call->list, &node->val); in fill_node()
660 list_for_each_entry_safe(call, tmp, &new->val, list) { in add_child()
661 list_del_init(&call->list); in add_child()
662 map_symbol__exit(&call->ms); in add_child()
663 zfree(&call->brtype_stat); in add_child()
670 new->children_hit = 0; in add_child()
671 new->hit = period; in add_child()
672 new->children_count = 0; in add_child()
673 new->count = 1; in add_child()
678 MATCH_ERROR = -1,
695 cmp = -1; in match_chain_strings()
711 * to compare just relative addresses. -acme
728 static enum match_result match_chain(struct callchain_cursor_node *node, in match_chain() argument
735 match = match_chain_strings(cnode->srcline, node->srcline); in match_chain()
738 /* otherwise fall-back to symbol-based comparison below */ in match_chain()
741 if (node->ms.sym && cnode->ms.sym) { in match_chain()
748 if (cnode->ms.sym->inlined || node->ms.sym->inlined) { in match_chain()
749 match = match_chain_strings(cnode->ms.sym->name, in match_chain()
750 node->ms.sym->name); in match_chain()
754 match = match_chain_dso_addresses(cnode->ms.map, cnode->ms.sym->start, in match_chain()
755 node->ms.map, node->ms.sym->start); in match_chain()
759 /* otherwise fall-back to IP-based comparison below */ in match_chain()
763 match = match_chain_dso_addresses(cnode->ms.map, cnode->ip, node->ms.map, node->ip); in match_chain()
767 if (match == MATCH_EQ && node->branch) { in match_chain()
768 cnode->branch_count++; in match_chain()
770 if (node->branch_from) { in match_chain()
774 if (!cnode->brtype_stat) { in match_chain()
775 cnode->brtype_stat = zalloc(sizeof(*cnode->brtype_stat)); in match_chain()
776 if (!cnode->brtype_stat) { in match_chain()
781 cnode->brtype_stat->branch_to = true; in match_chain()
783 if (node->branch_flags.predicted) in match_chain()
784 cnode->predicted_count++; in match_chain()
786 if (node->branch_flags.abort) in match_chain()
787 cnode->abort_count++; in match_chain()
789 branch_type_count(cnode->brtype_stat, in match_chain()
790 &node->branch_flags, in match_chain()
791 node->branch_from, in match_chain()
792 node->ip); in match_chain()
797 if (cnode->brtype_stat && cnode->brtype_stat->branch_to) in match_chain()
798 cnode->brtype_stat->branch_to = false; in match_chain()
799 cnode->cycles_count += node->branch_flags.cycles; in match_chain()
800 cnode->iter_count += node->nr_loop_iter; in match_chain()
801 cnode->iter_cycles += node->iter_cycles; in match_chain()
802 cnode->from_count++; in match_chain()
810 * Split the parent in two parts (a new child is created) and
811 * give a part of its callchain to the created child.
812 * Then create another child to host the given callchain of new branch
827 return -1; in split_add_child()
829 /* split the callchain and move a part to the new child */ in split_add_child()
830 old_tail = parent->val.prev; in split_add_child()
831 list_del_range(&to_split->list, old_tail); in split_add_child()
832 new->val.next = &to_split->list; in split_add_child()
833 new->val.prev = old_tail; in split_add_child()
834 to_split->list.prev = &new->val; in split_add_child()
835 old_tail->next = &new->val; in split_add_child()
838 new->hit = parent->hit; in split_add_child()
839 new->children_hit = parent->children_hit; in split_add_child()
840 parent->children_hit = callchain_cumul_hits(new); in split_add_child()
841 new->val_nr = parent->val_nr - idx_local; in split_add_child()
842 parent->val_nr = idx_local; in split_add_child()
843 new->count = parent->count; in split_add_child()
844 new->children_count = parent->children_count; in split_add_child()
845 parent->children_count = callchain_cumul_counts(new); in split_add_child()
847 /* create a new child for the new branch if any */ in split_add_child()
848 if (idx_total < cursor->nr) { in split_add_child()
851 struct callchain_cursor_node *node; in split_add_child() local
854 parent->hit = 0; in split_add_child()
855 parent->children_hit += period; in split_add_child()
856 parent->count = 0; in split_add_child()
857 parent->children_count += 1; in split_add_child()
859 node = callchain_cursor_current(cursor); in split_add_child()
862 return -1; in split_add_child()
865 * This is second child since we moved parent's children in split_add_child()
866 * to new (first) child above. in split_add_child()
868 p = parent->rb_root_in.rb_node; in split_add_child()
870 cnode = list_first_entry(&first->val, struct callchain_list, in split_add_child()
873 if (match_chain(node, cnode) == MATCH_LT) in split_add_child()
874 pp = &p->rb_left; in split_add_child()
876 pp = &p->rb_right; in split_add_child()
878 rb_link_node(&new->rb_node_in, p, pp); in split_add_child()
879 rb_insert_color(&new->rb_node_in, &parent->rb_root_in); in split_add_child()
881 parent->hit = period; in split_add_child()
882 parent->count = 1; in split_add_child()
898 struct callchain_cursor_node *node; in append_chain_children() local
899 struct rb_node **p = &root->rb_root_in.rb_node; in append_chain_children()
902 node = callchain_cursor_current(cursor); in append_chain_children()
903 if (!node) in append_chain_children()
904 return -1; in append_chain_children()
918 return -1; in append_chain_children()
921 p = &parent->rb_left; in append_chain_children()
923 p = &parent->rb_right; in append_chain_children()
925 /* nothing in children, add to the current node */ in append_chain_children()
928 return -1; in append_chain_children()
930 rb_link_node(&rnode->rb_node_in, parent, p); in append_chain_children()
931 rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); in append_chain_children()
934 root->children_hit += period; in append_chain_children()
935 root->children_count++; in append_chain_children()
945 u64 start = cursor->pos; in append_chain()
951 * Lookup in the current node in append_chain()
956 list_for_each_entry(cnode, &root->val, list) { in append_chain()
957 struct callchain_cursor_node *node; in append_chain() local
959 node = callchain_cursor_current(cursor); in append_chain()
960 if (!node) in append_chain()
963 cmp = match_chain(node, cnode); in append_chain()
978 matches = cursor->pos - start; in append_chain()
980 /* we match only a part of the node. Split it and add the new chain */ in append_chain()
981 if (matches < root->val_nr) { in append_chain()
990 if (matches == root->val_nr && cursor->pos == cursor->nr) { in append_chain()
991 root->hit += period; in append_chain()
992 root->count++; in append_chain()
996 /* We match the node and still have a part remaining */ in append_chain()
1008 return -1; in callchain_append()
1010 if (!cursor->nr) in callchain_append()
1015 if (append_chain_children(&root->node, cursor, period) < 0) in callchain_append()
1016 return -1; in callchain_append()
1018 if (cursor->nr > root->max_depth) in callchain_append()
1019 root->max_depth = cursor->nr; in callchain_append()
1028 struct callchain_cursor_node **old_last = cursor->last; in merge_chain_branch()
1029 struct callchain_node *child; in merge_chain_branch() local
1032 int old_pos = cursor->nr; in merge_chain_branch()
1035 list_for_each_entry_safe(list, next_list, &src->val, list) { in merge_chain_branch()
1037 .maps = maps__get(list->ms.maps), in merge_chain_branch()
1038 .map = map__get(list->ms.map), in merge_chain_branch()
1040 callchain_cursor_append(cursor, list->ip, &ms, false, NULL, 0, 0, 0, list->srcline); in merge_chain_branch()
1041 list_del_init(&list->list); in merge_chain_branch()
1043 map_symbol__exit(&list->ms); in merge_chain_branch()
1044 zfree(&list->brtype_stat); in merge_chain_branch()
1048 if (src->hit) { in merge_chain_branch()
1050 if (append_chain_children(dst, cursor, src->hit) < 0) in merge_chain_branch()
1051 return -1; in merge_chain_branch()
1054 n = rb_first(&src->rb_root_in); in merge_chain_branch()
1056 child = container_of(n, struct callchain_node, rb_node_in); in merge_chain_branch()
1058 rb_erase(&child->rb_node_in, &src->rb_root_in); in merge_chain_branch()
1060 err = merge_chain_branch(cursor, dst, child); in merge_chain_branch()
1064 free(child); in merge_chain_branch()
1067 cursor->nr = old_pos; in merge_chain_branch()
1068 cursor->last = old_last; in merge_chain_branch()
1076 return merge_chain_branch(cursor, &dst->node, &src->node); in callchain_merge()
1085 struct callchain_cursor_node *node = *cursor->last; in callchain_cursor_append() local
1087 if (!node) { in callchain_cursor_append()
1088 node = calloc(1, sizeof(*node)); in callchain_cursor_append()
1089 if (!node) in callchain_cursor_append()
1090 return -ENOMEM; in callchain_cursor_append()
1092 *cursor->last = node; in callchain_cursor_append()
1095 node->ip = ip; in callchain_cursor_append()
1096 map_symbol__exit(&node->ms); in callchain_cursor_append()
1097 node->ms = *ms; in callchain_cursor_append()
1098 node->ms.maps = maps__get(ms->maps); in callchain_cursor_append()
1099 node->ms.map = map__get(ms->map); in callchain_cursor_append()
1100 node->branch = branch; in callchain_cursor_append()
1101 node->nr_loop_iter = nr_loop_iter; in callchain_cursor_append()
1102 node->iter_cycles = iter_cycles; in callchain_cursor_append()
1103 node->srcline = srcline; in callchain_cursor_append()
1106 memcpy(&node->branch_flags, flags, in callchain_cursor_append()
1109 node->branch_from = branch_from; in callchain_cursor_append()
1110 cursor->nr++; in callchain_cursor_append()
1112 cursor->last = &node->next; in callchain_cursor_append()
1122 if (sample->callchain == NULL && !symbol_conf.show_branchflag_count) in sample__resolve_callchain()
1127 return thread__resolve_callchain(al->thread, cursor, evsel, sample, in sample__resolve_callchain()
1135 if ((!symbol_conf.use_callchain || sample->callchain == NULL) && in hist_entry__append_callchain()
1138 return callchain_append(he->callchain, get_tls_callchain_cursor(), sample->period); in hist_entry__append_callchain()
1141 int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *node, in fill_callchain_info() argument
1144 struct machine *machine = node->ms.maps ? maps__machine(node->ms.maps) : NULL; in fill_callchain_info()
1146 maps__put(al->maps); in fill_callchain_info()
1147 al->maps = maps__get(node->ms.maps); in fill_callchain_info()
1148 map__put(al->map); in fill_callchain_info()
1149 al->map = map__get(node->ms.map); in fill_callchain_info()
1150 al->sym = node->ms.sym; in fill_callchain_info()
1151 al->srcline = node->srcline; in fill_callchain_info()
1152 al->addr = node->ip; in fill_callchain_info()
1154 if (al->sym == NULL) { in fill_callchain_info()
1157 if (al->map == NULL) in fill_callchain_info()
1160 if (maps__equal(al->maps, machine__kernel_maps(machine))) { in fill_callchain_info()
1162 al->cpumode = PERF_RECORD_MISC_KERNEL; in fill_callchain_info()
1163 al->level = 'k'; in fill_callchain_info()
1165 al->cpumode = PERF_RECORD_MISC_GUEST_KERNEL; in fill_callchain_info()
1166 al->level = 'g'; in fill_callchain_info()
1170 al->cpumode = PERF_RECORD_MISC_USER; in fill_callchain_info()
1171 al->level = '.'; in fill_callchain_info()
1173 al->cpumode = PERF_RECORD_MISC_GUEST_USER; in fill_callchain_info()
1174 al->level = 'u'; in fill_callchain_info()
1176 al->cpumode = PERF_RECORD_MISC_HYPERVISOR; in fill_callchain_info()
1177 al->level = 'H'; in fill_callchain_info()
1192 if (cl->ms.sym) { in callchain_list__sym_name()
1193 const char *inlined = cl->ms.sym->inlined ? " (inlined)" : ""; in callchain_list__sym_name()
1195 if (show_srcline && cl->srcline) in callchain_list__sym_name()
1197 cl->ms.sym->name, cl->srcline, in callchain_list__sym_name()
1201 cl->ms.sym->name, inlined); in callchain_list__sym_name()
1203 printed = scnprintf(bf, bfsize, "%#" PRIx64, cl->ip); in callchain_list__sym_name()
1206 scnprintf(bf + printed, bfsize - printed, " %s", in callchain_list__sym_name()
1207 cl->ms.map ? in callchain_list__sym_name()
1208 dso__short_name(map__dso(cl->ms.map)) : in callchain_list__sym_name()
1214 char *callchain_node__scnprintf_value(struct callchain_node *node, in callchain_node__scnprintf_value() argument
1218 u64 period = callchain_cumul_hits(node); in callchain_node__scnprintf_value()
1219 unsigned count = callchain_cumul_counts(node); in callchain_node__scnprintf_value()
1222 period = node->hit; in callchain_node__scnprintf_value()
1223 count = node->count; in callchain_node__scnprintf_value()
1243 int callchain_node__fprintf_value(struct callchain_node *node, in callchain_node__fprintf_value() argument
1247 u64 period = callchain_cumul_hits(node); in callchain_node__fprintf_value()
1248 unsigned count = callchain_cumul_counts(node); in callchain_node__fprintf_value()
1251 period = node->hit; in callchain_node__fprintf_value()
1252 count = node->count; in callchain_node__fprintf_value()
1269 static void callchain_counts_value(struct callchain_node *node, in callchain_counts_value() argument
1275 list_for_each_entry(clist, &node->val, list) { in callchain_counts_value()
1277 *branch_count += clist->branch_count; in callchain_counts_value()
1280 *predicted_count += clist->predicted_count; in callchain_counts_value()
1283 *abort_count += clist->abort_count; in callchain_counts_value()
1286 *cycles_count += clist->cycles_count; in callchain_counts_value()
1290 static int callchain_node_branch_counts_cumul(struct callchain_node *node, in callchain_node_branch_counts_cumul() argument
1296 struct callchain_node *child; in callchain_node_branch_counts_cumul() local
1299 n = rb_first(&node->rb_root_in); in callchain_node_branch_counts_cumul()
1301 child = rb_entry(n, struct callchain_node, rb_node_in); in callchain_node_branch_counts_cumul()
1304 callchain_node_branch_counts_cumul(child, branch_count, in callchain_node_branch_counts_cumul()
1309 callchain_counts_value(child, branch_count, in callchain_node_branch_counts_cumul()
1333 return callchain_node_branch_counts_cumul(&root->node, in callchain_branch_counts()
1368 bf + printed, bfsize - printed, 0.0); in branch_to_str()
1374 bf + printed, bfsize - printed, 0.1); in branch_to_str()
1378 printed += scnprintf(bf + printed, bfsize - printed, ")"); in branch_to_str()
1395 bf + printed, bfsize - printed); in branch_from_str()
1402 v, bf + printed, bfsize - printed); in branch_from_str()
1406 bf + printed, bfsize - printed); in branch_from_str()
1411 printed += scnprintf(bf + printed, bfsize - printed, ")"); in branch_from_str()
1428 if (brtype_stat->branch_to) { in counts_str_build()
1472 brtype_stat = clist->brtype_stat ?: &empty_brtype_stat; in callchain_list_counts__printf_value()
1473 branch_count = clist->branch_count; in callchain_list_counts__printf_value()
1474 predicted_count = clist->predicted_count; in callchain_list_counts__printf_value()
1475 abort_count = clist->abort_count; in callchain_list_counts__printf_value()
1476 cycles_count = clist->cycles_count; in callchain_list_counts__printf_value()
1477 iter_count = clist->iter_count; in callchain_list_counts__printf_value()
1478 iter_cycles = clist->iter_cycles; in callchain_list_counts__printf_value()
1479 from_count = clist->from_count; in callchain_list_counts__printf_value()
1487 static void free_callchain_node(struct callchain_node *node) in free_callchain_node() argument
1490 struct callchain_node *child; in free_callchain_node() local
1493 list_for_each_entry_safe(list, tmp, &node->parent_val, list) { in free_callchain_node()
1494 list_del_init(&list->list); in free_callchain_node()
1495 map_symbol__exit(&list->ms); in free_callchain_node()
1496 zfree(&list->brtype_stat); in free_callchain_node()
1500 list_for_each_entry_safe(list, tmp, &node->val, list) { in free_callchain_node()
1501 list_del_init(&list->list); in free_callchain_node()
1502 map_symbol__exit(&list->ms); in free_callchain_node()
1503 zfree(&list->brtype_stat); in free_callchain_node()
1507 n = rb_first(&node->rb_root_in); in free_callchain_node()
1509 child = container_of(n, struct callchain_node, rb_node_in); in free_callchain_node()
1511 rb_erase(&child->rb_node_in, &node->rb_root_in); in free_callchain_node()
1513 free_callchain_node(child); in free_callchain_node()
1514 free(child); in free_callchain_node()
1523 free_callchain_node(&root->node); in free_callchain()
1526 static u64 decay_callchain_node(struct callchain_node *node) in decay_callchain_node() argument
1528 struct callchain_node *child; in decay_callchain_node() local
1532 n = rb_first(&node->rb_root_in); in decay_callchain_node()
1534 child = container_of(n, struct callchain_node, rb_node_in); in decay_callchain_node()
1536 child_hits += decay_callchain_node(child); in decay_callchain_node()
1540 node->hit = (node->hit * 7) / 8; in decay_callchain_node()
1541 node->children_hit = child_hits; in decay_callchain_node()
1543 return node->hit; in decay_callchain_node()
1551 decay_callchain_node(&root->node); in decay_callchain()
1554 int callchain_node__make_parent_list(struct callchain_node *node) in callchain_node__make_parent_list() argument
1556 struct callchain_node *parent = node->parent; in callchain_node__make_parent_list()
1561 list_for_each_entry_reverse(chain, &parent->val, list) { in callchain_node__make_parent_list()
1566 new->has_children = false; in callchain_node__make_parent_list()
1567 new->ms.map = map__get(new->ms.map); in callchain_node__make_parent_list()
1568 list_add_tail(&new->list, &head); in callchain_node__make_parent_list()
1570 parent = parent->parent; in callchain_node__make_parent_list()
1574 list_move_tail(&chain->list, &node->parent_val); in callchain_node__make_parent_list()
1576 if (!list_empty(&node->parent_val)) { in callchain_node__make_parent_list()
1577 chain = list_first_entry(&node->parent_val, struct callchain_list, list); in callchain_node__make_parent_list()
1578 chain->has_children = rb_prev(&node->rb_node) || rb_next(&node->rb_node); in callchain_node__make_parent_list()
1580 chain = list_first_entry(&node->val, struct callchain_list, list); in callchain_node__make_parent_list()
1581 chain->has_children = false; in callchain_node__make_parent_list()
1587 list_del_init(&chain->list); in callchain_node__make_parent_list()
1588 map_symbol__exit(&chain->ms); in callchain_node__make_parent_list()
1589 zfree(&chain->brtype_stat); in callchain_node__make_parent_list()
1592 return -ENOMEM; in callchain_node__make_parent_list()
1598 struct callchain_cursor_node *node, *next; in callchain_cursor__delete() local
1601 for (node = cursor->first; node != NULL; node = next) { in callchain_cursor__delete()
1602 next = node->next; in callchain_cursor__delete()
1603 free(node); in callchain_cursor__delete()
1641 struct callchain_cursor_node *node; in callchain_cursor__copy() local
1643 node = callchain_cursor_current(src); in callchain_cursor__copy()
1644 if (node == NULL) in callchain_cursor__copy()
1647 rc = callchain_cursor_append(dst, node->ip, &node->ms, in callchain_cursor__copy()
1648 node->branch, &node->branch_flags, in callchain_cursor__copy()
1649 node->nr_loop_iter, in callchain_cursor__copy()
1650 node->iter_cycles, in callchain_cursor__copy()
1651 node->branch_from, node->srcline); in callchain_cursor__copy()
1667 struct callchain_cursor_node *node; in callchain_cursor_reset() local
1669 cursor->nr = 0; in callchain_cursor_reset()
1670 cursor->last = &cursor->first; in callchain_cursor_reset()
1672 for (node = cursor->first; node != NULL; node = node->next) in callchain_cursor_reset()
1673 map_symbol__exit(&node->ms); in callchain_cursor_reset()
1707 match = match_chain_strings(base_chain->srcline, in chain_match()
1708 pair_chain->srcline); in chain_match()
1712 match = match_chain_dso_addresses(base_chain->ms.map, in chain_match()
1713 base_chain->ip, in chain_match()
1714 pair_chain->ms.map, in chain_match()
1715 pair_chain->ip); in chain_match()
1726 pair_chain = list_first_entry(&pair_cnode->val, in callchain_cnode_matched()
1730 list_for_each_entry(base_chain, &base_cnode->val, list) { in callchain_cnode_matched()
1731 if (&pair_chain->list == &pair_cnode->val) in callchain_cnode_matched()
1734 if (!base_chain->srcline || !pair_chain->srcline) { in callchain_cnode_matched()
1750 if (pair_chain && (&pair_chain->list != &pair_cnode->val)) in callchain_cnode_matched()
1758 struct rb_root *root = &he->sorted_chain; in count_callchain_hits()
1760 struct callchain_node *node; in count_callchain_hits() local
1764 node = rb_entry(rb_node, struct callchain_node, rb_node); in count_callchain_hits()
1765 chain_hits += node->hit; in count_callchain_hits()
1774 struct rb_node *next = rb_first_cached(&hists->entries); in callchain_total_hits()
1782 next = rb_next(&he->rb_node); in callchain_total_hits()
1793 list_for_each_entry(chain, &cnode->val, list) { in callchain_avg_cycles()
1794 if (chain->srcline && chain->branch_count) in callchain_avg_cycles()
1795 cycles += chain->cycles_count / chain->branch_count; in callchain_avg_cycles()
1809 return -ENOMEM; in sample__for_each_callchain_node()
1822 struct callchain_cursor_node *node = callchain_cursor_current(cursor); in sample__for_each_callchain_node() local
1824 if (!node) in sample__for_each_callchain_node()
1827 ret = cb(node, data); in sample__for_each_callchain_node()