path: root/kernel/bpf/states.c

// 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/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