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