diff options
Diffstat (limited to 'tools/perf/util/callchain.c')
-rw-r--r-- | tools/perf/util/callchain.c | 147 |
1 files changed, 36 insertions, 111 deletions
diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c index e3970e3..482f680 100644 --- a/tools/perf/util/callchain.c +++ b/tools/perf/util/callchain.c @@ -21,6 +21,12 @@ __thread struct callchain_cursor callchain_cursor; +#define chain_for_each_child(child, parent) \ + list_for_each_entry(child, &parent->children, siblings) + +#define chain_for_each_child_safe(child, next, parent) \ + list_for_each_entry_safe(child, next, &parent->children, siblings) + static void rb_insert_callchain(struct rb_root *root, struct callchain_node *chain, enum chain_mode mode) @@ -65,16 +71,10 @@ static void __sort_chain_flat(struct rb_root *rb_root, struct callchain_node *node, u64 min_hit) { - struct rb_node *n; struct callchain_node *child; - n = rb_first(&node->rb_root_in); - while (n) { - child = rb_entry(n, struct callchain_node, rb_node_in); - n = rb_next(n); - + chain_for_each_child(child, node) __sort_chain_flat(rb_root, child, min_hit); - } if (node->hit && node->hit >= min_hit) rb_insert_callchain(rb_root, node, CHAIN_FLAT); @@ -94,16 +94,11 @@ sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root, static void __sort_chain_graph_abs(struct callchain_node *node, u64 min_hit) { - struct rb_node *n; struct callchain_node *child; node->rb_root = RB_ROOT; - n = rb_first(&node->rb_root_in); - - while (n) { - child = rb_entry(n, struct callchain_node, rb_node_in); - n = rb_next(n); + chain_for_each_child(child, node) { __sort_chain_graph_abs(child, min_hit); if (callchain_cumul_hits(child) >= min_hit) rb_insert_callchain(&node->rb_root, child, @@ -122,18 +117,13 @@ sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root, static void __sort_chain_graph_rel(struct callchain_node *node, double min_percent) { - struct rb_node *n; struct callchain_node *child; u64 min_hit; node->rb_root = RB_ROOT; min_hit = ceil(node->children_hit * min_percent); - n = rb_first(&node->rb_root_in); - while (n) { - child = rb_entry(n, struct callchain_node, rb_node_in); - n = rb_next(n); - + chain_for_each_child(child, node) { __sort_chain_graph_rel(child, min_percent); if (callchain_cumul_hits(child) >= min_hit) rb_insert_callchain(&node->rb_root, child, @@ -183,26 +173,19 @@ create_child(struct callchain_node *parent, bool inherit_children) return NULL; } new->parent = parent; + INIT_LIST_HEAD(&new->children); INIT_LIST_HEAD(&new->val); if (inherit_children) { - struct rb_node *n; - struct callchain_node *child; - - new->rb_root_in = parent->rb_root_in; - parent->rb_root_in = RB_ROOT; + struct callchain_node *next; - n = rb_first(&new->rb_root_in); - while (n) { - child = rb_entry(n, struct callchain_node, rb_node_in); - child->parent = new; - n = rb_next(n); - } + list_splice(&parent->children, &new->children); + INIT_LIST_HEAD(&parent->children); - /* make it the first child */ - rb_link_node(&new->rb_node_in, NULL, &parent->rb_root_in.rb_node); - rb_insert_color(&new->rb_node_in, &parent->rb_root_in); + chain_for_each_child(next, new) + next->parent = new; } + list_add_tail(&new->siblings, &parent->children); return new; } @@ -240,7 +223,7 @@ fill_node(struct callchain_node *node, struct callchain_cursor *cursor) } } -static struct callchain_node * +static void add_child(struct callchain_node *parent, struct callchain_cursor *cursor, u64 period) @@ -252,19 +235,6 @@ add_child(struct callchain_node *parent, new->children_hit = 0; new->hit = period; - return new; -} - -static s64 match_chain(struct callchain_cursor_node *node, - struct callchain_list *cnode) -{ - struct symbol *sym = node->sym; - - if (cnode->ms.sym && sym && - callchain_param.key == CCKEY_FUNCTION) - return cnode->ms.sym->start - sym->start; - else - return cnode->ip - node->ip; } /* @@ -302,33 +272,9 @@ split_add_child(struct callchain_node *parent, /* create a new child for the new branch if any */ if (idx_total < cursor->nr) { - struct callchain_node *first; - struct callchain_list *cnode; - struct callchain_cursor_node *node; - struct rb_node *p, **pp; - parent->hit = 0; + add_child(parent, cursor, period); parent->children_hit += period; - - node = callchain_cursor_current(cursor); - new = add_child(parent, cursor, period); - - /* - * This is second child since we moved parent's children - * to new (first) child above. - */ - p = parent->rb_root_in.rb_node; - first = rb_entry(p, struct callchain_node, rb_node_in); - cnode = list_first_entry(&first->val, struct callchain_list, - list); - - if (match_chain(node, cnode) < 0) - pp = &p->rb_left; - else - pp = &p->rb_right; - - rb_link_node(&new->rb_node_in, p, pp); - rb_insert_color(&new->rb_node_in, &parent->rb_root_in); } else { parent->hit = period; } @@ -345,40 +291,16 @@ append_chain_children(struct callchain_node *root, u64 period) { struct callchain_node *rnode; - struct callchain_cursor_node *node; - struct rb_node **p = &root->rb_root_in.rb_node; - struct rb_node *parent = NULL; - - node = callchain_cursor_current(cursor); - if (!node) - return; /* lookup in childrens */ - while (*p) { - s64 ret; - struct callchain_list *cnode; + chain_for_each_child(rnode, root) { + unsigned int ret = append_chain(rnode, cursor, period); - parent = *p; - rnode = rb_entry(parent, struct callchain_node, rb_node_in); - cnode = list_first_entry(&rnode->val, struct callchain_list, - list); - - /* just check first entry */ - ret = match_chain(node, cnode); - if (ret == 0) { - append_chain(rnode, cursor, period); + if (!ret) goto inc_children_hit; - } - - if (ret < 0) - p = &parent->rb_left; - else - p = &parent->rb_right; } /* nothing in children, add to the current node */ - rnode = add_child(root, cursor, period); - rb_link_node(&rnode->rb_node_in, parent, p); - rb_insert_color(&rnode->rb_node_in, &root->rb_root_in); + add_child(root, cursor, period); inc_children_hit: root->children_hit += period; @@ -403,20 +325,28 @@ append_chain(struct callchain_node *root, */ list_for_each_entry(cnode, &root->val, list) { struct callchain_cursor_node *node; + struct symbol *sym; node = callchain_cursor_current(cursor); if (!node) break; - if (match_chain(node, cnode) != 0) + sym = node->sym; + + if (cnode->ms.sym && sym && + callchain_param.key == CCKEY_FUNCTION) { + if (cnode->ms.sym->start != sym->start) + break; + } else if (cnode->ip != node->ip) break; - found = true; + if (!found) + found = true; callchain_cursor_advance(cursor); } - /* matches not, relay no the parent */ + /* matches not, relay on the parent */ if (!found) { cursor->curr = curr_snap; cursor->pos = start; @@ -465,9 +395,8 @@ merge_chain_branch(struct callchain_cursor *cursor, struct callchain_node *dst, struct callchain_node *src) { struct callchain_cursor_node **old_last = cursor->last; - struct callchain_node *child; + struct callchain_node *child, *next_child; struct callchain_list *list, *next_list; - struct rb_node *n; int old_pos = cursor->nr; int err = 0; @@ -483,16 +412,12 @@ merge_chain_branch(struct callchain_cursor *cursor, append_chain_children(dst, cursor, src->hit); } - n = rb_first(&src->rb_root_in); - while (n) { - child = container_of(n, struct callchain_node, rb_node_in); - n = rb_next(n); - rb_erase(&child->rb_node_in, &src->rb_root_in); - + chain_for_each_child_safe(child, next_child, src) { err = merge_chain_branch(cursor, dst, child); if (err) break; + list_del(&child->siblings); free(child); } |