nftables: Set implementation for arbitrary concatenation of ranges
Subsystems (5)
v3 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.
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
PATCH v3 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.
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
@@ -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
PATCH v3 2/9 netfilter: nf_tables: add NFTA_SET_ELEM_KEY_END attribute
In reply to Stefano BrivioFrom: 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.
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
@@ -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
@@ -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
@@ -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, - ®s->data[priv->sreg_key], + ®s->data[priv->sreg_key],NULL , ®s->data[priv->sreg_data], timeout,0 ,GFP_ATOMIC );if (elem ==NULL )
Signature · 1 line
2.24.1
PATCH v3 3/9 netfilter: nf_tables: Support for sets with multiple ranged fields
In reply to Stefano BrivioIntroduce 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: 2v3: 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
@@ -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
@@ -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
@@ -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
PATCH v3 4/9 bitmap: Introduce bitmap_cut(): cut bits and shift remaining
In reply to Stefano BrivioThe 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.
---
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
@@ -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
PATCH v3 6/9 selftests: netfilter: Introduce tests for sets with range concatenation
In reply to Stefano BrivioThis 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.
---
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
@@ -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
PATCH v3 5/9 nf_tables: Add set type for arbitrary concatenation of ranges
In reply to Stefano BrivioThis 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
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
@@ -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
@@ -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
@@ -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
PATCH v3 7/9 nft_set_pipapo: Prepare for vectorised implementation: alignment
In reply to Stefano BrivioSIMD 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.
---
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
@@ -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
PATCH v3 8/9 nft_set_pipapo: Prepare for vectorised implementation: helpers
In reply to Stefano BrivioMove most macros and helpers to a header file, so that they can be conveniently used by related implementations.
No functional changes are intended here.
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
@@ -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 && 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
PATCH v3 9/9 nft_set_pipapo: Introduce AVX2-based lookup implementation
In reply to Stefano BrivioIf 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]>.
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
kbuild test robot
build botRe: [PATCH nf-next v3 5/9] nf_tables: Add set type for arbitrary concatenation of ranges
In reply to Stefano BrivioThank 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-rc7 next-20200117] [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/20200119-222102 base: https://git.kernel.org/pub/scm/linux/kernel/git/pablo/nf-next.git master config: m68k-multi_defconfig (attached as .config) compiler: m68k-linux-gcc (GCC) 7.5.0
reproduce:
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
GCC_VERSION=7.5.0 make.cross ARCH=m68k
If you fix the issue, kindly add following tag
All errors (new ones prefixed by >>):
>> ERROR: "__udivdi3" [net/netfilter/nf_tables_set.ko] undefined! >> ERROR: "__divdi3" [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
Re: [PATCH nf-next v3 5/9] nf_tables: Add set type for arbitrary concatenation of ranges
Quoted 4 lines · On Tue, 21 Jan 2020 00:13:17 +0800 kbuild test robot <[email protected]> wrote:
All errors (new ones prefixed by >>):
Quoted 2 lines
Quoted 2 lines
ERROR: "
__udivdi3" [net/netfilter/nf_tables_set.ko] undefined!
ERROR: "__divdi3" [net/netfilter/nf_tables_set.ko] undefined!
Right, this needs:
net/netfilter/nft_set_pipapo.c +1 -1
@@ -1925,7 +1925,7 @@ static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,/* Rules in lookup and mapping tables are needed for each entry */ est->size = desc->size * entry_size; -if (est->size && est->size / desc->size != entry_size) +if (est->size &&div_u64 (est->size, desc->size) != entry_size)return false; est->size += sizeof(struct nft_pipapo) +
I will change that in the next version.
Signature · 1 line
Stefano