Re: static and dynamic linking. Was: [PATCH bpf-next v3 1/5] bpf: Support chain calling multiple BPF

[Alexei Starovoitov <alexei.starovoitov@gmail.com>]

On Tue, Nov 12, 2019 at 09:25:06PM +0000, Edward Cree wrote:
> On 12/11/2019 19:52, Alexei Starovoitov wrote:
> > We haven't yet defined what 'extern' keyword in the program means.
> > There are a preliminary patches for llvm to support extern variables. Extern
> > functions are not done yet. We have to walk before we run. With dynamic linking
> > I'm proposing an api for the kernel that I think will work regardless of how
> > libbpf and llvm decide to define the meaning of 'extern'.
> Fwiw the 'natural' C way of doing it would be that for any extern symbol in
>  the C file, the ELF file gets a symbol entry with st_shndx=SHN_UNDEF, and
>  code in .text that uses that symbol gets relocation entries.  That's (AIUI)
>  how it works on 'normal' architectures, and that's what my ebld linker
>  understands; when it sees a definition in another file for that symbol
>  (matched just by the symbol name) it applies all the relocations of the
>  symbol to the appropriate progbits.
> I don't really see what else you could define 'extern' to mean.

That's exactly the problem with standard 'extern'. ELF preserves the name only.
There is no type. I think size is there, but linkers ignore it. There is also
no way to place extern into a section. Currently SEC("..") is a standard way to
annotate bpf programs. I think reliable 'extern' has to have more than just
name. 'extern int foo;' can be a reference to 'int foo;' in another BPF ELF
file, or it can be a reference to 'int foo;' in already loaded BPF prog, or it
can be a reference to 'int foo;' inside the kernel itself, or it can be a
reference to pseudo variable that libbpf should replace. For example 'extern
int kernel_version;' or 'extern int CONFIG_HZ;' would be useful extern-like
variables that program might want to use. Disambiguating by name is probably
not enough. We can define an order of resolution. libbpf will search in other
.o first, then will search in loaded bpf progs, than in kernel, and if all
fails than will resolve things like 'extern int CONFIG_HZ' on its own. It feels
fragile though. I think we need to be able to specify something like section to
extern variables and functions. That would be a compiler extension.

> > Partial verification should be available regardless of
> > whether kernel performs dynamic linking or libbpf staticly links multiple .o
> > together.
> It's not clear to me how partial verification would work for statically
>  linked programs — could you elaborate on this?

I was imagining that the verifier will do per-function verification
of program with sub-programs instead of analyzing from root.
Today the verifier is essentially told: Here is XDP program. Check that it's
valid with any valid context. Now imagine the verifier sees a function:
int foo(struct xdp_md *ctx);
The verifier can check that the function is safe when 'ctx' is valid. There is
no program type for the verifier to deal with. Such 'foo' is an abstract
program. It receives a valid pointer to xpd_md and can call any helper that
accepts xdp_md.

Applying the same logic for two arguments:
int foo(struct xdp_md *arg1, struct __sk_buff *arg2);
The verifier can check that such function is safe when both arg1 and arg2 are
valid pointers. This is not a realistic function. It illustrates the idea that
programs/functions can be abstract. Valid pointers of different types are
received and can be further passed into different helpers when types match.

The next step is to extend this thought process to integers.
int foo(struct xdp_md *arg1, int arg2);
The verifier can check that the program is valid for any valid arg1 and
arg2 = mark_reg_unbounded().

Support for pointers to non-context structs are a bit harder. That needs
more thinking. It should be possible to support:
int foo(struct xdp_md *arg1, char *arg2, bpf_size_t arg3);
The verifier will validate that arg2 array is accessed in [0, arg3] range.

I think that will cover most of the use cases. It won't be possible to support
aribtrary passing of pointers the way current bpf2bpf calls support, but I
think it's an acceptable limitation for partial verification.