[PATCH bpf-next 1/2] bpf: fix maximum stack depth tracking logic

[Alexei Starovoitov <ast@kernel.org>]

instead of computing max stack depth for current call chain only
track the maximum possible stack depth of any function at given
frame position. Such algorithm is simple and fast, but conservative,
since it overestimates amount of stack used. Consider:
main() // stack 32
{
  A();
  B();
}

A(){} // stack 256

B()  // stack 64
{
  A();
}

since A() is called at frame[1] and frame[2], the algorithm
will estimate the max stack depth as 32 + 256 + 256 and will reject
such program, though real max is 32 + 64 + 256.

Fortunately the algorithm is good enough in practice. The alternative
would be to track max stack of every function in the fast pass through
the verifier and then do additional CFG walk just to compute max total.

Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
Reported-by: Jann Horn <jannh@google.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h | 17 +++++++++++++++++
 kernel/bpf/verifier.c        | 15 +++++++++------
 2 files changed, 26 insertions(+), 6 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index aaac589e490c..adc65ef093d1 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -194,7 +194,24 @@ struct bpf_verifier_env {
 	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];
+	/* gradually computes the maximum stack depth out of all functions
+	 * called at this frame position. Example:
+	 * main()
+	 * {
+	 *   a();
+	 *   b();
+	 * }
+	 * b()
+	 * {
+	 *   a();
+	 * }
+	 * frame_stack_depth[0] = stack depth of main()
+	 * frame_stack_depth[1] = max { stack depth of a(), stack depth of b() }
+	 * frame_stack_depth[2] = stack depth of a()
+	 */
+	u16 frame_stack_depth[MAX_CALL_FRAMES];
 	u32 subprog_cnt;
 };
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4ae46b2cba88..096681bcb312 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1434,15 +1434,18 @@ static int update_stack_depth(struct bpf_verifier_env *env,
 	struct bpf_verifier_state *cur = env->cur_state;
 	int i;
 
+	if (stack < -off)
+		/* update known max for given subprogram */
+		env->subprog_stack_depth[func->subprogno] = -off;
+
+	stack = env->frame_stack_depth[func->frameno];
 	if (stack >= -off)
 		return 0;
+	env->frame_stack_depth[func->frameno] = -off;
 
-	/* update known max for given subprogram */
-	env->subprog_stack_depth[func->subprogno] = -off;
-
-	/* compute the total for current call chain */
-	for (i = 0; i <= cur->curframe; i++) {
-		u32 depth = env->subprog_stack_depth[cur->frame[i]->subprogno];
+	/* some frame changed its max, recompute the total */
+	for (i = 0; i < MAX_CALL_FRAMES; i++) {
+		u32 depth = env->frame_stack_depth[i];
 
 		/* round up to 32-bytes, since this is granularity
 		 * of interpreter stack sizes
-- 
2.9.5