[PATCH nft 1/3] meta: add random and probability match

[PATCH nft 1/3] meta: add random and probability match

[Florian Westphal]

Hi.

This is yet another attempt at the random/probability matching.

First patch adds a simple 'meta random' expression.

Second patch adds a 'probability' mode which internally maps to
the random one and takes care of scaling the '0.x' probability
to the needed integer.

Third patch is the reverse translation, so that users that
input

meta probability 0.001

will see the same on list instead of

meta random <= 4294967

Patch 2 and 3 use meta statement to add this probability mode.

Let me know, if needed I can also only push patch #1.

I also have a patch for meta.t to add tests for this.

[PATCH nft 1/3] meta: add random expression key

[Florian Westphal]

meta random fills a 32bit register with a pseudo-random number.

For instance one can now use

meta random <= 2147483647

... to match every 2nd packet, on average.

A followup patch will add a short-hand version ('probability 0.5') so
that users do not have to deal with details.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 src/meta.c         | 6 ++++++
 src/parser_bison.y | 1 +
 2 files changed, 7 insertions(+)

diff --git a/src/meta.c b/src/meta.c
index 75431a2..8b1a2fc 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>
@@ -418,6 +420,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("random",    &integer_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)
@@ -428,6 +433,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;
diff --git a/src/parser_bison.y b/src/parser_bison.y
index d7cba23..fdbfed9 100644
--- a/src/parser_bison.y
+++ b/src/parser_bison.y
@@ -2336,6 +2336,7 @@ meta_key_qualified	:	LENGTH		{ $$ = NFT_META_LEN; }
 			|	L4PROTO		{ $$ = NFT_META_L4PROTO; }
 			|	PROTOCOL	{ $$ = NFT_META_PROTOCOL; }
 			|	PRIORITY	{ $$ = NFT_META_PRIORITY; }
+			|	RANDOM		{ $$ = NFT_META_PRANDOM; }
 			;
 
 meta_key_unqualified	:	MARK		{ $$ = NFT_META_MARK; }
-- 
2.7.3

Re: [PATCH nft 1/3] meta: add random expression key

[Pablo Neira Ayuso]

On Tue, Jul 05, 2016 at 09:35:33AM +0200, Florian Westphal wrote:
> meta random fills a 32bit register with a pseudo-random number.
> 
> For instance one can now use
> 
> meta random <= 2147483647
> 
> ... to match every 2nd packet, on average.
> 
> A followup patch will add a short-hand version ('probability 0.5') so
> that users do not have to deal with details.
> 
> Signed-off-by: Florian Westphal <fw@strlen.de>

Please, apply this patch.

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

We can later on revisit the probability scaling, so keep 2/3 and 3/3
back by now.

Thanks.

Re: [PATCH nft 1/3] meta: add random expression key

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> On Tue, Jul 05, 2016 at 09:35:33AM +0200, Florian Westphal wrote:
> > meta random fills a 32bit register with a pseudo-random number.
> > 
> > For instance one can now use
> > 
> > meta random <= 2147483647
> > 
> > ... to match every 2nd packet, on average.
> > 
> > A followup patch will add a short-hand version ('probability 0.5') so
> > that users do not have to deal with details.
> > 
> > Signed-off-by: Florian Westphal <fw@strlen.de>
> 
> Please, apply this patch.
> 
> Acked-by: Pablo Neira Ayuso <pablo@netfilter.org>
> 
> We can later on revisit the probability scaling, so keep 2/3 and 3/3
> back by now.

Done, I pushed a slightly amended version (no additional #include, only
needed in followup changes, I also edited the changelog to not mention
probability anymore.

[PATCH nft 2/3] meta: add short-hand mnemonic for probalistic matching

[Florian Westphal]

Allow users to use a simpler way to specify probalistic matching, e. g.:

meta probability 0.5		(match approx. every 2nd packet)
meta probability 0.001		(match approx. once every 1000 packets)

nft list will still show
meta random <= 2147483647
meta random <= 4294967

a followup patch will hide this internal representation (comparing
random 32 bit value with the scaled constant) -- we will munge the
expression statement and turn it into a special-cased meta one during
netlink delinearization.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/meta.h     |  4 ++++
 src/meta.c         | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/parser_bison.y | 19 +++++++++++++++++++
 src/scanner.l      |  5 +++++
 4 files changed, 83 insertions(+)

diff --git a/include/meta.h b/include/meta.h
index f25b147..aafd232 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 stmt *meta_stmt_meta_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/meta.c b/src/meta.c
index 8b1a2fc..2b0d5f0 100644
--- a/src/meta.c
+++ b/src/meta.c
@@ -364,6 +364,47 @@ static const struct datatype devgroup_type = {
 	.flags		= DTYPE_F_PREFIX,
 };
 
+#define META_PROB_FMT	"%.9f"
+
+/* UINT_MAX == 1.0, UINT_MAX/2 == 0.5, etc. */
+struct error_record *meta_probability_parse(const struct location *loc, const char *str,
+					    uint32_t *value)
+{
+		static const uint64_t precision = 1000000000;
+		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;
+
+		if (tmp > UINT_MAX)
+			goto overflow;
+
+		tmp *= UINT_MAX;
+		tmp /= precision;
+
+		if (tmp >= UINT_MAX)
+			goto overflow;
+
+		*value = (uint32_t) tmp;
+		if (*value == 0)
+			return error(loc, "Probability " META_PROB_FMT " too %s", d, "small");
+
+		return NULL;
+ overflow:
+		return error(loc, "Probability " META_PROB_FMT " too %s", d, "big");
+}
+
 static const struct meta_template meta_templates[] = {
 	[NFT_META_LEN]		= META_TEMPLATE("length",    &integer_type,
 						4 * 8, BYTEORDER_HOST_ENDIAN),
@@ -618,3 +659,17 @@ struct stmt *meta_stmt_meta_iiftype(const struct location *loc, uint16_t type)
 	dep = relational_expr_alloc(loc, OP_EQ, left, right);
 	return expr_stmt_alloc(&dep->location, dep);
 }
+
+struct stmt *meta_stmt_meta_probability(const struct location *loc, uint32_t p)
+{
+	struct expr *e, *left, *right;
+
+	left = meta_expr_alloc(loc, NFT_META_PRANDOM);
+	right = constant_expr_alloc(loc, &integer_type,
+				    BYTEORDER_HOST_ENDIAN,
+				    sizeof(p) * BITS_PER_BYTE, &p);
+
+	e = relational_expr_alloc(loc, OP_LTE, left, right);
+
+	return expr_stmt_alloc(&e->location, e);
+}
diff --git a/src/parser_bison.y b/src/parser_bison.y
index fdbfed9..dceb90f 100644
--- a/src/parser_bison.y
+++ b/src/parser_bison.y
@@ -2367,6 +2367,25 @@ meta_stmt		:	META	meta_key	SET	expr
 			{
 				$$ = meta_stmt_alloc(&@$, $1, $3);
 			}
+			|	META	STRING		STRING
+			{
+				struct error_record *erec;
+				uint32_t value;
+
+				if (strcmp($2, "probability") != 0) {
+					erec_queue(error(&@$, "unknown meta option %s", $2),
+						   state->msgs);
+					YYERROR;
+				}
+
+				erec = meta_probability_parse(&@$, $3, &value);
+				if (erec != NULL) {
+					erec_queue(erec, state->msgs);
+					YYERROR;
+				}
+
+				$$ = meta_stmt_meta_probability(&@$, value);
+			}
 			;
 
 ct_expr			: 	CT	ct_key
diff --git a/src/scanner.l b/src/scanner.l
index 88669d0..29ffe94 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}|[/\-_\.])*
@@ -490,6 +491,10 @@ addrstring	({macaddr}|{ip4addr}|{ip6addr})
 				return NUM;
 			}
 
+{probability}		{
+				yylval->string = xstrdup(yytext);
+				return STRING;
+			}
 {hexstring}		{
 				errno = 0;
 				yylval->val = strtoull(yytext, NULL, 0);
-- 
2.7.3

Re: [PATCH nft 2/3] meta: add short-hand mnemonic for probalistic matching

[Pablo Neira Ayuso]

On Tue, Jul 05, 2016 at 09:35:34AM +0200, Florian Westphal wrote:
> Allow users to use a simpler way to specify probalistic matching, e. g.:
> 
> meta probability 0.5		(match approx. every 2nd packet)
> meta probability 0.001		(match approx. once every 1000 packets)
> 
> nft list will still show
> meta random <= 2147483647
> meta random <= 4294967

I don't like this asymmetry.

What is the usecase for 'meta random' out of this probability case that
maps to what xt_statistics offers?

Re: [PATCH nft 2/3] meta: add short-hand mnemonic for probalistic matching

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> On Tue, Jul 05, 2016 at 09:35:34AM +0200, Florian Westphal wrote:
> > Allow users to use a simpler way to specify probalistic matching, e. g.:
> > 
> > meta probability 0.5		(match approx. every 2nd packet)
> > meta probability 0.001		(match approx. once every 1000 packets)
> > 
> > nft list will still show
> > meta random <= 2147483647
> > meta random <= 4294967
> 
> I don't like this asymmetry.

Its changed in patch #3 when adding the shorthand reverse translation.

> What is the usecase for 'meta random' out of this probability case that
> maps to what xt_statistics offers?

Nothing, but the meta random might be interesting to e.g. set random
(ct)mark for load balancing purposes.

Re: [PATCH nft 2/3] meta: add short-hand mnemonic for probalistic matching

[Pablo Neira Ayuso]

On Thu, Jul 14, 2016 at 12:52:18PM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > On Tue, Jul 05, 2016 at 09:35:34AM +0200, Florian Westphal wrote:
> > > Allow users to use a simpler way to specify probalistic matching, e. g.:
> > > 
> > > meta probability 0.5		(match approx. every 2nd packet)
> > > meta probability 0.001		(match approx. once every 1000 packets)
> > > 
> > > nft list will still show
> > > meta random <= 2147483647
> > > meta random <= 4294967
> > 
> > I don't like this asymmetry.
> 
> Its changed in patch #3 when adding the shorthand reverse
> translation.

But if the user introduces a meta random value that can be mapped to
probability datatype, we would still hit this asymmetry, right? So the
guess game would fail and the user would get confused.

> > What is the usecase for 'meta random' out of this probability case that
> > maps to what xt_statistics offers?
> 
> Nothing, but the meta random might be interesting to e.g. set random
> (ct)mark for load balancing purposes.

Could you have a look at the libnftnl userdata tlv infrastructure? We
can probably place this information the RULE_USERDATA so we provide an
explicit indication to userspace of how to interpret this.  Currently
this is only used for rule comments, but we can stash this
how-to-interpret-this information there.

The idea is to keep this information around as context in the
delinearize step, so we can replace the default datatype that is
assigned to the one that displays this as a probability from the
rule_parse_postprocess() phase.

Re: [PATCH nft 2/3] meta: add short-hand mnemonic for probalistic matching

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> But if the user introduces a meta random value that can be mapped to
> probability datatype, we would still hit this asymmetry, right? So the
> guess game would fail and the user would get confused.

Yes, but thats not really different from what we do with dependency
removal, e.g. with 'ip protocol tcp tcp dport 22', the 'ip protocol tcp'
is still elided from list output since its redundant.

> > Nothing, but the meta random might be interesting to e.g. set random
> > (ct)mark for load balancing purposes.
> 
> Could you have a look at the libnftnl userdata tlv infrastructure? We
> can probably place this information the RULE_USERDATA so we provide an
> explicit indication to userspace of how to interpret this.  Currently
> this is only used for rule comments, but we can stash this
> how-to-interpret-this information there.

Sure, I will have a look.  It might take a while though.

Re: [PATCH nft 2/3] meta: add short-hand mnemonic for probalistic matching

[Pablo Neira Ayuso]

On Thu, Jul 14, 2016 at 02:08:40PM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > But if the user introduces a meta random value that can be mapped to
> > probability datatype, we would still hit this asymmetry, right? So the
> > guess game would fail and the user would get confused.
> 
> Yes, but thats not really different from what we do with dependency
> removal, e.g. with 'ip protocol tcp tcp dport 22', the 'ip protocol tcp'
> is still elided from list output since its redundant.

Dependencies are a different thing, they are dealing with redundant
information. This is about what datatype userspace should use to
intepret data.

> > > Nothing, but the meta random might be interesting to e.g. set random
> > > (ct)mark for load balancing purposes.
> > 
> > Could you have a look at the libnftnl userdata tlv infrastructure? We
> > can probably place this information the RULE_USERDATA so we provide an
> > explicit indication to userspace of how to interpret this.  Currently
> > this is only used for rule comments, but we can stash this
> > how-to-interpret-this information there.
> 
> Sure, I will have a look.  It might take a while though.

Thanks.

[PATCH nft 3/3] netlink_delinearize, meta: show meta prandom <= value as probability mnemonic

[Florian Westphal]

During delinearization, check if we're looking at an expression
statement of the form

	  OP_LTE
META_PRANDOM  VALUE

And, if so, delete the expression statement and turn it into a
meta statement, where value expression is stashed inside the
meta statement struct.

We can do this because there is no 'set' support for prandom.
When printing a meta statement, check if the key is PRANDOM
and if so print the expression as a 'floating point' probability value.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 src/meta.c                | 16 ++++++++++++++++
 src/netlink_delinearize.c | 30 ++++++++++++++++++++++++++----
 2 files changed, 42 insertions(+), 4 deletions(-)

diff --git a/src/meta.c b/src/meta.c
index 2b0d5f0..bf8a430 100644
--- a/src/meta.c
+++ b/src/meta.c
@@ -601,8 +601,24 @@ struct expr *meta_expr_alloc(const struct location *loc, enum nft_meta_keys key)
 	return expr;
 }
 
+static void print_probability(const struct expr *expr)
+{
+	uint64_t value = mpz_get_uint64(expr->value);
+	double d, dividend;
+
+	dividend = (double)UINT_MAX;
+	d = (double)value;
+
+	printf("meta probability " META_PROB_FMT, d / dividend);
+}
+
 static void meta_stmt_print(const struct stmt *stmt)
 {
+	if (stmt->meta.key == NFT_META_PRANDOM) {
+		print_probability(stmt->meta.expr);
+		return;
+	}
+
 	if (meta_key_is_qualified(stmt->meta.key))
 		printf("meta %s set ", meta_templates[stmt->meta.key].token);
 	else
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 7735699..138132a 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -1181,19 +1181,41 @@ static void ct_meta_common_postprocess(const struct expr *expr)
 static void meta_match_postprocess(struct rule_pp_ctx *ctx,
 				   const struct expr *expr)
 {
+	struct stmt *nstmt, *stmt = ctx->stmt;
+	struct expr *right = expr->right;
 	struct expr *left = expr->left;
 
 	switch (expr->op) {
+	case OP_LTE: {
+		uint64_t value;
+
+		if (stmt->expr != expr ||
+		    left->meta.key != NFT_META_PRANDOM ||
+		    right->ops->type != EXPR_VALUE)
+			break;
+
+		value = mpz_get_uint64(right->value);
+		if (value < 4 || value > UINT_MAX)
+			break;
+
+		nstmt = meta_stmt_alloc(&stmt->location, NFT_META_PRANDOM,
+					expr_get(expr->right));
+
+		list_add_tail(&nstmt->list, &stmt->list);
+		list_del(&stmt->list);
+		stmt_free(stmt);
+		ctx->stmt = nstmt;
+		break;
+	}
 	case OP_EQ:
-		if (expr->right->ops->type == EXPR_RANGE)
+		if (right->ops->type == EXPR_RANGE)
 			break;
 
-		expr->left->ops->pctx_update(&ctx->pctx, expr);
+		left->ops->pctx_update(&ctx->pctx, expr);
 
 		if (ctx->pdctx.pbase == PROTO_BASE_INVALID &&
 		    left->flags & EXPR_F_PROTOCOL)
-			payload_dependency_store(&ctx->pdctx, ctx->stmt,
-						 left->meta.base);
+			payload_dependency_store(&ctx->pdctx, stmt, left->meta.base);
 		break;
 	default:
 		ct_meta_common_postprocess(expr);
-- 
2.7.3