// 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; 	/* Stack arg stores (r11-based) are outside the tracked register set. */	if (is_stack_arg_st(insn) || is_stack_arg_stx(insn))		return;	if (is_stack_arg_ldx(insn)) {		ci_out[insn->dst_reg] = unknown;		return;	} 	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 (insn->imm & BPF_FETCH)			*src = unknown;		break;	}} /* Join function: merge output state into a successor's input state. */static bool const_reg_join(struct const_arg_info *ci_target,			   struct const_arg_info *ci_out){	bool changed = false;	int r; 	for (r = 0; r < MAX_BPF_REG; r++) {		struct const_arg_info *old = &ci_target[r];		struct const_arg_info *new = &ci_out[r]; 		if (ci_is_unvisited(old) && !ci_is_unvisited(new)) {			ci_target[r] = *new;			changed = true;		} else if (!ci_is_unknown(old) && !ci_is_unvisited(old) &&			   (new->state != old->state || new->val != old->val ||			    new->map_index != old->map_index)) {			old->state = CONST_ARG_UNKNOWN;			changed = true;		}	}	return changed;} int bpf_compute_const_regs(struct bpf_verifier_env *env){	struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };	struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;	struct bpf_insn *insns = env->prog->insnsi;	int insn_cnt = env->prog->len;	struct const_arg_info (*ci_in)[MAX_BPF_REG];	struct const_arg_info ci_out[MAX_BPF_REG];	struct bpf_iarray *succ;	bool changed;	int i, r; 	/* kvzalloc zeroes memory, so all entries start as CONST_ARG_UNVISITED (0) */	ci_in = kvzalloc_objs(*ci_in, insn_cnt, GFP_KERNEL_ACCOUNT);	if (!ci_in)		return -ENOMEM; 	/* Subprogram entries (including main at subprog 0): all registers unknown */	for (i = 0; i < env->subprog_cnt; i++) {		int start = env->subprog_info[i].start; 		for (r = 0; r < MAX_BPF_REG; r++)			ci_in[start][r] = unknown;	} redo:	changed = false;	for (i = env->cfg.cur_postorder - 1; i >= 0; i--) {		int idx = env->cfg.insn_postorder[i];		struct bpf_insn *insn = &insns[idx];		struct const_arg_info *ci = ci_in[idx]; 		memcpy(ci_out, ci, sizeof(ci_out)); 		const_reg_xfer(env, ci_out, insn, insns, idx); 		succ = bpf_insn_successors(env, idx);		for (int s = 0; s < succ->cnt; s++)			changed |= const_reg_join(ci_in[succ->items[s]], ci_out);	}	if (changed)		goto redo; 	/* Save computed constants into insn_aux[] if they fit into 32-bit */	for (i = 0; i < insn_cnt; i++) {		u16 mask = 0, map_mask = 0, subprog_mask = 0;		struct bpf_insn_aux_data *aux = &insn_aux[i];		struct const_arg_info *ci = ci_in[i]; 		for (r = BPF_REG_0; r < ARRAY_SIZE(aux->const_reg_vals); r++) {			struct const_arg_info *c = &ci[r]; 			switch (c->state) {			case CONST_ARG_CONST: {				u64 val = c->val; 				if (val != (u32)val)					break;				mask |= BIT(r);				aux->const_reg_vals[r] = val;				break;			}			case CONST_ARG_MAP_PTR:				map_mask |= BIT(r);				aux->const_reg_vals[r] = c->map_index;				break;			case CONST_ARG_SUBPROG:				subprog_mask |= BIT(r);				aux->const_reg_vals[r] = c->val;				break;			default:				break;			}		}		aux->const_reg_mask = mask;		aux->const_reg_map_mask = map_mask;		aux->const_reg_subprog_mask = subprog_mask;	} 	kvfree(ci_in);	return 0;} static int eval_const_branch(u8 opcode, u64 dst_val, u64 src_val){	switch (BPF_OP(opcode)) {	case BPF_JEQ:	return dst_val == src_val;	case BPF_JNE:	return dst_val != src_val;	case BPF_JGT:	return dst_val > src_val;	case BPF_JGE:	return dst_val >= src_val;	case BPF_JLT:	return dst_val < src_val;	case BPF_JLE:	return dst_val <= src_val;	case BPF_JSGT:	return (s64)dst_val > (s64)src_val;	case BPF_JSGE:	return (s64)dst_val >= (s64)src_val;	case BPF_JSLT:	return (s64)dst_val < (s64)src_val;	case BPF_JSLE:	return (s64)dst_val <= (s64)src_val;	case BPF_JSET:	return (bool)(dst_val & src_val);	default:	return -1;	}} /* * Rewrite conditional branches with constant outcomes into unconditional * jumps using register values resolved by bpf_compute_const_regs() pass. * This eliminates dead edges from the CFG so that compute_live_registers() * doesn't propagate liveness through dead code. */int bpf_prune_dead_branches(struct bpf_verifier_env *env){	struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;	struct bpf_insn *insns = env->prog->insnsi;	int insn_cnt = env->prog->len;	bool changed = false;	int i; 	for (i = 0; i < insn_cnt; i++) {		struct bpf_insn_aux_data *aux = &insn_aux[i];		struct bpf_insn *insn = &insns[i];		u8 class = BPF_CLASS(insn->code);		u64 dst_val, src_val;		int taken; 		if (!bpf_insn_is_cond_jump(insn->code))			continue;		if (bpf_is_may_goto_insn(insn))			continue; 		if (!(aux->const_reg_mask & BIT(insn->dst_reg)))			continue;		dst_val = aux->const_reg_vals[insn->dst_reg]; 		if (BPF_SRC(insn->code) == BPF_K) {			src_val = insn->imm;		} else {			if (!(aux->const_reg_mask & BIT(insn->src_reg)))				continue;			src_val = aux->const_reg_vals[insn->src_reg];		} 		if (class == BPF_JMP32) {			/*			 * The (s32) cast maps the 32-bit range into two u64 sub-ranges:			 * [0x00000000, 0x7FFFFFFF] -> [0x0000000000000000, 0x000000007FFFFFFF]			 * [0x80000000, 0xFFFFFFFF] -> [0xFFFFFFFF80000000, 0xFFFFFFFFFFFFFFFF]			 * The ordering is preserved within each sub-range, and			 * the second sub-range is above the first as u64.			 */			dst_val = (s32)dst_val;			src_val = (s32)src_val;		} 		taken = eval_const_branch(insn->code, dst_val, src_val);		if (taken < 0) {			bpf_log(&env->log, "Unknown conditional jump %x\n", insn->code);			return -EFAULT;		}		*insn = BPF_JMP_A(taken ? insn->off : 0);		changed = true;	} 	if (!changed)		return 0;	/* recompute postorder, since CFG has changed */	kvfree(env->cfg.insn_postorder);	env->cfg.insn_postorder = NULL;	return bpf_compute_postorder(env);}