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(node: left, parent: node, rb_link: 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(node: right, parent: node, rb_link: 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(left: &head->node, 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(node: &entry->node, parent, rb_link: 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(left: &head->node, 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(right: &tail->node, 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(br: 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(right: &tail->node, 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(left: &hole->node, 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 | } |
333 | |