lib/bpf/bpf_validate.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2018 Intel Corporation
   3  */
   4
   5 #include <stdio.h>
   6 #include <string.h>
   7 #include <errno.h>
   8 #include <stdint.h>
   9 #include <inttypes.h>
  10
  11 #include <rte_common.h>
  12
  13 #include "bpf_impl.h"
  14
  15 #define BPF_ARG_PTR_STACK RTE_BPF_ARG_RESERVED
  16
  17 struct bpf_reg_val {
  18         struct rte_bpf_arg v;
  19         uint64_t mask;
  20         struct {
  21                 int64_t min;
  22                 int64_t max;
  23         } s;
  24         struct {
  25                 uint64_t min;
  26                 uint64_t max;
  27         } u;
  28 };
  29
  30 struct bpf_eval_state {
  31         struct bpf_reg_val rv[EBPF_REG_NUM];
  32         struct bpf_reg_val sv[MAX_BPF_STACK_SIZE / sizeof(uint64_t)];
  33 };
  34
  35 /* possible instruction node colour */
  36 enum {
  37         WHITE,
  38         GREY,
  39         BLACK,
  40         MAX_NODE_COLOUR
  41 };
  42
  43 /* possible edge types */
  44 enum {
  45         UNKNOWN_EDGE,
  46         TREE_EDGE,
  47         BACK_EDGE,
  48         CROSS_EDGE,
  49         MAX_EDGE_TYPE
  50 };
  51
  52 #define MAX_EDGES       2
  53
  54 struct inst_node {
  55         uint8_t colour;
  56         uint8_t nb_edge:4;
  57         uint8_t cur_edge:4;
  58         uint8_t edge_type[MAX_EDGES];
  59         uint32_t edge_dest[MAX_EDGES];
  60         uint32_t prev_node;
  61         struct bpf_eval_state *evst;
  62 };
  63
  64 struct bpf_verifier {
  65         const struct rte_bpf_prm *prm;
  66         struct inst_node *in;
  67         uint64_t stack_sz;
  68         uint32_t nb_nodes;
  69         uint32_t nb_jcc_nodes;
  70         uint32_t nb_ldmb_nodes;
  71         uint32_t node_colour[MAX_NODE_COLOUR];
  72         uint32_t edge_type[MAX_EDGE_TYPE];
  73         struct bpf_eval_state *evst;
  74         struct inst_node *evin;
  75         struct {
  76                 uint32_t num;
  77                 uint32_t cur;
  78                 struct bpf_eval_state *ent;
  79         } evst_pool;
  80 };
  81
  82 struct bpf_ins_check {
  83         struct {
  84                 uint16_t dreg;
  85                 uint16_t sreg;
  86         } mask;
  87         struct {
  88                 uint16_t min;
  89                 uint16_t max;
  90         } off;
  91         struct {
  92                 uint32_t min;
  93                 uint32_t max;
  94         } imm;
  95         const char * (*check)(const struct ebpf_insn *);
  96         const char * (*eval)(struct bpf_verifier *, const struct ebpf_insn *);
  97 };
  98
  99 #define ALL_REGS        RTE_LEN2MASK(EBPF_REG_NUM, uint16_t)
 100 #define WRT_REGS        RTE_LEN2MASK(EBPF_REG_10, uint16_t)
 101 #define ZERO_REG        RTE_LEN2MASK(EBPF_REG_1, uint16_t)
 102
 103 /* For LD_IND R6 is an implicit CTX register. */
 104 #define IND_SRC_REGS    (WRT_REGS ^ 1 << EBPF_REG_6)
 105
 106 /*
 107  * check and evaluate functions for particular instruction types.
 108  */
 109
 110 static const char *
 111 check_alu_bele(const struct ebpf_insn *ins)
 112 {
 113         if (ins->imm != 16 && ins->imm != 32 && ins->imm != 64)
 114                 return "invalid imm field";
 115         return NULL;
 116 }
 117
 118 static const char *
 119 eval_exit(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 120 {
 121         RTE_SET_USED(ins);
 122         if (bvf->evst->rv[EBPF_REG_0].v.type == RTE_BPF_ARG_UNDEF)
 123                 return "undefined return value";
 124         return NULL;
 125 }
 126
 127 /* setup max possible with this mask bounds */
 128 static void
 129 eval_umax_bound(struct bpf_reg_val *rv, uint64_t mask)
 130 {
 131         rv->u.max = mask;
 132         rv->u.min = 0;
 133 }
 134
 135 static void
 136 eval_smax_bound(struct bpf_reg_val *rv, uint64_t mask)
 137 {
 138         rv->s.max = mask >> 1;
 139         rv->s.min = rv->s.max ^ UINT64_MAX;
 140 }
 141
 142 static void
 143 eval_max_bound(struct bpf_reg_val *rv, uint64_t mask)
 144 {
 145         eval_umax_bound(rv, mask);
 146         eval_smax_bound(rv, mask);
 147 }
 148
 149 static void
 150 eval_fill_max_bound(struct bpf_reg_val *rv, uint64_t mask)
 151 {
 152         eval_max_bound(rv, mask);
 153         rv->v.type = RTE_BPF_ARG_RAW;
 154         rv->mask = mask;
 155 }
 156
 157 static void
 158 eval_fill_imm64(struct bpf_reg_val *rv, uint64_t mask, uint64_t val)
 159 {
 160         rv->mask = mask;
 161         rv->s.min = val;
 162         rv->s.max = val;
 163         rv->u.min = val;
 164         rv->u.max = val;
 165 }
 166
 167 static void
 168 eval_fill_imm(struct bpf_reg_val *rv, uint64_t mask, int32_t imm)
 169 {
 170         uint64_t v;
 171
 172         v = (uint64_t)imm & mask;
 173
 174         rv->v.type = RTE_BPF_ARG_RAW;
 175         eval_fill_imm64(rv, mask, v);
 176 }
 177
 178 static const char *
 179 eval_ld_imm64(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 180 {
 181         uint32_t i;
 182         uint64_t val;
 183         struct bpf_reg_val *rd;
 184
 185         val = (uint32_t)ins[0].imm | (uint64_t)(uint32_t)ins[1].imm << 32;
 186
 187         rd = bvf->evst->rv + ins->dst_reg;
 188         rd->v.type = RTE_BPF_ARG_RAW;
 189         eval_fill_imm64(rd, UINT64_MAX, val);
 190
 191         for (i = 0; i != bvf->prm->nb_xsym; i++) {
 192
 193                 /* load of external variable */
 194                 if (bvf->prm->xsym[i].type == RTE_BPF_XTYPE_VAR &&
 195                                 (uintptr_t)bvf->prm->xsym[i].var.val == val) {
 196                         rd->v = bvf->prm->xsym[i].var.desc;
 197                         eval_fill_imm64(rd, UINT64_MAX, 0);
 198                         break;
 199                 }
 200         }
 201
 202         return NULL;
 203 }
 204
 205 static void
 206 eval_apply_mask(struct bpf_reg_val *rv, uint64_t mask)
 207 {
 208         struct bpf_reg_val rt;
 209
 210         rt.u.min = rv->u.min & mask;
 211         rt.u.max = rv->u.max & mask;
 212         if (rt.u.min != rv->u.min || rt.u.max != rv->u.max) {
 213                 rv->u.max = RTE_MAX(rt.u.max, mask);
 214                 rv->u.min = 0;
 215         }
 216
 217         eval_smax_bound(&rt, mask);
 218         rv->s.max = RTE_MIN(rt.s.max, rv->s.max);
 219         rv->s.min = RTE_MAX(rt.s.min, rv->s.min);
 220
 221         rv->mask = mask;
 222 }
 223
 224 static void
 225 eval_add(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
 226 {
 227         struct bpf_reg_val rv;
 228
 229         rv.u.min = (rd->u.min + rs->u.min) & msk;
 230         rv.u.max = (rd->u.max + rs->u.max) & msk;
 231         rv.s.min = (rd->s.min + rs->s.min) & msk;
 232         rv.s.max = (rd->s.max + rs->s.max) & msk;
 233
 234         /*
 235          * if at least one of the operands is not constant,
 236          * then check for overflow
 237          */
 238         if ((rd->u.min != rd->u.max || rs->u.min != rs->u.max) &&
 239                         (rv.u.min < rd->u.min || rv.u.max < rd->u.max))
 240                 eval_umax_bound(&rv, msk);
 241
 242         if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
 243                         (((rs->s.min < 0 && rv.s.min > rd->s.min) ||
 244                         rv.s.min < rd->s.min) ||
 245                         ((rs->s.max < 0 && rv.s.max > rd->s.max) ||
 246                                 rv.s.max < rd->s.max)))
 247                 eval_smax_bound(&rv, msk);
 248
 249         rd->s = rv.s;
 250         rd->u = rv.u;
 251 }
 252
 253 static void
 254 eval_sub(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
 255 {
 256         struct bpf_reg_val rv;
 257
 258         rv.u.min = (rd->u.min - rs->u.max) & msk;
 259         rv.u.max = (rd->u.max - rs->u.min) & msk;
 260         rv.s.min = (rd->s.min - rs->s.max) & msk;
 261         rv.s.max = (rd->s.max - rs->s.min) & msk;
 262
 263         /*
 264          * if at least one of the operands is not constant,
 265          * then check for overflow
 266          */
 267         if ((rd->u.min != rd->u.max || rs->u.min != rs->u.max) &&
 268                         (rv.u.min > rd->u.min || rv.u.max > rd->u.max))
 269                 eval_umax_bound(&rv, msk);
 270
 271         if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
 272                         (((rs->s.min < 0 && rv.s.min < rd->s.min) ||
 273                         rv.s.min > rd->s.min) ||
 274                         ((rs->s.max < 0 && rv.s.max < rd->s.max) ||
 275                         rv.s.max > rd->s.max)))
 276                 eval_smax_bound(&rv, msk);
 277
 278         rd->s = rv.s;
 279         rd->u = rv.u;
 280 }
 281
 282 static void
 283 eval_lsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 284         uint64_t msk)
 285 {
 286         /* check if shift value is less then max result bits */
 287         if (rs->u.max >= opsz) {
 288                 eval_max_bound(rd, msk);
 289                 return;
 290         }
 291
 292         /* check for overflow */
 293         if (rd->u.max > RTE_LEN2MASK(opsz - rs->u.max, uint64_t))
 294                 eval_umax_bound(rd, msk);
 295         else {
 296                 rd->u.max <<= rs->u.max;
 297                 rd->u.min <<= rs->u.min;
 298         }
 299
 300         /* check that dreg values are and would remain always positive */
 301         if ((uint64_t)rd->s.min >> (opsz - 1) != 0 || rd->s.max >=
 302                         RTE_LEN2MASK(opsz - rs->u.max - 1, int64_t))
 303                 eval_smax_bound(rd, msk);
 304         else {
 305                 rd->s.max <<= rs->u.max;
 306                 rd->s.min <<= rs->u.min;
 307         }
 308 }
 309
 310 static void
 311 eval_rsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 312         uint64_t msk)
 313 {
 314         /* check if shift value is less then max result bits */
 315         if (rs->u.max >= opsz) {
 316                 eval_max_bound(rd, msk);
 317                 return;
 318         }
 319
 320         rd->u.max >>= rs->u.min;
 321         rd->u.min >>= rs->u.max;
 322
 323         /* check that dreg values are always positive */
 324         if ((uint64_t)rd->s.min >> (opsz - 1) != 0)
 325                 eval_smax_bound(rd, msk);
 326         else {
 327                 rd->s.max >>= rs->u.min;
 328                 rd->s.min >>= rs->u.max;
 329         }
 330 }
 331
 332 static void
 333 eval_arsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 334         uint64_t msk)
 335 {
 336         uint32_t shv;
 337
 338         /* check if shift value is less then max result bits */
 339         if (rs->u.max >= opsz) {
 340                 eval_max_bound(rd, msk);
 341                 return;
 342         }
 343
 344         rd->u.max = (int64_t)rd->u.max >> rs->u.min;
 345         rd->u.min = (int64_t)rd->u.min >> rs->u.max;
 346
 347         /* if we have 32-bit values - extend them to 64-bit */
 348         if (opsz == sizeof(uint32_t) * CHAR_BIT) {
 349                 rd->s.min <<= opsz;
 350                 rd->s.max <<= opsz;
 351                 shv = opsz;
 352         } else
 353                 shv = 0;
 354
 355         if (rd->s.min < 0)
 356                 rd->s.min = (rd->s.min >> (rs->u.min + shv)) & msk;
 357         else
 358                 rd->s.min = (rd->s.min >> (rs->u.max + shv)) & msk;
 359
 360         if (rd->s.max < 0)
 361                 rd->s.max = (rd->s.max >> (rs->u.max + shv)) & msk;
 362         else
 363                 rd->s.max = (rd->s.max >> (rs->u.min + shv)) & msk;
 364 }
 365
 366 static uint64_t
 367 eval_umax_bits(uint64_t v, size_t opsz)
 368 {
 369         if (v == 0)
 370                 return 0;
 371
 372         v = __builtin_clzll(v);
 373         return RTE_LEN2MASK(opsz - v, uint64_t);
 374 }
 375
 376 /* estimate max possible value for (v1 & v2) */
 377 static uint64_t
 378 eval_uand_max(uint64_t v1, uint64_t v2, size_t opsz)
 379 {
 380         v1 = eval_umax_bits(v1, opsz);
 381         v2 = eval_umax_bits(v2, opsz);
 382         return (v1 & v2);
 383 }
 384
 385 /* estimate max possible value for (v1 | v2) */
 386 static uint64_t
 387 eval_uor_max(uint64_t v1, uint64_t v2, size_t opsz)
 388 {
 389         v1 = eval_umax_bits(v1, opsz);
 390         v2 = eval_umax_bits(v2, opsz);
 391         return (v1 | v2);
 392 }
 393
 394 static void
 395 eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 396         uint64_t msk)
 397 {
 398         /* both operands are constants */
 399         if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
 400                 rd->u.min &= rs->u.min;
 401                 rd->u.max &= rs->u.max;
 402         } else {
 403                 rd->u.max = eval_uand_max(rd->u.max, rs->u.max, opsz);
 404                 rd->u.min &= rs->u.min;
 405         }
 406
 407         /* both operands are constants */
 408         if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
 409                 rd->s.min &= rs->s.min;
 410                 rd->s.max &= rs->s.max;
 411         /* at least one of operand is non-negative */
 412         } else if (rd->s.min >= 0 || rs->s.min >= 0) {
 413                 rd->s.max = eval_uand_max(rd->s.max & (msk >> 1),
 414                         rs->s.max & (msk >> 1), opsz);
 415                 rd->s.min &= rs->s.min;
 416         } else
 417                 eval_smax_bound(rd, msk);
 418 }
 419
 420 static void
 421 eval_or(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 422         uint64_t msk)
 423 {
 424         /* both operands are constants */
 425         if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
 426                 rd->u.min |= rs->u.min;
 427                 rd->u.max |= rs->u.max;
 428         } else {
 429                 rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
 430                 rd->u.min |= rs->u.min;
 431         }
 432
 433         /* both operands are constants */
 434         if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
 435                 rd->s.min |= rs->s.min;
 436                 rd->s.max |= rs->s.max;
 437
 438         /* both operands are non-negative */
 439         } else if (rd->s.min >= 0 || rs->s.min >= 0) {
 440                 rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
 441                 rd->s.min |= rs->s.min;
 442         } else
 443                 eval_smax_bound(rd, msk);
 444 }
 445
 446 static void
 447 eval_xor(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 448         uint64_t msk)
 449 {
 450         /* both operands are constants */
 451         if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
 452                 rd->u.min ^= rs->u.min;
 453                 rd->u.max ^= rs->u.max;
 454         } else {
 455                 rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
 456                 rd->u.min = 0;
 457         }
 458
 459         /* both operands are constants */
 460         if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
 461                 rd->s.min ^= rs->s.min;
 462                 rd->s.max ^= rs->s.max;
 463
 464         /* both operands are non-negative */
 465         } else if (rd->s.min >= 0 || rs->s.min >= 0) {
 466                 rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
 467                 rd->s.min = 0;
 468         } else
 469                 eval_smax_bound(rd, msk);
 470 }
 471
 472 static void
 473 eval_mul(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 474         uint64_t msk)
 475 {
 476         /* both operands are constants */
 477         if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
 478                 rd->u.min = (rd->u.min * rs->u.min) & msk;
 479                 rd->u.max = (rd->u.max * rs->u.max) & msk;
 480         /* check for overflow */
 481         } else if (rd->u.max <= msk >> opsz / 2 && rs->u.max <= msk >> opsz) {
 482                 rd->u.max *= rs->u.max;
 483                 rd->u.min *= rd->u.min;
 484         } else
 485                 eval_umax_bound(rd, msk);
 486
 487         /* both operands are constants */
 488         if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
 489                 rd->s.min = (rd->s.min * rs->s.min) & msk;
 490                 rd->s.max = (rd->s.max * rs->s.max) & msk;
 491         /* check that both operands are positive and no overflow */
 492         } else if (rd->s.min >= 0 && rs->s.min >= 0) {
 493                 rd->s.max *= rs->s.max;
 494                 rd->s.min *= rd->s.min;
 495         } else
 496                 eval_smax_bound(rd, msk);
 497 }
 498
 499 static const char *
 500 eval_divmod(uint32_t op, struct bpf_reg_val *rd, struct bpf_reg_val *rs,
 501         size_t opsz, uint64_t msk)
 502 {
 503         /* both operands are constants */
 504         if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
 505                 if (rs->u.max == 0)
 506                         return "division by 0";
 507                 if (op == BPF_DIV) {
 508                         rd->u.min /= rs->u.min;
 509                         rd->u.max /= rs->u.max;
 510                 } else {
 511                         rd->u.min %= rs->u.min;
 512                         rd->u.max %= rs->u.max;
 513                 }
 514         } else {
 515                 if (op == BPF_MOD)
 516                         rd->u.max = RTE_MIN(rd->u.max, rs->u.max - 1);
 517                 else
 518                         rd->u.max = rd->u.max;
 519                 rd->u.min = 0;
 520         }
 521
 522         /* if we have 32-bit values - extend them to 64-bit */
 523         if (opsz == sizeof(uint32_t) * CHAR_BIT) {
 524                 rd->s.min = (int32_t)rd->s.min;
 525                 rd->s.max = (int32_t)rd->s.max;
 526                 rs->s.min = (int32_t)rs->s.min;
 527                 rs->s.max = (int32_t)rs->s.max;
 528         }
 529
 530         /* both operands are constants */
 531         if (rd->s.min == rd->s.max && rs->s.min == rs->s.max) {
 532                 if (rs->s.max == 0)
 533                         return "division by 0";
 534                 if (op == BPF_DIV) {
 535                         rd->s.min /= rs->s.min;
 536                         rd->s.max /= rs->s.max;
 537                 } else {
 538                         rd->s.min %= rs->s.min;
 539                         rd->s.max %= rs->s.max;
 540                 }
 541         } else if (op == BPF_MOD) {
 542                 rd->s.min = RTE_MAX(rd->s.max, 0);
 543                 rd->s.min = RTE_MIN(rd->s.min, 0);
 544         } else
 545                 eval_smax_bound(rd, msk);
 546
 547         rd->s.max &= msk;
 548         rd->s.min &= msk;
 549
 550         return NULL;
 551 }
 552
 553 static void
 554 eval_neg(struct bpf_reg_val *rd, size_t opsz, uint64_t msk)
 555 {
 556         uint64_t ux, uy;
 557         int64_t sx, sy;
 558
 559         /* if we have 32-bit values - extend them to 64-bit */
 560         if (opsz == sizeof(uint32_t) * CHAR_BIT) {
 561                 rd->u.min = (int32_t)rd->u.min;
 562                 rd->u.max = (int32_t)rd->u.max;
 563         }
 564
 565         ux = -(int64_t)rd->u.min & msk;
 566         uy = -(int64_t)rd->u.max & msk;
 567
 568         rd->u.max = RTE_MAX(ux, uy);
 569         rd->u.min = RTE_MIN(ux, uy);
 570
 571         /* if we have 32-bit values - extend them to 64-bit */
 572         if (opsz == sizeof(uint32_t) * CHAR_BIT) {
 573                 rd->s.min = (int32_t)rd->s.min;
 574                 rd->s.max = (int32_t)rd->s.max;
 575         }
 576
 577         sx = -rd->s.min & msk;
 578         sy = -rd->s.max & msk;
 579
 580         rd->s.max = RTE_MAX(sx, sy);
 581         rd->s.min = RTE_MIN(sx, sy);
 582 }
 583
 584 static const char *
 585 eval_ld_mbuf(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 586 {
 587         uint32_t i, mode;
 588         struct bpf_reg_val *rv, ri, rs;
 589
 590         mode = BPF_MODE(ins->code);
 591
 592         /* R6 is an implicit input that must contain pointer to mbuf */
 593         if (bvf->evst->rv[EBPF_REG_6].v.type != RTE_BPF_ARG_PTR_MBUF)
 594                 return "invalid type for implicit ctx register";
 595
 596         if (mode == BPF_IND) {
 597                 rs = bvf->evst->rv[ins->src_reg];
 598                 if (rs.v.type != RTE_BPF_ARG_RAW)
 599                         return "unexpected type for src register";
 600
 601                 eval_fill_imm(&ri, UINT64_MAX, ins->imm);
 602                 eval_add(&rs, &ri, UINT64_MAX);
 603
 604                 if (rs.s.max < 0 || rs.u.min > UINT32_MAX)
 605                         return "mbuf boundary violation";
 606         }
 607
 608         /* R1-R5 scratch registers */
 609         for (i = EBPF_REG_1; i != EBPF_REG_6; i++)
 610                 bvf->evst->rv[i].v.type = RTE_BPF_ARG_UNDEF;
 611
 612         /* R0 is an implicit output, contains data fetched from the packet */
 613         rv = bvf->evst->rv + EBPF_REG_0;
 614         rv->v.size = bpf_size(BPF_SIZE(ins->code));
 615         eval_fill_max_bound(rv, RTE_LEN2MASK(rv->v.size * CHAR_BIT, uint64_t));
 616
 617         return NULL;
 618 }
 619
 620 /*
 621  * check that destination and source operand are in defined state.
 622  */
 623 static const char *
 624 eval_defined(const struct bpf_reg_val *dst, const struct bpf_reg_val *src)
 625 {
 626         if (dst != NULL && dst->v.type == RTE_BPF_ARG_UNDEF)
 627                 return "dest reg value is undefined";
 628         if (src != NULL && src->v.type == RTE_BPF_ARG_UNDEF)
 629                 return "src reg value is undefined";
 630         return NULL;
 631 }
 632
 633 static const char *
 634 eval_alu(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 635 {
 636         uint64_t msk;
 637         uint32_t op;
 638         size_t opsz;
 639         const char *err;
 640         struct bpf_eval_state *st;
 641         struct bpf_reg_val *rd, rs;
 642
 643         opsz = (BPF_CLASS(ins->code) == BPF_ALU) ?
 644                 sizeof(uint32_t) : sizeof(uint64_t);
 645         opsz = opsz * CHAR_BIT;
 646         msk = RTE_LEN2MASK(opsz, uint64_t);
 647
 648         st = bvf->evst;
 649         rd = st->rv + ins->dst_reg;
 650
 651         if (BPF_SRC(ins->code) == BPF_X) {
 652                 rs = st->rv[ins->src_reg];
 653                 eval_apply_mask(&rs, msk);
 654         } else
 655                 eval_fill_imm(&rs, msk, ins->imm);
 656
 657         eval_apply_mask(rd, msk);
 658
 659         op = BPF_OP(ins->code);
 660
 661         /* Allow self-xor as way to zero register */
 662         if (op == BPF_XOR && BPF_SRC(ins->code) == BPF_X &&
 663             ins->src_reg == ins->dst_reg) {
 664                 eval_fill_imm(&rs, UINT64_MAX, 0);
 665                 eval_fill_imm(rd, UINT64_MAX, 0);
 666         }
 667
 668         err = eval_defined((op != EBPF_MOV) ? rd : NULL,
 669                            (op != BPF_NEG) ? &rs : NULL);
 670         if (err != NULL)
 671                 return err;
 672
 673         if (op == BPF_ADD)
 674                 eval_add(rd, &rs, msk);
 675         else if (op == BPF_SUB)
 676                 eval_sub(rd, &rs, msk);
 677         else if (op == BPF_LSH)
 678                 eval_lsh(rd, &rs, opsz, msk);
 679         else if (op == BPF_RSH)
 680                 eval_rsh(rd, &rs, opsz, msk);
 681         else if (op == EBPF_ARSH)
 682                 eval_arsh(rd, &rs, opsz, msk);
 683         else if (op == BPF_AND)
 684                 eval_and(rd, &rs, opsz, msk);
 685         else if (op == BPF_OR)
 686                 eval_or(rd, &rs, opsz, msk);
 687         else if (op == BPF_XOR)
 688                 eval_xor(rd, &rs, opsz, msk);
 689         else if (op == BPF_MUL)
 690                 eval_mul(rd, &rs, opsz, msk);
 691         else if (op == BPF_DIV || op == BPF_MOD)
 692                 err = eval_divmod(op, rd, &rs, opsz, msk);
 693         else if (op == BPF_NEG)
 694                 eval_neg(rd, opsz, msk);
 695         else if (op == EBPF_MOV)
 696                 *rd = rs;
 697         else
 698                 eval_max_bound(rd, msk);
 699
 700         return err;
 701 }
 702
 703 static const char *
 704 eval_bele(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 705 {
 706         uint64_t msk;
 707         struct bpf_eval_state *st;
 708         struct bpf_reg_val *rd;
 709         const char *err;
 710
 711         msk = RTE_LEN2MASK(ins->imm, uint64_t);
 712
 713         st = bvf->evst;
 714         rd = st->rv + ins->dst_reg;
 715
 716         err = eval_defined(rd, NULL);
 717         if (err != NULL)
 718                 return err;
 719
 720 #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
 721         if (ins->code == (BPF_ALU | EBPF_END | EBPF_TO_BE))
 722                 eval_max_bound(rd, msk);
 723         else
 724                 eval_apply_mask(rd, msk);
 725 #else
 726         if (ins->code == (BPF_ALU | EBPF_END | EBPF_TO_LE))
 727                 eval_max_bound(rd, msk);
 728         else
 729                 eval_apply_mask(rd, msk);
 730 #endif
 731
 732         return NULL;
 733 }
 734
 735 static const char *
 736 eval_ptr(struct bpf_verifier *bvf, struct bpf_reg_val *rm, uint32_t opsz,
 737         uint32_t align, int16_t off)
 738 {
 739         struct bpf_reg_val rv;
 740
 741         /* calculate reg + offset */
 742         eval_fill_imm(&rv, rm->mask, off);
 743         eval_add(rm, &rv, rm->mask);
 744
 745         if (RTE_BPF_ARG_PTR_TYPE(rm->v.type) == 0)
 746                 return "destination is not a pointer";
 747
 748         if (rm->mask != UINT64_MAX)
 749                 return "pointer truncation";
 750
 751         if (rm->u.max + opsz > rm->v.size ||
 752                         (uint64_t)rm->s.max + opsz > rm->v.size ||
 753                         rm->s.min < 0)
 754                 return "memory boundary violation";
 755
 756         if (rm->u.max % align !=  0)
 757                 return "unaligned memory access";
 758
 759         if (rm->v.type == BPF_ARG_PTR_STACK) {
 760
 761                 if (rm->u.max != rm->u.min || rm->s.max != rm->s.min ||
 762                                 rm->u.max != (uint64_t)rm->s.max)
 763                         return "stack access with variable offset";
 764
 765                 bvf->stack_sz = RTE_MAX(bvf->stack_sz, rm->v.size - rm->u.max);
 766
 767         /* pointer to mbuf */
 768         } else if (rm->v.type == RTE_BPF_ARG_PTR_MBUF) {
 769
 770                 if (rm->u.max != rm->u.min || rm->s.max != rm->s.min ||
 771                                 rm->u.max != (uint64_t)rm->s.max)
 772                         return "mbuf access with variable offset";
 773         }
 774
 775         return NULL;
 776 }
 777
 778 static void
 779 eval_max_load(struct bpf_reg_val *rv, uint64_t mask)
 780 {
 781         eval_umax_bound(rv, mask);
 782
 783         /* full 64-bit load */
 784         if (mask == UINT64_MAX)
 785                 eval_smax_bound(rv, mask);
 786
 787         /* zero-extend load */
 788         rv->s.min = rv->u.min;
 789         rv->s.max = rv->u.max;
 790 }
 791
 792
 793 static const char *
 794 eval_load(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 795 {
 796         uint32_t opsz;
 797         uint64_t msk;
 798         const char *err;
 799         struct bpf_eval_state *st;
 800         struct bpf_reg_val *rd, rs;
 801         const struct bpf_reg_val *sv;
 802
 803         st = bvf->evst;
 804         rd = st->rv + ins->dst_reg;
 805         rs = st->rv[ins->src_reg];
 806         opsz = bpf_size(BPF_SIZE(ins->code));
 807         msk = RTE_LEN2MASK(opsz * CHAR_BIT, uint64_t);
 808
 809         err = eval_ptr(bvf, &rs, opsz, 1, ins->off);
 810         if (err != NULL)
 811                 return err;
 812
 813         if (rs.v.type == BPF_ARG_PTR_STACK) {
 814
 815                 sv = st->sv + rs.u.max / sizeof(uint64_t);
 816                 if (sv->v.type == RTE_BPF_ARG_UNDEF || sv->mask < msk)
 817                         return "undefined value on the stack";
 818
 819                 *rd = *sv;
 820
 821         /* pointer to mbuf */
 822         } else if (rs.v.type == RTE_BPF_ARG_PTR_MBUF) {
 823
 824                 if (rs.u.max == offsetof(struct rte_mbuf, next)) {
 825                         eval_fill_imm(rd, msk, 0);
 826                         rd->v = rs.v;
 827                 } else if (rs.u.max == offsetof(struct rte_mbuf, buf_addr)) {
 828                         eval_fill_imm(rd, msk, 0);
 829                         rd->v.type = RTE_BPF_ARG_PTR;
 830                         rd->v.size = rs.v.buf_size;
 831                 } else if (rs.u.max == offsetof(struct rte_mbuf, data_off)) {
 832                         eval_fill_imm(rd, msk, RTE_PKTMBUF_HEADROOM);
 833                         rd->v.type = RTE_BPF_ARG_RAW;
 834                 } else {
 835                         eval_max_load(rd, msk);
 836                         rd->v.type = RTE_BPF_ARG_RAW;
 837                 }
 838
 839         /* pointer to raw data */
 840         } else {
 841                 eval_max_load(rd, msk);
 842                 rd->v.type = RTE_BPF_ARG_RAW;
 843         }
 844
 845         return NULL;
 846 }
 847
 848 static const char *
 849 eval_mbuf_store(const struct bpf_reg_val *rv, uint32_t opsz)
 850 {
 851         uint32_t i;
 852
 853         static const struct {
 854                 size_t off;
 855                 size_t sz;
 856         } mbuf_ro_fileds[] = {
 857                 { .off = offsetof(struct rte_mbuf, buf_addr), },
 858                 { .off = offsetof(struct rte_mbuf, refcnt), },
 859                 { .off = offsetof(struct rte_mbuf, nb_segs), },
 860                 { .off = offsetof(struct rte_mbuf, buf_len), },
 861                 { .off = offsetof(struct rte_mbuf, pool), },
 862                 { .off = offsetof(struct rte_mbuf, next), },
 863                 { .off = offsetof(struct rte_mbuf, priv_size), },
 864         };
 865
 866         for (i = 0; i != RTE_DIM(mbuf_ro_fileds) &&
 867                         (mbuf_ro_fileds[i].off + mbuf_ro_fileds[i].sz <=
 868                         rv->u.max || rv->u.max + opsz <= mbuf_ro_fileds[i].off);
 869                         i++)
 870                 ;
 871
 872         if (i != RTE_DIM(mbuf_ro_fileds))
 873                 return "store to the read-only mbuf field";
 874
 875         return NULL;
 876
 877 }
 878
 879 static const char *
 880 eval_store(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 881 {
 882         uint32_t opsz;
 883         uint64_t msk;
 884         const char *err;
 885         struct bpf_eval_state *st;
 886         struct bpf_reg_val rd, rs, *sv;
 887
 888         opsz = bpf_size(BPF_SIZE(ins->code));
 889         msk = RTE_LEN2MASK(opsz * CHAR_BIT, uint64_t);
 890
 891         st = bvf->evst;
 892         rd = st->rv[ins->dst_reg];
 893
 894         if (BPF_CLASS(ins->code) == BPF_STX) {
 895                 rs = st->rv[ins->src_reg];
 896                 eval_apply_mask(&rs, msk);
 897         } else
 898                 eval_fill_imm(&rs, msk, ins->imm);
 899
 900         err = eval_defined(NULL, &rs);
 901         if (err != NULL)
 902                 return err;
 903
 904         err = eval_ptr(bvf, &rd, opsz, 1, ins->off);
 905         if (err != NULL)
 906                 return err;
 907
 908         if (rd.v.type == BPF_ARG_PTR_STACK) {
 909
 910                 sv = st->sv + rd.u.max / sizeof(uint64_t);
 911                 if (BPF_CLASS(ins->code) == BPF_STX &&
 912                                 BPF_MODE(ins->code) == EBPF_XADD)
 913                         eval_max_bound(sv, msk);
 914                 else
 915                         *sv = rs;
 916
 917         /* pointer to mbuf */
 918         } else if (rd.v.type == RTE_BPF_ARG_PTR_MBUF) {
 919                 err = eval_mbuf_store(&rd, opsz);
 920                 if (err != NULL)
 921                         return err;
 922         }
 923
 924         return NULL;
 925 }
 926
 927 static const char *
 928 eval_func_arg(struct bpf_verifier *bvf, const struct rte_bpf_arg *arg,
 929         struct bpf_reg_val *rv)
 930 {
 931         uint32_t i, n;
 932         struct bpf_eval_state *st;
 933         const char *err;
 934
 935         st = bvf->evst;
 936
 937         if (rv->v.type == RTE_BPF_ARG_UNDEF)
 938                 return "Undefined argument type";
 939
 940         if (arg->type != rv->v.type &&
 941                         arg->type != RTE_BPF_ARG_RAW &&
 942                         (arg->type != RTE_BPF_ARG_PTR ||
 943                         RTE_BPF_ARG_PTR_TYPE(rv->v.type) == 0))
 944                 return "Invalid argument type";
 945
 946         err = NULL;
 947
 948         /* argument is a pointer */
 949         if (RTE_BPF_ARG_PTR_TYPE(arg->type) != 0) {
 950
 951                 err = eval_ptr(bvf, rv, arg->size, 1, 0);
 952
 953                 /*
 954                  * pointer to the variable on the stack is passed
 955                  * as an argument, mark stack space it occupies as initialized.
 956                  */
 957                 if (err == NULL && rv->v.type == BPF_ARG_PTR_STACK) {
 958
 959                         i = rv->u.max / sizeof(uint64_t);
 960                         n = i + arg->size / sizeof(uint64_t);
 961                         while (i != n) {
 962                                 eval_fill_max_bound(st->sv + i, UINT64_MAX);
 963                                 i++;
 964                         };
 965                 }
 966         }
 967
 968         return err;
 969 }
 970
 971 static const char *
 972 eval_call(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 973 {
 974         uint32_t i, idx;
 975         struct bpf_reg_val *rv;
 976         const struct rte_bpf_xsym *xsym;
 977         const char *err;
 978
 979         idx = ins->imm;
 980
 981         if (idx >= bvf->prm->nb_xsym ||
 982                         bvf->prm->xsym[idx].type != RTE_BPF_XTYPE_FUNC)
 983                 return "invalid external function index";
 984
 985         /* for now don't support function calls on 32 bit platform */
 986         if (sizeof(uint64_t) != sizeof(uintptr_t))
 987                 return "function calls are supported only for 64 bit apps";
 988
 989         xsym = bvf->prm->xsym + idx;
 990
 991         /* evaluate function arguments */
 992         err = NULL;
 993         for (i = 0; i != xsym->func.nb_args && err == NULL; i++) {
 994                 err = eval_func_arg(bvf, xsym->func.args + i,
 995                         bvf->evst->rv + EBPF_REG_1 + i);
 996         }
 997
 998         /* R1-R5 argument/scratch registers */
 999         for (i = EBPF_REG_1; i != EBPF_REG_6; i++)
1000                 bvf->evst->rv[i].v.type = RTE_BPF_ARG_UNDEF;
1001
1002         /* update return value */
1003
1004         rv = bvf->evst->rv + EBPF_REG_0;
1005         rv->v = xsym->func.ret;
1006         if (rv->v.type == RTE_BPF_ARG_RAW)
1007                 eval_fill_max_bound(rv,
1008                         RTE_LEN2MASK(rv->v.size * CHAR_BIT, uint64_t));
1009         else if (RTE_BPF_ARG_PTR_TYPE(rv->v.type) != 0)
1010                 eval_fill_imm64(rv, UINTPTR_MAX, 0);
1011
1012         return err;
1013 }
1014
1015 static void
1016 eval_jeq_jne(struct bpf_reg_val *trd, struct bpf_reg_val *trs)
1017 {
1018         /* sreg is constant */
1019         if (trs->u.min == trs->u.max) {
1020                 trd->u = trs->u;
1021         /* dreg is constant */
1022         } else if (trd->u.min == trd->u.max) {
1023                 trs->u = trd->u;
1024         } else {
1025                 trd->u.max = RTE_MIN(trd->u.max, trs->u.max);
1026                 trd->u.min = RTE_MAX(trd->u.min, trs->u.min);
1027                 trs->u = trd->u;
1028         }
1029
1030         /* sreg is constant */
1031         if (trs->s.min == trs->s.max) {
1032                 trd->s = trs->s;
1033         /* dreg is constant */
1034         } else if (trd->s.min == trd->s.max) {
1035                 trs->s = trd->s;
1036         } else {
1037                 trd->s.max = RTE_MIN(trd->s.max, trs->s.max);
1038                 trd->s.min = RTE_MAX(trd->s.min, trs->s.min);
1039                 trs->s = trd->s;
1040         }
1041 }
1042
1043 static void
1044 eval_jgt_jle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1045         struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1046 {
1047         frd->u.max = RTE_MIN(frd->u.max, frs->u.min);
1048         trd->u.min = RTE_MAX(trd->u.min, trs->u.min + 1);
1049 }
1050
1051 static void
1052 eval_jlt_jge(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1053         struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1054 {
1055         frd->u.min = RTE_MAX(frd->u.min, frs->u.min);
1056         trd->u.max = RTE_MIN(trd->u.max, trs->u.max - 1);
1057 }
1058
1059 static void
1060 eval_jsgt_jsle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1061         struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1062 {
1063         frd->s.max = RTE_MIN(frd->s.max, frs->s.min);
1064         trd->s.min = RTE_MAX(trd->s.min, trs->s.min + 1);
1065 }
1066
1067 static void
1068 eval_jslt_jsge(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
1069         struct bpf_reg_val *frd, struct bpf_reg_val *frs)
1070 {
1071         frd->s.min = RTE_MAX(frd->s.min, frs->s.min);
1072         trd->s.max = RTE_MIN(trd->s.max, trs->s.max - 1);
1073 }
1074
1075 static const char *
1076 eval_jcc(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
1077 {
1078         uint32_t op;
1079         const char *err;
1080         struct bpf_eval_state *fst, *tst;
1081         struct bpf_reg_val *frd, *frs, *trd, *trs;
1082         struct bpf_reg_val rvf, rvt;
1083
1084         tst = bvf->evst;
1085         fst = bvf->evin->evst;
1086
1087         frd = fst->rv + ins->dst_reg;
1088         trd = tst->rv + ins->dst_reg;
1089
1090         if (BPF_SRC(ins->code) == BPF_X) {
1091                 frs = fst->rv + ins->src_reg;
1092                 trs = tst->rv + ins->src_reg;
1093         } else {
1094                 frs = &rvf;
1095                 trs = &rvt;
1096                 eval_fill_imm(frs, UINT64_MAX, ins->imm);
1097                 eval_fill_imm(trs, UINT64_MAX, ins->imm);
1098         }
1099
1100         err = eval_defined(trd, trs);
1101         if (err != NULL)
1102                 return err;
1103
1104         op = BPF_OP(ins->code);
1105
1106         if (op == BPF_JEQ)
1107                 eval_jeq_jne(trd, trs);
1108         else if (op == EBPF_JNE)
1109                 eval_jeq_jne(frd, frs);
1110         else if (op == BPF_JGT)
1111                 eval_jgt_jle(trd, trs, frd, frs);
1112         else if (op == EBPF_JLE)
1113                 eval_jgt_jle(frd, frs, trd, trs);
1114         else if (op == EBPF_JLT)
1115                 eval_jlt_jge(trd, trs, frd, frs);
1116         else if (op == BPF_JGE)
1117                 eval_jlt_jge(frd, frs, trd, trs);
1118         else if (op == EBPF_JSGT)
1119                 eval_jsgt_jsle(trd, trs, frd, frs);
1120         else if (op == EBPF_JSLE)
1121                 eval_jsgt_jsle(frd, frs, trd, trs);
1122         else if (op == EBPF_JSLT)
1123                 eval_jslt_jsge(trd, trs, frd, frs);
1124         else if (op == EBPF_JSGE)
1125                 eval_jslt_jsge(frd, frs, trd, trs);
1126
1127         return NULL;
1128 }
1129
1130 /*
1131  * validate parameters for each instruction type.
1132  */
1133 static const struct bpf_ins_check ins_chk[UINT8_MAX + 1] = {
1134         /* ALU IMM 32-bit instructions */
1135         [(BPF_ALU | BPF_ADD | BPF_K)] = {
1136                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1137                 .off = { .min = 0, .max = 0},
1138                 .imm = { .min = 0, .max = UINT32_MAX,},
1139                 .eval = eval_alu,
1140         },
1141         [(BPF_ALU | BPF_SUB | BPF_K)] = {
1142                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1143                 .off = { .min = 0, .max = 0},
1144                 .imm = { .min = 0, .max = UINT32_MAX,},
1145                 .eval = eval_alu,
1146         },
1147         [(BPF_ALU | BPF_AND | BPF_K)] = {
1148                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1149                 .off = { .min = 0, .max = 0},
1150                 .imm = { .min = 0, .max = UINT32_MAX,},
1151                 .eval = eval_alu,
1152         },
1153         [(BPF_ALU | BPF_OR | BPF_K)] = {
1154                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1155                 .off = { .min = 0, .max = 0},
1156                 .imm = { .min = 0, .max = UINT32_MAX,},
1157                 .eval = eval_alu,
1158         },
1159         [(BPF_ALU | BPF_LSH | BPF_K)] = {
1160                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1161                 .off = { .min = 0, .max = 0},
1162                 .imm = { .min = 0, .max = UINT32_MAX,},
1163                 .eval = eval_alu,
1164         },
1165         [(BPF_ALU | BPF_RSH | BPF_K)] = {
1166                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1167                 .off = { .min = 0, .max = 0},
1168                 .imm = { .min = 0, .max = UINT32_MAX,},
1169                 .eval = eval_alu,
1170         },
1171         [(BPF_ALU | BPF_XOR | BPF_K)] = {
1172                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1173                 .off = { .min = 0, .max = 0},
1174                 .imm = { .min = 0, .max = UINT32_MAX,},
1175                 .eval = eval_alu,
1176         },
1177         [(BPF_ALU | BPF_MUL | BPF_K)] = {
1178                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1179                 .off = { .min = 0, .max = 0},
1180                 .imm = { .min = 0, .max = UINT32_MAX,},
1181                 .eval = eval_alu,
1182         },
1183         [(BPF_ALU | EBPF_MOV | BPF_K)] = {
1184                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1185                 .off = { .min = 0, .max = 0},
1186                 .imm = { .min = 0, .max = UINT32_MAX,},
1187                 .eval = eval_alu,
1188         },
1189         [(BPF_ALU | BPF_DIV | BPF_K)] = {
1190                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1191                 .off = { .min = 0, .max = 0},
1192                 .imm = { .min = 1, .max = UINT32_MAX},
1193                 .eval = eval_alu,
1194         },
1195         [(BPF_ALU | BPF_MOD | BPF_K)] = {
1196                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1197                 .off = { .min = 0, .max = 0},
1198                 .imm = { .min = 1, .max = UINT32_MAX},
1199                 .eval = eval_alu,
1200         },
1201         /* ALU IMM 64-bit instructions */
1202         [(EBPF_ALU64 | BPF_ADD | BPF_K)] = {
1203                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1204                 .off = { .min = 0, .max = 0},
1205                 .imm = { .min = 0, .max = UINT32_MAX,},
1206                 .eval = eval_alu,
1207         },
1208         [(EBPF_ALU64 | BPF_SUB | BPF_K)] = {
1209                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1210                 .off = { .min = 0, .max = 0},
1211                 .imm = { .min = 0, .max = UINT32_MAX,},
1212                 .eval = eval_alu,
1213         },
1214         [(EBPF_ALU64 | BPF_AND | BPF_K)] = {
1215                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1216                 .off = { .min = 0, .max = 0},
1217                 .imm = { .min = 0, .max = UINT32_MAX,},
1218                 .eval = eval_alu,
1219         },
1220         [(EBPF_ALU64 | BPF_OR | BPF_K)] = {
1221                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1222                 .off = { .min = 0, .max = 0},
1223                 .imm = { .min = 0, .max = UINT32_MAX,},
1224                 .eval = eval_alu,
1225         },
1226         [(EBPF_ALU64 | BPF_LSH | BPF_K)] = {
1227                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1228                 .off = { .min = 0, .max = 0},
1229                 .imm = { .min = 0, .max = UINT32_MAX,},
1230                 .eval = eval_alu,
1231         },
1232         [(EBPF_ALU64 | BPF_RSH | BPF_K)] = {
1233                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1234                 .off = { .min = 0, .max = 0},
1235                 .imm = { .min = 0, .max = UINT32_MAX,},
1236                 .eval = eval_alu,
1237         },
1238         [(EBPF_ALU64 | EBPF_ARSH | BPF_K)] = {
1239                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1240                 .off = { .min = 0, .max = 0},
1241                 .imm = { .min = 0, .max = UINT32_MAX,},
1242                 .eval = eval_alu,
1243         },
1244         [(EBPF_ALU64 | BPF_XOR | BPF_K)] = {
1245                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1246                 .off = { .min = 0, .max = 0},
1247                 .imm = { .min = 0, .max = UINT32_MAX,},
1248                 .eval = eval_alu,
1249         },
1250         [(EBPF_ALU64 | BPF_MUL | BPF_K)] = {
1251                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1252                 .off = { .min = 0, .max = 0},
1253                 .imm = { .min = 0, .max = UINT32_MAX,},
1254                 .eval = eval_alu,
1255         },
1256         [(EBPF_ALU64 | EBPF_MOV | BPF_K)] = {
1257                 .mask = {.dreg = WRT_REGS, .sreg = ZERO_REG},
1258                 .off = { .min = 0, .max = 0},
1259                 .imm = { .min = 0, .max = UINT32_MAX,},
1260                 .eval = eval_alu,
1261         },
1262         [(EBPF_ALU64 | BPF_DIV | BPF_K)] = {
1263                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1264                 .off = { .min = 0, .max = 0},
1265                 .imm = { .min = 1, .max = UINT32_MAX},
1266                 .eval = eval_alu,
1267         },
1268         [(EBPF_ALU64 | BPF_MOD | BPF_K)] = {
1269                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1270                 .off = { .min = 0, .max = 0},
1271                 .imm = { .min = 1, .max = UINT32_MAX},
1272                 .eval = eval_alu,
1273         },
1274         /* ALU REG 32-bit instructions */
1275         [(BPF_ALU | BPF_ADD | BPF_X)] = {
1276                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1277                 .off = { .min = 0, .max = 0},
1278                 .imm = { .min = 0, .max = 0},
1279                 .eval = eval_alu,
1280         },
1281         [(BPF_ALU | BPF_SUB | BPF_X)] = {
1282                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1283                 .off = { .min = 0, .max = 0},
1284                 .imm = { .min = 0, .max = 0},
1285                 .eval = eval_alu,
1286         },
1287         [(BPF_ALU | BPF_AND | BPF_X)] = {
1288                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1289                 .off = { .min = 0, .max = 0},
1290                 .imm = { .min = 0, .max = 0},
1291                 .eval = eval_alu,
1292         },
1293         [(BPF_ALU | BPF_OR | BPF_X)] = {
1294                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1295                 .off = { .min = 0, .max = 0},
1296                 .imm = { .min = 0, .max = 0},
1297                 .eval = eval_alu,
1298         },
1299         [(BPF_ALU | BPF_LSH | BPF_X)] = {
1300                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1301                 .off = { .min = 0, .max = 0},
1302                 .imm = { .min = 0, .max = 0},
1303                 .eval = eval_alu,
1304         },
1305         [(BPF_ALU | BPF_RSH | BPF_X)] = {
1306                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1307                 .off = { .min = 0, .max = 0},
1308                 .imm = { .min = 0, .max = 0},
1309                 .eval = eval_alu,
1310         },
1311         [(BPF_ALU | BPF_XOR | BPF_X)] = {
1312                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1313                 .off = { .min = 0, .max = 0},
1314                 .imm = { .min = 0, .max = 0},
1315                 .eval = eval_alu,
1316         },
1317         [(BPF_ALU | BPF_MUL | BPF_X)] = {
1318                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1319                 .off = { .min = 0, .max = 0},
1320                 .imm = { .min = 0, .max = 0},
1321                 .eval = eval_alu,
1322         },
1323         [(BPF_ALU | BPF_DIV | BPF_X)] = {
1324                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1325                 .off = { .min = 0, .max = 0},
1326                 .imm = { .min = 0, .max = 0},
1327                 .eval = eval_alu,
1328         },
1329         [(BPF_ALU | BPF_MOD | BPF_X)] = {
1330                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1331                 .off = { .min = 0, .max = 0},
1332                 .imm = { .min = 0, .max = 0},
1333                 .eval = eval_alu,
1334         },
1335         [(BPF_ALU | EBPF_MOV | BPF_X)] = {
1336                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1337                 .off = { .min = 0, .max = 0},
1338                 .imm = { .min = 0, .max = 0},
1339                 .eval = eval_alu,
1340         },
1341         [(BPF_ALU | BPF_NEG)] = {
1342                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1343                 .off = { .min = 0, .max = 0},
1344                 .imm = { .min = 0, .max = 0},
1345                 .eval = eval_alu,
1346         },
1347         [(BPF_ALU | EBPF_END | EBPF_TO_BE)] = {
1348                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1349                 .off = { .min = 0, .max = 0},
1350                 .imm = { .min = 16, .max = 64},
1351                 .check = check_alu_bele,
1352                 .eval = eval_bele,
1353         },
1354         [(BPF_ALU | EBPF_END | EBPF_TO_LE)] = {
1355                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1356                 .off = { .min = 0, .max = 0},
1357                 .imm = { .min = 16, .max = 64},
1358                 .check = check_alu_bele,
1359                 .eval = eval_bele,
1360         },
1361         /* ALU REG 64-bit instructions */
1362         [(EBPF_ALU64 | BPF_ADD | BPF_X)] = {
1363                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1364                 .off = { .min = 0, .max = 0},
1365                 .imm = { .min = 0, .max = 0},
1366                 .eval = eval_alu,
1367         },
1368         [(EBPF_ALU64 | BPF_SUB | BPF_X)] = {
1369                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1370                 .off = { .min = 0, .max = 0},
1371                 .imm = { .min = 0, .max = 0},
1372                 .eval = eval_alu,
1373         },
1374         [(EBPF_ALU64 | BPF_AND | BPF_X)] = {
1375                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1376                 .off = { .min = 0, .max = 0},
1377                 .imm = { .min = 0, .max = 0},
1378                 .eval = eval_alu,
1379         },
1380         [(EBPF_ALU64 | BPF_OR | BPF_X)] = {
1381                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1382                 .off = { .min = 0, .max = 0},
1383                 .imm = { .min = 0, .max = 0},
1384                 .eval = eval_alu,
1385         },
1386         [(EBPF_ALU64 | BPF_LSH | BPF_X)] = {
1387                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1388                 .off = { .min = 0, .max = 0},
1389                 .imm = { .min = 0, .max = 0},
1390                 .eval = eval_alu,
1391         },
1392         [(EBPF_ALU64 | BPF_RSH | BPF_X)] = {
1393                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1394                 .off = { .min = 0, .max = 0},
1395                 .imm = { .min = 0, .max = 0},
1396                 .eval = eval_alu,
1397         },
1398         [(EBPF_ALU64 | EBPF_ARSH | BPF_X)] = {
1399                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1400                 .off = { .min = 0, .max = 0},
1401                 .imm = { .min = 0, .max = 0},
1402                 .eval = eval_alu,
1403         },
1404         [(EBPF_ALU64 | BPF_XOR | BPF_X)] = {
1405                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1406                 .off = { .min = 0, .max = 0},
1407                 .imm = { .min = 0, .max = 0},
1408                 .eval = eval_alu,
1409         },
1410         [(EBPF_ALU64 | BPF_MUL | BPF_X)] = {
1411                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1412                 .off = { .min = 0, .max = 0},
1413                 .imm = { .min = 0, .max = 0},
1414                 .eval = eval_alu,
1415         },
1416         [(EBPF_ALU64 | BPF_DIV | BPF_X)] = {
1417                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1418                 .off = { .min = 0, .max = 0},
1419                 .imm = { .min = 0, .max = 0},
1420                 .eval = eval_alu,
1421         },
1422         [(EBPF_ALU64 | BPF_MOD | BPF_X)] = {
1423                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1424                 .off = { .min = 0, .max = 0},
1425                 .imm = { .min = 0, .max = 0},
1426                 .eval = eval_alu,
1427         },
1428         [(EBPF_ALU64 | EBPF_MOV | BPF_X)] = {
1429                 .mask = { .dreg = WRT_REGS, .sreg = ALL_REGS},
1430                 .off = { .min = 0, .max = 0},
1431                 .imm = { .min = 0, .max = 0},
1432                 .eval = eval_alu,
1433         },
1434         [(EBPF_ALU64 | BPF_NEG)] = {
1435                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1436                 .off = { .min = 0, .max = 0},
1437                 .imm = { .min = 0, .max = 0},
1438                 .eval = eval_alu,
1439         },
1440         /* load instructions */
1441         [(BPF_LDX | BPF_MEM | BPF_B)] = {
1442                 .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1443                 .off = { .min = 0, .max = UINT16_MAX},
1444                 .imm = { .min = 0, .max = 0},
1445                 .eval = eval_load,
1446         },
1447         [(BPF_LDX | BPF_MEM | BPF_H)] = {
1448                 .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1449                 .off = { .min = 0, .max = UINT16_MAX},
1450                 .imm = { .min = 0, .max = 0},
1451                 .eval = eval_load,
1452         },
1453         [(BPF_LDX | BPF_MEM | BPF_W)] = {
1454                 .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1455                 .off = { .min = 0, .max = UINT16_MAX},
1456                 .imm = { .min = 0, .max = 0},
1457                 .eval = eval_load,
1458         },
1459         [(BPF_LDX | BPF_MEM | EBPF_DW)] = {
1460                 .mask = {. dreg = WRT_REGS, .sreg = ALL_REGS},
1461                 .off = { .min = 0, .max = UINT16_MAX},
1462                 .imm = { .min = 0, .max = 0},
1463                 .eval = eval_load,
1464         },
1465         /* load 64 bit immediate value */
1466         [(BPF_LD | BPF_IMM | EBPF_DW)] = {
1467                 .mask = { .dreg = WRT_REGS, .sreg = ZERO_REG},
1468                 .off = { .min = 0, .max = 0},
1469                 .imm = { .min = 0, .max = UINT32_MAX},
1470                 .eval = eval_ld_imm64,
1471         },
1472         /* load absolute instructions */
1473         [(BPF_LD | BPF_ABS | BPF_B)] = {
1474                 .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
1475                 .off = { .min = 0, .max = 0},
1476                 .imm = { .min = 0, .max = INT32_MAX},
1477                 .eval = eval_ld_mbuf,
1478         },
1479         [(BPF_LD | BPF_ABS | BPF_H)] = {
1480                 .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
1481                 .off = { .min = 0, .max = 0},
1482                 .imm = { .min = 0, .max = INT32_MAX},
1483                 .eval = eval_ld_mbuf,
1484         },
1485         [(BPF_LD | BPF_ABS | BPF_W)] = {
1486                 .mask = {. dreg = ZERO_REG, .sreg = ZERO_REG},
1487                 .off = { .min = 0, .max = 0},
1488                 .imm = { .min = 0, .max = INT32_MAX},
1489                 .eval = eval_ld_mbuf,
1490         },
1491         /* load indirect instructions */
1492         [(BPF_LD | BPF_IND | BPF_B)] = {
1493                 .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
1494                 .off = { .min = 0, .max = 0},
1495                 .imm = { .min = 0, .max = UINT32_MAX},
1496                 .eval = eval_ld_mbuf,
1497         },
1498         [(BPF_LD | BPF_IND | BPF_H)] = {
1499                 .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
1500                 .off = { .min = 0, .max = 0},
1501                 .imm = { .min = 0, .max = UINT32_MAX},
1502                 .eval = eval_ld_mbuf,
1503         },
1504         [(BPF_LD | BPF_IND | BPF_W)] = {
1505                 .mask = {. dreg = ZERO_REG, .sreg = IND_SRC_REGS},
1506                 .off = { .min = 0, .max = 0},
1507                 .imm = { .min = 0, .max = UINT32_MAX},
1508                 .eval = eval_ld_mbuf,
1509         },
1510         /* store REG instructions */
1511         [(BPF_STX | BPF_MEM | BPF_B)] = {
1512                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1513                 .off = { .min = 0, .max = UINT16_MAX},
1514                 .imm = { .min = 0, .max = 0},
1515                 .eval = eval_store,
1516         },
1517         [(BPF_STX | BPF_MEM | BPF_H)] = {
1518                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1519                 .off = { .min = 0, .max = UINT16_MAX},
1520                 .imm = { .min = 0, .max = 0},
1521                 .eval = eval_store,
1522         },
1523         [(BPF_STX | BPF_MEM | BPF_W)] = {
1524                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1525                 .off = { .min = 0, .max = UINT16_MAX},
1526                 .imm = { .min = 0, .max = 0},
1527                 .eval = eval_store,
1528         },
1529         [(BPF_STX | BPF_MEM | EBPF_DW)] = {
1530                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1531                 .off = { .min = 0, .max = UINT16_MAX},
1532                 .imm = { .min = 0, .max = 0},
1533                 .eval = eval_store,
1534         },
1535         /* atomic add instructions */
1536         [(BPF_STX | EBPF_XADD | BPF_W)] = {
1537                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1538                 .off = { .min = 0, .max = UINT16_MAX},
1539                 .imm = { .min = 0, .max = 0},
1540                 .eval = eval_store,
1541         },
1542         [(BPF_STX | EBPF_XADD | EBPF_DW)] = {
1543                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1544                 .off = { .min = 0, .max = UINT16_MAX},
1545                 .imm = { .min = 0, .max = 0},
1546                 .eval = eval_store,
1547         },
1548         /* store IMM instructions */
1549         [(BPF_ST | BPF_MEM | BPF_B)] = {
1550                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1551                 .off = { .min = 0, .max = UINT16_MAX},
1552                 .imm = { .min = 0, .max = UINT32_MAX},
1553                 .eval = eval_store,
1554         },
1555         [(BPF_ST | BPF_MEM | BPF_H)] = {
1556                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1557                 .off = { .min = 0, .max = UINT16_MAX},
1558                 .imm = { .min = 0, .max = UINT32_MAX},
1559                 .eval = eval_store,
1560         },
1561         [(BPF_ST | BPF_MEM | BPF_W)] = {
1562                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1563                 .off = { .min = 0, .max = UINT16_MAX},
1564                 .imm = { .min = 0, .max = UINT32_MAX},
1565                 .eval = eval_store,
1566         },
1567         [(BPF_ST | BPF_MEM | EBPF_DW)] = {
1568                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1569                 .off = { .min = 0, .max = UINT16_MAX},
1570                 .imm = { .min = 0, .max = UINT32_MAX},
1571                 .eval = eval_store,
1572         },
1573         /* jump instruction */
1574         [(BPF_JMP | BPF_JA)] = {
1575                 .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
1576                 .off = { .min = 0, .max = UINT16_MAX},
1577                 .imm = { .min = 0, .max = 0},
1578         },
1579         /* jcc IMM instructions */
1580         [(BPF_JMP | BPF_JEQ | BPF_K)] = {
1581                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1582                 .off = { .min = 0, .max = UINT16_MAX},
1583                 .imm = { .min = 0, .max = UINT32_MAX},
1584                 .eval = eval_jcc,
1585         },
1586         [(BPF_JMP | EBPF_JNE | BPF_K)] = {
1587                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1588                 .off = { .min = 0, .max = UINT16_MAX},
1589                 .imm = { .min = 0, .max = UINT32_MAX},
1590                 .eval = eval_jcc,
1591         },
1592         [(BPF_JMP | BPF_JGT | BPF_K)] = {
1593                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1594                 .off = { .min = 0, .max = UINT16_MAX},
1595                 .imm = { .min = 0, .max = UINT32_MAX},
1596                 .eval = eval_jcc,
1597         },
1598         [(BPF_JMP | EBPF_JLT | BPF_K)] = {
1599                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1600                 .off = { .min = 0, .max = UINT16_MAX},
1601                 .imm = { .min = 0, .max = UINT32_MAX},
1602                 .eval = eval_jcc,
1603         },
1604         [(BPF_JMP | BPF_JGE | BPF_K)] = {
1605                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1606                 .off = { .min = 0, .max = UINT16_MAX},
1607                 .imm = { .min = 0, .max = UINT32_MAX},
1608                 .eval = eval_jcc,
1609         },
1610         [(BPF_JMP | EBPF_JLE | BPF_K)] = {
1611                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1612                 .off = { .min = 0, .max = UINT16_MAX},
1613                 .imm = { .min = 0, .max = UINT32_MAX},
1614                 .eval = eval_jcc,
1615         },
1616         [(BPF_JMP | EBPF_JSGT | BPF_K)] = {
1617                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1618                 .off = { .min = 0, .max = UINT16_MAX},
1619                 .imm = { .min = 0, .max = UINT32_MAX},
1620                 .eval = eval_jcc,
1621         },
1622         [(BPF_JMP | EBPF_JSLT | BPF_K)] = {
1623                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1624                 .off = { .min = 0, .max = UINT16_MAX},
1625                 .imm = { .min = 0, .max = UINT32_MAX},
1626                 .eval = eval_jcc,
1627         },
1628         [(BPF_JMP | EBPF_JSGE | BPF_K)] = {
1629                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1630                 .off = { .min = 0, .max = UINT16_MAX},
1631                 .imm = { .min = 0, .max = UINT32_MAX},
1632                 .eval = eval_jcc,
1633         },
1634         [(BPF_JMP | EBPF_JSLE | BPF_K)] = {
1635                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1636                 .off = { .min = 0, .max = UINT16_MAX},
1637                 .imm = { .min = 0, .max = UINT32_MAX},
1638                 .eval = eval_jcc,
1639         },
1640         [(BPF_JMP | BPF_JSET | BPF_K)] = {
1641                 .mask = { .dreg = ALL_REGS, .sreg = ZERO_REG},
1642                 .off = { .min = 0, .max = UINT16_MAX},
1643                 .imm = { .min = 0, .max = UINT32_MAX},
1644                 .eval = eval_jcc,
1645         },
1646         /* jcc REG instructions */
1647         [(BPF_JMP | BPF_JEQ | BPF_X)] = {
1648                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1649                 .off = { .min = 0, .max = UINT16_MAX},
1650                 .imm = { .min = 0, .max = 0},
1651                 .eval = eval_jcc,
1652         },
1653         [(BPF_JMP | EBPF_JNE | BPF_X)] = {
1654                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1655                 .off = { .min = 0, .max = UINT16_MAX},
1656                 .imm = { .min = 0, .max = 0},
1657                 .eval = eval_jcc,
1658         },
1659         [(BPF_JMP | BPF_JGT | BPF_X)] = {
1660                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1661                 .off = { .min = 0, .max = UINT16_MAX},
1662                 .imm = { .min = 0, .max = 0},
1663                 .eval = eval_jcc,
1664         },
1665         [(BPF_JMP | EBPF_JLT | BPF_X)] = {
1666                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1667                 .off = { .min = 0, .max = UINT16_MAX},
1668                 .imm = { .min = 0, .max = 0},
1669                 .eval = eval_jcc,
1670         },
1671         [(BPF_JMP | BPF_JGE | BPF_X)] = {
1672                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1673                 .off = { .min = 0, .max = UINT16_MAX},
1674                 .imm = { .min = 0, .max = 0},
1675                 .eval = eval_jcc,
1676         },
1677         [(BPF_JMP | EBPF_JLE | BPF_X)] = {
1678                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1679                 .off = { .min = 0, .max = UINT16_MAX},
1680                 .imm = { .min = 0, .max = 0},
1681                 .eval = eval_jcc,
1682         },
1683         [(BPF_JMP | EBPF_JSGT | BPF_X)] = {
1684                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1685                 .off = { .min = 0, .max = UINT16_MAX},
1686                 .imm = { .min = 0, .max = 0},
1687                 .eval = eval_jcc,
1688         },
1689         [(BPF_JMP | EBPF_JSLT | BPF_X)] = {
1690                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1691                 .off = { .min = 0, .max = UINT16_MAX},
1692                 .imm = { .min = 0, .max = 0},
1693         },
1694         [(BPF_JMP | EBPF_JSGE | BPF_X)] = {
1695                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1696                 .off = { .min = 0, .max = UINT16_MAX},
1697                 .imm = { .min = 0, .max = 0},
1698                 .eval = eval_jcc,
1699         },
1700         [(BPF_JMP | EBPF_JSLE | BPF_X)] = {
1701                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1702                 .off = { .min = 0, .max = UINT16_MAX},
1703                 .imm = { .min = 0, .max = 0},
1704                 .eval = eval_jcc,
1705         },
1706         [(BPF_JMP | BPF_JSET | BPF_X)] = {
1707                 .mask = { .dreg = ALL_REGS, .sreg = ALL_REGS},
1708                 .off = { .min = 0, .max = UINT16_MAX},
1709                 .imm = { .min = 0, .max = 0},
1710                 .eval = eval_jcc,
1711         },
1712         /* call instruction */
1713         [(BPF_JMP | EBPF_CALL)] = {
1714                 .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
1715                 .off = { .min = 0, .max = 0},
1716                 .imm = { .min = 0, .max = UINT32_MAX},
1717                 .eval = eval_call,
1718         },
1719         /* ret instruction */
1720         [(BPF_JMP | EBPF_EXIT)] = {
1721                 .mask = { .dreg = ZERO_REG, .sreg = ZERO_REG},
1722                 .off = { .min = 0, .max = 0},
1723                 .imm = { .min = 0, .max = 0},
1724                 .eval = eval_exit,
1725         },
1726 };
1727
1728 /*
1729  * make sure that instruction syntax is valid,
1730  * and its fields don't violate particular instruction type restrictions.
1731  */
1732 static const char *
1733 check_syntax(const struct ebpf_insn *ins)
1734 {
1735
1736         uint8_t op;
1737         uint16_t off;
1738         uint32_t imm;
1739
1740         op = ins->code;
1741
1742         if (ins_chk[op].mask.dreg == 0)
1743                 return "invalid opcode";
1744
1745         if ((ins_chk[op].mask.dreg & 1 << ins->dst_reg) == 0)
1746                 return "invalid dst-reg field";
1747
1748         if ((ins_chk[op].mask.sreg & 1 << ins->src_reg) == 0)
1749                 return "invalid src-reg field";
1750
1751         off = ins->off;
1752         if (ins_chk[op].off.min > off || ins_chk[op].off.max < off)
1753                 return "invalid off field";
1754
1755         imm = ins->imm;
1756         if (ins_chk[op].imm.min > imm || ins_chk[op].imm.max < imm)
1757                 return "invalid imm field";
1758
1759         if (ins_chk[op].check != NULL)
1760                 return ins_chk[op].check(ins);
1761
1762         return NULL;
1763 }
1764
1765 /*
1766  * helper function, return instruction index for the given node.
1767  */
1768 static uint32_t
1769 get_node_idx(const struct bpf_verifier *bvf, const struct inst_node *node)
1770 {
1771         return node - bvf->in;
1772 }
1773
1774 /*
1775  * helper function, used to walk through constructed CFG.
1776  */
1777 static struct inst_node *
1778 get_next_node(struct bpf_verifier *bvf, struct inst_node *node)
1779 {
1780         uint32_t ce, ne, dst;
1781
1782         ne = node->nb_edge;
1783         ce = node->cur_edge;
1784         if (ce == ne)
1785                 return NULL;
1786
1787         node->cur_edge++;
1788         dst = node->edge_dest[ce];
1789         return bvf->in + dst;
1790 }
1791
1792 static void
1793 set_node_colour(struct bpf_verifier *bvf, struct inst_node *node,
1794         uint32_t new)
1795 {
1796         uint32_t prev;
1797
1798         prev = node->colour;
1799         node->colour = new;
1800
1801         bvf->node_colour[prev]--;
1802         bvf->node_colour[new]++;
1803 }
1804
1805 /*
1806  * helper function, add new edge between two nodes.
1807  */
1808 static int
1809 add_edge(struct bpf_verifier *bvf, struct inst_node *node, uint32_t nidx)
1810 {
1811         uint32_t ne;
1812
1813         if (nidx > bvf->prm->nb_ins) {
1814                 RTE_BPF_LOG(ERR, "%s: program boundary violation at pc: %u, "
1815                         "next pc: %u\n",
1816                         __func__, get_node_idx(bvf, node), nidx);
1817                 return -EINVAL;
1818         }
1819
1820         ne = node->nb_edge;
1821         if (ne >= RTE_DIM(node->edge_dest)) {
1822                 RTE_BPF_LOG(ERR, "%s: internal error at pc: %u\n",
1823                         __func__, get_node_idx(bvf, node));
1824                 return -EINVAL;
1825         }
1826
1827         node->edge_dest[ne] = nidx;
1828         node->nb_edge = ne + 1;
1829         return 0;
1830 }
1831
1832 /*
1833  * helper function, determine type of edge between two nodes.
1834  */
1835 static void
1836 set_edge_type(struct bpf_verifier *bvf, struct inst_node *node,
1837         const struct inst_node *next)
1838 {
1839         uint32_t ce, clr, type;
1840
1841         ce = node->cur_edge - 1;
1842         clr = next->colour;
1843
1844         type = UNKNOWN_EDGE;
1845
1846         if (clr == WHITE)
1847                 type = TREE_EDGE;
1848         else if (clr == GREY)
1849                 type = BACK_EDGE;
1850         else if (clr == BLACK)
1851                 /*
1852                  * in fact it could be either direct or cross edge,
1853                  * but for now, we don't need to distinguish between them.
1854                  */
1855                 type = CROSS_EDGE;
1856
1857         node->edge_type[ce] = type;
1858         bvf->edge_type[type]++;
1859 }
1860
1861 static struct inst_node *
1862 get_prev_node(struct bpf_verifier *bvf, struct inst_node *node)
1863 {
1864         return  bvf->in + node->prev_node;
1865 }
1866
1867 /*
1868  * Depth-First Search (DFS) through previously constructed
1869  * Control Flow Graph (CFG).
1870  * Information collected at this path would be used later
1871  * to determine is there any loops, and/or unreachable instructions.
1872  */
1873 static void
1874 dfs(struct bpf_verifier *bvf)
1875 {
1876         struct inst_node *next, *node;
1877
1878         node = bvf->in;
1879         while (node != NULL) {
1880
1881                 if (node->colour == WHITE)
1882                         set_node_colour(bvf, node, GREY);
1883
1884                 if (node->colour == GREY) {
1885
1886                         /* find next unprocessed child node */
1887                         do {
1888                                 next = get_next_node(bvf, node);
1889                                 if (next == NULL)
1890                                         break;
1891                                 set_edge_type(bvf, node, next);
1892                         } while (next->colour != WHITE);
1893
1894                         if (next != NULL) {
1895                                 /* proceed with next child */
1896                                 next->prev_node = get_node_idx(bvf, node);
1897                                 node = next;
1898                         } else {
1899                                 /*
1900                                  * finished with current node and all it's kids,
1901                                  * proceed with parent
1902                                  */
1903                                 set_node_colour(bvf, node, BLACK);
1904                                 node->cur_edge = 0;
1905                                 node = get_prev_node(bvf, node);
1906                         }
1907                 } else
1908                         node = NULL;
1909         }
1910 }
1911
1912 /*
1913  * report unreachable instructions.
1914  */
1915 static void
1916 log_unreachable(const struct bpf_verifier *bvf)
1917 {
1918         uint32_t i;
1919         struct inst_node *node;
1920         const struct ebpf_insn *ins;
1921
1922         for (i = 0; i != bvf->prm->nb_ins; i++) {
1923
1924                 node = bvf->in + i;
1925                 ins = bvf->prm->ins + i;
1926
1927                 if (node->colour == WHITE &&
1928                                 ins->code != (BPF_LD | BPF_IMM | EBPF_DW))
1929                         RTE_BPF_LOG(ERR, "unreachable code at pc: %u;\n", i);
1930         }
1931 }
1932
1933 /*
1934  * report loops detected.
1935  */
1936 static void
1937 log_loop(const struct bpf_verifier *bvf)
1938 {
1939         uint32_t i, j;
1940         struct inst_node *node;
1941
1942         for (i = 0; i != bvf->prm->nb_ins; i++) {
1943
1944                 node = bvf->in + i;
1945                 if (node->colour != BLACK)
1946                         continue;
1947
1948                 for (j = 0; j != node->nb_edge; j++) {
1949                         if (node->edge_type[j] == BACK_EDGE)
1950                                 RTE_BPF_LOG(ERR,
1951                                         "loop at pc:%u --> pc:%u;\n",
1952                                         i, node->edge_dest[j]);
1953                 }
1954         }
1955 }
1956
1957 /*
1958  * First pass goes though all instructions in the set, checks that each
1959  * instruction is a valid one (correct syntax, valid field values, etc.)
1960  * and constructs control flow graph (CFG).
1961  * Then depth-first search is performed over the constructed graph.
1962  * Programs with unreachable instructions and/or loops will be rejected.
1963  */
1964 static int
1965 validate(struct bpf_verifier *bvf)
1966 {
1967         int32_t rc;
1968         uint32_t i;
1969         struct inst_node *node;
1970         const struct ebpf_insn *ins;
1971         const char *err;
1972
1973         rc = 0;
1974         for (i = 0; i < bvf->prm->nb_ins; i++) {
1975
1976                 ins = bvf->prm->ins + i;
1977                 node = bvf->in + i;
1978
1979                 err = check_syntax(ins);
1980                 if (err != 0) {
1981                         RTE_BPF_LOG(ERR, "%s: %s at pc: %u\n",
1982                                 __func__, err, i);
1983                         rc |= -EINVAL;
1984                 }
1985
1986                 /*
1987                  * construct CFG, jcc nodes have to outgoing edges,
1988                  * 'exit' nodes - none, all other nodes have exactly one
1989                  * outgoing edge.
1990                  */
1991                 switch (ins->code) {
1992                 case (BPF_JMP | EBPF_EXIT):
1993                         break;
1994                 case (BPF_JMP | BPF_JEQ | BPF_K):
1995                 case (BPF_JMP | EBPF_JNE | BPF_K):
1996                 case (BPF_JMP | BPF_JGT | BPF_K):
1997                 case (BPF_JMP | EBPF_JLT | BPF_K):
1998                 case (BPF_JMP | BPF_JGE | BPF_K):
1999                 case (BPF_JMP | EBPF_JLE | BPF_K):
2000                 case (BPF_JMP | EBPF_JSGT | BPF_K):
2001                 case (BPF_JMP | EBPF_JSLT | BPF_K):
2002                 case (BPF_JMP | EBPF_JSGE | BPF_K):
2003                 case (BPF_JMP | EBPF_JSLE | BPF_K):
2004                 case (BPF_JMP | BPF_JSET | BPF_K):
2005                 case (BPF_JMP | BPF_JEQ | BPF_X):
2006                 case (BPF_JMP | EBPF_JNE | BPF_X):
2007                 case (BPF_JMP | BPF_JGT | BPF_X):
2008                 case (BPF_JMP | EBPF_JLT | BPF_X):
2009                 case (BPF_JMP | BPF_JGE | BPF_X):
2010                 case (BPF_JMP | EBPF_JLE | BPF_X):
2011                 case (BPF_JMP | EBPF_JSGT | BPF_X):
2012                 case (BPF_JMP | EBPF_JSLT | BPF_X):
2013                 case (BPF_JMP | EBPF_JSGE | BPF_X):
2014                 case (BPF_JMP | EBPF_JSLE | BPF_X):
2015                 case (BPF_JMP | BPF_JSET | BPF_X):
2016                         rc |= add_edge(bvf, node, i + ins->off + 1);
2017                         rc |= add_edge(bvf, node, i + 1);
2018                         bvf->nb_jcc_nodes++;
2019                         break;
2020                 case (BPF_JMP | BPF_JA):
2021                         rc |= add_edge(bvf, node, i + ins->off + 1);
2022                         break;
2023                 /* load 64 bit immediate value */
2024                 case (BPF_LD | BPF_IMM | EBPF_DW):
2025                         rc |= add_edge(bvf, node, i + 2);
2026                         i++;
2027                         break;
2028                 case (BPF_LD | BPF_ABS | BPF_B):
2029                 case (BPF_LD | BPF_ABS | BPF_H):
2030                 case (BPF_LD | BPF_ABS | BPF_W):
2031                 case (BPF_LD | BPF_IND | BPF_B):
2032                 case (BPF_LD | BPF_IND | BPF_H):
2033                 case (BPF_LD | BPF_IND | BPF_W):
2034                         bvf->nb_ldmb_nodes++;
2035                         /* fallthrough */
2036                 default:
2037                         rc |= add_edge(bvf, node, i + 1);
2038                         break;
2039                 }
2040
2041                 bvf->nb_nodes++;
2042                 bvf->node_colour[WHITE]++;
2043         }
2044
2045         if (rc != 0)
2046                 return rc;
2047
2048         dfs(bvf);
2049
2050         RTE_BPF_LOG(DEBUG, "%s(%p) stats:\n"
2051                 "nb_nodes=%u;\n"
2052                 "nb_jcc_nodes=%u;\n"
2053                 "node_color={[WHITE]=%u, [GREY]=%u,, [BLACK]=%u};\n"
2054                 "edge_type={[UNKNOWN]=%u, [TREE]=%u, [BACK]=%u, [CROSS]=%u};\n",
2055                 __func__, bvf,
2056                 bvf->nb_nodes,
2057                 bvf->nb_jcc_nodes,
2058                 bvf->node_colour[WHITE], bvf->node_colour[GREY],
2059                         bvf->node_colour[BLACK],
2060                 bvf->edge_type[UNKNOWN_EDGE], bvf->edge_type[TREE_EDGE],
2061                 bvf->edge_type[BACK_EDGE], bvf->edge_type[CROSS_EDGE]);
2062
2063         if (bvf->node_colour[BLACK] != bvf->nb_nodes) {
2064                 RTE_BPF_LOG(ERR, "%s(%p) unreachable instructions;\n",
2065                         __func__, bvf);
2066                 log_unreachable(bvf);
2067                 return -EINVAL;
2068         }
2069
2070         if (bvf->node_colour[GREY] != 0 || bvf->node_colour[WHITE] != 0 ||
2071                         bvf->edge_type[UNKNOWN_EDGE] != 0) {
2072                 RTE_BPF_LOG(ERR, "%s(%p) DFS internal error;\n",
2073                         __func__, bvf);
2074                 return -EINVAL;
2075         }
2076
2077         if (bvf->edge_type[BACK_EDGE] != 0) {
2078                 RTE_BPF_LOG(ERR, "%s(%p) loops detected;\n",
2079                         __func__, bvf);
2080                 log_loop(bvf);
2081                 return -EINVAL;
2082         }
2083
2084         return 0;
2085 }
2086
2087 /*
2088  * helper functions get/free eval states.
2089  */
2090 static struct bpf_eval_state *
2091 pull_eval_state(struct bpf_verifier *bvf)
2092 {
2093         uint32_t n;
2094
2095         n = bvf->evst_pool.cur;
2096         if (n == bvf->evst_pool.num)
2097                 return NULL;
2098
2099         bvf->evst_pool.cur = n + 1;
2100         return bvf->evst_pool.ent + n;
2101 }
2102
2103 static void
2104 push_eval_state(struct bpf_verifier *bvf)
2105 {
2106         bvf->evst_pool.cur--;
2107 }
2108
2109 static void
2110 evst_pool_fini(struct bpf_verifier *bvf)
2111 {
2112         bvf->evst = NULL;
2113         free(bvf->evst_pool.ent);
2114         memset(&bvf->evst_pool, 0, sizeof(bvf->evst_pool));
2115 }
2116
2117 static int
2118 evst_pool_init(struct bpf_verifier *bvf)
2119 {
2120         uint32_t n;
2121
2122         n = bvf->nb_jcc_nodes + 1;
2123
2124         bvf->evst_pool.ent = calloc(n, sizeof(bvf->evst_pool.ent[0]));
2125         if (bvf->evst_pool.ent == NULL)
2126                 return -ENOMEM;
2127
2128         bvf->evst_pool.num = n;
2129         bvf->evst_pool.cur = 0;
2130
2131         bvf->evst = pull_eval_state(bvf);
2132         return 0;
2133 }
2134
2135 /*
2136  * Save current eval state.
2137  */
2138 static int
2139 save_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
2140 {
2141         struct bpf_eval_state *st;
2142
2143         /* get new eval_state for this node */
2144         st = pull_eval_state(bvf);
2145         if (st == NULL) {
2146                 RTE_BPF_LOG(ERR,
2147                         "%s: internal error (out of space) at pc: %u\n",
2148                         __func__, get_node_idx(bvf, node));
2149                 return -ENOMEM;
2150         }
2151
2152         /* make a copy of current state */
2153         memcpy(st, bvf->evst, sizeof(*st));
2154
2155         /* swap current state with new one */
2156         node->evst = bvf->evst;
2157         bvf->evst = st;
2158
2159         RTE_BPF_LOG(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;\n",
2160                 __func__, bvf, get_node_idx(bvf, node), node->evst, bvf->evst);
2161
2162         return 0;
2163 }
2164
2165 /*
2166  * Restore previous eval state and mark current eval state as free.
2167  */
2168 static void
2169 restore_eval_state(struct bpf_verifier *bvf, struct inst_node *node)
2170 {
2171         RTE_BPF_LOG(DEBUG, "%s(bvf=%p,node=%u) old/new states: %p/%p;\n",
2172                 __func__, bvf, get_node_idx(bvf, node), bvf->evst, node->evst);
2173
2174         bvf->evst = node->evst;
2175         node->evst = NULL;
2176         push_eval_state(bvf);
2177 }
2178
2179 static void
2180 log_eval_state(const struct bpf_verifier *bvf, const struct ebpf_insn *ins,
2181         uint32_t pc, int32_t loglvl)
2182 {
2183         const struct bpf_eval_state *st;
2184         const struct bpf_reg_val *rv;
2185
2186         rte_log(loglvl, rte_bpf_logtype, "%s(pc=%u):\n", __func__, pc);
2187
2188         st = bvf->evst;
2189         rv = st->rv + ins->dst_reg;
2190
2191         rte_log(loglvl, rte_bpf_logtype,
2192                 "r%u={\n"
2193                 "\tv={type=%u, size=%zu},\n"
2194                 "\tmask=0x%" PRIx64 ",\n"
2195                 "\tu={min=0x%" PRIx64 ", max=0x%" PRIx64 "},\n"
2196                 "\ts={min=%" PRId64 ", max=%" PRId64 "},\n"
2197                 "};\n",
2198                 ins->dst_reg,
2199                 rv->v.type, rv->v.size,
2200                 rv->mask,
2201                 rv->u.min, rv->u.max,
2202                 rv->s.min, rv->s.max);
2203 }
2204
2205 /*
2206  * Do second pass through CFG and try to evaluate instructions
2207  * via each possible path.
2208  * Right now evaluation functionality is quite limited.
2209  * Still need to add extra checks for:
2210  * - use/return uninitialized registers.
2211  * - use uninitialized data from the stack.
2212  * - memory boundaries violation.
2213  */
2214 static int
2215 evaluate(struct bpf_verifier *bvf)
2216 {
2217         int32_t rc;
2218         uint32_t idx, op;
2219         const char *err;
2220         const struct ebpf_insn *ins;
2221         struct inst_node *next, *node;
2222
2223         /* initial state of frame pointer */
2224         static const struct bpf_reg_val rvfp = {
2225                 .v = {
2226                         .type = BPF_ARG_PTR_STACK,
2227                         .size = MAX_BPF_STACK_SIZE,
2228                 },
2229                 .mask = UINT64_MAX,
2230                 .u = {.min = MAX_BPF_STACK_SIZE, .max = MAX_BPF_STACK_SIZE},
2231                 .s = {.min = MAX_BPF_STACK_SIZE, .max = MAX_BPF_STACK_SIZE},
2232         };
2233
2234         bvf->evst->rv[EBPF_REG_1].v = bvf->prm->prog_arg;
2235         bvf->evst->rv[EBPF_REG_1].mask = UINT64_MAX;
2236         if (bvf->prm->prog_arg.type == RTE_BPF_ARG_RAW)
2237                 eval_max_bound(bvf->evst->rv + EBPF_REG_1, UINT64_MAX);
2238
2239         bvf->evst->rv[EBPF_REG_10] = rvfp;
2240
2241         ins = bvf->prm->ins;
2242         node = bvf->in;
2243         next = node;
2244         rc = 0;
2245
2246         while (node != NULL && rc == 0) {
2247
2248                 /*
2249                  * current node evaluation, make sure we evaluate
2250                  * each node only once.
2251                  */
2252                 if (next != NULL) {
2253
2254                         bvf->evin = node;
2255                         idx = get_node_idx(bvf, node);
2256                         op = ins[idx].code;
2257
2258                         /* for jcc node make a copy of evaluation state */
2259                         if (node->nb_edge > 1)
2260                                 rc |= save_eval_state(bvf, node);
2261
2262                         if (ins_chk[op].eval != NULL && rc == 0) {
2263                                 err = ins_chk[op].eval(bvf, ins + idx);
2264                                 if (err != NULL) {
2265                                         RTE_BPF_LOG(ERR, "%s: %s at pc: %u\n",
2266                                                 __func__, err, idx);
2267                                         rc = -EINVAL;
2268                                 }
2269                         }
2270
2271                         log_eval_state(bvf, ins + idx, idx, RTE_LOG_DEBUG);
2272                         bvf->evin = NULL;
2273                 }
2274
2275                 /* proceed through CFG */
2276                 next = get_next_node(bvf, node);
2277                 if (next != NULL) {
2278
2279                         /* proceed with next child */
2280                         if (node->cur_edge == node->nb_edge &&
2281                                         node->evst != NULL)
2282                                 restore_eval_state(bvf, node);
2283
2284                         next->prev_node = get_node_idx(bvf, node);
2285                         node = next;
2286                 } else {
2287                         /*
2288                          * finished with current node and all it's kids,
2289                          * proceed with parent
2290                          */
2291                         node->cur_edge = 0;
2292                         node = get_prev_node(bvf, node);
2293
2294                         /* finished */
2295                         if (node == bvf->in)
2296                                 node = NULL;
2297                 }
2298         }
2299
2300         return rc;
2301 }
2302
2303 int
2304 bpf_validate(struct rte_bpf *bpf)
2305 {
2306         int32_t rc;
2307         struct bpf_verifier bvf;
2308
2309         /* check input argument type, don't allow mbuf ptr on 32-bit */
2310         if (bpf->prm.prog_arg.type != RTE_BPF_ARG_RAW &&
2311                         bpf->prm.prog_arg.type != RTE_BPF_ARG_PTR &&
2312                         (sizeof(uint64_t) != sizeof(uintptr_t) ||
2313                         bpf->prm.prog_arg.type != RTE_BPF_ARG_PTR_MBUF)) {
2314                 RTE_BPF_LOG(ERR, "%s: unsupported argument type\n", __func__);
2315                 return -ENOTSUP;
2316         }
2317
2318         memset(&bvf, 0, sizeof(bvf));
2319         bvf.prm = &bpf->prm;
2320         bvf.in = calloc(bpf->prm.nb_ins, sizeof(bvf.in[0]));
2321         if (bvf.in == NULL)
2322                 return -ENOMEM;
2323
2324         rc = validate(&bvf);
2325
2326         if (rc == 0) {
2327                 rc = evst_pool_init(&bvf);
2328                 if (rc == 0)
2329                         rc = evaluate(&bvf);
2330                 evst_pool_fini(&bvf);
2331         }
2332
2333         free(bvf.in);
2334
2335         /* copy collected info */
2336         if (rc == 0) {
2337                 bpf->stack_sz = bvf.stack_sz;
2338
2339                 /* for LD_ABS/LD_IND, we'll need extra space on the stack */
2340                 if (bvf.nb_ldmb_nodes != 0)
2341                         bpf->stack_sz = RTE_ALIGN_CEIL(bpf->stack_sz +
2342                                 sizeof(uint64_t), sizeof(uint64_t));
2343         }
2344
2345         return rc;
2346 }