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