489 lines · c
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 12struct cfg {13 struct list_head funcs;14 int func_num;15};16 17struct 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 26struct 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 0x036#define EDGE_FLAG_FALLTHROUGH 0x137#define EDGE_FLAG_JUMP 0x238struct 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 046#define EXIT_BLOCK_INDEX 147#define NUM_FIXED_BLOCKS 248#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 63static 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("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_func->l, &func->l);83 cfg->func_num++;84 85 return new_func;86}87 88static 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("OOM when allocating BB node");104 return NULL;105 }106 new_bb->head = insn;107 INIT_LIST_HEAD(&new_bb->e_prevs);108 INIT_LIST_HEAD(&new_bb->e_succs);109 list_add(&new_bb->l, &bb->l);110 111 return new_bb;112}113 114static 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("OOM when allocating BB node");121 return NULL;122 }123 124 INIT_LIST_HEAD(&bb->e_prevs);125 INIT_LIST_HEAD(&bb->e_succs);126 list_add(&bb->l, after);127 128 return bb;129}130 131static 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, 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, 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 160static bool is_jmp_insn(__u8 code)161{162 return BPF_CLASS(code) == BPF_JMP || BPF_CLASS(code) == BPF_JMP32;163}164 165static 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(&func->bbs);173 bb = func_append_bb(func, cur);174 if (!bb)175 return true;176 177 for (; cur <= end; cur++) {178 if (is_jmp_insn(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, cur + cur->off + 1);185 if (!bb)186 return true;187 188 if (opcode != BPF_JA) {189 bb = func_append_bb(func, cur + 1);190 if (!bb)191 return true;192 }193 }194 }195 196 return false;197}198 199static 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 216static bool func_add_special_bb(struct func_node *func)217{218 struct bb_node *bb;219 220 bb = func_insert_dummy_bb(&func->bbs);221 if (!bb)222 return true;223 bb->idx = ENTRY_BLOCK_INDEX;224 225 bb = func_insert_dummy_bb(&func_last_bb(func)->l);226 if (!bb)227 return true;228 bb->idx = EXIT_BLOCK_INDEX;229 230 return false;231}232 233static 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 243static 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 256static 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("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 277static 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(bb, bb_next(bb), EDGE_FLAG_FALLTHROUGH);285 if (!e)286 return true;287 list_add_tail(&e->l, &bb->e_succs);288 289 bb = exit_bb(func);290 e = new_edge(bb_prev(bb), bb, EDGE_FLAG_FALLTHROUGH);291 if (!e)292 return true;293 list_add_tail(&e->l, &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(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(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(&e->l, &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->off + 1);313 e->flags |= EDGE_FLAG_JUMP;314 list_add_tail(&e->l, &bb->e_succs);315 continue;316 }317 318 e->dst = bb_next(bb);319 e->flags |= EDGE_FLAG_FALLTHROUGH;320 list_add_tail(&e->l, &bb->e_succs);321 322 e = new_edge(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->off + 1);327 list_add_tail(&e->l, &bb->e_succs);328 }329 330 return false;331}332 333static 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(&cfg->funcs);339 340 if (cfg_partition_funcs(cfg, insn, 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 354static 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(&e->l);366 free(e);367 }368 369 list_for_each_entry_safe(e, e2, &bb->e_succs, l) {370 list_del(&e->l);371 free(e);372 }373 374 list_del(&bb->l);375 free(bb);376 }377 378 list_del(&func->l);379 free(func);380 }381}382 383static void384draw_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 else392 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, bb->head, bb->tail, start_idx,406 opcodes, linum);407 printf("}");408 }409 410 printf("\"];\n\n");411}412 413static 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(&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 432static void433func_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 443static 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 to453 * 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 459static void460cfg_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 475void 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, insn, len))483 return;484 485 cfg_dump(&cfg, dd, opcodes, linum);486 487 cfg_destroy(&cfg);488}489