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

On Fri, Dec 22, 2017 at 10:33 PM, Alexei Starovoitov [off-list ref] wrote:

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>

Does this work in cases where multiple invocations of a function have
different stack access patterns because their inputs have different
bounds?

Consider this pseudocode example:

void main(void) {
  func1(0);
  func1(1);
  func2(1);
}
void func1(int alloc_or_recurse) {
  if (alloc_or_recurse) {
    frame_pointer[-300] = 1;
  } else {
    func2(alloc_or_recurse);
  }
}
void func2(int alloc_or_recurse) {
  if (alloc_or_recurse) {
    frame_pointer[-300] = 1;
  }
}

AFAICS this will work as follows:

Call to func1->func2 runs without any stack accesses because the
verifier can prove that alloc_or_recurse is 0.
Second call to func1 allocates stack memory, bumping up
frame_stack_depth[1].
Second call to func2 allocates stack memory, leaving
frame_stack_depth[1] the same.

So I think this will still pass the verifier, even though func1
and func2 will end up with 300 bytes stack memory each, causing
the func1->func2 call to use more stack memory than permitted.