[PATCH nft 0/3] meta: random match for statistic sampling

[PATCH nft 0/3] meta: random match for statistic sampling

[Florian Westphal]

Replacement for iptables -m statistic 'random' mode.
I added it to meta match even though its not directly related to an skb
member. We already have cpu match which isn't related to skb either and
adding a new expression just for this seemed overkill.

If you'd rather like a new prandom expression just let me know and
I can rework it.

There is also a libnftnl patch but its only so that debug output
displays 'meta prandom' rather than 'meta unknown'.

Result after several minutes of constant flooding:

counter packets 2961796882 bytes 248790938088
meta random <= 0.900000000 counter packets 2665649546 bytes 223914561864
meta random <= 0.500000000 counter packets 1480856860 bytes 124391976240
meta random <= 0.100000000 counter packets 296190072 bytes 24879966048
meta random <= 0.010000000 counter packets 29618610 bytes 2487963240
meta random <= 0.001000000 counter packets 2963660 bytes 248947440
meta random <= 0.000100000 counter packets 295486 bytes 24820824
meta random <= 0.000010000 counter packets 29450 bytes 2473800
meta random <= 0.000001000 counter packets 2911 bytes 244524
meta random <= 0.000000100 counter packets 267 bytes 22428
meta random <= 0.000000010 counter packets 26 bytes 2184
meta random <= 0.000000001 counter packets 4 bytes 336

... so it seems to work as intended.

Let me know if you spot any issues with current approach.

Kernel part only does '*dest = prandom_u32()', I'll submit it once
I know that this approach is deemed sane.

Thanks!

[PATCH nft 1/3] evaluate: move default op lookup into helper

[Florian Westphal]

Split it into its own function, caller is already quite big.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 src/evaluate.c | 43 ++++++++++++++++++++++---------------------
 1 file changed, 22 insertions(+), 21 deletions(-)

diff --git a/src/evaluate.c b/src/evaluate.c
index ed78896..4d741e3 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1119,6 +1119,26 @@ static int binop_transfer(struct eval_ctx *ctx, struct expr **expr)
 	return 0;
 }
 
+static enum ops expr_defaultop(const struct expr *e)
+{
+	switch (e->ops->type) {
+	case EXPR_RANGE:
+		return OP_RANGE;
+	case EXPR_SET:
+	case EXPR_SET_REF:
+		return OP_LOOKUP;
+	case EXPR_LIST:
+		return OP_FLAGCMP;
+	default:
+		if (e->dtype->basetype != NULL &&
+		    e->dtype->basetype->type == TYPE_BITMASK)
+			return OP_FLAGCMP;
+		break;
+	}
+
+	return OP_EQ;
+}
+
 static int expr_evaluate_relational(struct eval_ctx *ctx, struct expr **expr)
 {
 	struct expr *rel = *expr, *left, *right;
@@ -1131,27 +1151,8 @@ static int expr_evaluate_relational(struct eval_ctx *ctx, struct expr **expr)
 		return -1;
 	right = rel->right;
 
-	if (rel->op == OP_IMPLICIT) {
-		switch (right->ops->type) {
-		case EXPR_RANGE:
-			rel->op = OP_RANGE;
-			break;
-		case EXPR_SET:
-		case EXPR_SET_REF:
-			rel->op = OP_LOOKUP;
-			break;
-		case EXPR_LIST:
-			rel->op = OP_FLAGCMP;
-			break;
-		default:
-			if (right->dtype->basetype != NULL &&
-			    right->dtype->basetype->type == TYPE_BITMASK)
-				rel->op = OP_FLAGCMP;
-			else
-				rel->op = OP_EQ;
-			break;
-		}
-	}
+	if (rel->op == OP_IMPLICIT)
+		rel->op = expr_defaultop(rel->right);
 
 	if (!expr_is_constant(right))
 		return expr_binary_error(ctx->msgs, right, rel,
-- 
2.4.10

[PATCH nft 2/3] meta: add prandom matching

[Florian Westphal]

Probalistic random matching just like iptables
-m statistic --mode random --probability 0.1.

It introduces a new 'probability' type, which looks like fractional
value ("0.25") to the user, but is internally scaled to a uint32_t
where 1.0 is UINT_MAX.

Furthermore, make the default op for the type <= so that
"nft ... meta random 0.5" will match every 2nd packet.

This means that users can still do something like
"nft ... meta random eq 0.1" although thats not very useful (matching
probability 1/UINT_MAX).

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 doc/nft.xml                         | 14 ++++++++++
 include/datatype.h                  |  2 ++
 include/linux/netfilter/nf_tables.h |  2 ++
 src/evaluate.c                      |  3 +++
 src/meta.c                          | 54 +++++++++++++++++++++++++++++++++++++
 src/parser_bison.y                  |  1 +
 src/scanner.l                       |  6 ++++-
 7 files changed, 81 insertions(+), 1 deletion(-)

diff --git a/doc/nft.xml b/doc/nft.xml
index 7cc9988..a934ad3 100644
--- a/doc/nft.xml
+++ b/doc/nft.xml
@@ -966,6 +966,7 @@ filter output ip6 daddr ::1
 						<arg>l4proto</arg>
 						<arg>protocol</arg>
 						<arg>priority</arg>
+						<arg>random</arg>
 					</group>
 				</cmdsynopsis>
 				<cmdsynopsis>
@@ -1032,6 +1033,11 @@ filter output ip6 daddr ::1
 								<entry>integer (32 bit)</entry>
 							</row>
 							<row>
+								<entry>random</entry>
+								<entry>probability</entry>
+								<entry>probability_type</entry>
+							</row>
+							<row>
 								<entry>mark</entry>
 								<entry>Packet mark</entry>
 								<entry>packetmark</entry>
@@ -1187,6 +1193,14 @@ filter output ip6 daddr ::1
 									Broadcast (to all), Multicast (to group).
 								</entry>
 							</row>
+							<row>
+								<entry>probability_type</entry>
+								<entry>
+									Probability type: floating point value, must be within 0.0 and 0.9999999.
+									The value given is internally mapped to a 32bit integer number.
+								</entry>
+							</row>
+
 						</tbody>
 					</tgroup>
 				</table>
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/src/evaluate.c b/src/evaluate.c
index 4d741e3..9fe0d14 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1133,6 +1133,9 @@ static enum ops expr_defaultop(const struct expr *e)
 		if (e->dtype->basetype != NULL &&
 		    e->dtype->basetype->type == TYPE_BITMASK)
 			return OP_FLAGCMP;
+
+		if (e->dtype->type == TYPE_PROBABILITY)
+			return OP_LTE;
 		break;
 	}
 
diff --git a/src/meta.c b/src/meta.c
index 8cbc974..cfdb2e0 100644
--- a/src/meta.c
+++ b/src/meta.c
@@ -360,6 +360,55 @@ static const struct datatype devgroup_type = {
 	.flags		= DTYPE_F_PREFIX,
 };
 
+/* UINT_MAX == 1.0, UINT_MAX/2 == 0.5, etc. */
+static void probability_type_print(const struct expr *expr)
+{
+	uint64_t v = mpz_get_uint32(expr->value) + 0;
+
+	printf("%.9f", 1.0 * v / 0x80000000 / 2.0);
+}
+
+static struct error_record *probability_type_parse(const struct expr *sym,
+						   struct expr **res)
+{
+	char *end;
+	uint64_t value;
+	uint32_t import_value;
+	double limit = 0.000000001;
+	double d = strtod(sym->identifier, &end);
+
+	if (end == sym->identifier)
+		return error(&sym->location, "Could not parse %s", sym->dtype->desc);
+
+	if (d < limit)
+		return error(&sym->location, "Could not parse %s, must be larger or equal to %.9f", sym->dtype->desc,
+			     limit);
+
+	d *= 1000000000u;
+	value = (unsigned long) d;
+	value *= 0x80000000;
+	value *= 2;
+	value /= 1000000000u;
+
+	import_value = value;
+	*res = constant_expr_alloc(&sym->location, sym->dtype,
+				   BYTEORDER_HOST_ENDIAN,
+				   sizeof(import_value) * BITS_PER_BYTE,
+				   &import_value);
+	return NULL;
+}
+
+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,
+	.parse		= probability_type_parse,
+};
+
 static const struct meta_template meta_templates[] = {
 	[NFT_META_LEN]		= META_TEMPLATE("length",    &integer_type,
 						4 * 8, BYTEORDER_HOST_ENDIAN),
@@ -416,6 +465,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",    &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 +478,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;
@@ -589,6 +642,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..d22b66b 100644
--- a/src/parser_bison.y
+++ b/src/parser_bison.y
@@ -2235,6 +2235,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; }
diff --git a/src/scanner.l b/src/scanner.l
index a0dee47..d33ab03 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}|[/\-_\.])*
@@ -486,7 +487,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

Re: [PATCH nft 2/3] meta: add prandom matching

[Patrick McHardy]

Am 2. Februar 2016 00:19:00 MEZ, schrieb Florian Westphal <fw@strlen.de>:
>
> enum datatypes {
> 	TYPE_INVALID,
>@@ -78,6 +79,7 @@ enum datatypes {
> 	TYPE_ICMPV6_CODE,
> 	TYPE_ICMPX_CODE,
> 	TYPE_DEVGROUP,
>+	TYPE_PROBABILITY,
> 	__TYPE_MAX
> 

Any reason why you chose to add this type instead of a generic floating point type?

Re: [PATCH nft 2/3] meta: add prandom matching

[Florian Westphal]

Patrick McHardy <kaber@trash.net> wrote:
> Am 2. Februar 2016 00:19:00 MEZ, schrieb Florian Westphal <fw@strlen.de>:
> >
> > enum datatypes {
> > 	TYPE_INVALID,
> >@@ -78,6 +79,7 @@ enum datatypes {
> > 	TYPE_ICMPV6_CODE,
> > 	TYPE_ICMPX_CODE,
> > 	TYPE_DEVGROUP,
> >+	TYPE_PROBABILITY,
> > 	__TYPE_MAX
> > 
> 
> Any reason why you chose to add this type instead of a generic floating point type?

I wanted 0.9999 be tranlated to a value close to UINT32_MAX and 0.00001
to something close to zero so that "meta random 0.999" can be translated to
something like

reg1 = prandom_u32()
reg1 <= 0xffffffee

I.e. this type cannot represent 5.2 (or whatever).

Does that answer your question?

Re: [PATCH nft 2/3] meta: add prandom matching

[Patrick McHardy]

On 04.02, Florian Westphal wrote:
> Patrick McHardy <kaber@trash.net> wrote:
> > Am 2. Februar 2016 00:19:00 MEZ, schrieb Florian Westphal <fw@strlen.de>:
> > >
> > > enum datatypes {
> > > 	TYPE_INVALID,
> > >@@ -78,6 +79,7 @@ enum datatypes {
> > > 	TYPE_ICMPV6_CODE,
> > > 	TYPE_ICMPX_CODE,
> > > 	TYPE_DEVGROUP,
> > >+	TYPE_PROBABILITY,
> > > 	__TYPE_MAX
> > > 
> > 
> > Any reason why you chose to add this type instead of a generic floating point type?
> 
> I wanted 0.9999 be tranlated to a value close to UINT32_MAX and 0.00001
> to something close to zero so that "meta random 0.999" can be translated to
> something like
> 
> reg1 = prandom_u32()
> reg1 <= 0xffffffee
> 
> I.e. this type cannot represent 5.2 (or whatever).
> 
> Does that answer your question?

Not really unless I'm misunderstanding your intention. That part is
related to the kernel internal representation and could be handled
during linearization.

Re: [PATCH nft 2/3] meta: add prandom matching

[Florian Westphal]

Patrick McHardy <kaber@trash.net> wrote:
> > > Any reason why you chose to add this type instead of a generic floating point type?
> > 
> > I wanted 0.9999 be tranlated to a value close to UINT32_MAX and 0.00001
> > to something close to zero so that "meta random 0.999" can be translated to
> > something like
> > 
> > reg1 = prandom_u32()
> > reg1 <= 0xffffffee
> > 
> > I.e. this type cannot represent 5.2 (or whatever).
> > 
> > Does that answer your question?
> 
> Not really unless I'm misunderstanding your intention. That part is
> related to the kernel internal representation and could be handled
> during linearization.

So what would you suggest?
Add support for translating double to mpz_t?
What precisions would you support?

How to handle the scaling at (de)linearization
time if type doesn't do that aynmore?

What should happen when user asks for meta random 42.23 ?

Re: [PATCH nft 2/3] meta: add prandom matching

[Florian Westphal]

Florian Westphal <fw@strlen.de> wrote:
> Patrick McHardy <kaber@trash.net> wrote:
> > > > Any reason why you chose to add this type instead of a generic floating point type?
> > > 
> > > I wanted 0.9999 be tranlated to a value close to UINT32_MAX and 0.00001
> > > to something close to zero so that "meta random 0.999" can be translated to
> > > something like
> > > 
> > > reg1 = prandom_u32()
> > > reg1 <= 0xffffffee
> > > 
> > > I.e. this type cannot represent 5.2 (or whatever).
> > > 
> > > Does that answer your question?
> > 
> > Not really unless I'm misunderstanding your intention. That part is
> > related to the kernel internal representation and could be handled
> > during linearization.
> 
> So what would you suggest?
> Add support for translating double to mpz_t?
> What precisions would you support?

So I've started to generalize the proposed precision type
into type_float which would support 0.000000001 as smallest value.

Does that seem ok or would you use a different precision?
(If so, what & why?)

Thanks!

> What should happen when user asks for meta random 42.23 ?

That still stands, where would this error be detect best?

Re: [PATCH nft 2/3] meta: add prandom matching

[Florian Westphal]

Florian Westphal <fw@strlen.de> wrote:
> Florian Westphal <fw@strlen.de> wrote:
> > Patrick McHardy <kaber@trash.net> wrote:
> > > > > Any reason why you chose to add this type instead of a generic floating point type?
> > > > 
> > > > I wanted 0.9999 be tranlated to a value close to UINT32_MAX and 0.00001
> > > > to something close to zero so that "meta random 0.999" can be translated to
> > > > something like
> > > > 
> > > > reg1 = prandom_u32()
> > > > reg1 <= 0xffffffee
> > > > 
> > > > I.e. this type cannot represent 5.2 (or whatever).
> > > > 
> > > > Does that answer your question?
> > > 
> > > Not really unless I'm misunderstanding your intention. That part is
> > > related to the kernel internal representation and could be handled
> > > during linearization.
> > 
> > So what would you suggest?
> > Add support for translating double to mpz_t?
> > What precisions would you support?
> 
> So I've started to generalize the proposed precision type
> into type_float which would support 0.000000001 as smallest value.
> 
> Does that seem ok or would you use a different precision?
> (If so, what & why?)

> > What should happen when user asks for meta random 42.23 ?
> 
> That still stands, where would this error be detect best?

I've also been unable to figure out where the u32 scaling has
to be performed, netlink_linearize.c seems to be a very poor place
for this since it would mean special-casing netlink_gen_cmp
to check for OP_LTE and presence of EXPR_META with the meta PRANDOM
key...?

In fact, doing the scaling via precision_type seems to
be a lot simpler as then its applied only in this one case of the
prandom META_TEMPLATE while keeping this detail limited to meta.c.

Re: [PATCH nft 2/3] meta: add prandom matching

[Patrick McHardy]

On 04.02, Florian Westphal wrote:
> Florian Westphal <fw@strlen.de> wrote:
>
> > > What should happen when user asks for meta random 42.23 ?
> > 
> > That still stands, where would this error be detect best?
> 
> I've also been unable to figure out where the u32 scaling has
> to be performed, netlink_linearize.c seems to be a very poor place
> for this since it would mean special-casing netlink_gen_cmp
> to check for OP_LTE and presence of EXPR_META with the meta PRANDOM
> key...?
> 
> In fact, doing the scaling via precision_type seems to
> be a lot simpler as then its applied only in this one case of the
> prandom META_TEMPLATE while keeping this detail limited to meta.c.

Yes, on second thought I agree, sorry. Maybe the work is not lost though,
what does seem to make sense is to use a float basetype and derive your
probability type from that.

Re: [PATCH nft 2/3] meta: add prandom matching

[Florian Westphal]

Patrick McHardy <kaber@trash.net> wrote:

Hi Patrick

> On 04.02, Florian Westphal wrote:
> > In fact, doing the scaling via precision_type seems to
> > be a lot simpler as then its applied only in this one case of the
> > prandom META_TEMPLATE while keeping this detail limited to meta.c.
> 
> Yes, on second thought I agree, sorry. Maybe the work is not lost though,
> what does seem to make sense is to use a float basetype and derive your
> probability type from that.

I can do this.
However, I don't currently see any other type that could be derived from
that.  Would you be OK with leaving things as-is and adding a float
type later on once a use case presents itself?

I would re-word the commit message to mention the 'missing' float base type.

Thanks!

Re: [PATCH nft 2/3] meta: add prandom matching

[Pablo Neira Ayuso]

On Mon, Feb 15, 2016 at 01:54:46PM +0100, Florian Westphal wrote:
> Patrick McHardy <kaber@trash.net> wrote:
> 
> Hi Patrick
> 
> > On 04.02, Florian Westphal wrote:
> > > In fact, doing the scaling via precision_type seems to
> > > be a lot simpler as then its applied only in this one case of the
> > > prandom META_TEMPLATE while keeping this detail limited to meta.c.
> > 
> > Yes, on second thought I agree, sorry. Maybe the work is not lost though,
> > what does seem to make sense is to use a float basetype and derive your
> > probability type from that.
> 
> I can do this.
> However, I don't currently see any other type that could be derived from
> that.  Would you be OK with leaving things as-is and adding a float
> type later on once a use case presents itself?

I also think you can add a new TYPE_FLOAT.

Then, from the evaluation step make sure that META_PRANDOM is under
the valid limits (0, 1].

These TYPE_* will be part of the public API of the high level library
at some point, they describe the datatype that are used in set
definitions in the kernel (through the NFTA_SET_DATATYPE netlink
attribute and the new NFTA_SET_USERDATA through TLVs).

Re: [PATCH nft 2/3] meta: add prandom matching

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> On Mon, Feb 15, 2016 at 01:54:46PM +0100, Florian Westphal wrote:
> > Patrick McHardy <kaber@trash.net> wrote:
> > 
> > Hi Patrick
> > 
> > > On 04.02, Florian Westphal wrote:
> > > > In fact, doing the scaling via precision_type seems to
> > > > be a lot simpler as then its applied only in this one case of the
> > > > prandom META_TEMPLATE while keeping this detail limited to meta.c.
> > > 
> > > Yes, on second thought I agree, sorry. Maybe the work is not lost though,
> > > what does seem to make sense is to use a float basetype and derive your
> > > probability type from that.
> > 
> > I can do this.
> > However, I don't currently see any other type that could be derived from
> > that.  Would you be OK with leaving things as-is and adding a float
> > type later on once a use case presents itself?
> 
> I also think you can add a new TYPE_FLOAT.

Yes, but what I'm asking is: 'What for'?

> Then, from the evaluation step make sure that META_PRANDOM is under
> the valid limits (0, 1].

Thats not so simple.  META_PRANDOM is scaled so its represented
as 1.0 == UINT32_MAX and 0 = 0.

We can't do that for TYPE_FLOAT since it means that it could not
represent values > 1.0 .

Doing the scaling in the eval step is possible but its a bit ugly.

> These TYPE_* will be part of the public API of the high level library
> at some point, they describe the datatype that are used in set
> definitions in the kernel (through the NFTA_SET_DATATYPE netlink
> attribute and the new NFTA_SET_USERDATA through TLVs).

I understand, but,  the proposed float and probability types
are very different, and allow for very little re-use.

For example on printing the probability type has to undo the scaling
so we print 1.0 instead of $bignum.

Re: [PATCH nft 2/3] meta: add prandom matching

[Pablo Neira Ayuso]

On Tue, Feb 16, 2016 at 01:00:24PM +0100, Florian Westphal wrote:
> I understand, but,  the proposed float and probability types
> are very different, and allow for very little re-use.

I see, then stick to the probability datatype.

Re: [PATCH nft 2/3] meta: add prandom matching

[Patrick McHardy]

On 04.02, Florian Westphal wrote:
> Florian Westphal <fw@strlen.de> wrote:
> > Patrick McHardy <kaber@trash.net> wrote:
> > > > > Any reason why you chose to add this type instead of a generic floating point type?
> > > > 
> > > > I wanted 0.9999 be tranlated to a value close to UINT32_MAX and 0.00001
> > > > to something close to zero so that "meta random 0.999" can be translated to
> > > > something like
> > > > 
> > > > reg1 = prandom_u32()
> > > > reg1 <= 0xffffffee
> > > > 
> > > > I.e. this type cannot represent 5.2 (or whatever).
> > > > 
> > > > Does that answer your question?
> > > 
> > > Not really unless I'm misunderstanding your intention. That part is
> > > related to the kernel internal representation and could be handled
> > > during linearization.
> > 
> > So what would you suggest?
> > Add support for translating double to mpz_t?
> > What precisions would you support?
> 
> So I've started to generalize the proposed precision type
> into type_float which would support 0.000000001 as smallest value.

Sounds good.

> Does that seem ok or would you use a different precision?
> (If so, what & why?)

Seems reasonable for this case as 0.000000000232 is the smallest value
in 32 bit representation.

> Thanks!
> 
> > What should happen when user asks for meta random 42.23 ?
> 
> That still stands, where would this error be detect best?

It would be nice to handle this in expr_evaluate_value() by propagating
the limit from the RHS somehow. Right now we base our limits on the
available bits, we'd also need a numeric limit for this case.

I guess the question is related to how we're going to do the mapping
to 32 bit integers. Define a global mapping that is valid for all floats?
Then the normal bit based range check would work. Not sure if that makes
sense though.

You're way might have been the better one after all.

[PATCH nft 3/3] tests: add test cases for meta random

[Florian Westphal]

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

diff --git a/tests/py/any/meta.t b/tests/py/any/meta.t
index c10297a..6298e5c 100644
--- a/tests/py/any/meta.t
+++ b/tests/py/any/meta.t
@@ -197,3 +197,9 @@ 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 random 0.999999999;ok;meta random <= 0.999999999
+meta random 0.5;ok;meta random <= 0.500000000
+meta random 0.001;ok;meta random <= 0.001000000
+meta random 0.000000001;ok;meta random <= 0.000000001
+meta random 0.0000000005;fail
diff --git a/tests/py/any/meta.t.payload b/tests/py/any/meta.t.payload
index 9f7a6d9..5ca13b0 100644
--- a/tests/py/any/meta.t.payload
+++ b/tests/py/any/meta.t.payload
@@ -754,3 +754,22 @@ ip test-ip4 output
   [ meta load oif => reg 9 ]
   [ lookup reg 1 set map%d dreg 0 ]
 
+# meta random 0.999999999
+ip test-ip4 input
+  [ meta load prandom => reg 1 ]
+  [ cmp lte reg 1 0xfbffffff ]
+
+# meta random 0.5
+ip test-ip4 input
+  [ meta load prandom => reg 1 ]
+  [ cmp lte reg 1 0x00000080 ]
+
+# meta random 0.001
+ip test-ip4 input
+  [ meta load prandom => reg 1 ]
+  [ cmp lte reg 1 0x37894100 ]
+
+# meta random 0.000000001
+ip test-ip4 input
+  [ meta load prandom => reg 1 ]
+  [ cmp lte reg 1 0x04000000 ]
-- 
2.4.10

Re: [PATCH nft 0/3] meta: random match for statistic sampling

[Pablo Neira Ayuso]

On Tue, Feb 02, 2016 at 12:18:58AM +0100, Florian Westphal wrote:
> Replacement for iptables -m statistic 'random' mode.
> I added it to meta match even though its not directly related to an skb
> member. We already have cpu match which isn't related to skb either and
> adding a new expression just for this seemed overkill.
> 
> If you'd rather like a new prandom expression just let me know and
> I can rework it.
> 
> There is also a libnftnl patch but its only so that debug output
> displays 'meta prandom' rather than 'meta unknown'.
> 
> Result after several minutes of constant flooding:
> 
> counter packets 2961796882 bytes 248790938088
> meta random <= 0.900000000 counter packets 2665649546 bytes 223914561864
> meta random <= 0.500000000 counter packets 1480856860 bytes 124391976240
> meta random <= 0.100000000 counter packets 296190072 bytes 24879966048
> meta random <= 0.010000000 counter packets 29618610 bytes 2487963240
> meta random <= 0.001000000 counter packets 2963660 bytes 248947440
> meta random <= 0.000100000 counter packets 295486 bytes 24820824
> meta random <= 0.000010000 counter packets 29450 bytes 2473800
> meta random <= 0.000001000 counter packets 2911 bytes 244524
> meta random <= 0.000000100 counter packets 267 bytes 22428
> meta random <= 0.000000010 counter packets 26 bytes 2184
> meta random <= 0.000000001 counter packets 4 bytes 336
> 
> ... so it seems to work as intended.
> 
> Let me know if you spot any issues with current approach.
> 
> Kernel part only does '*dest = prandom_u32()', I'll submit it once
> I know that this approach is deemed sane.

Fine with me.

I also started a patch to add nth and jhash support, but it's
incomplete. Laura (she's on Cc) also wanted to have these for her work
on modeling load balancer schedulers with nft.

Thanks.