[PATCH nft 1/3] expression: add helper to decide if operator needs to be shown

[PATCH nft 1/3] expression: add helper to decide if operator needs to be shown

[Florian Westphal]

tcp dport 22 is treated as if user had given 'tcp dport == 22'.
When printing, the implicit == is omitted.

In some other cases we use OP_AND instead, e.g.
tcp flags ack means 'tcp flags & ack != 0'.

In all of these cases, we print the rule in the short form,
without showing this implicit operator.

Future patches will add other cases where an operator
other than AND or EQ can be suppressed, so add an explicit
helper that can suppress the operator symbol.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 src/expression.c | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/src/expression.c b/src/expression.c
index ab195e5..c96bce4 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -514,21 +514,27 @@ static void binop_arg_print(const struct expr *op, const struct expr *arg)
 		printf(")");
 }
 
-static bool must_print_eq_op(const struct expr *expr)
+static bool must_print_op(const struct expr *binop)
 {
-	if (expr->right->dtype->basetype != NULL &&
-	    expr->right->dtype->basetype->type == TYPE_BITMASK)
-		return true;
+	switch (binop->op) {
+	case OP_EQ:
+		if (binop->right->dtype->basetype != NULL &&
+		     binop->right->dtype->basetype->type == TYPE_BITMASK)
+			return true;
 
-	return expr->left->ops->type == EXPR_BINOP;
+		return binop->left->ops->type == EXPR_BINOP;
+	default:
+		break;
+	}
+
+	return true;
 }
 
 static void binop_expr_print(const struct expr *expr)
 {
 	binop_arg_print(expr, expr->left);
 
-	if (expr_op_symbols[expr->op] &&
-	    (expr->op != OP_EQ || must_print_eq_op(expr)))
+	if (expr_op_symbols[expr->op] && must_print_op(expr))
 		printf(" %s ", expr_op_symbols[expr->op]);
 	else
 		printf(" ");
-- 
2.4.10

[PATCH nft 3/4] meta: add probability matching

[Florian Westphal]

nft meta probability 0.5

probalistic matching just like iptables
'-m statistic --mode random --probability 0.5':

Internally nft translates the request to this:

  [ meta load prandom => reg 1 ]
  [ cmp lte reg 1 0xffffff7f ]

but this stays hidden from the user (i.e. <= operator
is not shown on list).

The float value has to be in range of 0.0000001 to 0.9999999 and
is internally scaled from 0 to UINT_MAX (the higher the value,
the higher the likelyhood of 'random() <= value' being true).

This patch deliberately doesn't add the META_PRANDOM key
to the existing meta keys -- this way we do not allow statement
like 'meta probability ne 0.2' since parser will expect a probability
value instead of 'ne'.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 NB: If you still dislike TYPE_PROBABILITY it would be possible
 to handle the de-scaling during netlink delinearization.

 This would also allow us to zap the relational expression
 at the same time which in turn avoids the code to suppress
 OP_LTE for the probability case.

 Only problem is that it needs a bit of meta.c details in
 netlink_delinearize (can only do the re-scaling in case of
 RELOP w. OP_LTE && left-type-is-meta && meta-key-is-prandom).

 Thoughts?

 include/datatype.h                  |  2 ++
 include/linux/netfilter/nf_tables.h |  2 ++
 include/meta.h                      |  4 +++
 src/expression.c                    |  2 ++
 src/meta.c                          | 70 +++++++++++++++++++++++++++++++++++++
 src/parser_bison.y                  | 24 +++++++++++--
 src/scanner.l                       |  7 +++-
 7 files changed, 108 insertions(+), 3 deletions(-)

diff --git a/include/datatype.h b/include/datatype.h
index 91ca2dd..dbfd8ff 100644
--- a/include/datatype.h
+++ b/include/datatype.h
@@ -40,6 +40,7 @@
  * @TYPE_ICMPV6_CODE:	icmpv6 code (integer subtype)
  * @TYPE_ICMPX_CODE:	icmpx code (integer subtype)
  * @TYPE_DEVGROUP:	devgroup code (integer subtype)
+ * @TYPE_PROBABILITY:	probability value (integer subtype)
  */
 enum datatypes {
 	TYPE_INVALID,
@@ -78,6 +79,7 @@ enum datatypes {
 	TYPE_ICMPV6_CODE,
 	TYPE_ICMPX_CODE,
 	TYPE_DEVGROUP,
+	TYPE_PROBABILITY,
 	__TYPE_MAX
 };
 #define TYPE_MAX		(__TYPE_MAX - 1)
diff --git a/include/linux/netfilter/nf_tables.h b/include/linux/netfilter/nf_tables.h
index 310c785..2fba42d 100644
--- a/include/linux/netfilter/nf_tables.h
+++ b/include/linux/netfilter/nf_tables.h
@@ -668,6 +668,7 @@ enum nft_exthdr_attributes {
  * @NFT_META_IIFGROUP: packet input interface group
  * @NFT_META_OIFGROUP: packet output interface group
  * @NFT_META_CGROUP: socket control group (skb->sk->sk_classid)
+ * @NFT_META_PRANDOM: a 32bit pseudo-random number
  */
 enum nft_meta_keys {
 	NFT_META_LEN,
@@ -694,6 +695,7 @@ enum nft_meta_keys {
 	NFT_META_IIFGROUP,
 	NFT_META_OIFGROUP,
 	NFT_META_CGROUP,
+	NFT_META_PRANDOM,
 };
 
 /**
diff --git a/include/meta.h b/include/meta.h
index f25b147..61e3da1 100644
--- a/include/meta.h
+++ b/include/meta.h
@@ -26,6 +26,10 @@ struct meta_template {
 extern struct expr *meta_expr_alloc(const struct location *loc,
 				    enum nft_meta_keys key);
 
+struct error_record *meta_probability_parse(const struct location *loc,
+				    const char *s, uint32_t *v);
+struct expr *meta_expr_alloc_probability(const struct location *loc, uint32_t p);
+
 struct stmt *meta_stmt_meta_iiftype(const struct location *loc, uint16_t type);
 
 const struct datatype ifindex_type;
diff --git a/src/expression.c b/src/expression.c
index c96bce4..4e88e5c 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -523,6 +523,8 @@ static bool must_print_op(const struct expr *binop)
 			return true;
 
 		return binop->left->ops->type == EXPR_BINOP;
+	case OP_LTE:
+		return binop->left->dtype->type != TYPE_PROBABILITY;
 	default:
 		break;
 	}
diff --git a/src/meta.c b/src/meta.c
index b8db0f8..13c3f6e 100644
--- a/src/meta.c
+++ b/src/meta.c
@@ -10,11 +10,13 @@
  * Development of this code funded by Astaro AG (http://www.astaro.com/)
  */
 
+#include <errno.h>
 #include <stddef.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <stdint.h>
 #include <string.h>
+#include <limits.h>
 #include <net/if.h>
 #include <net/if_arp.h>
 #include <pwd.h>
@@ -360,6 +362,57 @@ static const struct datatype devgroup_type = {
 	.flags		= DTYPE_F_PREFIX,
 };
 
+/* UINT_MAX == 1.0, UINT_MAX/2 == 0.5, etc. */
+#define META_PROB_FMT	"%.7f"
+static void probability_type_print(const struct expr *expr)
+{
+	uint64_t v = mpz_get_uint32(expr->value) + 1;
+
+	printf(META_PROB_FMT, 1.0 * v / 0x80000000 / 2.0);
+}
+
+static const struct datatype probability_type = {
+	.type		= TYPE_PROBABILITY,
+	.name		= "probability",
+	.desc		= "probability value",
+	.byteorder	= BYTEORDER_BIG_ENDIAN,
+	.size		= 4 * BITS_PER_BYTE,
+	.basetype	= &integer_type,
+	.print		= probability_type_print,
+};
+
+struct error_record *meta_probability_parse(const struct location *loc, const char *str,
+					    uint32_t *value)
+{
+		static const uint64_t precision = 10000000;
+		uint64_t tmp;
+		char *end;
+		double d, scaled;
+
+		errno = 0;
+		d = strtod(str, &end);
+
+		if (errno)
+			return error(loc, "Could not parse probability %s: %s", str, strerror(errno));
+		if (end == str)
+			return error(loc, "Could not parse probability %s", str);
+
+		scaled = d;
+		scaled *= precision;
+		tmp = (uint64_t) scaled;
+		tmp *= UINT_MAX;
+		tmp /= precision;
+
+		if (tmp >= UINT_MAX || d > 0.9999999)
+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "big");
+
+		*value = (uint32_t) tmp;
+		if (*value == 0)
+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "small");
+
+		return NULL;
+}
+
 static const struct meta_template meta_templates[] = {
 	[NFT_META_LEN]		= META_TEMPLATE("length",    &integer_type,
 						4 * 8, BYTEORDER_HOST_ENDIAN),
@@ -416,6 +469,9 @@ static const struct meta_template meta_templates[] = {
 	[NFT_META_CGROUP]	= META_TEMPLATE("cgroup",    &integer_type,
 						4 * BITS_PER_BYTE,
 						BYTEORDER_HOST_ENDIAN),
+	[NFT_META_PRANDOM]	= META_TEMPLATE("probability",    &probability_type,
+						4 * BITS_PER_BYTE,
+						BYTEORDER_BIG_ENDIAN), /* avoid conversion; doesn't have endianess */
 };
 
 static bool meta_key_is_qualified(enum nft_meta_keys key)
@@ -426,6 +482,7 @@ static bool meta_key_is_qualified(enum nft_meta_keys key)
 	case NFT_META_L4PROTO:
 	case NFT_META_PROTOCOL:
 	case NFT_META_PRIORITY:
+	case NFT_META_PRANDOM:
 		return true;
 	default:
 		return false;
@@ -552,6 +609,18 @@ struct expr *meta_expr_alloc(const struct location *loc, enum nft_meta_keys key)
 	return expr;
 }
 
+struct expr *meta_expr_alloc_probability(const struct location *loc, uint32_t p)
+{
+	struct expr *meta = meta_expr_alloc(loc, NFT_META_PRANDOM);
+	struct expr *pexp;
+
+	pexp = constant_expr_alloc(loc, &probability_type,
+				   BYTEORDER_HOST_ENDIAN,
+				   BITS_PER_BYTE * sizeof(p), &p);
+
+	return relational_expr_alloc(loc, OP_LTE, meta, pexp);
+}
+
 static void meta_stmt_print(const struct stmt *stmt)
 {
 	if (meta_key_is_qualified(stmt->meta.key))
@@ -589,6 +658,7 @@ static void __init meta_init(void)
 	datatype_register(&gid_type);
 	datatype_register(&devgroup_type);
 	datatype_register(&pkttype_type);
+	datatype_register(&probability_type);
 }
 
 /*
diff --git a/src/parser_bison.y b/src/parser_bison.y
index 05ade0f..b56a5b1 100644
--- a/src/parser_bison.y
+++ b/src/parser_bison.y
@@ -329,6 +329,7 @@ static void location_update(struct location *loc, struct location *rhs, int n)
 %token IBRIPORT			"ibriport"
 %token OBRIPORT			"obriport"
 %token PKTTYPE			"pkttype"
+%token PROBABILITY		"probability"
 %token CPU			"cpu"
 %token IIFGROUP			"iifgroup"
 %token OIFGROUP			"oifgroup"
@@ -563,8 +564,8 @@ static void location_update(struct location *loc, struct location *rhs, int n)
 %destructor { expr_free($$); }	mh_hdr_expr
 %type <val>			mh_hdr_field
 
-%type <expr>			meta_expr
-%destructor { expr_free($$); }	meta_expr
+%type <expr>			meta_expr	meta_probability_expr
+%destructor { expr_free($$); }	meta_expr	meta_probability_expr
 %type <val>			meta_key	meta_key_qualified	meta_key_unqualified
 
 %type <expr>			ct_expr
@@ -1764,6 +1765,10 @@ match_stmt		:	relational_expr
 			{
 				$$ = expr_stmt_alloc(&@$, $1);
 			}
+			|	meta_probability_expr
+			{
+				$$ = expr_stmt_alloc(&@$, $1);
+			}
 			;
 
 symbol_expr		:	string
@@ -2226,6 +2231,21 @@ meta_expr		:	META	meta_key
 			}
 			;
 
+meta_probability_expr	:	META	PROBABILITY	STRING
+			{
+				struct error_record *erec;
+				uint32_t value;
+
+				erec = meta_probability_parse(&@$, $3, &value);
+				if (erec != NULL) {
+					erec_queue(erec, state->msgs);
+					YYERROR;
+				}
+
+				$$ = meta_expr_alloc_probability(&@$, value);
+			}
+			;
+
 meta_key		:	meta_key_qualified
 			|	meta_key_unqualified
 			;
diff --git a/src/scanner.l b/src/scanner.l
index a0dee47..2af4616 100644
--- a/src/scanner.l
+++ b/src/scanner.l
@@ -110,6 +110,7 @@ digit		[0-9]
 hexdigit	[0-9a-fA-F]
 decstring	{digit}+
 hexstring	0[xX]{hexdigit}+
+probability	0.{decstring}
 range		({decstring}?:{decstring}?)
 letter		[a-zA-Z]
 string		({letter})({letter}|{digit}|[/\-_\.])*
@@ -445,6 +446,7 @@ addrstring	({macaddr}|{ip4addr}|{ip6addr})
 "ibriport"		{ return IBRIPORT; }
 "obriport"		{ return OBRIPORT; }
 "pkttype"		{ return PKTTYPE; }
+"probability"		{ return PROBABILITY; }
 "cpu"			{ return CPU; }
 "iifgroup"		{ return IIFGROUP; }
 "oifgroup"		{ return OIFGROUP; }
@@ -486,7 +488,10 @@ addrstring	({macaddr}|{ip4addr}|{ip6addr})
 				}
 				return NUM;
 			}
-
+{probability}		{
+				yylval->string = xstrdup(yytext);
+				return STRING;
+			}
 {hexstring}		{
 				errno = 0;
 				yylval->val = strtoull(yytext, NULL, 0);
-- 
2.4.10

[PATCH nft 4/4] meta: add tests for probability matching

[Florian Westphal]

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 tests/py/any/meta.t         | 16 ++++++++++++++++
 tests/py/any/meta.t.payload | 15 +++++++++++++++
 2 files changed, 31 insertions(+)

diff --git a/tests/py/any/meta.t b/tests/py/any/meta.t
index c10297a..4fa961f 100644
--- a/tests/py/any/meta.t
+++ b/tests/py/any/meta.t
@@ -197,3 +197,19 @@ meta cgroup {1048577-1048578};ok;cgroup { 1048577-1048578}
 meta iif . meta oif { lo . eth0 };ok
 meta iif . meta oif . meta mark { lo . eth0 . 0x0000000a };ok
 meta iif . meta oif vmap { lo . eth0 : drop };ok
+
+meta probability 0.0000001;ok
+meta probability 0.5;ok;meta probability 0.5000000
+meta probability 0.9999999;ok
+
+# outside of supported precision range
+meta probability 0.00000001;fail
+meta probability 0.99999999;fail
+
+# meta probability cannot be used with operators
+meta probability eq 0.5;fail
+
+# not 0.xxx format
+meta probability 1.5;fail
+meta probability foobar;fail
+meta probability 0;fail
diff --git a/tests/py/any/meta.t.payload b/tests/py/any/meta.t.payload
index 9f7a6d9..7c5eb72 100644
--- a/tests/py/any/meta.t.payload
+++ b/tests/py/any/meta.t.payload
@@ -754,3 +754,18 @@ ip test-ip4 output
   [ meta load oif => reg 9 ]
   [ lookup reg 1 set map%d dreg 0 ]
 
+# meta probability 0.0000001
+ip test-ip4 input
+  [ meta load prandom => reg 1 ]
+  [ cmp lte reg 1 0xad010000 ]
+
+# meta probability 0.5
+ip test-ip4 input
+  [ meta load prandom => reg 1 ]
+  [ cmp lte reg 1 0xffffff7f ]
+
+# meta probability 0.9999999
+ip test-ip4 input
+  [ meta load prandom => reg 1 ]
+  [ cmp lte reg 1 0x51feffff ]
+
-- 
2.4.10

Re: [PATCH nft 3/4] meta: add probability matching

[Jan Engelhardt]

On Thursday 2016-03-03 18:56, Florian Westphal wrote:

>The float value has to be in range of 0.0000001 to 0.9999999 and
>+
>+		if (tmp >= UINT_MAX || d > 0.9999999)
>+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "big");

You are misappropriating some 430 points here. 0.9999999 maps to
just 0xfffffe51.

>+		*value = (uint32_t) tmp;
>+		if (*value == 0)
>+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "small");

Though d==0 and d==1 are not overly useful, why prohibit them? iptables 
allowed taking them, and I hear people are working on a translator...*boom*

Re: [PATCH nft 3/4] meta: add probability matching

[Florian Westphal]

Jan Engelhardt <jengelh@inai.de> wrote:
> On Thursday 2016-03-03 18:56, Florian Westphal wrote:
> 
> >The float value has to be in range of 0.0000001 to 0.9999999 and
> >+
> >+		if (tmp >= UINT_MAX || d > 0.9999999)
> >+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "big");
> 
> You are misappropriating some 430 points here. 0.9999999 maps to
> just 0xfffffe51.

Sorry, I am not following.
What would you likew to change here?

> >+		*value = (uint32_t) tmp;
> >+		if (*value == 0)
> >+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "small");
> 
> Though d==0 and d==1 are not overly useful, why prohibit them? iptables 
> allowed taking them, and I hear people are working on a translator...*boom*

No, thats easy to translate to nft :-)

1.0 -> ""
0.0 -> "#"

i.e. not print a "1.0" match, its always true so irrelevant and print
comment a sign (#) to make nft ignore whatever comes after it, since it
did not match in the iptables rule either.

Re: [PATCH nft 3/4] meta: add probability matching

[Jan Engelhardt]

On Thursday 2016-03-03 21:32, Florian Westphal wrote:

>Jan Engelhardt <jengelh@inai.de> wrote:
>> On Thursday 2016-03-03 18:56, Florian Westphal wrote:
>> 
>> >The float value has to be in range of 0.0000001 to 0.9999999 and
>> >+
>> >+		if (tmp >= UINT_MAX || d > 0.9999999)
>> >+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "big");
>> 
>> You are misappropriating some 430 points here. 0.9999999 maps to
>> just 0xfffffe51.
>
>Sorry, I am not following.

0.9999999997 is still a valid probability, but you are making it 
impossible to select it by cutting off at d > 0.9999999000.


>What would you likew to change here?

Change to
	if (tmp >= UINT_MAX || d >= 1)

(or better yet, d > 1)

Re: [PATCH nft 3/4] meta: add probability matching

[Florian Westphal]

Jan Engelhardt <jengelh@inai.de> wrote:
> >> >+		if (tmp >= UINT_MAX || d > 0.9999999)
> >> >+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "big");
> >> 
> >> You are misappropriating some 430 points here. 0.9999999 maps to
> >> just 0xfffffe51.
> >
> >Sorry, I am not following.
> 
> 0.9999999997 is still a valid probability, but you are making it 
> impossible to select it by cutting off at d > 0.9999999000.

I'll change it to allow one more digit, so that supported range will
be 0.00000001 (0x0000002a) to
   0.99999999 (0xffffffd4).

(I'll wait a bit in case anyone has opinion where to suppress display of
 LTE op and where to handle de-scaling of the kernel side integer back
 to 0.12345 output).

Re: [PATCH nft 3/4] meta: add probability matching

[Jan Engelhardt]

On Friday 2016-03-04 12:12, Florian Westphal wrote:
>Jan Engelhardt <jengelh@inai.de> wrote:
>> >> >+		if (tmp >= UINT_MAX || d > 0.9999999)
>> >> >+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "big");
>> >> 
>> >> You are misappropriating some 430 points here. 0.9999999 maps to
>> >> just 0xfffffe51.
>> >
>> >Sorry, I am not following.
>> 
>> 0.9999999997 is still a valid probability, but you are making it 
>> impossible to select it by cutting off at d > 0.9999999000.
>
>I'll change it to allow one more digit, so that supported range will
>be 0.00000001 [10^-8] (0x0000002a) to
>   0.99999999 (0xffffffd4).

Let's ask differently. What precludes the use of the full range
(0x0/0x1) [2*10^-10] to (0xffffffff)?

Re: [PATCH nft 3/4] meta: add probability matching

[Florian Westphal]

Jan Engelhardt <jengelh@inai.de> wrote:
> On Friday 2016-03-04 12:12, Florian Westphal wrote:
> >Jan Engelhardt <jengelh@inai.de> wrote:
> >> >> >+		if (tmp >= UINT_MAX || d > 0.9999999)
> >> >> >+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "big");
> >> >> 
> >> >> You are misappropriating some 430 points here. 0.9999999 maps to
> >> >> just 0xfffffe51.
> >> >
> >> >Sorry, I am not following.
> >> 
> >> 0.9999999997 is still a valid probability, but you are making it 
> >> impossible to select it by cutting off at d > 0.9999999000.
> >
> >I'll change it to allow one more digit, so that supported range will
> >be 0.00000001 [10^-8] (0x0000002a) to
> >   0.99999999 (0xffffffd4).
> 
> Let's ask differently. What precludes the use of the full range
> (0x0/0x1) [2*10^-10] to (0xffffffff)?

Mapping smallest probability to 0x1 and largest one to 0xffffffff
means I lose ability to print back a number as entered.