The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [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> |
| 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 * |
| 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 | * |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 116 | * In case of extended events (required no phisical counters), the associated |
| 117 | * counter_map entry will be -1. |
| 118 | * |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 119 | * Possible improvment if neccessary: partition counters in class of counter, |
| 120 | * two counter belong to the same class if they allow exactly the same set of |
| 121 | * event. Now using a variant of the backtrack algo can works on class of |
| 122 | * counter rather on counter (this is not an improvment if each counter goes |
| 123 | * in it's own class) |
| 124 | */ |
| 125 | static int |
| 126 | allocate_counter(counter_arc_head const * ctr_arc, int max_depth, int depth, |
| 127 | u32 allocated_mask, size_t * counter_map) |
| 128 | { |
| 129 | struct list_head * pos; |
| 130 | |
| 131 | if (depth == max_depth) |
| 132 | return 1; |
| 133 | |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 134 | /* If ctr_arc is not available, counter_map is -1 */ |
| 135 | if((&ctr_arc[depth].next)->next == &ctr_arc[depth].next) { |
| 136 | counter_map[depth] = -1; |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 137 | if (allocate_counter(ctr_arc, max_depth, depth + 1, |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 138 | allocated_mask, |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 139 | counter_map)) |
| 140 | return 1; |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 141 | } else { |
| 142 | list_for_each(pos, &ctr_arc[depth].next) { |
| 143 | counter_arc const * arc = list_entry(pos, counter_arc, next); |
| 144 | |
| 145 | if (allocated_mask & (1 << arc->counter)) |
| 146 | continue; |
| 147 | |
| 148 | counter_map[depth] = arc->counter; |
| 149 | |
| 150 | if (allocate_counter(ctr_arc, max_depth, depth + 1, |
| 151 | allocated_mask | (1 << arc->counter), |
| 152 | counter_map)) |
| 153 | return 1; |
| 154 | } |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 155 | } |
| 156 | |
| 157 | return 0; |
| 158 | } |
| 159 | |
| 160 | /* determine which directories are counter directories |
| 161 | */ |
| 162 | static int perfcounterdir(const struct dirent * entry) |
| 163 | { |
| 164 | return (isdigit(entry->d_name[0])); |
| 165 | } |
| 166 | |
| 167 | |
| 168 | /** |
| 169 | * @param mask pointer where to place bit mask of unavailable counters |
| 170 | * |
| 171 | * return >= 0 number of counters that are available |
| 172 | * < 0 could not determine number of counters |
| 173 | * |
| 174 | */ |
| 175 | static int op_get_counter_mask(u32 * mask) |
| 176 | { |
| 177 | struct dirent **counterlist; |
| 178 | int count, i; |
| 179 | /* assume nothing is available */ |
| 180 | u32 available=0; |
| 181 | |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 182 | count = scandir("/dev/oprofile", &counterlist, perfcounterdir, |
| 183 | alphasort); |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 184 | if (count < 0) |
| 185 | /* unable to determine bit mask */ |
| 186 | return -1; |
| 187 | /* convert to bit map (0 where counter exists) */ |
| 188 | for (i=0; i<count; ++i) { |
| 189 | available |= 1 << atoi(counterlist[i]->d_name); |
| 190 | free(counterlist[i]); |
| 191 | } |
| 192 | *mask=~available; |
| 193 | free(counterlist); |
| 194 | return count; |
| 195 | } |
| 196 | |
| 197 | size_t * map_event_to_counter(struct op_event const * pev[], int nr_events, |
| 198 | op_cpu cpu_type) |
| 199 | { |
| 200 | counter_arc_head * ctr_arc; |
| 201 | size_t * counter_map; |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 202 | int i, nr_counters, nr_pmc_events; |
| 203 | op_cpu curr_cpu_type; |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 204 | u32 unavailable_counters = 0; |
| 205 | |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 206 | /* Either ophelp or one of the libop tests may invoke this |
| 207 | * function with a non-native cpu_type. If so, we should not |
| 208 | * call op_get_counter_mask because that will look for real counter |
| 209 | * information in oprofilefs. |
| 210 | */ |
| 211 | curr_cpu_type = op_get_cpu_type(); |
| 212 | if (cpu_type != curr_cpu_type) |
| 213 | nr_counters = op_get_nr_counters(cpu_type); |
| 214 | else |
| 215 | nr_counters = op_get_counter_mask(&unavailable_counters); |
| 216 | |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 217 | /* no counters then probably perfmon managing perfmon hw */ |
| 218 | if (nr_counters <= 0) { |
| 219 | nr_counters = op_get_nr_counters(cpu_type); |
| 220 | unavailable_counters = (~0) << nr_counters; |
| 221 | } |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 222 | |
| 223 | /* Check to see if we have enough physical counters to map events*/ |
| 224 | for (i = 0, nr_pmc_events = 0; i < nr_events; i++) |
| 225 | if(pev[i]->ext == NULL) |
| 226 | if (++nr_pmc_events > nr_counters) |
| 227 | return 0; |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 228 | |
| 229 | ctr_arc = build_counter_arc(pev, nr_events); |
| 230 | |
Ben Cheng | 5a4eb4e | 2009-09-14 16:00:41 -0700 | [diff] [blame] | 231 | counter_map = xmalloc(nr_events * sizeof(size_t)); |
The Android Open Source Project | 10e23ee | 2009-03-03 19:30:30 -0800 | [diff] [blame] | 232 | |
| 233 | if (!allocate_counter(ctr_arc, nr_events, 0, unavailable_counters, |
| 234 | counter_map)) { |
| 235 | free(counter_map); |
| 236 | counter_map = 0; |
| 237 | } |
| 238 | |
| 239 | delete_counter_arc(ctr_arc, nr_events); |
| 240 | return counter_map; |
| 241 | } |