projects/linux·blob assoc-array-fixes · refs

1599 lines · 53.1 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/cnum.h>
6#include <linux/filter.h>
7
8#define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
9
10#define BPF_COMPLEXITY_LIMIT_STATES 64
11
12static bool is_may_goto_insn_at(struct bpf_verifier_env *env, int insn_idx)
13{
14 return bpf_is_may_goto_insn(&env->prog->insnsi[insn_idx]);
15}
16
17static bool is_iter_next_insn(struct bpf_verifier_env *env, int insn_idx)
18{
19 return env->insn_aux_data[insn_idx].is_iter_next;
20}
21
22static void update_peak_states(struct bpf_verifier_env *env)
23{
24 u32 cur_states;
25
26 cur_states = env->explored_states_size + env->free_list_size + env->num_backedges;
27 env->peak_states = max(env->peak_states, cur_states);
28}
29
30/* struct bpf_verifier_state->parent refers to states
31 * that are in either of env->{expored_states,free_list}.
32 * In both cases the state is contained in struct bpf_verifier_state_list.
33 */
34static struct bpf_verifier_state_list *state_parent_as_list(struct bpf_verifier_state *st)
35{
36 if (st->parent)
37 return container_of(st->parent, struct bpf_verifier_state_list, state);
38 return NULL;
39}
40
41static bool incomplete_read_marks(struct bpf_verifier_env *env,
42 struct bpf_verifier_state *st);
43
44/* A state can be freed if it is no longer referenced:
45 * - is in the env->free_list;
46 * - has no children states;
47 */
48static void maybe_free_verifier_state(struct bpf_verifier_env *env,
49 struct bpf_verifier_state_list *sl)
50{
51 if (!sl->in_free_list
52 || sl->state.branches != 0
53 || incomplete_read_marks(env, &sl->state))
54 return;
55 list_del(&sl->node);
56 bpf_free_verifier_state(&sl->state, false);
57 kfree(sl);
58 env->free_list_size--;
59}
60
61/* For state @st look for a topmost frame with frame_insn_idx() in some SCC,
62 * if such frame exists form a corresponding @callchain as an array of
63 * call sites leading to this frame and SCC id.
64 * E.g.:
65 *
66 * void foo() { A: loop {... SCC#1 ...}; }
67 * void bar() { B: loop { C: foo(); ... SCC#2 ... }
68 * D: loop { E: foo(); ... SCC#3 ... } }
69 * void main() { F: bar(); }
70 *
71 * @callchain at (A) would be either (F,SCC#2) or (F,SCC#3) depending
72 * on @st frame call sites being (F,C,A) or (F,E,A).
73 */
74static bool compute_scc_callchain(struct bpf_verifier_env *env,
75 struct bpf_verifier_state *st,
76 struct bpf_scc_callchain *callchain)
77{
78 u32 i, scc, insn_idx;
79
80 memset(callchain, 0, sizeof(*callchain));
81 for (i = 0; i <= st->curframe; i++) {
82 insn_idx = bpf_frame_insn_idx(st, i);
83 scc = env->insn_aux_data[insn_idx].scc;
84 if (scc) {
85 callchain->scc = scc;
86 break;
87 } else if (i < st->curframe) {
88 callchain->callsites[i] = insn_idx;
89 } else {
90 return false;
91 }
92 }
93 return true;
94}
95
96/* Check if bpf_scc_visit instance for @callchain exists. */
97static struct bpf_scc_visit *scc_visit_lookup(struct bpf_verifier_env *env,
98 struct bpf_scc_callchain *callchain)
99{
100 struct bpf_scc_info *info = env->scc_info[callchain->scc];
101 struct bpf_scc_visit *visits = info->visits;
102 u32 i;
103
104 if (!info)
105 return NULL;
106 for (i = 0; i < info->num_visits; i++)
107 if (memcmp(callchain, &visits[i].callchain, sizeof(*callchain)) == 0)
108 return &visits[i];
109 return NULL;
110}
111
112/* Allocate a new bpf_scc_visit instance corresponding to @callchain.
113 * Allocated instances are alive for a duration of the do_check_common()
114 * call and are freed by free_states().
115 */
116static struct bpf_scc_visit *scc_visit_alloc(struct bpf_verifier_env *env,
117 struct bpf_scc_callchain *callchain)
118{
119 struct bpf_scc_visit *visit;
120 struct bpf_scc_info *info;
121 u32 scc, num_visits;
122 u64 new_sz;
123
124 scc = callchain->scc;
125 info = env->scc_info[scc];
126 num_visits = info ? info->num_visits : 0;
127 new_sz = sizeof(*info) + sizeof(struct bpf_scc_visit) * (num_visits + 1);
128 info = kvrealloc(env->scc_info[scc], new_sz, GFP_KERNEL_ACCOUNT);
129 if (!info)
130 return NULL;
131 env->scc_info[scc] = info;
132 info->num_visits = num_visits + 1;
133 visit = &info->visits[num_visits];
134 memset(visit, 0, sizeof(*visit));
135 memcpy(&visit->callchain, callchain, sizeof(*callchain));
136 return visit;
137}
138
139/* Form a string '(callsite#1,callsite#2,...,scc)' in env->tmp_str_buf */
140static char *format_callchain(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain)
141{
142 char *buf = env->tmp_str_buf;
143 int i, delta = 0;
144
145 delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "(");
146 for (i = 0; i < ARRAY_SIZE(callchain->callsites); i++) {
147 if (!callchain->callsites[i])
148 break;
149 delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "%u,",
150 callchain->callsites[i]);
151 }
152 delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "%u)", callchain->scc);
153 return env->tmp_str_buf;
154}
155
156/* If callchain for @st exists (@st is in some SCC), ensure that
157 * bpf_scc_visit instance for this callchain exists.
158 * If instance does not exist or is empty, assign visit->entry_state to @st.
159 */
160static int maybe_enter_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
161{
162 struct bpf_scc_callchain *callchain = &env->callchain_buf;
163 struct bpf_scc_visit *visit;
164
165 if (!compute_scc_callchain(env, st, callchain))
166 return 0;
167 visit = scc_visit_lookup(env, callchain);
168 visit = visit ?: scc_visit_alloc(env, callchain);
169 if (!visit)
170 return -ENOMEM;
171 if (!visit->entry_state) {
172 visit->entry_state = st;
173 if (env->log.level & BPF_LOG_LEVEL2)
174 verbose(env, "SCC enter %s\n", format_callchain(env, callchain));
175 }
176 return 0;
177}
178
179static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visit *visit);
180
181/* If callchain for @st exists (@st is in some SCC), make it empty:
182 * - set visit->entry_state to NULL;
183 * - flush accumulated backedges.
184 */
185static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
186{
187 struct bpf_scc_callchain *callchain = &env->callchain_buf;
188 struct bpf_scc_visit *visit;
189
190 if (!compute_scc_callchain(env, st, callchain))
191 return 0;
192 visit = scc_visit_lookup(env, callchain);
193 if (!visit) {
194 /*
195 * If path traversal stops inside an SCC, corresponding bpf_scc_visit
196 * must exist for non-speculative paths. For non-speculative paths
197 * traversal stops when:
198 * a. Verification error is found, maybe_exit_scc() is not called.
199 * b. Top level BPF_EXIT is reached. Top level BPF_EXIT is not a member
200 * of any SCC.
201 * c. A checkpoint is reached and matched. Checkpoints are created by
202 * is_state_visited(), which calls maybe_enter_scc(), which allocates
203 * bpf_scc_visit instances for checkpoints within SCCs.
204 * (c) is the only case that can reach this point.
205 */
206 if (!st->speculative) {
207 verifier_bug(env, "scc exit: no visit info for call chain %s",
208 format_callchain(env, callchain));
209 return -EFAULT;
210 }
211 return 0;
212 }
213 if (visit->entry_state != st)
214 return 0;
215 if (env->log.level & BPF_LOG_LEVEL2)
216 verbose(env, "SCC exit %s\n", format_callchain(env, callchain));
217 visit->entry_state = NULL;
218 env->num_backedges -= visit->num_backedges;
219 visit->num_backedges = 0;
220 update_peak_states(env);
221 return propagate_backedges(env, visit);
222}
223
224/* Lookup an bpf_scc_visit instance corresponding to @st callchain
225 * and add @backedge to visit->backedges. @st callchain must exist.
226 */
227static int add_scc_backedge(struct bpf_verifier_env *env,
228 struct bpf_verifier_state *st,
229 struct bpf_scc_backedge *backedge)
230{
231 struct bpf_scc_callchain *callchain = &env->callchain_buf;
232 struct bpf_scc_visit *visit;
233
234 if (!compute_scc_callchain(env, st, callchain)) {
235 verifier_bug(env, "add backedge: no SCC in verification path, insn_idx %d",
236 st->insn_idx);
237 return -EFAULT;
238 }
239 visit = scc_visit_lookup(env, callchain);
240 if (!visit) {
241 verifier_bug(env, "add backedge: no visit info for call chain %s",
242 format_callchain(env, callchain));
243 return -EFAULT;
244 }
245 if (env->log.level & BPF_LOG_LEVEL2)
246 verbose(env, "SCC backedge %s\n", format_callchain(env, callchain));
247 backedge->next = visit->backedges;
248 visit->backedges = backedge;
249 visit->num_backedges++;
250 env->num_backedges++;
251 update_peak_states(env);
252 return 0;
253}
254
255/* bpf_reg_state->live marks for registers in a state @st are incomplete,
256 * if state @st is in some SCC and not all execution paths starting at this
257 * SCC are fully explored.
258 */
259static bool incomplete_read_marks(struct bpf_verifier_env *env,
260 struct bpf_verifier_state *st)
261{
262 struct bpf_scc_callchain *callchain = &env->callchain_buf;
263 struct bpf_scc_visit *visit;
264
265 if (!compute_scc_callchain(env, st, callchain))
266 return false;
267 visit = scc_visit_lookup(env, callchain);
268 if (!visit)
269 return false;
270 return !!visit->backedges;
271}
272
273int bpf_update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
274{
275 struct bpf_verifier_state_list *sl = NULL, *parent_sl;
276 struct bpf_verifier_state *parent;
277 int err;
278
279 while (st) {
280 u32 br = --st->branches;
281
282 /* verifier_bug_if(br > 1, ...) technically makes sense here,
283 * but see comment in push_stack(), hence:
284 */
285 verifier_bug_if((int)br < 0, env, "%s:branches_to_explore=%d", __func__, br);
286 if (br)
287 break;
288 err = maybe_exit_scc(env, st);
289 if (err)
290 return err;
291 parent = st->parent;
292 parent_sl = state_parent_as_list(st);
293 if (sl)
294 maybe_free_verifier_state(env, sl);
295 st = parent;
296 sl = parent_sl;
297 }
298 return 0;
299}
300
301/* check %cur's range satisfies %old's */
302static bool range_within(const struct bpf_reg_state *old,
303 const struct bpf_reg_state *cur)
304{
305 return cnum64_is_subset(old->r64, cur->r64) &&
306 cnum32_is_subset(old->r32, cur->r32);
307}
308
309/* If in the old state two registers had the same id, then they need to have
310 * the same id in the new state as well. But that id could be different from
311 * the old state, so we need to track the mapping from old to new ids.
312 * Once we have seen that, say, a reg with old id 5 had new id 9, any subsequent
313 * regs with old id 5 must also have new id 9 for the new state to be safe. But
314 * regs with a different old id could still have new id 9, we don't care about
315 * that.
316 * So we look through our idmap to see if this old id has been seen before. If
317 * so, we require the new id to match; otherwise, we add the id pair to the map.
318 */
319static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
320{
321 struct bpf_id_pair *map = idmap->map;
322 unsigned int i;
323
324 /* either both IDs should be set or both should be zero */
325 if (!!old_id != !!cur_id)
326 return false;
327
328 if (old_id == 0) /* cur_id == 0 as well */
329 return true;
330
331 for (i = 0; i < idmap->cnt; i++) {
332 if (map[i].old == old_id)
333 return map[i].cur == cur_id;
334 if (map[i].cur == cur_id)
335 return false;
336 }
337
338 /* Reached the end of known mappings; haven't seen this id before */
339 if (idmap->cnt < BPF_ID_MAP_SIZE) {
340 map[idmap->cnt].old = old_id;
341 map[idmap->cnt].cur = cur_id;
342 idmap->cnt++;
343 return true;
344 }
345
346 /*
347 * idmap slots are bounded by the number of registers and stack slots.
348 * Since referenced dynptrs acquire intermediate references that do
349 * not live in either, so the map can be exhausted. Since it is unlikely,
350 * fail the verification by treating the states as not equivalent.
351 */
352 return false;
353}
354
355/*
356 * Compare scalar register IDs for state equivalence.
357 *
358 * When old_id == 0, the old register is independent - not linked to any
359 * other register. Any linking in the current state only adds constraints,
360 * making it more restrictive. Since the old state didn't rely on any ID
361 * relationships for this register, it's always safe to accept cur regardless
362 * of its ID. Hence, return true immediately.
363 *
364 * When old_id != 0 but cur_id == 0, we need to ensure that different
365 * independent registers in cur don't incorrectly satisfy the ID matching
366 * requirements of linked registers in old.
367 *
368 * Example: if old has r6.id=X and r7.id=X (linked), but cur has r6.id=0
369 * and r7.id=0 (both independent), without temp IDs both would map old_id=X
370 * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map
371 * X->temp2, but X is already mapped to temp1, so the check fails correctly.
372 *
373 * When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the
374 * base id (flag stripped) must both map consistently. Example: old has
375 * r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag
376 * (r3 derived from unrelated r4). Without the base check, idmap gets two
377 * independent entries A->B and A|flag->C|flag, missing that A->C conflicts
378 * with A->B. The base ID cross-check catches this.
379 */
380static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
381{
382 if (!old_id)
383 return true;
384
385 cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen;
386
387 if (!check_ids(old_id, cur_id, idmap))
388 return false;
389 if (old_id & BPF_ADD_CONST) {
390 old_id &= ~BPF_ADD_CONST;
391 cur_id &= ~BPF_ADD_CONST;
392 if (!check_ids(old_id, cur_id, idmap))
393 return false;
394 }
395 return true;
396}
397
398static void __clean_func_state(struct bpf_verifier_env *env,
399 struct bpf_func_state *st,
400 u16 live_regs, int frame)
401{
402 int i, j;
403
404 for (i = 0; i < BPF_REG_FP; i++) {
405 /* liveness must not touch this register anymore */
406 if (!(live_regs & BIT(i)))
407 /* since the register is unused, clear its state
408 * to make further comparison simpler
409 */
410 bpf_mark_reg_not_init(env, &st->regs[i]);
411 }
412
413 /*
414 * Clean dead 4-byte halves within each SPI independently.
415 * half_spi 2*i → lower half: slot_type[0..3] (closer to FP)
416 * half_spi 2*i+1 → upper half: slot_type[4..7] (farther from FP)
417 */
418 for (i = 0; i < st->allocated_stack / BPF_REG_SIZE; i++) {
419 bool lo_live = bpf_stack_slot_alive(env, frame, i * 2);
420 bool hi_live = bpf_stack_slot_alive(env, frame, i * 2 + 1);
421
422 if (!hi_live || !lo_live) {
423 int start = !lo_live ? 0 : BPF_REG_SIZE / 2;
424 int end = !hi_live ? BPF_REG_SIZE : BPF_REG_SIZE / 2;
425 u8 stype = st->stack[i].slot_type[7];
426
427 /*
428 * Don't clear special slots.
429 * destroy_if_dynptr_stack_slot() needs STACK_DYNPTR to
430 * detect overwrites and invalidate associated data slices.
431 * is_iter_reg_valid_uninit() and is_irq_flag_reg_valid_uninit()
432 * check for their respective slot types to detect double-create.
433 */
434 if (stype == STACK_DYNPTR || stype == STACK_ITER ||
435 stype == STACK_IRQ_FLAG)
436 continue;
437
438 /*
439 * Only scalar spills can be degraded to raw stack bytes
440 * when their high half is dead. Pointer spills need the
441 * saved spilled_ptr metadata so partial fills keep
442 * rejecting as non-scalar register fills.
443 */
444 if (!hi_live) {
445 struct bpf_reg_state *spill = &st->stack[i].spilled_ptr;
446
447 if (lo_live && stype == STACK_SPILL) {
448 if (spill->type != SCALAR_VALUE)
449 continue;
450 /*
451 * Can't replace with STACK_ZERO, because
452 * that requires bpf_mark_chain_precision().
453 */
454 if (bpf_register_is_null(spill))
455 continue;
456 for (j = 0; j < 4; j++) {
457 u8 *t = &st->stack[i].slot_type[j];
458
459 if (*t == STACK_SPILL)
460 *t = STACK_MISC;
461 }
462 }
463 bpf_mark_reg_not_init(env, spill);
464 }
465 for (j = start; j < end; j++)
466 st->stack[i].slot_type[j] = STACK_POISON;
467 }
468 }
469}
470
471static int clean_verifier_state(struct bpf_verifier_env *env,
472 struct bpf_verifier_state *st)
473{
474 int i, err;
475
476 err = bpf_live_stack_query_init(env, st);
477 if (err)
478 return err;
479 for (i = 0; i <= st->curframe; i++) {
480 u32 ip = bpf_frame_insn_idx(st, i);
481 u16 live_regs = env->insn_aux_data[ip].live_regs_before;
482
483 __clean_func_state(env, st->frame[i], live_regs, i);
484 }
485 return 0;
486}
487
488static bool regs_exact(const struct bpf_reg_state *rold,
489 const struct bpf_reg_state *rcur,
490 struct bpf_idmap *idmap)
491{
492 return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
493 check_ids(rold->id, rcur->id, idmap) &&
494 check_ids(rold->parent_id, rcur->parent_id, idmap) &&
495 check_ids(rold->map_uid, rcur->map_uid, idmap);
496}
497
498enum exact_level {
499 NOT_EXACT,
500 EXACT,
501 RANGE_WITHIN
502};
503
504/* Returns true if (rold safe implies rcur safe) */
505static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
506 struct bpf_reg_state *rcur, struct bpf_idmap *idmap,
507 enum exact_level exact)
508{
509 if (exact == EXACT)
510 return regs_exact(rold, rcur, idmap);
511
512 if (rold->type == NOT_INIT)
513 /* explored state can't have used this */
514 return true;
515
516 /* Enforce that register types have to match exactly, including their
517 * modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general
518 * rule.
519 *
520 * One can make a point that using a pointer register as unbounded
521 * SCALAR would be technically acceptable, but this could lead to
522 * pointer leaks because scalars are allowed to leak while pointers
523 * are not. We could make this safe in special cases if root is
524 * calling us, but it's probably not worth the hassle.
525 *
526 * Also, register types that are *not* MAYBE_NULL could technically be
527 * safe to use as their MAYBE_NULL variants (e.g., PTR_TO_MAP_VALUE
528 * is safe to be used as PTR_TO_MAP_VALUE_OR_NULL, provided both point
529 * to the same map).
530 * However, if the old MAYBE_NULL register then got NULL checked,
531 * doing so could have affected others with the same id, and we can't
532 * check for that because we lost the id when we converted to
533 * a non-MAYBE_NULL variant.
534 * So, as a general rule we don't allow mixing MAYBE_NULL and
535 * non-MAYBE_NULL registers as well.
536 */
537 if (rold->type != rcur->type)
538 return false;
539
540 switch (base_type(rold->type)) {
541 case SCALAR_VALUE:
542 if (env->explore_alu_limits) {
543 /* explore_alu_limits disables tnum_in() and range_within()
544 * logic and requires everything to be strict
545 */
546 return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
547 check_scalar_ids(rold->id, rcur->id, idmap);
548 }
549 if (!rold->precise && exact == NOT_EXACT)
550 return true;
551 /*
552 * Linked register tracking uses rold->id to detect relationships.
553 * When rold->id == 0, the register is independent and any linking
554 * in rcur only adds constraints. When rold->id != 0, we must verify
555 * id mapping and (for BPF_ADD_CONST) offset consistency.
556 *
557 * +------------------+-----------+------------------+---------------+
558 * | | rold->id | rold + ADD_CONST | rold->id == 0 |
559 * |------------------+-----------+------------------+---------------|
560 * | rcur->id | range,ids | false | range |
561 * | rcur + ADD_CONST | false | range,ids,off | range |
562 * | rcur->id == 0 | range,ids | false | range |
563 * +------------------+-----------+------------------+---------------+
564 *
565 * Why check_ids() for scalar registers?
566 *
567 * Consider the following BPF code:
568 * 1: r6 = ... unbound scalar, ID=a ...
569 * 2: r7 = ... unbound scalar, ID=b ...
570 * 3: if (r6 > r7) goto +1
571 * 4: r6 = r7
572 * 5: if (r6 > X) goto ...
573 * 6: ... memory operation using r7 ...
574 *
575 * First verification path is [1-6]:
576 * - at (4) same bpf_reg_state::id (b) would be assigned to r6 and r7;
577 * - at (5) r6 would be marked <= X, sync_linked_regs() would also mark
578 * r7 <= X, because r6 and r7 share same id.
579 * Next verification path is [1-4, 6].
580 *
581 * Instruction (6) would be reached in two states:
582 * I. r6{.id=b}, r7{.id=b} via path 1-6;
583 * II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
584 *
585 * Use check_ids() to distinguish these states.
586 * ---
587 * Also verify that new value satisfies old value range knowledge.
588 */
589
590 /*
591 * ADD_CONST flags must match exactly: BPF_ADD_CONST32 and
592 * BPF_ADD_CONST64 have different linking semantics in
593 * sync_linked_regs() (alu32 zero-extends, alu64 does not),
594 * so pruning across different flag types is unsafe.
595 */
596 if (rold->id &&
597 (rold->id & BPF_ADD_CONST) != (rcur->id & BPF_ADD_CONST))
598 return false;
599
600 /* Both have offset linkage: offsets must match */
601 if ((rold->id & BPF_ADD_CONST) && rold->delta != rcur->delta)
602 return false;
603
604 if (!check_scalar_ids(rold->id, rcur->id, idmap))
605 return false;
606
607 return range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off);
608 case PTR_TO_MAP_KEY:
609 case PTR_TO_MAP_VALUE:
610 case PTR_TO_MEM:
611 case PTR_TO_BUF:
612 case PTR_TO_TP_BUFFER:
613 /* If the new min/max/var_off satisfy the old ones and
614 * everything else matches, we are OK.
615 */
616 return memcmp(rold, rcur, offsetof(struct bpf_reg_state, var_off)) == 0 &&
617 range_within(rold, rcur) &&
618 tnum_in(rold->var_off, rcur->var_off) &&
619 check_ids(rold->id, rcur->id, idmap) &&
620 check_ids(rold->parent_id, rcur->parent_id, idmap) &&
621 check_ids(rold->map_uid, rcur->map_uid, idmap);
622 case PTR_TO_PACKET_META:
623 case PTR_TO_PACKET:
624 /* We must have at least as much range as the old ptr
625 * did, so that any accesses which were safe before are
626 * still safe. This is true even if old range < old off,
627 * since someone could have accessed through (ptr - k), or
628 * even done ptr -= k in a register, to get a safe access.
629 */
630 if (rold->range < 0 || rcur->range < 0) {
631 /* special case for [BEYOND|AT]_PKT_END */
632 if (rold->range != rcur->range)
633 return false;
634 } else if (rold->range > rcur->range) {
635 return false;
636 }
637 /* id relations must be preserved */
638 if (!check_ids(rold->id, rcur->id, idmap))
639 return false;
640 /* Preserve displacements between pointers sharing an ID. */
641 if (rold->id && rold->r64.base != rcur->r64.base)
642 return false;
643 /* new val must satisfy old val knowledge */
644 return range_within(rold, rcur) &&
645 tnum_in(rold->var_off, rcur->var_off);
646 case PTR_TO_STACK:
647 return regs_exact(rold, rcur, idmap);
648 case PTR_TO_ARENA:
649 return true;
650 case PTR_TO_INSN:
651 return memcmp(rold, rcur, offsetof(struct bpf_reg_state, var_off)) == 0 &&
652 range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off);
653 default:
654 return regs_exact(rold, rcur, idmap);
655 }
656}
657
658static struct bpf_reg_state unbound_reg;
659
660static __init int unbound_reg_init(void)
661{
662 bpf_mark_reg_unknown_imprecise(&unbound_reg);
663 return 0;
664}
665late_initcall(unbound_reg_init);
666
667static bool is_spilled_scalar_after(const struct bpf_stack_state *stack, int im)
668{
669 return stack->slot_type[im] == STACK_SPILL &&
670 stack->spilled_ptr.type == SCALAR_VALUE;
671}
672
673static bool is_stack_misc_after(struct bpf_verifier_env *env,
674 struct bpf_stack_state *stack, int im)
675{
676 u32 i;
677
678 for (i = im; i < ARRAY_SIZE(stack->slot_type); ++i) {
679 if ((stack->slot_type[i] == STACK_MISC) ||
680 ((stack->slot_type[i] == STACK_INVALID || stack->slot_type[i] == STACK_POISON) &&
681 env->allow_uninit_stack))
682 continue;
683 return false;
684 }
685
686 return true;
687}
688
689static struct bpf_reg_state *scalar_reg_for_stack(struct bpf_verifier_env *env,
690 struct bpf_stack_state *stack, int im)
691{
692 if (is_spilled_scalar_after(stack, im))
693 return &stack->spilled_ptr;
694
695 if (is_stack_misc_after(env, stack, im))
696 return &unbound_reg;
697
698 return NULL;
699}
700
701static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
702 struct bpf_func_state *cur, struct bpf_idmap *idmap,
703 enum exact_level exact)
704{
705 int i, spi;
706
707 /* walk slots of the explored stack and ignore any additional
708 * slots in the current stack, since explored(safe) state
709 * didn't use them
710 */
711 for (i = 0; i < old->allocated_stack; i++) {
712 struct bpf_reg_state *old_reg, *cur_reg;
713 int im = i % BPF_REG_SIZE;
714
715 spi = i / BPF_REG_SIZE;
716
717 if (exact == EXACT) {
718 u8 old_type = old->stack[spi].slot_type[i % BPF_REG_SIZE];
719 u8 cur_type = i < cur->allocated_stack ?
720 cur->stack[spi].slot_type[i % BPF_REG_SIZE] : STACK_INVALID;
721
722 /* STACK_INVALID and STACK_POISON are equivalent for pruning */
723 if (old_type == STACK_POISON)
724 old_type = STACK_INVALID;
725 if (cur_type == STACK_POISON)
726 cur_type = STACK_INVALID;
727 if (i >= cur->allocated_stack || old_type != cur_type)
728 return false;
729 }
730
731 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID ||
732 old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_POISON)
733 continue;
734
735 if (env->allow_uninit_stack &&
736 old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC)
737 continue;
738
739 /* explored stack has more populated slots than current stack
740 * and these slots were used
741 */
742 if (i >= cur->allocated_stack)
743 return false;
744
745 /*
746 * 64 and 32-bit scalar spills vs MISC/INVALID slots and vice versa.
747 * Load from MISC/INVALID slots produces unbound scalar.
748 * Construct a fake register for such stack and call
749 * regsafe() to ensure scalar ids are compared.
750 */
751 if (im == 0 || im == 4) {
752 old_reg = scalar_reg_for_stack(env, &old->stack[spi], im);
753 cur_reg = scalar_reg_for_stack(env, &cur->stack[spi], im);
754 if (old_reg && cur_reg) {
755 if (!regsafe(env, old_reg, cur_reg, idmap, exact))
756 return false;
757 i += (im == 0 ? BPF_REG_SIZE - 1 : 3);
758 continue;
759 }
760 }
761
762 /* if old state was safe with misc data in the stack
763 * it will be safe with zero-initialized stack.
764 * The opposite is not true
765 */
766 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC &&
767 cur->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_ZERO)
768 continue;
769 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
770 cur->stack[spi].slot_type[i % BPF_REG_SIZE])
771 /* Ex: old explored (safe) state has STACK_SPILL in
772 * this stack slot, but current has STACK_MISC ->
773 * this verifier states are not equivalent,
774 * return false to continue verification of this path
775 */
776 return false;
777 if (i % BPF_REG_SIZE != BPF_REG_SIZE - 1)
778 continue;
779 /* Both old and cur are having same slot_type */
780 switch (old->stack[spi].slot_type[BPF_REG_SIZE - 1]) {
781 case STACK_SPILL:
782 /* when explored and current stack slot are both storing
783 * spilled registers, check that stored pointers types
784 * are the same as well.
785 * Ex: explored safe path could have stored
786 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -8}
787 * but current path has stored:
788 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -16}
789 * such verifier states are not equivalent.
790 * return false to continue verification of this path
791 */
792 if (!regsafe(env, &old->stack[spi].spilled_ptr,
793 &cur->stack[spi].spilled_ptr, idmap, exact))
794 return false;
795 break;
796 case STACK_DYNPTR:
797 old_reg = &old->stack[spi].spilled_ptr;
798 cur_reg = &cur->stack[spi].spilled_ptr;
799 if (old_reg->dynptr.type != cur_reg->dynptr.type ||
800 old_reg->dynptr.first_slot != cur_reg->dynptr.first_slot ||
801 !check_ids(old_reg->id, cur_reg->id, idmap) ||
802 !check_ids(old_reg->parent_id, cur_reg->parent_id, idmap))
803 return false;
804 break;
805 case STACK_ITER:
806 old_reg = &old->stack[spi].spilled_ptr;
807 cur_reg = &cur->stack[spi].spilled_ptr;
808 /* iter.depth is not compared between states as it
809 * doesn't matter for correctness and would otherwise
810 * prevent convergence; we maintain it only to prevent
811 * infinite loop check triggering, see
812 * iter_active_depths_differ()
813 */
814 if (old_reg->type != cur_reg->type ||
815 old_reg->iter.btf != cur_reg->iter.btf ||
816 old_reg->iter.btf_id != cur_reg->iter.btf_id ||
817 old_reg->iter.state != cur_reg->iter.state ||
818 /* ignore {old_reg,cur_reg}->iter.depth, see above */
819 !check_ids(old_reg->id, cur_reg->id, idmap))
820 return false;
821 break;
822 case STACK_IRQ_FLAG:
823 old_reg = &old->stack[spi].spilled_ptr;
824 cur_reg = &cur->stack[spi].spilled_ptr;
825 if (!check_ids(old_reg->id, cur_reg->id, idmap) ||
826 old_reg->irq.kfunc_class != cur_reg->irq.kfunc_class)
827 return false;
828 break;
829 case STACK_MISC:
830 case STACK_ZERO:
831 case STACK_INVALID:
832 case STACK_POISON:
833 continue;
834 /* Ensure that new unhandled slot types return false by default */
835 default:
836 return false;
837 }
838 }
839 return true;
840}
841
842/*
843 * Compare stack arg slots between old and current states.
844 * Outgoing stack args are path-local state and must agree for pruning.
845 */
846static bool stack_arg_safe(struct bpf_verifier_env *env, struct bpf_func_state *old,
847 struct bpf_func_state *cur, struct bpf_idmap *idmap,
848 enum exact_level exact)
849{
850 int i, nslots;
851
852 nslots = max(old->out_stack_arg_cnt, cur->out_stack_arg_cnt);
853 for (i = 0; i < nslots; i++) {
854 struct bpf_reg_state *old_arg, *cur_arg;
855 struct bpf_reg_state not_init = { .type = NOT_INIT };
856
857 old_arg = i < old->out_stack_arg_cnt ?
858 &old->stack_arg_regs[i] : &not_init;
859 cur_arg = i < cur->out_stack_arg_cnt ?
860 &cur->stack_arg_regs[i] : &not_init;
861 if (!regsafe(env, old_arg, cur_arg, idmap, exact))
862 return false;
863 }
864
865 return true;
866}
867
868static bool refsafe(struct bpf_verifier_state *old, struct bpf_verifier_state *cur,
869 struct bpf_idmap *idmap)
870{
871 int i;
872
873 if (old->acquired_refs != cur->acquired_refs)
874 return false;
875
876 if (old->active_locks != cur->active_locks)
877 return false;
878
879 if (old->active_preempt_locks != cur->active_preempt_locks)
880 return false;
881
882 if (old->active_rcu_locks != cur->active_rcu_locks)
883 return false;
884
885 if (!check_ids(old->active_irq_id, cur->active_irq_id, idmap))
886 return false;
887
888 if (!check_ids(old->active_lock_id, cur->active_lock_id, idmap) ||
889 old->active_lock_ptr != cur->active_lock_ptr)
890 return false;
891
892 for (i = 0; i < old->acquired_refs; i++) {
893 if (!check_ids(old->refs[i].id, cur->refs[i].id, idmap) ||
894 old->refs[i].type != cur->refs[i].type)
895 return false;
896 switch (old->refs[i].type) {
897 case REF_TYPE_PTR:
898 if (!check_ids(old->refs[i].parent_id, cur->refs[i].parent_id, idmap))
899 return false;
900 break;
901 case REF_TYPE_IRQ:
902 break;
903 case REF_TYPE_LOCK:
904 case REF_TYPE_RES_LOCK:
905 case REF_TYPE_RES_LOCK_IRQ:
906 if (old->refs[i].ptr != cur->refs[i].ptr)
907 return false;
908 break;
909 default:
910 WARN_ONCE(1, "Unhandled enum type for reference state: %d\n", old->refs[i].type);
911 return false;
912 }
913 }
914
915 return true;
916}
917
918/* compare two verifier states
919 *
920 * all states stored in state_list are known to be valid, since
921 * verifier reached 'bpf_exit' instruction through them
922 *
923 * this function is called when verifier exploring different branches of
924 * execution popped from the state stack. If it sees an old state that has
925 * more strict register state and more strict stack state then this execution
926 * branch doesn't need to be explored further, since verifier already
927 * concluded that more strict state leads to valid finish.
928 *
929 * Therefore two states are equivalent if register state is more conservative
930 * and explored stack state is more conservative than the current one.
931 * Example:
932 * explored current
933 * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC)
934 * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC)
935 *
936 * In other words if current stack state (one being explored) has more
937 * valid slots than old one that already passed validation, it means
938 * the verifier can stop exploring and conclude that current state is valid too
939 *
940 * Similarly with registers. If explored state has register type as invalid
941 * whereas register type in current state is meaningful, it means that
942 * the current state will reach 'bpf_exit' instruction safely
943 */
944static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old,
945 struct bpf_func_state *cur, u32 insn_idx, enum exact_level exact)
946{
947 u16 live_regs = env->insn_aux_data[insn_idx].live_regs_before;
948 u16 i;
949
950 if (old->callback_depth > cur->callback_depth)
951 return false;
952
953 if (!old->no_stack_arg_load && cur->no_stack_arg_load)
954 return false;
955
956 for (i = 0; i < MAX_BPF_REG; i++)
957 if (((1 << i) & live_regs) &&
958 !regsafe(env, &old->regs[i], &cur->regs[i],
959 &env->idmap_scratch, exact))
960 return false;
961
962 if (!stacksafe(env, old, cur, &env->idmap_scratch, exact))
963 return false;
964
965 if (!stack_arg_safe(env, old, cur, &env->idmap_scratch, exact))
966 return false;
967
968 return true;
969}
970
971static void reset_idmap_scratch(struct bpf_verifier_env *env)
972{
973 struct bpf_idmap *idmap = &env->idmap_scratch;
974
975 idmap->tmp_id_gen = env->id_gen;
976 idmap->cnt = 0;
977}
978
979static bool states_equal(struct bpf_verifier_env *env,
980 struct bpf_verifier_state *old,
981 struct bpf_verifier_state *cur,
982 enum exact_level exact)
983{
984 u32 insn_idx;
985 int i;
986
987 if (old->curframe != cur->curframe)
988 return false;
989
990 reset_idmap_scratch(env);
991
992 /* Verification state from speculative execution simulation
993 * must never prune a non-speculative execution one.
994 */
995 if (old->speculative && !cur->speculative)
996 return false;
997
998 if (old->in_sleepable != cur->in_sleepable)
999 return false;
1000
1001 if (!refsafe(old, cur, &env->idmap_scratch))
1002 return false;
1003
1004 /* for states to be equal callsites have to be the same
1005 * and all frame states need to be equivalent
1006 */
1007 for (i = 0; i <= old->curframe; i++) {
1008 insn_idx = bpf_frame_insn_idx(old, i);
1009 if (old->frame[i]->callsite != cur->frame[i]->callsite)
1010 return false;
1011 if (!func_states_equal(env, old->frame[i], cur->frame[i], insn_idx, exact))
1012 return false;
1013 }
1014 return true;
1015}
1016
1017/* find precise scalars in the previous equivalent state and
1018 * propagate them into the current state
1019 */
1020static int propagate_precision(struct bpf_verifier_env *env,
1021 const struct bpf_verifier_state *old,
1022 struct bpf_verifier_state *cur,
1023 bool *changed)
1024{
1025 struct bpf_reg_state *state_reg;
1026 struct bpf_func_state *state;
1027 int i, err = 0, fr;
1028 bool first;
1029
1030 for (fr = old->curframe; fr >= 0; fr--) {
1031 state = old->frame[fr];
1032 state_reg = state->regs;
1033 first = true;
1034 for (i = 0; i < BPF_REG_FP; i++, state_reg++) {
1035 if (state_reg->type != SCALAR_VALUE ||
1036 !state_reg->precise)
1037 continue;
1038 if (env->log.level & BPF_LOG_LEVEL2) {
1039 if (first)
1040 verbose(env, "frame %d: propagating r%d", fr, i);
1041 else
1042 verbose(env, ",r%d", i);
1043 }
1044 bpf_bt_set_frame_reg(&env->bt, fr, i);
1045 first = false;
1046 }
1047
1048 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) {
1049 if (!bpf_is_spilled_reg(&state->stack[i]))
1050 continue;
1051 state_reg = &state->stack[i].spilled_ptr;
1052 if (state_reg->type != SCALAR_VALUE ||
1053 !state_reg->precise)
1054 continue;
1055 if (env->log.level & BPF_LOG_LEVEL2) {
1056 if (first)
1057 verbose(env, "frame %d: propagating fp%d",
1058 fr, (-i - 1) * BPF_REG_SIZE);
1059 else
1060 verbose(env, ",fp%d", (-i - 1) * BPF_REG_SIZE);
1061 }
1062 bpf_bt_set_frame_slot(&env->bt, fr, i);
1063 first = false;
1064 }
1065 if (!first && (env->log.level & BPF_LOG_LEVEL2))
1066 verbose(env, "\n");
1067 }
1068
1069 err = bpf_mark_chain_precision(env, cur, -1, changed);
1070 if (err < 0)
1071 return err;
1072
1073 return 0;
1074}
1075
1076#define MAX_BACKEDGE_ITERS 64
1077
1078/* Propagate read and precision marks from visit->backedges[*].state->equal_state
1079 * to corresponding parent states of visit->backedges[*].state until fixed point is reached,
1080 * then free visit->backedges.
1081 * After execution of this function incomplete_read_marks() will return false
1082 * for all states corresponding to @visit->callchain.
1083 */
1084static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visit *visit)
1085{
1086 struct bpf_scc_backedge *backedge;
1087 struct bpf_verifier_state *st;
1088 bool changed;
1089 int i, err;
1090
1091 i = 0;
1092 do {
1093 if (i++ > MAX_BACKEDGE_ITERS) {
1094 if (env->log.level & BPF_LOG_LEVEL2)
1095 verbose(env, "%s: too many iterations\n", __func__);
1096 for (backedge = visit->backedges; backedge; backedge = backedge->next)
1097 bpf_mark_all_scalars_precise(env, &backedge->state);
1098 break;
1099 }
1100 changed = false;
1101 for (backedge = visit->backedges; backedge; backedge = backedge->next) {
1102 st = &backedge->state;
1103 err = propagate_precision(env, st->equal_state, st, &changed);
1104 if (err)
1105 return err;
1106 }
1107 } while (changed);
1108
1109 bpf_free_backedges(visit);
1110 return 0;
1111}
1112
1113static bool states_maybe_looping(struct bpf_verifier_state *old,
1114 struct bpf_verifier_state *cur)
1115{
1116 struct bpf_func_state *fold, *fcur;
1117 int i, fr = cur->curframe;
1118
1119 if (old->curframe != fr)
1120 return false;
1121
1122 fold = old->frame[fr];
1123 fcur = cur->frame[fr];
1124 for (i = 0; i < MAX_BPF_REG; i++)
1125 if (memcmp(&fold->regs[i], &fcur->regs[i],
1126 offsetof(struct bpf_reg_state, precise)))
1127 return false;
1128 return true;
1129}
1130
1131/* is_state_visited() handles iter_next() (see process_iter_next_call() for
1132 * terminology) calls specially: as opposed to bounded BPF loops, it *expects*
1133 * states to match, which otherwise would look like an infinite loop. So while
1134 * iter_next() calls are taken care of, we still need to be careful and
1135 * prevent erroneous and too eager declaration of "infinite loop", when
1136 * iterators are involved.
1137 *
1138 * Here's a situation in pseudo-BPF assembly form:
1139 *
1140 * 0: again: ; set up iter_next() call args
1141 * 1: r1 = &it ; <CHECKPOINT HERE>
1142 * 2: call bpf_iter_num_next ; this is iter_next() call
1143 * 3: if r0 == 0 goto done
1144 * 4: ... something useful here ...
1145 * 5: goto again ; another iteration
1146 * 6: done:
1147 * 7: r1 = &it
1148 * 8: call bpf_iter_num_destroy ; clean up iter state
1149 * 9: exit
1150 *
1151 * This is a typical loop. Let's assume that we have a prune point at 1:,
1152 * before we get to `call bpf_iter_num_next` (e.g., because of that `goto
1153 * again`, assuming other heuristics don't get in a way).
1154 *
1155 * When we first time come to 1:, let's say we have some state X. We proceed
1156 * to 2:, fork states, enqueue ACTIVE, validate NULL case successfully, exit.
1157 * Now we come back to validate that forked ACTIVE state. We proceed through
1158 * 3-5, come to goto, jump to 1:. Let's assume our state didn't change, so we
1159 * are converging. But the problem is that we don't know that yet, as this
1160 * convergence has to happen at iter_next() call site only. So if nothing is
1161 * done, at 1: verifier will use bounded loop logic and declare infinite
1162 * looping (and would be *technically* correct, if not for iterator's
1163 * "eventual sticky NULL" contract, see process_iter_next_call()). But we
1164 * don't want that. So what we do in process_iter_next_call() when we go on
1165 * another ACTIVE iteration, we bump slot->iter.depth, to mark that it's
1166 * a different iteration. So when we suspect an infinite loop, we additionally
1167 * check if any of the *ACTIVE* iterator states depths differ. If yes, we
1168 * pretend we are not looping and wait for next iter_next() call.
1169 *
1170 * This only applies to ACTIVE state. In DRAINED state we don't expect to
1171 * loop, because that would actually mean infinite loop, as DRAINED state is
1172 * "sticky", and so we'll keep returning into the same instruction with the
1173 * same state (at least in one of possible code paths).
1174 *
1175 * This approach allows to keep infinite loop heuristic even in the face of
1176 * active iterator. E.g., C snippet below is and will be detected as
1177 * infinitely looping:
1178 *
1179 * struct bpf_iter_num it;
1180 * int *p, x;
1181 *
1182 * bpf_iter_num_new(&it, 0, 10);
1183 * while ((p = bpf_iter_num_next(&t))) {
1184 * x = p;
1185 * while (x--) {} // <<-- infinite loop here
1186 * }
1187 *
1188 */
1189static bool iter_active_depths_differ(struct bpf_verifier_state *old, struct bpf_verifier_state *cur)
1190{
1191 struct bpf_reg_state *slot, *cur_slot;
1192 struct bpf_func_state *state;
1193 int i, fr;
1194
1195 for (fr = old->curframe; fr >= 0; fr--) {
1196 state = old->frame[fr];
1197 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) {
1198 if (state->stack[i].slot_type[0] != STACK_ITER)
1199 continue;
1200
1201 slot = &state->stack[i].spilled_ptr;
1202 if (slot->iter.state != BPF_ITER_STATE_ACTIVE)
1203 continue;
1204
1205 cur_slot = &cur->frame[fr]->stack[i].spilled_ptr;
1206 if (cur_slot->iter.depth != slot->iter.depth)
1207 return true;
1208 }
1209 }
1210 return false;
1211}
1212
1213static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
1214{
1215 struct bpf_func_state *func;
1216 struct bpf_reg_state *reg;
1217 int i, j;
1218
1219 for (i = 0; i <= st->curframe; i++) {
1220 func = st->frame[i];
1221 for (j = 0; j < BPF_REG_FP; j++) {
1222 reg = &func->regs[j];
1223 if (reg->type != SCALAR_VALUE)
1224 continue;
1225 reg->precise = false;
1226 }
1227 for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) {
1228 if (!bpf_is_spilled_reg(&func->stack[j]))
1229 continue;
1230 reg = &func->stack[j].spilled_ptr;
1231 if (reg->type != SCALAR_VALUE)
1232 continue;
1233 reg->precise = false;
1234 }
1235 }
1236}
1237
1238int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
1239{
1240 struct bpf_verifier_state_list *new_sl;
1241 struct bpf_verifier_state_list *sl;
1242 struct bpf_verifier_state *cur = env->cur_state, *new;
1243 bool force_new_state, add_new_state, loop;
1244 int n, err, states_cnt = 0;
1245 struct list_head *pos, *tmp, *head;
1246
1247 force_new_state = env->test_state_freq || bpf_is_force_checkpoint(env, insn_idx) ||
1248 /* Avoid accumulating infinitely long jmp history */
1249 cur->jmp_history_cnt > 40;
1250
1251 /* bpf progs typically have pruning point every 4 instructions
1252 * http://vger.kernel.org/bpfconf2019.html#session-1
1253 * Do not add new state for future pruning if the verifier hasn't seen
1254 * at least 2 jumps and at least 8 instructions.
1255 * This heuristics helps decrease 'total_states' and 'peak_states' metric.
1256 * In tests that amounts to up to 50% reduction into total verifier
1257 * memory consumption and 20% verifier time speedup.
1258 */
1259 add_new_state = force_new_state;
1260 if (env->jmps_processed - env->prev_jmps_processed >= 2 &&
1261 env->insn_processed - env->prev_insn_processed >= 8)
1262 add_new_state = true;
1263
1264 /* keep cleaning the current state as registers/stack become dead */
1265 err = clean_verifier_state(env, cur);
1266 if (err)
1267 return err;
1268
1269 loop = false;
1270 head = bpf_explored_state(env, insn_idx);
1271 list_for_each_safe(pos, tmp, head) {
1272 sl = container_of(pos, struct bpf_verifier_state_list, node);
1273 states_cnt++;
1274 if (sl->state.insn_idx != insn_idx)
1275 continue;
1276
1277 if (sl->state.branches) {
1278 struct bpf_func_state *frame = sl->state.frame[sl->state.curframe];
1279
1280 if (frame->in_async_callback_fn &&
1281 frame->async_entry_cnt != cur->frame[cur->curframe]->async_entry_cnt) {
1282 /* Different async_entry_cnt means that the verifier is
1283 * processing another entry into async callback.
1284 * Seeing the same state is not an indication of infinite
1285 * loop or infinite recursion.
1286 * But finding the same state doesn't mean that it's safe
1287 * to stop processing the current state. The previous state
1288 * hasn't yet reached bpf_exit, since state.branches > 0.
1289 * Checking in_async_callback_fn alone is not enough either.
1290 * Since the verifier still needs to catch infinite loops
1291 * inside async callbacks.
1292 */
1293 goto skip_inf_loop_check;
1294 }
1295 /* BPF open-coded iterators loop detection is special.
1296 * states_maybe_looping() logic is too simplistic in detecting
1297 * states that *might* be equivalent, because it doesn't know
1298 * about ID remapping, so don't even perform it.
1299 * See process_iter_next_call() and iter_active_depths_differ()
1300 * for overview of the logic. When current and one of parent
1301 * states are detected as equivalent, it's a good thing: we prove
1302 * convergence and can stop simulating further iterations.
1303 * It's safe to assume that iterator loop will finish, taking into
1304 * account iter_next() contract of eventually returning
1305 * sticky NULL result.
1306 *
1307 * Note, that states have to be compared exactly in this case because
1308 * read and precision marks might not be finalized inside the loop.
1309 * E.g. as in the program below:
1310 *
1311 * 1. r7 = -16
1312 * 2. r6 = bpf_get_prandom_u32()
1313 * 3. while (bpf_iter_num_next(&fp[-8])) {
1314 * 4. if (r6 != 42) {
1315 * 5. r7 = -32
1316 * 6. r6 = bpf_get_prandom_u32()
1317 * 7. continue
1318 * 8. }
1319 * 9. r0 = r10
1320 * 10. r0 += r7
1321 * 11. r8 = *(u64 *)(r0 + 0)
1322 * 12. r6 = bpf_get_prandom_u32()
1323 * 13. }
1324 *
1325 * Here verifier would first visit path 1-3, create a checkpoint at 3
1326 * with r7=-16, continue to 4-7,3. Existing checkpoint at 3 does
1327 * not have read or precision mark for r7 yet, thus inexact states
1328 * comparison would discard current state with r7=-32
1329 * => unsafe memory access at 11 would not be caught.
1330 */
1331 if (is_iter_next_insn(env, insn_idx)) {
1332 if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
1333 struct bpf_func_state *cur_frame;
1334 struct bpf_reg_state *iter_state, *iter_reg;
1335 int spi;
1336
1337 cur_frame = cur->frame[cur->curframe];
1338 /* btf_check_iter_kfuncs() enforces that
1339 * iter state pointer is always the first arg
1340 */
1341 iter_reg = &cur_frame->regs[BPF_REG_1];
1342 /* current state is valid due to states_equal(),
1343 * so we can assume valid iter and reg state,
1344 * no need for extra (re-)validations
1345 */
1346 spi = bpf_get_spi(iter_reg->var_off.value);
1347 iter_state = &bpf_func(env, iter_reg)->stack[spi].spilled_ptr;
1348 if (iter_state->iter.state == BPF_ITER_STATE_ACTIVE) {
1349 loop = true;
1350 goto hit;
1351 }
1352 }
1353 goto skip_inf_loop_check;
1354 }
1355 if (is_may_goto_insn_at(env, insn_idx)) {
1356 if (sl->state.may_goto_depth != cur->may_goto_depth &&
1357 states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
1358 loop = true;
1359 goto hit;
1360 }
1361 }
1362 if (bpf_calls_callback(env, insn_idx)) {
1363 if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
1364 loop = true;
1365 goto hit;
1366 }
1367 goto skip_inf_loop_check;
1368 }
1369 /* attempt to detect infinite loop to avoid unnecessary doomed work */
1370 if (states_maybe_looping(&sl->state, cur) &&
1371 states_equal(env, &sl->state, cur, EXACT) &&
1372 !iter_active_depths_differ(&sl->state, cur) &&
1373 sl->state.may_goto_depth == cur->may_goto_depth &&
1374 sl->state.callback_unroll_depth == cur->callback_unroll_depth) {
1375 verbose_linfo(env, insn_idx, "; ");
1376 verbose(env, "infinite loop detected at insn %d\n", insn_idx);
1377 verbose(env, "cur state:");
1378 print_verifier_state(env, cur, cur->curframe, true);
1379 verbose(env, "old state:");
1380 print_verifier_state(env, &sl->state, cur->curframe, true);
1381 return -EINVAL;
1382 }
1383 /* if the verifier is processing a loop, avoid adding new state
1384 * too often, since different loop iterations have distinct
1385 * states and may not help future pruning.
1386 * This threshold shouldn't be too low to make sure that
1387 * a loop with large bound will be rejected quickly.
1388 * The most abusive loop will be:
1389 * r1 += 1
1390 * if r1 < 1000000 goto pc-2
1391 * 1M insn_procssed limit / 100 == 10k peak states.
1392 * This threshold shouldn't be too high either, since states
1393 * at the end of the loop are likely to be useful in pruning.
1394 */
1395skip_inf_loop_check:
1396 if (!force_new_state &&
1397 env->jmps_processed - env->prev_jmps_processed < 20 &&
1398 env->insn_processed - env->prev_insn_processed < 100)
1399 add_new_state = false;
1400 goto miss;
1401 }
1402 /* See comments for mark_all_regs_read_and_precise() */
1403 loop = incomplete_read_marks(env, &sl->state);
1404 if (states_equal(env, &sl->state, cur, loop ? RANGE_WITHIN : NOT_EXACT)) {
1405hit:
1406 sl->hit_cnt++;
1407
1408 /* if previous state reached the exit with precision and
1409 * current state is equivalent to it (except precision marks)
1410 * the precision needs to be propagated back in
1411 * the current state.
1412 */
1413 err = 0;
1414 if (bpf_is_jmp_point(env, env->insn_idx))
1415 err = bpf_push_jmp_history(env, cur, 0, 0, 0, 0);
1416 err = err ? : propagate_precision(env, &sl->state, cur, NULL);
1417 if (err)
1418 return err;
1419 /* When processing iterator based loops above propagate_liveness and
1420 * propagate_precision calls are not sufficient to transfer all relevant
1421 * read and precision marks. E.g. consider the following case:
1422 *
1423 * .-> A --. Assume the states are visited in the order A, B, C.
1424 * | | | Assume that state B reaches a state equivalent to state A.
1425 * | v v At this point, state C is not processed yet, so state A
1426 * '-- B C has not received any read or precision marks from C.
1427 * Thus, marks propagated from A to B are incomplete.
1428 *
1429 * The verifier mitigates this by performing the following steps:
1430 *
1431 * - Prior to the main verification pass, strongly connected components
1432 * (SCCs) are computed over the program's control flow graph,
1433 * intraprocedurally.
1434 *
1435 * - During the main verification pass, `maybe_enter_scc()` checks
1436 * whether the current verifier state is entering an SCC. If so, an
1437 * instance of a `bpf_scc_visit` object is created, and the state
1438 * entering the SCC is recorded as the entry state.
1439 *
1440 * - This instance is associated not with the SCC itself, but with a
1441 * `bpf_scc_callchain`: a tuple consisting of the call sites leading to
1442 * the SCC and the SCC id. See `compute_scc_callchain()`.
1443 *
1444 * - When a verification path encounters a `states_equal(...,
1445 * RANGE_WITHIN)` condition, there exists a call chain describing the
1446 * current state and a corresponding `bpf_scc_visit` instance. A copy
1447 * of the current state is created and added to
1448 * `bpf_scc_visit->backedges`.
1449 *
1450 * - When a verification path terminates, `maybe_exit_scc()` is called
1451 * from `bpf_update_branch_counts()`. For states with `branches == 0`, it
1452 * checks whether the state is the entry state of any `bpf_scc_visit`
1453 * instance. If it is, this indicates that all paths originating from
1454 * this SCC visit have been explored. `propagate_backedges()` is then
1455 * called, which propagates read and precision marks through the
1456 * backedges until a fixed point is reached.
1457 * (In the earlier example, this would propagate marks from A to B,
1458 * from C to A, and then again from A to B.)
1459 *
1460 * A note on callchains
1461 * --------------------
1462 *
1463 * Consider the following example:
1464 *
1465 * void foo() { loop { ... SCC#1 ... } }
1466 * void main() {
1467 * A: foo();
1468 * B: ...
1469 * C: foo();
1470 * }
1471 *
1472 * Here, there are two distinct callchains leading to SCC#1:
1473 * - (A, SCC#1)
1474 * - (C, SCC#1)
1475 *
1476 * Each callchain identifies a separate `bpf_scc_visit` instance that
1477 * accumulates backedge states. The `propagate_{liveness,precision}()`
1478 * functions traverse the parent state of each backedge state, which
1479 * means these parent states must remain valid (i.e., not freed) while
1480 * the corresponding `bpf_scc_visit` instance exists.
1481 *
1482 * Associating `bpf_scc_visit` instances directly with SCCs instead of
1483 * callchains would break this invariant:
1484 * - States explored during `C: foo()` would contribute backedges to
1485 * SCC#1, but SCC#1 would only be exited once the exploration of
1486 * `A: foo()` completes.
1487 * - By that time, the states explored between `A: foo()` and `C: foo()`
1488 * (i.e., `B: ...`) may have already been freed, causing the parent
1489 * links for states from `C: foo()` to become invalid.
1490 */
1491 if (loop) {
1492 struct bpf_scc_backedge *backedge;
1493
1494 backedge = kzalloc_obj(*backedge,
1495 GFP_KERNEL_ACCOUNT);
1496 if (!backedge)
1497 return -ENOMEM;
1498 err = bpf_copy_verifier_state(&backedge->state, cur);
1499 backedge->state.equal_state = &sl->state;
1500 backedge->state.insn_idx = insn_idx;
1501 err = err ?: add_scc_backedge(env, &sl->state, backedge);
1502 if (err) {
1503 bpf_free_verifier_state(&backedge->state, false);
1504 kfree(backedge);
1505 return err;
1506 }
1507 }
1508 return 1;
1509 }
1510miss:
1511 /* when new state is not going to be added do not increase miss count.
1512 * Otherwise several loop iterations will remove the state
1513 * recorded earlier. The goal of these heuristics is to have
1514 * states from some iterations of the loop (some in the beginning
1515 * and some at the end) to help pruning.
1516 */
1517 if (add_new_state)
1518 sl->miss_cnt++;
1519 /* heuristic to determine whether this state is beneficial
1520 * to keep checking from state equivalence point of view.
1521 * Higher numbers increase max_states_per_insn and verification time,
1522 * but do not meaningfully decrease insn_processed.
1523 * 'n' controls how many times state could miss before eviction.
1524 * Use bigger 'n' for checkpoints because evicting checkpoint states
1525 * too early would hinder iterator convergence.
1526 */
1527 n = bpf_is_force_checkpoint(env, insn_idx) && sl->state.branches > 0 ? 64 : 3;
1528 if (sl->miss_cnt > sl->hit_cnt * n + n) {
1529 /* the state is unlikely to be useful. Remove it to
1530 * speed up verification
1531 */
1532 sl->in_free_list = true;
1533 list_del(&sl->node);
1534 list_add(&sl->node, &env->free_list);
1535 env->free_list_size++;
1536 env->explored_states_size--;
1537 maybe_free_verifier_state(env, sl);
1538 }
1539 }
1540
1541 if (env->max_states_per_insn < states_cnt)
1542 env->max_states_per_insn = states_cnt;
1543
1544 if (!env->bpf_capable && states_cnt > BPF_COMPLEXITY_LIMIT_STATES)
1545 return 0;
1546
1547 if (!add_new_state)
1548 return 0;
1549
1550 /* There were no equivalent states, remember the current one.
1551 * Technically the current state is not proven to be safe yet,
1552 * but it will either reach outer most bpf_exit (which means it's safe)
1553 * or it will be rejected. When there are no loops the verifier won't be
1554 * seeing this tuple (frame[0].callsite, frame[1].callsite, .. insn_idx)
1555 * again on the way to bpf_exit.
1556 * When looping the sl->state.branches will be > 0 and this state
1557 * will not be considered for equivalence until branches == 0.
1558 */
1559 new_sl = kzalloc_obj(struct bpf_verifier_state_list, GFP_KERNEL_ACCOUNT);
1560 if (!new_sl)
1561 return -ENOMEM;
1562 env->total_states++;
1563 env->explored_states_size++;
1564 update_peak_states(env);
1565 env->prev_jmps_processed = env->jmps_processed;
1566 env->prev_insn_processed = env->insn_processed;
1567
1568 /* forget precise markings we inherited, see __mark_chain_precision */
1569 if (env->bpf_capable)
1570 mark_all_scalars_imprecise(env, cur);
1571
1572 bpf_clear_singular_ids(env, cur);
1573
1574 /* add new state to the head of linked list */
1575 new = &new_sl->state;
1576 err = bpf_copy_verifier_state(new, cur);
1577 if (err) {
1578 bpf_free_verifier_state(new, false);
1579 kfree(new_sl);
1580 return err;
1581 }
1582 new->insn_idx = insn_idx;
1583 verifier_bug_if(new->branches != 1, env,
1584 "%s:branches_to_explore=%d insn %d",
1585 __func__, new->branches, insn_idx);
1586 err = maybe_enter_scc(env, new);
1587 if (err) {
1588 bpf_free_verifier_state(new, false);
1589 kfree(new_sl);
1590 return err;
1591 }
1592
1593 cur->parent = new;
1594 cur->first_insn_idx = insn_idx;
1595 cur->dfs_depth = new->dfs_depth + 1;
1596 bpf_clear_jmp_history(cur);
1597 list_add(&new_sl->node, head);
1598 return 0;
1599}