// SPDX-License-Identifier: GPL-2.0-only/* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */ #include <linux/bpf_verifier.h>#include <linux/btf.h>#include <linux/hashtable.h>#include <linux/jhash.h>#include <linux/slab.h>#include <linux/sort.h> #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) struct per_frame_masks { spis_t may_read; /* stack slots that may be read by this instruction */ spis_t must_write; /* stack slots written by this instruction */ spis_t live_before; /* stack slots that may be read by this insn and its successors */}; /* * A function instance keyed by (callsite, depth). * Encapsulates read and write marks for each instruction in the function. * Marks are tracked for each frame up to @depth. */struct func_instance { struct hlist_node hl_node; u32 callsite; /* call insn that invoked this subprog (subprog_start for depth 0) */ u32 depth; /* call depth (0 = entry subprog) */ u32 subprog; /* subprog index */ u32 subprog_start; /* cached env->subprog_info[subprog].start */ u32 insn_cnt; /* cached number of insns in the function */ /* Per frame, per instruction masks, frames allocated lazily. */ struct per_frame_masks *frames[MAX_CALL_FRAMES]; bool must_write_initialized;}; struct live_stack_query { struct func_instance *instances[MAX_CALL_FRAMES]; /* valid in range [0..curframe] */ u32 callsites[MAX_CALL_FRAMES]; /* callsite[i] = insn calling frame i+1 */ u32 curframe; u32 insn_idx;}; struct bpf_liveness { DECLARE_HASHTABLE(func_instances, 8); /* maps (depth, callsite) to func_instance */ struct live_stack_query live_stack_query; /* cache to avoid repetitive ht lookups */ u32 subprog_calls; /* analyze_subprog() invocations */}; /* * Hash/compare key for func_instance: (depth, callsite). * For depth == 0 (entry subprog), @callsite is the subprog start insn. * For depth > 0, @callsite is the call instruction index that invoked the subprog. */static u32 instance_hash(u32 callsite, u32 depth){ u32 key[2] = { depth, callsite }; return jhash2(key, 2, 0);} static struct func_instance *find_instance(struct bpf_verifier_env *env, u32 callsite, u32 depth){ struct bpf_liveness *liveness = env->liveness; struct func_instance *f; u32 key = instance_hash(callsite, depth); hash_for_each_possible(liveness->func_instances, f, hl_node, key) if (f->depth == depth && f->callsite == callsite) return f; return NULL;} static struct func_instance *call_instance(struct bpf_verifier_env *env, struct func_instance *caller, u32 callsite, int subprog){ u32 depth = caller ? caller->depth + 1 : 0; u32 subprog_start = env->subprog_info[subprog].start; u32 lookup_key = depth > 0 ? callsite : subprog_start; struct func_instance *f; u32 hash; f = find_instance(env, lookup_key, depth); if (f) return f; f = kvzalloc_obj(*f, GFP_KERNEL_ACCOUNT); if (!f) return ERR_PTR(-ENOMEM); f->callsite = lookup_key; f->depth = depth; f->subprog = subprog; f->subprog_start = subprog_start; f->insn_cnt = (env->subprog_info + subprog + 1)->start - subprog_start; hash = instance_hash(lookup_key, depth); hash_add(env->liveness->func_instances, &f->hl_node, hash); return f;} static struct func_instance *lookup_instance(struct bpf_verifier_env *env, struct bpf_verifier_state *st, u32 frameno){ u32 callsite, subprog_start; struct func_instance *f; u32 key, depth; subprog_start = env->subprog_info[st->frame[frameno]->subprogno].start; callsite = frameno > 0 ? st->frame[frameno]->callsite : subprog_start; for (depth = frameno; ; depth--) { key = depth > 0 ? callsite : subprog_start; f = find_instance(env, key, depth); if (f || depth == 0) return f; }} int bpf_stack_liveness_init(struct bpf_verifier_env *env){ env->liveness = kvzalloc_obj(*env->liveness, GFP_KERNEL_ACCOUNT); if (!env->liveness) return -ENOMEM; hash_init(env->liveness->func_instances); return 0;} void bpf_stack_liveness_free(struct bpf_verifier_env *env){ struct func_instance *instance; struct hlist_node *tmp; int bkt, i; if (!env->liveness) return; hash_for_each_safe(env->liveness->func_instances, bkt, tmp, instance, hl_node) { for (i = 0; i <= instance->depth; i++) kvfree(instance->frames[i]); kvfree(instance); } kvfree(env->liveness);} /* * Convert absolute instruction index @insn_idx to an index relative * to start of the function corresponding to @instance. */static int relative_idx(struct func_instance *instance, u32 insn_idx){ return insn_idx - instance->subprog_start;} static struct per_frame_masks *get_frame_masks(struct func_instance *instance, u32 frame, u32 insn_idx){ if (!instance->frames[frame]) return NULL; return &instance->frames[frame][relative_idx(instance, insn_idx)];} static struct per_frame_masks *alloc_frame_masks(struct func_instance *instance, u32 frame, u32 insn_idx){ struct per_frame_masks *arr; if (!instance->frames[frame]) { arr = kvzalloc_objs(*arr, instance->insn_cnt, GFP_KERNEL_ACCOUNT); instance->frames[frame] = arr; if (!arr) return ERR_PTR(-ENOMEM); } return get_frame_masks(instance, frame, insn_idx);} /* Accumulate may_read masks for @frame at @insn_idx */static int mark_stack_read(struct func_instance *instance, u32 frame, u32 insn_idx, spis_t mask){ struct per_frame_masks *masks; masks = alloc_frame_masks(instance, frame, insn_idx); if (IS_ERR(masks)) return PTR_ERR(masks); masks->may_read = spis_or(masks->may_read, mask); return 0;} static int mark_stack_write(struct func_instance *instance, u32 frame, u32 insn_idx, spis_t mask){ struct per_frame_masks *masks; masks = alloc_frame_masks(instance, frame, insn_idx); if (IS_ERR(masks)) return PTR_ERR(masks); masks->must_write = spis_or(masks->must_write, mask); return 0;} int bpf_jmp_offset(struct bpf_insn *insn){ u8 code = insn->code; if (code == (BPF_JMP32 | BPF_JA)) return insn->imm; return insn->off;} __diag_push();__diag_ignore_all("-Woverride-init", "Allow field initialization overrides for opcode_info_tbl"); /* * Returns an array of instructions succ, with succ->items[0], ..., * succ->items[n-1] with successor instructions, where n=succ->cnt */inline struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx){ static const struct opcode_info { bool can_jump; bool can_fallthrough; } opcode_info_tbl[256] = { [0 ... 255] = {.can_jump = false, .can_fallthrough = true}, #define _J(code, ...) \ [BPF_JMP | code] = __VA_ARGS__, \ [BPF_JMP32 | code] = __VA_ARGS__ _J(BPF_EXIT, {.can_jump = false, .can_fallthrough = false}), _J(BPF_JA, {.can_jump = true, .can_fallthrough = false}), _J(BPF_JEQ, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JNE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JLT, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JLE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JGT, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JGE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSGT, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSGE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSLT, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSLE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JCOND, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSET, {.can_jump = true, .can_fallthrough = true}), #undef _J }; struct bpf_prog *prog = env->prog; struct bpf_insn *insn = &prog->insnsi[idx]; const struct opcode_info *opcode_info; struct bpf_iarray *succ, *jt; int insn_sz; jt = env->insn_aux_data[idx].jt; if (unlikely(jt)) return jt; /* pre-allocated array of size up to 2; reset cnt, as it may have been used already */ succ = env->succ; succ->cnt = 0; opcode_info = &opcode_info_tbl[BPF_CLASS(insn->code) | BPF_OP(insn->code)]; insn_sz = bpf_is_ldimm64(insn) ? 2 : 1; if (opcode_info->can_fallthrough) succ->items[succ->cnt++] = idx + insn_sz; if (opcode_info->can_jump) succ->items[succ->cnt++] = idx + bpf_jmp_offset(insn) + 1; return succ;} __diag_pop(); static inline bool update_insn(struct bpf_verifier_env *env, struct func_instance *instance, u32 frame, u32 insn_idx){ spis_t new_before, new_after; struct per_frame_masks *insn, *succ_insn; struct bpf_iarray *succ; u32 s; bool changed; succ = bpf_insn_successors(env, insn_idx); if (succ->cnt == 0) return false; changed = false; insn = get_frame_masks(instance, frame, insn_idx); new_before = SPIS_ZERO; new_after = SPIS_ZERO; for (s = 0; s < succ->cnt; ++s) { succ_insn = get_frame_masks(instance, frame, succ->items[s]); new_after = spis_or(new_after, succ_insn->live_before); } /* * New "live_before" is a union of all "live_before" of successors * minus slots written by instruction plus slots read by instruction. * new_before = (new_after & ~insn->must_write) | insn->may_read */ new_before = spis_or(spis_and(new_after, spis_not(insn->must_write)), insn->may_read); changed |= !spis_equal(new_before, insn->live_before); insn->live_before = new_before; return changed;} /* Fixed-point computation of @live_before marks */static void update_instance(struct bpf_verifier_env *env, struct func_instance *instance){ u32 i, frame, po_start, po_end; int *insn_postorder = env->cfg.insn_postorder; struct bpf_subprog_info *subprog; bool changed; instance->must_write_initialized = true; subprog = &env->subprog_info[instance->subprog]; po_start = subprog->postorder_start; po_end = (subprog + 1)->postorder_start; /* repeat until fixed point is reached */ do { changed = false; for (frame = 0; frame <= instance->depth; frame++) { if (!instance->frames[frame]) continue; for (i = po_start; i < po_end; i++) changed |= update_insn(env, instance, frame, insn_postorder[i]); } } while (changed);} static bool is_live_before(struct func_instance *instance, u32 insn_idx, u32 frameno, u32 half_spi){ struct per_frame_masks *masks; masks = get_frame_masks(instance, frameno, insn_idx); return masks && spis_test_bit(masks->live_before, half_spi);} int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st){ struct live_stack_query *q = &env->liveness->live_stack_query; struct func_instance *instance; u32 frame; memset(q, 0, sizeof(*q)); for (frame = 0; frame <= st->curframe; frame++) { instance = lookup_instance(env, st, frame); if (IS_ERR_OR_NULL(instance)) q->instances[frame] = NULL; else q->instances[frame] = instance; if (frame < st->curframe) q->callsites[frame] = st->frame[frame + 1]->callsite; } q->curframe = st->curframe; q->insn_idx = st->insn_idx; return 0;} bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 half_spi){ /* * Slot is alive if it is read before q->insn_idx in current func instance, * or if for some outer func instance: * - alive before callsite if callsite calls callback, otherwise * - alive after callsite */ struct live_stack_query *q = &env->liveness->live_stack_query; struct func_instance *instance, *curframe_instance; u32 i, callsite, rel; int cur_delta, delta; bool alive = false; curframe_instance = q->instances[q->curframe]; if (!curframe_instance) return true; cur_delta = (int)curframe_instance->depth - (int)q->curframe; rel = frameno + cur_delta; if (rel <= curframe_instance->depth) alive = is_live_before(curframe_instance, q->insn_idx, rel, half_spi); if (alive) return true; for (i = frameno; i < q->curframe; i++) { instance = q->instances[i]; if (!instance) return true; /* Map actual frameno to frame index within this instance */ delta = (int)instance->depth - (int)i; rel = frameno + delta; if (rel > instance->depth) return true; /* Get callsite from verifier state, not from instance callchain */ callsite = q->callsites[i]; alive = bpf_calls_callback(env, callsite) ? is_live_before(instance, callsite, rel, half_spi) : is_live_before(instance, callsite + 1, rel, half_spi); if (alive) return true; } return false;} static char *fmt_subprog(struct bpf_verifier_env *env, int subprog){ const char *name = env->subprog_info[subprog].name; snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf), "subprog#%d%s%s", subprog, name ? " " : "", name ? name : ""); return env->tmp_str_buf;} static char *fmt_instance(struct bpf_verifier_env *env, struct func_instance *instance){ snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf), "(d%d,cs%d)", instance->depth, instance->callsite); return env->tmp_str_buf;} static int spi_off(int spi){ return -(spi + 1) * BPF_REG_SIZE;} /* * When both halves of an 8-byte SPI are set, print as "-8","-16",... * When only one half is set, print as "-4h","-8h",... * Runs of 3+ consecutive fully-set SPIs are collapsed: "fp0-8..-24" */static char *fmt_spis_mask(struct bpf_verifier_env *env, int frame, bool first, spis_t spis){ int buf_sz = sizeof(env->tmp_str_buf); char *buf = env->tmp_str_buf; int spi, n, run_start; buf[0] = '\0'; for (spi = 0; spi < STACK_SLOTS / 2 && buf_sz > 0; spi++) { bool lo = spis_test_bit(spis, spi * 2); bool hi = spis_test_bit(spis, spi * 2 + 1); const char *space = first ? "" : " "; if (!lo && !hi) continue; if (!lo || !hi) { /* half-spi */ n = scnprintf(buf, buf_sz, "%sfp%d%d%s", space, frame, spi_off(spi) + (lo ? STACK_SLOT_SZ : 0), "h"); } else if (spi + 2 < STACK_SLOTS / 2 && spis_test_bit(spis, spi * 2 + 2) && spis_test_bit(spis, spi * 2 + 3) && spis_test_bit(spis, spi * 2 + 4) && spis_test_bit(spis, spi * 2 + 5)) { /* 3+ consecutive full spis */ run_start = spi; while (spi + 1 < STACK_SLOTS / 2 && spis_test_bit(spis, (spi + 1) * 2) && spis_test_bit(spis, (spi + 1) * 2 + 1)) spi++; n = scnprintf(buf, buf_sz, "%sfp%d%d..%d", space, frame, spi_off(run_start), spi_off(spi)); } else { /* just a full spi */ n = scnprintf(buf, buf_sz, "%sfp%d%d", space, frame, spi_off(spi)); } first = false; buf += n; buf_sz -= n; } return env->tmp_str_buf;} static void print_instance(struct bpf_verifier_env *env, struct func_instance *instance){ int start = env->subprog_info[instance->subprog].start; struct bpf_insn *insns = env->prog->insnsi; struct per_frame_masks *masks; int len = instance->insn_cnt; int insn_idx, frame, i; bool has_use, has_def; u64 pos, insn_pos; if (!(env->log.level & BPF_LOG_LEVEL2)) return; verbose(env, "stack use/def %s ", fmt_subprog(env, instance->subprog)); verbose(env, "%s:\n", fmt_instance(env, instance)); for (i = 0; i < len; i++) { insn_idx = start + i; has_use = false; has_def = false; pos = env->log.end_pos; verbose(env, "%3d: ", insn_idx); bpf_verbose_insn(env, &insns[insn_idx]); insn_pos = env->log.end_pos; verbose(env, "%*c;", bpf_vlog_alignment(insn_pos - pos), ' ');Lines 1–500 of 2332. Load more
// SPDX-License-Identifier: GPL-2.0-only /* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */ #include <linux/bpf_verifier.h> #include <linux/btf.h> #include <linux/hashtable.h> #include <linux/jhash.h> #include <linux/slab.h> #include <linux/sort.h> #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) struct per_frame_masks { spis_t may_read; /* stack slots that may be read by this instruction */ spis_t must_write; /* stack slots written by this instruction */ spis_t live_before; /* stack slots that may be read by this insn and its successors */ }; /* * A function instance keyed by (callsite, depth). * Encapsulates read and write marks for each instruction in the function. * Marks are tracked for each frame up to @depth. */ struct func_instance { struct hlist_node hl_node; u32 callsite; /* call insn that invoked this subprog (subprog_start for depth 0) */ u32 depth; /* call depth (0 = entry subprog) */ u32 subprog; /* subprog index */ u32 subprog_start; /* cached env->subprog_info[subprog].start */ u32 insn_cnt; /* cached number of insns in the function */ /* Per frame, per instruction masks, frames allocated lazily. */ struct per_frame_masks *frames[MAX_CALL_FRAMES]; bool must_write_initialized; }; struct live_stack_query { struct func_instance *instances[MAX_CALL_FRAMES]; /* valid in range [0..curframe] */ u32 callsites[MAX_CALL_FRAMES]; /* callsite[i] = insn calling frame i+1 */ u32 curframe; u32 insn_idx; }; struct bpf_liveness { DECLARE_HASHTABLE(func_instances, 8); /* maps (depth, callsite) to func_instance */ struct live_stack_query live_stack_query; /* cache to avoid repetitive ht lookups */ u32 subprog_calls; /* analyze_subprog() invocations */ }; /* * Hash/compare key for func_instance: (depth, callsite). * For depth == 0 (entry subprog), @callsite is the subprog start insn. * For depth > 0, @callsite is the call instruction index that invoked the subprog. */ static u32 instance_hash(u32 callsite, u32 depth) { u32 key[2] = { depth, callsite }; return jhash2(key, 2, 0); } static struct func_instance *find_instance(struct bpf_verifier_env *env, u32 callsite, u32 depth) { struct bpf_liveness *liveness = env->liveness; struct func_instance *f; u32 key = instance_hash(callsite, depth); hash_for_each_possible(liveness->func_instances, f, hl_node, key) if (f->depth == depth && f->callsite == callsite) return f; return NULL; } static struct func_instance *call_instance(struct bpf_verifier_env *env, struct func_instance *caller, u32 callsite, int subprog) { u32 depth = caller ? caller->depth + 1 : 0; u32 subprog_start = env->subprog_info[subprog].start; u32 lookup_key = depth > 0 ? callsite : subprog_start; struct func_instance *f; u32 hash; f = find_instance(env, lookup_key, depth); if (f) return f; f = kvzalloc_obj(*f, GFP_KERNEL_ACCOUNT); if (!f) return ERR_PTR(-ENOMEM); f->callsite = lookup_key; f->depth = depth; f->subprog = subprog; f->subprog_start = subprog_start; f->insn_cnt = (env->subprog_info + subprog + 1)->start - subprog_start; hash = instance_hash(lookup_key, depth); hash_add(env->liveness->func_instances, &f->hl_node, hash); return f; } static struct func_instance *lookup_instance(struct bpf_verifier_env *env, struct bpf_verifier_state *st, u32 frameno) { u32 callsite, subprog_start; struct func_instance *f; u32 key, depth; subprog_start = env->subprog_info[st->frame[frameno]->subprogno].start; callsite = frameno > 0 ? st->frame[frameno]->callsite : subprog_start; for (depth = frameno; ; depth--) { key = depth > 0 ? callsite : subprog_start; f = find_instance(env, key, depth); if (f || depth == 0) return f; } } int bpf_stack_liveness_init(struct bpf_verifier_env *env) { env->liveness = kvzalloc_obj(*env->liveness, GFP_KERNEL_ACCOUNT); if (!env->liveness) return -ENOMEM; hash_init(env->liveness->func_instances); return 0; } void bpf_stack_liveness_free(struct bpf_verifier_env *env) { struct func_instance *instance; struct hlist_node *tmp; int bkt, i; if (!env->liveness) return; hash_for_each_safe(env->liveness->func_instances, bkt, tmp, instance, hl_node) { for (i = 0; i <= instance->depth; i++) kvfree(instance->frames[i]); kvfree(instance); } kvfree(env->liveness); } /* * Convert absolute instruction index @insn_idx to an index relative * to start of the function corresponding to @instance. */ static int relative_idx(struct func_instance *instance, u32 insn_idx) { return insn_idx - instance->subprog_start; } static struct per_frame_masks *get_frame_masks(struct func_instance *instance, u32 frame, u32 insn_idx) { if (!instance->frames[frame]) return NULL; return &instance->frames[frame][relative_idx(instance, insn_idx)]; } static struct per_frame_masks *alloc_frame_masks(struct func_instance *instance, u32 frame, u32 insn_idx) { struct per_frame_masks *arr; if (!instance->frames[frame]) { arr = kvzalloc_objs(*arr, instance->insn_cnt, GFP_KERNEL_ACCOUNT); instance->frames[frame] = arr; if (!arr) return ERR_PTR(-ENOMEM); } return get_frame_masks(instance, frame, insn_idx); } /* Accumulate may_read masks for @frame at @insn_idx */ static int mark_stack_read(struct func_instance *instance, u32 frame, u32 insn_idx, spis_t mask) { struct per_frame_masks *masks; masks = alloc_frame_masks(instance, frame, insn_idx); if (IS_ERR(masks)) return PTR_ERR(masks); masks->may_read = spis_or(masks->may_read, mask); return 0; } static int mark_stack_write(struct func_instance *instance, u32 frame, u32 insn_idx, spis_t mask) { struct per_frame_masks *masks; masks = alloc_frame_masks(instance, frame, insn_idx); if (IS_ERR(masks)) return PTR_ERR(masks); masks->must_write = spis_or(masks->must_write, mask); return 0; } int bpf_jmp_offset(struct bpf_insn *insn) { u8 code = insn->code; if (code == (BPF_JMP32 | BPF_JA)) return insn->imm; return insn->off; } __diag_push(); __diag_ignore_all("-Woverride-init", "Allow field initialization overrides for opcode_info_tbl"); /* * Returns an array of instructions succ, with succ->items[0], ..., * succ->items[n-1] with successor instructions, where n=succ->cnt */ inline struct bpf_iarray * bpf_insn_successors(struct bpf_verifier_env *env, u32 idx) { static const struct opcode_info { bool can_jump; bool can_fallthrough; } opcode_info_tbl[256] = { [0 ... 255] = {.can_jump = false, .can_fallthrough = true}, #define _J(code, ...) \ [BPF_JMP | code] = __VA_ARGS__, \ [BPF_JMP32 | code] = __VA_ARGS__ _J(BPF_EXIT, {.can_jump = false, .can_fallthrough = false}), _J(BPF_JA, {.can_jump = true, .can_fallthrough = false}), _J(BPF_JEQ, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JNE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JLT, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JLE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JGT, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JGE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSGT, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSGE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSLT, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSLE, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JCOND, {.can_jump = true, .can_fallthrough = true}), _J(BPF_JSET, {.can_jump = true, .can_fallthrough = true}), #undef _J }; struct bpf_prog *prog = env->prog; struct bpf_insn *insn = &prog->insnsi[idx]; const struct opcode_info *opcode_info; struct bpf_iarray *succ, *jt; int insn_sz; jt = env->insn_aux_data[idx].jt; if (unlikely(jt)) return jt; /* pre-allocated array of size up to 2; reset cnt, as it may have been used already */ succ = env->succ; succ->cnt = 0; opcode_info = &opcode_info_tbl[BPF_CLASS(insn->code) | BPF_OP(insn->code)]; insn_sz = bpf_is_ldimm64(insn) ? 2 : 1; if (opcode_info->can_fallthrough) succ->items[succ->cnt++] = idx + insn_sz; if (opcode_info->can_jump) succ->items[succ->cnt++] = idx + bpf_jmp_offset(insn) + 1; return succ; } __diag_pop(); static inline bool update_insn(struct bpf_verifier_env *env, struct func_instance *instance, u32 frame, u32 insn_idx) { spis_t new_before, new_after; struct per_frame_masks *insn, *succ_insn; struct bpf_iarray *succ; u32 s; bool changed; succ = bpf_insn_successors(env, insn_idx); if (succ->cnt == 0) return false; changed = false; insn = get_frame_masks(instance, frame, insn_idx); new_before = SPIS_ZERO; new_after = SPIS_ZERO; for (s = 0; s < succ->cnt; ++s) { succ_insn = get_frame_masks(instance, frame, succ->items[s]); new_after = spis_or(new_after, succ_insn->live_before); } /* * New "live_before" is a union of all "live_before" of successors * minus slots written by instruction plus slots read by instruction. * new_before = (new_after & ~insn->must_write) | insn->may_read */ new_before = spis_or(spis_and(new_after, spis_not(insn->must_write)), insn->may_read); changed |= !spis_equal(new_before, insn->live_before); insn->live_before = new_before; return changed; } /* Fixed-point computation of @live_before marks */ static void update_instance(struct bpf_verifier_env *env, struct func_instance *instance) { u32 i, frame, po_start, po_end; int *insn_postorder = env->cfg.insn_postorder; struct bpf_subprog_info *subprog; bool changed; instance->must_write_initialized = true; subprog = &env->subprog_info[instance->subprog]; po_start = subprog->postorder_start; po_end = (subprog + 1)->postorder_start; /* repeat until fixed point is reached */ do { changed = false; for (frame = 0; frame <= instance->depth; frame++) { if (!instance->frames[frame]) continue; for (i = po_start; i < po_end; i++) changed |= update_insn(env, instance, frame, insn_postorder[i]); } } while (changed); } static bool is_live_before(struct func_instance *instance, u32 insn_idx, u32 frameno, u32 half_spi) { struct per_frame_masks *masks; masks = get_frame_masks(instance, frameno, insn_idx); return masks && spis_test_bit(masks->live_before, half_spi); } int bpf_live_stack_query_init(struct bpf_verifier_env *env, struct bpf_verifier_state *st) { struct live_stack_query *q = &env->liveness->live_stack_query; struct func_instance *instance; u32 frame; memset(q, 0, sizeof(*q)); for (frame = 0; frame <= st->curframe; frame++) { instance = lookup_instance(env, st, frame); if (IS_ERR_OR_NULL(instance)) q->instances[frame] = NULL; else q->instances[frame] = instance; if (frame < st->curframe) q->callsites[frame] = st->frame[frame + 1]->callsite; } q->curframe = st->curframe; q->insn_idx = st->insn_idx; return 0; } bool bpf_stack_slot_alive(struct bpf_verifier_env *env, u32 frameno, u32 half_spi) { /* * Slot is alive if it is read before q->insn_idx in current func instance, * or if for some outer func instance: * - alive before callsite if callsite calls callback, otherwise * - alive after callsite */ struct live_stack_query *q = &env->liveness->live_stack_query; struct func_instance *instance, *curframe_instance; u32 i, callsite, rel; int cur_delta, delta; bool alive = false; curframe_instance = q->instances[q->curframe]; if (!curframe_instance) return true; cur_delta = (int)curframe_instance->depth - (int)q->curframe; rel = frameno + cur_delta; if (rel <= curframe_instance->depth) alive = is_live_before(curframe_instance, q->insn_idx, rel, half_spi); if (alive) return true; for (i = frameno; i < q->curframe; i++) { instance = q->instances[i]; if (!instance) return true; /* Map actual frameno to frame index within this instance */ delta = (int)instance->depth - (int)i; rel = frameno + delta; if (rel > instance->depth) return true; /* Get callsite from verifier state, not from instance callchain */ callsite = q->callsites[i]; alive = bpf_calls_callback(env, callsite) ? is_live_before(instance, callsite, rel, half_spi) : is_live_before(instance, callsite + 1, rel, half_spi); if (alive) return true; } return false; } static char *fmt_subprog(struct bpf_verifier_env *env, int subprog) { const char *name = env->subprog_info[subprog].name; snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf), "subprog#%d%s%s", subprog, name ? " " : "", name ? name : ""); return env->tmp_str_buf; } static char *fmt_instance(struct bpf_verifier_env *env, struct func_instance *instance) { snprintf(env->tmp_str_buf, sizeof(env->tmp_str_buf), "(d%d,cs%d)", instance->depth, instance->callsite); return env->tmp_str_buf; } static int spi_off(int spi) { return -(spi + 1) * BPF_REG_SIZE; } /* * When both halves of an 8-byte SPI are set, print as "-8","-16",... * When only one half is set, print as "-4h","-8h",... * Runs of 3+ consecutive fully-set SPIs are collapsed: "fp0-8..-24" */ static char *fmt_spis_mask(struct bpf_verifier_env *env, int frame, bool first, spis_t spis) { int buf_sz = sizeof(env->tmp_str_buf); char *buf = env->tmp_str_buf; int spi, n, run_start; buf[0] = '\0'; for (spi = 0; spi < STACK_SLOTS / 2 && buf_sz > 0; spi++) { bool lo = spis_test_bit(spis, spi * 2); bool hi = spis_test_bit(spis, spi * 2 + 1); const char *space = first ? "" : " "; if (!lo && !hi) continue; if (!lo || !hi) { /* half-spi */ n = scnprintf(buf, buf_sz, "%sfp%d%d%s", space, frame, spi_off(spi) + (lo ? STACK_SLOT_SZ : 0), "h"); } else if (spi + 2 < STACK_SLOTS / 2 && spis_test_bit(spis, spi * 2 + 2) && spis_test_bit(spis, spi * 2 + 3) && spis_test_bit(spis, spi * 2 + 4) && spis_test_bit(spis, spi * 2 + 5)) { /* 3+ consecutive full spis */ run_start = spi; while (spi + 1 < STACK_SLOTS / 2 && spis_test_bit(spis, (spi + 1) * 2) && spis_test_bit(spis, (spi + 1) * 2 + 1)) spi++; n = scnprintf(buf, buf_sz, "%sfp%d%d..%d", space, frame, spi_off(run_start), spi_off(spi)); } else { /* just a full spi */ n = scnprintf(buf, buf_sz, "%sfp%d%d", space, frame, spi_off(spi)); } first = false; buf += n; buf_sz -= n; } return env->tmp_str_buf; } static void print_instance(struct bpf_verifier_env *env, struct func_instance *instance) { int start = env->subprog_info[instance->subprog].start; struct bpf_insn *insns = env->prog->insnsi; struct per_frame_masks *masks; int len = instance->insn_cnt; int insn_idx, frame, i; bool has_use, has_def; u64 pos, insn_pos; if (!(env->log.level & BPF_LOG_LEVEL2)) return; verbose(env, "stack use/def %s ", fmt_subprog(env, instance->subprog)); verbose(env, "%s:\n", fmt_instance(env, instance)); for (i = 0; i < len; i++) { insn_idx = start + i; has_use = false; has_def = false; pos = env->log.end_pos; verbose(env, "%3d: ", insn_idx); bpf_verbose_insn(env, &insns[insn_idx]); insn_pos = env->log.end_pos; verbose(env, "%*c;", bpf_vlog_alignment(insn_pos - pos), ' ');