180331752SJiong Wang // SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause)
202ff58dcSJakub Kicinski /* Copyright (C) 2018 Netronome Systems, Inc. */
380331752SJiong Wang
480331752SJiong Wang #include <linux/list.h>
580331752SJiong Wang #include <stdlib.h>
680331752SJiong Wang #include <string.h>
780331752SJiong Wang
880331752SJiong Wang #include "cfg.h"
980331752SJiong Wang #include "main.h"
10efcef17aSJiong Wang #include "xlated_dumper.h"
1180331752SJiong Wang
1280331752SJiong Wang struct cfg {
1380331752SJiong Wang struct list_head funcs;
1480331752SJiong Wang int func_num;
1580331752SJiong Wang };
1680331752SJiong Wang
1780331752SJiong Wang struct func_node {
1880331752SJiong Wang struct list_head l;
190824611fSJiong Wang struct list_head bbs;
2080331752SJiong Wang struct bpf_insn *start;
2180331752SJiong Wang struct bpf_insn *end;
2280331752SJiong Wang int idx;
230824611fSJiong Wang int bb_num;
240824611fSJiong Wang };
250824611fSJiong Wang
260824611fSJiong Wang struct bb_node {
270824611fSJiong Wang struct list_head l;
286e9eb7e3SJiong Wang struct list_head e_prevs;
296e9eb7e3SJiong Wang struct list_head e_succs;
300824611fSJiong Wang struct bpf_insn *head;
310824611fSJiong Wang struct bpf_insn *tail;
320824611fSJiong Wang int idx;
3380331752SJiong Wang };
3480331752SJiong Wang
356e9eb7e3SJiong Wang #define EDGE_FLAG_EMPTY 0x0
366e9eb7e3SJiong Wang #define EDGE_FLAG_FALLTHROUGH 0x1
376e9eb7e3SJiong Wang #define EDGE_FLAG_JUMP 0x2
386e9eb7e3SJiong Wang struct edge_node {
396e9eb7e3SJiong Wang struct list_head l;
406e9eb7e3SJiong Wang struct bb_node *src;
416e9eb7e3SJiong Wang struct bb_node *dst;
426e9eb7e3SJiong Wang int flags;
436e9eb7e3SJiong Wang };
446e9eb7e3SJiong Wang
456e9eb7e3SJiong Wang #define ENTRY_BLOCK_INDEX 0
466e9eb7e3SJiong Wang #define EXIT_BLOCK_INDEX 1
476e9eb7e3SJiong Wang #define NUM_FIXED_BLOCKS 2
4880331752SJiong Wang #define func_prev(func) list_prev_entry(func, l)
4980331752SJiong Wang #define func_next(func) list_next_entry(func, l)
500824611fSJiong Wang #define bb_prev(bb) list_prev_entry(bb, l)
510824611fSJiong Wang #define bb_next(bb) list_next_entry(bb, l)
526e9eb7e3SJiong Wang #define entry_bb(func) func_first_bb(func)
536e9eb7e3SJiong Wang #define exit_bb(func) func_last_bb(func)
5480331752SJiong Wang #define cfg_first_func(cfg) \
5580331752SJiong Wang list_first_entry(&cfg->funcs, struct func_node, l)
5680331752SJiong Wang #define cfg_last_func(cfg) \
5780331752SJiong Wang list_last_entry(&cfg->funcs, struct func_node, l)
580824611fSJiong Wang #define func_first_bb(func) \
590824611fSJiong Wang list_first_entry(&func->bbs, struct bb_node, l)
600824611fSJiong Wang #define func_last_bb(func) \
610824611fSJiong Wang list_last_entry(&func->bbs, struct bb_node, l)
6280331752SJiong Wang
cfg_append_func(struct cfg * cfg,struct bpf_insn * insn)6380331752SJiong Wang static struct func_node *cfg_append_func(struct cfg *cfg, struct bpf_insn *insn)
6480331752SJiong Wang {
6580331752SJiong Wang struct func_node *new_func, *func;
6680331752SJiong Wang
6780331752SJiong Wang list_for_each_entry(func, &cfg->funcs, l) {
6880331752SJiong Wang if (func->start == insn)
6980331752SJiong Wang return func;
7080331752SJiong Wang else if (func->start > insn)
7180331752SJiong Wang break;
7280331752SJiong Wang }
7380331752SJiong Wang
7480331752SJiong Wang func = func_prev(func);
7580331752SJiong Wang new_func = calloc(1, sizeof(*new_func));
7680331752SJiong Wang if (!new_func) {
7780331752SJiong Wang p_err("OOM when allocating FUNC node");
7880331752SJiong Wang return NULL;
7980331752SJiong Wang }
8080331752SJiong Wang new_func->start = insn;
8180331752SJiong Wang new_func->idx = cfg->func_num;
8280331752SJiong Wang list_add(&new_func->l, &func->l);
8380331752SJiong Wang cfg->func_num++;
8480331752SJiong Wang
8580331752SJiong Wang return new_func;
8680331752SJiong Wang }
8780331752SJiong Wang
func_append_bb(struct func_node * func,struct bpf_insn * insn)880824611fSJiong Wang static struct bb_node *func_append_bb(struct func_node *func,
890824611fSJiong Wang struct bpf_insn *insn)
900824611fSJiong Wang {
910824611fSJiong Wang struct bb_node *new_bb, *bb;
920824611fSJiong Wang
930824611fSJiong Wang list_for_each_entry(bb, &func->bbs, l) {
940824611fSJiong Wang if (bb->head == insn)
950824611fSJiong Wang return bb;
960824611fSJiong Wang else if (bb->head > insn)
970824611fSJiong Wang break;
980824611fSJiong Wang }
990824611fSJiong Wang
1000824611fSJiong Wang bb = bb_prev(bb);
1010824611fSJiong Wang new_bb = calloc(1, sizeof(*new_bb));
1020824611fSJiong Wang if (!new_bb) {
1030824611fSJiong Wang p_err("OOM when allocating BB node");
1040824611fSJiong Wang return NULL;
1050824611fSJiong Wang }
1060824611fSJiong Wang new_bb->head = insn;
1076e9eb7e3SJiong Wang INIT_LIST_HEAD(&new_bb->e_prevs);
1086e9eb7e3SJiong Wang INIT_LIST_HEAD(&new_bb->e_succs);
1090824611fSJiong Wang list_add(&new_bb->l, &bb->l);
1100824611fSJiong Wang
1110824611fSJiong Wang return new_bb;
1120824611fSJiong Wang }
1130824611fSJiong Wang
func_insert_dummy_bb(struct list_head * after)1146e9eb7e3SJiong Wang static struct bb_node *func_insert_dummy_bb(struct list_head *after)
1156e9eb7e3SJiong Wang {
1166e9eb7e3SJiong Wang struct bb_node *bb;
1176e9eb7e3SJiong Wang
1186e9eb7e3SJiong Wang bb = calloc(1, sizeof(*bb));
1196e9eb7e3SJiong Wang if (!bb) {
1206e9eb7e3SJiong Wang p_err("OOM when allocating BB node");
1216e9eb7e3SJiong Wang return NULL;
1226e9eb7e3SJiong Wang }
1236e9eb7e3SJiong Wang
1246e9eb7e3SJiong Wang INIT_LIST_HEAD(&bb->e_prevs);
1256e9eb7e3SJiong Wang INIT_LIST_HEAD(&bb->e_succs);
1266e9eb7e3SJiong Wang list_add(&bb->l, after);
1276e9eb7e3SJiong Wang
1286e9eb7e3SJiong Wang return bb;
1296e9eb7e3SJiong Wang }
1306e9eb7e3SJiong Wang
cfg_partition_funcs(struct cfg * cfg,struct bpf_insn * cur,struct bpf_insn * end)13180331752SJiong Wang static bool cfg_partition_funcs(struct cfg *cfg, struct bpf_insn *cur,
13280331752SJiong Wang struct bpf_insn *end)
13380331752SJiong Wang {
13480331752SJiong Wang struct func_node *func, *last_func;
13580331752SJiong Wang
13680331752SJiong Wang func = cfg_append_func(cfg, cur);
13780331752SJiong Wang if (!func)
13880331752SJiong Wang return true;
13980331752SJiong Wang
14080331752SJiong Wang for (; cur < end; cur++) {
14180331752SJiong Wang if (cur->code != (BPF_JMP | BPF_CALL))
14280331752SJiong Wang continue;
14380331752SJiong Wang if (cur->src_reg != BPF_PSEUDO_CALL)
14480331752SJiong Wang continue;
14580331752SJiong Wang func = cfg_append_func(cfg, cur + cur->off + 1);
14680331752SJiong Wang if (!func)
14780331752SJiong Wang return true;
14880331752SJiong Wang }
14980331752SJiong Wang
15080331752SJiong Wang last_func = cfg_last_func(cfg);
15180331752SJiong Wang last_func->end = end - 1;
15280331752SJiong Wang func = cfg_first_func(cfg);
15380331752SJiong Wang list_for_each_entry_from(func, &last_func->l, l) {
15480331752SJiong Wang func->end = func_next(func)->start - 1;
15580331752SJiong Wang }
15680331752SJiong Wang
15780331752SJiong Wang return false;
15880331752SJiong Wang }
15980331752SJiong Wang
is_jmp_insn(__u8 code)1606e7e034eSQuentin Monnet static bool is_jmp_insn(__u8 code)
161df791dc1SJiong Wang {
162df791dc1SJiong Wang return BPF_CLASS(code) == BPF_JMP || BPF_CLASS(code) == BPF_JMP32;
163df791dc1SJiong Wang }
164df791dc1SJiong Wang
func_partition_bb_head(struct func_node * func)1650824611fSJiong Wang static bool func_partition_bb_head(struct func_node *func)
1660824611fSJiong Wang {
1670824611fSJiong Wang struct bpf_insn *cur, *end;
1680824611fSJiong Wang struct bb_node *bb;
1690824611fSJiong Wang
1700824611fSJiong Wang cur = func->start;
1710824611fSJiong Wang end = func->end;
1720824611fSJiong Wang INIT_LIST_HEAD(&func->bbs);
1730824611fSJiong Wang bb = func_append_bb(func, cur);
1740824611fSJiong Wang if (!bb)
1750824611fSJiong Wang return true;
1760824611fSJiong Wang
1770824611fSJiong Wang for (; cur <= end; cur++) {
178df791dc1SJiong Wang if (is_jmp_insn(cur->code)) {
1796e7e034eSQuentin Monnet __u8 opcode = BPF_OP(cur->code);
1800824611fSJiong Wang
1810824611fSJiong Wang if (opcode == BPF_EXIT || opcode == BPF_CALL)
1820824611fSJiong Wang continue;
1830824611fSJiong Wang
1840824611fSJiong Wang bb = func_append_bb(func, cur + cur->off + 1);
1850824611fSJiong Wang if (!bb)
1860824611fSJiong Wang return true;
1870824611fSJiong Wang
1880824611fSJiong Wang if (opcode != BPF_JA) {
1890824611fSJiong Wang bb = func_append_bb(func, cur + 1);
1900824611fSJiong Wang if (!bb)
1910824611fSJiong Wang return true;
1920824611fSJiong Wang }
1930824611fSJiong Wang }
1940824611fSJiong Wang }
1950824611fSJiong Wang
1960824611fSJiong Wang return false;
1970824611fSJiong Wang }
1980824611fSJiong Wang
func_partition_bb_tail(struct func_node * func)1990824611fSJiong Wang static void func_partition_bb_tail(struct func_node *func)
2000824611fSJiong Wang {
2016e9eb7e3SJiong Wang unsigned int bb_idx = NUM_FIXED_BLOCKS;
2020824611fSJiong Wang struct bb_node *bb, *last;
2030824611fSJiong Wang
2040824611fSJiong Wang last = func_last_bb(func);
2050824611fSJiong Wang last->tail = func->end;
2060824611fSJiong Wang bb = func_first_bb(func);
2070824611fSJiong Wang list_for_each_entry_from(bb, &last->l, l) {
2080824611fSJiong Wang bb->tail = bb_next(bb)->head - 1;
2090824611fSJiong Wang bb->idx = bb_idx++;
2100824611fSJiong Wang }
2110824611fSJiong Wang
2120824611fSJiong Wang last->idx = bb_idx++;
2130824611fSJiong Wang func->bb_num = bb_idx;
2140824611fSJiong Wang }
2150824611fSJiong Wang
func_add_special_bb(struct func_node * func)2166e9eb7e3SJiong Wang static bool func_add_special_bb(struct func_node *func)
2176e9eb7e3SJiong Wang {
2186e9eb7e3SJiong Wang struct bb_node *bb;
2196e9eb7e3SJiong Wang
2206e9eb7e3SJiong Wang bb = func_insert_dummy_bb(&func->bbs);
2216e9eb7e3SJiong Wang if (!bb)
2226e9eb7e3SJiong Wang return true;
2236e9eb7e3SJiong Wang bb->idx = ENTRY_BLOCK_INDEX;
2246e9eb7e3SJiong Wang
2256e9eb7e3SJiong Wang bb = func_insert_dummy_bb(&func_last_bb(func)->l);
2266e9eb7e3SJiong Wang if (!bb)
2276e9eb7e3SJiong Wang return true;
2286e9eb7e3SJiong Wang bb->idx = EXIT_BLOCK_INDEX;
2296e9eb7e3SJiong Wang
2306e9eb7e3SJiong Wang return false;
2316e9eb7e3SJiong Wang }
2326e9eb7e3SJiong Wang
func_partition_bb(struct func_node * func)2330824611fSJiong Wang static bool func_partition_bb(struct func_node *func)
2340824611fSJiong Wang {
2350824611fSJiong Wang if (func_partition_bb_head(func))
2360824611fSJiong Wang return true;
2370824611fSJiong Wang
2380824611fSJiong Wang func_partition_bb_tail(func);
2390824611fSJiong Wang
2400824611fSJiong Wang return false;
2410824611fSJiong Wang }
2420824611fSJiong Wang
func_search_bb_with_head(struct func_node * func,struct bpf_insn * insn)2436e9eb7e3SJiong Wang static struct bb_node *func_search_bb_with_head(struct func_node *func,
2446e9eb7e3SJiong Wang struct bpf_insn *insn)
2456e9eb7e3SJiong Wang {
2466e9eb7e3SJiong Wang struct bb_node *bb;
2476e9eb7e3SJiong Wang
2486e9eb7e3SJiong Wang list_for_each_entry(bb, &func->bbs, l) {
2496e9eb7e3SJiong Wang if (bb->head == insn)
2506e9eb7e3SJiong Wang return bb;
2516e9eb7e3SJiong Wang }
2526e9eb7e3SJiong Wang
2536e9eb7e3SJiong Wang return NULL;
2546e9eb7e3SJiong Wang }
2556e9eb7e3SJiong Wang
new_edge(struct bb_node * src,struct bb_node * dst,int flags)2566e9eb7e3SJiong Wang static struct edge_node *new_edge(struct bb_node *src, struct bb_node *dst,
2576e9eb7e3SJiong Wang int flags)
2586e9eb7e3SJiong Wang {
2596e9eb7e3SJiong Wang struct edge_node *e;
2606e9eb7e3SJiong Wang
2616e9eb7e3SJiong Wang e = calloc(1, sizeof(*e));
2626e9eb7e3SJiong Wang if (!e) {
2636e9eb7e3SJiong Wang p_err("OOM when allocating edge node");
2646e9eb7e3SJiong Wang return NULL;
2656e9eb7e3SJiong Wang }
2666e9eb7e3SJiong Wang
2676e9eb7e3SJiong Wang if (src)
2686e9eb7e3SJiong Wang e->src = src;
2696e9eb7e3SJiong Wang if (dst)
2706e9eb7e3SJiong Wang e->dst = dst;
2716e9eb7e3SJiong Wang
2726e9eb7e3SJiong Wang e->flags |= flags;
2736e9eb7e3SJiong Wang
2746e9eb7e3SJiong Wang return e;
2756e9eb7e3SJiong Wang }
2766e9eb7e3SJiong Wang
func_add_bb_edges(struct func_node * func)2776e9eb7e3SJiong Wang static bool func_add_bb_edges(struct func_node *func)
2786e9eb7e3SJiong Wang {
2796e9eb7e3SJiong Wang struct bpf_insn *insn;
2806e9eb7e3SJiong Wang struct edge_node *e;
2816e9eb7e3SJiong Wang struct bb_node *bb;
2826e9eb7e3SJiong Wang
2836e9eb7e3SJiong Wang bb = entry_bb(func);
2846e9eb7e3SJiong Wang e = new_edge(bb, bb_next(bb), EDGE_FLAG_FALLTHROUGH);
2856e9eb7e3SJiong Wang if (!e)
2866e9eb7e3SJiong Wang return true;
2876e9eb7e3SJiong Wang list_add_tail(&e->l, &bb->e_succs);
2886e9eb7e3SJiong Wang
2896e9eb7e3SJiong Wang bb = exit_bb(func);
2906e9eb7e3SJiong Wang e = new_edge(bb_prev(bb), bb, EDGE_FLAG_FALLTHROUGH);
2916e9eb7e3SJiong Wang if (!e)
2926e9eb7e3SJiong Wang return true;
2936e9eb7e3SJiong Wang list_add_tail(&e->l, &bb->e_prevs);
2946e9eb7e3SJiong Wang
2956e9eb7e3SJiong Wang bb = entry_bb(func);
2966e9eb7e3SJiong Wang bb = bb_next(bb);
2976e9eb7e3SJiong Wang list_for_each_entry_from(bb, &exit_bb(func)->l, l) {
2986e9eb7e3SJiong Wang e = new_edge(bb, NULL, EDGE_FLAG_EMPTY);
2996e9eb7e3SJiong Wang if (!e)
3006e9eb7e3SJiong Wang return true;
3016e9eb7e3SJiong Wang e->src = bb;
3026e9eb7e3SJiong Wang
3036e9eb7e3SJiong Wang insn = bb->tail;
304df791dc1SJiong Wang if (!is_jmp_insn(insn->code) ||
3056e9eb7e3SJiong Wang BPF_OP(insn->code) == BPF_EXIT) {
3066e9eb7e3SJiong Wang e->dst = bb_next(bb);
3076e9eb7e3SJiong Wang e->flags |= EDGE_FLAG_FALLTHROUGH;
3086e9eb7e3SJiong Wang list_add_tail(&e->l, &bb->e_succs);
3096e9eb7e3SJiong Wang continue;
3106e9eb7e3SJiong Wang } else if (BPF_OP(insn->code) == BPF_JA) {
3116e9eb7e3SJiong Wang e->dst = func_search_bb_with_head(func,
3126e9eb7e3SJiong Wang insn + insn->off + 1);
3136e9eb7e3SJiong Wang e->flags |= EDGE_FLAG_JUMP;
3146e9eb7e3SJiong Wang list_add_tail(&e->l, &bb->e_succs);
3156e9eb7e3SJiong Wang continue;
3166e9eb7e3SJiong Wang }
3176e9eb7e3SJiong Wang
3186e9eb7e3SJiong Wang e->dst = bb_next(bb);
3196e9eb7e3SJiong Wang e->flags |= EDGE_FLAG_FALLTHROUGH;
3206e9eb7e3SJiong Wang list_add_tail(&e->l, &bb->e_succs);
3216e9eb7e3SJiong Wang
3226e9eb7e3SJiong Wang e = new_edge(bb, NULL, EDGE_FLAG_JUMP);
3236e9eb7e3SJiong Wang if (!e)
3246e9eb7e3SJiong Wang return true;
3256e9eb7e3SJiong Wang e->src = bb;
3266e9eb7e3SJiong Wang e->dst = func_search_bb_with_head(func, insn + insn->off + 1);
3276e9eb7e3SJiong Wang list_add_tail(&e->l, &bb->e_succs);
3286e9eb7e3SJiong Wang }
3296e9eb7e3SJiong Wang
3306e9eb7e3SJiong Wang return false;
3316e9eb7e3SJiong Wang }
3326e9eb7e3SJiong Wang
cfg_build(struct cfg * cfg,struct bpf_insn * insn,unsigned int len)33380331752SJiong Wang static bool cfg_build(struct cfg *cfg, struct bpf_insn *insn, unsigned int len)
33480331752SJiong Wang {
33580331752SJiong Wang int cnt = len / sizeof(*insn);
3360824611fSJiong Wang struct func_node *func;
33780331752SJiong Wang
33880331752SJiong Wang INIT_LIST_HEAD(&cfg->funcs);
33980331752SJiong Wang
3400824611fSJiong Wang if (cfg_partition_funcs(cfg, insn, insn + cnt))
3410824611fSJiong Wang return true;
3420824611fSJiong Wang
3430824611fSJiong Wang list_for_each_entry(func, &cfg->funcs, l) {
3446e9eb7e3SJiong Wang if (func_partition_bb(func) || func_add_special_bb(func))
3456e9eb7e3SJiong Wang return true;
3466e9eb7e3SJiong Wang
3476e9eb7e3SJiong Wang if (func_add_bb_edges(func))
3480824611fSJiong Wang return true;
3490824611fSJiong Wang }
3500824611fSJiong Wang
3510824611fSJiong Wang return false;
35280331752SJiong Wang }
35380331752SJiong Wang
cfg_destroy(struct cfg * cfg)35480331752SJiong Wang static void cfg_destroy(struct cfg *cfg)
35580331752SJiong Wang {
35680331752SJiong Wang struct func_node *func, *func2;
35780331752SJiong Wang
35880331752SJiong Wang list_for_each_entry_safe(func, func2, &cfg->funcs, l) {
3590824611fSJiong Wang struct bb_node *bb, *bb2;
3600824611fSJiong Wang
3610824611fSJiong Wang list_for_each_entry_safe(bb, bb2, &func->bbs, l) {
3626e9eb7e3SJiong Wang struct edge_node *e, *e2;
3636e9eb7e3SJiong Wang
3646e9eb7e3SJiong Wang list_for_each_entry_safe(e, e2, &bb->e_prevs, l) {
3656e9eb7e3SJiong Wang list_del(&e->l);
3666e9eb7e3SJiong Wang free(e);
3676e9eb7e3SJiong Wang }
3686e9eb7e3SJiong Wang
3696e9eb7e3SJiong Wang list_for_each_entry_safe(e, e2, &bb->e_succs, l) {
3706e9eb7e3SJiong Wang list_del(&e->l);
3716e9eb7e3SJiong Wang free(e);
3726e9eb7e3SJiong Wang }
3736e9eb7e3SJiong Wang
3740824611fSJiong Wang list_del(&bb->l);
3750824611fSJiong Wang free(bb);
3760824611fSJiong Wang }
3770824611fSJiong Wang
37880331752SJiong Wang list_del(&func->l);
37980331752SJiong Wang free(func);
38080331752SJiong Wang }
38180331752SJiong Wang }
38280331752SJiong Wang
3839fd49684SQuentin Monnet static void
draw_bb_node(struct func_node * func,struct bb_node * bb,struct dump_data * dd,bool opcodes,bool linum)384*7483a7a7SQuentin Monnet draw_bb_node(struct func_node *func, struct bb_node *bb, struct dump_data *dd,
385*7483a7a7SQuentin Monnet bool opcodes, bool linum)
386efcef17aSJiong Wang {
387efcef17aSJiong Wang const char *shape;
388efcef17aSJiong Wang
389efcef17aSJiong Wang if (bb->idx == ENTRY_BLOCK_INDEX || bb->idx == EXIT_BLOCK_INDEX)
390efcef17aSJiong Wang shape = "Mdiamond";
391efcef17aSJiong Wang else
392efcef17aSJiong Wang shape = "record";
393efcef17aSJiong Wang
394efcef17aSJiong Wang printf("\tfn_%d_bb_%d [shape=%s,style=filled,label=\"",
395efcef17aSJiong Wang func->idx, bb->idx, shape);
396efcef17aSJiong Wang
397efcef17aSJiong Wang if (bb->idx == ENTRY_BLOCK_INDEX) {
398efcef17aSJiong Wang printf("ENTRY");
399efcef17aSJiong Wang } else if (bb->idx == EXIT_BLOCK_INDEX) {
400efcef17aSJiong Wang printf("EXIT");
401efcef17aSJiong Wang } else {
402efcef17aSJiong Wang unsigned int start_idx;
4039fd49684SQuentin Monnet printf("{\\\n");
404efcef17aSJiong Wang start_idx = bb->head - func->start;
405*7483a7a7SQuentin Monnet dump_xlated_for_graph(dd, bb->head, bb->tail, start_idx,
406*7483a7a7SQuentin Monnet opcodes, linum);
407efcef17aSJiong Wang printf("}");
408efcef17aSJiong Wang }
409efcef17aSJiong Wang
410efcef17aSJiong Wang printf("\"];\n\n");
411efcef17aSJiong Wang }
412efcef17aSJiong Wang
draw_bb_succ_edges(struct func_node * func,struct bb_node * bb)413efcef17aSJiong Wang static void draw_bb_succ_edges(struct func_node *func, struct bb_node *bb)
414efcef17aSJiong Wang {
415efcef17aSJiong Wang const char *style = "\"solid,bold\"";
416efcef17aSJiong Wang const char *color = "black";
417efcef17aSJiong Wang int func_idx = func->idx;
418efcef17aSJiong Wang struct edge_node *e;
419efcef17aSJiong Wang int weight = 10;
420efcef17aSJiong Wang
421efcef17aSJiong Wang if (list_empty(&bb->e_succs))
422efcef17aSJiong Wang return;
423efcef17aSJiong Wang
424efcef17aSJiong Wang list_for_each_entry(e, &bb->e_succs, l) {
425efcef17aSJiong Wang printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=%s, color=%s, weight=%d, constraint=true",
426efcef17aSJiong Wang func_idx, e->src->idx, func_idx, e->dst->idx,
427efcef17aSJiong Wang style, color, weight);
428efcef17aSJiong Wang printf("];\n");
429efcef17aSJiong Wang }
430efcef17aSJiong Wang }
431efcef17aSJiong Wang
432*7483a7a7SQuentin Monnet static void
func_output_bb_def(struct func_node * func,struct dump_data * dd,bool opcodes,bool linum)433*7483a7a7SQuentin Monnet func_output_bb_def(struct func_node *func, struct dump_data *dd,
434*7483a7a7SQuentin Monnet bool opcodes, bool linum)
435efcef17aSJiong Wang {
436efcef17aSJiong Wang struct bb_node *bb;
437efcef17aSJiong Wang
438efcef17aSJiong Wang list_for_each_entry(bb, &func->bbs, l) {
439*7483a7a7SQuentin Monnet draw_bb_node(func, bb, dd, opcodes, linum);
440efcef17aSJiong Wang }
441efcef17aSJiong Wang }
442efcef17aSJiong Wang
func_output_edges(struct func_node * func)443efcef17aSJiong Wang static void func_output_edges(struct func_node *func)
444efcef17aSJiong Wang {
445efcef17aSJiong Wang int func_idx = func->idx;
446efcef17aSJiong Wang struct bb_node *bb;
447efcef17aSJiong Wang
448efcef17aSJiong Wang list_for_each_entry(bb, &func->bbs, l) {
449efcef17aSJiong Wang draw_bb_succ_edges(func, bb);
450efcef17aSJiong Wang }
451efcef17aSJiong Wang
452efcef17aSJiong Wang /* Add an invisible edge from ENTRY to EXIT, this is to
453efcef17aSJiong Wang * improve the graph layout.
454efcef17aSJiong Wang */
455efcef17aSJiong Wang printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=\"invis\", constraint=true];\n",
456efcef17aSJiong Wang func_idx, ENTRY_BLOCK_INDEX, func_idx, EXIT_BLOCK_INDEX);
457efcef17aSJiong Wang }
458efcef17aSJiong Wang
459*7483a7a7SQuentin Monnet static void
cfg_dump(struct cfg * cfg,struct dump_data * dd,bool opcodes,bool linum)460*7483a7a7SQuentin Monnet cfg_dump(struct cfg *cfg, struct dump_data *dd, bool opcodes, bool linum)
461efcef17aSJiong Wang {
462efcef17aSJiong Wang struct func_node *func;
463efcef17aSJiong Wang
464efcef17aSJiong Wang printf("digraph \"DOT graph for eBPF program\" {\n");
465efcef17aSJiong Wang list_for_each_entry(func, &cfg->funcs, l) {
466efcef17aSJiong Wang printf("subgraph \"cluster_%d\" {\n\tstyle=\"dashed\";\n\tcolor=\"black\";\n\tlabel=\"func_%d ()\";\n",
467efcef17aSJiong Wang func->idx, func->idx);
468*7483a7a7SQuentin Monnet func_output_bb_def(func, dd, opcodes, linum);
469efcef17aSJiong Wang func_output_edges(func);
470efcef17aSJiong Wang printf("}\n");
471efcef17aSJiong Wang }
472efcef17aSJiong Wang printf("}\n");
473efcef17aSJiong Wang }
474efcef17aSJiong Wang
dump_xlated_cfg(struct dump_data * dd,void * buf,unsigned int len,bool opcodes,bool linum)475*7483a7a7SQuentin Monnet void dump_xlated_cfg(struct dump_data *dd, void *buf, unsigned int len,
476*7483a7a7SQuentin Monnet bool opcodes, bool linum)
47780331752SJiong Wang {
47880331752SJiong Wang struct bpf_insn *insn = buf;
47980331752SJiong Wang struct cfg cfg;
48080331752SJiong Wang
48180331752SJiong Wang memset(&cfg, 0, sizeof(cfg));
48280331752SJiong Wang if (cfg_build(&cfg, insn, len))
48380331752SJiong Wang return;
48480331752SJiong Wang
485*7483a7a7SQuentin Monnet cfg_dump(&cfg, dd, opcodes, linum);
486efcef17aSJiong Wang
48780331752SJiong Wang cfg_destroy(&cfg);
48880331752SJiong Wang }
489