diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 17990dd56e65..32f27cbe721b 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -175,8 +175,11 @@ static inline bool bpf_verifier_log_needed(const struct bpf_verifier_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 */
 };
 
 /* single container for all structs
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 587eb445bfa2..45f530e4a65e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -784,6 +784,7 @@ static int add_subprog(struct bpf_verifier_env *env, int off)
 		info = &env->subprog_info[ret];
 		info->start = off;
 		info->stack_depth = 0;
+		memset(info->callees, 0, sizeof(info->callees));
 		env->insn_aux_data[off].subprogno = ret;
 	}
 	return ret;
@@ -793,13 +794,13 @@ static int check_subprogs(struct bpf_verifier_env *env)
 {
 	struct bpf_insn_aux_data *aux = env->insn_aux_data;
 	struct bpf_insn *insns = env->prog->insnsi;
-	int insn_cnt = env->prog->len, i, err;
+	int insn_cnt = env->prog->len, i, subprog;
 	int cur_subprog;
 
 	/* Find subprog starts */
-	err = add_subprog(env, 0); /* subprog 0, main(), starts at insn 0 */
-	if (err < 0)
-		return err;
+	subprog = add_subprog(env, 0); /* subprog 0, main(), starts at insn 0 */
+	if (subprog < 0)
+		return subprog;
 	for (i = 0; i < insn_cnt; i++)
 		if (insns[i].code == (BPF_JMP | BPF_CALL) &&
 		    insns[i].src_reg == BPF_PSEUDO_CALL) {
@@ -814,9 +815,9 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			/* add_subprog marks the callee entry point with the
 			 * new subprogno.
 			 */
-			err = add_subprog(env, i + insns[i].imm + 1);
-			if (err < 0)
-				return err;
+			subprog = add_subprog(env, i + insns[i].imm + 1);
+			if (subprog < 0)
+				return subprog;
 		}
 
 	if (env->log.level > 1)
@@ -842,6 +843,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 		u8 opcode = BPF_OP(insns[i].code);
 		int target;
 
+		cur_subprog = aux[i].subprogno;
 		/* Determine where control flow from this insn goes */
 		if (BPF_CLASS(insns[i].code) != BPF_JMP) {
 			fallthrough = true;
@@ -855,9 +857,18 @@ static int check_subprogs(struct bpf_verifier_env *env)
 				 */
 				continue;
 			case BPF_CALL:
-				/* If pseudo-call, already handled marking the
-				 * callee.  Both kinds of call will eventually
-				 * return and pass to the following insn.
+				if (insns[i].src_reg == BPF_PSEUDO_CALL) {
+					/* record edge in call graph */
+					subprog = find_subprog(env, i + insns[i].imm + 1);
+					if (subprog < 0)
+						return subprog;
+					__set_bit(subprog, env->subprog_info[cur_subprog].callees);
+					/* already handled marking the callee
+					 * back in add_subprog, so jump is false
+					 */
+				}
+				/* Call will eventually return and pass control
+				 * to the following insn.
 				 */
 				fallthrough = true;
 				break;
@@ -876,7 +887,6 @@ static int check_subprogs(struct bpf_verifier_env *env)
 		}
 
 		/* Check that that control flow doesn't leave the subprog */
-		cur_subprog = aux[i].subprogno;
 		if (fallthrough) {
 			if (i + 1 >= insn_cnt) {
 				verbose(env, "no exit/jump at end of program (insn %d)\n",
@@ -1533,78 +1543,96 @@ static int update_stack_depth(struct bpf_verifier_env *env,
 			      const struct bpf_func_state *func,
 			      int off)
 {
-	u16 stack = env->subprog_info[func->subprogno].stack_depth;
+	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_info[func->subprogno].stack_depth = -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.
+ * The tsort is performed using Kahn's algorithm.  Since that algorithm selects
+ * nodes in the order of the sorted output, we can do our processing in the loop
+ * that does the tsort, rather than storing the sorted list and then having a
+ * second loop to iterate over it and compute the total_stack_depth values.
  */
 static int check_max_stack_depth(struct bpf_verifier_env *env)
 {
-	int depth = 0, frame = 0, subprog = 0, i = 0;
-	struct bpf_insn_aux_data *aux = env->insn_aux_data;
-	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];
+	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.  Since all callers of this
+		 * function have already been processed, the value now in
+		 * info->total_stack_depth reflects the deepest call chain of
+		 * this function.
+		 */
+		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;
+		}
+		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);
 
-process_func:
-	/* round up to 32-bytes, since this is granularity
-	 * of interpreter stack size
-	 */
-	depth += round_up(max_t(u32, env->subprog_info[subprog].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;
+			/* Update callee total stack depth.  Since our own
+			 * max total_stack_depth is known, the callee tsd is
+			 * at least that plus the callee's stack frame size.
+			 */
+			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);
+		}
 	}
-continue_func:
-	for (; i < insn_cnt && aux[i].subprogno == subprog; 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;
-		}
-		frame++;
-		if (frame >= MAX_CALL_FRAMES) {
-			WARN_ONCE(1, "verifier bug. Call stack is too deep\n");
-			return -EFAULT;
-		}
-		goto process_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;
 	}
-	/* 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_info[subprog].stack_depth, 1),
-			  32);
-	frame--;
-	i = ret_insn[frame];
-	subprog = ret_prog[frame];
-	goto continue_func;
+	return 0;
 }
 
 #ifndef CONFIG_BPF_JIT_ALWAYS_ON
