[RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

[RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

[Edward Cree]

By storing subprog boundaries as a subprogno mark on each insn, rather than
 a start (and implicit end) for each subprog, we collect a number of gains:
* More efficient determination of which subprog contains a given insn, and
  thus of find_subprog (which subprog begins at a given insn).
* Number of verifier passes is reduced, since most of the work is done in
  the main insn walk (do_check()).
* Subprogs no longer have to be contiguous; so long as they don't overlap
  and there are no unreachable insns, verifier is happy.  (This does require
  a small amount of care at jit_subprogs() time to fix up jump offsets, so
  we could instead disallow this if people prefer.)

Some other changes were also included to support this:
* Per-subprog info is stored in env->subprog_info, an array of structs,
  rather than several arrays with a common index.
* Call graph is now stored in the new bpf_subprog_info struct; used here for
  check_max_stack_depth() but may have other uses too.
* LD_ABS and LD_IND were previously disallowed in programs that also contain
  subprog calls.  Now they are only disallowed in callees, i.e. main() can
  always use them even if it also uses subprog calls.  AFAICT this is safe
  (main()'s r1 arg is still known to be ctx, so prologue can do its stuff).
  But again it can be disallowed if necessary.

Most tests in test_verifier pass (a few had to be changed to expect different
 failure messages), but there are a couple I wasn't quite sure what to do
 with - see comment on patch #2.

Edward Cree (2):
  bpf/verifier: validate func_calls by marking at do_check() time
  bpf/verifier: update selftests

 include/linux/bpf_verifier.h                |  24 +-
 kernel/bpf/verifier.c                       | 425 +++++++++++++++-------------
 tools/testing/selftests/bpf/test_verifier.c |  46 +--
 3 files changed, 271 insertions(+), 224 deletions(-)

[RFC PATCH bpf-next 1/2] bpf/verifier: validate func_calls by marking at do_check() time

[Edward Cree]

Removes a couple of passes from the verifier, one to check subprogs don't
 overlap etc., and one to compute max stack depth (which now is done by
 topologically sorting the call graph).

Signed-off-by: Edward Cree <ecree@solarflare.com>
---
 include/linux/bpf_verifier.h |  24 ++-
 kernel/bpf/verifier.c        | 425 +++++++++++++++++++++++--------------------
 2 files changed, 242 insertions(+), 207 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 6b66cd1aa0b9..0387e0c61161 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -146,6 +146,8 @@ struct bpf_insn_aux_data {
 		s32 call_imm;			/* saved imm field of call insn */
 	};
 	int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
+	u16 subprogno; /* subprog in which this insn resides, valid iff @seen */
+	u16 subprog_off; /* insn_idx within subprog, computed in jit_subprogs */
 	bool seen; /* this insn was processed by the verifier */
 };
 
@@ -168,6 +170,15 @@ static inline bool bpf_verifier_log_full(const struct bpf_verifer_log *log)
 
 #define BPF_MAX_SUBPROGS 256
 
+struct bpf_subprog_info {
+	/* which other subprogs does this one directly call? */
+	DECLARE_BITMAP(callees, BPF_MAX_SUBPROGS);
+	u32 start; /* insn idx of function entry point */
+	u16 stack_depth; /* max. stack depth used by this function */
+	u16 total_stack_depth; /* max. stack depth used by entire call chain */
+	u16 len; /* #insns in this subprog */
+};
+
 /* single container for all structs
  * one verifier_env per bpf_check() call
  */
@@ -186,20 +197,23 @@ struct bpf_verifier_env {
 	bool seen_direct_write;
 	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 	struct bpf_verifer_log log;
-	u32 subprog_starts[BPF_MAX_SUBPROGS];
-	/* 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];
 	u32 subprog_cnt;
 };
 
 __printf(2, 3) void bpf_verifier_log_write(struct bpf_verifier_env *env,
 					   const char *fmt, ...);
 
-static inline struct bpf_reg_state *cur_regs(struct bpf_verifier_env *env)
+static inline struct bpf_func_state *cur_frame(struct bpf_verifier_env *env)
 {
 	struct bpf_verifier_state *cur = env->cur_state;
 
-	return cur->frame[cur->curframe]->regs;
+	return cur->frame[cur->curframe];
+}
+
+static inline struct bpf_reg_state *cur_regs(struct bpf_verifier_env *env)
+{
+	return cur_frame(env)->regs;
 }
 
 int bpf_prog_offload_verifier_prep(struct bpf_verifier_env *env);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5fb69a85d967..2dc69fb3bfbe 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -728,111 +728,49 @@ enum reg_arg_type {
 	DST_OP_NO_MARK	/* same as above, check only, don't mark */
 };
 
-static int cmp_subprogs(const void *a, const void *b)
+static int find_subprog(struct bpf_verifier_env *env, int insn_idx)
 {
-	return *(int *)a - *(int *)b;
-}
-
-static int find_subprog(struct bpf_verifier_env *env, int off)
-{
-	u32 *p;
+	struct bpf_insn_aux_data *aux;
+	int insn_cnt = env->prog->len;
+	u32 subprogno;
 
-	p = bsearch(&off, env->subprog_starts, env->subprog_cnt,
-		    sizeof(env->subprog_starts[0]), cmp_subprogs);
-	if (!p)
+	if (insn_idx >= insn_cnt || insn_idx < 0) {
+		verbose(env, "find_subprog of invalid insn_idx %d\n", insn_idx);
+		return -EINVAL;
+	}
+	aux = &env->insn_aux_data[insn_idx];
+	if (!aux->seen) /* haven't visited this line yet */
 		return -ENOENT;
-	return p - env->subprog_starts;
-
+	subprogno = aux->subprogno;
+	/* validate that we are at start of subprog */
+	if (env->subprog_info[subprogno].start != insn_idx) {
+		verbose(env, "insn_idx %d is in subprog %u but that starts at %d\n",
+			insn_idx, subprogno, env->subprog_info[subprogno].start);
+		return -EINVAL;
+	}
+	return subprogno;
 }
 
 static int add_subprog(struct bpf_verifier_env *env, int off)
 {
 	int insn_cnt = env->prog->len;
+	struct bpf_subprog_info *info;
 	int ret;
 
 	if (off >= insn_cnt || off < 0) {
 		verbose(env, "call to invalid destination\n");
 		return -EINVAL;
 	}
-	ret = find_subprog(env, off);
-	if (ret >= 0)
-		return 0;
 	if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
 		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);
-	return 0;
-}
-
-static int check_subprogs(struct bpf_verifier_env *env)
-{
-	int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
-	struct bpf_insn *insn = env->prog->insnsi;
-	int insn_cnt = env->prog->len;
-
-	/* 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))
-			continue;
-		if (insn[i].src_reg != BPF_PSEUDO_CALL)
-			continue;
-		if (!env->allow_ptr_leaks) {
-			verbose(env, "function calls to other bpf functions are allowed for root only\n");
-			return -EPERM;
-		}
-		if (bpf_prog_is_dev_bound(env->prog->aux)) {
-			verbose(env, "function calls in offloaded programs are not supported yet\n");
-			return -EINVAL;
-		}
-		ret = add_subprog(env, i + insn[i].imm + 1);
-		if (ret < 0)
-			return ret;
-	}
-
-	if (env->log.level > 1)
-		for (i = 0; i < env->subprog_cnt; i++)
-			verbose(env, "func#%d @%d\n", i, env->subprog_starts[i]);
-
-	/* now check that all jumps are within the same subprog */
-	subprog_start = 0;
-	if (env->subprog_cnt == cur_subprog)
-		subprog_end = insn_cnt;
-	else
-		subprog_end = env->subprog_starts[cur_subprog++];
-	for (i = 0; i < insn_cnt; i++) {
-		u8 code = insn[i].code;
-
-		if (BPF_CLASS(code) != BPF_JMP)
-			goto next;
-		if (BPF_OP(code) == BPF_EXIT || BPF_OP(code) == BPF_CALL)
-			goto next;
-		off = i + insn[i].off + 1;
-		if (off < subprog_start || off >= subprog_end) {
-			verbose(env, "jump out of range from insn %d to %d\n", i, off);
-			return -EINVAL;
-		}
-next:
-		if (i == subprog_end - 1) {
-			/* to avoid fall-through from one subprog into another
-			 * the last insn of the subprog should be either exit
-			 * or unconditional jump back
-			 */
-			if (code != (BPF_JMP | BPF_EXIT) &&
-			    code != (BPF_JMP | BPF_JA)) {
-				verbose(env, "last insn is not an exit or jmp\n");
-				return -EINVAL;
-			}
-			subprog_start = subprog_end;
-			if (env->subprog_cnt == cur_subprog)
-				subprog_end = insn_cnt;
-			else
-				subprog_end = env->subprog_starts[cur_subprog++];
-		}
-	}
-	return 0;
+	ret = env->subprog_cnt++;
+	info = &env->subprog_info[ret];
+	info->start = off;
+	info->stack_depth = 0;
+	memset(info->callees, 0, sizeof(info->callees));
+	return ret;
 }
 
 static
@@ -1454,80 +1392,83 @@ 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];
+	struct bpf_subprog_info *info;
 
-	if (stack >= -off)
-		return 0;
+	if (!func) return -EFAULT;
+	if (func->subprogno >= BPF_MAX_SUBPROGS) return -E2BIG;
+	info = &env->subprog_info[func->subprogno];
 
 	/* update known max for given subprogram */
-	env->subprog_stack_depth[func->subprogno] = -off;
+	info->stack_depth = max_t(u16, info->stack_depth, -off);
 	return 0;
 }
 
-/* starting from main bpf function walk all instructions of the function
- * and recursively walk all callees that given function can call.
- * Ignore jump and exit insns.
- * Since recursion is prevented by check_cfg() this algorithm
- * only needs a local stack of MAX_CALL_FRAMES to remember callsites
+/* Topologically sort the call graph, and thereby determine the maximum stack
+ * depth of each subprog's worst-case call chain.  Store in total_stack_depth.
  */
 static int check_max_stack_depth(struct bpf_verifier_env *env)
 {
-	int depth = 0, frame = 0, subprog = 0, i = 0, subprog_end;
-	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];
-
-process_func:
-	/* 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);
-	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)
-		subprog_end = insn_cnt;
-	else
-		subprog_end = env->subprog_starts[subprog];
-	for (; i < subprog_end; i++) {
-		if (insn[i].code != (BPF_JMP | BPF_CALL))
-			continue;
-		if (insn[i].src_reg != BPF_PSEUDO_CALL)
-			continue;
-		/* remember insn and function to return to */
-		ret_insn[frame] = i + 1;
-		ret_prog[frame] = subprog;
-
-		/* find the callee */
-		i = i + insn[i].imm + 1;
-		subprog = find_subprog(env, i);
-		if (subprog < 0) {
-			WARN_ONCE(1, "verifier bug. No program starts at insn %d\n",
-				  i);
-			return -EFAULT;
+	DECLARE_BITMAP(frontier, BPF_MAX_SUBPROGS) = {0};
+	DECLARE_BITMAP(visited, BPF_MAX_SUBPROGS) = {0};
+	int subprog, i, j;
+
+	/* subprog 0 has no incoming edges, and should be the only such */
+	__set_bit(0, frontier);
+	env->subprog_info[0].total_stack_depth = env->subprog_info[0].stack_depth;
+
+	while (true) {
+		/* select a frontier node */
+		subprog = find_first_bit(frontier, BPF_MAX_SUBPROGS);
+		if (subprog >= BPF_MAX_SUBPROGS) /* frontier is empty, done */
+			break;
+		/* remove it from the frontier */
+		__clear_bit(subprog, frontier);
+		/* validate its total stack depth */
+		if (env->subprog_info[subprog].total_stack_depth > MAX_BPF_STACK) {
+			verbose(env, "combined stack size of calls to %d (at insn %d) is %d.  Too large\n",
+				subprog, env->subprog_info[subprog].start,
+				env->subprog_info[subprog].total_stack_depth);
+			return -EACCES;
 		}
-		subprog++;
-		frame++;
-		if (frame >= MAX_CALL_FRAMES) {
-			WARN_ONCE(1, "verifier bug. Call stack is too deep\n");
-			return -EFAULT;
+		if (env->log.level > 1) {
+			verbose(env, "combined stack size of calls to %d (at insn %d) is %d\n",
+				subprog, env->subprog_info[subprog].start,
+				env->subprog_info[subprog].total_stack_depth);
+		}
+		__set_bit(subprog, visited);
+		/* for each callee */
+		for_each_set_bit(i, env->subprog_info[subprog].callees,
+				 BPF_MAX_SUBPROGS) {
+			/* round up to 32-bytes, since this is granularity of
+			 * interpreter stack size
+			 */
+			u16 stack_depth = round_up(max_t(u16, env->subprog_info[i].stack_depth, 1), 32);
+
+			/* Update callee total stack depth */
+			env->subprog_info[i].total_stack_depth = max_t(u16,
+				env->subprog_info[i].total_stack_depth,
+				env->subprog_info[subprog].total_stack_depth +
+				stack_depth);
+			/* does it have unvisited callers? */
+			for_each_clear_bit(j, visited, env->subprog_cnt) {
+				if (test_bit(i, env->subprog_info[j].callees))
+					break;
+			}
+			/* if not, add it to the frontier */
+			if (j >= env->subprog_cnt)
+				__set_bit(i, frontier);
 		}
-		goto process_func;
 	}
-	/* end of for() loop means the last insn of the 'subprog'
-	 * was reached. Doesn't matter whether it was JA or EXIT
-	 */
-	if (frame == 0)
-		return 0;
-	depth -= round_up(max_t(u32, env->subprog_stack_depth[subprog], 1), 32);
-	frame--;
-	i = ret_insn[frame];
-	subprog = ret_prog[frame];
-	goto continue_func;
+
+	/* are any nodes left unvisited? */
+	subprog = find_first_zero_bit(visited, env->subprog_cnt);
+	if (subprog < env->subprog_cnt) {
+		/* then call graph is not acyclic, which shouldn't happen */
+		verbose(env, "verifier bug.  Call graph has a cycle including subprog %d (at insn %d)\n",
+			subprog, env->subprog_info[subprog].start);
+		return -EFAULT;
+	}
+	return 0;
 }
 
 #ifndef CONFIG_BPF_JIT_ALWAYS_ON
@@ -1542,8 +1483,7 @@ static int get_callee_stack_depth(struct bpf_verifier_env *env,
 			  start);
 		return -EFAULT;
 	}
-	subprog++;
-	return env->subprog_stack_depth[subprog];
+	return env->subprog_info[subprog].stack_depth;
 }
 #endif
 
@@ -2078,7 +2018,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;
 		}
@@ -2213,21 +2153,32 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 {
 	struct bpf_verifier_state *state = env->cur_state;
 	struct bpf_func_state *caller, *callee;
-	int i, subprog, target_insn;
+	int i, subprog, target;
 
 	if (state->curframe + 1 >= MAX_CALL_FRAMES) {
 		verbose(env, "the call stack of %d frames is too deep\n",
 			state->curframe + 2);
 		return -E2BIG;
 	}
-
-	target_insn = *insn_idx + insn->imm;
-	subprog = find_subprog(env, target_insn + 1);
-	if (subprog < 0) {
-		verbose(env, "verifier bug. No program starts at insn %d\n",
-			target_insn + 1);
-		return -EFAULT;
+	if (!env->allow_ptr_leaks) {
+		verbose(env, "function calls to other bpf functions are allowed for root only\n");
+		return -EPERM;
 	}
+	if (bpf_prog_is_dev_bound(env->prog->aux)) {
+		verbose(env, "function calls in offloaded programs are not supported yet\n");
+		return -EINVAL;
+	}
+
+
+	target = *insn_idx + insn->imm;
+	/* We will increment insn_idx (PC) in do_check() after handling this
+	 * call insn, so the actual start of the function is target + 1.
+	 */
+	subprog = find_subprog(env, target + 1);
+	if (subprog == -ENOENT)
+		subprog = add_subprog(env, target + 1);
+	if (subprog < 0)
+		return subprog;
 
 	caller = state->frame[state->curframe];
 	if (state->frame[state->curframe + 1]) {
@@ -2241,6 +2192,9 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		return -ENOMEM;
 	state->frame[state->curframe + 1] = callee;
 
+	/* record edge in call graph */
+	__set_bit(subprog, env->subprog_info[caller->subprogno].callees);
+
 	/* callee cannot access r0, r6 - r9 for reading and has to write
 	 * into its own stack before reading from it.
 	 * callee can read/write into caller's stack
@@ -2249,7 +2203,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++)
@@ -2265,7 +2219,7 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	state->curframe++;
 
 	/* and go analyze first insn of the callee */
-	*insn_idx = target_insn;
+	*insn_idx = target;
 
 	if (env->log.level) {
 		verbose(env, "caller:\n");
@@ -3807,13 +3761,15 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
 		return -EINVAL;
 	}
 
-	if (env->subprog_cnt) {
+	if (cur_frame(env)->subprogno) {
 		/* 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
 		 * for main prog as well since JITs would need to analyze
 		 * all functions in order to make proper register save/restore
-		 * decisions in the main prog. Hence disallow LD_ABS with calls
+		 * decisions in the main prog. Hence disallow LD_ABS with calls.
+		 * However, if we're the main-function (subprog 0) then we know
+		 * _we_ were called with r1 == ctx, so it's fine.
 		 */
 		verbose(env, "BPF_LD_[ABS|IND] instructions cannot be mixed with bpf-to-bpf calls\n");
 		return -EINVAL;
@@ -3995,10 +3951,6 @@ static int check_cfg(struct bpf_verifier_env *env)
 	int ret = 0;
 	int i, t;
 
-	ret = check_subprogs(env);
-	if (ret < 0)
-		return ret;
-
 	insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
 	if (!insn_state)
 		return -ENOMEM;
@@ -4521,6 +4473,7 @@ static int do_check(struct bpf_verifier_env *env)
 	int insn_cnt = env->prog->len, i;
 	int insn_idx, prev_insn_idx = 0;
 	int insn_processed = 0;
+	int mainprogno;
 	bool do_print_state = false;
 
 	state = kzalloc(sizeof(struct bpf_verifier_state), GFP_KERNEL);
@@ -4534,12 +4487,17 @@ static int do_check(struct bpf_verifier_env *env)
 		return -ENOMEM;
 	}
 	env->cur_state = state;
+	mainprogno = add_subprog(env, 0);
+	if (mainprogno < 0)
+		return mainprogno;
 	init_func_state(env, state->frame[0],
 			BPF_MAIN_FUNC /* callsite */,
 			0 /* frameno */,
-			0 /* subprogno, zero == main subprog */);
+			mainprogno /* subprogno */);
 	insn_idx = 0;
 	for (;;) {
+		struct bpf_insn_aux_data *aux = &env->insn_aux_data[insn_idx];
+		struct bpf_func_state *frame = cur_frame(env);
 		struct bpf_insn *insn;
 		u8 class;
 		int err;
@@ -4560,6 +4518,17 @@ static int do_check(struct bpf_verifier_env *env)
 			return -E2BIG;
 		}
 
+		/* check the insn doesn't appear in multiple subprogs, which
+		 * would imply bad function calls/returns/jumps
+		 */
+		if (aux->seen && aux->subprogno != frame->subprogno) {
+			verbose(env, "insn %d was in subprog %u, now %u\n",
+				insn_idx, aux->subprogno, frame->subprogno);
+			return -EINVAL;
+		}
+		aux->subprogno = frame->subprogno;
+		aux->seen = true;
+
 		err = is_state_visited(env, insn_idx);
 		if (err < 0)
 			return err;
@@ -4584,7 +4553,7 @@ static int do_check(struct bpf_verifier_env *env)
 			else
 				verbose(env, "\nfrom %d to %d:",
 					prev_insn_idx, insn_idx);
-			print_verifier_state(env, state->frame[state->curframe]);
+			print_verifier_state(env, frame);
 			do_print_state = false;
 		}
 
@@ -4605,7 +4574,6 @@ static int do_check(struct bpf_verifier_env *env)
 		}
 
 		regs = cur_regs(env);
-		env->insn_aux_data[insn_idx].seen = true;
 		if (class == BPF_ALU || class == BPF_ALU64) {
 			err = check_alu_op(env, insn);
 			if (err)
@@ -4821,7 +4789,15 @@ static int do_check(struct bpf_verifier_env *env)
 					return err;
 
 				insn_idx++;
-				env->insn_aux_data[insn_idx].seen = true;
+				/* Mark second half of LD_IMM64 insn */
+				aux++;
+				if (aux->seen && aux->subprogno != frame->subprogno) {
+					verbose(env, "insn %d was in subprog %u, now %u\n",
+						insn_idx, aux->subprogno, frame->subprogno);
+					return -EINVAL;
+				}
+				aux->subprogno = frame->subprogno;
+				aux->seen = true;
 			} else {
 				verbose(env, "invalid BPF_LD mode\n");
 				return -EINVAL;
@@ -4836,15 +4812,15 @@ 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++) {
-		u32 depth = env->subprog_stack_depth[i];
+	for (i = 0; i < env->subprog_cnt; i++) {
+		u32 depth = env->subprog_info[i].stack_depth;
 
-		verbose(env, "%d", depth);
-		if (i + 1 < env->subprog_cnt + 1)
+		if (i)
 			verbose(env, "+");
+		verbose(env, "%d", depth);
 	}
 	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;
 }
 
@@ -5037,8 +5013,10 @@ static int adjust_insn_aux_data(struct bpf_verifier_env *env, u32 prog_len,
 	memcpy(new_data, old_data, sizeof(struct bpf_insn_aux_data) * off);
 	memcpy(new_data + off + cnt - 1, old_data + off,
 	       sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
-	for (i = off; i < off + cnt - 1; i++)
+	for (i = off; i < off + cnt - 1; i++) {
 		new_data[i].seen = true;
+		new_data[i].subprogno = old_data[off].subprogno;
+	}
 	env->insn_aux_data = new_data;
 	vfree(old_data);
 	return 0;
@@ -5051,9 +5029,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;
 	}
 }
 
@@ -5212,15 +5190,19 @@ static int convert_ctx_accesses(struct bpf_verifier_env *env)
 static int jit_subprogs(struct bpf_verifier_env *env)
 {
 	struct bpf_prog *prog = env->prog, **func, *tmp;
-	int i, j, subprog_start, subprog_end = 0, len, subprog;
+	int i, j, subprog;
 	struct bpf_insn *insn;
 	void *old_bpf_func;
 	int err = -ENOMEM;
 
-	if (env->subprog_cnt == 0)
+	if (env->subprog_cnt <= 1)
 		return 0;
 
+	for (i = 0; i <= env->subprog_cnt; i++)
+		env->subprog_info[i].len = 0;
+
 	for (i = 0, insn = prog->insnsi; i < prog->len; i++, insn++) {
+		env->subprog_info[env->insn_aux_data[i].subprogno].len++;
 		if (insn->code != (BPF_JMP | BPF_CALL) ||
 		    insn->src_reg != BPF_PSEUDO_CALL)
 			continue;
@@ -5233,7 +5215,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
 		 */
@@ -5242,25 +5224,59 @@ 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++) {
-		subprog_start = subprog_end;
-		if (env->subprog_cnt == i)
-			subprog_end = prog->len;
-		else
-			subprog_end = env->subprog_starts[i];
+	for (i = 0; i < env->subprog_cnt; i++) {
+		struct bpf_subprog_info *info = &env->subprog_info[i];
+		int k = 0;
 
-		len = subprog_end - subprog_start;
-		func[i] = bpf_prog_alloc(bpf_prog_size(len), GFP_USER);
+		func[i] = bpf_prog_alloc(bpf_prog_size(info->len), GFP_USER);
 		if (!func[i])
 			goto out_free;
-		memcpy(func[i]->insnsi, &prog->insnsi[subprog_start],
-		       len * sizeof(struct bpf_insn));
+
+		for (j = 0; j < prog->len; j++) {
+			if (env->insn_aux_data[j].subprogno != i)
+				continue;
+			if (WARN_ON_ONCE(k >= info->len)) {
+				verbose(env, "Tried to add insn %d to subprog %d but previously counted %d\n",
+					k, i, info->len);
+				err = -EFAULT;
+				goto out_free;
+			}
+			env->insn_aux_data[j].subprog_off = k;
+			memcpy(func[i]->insnsi + k++, prog->insnsi + j,
+			       sizeof(struct bpf_insn));
+		}
+		if (WARN_ON_ONCE(k != info->len)) {
+			verbose(env, "Only %d insns in subprog %d but previously counted %d\n",
+				k, i, info->len);
+		}
+		/* Fix up jump offsets.  If a subprog was not contiguous, then
+		 * jumps within it need their offsets adjusting to account for
+		 * the insns that are not present in the subprog.
+		 */
+		for (j = 0; j < prog->len; j++) {
+			if (env->insn_aux_data[j].subprogno != i)
+				continue;
+			k = env->insn_aux_data[j].subprog_off;
+			insn = func[i]->insnsi + k;
+			if (BPF_CLASS(insn->code) == BPF_JMP &&
+			    BPF_OP(insn->code) != BPF_CALL &&
+			    BPF_OP(insn->code) != BPF_EXIT) {
+				/* This was a jump from orig[j] to orig[j+off+1]
+				 * which becomes a jump from new[k] to
+				 * new[aux[j+off+1].subprog_off]
+				 */
+				int t = env->insn_aux_data[j + insn->off + 1].subprog_off;
+
+				insn->off = t - k - 1;
+			}
+		}
+
 		func[i]->type = prog->type;
-		func[i]->len = len;
+		func[i]->len = info->len;
 		if (bpf_prog_calc_tag(func[i]))
 			goto out_free;
 		func[i]->is_func = 1;
@@ -5268,7 +5284,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) {
@@ -5281,7 +5297,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) ||
@@ -5289,12 +5305,16 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 				continue;
 			subprog = insn->off;
 			insn->off = 0;
+			if (subprog < 0 || subprog >= env->subprog_cnt) {
+				err = -EFAULT;
+				goto out_free;
+			}
 			insn->imm = (u64 (*)(u64, u64, u64, u64, u64))
 				func[subprog]->bpf_func -
 				__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) {
@@ -5308,7 +5328,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]);
 	}
@@ -5325,7 +5345,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;
@@ -5334,10 +5354,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);
@@ -5367,6 +5387,7 @@ static int fixup_call_args(struct bpf_verifier_env *env)
 		err = jit_subprogs(env);
 		if (err == 0)
 			return 0;
+		verbose(env, "failed to jit_subprogs %d\n", err);
 	}
 #ifndef CONFIG_BPF_JIT_ALWAYS_ON
 	for (i = 0; i < prog->len; i++, insn++) {

[RFC PATCH bpf-next 2/2] bpf/verifier: update selftests

[Edward Cree]

Error messages for some bad programs have changed, partly because we now
 check for loops / out-of-bounds jumps before checking subprogs.

Problematic selftests:
513 calls: wrong recursive calls
 This is now rejected with 'unreachable insn 1'.  I'm not entirely sure what
 it was meant to do/test, since all of the JMP|CALLs are also unreachable.
546 calls: ld_abs with changing ctx data in callee
 Rejected with R1 !read_ok.  It was testing for the "can't mix LD_ABS with
 function calls", which has now changed to "can't use LD_ABS in functions
 other than main()".  I'm still not 100% sure that's right though.

Signed-off-by: Edward Cree <ecree@solarflare.com>
---
 tools/testing/selftests/bpf/test_verifier.c | 46 ++++++++++++++++++-----------
 1 file changed, 29 insertions(+), 17 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 697bd83de295..9c7531887ee3 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -644,7 +644,7 @@ static struct bpf_test tests[] = {
 		.insns = {
 			BPF_ALU64_REG(BPF_MOV, BPF_REG_0, BPF_REG_2),
 		},
-		.errstr = "not an exit",
+		.errstr = "jump out of range",
 		.result = REJECT,
 	},
 	{
@@ -9288,7 +9288,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "last insn is not an exit or jmp",
+		.errstr = "insn 1 was in subprog 1, now 0",
 		.result = REJECT,
 	},
 	{
@@ -9354,7 +9354,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "jump out of range",
+		.errstr = "insn 5 was in subprog 1, now 0",
 		.result = REJECT,
 	},
 	{
@@ -9633,7 +9633,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_SCHED_CLS,
-		.errstr = "jump out of range from insn 1 to 4",
+		.errstr = "insn 5 was in subprog 1, now 0",
 		.result = REJECT,
 	},
 	{
@@ -9649,13 +9649,12 @@ static struct bpf_test tests[] = {
 			BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_0),
 			BPF_MOV64_REG(BPF_REG_0, BPF_REG_7),
 			BPF_EXIT_INSN(),
-			BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1,
-				    offsetof(struct __sk_buff, len)),
+			BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, 8),
 			BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, -3),
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "jump out of range from insn 11 to 9",
+		.errstr = "insn 9 was in subprog 1, now 2",
 		.result = REJECT,
 	},
 	{
@@ -9707,7 +9706,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "invalid destination",
+		.errstr = "jump out of range from insn 2 to -1",
 		.result = REJECT,
 	},
 	{
@@ -9719,7 +9718,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "invalid destination",
+		.errstr = "jump out of range from insn 2 to -2147483646",
 		.result = REJECT,
 	},
 	{
@@ -9732,7 +9731,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "jump out of range",
+		.errstr = "insn 1 was in subprog 0, now 1",
 		.result = REJECT,
 	},
 	{
@@ -9745,7 +9744,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "jump out of range",
+		.errstr = "insn 4 was in subprog 1, now 0",
 		.result = REJECT,
 	},
 	{
@@ -9759,7 +9758,7 @@ static struct bpf_test tests[] = {
 			BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, -2),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "not an exit",
+		.errstr = "jump out of range from insn 5 to 6",
 		.result = REJECT,
 	},
 	{
@@ -9773,7 +9772,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "last insn",
+		.errstr = "insn_idx 5 is in subprog 1 but that starts at 4",
 		.result = REJECT,
 	},
 	{
@@ -9788,7 +9787,7 @@ static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "last insn",
+		.errstr = "insn_idx 5 is in subprog 1 but that starts at 4",
 		.result = REJECT,
 	},
 	{
@@ -9828,12 +9827,11 @@ static struct bpf_test tests[] = {
 			BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_0),
 			BPF_MOV64_REG(BPF_REG_0, BPF_REG_7),
 			BPF_MOV64_REG(BPF_REG_0, BPF_REG_0),
-			BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1,
-				    offsetof(struct __sk_buff, len)),
+			BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, 8),
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "not an exit",
+		.errstr = "insn 10 was in subprog 2, now 1",
 		.result = REJECT,
 	},
 	{
@@ -11073,6 +11071,20 @@ static struct bpf_test tests[] = {
 		.prog_type = BPF_PROG_TYPE_XDP,
 	},
 	{
+		"calls: interleaved functions",
+		.insns = {
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 2),
+			BPF_MOV64_IMM(BPF_REG_0, 1),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 2),
+			BPF_MOV64_IMM(BPF_REG_0, 2),
+			BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+			BPF_EXIT_INSN(),
+			BPF_EXIT_INSN(),
+		},
+		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
+		.result = ACCEPT,
+	},
+	{
 		"search pruning: all branches should be verified (nop operation)",
 		.insns = {
 			BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),

Re: [RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

[Alexei Starovoitov]

On Thu, Feb 08, 2018 at 07:31:55PM +0000, Edward Cree wrote:
> By storing subprog boundaries as a subprogno mark on each insn, rather than
>  a start (and implicit end) for each subprog, we collect a number of gains:
> * More efficient determination of which subprog contains a given insn, and
>   thus of find_subprog (which subprog begins at a given insn).
> * Number of verifier passes is reduced, since most of the work is done in
>   the main insn walk (do_check()).

unfortunately this is the opposite of where the verifier should be heading.
For bpf libraries and indirect call support the verifier has to be further
split into more distinct passes. Not less. Since it needs to determine
function boundaries and general validity of the instructions without
performing do_check()-style walk.
The function in the given prog may be called by other bpf functions that will be
loaded later and just like indirect calls the final 'check all pointers
and load/stores' pass (currently done by do_check) will done last.
(In case of indirect calls this pass will done at the time of
bpf_map_update() call)
while all preparatory passes like function boundaries, basic block
detection, control flow check and general instruction sanity will
be done before that final run-time linking phase.
Hence we cannot merge subprog detection pass with anything else.
It has to be done first.

> * Subprogs no longer have to be contiguous; so long as they don't overlap
>   and there are no unreachable insns, verifier is happy.  (This does require
>   a small amount of care at jit_subprogs() time to fix up jump offsets, so
>   we could instead disallow this if people prefer.)

do you have patches to make llvm blend multiple C functions into
non-contiguous piece of .text code ? What would be the purpose of
such bizarre code generation?
If not, there is no reason to support such code layout in the verifier.

> Some other changes were also included to support this:
> * Per-subprog info is stored in env->subprog_info, an array of structs,
>   rather than several arrays with a common index.
> * Call graph is now stored in the new bpf_subprog_info struct; used here for
>   check_max_stack_depth() but may have other uses too.

The new maximum stack depth algorithm is interesting, but it looks
unrelated to the rest and much harder to understand
comparing to existing check_max_stack_depth() algorithm.
The patches must explain the benefits clearly. Currently it's not the case.

> * LD_ABS and LD_IND were previously disallowed in programs that also contain
>   subprog calls.  Now they are only disallowed in callees, i.e. main() can
>   always use them even if it also uses subprog calls.  AFAICT this is safe
>   (main()'s r1 arg is still known to be ctx, so prologue can do its stuff).
>   But again it can be disallowed if necessary.

What is the purpose of allowing ld_abs in calls ?
The work over the last years have been to avoid ld_abs as much as possible,
since these instructions are slow, carry a lot of legacy baggage and corner cases
that cause JITs and verifier to do additional work and make every piece more complex.
Allowing ld_abs with calls is going into the opposite direction.
Personally I very much dislike patches that "lets do this just because".
Nothing in the patch 1 or in this cover letter explain the reason.

Overall I think the set is more harmful than useful.

If you like to help developing bpf infrastructure please focus
on replacing signed/unsigned min/max tracking logic with simpler and safer logic.
1. [su]minmax burning memory and making verifier process slower
2. it's internally inconsistent, since it can determine that smin > smax.
   We had to remove that WARN_ON, but underlying issue remains.
3. it had been source of security bugs
4. The reason it was introduced was to verify validity of variable length
   array access, but it can be done much simpler instead.
We're dealing with C compiled code here and C arrays have zero till N range.
There is no reason to track that a variable can be between -100 to -10.
This tracking is a waste of verifier resources for realistic C programs.
All of [su]minmax can be replaced with {u32_max_value, can_be_zero, can_be_negative}
tracking which is 4 bytes and 2 bits of info per bpf_reg_state instead of 32 bytes.
Such tracking will be more accurate as well.
llvm can optimize 'var >= 1' compare into 'var != 0' and we've seen
cases that this optimization breaks minmax tracking, since !=0 simply
doesn't fit into minmax logic. One can argue reg_set_min_max() needs to track
this extra boolean state as well, but then it would mean more inconsistency
in the bpf_reg_state and information contradicting each other.
Any verifier pass looking at bpf_reg_state at any given time should
see bpf_reg_state being valid and not guessing why smin is suddenly more
than smax.

Re: [RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

[Edward Cree]

On 10/02/18 03:18, Alexei Starovoitov wrote:
> On Thu, Feb 08, 2018 at 07:31:55PM +0000, Edward Cree wrote:
>> By storing subprog boundaries as a subprogno mark on each insn, rather than
>>  a start (and implicit end) for each subprog, we collect a number of gains:
>> * More efficient determination of which subprog contains a given insn, and
>>   thus of find_subprog (which subprog begins at a given insn).
>> * Number of verifier passes is reduced, since most of the work is done in
>>   the main insn walk (do_check()).
> unfortunately this is the opposite of where the verifier should be heading.
> For bpf libraries and indirect call support the verifier has to be further
> split into more distinct passes. Not less. Since it needs to determine
> function boundaries and general validity of the instructions without
> performing do_check()-style walk.
> The function in the given prog may be called by other bpf functions that will be
> loaded later and just like indirect calls the final 'check all pointers
> and load/stores' pass (currently done by do_check) will done last.
Strictly speaking, any kind of sanity check done before the program can be
 do_check() walked can only be a kind of early-fail optimisation, because
 the final 'check pointers and load/stores' (and register types in general,
 and any data value tracking we may use for bounded loops) can depend on
 values returned from callees.
So I am tempted to suggest that any such 'early sanity passes' should be in
 addition to, rather than instead of, checks at walk time.
> (In case of indirect calls this pass will done at the time of
> bpf_map_update() call)
Btw I hope you're planning to only have these maps writable by the control
 plane, and not from within BPF programs themselves; allowing BPF execution
 to trigger a verifier run would be... interesting.

> while all preparatory passes like function boundaries, basic block
> detection, control flow check and general instruction sanity will
> be done before that final run-time linking phase.
> Hence we cannot merge subprog detection pass with anything else.
> It has to be done first.
Why does it *have* to be done first?  Why would a verifier that postponed
 all checks until the complete prog was available be actually wrong?

>> * Subprogs no longer have to be contiguous; so long as they don't overlap
>>   and there are no unreachable insns, verifier is happy.  (This does require
>>   a small amount of care at jit_subprogs() time to fix up jump offsets, so
>>   we could instead disallow this if people prefer.)
> do you have patches to make llvm blend multiple C functions into
> non-contiguous piece of .text code ?
I have an assembler that produces eBPF object files.  I can make whatever
 crazy .text I want ;-)
> What would be the purpose of such bizarre code generation?
> If not, there is no reason to support such code layout in the verifier.
But the real reason is that disallowing it would have required writing an
 extra check, and I wanted to get a first prototype out for discussion ASAP.

>> Some other changes were also included to support this:
>> * Per-subprog info is stored in env->subprog_info, an array of structs,
>>   rather than several arrays with a common index.
>> * Call graph is now stored in the new bpf_subprog_info struct; used here for
>>   check_max_stack_depth() but may have other uses too.
> The new maximum stack depth algorithm is interesting, but it looks
> unrelated to the rest and much harder to understand
It's basically Kahn's algorithm from https://en.wikipedia.org/wiki/Topological_sorting
 if that helps?  I could perhaps explain that more fully in comments.
> comparing to existing check_max_stack_depth() algorithm.
> The patches must explain the benefits clearly. Currently it's not the case.
The benefit here, which indeed I didn't clearly explain, is that we replace
 a full recursive-walk pass with an algorithm that's O(n) in the number of
 subprogs.

>> * LD_ABS and LD_IND were previously disallowed in programs that also contain
>>   subprog calls.  Now they are only disallowed in callees, i.e. main() can
>>   always use them even if it also uses subprog calls.  AFAICT this is safe
>>   (main()'s r1 arg is still known to be ctx, so prologue can do its stuff).
>>   But again it can be disallowed if necessary.
> What is the purpose of allowing ld_abs in calls ?
> The work over the last years have been to avoid ld_abs as much as possible,
> since these instructions are slow, carry a lot of legacy baggage and corner cases
> that cause JITs and verifier to do additional work and make every piece more complex.
> Allowing ld_abs with calls is going into the opposite direction.
> Personally I very much dislike patches that "lets do this just because".
> Nothing in the patch 1 or in this cover letter explain the reason.
Again, it was because it was more effort to forbid than allow (if we walk a
 ld_abs before the first call, we don't know yet that calls are coming, so
 I'd need to do something like recording in check_cfg that a call was seen)
 and I wanted to get the prototype out there.
There are more patches coming, btw; I am not just doing a random collection
 of changes but rather working towards a prototype implementation of bounded
 loops.  (I also have a 'parent-pointer-per-reg' patch, passing tests, in the
 series.  That cuts out 100 lines!)  While it's probably different to the way
 you're planning/expecting them to be handled, I think it's worth having both
 approaches to compare.  There's a reason this series is marked RFC ;-)

> Overall I think the set is more harmful than useful.
>
> If you like to help developing bpf infrastructure please focus
> on replacing signed/unsigned min/max tracking logic with simpler and safer logic.
If you like to keep bringing up [su]minmax tracking, please focus on
 answering the points I've repeatedly raised about the alternatives being
 confusing and complicated (due to asymmetry) which leads (and historically
 led) to them being buggy.

> 1. [su]minmax burning memory and making verifier process slower
Memory is cheap.  Do you have numbers that show it's a problem in the real
 world for someone, or are you committing premature optimisation?  (Even
 with (say) 4k explored_states * 11 regs, it's only 1.4MB.  All this fuss
 over just those 32 bytes per reg... it probably takes more memory just to
 store all our arguments about [su]minmax.)
> 2. it's internally inconsistent, since it can determine that smin > smax.
>    We had to remove that WARN_ON, but underlying issue remains.
IIRC the old tracking could do the same; if you did two JSGTs you could get
 a branch where min_value > max_value.  This is a natural result of
 following such 'impossible' branches, in no sense specific to [su]minmax.

> 3. it had been source of security bugs
So had the alternative, whose bugs stayed hidden for longer because of the
 inelegant, asymmetric complexity of the code.

> 4. The reason it was introduced was to verify validity of variable length
>    array access, but it can be done much simpler instead.
> We're dealing with C compiled code here and C arrays have zero till N range.
> There is no reason to track that a variable can be between -100 to -10.
But there is reason to track whether a bound came from a signed or an
 unsigned compare, and I don't see why it should be a point against the
 _clean_ implementation that it happens to also support unusual things.
> This tracking is a waste of verifier resources for realistic C programs.
And what if someone subtracts a variable with a min_value from another, and
 the min_value is necessary to prove the access safe?  I suppose that's
 'unrealistic', up until the day that someone wants to do it.
Also, my design for bounded loops really does need a min_value in order to
 handle an increasing loop counter.

> All of [su]minmax can be replaced with {u32_max_value, can_be_zero, can_be_negative}
> tracking which is 4 bytes and 2 bits of info per bpf_reg_state instead of 32 bytes.
> Such tracking will be more accurate as well.
> llvm can optimize 'var >= 1' compare into 'var != 0' and we've seen
> cases that this optimization breaks minmax tracking, since !=0 simply
> doesn't fit into minmax logic. One can argue reg_set_min_max() needs to track
> this extra boolean state as well,
Well, if real-world programs are hitting this and need it, then yes,
 handling for jeq/jne 0 should be changed to give umin >= 1.

> but then it would mean more inconsistency
> in the bpf_reg_state and information contradicting each other.
> Any verifier pass looking at bpf_reg_state at any given time should
> see bpf_reg_state being valid and not guessing why smin is suddenly more
> than smax.
Again, nothing to do with [su]minmax, your approach could have a state in
 which max_value=0 and can_be_zero is false, for the exact same reason.

-Ed

Re: [RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

[John Fastabend]

On 02/12/2018 02:22 AM, Edward Cree wrote:
> On 10/02/18 03:18, Alexei Starovoitov wrote:
>> On Thu, Feb 08, 2018 at 07:31:55PM +0000, Edward Cree wrote:
>>> By storing subprog boundaries as a subprogno mark on each insn, rather than
>>>  a start (and implicit end) for each subprog, we collect a number of gains:
>>> * More efficient determination of which subprog contains a given insn, and
>>>   thus of find_subprog (which subprog begins at a given insn).
>>> * Number of verifier passes is reduced, since most of the work is done in
>>>   the main insn walk (do_check()).
>> unfortunately this is the opposite of where the verifier should be heading.
>> For bpf libraries and indirect call support the verifier has to be further
>> split into more distinct passes. Not less. Since it needs to determine
>> function boundaries and general validity of the instructions without
>> performing do_check()-style walk.
>> The function in the given prog may be called by other bpf functions that will be
>> loaded later and just like indirect calls the final 'check all pointers
>> and load/stores' pass (currently done by do_check) will done last.
> Strictly speaking, any kind of sanity check done before the program can be
>  do_check() walked can only be a kind of early-fail optimisation, because
>  the final 'check pointers and load/stores' (and register types in general,
>  and any data value tracking we may use for bounded loops) can depend on
>  values returned from callees.

But all the control flow analysis can be done before actual values are known.
Also for bounded loops the required restrictions on values can be known.

> So I am tempted to suggest that any such 'early sanity passes' should be in
>  addition to, rather than instead of, checks at walk time.

Disagree. We can verify control flow early. I view this similar to gcc and
LLVM except instead of optimizing passes we need have verification passes.

>> (In case of indirect calls this pass will done at the time of
>> bpf_map_update() call)
> Btw I hope you're planning to only have these maps writable by the control
>  plane, and not from within BPF programs themselves; allowing BPF execution
>  to trigger a verifier run would be... interesting.
> 
>> while all preparatory passes like function boundaries, basic block
>> detection, control flow check and general instruction sanity will
>> be done before that final run-time linking phase.
>> Hence we cannot merge subprog detection pass with anything else.
>> It has to be done first.
> Why does it *have* to be done first?  Why would a verifier that postponed
>  all checks until the complete prog was available be actually wrong?
> 

I think this is more to keep the code reasonable and understandable. Also
delaying basic block detection and loop detection doesn't seem correct to
me nor really practical. Lots of CFG analysis doesn't care about data values
and I don't see any way to do this inline with the existing passes. Adding
it after is dangerous because the verifier would have to avoid looping or
otherwise tripping up over invalid CFGs.

>>> * Subprogs no longer have to be contiguous; so long as they don't overlap
>>>   and there are no unreachable insns, verifier is happy.  (This does require
>>>   a small amount of care at jit_subprogs() time to fix up jump offsets, so
>>>   we could instead disallow this if people prefer.)
>> do you have patches to make llvm blend multiple C functions into
>> non-contiguous piece of .text code ?
> I have an assembler that produces eBPF object files.  I can make whatever
>  crazy .text I want ;-)

But that doesn't mean the verifier has to support it. I think we can make
the trade-off between simplifying the verifier and trying to handle problematic
code patterns if they are not common. ;)

>> What would be the purpose of such bizarre code generation?
>> If not, there is no reason to support such code layout in the verifier.
> But the real reason is that disallowing it would have required writing an
>  extra check, and I wanted to get a first prototype out for discussion ASAP.
> 

Will need to look over the code again.

>>> Some other changes were also included to support this:
>>> * Per-subprog info is stored in env->subprog_info, an array of structs,
>>>   rather than several arrays with a common index.
>>> * Call graph is now stored in the new bpf_subprog_info struct; used here for
>>>   check_max_stack_depth() but may have other uses too.
>> The new maximum stack depth algorithm is interesting, but it looks
>> unrelated to the rest and much harder to understand
> It's basically Kahn's algorithm from https://en.wikipedia.org/wiki/Topological_sorting
>  if that helps?  I could perhaps explain that more fully in comments.
>> comparing to existing check_max_stack_depth() algorithm.
>> The patches must explain the benefits clearly. Currently it's not the case.
> The benefit here, which indeed I didn't clearly explain, is that we replace
>  a full recursive-walk pass with an algorithm that's O(n) in the number of
>  subprogs.
> 
>>> * LD_ABS and LD_IND were previously disallowed in programs that also contain
>>>   subprog calls.  Now they are only disallowed in callees, i.e. main() can
>>>   always use them even if it also uses subprog calls.  AFAICT this is safe
>>>   (main()'s r1 arg is still known to be ctx, so prologue can do its stuff).
>>>   But again it can be disallowed if necessary.
>> What is the purpose of allowing ld_abs in calls ?
>> The work over the last years have been to avoid ld_abs as much as possible,
>> since these instructions are slow, carry a lot of legacy baggage and corner cases
>> that cause JITs and verifier to do additional work and make every piece more complex.
>> Allowing ld_abs with calls is going into the opposite direction.
>> Personally I very much dislike patches that "lets do this just because".
>> Nothing in the patch 1 or in this cover letter explain the reason.
> Again, it was because it was more effort to forbid than allow (if we walk a
>  ld_abs before the first call, we don't know yet that calls are coming, so
>  I'd need to do something like recording in check_cfg that a call was seen)
>  and I wanted to get the prototype out there.
> There are more patches coming, btw; I am not just doing a random collection
>  of changes but rather working towards a prototype implementation of bounded
>  loops.  (I also have a 'parent-pointer-per-reg' patch, passing tests, in the
>  series.  That cuts out 100 lines!)  While it's probably different to the way
>  you're planning/expecting them to be handled, I think it's worth having both
>  approaches to compare.  There's a reason this series is marked RFC ;-)
> 
>> Overall I think the set is more harmful than useful.
>>
>> If you like to help developing bpf infrastructure please focus
>> on replacing signed/unsigned min/max tracking logic with simpler and safer logic.
> If you like to keep bringing up [su]minmax tracking, please focus on
>  answering the points I've repeatedly raised about the alternatives being
>  confusing and complicated (due to asymmetry) which leads (and historically
>  led) to them being buggy.
> 
>> 1. [su]minmax burning memory and making verifier process slower
> Memory is cheap.  Do you have numbers that show it's a problem in the real
>  world for someone, or are you committing premature optimisation?  (Even
>  with (say) 4k explored_states * 11 regs, it's only 1.4MB.  All this fuss
>  over just those 32 bytes per reg... it probably takes more memory just to
>  store all our arguments about [su]minmax.)
>> 2. it's internally inconsistent, since it can determine that smin > smax.
>>    We had to remove that WARN_ON, but underlying issue remains.
> IIRC the old tracking could do the same; if you did two JSGTs you could get
>  a branch where min_value > max_value.  This is a natural result of
>  following such 'impossible' branches, in no sense specific to [su]minmax.
> 
>> 3. it had been source of security bugs
> So had the alternative, whose bugs stayed hidden for longer because of the
>  inelegant, asymmetric complexity of the code.
> 
>> 4. The reason it was introduced was to verify validity of variable length
>>    array access, but it can be done much simpler instead.
>> We're dealing with C compiled code here and C arrays have zero till N range.
>> There is no reason to track that a variable can be between -100 to -10.
> But there is reason to track whether a bound came from a signed or an
>  unsigned compare, and I don't see why it should be a point against the
>  _clean_ implementation that it happens to also support unusual things.
>> This tracking is a waste of verifier resources for realistic C programs.
> And what if someone subtracts a variable with a min_value from another, and
>  the min_value is necessary to prove the access safe?  I suppose that's
>  'unrealistic', up until the day that someone wants to do it.
> Also, my design for bounded loops really does need a min_value in order to
>  handle an increasing loop counter.

I have some code that is getting close to working on bounded loops. Here
is how I think it should work, (with some annotations on what I have).

1. First task is to ensure all loops are natural loops. A natural loop is
   just a loop that doesn't have any jumps into the middle of the loop, only
   a single entry point. Necessary condition to find induction variables
   later, at least without making things overly complex.

   The more precise definition, the natural loop of back edge a->b is {b}
   plus nodes {n_0,..., n_i} that can reach a without going through b.

   To find these we do the following

   1.a: Build the CFG of all the instructions so we can walk around the
        program easily.
   1.b: Find the basic blocks and build the basic block CFG. After this
        with a few helper calls we can move around the CFG both at block
        level and insn level.
   1.c: Build the dom tree and post dom tree. This is a data structure that
        allows us to actually find the natural loops. I can write more about
        this later.
   1.d: Using the post dom tree verify all the CFG loops are in fact
        natural loops. I made some simplifications here and threw
        out loops that have multiple jumps to the header node and nested
        loops for now. Both can be handled with some additional complexity.

  Versions of the above can be found in gcc and llvm so it appears to be
  fairly regular stuff from the compiler side. For LLVM the passes are
  --loops, --postdomtree. I dumped the various CFG into dot format and
  and graphed them for fun. The above seemed to work fine and rejected the
  small set of "bad" programs I threw at it.

2. Next on the list is to find all the induction variables. These are variables
   of the form `i = i + c` where 'c' is a constant in this case. Its easy
   to get carried away here and let `c` be all sorts of things linear expressions,
   or other induction variables. But requiring it to be a constant simplifies
   the problem a lot and is still very useful.

   Then ensure that the loop variable is a loop induction variable e.g. its
   just one of the values found above.

   Couple comments, the decreasing case can also be handled without much trouble
   I just didn't bother yet, `i = i - c`. Also the 'i = i + c` can not be inside
   a CFG that can be skipped e.g. if/else logic.

3. Finally, ensure the comparison is JGT with a constant. Of course that is just
   one case all the other cases could probably be added as well with case
   analysis. Also it doesn't need to be a constant if it is bounded but starting
   with constant first and then relaxing the constraints later seems like a good
   start to me.

OK, 2,3, are more of a rough sketch, but I can probably get a prototype out in
a few weeks. I need to get some sockmap code out in the next days so busy this
week. Perhaps this weekend. The code currently does 1 and 2 above, where 1 is
tested reasonably well, 2 less so and finally 3 is just a sketch and untested.

 4. The last step is we need some worst case analysis to ensure the loop although
    eventually terminating is not too long. This I've not done much with yet. Here
    is where I guess min values will be useful. The worst case loop count would
    be, `c - min_value` then `(c - min_value) * max(loop_cfg(i))` would be the
    the worst case instruction that might be executed. Where loop_cfg(i) is the
    max insns that can be run through the loop with worst case CFG path. 

I think logically the above is about what we should aim for.

> 
>> All of [su]minmax can be replaced with {u32_max_value, can_be_zero, can_be_negative}
>> tracking which is 4 bytes and 2 bits of info per bpf_reg_state instead of 32 bytes.
>> Such tracking will be more accurate as well.
>> llvm can optimize 'var >= 1' compare into 'var != 0' and we've seen
>> cases that this optimization breaks minmax tracking, since !=0 simply
>> doesn't fit into minmax logic. One can argue reg_set_min_max() needs to track
>> this extra boolean state as well,
> Well, if real-world programs are hitting this and need it, then yes,
>  handling for jeq/jne 0 should be changed to give umin >= 1.
> 
>> but then it would mean more inconsistency
>> in the bpf_reg_state and information contradicting each other.
>> Any verifier pass looking at bpf_reg_state at any given time should
>> see bpf_reg_state being valid and not guessing why smin is suddenly more
>> than smax.
> Again, nothing to do with [su]minmax, your approach could have a state in
>  which max_value=0 and can_be_zero is false, for the exact same reason.
> 
> -Ed
> 

Re: [RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

[Edward Cree]

On 13/02/18 05:09, John Fastabend wrote:
> I have some code that is getting close to working on bounded loops. Here
> is how I think it should work, (with some annotations on what I have).
Thanks for this!  For comparison, since my code is also 'getting close to
 working' here's how my approach works.

First, we get rid of (most of) check_cfg().  Replace it with a function
 that just puts the state-list marks on jump targets (including following-
 insns of conditional jumps and calls), then does a quick check that every
 insn following any JMP-class insn has a state-list mark (this suffices to
 detect statically-unreachable code).  2*O(n) in insn_cnt, and much easier
 to understand than check_cfg (I only recently figured out that it's also
 a topological sort algorithm).

Now of course at this point there is nothing to prevent loops at all, so in
 is_state_visited we now add a check where we search backwards through the
 parentage chain for a state with the same insn_idx as us.  (We have to
 change a couple of things for this to work: store the insn_idx of the
 current frame instead of the callsite (insn_idx of the calling frame), and
 thanks to function calls it turns out that the chain we want doesn't match
 that for any of the registers.  So I gave registers their own parentage
 chains (that's a nice simplification and worth doing in itself) and added
 a new chain to func_states that does what I want.)  If we find such a state,
 we have looped, so we reject the prog.

So far the diffstat has 159 insertions, 353 deletions.  The downside of
 course is that walking the parentage chain all the time to look for loops
 is going to hurt performance.  I haven't yet come up with a way around that
 but some time spent meditating on data structures might turn something up ;)

Next we want to start allowing the loop as long as it's bounded.  So when we
 detect the loop in is_state_visited, we look at the last jump we did.  (With
 a slight tweak we can make this always available in prev_insn_idx, even if
 we elided the push/pop_stack in check_cond_jmp_op.)  We then look at the
 jump insn, the old state (conveniently returned from our loop detection
 routine!) and the new state, to decide whether the loop is moving towards
 termination.  The test I'm using for now shares some "it's just one case"
 limits as your point 3 :-)  For now it's:
  a) Is the jump a JLT with a constant?  (Same reason as yours.)
  b) Are we in the 'jump true' branch?  (I haven't quite figured out how to
     make sure of this in general, checking insn_idx < prev_insn_idx works
     but rules out back-edges with forward jumps.  Fortunately those only
     occur in unnatural loops so we don't have to support them all.)
  c) Does the jump reg hold a SCALAR_VALUE in both old and new states?
  d) Did the jump reg->umin_value increase from old to new states?
  e) How _fast_ did it increase?  Rule for now is to take the delta, multiply
     it by 16, and if that exceeds the jump compare constant, we're happy.
     This doesn't actually limit loops to 16 times, because the delta could
     decay exponentially - the worst case comes out as 687 iterations.  But
     we could do something cleverer with recording the delta so we can insist
     on linear induction variables (i = i + c) so that we can give those more
     iterations without giving too many to the worst case exponential.

If all of these checks pass, then the loop is (so far) behaving itself.  So
 we mark the old state with a "this is being looped on" flag (which prevents
 it from being used for pruning.  I haven't yet come up with a way to clear
 the flag when all the state's descendants have reached an exit, so this
 will unfortunately reduce pruning effectiveness) and then we carry on the
 walk.  do_check() will ultimately walk around the loop as many times as the
 program will.

Of course, there's one problem here: when do_check walks the loop for the
 last time, and knows that the loop test has to be false... it will still
 follow the branch anyway and keep walking forever.  So I also had to add a
 patch to not follow 'impossible' branches, determined by the jump register
 getting inconsistent bounds.  This is similar to what check_cond_jmp_op()
 already does with JEQ/JNE of const reg against const imm.

>     The worst case loop count would
>     be, `c - min_value` then `(c - min_value) * max(loop_cfg(i))` would be the
>     the worst case instruction that might be executed. Where loop_cfg(i) is the
>     max insns that can be run through the loop with worst case CFG path.
Currently I don't have any equivalent of that loop_cfg(i) factor, so I'm
 applying the same max iteration count to all loops regardless of the size of
 the loop body.  But I guess I could do something like counting insns since
 parent state and recording that in the explored_states, so that when I have
 my detected loop I can count how long it is.

Anyway, that's my design, I hope it wasn't _too_ horrifying, and I hope to
 have some RFC patches in the next week or so.

-Ed

Re: [RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

[Alexei Starovoitov]

On Tue, Feb 13, 2018 at 06:14:53PM +0000, Edward Cree wrote:
> 
> Anyway, that's my design, I hope it wasn't _too_ horrifying, and I hope to
>  have some RFC patches in the next week or so.

I prefer John's approach since it fits into my thinking how verifier should evolve
and follows the outline compilers have been developed for generations.
imo "divide and conquer" should be a center piece of verifier design.
Unfortunately we didn't follow this thinking everywhere and ended up with mess
in few places, but we need to move into that direction.
In practice it means splitting verifier into distinct passes that do one job
and do it well.
In John's proposal it's:
- function call boundaries
- basic block detection
- control flow build
- dom tree build
- existing do_check pass
- etc
I'm working on splitting do_check() further, since reserved fields check
should have been done as separate pass instead of imbedded into do_check().

Also since you're refusing to cleanup [su]minmax I'd have to find
time to do it myself and to revive the work I've started here:
https://git.kernel.org/pub/scm/linux/kernel/git/ast/bpf.git/commit/?h=verif_simplif_v1
_before_ any significant amount of code will land in the verifier,
so please bare with me.
At this point all new verifier code will be deferred until [su]minmax
issues are resolved.

Re: [RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

[Jiong Wang]

On 13/02/2018 05:09, John Fastabend wrote:
> To find these we do the following
>     1.a: Build the CFG of all the instructions so we can walk around the
>          program easily.
>     1.b: Find the basic blocks and build the basic block CFG. After this
>          with a few helper calls we can move around the CFG both at block
>          level and insn level.
>     1.c: Build the dom tree and post dom tree. This is a data structure that
>          allows us to actually find the natural loops. I can write more about
>          this later.
>     1.d: Using the post dom tree verify all the CFG loops are in fact
>          natural loops. I made some simplifications here and threw
>          out loops that have multiple jumps to the header node and nested
>          loops for now. Both can be handled with some additional complexity.
>
>    Versions of the above can be found in gcc and llvm so it appears to be
>    fairly regular stuff from the compiler side. For LLVM the passes are
>    --loops, --postdomtree. I dumped the various CFG into dot format and
>    and graphed them for fun.

This part of work are very interesting. It will be very helpful if these CFG
information are kept even after verification pass finished, or if the storage
overhead is a concern, made into reusable functions.

I plan to implement similar graph dump in bpftool, i.e. be able to dump eBPF
CFG into .dot graph and color the graph according to some simple static analysis,
these exactly need such CFG information.

Regards,
Jiong