~hc/RK356X_SDK_RELEASE.git

..	..	@@ -1,22 +1,34 @@
1	1	// SPDX-License-Identifier: GPL-2.0
2		-#include "util.h"
	2	+#include "callchain.h"
	3	+#include "debug.h"
	4	+#include "dso.h"
3	5	#include "build-id.h"
4	6	#include "hist.h"
5	7	#include "map.h"
	8	+#include "map_symbol.h"
	9	+#include "branch.h"
	10	+#include "mem-events.h"
6	11	#include "session.h"
7	12	#include "namespaces.h"
	13	+#include "cgroup.h"
8	14	#include "sort.h"
9	15	#include "units.h"
10	16	#include "evlist.h"
11	17	#include "evsel.h"
12	18	#include "annotate.h"
13	19	#include "srcline.h"
	20	+#include "symbol.h"
14	21	#include "thread.h"
	22	+#include "block-info.h"
15	23	#include "ui/progress.h"
16	24	#include <errno.h>
17	25	#include <math.h>
18	26	#include <inttypes.h>
19	27	#include <sys/param.h>
	28	+#include <linux/rbtree.h>
	29	+#include <linux/string.h>
	30	+#include <linux/time64.h>
	31	+#include <linux/zalloc.h>
20	32
21	33	static bool hists__filter_entry_by_dso(struct hists *hists,
22	34	struct hist_entry *he);
..	..	@@ -70,6 +82,8 @@
70	82	int symlen;
71	83	u16 len;
72	84
	85	+ if (h->block_info)
	86	+ return;
73	87	/*
74	88	* +4 accounts for '[x] ' priv level info
75	89	* +2 accounts for 0x prefix on raw addresses
..	..	@@ -99,13 +113,13 @@
99	113	hists__new_col_len(hists, HISTC_PARENT, h->parent->namelen);
100	114
101	115	if (h->branch_info) {
102		- if (h->branch_info->from.sym) {
103		- symlen = (int)h->branch_info->from.sym->namelen + 4;
	116	+ if (h->branch_info->from.ms.sym) {
	117	+ symlen = (int)h->branch_info->from.ms.sym->namelen + 4;
104	118	if (verbose > 0)
105	119	symlen += BITS_PER_LONG / 4 + 2 + 3;
106	120	hists__new_col_len(hists, HISTC_SYMBOL_FROM, symlen);
107	121
108		- symlen = dso__name_len(h->branch_info->from.map->dso);
	122	+ symlen = dso__name_len(h->branch_info->from.ms.map->dso);
109	123	hists__new_col_len(hists, HISTC_DSO_FROM, symlen);
110	124	} else {
111	125	symlen = unresolved_col_width + 4 + 2;
..	..	@@ -113,13 +127,13 @@
113	127	hists__set_unres_dso_col_len(hists, HISTC_DSO_FROM);
114	128	}
115	129
116		- if (h->branch_info->to.sym) {
117		- symlen = (int)h->branch_info->to.sym->namelen + 4;
	130	+ if (h->branch_info->to.ms.sym) {
	131	+ symlen = (int)h->branch_info->to.ms.sym->namelen + 4;
118	132	if (verbose > 0)
119	133	symlen += BITS_PER_LONG / 4 + 2 + 3;
120	134	hists__new_col_len(hists, HISTC_SYMBOL_TO, symlen);
121	135
122		- symlen = dso__name_len(h->branch_info->to.map->dso);
	136	+ symlen = dso__name_len(h->branch_info->to.ms.map->dso);
123	137	hists__new_col_len(hists, HISTC_DSO_TO, symlen);
124	138	} else {
125	139	symlen = unresolved_col_width + 4 + 2;
..	..	@@ -136,8 +150,8 @@
136	150	}
137	151
138	152	if (h->mem_info) {
139		- if (h->mem_info->daddr.sym) {
140		- symlen = (int)h->mem_info->daddr.sym->namelen + 4
	153	+ if (h->mem_info->daddr.ms.sym) {
	154	+ symlen = (int)h->mem_info->daddr.ms.sym->namelen + 4
141	155	+ unresolved_col_width + 2;
142	156	hists__new_col_len(hists, HISTC_MEM_DADDR_SYMBOL,
143	157	symlen);
..	..	@@ -151,8 +165,8 @@
151	165	symlen);
152	166	}
153	167
154		- if (h->mem_info->iaddr.sym) {
155		- symlen = (int)h->mem_info->iaddr.sym->namelen + 4
	168	+ if (h->mem_info->iaddr.ms.sym) {
	169	+ symlen = (int)h->mem_info->iaddr.ms.sym->namelen + 4
156	170	+ unresolved_col_width + 2;
157	171	hists__new_col_len(hists, HISTC_MEM_IADDR_SYMBOL,
158	172	symlen);
..	..	@@ -162,8 +176,8 @@
162	176	symlen);
163	177	}
164	178
165		- if (h->mem_info->daddr.map) {
166		- symlen = dso__name_len(h->mem_info->daddr.map->dso);
	179	+ if (h->mem_info->daddr.ms.map) {
	180	+ symlen = dso__name_len(h->mem_info->daddr.ms.map->dso);
167	181	hists__new_col_len(hists, HISTC_MEM_DADDR_DSO,
168	182	symlen);
169	183	} else {
..	..	@@ -181,6 +195,7 @@
181	195	hists__set_unres_dso_col_len(hists, HISTC_MEM_DADDR_DSO);
182	196	}
183	197
	198	+ hists__new_col_len(hists, HISTC_CGROUP, 6);
184	199	hists__new_col_len(hists, HISTC_CGROUP_ID, 20);
185	200	hists__new_col_len(hists, HISTC_CPU, 3);
186	201	hists__new_col_len(hists, HISTC_SOCKET, 6);
..	..	@@ -190,6 +205,10 @@
190	205	hists__new_col_len(hists, HISTC_MEM_LVL, 21 + 3);
191	206	hists__new_col_len(hists, HISTC_LOCAL_WEIGHT, 12);
192	207	hists__new_col_len(hists, HISTC_GLOBAL_WEIGHT, 12);
	208	+ if (symbol_conf.nanosecs)
	209	+ hists__new_col_len(hists, HISTC_TIME, 16);
	210	+ else
	211	+ hists__new_col_len(hists, HISTC_TIME, 12);
193	212
194	213	if (h->srcline) {
195	214	len = MAX(strlen(h->srcline), strlen(sort_srcline.se_header));
..	..	@@ -205,11 +224,21 @@
205	224
206	225	if (h->trace_output)
207	226	hists__new_col_len(hists, HISTC_TRACE, strlen(h->trace_output));
	227	+
	228	+ if (h->cgroup) {
	229	+ const char *cgrp_name = "unknown";
	230	+ struct cgroup *cgrp = cgroup__find(h->ms.maps->machine->env,
	231	+ h->cgroup);
	232	+ if (cgrp != NULL)
	233	+ cgrp_name = cgrp->name;
	234	+
	235	+ hists__new_col_len(hists, HISTC_CGROUP, strlen(cgrp_name));
	236	+ }
208	237	}
209	238
210	239	void hists__output_recalc_col_len(struct hists *hists, int max_rows)
211	240	{
212		- struct rb_node *next = rb_first(&hists->entries);
	241	+ struct rb_node *next = rb_first_cached(&hists->entries);
213	242	struct hist_entry *n;
214	243	int row = 0;
215	244
..	..	@@ -242,6 +271,14 @@
242	271	default:
243	272	break;
244	273	}
	274	+}
	275	+
	276	+static long hist_time(unsigned long htime)
	277	+{
	278	+ unsigned long time_quantum = symbol_conf.time_quantum;
	279	+ if (time_quantum)
	280	+ return (htime / time_quantum) * time_quantum;
	281	+ return htime;
245	282	}
246	283
247	284	static void he_stat__add_period(struct he_stat *he_stat, u64 period,
..	..	@@ -296,7 +333,7 @@
296	333
297	334	if (!he->leaf) {
298	335	struct hist_entry *child;
299		- struct rb_node *node = rb_first(&he->hroot_out);
	336	+ struct rb_node *node = rb_first_cached(&he->hroot_out);
300	337	while (node) {
301	338	child = rb_entry(node, struct hist_entry, rb_node);
302	339	node = rb_next(node);
..	..	@@ -311,8 +348,8 @@
311	348
312	349	static void hists__delete_entry(struct hists hists, struct hist_entry he)
313	350	{
314		- struct rb_root *root_in;
315		- struct rb_root *root_out;
	351	+ struct rb_root_cached *root_in;
	352	+ struct rb_root_cached *root_out;
316	353
317	354	if (he->parent_he) {
318	355	root_in = &he->parent_he->hroot_in;
..	..	@@ -325,8 +362,8 @@
325	362	root_out = &hists->entries;
326	363	}
327	364
328		- rb_erase(&he->rb_node_in, root_in);
329		- rb_erase(&he->rb_node, root_out);
	365	+ rb_erase_cached(&he->rb_node_in, root_in);
	366	+ rb_erase_cached(&he->rb_node, root_out);
330	367
331	368	--hists->nr_entries;
332	369	if (!he->filtered)
..	..	@@ -337,7 +374,7 @@
337	374
338	375	void hists__decay_entries(struct hists *hists, bool zap_user, bool zap_kernel)
339	376	{
340		- struct rb_node *next = rb_first(&hists->entries);
	377	+ struct rb_node *next = rb_first_cached(&hists->entries);
341	378	struct hist_entry *n;
342	379
343	380	while (next) {
..	..	@@ -353,7 +390,7 @@
353	390
354	391	void hists__delete_entries(struct hists *hists)
355	392	{
356		- struct rb_node *next = rb_first(&hists->entries);
	393	+ struct rb_node *next = rb_first_cached(&hists->entries);
357	394	struct hist_entry *n;
358	395
359	396	while (next) {
..	..	@@ -362,6 +399,24 @@
362	399
363	400	hists__delete_entry(hists, n);
364	401	}
	402	+}
	403	+
	404	+struct hist_entry hists__get_entry(struct hists hists, int idx)
	405	+{
	406	+ struct rb_node *next = rb_first_cached(&hists->entries);
	407	+ struct hist_entry *n;
	408	+ int i = 0;
	409	+
	410	+ while (next) {
	411	+ n = rb_entry(next, struct hist_entry, rb_node);
	412	+ if (i == idx)
	413	+ return n;
	414	+
	415	+ next = rb_next(&n->rb_node);
	416	+ i++;
	417	+ }
	418	+
	419	+ return NULL;
365	420	}
366	421
367	422	/*
..	..	@@ -394,22 +449,19 @@
394	449	* adding new entries. So we need to save a copy.
395	450	*/
396	451	he->branch_info = malloc(sizeof(*he->branch_info));
397		- if (he->branch_info == NULL) {
398		- map__zput(he->ms.map);
399		- free(he->stat_acc);
400		- return -ENOMEM;
401		- }
	452	+ if (he->branch_info == NULL)
	453	+ goto err;
402	454
403	455	memcpy(he->branch_info, template->branch_info,
404	456	sizeof(*he->branch_info));
405	457
406		- map__get(he->branch_info->from.map);
407		- map__get(he->branch_info->to.map);
	458	+ map__get(he->branch_info->from.ms.map);
	459	+ map__get(he->branch_info->to.ms.map);
408	460	}
409	461
410	462	if (he->mem_info) {
411		- map__get(he->mem_info->iaddr.map);
412		- map__get(he->mem_info->daddr.map);
	463	+ map__get(he->mem_info->iaddr.ms.map);
	464	+ map__get(he->mem_info->daddr.ms.map);
413	465	}
414	466
415	467	if (hist_entry__has_callchains(he) && symbol_conf.use_callchain)
..	..	@@ -417,31 +469,53 @@
417	469
418	470	if (he->raw_data) {
419	471	he->raw_data = memdup(he->raw_data, he->raw_size);
420		-
421		- if (he->raw_data == NULL) {
422		- map__put(he->ms.map);
423		- if (he->branch_info) {
424		- map__put(he->branch_info->from.map);
425		- map__put(he->branch_info->to.map);
426		- free(he->branch_info);
427		- }
428		- if (he->mem_info) {
429		- map__put(he->mem_info->iaddr.map);
430		- map__put(he->mem_info->daddr.map);
431		- }
432		- free(he->stat_acc);
433		- return -ENOMEM;
434		- }
	472	+ if (he->raw_data == NULL)
	473	+ goto err_infos;
435	474	}
	475	+
	476	+ if (he->srcline) {
	477	+ he->srcline = strdup(he->srcline);
	478	+ if (he->srcline == NULL)
	479	+ goto err_rawdata;
	480	+ }
	481	+
	482	+ if (symbol_conf.res_sample) {
	483	+ he->res_samples = calloc(sizeof(struct res_sample),
	484	+ symbol_conf.res_sample);
	485	+ if (!he->res_samples)
	486	+ goto err_srcline;
	487	+ }
	488	+
436	489	INIT_LIST_HEAD(&he->pairs.node);
437	490	thread__get(he->thread);
438		- he->hroot_in = RB_ROOT;
439		- he->hroot_out = RB_ROOT;
	491	+ he->hroot_in = RB_ROOT_CACHED;
	492	+ he->hroot_out = RB_ROOT_CACHED;
440	493
441	494	if (!symbol_conf.report_hierarchy)
442	495	he->leaf = true;
443	496
444	497	return 0;
	498	+
	499	+err_srcline:
	500	+ zfree(&he->srcline);
	501	+
	502	+err_rawdata:
	503	+ zfree(&he->raw_data);
	504	+
	505	+err_infos:
	506	+ if (he->branch_info) {
	507	+ map__put(he->branch_info->from.ms.map);
	508	+ map__put(he->branch_info->to.ms.map);
	509	+ zfree(&he->branch_info);
	510	+ }
	511	+ if (he->mem_info) {
	512	+ map__put(he->mem_info->iaddr.ms.map);
	513	+ map__put(he->mem_info->daddr.ms.map);
	514	+ }
	515	+err:
	516	+ map__zput(he->ms.map);
	517	+ zfree(&he->stat_acc);
	518	+ return -ENOMEM;
445	519	}
446	520
447	521	static void *hist_entry__zalloc(size_t size)
..	..	@@ -513,8 +587,9 @@
513	587	int64_t cmp;
514	588	u64 period = entry->stat.period;
515	589	u64 weight = entry->stat.weight;
	590	+ bool leftmost = true;
516	591
517		- p = &hists->entries_in->rb_node;
	592	+ p = &hists->entries_in->rb_root.rb_node;
518	593
519	594	while (*p != NULL) {
520	595	parent = *p;
..	..	@@ -542,6 +617,8 @@
542	617	*/
543	618	mem_info__zput(entry->mem_info);
544	619
	620	+ block_info__zput(entry->block_info);
	621	+
545	622	/* If the map of an existing hist_entry has
546	623	* become out-of-date due to an exec() or
547	624	* similar, update it. Otherwise we will
..	..	@@ -557,8 +634,10 @@
557	634
558	635	if (cmp < 0)
559	636	p = &(*p)->rb_left;
560		- else
	637	+ else {
561	638	p = &(*p)->rb_right;
	639	+ leftmost = false;
	640	+ }
562	641	}
563	642
564	643	he = hist_entry__new(entry, sample_self);
..	..	@@ -570,7 +649,7 @@
570	649	hists->nr_entries++;
571	650
572	651	rb_link_node(&he->rb_node_in, parent, p);
573		- rb_insert_color(&he->rb_node_in, hists->entries_in);
	652	+ rb_insert_color_cached(&he->rb_node_in, hists->entries_in, leftmost);
574	653	out:
575	654	if (sample_self)
576	655	he_stat__add_cpumode_period(&he->stat, al->cpumode, period);
..	..	@@ -579,12 +658,39 @@
579	658	return he;
580	659	}
581	660
	661	+static unsigned random_max(unsigned high)
	662	+{
	663	+ unsigned thresh = -high % high;
	664	+ for (;;) {
	665	+ unsigned r = random();
	666	+ if (r >= thresh)
	667	+ return r % high;
	668	+ }
	669	+}
	670	+
	671	+static void hists__res_sample(struct hist_entry he, struct perf_sample sample)
	672	+{
	673	+ struct res_sample *r;
	674	+ int j;
	675	+
	676	+ if (he->num_res < symbol_conf.res_sample) {
	677	+ j = he->num_res++;
	678	+ } else {
	679	+ j = random_max(symbol_conf.res_sample);
	680	+ }
	681	+ r = &he->res_samples[j];
	682	+ r->time = sample->time;
	683	+ r->cpu = sample->cpu;
	684	+ r->tid = sample->tid;
	685	+}
	686	+
582	687	static struct hist_entry*
583	688	__hists__add_entry(struct hists *hists,
584	689	struct addr_location *al,
585	690	struct symbol *sym_parent,
586	691	struct branch_info *bi,
587	692	struct mem_info *mi,
	693	+ struct block_info *block_info,
588	694	struct perf_sample *sample,
589	695	bool sample_self,
590	696	struct hist_entry_ops *ops)
..	..	@@ -597,11 +703,13 @@
597	703	.dev = ns ? ns->link_info[CGROUP_NS_INDEX].dev : 0,
598	704	.ino = ns ? ns->link_info[CGROUP_NS_INDEX].ino : 0,
599	705	},
	706	+ .cgroup = sample->cgroup,
600	707	.ms = {
	708	+ .maps = al->maps,
601	709	.map = al->map,
602	710	.sym = al->sym,
603	711	},
604		- .srcline = al->srcline ? strdup(al->srcline) : NULL,
	712	+ .srcline = (char *) al->srcline,
605	713	.socket = al->socket,
606	714	.cpu = al->cpu,
607	715	.cpumode = al->cpumode,
..	..	@@ -617,14 +725,18 @@
617	725	.hists = hists,
618	726	.branch_info = bi,
619	727	.mem_info = mi,
	728	+ .block_info = block_info,
620	729	.transaction = sample->transaction,
621	730	.raw_data = sample->raw_data,
622	731	.raw_size = sample->raw_size,
623	732	.ops = ops,
	733	+ .time = hist_time(sample->time),
624	734	}, *he = hists__findnew_entry(hists, &entry, al, sample_self);
625	735
626	736	if (!hists->has_callchains && he && he->callchain_size != 0)
627	737	hists->has_callchains = true;
	738	+ if (he && symbol_conf.res_sample)
	739	+ hists__res_sample(he, sample);
628	740	return he;
629	741	}
630	742
..	..	@@ -636,7 +748,7 @@
636	748	struct perf_sample *sample,
637	749	bool sample_self)
638	750	{
639		- return __hists__add_entry(hists, al, sym_parent, bi, mi,
	751	+ return __hists__add_entry(hists, al, sym_parent, bi, mi, NULL,
640	752	sample, sample_self, NULL);
641	753	}
642	754
..	..	@@ -649,8 +761,25 @@
649	761	struct perf_sample *sample,
650	762	bool sample_self)
651	763	{
652		- return __hists__add_entry(hists, al, sym_parent, bi, mi,
	764	+ return __hists__add_entry(hists, al, sym_parent, bi, mi, NULL,
653	765	sample, sample_self, ops);
	766	+}
	767	+
	768	+struct hist_entry hists__add_entry_block(struct hists hists,
	769	+ struct addr_location *al,
	770	+ struct block_info *block_info)
	771	+{
	772	+ struct hist_entry entry = {
	773	+ .block_info = block_info,
	774	+ .hists = hists,
	775	+ .ms = {
	776	+ .maps = al->maps,
	777	+ .map = al->map,
	778	+ .sym = al->sym,
	779	+ },
	780	+ }, *he = hists__findnew_entry(hists, &entry, al, false);
	781	+
	782	+ return he;
654	783	}
655	784
656	785	static int
..	..	@@ -719,7 +848,7 @@
719	848	iter_finish_mem_entry(struct hist_entry_iter *iter,
720	849	struct addr_location *al __maybe_unused)
721	850	{
722		- struct perf_evsel *evsel = iter->evsel;
	851	+ struct evsel *evsel = iter->evsel;
723	852	struct hists *hists = evsel__hists(evsel);
724	853	struct hist_entry *he = iter->he;
725	854	int err = -EINVAL;
..	..	@@ -779,8 +908,9 @@
779	908	if (iter->curr >= iter->total)
780	909	return 0;
781	910
782		- al->map = bi[i].to.map;
783		- al->sym = bi[i].to.sym;
	911	+ al->maps = bi[i].to.ms.maps;
	912	+ al->map = bi[i].to.ms.map;
	913	+ al->sym = bi[i].to.ms.sym;
784	914	al->addr = bi[i].to.addr;
785	915	return 1;
786	916	}
..	..	@@ -789,7 +919,7 @@
789	919	iter_add_next_branch_entry(struct hist_entry_iter iter, struct addr_location al)
790	920	{
791	921	struct branch_info *bi;
792		- struct perf_evsel *evsel = iter->evsel;
	922	+ struct evsel *evsel = iter->evsel;
793	923	struct hists *hists = evsel__hists(evsel);
794	924	struct perf_sample *sample = iter->sample;
795	925	struct hist_entry *he = NULL;
..	..	@@ -798,7 +928,7 @@
798	928
799	929	bi = iter->priv;
800	930
801		- if (iter->hide_unresolved && !(bi[i].from.sym && bi[i].to.sym))
	931	+ if (iter->hide_unresolved && !(bi[i].from.ms.sym && bi[i].to.ms.sym))
802	932	goto out;
803	933
804	934	/*
..	..	@@ -841,7 +971,7 @@
841	971	static int
842	972	iter_add_single_normal_entry(struct hist_entry_iter iter, struct addr_location al)
843	973	{
844		- struct perf_evsel *evsel = iter->evsel;
	974	+ struct evsel *evsel = iter->evsel;
845	975	struct perf_sample *sample = iter->sample;
846	976	struct hist_entry *he;
847	977
..	..	@@ -859,7 +989,7 @@
859	989	struct addr_location *al __maybe_unused)
860	990	{
861	991	struct hist_entry *he = iter->he;
862		- struct perf_evsel *evsel = iter->evsel;
	992	+ struct evsel *evsel = iter->evsel;
863	993	struct perf_sample *sample = iter->sample;
864	994
865	995	if (he == NULL)
..	..	@@ -899,7 +1029,7 @@
899	1029	iter_add_single_cumulative_entry(struct hist_entry_iter *iter,
900	1030	struct addr_location *al)
901	1031	{
902		- struct perf_evsel *evsel = iter->evsel;
	1032	+ struct evsel *evsel = iter->evsel;
903	1033	struct hists *hists = evsel__hists(evsel);
904	1034	struct perf_sample *sample = iter->sample;
905	1035	struct hist_entry **he_cache = iter->priv;
..	..	@@ -940,11 +1070,25 @@
940	1070	return fill_callchain_info(al, node, iter->hide_unresolved);
941	1071	}
942	1072
	1073	+static bool
	1074	+hist_entry__fast__sym_diff(struct hist_entry *left,
	1075	+ struct hist_entry *right)
	1076	+{
	1077	+ struct symbol *sym_l = left->ms.sym;
	1078	+ struct symbol *sym_r = right->ms.sym;
	1079	+
	1080	+ if (!sym_l && !sym_r)
	1081	+ return left->ip != right->ip;
	1082	+
	1083	+ return !!_sort__sym_cmp(sym_l, sym_r);
	1084	+}
	1085	+
	1086	+
943	1087	static int
944	1088	iter_add_next_cumulative_entry(struct hist_entry_iter *iter,
945	1089	struct addr_location *al)
946	1090	{
947		- struct perf_evsel *evsel = iter->evsel;
	1091	+ struct evsel *evsel = iter->evsel;
948	1092	struct perf_sample *sample = iter->sample;
949	1093	struct hist_entry **he_cache = iter->priv;
950	1094	struct hist_entry *he;
..	..	@@ -955,16 +1099,18 @@
955	1099	.comm = thread__comm(al->thread),
956	1100	.ip = al->addr,
957	1101	.ms = {
	1102	+ .maps = al->maps,
958	1103	.map = al->map,
959	1104	.sym = al->sym,
960	1105	},
961		- .srcline = al->srcline ? strdup(al->srcline) : NULL,
	1106	+ .srcline = (char *) al->srcline,
962	1107	.parent = iter->parent,
963	1108	.raw_data = sample->raw_data,
964	1109	.raw_size = sample->raw_size,
965	1110	};
966	1111	int i;
967	1112	struct callchain_cursor cursor;
	1113	+ bool fast = hists__has(he_tmp.hists, sym);
968	1114
969	1115	callchain_cursor_snapshot(&cursor, &callchain_cursor);
970	1116
..	..	@@ -975,6 +1121,14 @@
975	1121	* It's possible that it has cycles or recursive calls.
976	1122	*/
977	1123	for (i = 0; i < iter->curr; i++) {
	1124	+ /*
	1125	+ * For most cases, there are no duplicate entries in callchain.
	1126	+ * The symbols are usually different. Do a quick check for
	1127	+ * symbols first.
	1128	+ */
	1129	+ if (fast && hist_entry__fast__sym_diff(he_cache[i], &he_tmp))
	1130	+ continue;
	1131	+
978	1132	if (hist_entry__cmp(he_cache[i], &he_tmp) == 0) {
979	1133	/* to avoid calling callback function */
980	1134	iter->he = NULL;
..	..	@@ -1137,32 +1291,36 @@
1137	1291	map__zput(he->ms.map);
1138	1292
1139	1293	if (he->branch_info) {
1140		- map__zput(he->branch_info->from.map);
1141		- map__zput(he->branch_info->to.map);
	1294	+ map__zput(he->branch_info->from.ms.map);
	1295	+ map__zput(he->branch_info->to.ms.map);
1142	1296	free_srcline(he->branch_info->srcline_from);
1143	1297	free_srcline(he->branch_info->srcline_to);
1144	1298	zfree(&he->branch_info);
1145	1299	}
1146	1300
1147	1301	if (he->mem_info) {
1148		- map__zput(he->mem_info->iaddr.map);
1149		- map__zput(he->mem_info->daddr.map);
	1302	+ map__zput(he->mem_info->iaddr.ms.map);
	1303	+ map__zput(he->mem_info->daddr.ms.map);
1150	1304	mem_info__zput(he->mem_info);
1151	1305	}
1152	1306
	1307	+ if (he->block_info)
	1308	+ block_info__zput(he->block_info);
	1309	+
	1310	+ zfree(&he->res_samples);
1153	1311	zfree(&he->stat_acc);
1154	1312	free_srcline(he->srcline);
1155	1313	if (he->srcfile && he->srcfile[0])
1156		- free(he->srcfile);
	1314	+ zfree(&he->srcfile);
1157	1315	free_callchain(he->callchain);
1158		- free(he->trace_output);
1159		- free(he->raw_data);
	1316	+ zfree(&he->trace_output);
	1317	+ zfree(&he->raw_data);
1160	1318	ops->free(he);
1161	1319	}
1162	1320
1163	1321	/*
1164	1322	* If this is not the last column, then we need to pad it according to the
1165		- * pre-calculated max lenght for this column, otherwise don't bother adding
	1323	+ * pre-calculated max length for this column, otherwise don't bother adding
1166	1324	* spaces because that would break viewing this with, for instance, 'less',
1167	1325	* that would show tons of trailing spaces when a long C++ demangled method
1168	1326	* names is sampled.
..	..	@@ -1281,16 +1439,17 @@
1281	1439	}
1282	1440
1283	1441	static struct hist_entry hierarchy_insert_entry(struct hists hists,
1284		- struct rb_root *root,
	1442	+ struct rb_root_cached *root,
1285	1443	struct hist_entry *he,
1286	1444	struct hist_entry *parent_he,
1287	1445	struct perf_hpp_list *hpp_list)
1288	1446	{
1289		- struct rb_node **p = &root->rb_node;
	1447	+ struct rb_node **p = &root->rb_root.rb_node;
1290	1448	struct rb_node *parent = NULL;
1291	1449	struct hist_entry iter, new;
1292	1450	struct perf_hpp_fmt *fmt;
1293	1451	int64_t cmp;
	1452	+ bool leftmost = true;
1294	1453
1295	1454	while (*p != NULL) {
1296	1455	parent = *p;
..	..	@@ -1310,8 +1469,10 @@
1310	1469
1311	1470	if (cmp < 0)
1312	1471	p = &parent->rb_left;
1313		- else
	1472	+ else {
1314	1473	p = &parent->rb_right;
	1474	+ leftmost = false;
	1475	+ }
1315	1476	}
1316	1477
1317	1478	new = hist_entry__new(he, true);
..	..	@@ -1345,12 +1506,12 @@
1345	1506	}
1346	1507
1347	1508	rb_link_node(&new->rb_node_in, parent, p);
1348		- rb_insert_color(&new->rb_node_in, root);
	1509	+ rb_insert_color_cached(&new->rb_node_in, root, leftmost);
1349	1510	return new;
1350	1511	}
1351	1512
1352	1513	static int hists__hierarchy_insert_entry(struct hists *hists,
1353		- struct rb_root *root,
	1514	+ struct rb_root_cached *root,
1354	1515	struct hist_entry *he)
1355	1516	{
1356	1517	struct perf_hpp_list_node *node;
..	..	@@ -1397,13 +1558,14 @@
1397	1558	}
1398	1559
1399	1560	static int hists__collapse_insert_entry(struct hists *hists,
1400		- struct rb_root *root,
	1561	+ struct rb_root_cached *root,
1401	1562	struct hist_entry *he)
1402	1563	{
1403		- struct rb_node **p = &root->rb_node;
	1564	+ struct rb_node **p = &root->rb_root.rb_node;
1404	1565	struct rb_node *parent = NULL;
1405	1566	struct hist_entry *iter;
1406	1567	int64_t cmp;
	1568	+ bool leftmost = true;
1407	1569
1408	1570	if (symbol_conf.report_hierarchy)
1409	1571	return hists__hierarchy_insert_entry(hists, root, he);
..	..	@@ -1434,19 +1596,21 @@
1434	1596
1435	1597	if (cmp < 0)
1436	1598	p = &(*p)->rb_left;
1437		- else
	1599	+ else {
1438	1600	p = &(*p)->rb_right;
	1601	+ leftmost = false;
	1602	+ }
1439	1603	}
1440	1604	hists->nr_entries++;
1441	1605
1442	1606	rb_link_node(&he->rb_node_in, parent, p);
1443		- rb_insert_color(&he->rb_node_in, root);
	1607	+ rb_insert_color_cached(&he->rb_node_in, root, leftmost);
1444	1608	return 1;
1445	1609	}
1446	1610
1447		-struct rb_root hists__get_rotate_entries_in(struct hists hists)
	1611	+struct rb_root_cached hists__get_rotate_entries_in(struct hists hists)
1448	1612	{
1449		- struct rb_root *root;
	1613	+ struct rb_root_cached *root;
1450	1614
1451	1615	pthread_mutex_lock(&hists->lock);
1452	1616
..	..	@@ -1469,7 +1633,7 @@
1469	1633
1470	1634	int hists__collapse_resort(struct hists hists, struct ui_progress prog)
1471	1635	{
1472		- struct rb_root *root;
	1636	+ struct rb_root_cached *root;
1473	1637	struct rb_node *next;
1474	1638	struct hist_entry *n;
1475	1639	int ret;
..	..	@@ -1481,7 +1645,7 @@
1481	1645
1482	1646	root = hists__get_rotate_entries_in(hists);
1483	1647
1484		- next = rb_first(root);
	1648	+ next = rb_first_cached(root);
1485	1649
1486	1650	while (next) {
1487	1651	if (session_done())
..	..	@@ -1489,7 +1653,7 @@
1489	1653	n = rb_entry(next, struct hist_entry, rb_node_in);
1490	1654	next = rb_next(&n->rb_node_in);
1491	1655
1492		- rb_erase(&n->rb_node_in, root);
	1656	+ rb_erase_cached(&n->rb_node_in, root);
1493	1657	ret = hists__collapse_insert_entry(hists, &hists->entries_collapsed, n);
1494	1658	if (ret < 0)
1495	1659	return -1;
..	..	@@ -1560,7 +1724,7 @@
1560	1724	struct rb_node *node;
1561	1725	struct hist_entry *he;
1562	1726
1563		- node = rb_first(&hists->entries);
	1727	+ node = rb_first_cached(&hists->entries);
1564	1728
1565	1729	hists->stats.total_period = 0;
1566	1730	hists->stats.total_non_filtered_period = 0;
..	..	@@ -1580,13 +1744,14 @@
1580	1744	}
1581	1745	}
1582	1746
1583		-static void hierarchy_insert_output_entry(struct rb_root *root,
	1747	+static void hierarchy_insert_output_entry(struct rb_root_cached *root,
1584	1748	struct hist_entry *he)
1585	1749	{
1586		- struct rb_node **p = &root->rb_node;
	1750	+ struct rb_node **p = &root->rb_root.rb_node;
1587	1751	struct rb_node *parent = NULL;
1588	1752	struct hist_entry *iter;
1589	1753	struct perf_hpp_fmt *fmt;
	1754	+ bool leftmost = true;
1590	1755
1591	1756	while (*p != NULL) {
1592	1757	parent = *p;
..	..	@@ -1594,12 +1759,14 @@
1594	1759
1595	1760	if (hist_entry__sort(he, iter) > 0)
1596	1761	p = &parent->rb_left;
1597		- else
	1762	+ else {
1598	1763	p = &parent->rb_right;
	1764	+ leftmost = false;
	1765	+ }
1599	1766	}
1600	1767
1601	1768	rb_link_node(&he->rb_node, parent, p);
1602		- rb_insert_color(&he->rb_node, root);
	1769	+ rb_insert_color_cached(&he->rb_node, root, leftmost);
1603	1770
1604	1771	/* update column width of dynamic entry */
1605	1772	perf_hpp_list__for_each_sort_list(he->hpp_list, fmt) {
..	..	@@ -1610,16 +1777,16 @@
1610	1777
1611	1778	static void hists__hierarchy_output_resort(struct hists *hists,
1612	1779	struct ui_progress *prog,
1613		- struct rb_root *root_in,
1614		- struct rb_root *root_out,
	1780	+ struct rb_root_cached *root_in,
	1781	+ struct rb_root_cached *root_out,
1615	1782	u64 min_callchain_hits,
1616	1783	bool use_callchain)
1617	1784	{
1618	1785	struct rb_node *node;
1619	1786	struct hist_entry *he;
1620	1787
1621		- *root_out = RB_ROOT;
1622		- node = rb_first(root_in);
	1788	+ *root_out = RB_ROOT_CACHED;
	1789	+ node = rb_first_cached(root_in);
1623	1790
1624	1791	while (node) {
1625	1792	he = rb_entry(node, struct hist_entry, rb_node_in);
..	..	@@ -1662,15 +1829,16 @@
1662	1829	}
1663	1830	}
1664	1831
1665		-static void __hists__insert_output_entry(struct rb_root *entries,
	1832	+static void __hists__insert_output_entry(struct rb_root_cached *entries,
1666	1833	struct hist_entry *he,
1667	1834	u64 min_callchain_hits,
1668	1835	bool use_callchain)
1669	1836	{
1670		- struct rb_node **p = &entries->rb_node;
	1837	+ struct rb_node **p = &entries->rb_root.rb_node;
1671	1838	struct rb_node *parent = NULL;
1672	1839	struct hist_entry *iter;
1673	1840	struct perf_hpp_fmt *fmt;
	1841	+ bool leftmost = true;
1674	1842
1675	1843	if (use_callchain) {
1676	1844	if (callchain_param.mode == CHAIN_GRAPH_REL) {
..	..	@@ -1691,12 +1859,14 @@
1691	1859
1692	1860	if (hist_entry__sort(he, iter) > 0)
1693	1861	p = &(*p)->rb_left;
1694		- else
	1862	+ else {
1695	1863	p = &(*p)->rb_right;
	1864	+ leftmost = false;
	1865	+ }
1696	1866	}
1697	1867
1698	1868	rb_link_node(&he->rb_node, parent, p);
1699		- rb_insert_color(&he->rb_node, entries);
	1869	+ rb_insert_color_cached(&he->rb_node, entries, leftmost);
1700	1870
1701	1871	perf_hpp_list__for_each_sort_list(&perf_hpp_list, fmt) {
1702	1872	if (perf_hpp__is_dynamic_entry(fmt) &&
..	..	@@ -1706,9 +1876,10 @@
1706	1876	}
1707	1877
1708	1878	static void output_resort(struct hists hists, struct ui_progress prog,
1709		- bool use_callchain, hists__resort_cb_t cb)
	1879	+ bool use_callchain, hists__resort_cb_t cb,
	1880	+ void *cb_arg)
1710	1881	{
1711		- struct rb_root *root;
	1882	+ struct rb_root_cached *root;
1712	1883	struct rb_node *next;
1713	1884	struct hist_entry *n;
1714	1885	u64 callchain_total;
..	..	@@ -1738,14 +1909,14 @@
1738	1909	else
1739	1910	root = hists->entries_in;
1740	1911
1741		- next = rb_first(root);
1742		- hists->entries = RB_ROOT;
	1912	+ next = rb_first_cached(root);
	1913	+ hists->entries = RB_ROOT_CACHED;
1743	1914
1744	1915	while (next) {
1745	1916	n = rb_entry(next, struct hist_entry, rb_node_in);
1746	1917	next = rb_next(&n->rb_node_in);
1747	1918
1748		- if (cb && cb(n))
	1919	+ if (cb && cb(n, cb_arg))
1749	1920	continue;
1750	1921
1751	1922	__hists__insert_output_entry(&hists->entries, n, min_callchain_hits, use_callchain);
..	..	@@ -1759,7 +1930,8 @@
1759	1930	}
1760	1931	}
1761	1932
1762		-void perf_evsel__output_resort(struct perf_evsel evsel, struct ui_progress prog)
	1933	+void evsel__output_resort_cb(struct evsel evsel, struct ui_progress prog,
	1934	+ hists__resort_cb_t cb, void *cb_arg)
1763	1935	{
1764	1936	bool use_callchain;
1765	1937
..	..	@@ -1770,18 +1942,23 @@
1770	1942
1771	1943	use_callchain \|= symbol_conf.show_branchflag_count;
1772	1944
1773		- output_resort(evsel__hists(evsel), prog, use_callchain, NULL);
	1945	+ output_resort(evsel__hists(evsel), prog, use_callchain, cb, cb_arg);
	1946	+}
	1947	+
	1948	+void evsel__output_resort(struct evsel evsel, struct ui_progress prog)
	1949	+{
	1950	+ return evsel__output_resort_cb(evsel, prog, NULL, NULL);
1774	1951	}
1775	1952
1776	1953	void hists__output_resort(struct hists hists, struct ui_progress prog)
1777	1954	{
1778		- output_resort(hists, prog, symbol_conf.use_callchain, NULL);
	1955	+ output_resort(hists, prog, symbol_conf.use_callchain, NULL, NULL);
1779	1956	}
1780	1957
1781	1958	void hists__output_resort_cb(struct hists hists, struct ui_progress prog,
1782	1959	hists__resort_cb_t cb)
1783	1960	{
1784		- output_resort(hists, prog, symbol_conf.use_callchain, cb);
	1961	+ output_resort(hists, prog, symbol_conf.use_callchain, cb, NULL);
1785	1962	}
1786	1963
1787	1964	static bool can_goto_child(struct hist_entry *he, enum hierarchy_move_dir hmd)
..	..	@@ -1800,7 +1977,7 @@
1800	1977	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
1801	1978
1802	1979	while (can_goto_child(he, HMD_NORMAL)) {
1803		- node = rb_last(&he->hroot_out);
	1980	+ node = rb_last(&he->hroot_out.rb_root);
1804	1981	he = rb_entry(node, struct hist_entry, rb_node);
1805	1982	}
1806	1983	return node;
..	..	@@ -1811,7 +1988,7 @@
1811	1988	struct hist_entry *he = rb_entry(node, struct hist_entry, rb_node);
1812	1989
1813	1990	if (can_goto_child(he, hmd))
1814		- node = rb_first(&he->hroot_out);
	1991	+ node = rb_first_cached(&he->hroot_out);
1815	1992	else
1816	1993	node = rb_next(node);
1817	1994
..	..	@@ -1849,7 +2026,7 @@
1849	2026	if (he->leaf)
1850	2027	return false;
1851	2028
1852		- node = rb_first(&he->hroot_out);
	2029	+ node = rb_first_cached(&he->hroot_out);
1853	2030	child = rb_entry(node, struct hist_entry, rb_node);
1854	2031
1855	2032	while (node && child->filtered) {
..	..	@@ -1967,7 +2144,7 @@
1967	2144	hists__reset_filter_stats(hists);
1968	2145	hists__reset_col_len(hists);
1969	2146
1970		- for (nd = rb_first(&hists->entries); nd; nd = rb_next(nd)) {
	2147	+ for (nd = rb_first_cached(&hists->entries); nd; nd = rb_next(nd)) {
1971	2148	struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
1972	2149
1973	2150	if (filter(hists, h))
..	..	@@ -1977,13 +2154,15 @@
1977	2154	}
1978	2155	}
1979	2156
1980		-static void resort_filtered_entry(struct rb_root root, struct hist_entry he)
	2157	+static void resort_filtered_entry(struct rb_root_cached *root,
	2158	+ struct hist_entry *he)
1981	2159	{
1982		- struct rb_node **p = &root->rb_node;
	2160	+ struct rb_node **p = &root->rb_root.rb_node;
1983	2161	struct rb_node *parent = NULL;
1984	2162	struct hist_entry *iter;
1985		- struct rb_root new_root = RB_ROOT;
	2163	+ struct rb_root_cached new_root = RB_ROOT_CACHED;
1986	2164	struct rb_node *nd;
	2165	+ bool leftmost = true;
1987	2166
1988	2167	while (*p != NULL) {
1989	2168	parent = *p;
..	..	@@ -1991,22 +2170,24 @@
1991	2170
1992	2171	if (hist_entry__sort(he, iter) > 0)
1993	2172	p = &(*p)->rb_left;
1994		- else
	2173	+ else {
1995	2174	p = &(*p)->rb_right;
	2175	+ leftmost = false;
	2176	+ }
1996	2177	}
1997	2178
1998	2179	rb_link_node(&he->rb_node, parent, p);
1999		- rb_insert_color(&he->rb_node, root);
	2180	+ rb_insert_color_cached(&he->rb_node, root, leftmost);
2000	2181
2001	2182	if (he->leaf \|\| he->filtered)
2002	2183	return;
2003	2184
2004		- nd = rb_first(&he->hroot_out);
	2185	+ nd = rb_first_cached(&he->hroot_out);
2005	2186	while (nd) {
2006	2187	struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2007	2188
2008	2189	nd = rb_next(nd);
2009		- rb_erase(&h->rb_node, &he->hroot_out);
	2190	+ rb_erase_cached(&h->rb_node, &he->hroot_out);
2010	2191
2011	2192	resort_filtered_entry(&new_root, h);
2012	2193	}
..	..	@@ -2017,14 +2198,14 @@
2017	2198	static void hists__filter_hierarchy(struct hists hists, int type, const void arg)
2018	2199	{
2019	2200	struct rb_node *nd;
2020		- struct rb_root new_root = RB_ROOT;
	2201	+ struct rb_root_cached new_root = RB_ROOT_CACHED;
2021	2202
2022	2203	hists->stats.nr_non_filtered_samples = 0;
2023	2204
2024	2205	hists__reset_filter_stats(hists);
2025	2206	hists__reset_col_len(hists);
2026	2207
2027		- nd = rb_first(&hists->entries);
	2208	+ nd = rb_first_cached(&hists->entries);
2028	2209	while (nd) {
2029	2210	struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2030	2211	int ret;
..	..	@@ -2068,12 +2249,12 @@
2068	2249	* resort output after applying a new filter since filter in a lower
2069	2250	* hierarchy can change periods in a upper hierarchy.
2070	2251	*/
2071		- nd = rb_first(&hists->entries);
	2252	+ nd = rb_first_cached(&hists->entries);
2072	2253	while (nd) {
2073	2254	struct hist_entry *h = rb_entry(nd, struct hist_entry, rb_node);
2074	2255
2075	2256	nd = rb_next(nd);
2076		- rb_erase(&h->rb_node, &hists->entries);
	2257	+ rb_erase_cached(&h->rb_node, &hists->entries);
2077	2258
2078	2259	resort_filtered_entry(&new_root, h);
2079	2260	}
..	..	@@ -2142,18 +2323,19 @@
2142	2323	static struct hist_entry hists__add_dummy_entry(struct hists hists,
2143	2324	struct hist_entry *pair)
2144	2325	{
2145		- struct rb_root *root;
	2326	+ struct rb_root_cached *root;
2146	2327	struct rb_node **p;
2147	2328	struct rb_node *parent = NULL;
2148	2329	struct hist_entry *he;
2149	2330	int64_t cmp;
	2331	+ bool leftmost = true;
2150	2332
2151	2333	if (hists__has(hists, need_collapse))
2152	2334	root = &hists->entries_collapsed;
2153	2335	else
2154	2336	root = hists->entries_in;
2155	2337
2156		- p = &root->rb_node;
	2338	+ p = &root->rb_root.rb_node;
2157	2339
2158	2340	while (*p != NULL) {
2159	2341	parent = *p;
..	..	@@ -2166,8 +2348,10 @@
2166	2348
2167	2349	if (cmp < 0)
2168	2350	p = &(*p)->rb_left;
2169		- else
	2351	+ else {
2170	2352	p = &(*p)->rb_right;
	2353	+ leftmost = false;
	2354	+ }
2171	2355	}
2172	2356
2173	2357	he = hist_entry__new(pair, true);
..	..	@@ -2177,7 +2361,7 @@
2177	2361	if (symbol_conf.cumulate_callchain)
2178	2362	memset(he->stat_acc, 0, sizeof(he->stat));
2179	2363	rb_link_node(&he->rb_node_in, parent, p);
2180		- rb_insert_color(&he->rb_node_in, root);
	2364	+ rb_insert_color_cached(&he->rb_node_in, root, leftmost);
2181	2365	hists__inc_stats(hists, he);
2182	2366	he->dummy = true;
2183	2367	}
..	..	@@ -2186,15 +2370,16 @@
2186	2370	}
2187	2371
2188	2372	static struct hist_entry add_dummy_hierarchy_entry(struct hists hists,
2189		- struct rb_root *root,
	2373	+ struct rb_root_cached *root,
2190	2374	struct hist_entry *pair)
2191	2375	{
2192	2376	struct rb_node **p;
2193	2377	struct rb_node *parent = NULL;
2194	2378	struct hist_entry *he;
2195	2379	struct perf_hpp_fmt *fmt;
	2380	+ bool leftmost = true;
2196	2381
2197		- p = &root->rb_node;
	2382	+ p = &root->rb_root.rb_node;
2198	2383	while (*p != NULL) {
2199	2384	int64_t cmp = 0;
2200	2385
..	..	@@ -2211,14 +2396,16 @@
2211	2396
2212	2397	if (cmp < 0)
2213	2398	p = &parent->rb_left;
2214		- else
	2399	+ else {
2215	2400	p = &parent->rb_right;
	2401	+ leftmost = false;
	2402	+ }
2216	2403	}
2217	2404
2218	2405	he = hist_entry__new(pair, true);
2219	2406	if (he) {
2220	2407	rb_link_node(&he->rb_node_in, parent, p);
2221		- rb_insert_color(&he->rb_node_in, root);
	2408	+ rb_insert_color_cached(&he->rb_node_in, root, leftmost);
2222	2409
2223	2410	he->dummy = true;
2224	2411	he->hists = hists;
..	..	@@ -2235,9 +2422,9 @@
2235	2422	struct rb_node *n;
2236	2423
2237	2424	if (hists__has(hists, need_collapse))
2238		- n = hists->entries_collapsed.rb_node;
	2425	+ n = hists->entries_collapsed.rb_root.rb_node;
2239	2426	else
2240		- n = hists->entries_in->rb_node;
	2427	+ n = hists->entries_in->rb_root.rb_node;
2241	2428
2242	2429	while (n) {
2243	2430	struct hist_entry *iter = rb_entry(n, struct hist_entry, rb_node_in);
..	..	@@ -2254,10 +2441,10 @@
2254	2441	return NULL;
2255	2442	}
2256	2443
2257		-static struct hist_entry hists__find_hierarchy_entry(struct rb_root root,
	2444	+static struct hist_entry hists__find_hierarchy_entry(struct rb_root_cached root,
2258	2445	struct hist_entry *he)
2259	2446	{
2260		- struct rb_node *n = root->rb_node;
	2447	+ struct rb_node *n = root->rb_root.rb_node;
2261	2448
2262	2449	while (n) {
2263	2450	struct hist_entry *iter;
..	..	@@ -2282,13 +2469,13 @@
2282	2469	return NULL;
2283	2470	}
2284	2471
2285		-static void hists__match_hierarchy(struct rb_root *leader_root,
2286		- struct rb_root *other_root)
	2472	+static void hists__match_hierarchy(struct rb_root_cached *leader_root,
	2473	+ struct rb_root_cached *other_root)
2287	2474	{
2288	2475	struct rb_node *nd;
2289	2476	struct hist_entry pos, pair;
2290	2477
2291		- for (nd = rb_first(leader_root); nd; nd = rb_next(nd)) {
	2478	+ for (nd = rb_first_cached(leader_root); nd; nd = rb_next(nd)) {
2292	2479	pos = rb_entry(nd, struct hist_entry, rb_node_in);
2293	2480	pair = hists__find_hierarchy_entry(other_root, pos);
2294	2481
..	..	@@ -2304,7 +2491,7 @@
2304	2491	*/
2305	2492	void hists__match(struct hists leader, struct hists other)
2306	2493	{
2307		- struct rb_root *root;
	2494	+ struct rb_root_cached *root;
2308	2495	struct rb_node *nd;
2309	2496	struct hist_entry pos, pair;
2310	2497
..	..	@@ -2319,7 +2506,7 @@
2319	2506	else
2320	2507	root = leader->entries_in;
2321	2508
2322		- for (nd = rb_first(root); nd; nd = rb_next(nd)) {
	2509	+ for (nd = rb_first_cached(root); nd; nd = rb_next(nd)) {
2323	2510	pos = rb_entry(nd, struct hist_entry, rb_node_in);
2324	2511	pair = hists__find_entry(other, pos);
2325	2512
..	..	@@ -2330,13 +2517,13 @@
2330	2517
2331	2518	static int hists__link_hierarchy(struct hists *leader_hists,
2332	2519	struct hist_entry *parent,
2333		- struct rb_root *leader_root,
2334		- struct rb_root *other_root)
	2520	+ struct rb_root_cached *leader_root,
	2521	+ struct rb_root_cached *other_root)
2335	2522	{
2336	2523	struct rb_node *nd;
2337	2524	struct hist_entry pos, leader;
2338	2525
2339		- for (nd = rb_first(other_root); nd; nd = rb_next(nd)) {
	2526	+ for (nd = rb_first_cached(other_root); nd; nd = rb_next(nd)) {
2340	2527	pos = rb_entry(nd, struct hist_entry, rb_node_in);
2341	2528
2342	2529	if (hist_entry__has_pairs(pos)) {
..	..	@@ -2379,7 +2566,7 @@
2379	2566	*/
2380	2567	int hists__link(struct hists leader, struct hists other)
2381	2568	{
2382		- struct rb_root *root;
	2569	+ struct rb_root_cached *root;
2383	2570	struct rb_node *nd;
2384	2571	struct hist_entry pos, pair;
2385	2572
..	..	@@ -2395,7 +2582,7 @@
2395	2582	else
2396	2583	root = other->entries_in;
2397	2584
2398		- for (nd = rb_first(root); nd; nd = rb_next(nd)) {
	2585	+ for (nd = rb_first_cached(root); nd; nd = rb_next(nd)) {
2399	2586	pos = rb_entry(nd, struct hist_entry, rb_node_in);
2400	2587
2401	2588	if (!hist_entry__has_pairs(pos)) {
..	..	@@ -2409,13 +2596,34 @@
2409	2596	return 0;
2410	2597	}
2411	2598
	2599	+int hists__unlink(struct hists *hists)
	2600	+{
	2601	+ struct rb_root_cached *root;
	2602	+ struct rb_node *nd;
	2603	+ struct hist_entry *pos;
	2604	+
	2605	+ if (hists__has(hists, need_collapse))
	2606	+ root = &hists->entries_collapsed;
	2607	+ else
	2608	+ root = hists->entries_in;
	2609	+
	2610	+ for (nd = rb_first_cached(root); nd; nd = rb_next(nd)) {
	2611	+ pos = rb_entry(nd, struct hist_entry, rb_node_in);
	2612	+ list_del_init(&pos->pairs.node);
	2613	+ }
	2614	+
	2615	+ return 0;
	2616	+}
	2617	+
2412	2618	void hist__account_cycles(struct branch_stack bs, struct addr_location al,
2413		- struct perf_sample *sample, bool nonany_branch_mode)
	2619	+ struct perf_sample *sample, bool nonany_branch_mode,
	2620	+ u64 *total_cycles)
2414	2621	{
2415	2622	struct branch_info *bi;
	2623	+ struct branch_entry *entries = perf_sample__branch_entries(sample);
2416	2624
2417	2625	/* If we have branch cycles always annotate them. */
2418		- if (bs && bs->nr && bs->entries[0].flags.cycles) {
	2626	+ if (bs && bs->nr && entries[0].flags.cycles) {
2419	2627	int i;
2420	2628
2421	2629	bi = sample__resolve_bstack(sample, al);
..	..	@@ -2437,19 +2645,22 @@
2437	2645	nonany_branch_mode ? NULL : prev,
2438	2646	bi[i].flags.cycles);
2439	2647	prev = &bi[i].to;
	2648	+
	2649	+ if (total_cycles)
	2650	+ *total_cycles += bi[i].flags.cycles;
2440	2651	}
2441	2652	free(bi);
2442	2653	}
2443	2654	}
2444	2655	}
2445	2656
2446		-size_t perf_evlist__fprintf_nr_events(struct perf_evlist evlist, FILE fp)
	2657	+size_t perf_evlist__fprintf_nr_events(struct evlist evlist, FILE fp)
2447	2658	{
2448		- struct perf_evsel *pos;
	2659	+ struct evsel *pos;
2449	2660	size_t ret = 0;
2450	2661
2451	2662	evlist__for_each_entry(evlist, pos) {
2452		- ret += fprintf(fp, "%s stats:\n", perf_evsel__name(pos));
	2663	+ ret += fprintf(fp, "%s stats:\n", evsel__name(pos));
2453	2664	ret += events_stats__fprintf(&evsel__hists(pos)->stats, fp);
2454	2665	}
2455	2666
..	..	@@ -2468,12 +2679,12 @@
2468	2679	char unit;
2469	2680	int printed;
2470	2681	const struct dso *dso = hists->dso_filter;
2471		- const struct thread *thread = hists->thread_filter;
	2682	+ struct thread *thread = hists->thread_filter;
2472	2683	int socket_id = hists->socket_filter;
2473	2684	unsigned long nr_samples = hists->stats.nr_events[PERF_RECORD_SAMPLE];
2474	2685	u64 nr_events = hists->stats.total_period;
2475		- struct perf_evsel *evsel = hists_to_evsel(hists);
2476		- const char *ev_name = perf_evsel__name(evsel);
	2686	+ struct evsel *evsel = hists_to_evsel(hists);
	2687	+ const char *ev_name = evsel__name(evsel);
2477	2688	char buf[512], sample_freq_str[64] = "";
2478	2689	size_t buflen = sizeof(buf);
2479	2690	char ref[30] = " show reference callgraph, ";
..	..	@@ -2484,10 +2695,10 @@
2484	2695	nr_events = hists->stats.total_non_filtered_period;
2485	2696	}
2486	2697
2487		- if (perf_evsel__is_group_event(evsel)) {
2488		- struct perf_evsel *pos;
	2698	+ if (evsel__is_group_event(evsel)) {
	2699	+ struct evsel *pos;
2489	2700
2490		- perf_evsel__group_desc(evsel, buf, buflen);
	2701	+ evsel__group_desc(evsel, buf, buflen);
2491	2702	ev_name = buf;
2492	2703
2493	2704	for_each_group_member(pos, evsel) {
..	..	@@ -2508,12 +2719,12 @@
2508	2719	enable_ref = true;
2509	2720
2510	2721	if (show_freq)
2511		- scnprintf(sample_freq_str, sizeof(sample_freq_str), " %d Hz,", evsel->attr.sample_freq);
	2722	+ scnprintf(sample_freq_str, sizeof(sample_freq_str), " %d Hz,", evsel->core.attr.sample_freq);
2512	2723
2513	2724	nr_samples = convert_unit(nr_samples, &unit);
2514	2725	printed = scnprintf(bf, size,
2515	2726	"Samples: %lu%c of event%s '%s',%s%sEvent count (approx.): %" PRIu64,
2516		- nr_samples, unit, evsel->nr_members > 1 ? "s" : "",
	2727	+ nr_samples, unit, evsel->core.nr_members > 1 ? "s" : "",
2517	2728	ev_name, sample_freq_str, enable_ref ? ref : " ", nr_events);
2518	2729
2519	2730
..	..	@@ -2568,10 +2779,10 @@
2568	2779	int __hists__init(struct hists hists, struct perf_hpp_list hpp_list)
2569	2780	{
2570	2781	memset(hists, 0, sizeof(*hists));
2571		- hists->entries_in_array[0] = hists->entries_in_array[1] = RB_ROOT;
	2782	+ hists->entries_in_array[0] = hists->entries_in_array[1] = RB_ROOT_CACHED;
2572	2783	hists->entries_in = &hists->entries_in_array[0];
2573		- hists->entries_collapsed = RB_ROOT;
2574		- hists->entries = RB_ROOT;
	2784	+ hists->entries_collapsed = RB_ROOT_CACHED;
	2785	+ hists->entries = RB_ROOT_CACHED;
2575	2786	pthread_mutex_init(&hists->lock, NULL);
2576	2787	hists->socket_filter = -1;
2577	2788	hists->hpp_list = hpp_list;
..	..	@@ -2579,14 +2790,14 @@
2579	2790	return 0;
2580	2791	}
2581	2792
2582		-static void hists__delete_remaining_entries(struct rb_root *root)
	2793	+static void hists__delete_remaining_entries(struct rb_root_cached *root)
2583	2794	{
2584	2795	struct rb_node *node;
2585	2796	struct hist_entry *he;
2586	2797
2587		- while (!RB_EMPTY_ROOT(root)) {
2588		- node = rb_first(root);
2589		- rb_erase(node, root);
	2798	+ while (!RB_EMPTY_ROOT(&root->rb_root)) {
	2799	+ node = rb_first_cached(root);
	2800	+ rb_erase_cached(node, root);
2590	2801
2591	2802	he = rb_entry(node, struct hist_entry, rb_node_in);
2592	2803	hist_entry__delete(he);
..	..	@@ -2601,7 +2812,7 @@
2601	2812	hists__delete_remaining_entries(&hists->entries_collapsed);
2602	2813	}
2603	2814
2604		-static void hists_evsel__exit(struct perf_evsel *evsel)
	2815	+static void hists_evsel__exit(struct evsel *evsel)
2605	2816	{
2606	2817	struct hists *hists = evsel__hists(evsel);
2607	2818	struct perf_hpp_fmt fmt, pos;
..	..	@@ -2611,15 +2822,15 @@
2611	2822
2612	2823	list_for_each_entry_safe(node, tmp, &hists->hpp_formats, list) {
2613	2824	perf_hpp_list__for_each_format_safe(&node->hpp, fmt, pos) {
2614		- list_del(&fmt->list);
	2825	+ list_del_init(&fmt->list);
2615	2826	free(fmt);
2616	2827	}
2617		- list_del(&node->list);
	2828	+ list_del_init(&node->list);
2618	2829	free(node);
2619	2830	}
2620	2831	}
2621	2832
2622		-static int hists_evsel__init(struct perf_evsel *evsel)
	2833	+static int hists_evsel__init(struct evsel *evsel)
2623	2834	{
2624	2835	struct hists *hists = evsel__hists(evsel);
2625	2836
..	..	@@ -2634,9 +2845,8 @@
2634	2845
2635	2846	int hists__init(void)
2636	2847	{
2637		- int err = perf_evsel__object_config(sizeof(struct hists_evsel),
2638		- hists_evsel__init,
2639		- hists_evsel__exit);
	2848	+ int err = evsel__object_config(sizeof(struct hists_evsel),
	2849	+ hists_evsel__init, hists_evsel__exit);
2640	2850	if (err)
2641	2851	fputs("FATAL ERROR: Couldn't setup hists class\n", stderr);
2642	2852