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