Skip to contentSkip to conversation

meta: add random and probability match

PATCH In review Florian Westphal 2 participants 11 messages Jul 5, 2016 – Jul 18, 2016 netfilter

lore
Share & tools
lore

Florian Westphal

author maintainer
#0 lore raw

PATCH 1/3 meta: add random and probability match

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.

author maintainer
#1 lore raw

PATCH 1/3 meta: add random expression key

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.

---
 src/meta.c         | 6 ++++++
 src/parser_bison.y | 1 +
 2 files changed, 7 insertions(+)
src/meta.c +6 -0
index 75431a2..8b1a2fc 100644
@@ -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;
src/parser_bison.y +1 -0
index d7cba23..fdbfed9 100644
@@ -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; }
Signature · 1 line
2.7.3
maintainer Acked-by on v1 1/3
#2 lore raw

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

Quoted 4 lines · Florian Westphal

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

For instance one can now use

Quoted 8 lines

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.

Please, apply this patch.

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

Thanks.

author maintainer
#3 lore raw

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

Quoted 12 lines · Pablo Neira Ayuso
Quoted 11 lines · 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.

Quoted 8 lines
Quoted 1 line

Please, apply this patch.

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.

author maintainer
#4 lore raw

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

In reply to 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.

---
 include/meta.h     |  4 ++++
 src/meta.c         | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/parser_bison.y | 19 +++++++++++++++++++
 src/scanner.l      |  5 +++++
 4 files changed, 83 insertions(+)
include/meta.h +4 -0
index f25b147..aafd232 100644
@@ -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;
src/meta.c +55 -0

64 lines not on this page · raw message

src/parser_bison.y +19 -0
index fdbfed9..dceb90f 100644
@@ -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
src/scanner.l +5 -0
index 88669d0..29ffe94 100644
@@ -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);
Signature · 1 line
2.7.3
#5 lore raw

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

Quoted 8 lines · 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

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?

author maintainer
#6 lore raw

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

Quoted 11 lines · Pablo Neira Ayuso
Quoted 8 lines · 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

I don't like this asymmetry.

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

Quoted 2 lines

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.

#7 lore raw

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

Quoted 7 lines · Florian Westphal
Quoted 6 lines · Pablo Neira Ayuso
Quoted 5 lines · 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)

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

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.

Quoted 5 lines
Quoted 2 lines

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.

author maintainer
#8 lore raw

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

Quoted 3 lines · Pablo Neira Ayuso

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.

Quoted 8 lines
Quoted 2 lines

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.

#9 lore raw

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

Quoted 8 lines · Florian Westphal
Quoted 3 lines · Pablo Neira Ayuso

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.

Quoted 10 lines
Quoted 8 lines
Quoted 2 lines

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.

author maintainer
#10 lore raw

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

In reply to 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.

---
 src/meta.c                | 16 ++++++++++++++++
 src/netlink_delinearize.c | 30 ++++++++++++++++++++++++++----
 2 files changed, 42 insertions(+), 4 deletions(-)
src/meta.c +16 -0
index 2b0d5f0..bf8a430 100644
@@ -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
src/netlink_delinearize.c +26 -4
index 7735699..138132a 100644
@@ -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);
Signature · 1 line
2.7.3