XDP bpf_tail_call_redirect(): yea or nay?

XDP bpf_tail_call_redirect(): yea or nay?

[Björn Töpel]

Before I start hacking on this, I might as well check with the XDP
folks if this considered a crappy idea or not. :-)

The XDP redirect flow for a packet is typical a dance of
bpf_redirect_map() that updates the bpf_redirect_info structure with
maps type/items, which is then followed by an xdp_do_redirect(). That
function takes an action based on the bpf_redirect_info content.

I'd like to get rid of the xdp_do_redirect() call, and the
bpf_redirect_info (per-cpu) lookup. The idea is to introduce a new
(oh-no!) XDP action, say, XDP_CONSUMED and a built-in helper with
tail-call semantics.

Something across the lines of:

--8<--

struct {
        __uint(type, BPF_MAP_TYPE_XSKMAP);
        __uint(max_entries, MAX_SOCKS);
        __uint(key_size, sizeof(int));
        __uint(value_size, sizeof(int));
} xsks_map SEC(".maps");

SEC("xdp1")
int xdp_prog1(struct xdp_md *ctx)
{
        bpf_tail_call_redirect(ctx, &xsks_map, 0);
        // Redirect the packet to an AF_XDP socket at entry 0 of the
        // map.
        //
        // After a successful call, ctx is said to be
        // consumed. XDP_CONSUMED will be returned by the program.
        // Note that if the call is not successful, the buffer is
        // still valid.
        //
        // XDP_CONSUMED in the driver means that the driver should not
        // issue an xdp_do_direct() call, but only xdp_flush().
        //
        // The verifier need to be taught that XDP_CONSUMED can only
        // be returned "indirectly", meaning a bpf_tail_call_XXX()
        // call. An explicit "return XDP_CONSUMED" should be
        // rejected. Can that be implemented?
        return XDP_PASS; // or any other valid action.
}

-->8--

The bpf_tail_call_redirect() would work with all redirectable maps.

Thoughts? Tomatoes? Pitchforks?


Björn

Re: XDP bpf_tail_call_redirect(): yea or nay?

[Toke Høiland-Jørgensen]

Björn Töpel <bjorn.topel@gmail.com> writes:

> Before I start hacking on this, I might as well check with the XDP
> folks if this considered a crappy idea or not. :-)
>
> The XDP redirect flow for a packet is typical a dance of
> bpf_redirect_map() that updates the bpf_redirect_info structure with
> maps type/items, which is then followed by an xdp_do_redirect(). That
> function takes an action based on the bpf_redirect_info content.
>
> I'd like to get rid of the xdp_do_redirect() call, and the
> bpf_redirect_info (per-cpu) lookup. The idea is to introduce a new
> (oh-no!) XDP action, say, XDP_CONSUMED and a built-in helper with
> tail-call semantics.
>
> Something across the lines of:
>
> --8<--
>
> struct {
>         __uint(type, BPF_MAP_TYPE_XSKMAP);
>         __uint(max_entries, MAX_SOCKS);
>         __uint(key_size, sizeof(int));
>         __uint(value_size, sizeof(int));
> } xsks_map SEC(".maps");
>
> SEC("xdp1")
> int xdp_prog1(struct xdp_md *ctx)
> {
>         bpf_tail_call_redirect(ctx, &xsks_map, 0);
>         // Redirect the packet to an AF_XDP socket at entry 0 of the
>         // map.
>         //
>         // After a successful call, ctx is said to be
>         // consumed. XDP_CONSUMED will be returned by the program.
>         // Note that if the call is not successful, the buffer is
>         // still valid.
>         //
>         // XDP_CONSUMED in the driver means that the driver should not
>         // issue an xdp_do_direct() call, but only xdp_flush().
>         //
>         // The verifier need to be taught that XDP_CONSUMED can only
>         // be returned "indirectly", meaning a bpf_tail_call_XXX()
>         // call. An explicit "return XDP_CONSUMED" should be
>         // rejected. Can that be implemented?
>         return XDP_PASS; // or any other valid action.
> }
>
> -->8--
>
> The bpf_tail_call_redirect() would work with all redirectable maps.
>
> Thoughts? Tomatoes? Pitchforks?

The above answers the 'what'. Might be easier to evaluate if you also
included the 'why'? :)

-Toke

Re: XDP bpf_tail_call_redirect(): yea or nay?

[Björn Töpel]

On Thu, 7 May 2020 at 15:44, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> Björn Töpel <bjorn.topel@gmail.com> writes:
>
> > Before I start hacking on this, I might as well check with the XDP
> > folks if this considered a crappy idea or not. :-)
> >
> > The XDP redirect flow for a packet is typical a dance of
> > bpf_redirect_map() that updates the bpf_redirect_info structure with
> > maps type/items, which is then followed by an xdp_do_redirect(). That
> > function takes an action based on the bpf_redirect_info content.
> >
> > I'd like to get rid of the xdp_do_redirect() call, and the
> > bpf_redirect_info (per-cpu) lookup. The idea is to introduce a new
> > (oh-no!) XDP action, say, XDP_CONSUMED and a built-in helper with
> > tail-call semantics.
> >
> > Something across the lines of:
> >
> > --8<--
> >
> > struct {
> >         __uint(type, BPF_MAP_TYPE_XSKMAP);
> >         __uint(max_entries, MAX_SOCKS);
> >         __uint(key_size, sizeof(int));
> >         __uint(value_size, sizeof(int));
> > } xsks_map SEC(".maps");
> >
> > SEC("xdp1")
> > int xdp_prog1(struct xdp_md *ctx)
> > {
> >         bpf_tail_call_redirect(ctx, &xsks_map, 0);
> >         // Redirect the packet to an AF_XDP socket at entry 0 of the
> >         // map.
> >         //
> >         // After a successful call, ctx is said to be
> >         // consumed. XDP_CONSUMED will be returned by the program.
> >         // Note that if the call is not successful, the buffer is
> >         // still valid.
> >         //
> >         // XDP_CONSUMED in the driver means that the driver should not
> >         // issue an xdp_do_direct() call, but only xdp_flush().
> >         //
> >         // The verifier need to be taught that XDP_CONSUMED can only
> >         // be returned "indirectly", meaning a bpf_tail_call_XXX()
> >         // call. An explicit "return XDP_CONSUMED" should be
> >         // rejected. Can that be implemented?
> >         return XDP_PASS; // or any other valid action.
> > }
> >
> > -->8--
> >
> > The bpf_tail_call_redirect() would work with all redirectable maps.
> >
> > Thoughts? Tomatoes? Pitchforks?
>
> The above answers the 'what'. Might be easier to evaluate if you also
> included the 'why'? :)
>

Ah! Sorry! Performance, performance, performance. Getting rid of a
bunch of calls/instructions per packet, which helps my (AF_XDP) case.
This would be faster than the regular REDIRECT path. Today, in
bpf_redirect_map(), instead of actually performing the action, we
populate the bpf_redirect_info structure, just to look up the action
again in xdp_do_redirect().

I'm pretty certain this would be a gain for AF_XDP (quite easy to do a
quick hack, and measure). It would also shave off the same amount of
instructions for "vanilla" XDP_REDIRECT cases. The bigger issue; Is
this new semantic something people would be comfortable being added to
XDP.


Cheers,
Björn

Re: XDP bpf_tail_call_redirect(): yea or nay?

[Toke Høiland-Jørgensen]

Björn Töpel <bjorn.topel@gmail.com> writes:

> On Thu, 7 May 2020 at 15:44, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>>
>> Björn Töpel <bjorn.topel@gmail.com> writes:
>>
>> > Before I start hacking on this, I might as well check with the XDP
>> > folks if this considered a crappy idea or not. :-)
>> >
>> > The XDP redirect flow for a packet is typical a dance of
>> > bpf_redirect_map() that updates the bpf_redirect_info structure with
>> > maps type/items, which is then followed by an xdp_do_redirect(). That
>> > function takes an action based on the bpf_redirect_info content.
>> >
>> > I'd like to get rid of the xdp_do_redirect() call, and the
>> > bpf_redirect_info (per-cpu) lookup. The idea is to introduce a new
>> > (oh-no!) XDP action, say, XDP_CONSUMED and a built-in helper with
>> > tail-call semantics.
>> >
>> > Something across the lines of:
>> >
>> > --8<--
>> >
>> > struct {
>> >         __uint(type, BPF_MAP_TYPE_XSKMAP);
>> >         __uint(max_entries, MAX_SOCKS);
>> >         __uint(key_size, sizeof(int));
>> >         __uint(value_size, sizeof(int));
>> > } xsks_map SEC(".maps");
>> >
>> > SEC("xdp1")
>> > int xdp_prog1(struct xdp_md *ctx)
>> > {
>> >         bpf_tail_call_redirect(ctx, &xsks_map, 0);
>> >         // Redirect the packet to an AF_XDP socket at entry 0 of the
>> >         // map.
>> >         //
>> >         // After a successful call, ctx is said to be
>> >         // consumed. XDP_CONSUMED will be returned by the program.
>> >         // Note that if the call is not successful, the buffer is
>> >         // still valid.
>> >         //
>> >         // XDP_CONSUMED in the driver means that the driver should not
>> >         // issue an xdp_do_direct() call, but only xdp_flush().
>> >         //
>> >         // The verifier need to be taught that XDP_CONSUMED can only
>> >         // be returned "indirectly", meaning a bpf_tail_call_XXX()
>> >         // call. An explicit "return XDP_CONSUMED" should be
>> >         // rejected. Can that be implemented?
>> >         return XDP_PASS; // or any other valid action.
>> > }
>> >
>> > -->8--
>> >
>> > The bpf_tail_call_redirect() would work with all redirectable maps.
>> >
>> > Thoughts? Tomatoes? Pitchforks?
>>
>> The above answers the 'what'. Might be easier to evaluate if you also
>> included the 'why'? :)
>>
>
> Ah! Sorry! Performance, performance, performance. Getting rid of a
> bunch of calls/instructions per packet, which helps my (AF_XDP) case.
> This would be faster than the regular REDIRECT path. Today, in
> bpf_redirect_map(), instead of actually performing the action, we
> populate the bpf_redirect_info structure, just to look up the action
> again in xdp_do_redirect().
>
> I'm pretty certain this would be a gain for AF_XDP (quite easy to do a
> quick hack, and measure). It would also shave off the same amount of
> instructions for "vanilla" XDP_REDIRECT cases. The bigger issue; Is
> this new semantic something people would be comfortable being added to
> XDP.

Well, my immediate thought would be that the added complexity would not
be worth it, because:

- A new action would mean either you'd need to patch all drivers or
  (more likely) we'd end up with yet another difference between drivers'
  XDP support.

- BPF developers would suddenly have to choose - do this new faster
  thing, or be compatible? And manage the choice based on drivers they
  expect to run on, etc. This was already confusing with
  bpf_redirect()/bpf_redirect_map(), and this would introduce a third
  option!

So in light of this, I'd say the performance benefit would have to be
quite substantial for this to be worth it. Which we won't know until you
try it, I guess :)

Thinking of alternatives - couldn't you shoe-horn this into the existing
helper and return code? Say, introduce an IMMEDIATE_RETURN flag to the
existing helpers, which would change the behaviour to the tail call
semantics. When used, xdp_do_redirect() would then return immediately
(or you could even turn xdp_do_redirect() into an inlined wrapper that
checks the flag before issuing a CALL to the existing function). Any
reason why that wouldn't work?

-Toke

Re: XDP bpf_tail_call_redirect(): yea or nay?

[John Fastabend]

Toke Høiland-Jørgensen wrote:
> Björn Töpel <bjorn.topel@gmail.com> writes:
> 
> > On Thu, 7 May 2020 at 15:44, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
> >>
> >> Björn Töpel <bjorn.topel@gmail.com> writes:
> >>
> >> > Before I start hacking on this, I might as well check with the XDP
> >> > folks if this considered a crappy idea or not. :-)
> >> >
> >> > The XDP redirect flow for a packet is typical a dance of
> >> > bpf_redirect_map() that updates the bpf_redirect_info structure with
> >> > maps type/items, which is then followed by an xdp_do_redirect(). That
> >> > function takes an action based on the bpf_redirect_info content.
> >> >
> >> > I'd like to get rid of the xdp_do_redirect() call, and the
> >> > bpf_redirect_info (per-cpu) lookup. The idea is to introduce a new
> >> > (oh-no!) XDP action, say, XDP_CONSUMED and a built-in helper with
> >> > tail-call semantics.
> >> >
> >> > Something across the lines of:
> >> >
> >> > --8<--
> >> >
> >> > struct {
> >> >         __uint(type, BPF_MAP_TYPE_XSKMAP);
> >> >         __uint(max_entries, MAX_SOCKS);
> >> >         __uint(key_size, sizeof(int));
> >> >         __uint(value_size, sizeof(int));
> >> > } xsks_map SEC(".maps");
> >> >
> >> > SEC("xdp1")
> >> > int xdp_prog1(struct xdp_md *ctx)
> >> > {
> >> >         bpf_tail_call_redirect(ctx, &xsks_map, 0);
> >> >         // Redirect the packet to an AF_XDP socket at entry 0 of the
> >> >         // map.
> >> >         //
> >> >         // After a successful call, ctx is said to be
> >> >         // consumed. XDP_CONSUMED will be returned by the program.
> >> >         // Note that if the call is not successful, the buffer is
> >> >         // still valid.
> >> >         //
> >> >         // XDP_CONSUMED in the driver means that the driver should not
> >> >         // issue an xdp_do_direct() call, but only xdp_flush().
> >> >         //
> >> >         // The verifier need to be taught that XDP_CONSUMED can only
> >> >         // be returned "indirectly", meaning a bpf_tail_call_XXX()
> >> >         // call. An explicit "return XDP_CONSUMED" should be
> >> >         // rejected. Can that be implemented?
> >> >         return XDP_PASS; // or any other valid action.
> >> > }

I'm wondering if we can teach the verifier to recognize tail calls,

int xdp_prog1(struct xdp_md *ctx)
{
	return xdp_do_redirect(ctx, &xsks_map, 0);
}

This would be useful for normal calls as well. I guess the question here
is would a tail call be sufficient for above case or do you need the
'return XDP_PASS' at the end? If so maybe we could fold it into the
helper somehow.

I think it would also address Toke's concerns, no new action so
bpf developers can just develope like normal but "smart" developers
will try do calls as tail calls. Not sure it can be done without
driver changes though.

> >> >
> >> > -->8--
> >> >
> >> > The bpf_tail_call_redirect() would work with all redirectable maps.
> >> >
> >> > Thoughts? Tomatoes? Pitchforks?
> >>
> >> The above answers the 'what'. Might be easier to evaluate if you also
> >> included the 'why'? :)
> >>
> >
> > Ah! Sorry! Performance, performance, performance. Getting rid of a
> > bunch of calls/instructions per packet, which helps my (AF_XDP) case.
> > This would be faster than the regular REDIRECT path. Today, in
> > bpf_redirect_map(), instead of actually performing the action, we
> > populate the bpf_redirect_info structure, just to look up the action
> > again in xdp_do_redirect().
> >
> > I'm pretty certain this would be a gain for AF_XDP (quite easy to do a
> > quick hack, and measure). It would also shave off the same amount of
> > instructions for "vanilla" XDP_REDIRECT cases. The bigger issue; Is
> > this new semantic something people would be comfortable being added to
> > XDP.
> 
> Well, my immediate thought would be that the added complexity would not
> be worth it, because:
> 
> - A new action would mean either you'd need to patch all drivers or
>   (more likely) we'd end up with yet another difference between drivers'
>   XDP support.
> 
> - BPF developers would suddenly have to choose - do this new faster
>   thing, or be compatible? And manage the choice based on drivers they
>   expect to run on, etc. This was already confusing with
>   bpf_redirect()/bpf_redirect_map(), and this would introduce a third
>   option!
> 
> So in light of this, I'd say the performance benefit would have to be
> quite substantial for this to be worth it. Which we won't know until you
> try it, I guess :)

Knowing the number would be useful. But if it can be done in general
way it may not need to be as high because its not a special xdp thing.

> 
> Thinking of alternatives - couldn't you shoe-horn this into the existing
> helper and return code? Say, introduce an IMMEDIATE_RETURN flag to the
> existing helpers, which would change the behaviour to the tail call
> semantics. When used, xdp_do_redirect() would then return immediately
> (or you could even turn xdp_do_redirect() into an inlined wrapper that
> checks the flag before issuing a CALL to the existing function). Any
> reason why that wouldn't work?

I think it would work but I it would be even nicer if clang, verifier
and jit caught the tail call pattern and did it automatically.

> 
> -Toke
> 

Re: XDP bpf_tail_call_redirect(): yea or nay?

[Toke Høiland-Jørgensen]

John Fastabend <john.fastabend@gmail.com> writes:

> Toke Høiland-Jørgensen wrote:
>> Björn Töpel <bjorn.topel@gmail.com> writes:
>> 
>> > On Thu, 7 May 2020 at 15:44, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>> >>
>> >> Björn Töpel <bjorn.topel@gmail.com> writes:
>> >>
>> >> > Before I start hacking on this, I might as well check with the XDP
>> >> > folks if this considered a crappy idea or not. :-)
>> >> >
>> >> > The XDP redirect flow for a packet is typical a dance of
>> >> > bpf_redirect_map() that updates the bpf_redirect_info structure with
>> >> > maps type/items, which is then followed by an xdp_do_redirect(). That
>> >> > function takes an action based on the bpf_redirect_info content.
>> >> >
>> >> > I'd like to get rid of the xdp_do_redirect() call, and the
>> >> > bpf_redirect_info (per-cpu) lookup. The idea is to introduce a new
>> >> > (oh-no!) XDP action, say, XDP_CONSUMED and a built-in helper with
>> >> > tail-call semantics.
>> >> >
>> >> > Something across the lines of:
>> >> >
>> >> > --8<--
>> >> >
>> >> > struct {
>> >> >         __uint(type, BPF_MAP_TYPE_XSKMAP);
>> >> >         __uint(max_entries, MAX_SOCKS);
>> >> >         __uint(key_size, sizeof(int));
>> >> >         __uint(value_size, sizeof(int));
>> >> > } xsks_map SEC(".maps");
>> >> >
>> >> > SEC("xdp1")
>> >> > int xdp_prog1(struct xdp_md *ctx)
>> >> > {
>> >> >         bpf_tail_call_redirect(ctx, &xsks_map, 0);
>> >> >         // Redirect the packet to an AF_XDP socket at entry 0 of the
>> >> >         // map.
>> >> >         //
>> >> >         // After a successful call, ctx is said to be
>> >> >         // consumed. XDP_CONSUMED will be returned by the program.
>> >> >         // Note that if the call is not successful, the buffer is
>> >> >         // still valid.
>> >> >         //
>> >> >         // XDP_CONSUMED in the driver means that the driver should not
>> >> >         // issue an xdp_do_direct() call, but only xdp_flush().
>> >> >         //
>> >> >         // The verifier need to be taught that XDP_CONSUMED can only
>> >> >         // be returned "indirectly", meaning a bpf_tail_call_XXX()
>> >> >         // call. An explicit "return XDP_CONSUMED" should be
>> >> >         // rejected. Can that be implemented?
>> >> >         return XDP_PASS; // or any other valid action.
>> >> > }
>
> I'm wondering if we can teach the verifier to recognize tail calls,
>
> int xdp_prog1(struct xdp_md *ctx)
> {
> 	return xdp_do_redirect(ctx, &xsks_map, 0);
> }
>
> This would be useful for normal calls as well. I guess the question here
> is would a tail call be sufficient for above case or do you need the
> 'return XDP_PASS' at the end? If so maybe we could fold it into the
> helper somehow.
>
> I think it would also address Toke's concerns, no new action so
> bpf developers can just develope like normal but "smart" developers
> will try do calls as tail calls.

This is certainly an interesting idea! Functional languages tend to
auto-optimise tail calls, so detecting them is certainly possible, at
least for the compiler. I suppose this could be a follow-on
optimisation, though, couldn't it? From the PoV of the surrounding code
(in the kernel), it doesn't really matter if the behaviour was signalled
by an explicit flag added in the code, or if this flag was automatically
added by the compiler.

> Not sure it can be done without driver changes though.

Well yeah, that's hard to know in the abstract, obviously. My point is
just that we should look very hard indeed before we decide it can't :)

-Toke

Re: XDP bpf_tail_call_redirect(): yea or nay?

[Alexei Starovoitov]

On Thu, May 7, 2020 at 11:09 AM John Fastabend <john.fastabend@gmail.com> wrote:
>
> I think it would work but I it would be even nicer if clang, verifier
> and jit caught the tail call pattern and did it automatically.

I've been advocating for proper tail calls for some time :)
All it needs is indirect jump instruction in the ISA.
The changes to llvm are trivial. Encoding of new insn is
straightforward as well.
The verifier side is tricky.
What you're proposing makes sense to me.
Somehow I thought that we need full indirect jump from day one,
but above is much simpler. It's a subset of it.
It's still an indirect jump, but target is always fixed.
The register will be initialized with fixed address of next kernel function
(or helper). That should be easy enough to support in the verifier.
llvm will generate:
ld_imm64 rX = addr_of_next_helper // that could be encoded via pseudo,
like for calls to helpers
jmp *rX

We can introduce an extension to JA insn instead that
takes 64-bit immediate or pc relative offset, but I think
it will be more messy to support through llvm, libbpf relocations and
the verifier.

Re: XDP bpf_tail_call_redirect(): yea or nay?

[Björn Töpel]

On Thu, 7 May 2020 at 20:08, John Fastabend <john.fastabend@gmail.com> wrote:
>
[]
>
> I'm wondering if we can teach the verifier to recognize tail calls,
>
> int xdp_prog1(struct xdp_md *ctx)
> {
>         return xdp_do_redirect(ctx, &xsks_map, 0);
> }
>
> This would be useful for normal calls as well. I guess the question here
> is would a tail call be sufficient for above case or do you need the
> 'return XDP_PASS' at the end? If so maybe we could fold it into the
> helper somehow.
>

No, that was just for handling the "failed call", bpf_tail_call() style.

> I think it would also address Toke's concerns, no new action so
> bpf developers can just develope like normal but "smart" developers
> will try do calls as tail calls. Not sure it can be done without
> driver changes though.
>

Take me though this. So, the new xdp_do_redirect() would return
XDP_REDIRECT? If the call is a tail call, we can "consume" (perform
the REDIRECT action) in the helper, set a "we're done/tail call
performed" flag in bpf_redirect_info and the xdp_do_redirect() checks
this flag and returns directly. If the call is *not* a tail call, the
regular REDIRECT path is performed. Am I following that correctly? So
we would be able to detect if the optimization has been performed, so
the "consume" semantics can be done.

Or do you mean that xdp_do_redirect() is only allowed if it can be
tailcall optimized?

int xdp_prog1(struct xdp_md *ctx)
{
        int ret;

        ret = xdp_do_redirect(ctx, &xsks_map, 0);
        // If xdp_do_redirect() consumes the context, the ctx is stale
        // here.
        ...
        return ret;
}

Let me clarify what I'm trying to do. bpf_redirect_map() performs a
lookup into the map. It would make sense to perform the action here as
well, since everything (maptype/item)is known. Today,
bpf_redirect_info is populated, and then the maptype is looked up
again from xdp_do_redirect(), and bpf_redirect_info() is cleared. I'd
like to get rid of bpf_redirect_info and xdp_do_redirect(), when
possible.

> > >> >
> > >> > -->8--
> > >> >
> > >> > The bpf_tail_call_redirect() would work with all redirectable maps.
> > >> >
> > >> > Thoughts? Tomatoes? Pitchforks?
> > >>
> > >> The above answers the 'what'. Might be easier to evaluate if you also
> > >> included the 'why'? :)
> > >>
> > >
> > > Ah! Sorry! Performance, performance, performance. Getting rid of a
> > > bunch of calls/instructions per packet, which helps my (AF_XDP) case.
> > > This would be faster than the regular REDIRECT path. Today, in
> > > bpf_redirect_map(), instead of actually performing the action, we
> > > populate the bpf_redirect_info structure, just to look up the action
> > > again in xdp_do_redirect().
> > >
> > > I'm pretty certain this would be a gain for AF_XDP (quite easy to do a
> > > quick hack, and measure). It would also shave off the same amount of
> > > instructions for "vanilla" XDP_REDIRECT cases. The bigger issue; Is
> > > this new semantic something people would be comfortable being added to
> > > XDP.
> >
> > Well, my immediate thought would be that the added complexity would not
> > be worth it, because:
> >
> > - A new action would mean either you'd need to patch all drivers or
> >   (more likely) we'd end up with yet another difference between drivers'
> >   XDP support.
> >
> > - BPF developers would suddenly have to choose - do this new faster
> >   thing, or be compatible? And manage the choice based on drivers they
> >   expect to run on, etc. This was already confusing with
> >   bpf_redirect()/bpf_redirect_map(), and this would introduce a third
> >   option!
> >
> > So in light of this, I'd say the performance benefit would have to be
> > quite substantial for this to be worth it. Which we won't know until you
> > try it, I guess :)
>
> Knowing the number would be useful. But if it can be done in general
> way it may not need to be as high because its not a special xdp thing.
>

Yeah, I need to do some experimentation here!

> >
> > Thinking of alternatives - couldn't you shoe-horn this into the existing
> > helper and return code? Say, introduce an IMMEDIATE_RETURN flag to the
> > existing helpers, which would change the behaviour to the tail call
> > semantics. When used, xdp_do_redirect() would then return immediately
> > (or you could even turn xdp_do_redirect() into an inlined wrapper that
> > checks the flag before issuing a CALL to the existing function). Any
> > reason why that wouldn't work?
>
> I think it would work but I it would be even nicer if clang, verifier
> and jit caught the tail call pattern and did it automatically.
>

Yes. :-)


Thanks for the input, and the ideas!
Björn

> >
> > -Toke
> >

Re: XDP bpf_tail_call_redirect(): yea or nay?

[Toke Høiland-Jørgensen]

Björn Töpel <bjorn.topel@gmail.com> writes:

> On Thu, 7 May 2020 at 20:08, John Fastabend <john.fastabend@gmail.com> wrote:
>>
> []
>>
>> I'm wondering if we can teach the verifier to recognize tail calls,
>>
>> int xdp_prog1(struct xdp_md *ctx)
>> {
>>         return xdp_do_redirect(ctx, &xsks_map, 0);
>> }
>>
>> This would be useful for normal calls as well. I guess the question here
>> is would a tail call be sufficient for above case or do you need the
>> 'return XDP_PASS' at the end? If so maybe we could fold it into the
>> helper somehow.
>>
>
> No, that was just for handling the "failed call", bpf_tail_call() style.
>
>> I think it would also address Toke's concerns, no new action so
>> bpf developers can just develope like normal but "smart" developers
>> will try do calls as tail calls. Not sure it can be done without
>> driver changes though.
>>
>
> Take me though this. So, the new xdp_do_redirect() would return
> XDP_REDIRECT? If the call is a tail call, we can "consume" (perform
> the REDIRECT action) in the helper, set a "we're done/tail call
> performed" flag in bpf_redirect_info and the xdp_do_redirect() checks
> this flag and returns directly. If the call is *not* a tail call, the
> regular REDIRECT path is performed. Am I following that correctly? So
> we would be able to detect if the optimization has been performed, so
> the "consume" semantics can be done.

Yeah, that was my understanding. And what I meant with the 'new flag'
bit was that you could prototype this by just adding a new flag to
bpf_redirect_map() which would trigger this consume behaviour. That
would allow you to get performance numbers without waiting for the
verifier to learn about tail calls... :)

-Toke

Re: XDP bpf_tail_call_redirect(): yea or nay?

[Björn Töpel]

On Thu, 7 May 2020 at 16:48, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
[]
> Well, my immediate thought would be that the added complexity would not
> be worth it, because:
>
> - A new action would mean either you'd need to patch all drivers or
>   (more likely) we'd end up with yet another difference between drivers'
>   XDP support.
>

Right, but it would be trivial to add for drivers that already support
XDP_REDIRECT, so I'm not worried about that particular problem. That
aside, let's move on. I agree that adding action should be avoided!

> - BPF developers would suddenly have to choose - do this new faster
>   thing, or be compatible? And manage the choice based on drivers they
>   expect to run on, etc. This was already confusing with
>   bpf_redirect()/bpf_redirect_map(), and this would introduce a third
>   option!
>

True. For the sake of the argument; Adding flags vs adding a new
helper, i.e. bpf_redirect_map(flag_with_new_semantic) vs a new helper.
Today XDP developers that use bpf_redirect_map() need to consider
whether the kernel support the "pass action via flags" or not, so this
would be a *fourth* option. :-P

I'm with you here. The best option would be a transparent one.


> So in light of this, I'd say the performance benefit would have to be
> quite substantial for this to be worth it. Which we won't know until you
> try it, I guess :)
>

Hear, hear!

> Thinking of alternatives - couldn't you shoe-horn this into the existing
> helper and return code? Say, introduce an IMMEDIATE_RETURN flag to the
> existing helpers, which would change the behaviour to the tail call
> semantics. When used, xdp_do_redirect() would then return immediately
> (or you could even turn xdp_do_redirect() into an inlined wrapper that
> checks the flag before issuing a CALL to the existing function). Any
> reason why that wouldn't work?
>

Sure, but this wouldn't remove the per-cpu/bpf_redirect_info lookup.
Then again, maybe it's better to start there. To clarify, just a flag
isn't sufficient. It would need to be a guarantee that the program
exists after the call, i.e. tail call support. From clang/BPF
instruction (Alexei's/John's replies), or something like
bpf_tail_call(). Unless I'm missing something... Or do you mean that
the flag IMMEDIATE_RETURN would perform the action in the helper? The
context would be stale after that call, and the verifier should reject
a program that pokes the context, but the flag is a runtime thing. It
sounds like a pretty complex verifier task to determine if
IMMEDIATE_RETURN is set, and then reject ctx accesses there.


Thanks for the input, and good ideas!
Björn

> -Toke
>