[deliverable/linux.git] / tools / perf / util / hist.c

#include "hist.h"
#include "session.h"
#include "sort.h"
#include <math.h>

struct callchain_param	callchain_param = {
	.mode	= CHAIN_GRAPH_REL,
	.min_percent = 0.5
};

/*
 * histogram, sorted on item, collects counts
 */

struct hist_entry *__perf_session__add_hist_entry(struct rb_root *hists,
						  struct addr_location *al,
						  struct symbol *sym_parent,
						  u64 count, bool *hit)
{
	struct rb_node **p = &hists->rb_node;
	struct rb_node *parent = NULL;
	struct hist_entry *he;
	struct hist_entry entry = {
		.thread	= al->thread,
		.ms = {
			.map	= al->map,
			.sym	= al->sym,
		},
		.ip	= al->addr,
		.level	= al->level,
		.count	= count,
		.parent = sym_parent,
	};
	int cmp;

	while (*p != NULL) {
		parent = *p;
		he = rb_entry(parent, struct hist_entry, rb_node);

		cmp = hist_entry__cmp(&entry, he);

		if (!cmp) {
			*hit = true;
			return he;
		}

		if (cmp < 0)
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

	he = malloc(sizeof(*he));
	if (!he)
		return NULL;
	*he = entry;
	rb_link_node(&he->rb_node, parent, p);
	rb_insert_color(&he->rb_node, hists);
	*hit = false;
	return he;
}

int64_t
hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
{
	struct sort_entry *se;
	int64_t cmp = 0;

	list_for_each_entry(se, &hist_entry__sort_list, list) {
		cmp = se->cmp(left, right);
		if (cmp)
			break;
	}

	return cmp;
}

int64_t
hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
{
	struct sort_entry *se;
	int64_t cmp = 0;

	list_for_each_entry(se, &hist_entry__sort_list, list) {
		int64_t (*f)(struct hist_entry *, struct hist_entry *);

		f = se->collapse ?: se->cmp;

		cmp = f(left, right);
		if (cmp)
			break;
	}

	return cmp;
}

void hist_entry__free(struct hist_entry *he)
{
	free(he);
}

/*
 * collapse the histogram
 */

static void collapse__insert_entry(struct rb_root *root, struct hist_entry *he)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct hist_entry *iter;
	int64_t cmp;

	while (*p != NULL) {
		parent = *p;
		iter = rb_entry(parent, struct hist_entry, rb_node);

		cmp = hist_entry__collapse(iter, he);

		if (!cmp) {
			iter->count += he->count;
			hist_entry__free(he);
			return;
		}

		if (cmp < 0)
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

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

void perf_session__collapse_resort(struct rb_root *hists)
{
	struct rb_root tmp;
	struct rb_node *next;
	struct hist_entry *n;

	if (!sort__need_collapse)
		return;

	tmp = RB_ROOT;
	next = rb_first(hists);

	while (next) {
		n = rb_entry(next, struct hist_entry, rb_node);
		next = rb_next(&n->rb_node);

		rb_erase(&n->rb_node, hists);
		collapse__insert_entry(&tmp, n);
	}

	*hists = tmp;
}

/*
 * reverse the map, sort on count.
 */

static void perf_session__insert_output_hist_entry(struct rb_root *root,
						   struct hist_entry *he,
						   u64 min_callchain_hits)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct hist_entry *iter;

	if (symbol_conf.use_callchain)
		callchain_param.sort(&he->sorted_chain, &he->callchain,
				      min_callchain_hits, &callchain_param);

	while (*p != NULL) {
		parent = *p;
		iter = rb_entry(parent, struct hist_entry, rb_node);

		if (he->count > iter->count)
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

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

void perf_session__output_resort(struct rb_root *hists, u64 total_samples)
{
	struct rb_root tmp;
	struct rb_node *next;
	struct hist_entry *n;
	u64 min_callchain_hits;

	min_callchain_hits =
		total_samples * (callchain_param.min_percent / 100);

	tmp = RB_ROOT;
	next = rb_first(hists);

	while (next) {
		n = rb_entry(next, struct hist_entry, rb_node);
		next = rb_next(&n->rb_node);

		rb_erase(&n->rb_node, hists);
		perf_session__insert_output_hist_entry(&tmp, n,
						       min_callchain_hits);
	}

	*hists = tmp;
}

static size_t callchain__fprintf_left_margin(FILE *fp, int left_margin)
{
	int i;
	int ret = fprintf(fp, "            ");

	for (i = 0; i < left_margin; i++)
		ret += fprintf(fp, " ");

	return ret;
}

static size_t ipchain__fprintf_graph_line(FILE *fp, int depth, int depth_mask,
					  int left_margin)
{
	int i;
	size_t ret = callchain__fprintf_left_margin(fp, left_margin);

	for (i = 0; i < depth; i++)
		if (depth_mask & (1 << i))
			ret += fprintf(fp, "|          ");
		else
			ret += fprintf(fp, "           ");

	ret += fprintf(fp, "\n");

	return ret;
}

static size_t ipchain__fprintf_graph(FILE *fp, struct callchain_list *chain,
				     int depth, int depth_mask, int count,
				     u64 total_samples, int hits,
				     int left_margin)
{
	int i;
	size_t ret = 0;

	ret += callchain__fprintf_left_margin(fp, left_margin);
	for (i = 0; i < depth; i++) {
		if (depth_mask & (1 << i))
			ret += fprintf(fp, "|");
		else
			ret += fprintf(fp, " ");
		if (!count && i == depth - 1) {
			double percent;

			percent = hits * 100.0 / total_samples;
			ret += percent_color_fprintf(fp, "--%2.2f%%-- ", percent);
		} else
			ret += fprintf(fp, "%s", "          ");
	}
	if (chain->ms.sym)
		ret += fprintf(fp, "%s\n", chain->ms.sym->name);
	else
		ret += fprintf(fp, "%p\n", (void *)(long)chain->ip);

	return ret;
}

static struct symbol *rem_sq_bracket;
static struct callchain_list rem_hits;

static void init_rem_hits(void)
{
	rem_sq_bracket = malloc(sizeof(*rem_sq_bracket) + 6);
	if (!rem_sq_bracket) {
		fprintf(stderr, "Not enough memory to display remaining hits\n");
		return;
	}

	strcpy(rem_sq_bracket->name, "[...]");
	rem_hits.ms.sym = rem_sq_bracket;
}

static size_t __callchain__fprintf_graph(FILE *fp, struct callchain_node *self,
					 u64 total_samples, int depth,
					 int depth_mask, int left_margin)
{
	struct rb_node *node, *next;
	struct callchain_node *child;
	struct callchain_list *chain;
	int new_depth_mask = depth_mask;
	u64 new_total;
	u64 remaining;
	size_t ret = 0;
	int i;

	if (callchain_param.mode == CHAIN_GRAPH_REL)
		new_total = self->children_hit;
	else
		new_total = total_samples;

	remaining = new_total;

	node = rb_first(&self->rb_root);
	while (node) {
		u64 cumul;

		child = rb_entry(node, struct callchain_node, rb_node);
		cumul = cumul_hits(child);
		remaining -= cumul;

		/*
		 * The depth mask manages the output of pipes that show
		 * the depth. We don't want to keep the pipes of the current
		 * level for the last child of this depth.
		 * Except if we have remaining filtered hits. They will
		 * supersede the last child
		 */
		next = rb_next(node);
		if (!next && (callchain_param.mode != CHAIN_GRAPH_REL || !remaining))
			new_depth_mask &= ~(1 << (depth - 1));

		/*
		 * But we keep the older depth mask for the line separator
		 * to keep the level link until we reach the last child
		 */
		ret += ipchain__fprintf_graph_line(fp, depth, depth_mask,
						   left_margin);
		i = 0;
		list_for_each_entry(chain, &child->val, list) {
			ret += ipchain__fprintf_graph(fp, chain, depth,
						      new_depth_mask, i++,
						      new_total,
						      cumul,
						      left_margin);
		}
		ret += __callchain__fprintf_graph(fp, child, new_total,
						  depth + 1,
						  new_depth_mask | (1 << depth),
						  left_margin);
		node = next;
	}

	if (callchain_param.mode == CHAIN_GRAPH_REL &&
		remaining && remaining != new_total) {

		if (!rem_sq_bracket)
			return ret;

		new_depth_mask &= ~(1 << (depth - 1));

		ret += ipchain__fprintf_graph(fp, &rem_hits, depth,
					      new_depth_mask, 0, new_total,
					      remaining, left_margin);
	}

	return ret;
}

static size_t callchain__fprintf_graph(FILE *fp, struct callchain_node *self,
				       u64 total_samples, int left_margin)
{
	struct callchain_list *chain;
	bool printed = false;
	int i = 0;
	int ret = 0;

	list_for_each_entry(chain, &self->val, list) {
		if (!i++ && sort__first_dimension == SORT_SYM)
			continue;

		if (!printed) {
			ret += callchain__fprintf_left_margin(fp, left_margin);
			ret += fprintf(fp, "|\n");
			ret += callchain__fprintf_left_margin(fp, left_margin);
			ret += fprintf(fp, "---");

			left_margin += 3;
			printed = true;
		} else
			ret += callchain__fprintf_left_margin(fp, left_margin);

		if (chain->ms.sym)
			ret += fprintf(fp, " %s\n", chain->ms.sym->name);
		else
			ret += fprintf(fp, " %p\n", (void *)(long)chain->ip);
	}

	ret += __callchain__fprintf_graph(fp, self, total_samples, 1, 1, left_margin);

	return ret;
}

static size_t callchain__fprintf_flat(FILE *fp, struct callchain_node *self,
				      u64 total_samples)
{
	struct callchain_list *chain;
	size_t ret = 0;

	if (!self)
		return 0;

	ret += callchain__fprintf_flat(fp, self->parent, total_samples);


	list_for_each_entry(chain, &self->val, list) {
		if (chain->ip >= PERF_CONTEXT_MAX)
			continue;
		if (chain->ms.sym)
			ret += fprintf(fp, "                %s\n", chain->ms.sym->name);
		else
			ret += fprintf(fp, "                %p\n",
					(void *)(long)chain->ip);
	}

	return ret;
}

static size_t hist_entry_callchain__fprintf(FILE *fp, struct hist_entry *self,
					    u64 total_samples, int left_margin)
{
	struct rb_node *rb_node;
	struct callchain_node *chain;
	size_t ret = 0;

	rb_node = rb_first(&self->sorted_chain);
	while (rb_node) {
		double percent;

		chain = rb_entry(rb_node, struct callchain_node, rb_node);
		percent = chain->hit * 100.0 / total_samples;
		switch (callchain_param.mode) {
		case CHAIN_FLAT:
			ret += percent_color_fprintf(fp, "           %6.2f%%\n",
						     percent);
			ret += callchain__fprintf_flat(fp, chain, total_samples);
			break;
		case CHAIN_GRAPH_ABS: /* Falldown */
		case CHAIN_GRAPH_REL:
			ret += callchain__fprintf_graph(fp, chain, total_samples,
							left_margin);
		case CHAIN_NONE:
		default:
			break;
		}
		ret += fprintf(fp, "\n");
		rb_node = rb_next(rb_node);
	}

	return ret;
}

size_t hist_entry__fprintf(struct hist_entry *self,
			   struct perf_session *pair_session,
			   bool show_displacement,
			   long displacement, FILE *fp,
			   u64 session_total)
{
	struct sort_entry *se;
	u64 count, total;
	const char *sep = symbol_conf.field_sep;
	size_t ret;

	if (symbol_conf.exclude_other && !self->parent)
		return 0;

	if (pair_session) {
		count = self->pair ? self->pair->count : 0;
		total = pair_session->events_stats.total;
	} else {
		count = self->count;
		total = session_total;
	}

	if (total)
		ret = percent_color_fprintf(fp, sep ? "%.2f" : "   %6.2f%%",
					    (count * 100.0) / total);
	else
		ret = fprintf(fp, sep ? "%lld" : "%12lld ", count);

	if (symbol_conf.show_nr_samples) {
		if (sep)
			ret += fprintf(fp, "%c%lld", *sep, count);
		else
			ret += fprintf(fp, "%11lld", count);
	}

	if (pair_session) {
		char bf[32];
		double old_percent = 0, new_percent = 0, diff;

		if (total > 0)
			old_percent = (count * 100.0) / total;
		if (session_total > 0)
			new_percent = (self->count * 100.0) / session_total;

		diff = new_percent - old_percent;

		if (fabs(diff) >= 0.01)
			snprintf(bf, sizeof(bf), "%+4.2F%%", diff);
		else
			snprintf(bf, sizeof(bf), " ");

		if (sep)
			ret += fprintf(fp, "%c%s", *sep, bf);
		else
			ret += fprintf(fp, "%11.11s", bf);

		if (show_displacement) {
			if (displacement)
				snprintf(bf, sizeof(bf), "%+4ld", displacement);
			else
				snprintf(bf, sizeof(bf), " ");

			if (sep)
				ret += fprintf(fp, "%c%s", *sep, bf);
			else
				ret += fprintf(fp, "%6.6s", bf);
		}
	}

	list_for_each_entry(se, &hist_entry__sort_list, list) {
		if (se->elide)
			continue;

		ret += fprintf(fp, "%s", sep ?: "  ");
		ret += se->print(fp, self, se->width ? *se->width : 0);
	}

	return ret + fprintf(fp, "\n");
}

static size_t hist_entry__fprintf_callchain(struct hist_entry *self, FILE *fp,
					    u64 session_total)
{
	int left_margin = 0;

	if (sort__first_dimension == SORT_COMM) {
		struct sort_entry *se = list_first_entry(&hist_entry__sort_list,
							 typeof(*se), list);
		left_margin = se->width ? *se->width : 0;
		left_margin -= thread__comm_len(self->thread);
	}

	return hist_entry_callchain__fprintf(fp, self, session_total,
					     left_margin);
}

size_t perf_session__fprintf_hists(struct rb_root *hists,
				   struct perf_session *pair,
				   bool show_displacement, FILE *fp,
				   u64 session_total)
{
	struct sort_entry *se;
	struct rb_node *nd;
	size_t ret = 0;
	unsigned long position = 1;
	long displacement = 0;
	unsigned int width;
	const char *sep = symbol_conf.field_sep;
	char *col_width = symbol_conf.col_width_list_str;

	init_rem_hits();

	fprintf(fp, "# %s", pair ? "Baseline" : "Overhead");

	if (symbol_conf.show_nr_samples) {
		if (sep)
			fprintf(fp, "%cSamples", *sep);
		else
			fputs("  Samples  ", fp);
	}

	if (pair) {
		if (sep)
			ret += fprintf(fp, "%cDelta", *sep);
		else
			ret += fprintf(fp, "  Delta    ");

		if (show_displacement) {
			if (sep)
				ret += fprintf(fp, "%cDisplacement", *sep);
			else
				ret += fprintf(fp, " Displ");
		}
	}

	list_for_each_entry(se, &hist_entry__sort_list, list) {
		if (se->elide)
			continue;
		if (sep) {
			fprintf(fp, "%c%s", *sep, se->header);
			continue;
		}
		width = strlen(se->header);
		if (se->width) {
			if (symbol_conf.col_width_list_str) {
				if (col_width) {
					*se->width = atoi(col_width);
					col_width = strchr(col_width, ',');
					if (col_width)
						++col_width;
				}
			}
			width = *se->width = max(*se->width, width);
		}
		fprintf(fp, "  %*s", width, se->header);
	}
	fprintf(fp, "\n");

	if (sep)
		goto print_entries;

	fprintf(fp, "# ........");
	if (symbol_conf.show_nr_samples)
		fprintf(fp, " ..........");
	if (pair) {
		fprintf(fp, " ..........");
		if (show_displacement)
			fprintf(fp, " .....");
	}
	list_for_each_entry(se, &hist_entry__sort_list, list) {
		unsigned int i;

		if (se->elide)
			continue;

		fprintf(fp, "  ");
		if (se->width)
			width = *se->width;
		else
			width = strlen(se->header);
		for (i = 0; i < width; i++)
			fprintf(fp, ".");
	}

	fprintf(fp, "\n#\n");

print_entries:
	for (nd = rb_first(hists); nd; nd = rb_next(nd)) {
		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);

		if (show_displacement) {
			if (h->pair != NULL)
				displacement = ((long)h->pair->position -
					        (long)position);
			else
				displacement = 0;
			++position;
		}
		ret += hist_entry__fprintf(h, pair, show_displacement,
					   displacement, fp, session_total);

		if (symbol_conf.use_callchain)
			ret += hist_entry__fprintf_callchain(h, fp, session_total);

		if (h->ms.map == NULL && verbose > 1) {
			__map_groups__fprintf_maps(&h->thread->mg,
						   MAP__FUNCTION, verbose, fp);
			fprintf(fp, "%.10s end\n", graph_dotted_line);
		}
	}

	free(rem_sq_bracket);

	return ret;
}
Commit	Line	Data
3d1d07ec	1	#include "hist.h"
4e4f06e4 ACM	2	#include "session.h"
4e4f06e4 ACM	3	#include "sort.h"
9b33827d	4	#include <math.h>
3d1d07ec JK	5
	6	struct callchain_param callchain_param = {
	7	.mode = CHAIN_GRAPH_REL,
	8	.min_percent = 0.5
	9	};
	10
3d1d07ec JK	11	/*
	12	* histogram, sorted on item, collects counts
	13	*/
	14
d403d0ac	15	struct hist_entry __perf_session__add_hist_entry(struct rb_root hists,
4e4f06e4 ACM	16	struct addr_location *al,
	17	struct symbol *sym_parent,
	18	u64 count, bool *hit)
9735abf1	19	{
d403d0ac	20	struct rb_node **p = &hists->rb_node;
9735abf1 ACM	21	struct rb_node *parent = NULL;
	22	struct hist_entry *he;
	23	struct hist_entry entry = {
1ed091c4	24	.thread = al->thread,
59fd5306 ACM	25	.ms = {
	26	.map = al->map,
	27	.sym = al->sym,
	28	},
1ed091c4 ACM	29	.ip = al->addr,
1ed091c4 ACM	30	.level = al->level,
9735abf1 ACM	31	.count = count,
	32	.parent = sym_parent,
	33	};
	34	int cmp;
	35
	36	while (*p != NULL) {
	37	parent = *p;
	38	he = rb_entry(parent, struct hist_entry, rb_node);
	39
	40	cmp = hist_entry__cmp(&entry, he);
	41
	42	if (!cmp) {
	43	*hit = true;
	44	return he;
	45	}
	46
	47	if (cmp < 0)
	48	p = &(*p)->rb_left;
	49	else
	50	p = &(*p)->rb_right;
	51	}
	52
	53	he = malloc(sizeof(*he));
	54	if (!he)
	55	return NULL;
	56	*he = entry;
	57	rb_link_node(&he->rb_node, parent, p);
d403d0ac	58	rb_insert_color(&he->rb_node, hists);
9735abf1 ACM	59	*hit = false;
	60	return he;
	61	}
	62
3d1d07ec JK	63	int64_t
	64	hist_entry__cmp(struct hist_entry left, struct hist_entry right)
	65	{
	66	struct sort_entry *se;
	67	int64_t cmp = 0;
	68
	69	list_for_each_entry(se, &hist_entry__sort_list, list) {
	70	cmp = se->cmp(left, right);
	71	if (cmp)
	72	break;
	73	}
	74
	75	return cmp;
	76	}
	77
	78	int64_t
	79	hist_entry__collapse(struct hist_entry left, struct hist_entry right)
	80	{
	81	struct sort_entry *se;
	82	int64_t cmp = 0;
	83
	84	list_for_each_entry(se, &hist_entry__sort_list, list) {
	85	int64_t (f)(struct hist_entry , struct hist_entry *);
	86
	87	f = se->collapse ?: se->cmp;
	88
	89	cmp = f(left, right);
	90	if (cmp)
	91	break;
	92	}
	93
	94	return cmp;
	95	}
	96
	97	void hist_entry__free(struct hist_entry *he)
	98	{
	99	free(he);
	100	}
	101
	102	/*
	103	* collapse the histogram
	104	*/
	105
b9bf0892	106	static void collapse__insert_entry(struct rb_root root, struct hist_entry he)
3d1d07ec	107	{
b9bf0892	108	struct rb_node **p = &root->rb_node;
3d1d07ec JK	109	struct rb_node *parent = NULL;
	110	struct hist_entry *iter;
	111	int64_t cmp;
	112
	113	while (*p != NULL) {
	114	parent = *p;
	115	iter = rb_entry(parent, struct hist_entry, rb_node);
	116
	117	cmp = hist_entry__collapse(iter, he);
	118
	119	if (!cmp) {
	120	iter->count += he->count;
	121	hist_entry__free(he);
	122	return;
	123	}
	124
	125	if (cmp < 0)
	126	p = &(*p)->rb_left;
	127	else
	128	p = &(*p)->rb_right;
	129	}
	130
	131	rb_link_node(&he->rb_node, parent, p);
b9bf0892	132	rb_insert_color(&he->rb_node, root);
3d1d07ec JK	133	}
3d1d07ec JK	134
eefc465c	135	void perf_session__collapse_resort(struct rb_root *hists)
3d1d07ec	136	{
b9bf0892	137	struct rb_root tmp;
3d1d07ec JK	138	struct rb_node *next;
	139	struct hist_entry *n;
	140
	141	if (!sort__need_collapse)
	142	return;
	143
b9bf0892	144	tmp = RB_ROOT;
eefc465c	145	next = rb_first(hists);
b9bf0892	146
3d1d07ec JK	147	while (next) {
	148	n = rb_entry(next, struct hist_entry, rb_node);
	149	next = rb_next(&n->rb_node);
	150
eefc465c	151	rb_erase(&n->rb_node, hists);
b9bf0892	152	collapse__insert_entry(&tmp, n);
3d1d07ec	153	}
b9bf0892	154
eefc465c	155	*hists = tmp;
3d1d07ec JK	156	}
	157
	158	/*
	159	* reverse the map, sort on count.
	160	*/
	161
d599db3f	162	static void perf_session__insert_output_hist_entry(struct rb_root *root,
4e4f06e4 ACM	163	struct hist_entry *he,
4e4f06e4 ACM	164	u64 min_callchain_hits)
3d1d07ec	165	{
b9bf0892	166	struct rb_node **p = &root->rb_node;
3d1d07ec JK	167	struct rb_node *parent = NULL;
	168	struct hist_entry *iter;
	169
d599db3f	170	if (symbol_conf.use_callchain)
3d1d07ec JK	171	callchain_param.sort(&he->sorted_chain, &he->callchain,
	172	min_callchain_hits, &callchain_param);
	173
	174	while (*p != NULL) {
	175	parent = *p;
	176	iter = rb_entry(parent, struct hist_entry, rb_node);
	177
	178	if (he->count > iter->count)
	179	p = &(*p)->rb_left;
	180	else
	181	p = &(*p)->rb_right;
	182	}
	183
	184	rb_link_node(&he->rb_node, parent, p);
b9bf0892	185	rb_insert_color(&he->rb_node, root);
3d1d07ec JK	186	}
3d1d07ec JK	187
eefc465c	188	void perf_session__output_resort(struct rb_root *hists, u64 total_samples)
3d1d07ec	189	{
b9bf0892	190	struct rb_root tmp;
3d1d07ec JK	191	struct rb_node *next;
3d1d07ec JK	192	struct hist_entry *n;
3d1d07ec JK	193	u64 min_callchain_hits;
	194
	195	min_callchain_hits =
	196	total_samples * (callchain_param.min_percent / 100);
	197
b9bf0892	198	tmp = RB_ROOT;
eefc465c	199	next = rb_first(hists);
3d1d07ec JK	200
	201	while (next) {
	202	n = rb_entry(next, struct hist_entry, rb_node);
	203	next = rb_next(&n->rb_node);
	204
eefc465c	205	rb_erase(&n->rb_node, hists);
d599db3f	206	perf_session__insert_output_hist_entry(&tmp, n,
4e4f06e4	207	min_callchain_hits);
3d1d07ec	208	}
b9bf0892	209
eefc465c	210	*hists = tmp;
3d1d07ec	211	}
4ecf84d0 ACM	212
	213	static size_t callchain__fprintf_left_margin(FILE *fp, int left_margin)
	214	{
	215	int i;
	216	int ret = fprintf(fp, " ");
	217
	218	for (i = 0; i < left_margin; i++)
	219	ret += fprintf(fp, " ");
	220
	221	return ret;
	222	}
	223
	224	static size_t ipchain__fprintf_graph_line(FILE *fp, int depth, int depth_mask,
	225	int left_margin)
	226	{
	227	int i;
	228	size_t ret = callchain__fprintf_left_margin(fp, left_margin);
	229
	230	for (i = 0; i < depth; i++)
	231	if (depth_mask & (1 << i))
	232	ret += fprintf(fp, "\| ");
	233	else
	234	ret += fprintf(fp, " ");
	235
	236	ret += fprintf(fp, "\n");
	237
	238	return ret;
	239	}
	240
	241	static size_t ipchain__fprintf_graph(FILE fp, struct callchain_list chain,
	242	int depth, int depth_mask, int count,
	243	u64 total_samples, int hits,
	244	int left_margin)
	245	{
	246	int i;
	247	size_t ret = 0;
	248
	249	ret += callchain__fprintf_left_margin(fp, left_margin);
	250	for (i = 0; i < depth; i++) {
	251	if (depth_mask & (1 << i))
	252	ret += fprintf(fp, "\|");
	253	else
	254	ret += fprintf(fp, " ");
	255	if (!count && i == depth - 1) {
	256	double percent;
	257
	258	percent = hits * 100.0 / total_samples;
	259	ret += percent_color_fprintf(fp, "--%2.2f%%-- ", percent);
	260	} else
	261	ret += fprintf(fp, "%s", " ");
	262	}
b3c9ac08 ACM	263	if (chain->ms.sym)
b3c9ac08 ACM	264	ret += fprintf(fp, "%s\n", chain->ms.sym->name);
4ecf84d0 ACM	265	else
	266	ret += fprintf(fp, "%p\n", (void *)(long)chain->ip);
	267
	268	return ret;
	269	}
	270
	271	static struct symbol *rem_sq_bracket;
	272	static struct callchain_list rem_hits;
	273
	274	static void init_rem_hits(void)
	275	{
	276	rem_sq_bracket = malloc(sizeof(*rem_sq_bracket) + 6);
	277	if (!rem_sq_bracket) {
	278	fprintf(stderr, "Not enough memory to display remaining hits\n");
	279	return;
	280	}
	281
	282	strcpy(rem_sq_bracket->name, "[...]");
b3c9ac08	283	rem_hits.ms.sym = rem_sq_bracket;
4ecf84d0 ACM	284	}
	285
	286	static size_t __callchain__fprintf_graph(FILE fp, struct callchain_node self,
	287	u64 total_samples, int depth,
	288	int depth_mask, int left_margin)
	289	{
	290	struct rb_node node, next;
	291	struct callchain_node *child;
	292	struct callchain_list *chain;
	293	int new_depth_mask = depth_mask;
	294	u64 new_total;
	295	u64 remaining;
	296	size_t ret = 0;
	297	int i;
	298
	299	if (callchain_param.mode == CHAIN_GRAPH_REL)
	300	new_total = self->children_hit;
	301	else
	302	new_total = total_samples;
	303
	304	remaining = new_total;
	305
	306	node = rb_first(&self->rb_root);
	307	while (node) {
	308	u64 cumul;
	309
	310	child = rb_entry(node, struct callchain_node, rb_node);
	311	cumul = cumul_hits(child);
	312	remaining -= cumul;
	313
	314	/*
	315	* The depth mask manages the output of pipes that show
	316	* the depth. We don't want to keep the pipes of the current
	317	* level for the last child of this depth.
	318	* Except if we have remaining filtered hits. They will
	319	* supersede the last child
	320	*/
	321	next = rb_next(node);
	322	if (!next && (callchain_param.mode != CHAIN_GRAPH_REL \|\| !remaining))
	323	new_depth_mask &= ~(1 << (depth - 1));
	324
	325	/*
3ad2f3fb	326	* But we keep the older depth mask for the line separator
4ecf84d0 ACM	327	* to keep the level link until we reach the last child
	328	*/
	329	ret += ipchain__fprintf_graph_line(fp, depth, depth_mask,
	330	left_margin);
	331	i = 0;
	332	list_for_each_entry(chain, &child->val, list) {
4ecf84d0 ACM	333	ret += ipchain__fprintf_graph(fp, chain, depth,
	334	new_depth_mask, i++,
	335	new_total,
	336	cumul,
	337	left_margin);
	338	}
	339	ret += __callchain__fprintf_graph(fp, child, new_total,
	340	depth + 1,
	341	new_depth_mask \| (1 << depth),
	342	left_margin);
	343	node = next;
	344	}
	345
	346	if (callchain_param.mode == CHAIN_GRAPH_REL &&
	347	remaining && remaining != new_total) {
	348
	349	if (!rem_sq_bracket)
	350	return ret;
	351
	352	new_depth_mask &= ~(1 << (depth - 1));
	353
	354	ret += ipchain__fprintf_graph(fp, &rem_hits, depth,
	355	new_depth_mask, 0, new_total,
	356	remaining, left_margin);
	357	}
	358
	359	return ret;
	360	}
	361
	362	static size_t callchain__fprintf_graph(FILE fp, struct callchain_node self,
	363	u64 total_samples, int left_margin)
	364	{
	365	struct callchain_list *chain;
	366	bool printed = false;
	367	int i = 0;
	368	int ret = 0;
	369
	370	list_for_each_entry(chain, &self->val, list) {
4ecf84d0 ACM	371	if (!i++ && sort__first_dimension == SORT_SYM)
	372	continue;
	373
	374	if (!printed) {
	375	ret += callchain__fprintf_left_margin(fp, left_margin);
	376	ret += fprintf(fp, "\|\n");
	377	ret += callchain__fprintf_left_margin(fp, left_margin);
	378	ret += fprintf(fp, "---");
	379
	380	left_margin += 3;
	381	printed = true;
	382	} else
	383	ret += callchain__fprintf_left_margin(fp, left_margin);
	384
b3c9ac08 ACM	385	if (chain->ms.sym)
b3c9ac08 ACM	386	ret += fprintf(fp, " %s\n", chain->ms.sym->name);
4ecf84d0 ACM	387	else
	388	ret += fprintf(fp, " %p\n", (void *)(long)chain->ip);
	389	}
	390
	391	ret += __callchain__fprintf_graph(fp, self, total_samples, 1, 1, left_margin);
	392
	393	return ret;
	394	}
	395
	396	static size_t callchain__fprintf_flat(FILE fp, struct callchain_node self,
	397	u64 total_samples)
	398	{
	399	struct callchain_list *chain;
	400	size_t ret = 0;
	401
	402	if (!self)
	403	return 0;
	404
	405	ret += callchain__fprintf_flat(fp, self->parent, total_samples);
	406
	407
	408	list_for_each_entry(chain, &self->val, list) {
	409	if (chain->ip >= PERF_CONTEXT_MAX)
	410	continue;
b3c9ac08 ACM	411	if (chain->ms.sym)
b3c9ac08 ACM	412	ret += fprintf(fp, " %s\n", chain->ms.sym->name);
4ecf84d0 ACM	413	else
	414	ret += fprintf(fp, " %p\n",
	415	(void *)(long)chain->ip);
	416	}
	417
	418	return ret;
	419	}
	420
	421	static size_t hist_entry_callchain__fprintf(FILE fp, struct hist_entry self,
	422	u64 total_samples, int left_margin)
	423	{
	424	struct rb_node *rb_node;
	425	struct callchain_node *chain;
	426	size_t ret = 0;
	427
	428	rb_node = rb_first(&self->sorted_chain);
	429	while (rb_node) {
	430	double percent;
	431
	432	chain = rb_entry(rb_node, struct callchain_node, rb_node);
	433	percent = chain->hit * 100.0 / total_samples;
	434	switch (callchain_param.mode) {
	435	case CHAIN_FLAT:
	436	ret += percent_color_fprintf(fp, " %6.2f%%\n",
	437	percent);
	438	ret += callchain__fprintf_flat(fp, chain, total_samples);
	439	break;
	440	case CHAIN_GRAPH_ABS: /* Falldown */
	441	case CHAIN_GRAPH_REL:
	442	ret += callchain__fprintf_graph(fp, chain, total_samples,
	443	left_margin);
	444	case CHAIN_NONE:
	445	default:
	446	break;
	447	}
	448	ret += fprintf(fp, "\n");
	449	rb_node = rb_next(rb_node);
	450	}
	451
	452	return ret;
	453	}
	454
dd2ee78d ACM	455	size_t hist_entry__fprintf(struct hist_entry *self,
	456	struct perf_session *pair_session,
	457	bool show_displacement,
	458	long displacement, FILE *fp,
	459	u64 session_total)
4ecf84d0 ACM	460	{
4ecf84d0 ACM	461	struct sort_entry *se;
c351c281 ACM	462	u64 count, total;
c351c281 ACM	463	const char *sep = symbol_conf.field_sep;
4ecf84d0 ACM	464	size_t ret;
	465
	466	if (symbol_conf.exclude_other && !self->parent)
	467	return 0;
	468
c351c281 ACM	469	if (pair_session) {
	470	count = self->pair ? self->pair->count : 0;
	471	total = pair_session->events_stats.total;
	472	} else {
	473	count = self->count;
eefc465c	474	total = session_total;
c351c281 ACM	475	}
	476
	477	if (total)
	478	ret = percent_color_fprintf(fp, sep ? "%.2f" : " %6.2f%%",
	479	(count * 100.0) / total);
4ecf84d0	480	else
c351c281	481	ret = fprintf(fp, sep ? "%lld" : "%12lld ", count);
4ecf84d0 ACM	482
4ecf84d0 ACM	483	if (symbol_conf.show_nr_samples) {
c351c281	484	if (sep)
dd2ee78d	485	ret += fprintf(fp, "%c%lld", *sep, count);
4ecf84d0	486	else
dd2ee78d	487	ret += fprintf(fp, "%11lld", count);
c351c281 ACM	488	}
	489
	490	if (pair_session) {
	491	char bf[32];
	492	double old_percent = 0, new_percent = 0, diff;
	493
	494	if (total > 0)
9b33827d	495	old_percent = (count * 100.0) / total;
eefc465c EM	496	if (session_total > 0)
eefc465c EM	497	new_percent = (self->count * 100.0) / session_total;
c351c281	498
9b33827d	499	diff = new_percent - old_percent;
c351c281	500
9b33827d	501	if (fabs(diff) >= 0.01)
c351c281 ACM	502	snprintf(bf, sizeof(bf), "%+4.2F%%", diff);
	503	else
	504	snprintf(bf, sizeof(bf), " ");
	505
	506	if (sep)
	507	ret += fprintf(fp, "%c%s", *sep, bf);
	508	else
	509	ret += fprintf(fp, "%11.11s", bf);
	510
	511	if (show_displacement) {
	512	if (displacement)
	513	snprintf(bf, sizeof(bf), "%+4ld", displacement);
	514	else
	515	snprintf(bf, sizeof(bf), " ");
	516
	517	if (sep)
dd2ee78d	518	ret += fprintf(fp, "%c%s", *sep, bf);
c351c281	519	else
dd2ee78d	520	ret += fprintf(fp, "%6.6s", bf);
c351c281	521	}
4ecf84d0 ACM	522	}
	523
	524	list_for_each_entry(se, &hist_entry__sort_list, list) {
	525	if (se->elide)
	526	continue;
	527
dd2ee78d	528	ret += fprintf(fp, "%s", sep ?: " ");
4ecf84d0 ACM	529	ret += se->print(fp, self, se->width ? *se->width : 0);
	530	}
	531
3997d377 ACM	532	return ret + fprintf(fp, "\n");
3997d377 ACM	533	}
4ecf84d0	534
3997d377 ACM	535	static size_t hist_entry__fprintf_callchain(struct hist_entry self, FILE fp,
	536	u64 session_total)
	537	{
	538	int left_margin = 0;
4ecf84d0	539
3997d377 ACM	540	if (sort__first_dimension == SORT_COMM) {
	541	struct sort_entry *se = list_first_entry(&hist_entry__sort_list,
	542	typeof(*se), list);
	543	left_margin = se->width ? *se->width : 0;
	544	left_margin -= thread__comm_len(self->thread);
4ecf84d0 ACM	545	}
4ecf84d0 ACM	546
3997d377 ACM	547	return hist_entry_callchain__fprintf(fp, self, session_total,
3997d377 ACM	548	left_margin);
4ecf84d0 ACM	549	}
4ecf84d0 ACM	550
eefc465c	551	size_t perf_session__fprintf_hists(struct rb_root *hists,
c351c281	552	struct perf_session *pair,
eefc465c EM	553	bool show_displacement, FILE *fp,
eefc465c EM	554	u64 session_total)
4ecf84d0	555	{
4ecf84d0 ACM	556	struct sort_entry *se;
	557	struct rb_node *nd;
	558	size_t ret = 0;
c351c281 ACM	559	unsigned long position = 1;
c351c281 ACM	560	long displacement = 0;
4ecf84d0	561	unsigned int width;
c351c281	562	const char *sep = symbol_conf.field_sep;
4ecf84d0 ACM	563	char *col_width = symbol_conf.col_width_list_str;
	564
	565	init_rem_hits();
	566
c351c281 ACM	567	fprintf(fp, "# %s", pair ? "Baseline" : "Overhead");
c351c281 ACM	568
4ecf84d0	569	if (symbol_conf.show_nr_samples) {
c351c281 ACM	570	if (sep)
c351c281 ACM	571	fprintf(fp, "%cSamples", *sep);
4ecf84d0 ACM	572	else
	573	fputs(" Samples ", fp);
	574	}
c351c281 ACM	575
	576	if (pair) {
	577	if (sep)
	578	ret += fprintf(fp, "%cDelta", *sep);
	579	else
	580	ret += fprintf(fp, " Delta ");
	581
	582	if (show_displacement) {
	583	if (sep)
	584	ret += fprintf(fp, "%cDisplacement", *sep);
	585	else
	586	ret += fprintf(fp, " Displ");
	587	}
	588	}
	589
4ecf84d0 ACM	590	list_for_each_entry(se, &hist_entry__sort_list, list) {
	591	if (se->elide)
	592	continue;
c351c281 ACM	593	if (sep) {
c351c281 ACM	594	fprintf(fp, "%c%s", *sep, se->header);
4ecf84d0 ACM	595	continue;
	596	}
	597	width = strlen(se->header);
	598	if (se->width) {
	599	if (symbol_conf.col_width_list_str) {
	600	if (col_width) {
	601	*se->width = atoi(col_width);
	602	col_width = strchr(col_width, ',');
	603	if (col_width)
	604	++col_width;
	605	}
	606	}
	607	width = se->width = max(se->width, width);
	608	}
	609	fprintf(fp, " %*s", width, se->header);
	610	}
	611	fprintf(fp, "\n");
	612
c351c281	613	if (sep)
4ecf84d0 ACM	614	goto print_entries;
	615
	616	fprintf(fp, "# ........");
	617	if (symbol_conf.show_nr_samples)
	618	fprintf(fp, " ..........");
c351c281 ACM	619	if (pair) {
	620	fprintf(fp, " ..........");
	621	if (show_displacement)
	622	fprintf(fp, " .....");
	623	}
4ecf84d0 ACM	624	list_for_each_entry(se, &hist_entry__sort_list, list) {
	625	unsigned int i;
	626
	627	if (se->elide)
	628	continue;
	629
	630	fprintf(fp, " ");
	631	if (se->width)
	632	width = *se->width;
	633	else
	634	width = strlen(se->header);
	635	for (i = 0; i < width; i++)
	636	fprintf(fp, ".");
	637	}
4ecf84d0	638
c351c281	639	fprintf(fp, "\n#\n");
4ecf84d0 ACM	640
4ecf84d0 ACM	641	print_entries:
eefc465c	642	for (nd = rb_first(hists); nd; nd = rb_next(nd)) {
c351c281 ACM	643	struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
	644
	645	if (show_displacement) {
	646	if (h->pair != NULL)
	647	displacement = ((long)h->pair->position -
	648	(long)position);
	649	else
	650	displacement = 0;
	651	++position;
	652	}
eefc465c EM	653	ret += hist_entry__fprintf(h, pair, show_displacement,
eefc465c EM	654	displacement, fp, session_total);
3997d377 ACM	655
	656	if (symbol_conf.use_callchain)
	657	ret += hist_entry__fprintf_callchain(h, fp, session_total);
	658
59fd5306	659	if (h->ms.map == NULL && verbose > 1) {
65f2ed2b	660	__map_groups__fprintf_maps(&h->thread->mg,
c6e718ff	661	MAP__FUNCTION, verbose, fp);
65f2ed2b ACM	662	fprintf(fp, "%.10s end\n", graph_dotted_line);
65f2ed2b ACM	663	}
4ecf84d0 ACM	664	}
4ecf84d0 ACM	665
4ecf84d0 ACM	666	free(rem_sq_bracket);
	667
	668	return ret;
	669	}