perf/util/block-range.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 #include "block-range.h"
0003 #include "annotate.h"
0004 #include <assert.h>
0005 #include <stdlib.h>
0006
0007 struct {
0008     struct rb_root root;
0009     u64 blocks;
0010 } block_ranges;
0011
0012 static void block_range__debug(void)
0013 {
0014     /*
0015      * XXX still paranoid for now; see if we can make this depend on
0016      * DEBUG=1 builds.
0017      */
0018 #if 1
0019     struct rb_node *rb;
0020     u64 old = 0; /* NULL isn't executable */
0021
0022     for (rb = rb_first(&block_ranges.root); rb; rb = rb_next(rb)) {
0023         struct block_range *entry = rb_entry(rb, struct block_range, node);
0024
0025         assert(old < entry->start);
0026         assert(entry->start <= entry->end); /* single instruction block; jump to a jump */
0027
0028         old = entry->end;
0029     }
0030 #endif
0031 }
0032
0033 struct block_range *block_range__find(u64 addr)
0034 {
0035     struct rb_node **p = &block_ranges.root.rb_node;
0036     struct rb_node *parent = NULL;
0037     struct block_range *entry;
0038
0039     while (*p != NULL) {
0040         parent = *p;
0041         entry = rb_entry(parent, struct block_range, node);
0042
0043         if (addr < entry->start)
0044             p = &parent->rb_left;
0045         else if (addr > entry->end)
0046             p = &parent->rb_right;
0047         else
0048             return entry;
0049     }
0050
0051     return NULL;
0052 }
0053
0054 static inline void rb_link_left_of_node(struct rb_node *left, struct rb_node *node)
0055 {
0056     struct rb_node **p = &node->rb_left;
0057     while (*p) {
0058         node = *p;
0059         p = &node->rb_right;
0060     }
0061     rb_link_node(left, node, p);
0062 }
0063
0064 static inline void rb_link_right_of_node(struct rb_node *right, struct rb_node *node)
0065 {
0066     struct rb_node **p = &node->rb_right;
0067     while (*p) {
0068         node = *p;
0069         p = &node->rb_left;
0070     }
0071     rb_link_node(right, node, p);
0072 }
0073
0074 /**
0075  * block_range__create
0076  * @start: branch target starting this basic block
0077  * @end:   branch ending this basic block
0078  *
0079  * Create all the required block ranges to precisely span the given range.
0080  */
0081 struct block_range_iter block_range__create(u64 start, u64 end)
0082 {
0083     struct rb_node **p = &block_ranges.root.rb_node;
0084     struct rb_node *n, *parent = NULL;
0085     struct block_range *next, *entry = NULL;
0086     struct block_range_iter iter = { NULL, NULL };
0087
0088     while (*p != NULL) {
0089         parent = *p;
0090         entry = rb_entry(parent, struct block_range, node);
0091
0092         if (start < entry->start)
0093             p = &parent->rb_left;
0094         else if (start > entry->end)
0095             p = &parent->rb_right;
0096         else
0097             break;
0098     }
0099
0100     /*
0101      * Didn't find anything.. there's a hole at @start, however @end might
0102      * be inside/behind the next range.
0103      */
0104     if (!*p) {
0105         if (!entry) /* tree empty */
0106             goto do_whole;
0107
0108         /*
0109          * If the last node is before, advance one to find the next.
0110          */
0111         n = parent;
0112         if (entry->end < start) {
0113             n = rb_next(n);
0114             if (!n)
0115                 goto do_whole;
0116         }
0117         next = rb_entry(n, struct block_range, node);
0118
0119         if (next->start <= end) { /* add head: [start...][n->start...] */
0120             struct block_range *head = malloc(sizeof(struct block_range));
0121             if (!head)
0122                 return iter;
0123
0124             *head = (struct block_range){
0125                 .start      = start,
0126                 .end        = next->start - 1,
0127                 .is_target  = 1,
0128                 .is_branch  = 0,
0129             };
0130
0131             rb_link_left_of_node(&head->node, &next->node);
0132             rb_insert_color(&head->node, &block_ranges.root);
0133             block_range__debug();
0134
0135             iter.start = head;
0136             goto do_tail;
0137         }
0138
0139 do_whole:
0140         /*
0141          * The whole [start..end] range is non-overlapping.
0142          */
0143         entry = malloc(sizeof(struct block_range));
0144         if (!entry)
0145             return iter;
0146
0147         *entry = (struct block_range){
0148             .start      = start,
0149             .end        = end,
0150             .is_target  = 1,
0151             .is_branch  = 1,
0152         };
0153
0154         rb_link_node(&entry->node, parent, p);
0155         rb_insert_color(&entry->node, &block_ranges.root);
0156         block_range__debug();
0157
0158         iter.start = entry;
0159         iter.end   = entry;
0160         goto done;
0161     }
0162
0163     /*
0164      * We found a range that overlapped with ours, split if needed.
0165      */
0166     if (entry->start < start) { /* split: [e->start...][start...] */
0167         struct block_range *head = malloc(sizeof(struct block_range));
0168         if (!head)
0169             return iter;
0170
0171         *head = (struct block_range){
0172             .start      = entry->start,
0173             .end        = start - 1,
0174             .is_target  = entry->is_target,
0175             .is_branch  = 0,
0176
0177             .coverage   = entry->coverage,
0178             .entry      = entry->entry,
0179         };
0180
0181         entry->start        = start;
0182         entry->is_target    = 1;
0183         entry->entry        = 0;
0184
0185         rb_link_left_of_node(&head->node, &entry->node);
0186         rb_insert_color(&head->node, &block_ranges.root);
0187         block_range__debug();
0188
0189     } else if (entry->start == start)
0190         entry->is_target = 1;
0191
0192     iter.start = entry;
0193
0194 do_tail:
0195     /*
0196      * At this point we've got: @iter.start = [@start...] but @end can still be
0197      * inside or beyond it.
0198      */
0199     entry = iter.start;
0200     for (;;) {
0201         /*
0202          * If @end is inside @entry, split.
0203          */
0204         if (end < entry->end) { /* split: [...end][...e->end] */
0205             struct block_range *tail = malloc(sizeof(struct block_range));
0206             if (!tail)
0207                 return iter;
0208
0209             *tail = (struct block_range){
0210                 .start      = end + 1,
0211                 .end        = entry->end,
0212                 .is_target  = 0,
0213                 .is_branch  = entry->is_branch,
0214
0215                 .coverage   = entry->coverage,
0216                 .taken      = entry->taken,
0217                 .pred       = entry->pred,
0218             };
0219
0220             entry->end      = end;
0221             entry->is_branch    = 1;
0222             entry->taken        = 0;
0223             entry->pred     = 0;
0224
0225             rb_link_right_of_node(&tail->node, &entry->node);
0226             rb_insert_color(&tail->node, &block_ranges.root);
0227             block_range__debug();
0228
0229             iter.end = entry;
0230             goto done;
0231         }
0232
0233         /*
0234          * If @end matches @entry, done
0235          */
0236         if (end == entry->end) {
0237             entry->is_branch = 1;
0238             iter.end = entry;
0239             goto done;
0240         }
0241
0242         next = block_range__next(entry);
0243         if (!next)
0244             goto add_tail;
0245
0246         /*
0247          * If @end is in beyond @entry but not inside @next, add tail.
0248          */
0249         if (end < next->start) { /* add tail: [...e->end][...end] */
0250             struct block_range *tail;
0251 add_tail:
0252             tail = malloc(sizeof(struct block_range));
0253             if (!tail)
0254                 return iter;
0255
0256             *tail = (struct block_range){
0257                 .start      = entry->end + 1,
0258                 .end        = end,
0259                 .is_target  = 0,
0260                 .is_branch  = 1,
0261             };
0262
0263             rb_link_right_of_node(&tail->node, &entry->node);
0264             rb_insert_color(&tail->node, &block_ranges.root);
0265             block_range__debug();
0266
0267             iter.end = tail;
0268             goto done;
0269         }
0270
0271         /*
0272          * If there is a hole between @entry and @next, fill it.
0273          */
0274         if (entry->end + 1 != next->start) {
0275             struct block_range *hole = malloc(sizeof(struct block_range));
0276             if (!hole)
0277                 return iter;
0278
0279             *hole = (struct block_range){
0280                 .start      = entry->end + 1,
0281                 .end        = next->start - 1,
0282                 .is_target  = 0,
0283                 .is_branch  = 0,
0284             };
0285
0286             rb_link_left_of_node(&hole->node, &next->node);
0287             rb_insert_color(&hole->node, &block_ranges.root);
0288             block_range__debug();
0289         }
0290
0291         entry = next;
0292     }
0293
0294 done:
0295     assert(iter.start->start == start && iter.start->is_target);
0296     assert(iter.end->end == end && iter.end->is_branch);
0297
0298     block_ranges.blocks++;
0299
0300     return iter;
0301 }
0302
0303
0304 /*
0305  * Compute coverage as:
0306  *
0307  *    br->coverage / br->sym->max_coverage
0308  *
0309  * This ensures each symbol has a 100% spot, to reflect that each symbol has a
0310  * most covered section.
0311  *
0312  * Returns [0-1] for coverage and -1 if we had no data what so ever or the
0313  * symbol does not exist.
0314  */
0315 double block_range__coverage(struct block_range *br)
0316 {
0317     struct symbol *sym;
0318
0319     if (!br) {
0320         if (block_ranges.blocks)
0321             return 0;
0322
0323         return -1;
0324     }
0325
0326     sym = br->sym;
0327     if (!sym)
0328         return -1;
0329
0330     return (double)br->coverage / symbol__annotation(sym)->max_coverage;
0331 }