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("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 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("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 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("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 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, 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 160 static bool func_partition_bb_head(struct func_node *func) 161 { 162 struct bpf_insn *cur, *end; 163 struct bb_node *bb; 164 165 cur = func->start; 166 end = func->end; 167 INIT_LIST_HEAD(&func->bbs); 168 bb = func_append_bb(func, cur); 169 if (!bb) 170 return true; 171 172 for (; cur <= end; cur++) { 173 if (BPF_CLASS(cur->code) == BPF_JMP) { 174 u8 opcode = BPF_OP(cur->code); 175 176 if (opcode == BPF_EXIT || opcode == BPF_CALL) 177 continue; 178 179 bb = func_append_bb(func, cur + cur->off + 1); 180 if (!bb) 181 return true; 182 183 if (opcode != BPF_JA) { 184 bb = func_append_bb(func, cur + 1); 185 if (!bb) 186 return true; 187 } 188 } 189 } 190 191 return false; 192 } 193 194 static void func_partition_bb_tail(struct func_node *func) 195 { 196 unsigned int bb_idx = NUM_FIXED_BLOCKS; 197 struct bb_node *bb, *last; 198 199 last = func_last_bb(func); 200 last->tail = func->end; 201 bb = func_first_bb(func); 202 list_for_each_entry_from(bb, &last->l, l) { 203 bb->tail = bb_next(bb)->head - 1; 204 bb->idx = bb_idx++; 205 } 206 207 last->idx = bb_idx++; 208 func->bb_num = bb_idx; 209 } 210 211 static bool func_add_special_bb(struct func_node *func) 212 { 213 struct bb_node *bb; 214 215 bb = func_insert_dummy_bb(&func->bbs); 216 if (!bb) 217 return true; 218 bb->idx = ENTRY_BLOCK_INDEX; 219 220 bb = func_insert_dummy_bb(&func_last_bb(func)->l); 221 if (!bb) 222 return true; 223 bb->idx = EXIT_BLOCK_INDEX; 224 225 return false; 226 } 227 228 static bool func_partition_bb(struct func_node *func) 229 { 230 if (func_partition_bb_head(func)) 231 return true; 232 233 func_partition_bb_tail(func); 234 235 return false; 236 } 237 238 static struct bb_node *func_search_bb_with_head(struct func_node *func, 239 struct bpf_insn *insn) 240 { 241 struct bb_node *bb; 242 243 list_for_each_entry(bb, &func->bbs, l) { 244 if (bb->head == insn) 245 return bb; 246 } 247 248 return NULL; 249 } 250 251 static struct edge_node *new_edge(struct bb_node *src, struct bb_node *dst, 252 int flags) 253 { 254 struct edge_node *e; 255 256 e = calloc(1, sizeof(*e)); 257 if (!e) { 258 p_err("OOM when allocating edge node"); 259 return NULL; 260 } 261 262 if (src) 263 e->src = src; 264 if (dst) 265 e->dst = dst; 266 267 e->flags |= flags; 268 269 return e; 270 } 271 272 static bool func_add_bb_edges(struct func_node *func) 273 { 274 struct bpf_insn *insn; 275 struct edge_node *e; 276 struct bb_node *bb; 277 278 bb = entry_bb(func); 279 e = new_edge(bb, bb_next(bb), EDGE_FLAG_FALLTHROUGH); 280 if (!e) 281 return true; 282 list_add_tail(&e->l, &bb->e_succs); 283 284 bb = exit_bb(func); 285 e = new_edge(bb_prev(bb), bb, EDGE_FLAG_FALLTHROUGH); 286 if (!e) 287 return true; 288 list_add_tail(&e->l, &bb->e_prevs); 289 290 bb = entry_bb(func); 291 bb = bb_next(bb); 292 list_for_each_entry_from(bb, &exit_bb(func)->l, l) { 293 e = new_edge(bb, NULL, EDGE_FLAG_EMPTY); 294 if (!e) 295 return true; 296 e->src = bb; 297 298 insn = bb->tail; 299 if (BPF_CLASS(insn->code) != BPF_JMP || 300 BPF_OP(insn->code) == BPF_EXIT) { 301 e->dst = bb_next(bb); 302 e->flags |= EDGE_FLAG_FALLTHROUGH; 303 list_add_tail(&e->l, &bb->e_succs); 304 continue; 305 } else if (BPF_OP(insn->code) == BPF_JA) { 306 e->dst = func_search_bb_with_head(func, 307 insn + insn->off + 1); 308 e->flags |= EDGE_FLAG_JUMP; 309 list_add_tail(&e->l, &bb->e_succs); 310 continue; 311 } 312 313 e->dst = bb_next(bb); 314 e->flags |= EDGE_FLAG_FALLTHROUGH; 315 list_add_tail(&e->l, &bb->e_succs); 316 317 e = new_edge(bb, NULL, EDGE_FLAG_JUMP); 318 if (!e) 319 return true; 320 e->src = bb; 321 e->dst = func_search_bb_with_head(func, insn + insn->off + 1); 322 list_add_tail(&e->l, &bb->e_succs); 323 } 324 325 return false; 326 } 327 328 static bool cfg_build(struct cfg *cfg, struct bpf_insn *insn, unsigned int len) 329 { 330 int cnt = len / sizeof(*insn); 331 struct func_node *func; 332 333 INIT_LIST_HEAD(&cfg->funcs); 334 335 if (cfg_partition_funcs(cfg, insn, insn + cnt)) 336 return true; 337 338 list_for_each_entry(func, &cfg->funcs, l) { 339 if (func_partition_bb(func) || func_add_special_bb(func)) 340 return true; 341 342 if (func_add_bb_edges(func)) 343 return true; 344 } 345 346 return false; 347 } 348 349 static void cfg_destroy(struct cfg *cfg) 350 { 351 struct func_node *func, *func2; 352 353 list_for_each_entry_safe(func, func2, &cfg->funcs, l) { 354 struct bb_node *bb, *bb2; 355 356 list_for_each_entry_safe(bb, bb2, &func->bbs, l) { 357 struct edge_node *e, *e2; 358 359 list_for_each_entry_safe(e, e2, &bb->e_prevs, l) { 360 list_del(&e->l); 361 free(e); 362 } 363 364 list_for_each_entry_safe(e, e2, &bb->e_succs, l) { 365 list_del(&e->l); 366 free(e); 367 } 368 369 list_del(&bb->l); 370 free(bb); 371 } 372 373 list_del(&func->l); 374 free(func); 375 } 376 } 377 378 static void draw_bb_node(struct func_node *func, struct bb_node *bb) 379 { 380 const char *shape; 381 382 if (bb->idx == ENTRY_BLOCK_INDEX || bb->idx == EXIT_BLOCK_INDEX) 383 shape = "Mdiamond"; 384 else 385 shape = "record"; 386 387 printf("\tfn_%d_bb_%d [shape=%s,style=filled,label=\"", 388 func->idx, bb->idx, shape); 389 390 if (bb->idx == ENTRY_BLOCK_INDEX) { 391 printf("ENTRY"); 392 } else if (bb->idx == EXIT_BLOCK_INDEX) { 393 printf("EXIT"); 394 } else { 395 unsigned int start_idx; 396 struct dump_data dd = {}; 397 398 printf("{"); 399 kernel_syms_load(&dd); 400 start_idx = bb->head - func->start; 401 dump_xlated_for_graph(&dd, bb->head, bb->tail, start_idx); 402 kernel_syms_destroy(&dd); 403 printf("}"); 404 } 405 406 printf("\"];\n\n"); 407 } 408 409 static void draw_bb_succ_edges(struct func_node *func, struct bb_node *bb) 410 { 411 const char *style = "\"solid,bold\""; 412 const char *color = "black"; 413 int func_idx = func->idx; 414 struct edge_node *e; 415 int weight = 10; 416 417 if (list_empty(&bb->e_succs)) 418 return; 419 420 list_for_each_entry(e, &bb->e_succs, l) { 421 printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=%s, color=%s, weight=%d, constraint=true", 422 func_idx, e->src->idx, func_idx, e->dst->idx, 423 style, color, weight); 424 printf("];\n"); 425 } 426 } 427 428 static void func_output_bb_def(struct func_node *func) 429 { 430 struct bb_node *bb; 431 432 list_for_each_entry(bb, &func->bbs, l) { 433 draw_bb_node(func, bb); 434 } 435 } 436 437 static void func_output_edges(struct func_node *func) 438 { 439 int func_idx = func->idx; 440 struct bb_node *bb; 441 442 list_for_each_entry(bb, &func->bbs, l) { 443 draw_bb_succ_edges(func, bb); 444 } 445 446 /* Add an invisible edge from ENTRY to EXIT, this is to 447 * improve the graph layout. 448 */ 449 printf("\tfn_%d_bb_%d:s -> fn_%d_bb_%d:n [style=\"invis\", constraint=true];\n", 450 func_idx, ENTRY_BLOCK_INDEX, func_idx, EXIT_BLOCK_INDEX); 451 } 452 453 static void cfg_dump(struct cfg *cfg) 454 { 455 struct func_node *func; 456 457 printf("digraph \"DOT graph for eBPF program\" {\n"); 458 list_for_each_entry(func, &cfg->funcs, l) { 459 printf("subgraph \"cluster_%d\" {\n\tstyle=\"dashed\";\n\tcolor=\"black\";\n\tlabel=\"func_%d ()\";\n", 460 func->idx, func->idx); 461 func_output_bb_def(func); 462 func_output_edges(func); 463 printf("}\n"); 464 } 465 printf("}\n"); 466 } 467 468 void dump_xlated_cfg(void *buf, unsigned int len) 469 { 470 struct bpf_insn *insn = buf; 471 struct cfg cfg; 472 473 memset(&cfg, 0, sizeof(cfg)); 474 if (cfg_build(&cfg, insn, len)) 475 return; 476 477 cfg_dump(&cfg); 478 479 cfg_destroy(&cfg); 480 } 481