Re: [PATCH bpf-next 3/6] bpf: Introduce function-by-function verification

On Wed, Jan 08, 2020 at 11:28:21AM +0100, Toke Høiland-Jørgensen wrote:

Alexei Starovoitov [off-list ref] writes:

quoted

New llvm and old llvm with libbpf help produce BTF that distinguish global and
static functions. Unlike arguments of static function the arguments of global
functions cannot be removed or optimized away by llvm. The compiler has to use
exactly the arguments specified in a function prototype. The argument type
information allows the verifier validate each global function independently.
For now only supported argument types are pointer to context and scalars. In
the future pointers to structures, sizes, pointer to packet data can be
supported as well. Consider the following example:

static int f1(int ...)
{
  ...
}

int f3(int b);

int f2(int a)
{
  f1(a) + f3(a);
}

int f3(int b)
{
  ...
}

int main(...)
{
  f1(...) + f2(...) + f3(...);
}

The verifier will start its safety checks from the first global function f2().
It will recursively descend into f1() because it's static. Then it will check
that arguments match for the f3() invocation inside f2(). It will not descend
into f3(). It will finish f2() that has to be successfully verified for all
possible values of 'a'. Then it will proceed with f3(). That function also has
to be safe for all possible values of 'b'. Then it will start subprog 0 (which
is main() function). It will recursively descend into f1() and will skip full
check of f2() and f3(), since they are global. The order of processing global
functions doesn't affect safety, since all global functions must be proven safe
based on their arguments only.

Such function by function verification can drastically improve speed of the
verification and reduce complexity.

Note that the stack limit of 512 still applies to the call chain regardless whether
functions were static or global. The nested level of 8 also still applies. The
same recursion prevention checks are in place as well.

The type information and static/global kind is preserved after the verification
hence in the above example global function f2() and f3() can be replaced later
by equivalent functions with the same types that are loaded and verified later
without affecting safety of this main() program. Such replacement (re-linking)
of global functions is a subject of future patches.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Great to see this progressing; and thanks for breaking things up, makes
it much easier to follow along!

One question:

quoted

+enum btf_func_linkage {
+	BTF_FUNC_STATIC = 0,
+	BTF_FUNC_GLOBAL = 1,
+	BTF_FUNC_EXTERN = 2,
+};

What's supposed to happen with FUNC_EXTERN? That is specifically for the
re-linking follow-up?

I was thinking to complete the whole thing with re-linking and then send it,
but llvm 10 feature cut off date is end of this week, so we have to land llvm
bits asap. I'd like to land patch 1 with libbpf sanitization first before
landing llvm. llvm release cadence is ~4 month and it would be sad to miss it.
Note we will be able to tweak encoding if really necessary after next week.
(BTF encoding gets fixed in ABI only after full kernel release).
It's unlikely though. I think the encoding is good. I've played with few
different variants and this one fits the best. FUNC_EXTERN encoding as 2 is
kinda obvious when encoding for global vs static is selected. The kernel and
libbpf will not be using FUNC_EXTERN yet, but llvm is tested to do the right
thing already, so I think it's fine to add it to btf.h now.

As far as future plans when libbpf sees FUNC_EXTERN it will do the linking the
way we discussed in the other thread. The kernel will support FUNC_EXTERN when
we introduce dynamic libraries. A collection of bpf functions will be loaded
into the kernel first (like libc.so) and later programs will have FUNC_EXTERN
as part of their BTF to be resolved while loading. The func name to btf_id
resolution will be done by libbpf. The kernel verifier will do the type
checking on BTFs. So the kernel side of FUNC_EXTERN support will be minimal,
but to your point below...

This doesn't reject linkage==BTF_FUNC_EXTERN; so for this patch
FUNC_EXTERN will be treated the same as FUNC_STATIC (it'll fail the
is_global check below)? Or did I miss somewhere else where
BTF_FUNC_EXTERN is rejected?

... is absolutely correct. My bad. Added this bit too soon.
Will remove. The kernel should accept FUNC_GLOBAL only in this patch set.