Skip to contentSkip to conversation

nftables: Set implementation for arbitrary concatenation of ranges

PATCH In review Stefano Brivio 4 participants 20 messages Jan 21, 2020 – Feb 20, 2020

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

v4 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 5/9, 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 5/9 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.

Patches 1/9 to 3/9 implement the needed infrastructure: new attributes are used to describe length of single ranged fields in concatenations and to denote the upper bound for ranges.

Patch 4/9 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 5/9 is the actual set implementation.

Patch 6/9 introduces selftests for the new implementation.

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

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

The nftables and libnftnl counterparts depend on changes to the UAPI header file included in patches 2/9 and 3/9.

Credits go to Jay Ligatti, Josh Kuhn, and Chris Gage for their original Grouper implementation and article from ICCCN proceedings (see reference in patch 5/9), 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 5/9.

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, to Phil Sutter for reaffirming the need for the use case covered here, and to Pablo Neira Ayuso for proposing a dramatic simplification of the infrastructure.

v4:
- fix build for 32-bit architectures: 64-bit division needs div_u64() in 5/9 (kbuild test robot <[email protected]>)
v3:
- add patches 1/9 and 2/9
- drop patch 5/8 (unrolled lookup loops), as it actually decreases matching rates in some cases
- other changes listed in single patches
v2: Changes listed in messages for 3/8 and 8/8

Pablo Neira Ayuso (2):
netfilter: nf_tables: add nft_setelem_parse_key()
netfilter: nf_tables: add NFTA_SET_ELEM_KEY_END attribute

Stefano Brivio (7):
netfilter: nf_tables: Support for sets 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: 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.h             |   22 +-
 include/net/netfilter/nf_tables_core.h        |    2 +
 include/uapi/linux/netfilter/nf_tables.h      |   17 +
 lib/bitmap.c                                  |   66 +
 net/netfilter/Makefile                        |    8 +-
 net/netfilter/nf_tables_api.c                 |  260 ++-
 net/netfilter/nf_tables_set_core.c            |    8 +
 net/netfilter/nft_dynset.c                    |    2 +-
 net/netfilter/nft_set_pipapo.c                | 2012 +++++++++++++++++
 net/netfilter/nft_set_pipapo.h                |  237 ++
 net/netfilter/nft_set_pipapo_avx2.c           |  842 +++++++
 net/netfilter/nft_set_pipapo_avx2.h           |   14 +
 net/netfilter/nft_set_rbtree.c                |    3 +
 tools/testing/selftests/netfilter/Makefile    |    3 +-
 .../selftests/netfilter/nft_concat_range.sh   | 1481 ++++++++++++
 16 files changed, 4911 insertions(+), 70 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.24.1
#1 lore raw

PATCH v4 1/9 netfilter: nf_tables: add nft_setelem_parse_key()

From: Pablo Neira Ayuso <[email protected]>

Add helper function to parse the set element key netlink attribute.

v4: No changes
v3: New patch

[sbrivio: refactor error paths and labels; use NFT_DATA_VALUE_MAXLEN
instead of sizeof(*key) in helper, value can be longer than that; rebase]

---
 net/netfilter/nf_tables_api.c | 91 +++++++++++++++++------------------
 1 file changed, 45 insertions(+), 46 deletions(-)
net/netfilter/nf_tables_api.c +45 -46
index 43f05b3acd60..0628b9ad7aa4 100644
@@ -4490,11 +4490,28 @@ static int nft_setelem_parse_flags(const struct nft_set *set,
 	return 0;
 }
 
+static int nft_setelem_parse_key(struct nft_ctx *ctx, struct nft_set *set,
+				 struct nft_data *key, struct nlattr *attr)
+{
+	struct nft_data_desc desc;
+	int err;
+
+	err = nft_data_init(ctx, key, NFT_DATA_VALUE_MAXLEN, &desc, attr);
+	if (err < 0)
+		return err;
+
+	if (desc.type != NFT_DATA_VALUE || desc.len != set->klen) {
+		nft_data_release(key, desc.type);
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
 static int nft_get_set_elem(struct nft_ctx *ctx, struct nft_set *set,
 			    const struct nlattr *attr)
 {
 	struct nlattr *nla[NFTA_SET_ELEM_MAX + 1];
-	struct nft_data_desc desc;
 	struct nft_set_elem elem;
 	struct sk_buff *skb;
 	uint32_t flags = 0;
@@ -4513,17 +4530,11 @@ static int nft_get_set_elem(struct nft_ctx *ctx, struct nft_set *set,
 	if (err < 0)
 		return err;
 
-	err = nft_data_init(ctx, &elem.key.val, sizeof(elem.key), &desc,
-			    nla[NFTA_SET_ELEM_KEY]);
+	err = nft_setelem_parse_key(ctx, set, &elem.key.val,
+				    nla[NFTA_SET_ELEM_KEY]);
 	if (err < 0)
 		return err;
 
-	err = -EINVAL;
-	if (desc.type != NFT_DATA_VALUE || desc.len != set->klen) {
-		nft_data_release(&elem.key.val, desc.type);
-		return err;
-	}
-
 	priv = set->ops->get(ctx->net, set, &elem, flags);
 	if (IS_ERR(priv))
 		return PTR_ERR(priv);
@@ -4722,13 +4733,13 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set,
 {
 	struct nlattr *nla[NFTA_SET_ELEM_MAX + 1];
 	u8 genmask = nft_genmask_next(ctx->net);
-	struct nft_data_desc d1, d2;
 	struct nft_set_ext_tmpl tmpl;
 	struct nft_set_ext *ext, *ext2;
 	struct nft_set_elem elem;
 	struct nft_set_binding *binding;
 	struct nft_object *obj = NULL;
 	struct nft_userdata *udata;
+	struct nft_data_desc desc;
 	struct nft_data data;
 	enum nft_registers dreg;
 	struct nft_trans *trans;
@@ -4794,15 +4805,12 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set,
 			return err;
 	}
 
-	err = nft_data_init(ctx, &elem.key.val, sizeof(elem.key), &d1,
-			    nla[NFTA_SET_ELEM_KEY]);
+	err = nft_setelem_parse_key(ctx, set, &elem.key.val,
+				    nla[NFTA_SET_ELEM_KEY]);
 	if (err < 0)
 		goto err1;
-	err = -EINVAL;
-	if (d1.type != NFT_DATA_VALUE || d1.len != set->klen)
-		goto err2;
 
-	nft_set_ext_add_length(&tmpl, NFT_SET_EXT_KEY, d1.len);
+	nft_set_ext_add_length(&tmpl, NFT_SET_EXT_KEY, set->klen);
 	if (timeout > 0) {
 		nft_set_ext_add(&tmpl, NFT_SET_EXT_EXPIRATION);
 		if (timeout != set->timeout)
@@ -4825,13 +4833,13 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set,
 	}
 
 	if (nla[NFTA_SET_ELEM_DATA] != NULL) {
-		err = nft_data_init(ctx, &data, sizeof(data), &d2,
+		err = nft_data_init(ctx, &data, sizeof(data), &desc,
 				    nla[NFTA_SET_ELEM_DATA]);
 		if (err < 0)
 			goto err2;
 
 		err = -EINVAL;
-		if (set->dtype != NFT_DATA_VERDICT && d2.len != set->dlen)
+		if (set->dtype != NFT_DATA_VERDICT && desc.len != set->dlen)
 			goto err3;
 
 		dreg = nft_type_to_reg(set->dtype);
@@ -4848,18 +4856,18 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set,
 
 			err = nft_validate_register_store(&bind_ctx, dreg,
 							  &data,
-							  d2.type, d2.len);
+							  desc.type, desc.len);
 			if (err < 0)
 				goto err3;
 
-			if (d2.type == NFT_DATA_VERDICT &&
+			if (desc.type == NFT_DATA_VERDICT &&
 			    (data.verdict.code == NFT_GOTO ||
 			     data.verdict.code == NFT_JUMP))
 				nft_validate_state_update(ctx->net,
 							  NFT_VALIDATE_NEED);
 		}
 
-		nft_set_ext_add_length(&tmpl, NFT_SET_EXT_DATA, d2.len);
+		nft_set_ext_add_length(&tmpl, NFT_SET_EXT_DATA, desc.len);
 	}
 
 	/* The full maximum length of userdata can exceed the maximum
@@ -4942,9 +4950,9 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set,
 	kfree(elem.priv);
 err3:
 	if (nla[NFTA_SET_ELEM_DATA] != NULL)
-		nft_data_release(&data, d2.type);
+		nft_data_release(&data, desc.type);
 err2:
-	nft_data_release(&elem.key.val, d1.type);
+	nft_data_release(&elem.key.val, NFT_DATA_VALUE);
 err1:
 	return err;
 }
@@ -5040,7 +5048,6 @@ static int nft_del_setelem(struct nft_ctx *ctx, struct nft_set *set,
 {
 	struct nlattr *nla[NFTA_SET_ELEM_MAX + 1];
 	struct nft_set_ext_tmpl tmpl;
-	struct nft_data_desc desc;
 	struct nft_set_elem elem;
 	struct nft_set_ext *ext;
 	struct nft_trans *trans;
@@ -5051,11 +5058,10 @@ static int nft_del_setelem(struct nft_ctx *ctx, struct nft_set *set,
 	err = nla_parse_nested_deprecated(nla, NFTA_SET_ELEM_MAX, attr,
 					  nft_set_elem_policy, NULL);
 	if (err < 0)
-		goto err1;
+		return err;
 
-	err = -EINVAL;
 	if (nla[NFTA_SET_ELEM_KEY] == NULL)
-		goto err1;
+		return -EINVAL;
 
 	nft_set_ext_prepare(&tmpl);
 
@@ -5065,37 +5071,31 @@ static int nft_del_setelem(struct nft_ctx *ctx, struct nft_set *set,
 	if (flags != 0)
 		nft_set_ext_add(&tmpl, NFT_SET_EXT_FLAGS);
 
-	err = nft_data_init(ctx, &elem.key.val, sizeof(elem.key), &desc,
-			    nla[NFTA_SET_ELEM_KEY]);
+	err = nft_setelem_parse_key(ctx, set, &elem.key.val,
+				    nla[NFTA_SET_ELEM_KEY]);
 	if (err < 0)
-		goto err1;
-
-	err = -EINVAL;
-	if (desc.type != NFT_DATA_VALUE || desc.len != set->klen)
-		goto err2;
+		return err;
 
-	nft_set_ext_add_length(&tmpl, NFT_SET_EXT_KEY, desc.len);
+	nft_set_ext_add_length(&tmpl, NFT_SET_EXT_KEY, set->klen);
 
 	err = -ENOMEM;
 	elem.priv = nft_set_elem_init(set, &tmpl, elem.key.val.data, NULL, 0,
 				      0, GFP_KERNEL);
 	if (elem.priv == NULL)
-		goto err2;
+		goto fail_elem;
 
 	ext = nft_set_elem_ext(set, elem.priv);
 	if (flags)
 		*nft_set_ext_flags(ext) = flags;
 
 	trans = nft_trans_elem_alloc(ctx, NFT_MSG_DELSETELEM, set);
-	if (trans == NULL) {
-		err = -ENOMEM;
-		goto err3;
-	}
+	if (trans == NULL)
+		goto fail_trans;
 
 	priv = set->ops->deactivate(ctx->net, set, &elem);
 	if (priv == NULL) {
 		err = -ENOENT;
-		goto err4;
+		goto fail_ops;
 	}
 	kfree(elem.priv);
 	elem.priv = priv;
@@ -5106,13 +5106,12 @@ static int nft_del_setelem(struct nft_ctx *ctx, struct nft_set *set,
 	list_add_tail(&trans->list, &ctx->net->nft.commit_list);
 	return 0;
 
-err4:
+fail_ops:
 	kfree(trans);
-err3:
+fail_trans:
 	kfree(elem.priv);
-err2:
-	nft_data_release(&elem.key.val, desc.type);
-err1:
+fail_elem:
+	nft_data_release(&elem.key.val, NFT_DATA_VALUE);
 	return err;
 }
 
Signature · 1 line
2.24.1
#2 lore raw

PATCH v4 2/9 netfilter: nf_tables: add NFTA_SET_ELEM_KEY_END attribute

In reply to Stefano Brivio

From: Pablo Neira Ayuso <[email protected]>

Add NFTA_SET_ELEM_KEY_END attribute to convey the closing element of the interval between kernel and userspace.

This patch also adds the NFT_SET_EXT_KEY_END extension to store the closing element value in this interval.

v4: No changes
v3: New patch

[sbrivio: refactor error paths and labels; add corresponding
nft_set_ext_type for new key; rebase]

---
 include/net/netfilter/nf_tables.h        | 14 +++-
 include/uapi/linux/netfilter/nf_tables.h |  2 +
 net/netfilter/nf_tables_api.c            | 85 ++++++++++++++++++------
 net/netfilter/nft_dynset.c               |  2 +-
 4 files changed, 79 insertions(+), 24 deletions(-)
include/net/netfilter/nf_tables.h +13 -1
index fe7c50acc681..504c0aa93805 100644
@@ -231,6 +231,7 @@ struct nft_userdata {
  *	struct nft_set_elem - generic representation of set elements
  *
  *	@key: element key
+ *	@key_end: closing element key
  *	@priv: element private data and extensions
  */
 struct nft_set_elem {
@@ -238,6 +239,10 @@ struct nft_set_elem {
 		u32		buf[NFT_DATA_VALUE_MAXLEN / sizeof(u32)];
 		struct nft_data	val;
 	} key;
+	union {
+		u32		buf[NFT_DATA_VALUE_MAXLEN / sizeof(u32)];
+		struct nft_data	val;
+	} key_end;
 	void			*priv;
 };
 
@@ -502,6 +507,7 @@ void nf_tables_destroy_set(const struct nft_ctx *ctx, struct nft_set *set);
  *	enum nft_set_extensions - set extension type IDs
  *
  *	@NFT_SET_EXT_KEY: element key
+ *	@NFT_SET_EXT_KEY_END: upper bound element key, for ranges
  *	@NFT_SET_EXT_DATA: mapping data
  *	@NFT_SET_EXT_FLAGS: element flags
  *	@NFT_SET_EXT_TIMEOUT: element timeout
@@ -513,6 +519,7 @@ void nf_tables_destroy_set(const struct nft_ctx *ctx, struct nft_set *set);
  */
 enum nft_set_extensions {
 	NFT_SET_EXT_KEY,
+	NFT_SET_EXT_KEY_END,
 	NFT_SET_EXT_DATA,
 	NFT_SET_EXT_FLAGS,
 	NFT_SET_EXT_TIMEOUT,
@@ -606,6 +613,11 @@ static inline struct nft_data *nft_set_ext_key(const struct nft_set_ext *ext)
 	return nft_set_ext(ext, NFT_SET_EXT_KEY);
 }
 
+static inline struct nft_data *nft_set_ext_key_end(const struct nft_set_ext *ext)
+{
+	return nft_set_ext(ext, NFT_SET_EXT_KEY_END);
+}
+
 static inline struct nft_data *nft_set_ext_data(const struct nft_set_ext *ext)
 {
 	return nft_set_ext(ext, NFT_SET_EXT_DATA);
@@ -655,7 +667,7 @@ static inline struct nft_object **nft_set_ext_obj(const struct nft_set_ext *ext)
 
 void *nft_set_elem_init(const struct nft_set *set,
 			const struct nft_set_ext_tmpl *tmpl,
-			const u32 *key, const u32 *data,
+			const u32 *key, const u32 *key_end, const u32 *data,
 			u64 timeout, u64 expiration, gfp_t gfp);
 void nft_set_elem_destroy(const struct nft_set *set, void *elem,
 			  bool destroy_expr);
include/uapi/linux/netfilter/nf_tables.h +2 -0
index 261864736b26..c13106496bd2 100644
@@ -370,6 +370,7 @@ enum nft_set_elem_flags {
  * @NFTA_SET_ELEM_USERDATA: user data (NLA_BINARY)
  * @NFTA_SET_ELEM_EXPR: expression (NLA_NESTED: nft_expr_attributes)
  * @NFTA_SET_ELEM_OBJREF: stateful object reference (NLA_STRING)
+ * @NFTA_SET_ELEM_KEY_END: closing key value (NLA_NESTED: nft_data)
  */
 enum nft_set_elem_attributes {
 	NFTA_SET_ELEM_UNSPEC,
@@ -382,6 +383,7 @@ enum nft_set_elem_attributes {
 	NFTA_SET_ELEM_EXPR,
 	NFTA_SET_ELEM_PAD,
 	NFTA_SET_ELEM_OBJREF,
+	NFTA_SET_ELEM_KEY_END,
 	__NFTA_SET_ELEM_MAX
 };
 #define NFTA_SET_ELEM_MAX	(__NFTA_SET_ELEM_MAX - 1)
net/netfilter/nf_tables_api.c +63 -22

208 lines not on this page · raw message

net/netfilter/nft_dynset.c +1 -1
index 8887295414dc..683785225a3e 100644
@@ -54,7 +54,7 @@ static void *nft_dynset_new(struct nft_set *set, const struct nft_expr *expr,
 
 	timeout = priv->timeout ? : set->timeout;
 	elem = nft_set_elem_init(set, &priv->tmpl,
-				 &regs->data[priv->sreg_key],
+				 &regs->data[priv->sreg_key], NULL,
 				 &regs->data[priv->sreg_data],
 				 timeout, 0, GFP_ATOMIC);
 	if (elem == NULL)
Signature · 1 line
2.24.1
#3 lore raw

PATCH v4 3/9 netfilter: nf_tables: Support for sets with multiple ranged fields

In reply to Stefano Brivio

Introduce a new nested netlink attribute, NFTA_SET_DESC_CONCAT, 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 be selected as they specify support for NFT_SET_INTERVAL and allow desc->field_count to be greater than one. Explicitly disallow this for nft_set_rbtree.

In order to specify the interval for a set entry, userspace would include in NFTA_SET_DESC_CONCAT attributes field lengths, and pass range endpoints as two separate keys, represented by attributes NFTA_SET_ELEM_KEY and NFTA_SET_ELEM_KEY_END.

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:

NFTA_SET_ELEM_KEY: 192.0.2.0 . 22
NFTA_SET_ELEM_KEY_END: 192.0.2.42 . 25

and NFTA_SET_DESC_CONCAT attribute would contain:

NFTA_LIST_ELEM

    NFTA_SET_FIELD_LEN:		4
  NFTA_LIST_ELEM
    NFTA_SET_FIELD_LEN:		2

v4: No changes
v3: Complete rework, NFTA_SET_DESC_CONCAT instead of NFTA_SET_SUBKEY
v2: No changes

---
 include/net/netfilter/nf_tables.h        |  8 +++
 include/uapi/linux/netfilter/nf_tables.h | 15 ++++
 net/netfilter/nf_tables_api.c            | 90 +++++++++++++++++++++++-
 net/netfilter/nft_set_rbtree.c           |  3 +
 4 files changed, 115 insertions(+), 1 deletion(-)
include/net/netfilter/nf_tables.h +8 -0
index 504c0aa93805..4170c033d461 100644
@@ -264,11 +264,15 @@ struct nft_set_iter {
  *	@klen: key length
  *	@dlen: data length
  *	@size: number of set elements
+ *	@field_len: length of each field in concatenation, bytes
+ *	@field_count: number of concatenated fields in element
  */
 struct nft_set_desc {
 	unsigned int		klen;
 	unsigned int		dlen;
 	unsigned int		size;
+	u8			field_len[NFT_REG32_COUNT];
+	u8			field_count;
 };
 
 /**
@@ -409,6 +413,8 @@ void nft_unregister_set(struct nft_set_type *type);
  * 	@dtype: data type (verdict or numeric type defined by userspace)
  * 	@objtype: object type (see NFT_OBJECT_* definitions)
  * 	@size: maximum set size
+ *	@field_len: length of each field in concatenation, bytes
+ *	@field_count: number of concatenated fields in element
  *	@use: number of rules references to this set
  * 	@nelems: number of elements
  * 	@ndeact: number of deactivated elements queued for removal
@@ -435,6 +441,8 @@ struct nft_set {
 	u32				dtype;
 	u32				objtype;
 	u32				size;
+	u8				field_len[NFT_REG32_COUNT];
+	u8				field_count;
 	u32				use;
 	atomic_t			nelems;
 	u32				ndeact;
include/uapi/linux/netfilter/nf_tables.h +15 -0
index c13106496bd2..065218a20bb7 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
@@ -301,14 +302,28 @@ enum nft_set_policies {
  * enum nft_set_desc_attributes - set element description
  *
  * @NFTA_SET_DESC_SIZE: number of elements in set (NLA_U32)
+ * @NFTA_SET_DESC_CONCAT: description of field concatenation (NLA_NESTED)
  */
 enum nft_set_desc_attributes {
 	NFTA_SET_DESC_UNSPEC,
 	NFTA_SET_DESC_SIZE,
+	NFTA_SET_DESC_CONCAT,
 	__NFTA_SET_DESC_MAX
 };
 #define NFTA_SET_DESC_MAX	(__NFTA_SET_DESC_MAX - 1)
 
+/**
+ * enum nft_set_field_attributes - attributes of concatenated fields
+ *
+ * @NFTA_SET_FIELD_LEN: length of single field, in bits (NLA_U32)
+ */
+enum nft_set_field_attributes {
+	NFTA_SET_FIELD_UNSPEC,
+	NFTA_SET_FIELD_LEN,
+	__NFTA_SET_FIELD_MAX
+};
+#define NFTA_SET_FIELD_MAX	(__NFTA_SET_FIELD_MAX - 1)
+
 /**
  * enum nft_set_attributes - nf_tables set netlink attributes
  *
net/netfilter/nf_tables_api.c +89 -1

138 lines not on this page · raw message

net/netfilter/nft_set_rbtree.c +3 -0
index a9f804f7a04a..5000b938ab1e 100644
@@ -466,6 +466,9 @@ static void nft_rbtree_destroy(const struct nft_set *set)
 static bool nft_rbtree_estimate(const struct nft_set_desc *desc, u32 features,
 				struct nft_set_estimate *est)
 {
+	if (desc->field_count > 1)
+		return false;
+
 	if (desc->size)
 		est->size = sizeof(struct nft_rbtree) +
 			    desc->size * sizeof(struct nft_rbtree_elem);
Signature · 1 line
2.24.1
#4 lore raw

PATCH v4 4/9 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.

---
v4: No changes
v3: No changes
v2: No changes

 include/linux/bitmap.h |  4 +++
 lib/bitmap.c           | 66 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+)
include/linux/bitmap.h +4 -0
index ff335b22f23c..f0f3a9fffa6a 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_replace(dst, old, new, mask, nbits)  *dst = (*old & ~(*mask)) | (*new & *mask)
  *  bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
  *  bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
@@ -133,6 +134,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.24.1
#5 lore raw

PATCH v4 5/9 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.

At this point, without further optimisations, nft_concat_range.sh 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): 10190076pps
baseline hash (non-ranged entries): 6179564pps
baseline rbtree (match on first field only): 2950341pps
set with 1000 full, ranged entries: 2304165pps
port,net [ OK ]
baseline (drop from netdev hook): 10143615pps
baseline hash (non-ranged entries): 6135776pps
baseline rbtree (match on first field only): 4311934pps
set with 100 full, ranged entries: 4131471pps
net6,port [ OK ]

    baseline (drop from netdev hook):               9730404pps
    baseline hash (non-ranged entries):             4809557pps
    baseline rbtree (match on first field only):    1501699pps
    set with  1000 full, ranged entries:            1092557pps
  port,proto                                                    [ OK ]
    baseline (drop from netdev hook):              10812426pps
    baseline hash (non-ranged entries):             6929353pps
    baseline rbtree (match on first field only):    3027105pps
    set with 30000 full, ranged entries:             284147pps
  net6,port,mac                                                 [ OK ]
    baseline (drop from netdev hook):               9660114pps
    baseline hash (non-ranged entries):             3778877pps
    baseline rbtree (match on first field only):    3179379pps
    set with    10 full, ranged entries:            2082880pps
  net6,port,mac,proto                                           [ OK ]
    baseline (drop from netdev hook):               9718324pps
    baseline hash (non-ranged entries):             3799021pps
    baseline rbtree (match on first field only):    1506689pps

set with 1000 full, ranged entries: 783810pps
net,mac [ OK ]
baseline (drop from netdev hook): 10190029pps
baseline hash (non-ranged entries): 5172218pps
baseline rbtree (match on first field only): 2946863pps
set with 1000 full, ranged entries: 1279122pps

v4:
- fix build for 32-bit architectures: 64-bit division needs div_u64() (kbuild test robot <[email protected]>)
v3:
- rework interface for field length specification, NFT_SET_SUBKEY disappears and information is stored in description
- remove scratch area to store closing element of ranges, as elements now come with an actual attribute to specify the upper range limit (Pablo Neira Ayuso)
- also remove pointer to 'start' element from mapping table, closing key is now accessible via extension data
- use bytes right away instead of bits for field lengths, this way we can also double the inner loop of the lookup function to take care of upper and lower bits in a single iteration (minor performance improvement)
- make it clearer that set operations are actually atomic API-wise, but we can't e.g. implement flush() as one-shot action
- fix type for 'dup' in nft_pipapo_insert(), check for duplicates only in the next generation, and in general take care of differentiating generation mask cases depending on the operation (Pablo Neira Ayuso)
- report C implementation matching rate in commit message, so that AVX2 implementation can be compared (Pablo Neira Ayuso)
v2:
- protect access to scratch maps in nft_pipapo_lookup() with local_bh_disable/enable() (Florian Westphal)
- drop rcu_read_lock/unlock() from nft_pipapo_lookup(), it's already implied (Florian Westphal)
- explain why partial allocation failures don't need handling in pipapo_realloc_scratch(), rename 'm' to clone and update related kerneldoc to make it clear we're not operating on the live copy (Florian Westphal)
- add expicit check for priv->start_elem in nft_pipapo_insert() to avoid ending up in nft_pipapo_walk() with a NULL start element, and also zero it out in every operation that might make it invalid, so that insertion doesn't proceed with an invalid element (Florian Westphal)

---
 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         | 2102 ++++++++++++++++++++++++
 4 files changed, 2107 insertions(+), 1 deletion(-)
 create mode 100644 net/netfilter/nft_set_pipapo.c
include/net/netfilter/nf_tables_core.h +1 -0
index 2656155b4069..29e7e1021267 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 +2102 -0

2,102 lines not on this page · raw message

Signature · 1 line
2.24.1
#6 lore raw

Re: [PATCH nf-next v4 5/9] nf_tables: Add set type for arbitrary concatenation of ranges

Hi Stefano,

A bit of late feedback on your new datastructure.

Did you tests with 8-bits grouping instead of 4-bits?

Assuming a concatenation of 12 bytes (each field 4 bytes, hence 3 fields):

* Using 4-bits groups: the number of buckets is 2^4 = 16 multiplied by the bucket word (assuming one long word, 8 bytes, 64 pipapo rules) is 16 * 8 = 128 bytes per group-row in the looking table. Then, the number of group-rows is 8 given that 32 bits, then 32 / 4 = 8 group-rows.

8 * 128 bytes = 1024 bytes per lookup table.

Assuming 3 fields, then this is 1024 * 3 = 3072 bytes.

* Using 8-bits groups: 2^8 = 256, then 256 * 8 = 2048 bytes per group-row. Then, 32 / 8 = 4 group-rows in total.

4 * 2048 bytes = 8192 bytes per lookup table.

Therefore, 3 * 8192 = 24576 bytes. Still rather small.

This is missing the mapping table that links the lookup tables in the memory counting. And I'm assuming that the number of pipapo rules in the lookup table fits into 64-bits bucket long word.

Anyway, my understanding is that the more bits you use for grouping, the larger the lookup table becomes.

Still, both look very small in terms of memory consumption for these days.

I'm just telling this because the C implementation can probably get better numbers at the cost of consuming more memory? Probably do this at some point?

BTW, with a few more knobs it should be possible to integrate better this datastructure into the transaction infrastructure, this can be done incrementally.

More questions below.

On Wed, Jan 22, 2020 at 12:17:55AM +0100, Stefano Brivio wrote:
[...]

Quoted 5 lines
net/netfilter/nft_set_pipapo.c new file +0 -0
new file mode 100644
index 000000000000..f0cb1e13af50

[...]

Quoted 20 lines

+ *

+ *       rule indices in current field: 0    1    2
+ *       map to rules in next field:    0    1    1

+ *
+ * the new result bitmap will be 0x02: rule 1 was set, and rule 1 will be
+ * set.
+ *

+ *      We can now extend this example to cover the second iteration of the step
+ *      above (lookup and AND bitmap): assuming the port field is
+ *      2048 < 0  0  5  0 >, with starting result bitmap 0x2, and lookup table
+ *      for "port" field from pre-computation example:

+ *
+ * ::
+ *
+ * bucket
+ * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

+ *        0   0,1
+ *        1   0,1
+ *        2                    0   1
+ *        3   0,1
Quoted 14 lines

+ *
+ * operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5]
+ * & 0x3 [bucket 0], resulting bitmap is 0x2.
+ *
+ * - if this is the last field in the set, look up the value from the mapping
+ * array corresponding to the final result bitmap
+ *
+ * Example: 0x2 resulting bitmap from 192.168.1.5:2048, mapping array for
+ * last field from insertion example:
+ *
+ * ::
+ *
+ * rule indices in last field: 0 1
+ * map to elements: 0x42 0x66

Should this be instead?

rule indices in last field: 0 1
map to elements: 0x66 0x42

If the resulting bitmap is 0x2, then this is actually pointing to rule index 1 in this lookup table, that is the 2048.

Quoted 1 line

+ * the matching element is at 0x42.

Hence, the matching 0x42 element.

Otherwise, I don't understand how to interpret the "result bitmap". I thought this contains the matching pipapo rule index that is expressed as a bitmask.

[...]

Quoted 10 lines
net/netfilter/nft_set_pipapo.c new file +10 -0
+static 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;
+
+	for (k = 0; k < len; k++) {
+		bitset = map[k];
+		while (bitset) {

net/netfilter/nft_set_pipapo.c line 506

Quoted 10 lines
net/netfilter/nft_set_pipapo.c new file +10 -0
+			unsigned long t = bitset & -bitset;
+			int r = __builtin_ctzl(bitset);
+			int i = k * BITS_PER_LONG + r;
+
+			if (unlikely(i >= rules)) {
+				map[k] = 0;
+				return -1;
+			}
+
+			if (unlikely(match_only)) {

Not a big issue, but this branch holds true for the last field, my understanding for unlikely() is that it should be used for paths where 99.99...% is not going to happen. Not a big issue, just that when reading the code I got confused this is actually likely to happen.

Quoted 15 lines
net/netfilter/nft_set_pipapo.c new file +15 -0
+				bitmap_clear(map, i, 1);
+				return i;
+			}
+
+			ret = 0;
+
+			bitmap_set(dst, mt[i].to, mt[i].n);
+
+			bitset ^= t;
+		}
+		map[k] = 0;
+	}
+
+	return ret;
+}> 
#7 lore raw

Re: [PATCH nf-next v4 5/9] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 5 lines · On Fri, 7 Feb 2020 12:23:08 +0100 Pablo Neira Ayuso <[email protected]> wrote:

Hi Stefano,

A bit of late feedback on your new datastructure.

Did you tests with 8-bits grouping instead of 4-bits?

Yes, at the very beginning, not with the final implementation. It was somewhat faster (on x86_64, I don't remember how much) for small numbers of rules, then I thought we would use too much memory, because:

Quoted 16 lines

Assuming a concatenation of 12 bytes (each field 4 bytes, hence 3 fields):

* Using 4-bits groups: the number of buckets is 2^4 = 16 multiplied by the bucket word (assuming one long word, 8 bytes, 64 pipapo rules) is 16 * 8 = 128 bytes per group-row in the looking table. Then, the number of group-rows is 8 given that 32 bits, then 32 / 4 = 8 group-rows.

8 * 128 bytes = 1024 bytes per lookup table.

Assuming 3 fields, then this is 1024 * 3 = 3072 bytes.

* Using 8-bits groups: 2^8 = 256, then 256 * 8 = 2048 bytes per group-row. Then, 32 / 8 = 4 group-rows in total.

Quoted 7 lines

4 * 2048 bytes = 8192 bytes per lookup table.

Therefore, 3 * 8192 = 24576 bytes. Still rather small.

This is missing the mapping table that links the lookup tables in the memory counting. And I'm assuming that the number of pipapo rules in the lookup table fits into 64-bits bucket long word.

...the (reasonable?) worst case I wanted to cover was two IPv6 addresses, one port, one MAC address (in ipset terms "net,net,port,mac"), with 2 ^ 16 unique, non-overlapping entries each (or ranges expanding to that amount of rules), because that's what (single, non-concatenated) ipset "bitmap" types can do.

Also ignoring the mapping table (it's "small"), with 4-bit buckets:

- for the IPv6 addresses, we have 16 buckets, each 2 ^ 16 bits wide, and 32 groups (128 bits / 4 bits), that is, 8MiB in total

- for the MAC address, 16 buckets, each 2 ^ 16 bits wide, and 12 groups, 1.5MiB

- for the port, 16 buckets, each 2 ^ 12 bits wide, 2 groups, 0.25MiB

that is, 9.75MiB.

With 8-bit buckets: we can just multiply everything by 8 (that is, 2 ^ 8 / 2 ^ 4 / 2, because we have 2 ^ (8 - 4) times the buckets, with half the groups), 78MiB.

And that started feeling like "a lot". However, I'm probably overdoing with the worst case -- this was just to explain what brought me to the 4-bit choice, now I start doubting about it.

Quoted 9 lines

Anyway, my understanding is that the more bits you use for grouping, the larger the lookup table becomes.

Still, both look very small in terms of memory consumption for these days.

I'm just telling this because the C implementation can probably get better numbers at the cost of consuming more memory? Probably do this at some point?

Another topic is the additional amount of cachelines we would use. I don't expect that effect to be visible, but I might be wrong.

So yes, I think it's definitely worth a try, thanks for the hint! I'll try to look into this soon and test it on a few archs (something with small cachelines, say MIPS r2k, would be worth checking, too).

We could even consider to dynamically adjust group size depending on the set size, I don't know yet if that gets too convoluted.

Quoted 49 lines

BTW, with a few more knobs it should be possible to integrate better this datastructure into the transaction infrastructure, this can be done incrementally.

More questions below.

On Wed, Jan 22, 2020 at 12:17:55AM +0100, Stefano Brivio wrote:
[...]

Quoted 5 lines
net/netfilter/nft_set_pipapo.c new file +0 -0
new file mode 100644
index 000000000000..f0cb1e13af50

[...]

Quoted 20 lines

+ *

+ *       rule indices in current field: 0    1    2
+ *       map to rules in next field:    0    1    1

+ *
+ * the new result bitmap will be 0x02: rule 1 was set, and rule 1 will be
+ * set.
+ *

+ *      We can now extend this example to cover the second iteration of the step
+ *      above (lookup and AND bitmap): assuming the port field is
+ *      2048 < 0  0  5  0 >, with starting result bitmap 0x2, and lookup table
+ *      for "port" field from pre-computation example:

+ *
+ * ::
+ *
+ * bucket
+ * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

+ *        0   0,1
+ *        1   0,1
+ *        2                    0   1
+ *        3   0,1
Quoted 14 lines

+ *
+ * operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5]
+ * & 0x3 [bucket 0], resulting bitmap is 0x2.
+ *
+ * - if this is the last field in the set, look up the value from the mapping
+ * array corresponding to the final result bitmap
+ *
+ * Example: 0x2 resulting bitmap from 192.168.1.5:2048, mapping array for
+ * last field from insertion example:
+ *
+ * ::
+ *
+ * rule indices in last field: 0 1
+ * map to elements: 0x42 0x66

Quoted 7 lines

Should this be instead?

rule indices in last field: 0 1
map to elements: 0x66 0x42

If the resulting bitmap is 0x2, then this is actually pointing to rule index 1 in this lookup table, that is the 2048.

Right! Good catch, thanks.

I swapped the values also in the "insertion" example above. For some reason, this was correct in the equivalent example of the stand-alone implementation:
https://pipapo.lameexcu.se/pipapo/tree/pipapo.c#n162

Quoted 7 lines
Quoted 1 line

+ * the matching element is at 0x42.

Hence, the matching 0x42 element.

Otherwise, I don't understand how to interpret the "result bitmap". I thought this contains the matching pipapo rule index that is expressed as a bitmask.

Yes, that's correct. Let me know if you want me to send a patch or if you'd rather fix it.

Quoted 18 lines

[...]

Quoted 17 lines
net/netfilter/nft_set_pipapo.c new file +17 -0
+static 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;
+
+	for (k = 0; k < len; k++) {
+		bitset = map[k];
+		while (bitset) {
+			unsigned long t = bitset & -bitset;
+			int r = __builtin_ctzl(bitset);
+			int i = k * BITS_PER_LONG + r;
+
+			if (unlikely(i >= rules)) {
+				map[k] = 0;
+				return -1;
Quoted 8 lines

net/netfilter/nft_set_pipapo.c line 506

Quoted 3 lines
net/netfilter/nft_set_pipapo.c new file +3 -0
+			}
+
+			if (unlikely(match_only)) {  

Not a big issue, but this branch holds true for the last field, my understanding for unlikely() is that it should be used for paths where 99.99...% is not going to happen. Not a big issue, just that when reading the code I got confused this is actually likely to happen.

You're right, I wanted to make sure we avoid branching for the "common" case (this early return happens just once), but this is probably an abuse. I'll look into a more acceptable way to achieve this.

Quoted 15 lines
Quoted 15 lines
net/netfilter/nft_set_pipapo.c new file +15 -0
+				bitmap_clear(map, i, 1);
+				return i;
+			}
+
+			ret = 0;
+
+			bitmap_set(dst, mt[i].to, mt[i].n);
+
+			bitset ^= t;
+		}
+		map[k] = 0;
+	}
+
+	return ret;  
+}>   
Signature · 1 line
Stefano
#8 lore raw

Re: [PATCH nf-next v4 5/9] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 2 lines · Stefano Brivio

On Fri, 7 Feb 2020 12:23:08 +0100
Pablo Neira Ayuso <[email protected]> wrote:

[...]

Quoted 30 lines
Quoted 1 line

Did you tests with 8-bits grouping instead of 4-bits?

Yes, at the very beginning, not with the final implementation. It was somewhat faster (on x86_64, I don't remember how much) for small numbers of rules, then I thought we would use too much memory, because:

Quoted 16 lines

Assuming a concatenation of 12 bytes (each field 4 bytes, hence 3 fields):

* Using 4-bits groups: the number of buckets is 2^4 = 16 multiplied by the bucket word (assuming one long word, 8 bytes, 64 pipapo rules) is 16 * 8 = 128 bytes per group-row in the looking table. Then, the number of group-rows is 8 given that 32 bits, then 32 / 4 = 8 group-rows.

8 * 128 bytes = 1024 bytes per lookup table.

Assuming 3 fields, then this is 1024 * 3 = 3072 bytes.

* Using 8-bits groups: 2^8 = 256, then 256 * 8 = 2048 bytes per group-row. Then, 32 / 8 = 4 group-rows in total.

Quoted 7 lines

4 * 2048 bytes = 8192 bytes per lookup table.

Therefore, 3 * 8192 = 24576 bytes. Still rather small.

This is missing the mapping table that links the lookup tables in the memory counting. And I'm assuming that the number of pipapo rules in the lookup table fits into 64-bits bucket long word.

Quoted 5 lines

...the (reasonable?) worst case I wanted to cover was two IPv6 addresses, one port, one MAC address (in ipset terms "net,net,port,mac"), with 2 ^ 16 unique, non-overlapping entries each (or ranges expanding to that amount of rules), because that's what (single, non-concatenated) ipset "bitmap" types can do.

I see, so you were considering the worst case. You're assuming each element takes exactly one pipapo rule, so it's 2^16 elements, correct?

You refer to a property that says that you can split a range into a 2*n netmasks IIRC. Do you know what is the worst case when splitting ranges?

There is no ipset set like this, but I agree usecase might happen.

Quoted 9 lines

Also ignoring the mapping table (it's "small"), with 4-bit buckets:

- for the IPv6 addresses, we have 16 buckets, each 2 ^ 16 bits wide, and 32 groups (128 bits / 4 bits), that is, 8MiB in total

- for the MAC address, 16 buckets, each 2 ^ 16 bits wide, and 12 groups, 1.5MiB

Quoted 7 lines

- for the port, 16 buckets, each 2 ^ 12 bits wide, 2 groups, 0.25MiB

that is, 9.75MiB.

With 8-bit buckets: we can just multiply everything by 8 (that is, 2 ^ 8 / 2 ^ 4 / 2, because we have 2 ^ (8 - 4) times the buckets, with half the groups), 78MiB.

Yes, this is large. Compared to a hashtable with 2^16 entries, then it's 2^17 hashtable buckets and using struct hlist_head, this is 2 MBytes. Then, each hlist_node is 16 bytes, so 2^16 * 16 ~= 1 MByte. That is 3 MBytes if my maths are fine.

Just telling this to find what could be considered as reasonable amount of memory to be consumed. ~10 MBytes is slightly more than, but I agree you selected a reasonable worst through this "complex tuple".

Quoted 17 lines

And that started feeling like "a lot". However, I'm probably overdoing with the worst case -- this was just to explain what brought me to the 4-bit choice, now I start doubting about it.

Quoted 9 lines

Anyway, my understanding is that the more bits you use for grouping, the larger the lookup table becomes.

Still, both look very small in terms of memory consumption for these days.

I'm just telling this because the C implementation can probably get better numbers at the cost of consuming more memory? Probably do this at some point?

Another topic is the additional amount of cachelines we would use. I don't expect that effect to be visible, but I might be wrong.

Quoted 6 lines

So yes, I think it's definitely worth a try, thanks for the hint! I'll try to look into this soon and test it on a few archs (something with small cachelines, say MIPS r2k, would be worth checking, too).

We could even consider to dynamically adjust group size depending on the set size, I don't know yet if that gets too convoluted.

Yes, keeping this maintainable is a good idea.

The per-cpu scratch index is only required if we cannot fit in the "result bitmap" into the stack, right?

Probably up to 256 bytes result bitmap in the stack is reasonable? That makes 8192 pipapo rules. There will be no need to disable bh and make use of the percpu scratchpad area in that case.

If adjusting the code to deal with variable length "pipapo word" size is not too convoluted, then you could just deal with the variable word size from the insert / delete / get (slow) path and register one lookup function for the version that is optimized for this pipapo word size.

Probably adding helper function to deal with pipapo words would help to prepare for such update in the future. There is the ->estimate function that allows to calculate for the best word size depending on all the information this gets from the set definition.

Just to keep this in the radar for future work.

Thanks.

#9 lore raw

Re: [PATCH nf-next v4 5/9] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 34 lines · On Fri, 14 Feb 2020 19:16:34 +0100 Pablo Neira Ayuso <[email protected]>…
Quoted 2 lines · Stefano Brivio

On Fri, 7 Feb 2020 12:23:08 +0100
Pablo Neira Ayuso <[email protected]> wrote:

[...]

Quoted 30 lines
Quoted 1 line

Did you tests with 8-bits grouping instead of 4-bits?

Yes, at the very beginning, not with the final implementation. It was somewhat faster (on x86_64, I don't remember how much) for small numbers of rules, then I thought we would use too much memory, because:

Quoted 23 lines

Assuming a concatenation of 12 bytes (each field 4 bytes, hence 3 fields):

* Using 4-bits groups: the number of buckets is 2^4 = 16 multiplied by the bucket word (assuming one long word, 8 bytes, 64 pipapo rules) is 16 * 8 = 128 bytes per group-row in the looking table. Then, the number of group-rows is 8 given that 32 bits, then 32 / 4 = 8 group-rows.

8 * 128 bytes = 1024 bytes per lookup table.

Assuming 3 fields, then this is 1024 * 3 = 3072 bytes.

* Using 8-bits groups: 2^8 = 256, then 256 * 8 = 2048 bytes per group-row. Then, 32 / 8 = 4 group-rows in total.

4 * 2048 bytes = 8192 bytes per lookup table.

Therefore, 3 * 8192 = 24576 bytes. Still rather small.

This is missing the mapping table that links the lookup tables in the memory counting. And I'm assuming that the number of pipapo rules in the lookup table fits into 64-bits bucket long word.

Quoted 8 lines
Quoted 5 lines

...the (reasonable?) worst case I wanted to cover was two IPv6 addresses, one port, one MAC address (in ipset terms "net,net,port,mac"), with 2 ^ 16 unique, non-overlapping entries each (or ranges expanding to that amount of rules), because that's what (single, non-concatenated) ipset "bitmap" types can do.

I see, so you were considering the worst case. You're assuming each element takes exactly one pipapo rule, so it's 2^16 elements, correct?

Yes, right: the ranges I considered would be disjoint and of size one (single, non-overlapping addresses). I start thinking my worst case is nowhere close to being reasonable, actually. :)

Quoted 3 lines

You refer to a property that says that you can split a range into a 2*n netmasks IIRC. Do you know what is the worst case when splitting ranges?

I'm not sure I got your question: that is exactly the worst case, i.e. we can have _up to_ 2 * n netmasks (hence rules) given a range of n bits. There's an additional upper bound on this, given by the address space, but single fields in a concatenation can overlap.

For example, we can have up to 128 rules for an IPv6 range where at least 64 bits differ between the endpoints, and which would contain 2 ^ 64 addresses. Or, say, the IPv4 range 1.2.3.4 - 255.255.0.2 is expressed by 42 rules.

By the way, 0.0.0.1 - 255.255.255.254 takes 62 rules, so we can *probably* say it's 2 * n - 2, but I don't have a formal proof for that.

I have a couple of ways in mind to get that down to n / 2, but it's not straightforward and it will take me some time (assuming it makes sense). For the n bound, we can introduce negations (proof in literature), and I have some kind of ugly prototype. For the n / 2 bound, I'd need some auxiliary data structure to keep insertion invertible.

In practice, the "average" case is much less, but to define it we would first need to agree on what are the actual components of the multivariate distribution... size and start? Is it a Poisson distribution then? After spending some time on this and disagreeing with myself I'd shyly recommend to skip the topic. :)

Quoted 1 line

There is no ipset set like this, but I agree usecase might happen.

Actually, for ipset, a "net,port,net,port" type was proposed (netfilter-devel <[email protected]>), but when József enquired about the intended use case, none was given. So maybe this whole "net,net,port,mac" story makes even less sense.

Quoted 13 lines
Quoted 13 lines

Also ignoring the mapping table (it's "small"), with 4-bit buckets:

- for the IPv6 addresses, we have 16 buckets, each 2 ^ 16 bits wide, and 32 groups (128 bits / 4 bits), that is, 8MiB in total

- for the MAC address, 16 buckets, each 2 ^ 16 bits wide, and 12 groups, 1.5MiB

- for the port, 16 buckets, each 2 ^ 12 bits wide, 2 groups, 0.25MiB

that is, 9.75MiB.

Quoted 8 lines
Quoted 3 lines

With 8-bit buckets: we can just multiply everything by 8 (that is, 2 ^ 8 / 2 ^ 4 / 2, because we have 2 ^ (8 - 4) times the buckets, with half the groups), 78MiB.

Yes, this is large. Compared to a hashtable with 2^16 entries, then it's 2^17 hashtable buckets and using struct hlist_head, this is 2 MBytes. Then, each hlist_node is 16 bytes, so 2^16 * 16 ~= 1 MByte. That is 3 MBytes if my maths are fine.

Sounds correct to me as well.

Quoted 25 lines

Just telling this to find what could be considered as reasonable amount of memory to be consumed. ~10 MBytes is slightly more than, but I agree you selected a reasonable worst through this "complex tuple".

Quoted 21 lines

And that started feeling like "a lot". However, I'm probably overdoing with the worst case -- this was just to explain what brought me to the 4-bit choice, now I start doubting about it.

Quoted 9 lines

Anyway, my understanding is that the more bits you use for grouping, the larger the lookup table becomes.

Still, both look very small in terms of memory consumption for these days.

I'm just telling this because the C implementation can probably get better numbers at the cost of consuming more memory? Probably do this at some point?

Another topic is the additional amount of cachelines we would use. I don't expect that effect to be visible, but I might be wrong.

So yes, I think it's definitely worth a try, thanks for the hint! I'll try to look into this soon and test it on a few archs (something with small cachelines, say MIPS r2k, would be worth checking, too).

Quoted 7 lines
Quoted 2 lines

We could even consider to dynamically adjust group size depending on the set size, I don't know yet if that gets too convoluted.

Yes, keeping this maintainable is a good idea.

The per-cpu scratch index is only required if we cannot fit in the "result bitmap" into the stack, right?

Right.

Quoted 3 lines

Probably up to 256 bytes result bitmap in the stack is reasonable? That makes 8192 pipapo rules. There will be no need to disable bh and make use of the percpu scratchpad area in that case.

Right -- the question is whether that would mean yet another implementation for the lookup function.

Quoted 5 lines

If adjusting the code to deal with variable length "pipapo word" size is not too convoluted, then you could just deal with the variable word size from the insert / delete / get (slow) path and register one lookup function for the version that is optimized for this pipapo word size.

Yes, I like this a lot -- we would also need one function to rebuild tables when the word size changes, but that sounds almost trivial. Changes for the slow path are actually rather simple.

Still, I start doubting quite heavily that my original worst case is reasonable. If we stick to the one you mentioned, or even something in between, it makes no sense to keep 4-bit buckets.

By the way, I went ahead and tried the 8-bit bucket version of the C implementation only, on my usual x86_64 box (one thread, AMD Epyc 7351). I think it's worth it:

4-bit 8-bit
net,port
1000 entries 2304165pps 2901299pps
port,net
100 entries 4131471pps 4751247pps
net6,port
1000 entries 1092557pps 1651037pps
port,proto
30000 entries 284147pps 449665pps
net6,port,mac
10 entries 2082880pps 2762291pps
net6,port,mac,proto
1000 entries 783810pps 1195823pps
net,mac
1000 entries 1279122pps 1934003pps

I would now proceed extending this to the AVX2 implementation and (once I finish it) to the NEON one, I actually expect bigger gains there.

Quoted 4 lines

Probably adding helper function to deal with pipapo words would help to prepare for such update in the future. There is the ->estimate function that allows to calculate for the best word size depending on all the information this gets from the set definition.

Hm, I really think it should be kind of painless to make this dynamic on insertion/deletion.

Signature · 1 line
Stefano
#10 lore raw

Re: [PATCH nf-next v4 5/9] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 2 lines · Stefano Brivio

On Fri, 14 Feb 2020 19:16:34 +0100
Pablo Neira Ayuso <[email protected]> wrote:

[...]

Quoted 9 lines
Quoted 3 lines

You refer to a property that says that you can split a range into a 2*n netmasks IIRC. Do you know what is the worst case when splitting ranges?

I'm not sure I got your question: that is exactly the worst case, i.e. we can have _up to_ 2 * n netmasks (hence rules) given a range of n bits. There's an additional upper bound on this, given by the address space, but single fields in a concatenation can overlap.

Quoted 7 lines

For example, we can have up to 128 rules for an IPv6 range where at least 64 bits differ between the endpoints, and which would contain 2 ^ 64 addresses. Or, say, the IPv4 range 1.2.3.4 - 255.255.0.2 is expressed by 42 rules.

By the way, 0.0.0.1 - 255.255.255.254 takes 62 rules, so we can *probably* say it's 2 * n - 2, but I don't have a formal proof for that.

By "splitting" I was actually refering to "expanding", so you're replying here to my worst-case range-to-rules expansion question.

Quoted 6 lines

I have a couple of ways in mind to get that down to n / 2, but it's not straightforward and it will take me some time (assuming it makes sense). For the n bound, we can introduce negations (proof in literature), and I have some kind of ugly prototype. For the n / 2 bound, I'd need some auxiliary data structure to keep insertion invertible.

OK, so there is room to improve the "rule expansion" logic. I didn't spend much time on that front yet.

Quoted 5 lines

In practice, the "average" case is much less, but to define it we would first need to agree on what are the actual components of the multivariate distribution... size and start? Is it a Poisson distribution then? After spending some time on this and disagreeing with myself I'd shyly recommend to skip the topic. :)

Yes, I agree to stick to something relatively simple and good is just fine.

Quoted 6 lines
Quoted 1 line

There is no ipset set like this, but I agree usecase might happen.

Actually, for ipset, a "net,port,net,port" type was proposed (netfilter-devel <[email protected]>), but when József enquired about the intended use case, none was given. So maybe this whole "net,net,port,mac" story makes even less sense.

Would it make sense to you to restrict pipapo to 3 fields until there is someone with a usecase for this?

[...]

Quoted 11 lines
Quoted 2 lines

The per-cpu scratch index is only required if we cannot fit in the "result bitmap" into the stack, right?

Right.

Quoted 3 lines

Probably up to 256 bytes result bitmap in the stack is reasonable? That makes 8192 pipapo rules. There will be no need to disable bh and make use of the percpu scratchpad area in that case.

Right -- the question is whether that would mean yet another implementation for the lookup function.

This would need another lookup function that can be selected from control plane path. The set size and the range-to-rule expansion worst-case can tell us if it would fit into the stack. It's would be just one extra lookup function for this case, ~80-100 LOC.

Quoted 6 lines
Quoted 5 lines

If adjusting the code to deal with variable length "pipapo word" size is not too convoluted, then you could just deal with the variable word size from the insert / delete / get (slow) path and register one lookup function for the version that is optimized for this pipapo word size.

Quoted 7 lines

Yes, I like this a lot -- we would also need one function to rebuild tables when the word size changes, but that sounds almost trivial. Changes for the slow path are actually rather simple.

Still, I start doubting quite heavily that my original worst case is reasonable. If we stick to the one you mentioned, or even something in between, it makes no sense to keep 4-bit buckets.

OK, then moving to 8-bits will probably remove a bit of code which is dealing with "nibbles".

Quoted 4 lines

By the way, I went ahead and tried the 8-bit bucket version of the C implementation only, on my usual x86_64 box (one thread, AMD Epyc 7351). I think it's worth it:

Quoted 15 lines

4-bit 8-bit
net,port
1000 entries 2304165pps 2901299pps
port,net
100 entries 4131471pps 4751247pps
net6,port
1000 entries 1092557pps 1651037pps
port,proto
30000 entries 284147pps 449665pps
net6,port,mac
10 entries 2082880pps 2762291pps
net6,port,mac,proto
1000 entries 783810pps 1195823pps
net,mac
1000 entries 1279122pps 1934003pps

Assuming the same concatenation type, larger bucket size makes pps drop in the C implementation?

Quoted 2 lines

I would now proceed extending this to the AVX2 implementation and (once I finish it) to the NEON one, I actually expect bigger gains there.

Good. BTW, probably you can add a new NFT_SET_CLASS_JIT class that comes becomes NFT_SET_CLASS_O_1 to make the set routine that selects the set pick the jit version instead.

Quoted 7 lines
Quoted 4 lines

Probably adding helper function to deal with pipapo words would help to prepare for such update in the future. There is the ->estimate function that allows to calculate for the best word size depending on all the information this gets from the set definition.

Hm, I really think it should be kind of painless to make this dynamic on insertion/deletion.

OK, good. How would you like to proceed?

Thanks!

#11 lore raw

Re: [PATCH nf-next v4 5/9] nf_tables: Add set type for arbitrary concatenation of ranges

Quoted 31 lines · On Fri, 14 Feb 2020 21:42:25 +0100 Pablo Neira Ayuso <[email protected]>…
Quoted 2 lines · Stefano Brivio

On Fri, 14 Feb 2020 19:16:34 +0100
Pablo Neira Ayuso <[email protected]> wrote:

[...]

Quoted 9 lines
Quoted 3 lines

You refer to a property that says that you can split a range into a 2*n netmasks IIRC. Do you know what is the worst case when splitting ranges?

I'm not sure I got your question: that is exactly the worst case, i.e. we can have _up to_ 2 * n netmasks (hence rules) given a range of n bits. There's an additional upper bound on this, given by the address space, but single fields in a concatenation can overlap.

Quoted 7 lines

For example, we can have up to 128 rules for an IPv6 range where at least 64 bits differ between the endpoints, and which would contain 2 ^ 64 addresses. Or, say, the IPv4 range 1.2.3.4 - 255.255.0.2 is expressed by 42 rules.

By the way, 0.0.0.1 - 255.255.255.254 takes 62 rules, so we can *probably* say it's 2 * n - 2, but I don't have a formal proof for that.

By "splitting" I was actually refering to "expanding", so you're replying here to my worst-case range-to-rules expansion question.

Quoted 6 lines

I have a couple of ways in mind to get that down to n / 2, but it's not straightforward and it will take me some time (assuming it makes sense). For the n bound, we can introduce negations (proof in literature), and I have some kind of ugly prototype. For the n / 2 bound, I'd need some auxiliary data structure to keep insertion invertible.

Quoted 2 lines

OK, so there is room to improve the "rule expansion" logic. I didn't spend much time on that front yet.

I wrote some (barely understandable if at all) notes here:
https://pipapo.lameexcu.se/pipapo/tree/pipapo.c#n271

but I can't guarantee at this stage that it can all be implemented, or not necessarily in that way. Should you ever (try to) read it, take it as a rough, buggy draft.

Quoted 11 lines
Quoted 5 lines

In practice, the "average" case is much less, but to define it we would first need to agree on what are the actual components of the multivariate distribution... size and start? Is it a Poisson distribution then? After spending some time on this and disagreeing with myself I'd shyly recommend to skip the topic. :)

Yes, I agree to stick to something relatively simple and good is just fine.

Quoted 2 lines
Quoted 1 line

There is no ipset set like this, but I agree usecase might happen.

Quoted 7 lines
Quoted 4 lines

Actually, for ipset, a "net,port,net,port" type was proposed (netfilter-devel <[email protected]>), but when József enquired about the intended use case, none was given. So maybe this whole "net,net,port,mac" story makes even less sense.

Would it make sense to you to restrict pipapo to 3 fields until there is someone with a usecase for this?

I wouldn't. I'd rather implement the dynamic switch of bucket size if this is the alternative. I think the current version is rather generic, doesn't use too much memory, and is also reasonably tested, so I don't feel like taking working functionality away.

Quoted 10 lines

[...]

Quoted 9 lines
Quoted 2 lines

The per-cpu scratch index is only required if we cannot fit in the "result bitmap" into the stack, right?

Right.

Quoted 3 lines

Probably up to 256 bytes result bitmap in the stack is reasonable? That makes 8192 pipapo rules. There will be no need to disable bh and make use of the percpu scratchpad area in that case.

Quoted 7 lines
Quoted 2 lines

Right -- the question is whether that would mean yet another implementation for the lookup function.

This would need another lookup function that can be selected from control plane path. The set size and the range-to-rule expansion worst-case can tell us if it would fit into the stack. It's would be just one extra lookup function for this case, ~80-100 LOC.

Ah, you're right, it's not much. On the other hand, advantages seems to be:

- dropping the local_bh_{disable,enable}() pair: I can't find numbers right now, but the difference in pps between v2 (when Florian pointed out it was needed) and v1 wasn't statistically relevant

- avoiding the access to per-cpu allocated areas, here I have before/after numbers just for net,mac with 1000 entries on the AVX2 implementation (AMD 7351, one thread), it didn't look significant, 3.99Mpps instead of 3.90Mpps. Maybe it would make a difference when tested on more threads though (as a reference, same CPU, 10 threads, as of v2: 38.02Mpps) or with smaller L2

- memory usage (and how that affects locality on some archs), but if we do this for cases with small numbers of entries, it's probably not a big difference either

Anyway, I guess it's worth a try -- I'll try to find some time for it.

Quoted 10 lines
Quoted 10 lines
Quoted 5 lines

If adjusting the code to deal with variable length "pipapo word" size is not too convoluted, then you could just deal with the variable word size from the insert / delete / get (slow) path and register one lookup function for the version that is optimized for this pipapo word size.

Yes, I like this a lot -- we would also need one function to rebuild tables when the word size changes, but that sounds almost trivial. Changes for the slow path are actually rather simple.

Quoted 6 lines
Quoted 3 lines

Still, I start doubting quite heavily that my original worst case is reasonable. If we stick to the one you mentioned, or even something in between, it makes no sense to keep 4-bit buckets.

OK, then moving to 8-bits will probably remove a bit of code which is dealing with "nibbles".

Right now I have:

	 1 file changed, 16 insertions(+), 37 deletions(-)

but okay, I'll give the dynamic switch a try, first.

Quoted 20 lines
Quoted 4 lines

By the way, I went ahead and tried the 8-bit bucket version of the C implementation only, on my usual x86_64 box (one thread, AMD Epyc 7351). I think it's worth it:

Quoted 15 lines

4-bit 8-bit
net,port
1000 entries 2304165pps 2901299pps
port,net
100 entries 4131471pps 4751247pps
net6,port
1000 entries 1092557pps 1651037pps
port,proto
30000 entries 284147pps 449665pps
net6,port,mac
10 entries 2082880pps 2762291pps
net6,port,mac,proto
1000 entries 783810pps 1195823pps
net,mac
1000 entries 1279122pps 1934003pps

Quoted 2 lines

Assuming the same concatenation type, larger bucket size makes pps drop in the C implementation?

Uh, no, they go up with larger buckets, in the figures above we have +26%, +15%, +51%, +58%, +33%, +53%, +51%.

Quoted 6 lines
Quoted 2 lines

I would now proceed extending this to the AVX2 implementation and (once I finish it) to the NEON one, I actually expect bigger gains there.

Good. BTW, probably you can add a new NFT_SET_CLASS_JIT class that comes becomes NFT_SET_CLASS_O_1 to make the set routine that selects the set pick the jit version instead.

It's not exactly JIT though :) it's hand-written assembly. It's coming up a bit nicer for NEON as I can use compiler intrinsics there.

Maybe I didn't understand your point, but I don't think this is needed. In 9/9 of v4 I simply had, in nft_pipapo_avx2_estimate():

	if (!boot_cpu_has(X86_FEATURE_AVX2) || !boot_cpu_has(X86_FEATURE_AVX))
		return false;
Quoted 9 lines
Quoted 7 lines
Quoted 4 lines

Probably adding helper function to deal with pipapo words would help to prepare for such update in the future. There is the ->estimate function that allows to calculate for the best word size depending on all the information this gets from the set definition.

Hm, I really think it should be kind of painless to make this dynamic on insertion/deletion.

OK, good. How would you like to proceed?

Let me give a shot at the dynamic bucket size switching. If that looks reasonable, I'd proceed extending that to the AVX2 implementation, finish the NEON implementation including it right away, and prepare a series. If it doesn't, I'll report back :)

Signature · 1 line
Stefano
#12 lore raw

PATCH v4 6/9 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.

---
v4: No changes
v3: No changes
v2: No changes

 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.24.1
#13 lore raw

PATCH v4 7/9 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.

---
v4: No changes
v3: No changes
v2: No changes

 net/netfilter/nft_set_pipapo.c | 115 +++++++++++++++++++++++++++------
 1 file changed, 97 insertions(+), 18 deletions(-)
net/netfilter/nft_set_pipapo.c +97 -18
index f0cb1e13af50..a9665d44e4f8 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;
@@ -668,8 +692,8 @@ static struct nft_pipapo_elem *pipapo_get(const struct net *net,
 	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
@@ -763,6 +787,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;
@@ -773,12 +801,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));
@@ -807,7 +837,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);
 	}
 
@@ -829,7 +859,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);
@@ -1053,8 +1084,12 @@ static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
 
 	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) {
 			/* On failure, there's no need to undo previous
@@ -1070,6 +1105,11 @@ static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
 		kfree(*per_cpu_ptr(clone->scratch, i));
 
 		*per_cpu_ptr(clone->scratch, i) = scratch;
+
+#ifdef NFT_PIPAPO_ALIGN
+		scratch_aligned = NFT_PIPAPO_LT_ALIGN(scratch);
+		*per_cpu_ptr(clone->scratch_aligned, i) = scratch_aligned;
+#endif
 	}
 
 	return 0;
@@ -1200,21 +1240,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);
 
@@ -1237,8 +1289,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);
@@ -1394,7 +1449,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,
@@ -1498,6 +1554,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);
@@ -1701,7 +1760,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))
@@ -1975,11 +2035,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);
 
 	nft_pipapo_for_each_field(f, i, m) {
@@ -1990,7 +2060,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;
 	}
 
@@ -2008,7 +2078,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;
@@ -2043,16 +2117,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.24.1
#14 lore raw

PATCH v4 8/9 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.

v4: No changes
v3: Fix comment for pipapo_estimate_size(), we return 0 on overflow
v2: No changes

---
 net/netfilter/nft_set_pipapo.c | 216 ++----------------------------
 net/netfilter/nft_set_pipapo.h | 237 +++++++++++++++++++++++++++++++++
 2 files changed, 248 insertions(+), 205 deletions(-)
 create mode 100644 net/netfilter/nft_set_pipapo.h
net/netfilter/nft_set_pipapo.c +11 -205
index a9665d44e4f8..e7f4cecea7d6 100644
@@ -330,167 +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
- */
-struct nft_pipapo {
-	struct nft_pipapo_match __rcu *match;
-	struct nft_pipapo_match *clone;
-	int groups;
-	int width;
-	bool dirty;
-	unsigned long last_gc;
-};
-
-struct nft_pipapo_elem;
-
-/**
- * struct nft_pipapo_elem - API-facing representation of single set element
- * @ext:	nftables API extensions
- */
-struct nft_pipapo_elem {
-	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
@@ -508,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;
@@ -583,26 +435,13 @@ 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;
 
 		/* For each 4-bit group: select lookup table bucket depending on
 		 * packet bytes value, then AND bucket value
 		 */
-		for (group = 0; group < f->groups; group += 2) {
-			u8 v;
-
-			v = *rp >> 4;
-			__bitmap_and(res_map, res_map, lt + v * f->bsize,
-				     f->bsize * BITS_PER_LONG);
-			lt += f->bsize * NFT_PIPAPO_BUCKETS;
-
-			v = *rp & 0x0f;
-			rp++;
-			__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
 		 * the last field, in which case return the matched 'ext'
@@ -1943,56 +1782,23 @@ static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
 }
 
 /**
- * nft_pipapo_estimate() - Estimate set size, space and lookup complexity
- * @desc:	Set description, element count and field description used here
+ * nft_pipapo_estimate() - Set size, space and lookup complexity
+ * @desc:	Set description, element count and field description used
  * @features:	Flags: NFT_SET_INTERVAL 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 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 only for compatible range concatenations
+ * Return: true if set description is compatible, false otherwise
  */
 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
 				struct nft_set_estimate *est)
 {
-	unsigned long entry_size;
-	int i;
-
 	if (!(features & NFT_SET_INTERVAL) || desc->field_count <= 1)
 		return false;
 
-	for (i = 0, entry_size = 0; i < desc->field_count; i++) {
-		unsigned long rules;
-
-		if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
-			return false;
-
-		/* Worst-case ranges for each concatenated field: each n-bit
-		 * field can expand to up to n * 2 rules in each bucket, and
-		 * each rule also needs a mapping bucket.
-		 */
-		rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
-		entry_size += rules * NFT_PIPAPO_BUCKETS / BITS_PER_BYTE;
-		entry_size += rules * sizeof(union nft_pipapo_map_bucket);
-	}
-
-	/* Rules in lookup and mapping tables are needed for each entry */
-	est->size = desc->size * entry_size;
-	if (est->size && div_u64(est->size, desc->size) != entry_size)
+	est->size = pipapo_estimate_size(desc);
+	if (!est->size)
 		return false;
 
-	est->size += sizeof(struct nft_pipapo) +
-		     sizeof(struct nft_pipapo_match) * 2;
-
-	est->size += sizeof(struct nft_pipapo_field) * desc->field_count;
-
 	est->lookup = NFT_SET_CLASS_O_LOG_N;
 
 	est->space = NFT_SET_CLASS_O_N;
net/netfilter/nft_set_pipapo.h new file +237 -0

237 lines not on this page · raw message

Signature · 1 line
2.24.1
#15 lore raw

PATCH v4 9/9 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 operations 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 7402 thread (3.35GHz, 768 KiB L1D$, 12 MiB L2$):
net,port [ OK ]
baseline (drop from netdev hook): 13816909pps
baseline hash (non-ranged entries): 7706821pps
baseline rbtree (match on first field only): 3719979pps
set with 1000 full, ranged entries: 5843256pps
port,net [ OK ]
baseline (drop from netdev hook): 13440355pps
baseline hash (non-ranged entries): 7755855pps
baseline rbtree (match on first field only): 5404151pps
set with 100 full, ranged entries: 6274637pps
net6,port [ OK ]
baseline (drop from netdev hook): 12695318pps
baseline hash (non-ranged entries): 5998414pps
baseline rbtree (match on first field only): 1704466pps
set with 1000 full, ranged entries: 3258636pps
port,proto [ OK ]
baseline (drop from netdev hook): 14045198pps
baseline hash (non-ranged entries): 8586447pps
baseline rbtree (match on first field only): 3811115pps
set with 30000 full, ranged entries: 2200493pps
net6,port,mac [ OK ]
baseline (drop from netdev hook): 12644024pps
baseline hash (non-ranged entries): 4834372pps
baseline rbtree (match on first field only): 3654772pps
set with 10 full, ranged entries: 3655568pps
net6,port,mac,proto [ OK ]
baseline (drop from netdev hook): 12545632pps
baseline hash (non-ranged entries): 4656663pps
baseline rbtree (match on first field only): 1713780pps
set with 1000 full, ranged entries: 2529071pps
net,mac [ OK ]
baseline (drop from netdev hook): 13766991pps
baseline hash (non-ranged entries): 6440069pps
baseline rbtree (match on first field only): 3739526pps
set with 1000 full, ranged entries: 4818210pps

- for one AMD Epyc 7351 thread (2.9GHz, 512 KiB L1D$, 8 MiB L2$):
net,port [ OK ]
baseline (drop from netdev hook): 10170346pps
baseline hash (non-ranged entries): 6214729pps
baseline rbtree (match on first field only): 2589686pps
set with 1000 full, ranged entries: 4695300pps
port,net [ OK ]
baseline (drop from netdev hook): 10162240pps
baseline hash (non-ranged entries): 6199651pps
baseline rbtree (match on first field only): 4176819pps
set with 100 full, ranged entries: 4884376pps
net6,port [ OK ]

    baseline (drop from netdev hook):               9732630pps
    baseline hash (non-ranged entries):             4747333pps
    baseline rbtree (match on first field only):    1376541pps
    set with  1000 full, ranged entries:            2486028pps
  port,proto                                                    [ OK ]
    baseline (drop from netdev hook):              10682224pps
    baseline hash (non-ranged entries):             6872565pps
    baseline rbtree (match on first field only):    2793442pps
    set with 30000 full, ranged entries:            1876571pps
  net6,port,mac                                                 [ OK ]
    baseline (drop from netdev hook):               9718917pps
    baseline hash (non-ranged entries):             3969930pps
    baseline rbtree (match on first field only):    3082588pps
    set with    10 full, ranged entries:            2988231pps
  net6,port,mac,proto                                           [ OK ]
    baseline (drop from netdev hook):               9754800pps
    baseline hash (non-ranged entries):             3810961pps
    baseline rbtree (match on first field only):    1365740pps
    set with  1000 full, ranged entries:            1967771pps

net,mac [ OK ]
baseline (drop from netdev hook): 10206690pps
baseline hash (non-ranged entries): 5237175pps
baseline rbtree (match on first field only): 2975866pps
set with 1000 full, ranged entries: 3896154pps

- for one Intel Core i7-6600U thread (3.4GHz, 64 KiB L1D$, 512 KiB L2$):
net,port [ OK ]
baseline (drop from netdev hook): 10021039pps
baseline hash (non-ranged entries): 6061766pps
baseline rbtree (match on first field only): 3304312pps
set with 1000 full, ranged entries: 4844887pps
port,net [ OK ]
baseline (drop from netdev hook): 10865207pps
baseline hash (non-ranged entries): 6435691pps
baseline rbtree (match on first field only): 4861128pps
set with 100 full, ranged entries: 5246583pps
net6,port [ OK ]
baseline (drop from netdev hook): 10173990pps
baseline hash (non-ranged entries): 4992955pps
baseline rbtree (match on first field only): 1769058pps
set with 1000 full, ranged entries: 3186628pps
port,proto [ OK ]
baseline (drop from netdev hook): 10680118pps
baseline hash (non-ranged entries): 7127671pps
baseline rbtree (match on first field only): 4001820pps
set with 30000 full, ranged entries: 2591677pps
net6,port,mac [ OK ]

    baseline (drop from netdev hook):               9932346pps
    baseline hash (non-ranged entries):             4216648pps
    baseline rbtree (match on first field only):    3414029pps
    set with    10 full, ranged entries:            3164909pps
  net6,port,mac,proto                                           [ OK ]
    baseline (drop from netdev hook):               9967056pps
    baseline hash (non-ranged entries):             4024868pps
    baseline rbtree (match on first field only):    1777420pps
    set with  1000 full, ranged entries:            2457853pps

net,mac [ OK ]
baseline (drop from netdev hook): 10702441pps
baseline hash (non-ranged entries): 5615505pps
baseline rbtree (match on first field only): 3488851pps
set with 1000 full, ranged entries: 4257577pps

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.

The vectorised implementation is automatically selected whenever the AVX2 feature is available, and this can be detected with the following check:

	[ $(uname -m) = "x86_64" ] && grep -q avx2 /proc/cpuinfo

In order to make set selection more explicit and visible, we might at a later time export a different name, by introducing a new attribute, e.g. NFTA_SET_OPS, as suggested by Phil Sutter on netfilter-devel in <[email protected]>.

v4: No changes
v3:
- update matching rate data in commit message
- skip AVX2 check in Makefile for i386
(kbuild test robot <[email protected]>)
v2:
- extend scope of kernel_fpu_begin/end() to protect all accesses to scratch maps (Florian Westphal)
- drop rcu_read_lock/unlock() from nft_pipapo_avx2_lookup(), it's already implied (Florian Westphal)
- mention in commit message how to check if this set is used

---
 include/net/netfilter/nf_tables_core.h |   1 +
 net/netfilter/Makefile                 |   5 +
 net/netfilter/nf_tables_set_core.c     |   6 +
 net/netfilter/nft_set_pipapo.c         |  25 +
 net/netfilter/nft_set_pipapo_avx2.c    | 842 +++++++++++++++++++++++++
 net/netfilter/nft_set_pipapo_avx2.h    |  14 +
 6 files changed, 893 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 29e7e1021267..549d5f9ea8c3 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 +5 -0
index 3f572e5a975e..4c1896943f6e 100644
@@ -83,6 +83,11 @@ 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
+ifeq ($(ARCH),x86_64)
+ifneq (,$(findstring -DCONFIG_AS_AVX2=1,$(KBUILD_CFLAGS)))
+nf_tables_set-objs += nft_set_pipapo_avx2.o
+endif
+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 e7f4cecea7d6..396eb434aa75 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 */
@@ -1985,3 +1986,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,
+	.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 +842 -0

842 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.24.1
#16 lore raw

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

Thank you for the patch! Yet something to improve:

Hi Stefano,

Thank you for the patch! Yet something to improve:

[auto build test ERROR on nf-next/master]
[also build test ERROR on kselftest/next]
[cannot apply to nf/master linus/master ipvs/master v5.5 next-20200124] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system. BTW, we also suggest to use '--base' option to specify the base tree in git format-patch, please see https://stackoverflow.com/a/37406982]

url:    https://github.com/0day-ci/linux/commits/Stefano-Brivio/nftables-Set-implementation-for-arbitrary-concatenation-of-ranges/20200124-112940
base:   https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git master
config: i386-randconfig-d001-20200127 (attached as .config)
compiler: gcc-7 (Debian 7.5.0-3) 7.5.0
reproduce:
        # save the attached .config to linux build tree
        make ARCH=i386 

If you fix the issue, kindly add following tag

All errors (new ones prefixed by >>):

>> ERROR: "nft_pipapo_avx2_lookup" [net/netfilter/nf_tables_set.ko] undefined!
>> ERROR: "nft_pipapo_avx2_estimate" [net/netfilter/nf_tables_set.ko] undefined!

---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org Intel Corporation

#17 lore raw
In reply to Stefano Brivio
Quoted 43 lines · Stefano Brivio

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 5/9, 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 5/9 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.

Patches 1/9 to 3/9 implement the needed infrastructure: new attributes are used to describe length of single ranged fields in concatenations and to denote the upper bound for ranges.

Quoted 7 lines

Patch 4/9 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 5/9 is the actual set implementation.

Patch 6/9 introduces selftests for the new implementation.

Applied up to 6/9.

Merge window will close soon and I'm going to be a bit defensive and take only the batch that include the initial implementation. I would prefer if we all use this round to start using the C implementation upstream and report bugs. While I have received positive feedback from other fellows meanwhile privately, this batch is large and I'm inclined to follow this approach.

Please, don't be disappointed, and just follow up with more patches once merge window opens up again.

Thanks.

reviewer
#18 lore raw
In reply to Stefano Brivio

Hi Stefano,

When playing with adding multiple elements, I suddenly noticed a disturbance in the force (general protection fault). Here's a reproducer:

| $NFT -f - <<EOF
| table t {
|         set s {
|                 type ipv4_addr . inet_service
|                 flags interval
|         }
| }
| EOF
| 
| $NFT add element t s '{ 10.0.0.1 . 22-25, 10.0.0.1 . 10-20 }'
| $NFT flush set t s
| $NFT add element t s '{ 10.0.0.1 . 10-20, 10.0.0.1 . 22-25 }'

It is pretty reliable, though sometimes needs a second call. Looks like some things going on in parallel which shouldn't. Here's a typical last breath:

[   71.319848] general protection fault, probably for non-canonical address 0x6f6b6e696c2e756e: 0000 [#1] PREEMPT SMP PTI
[   71.321540] CPU: 3 PID: 1201 Comm: kworker/3:2 Not tainted 5.6.0-rc1-00377-g2bb07f4e1d861 #192
[   71.322746] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20190711_202441-buildvm-armv7-10.arm.fedoraproject.org-2.fc31 04/01/2014
[   71.324430] Workqueue: events nf_tables_trans_destroy_work [nf_tables]
[   71.325387] RIP: 0010:nft_set_elem_destroy+0xa5/0x110 [nf_tables]
[   71.326164] Code: 89 d4 84 c0 74 0e 8b 77 44 0f b6 f8 48 01 df e8 41 ff ff ff 45 84 e4 74 36 44 0f b6 63 08 45 84 e4 74 2c 49 01 dc 49 8b 04 24 <48> 8b 40 38 48 85 c0 74 4f 48 89 e7 4c 8b
[   71.328423] RSP: 0018:ffffc9000226fd90 EFLAGS: 00010282
[   71.329225] RAX: 6f6b6e696c2e756e RBX: ffff88813ab79f60 RCX: ffff88813931b5a0
[   71.330365] RDX: 0000000000000001 RSI: 0000000000000000 RDI: ffff88813ab79f9a
[   71.331473] RBP: ffff88813ab79f60 R08: 0000000000000008 R09: 0000000000000000
[   71.332627] R10: 000000000000021c R11: 0000000000000000 R12: ffff88813ab79fc2
[   71.333615] R13: ffff88813b3adf50 R14: dead000000000100 R15: ffff88813931b8a0
[   71.334596] FS:  0000000000000000(0000) GS:ffff88813bd80000(0000) knlGS:0000000000000000
[   71.335780] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[   71.336577] CR2: 000055ac683710f0 CR3: 000000013a222003 CR4: 0000000000360ee0
[   71.337533] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[   71.338557] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
[   71.339718] Call Trace:
[   71.340093]  nft_pipapo_destroy+0x7a/0x170 [nf_tables_set]
[   71.340973]  nft_set_destroy+0x20/0x50 [nf_tables]
[   71.341879]  nf_tables_trans_destroy_work+0x246/0x260 [nf_tables]
[   71.342916]  process_one_work+0x1d5/0x3c0
[   71.343601]  worker_thread+0x4a/0x3c0
[   71.344229]  kthread+0xfb/0x130
[   71.344780]  ? process_one_work+0x3c0/0x3c0
[   71.345477]  ? kthread_park+0x90/0x90
[   71.346129]  ret_from_fork+0x35/0x40
[   71.346748] Modules linked in: nf_tables_set nf_tables nfnetlink 8021q [last unloaded: nfnetlink]
[   71.348153] ---[ end trace 2eaa8149ca759bcc ]---
[   71.349066] RIP: 0010:nft_set_elem_destroy+0xa5/0x110 [nf_tables]
[   71.350016] Code: 89 d4 84 c0 74 0e 8b 77 44 0f b6 f8 48 01 df e8 41 ff ff ff 45 84 e4 74 36 44 0f b6 63 08 45 84 e4 74 2c 49 01 dc 49 8b 04 24 <48> 8b 40 38 48 85 c0 74 4f 48 89 e7 4c 8b
[   71.350017] RSP: 0018:ffffc9000226fd90 EFLAGS: 00010282
[   71.350019] RAX: 6f6b6e696c2e756e RBX: ffff88813ab79f60 RCX: ffff88813931b5a0
[   71.350019] RDX: 0000000000000001 RSI: 0000000000000000 RDI: ffff88813ab79f9a
[   71.350020] RBP: ffff88813ab79f60 R08: 0000000000000008 R09: 0000000000000000
[   71.350021] R10: 000000000000021c R11: 0000000000000000 R12: ffff88813ab79fc2
[   71.350022] R13: ffff88813b3adf50 R14: dead000000000100 R15: ffff88813931b8a0
[   71.350025] FS:  0000000000000000(0000) GS:ffff88813bd80000(0000) knlGS:0000000000000000
[   71.350026] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[   71.350027] CR2: 000055ac683710f0 CR3: 000000013a222003 CR4: 0000000000360ee0
[   71.350028] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[   71.350028] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
[   71.350030] Kernel panic - not syncing: Fatal exception
[   71.350412] Kernel Offset: disabled
[   71.365922] ---[ end Kernel panic - not syncing: Fatal exception ]---

Cheers, Phil

#19 lore raw

Hi Phil,

Quoted 19 lines · On Thu, 20 Feb 2020 11:52:41 +0100 Phil Sutter <[email protected]> wrote:

Hi Stefano,

When playing with adding multiple elements, I suddenly noticed a disturbance in the force (general protection fault). Here's a reproducer:

| $NFT -f - <<EOF
| table t {
|         set s {
|                 type ipv4_addr . inet_service
|                 flags interval
|         }
| }
| EOF
| 
| $NFT add element t s '{ 10.0.0.1 . 22-25, 10.0.0.1 . 10-20 }'
| $NFT flush set t s
| $NFT add element t s '{ 10.0.0.1 . 10-20, 10.0.0.1 . 22-25 }'
Quoted 8 lines

It is pretty reliable, though sometimes needs a second call. Looks like some things going on in parallel which shouldn't. Here's a typical last breath:

[   71.319848] general protection fault, probably for non-canonical address 0x6f6b6e696c2e756e: 0000 [#1] PREEMPT SMP PTI
[   71.321540] CPU: 3 PID: 1201 Comm: kworker/3:2 Not tainted 5.6.0-rc1-00377-g2bb07f4e1d861 #192
[   71.322746] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20190711_202441-buildvm-armv7-10.arm.fedoraproject.org-2.fc31 04/01/2014
[   71.324430] Workqueue: events nf_tables_trans_destroy_work [nf_tables]
[   71.325387] RIP: 0010:nft_set_elem_destroy+0xa5/0x110 [nf_tables]

Ouch, thanks for reporting, I'll check in a few hours.

Signature · 1 line
Stefano