Loading...
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
7struct {
8 struct rb_root root;
9 u64 blocks;
10} block_ranges;
11
12static 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
33struct 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
54static 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
64static 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 */
81struct 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
139do_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
194do_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;
251add_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
294done:
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 */
315double 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}
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
7struct {
8 struct rb_root root;
9 u64 blocks;
10} block_ranges;
11
12static 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
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 else
44 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__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 */
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 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
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 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;
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_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 */
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}