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 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 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 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 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 160df791dc1SJiong Wang 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 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)) { 1790824611fSJiong Wang 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 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 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 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 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 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 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 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 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 383efcef17aSJiong Wang static void draw_bb_node(struct func_node *func, struct bb_node *bb) 384efcef17aSJiong Wang { 385efcef17aSJiong Wang const char *shape; 386efcef17aSJiong Wang 387efcef17aSJiong Wang if (bb->idx == ENTRY_BLOCK_INDEX || bb->idx == EXIT_BLOCK_INDEX) 388efcef17aSJiong Wang shape = "Mdiamond"; 389efcef17aSJiong Wang else 390efcef17aSJiong Wang shape = "record"; 391efcef17aSJiong Wang 392efcef17aSJiong Wang printf("\tfn_%d_bb_%d [shape=%s,style=filled,label=\"", 393efcef17aSJiong Wang func->idx, bb->idx, shape); 394efcef17aSJiong Wang 395efcef17aSJiong Wang if (bb->idx == ENTRY_BLOCK_INDEX) { 396efcef17aSJiong Wang printf("ENTRY"); 397efcef17aSJiong Wang } else if (bb->idx == EXIT_BLOCK_INDEX) { 398efcef17aSJiong Wang printf("EXIT"); 399efcef17aSJiong Wang } else { 400efcef17aSJiong Wang unsigned int start_idx; 401efcef17aSJiong Wang struct dump_data dd = {}; 402efcef17aSJiong Wang 403efcef17aSJiong Wang printf("{"); 404efcef17aSJiong Wang kernel_syms_load(&dd); 405efcef17aSJiong Wang start_idx = bb->head - func->start; 406efcef17aSJiong Wang dump_xlated_for_graph(&dd, bb->head, bb->tail, start_idx); 407efcef17aSJiong Wang kernel_syms_destroy(&dd); 408efcef17aSJiong Wang printf("}"); 409efcef17aSJiong Wang } 410efcef17aSJiong Wang 411efcef17aSJiong Wang printf("\"];\n\n"); 412efcef17aSJiong Wang } 413efcef17aSJiong Wang 414efcef17aSJiong Wang static void draw_bb_succ_edges(struct func_node *func, struct bb_node *bb) 415efcef17aSJiong Wang { 416efcef17aSJiong Wang const char *style = "\"solid,bold\""; 417efcef17aSJiong Wang const char *color = "black"; 418efcef17aSJiong Wang int func_idx = func->idx; 419efcef17aSJiong Wang struct edge_node *e; 420efcef17aSJiong Wang int weight = 10; 421efcef17aSJiong Wang 422efcef17aSJiong Wang if (list_empty(&bb->e_succs)) 423efcef17aSJiong Wang return; 424efcef17aSJiong Wang 425efcef17aSJiong Wang list_for_each_entry(e, &bb->e_succs, l) { 426efcef17aSJiong Wang printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=%s, color=%s, weight=%d, constraint=true", 427efcef17aSJiong Wang func_idx, e->src->idx, func_idx, e->dst->idx, 428efcef17aSJiong Wang style, color, weight); 429efcef17aSJiong Wang printf("];\n"); 430efcef17aSJiong Wang } 431efcef17aSJiong Wang } 432efcef17aSJiong Wang 433efcef17aSJiong Wang static void func_output_bb_def(struct func_node *func) 434efcef17aSJiong Wang { 435efcef17aSJiong Wang struct bb_node *bb; 436efcef17aSJiong Wang 437efcef17aSJiong Wang list_for_each_entry(bb, &func->bbs, l) { 438efcef17aSJiong Wang draw_bb_node(func, bb); 439efcef17aSJiong Wang } 440efcef17aSJiong Wang } 441efcef17aSJiong Wang 442efcef17aSJiong Wang static void func_output_edges(struct func_node *func) 443efcef17aSJiong Wang { 444efcef17aSJiong Wang int func_idx = func->idx; 445efcef17aSJiong Wang struct bb_node *bb; 446efcef17aSJiong Wang 447efcef17aSJiong Wang list_for_each_entry(bb, &func->bbs, l) { 448efcef17aSJiong Wang draw_bb_succ_edges(func, bb); 449efcef17aSJiong Wang } 450efcef17aSJiong Wang 451efcef17aSJiong Wang /* Add an invisible edge from ENTRY to EXIT, this is to 452efcef17aSJiong Wang * improve the graph layout. 453efcef17aSJiong Wang */ 454efcef17aSJiong Wang printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=\"invis\", constraint=true];\n", 455efcef17aSJiong Wang func_idx, ENTRY_BLOCK_INDEX, func_idx, EXIT_BLOCK_INDEX); 456efcef17aSJiong Wang } 457efcef17aSJiong Wang 458efcef17aSJiong Wang static void cfg_dump(struct cfg *cfg) 459efcef17aSJiong Wang { 460efcef17aSJiong Wang struct func_node *func; 461efcef17aSJiong Wang 462efcef17aSJiong Wang printf("digraph \"DOT graph for eBPF program\" {\n"); 463efcef17aSJiong Wang list_for_each_entry(func, &cfg->funcs, l) { 464efcef17aSJiong Wang printf("subgraph \"cluster_%d\" {\n\tstyle=\"dashed\";\n\tcolor=\"black\";\n\tlabel=\"func_%d ()\";\n", 465efcef17aSJiong Wang func->idx, func->idx); 466efcef17aSJiong Wang func_output_bb_def(func); 467efcef17aSJiong Wang func_output_edges(func); 468efcef17aSJiong Wang printf("}\n"); 469efcef17aSJiong Wang } 470efcef17aSJiong Wang printf("}\n"); 471efcef17aSJiong Wang } 472efcef17aSJiong Wang 47380331752SJiong Wang void dump_xlated_cfg(void *buf, unsigned int len) 47480331752SJiong Wang { 47580331752SJiong Wang struct bpf_insn *insn = buf; 47680331752SJiong Wang struct cfg cfg; 47780331752SJiong Wang 47880331752SJiong Wang memset(&cfg, 0, sizeof(cfg)); 47980331752SJiong Wang if (cfg_build(&cfg, insn, len)) 48080331752SJiong Wang return; 48180331752SJiong Wang 482efcef17aSJiong Wang cfg_dump(&cfg); 483efcef17aSJiong Wang 48480331752SJiong Wang cfg_destroy(&cfg); 48580331752SJiong Wang } 486