tools/perf/util/block-range.c

   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 }