lib/librte_bpf/bpf_validate.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2018 Intel Corporation
   3  */
   4
   5 #include <stdarg.h>
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include <errno.h>
   9 #include <stdint.h>
  10 #include <inttypes.h>
  11
  12 #include <rte_common.h>
  13 #include <rte_eal.h>
  14
  15 #include "bpf_impl.h"
  16
  17 /* possible instruction node colour */
  18 enum {
  19         WHITE,
  20         GREY,
  21         BLACK,
  22         MAX_NODE_COLOUR
  23 };
  24
  25 /* possible edge types */
  26 enum {
  27         UNKNOWN_EDGE,
  28         TREE_EDGE,
  29         BACK_EDGE,
  30         CROSS_EDGE,
  31         MAX_EDGE_TYPE
  32 };
  33
  34 struct bpf_reg_state {
  35         uint64_t val;
  36 };
  37
  38 struct bpf_eval_state {
  39         struct bpf_reg_state rs[EBPF_REG_NUM];
  40 };
  41
  42 #define MAX_EDGES       2
  43
  44 struct inst_node {
  45         uint8_t colour;
  46         uint8_t nb_edge:4;
  47         uint8_t cur_edge:4;
  48         uint8_t edge_type[MAX_EDGES];
  49         uint32_t edge_dest[MAX_EDGES];
  50         uint32_t prev_node;
  51         struct bpf_eval_state *evst;
  52 };
  53
  54 struct bpf_verifier {
  55         const struct rte_bpf_prm *prm;
  56         struct inst_node *in;
  57         int32_t stack_sz;
  58         uint32_t nb_nodes;
  59         uint32_t nb_jcc_nodes;
  60         uint32_t node_colour[MAX_NODE_COLOUR];
  61         uint32_t edge_type[MAX_EDGE_TYPE];
  62         struct bpf_eval_state *evst;
  63         struct {
  64                 uint32_t num;
  65                 uint32_t cur;
  66                 struct bpf_eval_state *ent;
  67         } evst_pool;
  68 };
  69
  70 struct bpf_ins_check {
  71         struct {
  72                 uint16_t dreg;
  73                 uint16_t sreg;
  74         } mask;
  75         struct {
  76                 uint16_t min;
  77                 uint16_t max;
  78         } off;
  79         struct {
  80                 uint32_t min;
  81                 uint32_t max;
  82         } imm;
  83         const char * (*check)(const struct ebpf_insn *);
  84         const char * (*eval)(struct bpf_verifier *, const struct ebpf_insn *);
  85 };
  86
  87 #define ALL_REGS        RTE_LEN2MASK(EBPF_REG_NUM, uint16_t)
  88 #define WRT_REGS        RTE_LEN2MASK(EBPF_REG_10, uint16_t)
  89 #define ZERO_REG        RTE_LEN2MASK(EBPF_REG_1, uint16_t)
  90
  91 /*
  92  * check and evaluate functions for particular instruction types.
  93  */
  94
  95 static const char *
  96 check_alu_bele(const struct ebpf_insn *ins)
  97 {
  98         if (ins->imm != 16 && ins->imm != 32 && ins->imm != 64)
  99                 return "invalid imm field";
 100         return NULL;
 101 }
 102
 103 static const char *
 104 eval_stack(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 105 {
 106         int32_t ofs;
 107
 108         ofs = ins->off;
 109
 110         if (ofs >= 0 || ofs < -MAX_BPF_STACK_SIZE)
 111                 return "stack boundary violation";
 112
 113         ofs = -ofs;
 114         bvf->stack_sz = RTE_MAX(bvf->stack_sz, ofs);
 115         return NULL;
 116 }
 117
 118 static const char *
 119 eval_store(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 120 {
 121         if (ins->dst_reg == EBPF_REG_10)
 122                 return eval_stack(bvf, ins);
 123         return NULL;
 124 }
 125
 126 static const char *
 127 eval_load(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 128 {
 129         if (ins->src_reg == EBPF_REG_10)
 130                 return eval_stack(bvf, ins);
 131         return NULL;
 132 }
 133
 134 static const char *
 135 eval_call(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 136 {
 137         uint32_t idx;
 138
 139         idx = ins->imm;
 140
 141         if (idx >= bvf->prm->nb_xsym ||
 142                         bvf->prm->xsym[idx].type != RTE_BPF_XTYPE_FUNC)
 143                 return "invalid external function index";
 144
 145         /* for now don't support function calls on 32 bit platform */
 146         if (sizeof(uint64_t) != sizeof(uintptr_t))
 147                 return "function calls are supported only for 64 bit apps";
 148         return NULL;
 149 }
 150
 151 /*
 152  * validate parameters for each instruction type.
 153  */
 154 static const struct bpf_ins_check ins_chk[UINT8_MAX] = {
 155         /* ALU IMM 32-bit instructions */
 156         [(BPF_ALU | BPF_ADD | BPF_K)] = {
 157                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 158                 .off = { .min = 0, .max = 0},
 159                 .imm = { .min = 0, .max = UINT32_MAX,},
 160         },
 161         [(BPF_ALU | BPF_SUB | BPF_K)] = {
 162                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 163                 .off = { .min = 0, .max = 0},
 164                 .imm = { .min = 0, .max = UINT32_MAX,},
 165         },
 166         [(BPF_ALU | BPF_AND | BPF_K)] = {
 167                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 168                 .off = { .min = 0, .max = 0},
 169                 .imm = { .min = 0, .max = UINT32_MAX,},
 170         },
 171         [(BPF_ALU | BPF_OR | BPF_K)] = {
 172                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 173                 .off = { .min = 0, .max = 0},
 174                 .imm = { .min = 0, .max = UINT32_MAX,},
 175         },
 176         [(BPF_ALU | BPF_LSH | BPF_K)] = {
 177                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 178                 .off = { .min = 0, .max = 0},
 179                 .imm = { .min = 0, .max = UINT32_MAX,},
 180         },
 181         [(BPF_ALU | BPF_RSH | BPF_K)] = {
 182                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 183                 .off = { .min = 0, .max = 0},
 184                 .imm = { .min = 0, .max = UINT32_MAX,},
 185         },
 186         [(BPF_ALU | BPF_XOR | BPF_K)] = {
 187                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 188                 .off = { .min = 0, .max = 0},
 189                 .imm = { .min = 0, .max = UINT32_MAX,},
 190         },
 191         [(BPF_ALU | BPF_MUL | BPF_K)] = {
 192                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 193                 .off = { .min = 0, .max = 0},
 194                 .imm = { .min = 0, .max = UINT32_MAX,},
 195         },
 196         [(BPF_ALU | EBPF_MOV | BPF_K)] = {
 197                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 198                 .off = { .min = 0, .max = 0},
 199                 .imm = { .min = 0, .max = UINT32_MAX,},
 200         },
 201         [(BPF_ALU | BPF_DIV | BPF_K)] = {
 202                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 203                 .off = { .min = 0, .max = 0},
 204                 .imm = { .min = 1, .max = UINT32_MAX},
 205         },
 206         [(BPF_ALU | BPF_MOD | BPF_K)] = {
 207                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 208                 .off = { .min = 0, .max = 0},
 209                 .imm = { .min = 1, .max = UINT32_MAX},
 210         },
 211         /* ALU IMM 64-bit instructions */
 212         [(EBPF_ALU64 | BPF_ADD | BPF_K)] = {
 213                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 214                 .off = { .min = 0, .max = 0},
 215                 .imm = { .min = 0, .max = UINT32_MAX,},
 216         },
 217         [(EBPF_ALU64 | BPF_SUB | BPF_K)] = {
 218                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 219                 .off = { .min = 0, .max = 0},
 220                 .imm = { .min = 0, .max = UINT32_MAX,},
 221         },
 222         [(EBPF_ALU64 | BPF_AND | BPF_K)] = {
 223                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 224                 .off = { .min = 0, .max = 0},
 225                 .imm = { .min = 0, .max = UINT32_MAX,},
 226         },
 227         [(EBPF_ALU64 | BPF_OR | BPF_K)] = {
 228                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 229                 .off = { .min = 0, .max = 0},
 230                 .imm = { .min = 0, .max = UINT32_MAX,},
 231         },
 232         [(EBPF_ALU64 | BPF_LSH | BPF_K)] = {
 233                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 234                 .off = { .min = 0, .max = 0},
 235                 .imm = { .min = 0, .max = UINT32_MAX,},
 236         },
 237         [(EBPF_ALU64 | BPF_RSH | BPF_K)] = {
 238                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 239                 .off = { .min = 0, .max = 0},
 240                 .imm = { .min = 0, .max = UINT32_MAX,},
 241         },
 242         [(EBPF_ALU64 | EBPF_ARSH | BPF_K)] = {
 243                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 244                 .off = { .min = 0, .max = 0},
 245                 .imm = { .min = 0, .max = UINT32_MAX,},
 246         },
 247         [(EBPF_ALU64 | BPF_XOR | BPF_K)] = {
 248                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 249                 .off = { .min = 0, .max = 0},
 250                 .imm = { .min = 0, .max = UINT32_MAX,},
 251         },
 252         [(EBPF_ALU64 | BPF_MUL | BPF_K)] = {
 253                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 254                 .off = { .min = 0, .max = 0},
 255                 .imm = { .min = 0, .max = UINT32_MAX,},
 256         },
 257         [(EBPF_ALU64 | EBPF_MOV | BPF_K)] = {
 258                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
 259                 .off = { .min = 0, .max = 0},
 260                 .imm = { .min = 0, .max = UINT32_MAX,},
 261         },
 262         [(EBPF_ALU64 | BPF_DIV | BPF_K)] = {
 263                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 264                 .off = { .min = 0, .max = 0},
 265                 .imm = { .min = 1, .max = UINT32_MAX},
 266         },
 267         [(EBPF_ALU64 | BPF_MOD | BPF_K)] = {
 268                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 269                 .off = { .min = 0, .max = 0},
 270                 .imm = { .min = 1, .max = UINT32_MAX},
 271         },
 272         /* ALU REG 32-bit instructions */
 273         [(BPF_ALU | BPF_ADD | BPF_X)] = {
 274                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 275                 .off = { .min = 0, .max = 0},
 276                 .imm = { .min = 0, .max = 0},
 277         },
 278         [(BPF_ALU | BPF_SUB | BPF_X)] = {
 279                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 280                 .off = { .min = 0, .max = 0},
 281                 .imm = { .min = 0, .max = 0},
 282         },
 283         [(BPF_ALU | BPF_AND | BPF_X)] = {
 284                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 285                 .off = { .min = 0, .max = 0},
 286                 .imm = { .min = 0, .max = 0},
 287         },
 288         [(BPF_ALU | BPF_OR | BPF_X)] = {
 289                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 290                 .off = { .min = 0, .max = 0},
 291                 .imm = { .min = 0, .max = 0},
 292         },
 293         [(BPF_ALU | BPF_LSH | BPF_X)] = {
 294                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 295                 .off = { .min = 0, .max = 0},
 296                 .imm = { .min = 0, .max = 0},
 297         },
 298         [(BPF_ALU | BPF_RSH | BPF_X)] = {
 299                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 300                 .off = { .min = 0, .max = 0},
 301                 .imm = { .min = 0, .max = 0},
 302         },
 303         [(BPF_ALU | BPF_XOR | BPF_X)] = {
 304                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 305                 .off = { .min = 0, .max = 0},
 306                 .imm = { .min = 0, .max = 0},
 307         },
 308         [(BPF_ALU | BPF_MUL | BPF_X)] = {
 309                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 310                 .off = { .min = 0, .max = 0},
 311                 .imm = { .min = 0, .max = 0},
 312         },
 313         [(BPF_ALU | BPF_DIV | BPF_X)] = {
 314                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 315                 .off = { .min = 0, .max = 0},
 316                 .imm = { .min = 0, .max = 0},
 317         },
 318         [(BPF_ALU | BPF_MOD | BPF_X)] = {
 319                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 320                 .off = { .min = 0, .max = 0},
 321                 .imm = { .min = 0, .max = 0},
 322         },
 323         [(BPF_ALU | EBPF_MOV | BPF_X)] = {
 324                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 325                 .off = { .min = 0, .max = 0},
 326                 .imm = { .min = 0, .max = 0},
 327         },
 328         [(BPF_ALU | BPF_NEG)] = {
 329                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 330                 .off = { .min = 0, .max = 0},
 331                 .imm = { .min = 0, .max = 0},
 332         },
 333         [(BPF_ALU | EBPF_END | EBPF_TO_BE)] = {
 334                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 335                 .off = { .min = 0, .max = 0},
 336                 .imm = { .min = 16, .max = 64},
 337                 .check = check_alu_bele,
 338         },
 339         [(BPF_ALU | EBPF_END | EBPF_TO_LE)] = {
 340                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 341                 .off = { .min = 0, .max = 0},
 342                 .imm = { .min = 16, .max = 64},
 343                 .check = check_alu_bele,
 344         },
 345         /* ALU REG 64-bit instructions */
 346         [(EBPF_ALU64 | BPF_ADD | BPF_X)] = {
 347                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 348                 .off = { .min = 0, .max = 0},
 349                 .imm = { .min = 0, .max = 0},
 350         },
 351         [(EBPF_ALU64 | BPF_SUB | BPF_X)] = {
 352                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 353                 .off = { .min = 0, .max = 0},
 354                 .imm = { .min = 0, .max = 0},
 355         },
 356         [(EBPF_ALU64 | BPF_AND | BPF_X)] = {
 357                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 358                 .off = { .min = 0, .max = 0},
 359                 .imm = { .min = 0, .max = 0},
 360         },
 361         [(EBPF_ALU64 | BPF_OR | BPF_X)] = {
 362                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 363                 .off = { .min = 0, .max = 0},
 364                 .imm = { .min = 0, .max = 0},
 365         },
 366         [(EBPF_ALU64 | BPF_LSH | BPF_X)] = {
 367                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 368                 .off = { .min = 0, .max = 0},
 369                 .imm = { .min = 0, .max = 0},
 370         },
 371         [(EBPF_ALU64 | BPF_RSH | BPF_X)] = {
 372                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 373                 .off = { .min = 0, .max = 0},
 374                 .imm = { .min = 0, .max = 0},
 375         },
 376         [(EBPF_ALU64 | EBPF_ARSH | BPF_X)] = {
 377                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 378                 .off = { .min = 0, .max = 0},
 379                 .imm = { .min = 0, .max = 0},
 380         },
 381         [(EBPF_ALU64 | BPF_XOR | BPF_X)] = {
 382                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 383                 .off = { .min = 0, .max = 0},
 384                 .imm = { .min = 0, .max = 0},
 385         },
 386         [(EBPF_ALU64 | BPF_MUL | BPF_X)] = {
 387                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 388                 .off = { .min = 0, .max = 0},
 389                 .imm = { .min = 0, .max = 0},
 390         },
 391         [(EBPF_ALU64 | BPF_DIV | BPF_X)] = {
 392                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 393                 .off = { .min = 0, .max = 0},
 394                 .imm = { .min = 0, .max = 0},
 395         },
 396         [(EBPF_ALU64 | BPF_MOD | BPF_X)] = {
 397                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 398                 .off = { .min = 0, .max = 0},
 399                 .imm = { .min = 0, .max = 0},
 400         },
 401         [(EBPF_ALU64 | EBPF_MOV | BPF_X)] = {
 402                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
 403                 .off = { .min = 0, .max = 0},
 404                 .imm = { .min = 0, .max = 0},
 405         },
 406         [(EBPF_ALU64 | BPF_NEG)] = {
 407                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 408                 .off = { .min = 0, .max = 0},
 409                 .imm = { .min = 0, .max = 0},
 410         },
 411         /* load instructions */
 412         [(BPF_LDX | BPF_MEM | BPF_B)] = {
 413                 .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
 414                 .off = { .min = 0, .max = UINT16_MAX},
 415                 .imm = { .min = 0, .max = 0},
 416                 .eval = eval_load,
 417         },
 418         [(BPF_LDX | BPF_MEM | BPF_H)] = {
 419                 .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
 420                 .off = { .min = 0, .max = UINT16_MAX},
 421                 .imm = { .min = 0, .max = 0},
 422                 .eval = eval_load,
 423         },
 424         [(BPF_LDX | BPF_MEM | BPF_W)] = {
 425                 .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
 426                 .off = { .min = 0, .max = UINT16_MAX},
 427                 .imm = { .min = 0, .max = 0},
 428                 .eval = eval_load,
 429         },
 430         [(BPF_LDX | BPF_MEM | EBPF_DW)] = {
 431                 .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
 432                 .off = { .min = 0, .max = UINT16_MAX},
 433                 .imm = { .min = 0, .max = 0},
 434                 .eval = eval_load,
 435         },
 436         /* load 64 bit immediate value */
 437         [(BPF_LD | BPF_IMM | EBPF_DW)] = {
 438                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
 439                 .off = { .min = 0, .max = 0},
 440                 .imm = { .min = 0, .max = UINT32_MAX},
 441         },
 442         /* store REG instructions */
 443         [(BPF_STX | BPF_MEM | BPF_B)] = {
 444                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 445                 .off = { .min = 0, .max = UINT16_MAX},
 446                 .imm = { .min = 0, .max = 0},
 447                 .eval = eval_store,
 448         },
 449         [(BPF_STX | BPF_MEM | BPF_H)] = {
 450                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 451                 .off = { .min = 0, .max = UINT16_MAX},
 452                 .imm = { .min = 0, .max = 0},
 453                 .eval = eval_store,
 454         },
 455         [(BPF_STX | BPF_MEM | BPF_W)] = {
 456                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 457                 .off = { .min = 0, .max = UINT16_MAX},
 458                 .imm = { .min = 0, .max = 0},
 459                 .eval = eval_store,
 460         },
 461         [(BPF_STX | BPF_MEM | EBPF_DW)] = {
 462                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 463                 .off = { .min = 0, .max = UINT16_MAX},
 464                 .imm = { .min = 0, .max = 0},
 465                 .eval = eval_store,
 466         },
 467         /* atomic add instructions */
 468         [(BPF_STX | EBPF_XADD | BPF_W)] = {
 469                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 470                 .off = { .min = 0, .max = UINT16_MAX},
 471                 .imm = { .min = 0, .max = 0},
 472                 .eval = eval_store,
 473         },
 474         [(BPF_STX | EBPF_XADD | EBPF_DW)] = {
 475                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 476                 .off = { .min = 0, .max = UINT16_MAX},
 477                 .imm = { .min = 0, .max = 0},
 478                 .eval = eval_store,
 479         },
 480         /* store IMM instructions */
 481         [(BPF_ST | BPF_MEM | BPF_B)] = {
 482                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 483                 .off = { .min = 0, .max = UINT16_MAX},
 484                 .imm = { .min = 0, .max = UINT32_MAX},
 485                 .eval = eval_store,
 486         },
 487         [(BPF_ST | BPF_MEM | BPF_H)] = {
 488                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 489                 .off = { .min = 0, .max = UINT16_MAX},
 490                 .imm = { .min = 0, .max = UINT32_MAX},
 491                 .eval = eval_store,
 492         },
 493         [(BPF_ST | BPF_MEM | BPF_W)] = {
 494                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 495                 .off = { .min = 0, .max = UINT16_MAX},
 496                 .imm = { .min = 0, .max = UINT32_MAX},
 497                 .eval = eval_store,
 498         },
 499         [(BPF_ST | BPF_MEM | EBPF_DW)] = {
 500                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 501                 .off = { .min = 0, .max = UINT16_MAX},
 502                 .imm = { .min = 0, .max = UINT32_MAX},
 503                 .eval = eval_store,
 504         },
 505         /* jump instruction */
 506         [(BPF_JMP | BPF_JA)] = {
 507                 .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
 508                 .off = { .min = 0, .max = UINT16_MAX},
 509                 .imm = { .min = 0, .max = 0},
 510         },
 511         /* jcc IMM instructions */
 512         [(BPF_JMP | BPF_JEQ | BPF_K)] = {
 513                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 514                 .off = { .min = 0, .max = UINT16_MAX},
 515                 .imm = { .min = 0, .max = UINT32_MAX},
 516         },
 517         [(BPF_JMP | EBPF_JNE | BPF_K)] = {
 518                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 519                 .off = { .min = 0, .max = UINT16_MAX},
 520                 .imm = { .min = 0, .max = UINT32_MAX},
 521         },
 522         [(BPF_JMP | BPF_JGT | BPF_K)] = {
 523                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 524                 .off = { .min = 0, .max = UINT16_MAX},
 525                 .imm = { .min = 0, .max = UINT32_MAX},
 526         },
 527         [(BPF_JMP | EBPF_JLT | BPF_K)] = {
 528                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 529                 .off = { .min = 0, .max = UINT16_MAX},
 530                 .imm = { .min = 0, .max = UINT32_MAX},
 531         },
 532         [(BPF_JMP | BPF_JGE | BPF_K)] = {
 533                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 534                 .off = { .min = 0, .max = UINT16_MAX},
 535                 .imm = { .min = 0, .max = UINT32_MAX},
 536         },
 537         [(BPF_JMP | EBPF_JLE | BPF_K)] = {
 538                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 539                 .off = { .min = 0, .max = UINT16_MAX},
 540                 .imm = { .min = 0, .max = UINT32_MAX},
 541         },
 542         [(BPF_JMP | EBPF_JSGT | BPF_K)] = {
 543                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 544                 .off = { .min = 0, .max = UINT16_MAX},
 545                 .imm = { .min = 0, .max = UINT32_MAX},
 546         },
 547         [(BPF_JMP | EBPF_JSLT | BPF_K)] = {
 548                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 549                 .off = { .min = 0, .max = UINT16_MAX},
 550                 .imm = { .min = 0, .max = UINT32_MAX},
 551         },
 552         [(BPF_JMP | EBPF_JSGE | BPF_K)] = {
 553                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 554                 .off = { .min = 0, .max = UINT16_MAX},
 555                 .imm = { .min = 0, .max = UINT32_MAX},
 556         },
 557         [(BPF_JMP | EBPF_JSLE | BPF_K)] = {
 558                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 559                 .off = { .min = 0, .max = UINT16_MAX},
 560                 .imm = { .min = 0, .max = UINT32_MAX},
 561         },
 562         [(BPF_JMP | BPF_JSET | BPF_K)] = {
 563                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
 564                 .off = { .min = 0, .max = UINT16_MAX},
 565                 .imm = { .min = 0, .max = UINT32_MAX},
 566         },
 567         /* jcc REG instructions */
 568         [(BPF_JMP | BPF_JEQ | BPF_X)] = {
 569                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 570                 .off = { .min = 0, .max = UINT16_MAX},
 571                 .imm = { .min = 0, .max = 0},
 572         },
 573         [(BPF_JMP | EBPF_JNE | BPF_X)] = {
 574                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 575                 .off = { .min = 0, .max = UINT16_MAX},
 576                 .imm = { .min = 0, .max = 0},
 577         },
 578         [(BPF_JMP | BPF_JGT | BPF_X)] = {
 579                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 580                 .off = { .min = 0, .max = UINT16_MAX},
 581                 .imm = { .min = 0, .max = 0},
 582         },
 583         [(BPF_JMP | EBPF_JLT | BPF_X)] = {
 584                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 585                 .off = { .min = 0, .max = UINT16_MAX},
 586                 .imm = { .min = 0, .max = 0},
 587         },
 588         [(BPF_JMP | BPF_JGE | BPF_X)] = {
 589                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 590                 .off = { .min = 0, .max = UINT16_MAX},
 591                 .imm = { .min = 0, .max = 0},
 592         },
 593         [(BPF_JMP | EBPF_JLE | BPF_X)] = {
 594                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 595                 .off = { .min = 0, .max = UINT16_MAX},
 596                 .imm = { .min = 0, .max = 0},
 597         },
 598         [(BPF_JMP | EBPF_JSGT | BPF_X)] = {
 599                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 600                 .off = { .min = 0, .max = UINT16_MAX},
 601                 .imm = { .min = 0, .max = 0},
 602         },
 603         [(BPF_JMP | EBPF_JSLT | BPF_X)] = {
 604                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 605                 .off = { .min = 0, .max = UINT16_MAX},
 606                 .imm = { .min = 0, .max = 0},
 607         },
 608         [(BPF_JMP | EBPF_JSGE | BPF_X)] = {
 609                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 610                 .off = { .min = 0, .max = UINT16_MAX},
 611                 .imm = { .min = 0, .max = 0},
 612         },
 613         [(BPF_JMP | EBPF_JSLE | BPF_X)] = {
 614                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 615                 .off = { .min = 0, .max = UINT16_MAX},
 616                 .imm = { .min = 0, .max = 0},
 617         },
 618         [(BPF_JMP | BPF_JSET | BPF_X)] = {
 619                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
 620                 .off = { .min = 0, .max = UINT16_MAX},
 621                 .imm = { .min = 0, .max = 0},
 622         },
 623         /* call instruction */
 624         [(BPF_JMP | EBPF_CALL)] = {
 625                 .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
 626                 .off = { .min = 0, .max = 0},
 627                 .imm = { .min = 0, .max = UINT32_MAX},
 628                 .eval = eval_call,
 629         },
 630         /* ret instruction */
 631         [(BPF_JMP | EBPF_EXIT)] = {
 632                 .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
 633                 .off = { .min = 0, .max = 0},
 634                 .imm = { .min = 0, .max = 0},
 635         },
 636 };
 637
 638 /*
 639  * make sure that instruction syntax is valid,
 640  * and it fields don't violate partciular instrcution type restrictions.
 641  */
 642 static const char *
 643 check_syntax(const struct ebpf_insn *ins)
 644 {
 645
 646         uint8_t op;
 647         uint16_t off;
 648         uint32_t imm;
 649
 650         op = ins->code;
 651
 652         if (ins_chk[op].mask.dreg == 0)
 653                 return "invalid opcode";
 654
 655         if ((ins_chk[op].mask.dreg & 1 << ins->dst_reg) == 0)
 656                 return "invalid dst-reg field";
 657
 658         if ((ins_chk[op].mask.sreg & 1 << ins->src_reg) == 0)
 659                 return "invalid src-reg field";
 660
 661         off = ins->off;
 662         if (ins_chk[op].off.min > off || ins_chk[op].off.max < off)
 663                 return "invalid off field";
 664
 665         imm = ins->imm;
 666         if (ins_chk[op].imm.min > imm || ins_chk[op].imm.max < imm)
 667                 return "invalid imm field";
 668
 669         if (ins_chk[op].check != NULL)
 670                 return ins_chk[op].check(ins);
 671
 672         return NULL;
 673 }
 674
 675 /*
 676  * helper function, return instruction index for the given node.
 677  */
 678 static uint32_t
 679 get_node_idx(const struct bpf_verifier *bvf, const struct inst_node *node)
 680 {
 681         return node - bvf->in;
 682 }
 683
 684 /*
 685  * helper function, used to walk through constructed CFG.
 686  */
 687 static struct inst_node *
 688 get_next_node(struct bpf_verifier *bvf, struct inst_node *node)
 689 {
 690         uint32_t ce, ne, dst;
 691
 692         ne = node->nb_edge;
 693         ce = node->cur_edge;
 694         if (ce == ne)
 695                 return NULL;
 696
 697         node->cur_edge++;
 698         dst = node->edge_dest[ce];
 699         return bvf->in + dst;
 700 }
 701
 702 static void
 703 set_node_colour(struct bpf_verifier *bvf, struct inst_node *node,
 704         uint32_t new)
 705 {
 706         uint32_t prev;
 707
 708         prev = node->colour;
 709         node->colour = new;
 710
 711         bvf->node_colour[prev]--;
 712         bvf->node_colour[new]++;
 713 }
 714
 715 /*
 716  * helper function, add new edge between two nodes.
 717  */
 718 static int
 719 add_edge(struct bpf_verifier *bvf, struct inst_node *node, uint32_t nidx)
 720 {
 721         uint32_t ne;
 722
 723         if (nidx > bvf->prm->nb_ins) {
 724                 RTE_BPF_LOG(ERR, "%s: program boundary violation at pc: %u, "
 725                         "next pc: %u\n",
 726                         __func__, get_node_idx(bvf, node), nidx);
 727                 return -EINVAL;
 728         }
 729
 730         ne = node->nb_edge;
 731         if (ne >= RTE_DIM(node->edge_dest)) {
 732                 RTE_BPF_LOG(ERR, "%s: internal error at pc: %u\n",
 733                         __func__, get_node_idx(bvf, node));
 734                 return -EINVAL;
 735         }
 736
 737         node->edge_dest[ne] = nidx;
 738         node->nb_edge = ne + 1;
 739         return 0;
 740 }
 741
 742 /*
 743  * helper function, determine type of edge between two nodes.
 744  */
 745 static void
 746 set_edge_type(struct bpf_verifier *bvf, struct inst_node *node,
 747         const struct inst_node *next)
 748 {
 749         uint32_t ce, clr, type;
 750
 751         ce = node->cur_edge - 1;
 752         clr = next->colour;
 753
 754         type = UNKNOWN_EDGE;
 755
 756         if (clr == WHITE)
 757                 type = TREE_EDGE;
 758         else if (clr == GREY)
 759                 type = BACK_EDGE;
 760         else if (clr == BLACK)
 761                 /*
 762                  * in fact it could be either direct or cross edge,
 763                  * but for now, we don't need to distinguish between them.
 764                  */
 765                 type = CROSS_EDGE;
 766
 767         node->edge_type[ce] = type;
 768         bvf->edge_type[type]++;
 769 }
 770
 771 static struct inst_node *
 772 get_prev_node(struct bpf_verifier *bvf, struct inst_node *node)
 773 {
 774         return  bvf->in + node->prev_node;
 775 }
 776
 777 /*
 778  * Depth-First Search (DFS) through previously constructed
 779  * Control Flow Graph (CFG).
 780  * Information collected at this path would be used later
 781  * to determine is there any loops, and/or unreachable instructions.
 782  */
 783 static void
 784 dfs(struct bpf_verifier *bvf)
 785 {
 786         struct inst_node *next, *node;
 787
 788         node = bvf->in;
 789         while (node != NULL) {
 790
 791                 if (node->colour == WHITE)
 792                         set_node_colour(bvf, node, GREY);
 793
 794                 if (node->colour == GREY) {
 795
 796                         /* find next unprocessed child node */
 797                         do {
 798                                 next = get_next_node(bvf, node);
 799                                 if (next == NULL)
 800                                         break;
 801                                 set_edge_type(bvf, node, next);
 802                         } while (next->colour != WHITE);
 803
 804                         if (next != NULL) {
 805                                 /* proceed with next child */
 806                                 next->prev_node = get_node_idx(bvf, node);
 807                                 node = next;
 808                         } else {
 809                                 /*
 810                                  * finished with current node and all it's kids,
 811                                  * proceed with parent
 812                                  */
 813                                 set_node_colour(bvf, node, BLACK);
 814                                 node->cur_edge = 0;
 815                                 node = get_prev_node(bvf, node);
 816                         }
 817                 } else
 818                         node = NULL;
 819         }
 820 }
 821
 822 /*
 823  * report unreachable instructions.
 824  */
 825 static void
 826 log_unreachable(const struct bpf_verifier *bvf)
 827 {
 828         uint32_t i;
 829         struct inst_node *node;
 830         const struct ebpf_insn *ins;
 831
 832         for (i = 0; i != bvf->prm->nb_ins; i++) {
 833
 834                 node = bvf->in + i;
 835                 ins = bvf->prm->ins + i;
 836
 837                 if (node->colour == WHITE &&
 838                                 ins->code != (BPF_LD | BPF_IMM | EBPF_DW))
 839                         RTE_BPF_LOG(ERR, "unreachable code at pc: %u;\n", i);
 840         }
 841 }
 842
 843 /*
 844  * report loops detected.
 845  */
 846 static void
 847 log_loop(const struct bpf_verifier *bvf)
 848 {
 849         uint32_t i, j;
 850         struct inst_node *node;
 851
 852         for (i = 0; i != bvf->prm->nb_ins; i++) {
 853
 854                 node = bvf->in + i;
 855                 if (node->colour != BLACK)
 856                         continue;
 857
 858                 for (j = 0; j != node->nb_edge; j++) {
 859                         if (node->edge_type[j] == BACK_EDGE)
 860                                 RTE_BPF_LOG(ERR,
 861                                         "loop at pc:%u --> pc:%u;\n",
 862                                         i, node->edge_dest[j]);
 863                 }
 864         }
 865 }
 866
 867 /*
 868  * First pass goes though all instructions in the set, checks that each
 869  * instruction is a valid one (correct syntax, valid field values, etc.)
 870  * and constructs control flow graph (CFG).
 871  * Then deapth-first search is performed over the constructed graph.
 872  * Programs with unreachable instructions and/or loops will be rejected.
 873  */
 874 static int
 875 validate(struct bpf_verifier *bvf)
 876 {
 877         int32_t rc;
 878         uint32_t i;
 879         struct inst_node *node;
 880         const struct ebpf_insn *ins;
 881         const char *err;
 882
 883         rc = 0;
 884         for (i = 0; i < bvf->prm->nb_ins; i++) {
 885
 886                 ins = bvf->prm->ins + i;
 887                 node = bvf->in + i;
 888
 889                 err = check_syntax(ins);
 890                 if (err != 0) {
 891                         RTE_BPF_LOG(ERR, "%s: %s at pc: %u\n",
 892                                 __func__, err, i);
 893                         rc |= -EINVAL;
 894                 }
 895
 896                 /*
 897                  * construct CFG, jcc nodes have to outgoing edges,
 898                  * 'exit' nodes - none, all others nodes have exaclty one
 899                  * outgoing edge.
 900                  */
 901                 switch (ins->code) {
 902                 case (BPF_JMP | EBPF_EXIT):
 903                         break;
 904                 case (BPF_JMP | BPF_JEQ | BPF_K):
 905                 case (BPF_JMP | EBPF_JNE | BPF_K):
 906                 case (BPF_JMP | BPF_JGT | BPF_K):
 907                 case (BPF_JMP | EBPF_JLT | BPF_K):
 908                 case (BPF_JMP | BPF_JGE | BPF_K):
 909                 case (BPF_JMP | EBPF_JLE | BPF_K):
 910                 case (BPF_JMP | EBPF_JSGT | BPF_K):
 911                 case (BPF_JMP | EBPF_JSLT | BPF_K):
 912                 case (BPF_JMP | EBPF_JSGE | BPF_K):
 913                 case (BPF_JMP | EBPF_JSLE | BPF_K):
 914                 case (BPF_JMP | BPF_JSET | BPF_K):
 915                 case (BPF_JMP | BPF_JEQ | BPF_X):
 916                 case (BPF_JMP | EBPF_JNE | BPF_X):
 917                 case (BPF_JMP | BPF_JGT | BPF_X):
 918                 case (BPF_JMP | EBPF_JLT | BPF_X):
 919                 case (BPF_JMP | BPF_JGE | BPF_X):
 920                 case (BPF_JMP | EBPF_JLE | BPF_X):
 921                 case (BPF_JMP | EBPF_JSGT | BPF_X):
 922                 case (BPF_JMP | EBPF_JSLT | BPF_X):
 923                 case (BPF_JMP | EBPF_JSGE | BPF_X):
 924                 case (BPF_JMP | EBPF_JSLE | BPF_X):
 925                 case (BPF_JMP | BPF_JSET | BPF_X):
 926                         rc |= add_edge(bvf, node, i + ins->off + 1);
 927                         rc |= add_edge(bvf, node, i + 1);
 928                         bvf->nb_jcc_nodes++;
 929                         break;
 930                 case (BPF_JMP | BPF_JA):
 931                         rc |= add_edge(bvf, node, i + ins->off + 1);
 932                         break;
 933                 /* load 64 bit immediate value */
 934                 case (BPF_LD | BPF_IMM | EBPF_DW):
 935                         rc |= add_edge(bvf, node, i + 2);
 936                         i++;
 937                         break;
 938                 default:
 939                         rc |= add_edge(bvf, node, i + 1);
 940                         break;
 941                 }
 942
 943                 bvf->nb_nodes++;
 944                 bvf->node_colour[WHITE]++;
 945         }
 946
 947         if (rc != 0)
 948                 return rc;
 949
 950         dfs(bvf);
 951
 952         RTE_BPF_LOG(DEBUG, "%s(%p) stats:\n"
 953                 "nb_nodes=%u;\n"
 954                 "nb_jcc_nodes=%u;\n"
 955                 "node_color={[WHITE]=%u, [GREY]=%u,, [BLACK]=%u};\n"
 956                 "edge_type={[UNKNOWN]=%u, [TREE]=%u, [BACK]=%u, [CROSS]=%u};\n",
 957                 __func__, bvf,
 958                 bvf->nb_nodes,
 959                 bvf->nb_jcc_nodes,
 960                 bvf->node_colour[WHITE], bvf->node_colour[GREY],
 961                         bvf->node_colour[BLACK],
 962                 bvf->edge_type[UNKNOWN_EDGE], bvf->edge_type[TREE_EDGE],
 963                 bvf->edge_type[BACK_EDGE], bvf->edge_type[CROSS_EDGE]);
 964
 965         if (bvf->node_colour[BLACK] != bvf->nb_nodes) {
 966                 RTE_BPF_LOG(ERR, "%s(%p) unreachable instructions;\n",
 967                         __func__, bvf);
 968                 log_unreachable(bvf);
 969                 return -EINVAL;
 970         }
 971
 972         if (bvf->node_colour[GREY] != 0 || bvf->node_colour[WHITE] != 0 ||
 973                         bvf->edge_type[UNKNOWN_EDGE] != 0) {
 974                 RTE_BPF_LOG(ERR, "%s(%p) DFS internal error;\n",
 975                         __func__, bvf);
 976                 return -EINVAL;
 977         }
 978
 979         if (bvf->edge_type[BACK_EDGE] != 0) {
 980                 RTE_BPF_LOG(ERR, "%s(%p) loops detected;\n",
 981                         __func__, bvf);
 982                 log_loop(bvf);
 983                 return -EINVAL;
 984         }
 985
 986         return 0;
 987 }
 988
 989 /*
 990  * helper functions get/free eval states.
 991  */
 992 static struct bpf_eval_state *
 993 pull_eval_state(struct bpf_verifier *bvf)
 994 {
 995         uint32_t n;
 996
 997         n = bvf->evst_pool.cur;
 998         if (n == bvf->evst_pool.num)
 999                 return NULL;
1000
1001         bvf->evst_pool.cur = n + 1;
1002         return bvf->evst_pool.ent + n;
1003 }
1004
1005 static void
1006 push_eval_state(struct bpf_verifier *bvf)
1007 {
1008         bvf->evst_pool.cur--;
1009 }
1010
1011 static void
1012 evst_pool_fini(struct bpf_verifier *bvf)
1013 {
1014         bvf->evst = NULL;
1015         free(bvf->evst_pool.ent);
1016         memset(&bvf->evst_pool, 0, sizeof(bvf->evst_pool));
1017 }
1018
1019 static int
1020 evst_pool_init(struct bpf_verifier *bvf)
1021 {
1022         uint32_t n;
1023
1024         n = bvf->nb_jcc_nodes + 1;
1025
1026         bvf->evst_pool.ent = calloc(n, sizeof(bvf->evst_pool.ent[0]));
1027         if (bvf->evst_pool.ent == NULL)
1028                 return -ENOMEM;
1029
1030         bvf->evst_pool.num = n;
1031         bvf->evst_pool.cur = 0;
1032
1033         bvf->evst = pull_eval_state(bvf);
1034         return 0;
1035 }
1036
1037 /*
1038  * Save current eval state.
1039  */
1040 static int
1041 save_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
1042 {
1043         struct bpf_eval_state *st;
1044
1045         /* get new eval_state for this node */
1046         st = pull_eval_state(bvf);
1047         if (st == NULL) {
1048                 RTE_BPF_LOG(ERR,
1049                         "%s: internal error (out of space) at pc: %u",
1050                         __func__, get_node_idx(bvf, node));
1051                 return -ENOMEM;
1052         }
1053
1054         /* make a copy of current state */
1055         memcpy(st, bvf->evst, sizeof(*st));
1056
1057         /* swap current state with new one */
1058         node->evst = bvf->evst;
1059         bvf->evst = st;
1060
1061         RTE_BPF_LOG(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;\n",
1062                 __func__, bvf, get_node_idx(bvf, node), node->evst, bvf->evst);
1063
1064         return 0;
1065 }
1066
1067 /*
1068  * Restore previous eval state and mark current eval state as free.
1069  */
1070 static void
1071 restore_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
1072 {
1073         RTE_BPF_LOG(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;\n",
1074                 __func__, bvf, get_node_idx(bvf, node), bvf->evst, node->evst);
1075
1076         bvf->evst = node->evst;
1077         node->evst = NULL;
1078         push_eval_state(bvf);
1079 }
1080
1081 /*
1082  * Do second pass through CFG and try to evaluate instructions
1083  * via each possible path.
1084  * Right now evaluation functionality is quite limited.
1085  * Still need to add extra checks for:
1086  * - use/return uninitialized registers.
1087  * - use uninitialized data from the stack.
1088  * - memory boundaries violation.
1089  */
1090 static int
1091 evaluate(struct bpf_verifier *bvf)
1092 {
1093         int32_t rc;
1094         uint32_t idx, op;
1095         const char *err;
1096         const struct ebpf_insn *ins;
1097         struct inst_node *next, *node;
1098
1099         node = bvf->in;
1100         ins = bvf->prm->ins;
1101         rc = 0;
1102
1103         while (node != NULL && rc == 0) {
1104
1105                 /* current node evaluation */
1106                 idx = get_node_idx(bvf, node);
1107                 op = ins[idx].code;
1108
1109                 if (ins_chk[op].eval != NULL) {
1110                         err = ins_chk[op].eval(bvf, ins + idx);
1111                         if (err != NULL) {
1112                                 RTE_BPF_LOG(ERR, "%s: %s at pc: %u\n",
1113                                         __func__, err, idx);
1114                                 rc = -EINVAL;
1115                         }
1116                 }
1117
1118                 /* proceed through CFG */
1119                 next = get_next_node(bvf, node);
1120                 if (next != NULL) {
1121
1122                         /* proceed with next child */
1123                         if (node->cur_edge != node->nb_edge)
1124                                 rc |= save_eval_state(bvf, node);
1125                         else if (node->evst != NULL)
1126                                 restore_eval_state(bvf, node);
1127
1128                         next->prev_node = get_node_idx(bvf, node);
1129                         node = next;
1130                 } else {
1131                         /*
1132                          * finished with current node and all it's kids,
1133                          * proceed with parent
1134                          */
1135                         node->cur_edge = 0;
1136                         node = get_prev_node(bvf, node);
1137
1138                         /* finished */
1139                         if (node == bvf->in)
1140                                 node = NULL;
1141                 }
1142         }
1143
1144         return rc;
1145 }
1146
1147 int
1148 bpf_validate(struct rte_bpf *bpf)
1149 {
1150         int32_t rc;
1151         struct bpf_verifier bvf;
1152
1153         /* check input argument type, don't allow mbuf ptr on 32-bit */
1154         if (bpf->prm.prog_arg.type != RTE_BPF_ARG_RAW &&
1155                         bpf->prm.prog_arg.type != RTE_BPF_ARG_PTR &&
1156                         (sizeof(uint64_t) != sizeof(uintptr_t) ||
1157                         bpf->prm.prog_arg.type != RTE_BPF_ARG_PTR_MBUF)) {
1158                 RTE_BPF_LOG(ERR, "%s: unsupported argument type\n", __func__);
1159                 return -ENOTSUP;
1160         }
1161
1162         memset(&bvf, 0, sizeof(bvf));
1163         bvf.prm = &bpf->prm;
1164         bvf.in = calloc(bpf->prm.nb_ins, sizeof(bvf.in[0]));
1165         if (bvf.in == NULL)
1166                 return -ENOMEM;
1167
1168         rc = validate(&bvf);
1169
1170         if (rc == 0) {
1171                 rc = evst_pool_init(&bvf);
1172                 if (rc == 0)
1173                         rc = evaluate(&bvf);
1174                 evst_pool_fini(&bvf);
1175         }
1176
1177         free(bvf.in);
1178
1179         /* copy collected info */
1180         if (rc == 0)
1181                 bpf->stack_sz = bvf.stack_sz;
1182
1183         return rc;
1184 }