src: support for nat with interval concatenation

This patch allows you to combine concatenation and interval in NAT
mappings, e.g.

 add rule x y dnat to ip saddr . tcp dport map { 192.168.1.2 . 80 : 10.141.10.2-10.141.10.5 . 8888-8999 }

This generates the following NAT expression:

 [ nat dnat ip addr_min reg 1 addr_max reg 10 proto_min reg 9 proto_max reg 11 ]

which expects to obtain the following tuple:

 IP address (min), source port (min), IP address (max), source port (max)

to be obtained from the map. This representation simplifies the
delinearize path, since the datatype is specified as:

 ipv4_addr . inet_service.

A few more notes on this update:

- alloc_nftnl_setelem() needs a variant netlink_gen_data() to deal with
  the representation of the range on the rhs of the mapping. In contrast
  to interval concatenation in the key side, where the range is expressed
  as two netlink attributes, the data side of the set element mapping
  stores the interval concatenation in a contiguos memory area, see
  __netlink_gen_concat_expand() for reference.

- add range_expr_postprocess() to postprocess the data mapping range.
  If either one single IP address or port is used, then the minimum and
  maximum value in the range is the same value, e.g. to avoid listing
  80-80, this round simplify the range. This also invokes the range
  to prefix conversion routine.

- add concat_elem_expr() helper function to consolidate code to build
  the concatenation expression on the rhs element data side.

This patch also adds tests/py and tests/shell.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

4 files changed, 201 insertions, 40 deletions

diff --git a/src/evaluate.c b/src/evaluate.c
index 7d59e260..0ea57b0c 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1605,6 +1605,26 @@ static int expr_evaluate_map(struct eval_ctx *ctx, struct expr **expr)
 	return 0;
 }
 
+static bool data_mapping_has_interval(struct expr *data)
+{
+	struct expr *i;
+
+	if (data->etype == EXPR_RANGE ||
+	    data->etype == EXPR_PREFIX)
+		return true;
+
+	if (data->etype != EXPR_CONCAT)
+		return false;
+
+	list_for_each_entry(i, &data->expressions, list) {
+		if (i->etype == EXPR_RANGE ||
+		    i->etype == EXPR_PREFIX)
+			return true;
+	}
+
+	return false;
+}
+
 static int expr_evaluate_mapping(struct eval_ctx *ctx, struct expr **expr)
 {
 	struct expr *mapping = *expr;
@@ -1644,8 +1664,7 @@ static int expr_evaluate_mapping(struct eval_ctx *ctx, struct expr **expr)
 				  "Value must be a constant");
 
 	if (set_is_anonymous(set->flags) &&
-	    (mapping->right->etype == EXPR_RANGE ||
-	     mapping->right->etype == EXPR_PREFIX))
+	    data_mapping_has_interval(mapping->right))
 		set->data->flags |= EXPR_F_INTERVAL;
 
 	if (!(set->data->flags & EXPR_F_INTERVAL) &&
@@ -3140,6 +3159,9 @@ static int stmt_evaluate_nat_map(struct eval_ctx *ctx, struct stmt *stmt)
 		return 0;
 
 	data = stmt->nat.addr->mappings->set->data;
+	if (data->flags & EXPR_F_INTERVAL)
+		stmt->nat.type_flags |= STMT_NAT_F_INTERVAL;
+
 	datatype_set(data, dtype);
 
 	if (expr_ops(data)->type != EXPR_CONCAT)
@@ -3903,13 +3925,13 @@ static int set_evaluate(struct eval_ctx *ctx, struct set *set)
 			return set_error(ctx, set, "map definition does not "
 					 "specify mapping data type");
 
-		if (set->data->flags & EXPR_F_INTERVAL)
-			set->data->len *= 2;
-
 		if (set->data->etype == EXPR_CONCAT &&
 		    set_expr_evaluate_concat(ctx, &set->data) < 0)
 			return -1;
 
+		if (set->data->flags & EXPR_F_INTERVAL)
+			set->data->len *= 2;
+
 		if (set->data->len == 0 && set->data->dtype->type != TYPE_VERDICT)
 			return set_key_data_error(ctx, set,
 						  set->data->dtype, type);
diff --git a/src/netlink.c b/src/netlink.c
index c5fd3804..cbf9d436 100644
--- a/src/netlink.c
+++ b/src/netlink.c
@@ -97,6 +97,9 @@ struct nftnl_expr *alloc_nft_expr(const char *name)
 	return nle;
 }
 
+void __netlink_gen_data(const struct expr *expr,
+			struct nft_data_linearize *data, bool expand);
+
 static struct nftnl_set_elem *alloc_nftnl_setelem(const struct expr *set,
 						  const struct expr *expr)
 {
@@ -130,11 +133,11 @@ static struct nftnl_set_elem *alloc_nftnl_setelem(const struct expr *set,
 	case EXPR_SET_ELEM_CATCHALL:
 		break;
 	default:
-		netlink_gen_data(key, &nld);
+		__netlink_gen_data(key, &nld, false);
 		nftnl_set_elem_set(nlse, NFTNL_SET_ELEM_KEY, &nld.value, nld.len);
 		if (set->set_flags & NFT_SET_INTERVAL && key->field_count > 1) {
 			key->flags |= EXPR_F_INTERVAL_END;
-			netlink_gen_data(key, &nld);
+			__netlink_gen_data(key, &nld, false);
 			key->flags &= ~EXPR_F_INTERVAL_END;
 
 			nftnl_set_elem_set(nlse, NFTNL_SET_ELEM_KEY_END,
@@ -185,7 +188,7 @@ static struct nftnl_set_elem *alloc_nftnl_setelem(const struct expr *set,
 		nftnl_udata_buf_free(udbuf);
 	}
 	if (set_is_datamap(set->set_flags) && data != NULL) {
-		netlink_gen_data(data, &nld);
+		__netlink_gen_data(data, &nld, !(data->flags & EXPR_F_SINGLETON));
 		switch (data->etype) {
 		case EXPR_VERDICT:
 			nftnl_set_elem_set_u32(nlse, NFTNL_SET_ELEM_VERDICT,
@@ -270,8 +273,8 @@ static int netlink_gen_concat_data_expr(int end, const struct expr *i,
 	return netlink_export_pad(data, i->value, i);
 }
 
-static void netlink_gen_concat_data(const struct expr *expr,
-				    struct nft_data_linearize *nld)
+static void __netlink_gen_concat(const struct expr *expr,
+				 struct nft_data_linearize *nld)
 {
 	unsigned int len = expr->len / BITS_PER_BYTE, offset = 0;
 	int end = expr->flags & EXPR_F_INTERVAL_END;
@@ -287,6 +290,35 @@ static void netlink_gen_concat_data(const struct expr *expr,
 	nld->len = len;
 }
 
+static void __netlink_gen_concat_expand(const struct expr *expr,
+				        struct nft_data_linearize *nld)
+{
+	unsigned int len = div_round_up(expr->len, BITS_PER_BYTE) * 2, 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(false, i, data + offset);
+
+	list_for_each_entry(i, &expr->expressions, list)
+		offset += netlink_gen_concat_data_expr(true, i, data + offset);
+
+	memcpy(nld->value, data, len);
+	nld->len = len;
+}
+
+static void netlink_gen_concat_data(const struct expr *expr,
+				    struct nft_data_linearize *nld,
+				    bool expand)
+{
+	if (expand)
+		__netlink_gen_concat_expand(expr, nld);
+	else
+		__netlink_gen_concat(expr, nld);
+}
+
 static void netlink_gen_constant_data(const struct expr *expr,
 				      struct nft_data_linearize *data)
 {
@@ -366,13 +398,14 @@ static void netlink_gen_prefix(const struct expr *expr,
 	nld->len = len;
 }
 
-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, bool expand)
 {
 	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, expand);
 	case EXPR_VERDICT:
 		return netlink_gen_verdict(expr, data);
 	case EXPR_RANGE:
@@ -384,6 +417,11 @@ 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)
+{
+	__netlink_gen_data(expr, data, false);
+}
+
 struct expr *netlink_alloc_value(const struct location *loc,
 				 const struct nft_data_delinearize *nld)
 {
@@ -1053,10 +1091,28 @@ struct expr *range_expr_to_prefix(struct expr *range)
 	return range;
 }
 
-static struct expr *netlink_parse_interval_elem(const struct datatype *dtype,
+static struct expr *range_expr_reduce(struct expr *range)
+{
+	struct expr *expr;
+
+	if (!mpz_cmp(range->left->value, range->right->value)) {
+		expr = expr_get(range->left);
+		expr_free(range);
+		return expr;
+	}
+
+	if (range->left->dtype->type != TYPE_IPADDR &&
+	    range->left->dtype->type != TYPE_IP6ADDR)
+		return range;
+
+	return range_expr_to_prefix(range);
+}
+
+static struct expr *netlink_parse_interval_elem(const struct set *set,
 						struct expr *expr)
 {
 	unsigned int len = div_round_up(expr->len, BITS_PER_BYTE);
+	const struct datatype *dtype = set->data->dtype;
 	struct expr *range, *left, *right;
 	char data[len];
 
@@ -1073,31 +1129,84 @@ static struct expr *netlink_parse_interval_elem(const struct datatype *dtype,
 	return range_expr_to_prefix(range);
 }
 
-static struct expr *netlink_parse_concat_elem(const struct datatype *dtype,
-					      struct expr *data)
+static struct expr *concat_elem_expr(struct expr *expr,
+				     const struct datatype *dtype,
+				     struct expr *data, int *off)
 {
 	const struct datatype *subtype;
+
+	subtype = concat_subtype_lookup(dtype->type, --(*off));
+
+	expr = constant_expr_splice(data, subtype->size);
+	expr->dtype = subtype;
+	expr->byteorder = subtype->byteorder;
+
+	if (expr->byteorder == BYTEORDER_HOST_ENDIAN)
+		mpz_switch_byteorder(expr->value, expr->len / BITS_PER_BYTE);
+
+	if (expr->dtype->basetype != NULL &&
+	    expr->dtype->basetype->type == TYPE_BITMASK)
+		expr = bitmask_expr_to_binops(expr);
+
+	data->len -= netlink_padding_len(expr->len);
+
+	return expr;
+}
+
+static struct expr *netlink_parse_concat_elem_key(const struct set *set,
+						  struct expr *data)
+{
+	const struct datatype *dtype = set->key->dtype;
 	struct expr *concat, *expr;
 	int off = dtype->subtypes;
 
 	concat = concat_expr_alloc(&data->location);
 	while (off > 0) {
-		subtype = concat_subtype_lookup(dtype->type, --off);
+		expr = concat_elem_expr(expr, dtype, data, &off);
+		compound_expr_add(concat, expr);
+	}
+
+	expr_free(data);
+
+	return concat;
+}
+
+static struct expr *netlink_parse_concat_elem(const struct set *set,
+					      struct expr *data)
+{
+	const struct datatype *dtype = set->data->dtype;
+	struct expr *concat, *expr, *left, *range;
+	struct list_head expressions;
+	int off = dtype->subtypes;
+
+	init_list_head(&expressions);
+
+	concat = concat_expr_alloc(&data->location);
+	while (off > 0) {
+		expr = concat_elem_expr(expr, dtype, data, &off);
+		list_add_tail(&expr->list, &expressions);
+	}
 
-		expr		= constant_expr_splice(data, subtype->size);
-		expr->dtype     = subtype;
-		expr->byteorder = subtype->byteorder;
+	if (set->data->flags & EXPR_F_INTERVAL) {
+		assert(!list_empty(&expressions));
 
-		if (expr->byteorder == BYTEORDER_HOST_ENDIAN)
-			mpz_switch_byteorder(expr->value, expr->len / BITS_PER_BYTE);
+		off = dtype->subtypes;
 
-		if (expr->dtype->basetype != NULL &&
-		    expr->dtype->basetype->type == TYPE_BITMASK)
-			expr = bitmask_expr_to_binops(expr);
+		while (off > 0) {
+			left = list_first_entry(&expressions, struct expr, list);
 
-		compound_expr_add(concat, expr);
-		data->len -= netlink_padding_len(expr->len);
+			expr = concat_elem_expr(expr, dtype, data, &off);
+			list_del(&left->list);
+
+			range = range_expr_alloc(&data->location, left, expr);
+			range = range_expr_reduce(range);
+			compound_expr_add(concat, range);
+		}
+		assert(list_empty(&expressions));
+	} else {
+		list_splice_tail(&expressions, &concat->expressions);
 	}
+
 	expr_free(data);
 
 	return concat;
@@ -1169,7 +1278,7 @@ key_end:
 		datatype_set(key, set->key->dtype);
 		key->byteorder	= set->key->byteorder;
 		if (set->key->dtype->subtypes)
-			key = netlink_parse_concat_elem(set->key->dtype, key);
+			key = netlink_parse_concat_elem_key(set, key);
 
 		if (!(set->flags & NFT_SET_INTERVAL) &&
 		    key->byteorder == BYTEORDER_HOST_ENDIAN)
@@ -1232,10 +1341,10 @@ key_end:
 		datatype_set(data, set->data->dtype);
 		data->byteorder = set->data->byteorder;
 
-		if (set->data->flags & EXPR_F_INTERVAL)
-			data = netlink_parse_interval_elem(set->data->dtype, data);
-		else if (set->data->dtype->subtypes)
-			data = netlink_parse_concat_elem(set->data->dtype, data);
+		if (set->data->dtype->subtypes) {
+			data = netlink_parse_concat_elem(set, data);
+		} else if (set->data->flags & EXPR_F_INTERVAL)
+			data = netlink_parse_interval_elem(set, data);
 
 		if (data->byteorder == BYTEORDER_HOST_ENDIAN)
 			mpz_switch_byteorder(data->value, data->len / BITS_PER_BYTE);
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index a4ae938a..c7dae266 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -1015,7 +1015,8 @@ static void netlink_parse_reject(struct netlink_parse_ctx *ctx,
 	ctx->stmt = stmt;
 }
 
-static bool is_nat_addr_map(const struct expr *addr, uint8_t family)
+static bool is_nat_addr_map(const struct expr *addr, uint8_t family,
+			    struct stmt *stmt)
 {
 	const struct expr *mappings, *data;
 	const struct set *set;
@@ -1034,14 +1035,31 @@ static bool is_nat_addr_map(const struct expr *addr, uint8_t family)
 	if (!(data->flags & EXPR_F_INTERVAL))
 		return false;
 
+	stmt->nat.family = family;
+
 	/* if we're dealing with an address:address map,
 	 * the length will be bit_sizeof(addr) + 32 (one register).
 	 */
 	switch (family) {
 	case NFPROTO_IPV4:
-		return data->len == 32 + 32;
+		if (data->len == 32 + 32) {
+			stmt->nat.type_flags |= STMT_NAT_F_INTERVAL;
+			return true;
+		} else if (data->len == 32 + 32 + 32 + 32) {
+			stmt->nat.type_flags |= STMT_NAT_F_INTERVAL |
+						STMT_NAT_F_CONCAT;
+			return true;
+		}
+		break;
 	case NFPROTO_IPV6:
-		return data->len == 128 + 128;
+		if (data->len == 128 + 128) {
+			stmt->nat.type_flags |= STMT_NAT_F_INTERVAL;
+			return true;
+		} else if (data->len == 128 + 32 + 128 + 32) {
+			stmt->nat.type_flags |= STMT_NAT_F_INTERVAL |
+						STMT_NAT_F_CONCAT;
+			return true;
+		}
 	}
 
 	return false;
@@ -1117,7 +1135,7 @@ static void netlink_parse_nat(struct netlink_parse_ctx *ctx,
 		stmt->nat.addr = addr;
 	}
 
-	if (is_nat_addr_map(addr, family)) {
+	if (is_nat_addr_map(addr, family, stmt)) {
 		stmt->nat.family = family;
 		ctx->stmt = stmt;
 		return;
diff --git a/src/netlink_linearize.c b/src/netlink_linearize.c
index b1f3feee..9ab3ec3e 100644
--- a/src/netlink_linearize.c
+++ b/src/netlink_linearize.c
@@ -1165,11 +1165,14 @@ static void netlink_gen_nat_stmt(struct netlink_linearize_ctx *ctx,
 					     amin_reg);
 			if (stmt->nat.addr->etype == EXPR_MAP &&
 			    stmt->nat.addr->mappings->set->data->flags & EXPR_F_INTERVAL) {
-				amax_reg = get_register(ctx, NULL);
-				registers++;
 				amin_reg += netlink_register_space(nat_addrlen(family));
-				netlink_put_register(nle, NFTNL_EXPR_NAT_REG_ADDR_MAX,
-						     amin_reg);
+				if (stmt->nat.type_flags & STMT_NAT_F_CONCAT) {
+					netlink_put_register(nle, nftnl_reg_pmin,
+							     amin_reg);
+				} else {
+					netlink_put_register(nle, NFTNL_EXPR_NAT_REG_ADDR_MAX,
+							     amin_reg);
+				}
 			}
 		}
 
@@ -1181,6 +1184,12 @@ static void netlink_gen_nat_stmt(struct netlink_linearize_ctx *ctx,
 
 			pmin_reg = amin_reg;
 
+			if (stmt->nat.type_flags & STMT_NAT_F_INTERVAL) {
+				pmin_reg += netlink_register_space(nat_addrlen(family));
+				netlink_put_register(nle, NFTNL_EXPR_NAT_REG_ADDR_MAX,
+						     pmin_reg);
+			}
+
 			/* if STMT_NAT_F_CONCAT is set, the mapped type is a
 			 * concatenation of 'addr . inet_service'.
 			 * The map lookup will then return the
@@ -1189,7 +1198,10 @@ static void netlink_gen_nat_stmt(struct netlink_linearize_ctx *ctx,
 			 * will hold the inet_service part.
 			 */
 			pmin_reg += netlink_register_space(nat_addrlen(family));
-			netlink_put_register(nle, nftnl_reg_pmin, pmin_reg);
+			if (stmt->nat.type_flags & STMT_NAT_F_INTERVAL)
+				netlink_put_register(nle, nftnl_reg_pmax, pmin_reg);
+			else
+				netlink_put_register(nle, nftnl_reg_pmin, pmin_reg);
 		}
 	}