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 r0_precise; 524 525 /* Backtracking to a nested function call, 'idx' is a part of 526 * the inner frame 'subseq_idx' is a part of the outer frame. 527 * In case of a regular function call, instructions giving 528 * precision to registers R1-R5 should have been found already. 529 * In case of a callback, it is ok to have R1-R5 marked for 530 * backtracking, as these registers are set by the function 531 * invoking callback. 532 */ 533 if (subseq_idx >= 0 && bpf_calls_callback(env, subseq_idx)) 534 for (i = BPF_REG_1; i <= BPF_REG_5; i++) 535 bt_clear_reg(bt, i); 536 if (bt_reg_mask(bt) & BPF_REGMASK_ARGS) { 537 verifier_bug(env, "backtracking exit unexpected regs %x", 538 bt_reg_mask(bt)); 539 return -EFAULT; 540 } 541 542 /* BPF_EXIT in subprog or callback always returns 543 * right after the call instruction, so by checking 544 * whether the instruction at subseq_idx-1 is subprog 545 * call or not we can distinguish actual exit from 546 * *subprog* from exit from *callback*. In the former 547 * case, we need to propagate r0 precision, if 548 * necessary. In the former we never do that. 549 */ 550 r0_precise = subseq_idx - 1 >= 0 && 551 bpf_pseudo_call(&env->prog->insnsi[subseq_idx - 1]) && 552 bt_is_reg_set(bt, BPF_REG_0); 553 554 bt_clear_reg(bt, BPF_REG_0); 555 if (bt_subprog_enter(bt)) 556 return -EFAULT; 557 558 if (r0_precise) 559 bt_set_reg(bt, BPF_REG_0); 560 /* r6-r9 and stack slots will stay set in caller frame 561 * bitmasks until we return back from callee(s) 562 */ 563 return 0; 564 } else if (BPF_SRC(insn->code) == BPF_X) { 565 if (!bt_is_reg_set(bt, dreg) && !bt_is_reg_set(bt, sreg)) 566 return 0; 567 /* dreg <cond> sreg 568 * Both dreg and sreg need precision before 569 * this insn. If only sreg was marked precise 570 * before it would be equally necessary to 571 * propagate it to dreg. 572 */ 573 if (!hist || !(hist->flags & INSN_F_SRC_REG_STACK)) 574 bt_set_reg(bt, sreg); 575 if (!hist || !(hist->flags & INSN_F_DST_REG_STACK)) 576 bt_set_reg(bt, dreg); 577 } else if (BPF_SRC(insn->code) == BPF_K) { 578 /* dreg <cond> K 579 * Only dreg still needs precision before 580 * this insn, so for the K-based conditional 581 * there is nothing new to be marked. 582 */ 583 } 584 } else if (class == BPF_LD) { 585 if (!bt_is_reg_set(bt, dreg)) 586 return 0; 587 bt_clear_reg(bt, dreg); 588 /* It's ld_imm64 or ld_abs or ld_ind. 589 * For ld_imm64 no further tracking of precision 590 * into parent is necessary 591 */ 592 if (mode == BPF_IND || mode == BPF_ABS) 593 /* to be analyzed */ 594 return -ENOTSUPP; 595 } 596 /* Propagate precision marks to linked registers, to account for 597 * registers marked as precise in this function. 598 */ 599 bpf_bt_sync_linked_regs(bt, hist); 600 return 0; 601 } 602 603 /* the scalar precision tracking algorithm: 604 * . at the start all registers have precise=false. 605 * . scalar ranges are tracked as normal through alu and jmp insns. 606 * . once precise value of the scalar register is used in: 607 * . ptr + scalar alu 608 * . if (scalar cond K|scalar) 609 * . helper_call(.., scalar, ...) where ARG_CONST is expected 610 * backtrack through the verifier states and mark all registers and 611 * stack slots with spilled constants that these scalar registers 612 * should be precise. 613 * . during state pruning two registers (or spilled stack slots) 614 * are equivalent if both are not precise. 615 * 616 * Note the verifier cannot simply walk register parentage chain, 617 * since many different registers and stack slots could have been 618 * used to compute single precise scalar. 619 * 620 * The approach of starting with precise=true for all registers and then 621 * backtrack to mark a register as not precise when the verifier detects 622 * that program doesn't care about specific value (e.g., when helper 623 * takes register as ARG_ANYTHING parameter) is not safe. 624 * 625 * It's ok to walk single parentage chain of the verifier states. 626 * It's possible that this backtracking will go all the way till 1st insn. 627 * All other branches will be explored for needing precision later. 628 * 629 * The backtracking needs to deal with cases like: 630 * 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) 631 * r9 -= r8 632 * r5 = r9 633 * if r5 > 0x79f goto pc+7 634 * R5_w=inv(id=0,umax_value=1951,var_off=(0x0; 0x7ff)) 635 * r5 += 1 636 * ... 637 * call bpf_perf_event_output#25 638 * where .arg5_type = ARG_MEM_SIZE_OR_ZERO 639 * 640 * and this case: 641 * r6 = 1 642 * call foo // uses callee's r6 inside to compute r0 643 * r0 += r6 644 * if r0 == 0 goto 645 * 646 * to track above reg_mask/stack_mask needs to be independent for each frame. 647 * 648 * Also if parent's curframe > frame where backtracking started, 649 * the verifier need to mark registers in both frames, otherwise callees 650 * may incorrectly prune callers. This is similar to 651 * commit 7640ead93924 ("bpf: verifier: make sure callees don't prune with caller differences") 652 * 653 * For now backtracking falls back into conservative marking. 654 */ 655 void bpf_mark_all_scalars_precise(struct bpf_verifier_env *env, 656 struct bpf_verifier_state *st) 657 { 658 struct bpf_func_state *func; 659 struct bpf_reg_state *reg; 660 int i, j; 661 662 if (env->log.level & BPF_LOG_LEVEL2) { 663 verbose(env, "mark_precise: frame%d: falling back to forcing all scalars precise\n", 664 st->curframe); 665 } 666 667 /* big hammer: mark all scalars precise in this path. 668 * pop_stack may still get !precise scalars. 669 * We also skip current state and go straight to first parent state, 670 * because precision markings in current non-checkpointed state are 671 * not needed. See why in the comment in __mark_chain_precision below. 672 */ 673 for (st = st->parent; st; st = st->parent) { 674 for (i = 0; i <= st->curframe; i++) { 675 func = st->frame[i]; 676 for (j = 0; j < BPF_REG_FP; j++) { 677 reg = &func->regs[j]; 678 if (reg->type != SCALAR_VALUE || reg->precise) 679 continue; 680 reg->precise = true; 681 if (env->log.level & BPF_LOG_LEVEL2) { 682 verbose(env, "force_precise: frame%d: forcing r%d to be precise\n", 683 i, j); 684 } 685 } 686 for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) { 687 if (!bpf_is_spilled_reg(&func->stack[j])) 688 continue; 689 reg = &func->stack[j].spilled_ptr; 690 if (reg->type != SCALAR_VALUE || reg->precise) 691 continue; 692 reg->precise = true; 693 if (env->log.level & BPF_LOG_LEVEL2) { 694 verbose(env, "force_precise: frame%d: forcing fp%d to be precise\n", 695 i, -(j + 1) * 8); 696 } 697 } 698 } 699 } 700 } 701 702 /* 703 * bpf_mark_chain_precision() backtracks BPF program instruction sequence and 704 * chain of verifier states making sure that register *regno* (if regno >= 0) 705 * and/or stack slot *spi* (if spi >= 0) are marked as precisely tracked 706 * SCALARS, as well as any other registers and slots that contribute to 707 * a tracked state of given registers/stack slots, depending on specific BPF 708 * assembly instructions (see backtrack_insns() for exact instruction handling 709 * logic). This backtracking relies on recorded jmp_history and is able to 710 * traverse entire chain of parent states. This process ends only when all the 711 * necessary registers/slots and their transitive dependencies are marked as 712 * precise. 713 * 714 * One important and subtle aspect is that precise marks *do not matter* in 715 * the currently verified state (current state). It is important to understand 716 * why this is the case. 717 * 718 * First, note that current state is the state that is not yet "checkpointed", 719 * i.e., it is not yet put into env->explored_states, and it has no children 720 * states as well. It's ephemeral, and can end up either a) being discarded if 721 * compatible explored state is found at some point or BPF_EXIT instruction is 722 * reached or b) checkpointed and put into env->explored_states, branching out 723 * into one or more children states. 724 * 725 * In the former case, precise markings in current state are completely 726 * ignored by state comparison code (see regsafe() for details). Only 727 * checkpointed ("old") state precise markings are important, and if old 728 * state's register/slot is precise, regsafe() assumes current state's 729 * register/slot as precise and checks value ranges exactly and precisely. If 730 * states turn out to be compatible, current state's necessary precise 731 * markings and any required parent states' precise markings are enforced 732 * after the fact with propagate_precision() logic, after the fact. But it's 733 * important to realize that in this case, even after marking current state 734 * registers/slots as precise, we immediately discard current state. So what 735 * actually matters is any of the precise markings propagated into current 736 * state's parent states, which are always checkpointed (due to b) case above). 737 * As such, for scenario a) it doesn't matter if current state has precise 738 * markings set or not. 739 * 740 * Now, for the scenario b), checkpointing and forking into child(ren) 741 * state(s). Note that before current state gets to checkpointing step, any 742 * processed instruction always assumes precise SCALAR register/slot 743 * knowledge: if precise value or range is useful to prune jump branch, BPF 744 * verifier takes this opportunity enthusiastically. Similarly, when 745 * register's value is used to calculate offset or memory address, exact 746 * knowledge of SCALAR range is assumed, checked, and enforced. So, similar to 747 * what we mentioned above about state comparison ignoring precise markings 748 * during state comparison, BPF verifier ignores and also assumes precise 749 * markings *at will* during instruction verification process. But as verifier 750 * assumes precision, it also propagates any precision dependencies across 751 * parent states, which are not yet finalized, so can be further restricted 752 * based on new knowledge gained from restrictions enforced by their children 753 * states. This is so that once those parent states are finalized, i.e., when 754 * they have no more active children state, state comparison logic in 755 * is_state_visited() would enforce strict and precise SCALAR ranges, if 756 * required for correctness. 757 * 758 * To build a bit more intuition, note also that once a state is checkpointed, 759 * the path we took to get to that state is not important. This is crucial 760 * property for state pruning. When state is checkpointed and finalized at 761 * some instruction index, it can be correctly and safely used to "short 762 * circuit" any *compatible* state that reaches exactly the same instruction 763 * index. I.e., if we jumped to that instruction from a completely different 764 * code path than original finalized state was derived from, it doesn't 765 * matter, current state can be discarded because from that instruction 766 * forward having a compatible state will ensure we will safely reach the 767 * exit. States describe preconditions for further exploration, but completely 768 * forget the history of how we got here. 769 * 770 * This also means that even if we needed precise SCALAR range to get to 771 * finalized state, but from that point forward *that same* SCALAR register is 772 * never used in a precise context (i.e., it's precise value is not needed for 773 * correctness), it's correct and safe to mark such register as "imprecise" 774 * (i.e., precise marking set to false). This is what we rely on when we do 775 * not set precise marking in current state. If no child state requires 776 * precision for any given SCALAR register, it's safe to dictate that it can 777 * be imprecise. If any child state does require this register to be precise, 778 * we'll mark it precise later retroactively during precise markings 779 * propagation from child state to parent states. 780 * 781 * Skipping precise marking setting in current state is a mild version of 782 * relying on the above observation. But we can utilize this property even 783 * more aggressively by proactively forgetting any precise marking in the 784 * current state (which we inherited from the parent state), right before we 785 * checkpoint it and branch off into new child state. This is done by 786 * mark_all_scalars_imprecise() to hopefully get more permissive and generic 787 * finalized states which help in short circuiting more future states. 788 */ 789 int bpf_mark_chain_precision(struct bpf_verifier_env *env, 790 struct bpf_verifier_state *starting_state, 791 int regno, 792 bool *changed) 793 { 794 struct bpf_verifier_state *st = starting_state; 795 struct backtrack_state *bt = &env->bt; 796 int first_idx = st->first_insn_idx; 797 int last_idx = starting_state->insn_idx; 798 int subseq_idx = -1; 799 struct bpf_func_state *func; 800 bool tmp, skip_first = true; 801 struct bpf_reg_state *reg; 802 int i, fr, err; 803 804 if (!env->bpf_capable) 805 return 0; 806 807 changed = changed ?: &tmp; 808 /* set frame number from which we are starting to backtrack */ 809 bt_init(bt, starting_state->curframe); 810 811 /* Do sanity checks against current state of register and/or stack 812 * slot, but don't set precise flag in current state, as precision 813 * tracking in the current state is unnecessary. 814 */ 815 func = st->frame[bt->frame]; 816 if (regno >= 0) { 817 reg = &func->regs[regno]; 818 if (reg->type != SCALAR_VALUE) { 819 verifier_bug(env, "backtracking misuse"); 820 return -EFAULT; 821 } 822 bt_set_reg(bt, regno); 823 } 824 825 if (bt_empty(bt)) 826 return 0; 827 828 for (;;) { 829 DECLARE_BITMAP(mask, 64); 830 u32 history = st->jmp_history_cnt; 831 struct bpf_jmp_history_entry *hist; 832 833 if (env->log.level & BPF_LOG_LEVEL2) { 834 verbose(env, "mark_precise: frame%d: last_idx %d first_idx %d subseq_idx %d \n", 835 bt->frame, last_idx, first_idx, subseq_idx); 836 } 837 838 if (last_idx < 0) { 839 /* we are at the entry into subprog, which 840 * is expected for global funcs, but only if 841 * requested precise registers are R1-R5 842 * (which are global func's input arguments) 843 */ 844 if (st->curframe == 0 && 845 st->frame[0]->subprogno > 0 && 846 st->frame[0]->callsite == BPF_MAIN_FUNC && 847 bt_stack_mask(bt) == 0 && 848 (bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) == 0) { 849 bitmap_from_u64(mask, bt_reg_mask(bt)); 850 for_each_set_bit(i, mask, 32) { 851 reg = &st->frame[0]->regs[i]; 852 bt_clear_reg(bt, i); 853 if (reg->type == SCALAR_VALUE) { 854 reg->precise = true; 855 *changed = true; 856 } 857 } 858 return 0; 859 } 860 861 verifier_bug(env, "backtracking func entry subprog %d reg_mask %x stack_mask %llx", 862 st->frame[0]->subprogno, bt_reg_mask(bt), bt_stack_mask(bt)); 863 return -EFAULT; 864 } 865 866 for (i = last_idx;;) { 867 if (skip_first) { 868 err = 0; 869 skip_first = false; 870 } else { 871 hist = get_jmp_hist_entry(st, history, i); 872 err = backtrack_insn(env, i, subseq_idx, hist, bt); 873 } 874 if (err == -ENOTSUPP) { 875 bpf_mark_all_scalars_precise(env, starting_state); 876 bt_reset(bt); 877 return 0; 878 } else if (err) { 879 return err; 880 } 881 if (bt_empty(bt)) 882 /* Found assignment(s) into tracked register in this state. 883 * Since this state is already marked, just return. 884 * Nothing to be tracked further in the parent state. 885 */ 886 return 0; 887 subseq_idx = i; 888 i = get_prev_insn_idx(st, i, &history); 889 if (i == -ENOENT) 890 break; 891 if (i >= env->prog->len) { 892 /* This can happen if backtracking reached insn 0 893 * and there are still reg_mask or stack_mask 894 * to backtrack. 895 * It means the backtracking missed the spot where 896 * particular register was initialized with a constant. 897 */ 898 verifier_bug(env, "backtracking idx %d", i); 899 return -EFAULT; 900 } 901 } 902 st = st->parent; 903 if (!st) 904 break; 905 906 for (fr = bt->frame; fr >= 0; fr--) { 907 func = st->frame[fr]; 908 bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr)); 909 for_each_set_bit(i, mask, 32) { 910 reg = &func->regs[i]; 911 if (reg->type != SCALAR_VALUE) { 912 bt_clear_frame_reg(bt, fr, i); 913 continue; 914 } 915 if (reg->precise) { 916 bt_clear_frame_reg(bt, fr, i); 917 } else { 918 reg->precise = true; 919 *changed = true; 920 } 921 } 922 923 bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr)); 924 for_each_set_bit(i, mask, 64) { 925 if (verifier_bug_if(i >= func->allocated_stack / BPF_REG_SIZE, 926 env, "stack slot %d, total slots %d", 927 i, func->allocated_stack / BPF_REG_SIZE)) 928 return -EFAULT; 929 930 if (!bpf_is_spilled_scalar_reg(&func->stack[i])) { 931 bt_clear_frame_slot(bt, fr, i); 932 continue; 933 } 934 reg = &func->stack[i].spilled_ptr; 935 if (reg->precise) { 936 bt_clear_frame_slot(bt, fr, i); 937 } else { 938 reg->precise = true; 939 *changed = true; 940 } 941 } 942 for (i = 0; i < func->out_stack_arg_cnt; i++) { 943 if (!bt_is_frame_stack_arg_slot_set(bt, fr, i)) 944 continue; 945 reg = &func->stack_arg_regs[i]; 946 if (reg->type != SCALAR_VALUE || reg->precise) { 947 bt_clear_frame_stack_arg_slot(bt, fr, i); 948 } else { 949 reg->precise = true; 950 *changed = true; 951 } 952 } 953 if (env->log.level & BPF_LOG_LEVEL2) { 954 fmt_reg_mask(env->tmp_str_buf, TMP_STR_BUF_LEN, 955 bt_frame_reg_mask(bt, fr)); 956 verbose(env, "mark_precise: frame%d: parent state regs=%s ", 957 fr, env->tmp_str_buf); 958 bpf_fmt_stack_mask(env->tmp_str_buf, TMP_STR_BUF_LEN, 959 bt_frame_stack_mask(bt, fr)); 960 verbose(env, "stack=%s: ", env->tmp_str_buf); 961 print_verifier_state(env, st, fr, true); 962 } 963 } 964 965 if (bt_empty(bt)) 966 return 0; 967 968 subseq_idx = first_idx; 969 last_idx = st->last_insn_idx; 970 first_idx = st->first_insn_idx; 971 } 972 973 /* if we still have requested precise regs or slots, we missed 974 * something (e.g., stack access through non-r10 register), so 975 * fallback to marking all precise 976 */ 977 if (!bt_empty(bt)) { 978 bpf_mark_all_scalars_precise(env, starting_state); 979 bt_reset(bt); 980 } 981 982 return 0; 983 } 984