[PATCH nft 1/7,v2] tests: vlan pcp and cfi are located in the first byte

[PATCH nft 1/7,v2] tests: vlan pcp and cfi are located in the first byte

[Pablo Neira Ayuso]

Adjust tests to fix wrong payloads, both pcp and cfi are located in the
first nibble of the first byte.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
v2: Fix vlan test for simple ranges too.

 tests/regression/bridge/vlan.t.payload | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

diff --git a/tests/regression/bridge/vlan.t.payload b/tests/regression/bridge/vlan.t.payload
index 35dc437..78ee7ef 100644
--- a/tests/regression/bridge/vlan.t.payload
+++ b/tests/regression/bridge/vlan.t.payload
@@ -21,7 +21,7 @@ bridge test-bridge input
   [ payload load 2b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x0000ff0f ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x0000fe0f ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x00000010 ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x00000000 ]
 
@@ -32,7 +32,7 @@ bridge test-bridge input
   [ payload load 2b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x0000ff0f ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x0000fe0f ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x00000010 ) ^ 0x00000000 ]
   [ cmp neq reg 1 0x00000010 ]
 
@@ -43,7 +43,7 @@ bridge test-bridge input
   [ payload load 2b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x0000ff0f ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x0000fe0f ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x00000010 ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x00000010 ]
 
@@ -70,7 +70,7 @@ bridge test-bridge input
   [ payload load 2b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x0000ff0f ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x0000fe0f ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x00000010 ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x00000000 ]
 
@@ -81,7 +81,7 @@ bridge test-bridge input
   [ payload load 2b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x0000ff0f ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x0000fe0f ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x00000010 ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x00000010 ]
 
@@ -163,10 +163,10 @@ bridge test-bridge input
   [ payload load 2b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x0000ff0f ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x0000fe0f ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x00000010 ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x00000010 ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x000000e0 ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x000000e0 ]
 
@@ -177,10 +177,10 @@ bridge test-bridge input
   [ payload load 2b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x0000ff0f ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x0000fe0f ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x00000010 ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x00000010 ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x000000e0 ) ^ 0x00000000 ]
   [ cmp eq reg 1 0x00000060 ]
 
@@ -194,8 +194,8 @@ bridge test-bridge input
   [ payload load 2b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x0000ff0f ) ^ 0x00000000 ]
   [ lookup reg 1 set set%d ]
-  [ payload load 1b @ link header + 15 => reg 1 ]
+  [ payload load 1b @ link header + 14 => reg 1 ]
   [ bitwise reg 1 = (reg=1 & 0x000000e0 ) ^ 0x00000000 ]
-  [ cmp gte reg 1 0x00000001 ]
-  [ cmp lte reg 1 0x00000003 ]
+  [ cmp gte reg 1 0x00000020 ]
+  [ cmp lte reg 1 0x00000060 ]
 
-- 
2.1.4

[PATCH nft 2/7,v2] src: fix sub-byte protocol header definitions

[Pablo Neira Ayuso]

Update bitfield definitions to match according to the way they are
expressed in RFC and IEEE specifications.

This required a bit of update for c3f0501 ("src: netlink_linearize:
handle sub-byte lengths").

>From the linearize step, to calculate the shift based on the bitfield
offset, we need to obtain the length of the word in bytes:

	len = round_up(expr->len, BITS_PER_BYTE);

Then, we substract the offset bits and the bitfield length.

        shift = len - (offset + expr->len);

>From the delinearize, payload_expr_trim() needs to obtain the real
offset through:

	off = round_up(mask->len, BITS_PER_BYTE) - mask_len;

For vlan id (offset 12), this gets the position of the last bit set in
the mask (ie. 12), then we substract the length we fetch in bytes (16),
so we obtain the real bitfield offset (4).

Then, we add that to the original payload offset that was expressed in
bytes:

	payload_offset += off;

Note that payload_expr_trim() now also adjusts the payload expression to
its real length and offset so we don't need to propagate the mask
expression.

Reported-by: Patrick McHardy <kaber@trash.net>>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
v2: Get rid of payload_expr_expand() change.
    Fully adjust payload expression for payload_trim_expr()
    Use mask_length() instead of mpz_fls()

 include/payload.h         |  3 +--
 include/proto.h           |  4 ++--
 include/utils.h           |  1 +
 src/netlink_delinearize.c | 23 ++++++++++-------------
 src/netlink_linearize.c   | 35 ++++++++++++++++++++++-------------
 src/payload.c             | 32 ++++++++++++++++++--------------
 src/proto.c               | 17 +++++++++--------
 7 files changed, 63 insertions(+), 52 deletions(-)

diff --git a/include/payload.h b/include/payload.h
index ca9b013..9192d6e 100644
--- a/include/payload.h
+++ b/include/payload.h
@@ -20,9 +20,8 @@ extern struct expr *payload_expr_join(const struct expr *e1,
 				      const struct expr *e2);
 
 bool payload_expr_trim(struct expr *expr, struct expr *mask,
-		       const struct proto_ctx *ctx);
+		       const struct proto_ctx *ctx, unsigned int *shift);
 extern void payload_expr_expand(struct list_head *list, struct expr *expr,
-				struct expr *mask,
 				const struct proto_ctx *ctx);
 extern void payload_expr_complete(struct expr *expr,
 				  const struct proto_ctx *ctx);
diff --git a/include/proto.h b/include/proto.h
index 974116f..d90bccd 100644
--- a/include/proto.h
+++ b/include/proto.h
@@ -159,9 +159,9 @@ enum eth_hdr_fields {
 
 enum vlan_hdr_fields {
 	VLANHDR_INVALID,
-	VLANHDR_VID,
-	VLANHDR_CFI,
 	VLANHDR_PCP,
+	VLANHDR_CFI,
+	VLANHDR_VID,
 	VLANHDR_TYPE,
 };
 
diff --git a/include/utils.h b/include/utils.h
index e94ae81..8a1dc5e 100644
--- a/include/utils.h
+++ b/include/utils.h
@@ -69,6 +69,7 @@
 #define field_sizeof(t, f)	(sizeof(((t *)NULL)->f))
 #define array_size(arr)		(sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))
 #define div_round_up(n, d)	(((n) + (d) - 1) / (d))
+#define round_up(n, b)		(div_round_up(n, b) * b)
 
 #define min(x, y) ({				\
 	typeof(x) _min1 = (x);			\
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 3e1f912..e5cee16 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -998,8 +998,7 @@ static void integer_type_postprocess(struct expr *expr)
 
 static void payload_match_expand(struct rule_pp_ctx *ctx,
 				 struct expr *expr,
-				 struct expr *payload,
-				 struct expr *mask)
+				 struct expr *payload)
 {
 	struct expr *left = payload, *right = expr->right, *tmp;
 	struct list_head list = LIST_HEAD_INIT(list);
@@ -1008,7 +1007,7 @@ static void payload_match_expand(struct rule_pp_ctx *ctx,
 	enum proto_bases base = left->payload.base;
 	const struct expr_ops *payload_ops = left->ops;
 
-	payload_expr_expand(&list, left, mask, &ctx->pctx);
+	payload_expr_expand(&list, left, &ctx->pctx);
 
 	list_for_each_entry(left, &list, list) {
 		tmp = constant_expr_splice(right, left->len);
@@ -1063,8 +1062,7 @@ static void payload_match_expand(struct rule_pp_ctx *ctx,
 
 static void payload_match_postprocess(struct rule_pp_ctx *ctx,
 				      struct expr *expr,
-				      struct expr *payload,
-				      struct expr *mask)
+				      struct expr *payload)
 {
 	enum proto_bases base = payload->payload.base;
 
@@ -1075,7 +1073,7 @@ static void payload_match_postprocess(struct rule_pp_ctx *ctx,
 	case OP_EQ:
 	case OP_NEQ:
 		if (expr->right->ops->type == EXPR_VALUE) {
-			payload_match_expand(ctx, expr, payload, mask);
+			payload_match_expand(ctx, expr, payload);
 			break;
 		}
 		/* Fall through */
@@ -1190,6 +1188,7 @@ static void relational_binop_postprocess(struct rule_pp_ctx *ctx, struct expr *e
 		   binop->right->ops->type == EXPR_VALUE) {
 		struct expr *payload = binop->left;
 		struct expr *mask = binop->right;
+		unsigned int shift;
 
 		/*
 		 * This *might* be a payload match testing header fields that
@@ -1214,7 +1213,7 @@ static void relational_binop_postprocess(struct rule_pp_ctx *ctx, struct expr *e
 		 * payload_expr_trim will figure out if the mask is needed to match
 		 * templates.
 		 */
-		if (payload_expr_trim(payload, mask, &ctx->pctx)) {
+		if (payload_expr_trim(payload, mask, &ctx->pctx, &shift)) {
 			/* mask is implicit, binop needs to be removed.
 			 *
 			 * Fix all values of the expression according to the mask
@@ -1226,13 +1225,11 @@ static void relational_binop_postprocess(struct rule_pp_ctx *ctx, struct expr *e
 			 */
 			if (value->ops->type == EXPR_VALUE) {
 				assert(value->len >= expr->left->right->len);
-				value->len = mask->len;
+				mpz_rshift_ui(value->value, shift);
+				value->len = payload->len;
 			}
 
-			payload->len = mask->len;
-			payload->payload.offset += mpz_scan1(mask->value, 0);
-
-			payload_match_postprocess(ctx, expr, payload, mask);
+			payload_match_postprocess(ctx, expr, payload);
 
 			assert(expr->left->ops->type == EXPR_BINOP);
 
@@ -1383,7 +1380,7 @@ static void expr_postprocess(struct rule_pp_ctx *ctx, struct expr **exprp)
 	case EXPR_RELATIONAL:
 		switch (expr->left->ops->type) {
 		case EXPR_PAYLOAD:
-			payload_match_postprocess(ctx, expr, expr->left, NULL);
+			payload_match_postprocess(ctx, expr, expr->left);
 			return;
 		default:
 			expr_postprocess(ctx, &expr->left);
diff --git a/src/netlink_linearize.c b/src/netlink_linearize.c
index 0790dce..131c3f9 100644
--- a/src/netlink_linearize.c
+++ b/src/netlink_linearize.c
@@ -103,27 +103,37 @@ static void netlink_gen_concat(struct netlink_linearize_ctx *ctx,
 	}
 }
 
+static unsigned int payload_shift_calc(const struct expr *expr)
+{
+	unsigned int offset, len;
+	int shift;
+
+	offset = expr->payload.offset % BITS_PER_BYTE;
+	len = round_up(expr->len, BITS_PER_BYTE);
+	shift = len - (offset + expr->len);
+	assert(shift >= 0);
+
+	return shift;
+}
+
 static void netlink_gen_payload_mask(struct netlink_linearize_ctx *ctx,
 				     const struct expr *expr,
 				     enum nft_registers dreg)
 {
 	struct nft_data_linearize nld, zero = {};
+	unsigned int shift, len, masklen;
 	struct nftnl_expr *nle;
-	unsigned int offset, len, masklen;
 	mpz_t mask;
 
-	offset = expr->payload.offset % BITS_PER_BYTE;
-	masklen = expr->len + offset;
-
-	if (masklen > 128)
-		BUG("expr mask length is %u (len %u, offset %u)\n",
-				masklen, expr->len, offset);
+	shift = payload_shift_calc(expr);
+	if (!shift && expr->payload.offset % BITS_PER_BYTE == 0)
+		return;
 
+	masklen = expr->len + shift;
+	assert(masklen <= NFT_REG_SIZE * BITS_PER_BYTE);
 	mpz_init2(mask, masklen);
 	mpz_bitmask(mask, expr->len);
-
-	if (offset)
-		mpz_lshift_ui(mask, offset);
+	mpz_lshift_ui(mask, shift);
 
 	nle = alloc_nft_expr("bitwise");
 
@@ -158,8 +168,7 @@ static void netlink_gen_payload(struct netlink_linearize_ctx *ctx,
 
 	nftnl_rule_add_expr(ctx->nlr, nle);
 
-	if (expr->len % BITS_PER_BYTE)
-		netlink_gen_payload_mask(ctx, expr, dreg);
+	netlink_gen_payload_mask(ctx, expr, dreg);
 }
 
 static void netlink_gen_exthdr(struct netlink_linearize_ctx *ctx,
@@ -287,7 +296,7 @@ static void payload_shift_value(const struct expr *left, struct expr *right)
 	    left->ops->type != EXPR_PAYLOAD)
 		return;
 
-	mpz_lshift_ui(right->value, left->payload.offset % BITS_PER_BYTE);
+	mpz_lshift_ui(right->value, payload_shift_calc(left));
 }
 
 static struct expr *netlink_gen_prefix(struct netlink_linearize_ctx *ctx,
diff --git a/src/payload.c b/src/payload.c
index a97041e..fe91ee0 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -339,18 +339,21 @@ static unsigned int mask_length(const struct expr *mask)
  * Walk the template list and determine if a match can be found without
  * using the provided mask.
  *
- * If the mask has to be used, trim the mask length accordingly
- * and return true to let the caller know that the mask is a dependency.
+ * If the mask has to be used, trim the payload expression length accordingly,
+ * adjust the payload offset and return true to let the caller know that the
+ * mask can be removed. This function also returns the shift for the right hand
+ * constant side of the expression.
  */
 bool payload_expr_trim(struct expr *expr, struct expr *mask,
-		       const struct proto_ctx *ctx)
+		       const struct proto_ctx *ctx, unsigned int *shift)
 {
-	unsigned int payload_offset = expr->payload.offset + mask_to_offset(mask);
+	unsigned int payload_offset = expr->payload.offset;
+	unsigned int mask_offset = mask_to_offset(mask);
 	unsigned int mask_len = mask_length(mask);
 	const struct proto_hdr_template *tmpl;
 	unsigned int payload_len = expr->len;
 	const struct proto_desc *desc;
-	unsigned int i, matched_len = mask_to_offset(mask);
+	unsigned int off, i, len = 0;
 
 	assert(expr->ops->type == EXPR_PAYLOAD);
 
@@ -365,6 +368,9 @@ bool payload_expr_trim(struct expr *expr, struct expr *mask,
 		payload_offset -= ctx->protocol[expr->payload.base].offset;
 	}
 
+	off = round_up(mask->len, BITS_PER_BYTE) - mask_len;
+	payload_offset += off;
+
 	for (i = 1; i < array_size(desc->templates); i++) {
 		tmpl = &desc->templates[i];
 		if (tmpl->offset != payload_offset)
@@ -374,14 +380,15 @@ bool payload_expr_trim(struct expr *expr, struct expr *mask,
 			return false;
 
 		payload_len -= tmpl->len;
-		matched_len += tmpl->len;
 		payload_offset += tmpl->len;
+		len += tmpl->len;
 		if (payload_len == 0)
 			return false;
 
-		if (matched_len == mask_len) {
-			assert(mask->len >= mask_len);
-			mask->len = mask_len;
+		if (mask_offset + len == mask_len) {
+			expr->payload.offset += off;
+			expr->len = len;
+			*shift = mask_offset;
 			return true;
 		}
 	}
@@ -395,7 +402,6 @@ bool payload_expr_trim(struct expr *expr, struct expr *mask,
  *
  * @list:	list to append expanded payload expressions to
  * @expr:	the payload expression to expand
- * @mask:	optional/implicit mask to use when searching templates
  * @ctx:	protocol context
  *
  * Expand a merged adjacent payload expression into its original components
@@ -405,16 +411,14 @@ bool payload_expr_trim(struct expr *expr, struct expr *mask,
  * 	 offset order.
  */
 void payload_expr_expand(struct list_head *list, struct expr *expr,
-			 struct expr *mask, const struct proto_ctx *ctx)
+			 const struct proto_ctx *ctx)
 {
-	unsigned int off = mask_to_offset(mask);
 	const struct proto_hdr_template *tmpl;
 	const struct proto_desc *desc;
 	struct expr *new;
 	unsigned int i;
 
 	assert(expr->ops->type == EXPR_PAYLOAD);
-	assert(!mask || mask->len != 0);
 
 	desc = ctx->protocol[expr->payload.base].desc;
 	if (desc == NULL)
@@ -431,7 +435,7 @@ void payload_expr_expand(struct list_head *list, struct expr *expr,
 			list_add_tail(&new->list, list);
 			expr->len	     -= tmpl->len;
 			expr->payload.offset += tmpl->len;
-			if (expr->len == off)
+			if (expr->len == 0)
 				return;
 		} else
 			break;
diff --git a/src/proto.c b/src/proto.c
index 0fe0b88..68d635f 100644
--- a/src/proto.c
+++ b/src/proto.c
@@ -407,9 +407,9 @@ const struct proto_desc proto_tcp = {
 		[TCPHDR_SEQ]		= TCPHDR_FIELD("sequence", seq),
 		[TCPHDR_ACKSEQ]		= TCPHDR_FIELD("ackseq", ack_seq),
 		[TCPHDR_DOFF]		= HDR_BITFIELD("doff", &integer_type,
-						       (12 * BITS_PER_BYTE) + 4, 4),
+						       (12 * BITS_PER_BYTE), 4),
 		[TCPHDR_RESERVED]	= HDR_BITFIELD("reserved", &integer_type,
-						       (12 * BITS_PER_BYTE) + 0, 4),
+						       (12 * BITS_PER_BYTE) + 4, 4),
 		[TCPHDR_FLAGS]		= HDR_BITFIELD("flags", &tcp_flag_type,
 						       13 * BITS_PER_BYTE,
 						       BITS_PER_BYTE),
@@ -459,7 +459,8 @@ const struct proto_desc proto_dccp = {
 	.templates	= {
 		[DCCPHDR_SPORT]		= INET_SERVICE("sport", struct dccp_hdr, dccph_sport),
 		[DCCPHDR_DPORT]		= INET_SERVICE("dport", struct dccp_hdr, dccph_dport),
-		[DCCPHDR_TYPE]		= HDR_BITFIELD("type", &dccp_pkttype_type, 67, 4),
+		[DCCPHDR_TYPE]		= HDR_BITFIELD("type", &dccp_pkttype_type,
+						       (8 * BITS_PER_BYTE) + 3, 4),
 	},
 };
 
@@ -508,8 +509,8 @@ const struct proto_desc proto_ip = {
 		PROTO_LINK(IPPROTO_SCTP,	&proto_sctp),
 	},
 	.templates	= {
-		[IPHDR_VERSION]		= HDR_BITFIELD("version", &integer_type, 4, 4),
-		[IPHDR_HDRLENGTH]	= HDR_BITFIELD("hdrlength", &integer_type, 0, 4),
+		[IPHDR_VERSION]		= HDR_BITFIELD("version", &integer_type, 0, 4),
+		[IPHDR_HDRLENGTH]	= HDR_BITFIELD("hdrlength", &integer_type, 4, 4),
 		[IPHDR_TOS]		= IPHDR_FIELD("tos",		tos),
 		[IPHDR_LENGTH]		= IPHDR_FIELD("length",		tot_len),
 		[IPHDR_ID]		= IPHDR_FIELD("id",		id),
@@ -730,9 +731,9 @@ const struct proto_desc proto_vlan = {
 
 	},
 	.templates	= {
-		[VLANHDR_VID]		= VLANHDR_BITFIELD("id", 0, 12),
-		[VLANHDR_CFI]		= VLANHDR_BITFIELD("cfi", 12, 1),
-		[VLANHDR_PCP]		= VLANHDR_BITFIELD("pcp", 13, 3),
+		[VLANHDR_PCP]		= VLANHDR_BITFIELD("pcp", 0, 3),
+		[VLANHDR_CFI]		= VLANHDR_BITFIELD("cfi", 3, 1),
+		[VLANHDR_VID]		= VLANHDR_BITFIELD("id", 4, 12),
 		[VLANHDR_TYPE]		= VLANHDR_TYPE("type", &ethertype_type, vlan_type),
 	},
 };
-- 
2.1.4

Re: [PATCH nft 2/7,v2] src: fix sub-byte protocol header definitions

[Pablo Neira Ayuso]

On Sat, Dec 05, 2015 at 08:04:21PM +0100, Pablo Neira Ayuso wrote:
> Update bitfield definitions to match according to the way they are
> expressed in RFC and IEEE specifications.

I'm going to apply these series up to 3/7 so we get the definitions
following the RFC/IEEE format.

Note that vlan ranges are still broken (the code that is generated to
match a pcp range is not correct).

I'm reworking 4/7 and upper, I'm willing to address all the possible
issues in one go. Will likely be sending an email with feedback on my
proposal design for better subbyte handling.

[PATCH nft 3/7] netlink_delinearize: postprocess expression before range merge

[Pablo Neira Ayuso]

Dependency statement go away after postprocess, so we should consider
them for possible range merges.

This problem was uncovered when adding support for sub-byte payload
ranges.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/netlink_delinearize.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index e5cee16..8cbabc3 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -1558,11 +1558,11 @@ static void stmt_expr_postprocess(struct rule_pp_ctx *ctx, struct stmt *prev)
 {
 	enum ops op;
 
-	if (prev && ctx->stmt->ops->type == prev->ops->type &&
+	expr_postprocess(ctx, &ctx->stmt->expr);
+
+	if (prev && ctx->stmt && ctx->stmt->ops->type == prev->ops->type &&
 	    expr_may_merge_range(ctx->stmt->expr, prev->expr, &op))
 		expr_postprocess_range(ctx, prev, op);
-
-	expr_postprocess(ctx, &ctx->stmt->expr);
 }
 
 static void rule_parse_postprocess(struct netlink_parse_ctx *ctx, struct rule *rule)
-- 
2.1.4

[PATCH nft 4/7] evaluate: transfer right shifts to constant side

[Pablo Neira Ayuso]

From: Patrick McHardy <kaber@trash.net>

This provides a generic way to transfer shifts from the left hand side
to the right hand constant side of a relational expression when
performing transformations from the evaluation step.

Signed-off-by: Patrick McHardy <kaber@trash.net>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/evaluate.c | 30 ++++++++++++++++++++++++++----
 1 file changed, 26 insertions(+), 4 deletions(-)

diff --git a/src/evaluate.c b/src/evaluate.c
index 7aab6aa..d62870a 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -646,6 +646,7 @@ static int constant_binop_simplify(struct eval_ctx *ctx, struct expr **expr)
 		break;
 	case OP_LSHIFT:
 		assert(left->byteorder == BYTEORDER_HOST_ENDIAN);
+		mpz_set(val, left->value);
 		mpz_lshift_ui(val, mpz_get_uint32(right->value));
 		mpz_and(val, val, mask);
 		break;
@@ -1021,6 +1022,8 @@ static int binop_can_transfer(struct eval_ctx *ctx,
 			return expr_binary_error(ctx->msgs, right, left,
 						 "Comparison is always false");
 		return 1;
+	case OP_RSHIFT:
+		return 1;
 	case OP_XOR:
 		return 1;
 	default:
@@ -1038,6 +1041,10 @@ static int binop_transfer_one(struct eval_ctx *ctx,
 		(*right) = binop_expr_alloc(&(*right)->location, OP_RSHIFT,
 					    *right, expr_get(left->right));
 		break;
+	case OP_RSHIFT:
+		(*right) = binop_expr_alloc(&(*right)->location, OP_LSHIFT,
+					    *right, expr_get(left->right));
+		break;
 	case OP_XOR:
 		(*right) = binop_expr_alloc(&(*right)->location, OP_XOR,
 					    *right, expr_get(left->right));
@@ -1052,6 +1059,7 @@ static int binop_transfer_one(struct eval_ctx *ctx,
 static int binop_transfer(struct eval_ctx *ctx, struct expr **expr)
 {
 	struct expr *left = (*expr)->left, *i, *next;
+	unsigned int shift;
 	int err;
 
 	if (left->ops->type != EXPR_BINOP)
@@ -1083,10 +1091,24 @@ static int binop_transfer(struct eval_ctx *ctx, struct expr **expr)
 		return 0;
 	}
 
-	left = expr_get((*expr)->left->left);
-	left->dtype = (*expr)->left->dtype;
-	expr_free((*expr)->left);
-	(*expr)->left = left;
+	switch (left->op) {
+	case OP_RSHIFT:
+		/* Mask out the bits the shift would have masked out */
+		shift = mpz_get_uint8(left->right->value);
+		mpz_bitmask(left->right->value, left->left->len);
+		mpz_lshift_ui(left->right->value, shift);
+		left->op = OP_AND;
+		break;
+	case OP_LSHIFT:
+	case OP_XOR:
+		left = expr_get((*expr)->left->left);
+		left->dtype = (*expr)->left->dtype;
+		expr_free((*expr)->left);
+		(*expr)->left = left;
+		break;
+	default:
+		BUG("invalid binop operation %u", left->op);
+	}
 	return 0;
 }
 
-- 
2.1.4

[PATCH nft 5/7] evaluate: transfer right shifts to range side

[Pablo Neira Ayuso]

This provides a generic way to transfer shifts from the left hand side
to the right hand range side of a relational expression when performing
transformations from the evaluation step.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/evaluate.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/src/evaluate.c b/src/evaluate.c
index d62870a..0fcdb73 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1073,6 +1073,18 @@ static int binop_transfer(struct eval_ctx *ctx, struct expr **expr)
 		if (binop_transfer_one(ctx, left, &(*expr)->right) < 0)
 			return -1;
 		break;
+	case EXPR_RANGE:
+		err = binop_can_transfer(ctx, left, (*expr)->right->left);
+		if (err <= 0)
+			return err;
+		err = binop_can_transfer(ctx, left, (*expr)->right->right);
+		if (err <= 0)
+			return err;
+		if (binop_transfer_one(ctx, left, &(*expr)->right->left) < 0)
+			return -1;
+		if (binop_transfer_one(ctx, left, &(*expr)->right->right) < 0)
+			return -1;
+		break;
 	case EXPR_SET:
 		list_for_each_entry(i, &(*expr)->right->expressions, list) {
 			err = binop_can_transfer(ctx, left, i);
-- 
2.1.4

[PATCH nft 6/7] evaluate: transfer right shifts to set reference side

[Pablo Neira Ayuso]

This provides a generic way to transfer shifts from the left hand side
to the right hand range side of a relational expression when performing
transformations from the evaluation step.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/evaluate.c            | 14 ++++++++++++++
 src/netlink_delinearize.c | 19 ++++++++++++++++---
 2 files changed, 30 insertions(+), 3 deletions(-)

diff --git a/src/evaluate.c b/src/evaluate.c
index 0fcdb73..eb191ed 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1099,6 +1099,20 @@ static int binop_transfer(struct eval_ctx *ctx, struct expr **expr)
 			list_add_tail(&i->list, &next->list);
 		}
 		break;
+	case EXPR_SET_REF:
+		list_for_each_entry(i, &(*expr)->right->set->init->expressions, list) {
+			err = binop_can_transfer(ctx, left, i->key);
+			if (err <= 0)
+				return err;
+		}
+		list_for_each_entry_safe(i, next, &(*expr)->right->set->init->expressions,
+					 list) {
+			list_del(&i->list);
+			if (binop_transfer_one(ctx, left, &i->key) < 0)
+				return -1;
+			list_add_tail(&i->list, &next->list);
+		}
+		break;
 	default:
 		return 0;
 	}
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 8cbabc3..c5e5c69 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -1184,8 +1184,7 @@ static void relational_binop_postprocess(struct rule_pp_ctx *ctx, struct expr *e
 		expr_free(value);
 		expr_free(binop);
 	} else if (binop->op == OP_AND &&
-		   binop->left->ops->type == EXPR_PAYLOAD &&
-		   binop->right->ops->type == EXPR_VALUE) {
+		   binop->left->ops->type == EXPR_PAYLOAD) {
 		struct expr *payload = binop->left;
 		struct expr *mask = binop->right;
 		unsigned int shift;
@@ -1223,10 +1222,24 @@ static void relational_binop_postprocess(struct rule_pp_ctx *ctx, struct expr *e
 			 * Finally, convert the expression to 1) by replacing
 			 * the binop with the binop payload expr.
 			 */
-			if (value->ops->type == EXPR_VALUE) {
+			switch (value->ops->type) {
+			case EXPR_VALUE:
 				assert(value->len >= expr->left->right->len);
 				mpz_rshift_ui(value->value, shift);
 				value->len = payload->len;
+				break;
+			case EXPR_SET_REF: {
+				struct expr *i;
+
+				list_for_each_entry(i, &value->set->init->expressions, list) {
+					assert(i->key->len >= expr->left->right->len);
+					mpz_rshift_ui(i->key->value, shift);
+					i->key->len = payload->len;
+				}
+				break;
+				}
+			default:
+				break;
 			}
 
 			payload_match_postprocess(ctx, expr, payload);
-- 
2.1.4

[PATCH nft 7/7] src: move payload sub-byte matching to the evaluation step

[Pablo Neira Ayuso]

Generating the bitwise logic to match sub-byte payload fields from the
linearize step has several problems.

1) When the bits are split between two bytes and the payload field is
   smaller than one byte, we need to extend the expression length on
   both sides (payload and constant) of the relational expression.

2) Explicit bitmask operations on sub-byte payload fields need to be
   merge to the implicit bitmask operation, otherwise we generate two
   bitwise instructions.

Moreover, with this approach, we can benefit from the binary operation
transfer for shifts to provide a generic way to adjust the constant side
of the expression.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/evaluate.c          | 71 ++++++++++++++++++++++++++++++++++++++++++++++---
 src/netlink_linearize.c | 60 -----------------------------------------
 2 files changed, 68 insertions(+), 63 deletions(-)

diff --git a/src/evaluate.c b/src/evaluate.c
index eb191ed..4ee82ef 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -457,12 +457,74 @@ static int __expr_evaluate_payload(struct eval_ctx *ctx, struct expr *expr)
 	return 0;
 }
 
-static int expr_evaluate_payload(struct eval_ctx *ctx, struct expr **expr)
+static unsigned int expr_payload_shift_calc(const struct expr *expr)
 {
-	if (__expr_evaluate_payload(ctx, *expr) < 0)
+	unsigned int offset, len;
+	int shift;
+
+	offset = expr->payload.offset % BITS_PER_BYTE;
+	len = round_up(expr->len, BITS_PER_BYTE);
+	shift = len - (offset + expr->len);
+	assert(shift >= 0);
+
+	return shift;
+}
+
+static void expr_evaluate_payload_bits(struct eval_ctx *ctx,
+				       struct expr **exprp)
+{
+	struct expr *expr = *exprp, *and, *mask, *lshift, *off;
+	unsigned int shift, masklen;
+	mpz_t bitmask;
+
+	shift = expr_payload_shift_calc(expr);
+	masklen = expr->len + shift;
+	assert(masklen <= NFT_REG_SIZE * BITS_PER_BYTE);
+
+	mpz_init2(bitmask, masklen);
+	mpz_bitmask(bitmask, expr->len);
+	mpz_lshift_ui(bitmask, shift);
+
+	mask = constant_expr_alloc(&expr->location, expr_basetype(expr),
+				   BYTEORDER_HOST_ENDIAN, masklen, NULL);
+	mpz_set(mask->value, bitmask);
+
+	and = binop_expr_alloc(&expr->location, OP_AND, expr, mask);
+	and->dtype	= expr->dtype;
+	and->byteorder	= expr->byteorder;
+	and->len	= masklen;
+
+	if (shift) {
+		off = constant_expr_alloc(&expr->location,
+					  expr_basetype(expr),
+					  BYTEORDER_BIG_ENDIAN,
+					  masklen, &shift);
+
+		lshift = binop_expr_alloc(&expr->location, OP_RSHIFT, and, off);
+		lshift->dtype		= expr->dtype;
+		lshift->byteorder	= expr->byteorder;
+		lshift->len		= masklen;
+
+		*exprp = lshift;
+	} else
+		*exprp = and;
+}
+
+static int expr_evaluate_payload(struct eval_ctx *ctx, struct expr **exprp)
+{
+	struct expr *expr = *exprp;
+
+	if (__expr_evaluate_payload(ctx, expr) < 0)
 		return -1;
 
-	return expr_evaluate_primary(ctx, expr);
+	if (expr_evaluate_primary(ctx, exprp) < 0)
+		return -1;
+
+	if (expr->payload.offset % BITS_PER_BYTE != 0 ||
+	    expr->len % BITS_PER_BYTE != 0)
+		expr_evaluate_payload_bits(ctx, exprp);
+
+	return 0;
 }
 
 /*
@@ -1042,6 +1104,9 @@ static int binop_transfer_one(struct eval_ctx *ctx,
 					    *right, expr_get(left->right));
 		break;
 	case OP_RSHIFT:
+		if (mpz_get_uint32(left->right->value) >= ctx->ectx.len)
+			ctx->ectx.len += mpz_get_uint32(left->right->value);
+
 		(*right) = binop_expr_alloc(&(*right)->location, OP_LSHIFT,
 					    *right, expr_get(left->right));
 		break;
diff --git a/src/netlink_linearize.c b/src/netlink_linearize.c
index 131c3f9..e9dfdf9 100644
--- a/src/netlink_linearize.c
+++ b/src/netlink_linearize.c
@@ -103,54 +103,6 @@ static void netlink_gen_concat(struct netlink_linearize_ctx *ctx,
 	}
 }
 
-static unsigned int payload_shift_calc(const struct expr *expr)
-{
-	unsigned int offset, len;
-	int shift;
-
-	offset = expr->payload.offset % BITS_PER_BYTE;
-	len = round_up(expr->len, BITS_PER_BYTE);
-	shift = len - (offset + expr->len);
-	assert(shift >= 0);
-
-	return shift;
-}
-
-static void netlink_gen_payload_mask(struct netlink_linearize_ctx *ctx,
-				     const struct expr *expr,
-				     enum nft_registers dreg)
-{
-	struct nft_data_linearize nld, zero = {};
-	unsigned int shift, len, masklen;
-	struct nftnl_expr *nle;
-	mpz_t mask;
-
-	shift = payload_shift_calc(expr);
-	if (!shift && expr->payload.offset % BITS_PER_BYTE == 0)
-		return;
-
-	masklen = expr->len + shift;
-	assert(masklen <= NFT_REG_SIZE * BITS_PER_BYTE);
-	mpz_init2(mask, masklen);
-	mpz_bitmask(mask, expr->len);
-	mpz_lshift_ui(mask, shift);
-
-	nle = alloc_nft_expr("bitwise");
-
-	len = div_round_up(expr->len, BITS_PER_BYTE);
-
-	nftnl_expr_set_u32(nle, NFT_EXPR_BITWISE_SREG, dreg);
-	nftnl_expr_set_u32(nle, NFT_EXPR_BITWISE_DREG, dreg);
-	nftnl_expr_set_u32(nle, NFT_EXPR_BITWISE_LEN, len);
-
-	netlink_gen_raw_data(mask, expr->byteorder, len, &nld);
-	nftnl_expr_set(nle, NFT_EXPR_BITWISE_MASK, nld.value, nld.len);
-	nftnl_expr_set(nle, NFT_EXPR_BITWISE_XOR, &zero.value, nld.len);
-
-	mpz_clear(mask);
-	nftnl_rule_add_expr(ctx->nlr, nle);
-}
-
 static void netlink_gen_payload(struct netlink_linearize_ctx *ctx,
 				const struct expr *expr,
 				enum nft_registers dreg)
@@ -167,8 +119,6 @@ static void netlink_gen_payload(struct netlink_linearize_ctx *ctx,
 			   div_round_up(expr->len, BITS_PER_BYTE));
 
 	nftnl_rule_add_expr(ctx->nlr, nle);
-
-	netlink_gen_payload_mask(ctx, expr, dreg);
 }
 
 static void netlink_gen_exthdr(struct netlink_linearize_ctx *ctx,
@@ -290,15 +240,6 @@ static void netlink_gen_range(struct netlink_linearize_ctx *ctx,
 			      const struct expr *expr,
 			      enum nft_registers dreg);
 
-static void payload_shift_value(const struct expr *left, struct expr *right)
-{
-	if (right->ops->type != EXPR_VALUE ||
-	    left->ops->type != EXPR_PAYLOAD)
-		return;
-
-	mpz_lshift_ui(right->value, payload_shift_calc(left));
-}
-
 static struct expr *netlink_gen_prefix(struct netlink_linearize_ctx *ctx,
 				       const struct expr *expr,
 				       enum nft_registers sreg)
@@ -367,7 +308,6 @@ static void netlink_gen_cmp(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));
-	payload_shift_value(expr->left, right);
 	netlink_gen_data(right, &nld);
 	nftnl_expr_set(nle, NFTNL_EXPR_CMP_DATA, nld.value, len);
 	release_register(ctx, expr->left);
-- 
2.1.4