1#include "perf.h"
2#include "tests.h"
3#include "debug.h"
4#include "symbol.h"
5#include "sort.h"
6#include "evsel.h"
7#include "evlist.h"
8#include "machine.h"
9#include "thread.h"
10#include "parse-events.h"
11
12static struct {
13	u32 pid;
14	const char *comm;
15} fake_threads[] = {
16	{ 100, "perf" },
17	{ 200, "perf" },
18	{ 300, "bash" },
19};
20
21static struct {
22	u32 pid;
23	u64 start;
24	const char *filename;
25} fake_mmap_info[] = {
26	{ 100, 0x40000, "perf" },
27	{ 100, 0x50000, "libc" },
28	{ 100, 0xf0000, "[kernel]" },
29	{ 200, 0x40000, "perf" },
30	{ 200, 0x50000, "libc" },
31	{ 200, 0xf0000, "[kernel]" },
32	{ 300, 0x40000, "bash" },
33	{ 300, 0x50000, "libc" },
34	{ 300, 0xf0000, "[kernel]" },
35};
36
37struct fake_sym {
38	u64 start;
39	u64 length;
40	const char *name;
41};
42
43static struct fake_sym perf_syms[] = {
44	{ 700, 100, "main" },
45	{ 800, 100, "run_command" },
46	{ 900, 100, "cmd_record" },
47};
48
49static struct fake_sym bash_syms[] = {
50	{ 700, 100, "main" },
51	{ 800, 100, "xmalloc" },
52	{ 900, 100, "xfree" },
53};
54
55static struct fake_sym libc_syms[] = {
56	{ 700, 100, "malloc" },
57	{ 800, 100, "free" },
58	{ 900, 100, "realloc" },
59};
60
61static struct fake_sym kernel_syms[] = {
62	{ 700, 100, "schedule" },
63	{ 800, 100, "page_fault" },
64	{ 900, 100, "sys_perf_event_open" },
65};
66
67static struct {
68	const char *dso_name;
69	struct fake_sym *syms;
70	size_t nr_syms;
71} fake_symbols[] = {
72	{ "perf", perf_syms, ARRAY_SIZE(perf_syms) },
73	{ "bash", bash_syms, ARRAY_SIZE(bash_syms) },
74	{ "libc", libc_syms, ARRAY_SIZE(libc_syms) },
75	{ "[kernel]", kernel_syms, ARRAY_SIZE(kernel_syms) },
76};
77
78static struct machine *setup_fake_machine(struct machines *machines)
79{
80	struct machine *machine = machines__find(machines, HOST_KERNEL_ID);
81	size_t i;
82
83	if (machine == NULL) {
84		pr_debug("Not enough memory for machine setup\n");
85		return NULL;
86	}
87
88	for (i = 0; i < ARRAY_SIZE(fake_threads); i++) {
89		struct thread *thread;
90
91		thread = machine__findnew_thread(machine, fake_threads[i].pid,
92						 fake_threads[i].pid);
93		if (thread == NULL)
94			goto out;
95
96		thread__set_comm(thread, fake_threads[i].comm);
97	}
98
99	for (i = 0; i < ARRAY_SIZE(fake_mmap_info); i++) {
100		union perf_event fake_mmap_event = {
101			.mmap = {
102				.header = { .misc = PERF_RECORD_MISC_USER, },
103				.pid = fake_mmap_info[i].pid,
104				.start = fake_mmap_info[i].start,
105				.len = 0x1000ULL,
106				.pgoff = 0ULL,
107			},
108		};
109
110		strcpy(fake_mmap_event.mmap.filename,
111		       fake_mmap_info[i].filename);
112
113		machine__process_mmap_event(machine, &fake_mmap_event);
114	}
115
116	for (i = 0; i < ARRAY_SIZE(fake_symbols); i++) {
117		size_t k;
118		struct dso *dso;
119
120		dso = __dsos__findnew(&machine->user_dsos,
121				      fake_symbols[i].dso_name);
122		if (dso == NULL)
123			goto out;
124
125		/* emulate dso__load() */
126		dso__set_loaded(dso, MAP__FUNCTION);
127
128		for (k = 0; k < fake_symbols[i].nr_syms; k++) {
129			struct symbol *sym;
130			struct fake_sym *fsym = &fake_symbols[i].syms[k];
131
132			sym = symbol__new(fsym->start, fsym->length,
133					  STB_GLOBAL, fsym->name);
134			if (sym == NULL)
135				goto out;
136
137			symbols__insert(&dso->symbols[MAP__FUNCTION], sym);
138		}
139	}
140
141	return machine;
142
143out:
144	pr_debug("Not enough memory for machine setup\n");
145	machine__delete_threads(machine);
146	machine__delete(machine);
147	return NULL;
148}
149
150struct sample {
151	u32 pid;
152	u64 ip;
153	struct thread *thread;
154	struct map *map;
155	struct symbol *sym;
156};
157
158static struct sample fake_common_samples[] = {
159	/* perf [kernel] schedule() */
160	{ .pid = 100, .ip = 0xf0000 + 700, },
161	/* perf [perf]   main() */
162	{ .pid = 200, .ip = 0x40000 + 700, },
163	/* perf [perf]   cmd_record() */
164	{ .pid = 200, .ip = 0x40000 + 900, },
165	/* bash [bash]   xmalloc() */
166	{ .pid = 300, .ip = 0x40000 + 800, },
167	/* bash [libc]   malloc() */
168	{ .pid = 300, .ip = 0x50000 + 700, },
169};
170
171static struct sample fake_samples[][5] = {
172	{
173		/* perf [perf]   run_command() */
174		{ .pid = 100, .ip = 0x40000 + 800, },
175		/* perf [libc]   malloc() */
176		{ .pid = 100, .ip = 0x50000 + 700, },
177		/* perf [kernel] page_fault() */
178		{ .pid = 100, .ip = 0xf0000 + 800, },
179		/* perf [kernel] sys_perf_event_open() */
180		{ .pid = 200, .ip = 0xf0000 + 900, },
181		/* bash [libc]   free() */
182		{ .pid = 300, .ip = 0x50000 + 800, },
183	},
184	{
185		/* perf [libc]   free() */
186		{ .pid = 200, .ip = 0x50000 + 800, },
187		/* bash [libc]   malloc() */
188		{ .pid = 300, .ip = 0x50000 + 700, }, /* will be merged */
189		/* bash [bash]   xfee() */
190		{ .pid = 300, .ip = 0x40000 + 900, },
191		/* bash [libc]   realloc() */
192		{ .pid = 300, .ip = 0x50000 + 900, },
193		/* bash [kernel] page_fault() */
194		{ .pid = 300, .ip = 0xf0000 + 800, },
195	},
196};
197
198static int add_hist_entries(struct perf_evlist *evlist, struct machine *machine)
199{
200	struct perf_evsel *evsel;
201	struct addr_location al;
202	struct hist_entry *he;
203	struct perf_sample sample = { .cpu = 0, };
204	size_t i = 0, k;
205
206	/*
207	 * each evsel will have 10 samples - 5 common and 5 distinct.
208	 * However the second evsel also has a collapsed entry for
209	 * "bash [libc] malloc" so total 9 entries will be in the tree.
210	 */
211	list_for_each_entry(evsel, &evlist->entries, node) {
212		for (k = 0; k < ARRAY_SIZE(fake_common_samples); k++) {
213			const union perf_event event = {
214				.header = {
215					.misc = PERF_RECORD_MISC_USER,
216				},
217			};
218
219			sample.pid = fake_common_samples[k].pid;
220			sample.ip = fake_common_samples[k].ip;
221			if (perf_event__preprocess_sample(&event, machine, &al,
222							  &sample) < 0)
223				goto out;
224
225			he = __hists__add_entry(&evsel->hists, &al, NULL, 1, 1);
226			if (he == NULL)
227				goto out;
228
229			fake_common_samples[k].thread = al.thread;
230			fake_common_samples[k].map = al.map;
231			fake_common_samples[k].sym = al.sym;
232		}
233
234		for (k = 0; k < ARRAY_SIZE(fake_samples[i]); k++) {
235			const union perf_event event = {
236				.header = {
237					.misc = PERF_RECORD_MISC_USER,
238				},
239			};
240
241			sample.pid = fake_samples[i][k].pid;
242			sample.ip = fake_samples[i][k].ip;
243			if (perf_event__preprocess_sample(&event, machine, &al,
244							  &sample) < 0)
245				goto out;
246
247			he = __hists__add_entry(&evsel->hists, &al, NULL, 1, 1);
248			if (he == NULL)
249				goto out;
250
251			fake_samples[i][k].thread = al.thread;
252			fake_samples[i][k].map = al.map;
253			fake_samples[i][k].sym = al.sym;
254		}
255		i++;
256	}
257
258	return 0;
259
260out:
261	pr_debug("Not enough memory for adding a hist entry\n");
262	return -1;
263}
264
265static int find_sample(struct sample *samples, size_t nr_samples,
266		       struct thread *t, struct map *m, struct symbol *s)
267{
268	while (nr_samples--) {
269		if (samples->thread == t && samples->map == m &&
270		    samples->sym == s)
271			return 1;
272		samples++;
273	}
274	return 0;
275}
276
277static int __validate_match(struct hists *hists)
278{
279	size_t count = 0;
280	struct rb_root *root;
281	struct rb_node *node;
282
283	/*
284	 * Only entries from fake_common_samples should have a pair.
285	 */
286	if (sort__need_collapse)
287		root = &hists->entries_collapsed;
288	else
289		root = hists->entries_in;
290
291	node = rb_first(root);
292	while (node) {
293		struct hist_entry *he;
294
295		he = rb_entry(node, struct hist_entry, rb_node_in);
296
297		if (hist_entry__has_pairs(he)) {
298			if (find_sample(fake_common_samples,
299					ARRAY_SIZE(fake_common_samples),
300					he->thread, he->ms.map, he->ms.sym)) {
301				count++;
302			} else {
303				pr_debug("Can't find the matched entry\n");
304				return -1;
305			}
306		}
307
308		node = rb_next(node);
309	}
310
311	if (count != ARRAY_SIZE(fake_common_samples)) {
312		pr_debug("Invalid count for matched entries: %zd of %zd\n",
313			 count, ARRAY_SIZE(fake_common_samples));
314		return -1;
315	}
316
317	return 0;
318}
319
320static int validate_match(struct hists *leader, struct hists *other)
321{
322	return __validate_match(leader) || __validate_match(other);
323}
324
325static int __validate_link(struct hists *hists, int idx)
326{
327	size_t count = 0;
328	size_t count_pair = 0;
329	size_t count_dummy = 0;
330	struct rb_root *root;
331	struct rb_node *node;
332
333	/*
334	 * Leader hists (idx = 0) will have dummy entries from other,
335	 * and some entries will have no pair.  However every entry
336	 * in other hists should have (dummy) pair.
337	 */
338	if (sort__need_collapse)
339		root = &hists->entries_collapsed;
340	else
341		root = hists->entries_in;
342
343	node = rb_first(root);
344	while (node) {
345		struct hist_entry *he;
346
347		he = rb_entry(node, struct hist_entry, rb_node_in);
348
349		if (hist_entry__has_pairs(he)) {
350			if (!find_sample(fake_common_samples,
351					 ARRAY_SIZE(fake_common_samples),
352					 he->thread, he->ms.map, he->ms.sym) &&
353			    !find_sample(fake_samples[idx],
354					 ARRAY_SIZE(fake_samples[idx]),
355					 he->thread, he->ms.map, he->ms.sym)) {
356				count_dummy++;
357			}
358			count_pair++;
359		} else if (idx) {
360			pr_debug("A entry from the other hists should have pair\n");
361			return -1;
362		}
363
364		count++;
365		node = rb_next(node);
366	}
367
368	/*
369	 * Note that we have a entry collapsed in the other (idx = 1) hists.
370	 */
371	if (idx == 0) {
372		if (count_dummy != ARRAY_SIZE(fake_samples[1]) - 1) {
373			pr_debug("Invalid count of dummy entries: %zd of %zd\n",
374				 count_dummy, ARRAY_SIZE(fake_samples[1]) - 1);
375			return -1;
376		}
377		if (count != count_pair + ARRAY_SIZE(fake_samples[0])) {
378			pr_debug("Invalid count of total leader entries: %zd of %zd\n",
379				 count, count_pair + ARRAY_SIZE(fake_samples[0]));
380			return -1;
381		}
382	} else {
383		if (count != count_pair) {
384			pr_debug("Invalid count of total other entries: %zd of %zd\n",
385				 count, count_pair);
386			return -1;
387		}
388		if (count_dummy > 0) {
389			pr_debug("Other hists should not have dummy entries: %zd\n",
390				 count_dummy);
391			return -1;
392		}
393	}
394
395	return 0;
396}
397
398static int validate_link(struct hists *leader, struct hists *other)
399{
400	return __validate_link(leader, 0) || __validate_link(other, 1);
401}
402
403static void print_hists(struct hists *hists)
404{
405	int i = 0;
406	struct rb_root *root;
407	struct rb_node *node;
408
409	if (sort__need_collapse)
410		root = &hists->entries_collapsed;
411	else
412		root = hists->entries_in;
413
414	pr_info("----- %s --------\n", __func__);
415	node = rb_first(root);
416	while (node) {
417		struct hist_entry *he;
418
419		he = rb_entry(node, struct hist_entry, rb_node_in);
420
421		pr_info("%2d: entry: %-8s [%-8s] %20s: period = %"PRIu64"\n",
422			i, he->thread->comm, he->ms.map->dso->short_name,
423			he->ms.sym->name, he->stat.period);
424
425		i++;
426		node = rb_next(node);
427	}
428}
429
430int test__hists_link(void)
431{
432	int err = -1;
433	struct machines machines;
434	struct machine *machine = NULL;
435	struct perf_evsel *evsel, *first;
436	struct perf_evlist *evlist = perf_evlist__new();
437
438	if (evlist == NULL)
439                return -ENOMEM;
440
441	err = parse_events(evlist, "cpu-clock");
442	if (err)
443		goto out;
444	err = parse_events(evlist, "task-clock");
445	if (err)
446		goto out;
447
448	/* default sort order (comm,dso,sym) will be used */
449	if (setup_sorting() < 0)
450		goto out;
451
452	machines__init(&machines);
453
454	/* setup threads/dso/map/symbols also */
455	machine = setup_fake_machine(&machines);
456	if (!machine)
457		goto out;
458
459	if (verbose > 1)
460		machine__fprintf(machine, stderr);
461
462	/* process sample events */
463	err = add_hist_entries(evlist, machine);
464	if (err < 0)
465		goto out;
466
467	list_for_each_entry(evsel, &evlist->entries, node) {
468		hists__collapse_resort(&evsel->hists);
469
470		if (verbose > 2)
471			print_hists(&evsel->hists);
472	}
473
474	first = perf_evlist__first(evlist);
475	evsel = perf_evlist__last(evlist);
476
477	/* match common entries */
478	hists__match(&first->hists, &evsel->hists);
479	err = validate_match(&first->hists, &evsel->hists);
480	if (err)
481		goto out;
482
483	/* link common and/or dummy entries */
484	hists__link(&first->hists, &evsel->hists);
485	err = validate_link(&first->hists, &evsel->hists);
486	if (err)
487		goto out;
488
489	err = 0;
490
491out:
492	/* tear down everything */
493	perf_evlist__delete(evlist);
494	machines__exit(&machines);
495
496	return err;
497}
498