1 // SPDX-License-Identifier: GPL-2.0-only 2 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ 3 4 #include <linux/bpf_verifier.h> 5 6 /* 7 * Forward dataflow analysis to determine constant register values at every 8 * instruction. Tracks 64-bit constant values in R0-R9 through the program, 9 * using a fixed-point iteration in reverse postorder. Records which registers 10 * hold known constants and their values in 11 * env->insn_aux_data[].{const_reg_mask, const_reg_vals}. 12 */ 13 14 enum const_arg_state { 15 CONST_ARG_UNVISITED, /* instruction not yet reached */ 16 CONST_ARG_UNKNOWN, /* register value not a known constant */ 17 CONST_ARG_CONST, /* register holds a known 64-bit constant */ 18 CONST_ARG_MAP_PTR, /* register holds a map pointer, map_index is set */ 19 CONST_ARG_MAP_VALUE, /* register points to map value data, val is offset */ 20 CONST_ARG_SUBPROG, /* register holds a subprog pointer, val is subprog number */ 21 }; 22 23 struct const_arg_info { 24 enum const_arg_state state; 25 u32 map_index; 26 u64 val; 27 }; 28 29 static bool ci_is_unvisited(const struct const_arg_info *ci) 30 { 31 return ci->state == CONST_ARG_UNVISITED; 32 } 33 34 static bool ci_is_unknown(const struct const_arg_info *ci) 35 { 36 return ci->state == CONST_ARG_UNKNOWN; 37 } 38 39 static bool ci_is_const(const struct const_arg_info *ci) 40 { 41 return ci->state == CONST_ARG_CONST; 42 } 43 44 static bool ci_is_map_value(const struct const_arg_info *ci) 45 { 46 return ci->state == CONST_ARG_MAP_VALUE; 47 } 48 49 /* Transfer function: compute output register state from instruction. */ 50 static void const_reg_xfer(struct bpf_verifier_env *env, struct const_arg_info *ci_out, 51 struct bpf_insn *insn, struct bpf_insn *insns, int idx) 52 { 53 struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 }; 54 struct const_arg_info *dst = &ci_out[insn->dst_reg]; 55 struct const_arg_info *src = &ci_out[insn->src_reg]; 56 u8 class = BPF_CLASS(insn->code); 57 u8 mode = BPF_MODE(insn->code); 58 u8 opcode = BPF_OP(insn->code) | BPF_SRC(insn->code); 59 int r; 60 61 /* Stack arg stores (r11-based) are outside the tracked register set. */ 62 if (is_stack_arg_st(insn) || is_stack_arg_stx(insn)) 63 return; 64 if (is_stack_arg_ldx(insn)) { 65 ci_out[insn->dst_reg] = unknown; 66 return; 67 } 68 69 switch (class) { 70 case BPF_ALU: 71 case BPF_ALU64: 72 switch (opcode) { 73 case BPF_MOV | BPF_K: 74 dst->state = CONST_ARG_CONST; 75 dst->val = (s64)insn->imm; 76 break; 77 case BPF_MOV | BPF_X: 78 *dst = *src; 79 if (!insn->off) 80 break; 81 if (!ci_is_const(dst)) { 82 *dst = unknown; 83 break; 84 } 85 switch (insn->off) { 86 case 8: dst->val = (s8)dst->val; break; 87 case 16: dst->val = (s16)dst->val; break; 88 case 32: dst->val = (s32)dst->val; break; 89 default: *dst = unknown; break; 90 } 91 break; 92 case BPF_ADD | BPF_K: 93 if (!ci_is_const(dst) && !ci_is_map_value(dst)) { 94 *dst = unknown; 95 break; 96 } 97 dst->val += insn->imm; 98 break; 99 case BPF_SUB | BPF_K: 100 if (!ci_is_const(dst) && !ci_is_map_value(dst)) { 101 *dst = unknown; 102 break; 103 } 104 dst->val -= insn->imm; 105 break; 106 case BPF_AND | BPF_K: 107 if (!ci_is_const(dst)) { 108 if (!insn->imm) { 109 dst->state = CONST_ARG_CONST; 110 dst->val = 0; 111 } else { 112 *dst = unknown; 113 } 114 break; 115 } 116 dst->val &= (s64)insn->imm; 117 break; 118 case BPF_AND | BPF_X: 119 if (ci_is_const(dst) && dst->val == 0) 120 break; /* 0 & x == 0 */ 121 if (ci_is_const(src) && src->val == 0) { 122 dst->state = CONST_ARG_CONST; 123 dst->val = 0; 124 break; 125 } 126 if (!ci_is_const(dst) || !ci_is_const(src)) { 127 *dst = unknown; 128 break; 129 } 130 dst->val &= src->val; 131 break; 132 default: 133 *dst = unknown; 134 break; 135 } 136 if (class == BPF_ALU) { 137 if (ci_is_const(dst)) 138 dst->val = (u32)dst->val; 139 else if (!ci_is_unknown(dst)) 140 *dst = unknown; 141 } 142 break; 143 case BPF_LD: 144 if (mode == BPF_ABS || mode == BPF_IND) 145 goto process_call; 146 if (mode != BPF_IMM || BPF_SIZE(insn->code) != BPF_DW) 147 break; 148 if (insn->src_reg == BPF_PSEUDO_FUNC) { 149 int subprog = bpf_find_subprog(env, idx + insn->imm + 1); 150 151 if (subprog >= 0) { 152 dst->state = CONST_ARG_SUBPROG; 153 dst->val = subprog; 154 } else { 155 *dst = unknown; 156 } 157 } else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE || 158 insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE) { 159 dst->state = CONST_ARG_MAP_VALUE; 160 dst->map_index = env->insn_aux_data[idx].map_index; 161 dst->val = env->insn_aux_data[idx].map_off; 162 } else if (insn->src_reg == BPF_PSEUDO_MAP_FD || 163 insn->src_reg == BPF_PSEUDO_MAP_IDX) { 164 dst->state = CONST_ARG_MAP_PTR; 165 dst->map_index = env->insn_aux_data[idx].map_index; 166 } else if (insn->src_reg == 0) { 167 dst->state = CONST_ARG_CONST; 168 dst->val = (u64)(u32)insn->imm | ((u64)(u32)insns[idx + 1].imm << 32); 169 } else { 170 *dst = unknown; 171 } 172 break; 173 case BPF_LDX: 174 if (!ci_is_map_value(src)) { 175 *dst = unknown; 176 break; 177 } 178 struct bpf_map *map = env->used_maps[src->map_index]; 179 int size = bpf_size_to_bytes(BPF_SIZE(insn->code)); 180 bool is_ldsx = mode == BPF_MEMSX; 181 int off = src->val + insn->off; 182 u64 val = 0; 183 u32 cnt; 184 185 if (!bpf_map_is_rdonly(map) || !map->ops->map_direct_value_addr || 186 off < 0 || off + size > map->value_size || 187 /* so are the addresses of functions that the map points to */ 188 bpf_map_range_func_ptrs(env, map, off, size, &cnt) || 189 bpf_map_direct_read(map, off, size, &val, is_ldsx)) { 190 *dst = unknown; 191 break; 192 } 193 dst->state = CONST_ARG_CONST; 194 dst->val = val; 195 break; 196 case BPF_JMP: 197 /* both 'call imm' and 'callx reg' clobber caller saved registers */ 198 if (BPF_OP(insn->code) != BPF_CALL) 199 break; 200 process_call: 201 for (r = BPF_REG_0; r <= BPF_REG_5; r++) 202 ci_out[r] = unknown; 203 break; 204 case BPF_STX: 205 r = bpf_atomic_load_reg(insn); 206 if (r >= 0) 207 ci_out[r] = unknown; 208 break; 209 } 210 } 211 212 /* Join function: merge output state into a successor's input state. */ 213 static bool const_reg_join(struct const_arg_info *ci_target, 214 struct const_arg_info *ci_out) 215 { 216 bool changed = false; 217 int r; 218 219 for (r = 0; r < MAX_BPF_REG; r++) { 220 struct const_arg_info *old = &ci_target[r]; 221 struct const_arg_info *new = &ci_out[r]; 222 223 if (ci_is_unvisited(old) && !ci_is_unvisited(new)) { 224 ci_target[r] = *new; 225 changed = true; 226 } else if (!ci_is_unknown(old) && !ci_is_unvisited(old) && 227 (new->state != old->state || new->val != old->val || 228 new->map_index != old->map_index)) { 229 old->state = CONST_ARG_UNKNOWN; 230 changed = true; 231 } 232 } 233 return changed; 234 } 235 236 int bpf_compute_const_regs(struct bpf_verifier_env *env) 237 { 238 struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 }; 239 struct bpf_insn_aux_data *insn_aux = env->insn_aux_data; 240 struct bpf_insn *insns = env->prog->insnsi; 241 int insn_cnt = env->prog->len; 242 struct const_arg_info (*ci_in)[MAX_BPF_REG]; 243 struct const_arg_info ci_out[MAX_BPF_REG]; 244 struct bpf_iarray *succ; 245 bool changed; 246 int i, r; 247 248 /* kvzalloc zeroes memory, so all entries start as CONST_ARG_UNVISITED (0) */ 249 ci_in = kvzalloc_objs(*ci_in, insn_cnt, GFP_KERNEL_ACCOUNT); 250 if (!ci_in) 251 return -ENOMEM; 252 253 /* Subprogram entries (including main at subprog 0): all registers unknown */ 254 for (i = 0; i < env->subprog_cnt; i++) { 255 int start = env->subprog_info[i].start; 256 257 for (r = 0; r < MAX_BPF_REG; r++) 258 ci_in[start][r] = unknown; 259 } 260 261 redo: 262 changed = false; 263 for (i = env->cfg.cur_postorder - 1; i >= 0; i--) { 264 int idx = env->cfg.insn_postorder[i]; 265 struct bpf_insn *insn = &insns[idx]; 266 struct const_arg_info *ci = ci_in[idx]; 267 268 memcpy(ci_out, ci, sizeof(ci_out)); 269 270 const_reg_xfer(env, ci_out, insn, insns, idx); 271 272 succ = bpf_insn_successors(env, idx); 273 for (int s = 0; s < succ->cnt; s++) 274 changed |= const_reg_join(ci_in[succ->items[s]], ci_out); 275 } 276 if (changed) 277 goto redo; 278 279 /* Save computed constants into insn_aux[] if they fit into 32-bit */ 280 for (i = 0; i < insn_cnt; i++) { 281 u16 mask = 0, map_mask = 0, subprog_mask = 0; 282 struct bpf_insn_aux_data *aux = &insn_aux[i]; 283 struct const_arg_info *ci = ci_in[i]; 284 285 for (r = BPF_REG_0; r < ARRAY_SIZE(aux->const_reg_vals); r++) { 286 struct const_arg_info *c = &ci[r]; 287 288 switch (c->state) { 289 case CONST_ARG_CONST: { 290 u64 val = c->val; 291 292 if (val != (u32)val) 293 break; 294 mask |= BIT(r); 295 aux->const_reg_vals[r] = val; 296 break; 297 } 298 case CONST_ARG_MAP_PTR: 299 map_mask |= BIT(r); 300 aux->const_reg_vals[r] = c->map_index; 301 break; 302 case CONST_ARG_SUBPROG: 303 subprog_mask |= BIT(r); 304 aux->const_reg_vals[r] = c->val; 305 break; 306 default: 307 break; 308 } 309 } 310 aux->const_reg_mask = mask; 311 aux->const_reg_map_mask = map_mask; 312 aux->const_reg_subprog_mask = subprog_mask; 313 } 314 315 kvfree(ci_in); 316 return 0; 317 } 318 319 static int eval_const_branch(u8 opcode, u64 dst_val, u64 src_val) 320 { 321 switch (BPF_OP(opcode)) { 322 case BPF_JEQ: return dst_val == src_val; 323 case BPF_JNE: return dst_val != src_val; 324 case BPF_JGT: return dst_val > src_val; 325 case BPF_JGE: return dst_val >= src_val; 326 case BPF_JLT: return dst_val < src_val; 327 case BPF_JLE: return dst_val <= src_val; 328 case BPF_JSGT: return (s64)dst_val > (s64)src_val; 329 case BPF_JSGE: return (s64)dst_val >= (s64)src_val; 330 case BPF_JSLT: return (s64)dst_val < (s64)src_val; 331 case BPF_JSLE: return (s64)dst_val <= (s64)src_val; 332 case BPF_JSET: return (bool)(dst_val & src_val); 333 default: return -1; 334 } 335 } 336 337 /* 338 * Rewrite conditional branches with constant outcomes into unconditional 339 * jumps using register values resolved by bpf_compute_const_regs() pass. 340 * This eliminates dead edges from the CFG so that compute_live_registers() 341 * doesn't propagate liveness through dead code. 342 */ 343 int bpf_prune_dead_branches(struct bpf_verifier_env *env) 344 { 345 struct bpf_insn_aux_data *insn_aux = env->insn_aux_data; 346 struct bpf_insn *insns = env->prog->insnsi; 347 int insn_cnt = env->prog->len; 348 bool changed = false; 349 int i; 350 351 for (i = 0; i < insn_cnt; i++) { 352 struct bpf_insn_aux_data *aux = &insn_aux[i]; 353 struct bpf_insn *insn = &insns[i]; 354 u8 class = BPF_CLASS(insn->code); 355 u64 dst_val, src_val; 356 int taken; 357 358 if (!bpf_insn_is_cond_jump(insn->code)) 359 continue; 360 if (BPF_OP(insn->code) == BPF_JCOND) 361 continue; 362 363 if (!(aux->const_reg_mask & BIT(insn->dst_reg))) 364 continue; 365 dst_val = aux->const_reg_vals[insn->dst_reg]; 366 367 if (BPF_SRC(insn->code) == BPF_K) { 368 src_val = insn->imm; 369 } else { 370 if (!(aux->const_reg_mask & BIT(insn->src_reg))) 371 continue; 372 src_val = aux->const_reg_vals[insn->src_reg]; 373 } 374 375 if (class == BPF_JMP32) { 376 /* 377 * The (s32) cast maps the 32-bit range into two u64 sub-ranges: 378 * [0x00000000, 0x7FFFFFFF] -> [0x0000000000000000, 0x000000007FFFFFFF] 379 * [0x80000000, 0xFFFFFFFF] -> [0xFFFFFFFF80000000, 0xFFFFFFFFFFFFFFFF] 380 * The ordering is preserved within each sub-range, and 381 * the second sub-range is above the first as u64. 382 */ 383 dst_val = (s32)dst_val; 384 src_val = (s32)src_val; 385 } 386 387 taken = eval_const_branch(insn->code, dst_val, src_val); 388 if (taken < 0) { 389 bpf_log(&env->log, "Unknown conditional jump %x\n", insn->code); 390 return -EFAULT; 391 } 392 *insn = BPF_JMP_A(taken ? insn->off : 0); 393 changed = true; 394 } 395 396 if (!changed) 397 return 0; 398 /* recompute postorder, since CFG has changed */ 399 kvfree(env->cfg.insn_postorder); 400 env->cfg.insn_postorder = NULL; 401 kvfree(env->cfg.postorder_nums); 402 env->cfg.postorder_nums = NULL; 403 return bpf_compute_postorder(env); 404 } 405