Skip to contentSkip to conversation

Introduce support for concatenated ranges

PATCH Applied Stefano Brivio 4 participants 17 messages Jan 30, 2020 – Feb 10, 2020 netfilter

lore
Share & tools
lore
#0 lore raw

v4 cover Introduce support for concatenated ranges

This is the counterpart of kernel series:
nftables: Set implementation for arbitrary concatenation of ranges

Patch 1/4 updates the nf_tables.h UAPI header from the kernel, as it includes changes needed in the subsequent patches.

Patch 2/4 adds support for the NFTA_SET_DESC_CONCAT netlink
attributes: they specify the length of fields within concatenations, and they are needed by set implementations in the kernel to figure out where single fields start and stop.

Patch 3/4 introduces new key data semantics needed to represent arbitrary concatenation of ranges, as well as required changes in lexer and expression evaluation. Closing element of concatenated ranges is now expressed by a separate key, as proposed by Pablo.

Patch 4/4 adds test cases for operations on the new set type.

v4: Patch 1/4 added, no further changes
v3: Changes listed in messages for all patches
v2: Changes listed in messages for 2/3 and 3/3

Stefano Brivio (4):
include: resync nf_tables.h cache copy
src: Add support for NFTNL_SET_DESC_CONCAT
src: Add support for concatenated set ranges
tests: Introduce test for set with concatenated ranges

 include/expression.h                          |   3 +
 include/linux/netfilter/nf_tables.h           |  17 ++
 include/rule.h                                |  11 +-
 src/evaluate.c                                |  19 +-
 src/mnl.c                                     |   7 +
 src/netlink.c                                 | 120 ++++++++++---
 src/parser_bison.y                            |  17 +-
 src/rule.c                                    |  15 +-
 src/segtree.c                                 | 117 +++++++++++++
 .../testcases/sets/0042concatenated_ranges_0  | 162 ++++++++++++++++++
 10 files changed, 445 insertions(+), 43 deletions(-)
 create mode 100755 tests/shell/testcases/sets/0042concatenated_ranges_0
Signature · 1 line
2.24.1
#1 lore raw

PATCH v4 1/4 include: resync nf_tables.h cache copy

Get this header in sync with nf-next as of merge commit b3a608222336 (5.6-rc1-ish).

---
v4: New patch

 include/linux/netfilter/nf_tables.h | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
include/linux/netfilter/nf_tables.h +17 -0
index 261864736b26..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
  *
@@ -370,6 +385,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 +398,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)
Signature · 1 line
2.24.1
#3 lore raw

PATCH v4 2/4 src: Add support for NFTNL_SET_DESC_CONCAT

In reply to Stefano Brivio

To support arbitrary range concatenations, the kernel needs to know how long each field in the concatenation is. The new libnftnl NFTNL_SET_DESC_CONCAT set attribute describes this as an array of lengths, in bytes, of concatenated fields.

While evaluating concatenated expressions, export the datatype size into the new field_len array, and hand the data over via libnftnl.

Similarly, when data is passed back from libnftnl, parse it into the set description.

When set data is cloned, we now need to copy the additional fields in set_clone(), too.

This change depends on the libnftnl patch with title:
set: Add support for NFTA_SET_DESC_CONCAT attributes

v4: No changes
v3: Rework to use set description data instead of a stand-alone
attribute
v2: No changes

---
 include/expression.h |  2 ++
 include/rule.h       |  6 +++++-
 src/evaluate.c       | 14 +++++++++++---
 src/mnl.c            |  7 +++++++
 src/netlink.c        | 11 +++++++++++
 src/rule.c           |  2 +-
 6 files changed, 37 insertions(+), 5 deletions(-)
include/expression.h +2 -0
index b3e79c490b1a..6196be58c2a6 100644
@@ -261,6 +261,8 @@ struct expr {
 			struct list_head	expressions;
 			unsigned int		size;
 			uint32_t		set_flags;
+			uint8_t			field_len[NFT_REG32_COUNT];
+			uint8_t			field_count;
 		};
 		struct {
 			/* EXPR_SET_REF */
include/rule.h +5 -1
index d5b31765612e..a7f106f715cf 100644
@@ -289,7 +289,9 @@ extern struct rule *rule_lookup_by_index(const struct chain *chain,
  * @rg_cache:	cached range element (left)
  * @policy:	set mechanism policy
  * @automerge:	merge adjacents and overlapping elements, if possible
- * @desc:	set mechanism desc
+ * @desc.size:		count of set elements
+ * @desc.field_len:	length of single concatenated fields, bytes
+ * @desc.field_count:	count of concatenated fields
  */
 struct set {
 	struct list_head	list;
@@ -310,6 +312,8 @@ struct set {
 	bool			key_typeof_valid;
 	struct {
 		uint32_t	size;
+		uint8_t		field_len[NFT_REG32_COUNT];
+		uint8_t		field_count;
 	} desc;
 };
 
src/evaluate.c +11 -3
index 09dd493f0757..55591f5f3526 100644
@@ -1217,6 +1217,8 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr,
 	struct expr *i, *next;
 
 	list_for_each_entry_safe(i, next, &(*expr)->expressions, list) {
+		unsigned dsize_bytes;
+
 		if (expr_is_constant(*expr) && dtype && off == 0)
 			return expr_binary_error(ctx->msgs, i, *expr,
 						 "unexpected concat component, "
@@ -1241,6 +1243,9 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr,
 						 i->dtype->name);
 
 		ntype = concat_subtype_add(ntype, i->dtype->type);
+
+		dsize_bytes = div_round_up(i->dtype->size, BITS_PER_BYTE);
+		(*expr)->field_len[(*expr)->field_count++] = dsize_bytes;
 	}
 
 	(*expr)->flags |= flags;
@@ -3345,9 +3350,12 @@ static int set_evaluate(struct eval_ctx *ctx, struct set *set)
 			return set_key_data_error(ctx, set,
 						  set->key->dtype, type);
 	}
-	if (set->flags & NFT_SET_INTERVAL &&
-	    set->key->etype == EXPR_CONCAT)
-		return set_error(ctx, set, "concatenated types not supported in interval sets");
+
+	if (set->flags & NFT_SET_INTERVAL && set->key->etype == EXPR_CONCAT) {
+		memcpy(&set->desc.field_len, &set->key->field_len,
+		       sizeof(set->desc.field_len));
+		set->desc.field_count = set->key->field_count;
+	}
 
 	if (set_is_datamap(set->flags)) {
 		if (set->data == NULL)
src/mnl.c +7 -0
index d5bdff293c61..340380ba6fef 100644
@@ -905,6 +905,13 @@ int mnl_nft_set_add(struct netlink_ctx *ctx, const struct cmd *cmd,
 	if (set->data)
 		set_key_expression(ctx, set->data, set->flags, udbuf, NFTNL_UDATA_SET_DATA_TYPEOF);
 
+	if (set->desc.field_len[0]) {
+		nftnl_set_set_data(nls, NFTNL_SET_DESC_CONCAT,
+				   set->desc.field_len,
+				   set->desc.field_count *
+				   sizeof(set->desc.field_len[0]));
+	}
+
 	nftnl_set_set_data(nls, NFTNL_SET_USERDATA, nftnl_udata_buf_data(udbuf),
 			   nftnl_udata_buf_len(udbuf));
 	nftnl_udata_buf_free(udbuf);
src/netlink.c +11 -0
index a9ccebaf8efd..791943b4d926 100644
@@ -773,6 +773,17 @@ struct set *netlink_delinearize_set(struct netlink_ctx *ctx,
 	if (nftnl_set_is_set(nls, NFTNL_SET_DESC_SIZE))
 		set->desc.size = nftnl_set_get_u32(nls, NFTNL_SET_DESC_SIZE);
 
+	if (nftnl_set_is_set(nls, NFTNL_SET_DESC_CONCAT)) {
+		uint32_t len = NFT_REG32_COUNT;
+		const uint8_t *data;
+
+		data = nftnl_set_get_data(nls, NFTNL_SET_DESC_CONCAT, &len);
+		if (data) {
+			memcpy(set->desc.field_len, data, len);
+			set->desc.field_count = len;
+		}
+	}
+
 	return set;
 }
 
src/rule.c +1 -1
index 883b07072025..4853c4f302ee 100644
@@ -337,7 +337,7 @@ struct set *set_clone(const struct set *set)
 	new_set->objtype	= set->objtype;
 	new_set->policy		= set->policy;
 	new_set->automerge	= set->automerge;
-	new_set->desc.size	= set->desc.size;
+	new_set->desc		= set->desc;
 
 	return new_set;
 }
Signature · 1 line
2.24.1
#5 lore raw

PATCH v4 3/4 src: Add support for concatenated set ranges

In reply to Stefano Brivio

After exporting field lengths via NFTNL_SET_DESC_CONCAT attributes, we now need to adjust parsing of user input and generation of netlink key data to complete support for concatenation of set ranges.

Instead of using separate elements for start and end of a range, denoting the end element by the NFT_SET_ELEM_INTERVAL_END flag, as it's currently done for ranges without concatenation, we'll use the new attribute NFTNL_SET_ELEM_KEY_END as suggested by Pablo. It behaves in the same way as NFTNL_SET_ELEM_KEY, but it indicates that the included key represents the upper bound of a range.

For example, "packets with an IPv4 address between 192.0.2.0 and 192.0.2.42, with destination port between 22 and 25", needs to be expressed as a single element with two keys:

NFTA_SET_ELEM_KEY: 192.0.2.0 . 22
NFTA_SET_ELEM_KEY_END: 192.0.2.42 . 25

To achieve this, we need to:

- adjust the lexer rules to allow multiton expressions as elements of a concatenation. As wildcards are not allowed (semantics would be ambiguous), exclude wildcards expressions from the set of possible multiton expressions, and allow them directly where needed. Concatenations now admit prefixes and ranges

- generate, for each element in a range concatenation, a second key attribute, that includes the upper bound for the range

- also expand prefixes and non-ranged values in the concatenation to ranges: given a set with interval and concatenation support, the kernel has no way to tell which elements are ranged, so they all need to be. For example, 192.0.2.0 . 192.0.2.9 : 1024 is sent as:

NFTA_SET_ELEM_KEY: 192.0.2.0 . 1024
NFTA_SET_ELEM_KEY_END: 192.0.2.9 . 1024

- aggregate ranges when elements received by the kernel represent concatenated ranges, see concat_range_aggregate()

- perform a few minor adjustments where interval expressions are already handled: we have intervals in these sets, but the set specification isn't just an interval, so we can't just aggregate and deaggregate interval ranges linearly

v4: No changes
v3:
- rework to use a separate key for closing element of range instead of a separate element with EXPR_F_INTERVAL_END set (Pablo Neira Ayuso)
v2:
- reworked netlink_gen_concat_data(), moved loop body to a new function, netlink_gen_concat_data_expr() (Phil Sutter)
- dropped repeated pattern in bison file, replaced by a new helper, compound_expr_alloc_or_add() (Phil Sutter)
- added set_is_nonconcat_range() helper (Phil Sutter)
- in expr_evaluate_set(), we need to set NFT_SET_SUBKEY also on empty sets where the set in the context already has the flag
- dropped additional 'end' parameter from netlink_gen_data(), temporarily set EXPR_F_INTERVAL_END on expressions and use that from netlink_gen_concat_data() to figure out we need to add the 'end' element (Phil Sutter)
- replace range_mask_len() by a simplified version, as we don't need to actually store the composing masks of a range (Phil Sutter)

---
 include/expression.h |   1 +
 include/rule.h       |   5 ++
 src/evaluate.c       |   5 ++
 src/netlink.c        | 109 +++++++++++++++++++++++++++++-----------
 src/parser_bison.y   |  17 +++++--
 src/rule.c           |  13 ++---
 src/segtree.c        | 117 +++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 229 insertions(+), 38 deletions(-)
include/expression.h +1 -0
index 6196be58c2a6..cbf09b59c82b 100644
@@ -465,6 +465,7 @@ extern int set_to_intervals(struct list_head *msgs, struct set *set,
 			    struct expr *init, bool add,
 			    unsigned int debug_mask, bool merge,
 			    struct output_ctx *octx);
+extern void concat_range_aggregate(struct expr *set);
 extern void interval_map_decompose(struct expr *set);
 
 extern struct expr *get_set_intervals(const struct set *set,
include/rule.h +5 -0
index a7f106f715cf..c232221e541b 100644
@@ -372,6 +372,11 @@ static inline bool set_is_interval(uint32_t set_flags)
 	return set_flags & NFT_SET_INTERVAL;
 }
 
+static inline bool set_is_non_concat_range(struct set *s)
+{
+	return (s->flags & NFT_SET_INTERVAL) && s->desc.field_count <= 1;
+}
+
 #include <statement.h>
 
 struct counter {
src/evaluate.c +5 -0
index 55591f5f3526..208250715e1f 100644
@@ -136,6 +136,11 @@ static int byteorder_conversion(struct eval_ctx *ctx, struct expr **expr,
 
 	if ((*expr)->byteorder == byteorder)
 		return 0;
+
+	/* Conversion for EXPR_CONCAT is handled for single composing ranges */
+	if ((*expr)->etype == EXPR_CONCAT)
+		return 0;
+
 	if (expr_basetype(*expr)->type != TYPE_INTEGER)
 		return expr_error(ctx->msgs, *expr,
 			 	  "Byteorder mismatch: expected %s, got %s",
src/netlink.c +81 -28

176 lines not on this page · raw message

src/parser_bison.y +13 -4
index 799f7a308b07..e86cf7a9a6ff 100644
@@ -3592,7 +3592,6 @@ range_rhs_expr		:	basic_rhs_expr	DASH	basic_rhs_expr
 
 multiton_rhs_expr	:	prefix_rhs_expr
 			|	range_rhs_expr
-			|	wildcard_expr
 			;
 
 map_expr		:	concat_expr	MAP	rhs_expr
@@ -3686,7 +3685,7 @@ set_elem_option		:	TIMEOUT			time_spec
 			;
 
 set_lhs_expr		:	concat_rhs_expr
-			|	multiton_rhs_expr
+			|	wildcard_expr
 			;
 
 set_rhs_expr		:	concat_rhs_expr
@@ -3939,7 +3938,7 @@ list_rhs_expr		:	basic_rhs_expr		COMMA		basic_rhs_expr
 			;
 
 rhs_expr		:	concat_rhs_expr		{ $$ = $1; }
-			|	multiton_rhs_expr	{ $$ = $1; }
+			|	wildcard_expr		{ $$ = $1; }
 			|	set_expr		{ $$ = $1; }
 			|	set_ref_symbol_expr	{ $$ = $1; }
 			;
@@ -3980,7 +3979,17 @@ basic_rhs_expr		:	inclusive_or_rhs_expr
 			;
 
 concat_rhs_expr		:	basic_rhs_expr
-			|	concat_rhs_expr	DOT	basic_rhs_expr
+			|	multiton_rhs_expr
+			|	concat_rhs_expr		DOT	multiton_rhs_expr
+			{
+				struct location rhs[] = {
+					[1]	= @2,
+					[2]	= @3,
+				};
+
+				$$ = handle_concat_expr(&@$, $$, $1, $3, rhs);
+			}
+			|	concat_rhs_expr		DOT	basic_rhs_expr
 			{
 				struct location rhs[] = {
 					[1]	= @2,
src/rule.c +7 -6
index 4853c4f302ee..337a66bbd5fa 100644
@@ -1540,7 +1540,8 @@ static int __do_add_setelems(struct netlink_ctx *ctx, struct set *set,
 		return -1;
 
 	if (set->init != NULL &&
-	    set->flags & NFT_SET_INTERVAL) {
+	    set->flags & NFT_SET_INTERVAL &&
+	    set->desc.field_count <= 1) {
 		interval_map_decompose(expr);
 		list_splice_tail_init(&expr->expressions, &set->init->expressions);
 		set->init->size += expr->size;
@@ -1561,7 +1562,7 @@ static int do_add_setelems(struct netlink_ctx *ctx, struct cmd *cmd,
 	table = table_lookup(h, &ctx->nft->cache);
 	set = set_lookup(table, h->set.name);
 
-	if (set->flags & NFT_SET_INTERVAL &&
+	if (set_is_non_concat_range(set) &&
 	    set_to_intervals(ctx->msgs, set, init, true,
 			     ctx->nft->debug_mask, set->automerge,
 			     &ctx->nft->output) < 0)
@@ -1576,7 +1577,7 @@ static int do_add_set(struct netlink_ctx *ctx, const struct cmd *cmd,
 	struct set *set = cmd->set;
 
 	if (set->init != NULL) {
-		if (set->flags & NFT_SET_INTERVAL &&
+		if (set_is_non_concat_range(set) &&
 		    set_to_intervals(ctx->msgs, set, set->init, true,
 				     ctx->nft->debug_mask, set->automerge,
 				     &ctx->nft->output) < 0)
@@ -1662,7 +1663,7 @@ static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)
 	table = table_lookup(h, &ctx->nft->cache);
 	set = set_lookup(table, h->set.name);
 
-	if (set->flags & NFT_SET_INTERVAL &&
+	if (set_is_non_concat_range(set) &&
 	    set_to_intervals(ctx->msgs, set, expr, false,
 			     ctx->nft->debug_mask, set->automerge,
 			     &ctx->nft->output) < 0)
@@ -2516,7 +2517,7 @@ static int do_get_setelems(struct netlink_ctx *ctx, struct cmd *cmd,
 	set = set_lookup(table, cmd->handle.set.name);
 
 	/* Create a list of elements based of what we got from command line. */
-	if (set->flags & NFT_SET_INTERVAL)
+	if (set_is_non_concat_range(set))
 		init = get_set_intervals(set, cmd->expr);
 	else
 		init = cmd->expr;
@@ -2529,7 +2530,7 @@ static int do_get_setelems(struct netlink_ctx *ctx, struct cmd *cmd,
 	if (err >= 0)
 		__do_list_set(ctx, cmd, table, new_set);
 
-	if (set->flags & NFT_SET_INTERVAL)
+	if (set_is_non_concat_range(set))
 		expr_free(init);
 
 	set_free(new_set);
src/segtree.c +117 -0

135 lines not on this page · raw message

Signature · 1 line
2.24.1
#10 lore raw

PATCH v4 4/4 tests: Introduce test for set with concatenated ranges

In reply to Stefano Brivio

This test checks that set elements can be added, deleted, that addition and deletion are refused when appropriate, that entries time out properly, and that they can be fetched by matching values in the given ranges.

v4: No changes
v3:
- renumber test to 0042, 0041 was added meanwhile
v2:
- actually check an IPv6 prefix, instead of specifying everything as explicit ranges in ELEMS_ipv6_addr
- renumber test to 0041, 0038 already exists

---
 .../testcases/sets/0042concatenated_ranges_0  | 162 ++++++++++++++++++
 1 file changed, 162 insertions(+)
 create mode 100755 tests/shell/testcases/sets/0042concatenated_ranges_0
tests/shell/testcases/sets/0042concatenated_ranges_0 new file +162 -0
new file mode 100755
index 000000000000..244c5ffe7c75
@@ -0,0 +1,162 @@
+#!/bin/sh -e
+#
+# 0042concatenated_ranges_0 - Add, get, list, timeout for concatenated ranges
+#
+# Cycle over supported data types, forming concatenations of three fields, for
+# all possible permutations, and:
+# - add entries to set
+# - list them
+# - check that they can't be added again
+# - get entries by specifying a value matching ranges for all fields
+# - delete them
+# - add them with 1s timeout
+# - check that they can't be added again right away
+# - check that they are not listed after 1s
+# - delete them
+# - make sure they can't be deleted again
+
+TYPES="ipv4_addr ipv6_addr ether_addr inet_proto inet_service mark"
+
+RULESPEC_ipv4_addr="ip saddr"
+ELEMS_ipv4_addr="192.0.2.1 198.51.100.0/25 203.0.113.0-203.0.113.129"
+ADD_ipv4_addr="192.0.2.252/31"
+GET_ipv4_addr="198.51.100.127 198.51.100.0/25"
+
+RULESPEC_ipv6_addr="ip6 daddr"
+ELEMS_ipv6_addr="2001:db8:c0c:c0de::1-2001:db8:cacc::a 2001:db8::1 2001:db8:dada:da::/64"
+ADD_ipv6_addr="2001:db8::d1ca:d1ca"
+GET_ipv6_addr="2001:db8::1 2001:db8::1"
+
+RULESPEC_ether_addr="ether saddr"
+ELEMS_ether_addr="00:0a:c1:d1:f1:ed-00:0a:c1:dd:ec:af 00:0b:0c:ca:cc:10-c1:a0:c1:cc:10:00 f0:ca:cc:1a:b0:1a"
+ADD_ether_addr="00:be:1d:ed:ab:e1"
+GET_ether_addr="ac:c1:ac:c0:ce:c0 00:0b:0c:ca:cc:10-c1:a0:c1:cc:10:00"
+
+RULESPEC_inet_proto="meta l4proto"
+ELEMS_inet_proto="tcp udp icmp"
+ADD_inet_proto="sctp"
+GET_inet_proto="udp udp"
+
+RULESPEC_inet_service="tcp dport"
+ELEMS_inet_service="22-23 1024-32768 31337"
+ADD_inet_service="32769-65535"
+GET_inet_service="32768 1024-32768"
+
+RULESPEC_mark="mark"
+ELEMS_mark="0x00000064-0x000000c8 0x0000006f 0x0000fffd-0x0000ffff"
+ADD_mark="0x0000002a"
+GET_mark="0x0000006f 0x0000006f"
+
+tmp="$(mktemp)"
+trap "rm -f ${tmp}" EXIT
+
+render() {
+	eval "echo \"$(cat ${1})\""
+}
+
+cat <<'EOF' > "${tmp}"
+flush ruleset
+
+table inet filter {
+	set test {
+		type ${ta} . ${tb} . ${tc}
+		flags interval,timeout
+		elements = { ${a1} . ${b1} . ${c1} ,
+			     ${a2} . ${b2} . ${c2} ,
+			     ${a3} . ${b3} . ${c3} }
+	}
+
+	chain output {
+		type filter hook output priority 0; policy accept;
+		${sa} . ${sb} . ${sc} @test counter
+	}
+}
+EOF
+
+for ta in ${TYPES}; do
+	eval a=\$ELEMS_${ta}
+	a1=${a%% *}; a2=$(expr "$a" : ".* \(.*\) .*"); a3=${a##* }
+	eval sa=\$RULESPEC_${ta}
+
+	for tb in ${TYPES}; do
+		[ "${tb}" = "${ta}" ] && continue
+		if [ "${tb}" = "ipv6_addr" ]; then
+			[ "${ta}" = "ipv4_addr" ] && continue
+		elif [ "${tb}" = "ipv4_addr" ]; then
+			[ "${ta}" = "ipv6_addr" ] && continue
+		fi
+
+		eval b=\$ELEMS_${tb}
+		b1=${b%% *}; b2=$(expr "$b" : ".* \(.*\) .*"); b3=${b##* }
+		eval sb=\$RULESPEC_${tb}
+
+		for tc in ${TYPES}; do
+			[ "${tc}" = "${ta}" ] && continue
+			[ "${tc}" = "${tb}" ] && continue
+			if [ "${tc}" = "ipv6_addr" ]; then
+				[ "${ta}" = "ipv4_addr" ] && continue
+				[ "${tb}" = "ipv4_addr" ] && continue
+			elif [ "${tc}" = "ipv4_addr" ]; then
+				[ "${ta}" = "ipv6_addr" ] && continue
+				[ "${tb}" = "ipv6_addr" ] && continue
+			fi
+
+			eval c=\$ELEMS_${tc}
+			c1=${c%% *}; c2=$(expr "$c" : ".* \(.*\) .*"); c3=${c##* }
+			eval sc=\$RULESPEC_${tc}
+
+			render ${tmp} | ${NFT} -f -
+
+			[ $(${NFT} list set inet filter test |		\
+			   grep -c -e "${a1} . ${b1} . ${c1}"		\
+				   -e "${a2} . ${b2} . ${c2}"		\
+				   -e "${a3} . ${b3} . ${c3}") -eq 3 ]
+
+			! ${NFT} add element inet filter test \
+				"{ ${a1} . ${b1} . ${c1} }" 2>/dev/null
+			! ${NFT} add element inet filter test \
+				"{ ${a2} . ${b2} . ${c2} }" 2>/dev/null
+			! ${NFT} add element inet filter test \
+				"{ ${a3} . ${b3} . ${c3} }" 2>/dev/null
+
+			${NFT} delete element inet filter test \
+				"{ ${a1} . ${b1} . ${c1} }"
+			! ${NFT} delete element inet filter test \
+				"{ ${a1} . ${b1} . ${c1} }" 2>/dev/null
+
+			eval add_a=\$ADD_${ta}
+			eval add_b=\$ADD_${tb}
+			eval add_c=\$ADD_${tc}
+			${NFT} add element inet filter test \
+				"{ ${add_a} . ${add_b} . ${add_c} timeout 1s}"
+			[ $(${NFT} list set inet filter test |		\
+			   grep -c "${add_a} . ${add_b} . ${add_c}") -eq 1 ]
+			! ${NFT} add element inet filter test \
+				"{ ${add_a} . ${add_b} . ${add_c} timeout 1s}" \
+				2>/dev/null
+
+			eval get_a=\$GET_${ta}
+			eval get_b=\$GET_${tb}
+			eval get_c=\$GET_${tc}
+			exp_a=${get_a##* }; get_a=${get_a%% *}
+			exp_b=${get_b##* }; get_b=${get_b%% *}
+			exp_c=${get_c##* }; get_c=${get_c%% *}
+			[ $(${NFT} get element inet filter test 	\
+			   "{ ${get_a} . ${get_b} . ${get_c} }" |	\
+			   grep -c "${exp_a} . ${exp_b} . ${exp_c}") -eq 1 ]
+
+			sleep 1
+			[ $(${NFT} list set inet filter test |		\
+			   grep -c "${add_a} . ${add_b} . ${add_c}") -eq 0 ]
+
+			${NFT} delete element inet filter test \
+				"{ ${a2} . ${b2} . ${c2} }"
+			${NFT} delete element inet filter test \
+				"{ ${a3} . ${b3} . ${c3} }"
+			! ${NFT} delete element inet filter test \
+				"{ ${a2} . ${b2} . ${c2} }" 2>/dev/null
+			! ${NFT} delete element inet filter test \
+				"{ ${a3} . ${b3} . ${c3} }" 2>/dev/null
+		done
+	done
+done
Signature · 1 line
2.24.1
reviewer
#11 lore raw

Re: [PATCH nft v4 4/4] tests: Introduce test for set with concatenated ranges

Hi,

Quoted 4 lines · Stefano Brivio

This test checks that set elements can be added, deleted, that addition and deletion are refused when appropriate, that entries time out properly, and that they can be fetched by matching values in the given ranges.

Not worth blocking this series, but I really think this test should be reduced in size. On my VM, it takes 3.5min to complete, out of which 96secs are spent in sleep. /o\

Cheers, Phil

maintainer Applied
#2 lore raw

Re: [PATCH nft v4 1/4] include: resync nf_tables.h cache copy

In reply to Stefano Brivio
Quoted 2 lines · Stefano Brivio

Get this header in sync with nf-next as of merge commit b3a608222336 (5.6-rc1-ish).

Applied, thanks Stefano.

#4 lore raw

Re: [PATCH nft v4 2/4] src: Add support for NFTNL_SET_DESC_CONCAT

In reply to Stefano Brivio
Quoted 8 lines · Stefano Brivio

To support arbitrary range concatenations, the kernel needs to know how long each field in the concatenation is. The new libnftnl NFTNL_SET_DESC_CONCAT set attribute describes this as an array of lengths, in bytes, of concatenated fields.

While evaluating concatenated expressions, export the datatype size into the new field_len array, and hand the data over via libnftnl.

Quoted 8 lines

Similarly, when data is passed back from libnftnl, parse it into the set description.

When set data is cloned, we now need to copy the additional fields in set_clone(), too.

This change depends on the libnftnl patch with title:
set: Add support for NFTA_SET_DESC_CONCAT attributes

Also applied, thanks.

maintainer Applied
#6 lore raw

Re: [PATCH nft v4 3/4] src: Add support for concatenated set ranges

In reply to Stefano Brivio

Applied, thanks. See comments below though.

Quoted 36 lines · Stefano Brivio

After exporting field lengths via NFTNL_SET_DESC_CONCAT attributes, we now need to adjust parsing of user input and generation of netlink key data to complete support for concatenation of set ranges.

Instead of using separate elements for start and end of a range, denoting the end element by the NFT_SET_ELEM_INTERVAL_END flag, as it's currently done for ranges without concatenation, we'll use the new attribute NFTNL_SET_ELEM_KEY_END as suggested by Pablo. It behaves in the same way as NFTNL_SET_ELEM_KEY, but it indicates that the included key represents the upper bound of a range.

For example, "packets with an IPv4 address between 192.0.2.0 and 192.0.2.42, with destination port between 22 and 25", needs to be expressed as a single element with two keys:

NFTA_SET_ELEM_KEY: 192.0.2.0 . 22
NFTA_SET_ELEM_KEY_END: 192.0.2.42 . 25

To achieve this, we need to:

- adjust the lexer rules to allow multiton expressions as elements of a concatenation. As wildcards are not allowed (semantics would be ambiguous), exclude wildcards expressions from the set of possible multiton expressions, and allow them directly where needed. Concatenations now admit prefixes and ranges

- generate, for each element in a range concatenation, a second key attribute, that includes the upper bound for the range

- also expand prefixes and non-ranged values in the concatenation to ranges: given a set with interval and concatenation support, the kernel has no way to tell which elements are ranged, so they all need to be. For example, 192.0.2.0 . 192.0.2.9 : 1024 is sent as:

Quoted 5 lines

NFTA_SET_ELEM_KEY: 192.0.2.0 . 1024
NFTA_SET_ELEM_KEY_END: 192.0.2.9 . 1024

- aggregate ranges when elements received by the kernel represent concatenated ranges, see concat_range_aggregate()

I think concat_range_aggregate() can be remove.

NFTA_SET_ELEM_KEY and the NFTA_SET_ELEM_KEY_END are now coming in the same element. From the set element delinearization path this could just build the range, correct?

[...]

include/rule.h static inline bool set_is_interval(uint32_t set_flags) · line 378

Quoted 12 lines
include/rule.h +4 -0
index a7f106f715cf..c232221e541b 100644
@@ -372,6 +372,11 @@ static inline bool set_is_interval(uint32_t set_flags)
 	return set_flags & NFT_SET_INTERVAL;
 }
 
+static inline bool set_is_non_concat_range(struct set *s)
+{
+	return (s->flags & NFT_SET_INTERVAL) && s->desc.field_count <= 1;
+}

I might make a second pass to revisit this new helper.

Probably, we can pass struct set to all set_is_*() helpers instead, and use set_is_interval() for the legacy interval representation that is using the segtree infrastructure.

#12 lore raw

Re: [PATCH nft v4 4/4] tests: Introduce test for set with concatenated ranges

In reply to Stefano Brivio
Quoted 4 lines · Stefano Brivio

This test checks that set elements can be added, deleted, that addition and deletion are refused when appropriate, that entries time out properly, and that they can be fetched by matching values in the given ranges.

I'll keep this back so Phil doesn't have to do some knitting work meanwhile the tests finishes for those 3 minutes.

If this can be shortened, better. Probably you can add a parameter to enable the extra torture test mode not that is away from the ./run-test.sh path.

#8 lore raw

Re: [PATCH nft v4 3/4] src: Add support for concatenated set ranges

In reply to Stefano Brivio

src/evaluate.c static int byteorder_conversion(struct eval_ctx *ctx, struct expr **expr, · line 142

Quoted 12 lines · Stefano Brivio
src/evaluate.c +4 -0
index 55591f5f3526..208250715e1f 100644
@@ -136,6 +136,11 @@ static int byteorder_conversion(struct eval_ctx *ctx, struct expr **expr,
 
 	if ((*expr)->byteorder == byteorder)
 		return 0;
+
+	/* Conversion for EXPR_CONCAT is handled for single composing ranges */
+	if ((*expr)->etype == EXPR_CONCAT)
+		return 0;

Are you also sure this is correct?

This code was probably not exercised before with non-range concatenations.

Thanks.

Quoted 4 lines
src/evaluate.c +1 -0
+
 	if (expr_basetype(*expr)->type != TYPE_INTEGER)
 		return expr_error(ctx->msgs, *expr,
 			 	  "Byteorder mismatch: expected %s, got %s",
#7 lore raw

Re: [PATCH nft v4 3/4] src: Add support for concatenated set ranges

In reply to Pablo Neira Ayuso
Quoted 42 lines · On Fri, 7 Feb 2020 11:33:06 +0100 Pablo Neira Ayuso <[email protected]> wrote:

Applied, thanks. See comments below though.

Quoted 39 lines · Stefano Brivio

After exporting field lengths via NFTNL_SET_DESC_CONCAT attributes, we now need to adjust parsing of user input and generation of netlink key data to complete support for concatenation of set ranges.

Instead of using separate elements for start and end of a range, denoting the end element by the NFT_SET_ELEM_INTERVAL_END flag, as it's currently done for ranges without concatenation, we'll use the new attribute NFTNL_SET_ELEM_KEY_END as suggested by Pablo. It behaves in the same way as NFTNL_SET_ELEM_KEY, but it indicates that the included key represents the upper bound of a range.

For example, "packets with an IPv4 address between 192.0.2.0 and 192.0.2.42, with destination port between 22 and 25", needs to be expressed as a single element with two keys:

NFTA_SET_ELEM_KEY: 192.0.2.0 . 22
NFTA_SET_ELEM_KEY_END: 192.0.2.42 . 25

To achieve this, we need to:

- adjust the lexer rules to allow multiton expressions as elements of a concatenation. As wildcards are not allowed (semantics would be ambiguous), exclude wildcards expressions from the set of possible multiton expressions, and allow them directly where needed. Concatenations now admit prefixes and ranges

- generate, for each element in a range concatenation, a second key attribute, that includes the upper bound for the range

- also expand prefixes and non-ranged values in the concatenation to ranges: given a set with interval and concatenation support, the kernel has no way to tell which elements are ranged, so they all need to be. For example, 192.0.2.0 . 192.0.2.9 : 1024 is sent as:

NFTA_SET_ELEM_KEY: 192.0.2.0 . 1024
NFTA_SET_ELEM_KEY_END: 192.0.2.9 . 1024

Quoted 8 lines
Quoted 2 lines

- aggregate ranges when elements received by the kernel represent concatenated ranges, see concat_range_aggregate()

I think concat_range_aggregate() can be remove.

NFTA_SET_ELEM_KEY and the NFTA_SET_ELEM_KEY_END are now coming in the same element. From the set element delinearization path this could just build the range, correct?

Correct, with two caveats:

- building ranges isn't that straightforward. Some complexity currently in concat_range_aggregate() would go away if we embed that logic in netlink_delinearize_setelem(), but most of it would remain, and that logic doesn't seem to belong to "netlink" functions. I guess this is quite subjective though

- if we keep a mechanism that can build ranges this way, the day we want to switch to NFTA_SET_ELEM_KEY_END for ranges in general, also for other set types (or without concatenation anyway), maintaining compatibility with older kernels, it should be easier to let concat_range_aggregate() handle all cases. I'm not sure, I haven't really thought it through

Quoted 16 lines

[...]

include/rule.h static inline bool set_is_interval(uint32_t set_flags) · line 378

Quoted 12 lines
include/rule.h +4 -0
index a7f106f715cf..c232221e541b 100644
@@ -372,6 +372,11 @@ static inline bool set_is_interval(uint32_t set_flags)
 	return set_flags & NFT_SET_INTERVAL;
 }
 
+static inline bool set_is_non_concat_range(struct set *s)
+{
+	return (s->flags & NFT_SET_INTERVAL) && s->desc.field_count <= 1;
+}  

I might make a second pass to revisit this new helper.

Quoted 3 lines

Probably, we can pass struct set to all set_is_*() helpers instead, and use set_is_interval() for the legacy interval representation that is using the segtree infrastructure.

Ah, yes, I also think that would make sense.

By the way, while I didn't switch other helpers to take 'struct set' in this series (because it didn't fit the scope), I'm quite convinced that functions called set_is_*() should really take a 'set' as argument. :)

Signature · 1 line
Stefano
#13 lore raw

Re: [PATCH nft v4 4/4] tests: Introduce test for set with concatenated ranges

In reply to Pablo Neira Ayuso
Quoted 8 lines · On Fri, 7 Feb 2020 11:34:42 +0100 Pablo Neira Ayuso <[email protected]> wrote:
Quoted 4 lines · Stefano Brivio

This test checks that set elements can be added, deleted, that addition and deletion are refused when appropriate, that entries time out properly, and that they can be fetched by matching values in the given ranges.

I'll keep this back so Phil doesn't have to do some knitting work meanwhile the tests finishes for those 3 minutes.

But I wanted to see his production :(

Quoted 3 lines

If this can be shortened, better. Probably you can add a parameter to enable the extra torture test mode not that is away from the ./run-test.sh path.

I can't think of an easy way to remove that sleep(1), I could decrease the timeouts passed to nft but then there's no portable way to wait for less than one second.

Probably a good way to make it faster and still retain coverage would be to decrease the amount of combinations. Right now, most of the 6 ^ 3 combinations (six "types", three values each to have: single, prefix, range -- where allowed) are tested. I could stop after the first 3 x 3 matrix instead, if we come from run-tests.sh.

Let me know if you have other ideas, otherwise I'd send a patch doing this.

Signature · 1 line
Stefano
#9 lore raw

Re: [PATCH nft v4 3/4] src: Add support for concatenated set ranges

In reply to Pablo Neira Ayuso
Quoted 7 lines · On Fri, 7 Feb 2020 12:18:11 +0100 Pablo Neira Ayuso <[email protected]> wrote:
Quoted 6 lines · Stefano Brivio
src/evaluate.c +0 -0
index 55591f5f3526..208250715e1f 100644
@@ -136,6 +136,11 @@ static int byteorder_conversion(struct eval_ctx *ctx, struct expr **expr,
 
Quoted 8 lines

src/evaluate.c static int byteorder_conversion(struct eval_ctx *ctx, struct expr **expr, · line 142

Quoted 6 lines
src/evaluate.c +4 -0
 	if ((*expr)->byteorder == byteorder)
 		return 0;
+
+	/* Conversion for EXPR_CONCAT is handled for single composing ranges */
+	if ((*expr)->etype == EXPR_CONCAT)
+		return 0;  

Are you also sure this is correct?

Yes, I think so: if we add a set with a concatenation of three elements, byteorder_conversion() will be called three times with (*expr)->etype == EXPR_VALUE (which is what we might actually need to convert), and then once with EXPR_CONCAT, for which we have nothing to do.

Quoted 2 lines

This code was probably not exercised before with non-range concatenations.

I've seen it called for ranges in general. Do you mean we'd never get past:

	if ((*expr)->byteorder == byteorder)
		return 0;

?

Signature · 1 line
Stefano
reviewer
#14 lore raw

Re: [PATCH nft v4 4/4] tests: Introduce test for set with concatenated ranges

In reply to Stefano Brivio
Quoted 9 lines · Stefano Brivio
Quoted 6 lines · On Fri, 7 Feb 2020 11:34:42 +0100 Pablo Neira Ayuso <[email protected]> wrote:
Quoted 4 lines · Stefano Brivio

This test checks that set elements can be added, deleted, that addition and deletion are refused when appropriate, that entries time out properly, and that they can be fetched by matching values in the given ranges.

Quoted 4 lines
Quoted 2 lines

I'll keep this back so Phil doesn't have to do some knitting work meanwhile the tests finishes for those 3 minutes.

But I wanted to see his production :(

I'm not good at knitting, always liked crocheting more. That said, I like fast testsuites more than any of those. ;)

Quoted 8 lines
Quoted 3 lines

If this can be shortened, better. Probably you can add a parameter to enable the extra torture test mode not that is away from the ./run-test.sh path.

I can't think of an easy way to remove that sleep(1), I could decrease the timeouts passed to nft but then there's no portable way to wait for less than one second.

Quoted 8 lines

Probably a good way to make it faster and still retain coverage would be to decrease the amount of combinations. Right now, most of the 6 ^ 3 combinations (six "types", three values each to have: single, prefix, range -- where allowed) are tested. I could stop after the first 3 x 3 matrix instead, if we come from run-tests.sh.

Let me know if you have other ideas, otherwise I'd send a patch doing this.

You could test the timeout feature just once and for all? I doubt there will ever be a bug in that feature which only a certain data type exposes, but you may e.g. create all the sets with elements at the same time so waiting for the timeout once is enough.

Cheers, Phil

maintainer
#15 lore raw

Re: [PATCH nft v4 4/4] tests: Introduce test for set with concatenated ranges

In reply to Stefano Brivio
Quoted 14 lines · Stefano Brivio
Quoted 8 lines · On Fri, 7 Feb 2020 11:34:42 +0100 Pablo Neira Ayuso <[email protected]> wrote:
Quoted 4 lines · Stefano Brivio

This test checks that set elements can be added, deleted, that addition and deletion are refused when appropriate, that entries time out properly, and that they can be fetched by matching values in the given ranges.

I'll keep this back so Phil doesn't have to do some knitting work meanwhile the tests finishes for those 3 minutes.

But I wanted to see his production :(

Quoted 7 lines
Quoted 3 lines

If this can be shortened, better. Probably you can add a parameter to enable the extra torture test mode not that is away from the ./run-test.sh path.

I can't think of an easy way to remove that sleep(1), I could decrease the timeouts passed to nft but then there's no portable way to wait for less than one second.

Even busybox' sleep can do 'sleep 0.01', do we really need to be *that* portable?

#16 lore raw

Re: [PATCH nft v4 4/4] tests: Introduce test for set with concatenated ranges

Quoted 19 lines · On Mon, 10 Feb 2020 17:04:10 +0100 Florian Westphal <[email protected]> wrote:
Quoted 18 lines · Stefano Brivio
Quoted 8 lines · On Fri, 7 Feb 2020 11:34:42 +0100 Pablo Neira Ayuso <[email protected]> wrote:
Quoted 4 lines · Stefano Brivio

This test checks that set elements can be added, deleted, that addition and deletion are refused when appropriate, that entries time out properly, and that they can be fetched by matching values in the given ranges.

I'll keep this back so Phil doesn't have to do some knitting work meanwhile the tests finishes for those 3 minutes.

But I wanted to see his production :(

Quoted 3 lines

If this can be shortened, better. Probably you can add a parameter to enable the extra torture test mode not that is away from the ./run-test.sh path.

Quoted 5 lines
Quoted 3 lines

I can't think of an easy way to remove that sleep(1), I could decrease the timeouts passed to nft but then there's no portable way to wait for less than one second.

Even busybox' sleep can do 'sleep 0.01'

Wait, that's only if you build it with ENABLE_FEATURE_FANCY_SLEEP and ENABLE_FLOAT_DURATION.

Quoted 1 line

do we really need to be *that* portable?

I don't actually know :)

However, with Phil's idea:

Quoted 4 lines · On Mon, 10 Feb 2020 16:51:47 +0100 Phil Sutter <[email protected]> wrote:

You could test the timeout feature just once and for all? I doubt there will ever be a bug in that feature which only a certain data type exposes, but you may e.g. create all the sets with elements at the same time so waiting for the timeout once is enough.

which I think is entirely reasonable, this becomes a single one-second sleep, so it shouldn't be a problem anymore.

I would propose that I try this first, see if it gets reasonable, if it's not enough I'd go on and just reduce the number of combinations depending on how the script is invoked.

Signature · 1 line
Stefano