linux - tools/perf/util/hist.c

3100 lines · 75.6 KiB

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