Packet pointer invalidation and subprograms

Packet pointer invalidation and subprograms

[Nick Zavaritsky]

Hi,

Calls to helpers such as bpf_skb_pull_data, are supposed to invalidate
all prior checks on packet pointers.

I noticed that if I wrap a call to bpf_skb_pull_data in a function with
global linkage, pointers checked prior to the call are still considered
valid after the call. The program is accepted on 6.8 and 6.13-rc1.

I'm curious if it is by design and if not, if it is a known issue.
Please find the program below.

#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>

__attribute__((__noinline__))
long skb_pull_data(struct __sk_buff *sk, __u32 len)
{
    return bpf_skb_pull_data(sk, len);
}

SEC("tc")
int test_invalidate_checks(struct __sk_buff *sk)
{
    int *p = (void *)(long)sk->data;
    if ((void *)(p + 1) > (void *)(long)sk->data_end) return TCX_DROP;
    skb_pull_data(sk, 0);
    *p = 42;
    return TCX_PASS;
}

If I remove noinline or add static, the program is rejected as expected.

Re: Packet pointer invalidation and subprograms

[Eduard Zingerman]

On Tue, 2024-12-03 at 17:26 +0100, Nick Zavaritsky wrote:
> Hi,
> 
> Calls to helpers such as bpf_skb_pull_data, are supposed to invalidate
> all prior checks on packet pointers.
> 
> I noticed that if I wrap a call to bpf_skb_pull_data in a function with
> global linkage, pointers checked prior to the call are still considered
> valid after the call. The program is accepted on 6.8 and 6.13-rc1.
> 
> I'm curious if it is by design and if not, if it is a known issue.
> Please find the program below.
> 
> #include <linux/bpf.h>
> #include <bpf/bpf_helpers.h>
> 
> __attribute__((__noinline__))
> long skb_pull_data(struct __sk_buff *sk, __u32 len)
> {
>     return bpf_skb_pull_data(sk, len);
> }
> 
> SEC("tc")
> int test_invalidate_checks(struct __sk_buff *sk)
> {
>     int *p = (void *)(long)sk->data;
>     if ((void *)(p + 1) > (void *)(long)sk->data_end) return TCX_DROP;
>     skb_pull_data(sk, 0);
>     *p = 42;
>     return TCX_PASS;
> }
> 
> If I remove noinline or add static, the program is rejected as expected.
> 

Hi Nick,

Thank you for the report. This is a bug. Technically, packet pointers
are invalidated by clear_all_pkt_pointers() called from check_helper_callf().
This functions looks through all packets in current verifier state.
However, global functions are verified independent of call sites,
so pointer 'p' does not exist in verifier state when 'skb_pull_data'
is verified, and thus is not invalidated.

Re: Packet pointer invalidation and subprograms

[Eduard Zingerman]

On Tue, 2024-12-03 at 12:19 -0800, Eduard Zingerman wrote:
> On Tue, 2024-12-03 at 17:26 +0100, Nick Zavaritsky wrote:
> > Hi,
> > 
> > Calls to helpers such as bpf_skb_pull_data, are supposed to invalidate
> > all prior checks on packet pointers.
> > 
> > I noticed that if I wrap a call to bpf_skb_pull_data in a function with
> > global linkage, pointers checked prior to the call are still considered
> > valid after the call. The program is accepted on 6.8 and 6.13-rc1.
> > 
> > I'm curious if it is by design and if not, if it is a known issue.
> > Please find the program below.
> > 
> > #include <linux/bpf.h>
> > #include <bpf/bpf_helpers.h>
> > 
> > __attribute__((__noinline__))
> > long skb_pull_data(struct __sk_buff *sk, __u32 len)
> > {
> >     return bpf_skb_pull_data(sk, len);
> > }
> > 
> > SEC("tc")
> > int test_invalidate_checks(struct __sk_buff *sk)
> > {
> >     int *p = (void *)(long)sk->data;
> >     if ((void *)(p + 1) > (void *)(long)sk->data_end) return TCX_DROP;
> >     skb_pull_data(sk, 0);
> >     *p = 42;
> >     return TCX_PASS;
> > }
> > 
> > If I remove noinline or add static, the program is rejected as expected.
> > 
> 
> Hi Nick,
> 
> Thank you for the report. This is a bug. Technically, packet pointers
> are invalidated by clear_all_pkt_pointers() called from check_helper_callf().
> This functions looks through all packets in current verifier state.
> However, global functions are verified independent of call sites,
> so pointer 'p' does not exist in verifier state when 'skb_pull_data'
> is verified, and thus is not invalidated.
> 

There are several ways to fix this:
- The "dumb" way:
  - forbid calling helpers that bpf_helper_changes_pkt_data()
    from global functions.
- The "simple" way:
  - at some early stage:
    - scan all global functions, to see if there are any calls to
      helpers that bpf_helper_changes_pkt_data(). If there are,
      remember this as an "effect" of the function;
    - build a call-graph of global functions and propagate computed
      effects over this call-graph (if A calls B and B does
      clear_all_pkt_pointers(), then A also does it).
  - during main verification phase, if a call to a global function is
    verified, check it's effects and update state accordingly
    (e.g. call clear_all_pkt_pointers()).
- The "correct" way:
  - build a call-graph of global functions;
  - verify these functions in a post-order;
  - while verifying, collect "effects" information
    (so far, the single effect is whether or not
     clear_all_pkt_pointers() had been ever called for the function);
  - if a call to global function is verified, check it's effects and
    update state accordingly (e.g. call clear_all_pkt_pointers()).

"dumb" is probably a no-go as it is too restrictive.
The only advantage of "simple" over "correct" that I see is
that the logic for clear_all_pkt_pointers() remains confined
to check_helper_call() and is not duplicated in a separate pass.
In theory, this also allows to compute more complex function effects
on the main verification pass.

I think "simple" is a way to go at the moment.

Alexei, Andrii, what do you think?

Re: Packet pointer invalidation and subprograms

[Andrii Nakryiko]

On Tue, Dec 3, 2024 at 1:42 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2024-12-03 at 12:19 -0800, Eduard Zingerman wrote:
> > On Tue, 2024-12-03 at 17:26 +0100, Nick Zavaritsky wrote:
> > > Hi,
> > >
> > > Calls to helpers such as bpf_skb_pull_data, are supposed to invalidate
> > > all prior checks on packet pointers.
> > >
> > > I noticed that if I wrap a call to bpf_skb_pull_data in a function with
> > > global linkage, pointers checked prior to the call are still considered
> > > valid after the call. The program is accepted on 6.8 and 6.13-rc1.
> > >
> > > I'm curious if it is by design and if not, if it is a known issue.
> > > Please find the program below.
> > >
> > > #include <linux/bpf.h>
> > > #include <bpf/bpf_helpers.h>
> > >
> > > __attribute__((__noinline__))
> > > long skb_pull_data(struct __sk_buff *sk, __u32 len)
> > > {
> > >     return bpf_skb_pull_data(sk, len);
> > > }
> > >
> > > SEC("tc")
> > > int test_invalidate_checks(struct __sk_buff *sk)
> > > {
> > >     int *p = (void *)(long)sk->data;
> > >     if ((void *)(p + 1) > (void *)(long)sk->data_end) return TCX_DROP;
> > >     skb_pull_data(sk, 0);
> > >     *p = 42;
> > >     return TCX_PASS;
> > > }
> > >
> > > If I remove noinline or add static, the program is rejected as expected.
> > >
> >
> > Hi Nick,
> >
> > Thank you for the report. This is a bug. Technically, packet pointers
> > are invalidated by clear_all_pkt_pointers() called from check_helper_callf().
> > This functions looks through all packets in current verifier state.
> > However, global functions are verified independent of call sites,
> > so pointer 'p' does not exist in verifier state when 'skb_pull_data'
> > is verified, and thus is not invalidated.
> >
>
> There are several ways to fix this:
> - The "dumb" way:
>   - forbid calling helpers that bpf_helper_changes_pkt_data()
>     from global functions.
> - The "simple" way:
>   - at some early stage:
>     - scan all global functions, to see if there are any calls to
>       helpers that bpf_helper_changes_pkt_data(). If there are,
>       remember this as an "effect" of the function;
>     - build a call-graph of global functions and propagate computed
>       effects over this call-graph (if A calls B and B does
>       clear_all_pkt_pointers(), then A also does it).
>   - during main verification phase, if a call to a global function is
>     verified, check it's effects and update state accordingly
>     (e.g. call clear_all_pkt_pointers()).
> - The "correct" way:
>   - build a call-graph of global functions;
>   - verify these functions in a post-order;
>   - while verifying, collect "effects" information
>     (so far, the single effect is whether or not
>      clear_all_pkt_pointers() had been ever called for the function);

So this is the only "side effect" we have right now? Are there any
others we have already or can reasonably anticipate? I'm just trying
to decide if we need to generalize this concept.

>   - if a call to global function is verified, check it's effects and
>     update state accordingly (e.g. call clear_all_pkt_pointers()).
>
> "dumb" is probably a no-go as it is too restrictive.
> The only advantage of "simple" over "correct" that I see is
> that the logic for clear_all_pkt_pointers() remains confined
> to check_helper_call() and is not duplicated in a separate pass.

"simple" doesn't take into account dead code elimination, undermining
BPF CO-RE-based feature detection, so I think this is also a no-go

> In theory, this also allows to compute more complex function effects
> on the main verification pass.
>
> I think "simple" is a way to go at the moment.

I think neither of the above are fully valid, tbh. "correct" will do
eager subprog validation, even if due to dead code elimination that
global function might not have been called.

From the outset, I think the "right" way to solve this would be to
start verification from the main program. When we encounter global
subprog verification, we pause verification for the main program,
create a new isolated verifier state, proceed with global subprog
verification, and so on until we check everything. So basically a
stack of subprogs to validate.

This is PITA, of course, just for this (which is also the question
about the generalization of the "side effects" concept). So I don't
know, maybe for now the "dumb" way is the way?

>
> Alexei, Andrii, what do you think?
>

Re: Packet pointer invalidation and subprograms

[Kumar Kartikeya Dwivedi]

On Fri, 6 Dec 2024 at 01:04, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Dec 3, 2024 at 1:42 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Tue, 2024-12-03 at 12:19 -0800, Eduard Zingerman wrote:
> > > On Tue, 2024-12-03 at 17:26 +0100, Nick Zavaritsky wrote:
> > > > Hi,
> > > >
> > > > Calls to helpers such as bpf_skb_pull_data, are supposed to invalidate
> > > > all prior checks on packet pointers.
> > > >
> > > > I noticed that if I wrap a call to bpf_skb_pull_data in a function with
> > > > global linkage, pointers checked prior to the call are still considered
> > > > valid after the call. The program is accepted on 6.8 and 6.13-rc1.
> > > >
> > > > I'm curious if it is by design and if not, if it is a known issue.
> > > > Please find the program below.
> > > >
> > > > #include <linux/bpf.h>
> > > > #include <bpf/bpf_helpers.h>
> > > >
> > > > __attribute__((__noinline__))
> > > > long skb_pull_data(struct __sk_buff *sk, __u32 len)
> > > > {
> > > >     return bpf_skb_pull_data(sk, len);
> > > > }
> > > >
> > > > SEC("tc")
> > > > int test_invalidate_checks(struct __sk_buff *sk)
> > > > {
> > > >     int *p = (void *)(long)sk->data;
> > > >     if ((void *)(p + 1) > (void *)(long)sk->data_end) return TCX_DROP;
> > > >     skb_pull_data(sk, 0);
> > > >     *p = 42;
> > > >     return TCX_PASS;
> > > > }
> > > >
> > > > If I remove noinline or add static, the program is rejected as expected.
> > > >
> > >
> > > Hi Nick,
> > >
> > > Thank you for the report. This is a bug. Technically, packet pointers
> > > are invalidated by clear_all_pkt_pointers() called from check_helper_callf().
> > > This functions looks through all packets in current verifier state.
> > > However, global functions are verified independent of call sites,
> > > so pointer 'p' does not exist in verifier state when 'skb_pull_data'
> > > is verified, and thus is not invalidated.
> > >
> >
> > There are several ways to fix this:
> > - The "dumb" way:
> >   - forbid calling helpers that bpf_helper_changes_pkt_data()
> >     from global functions.
> > - The "simple" way:
> >   - at some early stage:
> >     - scan all global functions, to see if there are any calls to
> >       helpers that bpf_helper_changes_pkt_data(). If there are,
> >       remember this as an "effect" of the function;
> >     - build a call-graph of global functions and propagate computed
> >       effects over this call-graph (if A calls B and B does
> >       clear_all_pkt_pointers(), then A also does it).
> >   - during main verification phase, if a call to a global function is
> >     verified, check it's effects and update state accordingly
> >     (e.g. call clear_all_pkt_pointers()).
> > - The "correct" way:
> >   - build a call-graph of global functions;
> >   - verify these functions in a post-order;
> >   - while verifying, collect "effects" information
> >     (so far, the single effect is whether or not
> >      clear_all_pkt_pointers() had been ever called for the function);
>
> So this is the only "side effect" we have right now? Are there any
> others we have already or can reasonably anticipate? I'm just trying
> to decide if we need to generalize this concept.

It would be good to generalize, we can use such "effects" or
"summarization" to also know whether a global func is sleepable or
not.
This would allow lifting the current restriction of calling them from
atomic contexts seen in verifier state, right that's the only thing
that's preventing the call. So it would be a nice side benefit.

>
> >   - if a call to global function is verified, check it's effects and
> >     update state accordingly (e.g. call clear_all_pkt_pointers()).
> >
> > "dumb" is probably a no-go as it is too restrictive.
> > The only advantage of "simple" over "correct" that I see is
> > that the logic for clear_all_pkt_pointers() remains confined
> > to check_helper_call() and is not duplicated in a separate pass.
>
> "simple" doesn't take into account dead code elimination, undermining
> BPF CO-RE-based feature detection, so I think this is also a no-go
>
> > In theory, this also allows to compute more complex function effects
> > on the main verification pass.
> >
> > I think "simple" is a way to go at the moment.
>
> I think neither of the above are fully valid, tbh. "correct" will do
> eager subprog validation, even if due to dead code elimination that
> global function might not have been called.
>
> From the outset, I think the "right" way to solve this would be to
> start verification from the main program. When we encounter global
> subprog verification, we pause verification for the main program,
> create a new isolated verifier state, proceed with global subprog
> verification, and so on until we check everything. So basically a
> stack of subprogs to validate.
>
> This is PITA, of course, just for this (which is also the question
> about the generalization of the "side effects" concept). So I don't
> know, maybe for now the "dumb" way is the way?
>
> >
> > Alexei, Andrii, what do you think?
> >
>

Re: Packet pointer invalidation and subprograms

[Eduard Zingerman]

On Thu, 2024-12-05 at 16:03 -0800, Andrii Nakryiko wrote:

[...]

> > There are several ways to fix this:
> > - The "dumb" way:
> >   - forbid calling helpers that bpf_helper_changes_pkt_data()
> >     from global functions.
> > - The "simple" way:
> >   - at some early stage:
> >     - scan all global functions, to see if there are any calls to
> >       helpers that bpf_helper_changes_pkt_data(). If there are,
> >       remember this as an "effect" of the function;
> >     - build a call-graph of global functions and propagate computed
> >       effects over this call-graph (if A calls B and B does
> >       clear_all_pkt_pointers(), then A also does it).
> >   - during main verification phase, if a call to a global function is
> >     verified, check it's effects and update state accordingly
> >     (e.g. call clear_all_pkt_pointers()).
> > - The "correct" way:
> >   - build a call-graph of global functions;
> >   - verify these functions in a post-order;
> >   - while verifying, collect "effects" information
> >     (so far, the single effect is whether or not
> >      clear_all_pkt_pointers() had been ever called for the function);
> 
> So this is the only "side effect" we have right now? Are there any
> others we have already or can reasonably anticipate? I'm just trying
> to decide if we need to generalize this concept.

Don't have anything to add to Kumar's answer.

> >   - if a call to global function is verified, check it's effects and
> >     update state accordingly (e.g. call clear_all_pkt_pointers()).
> > 
> > "dumb" is probably a no-go as it is too restrictive.
> > The only advantage of "simple" over "correct" that I see is
> > that the logic for clear_all_pkt_pointers() remains confined
> > to check_helper_call() and is not duplicated in a separate pass.
> 
> "simple" doesn't take into account dead code elimination, undermining
> BPF CO-RE-based feature detection, so I think this is also a no-go

That's a bummer :)
I takled with Alexei yesterday and he preferred "simple",
so I went ahead and the fix does look simple:
https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug

> > > In theory, this also allows to compute more complex function effects
> > on the main verification pass.
> > 
> > I think "simple" is a way to go at the moment.
> 
> I think neither of the above are fully valid, tbh. "correct" will do
> eager subprog validation, even if due to dead code elimination that
> global function might not have been called.
> 
> From the outset, I think the "right" way to solve this would be to
> start verification from the main program. When we encounter global
> subprog verification, we pause verification for the main program,
> create a new isolated verifier state, proceed with global subprog
> verification, and so on until we check everything. So basically a
> stack of subprogs to validate.

This might be not that hard to do, actually.

If global function had not been verified yet, and a call to such
function is encountered:
- setup arguments as for global function verification;
- keep stack and BPF_EXIT processing as for non-global functions;

> This is PITA, of course, just for this (which is also the question
> about the generalization of the "side effects" concept). So I don't
> know, maybe for now the "dumb" way is the way?

Idk, "dumb" seems too restrictive.

Re: Packet pointer invalidation and subprograms

[Alexei Starovoitov]

On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> so I went ahead and the fix does look simple:
> https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug

Looks simple enough to me.
Ship it for bpf tree.
If we can come up with something better we can do it later in bpf-next.

I very much prefer to avoid complexity as much as possible.

Re: Packet pointer invalidation and subprograms

[Eduard Zingerman]

On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > so I went ahead and the fix does look simple:
> > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> 
> Looks simple enough to me.
> Ship it for bpf tree.
> If we can come up with something better we can do it later in bpf-next.
> 
> I very much prefer to avoid complexity as much as possible.

Sent the patch-set for "simple".
It is better then "dumb" by any metric anyways.
Will try what Andrii suggests, as allowing calling global sub-programs
from non-sleepable context sounds interesting.

Re: Packet pointer invalidation and subprograms

[Andrii Nakryiko]

On Thu, Dec 5, 2024 at 8:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> > On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > so I went ahead and the fix does look simple:
> > > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> >
> > Looks simple enough to me.
> > Ship it for bpf tree.
> > If we can come up with something better we can do it later in bpf-next.
> >
> > I very much prefer to avoid complexity as much as possible.
>
> Sent the patch-set for "simple".
> It is better then "dumb" by any metric anyways.
> Will try what Andrii suggests, as allowing calling global sub-programs
> from non-sleepable context sounds interesting.
>

I haven't looked at your patches yet, but keep in mind another gotcha
with subprograms: they can be freplace'd by another BPF program
(clearly freplace programs were a successful reduction of
complexity... ;)

What this means in practice is whatever deductions you get out of
analyzing any specific original subprogram might be violated by
freplace program if we don't enforce them during freplace attachment.


Anyways, I came here to say that I think I have a much simpler
solution that won't require big changes to the BPF verifier: tags. We
can shift the burden to the user having to declare the intent upfront
through subprog tags. And then, during verification of that global
subprog, the verifier can enforce that only explicitly declared side
effects can be enacted by the subprogram's code (taking into account
lazy dead code detection logic).

We already take advantage of declarative tags for global subprog args
(__arg_trusted, etc), we can do the same for the function itself. We
can have __subprog_invalidates_all_pkt_pointers tag (and yes, I do
insist on this laconic name, of course), and during verification of
subprogram we just make sure that subprog was annotated as such, if
one of those fancy helpers is called directly in subprog itself or
transitively through any of *actually* called subprogs.

All this will preserve the lazy approach we have with no need to look
ahead into subprog's implementation. I'd keep the concept of global
subprog completely and exhaustively described with its type signature
and associated tags as much as possible.

P.S. We still need to keep in mind freplace complications, of course.

Re: Packet pointer invalidation and subprograms

[Eduard Zingerman]

On Thu, 2024-12-05 at 22:22 -0800, Andrii Nakryiko wrote:
> On Thu, Dec 5, 2024 at 8:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> > > On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > 
> > > > so I went ahead and the fix does look simple:
> > > > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> > > 
> > > Looks simple enough to me.
> > > Ship it for bpf tree.
> > > If we can come up with something better we can do it later in bpf-next.
> > > 
> > > I very much prefer to avoid complexity as much as possible.
> > 
> > Sent the patch-set for "simple".
> > It is better then "dumb" by any metric anyways.
> > Will try what Andrii suggests, as allowing calling global sub-programs
> > from non-sleepable context sounds interesting.
> > 
> 
> I haven't looked at your patches yet, but keep in mind another gotcha
> with subprograms: they can be freplace'd by another BPF program
> (clearly freplace programs were a successful reduction of
> complexity... ;)

If there would be no general objections for the patch-set I posted,
I'll do a v2 with an additional flag in bpf_prog_aux/bpf_func_info_aux
to be checked when freplace attachment is done.

> What this means in practice is whatever deductions you get out of
> analyzing any specific original subprogram might be violated by
> freplace program if we don't enforce them during freplace attachment.
> 
> 
> Anyways, I came here to say that I think I have a much simpler
> solution that won't require big changes to the BPF verifier: tags. We
> can shift the burden to the user having to declare the intent upfront
> through subprog tags. And then, during verification of that global
> subprog, the verifier can enforce that only explicitly declared side
> effects can be enacted by the subprogram's code (taking into account
> lazy dead code detection logic).

I considered tags, but didn't like it much for something so easily computable.
Please take a look at the patch, the change for check_cfg() is 32 lines.

> We already take advantage of declarative tags for global subprog args
> (__arg_trusted, etc), we can do the same for the function itself. We
> can have __subprog_invalidates_all_pkt_pointers tag (and yes, I do
> insist on this laconic name, of course), and during verification of
> subprogram we just make sure that subprog was annotated as such, if
> one of those fancy helpers is called directly in subprog itself or
> transitively through any of *actually* called subprogs.
> 
> All this will preserve the lazy approach we have with no need to look
> ahead into subprog's implementation. I'd keep the concept of global
> subprog completely and exhaustively described with its type signature
> and associated tags as much as possible.
> 
> P.S. We still need to keep in mind freplace complications, of course.

Re: Packet pointer invalidation and subprograms

[Alexei Starovoitov]

On Thu, Dec 5, 2024 at 10:23 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Thu, Dec 5, 2024 at 8:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> > > On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > so I went ahead and the fix does look simple:
> > > > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> > >
> > > Looks simple enough to me.
> > > Ship it for bpf tree.
> > > If we can come up with something better we can do it later in bpf-next.
> > >
> > > I very much prefer to avoid complexity as much as possible.
> >
> > Sent the patch-set for "simple".
> > It is better then "dumb" by any metric anyways.
> > Will try what Andrii suggests, as allowing calling global sub-programs
> > from non-sleepable context sounds interesting.
> >
>
> I haven't looked at your patches yet, but keep in mind another gotcha
> with subprograms: they can be freplace'd by another BPF program
> (clearly freplace programs were a successful reduction of
> complexity... ;)
>
> What this means in practice is whatever deductions you get out of
> analyzing any specific original subprogram might be violated by
> freplace program if we don't enforce them during freplace attachment.
>
>
> Anyways, I came here to say that I think I have a much simpler
> solution that won't require big changes to the BPF verifier: tags. We
> can shift the burden to the user having to declare the intent upfront
> through subprog tags. And then, during verification of that global
> subprog, the verifier can enforce that only explicitly declared side
> effects can be enacted by the subprogram's code (taking into account
> lazy dead code detection logic).
>
> We already take advantage of declarative tags for global subprog args
> (__arg_trusted, etc), we can do the same for the function itself. We
> can have __subprog_invalidates_all_pkt_pointers tag (and yes, I do
> insist on this laconic name, of course), and during verification of
> subprogram we just make sure that subprog was annotated as such, if
> one of those fancy helpers is called directly in subprog itself or
> transitively through any of *actually* called subprogs.

tags for args was an aid to the verifier. Nothing is broken without them.
Here it's about correctness.
So we cannot use tags to solve this case.

Re: Packet pointer invalidation and subprograms

[Andrii Nakryiko]

On Fri, Dec 6, 2024 at 2:44 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2024-12-05 at 22:22 -0800, Andrii Nakryiko wrote:
> > On Thu, Dec 5, 2024 at 8:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> > > > On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > >
> > > > > so I went ahead and the fix does look simple:
> > > > > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> > > >
> > > > Looks simple enough to me.
> > > > Ship it for bpf tree.
> > > > If we can come up with something better we can do it later in bpf-next.
> > > >
> > > > I very much prefer to avoid complexity as much as possible.
> > >
> > > Sent the patch-set for "simple".
> > > It is better then "dumb" by any metric anyways.
> > > Will try what Andrii suggests, as allowing calling global sub-programs
> > > from non-sleepable context sounds interesting.
> > >
> >
> > I haven't looked at your patches yet, but keep in mind another gotcha
> > with subprograms: they can be freplace'd by another BPF program
> > (clearly freplace programs were a successful reduction of
> > complexity... ;)
>
> If there would be no general objections for the patch-set I posted,
> I'll do a v2 with an additional flag in bpf_prog_aux/bpf_func_info_aux
> to be checked when freplace attachment is done.
>
> > What this means in practice is whatever deductions you get out of
> > analyzing any specific original subprogram might be violated by
> > freplace program if we don't enforce them during freplace attachment.
> >
> >
> > Anyways, I came here to say that I think I have a much simpler
> > solution that won't require big changes to the BPF verifier: tags. We
> > can shift the burden to the user having to declare the intent upfront
> > through subprog tags. And then, during verification of that global
> > subprog, the verifier can enforce that only explicitly declared side
> > effects can be enacted by the subprogram's code (taking into account
> > lazy dead code detection logic).
>
> I considered tags, but didn't like it much for something so easily computable.

The tags would be that generalizable side effect declaration approach,
so seems worth it to set a uniform approach.

> Please take a look at the patch, the change for check_cfg() is 32 lines.

I did, actually. And I already explained what I don't like about it:
eagerness. check_cfg() is not the right place for this, if we want to
support dead code elimination and BPF CO-RE-based feature gating.
Which your patches clearly violate, so I don't like them, sorry.

We made this eagerness mistake with global subprogs verification
previously, and had to switch it to lazy on-demand global subprog
validation. I think we should preserve this lazy approach going
forward.

>
> > We already take advantage of declarative tags for global subprog args
> > (__arg_trusted, etc), we can do the same for the function itself. We
> > can have __subprog_invalidates_all_pkt_pointers tag (and yes, I do
> > insist on this laconic name, of course), and during verification of
> > subprogram we just make sure that subprog was annotated as such, if
> > one of those fancy helpers is called directly in subprog itself or
> > transitively through any of *actually* called subprogs.
> >
> > All this will preserve the lazy approach we have with no need to look
> > ahead into subprog's implementation. I'd keep the concept of global
> > subprog completely and exhaustively described with its type signature
> > and associated tags as much as possible.
> >
> > P.S. We still need to keep in mind freplace complications, of course.
>
>

Re: Packet pointer invalidation and subprograms

[Andrii Nakryiko]

On Fri, Dec 6, 2024 at 8:08 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Thu, Dec 5, 2024 at 10:23 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Thu, Dec 5, 2024 at 8:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> > > > On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > >
> > > > > so I went ahead and the fix does look simple:
> > > > > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> > > >
> > > > Looks simple enough to me.
> > > > Ship it for bpf tree.
> > > > If we can come up with something better we can do it later in bpf-next.
> > > >
> > > > I very much prefer to avoid complexity as much as possible.
> > >
> > > Sent the patch-set for "simple".
> > > It is better then "dumb" by any metric anyways.
> > > Will try what Andrii suggests, as allowing calling global sub-programs
> > > from non-sleepable context sounds interesting.
> > >
> >
> > I haven't looked at your patches yet, but keep in mind another gotcha
> > with subprograms: they can be freplace'd by another BPF program
> > (clearly freplace programs were a successful reduction of
> > complexity... ;)
> >
> > What this means in practice is whatever deductions you get out of
> > analyzing any specific original subprogram might be violated by
> > freplace program if we don't enforce them during freplace attachment.
> >
> >
> > Anyways, I came here to say that I think I have a much simpler
> > solution that won't require big changes to the BPF verifier: tags. We
> > can shift the burden to the user having to declare the intent upfront
> > through subprog tags. And then, during verification of that global
> > subprog, the verifier can enforce that only explicitly declared side
> > effects can be enacted by the subprogram's code (taking into account
> > lazy dead code detection logic).
> >
> > We already take advantage of declarative tags for global subprog args
> > (__arg_trusted, etc), we can do the same for the function itself. We
> > can have __subprog_invalidates_all_pkt_pointers tag (and yes, I do
> > insist on this laconic name, of course), and during verification of
> > subprogram we just make sure that subprog was annotated as such, if
> > one of those fancy helpers is called directly in subprog itself or
> > transitively through any of *actually* called subprogs.
>
> tags for args was an aid to the verifier. Nothing is broken without them.
> Here it's about correctness.
> So we cannot use tags to solve this case.

Hm.. Just like without an arg tag, verifier would conservatively
assume that `struct task_struct *task` global subprog argument is just
some opaque memory, not really a task, and would verify that argument
and code working with it as such. If a user did something that
required extra task_struct semantics, then that would be a
verification error. Unless the user added __arg_trusted, of course.

Same thing here. We *assume* that global subprog doesn't have this
packet pointers side effect. If later during verification it turns out
it does have this effect -- this is an error and subprog gets
rejected. Unless the user provided
__subprog_invalidates_all_pkt_pointers, of course. Same thing.

I'm not saying we shouldn't fix the issue, I'm saying we should fix it
in a different place and add a tag to enable this side effect.

Re: Packet pointer invalidation and subprograms

[Alexei Starovoitov]

On Fri, Dec 6, 2024 at 8:13 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Fri, Dec 6, 2024 at 8:08 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Thu, Dec 5, 2024 at 10:23 PM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Thu, Dec 5, 2024 at 8:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> > > > > On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > >
> > > > > > so I went ahead and the fix does look simple:
> > > > > > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> > > > >
> > > > > Looks simple enough to me.
> > > > > Ship it for bpf tree.
> > > > > If we can come up with something better we can do it later in bpf-next.
> > > > >
> > > > > I very much prefer to avoid complexity as much as possible.
> > > >
> > > > Sent the patch-set for "simple".
> > > > It is better then "dumb" by any metric anyways.
> > > > Will try what Andrii suggests, as allowing calling global sub-programs
> > > > from non-sleepable context sounds interesting.
> > > >
> > >
> > > I haven't looked at your patches yet, but keep in mind another gotcha
> > > with subprograms: they can be freplace'd by another BPF program
> > > (clearly freplace programs were a successful reduction of
> > > complexity... ;)
> > >
> > > What this means in practice is whatever deductions you get out of
> > > analyzing any specific original subprogram might be violated by
> > > freplace program if we don't enforce them during freplace attachment.
> > >
> > >
> > > Anyways, I came here to say that I think I have a much simpler
> > > solution that won't require big changes to the BPF verifier: tags. We
> > > can shift the burden to the user having to declare the intent upfront
> > > through subprog tags. And then, during verification of that global
> > > subprog, the verifier can enforce that only explicitly declared side
> > > effects can be enacted by the subprogram's code (taking into account
> > > lazy dead code detection logic).
> > >
> > > We already take advantage of declarative tags for global subprog args
> > > (__arg_trusted, etc), we can do the same for the function itself. We
> > > can have __subprog_invalidates_all_pkt_pointers tag (and yes, I do
> > > insist on this laconic name, of course), and during verification of
> > > subprogram we just make sure that subprog was annotated as such, if
> > > one of those fancy helpers is called directly in subprog itself or
> > > transitively through any of *actually* called subprogs.
> >
> > tags for args was an aid to the verifier. Nothing is broken without them.
> > Here it's about correctness.
> > So we cannot use tags to solve this case.
>
> Hm.. Just like without an arg tag, verifier would conservatively
> assume that `struct task_struct *task` global subprog argument is just
> some opaque memory, not really a task, and would verify that argument
> and code working with it as such. If a user did something that
> required extra task_struct semantics, then that would be a
> verification error. Unless the user added __arg_trusted, of course.
>
> Same thing here. We *assume* that global subprog doesn't have this
> packet pointers side effect. If later during verification it turns out
> it does have this effect -- this is an error and subprog gets
> rejected. Unless the user provided
> __subprog_invalidates_all_pkt_pointers, of course. Same thing.

So depending on the order of walking the progs, compiler layout,
static vs global the extra tag is either mandatory or not.
That is horrible UX. I really don't like moving the burden to the user
when the verifier can see it all.
arg_ctx is different. The verifier just doesn't have the knowledge.

Re: Packet pointer invalidation and subprograms

[Eduard Zingerman]

On Fri, 2024-12-06 at 08:08 -0800, Andrii Nakryiko wrote:

[...]

> The tags would be that generalizable side effect declaration approach,
> so seems worth it to set a uniform approach.
> 
> > Please take a look at the patch, the change for check_cfg() is 32 lines.
> 
> I did, actually. And I already explained what I don't like about it:
> eagerness. check_cfg() is not the right place for this, if we want to
> support dead code elimination and BPF CO-RE-based feature gating.
> Which your patches clearly violate, so I don't like them, sorry.
> 
> We made this eagerness mistake with global subprogs verification
> previously, and had to switch it to lazy on-demand global subprog
> validation. I think we should preserve this lazy approach going
> forward.

In this context tags have same detection power as current changes for check_cfg(),
it is not possible to remove tag using dead code elimination.
So I really don't see any advantages in the context of this particular issue.

[...]

Re: Packet pointer invalidation and subprograms

[Andrii Nakryiko]

On Fri, Dec 6, 2024 at 8:20 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Dec 6, 2024 at 8:13 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Fri, Dec 6, 2024 at 8:08 AM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Thu, Dec 5, 2024 at 10:23 PM Andrii Nakryiko
> > > <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > On Thu, Dec 5, 2024 at 8:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > >
> > > > > On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> > > > > > On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > > >
> > > > > > > so I went ahead and the fix does look simple:
> > > > > > > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> > > > > >
> > > > > > Looks simple enough to me.
> > > > > > Ship it for bpf tree.
> > > > > > If we can come up with something better we can do it later in bpf-next.
> > > > > >
> > > > > > I very much prefer to avoid complexity as much as possible.
> > > > >
> > > > > Sent the patch-set for "simple".
> > > > > It is better then "dumb" by any metric anyways.
> > > > > Will try what Andrii suggests, as allowing calling global sub-programs
> > > > > from non-sleepable context sounds interesting.
> > > > >
> > > >
> > > > I haven't looked at your patches yet, but keep in mind another gotcha
> > > > with subprograms: they can be freplace'd by another BPF program
> > > > (clearly freplace programs were a successful reduction of
> > > > complexity... ;)
> > > >
> > > > What this means in practice is whatever deductions you get out of
> > > > analyzing any specific original subprogram might be violated by
> > > > freplace program if we don't enforce them during freplace attachment.
> > > >
> > > >
> > > > Anyways, I came here to say that I think I have a much simpler
> > > > solution that won't require big changes to the BPF verifier: tags. We
> > > > can shift the burden to the user having to declare the intent upfront
> > > > through subprog tags. And then, during verification of that global
> > > > subprog, the verifier can enforce that only explicitly declared side
> > > > effects can be enacted by the subprogram's code (taking into account
> > > > lazy dead code detection logic).
> > > >
> > > > We already take advantage of declarative tags for global subprog args
> > > > (__arg_trusted, etc), we can do the same for the function itself. We
> > > > can have __subprog_invalidates_all_pkt_pointers tag (and yes, I do
> > > > insist on this laconic name, of course), and during verification of
> > > > subprogram we just make sure that subprog was annotated as such, if
> > > > one of those fancy helpers is called directly in subprog itself or
> > > > transitively through any of *actually* called subprogs.
> > >
> > > tags for args was an aid to the verifier. Nothing is broken without them.
> > > Here it's about correctness.
> > > So we cannot use tags to solve this case.
> >
> > Hm.. Just like without an arg tag, verifier would conservatively
> > assume that `struct task_struct *task` global subprog argument is just
> > some opaque memory, not really a task, and would verify that argument
> > and code working with it as such. If a user did something that
> > required extra task_struct semantics, then that would be a
> > verification error. Unless the user added __arg_trusted, of course.
> >
> > Same thing here. We *assume* that global subprog doesn't have this
> > packet pointers side effect. If later during verification it turns out
> > it does have this effect -- this is an error and subprog gets
> > rejected. Unless the user provided
> > __subprog_invalidates_all_pkt_pointers, of course. Same thing.
>
> So depending on the order of walking the progs, compiler layout,
> static vs global the extra tag is either mandatory or not.

How so? If the verifier can *reach* one of those special helpers
during verification, then this tag would be required *for global
subprog*.

Or, *importantly*, if user anticipates that "freplace-ment" BPF
program for such subprog might need to invalidate packet pointers, but
the default subprog implementation doesn't actually call any of those
special helpers, user can just explicitly say that "yes, this subprog
should be treated as such that invalidates pkt pointers". With your
approach there is no way to even express this, unless you hack default
subprog implementation to intentionally have reachable
pkt-invalidating helper, but not really call it at runtime.

Think about some more advanced XDP chainer approach, where replacement
slots would need this pkt invalidation capabilities (but default
subprogs just are no-ops).

> That is horrible UX. I really don't like moving the burden to the user
> when the verifier can see it all.

I disagree, but it doesn't matter. It's being clear and explicit about
functionality that global subprog (verified in isolation) needs right
now or might need later (e.g., due to freplace-ment)

> arg_ctx is different. The verifier just doesn't have the knowledge.

No, it's not. It's conceptually absolutely the same. Verifier can
derive that global subprog arg has to be a trusted pointer. It's just
that with pkt invalidation it's trivial enough to detect (crudely and
eagerly, but still) in check_cfg(), while for trusted pointers you
can't take this shortcut.

I don't like the check_cfg()-based approach, it's hacky and subpar
workaround, and goes against all the lazy verification philosophy we
pursued with BPF CO-RE. I'm happy to discuss this offline if that will
be easier to get through all the nuance, but if you guys insist, so be
it.

Re: Packet pointer invalidation and subprograms

[Andrii Nakryiko]

On Fri, Dec 6, 2024 at 9:29 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2024-12-06 at 08:08 -0800, Andrii Nakryiko wrote:
>
> [...]
>
> > The tags would be that generalizable side effect declaration approach,
> > so seems worth it to set a uniform approach.
> >
> > > Please take a look at the patch, the change for check_cfg() is 32 lines.
> >
> > I did, actually. And I already explained what I don't like about it:
> > eagerness. check_cfg() is not the right place for this, if we want to
> > support dead code elimination and BPF CO-RE-based feature gating.
> > Which your patches clearly violate, so I don't like them, sorry.
> >
> > We made this eagerness mistake with global subprogs verification
> > previously, and had to switch it to lazy on-demand global subprog
> > validation. I think we should preserve this lazy approach going
> > forward.
>
> In this context tags have same detection power as current changes for check_cfg(),

You keep ignoring the eagerness issue. I can't decide whether you
think *it makes no difference* (I disagree, but whatever), or you *see
no difference* (in which case let me know and I can explain with some
simple example).

> it is not possible to remove tag using dead code elimination.

That's not the point of the tag to be dynamically adjustable. It's the
opposite. It's something that the user declares upfront, and this is
being enforced by the verifier (to prevent user errors, for example).
If the user wants to have a "dynamic tag", they can have two global
subprogs, one with and one without the tag, and pick which one should
be called through, e.g., .rodata feature flag variable. I.e., make
this decision outside of global subprog itself.

> So I really don't see any advantages in the context of this particular issue.

See also my reply to Alexei, and keep in mind freplace scenario, as
one of the things your approach can't support.

>
> [...]
>

Re: Packet pointer invalidation and subprograms

[Eduard Zingerman]

On Fri, 2024-12-06 at 09:46 -0800, Andrii Nakryiko wrote:
> On Fri, Dec 6, 2024 at 9:29 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Fri, 2024-12-06 at 08:08 -0800, Andrii Nakryiko wrote:
> > 
> > [...]
> > 
> > > The tags would be that generalizable side effect declaration approach,
> > > so seems worth it to set a uniform approach.
> > > 
> > > > Please take a look at the patch, the change for check_cfg() is 32 lines.
> > > 
> > > I did, actually. And I already explained what I don't like about it:
> > > eagerness. check_cfg() is not the right place for this, if we want to
> > > support dead code elimination and BPF CO-RE-based feature gating.
> > > Which your patches clearly violate, so I don't like them, sorry.
> > > 
> > > We made this eagerness mistake with global subprogs verification
> > > previously, and had to switch it to lazy on-demand global subprog
> > > validation. I think we should preserve this lazy approach going
> > > forward.
> > 
> > In this context tags have same detection power as current changes for check_cfg(),
> 
> You keep ignoring the eagerness issue. I can't decide whether you
> think *it makes no difference* (I disagree, but whatever), or you *see
> no difference* (in which case let me know and I can explain with some
> simple example).

In the context of the packet pointer invalidation I see no difference.
Tags are as eager as check_cfg() traversal.

> > it is not possible to remove tag using dead code elimination.
> 
> That's not the point of the tag to be dynamically adjustable. It's the
> opposite. It's something that the user declares upfront, and this is
> being enforced by the verifier (to prevent user errors, for example).
> If the user wants to have a "dynamic tag", they can have two global
> subprogs, one with and one without the tag, and pick which one should
> be called through, e.g., .rodata feature flag variable. I.e., make
> this decision outside of global subprog itself.
> 
> > So I really don't see any advantages in the context of this particular issue.
> 
> See also my reply to Alexei, and keep in mind freplace scenario, as
> one of the things your approach can't support.

Some freplace related mark will have to be present after program verification.
It might be in a form of a tag, or in a form of an additional bit in
an auxiliary structure. There would be code to check this with both approaches.

Re: Packet pointer invalidation and subprograms

[Andrii Nakryiko]

On Fri, Dec 6, 2024 at 9:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2024-12-06 at 09:46 -0800, Andrii Nakryiko wrote:
> > On Fri, Dec 6, 2024 at 9:29 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Fri, 2024-12-06 at 08:08 -0800, Andrii Nakryiko wrote:
> > >
> > > [...]
> > >
> > > > The tags would be that generalizable side effect declaration approach,
> > > > so seems worth it to set a uniform approach.
> > > >
> > > > > Please take a look at the patch, the change for check_cfg() is 32 lines.
> > > >
> > > > I did, actually. And I already explained what I don't like about it:
> > > > eagerness. check_cfg() is not the right place for this, if we want to
> > > > support dead code elimination and BPF CO-RE-based feature gating.
> > > > Which your patches clearly violate, so I don't like them, sorry.
> > > >
> > > > We made this eagerness mistake with global subprogs verification
> > > > previously, and had to switch it to lazy on-demand global subprog
> > > > validation. I think we should preserve this lazy approach going
> > > > forward.
> > >
> > > In this context tags have same detection power as current changes for check_cfg(),
> >
> > You keep ignoring the eagerness issue. I can't decide whether you
> > think *it makes no difference* (I disagree, but whatever), or you *see
> > no difference* (in which case let me know and I can explain with some
> > simple example).
>
> In the context of the packet pointer invalidation I see no difference.
> Tags are as eager as check_cfg() traversal.

Goodness, Eduard...

static __noinline void maybe_trigger_pkt_invalidation(bool do_trigger)
{
    if (do_trigger)
       bpf_whatever_helper_triggers_pkt_invalidation();
    /* presumably do something useful here */
}

__weak /*global*/ int global_no_pkt_invalidation(void)
{
    maybe_trigger_pkt_invalidation(false); /* DO NOT trigger */
    return 0;
}

__weak /*global*/  __subprog_triggers_pkt_invalidation_and_I_mean_it
int global_make_pkt_invalidation_great(void)
{
    maybe_trigger_pkt_invalidation(true); /* DO trigger */
    return 0;
}

What does your check_cfg() say about global_no_pkt_invalidation()? Can
it trigger pkt invalidation or not?

>
> > > it is not possible to remove tag using dead code elimination.
> >
> > That's not the point of the tag to be dynamically adjustable. It's the
> > opposite. It's something that the user declares upfront, and this is
> > being enforced by the verifier (to prevent user errors, for example).
> > If the user wants to have a "dynamic tag", they can have two global
> > subprogs, one with and one without the tag, and pick which one should
> > be called through, e.g., .rodata feature flag variable. I.e., make
> > this decision outside of global subprog itself.
> >
> > > So I really don't see any advantages in the context of this particular issue.
> >
> > See also my reply to Alexei, and keep in mind freplace scenario, as
> > one of the things your approach can't support.
>
> Some freplace related mark will have to be present after program verification.
> It might be in a form of a tag, or in a form of an additional bit in
> an auxiliary structure. There would be code to check this with both approaches.
>

tag vs check_cfg() is not about that aspect, in both cases we need to
recod whether subprog can trigger pkt invalidation or not.

It's about whether we derive this (and then where, in check_cfg() or
in proper verification pass), or whether the user declares it and we
enforce that in the verifier.

Re: Packet pointer invalidation and subprograms

[Kumar Kartikeya Dwivedi]

On Fri, 6 Dec 2024 at 18:42, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
>
> On Fri, Dec 6, 2024 at 8:20 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Fri, Dec 6, 2024 at 8:13 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Fri, Dec 6, 2024 at 8:08 AM Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > On Thu, Dec 5, 2024 at 10:23 PM Andrii Nakryiko
> > > > <andrii.nakryiko@gmail.com> wrote:
> > > > >
> > > > > On Thu, Dec 5, 2024 at 8:07 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > >
> > > > > > On Thu, 2024-12-05 at 17:44 -0800, Alexei Starovoitov wrote:
> > > > > > > On Thu, Dec 5, 2024 at 4:29 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > > > >
> > > > > > > > so I went ahead and the fix does look simple:
> > > > > > > > https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
> > > > > > >
> > > > > > > Looks simple enough to me.
> > > > > > > Ship it for bpf tree.
> > > > > > > If we can come up with something better we can do it later in bpf-next.
> > > > > > >
> > > > > > > I very much prefer to avoid complexity as much as possible.
> > > > > >
> > > > > > Sent the patch-set for "simple".
> > > > > > It is better then "dumb" by any metric anyways.
> > > > > > Will try what Andrii suggests, as allowing calling global sub-programs
> > > > > > from non-sleepable context sounds interesting.
> > > > > >
> > > > >
> > > > > I haven't looked at your patches yet, but keep in mind another gotcha
> > > > > with subprograms: they can be freplace'd by another BPF program
> > > > > (clearly freplace programs were a successful reduction of
> > > > > complexity... ;)
> > > > >
> > > > > What this means in practice is whatever deductions you get out of
> > > > > analyzing any specific original subprogram might be violated by
> > > > > freplace program if we don't enforce them during freplace attachment.
> > > > >
> > > > >
> > > > > Anyways, I came here to say that I think I have a much simpler
> > > > > solution that won't require big changes to the BPF verifier: tags. We
> > > > > can shift the burden to the user having to declare the intent upfront
> > > > > through subprog tags. And then, during verification of that global
> > > > > subprog, the verifier can enforce that only explicitly declared side
> > > > > effects can be enacted by the subprogram's code (taking into account
> > > > > lazy dead code detection logic).
> > > > >
> > > > > We already take advantage of declarative tags for global subprog args
> > > > > (__arg_trusted, etc), we can do the same for the function itself. We
> > > > > can have __subprog_invalidates_all_pkt_pointers tag (and yes, I do
> > > > > insist on this laconic name, of course), and during verification of
> > > > > subprogram we just make sure that subprog was annotated as such, if
> > > > > one of those fancy helpers is called directly in subprog itself or
> > > > > transitively through any of *actually* called subprogs.
> > > >
> > > > tags for args was an aid to the verifier. Nothing is broken without them.
> > > > Here it's about correctness.
> > > > So we cannot use tags to solve this case.
> > >
> > > Hm.. Just like without an arg tag, verifier would conservatively
> > > assume that `struct task_struct *task` global subprog argument is just
> > > some opaque memory, not really a task, and would verify that argument
> > > and code working with it as such. If a user did something that
> > > required extra task_struct semantics, then that would be a
> > > verification error. Unless the user added __arg_trusted, of course.
> > >
> > > Same thing here. We *assume* that global subprog doesn't have this
> > > packet pointers side effect. If later during verification it turns out
> > > it does have this effect -- this is an error and subprog gets
> > > rejected. Unless the user provided
> > > __subprog_invalidates_all_pkt_pointers, of course. Same thing.
> >
> > So depending on the order of walking the progs, compiler layout,
> > static vs global the extra tag is either mandatory or not.
>
> How so? If the verifier can *reach* one of those special helpers
> during verification, then this tag would be required *for global
> subprog*.
>
> Or, *importantly*, if user anticipates that "freplace-ment" BPF
> program for such subprog might need to invalidate packet pointers, but
> the default subprog implementation doesn't actually call any of those
> special helpers, user can just explicitly say that "yes, this subprog
> should be treated as such that invalidates pkt pointers". With your
> approach there is no way to even express this, unless you hack default
> subprog implementation to intentionally have reachable
> pkt-invalidating helper, but not really call it at runtime.
>
> Think about some more advanced XDP chainer approach, where replacement
> slots would need this pkt invalidation capabilities (but default
> subprogs just are no-ops).

I think Andrii has a good point here, this would be an entirely
plausible scenario,
and with summarization alone we would reject such freplace. Then, the user,
due to the lack of explicit tagging, will insert an extra helper call
that does nothing
just to indicate "invalidates all packets" side effect when it could
have been done explicitly.
So in effect they just explicitly declared their intent, not through a
tag, but through code.

It might be that we can have a mix of both automatic detection and
such tagging, I was actually considering that this might be better (it
avoids extra burden for the common case, and allows explicit tagging
where necessary),  but then if the preference is to contain complexity
in the verifier, one wonders why not just explicitly tag anyway and
not add extra code? The same can be done for sleepable case in theory.


>
> > That is horrible UX. I really don't like moving the burden to the user
> > when the verifier can see it all.
>
> I disagree, but it doesn't matter. It's being clear and explicit about
> functionality that global subprog (verified in isolation) needs right
> now or might need later (e.g., due to freplace-ment)
>
> > arg_ctx is different. The verifier just doesn't have the knowledge.
>
> No, it's not. It's conceptually absolutely the same. Verifier can
> derive that global subprog arg has to be a trusted pointer. It's just
> that with pkt invalidation it's trivial enough to detect (crudely and
> eagerly, but still) in check_cfg(), while for trusted pointers you
> can't take this shortcut.
>
> I don't like the check_cfg()-based approach, it's hacky and subpar
> workaround, and goes against all the lazy verification philosophy we
> pursued with BPF CO-RE. I'm happy to discuss this offline if that will
> be easier to get through all the nuance, but if you guys insist, so be
> it.

Re: Packet pointer invalidation and subprograms

[Alexei Starovoitov]

On Fri, Dec 6, 2024 at 9:42 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
>
> Or, *importantly*, if user anticipates that "freplace-ment" BPF
> program for such subprog might need to invalidate packet pointers, but
> the default subprog implementation doesn't actually call any of those
> special helpers, user can just explicitly say that "yes, this subprog
> should be treated as such that invalidates pkt pointers". With your
> approach there is no way to even express this, unless you hack default
> subprog implementation to intentionally have reachable
> pkt-invalidating helper, but not really call it at runtime.

Exactly.
This artificial issue can be easily solved without tags.
The nop subprog can have an empty call to bpf_skb_pull_data(skb, 0).
And it will be much more obvious to anyone reading the C code
instead of a magic tag.

> No, it's not. It's conceptually absolutely the same. Verifier can
> derive that global subprog arg has to be a trusted pointer. It's just
> that with pkt invalidation it's trivial enough to detect (crudely and
> eagerly, but still) in check_cfg(), while for trusted pointers you
> can't take this shortcut.

Not really. We only introduced the following tags:
__arg_ctx
__arg_trusted
__arg_arena
because the verifier cannot infer them.
We are _not_ going to introduce __arg_dynptr as we argued in the past.
Anything that can be expressed via normal C should stay in C.

Re: Packet pointer invalidation and subprograms

[Eduard Zingerman]

On Fri, 2024-12-06 at 10:10 -0800, Andrii Nakryiko wrote:

[...]

> > > You keep ignoring the eagerness issue. I can't decide whether you
> > > think *it makes no difference* (I disagree, but whatever), or you *see
> > > no difference* (in which case let me know and I can explain with some
> > > simple example).
> > 
> > In the context of the packet pointer invalidation I see no difference.
> > Tags are as eager as check_cfg() traversal.
> 
> Goodness, Eduard...
> 
> static __noinline void maybe_trigger_pkt_invalidation(bool do_trigger)
> {
>     if (do_trigger)
>        bpf_whatever_helper_triggers_pkt_invalidation();
>     /* presumably do something useful here */
> }
> 
> __weak /*global*/ int global_no_pkt_invalidation(void)
> {
>     maybe_trigger_pkt_invalidation(false); /* DO NOT trigger */
>     return 0;
> }
> 
> __weak /*global*/  __subprog_triggers_pkt_invalidation_and_I_mean_it
> int global_make_pkt_invalidation_great(void)
> {
>     maybe_trigger_pkt_invalidation(true); /* DO trigger */
>     return 0;
> }
> 
> What does your check_cfg() say about global_no_pkt_invalidation()? Can
> it trigger pkt invalidation or not?

Ok, I see your point, thank you for the example.

[...]

> > > > it is not possible to remove tag using dead code elimination.
> > > 
> > > That's not the point of the tag to be dynamically adjustable. It's the
> > > opposite. It's something that the user declares upfront, and this is
> > > being enforced by the verifier (to prevent user errors, for example).
> > > If the user wants to have a "dynamic tag", they can have two global
> > > subprogs, one with and one without the tag, and pick which one should
> > > be called through, e.g., .rodata feature flag variable. I.e., make
> > > this decision outside of global subprog itself.
> > > 
> > > > So I really don't see any advantages in the context of this particular issue.
> > > 
> > > See also my reply to Alexei, and keep in mind freplace scenario, as
> > > one of the things your approach can't support.
> > 
> > Some freplace related mark will have to be present after program verification.
> > It might be in a form of a tag, or in a form of an additional bit in
> > an auxiliary structure. There would be code to check this with both approaches.
> > 
> 
> tag vs check_cfg() is not about that aspect, in both cases we need to
> recod whether subprog can trigger pkt invalidation or not.
> 
> It's about whether we derive this (and then where, in check_cfg() or
> in proper verification pass), or whether the user declares it and we
> enforce that in the verifier.

So both approaches can handle freplace.

Re: Packet pointer invalidation and subprograms

[Kumar Kartikeya Dwivedi]

On Fri, 6 Dec 2024 at 19:26, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Dec 6, 2024 at 9:42 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> >
> > Or, *importantly*, if user anticipates that "freplace-ment" BPF
> > program for such subprog might need to invalidate packet pointers, but
> > the default subprog implementation doesn't actually call any of those
> > special helpers, user can just explicitly say that "yes, this subprog
> > should be treated as such that invalidates pkt pointers". With your
> > approach there is no way to even express this, unless you hack default
> > subprog implementation to intentionally have reachable
> > pkt-invalidating helper, but not really call it at runtime.
>
> Exactly.
> This artificial issue can be easily solved without tags.
> The nop subprog can have an empty call to bpf_skb_pull_data(skb, 0).
> And it will be much more obvious to anyone reading the C code
> instead of a magic tag.

Wouldn't it be less obvious? You would still need a fat comment
explaining why you're doing a dummy bpf_skb_pull_data, because
normally it wouldn't occur if it is to clear pkt pointers, and you
will say it's because it tells the verifier that it invalidates the
packet for the caller.

It would certainly be clear if we had a bpf_skb_clear_pkt_ptrs, which
would be a verifier built-in and no-op at runtime, but we don't. But
then that's the same as a tag.

>
> > No, it's not. It's conceptually absolutely the same. Verifier can
> > derive that global subprog arg has to be a trusted pointer. It's just
> > that with pkt invalidation it's trivial enough to detect (crudely and
> > eagerly, but still) in check_cfg(), while for trusted pointers you
> > can't take this shortcut.
>
> Not really. We only introduced the following tags:
> __arg_ctx
> __arg_trusted
> __arg_arena
> because the verifier cannot infer them.
> We are _not_ going to introduce __arg_dynptr as we argued in the past.
> Anything that can be expressed via normal C should stay in C.

Re: Packet pointer invalidation and subprograms

[Alexei Starovoitov]

On Fri, Dec 6, 2024 at 10:24 AM Kumar Kartikeya Dwivedi
<memxor@gmail.com> wrote:
>
> I think Andrii has a good point here, this would be an entirely
> plausible scenario,
> and with summarization alone we would reject such freplace. Then, the user,
> due to the lack of explicit tagging, will insert an extra helper call
> that does nothing
> just to indicate "invalidates all packets" side effect when it could
> have been done explicitly.
> So in effect they just explicitly declared their intent, not through a
> tag, but through code.

Exactly and that's how it should be done. Through the code.
C is the language to do that. Magic tag is an extra language hack
that people need to learn, remember, teach others, etc.

We've introduced __arg_ctx and so far the only adopters were
the programs where Andrii added it by himself.
Anyone reading it has no idea what __arg* do.
It's all magic. While C has clear meaning.

Re: Packet pointer invalidation and subprograms

[Alexei Starovoitov]

On Fri, Dec 6, 2024 at 10:30 AM Kumar Kartikeya Dwivedi
<memxor@gmail.com> wrote:
>
> On Fri, 6 Dec 2024 at 19:26, Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Fri, Dec 6, 2024 at 9:42 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > >
> > > Or, *importantly*, if user anticipates that "freplace-ment" BPF
> > > program for such subprog might need to invalidate packet pointers, but
> > > the default subprog implementation doesn't actually call any of those
> > > special helpers, user can just explicitly say that "yes, this subprog
> > > should be treated as such that invalidates pkt pointers". With your
> > > approach there is no way to even express this, unless you hack default
> > > subprog implementation to intentionally have reachable
> > > pkt-invalidating helper, but not really call it at runtime.
> >
> > Exactly.
> > This artificial issue can be easily solved without tags.
> > The nop subprog can have an empty call to bpf_skb_pull_data(skb, 0).
> > And it will be much more obvious to anyone reading the C code
> > instead of a magic tag.
>
> Wouldn't it be less obvious? You would still need a fat comment
> explaining why you're doing a dummy bpf_skb_pull_data, because
> normally it wouldn't occur if it is to clear pkt pointers, and you
> will say it's because it tells the verifier that it invalidates the
> packet for the caller.
>
> It would certainly be clear if we had a bpf_skb_clear_pkt_ptrs, which
> would be a verifier built-in and no-op at runtime, but we don't. But
> then that's the same as a tag.

It's not at all the same. It's C vs our special C language extension
that gcc still doesn't support.

Re: Packet pointer invalidation and subprograms

[Kumar Kartikeya Dwivedi]

On Fri, 6 Dec 2024 at 19:30, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Dec 6, 2024 at 10:24 AM Kumar Kartikeya Dwivedi
> <memxor@gmail.com> wrote:
> >
> > I think Andrii has a good point here, this would be an entirely
> > plausible scenario,
> > and with summarization alone we would reject such freplace. Then, the user,
> > due to the lack of explicit tagging, will insert an extra helper call
> > that does nothing
> > just to indicate "invalidates all packets" side effect when it could
> > have been done explicitly.
> > So in effect they just explicitly declared their intent, not through a
> > tag, but through code.
>
> Exactly and that's how it should be done. Through the code.
> C is the language to do that. Magic tag is an extra language hack
> that people need to learn, remember, teach others, etc.

I agree that ascertaining stuff from C itself is friendlier with no
extra burden,
but that is only as long as the C expression itself has a clear meaning.

When you need to write extra stuff to tell the verifier something, C
or not C doesn't really matter.
Like your example, people will still need to remember and tell others
that to ensure they can freplace
with a pkt invalidating global prog, they need this dummy
bpf_skb_pull_data trick.

The medium used to express the intent at that point matters less,
the bigger picture is that the user still needs to communicate it somehow.

We can agree or disagree whether tags are the better or worse way to
do it, but you're doing the same thing in both cases.

>
> We've introduced __arg_ctx and so far the only adopters were
> the programs where Andrii added it by himself.
> Anyone reading it has no idea what __arg* do.
> It's all magic. While C has clear meaning.