projects/linux·blob master · refs

993 lines · 32.4 KiB

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 */
11int 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
57static 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
64static 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 */
84static 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
105static 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
113static inline void bt_init(struct backtrack_state *bt, u32 frame)
114{
115 bt->frame = frame;
116}
117
118static 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
126static 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
137static 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
142static 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
147static 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
157static 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
167static inline void bt_clear_frame_reg(struct backtrack_state *bt, u32 frame, u32 reg)
168{
169 bt->reg_masks[frame] &= ~(1 << reg);
170}
171
172static inline void bt_set_reg(struct backtrack_state *bt, u32 reg)
173{
174 bpf_bt_set_frame_reg(bt, bt->frame, reg);
175}
176
177static inline void bt_clear_reg(struct backtrack_state *bt, u32 reg)
178{
179 bt_clear_frame_reg(bt, bt->frame, reg);
180}
181
182static inline void bt_clear_frame_slot(struct backtrack_state *bt, u32 frame, u32 slot)
183{
184 bt->stack_masks[frame] &= ~(1ull << slot);
185}
186
187static inline u32 bt_frame_reg_mask(struct backtrack_state *bt, u32 frame)
188{
189 return bt->reg_masks[frame];
190}
191
192static inline u32 bt_reg_mask(struct backtrack_state *bt)
193{
194 return bt->reg_masks[bt->frame];
195}
196
197static inline u64 bt_frame_stack_mask(struct backtrack_state *bt, u32 frame)
198{
199 return bt->stack_masks[frame];
200}
201
202static inline u64 bt_stack_mask(struct backtrack_state *bt)
203{
204 return bt->stack_masks[bt->frame];
205}
206
207static inline u8 bt_stack_arg_mask(struct backtrack_state *bt)
208{
209 return bt->stack_arg_masks[bt->frame];
210}
211
212static 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 */
218static 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 */
237void 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 */
265static 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 */
665void 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 */
799int 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}