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