[PATCH 0/6] nftables: support concat types in sets

[PATCH 0/6] nftables: support concat types in sets

[Patrick McHardy]

This patchset is a first step to implement full concatenation support.
It adds support to specify concat types in set declarations and to
reconstruct the proper type from the data stored in the kernel.

The changes consist of:

 * generate proper names for the concat types for use in error reporting
 * don't use ->size to store the number of subtypes, the size will be
   needed to hold the entire concatenated data size, which may include
   padding
 * change concat_type_alloc() to construct the type from the numeric id
 * change the grammar to support concat type specification

The next step will be to change register addressing to 4 byte register
size and support loads and stores to spawn multiple registers. Patches
for this will follow shorly.


Patrick McHardy (6):
      datatype: generate name for concat types
      datatype: add new subtypes field to account number of concat data types
      datatype: add define for maximum number of bits and mask of datatype id
      utils: add fls()
      datatype: change concat_type_alloc() to construct type from id
      parser: alloc specifying concat types in set declarations

 include/datatype.h |  7 +++++-
 include/utils.h    | 37 ++++++++++++++++++++++++++++++++
 src/datatype.c     | 30 ++++++++++++++++++--------
 src/evaluate.c     | 11 ++++++----
 src/netlink.c      |  2 ++
 src/parser_bison.y | 63 +++++++++++++++++++++++++++++++++++-------------------
 6 files changed, 114 insertions(+), 36 deletions(-)

[PATCH 1/6] datatype: generate name for concat types

[Patrick McHardy]

The name of a concat type is the names of the individual types concatenated
using a '.'.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 src/datatype.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/src/datatype.c b/src/datatype.c
index 4519d87..29c967b 100644
--- a/src/datatype.c
+++ b/src/datatype.c
@@ -927,12 +927,16 @@ const struct datatype *concat_type_alloc(const struct expr *expr)
 	struct datatype *dtype;
 	struct expr *i;
 	char desc[256] = "concatenation of (";
+	char name[256] = "";
 	unsigned int type = 0, size = 0;
 
 	list_for_each_entry(i, &expr->expressions, list) {
-		if (size != 0)
+		if (size != 0) {
 			strncat(desc, ", ", sizeof(desc) - strlen(desc) - 1);
+			strncat(name, " . ", sizeof(name) - strlen(name) - 1);
+		}
 		strncat(desc, i->dtype->desc, sizeof(desc) - strlen(desc) - 1);
+		strncat(name, i->dtype->name, sizeof(name) - strlen(name) - 1);
 
 		type <<= 8;
 		type  |= i->dtype->type;
@@ -943,6 +947,7 @@ const struct datatype *concat_type_alloc(const struct expr *expr)
 	dtype		= dtype_alloc();
 	dtype->type	= type;
 	dtype->size	= size;
+	dtype->name	= xstrdup(name);
 	dtype->desc	= xstrdup(desc);
 	dtype->parse	= concat_type_parse;
 
@@ -952,6 +957,7 @@ const struct datatype *concat_type_alloc(const struct expr *expr)
 void concat_type_destroy(const struct datatype *dtype)
 {
 	if (dtype->flags & DTYPE_F_ALLOC) {
+		xfree(dtype->name);
 		xfree(dtype->desc);
 		xfree(dtype);
 	}
-- 
2.1.0

[PATCH 2/6] datatype: add new subtypes field to account number of concat data types

[Patrick McHardy]

Using the size is confusing since it usually holds the size of
the data. Add a new "subtypes" member, which holds the number
of datatypes the concat type is made of.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/datatype.h | 2 ++
 src/datatype.c     | 8 +++++---
 src/evaluate.c     | 6 ++++--
 3 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/include/datatype.h b/include/datatype.h
index 3f13dcd..50b85c3 100644
--- a/include/datatype.h
+++ b/include/datatype.h
@@ -115,6 +115,7 @@ enum datatype_flags {
  * @byteorder:	byteorder of type (non-basetypes only)
  * @flags:	flags
  * @size:	type size (fixed sized non-basetypes only)
+ * @subtypes:	number of subtypes (concat type)
  * @name:	type name
  * @desc:	type description
  * @basetype:	basetype for subtypes, determines type compatibilty
@@ -128,6 +129,7 @@ struct datatype {
 	enum byteorder			byteorder;
 	unsigned int			flags;
 	unsigned int			size;
+	unsigned int			subtypes;
 	const char			*name;
 	const char			*desc;
 	const struct datatype		*basetype;
diff --git a/src/datatype.c b/src/datatype.c
index 29c967b..7fc3287 100644
--- a/src/datatype.c
+++ b/src/datatype.c
@@ -928,10 +928,10 @@ const struct datatype *concat_type_alloc(const struct expr *expr)
 	struct expr *i;
 	char desc[256] = "concatenation of (";
 	char name[256] = "";
-	unsigned int type = 0, size = 0;
+	unsigned int type = 0, size = 0, subtypes = 0;
 
 	list_for_each_entry(i, &expr->expressions, list) {
-		if (size != 0) {
+		if (subtypes != 0) {
 			strncat(desc, ", ", sizeof(desc) - strlen(desc) - 1);
 			strncat(name, " . ", sizeof(name) - strlen(name) - 1);
 		}
@@ -940,13 +940,15 @@ const struct datatype *concat_type_alloc(const struct expr *expr)
 
 		type <<= 8;
 		type  |= i->dtype->type;
-		size++;
+		size  += i->dtype->size;
+		subtypes++;
 	}
 	strncat(desc, ")", sizeof(desc) - strlen(desc) - 1);
 
 	dtype		= dtype_alloc();
 	dtype->type	= type;
 	dtype->size	= size;
+	dtype->subtypes = subtypes;
 	dtype->name	= xstrdup(name);
 	dtype->desc	= xstrdup(desc);
 	dtype->parse	= concat_type_parse;
diff --git a/src/evaluate.c b/src/evaluate.c
index 0732660..79edf02 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -605,10 +605,10 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
 {
 	const struct datatype *dtype = ctx->ectx.dtype, *tmp;
 	unsigned int type = dtype ? dtype->type : 0;
-	int off = dtype ? dtype->size: 0;
+	int off = dtype ? dtype->subtypes : 0;
 	unsigned int flags = EXPR_F_CONSTANT | EXPR_F_SINGLETON;
 	struct expr *i, *next;
-	unsigned int n;
+	unsigned int n, len = 0;
 
 	n = 1;
 	list_for_each_entry_safe(i, next, &(*expr)->expressions, list) {
@@ -624,11 +624,13 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
 			return -1;
 		flags &= i->flags;
 
+		len += i->len;
 		n++;
 	}
 
 	(*expr)->flags |= flags;
 	(*expr)->dtype = concat_type_alloc(*expr);
+	(*expr)->len   = len;
 
 	if (off > 0)
 		return expr_error(ctx->msgs, *expr,
-- 
2.1.0

[PATCH 3/6] datatype: add define for maximum number of bits and mask of datatype id

[Patrick McHardy]

The id of concat datatypes is composed of the ids of the individual
datatypes. Add a define for the number of bits for each datatype id
and a mask.

The number of bits is chosen as 6, allowing for 63 datatypes, or twice
as much as we currently have. This allows for concatenations of 5
types using 32 bits.

The value is statically chosen instead of basing it on the current
numbers of datatypes since we don't want the maximum concatenation
size to vary between versions, also new versions are supposed to be
able to propery parse a ruleset generated by an older version.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/datatype.h | 3 +++
 src/datatype.c     | 3 ++-
 src/evaluate.c     | 2 +-
 3 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/include/datatype.h b/include/datatype.h
index 50b85c3..ca6ba9f 100644
--- a/include/datatype.h
+++ b/include/datatype.h
@@ -82,6 +82,9 @@ enum datatypes {
 };
 #define TYPE_MAX		(__TYPE_MAX - 1)
 
+#define TYPE_BITS		6
+#define TYPE_MASK		((1 << TYPE_BITS) - 1)
+
 /**
  * enum byteorder
  *
diff --git a/src/datatype.c b/src/datatype.c
index 7fc3287..b63d96d 100644
--- a/src/datatype.c
+++ b/src/datatype.c
@@ -51,6 +51,7 @@ static const struct datatype *datatypes[TYPE_MAX + 1] = {
 
 void datatype_register(const struct datatype *dtype)
 {
+	BUILD_BUG_ON(TYPE_MAX & ~TYPE_MASK);
 	datatypes[dtype->type] = dtype;
 }
 
@@ -938,7 +939,7 @@ const struct datatype *concat_type_alloc(const struct expr *expr)
 		strncat(desc, i->dtype->desc, sizeof(desc) - strlen(desc) - 1);
 		strncat(name, i->dtype->name, sizeof(name) - strlen(name) - 1);
 
-		type <<= 8;
+		type <<= TYPE_BITS;
 		type  |= i->dtype->type;
 		size  += i->dtype->size;
 		subtypes++;
diff --git a/src/evaluate.c b/src/evaluate.c
index 79edf02..9cb2376 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -617,7 +617,7 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
 						 "unexpected concat component, "
 						 "expecting %s",
 						 dtype->desc);
-		tmp = datatype_lookup((type >> 8 * --off) & 0xff);
+		tmp = datatype_lookup((type >> TYPE_BITS * --off) & TYPE_MASK);
 		expr_set_context(&ctx->ectx, tmp, tmp->size);
 
 		if (list_member_evaluate(ctx, &i) < 0)
-- 
2.1.0

[PATCH 4/6] utils: add fls()

[Patrick McHardy]

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/utils.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/include/utils.h b/include/utils.h
index 15b2e39..45cb5a7 100644
--- a/include/utils.h
+++ b/include/utils.h
@@ -76,6 +76,43 @@
 	(void) (&_max1 == &_max2);		\
 	_max1 > _max2 ? _max1 : _max2; })
 
+
+/**
+ * fls - find last (most-significant) bit set
+ * @x: the word to search
+ *
+ * This is defined the same way as ffs.
+ * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
+ */
+static inline int fls(int x)
+{
+	int r = 32;
+
+	if (!x)
+		return 0;
+	if (!(x & 0xffff0000u)) {
+		x <<= 16;
+		r -= 16;
+	}
+	if (!(x & 0xff000000u)) {
+		x <<= 8;
+		r -= 8;
+	}
+	if (!(x & 0xf0000000u)) {
+		x <<= 4;
+		r -= 4;
+	}
+	if (!(x & 0xc0000000u)) {
+		x <<= 2;
+		r -= 2;
+	}
+	if (!(x & 0x80000000u)) {
+		x <<= 1;
+		r -= 1;
+	}
+	return r;
+}
+
 extern void __memory_allocation_error(const char *filename, uint32_t line) __noreturn;
 
 #define memory_allocation_error()		\
-- 
2.1.0

[PATCH 5/6] datatype: change concat_type_alloc() to construct type from id

[Patrick McHardy]

The kernel only stored the id so we need to be able to reconstruct
the datatype from the id only.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/datatype.h |  2 +-
 src/datatype.c     | 21 ++++++++++++---------
 src/evaluate.c     | 11 ++++++-----
 3 files changed, 19 insertions(+), 15 deletions(-)

diff --git a/include/datatype.h b/include/datatype.h
index ca6ba9f..f05f987 100644
--- a/include/datatype.h
+++ b/include/datatype.h
@@ -212,7 +212,7 @@ extern const struct datatype icmpv6_code_type;
 extern const struct datatype icmpx_code_type;
 extern const struct datatype time_type;
 
-extern const struct datatype *concat_type_alloc(const struct expr *expr);
+extern const struct datatype *concat_type_alloc(uint32_t type);
 extern void concat_type_destroy(const struct datatype *dtype);
 
 #endif /* NFTABLES_DATATYPE_H */
diff --git a/src/datatype.c b/src/datatype.c
index b63d96d..cfb63b7 100644
--- a/src/datatype.c
+++ b/src/datatype.c
@@ -923,25 +923,28 @@ static struct datatype *dtype_alloc(void)
 	return dtype;
 }
 
-const struct datatype *concat_type_alloc(const struct expr *expr)
+const struct datatype *concat_type_alloc(uint32_t type)
 {
+	const struct datatype *i;
 	struct datatype *dtype;
-	struct expr *i;
 	char desc[256] = "concatenation of (";
 	char name[256] = "";
-	unsigned int type = 0, size = 0, subtypes = 0;
+	unsigned int size = 0, subtypes = 0, n;
+
+	n = div_round_up(fls(type), TYPE_BITS);
+	while ((type >> TYPE_BITS * --n) & TYPE_MASK) {
+		i = datatype_lookup((type >> TYPE_BITS * n) & TYPE_MASK);
+		if (i == NULL)
+			return NULL;
 
-	list_for_each_entry(i, &expr->expressions, list) {
 		if (subtypes != 0) {
 			strncat(desc, ", ", sizeof(desc) - strlen(desc) - 1);
 			strncat(name, " . ", sizeof(name) - strlen(name) - 1);
 		}
-		strncat(desc, i->dtype->desc, sizeof(desc) - strlen(desc) - 1);
-		strncat(name, i->dtype->name, sizeof(name) - strlen(name) - 1);
+		strncat(desc, i->desc, sizeof(desc) - strlen(desc) - 1);
+		strncat(name, i->name, sizeof(name) - strlen(name) - 1);
 
-		type <<= TYPE_BITS;
-		type  |= i->dtype->type;
-		size  += i->dtype->size;
+		size += i->size;
 		subtypes++;
 	}
 	strncat(desc, ")", sizeof(desc) - strlen(desc) - 1);
diff --git a/src/evaluate.c b/src/evaluate.c
index 9cb2376..8f0acf7 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -604,11 +604,11 @@ static int list_member_evaluate(struct eval_ctx *ctx, struct expr **expr)
 static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
 {
 	const struct datatype *dtype = ctx->ectx.dtype, *tmp;
-	unsigned int type = dtype ? dtype->type : 0;
+	uint32_t type = dtype ? dtype->type : 0, ntype = 0;
 	int off = dtype ? dtype->subtypes : 0;
 	unsigned int flags = EXPR_F_CONSTANT | EXPR_F_SINGLETON;
 	struct expr *i, *next;
-	unsigned int n, len = 0;
+	unsigned int n;
 
 	n = 1;
 	list_for_each_entry_safe(i, next, &(*expr)->expressions, list) {
@@ -624,13 +624,14 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
 			return -1;
 		flags &= i->flags;
 
-		len += i->len;
+		ntype <<= TYPE_BITS;
+		ntype  |= i->dtype->type;
 		n++;
 	}
 
 	(*expr)->flags |= flags;
-	(*expr)->dtype = concat_type_alloc(*expr);
-	(*expr)->len   = len;
+	(*expr)->dtype = concat_type_alloc(ntype);
+	(*expr)->len   = (*expr)->dtype->size;
 
 	if (off > 0)
 		return expr_error(ctx->msgs, *expr,
-- 
2.1.0

[PATCH 6/6] parser: alloc specifying concat types in set declarations

[Patrick McHardy]

Support specification of concat types in set declarations:

add set filter test {
	type ipv4_addr . inet_service
}

Netlink delinearization is changed to reconstruct the type from the id.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 src/netlink.c      |  2 ++
 src/parser_bison.y | 63 +++++++++++++++++++++++++++++++++++-------------------
 2 files changed, 43 insertions(+), 22 deletions(-)

diff --git a/src/netlink.c b/src/netlink.c
index e59e297..feaea19 100644
--- a/src/netlink.c
+++ b/src/netlink.c
@@ -986,6 +986,8 @@ static const struct datatype *dtype_map_from_kernel(enum nft_data_types type)
 	case NFT_DATA_VERDICT:
 		return &verdict_type;
 	default:
+		if (type & ~TYPE_MASK)
+			return concat_type_alloc(type);
 		return datatype_lookup(type);
 	}
 }
diff --git a/src/parser_bison.y b/src/parser_bison.y
index 515a11a..c6d9104 100644
--- a/src/parser_bison.y
+++ b/src/parser_bison.y
@@ -132,6 +132,7 @@ static void location_update(struct location *loc, struct location *rhs, int n)
 	struct stmt		*stmt;
 	struct expr		*expr;
 	struct set		*set;
+	const struct datatype	*datatype;
 }
 
 %token TOKEN_EOF 0		"end of file"
@@ -395,6 +396,9 @@ static void location_update(struct location *loc, struct location *rhs, int n)
 %type <string>			identifier string comment_spec
 %destructor { xfree($$); }	identifier string comment_spec
 
+%type <val>			type_identifier
+%type <datatype>		data_type
+
 %type <cmd>			line
 %destructor { cmd_free($$); }	line
 
@@ -914,14 +918,9 @@ set_block_alloc		:	/* empty */
 set_block		:	/* empty */	{ $$ = $<set>-1; }
 			|	set_block	common_block
 			|	set_block	stmt_seperator
-			|	set_block	TYPE		identifier	stmt_seperator
+			|	set_block	TYPE		data_type	stmt_seperator
 			{
-				$1->keytype = datatype_lookup_byname($3);
-				if ($1->keytype == NULL) {
-					erec_queue(error(&@3, "unknown datatype %s", $3),
-						   state->msgs);
-					YYERROR;
-				}
+				$1->keytype = $3;
 				$$ = $1;
 			}
 			|	set_block	FLAGS		set_flag_list	stmt_seperator
@@ -959,23 +958,11 @@ map_block		:	/* empty */	{ $$ = $<set>-1; }
 			|	map_block	common_block
 			|	map_block	stmt_seperator
 			|	map_block	TYPE
-						identifier	COLON	identifier
+						data_type	COLON	data_type
 						stmt_seperator
 			{
-				$1->keytype = datatype_lookup_byname($3);
-				if ($1->keytype == NULL) {
-					erec_queue(error(&@3, "unknown datatype %s", $3),
-						   state->msgs);
-					YYERROR;
-				}
-
-				$1->datatype = datatype_lookup_byname($5);
-				if ($1->datatype == NULL) {
-					erec_queue(error(&@5, "unknown datatype %s", $5),
-						   state->msgs);
-					YYERROR;
-				}
-
+				$1->keytype  = $3;
+				$1->datatype = $5;
 				$$ = $1;
 			}
 			|	map_block	FLAGS		set_flag_list	stmt_seperator
@@ -1005,6 +992,38 @@ set_policy_spec		:	PERFORMANCE	{ $$ = NFT_SET_POL_PERFORMANCE; }
 			|	MEMORY		{ $$ = NFT_SET_POL_MEMORY; }
 			;
 
+data_type		:	type_identifier
+			{
+				if ($1 & ~TYPE_MASK)
+					$$ = concat_type_alloc($1);
+				else
+					$$ = datatype_lookup($1);
+			}
+			;
+
+type_identifier		:	identifier
+			{
+				const struct datatype *dtype = datatype_lookup_byname($1);
+				if (dtype == NULL) {
+					erec_queue(error(&@1, "unknown datatype %s", $1),
+						   state->msgs);
+					YYERROR;
+				}
+				$$ = dtype->type;
+			}
+			|	type_identifier	DOT		identifier
+			{
+				const struct datatype *dtype = datatype_lookup_byname($3);
+				if (dtype == NULL) {
+					erec_queue(error(&@3, "unknown datatype %s", $3),
+						   state->msgs);
+					YYERROR;
+				}
+				$$ <<= TYPE_BITS;
+				$$ |= dtype->type;
+			}
+			;
+
 hook_spec		:	TYPE		STRING		HOOK		STRING		PRIORITY	NUM
 			{
 				$<chain>0->type		= chain_type_name_lookup($2);
-- 
2.1.0