[linux-2.6-block.git] / tools / perf / util / hist.c

#include "annotate.h"
#include "util.h"
#include "build-id.h"
#include "hist.h"
#include "session.h"
#include "sort.h"
#include <math.h>

static bool hists__filter_entry_by_dso(struct hists *hists,
				       struct hist_entry *he);
static bool hists__filter_entry_by_thread(struct hists *hists,
					  struct hist_entry *he);
static bool hists__filter_entry_by_symbol(struct hists *hists,
					  struct hist_entry *he);

enum hist_filter {
	HIST_FILTER__DSO,
	HIST_FILTER__THREAD,
	HIST_FILTER__PARENT,
	HIST_FILTER__SYMBOL,
};

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

u16 hists__col_len(struct hists *hists, enum hist_column col)
{
	return hists->col_len[col];
}

void hists__set_col_len(struct hists *hists, enum hist_column col, u16 len)
{
	hists->col_len[col] = len;
}

bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len)
{
	if (len > hists__col_len(hists, col)) {
		hists__set_col_len(hists, col, len);
		return true;
	}
	return false;
}

void hists__reset_col_len(struct hists *hists)
{
	enum hist_column col;

	for (col = 0; col < HISTC_NR_COLS; ++col)
		hists__set_col_len(hists, col, 0);
}

static void hists__set_unres_dso_col_len(struct hists *hists, int dso)
{
	const unsigned int unresolved_col_width = BITS_PER_LONG / 4;

	if (hists__col_len(hists, dso) < unresolved_col_width &&
	    !symbol_conf.col_width_list_str && !symbol_conf.field_sep &&
	    !symbol_conf.dso_list)
		hists__set_col_len(hists, dso, unresolved_col_width);
}

void hists__calc_col_len(struct hists *hists, struct hist_entry *h)
{
	const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
	u16 len;

	if (h->ms.sym)
		hists__new_col_len(hists, HISTC_SYMBOL, h->ms.sym->namelen + 4);
	else
		hists__set_unres_dso_col_len(hists, HISTC_DSO);

	len = thread__comm_len(h->thread);
	if (hists__new_col_len(hists, HISTC_COMM, len))
		hists__set_col_len(hists, HISTC_THREAD, len + 6);

	if (h->ms.map) {
		len = dso__name_len(h->ms.map->dso);
		hists__new_col_len(hists, HISTC_DSO, len);
	}

	if (h->branch_info) {
		int symlen;
		/*
		 * +4 accounts for '[x] ' priv level info
		 * +2 account of 0x prefix on raw addresses
		 */
		if (h->branch_info->from.sym) {
			symlen = (int)h->branch_info->from.sym->namelen + 4;
			hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);

			symlen = dso__name_len(h->branch_info->from.map->dso);
			hists__new_col_len(hists, HISTC_DSO_FROM, symlen);
		} else {
			symlen = unresolved_col_width + 4 + 2;
			hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
			hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM);
		}

		if (h->branch_info->to.sym) {
			symlen = (int)h->branch_info->to.sym->namelen + 4;
			hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);

			symlen = dso__name_len(h->branch_info->to.map->dso);
			hists__new_col_len(hists, HISTC_DSO_TO, symlen);
		} else {
			symlen = unresolved_col_width + 4 + 2;
			hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
			hists__set_unres_dso_col_len(hists, HISTC_DSO_TO);
		}
	}
}

void hists__output_recalc_col_len(struct hists *hists, int max_rows)
{
	struct rb_node *next = rb_first(&hists->entries);
	struct hist_entry *n;
	int row = 0;

	hists__reset_col_len(hists);

	while (next && row++ < max_rows) {
		n = rb_entry(next, struct hist_entry, rb_node);
		if (!n->filtered)
			hists__calc_col_len(hists, n);
		next = rb_next(&n->rb_node);
	}
}

static void hist_entry__add_cpumode_period(struct hist_entry *he,
					   unsigned int cpumode, u64 period)
{
	switch (cpumode) {
	case PERF_RECORD_MISC_KERNEL:
		he->period_sys += period;
		break;
	case PERF_RECORD_MISC_USER:
		he->period_us += period;
		break;
	case PERF_RECORD_MISC_GUEST_KERNEL:
		he->period_guest_sys += period;
		break;
	case PERF_RECORD_MISC_GUEST_USER:
		he->period_guest_us += period;
		break;
	default:
		break;
	}
}

static void hist_entry__decay(struct hist_entry *he)
{
	he->period = (he->period * 7) / 8;
	he->nr_events = (he->nr_events * 7) / 8;
}

static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
{
	u64 prev_period = he->period;

	if (prev_period == 0)
		return true;

	hist_entry__decay(he);

	if (!he->filtered)
		hists->stats.total_period -= prev_period - he->period;

	return he->period == 0;
}

static void __hists__decay_entries(struct hists *hists, bool zap_user,
				   bool zap_kernel, bool threaded)
{
	struct rb_node *next = rb_first(&hists->entries);
	struct hist_entry *n;

	while (next) {
		n = rb_entry(next, struct hist_entry, rb_node);
		next = rb_next(&n->rb_node);
		/*
		 * We may be annotating this, for instance, so keep it here in
		 * case some it gets new samples, we'll eventually free it when
		 * the user stops browsing and it agains gets fully decayed.
		 */
		if (((zap_user && n->level == '.') ||
		     (zap_kernel && n->level != '.') ||
		     hists__decay_entry(hists, n)) &&
		    !n->used) {
			rb_erase(&n->rb_node, &hists->entries);

			if (sort__need_collapse || threaded)
				rb_erase(&n->rb_node_in, &hists->entries_collapsed);

			hist_entry__free(n);
			--hists->nr_entries;
		}
	}
}

void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
{
	return __hists__decay_entries(hists, zap_user, zap_kernel, false);
}

void hists__decay_entries_threaded(struct hists *hists,
				   bool zap_user, bool zap_kernel)
{
	return __hists__decay_entries(hists, zap_user, zap_kernel, true);
}

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

static struct hist_entry *hist_entry__new(struct hist_entry *template)
{
	size_t callchain_size = symbol_conf.use_callchain ? sizeof(struct callchain_root) : 0;
	struct hist_entry *he = malloc(sizeof(*he) + callchain_size);

	if (he != NULL) {
		*he = *template;
		he->nr_events = 1;
		if (he->ms.map)
			he->ms.map->referenced = true;
		if (symbol_conf.use_callchain)
			callchain_init(he->callchain);
	}

	return he;
}

static void hists__inc_nr_entries(struct hists *hists, struct hist_entry *h)
{
	if (!h->filtered) {
		hists__calc_col_len(hists, h);
		++hists->nr_entries;
		hists->stats.total_period += h->period;
	}
}

static u8 symbol__parent_filter(const struct symbol *parent)
{
	if (symbol_conf.exclude_other && parent == NULL)
		return 1 << HIST_FILTER__PARENT;
	return 0;
}

static struct hist_entry *add_hist_entry(struct hists *hists,
				      struct hist_entry *entry,
				      struct addr_location *al,
				      u64 period)
{
	struct rb_node **p;
	struct rb_node *parent = NULL;
	struct hist_entry *he;
	int cmp;

	pthread_mutex_lock(&hists->lock);

	p = &hists->entries_in->rb_node;

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

		cmp = hist_entry__cmp(entry, he);

		if (!cmp) {
			he->period += period;
			++he->nr_events;

			/* If the map of an existing hist_entry has
			 * become out-of-date due to an exec() or
			 * similar, update it.  Otherwise we will
			 * mis-adjust symbol addresses when computing
			 * the history counter to increment.
			 */
			if (he->ms.map != entry->ms.map) {
				he->ms.map = entry->ms.map;
				if (he->ms.map)
					he->ms.map->referenced = true;
			}
			goto out;
		}

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

	he = hist_entry__new(entry);
	if (!he)
		goto out_unlock;

	rb_link_node(&he->rb_node_in, parent, p);
	rb_insert_color(&he->rb_node_in, hists->entries_in);
out:
	hist_entry__add_cpumode_period(he, al->cpumode, period);
out_unlock:
	pthread_mutex_unlock(&hists->lock);
	return he;
}

struct hist_entry *__hists__add_branch_entry(struct hists *self,
					     struct addr_location *al,
					     struct symbol *sym_parent,
					     struct branch_info *bi,
					     u64 period)
{
	struct hist_entry entry = {
		.thread	= al->thread,
		.ms = {
			.map	= bi->to.map,
			.sym	= bi->to.sym,
		},
		.cpu	= al->cpu,
		.ip	= bi->to.addr,
		.level	= al->level,
		.period	= period,
		.parent = sym_parent,
		.filtered = symbol__parent_filter(sym_parent),
		.branch_info = bi,
	};

	return add_hist_entry(self, &entry, al, period);
}

struct hist_entry *__hists__add_entry(struct hists *self,
				      struct addr_location *al,
				      struct symbol *sym_parent, u64 period)
{
	struct hist_entry entry = {
		.thread	= al->thread,
		.ms = {
			.map	= al->map,
			.sym	= al->sym,
		},
		.cpu	= al->cpu,
		.ip	= al->addr,
		.level	= al->level,
		.period	= period,
		.parent = sym_parent,
		.filtered = symbol__parent_filter(sym_parent),
	};

	return add_hist_entry(self, &entry, al, period);
}

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->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->se_collapse ?: se->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 bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
					 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_in);

		cmp = hist_entry__collapse(iter, he);

		if (!cmp) {
			iter->period		+= he->period;
			iter->period_sys	+= he->period_sys;
			iter->period_us		+= he->period_us;
			iter->period_guest_sys	+= he->period_guest_sys;
			iter->period_guest_us	+= he->period_guest_us;
			iter->nr_events		+= he->nr_events;

			if (symbol_conf.use_callchain) {
				callchain_cursor_reset(&callchain_cursor);
				callchain_merge(&callchain_cursor,
						iter->callchain,
						he->callchain);
			}
			hist_entry__free(he);
			return false;
		}

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

	rb_link_node(&he->rb_node_in, parent, p);
	rb_insert_color(&he->rb_node_in, root);
	return true;
}

static struct rb_root *hists__get_rotate_entries_in(struct hists *hists)
{
	struct rb_root *root;

	pthread_mutex_lock(&hists->lock);

	root = hists->entries_in;
	if (++hists->entries_in > &hists->entries_in_array[1])
		hists->entries_in = &hists->entries_in_array[0];

	pthread_mutex_unlock(&hists->lock);

	return root;
}

static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
{
	hists__filter_entry_by_dso(hists, he);
	hists__filter_entry_by_thread(hists, he);
	hists__filter_entry_by_symbol(hists, he);
}

static void __hists__collapse_resort(struct hists *hists, bool threaded)
{
	struct rb_root *root;
	struct rb_node *next;
	struct hist_entry *n;

	if (!sort__need_collapse && !threaded)
		return;

	root = hists__get_rotate_entries_in(hists);
	next = rb_first(root);

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

		rb_erase(&n->rb_node_in, root);
		if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) {
			/*
			 * If it wasn't combined with one of the entries already
			 * collapsed, we need to apply the filters that may have
			 * been set by, say, the hist_browser.
			 */
			hists__apply_filters(hists, n);
		}
	}
}

void hists__collapse_resort(struct hists *hists)
{
	return __hists__collapse_resort(hists, false);
}

void hists__collapse_resort_threaded(struct hists *hists)
{
	return __hists__collapse_resort(hists, true);
}

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

static void __hists__insert_output_entry(struct rb_root *entries,
					 struct hist_entry *he,
					 u64 min_callchain_hits)
{
	struct rb_node **p = &entries->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->period > iter->period)
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

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

static void __hists__output_resort(struct hists *hists, bool threaded)
{
	struct rb_root *root;
	struct rb_node *next;
	struct hist_entry *n;
	u64 min_callchain_hits;

	min_callchain_hits = hists->stats.total_period * (callchain_param.min_percent / 100);

	if (sort__need_collapse || threaded)
		root = &hists->entries_collapsed;
	else
		root = hists->entries_in;

	next = rb_first(root);
	hists->entries = RB_ROOT;

	hists->nr_entries = 0;
	hists->stats.total_period = 0;
	hists__reset_col_len(hists);

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

		__hists__insert_output_entry(&hists->entries, n, min_callchain_hits);
		hists__inc_nr_entries(hists, n);
	}
}

void hists__output_resort(struct hists *hists)
{
	return __hists__output_resort(hists, false);
}

void hists__output_resort_threaded(struct hists *hists)
{
	return __hists__output_resort(hists, true);
}

static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
				       enum hist_filter filter)
{
	h->filtered &= ~(1 << filter);
	if (h->filtered)
		return;

	++hists->nr_entries;
	if (h->ms.unfolded)
		hists->nr_entries += h->nr_rows;
	h->row_offset = 0;
	hists->stats.total_period += h->period;
	hists->stats.nr_events[PERF_RECORD_SAMPLE] += h->nr_events;

	hists__calc_col_len(hists, h);
}


static bool hists__filter_entry_by_dso(struct hists *hists,
				       struct hist_entry *he)
{
	if (hists->dso_filter != NULL &&
	    (he->ms.map == NULL || he->ms.map->dso != hists->dso_filter)) {
		he->filtered |= (1 << HIST_FILTER__DSO);
		return true;
	}

	return false;
}

void hists__filter_by_dso(struct hists *hists)
{
	struct rb_node *nd;

	hists->nr_entries = hists->stats.total_period = 0;
	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
	hists__reset_col_len(hists);

	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);

		if (symbol_conf.exclude_other && !h->parent)
			continue;

		if (hists__filter_entry_by_dso(hists, h))
			continue;

		hists__remove_entry_filter(hists, h, HIST_FILTER__DSO);
	}
}

static bool hists__filter_entry_by_thread(struct hists *hists,
					  struct hist_entry *he)
{
	if (hists->thread_filter != NULL &&
	    he->thread != hists->thread_filter) {
		he->filtered |= (1 << HIST_FILTER__THREAD);
		return true;
	}

	return false;
}

void hists__filter_by_thread(struct hists *hists)
{
	struct rb_node *nd;

	hists->nr_entries = hists->stats.total_period = 0;
	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
	hists__reset_col_len(hists);

	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);

		if (hists__filter_entry_by_thread(hists, h))
			continue;

		hists__remove_entry_filter(hists, h, HIST_FILTER__THREAD);
	}
}

static bool hists__filter_entry_by_symbol(struct hists *hists,
					  struct hist_entry *he)
{
	if (hists->symbol_filter_str != NULL &&
	    (!he->ms.sym || strstr(he->ms.sym->name,
				   hists->symbol_filter_str) == NULL)) {
		he->filtered |= (1 << HIST_FILTER__SYMBOL);
		return true;
	}

	return false;
}

void hists__filter_by_symbol(struct hists *hists)
{
	struct rb_node *nd;

	hists->nr_entries = hists->stats.total_period = 0;
	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
	hists__reset_col_len(hists);

	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);

		if (hists__filter_entry_by_symbol(hists, h))
			continue;

		hists__remove_entry_filter(hists, h, HIST_FILTER__SYMBOL);
	}
}

int hist_entry__inc_addr_samples(struct hist_entry *he, int evidx, u64 ip)
{
	return symbol__inc_addr_samples(he->ms.sym, he->ms.map, evidx, ip);
}

int hist_entry__annotate(struct hist_entry *he, size_t privsize)
{
	return symbol__annotate(he->ms.sym, he->ms.map, privsize);
}

void hists__inc_nr_events(struct hists *hists, u32 type)
{
	++hists->stats.nr_events[0];
	++hists->stats.nr_events[type];
}
Commit	Line	Data
78f7defe	1	#include "annotate.h"
8a0ecfb8	2	#include "util.h"
598357eb	3	#include "build-id.h"
3d1d07ec	4	#include "hist.h"
4e4f06e4 ACM	5	#include "session.h"
4e4f06e4 ACM	6	#include "sort.h"
9b33827d	7	#include <math.h>
3d1d07ec	8
90cf1fb5 ACM	9	static bool hists__filter_entry_by_dso(struct hists *hists,
	10	struct hist_entry *he);
	11	static bool hists__filter_entry_by_thread(struct hists *hists,
	12	struct hist_entry *he);
e94d53eb NK	13	static bool hists__filter_entry_by_symbol(struct hists *hists,
e94d53eb NK	14	struct hist_entry *he);
90cf1fb5	15
7a007ca9 ACM	16	enum hist_filter {
	17	HIST_FILTER__DSO,
	18	HIST_FILTER__THREAD,
	19	HIST_FILTER__PARENT,
e94d53eb	20	HIST_FILTER__SYMBOL,
7a007ca9 ACM	21	};
7a007ca9 ACM	22
3d1d07ec JK	23	struct callchain_param callchain_param = {
3d1d07ec JK	24	.mode = CHAIN_GRAPH_REL,
d797fdc5 SL	25	.min_percent = 0.5,
d797fdc5 SL	26	.order = ORDER_CALLEE
3d1d07ec JK	27	};
3d1d07ec JK	28
42b28ac0	29	u16 hists__col_len(struct hists *hists, enum hist_column col)
8a6c5b26	30	{
42b28ac0	31	return hists->col_len[col];
8a6c5b26 ACM	32	}
8a6c5b26 ACM	33
42b28ac0	34	void hists__set_col_len(struct hists *hists, enum hist_column col, u16 len)
8a6c5b26	35	{
42b28ac0	36	hists->col_len[col] = len;
8a6c5b26 ACM	37	}
8a6c5b26 ACM	38
42b28ac0	39	bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len)
8a6c5b26	40	{
42b28ac0 ACM	41	if (len > hists__col_len(hists, col)) {
42b28ac0 ACM	42	hists__set_col_len(hists, col, len);
8a6c5b26 ACM	43	return true;
	44	}
	45	return false;
	46	}
	47
7ccf4f90	48	void hists__reset_col_len(struct hists *hists)
8a6c5b26 ACM	49	{
	50	enum hist_column col;
	51
	52	for (col = 0; col < HISTC_NR_COLS; ++col)
42b28ac0	53	hists__set_col_len(hists, col, 0);
8a6c5b26 ACM	54	}
8a6c5b26 ACM	55
b5387528 RAV	56	static void hists__set_unres_dso_col_len(struct hists *hists, int dso)
	57	{
	58	const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
	59
	60	if (hists__col_len(hists, dso) < unresolved_col_width &&
	61	!symbol_conf.col_width_list_str && !symbol_conf.field_sep &&
	62	!symbol_conf.dso_list)
	63	hists__set_col_len(hists, dso, unresolved_col_width);
	64	}
	65
7ccf4f90	66	void hists__calc_col_len(struct hists hists, struct hist_entry h)
8a6c5b26	67	{
b5387528	68	const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
8a6c5b26 ACM	69	u16 len;
	70
	71	if (h->ms.sym)
b5387528 RAV	72	hists__new_col_len(hists, HISTC_SYMBOL, h->ms.sym->namelen + 4);
	73	else
	74	hists__set_unres_dso_col_len(hists, HISTC_DSO);
8a6c5b26 ACM	75
8a6c5b26 ACM	76	len = thread__comm_len(h->thread);
42b28ac0 ACM	77	if (hists__new_col_len(hists, HISTC_COMM, len))
42b28ac0 ACM	78	hists__set_col_len(hists, HISTC_THREAD, len + 6);
8a6c5b26 ACM	79
	80	if (h->ms.map) {
	81	len = dso__name_len(h->ms.map->dso);
42b28ac0	82	hists__new_col_len(hists, HISTC_DSO, len);
8a6c5b26	83	}
b5387528 RAV	84
	85	if (h->branch_info) {
	86	int symlen;
	87	/*
	88	* +4 accounts for '[x] ' priv level info
	89	* +2 account of 0x prefix on raw addresses
	90	*/
	91	if (h->branch_info->from.sym) {
	92	symlen = (int)h->branch_info->from.sym->namelen + 4;
	93	hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
	94
	95	symlen = dso__name_len(h->branch_info->from.map->dso);
	96	hists__new_col_len(hists, HISTC_DSO_FROM, symlen);
	97	} else {
	98	symlen = unresolved_col_width + 4 + 2;
	99	hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
	100	hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM);
	101	}
	102
	103	if (h->branch_info->to.sym) {
	104	symlen = (int)h->branch_info->to.sym->namelen + 4;
	105	hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
	106
	107	symlen = dso__name_len(h->branch_info->to.map->dso);
	108	hists__new_col_len(hists, HISTC_DSO_TO, symlen);
	109	} else {
	110	symlen = unresolved_col_width + 4 + 2;
	111	hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
	112	hists__set_unres_dso_col_len(hists, HISTC_DSO_TO);
	113	}
	114	}
8a6c5b26 ACM	115	}
8a6c5b26 ACM	116
7ccf4f90 NK	117	void hists__output_recalc_col_len(struct hists *hists, int max_rows)
	118	{
	119	struct rb_node *next = rb_first(&hists->entries);
	120	struct hist_entry *n;
	121	int row = 0;
	122
	123	hists__reset_col_len(hists);
	124
	125	while (next && row++ < max_rows) {
	126	n = rb_entry(next, struct hist_entry, rb_node);
	127	if (!n->filtered)
	128	hists__calc_col_len(hists, n);
	129	next = rb_next(&n->rb_node);
	130	}
	131	}
	132
12c14278	133	static void hist_entry__add_cpumode_period(struct hist_entry *he,
c82ee828	134	unsigned int cpumode, u64 period)
a1645ce1	135	{
28e2a106	136	switch (cpumode) {
a1645ce1	137	case PERF_RECORD_MISC_KERNEL:
12c14278	138	he->period_sys += period;
a1645ce1 ZY	139	break;
a1645ce1 ZY	140	case PERF_RECORD_MISC_USER:
12c14278	141	he->period_us += period;
a1645ce1 ZY	142	break;
a1645ce1 ZY	143	case PERF_RECORD_MISC_GUEST_KERNEL:
12c14278	144	he->period_guest_sys += period;
a1645ce1 ZY	145	break;
a1645ce1 ZY	146	case PERF_RECORD_MISC_GUEST_USER:
12c14278	147	he->period_guest_us += period;
a1645ce1 ZY	148	break;
	149	default:
	150	break;
	151	}
	152	}
	153
ab81f3fd ACM	154	static void hist_entry__decay(struct hist_entry *he)
	155	{
	156	he->period = (he->period * 7) / 8;
	157	he->nr_events = (he->nr_events * 7) / 8;
	158	}
	159
	160	static bool hists__decay_entry(struct hists hists, struct hist_entry he)
	161	{
c64550cf ACM	162	u64 prev_period = he->period;
	163
	164	if (prev_period == 0)
df71d95f	165	return true;
c64550cf	166
ab81f3fd	167	hist_entry__decay(he);
c64550cf ACM	168
	169	if (!he->filtered)
	170	hists->stats.total_period -= prev_period - he->period;
	171
ab81f3fd ACM	172	return he->period == 0;
	173	}
	174
b079d4e9 ACM	175	static void __hists__decay_entries(struct hists *hists, bool zap_user,
b079d4e9 ACM	176	bool zap_kernel, bool threaded)
ab81f3fd ACM	177	{
	178	struct rb_node *next = rb_first(&hists->entries);
	179	struct hist_entry *n;
	180
	181	while (next) {
	182	n = rb_entry(next, struct hist_entry, rb_node);
	183	next = rb_next(&n->rb_node);
df71d95f ACM	184	/*
	185	* We may be annotating this, for instance, so keep it here in
	186	* case some it gets new samples, we'll eventually free it when
	187	* the user stops browsing and it agains gets fully decayed.
	188	*/
b079d4e9 ACM	189	if (((zap_user && n->level == '.') \|\|
	190	(zap_kernel && n->level != '.') \|\|
	191	hists__decay_entry(hists, n)) &&
	192	!n->used) {
ab81f3fd ACM	193	rb_erase(&n->rb_node, &hists->entries);
ab81f3fd ACM	194
e345fa18	195	if (sort__need_collapse \|\| threaded)
ab81f3fd ACM	196	rb_erase(&n->rb_node_in, &hists->entries_collapsed);
	197
	198	hist_entry__free(n);
	199	--hists->nr_entries;
	200	}
	201	}
	202	}
	203
b079d4e9	204	void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
e345fa18	205	{
b079d4e9	206	return __hists__decay_entries(hists, zap_user, zap_kernel, false);
e345fa18 ACM	207	}
e345fa18 ACM	208
b079d4e9 ACM	209	void hists__decay_entries_threaded(struct hists *hists,
b079d4e9 ACM	210	bool zap_user, bool zap_kernel)
e345fa18	211	{
b079d4e9	212	return __hists__decay_entries(hists, zap_user, zap_kernel, true);
e345fa18 ACM	213	}
e345fa18 ACM	214
3d1d07ec	215	/*
c82ee828	216	* histogram, sorted on item, collects periods
3d1d07ec JK	217	*/
3d1d07ec JK	218
28e2a106 ACM	219	static struct hist_entry hist_entry__new(struct hist_entry template)
28e2a106 ACM	220	{
d2009c51	221	size_t callchain_size = symbol_conf.use_callchain ? sizeof(struct callchain_root) : 0;
12c14278	222	struct hist_entry he = malloc(sizeof(he) + callchain_size);
28e2a106	223
12c14278 ACM	224	if (he != NULL) {
	225	he = template;
	226	he->nr_events = 1;
	227	if (he->ms.map)
	228	he->ms.map->referenced = true;
28e2a106	229	if (symbol_conf.use_callchain)
12c14278	230	callchain_init(he->callchain);
28e2a106 ACM	231	}
28e2a106 ACM	232
12c14278	233	return he;
28e2a106 ACM	234	}
28e2a106 ACM	235
42b28ac0	236	static void hists__inc_nr_entries(struct hists hists, struct hist_entry h)
fefb0b94	237	{
8a6c5b26	238	if (!h->filtered) {
42b28ac0 ACM	239	hists__calc_col_len(hists, h);
42b28ac0 ACM	240	++hists->nr_entries;
1980c2eb	241	hists->stats.total_period += h->period;
8a6c5b26	242	}
fefb0b94 ACM	243	}
fefb0b94 ACM	244
7a007ca9 ACM	245	static u8 symbol__parent_filter(const struct symbol *parent)
	246	{
	247	if (symbol_conf.exclude_other && parent == NULL)
	248	return 1 << HIST_FILTER__PARENT;
	249	return 0;
	250	}
	251
b5387528 RAV	252	static struct hist_entry add_hist_entry(struct hists hists,
b5387528 RAV	253	struct hist_entry *entry,
1c02c4d2	254	struct addr_location *al,
b5387528	255	u64 period)
9735abf1	256	{
1980c2eb	257	struct rb_node **p;
9735abf1 ACM	258	struct rb_node *parent = NULL;
9735abf1 ACM	259	struct hist_entry *he;
9735abf1 ACM	260	int cmp;
9735abf1 ACM	261
1980c2eb ACM	262	pthread_mutex_lock(&hists->lock);
	263
	264	p = &hists->entries_in->rb_node;
	265
9735abf1 ACM	266	while (*p != NULL) {
9735abf1 ACM	267	parent = *p;
1980c2eb	268	he = rb_entry(parent, struct hist_entry, rb_node_in);
9735abf1	269
b5387528	270	cmp = hist_entry__cmp(entry, he);
9735abf1 ACM	271
9735abf1 ACM	272	if (!cmp) {
c82ee828 ACM	273	he->period += period;
c82ee828 ACM	274	++he->nr_events;
63fa471d DM	275
	276	/* If the map of an existing hist_entry has
	277	* become out-of-date due to an exec() or
	278	* similar, update it. Otherwise we will
	279	* mis-adjust symbol addresses when computing
	280	* the history counter to increment.
	281	*/
	282	if (he->ms.map != entry->ms.map) {
	283	he->ms.map = entry->ms.map;
	284	if (he->ms.map)
	285	he->ms.map->referenced = true;
	286	}
28e2a106	287	goto out;
9735abf1 ACM	288	}
	289
	290	if (cmp < 0)
	291	p = &(*p)->rb_left;
	292	else
	293	p = &(*p)->rb_right;
	294	}
	295
b5387528	296	he = hist_entry__new(entry);
9735abf1	297	if (!he)
1980c2eb ACM	298	goto out_unlock;
	299
	300	rb_link_node(&he->rb_node_in, parent, p);
	301	rb_insert_color(&he->rb_node_in, hists->entries_in);
28e2a106	302	out:
c82ee828	303	hist_entry__add_cpumode_period(he, al->cpumode, period);
1980c2eb ACM	304	out_unlock:
1980c2eb ACM	305	pthread_mutex_unlock(&hists->lock);
9735abf1 ACM	306	return he;
	307	}
	308
b5387528 RAV	309	struct hist_entry __hists__add_branch_entry(struct hists self,
	310	struct addr_location *al,
	311	struct symbol *sym_parent,
	312	struct branch_info *bi,
	313	u64 period)
	314	{
	315	struct hist_entry entry = {
	316	.thread = al->thread,
	317	.ms = {
	318	.map = bi->to.map,
	319	.sym = bi->to.sym,
	320	},
	321	.cpu = al->cpu,
	322	.ip = bi->to.addr,
	323	.level = al->level,
	324	.period = period,
	325	.parent = sym_parent,
	326	.filtered = symbol__parent_filter(sym_parent),
	327	.branch_info = bi,
	328	};
	329
	330	return add_hist_entry(self, &entry, al, period);
	331	}
	332
	333	struct hist_entry __hists__add_entry(struct hists self,
	334	struct addr_location *al,
	335	struct symbol *sym_parent, u64 period)
	336	{
	337	struct hist_entry entry = {
	338	.thread = al->thread,
	339	.ms = {
	340	.map = al->map,
	341	.sym = al->sym,
	342	},
	343	.cpu = al->cpu,
	344	.ip = al->addr,
	345	.level = al->level,
	346	.period = period,
	347	.parent = sym_parent,
	348	.filtered = symbol__parent_filter(sym_parent),
	349	};
	350
	351	return add_hist_entry(self, &entry, al, period);
	352	}
	353
3d1d07ec JK	354	int64_t
	355	hist_entry__cmp(struct hist_entry left, struct hist_entry right)
	356	{
	357	struct sort_entry *se;
	358	int64_t cmp = 0;
	359
	360	list_for_each_entry(se, &hist_entry__sort_list, list) {
fcd14984	361	cmp = se->se_cmp(left, right);
3d1d07ec JK	362	if (cmp)
	363	break;
	364	}
	365
	366	return cmp;
	367	}
	368
	369	int64_t
	370	hist_entry__collapse(struct hist_entry left, struct hist_entry right)
	371	{
	372	struct sort_entry *se;
	373	int64_t cmp = 0;
	374
	375	list_for_each_entry(se, &hist_entry__sort_list, list) {
	376	int64_t (f)(struct hist_entry , struct hist_entry *);
	377
fcd14984	378	f = se->se_collapse ?: se->se_cmp;
3d1d07ec JK	379
	380	cmp = f(left, right);
	381	if (cmp)
	382	break;
	383	}
	384
	385	return cmp;
	386	}
	387
	388	void hist_entry__free(struct hist_entry *he)
	389	{
	390	free(he);
	391	}
	392
	393	/*
	394	* collapse the histogram
	395	*/
	396
1d037ca1	397	static bool hists__collapse_insert_entry(struct hists *hists __maybe_unused,
1b3a0e95 FW	398	struct rb_root *root,
1b3a0e95 FW	399	struct hist_entry *he)
3d1d07ec	400	{
b9bf0892	401	struct rb_node **p = &root->rb_node;
3d1d07ec JK	402	struct rb_node *parent = NULL;
	403	struct hist_entry *iter;
	404	int64_t cmp;
	405
	406	while (*p != NULL) {
	407	parent = *p;
1980c2eb	408	iter = rb_entry(parent, struct hist_entry, rb_node_in);
3d1d07ec JK	409
	410	cmp = hist_entry__collapse(iter, he);
	411
	412	if (!cmp) {
9ec60972 NK	413	iter->period += he->period;
	414	iter->period_sys += he->period_sys;
	415	iter->period_us += he->period_us;
	416	iter->period_guest_sys += he->period_guest_sys;
	417	iter->period_guest_us += he->period_guest_us;
	418	iter->nr_events += he->nr_events;
	419
1b3a0e95	420	if (symbol_conf.use_callchain) {
47260645 NK	421	callchain_cursor_reset(&callchain_cursor);
	422	callchain_merge(&callchain_cursor,
	423	iter->callchain,
1b3a0e95 FW	424	he->callchain);
1b3a0e95 FW	425	}
3d1d07ec	426	hist_entry__free(he);
fefb0b94	427	return false;
3d1d07ec JK	428	}
	429
	430	if (cmp < 0)
	431	p = &(*p)->rb_left;
	432	else
	433	p = &(*p)->rb_right;
	434	}
	435
1980c2eb ACM	436	rb_link_node(&he->rb_node_in, parent, p);
1980c2eb ACM	437	rb_insert_color(&he->rb_node_in, root);
fefb0b94	438	return true;
3d1d07ec JK	439	}
3d1d07ec JK	440
1980c2eb	441	static struct rb_root hists__get_rotate_entries_in(struct hists hists)
3d1d07ec	442	{
1980c2eb ACM	443	struct rb_root *root;
	444
	445	pthread_mutex_lock(&hists->lock);
	446
	447	root = hists->entries_in;
	448	if (++hists->entries_in > &hists->entries_in_array[1])
	449	hists->entries_in = &hists->entries_in_array[0];
	450
	451	pthread_mutex_unlock(&hists->lock);
	452
	453	return root;
	454	}
	455
90cf1fb5 ACM	456	static void hists__apply_filters(struct hists hists, struct hist_entry he)
	457	{
	458	hists__filter_entry_by_dso(hists, he);
	459	hists__filter_entry_by_thread(hists, he);
e94d53eb	460	hists__filter_entry_by_symbol(hists, he);
90cf1fb5 ACM	461	}
90cf1fb5 ACM	462
1980c2eb ACM	463	static void __hists__collapse_resort(struct hists *hists, bool threaded)
	464	{
	465	struct rb_root *root;
3d1d07ec JK	466	struct rb_node *next;
	467	struct hist_entry *n;
	468
1980c2eb	469	if (!sort__need_collapse && !threaded)
3d1d07ec JK	470	return;
3d1d07ec JK	471
1980c2eb ACM	472	root = hists__get_rotate_entries_in(hists);
1980c2eb ACM	473	next = rb_first(root);
b9bf0892	474
3d1d07ec	475	while (next) {
1980c2eb ACM	476	n = rb_entry(next, struct hist_entry, rb_node_in);
1980c2eb ACM	477	next = rb_next(&n->rb_node_in);
3d1d07ec	478
1980c2eb	479	rb_erase(&n->rb_node_in, root);
90cf1fb5 ACM	480	if (hists__collapse_insert_entry(hists, &hists->entries_collapsed, n)) {
	481	/*
	482	* If it wasn't combined with one of the entries already
	483	* collapsed, we need to apply the filters that may have
	484	* been set by, say, the hist_browser.
	485	*/
	486	hists__apply_filters(hists, n);
90cf1fb5	487	}
3d1d07ec	488	}
1980c2eb	489	}
b9bf0892	490
1980c2eb ACM	491	void hists__collapse_resort(struct hists *hists)
	492	{
	493	return __hists__collapse_resort(hists, false);
	494	}
	495
	496	void hists__collapse_resort_threaded(struct hists *hists)
	497	{
	498	return __hists__collapse_resort(hists, true);
3d1d07ec JK	499	}
	500
	501	/*
c82ee828	502	* reverse the map, sort on period.
3d1d07ec JK	503	*/
3d1d07ec JK	504
1c02c4d2 ACM	505	static void __hists__insert_output_entry(struct rb_root *entries,
	506	struct hist_entry *he,
	507	u64 min_callchain_hits)
3d1d07ec	508	{
1c02c4d2	509	struct rb_node **p = &entries->rb_node;
3d1d07ec JK	510	struct rb_node *parent = NULL;
	511	struct hist_entry *iter;
	512
d599db3f	513	if (symbol_conf.use_callchain)
b9fb9304	514	callchain_param.sort(&he->sorted_chain, he->callchain,
3d1d07ec JK	515	min_callchain_hits, &callchain_param);
	516
	517	while (*p != NULL) {
	518	parent = *p;
	519	iter = rb_entry(parent, struct hist_entry, rb_node);
	520
c82ee828	521	if (he->period > iter->period)
3d1d07ec JK	522	p = &(*p)->rb_left;
	523	else
	524	p = &(*p)->rb_right;
	525	}
	526
	527	rb_link_node(&he->rb_node, parent, p);
1c02c4d2	528	rb_insert_color(&he->rb_node, entries);
3d1d07ec JK	529	}
3d1d07ec JK	530
1980c2eb	531	static void __hists__output_resort(struct hists *hists, bool threaded)
3d1d07ec	532	{
1980c2eb	533	struct rb_root *root;
3d1d07ec JK	534	struct rb_node *next;
3d1d07ec JK	535	struct hist_entry *n;
3d1d07ec JK	536	u64 min_callchain_hits;
3d1d07ec JK	537
42b28ac0	538	min_callchain_hits = hists->stats.total_period * (callchain_param.min_percent / 100);
3d1d07ec	539
1980c2eb ACM	540	if (sort__need_collapse \|\| threaded)
	541	root = &hists->entries_collapsed;
	542	else
	543	root = hists->entries_in;
	544
	545	next = rb_first(root);
	546	hists->entries = RB_ROOT;
3d1d07ec	547
42b28ac0	548	hists->nr_entries = 0;
7928631a	549	hists->stats.total_period = 0;
42b28ac0	550	hists__reset_col_len(hists);
fefb0b94	551
3d1d07ec	552	while (next) {
1980c2eb ACM	553	n = rb_entry(next, struct hist_entry, rb_node_in);
1980c2eb ACM	554	next = rb_next(&n->rb_node_in);
3d1d07ec	555
1980c2eb	556	__hists__insert_output_entry(&hists->entries, n, min_callchain_hits);
42b28ac0	557	hists__inc_nr_entries(hists, n);
3d1d07ec	558	}
1980c2eb	559	}
b9bf0892	560
1980c2eb ACM	561	void hists__output_resort(struct hists *hists)
	562	{
	563	return __hists__output_resort(hists, false);
	564	}
	565
	566	void hists__output_resort_threaded(struct hists *hists)
	567	{
	568	return __hists__output_resort(hists, true);
3d1d07ec	569	}
4ecf84d0	570
42b28ac0	571	static void hists__remove_entry_filter(struct hists hists, struct hist_entry h,
cc5edb0e ACM	572	enum hist_filter filter)
	573	{
	574	h->filtered &= ~(1 << filter);
	575	if (h->filtered)
	576	return;
	577
42b28ac0	578	++hists->nr_entries;
0f0cbf7a	579	if (h->ms.unfolded)
42b28ac0	580	hists->nr_entries += h->nr_rows;
0f0cbf7a	581	h->row_offset = 0;
42b28ac0 ACM	582	hists->stats.total_period += h->period;
42b28ac0 ACM	583	hists->stats.nr_events[PERF_RECORD_SAMPLE] += h->nr_events;
cc5edb0e	584
42b28ac0	585	hists__calc_col_len(hists, h);
cc5edb0e ACM	586	}
cc5edb0e ACM	587
90cf1fb5 ACM	588
	589	static bool hists__filter_entry_by_dso(struct hists *hists,
	590	struct hist_entry *he)
	591	{
	592	if (hists->dso_filter != NULL &&
	593	(he->ms.map == NULL \|\| he->ms.map->dso != hists->dso_filter)) {
	594	he->filtered \|= (1 << HIST_FILTER__DSO);
	595	return true;
	596	}
	597
	598	return false;
	599	}
	600
d7b76f09	601	void hists__filter_by_dso(struct hists *hists)
b09e0190 ACM	602	{
	603	struct rb_node *nd;
	604
42b28ac0 ACM	605	hists->nr_entries = hists->stats.total_period = 0;
	606	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
	607	hists__reset_col_len(hists);
b09e0190	608
42b28ac0	609	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
b09e0190 ACM	610	struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
	611
	612	if (symbol_conf.exclude_other && !h->parent)
	613	continue;
	614
90cf1fb5	615	if (hists__filter_entry_by_dso(hists, h))
b09e0190	616	continue;
b09e0190	617
42b28ac0	618	hists__remove_entry_filter(hists, h, HIST_FILTER__DSO);
b09e0190 ACM	619	}
	620	}
	621
90cf1fb5 ACM	622	static bool hists__filter_entry_by_thread(struct hists *hists,
	623	struct hist_entry *he)
	624	{
	625	if (hists->thread_filter != NULL &&
	626	he->thread != hists->thread_filter) {
	627	he->filtered \|= (1 << HIST_FILTER__THREAD);
	628	return true;
	629	}
	630
	631	return false;
	632	}
	633
d7b76f09	634	void hists__filter_by_thread(struct hists *hists)
b09e0190 ACM	635	{
	636	struct rb_node *nd;
	637
42b28ac0 ACM	638	hists->nr_entries = hists->stats.total_period = 0;
	639	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
	640	hists__reset_col_len(hists);
b09e0190	641
42b28ac0	642	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
b09e0190 ACM	643	struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
b09e0190 ACM	644
90cf1fb5	645	if (hists__filter_entry_by_thread(hists, h))
b09e0190	646	continue;
cc5edb0e	647
42b28ac0	648	hists__remove_entry_filter(hists, h, HIST_FILTER__THREAD);
b09e0190 ACM	649	}
b09e0190 ACM	650	}
ef7b93a1	651
e94d53eb NK	652	static bool hists__filter_entry_by_symbol(struct hists *hists,
	653	struct hist_entry *he)
	654	{
	655	if (hists->symbol_filter_str != NULL &&
	656	(!he->ms.sym \|\| strstr(he->ms.sym->name,
	657	hists->symbol_filter_str) == NULL)) {
	658	he->filtered \|= (1 << HIST_FILTER__SYMBOL);
	659	return true;
	660	}
	661
	662	return false;
	663	}
	664
	665	void hists__filter_by_symbol(struct hists *hists)
	666	{
	667	struct rb_node *nd;
	668
	669	hists->nr_entries = hists->stats.total_period = 0;
	670	hists->stats.nr_events[PERF_RECORD_SAMPLE] = 0;
	671	hists__reset_col_len(hists);
	672
	673	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
	674	struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
	675
	676	if (hists__filter_entry_by_symbol(hists, h))
	677	continue;
	678
	679	hists__remove_entry_filter(hists, h, HIST_FILTER__SYMBOL);
	680	}
	681	}
	682
2f525d01	683	int hist_entry__inc_addr_samples(struct hist_entry *he, int evidx, u64 ip)
ef7b93a1	684	{
2f525d01	685	return symbol__inc_addr_samples(he->ms.sym, he->ms.map, evidx, ip);
ef7b93a1 ACM	686	}
ef7b93a1 ACM	687
ce6f4fab	688	int hist_entry__annotate(struct hist_entry *he, size_t privsize)
ef7b93a1	689	{
ce6f4fab	690	return symbol__annotate(he->ms.sym, he->ms.map, privsize);
ef7b93a1	691	}
c8446b9b	692
42b28ac0	693	void hists__inc_nr_events(struct hists *hists, u32 type)
c8446b9b	694	{
42b28ac0 ACM	695	++hists->stats.nr_events[0];
42b28ac0 ACM	696	++hists->stats.nr_events[type];
c8446b9b	697	}