// SPDX-License-Identifier: GPL-2.0-only/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */#include <linux/bpf.h>#include <linux/bpf_verifier.h>#include <linux/cnum.h>#include <linux/filter.h> #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) #define BPF_COMPLEXITY_LIMIT_STATES 64 static bool is_may_goto_insn_at(struct bpf_verifier_env *env, int insn_idx){ return bpf_is_may_goto_insn(&env->prog->insnsi[insn_idx]);} static bool is_iter_next_insn(struct bpf_verifier_env *env, int insn_idx){ return env->insn_aux_data[insn_idx].is_iter_next;} static void update_peak_states(struct bpf_verifier_env *env){ u32 cur_states; cur_states = env->explored_states_size + env->free_list_size + env->num_backedges; env->peak_states = max(env->peak_states, cur_states);} /* struct bpf_verifier_state->parent refers to states * that are in either of env->{expored_states,free_list}. * In both cases the state is contained in struct bpf_verifier_state_list. */static struct bpf_verifier_state_list *state_parent_as_list(struct bpf_verifier_state *st){ if (st->parent) return container_of(st->parent, struct bpf_verifier_state_list, state); return NULL;} static bool incomplete_read_marks(struct bpf_verifier_env *env, struct bpf_verifier_state *st); /* A state can be freed if it is no longer referenced: * - is in the env->free_list; * - has no children states; */static void maybe_free_verifier_state(struct bpf_verifier_env *env, struct bpf_verifier_state_list *sl){ if (!sl->in_free_list || sl->state.branches != 0 || incomplete_read_marks(env, &sl->state)) return; list_del(&sl->node); bpf_free_verifier_state(&sl->state, false); kfree(sl); env->free_list_size--;} /* For state @st look for a topmost frame with frame_insn_idx() in some SCC, * if such frame exists form a corresponding @callchain as an array of * call sites leading to this frame and SCC id. * E.g.: * * void foo() { A: loop {... SCC#1 ...}; } * void bar() { B: loop { C: foo(); ... SCC#2 ... } * D: loop { E: foo(); ... SCC#3 ... } } * void main() { F: bar(); } * * @callchain at (A) would be either (F,SCC#2) or (F,SCC#3) depending * on @st frame call sites being (F,C,A) or (F,E,A). */static bool compute_scc_callchain(struct bpf_verifier_env *env, struct bpf_verifier_state *st, struct bpf_scc_callchain *callchain){ u32 i, scc, insn_idx; memset(callchain, 0, sizeof(*callchain)); for (i = 0; i <= st->curframe; i++) { insn_idx = bpf_frame_insn_idx(st, i); scc = env->insn_aux_data[insn_idx].scc; if (scc) { callchain->scc = scc; break; } else if (i < st->curframe) { callchain->callsites[i] = insn_idx; } else { return false; } } return true;} /* Check if bpf_scc_visit instance for @callchain exists. */static struct bpf_scc_visit *scc_visit_lookup(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain){ struct bpf_scc_info *info = env->scc_info[callchain->scc]; struct bpf_scc_visit *visits = info->visits; u32 i; if (!info) return NULL; for (i = 0; i < info->num_visits; i++) if (memcmp(callchain, &visits[i].callchain, sizeof(*callchain)) == 0) return &visits[i]; return NULL;} /* Allocate a new bpf_scc_visit instance corresponding to @callchain. * Allocated instances are alive for a duration of the do_check_common() * call and are freed by free_states(). */static struct bpf_scc_visit *scc_visit_alloc(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain){ struct bpf_scc_visit *visit; struct bpf_scc_info *info; u32 scc, num_visits; u64 new_sz; scc = callchain->scc; info = env->scc_info[scc]; num_visits = info ? info->num_visits : 0; new_sz = sizeof(*info) + sizeof(struct bpf_scc_visit) * (num_visits + 1); info = kvrealloc(env->scc_info[scc], new_sz, GFP_KERNEL_ACCOUNT); if (!info) return NULL; env->scc_info[scc] = info; info->num_visits = num_visits + 1; visit = &info->visits[num_visits]; memset(visit, 0, sizeof(*visit)); memcpy(&visit->callchain, callchain, sizeof(*callchain)); return visit;} /* Form a string '(callsite#1,callsite#2,...,scc)' in env->tmp_str_buf */static char *format_callchain(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain){ char *buf = env->tmp_str_buf; int i, delta = 0; delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "("); for (i = 0; i < ARRAY_SIZE(callchain->callsites); i++) { if (!callchain->callsites[i]) break; delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "%u,", callchain->callsites[i]); } delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "%u)", callchain->scc); return env->tmp_str_buf;} /* If callchain for @st exists (@st is in some SCC), ensure that * bpf_scc_visit instance for this callchain exists. * If instance does not exist or is empty, assign visit->entry_state to @st. */static int maybe_enter_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st){ struct bpf_scc_callchain *callchain = &env->callchain_buf; struct bpf_scc_visit *visit; if (!compute_scc_callchain(env, st, callchain)) return 0; visit = scc_visit_lookup(env, callchain); visit = visit ?: scc_visit_alloc(env, callchain); if (!visit) return -ENOMEM; if (!visit->entry_state) { visit->entry_state = st; if (env->log.level & BPF_LOG_LEVEL2) verbose(env, "SCC enter %s\n", format_callchain(env, callchain)); } return 0;} static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visit *visit); /* If callchain for @st exists (@st is in some SCC), make it empty: * - set visit->entry_state to NULL; * - flush accumulated backedges. */static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st){ struct bpf_scc_callchain *callchain = &env->callchain_buf; struct bpf_scc_visit *visit; if (!compute_scc_callchain(env, st, callchain)) return 0; visit = scc_visit_lookup(env, callchain); if (!visit) { /* * If path traversal stops inside an SCC, corresponding bpf_scc_visit * must exist for non-speculative paths. For non-speculative paths * traversal stops when: * a. Verification error is found, maybe_exit_scc() is not called. * b. Top level BPF_EXIT is reached. Top level BPF_EXIT is not a member * of any SCC. * c. A checkpoint is reached and matched. Checkpoints are created by * is_state_visited(), which calls maybe_enter_scc(), which allocates * bpf_scc_visit instances for checkpoints within SCCs. * (c) is the only case that can reach this point. */ if (!st->speculative) { verifier_bug(env, "scc exit: no visit info for call chain %s", format_callchain(env, callchain)); return -EFAULT; } return 0; } if (visit->entry_state != st) return 0; if (env->log.level & BPF_LOG_LEVEL2) verbose(env, "SCC exit %s\n", format_callchain(env, callchain)); visit->entry_state = NULL; env->num_backedges -= visit->num_backedges; visit->num_backedges = 0; update_peak_states(env); return propagate_backedges(env, visit);} /* Lookup an bpf_scc_visit instance corresponding to @st callchain * and add @backedge to visit->backedges. @st callchain must exist. */static int add_scc_backedge(struct bpf_verifier_env *env, struct bpf_verifier_state *st, struct bpf_scc_backedge *backedge){ struct bpf_scc_callchain *callchain = &env->callchain_buf; struct bpf_scc_visit *visit; if (!compute_scc_callchain(env, st, callchain)) { verifier_bug(env, "add backedge: no SCC in verification path, insn_idx %d", st->insn_idx); return -EFAULT; } visit = scc_visit_lookup(env, callchain); if (!visit) { verifier_bug(env, "add backedge: no visit info for call chain %s", format_callchain(env, callchain)); return -EFAULT; } if (env->log.level & BPF_LOG_LEVEL2) verbose(env, "SCC backedge %s\n", format_callchain(env, callchain)); backedge->next = visit->backedges; visit->backedges = backedge; visit->num_backedges++; env->num_backedges++; update_peak_states(env); return 0;} /* bpf_reg_state->live marks for registers in a state @st are incomplete, * if state @st is in some SCC and not all execution paths starting at this * SCC are fully explored. */static bool incomplete_read_marks(struct bpf_verifier_env *env, struct bpf_verifier_state *st){ struct bpf_scc_callchain *callchain = &env->callchain_buf; struct bpf_scc_visit *visit; if (!compute_scc_callchain(env, st, callchain)) return false; visit = scc_visit_lookup(env, callchain); if (!visit) return false; return !!visit->backedges;} int bpf_update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st){ struct bpf_verifier_state_list *sl = NULL, *parent_sl; struct bpf_verifier_state *parent; int err; while (st) { u32 br = --st->branches; /* verifier_bug_if(br > 1, ...) technically makes sense here, * but see comment in push_stack(), hence: */ verifier_bug_if((int)br < 0, env, "%s:branches_to_explore=%d", __func__, br); if (br) break; err = maybe_exit_scc(env, st); if (err) return err; parent = st->parent; parent_sl = state_parent_as_list(st); if (sl) maybe_free_verifier_state(env, sl); st = parent; sl = parent_sl; } return 0;} /* check %cur's range satisfies %old's */static bool range_within(const struct bpf_reg_state *old, const struct bpf_reg_state *cur){ return cnum64_is_subset(old->r64, cur->r64) && cnum32_is_subset(old->r32, cur->r32);} /* If in the old state two registers had the same id, then they need to have * the same id in the new state as well. But that id could be different from * the old state, so we need to track the mapping from old to new ids. * Once we have seen that, say, a reg with old id 5 had new id 9, any subsequent * regs with old id 5 must also have new id 9 for the new state to be safe. But * regs with a different old id could still have new id 9, we don't care about * that. * So we look through our idmap to see if this old id has been seen before. If * so, we require the new id to match; otherwise, we add the id pair to the map. */static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap){ struct bpf_id_pair *map = idmap->map; unsigned int i; /* either both IDs should be set or both should be zero */ if (!!old_id != !!cur_id) return false; if (old_id == 0) /* cur_id == 0 as well */ return true; for (i = 0; i < idmap->cnt; i++) { if (map[i].old == old_id) return map[i].cur == cur_id; if (map[i].cur == cur_id) return false; } /* Reached the end of known mappings; haven't seen this id before */ if (idmap->cnt < BPF_ID_MAP_SIZE) { map[idmap->cnt].old = old_id; map[idmap->cnt].cur = cur_id; idmap->cnt++; return true; } /* * idmap slots are bounded by the number of registers and stack slots. * Since referenced dynptrs acquire intermediate references that do * not live in either, so the map can be exhausted. Since it is unlikely, * fail the verification by treating the states as not equivalent. */ return false;} /* * Compare scalar register IDs for state equivalence. * * When old_id == 0, the old register is independent - not linked to any * other register. Any linking in the current state only adds constraints, * making it more restrictive. Since the old state didn't rely on any ID * relationships for this register, it's always safe to accept cur regardless * of its ID. Hence, return true immediately. * * When old_id != 0 but cur_id == 0, we need to ensure that different * independent registers in cur don't incorrectly satisfy the ID matching * requirements of linked registers in old. * * Example: if old has r6.id=X and r7.id=X (linked), but cur has r6.id=0 * and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. * * When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the * base id (flag stripped) must both map consistently. Example: old has * r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag * (r3 derived from unrelated r4). Without the base check, idmap gets two * independent entries A->B and A|flag->C|flag, missing that A->C conflicts * with A->B. The base ID cross-check catches this. */static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap){ if (!old_id) return true; cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; if (!check_ids(old_id, cur_id, idmap)) return false; if (old_id & BPF_ADD_CONST) { old_id &= ~BPF_ADD_CONST; cur_id &= ~BPF_ADD_CONST; if (!check_ids(old_id, cur_id, idmap)) return false; } return true;} static void __clean_func_state(struct bpf_verifier_env *env, struct bpf_func_state *st, u16 live_regs, int frame){ int i, j; for (i = 0; i < BPF_REG_FP; i++) { /* liveness must not touch this register anymore */ if (!(live_regs & BIT(i))) /* since the register is unused, clear its state * to make further comparison simpler */ bpf_mark_reg_not_init(env, &st->regs[i]); } /* * Clean dead 4-byte halves within each SPI independently. * half_spi 2*i → lower half: slot_type[0..3] (closer to FP) * half_spi 2*i+1 → upper half: slot_type[4..7] (farther from FP) */ for (i = 0; i < st->allocated_stack / BPF_REG_SIZE; i++) { bool lo_live = bpf_stack_slot_alive(env, frame, i * 2); bool hi_live = bpf_stack_slot_alive(env, frame, i * 2 + 1); if (!hi_live || !lo_live) { int start = !lo_live ? 0 : BPF_REG_SIZE / 2; int end = !hi_live ? BPF_REG_SIZE : BPF_REG_SIZE / 2; u8 stype = st->stack[i].slot_type[7]; /* * Don't clear special slots. * destroy_if_dynptr_stack_slot() needs STACK_DYNPTR to * detect overwrites and invalidate associated data slices. * is_iter_reg_valid_uninit() and is_irq_flag_reg_valid_uninit() * check for their respective slot types to detect double-create. */ if (stype == STACK_DYNPTR || stype == STACK_ITER || stype == STACK_IRQ_FLAG) continue; /* * Only scalar spills can be degraded to raw stack bytes * when their high half is dead. Pointer spills need the * saved spilled_ptr metadata so partial fills keep * rejecting as non-scalar register fills. */ if (!hi_live) { struct bpf_reg_state *spill = &st->stack[i].spilled_ptr; if (lo_live && stype == STACK_SPILL) { if (spill->type != SCALAR_VALUE) continue; /* * Can't replace with STACK_ZERO, because * that requires bpf_mark_chain_precision(). */ if (bpf_register_is_null(spill)) continue; for (j = 0; j < 4; j++) { u8 *t = &st->stack[i].slot_type[j]; if (*t == STACK_SPILL) *t = STACK_MISC; } } bpf_mark_reg_not_init(env, spill); } for (j = start; j < end; j++) st->stack[i].slot_type[j] = STACK_POISON; } }} static int clean_verifier_state(struct bpf_verifier_env *env, struct bpf_verifier_state *st){ int i, err; err = bpf_live_stack_query_init(env, st); if (err) return err; for (i = 0; i <= st->curframe; i++) { u32 ip = bpf_frame_insn_idx(st, i); u16 live_regs = env->insn_aux_data[ip].live_regs_before; __clean_func_state(env, st->frame[i], live_regs, i); } return 0;} static bool regs_exact(const struct bpf_reg_state *rold, const struct bpf_reg_state *rcur, struct bpf_idmap *idmap){ return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 && check_ids(rold->id, rcur->id, idmap) && check_ids(rold->parent_id, rcur->parent_id, idmap);} enum exact_level { NOT_EXACT, EXACT, RANGE_WITHINLines 1–500 of 1597. Load more
// SPDX-License-Identifier: GPL-2.0-only /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ #include <linux/bpf.h> #include <linux/bpf_verifier.h> #include <linux/cnum.h> #include <linux/filter.h> #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) #define BPF_COMPLEXITY_LIMIT_STATES 64 static bool is_may_goto_insn_at(struct bpf_verifier_env *env, int insn_idx) { return bpf_is_may_goto_insn(&env->prog->insnsi[insn_idx]); } static bool is_iter_next_insn(struct bpf_verifier_env *env, int insn_idx) { return env->insn_aux_data[insn_idx].is_iter_next; } static void update_peak_states(struct bpf_verifier_env *env) { u32 cur_states; cur_states = env->explored_states_size + env->free_list_size + env->num_backedges; env->peak_states = max(env->peak_states, cur_states); } /* struct bpf_verifier_state->parent refers to states * that are in either of env->{expored_states,free_list}. * In both cases the state is contained in struct bpf_verifier_state_list. */ static struct bpf_verifier_state_list *state_parent_as_list(struct bpf_verifier_state *st) { if (st->parent) return container_of(st->parent, struct bpf_verifier_state_list, state); return NULL; } static bool incomplete_read_marks(struct bpf_verifier_env *env, struct bpf_verifier_state *st); /* A state can be freed if it is no longer referenced: * - is in the env->free_list; * - has no children states; */ static void maybe_free_verifier_state(struct bpf_verifier_env *env, struct bpf_verifier_state_list *sl) { if (!sl->in_free_list || sl->state.branches != 0 || incomplete_read_marks(env, &sl->state)) return; list_del(&sl->node); bpf_free_verifier_state(&sl->state, false); kfree(sl); env->free_list_size--; } /* For state @st look for a topmost frame with frame_insn_idx() in some SCC, * if such frame exists form a corresponding @callchain as an array of * call sites leading to this frame and SCC id. * E.g.: * * void foo() { A: loop {... SCC#1 ...}; } * void bar() { B: loop { C: foo(); ... SCC#2 ... } * D: loop { E: foo(); ... SCC#3 ... } } * void main() { F: bar(); } * * @callchain at (A) would be either (F,SCC#2) or (F,SCC#3) depending * on @st frame call sites being (F,C,A) or (F,E,A). */ static bool compute_scc_callchain(struct bpf_verifier_env *env, struct bpf_verifier_state *st, struct bpf_scc_callchain *callchain) { u32 i, scc, insn_idx; memset(callchain, 0, sizeof(*callchain)); for (i = 0; i <= st->curframe; i++) { insn_idx = bpf_frame_insn_idx(st, i); scc = env->insn_aux_data[insn_idx].scc; if (scc) { callchain->scc = scc; break; } else if (i < st->curframe) { callchain->callsites[i] = insn_idx; } else { return false; } } return true; } /* Check if bpf_scc_visit instance for @callchain exists. */ static struct bpf_scc_visit *scc_visit_lookup(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain) { struct bpf_scc_info *info = env->scc_info[callchain->scc]; struct bpf_scc_visit *visits = info->visits; u32 i; if (!info) return NULL; for (i = 0; i < info->num_visits; i++) if (memcmp(callchain, &visits[i].callchain, sizeof(*callchain)) == 0) return &visits[i]; return NULL; } /* Allocate a new bpf_scc_visit instance corresponding to @callchain. * Allocated instances are alive for a duration of the do_check_common() * call and are freed by free_states(). */ static struct bpf_scc_visit *scc_visit_alloc(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain) { struct bpf_scc_visit *visit; struct bpf_scc_info *info; u32 scc, num_visits; u64 new_sz; scc = callchain->scc; info = env->scc_info[scc]; num_visits = info ? info->num_visits : 0; new_sz = sizeof(*info) + sizeof(struct bpf_scc_visit) * (num_visits + 1); info = kvrealloc(env->scc_info[scc], new_sz, GFP_KERNEL_ACCOUNT); if (!info) return NULL; env->scc_info[scc] = info; info->num_visits = num_visits + 1; visit = &info->visits[num_visits]; memset(visit, 0, sizeof(*visit)); memcpy(&visit->callchain, callchain, sizeof(*callchain)); return visit; } /* Form a string '(callsite#1,callsite#2,...,scc)' in env->tmp_str_buf */ static char *format_callchain(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain) { char *buf = env->tmp_str_buf; int i, delta = 0; delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "("); for (i = 0; i < ARRAY_SIZE(callchain->callsites); i++) { if (!callchain->callsites[i]) break; delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "%u,", callchain->callsites[i]); } delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "%u)", callchain->scc); return env->tmp_str_buf; } /* If callchain for @st exists (@st is in some SCC), ensure that * bpf_scc_visit instance for this callchain exists. * If instance does not exist or is empty, assign visit->entry_state to @st. */ static int maybe_enter_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st) { struct bpf_scc_callchain *callchain = &env->callchain_buf; struct bpf_scc_visit *visit; if (!compute_scc_callchain(env, st, callchain)) return 0; visit = scc_visit_lookup(env, callchain); visit = visit ?: scc_visit_alloc(env, callchain); if (!visit) return -ENOMEM; if (!visit->entry_state) { visit->entry_state = st; if (env->log.level & BPF_LOG_LEVEL2) verbose(env, "SCC enter %s\n", format_callchain(env, callchain)); } return 0; } static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visit *visit); /* If callchain for @st exists (@st is in some SCC), make it empty: * - set visit->entry_state to NULL; * - flush accumulated backedges. */ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st) { struct bpf_scc_callchain *callchain = &env->callchain_buf; struct bpf_scc_visit *visit; if (!compute_scc_callchain(env, st, callchain)) return 0; visit = scc_visit_lookup(env, callchain); if (!visit) { /* * If path traversal stops inside an SCC, corresponding bpf_scc_visit * must exist for non-speculative paths. For non-speculative paths * traversal stops when: * a. Verification error is found, maybe_exit_scc() is not called. * b. Top level BPF_EXIT is reached. Top level BPF_EXIT is not a member * of any SCC. * c. A checkpoint is reached and matched. Checkpoints are created by * is_state_visited(), which calls maybe_enter_scc(), which allocates * bpf_scc_visit instances for checkpoints within SCCs. * (c) is the only case that can reach this point. */ if (!st->speculative) { verifier_bug(env, "scc exit: no visit info for call chain %s", format_callchain(env, callchain)); return -EFAULT; } return 0; } if (visit->entry_state != st) return 0; if (env->log.level & BPF_LOG_LEVEL2) verbose(env, "SCC exit %s\n", format_callchain(env, callchain)); visit->entry_state = NULL; env->num_backedges -= visit->num_backedges; visit->num_backedges = 0; update_peak_states(env); return propagate_backedges(env, visit); } /* Lookup an bpf_scc_visit instance corresponding to @st callchain * and add @backedge to visit->backedges. @st callchain must exist. */ static int add_scc_backedge(struct bpf_verifier_env *env, struct bpf_verifier_state *st, struct bpf_scc_backedge *backedge) { struct bpf_scc_callchain *callchain = &env->callchain_buf; struct bpf_scc_visit *visit; if (!compute_scc_callchain(env, st, callchain)) { verifier_bug(env, "add backedge: no SCC in verification path, insn_idx %d", st->insn_idx); return -EFAULT; } visit = scc_visit_lookup(env, callchain); if (!visit) { verifier_bug(env, "add backedge: no visit info for call chain %s", format_callchain(env, callchain)); return -EFAULT; } if (env->log.level & BPF_LOG_LEVEL2) verbose(env, "SCC backedge %s\n", format_callchain(env, callchain)); backedge->next = visit->backedges; visit->backedges = backedge; visit->num_backedges++; env->num_backedges++; update_peak_states(env); return 0; } /* bpf_reg_state->live marks for registers in a state @st are incomplete, * if state @st is in some SCC and not all execution paths starting at this * SCC are fully explored. */ static bool incomplete_read_marks(struct bpf_verifier_env *env, struct bpf_verifier_state *st) { struct bpf_scc_callchain *callchain = &env->callchain_buf; struct bpf_scc_visit *visit; if (!compute_scc_callchain(env, st, callchain)) return false; visit = scc_visit_lookup(env, callchain); if (!visit) return false; return !!visit->backedges; } int bpf_update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st) { struct bpf_verifier_state_list *sl = NULL, *parent_sl; struct bpf_verifier_state *parent; int err; while (st) { u32 br = --st->branches; /* verifier_bug_if(br > 1, ...) technically makes sense here, * but see comment in push_stack(), hence: */ verifier_bug_if((int)br < 0, env, "%s:branches_to_explore=%d", __func__, br); if (br) break; err = maybe_exit_scc(env, st); if (err) return err; parent = st->parent; parent_sl = state_parent_as_list(st); if (sl) maybe_free_verifier_state(env, sl); st = parent; sl = parent_sl; } return 0; } /* check %cur's range satisfies %old's */ static bool range_within(const struct bpf_reg_state *old, const struct bpf_reg_state *cur) { return cnum64_is_subset(old->r64, cur->r64) && cnum32_is_subset(old->r32, cur->r32); } /* If in the old state two registers had the same id, then they need to have * the same id in the new state as well. But that id could be different from * the old state, so we need to track the mapping from old to new ids. * Once we have seen that, say, a reg with old id 5 had new id 9, any subsequent * regs with old id 5 must also have new id 9 for the new state to be safe. But * regs with a different old id could still have new id 9, we don't care about * that. * So we look through our idmap to see if this old id has been seen before. If * so, we require the new id to match; otherwise, we add the id pair to the map. */ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) { struct bpf_id_pair *map = idmap->map; unsigned int i; /* either both IDs should be set or both should be zero */ if (!!old_id != !!cur_id) return false; if (old_id == 0) /* cur_id == 0 as well */ return true; for (i = 0; i < idmap->cnt; i++) { if (map[i].old == old_id) return map[i].cur == cur_id; if (map[i].cur == cur_id) return false; } /* Reached the end of known mappings; haven't seen this id before */ if (idmap->cnt < BPF_ID_MAP_SIZE) { map[idmap->cnt].old = old_id; map[idmap->cnt].cur = cur_id; idmap->cnt++; return true; } /* * idmap slots are bounded by the number of registers and stack slots. * Since referenced dynptrs acquire intermediate references that do * not live in either, so the map can be exhausted. Since it is unlikely, * fail the verification by treating the states as not equivalent. */ return false; } /* * Compare scalar register IDs for state equivalence. * * When old_id == 0, the old register is independent - not linked to any * other register. Any linking in the current state only adds constraints, * making it more restrictive. Since the old state didn't rely on any ID * relationships for this register, it's always safe to accept cur regardless * of its ID. Hence, return true immediately. * * When old_id != 0 but cur_id == 0, we need to ensure that different * independent registers in cur don't incorrectly satisfy the ID matching * requirements of linked registers in old. * * Example: if old has r6.id=X and r7.id=X (linked), but cur has r6.id=0 * and r7.id=0 (both independent), without temp IDs both would map old_id=X * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map * X->temp2, but X is already mapped to temp1, so the check fails correctly. * * When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the * base id (flag stripped) must both map consistently. Example: old has * r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag * (r3 derived from unrelated r4). Without the base check, idmap gets two * independent entries A->B and A|flag->C|flag, missing that A->C conflicts * with A->B. The base ID cross-check catches this. */ static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) { if (!old_id) return true; cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; if (!check_ids(old_id, cur_id, idmap)) return false; if (old_id & BPF_ADD_CONST) { old_id &= ~BPF_ADD_CONST; cur_id &= ~BPF_ADD_CONST; if (!check_ids(old_id, cur_id, idmap)) return false; } return true; } static void __clean_func_state(struct bpf_verifier_env *env, struct bpf_func_state *st, u16 live_regs, int frame) { int i, j; for (i = 0; i < BPF_REG_FP; i++) { /* liveness must not touch this register anymore */ if (!(live_regs & BIT(i))) /* since the register is unused, clear its state * to make further comparison simpler */ bpf_mark_reg_not_init(env, &st->regs[i]); } /* * Clean dead 4-byte halves within each SPI independently. * half_spi 2*i → lower half: slot_type[0..3] (closer to FP) * half_spi 2*i+1 → upper half: slot_type[4..7] (farther from FP) */ for (i = 0; i < st->allocated_stack / BPF_REG_SIZE; i++) { bool lo_live = bpf_stack_slot_alive(env, frame, i * 2); bool hi_live = bpf_stack_slot_alive(env, frame, i * 2 + 1); if (!hi_live || !lo_live) { int start = !lo_live ? 0 : BPF_REG_SIZE / 2; int end = !hi_live ? BPF_REG_SIZE : BPF_REG_SIZE / 2; u8 stype = st->stack[i].slot_type[7]; /* * Don't clear special slots. * destroy_if_dynptr_stack_slot() needs STACK_DYNPTR to * detect overwrites and invalidate associated data slices. * is_iter_reg_valid_uninit() and is_irq_flag_reg_valid_uninit() * check for their respective slot types to detect double-create. */ if (stype == STACK_DYNPTR || stype == STACK_ITER || stype == STACK_IRQ_FLAG) continue; /* * Only scalar spills can be degraded to raw stack bytes * when their high half is dead. Pointer spills need the * saved spilled_ptr metadata so partial fills keep * rejecting as non-scalar register fills. */ if (!hi_live) { struct bpf_reg_state *spill = &st->stack[i].spilled_ptr; if (lo_live && stype == STACK_SPILL) { if (spill->type != SCALAR_VALUE) continue; /* * Can't replace with STACK_ZERO, because * that requires bpf_mark_chain_precision(). */ if (bpf_register_is_null(spill)) continue; for (j = 0; j < 4; j++) { u8 *t = &st->stack[i].slot_type[j]; if (*t == STACK_SPILL) *t = STACK_MISC; } } bpf_mark_reg_not_init(env, spill); } for (j = start; j < end; j++) st->stack[i].slot_type[j] = STACK_POISON; } } } static int clean_verifier_state(struct bpf_verifier_env *env, struct bpf_verifier_state *st) { int i, err; err = bpf_live_stack_query_init(env, st); if (err) return err; for (i = 0; i <= st->curframe; i++) { u32 ip = bpf_frame_insn_idx(st, i); u16 live_regs = env->insn_aux_data[ip].live_regs_before; __clean_func_state(env, st->frame[i], live_regs, i); } return 0; } static bool regs_exact(const struct bpf_reg_state *rold, const struct bpf_reg_state *rcur, struct bpf_idmap *idmap) { return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 && check_ids(rold->id, rcur->id, idmap) && check_ids(rold->parent_id, rcur->parent_id, idmap); } enum exact_level { NOT_EXACT, EXACT, RANGE_WITHIN