[PATCH nf-next 0/2] nf_tables: avoid retpoline overhead on set lookups

[PATCH nf-next 0/2] nf_tables: avoid retpoline overhead on set lookups

[Florian Westphal]

This adds a nft_set_do_lookup() helper, then extends it to use
direct calls when RETPOLINE feature is enabled.

For non-retpoline builds, nft_set_do_lookup() inline helper
does a indirect call.  INDIRECT_CALLABLE_SCOPE macro allows to
keep the lookup functions static in this case.

Florian Westphal (2):
  netfilter: add and use nft_set_do_lookup helper
  netfilter: nf_tables: prefer direct calls for set lookups

 include/net/netfilter/nf_tables_core.h | 30 ++++++++++++++++++++++
 net/netfilter/nft_lookup.c             | 35 ++++++++++++++++++++++++--
 net/netfilter/nft_objref.c             |  4 +--
 net/netfilter/nft_set_bitmap.c         |  5 ++--
 net/netfilter/nft_set_hash.c           | 17 +++++++------
 net/netfilter/nft_set_pipapo.c         |  5 ++--
 net/netfilter/nft_set_pipapo_avx2.h    |  2 --
 net/netfilter/nft_set_rbtree.c         |  5 ++--
 8 files changed, 84 insertions(+), 19 deletions(-)

-- 
2.26.3

[PATCH nf-next 1/2] netfilter: add and use nft_set_do_lookup helper

[Florian Westphal]

Followup patch will add a CONFIG_RETPOLINE wrapper to avoid
the ops->lookup() indirection cost for retpoline builds.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/net/netfilter/nf_tables_core.h | 7 +++++++
 net/netfilter/nft_lookup.c             | 4 ++--
 net/netfilter/nft_objref.c             | 4 ++--
 3 files changed, 11 insertions(+), 4 deletions(-)

diff --git a/include/net/netfilter/nf_tables_core.h b/include/net/netfilter/nf_tables_core.h
index fd10a7862fdc..5eb699454490 100644
--- a/include/net/netfilter/nf_tables_core.h
+++ b/include/net/netfilter/nf_tables_core.h
@@ -88,6 +88,13 @@ extern const struct nft_set_type nft_set_bitmap_type;
 extern const struct nft_set_type nft_set_pipapo_type;
 extern const struct nft_set_type nft_set_pipapo_avx2_type;
 
+static inline bool
+nft_set_do_lookup(const struct net *net, const struct nft_set *set,
+		  const u32 *key, const struct nft_set_ext **ext)
+{
+	return set->ops->lookup(net, set, key, ext);
+}
+
 struct nft_expr;
 struct nft_regs;
 struct nft_pktinfo;
diff --git a/net/netfilter/nft_lookup.c b/net/netfilter/nft_lookup.c
index a479f8a1270c..1a8581879af5 100644
--- a/net/netfilter/nft_lookup.c
+++ b/net/netfilter/nft_lookup.c
@@ -33,8 +33,8 @@ void nft_lookup_eval(const struct nft_expr *expr,
 	const struct net *net = nft_net(pkt);
 	bool found;
 
-	found = set->ops->lookup(net, set, &regs->data[priv->sreg], &ext) ^
-				 priv->invert;
+	found =	nft_set_do_lookup(net, set, &regs->data[priv->sreg], &ext) ^
+				  priv->invert;
 	if (!found) {
 		ext = nft_set_catchall_lookup(net, set);
 		if (!ext) {
diff --git a/net/netfilter/nft_objref.c b/net/netfilter/nft_objref.c
index 7e47edee88ee..94b2327e71dc 100644
--- a/net/netfilter/nft_objref.c
+++ b/net/netfilter/nft_objref.c
@@ -9,7 +9,7 @@
 #include <linux/netlink.h>
 #include <linux/netfilter.h>
 #include <linux/netfilter/nf_tables.h>
-#include <net/netfilter/nf_tables.h>
+#include <net/netfilter/nf_tables_core.h>
 
 #define nft_objref_priv(expr)	*((struct nft_object **)nft_expr_priv(expr))
 
@@ -110,7 +110,7 @@ static void nft_objref_map_eval(const struct nft_expr *expr,
 	struct nft_object *obj;
 	bool found;
 
-	found = set->ops->lookup(net, set, &regs->data[priv->sreg], &ext);
+	found = nft_set_do_lookup(net, set, &regs->data[priv->sreg], &ext);
 	if (!found) {
 		ext = nft_set_catchall_lookup(net, set);
 		if (!ext) {
-- 
2.26.3

[PATCH nf-next 2/2] netfilter: nf_tables: prefer direct calls for set lookups

[Florian Westphal]

Extend nft_set_do_lookup() to use direct calls when retpoline feature
is enabled.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/net/netfilter/nf_tables_core.h | 23 +++++++++++++++++++
 net/netfilter/nft_lookup.c             | 31 ++++++++++++++++++++++++++
 net/netfilter/nft_set_bitmap.c         |  5 +++--
 net/netfilter/nft_set_hash.c           | 17 ++++++++------
 net/netfilter/nft_set_pipapo.c         |  5 +++--
 net/netfilter/nft_set_pipapo_avx2.h    |  2 --
 net/netfilter/nft_set_rbtree.c         |  5 +++--
 7 files changed, 73 insertions(+), 15 deletions(-)

diff --git a/include/net/netfilter/nf_tables_core.h b/include/net/netfilter/nf_tables_core.h
index 5eb699454490..789e9eadd76d 100644
--- a/include/net/netfilter/nf_tables_core.h
+++ b/include/net/netfilter/nf_tables_core.h
@@ -3,6 +3,7 @@
 #define _NET_NF_TABLES_CORE_H
 
 #include <net/netfilter/nf_tables.h>
+#include <linux/indirect_call_wrapper.h>
 
 extern struct nft_expr_type nft_imm_type;
 extern struct nft_expr_type nft_cmp_type;
@@ -88,12 +89,34 @@ extern const struct nft_set_type nft_set_bitmap_type;
 extern const struct nft_set_type nft_set_pipapo_type;
 extern const struct nft_set_type nft_set_pipapo_avx2_type;
 
+#ifdef CONFIG_RETPOLINE
+bool nft_rhash_lookup(const struct net *net, const struct nft_set *set,
+		      const u32 *key, const struct nft_set_ext **ext);
+bool nft_rbtree_lookup(const struct net *net, const struct nft_set *set,
+		       const u32 *key, const struct nft_set_ext **ext);
+bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
+		       const u32 *key, const struct nft_set_ext **ext);
+bool nft_hash_lookup_fast(const struct net *net,
+			  const struct nft_set *set,
+			  const u32 *key, const struct nft_set_ext **ext);
+bool nft_hash_lookup(const struct net *net, const struct nft_set *set,
+		     const u32 *key, const struct nft_set_ext **ext);
+bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
+			    const u32 *key, const struct nft_set_ext **ext);
+bool nft_set_do_lookup(const struct net *net, const struct nft_set *set,
+		       const u32 *key, const struct nft_set_ext **ext);
+#else
 static inline bool
 nft_set_do_lookup(const struct net *net, const struct nft_set *set,
 		  const u32 *key, const struct nft_set_ext **ext)
 {
 	return set->ops->lookup(net, set, key, ext);
 }
+#endif
+
+/* called from nft_pipapo.c */
+bool nft_pipapo_avx2_lookup(const struct net *net, const struct nft_set *set,
+			    const u32 *key, const struct nft_set_ext **ext);
 
 struct nft_expr;
 struct nft_regs;
diff --git a/net/netfilter/nft_lookup.c b/net/netfilter/nft_lookup.c
index 1a8581879af5..90becbf5bff3 100644
--- a/net/netfilter/nft_lookup.c
+++ b/net/netfilter/nft_lookup.c
@@ -23,6 +23,37 @@ struct nft_lookup {
 	struct nft_set_binding		binding;
 };
 
+#ifdef CONFIG_RETPOLINE
+bool nft_set_do_lookup(const struct net *net, const struct nft_set *set,
+		       const u32 *key, const struct nft_set_ext **ext)
+{
+	if (set->ops == &nft_set_hash_fast_type.ops)
+		return nft_hash_lookup_fast(net, set, key, ext);
+	if (set->ops == &nft_set_hash_type.ops)
+		return nft_hash_lookup(net, set, key, ext);
+
+	if (set->ops == &nft_set_rhash_type.ops)
+		return nft_rhash_lookup(net, set, key, ext);
+
+	if (set->ops == &nft_set_bitmap_type.ops)
+		return nft_bitmap_lookup(net, set, key, ext);
+
+	if (set->ops == &nft_set_pipapo_type.ops)
+		return nft_pipapo_lookup(net, set, key, ext);
+#if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
+	if (set->ops == &nft_set_pipapo_avx2_type.ops)
+		return nft_pipapo_avx2_lookup(net, set, key, ext);
+#endif
+
+	if (set->ops == &nft_set_rbtree_type.ops)
+		return nft_rbtree_lookup(net, set, key, ext);
+
+	WARN_ON_ONCE(1);
+	return set->ops->lookup(net, set, key, ext);
+}
+EXPORT_SYMBOL_GPL(nft_set_do_lookup);
+#endif
+
 void nft_lookup_eval(const struct nft_expr *expr,
 		     struct nft_regs *regs,
 		     const struct nft_pktinfo *pkt)
diff --git a/net/netfilter/nft_set_bitmap.c b/net/netfilter/nft_set_bitmap.c
index 2a81ea421819..e7ae5914971e 100644
--- a/net/netfilter/nft_set_bitmap.c
+++ b/net/netfilter/nft_set_bitmap.c
@@ -73,8 +73,9 @@ nft_bitmap_active(const u8 *bitmap, u32 idx, u32 off, u8 genmask)
 	return (bitmap[idx] & (0x3 << off)) & (genmask << off);
 }
 
-static bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
-			      const u32 *key, const struct nft_set_ext **ext)
+INDIRECT_CALLABLE_SCOPE
+bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
+		       const u32 *key, const struct nft_set_ext **ext)
 {
 	const struct nft_bitmap *priv = nft_set_priv(set);
 	u8 genmask = nft_genmask_cur(net);
diff --git a/net/netfilter/nft_set_hash.c b/net/netfilter/nft_set_hash.c
index 7b3d0a78c569..df40314de21f 100644
--- a/net/netfilter/nft_set_hash.c
+++ b/net/netfilter/nft_set_hash.c
@@ -74,8 +74,9 @@ static const struct rhashtable_params nft_rhash_params = {
 	.automatic_shrinking	= true,
 };
 
-static bool nft_rhash_lookup(const struct net *net, const struct nft_set *set,
-			     const u32 *key, const struct nft_set_ext **ext)
+INDIRECT_CALLABLE_SCOPE
+bool nft_rhash_lookup(const struct net *net, const struct nft_set *set,
+		      const u32 *key, const struct nft_set_ext **ext)
 {
 	struct nft_rhash *priv = nft_set_priv(set);
 	const struct nft_rhash_elem *he;
@@ -446,8 +447,9 @@ struct nft_hash_elem {
 	struct nft_set_ext		ext;
 };
 
-static bool nft_hash_lookup(const struct net *net, const struct nft_set *set,
-			    const u32 *key, const struct nft_set_ext **ext)
+INDIRECT_CALLABLE_SCOPE
+bool nft_hash_lookup(const struct net *net, const struct nft_set *set,
+		     const u32 *key, const struct nft_set_ext **ext)
 {
 	struct nft_hash *priv = nft_set_priv(set);
 	u8 genmask = nft_genmask_cur(net);
@@ -484,9 +486,10 @@ static void *nft_hash_get(const struct net *net, const struct nft_set *set,
 	return ERR_PTR(-ENOENT);
 }
 
-static bool nft_hash_lookup_fast(const struct net *net,
-				 const struct nft_set *set,
-				 const u32 *key, const struct nft_set_ext **ext)
+INDIRECT_CALLABLE_SCOPE
+bool nft_hash_lookup_fast(const struct net *net,
+			  const struct nft_set *set,
+			  const u32 *key, const struct nft_set_ext **ext)
 {
 	struct nft_hash *priv = nft_set_priv(set);
 	u8 genmask = nft_genmask_cur(net);
diff --git a/net/netfilter/nft_set_pipapo.c b/net/netfilter/nft_set_pipapo.c
index 528a2d7ca991..9addc0b447f7 100644
--- a/net/netfilter/nft_set_pipapo.c
+++ b/net/netfilter/nft_set_pipapo.c
@@ -408,8 +408,9 @@ int pipapo_refill(unsigned long *map, int len, int rules, unsigned long *dst,
  *
  * Return: true on match, false otherwise.
  */
-static bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
-			      const u32 *key, const struct nft_set_ext **ext)
+INDIRECT_CALLABLE_SCOPE
+bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
+		       const u32 *key, const struct nft_set_ext **ext)
 {
 	struct nft_pipapo *priv = nft_set_priv(set);
 	unsigned long *res_map, *fill_map;
diff --git a/net/netfilter/nft_set_pipapo_avx2.h b/net/netfilter/nft_set_pipapo_avx2.h
index 394bcb704db7..dbb6aaca8a7a 100644
--- a/net/netfilter/nft_set_pipapo_avx2.h
+++ b/net/netfilter/nft_set_pipapo_avx2.h
@@ -5,8 +5,6 @@
 #include <asm/fpu/xstate.h>
 #define NFT_PIPAPO_ALIGN	(XSAVE_YMM_SIZE / BITS_PER_BYTE)
 
-bool nft_pipapo_avx2_lookup(const struct net *net, const struct nft_set *set,
-			    const u32 *key, const struct nft_set_ext **ext);
 bool nft_pipapo_avx2_estimate(const struct nft_set_desc *desc, u32 features,
 			      struct nft_set_estimate *est);
 #endif /* defined(CONFIG_X86_64) && !defined(CONFIG_UML) */
diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index 9e36eb4a7429..d600a566da32 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -107,8 +107,9 @@ static bool __nft_rbtree_lookup(const struct net *net, const struct nft_set *set
 	return false;
 }
 
-static bool nft_rbtree_lookup(const struct net *net, const struct nft_set *set,
-			      const u32 *key, const struct nft_set_ext **ext)
+INDIRECT_CALLABLE_SCOPE
+bool nft_rbtree_lookup(const struct net *net, const struct nft_set *set,
+		       const u32 *key, const struct nft_set_ext **ext)
 {
 	struct nft_rbtree *priv = nft_set_priv(set);
 	unsigned int seq = read_seqcount_begin(&priv->count);
-- 
2.26.3

Re: [PATCH nf-next 0/2] nf_tables: avoid retpoline overhead on set lookups

[Stefano Brivio]

Hi Florian,

On Thu, 13 May 2021 22:29:54 +0200
Florian Westphal <fw@strlen.de> wrote:

> This adds a nft_set_do_lookup() helper, then extends it to use
> direct calls when RETPOLINE feature is enabled.
> 
> For non-retpoline builds, nft_set_do_lookup() inline helper
> does a indirect call.  INDIRECT_CALLABLE_SCOPE macro allows to
> keep the lookup functions static in this case.

Thanks for doing this! And sorry I looked into it more than one year
ago without ever finishing it ;)

I ran some quick tests, I was curious to see the impact of dropping
indirect calls on that path. With the 'performance' test cases of
nft_concat_range.sh, roughly estimating clock cycles as clock frequency
divided by packet rate, it looks like this offsets entirely the usage of
retpolines!

With a 'return true;' in the lookup function (I patched nft_set_pipapo),
on my usual single AMD Epyc 7351 thread, 2.9GHz, average of three runs,
I get:

                                               | packet |  est.  |
                                               |  rate  | cycles |
                                               | (Mpps) |        |
-----------------------------------------------|--------|--------|
Without retpolines, netdev drop                | 15.443 |    188 |
Without retpolines, dummy lookup function      |  9.995 |    292 |
-> Without retpolines, set lookup              |        |    104-|-.
- - - - - - - - - - - - - - - - - - - - - - - -|- - - - | - - - -|
With retpolines, netdev drop                   | 10.420 |    278 | |
With retpolines, dummy lookup function         |  7.038 |    412 |
-> With retpolines, set lookup                 |        |    134 | |
- - - - - - - - - - - - - - - - - - - - - - - -|- - - - | - - - -|
This series, retpolines, netdev drop           | 10.431 |    278 | |
This series, retpolines, dummy lookup function |  7.549 |    384 |
-> This series, retpolines, set lookup         |  ^ +7% |    106-|-'

estimated clock cycles for set lookup only are the difference between
cycles to hit the dummy lookup function and cycles to drop packets from
the netdev hook -- they're now approximately the same with and without
retpolines.

For context, I also ran the whole set of tests with actual matching.
This is indicative, just a single run:

 --------------.-----------------------------------.--------------------------.
AMD Epyc 7351  |          baselines, Mpps          |       this series        |
 1 thread      |___________________________________|__________________________|
 2.9GHz        |        |        |        |        |        |        |        |
 512KiB L1D$   | netdev |  hash  | rbtree |        |  hash  | rbtree |        |
 --------------|  hook  |   no   | single |        |   no   | single |        |
type   entries |  drop  | ranges | field  | pipapo | ranges | field  | pipapo |
 --------------|--------|--------|--------|--------|--------|-----------------|
net,port       |        |        |        |        | +15%   |  +4%   |  +4%   |
         1000  |   10.1 |    5.2 |    2.7 |    4.6 |    6.0 |    2.8 |    4.8 |
 --------------|--------|--------|--------|--------|--------|--------|--------|
port,net       |        |        |        |        | +11%   |  +5%   |  +4%   |
          100  |   10.4 |    5.4 |    4.1 |    5.0 |    6.0 |    4.3 |    5.2 |
 --------------|--------|--------|--------|--------|--------|--------|--------|
net6,port      |        |        |        |        | +15%   |  +9%   |  +6%   |
         1000  |   10.0 |    4.6 |    1.1 |    3.1 |    9.9 |    1.2 |    3.3 |
 --------------|--------|--------|--------|--------|--------|--------|--------|
port,proto     |        |        |        |        |  +7%   |  +3%   |  +3%   |
        10000  |   10.7 |    6.0 |    3.0 |    3.0 |    6.4 |    3.1 |    3.1 |
 --------------|--------|--------|--------|--------|--------|--------|--------|
net6,port,mac  |        |        |        |        |  +3%   |  +4%   |  +3%   |
           10  |    9.9 |    3.8 |    2.7 |    3.3 |    3.9 |    2.8 |    3.4 |
 --------------|--------|--------|--------|--------|--------|--------|--------|
net6,port,mac, |        |        |        |        |  +3%   |  +9%   |  +4%   |
proto    1000  |   10.0 |    3.6 |    1.1 |    2.4 |    3.7 |    1.2 |    2.5 |
 --------------|--------|--------|--------|--------|--------|--------|--------|
net,mac        |        |        |        |        |  +6%   |  +4%   |  +3%   |
         1000  |   10.5 |    4.8 |    2.7 |    4.0 |    5.1 |    2.8 |    4.1 |
 --------------'--------'--------'--------'--------'--------'--------'--------'

-- 
Stefano

Re: [PATCH nf-next 0/2] nf_tables: avoid retpoline overhead on set lookups

[Pablo Neira Ayuso]

On Thu, May 13, 2021 at 10:29:54PM +0200, Florian Westphal wrote:
> This adds a nft_set_do_lookup() helper, then extends it to use
> direct calls when RETPOLINE feature is enabled.
> 
> For non-retpoline builds, nft_set_do_lookup() inline helper
> does a indirect call.  INDIRECT_CALLABLE_SCOPE macro allows to
> keep the lookup functions static in this case.

Applied, thanks.