1 #include "block-range.h"
9 static void block_range__debug(void)
12 * XXX still paranoid for now; see if we can make this depend on
17 u64 old
= 0; /* NULL isn't executable */
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
);
22 assert(old
< entry
->start
);
23 assert(entry
->start
<= entry
->end
); /* single instruction block; jump to a jump */
30 struct block_range
*block_range__find(u64 addr
)
32 struct rb_node
**p
= &block_ranges
.root
.rb_node
;
33 struct rb_node
*parent
= NULL
;
34 struct block_range
*entry
;
38 entry
= rb_entry(parent
, struct block_range
, node
);
40 if (addr
< entry
->start
)
42 else if (addr
> entry
->end
)
43 p
= &parent
->rb_right
;
51 static inline void rb_link_left_of_node(struct rb_node
*left
, struct rb_node
*node
)
53 struct rb_node
**p
= &node
->rb_left
;
58 rb_link_node(left
, node
, p
);
61 static inline void rb_link_right_of_node(struct rb_node
*right
, struct rb_node
*node
)
63 struct rb_node
**p
= &node
->rb_right
;
68 rb_link_node(right
, node
, p
);
73 * @start: branch target starting this basic block
74 * @end: branch ending this basic block
76 * Create all the required block ranges to precisely span the given range.
78 struct block_range_iter
block_range__create(u64 start
, u64 end
)
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
};
87 entry
= rb_entry(parent
, struct block_range
, node
);
89 if (start
< entry
->start
)
91 else if (start
> entry
->end
)
92 p
= &parent
->rb_right
;
98 * Didn't find anything.. there's a hole at @start, however @end might
99 * be inside/behind the next range.
102 if (!entry
) /* tree empty */
106 * If the last node is before, advance one to find the next.
109 if (entry
->end
< start
) {
114 next
= rb_entry(n
, struct block_range
, node
);
116 if (next
->start
<= end
) { /* add head: [start...][n->start...] */
117 struct block_range
*head
= malloc(sizeof(struct block_range
));
121 *head
= (struct block_range
){
123 .end
= next
->start
- 1,
128 rb_link_left_of_node(&head
->node
, &next
->node
);
129 rb_insert_color(&head
->node
, &block_ranges
.root
);
130 block_range__debug();
138 * The whole [start..end] range is non-overlapping.
140 entry
= malloc(sizeof(struct block_range
));
144 *entry
= (struct block_range
){
151 rb_link_node(&entry
->node
, parent
, p
);
152 rb_insert_color(&entry
->node
, &block_ranges
.root
);
153 block_range__debug();
161 * We found a range that overlapped with ours, split if needed.
163 if (entry
->start
< start
) { /* split: [e->start...][start...] */
164 struct block_range
*head
= malloc(sizeof(struct block_range
));
168 *head
= (struct block_range
){
169 .start
= entry
->start
,
171 .is_target
= entry
->is_target
,
174 .coverage
= entry
->coverage
,
175 .entry
= entry
->entry
,
178 entry
->start
= start
;
179 entry
->is_target
= 1;
182 rb_link_left_of_node(&head
->node
, &entry
->node
);
183 rb_insert_color(&head
->node
, &block_ranges
.root
);
184 block_range__debug();
186 } else if (entry
->start
== start
)
187 entry
->is_target
= 1;
193 * At this point we've got: @iter.start = [@start...] but @end can still be
194 * inside or beyond it.
199 * If @end is inside @entry, split.
201 if (end
< entry
->end
) { /* split: [...end][...e->end] */
202 struct block_range
*tail
= malloc(sizeof(struct block_range
));
206 *tail
= (struct block_range
){
210 .is_branch
= entry
->is_branch
,
212 .coverage
= entry
->coverage
,
213 .taken
= entry
->taken
,
218 entry
->is_branch
= 1;
222 rb_link_right_of_node(&tail
->node
, &entry
->node
);
223 rb_insert_color(&tail
->node
, &block_ranges
.root
);
224 block_range__debug();
231 * If @end matches @entry, done
233 if (end
== entry
->end
) {
234 entry
->is_branch
= 1;
239 next
= block_range__next(entry
);
244 * If @end is in beyond @entry but not inside @next, add tail.
246 if (end
< next
->start
) { /* add tail: [...e->end][...end] */
247 struct block_range
*tail
;
249 tail
= malloc(sizeof(struct block_range
));
253 *tail
= (struct block_range
){
254 .start
= entry
->end
+ 1,
260 rb_link_right_of_node(&tail
->node
, &entry
->node
);
261 rb_insert_color(&tail
->node
, &block_ranges
.root
);
262 block_range__debug();
269 * If there is a hole between @entry and @next, fill it.
271 if (entry
->end
+ 1 != next
->start
) {
272 struct block_range
*hole
= malloc(sizeof(struct block_range
));
276 *hole
= (struct block_range
){
277 .start
= entry
->end
+ 1,
278 .end
= next
->start
- 1,
283 rb_link_left_of_node(&hole
->node
, &next
->node
);
284 rb_insert_color(&hole
->node
, &block_ranges
.root
);
285 block_range__debug();
292 assert(iter
.start
->start
== start
&& iter
.start
->is_target
);
293 assert(iter
.end
->end
== end
&& iter
.end
->is_branch
);
295 block_ranges
.blocks
++;
302 * Compute coverage as:
304 * br->coverage / br->sym->max_coverage
306 * This ensures each symbol has a 100% spot, to reflect that each symbol has a
307 * most covered section.
309 * Returns [0-1] for coverage and -1 if we had no data what so ever or the
310 * symbol does not exist.
312 double block_range__coverage(struct block_range
*br
)
317 if (block_ranges
.blocks
)
327 return (double)br
->coverage
/ symbol__annotation(sym
)->max_coverage
;