The next patch would require doing postorder traversal of individual
subprograms. Facilitate this by moving env->cfg.insn_postorder
computation from check_cfg() to a separate pass, as check_cfg()
descends into called subprograms (and it needs to, because of
merge_callee_effects() logic).
env->cfg.insn_postorder is used only by compute_live_registers(),
this function does not track cross subprogram dependencies,
thus the change does not affect it's operation.
Signed-off-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
---
include/linux/bpf_verifier.h | 6 +++-
kernel/bpf/verifier.c | 67 +++++++++++++++++++++++++++++-------
2 files changed, 59 insertions(+), 14 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 93563564bde5..bd87e80f9423 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -665,6 +665,7 @@ struct bpf_subprog_info {
/* 'start' has to be the first field otherwise find_subprog() won't work */
u32 start; /* insn idx of function entry point */
u32 linfo_idx; /* The idx to the main_prog->aux->linfo */
+ u32 postorder_start; /* The idx to the env->cfg.insn_postorder */
u16 stack_depth; /* max. stack depth used by this function */
u16 stack_extra;
/* offsets in range [stack_depth .. fastcall_stack_off)
@@ -794,7 +795,10 @@ struct bpf_verifier_env {
struct {
int *insn_state;
int *insn_stack;
- /* vector of instruction indexes sorted in post-order */
+ /*
+ * vector of instruction indexes sorted in post-order, grouped by subprogram,
+ * see bpf_subprog_info->postorder_start.
+ */
int *insn_postorder;
int cur_stack;
/* current position in the insn_postorder vector */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5658e1e1d5c5..bdcc20d2fab6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17834,7 +17834,7 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
static int check_cfg(struct bpf_verifier_env *env)
{
int insn_cnt = env->prog->len;
- int *insn_stack, *insn_state, *insn_postorder;
+ int *insn_stack, *insn_state;
int ex_insn_beg, i, ret = 0;
insn_state = env->cfg.insn_state = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
@@ -17847,14 +17847,6 @@ static int check_cfg(struct bpf_verifier_env *env)
return -ENOMEM;
}
- insn_postorder = env->cfg.insn_postorder =
- kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL_ACCOUNT);
- if (!insn_postorder) {
- kvfree(insn_state);
- kvfree(insn_stack);
- return -ENOMEM;
- }
-
ex_insn_beg = env->exception_callback_subprog
? env->subprog_info[env->exception_callback_subprog].start
: 0;
@@ -17872,7 +17864,6 @@ static int check_cfg(struct bpf_verifier_env *env)
case DONE_EXPLORING:
insn_state[t] = EXPLORED;
env->cfg.cur_stack--;
- insn_postorder[env->cfg.cur_postorder++] = t;
break;
case KEEP_EXPLORING:
break;
@@ -17926,6 +17917,55 @@ static int check_cfg(struct bpf_verifier_env *env)
return ret;
}
+/*
+ * For each subprogram 'i' fill array env->cfg.insn_subprogram sub-range
+ * [env->subprog_info[i].postorder_start, env->subprog_info[i+1].postorder_start)
+ * with indices of 'i' instructions in postorder.
+ */
+static int compute_postorder(struct bpf_verifier_env *env)
+{
+ u32 cur_postorder, i, top, stack_sz, s, succ_cnt, succ[2];
+ int *stack = NULL, *postorder = NULL, *state = NULL;
+
+ postorder = kvcalloc(env->prog->len, sizeof(int), GFP_KERNEL_ACCOUNT);
+ state = kvcalloc(env->prog->len, sizeof(int), GFP_KERNEL_ACCOUNT);
+ stack = kvcalloc(env->prog->len, sizeof(int), GFP_KERNEL_ACCOUNT);
+ if (!postorder || !state || !stack) {
+ kvfree(postorder);
+ kvfree(state);
+ kvfree(stack);
+ return -ENOMEM;
+ }
+ cur_postorder = 0;
+ for (i = 0; i < env->subprog_cnt; i++) {
+ env->subprog_info[i].postorder_start = cur_postorder;
+ stack[0] = env->subprog_info[i].start;
+ stack_sz = 1;
+ do {
+ top = stack[stack_sz - 1];
+ if (state[top] & EXPLORED) {
+ postorder[cur_postorder++] = top;
+ stack_sz--;
+ continue;
+ }
+ succ_cnt = bpf_insn_successors(env->prog, top, succ);
+ for (s = 0; s < succ_cnt; ++s) {
+ if (!state[succ[s]]) {
+ stack[stack_sz++] = succ[s];
+ state[succ[s]] |= DISCOVERED;
+ }
+ }
+ state[top] |= EXPLORED;
+ } while (stack_sz);
+ }
+ env->subprog_info[i].postorder_start = cur_postorder;
+ env->cfg.insn_postorder = postorder;
+ env->cfg.cur_postorder = cur_postorder;
+ kvfree(stack);
+ kvfree(state);
+ return 0;
+}
+
static int check_abnormal_return(struct bpf_verifier_env *env)
{
int i;
@@ -24387,9 +24427,6 @@ static int compute_live_registers(struct bpf_verifier_env *env)
out:
kvfree(state);
- kvfree(env->cfg.insn_postorder);
- env->cfg.insn_postorder = NULL;
- env->cfg.cur_postorder = 0;
return err;
}
@@ -24692,6 +24729,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
if (ret < 0)
goto skip_full_check;
+ ret = compute_postorder(env);
+ if (ret < 0)
+ goto skip_full_check;
+
ret = check_attach_btf_id(env);
if (ret)
goto skip_full_check;
--
2.47.3
