333 lines · c
1// SPDX-License-Identifier: GPL-2.02#include "block-range.h"3#include "annotate.h"4#include <assert.h>5#include <stdlib.h>6 7struct {8 struct rb_root root;9 u64 blocks;10} block_ranges;11 12static void block_range__debug(void)13{14#ifndef NDEBUG15 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#endif27}28 29struct 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 else44 return entry;45 }46 47 return NULL;48}49 50static 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 60static 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__create72 * @start: branch target starting this basic block73 * @end: branch ending this basic block74 *75 * Create all the required block ranges to precisely span the given range.76 */77struct 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 else93 break;94 }95 96 /*97 * Didn't find anything.. there's a hole at @start, however @end might98 * 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 135do_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 190do_tail:191 /*192 * At this point we've got: @iter.start = [@start...] but @end can still be193 * 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, done231 */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;247add_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 290done: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_coverage304 *305 * This ensures each symbol has a 100% spot, to reflect that each symbol has a306 * most covered section.307 *308 * Returns [0-1] for coverage and -1 if we had no data what so ever or the309 * symbol does not exist.310 */311double block_range__coverage(struct block_range *br)312{313 struct symbol *sym;314 struct annotated_branch *branch;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 branch = symbol__annotation(sym)->branch;328 if (!branch)329 return -1;330 331 return (double)br->coverage / branch->max_coverage;332}333