hist.c 41.8 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
static void __hists__insert_output_entry(struct rb_root *entries,
					 struct hist_entry *he,
1323 1324
					 u64 min_callchain_hits,
					 bool use_callchain)
1325
{
1326
	struct rb_node **p = &entries->rb_node;
1327 1328 1329
	struct rb_node *parent = NULL;
	struct hist_entry *iter;

1330 1331 1332 1333 1334 1335 1336 1337 1338
	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);
		}
1339
		callchain_param.sort(&he->sorted_chain, he->callchain,
1340
				      min_callchain_hits, &callchain_param);
1341
	}
1342 1343 1344 1345 1346

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

1347
		if (hist_entry__sort(he, iter) > 0)
1348 1349 1350 1351 1352 1353
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

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

1357 1358
static void output_resort(struct hists *hists, struct ui_progress *prog,
			  bool use_callchain)
1359
{
1360
	struct rb_root *root;
1361 1362
	struct rb_node *next;
	struct hist_entry *n;
1363
	u64 callchain_total;
1364 1365
	u64 min_callchain_hits;

1366 1367 1368 1369 1370
	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);
1371

1372
	if (sort__need_collapse)
1373 1374 1375 1376 1377 1378
		root = &hists->entries_collapsed;
	else
		root = hists->entries_in;

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

1380
	hists__reset_stats(hists);
1381
	hists__reset_col_len(hists);
1382

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

1387
		__hists__insert_output_entry(&hists->entries, n, min_callchain_hits, use_callchain);
1388
		hists__inc_stats(hists, n);
1389 1390 1391

		if (!n->filtered)
			hists__calc_col_len(hists, n);
1392 1393 1394

		if (prog)
			ui_progress__update(prog, 1);
1395
	}
1396
}
1397

1398
void perf_evsel__output_resort(struct perf_evsel *evsel, struct ui_progress *prog)
1399 1400 1401 1402 1403 1404 1405 1406
{
	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;

1407 1408 1409 1410 1411 1412
	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);
1413 1414
}

1415
static void hists__remove_entry_filter(struct hists *hists, struct hist_entry *h,
1416 1417 1418 1419 1420 1421
				       enum hist_filter filter)
{
	h->filtered &= ~(1 << filter);
	if (h->filtered)
		return;

1422
	/* force fold unfiltered entry for simplicity */
1423
	h->unfolded = false;
1424
	h->row_offset = 0;
1425
	h->nr_rows = 0;
1426

1427
	hists->stats.nr_non_filtered_samples += h->stat.nr_events;
1428

1429
	hists__inc_filter_stats(hists, h);
1430
	hists__calc_col_len(hists, h);
1431 1432
}

1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457

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

1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470
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;
}

1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482
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;
}

1483 1484 1485
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)
1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496
{
	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);

1497
		if (filter(hists, h))
1498 1499
			continue;

1500
		hists__remove_entry_filter(hists, h, type);
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
void hists__filter_by_thread(struct hists *hists)
{
	hists__filter_by_type(hists, HIST_FILTER__THREAD,
			      hists__filter_entry_by_thread);
}

void hists__filter_by_dso(struct hists *hists)
{
	hists__filter_by_type(hists, HIST_FILTER__DSO,
			      hists__filter_entry_by_dso);
}

void hists__filter_by_symbol(struct hists *hists)
{
	hists__filter_by_type(hists, HIST_FILTER__SYMBOL,
			      hists__filter_entry_by_symbol);
}

void hists__filter_by_socket(struct hists *hists)
{
	hists__filter_by_type(hists, HIST_FILTER__SOCKET,
			      hists__filter_entry_by_socket);
}

1528 1529 1530 1531 1532 1533
void events_stats__inc(struct events_stats *stats, u32 type)
{
	++stats->nr_events[0];
	++stats->nr_events[type];
}

1534
void hists__inc_nr_events(struct hists *hists, u32 type)
1535
{
1536
	events_stats__inc(&hists->stats, type);
1537
}
1538

1539 1540 1541 1542 1543 1544 1545
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++;
}

1546 1547 1548
static struct hist_entry *hists__add_dummy_entry(struct hists *hists,
						 struct hist_entry *pair)
{
1549 1550
	struct rb_root *root;
	struct rb_node **p;
1551 1552
	struct rb_node *parent = NULL;
	struct hist_entry *he;
1553
	int64_t cmp;
1554

1555 1556 1557 1558 1559 1560 1561
	if (sort__need_collapse)
		root = &hists->entries_collapsed;
	else
		root = hists->entries_in;

	p = &root->rb_node;

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

1566
		cmp = hist_entry__collapse(he, pair);
1567 1568 1569 1570 1571 1572 1573 1574 1575 1576

		if (!cmp)
			goto out;

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

1577
	he = hist_entry__new(pair, true);
1578
	if (he) {
1579 1580
		memset(&he->stat, 0, sizeof(he->stat));
		he->hists = hists;
1581 1582
		rb_link_node(&he->rb_node_in, parent, p);
		rb_insert_color(&he->rb_node_in, root);
1583
		hists__inc_stats(hists, he);
1584
		he->dummy = true;
1585 1586 1587 1588 1589
	}
out:
	return he;
}

1590 1591 1592
static struct hist_entry *hists__find_entry(struct hists *hists,
					    struct hist_entry *he)
{
1593 1594 1595 1596 1597 1598
	struct rb_node *n;

	if (sort__need_collapse)
		n = hists->entries_collapsed.rb_node;
	else
		n = hists->entries_in->rb_node;
1599 1600

	while (n) {
1601 1602
		struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in);
		int64_t cmp = hist_entry__collapse(iter, he);
1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619

		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)
{
1620
	struct rb_root *root;
1621 1622 1623
	struct rb_node *nd;
	struct hist_entry *pos, *pair;

1624 1625 1626 1627 1628 1629 1630
	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);
1631 1632 1633
		pair = hists__find_entry(other, pos);

		if (pair)
1634
			hist_entry__add_pair(pair, pos);
1635 1636
	}
}
1637 1638 1639 1640 1641 1642 1643 1644

/*
 * 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)
{
1645
	struct rb_root *root;
1646 1647 1648
	struct rb_node *nd;
	struct hist_entry *pos, *pair;

1649 1650 1651 1652 1653 1654 1655
	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);
1656 1657 1658 1659 1660

		if (!hist_entry__has_pairs(pos)) {
			pair = hists__add_dummy_entry(leader, pos);
			if (pair == NULL)
				return -1;
1661
			hist_entry__add_pair(pos, pair);
1662 1663 1664 1665 1666
		}
	}

	return 0;
}
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
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);
		}
	}
}
1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715

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


1716 1717 1718 1719 1720
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 已提交
1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733

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;
}
1734 1735 1736 1737 1738 1739 1740 1741

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

	return 0;
}
1742

1743
int __hists__init(struct hists *hists, struct perf_hpp_list *hpp_list)
1744 1745 1746 1747 1748 1749 1750
{
	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);
1751
	hists->socket_filter = -1;
1752
	hists->hpp_list = hpp_list;
1753 1754 1755
	return 0;
}

1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777
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);
}

1778 1779 1780 1781
static void hists_evsel__exit(struct perf_evsel *evsel)
{
	struct hists *hists = evsel__hists(evsel);

1782
	hists__delete_all_entries(hists);
1783 1784
}

1785 1786 1787 1788
static int hists_evsel__init(struct perf_evsel *evsel)
{
	struct hists *hists = evsel__hists(evsel);

1789
	__hists__init(hists, &perf_hpp_list);
1790 1791 1792
	return 0;
}

1793 1794 1795 1796 1797 1798 1799 1800
/*
 * 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),
1801 1802
					    hists_evsel__init,
					    hists_evsel__exit);
1803 1804 1805 1806 1807
	if (err)
		fputs("FATAL ERROR: Couldn't setup hists class\n", stderr);

	return err;
}
1808 1809 1810 1811 1812 1813

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