]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - tools/perf/util/block-range.c
1 // SPDX-License-Identifier: GPL-2.0
2 #include "block-range.h"
12 static void block_range__debug(void)
15 * XXX still paranoid for now; see if we can make this depend on
20 u64 old
= 0; /* NULL isn't executable */
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
);
25 assert(old
< entry
->start
);
26 assert(entry
->start
<= entry
->end
); /* single instruction block; jump to a jump */
33 struct block_range
*block_range__find(u64 addr
)
35 struct rb_node
**p
= &block_ranges
.root
.rb_node
;
36 struct rb_node
*parent
= NULL
;
37 struct block_range
*entry
;
41 entry
= rb_entry(parent
, struct block_range
, node
);
43 if (addr
< entry
->start
)
45 else if (addr
> entry
->end
)
46 p
= &parent
->rb_right
;
54 static inline void rb_link_left_of_node(struct rb_node
*left
, struct rb_node
*node
)
56 struct rb_node
**p
= &node
->rb_left
;
61 rb_link_node(left
, node
, p
);
64 static inline void rb_link_right_of_node(struct rb_node
*right
, struct rb_node
*node
)
66 struct rb_node
**p
= &node
->rb_right
;
71 rb_link_node(right
, node
, p
);
76 * @start: branch target starting this basic block
77 * @end: branch ending this basic block
79 * Create all the required block ranges to precisely span the given range.
81 struct block_range_iter
block_range__create(u64 start
, u64 end
)
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
};
90 entry
= rb_entry(parent
, struct block_range
, node
);
92 if (start
< entry
->start
)
94 else if (start
> entry
->end
)
95 p
= &parent
->rb_right
;
101 * Didn't find anything.. there's a hole at @start, however @end might
102 * be inside/behind the next range.
105 if (!entry
) /* tree empty */
109 * If the last node is before, advance one to find the next.
112 if (entry
->end
< start
) {
117 next
= rb_entry(n
, struct block_range
, node
);
119 if (next
->start
<= end
) { /* add head: [start...][n->start...] */
120 struct block_range
*head
= malloc(sizeof(struct block_range
));
124 *head
= (struct block_range
){
126 .end
= next
->start
- 1,
131 rb_link_left_of_node(&head
->node
, &next
->node
);
132 rb_insert_color(&head
->node
, &block_ranges
.root
);
133 block_range__debug();
141 * The whole [start..end] range is non-overlapping.
143 entry
= malloc(sizeof(struct block_range
));
147 *entry
= (struct block_range
){
154 rb_link_node(&entry
->node
, parent
, p
);
155 rb_insert_color(&entry
->node
, &block_ranges
.root
);
156 block_range__debug();
164 * We found a range that overlapped with ours, split if needed.
166 if (entry
->start
< start
) { /* split: [e->start...][start...] */
167 struct block_range
*head
= malloc(sizeof(struct block_range
));
171 *head
= (struct block_range
){
172 .start
= entry
->start
,
174 .is_target
= entry
->is_target
,
177 .coverage
= entry
->coverage
,
178 .entry
= entry
->entry
,
181 entry
->start
= start
;
182 entry
->is_target
= 1;
185 rb_link_left_of_node(&head
->node
, &entry
->node
);
186 rb_insert_color(&head
->node
, &block_ranges
.root
);
187 block_range__debug();
189 } else if (entry
->start
== start
)
190 entry
->is_target
= 1;
196 * At this point we've got: @iter.start = [@start...] but @end can still be
197 * inside or beyond it.
202 * If @end is inside @entry, split.
204 if (end
< entry
->end
) { /* split: [...end][...e->end] */
205 struct block_range
*tail
= malloc(sizeof(struct block_range
));
209 *tail
= (struct block_range
){
213 .is_branch
= entry
->is_branch
,
215 .coverage
= entry
->coverage
,
216 .taken
= entry
->taken
,
221 entry
->is_branch
= 1;
225 rb_link_right_of_node(&tail
->node
, &entry
->node
);
226 rb_insert_color(&tail
->node
, &block_ranges
.root
);
227 block_range__debug();
234 * If @end matches @entry, done
236 if (end
== entry
->end
) {
237 entry
->is_branch
= 1;
242 next
= block_range__next(entry
);
247 * If @end is in beyond @entry but not inside @next, add tail.
249 if (end
< next
->start
) { /* add tail: [...e->end][...end] */
250 struct block_range
*tail
;
252 tail
= malloc(sizeof(struct block_range
));
256 *tail
= (struct block_range
){
257 .start
= entry
->end
+ 1,
263 rb_link_right_of_node(&tail
->node
, &entry
->node
);
264 rb_insert_color(&tail
->node
, &block_ranges
.root
);
265 block_range__debug();
272 * If there is a hole between @entry and @next, fill it.
274 if (entry
->end
+ 1 != next
->start
) {
275 struct block_range
*hole
= malloc(sizeof(struct block_range
));
279 *hole
= (struct block_range
){
280 .start
= entry
->end
+ 1,
281 .end
= next
->start
- 1,
286 rb_link_left_of_node(&hole
->node
, &next
->node
);
287 rb_insert_color(&hole
->node
, &block_ranges
.root
);
288 block_range__debug();
295 assert(iter
.start
->start
== start
&& iter
.start
->is_target
);
296 assert(iter
.end
->end
== end
&& iter
.end
->is_branch
);
298 block_ranges
.blocks
++;
305 * Compute coverage as:
307 * br->coverage / br->sym->max_coverage
309 * This ensures each symbol has a 100% spot, to reflect that each symbol has a
310 * most covered section.
312 * Returns [0-1] for coverage and -1 if we had no data what so ever or the
313 * symbol does not exist.
315 double block_range__coverage(struct block_range
*br
)
320 if (block_ranges
.blocks
)
330 return (double)br
->coverage
/ symbol__annotation(sym
)->max_coverage
;