1 // SPDX-License-Identifier: GPL-2.0-only 2 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ 3 #include <linux/bpf.h> 4 #include <linux/bpf_verifier.h> 5 #include <linux/filter.h> 6 #include <linux/bitmap.h> 7 8 #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) 9 10 /* for any branch, call, exit record the history of jmps in the given state */ 11 int bpf_push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur, 12 int insn_flags, int spi, int frame, u64 linked_regs) 13 { 14 u32 cnt = cur->jmp_history_cnt; 15 struct bpf_jmp_history_entry *p; 16 size_t alloc_size; 17 18 /* combine instruction flags if we already recorded this instruction */ 19 if (env->cur_hist_ent) { 20 /* atomic instructions push insn_flags twice, for READ and 21 * WRITE sides, but they should agree on stack slot 22 */ 23 verifier_bug_if((env->cur_hist_ent->flags & insn_flags) && 24 (env->cur_hist_ent->flags & insn_flags) != insn_flags, 25 env, "insn history: insn_idx %d cur flags %x new flags %x", 26 env->insn_idx, env->cur_hist_ent->flags, insn_flags); 27 env->cur_hist_ent->flags |= insn_flags; 28 env->cur_hist_ent->spi = spi; 29 env->cur_hist_ent->frame = frame; 30 verifier_bug_if(env->cur_hist_ent->linked_regs != 0, env, 31 "insn history: insn_idx %d linked_regs: %#llx", 32 env->insn_idx, env->cur_hist_ent->linked_regs); 33 env->cur_hist_ent->linked_regs = linked_regs; 34 return 0; 35 } 36 37 cnt++; 38 alloc_size = kmalloc_size_roundup(size_mul(cnt, sizeof(*p))); 39 p = krealloc(cur->jmp_history, alloc_size, GFP_KERNEL_ACCOUNT); 40 if (!p) 41 return -ENOMEM; 42 cur->jmp_history = p; 43 44 p = &cur->jmp_history[cnt - 1]; 45 p->idx = env->insn_idx; 46 p->prev_idx = env->prev_insn_idx; 47 p->flags = insn_flags; 48 p->spi = spi; 49 p->frame = frame; 50 p->linked_regs = linked_regs; 51 cur->jmp_history_cnt = cnt; 52 env->cur_hist_ent = p; 53 54 return 0; 55 } 56 57 static bool is_atomic_load_insn(const struct bpf_insn *insn) 58 { 59 return BPF_CLASS(insn->code) == BPF_STX && 60 BPF_MODE(insn->code) == BPF_ATOMIC && 61 insn->imm == BPF_LOAD_ACQ; 62 } 63 64 static bool is_atomic_fetch_insn(const struct bpf_insn *insn) 65 { 66 return BPF_CLASS(insn->code) == BPF_STX && 67 BPF_MODE(insn->code) == BPF_ATOMIC && 68 (insn->imm & BPF_FETCH); 69 } 70 71 /* Backtrack one insn at a time. If idx is not at the top of recorded 72 * history then previous instruction came from straight line execution. 73 * Return -ENOENT if we exhausted all instructions within given state. 74 * 75 * It's legal to have a bit of a looping with the same starting and ending 76 * insn index within the same state, e.g.: 3->4->5->3, so just because current 77 * instruction index is the same as state's first_idx doesn't mean we are 78 * done. If there is still some jump history left, we should keep going. We 79 * need to take into account that we might have a jump history between given 80 * state's parent and itself, due to checkpointing. In this case, we'll have 81 * history entry recording a jump from last instruction of parent state and 82 * first instruction of given state. 83 */ 84 static int get_prev_insn_idx(struct bpf_verifier_state *st, int i, 85 u32 *history) 86 { 87 u32 cnt = *history; 88 89 if (i == st->first_insn_idx) { 90 if (cnt == 0) 91 return -ENOENT; 92 if (cnt == 1 && st->jmp_history[0].idx == i) 93 return -ENOENT; 94 } 95 96 if (cnt && st->jmp_history[cnt - 1].idx == i) { 97 i = st->jmp_history[cnt - 1].prev_idx; 98 (*history)--; 99 } else { 100 i--; 101 } 102 return i; 103 } 104 105 static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st, 106 u32 hist_end, int insn_idx) 107 { 108 if (hist_end > 0 && st->jmp_history[hist_end - 1].idx == insn_idx) 109 return &st->jmp_history[hist_end - 1]; 110 return NULL; 111 } 112 113 static inline void bt_init(struct backtrack_state *bt, u32 frame) 114 { 115 bt->frame = frame; 116 } 117 118 static inline void bt_reset(struct backtrack_state *bt) 119 { 120 struct bpf_verifier_env *env = bt->env; 121 122 memset(bt, 0, sizeof(*bt)); 123 bt->env = env; 124 } 125 126 static inline u32 bt_empty(struct backtrack_state *bt) 127 { 128 u64 mask = 0; 129 int i; 130 131 for (i = 0; i <= bt->frame; i++) 132 mask |= bt->reg_masks[i] | bt->stack_masks[i] | bt->stack_arg_masks[i]; 133 134 return mask == 0; 135 } 136 137 static inline void bt_clear_frame_stack_arg_slot(struct backtrack_state *bt, u32 frame, u32 slot) 138 { 139 bt->stack_arg_masks[frame] &= ~(1 << slot); 140 } 141 142 static inline bool bt_is_frame_stack_arg_slot_set(struct backtrack_state *bt, u32 frame, u32 slot) 143 { 144 return bt->stack_arg_masks[frame] & (1 << slot); 145 } 146 147 static inline int bt_subprog_enter(struct backtrack_state *bt) 148 { 149 if (bt->frame == MAX_CALL_FRAMES - 1) { 150 verifier_bug(bt->env, "subprog enter from frame %d", bt->frame); 151 return -EFAULT; 152 } 153 bt->frame++; 154 return 0; 155 } 156 157 static inline int bt_subprog_exit(struct backtrack_state *bt) 158 { 159 if (bt->frame == 0) { 160 verifier_bug(bt->env, "subprog exit from frame 0"); 161 return -EFAULT; 162 } 163 bt->frame--; 164 return 0; 165 } 166 167 static inline void bt_clear_frame_reg(struct backtrack_state *bt, u32 frame, u32 reg) 168 { 169 bt->reg_masks[frame] &= ~(1 << reg); 170 } 171 172 static inline void bt_set_reg(struct backtrack_state *bt, u32 reg) 173 { 174 bpf_bt_set_frame_reg(bt, bt->frame, reg); 175 } 176 177 static inline void bt_clear_reg(struct backtrack_state *bt, u32 reg) 178 { 179 bt_clear_frame_reg(bt, bt->frame, reg); 180 } 181 182 static inline void bt_clear_frame_slot(struct backtrack_state *bt, u32 frame, u32 slot) 183 { 184 bt->stack_masks[frame] &= ~(1ull << slot); 185 } 186 187 static inline u32 bt_frame_reg_mask(struct backtrack_state *bt, u32 frame) 188 { 189 return bt->reg_masks[frame]; 190 } 191 192 static inline u32 bt_reg_mask(struct backtrack_state *bt) 193 { 194 return bt->reg_masks[bt->frame]; 195 } 196 197 static inline u64 bt_frame_stack_mask(struct backtrack_state *bt, u32 frame) 198 { 199 return bt->stack_masks[frame]; 200 } 201 202 static inline u64 bt_stack_mask(struct backtrack_state *bt) 203 { 204 return bt->stack_masks[bt->frame]; 205 } 206 207 static inline u8 bt_stack_arg_mask(struct backtrack_state *bt) 208 { 209 return bt->stack_arg_masks[bt->frame]; 210 } 211 212 static inline bool bt_is_reg_set(struct backtrack_state *bt, u32 reg) 213 { 214 return bt->reg_masks[bt->frame] & (1 << reg); 215 } 216 217 /* format registers bitmask, e.g., "r0,r2,r4" for 0x15 mask */ 218 static void fmt_reg_mask(char *buf, ssize_t buf_sz, u32 reg_mask) 219 { 220 DECLARE_BITMAP(mask, 64); 221 bool first = true; 222 int i, n; 223 224 buf[0] = '\0'; 225 226 bitmap_from_u64(mask, reg_mask); 227 for_each_set_bit(i, mask, 32) { 228 n = snprintf(buf, buf_sz, "%sr%d", first ? "" : ",", i); 229 first = false; 230 buf += n; 231 buf_sz -= n; 232 if (buf_sz < 0) 233 break; 234 } 235 } 236 /* format stack slots bitmask, e.g., "-8,-24,-40" for 0x15 mask */ 237 void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask) 238 { 239 DECLARE_BITMAP(mask, 64); 240 bool first = true; 241 int i, n; 242 243 buf[0] = '\0'; 244 245 bitmap_from_u64(mask, stack_mask); 246 for_each_set_bit(i, mask, 64) { 247 n = snprintf(buf, buf_sz, "%s%d", first ? "" : ",", -(i + 1) * 8); 248 first = false; 249 buf += n; 250 buf_sz -= n; 251 if (buf_sz < 0) 252 break; 253 } 254 } 255 256 /* For given verifier state backtrack_insn() is called from the last insn to 257 * the first insn. Its purpose is to compute a bitmask of registers and 258 * stack slots that needs precision in the parent verifier state. 259 * 260 * @idx is an index of the instruction we are currently processing; 261 * @subseq_idx is an index of the subsequent instruction that: 262 * - *would be* executed next, if jump history is viewed in forward order; 263 * - *was* processed previously during backtracking. 264 */ 265 static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx, 266 struct bpf_jmp_history_entry *hist, struct backtrack_state *bt) 267 { 268 struct bpf_insn *insn = env->prog->insnsi + idx; 269 u8 class = BPF_CLASS(insn->code); 270 u8 opcode = BPF_OP(insn->code); 271 u8 mode = BPF_MODE(insn->code); 272 u32 dreg = insn->dst_reg; 273 u32 sreg = insn->src_reg; 274 u32 spi, i, fr; 275 276 if (insn->code == 0) 277 return 0; 278 if (env->log.level & BPF_LOG_LEVEL2) { 279 fmt_reg_mask(env->tmp_str_buf, TMP_STR_BUF_LEN, bt_reg_mask(bt)); 280 verbose(env, "mark_precise: frame%d: regs=%s ", 281 bt->frame, env->tmp_str_buf); 282 bpf_fmt_stack_mask(env->tmp_str_buf, TMP_STR_BUF_LEN, bt_stack_mask(bt)); 283 verbose(env, "stack=%s before ", env->tmp_str_buf); 284 verbose(env, "%d: ", idx); 285 bpf_verbose_insn(env, insn); 286 verbose(env, "\n"); 287 } 288 289 /* If there is a history record that some registers gained range at this insn, 290 * propagate precision marks to those registers, so that bt_is_reg_set() 291 * accounts for these registers. 292 */ 293 bpf_bt_sync_linked_regs(bt, hist); 294 295 if (class == BPF_ALU || class == BPF_ALU64) { 296 if (!bt_is_reg_set(bt, dreg)) 297 return 0; 298 if (opcode == BPF_END || opcode == BPF_NEG) { 299 /* sreg is reserved and unused 300 * dreg still need precision before this insn 301 */ 302 return 0; 303 } else if (opcode == BPF_MOV) { 304 if (BPF_SRC(insn->code) == BPF_X) { 305 /* dreg = sreg or dreg = (s8, s16, s32)sreg 306 * dreg needs precision after this insn 307 * sreg needs precision before this insn 308 */ 309 bt_clear_reg(bt, dreg); 310 if (sreg != BPF_REG_FP) 311 bt_set_reg(bt, sreg); 312 } else { 313 /* dreg = K 314 * dreg needs precision after this insn. 315 * Corresponding register is already marked 316 * as precise=true in this verifier state. 317 * No further markings in parent are necessary 318 */ 319 bt_clear_reg(bt, dreg); 320 } 321 } else { 322 if (BPF_SRC(insn->code) == BPF_X) { 323 /* dreg += sreg 324 * both dreg and sreg need precision 325 * before this insn 326 */ 327 if (sreg != BPF_REG_FP) 328 bt_set_reg(bt, sreg); 329 } /* else dreg += K 330 * dreg still needs precision before this insn 331 */ 332 } 333 } else if (class == BPF_LDX || 334 is_atomic_load_insn(insn) || 335 is_atomic_fetch_insn(insn)) { 336 u32 load_reg = dreg; 337 338 /* 339 * Atomic fetch operation writes the old value into 340 * a register (sreg or r0) and if it was tracked for 341 * precision, propagate to the stack slot like we do 342 * in regular ldx. 343 */ 344 if (is_atomic_fetch_insn(insn)) 345 load_reg = insn->imm == BPF_CMPXCHG ? 346 BPF_REG_0 : sreg; 347 348 if (!bt_is_reg_set(bt, load_reg)) 349 return 0; 350 bt_clear_reg(bt, load_reg); 351 352 if (hist && hist->flags & INSN_F_STACK_ARG_ACCESS) { 353 spi = hist->spi; 354 /* 355 * Stack arg read: callee reads from r11+off, but 356 * the data lives in the caller's stack_arg_regs. 357 * Set the mask in the caller frame so precision 358 * is marked in the caller's slot at the callee 359 * entry checkpoint. 360 */ 361 bt_set_frame_stack_arg_slot(bt, bt->frame - 1, spi); 362 return 0; 363 } 364 365 /* scalars can only be spilled into stack w/o losing precision. 366 * Load from any other memory can be zero extended. 367 * The desire to keep that precision is already indicated 368 * by 'precise' mark in corresponding register of this state. 369 * No further tracking necessary. 370 */ 371 if (!hist || !(hist->flags & INSN_F_STACK_ACCESS)) 372 return 0; 373 /* dreg = *(u64 *)[fp - off] was a fill from the stack. 374 * that [fp - off] slot contains scalar that needs to be 375 * tracked with precision 376 */ 377 spi = hist->spi; 378 fr = hist->frame; 379 bpf_bt_set_frame_slot(bt, fr, spi); 380 } else if (class == BPF_STX || class == BPF_ST) { 381 if (bt_is_reg_set(bt, dreg)) 382 /* stx & st shouldn't be using _scalar_ dst_reg 383 * to access memory. It means backtracking 384 * encountered a case of pointer subtraction. 385 */ 386 return -ENOTSUPP; 387 388 if (hist && hist->flags & INSN_F_STACK_ARG_ACCESS) { 389 spi = hist->spi; 390 if (!bt_is_frame_stack_arg_slot_set(bt, bt->frame, spi)) 391 return 0; 392 bt_clear_frame_stack_arg_slot(bt, bt->frame, spi); 393 if (class == BPF_STX) 394 bt_set_reg(bt, sreg); 395 return 0; 396 } 397 398 /* scalars can only be spilled into stack */ 399 if (!hist || !(hist->flags & INSN_F_STACK_ACCESS)) 400 return 0; 401 spi = hist->spi; 402 fr = hist->frame; 403 if (!bt_is_frame_slot_set(bt, fr, spi)) 404 return 0; 405 bt_clear_frame_slot(bt, fr, spi); 406 if (class == BPF_STX) 407 bt_set_reg(bt, sreg); 408 } else if (class == BPF_JMP || class == BPF_JMP32) { 409 if (bpf_pseudo_call(insn)) { 410 int subprog_insn_idx, subprog; 411 412 subprog_insn_idx = idx + insn->imm + 1; 413 subprog = bpf_find_subprog(env, subprog_insn_idx); 414 if (subprog < 0) 415 return -EFAULT; 416 417 if (bpf_subprog_is_global(env, subprog)) { 418 /* check that jump history doesn't have any 419 * extra instructions from subprog; the next 420 * instruction after call to global subprog 421 * should be literally next instruction in 422 * caller program 423 */ 424 verifier_bug_if(idx + 1 != subseq_idx, env, 425 "extra insn from subprog"); 426 /* r1-r5 are invalidated after subprog call, 427 * so for global func call it shouldn't be set 428 * anymore 429 */ 430 if (bt_reg_mask(bt) & BPF_REGMASK_ARGS) { 431 verifier_bug(env, "global subprog unexpected regs %x", 432 bt_reg_mask(bt)); 433 return -EFAULT; 434 } 435 /* global subprog always sets R0 */ 436 bt_clear_reg(bt, BPF_REG_0); 437 return 0; 438 } else { 439 /* static subprog call instruction, which 440 * means that we are exiting current subprog, 441 * so only r1-r5 could be still requested as 442 * precise, r0 and r6-r10 or any stack slot in 443 * the current frame should be zero by now 444 */ 445 if (bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) { 446 verifier_bug(env, "static subprog unexpected regs %x", 447 bt_reg_mask(bt)); 448 return -EFAULT; 449 } 450 /* we are now tracking register spills correctly, 451 * so any instance of leftover slots is a bug 452 */ 453 if (bt_stack_mask(bt) != 0) { 454 verifier_bug(env, 455 "static subprog leftover stack slots %llx", 456 bt_stack_mask(bt)); 457 return -EFAULT; 458 } 459 /* propagate r1-r5 to the caller */ 460 for (i = BPF_REG_1; i <= BPF_REG_5; i++) { 461 if (bt_is_reg_set(bt, i)) { 462 bt_clear_reg(bt, i); 463 bpf_bt_set_frame_reg(bt, bt->frame - 1, i); 464 } 465 } 466 if (bt_stack_arg_mask(bt)) { 467 verifier_bug(env, 468 "static subprog leftover stack arg slots %x", 469 bt_stack_arg_mask(bt)); 470 return -EFAULT; 471 } 472 if (bt_subprog_exit(bt)) 473 return -EFAULT; 474 return 0; 475 } 476 } else if (bpf_is_sync_callback_calling_insn(insn) && idx != subseq_idx - 1) { 477 /* exit from callback subprog to callback-calling helper or 478 * kfunc call. Use idx/subseq_idx check to discern it from 479 * straight line code backtracking. 480 * Unlike the subprog call handling above, we shouldn't 481 * propagate precision of r1-r5 (if any requested), as they are 482 * not actually arguments passed directly to callback subprogs 483 */ 484 if (bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) { 485 verifier_bug(env, "callback unexpected regs %x", 486 bt_reg_mask(bt)); 487 return -EFAULT; 488 } 489 if (bt_stack_mask(bt) != 0) { 490 verifier_bug(env, "callback leftover stack slots %llx", 491 bt_stack_mask(bt)); 492 return -EFAULT; 493 } 494 /* clear r1-r5 in callback subprog's mask */ 495 for (i = BPF_REG_1; i <= BPF_REG_5; i++) 496 bt_clear_reg(bt, i); 497 if (bt_subprog_exit(bt)) 498 return -EFAULT; 499 return 0; 500 } else if (opcode == BPF_CALL) { 501 /* kfunc with imm==0 is invalid and fixup_kfunc_call will 502 * catch this error later. Make backtracking conservative 503 * with ENOTSUPP. 504 */ 505 if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL && insn->imm == 0) 506 return -ENOTSUPP; 507 /* regular helper call sets R0 */ 508 bt_clear_reg(bt, BPF_REG_0); 509 if (bt_reg_mask(bt) & BPF_REGMASK_ARGS) { 510 /* if backtracking was looking for registers R1-R5 511 * they should have been found already. 512 */ 513 verifier_bug(env, "backtracking call unexpected regs %x", 514 bt_reg_mask(bt)); 515 return -EFAULT; 516 } 517 if (insn->src_reg == BPF_REG_0 && insn->imm == BPF_FUNC_tail_call 518 && subseq_idx - idx != 1) { 519 if (bt_subprog_enter(bt)) 520 return -EFAULT; 521 } 522 } else if (opcode == BPF_EXIT) { 523 bool from_subprog_call, r0_precise; 524 525 /* BPF_EXIT in subprog or callback always returns 526 * right after the call instruction, so by checking 527 * whether the instruction at subseq_idx-1 is subprog 528 * call or not we can distinguish actual exit from 529 * *subprog* from exit from *callback*. In the former 530 * case, we need to propagate r0 precision, if 531 * necessary. In the former we never do that. 532 */ 533 from_subprog_call = subseq_idx - 1 >= 0 && 534 bpf_pseudo_call(&env->prog->insnsi[subseq_idx - 1]); 535 536 r0_precise = from_subprog_call && bt_is_reg_set(bt, BPF_REG_0); 537 538 /* Backtracking to a nested function call, 'idx' is a part of 539 * the inner frame 'subseq_idx' is a part of the outer frame. 540 * In case of a regular function call, instructions giving 541 * precision to registers R1-R5 should have been found already. 542 * In case of a callback from bpf_loop(), R{1,4} in the calling 543 * frame would be set as precise and that is correct. 544 */ 545 if (from_subprog_call && (bt_reg_mask(bt) & BPF_REGMASK_ARGS)) { 546 verifier_bug(env, "backtracking exit unexpected regs %x", 547 bt_reg_mask(bt)); 548 return -EFAULT; 549 } 550 551 bt_clear_reg(bt, BPF_REG_0); 552 if (bt_subprog_enter(bt)) 553 return -EFAULT; 554 555 if (r0_precise) 556 bt_set_reg(bt, BPF_REG_0); 557 /* r6-r9 and stack slots will stay set in caller frame 558 * bitmasks until we return back from callee(s) 559 */ 560 return 0; 561 } else if (BPF_SRC(insn->code) == BPF_X) { 562 if (!bt_is_reg_set(bt, dreg) && !bt_is_reg_set(bt, sreg)) 563 return 0; 564 /* dreg <cond> sreg 565 * Both dreg and sreg need precision before 566 * this insn. If only sreg was marked precise 567 * before it would be equally necessary to 568 * propagate it to dreg. 569 */ 570 if (!hist || !(hist->flags & INSN_F_SRC_REG_STACK)) 571 bt_set_reg(bt, sreg); 572 if (!hist || !(hist->flags & INSN_F_DST_REG_STACK)) 573 bt_set_reg(bt, dreg); 574 } else if (BPF_SRC(insn->code) == BPF_K) { 575 /* dreg <cond> K 576 * Only dreg still needs precision before 577 * this insn, so for the K-based conditional 578 * there is nothing new to be marked. 579 */ 580 } 581 } else if (class == BPF_LD) { 582 /* It's ld_imm64 or ld_abs or ld_ind. 583 * For ld_imm64 no further tracking of precision 584 * into parent is necessary 585 */ 586 if (mode == BPF_IMM) { 587 bt_clear_reg(bt, dreg); 588 return 0; 589 } 590 /* 591 * BPF_{IND,ABS} are modelled as two branches: 592 * - fallthrough; 593 * - implicit subprogram exit. 594 * It is necessary to switch current frame if 595 * implicit subprogram exit branch is backtracked. 596 */ 597 if (mode == BPF_IND || mode == BPF_ABS) { 598 if (bt_is_reg_set(bt, dreg)) 599 return -ENOTSUPP; 600 if (subseq_idx != idx + 1) 601 if (bt_subprog_enter(bt)) 602 return -EFAULT; 603 return 0; 604 } 605 } 606 /* Propagate precision marks to linked registers, to account for 607 * registers marked as precise in this function. 608 */ 609 bpf_bt_sync_linked_regs(bt, hist); 610 return 0; 611 } 612 613 /* the scalar precision tracking algorithm: 614 * . at the start all registers have precise=false. 615 * . scalar ranges are tracked as normal through alu and jmp insns. 616 * . once precise value of the scalar register is used in: 617 * . ptr + scalar alu 618 * . if (scalar cond K|scalar) 619 * . helper_call(.., scalar, ...) where ARG_CONST is expected 620 * backtrack through the verifier states and mark all registers and 621 * stack slots with spilled constants that these scalar registers 622 * should be precise. 623 * . during state pruning two registers (or spilled stack slots) 624 * are equivalent if both are not precise. 625 * 626 * Note the verifier cannot simply walk register parentage chain, 627 * since many different registers and stack slots could have been 628 * used to compute single precise scalar. 629 * 630 * The approach of starting with precise=true for all registers and then 631 * backtrack to mark a register as not precise when the verifier detects 632 * that program doesn't care about specific value (e.g., when helper 633 * takes register as ARG_ANYTHING parameter) is not safe. 634 * 635 * It's ok to walk single parentage chain of the verifier states. 636 * It's possible that this backtracking will go all the way till 1st insn. 637 * All other branches will be explored for needing precision later. 638 * 639 * The backtracking needs to deal with cases like: 640 * R8=map_value(id=0,off=0,ks=4,vs=1952,imm=0) R9_w=map_value(id=0,off=40,ks=4,vs=1952,imm=0) 641 * r9 -= r8 642 * r5 = r9 643 * if r5 > 0x79f goto pc+7 644 * R5_w=inv(id=0,umax_value=1951,var_off=(0x0; 0x7ff)) 645 * r5 += 1 646 * ... 647 * call bpf_perf_event_output#25 648 * where .arg5_type = ARG_MEM_SIZE_OR_ZERO 649 * 650 * and this case: 651 * r6 = 1 652 * call foo // uses callee's r6 inside to compute r0 653 * r0 += r6 654 * if r0 == 0 goto 655 * 656 * to track above reg_mask/stack_mask needs to be independent for each frame. 657 * 658 * Also if parent's curframe > frame where backtracking started, 659 * the verifier need to mark registers in both frames, otherwise callees 660 * may incorrectly prune callers. This is similar to 661 * commit 7640ead93924 ("bpf: verifier: make sure callees don't prune with caller differences") 662 * 663 * For now backtracking falls back into conservative marking. 664 */ 665 void bpf_mark_all_scalars_precise(struct bpf_verifier_env *env, 666 struct bpf_verifier_state *st) 667 { 668 struct bpf_func_state *func; 669 struct bpf_reg_state *reg; 670 int i, j; 671 672 if (env->log.level & BPF_LOG_LEVEL2) { 673 verbose(env, "mark_precise: frame%d: falling back to forcing all scalars precise\n", 674 st->curframe); 675 } 676 677 /* big hammer: mark all scalars precise in this path. 678 * pop_stack may still get !precise scalars. 679 * We also skip current state and go straight to first parent state, 680 * because precision markings in current non-checkpointed state are 681 * not needed. See why in the comment in __mark_chain_precision below. 682 */ 683 for (st = st->parent; st; st = st->parent) { 684 for (i = 0; i <= st->curframe; i++) { 685 func = st->frame[i]; 686 for (j = 0; j < BPF_REG_FP; j++) { 687 reg = &func->regs[j]; 688 if (reg->type != SCALAR_VALUE || reg->precise) 689 continue; 690 reg->precise = true; 691 if (env->log.level & BPF_LOG_LEVEL2) { 692 verbose(env, "force_precise: frame%d: forcing r%d to be precise\n", 693 i, j); 694 } 695 } 696 for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) { 697 if (!bpf_is_spilled_reg(&func->stack[j])) 698 continue; 699 reg = &func->stack[j].spilled_ptr; 700 if (reg->type != SCALAR_VALUE || reg->precise) 701 continue; 702 reg->precise = true; 703 if (env->log.level & BPF_LOG_LEVEL2) { 704 verbose(env, "force_precise: frame%d: forcing fp%d to be precise\n", 705 i, -(j + 1) * 8); 706 } 707 } 708 } 709 } 710 } 711 712 /* 713 * bpf_mark_chain_precision() backtracks BPF program instruction sequence and 714 * chain of verifier states making sure that register *regno* (if regno >= 0) 715 * and/or stack slot *spi* (if spi >= 0) are marked as precisely tracked 716 * SCALARS, as well as any other registers and slots that contribute to 717 * a tracked state of given registers/stack slots, depending on specific BPF 718 * assembly instructions (see backtrack_insns() for exact instruction handling 719 * logic). This backtracking relies on recorded jmp_history and is able to 720 * traverse entire chain of parent states. This process ends only when all the 721 * necessary registers/slots and their transitive dependencies are marked as 722 * precise. 723 * 724 * One important and subtle aspect is that precise marks *do not matter* in 725 * the currently verified state (current state). It is important to understand 726 * why this is the case. 727 * 728 * First, note that current state is the state that is not yet "checkpointed", 729 * i.e., it is not yet put into env->explored_states, and it has no children 730 * states as well. It's ephemeral, and can end up either a) being discarded if 731 * compatible explored state is found at some point or BPF_EXIT instruction is 732 * reached or b) checkpointed and put into env->explored_states, branching out 733 * into one or more children states. 734 * 735 * In the former case, precise markings in current state are completely 736 * ignored by state comparison code (see regsafe() for details). Only 737 * checkpointed ("old") state precise markings are important, and if old 738 * state's register/slot is precise, regsafe() assumes current state's 739 * register/slot as precise and checks value ranges exactly and precisely. If 740 * states turn out to be compatible, current state's necessary precise 741 * markings and any required parent states' precise markings are enforced 742 * after the fact with propagate_precision() logic, after the fact. But it's 743 * important to realize that in this case, even after marking current state 744 * registers/slots as precise, we immediately discard current state. So what 745 * actually matters is any of the precise markings propagated into current 746 * state's parent states, which are always checkpointed (due to b) case above). 747 * As such, for scenario a) it doesn't matter if current state has precise 748 * markings set or not. 749 * 750 * Now, for the scenario b), checkpointing and forking into child(ren) 751 * state(s). Note that before current state gets to checkpointing step, any 752 * processed instruction always assumes precise SCALAR register/slot 753 * knowledge: if precise value or range is useful to prune jump branch, BPF 754 * verifier takes this opportunity enthusiastically. Similarly, when 755 * register's value is used to calculate offset or memory address, exact 756 * knowledge of SCALAR range is assumed, checked, and enforced. So, similar to 757 * what we mentioned above about state comparison ignoring precise markings 758 * during state comparison, BPF verifier ignores and also assumes precise 759 * markings *at will* during instruction verification process. But as verifier 760 * assumes precision, it also propagates any precision dependencies across 761 * parent states, which are not yet finalized, so can be further restricted 762 * based on new knowledge gained from restrictions enforced by their children 763 * states. This is so that once those parent states are finalized, i.e., when 764 * they have no more active children state, state comparison logic in 765 * is_state_visited() would enforce strict and precise SCALAR ranges, if 766 * required for correctness. 767 * 768 * To build a bit more intuition, note also that once a state is checkpointed, 769 * the path we took to get to that state is not important. This is crucial 770 * property for state pruning. When state is checkpointed and finalized at 771 * some instruction index, it can be correctly and safely used to "short 772 * circuit" any *compatible* state that reaches exactly the same instruction 773 * index. I.e., if we jumped to that instruction from a completely different 774 * code path than original finalized state was derived from, it doesn't 775 * matter, current state can be discarded because from that instruction 776 * forward having a compatible state will ensure we will safely reach the 777 * exit. States describe preconditions for further exploration, but completely 778 * forget the history of how we got here. 779 * 780 * This also means that even if we needed precise SCALAR range to get to 781 * finalized state, but from that point forward *that same* SCALAR register is 782 * never used in a precise context (i.e., it's precise value is not needed for 783 * correctness), it's correct and safe to mark such register as "imprecise" 784 * (i.e., precise marking set to false). This is what we rely on when we do 785 * not set precise marking in current state. If no child state requires 786 * precision for any given SCALAR register, it's safe to dictate that it can 787 * be imprecise. If any child state does require this register to be precise, 788 * we'll mark it precise later retroactively during precise markings 789 * propagation from child state to parent states. 790 * 791 * Skipping precise marking setting in current state is a mild version of 792 * relying on the above observation. But we can utilize this property even 793 * more aggressively by proactively forgetting any precise marking in the 794 * current state (which we inherited from the parent state), right before we 795 * checkpoint it and branch off into new child state. This is done by 796 * mark_all_scalars_imprecise() to hopefully get more permissive and generic 797 * finalized states which help in short circuiting more future states. 798 */ 799 int bpf_mark_chain_precision(struct bpf_verifier_env *env, 800 struct bpf_verifier_state *starting_state, 801 int regno, 802 bool *changed) 803 { 804 struct bpf_verifier_state *st = starting_state; 805 struct backtrack_state *bt = &env->bt; 806 int first_idx = st->first_insn_idx; 807 int last_idx = starting_state->insn_idx; 808 int subseq_idx = -1; 809 struct bpf_func_state *func; 810 bool tmp, skip_first = true; 811 struct bpf_reg_state *reg; 812 int i, fr, err; 813 814 if (!env->bpf_capable) 815 return 0; 816 817 changed = changed ?: &tmp; 818 /* set frame number from which we are starting to backtrack */ 819 bt_init(bt, starting_state->curframe); 820 821 /* Do sanity checks against current state of register and/or stack 822 * slot, but don't set precise flag in current state, as precision 823 * tracking in the current state is unnecessary. 824 */ 825 func = st->frame[bt->frame]; 826 if (regno >= 0) { 827 reg = &func->regs[regno]; 828 if (reg->type != SCALAR_VALUE) { 829 verifier_bug(env, "backtracking misuse"); 830 return -EFAULT; 831 } 832 bt_set_reg(bt, regno); 833 } 834 835 if (bt_empty(bt)) 836 return 0; 837 838 for (;;) { 839 DECLARE_BITMAP(mask, 64); 840 u32 history = st->jmp_history_cnt; 841 struct bpf_jmp_history_entry *hist; 842 843 if (env->log.level & BPF_LOG_LEVEL2) { 844 verbose(env, "mark_precise: frame%d: last_idx %d first_idx %d subseq_idx %d \n", 845 bt->frame, last_idx, first_idx, subseq_idx); 846 } 847 848 if (last_idx < 0) { 849 /* we are at the entry into subprog, which 850 * is expected for global funcs, but only if 851 * requested precise registers are R1-R5 852 * (which are global func's input arguments) 853 */ 854 if (st->curframe == 0 && 855 st->frame[0]->subprogno > 0 && 856 st->frame[0]->callsite == BPF_MAIN_FUNC && 857 bt_stack_mask(bt) == 0 && 858 (bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) == 0) { 859 bitmap_from_u64(mask, bt_reg_mask(bt)); 860 for_each_set_bit(i, mask, 32) { 861 reg = &st->frame[0]->regs[i]; 862 bt_clear_reg(bt, i); 863 if (reg->type == SCALAR_VALUE) { 864 reg->precise = true; 865 *changed = true; 866 } 867 } 868 return 0; 869 } 870 871 verifier_bug(env, "backtracking func entry subprog %d reg_mask %x stack_mask %llx", 872 st->frame[0]->subprogno, bt_reg_mask(bt), bt_stack_mask(bt)); 873 return -EFAULT; 874 } 875 876 for (i = last_idx;;) { 877 if (skip_first) { 878 err = 0; 879 skip_first = false; 880 } else { 881 hist = get_jmp_hist_entry(st, history, i); 882 err = backtrack_insn(env, i, subseq_idx, hist, bt); 883 } 884 if (err == -ENOTSUPP) { 885 bpf_mark_all_scalars_precise(env, starting_state); 886 bt_reset(bt); 887 return 0; 888 } else if (err) { 889 return err; 890 } 891 if (bt_empty(bt)) 892 /* Found assignment(s) into tracked register in this state. 893 * Since this state is already marked, just return. 894 * Nothing to be tracked further in the parent state. 895 */ 896 return 0; 897 subseq_idx = i; 898 i = get_prev_insn_idx(st, i, &history); 899 if (i == -ENOENT) 900 break; 901 if (i >= env->prog->len) { 902 /* This can happen if backtracking reached insn 0 903 * and there are still reg_mask or stack_mask 904 * to backtrack. 905 * It means the backtracking missed the spot where 906 * particular register was initialized with a constant. 907 */ 908 verifier_bug(env, "backtracking idx %d", i); 909 return -EFAULT; 910 } 911 } 912 st = st->parent; 913 if (!st) 914 break; 915 916 for (fr = bt->frame; fr >= 0; fr--) { 917 func = st->frame[fr]; 918 bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr)); 919 for_each_set_bit(i, mask, 32) { 920 reg = &func->regs[i]; 921 if (reg->type != SCALAR_VALUE) { 922 bt_clear_frame_reg(bt, fr, i); 923 continue; 924 } 925 if (reg->precise) { 926 bt_clear_frame_reg(bt, fr, i); 927 } else { 928 reg->precise = true; 929 *changed = true; 930 } 931 } 932 933 bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr)); 934 for_each_set_bit(i, mask, 64) { 935 if (verifier_bug_if(i >= func->allocated_stack / BPF_REG_SIZE, 936 env, "stack slot %d, total slots %d", 937 i, func->allocated_stack / BPF_REG_SIZE)) 938 return -EFAULT; 939 940 if (!bpf_is_spilled_scalar_reg(&func->stack[i])) { 941 bt_clear_frame_slot(bt, fr, i); 942 continue; 943 } 944 reg = &func->stack[i].spilled_ptr; 945 if (reg->precise) { 946 bt_clear_frame_slot(bt, fr, i); 947 } else { 948 reg->precise = true; 949 *changed = true; 950 } 951 } 952 for (i = 0; i < func->out_stack_arg_cnt; i++) { 953 if (!bt_is_frame_stack_arg_slot_set(bt, fr, i)) 954 continue; 955 reg = &func->stack_arg_regs[i]; 956 if (reg->type != SCALAR_VALUE || reg->precise) { 957 bt_clear_frame_stack_arg_slot(bt, fr, i); 958 } else { 959 reg->precise = true; 960 *changed = true; 961 } 962 } 963 if (env->log.level & BPF_LOG_LEVEL2) { 964 fmt_reg_mask(env->tmp_str_buf, TMP_STR_BUF_LEN, 965 bt_frame_reg_mask(bt, fr)); 966 verbose(env, "mark_precise: frame%d: parent state regs=%s ", 967 fr, env->tmp_str_buf); 968 bpf_fmt_stack_mask(env->tmp_str_buf, TMP_STR_BUF_LEN, 969 bt_frame_stack_mask(bt, fr)); 970 verbose(env, "stack=%s: ", env->tmp_str_buf); 971 print_verifier_state(env, st, fr, true); 972 } 973 } 974 975 if (bt_empty(bt)) 976 return 0; 977 978 subseq_idx = first_idx; 979 last_idx = st->last_insn_idx; 980 first_idx = st->first_insn_idx; 981 } 982 983 /* if we still have requested precise regs or slots, we missed 984 * something (e.g., stack access through non-r10 register), so 985 * fallback to marking all precise 986 */ 987 if (!bt_empty(bt)) { 988 bpf_mark_all_scalars_precise(env, starting_state); 989 bt_reset(bt); 990 } 991 992 return 0; 993 } 994