The table is on the instructions and the landing pads are in the control flow graph. What is left before bpf_throw() can be taught to dispatch them is to work out what that walk will need, and refuse the shapes it could not handle. bpf_check_cleanup_exceptions() runs after bpf_check_cfg(). Everything it needs is control flow, so it reads what that walk has already worked out rather than working it out again: subprog_info.might_throw which subprograms an exception may leave, closed over the call graph by merge_callee_effects() as the walk pops each callee cleanup_reachability() what each instruction can reach -- a resume, a plain exit, a throw, an indirect jump cleanup_mark_pad_bodies() which instructions only ever run with an exception already in flight What it refuses: - a pad that reaches both a resume and a plain exit, or neither: nothing says whether it is a cleanup pad or a catch pad - a catch pad, which ends in a plain exit: the walker calls a pad as a subroutine and cannot hand a frame back its own execution - a throw in a pad, or a call from a pad to a subprogram that can throw: a second unwind over frames the first is still discarding - a bpf_unwind_resume() outside a pad body - a subprogram that may unwind used as a helper callback: the helper's own kernel frame would end the walk before it found a boundary - a tail call, an indirect jump, or an outgoing on-stack call argument in a pad body, all of which touch a stack the pad does not own Signed-off-by: Yonghong Song --- include/linux/bpf_verifier.h | 1 + kernel/bpf/exception.c | 397 +++++++++++++++++++++++++++++++++++ kernel/bpf/exception.h | 2 + kernel/bpf/fixups.c | 1 + kernel/bpf/verifier.c | 8 + 5 files changed, 409 insertions(+) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 7463e86d15ee..fe8b26351a15 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -682,6 +682,7 @@ struct bpf_insn_aux_data { bool non_sleepable; /* helper/kfunc may be called from non-sleepable context */ bool is_iter_next; /* bpf_iter__next() kfunc call */ bool cleanup_throw_site; /* call to bpf_throw() */ + bool in_cleanup_pad; /* only runs with an exception in flight */ /* * 1 + the instruction index of the exception cleanup landing pad this * call site unwinds to, or 0 for none. diff --git a/kernel/bpf/exception.c b/kernel/bpf/exception.c index dfe9c2a9ce7d..b2bf831242b8 100644 --- a/kernel/bpf/exception.c +++ b/kernel/bpf/exception.c @@ -6,6 +6,7 @@ #include #include #include +#include #include "exception.h" #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args) @@ -23,6 +24,130 @@ static bool insn_is_exc_kfunc(const struct bpf_insn *insn, int kf) insn->imm == exc_kfunc_list[kf]; } +/* What an instruction does to intra-subprog control flow. */ +enum cleanup_insn_kind { + CLEANUP_INSN_PLAIN, /* the next insn runs */ + CLEANUP_INSN_JUMP, /* unconditional jump */ + CLEANUP_INSN_COND, /* the next insn runs, or the branch target */ + CLEANUP_INSN_EXIT, + CLEANUP_INSN_THROW, /* call bpf_throw: nothing after it runs */ + CLEANUP_INSN_RESUME, /* call bpf_unwind_resume: likewise */ + CLEANUP_INSN_CALL, /* call to another subprog */ + CLEANUP_INSN_GOTOX, /* indirect jump: successors not known here */ +}; + +/* What each instruction can reach, computed once by cleanup_reachability(). */ +#define CLEANUP_REACH_RESUME BIT(0) /* a bpf_unwind_resume() call */ +#define CLEANUP_REACH_EXIT BIT(1) /* a plain BPF_EXIT */ +#define CLEANUP_REACH_UNKNOWN BIT(2) /* an indirect jump */ +#define CLEANUP_REACH_THROW BIT(3) /* a bpf_throw() call */ + +/* Scratch shared by the analyses, sized once so no walker has to allocate. */ +struct cleanup_ctx { + struct bpf_verifier_env *env; + u8 *reach; /* per insn: CLEANUP_REACH_* mask */ + u32 *stack; /* per insn: DFS stack */ + void *scratch; /* the one allocation all of the above live in */ +}; + +static bool in_pad(struct bpf_verifier_env *env, u32 i) +{ + return env->insn_aux_data[i].in_cleanup_pad; +} + +/* One scratch array for cleanup_alloc() to hand out. */ +struct cleanup_alloc_req { + void **dst; + size_t n, sz; +}; + +static void *cleanup_alloc(const struct cleanup_alloc_req *tab, u32 cnt) +{ + size_t total = 0; + char *block, *p; + u32 i; + + for (i = 0; i < cnt; i++) + total += round_up(tab[i].n * tab[i].sz, 8); + + block = kvzalloc(total, GFP_KERNEL_ACCOUNT | __GFP_NOWARN); + if (!block) + return NULL; + + for (i = 0, p = block; i < cnt; i++) { + *tab[i].dst = p; + p += round_up(tab[i].n * tab[i].sz, 8); + } + return block; +} + +static int cleanup_subprog_of(struct bpf_verifier_env *env, u32 off) +{ + struct bpf_subprog_info *info = bpf_find_containing_subprog(env, off); + + return info ? info - env->subprog_info : -1; +} + +/* The subprogram a linear pass is currently in. */ +struct cleanup_cursor { + u32 start, end; /* [start, end) of the current subprogram */ + int sub; /* its index */ +}; + +#define CLEANUP_CURSOR_INIT { .sub = -1 } + +static void cleanup_cursor_to(struct bpf_verifier_env *env, struct cleanup_cursor *c, u32 i) +{ + while (i >= c->end) { + c->sub++; + c->start = env->subprog_info[c->sub].start; + c->end = env->subprog_info[c->sub + 1].start; + } +} + +static enum cleanup_insn_kind cleanup_classify(struct bpf_verifier_env *env, u32 i, + int *next, int *target) +{ + struct bpf_insn *insn = &env->prog->insnsi[i]; + u8 class = BPF_CLASS(insn->code); + + *next = i + 1; + *target = -1; + + if (insn->code == (BPF_LD | BPF_IMM | BPF_DW)) { + *next = i + 2; + return CLEANUP_INSN_PLAIN; + } + if (class != BPF_JMP && class != BPF_JMP32) + return CLEANUP_INSN_PLAIN; + + switch (BPF_OP(insn->code)) { + case BPF_EXIT: + *next = -1; + return CLEANUP_INSN_EXIT; + case BPF_JA: + *next = -1; + if (BPF_SRC(insn->code) == BPF_X) + return CLEANUP_INSN_GOTOX; + *target = class == BPF_JMP32 ? i + insn->imm + 1 : i + insn->off + 1; + return CLEANUP_INSN_JUMP; + case BPF_CALL: + if (bpf_is_throw_kfunc(insn)) { + *next = -1; + return CLEANUP_INSN_THROW; + } + if (insn_is_exc_kfunc(insn, EXC_KF_bpf_unwind_resume)) { + *next = -1; + return CLEANUP_INSN_RESUME; + } + return bpf_pseudo_call(insn) ? CLEANUP_INSN_CALL : CLEANUP_INSN_PLAIN; + default: + /* Conditional jump, including BPF_JCOND. */ + *target = i + insn->off + 1; + return CLEANUP_INSN_COND; + } +} + static void cleanup_mark_throw_sites(struct bpf_verifier_env *env) { u32 i; @@ -32,6 +157,247 @@ static void cleanup_mark_throw_sites(struct bpf_verifier_env *env) env->insn_aux_data[i].cleanup_throw_site = true; } +int bpf_cleanup_check_callback(struct bpf_verifier_env *env, int subprog) +{ + if (!env->cleanup_info_cnt || !env->subprog_info[subprog].might_throw) + return 0; + + verbose(env, "subprog %d may unwind and is used as a callback\n", subprog); + return -EINVAL; +} + +/* Intra-subprog successors of @i, or -1 each when absent. */ +static enum cleanup_insn_kind cleanup_succ(struct bpf_verifier_env *env, u32 i, + u32 start, u32 end, int *next, int *target) +{ + enum cleanup_insn_kind kind = cleanup_classify(env, i, next, target); + + if (*next < (int)start || *next >= (int)end) + *next = -1; + if (*target < (int)start || *target >= (int)end) + *target = -1; + return kind; +} + +static void cleanup_add_pred(u32 *head, u32 *link, u32 to, u32 e) +{ + link[e] = head[to]; + head[to] = e + 1; +} + +/* What every instruction can reach along intra-subprog edges, for + * cleanup_pad_is_catch(). One backward walk over a predecessor index, rather + * than a forward walk from each landing pad, which would be quadratic. + */ +static int cleanup_reachability(struct cleanup_ctx *ctx) +{ + struct bpf_verifier_env *env = ctx->env; + u32 len = env->prog->len; + struct cleanup_cursor c = CLEANUP_CURSOR_INIT; + u32 *head = NULL, *link = NULL; + bool *queued = NULL; + u32 i, sp = 0; + void *scratch; + const struct cleanup_alloc_req tab[] = { + { (void **)&head, len, sizeof(*head) }, + { (void **)&link, 2 * (size_t)len, sizeof(*link) }, + { (void **)&queued, len, sizeof(*queued) }, + }; + + scratch = cleanup_alloc(tab, ARRAY_SIZE(tab)); + if (!scratch) + return -ENOMEM; + + /* Index the predecessors, and seed the walk at the terminators. */ + for (i = 0; i < len; i++) { + enum cleanup_insn_kind kind; + int next, target; + + cleanup_cursor_to(env, &c, i); + kind = cleanup_succ(env, i, c.start, c.end, &next, &target); + + if (kind == CLEANUP_INSN_RESUME) + ctx->reach[i] |= CLEANUP_REACH_RESUME; + else if (kind == CLEANUP_INSN_EXIT) + ctx->reach[i] |= CLEANUP_REACH_EXIT; + else if (kind == CLEANUP_INSN_GOTOX) + ctx->reach[i] |= CLEANUP_REACH_UNKNOWN; + else if (kind == CLEANUP_INSN_THROW) + ctx->reach[i] |= CLEANUP_REACH_THROW; + + if (next >= 0) + cleanup_add_pred(head, link, next, 2 * i); + if (target >= 0) + cleanup_add_pred(head, link, target, 2 * i + 1); + + if (ctx->reach[i]) { + queued[i] = true; + ctx->stack[sp++] = i; + } + } + + /* Each instruction re-enters the worklist at most once per bit it + * gains, so this is linear in the number of edges. + */ + while (sp) { + u32 j = ctx->stack[--sp]; + u8 flags = ctx->reach[j]; + u32 e; + + queued[j] = false; + for (e = head[j]; e; e = link[e - 1]) { + u32 p = (e - 1) / 2; + + if ((ctx->reach[p] | flags) == ctx->reach[p]) + continue; + ctx->reach[p] |= flags; + if (!queued[p]) { + queued[p] = true; + ctx->stack[sp++] = p; + } + } + } + kvfree(scratch); + return 0; +} + +static int cleanup_pad_is_catch(struct cleanup_ctx *ctx, u32 pad) +{ + u8 reach = ctx->reach[pad]; + + if (reach & CLEANUP_REACH_UNKNOWN) { + verbose(ctx->env, "cleanup landing pad %u reaches an indirect jump\n", pad); + return -EINVAL; + } + if (reach & CLEANUP_REACH_THROW) { + verbose(ctx->env, + "cleanup landing pad %u can throw while an exception is in flight\n", + pad); + return -EINVAL; + } + if (!(reach & CLEANUP_REACH_RESUME) == !(reach & CLEANUP_REACH_EXIT)) { + verbose(ctx->env, "cleanup landing pad %u %s\n", pad, + (reach & CLEANUP_REACH_RESUME) ? + "reaches both bpf_unwind_resume() and a plain exit" : + "reaches neither bpf_unwind_resume() nor an exit"); + return -EINVAL; + } + return !!(reach & CLEANUP_REACH_EXIT); +} + +static int cleanup_check_pad_insn(struct bpf_verifier_env *env, u32 i) +{ + struct bpf_insn *insn = &env->prog->insnsi[i]; + + if (bpf_helper_call(insn) && insn->imm == BPF_FUNC_tail_call) { + verbose(env, + "bpf_tail_call() at insn %u is in an exception cleanup landing pad\n", + i); + return -EINVAL; + } + /* Stack arguments are not supported. */ + if (is_stack_arg_st(insn) || is_stack_arg_stx(insn)) { + verbose(env, + "insn %u passes an on-stack call argument in an exception cleanup landing pad\n", + i); + return -EINVAL; + } + /* Likewise, stack arguments are not supported. */ + if (bpf_pseudo_kfunc_call(insn)) { + struct bpf_call_summary cs; + + if (bpf_get_call_summary(env, insn, &cs) && + cs.arg_slot_cnt > MAX_BPF_FUNC_REG_ARGS) { + verbose(env, + "insn %u passes an on-stack call argument in an exception cleanup landing pad\n", + i); + return -EINVAL; + } + } + return 0; +} + +static int cleanup_mark_pad_bodies(struct cleanup_ctx *ctx) +{ + struct bpf_verifier_env *env = ctx->env; + u32 i, sp = 0; + int ret; + + for (i = 0; i < env->cleanup_info_cnt; i++) { + u32 pad = env->cleanup_info[i].landing_pad_off; + + if (in_pad(env, pad)) + continue; + + ret = cleanup_pad_is_catch(ctx, pad); + if (ret < 0) + return ret; + if (ret) { + verbose(env, + "catch landing pad %u is not supported yet, only cleanup pads that resume\n", + pad); + return -EOPNOTSUPP; + } + env->insn_aux_data[pad].in_cleanup_pad = true; + ctx->stack[sp++] = pad; + } + + while (sp) { + u32 j = ctx->stack[--sp]; + enum cleanup_insn_kind kind; + int next, target, sub; + u32 start, end; + + ret = cleanup_check_pad_insn(env, j); + if (ret) + return ret; + + sub = cleanup_subprog_of(env, j); + start = env->subprog_info[sub].start; + end = env->subprog_info[sub + 1].start; + kind = cleanup_succ(env, j, start, end, &next, &target); + + if (kind == CLEANUP_INSN_CALL) { + int callee = cleanup_subprog_of(env, j + env->prog->insnsi[j].imm + 1); + + if (env->subprog_info[callee].might_throw) { + verbose(env, + "cleanup landing pad calls subprog %d at insn %u, which can throw while an exception is in flight\n", + callee, j); + return -EINVAL; + } + } + + if (next >= 0 && !in_pad(env, next)) { + env->insn_aux_data[next].in_cleanup_pad = true; + ctx->stack[sp++] = next; + } + if (target >= 0 && !in_pad(env, target)) { + env->insn_aux_data[target].in_cleanup_pad = true; + ctx->stack[sp++] = target; + } + } + return 0; +} + +static int cleanup_check_resumes(struct cleanup_ctx *ctx) +{ + struct bpf_verifier_env *env = ctx->env; + u32 i; + + for (i = 0; i < env->prog->len; i++) { + if (!insn_is_exc_kfunc(&env->prog->insnsi[i], EXC_KF_bpf_unwind_resume)) + continue; + if (in_pad(env, i)) + continue; + verbose(env, + "bpf_unwind_resume() at insn %u is not in an exception cleanup landing pad\n", + i); + return -EINVAL; + } + return 0; +} + static void cleanup_mark_call_sites(struct bpf_verifier_env *env) { u32 i, j; @@ -78,6 +444,37 @@ int bpf_prepare_cleanup_exceptions(struct bpf_verifier_env *env) return 0; } +int bpf_check_cleanup_exceptions(struct bpf_verifier_env *env) +{ + u32 len = env->prog->len; + struct cleanup_ctx ctx = { .env = env }; + const struct cleanup_alloc_req tab[] = { + { (void **)&ctx.reach, len, sizeof(*ctx.reach) }, + { (void **)&ctx.stack, len, sizeof(*ctx.stack) }, + }; + int ret; + + if (!env->cleanup_info_cnt) + return 0; + + ctx.scratch = cleanup_alloc(tab, ARRAY_SIZE(tab)); + if (!ctx.scratch) + return -ENOMEM; + + ret = cleanup_reachability(&ctx); + if (ret) + goto out; + + ret = cleanup_mark_pad_bodies(&ctx); + if (ret) + goto out; + + ret = cleanup_check_resumes(&ctx); +out: + kvfree(ctx.scratch); + return ret; +} + bool bpf_is_unwind_resume_kfunc(const struct bpf_insn *insn) { return insn_is_exc_kfunc(insn, EXC_KF_bpf_unwind_resume); diff --git a/kernel/bpf/exception.h b/kernel/bpf/exception.h index f51383fd775c..7313dd2b65a1 100644 --- a/kernel/bpf/exception.h +++ b/kernel/bpf/exception.h @@ -8,6 +8,8 @@ struct bpf_verifier_env; int bpf_prepare_cleanup_exceptions(struct bpf_verifier_env *env); +int bpf_check_cleanup_exceptions(struct bpf_verifier_env *env); +int bpf_cleanup_check_callback(struct bpf_verifier_env *env, int subprog); int bpf_cleanup_pad_of_call(struct bpf_verifier_env *env, u32 idx); #endif /* _LINUX_BPF_EXCEPTION_H */ diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c index 82b00fac6bd6..f120ae66dbbc 100644 --- a/kernel/bpf/fixups.c +++ b/kernel/bpf/fixups.c @@ -252,6 +252,7 @@ static void adjust_insn_aux_data(struct bpf_verifier_env *env, /* Expand insni[off]'s seen count to the patched range. */ data[i].seen = old_seen; data[i].zext_dst = bpf_insn_def32(new_prog, insn + i) >= 0; + data[i].in_cleanup_pad = data[off + cnt - 1].in_cleanup_pad; if (!memcmp(insn + i, original_insn, sizeof(struct bpf_insn))) { data[i].non_stack_access = data[off + cnt - 1].non_stack_access; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 6496c30a10f7..9cbdb8339701 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -10485,6 +10485,10 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins * callbacks */ env->subprog_info[subprog].is_cb = true; + err = bpf_cleanup_check_callback(env, subprog); + if (err) + return err; + if (bpf_pseudo_kfunc_call(insn) && !is_callback_calling_kfunc(insn->imm)) { verifier_bug(env, "kfunc %s#%d not marked as callback-calling", @@ -21664,6 +21668,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, if (ret < 0) goto skip_full_check; + ret = bpf_check_cleanup_exceptions(env); + if (ret < 0) + goto skip_full_check; + ret = bpf_compute_postorder(env); if (ret < 0) goto skip_full_check; -- 2.53.0-Meta