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