tools/perf/util/block-range.c

   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         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 }