meta: add random and probability match
Florian Westphal
maintainerPATCH 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.
Florian Westphal
maintainerPATCH 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
@@ -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
@@ -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
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.
Signed-off-by Florian Westphal <[email protected]>
Please, apply this patch.
We can later on revisit the probability scaling, so keep 2/3 and 3/3 back by now.
Thanks.
Florian Westphal
maintainerRe: [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
Signed-off-by Florian Westphal <[email protected]>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.
Florian Westphal
maintainerPATCH 2/3 meta: add short-hand mnemonic for probalistic matching
In reply to Florian WestphalAllow 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
@@ -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
@@ -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
@@ -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
Pablo Neira Ayuso
maintainerRe: [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?
Florian Westphal
maintainerRe: [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 <= 4294967I 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_statisticsoffers?
Nothing, but the meta random might be interesting to e.g. set random (ct)mark for load balancing purposes.
Pablo Neira Ayuso
maintainerRe: [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 <= 4294967I 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_statisticsoffers?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.
Florian Westphal
maintainerRe: [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_USERDATAso 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.
Pablo Neira Ayuso
maintainerRe: [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_USERDATAso 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.
Florian Westphal
maintainerPATCH 3/3 netlink_delinearize, meta: show meta prandom <= value as probability mnemonic
In reply to Florian WestphalDuring delinearization, check if we're looking at an expression statement of the form
OP_LTEMETA_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
@@ -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
@@ -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