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

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 08 Jan 2020 11:28:21 +0100

Alexei Starovoitov <[email-masked]> 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 <[email-masked]>

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?

>  /* BTF_KIND_VAR is followed by a single "struct btf_var" to describe
>   * additional information related to the variable such as its linkage.
>   */
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index ed2075884724..e28ec89971ce 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -2621,8 +2621,8 @@ static s32 btf_func_check_meta(struct btf_verifier_env *env,
>  		return -EINVAL;
>  	}
>  
> -	if (btf_type_vlen(t)) {
> -		btf_verifier_log_type(env, t, "vlen != 0");
> +	if (btf_type_vlen(t) > BTF_FUNC_EXTERN) {
> +		btf_verifier_log_type(env, t, "invalid func linkage");

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?

-Toke