1 // SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause)
48 #define func_prev(func)		list_prev_entry(func, l)  argument
49 #define func_next(func)		list_next_entry(func, l)  argument
52 #define entry_bb(func)		func_first_bb(func)  argument
53 #define exit_bb(func)		func_last_bb(func)  argument
55 	list_first_entry(&cfg->funcs, struct func_node, l)
57 	list_last_entry(&cfg->funcs, struct func_node, l)
58 #define func_first_bb(func)	\  argument
59 	list_first_entry(&func->bbs, struct bb_node, l)
60 #define func_last_bb(func)	\  argument
61 	list_last_entry(&func->bbs, struct bb_node, l)
65 	struct func_node *new_func, *func;  in cfg_append_func()  local
67 	list_for_each_entry(func, &cfg->funcs, l) {  in cfg_append_func()
68 		if (func->start == insn)  in cfg_append_func()
69 			return func;  in cfg_append_func()
70 		else if (func->start > insn)  in cfg_append_func()
74 	func = func_prev(func);  in cfg_append_func()
77 		p_err("OOM when allocating FUNC node");  in cfg_append_func()
80 	new_func->start = insn;  in cfg_append_func()
81 	new_func->idx = cfg->func_num;  in cfg_append_func()
82 	list_add(&new_func->l, &func->l);  in cfg_append_func()
83 	cfg->func_num++;  in cfg_append_func()
88 static struct bb_node *func_append_bb(struct func_node *func,  in func_append_bb()  argument
93 	list_for_each_entry(bb, &func->bbs, l) {  in func_append_bb()
94 		if (bb->head == insn)  in func_append_bb()
96 		else if (bb->head > insn)  in func_append_bb()
106 	new_bb->head = insn;  in func_append_bb()
107 	INIT_LIST_HEAD(&new_bb->e_prevs);  in func_append_bb()
108 	INIT_LIST_HEAD(&new_bb->e_succs);  in func_append_bb()
109 	list_add(&new_bb->l, &bb->l);  in func_append_bb()
124 	INIT_LIST_HEAD(&bb->e_prevs);  in func_insert_dummy_bb()
125 	INIT_LIST_HEAD(&bb->e_succs);  in func_insert_dummy_bb()
126 	list_add(&bb->l, after);  in func_insert_dummy_bb()
134 	struct func_node *func, *last_func;  in cfg_partition_funcs()  local
136 	func = cfg_append_func(cfg, cur);  in cfg_partition_funcs()
137 	if (!func)  in cfg_partition_funcs()
141 		if (cur->code != (BPF_JMP | BPF_CALL))  in cfg_partition_funcs()
143 		if (cur->src_reg != BPF_PSEUDO_CALL)  in cfg_partition_funcs()
145 		func = cfg_append_func(cfg, cur + cur->off + 1);  in cfg_partition_funcs()
146 		if (!func)  in cfg_partition_funcs()
151 	last_func->end = end - 1;  in cfg_partition_funcs()
152 	func = cfg_first_func(cfg);  in cfg_partition_funcs()
153 	list_for_each_entry_from(func, &last_func->l, l) {  in cfg_partition_funcs()
154 		func->end = func_next(func)->start - 1;  in cfg_partition_funcs()
165 static bool func_partition_bb_head(struct func_node *func)  in func_partition_bb_head()  argument
170 	cur = func->start;  in func_partition_bb_head()
171 	end = func->end;  in func_partition_bb_head()
172 	INIT_LIST_HEAD(&func->bbs);  in func_partition_bb_head()
173 	bb = func_append_bb(func, cur);  in func_partition_bb_head()
178 		if (is_jmp_insn(cur->code)) {  in func_partition_bb_head()
179 			__u8 opcode = BPF_OP(cur->code);  in func_partition_bb_head()
184 			bb = func_append_bb(func, cur + cur->off + 1);  in func_partition_bb_head()
189 				bb = func_append_bb(func, cur + 1);  in func_partition_bb_head()
199 static void func_partition_bb_tail(struct func_node *func)  in func_partition_bb_tail()  argument
204 	last = func_last_bb(func);  in func_partition_bb_tail()
205 	last->tail = func->end;  in func_partition_bb_tail()
206 	bb = func_first_bb(func);  in func_partition_bb_tail()
207 	list_for_each_entry_from(bb, &last->l, l) {  in func_partition_bb_tail()
208 		bb->tail = bb_next(bb)->head - 1;  in func_partition_bb_tail()
209 		bb->idx = bb_idx++;  in func_partition_bb_tail()
212 	last->idx = bb_idx++;  in func_partition_bb_tail()
213 	func->bb_num = bb_idx;  in func_partition_bb_tail()
216 static bool func_add_special_bb(struct func_node *func)  in func_add_special_bb()  argument
220 	bb = func_insert_dummy_bb(&func->bbs);  in func_add_special_bb()
223 	bb->idx = ENTRY_BLOCK_INDEX;  in func_add_special_bb()
225 	bb = func_insert_dummy_bb(&func_last_bb(func)->l);  in func_add_special_bb()
228 	bb->idx = EXIT_BLOCK_INDEX;  in func_add_special_bb()
233 static bool func_partition_bb(struct func_node *func)  in func_partition_bb()  argument
235 	if (func_partition_bb_head(func))  in func_partition_bb()
238 	func_partition_bb_tail(func);  in func_partition_bb()
243 static struct bb_node *func_search_bb_with_head(struct func_node *func,  in func_search_bb_with_head()  argument
248 	list_for_each_entry(bb, &func->bbs, l) {  in func_search_bb_with_head()
249 		if (bb->head == insn)  in func_search_bb_with_head()
268 		e->src = src;  in new_edge()
270 		e->dst = dst;  in new_edge()
272 	e->flags |= flags;  in new_edge()
277 static bool func_add_bb_edges(struct func_node *func)  in func_add_bb_edges()  argument
283 	bb = entry_bb(func);  in func_add_bb_edges()
287 	list_add_tail(&e->l, &bb->e_succs);  in func_add_bb_edges()
289 	bb = exit_bb(func);  in func_add_bb_edges()
293 	list_add_tail(&e->l, &bb->e_prevs);  in func_add_bb_edges()
295 	bb = entry_bb(func);  in func_add_bb_edges()
297 	list_for_each_entry_from(bb, &exit_bb(func)->l, l) {  in func_add_bb_edges()
301 		e->src = bb;  in func_add_bb_edges()
303 		insn = bb->tail;  in func_add_bb_edges()
304 		if (!is_jmp_insn(insn->code) ||  in func_add_bb_edges()
305 		    BPF_OP(insn->code) == BPF_CALL ||  in func_add_bb_edges()
306 		    BPF_OP(insn->code) == BPF_EXIT) {  in func_add_bb_edges()
307 			e->dst = bb_next(bb);  in func_add_bb_edges()
308 			e->flags |= EDGE_FLAG_FALLTHROUGH;  in func_add_bb_edges()
309 			list_add_tail(&e->l, &bb->e_succs);  in func_add_bb_edges()
311 		} else if (BPF_OP(insn->code) == BPF_JA) {  in func_add_bb_edges()
312 			e->dst = func_search_bb_with_head(func,  in func_add_bb_edges()
313 							  insn + insn->off + 1);  in func_add_bb_edges()
314 			e->flags |= EDGE_FLAG_JUMP;  in func_add_bb_edges()
315 			list_add_tail(&e->l, &bb->e_succs);  in func_add_bb_edges()
319 		e->dst = bb_next(bb);  in func_add_bb_edges()
320 		e->flags |= EDGE_FLAG_FALLTHROUGH;  in func_add_bb_edges()
321 		list_add_tail(&e->l, &bb->e_succs);  in func_add_bb_edges()
326 		e->src = bb;  in func_add_bb_edges()
327 		e->dst = func_search_bb_with_head(func, insn + insn->off + 1);  in func_add_bb_edges()
328 		list_add_tail(&e->l, &bb->e_succs);  in func_add_bb_edges()
337 	struct func_node *func;  in cfg_build()  local
339 	INIT_LIST_HEAD(&cfg->funcs);  in cfg_build()
344 	list_for_each_entry(func, &cfg->funcs, l) {  in cfg_build()
345 		if (func_partition_bb(func) || func_add_special_bb(func))  in cfg_build()
348 		if (func_add_bb_edges(func))  in cfg_build()
357 	struct func_node *func, *func2;  in cfg_destroy()  local
359 	list_for_each_entry_safe(func, func2, &cfg->funcs, l) {  in cfg_destroy()
362 		list_for_each_entry_safe(bb, bb2, &func->bbs, l) {  in cfg_destroy()
365 			list_for_each_entry_safe(e, e2, &bb->e_prevs, l) {  in cfg_destroy()
366 				list_del(&e->l);  in cfg_destroy()
370 			list_for_each_entry_safe(e, e2, &bb->e_succs, l) {  in cfg_destroy()
371 				list_del(&e->l);  in cfg_destroy()
375 			list_del(&bb->l);  in cfg_destroy()
379 		list_del(&func->l);  in cfg_destroy()
380 		free(func);  in cfg_destroy()
385 draw_bb_node(struct func_node *func, struct bb_node *bb, struct dump_data *dd,  in draw_bb_node()  argument
390 	if (bb->idx == ENTRY_BLOCK_INDEX || bb->idx == EXIT_BLOCK_INDEX)  in draw_bb_node()
396 	       func->idx, bb->idx, shape);  in draw_bb_node()
398 	if (bb->idx == ENTRY_BLOCK_INDEX) {  in draw_bb_node()
400 	} else if (bb->idx == EXIT_BLOCK_INDEX) {  in draw_bb_node()
405 		start_idx = bb->head - func->start;  in draw_bb_node()
406 		dump_xlated_for_graph(dd, bb->head, bb->tail, start_idx,  in draw_bb_node()
414 static void draw_bb_succ_edges(struct func_node *func, struct bb_node *bb)  in draw_bb_succ_edges()  argument
418 	int func_idx = func->idx;  in draw_bb_succ_edges()
422 	if (list_empty(&bb->e_succs))  in draw_bb_succ_edges()
425 	list_for_each_entry(e, &bb->e_succs, l) {  in draw_bb_succ_edges()
426 		printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=%s, color=%s, weight=%d, constraint=true",  in draw_bb_succ_edges()
427 		       func_idx, e->src->idx, func_idx, e->dst->idx,  in draw_bb_succ_edges()
434 func_output_bb_def(struct func_node *func, struct dump_data *dd,  in func_output_bb_def()  argument
439 	list_for_each_entry(bb, &func->bbs, l) {  in func_output_bb_def()
440 		draw_bb_node(func, bb, dd, opcodes, linum);  in func_output_bb_def()
444 static void func_output_edges(struct func_node *func)  in func_output_edges()  argument
446 	int func_idx = func->idx;  in func_output_edges()
449 	list_for_each_entry(bb, &func->bbs, l) {  in func_output_edges()
450 		draw_bb_succ_edges(func, bb);  in func_output_edges()
456 	printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=\"invis\", constraint=true];\n",  in func_output_edges()
463 	struct func_node *func;  in cfg_dump()  local
466 	list_for_each_entry(func, &cfg->funcs, l) {  in cfg_dump()
468 		       func->idx, func->idx);  in cfg_dump()
469 		func_output_bb_def(func, dd, opcodes, linum);  in cfg_dump()
470 		func_output_edges(func);  in cfg_dump()