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