Skip to contentSkip to conversation

Introduce support for concatenated ranges

PATCH Superseded Stefano Brivio 2 participants 9 messages Nov 19, 2019 – Nov 21, 2019 netfilter

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

cover Introduce support for concatenated ranges

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

and it has a UAPI dependency on kernel patch:
[PATCH nf-next 1/8] nf_tables: Support for subkeys, set with multiple ranged fields

Patch 1/3 adds support for NFT_SET_SUBKEY: these new netlink attributes 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 2/3 introduces new key data semantics needed to represent arbitrary concatenation of ranges with minimal UAPI modifications, as well as required changes in lexer and expression evaluation.

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

I'm not updating the UAPI header copy in this series, please let me know if I'd better do that.

Stefano Brivio (3):
src: Add support for and export NFT_SET_SUBKEY attributes
src: Add support for concatenated set ranges
tests: Introduce test for set with concatenated ranges

 include/expression.h                          |   4 +
 include/netlink.h                             |   2 +-
 include/rule.h                                |   1 +
 src/evaluate.c                                |  25 ++-
 src/mnl.c                                     |   4 +
 src/netlink.c                                 |  95 +++++++---
 src/netlink_linearize.c                       |  16 +-
 src/parser_bison.y                            |  25 ++-
 src/rule.c                                    |  10 +-
 src/segtree.c                                 | 134 +++++++++++++++
 .../testcases/sets/0038concatenated_ranges_0  | 162 ++++++++++++++++++
 11 files changed, 432 insertions(+), 46 deletions(-)
 create mode 100755 tests/shell/testcases/sets/0038concatenated_ranges_0
Signature · 1 line
2.23.0
#1 lore raw

PATCH 1/3 src: Add support for and export NFT_SET_SUBKEY attributes

To support arbitrary range concatenations, the kernel needs to know how long each field in the concatenation is.

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

Note that, while the subkey length is expressed in bits, and the kernel attribute is 32-bit long to make UAPI more future-proof, we just reserve 8 bits for it, at the moment, and still store this data in bits.

As we don't have subkeys exceeding 128 bits in length, this should be fine, at least for a while, but it can be easily changed later on to use the full 32 bits allowed by the netlink attribute.

This change depends on the UAPI kernel patch with title:
netfilter: nf_tables: Support for subkeys, set with multiple ranged fields

---
 include/expression.h |  1 +
 include/rule.h       |  1 +
 src/evaluate.c       | 12 ++++++++----
 src/mnl.c            |  4 ++++
 4 files changed, 14 insertions(+), 4 deletions(-)
include/expression.h +1 -0
index 717b6755..b6d5adb2 100644
@@ -256,6 +256,7 @@ struct expr {
 			struct list_head	expressions;
 			unsigned int		size;
 			uint32_t		set_flags;
+			uint8_t			subkey_len[NFT_REG32_COUNT];
 		};
 		struct {
 			/* EXPR_SET_REF */
include/rule.h +1 -0
index 0b2eba37..a263947d 100644
@@ -308,6 +308,7 @@ struct set {
 	struct expr		*rg_cache;
 	uint32_t		policy;
 	bool			automerge;
+	uint8_t			subkey_len[NFT_REG32_COUNT];
 	struct {
 		uint32_t	size;
 	} desc;
src/evaluate.c +8 -4
index e54eaf1a..e1ecf4de 100644
@@ -1211,7 +1211,7 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr,
 {
 	const struct datatype *dtype = ctx->ectx.dtype, *tmp;
 	uint32_t type = dtype ? dtype->type : 0, ntype = 0;
-	int off = dtype ? dtype->subtypes : 0;
+	int off = dtype ? dtype->subtypes : 0, subkey_idx = 0;
 	unsigned int flags = EXPR_F_CONSTANT | EXPR_F_SINGLETON;
 	struct expr *i, *next;
 
@@ -1240,6 +1240,8 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr,
 						 i->dtype->name);
 
 		ntype = concat_subtype_add(ntype, i->dtype->type);
+
+		(*expr)->subkey_len[subkey_idx++] = i->dtype->size;
 	}
 
 	(*expr)->flags |= flags;
@@ -3301,9 +3303,11 @@ static int set_evaluate(struct eval_ctx *ctx, struct set *set)
 					 "specified in %s definition",
 					 set->key->dtype->name, 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->subkey_len, &set->key->subkey_len,
+		       sizeof(set->subkey_len));
+		set->flags |= NFT_SET_SUBKEY;
+	}
 
 	if (set_is_datamap(set->flags)) {
 		if (set->datatype == NULL)
src/mnl.c +4 -0
index fdba0af8..292a26fd 100644
@@ -880,6 +880,10 @@ int mnl_nft_set_add(struct netlink_ctx *ctx, const struct cmd *cmd,
 				 set->automerge))
 		memory_allocation_error();
 
+	if (set->flags & NFT_SET_SUBKEY)
+		nftnl_set_set_data(nls, NFTNL_SET_SUBKEY, &set->subkey_len,
+				   sizeof(set->subkey_len));
+
 	nftnl_set_set_data(nls, NFTNL_SET_USERDATA, nftnl_udata_buf_data(udbuf),
 			   nftnl_udata_buf_len(udbuf));
 	nftnl_udata_buf_free(udbuf);
Signature · 1 line
2.23.0
#2 lore raw

PATCH 2/3 src: Add support for concatenated set ranges

In reply to Stefano Brivio

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

The expression of concatenated ranges is described in the kernel counterpart for this change, quoted here:

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

[...]

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

192.0.2.0 . 22
192.0.2.42 . 25 with NFT_SET_ELEM_INTERVAL_END

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

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

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

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

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 concatenated range, two elements: one containing the start expressions, and one containing the end expressions for all fields in the concatenation

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

    192.0.2.0 : 1024
    192.0.2.9 : 1024 [end]

- aggregate ranges when elements for NFT_SET_SUBKEY sets are received by the kernel, 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

---
 include/expression.h    |   3 +
 include/netlink.h       |   2 +-
 src/evaluate.c          |  13 +++-
 src/netlink.c           |  95 +++++++++++++++++++++-------
 src/netlink_linearize.c |  16 ++---
 src/parser_bison.y      |  25 ++++++--
 src/rule.c              |  10 +--
 src/segtree.c           | 134 ++++++++++++++++++++++++++++++++++++++++
 8 files changed, 256 insertions(+), 42 deletions(-)
include/expression.h +3 -0
index b6d5adb2..61596c2e 100644
@@ -459,10 +459,13 @@ 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,
 				      const struct expr *init);
+static void set_elem_add(const struct set *set, struct expr *init, mpz_t value,
+			 uint32_t flags);
 struct table;
 extern int get_set_decompose(struct table *table, struct set *set);
 
include/netlink.h +1 -1
index e6941714..ad9e0d2a 100644
@@ -93,7 +93,7 @@ static inline unsigned int netlink_padding_len(unsigned int size)
 }
 
 extern void netlink_gen_data(const struct expr *expr,
-			     struct nft_data_linearize *data);
+			     struct nft_data_linearize *data, int is_range_end);
 extern void netlink_gen_raw_data(const mpz_t value, enum byteorder byteorder,
 				 unsigned int len,
 				 struct nft_data_linearize *data);
src/evaluate.c +12 -1
index e1ecf4de..8cbb0cbe 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",
@@ -1352,10 +1357,16 @@ static int expr_evaluate_set(struct eval_ctx *ctx, struct expr **expr)
 			set->size      += i->size - 1;
 			set->set_flags |= i->set_flags;
 			expr_free(i);
-		} else if (!expr_is_singleton(i))
+		} else if (!expr_is_singleton(i)) {
 			set->set_flags |= NFT_SET_INTERVAL;
+			if (i->key->etype == EXPR_CONCAT)
+				set->set_flags |= NFT_SET_SUBKEY;
+		}
 	}
 
+	if (ctx->set->flags & (NFT_SET_SUBKEY))
+		set->set_flags |= NFT_SET_SUBKEY;
+
 	set->set_flags |= NFT_SET_CONSTANT;
 
 	datatype_set(set, ctx->ectx.dtype);
src/netlink.c +72 -23

183 lines not on this page · raw message

src/netlink_linearize.c +8 -8
index 498326d0..ef696336 100644
@@ -393,10 +393,10 @@ static void netlink_gen_range(struct netlink_linearize_ctx *ctx,
 		nle = alloc_nft_expr("range");
 		netlink_put_register(nle, NFTNL_EXPR_RANGE_SREG, sreg);
 		nftnl_expr_set_u32(nle, NFTNL_EXPR_RANGE_OP, NFT_RANGE_NEQ);
-		netlink_gen_data(range->left, &nld);
+		netlink_gen_data(range->left, &nld, 0);
 		nftnl_expr_set(nle, NFTNL_EXPR_RANGE_FROM_DATA,
 			       nld.value, nld.len);
-		netlink_gen_data(range->right, &nld);
+		netlink_gen_data(range->right, &nld, 0);
 		nftnl_expr_set(nle, NFTNL_EXPR_RANGE_TO_DATA,
 			       nld.value, nld.len);
 		nftnl_rule_add_expr(ctx->nlr, nle);
@@ -407,7 +407,7 @@ static void netlink_gen_range(struct netlink_linearize_ctx *ctx,
 		netlink_put_register(nle, NFTNL_EXPR_CMP_SREG, sreg);
 		nftnl_expr_set_u32(nle, NFTNL_EXPR_CMP_OP,
 				   netlink_gen_cmp_op(OP_GTE));
-		netlink_gen_data(range->left, &nld);
+		netlink_gen_data(range->left, &nld, 0);
 		nftnl_expr_set(nle, NFTNL_EXPR_CMP_DATA, nld.value, nld.len);
 		nftnl_rule_add_expr(ctx->nlr, nle);
 
@@ -415,7 +415,7 @@ static void netlink_gen_range(struct netlink_linearize_ctx *ctx,
 		netlink_put_register(nle, NFTNL_EXPR_CMP_SREG, sreg);
 		nftnl_expr_set_u32(nle, NFTNL_EXPR_CMP_OP,
 				   netlink_gen_cmp_op(OP_LTE));
-		netlink_gen_data(range->right, &nld);
+		netlink_gen_data(range->right, &nld, 0);
 		nftnl_expr_set(nle, NFTNL_EXPR_CMP_DATA, nld.value, nld.len);
 		nftnl_rule_add_expr(ctx->nlr, nle);
 		break;
@@ -446,7 +446,7 @@ static void netlink_gen_flagcmp(struct netlink_linearize_ctx *ctx,
 	mpz_init_set_ui(zero, 0);
 
 	netlink_gen_raw_data(zero, expr->right->byteorder, len, &nld);
-	netlink_gen_data(expr->right, &nld2);
+	netlink_gen_data(expr->right, &nld2, 0);
 
 	nle = alloc_nft_expr("bitwise");
 	netlink_put_register(nle, NFTNL_EXPR_BITWISE_SREG, sreg);
@@ -529,7 +529,7 @@ static void netlink_gen_relational(struct netlink_linearize_ctx *ctx,
 	netlink_put_register(nle, NFTNL_EXPR_CMP_SREG, sreg);
 	nftnl_expr_set_u32(nle, NFTNL_EXPR_CMP_OP,
 			   netlink_gen_cmp_op(expr->op));
-	netlink_gen_data(right, &nld);
+	netlink_gen_data(right, &nld, 0);
 	nftnl_expr_set(nle, NFTNL_EXPR_CMP_DATA, nld.value, len);
 	release_register(ctx, expr->left);
 
@@ -662,7 +662,7 @@ static void netlink_gen_immediate(struct netlink_linearize_ctx *ctx,
 
 	nle = alloc_nft_expr("immediate");
 	netlink_put_register(nle, NFTNL_EXPR_IMM_DREG, dreg);
-	netlink_gen_data(expr, &nld);
+	netlink_gen_data(expr, &nld, 0);
 	switch (expr->etype) {
 	case EXPR_VALUE:
 		nftnl_expr_set(nle, NFTNL_EXPR_IMM_DATA, nld.value, nld.len);
@@ -766,7 +766,7 @@ static void netlink_gen_objref_stmt(struct netlink_linearize_ctx *ctx,
 				   expr->mappings->set->handle.set_id);
 		break;
 	case EXPR_VALUE:
-		netlink_gen_data(stmt->objref.expr, &nld);
+		netlink_gen_data(stmt->objref.expr, &nld, 0);
 		nftnl_expr_set(nle, NFTNL_EXPR_OBJREF_IMM_NAME,
 			       nld.value, nld.len);
 		nftnl_expr_set_u32(nle, NFTNL_EXPR_OBJREF_IMM_TYPE,
src/parser_bison.y +20 -5
index 3f283256..2b718971 100644
@@ -3554,7 +3554,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
@@ -3648,7 +3647,7 @@ set_elem_option		:	TIMEOUT			time_spec
 			;
 
 set_lhs_expr		:	concat_rhs_expr
-			|	multiton_rhs_expr
+			|	wildcard_expr
 			;
 
 set_rhs_expr		:	concat_rhs_expr
@@ -3901,7 +3900,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; }
 			;
 
@@ -3941,7 +3940,24 @@ 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
+			{
+				if ($$->etype != EXPR_CONCAT) {
+					$$ = concat_expr_alloc(&@$);
+					compound_expr_add($$, $1);
+				} else {
+					struct location rhs[] = {
+						[1]	= @2,
+						[2]	= @3,
+					};
+					location_update(&$3->location, rhs, 2);
+					$$ = $1;
+					$$->location = @$;
+				}
+				compound_expr_add($$, $3);
+			}
+			|	concat_rhs_expr		DOT	basic_rhs_expr
 			{
 				if ($$->etype != EXPR_CONCAT) {
 					$$ = concat_expr_alloc(&@$);
@@ -3952,7 +3968,6 @@ concat_rhs_expr		:	basic_rhs_expr
 						[2]	= @3,
 					};
 					location_update(&$3->location, rhs, 2);
-
 					$$ = $1;
 					$$->location = @$;
 				}
src/rule.c +6 -4
index 4abc13c9..377781b1 100644
@@ -1526,6 +1526,7 @@ static int do_add_setelems(struct netlink_ctx *ctx, struct cmd *cmd,
 	set = set_lookup(table, h->set.name);
 
 	if (set->flags & NFT_SET_INTERVAL &&
+	    !(set->flags & NFT_SET_SUBKEY) &&
 	    set_to_intervals(ctx->msgs, set, init, true,
 			     ctx->nft->debug_mask, set->automerge,
 			     &ctx->nft->output) < 0)
@@ -1541,6 +1542,7 @@ static int do_add_set(struct netlink_ctx *ctx, const struct cmd *cmd,
 
 	if (set->init != NULL) {
 		if (set->flags & NFT_SET_INTERVAL &&
+		    !(set->flags & NFT_SET_SUBKEY) &&
 		    set_to_intervals(ctx->msgs, set, set->init, true,
 				     ctx->nft->debug_mask, set->automerge,
 				     &ctx->nft->output) < 0)
@@ -1618,15 +1620,15 @@ static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd)
 
 static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)
 {
-	struct handle *h = &cmd->handle;
 	struct expr *expr = cmd->expr;
+	struct handle *h = &cmd->handle;
 	struct table *table;
 	struct set *set;
 
 	table = table_lookup(h, &ctx->nft->cache);
 	set = set_lookup(table, h->set.name);
 
-	if (set->flags & NFT_SET_INTERVAL &&
+	if (set->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY) &&
 	    set_to_intervals(ctx->msgs, set, expr, false,
 			     ctx->nft->debug_mask, set->automerge,
 			     &ctx->nft->output) < 0)
@@ -2480,7 +2482,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->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY))
 		init = get_set_intervals(set, cmd->expr);
 	else
 		init = cmd->expr;
@@ -2493,7 +2495,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->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY))
 		expr_free(init);
 
 	set_free(new_set);
src/segtree.c +134 -0

152 lines not on this page · raw message

Signature · 1 line
2.23.0
reviewer
#3 lore raw

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

Hi,

On Tue, Nov 19, 2019 at 02:07:11AM +0100, Stefano Brivio wrote:
[...]

Quoted 4 lines
src/netlink.c +0 -0
index 7306e358..b8bfd199 100644

[...]

Quoted 18 lines
src/netlink.c +10 -4
@@ -199,10 +210,39 @@ static void netlink_gen_concat_data(const struct expr *expr,
 		memset(data, 0, sizeof(data));
 		offset = 0;
 		list_for_each_entry(i, &expr->expressions, list) {
-			assert(i->etype == EXPR_VALUE);
-			mpz_export_data(data + offset, i->value, i->byteorder,
-					div_round_up(i->len, BITS_PER_BYTE));
-			offset += netlink_padded_len(i->len) / BITS_PER_BYTE;
+			if (i->etype == EXPR_RANGE) {
+				const struct expr *e;
+
+				if (is_range_end)
+					e = i->right;
+				else
+					e = i->left;
+
+				offset += netlink_export_pad(data + offset,
+							     e->value, e);

src/netlink.c static void netlink_gen_concat_data(const struct expr *expr, · line 232

Quoted 10 lines
src/netlink.c +10 -0
+			} else if (i->etype == EXPR_PREFIX) {
+				if (is_range_end) {
+					mpz_t v;
+
+					mpz_init_bitmask(v, i->len -
+							    i->prefix_len);
+					mpz_add(v, i->prefix->value, v);
+					offset += netlink_export_pad(data +
+								     offset,
+								     v, i);

Given the right-alignment, maybe introduce __netlink_gen_concat_data() to contain the loop body?

Quoted 17 lines
src/netlink.c +13 -0
+					mpz_clear(v);
+					continue;
+				}
+
+				offset += netlink_export_pad(data + offset,
+							     i->prefix->value,
+							     i);
+			} else {
+				assert(i->etype == EXPR_VALUE);
+
+				offset += netlink_export_pad(data + offset,
+							     i->value, i);
+			}
 		}
 
 		memcpy(nld->value, data, len);

src/netlink.c static void netlink_gen_verdict(const struct expr *expr, · line 291

Quoted 6 lines
src/netlink.c +2 -1
@@ -247,13 +287,14 @@ static void netlink_gen_verdict(const struct expr *expr,
 	}
 }
 
-void netlink_gen_data(const struct expr *expr, struct nft_data_linearize *data)
+void netlink_gen_data(const struct expr *expr, struct nft_data_linearize *data,
+		      int end)

s/end/is_range_end/ for consistency?

Quoted 13 lines
src/netlink.c +1 -1
 {
 	switch (expr->etype) {
 	case EXPR_VALUE:
 		return netlink_gen_constant_data(expr, data);
 	case EXPR_CONCAT:
-		return netlink_gen_concat_data(expr, data);
+		return netlink_gen_concat_data(expr, data, end);
 	case EXPR_VERDICT:
 		return netlink_gen_verdict(expr, data);
 	default:
@@ -712,8 +753,14 @@ void alloc_setelem_cache(const struct expr *set, struct nftnl_set *nls)
 	const struct expr *expr;
 

src/netlink.c void alloc_setelem_cache(const struct expr *set, struct nftnl_set *nls) · line 763

Quoted 10 lines
src/netlink.c +7 -1
 	list_for_each_entry(expr, &set->expressions, list) {
-		nlse = alloc_nftnl_setelem(set, expr);
+		nlse = alloc_nftnl_setelem(set, expr, 0);
 		nftnl_set_elem_add(nls, nlse);
+
+		if (set->set_flags & NFT_SET_SUBKEY) {
+			nlse = alloc_nftnl_setelem(set, expr, 1);
+			nftnl_set_elem_add(nls, nlse);
+		}
+

Can't we drop 'const' from expr declaration and temporarily set EXPR_F_INTERVAL_END to carry the is_interval_end bit or does that mess up set element creation?

What I don't like about your code is how it adds an expression-type specific parameter to netlink_gen_data which is supposed to be type-agnostic. Avoiding this would also shrink this patch quite a bit.

[...]

Quoted 4 lines
src/parser_bison.y +0 -0
index 3f283256..2b718971 100644

[...]

Quoted 13 lines
src/parser_bison.y +8 -1
@@ -3941,7 +3940,24 @@ 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
+			{
+				if ($$->etype != EXPR_CONCAT) {
+					$$ = concat_expr_alloc(&@$);
+					compound_expr_add($$, $1);
+				} else {
+					struct location rhs[] = {

src/parser_bison.y basic_rhs_expr : inclusive_or_rhs_expr · line 3960

Quoted 10 lines
src/parser_bison.y +10 -0
+						[1]	= @2,
+						[2]	= @3,
+					};
+					location_update(&$3->location, rhs, 2);
+					$$ = $1;
+					$$->location = @$;
+				}
+				compound_expr_add($$, $3);
+			}
+			|	concat_rhs_expr		DOT	basic_rhs_expr

So this is the fifth copy of the same piece of code. :(

Isn't there a better way to solve that? If not, we could at least introduce a function compound_expr_alloc_or_add().

[...]

Quoted 4 lines
src/rule.c +0 -0
index 4abc13c9..377781b1 100644

[...]

src/rule.c static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd) · line 1624

Quoted 7 lines
src/rule.c +1 -1
@@ -1618,15 +1620,15 @@ static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd)
 
 static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)
 {
-	struct handle *h = &cmd->handle;
 	struct expr *expr = cmd->expr;
+	struct handle *h = &cmd->handle;

Unrelated change?

src/rule.c static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd) · line 1631

Quoted 8 lines
src/rule.c +1 -1
 	struct table *table;
 	struct set *set;
 
 	table = table_lookup(h, &ctx->nft->cache);
 	set = set_lookup(table, h->set.name);
 
-	if (set->flags & NFT_SET_INTERVAL &&
+	if (set->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY) &&

Maybe introduce set_is_non_concat_range() or something? Maybe even a macro, it's just about:

| return set->flags & (NFT_SET_INTERVAL | NFT_SET_SUBKEY) == NFT_SET_INTERVAL;

[...]

Quoted 4 lines
src/segtree.c +0 -0
index 9f1eecc0..e49576bc 100644

[...]

src/segtree.c static int expr_value_cmp(const void *p1, const void *p2) · line 833

Quoted 7 lines
src/segtree.c +3 -0
@@ -823,6 +828,9 @@ static int expr_value_cmp(const void *p1, const void *p2)
 	struct expr *e2 = *(void * const *)p2;
 	int ret;
 
+	if (expr_value(e1)->etype == EXPR_CONCAT)
+		return -1;
+

Funny how misleading expr_value()'s name is. ;)

[...]

Quoted 32 lines
src/segtree.c +32 -0
+/* Given start and end elements of a range, check if it can be represented as
+ * a single netmask, and if so, how long, by returning a zero or positive value.
+ */
+static int range_mask_len(mpz_t start, mpz_t end, unsigned int len)
+{
+	unsigned int step = 0, i;
+	mpz_t base, tmp;
+	int masks = 0;
+
+	mpz_init_set_ui(base, mpz_get_ui(start));
+
+	while (mpz_cmp(base, end) <= 0) {
+		step = 0;
+		while (!mpz_tstbit(base, step)) {
+			mpz_init_set_ui(tmp, mpz_get_ui(base));
+			for (i = 0; i <= step; i++)
+				mpz_setbit(tmp, i);
+			if (mpz_cmp(tmp, end) > 0) {
+				mpz_clear(tmp);
+				break;
+			}
+			mpz_clear(tmp);
+
+			step++;
+
+			if (step >= len)
+				goto out;
+		}
+
+		if (masks++)
+			goto out;
+

src/segtree.c static int expr_value_cmp(const void *p1, const void *p2) · line 886

Quoted 10 lines
src/segtree.c +10 -0
+		mpz_add_ui(base, base, 1 << step);
+	}
+
+out:
+	mpz_clear(base);
+
+	if (masks > 1)
+		return -1;
+	return len - step;
+}

I don't understand this algorithm. Intuitively, I would just:

| int tmp = len;
| while (start != end && !(start & 1) && (end & 1) && tmp) {
|	start >>= 1;
|	end >>= 1;
|	tmp--;
| }
| return (tmp && start == end) ? len - tmp : -1;

Is that slow when dealing with gmp?

Thanks, Phil

#4 lore raw

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

Hi,

Quoted 32 lines · On Tue, 19 Nov 2019 23:12:38 +0100 Phil Sutter <[email protected]> wrote:

Hi,

On Tue, Nov 19, 2019 at 02:07:11AM +0100, Stefano Brivio wrote:
[...]

Quoted 4 lines
src/netlink.c +0 -0
index 7306e358..b8bfd199 100644

[...]

Quoted 23 lines
src/netlink.c +15 -4
@@ -199,10 +210,39 @@ static void netlink_gen_concat_data(const struct expr *expr,
 		memset(data, 0, sizeof(data));
 		offset = 0;
 		list_for_each_entry(i, &expr->expressions, list) {
-			assert(i->etype == EXPR_VALUE);
-			mpz_export_data(data + offset, i->value, i->byteorder,
-					div_round_up(i->len, BITS_PER_BYTE));
-			offset += netlink_padded_len(i->len) / BITS_PER_BYTE;
+			if (i->etype == EXPR_RANGE) {
+				const struct expr *e;
+
+				if (is_range_end)
+					e = i->right;
+				else
+					e = i->left;
+
+				offset += netlink_export_pad(data + offset,
+							     e->value, e);
+			} else if (i->etype == EXPR_PREFIX) {
+				if (is_range_end) {
+					mpz_t v;
+
+					mpz_init_bitmask(v, i->len -
Quoted 8 lines

src/netlink.c static void netlink_gen_concat_data(const struct expr *expr, · line 232

Quoted 5 lines
src/netlink.c +5 -0
+							    i->prefix_len);
+					mpz_add(v, i->prefix->value, v);
+					offset += netlink_export_pad(data +
+								     offset,
+								     v, i);  

Given the right-alignment, maybe introduce __netlink_gen_concat_data() to contain the loop body?

While at it, I would also drop the if (1) that makes this function not so pretty. It was introduced by 53fc2c7a7998 ("netlink: move data related functions to netlink.c") where data was turned from a allocated buffer to VLA, but I don't see a reason why we can't do:

	unsigned int len = expr->len / BITS_PER_BYTE, offset = 0;
	unsigned char data[len];

So, the whole thing would look like (together with the other change you suggest):

--
static int netlink_gen_concat_data_expr(const struct expr *i,
unsigned char *data)

{
	if (i->etype == EXPR_RANGE) {
		const struct expr *e;

		if (i->flags & EXPR_F_INTERVAL_END)
			e = i->right;
		else
			e = i->left;

		return netlink_export_pad(data, e->value, e);
	}

	if (i->etype == EXPR_PREFIX) {
		if (i->flags & EXPR_F_INTERVAL_END) {
			int count;
			mpz_t v;

			mpz_init_bitmask(v, i->len - i->prefix_len);
			mpz_add(v, i->prefix->value, v);
			count = netlink_export_pad(data, v, i);
			mpz_clear(v);
			return count;
		}

		return netlink_export_pad(data, i->prefix->value, i);
	}

	assert(i->etype == EXPR_VALUE);

	return netlink_export_pad(data, i->value, i);
}

static void netlink_gen_concat_data(const struct expr *expr,
struct nft_data_linearize *nld)

{
	unsigned int len = expr->len / BITS_PER_BYTE, offset = 0;
	unsigned char data[len];
	const struct expr *i;

	memset(data, 0, len);

	list_for_each_entry(i, &expr->expressions, list)
		offset += netlink_gen_concat_data_expr(i, data + offset);

	memcpy(nld->value, data, len);
	nld->len = len;
}

--

Is that better?

Quoted 21 lines
Quoted 21 lines
src/netlink.c +13 -0
+					mpz_clear(v);
+					continue;
+				}
+
+				offset += netlink_export_pad(data + offset,
+							     i->prefix->value,
+							     i);
+			} else {
+				assert(i->etype == EXPR_VALUE);
+
+				offset += netlink_export_pad(data + offset,
+							     i->value, i);
+			}
 		}
 
 		memcpy(nld->value, data, len);
@@ -247,13 +287,14 @@ static void netlink_gen_verdict(const struct expr *expr,
 	}
 }
 
Quoted 5 lines

src/netlink.c static void netlink_gen_verdict(const struct expr *expr, · line 291

Quoted 3 lines
src/netlink.c +2 -1
-void netlink_gen_data(const struct expr *expr, struct nft_data_linearize *data)
+void netlink_gen_data(const struct expr *expr, struct nft_data_linearize *data,
+		      int end)  

s/end/is_range_end/ for consistency?

Oops, yes, it had 'is_range_end' in the prototype but not here. Probably dropping this anyway.

Quoted 13 lines
Quoted 13 lines
src/netlink.c +1 -1
 {
 	switch (expr->etype) {
 	case EXPR_VALUE:
 		return netlink_gen_constant_data(expr, data);
 	case EXPR_CONCAT:
-		return netlink_gen_concat_data(expr, data);
+		return netlink_gen_concat_data(expr, data, end);
 	case EXPR_VERDICT:
 		return netlink_gen_verdict(expr, data);
 	default:
@@ -712,8 +753,14 @@ void alloc_setelem_cache(const struct expr *set, struct nftnl_set *nls)
 	const struct expr *expr;
 
Quoted 14 lines

src/netlink.c void alloc_setelem_cache(const struct expr *set, struct nftnl_set *nls) · line 763

Quoted 10 lines
src/netlink.c +7 -1
 	list_for_each_entry(expr, &set->expressions, list) {
-		nlse = alloc_nftnl_setelem(set, expr);
+		nlse = alloc_nftnl_setelem(set, expr, 0);
 		nftnl_set_elem_add(nls, nlse);
+
+		if (set->set_flags & NFT_SET_SUBKEY) {
+			nlse = alloc_nftnl_setelem(set, expr, 1);
+			nftnl_set_elem_add(nls, nlse);
+		}
+  

Can't we drop 'const' from expr declaration and temporarily set EXPR_F_INTERVAL_END to carry the is_interval_end bit or does that mess up set element creation?

No, it actually works nicely, I simply didn't think of that.

Quoted 3 lines

What I don't like about your code is how it adds an expression-type specific parameter to netlink_gen_data which is supposed to be type-agnostic. Avoiding this would also shrink this patch quite a bit.

Indeed, I also didn't like that, thanks for the tip. I'm changing this in v2.

Quoted 32 lines

[...]

Quoted 4 lines
src/parser_bison.y +0 -0
index 3f283256..2b718971 100644

[...]

Quoted 13 lines
src/parser_bison.y +8 -1
@@ -3941,7 +3940,24 @@ 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
+			{
+				if ($$->etype != EXPR_CONCAT) {
+					$$ = concat_expr_alloc(&@$);
+					compound_expr_add($$, $1);
+				} else {
+					struct location rhs[] = {

src/parser_bison.y basic_rhs_expr : inclusive_or_rhs_expr · line 3960

Quoted 10 lines
src/parser_bison.y +10 -0
+						[1]	= @2,
+						[2]	= @3,
+					};
+					location_update(&$3->location, rhs, 2);
+					$$ = $1;
+					$$->location = @$;
+				}
+				compound_expr_add($$, $3);
+			}
+			|	concat_rhs_expr		DOT	basic_rhs_expr  

So this is the fifth copy of the same piece of code. :(

Quoted 1 line

Isn't there a better way to solve that?

I couldn't think of any.

Quoted 1 line

If not, we could at least introduce a function compound_expr_alloc_or_add().

Right, added. The only ugly aspect is that we also need to update the location of $3 here, and I don't think we should export location_update() from parser_bison.y, so this function needs to be in parser_byson.y itself, I guess.

Quoted 8 lines

[...]

Quoted 4 lines
src/rule.c +0 -0
index 4abc13c9..377781b1 100644

[...]

Quoted 2 lines
src/rule.c +0 -0
@@ -1618,15 +1620,15 @@ static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd)
 
Quoted 7 lines

src/rule.c static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd) · line 1624

Quoted 5 lines
src/rule.c +1 -1
 static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)
 {
-	struct handle *h = &cmd->handle;
 	struct expr *expr = cmd->expr;
+	struct handle *h = &cmd->handle;  

Unrelated change?

Oops.

Quoted 6 lines
Quoted 6 lines
src/rule.c +0 -0
 	struct table *table;
 	struct set *set;
 
 	table = table_lookup(h, &ctx->nft->cache);
 	set = set_lookup(table, h->set.name);
 
Quoted 7 lines

src/rule.c static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd) · line 1631

Quoted 2 lines
src/rule.c +1 -1
-	if (set->flags & NFT_SET_INTERVAL &&
+	if (set->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY) &&  

Maybe introduce set_is_non_concat_range() or something? Maybe even a macro, it's just about:

| return set->flags & (NFT_SET_INTERVAL | NFT_SET_SUBKEY) == NFT_SET_INTERVAL;

I'm adding that as static inline together with the other set_is_*() functions in rule.h, it looks consistent.

Quoted 53 lines

[...]

Quoted 4 lines
src/segtree.c +0 -0
index 9f1eecc0..e49576bc 100644

[...]

src/segtree.c static int expr_value_cmp(const void *p1, const void *p2) · line 833

Quoted 7 lines
src/segtree.c +3 -0
@@ -823,6 +828,9 @@ static int expr_value_cmp(const void *p1, const void *p2)
 	struct expr *e2 = *(void * const *)p2;
 	int ret;
 
+	if (expr_value(e1)->etype == EXPR_CONCAT)
+		return -1;
+  

Funny how misleading expr_value()'s name is. ;)

[...]

Quoted 36 lines
src/segtree.c +36 -0
+/* Given start and end elements of a range, check if it can be represented as
+ * a single netmask, and if so, how long, by returning a zero or positive value.
+ */
+static int range_mask_len(mpz_t start, mpz_t end, unsigned int len)
+{
+	unsigned int step = 0, i;
+	mpz_t base, tmp;
+	int masks = 0;
+
+	mpz_init_set_ui(base, mpz_get_ui(start));
+
+	while (mpz_cmp(base, end) <= 0) {
+		step = 0;
+		while (!mpz_tstbit(base, step)) {
+			mpz_init_set_ui(tmp, mpz_get_ui(base));
+			for (i = 0; i <= step; i++)
+				mpz_setbit(tmp, i);
+			if (mpz_cmp(tmp, end) > 0) {
+				mpz_clear(tmp);
+				break;
+			}
+			mpz_clear(tmp);
+
+			step++;
+
+			if (step >= len)
+				goto out;
+		}
+
+		if (masks++)
+			goto out;
+
+		mpz_add_ui(base, base, 1 << step);
+	}
+
+out:
Quoted 8 lines

src/segtree.c static int expr_value_cmp(const void *p1, const void *p2) · line 886

Quoted 6 lines
src/segtree.c +6 -0
+	mpz_clear(base);
+
+	if (masks > 1)
+		return -1;
+	return len - step;
+}  

I don't understand this algorithm.

It basically does the same thing as the function you wrote below, but instead of shifting 'start' and 'end', 'step' is increased, and set onto them, so that at every iteration we have the resulting mask available in 'base'.

That's not actually needed here, though. It's a left-over from a previous idea of generating composing netmasks in nftables rather than in the set. I'll switch to the "obvious" implementation.

Quoted 11 lines

Intuitively, I would just:

| int tmp = len;
| while (start != end && !(start & 1) && (end & 1) && tmp) {
|	start >>= 1;
|	end >>= 1;
|	tmp--;
| }
| return (tmp && start == end) ? len - tmp : -1;

Is that slow when dealing with gmp?

I don't think so, it also avoid copies and allocations, while shifting and setting bits have comparable complexities. I'd go with the gmp version of this.

Signature · 1 line
Stefano
reviewer
#5 lore raw

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

Hi,

Quoted 41 lines · Stefano Brivio
Quoted 30 lines · On Tue, 19 Nov 2019 23:12:38 +0100 Phil Sutter <[email protected]> wrote:

On Tue, Nov 19, 2019 at 02:07:11AM +0100, Stefano Brivio wrote:
[...]

Quoted 4 lines
src/netlink.c +0 -0
index 7306e358..b8bfd199 100644

[...]

Quoted 23 lines
src/netlink.c +15 -4
@@ -199,10 +210,39 @@ static void netlink_gen_concat_data(const struct expr *expr,
 		memset(data, 0, sizeof(data));
 		offset = 0;
 		list_for_each_entry(i, &expr->expressions, list) {
-			assert(i->etype == EXPR_VALUE);
-			mpz_export_data(data + offset, i->value, i->byteorder,
-					div_round_up(i->len, BITS_PER_BYTE));
-			offset += netlink_padded_len(i->len) / BITS_PER_BYTE;
+			if (i->etype == EXPR_RANGE) {
+				const struct expr *e;
+
+				if (is_range_end)
+					e = i->right;
+				else
+					e = i->left;
+
+				offset += netlink_export_pad(data + offset,
+							     e->value, e);
+			} else if (i->etype == EXPR_PREFIX) {
+				if (is_range_end) {
+					mpz_t v;
+
+					mpz_init_bitmask(v, i->len -
Quoted 8 lines

src/netlink.c static void netlink_gen_concat_data(const struct expr *expr, · line 232

Quoted 5 lines
src/netlink.c +5 -0
+							    i->prefix_len);
+					mpz_add(v, i->prefix->value, v);
+					offset += netlink_export_pad(data +
+								     offset,
+								     v, i);  

Given the right-alignment, maybe introduce __netlink_gen_concat_data() to contain the loop body?

Quoted 7 lines

While at it, I would also drop the if (1) that makes this function not so pretty. It was introduced by 53fc2c7a7998 ("netlink: move data related functions to netlink.c") where data was turned from a allocated buffer to VLA, but I don't see a reason why we can't do:

	unsigned int len = expr->len / BITS_PER_BYTE, offset = 0;
	unsigned char data[len];

ACK!

Quoted 30 lines

So, the whole thing would look like (together with the other change you suggest):

--
static int netlink_gen_concat_data_expr(const struct expr *i,
unsigned char *data)

{
	if (i->etype == EXPR_RANGE) {
		const struct expr *e;

		if (i->flags & EXPR_F_INTERVAL_END)
			e = i->right;
		else
			e = i->left;

		return netlink_export_pad(data, e->value, e);
	}

	if (i->etype == EXPR_PREFIX) {
		if (i->flags & EXPR_F_INTERVAL_END) {
			int count;
			mpz_t v;

			mpz_init_bitmask(v, i->len - i->prefix_len);
			mpz_add(v, i->prefix->value, v);
			count = netlink_export_pad(data, v, i);
			mpz_clear(v);
			return count;
		}
Quoted 7 lines
		return netlink_export_pad(data, i->prefix->value, i);
	}

	assert(i->etype == EXPR_VALUE);

	return netlink_export_pad(data, i->value, i);
}

I would even:

| static int
| netlink_gen_concat_data_expr(const struct expr *i, unsigned char *data)
| {
| 	mpz_t *valp = NULL;
| 
| 	switch (i->etype) {
| 	case EXPR_RANGE:
| 		i = (i->flags & EXPR_F_INTERVAL_END) ? i->right : i->left;
| 		break;
| 	case EXPR_PREFIX:
| 		if (i->flags & EXPR_F_INTERVAL_END) {
| 			int count;
| 			mpz_t v;
| 
| 			mpz_init_bitmask(v, i->len - i->prefix_len);
| 			mpz_add(v, i->prefix->value, v);
| 			count = netlink_export_pad(data, v, i);
| 			mpz_clear(v);
| 			return count;
| 		}
| 		valp = &i->prefix->value;
| 		break;
| 	case EXPR_VALUE:
| 		break;
| 	default:
| 		BUG("invalid expression type '%s' in set", expr_ops(i)->name);
| 	}
| 
| 	return netlink_export_pad(data, valp ? *valp : i->value, i);
| }

But that's up to you. :)

Quoted 15 lines

static void netlink_gen_concat_data(const struct expr *expr,
struct nft_data_linearize *nld)

{
	unsigned int len = expr->len / BITS_PER_BYTE, offset = 0;
	unsigned char data[len];
	const struct expr *i;

	memset(data, 0, len);

	list_for_each_entry(i, &expr->expressions, list)
		offset += netlink_gen_concat_data_expr(i, data + offset);

	memcpy(nld->value, data, len);
	nld->len = len;
}
Quoted 3 lines

--

Is that better?

Looks great, thanks!

[...]

Quoted 5 lines
Quoted 3 lines

So this is the fifth copy of the same piece of code. :(

Isn't there a better way to solve that?

I couldn't think of any.

I guess we would need an intermediate state which is 'multiton_rhs_expr DOT multiton_rhs_expr'. Might turn into a mess as well. :)

Quoted 6 lines
Quoted 1 line

If not, we could at least introduce a function compound_expr_alloc_or_add().

Right, added. The only ugly aspect is that we also need to update the location of $3 here, and I don't think we should export location_update() from parser_bison.y, so this function needs to be in parser_byson.y itself, I guess.

Yes, that's fine with me. It's just my c'n'p aversion which got worse when spending time with iptables code.

[..]

Quoted 10 lines
Quoted 7 lines

src/netlink.c static void netlink_gen_concat_data(const struct expr *expr, · line 233

Quoted 2 lines
src/netlink.c +1 -1
-	if (set->flags & NFT_SET_INTERVAL &&
+	if (set->flags & NFT_SET_INTERVAL && !(set->flags & NFT_SET_SUBKEY) &&  

Maybe introduce set_is_non_concat_range() or something? Maybe even a macro, it's just about:

| return set->flags & (NFT_SET_INTERVAL | NFT_SET_SUBKEY) == NFT_SET_INTERVAL;

I'm adding that as static inline together with the other set_is_*() functions in rule.h, it looks consistent.

ACK!

[...]

Quoted 21 lines
Quoted 1 line

I don't understand this algorithm.

It basically does the same thing as the function you wrote below, but instead of shifting 'start' and 'end', 'step' is increased, and set onto them, so that at every iteration we have the resulting mask available in 'base'.

That's not actually needed here, though. It's a left-over from a previous idea of generating composing netmasks in nftables rather than in the set. I'll switch to the "obvious" implementation.

Quoted 10 lines

Intuitively, I would just:

| int tmp = len;
| while (start != end && !(start & 1) && (end & 1) && tmp) {
|	start >>= 1;
|	end >>= 1;
|	tmp--;
| }
| return (tmp && start == end) ? len - tmp : -1;
Quoted 5 lines
Quoted 1 line

Is that slow when dealing with gmp?

I don't think so, it also avoid copies and allocations, while shifting and setting bits have comparable complexities. I'd go with the gmp version of this.

OK, thanks for explaining!

Cheers, Phil

#6 lore raw

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

Quoted 77 lines · On Wed, 20 Nov 2019 13:53:08 +0100 Phil Sutter <[email protected]> wrote:
Quoted 2 lines · Stefano Brivio

On Tue, 19 Nov 2019 23:12:38 +0100
Phil Sutter <[email protected]> wrote:

[...]

Quoted 30 lines

So, the whole thing would look like (together with the other change you suggest):

--
static int netlink_gen_concat_data_expr(const struct expr *i,
unsigned char *data)

{
	if (i->etype == EXPR_RANGE) {
		const struct expr *e;

		if (i->flags & EXPR_F_INTERVAL_END)
			e = i->right;
		else
			e = i->left;

		return netlink_export_pad(data, e->value, e);
	}

	if (i->etype == EXPR_PREFIX) {
		if (i->flags & EXPR_F_INTERVAL_END) {
			int count;
			mpz_t v;

			mpz_init_bitmask(v, i->len - i->prefix_len);
			mpz_add(v, i->prefix->value, v);
			count = netlink_export_pad(data, v, i);
			mpz_clear(v);
			return count;
		}
Quoted 7 lines
		return netlink_export_pad(data, i->prefix->value, i);
	}

	assert(i->etype == EXPR_VALUE);

	return netlink_export_pad(data, i->value, i);
}  

I would even:

| static int
| netlink_gen_concat_data_expr(const struct expr *i, unsigned char *data)
| {
| 	mpz_t *valp = NULL;
| 
| 	switch (i->etype) {
| 	case EXPR_RANGE:
| 		i = (i->flags & EXPR_F_INTERVAL_END) ? i->right : i->left;
| 		break;
| 	case EXPR_PREFIX:
| 		if (i->flags & EXPR_F_INTERVAL_END) {
| 			int count;
| 			mpz_t v;
| 
| 			mpz_init_bitmask(v, i->len - i->prefix_len);
| 			mpz_add(v, i->prefix->value, v);
| 			count = netlink_export_pad(data, v, i);
| 			mpz_clear(v);
| 			return count;
| 		}
| 		valp = &i->prefix->value;
| 		break;
| 	case EXPR_VALUE:
| 		break;
| 	default:
| 		BUG("invalid expression type '%s' in set", expr_ops(i)->name);
| 	}
| 
| 	return netlink_export_pad(data, valp ? *valp : i->value, i);
| }
Quoted 1 line

But that's up to you. :)

I think it's nicer with a switch and that BUG() is more helpful than a random assert, but I personally find that ternary condition on valp a bit difficult to follow.

I'd recycle most of your function without that -- it's actually shorter and still makes it clear enough what gets fed to netlink_export_pad().

Oh, and by the way, at this point we need to check flags on the 'key' expression.

Quoted 23 lines
Quoted 15 lines

static void netlink_gen_concat_data(const struct expr *expr,
struct nft_data_linearize *nld)

{
	unsigned int len = expr->len / BITS_PER_BYTE, offset = 0;
	unsigned char data[len];
	const struct expr *i;

	memset(data, 0, len);

	list_for_each_entry(i, &expr->expressions, list)
		offset += netlink_gen_concat_data_expr(i, data + offset);

	memcpy(nld->value, data, len);
	nld->len = len;
}
Quoted 3 lines

--

Is that better?

Looks great, thanks!

[...]

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

So this is the fifth copy of the same piece of code. :(

Isn't there a better way to solve that?

I couldn't think of any.

I guess we would need an intermediate state which is 'multiton_rhs_expr DOT multiton_rhs_expr'. Might turn into a mess as well. :)

I just tried to add that, and kept losing myself in the middle of it. It might be me, but it doesn't sound that promising when it comes to readability later.

I guess we already have enough levels of indirection here -- I'd just go with the compound_expr_alloc_or_add() you suggested.

Quoted 10 lines
Quoted 10 lines
Quoted 10 lines

Intuitively, I would just:

| int tmp = len;
| while (start != end && !(start & 1) && (end & 1) && tmp) {
|	start >>= 1;
|	end >>= 1;
|	tmp--;
| }
| return (tmp && start == end) ? len - tmp : -1;
Quoted 5 lines
Quoted 5 lines
Quoted 1 line

Is that slow when dealing with gmp?

I don't think so, it also avoid copies and allocations, while shifting and setting bits have comparable complexities. I'd go with the gmp version of this.

Actually, I need to preserve the original elements, so the two copies are needed anyway -- other than that, I basically recycled your function.

Signature · 1 line
Stefano
reviewer
#7 lore raw

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

Hi,

Quoted 80 lines · Stefano Brivio
Quoted 77 lines · On Wed, 20 Nov 2019 13:53:08 +0100 Phil Sutter <[email protected]> wrote:
Quoted 2 lines · Stefano Brivio

On Tue, 19 Nov 2019 23:12:38 +0100
Phil Sutter <[email protected]> wrote:

[...]

Quoted 30 lines

So, the whole thing would look like (together with the other change you suggest):

--
static int netlink_gen_concat_data_expr(const struct expr *i,
unsigned char *data)

{
	if (i->etype == EXPR_RANGE) {
		const struct expr *e;

		if (i->flags & EXPR_F_INTERVAL_END)
			e = i->right;
		else
			e = i->left;

		return netlink_export_pad(data, e->value, e);
	}

	if (i->etype == EXPR_PREFIX) {
		if (i->flags & EXPR_F_INTERVAL_END) {
			int count;
			mpz_t v;

			mpz_init_bitmask(v, i->len - i->prefix_len);
			mpz_add(v, i->prefix->value, v);
			count = netlink_export_pad(data, v, i);
			mpz_clear(v);
			return count;
		}
Quoted 7 lines
		return netlink_export_pad(data, i->prefix->value, i);
	}

	assert(i->etype == EXPR_VALUE);

	return netlink_export_pad(data, i->value, i);
}  

I would even:

| static int
| netlink_gen_concat_data_expr(const struct expr *i, unsigned char *data)
| {
| 	mpz_t *valp = NULL;
| 
| 	switch (i->etype) {
| 	case EXPR_RANGE:
| 		i = (i->flags & EXPR_F_INTERVAL_END) ? i->right : i->left;
| 		break;
| 	case EXPR_PREFIX:
| 		if (i->flags & EXPR_F_INTERVAL_END) {
| 			int count;
| 			mpz_t v;
| 
| 			mpz_init_bitmask(v, i->len - i->prefix_len);
| 			mpz_add(v, i->prefix->value, v);
| 			count = netlink_export_pad(data, v, i);
| 			mpz_clear(v);
| 			return count;
| 		}
| 		valp = &i->prefix->value;
| 		break;
| 	case EXPR_VALUE:
| 		break;
| 	default:
| 		BUG("invalid expression type '%s' in set", expr_ops(i)->name);
| 	}
| 
| 	return netlink_export_pad(data, valp ? *valp : i->value, i);
| }
Quoted 5 lines
Quoted 1 line

But that's up to you. :)

I think it's nicer with a switch and that BUG() is more helpful than a random assert, but I personally find that ternary condition on valp a bit difficult to follow.

Yes, I overdid it a bit there trying to have a single call to netlink_export_pad(). You found a good middle-ground!

[...]

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines

So this is the fifth copy of the same piece of code. :(

Isn't there a better way to solve that?

Quoted 8 lines
Quoted 4 lines
Quoted 1 line

I couldn't think of any.

I guess we would need an intermediate state which is 'multiton_rhs_expr DOT multiton_rhs_expr'. Might turn into a mess as well. :)

I just tried to add that, and kept losing myself in the middle of it. It might be me, but it doesn't sound that promising when it comes to readability later.

I suspected that already. :)

Quoted 15 lines

I guess we already have enough levels of indirection here -- I'd just go with the compound_expr_alloc_or_add() you suggested.

Quoted 12 lines
Quoted 12 lines
Quoted 11 lines

Intuitively, I would just:

| int tmp = len;
| while (start != end && !(start & 1) && (end & 1) && tmp) {
|	start >>= 1;
|	end >>= 1;
|	tmp--;
| }
| return (tmp && start == end) ? len - tmp : -1;

Is that slow when dealing with gmp?

Quoted 7 lines
Quoted 3 lines
Quoted 3 lines

I don't think so, it also avoid copies and allocations, while shifting and setting bits have comparable complexities. I'd go with the gmp version of this.

Actually, I need to preserve the original elements, so the two copies are needed anyway -- other than that, I basically recycled your function.

*Obviously* my algorithm assumed pass-by-value. ;)

Thanks, Phil

#8 lore raw

PATCH 3/3 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 they can be fetched by matching values in the given ranges.

---
 .../testcases/sets/0038concatenated_ranges_0  | 162 ++++++++++++++++++
 1 file changed, 162 insertions(+)
 create mode 100755 tests/shell/testcases/sets/0038concatenated_ranges_0
tests/shell/testcases/sets/0038concatenated_ranges_0 new file +162 -0
new file mode 100755
index 00000000..7dfab83e
@@ -0,0 +1,162 @@
+#!/bin/sh -e
+#
+# 0038concatenated_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 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::-2001:db8:dada:da:ffff:ffff:ffff:ffff"
+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.23.0