xref: /openbmc/linux/tools/bpf/bpftool/cfg.c (revision addee42a) 
1 // SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause)
2 /*
3  * Copyright (C) 2018 Netronome Systems, Inc.
4  *
5  * This software is dual licensed under the GNU General License Version 2,
6  * June 1991 as shown in the file COPYING in the top-level directory of this
7  * source tree or the BSD 2-Clause License provided below.  You have the
8  * option to license this software under the complete terms of either license.
9  *
10  * The BSD 2-Clause License:
11  *
12  *     Redistribution and use in source and binary forms, with or
13  *     without modification, are permitted provided that the following
14  *     conditions are met:
15  *
16  *      1. Redistributions of source code must retain the above
17  *         copyright notice, this list of conditions and the following
18  *         disclaimer.
19  *
20  *      2. Redistributions in binary form must reproduce the above
21  *         copyright notice, this list of conditions and the following
22  *         disclaimer in the documentation and/or other materials
23  *         provided with the distribution.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
29  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35  * POSSIBILITY OF SUCH DAMAGE.
36  */
37 
38 #include <linux/list.h>
39 #include <stdlib.h>
40 #include <string.h>
41 
42 #include "cfg.h"
43 #include "main.h"
44 #include "xlated_dumper.h"
45 
46 struct cfg {
47 	struct list_head funcs;
48 	int func_num;
49 };
50 
51 struct func_node {
52 	struct list_head l;
53 	struct list_head bbs;
54 	struct bpf_insn *start;
55 	struct bpf_insn *end;
56 	int idx;
57 	int bb_num;
58 };
59 
60 struct bb_node {
61 	struct list_head l;
62 	struct list_head e_prevs;
63 	struct list_head e_succs;
64 	struct bpf_insn *head;
65 	struct bpf_insn *tail;
66 	int idx;
67 };
68 
69 #define EDGE_FLAG_EMPTY		0x0
70 #define EDGE_FLAG_FALLTHROUGH	0x1
71 #define EDGE_FLAG_JUMP		0x2
72 struct edge_node {
73 	struct list_head l;
74 	struct bb_node *src;
75 	struct bb_node *dst;
76 	int flags;
77 };
78 
79 #define ENTRY_BLOCK_INDEX	0
80 #define EXIT_BLOCK_INDEX	1
81 #define NUM_FIXED_BLOCKS	2
82 #define func_prev(func)		list_prev_entry(func, l)
83 #define func_next(func)		list_next_entry(func, l)
84 #define bb_prev(bb)		list_prev_entry(bb, l)
85 #define bb_next(bb)		list_next_entry(bb, l)
86 #define entry_bb(func)		func_first_bb(func)
87 #define exit_bb(func)		func_last_bb(func)
88 #define cfg_first_func(cfg)	\
89 	list_first_entry(&cfg->funcs, struct func_node, l)
90 #define cfg_last_func(cfg)	\
91 	list_last_entry(&cfg->funcs, struct func_node, l)
92 #define func_first_bb(func)	\
93 	list_first_entry(&func->bbs, struct bb_node, l)
94 #define func_last_bb(func)	\
95 	list_last_entry(&func->bbs, struct bb_node, l)
96 
97 static struct func_node *cfg_append_func(struct cfg *cfg, struct bpf_insn *insn)
98 {
99 	struct func_node *new_func, *func;
100 
101 	list_for_each_entry(func, &cfg->funcs, l) {
102 		if (func->start == insn)
103 			return func;
104 		else if (func->start > insn)
105 			break;
106 	}
107 
108 	func = func_prev(func);
109 	new_func = calloc(1, sizeof(*new_func));
110 	if (!new_func) {
111 		p_err("OOM when allocating FUNC node");
112 		return NULL;
113 	}
114 	new_func->start = insn;
115 	new_func->idx = cfg->func_num;
116 	list_add(&new_func->l, &func->l);
117 	cfg->func_num++;
118 
119 	return new_func;
120 }
121 
122 static struct bb_node *func_append_bb(struct func_node *func,
123 				      struct bpf_insn *insn)
124 {
125 	struct bb_node *new_bb, *bb;
126 
127 	list_for_each_entry(bb, &func->bbs, l) {
128 		if (bb->head == insn)
129 			return bb;
130 		else if (bb->head > insn)
131 			break;
132 	}
133 
134 	bb = bb_prev(bb);
135 	new_bb = calloc(1, sizeof(*new_bb));
136 	if (!new_bb) {
137 		p_err("OOM when allocating BB node");
138 		return NULL;
139 	}
140 	new_bb->head = insn;
141 	INIT_LIST_HEAD(&new_bb->e_prevs);
142 	INIT_LIST_HEAD(&new_bb->e_succs);
143 	list_add(&new_bb->l, &bb->l);
144 
145 	return new_bb;
146 }
147 
148 static struct bb_node *func_insert_dummy_bb(struct list_head *after)
149 {
150 	struct bb_node *bb;
151 
152 	bb = calloc(1, sizeof(*bb));
153 	if (!bb) {
154 		p_err("OOM when allocating BB node");
155 		return NULL;
156 	}
157 
158 	INIT_LIST_HEAD(&bb->e_prevs);
159 	INIT_LIST_HEAD(&bb->e_succs);
160 	list_add(&bb->l, after);
161 
162 	return bb;
163 }
164 
165 static bool cfg_partition_funcs(struct cfg *cfg, struct bpf_insn *cur,
166 				struct bpf_insn *end)
167 {
168 	struct func_node *func, *last_func;
169 
170 	func = cfg_append_func(cfg, cur);
171 	if (!func)
172 		return true;
173 
174 	for (; cur < end; cur++) {
175 		if (cur->code != (BPF_JMP | BPF_CALL))
176 			continue;
177 		if (cur->src_reg != BPF_PSEUDO_CALL)
178 			continue;
179 		func = cfg_append_func(cfg, cur + cur->off + 1);
180 		if (!func)
181 			return true;
182 	}
183 
184 	last_func = cfg_last_func(cfg);
185 	last_func->end = end - 1;
186 	func = cfg_first_func(cfg);
187 	list_for_each_entry_from(func, &last_func->l, l) {
188 		func->end = func_next(func)->start - 1;
189 	}
190 
191 	return false;
192 }
193 
194 static bool func_partition_bb_head(struct func_node *func)
195 {
196 	struct bpf_insn *cur, *end;
197 	struct bb_node *bb;
198 
199 	cur = func->start;
200 	end = func->end;
201 	INIT_LIST_HEAD(&func->bbs);
202 	bb = func_append_bb(func, cur);
203 	if (!bb)
204 		return true;
205 
206 	for (; cur <= end; cur++) {
207 		if (BPF_CLASS(cur->code) == BPF_JMP) {
208 			u8 opcode = BPF_OP(cur->code);
209 
210 			if (opcode == BPF_EXIT || opcode == BPF_CALL)
211 				continue;
212 
213 			bb = func_append_bb(func, cur + cur->off + 1);
214 			if (!bb)
215 				return true;
216 
217 			if (opcode != BPF_JA) {
218 				bb = func_append_bb(func, cur + 1);
219 				if (!bb)
220 					return true;
221 			}
222 		}
223 	}
224 
225 	return false;
226 }
227 
228 static void func_partition_bb_tail(struct func_node *func)
229 {
230 	unsigned int bb_idx = NUM_FIXED_BLOCKS;
231 	struct bb_node *bb, *last;
232 
233 	last = func_last_bb(func);
234 	last->tail = func->end;
235 	bb = func_first_bb(func);
236 	list_for_each_entry_from(bb, &last->l, l) {
237 		bb->tail = bb_next(bb)->head - 1;
238 		bb->idx = bb_idx++;
239 	}
240 
241 	last->idx = bb_idx++;
242 	func->bb_num = bb_idx;
243 }
244 
245 static bool func_add_special_bb(struct func_node *func)
246 {
247 	struct bb_node *bb;
248 
249 	bb = func_insert_dummy_bb(&func->bbs);
250 	if (!bb)
251 		return true;
252 	bb->idx = ENTRY_BLOCK_INDEX;
253 
254 	bb = func_insert_dummy_bb(&func_last_bb(func)->l);
255 	if (!bb)
256 		return true;
257 	bb->idx = EXIT_BLOCK_INDEX;
258 
259 	return false;
260 }
261 
262 static bool func_partition_bb(struct func_node *func)
263 {
264 	if (func_partition_bb_head(func))
265 		return true;
266 
267 	func_partition_bb_tail(func);
268 
269 	return false;
270 }
271 
272 static struct bb_node *func_search_bb_with_head(struct func_node *func,
273 						struct bpf_insn *insn)
274 {
275 	struct bb_node *bb;
276 
277 	list_for_each_entry(bb, &func->bbs, l) {
278 		if (bb->head == insn)
279 			return bb;
280 	}
281 
282 	return NULL;
283 }
284 
285 static struct edge_node *new_edge(struct bb_node *src, struct bb_node *dst,
286 				  int flags)
287 {
288 	struct edge_node *e;
289 
290 	e = calloc(1, sizeof(*e));
291 	if (!e) {
292 		p_err("OOM when allocating edge node");
293 		return NULL;
294 	}
295 
296 	if (src)
297 		e->src = src;
298 	if (dst)
299 		e->dst = dst;
300 
301 	e->flags |= flags;
302 
303 	return e;
304 }
305 
306 static bool func_add_bb_edges(struct func_node *func)
307 {
308 	struct bpf_insn *insn;
309 	struct edge_node *e;
310 	struct bb_node *bb;
311 
312 	bb = entry_bb(func);
313 	e = new_edge(bb, bb_next(bb), EDGE_FLAG_FALLTHROUGH);
314 	if (!e)
315 		return true;
316 	list_add_tail(&e->l, &bb->e_succs);
317 
318 	bb = exit_bb(func);
319 	e = new_edge(bb_prev(bb), bb, EDGE_FLAG_FALLTHROUGH);
320 	if (!e)
321 		return true;
322 	list_add_tail(&e->l, &bb->e_prevs);
323 
324 	bb = entry_bb(func);
325 	bb = bb_next(bb);
326 	list_for_each_entry_from(bb, &exit_bb(func)->l, l) {
327 		e = new_edge(bb, NULL, EDGE_FLAG_EMPTY);
328 		if (!e)
329 			return true;
330 		e->src = bb;
331 
332 		insn = bb->tail;
333 		if (BPF_CLASS(insn->code) != BPF_JMP ||
334 		    BPF_OP(insn->code) == BPF_EXIT) {
335 			e->dst = bb_next(bb);
336 			e->flags |= EDGE_FLAG_FALLTHROUGH;
337 			list_add_tail(&e->l, &bb->e_succs);
338 			continue;
339 		} else if (BPF_OP(insn->code) == BPF_JA) {
340 			e->dst = func_search_bb_with_head(func,
341 							  insn + insn->off + 1);
342 			e->flags |= EDGE_FLAG_JUMP;
343 			list_add_tail(&e->l, &bb->e_succs);
344 			continue;
345 		}
346 
347 		e->dst = bb_next(bb);
348 		e->flags |= EDGE_FLAG_FALLTHROUGH;
349 		list_add_tail(&e->l, &bb->e_succs);
350 
351 		e = new_edge(bb, NULL, EDGE_FLAG_JUMP);
352 		if (!e)
353 			return true;
354 		e->src = bb;
355 		e->dst = func_search_bb_with_head(func, insn + insn->off + 1);
356 		list_add_tail(&e->l, &bb->e_succs);
357 	}
358 
359 	return false;
360 }
361 
362 static bool cfg_build(struct cfg *cfg, struct bpf_insn *insn, unsigned int len)
363 {
364 	int cnt = len / sizeof(*insn);
365 	struct func_node *func;
366 
367 	INIT_LIST_HEAD(&cfg->funcs);
368 
369 	if (cfg_partition_funcs(cfg, insn, insn + cnt))
370 		return true;
371 
372 	list_for_each_entry(func, &cfg->funcs, l) {
373 		if (func_partition_bb(func) || func_add_special_bb(func))
374 			return true;
375 
376 		if (func_add_bb_edges(func))
377 			return true;
378 	}
379 
380 	return false;
381 }
382 
383 static void cfg_destroy(struct cfg *cfg)
384 {
385 	struct func_node *func, *func2;
386 
387 	list_for_each_entry_safe(func, func2, &cfg->funcs, l) {
388 		struct bb_node *bb, *bb2;
389 
390 		list_for_each_entry_safe(bb, bb2, &func->bbs, l) {
391 			struct edge_node *e, *e2;
392 
393 			list_for_each_entry_safe(e, e2, &bb->e_prevs, l) {
394 				list_del(&e->l);
395 				free(e);
396 			}
397 
398 			list_for_each_entry_safe(e, e2, &bb->e_succs, l) {
399 				list_del(&e->l);
400 				free(e);
401 			}
402 
403 			list_del(&bb->l);
404 			free(bb);
405 		}
406 
407 		list_del(&func->l);
408 		free(func);
409 	}
410 }
411 
412 static void draw_bb_node(struct func_node *func, struct bb_node *bb)
413 {
414 	const char *shape;
415 
416 	if (bb->idx == ENTRY_BLOCK_INDEX || bb->idx == EXIT_BLOCK_INDEX)
417 		shape = "Mdiamond";
418 	else
419 		shape = "record";
420 
421 	printf("\tfn_%d_bb_%d [shape=%s,style=filled,label=\"",
422 	       func->idx, bb->idx, shape);
423 
424 	if (bb->idx == ENTRY_BLOCK_INDEX) {
425 		printf("ENTRY");
426 	} else if (bb->idx == EXIT_BLOCK_INDEX) {
427 		printf("EXIT");
428 	} else {
429 		unsigned int start_idx;
430 		struct dump_data dd = {};
431 
432 		printf("{");
433 		kernel_syms_load(&dd);
434 		start_idx = bb->head - func->start;
435 		dump_xlated_for_graph(&dd, bb->head, bb->tail, start_idx);
436 		kernel_syms_destroy(&dd);
437 		printf("}");
438 	}
439 
440 	printf("\"];\n\n");
441 }
442 
443 static void draw_bb_succ_edges(struct func_node *func, struct bb_node *bb)
444 {
445 	const char *style = "\"solid,bold\"";
446 	const char *color = "black";
447 	int func_idx = func->idx;
448 	struct edge_node *e;
449 	int weight = 10;
450 
451 	if (list_empty(&bb->e_succs))
452 		return;
453 
454 	list_for_each_entry(e, &bb->e_succs, l) {
455 		printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=%s, color=%s, weight=%d, constraint=true",
456 		       func_idx, e->src->idx, func_idx, e->dst->idx,
457 		       style, color, weight);
458 		printf("];\n");
459 	}
460 }
461 
462 static void func_output_bb_def(struct func_node *func)
463 {
464 	struct bb_node *bb;
465 
466 	list_for_each_entry(bb, &func->bbs, l) {
467 		draw_bb_node(func, bb);
468 	}
469 }
470 
471 static void func_output_edges(struct func_node *func)
472 {
473 	int func_idx = func->idx;
474 	struct bb_node *bb;
475 
476 	list_for_each_entry(bb, &func->bbs, l) {
477 		draw_bb_succ_edges(func, bb);
478 	}
479 
480 	/* Add an invisible edge from ENTRY to EXIT, this is to
481 	 * improve the graph layout.
482 	 */
483 	printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=\"invis\", constraint=true];\n",
484 	       func_idx, ENTRY_BLOCK_INDEX, func_idx, EXIT_BLOCK_INDEX);
485 }
486 
487 static void cfg_dump(struct cfg *cfg)
488 {
489 	struct func_node *func;
490 
491 	printf("digraph \"DOT graph for eBPF program\" {\n");
492 	list_for_each_entry(func, &cfg->funcs, l) {
493 		printf("subgraph \"cluster_%d\" {\n\tstyle=\"dashed\";\n\tcolor=\"black\";\n\tlabel=\"func_%d ()\";\n",
494 		       func->idx, func->idx);
495 		func_output_bb_def(func);
496 		func_output_edges(func);
497 		printf("}\n");
498 	}
499 	printf("}\n");
500 }
501 
502 void dump_xlated_cfg(void *buf, unsigned int len)
503 {
504 	struct bpf_insn *insn = buf;
505 	struct cfg cfg;
506 
507 	memset(&cfg, 0, sizeof(cfg));
508 	if (cfg_build(&cfg, insn, len))
509 		return;
510 
511 	cfg_dump(&cfg);
512 
513 	cfg_destroy(&cfg);
514 }
515