Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
70fbe057 PZ |
2 | #include "block-range.h" |
3 | #include "annotate.h" | |
e7a795d3 ACM |
4 | #include <assert.h> |
5 | #include <stdlib.h> | |
70fbe057 PZ |
6 | |
7 | struct { | |
8 | struct rb_root root; | |
9 | u64 blocks; | |
10 | } block_ranges; | |
11 | ||
12 | static void block_range__debug(void) | |
13 | { | |
984a785f | 14 | #ifndef NDEBUG |
70fbe057 PZ |
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(left, node, 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(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 | */ | |
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(&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 | ||
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(&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 | ||
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(&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; | |
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(&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 | ||
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; | |
2b215ec7 | 314 | struct annotated_branch *branch; |
70fbe057 PZ |
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 | ||
2b215ec7 NK |
327 | branch = symbol__annotation(sym)->branch; |
328 | if (!branch) | |
329 | return -1; | |
330 | ||
331 | return (double)br->coverage / branch->max_coverage; | |
70fbe057 | 332 | } |