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