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