projects/linux·blob master · refs

2332 lines · 65.3 KiB

1// SPDX-License-Identifier: GPL-2.0-only
2/* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */
3
4#include <linux/bpf_verifier.h>
5#include <linux/btf.h>
6#include <linux/hashtable.h>
7#include <linux/jhash.h>
8#include <linux/slab.h>
9#include <linux/sort.h>
10
11#define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
12
13struct per_frame_masks {
14 spis_t may_read; /* stack slots that may be read by this instruction */
15 spis_t must_write; /* stack slots written by this instruction */
16 spis_t live_before; /* stack slots that may be read by this insn and its successors */
17};
18
19/*
20 * A function instance keyed by (callsite, depth).
21 * Encapsulates read and write marks for each instruction in the function.
22 * Marks are tracked for each frame up to @depth.
23 */
24struct func_instance {
25 struct hlist_node hl_node;
26 u32 callsite; /* call insn that invoked this subprog (subprog_start for depth 0) */
27 u32 depth; /* call depth (0 = entry subprog) */
28 u32 subprog; /* subprog index */
29 u32 subprog_start; /* cached env->subprog_info[subprog].start */
30 u32 insn_cnt; /* cached number of insns in the function */
31 /* Per frame, per instruction masks, frames allocated lazily. */
32 struct per_frame_masks *frames[MAX_CALL_FRAMES];
33 bool must_write_initialized;
34};
35
36struct live_stack_query {
37 struct func_instance *instances[MAX_CALL_FRAMES]; /* valid in range [0..curframe] */
38 u32 callsites[MAX_CALL_FRAMES]; /* callsite[i] = insn calling frame i+1 */
39 u32 curframe;
40 u32 insn_idx;
41};
42
43struct bpf_liveness {
44 DECLARE_HASHTABLE(func_instances, 8); /* maps (depth, callsite) to func_instance */
45 struct live_stack_query live_stack_query; /* cache to avoid repetitive ht lookups */
46 u32 subprog_calls; /* analyze_subprog() invocations */
47};
48
49/*
50 * Hash/compare key for func_instance: (depth, callsite).
51 * For depth == 0 (entry subprog), @callsite is the subprog start insn.
52 * For depth > 0, @callsite is the call instruction index that invoked the subprog.
53 */
54static u32 instance_hash(u32 callsite, u32 depth)
55{
56 u32 key[2] = { depth, callsite };
57
58 return jhash2(key, 2, 0);
59}
60
61static struct func_instance *find_instance(struct bpf_verifier_env *env,
62 u32 callsite, u32 depth)
63{
64 struct bpf_liveness *liveness = env->liveness;
65 struct func_instance *f;
66 u32 key = instance_hash(callsite, depth);
67
68 hash_for_each_possible(liveness->func_instances, f, hl_node, key)
69 if (f->depth == depth && f->callsite == callsite)
70 return f;
71 return NULL;
72}
73
74static struct func_instance *call_instance(struct bpf_verifier_env *env,
75 struct func_instance *caller,
76 u32 callsite, int subprog)
77{
78 u32 depth = caller ? caller->depth + 1 : 0;
79 u32 subprog_start = env->subprog_info[subprog].start;
80 u32 lookup_key = depth > 0 ? callsite : subprog_start;
81 struct func_instance *f;
82 u32 hash;
83
84 f = find_instance(env, lookup_key, depth);
85 if (f)
86 return f;
87
88 f = kvzalloc_obj(*f, GFP_KERNEL_ACCOUNT);
89 if (!f)
90 return ERR_PTR(-ENOMEM);
91 f->callsite = lookup_key;
92 f->depth = depth;
93 f->subprog = subprog;
94 f->subprog_start = subprog_start;
95 f->insn_cnt = (env->subprog_info + subprog + 1)->start - subprog_start;
96 hash = instance_hash(lookup_key, depth);
97 hash_add(env->liveness->func_instances, &f->hl_node, hash);
98 return f;
99}
100
101static struct func_instance *lookup_instance(struct bpf_verifier_env *env,
102 struct bpf_verifier_state *st,
103 u32 frameno)
104{
105 u32 callsite, subprog_start;
106 struct func_instance *f;
107 u32 key, depth;
108
109 subprog_start = env->subprog_info[st->frame[frameno]->subprogno].start;
110 callsite = frameno > 0 ? st->frame[frameno]->callsite : subprog_start;
111
112 for (depth = frameno; ; depth--) {
113 key = depth > 0 ? callsite : subprog_start;
114 f = find_instance(env, key, depth);
115 if (f || depth == 0)
116 return f;
117 }
118}
119
120int bpf_stack_liveness_init(struct bpf_verifier_env *env)
121{
122 env->liveness = kvzalloc_obj(*env->liveness, GFP_KERNEL_ACCOUNT);
123 if (!env->liveness)
124 return -ENOMEM;
125 hash_init(env->liveness->func_instances);
126 return 0;
127}
128
129void bpf_stack_liveness_free(struct bpf_verifier_env *env)
130{
131 struct func_instance *instance;
132 struct hlist_node *tmp;
133 int bkt, i;
134
135 if (!env->liveness)
136 return;
137 hash_for_each_safe(env->liveness->func_instances, bkt, tmp, instance, hl_node) {
138 for (i = 0; i <= instance->depth; i++)
139 kvfree(instance->frames[i]);
140 kvfree(instance);
141 }
142 kvfree(env->liveness);
143}
144
145/*
146 * Convert absolute instruction index @insn_idx to an index relative
147 * to start of the function corresponding to @instance.
148 */
149static int relative_idx(struct func_instance *instance, u32 insn_idx)
150{
151 return insn_idx - instance->subprog_start;
152}
153
154static struct per_frame_masks *get_frame_masks(struct func_instance *instance,
155 u32 frame, u32 insn_idx)
156{
157 if (!instance->frames[frame])
158 return NULL;
159
160 return &instance->frames[frame][relative_idx(instance, insn_idx)];
161}
162
163static struct per_frame_masks *alloc_frame_masks(struct func_instance *instance,
164 u32 frame, u32 insn_idx)
165{
166 struct per_frame_masks *arr;
167
168 if (!instance->frames[frame]) {
169 arr = kvzalloc_objs(*arr, instance->insn_cnt,
170 GFP_KERNEL_ACCOUNT);
171 instance->frames[frame] = arr;
172 if (!arr)
173 return ERR_PTR(-ENOMEM);
174 }
175 return get_frame_masks(instance, frame, insn_idx);
176}
177
178/* Accumulate may_read masks for @frame at @insn_idx */
179static int mark_stack_read(struct func_instance *instance, u32 frame, u32 insn_idx, spis_t mask)
180{
181 struct per_frame_masks *masks;
182
183 masks = alloc_frame_masks(instance, frame, insn_idx);
184 if (IS_ERR(masks))
185 return PTR_ERR(masks);
186 masks->may_read = spis_or(masks->may_read, mask);
187 return 0;
188}
189
190static int mark_stack_write(struct func_instance *instance, u32 frame, u32 insn_idx, spis_t mask)
191{
192 struct per_frame_masks *masks;
193
194 masks = alloc_frame_masks(instance, frame, insn_idx);
195 if (IS_ERR(masks))
196 return PTR_ERR(masks);
197 masks->must_write = spis_or(masks->must_write, mask);
198 return 0;
199}
200
201int bpf_jmp_offset(struct bpf_insn *insn)
202{
203 u8 code = insn->code;
204
205 if (code == (BPF_JMP32 | BPF_JA))
206 return insn->imm;
207 return insn->off;
208}
209
210__diag_push();
211__diag_ignore_all("-Woverride-init", "Allow field initialization overrides for opcode_info_tbl");
212
213/*
214 * Returns an array of instructions succ, with succ->items[0], ...,
215 * succ->items[n-1] with successor instructions, where n=succ->cnt
216 */
217inline struct bpf_iarray *
218bpf_insn_successors(struct bpf_verifier_env *env, u32 idx)
219{
220 static const struct opcode_info {
221 bool can_jump;
222 bool can_fallthrough;
223 } opcode_info_tbl[256] = {
224 [0 ... 255] = {.can_jump = false, .can_fallthrough = true},
225 #define _J(code, ...) \
226 [BPF_JMP | code] = __VA_ARGS__, \
227 [BPF_JMP32 | code] = __VA_ARGS__
228
229 _J(BPF_EXIT, {.can_jump = false, .can_fallthrough = false}),
230 _J(BPF_JA, {.can_jump = true, .can_fallthrough = false}),
231 _J(BPF_JEQ, {.can_jump = true, .can_fallthrough = true}),
232 _J(BPF_JNE, {.can_jump = true, .can_fallthrough = true}),
233 _J(BPF_JLT, {.can_jump = true, .can_fallthrough = true}),
234 _J(BPF_JLE, {.can_jump = true, .can_fallthrough = true}),
235 _J(BPF_JGT, {.can_jump = true, .can_fallthrough = true}),
236 _J(BPF_JGE, {.can_jump = true, .can_fallthrough = true}),
237 _J(BPF_JSGT, {.can_jump = true, .can_fallthrough = true}),
238 _J(BPF_JSGE, {.can_jump = true, .can_fallthrough = true}),
239 _J(BPF_JSLT, {.can_jump = true, .can_fallthrough = true}),
240 _J(BPF_JSLE, {.can_jump = true, .can_fallthrough = true}),
241 _J(BPF_JCOND, {.can_jump = true, .can_fallthrough = true}),
242 _J(BPF_JSET, {.can_jump = true, .can_fallthrough = true}),
243 #undef _J
244 };
245 struct bpf_prog *prog = env->prog;
246 struct bpf_insn *insn = &prog->insnsi[idx];
247 const struct opcode_info *opcode_info;
248 struct bpf_iarray *succ, *jt;
249 int insn_sz;
250
251 jt = env->insn_aux_data[idx].jt;
252 if (unlikely(jt))
253 return jt;
254
255 /* pre-allocated array of size up to 2; reset cnt, as it may have been used already */
256 succ = env->succ;
257 succ->cnt = 0;
258
259 opcode_info = &opcode_info_tbl[BPF_CLASS(insn->code) | BPF_OP(insn->code)];
260 insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
261 if (opcode_info->can_fallthrough)
262 succ->items[succ->cnt++] = idx + insn_sz;
263
264 if (opcode_info->can_jump)
265 succ->items[succ->cnt++] = idx + bpf_jmp_offset(insn) + 1;
266
267 return succ;
268}
269
270__diag_pop();
271
272static inline bool update_insn(struct bpf_verifier_env *env,
273 struct func_instance *instance, u32 frame, u32 insn_idx)
274{
275 spis_t new_before, new_after;
276 struct per_frame_masks *insn, *succ_insn;
277 struct bpf_iarray *succ;
278 u32 s;
279 bool changed;
280
281 succ = bpf_insn_successors(env, insn_idx);
282 if (succ->cnt == 0)
283 return false;
284
285 changed = false;
286 insn = get_frame_masks(instance, frame, insn_idx);
287 new_before = SPIS_ZERO;
288 new_after = SPIS_ZERO;
289 for (s = 0; s < succ->cnt; ++s) {
290 succ_insn = get_frame_masks(instance, frame, succ->items[s]);
291 new_after = spis_or(new_after, succ_insn->live_before);
292 }
293 /*
294 * New "live_before" is a union of all "live_before" of successors
295 * minus slots written by instruction plus slots read by instruction.
296 * new_before = (new_after & ~insn->must_write) | insn->may_read
297 */
298 new_before = spis_or(spis_and(new_after, spis_not(insn->must_write)),
299 insn->may_read);
300 changed |= !spis_equal(new_before, insn->live_before);
301 insn->live_before = new_before;
302 return changed;
303}
304
305/* Fixed-point computation of @live_before marks */
306static void update_instance(struct bpf_verifier_env *env, struct func_instance *instance)
307{
308 u32 i, frame, po_start, po_end;
309 int *insn_postorder = env->cfg.insn_postorder;
310 struct bpf_subprog_info *subprog;
311 bool changed;
312
313 instance->must_write_initialized = true;
314 subprog = &env->subprog_info[instance->subprog];
315 po_start = subprog->postorder_start;
316 po_end = (subprog + 1)->postorder_start;
317 /* repeat until fixed point is reached */
318 do {
319 changed = false;
320 for (frame = 0; frame <= instance->depth; frame++) {
321 if (!instance->frames[frame])
322 continue;
323
324 for (i = po_start; i < po_end; i++)
325 changed |= update_insn(env, instance, frame, insn_postorder[i]);
326 }
327 } while (changed);
328}
329
330static bool is_live_before(struct func_instance *instance, u32 insn_idx, u32 frameno, u32 half_spi)
331{
332 struct per_frame_masks *masks;
333
334 masks = get_frame_masks(instance, frameno, insn_idx);
335 return masks && spis_test_bit(masks->live_before, half_spi);
336}
337
338int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
339{
340 struct live_stack_query *q = &env->liveness->live_stack_query;
341 struct func_instance *instance;
342 u32 frame;
343
344 memset(q, 0, sizeof(*q));
345 for (frame = 0; frame <= st->curframe; frame++) {
346 instance = lookup_instance(env, st, frame);
347 if (IS_ERR_OR_NULL(instance))
348 q->instances[frame] = NULL;
349 else
350 q->instances[frame] = instance;
351 if (frame < st->curframe)
352 q->callsites[frame] = st->frame[frame + 1]->callsite;
353 }
354 q->curframe = st->curframe;
355 q->insn_idx = st->insn_idx;
356 return 0;
357}
358
359bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 half_spi)
360{
361 /*
362 * Slot is alive if it is read before q->insn_idx in current func instance,
363 * or if for some outer func instance:
364 * - alive before callsite if callsite calls callback, otherwise
365 * - alive after callsite
366 */
367 struct live_stack_query *q = &env->liveness->live_stack_query;
368 struct func_instance *instance, *curframe_instance;
369 u32 i, callsite, rel;
370 int cur_delta, delta;
371 bool alive = false;
372
373 curframe_instance = q->instances[q->curframe];
374 if (!curframe_instance)
375 return true;
376 cur_delta = (int)curframe_instance->depth - (int)q->curframe;
377 rel = frameno + cur_delta;
378 if (rel <= curframe_instance->depth)
379 alive = is_live_before(curframe_instance, q->insn_idx, rel, half_spi);
380
381 if (alive)
382 return true;
383
384 for (i = frameno; i < q->curframe; i++) {
385 instance = q->instances[i];
386 if (!instance)
387 return true;
388 /* Map actual frameno to frame index within this instance */
389 delta = (int)instance->depth - (int)i;
390 rel = frameno + delta;
391 if (rel > instance->depth)
392 return true;
393
394 /* Get callsite from verifier state, not from instance callchain */
395 callsite = q->callsites[i];
396
397 alive = bpf_calls_callback(env, callsite)
398 ? is_live_before(instance, callsite, rel, half_spi)
399 : is_live_before(instance, callsite + 1, rel, half_spi);
400 if (alive)
401 return true;
402 }
403
404 return false;
405}
406
407static char *fmt_subprog(struct bpf_verifier_env *env, int subprog)
408{
409 const char *name = env->subprog_info[subprog].name;
410
411 snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf),
412 "subprog#%d%s%s", subprog, name ? " " : "", name ? name : "");
413 return env->tmp_str_buf;
414}
415
416static char *fmt_instance(struct bpf_verifier_env *env, struct func_instance *instance)
417{
418 snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf),
419 "(d%d,cs%d)", instance->depth, instance->callsite);
420 return env->tmp_str_buf;
421}
422
423static int spi_off(int spi)
424{
425 return -(spi + 1) * BPF_REG_SIZE;
426}
427
428/*
429 * When both halves of an 8-byte SPI are set, print as "-8","-16",...
430 * When only one half is set, print as "-4h","-8h",...
431 * Runs of 3+ consecutive fully-set SPIs are collapsed: "fp0-8..-24"
432 */
433static char *fmt_spis_mask(struct bpf_verifier_env *env, int frame, bool first, spis_t spis)
434{
435 int buf_sz = sizeof(env->tmp_str_buf);
436 char *buf = env->tmp_str_buf;
437 int spi, n, run_start;
438
439 buf[0] = '\0';
440
441 for (spi = 0; spi < STACK_SLOTS / 2 && buf_sz > 0; spi++) {
442 bool lo = spis_test_bit(spis, spi * 2);
443 bool hi = spis_test_bit(spis, spi * 2 + 1);
444 const char *space = first ? "" : " ";
445
446 if (!lo && !hi)
447 continue;
448
449 if (!lo || !hi) {
450 /* half-spi */
451 n = scnprintf(buf, buf_sz, "%sfp%d%d%s",
452 space, frame, spi_off(spi) + (lo ? STACK_SLOT_SZ : 0), "h");
453 } else if (spi + 2 < STACK_SLOTS / 2 &&
454 spis_test_bit(spis, spi * 2 + 2) &&
455 spis_test_bit(spis, spi * 2 + 3) &&
456 spis_test_bit(spis, spi * 2 + 4) &&
457 spis_test_bit(spis, spi * 2 + 5)) {
458 /* 3+ consecutive full spis */
459 run_start = spi;
460 while (spi + 1 < STACK_SLOTS / 2 &&
461 spis_test_bit(spis, (spi + 1) * 2) &&
462 spis_test_bit(spis, (spi + 1) * 2 + 1))
463 spi++;
464 n = scnprintf(buf, buf_sz, "%sfp%d%d..%d",
465 space, frame, spi_off(run_start), spi_off(spi));
466 } else {
467 /* just a full spi */
468 n = scnprintf(buf, buf_sz, "%sfp%d%d", space, frame, spi_off(spi));
469 }
470 first = false;
471 buf += n;
472 buf_sz -= n;
473 }
474 return env->tmp_str_buf;
475}
476
477static void print_instance(struct bpf_verifier_env *env, struct func_instance *instance)
478{
479 int start = env->subprog_info[instance->subprog].start;
480 struct bpf_insn *insns = env->prog->insnsi;
481 struct per_frame_masks *masks;
482 int len = instance->insn_cnt;
483 int insn_idx, frame, i;
484 bool has_use, has_def;
485 u64 pos, insn_pos;
486
487 if (!(env->log.level & BPF_LOG_LEVEL2))
488 return;
489
490 verbose(env, "stack use/def %s ", fmt_subprog(env, instance->subprog));
491 verbose(env, "%s:\n", fmt_instance(env, instance));
492 for (i = 0; i < len; i++) {
493 insn_idx = start + i;
494 has_use = false;
495 has_def = false;
496 pos = env->log.end_pos;
497 verbose(env, "%3d: ", insn_idx);
498 bpf_verbose_insn(env, &insns[insn_idx]);
499 insn_pos = env->log.end_pos;
500 verbose(env, "%*c;", bpf_vlog_alignment(insn_pos - pos), ' ');
501 pos = env->log.end_pos;
502 verbose(env, " use: ");
503 for (frame = instance->depth; frame >= 0; --frame) {
504 masks = get_frame_masks(instance, frame, insn_idx);
505 if (!masks || spis_is_zero(masks->may_read))
506 continue;
507 verbose(env, "%s", fmt_spis_mask(env, frame, !has_use, masks->may_read));
508 has_use = true;
509 }
510 if (!has_use)
511 bpf_vlog_reset(&env->log, pos);
512 pos = env->log.end_pos;
513 verbose(env, " def: ");
514 for (frame = instance->depth; frame >= 0; --frame) {
515 masks = get_frame_masks(instance, frame, insn_idx);
516 if (!masks || spis_is_zero(masks->must_write))
517 continue;
518 verbose(env, "%s", fmt_spis_mask(env, frame, !has_def, masks->must_write));
519 has_def = true;
520 }
521 if (!has_def)
522 bpf_vlog_reset(&env->log, has_use ? pos : insn_pos);
523 verbose(env, "\n");
524 if (bpf_is_ldimm64(&insns[insn_idx]))
525 i++;
526 }
527}
528
529static int cmp_instances(const void *pa, const void *pb)
530{
531 struct func_instance *a = *(struct func_instance **)pa;
532 struct func_instance *b = *(struct func_instance **)pb;
533 int dcallsite = (int)a->callsite - b->callsite;
534 int ddepth = (int)a->depth - b->depth;
535
536 if (dcallsite)
537 return dcallsite;
538 if (ddepth)
539 return ddepth;
540 return 0;
541}
542
543/* print use/def slots for all instances ordered by callsite first, then by depth */
544static int print_instances(struct bpf_verifier_env *env)
545{
546 struct func_instance *instance, **sorted_instances;
547 struct bpf_liveness *liveness = env->liveness;
548 int i, bkt, cnt;
549
550 cnt = 0;
551 hash_for_each(liveness->func_instances, bkt, instance, hl_node)
552 cnt++;
553 sorted_instances = kvmalloc_objs(*sorted_instances, cnt, GFP_KERNEL_ACCOUNT);
554 if (!sorted_instances)
555 return -ENOMEM;
556 cnt = 0;
557 hash_for_each(liveness->func_instances, bkt, instance, hl_node)
558 sorted_instances[cnt++] = instance;
559 sort(sorted_instances, cnt, sizeof(*sorted_instances), cmp_instances, NULL);
560 for (i = 0; i < cnt; i++)
561 print_instance(env, sorted_instances[i]);
562 kvfree(sorted_instances);
563 return 0;
564}
565
566/*
567 * Per-register tracking state for compute_subprog_args().
568 * Tracks which frame's FP a value is derived from
569 * and the byte offset from that frame's FP.
570 *
571 * The .frame field forms a lattice with three levels of precision:
572 *
573 * precise {frame=N, off=V} -- known absolute frame index and byte offset
574 * |
575 * offset-imprecise {frame=N, cnt=0}
576 * | -- known frame identity, unknown offset
577 * fully-imprecise {frame=ARG_IMPRECISE, mask=bitmask}
578 * -- unknown frame identity; .mask is a
579 * bitmask of which frame indices might be
580 * involved
581 *
582 * At CFG merge points, arg_track_join() moves down the lattice:
583 * - same frame + same offset -> precise
584 * - same frame + different offset -> offset-imprecise
585 * - different frames -> fully-imprecise (bitmask OR)
586 *
587 * At memory access sites (LDX/STX/ST), offset-imprecise marks only
588 * the known frame's access mask as SPIS_ALL, while fully-imprecise
589 * iterates bits in the bitmask and routes each frame to its target.
590 */
591#define MAX_ARG_OFFSETS 4
592
593struct arg_track {
594 union {
595 s16 off[MAX_ARG_OFFSETS]; /* byte offsets; off_cnt says how many */
596 u16 mask; /* arg bitmask when arg == ARG_IMPRECISE */
597 };
598 s8 frame; /* absolute frame index, or enum arg_track_state */
599 s8 off_cnt; /* 0 = offset-imprecise, 1-4 = # of precise offsets */
600};
601
602enum arg_track_state {
603 ARG_NONE = -1, /* not derived from any argument */
604 ARG_UNVISITED = -2, /* not yet reached by dataflow */
605 ARG_IMPRECISE = -3, /* lost identity; .mask is arg bitmask */
606};
607
608/* Track callee stack slots fp-8 through fp-512 (64 slots of 8 bytes each) */
609#define MAX_ARG_SPILL_SLOTS 64
610
611/*
612 * Combined register + stack arg tracking: R0-R10 at indices 0-10,
613 * outgoing stack arg slots at indices MAX_BPF_REG..MAX_BPF_REG+6.
614 */
615#define MAX_AT_TRACK_REGS (MAX_BPF_REG + MAX_STACK_ARG_SLOTS)
616
617static int stack_arg_off_to_slot(s16 off)
618{
619 int aoff = off < 0 ? -off : off;
620
621 if (aoff / 8 > MAX_STACK_ARG_SLOTS)
622 return -1;
623 return aoff / 8 - 1;
624}
625
626static bool arg_is_visited(const struct arg_track *at)
627{
628 return at->frame != ARG_UNVISITED;
629}
630
631static bool arg_is_fp(const struct arg_track *at)
632{
633 return at->frame >= 0 || at->frame == ARG_IMPRECISE;
634}
635
636static void verbose_arg_track(struct bpf_verifier_env *env, struct arg_track *at)
637{
638 int i;
639
640 switch (at->frame) {
641 case ARG_NONE: verbose(env, "_"); break;
642 case ARG_UNVISITED: verbose(env, "?"); break;
643 case ARG_IMPRECISE: verbose(env, "IMP%x", at->mask); break;
644 default:
645 /* frame >= 0: absolute frame index */
646 if (at->off_cnt == 0) {
647 verbose(env, "fp%d ?", at->frame);
648 } else {
649 for (i = 0; i < at->off_cnt; i++) {
650 if (i)
651 verbose(env, "|");
652 verbose(env, "fp%d%+d", at->frame, at->off[i]);
653 }
654 }
655 break;
656 }
657}
658
659static bool arg_track_eq(const struct arg_track *a, const struct arg_track *b)
660{
661 int i;
662
663 if (a->frame != b->frame)
664 return false;
665 if (a->frame == ARG_IMPRECISE)
666 return a->mask == b->mask;
667 if (a->frame < 0)
668 return true;
669 if (a->off_cnt != b->off_cnt)
670 return false;
671 for (i = 0; i < a->off_cnt; i++)
672 if (a->off[i] != b->off[i])
673 return false;
674 return true;
675}
676
677static struct arg_track arg_single(s8 arg, s16 off)
678{
679 struct arg_track at = {};
680
681 at.frame = arg;
682 at.off[0] = off;
683 at.off_cnt = 1;
684 return at;
685}
686
687/*
688 * Merge two sorted offset arrays, deduplicate.
689 * Returns off_cnt=0 if the result exceeds MAX_ARG_OFFSETS.
690 * Both args must have the same frame and off_cnt > 0.
691 */
692static struct arg_track arg_merge_offsets(struct arg_track a, struct arg_track b)
693{
694 struct arg_track result = { .frame = a.frame };
695 struct arg_track imp = { .frame = a.frame };
696 int i = 0, j = 0, k = 0;
697
698 while (i < a.off_cnt && j < b.off_cnt) {
699 s16 v;
700
701 if (a.off[i] <= b.off[j]) {
702 v = a.off[i++];
703 if (v == b.off[j])
704 j++;
705 } else {
706 v = b.off[j++];
707 }
708 if (k > 0 && result.off[k - 1] == v)
709 continue;
710 if (k >= MAX_ARG_OFFSETS)
711 return imp;
712 result.off[k++] = v;
713 }
714 while (i < a.off_cnt) {
715 if (k >= MAX_ARG_OFFSETS)
716 return imp;
717 result.off[k++] = a.off[i++];
718 }
719 while (j < b.off_cnt) {
720 if (k >= MAX_ARG_OFFSETS)
721 return imp;
722 result.off[k++] = b.off[j++];
723 }
724 result.off_cnt = k;
725 return result;
726}
727
728/*
729 * Merge two arg_tracks into ARG_IMPRECISE, collecting the frame
730 * bits from both operands. Precise frame indices (frame >= 0)
731 * contribute a single bit; existing ARG_IMPRECISE values
732 * contribute their full bitmask.
733 */
734static struct arg_track arg_join_imprecise(struct arg_track a, struct arg_track b)
735{
736 u32 m = 0;
737
738 if (a.frame >= 0)
739 m |= BIT(a.frame);
740 else if (a.frame == ARG_IMPRECISE)
741 m |= a.mask;
742
743 if (b.frame >= 0)
744 m |= BIT(b.frame);
745 else if (b.frame == ARG_IMPRECISE)
746 m |= b.mask;
747
748 return (struct arg_track){ .mask = m, .frame = ARG_IMPRECISE };
749}
750
751/* Join two arg_track values at merge points */
752static struct arg_track __arg_track_join(struct arg_track a, struct arg_track b)
753{
754 if (!arg_is_visited(&b))
755 return a;
756 if (!arg_is_visited(&a))
757 return b;
758 if (a.frame == b.frame && a.frame >= 0) {
759 /* Both offset-imprecise: stay imprecise */
760 if (a.off_cnt == 0 || b.off_cnt == 0)
761 return (struct arg_track){ .frame = a.frame };
762 /* Merge offset sets; falls back to off_cnt=0 if >4 */
763 return arg_merge_offsets(a, b);
764 }
765
766 /*
767 * args are different, but one of them is known
768 * arg + none -> arg
769 * none + arg -> arg
770 *
771 * none + none -> none
772 */
773 if (a.frame == ARG_NONE && b.frame == ARG_NONE)
774 return a;
775 if (a.frame >= 0 && b.frame == ARG_NONE) {
776 /*
777 * When joining single fp-N add fake fp+0 to
778 * keep stack_use and prevent stack_def
779 */
780 if (a.off_cnt == 1)
781 return arg_merge_offsets(a, arg_single(a.frame, 0));
782 return a;
783 }
784 if (b.frame >= 0 && a.frame == ARG_NONE) {
785 if (b.off_cnt == 1)
786 return arg_merge_offsets(b, arg_single(b.frame, 0));
787 return b;
788 }
789
790 return arg_join_imprecise(a, b);
791}
792
793static bool arg_track_join(struct bpf_verifier_env *env, int idx, int target, int r,
794 struct arg_track *in, struct arg_track out)
795{
796 struct arg_track old = *in;
797 struct arg_track new_val = __arg_track_join(old, out);
798
799 if (arg_track_eq(&new_val, &old))
800 return false;
801
802 *in = new_val;
803 if (!(env->log.level & BPF_LOG_LEVEL2) || !arg_is_visited(&old))
804 return true;
805
806 verbose(env, "arg JOIN insn %d -> %d ", idx, target);
807 if (r >= MAX_BPF_REG)
808 verbose(env, "sa%d: ", r - MAX_BPF_REG);
809 else if (r >= 0)
810 verbose(env, "r%d: ", r);
811 else
812 verbose(env, "fp%+d: ", r * 8);
813 verbose_arg_track(env, &old);
814 verbose(env, " + ");
815 verbose_arg_track(env, &out);
816 verbose(env, " => ");
817 verbose_arg_track(env, &new_val);
818 verbose(env, "\n");
819 return true;
820}
821
822/*
823 * Compute the result when an ALU op destroys offset precision.
824 * If a single arg is identifiable, preserve it with OFF_IMPRECISE.
825 * If two different args are involved or one is already ARG_IMPRECISE,
826 * the result is fully ARG_IMPRECISE.
827 */
828static void arg_track_alu64(struct arg_track *dst, const struct arg_track *src)
829{
830 WARN_ON_ONCE(!arg_is_visited(dst));
831 WARN_ON_ONCE(!arg_is_visited(src));
832
833 if (dst->frame >= 0 && (src->frame == ARG_NONE || src->frame == dst->frame)) {
834 /*
835 * rX += rY where rY is not arg derived
836 * rX += rX
837 */
838 dst->off_cnt = 0;
839 return;
840 }
841 if (src->frame >= 0 && dst->frame == ARG_NONE) {
842 /*
843 * rX += rY where rX is not arg derived
844 * rY identity leaks into rX
845 */
846 dst->off_cnt = 0;
847 dst->frame = src->frame;
848 return;
849 }
850
851 if (dst->frame == ARG_NONE && src->frame == ARG_NONE)
852 return;
853
854 *dst = arg_join_imprecise(*dst, *src);
855}
856
857static bool arg_add(s16 off, s64 delta, s16 *out)
858{
859 s16 d = delta;
860
861 if (d != delta)
862 return true;
863 return check_add_overflow(off, d, out);
864}
865
866static void arg_padd(struct arg_track *at, s64 delta)
867{
868 int i;
869
870 if (at->off_cnt == 0)
871 return;
872 for (i = 0; i < at->off_cnt; i++) {
873 s16 new_off;
874
875 if (arg_add(at->off[i], delta, &new_off)) {
876 at->off_cnt = 0;
877 return;
878 }
879 at->off[i] = new_off;
880 }
881}
882
883/*
884 * Convert a byte offset from FP to a callee stack slot index.
885 * Returns -1 if out of range or not 8-byte aligned.
886 * Slot 0 = fp-8, slot 1 = fp-16, ..., slot 7 = fp-64, ....
887 */
888static int fp_off_to_slot(s16 off)
889{
890 if (off >= 0 || off < -(int)(MAX_ARG_SPILL_SLOTS * 8))
891 return -1;
892 if (off % 8)
893 return -1;
894 return (-off) / 8 - 1;
895}
896
897static struct arg_track fill_from_stack(struct bpf_insn *insn,
898 struct arg_track *at_out, int reg,
899 struct arg_track *at_stack_out,
900 int depth)
901{
902 struct arg_track imp = {
903 .mask = (1u << (depth + 1)) - 1,
904 .frame = ARG_IMPRECISE
905 };
906 struct arg_track result = { .frame = ARG_NONE };
907 int cnt, i;
908
909 if (reg == BPF_REG_FP) {
910 int slot = fp_off_to_slot(insn->off);
911
912 return slot >= 0 ? at_stack_out[slot] : imp;
913 }
914 cnt = at_out[reg].off_cnt;
915 if (cnt == 0)
916 return imp;
917
918 for (i = 0; i < cnt; i++) {
919 s16 fp_off, slot;
920
921 if (arg_add(at_out[reg].off[i], insn->off, &fp_off))
922 return imp;
923 slot = fp_off_to_slot(fp_off);
924 if (slot < 0)
925 return imp;
926 result = __arg_track_join(result, at_stack_out[slot]);
927 }
928 return result;
929}
930
931/*
932 * Spill @val to all possible stack slots indicated by the FP offsets in @reg.
933 * For an 8-byte store, single candidate slot gets @val. multi-slots are joined.
934 * sub-8-byte store joins with ARG_NONE.
935 * When exact offset is unknown conservatively add reg values to all slots in at_stack_out.
936 */
937static void spill_to_stack(struct bpf_insn *insn, struct arg_track *at_out,
938 int reg, struct arg_track *at_stack_out,
939 struct arg_track *val, u32 sz)
940{
941 struct arg_track none = { .frame = ARG_NONE };
942 struct arg_track new_val = sz == 8 ? *val : none;
943 int cnt, i;
944
945 if (reg == BPF_REG_FP) {
946 int slot = fp_off_to_slot(insn->off);
947
948 if (slot >= 0)
949 at_stack_out[slot] = new_val;
950 return;
951 }
952 cnt = at_out[reg].off_cnt;
953 if (cnt == 0) {
954 for (int slot = 0; slot < MAX_ARG_SPILL_SLOTS; slot++)
955 at_stack_out[slot] = __arg_track_join(at_stack_out[slot], new_val);
956 return;
957 }
958 for (i = 0; i < cnt; i++) {
959 s16 fp_off;
960 int slot;
961
962 if (arg_add(at_out[reg].off[i], insn->off, &fp_off))
963 continue;
964 slot = fp_off_to_slot(fp_off);
965 if (slot < 0)
966 continue;
967 if (cnt == 1)
968 at_stack_out[slot] = new_val;
969 else
970 at_stack_out[slot] = __arg_track_join(at_stack_out[slot], new_val);
971 }
972}
973
974/*
975 * Clear all tracked callee stack slots overlapping the byte range
976 * [off, off+sz-1] where off is a negative FP-relative offset.
977 */
978static void clear_overlapping_stack_slots(struct arg_track *at_stack, s16 off, u32 sz, int cnt)
979{
980 struct arg_track none = { .frame = ARG_NONE };
981
982 if (cnt == 0) {
983 for (int i = 0; i < MAX_ARG_SPILL_SLOTS; i++)
984 at_stack[i] = __arg_track_join(at_stack[i], none);
985 return;
986 }
987 for (int i = 0; i < MAX_ARG_SPILL_SLOTS; i++) {
988 int slot_start = -((i + 1) * 8);
989 int slot_end = slot_start + 8;
990
991 if (slot_start < off + (int)sz && slot_end > off) {
992 if (cnt == 1)
993 at_stack[i] = none;
994 else
995 at_stack[i] = __arg_track_join(at_stack[i], none);
996 }
997 }
998}
999
1000/*
1001 * Clear stack slots overlapping all possible FP offsets in @reg.
1002 */
1003static void clear_stack_for_all_offs(struct bpf_insn *insn,
1004 struct arg_track *at_out, int reg,
1005 struct arg_track *at_stack_out, u32 sz)
1006{
1007 int cnt, i;
1008
1009 if (reg == BPF_REG_FP) {
1010 clear_overlapping_stack_slots(at_stack_out, insn->off, sz, 1);
1011 return;
1012 }
1013 cnt = at_out[reg].off_cnt;
1014 if (cnt == 0) {
1015 clear_overlapping_stack_slots(at_stack_out, 0, sz, cnt);
1016 return;
1017 }
1018 for (i = 0; i < cnt; i++) {
1019 s16 fp_off;
1020
1021 if (arg_add(at_out[reg].off[i], insn->off, &fp_off)) {
1022 clear_overlapping_stack_slots(at_stack_out, 0, sz, 0);
1023 break;
1024 }
1025 clear_overlapping_stack_slots(at_stack_out, fp_off, sz, cnt);
1026 }
1027}
1028
1029static void arg_track_log(struct bpf_verifier_env *env, struct bpf_insn *insn, int idx,
1030 struct arg_track *at_in, struct arg_track *at_stack_in,
1031 struct arg_track *at_out, struct arg_track *at_stack_out)
1032{
1033 bool printed = false;
1034 int i;
1035
1036 if (!(env->log.level & BPF_LOG_LEVEL2))
1037 return;
1038 for (i = 0; i < MAX_BPF_REG; i++) {
1039 if (arg_track_eq(&at_out[i], &at_in[i]))
1040 continue;
1041 if (!printed) {
1042 verbose(env, "%3d: ", idx);
1043 bpf_verbose_insn(env, insn);
1044 printed = true;
1045 }
1046 verbose(env, "\tr%d: ", i); verbose_arg_track(env, &at_in[i]);
1047 verbose(env, " -> "); verbose_arg_track(env, &at_out[i]);
1048 }
1049 /* Log outgoing stack arg slot transitions at indices MAX_BPF_REG..MAX_AT_TRACK_REGS-1 */
1050 for (i = 0; i < MAX_STACK_ARG_SLOTS; i++) {
1051 int ai = MAX_BPF_REG + i;
1052
1053 if (arg_track_eq(&at_out[ai], &at_in[ai]))
1054 continue;
1055 if (!printed) {
1056 verbose(env, "%3d: ", idx);
1057 bpf_verbose_insn(env, insn);
1058 printed = true;
1059 }
1060 verbose(env, "\tsa%d: ", i); verbose_arg_track(env, &at_in[ai]);
1061 verbose(env, " -> "); verbose_arg_track(env, &at_out[ai]);
1062 }
1063 for (i = 0; i < MAX_ARG_SPILL_SLOTS; i++) {
1064 if (arg_track_eq(&at_stack_out[i], &at_stack_in[i]))
1065 continue;
1066 if (!printed) {
1067 verbose(env, "%3d: ", idx);
1068 bpf_verbose_insn(env, insn);
1069 printed = true;
1070 }
1071 verbose(env, "\tfp%+d: ", -(i + 1) * 8); verbose_arg_track(env, &at_stack_in[i]);
1072 verbose(env, " -> "); verbose_arg_track(env, &at_stack_out[i]);
1073 }
1074 if (printed)
1075 verbose(env, "\n");
1076}
1077
1078static bool can_be_local_fp(int depth, int regno, struct arg_track *at)
1079{
1080 return regno == BPF_REG_FP || at->frame == depth ||
1081 (at->frame == ARG_IMPRECISE && (at->mask & BIT(depth)));
1082}
1083
1084/*
1085 * Pure dataflow transfer function for arg_track state.
1086 * Updates at_out[] based on how the instruction modifies registers.
1087 * Tracks spill/fill, but not other memory accesses.
1088 */
1089static void arg_track_xfer(struct bpf_verifier_env *env, struct bpf_insn *insn,
1090 int insn_idx,
1091 struct arg_track *at_out, struct arg_track *at_stack_out,
1092 const struct arg_track *at_stack_arg_entry,
1093 struct func_instance *instance,
1094 u32 *callsites)
1095{
1096 int depth = instance->depth;
1097 u8 class = BPF_CLASS(insn->code);
1098 u8 code = BPF_OP(insn->code);
1099 struct arg_track *dst = &at_out[insn->dst_reg];
1100 struct arg_track *src = &at_out[insn->src_reg];
1101 struct arg_track none = { .frame = ARG_NONE };
1102 int r, slot;
1103
1104 /* Handle stack arg stores and loads. */
1105 if (is_stack_arg_st(insn) || is_stack_arg_stx(insn)) {
1106 slot = stack_arg_off_to_slot(insn->off);
1107 if (slot >= 0) {
1108 if (is_stack_arg_stx(insn))
1109 at_out[MAX_BPF_REG + slot] = at_out[insn->src_reg];
1110 else
1111 at_out[MAX_BPF_REG + slot] = none;
1112 }
1113 } else if (is_stack_arg_ldx(insn)) {
1114 slot = stack_arg_off_to_slot(insn->off);
1115 at_out[insn->dst_reg] = (slot >= 0) ? at_stack_arg_entry[slot] : none;
1116 } else if (class == BPF_ALU64 && BPF_SRC(insn->code) == BPF_K) {
1117 if (code == BPF_MOV) {
1118 *dst = none;
1119 } else if (dst->frame >= 0) {
1120 if (code == BPF_ADD)
1121 arg_padd(dst, insn->imm);
1122 else if (code == BPF_SUB)
1123 arg_padd(dst, -(s64)insn->imm);
1124 else
1125 /* Any other 64-bit alu on the pointer makes it imprecise */
1126 dst->off_cnt = 0;
1127 } /* else if dst->frame is imprecise it stays so */
1128 } else if (class == BPF_ALU64 && BPF_SRC(insn->code) == BPF_X) {
1129 if (code == BPF_MOV) {
1130 if (insn->off == 0) {
1131 *dst = *src;
1132 } else {
1133 /* addr_space_cast destroys a pointer */
1134 *dst = none;
1135 }
1136 } else {
1137 arg_track_alu64(dst, src);
1138 }
1139 } else if (class == BPF_ALU) {
1140 /*
1141 * 32-bit alu destroys the pointer.
1142 * If src was a pointer it cannot leak into dst
1143 */
1144 *dst = none;
1145 } else if (class == BPF_JMP && code == BPF_CALL) {
1146 /*
1147 * at_stack_out[slot] is not cleared by the helper and subprog calls.
1148 * The fill_from_stack() may return the stale spill — which is an FP-derived arg_track
1149 * (the value that was originally spilled there). The loaded register then carries
1150 * a phantom FP-derived identity that doesn't correspond to what's actually in the slot.
1151 * This phantom FP pointer propagates forward, and wherever it's subsequently used
1152 * (as a helper argument, another store, etc.), it sets stack liveness bits.
1153 * Those bits correspond to stack accesses that don't actually happen.
1154 * So the effect is over-reporting stack liveness — marking slots as live that aren't
1155 * actually accessed. The verifier preserves more state than necessary across calls,
1156 * which is conservative.
1157 *
1158 * helpers can scratch stack slots, but they won't make a valid pointer out of it.
1159 * subprogs are allowed to write into parent slots, but they cannot write
1160 * _any_ FP-derived pointer into it (either their own or parent's FP).
1161 */
1162 for (r = BPF_REG_0; r <= BPF_REG_5; r++)
1163 at_out[r] = none;
1164 } else if (class == BPF_LDX) {
1165 u32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code));
1166 bool src_is_local_fp = can_be_local_fp(depth, insn->src_reg, src);
1167
1168 /*
1169 * Reload from callee stack: if src is current-frame FP-derived
1170 * and the load is an 8-byte BPF_MEM, try to restore the spill
1171 * identity. For imprecise sources fill_from_stack() returns
1172 * ARG_IMPRECISE (off_cnt == 0).
1173 */
1174 if (src_is_local_fp && BPF_MODE(insn->code) == BPF_MEM && sz == 8) {
1175 *dst = fill_from_stack(insn, at_out, insn->src_reg, at_stack_out, depth);
1176 } else if (src->frame >= 0 && src->frame < depth &&
1177 BPF_MODE(insn->code) == BPF_MEM && sz == 8) {
1178 struct arg_track *parent_stack =
1179 env->callsite_at_stack[callsites[src->frame]];
1180
1181 *dst = fill_from_stack(insn, at_out, insn->src_reg,
1182 parent_stack, src->frame);
1183 } else if (src->frame == ARG_IMPRECISE &&
1184 !(src->mask & BIT(depth)) && src->mask &&
1185 BPF_MODE(insn->code) == BPF_MEM && sz == 8) {
1186 /*
1187 * Imprecise src with only parent-frame bits:
1188 * conservative fallback.
1189 */
1190 *dst = *src;
1191 } else {
1192 *dst = none;
1193 }
1194 } else if (class == BPF_LD && BPF_MODE(insn->code) == BPF_IMM) {
1195 *dst = none;
1196 } else if (class == BPF_STX) {
1197 u32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code));
1198 bool dst_is_local_fp;
1199
1200 /* Track spills to current-frame FP-derived callee stack */
1201 dst_is_local_fp = can_be_local_fp(depth, insn->dst_reg, dst);
1202 if (dst_is_local_fp && BPF_MODE(insn->code) == BPF_MEM)
1203 spill_to_stack(insn, at_out, insn->dst_reg,
1204 at_stack_out, src, sz);
1205
1206 if (BPF_MODE(insn->code) == BPF_ATOMIC) {
1207 if (dst_is_local_fp && insn->imm != BPF_LOAD_ACQ)
1208 clear_stack_for_all_offs(insn, at_out, insn->dst_reg,
1209 at_stack_out, sz);
1210
1211 r = bpf_atomic_load_reg(insn);
1212 if (r >= 0)
1213 at_out[r] = none;
1214 }
1215 } else if (class == BPF_ST && BPF_MODE(insn->code) == BPF_MEM) {
1216 u32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code));
1217 bool dst_is_local_fp = can_be_local_fp(depth, insn->dst_reg, dst);
1218
1219 /* BPF_ST to FP-derived dst: clear overlapping stack slots */
1220 if (dst_is_local_fp)
1221 clear_stack_for_all_offs(insn, at_out, insn->dst_reg,
1222 at_stack_out, sz);
1223 }
1224}
1225
1226/*
1227 * Record access_bytes from helper/kfunc or load/store insn.
1228 * access_bytes > 0: stack read
1229 * access_bytes < 0: stack write
1230 * access_bytes == S64_MIN: unknown — conservative, mark [0..slot] as read
1231 * access_bytes == 0: no access
1232 *
1233 */
1234static int record_stack_access_off(struct func_instance *instance, s64 fp_off,
1235 s64 access_bytes, u32 frame, u32 insn_idx)
1236{
1237 s32 slot_hi, slot_lo;
1238 spis_t mask;
1239
1240 if (fp_off >= 0)
1241 /*
1242 * out of bounds stack access doesn't contribute
1243 * into actual stack liveness. It will be rejected
1244 * by the main verifier pass later.
1245 */
1246 return 0;
1247 if (access_bytes == S64_MIN) {
1248 /* helper/kfunc read unknown amount of bytes from fp_off until fp+0 */
1249 slot_hi = (-fp_off - 1) / STACK_SLOT_SZ;
1250 mask = SPIS_ZERO;
1251 spis_or_range(&mask, 0, slot_hi);
1252 return mark_stack_read(instance, frame, insn_idx, mask);
1253 }
1254 if (access_bytes > 0) {
1255 /* Mark any touched slot as use */
1256 slot_hi = (-fp_off - 1) / STACK_SLOT_SZ;
1257 slot_lo = max_t(s32, (-fp_off - access_bytes) / STACK_SLOT_SZ, 0);
1258 mask = SPIS_ZERO;
1259 spis_or_range(&mask, slot_lo, slot_hi);
1260 return mark_stack_read(instance, frame, insn_idx, mask);
1261 } else if (access_bytes < 0) {
1262 /* Mark only fully covered slots as def */
1263 access_bytes = -access_bytes;
1264 slot_hi = (-fp_off) / STACK_SLOT_SZ - 1;
1265 slot_lo = max_t(s32, (-fp_off - access_bytes + STACK_SLOT_SZ - 1) / STACK_SLOT_SZ, 0);
1266 if (slot_lo <= slot_hi) {
1267 mask = SPIS_ZERO;
1268 spis_or_range(&mask, slot_lo, slot_hi);
1269 return mark_stack_write(instance, frame, insn_idx, mask);
1270 }
1271 }
1272 return 0;
1273}
1274
1275/*
1276 * 'arg' is FP-derived argument to helper/kfunc or load/store that
1277 * reads (positive) or writes (negative) 'access_bytes' into 'use' or 'def'.
1278 */
1279static int record_stack_access(struct func_instance *instance,
1280 const struct arg_track *arg,
1281 s64 access_bytes, u32 frame, u32 insn_idx)
1282{
1283 int i, err;
1284
1285 if (access_bytes == 0)
1286 return 0;
1287 if (arg->off_cnt == 0) {
1288 if (access_bytes > 0 || access_bytes == S64_MIN)
1289 return mark_stack_read(instance, frame, insn_idx, SPIS_ALL);
1290 return 0;
1291 }
1292 if (access_bytes != S64_MIN && access_bytes < 0 && arg->off_cnt != 1)
1293 /* multi-offset write cannot set stack_def */
1294 return 0;
1295
1296 for (i = 0; i < arg->off_cnt; i++) {
1297 err = record_stack_access_off(instance, arg->off[i], access_bytes, frame, insn_idx);
1298 if (err)
1299 return err;
1300 }
1301 return 0;
1302}
1303
1304/*
1305 * When a pointer is ARG_IMPRECISE, conservatively mark every frame in
1306 * the bitmask as fully used.
1307 */
1308static int record_imprecise(struct func_instance *instance, u32 mask, u32 insn_idx)
1309{
1310 int depth = instance->depth;
1311 int f, err;
1312
1313 for (f = 0; mask; f++, mask >>= 1) {
1314 if (!(mask & 1))
1315 continue;
1316 if (f <= depth) {
1317 err = mark_stack_read(instance, f, insn_idx, SPIS_ALL);
1318 if (err)
1319 return err;
1320 }
1321 }
1322 return 0;
1323}
1324
1325/* Record load/store access for a given 'at' state of 'insn'. */
1326static int record_load_store_access(struct bpf_verifier_env *env,
1327 struct func_instance *instance,
1328 struct arg_track *at, int insn_idx)
1329{
1330 struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
1331 int depth = instance->depth;
1332 s32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code));
1333 u8 class = BPF_CLASS(insn->code);
1334 struct arg_track resolved, *ptr;
1335 int oi;
1336
1337 /*
1338 * Stack arg insns use dst_reg/src_reg=BPF_REG_PARAMS(11). Since at[]
1339 * is extended to MAX_AT_TRACK_REGS, at[11] holds the arg_track for
1340 * outgoing stack arg slot 0 — not the pointer used for the memory
1341 * access. Skip so the slot's tracked value isn't confused with the
1342 * base register that record_stack_access() expects.
1343 */
1344 if (is_stack_arg_stx(insn) || is_stack_arg_st(insn) || is_stack_arg_ldx(insn))
1345 return 0;
1346
1347 switch (class) {
1348 case BPF_LDX:
1349 ptr = &at[insn->src_reg];
1350 break;
1351 case BPF_STX:
1352 if (BPF_MODE(insn->code) == BPF_ATOMIC) {
1353 if (insn->imm == BPF_STORE_REL)
1354 sz = -sz;
1355 if (insn->imm == BPF_LOAD_ACQ)
1356 ptr = &at[insn->src_reg];
1357 else
1358 ptr = &at[insn->dst_reg];
1359 } else {
1360 ptr = &at[insn->dst_reg];
1361 sz = -sz;
1362 }
1363 break;
1364 case BPF_ST:
1365 ptr = &at[insn->dst_reg];
1366 sz = -sz;
1367 break;
1368 default:
1369 return 0;
1370 }
1371
1372 /* Resolve offsets: fold insn->off into arg_track */
1373 if (ptr->off_cnt > 0) {
1374 resolved.off_cnt = ptr->off_cnt;
1375 resolved.frame = ptr->frame;
1376 for (oi = 0; oi < ptr->off_cnt; oi++) {
1377 if (arg_add(ptr->off[oi], insn->off, &resolved.off[oi])) {
1378 resolved.off_cnt = 0;
1379 break;
1380 }
1381 }
1382 ptr = &resolved;
1383 }
1384
1385 if (ptr->frame >= 0 && ptr->frame <= depth)
1386 return record_stack_access(instance, ptr, sz, ptr->frame, insn_idx);
1387 if (ptr->frame == ARG_IMPRECISE)
1388 return record_imprecise(instance, ptr->mask, insn_idx);
1389 /* ARG_NONE: not derived from any frame pointer, skip */
1390 return 0;
1391}
1392
1393static int record_arg_access(struct bpf_verifier_env *env,
1394 struct func_instance *instance,
1395 struct bpf_insn *insn,
1396 struct arg_track *at, int arg_idx,
1397 int insn_idx)
1398{
1399 int depth = instance->depth;
1400 int frame = at->frame;
1401 int err = 0;
1402 s64 bytes;
1403
1404 if (!arg_is_fp(at))
1405 return 0;
1406
1407 if (bpf_helper_call(insn)) {
1408 bytes = bpf_helper_stack_access_bytes(env, insn, arg_idx, insn_idx);
1409 } else if (bpf_pseudo_kfunc_call(insn)) {
1410 bytes = bpf_kfunc_stack_access_bytes(env, insn, arg_idx, insn_idx);
1411 } else {
1412 for (int f = 0; f <= depth; f++) {
1413 err = mark_stack_read(instance, f, insn_idx, SPIS_ALL);
1414 if (err)
1415 return err;
1416 }
1417 return 0;
1418 }
1419 if (bytes == 0)
1420 return 0;
1421
1422 if (frame >= 0 && frame <= depth)
1423 err = record_stack_access(instance, at, bytes, frame, insn_idx);
1424 else if (frame == ARG_IMPRECISE)
1425 err = record_imprecise(instance, at->mask, insn_idx);
1426 return err;
1427}
1428
1429/* Record stack access for a given 'at' state of helper/kfunc 'insn' */
1430static int record_call_access(struct bpf_verifier_env *env,
1431 struct func_instance *instance,
1432 struct arg_track *at,
1433 int insn_idx)
1434{
1435 struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
1436 struct bpf_call_summary cs;
1437 int r, err, num_params = 5;
1438
1439 if (bpf_pseudo_call(insn))
1440 return 0;
1441
1442 if (bpf_get_call_summary(env, insn, &cs))
1443 num_params = cs.num_params;
1444
1445 for (r = BPF_REG_1; r < BPF_REG_1 + min(num_params, MAX_BPF_FUNC_REG_ARGS); r++) {
1446 err = record_arg_access(env, instance, insn, &at[r], r - 1, insn_idx);
1447 if (err)
1448 return err;
1449 }
1450
1451 for (r = 0; r < MAX_STACK_ARG_SLOTS && r < num_params - MAX_BPF_FUNC_REG_ARGS; r++) {
1452 err = record_arg_access(env, instance, insn, &at[MAX_BPF_REG + r],
1453 r + MAX_BPF_FUNC_REG_ARGS, insn_idx);
1454 if (err)
1455 return err;
1456 }
1457 return 0;
1458}
1459
1460/*
1461 * For a calls_callback helper, find the callback subprog and determine
1462 * which caller register maps to which callback register for FP passthrough.
1463 */
1464static int find_callback_subprog(struct bpf_verifier_env *env,
1465 struct bpf_insn *insn, int insn_idx,
1466 int *caller_reg, int *callee_reg)
1467{
1468 struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
1469 int cb_reg = -1;
1470
1471 *caller_reg = -1;
1472 *callee_reg = -1;
1473
1474 if (!bpf_helper_call(insn))
1475 return -1;
1476 switch (insn->imm) {
1477 case BPF_FUNC_loop:
1478 /* bpf_loop(nr, cb, ctx, flags): cb=R2, R3->cb R2 */
1479 cb_reg = BPF_REG_2;
1480 *caller_reg = BPF_REG_3;
1481 *callee_reg = BPF_REG_2;
1482 break;
1483 case BPF_FUNC_for_each_map_elem:
1484 /* for_each_map_elem(map, cb, ctx, flags): cb=R2, R3->cb R4 */
1485 cb_reg = BPF_REG_2;
1486 *caller_reg = BPF_REG_3;
1487 *callee_reg = BPF_REG_4;
1488 break;
1489 case BPF_FUNC_find_vma:
1490 /* find_vma(task, addr, cb, ctx, flags): cb=R3, R4->cb R3 */
1491 cb_reg = BPF_REG_3;
1492 *caller_reg = BPF_REG_4;
1493 *callee_reg = BPF_REG_3;
1494 break;
1495 case BPF_FUNC_user_ringbuf_drain:
1496 /* user_ringbuf_drain(map, cb, ctx, flags): cb=R2, R3->cb R2 */
1497 cb_reg = BPF_REG_2;
1498 *caller_reg = BPF_REG_3;
1499 *callee_reg = BPF_REG_2;
1500 break;
1501 default:
1502 return -1;
1503 }
1504
1505 if (!(aux->const_reg_subprog_mask & BIT(cb_reg)))
1506 return -2;
1507
1508 return aux->const_reg_vals[cb_reg];
1509}
1510
1511/* Per-subprog intermediate state kept alive across analysis phases */
1512struct subprog_at_info {
1513 struct arg_track (*at_in)[MAX_AT_TRACK_REGS];
1514 int len;
1515};
1516
1517static void print_subprog_arg_access(struct bpf_verifier_env *env,
1518 int subprog,
1519 struct subprog_at_info *info,
1520 struct arg_track (*at_stack_in)[MAX_ARG_SPILL_SLOTS])
1521{
1522 struct bpf_insn *insns = env->prog->insnsi;
1523 int start = env->subprog_info[subprog].start;
1524 int len = info->len;
1525 int i, r;
1526
1527 if (!(env->log.level & BPF_LOG_LEVEL2))
1528 return;
1529
1530 verbose(env, "%s:\n", fmt_subprog(env, subprog));
1531 for (i = 0; i < len; i++) {
1532 int idx = start + i;
1533 bool has_extra = false;
1534 u8 cls = BPF_CLASS(insns[idx].code);
1535 bool is_ldx_stx_call = cls == BPF_LDX || cls == BPF_STX ||
1536 insns[idx].code == (BPF_JMP | BPF_CALL);
1537
1538 verbose(env, "%3d: ", idx);
1539 bpf_verbose_insn(env, &insns[idx]);
1540 verbose(env, "\n");
1541
1542 /* Collect what needs printing */
1543 if (is_ldx_stx_call &&
1544 arg_is_visited(&info->at_in[i][0])) {
1545 for (r = 0; r < MAX_BPF_REG - 1; r++)
1546 if (arg_is_fp(&info->at_in[i][r]))
1547 has_extra = true;
1548 for (r = 0; r < MAX_STACK_ARG_SLOTS; r++)
1549 if (arg_is_fp(&info->at_in[i][MAX_BPF_REG + r]))
1550 has_extra = true;
1551 }
1552 if (is_ldx_stx_call) {
1553 for (r = 0; r < MAX_ARG_SPILL_SLOTS; r++)
1554 if (arg_is_fp(&at_stack_in[i][r]))
1555 has_extra = true;
1556 }
1557
1558 if (!has_extra) {
1559 if (bpf_is_ldimm64(&insns[idx]))
1560 i++;
1561 continue;
1562 }
1563
1564 bpf_vlog_reset(&env->log, env->log.end_pos - 1);
1565 verbose(env, " //");
1566
1567 if (is_ldx_stx_call && info->at_in &&
1568 arg_is_visited(&info->at_in[i][0])) {
1569 for (r = 0; r < MAX_BPF_REG - 1; r++) {
1570 if (!arg_is_fp(&info->at_in[i][r]))
1571 continue;
1572 verbose(env, " r%d=", r);
1573 verbose_arg_track(env, &info->at_in[i][r]);
1574 }
1575 for (r = 0; r < MAX_STACK_ARG_SLOTS; r++) {
1576 if (!arg_is_fp(&info->at_in[i][MAX_BPF_REG + r]))
1577 continue;
1578 verbose(env, " sa%d=", r);
1579 verbose_arg_track(env, &info->at_in[i][MAX_BPF_REG + r]);
1580 }
1581 }
1582
1583 if (is_ldx_stx_call) {
1584 for (r = 0; r < MAX_ARG_SPILL_SLOTS; r++) {
1585 if (!arg_is_fp(&at_stack_in[i][r]))
1586 continue;
1587 verbose(env, " fp%+d=", -(r + 1) * 8);
1588 verbose_arg_track(env, &at_stack_in[i][r]);
1589 }
1590 }
1591
1592 verbose(env, "\n");
1593 if (bpf_is_ldimm64(&insns[idx]))
1594 i++;
1595 }
1596}
1597
1598/*
1599 * Compute arg tracking dataflow for a single subprog.
1600 * Runs forward fixed-point with arg_track_xfer(), then records
1601 * memory accesses in a single linear pass over converged state.
1602 *
1603 * @callee_entry: pre-populated entry state for R1-R5 and stack args
1604 * NULL for main (subprog 0).
1605 * @info: stores at_in, len for debug printing.
1606 */
1607static int compute_subprog_args(struct bpf_verifier_env *env,
1608 struct subprog_at_info *info,
1609 struct arg_track *callee_entry,
1610 struct func_instance *instance,
1611 u32 *callsites)
1612{
1613 int subprog = instance->subprog;
1614 struct bpf_insn *insns = env->prog->insnsi;
1615 int depth = instance->depth;
1616 int start = env->subprog_info[subprog].start;
1617 int po_start = env->subprog_info[subprog].postorder_start;
1618 int end = env->subprog_info[subprog + 1].start;
1619 int po_end = env->subprog_info[subprog + 1].postorder_start;
1620 int len = end - start;
1621 struct arg_track (*at_in)[MAX_AT_TRACK_REGS] = NULL;
1622 struct arg_track at_out[MAX_AT_TRACK_REGS];
1623 struct arg_track (*at_stack_in)[MAX_ARG_SPILL_SLOTS] = NULL;
1624 struct arg_track *at_stack_out = NULL;
1625 struct arg_track at_stack_arg_entry[MAX_STACK_ARG_SLOTS];
1626 struct arg_track unvisited = { .frame = ARG_UNVISITED };
1627 struct arg_track none = { .frame = ARG_NONE };
1628 bool changed;
1629 int i, p, r, err = -ENOMEM;
1630
1631 at_in = kvmalloc_objs(*at_in, len, GFP_KERNEL_ACCOUNT);
1632 if (!at_in)
1633 goto err_free;
1634
1635 at_stack_in = kvmalloc_objs(*at_stack_in, len, GFP_KERNEL_ACCOUNT);
1636 if (!at_stack_in)
1637 goto err_free;
1638
1639 at_stack_out = kvmalloc_objs(*at_stack_out, MAX_ARG_SPILL_SLOTS, GFP_KERNEL_ACCOUNT);
1640 if (!at_stack_out)
1641 goto err_free;
1642
1643 for (i = 0; i < len; i++) {
1644 for (r = 0; r < MAX_AT_TRACK_REGS; r++)
1645 at_in[i][r] = unvisited;
1646 for (r = 0; r < MAX_ARG_SPILL_SLOTS; r++)
1647 at_stack_in[i][r] = unvisited;
1648 }
1649
1650 for (r = 0; r < MAX_AT_TRACK_REGS; r++)
1651 at_in[0][r] = none;
1652
1653 /* Entry: R10 is always precisely the current frame's FP */
1654 at_in[0][BPF_REG_FP] = arg_single(depth, 0);
1655
1656 /* R1-R5: from caller or ARG_NONE for main */
1657 if (callee_entry) {
1658 for (r = BPF_REG_1; r <= BPF_REG_5; r++)
1659 at_in[0][r] = callee_entry[r];
1660 }
1661
1662 /* Entry: all stack slots are ARG_NONE */
1663 for (r = 0; r < MAX_ARG_SPILL_SLOTS; r++)
1664 at_stack_in[0][r] = none;
1665
1666 /* Entry: incoming stack args from caller, or ARG_NONE for main */
1667 for (r = 0; r < MAX_STACK_ARG_SLOTS; r++)
1668 at_stack_arg_entry[r] = callee_entry ? callee_entry[MAX_BPF_REG + r] : none;
1669
1670 if (env->log.level & BPF_LOG_LEVEL2)
1671 verbose(env, "subprog#%d: analyzing (depth %d)...\n", subprog, depth);
1672
1673 /* Forward fixed-point iteration in reverse post order */
1674redo:
1675 changed = false;
1676 for (p = po_end - 1; p >= po_start; p--) {
1677 int idx = env->cfg.insn_postorder[p];
1678 int i = idx - start;
1679 struct bpf_insn *insn = &insns[idx];
1680 struct bpf_iarray *succ;
1681
1682 if (!arg_is_visited(&at_in[i][0]) && !arg_is_visited(&at_in[i][1]))
1683 continue;
1684
1685 memcpy(at_out, at_in[i], sizeof(at_out));
1686 memcpy(at_stack_out, at_stack_in[i], MAX_ARG_SPILL_SLOTS * sizeof(*at_stack_out));
1687
1688 arg_track_xfer(env, insn, idx, at_out, at_stack_out,
1689 at_stack_arg_entry, instance, callsites);
1690 arg_track_log(env, insn, idx, at_in[i], at_stack_in[i], at_out, at_stack_out);
1691
1692 /* Propagate to successors within this subprogram */
1693 succ = bpf_insn_successors(env, idx);
1694 for (int s = 0; s < succ->cnt; s++) {
1695 int target = succ->items[s];
1696 int ti;
1697
1698 /* Filter: stay within the subprogram's range */
1699 if (target < start || target >= end)
1700 continue;
1701 ti = target - start;
1702
1703 for (r = 0; r < MAX_AT_TRACK_REGS; r++)
1704 changed |= arg_track_join(env, idx, target, r,
1705 &at_in[ti][r], at_out[r]);
1706
1707 for (r = 0; r < MAX_ARG_SPILL_SLOTS; r++)
1708 changed |= arg_track_join(env, idx, target, -r - 1,
1709 &at_stack_in[ti][r], at_stack_out[r]);
1710 }
1711 }
1712 if (changed)
1713 goto redo;
1714
1715 /* Record memory accesses using converged at_in (RPO skips dead code) */
1716 for (p = po_end - 1; p >= po_start; p--) {
1717 int idx = env->cfg.insn_postorder[p];
1718 int i = idx - start;
1719 struct bpf_insn *insn = &insns[idx];
1720
1721 err = record_load_store_access(env, instance, at_in[i], idx);
1722 if (err)
1723 goto err_free;
1724
1725 if (insn->code == (BPF_JMP | BPF_CALL)) {
1726 err = record_call_access(env, instance, at_in[i], idx);
1727 if (err)
1728 goto err_free;
1729 }
1730
1731 if (bpf_pseudo_call(insn) || bpf_calls_callback(env, idx)) {
1732 kvfree(env->callsite_at_stack[idx]);
1733 env->callsite_at_stack[idx] =
1734 kvmalloc_objs(*env->callsite_at_stack[idx],
1735 MAX_ARG_SPILL_SLOTS, GFP_KERNEL_ACCOUNT);
1736 if (!env->callsite_at_stack[idx]) {
1737 err = -ENOMEM;
1738 goto err_free;
1739 }
1740 memcpy(env->callsite_at_stack[idx],
1741 at_stack_in[i], sizeof(struct arg_track) * MAX_ARG_SPILL_SLOTS);
1742 }
1743 }
1744
1745 info->at_in = at_in;
1746 at_in = NULL;
1747 info->len = len;
1748 print_subprog_arg_access(env, subprog, info, at_stack_in);
1749 err = 0;
1750
1751err_free:
1752 kvfree(at_stack_out);
1753 kvfree(at_stack_in);
1754 kvfree(at_in);
1755 return err;
1756}
1757
1758/* Return true if any of R1-R5 or stack args is derived from a frame pointer. */
1759static bool has_fp_args(struct arg_track *args)
1760{
1761 for (int r = BPF_REG_1; r <= BPF_REG_5; r++)
1762 if (arg_is_fp(&args[r]))
1763 return true;
1764 for (int r = 0; r < MAX_STACK_ARG_SLOTS; r++)
1765 if (arg_is_fp(&args[MAX_BPF_REG + r]))
1766 return true;
1767 return false;
1768}
1769
1770/*
1771 * Merge a freshly analyzed instance into the original.
1772 * may_read: union (any pass might read the slot).
1773 * must_write: intersection (only slots written on ALL passes are guaranteed).
1774 * live_before is recomputed by a subsequent update_instance() on @dst.
1775 */
1776static void merge_instances(struct func_instance *dst, struct func_instance *src)
1777{
1778 int f, i;
1779
1780 for (f = 0; f <= dst->depth; f++) {
1781 if (!src->frames[f]) {
1782 /* This pass didn't touch frame f — must_write intersects with empty. */
1783 if (dst->frames[f])
1784 for (i = 0; i < dst->insn_cnt; i++)
1785 dst->frames[f][i].must_write = SPIS_ZERO;
1786 continue;
1787 }
1788 if (!dst->frames[f]) {
1789 /* Previous pass didn't touch frame f — take src, zero must_write. */
1790 dst->frames[f] = src->frames[f];
1791 src->frames[f] = NULL;
1792 for (i = 0; i < dst->insn_cnt; i++)
1793 dst->frames[f][i].must_write = SPIS_ZERO;
1794 continue;
1795 }
1796 for (i = 0; i < dst->insn_cnt; i++) {
1797 dst->frames[f][i].may_read =
1798 spis_or(dst->frames[f][i].may_read,
1799 src->frames[f][i].may_read);
1800 dst->frames[f][i].must_write =
1801 spis_and(dst->frames[f][i].must_write,
1802 src->frames[f][i].must_write);
1803 }
1804 }
1805}
1806
1807static struct func_instance *fresh_instance(struct func_instance *src)
1808{
1809 struct func_instance *f;
1810
1811 f = kvzalloc_obj(*f, GFP_KERNEL_ACCOUNT);
1812 if (!f)
1813 return ERR_PTR(-ENOMEM);
1814 f->callsite = src->callsite;
1815 f->depth = src->depth;
1816 f->subprog = src->subprog;
1817 f->subprog_start = src->subprog_start;
1818 f->insn_cnt = src->insn_cnt;
1819 return f;
1820}
1821
1822static void free_instance(struct func_instance *instance)
1823{
1824 int i;
1825
1826 for (i = 0; i <= instance->depth; i++)
1827 kvfree(instance->frames[i]);
1828 kvfree(instance);
1829}
1830
1831/*
1832 * Recursively analyze a subprog with specific 'entry_args'.
1833 * Each callee is analyzed with the exact args from its call site.
1834 *
1835 * Args are recomputed for each call because the dataflow result at_in[]
1836 * depends on the entry args and frame depth. Consider: A->C->D and B->C->D
1837 * Callsites in A and B pass different args into C, so C is recomputed.
1838 * Then within C the same callsite passes different args into D.
1839 */
1840static int analyze_subprog(struct bpf_verifier_env *env,
1841 struct arg_track *entry_args,
1842 struct subprog_at_info *info,
1843 struct func_instance *instance,
1844 u32 *callsites)
1845{
1846 int subprog = instance->subprog;
1847 int depth = instance->depth;
1848 struct bpf_insn *insns = env->prog->insnsi;
1849 int start = env->subprog_info[subprog].start;
1850 int po_start = env->subprog_info[subprog].postorder_start;
1851 int po_end = env->subprog_info[subprog + 1].postorder_start;
1852 struct func_instance *prev_instance = NULL;
1853 int j, err;
1854
1855 if (++env->liveness->subprog_calls > 10000) {
1856 verbose(env, "liveness analysis exceeded complexity limit (%d calls)\n",
1857 env->liveness->subprog_calls);
1858 return -E2BIG;
1859 }
1860
1861 if (need_resched())
1862 cond_resched();
1863
1864 /*
1865 * When an instance is reused (must_write_initialized == true),
1866 * record into a fresh instance and merge afterward. This avoids
1867 * stale must_write marks for instructions not reached in this pass.
1868 */
1869 if (instance->must_write_initialized) {
1870 struct func_instance *fresh = fresh_instance(instance);
1871
1872 if (IS_ERR(fresh))
1873 return PTR_ERR(fresh);
1874 prev_instance = instance;
1875 instance = fresh;
1876 }
1877
1878 /* Free prior analysis if this subprog was already visited */
1879 kvfree(info[subprog].at_in);
1880 info[subprog].at_in = NULL;
1881
1882 err = compute_subprog_args(env, &info[subprog], entry_args, instance, callsites);
1883 if (err)
1884 goto out_free;
1885
1886 /* For each reachable call site in the subprog, recurse into callees */
1887 for (int p = po_start; p < po_end; p++) {
1888 int idx = env->cfg.insn_postorder[p];
1889 struct arg_track callee_args[MAX_AT_TRACK_REGS] = {};
1890 struct arg_track none = { .frame = ARG_NONE };
1891 struct bpf_insn *insn = &insns[idx];
1892 struct func_instance *callee_instance;
1893 int callee, target;
1894 int caller_reg, cb_callee_reg;
1895
1896 j = idx - start; /* relative index within this subprog */
1897
1898 if (bpf_pseudo_call(insn)) {
1899 target = idx + insn->imm + 1;
1900 callee = bpf_find_subprog(env, target);
1901 if (callee < 0)
1902 continue;
1903
1904 /* Build entry args: R1-R5 and stack args from at_in at call site */
1905 for (int r = BPF_REG_1; r <= BPF_REG_5; r++)
1906 callee_args[r] = info[subprog].at_in[j][r];
1907 for (int r = 0; r < MAX_STACK_ARG_SLOTS; r++)
1908 callee_args[MAX_BPF_REG + r] = info[subprog].at_in[j][MAX_BPF_REG + r];
1909 } else if (bpf_calls_callback(env, idx)) {
1910 callee = find_callback_subprog(env, insn, idx, &caller_reg, &cb_callee_reg);
1911 if (callee == -2) {
1912 /*
1913 * same bpf_loop() calls two different callbacks and passes
1914 * stack pointer to them
1915 */
1916 if (info[subprog].at_in[j][caller_reg].frame == ARG_NONE)
1917 continue;
1918 for (int f = 0; f <= depth; f++) {
1919 err = mark_stack_read(instance, f, idx, SPIS_ALL);
1920 if (err)
1921 goto out_free;
1922 }
1923 continue;
1924 }
1925 if (callee < 0)
1926 continue;
1927
1928 for (int r = BPF_REG_1; r <= BPF_REG_5; r++)
1929 callee_args[r] = none;
1930 for (int r = 0; r < MAX_STACK_ARG_SLOTS; r++)
1931 callee_args[MAX_BPF_REG + r] = none;
1932 callee_args[cb_callee_reg] = info[subprog].at_in[j][caller_reg];
1933 } else {
1934 continue;
1935 }
1936
1937 if (!has_fp_args(callee_args))
1938 continue;
1939
1940 if (depth == MAX_CALL_FRAMES - 1) {
1941 err = -EINVAL;
1942 goto out_free;
1943 }
1944
1945 callee_instance = call_instance(env, instance, idx, callee);
1946 if (IS_ERR(callee_instance)) {
1947 err = PTR_ERR(callee_instance);
1948 goto out_free;
1949 }
1950 callsites[depth] = idx;
1951 err = analyze_subprog(env, callee_args, info, callee_instance, callsites);
1952 if (err)
1953 goto out_free;
1954
1955 /* Pull callee's entry liveness back to caller's callsite */
1956 {
1957 u32 callee_start = callee_instance->subprog_start;
1958 struct per_frame_masks *entry;
1959
1960 for (int f = 0; f < callee_instance->depth; f++) {
1961 entry = get_frame_masks(callee_instance, f, callee_start);
1962 if (!entry)
1963 continue;
1964 err = mark_stack_read(instance, f, idx, entry->live_before);
1965 if (err)
1966 goto out_free;
1967 }
1968 }
1969 }
1970
1971 if (prev_instance) {
1972 merge_instances(prev_instance, instance);
1973 free_instance(instance);
1974 instance = prev_instance;
1975 }
1976 update_instance(env, instance);
1977 return 0;
1978
1979out_free:
1980 if (prev_instance)
1981 free_instance(instance);
1982 return err;
1983}
1984
1985int bpf_compute_subprog_arg_access(struct bpf_verifier_env *env)
1986{
1987 u32 callsites[MAX_CALL_FRAMES] = {};
1988 int insn_cnt = env->prog->len;
1989 struct func_instance *instance;
1990 struct subprog_at_info *info;
1991 int k, err = 0;
1992
1993 info = kvzalloc_objs(*info, env->subprog_cnt, GFP_KERNEL_ACCOUNT);
1994 if (!info)
1995 return -ENOMEM;
1996
1997 env->callsite_at_stack = kvzalloc_objs(*env->callsite_at_stack, insn_cnt,
1998 GFP_KERNEL_ACCOUNT);
1999 if (!env->callsite_at_stack) {
2000 kvfree(info);
2001 return -ENOMEM;
2002 }
2003
2004 /*
2005 * Analyze every subprog in reverse topological order (callers
2006 * before callees) so that each subprog is analyzed before its
2007 * callees, allowing the recursive walk inside analyze_subprog()
2008 * to naturally reach callees that receive FP-derived args.
2009 *
2010 * Subprogs and callbacks that don't receive FP-derived arguments
2011 * cannot access ancestor stack frames are analyzed independently.
2012 * Async callbacks (timer, workqueue) are handled the same way.
2013 */
2014 for (k = env->subprog_cnt - 1; k >= 0; k--) {
2015 int sub = env->subprog_topo_order[k];
2016
2017 if (info[sub].at_in && !bpf_subprog_is_global(env, sub))
2018 continue;
2019 instance = call_instance(env, NULL, 0, sub);
2020 if (IS_ERR(instance)) {
2021 err = PTR_ERR(instance);
2022 goto out;
2023 }
2024 err = analyze_subprog(env, NULL, info, instance, callsites);
2025 if (err)
2026 goto out;
2027 }
2028
2029 if (env->log.level & BPF_LOG_LEVEL2)
2030 err = print_instances(env);
2031
2032out:
2033 for (k = 0; k < insn_cnt; k++)
2034 kvfree(env->callsite_at_stack[k]);
2035 kvfree(env->callsite_at_stack);
2036 env->callsite_at_stack = NULL;
2037 for (k = 0; k < env->subprog_cnt; k++)
2038 kvfree(info[k].at_in);
2039 kvfree(info);
2040 return err;
2041}
2042
2043/* Each field is a register bitmask */
2044struct insn_live_regs {
2045 u32 use; /* registers read by instruction */
2046 u32 def; /* registers written by instruction */
2047 u32 in; /* registers that may be alive before instruction */
2048 u32 out; /* registers that may be alive after instruction */
2049};
2050
2051/* Bitmask with 1s for all caller saved registers */
2052#define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1)
2053
2054static inline u32 reg32_mask(u32 n) { return BIT(n); }
2055static inline u32 reg64_mask(u32 n) { return BIT(n) | BIT(n + 16); }
2056static inline u32 mask_widen(u32 m) { return m | (m << 16); }
2057static inline u16 mask_lo(u32 m) { return (u16)m; }
2058static inline u16 mask_hi(u32 m) { return (u16)(m >> 16); }
2059
2060/* Compute info->{use,def} fields for the instruction */
2061static void compute_insn_live_regs(struct bpf_verifier_env *env,
2062 struct bpf_insn *insn,
2063 struct insn_live_regs *info)
2064{
2065 struct bpf_call_summary cs;
2066 const u8 class = BPF_CLASS(insn->code);
2067 const u8 code = BPF_OP(insn->code);
2068 const u8 mode = BPF_MODE(insn->code);
2069 const u8 size = BPF_SIZE(insn->code);
2070 const u32 src = reg64_mask(insn->src_reg);
2071 const u32 dst = reg64_mask(insn->dst_reg);
2072 const u32 src32 = mask_lo(src);
2073 const u32 dst32 = mask_lo(dst);
2074 const u32 r0 = reg64_mask(0);
2075 u32 def = 0;
2076 u32 use = U32_MAX;
2077
2078 switch (class) {
2079 case BPF_LD:
2080 switch (mode) {
2081 case BPF_IMM:
2082 if (BPF_SIZE(insn->code) == BPF_DW) {
2083 def = dst;
2084 use = 0;
2085 }
2086 break;
2087 case BPF_ABS:
2088 case BPF_IND:
2089 /* stick with defaults */
2090 break;
2091 }
2092 break;
2093 case BPF_LDX:
2094 switch (mode) {
2095 case BPF_MEM:
2096 /* a narrow load still redefines the whole register */
2097 def = dst;
2098 use = src;
2099 break;
2100 case BPF_MEMSX:
2101 /*
2102 * sign extension defines the whole register;
2103 * src holds a pointer, hence is used as 64-bit.
2104 */
2105 def = dst;
2106 use = src;
2107 break;
2108 }
2109 break;
2110 case BPF_ST:
2111 switch (mode) {
2112 case BPF_MEM:
2113 def = 0;
2114 use = dst;
2115 break;
2116 }
2117 break;
2118 case BPF_STX:
2119 switch (mode) {
2120 case BPF_MEM:
2121 def = 0;
2122 use = dst | (size == BPF_DW ? src : src32);
2123 break;
2124 case BPF_ATOMIC: {
2125 /*
2126 * dst holds a pointer and is always used as 64-bit;
2127 * the value operand and r0 are read as 32-bit for BPF_W atomics.
2128 */
2129 u32 srcv = size == BPF_DW ? src : src32;
2130 u32 r0v = size == BPF_DW ? r0 : mask_lo(r0);
2131
2132 switch (insn->imm) {
2133 case BPF_CMPXCHG:
2134 use = r0v | dst | srcv;
2135 def = r0;
2136 break;
2137 case BPF_LOAD_ACQ:
2138 def = dst;
2139 use = src;
2140 break;
2141 case BPF_STORE_REL:
2142 def = 0;
2143 use = dst | srcv;
2144 break;
2145 default:
2146 use = dst | srcv;
2147 if (insn->imm & BPF_FETCH)
2148 def = src;
2149 else
2150 def = 0;
2151 }
2152 break;
2153 }
2154 }
2155 break;
2156 case BPF_ALU:
2157 case BPF_ALU64:
2158 switch (code) {
2159 case BPF_END:
2160 use = dst;
2161 def = dst;
2162 break;
2163 case BPF_MOV:
2164 def = dst;
2165 if (BPF_SRC(insn->code) == BPF_K)
2166 use = 0;
2167 else
2168 use = class == BPF_ALU64 ? src : src32;
2169 break;
2170 default:
2171 def = dst;
2172 if (BPF_SRC(insn->code) == BPF_K)
2173 use = class == BPF_ALU64 ? dst : dst32;
2174 else
2175 use = class == BPF_ALU64 ? (dst | src) : (dst32 | src32);
2176 }
2177 break;
2178 case BPF_JMP:
2179 case BPF_JMP32:
2180 switch (code) {
2181 case BPF_JA:
2182 def = 0;
2183 if (BPF_SRC(insn->code) == BPF_X)
2184 use = dst;
2185 else
2186 use = 0;
2187 break;
2188 case BPF_JCOND:
2189 def = 0;
2190 use = 0;
2191 break;
2192 case BPF_EXIT:
2193 def = 0;
2194 use = r0;
2195 break;
2196 case BPF_CALL:
2197 def = ALL_CALLER_SAVED_REGS;
2198 use = def & ~BIT(BPF_REG_0);
2199 if (bpf_get_call_summary(env, insn, &cs))
2200 use = GENMASK(min_t(u8, cs.num_params, MAX_BPF_FUNC_REG_ARGS), 1);
2201 def = mask_widen(def);
2202 use = mask_widen(use);
2203 break;
2204 default:
2205 def = 0;
2206 use = class == BPF_JMP ? dst : dst32;
2207 if (BPF_SRC(insn->code) == BPF_X)
2208 use |= class == BPF_JMP ? src : src32;
2209 }
2210 break;
2211 }
2212
2213 info->def = def;
2214 info->use = use;
2215}
2216
2217/* Compute may-live registers after each instruction in the program.
2218 * The register is live after the instruction I if it is read by some
2219 * instruction S following I during program execution and is not
2220 * overwritten between I and S.
2221 *
2222 * Store result in env->insn_aux_data[i].live_regs.
2223 */
2224int bpf_compute_live_registers(struct bpf_verifier_env *env)
2225{
2226 struct bpf_insn_aux_data *insn_aux = env->insn_aux_data;
2227 struct bpf_insn *insns = env->prog->insnsi;
2228 struct insn_live_regs *state;
2229 int insn_cnt = env->prog->len;
2230 u64 pos, insn_pos;
2231 int err = 0, i, j;
2232 bool changed;
2233
2234 /* Use the following algorithm:
2235 * - define the following:
2236 * - I.use : a set of all registers read by instruction I;
2237 * - I.def : a set of all registers written by instruction I;
2238 * - I.in : a set of all registers that may be alive before I execution;
2239 * - I.out : a set of all registers that may be alive after I execution;
2240 * - insn_successors(I): a set of instructions S that might immediately
2241 * follow I for some program execution;
2242 * - associate separate empty sets 'I.in' and 'I.out' with each instruction;
2243 * - visit each instruction in a postorder and update
2244 * state[i].in, state[i].out as follows:
2245 *
2246 * state[i].out = U [state[s].in for S in insn_successors(i)]
2247 * state[i].in = (state[i].out / state[i].def) U state[i].use
2248 *
2249 * (where U stands for set union, / stands for set difference)
2250 * - repeat the computation while {in,out} fields changes for
2251 * any instruction.
2252 */
2253 state = kvzalloc_objs(*state, insn_cnt, GFP_KERNEL_ACCOUNT);
2254 if (!state) {
2255 err = -ENOMEM;
2256 goto out;
2257 }
2258
2259 for (i = 0; i < insn_cnt; ++i)
2260 compute_insn_live_regs(env, &insns[i], &state[i]);
2261
2262 /* Forward pass: resolve stack access through FP-derived pointers */
2263 err = bpf_compute_subprog_arg_access(env);
2264 if (err)
2265 goto out;
2266
2267 changed = true;
2268 while (changed) {
2269 changed = false;
2270 for (i = 0; i < env->cfg.cur_postorder; ++i) {
2271 int insn_idx = env->cfg.insn_postorder[i];
2272 struct insn_live_regs *live = &state[insn_idx];
2273 struct bpf_iarray *succ;
2274 u32 new_out = 0;
2275 u32 new_in = 0;
2276
2277 succ = bpf_insn_successors(env, insn_idx);
2278 for (int s = 0; s < succ->cnt; ++s)
2279 new_out |= state[succ->items[s]].in;
2280 new_in = (new_out & ~live->def) | live->use;
2281 if (new_out != live->out || new_in != live->in) {
2282 live->in = new_in;
2283 live->out = new_out;
2284 changed = true;
2285 }
2286 }
2287 }
2288
2289 for (i = 0; i < insn_cnt; ++i) {
2290 int def32 = bpf_insn_def32(env->prog, &insns[i]);
2291 u32 out = state[i].out;
2292 u32 in = state[i].in;
2293
2294 insn_aux[i].live_regs_before = mask_lo(in) | mask_hi(in);
2295 /*
2296 * On architectures where 32-bit operations do not reset upper halves
2297 * of the registers, the verifier needs to zero extend a destination
2298 * register if an instruction defines a 32-bit subregister and the
2299 * upper half of that register is alive after the instruction.
2300 */
2301 insn_aux[i].zext_dst = def32 >= 0 && (mask_hi(out) & BIT(def32));
2302 }
2303
2304 if (env->log.level & BPF_LOG_LEVEL2) {
2305 verbose(env, "Live regs before insn:\n");
2306 for (i = 0; i < insn_cnt; ++i) {
2307 if (env->insn_aux_data[i].scc)
2308 verbose(env, "%3d ", env->insn_aux_data[i].scc);
2309 else
2310 verbose(env, " ");
2311 verbose(env, "%3d: ", i);
2312 for (j = BPF_REG_0; j < BPF_REG_10; ++j)
2313 if (insn_aux[i].live_regs_before & BIT(j))
2314 verbose(env, "%d", j);
2315 else
2316 verbose(env, ".");
2317 verbose(env, " ");
2318 pos = env->log.end_pos;
2319 bpf_verbose_insn(env, &insns[i]);
2320 insn_pos = env->log.end_pos;
2321 if (insn_aux[i].zext_dst)
2322 verbose(env, "%*c; zext", bpf_vlog_alignment(insn_pos - pos), ' ');
2323 verbose(env, "\n");
2324 if (bpf_is_ldimm64(&insns[i]))
2325 i++;
2326 }
2327 }
2328
2329out:
2330 kvfree(state);
2331 return err;
2332}