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
7struct {
8	struct rb_root root;
9	u64 blocks;
10} block_ranges;
11
12static 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
29struct 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
50static 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
60static 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 */
77struct 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
135do_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
190do_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;
247add_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
290done:
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 */
311double 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