[PATCH bpf-next 0/3] bpf: cleanups on managing subprog information

[PATCH bpf-next 0/3] bpf: cleanups on managing subprog information

[Jiong Wang]

This patch set clean up some code logic related with managing subprog
information.

Part of the set are inspried by Edwin's code in his RFC:

  "bpf/verifier: subprog/func_call simplifications"

but with clearer separation so it could be easier to review.

  - Path 1 unifies main prog and subprogs. All of them are registered in
    env->subprog_starts.

  - After patch 1, it is clear that subprog_starts and subprog_stack_depth
    could be merged as both of them now have main and subprog unified.
    Patch 2 therefore does the merge, all subprog information are centred
    at bpf_subprog_info.

  - Patch 3 goes further to introduce a new fake "exit" subprog which
    serves as an ending marker to the subprog list. We could then turn the
    following code snippets across verifier:

       if (env->subprog_cnt == cur_subprog + 1)
               subprog_end = insn_cnt;
       else
               subprog_end = env->subprog_info[cur_subprog + 1].start;

    into:
       subprog_end = env->subprog_info[cur_subprog + 1].start;

There is no functional change by this patch set.
No bpf selftest regression found after this patch set.

Jiong Wang (3):
  bpf: unify main prog and subprog
  bpf: centre subprog information fields
  bpf: add faked "ending" subprog

 include/linux/bpf_verifier.h |   9 ++--
 kernel/bpf/verifier.c        | 118 +++++++++++++++++++++----------------------
 2 files changed, 65 insertions(+), 62 deletions(-)

-- 
2.7.4

[PATCH bpf-next 1/3] bpf: unify main prog and subprog

[Jiong Wang]

Currently, verifier treat main prog and subprog differently. All subprogs
detected are kept in env->subprog_starts while main prog is not kept there.
Instead, main prog is implicitly defined as the prog start at 0.

There is actually no difference between main prog and subprog, it is better
to unify them, and register all progs detected into env->subprog_starts.

This could also help simplifying some code logic.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 include/linux/bpf_verifier.h |  2 +-
 kernel/bpf/verifier.c        | 57 ++++++++++++++++++++++++--------------------
 2 files changed, 32 insertions(+), 27 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 7e61c39..f655b92 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -191,7 +191,7 @@ struct bpf_verifier_env {
 	bool seen_direct_write;
 	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 	struct bpf_verifier_log log;
-	u32 subprog_starts[BPF_MAX_SUBPROGS];
+	u32 subprog_starts[BPF_MAX_SUBPROGS + 1];
 	/* computes the stack depth of each bpf function */
 	u16 subprog_stack_depth[BPF_MAX_SUBPROGS + 1];
 	u32 subprog_cnt;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index eb1a596..16ec977 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -765,7 +765,7 @@ static int add_subprog(struct bpf_verifier_env *env, int off)
 	ret = find_subprog(env, off);
 	if (ret >= 0)
 		return 0;
-	if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
+	if (env->subprog_cnt > BPF_MAX_SUBPROGS) {
 		verbose(env, "too many subprograms\n");
 		return -E2BIG;
 	}
@@ -781,6 +781,11 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	struct bpf_insn *insn = env->prog->insnsi;
 	int insn_cnt = env->prog->len;
 
+	/* Add entry function. */
+	ret = add_subprog(env, 0);
+	if (ret < 0)
+		return ret;
+
 	/* determine subprog starts. The end is one before the next starts */
 	for (i = 0; i < insn_cnt; i++) {
 		if (insn[i].code != (BPF_JMP | BPF_CALL))
@@ -806,10 +811,10 @@ static int check_subprogs(struct bpf_verifier_env *env)
 
 	/* now check that all jumps are within the same subprog */
 	subprog_start = 0;
-	if (env->subprog_cnt == cur_subprog)
+	if (env->subprog_cnt == cur_subprog + 1)
 		subprog_end = insn_cnt;
 	else
-		subprog_end = env->subprog_starts[cur_subprog++];
+		subprog_end = env->subprog_starts[cur_subprog + 1];
 	for (i = 0; i < insn_cnt; i++) {
 		u8 code = insn[i].code;
 
@@ -833,11 +838,13 @@ static int check_subprogs(struct bpf_verifier_env *env)
 				verbose(env, "last insn is not an exit or jmp\n");
 				return -EINVAL;
 			}
+			cur_subprog++;
 			subprog_start = subprog_end;
-			if (env->subprog_cnt == cur_subprog)
+			if (env->subprog_cnt == cur_subprog + 1)
 				subprog_end = insn_cnt;
 			else
-				subprog_end = env->subprog_starts[cur_subprog++];
+				subprog_end =
+					env->subprog_starts[cur_subprog + 1];
 		}
 	}
 	return 0;
@@ -1505,10 +1512,10 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 		return -EACCES;
 	}
 continue_func:
-	if (env->subprog_cnt == subprog)
+	if (env->subprog_cnt == subprog + 1)
 		subprog_end = insn_cnt;
 	else
-		subprog_end = env->subprog_starts[subprog];
+		subprog_end = env->subprog_starts[subprog + 1];
 	for (; i < subprog_end; i++) {
 		if (insn[i].code != (BPF_JMP | BPF_CALL))
 			continue;
@@ -1526,7 +1533,6 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 				  i);
 			return -EFAULT;
 		}
-		subprog++;
 		frame++;
 		if (frame >= MAX_CALL_FRAMES) {
 			WARN_ONCE(1, "verifier bug. Call stack is too deep\n");
@@ -1558,7 +1564,6 @@ static int get_callee_stack_depth(struct bpf_verifier_env *env,
 			  start);
 		return -EFAULT;
 	}
-	subprog++;
 	return env->subprog_stack_depth[subprog];
 }
 #endif
@@ -2087,7 +2092,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
 	case BPF_FUNC_tail_call:
 		if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY)
 			goto error;
-		if (env->subprog_cnt) {
+		if (env->subprog_cnt > 1) {
 			verbose(env, "tail_calls are not allowed in programs with bpf-to-bpf calls\n");
 			return -EINVAL;
 		}
@@ -2259,7 +2264,7 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 			/* remember the callsite, it will be used by bpf_exit */
 			*insn_idx /* callsite */,
 			state->curframe + 1 /* frameno within this callchain */,
-			subprog + 1 /* subprog number within this prog */);
+			subprog /* subprog number within this prog */);
 
 	/* copy r1 - r5 args that callee can access */
 	for (i = BPF_REG_1; i <= BPF_REG_5; i++)
@@ -3818,7 +3823,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
 		return -EINVAL;
 	}
 
-	if (env->subprog_cnt) {
+	if (env->subprog_cnt > 1) {
 		/* when program has LD_ABS insn JITs and interpreter assume
 		 * that r1 == ctx == skb which is not the case for callees
 		 * that can have arbitrary arguments. It's problematic
@@ -4849,11 +4854,11 @@ static int do_check(struct bpf_verifier_env *env)
 
 	verbose(env, "processed %d insns (limit %d), stack depth ",
 		insn_processed, BPF_COMPLEXITY_LIMIT_INSNS);
-	for (i = 0; i < env->subprog_cnt + 1; i++) {
+	for (i = 0; i < env->subprog_cnt; i++) {
 		u32 depth = env->subprog_stack_depth[i];
 
 		verbose(env, "%d", depth);
-		if (i + 1 < env->subprog_cnt + 1)
+		if (i + 1 < env->subprog_cnt)
 			verbose(env, "+");
 	}
 	verbose(env, "\n");
@@ -5230,7 +5235,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 	void *old_bpf_func;
 	int err = -ENOMEM;
 
-	if (env->subprog_cnt == 0)
+	if (env->subprog_cnt <= 1)
 		return 0;
 
 	for (i = 0, insn = prog->insnsi; i < prog->len; i++, insn++) {
@@ -5246,7 +5251,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 		/* temporarily remember subprog id inside insn instead of
 		 * aux_data, since next loop will split up all insns into funcs
 		 */
-		insn->off = subprog + 1;
+		insn->off = subprog;
 		/* remember original imm in case JIT fails and fallback
 		 * to interpreter will be needed
 		 */
@@ -5255,16 +5260,16 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 		insn->imm = 1;
 	}
 
-	func = kzalloc(sizeof(prog) * (env->subprog_cnt + 1), GFP_KERNEL);
+	func = kzalloc(sizeof(prog) * env->subprog_cnt, GFP_KERNEL);
 	if (!func)
 		return -ENOMEM;
 
-	for (i = 0; i <= env->subprog_cnt; i++) {
+	for (i = 0; i < env->subprog_cnt; i++) {
 		subprog_start = subprog_end;
-		if (env->subprog_cnt == i)
+		if (env->subprog_cnt == i + 1)
 			subprog_end = prog->len;
 		else
-			subprog_end = env->subprog_starts[i];
+			subprog_end = env->subprog_starts[i + 1];
 
 		len = subprog_end - subprog_start;
 		func[i] = bpf_prog_alloc(bpf_prog_size(len), GFP_USER);
@@ -5294,7 +5299,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 	 * now populate all bpf_calls with correct addresses and
 	 * run last pass of JIT
 	 */
-	for (i = 0; i <= env->subprog_cnt; i++) {
+	for (i = 0; i < env->subprog_cnt; i++) {
 		insn = func[i]->insnsi;
 		for (j = 0; j < func[i]->len; j++, insn++) {
 			if (insn->code != (BPF_JMP | BPF_CALL) ||
@@ -5307,7 +5312,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 				__bpf_call_base;
 		}
 	}
-	for (i = 0; i <= env->subprog_cnt; i++) {
+	for (i = 0; i < env->subprog_cnt; i++) {
 		old_bpf_func = func[i]->bpf_func;
 		tmp = bpf_int_jit_compile(func[i]);
 		if (tmp != func[i] || func[i]->bpf_func != old_bpf_func) {
@@ -5321,7 +5326,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 	/* finally lock prog and jit images for all functions and
 	 * populate kallsysm
 	 */
-	for (i = 0; i <= env->subprog_cnt; i++) {
+	for (i = 0; i < env->subprog_cnt; i++) {
 		bpf_prog_lock_ro(func[i]);
 		bpf_prog_kallsyms_add(func[i]);
 	}
@@ -5338,7 +5343,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 			continue;
 		insn->off = env->insn_aux_data[i].call_imm;
 		subprog = find_subprog(env, i + insn->off + 1);
-		addr  = (unsigned long)func[subprog + 1]->bpf_func;
+		addr  = (unsigned long)func[subprog]->bpf_func;
 		addr &= PAGE_MASK;
 		insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
 			    addr - __bpf_call_base;
@@ -5347,10 +5352,10 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 	prog->jited = 1;
 	prog->bpf_func = func[0]->bpf_func;
 	prog->aux->func = func;
-	prog->aux->func_cnt = env->subprog_cnt + 1;
+	prog->aux->func_cnt = env->subprog_cnt;
 	return 0;
 out_free:
-	for (i = 0; i <= env->subprog_cnt; i++)
+	for (i = 0; i < env->subprog_cnt; i++)
 		if (func[i])
 			bpf_jit_free(func[i]);
 	kfree(func);
-- 
2.7.4

[PATCH bpf-next 2/3] bpf: centre subprog information fields

[Jiong Wang]

It is better to centre all subprog information fields into one structure.
This structure could later serve as function node in call graph.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 include/linux/bpf_verifier.h |  9 ++++---
 kernel/bpf/verifier.c        | 62 +++++++++++++++++++++++---------------------
 2 files changed, 38 insertions(+), 33 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index f655b92..8f70dc1 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -173,6 +173,11 @@ static inline bool bpf_verifier_log_needed(const struct bpf_verifier_log *log)
 
 #define BPF_MAX_SUBPROGS 256
 
+struct bpf_subprog_info {
+	u32 start; /* insn idx of function entry point */
+	u16 stack_depth; /* max. stack depth used by this function */
+};
+
 /* single container for all structs
  * one verifier_env per bpf_check() call
  */
@@ -191,9 +196,7 @@ struct bpf_verifier_env {
 	bool seen_direct_write;
 	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 	struct bpf_verifier_log log;
-	u32 subprog_starts[BPF_MAX_SUBPROGS + 1];
-	/* computes the stack depth of each bpf function */
-	u16 subprog_stack_depth[BPF_MAX_SUBPROGS + 1];
+	struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
 	u32 subprog_cnt;
 };
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 16ec977..9764b9b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -738,18 +738,19 @@ enum reg_arg_type {
 
 static int cmp_subprogs(const void *a, const void *b)
 {
-	return *(int *)a - *(int *)b;
+	return ((struct bpf_subprog_info *)a)->start -
+	       ((struct bpf_subprog_info *)b)->start;
 }
 
 static int find_subprog(struct bpf_verifier_env *env, int off)
 {
-	u32 *p;
+	struct bpf_subprog_info *p;
 
-	p = bsearch(&off, env->subprog_starts, env->subprog_cnt,
-		    sizeof(env->subprog_starts[0]), cmp_subprogs);
+	p = bsearch(&off, env->subprog_info, env->subprog_cnt,
+		    sizeof(env->subprog_info[0]), cmp_subprogs);
 	if (!p)
 		return -ENOENT;
-	return p - env->subprog_starts;
+	return p - env->subprog_info;
 
 }
 
@@ -769,15 +770,16 @@ static int add_subprog(struct bpf_verifier_env *env, int off)
 		verbose(env, "too many subprograms\n");
 		return -E2BIG;
 	}
-	env->subprog_starts[env->subprog_cnt++] = off;
-	sort(env->subprog_starts, env->subprog_cnt,
-	     sizeof(env->subprog_starts[0]), cmp_subprogs, NULL);
+	env->subprog_info[env->subprog_cnt++].start = off;
+	sort(env->subprog_info, env->subprog_cnt,
+	     sizeof(env->subprog_info[0]), cmp_subprogs, NULL);
 	return 0;
 }
 
 static int check_subprogs(struct bpf_verifier_env *env)
 {
 	int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
+	struct bpf_subprog_info *subprog = env->subprog_info;
 	struct bpf_insn *insn = env->prog->insnsi;
 	int insn_cnt = env->prog->len;
 
@@ -807,14 +809,14 @@ static int check_subprogs(struct bpf_verifier_env *env)
 
 	if (env->log.level > 1)
 		for (i = 0; i < env->subprog_cnt; i++)
-			verbose(env, "func#%d @%d\n", i, env->subprog_starts[i]);
+			verbose(env, "func#%d @%d\n", i, subprog[i].start);
 
 	/* now check that all jumps are within the same subprog */
 	subprog_start = 0;
 	if (env->subprog_cnt == cur_subprog + 1)
 		subprog_end = insn_cnt;
 	else
-		subprog_end = env->subprog_starts[cur_subprog + 1];
+		subprog_end = subprog[cur_subprog + 1].start;
 	for (i = 0; i < insn_cnt; i++) {
 		u8 code = insn[i].code;
 
@@ -843,8 +845,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			if (env->subprog_cnt == cur_subprog + 1)
 				subprog_end = insn_cnt;
 			else
-				subprog_end =
-					env->subprog_starts[cur_subprog + 1];
+				subprog_end = subprog[cur_subprog + 1].start;
 		}
 	}
 	return 0;
@@ -1477,13 +1478,13 @@ static int update_stack_depth(struct bpf_verifier_env *env,
 			      const struct bpf_func_state *func,
 			      int off)
 {
-	u16 stack = env->subprog_stack_depth[func->subprogno];
+	u16 stack = env->subprog_info[func->subprogno].stack_depth;
 
 	if (stack >= -off)
 		return 0;
 
 	/* update known max for given subprogram */
-	env->subprog_stack_depth[func->subprogno] = -off;
+	env->subprog_info[func->subprogno].stack_depth = -off;
 	return 0;
 }
 
@@ -1495,7 +1496,8 @@ static int update_stack_depth(struct bpf_verifier_env *env,
  */
 static int check_max_stack_depth(struct bpf_verifier_env *env)
 {
-	int depth = 0, frame = 0, subprog = 0, i = 0, subprog_end;
+	int depth = 0, frame = 0, idx = 0, i = 0, subprog_end;
+	struct bpf_subprog_info *subprog = env->subprog_info;
 	struct bpf_insn *insn = env->prog->insnsi;
 	int insn_cnt = env->prog->len;
 	int ret_insn[MAX_CALL_FRAMES];
@@ -1505,17 +1507,17 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 	/* round up to 32-bytes, since this is granularity
 	 * of interpreter stack size
 	 */
-	depth += round_up(max_t(u32, env->subprog_stack_depth[subprog], 1), 32);
+	depth += round_up(max_t(u32, subprog[idx].stack_depth, 1), 32);
 	if (depth > MAX_BPF_STACK) {
 		verbose(env, "combined stack size of %d calls is %d. Too large\n",
 			frame + 1, depth);
 		return -EACCES;
 	}
 continue_func:
-	if (env->subprog_cnt == subprog + 1)
+	if (env->subprog_cnt == idx + 1)
 		subprog_end = insn_cnt;
 	else
-		subprog_end = env->subprog_starts[subprog + 1];
+		subprog_end = subprog[idx + 1].start;
 	for (; i < subprog_end; i++) {
 		if (insn[i].code != (BPF_JMP | BPF_CALL))
 			continue;
@@ -1523,12 +1525,12 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 			continue;
 		/* remember insn and function to return to */
 		ret_insn[frame] = i + 1;
-		ret_prog[frame] = subprog;
+		ret_prog[frame] = idx;
 
 		/* find the callee */
 		i = i + insn[i].imm + 1;
-		subprog = find_subprog(env, i);
-		if (subprog < 0) {
+		idx = find_subprog(env, i);
+		if (idx < 0) {
 			WARN_ONCE(1, "verifier bug. No program starts at insn %d\n",
 				  i);
 			return -EFAULT;
@@ -1545,10 +1547,10 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 	 */
 	if (frame == 0)
 		return 0;
-	depth -= round_up(max_t(u32, env->subprog_stack_depth[subprog], 1), 32);
+	depth -= round_up(max_t(u32, subprog[idx].stack_depth, 1), 32);
 	frame--;
 	i = ret_insn[frame];
-	subprog = ret_prog[frame];
+	idx = ret_prog[frame];
 	goto continue_func;
 }
 
@@ -1564,7 +1566,7 @@ static int get_callee_stack_depth(struct bpf_verifier_env *env,
 			  start);
 		return -EFAULT;
 	}
-	return env->subprog_stack_depth[subprog];
+	return env->subprog_info[subprog].stack_depth;
 }
 #endif
 
@@ -4855,14 +4857,14 @@ static int do_check(struct bpf_verifier_env *env)
 	verbose(env, "processed %d insns (limit %d), stack depth ",
 		insn_processed, BPF_COMPLEXITY_LIMIT_INSNS);
 	for (i = 0; i < env->subprog_cnt; i++) {
-		u32 depth = env->subprog_stack_depth[i];
+		u32 depth = env->subprog_info[i].stack_depth;
 
 		verbose(env, "%d", depth);
 		if (i + 1 < env->subprog_cnt)
 			verbose(env, "+");
 	}
 	verbose(env, "\n");
-	env->prog->aux->stack_depth = env->subprog_stack_depth[0];
+	env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
 	return 0;
 }
 
@@ -5069,9 +5071,9 @@ static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len
 	if (len == 1)
 		return;
 	for (i = 0; i < env->subprog_cnt; i++) {
-		if (env->subprog_starts[i] < off)
+		if (env->subprog_info[i].start < off)
 			continue;
-		env->subprog_starts[i] += len - 1;
+		env->subprog_info[i].start += len - 1;
 	}
 }
 
@@ -5269,7 +5271,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 		if (env->subprog_cnt == i + 1)
 			subprog_end = prog->len;
 		else
-			subprog_end = env->subprog_starts[i + 1];
+			subprog_end = env->subprog_info[i + 1].start;
 
 		len = subprog_end - subprog_start;
 		func[i] = bpf_prog_alloc(bpf_prog_size(len), GFP_USER);
@@ -5286,7 +5288,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 		 * Long term would need debug info to populate names
 		 */
 		func[i]->aux->name[0] = 'F';
-		func[i]->aux->stack_depth = env->subprog_stack_depth[i];
+		func[i]->aux->stack_depth = env->subprog_info[i].stack_depth;
 		func[i]->jit_requested = 1;
 		func[i] = bpf_int_jit_compile(func[i]);
 		if (!func[i]->jited) {
-- 
2.7.4

[PATCH bpf-next 3/3] bpf: add faked "ending" subprog

[Jiong Wang]

There are quite a few code snippet like the following in verifier:

       subprog_start = 0;
       if (env->subprog_cnt == cur_subprog + 1)
               subprog_end = insn_cnt;
       else
               subprog_end = env->subprog_info[cur_subprog + 1].start;

The reason is there is no marker in subprog_info array to tell the end of
it.

We could resolve this issue by introducing a faked "ending" subprog.
The special "ending" subprog is with "insn_cnt" as start offset, so it is
serving as the end mark whenever we iterate over all subprogs.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/verifier.c | 31 ++++++++++++-------------------
 1 file changed, 12 insertions(+), 19 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9764b9b..4a081e0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -766,7 +766,7 @@ static int add_subprog(struct bpf_verifier_env *env, int off)
 	ret = find_subprog(env, off);
 	if (ret >= 0)
 		return 0;
-	if (env->subprog_cnt > BPF_MAX_SUBPROGS) {
+	if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
 		verbose(env, "too many subprograms\n");
 		return -E2BIG;
 	}
@@ -807,16 +807,18 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			return ret;
 	}
 
+	/* Add a fake 'exit' subprog which could simplify subprog iteration
+	 * logic. 'subprog_cnt' should not be increased.
+	 */
+	subprog[env->subprog_cnt].start = insn_cnt;
+
 	if (env->log.level > 1)
 		for (i = 0; i < env->subprog_cnt; i++)
 			verbose(env, "func#%d @%d\n", i, subprog[i].start);
 
 	/* now check that all jumps are within the same subprog */
-	subprog_start = 0;
-	if (env->subprog_cnt == cur_subprog + 1)
-		subprog_end = insn_cnt;
-	else
-		subprog_end = subprog[cur_subprog + 1].start;
+	subprog_start = subprog[cur_subprog].start;
+	subprog_end = subprog[cur_subprog + 1].start;
 	for (i = 0; i < insn_cnt; i++) {
 		u8 code = insn[i].code;
 
@@ -840,11 +842,9 @@ static int check_subprogs(struct bpf_verifier_env *env)
 				verbose(env, "last insn is not an exit or jmp\n");
 				return -EINVAL;
 			}
-			cur_subprog++;
 			subprog_start = subprog_end;
-			if (env->subprog_cnt == cur_subprog + 1)
-				subprog_end = insn_cnt;
-			else
+			cur_subprog++;
+			if (cur_subprog < env->subprog_cnt)
 				subprog_end = subprog[cur_subprog + 1].start;
 		}
 	}
@@ -1499,7 +1499,6 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 	int depth = 0, frame = 0, idx = 0, i = 0, subprog_end;
 	struct bpf_subprog_info *subprog = env->subprog_info;
 	struct bpf_insn *insn = env->prog->insnsi;
-	int insn_cnt = env->prog->len;
 	int ret_insn[MAX_CALL_FRAMES];
 	int ret_prog[MAX_CALL_FRAMES];
 
@@ -1514,10 +1513,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 		return -EACCES;
 	}
 continue_func:
-	if (env->subprog_cnt == idx + 1)
-		subprog_end = insn_cnt;
-	else
-		subprog_end = subprog[idx + 1].start;
+	subprog_end = subprog[idx + 1].start;
 	for (; i < subprog_end; i++) {
 		if (insn[i].code != (BPF_JMP | BPF_CALL))
 			continue;
@@ -5268,10 +5264,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 
 	for (i = 0; i < env->subprog_cnt; i++) {
 		subprog_start = subprog_end;
-		if (env->subprog_cnt == i + 1)
-			subprog_end = prog->len;
-		else
-			subprog_end = env->subprog_info[i + 1].start;
+		subprog_end = env->subprog_info[i + 1].start;
 
 		len = subprog_end - subprog_start;
 		func[i] = bpf_prog_alloc(bpf_prog_size(len), GFP_USER);
-- 
2.7.4

Re: [PATCH bpf-next 0/3] bpf: cleanups on managing subprog information

[Alexei Starovoitov]

On Mon, Apr 30, 2018 at 06:28:13PM -0400, Jiong Wang wrote:
> 
> There is no functional change by this patch set.
> No bpf selftest regression found after this patch set.

I was about to apply them, but there is a regression:
[   27.773899] ==================================================================
[   27.774802] BUG: KASAN: slab-out-of-bounds in do_jit+0x5499/0x6020
[   27.775559] Read of size 4 at addr ffff8801197fe7f4 by task test_verifier/344
[   27.776412]
[   27.776607] CPU: 3 PID: 344 Comm: test_verifier Not tainted 4.17.0-rc2-00451-geb43cb64a84a #943
[   27.777644] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-1.el7.centos 04/01/2014
[   27.778894] Call Trace:
[   27.779217]  dump_stack+0x5b/0x8b
[   27.779675]  ? do_jit+0x5499/0x6020
[   27.780148]  print_address_description+0x73/0x290
[   27.780716]  ? do_jit+0x5499/0x6020
[   27.781152]  kasan_report+0x22b/0x350
[   27.781602]  do_jit+0x5499/0x6020
[   27.782020]  ? __mod_node_page_state+0xa2/0xd0
[   27.782557]  ? jit_fill_hole+0x20/0x20
[   27.783019]  ? ___slab_alloc+0x3e7/0x4d0
[   27.783498]  ? kasan_unpoison_shadow+0x30/0x40
[   27.784042]  ? kasan_kmalloc+0xa0/0xd0
[   27.784497]  ? __kmalloc+0x109/0x200
[   27.784931]  ? bpf_int_jit_compile+0x7ac/0xab0
[   27.785475]  bpf_int_jit_compile+0x2b6/0xab0
[   27.786001]  ? do_jit+0x6020/0x6020
[   27.786428]  ? kasan_kmalloc+0xa0/0xd0
[   27.786885]  bpf_check+0x2c05/0x4c40
[   27.787346]  ? fixup_bpf_calls+0x1140/0x1140
[   27.787865]  ? kasan_unpoison_shadow+0x30/0x40
[   27.788406]  ? kasan_kmalloc+0xa0/0xd0
[   27.788865]  ? memset+0x1f/0x40
[   27.789255]  ? bpf_obj_name_cpy+0x2d/0x200
[   27.789750]  bpf_prog_load+0xb07/0xeb0

simply running test_verifier with JIT and kasan on.

Re: [PATCH bpf-next 0/3] bpf: cleanups on managing subprog information

[Jiong Wang]

On 01/05/2018 23:22, Alexei Starovoitov wrote:
...
> [   27.784931]  ? bpf_int_jit_compile+0x7ac/0xab0
> [   27.785475]  bpf_int_jit_compile+0x2b6/0xab0
> [   27.786001]  ? do_jit+0x6020/0x6020
> [   27.786428]  ? kasan_kmalloc+0xa0/0xd0
> [   27.786885]  bpf_check+0x2c05/0x4c40
> [   27.787346]  ? fixup_bpf_calls+0x1140/0x1140
> [   27.787865]  ? kasan_unpoison_shadow+0x30/0x40
> [   27.788406]  ? kasan_kmalloc+0xa0/0xd0
> [   27.788865]  ? memset+0x1f/0x40
> [   27.789255]  ? bpf_obj_name_cpy+0x2d/0x200
> [   27.789750]  bpf_prog_load+0xb07/0xeb0
>
> simply running test_verifier with JIT and kasan on.

Ah, sorry, I should add "sysctl net/core/bpf_jit_enable=1" to my test
script, error reproduced.

convert_ctx_accesses and fixup_bpf_calls might insert ebpf insns that
prog->len would change.

The new fake "exit" subprog whose .start offset is prog->len should be
updated as well.

The "for" condition in adjust_subprog_starts:

   for (i = 0; i < env->subprog_cnt; i++) {

need to be changed into:

   for (i = 0; i <= env->subprog_cnt; i++) {

Will respin the patch set.

Thanks.

Regards,
Jiong

Re: [PATCH bpf-next 0/3] bpf: cleanups on managing subprog information

[John Fastabend]

On 05/02/2018 09:59 AM, Jiong Wang wrote:
> On 01/05/2018 23:22, Alexei Starovoitov wrote:
> ...
>> [   27.784931]  ? bpf_int_jit_compile+0x7ac/0xab0
>> [   27.785475]  bpf_int_jit_compile+0x2b6/0xab0
>> [   27.786001]  ? do_jit+0x6020/0x6020
>> [   27.786428]  ? kasan_kmalloc+0xa0/0xd0
>> [   27.786885]  bpf_check+0x2c05/0x4c40
>> [   27.787346]  ? fixup_bpf_calls+0x1140/0x1140
>> [   27.787865]  ? kasan_unpoison_shadow+0x30/0x40
>> [   27.788406]  ? kasan_kmalloc+0xa0/0xd0
>> [   27.788865]  ? memset+0x1f/0x40
>> [   27.789255]  ? bpf_obj_name_cpy+0x2d/0x200
>> [   27.789750]  bpf_prog_load+0xb07/0xeb0
>>
>> simply running test_verifier with JIT and kasan on.
> 
> Ah, sorry, I should add "sysctl net/core/bpf_jit_enable=1" to my test
> script, error reproduced.
> 
> convert_ctx_accesses and fixup_bpf_calls might insert ebpf insns that
> prog->len would change.
> 
> The new fake "exit" subprog whose .start offset is prog->len should be
> updated as well.
> 
> The "for" condition in adjust_subprog_starts:
> 
>   for (i = 0; i < env->subprog_cnt; i++) {
> 
> need to be changed into:
> 
>   for (i = 0; i <= env->subprog_cnt; i++) {
> 
> Will respin the patch set.
> 
> Thanks.
> 
> Regards,
> Jiong
> 

Also a bit of a nit, but if you are doing a respin. How about
consider renaming BPF_MAX_SUBPROGS -> BPF_MAX_PROGS. It will
make the naming more accurate and also avoid some diffs below
where changing '>=' to '>' is required.

@@ -191,7 +191,7 @@ struct bpf_verifier_env {
 	bool seen_direct_write;
 	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 	struct bpf_verifier_log log;
-	u32 subprog_starts[BPF_MAX_SUBPROGS];
+	u32 subprog_starts[BPF_MAX_SUBPROGS + 1];
 	/* computes the stack depth of each bpf function */
 	u16 subprog_stack_depth[BPF_MAX_SUBPROGS + 1];
 	u32 subprog_cnt;

Re: [PATCH bpf-next 0/3] bpf: cleanups on managing subprog information

[Jiong Wang]

On 02/05/2018 18:24, John Fastabend wrote:
> On 05/02/2018 09:59 AM, Jiong Wang wrote:
>> On 01/05/2018 23:22, Alexei Starovoitov wrote:
>> ...
>>> [   27.784931]  ? bpf_int_jit_compile+0x7ac/0xab0
>>> [   27.785475]  bpf_int_jit_compile+0x2b6/0xab0
>>> [   27.786001]  ? do_jit+0x6020/0x6020
>>> [   27.786428]  ? kasan_kmalloc+0xa0/0xd0
>>> [   27.786885]  bpf_check+0x2c05/0x4c40
>>> [   27.787346]  ? fixup_bpf_calls+0x1140/0x1140
>>> [   27.787865]  ? kasan_unpoison_shadow+0x30/0x40
>>> [   27.788406]  ? kasan_kmalloc+0xa0/0xd0
>>> [   27.788865]  ? memset+0x1f/0x40
>>> [   27.789255]  ? bpf_obj_name_cpy+0x2d/0x200
>>> [   27.789750]  bpf_prog_load+0xb07/0xeb0
>>>
>>> simply running test_verifier with JIT and kasan on.
>> Ah, sorry, I should add "sysctl net/core/bpf_jit_enable=1" to my test
>> script, error reproduced.
>>
>> convert_ctx_accesses and fixup_bpf_calls might insert ebpf insns that
>> prog->len would change.
>>
>> The new fake "exit" subprog whose .start offset is prog->len should be
>> updated as well.
>>
>> The "for" condition in adjust_subprog_starts:
>>
>>    for (i = 0; i < env->subprog_cnt; i++) {
>>
>> need to be changed into:
>>
>>    for (i = 0; i <= env->subprog_cnt; i++) {
>>
>> Will respin the patch set.
>>
>> Thanks.
>>
>> Regards,
>> Jiong
>>
> Also a bit of a nit, but if you are doing a respin. How about
> consider renaming BPF_MAX_SUBPROGS -> BPF_MAX_PROGS. It will
> make the naming more accurate and also avoid some diffs below
> where changing '>=' to '>' is required.

I have been pondering renaming BPF_MAX_SUBPROGS to other name like
what you suggested, but failed to convince myself, mostly due to there
are quite a few other variables etc that are using the "subprog" name
convention, so I am thinking use subprog is also fine as traditional
main prog/func is also a sub prog/func, it is just the entry one.

So I am thinking it might be not worth renaming everything related, and
tend to just keep it as is.

Thanks.

Regards,
Jiong

>
> @@ -191,7 +191,7 @@ struct bpf_verifier_env {
>   	bool seen_direct_write;
>   	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
>   	struct bpf_verifier_log log;
> -	u32 subprog_starts[BPF_MAX_SUBPROGS];
> +	u32 subprog_starts[BPF_MAX_SUBPROGS + 1];
>   	/* computes the stack depth of each bpf function */
>   	u16 subprog_stack_depth[BPF_MAX_SUBPROGS + 1];
>   	u32 subprog_cnt;