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