[RFC PATCH bpf-next 0/2] bpf_redirect_map() tail call detection and xdp_do_redirect() avoidance

[RFC PATCH bpf-next 0/2] bpf_redirect_map() tail call detection and xdp_do_redirect() avoidance

[Björn Töpel]

I hacked a quick PoC, based on the input from my earlier post [1].

Quick recap; For certain XDP programs, would it be possible to get rid
of the xdp_do_redirect() call (and the per-cpu write/read), and
instead perform the action directly from the BPF helper? If so, that
would potentially make the XDP_REDIRECT faster/less complex.

This PoC/RFC teach the verifier to detect when an XDP program is
structured such that all bpf_redirect_map() calls are tail calls. A
driver can then probe the BPF program, use the new
xdp_set_redirect_tailcall() function, and avoid the xdp_do_redirect()
call. This was Toke's suggestion, instead of my XDP_CONSUMED idea,
adding a new action.

To perform the xdp_do_redirect() tasks from the bpf_redirect_map()
helper, additional parameters are needed (XDP context, netdev, and XDP
program). They are passed via the bpf_redirect_into per-cpu structure
using the xdp_set_redirect_tailcall() function.

Note that the code is broken for programs mixing bpf_redirect() and
bpf_redirect_map()!

There are more details in the commits.

Is this a good idea? I have only measured for AF_XDP redirects, but
all XDP_REDIRECT targets should benefit. For AF_XDP the rxdrop
scenario went from 21.5 to 23.2 Mpps on my machine.

Next steps would be implement proper tail calls (suggested by John and
Alexei).

Getting input on my (horrible) verifier peephole hack, and a better
way to detect tail calls would be very welcome!

Disregard naming and style. I'm mostly interested what people think
about the concept, and if it's worth working on.

Next steps:
  * Better tail call detection in the verifier, instead of the naive
    peephole version in patch 1.
  * Implement proper tail calls (constrained, indirect jump BPF
    instruction).


Cheers,
Björn

[1] https://lore.kernel.org/bpf/CAJ+HfNidbgwtLinLQohwocUmoYyRcAG454ggGkCbseQPSA1cpw@mail.gmail.com/

Björn Töpel (2):
  bpf, xdp: add naive bpf_redirect_map() tail call detection
  i40e: avoid xdp_do_redirect() call when "redirect_tail_call" is set

 drivers/net/ethernet/intel/i40e/i40e_txrx.c | 14 ++++-
 drivers/net/ethernet/intel/i40e/i40e_xsk.c  | 14 ++++-
 include/linux/bpf_verifier.h                |  2 +
 include/linux/filter.h                      | 19 ++++++-
 kernel/bpf/verifier.c                       | 53 +++++++++++++++++++
 net/core/filter.c                           | 57 +++++++++++++++++++++
 6 files changed, 154 insertions(+), 5 deletions(-)


base-commit: cb8e59cc87201af93dfbb6c3dccc8fcad72a09c2
-- 
2.25.1

[RFC PATCH bpf-next 1/2] bpf, xdp: add naive bpf_redirect_map() tail call detection

[Björn Töpel]

From: Björn Töpel <bjorn.topel@intel.com>

The bpf_redirect_map() BPF helper is used to redirect a packet to the
endpoint referenced by a map element. Currently, there is no
restrictment how the helper is called, e.g.

  ret = bpf_redirect_map(...);
  ...
  ret = bpf_redirect_map(...);
  ... // e.g. modify packet
  return ret;

is a valid, albeit weird, program.

The unconstrained nature of BPF (redirect) helpers has implications
for the implementation of the XDP_REDIRECT call. Today, the redirect
flow for a packet is along the lines of:

  for_each_packet() {
    act = bpf_prog_run_xdp(xdp_prog, xdp); // does bpf_redirect_map() call
    if (act == XDP_REDIRECT)
      ret = xdp_do_redirect(...);
  }
  xdp_do_flush();

The bpf_redirect_map() helper populates a per-cpu structure, which is
picked up by the xdp_do_redirect() function that also performs the
redirect action.

What if the verifier could detect that certain programs have certain
constraints, so the functiontionality performed by xdp_do_redirect()
could be done directly from bpf_redirect_map()?

Here, the verifier is taught to detect program where all
bpf_redirect_map() calls, are tail calls. If a function call is a last
action performed in another function, it is said to be a tail call --
not to be confused with the BPF tail call helper.

This implementation is just a PoC, and not complete. It manages to
detect tail calls by a naive peephole scheme.

For the following program (the built in AF_XDP libbpf program):

  ...
  call bpf_redirect_map
  if w0 != 0 goto pc+X (goto exit)
  ...
  call bpf_redirect_map
  exit

the verifier detects that all calls are tail calls.

TODO:
 * Stateful tail call detection, instead of the current peephole one.
 * Add all helpers capable of returning XDP_REDIRECT, and not just
   bpf_redirect_map().

Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
---
 include/linux/bpf_verifier.h |  2 ++
 include/linux/filter.h       | 19 +++++++++++-
 kernel/bpf/verifier.c        | 53 +++++++++++++++++++++++++++++++++
 net/core/filter.c            | 57 ++++++++++++++++++++++++++++++++++++
 4 files changed, 130 insertions(+), 1 deletion(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index ca08db4ffb5f..e41fd9264c94 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -411,6 +411,8 @@ struct bpf_verifier_env {
 	u32 peak_states;
 	/* longest register parentage chain walked for liveness marking */
 	u32 longest_mark_read_walk;
+	bool all_redirect_map_tail;
+	u32 redirect_map_call_cnt;
 };
 
 __printf(2, 0) void bpf_verifier_vlog(struct bpf_verifier_log *log,
diff --git a/include/linux/filter.h b/include/linux/filter.h
index 259377723603..cdbc2ca8db4f 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -534,7 +534,8 @@ struct bpf_prog {
 				is_func:1,	/* program is a bpf function */
 				kprobe_override:1, /* Do we override a kprobe? */
 				has_callchain_buf:1, /* callchain buffer allocated? */
-				enforce_expected_attach_type:1; /* Enforce expected_attach_type checking at attach time */
+				enforce_expected_attach_type:1, /* Enforce expected_attach_type checking at attach time */
+				redirect_tail_call:1;
 	enum bpf_prog_type	type;		/* Type of BPF program */
 	enum bpf_attach_type	expected_attach_type; /* For some prog types */
 	u32			len;		/* Number of filter blocks */
@@ -613,6 +614,9 @@ struct bpf_redirect_info {
 	void *tgt_value;
 	struct bpf_map *map;
 	u32 kern_flags;
+	struct bpf_prog *xdp_prog_redirect_tailcall; // if !NULL, we can do "everything" from BPF context.
+	struct xdp_buff *xdp;
+	struct net_device *dev;
 };
 
 DECLARE_PER_CPU(struct bpf_redirect_info, bpf_redirect_info);
@@ -620,6 +624,19 @@ DECLARE_PER_CPU(struct bpf_redirect_info, bpf_redirect_info);
 /* flags for bpf_redirect_info kern_flags */
 #define BPF_RI_F_RF_NO_DIRECT	BIT(0)	/* no napi_direct on return_frame */
 
+
+static inline void xdp_set_redirect_tailcall(struct bpf_prog *xdp_prog,
+					     struct xdp_buff *xdp,
+					     struct net_device *dev)
+{
+	struct bpf_redirect_info *ri = this_cpu_ptr(&bpf_redirect_info);
+
+	ri->xdp_prog_redirect_tailcall = xdp_prog;
+	ri->xdp = xdp;
+	ri->dev = dev;
+}
+
+
 /* Compute the linear packet data range [data, data_end) which
  * will be accessed by various program types (cls_bpf, act_bpf,
  * lwt, ...). Subsystems allowing direct data access must (!)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5c7bbaac81ef..27a4fd5c8b8b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4594,6 +4594,54 @@ static int check_reference_leak(struct bpf_verifier_env *env)
 	return state->acquired_refs ? -EINVAL : 0;
 }
 
+static void check_redirect_map_tail_call(struct bpf_verifier_env *env, int func_id,
+					 int insn_idx)
+{
+	struct bpf_insn *insns = env->prog->insnsi;
+	int insn_cnt = env->prog->len;
+	bool is_tail_call = false;
+	struct bpf_insn *insn;
+
+	if (func_id != 	BPF_FUNC_redirect_map)
+		return;
+
+	/* Naive peephole tail call checking */
+	insn_idx++;
+again:
+	if (insn_idx >= insn_cnt)
+		goto out;
+
+	insn = &insns[insn_idx];
+	insn_idx++;
+
+	switch (insn->code) {
+	/* 1. Is the instruction following the call, an exit? */
+	case BPF_JMP | BPF_EXIT:
+		is_tail_call = true;
+		break;
+	/* 2. True branch of "if w0 != 0 goto pc+X", an exit? */
+	case BPF_JMP | BPF_JSGT | BPF_K:
+	case BPF_JMP32 | BPF_JSGT | BPF_K:
+		if (insn->dst_reg == BPF_REG_0 && insn->imm == 0) {
+			insn_idx += insn->off;
+			goto again;
+		}
+		break;
+	/* 3... more checks. XXX */
+	default:
+		break;
+	}
+
+out:
+	if (!env->redirect_map_call_cnt++) {
+		env->all_redirect_map_tail = is_tail_call;
+		return;
+	}
+
+	if (!is_tail_call)
+		env->all_redirect_map_tail = false;
+}
+
 static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn_idx)
 {
 	const struct bpf_func_proto *fn = NULL;
@@ -4685,6 +4733,8 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn
 		}
 	}
 
+	check_redirect_map_tail_call(env, func_id, insn_idx);
+
 	regs = cur_regs(env);
 
 	/* check that flags argument in get_local_storage(map, flags) is 0,
@@ -11064,6 +11114,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
 	if (ret == 0)
 		adjust_btf_func(env);
 
+	if (ret == 0)
+		env->prog->redirect_tail_call = env->all_redirect_map_tail;
+
 err_release_maps:
 	if (!env->prog->aux->used_maps)
 		/* if we didn't copy map pointers into bpf_prog_info, release
diff --git a/net/core/filter.c b/net/core/filter.c
index d01a244b5087..8cd8dee9359a 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -3701,6 +3701,60 @@ static const struct bpf_func_proto bpf_xdp_redirect_proto = {
 	.arg2_type      = ARG_ANYTHING,
 };
 
+static u64 __bpf_xdp_redirect_map_tailcall(struct bpf_map *map, u32 index,
+					   u64 flags,
+					   struct bpf_redirect_info *ri)
+{
+	struct xdp_buff *xdp = ri->xdp;
+	struct net_device *d = ri->dev;
+	struct bpf_prog *xdp_prog;
+	void *val;
+	int err;
+
+	switch (map->map_type) {
+	case BPF_MAP_TYPE_DEVMAP: {
+		val = __dev_map_lookup_elem(map, index);
+		if (unlikely(!val))
+			return flags;
+		err = dev_map_enqueue(val, xdp, d);
+		break;
+	}
+	case BPF_MAP_TYPE_DEVMAP_HASH: {
+		val = __dev_map_hash_lookup_elem(map, index);
+		if (unlikely(!val))
+			return flags;
+		err = dev_map_enqueue(val, xdp, d);
+		break;
+	}
+	case BPF_MAP_TYPE_CPUMAP: {
+		val = __cpu_map_lookup_elem(map, index);
+		if (unlikely(!val))
+			return flags;
+		err = cpu_map_enqueue(val, xdp, d);
+		break;
+	}
+	case BPF_MAP_TYPE_XSKMAP: {
+		val = __xsk_map_lookup_elem(map, index);
+		if (unlikely(!val))
+			return flags;
+		err = __xsk_map_redirect(val, xdp);
+		break;
+	}
+	default:
+		return flags;
+	}
+
+	xdp_prog = ri->xdp_prog_redirect_tailcall;
+	if (unlikely(err))
+		goto err;
+
+	_trace_xdp_redirect_map(d, xdp_prog, val, map, index);
+	return XDP_REDIRECT;
+err:
+	_trace_xdp_redirect_map_err(d, xdp_prog, val, map, index, err);
+	return XDP_DROP;
+}
+
 BPF_CALL_3(bpf_xdp_redirect_map, struct bpf_map *, map, u32, ifindex,
 	   u64, flags)
 {
@@ -3710,6 +3764,9 @@ BPF_CALL_3(bpf_xdp_redirect_map, struct bpf_map *, map, u32, ifindex,
 	if (unlikely(flags > XDP_TX))
 		return XDP_ABORTED;
 
+	if (ri->xdp_prog_redirect_tailcall)
+		return __bpf_xdp_redirect_map_tailcall(map, ifindex, flags, ri);
+
 	ri->tgt_value = __xdp_map_lookup_elem(map, ifindex);
 	if (unlikely(!ri->tgt_value)) {
 		/* If the lookup fails we want to clear out the state in the
-- 
2.25.1

[RFC PATCH bpf-next 2/2] i40e: avoid xdp_do_redirect() call when "redirect_tail_call" is set

[Björn Töpel]

From: Björn Töpel <bjorn.topel@intel.com>

If an XDP program, where all the bpf_redirect_map() calls are tail
calls (as defined by the previous commit), the driver does not need to
explicitly call xdp_do_redirect().

The driver checks the active XDP program, and notifies the BPF helper
indirectly via xdp_set_redirect_tailcall().

This is just a naive, as-simple-as-possible implementation, calling
xdp_set_redirect_tailcall() for each packet.

For the AF_XDP rxdrop benchmark the pps went from 21.5 to 23.2 Mpps.

Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
---
 drivers/net/ethernet/intel/i40e/i40e_txrx.c | 14 ++++++++++++--
 drivers/net/ethernet/intel/i40e/i40e_xsk.c  | 14 ++++++++++++--
 2 files changed, 24 insertions(+), 4 deletions(-)

diff --git a/drivers/net/ethernet/intel/i40e/i40e_txrx.c b/drivers/net/ethernet/intel/i40e/i40e_txrx.c
index f9555c847f73..0d8dbdc4f47e 100644
--- a/drivers/net/ethernet/intel/i40e/i40e_txrx.c
+++ b/drivers/net/ethernet/intel/i40e/i40e_txrx.c
@@ -2186,6 +2186,7 @@ static struct sk_buff *i40e_run_xdp(struct i40e_ring *rx_ring,
 	int err, result = I40E_XDP_PASS;
 	struct i40e_ring *xdp_ring;
 	struct bpf_prog *xdp_prog;
+	bool impl_redir = false;
 	u32 act;
 
 	rcu_read_lock();
@@ -2194,6 +2195,11 @@ static struct sk_buff *i40e_run_xdp(struct i40e_ring *rx_ring,
 	if (!xdp_prog)
 		goto xdp_out;
 
+	if (xdp_prog->redirect_tail_call) {
+		impl_redir = true;
+		xdp_set_redirect_tailcall(rx_ring->xdp_prog, xdp,
+					  rx_ring->netdev);
+	}
 	prefetchw(xdp->data_hard_start); /* xdp_frame write */
 
 	act = bpf_prog_run_xdp(xdp_prog, xdp);
@@ -2205,8 +2211,12 @@ static struct sk_buff *i40e_run_xdp(struct i40e_ring *rx_ring,
 		result = i40e_xmit_xdp_tx_ring(xdp, xdp_ring);
 		break;
 	case XDP_REDIRECT:
-		err = xdp_do_redirect(rx_ring->netdev, xdp, xdp_prog);
-		result = !err ? I40E_XDP_REDIR : I40E_XDP_CONSUMED;
+		if (impl_redir) {
+			result = I40E_XDP_REDIR;
+		} else {
+			err = xdp_do_redirect(rx_ring->netdev, xdp, xdp_prog);
+			result = !err ? I40E_XDP_REDIR : I40E_XDP_CONSUMED;
+		}
 		break;
 	default:
 		bpf_warn_invalid_xdp_action(act);
diff --git a/drivers/net/ethernet/intel/i40e/i40e_xsk.c b/drivers/net/ethernet/intel/i40e/i40e_xsk.c
index 7276580cbe64..0826f551649f 100644
--- a/drivers/net/ethernet/intel/i40e/i40e_xsk.c
+++ b/drivers/net/ethernet/intel/i40e/i40e_xsk.c
@@ -146,6 +146,7 @@ static int i40e_run_xdp_zc(struct i40e_ring *rx_ring, struct xdp_buff *xdp)
 	int err, result = I40E_XDP_PASS;
 	struct i40e_ring *xdp_ring;
 	struct bpf_prog *xdp_prog;
+	bool impl_redir = false;
 	u32 act;
 
 	rcu_read_lock();
@@ -153,6 +154,11 @@ static int i40e_run_xdp_zc(struct i40e_ring *rx_ring, struct xdp_buff *xdp)
 	 * this path is enabled by setting an XDP program.
 	 */
 	xdp_prog = READ_ONCE(rx_ring->xdp_prog);
+	if (xdp_prog->redirect_tail_call) {
+		impl_redir = true;
+		xdp_set_redirect_tailcall(rx_ring->xdp_prog, xdp,
+					  rx_ring->netdev);
+	}
 	act = bpf_prog_run_xdp(xdp_prog, xdp);
 
 	switch (act) {
@@ -163,8 +169,12 @@ static int i40e_run_xdp_zc(struct i40e_ring *rx_ring, struct xdp_buff *xdp)
 		result = i40e_xmit_xdp_tx_ring(xdp, xdp_ring);
 		break;
 	case XDP_REDIRECT:
-		err = xdp_do_redirect(rx_ring->netdev, xdp, xdp_prog);
-		result = !err ? I40E_XDP_REDIR : I40E_XDP_CONSUMED;
+		if (impl_redir) {
+			result = I40E_XDP_REDIR;
+		} else {
+			err = xdp_do_redirect(rx_ring->netdev, xdp, xdp_prog);
+			result = !err ? I40E_XDP_REDIR : I40E_XDP_CONSUMED;
+		}
 		break;
 	default:
 		bpf_warn_invalid_xdp_action(act);
-- 
2.25.1

Re: [RFC PATCH bpf-next 2/2] i40e: avoid xdp_do_redirect() call when "redirect_tail_call" is set

[Toke Høiland-Jørgensen]

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

> From: Björn Töpel <bjorn.topel@intel.com>
>
> If an XDP program, where all the bpf_redirect_map() calls are tail
> calls (as defined by the previous commit), the driver does not need to
> explicitly call xdp_do_redirect().
>
> The driver checks the active XDP program, and notifies the BPF helper
> indirectly via xdp_set_redirect_tailcall().
>
> This is just a naive, as-simple-as-possible implementation, calling
> xdp_set_redirect_tailcall() for each packet.

Do you really need the driver changes? The initial setup could be moved
to bpf_prog_run_xdp(), and xdp_do_redirect() could be changed to an
inline wrapper that just checks a flag and immediately returns 0 if the
redirect action was already performed. Or am I missing some reason why
this wouldn't work?

-Toke

Re: [RFC PATCH bpf-next 0/2] bpf_redirect_map() tail call detection and xdp_do_redirect() avoidance

[Toke Høiland-Jørgensen]

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

> Is this a good idea? I have only measured for AF_XDP redirects, but
> all XDP_REDIRECT targets should benefit. For AF_XDP the rxdrop
> scenario went from 21.5 to 23.2 Mpps on my machine.

I like it! I guess in the end the feasibility will depend on the quality
tail call detection, which I don't have any ideas for improving. I'm
sure someone else will, though :)

-Toke

Re: [RFC PATCH bpf-next 2/2] i40e: avoid xdp_do_redirect() call when "redirect_tail_call" is set

[Björn Töpel]

On Tue, 9 Jun 2020 at 21:47, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> Björn Töpel <bjorn.topel@gmail.com> writes:
>
> > From: Björn Töpel <bjorn.topel@intel.com>
> >
> > If an XDP program, where all the bpf_redirect_map() calls are tail
> > calls (as defined by the previous commit), the driver does not need to
> > explicitly call xdp_do_redirect().
> >
> > The driver checks the active XDP program, and notifies the BPF helper
> > indirectly via xdp_set_redirect_tailcall().
> >
> > This is just a naive, as-simple-as-possible implementation, calling
> > xdp_set_redirect_tailcall() for each packet.
>
> Do you really need the driver changes? The initial setup could be moved
> to bpf_prog_run_xdp(), and xdp_do_redirect() could be changed to an
> inline wrapper that just checks a flag and immediately returns 0 if the
> redirect action was already performed. Or am I missing some reason why
> this wouldn't work?
>

Indeed! That's a good idea!


Björn

> -Toke
>

Re: [RFC PATCH bpf-next 0/2] bpf_redirect_map() tail call detection and xdp_do_redirect() avoidance

[Jesper Dangaard Brouer]

> Björn Töpel <bjorn.topel@gmail.com> writes:
> 
> > Is this a good idea? I have only measured for AF_XDP redirects, but
> > all XDP_REDIRECT targets should benefit. For AF_XDP the rxdrop
> > scenario went from 21.5 to 23.2 Mpps on my machine.  

Do remember that you are reporting saving 3.4 nanosec (from 21.5 to
23.2 Mpps).  For comparison a function call cost around 1.2 ns, and I
think you have avoided two function calls xdp_do_redirect() and
dev_map_enqueue() (the rest should be inlined by compiler).  Thus, that
alone account for 2.4 ns.

-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Principal Kernel Engineer at Red Hat
  LinkedIn: http://www.linkedin.com/in/brouer