path: root/kernel/bpf/const_fold.c

// SPDX-License-Identifier: GPL-2.0-only
/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */

#include <linux/bpf_verifier.h>

/*
 * Forward dataflow analysis to determine constant register values at every
 * instruction. Tracks 64-bit constant values in R0-R9 through the program,
 * using a fixed-point iteration in reverse postorder. Records which registers
 * hold known constants and their values in
 * env->insn_aux_data[].{const_reg_mask, const_reg_vals}.
 */

enum const_arg_state {
	CONST_ARG_UNVISITED,	/* instruction not yet reached */
	CONST_ARG_UNKNOWN,	/* register value not a known constant */
	CONST_ARG_CONST,	/* register holds a known 64-bit constant */
	CONST_ARG_MAP_PTR,	/* register holds a map pointer, map_index is set */
	CONST_ARG_MAP_VALUE,	/* register points to map value data, val is offset */
	CONST_ARG_SUBPROG,	/* register holds a subprog pointer, val is subprog number */
};

struct const_arg_info {
	enum const_arg_state state;
	u32 map_index;
	u64 val;
};

static bool ci_is_unvisited(const struct const_arg_info *ci)
{
	return ci->state == CONST_ARG_UNVISITED;
}

static bool ci_is_unknown(const struct const_arg_info *ci)
{
	return ci->state == CONST_ARG_UNKNOWN;
}

static bool ci_is_const(const struct const_arg_info *ci)
{
	return ci->state == CONST_ARG_CONST;
}

static bool ci_is_map_value(const struct const_arg_info *ci)
{
	return ci->state == CONST_ARG_MAP_VALUE;
}

/* Transfer function: compute output register state from instruction. */
static void const_reg_xfer(struct bpf_verifier_env *env, struct const_arg_info *ci_out,
			   struct bpf_insn *insn, struct bpf_insn *insns, int idx)
{
	struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };
	struct const_arg_info *dst = &ci_out[insn->dst_reg];
	struct const_arg_info *src = &ci_out[insn->src_reg];
	u8 class = BPF_CLASS(insn->code);
	u8 mode = BPF_MODE(insn->code);
	u8 opcode = BPF_OP(insn->code) | BPF_SRC(insn->code);
	int r;

	switch (class) {
	case BPF_ALU:
	case BPF_ALU64:
		switch (opcode) {
		case BPF_MOV | BPF_K:
			dst->state = CONST_ARG_CONST;
			dst->val = (s64)insn->imm;
			break;
		case BPF_MOV | BPF_X:
			*dst = *src;
			if (!insn->off)
				break;
			if (!ci_is_const(dst)) {
				*dst = unknown;
				break;
			}
			switch (insn->off) {
			case 8:  dst->val = (s8)dst->val; break;
			case 16: dst->val = (s16)dst->val; break;
			case 32: dst->val = (s32)dst->val; break;
			default: *dst = unknown; break;
			}
			break;
		case BPF_ADD | BPF_K:
			if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
				*dst = unknown;
				break;
			}
			dst->val += insn->imm;
			break;
		case BPF_SUB | BPF_K:
			if (!ci_is_const(dst) && !ci_is_map_value(dst)) {
				*dst = unknown;
				break;
			}
			dst->val -= insn->imm;
			break;
		case BPF_AND | BPF_K:
			if (!ci_is_const(dst)) {
				if (!insn->imm) {
					dst->state = CONST_ARG_CONST;
					dst->val = 0;
				} else {
					*dst = unknown;
				}
				break;
			}
			dst->val &= (s64)insn->imm;
			break;
		case BPF_AND | BPF_X:
			if (ci_is_const(dst) && dst->val == 0)
				break; /* 0 & x == 0 */
			if (ci_is_const(src) && src->val == 0) {
				dst->state = CONST_ARG_CONST;
				dst->val = 0;
				break;
			}
			if (!ci_is_const(dst) || !ci_is_const(src)) {
				*dst = unknown;
				break;
			}
			dst->val &= src->val;
			break;
		default:
			*dst = unknown;
			break;
		}
		if (class == BPF_ALU) {
			if (ci_is_const(dst))
				dst->val = (u32)dst->val;
			else if (!ci_is_unknown(dst))
				*dst = unknown;
		}
		break;
	case BPF_LD:
		if (mode == BPF_ABS || mode == BPF_IND)
			goto process_call;
		if (mode != BPF_IMM || BPF_SIZE(insn->code) != BPF_DW)
			break;
		if (insn->src_reg == BPF_PSEUDO_FUNC) {
			int subprog = bpf_find_subprog(env, idx + insn->imm + 1);

			if (subprog >= 0) {
				dst->state = CONST_ARG_SUBPROG;
				dst->val = subprog;
			} else {
				*dst = unknown;
			}
		} else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE ||
			   insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE) {
			dst->state = CONST_ARG_MAP_VALUE;
			dst->map_index = env->insn_aux_data[idx].map_index;
			dst->val = env->insn_aux_data[idx].map_off;
		} else if (insn->src_reg == BPF_PSEUDO_MAP_FD ||
			   insn->src_reg == BPF_PSEUDO_MAP_IDX) {
			dst->state = CONST_ARG_MAP_PTR;
			dst->map_index = env->insn_aux_data[idx].map_index;
		} else if (insn->src_reg == 0) {
			dst->state = CONST_ARG_CONST;
			dst->val = (u64)(u32)insn->imm | ((u64)(u32)insns[idx + 1].imm << 32);
		} else {
			*dst = unknown;
		}
		break;
	case BPF_LDX:
		if (!ci_is_map_value(src)) {
			*dst = unknown;
			break;
		}
		struct bpf_map *map = env->used_maps[src->map_index];
		int size = bpf_size_to_bytes(BPF_SIZE(insn->code));
		bool is_ldsx = mode == BPF_MEMSX;
		int off = src->val + insn->off;
		u64 val = 0;

		if (!bpf_map_is_rdonly(map) || !map->ops->map_direct_value_addr ||
		    map->map_type == BPF_MAP_TYPE_INSN_ARRAY ||
		    off < 0 || off + size > map->value_size ||
		    bpf_map_direct_read(map, off, size, &val, is_ldsx)) {
			*dst = unknown;
			break;
		}
		dst->state = CONST_ARG_CONST;
		dst->val = val;
		break;
	case BPF_JMP:
		if (opcode != BPF_CALL)
			break;
process_call:
		for (r = BPF_REG_0; r <= BPF_REG_5; r++)
			ci_out[r] = unknown;
		break;
	case BPF_STX:
		if (mode != BPF_ATOMIC)
			break;
		if (insn->imm == BPF_CMPXCHG)
			ci_out[BPF_REG_0] = unknown;
		else if (insn->imm == BPF_LOAD_ACQ)
			*dst = unknown;
		else if (in