1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Compare and figure out the top N hottest streams
4 * Copyright (c) 2020, Intel Corporation.
5 * Author: Jin Yao
6 */
7
8#include <inttypes.h>
9#include <stdlib.h>
10#include <linux/zalloc.h>
11#include "debug.h"
12#include "hist.h"
13#include "sort.h"
14#include "stream.h"
15#include "evlist.h"
16
17static void evsel_streams__delete(struct evsel_streams *es, int nr_evsel)
18{
19	for (int i = 0; i < nr_evsel; i++)
20		zfree(&es[i].streams);
21
22	free(es);
23}
24
25void evlist_streams__delete(struct evlist_streams *els)
26{
27	evsel_streams__delete(els->ev_streams, els->nr_evsel);
28	free(els);
29}
30
31static struct evlist_streams *evlist_streams__new(int nr_evsel,
32						  int nr_streams_max)
33{
34	struct evlist_streams *els;
35	struct evsel_streams *es;
36
37	els = zalloc(sizeof(*els));
38	if (!els)
39		return NULL;
40
41	es = calloc(nr_evsel, sizeof(struct evsel_streams));
42	if (!es) {
43		free(els);
44		return NULL;
45	}
46
47	for (int i = 0; i < nr_evsel; i++) {
48		struct evsel_streams *s = &es[i];
49
50		s->streams = calloc(nr_streams_max, sizeof(struct stream));
51		if (!s->streams)
52			goto err;
53
54		s->nr_streams_max = nr_streams_max;
55		s->evsel_idx = -1;
56	}
57
58	els->ev_streams = es;
59	els->nr_evsel = nr_evsel;
60	return els;
61
62err:
63	evsel_streams__delete(es, nr_evsel);
64	return NULL;
65}
66
67/*
68 * The cnodes with high hit number are hot callchains.
69 */
70static void evsel_streams__set_hot_cnode(struct evsel_streams *es,
71					 struct callchain_node *cnode)
72{
73	int i, idx = 0;
74	u64 hit;
75
76	if (es->nr_streams < es->nr_streams_max) {
77		i = es->nr_streams;
78		es->streams[i].cnode = cnode;
79		es->nr_streams++;
80		return;
81	}
82
83	/*
84	 * Considering a few number of hot streams, only use simple
85	 * way to find the cnode with smallest hit number and replace.
86	 */
87	hit = (es->streams[0].cnode)->hit;
88	for (i = 1; i < es->nr_streams; i++) {
89		if ((es->streams[i].cnode)->hit < hit) {
90			hit = (es->streams[i].cnode)->hit;
91			idx = i;
92		}
93	}
94
95	if (cnode->hit > hit)
96		es->streams[idx].cnode = cnode;
97}
98
99static void update_hot_callchain(struct hist_entry *he,
100				 struct evsel_streams *es)
101{
102	struct rb_root *root = &he->sorted_chain;
103	struct rb_node *rb_node = rb_first(root);
104	struct callchain_node *cnode;
105
106	while (rb_node) {
107		cnode = rb_entry(rb_node, struct callchain_node, rb_node);
108		evsel_streams__set_hot_cnode(es, cnode);
109		rb_node = rb_next(rb_node);
110	}
111}
112
113static void init_hot_callchain(struct hists *hists, struct evsel_streams *es)
114{
115	struct rb_node *next = rb_first_cached(&hists->entries);
116
117	while (next) {
118		struct hist_entry *he;
119
120		he = rb_entry(next, struct hist_entry, rb_node);
121		update_hot_callchain(he, es);
122		next = rb_next(&he->rb_node);
123	}
124
125	es->streams_hits = callchain_total_hits(hists);
126}
127
128static int evlist__init_callchain_streams(struct evlist *evlist,
129					  struct evlist_streams *els)
130{
131	struct evsel_streams *es = els->ev_streams;
132	struct evsel *pos;
133	int i = 0;
134
135	BUG_ON(els->nr_evsel < evlist->core.nr_entries);
136
137	evlist__for_each_entry(evlist, pos) {
138		struct hists *hists = evsel__hists(pos);
139
140		hists__output_resort(hists, NULL);
141		init_hot_callchain(hists, &es[i]);
142		es[i].evsel_idx = pos->core.idx;
143		i++;
144	}
145
146	return 0;
147}
148
149struct evlist_streams *evlist__create_streams(struct evlist *evlist,
150					      int nr_streams_max)
151{
152	int nr_evsel = evlist->core.nr_entries, ret = -1;
153	struct evlist_streams *els = evlist_streams__new(nr_evsel,
154							 nr_streams_max);
155
156	if (!els)
157		return NULL;
158
159	ret = evlist__init_callchain_streams(evlist, els);
160	if (ret) {
161		evlist_streams__delete(els);
162		return NULL;
163	}
164
165	return els;
166}
167
168struct evsel_streams *evsel_streams__entry(struct evlist_streams *els,
169					   int evsel_idx)
170{
171	struct evsel_streams *es = els->ev_streams;
172
173	for (int i = 0; i < els->nr_evsel; i++) {
174		if (es[i].evsel_idx == evsel_idx)
175			return &es[i];
176	}
177
178	return NULL;
179}
180
181static struct stream *stream__callchain_match(struct stream *base_stream,
182					      struct evsel_streams *es_pair)
183{
184	for (int i = 0; i < es_pair->nr_streams; i++) {
185		struct stream *pair_stream = &es_pair->streams[i];
186
187		if (callchain_cnode_matched(base_stream->cnode,
188					    pair_stream->cnode)) {
189			return pair_stream;
190		}
191	}
192
193	return NULL;
194}
195
196static struct stream *stream__match(struct stream *base_stream,
197				    struct evsel_streams *es_pair)
198{
199	return stream__callchain_match(base_stream, es_pair);
200}
201
202static void stream__link(struct stream *base_stream, struct stream *pair_stream)
203{
204	base_stream->pair_cnode = pair_stream->cnode;
205	pair_stream->pair_cnode = base_stream->cnode;
206}
207
208void evsel_streams__match(struct evsel_streams *es_base,
209			  struct evsel_streams *es_pair)
210{
211	for (int i = 0; i < es_base->nr_streams; i++) {
212		struct stream *base_stream = &es_base->streams[i];
213		struct stream *pair_stream;
214
215		pair_stream = stream__match(base_stream, es_pair);
216		if (pair_stream)
217			stream__link(base_stream, pair_stream);
218	}
219}
220
221static void print_callchain_pair(struct stream *base_stream, int idx,
222				 struct evsel_streams *es_base,
223				 struct evsel_streams *es_pair)
224{
225	struct callchain_node *base_cnode = base_stream->cnode;
226	struct callchain_node *pair_cnode = base_stream->pair_cnode;
227	struct callchain_list *base_chain, *pair_chain;
228	char buf1[512], buf2[512], cbuf1[256], cbuf2[256];
229	char *s1, *s2;
230	double pct;
231
232	printf("\nhot chain pair %d:\n", idx);
233
234	pct = (double)base_cnode->hit / (double)es_base->streams_hits;
235	scnprintf(buf1, sizeof(buf1), "cycles: %ld, hits: %.2f%%",
236		  callchain_avg_cycles(base_cnode), pct * 100.0);
237
238	pct = (double)pair_cnode->hit / (double)es_pair->streams_hits;
239	scnprintf(buf2, sizeof(buf2), "cycles: %ld, hits: %.2f%%",
240		  callchain_avg_cycles(pair_cnode), pct * 100.0);
241
242	printf("%35s\t%35s\n", buf1, buf2);
243
244	printf("%35s\t%35s\n",
245	       "---------------------------",
246	       "--------------------------");
247
248	pair_chain = list_first_entry(&pair_cnode->val,
249				      struct callchain_list,
250				      list);
251
252	list_for_each_entry(base_chain, &base_cnode->val, list) {
253		if (&pair_chain->list == &pair_cnode->val)
254			return;
255
256		s1 = callchain_list__sym_name(base_chain, cbuf1, sizeof(cbuf1),
257					      false);
258		s2 = callchain_list__sym_name(pair_chain, cbuf2, sizeof(cbuf2),
259					      false);
260
261		scnprintf(buf1, sizeof(buf1), "%35s\t%35s", s1, s2);
262		printf("%s\n", buf1);
263		pair_chain = list_next_entry(pair_chain, list);
264	}
265}
266
267static void print_stream_callchain(struct stream *stream, int idx,
268				   struct evsel_streams *es, bool pair)
269{
270	struct callchain_node *cnode = stream->cnode;
271	struct callchain_list *chain;
272	char buf[512], cbuf[256], *s;
273	double pct;
274
275	printf("\nhot chain %d:\n", idx);
276
277	pct = (double)cnode->hit / (double)es->streams_hits;
278	scnprintf(buf, sizeof(buf), "cycles: %ld, hits: %.2f%%",
279		  callchain_avg_cycles(cnode), pct * 100.0);
280
281	if (pair) {
282		printf("%35s\t%35s\n", "", buf);
283		printf("%35s\t%35s\n",
284		       "", "--------------------------");
285	} else {
286		printf("%35s\n", buf);
287		printf("%35s\n", "--------------------------");
288	}
289
290	list_for_each_entry(chain, &cnode->val, list) {
291		s = callchain_list__sym_name(chain, cbuf, sizeof(cbuf), false);
292
293		if (pair)
294			scnprintf(buf, sizeof(buf), "%35s\t%35s", "", s);
295		else
296			scnprintf(buf, sizeof(buf), "%35s", s);
297
298		printf("%s\n", buf);
299	}
300}
301
302static void callchain_streams_report(struct evsel_streams *es_base,
303				     struct evsel_streams *es_pair)
304{
305	struct stream *base_stream;
306	int i, idx = 0;
307
308	printf("[ Matched hot streams ]\n");
309	for (i = 0; i < es_base->nr_streams; i++) {
310		base_stream = &es_base->streams[i];
311		if (base_stream->pair_cnode) {
312			print_callchain_pair(base_stream, ++idx,
313					     es_base, es_pair);
314		}
315	}
316
317	idx = 0;
318	printf("\n[ Hot streams in old perf data only ]\n");
319	for (i = 0; i < es_base->nr_streams; i++) {
320		base_stream = &es_base->streams[i];
321		if (!base_stream->pair_cnode) {
322			print_stream_callchain(base_stream, ++idx,
323					       es_base, false);
324		}
325	}
326
327	idx = 0;
328	printf("\n[ Hot streams in new perf data only ]\n");
329	for (i = 0; i < es_pair->nr_streams; i++) {
330		base_stream = &es_pair->streams[i];
331		if (!base_stream->pair_cnode) {
332			print_stream_callchain(base_stream, ++idx,
333					       es_pair, true);
334		}
335	}
336}
337
338void evsel_streams__report(struct evsel_streams *es_base,
339			   struct evsel_streams *es_pair)
340{
341	return callchain_streams_report(es_base, es_pair);
342}
343