projects/linux·blob master · refs

398 lines · 10.7 KiB

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
14enum 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
23struct const_arg_info {
24 enum const_arg_state state;
25 u32 map_index;
26 u64 val;
27};
28
29static bool ci_is_unvisited(const struct const_arg_info *ci)
30{
31 return ci->state == CONST_ARG_UNVISITED;
32}
33
34static bool ci_is_unknown(const struct const_arg_info *ci)
35{
36 return ci->state == CONST_ARG_UNKNOWN;
37}
38
39static bool ci_is_const(const struct const_arg_info *ci)
40{
41 return ci->state == CONST_ARG_CONST;
42}
43
44static 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. */
50static 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
184 if (!bpf_map_is_rdonly(map) || !map->ops->map_direct_value_addr ||
185 off < 0 || off + size > map->value_size ||
186 bpf_map_direct_read(map, off, size, &val, is_ldsx)) {
187 *dst = unknown;
188 break;
189 }
190 dst->state = CONST_ARG_CONST;
191 dst->val = val;
192 break;
193 case BPF_JMP:
194 if (opcode != BPF_CALL)
195 break;
196process_call:
197 for (r = BPF_REG_0; r <= BPF_REG_5; r++)
198 ci_out[r] = unknown;
199 break;
200 case BPF_STX:
201 r = bpf_atomic_load_reg(insn);
202 if (r >= 0)
203 ci_out[r] = unknown;
204 break;
205 }
206}
207
208/* Join function: merge output state into a successor's input state. */
209static bool const_reg_join(struct const_arg_info *ci_target,
210 struct const_arg_info *ci_out)
211{
212 bool changed = false;
213 int r;
214
215 for (r = 0; r < MAX_BPF_REG; r++) {
216 struct const_arg_info *old = &ci_target[r];
217 struct const_arg_info *new = &ci_out[r];
218
219 if (ci_is_unvisited(old) && !ci_is_unvisited(new)) {
220 ci_target[r] = *new;
221 changed = true;
222 } else if (!ci_is_unknown(old) && !ci_is_unvisited(old) &&
223 (new->state != old->state || new->val != old->val ||
224 new->map_index != old->map_index)) {
225 old->state = CONST_ARG_UNKNOWN;
226 changed = true;
227 }
228 }
229 return changed;
230}
231
232int bpf_compute_const_regs(struct bpf_verifier_env *env)
233{
234 struct const_arg_info unknown = { .state = CONST_ARG_UNKNOWN, .val = 0 };
235 struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
236 struct bpf_insn *insns = env->prog->insnsi;
237 int insn_cnt = env->prog->len;
238 struct const_arg_info (*ci_in)[MAX_BPF_REG];
239 struct const_arg_info ci_out[MAX_BPF_REG];
240 struct bpf_iarray *succ;
241 bool changed;
242 int i, r;
243
244 /* kvzalloc zeroes memory, so all entries start as CONST_ARG_UNVISITED (0) */
245 ci_in = kvzalloc_objs(*ci_in, insn_cnt, GFP_KERNEL_ACCOUNT);
246 if (!ci_in)
247 return -ENOMEM;
248
249 /* Subprogram entries (including main at subprog 0): all registers unknown */
250 for (i = 0; i < env->subprog_cnt; i++) {
251 int start = env->subprog_info[i].start;
252
253 for (r = 0; r < MAX_BPF_REG; r++)
254 ci_in[start][r] = unknown;
255 }
256
257redo:
258 changed = false;
259 for (i = env->cfg.cur_postorder - 1; i >= 0; i--) {
260 int idx = env->cfg.insn_postorder[i];
261 struct bpf_insn *insn = &insns[idx];
262 struct const_arg_info *ci = ci_in[idx];
263
264 memcpy(ci_out, ci, sizeof(ci_out));
265
266 const_reg_xfer(env, ci_out, insn, insns, idx);
267
268 succ = bpf_insn_successors(env, idx);
269 for (int s = 0; s < succ->cnt; s++)
270 changed |= const_reg_join(ci_in[succ->items[s]], ci_out);
271 }
272 if (changed)
273 goto redo;
274
275 /* Save computed constants into insn_aux[] if they fit into 32-bit */
276 for (i = 0; i < insn_cnt; i++) {
277 u16 mask = 0, map_mask = 0, subprog_mask = 0;
278 struct bpf_insn_aux_data *aux = &insn_aux[i];
279 struct const_arg_info *ci = ci_in[i];
280
281 for (r = BPF_REG_0; r < ARRAY_SIZE(aux->const_reg_vals); r++) {
282 struct const_arg_info *c = &ci[r];
283
284 switch (c->state) {
285 case CONST_ARG_CONST: {
286 u64 val = c->val;
287
288 if (val != (u32)val)
289 break;
290 mask |= BIT(r);
291 aux->const_reg_vals[r] = val;
292 break;
293 }
294 case CONST_ARG_MAP_PTR:
295 map_mask |= BIT(r);
296 aux->const_reg_vals[r] = c->map_index;
297 break;
298 case CONST_ARG_SUBPROG:
299 subprog_mask |= BIT(r);
300 aux->const_reg_vals[r] = c->val;
301 break;
302 default:
303 break;
304 }
305 }
306 aux->const_reg_mask = mask;
307 aux->const_reg_map_mask = map_mask;
308 aux->const_reg_subprog_mask = subprog_mask;
309 }
310
311 kvfree(ci_in);
312 return 0;
313}
314
315static int eval_const_branch(u8 opcode, u64 dst_val, u64 src_val)
316{
317 switch (BPF_OP(opcode)) {
318 case BPF_JEQ: return dst_val == src_val;
319 case BPF_JNE: return dst_val != src_val;
320 case BPF_JGT: return dst_val > src_val;
321 case BPF_JGE: return dst_val >= src_val;
322 case BPF_JLT: return dst_val < src_val;
323 case BPF_JLE: return dst_val <= src_val;
324 case BPF_JSGT: return (s64)dst_val > (s64)src_val;
325 case BPF_JSGE: return (s64)dst_val >= (s64)src_val;
326 case BPF_JSLT: return (s64)dst_val < (s64)src_val;
327 case BPF_JSLE: return (s64)dst_val <= (s64)src_val;
328 case BPF_JSET: return (bool)(dst_val & src_val);
329 default: return -1;
330 }
331}
332
333/*
334 * Rewrite conditional branches with constant outcomes into unconditional
335 * jumps using register values resolved by bpf_compute_const_regs() pass.
336 * This eliminates dead edges from the CFG so that compute_live_registers()
337 * doesn't propagate liveness through dead code.
338 */
339int bpf_prune_dead_branches(struct bpf_verifier_env *env)
340{
341 struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
342 struct bpf_insn *insns = env->prog->insnsi;
343 int insn_cnt = env->prog->len;
344 bool changed = false;
345 int i;
346
347 for (i = 0; i < insn_cnt; i++) {
348 struct bpf_insn_aux_data *aux = &insn_aux[i];
349 struct bpf_insn *insn = &insns[i];
350 u8 class = BPF_CLASS(insn->code);
351 u64 dst_val, src_val;
352 int taken;
353
354 if (!bpf_insn_is_cond_jump(insn->code))
355 continue;
356 if (bpf_is_may_goto_insn(insn))
357 continue;
358
359 if (!(aux->const_reg_mask & BIT(insn->dst_reg)))
360 continue;
361 dst_val = aux->const_reg_vals[insn->dst_reg];
362
363 if (BPF_SRC(insn->code) == BPF_K) {
364 src_val = insn->imm;
365 } else {
366 if (!(aux->const_reg_mask & BIT(insn->src_reg)))
367 continue;
368 src_val = aux->const_reg_vals[insn->src_reg];
369 }
370
371 if (class == BPF_JMP32) {
372 /*
373 * The (s32) cast maps the 32-bit range into two u64 sub-ranges:
374 * [0x00000000, 0x7FFFFFFF] -> [0x0000000000000000, 0x000000007FFFFFFF]
375 * [0x80000000, 0xFFFFFFFF] -> [0xFFFFFFFF80000000, 0xFFFFFFFFFFFFFFFF]
376 * The ordering is preserved within each sub-range, and
377 * the second sub-range is above the first as u64.
378 */
379 dst_val = (s32)dst_val;
380 src_val = (s32)src_val;
381 }
382
383 taken = eval_const_branch(insn->code, dst_val, src_val);
384 if (taken < 0) {
385 bpf_log(&env->log, "Unknown conditional jump %x\n", insn->code);
386 return -EFAULT;
387 }
388 *insn = BPF_JMP_A(taken ? insn->off : 0);
389 changed = true;
390 }
391
392 if (!changed)
393 return 0;
394 /* recompute postorder, since CFG has changed */
395 kvfree(env->cfg.insn_postorder);
396 env->cfg.insn_postorder = NULL;
397 return bpf_compute_postorder(env);
398}