Skip to contentSkip to conversation

nftables: Set implementation for arbitrary concatenation of ranges

PATCH Superseded Stefano Brivio 4 participants 22 messages Nov 19, 2019 – Nov 22, 2019

Subsystems (5)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

cover nftables: Set implementation for arbitrary concatenation of ranges

Existing nftables set implementations allow matching entries with interval expressions (rbtree), e.g. 192.0.2.1-192.0.2.4, entries specifying field concatenation (hash, rhash), e.g. 192.0.2.1:22, but not both.

In other words, none of the set types allows matching on range expressions for more than one packet field at a time, such as ipset does with types bitmap:ip,mac, and, to a more limited extent (netmasks, not arbitrary ranges), with types hash:net,net, hash:net,port, hash:ip,port,net, and hash:net,port,net.

As a pure hash-based approach is unsuitable for matching on ranges, and "proxying" the existing red-black tree type looks impractical as elements would need to be shared and managed across all employed trees, this new set implementation intends to fill the functionality gap by employing a relatively novel approach.

The fundamental idea, illustrated in deeper detail in patch 3/5, is to use lookup tables classifying a small number of grouped bits from each field, and map the lookup results in a way that yields a verdict for the full set of specified fields.

The grouping bit aspect is loosely inspired by the Grouper algorithm, by Jay Ligatti, Josh Kuhn, and Chris Gage (see patch 3/5 for the full reference).

A reference, stand-alone implementation of the algorithm itself is available at:
https://pipapo.lameexcu.se

Some notes about possible future optimisations are also mentioned there. This algorithm reduces the matching problem to, essentially, a repetitive sequence of simple bitwise operations, and is particularly suitable to be optimised by leveraging SIMD instruction sets. An AVX2-based implementation is also presented in this series.

I plan to post the adaptation of the existing AVX2 vectorised implementation for (at least) NEON at a later time.

Patch 1/8 implements the needed UAPI bits: additions to the existing interface are kept to a minimum by recycling existing concepts for both ranging and concatenation, as suggested by Florian.

Patch 2/8 adds a new bitmap operation that copies the source bitmap onto the destination while removing a given region, and is needed to delete regions of arrays mapping between lookup tables.

Patch 3/8 is the actual set implementation.

Patch 4/8 introduces selftests for the new implementation.

Patch 5/8 provides an easy optimisation with substantial gain on matching rates.

Patches 6/8 and 7/8 are preparatory work to add an alternative, vectorised lookup implementation.

Patch 8/8 contains the AVX2-based implementation of the lookup routines.

The nftables and libnftnl counterparts depend on changes to the UAPI header file included in patch 1/5.

Credits go to Jay Ligatti, Josh Kuhn, and Chris Gage for their original Grouper implementation and article from ICCCN proceedings (see reference in patch 3/5), and to Daniel Lemire for his public domain implementation of a fast iterator on set bits using built-in implementations of the CTZL operation, also included in patch 3/5.

Special thanks go to Florian Westphal for all the nftables consulting and the original interface idea, to Sabrina Dubroca for support with RCU and bit manipulation topics, to Eric Garver for an early review, and to Phil Sutter for reaffirming the need for the use case covered here.

Stefano Brivio (8):
netfilter: nf_tables: Support for subkeys, set with multiple ranged
fields
bitmap: Introduce bitmap_cut(): cut bits and shift remaining
nf_tables: Add set type for arbitrary concatenation of ranges
selftests: netfilter: Introduce tests for sets with range
concatenation
nft_set_pipapo: Provide unrolled lookup loops for common field sizes
nft_set_pipapo: Prepare for vectorised implementation: alignment
nft_set_pipapo: Prepare for vectorised implementation: helpers
nft_set_pipapo: Introduce AVX2-based lookup implementation

 include/linux/bitmap.h                        |    4 +
 include/net/netfilter/nf_tables_core.h        |    2 +
 include/uapi/linux/netfilter/nf_tables.h      |   16 +
 lib/bitmap.c                                  |   66 +
 net/netfilter/Makefile                        |    6 +-
 net/netfilter/nf_tables_api.c                 |    4 +-
 net/netfilter/nf_tables_set_core.c            |    8 +
 net/netfilter/nft_set_pipapo.c                | 2131 +++++++++++++++++
 net/netfilter/nft_set_pipapo.h                |  242 ++
 net/netfilter/nft_set_pipapo_avx2.c           |  840 +++++++
 net/netfilter/nft_set_pipapo_avx2.h           |   14 +
 tools/testing/selftests/netfilter/Makefile    |    3 +-
 .../selftests/netfilter/nft_concat_range.sh   | 1481 ++++++++++++
 13 files changed, 4813 insertions(+), 4 deletions(-)
 create mode 100644 net/netfilter/nft_set_pipapo.c
 create mode 100644 net/netfilter/nft_set_pipapo.h
 create mode 100644 net/netfilter/nft_set_pipapo_avx2.c
 create mode 100644 net/netfilter/nft_set_pipapo_avx2.h
 create mode 100755 tools/testing/selftests/netfilter/nft_concat_range.sh
Signature · 1 line
2.20.1
#1 lore raw

PATCH 1/8 nf_tables: Support for subkeys, set with multiple ranged fields

Introduce a new nested netlink attribute, NFTA_SET_SUBKEY, used to specify the length of each field in a set concatenation.

This allows set implementations to support concatenation of multiple ranged items, as they can divide the input key into matching data for every single field. Such set implementations would indicate this capability with the NFT_SET_SUBKEY flag.

In order to specify the interval for a set entry, userspace would simply keep using two elements per entry, as it happens now, with the end element indicating the upper interval bound. As a single element can now be a concatenation of several fields, with or without the NFT_SET_ELEM_INTERVAL_END flag, we obtain a convenient way to support multiple ranged fields in a set.

While at it, export the number of 32-bit registers available for packet matching, as nftables will need this to know the maximum number of field lengths that can be specified.

For example, "packets with an IPv4 address between 192.0.2.0 and 192.0.2.42, with destination port between 22 and 25", can be expressed as two concatenated elements:

192.0.2.0 . 22
192.0.2.42 . 25 with NFT_SET_ELEM_INTERVAL_END

and the NFTA_SET_SUBKEY attributes would be 32, 16, in that order.

Note that this does *not* represent the concatenated range:

0xc0 0x00 0x02 0x00 0x00 0x16 - 0xc0 0x00 0x02 0x2a 0x00 0x25

on the six packet bytes of interest. That is, the range specified does *not* include e.g. 0xc0 0x00 0x02 0x29 0x00 0x42, which is:
192.0.0.41 . 66

---
 include/uapi/linux/netfilter/nf_tables.h | 16 ++++++++++++++++
 net/netfilter/nf_tables_api.c            |  4 ++--
 2 files changed, 18 insertions(+), 2 deletions(-)
include/uapi/linux/netfilter/nf_tables.h +16 -0
index bb9b049310df..f8dbeac14898 100644
@@ -48,6 +48,7 @@ enum nft_registers {
 
 #define NFT_REG_SIZE	16
 #define NFT_REG32_SIZE	4
+#define NFT_REG32_COUNT	(NFT_REG32_15 - NFT_REG32_00 + 1)
 
 /**
  * enum nft_verdicts - nf_tables internal verdicts
@@ -275,6 +276,7 @@ enum nft_rule_compat_attributes {
  * @NFT_SET_TIMEOUT: set uses timeouts
  * @NFT_SET_EVAL: set can be updated from the evaluation path
  * @NFT_SET_OBJECT: set contains stateful objects
+ * @NFT_SET_SUBKEY: set uses subkeys to map intervals for multiple fields
  */
 enum nft_set_flags {
 	NFT_SET_ANONYMOUS		= 0x1,
@@ -284,6 +286,7 @@ enum nft_set_flags {
 	NFT_SET_TIMEOUT			= 0x10,
 	NFT_SET_EVAL			= 0x20,
 	NFT_SET_OBJECT			= 0x40,
+	NFT_SET_SUBKEY			= 0x80,
 };
 
 /**
@@ -309,6 +312,17 @@ enum nft_set_desc_attributes {
 };
 #define NFTA_SET_DESC_MAX	(__NFTA_SET_DESC_MAX - 1)
 
+/**
+ * enum nft_set_subkey_attributes - subkeys for multiple ranged fields
+ *
+ * @NFTA_SET_SUBKEY_LEN: length of single field, in bits (NLA_U32)
+ */
+enum nft_set_subkey_attributes {
+	NFTA_SET_SUBKEY_LEN,
+	__NFTA_SET_SUBKEY_MAX
+};
+#define NFTA_SET_SUBKEY_MAX	(__NFTA_SET_SUBKEY_MAX - 1)
+
 /**
  * enum nft_set_attributes - nf_tables set netlink attributes
  *
@@ -327,6 +341,7 @@ enum nft_set_desc_attributes {
  * @NFTA_SET_USERDATA: user data (NLA_BINARY)
  * @NFTA_SET_OBJ_TYPE: stateful object type (NLA_U32: NFT_OBJECT_*)
  * @NFTA_SET_HANDLE: set handle (NLA_U64)
+ * @NFTA_SET_SUBKEY: subkeys for multiple ranged fields (NLA_NESTED)
  */
 enum nft_set_attributes {
 	NFTA_SET_UNSPEC,
@@ -346,6 +361,7 @@ enum nft_set_attributes {
 	NFTA_SET_PAD,
 	NFTA_SET_OBJ_TYPE,
 	NFTA_SET_HANDLE,
+	NFTA_SET_SUBKEY,
 	__NFTA_SET_MAX
 };
 #define NFTA_SET_MAX		(__NFTA_SET_MAX - 1)
net/netfilter/nf_tables_api.c +2 -2
index ff04cdc87f76..a877d60f86a9 100644
@@ -3248,7 +3248,7 @@ EXPORT_SYMBOL_GPL(nft_unregister_set);
 
 #define NFT_SET_FEATURES	(NFT_SET_INTERVAL | NFT_SET_MAP | \
 				 NFT_SET_TIMEOUT | NFT_SET_OBJECT | \
-				 NFT_SET_EVAL)
+				 NFT_SET_EVAL | NFT_SET_SUBKEY)
 
 static bool nft_set_ops_candidate(const struct nft_set_type *type, u32 flags)
 {
@@ -3826,7 +3826,7 @@ static int nf_tables_newset(struct net *net, struct sock *nlsk,
 		if (flags & ~(NFT_SET_ANONYMOUS | NFT_SET_CONSTANT |
 			      NFT_SET_INTERVAL | NFT_SET_TIMEOUT |
 			      NFT_SET_MAP | NFT_SET_EVAL |
-			      NFT_SET_OBJECT))
+			      NFT_SET_OBJECT | NFT_SET_SUBKEY))
 			return -EINVAL;
 		/* Only one of these operations is supported */
 		if ((flags & (NFT_SET_MAP | NFT_SET_OBJECT)) ==
Signature · 1 line
2.20.1
#2 lore raw

PATCH 2/8 bitmap: Introduce bitmap_cut(): cut bits and shift remaining

In reply to Stefano Brivio

The new bitmap function bitmap_cut() copies bits from source to destination by removing the region specified by parameters first and cut, and remapping the bits above the cut region by right shifting them.

---
 include/linux/bitmap.h |  4 +++
 lib/bitmap.c           | 66 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+)
include/linux/bitmap.h +4 -0
index 29fc933df3bf..e66cff371688 100644
@@ -53,6 +53,7 @@
  *  bitmap_find_next_zero_area_off(buf, len, pos, n, mask)  as above
  *  bitmap_shift_right(dst, src, n, nbits)      *dst = *src >> n
  *  bitmap_shift_left(dst, src, n, nbits)       *dst = *src << n
+ *  bitmap_cut(dst, src, first, n, nbits)       Cut n bits from first, copy rest
  *  bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
  *  bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
  *  bitmap_onto(dst, orig, relmap, nbits)       *dst = orig relative to relmap
@@ -130,6 +131,9 @@ extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 				unsigned int shift, unsigned int nbits);
 extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 				unsigned int shift, unsigned int nbits);
+extern void bitmap_cut(unsigned long *dst, const unsigned long *src,
+		       unsigned int first, unsigned int cut,
+		       unsigned int nbits);
 extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 			const unsigned long *bitmap2, unsigned int nbits);
 extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
lib/bitmap.c +66 -0

72 lines not on this page · raw message

Signature · 1 line
2.20.1
#3 lore raw

PATCH 3/8 nf_tables: Add set type for arbitrary concatenation of ranges

In reply to Stefano Brivio

This new set type allows for intervals in concatenated fields, which are expressed in the usual way, that is, simple byte concatenation with padding to 32 bits for single fields, and given as ranges by specifying start and end elements containing, each, the full concatenation of start and end values for the single fields.

Ranges are expanded to composing netmasks, for each field: these are inserted as rules in per-field lookup tables. Bits to be classified are divided in 4-bit groups, and for each group, the lookup table contains 4^2 buckets, representing all the possible values of a bit group. This approach was inspired by the Grouper algorithm:
http://www.cse.usf.edu/~ligatti/projects/grouper/

Matching is performed by a sequence of AND operations between bucket values, with buckets selected according to the value of packet bits, for each group. The result of this sequence tells us which rules matched for a given field.

In order to concatenate several ranged fields, per-field rules are mapped using mapping arrays, one per field, that specify which rules should be considered while matching the next field. The mapping array for the last field contains a reference to the element originally inserted.

The notes in nft_set_pipapo.c cover the algorithm in deeper detail.

A pure hash-based approach is of no use here, as ranges need to be classified. An implementation based on "proxying" the existing red-black tree set type, creating a tree for each field, was considered, but deemed impractical due to the fact that elements would need to be shared between trees, at least as long as we want to keep UAPI changes to a minimum.

A stand-alone implementation of this algorithm is available at:
https://pipapo.lameexcu.se
together with notes about possible future optimisations (in pipapo.c).

This algorithm was designed with data locality in mind, and can be highly optimised for SIMD instruction sets, as the bulk of the matching work is done with repetitive, simple bitwise operations.

---
 include/net/netfilter/nf_tables_core.h |    1 +
 net/netfilter/Makefile                 |    3 +-
 net/netfilter/nf_tables_set_core.c     |    2 +
 net/netfilter/nft_set_pipapo.c         | 2169 ++++++++++++++++++++++++
 4 files changed, 2174 insertions(+), 1 deletion(-)
 create mode 100644 net/netfilter/nft_set_pipapo.c
include/net/netfilter/nf_tables_core.h +1 -0
index 7281895fa6d9..9759257ec8ec 100644
@@ -74,6 +74,7 @@ extern struct nft_set_type nft_set_hash_type;
 extern struct nft_set_type nft_set_hash_fast_type;
 extern struct nft_set_type nft_set_rbtree_type;
 extern struct nft_set_type nft_set_bitmap_type;
+extern struct nft_set_type nft_set_pipapo_type;
 
 struct nft_expr;
 struct nft_regs;
net/netfilter/Makefile +2 -1
index 5e9b2eb24349..3f572e5a975e 100644
@@ -81,7 +81,8 @@ nf_tables-objs := nf_tables_core.o nf_tables_api.o nft_chain_filter.o \
 		  nft_chain_route.o nf_tables_offload.o
 
 nf_tables_set-objs := nf_tables_set_core.o \
-		      nft_set_hash.o nft_set_bitmap.o nft_set_rbtree.o
+		      nft_set_hash.o nft_set_bitmap.o nft_set_rbtree.o \
+		      nft_set_pipapo.o
 
 obj-$(CONFIG_NF_TABLES)		+= nf_tables.o
 obj-$(CONFIG_NF_TABLES_SET)	+= nf_tables_set.o
net/netfilter/nf_tables_set_core.c +2 -0
index a9fce8d10051..586b621007eb 100644
@@ -9,12 +9,14 @@ static int __init nf_tables_set_module_init(void)
 	nft_register_set(&nft_set_rhash_type);
 	nft_register_set(&nft_set_bitmap_type);
 	nft_register_set(&nft_set_rbtree_type);
+	nft_register_set(&nft_set_pipapo_type);
 
 	return 0;
 }
 
 static void __exit nf_tables_set_module_exit(void)
 {
+	nft_unregister_set(&nft_set_pipapo_type);
 	nft_unregister_set(&nft_set_rbtree_type);
 	nft_unregister_set(&nft_set_bitmap_type);
 	nft_unregister_set(&nft_set_rhash_type);
net/netfilter/nft_set_pipapo.c new file +2169 -0

2,169 lines not on this page · raw message

Signature · 1 line
2.20.1
maintainer
#4 lore raw

Re: [PATCH nf-next 3/8] nf_tables: Add set type for arbitrary concatenation of ranges

net/netfilter/nft_set_pipapo.c line 558

Quoted 13 lines · Stefano Brivio
net/netfilter/nft_set_pipapo.c new file +13 -0
+static 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;
+	u8 genmask = nft_genmask_cur(net);
+	const u8 *rp = (const u8 *)key;
+	struct nft_pipapo_match *m;
+	struct nft_pipapo_field *f;
+	bool map_index;
+	int i;
+
+	map_index = raw_cpu_read(nft_pipapo_scratch_index);

I'm afraid this will need local_bh_disable to prevent reentry from softirq processing.

Review

Quoted 1 line
(quoted diff) +1 -0
+	rcu_read_lock();

All netfilter hooks run inside rcu read section, so this isn't needed.

net/netfilter/nft_set_pipapo.c line 1070

Quoted 12 lines
net/netfilter/nft_set_pipapo.c new file +12 -0
+static int pipapo_realloc_scratch(struct nft_pipapo_match *m,
+				  unsigned long bsize_max)
+{
+	int i;
+
+	for_each_possible_cpu(i) {
+		unsigned long *scratch;
+
+		scratch = kzalloc_node(bsize_max * sizeof(*scratch) * 2,
+				       GFP_KERNEL, cpu_to_node(i));
+		if (!scratch)
+			return -ENOMEM;

No need to handle partial failures on the other cpu / no rollback? AFAICS ->destroy will handle it correctly, i.e. next insertion may enter this again and allocate a same-sized chunk, so AFAICS its fine.

But still, it looks odd -- perhaps add a comment that there is no need to rollback earlier allocs.

Review

Quoted 2 lines
(quoted diff) +2 -0
+
+		kfree(*per_cpu_ptr(m->scratch, i));

I was about to ask what would prevent nft_pipapo_lookup() from accessing m->scratch. Its because "m" is the private clone. Perhaps add a comment here to that effect.

Quoted 11 lines

+ * @net: Network namespace
+ * @set: nftables API set representation
+ * @elem: nftables API element representation containing key data
+ * @flags: If NFT_SET_ELEM_INTERVAL_END is passed, this is the end element
+ * @ext2: Filled with pointer to &struct nft_set_ext in inserted element
+ *
+ * In this set implementation, this functions needs to be called twice, with
+ * start and end element, to obtain a valid entry insertion. Calls to this
+ * function are serialised, so we can store element and key data on the first
+ * call with start element, and use it on the second call once we get the end
+ * element too.

What guaranttess this?
AFAICS userspace could send a single element, with either NFT_SET_ELEM_INTERVAL_END, or only the start element.

#5 lore raw

Re: [PATCH nf-next 3/8] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 17 lines · On Wed, 20 Nov 2019 16:06:09 +0100 Florian Westphal <[email protected]> wrote:

net/netfilter/nft_set_pipapo.c line 558

Quoted 13 lines · Stefano Brivio
net/netfilter/nft_set_pipapo.c new file +13 -0
+static 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;
+	u8 genmask = nft_genmask_cur(net);
+	const u8 *rp = (const u8 *)key;
+	struct nft_pipapo_match *m;
+	struct nft_pipapo_field *f;
+	bool map_index;
+	int i;
+
+	map_index = raw_cpu_read(nft_pipapo_scratch_index);  

I'm afraid this will need local_bh_disable to prevent reentry from softirq processing.

I'm afraid you're right and yes, not just this: from here to the point where we're done using scratch maps or their index. Adding in v2.

Well, at least vectorised versions for (at least) x86, ARM and s390x won't have any overhead from it as they will already do that with kernel_fpu_begin()/kernel_neon_begin().

Quoted 3 lines

Review

Quoted 1 line
(quoted diff) +1 -0
+	rcu_read_lock();  

All netfilter hooks run inside rcu read section, so this isn't needed.

Dropping in v2.

Quoted 8 lines
Quoted 8 lines
net/netfilter/nft_set_pipapo.c new file +8 -0
+static int pipapo_realloc_scratch(struct nft_pipapo_match *m,
+				  unsigned long bsize_max)
+{
+	int i;
+
+	for_each_possible_cpu(i) {
+		unsigned long *scratch;
+
Quoted 8 lines

net/netfilter/nft_set_pipapo.c line 1070

Quoted 4 lines
net/netfilter/nft_set_pipapo.c new file +4 -0
+		scratch = kzalloc_node(bsize_max * sizeof(*scratch) * 2,
+				       GFP_KERNEL, cpu_to_node(i));
+		if (!scratch)
+			return -ENOMEM;  

No need to handle partial failures on the other cpu / no rollback? AFAICS ->destroy will handle it correctly, i.e. next insertion may enter this again and allocate a same-sized chunk, so AFAICS its fine.

There's no need because this is just called on insertion, so the new scratch maps will be bigger than the previous ones, and if only some allocations here succeed, that means some CPUs have a bigger allocated map, but the element is not inserted and the extra room is not used, because the caller won't update m->bsize_max.

Quoted 2 lines

But still, it looks odd -- perhaps add a comment that there is no need to rollback earlier allocs.

Sure, added.

Quoted 6 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+
+		kfree(*per_cpu_ptr(m->scratch, i));  

I was about to ask what would prevent nft_pipapo_lookup() from accessing m->scratch. Its because "m" is the private clone. Perhaps add a comment here to that effect.

I renamed 'm' to 'clone' and updated kerneldoc header, I think it's even clearer than a comment that way.

Quoted 12 lines
Quoted 11 lines

+ * @net: Network namespace
+ * @set: nftables API set representation
+ * @elem: nftables API element representation containing key data
+ * @flags: If NFT_SET_ELEM_INTERVAL_END is passed, this is the end element
+ * @ext2: Filled with pointer to &struct nft_set_ext in inserted element
+ *
+ * In this set implementation, this functions needs to be called twice, with
+ * start and end element, to obtain a valid entry insertion. Calls to this
+ * function are serialised, so we can store element and key data on the first
+ * call with start element, and use it on the second call once we get the end
+ * element too.

Quoted 1 line

What guaranttess this?

Well, the only guarantee that I'm expecting here is that the insert function is not called concurrently in the same namespace, and as far as I understand that comes from nf_tables_valid_genid(). However:

Quoted 2 lines

AFAICS userspace could send a single element, with either NFT_SET_ELEM_INTERVAL_END, or only the start element.

this is all possible, and:

- for a single element with NFT_SET_ELEM_INTERVAL_END, we'll reuse the last 'start' element ever seen, or an all-zero key if no 'start' elements were seen at all

- for a single 'start' element, no element is added

If the user chooses to configure firewalling with syzbot, my assumption is that all we have to do is to avoid crashing or leaking anything.

We could opt to be stricter indeed, by checking that a single netlink batch contains a corresponding number of start and end elements. This can't be done by the insert function though, we don't have enough context there.

A possible solution might be to implement a ->validate() callback similar to what's done for chains -- or maybe export the context to insert functions so that we can relate stuff to portid/seq.

Do you think it's worth it? In some sense, this should already be all consistent and safe.

Signature · 1 line
Stefano
maintainer
#6 lore raw

Re: [PATCH nf-next 3/8] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 8 lines · Stefano Brivio
Quoted 5 lines

Review

Quoted 1 line
(quoted diff) +1 -0
+		kfree(*per_cpu_ptr(m->scratch, i));  

I was about to ask what would prevent nft_pipapo_lookup() from accessing m->scratch. Its because "m" is the private clone. Perhaps add a comment here to that effect.

I renamed 'm' to 'clone' and updated kerneldoc header, I think it's even clearer than a comment that way.

Agree, thats even better, thanks!

Quoted 12 lines
Quoted 12 lines
Quoted 11 lines

+ * @net: Network namespace
+ * @set: nftables API set representation
+ * @elem: nftables API element representation containing key data
+ * @flags: If NFT_SET_ELEM_INTERVAL_END is passed, this is the end element
+ * @ext2: Filled with pointer to &struct nft_set_ext in inserted element
+ *
+ * In this set implementation, this functions needs to be called twice, with
+ * start and end element, to obtain a valid entry insertion. Calls to this
+ * function are serialised, so we can store element and key data on the first
+ * call with start element, and use it on the second call once we get the end
+ * element too.

Quoted 5 lines
Quoted 1 line

What guaranttess this?

Well, the only guarantee that I'm expecting here is that the insert function is not called concurrently in the same namespace, and as far as I understand that comes from nf_tables_valid_genid(). However:

Yes, insertion isn't parallel for same netns.

Quoted 5 lines
Quoted 2 lines

AFAICS userspace could send a single element, with either NFT_SET_ELEM_INTERVAL_END, or only the start element.

this is all possible, and:

Quoted 8 lines

- for a single element with NFT_SET_ELEM_INTERVAL_END, we'll reuse the last 'start' element ever seen, or an all-zero key if no 'start' elements were seen at all

- for a single 'start' element, no element is added

If the user chooses to configure firewalling with syzbot, my assumption is that all we have to do is to avoid crashing or leaking anything.

Yes, exactly, we should only reject what either
1. would crash kernel
2. makes obviously no sense (missing or contradiction attributes).

anything more than that isn't needed.

Quoted 4 lines

We could opt to be stricter indeed, by checking that a single netlink batch contains a corresponding number of start and end elements. This can't be done by the insert function though, we don't have enough context there.

Yes. If such 'single element with no end interval' can't happen or won't cause any problems then no action is needed.

#7 lore raw

Re: [PATCH nf-next 3/8] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 6 lines · On Thu, 21 Nov 2019 21:41:13 +0100 Florian Westphal <[email protected]> wrote:

Yes, exactly, we should only reject what either
1. would crash kernel
2. makes obviously no sense (missing or contradiction attributes).

anything more than that isn't needed.

Quoted 7 lines
Quoted 4 lines

We could opt to be stricter indeed, by checking that a single netlink batch contains a corresponding number of start and end elements. This can't be done by the insert function though, we don't have enough context there.

Yes. If such 'single element with no end interval' can't happen or won't cause any problems then no action is needed.

Yeah, I don't expect that to cause any problem. I don't have a kselftest or nft test for it, because that would require nft to send invalid elements, so I only tested those two cases manually. The nastiest thing I could come up with was start > end, and it's now covered by:

		if (memcmp(start, end,
			   f->groups / NFT_PIPAPO_GROUPS_PER_BYTE) > 0)
			return -EINVAL;

while:
- start == end is allowed, explicitly handled below
- end without any previous start (somewhat) correctly maps to < 0 > to end
- start without end won't trigger any insertion

Signature · 1 line
Stefano
#8 lore raw

Re: [PATCH nf-next 3/8] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 23 lines · On Thu, 21 Nov 2019 22:00:46 +0100 Stefano Brivio <[email protected]> wrote:
Quoted 6 lines · On Thu, 21 Nov 2019 21:41:13 +0100 Florian Westphal <[email protected]> wrote:

Yes, exactly, we should only reject what either
1. would crash kernel
2. makes obviously no sense (missing or contradiction attributes).

anything more than that isn't needed.

Quoted 7 lines
Quoted 4 lines

We could opt to be stricter indeed, by checking that a single netlink batch contains a corresponding number of start and end elements. This can't be done by the insert function though, we don't have enough context there.

Yes. If such 'single element with no end interval' can't happen or won't cause any problems then no action is needed.

Yeah, I don't expect that to cause any problem. I don't have a kselftest or nft test for it, because that would require nft to send invalid elements, so I only tested those two cases manually. The nastiest thing I could come up with was start > end, and it's now covered by:

Quoted 8 lines
		if (memcmp(start, end,
			   f->groups / NFT_PIPAPO_GROUPS_PER_BYTE) > 0)
			return -EINVAL;

while:
- start == end is allowed, explicitly handled below
- end without any previous start (somewhat) correctly maps to < 0 > to end

On the contrary, good that you mentioned this, I haven't been creative enough. If we allow a < 0 > start element and keep the start pointer set to NULL, this ends up being used as it is in ->walk(). Another problem I found is that on the sequence:

- start element only passed to ->insert()
- API frees the start element
- end element is then passed to ->insert()

we would end up with a dangling ->start pointer, which is again problematic on a number of operations including walk(). Fixed in v2 by adding explicit checks (and comments).

Signature · 1 line
Stefano
#9 lore raw

PATCH 4/8 selftests: netfilter: Introduce tests for sets with range concatenation

In reply to Stefano Brivio

This test covers functionality and stability of the newly added nftables set implementation supporting concatenation of ranged fields.

For some selected set expression types, test:
- correctness, by checking that packets match or don't
- concurrency, by attempting races between insertion, deletion, lookup
- timeout feature, checking that packets don't match expired entries

and (roughly) estimate matching rates, comparing to baselines for simple drop on netdev ingress hook and for hash and rbtrees sets.

In order to send packets, this needs one of sendip, netcat or bash. To flood with traffic, iperf3, iperf and netperf are supported. For performance measurements, this relies on the sample pktgen script pktgen_bench_xmit_mode_netif_receive.sh.

If none of the tools suitable for a given test are available, specific tests will be skipped.

---
 tools/testing/selftests/netfilter/Makefile    |    3 +-
 .../selftests/netfilter/nft_concat_range.sh   | 1481 +++++++++++++++++
 2 files changed, 1483 insertions(+), 1 deletion(-)
 create mode 100755 tools/testing/selftests/netfilter/nft_concat_range.sh
tools/testing/selftests/netfilter/Makefile +2 -1
index de1032b5ddea..08194aa44006 100644
@@ -2,6 +2,7 @@
 # Makefile for netfilter selftests
 
 TEST_PROGS := nft_trans_stress.sh nft_nat.sh bridge_brouter.sh \
-	conntrack_icmp_related.sh nft_flowtable.sh ipvs.sh
+	conntrack_icmp_related.sh nft_flowtable.sh ipvs.sh \
+	nft_concat_range.sh
 
 include ../lib.mk
tools/testing/selftests/netfilter/nft_concat_range.sh new file +1481 -0

1,481 lines not on this page · raw message

Signature · 1 line
2.20.1
#10 lore raw

PATCH 5/8 nft_set_pipapo: Provide unrolled lookup loops for common field sizes

In reply to Stefano Brivio

For non-vectorised lookup implementations, this increases matching rates by 20 to 30% for most set types.

---
 net/netfilter/nft_set_pipapo.c | 86 +++++++++++++++++++++++++++++-----
 1 file changed, 73 insertions(+), 13 deletions(-)
net/netfilter/nft_set_pipapo.c +73 -13
index 1829289a54f7..d4d8c509caf3 100644
@@ -532,6 +532,51 @@ static int pipapo_refill(unsigned long *map, int len, int rules,
 	return ret;
 }
 
+#define NFT_PIPAPO_AND_BUCKET(map, bucket, bsize, idx)			       \
+	do {								       \
+		for (idx = 0; idx < (bsize); idx++)			       \
+			map[idx] &= *((bucket) + idx);			       \
+	} while (0)
+
+#define NFT_PIPAPO_MATCH_2(map, lt, bsize, pkt, offset, idx)		       \
+	do {								       \
+		NFT_PIPAPO_AND_BUCKET(map,				       \
+				      lt +				       \
+				      (offset +  0 +   (*pkt >> 4)) * bsize,   \
+				      bsize, idx);			       \
+		NFT_PIPAPO_AND_BUCKET(map,				       \
+				      lt +				       \
+				      (offset + 16 + (*pkt & 0x0f)) * bsize,   \
+				      bsize, idx);			       \
+		pkt++;							       \
+	} while (0)
+
+#define NFT_PIPAPO_MATCH_4(map, lt, bsize, pkt, offset, idx)		       \
+	do {								       \
+		NFT_PIPAPO_MATCH_2(map, lt, bsize, pkt, offset, idx);	       \
+		NFT_PIPAPO_MATCH_2(map, lt, bsize, pkt, offset + 2 * 16, idx); \
+	} while (0)
+
+#define NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, offset, idx)		       \
+	do {								       \
+		NFT_PIPAPO_MATCH_4(map, lt, bsize, pkt, offset, idx);	       \
+		NFT_PIPAPO_MATCH_4(map, lt, bsize, pkt, offset + 4 * 16, idx); \
+	} while (0)
+
+#define NFT_PIPAPO_MATCH_12(map, lt, bsize, pkt, idx)			       \
+	do {								       \
+		NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, 0, idx);	       \
+		NFT_PIPAPO_MATCH_4(map, lt, bsize, pkt, 8 * 16, idx);	       \
+	} while (0)
+
+#define NFT_PIPAPO_MATCH_32(map, lt, bsize, pkt, idx)			       \
+	do {								       \
+		NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt,  0, idx);	       \
+		NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt,  8 * 16, idx);	       \
+		NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, 16 * 16, idx);	       \
+		NFT_PIPAPO_MATCH_8(map, lt, bsize, pkt, 24 * 16, idx);	       \
+	} while (0)
+
 /**
  * nft_pipapo_lookup() - Lookup function
  * @net:	Network namespace
@@ -571,24 +616,39 @@ static bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
 	nft_pipapo_for_each_field(f, i, m) {
 		bool last = i == m->field_count - 1;
 		unsigned long *lt = f->lt;
-		int b, group;
+		int b, group, j;
 
 		/* For each 4-bit group: select lookup table bucket depending on
-		 * packet bytes value, then AND bucket value
+		 * packet bytes value, then AND bucket value. Unroll loops for
+		 * the most common cases (protocol, port, IPv4 address, MAC
+		 * address, IPv6 address).
 		 */
-		for (group = 0; group < f->groups; group++) {
-			u8 v;
+		if (f->groups == 2) {
+			NFT_PIPAPO_MATCH_2(res_map, lt, f->bsize, rp, 0, j);
+		} else if (f->groups == 4) {
+			NFT_PIPAPO_MATCH_4(res_map, lt, f->bsize, rp, 0, j);
+		} else if (f->groups == 8) {
+			NFT_PIPAPO_MATCH_8(res_map, lt, f->bsize, rp, 0, j);
+		} else if (f->groups == 12) {
+			NFT_PIPAPO_MATCH_12(res_map, lt, f->bsize, rp, j);
+		} else if (f->groups == 32) {
+			NFT_PIPAPO_MATCH_32(res_map, lt, f->bsize, rp, j);
+		} else {
+			for (group = 0; group < f->groups; group++) {
+				u8 v;
+
+				if (group % 2) {
+					v = *rp & 0x0f;
+					rp++;
+				} else {
+					v = *rp >> 4;
+				}
+				__bitmap_and(res_map, res_map,
+					     lt + v * f->bsize,
+					     f->bsize * BITS_PER_LONG);
 
-			if (group % 2) {
-				v = *rp & 0x0f;
-				rp++;
-			} else {
-				v = *rp >> 4;
+				lt += f->bsize * NFT_PIPAPO_BUCKETS;
 			}
-			__bitmap_and(res_map, res_map, lt + v * f->bsize,
-				     f->bsize * BITS_PER_LONG);
-
-			lt += f->bsize * NFT_PIPAPO_BUCKETS;
 		}
 
 		/* Now populate the bitmap for the next field, unless this is
Signature · 1 line
2.20.1
#11 lore raw

PATCH 6/8 nft_set_pipapo: Prepare for vectorised implementation: alignment

In reply to Stefano Brivio

SIMD vector extension sets require stricter alignment than native instruction sets to operate efficiently (AVX, NEON) or for some instructions to work at all (AltiVec).

Provide facilities to define arbitrary alignment for lookup tables and scratch maps. By defining byte alignment with NFT_PIPAPO_ALIGN, lt_aligned and scratch_aligned pointers become available.

Additional headroom is allocated, and pointers to the possibly unaligned, originally allocated areas are kept so that they can be freed.

---
 net/netfilter/nft_set_pipapo.c | 115 +++++++++++++++++++++++++++------
 1 file changed, 97 insertions(+), 18 deletions(-)
net/netfilter/nft_set_pipapo.c +97 -18
index d4d8c509caf3..63d54f9fcac0 100644
@@ -377,6 +377,22 @@
 #define NFT_PIPAPO_RULE0_MAX		((1UL << (NFT_PIPAPO_MAP_TOBITS - 1)) \
 					- (1UL << NFT_PIPAPO_MAP_NBITS))
 
+/* Definitions for vectorised implementations */
+#ifdef NFT_PIPAPO_ALIGN
+#define NFT_PIPAPO_ALIGN_HEADROOM					\
+	(NFT_PIPAPO_ALIGN - ARCH_KMALLOC_MINALIGN)
+#define NFT_PIPAPO_LT_ALIGN(lt)		(PTR_ALIGN((lt), NFT_PIPAPO_ALIGN))
+#define NFT_PIPAPO_LT_ASSIGN(field, x)					\
+	do {								\
+		(field)->lt_aligned = NFT_PIPAPO_LT_ALIGN(x);		\
+		(field)->lt = (x);					\
+	} while (0)
+#else
+#define NFT_PIPAPO_ALIGN_HEADROOM	0
+#define NFT_PIPAPO_LT_ALIGN(lt)		(lt)
+#define NFT_PIPAPO_LT_ASSIGN(field, x)	((field)->lt = (x))
+#endif /* NFT_PIPAPO_ALIGN */
+
 #define nft_pipapo_for_each_field(field, index, match)		\
 	for ((field) = (match)->f, (index) = 0;			\
 	     (index) < (match)->field_count;			\
@@ -410,12 +426,16 @@ union nft_pipapo_map_bucket {
  * @rules:	Number of inserted rules
  * @bsize:	Size of each bucket in lookup table, in longs
  * @lt:		Lookup table: 'groups' rows of NFT_PIPAPO_BUCKETS buckets
+ * @lt_aligned:	Version of @lt aligned to NFT_PIPAPO_ALIGN bytes
  * @mt:		Mapping table: one bucket per rule
  */
 struct nft_pipapo_field {
 	int groups;
 	unsigned long rules;
 	size_t bsize;
+#ifdef NFT_PIPAPO_ALIGN
+	unsigned long *lt_aligned;
+#endif
 	unsigned long *lt;
 	union nft_pipapo_map_bucket *mt;
 };
@@ -424,12 +444,16 @@ struct nft_pipapo_field {
  * struct nft_pipapo_match - Data used for lookup and matching
  * @field_count		Amount of fields in set
  * @scratch:		Preallocated per-CPU maps for partial matching results
+ * @scratch_aligned:	Version of @scratch aligned to NFT_PIPAPO_ALIGN bytes
  * @bsize_max:		Maximum lookup table bucket size of all fields, in longs
  * @rcu			Matching data is swapped on commits
  * @f:			Fields, with lookup and mapping tables
  */
 struct nft_pipapo_match {
 	int field_count;
+#ifdef NFT_PIPAPO_ALIGN
+	unsigned long * __percpu *scratch_aligned;
+#endif
 	unsigned long * __percpu *scratch;
 	size_t bsize_max;
 	struct rcu_head rcu;
@@ -738,8 +762,8 @@ static void *pipapo_get(const struct net *net, const struct nft_set *set,
 	memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
 
 	nft_pipapo_for_each_field(f, i, m) {
+		unsigned long *lt = NFT_PIPAPO_LT_ALIGN(f->lt);
 		bool last = i == m->field_count - 1;
-		unsigned long *lt = f->lt;
 		int b, group;
 
 		/* For each 4-bit group: select lookup table bucket depending on
@@ -833,6 +857,10 @@ static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
 	int group, bucket;
 
 	new_bucket_size = DIV_ROUND_UP(rules, BITS_PER_LONG);
+#ifdef NFT_PIPAPO_ALIGN
+	new_bucket_size = roundup(new_bucket_size,
+				  NFT_PIPAPO_ALIGN / sizeof(*new_lt));
+#endif
 
 	if (new_bucket_size == f->bsize)
 		goto mt;
@@ -843,12 +871,14 @@ static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
 		copy = new_bucket_size;
 
 	new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS * new_bucket_size *
-			  sizeof(*new_lt), GFP_KERNEL);
+			  sizeof(*new_lt) + NFT_PIPAPO_ALIGN_HEADROOM,
+			  GFP_KERNEL);
 	if (!new_lt)
 		return -ENOMEM;
 
-	new_p = new_lt;
-	old_p = old_lt;
+	new_p = NFT_PIPAPO_LT_ALIGN(new_lt);
+	old_p = NFT_PIPAPO_LT_ALIGN(old_lt);
+
 	for (group = 0; group < f->groups; group++) {
 		for (bucket = 0; bucket < NFT_PIPAPO_BUCKETS; bucket++) {
 			memcpy(new_p, old_p, copy * sizeof(*new_p));
@@ -877,7 +907,7 @@ static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
 
 	if (new_lt) {
 		f->bsize = new_bucket_size;
-		f->lt = new_lt;
+		NFT_PIPAPO_LT_ASSIGN(f, new_lt);
 		kvfree(old_lt);
 	}
 
@@ -899,7 +929,8 @@ static void pipapo_bucket_set(struct nft_pipapo_field *f, int rule, int group,
 {
 	unsigned long *pos;
 
-	pos = f->lt + f->bsize * NFT_PIPAPO_BUCKETS * group;
+	pos = NFT_PIPAPO_LT_ALIGN(f->lt);
+	pos += f->bsize * NFT_PIPAPO_BUCKETS * group;
 	pos += f->bsize * v;
 
 	__set_bit(rule, pos);
@@ -1123,8 +1154,12 @@ static int pipapo_realloc_scratch(struct nft_pipapo_match *m,
 
 	for_each_possible_cpu(i) {
 		unsigned long *scratch;
+#ifdef NFT_PIPAPO_ALIGN
+		unsigned long *scratch_aligned;
+#endif
 
-		scratch = kzalloc_node(bsize_max * sizeof(*scratch) * 2,
+		scratch = kzalloc_node(bsize_max * sizeof(*scratch) * 2 +
+				       NFT_PIPAPO_ALIGN_HEADROOM,
 				       GFP_KERNEL, cpu_to_node(i));
 		if (!scratch)
 			return -ENOMEM;
@@ -1132,6 +1167,11 @@ static int pipapo_realloc_scratch(struct nft_pipapo_match *m,
 		kfree(*per_cpu_ptr(m->scratch, i));
 
 		*per_cpu_ptr(m->scratch, i) = scratch;
+
+#ifdef NFT_PIPAPO_ALIGN
+		scratch_aligned = NFT_PIPAPO_LT_ALIGN(scratch);
+		*per_cpu_ptr(m->scratch_aligned, i) = scratch_aligned;
+#endif
 	}
 
 	return 0;
@@ -1273,21 +1313,33 @@ static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
 	if (!new->scratch)
 		goto out_scratch;
 
+#ifdef NFT_PIPAPO_ALIGN
+	new->scratch_aligned = alloc_percpu(*new->scratch_aligned);
+	if (!new->scratch_aligned)
+		goto out_scratch;
+#endif
+
 	rcu_head_init(&new->rcu);
 
 	src = old->f;
 	dst = new->f;
 
 	for (i = 0; i < old->field_count; i++) {
+		unsigned long *new_lt;
+
 		memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
 
-		dst->lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS *
-				   src->bsize * sizeof(*dst->lt),
-				   GFP_KERNEL);
-		if (!dst->lt)
+		new_lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS *
+				  src->bsize * sizeof(*dst->lt) +
+				  NFT_PIPAPO_ALIGN_HEADROOM,
+				  GFP_KERNEL);
+		if (!new_lt)
 			goto out_lt;
 
-		memcpy(dst->lt, src->lt,
+		NFT_PIPAPO_LT_ASSIGN(dst, new_lt);
+
+		memcpy(NFT_PIPAPO_LT_ALIGN(new_lt),
+		       NFT_PIPAPO_LT_ALIGN(src->lt),
 		       src->bsize * sizeof(*dst->lt) *
 		       src->groups * NFT_PIPAPO_BUCKETS);
 
@@ -1310,8 +1362,11 @@ static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
 		kvfree(dst->lt);
 		dst--;
 	}
-	free_percpu(new->scratch);
+#ifdef NFT_PIPAPO_ALIGN
+	free_percpu(new->scratch_aligned);
+#endif
 out_scratch:
+	free_percpu(new->scratch);
 	kfree(new);
 
 	return ERR_PTR(-ENOMEM);
@@ -1467,7 +1522,8 @@ static void pipapo_drop(struct nft_pipapo_match *m,
 			unsigned long *pos;
 			int b;
 
-			pos = f->lt + g * NFT_PIPAPO_BUCKETS * f->bsize;
+			pos = NFT_PIPAPO_LT_ALIGN(f->lt) + g *
+			      NFT_PIPAPO_BUCKETS * f->bsize;
 
 			for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
 				bitmap_cut(pos, pos, rulemap[i].to,
@@ -1572,6 +1628,9 @@ static void pipapo_reclaim_match(struct rcu_head *rcu)
 	for_each_possible_cpu(i)
 		kfree(*per_cpu_ptr(m->scratch, i));
 
+#ifdef NFT_PIPAPO_ALIGN
+	free_percpu(m->scratch_aligned);
+#endif
 	free_percpu(m->scratch);
 
 	pipapo_free_fields(m);
@@ -1795,7 +1854,8 @@ static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule,
 		for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
 			unsigned long *pos;
 
-			pos = f->lt + (g * NFT_PIPAPO_BUCKETS + b) * f->bsize;
+			pos = NFT_PIPAPO_LT_ALIGN(f->lt) +
+			      (g * NFT_PIPAPO_BUCKETS + b) * f->bsize;
 			if (test_bit(first_rule, pos) && x0 == -1)
 				x0 = b;
 			if (test_bit(first_rule + rule_count - 1, pos))
@@ -2092,11 +2152,21 @@ static int nft_pipapo_init(const struct nft_set *set,
 	m->scratch = alloc_percpu(unsigned long *);
 	if (!m->scratch) {
 		err = -ENOMEM;
-		goto out_free;
+		goto out_scratch;
 	}
 	for_each_possible_cpu(i)
 		*per_cpu_ptr(m->scratch, i) = NULL;
 
+#ifdef NFT_PIPAPO_ALIGN
+	m->scratch_aligned = alloc_percpu(unsigned long *);
+	if (!m->scratch_aligned) {
+		err = -ENOMEM;
+		goto out_free;
+	}
+	for_each_possible_cpu(i)
+		*per_cpu_ptr(m->scratch_aligned, i) = NULL;
+#endif
+
 	rcu_head_init(&m->rcu);
 
 	f = m->f;
@@ -2114,7 +2184,7 @@ static int nft_pipapo_init(const struct nft_set *set,
 
 		f->bsize = 0;
 		f->rules = 0;
-		f->lt = NULL;
+		NFT_PIPAPO_LT_ASSIGN(f, NULL);
 		f->mt = NULL;
 
 		f++;
@@ -2134,7 +2204,11 @@ static int nft_pipapo_init(const struct nft_set *set,
 	return 0;
 
 out_free:
+#ifdef NFT_PIPAPO_ALIGN
+	free_percpu(m->scratch_aligned);
+#endif
 	free_percpu(m->scratch);
+out_scratch:
 	kfree(m);
 
 	return err;
@@ -2170,16 +2244,21 @@ static void nft_pipapo_destroy(const struct nft_set *set)
 			nft_set_elem_destroy(set, e, true);
 		}
 
+#ifdef NFT_PIPAPO_ALIGN
+		free_percpu(m->scratch_aligned);
+#endif
 		for_each_possible_cpu(cpu)
 			kfree(*per_cpu_ptr(m->scratch, cpu));
 		free_percpu(m->scratch);
-
 		pipapo_free_fields(m);
 		kfree(m);
 		priv->match = NULL;
 	}
 
 	if (priv->clone) {
+#ifdef NFT_PIPAPO_ALIGN
+		free_percpu(priv->clone->scratch_aligned);
+#endif
 		for_each_possible_cpu(cpu)
 			kfree(*per_cpu_ptr(priv->clone->scratch, cpu));
 		free_percpu(priv->clone->scratch);
Signature · 1 line
2.20.1
#12 lore raw

PATCH 7/8 nft_set_pipapo: Prepare for vectorised implementation: helpers

In reply to Stefano Brivio

Move most macros and helpers to a header file, so that they can be conveniently used by related implementations.

No functional changes are intended here.

---
 net/netfilter/nft_set_pipapo.c | 218 ++---------------------------
 net/netfilter/nft_set_pipapo.h | 242 +++++++++++++++++++++++++++++++++
 2 files changed, 250 insertions(+), 210 deletions(-)
 create mode 100644 net/netfilter/nft_set_pipapo.h
net/netfilter/nft_set_pipapo.c +8 -210
index 63d54f9fcac0..7fc3ec7232b7 100644
@@ -330,179 +330,20 @@
 
 #include <linux/kernel.h>
 #include <linux/init.h>
-#include <linux/log2.h>
 #include <linux/module.h>
 #include <linux/netlink.h>
 #include <linux/netfilter.h>
 #include <linux/netfilter/nf_tables.h>
 #include <net/netfilter/nf_tables_core.h>
 #include <uapi/linux/netfilter/nf_tables.h>
-#include <net/ipv6.h>			/* For the maximum length of a field */
 #include <linux/bitmap.h>
 #include <linux/bitops.h>
 
-/* Count of concatenated fields depends on count of 32-bit nftables registers */
-#define NFT_PIPAPO_MAX_FIELDS		NFT_REG32_COUNT
-
-/* Largest supported field size */
-#define NFT_PIPAPO_MAX_BYTES		(sizeof(struct in6_addr))
-#define NFT_PIPAPO_MAX_BITS		(NFT_PIPAPO_MAX_BYTES * BITS_PER_BYTE)
-
-/* Number of bits to be grouped together in lookup table buckets, arbitrary */
-#define NFT_PIPAPO_GROUP_BITS		4
-#define NFT_PIPAPO_GROUPS_PER_BYTE	(BITS_PER_BYTE / NFT_PIPAPO_GROUP_BITS)
-
-/* Fields are padded to 32 bits in input registers */
-#define NFT_PIPAPO_GROUPS_PADDED_SIZE(x)				\
-	(round_up((x) / NFT_PIPAPO_GROUPS_PER_BYTE, sizeof(u32)))
-#define NFT_PIPAPO_GROUPS_PADDING(x)					\
-	(NFT_PIPAPO_GROUPS_PADDED_SIZE((x)) - (x) / NFT_PIPAPO_GROUPS_PER_BYTE)
-
-/* Number of buckets, given by 2 ^ n, with n grouped bits */
-#define NFT_PIPAPO_BUCKETS		(1 << NFT_PIPAPO_GROUP_BITS)
-
-/* Each n-bit range maps to up to n * 2 rules */
-#define NFT_PIPAPO_MAP_NBITS		(const_ilog2(NFT_PIPAPO_MAX_BITS * 2))
-
-/* Use the rest of mapping table buckets for rule indices, but it makes no sense
- * to exceed 32 bits
- */
-#if BITS_PER_LONG == 64
-#define NFT_PIPAPO_MAP_TOBITS		32
-#else
-#define NFT_PIPAPO_MAP_TOBITS		(BITS_PER_LONG - NFT_PIPAPO_MAP_NBITS)
-#endif
-
-/* ...which gives us the highest allowed index for a rule */
-#define NFT_PIPAPO_RULE0_MAX		((1UL << (NFT_PIPAPO_MAP_TOBITS - 1)) \
-					- (1UL << NFT_PIPAPO_MAP_NBITS))
-
-/* Definitions for vectorised implementations */
-#ifdef NFT_PIPAPO_ALIGN
-#define NFT_PIPAPO_ALIGN_HEADROOM					\
-	(NFT_PIPAPO_ALIGN - ARCH_KMALLOC_MINALIGN)
-#define NFT_PIPAPO_LT_ALIGN(lt)		(PTR_ALIGN((lt), NFT_PIPAPO_ALIGN))
-#define NFT_PIPAPO_LT_ASSIGN(field, x)					\
-	do {								\
-		(field)->lt_aligned = NFT_PIPAPO_LT_ALIGN(x);		\
-		(field)->lt = (x);					\
-	} while (0)
-#else
-#define NFT_PIPAPO_ALIGN_HEADROOM	0
-#define NFT_PIPAPO_LT_ALIGN(lt)		(lt)
-#define NFT_PIPAPO_LT_ASSIGN(field, x)	((field)->lt = (x))
-#endif /* NFT_PIPAPO_ALIGN */
-
-#define nft_pipapo_for_each_field(field, index, match)		\
-	for ((field) = (match)->f, (index) = 0;			\
-	     (index) < (match)->field_count;			\
-	     (index)++, (field)++)
-
-/**
- * union nft_pipapo_map_bucket - Bucket of mapping table
- * @to:		First rule number (in next field) this rule maps to
- * @n:		Number of rules (in next field) this rule maps to
- * @e:		If there's no next field, pointer to element this rule maps to
- */
-union nft_pipapo_map_bucket {
-	struct {
-#if BITS_PER_LONG == 64
-		static_assert(NFT_PIPAPO_MAP_TOBITS <= 32);
-		u32 to;
-
-		static_assert(NFT_PIPAPO_MAP_NBITS <= 32);
-		u32 n;
-#else
-		unsigned long to:NFT_PIPAPO_MAP_TOBITS;
-		unsigned long  n:NFT_PIPAPO_MAP_NBITS;
-#endif
-	};
-	struct nft_pipapo_elem *e;
-};
-
-/**
- * struct nft_pipapo_field - Lookup, mapping tables and related data for a field
- * @groups:	Amount of 4-bit groups
- * @rules:	Number of inserted rules
- * @bsize:	Size of each bucket in lookup table, in longs
- * @lt:		Lookup table: 'groups' rows of NFT_PIPAPO_BUCKETS buckets
- * @lt_aligned:	Version of @lt aligned to NFT_PIPAPO_ALIGN bytes
- * @mt:		Mapping table: one bucket per rule
- */
-struct nft_pipapo_field {
-	int groups;
-	unsigned long rules;
-	size_t bsize;
-#ifdef NFT_PIPAPO_ALIGN
-	unsigned long *lt_aligned;
-#endif
-	unsigned long *lt;
-	union nft_pipapo_map_bucket *mt;
-};
-
-/**
- * struct nft_pipapo_match - Data used for lookup and matching
- * @field_count		Amount of fields in set
- * @scratch:		Preallocated per-CPU maps for partial matching results
- * @scratch_aligned:	Version of @scratch aligned to NFT_PIPAPO_ALIGN bytes
- * @bsize_max:		Maximum lookup table bucket size of all fields, in longs
- * @rcu			Matching data is swapped on commits
- * @f:			Fields, with lookup and mapping tables
- */
-struct nft_pipapo_match {
-	int field_count;
-#ifdef NFT_PIPAPO_ALIGN
-	unsigned long * __percpu *scratch_aligned;
-#endif
-	unsigned long * __percpu *scratch;
-	size_t bsize_max;
-	struct rcu_head rcu;
-	struct nft_pipapo_field f[0];
-};
+#include "nft_set_pipapo.h"
 
 /* Current working bitmap index, toggled between field matches */
 static DEFINE_PER_CPU(bool, nft_pipapo_scratch_index);
 
-/**
- * struct nft_pipapo - Representation of a set
- * @match:	Currently in-use matching data
- * @clone:	Copy where pending insertions and deletions are kept
- * @groups:	Total amount of 4-bit groups for fields in this set
- * @width:	Total bytes to be matched for one packet, including padding
- * @dirty:	Working copy has pending insertions or deletions
- * @last_gc:	Timestamp of last garbage collection run, jiffies
- * @start_data:	Key data of start element for insertion
- * @start_elem:	Start element for insertion
- *
- * nft_pipapo_insert() is called separately with start and end elements to be
- * inserted. While a tree implementation (see nft_set_rbtree) can insert nodes
- * in the tree right away, we need to cache the start element, and perform the
- * actual insertion once the end element is also seen. This is fine as insertion
- * is serialised by the nftables API.
- */
-struct nft_pipapo {
-	struct nft_pipapo_match __rcu *match;
-	struct nft_pipapo_match *clone;
-	int groups;
-	int width;
-	bool dirty;
-	unsigned long last_gc;
-	u8 start_data[NFT_DATA_VALUE_MAXLEN * sizeof(u32)];
-	struct nft_pipapo_elem *start_elem;
-};
-
-struct nft_pipapo_elem;
-
-/**
- * struct nft_pipapo_elem - API-facing representation of single set element
- * @start:	Pointer to element that represents start of interval
- * @ext:	nftables API extensions
- */
-struct nft_pipapo_elem {
-	struct nft_pipapo_elem *start;
-	struct nft_set_ext ext;
-};
-
 /**
  * pipapo_refill() - For each set bit, set bits from selected mapping table item
  * @map:	Bitmap to be scanned for set bits
@@ -520,9 +361,8 @@ struct nft_pipapo_elem {
  *
  * Return: -1 on no match, bit position on 'match_only', 0 otherwise.
  */
-static int pipapo_refill(unsigned long *map, int len, int rules,
-			 unsigned long *dst, union nft_pipapo_map_bucket *mt,
-			 bool match_only)
+int pipapo_refill(unsigned long *map, int len, int rules, unsigned long *dst,
+		  union nft_pipapo_map_bucket *mt, bool match_only)
 {
 	unsigned long bitset;
 	int k, ret = -1;
@@ -640,7 +480,7 @@ static bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
 	nft_pipapo_for_each_field(f, i, m) {
 		bool last = i == m->field_count - 1;
 		unsigned long *lt = f->lt;
-		int b, group, j;
+		int b, j;
 
 		/* For each 4-bit group: select lookup table bucket depending on
 		 * packet bytes value, then AND bucket value. Unroll loops for
@@ -658,21 +498,8 @@ static bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
 		} else if (f->groups == 32) {
 			NFT_PIPAPO_MATCH_32(res_map, lt, f->bsize, rp, j);
 		} else {
-			for (group = 0; group < f->groups; group++) {
-				u8 v;
-
-				if (group % 2) {
-					v = *rp & 0x0f;
-					rp++;
-				} else {
-					v = *rp >> 4;
-				}
-				__bitmap_and(res_map, res_map,
-					     lt + v * f->bsize,
-					     f->bsize * BITS_PER_LONG);
-
-				lt += f->bsize * NFT_PIPAPO_BUCKETS;
-			}
+			pipapo_and_field_buckets(f, res_map, rp);
+			rp += f->groups / NFT_PIPAPO_GROUPS_PER_BYTE;
 		}
 
 		/* Now populate the bitmap for the next field, unless this is
@@ -2052,21 +1879,11 @@ static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
 }
 
 /**
- * nft_pipapo_estimate() - Estimate set size, space and lookup complexity
+ * nft_pipapo_estimate() - Set size, space and lookup complexity
  * @desc:	Set description, initial element count used here
  * @features:	Flags: NFT_SET_SUBKEY needs to be there
  * @est:	Storage for estimation data
  *
- * The size for this set type can vary dramatically, as it depends on the number
- * of rules (composing netmasks) the entries expand to. We compute the worst
- * case here, in order to ensure that other types are used if concatenation of
- * ranges is not needed.
- *
- * In general, for a non-ranged entry or a single composing netmask, we need
- * one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
- * is, each input bit needs four bits of matching data), plus a bucket in the
- * mapping table for each field.
- *
  * Return: true
  */
 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
@@ -2075,26 +1892,7 @@ static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
 	if (!(features & NFT_SET_SUBKEY))
 		return false;
 
-	est->size = sizeof(struct nft_pipapo) + sizeof(struct nft_pipapo_match);
-
-	/* Worst-case with current amount of 32-bit VM registers (16 of them):
-	 * - 2 IPv6 addresses	8 registers
-	 * - 2 interface names	8 registers
-	 * that is, four 128-bit fields:
-	 */
-	est->size += sizeof(struct nft_pipapo_field) * 4;
-
-	/* expanding to worst-case ranges, 128 * 2 rules each, resulting in:
-	 * - 128 4-bit groups
-	 * - each set entry taking 256 bits in each bucket
-	 */
-	est->size += desc->size * NFT_PIPAPO_MAX_BITS / NFT_PIPAPO_GROUP_BITS *
-		     NFT_PIPAPO_BUCKETS * NFT_PIPAPO_MAX_BITS * 2 /
-		     BITS_PER_BYTE;
-
-	/* and we need mapping buckets, too */
-	est->size += desc->size * NFT_PIPAPO_MAP_NBITS *
-		     sizeof(union nft_pipapo_map_bucket);
+	est->size = pipapo_estimate_size(desc->size);
 
 	est->lookup = NFT_SET_CLASS_O_LOG_N;
 
net/netfilter/nft_set_pipapo.h new file +242 -0

242 lines not on this page · raw message

Signature · 1 line
2.20.1
#13 lore raw

PATCH 8/8 nft_set_pipapo: Introduce AVX2-based lookup implementation

In reply to Stefano Brivio

If the AVX2 set is available, we can exploit the repetitive characteristic of this algorithm to provide a fast, vectorised version by using 256-bit wide AVX2 operands for bucket loads and bitwise intersections.

In most cases, this implementation consistently outperforms rbtree set instances despite the fact they are configured to use a given, single, ranged data type out of the ones used for performance measurements by the nft_concat_range.sh kselftest.

That script, injecting packets directly on the ingoing device path with pktgen, reports:

- for one AMD Epyc 7351 thread (2.9GHz, 512 KiB L1D$, 8 MiB L2$):

TEST: performance
net,port [ OK ]
baseline (drop from netdev hook): 10195687pps
baseline hash (non-ranged entries): 6166047pps
baseline rbtree (match on first field only): 2648166pps
set with 1000 full, ranged entries: 5013920pps
port,net [ OK ]
baseline (drop from netdev hook): 10146446pps
baseline hash (non-ranged entries): 5958857pps
baseline rbtree (match on first field only): 3972543pps
set with 100 full, ranged entries: 5032332pps
net6,port [ OK ]

    baseline (drop from netdev hook):               9621089pps
    baseline hash (non-ranged entries):             4784304pps
    baseline rbtree (match on first field only):    1349369pps
    set with  1000 full, ranged entries:            2413250pps
  port,proto                                                    [ OK ]
    baseline (drop from netdev hook):              10821583pps
    baseline hash (non-ranged entries):             6809399pps
    baseline rbtree (match on first field only):    2799538pps
    set with 30000 full, ranged entries:            1921039pps
  net6,port,mac                                                 [ OK ]
    baseline (drop from netdev hook):               9460996pps
    baseline hash (non-ranged entries):             3893325pps
    baseline rbtree (match on first field only):    2919418pps
    set with    10 full, ranged entries:            2898623pps
  net6,port,mac,proto                                           [ OK ]
    baseline (drop from netdev hook):               9578663pps
    baseline hash (non-ranged entries):             3705263pps
    baseline rbtree (match on first field only):    1342876pps
    set with  1000 full, ranged entries:            2005030pps

net,mac [ OK ]
baseline (drop from netdev hook): 10153020pps
baseline hash (non-ranged entries): 5145586pps
baseline rbtree (match on first field only): 2664821pps
set with 1000 full, ranged entries: 3922839pps

- for one Intel Core i7-6600U thread (3.4GHz, 64 KiB L1D$, 512 KiB L2$):

TEST: performance
net,port [ OK ]
baseline (drop from netdev hook): 10229859pps
baseline hash (non-ranged entries): 6160930pps
baseline rbtree (match on first field only): 2926966pps
set with 1000 full, ranged entries: 4812717pps
port,net [ OK ]
baseline (drop from netdev hook): 10234013pps
baseline hash (non-ranged entries): 6164457pps
baseline rbtree (match on first field only): 4019270pps
set with 100 full, ranged entries: 5072830pps
net6,port [ OK ]

    baseline (drop from netdev hook):               9603512pps
    baseline hash (non-ranged entries):             4771150pps
    baseline rbtree (match on first field only):    1610077pps
    set with  1000 full, ranged entries:            2942229pps
  port,proto                                                    [ OK ]
    baseline (drop from netdev hook):              10912230pps
    baseline hash (non-ranged entries):             6906587pps
    baseline rbtree (match on first field only):    3156167pps
    set with 30000 full, ranged entries:            2440219pps
  net6,port,mac                                                 [ OK ]
    baseline (drop from netdev hook):              10020213pps
    baseline hash (non-ranged entries):             3415258pps
    baseline rbtree (match on first field only):    3167192pps
    set with    10 full, ranged entries:            2422204pps
  net6,port,mac,proto                                           [ OK ]
    baseline (drop from netdev hook):               9860087pps
    baseline hash (non-ranged entries):             3883861pps
    baseline rbtree (match on first field only):    1626784pps
    set with  1000 full, ranged entries:            2318861pps

net,mac [ OK ]
baseline (drop from netdev hook): 10313285pps
baseline hash (non-ranged entries): 5324213pps
baseline rbtree (match on first field only): 2970661pps
set with 1000 full, ranged entries: 4128105pps

A similar strategy could be easily reused to implement specialised versions for other SIMD sets, and I plan to post at least a NEON version at a later time.

---
 include/net/netfilter/nf_tables_core.h |   1 +
 net/netfilter/Makefile                 |   3 +
 net/netfilter/nf_tables_set_core.c     |   6 +
 net/netfilter/nft_set_pipapo.c         |  25 +
 net/netfilter/nft_set_pipapo_avx2.c    | 840 +++++++++++++++++++++++++
 net/netfilter/nft_set_pipapo_avx2.h    |  14 +
 6 files changed, 889 insertions(+)
 create mode 100644 net/netfilter/nft_set_pipapo_avx2.c
 create mode 100644 net/netfilter/nft_set_pipapo_avx2.h
include/net/netfilter/nf_tables_core.h +1 -0
index 9759257ec8ec..6b7cdc0a592f 100644
@@ -75,6 +75,7 @@ extern struct nft_set_type nft_set_hash_fast_type;
 extern struct nft_set_type nft_set_rbtree_type;
 extern struct nft_set_type nft_set_bitmap_type;
 extern struct nft_set_type nft_set_pipapo_type;
+extern struct nft_set_type nft_set_pipapo_avx2_type;
 
 struct nft_expr;
 struct nft_regs;
net/netfilter/Makefile +3 -0
index 3f572e5a975e..847b759895fc 100644
@@ -83,6 +83,9 @@ nf_tables-objs := nf_tables_core.o nf_tables_api.o nft_chain_filter.o \
 nf_tables_set-objs := nf_tables_set_core.o \
 		      nft_set_hash.o nft_set_bitmap.o nft_set_rbtree.o \
 		      nft_set_pipapo.o
+ifneq (,$(findstring -DCONFIG_AS_AVX2=1,$(KBUILD_CFLAGS)))
+nf_tables_set-objs += nft_set_pipapo_avx2.o
+endif
 
 obj-$(CONFIG_NF_TABLES)		+= nf_tables.o
 obj-$(CONFIG_NF_TABLES_SET)	+= nf_tables_set.o
net/netfilter/nf_tables_set_core.c +6 -0
index 586b621007eb..4fa8f610038c 100644
@@ -9,6 +9,9 @@ static int __init nf_tables_set_module_init(void)
 	nft_register_set(&nft_set_rhash_type);
 	nft_register_set(&nft_set_bitmap_type);
 	nft_register_set(&nft_set_rbtree_type);
+#ifdef CONFIG_AS_AVX2
+	nft_register_set(&nft_set_pipapo_avx2_type);
+#endif
 	nft_register_set(&nft_set_pipapo_type);
 
 	return 0;
@@ -17,6 +20,9 @@ static int __init nf_tables_set_module_init(void)
 static void __exit nf_tables_set_module_exit(void)
 {
 	nft_unregister_set(&nft_set_pipapo_type);
+#ifdef CONFIG_AS_AVX2
+	nft_unregister_set(&nft_set_pipapo_avx2_type);
+#endif
 	nft_unregister_set(&nft_set_rbtree_type);
 	nft_unregister_set(&nft_set_bitmap_type);
 	nft_unregister_set(&nft_set_rhash_type);
net/netfilter/nft_set_pipapo.c +25 -0
index 7fc3ec7232b7..067fe011f62a 100644
@@ -339,6 +339,7 @@
 #include <linux/bitmap.h>
 #include <linux/bitops.h>
 
+#include "nft_set_pipapo_avx2.h"
 #include "nft_set_pipapo.h"
 
 /* Current working bitmap index, toggled between field matches */
@@ -2104,3 +2105,27 @@ struct nft_set_type nft_set_pipapo_type __read_mostly = {
 		.elemsize	= offsetof(struct nft_pipapo_elem, ext),
 	},
 };
+
+#ifdef CONFIG_AS_AVX2
+struct nft_set_type nft_set_pipapo_avx2_type __read_mostly = {
+	.owner		= THIS_MODULE,
+	.features	= NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
+			  NFT_SET_TIMEOUT | NFT_SET_SUBKEY,
+	.ops		= {
+		.lookup		= nft_pipapo_avx2_lookup,
+		.insert		= nft_pipapo_insert,
+		.activate	= nft_pipapo_activate,
+		.deactivate	= nft_pipapo_deactivate,
+		.flush		= nft_pipapo_flush,
+		.remove		= nft_pipapo_remove,
+		.walk		= nft_pipapo_walk,
+		.get		= nft_pipapo_get,
+		.privsize	= nft_pipapo_privsize,
+		.estimate	= nft_pipapo_avx2_estimate,
+		.init		= nft_pipapo_init,
+		.destroy	= nft_pipapo_destroy,
+		.gc_init	= nft_pipapo_gc_init,
+		.elemsize	= offsetof(struct nft_pipapo_elem, ext),
+	},
+};
+#endif
net/netfilter/nft_set_pipapo_avx2.c new file +840 -0

840 lines not on this page · raw message

net/netfilter/nft_set_pipapo_avx2.h new file +14 -0
new file mode 100644
index 000000000000..396caf7bfca8
@@ -0,0 +1,14 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+#ifndef _NFT_SET_PIPAPO_AVX2_H
+
+#ifdef CONFIG_AS_AVX2
+#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 /* CONFIG_AS_AVX2 */
+
+#endif /* _NFT_SET_PIPAPO_AVX2_H */
Signature · 1 line
2.20.1
maintainer
#14 lore raw

Re: [PATCH nf-next 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation

Quoted 9 lines · Stefano Brivio

If the AVX2 set is available, we can exploit the repetitive characteristic of this algorithm to provide a fast, vectorised version by using 256-bit wide AVX2 operands for bucket loads and bitwise intersections.

In most cases, this implementation consistently outperforms rbtree set instances despite the fact they are configured to use a given, single, ranged data type out of the ones used for performance measurements by the nft_concat_range.sh kselftest.

I think in that case it makes sense to remove rbtree once this new set type has had some upstream exposure and let pipapo handle the range sets.

Stefano, if I understand this right then we could figure out which implementation (C or AVX) is used via "grep avx2 /proc/cpuinfo".

If not, I think we might want to expose some additional debug info on set dumps.

reviewer
#15 lore raw

Re: [PATCH nf-next 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation

Quoted 15 lines · Florian Westphal
Quoted 9 lines · Stefano Brivio

If the AVX2 set is available, we can exploit the repetitive characteristic of this algorithm to provide a fast, vectorised version by using 256-bit wide AVX2 operands for bucket loads and bitwise intersections.

In most cases, this implementation consistently outperforms rbtree set instances despite the fact they are configured to use a given, single, ranged data type out of the ones used for performance measurements by the nft_concat_range.sh kselftest.

I think in that case it makes sense to remove rbtree once this new set type has had some upstream exposure and let pipapo handle the range sets.

Quoted 5 lines

Stefano, if I understand this right then we could figure out which implementation (C or AVX) is used via "grep avx2 /proc/cpuinfo".

If not, I think we might want to expose some additional debug info on set dumps.

I once submitted a patch introducing NFTA_SET_OPS, an attribute holding set type's name in dumps. Maybe we can reuse that? It is message ID [email protected] (Subject: [PATCH v2 2/2] net:
nftables: Export set backend name via netlink).

Cheers, Phil

#16 lore raw

Re: [PATCH nf-next 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation

Quoted 12 lines · On Wed, 20 Nov 2019 17:08:00 +0100 Phil Sutter <[email protected]> wrote:
Quoted 11 lines · Florian Westphal
Quoted 9 lines · Stefano Brivio

If the AVX2 set is available, we can exploit the repetitive characteristic of this algorithm to provide a fast, vectorised version by using 256-bit wide AVX2 operands for bucket loads and bitwise intersections.

In most cases, this implementation consistently outperforms rbtree set instances despite the fact they are configured to use a given, single, ranged data type out of the ones used for performance measurements by the nft_concat_range.sh kselftest.

Quoted 6 lines
Quoted 6 lines

I think in that case it makes sense to remove rbtree once this new set type has had some upstream exposure and let pipapo handle the range sets.

Stefano, if I understand this right then we could figure out which implementation (C or AVX) is used via "grep avx2 /proc/cpuinfo".

In practice, that's correct.

Strictly speaking, this is not portable, because other architectures might decide to have an 'avx2' flag that means something different, so...

Quoted 7 lines
Quoted 2 lines

If not, I think we might want to expose some additional debug info on set dumps.

I once submitted a patch introducing NFTA_SET_OPS, an attribute holding set type's name in dumps. Maybe we can reuse that? It is message ID [email protected] (Subject: [PATCH v2 2/2] net:
nftables: Export set backend name via netlink).

...I would rather try to introduce this at a later time. I just
wonder: what was the problem with that series? :)

Signature · 1 line
Stefano
#17 lore raw

Re: [PATCH nf-next 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation

Quoted 5 lines · Stefano Brivio
Quoted 2 lines · On Wed, 20 Nov 2019 17:08:00 +0100 Phil Sutter <[email protected]> wrote:
Quoted 1 line · Florian Westphal

Stefano Brivio <[email protected]> wrote:

[...]

Quoted 10 lines
Quoted 7 lines
Quoted 2 lines

If not, I think we might want to expose some additional debug info on set dumps.

I once submitted a patch introducing NFTA_SET_OPS, an attribute holding set type's name in dumps. Maybe we can reuse that? It is message ID [email protected] (Subject: [PATCH v2 2/2] net:
nftables: Export set backend name via netlink).

...I would rather try to introduce this at a later time. I just
wonder: what was the problem with that series? :)

For datastructure like bitmap and hashtable, the tuning parameters are well-known probably and rather trivial for everyone. However, for composite datastructures, this is not.

In general, I think the developer should better know how to optimize the tuning of the datastructure based on the description. Rather than assuming that the user knows how to tune things and exposing n-thousand knobs for configuring things.

Moreover, if it turns out that we ever get something better than pipapo in the future to represent this, then we cannot transparently get rid of this code in favour of the new one. And I'm not telling I know a better way to do what you're proposing right now :-)

Probably, at some point we can start exposing knobs, but I'd rather see a bit more discussions on how to provide a good autotuning. By exposing all knobs, then such discussion might not ever happen?

maintainer
#18 lore raw

Re: [PATCH nf-next 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation

Quoted 3 lines · Pablo Neira Ayuso

Probably, at some point we can start exposing knobs, but I'd rather see a bit more discussions on how to provide a good autotuning. By exposing all knobs, then such discussion might not ever happen?

My remarks were not aimed at exposing knobs but to provide some debugging aid.

Say e.g. there is a bug in the avx implementation that isn't present in the C version, or vice versa. Or in rhashtable but not hashtable.

Right now it requires some guesswork to figure out what set backend is actually used for @myset, and it might make things easier for debugging if one could query the kernel for some information wrt. what set backend is used. I would try to avoid to expose anything that can't be ripped out again, so e.g. names or even just %pF of ->lookup() would perhaps be enough.

#19 lore raw

Re: [PATCH nf-next 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation

Quoted 10 lines · Florian Westphal
Quoted 3 lines · Pablo Neira Ayuso

Probably, at some point we can start exposing knobs, but I'd rather see a bit more discussions on how to provide a good autotuning. By exposing all knobs, then such discussion might not ever happen?

My remarks were not aimed at exposing knobs but to provide some debugging aid.

Say e.g. there is a bug in the avx implementation that isn't present in the C version, or vice versa. Or in rhashtable but not hashtable.

Ah indeed, thanks for explaining.

Quoted 6 lines

Right now it requires some guesswork to figure out what set backend is actually used for @myset, and it might make things easier for debugging if one could query the kernel for some information wrt. what set backend is used. I would try to avoid to expose anything that can't be ripped out again, so e.g. names or even just %pF of ->lookup() would perhaps be enough.

I think exposing names would be fine. Probably you can also add name to operations, instead of %pF of lookup.

Thanks.

#20 lore raw

Re: [PATCH nf-next 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation

Quoted 21 lines · Pablo Neira Ayuso
Quoted 10 lines · Florian Westphal
Quoted 3 lines · Pablo Neira Ayuso

Probably, at some point we can start exposing knobs, but I'd rather see a bit more discussions on how to provide a good autotuning. By exposing all knobs, then such discussion might not ever happen?

My remarks were not aimed at exposing knobs but to provide some debugging aid.

Say e.g. there is a bug in the avx implementation that isn't present in the C version, or vice versa. Or in rhashtable but not hashtable.

Ah indeed, thanks for explaining.

Quoted 6 lines

Right now it requires some guesswork to figure out what set backend is actually used for @myset, and it might make things easier for debugging if one could query the kernel for some information wrt. what set backend is used. I would try to avoid to expose anything that can't be ripped out again, so e.g. names or even just %pF of ->lookup() would perhaps be enough.

Quoted 2 lines

I think exposing names would be fine. Probably you can also add name to operations, instead of %pF of lookup.

At second spin, %pF should be fine too. Names are fine, you pick the way.

#21 lore raw

Re: [PATCH nf-next 8/8] nft_set_pipapo: Introduce AVX2-based lookup implementation

In reply to Florian Westphal
Quoted 6 lines · Florian Westphal
Quoted 5 lines · Stefano Brivio

If the AVX2 set is available, we can exploit the repetitive characteristic of this algorithm to provide a fast, vectorised version by using 256-bit wide AVX2 operands for bucket loads and bitwise intersections.

Quoted 8 lines
Quoted 4 lines

In most cases, this implementation consistently outperforms rbtree set instances despite the fact they are configured to use a given, single, ranged data type out of the ones used for performance measurements by the nft_concat_range.sh kselftest.

I think in that case it makes sense to remove rbtree once this new set type has had some upstream exposure and let pipapo handle the range sets.

Agreed.