1 | // SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause) |
2 | /* Copyright (C) 2018 Netronome Systems, Inc. */ |
3 | |
4 | #include <linux/list.h> |
5 | #include <stdlib.h> |
6 | #include <string.h> |
7 | |
8 | #include "cfg.h" |
9 | #include "main.h" |
10 | #include "xlated_dumper.h" |
11 | |
12 | struct cfg { |
13 | struct list_head funcs; |
14 | int func_num; |
15 | }; |
16 | |
17 | struct func_node { |
18 | struct list_head l; |
19 | struct list_head bbs; |
20 | struct bpf_insn *start; |
21 | struct bpf_insn *end; |
22 | int idx; |
23 | int bb_num; |
24 | }; |
25 | |
26 | struct bb_node { |
27 | struct list_head l; |
28 | struct list_head e_prevs; |
29 | struct list_head e_succs; |
30 | struct bpf_insn *head; |
31 | struct bpf_insn *tail; |
32 | int idx; |
33 | }; |
34 | |
35 | #define EDGE_FLAG_EMPTY 0x0 |
36 | #define EDGE_FLAG_FALLTHROUGH 0x1 |
37 | #define EDGE_FLAG_JUMP 0x2 |
38 | struct edge_node { |
39 | struct list_head l; |
40 | struct bb_node *src; |
41 | struct bb_node *dst; |
42 | int flags; |
43 | }; |
44 | |
45 | #define ENTRY_BLOCK_INDEX 0 |
46 | #define EXIT_BLOCK_INDEX 1 |
47 | #define NUM_FIXED_BLOCKS 2 |
48 | #define func_prev(func) list_prev_entry(func, l) |
49 | #define func_next(func) list_next_entry(func, l) |
50 | #define bb_prev(bb) list_prev_entry(bb, l) |
51 | #define bb_next(bb) list_next_entry(bb, l) |
52 | #define entry_bb(func) func_first_bb(func) |
53 | #define exit_bb(func) func_last_bb(func) |
54 | #define cfg_first_func(cfg) \ |
55 | list_first_entry(&cfg->funcs, struct func_node, l) |
56 | #define cfg_last_func(cfg) \ |
57 | list_last_entry(&cfg->funcs, struct func_node, l) |
58 | #define func_first_bb(func) \ |
59 | list_first_entry(&func->bbs, struct bb_node, l) |
60 | #define func_last_bb(func) \ |
61 | list_last_entry(&func->bbs, struct bb_node, l) |
62 | |
63 | static struct func_node *cfg_append_func(struct cfg *cfg, struct bpf_insn *insn) |
64 | { |
65 | struct func_node *new_func, *func; |
66 | |
67 | list_for_each_entry(func, &cfg->funcs, l) { |
68 | if (func->start == insn) |
69 | return func; |
70 | else if (func->start > insn) |
71 | break; |
72 | } |
73 | |
74 | func = func_prev(func); |
75 | new_func = calloc(1, sizeof(*new_func)); |
76 | if (!new_func) { |
77 | p_err(fmt: "OOM when allocating FUNC node" ); |
78 | return NULL; |
79 | } |
80 | new_func->start = insn; |
81 | new_func->idx = cfg->func_num; |
82 | list_add(new: &new_func->l, head: &func->l); |
83 | cfg->func_num++; |
84 | |
85 | return new_func; |
86 | } |
87 | |
88 | static struct bb_node *func_append_bb(struct func_node *func, |
89 | struct bpf_insn *insn) |
90 | { |
91 | struct bb_node *new_bb, *bb; |
92 | |
93 | list_for_each_entry(bb, &func->bbs, l) { |
94 | if (bb->head == insn) |
95 | return bb; |
96 | else if (bb->head > insn) |
97 | break; |
98 | } |
99 | |
100 | bb = bb_prev(bb); |
101 | new_bb = calloc(1, sizeof(*new_bb)); |
102 | if (!new_bb) { |
103 | p_err(fmt: "OOM when allocating BB node" ); |
104 | return NULL; |
105 | } |
106 | new_bb->head = insn; |
107 | INIT_LIST_HEAD(list: &new_bb->e_prevs); |
108 | INIT_LIST_HEAD(list: &new_bb->e_succs); |
109 | list_add(new: &new_bb->l, head: &bb->l); |
110 | |
111 | return new_bb; |
112 | } |
113 | |
114 | static struct bb_node *func_insert_dummy_bb(struct list_head *after) |
115 | { |
116 | struct bb_node *bb; |
117 | |
118 | bb = calloc(1, sizeof(*bb)); |
119 | if (!bb) { |
120 | p_err(fmt: "OOM when allocating BB node" ); |
121 | return NULL; |
122 | } |
123 | |
124 | INIT_LIST_HEAD(list: &bb->e_prevs); |
125 | INIT_LIST_HEAD(list: &bb->e_succs); |
126 | list_add(new: &bb->l, head: after); |
127 | |
128 | return bb; |
129 | } |
130 | |
131 | static bool cfg_partition_funcs(struct cfg *cfg, struct bpf_insn *cur, |
132 | struct bpf_insn *end) |
133 | { |
134 | struct func_node *func, *last_func; |
135 | |
136 | func = cfg_append_func(cfg, insn: cur); |
137 | if (!func) |
138 | return true; |
139 | |
140 | for (; cur < end; cur++) { |
141 | if (cur->code != (BPF_JMP | BPF_CALL)) |
142 | continue; |
143 | if (cur->src_reg != BPF_PSEUDO_CALL) |
144 | continue; |
145 | func = cfg_append_func(cfg, insn: cur + cur->off + 1); |
146 | if (!func) |
147 | return true; |
148 | } |
149 | |
150 | last_func = cfg_last_func(cfg); |
151 | last_func->end = end - 1; |
152 | func = cfg_first_func(cfg); |
153 | list_for_each_entry_from(func, &last_func->l, l) { |
154 | func->end = func_next(func)->start - 1; |
155 | } |
156 | |
157 | return false; |
158 | } |
159 | |
160 | static bool is_jmp_insn(__u8 code) |
161 | { |
162 | return BPF_CLASS(code) == BPF_JMP || BPF_CLASS(code) == BPF_JMP32; |
163 | } |
164 | |
165 | static bool func_partition_bb_head(struct func_node *func) |
166 | { |
167 | struct bpf_insn *cur, *end; |
168 | struct bb_node *bb; |
169 | |
170 | cur = func->start; |
171 | end = func->end; |
172 | INIT_LIST_HEAD(list: &func->bbs); |
173 | bb = func_append_bb(func, insn: cur); |
174 | if (!bb) |
175 | return true; |
176 | |
177 | for (; cur <= end; cur++) { |
178 | if (is_jmp_insn(code: cur->code)) { |
179 | __u8 opcode = BPF_OP(cur->code); |
180 | |
181 | if (opcode == BPF_EXIT || opcode == BPF_CALL) |
182 | continue; |
183 | |
184 | bb = func_append_bb(func, insn: cur + cur->off + 1); |
185 | if (!bb) |
186 | return true; |
187 | |
188 | if (opcode != BPF_JA) { |
189 | bb = func_append_bb(func, insn: cur + 1); |
190 | if (!bb) |
191 | return true; |
192 | } |
193 | } |
194 | } |
195 | |
196 | return false; |
197 | } |
198 | |
199 | static void func_partition_bb_tail(struct func_node *func) |
200 | { |
201 | unsigned int bb_idx = NUM_FIXED_BLOCKS; |
202 | struct bb_node *bb, *last; |
203 | |
204 | last = func_last_bb(func); |
205 | last->tail = func->end; |
206 | bb = func_first_bb(func); |
207 | list_for_each_entry_from(bb, &last->l, l) { |
208 | bb->tail = bb_next(bb)->head - 1; |
209 | bb->idx = bb_idx++; |
210 | } |
211 | |
212 | last->idx = bb_idx++; |
213 | func->bb_num = bb_idx; |
214 | } |
215 | |
216 | static bool func_add_special_bb(struct func_node *func) |
217 | { |
218 | struct bb_node *bb; |
219 | |
220 | bb = func_insert_dummy_bb(after: &func->bbs); |
221 | if (!bb) |
222 | return true; |
223 | bb->idx = ENTRY_BLOCK_INDEX; |
224 | |
225 | bb = func_insert_dummy_bb(after: &func_last_bb(func)->l); |
226 | if (!bb) |
227 | return true; |
228 | bb->idx = EXIT_BLOCK_INDEX; |
229 | |
230 | return false; |
231 | } |
232 | |
233 | static bool func_partition_bb(struct func_node *func) |
234 | { |
235 | if (func_partition_bb_head(func)) |
236 | return true; |
237 | |
238 | func_partition_bb_tail(func); |
239 | |
240 | return false; |
241 | } |
242 | |
243 | static struct bb_node *func_search_bb_with_head(struct func_node *func, |
244 | struct bpf_insn *insn) |
245 | { |
246 | struct bb_node *bb; |
247 | |
248 | list_for_each_entry(bb, &func->bbs, l) { |
249 | if (bb->head == insn) |
250 | return bb; |
251 | } |
252 | |
253 | return NULL; |
254 | } |
255 | |
256 | static struct edge_node *new_edge(struct bb_node *src, struct bb_node *dst, |
257 | int flags) |
258 | { |
259 | struct edge_node *e; |
260 | |
261 | e = calloc(1, sizeof(*e)); |
262 | if (!e) { |
263 | p_err(fmt: "OOM when allocating edge node" ); |
264 | return NULL; |
265 | } |
266 | |
267 | if (src) |
268 | e->src = src; |
269 | if (dst) |
270 | e->dst = dst; |
271 | |
272 | e->flags |= flags; |
273 | |
274 | return e; |
275 | } |
276 | |
277 | static bool func_add_bb_edges(struct func_node *func) |
278 | { |
279 | struct bpf_insn *insn; |
280 | struct edge_node *e; |
281 | struct bb_node *bb; |
282 | |
283 | bb = entry_bb(func); |
284 | e = new_edge(src: bb, bb_next(bb), EDGE_FLAG_FALLTHROUGH); |
285 | if (!e) |
286 | return true; |
287 | list_add_tail(new: &e->l, head: &bb->e_succs); |
288 | |
289 | bb = exit_bb(func); |
290 | e = new_edge(bb_prev(bb), dst: bb, EDGE_FLAG_FALLTHROUGH); |
291 | if (!e) |
292 | return true; |
293 | list_add_tail(new: &e->l, head: &bb->e_prevs); |
294 | |
295 | bb = entry_bb(func); |
296 | bb = bb_next(bb); |
297 | list_for_each_entry_from(bb, &exit_bb(func)->l, l) { |
298 | e = new_edge(src: bb, NULL, EDGE_FLAG_EMPTY); |
299 | if (!e) |
300 | return true; |
301 | e->src = bb; |
302 | |
303 | insn = bb->tail; |
304 | if (!is_jmp_insn(code: insn->code) || |
305 | BPF_OP(insn->code) == BPF_EXIT) { |
306 | e->dst = bb_next(bb); |
307 | e->flags |= EDGE_FLAG_FALLTHROUGH; |
308 | list_add_tail(new: &e->l, head: &bb->e_succs); |
309 | continue; |
310 | } else if (BPF_OP(insn->code) == BPF_JA) { |
311 | e->dst = func_search_bb_with_head(func, |
312 | insn: insn + insn->off + 1); |
313 | e->flags |= EDGE_FLAG_JUMP; |
314 | list_add_tail(new: &e->l, head: &bb->e_succs); |
315 | continue; |
316 | } |
317 | |
318 | e->dst = bb_next(bb); |
319 | e->flags |= EDGE_FLAG_FALLTHROUGH; |
320 | list_add_tail(new: &e->l, head: &bb->e_succs); |
321 | |
322 | e = new_edge(src: bb, NULL, EDGE_FLAG_JUMP); |
323 | if (!e) |
324 | return true; |
325 | e->src = bb; |
326 | e->dst = func_search_bb_with_head(func, insn: insn + insn->off + 1); |
327 | list_add_tail(new: &e->l, head: &bb->e_succs); |
328 | } |
329 | |
330 | return false; |
331 | } |
332 | |
333 | static bool cfg_build(struct cfg *cfg, struct bpf_insn *insn, unsigned int len) |
334 | { |
335 | int cnt = len / sizeof(*insn); |
336 | struct func_node *func; |
337 | |
338 | INIT_LIST_HEAD(list: &cfg->funcs); |
339 | |
340 | if (cfg_partition_funcs(cfg, cur: insn, end: insn + cnt)) |
341 | return true; |
342 | |
343 | list_for_each_entry(func, &cfg->funcs, l) { |
344 | if (func_partition_bb(func) || func_add_special_bb(func)) |
345 | return true; |
346 | |
347 | if (func_add_bb_edges(func)) |
348 | return true; |
349 | } |
350 | |
351 | return false; |
352 | } |
353 | |
354 | static void cfg_destroy(struct cfg *cfg) |
355 | { |
356 | struct func_node *func, *func2; |
357 | |
358 | list_for_each_entry_safe(func, func2, &cfg->funcs, l) { |
359 | struct bb_node *bb, *bb2; |
360 | |
361 | list_for_each_entry_safe(bb, bb2, &func->bbs, l) { |
362 | struct edge_node *e, *e2; |
363 | |
364 | list_for_each_entry_safe(e, e2, &bb->e_prevs, l) { |
365 | list_del(entry: &e->l); |
366 | free(e); |
367 | } |
368 | |
369 | list_for_each_entry_safe(e, e2, &bb->e_succs, l) { |
370 | list_del(entry: &e->l); |
371 | free(e); |
372 | } |
373 | |
374 | list_del(entry: &bb->l); |
375 | free(bb); |
376 | } |
377 | |
378 | list_del(entry: &func->l); |
379 | free(func); |
380 | } |
381 | } |
382 | |
383 | static void |
384 | draw_bb_node(struct func_node *func, struct bb_node *bb, struct dump_data *dd, |
385 | bool opcodes, bool linum) |
386 | { |
387 | const char *shape; |
388 | |
389 | if (bb->idx == ENTRY_BLOCK_INDEX || bb->idx == EXIT_BLOCK_INDEX) |
390 | shape = "Mdiamond" ; |
391 | else |
392 | shape = "record" ; |
393 | |
394 | printf("\tfn_%d_bb_%d [shape=%s,style=filled,label=\"" , |
395 | func->idx, bb->idx, shape); |
396 | |
397 | if (bb->idx == ENTRY_BLOCK_INDEX) { |
398 | printf("ENTRY" ); |
399 | } else if (bb->idx == EXIT_BLOCK_INDEX) { |
400 | printf("EXIT" ); |
401 | } else { |
402 | unsigned int start_idx; |
403 | printf("{\\\n" ); |
404 | start_idx = bb->head - func->start; |
405 | dump_xlated_for_graph(dd, buf: bb->head, buf_end: bb->tail, start_index: start_idx, |
406 | opcodes, linum); |
407 | printf("}" ); |
408 | } |
409 | |
410 | printf("\"];\n\n" ); |
411 | } |
412 | |
413 | static void draw_bb_succ_edges(struct func_node *func, struct bb_node *bb) |
414 | { |
415 | const char *style = "\"solid,bold\"" ; |
416 | const char *color = "black" ; |
417 | int func_idx = func->idx; |
418 | struct edge_node *e; |
419 | int weight = 10; |
420 | |
421 | if (list_empty(head: &bb->e_succs)) |
422 | return; |
423 | |
424 | list_for_each_entry(e, &bb->e_succs, l) { |
425 | printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=%s, color=%s, weight=%d, constraint=true" , |
426 | func_idx, e->src->idx, func_idx, e->dst->idx, |
427 | style, color, weight); |
428 | printf("];\n" ); |
429 | } |
430 | } |
431 | |
432 | static void |
433 | func_output_bb_def(struct func_node *func, struct dump_data *dd, |
434 | bool opcodes, bool linum) |
435 | { |
436 | struct bb_node *bb; |
437 | |
438 | list_for_each_entry(bb, &func->bbs, l) { |
439 | draw_bb_node(func, bb, dd, opcodes, linum); |
440 | } |
441 | } |
442 | |
443 | static void func_output_edges(struct func_node *func) |
444 | { |
445 | int func_idx = func->idx; |
446 | struct bb_node *bb; |
447 | |
448 | list_for_each_entry(bb, &func->bbs, l) { |
449 | draw_bb_succ_edges(func, bb); |
450 | } |
451 | |
452 | /* Add an invisible edge from ENTRY to EXIT, this is to |
453 | * improve the graph layout. |
454 | */ |
455 | printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=\"invis\", constraint=true];\n" , |
456 | func_idx, ENTRY_BLOCK_INDEX, func_idx, EXIT_BLOCK_INDEX); |
457 | } |
458 | |
459 | static void |
460 | cfg_dump(struct cfg *cfg, struct dump_data *dd, bool opcodes, bool linum) |
461 | { |
462 | struct func_node *func; |
463 | |
464 | printf("digraph \"DOT graph for eBPF program\" {\n" ); |
465 | list_for_each_entry(func, &cfg->funcs, l) { |
466 | printf("subgraph \"cluster_%d\" {\n\tstyle=\"dashed\";\n\tcolor=\"black\";\n\tlabel=\"func_%d ()\";\n" , |
467 | func->idx, func->idx); |
468 | func_output_bb_def(func, dd, opcodes, linum); |
469 | func_output_edges(func); |
470 | printf("}\n" ); |
471 | } |
472 | printf("}\n" ); |
473 | } |
474 | |
475 | void dump_xlated_cfg(struct dump_data *dd, void *buf, unsigned int len, |
476 | bool opcodes, bool linum) |
477 | { |
478 | struct bpf_insn *insn = buf; |
479 | struct cfg cfg; |
480 | |
481 | memset(&cfg, 0, sizeof(cfg)); |
482 | if (cfg_build(cfg: &cfg, insn, len)) |
483 | return; |
484 | |
485 | cfg_dump(cfg: &cfg, dd, opcodes, linum); |
486 | |
487 | cfg_destroy(cfg: &cfg); |
488 | } |
489 | |