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