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
22 typedef struct counter_arc_head {
23 /** the head of allowed counter for this event */
24 struct list_head next;
25 } counter_arc_head;
26
27
28 typedef 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 */
44 static counter_arc_head *
build_counter_arc(struct op_event const * pev[],int nr_events)45 build_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 */
delete_counter_arc(counter_arc_head * ctr_arc,int nr_events)85 static 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 */
122 static int
allocate_counter(counter_arc_head const * ctr_arc,int max_depth,int depth,u32 allocated_mask,size_t * counter_map)123 allocate_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 */
perfcounterdir(const struct dirent * entry)150 static 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 */
op_get_counter_mask(u32 * mask)163 static 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
map_event_to_counter(struct op_event const * pev[],int nr_events,op_cpu cpu_type)184 size_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