Upstream | cc2ee17 | 1970-01-12 13:46:40 +0000 | [diff] [blame] | 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> |
Ben Cheng | 2b16b5f | 2008-10-23 16:07:43 -0700 | [diff] [blame^] | 15 | #include <ctype.h> |
| 16 | #include <dirent.h> |
Upstream | cc2ee17 | 1970-01-12 13:46:40 +0000 | [diff] [blame] | 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 * |
| 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 | */ |
| 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 |
| 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)) |
Ben Cheng | 2b16b5f | 2008-10-23 16:07:43 -0700 | [diff] [blame^] | 135 | continue; |
Upstream | cc2ee17 | 1970-01-12 13:46:40 +0000 | [diff] [blame] | 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 | |
Ben Cheng | 2b16b5f | 2008-10-23 16:07:43 -0700 | [diff] [blame^] | 148 | /* determine which directories are counter directories |
| 149 | */ |
| 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 | */ |
| 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 | } |
Upstream | cc2ee17 | 1970-01-12 13:46:40 +0000 | [diff] [blame] | 183 | |
| 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; |
Ben Cheng | 2b16b5f | 2008-10-23 16:07:43 -0700 | [diff] [blame^] | 190 | u32 unavailable_counters = 0; |
Upstream | cc2ee17 | 1970-01-12 13:46:40 +0000 | [diff] [blame] | 191 | |
Ben Cheng | 2b16b5f | 2008-10-23 16:07:43 -0700 | [diff] [blame^] | 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 | } |
Upstream | cc2ee17 | 1970-01-12 13:46:40 +0000 | [diff] [blame] | 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 | |
Ben Cheng | 2b16b5f | 2008-10-23 16:07:43 -0700 | [diff] [blame^] | 205 | if (!allocate_counter(ctr_arc, nr_events, 0, unavailable_counters, |
| 206 | counter_map)) { |
Upstream | cc2ee17 | 1970-01-12 13:46:40 +0000 | [diff] [blame] | 207 | free(counter_map); |
| 208 | counter_map = 0; |
| 209 | } |
| 210 | |
| 211 | delete_counter_arc(ctr_arc, nr_events); |
| 212 | return counter_map; |
| 213 | } |