aboutsummaryrefslogtreecommitdiffstats
path: root/tools/perf/util/block-range.c
diff options
context:
space:
mode:
Diffstat (limited to 'tools/perf/util/block-range.c')
-rw-r--r--tools/perf/util/block-range.c328
1 files changed, 328 insertions, 0 deletions
diff --git a/tools/perf/util/block-range.c b/tools/perf/util/block-range.c
new file mode 100644
index 000000000000..7b3e1d75d803
--- /dev/null
+++ b/tools/perf/util/block-range.c
@@ -0,0 +1,328 @@
1#include "block-range.h"
2#include "annotate.h"
3
4struct {
5 struct rb_root root;
6 u64 blocks;
7} block_ranges;
8
9static void block_range__debug(void)
10{
11 /*
12 * XXX still paranoid for now; see if we can make this depend on
13 * DEBUG=1 builds.
14 */
15#if 1
16 struct rb_node *rb;
17 u64 old = 0; /* NULL isn't executable */
18
19 for (rb = rb_first(&block_ranges.root); rb; rb = rb_next(rb)) {
20 struct block_range *entry = rb_entry(rb, struct block_range, node);
21
22 assert(old < entry->start);
23 assert(entry->start <= entry->end); /* single instruction block; jump to a jump */
24
25 old = entry->end;
26 }
27#endif
28}
29
30struct block_range *block_range__find(u64 addr)
31{
32 struct rb_node **p = &block_ranges.root.rb_node;
33 struct rb_node *parent = NULL;
34 struct block_range *entry;
35
36 while (*p != NULL) {
37 parent = *p;
38 entry = rb_entry(parent, struct block_range, node);
39
40 if (addr < entry->start)
41 p = &parent->rb_left;
42 else if (addr > entry->end)
43 p = &parent->rb_right;
44 else
45 return entry;
46 }
47
48 return NULL;
49}
50
51static inline void rb_link_left_of_node(struct rb_node *left, struct rb_node *node)
52{
53 struct rb_node **p = &node->rb_left;
54 while (*p) {
55 node = *p;
56 p = &node->rb_right;
57 }
58 rb_link_node(left, node, p);
59}
60
61static inline void rb_link_right_of_node(struct rb_node *right, struct rb_node *node)
62{
63 struct rb_node **p = &node->rb_right;
64 while (*p) {
65 node = *p;
66 p = &node->rb_left;
67 }
68 rb_link_node(right, node, p);
69}
70
71/**
72 * block_range__create
73 * @start: branch target starting this basic block
74 * @end: branch ending this basic block
75 *
76 * Create all the required block ranges to precisely span the given range.
77 */
78struct block_range_iter block_range__create(u64 start, u64 end)
79{
80 struct rb_node **p = &block_ranges.root.rb_node;
81 struct rb_node *n, *parent = NULL;
82 struct block_range *next, *entry = NULL;
83 struct block_range_iter iter = { NULL, NULL };
84
85 while (*p != NULL) {
86 parent = *p;
87 entry = rb_entry(parent, struct block_range, node);
88
89 if (start < entry->start)
90 p = &parent->rb_left;
91 else if (start > entry->end)
92 p = &parent->rb_right;
93 else
94 break;
95 }
96
97 /*
98 * Didn't find anything.. there's a hole at @start, however @end might
99 * be inside/behind the next range.
100 */
101 if (!*p) {
102 if (!entry) /* tree empty */
103 goto do_whole;
104
105 /*
106 * If the last node is before, advance one to find the next.
107 */
108 n = parent;
109 if (entry->end < start) {
110 n = rb_next(n);
111 if (!n)
112 goto do_whole;
113 }
114 next = rb_entry(n, struct block_range, node);
115
116 if (next->start <= end) { /* add head: [start...][n->start...] */
117 struct block_range *head = malloc(sizeof(struct block_range));
118 if (!head)
119 return iter;
120
121 *head = (struct block_range){
122 .start = start,
123 .end = next->start - 1,
124 .is_target = 1,
125 .is_branch = 0,
126 };
127
128 rb_link_left_of_node(&head->node, &next->node);
129 rb_insert_color(&head->node, &block_ranges.root);
130 block_range__debug();
131
132 iter.start = head;
133 goto do_tail;
134 }
135
136do_whole:
137 /*
138 * The whole [start..end] range is non-overlapping.
139 */
140 entry = malloc(sizeof(struct block_range));
141 if (!entry)
142 return iter;
143
144 *entry = (struct block_range){
145 .start = start,
146 .end = end,
147 .is_target = 1,
148 .is_branch = 1,
149 };
150
151 rb_link_node(&entry->node, parent, p);
152 rb_insert_color(&entry->node, &block_ranges.root);
153 block_range__debug();
154
155 iter.start = entry;
156 iter.end = entry;
157 goto done;
158 }
159
160 /*
161 * We found a range that overlapped with ours, split if needed.
162 */
163 if (entry->start < start) { /* split: [e->start...][start...] */
164 struct block_range *head = malloc(sizeof(struct block_range));
165 if (!head)
166 return iter;
167
168 *head = (struct block_range){
169 .start = entry->start,
170 .end = start - 1,
171 .is_target = entry->is_target,
172 .is_branch = 0,
173
174 .coverage = entry->coverage,
175 .entry = entry->entry,
176 };
177
178 entry->start = start;
179 entry->is_target = 1;
180 entry->entry = 0;
181
182 rb_link_left_of_node(&head->node, &entry->node);
183 rb_insert_color(&head->node, &block_ranges.root);
184 block_range__debug();
185
186 } else if (entry->start == start)
187 entry->is_target = 1;
188
189 iter.start = entry;
190
191do_tail:
192 /*
193 * At this point we've got: @iter.start = [@start...] but @end can still be
194 * inside or beyond it.
195 */
196 entry = iter.start;
197 for (;;) {
198 /*
199 * If @end is inside @entry, split.
200 */
201 if (end < entry->end) { /* split: [...end][...e->end] */
202 struct block_range *tail = malloc(sizeof(struct block_range));
203 if (!tail)
204 return iter;
205
206 *tail = (struct block_range){
207 .start = end + 1,
208 .end = entry->end,
209 .is_target = 0,
210 .is_branch = entry->is_branch,
211
212 .coverage = entry->coverage,
213 .taken = entry->taken,
214 .pred = entry->pred,
215 };
216
217 entry->end = end;
218 entry->is_branch = 1;
219 entry->taken = 0;
220 entry->pred = 0;
221
222 rb_link_right_of_node(&tail->node, &entry->node);
223 rb_insert_color(&tail->node, &block_ranges.root);
224 block_range__debug();
225
226 iter.end = entry;
227 goto done;
228 }
229
230 /*
231 * If @end matches @entry, done
232 */
233 if (end == entry->end) {
234 entry->is_branch = 1;
235 iter.end = entry;
236 goto done;
237 }
238
239 next = block_range__next(entry);
240 if (!next)
241 goto add_tail;
242
243 /*
244 * If @end is in beyond @entry but not inside @next, add tail.
245 */
246 if (end < next->start) { /* add tail: [...e->end][...end] */
247 struct block_range *tail;
248add_tail:
249 tail = malloc(sizeof(struct block_range));
250 if (!tail)
251 return iter;
252
253 *tail = (struct block_range){
254 .start = entry->end + 1,
255 .end = end,
256 .is_target = 0,
257 .is_branch = 1,
258 };
259
260 rb_link_right_of_node(&tail->node, &entry->node);
261 rb_insert_color(&tail->node, &block_ranges.root);
262 block_range__debug();
263
264 iter.end = tail;
265 goto done;
266 }
267
268 /*
269 * If there is a hole between @entry and @next, fill it.
270 */
271 if (entry->end + 1 != next->start) {
272 struct block_range *hole = malloc(sizeof(struct block_range));
273 if (!hole)
274 return iter;
275
276 *hole = (struct block_range){
277 .start = entry->end + 1,
278 .end = next->start - 1,
279 .is_target = 0,
280 .is_branch = 0,
281 };
282
283 rb_link_left_of_node(&hole->node, &next->node);
284 rb_insert_color(&hole->node, &block_ranges.root);
285 block_range__debug();
286 }
287
288 entry = next;
289 }
290
291done:
292 assert(iter.start->start == start && iter.start->is_target);
293 assert(iter.end->end == end && iter.end->is_branch);
294
295 block_ranges.blocks++;
296
297 return iter;
298}
299
300
301/*
302 * Compute coverage as:
303 *
304 * br->coverage / br->sym->max_coverage
305 *
306 * This ensures each symbol has a 100% spot, to reflect that each symbol has a
307 * most covered section.
308 *
309 * Returns [0-1] for coverage and -1 if we had no data what so ever or the
310 * symbol does not exist.
311 */
312double block_range__coverage(struct block_range *br)
313{
314 struct symbol *sym;
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 return (double)br->coverage / symbol__annotation(sym)->max_coverage;
328}
generated by cgit v1.2.2 (git 2.25.0) at 2025-10-11 21:31:32 -0400