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