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