1// SPDX-License-Identifier: GPL-2.0
   2#include "util.h"
   3#include "build-id.h"
   4#include "hist.h"
   5#include "map.h"
   6#include "session.h"
   7#include "namespaces.h"
   8#include "sort.h"
   9#include "units.h"
  10#include "evlist.h"
  11#include "evsel.h"
  12#include "annotate.h"
  13#include "srcline.h"
  14#include "thread.h"
  15#include "ui/progress.h"
  16#include <errno.h>
  17#include <math.h>
  18#include <inttypes.h>
  19#include <sys/param.h>
  20
  21static bool hists__filter_entry_by_dso(struct hists *hists,
  22				       struct hist_entry *he);
  23static bool hists__filter_entry_by_thread(struct hists *hists,
  24					  struct hist_entry *he);
  25static bool hists__filter_entry_by_symbol(struct hists *hists,
  26					  struct hist_entry *he);
  27static bool hists__filter_entry_by_socket(struct hists *hists,
  28					  struct hist_entry *he);
  29
  30u16 hists__col_len(struct hists *hists, enum hist_column col)
 
 
 
 
 
 
  31{
  32	return hists->col_len[col];
  33}
  34
  35void hists__set_col_len(struct hists *hists, enum hist_column col, u16 len)
  36{
  37	hists->col_len[col] = len;
  38}
  39
  40bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len)
  41{
  42	if (len > hists__col_len(hists, col)) {
  43		hists__set_col_len(hists, col, len);
  44		return true;
  45	}
  46	return false;
  47}
  48
  49void hists__reset_col_len(struct hists *hists)
  50{
  51	enum hist_column col;
  52
  53	for (col = 0; col < HISTC_NR_COLS; ++col)
  54		hists__set_col_len(hists, col, 0);
  55}
  56
  57static void hists__set_unres_dso_col_len(struct hists *hists, int dso)
  58{
  59	const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
  60
  61	if (hists__col_len(hists, dso) < unresolved_col_width &&
  62	    !symbol_conf.col_width_list_str && !symbol_conf.field_sep &&
  63	    !symbol_conf.dso_list)
  64		hists__set_col_len(hists, dso, unresolved_col_width);
  65}
  66
  67void hists__calc_col_len(struct hists *hists, struct hist_entry *h)
  68{
  69	const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
  70	int symlen;
  71	u16 len;
  72
  73	/*
  74	 * +4 accounts for '[x] ' priv level info
  75	 * +2 accounts for 0x prefix on raw addresses
  76	 * +3 accounts for ' y ' symtab origin info
  77	 */
  78	if (h->ms.sym) {
  79		symlen = h->ms.sym->namelen + 4;
  80		if (verbose > 0)
  81			symlen += BITS_PER_LONG / 4 + 2 + 3;
  82		hists__new_col_len(hists, HISTC_SYMBOL, symlen);
  83	} else {
  84		symlen = unresolved_col_width + 4 + 2;
  85		hists__new_col_len(hists, HISTC_SYMBOL, symlen);
  86		hists__set_unres_dso_col_len(hists, HISTC_DSO);
  87	}
  88
  89	len = thread__comm_len(h->thread);
  90	if (hists__new_col_len(hists, HISTC_COMM, len))
  91		hists__set_col_len(hists, HISTC_THREAD, len + 8);
  92
  93	if (h->ms.map) {
  94		len = dso__name_len(h->ms.map->dso);
  95		hists__new_col_len(hists, HISTC_DSO, len);
  96	}
  97
  98	if (h->parent)
  99		hists__new_col_len(hists, HISTC_PARENT, h->parent->namelen);
 100
 101	if (h->branch_info) {
 102		if (h->branch_info->from.sym) {
 103			symlen = (int)h->branch_info->from.sym->namelen + 4;
 104			if (verbose > 0)
 105				symlen += BITS_PER_LONG / 4 + 2 + 3;
 106			hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
 107
 108			symlen = dso__name_len(h->branch_info->from.map->dso);
 109			hists__new_col_len(hists, HISTC_DSO_FROM, symlen);
 110		} else {
 111			symlen = unresolved_col_width + 4 + 2;
 112			hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
 113			hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM);
 114		}
 115
 116		if (h->branch_info->to.sym) {
 117			symlen = (int)h->branch_info->to.sym->namelen + 4;
 118			if (verbose > 0)
 119				symlen += BITS_PER_LONG / 4 + 2 + 3;
 120			hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
 121
 122			symlen = dso__name_len(h->branch_info->to.map->dso);
 123			hists__new_col_len(hists, HISTC_DSO_TO, symlen);
 124		} else {
 125			symlen = unresolved_col_width + 4 + 2;
 126			hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
 127			hists__set_unres_dso_col_len(hists, HISTC_DSO_TO);
 128		}
 129
 130		if (h->branch_info->srcline_from)
 131			hists__new_col_len(hists, HISTC_SRCLINE_FROM,
 132					strlen(h->branch_info->srcline_from));
 133		if (h->branch_info->srcline_to)
 134			hists__new_col_len(hists, HISTC_SRCLINE_TO,
 135					strlen(h->branch_info->srcline_to));
 136	}
 137
 138	if (h->mem_info) {
 139		if (h->mem_info->daddr.sym) {
 140			symlen = (int)h->mem_info->daddr.sym->namelen + 4
 141			       + unresolved_col_width + 2;
 142			hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
 143					   symlen);
 144			hists__new_col_len(hists, HISTC_MEM_DCACHELINE,
 145					   symlen + 1);
 146		} else {
 147			symlen = unresolved_col_width + 4 + 2;
 148			hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
 149					   symlen);
 150			hists__new_col_len(hists, HISTC_MEM_DCACHELINE,
 151					   symlen);
 152		}
 153
 154		if (h->mem_info->iaddr.sym) {
 155			symlen = (int)h->mem_info->iaddr.sym->namelen + 4
 156			       + unresolved_col_width + 2;
 157			hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL,
 158					   symlen);
 159		} else {
 160			symlen = unresolved_col_width + 4 + 2;
 161			hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL,
 162					   symlen);
 163		}
 164
 165		if (h->mem_info->daddr.map) {
 166			symlen = dso__name_len(h->mem_info->daddr.map->dso);
 167			hists__new_col_len(hists, HISTC_MEM_DADDR_DSO,
 168					   symlen);
 169		} else {
 170			symlen = unresolved_col_width + 4 + 2;
 171			hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
 172		}
 173
 174		hists__new_col_len(hists, HISTC_MEM_PHYS_DADDR,
 175				   unresolved_col_width + 4 + 2);
 176
 177	} else {
 178		symlen = unresolved_col_width + 4 + 2;
 179		hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, symlen);
 180		hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL, symlen);
 181		hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
 182	}
 183
 184	hists__new_col_len(hists, HISTC_CGROUP_ID, 20);
 185	hists__new_col_len(hists, HISTC_CPU, 3);
 186	hists__new_col_len(hists, HISTC_SOCKET, 6);
 187	hists__new_col_len(hists, HISTC_MEM_LOCKED, 6);
 188	hists__new_col_len(hists, HISTC_MEM_TLB, 22);
 189	hists__new_col_len(hists, HISTC_MEM_SNOOP, 12);
 190	hists__new_col_len(hists, HISTC_MEM_LVL, 21 + 3);
 191	hists__new_col_len(hists, HISTC_LOCAL_WEIGHT, 12);
 192	hists__new_col_len(hists, HISTC_GLOBAL_WEIGHT, 12);
 193
 194	if (h->srcline) {
 195		len = MAX(strlen(h->srcline), strlen(sort_srcline.se_header));
 196		hists__new_col_len(hists, HISTC_SRCLINE, len);
 197	}
 198
 199	if (h->srcfile)
 200		hists__new_col_len(hists, HISTC_SRCFILE, strlen(h->srcfile));
 201
 202	if (h->transaction)
 203		hists__new_col_len(hists, HISTC_TRANSACTION,
 204				   hist_entry__transaction_len());
 205
 206	if (h->trace_output)
 207		hists__new_col_len(hists, HISTC_TRACE, strlen(h->trace_output));
 208}
 209
 210void hists__output_recalc_col_len(struct hists *hists, int max_rows)
 211{
 212	struct rb_node *next = rb_first(&hists->entries);
 213	struct hist_entry *n;
 214	int row = 0;
 215
 216	hists__reset_col_len(hists);
 217
 218	while (next && row++ < max_rows) {
 219		n = rb_entry(next, struct hist_entry, rb_node);
 220		if (!n->filtered)
 221			hists__calc_col_len(hists, n);
 222		next = rb_next(&n->rb_node);
 223	}
 224}
 225
 226static void he_stat__add_cpumode_period(struct he_stat *he_stat,
 227					unsigned int cpumode, u64 period)
 228{
 229	switch (cpumode) {
 230	case PERF_RECORD_MISC_KERNEL:
 231		he_stat->period_sys += period;
 232		break;
 233	case PERF_RECORD_MISC_USER:
 234		he_stat->period_us += period;
 235		break;
 236	case PERF_RECORD_MISC_GUEST_KERNEL:
 237		he_stat->period_guest_sys += period;
 238		break;
 239	case PERF_RECORD_MISC_GUEST_USER:
 240		he_stat->period_guest_us += period;
 241		break;
 242	default:
 243		break;
 244	}
 245}
 246
 247static void he_stat__add_period(struct he_stat *he_stat, u64 period,
 248				u64 weight)
 249{
 250
 251	he_stat->period		+= period;
 252	he_stat->weight		+= weight;
 253	he_stat->nr_events	+= 1;
 254}
 255
 256static void he_stat__add_stat(struct he_stat *dest, struct he_stat *src)
 257{
 258	dest->period		+= src->period;
 259	dest->period_sys	+= src->period_sys;
 260	dest->period_us		+= src->period_us;
 261	dest->period_guest_sys	+= src->period_guest_sys;
 262	dest->period_guest_us	+= src->period_guest_us;
 263	dest->nr_events		+= src->nr_events;
 264	dest->weight		+= src->weight;
 265}
 266
 267static void he_stat__decay(struct he_stat *he_stat)
 268{
 269	he_stat->period = (he_stat->period * 7) / 8;
 270	he_stat->nr_events = (he_stat->nr_events * 7) / 8;
 271	/* XXX need decay for weight too? */
 272}
 273
 274static void hists__delete_entry(struct hists *hists, struct hist_entry *he);
 275
 276static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
 277{
 278	u64 prev_period = he->stat.period;
 279	u64 diff;
 280
 281	if (prev_period == 0)
 282		return true;
 283
 284	he_stat__decay(&he->stat);
 285	if (symbol_conf.cumulate_callchain)
 286		he_stat__decay(he->stat_acc);
 287	decay_callchain(he->callchain);
 288
 289	diff = prev_period - he->stat.period;
 290
 291	if (!he->depth) {
 292		hists->stats.total_period -= diff;
 293		if (!he->filtered)
 294			hists->stats.total_non_filtered_period -= diff;
 295	}
 296
 297	if (!he->leaf) {
 298		struct hist_entry *child;
 299		struct rb_node *node = rb_first(&he->hroot_out);
 300		while (node) {
 301			child = rb_entry(node, struct hist_entry, rb_node);
 302			node = rb_next(node);
 303
 304			if (hists__decay_entry(hists, child))
 305				hists__delete_entry(hists, child);
 306		}
 307	}
 308
 309	return he->stat.period == 0;
 310}
 311
 312static void hists__delete_entry(struct hists *hists, struct hist_entry *he)
 313{
 314	struct rb_root *root_in;
 315	struct rb_root *root_out;
 316
 317	if (he->parent_he) {
 318		root_in  = &he->parent_he->hroot_in;
 319		root_out = &he->parent_he->hroot_out;
 320	} else {
 321		if (hists__has(hists, need_collapse))
 322			root_in = &hists->entries_collapsed;
 323		else
 324			root_in = hists->entries_in;
 325		root_out = &hists->entries;
 326	}
 327
 328	rb_erase(&he->rb_node_in, root_in);
 329	rb_erase(&he->rb_node, root_out);
 330
 331	--hists->nr_entries;
 332	if (!he->filtered)
 333		--hists->nr_non_filtered_entries;
 334
 335	hist_entry__delete(he);
 336}
 337
 338void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
 339{
 340	struct rb_node *next = rb_first(&hists->entries);
 341	struct hist_entry *n;
 342
 343	while (next) {
 344		n = rb_entry(next, struct hist_entry, rb_node);
 345		next = rb_next(&n->rb_node);
 346		if (((zap_user && n->level == '.') ||
 347		     (zap_kernel && n->level != '.') ||
 348		     hists__decay_entry(hists, n))) {
 349			hists__delete_entry(hists, n);
 350		}
 351	}
 352}
 353
 354void hists__delete_entries(struct hists *hists)
 355{
 356	struct rb_node *next = rb_first(&hists->entries);
 357	struct hist_entry *n;
 358
 359	while (next) {
 360		n = rb_entry(next, struct hist_entry, rb_node);
 361		next = rb_next(&n->rb_node);
 362
 363		hists__delete_entry(hists, n);
 364	}
 365}
 366
 367/*
 368 * histogram, sorted on item, collects periods
 369 */
 370
 371static int hist_entry__init(struct hist_entry *he,
 372			    struct hist_entry *template,
 373			    bool sample_self)
 374{
 375	*he = *template;
 
 376
 377	if (symbol_conf.cumulate_callchain) {
 378		he->stat_acc = malloc(sizeof(he->stat));
 379		if (he->stat_acc == NULL)
 380			return -ENOMEM;
 381		memcpy(he->stat_acc, &he->stat, sizeof(he->stat));
 382		if (!sample_self)
 383			memset(&he->stat, 0, sizeof(he->stat));
 384	}
 385
 386	map__get(he->ms.map);
 387
 388	if (he->branch_info) {
 389		/*
 390		 * This branch info is (a part of) allocated from
 391		 * sample__resolve_bstack() and will be freed after
 392		 * adding new entries.  So we need to save a copy.
 393		 */
 394		he->branch_info = malloc(sizeof(*he->branch_info));
 395		if (he->branch_info == NULL) {
 396			map__zput(he->ms.map);
 397			free(he->stat_acc);
 398			return -ENOMEM;
 399		}
 400
 401		memcpy(he->branch_info, template->branch_info,
 402		       sizeof(*he->branch_info));
 403
 404		map__get(he->branch_info->from.map);
 405		map__get(he->branch_info->to.map);
 406	}
 407
 408	if (he->mem_info) {
 409		map__get(he->mem_info->iaddr.map);
 410		map__get(he->mem_info->daddr.map);
 411	}
 412
 413	if (symbol_conf.use_callchain)
 414		callchain_init(he->callchain);
 415
 416	if (he->raw_data) {
 417		he->raw_data = memdup(he->raw_data, he->raw_size);
 418
 419		if (he->raw_data == NULL) {
 420			map__put(he->ms.map);
 421			if (he->branch_info) {
 422				map__put(he->branch_info->from.map);
 423				map__put(he->branch_info->to.map);
 424				free(he->branch_info);
 425			}
 426			if (he->mem_info) {
 427				map__put(he->mem_info->iaddr.map);
 428				map__put(he->mem_info->daddr.map);
 429			}
 430			free(he->stat_acc);
 431			return -ENOMEM;
 432		}
 433	}
 434	INIT_LIST_HEAD(&he->pairs.node);
 435	thread__get(he->thread);
 436	he->hroot_in  = RB_ROOT;
 437	he->hroot_out = RB_ROOT;
 438
 439	if (!symbol_conf.report_hierarchy)
 440		he->leaf = true;
 441
 442	return 0;
 443}
 444
 445static void *hist_entry__zalloc(size_t size)
 446{
 447	return zalloc(size + sizeof(struct hist_entry));
 448}
 449
 450static void hist_entry__free(void *ptr)
 451{
 452	free(ptr);
 453}
 454
 455static struct hist_entry_ops default_ops = {
 456	.new	= hist_entry__zalloc,
 457	.free	= hist_entry__free,
 458};
 459
 460static struct hist_entry *hist_entry__new(struct hist_entry *template,
 461					  bool sample_self)
 462{
 463	struct hist_entry_ops *ops = template->ops;
 464	size_t callchain_size = 0;
 465	struct hist_entry *he;
 466	int err = 0;
 467
 468	if (!ops)
 469		ops = template->ops = &default_ops;
 470
 471	if (symbol_conf.use_callchain)
 472		callchain_size = sizeof(struct callchain_root);
 473
 474	he = ops->new(callchain_size);
 475	if (he) {
 476		err = hist_entry__init(he, template, sample_self);
 477		if (err) {
 478			ops->free(he);
 479			he = NULL;
 480		}
 481	}
 482
 483	return he;
 484}
 485
 486static u8 symbol__parent_filter(const struct symbol *parent)
 487{
 488	if (symbol_conf.exclude_other && parent == NULL)
 489		return 1 << HIST_FILTER__PARENT;
 490	return 0;
 491}
 492
 493static void hist_entry__add_callchain_period(struct hist_entry *he, u64 period)
 494{
 495	if (!symbol_conf.use_callchain)
 496		return;
 497
 498	he->hists->callchain_period += period;
 499	if (!he->filtered)
 500		he->hists->callchain_non_filtered_period += period;
 501}
 502
 503static struct hist_entry *hists__findnew_entry(struct hists *hists,
 504					       struct hist_entry *entry,
 505					       struct addr_location *al,
 506					       bool sample_self)
 507{
 508	struct rb_node **p;
 509	struct rb_node *parent = NULL;
 510	struct hist_entry *he;
 511	int64_t cmp;
 512	u64 period = entry->stat.period;
 513	u64 weight = entry->stat.weight;
 514
 515	p = &hists->entries_in->rb_node;
 
 
 
 
 
 
 
 
 
 516
 517	while (*p != NULL) {
 518		parent = *p;
 519		he = rb_entry(parent, struct hist_entry, rb_node_in);
 520
 521		/*
 522		 * Make sure that it receives arguments in a same order as
 523		 * hist_entry__collapse() so that we can use an appropriate
 524		 * function when searching an entry regardless which sort
 525		 * keys were used.
 526		 */
 527		cmp = hist_entry__cmp(he, entry);
 528
 529		if (!cmp) {
 530			if (sample_self) {
 531				he_stat__add_period(&he->stat, period, weight);
 532				hist_entry__add_callchain_period(he, period);
 533			}
 534			if (symbol_conf.cumulate_callchain)
 535				he_stat__add_period(he->stat_acc, period, weight);
 536
 537			/*
 538			 * This mem info was allocated from sample__resolve_mem
 539			 * and will not be used anymore.
 540			 */
 541			mem_info__zput(entry->mem_info);
 542
 543			/* If the map of an existing hist_entry has
 544			 * become out-of-date due to an exec() or
 545			 * similar, update it.  Otherwise we will
 546			 * mis-adjust symbol addresses when computing
 547			 * the history counter to increment.
 548			 */
 549			if (he->ms.map != entry->ms.map) {
 550				map__put(he->ms.map);
 551				he->ms.map = map__get(entry->ms.map);
 552			}
 553			goto out;
 554		}
 555
 556		if (cmp < 0)
 557			p = &(*p)->rb_left;
 558		else
 559			p = &(*p)->rb_right;
 560	}
 561
 562	he = hist_entry__new(entry, sample_self);
 563	if (!he)
 564		return NULL;
 565
 566	if (sample_self)
 567		hist_entry__add_callchain_period(he, period);
 568	hists->nr_entries++;
 569
 570	rb_link_node(&he->rb_node_in, parent, p);
 571	rb_insert_color(&he->rb_node_in, hists->entries_in);
 572out:
 573	if (sample_self)
 574		he_stat__add_cpumode_period(&he->stat, al->cpumode, period);
 575	if (symbol_conf.cumulate_callchain)
 576		he_stat__add_cpumode_period(he->stat_acc, al->cpumode, period);
 577	return he;
 578}
 579
 580static struct hist_entry*
 581__hists__add_entry(struct hists *hists,
 582		   struct addr_location *al,
 583		   struct symbol *sym_parent,
 584		   struct branch_info *bi,
 585		   struct mem_info *mi,
 586		   struct perf_sample *sample,
 587		   bool sample_self,
 588		   struct hist_entry_ops *ops)
 589{
 590	struct namespaces *ns = thread__namespaces(al->thread);
 591	struct hist_entry entry = {
 592		.thread	= al->thread,
 593		.comm = thread__comm(al->thread),
 594		.cgroup_id = {
 595			.dev = ns ? ns->link_info[CGROUP_NS_INDEX].dev : 0,
 596			.ino = ns ? ns->link_info[CGROUP_NS_INDEX].ino : 0,
 597		},
 598		.ms = {
 599			.map	= al->map,
 600			.sym	= al->sym,
 601		},
 602		.srcline = al->srcline ? strdup(al->srcline) : NULL,
 603		.socket	 = al->socket,
 604		.cpu	 = al->cpu,
 605		.cpumode = al->cpumode,
 606		.ip	 = al->addr,
 607		.level	 = al->level,
 608		.stat = {
 609			.nr_events = 1,
 610			.period	= sample->period,
 611			.weight = sample->weight,
 612		},
 613		.parent = sym_parent,
 614		.filtered = symbol__parent_filter(sym_parent) | al->filtered,
 615		.hists	= hists,
 616		.branch_info = bi,
 617		.mem_info = mi,
 618		.transaction = sample->transaction,
 619		.raw_data = sample->raw_data,
 620		.raw_size = sample->raw_size,
 621		.ops = ops,
 622	};
 623
 624	return hists__findnew_entry(hists, &entry, al, sample_self);
 625}
 626
 627struct hist_entry *hists__add_entry(struct hists *hists,
 628				    struct addr_location *al,
 629				    struct symbol *sym_parent,
 630				    struct branch_info *bi,
 631				    struct mem_info *mi,
 632				    struct perf_sample *sample,
 633				    bool sample_self)
 634{
 635	return __hists__add_entry(hists, al, sym_parent, bi, mi,
 636				  sample, sample_self, NULL);
 637}
 638
 639struct hist_entry *hists__add_entry_ops(struct hists *hists,
 640					struct hist_entry_ops *ops,
 641					struct addr_location *al,
 642					struct symbol *sym_parent,
 643					struct branch_info *bi,
 644					struct mem_info *mi,
 645					struct perf_sample *sample,
 646					bool sample_self)
 647{
 648	return __hists__add_entry(hists, al, sym_parent, bi, mi,
 649				  sample, sample_self, ops);
 650}
 651
 652static int
 653iter_next_nop_entry(struct hist_entry_iter *iter __maybe_unused,
 654		    struct addr_location *al __maybe_unused)
 655{
 656	return 0;
 657}
 658
 659static int
 660iter_add_next_nop_entry(struct hist_entry_iter *iter __maybe_unused,
 661			struct addr_location *al __maybe_unused)
 662{
 663	return 0;
 664}
 665
 666static int
 667iter_prepare_mem_entry(struct hist_entry_iter *iter, struct addr_location *al)
 668{
 669	struct perf_sample *sample = iter->sample;
 670	struct mem_info *mi;
 671
 672	mi = sample__resolve_mem(sample, al);
 673	if (mi == NULL)
 674		return -ENOMEM;
 675
 676	iter->priv = mi;
 677	return 0;
 678}
 679
 680static int
 681iter_add_single_mem_entry(struct hist_entry_iter *iter, struct addr_location *al)
 682{
 683	u64 cost;
 684	struct mem_info *mi = iter->priv;
 685	struct hists *hists = evsel__hists(iter->evsel);
 686	struct perf_sample *sample = iter->sample;
 687	struct hist_entry *he;
 688
 689	if (mi == NULL)
 690		return -EINVAL;
 691
 692	cost = sample->weight;
 693	if (!cost)
 694		cost = 1;
 695
 696	/*
 697	 * must pass period=weight in order to get the correct
 698	 * sorting from hists__collapse_resort() which is solely
 699	 * based on periods. We want sorting be done on nr_events * weight
 700	 * and this is indirectly achieved by passing period=weight here
 701	 * and the he_stat__add_period() function.
 702	 */
 703	sample->period = cost;
 704
 705	he = hists__add_entry(hists, al, iter->parent, NULL, mi,
 706			      sample, true);
 707	if (!he)
 708		return -ENOMEM;
 709
 710	iter->he = he;
 711	return 0;
 712}
 713
 714static int
 715iter_finish_mem_entry(struct hist_entry_iter *iter,
 716		      struct addr_location *al __maybe_unused)
 717{
 718	struct perf_evsel *evsel = iter->evsel;
 719	struct hists *hists = evsel__hists(evsel);
 720	struct hist_entry *he = iter->he;
 721	int err = -EINVAL;
 722
 723	if (he == NULL)
 724		goto out;
 725
 726	hists__inc_nr_samples(hists, he->filtered);
 727
 728	err = hist_entry__append_callchain(he, iter->sample);
 729
 730out:
 731	/*
 732	 * We don't need to free iter->priv (mem_info) here since the mem info
 733	 * was either already freed in hists__findnew_entry() or passed to a
 734	 * new hist entry by hist_entry__new().
 735	 */
 736	iter->priv = NULL;
 737
 738	iter->he = NULL;
 739	return err;
 740}
 741
 742static int
 743iter_prepare_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
 744{
 745	struct branch_info *bi;
 746	struct perf_sample *sample = iter->sample;
 747
 748	bi = sample__resolve_bstack(sample, al);
 749	if (!bi)
 750		return -ENOMEM;
 751
 752	iter->curr = 0;
 753	iter->total = sample->branch_stack->nr;
 754
 755	iter->priv = bi;
 756	return 0;
 757}
 758
 759static int
 760iter_add_single_branch_entry(struct hist_entry_iter *iter __maybe_unused,
 761			     struct addr_location *al __maybe_unused)
 762{
 763	return 0;
 764}
 765
 766static int
 767iter_next_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
 768{
 769	struct branch_info *bi = iter->priv;
 770	int i = iter->curr;
 771
 772	if (bi == NULL)
 773		return 0;
 774
 775	if (iter->curr >= iter->total)
 776		return 0;
 777
 778	al->map = bi[i].to.map;
 779	al->sym = bi[i].to.sym;
 780	al->addr = bi[i].to.addr;
 781	return 1;
 782}
 783
 784static int
 785iter_add_next_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
 786{
 787	struct branch_info *bi;
 788	struct perf_evsel *evsel = iter->evsel;
 789	struct hists *hists = evsel__hists(evsel);
 790	struct perf_sample *sample = iter->sample;
 791	struct hist_entry *he = NULL;
 792	int i = iter->curr;
 793	int err = 0;
 794
 795	bi = iter->priv;
 796
 797	if (iter->hide_unresolved && !(bi[i].from.sym && bi[i].to.sym))
 798		goto out;
 799
 800	/*
 801	 * The report shows the percentage of total branches captured
 802	 * and not events sampled. Thus we use a pseudo period of 1.
 803	 */
 804	sample->period = 1;
 805	sample->weight = bi->flags.cycles ? bi->flags.cycles : 1;
 806
 807	he = hists__add_entry(hists, al, iter->parent, &bi[i], NULL,
 808			      sample, true);
 809	if (he == NULL)
 810		return -ENOMEM;
 811
 812	hists__inc_nr_samples(hists, he->filtered);
 813
 814out:
 815	iter->he = he;
 816	iter->curr++;
 817	return err;
 818}
 819
 820static int
 821iter_finish_branch_entry(struct hist_entry_iter *iter,
 822			 struct addr_location *al __maybe_unused)
 823{
 824	zfree(&iter->priv);
 825	iter->he = NULL;
 826
 827	return iter->curr >= iter->total ? 0 : -1;
 828}
 829
 830static int
 831iter_prepare_normal_entry(struct hist_entry_iter *iter __maybe_unused,
 832			  struct addr_location *al __maybe_unused)
 833{
 834	return 0;
 835}
 836
 837static int
 838iter_add_single_normal_entry(struct hist_entry_iter *iter, struct addr_location *al)
 839{
 840	struct perf_evsel *evsel = iter->evsel;
 841	struct perf_sample *sample = iter->sample;
 842	struct hist_entry *he;
 843
 844	he = hists__add_entry(evsel__hists(evsel), al, iter->parent, NULL, NULL,
 845			      sample, true);
 846	if (he == NULL)
 847		return -ENOMEM;
 848
 849	iter->he = he;
 850	return 0;
 851}
 852
 853static int
 854iter_finish_normal_entry(struct hist_entry_iter *iter,
 855			 struct addr_location *al __maybe_unused)
 856{
 857	struct hist_entry *he = iter->he;
 858	struct perf_evsel *evsel = iter->evsel;
 859	struct perf_sample *sample = iter->sample;
 860
 861	if (he == NULL)
 862		return 0;
 863
 864	iter->he = NULL;
 865
 866	hists__inc_nr_samples(evsel__hists(evsel), he->filtered);
 867
 868	return hist_entry__append_callchain(he, sample);
 869}
 870
 871static int
 872iter_prepare_cumulative_entry(struct hist_entry_iter *iter,
 873			      struct addr_location *al __maybe_unused)
 874{
 875	struct hist_entry **he_cache;
 876
 877	callchain_cursor_commit(&callchain_cursor);
 878
 879	/*
 880	 * This is for detecting cycles or recursions so that they're
 881	 * cumulated only one time to prevent entries more than 100%
 882	 * overhead.
 883	 */
 884	he_cache = malloc(sizeof(*he_cache) * (callchain_cursor.nr + 1));
 885	if (he_cache == NULL)
 886		return -ENOMEM;
 887
 888	iter->priv = he_cache;
 889	iter->curr = 0;
 890
 891	return 0;
 892}
 893
 894static int
 895iter_add_single_cumulative_entry(struct hist_entry_iter *iter,
 896				 struct addr_location *al)
 897{
 898	struct perf_evsel *evsel = iter->evsel;
 899	struct hists *hists = evsel__hists(evsel);
 900	struct perf_sample *sample = iter->sample;
 901	struct hist_entry **he_cache = iter->priv;
 902	struct hist_entry *he;
 903	int err = 0;
 904
 905	he = hists__add_entry(hists, al, iter->parent, NULL, NULL,
 906			      sample, true);
 907	if (he == NULL)
 908		return -ENOMEM;
 909
 910	iter->he = he;
 911	he_cache[iter->curr++] = he;
 912
 913	hist_entry__append_callchain(he, sample);
 914
 915	/*
 916	 * We need to re-initialize the cursor since callchain_append()
 917	 * advanced the cursor to the end.
 918	 */
 919	callchain_cursor_commit(&callchain_cursor);
 920
 921	hists__inc_nr_samples(hists, he->filtered);
 922
 923	return err;
 924}
 925
 926static int
 927iter_next_cumulative_entry(struct hist_entry_iter *iter,
 928			   struct addr_location *al)
 929{
 930	struct callchain_cursor_node *node;
 931
 932	node = callchain_cursor_current(&callchain_cursor);
 933	if (node == NULL)
 934		return 0;
 935
 936	return fill_callchain_info(al, node, iter->hide_unresolved);
 937}
 938
 939static int
 940iter_add_next_cumulative_entry(struct hist_entry_iter *iter,
 941			       struct addr_location *al)
 942{
 943	struct perf_evsel *evsel = iter->evsel;
 944	struct perf_sample *sample = iter->sample;
 945	struct hist_entry **he_cache = iter->priv;
 946	struct hist_entry *he;
 947	struct hist_entry he_tmp = {
 948		.hists = evsel__hists(evsel),
 949		.cpu = al->cpu,
 950		.thread = al->thread,
 951		.comm = thread__comm(al->thread),
 952		.ip = al->addr,
 953		.ms = {
 954			.map = al->map,
 955			.sym = al->sym,
 956		},
 957		.srcline = al->srcline ? strdup(al->srcline) : NULL,
 958		.parent = iter->parent,
 959		.raw_data = sample->raw_data,
 960		.raw_size = sample->raw_size,
 961	};
 962	int i;
 963	struct callchain_cursor cursor;
 964
 965	callchain_cursor_snapshot(&cursor, &callchain_cursor);
 966
 967	callchain_cursor_advance(&callchain_cursor);
 968
 969	/*
 970	 * Check if there's duplicate entries in the callchain.
 971	 * It's possible that it has cycles or recursive calls.
 972	 */
 973	for (i = 0; i < iter->curr; i++) {
 974		if (hist_entry__cmp(he_cache[i], &he_tmp) == 0) {
 975			/* to avoid calling callback function */
 976			iter->he = NULL;
 977			return 0;
 978		}
 979	}
 980
 981	he = hists__add_entry(evsel__hists(evsel), al, iter->parent, NULL, NULL,
 982			      sample, false);
 983	if (he == NULL)
 984		return -ENOMEM;
 985
 986	iter->he = he;
 987	he_cache[iter->curr++] = he;
 988
 989	if (symbol_conf.use_callchain)
 990		callchain_append(he->callchain, &cursor, sample->period);
 991	return 0;
 992}
 993
 994static int
 995iter_finish_cumulative_entry(struct hist_entry_iter *iter,
 996			     struct addr_location *al __maybe_unused)
 997{
 998	zfree(&iter->priv);
 999	iter->he = NULL;
1000
1001	return 0;
1002}
1003
1004const struct hist_iter_ops hist_iter_mem = {
1005	.prepare_entry 		= iter_prepare_mem_entry,
1006	.add_single_entry 	= iter_add_single_mem_entry,
1007	.next_entry 		= iter_next_nop_entry,
1008	.add_next_entry 	= iter_add_next_nop_entry,
1009	.finish_entry 		= iter_finish_mem_entry,
1010};
1011
1012const struct hist_iter_ops hist_iter_branch = {
1013	.prepare_entry 		= iter_prepare_branch_entry,
1014	.add_single_entry 	= iter_add_single_branch_entry,
1015	.next_entry 		= iter_next_branch_entry,
1016	.add_next_entry 	= iter_add_next_branch_entry,
1017	.finish_entry 		= iter_finish_branch_entry,
1018};
1019
1020const struct hist_iter_ops hist_iter_normal = {
1021	.prepare_entry 		= iter_prepare_normal_entry,
1022	.add_single_entry 	= iter_add_single_normal_entry,
1023	.next_entry 		= iter_next_nop_entry,
1024	.add_next_entry 	= iter_add_next_nop_entry,
1025	.finish_entry 		= iter_finish_normal_entry,
1026};
1027
1028const struct hist_iter_ops hist_iter_cumulative = {
1029	.prepare_entry 		= iter_prepare_cumulative_entry,
1030	.add_single_entry 	= iter_add_single_cumulative_entry,
1031	.next_entry 		= iter_next_cumulative_entry,
1032	.add_next_entry 	= iter_add_next_cumulative_entry,
1033	.finish_entry 		= iter_finish_cumulative_entry,
1034};
1035
1036int hist_entry_iter__add(struct hist_entry_iter *iter, struct addr_location *al,
1037			 int max_stack_depth, void *arg)
1038{
1039	int err, err2;
1040	struct map *alm = NULL;
1041
1042	if (al && al->map)
1043		alm = map__get(al->map);
1044
1045	err = sample__resolve_callchain(iter->sample, &callchain_cursor, &iter->parent,
1046					iter->evsel, al, max_stack_depth);
1047	if (err)
1048		return err;
1049
1050	err = iter->ops->prepare_entry(iter, al);
1051	if (err)
1052		goto out;
1053
1054	err = iter->ops->add_single_entry(iter, al);
1055	if (err)
1056		goto out;
1057
1058	if (iter->he && iter->add_entry_cb) {
1059		err = iter->add_entry_cb(iter, al, true, arg);
1060		if (err)
1061			goto out;
1062	}
1063
1064	while (iter->ops->next_entry(iter, al)) {
1065		err = iter->ops->add_next_entry(iter, al);
1066		if (err)
1067			break;
1068
1069		if (iter->he && iter->add_entry_cb) {
1070			err = iter->add_entry_cb(iter, al, false, arg);
1071			if (err)
1072				goto out;
1073		}
1074	}
1075
1076out:
1077	err2 = iter->ops->finish_entry(iter, al);
1078	if (!err)
1079		err = err2;
1080
1081	map__put(alm);
1082
1083	return err;
1084}
1085
1086int64_t
1087hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
1088{
1089	struct hists *hists = left->hists;
1090	struct perf_hpp_fmt *fmt;
1091	int64_t cmp = 0;
1092
1093	hists__for_each_sort_list(hists, fmt) {
1094		if (perf_hpp__is_dynamic_entry(fmt) &&
1095		    !perf_hpp__defined_dynamic_entry(fmt, hists))
1096			continue;
1097
1098		cmp = fmt->cmp(fmt, left, right);
1099		if (cmp)
1100			break;
1101	}
1102
1103	return cmp;
1104}
1105
1106int64_t
1107hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
1108{
1109	struct hists *hists = left->hists;
1110	struct perf_hpp_fmt *fmt;
1111	int64_t cmp = 0;
1112
1113	hists__for_each_sort_list(hists, fmt) {
1114		if (perf_hpp__is_dynamic_entry(fmt) &&
1115		    !perf_hpp__defined_dynamic_entry(fmt, hists))
1116			continue;
1117
1118		cmp = fmt->collapse(fmt, left, right);
 
 
1119		if (cmp)
1120			break;
1121	}
1122
1123	return cmp;
1124}
1125
1126void hist_entry__delete(struct hist_entry *he)
1127{
1128	struct hist_entry_ops *ops = he->ops;
1129
1130	thread__zput(he->thread);
1131	map__zput(he->ms.map);
1132
1133	if (he->branch_info) {
1134		map__zput(he->branch_info->from.map);
1135		map__zput(he->branch_info->to.map);
1136		free_srcline(he->branch_info->srcline_from);
1137		free_srcline(he->branch_info->srcline_to);
1138		zfree(&he->branch_info);
1139	}
1140
1141	if (he->mem_info) {
1142		map__zput(he->mem_info->iaddr.map);
1143		map__zput(he->mem_info->daddr.map);
1144		mem_info__zput(he->mem_info);
1145	}
1146
1147	zfree(&he->stat_acc);
1148	free_srcline(he->srcline);
1149	if (he->srcfile && he->srcfile[0])
1150		free(he->srcfile);
1151	free_callchain(he->callchain);
1152	free(he->trace_output);
1153	free(he->raw_data);
1154	ops->free(he);
1155}
1156
1157/*
1158 * If this is not the last column, then we need to pad it according to the
1159 * pre-calculated max lenght for this column, otherwise don't bother adding
1160 * spaces because that would break viewing this with, for instance, 'less',
1161 * that would show tons of trailing spaces when a long C++ demangled method
1162 * names is sampled.
1163*/
1164int hist_entry__snprintf_alignment(struct hist_entry *he, struct perf_hpp *hpp,
1165				   struct perf_hpp_fmt *fmt, int printed)
1166{
1167	if (!list_is_last(&fmt->list, &he->hists->hpp_list->fields)) {
1168		const int width = fmt->width(fmt, hpp, he->hists);
1169		if (printed < width) {
1170			advance_hpp(hpp, printed);
1171			printed = scnprintf(hpp->buf, hpp->size, "%-*s", width - printed, " ");
1172		}
1173	}
1174
1175	return printed;
1176}
1177
1178/*
1179 * collapse the histogram
1180 */
1181
1182static void hists__apply_filters(struct hists *hists, struct hist_entry *he);
1183static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *he,
1184				       enum hist_filter type);
1185
1186typedef bool (*fmt_chk_fn)(struct perf_hpp_fmt *fmt);
1187
1188static bool check_thread_entry(struct perf_hpp_fmt *fmt)
1189{
1190	return perf_hpp__is_thread_entry(fmt) || perf_hpp__is_comm_entry(fmt);
1191}
1192
1193static void hist_entry__check_and_remove_filter(struct hist_entry *he,
1194						enum hist_filter type,
1195						fmt_chk_fn check)
1196{
1197	struct perf_hpp_fmt *fmt;
1198	bool type_match = false;
1199	struct hist_entry *parent = he->parent_he;
1200
1201	switch (type) {
1202	case HIST_FILTER__THREAD:
1203		if (symbol_conf.comm_list == NULL &&
1204		    symbol_conf.pid_list == NULL &&
1205		    symbol_conf.tid_list == NULL)
1206			return;
1207		break;
1208	case HIST_FILTER__DSO:
1209		if (symbol_conf.dso_list == NULL)
1210			return;
1211		break;
1212	case HIST_FILTER__SYMBOL:
1213		if (symbol_conf.sym_list == NULL)
1214			return;
1215		break;
1216	case HIST_FILTER__PARENT:
1217	case HIST_FILTER__GUEST:
1218	case HIST_FILTER__HOST:
1219	case HIST_FILTER__SOCKET:
1220	case HIST_FILTER__C2C:
1221	default:
1222		return;
1223	}
1224
1225	/* if it's filtered by own fmt, it has to have filter bits */
1226	perf_hpp_list__for_each_format(he->hpp_list, fmt) {
1227		if (check(fmt)) {
1228			type_match = true;
1229			break;
1230		}
1231	}
1232
1233	if (type_match) {
1234		/*
1235		 * If the filter is for current level entry, propagate
1236		 * filter marker to parents.  The marker bit was
1237		 * already set by default so it only needs to clear
1238		 * non-filtered entries.
1239		 */
1240		if (!(he->filtered & (1 << type))) {
1241			while (parent) {
1242				parent->filtered &= ~(1 << type);
1243				parent = parent->parent_he;
1244			}
1245		}
1246	} else {
1247		/*
1248		 * If current entry doesn't have matching formats, set
1249		 * filter marker for upper level entries.  it will be
1250		 * cleared if its lower level entries is not filtered.
1251		 *
1252		 * For lower-level entries, it inherits parent's
1253		 * filter bit so that lower level entries of a
1254		 * non-filtered entry won't set the filter marker.
1255		 */
1256		if (parent == NULL)
1257			he->filtered |= (1 << type);
1258		else
1259			he->filtered |= (parent->filtered & (1 << type));
1260	}
1261}
1262
1263static void hist_entry__apply_hierarchy_filters(struct hist_entry *he)
1264{
1265	hist_entry__check_and_remove_filter(he, HIST_FILTER__THREAD,
1266					    check_thread_entry);
1267
1268	hist_entry__check_and_remove_filter(he, HIST_FILTER__DSO,
1269					    perf_hpp__is_dso_entry);
1270
1271	hist_entry__check_and_remove_filter(he, HIST_FILTER__SYMBOL,
1272					    perf_hpp__is_sym_entry);
1273
1274	hists__apply_filters(he->hists, he);
1275}
1276
1277static struct hist_entry *hierarchy_insert_entry(struct hists *hists,
1278						 struct rb_root *root,
1279						 struct hist_entry *he,
1280						 struct hist_entry *parent_he,
1281						 struct perf_hpp_list *hpp_list)
1282{
1283	struct rb_node **p = &root->rb_node;
1284	struct rb_node *parent = NULL;
1285	struct hist_entry *iter, *new;
1286	struct perf_hpp_fmt *fmt;
1287	int64_t cmp;
1288
1289	while (*p != NULL) {
1290		parent = *p;
1291		iter = rb_entry(parent, struct hist_entry, rb_node_in);
1292
1293		cmp = 0;
1294		perf_hpp_list__for_each_sort_list(hpp_list, fmt) {
1295			cmp = fmt->collapse(fmt, iter, he);
1296			if (cmp)
1297				break;
1298		}
1299
1300		if (!cmp) {
1301			he_stat__add_stat(&iter->stat, &he->stat);
1302			return iter;
1303		}
1304
1305		if (cmp < 0)
1306			p = &parent->rb_left;
1307		else
1308			p = &parent->rb_right;
1309	}
1310
1311	new = hist_entry__new(he, true);
1312	if (new == NULL)
1313		return NULL;
1314
1315	hists->nr_entries++;
1316
1317	/* save related format list for output */
1318	new->hpp_list = hpp_list;
1319	new->parent_he = parent_he;
1320
1321	hist_entry__apply_hierarchy_filters(new);
1322
1323	/* some fields are now passed to 'new' */
1324	perf_hpp_list__for_each_sort_list(hpp_list, fmt) {
1325		if (perf_hpp__is_trace_entry(fmt) || perf_hpp__is_dynamic_entry(fmt))
1326			he->trace_output = NULL;
1327		else
1328			new->trace_output = NULL;
1329
1330		if (perf_hpp__is_srcline_entry(fmt))
1331			he->srcline = NULL;
1332		else
1333			new->srcline = NULL;
1334
1335		if (perf_hpp__is_srcfile_entry(fmt))
1336			he->srcfile = NULL;
1337		else
1338			new->srcfile = NULL;
1339	}
1340
1341	rb_link_node(&new->rb_node_in, parent, p);
1342	rb_insert_color(&new->rb_node_in, root);
1343	return new;
1344}
1345
1346static int hists__hierarchy_insert_entry(struct hists *hists,
1347					 struct rb_root *root,
1348					 struct hist_entry *he)
1349{
1350	struct perf_hpp_list_node *node;
1351	struct hist_entry *new_he = NULL;
1352	struct hist_entry *parent = NULL;
1353	int depth = 0;
1354	int ret = 0;
1355
1356	list_for_each_entry(node, &hists->hpp_formats, list) {
1357		/* skip period (overhead) and elided columns */
1358		if (node->level == 0 || node->skip)
1359			continue;
1360
1361		/* insert copy of 'he' for each fmt into the hierarchy */
1362		new_he = hierarchy_insert_entry(hists, root, he, parent, &node->hpp);
1363		if (new_he == NULL) {
1364			ret = -1;
1365			break;
1366		}
1367
1368		root = &new_he->hroot_in;
1369		new_he->depth = depth++;
1370		parent = new_he;
1371	}
1372
1373	if (new_he) {
1374		new_he->leaf = true;
1375
1376		if (symbol_conf.use_callchain) {
1377			callchain_cursor_reset(&callchain_cursor);
1378			if (callchain_merge(&callchain_cursor,
1379					    new_he->callchain,
1380					    he->callchain) < 0)
1381				ret = -1;
1382		}
1383	}
1384
1385	/* 'he' is no longer used */
1386	hist_entry__delete(he);
1387
1388	/* return 0 (or -1) since it already applied filters */
1389	return ret;
1390}
1391
1392static int hists__collapse_insert_entry(struct hists *hists,
1393					struct rb_root *root,
1394					struct hist_entry *he)
1395{
1396	struct rb_node **p = &root->rb_node;
1397	struct rb_node *parent = NULL;
1398	struct hist_entry *iter;
1399	int64_t cmp;
1400
1401	if (symbol_conf.report_hierarchy)
1402		return hists__hierarchy_insert_entry(hists, root, he);
1403
1404	while (*p != NULL) {
1405		parent = *p;
1406		iter = rb_entry(parent, struct hist_entry, rb_node_in);
1407
1408		cmp = hist_entry__collapse(iter, he);
1409
1410		if (!cmp) {
1411			int ret = 0;
1412
1413			he_stat__add_stat(&iter->stat, &he->stat);
1414			if (symbol_conf.cumulate_callchain)
1415				he_stat__add_stat(iter->stat_acc, he->stat_acc);
1416
1417			if (symbol_conf.use_callchain) {
1418				callchain_cursor_reset(&callchain_cursor);
1419				if (callchain_merge(&callchain_cursor,
1420						    iter->callchain,
1421						    he->callchain) < 0)
1422					ret = -1;
1423			}
1424			hist_entry__delete(he);
1425			return ret;
1426		}
1427
1428		if (cmp < 0)
1429			p = &(*p)->rb_left;
1430		else
1431			p = &(*p)->rb_right;
1432	}
1433	hists->nr_entries++;
1434
1435	rb_link_node(&he->rb_node_in, parent, p);
1436	rb_insert_color(&he->rb_node_in, root);
1437	return 1;
1438}
1439
1440struct rb_root *hists__get_rotate_entries_in(struct hists *hists)
1441{
1442	struct rb_root *root;
1443
1444	pthread_mutex_lock(&hists->lock);
1445
1446	root = hists->entries_in;
1447	if (++hists->entries_in > &hists->entries_in_array[1])
1448		hists->entries_in = &hists->entries_in_array[0];
1449
1450	pthread_mutex_unlock(&hists->lock);
1451
1452	return root;
1453}
1454
1455static void hists__apply_filters(struct hists *hists, struct hist_entry *he)
1456{
1457	hists__filter_entry_by_dso(hists, he);
1458	hists__filter_entry_by_thread(hists, he);
1459	hists__filter_entry_by_symbol(hists, he);
1460	hists__filter_entry_by_socket(hists, he);
1461}
1462
1463int hists__collapse_resort(struct hists *hists, struct ui_progress *prog)
1464{
1465	struct rb_root *root;
1466	struct rb_node *next;
1467	struct hist_entry *n;
1468	int ret;
1469
1470	if (!hists__has(hists, need_collapse))
1471		return 0;
1472
1473	hists->nr_entries = 0;
1474
1475	root = hists__get_rotate_entries_in(hists);
 
1476
1477	next = rb_first(root);
 
 
 
1478
1479	while (next) {
1480		if (session_done())
1481			break;
1482		n = rb_entry(next, struct hist_entry, rb_node_in);
1483		next = rb_next(&n->rb_node_in);
1484
1485		rb_erase(&n->rb_node_in, root);
1486		ret = hists__collapse_insert_entry(hists, &hists->entries_collapsed, n);
1487		if (ret < 0)
1488			return -1;
1489
1490		if (ret) {
1491			/*
1492			 * If it wasn't combined with one of the entries already
1493			 * collapsed, we need to apply the filters that may have
1494			 * been set by, say, the hist_browser.
1495			 */
1496			hists__apply_filters(hists, n);
1497		}
1498		if (prog)
1499			ui_progress__update(prog, 1);
1500	}
1501	return 0;
1502}
1503
1504static int hist_entry__sort(struct hist_entry *a, struct hist_entry *b)
1505{
1506	struct hists *hists = a->hists;
1507	struct perf_hpp_fmt *fmt;
1508	int64_t cmp = 0;
1509
1510	hists__for_each_sort_list(hists, fmt) {
1511		if (perf_hpp__should_skip(fmt, a->hists))
1512			continue;
1513
1514		cmp = fmt->sort(fmt, a, b);
1515		if (cmp)
1516			break;
1517	}
1518
1519	return cmp;
1520}
1521
1522static void hists__reset_filter_stats(struct hists *hists)
1523{
1524	hists->nr_non_filtered_entries = 0;
1525	hists->stats.total_non_filtered_period = 0;
1526}
1527
1528void hists__reset_stats(struct hists *hists)
1529{
1530	hists->nr_entries = 0;
1531	hists->stats.total_period = 0;
1532
1533	hists__reset_filter_stats(hists);
1534}
1535
1536static void hists__inc_filter_stats(struct hists *hists, struct hist_entry *h)
1537{
1538	hists->nr_non_filtered_entries++;
1539	hists->stats.total_non_filtered_period += h->stat.period;
1540}
1541
1542void hists__inc_stats(struct hists *hists, struct hist_entry *h)
1543{
1544	if (!h->filtered)
1545		hists__inc_filter_stats(hists, h);
1546
1547	hists->nr_entries++;
1548	hists->stats.total_period += h->stat.period;
1549}
1550
1551static void hierarchy_recalc_total_periods(struct hists *hists)
1552{
1553	struct rb_node *node;
1554	struct hist_entry *he;
1555
1556	node = rb_first(&hists->entries);
1557
1558	hists->stats.total_period = 0;
1559	hists->stats.total_non_filtered_period = 0;
1560
1561	/*
1562	 * recalculate total period using top-level entries only
1563	 * since lower level entries only see non-filtered entries
1564	 * but upper level entries have sum of both entries.
1565	 */
1566	while (node) {
1567		he = rb_entry(node, struct hist_entry, rb_node);
1568		node = rb_next(node);
1569
1570		hists->stats.total_period += he->stat.period;
1571		if (!he->filtered)
1572			hists->stats.total_non_filtered_period += he->stat.period;
1573	}
1574}
1575
1576static void hierarchy_insert_output_entry(struct rb_root *root,
1577					  struct hist_entry *he)
1578{
1579	struct rb_node **p = &root->rb_node;
1580	struct rb_node *parent = NULL;
1581	struct hist_entry *iter;
1582	struct perf_hpp_fmt *fmt;
1583
1584	while (*p != NULL) {
1585		parent = *p;
1586		iter = rb_entry(parent, struct hist_entry, rb_node);
1587
1588		if (hist_entry__sort(he, iter) > 0)
1589			p = &parent->rb_left;
1590		else
1591			p = &parent->rb_right;
1592	}
1593
1594	rb_link_node(&he->rb_node, parent, p);
1595	rb_insert_color(&he->rb_node, root);
1596
1597	/* update column width of dynamic entry */
1598	perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
1599		if (perf_hpp__is_dynamic_entry(fmt))
1600			fmt->sort(fmt, he, NULL);
1601	}
1602}
1603
1604static void hists__hierarchy_output_resort(struct hists *hists,
1605					   struct ui_progress *prog,
1606					   struct rb_root *root_in,
1607					   struct rb_root *root_out,
1608					   u64 min_callchain_hits,
1609					   bool use_callchain)
1610{
1611	struct rb_node *node;
1612	struct hist_entry *he;
1613
1614	*root_out = RB_ROOT;
1615	node = rb_first(root_in);
1616
1617	while (node) {
1618		he = rb_entry(node, struct hist_entry, rb_node_in);
1619		node = rb_next(node);
1620
1621		hierarchy_insert_output_entry(root_out, he);
1622
1623		if (prog)
1624			ui_progress__update(prog, 1);
1625
1626		hists->nr_entries++;
1627		if (!he->filtered) {
1628			hists->nr_non_filtered_entries++;
1629			hists__calc_col_len(hists, he);
1630		}
1631
1632		if (!he->leaf) {
1633			hists__hierarchy_output_resort(hists, prog,
1634						       &he->hroot_in,
1635						       &he->hroot_out,
1636						       min_callchain_hits,
1637						       use_callchain);
1638			continue;
1639		}
1640
1641		if (!use_callchain)
1642			continue;
1643
1644		if (callchain_param.mode == CHAIN_GRAPH_REL) {
1645			u64 total = he->stat.period;
1646
1647			if (symbol_conf.cumulate_callchain)
1648				total = he->stat_acc->period;
1649
1650			min_callchain_hits = total * (callchain_param.min_percent / 100);
1651		}
1652
1653		callchain_param.sort(&he->sorted_chain, he->callchain,
1654				     min_callchain_hits, &callchain_param);
1655	}
1656}
1657
1658static void __hists__insert_output_entry(struct rb_root *entries,
1659					 struct hist_entry *he,
1660					 u64 min_callchain_hits,
1661					 bool use_callchain)
1662{
1663	struct rb_node **p = &entries->rb_node;
1664	struct rb_node *parent = NULL;
1665	struct hist_entry *iter;
1666	struct perf_hpp_fmt *fmt;
1667
1668	if (use_callchain) {
1669		if (callchain_param.mode == CHAIN_GRAPH_REL) {
1670			u64 total = he->stat.period;
1671
1672			if (symbol_conf.cumulate_callchain)
1673				total = he->stat_acc->period;
1674
1675			min_callchain_hits = total * (callchain_param.min_percent / 100);
1676		}
1677		callchain_param.sort(&he->sorted_chain, he->callchain,
1678				      min_callchain_hits, &callchain_param);
1679	}
1680
1681	while (*p != NULL) {
1682		parent = *p;
1683		iter = rb_entry(parent, struct hist_entry, rb_node);
1684
1685		if (hist_entry__sort(he, iter) > 0)
1686			p = &(*p)->rb_left;
1687		else
1688			p = &(*p)->rb_right;
1689	}
1690
1691	rb_link_node(&he->rb_node, parent, p);
1692	rb_insert_color(&he->rb_node, entries);
1693
1694	perf_hpp_list__for_each_sort_list(&perf_hpp_list, fmt) {
1695		if (perf_hpp__is_dynamic_entry(fmt) &&
1696		    perf_hpp__defined_dynamic_entry(fmt, he->hists))
1697			fmt->sort(fmt, he, NULL);  /* update column width */
1698	}
1699}
1700
1701static void output_resort(struct hists *hists, struct ui_progress *prog,
1702			  bool use_callchain, hists__resort_cb_t cb)
1703{
1704	struct rb_root *root;
1705	struct rb_node *next;
1706	struct hist_entry *n;
1707	u64 callchain_total;
1708	u64 min_callchain_hits;
1709
1710	callchain_total = hists->callchain_period;
1711	if (symbol_conf.filter_relative)
1712		callchain_total = hists->callchain_non_filtered_period;
1713
1714	min_callchain_hits = callchain_total * (callchain_param.min_percent / 100);
1715
1716	hists__reset_stats(hists);
1717	hists__reset_col_len(hists);
1718
1719	if (symbol_conf.report_hierarchy) {
1720		hists__hierarchy_output_resort(hists, prog,
1721					       &hists->entries_collapsed,
1722					       &hists->entries,
1723					       min_callchain_hits,
1724					       use_callchain);
1725		hierarchy_recalc_total_periods(hists);
1726		return;
1727	}
1728
1729	if (hists__has(hists, need_collapse))
1730		root = &hists->entries_collapsed;
1731	else
1732		root = hists->entries_in;
1733
1734	next = rb_first(root);
1735	hists->entries = RB_ROOT;
1736
1737	while (next) {
1738		n = rb_entry(next, struct hist_entry, rb_node_in);
1739		next = rb_next(&n->rb_node_in);
1740
1741		if (cb && cb(n))
1742			continue;
1743
1744		__hists__insert_output_entry(&hists->entries, n, min_callchain_hits, use_callchain);
1745		hists__inc_stats(hists, n);
1746
1747		if (!n->filtered)
1748			hists__calc_col_len(hists, n);
1749
1750		if (prog)
1751			ui_progress__update(prog, 1);
 
1752	}
 
 
1753}
1754
1755void perf_evsel__output_resort(struct perf_evsel *evsel, struct ui_progress *prog)
1756{
1757	bool use_callchain;
1758
1759	if (evsel && symbol_conf.use_callchain && !symbol_conf.show_ref_callgraph)
1760		use_callchain = evsel->attr.sample_type & PERF_SAMPLE_CALLCHAIN;
1761	else
1762		use_callchain = symbol_conf.use_callchain;
1763
1764	use_callchain |= symbol_conf.show_branchflag_count;
 
1765
1766	output_resort(evsel__hists(evsel), prog, use_callchain, NULL);
1767}
1768
1769void hists__output_resort(struct hists *hists, struct ui_progress *prog)
1770{
1771	output_resort(hists, prog, symbol_conf.use_callchain, NULL);
1772}
1773
1774void hists__output_resort_cb(struct hists *hists, struct ui_progress *prog,
1775			     hists__resort_cb_t cb)
1776{
1777	output_resort(hists, prog, symbol_conf.use_callchain, cb);
1778}
1779
1780static bool can_goto_child(struct hist_entry *he, enum hierarchy_move_dir hmd)
1781{
1782	if (he->leaf || hmd == HMD_FORCE_SIBLING)
1783		return false;
 
1784
1785	if (he->unfolded || hmd == HMD_FORCE_CHILD)
1786		return true;
1787
1788	return false;
1789}
1790
1791struct rb_node *rb_hierarchy_last(struct rb_node *node)
 
 
 
1792{
1793	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
 
1794
1795	while (can_goto_child(he, HMD_NORMAL)) {
1796		node = rb_last(&he->hroot_out);
1797		he = rb_entry(node, struct hist_entry, rb_node);
 
 
 
 
 
 
 
 
 
 
1798	}
1799	return node;
1800}
1801
1802struct rb_node *__rb_hierarchy_next(struct rb_node *node, enum hierarchy_move_dir hmd)
1803{
1804	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
1805
1806	if (can_goto_child(he, hmd))
1807		node = rb_first(&he->hroot_out);
1808	else
1809		node = rb_next(node);
1810
1811	while (node == NULL) {
1812		he = he->parent_he;
1813		if (he == NULL)
1814			break;
1815
1816		node = rb_next(&he->rb_node);
1817	}
1818	return node;
1819}
1820
1821struct rb_node *rb_hierarchy_prev(struct rb_node *node)
1822{
1823	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
1824
1825	node = rb_prev(node);
1826	if (node)
1827		return rb_hierarchy_last(node);
1828
1829	he = he->parent_he;
1830	if (he == NULL)
1831		return NULL;
1832
1833	return &he->rb_node;
1834}
1835
1836bool hist_entry__has_hierarchy_children(struct hist_entry *he, float limit)
1837{
1838	struct rb_node *node;
1839	struct hist_entry *child;
1840	float percent;
1841
1842	if (he->leaf)
1843		return false;
1844
1845	node = rb_first(&he->hroot_out);
1846	child = rb_entry(node, struct hist_entry, rb_node);
1847
1848	while (node && child->filtered) {
1849		node = rb_next(node);
1850		child = rb_entry(node, struct hist_entry, rb_node);
1851	}
1852
1853	if (node)
1854		percent = hist_entry__get_percent_limit(child);
1855	else
1856		percent = 0;
1857
1858	return node && percent >= limit;
1859}
1860
1861static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
1862				       enum hist_filter filter)
1863{
1864	h->filtered &= ~(1 << filter);
 
 
 
 
 
 
 
 
 
1865
1866	if (symbol_conf.report_hierarchy) {
1867		struct hist_entry *parent = h->parent_he;
 
 
1868
1869		while (parent) {
1870			he_stat__add_stat(&parent->stat, &h->stat);
1871
1872			parent->filtered &= ~(1 << filter);
 
 
1873
1874			if (parent->filtered)
1875				goto next;
1876
1877			/* force fold unfiltered entry for simplicity */
1878			parent->unfolded = false;
1879			parent->has_no_entry = false;
1880			parent->row_offset = 0;
1881			parent->nr_rows = 0;
1882next:
1883			parent = parent->parent_he;
1884		}
1885	}
1886
1887	if (h->filtered)
1888		return;
 
 
 
 
 
 
 
 
1889
1890	/* force fold unfiltered entry for simplicity */
1891	h->unfolded = false;
1892	h->has_no_entry = false;
1893	h->row_offset = 0;
1894	h->nr_rows = 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1895
1896	hists->stats.nr_non_filtered_samples += h->stat.nr_events;
 
1897
1898	hists__inc_filter_stats(hists, h);
1899	hists__calc_col_len(hists, h);
1900}
1901
 
1902
1903static bool hists__filter_entry_by_dso(struct hists *hists,
1904				       struct hist_entry *he)
1905{
1906	if (hists->dso_filter != NULL &&
1907	    (he->ms.map == NULL || he->ms.map->dso != hists->dso_filter)) {
1908		he->filtered |= (1 << HIST_FILTER__DSO);
1909		return true;
1910	}
1911
1912	return false;
1913}
1914
1915static bool hists__filter_entry_by_thread(struct hists *hists,
1916					  struct hist_entry *he)
1917{
1918	if (hists->thread_filter != NULL &&
1919	    he->thread != hists->thread_filter) {
1920		he->filtered |= (1 << HIST_FILTER__THREAD);
1921		return true;
1922	}
1923
1924	return false;
1925}
 
1926
1927static bool hists__filter_entry_by_symbol(struct hists *hists,
1928					  struct hist_entry *he)
1929{
1930	if (hists->symbol_filter_str != NULL &&
1931	    (!he->ms.sym || strstr(he->ms.sym->name,
1932				   hists->symbol_filter_str) == NULL)) {
1933		he->filtered |= (1 << HIST_FILTER__SYMBOL);
1934		return true;
1935	}
 
1936
1937	return false;
1938}
 
 
1939
1940static bool hists__filter_entry_by_socket(struct hists *hists,
1941					  struct hist_entry *he)
1942{
1943	if ((hists->socket_filter > -1) &&
1944	    (he->socket != hists->socket_filter)) {
1945		he->filtered |= (1 << HIST_FILTER__SOCKET);
1946		return true;
1947	}
1948
1949	return false;
1950}
1951
1952typedef bool (*filter_fn_t)(struct hists *hists, struct hist_entry *he);
 
1953
1954static void hists__filter_by_type(struct hists *hists, int type, filter_fn_t filter)
 
1955{
1956	struct rb_node *nd;
 
1957
1958	hists->stats.nr_non_filtered_samples = 0;
 
1959
1960	hists__reset_filter_stats(hists);
1961	hists__reset_col_len(hists);
1962
1963	for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
1964		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1965
1966		if (filter(hists, h))
 
1967			continue;
1968
1969		hists__remove_entry_filter(hists, h, type);
 
 
 
1970	}
 
 
1971}
1972
1973static void resort_filtered_entry(struct rb_root *root, struct hist_entry *he)
 
1974{
1975	struct rb_node **p = &root->rb_node;
1976	struct rb_node *parent = NULL;
1977	struct hist_entry *iter;
1978	struct rb_root new_root = RB_ROOT;
1979	struct rb_node *nd;
1980
1981	while (*p != NULL) {
1982		parent = *p;
1983		iter = rb_entry(parent, struct hist_entry, rb_node);
1984
1985		if (hist_entry__sort(he, iter) > 0)
1986			p = &(*p)->rb_left;
1987		else
1988			p = &(*p)->rb_right;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1989	}
1990
1991	rb_link_node(&he->rb_node, parent, p);
1992	rb_insert_color(&he->rb_node, root);
1993
1994	if (he->leaf || he->filtered)
1995		return;
 
 
 
 
 
 
 
 
1996
1997	nd = rb_first(&he->hroot_out);
1998	while (nd) {
1999		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2000
2001		nd = rb_next(nd);
2002		rb_erase(&h->rb_node, &he->hroot_out);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2003
2004		resort_filtered_entry(&new_root, h);
 
 
 
 
2005	}
2006
2007	he->hroot_out = new_root;
2008}
 
2009
2010static void hists__filter_hierarchy(struct hists *hists, int type, const void *arg)
2011{
2012	struct rb_node *nd;
2013	struct rb_root new_root = RB_ROOT;
2014
2015	hists->stats.nr_non_filtered_samples = 0;
2016
2017	hists__reset_filter_stats(hists);
2018	hists__reset_col_len(hists);
2019
2020	nd = rb_first(&hists->entries);
2021	while (nd) {
2022		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2023		int ret;
2024
2025		ret = hist_entry__filter(h, type, arg);
2026
2027		/*
2028		 * case 1. non-matching type
2029		 * zero out the period, set filter marker and move to child
2030		 */
2031		if (ret < 0) {
2032			memset(&h->stat, 0, sizeof(h->stat));
2033			h->filtered |= (1 << type);
2034
2035			nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_CHILD);
2036		}
2037		/*
2038		 * case 2. matched type (filter out)
2039		 * set filter marker and move to next
2040		 */
2041		else if (ret == 1) {
2042			h->filtered |= (1 << type);
2043
2044			nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_SIBLING);
2045		}
2046		/*
2047		 * case 3. ok (not filtered)
2048		 * add period to hists and parents, erase the filter marker
2049		 * and move to next sibling
2050		 */
2051		else {
2052			hists__remove_entry_filter(hists, h, type);
2053
2054			nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_SIBLING);
 
 
 
2055		}
2056	}
2057
2058	hierarchy_recalc_total_periods(hists);
2059
2060	/*
2061	 * resort output after applying a new filter since filter in a lower
2062	 * hierarchy can change periods in a upper hierarchy.
2063	 */
2064	nd = rb_first(&hists->entries);
2065	while (nd) {
2066		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2067
2068		nd = rb_next(nd);
2069		rb_erase(&h->rb_node, &hists->entries);
2070
2071		resort_filtered_entry(&new_root, h);
 
 
2072	}
2073
2074	hists->entries = new_root;
2075}
2076
2077void hists__filter_by_thread(struct hists *hists)
2078{
2079	if (symbol_conf.report_hierarchy)
2080		hists__filter_hierarchy(hists, HIST_FILTER__THREAD,
2081					hists->thread_filter);
2082	else
2083		hists__filter_by_type(hists, HIST_FILTER__THREAD,
2084				      hists__filter_entry_by_thread);
2085}
2086
2087void hists__filter_by_dso(struct hists *hists)
2088{
2089	if (symbol_conf.report_hierarchy)
2090		hists__filter_hierarchy(hists, HIST_FILTER__DSO,
2091					hists->dso_filter);
2092	else
2093		hists__filter_by_type(hists, HIST_FILTER__DSO,
2094				      hists__filter_entry_by_dso);
2095}
2096
2097void hists__filter_by_symbol(struct hists *hists)
2098{
2099	if (symbol_conf.report_hierarchy)
2100		hists__filter_hierarchy(hists, HIST_FILTER__SYMBOL,
2101					hists->symbol_filter_str);
2102	else
2103		hists__filter_by_type(hists, HIST_FILTER__SYMBOL,
2104				      hists__filter_entry_by_symbol);
2105}
2106
2107void hists__filter_by_socket(struct hists *hists)
2108{
2109	if (symbol_conf.report_hierarchy)
2110		hists__filter_hierarchy(hists, HIST_FILTER__SOCKET,
2111					&hists->socket_filter);
2112	else
2113		hists__filter_by_type(hists, HIST_FILTER__SOCKET,
2114				      hists__filter_entry_by_socket);
2115}
2116
2117void events_stats__inc(struct events_stats *stats, u32 type)
2118{
2119	++stats->nr_events[0];
2120	++stats->nr_events[type];
2121}
2122
2123void hists__inc_nr_events(struct hists *hists, u32 type)
2124{
2125	events_stats__inc(&hists->stats, type);
2126}
2127
2128void hists__inc_nr_samples(struct hists *hists, bool filtered)
 
 
2129{
2130	events_stats__inc(&hists->stats, PERF_RECORD_SAMPLE);
2131	if (!filtered)
2132		hists->stats.nr_non_filtered_samples++;
 
 
2133}
2134
2135static struct hist_entry *hists__add_dummy_entry(struct hists *hists,
2136						 struct hist_entry *pair)
 
2137{
2138	struct rb_root *root;
2139	struct rb_node **p;
2140	struct rb_node *parent = NULL;
2141	struct hist_entry *he;
2142	int64_t cmp;
2143
2144	if (hists__has(hists, need_collapse))
2145		root = &hists->entries_collapsed;
2146	else
2147		root = hists->entries_in;
2148
2149	p = &root->rb_node;
2150
2151	while (*p != NULL) {
2152		parent = *p;
2153		he = rb_entry(parent, struct hist_entry, rb_node_in);
2154
2155		cmp = hist_entry__collapse(he, pair);
2156
2157		if (!cmp)
2158			goto out;
2159
2160		if (cmp < 0)
2161			p = &(*p)->rb_left;
2162		else
2163			p = &(*p)->rb_right;
2164	}
2165
2166	he = hist_entry__new(pair, true);
2167	if (he) {
2168		memset(&he->stat, 0, sizeof(he->stat));
2169		he->hists = hists;
2170		if (symbol_conf.cumulate_callchain)
2171			memset(he->stat_acc, 0, sizeof(he->stat));
2172		rb_link_node(&he->rb_node_in, parent, p);
2173		rb_insert_color(&he->rb_node_in, root);
2174		hists__inc_stats(hists, he);
2175		he->dummy = true;
2176	}
2177out:
2178	return he;
2179}
2180
2181static struct hist_entry *add_dummy_hierarchy_entry(struct hists *hists,
2182						    struct rb_root *root,
2183						    struct hist_entry *pair)
2184{
2185	struct rb_node **p;
2186	struct rb_node *parent = NULL;
2187	struct hist_entry *he;
2188	struct perf_hpp_fmt *fmt;
2189
2190	p = &root->rb_node;
2191	while (*p != NULL) {
2192		int64_t cmp = 0;
2193
2194		parent = *p;
2195		he = rb_entry(parent, struct hist_entry, rb_node_in);
2196
2197		perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
2198			cmp = fmt->collapse(fmt, he, pair);
2199			if (cmp)
2200				break;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2201		}
2202		if (!cmp)
2203			goto out;
2204
2205		if (cmp < 0)
2206			p = &parent->rb_left;
 
2207		else
2208			p = &parent->rb_right;
2209	}
2210
2211	he = hist_entry__new(pair, true);
2212	if (he) {
2213		rb_link_node(&he->rb_node_in, parent, p);
2214		rb_insert_color(&he->rb_node_in, root);
2215
2216		he->dummy = true;
2217		he->hists = hists;
2218		memset(&he->stat, 0, sizeof(he->stat));
2219		hists__inc_stats(hists, he);
2220	}
2221out:
2222	return he;
2223}
2224
2225static struct hist_entry *hists__find_entry(struct hists *hists,
2226					    struct hist_entry *he)
2227{
2228	struct rb_node *n;
2229
2230	if (hists__has(hists, need_collapse))
2231		n = hists->entries_collapsed.rb_node;
2232	else
2233		n = hists->entries_in->rb_node;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2234
2235	while (n) {
2236		struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in);
2237		int64_t cmp = hist_entry__collapse(iter, he);
2238
2239		if (cmp < 0)
2240			n = n->rb_left;
2241		else if (cmp > 0)
2242			n = n->rb_right;
2243		else
2244			return iter;
2245	}
2246
2247	return NULL;
2248}
2249
2250static struct hist_entry *hists__find_hierarchy_entry(struct rb_root *root,
2251						      struct hist_entry *he)
2252{
2253	struct rb_node *n = root->rb_node;
2254
2255	while (n) {
2256		struct hist_entry *iter;
2257		struct perf_hpp_fmt *fmt;
2258		int64_t cmp = 0;
2259
2260		iter = rb_entry(n, struct hist_entry, rb_node_in);
2261		perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
2262			cmp = fmt->collapse(fmt, iter, he);
2263			if (cmp)
2264				break;
 
 
 
 
 
 
 
 
 
 
 
 
 
2265		}
2266
2267		if (cmp < 0)
2268			n = n->rb_left;
2269		else if (cmp > 0)
2270			n = n->rb_right;
2271		else
2272			return iter;
2273	}
2274
2275	return NULL;
2276}
2277
2278static void hists__match_hierarchy(struct rb_root *leader_root,
2279				   struct rb_root *other_root)
2280{
2281	struct rb_node *nd;
2282	struct hist_entry *pos, *pair;
2283
2284	for (nd = rb_first(leader_root); nd; nd = rb_next(nd)) {
2285		pos  = rb_entry(nd, struct hist_entry, rb_node_in);
2286		pair = hists__find_hierarchy_entry(other_root, pos);
2287
2288		if (pair) {
2289			hist_entry__add_pair(pair, pos);
2290			hists__match_hierarchy(&pos->hroot_in, &pair->hroot_in);
2291		}
2292	}
2293}
2294
2295/*
2296 * Look for pairs to link to the leader buckets (hist_entries):
2297 */
2298void hists__match(struct hists *leader, struct hists *other)
2299{
2300	struct rb_root *root;
2301	struct rb_node *nd;
2302	struct hist_entry *pos, *pair;
2303
2304	if (symbol_conf.report_hierarchy) {
2305		/* hierarchy report always collapses entries */
2306		return hists__match_hierarchy(&leader->entries_collapsed,
2307					      &other->entries_collapsed);
 
 
 
2308	}
2309
2310	if (hists__has(leader, need_collapse))
2311		root = &leader->entries_collapsed;
2312	else
2313		root = leader->entries_in;
2314
2315	for (nd = rb_first(root); nd; nd = rb_next(nd)) {
2316		pos  = rb_entry(nd, struct hist_entry, rb_node_in);
2317		pair = hists__find_entry(other, pos);
2318
2319		if (pair)
2320			hist_entry__add_pair(pair, pos);
2321	}
 
2322}
2323
2324static int hists__link_hierarchy(struct hists *leader_hists,
2325				 struct hist_entry *parent,
2326				 struct rb_root *leader_root,
2327				 struct rb_root *other_root)
2328{
2329	struct rb_node *nd;
2330	struct hist_entry *pos, *leader;
2331
2332	for (nd = rb_first(other_root); nd; nd = rb_next(nd)) {
2333		pos = rb_entry(nd, struct hist_entry, rb_node_in);
2334
2335		if (hist_entry__has_pairs(pos)) {
2336			bool found = false;
2337
2338			list_for_each_entry(leader, &pos->pairs.head, pairs.node) {
2339				if (leader->hists == leader_hists) {
2340					found = true;
2341					break;
2342				}
2343			}
2344			if (!found)
2345				return -1;
2346		} else {
2347			leader = add_dummy_hierarchy_entry(leader_hists,
2348							   leader_root, pos);
2349			if (leader == NULL)
2350				return -1;
2351
2352			/* do not point parent in the pos */
2353			leader->parent_he = parent;
2354
2355			hist_entry__add_pair(pos, leader);
2356		}
 
 
 
 
2357
2358		if (!pos->leaf) {
2359			if (hists__link_hierarchy(leader_hists, leader,
2360						  &leader->hroot_in,
2361						  &pos->hroot_in) < 0)
2362				return -1;
2363		}
2364	}
2365	return 0;
2366}
2367
2368/*
2369 * Look for entries in the other hists that are not present in the leader, if
2370 * we find them, just add a dummy entry on the leader hists, with period=0,
2371 * nr_events=0, to serve as the list header.
2372 */
2373int hists__link(struct hists *leader, struct hists *other)
2374{
2375	struct rb_root *root;
2376	struct rb_node *nd;
2377	struct hist_entry *pos, *pair;
2378
2379	if (symbol_conf.report_hierarchy) {
2380		/* hierarchy report always collapses entries */
2381		return hists__link_hierarchy(leader, NULL,
2382					     &leader->entries_collapsed,
2383					     &other->entries_collapsed);
2384	}
2385
2386	if (hists__has(other, need_collapse))
2387		root = &other->entries_collapsed;
2388	else
2389		root = other->entries_in;
2390
2391	for (nd = rb_first(root); nd; nd = rb_next(nd)) {
2392		pos = rb_entry(nd, struct hist_entry, rb_node_in);
2393
2394		if (!hist_entry__has_pairs(pos)) {
2395			pair = hists__add_dummy_entry(leader, pos);
2396			if (pair == NULL)
2397				return -1;
2398			hist_entry__add_pair(pos, pair);
2399		}
2400	}
2401
2402	return 0;
2403}
2404
2405void hist__account_cycles(struct branch_stack *bs, struct addr_location *al,
2406			  struct perf_sample *sample, bool nonany_branch_mode)
2407{
2408	struct branch_info *bi;
2409
2410	/* If we have branch cycles always annotate them. */
2411	if (bs && bs->nr && bs->entries[0].flags.cycles) {
2412		int i;
2413
2414		bi = sample__resolve_bstack(sample, al);
2415		if (bi) {
2416			struct addr_map_symbol *prev = NULL;
2417
2418			/*
2419			 * Ignore errors, still want to process the
2420			 * other entries.
2421			 *
2422			 * For non standard branch modes always
2423			 * force no IPC (prev == NULL)
2424			 *
2425			 * Note that perf stores branches reversed from
2426			 * program order!
2427			 */
2428			for (i = bs->nr - 1; i >= 0; i--) {
2429				addr_map_symbol__account_cycles(&bi[i].from,
2430					nonany_branch_mode ? NULL : prev,
2431					bi[i].flags.cycles);
2432				prev = &bi[i].to;
2433			}
2434			free(bi);
2435		}
2436	}
2437}
2438
2439size_t perf_evlist__fprintf_nr_events(struct perf_evlist *evlist, FILE *fp)
2440{
2441	struct perf_evsel *pos;
2442	size_t ret = 0;
2443
2444	evlist__for_each_entry(evlist, pos) {
2445		ret += fprintf(fp, "%s stats:\n", perf_evsel__name(pos));
2446		ret += events_stats__fprintf(&evsel__hists(pos)->stats, fp);
2447	}
2448
2449	return ret;
2450}
2451
 
 
 
2452
2453u64 hists__total_period(struct hists *hists)
2454{
2455	return symbol_conf.filter_relative ? hists->stats.total_non_filtered_period :
2456		hists->stats.total_period;
2457}
2458
2459int __hists__scnprintf_title(struct hists *hists, char *bf, size_t size, bool show_freq)
2460{
2461	char unit;
2462	int printed;
2463	const struct dso *dso = hists->dso_filter;
2464	const struct thread *thread = hists->thread_filter;
2465	int socket_id = hists->socket_filter;
2466	unsigned long nr_samples = hists->stats.nr_events[PERF_RECORD_SAMPLE];
2467	u64 nr_events = hists->stats.total_period;
2468	struct perf_evsel *evsel = hists_to_evsel(hists);
2469	const char *ev_name = perf_evsel__name(evsel);
2470	char buf[512], sample_freq_str[64] = "";
2471	size_t buflen = sizeof(buf);
2472	char ref[30] = " show reference callgraph, ";
2473	bool enable_ref = false;
2474
2475	if (symbol_conf.filter_relative) {
2476		nr_samples = hists->stats.nr_non_filtered_samples;
2477		nr_events = hists->stats.total_non_filtered_period;
2478	}
2479
2480	if (perf_evsel__is_group_event(evsel)) {
2481		struct perf_evsel *pos;
2482
2483		perf_evsel__group_desc(evsel, buf, buflen);
2484		ev_name = buf;
2485
2486		for_each_group_member(pos, evsel) {
2487			struct hists *pos_hists = evsel__hists(pos);
2488
2489			if (symbol_conf.filter_relative) {
2490				nr_samples += pos_hists->stats.nr_non_filtered_samples;
2491				nr_events += pos_hists->stats.total_non_filtered_period;
2492			} else {
2493				nr_samples += pos_hists->stats.nr_events[PERF_RECORD_SAMPLE];
2494				nr_events += pos_hists->stats.total_period;
2495			}
2496		}
2497	}
2498
2499	if (symbol_conf.show_ref_callgraph &&
2500	    strstr(ev_name, "call-graph=no"))
2501		enable_ref = true;
2502
2503	if (show_freq)
2504		scnprintf(sample_freq_str, sizeof(sample_freq_str), " %d Hz,", evsel->attr.sample_freq);
2505
2506	nr_samples = convert_unit(nr_samples, &unit);
2507	printed = scnprintf(bf, size,
2508			   "Samples: %lu%c of event%s '%s',%s%sEvent count (approx.): %" PRIu64,
2509			   nr_samples, unit, evsel->nr_members > 1 ? "s" : "",
2510			   ev_name, sample_freq_str, enable_ref ? ref : " ", nr_events);
2511
2512
2513	if (hists->uid_filter_str)
2514		printed += snprintf(bf + printed, size - printed,
2515				    ", UID: %s", hists->uid_filter_str);
2516	if (thread) {
2517		if (hists__has(hists, thread)) {
2518			printed += scnprintf(bf + printed, size - printed,
2519				    ", Thread: %s(%d)",
2520				     (thread->comm_set ? thread__comm_str(thread) : ""),
2521				    thread->tid);
2522		} else {
2523			printed += scnprintf(bf + printed, size - printed,
2524				    ", Thread: %s",
2525				     (thread->comm_set ? thread__comm_str(thread) : ""));
2526		}
2527	}
2528	if (dso)
2529		printed += scnprintf(bf + printed, size - printed,
2530				    ", DSO: %s", dso->short_name);
2531	if (socket_id > -1)
2532		printed += scnprintf(bf + printed, size - printed,
2533				    ", Processor Socket: %d", socket_id);
2534
2535	return printed;
2536}
2537
2538int parse_filter_percentage(const struct option *opt __maybe_unused,
2539			    const char *arg, int unset __maybe_unused)
2540{
2541	if (!strcmp(arg, "relative"))
2542		symbol_conf.filter_relative = true;
2543	else if (!strcmp(arg, "absolute"))
2544		symbol_conf.filter_relative = false;
2545	else {
2546		pr_debug("Invalid percentage: %s\n", arg);
2547		return -1;
2548	}
2549
2550	return 0;
2551}
2552
2553int perf_hist_config(const char *var, const char *value)
2554{
2555	if (!strcmp(var, "hist.percentage"))
2556		return parse_filter_percentage(NULL, value, 0);
2557
2558	return 0;
2559}
2560
2561int __hists__init(struct hists *hists, struct perf_hpp_list *hpp_list)
2562{
2563	memset(hists, 0, sizeof(*hists));
2564	hists->entries_in_array[0] = hists->entries_in_array[1] = RB_ROOT;
2565	hists->entries_in = &hists->entries_in_array[0];
2566	hists->entries_collapsed = RB_ROOT;
2567	hists->entries = RB_ROOT;
2568	pthread_mutex_init(&hists->lock, NULL);
2569	hists->socket_filter = -1;
2570	hists->hpp_list = hpp_list;
2571	INIT_LIST_HEAD(&hists->hpp_formats);
2572	return 0;
2573}
2574
2575static void hists__delete_remaining_entries(struct rb_root *root)
2576{
2577	struct rb_node *node;
2578	struct hist_entry *he;
2579
2580	while (!RB_EMPTY_ROOT(root)) {
2581		node = rb_first(root);
2582		rb_erase(node, root);
2583
2584		he = rb_entry(node, struct hist_entry, rb_node_in);
2585		hist_entry__delete(he);
2586	}
2587}
2588
2589static void hists__delete_all_entries(struct hists *hists)
2590{
2591	hists__delete_entries(hists);
2592	hists__delete_remaining_entries(&hists->entries_in_array[0]);
2593	hists__delete_remaining_entries(&hists->entries_in_array[1]);
2594	hists__delete_remaining_entries(&hists->entries_collapsed);
2595}
2596
2597static void hists_evsel__exit(struct perf_evsel *evsel)
2598{
2599	struct hists *hists = evsel__hists(evsel);
2600	struct perf_hpp_fmt *fmt, *pos;
2601	struct perf_hpp_list_node *node, *tmp;
2602
2603	hists__delete_all_entries(hists);
2604
2605	list_for_each_entry_safe(node, tmp, &hists->hpp_formats, list) {
2606		perf_hpp_list__for_each_format_safe(&node->hpp, fmt, pos) {
2607			list_del(&fmt->list);
2608			free(fmt);
2609		}
2610		list_del(&node->list);
2611		free(node);
2612	}
2613}
2614
2615static int hists_evsel__init(struct perf_evsel *evsel)
2616{
2617	struct hists *hists = evsel__hists(evsel);
 
2618
2619	__hists__init(hists, &perf_hpp_list);
2620	return 0;
2621}
2622
2623/*
2624 * XXX We probably need a hists_evsel__exit() to free the hist_entries
2625 * stored in the rbtree...
2626 */
2627
2628int hists__init(void)
2629{
2630	int err = perf_evsel__object_config(sizeof(struct hists_evsel),
2631					    hists_evsel__init,
2632					    hists_evsel__exit);
2633	if (err)
2634		fputs("FATAL ERROR: Couldn't setup hists class\n", stderr);
2635
2636	return err;
2637}
 
2638
2639void perf_hpp_list__init(struct perf_hpp_list *list)
2640{
2641	INIT_LIST_HEAD(&list->fields);
2642	INIT_LIST_HEAD(&list->sorts);
2643}