Lines Matching +full:single +full:- +full:instance
1 // SPDX-License-Identifier: GPL-2.0-only
20 * A function instance keyed by (callsite, depth).
29 u32 subprog_start; /* cached env->subprog_info[subprog].start */
64 struct bpf_liveness *liveness = env->liveness; in find_instance()
68 hash_for_each_possible(liveness->func_instances, f, hl_node, key) in find_instance()
69 if (f->depth == depth && f->callsite == callsite) in find_instance()
78 u32 depth = caller ? caller->depth + 1 : 0; in call_instance()
79 u32 subprog_start = env->subprog_info[subprog].start; in call_instance()
90 return ERR_PTR(-ENOMEM); in call_instance()
91 f->callsite = lookup_key; in call_instance()
92 f->depth = depth; in call_instance()
93 f->subprog = subprog; in call_instance()
94 f->subprog_start = subprog_start; in call_instance()
95 f->insn_cnt = (env->subprog_info + subprog + 1)->start - subprog_start; in call_instance()
97 hash_add(env->liveness->func_instances, &f->hl_node, hash); in call_instance()
109 subprog_start = env->subprog_info[st->frame[frameno]->subprogno].start; in lookup_instance()
110 callsite = frameno > 0 ? st->frame[frameno]->callsite : subprog_start; in lookup_instance()
112 for (depth = frameno; ; depth--) { in lookup_instance()
122 env->liveness = kvzalloc_obj(*env->liveness, GFP_KERNEL_ACCOUNT); in bpf_stack_liveness_init()
123 if (!env->liveness) in bpf_stack_liveness_init()
124 return -ENOMEM; in bpf_stack_liveness_init()
125 hash_init(env->liveness->func_instances); in bpf_stack_liveness_init()
131 struct func_instance *instance; in bpf_stack_liveness_free() local
135 if (!env->liveness) in bpf_stack_liveness_free()
137 hash_for_each_safe(env->liveness->func_instances, bkt, tmp, instance, hl_node) { in bpf_stack_liveness_free()
138 for (i = 0; i <= instance->depth; i++) in bpf_stack_liveness_free()
139 kvfree(instance->frames[i]); in bpf_stack_liveness_free()
140 kvfree(instance); in bpf_stack_liveness_free()
142 kvfree(env->liveness); in bpf_stack_liveness_free()
147 * to start of the function corresponding to @instance.
149 static int relative_idx(struct func_instance *instance, u32 insn_idx) in relative_idx() argument
151 return insn_idx - instance->subprog_start; in relative_idx()
154 static struct per_frame_masks *get_frame_masks(struct func_instance *instance, in get_frame_masks() argument
157 if (!instance->frames[frame]) in get_frame_masks()
160 return &instance->frames[frame][relative_idx(instance, insn_idx)]; in get_frame_masks()
163 static struct per_frame_masks *alloc_frame_masks(struct func_instance *instance, in alloc_frame_masks() argument
168 if (!instance->frames[frame]) { in alloc_frame_masks()
169 arr = kvzalloc_objs(*arr, instance->insn_cnt, in alloc_frame_masks()
171 instance->frames[frame] = arr; in alloc_frame_masks()
173 return ERR_PTR(-ENOMEM); in alloc_frame_masks()
175 return get_frame_masks(instance, frame, insn_idx); in alloc_frame_masks()
179 static int mark_stack_read(struct func_instance *instance, u32 frame, u32 insn_idx, spis_t mask) in mark_stack_read() argument
183 masks = alloc_frame_masks(instance, frame, insn_idx); in mark_stack_read()
186 masks->may_read = spis_or(masks->may_read, mask); in mark_stack_read()
190 static int mark_stack_write(struct func_instance *instance, u32 frame, u32 insn_idx, spis_t mask) in mark_stack_write() argument
194 masks = alloc_frame_masks(instance, frame, insn_idx); in mark_stack_write()
197 masks->must_write = spis_or(masks->must_write, mask); in mark_stack_write()
203 u8 code = insn->code; in bpf_jmp_offset()
206 return insn->imm; in bpf_jmp_offset()
207 return insn->off; in bpf_jmp_offset()
211 __diag_ignore_all("-Woverride-init", "Allow field initialization overrides for opcode_info_tbl");
214 * Returns an array of instructions succ, with succ->items[0], ...,
215 * succ->items[n-1] with successor instructions, where n=succ->cnt
245 struct bpf_prog *prog = env->prog; in bpf_insn_successors()
246 struct bpf_insn *insn = &prog->insnsi[idx]; in bpf_insn_successors()
251 jt = env->insn_aux_data[idx].jt; in bpf_insn_successors()
255 /* pre-allocated array of size up to 2; reset cnt, as it may have been used already */ in bpf_insn_successors()
256 succ = env->succ; in bpf_insn_successors()
257 succ->cnt = 0; in bpf_insn_successors()
259 opcode_info = &opcode_info_tbl[BPF_CLASS(insn->code) | BPF_OP(insn->code)]; in bpf_insn_successors()
261 if (opcode_info->can_fallthrough) in bpf_insn_successors()
262 succ->items[succ->cnt++] = idx + insn_sz; in bpf_insn_successors()
264 if (opcode_info->can_jump) in bpf_insn_successors()
265 succ->items[succ->cnt++] = idx + bpf_jmp_offset(insn) + 1; in bpf_insn_successors()
274 struct func_instance *instance, u32 frame, u32 insn_idx) in update_insn() argument
283 if (succ->cnt == 0) in update_insn()
287 insn = get_frame_masks(instance, frame, insn_idx); in update_insn()
290 for (s = 0; s < succ->cnt; ++s) { in update_insn()
291 succ_insn = get_frame_masks(instance, frame, succ->items[s]); in update_insn()
292 new_after = spis_or(new_after, succ_insn->live_before); in update_insn()
297 * new_before = (new_after & ~insn->must_write) | insn->may_read in update_insn()
299 new_before = spis_or(spis_and(new_after, spis_not(insn->must_write)), in update_insn()
300 insn->may_read); in update_insn()
301 changed |= !spis_equal(new_before, insn->live_before); in update_insn()
302 insn->live_before = new_before; in update_insn()
306 /* Fixed-point computation of @live_before marks */
307 static void update_instance(struct bpf_verifier_env *env, struct func_instance *instance) in update_instance() argument
310 int *insn_postorder = env->cfg.insn_postorder; in update_instance()
314 instance->must_write_initialized = true; in update_instance()
315 subprog = &env->subprog_info[instance->subprog]; in update_instance()
316 po_start = subprog->postorder_start; in update_instance()
317 po_end = (subprog + 1)->postorder_start; in update_instance()
321 for (frame = 0; frame <= instance->depth; frame++) { in update_instance()
322 if (!instance->frames[frame]) in update_instance()
326 changed |= update_insn(env, instance, frame, insn_postorder[i]); in update_instance()
331 static bool is_live_before(struct func_instance *instance, u32 insn_idx, u32 frameno, u32 half_spi) in is_live_before() argument
335 masks = get_frame_masks(instance, frameno, insn_idx); in is_live_before()
336 return masks && spis_test_bit(masks->live_before, half_spi); in is_live_before()
341 struct live_stack_query *q = &env->liveness->live_stack_query; in bpf_live_stack_query_init()
342 struct func_instance *instance; in bpf_live_stack_query_init() local
346 for (frame = 0; frame <= st->curframe; frame++) { in bpf_live_stack_query_init()
347 instance = lookup_instance(env, st, frame); in bpf_live_stack_query_init()
348 if (IS_ERR_OR_NULL(instance)) in bpf_live_stack_query_init()
349 q->instances[frame] = NULL; in bpf_live_stack_query_init()
351 q->instances[frame] = instance; in bpf_live_stack_query_init()
352 if (frame < st->curframe) in bpf_live_stack_query_init()
353 q->callsites[frame] = st->frame[frame + 1]->callsite; in bpf_live_stack_query_init()
355 q->curframe = st->curframe; in bpf_live_stack_query_init()
356 q->insn_idx = st->insn_idx; in bpf_live_stack_query_init()
363 * Slot is alive if it is read before q->insn_idx in current func instance, in bpf_stack_slot_alive()
364 * or if for some outer func instance: in bpf_stack_slot_alive()
365 * - alive before callsite if callsite calls callback, otherwise in bpf_stack_slot_alive()
366 * - alive after callsite in bpf_stack_slot_alive()
368 struct live_stack_query *q = &env->liveness->live_stack_query; in bpf_stack_slot_alive()
369 struct func_instance *instance, *curframe_instance; in bpf_stack_slot_alive() local
374 curframe_instance = q->instances[q->curframe]; in bpf_stack_slot_alive()
377 cur_delta = (int)curframe_instance->depth - (int)q->curframe; in bpf_stack_slot_alive()
379 if (rel <= curframe_instance->depth) in bpf_stack_slot_alive()
380 alive = is_live_before(curframe_instance, q->insn_idx, rel, half_spi); in bpf_stack_slot_alive()
385 for (i = frameno; i < q->curframe; i++) { in bpf_stack_slot_alive()
386 instance = q->instances[i]; in bpf_stack_slot_alive()
387 if (!instance) in bpf_stack_slot_alive()
389 /* Map actual frameno to frame index within this instance */ in bpf_stack_slot_alive()
390 delta = (int)instance->depth - (int)i; in bpf_stack_slot_alive()
392 if (rel > instance->depth) in bpf_stack_slot_alive()
395 /* Get callsite from verifier state, not from instance callchain */ in bpf_stack_slot_alive()
396 callsite = q->callsites[i]; in bpf_stack_slot_alive()
399 ? is_live_before(instance, callsite, rel, half_spi) in bpf_stack_slot_alive()
400 : is_live_before(instance, callsite + 1, rel, half_spi); in bpf_stack_slot_alive()
410 const char *name = env->subprog_info[subprog].name; in fmt_subprog()
412 snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf), in fmt_subprog()
414 return env->tmp_str_buf; in fmt_subprog()
417 static char *fmt_instance(struct bpf_verifier_env *env, struct func_instance *instance) in fmt_instance() argument
419 snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf), in fmt_instance()
420 "(d%d,cs%d)", instance->depth, instance->callsite); in fmt_instance()
421 return env->tmp_str_buf; in fmt_instance()
426 return -(spi + 1) * BPF_REG_SIZE; in spi_off()
430 * When both halves of an 8-byte SPI are set, print as "-8","-16",...
431 * When only one half is set, print as "-4h","-8h",...
432 * Runs of 3+ consecutive fully-set SPIs are collapsed: "fp0-8..-24"
436 int buf_sz = sizeof(env->tmp_str_buf); in fmt_spis_mask()
437 char *buf = env->tmp_str_buf; in fmt_spis_mask()
451 /* half-spi */ in fmt_spis_mask()
473 buf_sz -= n; in fmt_spis_mask()
475 return env->tmp_str_buf; in fmt_spis_mask()
478 static void print_instance(struct bpf_verifier_env *env, struct func_instance *instance) in print_instance() argument
480 int start = env->subprog_info[instance->subprog].start; in print_instance()
481 struct bpf_insn *insns = env->prog->insnsi; in print_instance()
483 int len = instance->insn_cnt; in print_instance()
488 if (!(env->log.level & BPF_LOG_LEVEL2)) in print_instance()
491 verbose(env, "stack use/def %s ", fmt_subprog(env, instance->subprog)); in print_instance()
492 verbose(env, "%s:\n", fmt_instance(env, instance)); in print_instance()
497 pos = env->log.end_pos; in print_instance()
500 bpf_vlog_reset(&env->log, env->log.end_pos - 1); /* remove \n */ in print_instance()
501 insn_pos = env->log.end_pos; in print_instance()
502 verbose(env, "%*c;", bpf_vlog_alignment(insn_pos - pos), ' '); in print_instance()
503 pos = env->log.end_pos; in print_instance()
505 for (frame = instance->depth; frame >= 0; --frame) { in print_instance()
506 masks = get_frame_masks(instance, frame, insn_idx); in print_instance()
507 if (!masks || spis_is_zero(masks->may_read)) in print_instance()
509 verbose(env, "%s", fmt_spis_mask(env, frame, !has_use, masks->may_read)); in print_instance()
513 bpf_vlog_reset(&env->log, pos); in print_instance()
514 pos = env->log.end_pos; in print_instance()
516 for (frame = instance->depth; frame >= 0; --frame) { in print_instance()
517 masks = get_frame_masks(instance, frame, insn_idx); in print_instance()
518 if (!masks || spis_is_zero(masks->must_write)) in print_instance()
520 verbose(env, "%s", fmt_spis_mask(env, frame, !has_def, masks->must_write)); in print_instance()
524 bpf_vlog_reset(&env->log, has_use ? pos : insn_pos); in print_instance()
535 int dcallsite = (int)a->callsite - b->callsite; in cmp_instances()
536 int ddepth = (int)a->depth - b->depth; in cmp_instances()
548 struct func_instance *instance, **sorted_instances; in print_instances() local
549 struct bpf_liveness *liveness = env->liveness; in print_instances()
553 hash_for_each(liveness->func_instances, bkt, instance, hl_node) in print_instances()
557 return -ENOMEM; in print_instances()
559 hash_for_each(liveness->func_instances, bkt, instance, hl_node) in print_instances()
560 sorted_instances[cnt++] = instance; in print_instances()
569 * Per-register tracking state for compute_subprog_args().
575 * precise {frame=N, off=V} -- known absolute frame index and byte offset
577 * offset-imprecise {frame=N, cnt=0}
578 * | -- known frame identity, unknown offset
579 * fully-imprecise {frame=ARG_IMPRECISE, mask=bitmask}
580 * -- unknown frame identity; .mask is a
585 * - same frame + same offset -> precise
586 * - same frame + different offset -> offset-imprecise
587 * - different frames -> fully-imprecise (bitmask OR)
589 * At memory access sites (LDX/STX/ST), offset-imprecise marks only
590 * the known frame's access mask as SPIS_ALL, while fully-imprecise
601 s8 off_cnt; /* 0 = offset-imprecise, 1-4 = # of precise offsets */
605 ARG_NONE = -1, /* not derived from any argument */
606 ARG_UNVISITED = -2, /* not yet reached by dataflow */
607 ARG_IMPRECISE = -3, /* lost identity; .mask is arg bitmask */
610 /* Track callee stack slots fp-8 through fp-512 (64 slots of 8 bytes each) */
615 return at->frame != ARG_UNVISITED; in arg_is_visited()
620 return at->frame >= 0 || at->frame == ARG_IMPRECISE; in arg_is_fp()
627 switch (at->frame) { in verbose_arg_track()
630 case ARG_IMPRECISE: verbose(env, "IMP%x", at->mask); break; in verbose_arg_track()
633 if (at->off_cnt == 0) { in verbose_arg_track()
634 verbose(env, "fp%d ?", at->frame); in verbose_arg_track()
636 for (i = 0; i < at->off_cnt; i++) { in verbose_arg_track()
639 verbose(env, "fp%d%+d", at->frame, at->off[i]); in verbose_arg_track()
650 if (a->frame != b->frame) in arg_track_eq()
652 if (a->frame == ARG_IMPRECISE) in arg_track_eq()
653 return a->mask == b->mask; in arg_track_eq()
654 if (a->frame < 0) in arg_track_eq()
656 if (a->off_cnt != b->off_cnt) in arg_track_eq()
658 for (i = 0; i < a->off_cnt; i++) in arg_track_eq()
659 if (a->off[i] != b->off[i]) in arg_track_eq()
695 if (k > 0 && result.off[k - 1] == v) in arg_merge_offsets()
718 * contribute a single bit; existing ARG_IMPRECISE values
746 /* Both offset-imprecise: stay imprecise */ in __arg_track_join()
755 * arg + none -> arg in __arg_track_join()
756 * none + arg -> arg in __arg_track_join()
758 * none + none -> none in __arg_track_join()
764 * When joining single fp-N add fake fp+0 to in __arg_track_join()
790 if (!(env->log.level & BPF_LOG_LEVEL2) || !arg_is_visited(&old)) in arg_track_join()
793 verbose(env, "arg JOIN insn %d -> %d ", idx, target); in arg_track_join()
809 * If a single arg is identifiable, preserve it with OFF_IMPRECISE.
818 if (dst->frame >= 0 && (src->frame == ARG_NONE || src->frame == dst->frame)) { in arg_track_alu64()
823 dst->off_cnt = 0; in arg_track_alu64()
826 if (src->frame >= 0 && dst->frame == ARG_NONE) { in arg_track_alu64()
831 dst->off_cnt = 0; in arg_track_alu64()
832 dst->frame = src->frame; in arg_track_alu64()
836 if (dst->frame == ARG_NONE && src->frame == ARG_NONE) in arg_track_alu64()
855 if (at->off_cnt == 0) in arg_padd()
857 for (i = 0; i < at->off_cnt; i++) { in arg_padd()
860 if (arg_add(at->off[i], delta, &new_off)) { in arg_padd()
861 at->off_cnt = 0; in arg_padd()
864 at->off[i] = new_off; in arg_padd()
870 * Returns -1 if out of range or not 8-byte aligned.
871 * Slot 0 = fp-8, slot 1 = fp-16, ..., slot 7 = fp-64, ....
875 if (off >= 0 || off < -(int)(MAX_ARG_SPILL_SLOTS * 8)) in fp_off_to_slot()
876 return -1; in fp_off_to_slot()
878 return -1; in fp_off_to_slot()
879 return (-off) / 8 - 1; in fp_off_to_slot()
888 .mask = (1u << (depth + 1)) - 1, in fill_from_stack()
895 int slot = fp_off_to_slot(insn->off); in fill_from_stack()
906 if (arg_add(at_out[reg].off[i], insn->off, &fp_off)) in fill_from_stack()
918 * For an 8-byte store, single candidate slot gets @val. multi-slots are joined.
919 * sub-8-byte store joins with ARG_NONE.
931 int slot = fp_off_to_slot(insn->off); in spill_to_stack()
947 if (arg_add(at_out[reg].off[i], insn->off, &fp_off)) in spill_to_stack()
961 * [off, off+sz-1] where off is a negative FP-relative offset.
973 int slot_start = -((i + 1) * 8); in clear_overlapping_stack_slots()
995 clear_overlapping_stack_slots(at_stack_out, insn->off, sz, 1); in clear_stack_for_all_offs()
1006 if (arg_add(at_out[reg].off[i], insn->off, &fp_off)) { in clear_stack_for_all_offs()
1021 if (!(env->log.level & BPF_LOG_LEVEL2)) in arg_track_log()
1029 bpf_vlog_reset(&env->log, env->log.end_pos - 1); in arg_track_log()
1033 verbose(env, " -> "); verbose_arg_track(env, &at_out[i]); in arg_track_log()
1041 bpf_vlog_reset(&env->log, env->log.end_pos - 1); in arg_track_log()
1044 verbose(env, "\tfp%+d: ", -(i + 1) * 8); verbose_arg_track(env, &at_stack_in[i]); in arg_track_log()
1045 verbose(env, " -> "); verbose_arg_track(env, &at_stack_out[i]); in arg_track_log()
1053 return regno == BPF_REG_FP || at->frame == depth || in can_be_local_fp()
1054 (at->frame == ARG_IMPRECISE && (at->mask & BIT(depth))); in can_be_local_fp()
1065 struct func_instance *instance, in arg_track_xfer() argument
1068 int depth = instance->depth; in arg_track_xfer()
1069 u8 class = BPF_CLASS(insn->code); in arg_track_xfer()
1070 u8 code = BPF_OP(insn->code); in arg_track_xfer()
1071 struct arg_track *dst = &at_out[insn->dst_reg]; in arg_track_xfer()
1072 struct arg_track *src = &at_out[insn->src_reg]; in arg_track_xfer()
1076 if (class == BPF_ALU64 && BPF_SRC(insn->code) == BPF_K) { in arg_track_xfer()
1079 } else if (dst->frame >= 0) { in arg_track_xfer()
1081 arg_padd(dst, insn->imm); in arg_track_xfer()
1083 arg_padd(dst, -(s64)insn->imm); in arg_track_xfer()
1085 /* Any other 64-bit alu on the pointer makes it imprecise */ in arg_track_xfer()
1086 dst->off_cnt = 0; in arg_track_xfer()
1087 } /* else if dst->frame is imprecise it stays so */ in arg_track_xfer()
1088 } else if (class == BPF_ALU64 && BPF_SRC(insn->code) == BPF_X) { in arg_track_xfer()
1090 if (insn->off == 0) { in arg_track_xfer()
1101 * 32-bit alu destroys the pointer. in arg_track_xfer()
1108 * The fill_from_stack() may return the stale spill — which is an FP-derived arg_track in arg_track_xfer()
1110 * a phantom FP-derived identity that doesn't correspond to what's actually in the slot. in arg_track_xfer()
1114 * So the effect is over-reporting stack liveness — marking slots as live that aren't in arg_track_xfer()
1120 * _any_ FP-derived pointer into it (either their own or parent's FP). in arg_track_xfer()
1125 u32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code)); in arg_track_xfer()
1126 bool src_is_local_fp = can_be_local_fp(depth, insn->src_reg, src); in arg_track_xfer()
1129 * Reload from callee stack: if src is current-frame FP-derived in arg_track_xfer()
1130 * and the load is an 8-byte BPF_MEM, try to restore the spill in arg_track_xfer()
1134 if (src_is_local_fp && BPF_MODE(insn->code) == BPF_MEM && sz == 8) { in arg_track_xfer()
1135 *dst = fill_from_stack(insn, at_out, insn->src_reg, at_stack_out, depth); in arg_track_xfer()
1136 } else if (src->frame >= 0 && src->frame < depth && in arg_track_xfer()
1137 BPF_MODE(insn->code) == BPF_MEM && sz == 8) { in arg_track_xfer()
1139 env->callsite_at_stack[callsites[src->frame]]; in arg_track_xfer()
1141 *dst = fill_from_stack(insn, at_out, insn->src_reg, in arg_track_xfer()
1142 parent_stack, src->frame); in arg_track_xfer()
1143 } else if (src->frame == ARG_IMPRECISE && in arg_track_xfer()
1144 !(src->mask & BIT(depth)) && src->mask && in arg_track_xfer()
1145 BPF_MODE(insn->code) == BPF_MEM && sz == 8) { in arg_track_xfer()
1147 * Imprecise src with only parent-frame bits: in arg_track_xfer()
1154 } else if (class == BPF_LD && BPF_MODE(insn->code) == BPF_IMM) { in arg_track_xfer()
1157 u32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code)); in arg_track_xfer()
1160 /* Track spills to current-frame FP-derived callee stack */ in arg_track_xfer()
1161 dst_is_local_fp = can_be_local_fp(depth, insn->dst_reg, dst); in arg_track_xfer()
1162 if (dst_is_local_fp && BPF_MODE(insn->code) == BPF_MEM) in arg_track_xfer()
1163 spill_to_stack(insn, at_out, insn->dst_reg, in arg_track_xfer()
1166 if (BPF_MODE(insn->code) == BPF_ATOMIC) { in arg_track_xfer()
1167 if (dst_is_local_fp && insn->imm != BPF_LOAD_ACQ) in arg_track_xfer()
1168 clear_stack_for_all_offs(insn, at_out, insn->dst_reg, in arg_track_xfer()
1171 if (insn->imm == BPF_CMPXCHG) in arg_track_xfer()
1173 else if (insn->imm == BPF_LOAD_ACQ) in arg_track_xfer()
1175 else if (insn->imm & BPF_FETCH) in arg_track_xfer()
1178 } else if (class == BPF_ST && BPF_MODE(insn->code) == BPF_MEM) { in arg_track_xfer()
1179 u32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code)); in arg_track_xfer()
1180 bool dst_is_local_fp = can_be_local_fp(depth, insn->dst_reg, dst); in arg_track_xfer()
1182 /* BPF_ST to FP-derived dst: clear overlapping stack slots */ in arg_track_xfer()
1184 clear_stack_for_all_offs(insn, at_out, insn->dst_reg, in arg_track_xfer()
1197 static int record_stack_access_off(struct func_instance *instance, s64 fp_off, in record_stack_access_off() argument
1212 slot_hi = (-fp_off - 1) / STACK_SLOT_SZ; in record_stack_access_off()
1215 return mark_stack_read(instance, frame, insn_idx, mask); in record_stack_access_off()
1219 slot_hi = (-fp_off - 1) / STACK_SLOT_SZ; in record_stack_access_off()
1220 slot_lo = max_t(s32, (-fp_off - access_bytes) / STACK_SLOT_SZ, 0); in record_stack_access_off()
1223 return mark_stack_read(instance, frame, insn_idx, mask); in record_stack_access_off()
1226 access_bytes = -access_bytes; in record_stack_access_off()
1227 slot_hi = (-fp_off) / STACK_SLOT_SZ - 1; in record_stack_access_off()
1228 slot_lo = max_t(s32, (-fp_off - access_bytes + STACK_SLOT_SZ - 1) / STACK_SLOT_SZ, 0); in record_stack_access_off()
1232 return mark_stack_write(instance, frame, insn_idx, mask); in record_stack_access_off()
1239 * 'arg' is FP-derived argument to helper/kfunc or load/store that
1242 static int record_stack_access(struct func_instance *instance, in record_stack_access() argument
1250 if (arg->off_cnt == 0) { in record_stack_access()
1252 return mark_stack_read(instance, frame, insn_idx, SPIS_ALL); in record_stack_access()
1255 if (access_bytes != S64_MIN && access_bytes < 0 && arg->off_cnt != 1) in record_stack_access()
1256 /* multi-offset write cannot set stack_def */ in record_stack_access()
1259 for (i = 0; i < arg->off_cnt; i++) { in record_stack_access()
1260 err = record_stack_access_off(instance, arg->off[i], access_bytes, frame, insn_idx); in record_stack_access()
1271 static int record_imprecise(struct func_instance *instance, u32 mask, u32 insn_idx) in record_imprecise() argument
1273 int depth = instance->depth; in record_imprecise()
1280 err = mark_stack_read(instance, f, insn_idx, SPIS_ALL); in record_imprecise()
1290 struct func_instance *instance, in record_load_store_access() argument
1293 struct bpf_insn *insn = &env->prog->insnsi[insn_idx]; in record_load_store_access()
1294 int depth = instance->depth; in record_load_store_access()
1295 s32 sz = bpf_size_to_bytes(BPF_SIZE(insn->code)); in record_load_store_access()
1296 u8 class = BPF_CLASS(insn->code); in record_load_store_access()
1302 ptr = &at[insn->src_reg]; in record_load_store_access()
1305 if (BPF_MODE(insn->code) == BPF_ATOMIC) { in record_load_store_access()
1306 if (insn->imm == BPF_STORE_REL) in record_load_store_access()
1307 sz = -sz; in record_load_store_access()
1308 if (insn->imm == BPF_LOAD_ACQ) in record_load_store_access()
1309 ptr = &at[insn->src_reg]; in record_load_store_access()
1311 ptr = &at[insn->dst_reg]; in record_load_store_access()
1313 ptr = &at[insn->dst_reg]; in record_load_store_access()
1314 sz = -sz; in record_load_store_access()
1318 ptr = &at[insn->dst_reg]; in record_load_store_access()
1319 sz = -sz; in record_load_store_access()
1325 /* Resolve offsets: fold insn->off into arg_track */ in record_load_store_access()
1326 if (ptr->off_cnt > 0) { in record_load_store_access()
1327 resolved.off_cnt = ptr->off_cnt; in record_load_store_access()
1328 resolved.frame = ptr->frame; in record_load_store_access()
1329 for (oi = 0; oi < ptr->off_cnt; oi++) { in record_load_store_access()
1330 if (arg_add(ptr->off[oi], insn->off, &resolved.off[oi])) { in record_load_store_access()
1338 if (ptr->frame >= 0 && ptr->frame <= depth) in record_load_store_access()
1339 return record_stack_access(instance, ptr, sz, ptr->frame, insn_idx); in record_load_store_access()
1340 if (ptr->frame == ARG_IMPRECISE) in record_load_store_access()
1341 return record_imprecise(instance, ptr->mask, insn_idx); in record_load_store_access()
1348 struct func_instance *instance, in record_call_access() argument
1352 struct bpf_insn *insn = &env->prog->insnsi[insn_idx]; in record_call_access()
1353 int depth = instance->depth; in record_call_access()
1371 bytes = bpf_helper_stack_access_bytes(env, insn, r - 1, insn_idx); in record_call_access()
1373 bytes = bpf_kfunc_stack_access_bytes(env, insn, r - 1, insn_idx); in record_call_access()
1376 err = mark_stack_read(instance, f, insn_idx, SPIS_ALL); in record_call_access()
1386 err = record_stack_access(instance, &at[r], bytes, frame, insn_idx); in record_call_access()
1388 err = record_imprecise(instance, at[r].mask, insn_idx); in record_call_access()
1403 struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx]; in find_callback_subprog()
1404 int cb_reg = -1; in find_callback_subprog()
1406 *caller_reg = -1; in find_callback_subprog()
1407 *callee_reg = -1; in find_callback_subprog()
1410 return -1; in find_callback_subprog()
1411 switch (insn->imm) { in find_callback_subprog()
1413 /* bpf_loop(nr, cb, ctx, flags): cb=R2, R3->cb R2 */ in find_callback_subprog()
1419 /* for_each_map_elem(map, cb, ctx, flags): cb=R2, R3->cb R4 */ in find_callback_subprog()
1425 /* find_vma(task, addr, cb, ctx, flags): cb=R3, R4->cb R3 */ in find_callback_subprog()
1431 /* user_ringbuf_drain(map, cb, ctx, flags): cb=R2, R3->cb R2 */ in find_callback_subprog()
1437 return -1; in find_callback_subprog()
1440 if (!(aux->const_reg_subprog_mask & BIT(cb_reg))) in find_callback_subprog()
1441 return -2; in find_callback_subprog()
1443 return aux->const_reg_vals[cb_reg]; in find_callback_subprog()
1446 /* Per-subprog intermediate state kept alive across analysis phases */
1457 struct bpf_insn *insns = env->prog->insnsi; in print_subprog_arg_access()
1458 int start = env->subprog_info[subprog].start; in print_subprog_arg_access()
1459 int len = info->len; in print_subprog_arg_access()
1462 if (!(env->log.level & BPF_LOG_LEVEL2)) in print_subprog_arg_access()
1478 arg_is_visited(&info->at_in[i][0])) { in print_subprog_arg_access()
1479 for (r = 0; r < MAX_BPF_REG - 1; r++) in print_subprog_arg_access()
1480 if (arg_is_fp(&info->at_in[i][r])) in print_subprog_arg_access()
1495 bpf_vlog_reset(&env->log, env->log.end_pos - 1); in print_subprog_arg_access()
1498 if (is_ldx_stx_call && info->at_in && in print_subprog_arg_access()
1499 arg_is_visited(&info->at_in[i][0])) { in print_subprog_arg_access()
1500 for (r = 0; r < MAX_BPF_REG - 1; r++) { in print_subprog_arg_access()
1501 if (!arg_is_fp(&info->at_in[i][r])) in print_subprog_arg_access()
1504 verbose_arg_track(env, &info->at_in[i][r]); in print_subprog_arg_access()
1512 verbose(env, " fp%+d=", -(r + 1) * 8); in print_subprog_arg_access()
1524 * Compute arg tracking dataflow for a single subprog.
1525 * Runs forward fixed-point with arg_track_xfer(), then records
1526 * memory accesses in a single linear pass over converged state.
1528 * @callee_entry: pre-populated entry state for R1-R5
1535 struct func_instance *instance, in compute_subprog_args() argument
1538 int subprog = instance->subprog; in compute_subprog_args()
1539 struct bpf_insn *insns = env->prog->insnsi; in compute_subprog_args()
1540 int depth = instance->depth; in compute_subprog_args()
1541 int start = env->subprog_info[subprog].start; in compute_subprog_args()
1542 int po_start = env->subprog_info[subprog].postorder_start; in compute_subprog_args()
1543 int end = env->subprog_info[subprog + 1].start; in compute_subprog_args()
1544 int po_end = env->subprog_info[subprog + 1].postorder_start; in compute_subprog_args()
1545 int len = end - start; in compute_subprog_args()
1553 int i, p, r, err = -ENOMEM; in compute_subprog_args()
1580 /* R1-R5: from caller or ARG_NONE for main */ in compute_subprog_args()
1590 if (env->log.level & BPF_LOG_LEVEL2) in compute_subprog_args()
1593 /* Forward fixed-point iteration in reverse post order */ in compute_subprog_args()
1596 for (p = po_end - 1; p >= po_start; p--) { in compute_subprog_args()
1597 int idx = env->cfg.insn_postorder[p]; in compute_subprog_args()
1598 int i = idx - start; in compute_subprog_args()
1608 arg_track_xfer(env, insn, idx, at_out, at_stack_out, instance, callsites); in compute_subprog_args()
1613 for (int s = 0; s < succ->cnt; s++) { in compute_subprog_args()
1614 int target = succ->items[s]; in compute_subprog_args()
1620 ti = target - start; in compute_subprog_args()
1627 changed |= arg_track_join(env, idx, target, -r - 1, in compute_subprog_args()
1635 for (p = po_end - 1; p >= po_start; p--) { in compute_subprog_args()
1636 int idx = env->cfg.insn_postorder[p]; in compute_subprog_args()
1637 int i = idx - start; in compute_subprog_args()
1640 err = record_load_store_access(env, instance, at_in[i], idx); in compute_subprog_args()
1644 if (insn->code == (BPF_JMP | BPF_CALL)) { in compute_subprog_args()
1645 err = record_call_access(env, instance, at_in[i], idx); in compute_subprog_args()
1651 kvfree(env->callsite_at_stack[idx]); in compute_subprog_args()
1652 env->callsite_at_stack[idx] = in compute_subprog_args()
1653 kvmalloc_objs(*env->callsite_at_stack[idx], in compute_subprog_args()
1655 if (!env->callsite_at_stack[idx]) { in compute_subprog_args()
1656 err = -ENOMEM; in compute_subprog_args()
1659 memcpy(env->callsite_at_stack[idx], in compute_subprog_args()
1664 info->at_in = at_in; in compute_subprog_args()
1666 info->len = len; in compute_subprog_args()
1677 /* Return true if any of R1-R5 is derived from a frame pointer. */
1687 * Merge a freshly analyzed instance into the original.
1696 for (f = 0; f <= dst->depth; f++) { in merge_instances()
1697 if (!src->frames[f]) { in merge_instances()
1699 if (dst->frames[f]) in merge_instances()
1700 for (i = 0; i < dst->insn_cnt; i++) in merge_instances()
1701 dst->frames[f][i].must_write = SPIS_ZERO; in merge_instances()
1704 if (!dst->frames[f]) { in merge_instances()
1706 dst->frames[f] = src->frames[f]; in merge_instances()
1707 src->frames[f] = NULL; in merge_instances()
1708 for (i = 0; i < dst->insn_cnt; i++) in merge_instances()
1709 dst->frames[f][i].must_write = SPIS_ZERO; in merge_instances()
1712 for (i = 0; i < dst->insn_cnt; i++) { in merge_instances()
1713 dst->frames[f][i].may_read = in merge_instances()
1714 spis_or(dst->frames[f][i].may_read, in merge_instances()
1715 src->frames[f][i].may_read); in merge_instances()
1716 dst->frames[f][i].must_write = in merge_instances()
1717 spis_and(dst->frames[f][i].must_write, in merge_instances()
1718 src->frames[f][i].must_write); in merge_instances()
1729 return ERR_PTR(-ENOMEM); in fresh_instance()
1730 f->callsite = src->callsite; in fresh_instance()
1731 f->depth = src->depth; in fresh_instance()
1732 f->subprog = src->subprog; in fresh_instance()
1733 f->subprog_start = src->subprog_start; in fresh_instance()
1734 f->insn_cnt = src->insn_cnt; in fresh_instance()
1738 static void free_instance(struct func_instance *instance) in free_instance() argument
1742 for (i = 0; i <= instance->depth; i++) in free_instance()
1743 kvfree(instance->frames[i]); in free_instance()
1744 kvfree(instance); in free_instance()
1752 * depends on the entry args and frame depth. Consider: A->C->D and B->C->D
1759 struct func_instance *instance, in analyze_subprog() argument
1762 int subprog = instance->subprog; in analyze_subprog()
1763 int depth = instance->depth; in analyze_subprog()
1764 struct bpf_insn *insns = env->prog->insnsi; in analyze_subprog()
1765 int start = env->subprog_info[subprog].start; in analyze_subprog()
1766 int po_start = env->subprog_info[subprog].postorder_start; in analyze_subprog()
1767 int po_end = env->subprog_info[subprog + 1].postorder_start; in analyze_subprog()
1771 if (++env->liveness->subprog_calls > 10000) { in analyze_subprog()
1773 env->liveness->subprog_calls); in analyze_subprog()
1774 return -E2BIG; in analyze_subprog()
1782 * When an instance is reused (must_write_initialized == true), in analyze_subprog()
1783 * record into a fresh instance and merge afterward. This avoids in analyze_subprog()
1786 if (instance->must_write_initialized) { in analyze_subprog()
1787 struct func_instance *fresh = fresh_instance(instance); in analyze_subprog()
1791 prev_instance = instance; in analyze_subprog()
1792 instance = fresh; in analyze_subprog()
1799 err = compute_subprog_args(env, &info[subprog], entry_args, instance, callsites); in analyze_subprog()
1805 int idx = env->cfg.insn_postorder[p]; in analyze_subprog()
1813 j = idx - start; /* relative index within this subprog */ in analyze_subprog()
1816 target = idx + insn->imm + 1; in analyze_subprog()
1821 /* Build entry args: R1-R5 from at_in at call site */ in analyze_subprog()
1826 if (callee == -2) { in analyze_subprog()
1834 err = mark_stack_read(instance, f, idx, SPIS_ALL); in analyze_subprog()
1853 if (depth == MAX_CALL_FRAMES - 1) { in analyze_subprog()
1854 err = -EINVAL; in analyze_subprog()
1858 callee_instance = call_instance(env, instance, idx, callee); in analyze_subprog()
1870 u32 callee_start = callee_instance->subprog_start; in analyze_subprog()
1873 for (int f = 0; f < callee_instance->depth; f++) { in analyze_subprog()
1877 err = mark_stack_read(instance, f, idx, entry->live_before); in analyze_subprog()
1885 merge_instances(prev_instance, instance); in analyze_subprog()
1886 free_instance(instance); in analyze_subprog()
1887 instance = prev_instance; in analyze_subprog()
1889 update_instance(env, instance); in analyze_subprog()
1894 free_instance(instance); in analyze_subprog()
1901 int insn_cnt = env->prog->len; in bpf_compute_subprog_arg_access()
1902 struct func_instance *instance; in bpf_compute_subprog_arg_access() local
1906 info = kvzalloc_objs(*info, env->subprog_cnt, GFP_KERNEL_ACCOUNT); in bpf_compute_subprog_arg_access()
1908 return -ENOMEM; in bpf_compute_subprog_arg_access()
1910 env->callsite_at_stack = kvzalloc_objs(*env->callsite_at_stack, insn_cnt, in bpf_compute_subprog_arg_access()
1912 if (!env->callsite_at_stack) { in bpf_compute_subprog_arg_access()
1914 return -ENOMEM; in bpf_compute_subprog_arg_access()
1921 * to naturally reach callees that receive FP-derived args. in bpf_compute_subprog_arg_access()
1923 * Subprogs and callbacks that don't receive FP-derived arguments in bpf_compute_subprog_arg_access()
1927 for (k = env->subprog_cnt - 1; k >= 0; k--) { in bpf_compute_subprog_arg_access()
1928 int sub = env->subprog_topo_order[k]; in bpf_compute_subprog_arg_access()
1932 instance = call_instance(env, NULL, 0, sub); in bpf_compute_subprog_arg_access()
1933 if (IS_ERR(instance)) { in bpf_compute_subprog_arg_access()
1934 err = PTR_ERR(instance); in bpf_compute_subprog_arg_access()
1937 err = analyze_subprog(env, NULL, info, instance, callsites); in bpf_compute_subprog_arg_access()
1942 if (env->log.level & BPF_LOG_LEVEL2) in bpf_compute_subprog_arg_access()
1947 kvfree(env->callsite_at_stack[k]); in bpf_compute_subprog_arg_access()
1948 kvfree(env->callsite_at_stack); in bpf_compute_subprog_arg_access()
1949 env->callsite_at_stack = NULL; in bpf_compute_subprog_arg_access()
1950 for (k = 0; k < env->subprog_cnt; k++) in bpf_compute_subprog_arg_access()
1965 #define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1)
1967 /* Compute info->{use,def} fields for the instruction */
1973 u8 class = BPF_CLASS(insn->code); in compute_insn_live_regs()
1974 u8 code = BPF_OP(insn->code); in compute_insn_live_regs()
1975 u8 mode = BPF_MODE(insn->code); in compute_insn_live_regs()
1976 u16 src = BIT(insn->src_reg); in compute_insn_live_regs()
1977 u16 dst = BIT(insn->dst_reg); in compute_insn_live_regs()
1986 if (BPF_SIZE(insn->code) == BPF_DW) { in compute_insn_live_regs()
2021 switch (insn->imm) { in compute_insn_live_regs()
2036 if (insn->imm & BPF_FETCH) in compute_insn_live_regs()
2053 if (BPF_SRC(insn->code) == BPF_K) in compute_insn_live_regs()
2060 if (BPF_SRC(insn->code) == BPF_K) in compute_insn_live_regs()
2071 if (BPF_SRC(insn->code) == BPF_X) in compute_insn_live_regs()
2092 if (BPF_SRC(insn->code) == BPF_K) in compute_insn_live_regs()
2100 info->def = def; in compute_insn_live_regs()
2101 info->use = use; in compute_insn_live_regs()
2104 /* Compute may-live registers after each instruction in the program.
2109 * Store result in env->insn_aux_data[i].live_regs.
2113 struct bpf_insn_aux_data *insn_aux = env->insn_aux_data; in bpf_compute_live_registers()
2114 struct bpf_insn *insns = env->prog->insnsi; in bpf_compute_live_registers()
2116 int insn_cnt = env->prog->len; in bpf_compute_live_registers()
2121 * - define the following: in bpf_compute_live_registers()
2122 * - I.use : a set of all registers read by instruction I; in bpf_compute_live_registers()
2123 * - I.def : a set of all registers written by instruction I; in bpf_compute_live_registers()
2124 * - I.in : a set of all registers that may be alive before I execution; in bpf_compute_live_registers()
2125 * - I.out : a set of all registers that may be alive after I execution; in bpf_compute_live_registers()
2126 * - insn_successors(I): a set of instructions S that might immediately in bpf_compute_live_registers()
2128 * - associate separate empty sets 'I.in' and 'I.out' with each instruction; in bpf_compute_live_registers()
2129 * - visit each instruction in a postorder and update in bpf_compute_live_registers()
2136 * - repeat the computation while {in,out} fields changes for in bpf_compute_live_registers()
2141 err = -ENOMEM; in bpf_compute_live_registers()
2148 /* Forward pass: resolve stack access through FP-derived pointers */ in bpf_compute_live_registers()
2156 for (i = 0; i < env->cfg.cur_postorder; ++i) { in bpf_compute_live_registers()
2157 int insn_idx = env->cfg.insn_postorder[i]; in bpf_compute_live_registers()
2164 for (int s = 0; s < succ->cnt; ++s) in bpf_compute_live_registers()
2165 new_out |= state[succ->items[s]].in; in bpf_compute_live_registers()
2166 new_in = (new_out & ~live->def) | live->use; in bpf_compute_live_registers()
2167 if (new_out != live->out || new_in != live->in) { in bpf_compute_live_registers()
2168 live->in = new_in; in bpf_compute_live_registers()
2169 live->out = new_out; in bpf_compute_live_registers()
2178 if (env->log.level & BPF_LOG_LEVEL2) { in bpf_compute_live_registers()
2181 if (env->insn_aux_data[i].scc) in bpf_compute_live_registers()
2182 verbose(env, "%3d ", env->insn_aux_data[i].scc); in bpf_compute_live_registers()