Release 4.10 tools/perf/util/callchain.c

/*
 * Copyright (C) 2009-2011, Frederic Weisbecker <fweisbec@gmail.com>
 *
 * Handle the callchains from the stream in an ad-hoc radix tree and then
 * sort them in an rbtree.
 *
 * Using a radix for code path provides a fast retrieval and factorizes
 * memory use. Also that lets us use the paths in a hierarchical graph view.
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <errno.h>
#include <math.h>

#include "asm/bug.h"

#include "hist.h"
#include "util.h"
#include "sort.h"
#include "machine.h"
#include "callchain.h"


__thread struct callchain_cursor callchain_cursor;



int parse_callchain_record_opt(const char *arg, struct callchain_param *param)
{
	return parse_callchain_record(arg, param);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
15
65.22%
1
25.00%
kan liang
kan liang
8
34.78%
3
75.00%
Total
23
100.00%
4
100.00%



static int parse_callchain_mode(const char *value)
{
	if (!strncmp(value, "graph", strlen(value))) {
		callchain_param.mode = CHAIN_GRAPH_ABS;
		return 0;
	}
	if (!strncmp(value, "flat", strlen(value))) {
		callchain_param.mode = CHAIN_FLAT;
		return 0;
	}
	if (!strncmp(value, "fractal", strlen(value))) {
		callchain_param.mode = CHAIN_GRAPH_REL;
		return 0;
	}
	if (!strncmp(value, "folded", strlen(value))) {
		callchain_param.mode = CHAIN_FOLDED;
		return 0;
	}
	return -1;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
don zickus
don zickus
60
50.42%
1
25.00%
namhyung kim
namhyung kim
59
49.58%
3
75.00%
Total
119
100.00%
4
100.00%



static int parse_callchain_order(const char *value)
{
	if (!strncmp(value, "caller", strlen(value))) {
		callchain_param.order = ORDER_CALLER;
		callchain_param.order_set = true;
		return 0;
	}
	if (!strncmp(value, "callee", strlen(value))) {
		callchain_param.order = ORDER_CALLEE;
		callchain_param.order_set = true;
		return 0;
	}
	return -1;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
46
58.23%
2
66.67%
don zickus
don zickus
33
41.77%
1
33.33%
Total
79
100.00%
3
100.00%



static int parse_callchain_sort_key(const char *value)
{
	if (!strncmp(value, "function", strlen(value))) {
		callchain_param.key = CCKEY_FUNCTION;
		return 0;
	}
	if (!strncmp(value, "address", strlen(value))) {
		callchain_param.key = CCKEY_ADDRESS;
		return 0;
	}
	if (!strncmp(value, "branch", strlen(value))) {
		callchain_param.branch_callstack = 1;
		return 0;
	}
	return -1;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
35
37.63%
1
33.33%
don zickus
don zickus
32
34.41%
1
33.33%
andi kleen
andi kleen
26
27.96%
1
33.33%
Total
93
100.00%
3
100.00%



static int parse_callchain_value(const char *value)
{
	if (!strncmp(value, "percent", strlen(value))) {
		callchain_param.value = CCVAL_PERCENT;
		return 0;
	}
	if (!strncmp(value, "period", strlen(value))) {
		callchain_param.value = CCVAL_PERIOD;
		return 0;
	}
	if (!strncmp(value, "count", strlen(value))) {
		callchain_param.value = CCVAL_COUNT;
		return 0;
	}
	return -1;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
93
100.00%
1
100.00%
Total
93
100.00%
1
100.00%


static int

__parse_callchain_report_opt(const char *arg, bool allow_record_opt)
{
	char *tok;
	char *endptr;
	bool minpcnt_set = false;
	bool record_opt_set = false;
	bool try_stack_size = false;

	callchain_param.enabled = true;
	symbol_conf.use_callchain = true;

	if (!arg)
		return 0;

	while ((tok = strtok((char *)arg, ",")) != NULL) {
		if (!strncmp(tok, "none", strlen(tok))) {
			callchain_param.mode = CHAIN_NONE;
			callchain_param.enabled = false;
			symbol_conf.use_callchain = false;
			return 0;
		}

		if (!parse_callchain_mode(tok) ||
		    !parse_callchain_order(tok) ||
		    !parse_callchain_sort_key(tok) ||
		    !parse_callchain_value(tok)) {
			/* parsing ok - move on to the next */
			try_stack_size = false;
			goto next;
		} else if (allow_record_opt && !record_opt_set) {
			if (parse_callchain_record(tok, &callchain_param))
				goto try_numbers;

			/* assume that number followed by 'dwarf' is stack size */
			if (callchain_param.record_mode == CALLCHAIN_DWARF)
				try_stack_size = true;

			record_opt_set = true;
			goto next;
		}

try_numbers:
		if (try_stack_size) {
			unsigned long size = 0;

			if (get_stack_size(tok, &size) < 0)
				return -1;
			callchain_param.dump_size = size;
			try_stack_size = false;
		} else if (!minpcnt_set) {
			/* try to get the min percent */
			callchain_param.min_percent = strtod(tok, &endptr);
			if (tok == endptr)
				return -1;
			minpcnt_set = true;
		} else {
			/* try print limit at last */
			callchain_param.print_limit = strtoul(tok, &endptr, 0);
			if (tok == endptr)
				return -1;
		}
next:
		arg = NULL;
	}

	if (callchain_register_param(&callchain_param) < 0) {
		pr_err("Can't register callchain params\n");
		return -1;
	}
	return 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
269
82.01%
4
66.67%
don zickus
don zickus
47
14.33%
1
16.67%
arnaldo carvalho de melo
arnaldo carvalho de melo
12
3.66%
1
16.67%
Total
328
100.00%
6
100.00%



int parse_callchain_report_opt(const char *arg)
{
	return __parse_callchain_report_opt(arg, false);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
18
100.00%
1
100.00%
Total
18
100.00%
1
100.00%



int parse_callchain_top_opt(const char *arg)
{
	return __parse_callchain_report_opt(arg, true);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
18
100.00%
1
100.00%
Total
18
100.00%
1
100.00%



int perf_callchain_config(const char *var, const char *value)
{
	char *endptr;

	if (prefixcmp(var, "call-graph."))
		return 0;
	var += sizeof("call-graph.") - 1;

	if (!strcmp(var, "record-mode"))
		return parse_callchain_record_opt(value, &callchain_param);
	if (!strcmp(var, "dump-size")) {
		unsigned long size = 0;
		int ret;

		ret = get_stack_size(value, &size);
		callchain_param.dump_size = size;

		return ret;
	}
	if (!strcmp(var, "print-type"))
		return parse_callchain_mode(value);
	if (!strcmp(var, "order"))
		return parse_callchain_order(value);
	if (!strcmp(var, "sort-key"))
		return parse_callchain_sort_key(value);
	if (!strcmp(var, "threshold")) {
		callchain_param.min_percent = strtod(value, &endptr);
		if (value == endptr)
			return -1;
	}
	if (!strcmp(var, "print-limit")) {
		callchain_param.print_limit = strtod(value, &endptr);
		if (value == endptr)
			return -1;
	}

	return 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
215
98.62%
1
50.00%
kan liang
kan liang
3
1.38%
1
50.00%
Total
218
100.00%
2
100.00%


static void

rb_insert_callchain(struct rb_root *root, struct callchain_node *chain,
		    enum chain_mode mode)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct callchain_node *rnode;
	u64 chain_cumul = callchain_cumul_hits(chain);

	while (*p) {
		u64 rnode_cumul;

		parent = *p;
		rnode = rb_entry(parent, struct callchain_node, rb_node);
		rnode_cumul = callchain_cumul_hits(rnode);

		switch (mode) {
		case CHAIN_FLAT:
		case CHAIN_FOLDED:
			if (rnode->hit < chain->hit)
				p = &(*p)->rb_left;
			else
				p = &(*p)->rb_right;
			break;
		case CHAIN_GRAPH_ABS: /* Falldown */
		case CHAIN_GRAPH_REL:
			if (rnode_cumul < chain_cumul)
				p = &(*p)->rb_left;
			else
				p = &(*p)->rb_right;
			break;
		case CHAIN_NONE:
		default:
			break;
		}
	}

	rb_link_node(&chain->rb_node, parent, p);
	rb_insert_color(&chain->rb_node, root);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
185
96.86%
5
71.43%
ingo molnar
ingo molnar
3
1.57%
1
14.29%
namhyung kim
namhyung kim
3
1.57%
1
14.29%
Total
191
100.00%
7
100.00%


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);

		__sort_chain_flat(rb_root, child, min_hit);
	}

	if (node->hit && node->hit >= min_hit)
		rb_insert_callchain(rb_root, node, CHAIN_FLAT);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
57
60.64%
4
80.00%
namhyung kim
namhyung kim
37
39.36%
1
20.00%
Total
94
100.00%
5
100.00%

/*
 * Once we get every callchains from the stream, we can now
 * sort them by hit
 */

static void

sort_chain_flat(struct rb_root *rb_root, struct callchain_root *root,
		u64 min_hit, struct callchain_param *param __maybe_unused)
{
	*rb_root = RB_ROOT;
	__sort_chain_flat(rb_root, &root->node, min_hit);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
36
85.71%
3
60.00%
namhyung kim
namhyung kim
5
11.90%
1
20.00%
irina tirdea
irina tirdea
1
2.38%
1
20.00%
Total
42
100.00%
5
100.00%



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);

		__sort_chain_graph_abs(child, min_hit);
		if (callchain_cumul_hits(child) >= min_hit)
			rb_insert_callchain(&node->rb_root, child,
					    CHAIN_GRAPH_ABS);
	}
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
57
61.29%
5
83.33%
namhyung kim
namhyung kim
36
38.71%
1
16.67%
Total
93
100.00%
6
100.00%


static void

sort_chain_graph_abs(struct rb_root *rb_root, struct callchain_root *chain_root,
		     u64 min_hit, struct callchain_param *param __maybe_unused)
{
	__sort_chain_graph_abs(&chain_root->node, min_hit);
	rb_root->rb_node = chain_root->node.rb_root.rb_node;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
46
97.87%
5
83.33%
irina tirdea
irina tirdea
1
2.13%
1
16.67%
Total
47
100.00%
6
100.00%



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);

		__sort_chain_graph_rel(child, min_percent);
		if (callchain_cumul_hits(child) >= min_hit)
			rb_insert_callchain(&node->rb_root, child,
					    CHAIN_GRAPH_REL);
	}
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
71
66.36%
4
80.00%
namhyung kim
namhyung kim
36
33.64%
1
20.00%
Total
107
100.00%
5
100.00%


static void

sort_chain_graph_rel(struct rb_root *rb_root, struct callchain_root *chain_root,
		     u64 min_hit __maybe_unused, struct callchain_param *param)
{
	__sort_chain_graph_rel(&chain_root->node, param->min_percent / 100.0);
	rb_root->rb_node = chain_root->node.rb_root.rb_node;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
50
98.04%
3
75.00%
irina tirdea
irina tirdea
1
1.96%
1
25.00%
Total
51
100.00%
4
100.00%



int callchain_register_param(struct callchain_param *param)
{
	switch (param->mode) {
	case CHAIN_GRAPH_ABS:
		param->sort = sort_chain_graph_abs;
		break;
	case CHAIN_GRAPH_REL:
		param->sort = sort_chain_graph_rel;
		break;
	case CHAIN_FLAT:
	case CHAIN_FOLDED:
		param->sort = sort_chain_flat;
		break;
	case CHAIN_NONE:
	default:
		return -1;
	}
	return 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
56
90.32%
2
50.00%
ingo molnar
ingo molnar
3
4.84%
1
25.00%
namhyung kim
namhyung kim
3
4.84%
1
25.00%
Total
62
100.00%
4
100.00%

/*
 * Create a child for a parent. If inherit_children, then the new child
 * will become the new parent of it's parent children
 */

static struct callchain_node *

create_child(struct callchain_node *parent, bool inherit_children)
{
	struct callchain_node *new;

	new = zalloc(sizeof(*new));
	if (!new) {
		perror("not enough memory to create child for code path tree");
		return NULL;
	}
	new->parent = parent;
	INIT_LIST_HEAD(&new->val);
	INIT_LIST_HEAD(&new->parent_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;

		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);
		}

		/* 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);
	}

	return new;
}


Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
100
57.47%
2
40.00%
namhyung kim
namhyung kim
73
41.95%
2
40.00%
arnaldo carvalho de melo
arnaldo carvalho de melo
1
0.57%
1
20.00%
Total
174
100.00%
5
100.00%

/*
 * Fill the node with callchain values
 */

static int

fill_node(struct callchain_node *node, struct callchain_cursor *cursor)
{
	struct callchain_cursor_node *cursor_node;

	node->val_nr = cursor->nr - cursor->pos;
	if (!node->val_nr)
		pr_warning("Warning: empty node in callchain tree\n");

	cursor_node = callchain_cursor_current(cursor);

	while (cursor_node) {
		struct callchain_list *call;

		call = zalloc(sizeof(*call));
		if (!call) {
			perror("not enough memory for the code path tree");
			return -1;
		}
		call->ip = cursor_node->ip;
		call->ms.sym = cursor_node->sym;
		call->ms.map = map__get(cursor_node->map);

		if (cursor_node->branch) {
			call->branch_count = 1;

			if (cursor_node->branch_flags.predicted)
				call->predicted_count = 1;

			if (cursor_node->branch_flags.abort)
				call->abort_count = 1;

			call->cycles_count = cursor_node->branch_flags.cycles;
			call->iter_count = cursor_node->nr_loop_iter;
			call->samples_count = cursor_node->samples;
		}

		list_add_tail(&call->list, &node->val);

		callchain_cursor_advance(cursor);
		cursor_node = callchain_cursor_current(cursor);
	}
	return 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
frederic weisbecker
frederic weisbecker
135
62.21%
6
54.55%
jin yao
jin yao
68
31.34%
1
9.09%
namhyung kim
namhyung kim
8
3.69%
1
9.09%
krister johansen
krister johansen
3
1.38%
1
9.09%
arnaldo carvalho de melo
arnaldo carvalho de melo
3
1.38%
2
18.18%
Total
217
100.00%
11
100.00%


static struct callchain_node *

add_child(struct callchain_node *parent,
	  struct callchain_cursor *cursor,
	  u64 period)
{
	struct callchain_node *new;

	new = create_child(parent, false);
	if (new == NULL)
		return NULL;

	if (fill_node(new, cursor) < 0) {
		struct callchain_list *call, *tmp;

		list_for_each_entry_safe(call, tmp, &new->val, list) {
			list_del(&call->list);
			map__zput(call->ms.map);
			free(call);
		}
		free(new);
		return NULL;
	}

	new->children_hit = 0;
	new->hit = period;
	new->children_count = 0;
	new->count = 1;
	return new;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
75
55.97%
4
36.36%
frederic weisbecker
frederic weisbecker
50
37.31%
6
54.55%
krister johansen
krister johansen
9
6.72%
1
9.09%
Total
134
100.00%
11
100.00%


enum match_result {
	
MATCH_ERROR  = -1,
	
MATCH_EQ,
	
MATCH_LT,
	
MATCH_GT,
};



static enum match_result match_chain(struct callchain_cursor_node *node,
				     struct callchain_list *cnode)
{
	struct symbol *sym = node->sym;
	u64 left, right;

	if (cnode->ms.sym && sym &&
	    callchain_param.key == CCKEY_FUNCTION) {
		left = cnode->ms.sym->start;
		right = sym->start;
	} else {
		left = cnode->ip;
		right = node->ip;
	}

	if (left == right) {
		if (node->branch) {
			cnode->branch_count++;

			if (node->branch_flags.predicted)
				cnode->predicted_count++;

			if (node->branch_flags.abort)
				cnode->abort_count++;

			cnode->cycles_count += node->branch_flags.cycles;
			cnode->iter_count += node->nr_loop_iter;
			cnode->samples_count += node->samples;
		}

		return MATCH_EQ;
	}

	return left > right ? MATCH_GT : MATCH_LT;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
97
58.79%
2
50.00%
jin yao
jin yao
67
40.61%
1
25.00%
frederic weisbecker
frederic weisbecker
1
0.61%
1
25.00%
Total
165
100.00%
4
100.00%

/*
 * Split the parent in two parts (a new child is created) and
 * give a part of its callchain to the created child.
 * Then create another child to host the given callchain of new branch
 */

static int

split_add_child(struct callchain_node *parent,
		struct callchain_cursor *cursor,
		struct callchain_list *to_split,
		u64 idx_parents, u64 idx_local, u64 period)
{
	struct callchain_node *new;
	struct list_head *old_tail;
	unsigned int idx_total = idx_parents + idx_local;

	/* split */
	new = create_child(parent, true);
	if (new == NULL)
		return -1;

	/* split the callchain and move a part to the new child */
	old_tail = parent->val.prev;
	list_del_range(&to_split->list, old_tail);
	new->val.next = &to_split->list;
	new->val.prev = old_tail;
	to_split->list.prev = &new->val;
	old_tail->next = &new->val;

	/* split the hits */
	new->hit = parent->hit;
	new->children_hit = parent->children_hit;
	parent->children_hit = callchain_cumul_hits(new);
	new->val_nr = parent->val_nr - idx_local;
	parent->val_nr = idx_local;
	new->count = parent->count;
	new->children_count = parent->children_count;
	parent->children_count = callchain_cumul_counts(new);

	/* 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;
		parent->children_hit += period;
		parent->count = 0;
		parent->children_count += 1;

		node = callchain_cursor_current(cursor);
		new = add_child(parent, cursor, period);
		if (new == NULL)
			return -1;

		/*
                 * 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) == MATCH_LT)
			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;
		parent->count = 1;
	}
	return 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
namhyung kim
namhyung kim
195
50.65%
5
38.46%
frederic weisbecker
frederic weisbecker
189
49.09%
7
53.85%
ingo molnar
ingo molnar
1
0.26%
1
7.69%
Total
385
100.00%
13
100.00%

static enum match_result
append_chain(struct callchain_node *root,
	     struct callchain_cursor *cursor,
	     u64 period);


static int

append_chain_children