[GitHub/mt8127/android_kernel_alcatel_ttab.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) + (symbol_conf.use_callchain ?
				    sizeof(struct callchain_node) : 0));
	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);
}

u64 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;
	u64 nr_hists = 0;

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

	*hists = tmp;
	return nr_hists;
}

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

int hist_entry__snprintf(struct hist_entry *self,
			   char *s, size_t size,
			   struct perf_session *pair_session,
			   bool show_displacement,
			   long displacement, bool color,
			   u64 session_total)
{
	struct sort_entry *se;
	u64 count, total;
	const char *sep = symbol_conf.field_sep;
	int 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) {
		if (color)
			ret = percent_color_snprintf(s, size,
						     sep ? "%.2f" : "   %6.2f%%",
						     (count * 100.0) / total);
		else
			ret = snprintf(s, size, sep ? "%.2f" : "   %6.2f%%",
				       (count * 100.0) / total);
	} else
		ret = snprintf(s, size, sep ? "%lld" : "%12lld ", count);

	if (symbol_conf.show_nr_samples) {
		if (sep)
			ret += snprintf(s + ret, size - ret, "%c%lld", *sep, count);
		else
			ret += snprintf(s + ret, size - ret, "%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 += snprintf(s + ret, size - ret, "%c%s", *sep, bf);
		else
			ret += snprintf(s + ret, size - ret, "%11.11s", bf);

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

			if (sep)
				ret += snprintf(s + ret, size - ret, "%c%s", *sep, bf);
			else
				ret += snprintf(s + ret, size - ret, "%6.6s", bf);
		}
	}

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

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

	return ret;
}

int hist_entry__fprintf(struct hist_entry *self,
			struct perf_session *pair_session,
			bool show_displacement,
			long displacement, FILE *fp,
			u64 session_total)
{
	char bf[512];
	hist_entry__snprintf(self, bf, sizeof(bf), pair_session,
			     show_displacement, displacement,
			     true, session_total);
	return fprintf(fp, "%s\n", bf);
}

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