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

["Toke Høiland-Jørgensen" <toke@redhat.com>]

Alexei Starovoitov <alexei.starovoitov@gmail.com> writes:

> On Wed, Jan 08, 2020 at 11:28:21AM +0100, Toke Høiland-Jørgensen wrote:
>> Alexei Starovoitov <ast@kernel.org> writes:
>> 
>> > 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:
>> 
>> > +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.

Agreed, it would be sad to miss the cutoff!

> 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.

Sure, OK. Don't have any objections (or opinions on the encoding,
really), just want to understand how this all fits together.

> 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.

Right, FUNC_EXTERN will be rejected by the kernel unless it's patched up
with "target" btf_ids by libbpf before load? So it'll be
FUNC_GLOBAL-linked functions that will be replaceable after the fact
with the "dynamic re-linking" feature?

> 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.

Great, thanks!

-Toke