hist.c 48.1 KB
Newer Older
1
#include "util.h"
2
#include "build-id.h"
3
#include "hist.h"
4 5
#include "session.h"
#include "sort.h"
6
#include "evlist.h"
7
#include "evsel.h"
8
#include "annotate.h"
9
#include "ui/progress.h"
10
#include <math.h>
11

12 13 14 15
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);
16 17
static bool hists__filter_entry_by_symbol(struct hists *hists,
					  struct hist_entry *he);
18 19
static bool hists__filter_entry_by_socket(struct hists *hists,
					  struct hist_entry *he);
20

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

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

31
bool hists__new_col_len(struct hists *hists, enum hist_column col, u16 len)
32
{
33 34
	if (len > hists__col_len(hists, col)) {
		hists__set_col_len(hists, col, len);
35 36 37 38 39
		return true;
	}
	return false;
}

40
void hists__reset_col_len(struct hists *hists)
41 42 43 44
{
	enum hist_column col;

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

48 49 50 51 52 53 54 55 56 57
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);
}

58
void hists__calc_col_len(struct hists *hists, struct hist_entry *h)
59
{
60
	const unsigned int unresolved_col_width = BITS_PER_LONG / 4;
61
	int symlen;
62 63
	u16 len;

64 65 66 67 68 69 70 71 72 73 74
	/*
	 * +4 accounts for '[x] ' priv level info
	 * +2 accounts for 0x prefix on raw addresses
	 * +3 accounts for ' y ' symtab origin info
	 */
	if (h->ms.sym) {
		symlen = h->ms.sym->namelen + 4;
		if (verbose)
			symlen += BITS_PER_LONG / 4 + 2 + 3;
		hists__new_col_len(hists, HISTC_SYMBOL, symlen);
	} else {
75 76
		symlen = unresolved_col_width + 4 + 2;
		hists__new_col_len(hists, HISTC_SYMBOL, symlen);
77
		hists__set_unres_dso_col_len(hists, HISTC_DSO);
78
	}
79 80

	len = thread__comm_len(h->thread);
81 82
	if (hists__new_col_len(hists, HISTC_COMM, len))
		hists__set_col_len(hists, HISTC_THREAD, len + 6);
83 84 85

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

89 90 91
	if (h->parent)
		hists__new_col_len(hists, HISTC_PARENT, h->parent->namelen);

92 93 94
	if (h->branch_info) {
		if (h->branch_info->from.sym) {
			symlen = (int)h->branch_info->from.sym->namelen + 4;
95 96
			if (verbose)
				symlen += BITS_PER_LONG / 4 + 2 + 3;
97 98 99 100 101 102 103 104 105 106 107 108
			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;
109 110
			if (verbose)
				symlen += BITS_PER_LONG / 4 + 2 + 3;
111 112 113 114 115 116 117 118 119 120
			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);
		}
	}
121 122 123 124 125 126 127

	if (h->mem_info) {
		if (h->mem_info->daddr.sym) {
			symlen = (int)h->mem_info->daddr.sym->namelen + 4
			       + unresolved_col_width + 2;
			hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
					   symlen);
D
Don Zickus 已提交
128 129
			hists__new_col_len(hists, HISTC_MEM_DCACHELINE,
					   symlen + 1);
130 131 132 133
		} else {
			symlen = unresolved_col_width + 4 + 2;
			hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
					   symlen);
134 135
			hists__new_col_len(hists, HISTC_MEM_DCACHELINE,
					   symlen);
136
		}
137 138 139 140 141 142 143 144 145 146 147 148

		if (h->mem_info->iaddr.sym) {
			symlen = (int)h->mem_info->iaddr.sym->namelen + 4
			       + unresolved_col_width + 2;
			hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL,
					   symlen);
		} else {
			symlen = unresolved_col_width + 4 + 2;
			hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL,
					   symlen);
		}

149 150 151 152 153 154 155 156 157 158 159
		if (h->mem_info->daddr.map) {
			symlen = dso__name_len(h->mem_info->daddr.map->dso);
			hists__new_col_len(hists, HISTC_MEM_DADDR_DSO,
					   symlen);
		} else {
			symlen = unresolved_col_width + 4 + 2;
			hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
		}
	} else {
		symlen = unresolved_col_width + 4 + 2;
		hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL, symlen);
160
		hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL, symlen);
161 162 163
		hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
	}

164
	hists__new_col_len(hists, HISTC_CPU, 3);
165
	hists__new_col_len(hists, HISTC_SOCKET, 6);
166 167 168 169 170 171
	hists__new_col_len(hists, HISTC_MEM_LOCKED, 6);
	hists__new_col_len(hists, HISTC_MEM_TLB, 22);
	hists__new_col_len(hists, HISTC_MEM_SNOOP, 12);
	hists__new_col_len(hists, HISTC_MEM_LVL, 21 + 3);
	hists__new_col_len(hists, HISTC_LOCAL_WEIGHT, 12);
	hists__new_col_len(hists, HISTC_GLOBAL_WEIGHT, 12);
172

173 174 175
	if (h->srcline)
		hists__new_col_len(hists, HISTC_SRCLINE, strlen(h->srcline));

176 177 178
	if (h->srcfile)
		hists__new_col_len(hists, HISTC_SRCFILE, strlen(h->srcfile));

179 180 181
	if (h->transaction)
		hists__new_col_len(hists, HISTC_TRANSACTION,
				   hist_entry__transaction_len());
182 183 184

	if (h->trace_output)
		hists__new_col_len(hists, HISTC_TRACE, strlen(h->trace_output));
185 186
}

187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202
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);
	}
}

203 204
static void he_stat__add_cpumode_period(struct he_stat *he_stat,
					unsigned int cpumode, u64 period)
205
{
206
	switch (cpumode) {
207
	case PERF_RECORD_MISC_KERNEL:
208
		he_stat->period_sys += period;
209 210
		break;
	case PERF_RECORD_MISC_USER:
211
		he_stat->period_us += period;
212 213
		break;
	case PERF_RECORD_MISC_GUEST_KERNEL:
214
		he_stat->period_guest_sys += period;
215 216
		break;
	case PERF_RECORD_MISC_GUEST_USER:
217
		he_stat->period_guest_us += period;
218 219 220 221 222 223
		break;
	default:
		break;
	}
}

224 225
static void he_stat__add_period(struct he_stat *he_stat, u64 period,
				u64 weight)
226
{
227

228
	he_stat->period		+= period;
229
	he_stat->weight		+= weight;
230 231 232 233 234 235 236 237 238 239 240
	he_stat->nr_events	+= 1;
}

static void he_stat__add_stat(struct he_stat *dest, struct he_stat *src)
{
	dest->period		+= src->period;
	dest->period_sys	+= src->period_sys;
	dest->period_us		+= src->period_us;
	dest->period_guest_sys	+= src->period_guest_sys;
	dest->period_guest_us	+= src->period_guest_us;
	dest->nr_events		+= src->nr_events;
241
	dest->weight		+= src->weight;
242 243
}

244
static void he_stat__decay(struct he_stat *he_stat)
245
{
246 247
	he_stat->period = (he_stat->period * 7) / 8;
	he_stat->nr_events = (he_stat->nr_events * 7) / 8;
248
	/* XXX need decay for weight too? */
249 250 251 252
}

static bool hists__decay_entry(struct hists *hists, struct hist_entry *he)
{
253
	u64 prev_period = he->stat.period;
254
	u64 diff;
255 256

	if (prev_period == 0)
257
		return true;
258

259
	he_stat__decay(&he->stat);
260 261
	if (symbol_conf.cumulate_callchain)
		he_stat__decay(he->stat_acc);
262
	decay_callchain(he->callchain);
263

264 265 266
	diff = prev_period - he->stat.period;

	hists->stats.total_period -= diff;
267
	if (!he->filtered)
268
		hists->stats.total_non_filtered_period -= diff;
269

270
	return he->stat.period == 0;
271 272
}

273 274 275 276 277 278
static void hists__delete_entry(struct hists *hists, struct hist_entry *he)
{
	rb_erase(&he->rb_node, &hists->entries);

	if (sort__need_collapse)
		rb_erase(&he->rb_node_in, &hists->entries_collapsed);
279 280
	else
		rb_erase(&he->rb_node_in, hists->entries_in);
281 282 283 284 285 286 287 288

	--hists->nr_entries;
	if (!he->filtered)
		--hists->nr_non_filtered_entries;

	hist_entry__delete(he);
}

289
void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
290 291 292 293 294 295 296
{
	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);
297 298
		if (((zap_user && n->level == '.') ||
		     (zap_kernel && n->level != '.') ||
299
		     hists__decay_entry(hists, n))) {
300
			hists__delete_entry(hists, n);
301 302 303 304
		}
	}
}

N
Namhyung Kim 已提交
305 306 307 308 309 310 311 312 313
void hists__delete_entries(struct hists *hists)
{
	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);

314
		hists__delete_entry(hists, n);
N
Namhyung Kim 已提交
315 316 317
	}
}

318
/*
319
 * histogram, sorted on item, collects periods
320 321
 */

322 323
static struct hist_entry *hist_entry__new(struct hist_entry *template,
					  bool sample_self)
324
{
325 326 327
	size_t callchain_size = 0;
	struct hist_entry *he;

328
	if (symbol_conf.use_callchain)
329 330 331
		callchain_size = sizeof(struct callchain_root);

	he = zalloc(sizeof(*he) + callchain_size);
332

333 334
	if (he != NULL) {
		*he = *template;
335

336 337 338 339 340 341 342
		if (symbol_conf.cumulate_callchain) {
			he->stat_acc = malloc(sizeof(he->stat));
			if (he->stat_acc == NULL) {
				free(he);
				return NULL;
			}
			memcpy(he->stat_acc, &he->stat, sizeof(he->stat));
343 344
			if (!sample_self)
				memset(&he->stat, 0, sizeof(he->stat));
345 346
		}

347
		map__get(he->ms.map);
348 349

		if (he->branch_info) {
350 351
			/*
			 * This branch info is (a part of) allocated from
352
			 * sample__resolve_bstack() and will be freed after
353 354 355 356
			 * adding new entries.  So we need to save a copy.
			 */
			he->branch_info = malloc(sizeof(*he->branch_info));
			if (he->branch_info == NULL) {
357
				map__zput(he->ms.map);
358
				free(he->stat_acc);
359 360 361 362 363 364 365
				free(he);
				return NULL;
			}

			memcpy(he->branch_info, template->branch_info,
			       sizeof(*he->branch_info));

366 367
			map__get(he->branch_info->from.map);
			map__get(he->branch_info->to.map);
368 369
		}

370
		if (he->mem_info) {
371 372
			map__get(he->mem_info->iaddr.map);
			map__get(he->mem_info->daddr.map);
373 374
		}

375
		if (symbol_conf.use_callchain)
376
			callchain_init(he->callchain);
377

378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396
		if (he->raw_data) {
			he->raw_data = memdup(he->raw_data, he->raw_size);

			if (he->raw_data == NULL) {
				map__put(he->ms.map);
				if (he->branch_info) {
					map__put(he->branch_info->from.map);
					map__put(he->branch_info->to.map);
					free(he->branch_info);
				}
				if (he->mem_info) {
					map__put(he->mem_info->iaddr.map);
					map__put(he->mem_info->daddr.map);
				}
				free(he->stat_acc);
				free(he);
				return NULL;
			}
		}
397
		INIT_LIST_HEAD(&he->pairs.node);
398
		thread__get(he->thread);
399 400 401

		if (!symbol_conf.report_hierarchy)
			he->leaf = true;
402 403
	}

404
	return he;
405 406
}

407 408 409 410 411 412 413
static u8 symbol__parent_filter(const struct symbol *parent)
{
	if (symbol_conf.exclude_other && parent == NULL)
		return 1 << HIST_FILTER__PARENT;
	return 0;
}

414 415 416 417 418 419 420 421 422 423
static void hist_entry__add_callchain_period(struct hist_entry *he, u64 period)
{
	if (!symbol_conf.use_callchain)
		return;

	he->hists->callchain_period += period;
	if (!he->filtered)
		he->hists->callchain_non_filtered_period += period;
}

424 425 426 427
static struct hist_entry *hists__findnew_entry(struct hists *hists,
					       struct hist_entry *entry,
					       struct addr_location *al,
					       bool sample_self)
428
{
429
	struct rb_node **p;
430 431
	struct rb_node *parent = NULL;
	struct hist_entry *he;
432
	int64_t cmp;
433 434
	u64 period = entry->stat.period;
	u64 weight = entry->stat.weight;
435

436 437
	p = &hists->entries_in->rb_node;

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

442 443 444 445 446 447 448
		/*
		 * Make sure that it receives arguments in a same order as
		 * hist_entry__collapse() so that we can use an appropriate
		 * function when searching an entry regardless which sort
		 * keys were used.
		 */
		cmp = hist_entry__cmp(he, entry);
449 450

		if (!cmp) {
451
			if (sample_self) {
452
				he_stat__add_period(&he->stat, period, weight);
453
				hist_entry__add_callchain_period(he, period);
454
			}
455 456
			if (symbol_conf.cumulate_callchain)
				he_stat__add_period(he->stat_acc, period, weight);
457

458
			/*
459
			 * This mem info was allocated from sample__resolve_mem
460 461
			 * and will not be used anymore.
			 */
462
			zfree(&entry->mem_info);
463

464 465 466 467 468 469 470
			/* 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) {
471 472
				map__put(he->ms.map);
				he->ms.map = map__get(entry->ms.map);
473
			}
474
			goto out;
475 476 477 478 479 480 481 482
		}

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

483
	he = hist_entry__new(entry, sample_self);
484
	if (!he)
485
		return NULL;
486

487
	if (sample_self)
488 489
		hist_entry__add_callchain_period(he, period);
	hists->nr_entries++;
490

491 492
	rb_link_node(&he->rb_node_in, parent, p);
	rb_insert_color(&he->rb_node_in, hists->entries_in);
493
out:
494 495
	if (sample_self)
		he_stat__add_cpumode_period(&he->stat, al->cpumode, period);
496 497
	if (symbol_conf.cumulate_callchain)
		he_stat__add_cpumode_period(he->stat_acc, al->cpumode, period);
498 499 500
	return he;
}

501
struct hist_entry *__hists__add_entry(struct hists *hists,
502
				      struct addr_location *al,
503 504 505
				      struct symbol *sym_parent,
				      struct branch_info *bi,
				      struct mem_info *mi,
506
				      struct perf_sample *sample,
507
				      bool sample_self)
508 509 510
{
	struct hist_entry entry = {
		.thread	= al->thread,
511
		.comm = thread__comm(al->thread),
512 513 514 515
		.ms = {
			.map	= al->map,
			.sym	= al->sym,
		},
516
		.socket	 = al->socket,
517 518 519 520
		.cpu	 = al->cpu,
		.cpumode = al->cpumode,
		.ip	 = al->addr,
		.level	 = al->level,
521
		.stat = {
522
			.nr_events = 1,
523 524
			.period	= sample->period,
			.weight = sample->weight,
525
		},
526
		.parent = sym_parent,
527
		.filtered = symbol__parent_filter(sym_parent) | al->filtered,
528
		.hists	= hists,
529 530
		.branch_info = bi,
		.mem_info = mi,
531
		.transaction = sample->transaction,
532 533
		.raw_data = sample->raw_data,
		.raw_size = sample->raw_size,
534 535
	};

536
	return hists__findnew_entry(hists, &entry, al, sample_self);
537 538
}

539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571
static int
iter_next_nop_entry(struct hist_entry_iter *iter __maybe_unused,
		    struct addr_location *al __maybe_unused)
{
	return 0;
}

static int
iter_add_next_nop_entry(struct hist_entry_iter *iter __maybe_unused,
			struct addr_location *al __maybe_unused)
{
	return 0;
}

static int
iter_prepare_mem_entry(struct hist_entry_iter *iter, struct addr_location *al)
{
	struct perf_sample *sample = iter->sample;
	struct mem_info *mi;

	mi = sample__resolve_mem(sample, al);
	if (mi == NULL)
		return -ENOMEM;

	iter->priv = mi;
	return 0;
}

static int
iter_add_single_mem_entry(struct hist_entry_iter *iter, struct addr_location *al)
{
	u64 cost;
	struct mem_info *mi = iter->priv;
572
	struct hists *hists = evsel__hists(iter->evsel);
573
	struct perf_sample *sample = iter->sample;
574 575 576 577 578
	struct hist_entry *he;

	if (mi == NULL)
		return -EINVAL;

579
	cost = sample->weight;
580 581 582 583 584 585 586 587 588 589
	if (!cost)
		cost = 1;

	/*
	 * must pass period=weight in order to get the correct
	 * sorting from hists__collapse_resort() which is solely
	 * based on periods. We want sorting be done on nr_events * weight
	 * and this is indirectly achieved by passing period=weight here
	 * and the he_stat__add_period() function.
	 */
590 591
	sample->period = cost;

592
	he = __hists__add_entry(hists, al, iter->parent, NULL, mi,
593
				sample, true);
594 595 596 597 598 599 600 601
	if (!he)
		return -ENOMEM;

	iter->he = he;
	return 0;
}

static int
602 603
iter_finish_mem_entry(struct hist_entry_iter *iter,
		      struct addr_location *al __maybe_unused)
604 605
{
	struct perf_evsel *evsel = iter->evsel;
606
	struct hists *hists = evsel__hists(evsel);
607 608 609 610 611 612
	struct hist_entry *he = iter->he;
	int err = -EINVAL;

	if (he == NULL)
		goto out;

613
	hists__inc_nr_samples(hists, he->filtered);
614 615 616 617 618

	err = hist_entry__append_callchain(he, iter->sample);

out:
	/*
619 620 621
	 * We don't need to free iter->priv (mem_info) here since the mem info
	 * was either already freed in hists__findnew_entry() or passed to a
	 * new hist entry by hist_entry__new().
622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649
	 */
	iter->priv = NULL;

	iter->he = NULL;
	return err;
}

static int
iter_prepare_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
{
	struct branch_info *bi;
	struct perf_sample *sample = iter->sample;

	bi = sample__resolve_bstack(sample, al);
	if (!bi)
		return -ENOMEM;

	iter->curr = 0;
	iter->total = sample->branch_stack->nr;

	iter->priv = bi;
	return 0;
}

static int
iter_add_single_branch_entry(struct hist_entry_iter *iter __maybe_unused,
			     struct addr_location *al __maybe_unused)
{
650 651 652
	/* to avoid calling callback function */
	iter->he = NULL;

653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676
	return 0;
}

static int
iter_next_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
{
	struct branch_info *bi = iter->priv;
	int i = iter->curr;

	if (bi == NULL)
		return 0;

	if (iter->curr >= iter->total)
		return 0;

	al->map = bi[i].to.map;
	al->sym = bi[i].to.sym;
	al->addr = bi[i].to.addr;
	return 1;
}

static int
iter_add_next_branch_entry(struct hist_entry_iter *iter, struct addr_location *al)
{
677
	struct branch_info *bi;
678
	struct perf_evsel *evsel = iter->evsel;
679
	struct hists *hists = evsel__hists(evsel);
680
	struct perf_sample *sample = iter->sample;
681 682 683 684 685 686 687 688 689 690 691 692 693
	struct hist_entry *he = NULL;
	int i = iter->curr;
	int err = 0;

	bi = iter->priv;

	if (iter->hide_unresolved && !(bi[i].from.sym && bi[i].to.sym))
		goto out;

	/*
	 * The report shows the percentage of total branches captured
	 * and not events sampled. Thus we use a pseudo period of 1.
	 */
694 695 696
	sample->period = 1;
	sample->weight = bi->flags.cycles ? bi->flags.cycles : 1;

697
	he = __hists__add_entry(hists, al, iter->parent, &bi[i], NULL,
698
				sample, true);
699 700 701
	if (he == NULL)
		return -ENOMEM;

702
	hists__inc_nr_samples(hists, he->filtered);
703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733

out:
	iter->he = he;
	iter->curr++;
	return err;
}

static int
iter_finish_branch_entry(struct hist_entry_iter *iter,
			 struct addr_location *al __maybe_unused)
{
	zfree(&iter->priv);
	iter->he = NULL;

	return iter->curr >= iter->total ? 0 : -1;
}

static int
iter_prepare_normal_entry(struct hist_entry_iter *iter __maybe_unused,
			  struct addr_location *al __maybe_unused)
{
	return 0;
}

static int
iter_add_single_normal_entry(struct hist_entry_iter *iter, struct addr_location *al)
{
	struct perf_evsel *evsel = iter->evsel;
	struct perf_sample *sample = iter->sample;
	struct hist_entry *he;

734
	he = __hists__add_entry(evsel__hists(evsel), al, iter->parent, NULL, NULL,
735
				sample, true);
736 737 738 739 740 741 742 743
	if (he == NULL)
		return -ENOMEM;

	iter->he = he;
	return 0;
}

static int
744 745
iter_finish_normal_entry(struct hist_entry_iter *iter,
			 struct addr_location *al __maybe_unused)
746 747 748 749 750 751 752 753 754 755
{
	struct hist_entry *he = iter->he;
	struct perf_evsel *evsel = iter->evsel;
	struct perf_sample *sample = iter->sample;

	if (he == NULL)
		return 0;

	iter->he = NULL;

756
	hists__inc_nr_samples(evsel__hists(evsel), he->filtered);
757 758 759 760

	return hist_entry__append_callchain(he, sample);
}

761
static int
762
iter_prepare_cumulative_entry(struct hist_entry_iter *iter,
763 764
			      struct addr_location *al __maybe_unused)
{
765 766
	struct hist_entry **he_cache;

767
	callchain_cursor_commit(&callchain_cursor);
768 769 770 771 772 773

	/*
	 * This is for detecting cycles or recursions so that they're
	 * cumulated only one time to prevent entries more than 100%
	 * overhead.
	 */
774
	he_cache = malloc(sizeof(*he_cache) * (iter->max_stack + 1));
775 776 777 778 779 780
	if (he_cache == NULL)
		return -ENOMEM;

	iter->priv = he_cache;
	iter->curr = 0;

781 782 783 784 785 786 787 788
	return 0;
}

static int
iter_add_single_cumulative_entry(struct hist_entry_iter *iter,
				 struct addr_location *al)
{
	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_cache = iter->priv;
792 793 794
	struct hist_entry *he;
	int err = 0;

795
	he = __hists__add_entry(hists, al, iter->parent, NULL, NULL,
796
				sample, true);
797 798 799 800
	if (he == NULL)
		return -ENOMEM;

	iter->he = he;
801
	he_cache[iter->curr++] = he;
802

803
	hist_entry__append_callchain(he, sample);
804 805 806 807 808 809 810

	/*
	 * We need to re-initialize the cursor since callchain_append()
	 * advanced the cursor to the end.
	 */
	callchain_cursor_commit(&callchain_cursor);

811
	hists__inc_nr_samples(hists, he->filtered);
812 813 814 815 816 817 818 819 820 821 822 823 824 825

	return err;
}

static int
iter_next_cumulative_entry(struct hist_entry_iter *iter,
			   struct addr_location *al)
{
	struct callchain_cursor_node *node;

	node = callchain_cursor_current(&callchain_cursor);
	if (node == NULL)
		return 0;

826
	return fill_callchain_info(al, node, iter->hide_unresolved);
827 828 829 830 831 832 833 834
}

static int
iter_add_next_cumulative_entry(struct hist_entry_iter *iter,
			       struct addr_location *al)
{
	struct perf_evsel *evsel = iter->evsel;
	struct perf_sample *sample = iter->sample;
835
	struct hist_entry **he_cache = iter->priv;
836
	struct hist_entry *he;
837
	struct hist_entry he_tmp = {
838
		.hists = evsel__hists(evsel),
839 840 841 842 843 844 845 846 847
		.cpu = al->cpu,
		.thread = al->thread,
		.comm = thread__comm(al->thread),
		.ip = al->addr,
		.ms = {
			.map = al->map,
			.sym = al->sym,
		},
		.parent = iter->parent,
848 849
		.raw_data = sample->raw_data,
		.raw_size = sample->raw_size,
850 851
	};
	int i;
852 853 854 855 856
	struct callchain_cursor cursor;

	callchain_cursor_snapshot(&cursor, &callchain_cursor);

	callchain_cursor_advance(&callchain_cursor);
857 858 859 860 861 862

	/*
	 * Check if there's duplicate entries in the callchain.
	 * It's possible that it has cycles or recursive calls.
	 */
	for (i = 0; i < iter->curr; i++) {
863 864 865
		if (hist_entry__cmp(he_cache[i], &he_tmp) == 0) {
			/* to avoid calling callback function */
			iter->he = NULL;
866
			return 0;
867
		}
868
	}
869

870
	he = __hists__add_entry(evsel__hists(evsel), al, iter->parent, NULL, NULL,
871
				sample, false);
872 873 874 875
	if (he == NULL)
		return -ENOMEM;

	iter->he = he;
876
	he_cache[iter->curr++] = he;
877

878 879
	if (symbol_conf.use_callchain)
		callchain_append(he->callchain, &cursor, sample->period);
880 881 882 883 884 885 886
	return 0;
}

static int
iter_finish_cumulative_entry(struct hist_entry_iter *iter,
			     struct addr_location *al __maybe_unused)
{
887
	zfree(&iter->priv);
888
	iter->he = NULL;
889

890 891 892
	return 0;
}

893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916
const struct hist_iter_ops hist_iter_mem = {
	.prepare_entry 		= iter_prepare_mem_entry,
	.add_single_entry 	= iter_add_single_mem_entry,
	.next_entry 		= iter_next_nop_entry,
	.add_next_entry 	= iter_add_next_nop_entry,
	.finish_entry 		= iter_finish_mem_entry,
};

const struct hist_iter_ops hist_iter_branch = {
	.prepare_entry 		= iter_prepare_branch_entry,
	.add_single_entry 	= iter_add_single_branch_entry,
	.next_entry 		= iter_next_branch_entry,
	.add_next_entry 	= iter_add_next_branch_entry,
	.finish_entry 		= iter_finish_branch_entry,
};

const struct hist_iter_ops hist_iter_normal = {
	.prepare_entry 		= iter_prepare_normal_entry,
	.add_single_entry 	= iter_add_single_normal_entry,
	.next_entry 		= iter_next_nop_entry,
	.add_next_entry 	= iter_add_next_nop_entry,
	.finish_entry 		= iter_finish_normal_entry,
};

917 918 919 920 921 922 923 924
const struct hist_iter_ops hist_iter_cumulative = {
	.prepare_entry 		= iter_prepare_cumulative_entry,
	.add_single_entry 	= iter_add_single_cumulative_entry,
	.next_entry 		= iter_next_cumulative_entry,
	.add_next_entry 	= iter_add_next_cumulative_entry,
	.finish_entry 		= iter_finish_cumulative_entry,
};

925
int hist_entry_iter__add(struct hist_entry_iter *iter, struct addr_location *al,
926
			 int max_stack_depth, void *arg)
927 928 929
{
	int err, err2;

930 931
	err = sample__resolve_callchain(iter->sample, &iter->parent,
					iter->evsel, al, max_stack_depth);
932 933 934
	if (err)
		return err;

935 936
	iter->max_stack = max_stack_depth;

937 938 939 940 941 942 943 944
	err = iter->ops->prepare_entry(iter, al);
	if (err)
		goto out;

	err = iter->ops->add_single_entry(iter, al);
	if (err)
		goto out;

945 946 947 948 949 950
	if (iter->he && iter->add_entry_cb) {
		err = iter->add_entry_cb(iter, al, true, arg);
		if (err)
			goto out;
	}

951 952 953 954
	while (iter->ops->next_entry(iter, al)) {
		err = iter->ops->add_next_entry(iter, al);
		if (err)
			break;
955 956 957 958 959 960

		if (iter->he && iter->add_entry_cb) {
			err = iter->add_entry_cb(iter, al, false, arg);
			if (err)
				goto out;
		}
961 962 963 964 965 966 967 968 969 970
	}

out:
	err2 = iter->ops->finish_entry(iter, al);
	if (!err)
		err = err2;

	return err;
}

971 972 973
int64_t
hist_entry__cmp(struct hist_entry *left, struct hist_entry *right)
{
974
	struct hists *hists = left->hists;
975
	struct perf_hpp_fmt *fmt;
976 977
	int64_t cmp = 0;

978
	hists__for_each_sort_list(hists, fmt) {
979
		cmp = fmt->cmp(fmt, left, right);
980 981 982 983 984 985 986 987 988 989
		if (cmp)
			break;
	}

	return cmp;
}

int64_t
hist_entry__collapse(struct hist_entry *left, struct hist_entry *right)
{
990
	struct hists *hists = left->hists;
991
	struct perf_hpp_fmt *fmt;
992 993
	int64_t cmp = 0;

994
	hists__for_each_sort_list(hists, fmt) {
995
		cmp = fmt->collapse(fmt, left, right);
996 997 998 999 1000 1001 1002
		if (cmp)
			break;
	}

	return cmp;
}

1003
void hist_entry__delete(struct hist_entry *he)
1004
{
1005
	thread__zput(he->thread);
1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019
	map__zput(he->ms.map);

	if (he->branch_info) {
		map__zput(he->branch_info->from.map);
		map__zput(he->branch_info->to.map);
		zfree(&he->branch_info);
	}

	if (he->mem_info) {
		map__zput(he->mem_info->iaddr.map);
		map__zput(he->mem_info->daddr.map);
		zfree(&he->mem_info);
	}

1020
	zfree(&he->stat_acc);
1021
	free_srcline(he->srcline);
1022 1023
	if (he->srcfile && he->srcfile[0])
		free(he->srcfile);
1024
	free_callchain(he->callchain);
1025
	free(he->trace_output);
1026
	free(he->raw_data);
1027 1028 1029
	free(he);
}

1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050
/*
 * If this is not the last column, then we need to pad it according to the
 * pre-calculated max lenght for this column, otherwise don't bother adding
 * spaces because that would break viewing this with, for instance, 'less',
 * that would show tons of trailing spaces when a long C++ demangled method
 * names is sampled.
*/
int hist_entry__snprintf_alignment(struct hist_entry *he, struct perf_hpp *hpp,
				   struct perf_hpp_fmt *fmt, int printed)
{
	if (!list_is_last(&fmt->list, &he->hists->hpp_list->fields)) {
		const int width = fmt->width(fmt, hpp, hists_to_evsel(he->hists));
		if (printed < width) {
			advance_hpp(hpp, printed);
			printed = scnprintf(hpp->buf, hpp->size, "%-*s", width - printed, " ");
		}
	}

	return printed;
}

1051 1052 1053 1054
/*
 * collapse the histogram
 */

1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162
static void hists__apply_filters(struct hists *hists, struct hist_entry *he);

static struct hist_entry *hierarchy_insert_entry(struct hists *hists,
						 struct rb_root *root,
						 struct hist_entry *he,
						 struct perf_hpp_fmt *fmt)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct hist_entry *iter, *new;
	int64_t cmp;

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

		cmp = fmt->collapse(fmt, iter, he);
		if (!cmp) {
			he_stat__add_stat(&iter->stat, &he->stat);
			return iter;
		}

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

	new = hist_entry__new(he, true);
	if (new == NULL)
		return NULL;

	hists__apply_filters(hists, new);
	hists->nr_entries++;

	/* save related format for output */
	new->fmt = fmt;

	/* some fields are now passed to 'new' */
	if (perf_hpp__is_trace_entry(fmt))
		he->trace_output = NULL;
	else
		new->trace_output = NULL;

	if (perf_hpp__is_srcline_entry(fmt))
		he->srcline = NULL;
	else
		new->srcline = NULL;

	if (perf_hpp__is_srcfile_entry(fmt))
		he->srcfile = NULL;
	else
		new->srcfile = NULL;

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

static int hists__hierarchy_insert_entry(struct hists *hists,
					 struct rb_root *root,
					 struct hist_entry *he)
{
	struct perf_hpp_fmt *fmt;
	struct hist_entry *new_he = NULL;
	struct hist_entry *parent = NULL;
	int depth = 0;
	int ret = 0;

	hists__for_each_sort_list(hists, fmt) {
		if (!perf_hpp__is_sort_entry(fmt) &&
		    !perf_hpp__is_dynamic_entry(fmt))
			continue;
		if (perf_hpp__should_skip(fmt, hists))
			continue;

		/* insert copy of 'he' for each fmt into the hierarchy */
		new_he = hierarchy_insert_entry(hists, root, he, fmt);
		if (new_he == NULL) {
			ret = -1;
			break;
		}

		root = &new_he->hroot_in;
		new_he->parent_he = parent;
		new_he->depth = depth++;
		parent = new_he;
	}

	if (new_he) {
		new_he->leaf = true;

		if (symbol_conf.use_callchain) {
			callchain_cursor_reset(&callchain_cursor);
			if (callchain_merge(&callchain_cursor,
					    new_he->callchain,
					    he->callchain) < 0)
				ret = -1;
		}
	}

	/* 'he' is no longer used */
	hist_entry__delete(he);

	/* return 0 (or -1) since it already applied filters */
	return ret;
}

1163 1164
int hists__collapse_insert_entry(struct hists *hists, struct rb_root *root,
				 struct hist_entry *he)
1165
{
1166
	struct rb_node **p = &root->rb_node;
1167 1168 1169 1170
	struct rb_node *parent = NULL;
	struct hist_entry *iter;
	int64_t cmp;

1171 1172 1173
	if (symbol_conf.report_hierarchy)
		return hists__hierarchy_insert_entry(hists, root, he);

1174 1175
	while (*p != NULL) {
		parent = *p;
1176
		iter = rb_entry(parent, struct hist_entry, rb_node_in);
1177 1178 1179 1180

		cmp = hist_entry__collapse(iter, he);

		if (!cmp) {
1181 1182
			int ret = 0;

1183
			he_stat__add_stat(&iter->stat, &he->stat);
1184 1185
			if (symbol_conf.cumulate_callchain)
				he_stat__add_stat(iter->stat_acc, he->stat_acc);
1186

1187
			if (symbol_conf.use_callchain) {
1188
				callchain_cursor_reset(&callchain_cursor);
1189 1190 1191 1192
				if (callchain_merge(&callchain_cursor,
						    iter->callchain,
						    he->callchain) < 0)
					ret = -1;
1193
			}
1194
			hist_entry__delete(he);
1195
			return ret;
1196 1197 1198 1199 1200 1201 1202
		}

		if (cmp < 0)
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}
1203
	hists->nr_entries++;
1204

1205 1206
	rb_link_node(&he->rb_node_in, parent, p);
	rb_insert_color(&he->rb_node_in, root);
1207
	return 1;
1208 1209
}

1210
struct rb_root *hists__get_rotate_entries_in(struct hists *hists)
1211
{
1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224
	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;
}

1225 1226 1227 1228
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);
1229
	hists__filter_entry_by_symbol(hists, he);
1230
	hists__filter_entry_by_socket(hists, he);
1231 1232
}

1233
int hists__collapse_resort(struct hists *hists, struct ui_progress *prog)
1234 1235
{
	struct rb_root *root;
1236 1237
	struct rb_node *next;
	struct hist_entry *n;
1238
	int ret;
1239

1240
	if (!sort__need_collapse)
1241
		return 0;
1242

1243 1244
	hists->nr_entries = 0;

1245
	root = hists__get_rotate_entries_in(hists);
1246

1247
	next = rb_first(root);
1248

1249
	while (next) {
1250 1251
		if (session_done())
			break;
1252 1253
		n = rb_entry(next, struct hist_entry, rb_node_in);
		next = rb_next(&n->rb_node_in);
1254

1255
		rb_erase(&n->rb_node_in, root);
1256 1257 1258 1259 1260
		ret = hists__collapse_insert_entry(hists, &hists->entries_collapsed, n);
		if (ret < 0)
			return -1;

		if (ret) {
1261 1262 1263 1264 1265 1266 1267
			/*
			 * 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);
		}
1268 1269
		if (prog)
			ui_progress__update(prog, 1);
1270
	}
1271
	return 0;
1272
}
1273

1274
static int hist_entry__sort(struct hist_entry *a, struct hist_entry *b)
1275
{
1276
	struct hists *hists = a->hists;
1277 1278
	struct perf_hpp_fmt *fmt;
	int64_t cmp = 0;
1279

1280
	hists__for_each_sort_list(hists, fmt) {
1281
		if (perf_hpp__should_skip(fmt, a->hists))
1282 1283
			continue;

1284
		cmp = fmt->sort(fmt, a, b);
1285
		if (cmp)
1286 1287 1288
			break;
	}

1289
	return cmp;
1290 1291
}

1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320
static void hists__reset_filter_stats(struct hists *hists)
{
	hists->nr_non_filtered_entries = 0;
	hists->stats.total_non_filtered_period = 0;
}

void hists__reset_stats(struct hists *hists)
{
	hists->nr_entries = 0;
	hists->stats.total_period = 0;

	hists__reset_filter_stats(hists);
}

static void hists__inc_filter_stats(struct hists *hists, struct hist_entry *h)
{
	hists->nr_non_filtered_entries++;
	hists->stats.total_non_filtered_period += h->stat.period;
}

void hists__inc_stats(struct hists *hists, struct hist_entry *h)
{
	if (!h->filtered)
		hists__inc_filter_stats(hists, h);

	hists->nr_entries++;
	hists->stats.total_period += h->stat.period;
}

1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400
static void hierarchy_insert_output_entry(struct rb_root *root,
					  struct hist_entry *he)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct hist_entry *iter;

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

		if (hist_entry__sort(he, iter) > 0)
			p = &parent->rb_left;
		else
			p = &parent->rb_right;
	}

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

static void hists__hierarchy_output_resort(struct hists *hists,
					   struct ui_progress *prog,
					   struct rb_root *root_in,
					   struct rb_root *root_out,
					   u64 min_callchain_hits,
					   bool use_callchain)
{
	struct rb_node *node;
	struct hist_entry *he;

	*root_out = RB_ROOT;
	node = rb_first(root_in);

	while (node) {
		he = rb_entry(node, struct hist_entry, rb_node_in);
		node = rb_next(node);

		hierarchy_insert_output_entry(root_out, he);

		if (prog)
			ui_progress__update(prog, 1);

		if (!he->leaf) {
			hists__hierarchy_output_resort(hists, prog,
						       &he->hroot_in,
						       &he->hroot_out,
						       min_callchain_hits,
						       use_callchain);
			hists->nr_entries++;
			if (!he->filtered) {
				hists->nr_non_filtered_entries++;
				hists__calc_col_len(hists, he);
			}

			continue;
		}

		/* only update stat for leaf entries to avoid duplication */
		hists__inc_stats(hists, he);
		if (!he->filtered)
			hists__calc_col_len(hists, he);

		if (!use_callchain)
			continue;

		if (callchain_param.mode == CHAIN_GRAPH_REL) {
			u64 total = he->stat.period;

			if (symbol_conf.cumulate_callchain)
				total = he->stat_acc->period;

			min_callchain_hits = total * (callchain_param.min_percent / 100);
		}

		callchain_param.sort(&he->sorted_chain, he->callchain,
				     min_callchain_hits, &callchain_param);
	}
}

1401 1402
static void __hists__insert_output_entry(struct rb_root *entries,
					 struct hist_entry *he,
1403 1404
					 u64 min_callchain_hits,
					 bool use_callchain)
1405
{
1406
	struct rb_node **p = &entries->rb_node;
1407 1408 1409
	struct rb_node *parent = NULL;
	struct hist_entry *iter;

1410 1411 1412 1413 1414 1415 1416 1417 1418
	if (use_callchain) {
		if (callchain_param.mode == CHAIN_GRAPH_REL) {
			u64 total = he->stat.period;

			if (symbol_conf.cumulate_callchain)
				total = he->stat_acc->period;

			min_callchain_hits = total * (callchain_param.min_percent / 100);
		}
1419
		callchain_param.sort(&he->sorted_chain, he->callchain,
1420
				      min_callchain_hits, &callchain_param);
1421
	}
1422 1423 1424 1425 1426

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

1427
		if (hist_entry__sort(he, iter) > 0)
1428 1429 1430 1431 1432 1433
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

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

1437 1438
static void output_resort(struct hists *hists, struct ui_progress *prog,
			  bool use_callchain)
1439
{
1440
	struct rb_root *root;
1441 1442
	struct rb_node *next;
	struct hist_entry *n;
1443
	u64 callchain_total;
1444 1445
	u64 min_callchain_hits;

1446 1447 1448 1449 1450
	callchain_total = hists->callchain_period;
	if (symbol_conf.filter_relative)
		callchain_total = hists->callchain_non_filtered_period;

	min_callchain_hits = callchain_total * (callchain_param.min_percent / 100);
1451

1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462
	hists__reset_stats(hists);
	hists__reset_col_len(hists);

	if (symbol_conf.report_hierarchy) {
		return hists__hierarchy_output_resort(hists, prog,
						      &hists->entries_collapsed,
						      &hists->entries,
						      min_callchain_hits,
						      use_callchain);
	}

1463
	if (sort__need_collapse)
1464 1465 1466 1467 1468 1469
		root = &hists->entries_collapsed;
	else
		root = hists->entries_in;

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

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

1475
		__hists__insert_output_entry(&hists->entries, n, min_callchain_hits, use_callchain);
1476
		hists__inc_stats(hists, n);
1477 1478 1479

		if (!n->filtered)
			hists__calc_col_len(hists, n);
1480 1481 1482

		if (prog)
			ui_progress__update(prog, 1);
1483
	}
1484
}
1485

1486
void perf_evsel__output_resort(struct perf_evsel *evsel, struct ui_progress *prog)
1487 1488 1489 1490 1491 1492 1493 1494
{
	bool use_callchain;

	if (evsel && symbol_conf.use_callchain && !symbol_conf.show_ref_callgraph)
		use_callchain = evsel->attr.sample_type & PERF_SAMPLE_CALLCHAIN;
	else
		use_callchain = symbol_conf.use_callchain;

1495 1496 1497 1498 1499 1500
	output_resort(evsel__hists(evsel), prog, use_callchain);
}

void hists__output_resort(struct hists *hists, struct ui_progress *prog)
{
	output_resort(hists, prog, symbol_conf.use_callchain);
1501 1502
}

1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558
static bool can_goto_child(struct hist_entry *he, enum hierarchy_move_dir hmd)
{
	if (he->leaf || hmd == HMD_FORCE_SIBLING)
		return false;

	if (he->unfolded || hmd == HMD_FORCE_CHILD)
		return true;

	return false;
}

struct rb_node *rb_hierarchy_last(struct rb_node *node)
{
	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);

	while (can_goto_child(he, HMD_NORMAL)) {
		node = rb_last(&he->hroot_out);
		he = rb_entry(node, struct hist_entry, rb_node);
	}
	return node;
}

struct rb_node *__rb_hierarchy_next(struct rb_node *node, enum hierarchy_move_dir hmd)
{
	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);

	if (can_goto_child(he, hmd))
		node = rb_first(&he->hroot_out);
	else
		node = rb_next(node);

	while (node == NULL) {
		he = he->parent_he;
		if (he == NULL)
			break;

		node = rb_next(&he->rb_node);
	}
	return node;
}

struct rb_node *rb_hierarchy_prev(struct rb_node *node)
{
	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);

	node = rb_prev(node);
	if (node)
		return rb_hierarchy_last(node);

	he = he->parent_he;
	if (he == NULL)
		return NULL;

	return &he->rb_node;
}

1559
static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
1560 1561 1562
				       enum hist_filter filter)
{
	h->filtered &= ~(1 << filter);
1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583

	if (symbol_conf.report_hierarchy) {
		struct hist_entry *parent = h->parent_he;

		while (parent) {
			he_stat__add_stat(&parent->stat, &h->stat);

			parent->filtered &= ~(1 << filter);

			if (parent->filtered)
				goto next;

			/* force fold unfiltered entry for simplicity */
			parent->unfolded = false;
			parent->row_offset = 0;
			parent->nr_rows = 0;
next:
			parent = parent->parent_he;
		}
	}

1584 1585 1586
	if (h->filtered)
		return;

1587
	/* force fold unfiltered entry for simplicity */
1588
	h->unfolded = false;
1589
	h->row_offset = 0;
1590
	h->nr_rows = 0;
1591

1592
	hists->stats.nr_non_filtered_samples += h->stat.nr_events;
1593

1594
	hists__inc_filter_stats(hists, h);
1595
	hists__calc_col_len(hists, h);
1596 1597
}

1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622

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

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

1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635
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;
}

1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647
static bool hists__filter_entry_by_socket(struct hists *hists,
					  struct hist_entry *he)
{
	if ((hists->socket_filter > -1) &&
	    (he->socket != hists->socket_filter)) {
		he->filtered |= (1 << HIST_FILTER__SOCKET);
		return true;
	}

	return false;
}

1648 1649 1650
typedef bool (*filter_fn_t)(struct hists *hists, struct hist_entry *he);

static void hists__filter_by_type(struct hists *hists, int type, filter_fn_t filter)
1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661
{
	struct rb_node *nd;

	hists->stats.nr_non_filtered_samples = 0;

	hists__reset_filter_stats(hists);
	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);

1662
		if (filter(hists, h))
1663 1664
			continue;

1665
		hists__remove_entry_filter(hists, h, type);
1666 1667 1668
	}
}

1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705
static void resort_filtered_entry(struct rb_root *root, struct hist_entry *he)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct hist_entry *iter;
	struct rb_root new_root = RB_ROOT;
	struct rb_node *nd;

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

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

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

	if (he->leaf || he->filtered)
		return;

	nd = rb_first(&he->hroot_out);
	while (nd) {
		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);

		nd = rb_next(nd);
		rb_erase(&h->rb_node, &he->hroot_out);

		resort_filtered_entry(&new_root, h);
	}

	he->hroot_out = new_root;
}

1706 1707 1708
static void hists__filter_hierarchy(struct hists *hists, int type, const void *arg)
{
	struct rb_node *nd;
1709
	struct rb_root new_root = RB_ROOT;
1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752

	hists->stats.nr_non_filtered_samples = 0;

	hists__reset_filter_stats(hists);
	hists__reset_col_len(hists);

	nd = rb_first(&hists->entries);
	while (nd) {
		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
		int ret;

		ret = hist_entry__filter(h, type, arg);

		/*
		 * case 1. non-matching type
		 * zero out the period, set filter marker and move to child
		 */
		if (ret < 0) {
			memset(&h->stat, 0, sizeof(h->stat));
			h->filtered |= (1 << type);

			nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_CHILD);
		}
		/*
		 * case 2. matched type (filter out)
		 * set filter marker and move to next
		 */
		else if (ret == 1) {
			h->filtered |= (1 << type);

			nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_SIBLING);
		}
		/*
		 * case 3. ok (not filtered)
		 * add period to hists and parents, erase the filter marker
		 * and move to next sibling
		 */
		else {
			hists__remove_entry_filter(hists, h, type);

			nd = __rb_hierarchy_next(&h->rb_node, HMD_FORCE_SIBLING);
		}
	}
1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768

	/*
	 * resort output after applying a new filter since filter in a lower
	 * hierarchy can change periods in a upper hierarchy.
	 */
	nd = rb_first(&hists->entries);
	while (nd) {
		struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);

		nd = rb_next(nd);
		rb_erase(&h->rb_node, &hists->entries);

		resort_filtered_entry(&new_root, h);
	}

	hists->entries = new_root;
1769 1770
}

1771 1772
void hists__filter_by_thread(struct hists *hists)
{
1773 1774 1775 1776 1777 1778
	if (symbol_conf.report_hierarchy)
		hists__filter_hierarchy(hists, HIST_FILTER__THREAD,
					hists->thread_filter);
	else
		hists__filter_by_type(hists, HIST_FILTER__THREAD,
				      hists__filter_entry_by_thread);
1779 1780 1781 1782
}

void hists__filter_by_dso(struct hists *hists)
{
1783 1784 1785 1786 1787 1788
	if (symbol_conf.report_hierarchy)
		hists__filter_hierarchy(hists, HIST_FILTER__DSO,
					hists->dso_filter);
	else
		hists__filter_by_type(hists, HIST_FILTER__DSO,
				      hists__filter_entry_by_dso);
1789 1790 1791 1792
}

void hists__filter_by_symbol(struct hists *hists)
{
1793 1794 1795 1796 1797 1798
	if (symbol_conf.report_hierarchy)
		hists__filter_hierarchy(hists, HIST_FILTER__SYMBOL,
					hists->symbol_filter_str);
	else
		hists__filter_by_type(hists, HIST_FILTER__SYMBOL,
				      hists__filter_entry_by_symbol);
1799 1800 1801 1802
}

void hists__filter_by_socket(struct hists *hists)
{
1803 1804 1805 1806 1807 1808
	if (symbol_conf.report_hierarchy)
		hists__filter_hierarchy(hists, HIST_FILTER__SOCKET,
					&hists->socket_filter);
	else
		hists__filter_by_type(hists, HIST_FILTER__SOCKET,
				      hists__filter_entry_by_socket);
1809 1810
}

1811 1812 1813 1814 1815 1816
void events_stats__inc(struct events_stats *stats, u32 type)
{
	++stats->nr_events[0];
	++stats->nr_events[type];
}

1817
void hists__inc_nr_events(struct hists *hists, u32 type)
1818
{
1819
	events_stats__inc(&hists->stats, type);
1820
}
1821

1822 1823 1824 1825 1826 1827 1828
void hists__inc_nr_samples(struct hists *hists, bool filtered)
{
	events_stats__inc(&hists->stats, PERF_RECORD_SAMPLE);
	if (!filtered)
		hists->stats.nr_non_filtered_samples++;
}

1829 1830 1831
static struct hist_entry *hists__add_dummy_entry(struct hists *hists,
						 struct hist_entry *pair)
{
1832 1833
	struct rb_root *root;
	struct rb_node **p;
1834 1835
	struct rb_node *parent = NULL;
	struct hist_entry *he;
1836
	int64_t cmp;
1837

1838 1839 1840 1841 1842 1843 1844
	if (sort__need_collapse)
		root = &hists->entries_collapsed;
	else
		root = hists->entries_in;

	p = &root->rb_node;

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

1849
		cmp = hist_entry__collapse(he, pair);
1850 1851 1852 1853 1854 1855 1856 1857 1858 1859

		if (!cmp)
			goto out;

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

1860
	he = hist_entry__new(pair, true);
1861
	if (he) {
1862 1863
		memset(&he->stat, 0, sizeof(he->stat));
		he->hists = hists;
1864 1865
		rb_link_node(&he->rb_node_in, parent, p);
		rb_insert_color(&he->rb_node_in, root);
1866
		hists__inc_stats(hists, he);
1867
		he->dummy = true;
1868 1869 1870 1871 1872
	}
out:
	return he;
}

1873 1874 1875
static struct hist_entry *hists__find_entry(struct hists *hists,
					    struct hist_entry *he)
{
1876 1877 1878 1879 1880 1881
	struct rb_node *n;

	if (sort__need_collapse)
		n = hists->entries_collapsed.rb_node;
	else
		n = hists->entries_in->rb_node;
1882 1883

	while (n) {
1884 1885
		struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in);
		int64_t cmp = hist_entry__collapse(iter, he);
1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902

		if (cmp < 0)
			n = n->rb_left;
		else if (cmp > 0)
			n = n->rb_right;
		else
			return iter;
	}

	return NULL;
}

/*
 * Look for pairs to link to the leader buckets (hist_entries):
 */
void hists__match(struct hists *leader, struct hists *other)
{
1903
	struct rb_root *root;
1904 1905 1906
	struct rb_node *nd;
	struct hist_entry *pos, *pair;

1907 1908 1909 1910 1911 1912 1913
	if (sort__need_collapse)
		root = &leader->entries_collapsed;
	else
		root = leader->entries_in;

	for (nd = rb_first(root); nd; nd = rb_next(nd)) {
		pos  = rb_entry(nd, struct hist_entry, rb_node_in);
1914 1915 1916
		pair = hists__find_entry(other, pos);

		if (pair)
1917
			hist_entry__add_pair(pair, pos);
1918 1919
	}
}
1920 1921 1922 1923 1924 1925 1926 1927

/*
 * Look for entries in the other hists that are not present in the leader, if
 * we find them, just add a dummy entry on the leader hists, with period=0,
 * nr_events=0, to serve as the list header.
 */
int hists__link(struct hists *leader, struct hists *other)
{
1928
	struct rb_root *root;
1929 1930 1931
	struct rb_node *nd;
	struct hist_entry *pos, *pair;

1932 1933 1934 1935 1936 1937 1938
	if (sort__need_collapse)
		root = &other->entries_collapsed;
	else
		root = other->entries_in;

	for (nd = rb_first(root); nd; nd = rb_next(nd)) {
		pos = rb_entry(nd, struct hist_entry, rb_node_in);
1939 1940 1941 1942 1943

		if (!hist_entry__has_pairs(pos)) {
			pair = hists__add_dummy_entry(leader, pos);
			if (pair == NULL)
				return -1;
1944
			hist_entry__add_pair(pos, pair);
1945 1946 1947 1948 1949
		}
	}

	return 0;
}
1950

1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983
void hist__account_cycles(struct branch_stack *bs, struct addr_location *al,
			  struct perf_sample *sample, bool nonany_branch_mode)
{
	struct branch_info *bi;

	/* If we have branch cycles always annotate them. */
	if (bs && bs->nr && bs->entries[0].flags.cycles) {
		int i;

		bi = sample__resolve_bstack(sample, al);
		if (bi) {
			struct addr_map_symbol *prev = NULL;

			/*
			 * Ignore errors, still want to process the
			 * other entries.
			 *
			 * For non standard branch modes always
			 * force no IPC (prev == NULL)
			 *
			 * Note that perf stores branches reversed from
			 * program order!
			 */
			for (i = bs->nr - 1; i >= 0; i--) {
				addr_map_symbol__account_cycles(&bi[i].from,
					nonany_branch_mode ? NULL : prev,
					bi[i].flags.cycles);
				prev = &bi[i].to;
			}
			free(bi);
		}
	}
}
1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998

size_t perf_evlist__fprintf_nr_events(struct perf_evlist *evlist, FILE *fp)
{
	struct perf_evsel *pos;
	size_t ret = 0;

	evlist__for_each(evlist, pos) {
		ret += fprintf(fp, "%s stats:\n", perf_evsel__name(pos));
		ret += events_stats__fprintf(&evsel__hists(pos)->stats, fp);
	}

	return ret;
}


1999 2000 2001 2002 2003
u64 hists__total_period(struct hists *hists)
{
	return symbol_conf.filter_relative ? hists->stats.total_non_filtered_period :
		hists->stats.total_period;
}
N
Namhyung Kim 已提交
2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016

int parse_filter_percentage(const struct option *opt __maybe_unused,
			    const char *arg, int unset __maybe_unused)
{
	if (!strcmp(arg, "relative"))
		symbol_conf.filter_relative = true;
	else if (!strcmp(arg, "absolute"))
		symbol_conf.filter_relative = false;
	else
		return -1;

	return 0;
}
2017 2018 2019 2020 2021 2022 2023 2024

int perf_hist_config(const char *var, const char *value)
{
	if (!strcmp(var, "hist.percentage"))
		return parse_filter_percentage(NULL, value, 0);

	return 0;
}
2025

2026
int __hists__init(struct hists *hists, struct perf_hpp_list *hpp_list)
2027 2028 2029 2030 2031 2032 2033
{
	memset(hists, 0, sizeof(*hists));
	hists->entries_in_array[0] = hists->entries_in_array[1] = RB_ROOT;
	hists->entries_in = &hists->entries_in_array[0];
	hists->entries_collapsed = RB_ROOT;
	hists->entries = RB_ROOT;
	pthread_mutex_init(&hists->lock, NULL);
2034
	hists->socket_filter = -1;
2035
	hists->hpp_list = hpp_list;
2036 2037 2038
	return 0;
}

2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060
static void hists__delete_remaining_entries(struct rb_root *root)
{
	struct rb_node *node;
	struct hist_entry *he;

	while (!RB_EMPTY_ROOT(root)) {
		node = rb_first(root);
		rb_erase(node, root);

		he = rb_entry(node, struct hist_entry, rb_node_in);
		hist_entry__delete(he);
	}
}

static void hists__delete_all_entries(struct hists *hists)
{
	hists__delete_entries(hists);
	hists__delete_remaining_entries(&hists->entries_in_array[0]);
	hists__delete_remaining_entries(&hists->entries_in_array[1]);
	hists__delete_remaining_entries(&hists->entries_collapsed);
}

2061 2062 2063 2064
static void hists_evsel__exit(struct perf_evsel *evsel)
{
	struct hists *hists = evsel__hists(evsel);

2065
	hists__delete_all_entries(hists);
2066 2067
}

2068 2069 2070 2071
static int hists_evsel__init(struct perf_evsel *evsel)
{
	struct hists *hists = evsel__hists(evsel);

2072
	__hists__init(hists, &perf_hpp_list);
2073 2074 2075
	return 0;
}

2076 2077 2078 2079 2080 2081 2082 2083
/*
 * XXX We probably need a hists_evsel__exit() to free the hist_entries
 * stored in the rbtree...
 */

int hists__init(void)
{
	int err = perf_evsel__object_config(sizeof(struct hists_evsel),
2084 2085
					    hists_evsel__init,
					    hists_evsel__exit);
2086 2087 2088 2089 2090
	if (err)
		fputs("FATAL ERROR: Couldn't setup hists class\n", stderr);

	return err;
}
2091 2092 2093 2094 2095 2096

void perf_hpp_list__init(struct perf_hpp_list *list)
{
	INIT_LIST_HEAD(&list->fields);
	INIT_LIST_HEAD(&list->sorts);
}