1 #include "block-range.h" 2 #include "annotate.h" 3 4 struct { 5 struct rb_root root; 6 u64 blocks; 7 } block_ranges; 8 9 static void block_range__debug(void) 10 { 11 /* 12 * XXX still paranoid for now; see if we can make this depend on 13 * DEBUG=1 builds. 14 */ 15 #if 1 16 struct rb_node *rb; 17 u64 old = 0; /* NULL isn't executable */ 18 19 for (rb = rb_first(&block_ranges.root); rb; rb = rb_next(rb)) { 20 struct block_range *entry = rb_entry(rb, struct block_range, node); 21 22 assert(old < entry->start); 23 assert(entry->start <= entry->end); /* single instruction block; jump to a jump */ 24 25 old = entry->end; 26 } 27 #endif 28 } 29 30 struct block_range *block_range__find(u64 addr) 31 { 32 struct rb_node **p = &block_ranges.root.rb_node; 33 struct rb_node *parent = NULL; 34 struct block_range *entry; 35 36 while (*p != NULL) { 37 parent = *p; 38 entry = rb_entry(parent, struct block_range, node); 39 40 if (addr < entry->start) 41 p = &parent->rb_left; 42 else if (addr > entry->end) 43 p = &parent->rb_right; 44 else 45 return entry; 46 } 47 48 return NULL; 49 } 50 51 static inline void rb_link_left_of_node(struct rb_node *left, struct rb_node *node) 52 { 53 struct rb_node **p = &node->rb_left; 54 while (*p) { 55 node = *p; 56 p = &node->rb_right; 57 } 58 rb_link_node(left, node, p); 59 } 60 61 static inline void rb_link_right_of_node(struct rb_node *right, struct rb_node *node) 62 { 63 struct rb_node **p = &node->rb_right; 64 while (*p) { 65 node = *p; 66 p = &node->rb_left; 67 } 68 rb_link_node(right, node, p); 69 } 70 71 /** 72 * block_range__create 73 * @start: branch target starting this basic block 74 * @end: branch ending this basic block 75 * 76 * Create all the required block ranges to precisely span the given range. 77 */ 78 struct block_range_iter block_range__create(u64 start, u64 end) 79 { 80 struct rb_node **p = &block_ranges.root.rb_node; 81 struct rb_node *n, *parent = NULL; 82 struct block_range *next, *entry = NULL; 83 struct block_range_iter iter = { NULL, NULL }; 84 85 while (*p != NULL) { 86 parent = *p; 87 entry = rb_entry(parent, struct block_range, node); 88 89 if (start < entry->start) 90 p = &parent->rb_left; 91 else if (start > entry->end) 92 p = &parent->rb_right; 93 else 94 break; 95 } 96 97 /* 98 * Didn't find anything.. there's a hole at @start, however @end might 99 * be inside/behind the next range. 100 */ 101 if (!*p) { 102 if (!entry) /* tree empty */ 103 goto do_whole; 104 105 /* 106 * If the last node is before, advance one to find the next. 107 */ 108 n = parent; 109 if (entry->end < start) { 110 n = rb_next(n); 111 if (!n) 112 goto do_whole; 113 } 114 next = rb_entry(n, struct block_range, node); 115 116 if (next->start <= end) { /* add head: [start...][n->start...] */ 117 struct block_range *head = malloc(sizeof(struct block_range)); 118 if (!head) 119 return iter; 120 121 *head = (struct block_range){ 122 .start = start, 123 .end = next->start - 1, 124 .is_target = 1, 125 .is_branch = 0, 126 }; 127 128 rb_link_left_of_node(&head->node, &next->node); 129 rb_insert_color(&head->node, &block_ranges.root); 130 block_range__debug(); 131 132 iter.start = head; 133 goto do_tail; 134 } 135 136 do_whole: 137 /* 138 * The whole [start..end] range is non-overlapping. 139 */ 140 entry = malloc(sizeof(struct block_range)); 141 if (!entry) 142 return iter; 143 144 *entry = (struct block_range){ 145 .start = start, 146 .end = end, 147 .is_target = 1, 148 .is_branch = 1, 149 }; 150 151 rb_link_node(&entry->node, parent, p); 152 rb_insert_color(&entry->node, &block_ranges.root); 153 block_range__debug(); 154 155 iter.start = entry; 156 iter.end = entry; 157 goto done; 158 } 159 160 /* 161 * We found a range that overlapped with ours, split if needed. 162 */ 163 if (entry->start < start) { /* split: [e->start...][start...] */ 164 struct block_range *head = malloc(sizeof(struct block_range)); 165 if (!head) 166 return iter; 167 168 *head = (struct block_range){ 169 .start = entry->start, 170 .end = start - 1, 171 .is_target = entry->is_target, 172 .is_branch = 0, 173 174 .coverage = entry->coverage, 175 .entry = entry->entry, 176 }; 177 178 entry->start = start; 179 entry->is_target = 1; 180 entry->entry = 0; 181 182 rb_link_left_of_node(&head->node, &entry->node); 183 rb_insert_color(&head->node, &block_ranges.root); 184 block_range__debug(); 185 186 } else if (entry->start == start) 187 entry->is_target = 1; 188 189 iter.start = entry; 190 191 do_tail: 192 /* 193 * At this point we've got: @iter.start = [@start...] but @end can still be 194 * inside or beyond it. 195 */ 196 entry = iter.start; 197 for (;;) { 198 /* 199 * If @end is inside @entry, split. 200 */ 201 if (end < entry->end) { /* split: [...end][...e->end] */ 202 struct block_range *tail = malloc(sizeof(struct block_range)); 203 if (!tail) 204 return iter; 205 206 *tail = (struct block_range){ 207 .start = end + 1, 208 .end = entry->end, 209 .is_target = 0, 210 .is_branch = entry->is_branch, 211 212 .coverage = entry->coverage, 213 .taken = entry->taken, 214 .pred = entry->pred, 215 }; 216 217 entry->end = end; 218 entry->is_branch = 1; 219 entry->taken = 0; 220 entry->pred = 0; 221 222 rb_link_right_of_node(&tail->node, &entry->node); 223 rb_insert_color(&tail->node, &block_ranges.root); 224 block_range__debug(); 225 226 iter.end = entry; 227 goto done; 228 } 229 230 /* 231 * If @end matches @entry, done 232 */ 233 if (end == entry->end) { 234 entry->is_branch = 1; 235 iter.end = entry; 236 goto done; 237 } 238 239 next = block_range__next(entry); 240 if (!next) 241 goto add_tail; 242 243 /* 244 * If @end is in beyond @entry but not inside @next, add tail. 245 */ 246 if (end < next->start) { /* add tail: [...e->end][...end] */ 247 struct block_range *tail; 248 add_tail: 249 tail = malloc(sizeof(struct block_range)); 250 if (!tail) 251 return iter; 252 253 *tail = (struct block_range){ 254 .start = entry->end + 1, 255 .end = end, 256 .is_target = 0, 257 .is_branch = 1, 258 }; 259 260 rb_link_right_of_node(&tail->node, &entry->node); 261 rb_insert_color(&tail->node, &block_ranges.root); 262 block_range__debug(); 263 264 iter.end = tail; 265 goto done; 266 } 267 268 /* 269 * If there is a hole between @entry and @next, fill it. 270 */ 271 if (entry->end + 1 != next->start) { 272 struct block_range *hole = malloc(sizeof(struct block_range)); 273 if (!hole) 274 return iter; 275 276 *hole = (struct block_range){ 277 .start = entry->end + 1, 278 .end = next->start - 1, 279 .is_target = 0, 280 .is_branch = 0, 281 }; 282 283 rb_link_left_of_node(&hole->node, &next->node); 284 rb_insert_color(&hole->node, &block_ranges.root); 285 block_range__debug(); 286 } 287 288 entry = next; 289 } 290 291 done: 292 assert(iter.start->start == start && iter.start->is_target); 293 assert(iter.end->end == end && iter.end->is_branch); 294 295 block_ranges.blocks++; 296 297 return iter; 298 } 299 300 301 /* 302 * Compute coverage as: 303 * 304 * br->coverage / br->sym->max_coverage 305 * 306 * This ensures each symbol has a 100% spot, to reflect that each symbol has a 307 * most covered section. 308 * 309 * Returns [0-1] for coverage and -1 if we had no data what so ever or the 310 * symbol does not exist. 311 */ 312 double block_range__coverage(struct block_range *br) 313 { 314 struct symbol *sym; 315 316 if (!br) { 317 if (block_ranges.blocks) 318 return 0; 319 320 return -1; 321 } 322 323 sym = br->sym; 324 if (!sym) 325 return -1; 326 327 return (double)br->coverage / symbol__annotation(sym)->max_coverage; 328 } 329