op_alloc_counter.c revision 2b16b5ffd52ea5c0289e5ce794298bce5d941b2b 
1/**
2 * @file op_alloc_counter.c
3 * hardware counter allocation
4 *
5 * You can have silliness here.
6 *
7 * @remark Copyright 2002 OProfile authors
8 * @remark Read the file COPYING
9 *
10 * @author John Levon
11 * @author Philippe Elie
12 */
13
14#include <stdlib.h>
15#include <ctype.h>
16#include <dirent.h>
17
18#include "op_events.h"
19#include "op_libiberty.h"
20
21
22typedef struct counter_arc_head {
23	/** the head of allowed counter for this event */
24	struct list_head next;
25} counter_arc_head;
26
27
28typedef struct counter_arc {
29	/** counter nr */
30	int counter;
31	/** the next counter allowed for this event */
32	struct list_head next;
33} counter_arc;
34
35
36/**
37 * @param pev  an array of event
38 * @param nr_events  number of entry in pev
39 *
40 * build an array of counter list allowed for each events
41 *  counter_arc_head[i] is the list of allowed counter for pev[i] events
42 * The returned pointer is an array of nr_events entry
43 */
44static counter_arc_head *
45build_counter_arc(struct op_event const * pev[], int nr_events)
46{
47	counter_arc_head * ctr_arc;
48	int i;
49
50	ctr_arc = xmalloc(nr_events * sizeof(*ctr_arc));
51
52	for (i = 0; i < nr_events; ++i) {
53		int j;
54		u32 mask = pev[i]->counter_mask;
55
56		list_init(&ctr_arc[i].next);
57		for (j = 0; mask; ++j) {
58			if (mask & (1 << j)) {
59				counter_arc * arc =
60					xmalloc(sizeof(counter_arc));
61				arc->counter = j;
62				/* we are looping by increasing counter number,
63				 * allocation use a left to right tree walking
64				 * so we add at end to ensure counter will
65				 * be allocated by increasing number: it's not
66				 * required but a bit less surprising when
67				 * debugging code
68				 */
69				list_add_tail(&arc->next, &ctr_arc[i].next);
70				mask &= ~(1 << j);
71			}
72		}
73	}
74
75	return ctr_arc;
76}
77
78
79/**
80 * @param ctr_arc  the array to deallocate
81 * @param nr_events  number of entry in array
82 *
83 *  deallocate all previously allocated resource by build_counter_arc()
84 */
85static void delete_counter_arc(counter_arc_head * ctr_arc, int nr_events)
86{
87	int i;
88	for (i = 0; i < nr_events; ++i) {
89		struct list_head * pos, * pos2;
90		list_for_each_safe(pos, pos2, &ctr_arc[i].next) {
91			counter_arc * arc = list_entry(pos, counter_arc, next);
92			list_del(&arc->next);
93			free(arc);
94		}
95	}
96	free(ctr_arc);
97}
98
99
100/**
101 * @param ctr_arc  tree description, ctr_arc[i] is the i-th level of tree.
102 * @param max_depth  number of entry in array ctr_arc == depth of tree
103 * @param depth  current level we are exploring
104 * @param allocated_mask  current counter already allocated mask
105 * @param counter_map  array of counter number mapping, returned results go
106 *   here
107 *
108 * return non zero on succees, in this case counter_map is set to the counter
109 * mapping number.
110 *
111 * Solution is searched through a simple backtracking exploring recursively all
112 * possible solution until one is found, prunning is done in O(1) by tracking
113 * a bitmask of already allocated counter. Walking through node is done in
114 * preorder left to right.
115 *
116 * Possible improvment if neccessary: partition counters in class of counter,
117 * two counter belong to the same class if they allow exactly the same set of
118 * event. Now using a variant of the backtrack algo can works on class of
119 * counter rather on counter (this is not an improvment if each counter goes
120 * in it's own class)
121 */
122static int
123allocate_counter(counter_arc_head const * ctr_arc, int max_depth, int depth,
124		 u32 allocated_mask, size_t * counter_map)
125{
126	struct list_head * pos;
127
128	if (depth == max_depth)
129		return 1;
130
131	list_for_each(pos, &ctr_arc[depth].next) {
132		counter_arc const * arc = list_entry(pos, counter_arc, next);
133
134		if (allocated_mask & (1 << arc->counter))
135			continue;
136
137		counter_map[depth] = arc->counter;
138
139		if (allocate_counter(ctr_arc, max_depth, depth + 1,
140		                     allocated_mask | (1 << arc->counter),
141		                     counter_map))
142			return 1;
143	}
144
145	return 0;
146}
147
148/* determine which directories are counter directories
149 */
150static int perfcounterdir(const struct dirent * entry)
151{
152	return (isdigit(entry->d_name[0]));
153}
154
155
156/**
157 * @param mask pointer where to place bit mask of unavailable counters
158 *
159 * return >= 0 number of counters that are available
160 *        < 0  could not determine number of counters
161 *
162 */
163static int op_get_counter_mask(u32 * mask)
164{
165	struct dirent **counterlist;
166	int count, i;
167	/* assume nothing is available */
168	u32 available=0;
169
170	count = scandir("/dev/oprofile", &counterlist, perfcounterdir, alphasort);
171	if (count < 0)
172		/* unable to determine bit mask */
173		return -1;
174	/* convert to bit map (0 where counter exists) */
175	for (i=0; i<count; ++i) {
176		available |= 1 << atoi(counterlist[i]->d_name);
177		free(counterlist[i]);
178	}
179	*mask=~available;
180	free(counterlist);
181	return count;
182}
183
184size_t * map_event_to_counter(struct op_event const * pev[], int nr_events,
185                              op_cpu cpu_type)
186{
187	counter_arc_head * ctr_arc;
188	size_t * counter_map;
189	int nr_counters;
190	u32 unavailable_counters = 0;
191
192	nr_counters = op_get_counter_mask(&unavailable_counters);
193	/* no counters then probably perfmon managing perfmon hw */
194	if (nr_counters <= 0) {
195		nr_counters = op_get_nr_counters(cpu_type);
196		unavailable_counters = (~0) << nr_counters;
197	}
198	if (nr_counters < nr_events)
199		return 0;
200
201	ctr_arc = build_counter_arc(pev, nr_events);
202
203	counter_map = xmalloc(nr_counters * sizeof(size_t));
204
205	if (!allocate_counter(ctr_arc, nr_events, 0, unavailable_counters,
206			      counter_map)) {
207		free(counter_map);
208		counter_map = 0;
209	}
210
211	delete_counter_arc(ctr_arc, nr_events);
212	return counter_map;
213}
214