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 
7 struct {
8 	struct rb_root root;
9 	u64 blocks;
10 } block_ranges;
11 
block_range__debug(void)12 static 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 
block_range__find(u64 addr)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 
rb_link_left_of_node(struct rb_node * left,struct rb_node * node)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 
rb_link_right_of_node(struct rb_node * right,struct rb_node * node)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  */
block_range__create(u64 start,u64 end)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  */
block_range__coverage(struct block_range * br)311 double block_range__coverage(struct block_range *br)
312 {
313 	struct symbol *sym;
314 
315 	if (!br) {
316 		if (block_ranges.blocks)
317 			return 0;
318 
319 		return -1;
320 	}
321 
322 	sym = br->sym;
323 	if (!sym)
324 		return -1;
325 
326 	return (double)br->coverage / symbol__annotation(sym)->max_coverage;
327 }
328