1 // SPDX-License-Identifier: GPL-2.0-only 2 /* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */ 3 4 #include <linux/bpf_verifier.h> 5 #include <linux/jhash.h> 6 #include <linux/log2.h> 7 #include <linux/min_heap.h> 8 #include <linux/bug.h> 9 10 #define REGS_NUM (MAX_BPF_REG + MAX_BPF_STACK_SLOTS) 11 #define UNKNOWN_EXPR_ID 0 12 #define OPAQUE_EXPR_ID 1 13 14 /* 15 * BPF instructions use 'code', 'src_reg', 'off' and 'imm' fields for instruction encoding. 16 * For scalar evolution purpose we want to reuse most of the opcode definitions, 17 * but also add a few custom operations (REG and IMM). 18 * Use the enum below to uniformly represent all operations relevant for SCEV. 19 */ 20 enum expr_op { 21 /* leave range 0..255 for standard bpf opcodes */ 22 UNKNOWN = 256, /* start custom opcodes from the second byte */ 23 REG, 24 IMM, 25 SDIV, SMOD, 26 SEXT8, SEXT16, SEXT32, 27 ZEXT8, ZEXT16, ZEXT32, 28 BSWAP16, BSWAP32, BSWAP64, 29 /* during the loop body execution the value can be either of param[0] or param[1] */ 30 ANY, 31 /* some value that verifier is not going to track precisely */ 32 OPAQUE, 33 /* '*(u8/16/32 *)(r10 + X) = Y' writes define slot contents only partially */ 34 SPILL8, SPILL16, SPILL32, 35 /* 36 * SCEV expression corresponding to linear equation 'param[0] + param[1] * k', 37 * where k is a loop iteration number. Loop here refers to innermost loop 38 * containing instruction associated with this expression, as returned by 39 * bpf_loop_at_index(). 40 */ 41 LINEAR_SCEV, 42 }; 43 44 struct expr { 45 u32 op; 46 union { 47 u32 params[2]; 48 s64 imm; 49 }; 50 }; 51 52 struct expr_bucket { 53 u32 cnt; 54 u32 cap; 55 u32 ids[]; 56 }; 57 58 struct env { 59 bool empty; 60 u32 reg2expr[REGS_NUM]; 61 u32 reg2scev[REGS_NUM]; 62 }; 63 64 struct insn_envs { 65 u32 cnt; 66 struct { 67 int loop_header; 68 struct env *env; 69 } entries[]; 70 }; 71 72 #define EXPR_STACK_DEPTH 8 73 74 struct expr_stack_elt { 75 u32 id:28; 76 u32 pre:1; 77 u32 next_param:2; 78 }; 79 80 DEFINE_MIN_HEAP(int, scev_worklist); 81 82 struct scev { 83 /* 84 * Expressions are identified by id, exprs_ht ensures that 85 * each expression exists as a unique instance. 86 * This allows for fast equivalence check: id1 === id2. 87 */ 88 struct expr_bucket **exprs_ht; 89 struct scev_worklist worklist; 90 struct insn_envs **envs; 91 struct expr *exprs; 92 /* 93 * Loops are analyzed one by one, this array keeps track if a particular 94 * instruction was visited on a current pass. 95 */ 96 u32 *discovered; 97 u32 exprs_ht_cnt; 98 int exprs_cnt; 99 int exprs_cap; 100 int envs_cnt; 101 int stack_sz; 102 struct expr_stack_elt expr_stack[EXPR_STACK_DEPTH]; 103 u32 ids_buf[EXPR_STACK_DEPTH]; 104 }; 105 106 static u32 expr_hash(struct expr *e) 107 { 108 return jhash_3words(e->op, e->params[0], e->params[1], 0); 109 } 110 111 static int expr_eq(struct expr *a, struct expr *b) 112 { 113 return a->op == b->op && a->imm == b->imm; 114 } 115 116 static int add_expr(struct scev *scev, struct expr e) 117 { 118 struct expr_bucket *bucket; 119 u32 i, id, hash, new_cap; 120 void *tmp; 121 122 hash = expr_hash(&e) & (scev->exprs_ht_cnt - 1); 123 bucket = scev->exprs_ht[hash]; 124 125 if (bucket) { 126 for (i = 0; i < bucket->cnt; i++) { 127 id = bucket->ids[i]; 128 if (expr_eq(&e, &scev->exprs[id])) 129 return id; 130 } 131 } 132 133 if (!bucket || bucket->cap == bucket->cnt) { 134 new_cap = bucket ? bucket->cap * 2 : 4; 135 bucket = kvrealloc(bucket, sizeof(*bucket) + sizeof(u32) * new_cap, GFP_KERNEL_ACCOUNT | __GFP_ZERO); 136 if (!bucket) 137 return -ENOMEM; 138 scev->exprs_ht[hash] = bucket; 139 bucket->cap = new_cap; 140 } 141 142 if (scev->exprs_cnt == scev->exprs_cap) { 143 new_cap = scev->exprs_cap ? scev->exprs_cap * 2 : 256; 144 tmp = kvrealloc(scev->exprs, sizeof(struct expr) * new_cap, GFP_KERNEL_ACCOUNT); 145 if (!tmp) 146 return -ENOMEM; 147 scev->exprs = tmp; 148 scev->exprs_cap = new_cap; 149 } 150 151 id = scev->exprs_cnt++; 152 scev->exprs[id] = e; 153 bucket->ids[bucket->cnt++] = id; 154 return id; 155 } 156 157 static int expr2(struct scev *scev, u32 op, int a, int b) 158 { 159 if (a < 0) 160 return a; 161 if (b < 0) 162 return b; 163 return add_expr(scev, (struct expr){ .op = op, .params = {a, b} }); 164 } 165 166 static int expr1(struct scev *scev, u32 op, int a) 167 { 168 if (a < 0) 169 return a; 170 return expr2(scev, op, a, 0); 171 } 172 173 static int expr0(struct scev *scev, u32 op) 174 { 175 return expr2(scev, op, 0, 0); 176 } 177 178 static int imm_expr(struct scev *scev, s64 value) 179 { 180 return add_expr(scev, (struct expr){ .op = IMM, .imm = value }); 181 } 182 183 static bool same_exprs(struct scev *scev, int id_a, int id_b) 184 { 185 return id_a == id_b; 186 } 187 188 static bool is_imm(struct scev *scev, int id, s64 *imm) 189 { 190 if (scev->exprs[id].op != IMM) 191 return false; 192 *imm = scev->exprs[id].imm; 193 return true; 194 } 195 196 static bool is_op(struct scev *scev, int id, u32 op) 197 { 198 if (scev->exprs[id].op != op) 199 return false; 200 return true; 201 } 202 203 static bool is_unop(struct scev *scev, enum expr_op op, int id, u32 *p0) 204 { 205 if (scev->exprs[id].op != op) 206 return false; 207 *p0 = scev->exprs[id].params[0]; 208 return true; 209 } 210 211 static bool is_binop(struct scev *scev, enum expr_op op, int id, u32 *p0, u32 *p1) 212 { 213 if (scev->exprs[id].op != op) 214 return false; 215 *p0 = scev->exprs[id].params[0]; 216 *p1 = scev->exprs[id].params[1]; 217 return true; 218 } 219 220 static bool is_reg(struct scev *scev, int id, u32 *reg) 221 { 222 return is_unop(scev, REG, id, reg); 223 } 224 225 static bool is_add(struct scev *scev, int id, u32 *left, u32 *right) 226 { 227 return is_binop(scev, BPF_ADD, id, left, right); 228 } 229 230 static bool is_zext32(struct scev *scev, int id, u32 *left) 231 { 232 return is_unop(scev, ZEXT32, id, left); 233 } 234 235 static bool is_any(struct scev *scev, int id, u32 *left, u32 *right) 236 { 237 return is_binop(scev, ANY, id, left, right); 238 } 239 240 static bool is_linear(struct scev *scev, int id, u32 *base, u32 *slope) 241 { 242 return is_binop(scev, LINEAR_SCEV, id, base, slope); 243 } 244 245 static bool is_opaque(struct scev *scev, int id) 246 { 247 return is_op(scev, id, OPAQUE); 248 } 249 250 static void log_reg(struct bpf_verifier_env *env, u32 reg) 251 { 252 if (reg < MAX_BPF_REG) 253 bpf_log(&env->log, "r%d", reg); 254 else 255 bpf_log(&env->log, "*fp%d", (MAX_BPF_REG - reg - 1) * 8); 256 } 257 258 static const char *op_str(u32 op) 259 { 260 switch (op) { 261 case BPF_ADD: return "+"; 262 case BPF_SUB: return "-"; 263 case BPF_MUL: return "*"; 264 case BPF_DIV: return "/"; 265 case SDIV: return "s/"; 266 case BPF_OR: return "|"; 267 case BPF_AND: return "&"; 268 case BPF_LSH: return "<<"; 269 case BPF_RSH: return ">>"; 270 case BPF_NEG: return "-"; 271 case BPF_MOD: return "%"; 272 case SMOD: return "s%"; 273 case BPF_XOR: return "^"; 274 case BPF_ARSH: return "s>>"; 275 case SEXT8: return "sext8"; 276 case SEXT16: return "sext16"; 277 case SEXT32: return "sext32"; 278 case ZEXT8: return "zext8"; 279 case ZEXT16: return "zext16"; 280 case ZEXT32: return "zext32"; 281 case BSWAP16: return "bswap16"; 282 case BSWAP32: return "bswap32"; 283 case BSWAP64: return "bswap64"; 284 case SPILL8: return "spill8"; 285 case SPILL16: return "spill16"; 286 case SPILL32: return "spill32"; 287 case ANY: return "any"; 288 case LINEAR_SCEV: return "linear"; 289 } 290 return NULL; 291 } 292 293 static u32 op_params_num(u32 op) 294 { 295 switch (op) { 296 case BPF_ADD: 297 case BPF_SUB: 298 case BPF_MUL: 299 case BPF_DIV: 300 case BPF_MOD: 301 case BPF_OR: 302 case BPF_XOR: 303 case BPF_AND: 304 case BPF_LSH: 305 case BPF_RSH: 306 case BPF_ARSH: 307 case SDIV: 308 case SMOD: 309 case ANY: 310 case LINEAR_SCEV: 311 return 2; 312 case BPF_NEG: 313 case SEXT8: 314 case SEXT16: 315 case SEXT32: 316 case ZEXT8: 317 case ZEXT16: 318 case ZEXT32: 319 case BSWAP16: 320 case BSWAP32: 321 case BSWAP64: 322 case SPILL8: 323 case SPILL16: 324 case SPILL32: 325 return 1; 326 case REG: 327 case IMM: 328 case OPAQUE: 329 return 0; 330 default: 331 return 0; 332 } 333 } 334 335 static bool expr_stack_push(struct scev *scev, u32 id) 336 { 337 if (scev->stack_sz >= EXPR_STACK_DEPTH) 338 return false; 339 scev->expr_stack[scev->stack_sz].id = id; 340 scev->expr_stack[scev->stack_sz].pre = true; 341 scev->expr_stack[scev->stack_sz].next_param = 0; 342 scev->stack_sz++; 343 return true; 344 } 345 346 enum { 347 PRE = BIT(1), POST = BIT(2), DEPTH_LIMIT = BIT(3) 348 }; 349 350 static bool expr_next(struct scev *scev, u32 *id, u32 *order) 351 { 352 struct expr_stack_elt *elt; 353 struct expr *expr; 354 u32 num_params; 355 356 if (scev->stack_sz == 0) 357 return false; 358 359 elt = &scev->expr_stack[scev->stack_sz - 1]; 360 *id = elt->id; 361 *order = 0; 362 expr = &scev->exprs[elt->id]; 363 num_params = op_params_num(expr->op); 364 if (elt->pre) { 365 elt->pre = false; 366 *order = PRE; 367 return true; 368 } 369 if (elt->next_param == num_params) { 370 *order = POST; 371 scev->stack_sz--; 372 return true; 373 } 374 if (scev->stack_sz == EXPR_STACK_DEPTH) { 375 *order = POST | DEPTH_LIMIT; 376 scev->stack_sz--; 377 return true; 378 } 379 expr_stack_push(scev, expr->params[elt->next_param]); 380 elt->next_param++; 381 return expr_next(scev, id, order); 382 } 383 384 static void log_expr(struct bpf_verifier_env *env, u32 id) 385 { 386 struct bpf_verifier_log *log = &env->log; 387 struct scev *scev = env->scev; 388 struct expr *expr; 389 const char *str; 390 u32 order; 391 392 scev->stack_sz = 0; 393 expr_stack_push(scev, id); 394 while (expr_next(scev, &id, &order)) { 395 if ((order & PRE) && scev->stack_sz > 1) 396 bpf_log(log, " "); 397 expr = &scev->exprs[id]; 398 switch (expr->op) { 399 case UNKNOWN: 400 if (order & PRE) 401 bpf_log(log, "?"); 402 break; 403 case OPAQUE: 404 if (order & PRE) 405 bpf_log(log, "_"); 406 break; 407 case REG: 408 if (order & PRE) 409 log_reg(env, expr->params[0]); 410 break; 411 case IMM: 412 if (order & PRE) 413 bpf_log(log, "%lld", expr->imm); 414 break; 415 default: 416 if (order & PRE) { 417 str = op_str(expr->op); 418 bpf_log(log, "("); 419 if (str) 420 bpf_log(log, "%s", str); 421 else 422 bpf_log(log, "bad-expr-op %x", expr->op); 423 } 424 if (order & DEPTH_LIMIT) 425 bpf_log(log, "..."); 426 if (order & POST) 427 bpf_log(log, ")"); 428 } 429 } 430 } 431 432 static bool reg_alive_at(struct bpf_verifier_env *env, u32 reg, u32 insn_idx) 433 { 434 struct bpf_insn_aux_data *aux = env->insn_aux_data; 435 u16 live_regs = aux[insn_idx].live_regs_before; 436 437 return reg < MAX_BPF_REG 438 ? (BIT(reg) & live_regs) 439 : test_bit(reg - MAX_BPF_REG, aux[insn_idx].live_stack_before); 440 } 441 442 static void print_env(struct bpf_verifier_env *env, struct env *e, u32 insn_idx) 443 { 444 struct bpf_verifier_log *log = &env->log; 445 struct scev *scev = env->scev; 446 bool printed_some = false; 447 bool is_self_scev; 448 bool is_self_reg; 449 int i, r; 450 451 if (e->empty) { 452 bpf_log(log, " <empty>\n"); 453 return; 454 } 455 456 for (i = 0; i < REGS_NUM; i++) { 457 if (!reg_alive_at(env, i, insn_idx)) 458 continue; 459 is_self_reg = is_reg(scev, e->reg2expr[i], &r) && i == r; 460 is_self_scev = is_reg(scev, e->reg2scev[i], &r) && i == r; 461 if (is_self_reg && is_self_scev) 462 continue; 463 printed_some = true; 464 bpf_log(log, " "); 465 log_reg(env, i); 466 bpf_log(log, "="); 467 log_expr(env, e->reg2expr[i]); 468 if (e->reg2expr[i] != UNKNOWN_EXPR_ID) { 469 bpf_log(log, " / "); 470 log_expr(env, e->reg2scev[i]); 471 } 472 bpf_log(log, "\n"); 473 } 474 if (!printed_some) 475 bpf_log(log, " <all regs unchanged>\n"); 476 } 477 static struct env *find_loop_env(struct scev *scev, int loop_header, int insn_idx) 478 { 479 struct insn_envs *envs = scev->envs[insn_idx]; 480 u32 i; 481 482 if (!envs) 483 return NULL; 484 for (i = 0; i < envs->cnt; i++) 485 if (envs->entries[i].loop_header == loop_header) 486 return envs->entries[i].env; 487 return NULL; 488 } 489 490 static struct env *find_header_env(struct scev *scev, int header) 491 { 492 return find_loop_env(scev, header, header); 493 } 494 495 static struct env *get_loop_env(struct scev *scev, int loop_header, int insn_idx) 496 { 497 struct insn_envs *envs = scev->envs[insn_idx]; 498 u32 cnt = envs ? envs->cnt : 0; 499 struct insn_envs *tmp; 500 struct env *e; 501 502 e = find_loop_env(scev, loop_header, insn_idx); 503 if (e) 504 return e; 505 506 e = kzalloc(sizeof(*e), GFP_KERNEL_ACCOUNT); 507 if (!e) 508 return NULL; 509 510 tmp = krealloc(envs, struct_size(envs, entries, cnt + 1), GFP_KERNEL_ACCOUNT); 511 if (!tmp) { 512 kfree(e); 513 return NULL; 514 } 515 516 e->empty = true; 517 tmp->entries[cnt].loop_header = loop_header; 518 tmp->entries[cnt].env = e; 519 tmp->cnt = cnt + 1; 520 scev->envs[insn_idx] = tmp; 521 return e; 522 } 523 524 static int replace_reg(struct scev *scev, struct env *e, u32 reg, int id) 525 { 526 if (id < 0) 527 return id; 528 e->reg2expr[reg] = id; 529 return 0; 530 } 531 532 static int setup_initial_loop_env(struct bpf_verifier_env *env, struct env *e, int insn_idx) 533 { 534 struct scev *scev = env->scev; 535 int i, err; 536 537 /* 538 * Initial assignments are of form rX -> rX are needed as seeds for subsequent 539 * work queue pop / transfer() calls. Because e->empty is true, the first backedge 540 * join() will overwrite the them. compute_header_scevs() accounts for register 541 * states at loop entry. 542 */ 543 for (i = 0; i < REGS_NUM; i++) { 544 err = replace_reg(scev, e, i, expr1(scev, REG, i)); 545 if (err) 546 return err; 547 } 548 return 0; 549 } 550 551 static void forget_call_regs(struct env *e) 552 { 553 int i; 554 555 for (i = BPF_REG_0; i <= BPF_REG_5; i++) 556 e->reg2expr[i] = UNKNOWN_EXPR_ID; 557 } 558 559 static u32 spill_spi(struct bpf_insn *insn) 560 { 561 return -insn->off / BPF_REG_SIZE - 1; 562 } 563 564 static u32 off_to_reg(struct bpf_insn *insn) 565 { 566 return spill_spi(insn) + MAX_BPF_REG; 567 } 568 569 static bool is_spill_off(int off) 570 { 571 return off % BPF_REG_SIZE == 0 && 572 off <= -BPF_REG_SIZE && 573 off >= -MAX_BPF_STACK_JIT; 574 } 575 576 static void mark_opaque(struct env *e, int off, int size) 577 { 578 int b, spi; 579 580 for (b = off; b < off + size; b++) { 581 if (b >= 0 || b < -MAX_BPF_STACK_JIT) 582 continue; 583 spi = (-b - 1) / BPF_REG_SIZE; 584 e->reg2expr[MAX_BPF_REG + spi] = OPAQUE_EXPR_ID; 585 } 586 } 587 588 static int mk_spill(struct scev *scev, u8 size, int id) 589 { 590 switch (size) { 591 case BPF_B: return expr1(scev, SPILL8, id); 592 case BPF_H: return expr1(scev, SPILL16, id); 593 case BPF_W: return expr1(scev, SPILL32, id); 594 case BPF_DW: return id; 595 } 596 return UNKNOWN_EXPR_ID; 597 } 598 599 static int mk_fill(struct scev *scev, int id, u8 code) 600 { 601 bool sx = BPF_MODE(code) == BPF_MEMSX; 602 603 #ifdef __BIG_ENDIAN 604 /* A narrow fill from a DW spill reads high bits on big-endian. */ 605 if (BPF_SIZE(code) != BPF_DW) 606 return OPAQUE_EXPR_ID; 607 #endif 608 609 switch (BPF_SIZE(code)) { 610 case BPF_B: return expr1(scev, sx ? SEXT8 : ZEXT8, id); 611 case BPF_H: return expr1(scev, sx ? SEXT16 : ZEXT16, id); 612 case BPF_W: return expr1(scev, sx ? SEXT32 : ZEXT32, id); 613 case BPF_DW: return sx ? UNKNOWN_EXPR_ID : id; /* DW sign-extended load is invalid */ 614 } 615 return UNKNOWN_EXPR_ID; 616 } 617 618 static int maybe_store_fp(struct scev *scev, struct env *e, struct bpf_insn *insn, int id) 619 { 620 u8 size = BPF_SIZE(insn->code); 621 622 if (insn->dst_reg != BPF_REG_FP) 623 return 0; 624 if (is_spill_off(insn->off)) 625 return replace_reg(scev, e, off_to_reg(insn), mk_spill(scev, size, id)); 626 mark_opaque(e, insn->off, bpf_size_to_bytes(size)); 627 return 0; 628 } 629 630 static int maybe_load_fp(struct scev *scev, struct env *e, struct bpf_insn *insn) 631 { 632 int id; 633 634 if (insn->src_reg == BPF_REG_FP && is_spill_off(insn->off)) 635 id = mk_fill(scev, e->reg2expr[off_to_reg(insn)], insn->code); 636 else 637 id = OPAQUE_EXPR_ID; 638 return replace_reg(scev, e, insn->dst_reg, id); 639 } 640 641 static int transfer(struct bpf_verifier_env *env, struct env *e, int idx) 642 { 643 const bool little_endian = htons(0x3412) == 0x1234; 644 struct bpf_insn *insn = &env->prog->insnsi[idx]; 645 struct scev *scev = env->scev; 646 u32 *reg2expr = e->reg2expr; 647 u8 class = BPF_CLASS(insn->code); 648 u8 x_or_k = BPF_SRC(insn->code); 649 u8 opcode = BPF_OP(insn->code); 650 u8 mode = BPF_MODE(insn->code); 651 u32 dst = insn->dst_reg; 652 u32 src = insn->src_reg; 653 u32 op, sext; 654 bool need_bswap; 655 int i, id; 656 s64 imm; 657 658 switch (class) { 659 case BPF_ALU: 660 case BPF_ALU64: 661 switch (opcode) { 662 case BPF_MOV: 663 switch (insn->off) { 664 case 0: sext = 0; break; 665 case 8: sext = SEXT8; break; 666 case 16: sext = SEXT16; break; 667 case 32: sext = SEXT32; break; 668 default: 669 goto mark_dst_unknown; 670 } 671 672 if (x_or_k == BPF_X && insn->imm == 0) 673 id = reg2expr[src]; 674 else if (x_or_k == BPF_K && src == 0 && insn->off == 0) 675 id = imm_expr(scev, insn->imm); 676 else 677 goto mark_dst_unknown; 678 679 if (sext) 680 id = expr1(scev, sext, id); 681 if (class == BPF_ALU) 682 id = expr1(scev, ZEXT32, id); 683 684 return replace_reg(scev, e, dst, id); 685 686 case BPF_ADD: 687 case BPF_SUB: 688 case BPF_MUL: 689 case BPF_DIV: 690 case BPF_MOD: 691 case BPF_OR: 692 case BPF_XOR: 693 case BPF_AND: 694 case BPF_LSH: 695 case BPF_RSH: 696 case BPF_ARSH: 697 if (opcode == BPF_DIV && insn->off == 1) 698 op = SDIV; 699 else if (opcode == BPF_MOD && insn->off == 1) 700 op = SMOD; 701 else if (insn->off == 0) 702 op = opcode; 703 else 704 goto mark_dst_unknown; 705 706 if (x_or_k == BPF_X && insn->imm == 0) 707 id = reg2expr[src]; 708 else if (x_or_k == BPF_K && src == 0) 709 id = imm_expr(scev, insn->imm); 710 else 711 goto mark_dst_unknown; 712 713 id = expr2(scev, op, reg2expr[dst], id); 714 715 if (class == BPF_ALU) 716 id = expr1(scev, ZEXT32, id); 717 718 return replace_reg(scev, e, dst, id); 719 720 case BPF_NEG: 721 if (src == 0 && insn->off == 0 && insn->imm == 0) 722 id = expr1(scev, BPF_NEG, reg2expr[dst]); 723 else 724 goto mark_dst_unknown; 725 726 if (class == BPF_ALU) 727 id = expr1(scev, ZEXT32, id); 728 729 return replace_reg(scev, e, dst, id); 730 731 case BPF_END: 732 if (src != 0 || insn->off != 0 || (class == BPF_ALU64 && x_or_k != 0)) 733 goto mark_dst_unknown; 734 735 need_bswap = class == BPF_ALU64 || ((x_or_k == BPF_TO_LE) != little_endian); 736 switch (insn->imm) { 737 case 16: op = need_bswap ? BSWAP16 : ZEXT16; break; 738 case 32: op = need_bswap ? BSWAP32 : ZEXT32; break; 739 case 64: op = need_bswap ? BSWAP64 : 0; break; 740 default: 741 goto mark_dst_unknown; 742 } 743 744 id = reg2expr[dst]; 745 if (op) 746 id = expr1(scev, op, reg2expr[dst]); 747 748 return replace_reg(scev, e, dst, id); 749 default: 750 goto mark_dst_unknown; 751 } 752 break; 753 case BPF_LDX: 754 switch (mode) { 755 case BPF_MEM: 756 case BPF_MEMSX: 757 return maybe_load_fp(scev, e, insn); 758 default: 759 goto mark_dst_unknown; 760 } 761 case BPF_STX: 762 switch (mode) { 763 case BPF_MEM: 764 return maybe_store_fp(scev, e, insn, reg2expr[src]); 765 case BPF_ATOMIC: 766 if (insn->imm == BPF_LOAD_ACQ) 767 return maybe_load_fp(scev, e, insn); 768 if (insn->imm == BPF_STORE_REL) { 769 return maybe_store_fp(scev, e, insn, reg2expr[src]); 770 } 771 /* 772 * verifier does not track other atomic ops precisely, 773 * hence mark the results as opaque. 774 */ 775 if (insn->dst_reg == BPF_REG_FP) 776 mark_opaque(e, insn->off, bpf_size_to_bytes(BPF_SIZE(insn->code))); 777 if (insn->imm == BPF_CMPXCHG) 778 return replace_reg(scev, e, BPF_REG_0, OPAQUE_EXPR_ID); 779 if (insn->imm & BPF_FETCH) 780 return replace_reg(scev, e, src, OPAQUE_EXPR_ID); 781 break; 782 } 783 break; 784 case BPF_ST: 785 if (insn->dst_reg == BPF_REG_FP) { 786 id = imm_expr(scev, insn->imm); 787 if (id < 0) 788 return id; 789 return maybe_store_fp(scev, e, insn, id); 790 } 791 break; 792 case BPF_JMP: 793 case BPF_JMP32: 794 if (opcode == BPF_CALL) 795 forget_call_regs(e); 796 /* for non-CALL there are no changes in register states */ 797 break; 798 case BPF_LD: 799 switch (mode) { 800 case BPF_IMM: 801 /* rX = imm ll */ 802 if (BPF_SIZE(insn->code) == BPF_DW && insn->src_reg == 0) { 803 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm; 804 return replace_reg(scev, e, dst, imm_expr(scev, imm)); 805 } 806 /* map, map value, BTF id, function */ 807 if (BPF_SIZE(insn->code) == BPF_DW) 808 return replace_reg(scev, e, dst, OPAQUE_EXPR_ID); 809 goto mark_dst_unknown; 810 case BPF_ABS: 811 case BPF_IND: 812 forget_call_regs(e); 813 break; 814 default: 815 goto mark_dst_unknown; 816 } 817 break; 818 default: 819 /* unknown instruction, nuke state */ 820 for (i = 0; i < REGS_NUM; i++) 821 reg2expr[i] = UNKNOWN_EXPR_ID; 822 break; 823 } 824 return 0; 825 826 mark_dst_unknown: 827 reg2expr[dst] = UNKNOWN_EXPR_ID; 828 return 0; 829 } 830 831 /* 832 * Construct minimal 'ANY' expression by traversing 'a' and 'b' 833 * and accumulating non-duplicated non-ANY entries. 834 */ 835 static int mk_any(struct scev *scev, int a, int b) 836 { 837 struct expr_stack_elt *elt; 838 struct expr *expr; 839 u32 i, j, ids_buf_sz; 840 u32 roots[2] = {a, b}; 841 int id; 842 843 if (a < 0) 844 return a; 845 if (b < 0) 846 return b; 847 ids_buf_sz = 0; 848 for (i = 0; i < ARRAY_SIZE(roots); i++) { 849 scev->stack_sz = 0; 850 expr_stack_push(scev, roots[i]); 851 while (scev->stack_sz) { 852 elt = &scev->expr_stack[--scev->stack_sz]; 853 id = elt->id; 854 expr = &scev->exprs[elt->id]; 855 if (expr->op == ANY) { 856 if (!expr_stack_push(scev, expr->params[1]) || 857 !expr_stack_push(scev, expr->params[0])) 858 return UNKNOWN_EXPR_ID; 859 } else { 860 for (j = 0; j < ids_buf_sz; j++) { 861 if (same_exprs(scev, scev->ids_buf[j], id)) 862 goto next; 863 } 864 if (ids_buf_sz == ARRAY_SIZE(scev->ids_buf)) 865 return UNKNOWN_EXPR_ID; 866 scev->ids_buf[ids_buf_sz++] = id; 867 } 868 next:; 869 } 870 } 871 if (WARN_ON(ids_buf_sz == 0)) 872 return -EFAULT; 873 id = scev->ids_buf[0]; 874 for (i = 1; i < ids_buf_sz; i++) { 875 id = expr2(scev, ANY, id, scev->ids_buf[i]); 876 if (id < 0) 877 return id; 878 } 879 return id; 880 } 881 882 static int join(struct scev *scev, struct env *acc, struct env *cur) 883 { 884 int i, id; 885 886 if (acc->empty) { 887 memcpy(acc, cur, sizeof(*acc)); 888 acc->empty = false; 889 return 0; 890 } 891 892 for (i = 0; i < REGS_NUM; i++) { 893 if (!same_exprs(scev, acc->reg2expr[i], cur->reg2expr[i])) { 894 id = mk_any(scev, acc->reg2expr[i], cur->reg2expr[i]); 895 if (id < 0) 896 return id; 897 acc->reg2expr[i] = id; 898 } 899 } 900 return 0; 901 } 902 903 /* Mark any register modified in 'e' as unknown in 'acc'. */ 904 static void forget_modified_regs(struct scev *scev, struct env *acc, struct env *e) 905 { 906 u32 i, reg; 907 908 for (i = 0; i < REGS_NUM; i++) { 909 if (e && is_reg(scev, e->reg2expr[i], ®) && reg == i) 910 continue; 911 acc->reg2expr[i] = UNKNOWN_EXPR_ID; 912 } 913 } 914 915 /* For a loop H at `header`, mark any register modified as a result of H execution as unknown. */ 916 static void forget_non_invariants(struct bpf_verifier_env *env, struct env *acc, int header) 917 { 918 struct bpf_insn_aux_data *aux = env->insn_aux_data; 919 struct bpf_loop *loop = aux[header].loop; 920 struct scev *scev = env->scev; 921 int i, idx, h; 922 923 acc->empty = false; 924 forget_modified_regs(scev, acc, find_header_env(scev, header)); 925 for (i = 0; i < loop->exits_cnt; i++) { 926 idx = loop->exits[i].from; 927 h = bpf_loop_at_index(env, idx); 928 /* 929 * In order to account for situations like this: 930 * 931 * header: 932 * do { 933 * saved = rX; 934 * rX = -1000; 935 * do { // H 936 * if (random()) 937 * goto out; // E 938 * } while (inner_again); 939 * rX = saved; 940 * } while (outer_again); 941 * out: 942 * 943 * For exits originating in nested loops check that rX is invariant 944 * both at the header (H) and at exit (E). 945 */ 946 while (h != header) { 947 forget_modified_regs(scev, acc, find_header_env(scev, h)); 948 forget_modified_regs(scev, acc, find_loop_env(scev, h, idx)); 949 idx = h; 950 h = aux[h].loop_header; 951 } 952 /* 953 * For exits originating at the same loop the header is already accounted for, 954 * check only the exit environment. 955 */ 956 forget_modified_regs(scev, acc, find_loop_env(scev, header, idx)); 957 } 958 } 959 960 /* Order worklist in reverse post-order. */ 961 static bool reverse_postorder_less(const void *a, const void *b, void *arg) 962 { 963 const int *rank = arg; 964 965 return rank[*(const int *)a] > rank[*(const int *)b]; 966 } 967 968 static const struct min_heap_callbacks worklist_cb = { 969 .less = reverse_postorder_less, 970 }; 971 972 static int worklist_push(struct bpf_verifier_env *env, int loop_header, int idx) 973 { 974 struct scev *scev = env->scev; 975 struct scev_worklist *worklist = &scev->worklist; 976 u32 tag = (u32)loop_header + 1; 977 978 if (scev->discovered[idx] == tag) 979 return 0; 980 981 if (min_heap_full_inline(worklist)) { 982 size_t size = worklist->size ? worklist->size * 2 : 16; 983 int *data; 984 985 data = kvrealloc(worklist->data, array_size(size, sizeof(*data)), 986 GFP_KERNEL_ACCOUNT); 987 if (!data) 988 return -ENOMEM; 989 worklist->data = data; 990 worklist->size = size; 991 } 992 if (!min_heap_push_inline(worklist, &idx, &worklist_cb, env->cfg.postorder_nums)) 993 return -EFAULT; 994 995 scev->discovered[idx] = tag; 996 return 0; 997 } 998 999 static bool reg_alive_at_succ(struct bpf_verifier_env *env, u32 r, u32 insn_idx) 1000 { 1001 struct bpf_iarray *succ = bpf_insn_successors(env, insn_idx); 1002 u32 i; 1003 1004 for (i = 0; i < succ->cnt; i++) 1005 if (reg_alive_at(env, r, succ->items[i])) 1006 return true; 1007 return false; 1008 } 1009 1010 enum changes_at { 1011 LOG_AT_TRANSFER, 1012 LOG_AT_JOIN, 1013 }; 1014 1015 static void log_env_changes(struct bpf_verifier_env *env, enum changes_at at, 1016 struct env *old, struct env *new, int insn_idx) 1017 { 1018 struct bpf_verifier_log *log = &env->log; 1019 struct scev *scev = env->scev; 1020 u64 null_pos = log->end_pos; 1021 u32 old_id, new_id, regno; 1022 bool any_changes = false; 1023 bool is_self_scev; 1024 u64 len; 1025 int r; 1026 1027 bpf_log(log, "%s %4d: ", at == LOG_AT_TRANSFER ? "t" : "j", insn_idx); 1028 bpf_verbose_insn(env, &env->prog->insnsi[insn_idx]); 1029 len = log->end_pos - null_pos; 1030 bpf_log(log, "%*s", max(37 - (int)len, 1), " "); 1031 bpf_log(log, " ; "); 1032 for (r = 0; r < REGS_NUM; r++) { 1033 old_id = old->reg2expr[r]; 1034 new_id = new->reg2expr[r]; 1035 if (at == LOG_AT_TRANSFER && !reg_alive_at_succ(env, r, insn_idx)) 1036 continue; 1037 if (at == LOG_AT_JOIN && !reg_alive_at(env, r, insn_idx)) 1038 continue; 1039 if (same_exprs(scev, old_id, new_id)) 1040 continue; 1041 is_self_scev = is_reg(scev, new_id, ®no) && r == regno; 1042 if (old->empty && is_self_scev) 1043 continue; 1044 if (any_changes) 1045 bpf_log(log, ", "); 1046 log_reg(env, r); 1047 bpf_log(log, " "); 1048 log_expr(env, old_id); 1049 bpf_log(log, " -> "); 1050 log_expr(env, new_id); 1051 any_changes = true; 1052 } 1053 if (old->empty && !any_changes) 1054 bpf_log(log, "<empty join>"); 1055 bpf_log(log, "\n"); 1056 if (!old->empty && !any_changes) 1057 bpf_vlog_reset(log, null_pos); 1058 } 1059 1060 static bool is_probe_read_helper(u32 func_id) 1061 { 1062 return func_id == BPF_FUNC_probe_read || 1063 func_id == BPF_FUNC_probe_read_kernel || 1064 func_id == BPF_FUNC_probe_read_user || 1065 func_id == BPF_FUNC_probe_read_str || 1066 func_id == BPF_FUNC_probe_read_kernel_str || 1067 func_id == BPF_FUNC_probe_read_user_str; 1068 } 1069 1070 /* 1071 * If instruction is an indirect write to stack, invalidate SCEVs for spi's 1072 * that this instruction can touch. 1073 */ 1074 static void reset_scevs_at_indirect_writes(struct bpf_verifier_env *env, struct env *cur_env, int idx) 1075 { 1076 struct bpf_insn *insn = &env->prog->insnsi[idx]; 1077 struct scev *scev = env->scev; 1078 u8 class = BPF_CLASS(insn->code); 1079 const unsigned long *mask; 1080 u32 spi, reg; 1081 bool opaque; 1082 1083 /* Direct fp stores are fine. */ 1084 if ((class == BPF_ST || class == BPF_STX) && insn->dst_reg == BPF_REG_FP) 1085 return; 1086 1087 mask = bpf_may_write_mask(env, idx); 1088 opaque = bpf_helper_call(insn) && is_probe_read_helper(insn->imm); 1089 for_each_set_bit(spi, mask, MAX_BPF_STACK_SLOTS) { 1090 reg = MAX_BPF_REG + spi; 1091 if (cur_env->reg2expr[reg] == UNKNOWN_EXPR_ID) 1092 continue; 1093 replace_reg(scev, cur_env, reg, opaque ? OPAQUE_EXPR_ID : UNKNOWN_EXPR_ID); 1094 } 1095 } 1096 1097 /* Find the topmost loop header containing idx inside cur_header, or -1 if none. */ 1098 static int topmost_nested_loop(struct bpf_verifier_env *env, int idx, int cur_header) 1099 { 1100 struct bpf_insn_aux_data *aux = env->insn_aux_data; 1101 int header; 1102 1103 for (header = bpf_loop_at_index(env, idx); header >= 0; 1104 header = aux[header].loop_header) 1105 if (aux[header].loop_header == cur_header) 1106 return header; 1107 1108 return -1; 1109 } 1110 1111 /* 1112 * Join cur_env into the successor's environment and schedule their traversal. 1113 * Map successors in nested loops to their topmost nested header. 1114 * Ignore successors outside the current loop and its nested loops. 1115 */ 1116 static int join_successor(struct bpf_verifier_env *env, int cur_header, int succ_idx, 1117 struct env *old_env, struct env *cur_env) 1118 { 1119 bool log_level2 = env->log.level & BPF_LOG_LEVEL2; 1120 struct scev *scev = env->scev; 1121 int err, nested_header; 1122 struct env *succ_env; 1123 1124 /* 1125 * There are several possibilities for a successor: 1126 * - succ_idx can be a part of a loop outside of the cur_header's loop, 1127 * such edges are ignored. 1128 * - succ_idx can be a part of the same loop as cur_header, 1129 * for such edges succ_idx environment is updated: 1130 * e[succ_idx] = join(e[succ_idx], cur_env) 1131 * - succ_idx can be a part of some loop inner to cur_header, 1132 * in such a case there exists some loop header H, 1133 * such that H.loop_header == cur_header 1134 * and H is the same as succ_idx's loop or contains it. 1135 */ 1136 if (bpf_loop_at_index(env, succ_idx) != cur_header) { 1137 /* 1138 * topmost_nested_loop() either finds H or returns -1, 1139 * in case if succ_idx is a part of a loop outer to cur_header. 1140 */ 1141 nested_header = topmost_nested_loop(env, succ_idx, cur_header); 1142 if (nested_header < 0) 1143 return 0; 1144 succ_idx = nested_header; 1145 } 1146 succ_env = get_loop_env(scev, cur_header, succ_idx); 1147 if (!succ_env) 1148 return -ENOMEM; 1149 if (log_level2) 1150 memcpy(old_env, succ_env, sizeof(*old_env)); 1151 err = join(scev, succ_env, cur_env); 1152 if (err) 1153 return err; 1154 err = worklist_push(env, cur_header, succ_idx); 1155 if (err) 1156 return err; 1157 if (log_level2) 1158 log_env_changes(env, LOG_AT_JOIN, old_env, succ_env, succ_idx); 1159 return 0; 1160 } 1161 1162 /* Unsupported loops get only an unknown header environment. */ 1163 static bool can_compute_loop_scev(const struct bpf_loop *loop) 1164 { 1165 return !loop->irreducible && !loop->exits_overflow; 1166 } 1167 1168 static int compute_scev_for_loop(struct bpf_verifier_env *env, int cur_header) 1169 { 1170 struct scev_worklist *worklist = &env->scev->worklist; 1171 struct bpf_insn_aux_data *aux = env->insn_aux_data; 1172 struct bpf_loop *cur_loop = aux[cur_header].loop; 1173 struct env *header_env; 1174 struct scev *scev = env->scev; 1175 struct bpf_loop *nested_loop; 1176 struct env *cur_env = NULL; 1177 struct env *old_env = NULL; 1178 struct bpf_iarray *succ; 1179 bool log_level2 = env->log.level & BPF_LOG_LEVEL2; 1180 int s, i, err, idx, succ_idx; 1181 1182 if (log_level2) 1183 bpf_log(&env->log, "Computing SCEV for loop at %d:\n", cur_header); 1184 1185 /* 1186 * For irreducible loops, and for loops nesting a loop with a truncated 1187 * exit list, just assume that everything is clobbered for now. 1188 */ 1189 if (!can_compute_loop_scev(cur_loop)) { 1190 header_env = get_loop_env(scev, cur_header, cur_header); 1191 if (!header_env) 1192 return -ENOMEM; 1193 /* The freshly allocated environment has all expressions unknown. */ 1194 header_env->empty = false; 1195 return 0; 1196 } 1197 1198 cur_env = kzalloc(sizeof(*cur_env), GFP_KERNEL_ACCOUNT); 1199 if (!cur_env) 1200 goto nomem; 1201 if (log_level2) { 1202 old_env = kzalloc(sizeof(*old_env), GFP_KERNEL_ACCOUNT); 1203 if (!old_env) 1204 goto nomem; 1205 } 1206 header_env = get_loop_env(scev, cur_header, cur_header); 1207 if (!header_env) 1208 goto nomem; 1209 err = setup_initial_loop_env(env, header_env, cur_header); 1210 if (err) 1211 goto out; 1212 err = worklist_push(env, cur_header, cur_header); 1213 if (err) 1214 goto out; 1215 1216 while (worklist->nr) { 1217 idx = *min_heap_peek_inline(worklist); 1218 min_heap_pop_inline(worklist, &worklist_cb, env->cfg.postorder_nums); 1219 1220 /* join_successor() maps nested-loop entries to their representative header. */ 1221 nested_loop = idx != cur_header ? aux[idx].loop : NULL; 1222 memcpy(cur_env, find_loop_env(scev, cur_header, idx), sizeof(*cur_env)); 1223 if (nested_loop) { 1224 /* 1225 * Process nested loop as a single instruction by 1226 * forgetting anything non-invariant in the nested loop 1227 */ 1228 if (log_level2) 1229 memcpy(old_env, cur_env, sizeof(*old_env)); 1230 forget_non_invariants(env, cur_env, idx); 1231 if (log_level2) 1232 log_env_changes(env, LOG_AT_TRANSFER, old_env, cur_env, idx); 1233 /* 1234 * Treat nested loop exits as successors, 1235 * join cur_env into successor's envs. 1236 */ 1237 for (i = 0; i < nested_loop->exits_cnt; i++) { 1238 s = nested_loop->exits[i].to; 1239 err = join_successor(env, cur_header, s, old_env, cur_env); 1240 if (err) 1241 goto out; 1242 } 1243 } else { 1244 /* 1245 * Iterate instructions within a single basic block 1246 * starting at 'idx' mutating 'cur_env'. 1247 */ 1248 for (;;) { 1249 if (log_level2) 1250 memcpy(old_env, cur_env, sizeof(*old_env)); 1251 err = transfer(env, cur_env, idx); 1252 if (err) 1253 goto out; 1254 reset_scevs_at_indirect_writes(env, cur_env, idx); 1255 if (log_level2) 1256 log_env_changes(env, LOG_AT_TRANSFER, old_env, cur_env, idx); 1257 succ = bpf_insn_successors(env, idx); 1258 if (succ->cnt != 1) 1259 break; 1260 succ_idx = succ->items[0]; 1261 if (aux[idx].bb_end || aux[succ_idx].need_scev || 1262 bpf_loop_at_index(env, succ_idx) != cur_header) 1263 break; 1264 idx = succ_idx; 1265 } 1266 /* Join cur_env into basic block successor's envs. */ 1267 iarray_for_each(s, succ) { 1268 err = join_successor(env, cur_header, s, old_env, cur_env); 1269 if (err) 1270 goto out; 1271 } 1272 } 1273 } 1274 1275 err = 0; 1276 out: 1277 kfree(cur_env); 1278 kfree(old_env); 1279 return err; 1280 nomem: 1281 err = -ENOMEM; 1282 goto out; 1283 } 1284 1285 static void mark_latches(struct bpf_verifier_env *env) 1286 { 1287 struct bpf_insn_aux_data *aux = env->insn_aux_data; 1288 struct bpf_loop *loop; 1289 int len = env->prog->len; 1290 int i, j, k, from; 1291 1292 for (i = 0; i < len; i++) { 1293 loop = aux[i].loop; 1294 if (!loop) 1295 continue; 1296 aux[i].need_scev = true; 1297 if (!can_compute_loop_scev(loop)) 1298 continue; 1299 /* 1300 * Make sure to only set .need_scev for exits and latches 1301 * belonging to the loop at `i`. If can_compute_loop_scev() 1302 * fails for a loop, it should hide it's instructions from 1303 * compute_insn_scevs(). 1304 */ 1305 for (j = 0; j < loop->backedges_cnt; j++) 1306 for (k = 0; k < loop->backedges[j].latches_cnt; k++) 1307 aux[loop->backedges[j].latches[k]].need_scev = true; 1308 for (j = 0; j < loop->exits_cnt; j++) { 1309 from = loop->exits[j].from; 1310 if (bpf_loop_at_index(env, from) == i) 1311 aux[from].need_scev = true; 1312 } 1313 } 1314 } 1315 1316 static bool is_any_imm_reg_opaque(struct scev *scev, u32 id) 1317 { 1318 u32 l, r, reg, order; 1319 s64 imm; 1320 1321 scev->stack_sz = 0; 1322 expr_stack_push(scev, id); 1323 while (expr_next(scev, &id, &order)) { 1324 if (order & DEPTH_LIMIT) 1325 return false; 1326 if (!(order & PRE) || 1327 is_imm(scev, id, &imm) || 1328 is_reg(scev, id, ®) || 1329 is_opaque(scev, id) || 1330 is_any(scev, id, &l, &r)) 1331 continue; 1332 return false; 1333 } 1334 return true; 1335 } 1336 1337 /* 1338 * Can implement explicit stack version, but it is harder to read. 1339 * Stick with recursive version for now. 1340 */ 1341 static int transform_expr_once(struct scev *scev, u32 lvl, u32 root, void *priv, 1342 int (*fn)(struct scev *scev, u32 id, void *priv)) 1343 { 1344 struct expr expr; 1345 int p0, p1, id; 1346 1347 if (lvl >= EXPR_STACK_DEPTH) 1348 return UNKNOWN_EXPR_ID; 1349 1350 expr = scev->exprs[root]; /* snapshot the expr before potential realloc */ 1351 switch (op_params_num(expr.op)) { 1352 case 0: 1353 id = root; 1354 break; 1355 case 1: 1356 p0 = transform_expr_once(scev, lvl + 1, expr.params[0], priv, fn); 1357 id = expr1(scev, expr.op, p0); 1358 break; 1359 case 2: 1360 p0 = transform_expr_once(scev, lvl + 1, expr.params[0], priv, fn); 1361 p1 = transform_expr_once(scev, lvl + 1, expr.params[1], priv, fn); 1362 id = expr2(scev, expr.op, p0, p1); 1363 break; 1364 } 1365 return id < 0 ? id : fn(scev, id, priv); 1366 } 1367 1368 static int transform_expr(struct scev *scev, u32 root, void *priv, 1369 int (*fn)(struct scev *scev, u32 id, void *priv)) 1370 { 1371 int i = 0, id_old, id_new = root; 1372 1373 do { 1374 /* 1375 * The depth limit is somewhat arbitrary and is essentially a failsafe. 1376 * oscillation should not really happen. Still, it seems harsh to error out. 1377 */ 1378 if (i++ == 4 * EXPR_STACK_DEPTH) 1379 return UNKNOWN_EXPR_ID; 1380 id_old = id_new; 1381 id_new = transform_expr_once(scev, 0, id_old, priv, fn); 1382 if (id_new < 0) 1383 return id_new; 1384 } while (id_old != id_new); 1385 return id_new; 1386 } 1387 1388 static int simplify(struct scev *scev, u32 id, void *priv) 1389 { 1390 u32 l, r, base, slope; 1391 s64 imm1, imm2; 1392 1393 /* (+ (linear base slope) imm) -> (linear (+ base imm) slope) */ 1394 if (is_add(scev, id, &l, &r) && 1395 is_linear(scev, l, &base, &slope) && 1396 is_imm(scev, r, &imm1)) 1397 return expr2(scev, LINEAR_SCEV, expr2(scev, BPF_ADD, base, r), slope); 1398 1399 /* (+ imm imm) -> imm */ 1400 if (is_add(scev, id, &l, &r) && 1401 is_imm(scev, l, &imm1) && 1402 is_imm(scev, r, &imm2)) 1403 return imm_expr(scev, imm1 + imm2); 1404 1405 /* (zext32 (imm X)) -> (imm (u32)X) */ 1406 if (is_zext32(scev, id, &l) && is_imm(scev, l, &imm1)) 1407 return imm_expr(scev, (u64)(u32)imm1); 1408 1409 return id; 1410 } 1411 1412 static int compute_header_scevs(struct bpf_verifier_env *env, struct env *header_env) 1413 { 1414 struct scev *scev = env->scev; 1415 int l, r, id, ra, rb, ra_expr; 1416 s64 imm; 1417 1418 /* 1419 * Note: 1420 * reg2expr[ra] describes a change in rA's value over a single loop iteration. 1421 * It does not account for rA's entry value. However, the SCEV constructed for rA 1422 * must include an additional rA entry edge. For example: 1423 * 1424 * r0 = ..., r1 = 7 1425 * l: if r0 == 10 goto e // reg2expr[r1] == (imm 42) => reg2scev[r1] == (any r1 42) 1426 * r0 += 1 1427 * r1 = 42 1428 * goto l 1429 * e: 1430 * ... at exit r1 is in {7,42} ... 1431 */ 1432 for (ra = 0; ra < REGS_NUM; ra++) { 1433 ra_expr = transform_expr(scev, header_env->reg2expr[ra], NULL, simplify); 1434 if (ra_expr < 0) 1435 return ra_expr; 1436 header_env->reg2expr[ra] = ra_expr; 1437 /* rA = (+ rA IMM) -> (linear rA IMM) */ 1438 if (is_add(scev, ra_expr, &l, &r) && 1439 is_reg(scev, l, &rb) && 1440 is_imm(scev, r, &imm) && 1441 ra == rb) { 1442 id = expr2(scev, LINEAR_SCEV, l, r); 1443 if (id < 0) 1444 return id; 1445 header_env->reg2scev[ra] = id; 1446 continue; 1447 } 1448 /* rA = rA -> rA*/ 1449 if (is_reg(scev, ra_expr, &rb) && ra == rb) { 1450 header_env->reg2scev[ra] = ra_expr; 1451 continue; 1452 } 1453 /* rA = (any 1 2 3 4 ...) -> (any rA 1 2 3 4 ...) */ 1454 if (is_any_imm_reg_opaque(scev, ra_expr)) { 1455 id = mk_any(scev, expr1(scev, REG, ra), ra_expr); 1456 if (id < 0) 1457 return id; 1458 header_env->reg2scev[ra] = id; 1459 continue; 1460 } 1461 1462 } 1463 return 0; 1464 } 1465 static int instantiate_header_scevs(struct scev *scev, u32 id, void *priv) 1466 { 1467 u32 reg, *reg2scev = priv; 1468 1469 /* (reg r) -> ... equation at header ... */ 1470 if (is_reg(scev, id, ®)) 1471 return reg2scev[reg]; 1472 /* keep expression shapes */ 1473 return id; 1474 } 1475 1476 static int compute_insn_scevs(struct bpf_verifier_env *env, struct env *eheader, struct env *einsn) 1477 { 1478 struct scev *scev = env->scev; 1479 int id, reg; 1480 1481 for (reg = 0; reg < REGS_NUM; reg++) { 1482 id = einsn->reg2expr[reg]; 1483 id = transform_expr_once(scev, 0, id, eheader->reg2scev, instantiate_header_scevs); 1484 if (id < 0) 1485 return id; 1486 id = transform_expr(scev, id, NULL, simplify); 1487 if (id < 0) 1488 return id; 1489 einsn->reg2scev[reg] = id; 1490 } 1491 1492 return 0; 1493 } 1494 1495 static int log_scevs(struct bpf_verifier_env *env) 1496 { 1497 struct bpf_insn_aux_data *aux = env->insn_aux_data; 1498 struct bpf_verifier_log *log = &env->log; 1499 struct env *header_env, *latch_env; 1500 struct scev *scev = env->scev; 1501 struct bpf_loop *loop; 1502 int i, j, k, len, latch; 1503 1504 len = env->prog->len; 1505 for (i = 0; i < len; i++) { 1506 loop = aux[i].loop; 1507 if (!loop) 1508 continue; 1509 header_env = find_header_env(scev, i); 1510 bpf_log(log, "scev at header %d:\n", i); 1511 print_env(env, header_env, i); 1512 if (!can_compute_loop_scev(loop)) 1513 continue; 1514 for (j = 0; j < loop->backedges_cnt; j++) { 1515 for (k = 0; k < loop->backedges[j].latches_cnt; k++) { 1516 latch = loop->backedges[j].latches[k]; 1517 bpf_log(log, " scev at %s %d:\n", k ? "exit" : "latch", latch); 1518 latch_env = find_loop_env(scev, i, latch); 1519 if (verifier_bug_if(!latch_env, env, "i=%d, latch=%d", i, latch)) 1520 return -EFAULT; 1521 print_env(env, latch_env, latch); 1522 } 1523 } 1524 } 1525 return 0; 1526 } 1527 1528 int bpf_compute_scev(struct bpf_verifier_env *env) 1529 { 1530 struct bpf_insn_aux_data *aux = env->insn_aux_data; 1531 struct scev *scev = env->scev; 1532 int *postorder = env->cfg.insn_postorder; 1533 int cnt = env->cfg.cur_postorder; 1534 int i, idx, err, header; 1535 1536 mark_latches(env); 1537 /* 1538 * Visit loop headers in postorder, to guarantee that scevs 1539 * for innermost loops are computed first. 1540 */ 1541 for (i = 0; i < cnt; i++) { 1542 idx = postorder[i]; 1543 if (!aux[idx].loop) 1544 continue; 1545 err = compute_scev_for_loop(env, idx); 1546 if (err) 1547 return err; 1548 } 1549 1550 /* 1551 * Compute scevs from exprs collected on a previous step. Iterate instructions in 1552 * reverse post-order so that each loop header is processed before instructions 1553 * reachable from it. 1554 */ 1555 for (i = cnt - 1; i >= 0; i--) { 1556 idx = postorder[i]; 1557 if (!aux[idx].need_scev) 1558 continue; 1559 header = bpf_loop_at_index(env, idx); 1560 err = aux[idx].loop 1561 ? compute_header_scevs(env, find_header_env(scev, header)) 1562 : compute_insn_scevs(env, 1563 find_header_env(scev, header), 1564 find_loop_env(scev, header, idx)); 1565 if (err) 1566 return err; 1567 } 1568 1569 for (i = 0; i < env->prog->len; i++) 1570 if (aux[i].loop) 1571 aux[i].prune_point = true; 1572 1573 if (env->log.level & BPF_LOG_LEVEL2) { 1574 err = log_scevs(env); 1575 if (err) 1576 return err; 1577 } 1578 1579 return 0; 1580 } 1581 1582 void bpf_free_scev(struct bpf_verifier_env *env) 1583 { 1584 struct scev *scev = env->scev; 1585 struct insn_envs *envs; 1586 int i; 1587 u32 j; 1588 1589 if (!scev) 1590 return; 1591 for (i = 0; i < scev->envs_cnt; i++) { 1592 envs = scev->envs[i]; 1593 if (!envs) 1594 continue; 1595 for (j = 0; j < envs->cnt; j++) 1596 kfree(envs->entries[j].env); 1597 kfree(envs); 1598 } 1599 if (scev->exprs_ht) 1600 for (i = 0; i < scev->exprs_ht_cnt; i++) 1601 kvfree(scev->exprs_ht[i]); 1602 kvfree(scev->exprs_ht); 1603 kvfree(scev->worklist.data); 1604 kvfree(scev->envs); 1605 kvfree(scev->exprs); 1606 kvfree(scev->discovered); 1607 kfree(scev); 1608 env->scev = NULL; 1609 } 1610 1611 int bpf_init_scev(struct bpf_verifier_env *env) 1612 { 1613 struct scev *scev; 1614 1615 scev = kzalloc(sizeof(struct scev), GFP_KERNEL_ACCOUNT); 1616 if (!scev) 1617 return -ENOMEM; 1618 env->scev = scev; 1619 /* A power of two for hash & (exprs_ht_cnt - 1)` indexing. */ 1620 scev->exprs_ht_cnt = roundup_pow_of_two(max(256U, DIV_ROUND_UP(env->prog->len, 4))); 1621 scev->exprs_ht = kvcalloc(scev->exprs_ht_cnt, sizeof(*scev->exprs_ht), GFP_KERNEL_ACCOUNT); 1622 if (!scev->exprs_ht) 1623 goto nomem; 1624 if (expr0(scev, UNKNOWN) < 0 || expr0(scev, OPAQUE) < 0) 1625 goto nomem; 1626 scev->envs = kvcalloc(env->prog->len, sizeof(*scev->envs), GFP_KERNEL_ACCOUNT); 1627 scev->discovered = kvcalloc(env->prog->len, sizeof(*scev->discovered), GFP_KERNEL_ACCOUNT); 1628 if (!scev->envs || !scev->discovered) 1629 goto nomem; 1630 /* 1631 * Remember original program length, in case bpf_free_scev() 1632 * is called after bpf program rewrites that increase program 1633 * length. 1634 */ 1635 scev->envs_cnt = env->prog->len; 1636 return 0; 1637 nomem: 1638 bpf_free_scev(env); 1639 return -ENOMEM; 1640 } 1641