[linux-2.6-block.git] / tools / perf / tests / hists_link.c

#include "perf.h"
#include "tests.h"
#include "debug.h"
#include "symbol.h"
#include "sort.h"
#include "evsel.h"
#include "evlist.h"
#include "machine.h"
#include "thread.h"
#include "parse-events.h"

static struct {
	u32 pid;
	const char *comm;
} fake_threads[] = {
	{ 100, "perf" },
	{ 200, "perf" },
	{ 300, "bash" },
};

static struct {
	u32 pid;
	u64 start;
	const char *filename;
} fake_mmap_info[] = {
	{ 100, 0x40000, "perf" },
	{ 100, 0x50000, "libc" },
	{ 100, 0xf0000, "[kernel]" },
	{ 200, 0x40000, "perf" },
	{ 200, 0x50000, "libc" },
	{ 200, 0xf0000, "[kernel]" },
	{ 300, 0x40000, "bash" },
	{ 300, 0x50000, "libc" },
	{ 300, 0xf0000, "[kernel]" },
};

struct fake_sym {
	u64 start;
	u64 length;
	const char *name;
};

static struct fake_sym perf_syms[] = {
	{ 700, 100, "main" },
	{ 800, 100, "run_command" },
	{ 900, 100, "cmd_record" },
};

static struct fake_sym bash_syms[] = {
	{ 700, 100, "main" },
	{ 800, 100, "xmalloc" },
	{ 900, 100, "xfree" },
};

static struct fake_sym libc_syms[] = {
	{ 700, 100, "malloc" },
	{ 800, 100, "free" },
	{ 900, 100, "realloc" },
};

static struct fake_sym kernel_syms[] = {
	{ 700, 100, "schedule" },
	{ 800, 100, "page_fault" },
	{ 900, 100, "sys_perf_event_open" },
};

static struct {
	const char *dso_name;
	struct fake_sym *syms;
	size_t nr_syms;
} fake_symbols[] = {
	{ "perf", perf_syms, ARRAY_SIZE(perf_syms) },
	{ "bash", bash_syms, ARRAY_SIZE(bash_syms) },
	{ "libc", libc_syms, ARRAY_SIZE(libc_syms) },
	{ "[kernel]", kernel_syms, ARRAY_SIZE(kernel_syms) },
};

static struct machine *setup_fake_machine(void)
{
	struct rb_root machine_root = RB_ROOT;
	struct machine *machine;
	size_t i;

	machine = machines__findnew(&machine_root, HOST_KERNEL_ID);
	if (machine == NULL) {
		pr_debug("Not enough memory for machine setup\n");
		return NULL;
	}

	for (i = 0; i < ARRAY_SIZE(fake_threads); i++) {
		struct thread *thread;

		thread = machine__findnew_thread(machine, fake_threads[i].pid);
		if (thread == NULL)
			goto out;

		thread__set_comm(thread, fake_threads[i].comm);
	}

	for (i = 0; i < ARRAY_SIZE(fake_mmap_info); i++) {
		union perf_event fake_mmap_event = {
			.mmap = {
				.header = { .misc = PERF_RECORD_MISC_USER, },
				.pid = fake_mmap_info[i].pid,
				.start = fake_mmap_info[i].start,
				.len = 0x1000ULL,
				.pgoff = 0ULL,
			},
		};

		strcpy(fake_mmap_event.mmap.filename,
		       fake_mmap_info[i].filename);

		machine__process_mmap_event(machine, &fake_mmap_event);
	}

	for (i = 0; i < ARRAY_SIZE(fake_symbols); i++) {
		size_t k;
		struct dso *dso;

		dso = __dsos__findnew(&machine->user_dsos,
				      fake_symbols[i].dso_name);
		if (dso == NULL)
			goto out;

		/* emulate dso__load() */
		dso__set_loaded(dso, MAP__FUNCTION);

		for (k = 0; k < fake_symbols[i].nr_syms; k++) {
			struct symbol *sym;
			struct fake_sym *fsym = &fake_symbols[i].syms[k];

			sym = symbol__new(fsym->start, fsym->length,
					  STB_GLOBAL, fsym->name);
			if (sym == NULL)
				goto out;

			symbols__insert(&dso->symbols[MAP__FUNCTION], sym);
		}
	}

	return machine;

out:
	pr_debug("Not enough memory for machine setup\n");
	machine__delete_threads(machine);
	machine__delete(machine);
	return NULL;
}

struct sample {
	u32 pid;
	u64 ip;
	struct thread *thread;
	struct map *map;
	struct symbol *sym;
};

static struct sample fake_common_samples[] = {
	/* perf [kernel] schedule() */
	{ .pid = 100, .ip = 0xf0000 + 700, },
	/* perf [perf]   main() */
	{ .pid = 200, .ip = 0x40000 + 700, },
	/* perf [perf]   cmd_record() */
	{ .pid = 200, .ip = 0x40000 + 900, },
	/* bash [bash]   xmalloc() */
	{ .pid = 300, .ip = 0x40000 + 800, },
	/* bash [libc]   malloc() */
	{ .pid = 300, .ip = 0x50000 + 700, },
};

static struct sample fake_samples[][5] = {
	{
		/* perf [perf]   run_command() */
		{ .pid = 100, .ip = 0x40000 + 800, },
		/* perf [libc]   malloc() */
		{ .pid = 100, .ip = 0x50000 + 700, },
		/* perf [kernel] page_fault() */
		{ .pid = 100, .ip = 0xf0000 + 800, },
		/* perf [kernel] sys_perf_event_open() */
		{ .pid = 200, .ip = 0xf0000 + 900, },
		/* bash [libc]   free() */
		{ .pid = 300, .ip = 0x50000 + 800, },
	},
	{
		/* perf [libc]   free() */
		{ .pid = 200, .ip = 0x50000 + 800, },
		/* bash [libc]   malloc() */
		{ .pid = 300, .ip = 0x50000 + 700, }, /* will be merged */
		/* bash [bash]   xfee() */
		{ .pid = 300, .ip = 0x40000 + 900, },
		/* bash [libc]   realloc() */
		{ .pid = 300, .ip = 0x50000 + 900, },
		/* bash [kernel] page_fault() */
		{ .pid = 300, .ip = 0xf0000 + 800, },
	},
};

static int add_hist_entries(struct perf_evlist *evlist, struct machine *machine)
{
	struct perf_evsel *evsel;
	struct addr_location al;
	struct hist_entry *he;
	struct perf_sample sample = { .cpu = 0, };
	size_t i = 0, k;

	/*
	 * each evsel will have 10 samples - 5 common and 5 distinct.
	 * However the second evsel also has a collapsed entry for
	 * "bash [libc] malloc" so total 9 entries will be in the tree.
	 */
	list_for_each_entry(evsel, &evlist->entries, node) {
		for (k = 0; k < ARRAY_SIZE(fake_common_samples); k++) {
			const union perf_event event = {
				.ip = {
					.header = {
						.misc = PERF_RECORD_MISC_USER,
					},
					.pid = fake_common_samples[k].pid,
					.ip  = fake_common_samples[k].ip,
				},
			};

			if (perf_event__preprocess_sample(&event, machine, &al,
							  &sample, 0) < 0)
				goto out;

			he = __hists__add_entry(&evsel->hists, &al, NULL, 1);
			if (he == NULL)
				goto out;

			fake_common_samples[k].thread = al.thread;
			fake_common_samples[k].map = al.map;
			fake_common_samples[k].sym = al.sym;
		}

		for (k = 0; k < ARRAY_SIZE(fake_samples[i]); k++) {
			const union perf_event event = {
				.ip = {
					.header = {
						.misc = PERF_RECORD_MISC_USER,
					},
					.pid = fake_samples[i][k].pid,
					.ip  = fake_samples[i][k].ip,
				},
			};

			if (perf_event__preprocess_sample(&event, machine, &al,
							  &sample, 0) < 0)
				goto out;

			he = __hists__add_entry(&evsel->hists, &al, NULL, 1);
			if (he == NULL)
				goto out;

			fake_samples[i][k].thread = al.thread;
			fake_samples[i][k].map = al.map;
			fake_samples[i][k].sym = al.sym;
		}
		i++;
	}

	return 0;

out:
	pr_debug("Not enough memory for adding a hist entry\n");
	return -1;
}

static int find_sample(struct sample *samples, size_t nr_samples,
		       struct thread *t, struct map *m, struct symbol *s)
{
	while (nr_samples--) {
		if (samples->thread == t && samples->map == m &&
		    samples->sym == s)
			return 1;
		samples++;
	}
	return 0;
}

static int __validate_match(struct hists *hists)
{
	size_t count = 0;
	struct rb_root *root;
	struct rb_node *node;

	/*
	 * Only entries from fake_common_samples should have a pair.
	 */
	if (sort__need_collapse)
		root = &hists->entries_collapsed;
	else
		root = hists->entries_in;

	node = rb_first(root);
	while (node) {
		struct hist_entry *he;

		he = rb_entry(node, struct hist_entry, rb_node_in);

		if (hist_entry__has_pairs(he)) {
			if (find_sample(fake_common_samples,
					ARRAY_SIZE(fake_common_samples),
					he->thread, he->ms.map, he->ms.sym)) {
				count++;
			} else {
				pr_debug("Can't find the matched entry\n");
				return -1;
			}
		}

		node = rb_next(node);
	}

	if (count != ARRAY_SIZE(fake_common_samples)) {
		pr_debug("Invalid count for matched entries: %zd of %zd\n",
			 count, ARRAY_SIZE(fake_common_samples));
		return -1;
	}

	return 0;
}

static int validate_match(struct hists *leader, struct hists *other)
{
	return __validate_match(leader) || __validate_match(other);
}

static int __validate_link(struct hists *hists, int idx)
{
	size_t count = 0;
	size_t count_pair = 0;
	size_t count_dummy = 0;
	struct rb_root *root;
	struct rb_node *node;

	/*
	 * Leader hists (idx = 0) will have dummy entries from other,
	 * and some entries will have no pair.  However every entry
	 * in other hists should have (dummy) pair.
	 */
	if (sort__need_collapse)
		root = &hists->entries_collapsed;
	else
		root = hists->entries_in;

	node = rb_first(root);
	while (node) {
		struct hist_entry *he;

		he = rb_entry(node, struct hist_entry, rb_node_in);

		if (hist_entry__has_pairs(he)) {
			if (!find_sample(fake_common_samples,
					 ARRAY_SIZE(fake_common_samples),
					 he->thread, he->ms.map, he->ms.sym) &&
			    !find_sample(fake_samples[idx],
					 ARRAY_SIZE(fake_samples[idx]),
					 he->thread, he->ms.map, he->ms.sym)) {
				count_dummy++;
			}
			count_pair++;
		} else if (idx) {
			pr_debug("A entry from the other hists should have pair\n");
			return -1;
		}

		count++;
		node = rb_next(node);
	}

	/*
	 * Note that we have a entry collapsed in the other (idx = 1) hists.
	 */
	if (idx == 0) {
		if (count_dummy != ARRAY_SIZE(fake_samples[1]) - 1) {
			pr_debug("Invalid count of dummy entries: %zd of %zd\n",
				 count_dummy, ARRAY_SIZE(fake_samples[1]) - 1);
			return -1;
		}
		if (count != count_pair + ARRAY_SIZE(fake_samples[0])) {
			pr_debug("Invalid count of total leader entries: %zd of %zd\n",
				 count, count_pair + ARRAY_SIZE(fake_samples[0]));
			return -1;
		}
	} else {
		if (count != count_pair) {
			pr_debug("Invalid count of total other entries: %zd of %zd\n",
				 count, count_pair);
			return -1;
		}
		if (count_dummy > 0) {
			pr_debug("Other hists should not have dummy entries: %zd\n",
				 count_dummy);
			return -1;
		}
	}

	return 0;
}

static int validate_link(struct hists *leader, struct hists *other)
{
	return __validate_link(leader, 0) || __validate_link(other, 1);
}

static void print_hists(struct hists *hists)
{
	int i = 0;
	struct rb_root *root;
	struct rb_node *node;

	if (sort__need_collapse)
		root = &hists->entries_collapsed;
	else
		root = hists->entries_in;

	pr_info("----- %s --------\n", __func__);
	node = rb_first(root);
	while (node) {
		struct hist_entry *he;

		he = rb_entry(node, struct hist_entry, rb_node_in);

		pr_info("%2d: entry: %-8s [%-8s] %20s: period = %"PRIu64"\n",
			i, he->thread->comm, he->ms.map->dso->short_name,
			he->ms.sym->name, he->stat.period);

		i++;
		node = rb_next(node);
	}
}

int test__hists_link(void)
{
	int err = -1;
	struct machine *machine = NULL;
	struct perf_evsel *evsel, *first;
        struct perf_evlist *evlist = perf_evlist__new(NULL, NULL);

	if (evlist == NULL)
                return -ENOMEM;

	err = parse_events(evlist, "cpu-clock", 0);
	if (err)
		goto out;
	err = parse_events(evlist, "task-clock", 0);
	if (err)
		goto out;

	/* default sort order (comm,dso,sym) will be used */
	setup_sorting(NULL, NULL);

	/* setup threads/dso/map/symbols also */
	machine = setup_fake_machine();
	if (!machine)
		goto out;

	if (verbose > 1)
		machine__fprintf(machine, stderr);

	/* process sample events */
	err = add_hist_entries(evlist, machine);
	if (err < 0)
		goto out;

	list_for_each_entry(evsel, &evlist->entries, node) {
		hists__collapse_resort(&evsel->hists);

		if (verbose > 2)
			print_hists(&evsel->hists);
	}

	first = perf_evlist__first(evlist);
	evsel = perf_evlist__last(evlist);

	/* match common entries */
	hists__match(&first->hists, &evsel->hists);
	err = validate_match(&first->hists, &evsel->hists);
	if (err)
		goto out;

	/* link common and/or dummy entries */
	hists__link(&first->hists, &evsel->hists);
	err = validate_link(&first->hists, &evsel->hists);
	if (err)
		goto out;

	err = 0;

out:
	/* tear down everything */
	perf_evlist__delete(evlist);

	if (machine) {
		machine__delete_threads(machine);
		machine__delete(machine);
	}

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