[iptables] extensions: libxt_statistic: Complete nft translator

Submitted by Phil Sutter on March 13, 2017, 4:01 p.m.

Details

Message ID 20170313160153.21120-1-phil@nwl.cc
State RFC
Delegated to: Pablo Neira
Headers show

Commit Message

Phil Sutter March 13, 2017, 4:01 p.m.
This was missing a translation for random mode. The substitute should
mimick what iptables and xt_statistic kernel module do:

- iptables takes p in [0.0; 1.0] as probability of a packet to pass,
  then passes p' = lround(p * 0x80000000) to kernel.
- Kernel takes random r in [0; 0x7FFFFFFF] and matches packet if r < p'.

The nftables numgen expression works differently:

- nft takes 32bit int n (RHS) and 32bit modulo m and passes both to
  kernel.
- Kernel takes random r in [0; m[ and compares it to n to decide if
  packet matches.

So in order to replicate the r < p' condition of xt_statistic, choose
m = 0x80000000, op = OP_LT and n = p'.

In order to not generate unnecessarily big numbers, divide m and n by
gcd(m, n) before printing the nft rule.

Here are a few example translations:

$ iptables-translate -A INPUT -m statistic --mode random --probability 0.25
nft add rule ip filter INPUT numgen random mod 0x4 < 0x1 counter

$ iptables-translate -A INPUT -m statistic --mode random --probability 0.5
nft add rule ip filter INPUT numgen random mod 0x2 < 0x1 counter

$ iptables-translate -A INPUT -m statistic --mode random --probability 0.75
nft add rule ip filter INPUT numgen random mod 0x4 < 0x3 counter

$ iptables-translate -A INPUT -m statistic --mode random --probability 0.33
nft add rule ip filter INPUT numgen random mod 0x20000000 < 0xa8f5c29 counter

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
In general, I don't think the code is correct: To really match the
requested probability, an op of '<=' should be generated instead of '<'.
But if I'm not mistaken, this is actually a problem of xt_statistic and
not the converter's.
---
 extensions/libxt_statistic.c | 31 ++++++++++++++++++++++++++++++-
 1 file changed, 30 insertions(+), 1 deletion(-)

Comments

Pablo Neira March 13, 2017, 4:53 p.m.
On Mon, Mar 13, 2017 at 05:01:53PM +0100, Phil Sutter wrote:
[...]
> The nftables numgen expression works differently:

Phil, if you think we need a 1:1 mapping so iptables users moving to
nftables don't get confused, I'll be fine to take an update to
nft_numgen so we accomodate a new NFT_NG_PROBABILISTIC mode or so.

Thanks!
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Phil Sutter March 14, 2017, 2:11 p.m.
On Mon, Mar 13, 2017 at 05:53:53PM +0100, Pablo Neira Ayuso wrote:
> On Mon, Mar 13, 2017 at 05:01:53PM +0100, Phil Sutter wrote:
> [...]
> > The nftables numgen expression works differently:
> 
> Phil, if you think we need a 1:1 mapping so iptables users moving to
> nftables don't get confused, I'll be fine to take an update to
> nft_numgen so we accomodate a new NFT_NG_PROBABILISTIC mode or so.

Well, implementing the translator wasn't exactly trivial, but in general
I don't think numgen is particularly hard to use. Of course an explicit
probability mode might make things easier, but then I guess it wouldn't
fit into the LHS/RHS scheme anymore. So I personally don't care, but if
you see use in implementing it just let me know and I'll adjust the
converter to make use of it. :)

Cheers, Phil
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Pablo Neira March 15, 2017, 11:01 a.m.
On Tue, Mar 14, 2017 at 03:11:12PM +0100, Phil Sutter wrote:
> On Mon, Mar 13, 2017 at 05:53:53PM +0100, Pablo Neira Ayuso wrote:
> > On Mon, Mar 13, 2017 at 05:01:53PM +0100, Phil Sutter wrote:
> > [...]
> > > The nftables numgen expression works differently:
> > 
> > Phil, if you think we need a 1:1 mapping so iptables users moving to
> > nftables don't get confused, I'll be fine to take an update to
> > nft_numgen so we accomodate a new NFT_NG_PROBABILISTIC mode or so.
> 
> Well, implementing the translator wasn't exactly trivial, but in general
> I don't think numgen is particularly hard to use. Of course an explicit
> probability mode might make things easier, but then I guess it wouldn't
> fit into the LHS/RHS scheme anymore.

Right, we would need a specific statement for this.

Question is how useful this can be as statement. The usecases I found
for this are:

1) Load balancing, which is already covered by numgen via maps.
2) Simulate packet loss.

With a statement we could combine this probability thing with flow
tables, but still I wonder how useful can be to match packets using
probability at a per-flow level, a.k.a. hashprobability.

Florian already sent a patch to add an alias for this [1], problem is
that this break symmetry between what we add to the kernel and what we
may get, and that is going to break the rule deletion by description.

Just a brain dump on this in case anyone want to spend jiffies on
this.

[1] https://patchwork.ozlabs.org/patch/591534/
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Pablo Neira March 22, 2017, 1:27 p.m.
On Wed, Mar 15, 2017 at 12:01:27PM +0100, Pablo Neira Ayuso wrote:
> On Tue, Mar 14, 2017 at 03:11:12PM +0100, Phil Sutter wrote:
> > On Mon, Mar 13, 2017 at 05:53:53PM +0100, Pablo Neira Ayuso wrote:
> > > On Mon, Mar 13, 2017 at 05:01:53PM +0100, Phil Sutter wrote:
> > > [...]
> > > > The nftables numgen expression works differently:
> > > 
> > > Phil, if you think we need a 1:1 mapping so iptables users moving to
> > > nftables don't get confused, I'll be fine to take an update to
> > > nft_numgen so we accomodate a new NFT_NG_PROBABILISTIC mode or so.
> > 
> > Well, implementing the translator wasn't exactly trivial, but in general
> > I don't think numgen is particularly hard to use. Of course an explicit
> > probability mode might make things easier, but then I guess it wouldn't
> > fit into the LHS/RHS scheme anymore.
> 
> Right, we would need a specific statement for this.
> 
> Question is how useful this can be as statement. The usecases I found
> for this are:
> 
> 1) Load balancing, which is already covered by numgen via maps.
> 2) Simulate packet loss.

This packet loss simulation can be useful at ingress in testing
environments, I found people on the Internet using it for this
purpose.

> With a statement we could combine this probability thing with flow
> tables, but still I wonder how useful can be to match packets using
> probability at a per-flow level, a.k.a. hashprobability.
> 
> Florian already sent a patch to add an alias for this [1], problem is
> that this break symmetry between what we add to the kernel and what we
> may get, and that is going to break the rule deletion by description.
> 
> Just a brain dump on this in case anyone want to spend jiffies on
> this.
> 
> [1] https://patchwork.ozlabs.org/patch/591534/

Another idea for this:

I think we can probably map this probability thing to
NFT_META_PRANDOM, which is a bit hopeless these days that we got the
numgen expression. What I'm proposing is to replace the 'meta random'
thing to 'meta probability' by using the patch above Florian made
before v0.8 gets out.

This doesn't allow us though to use probability from the flow table,
so this approach doesn't allow for 'hashprobability' (think of this as
iptables hashlimit, we don't need specific extensions anymore, note
that the flow table thing allow us to provide these composites). If we
want to support this approach, then the single statement, as you
mentioned, is the way to go.
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch hide | download patch | download mbox

diff --git a/extensions/libxt_statistic.c b/extensions/libxt_statistic.c
index 4f3341a3d1162..9e84374257641 100644
--- a/extensions/libxt_statistic.c
+++ b/extensions/libxt_statistic.c
@@ -133,15 +133,44 @@  static void statistic_save(const void *ip, const struct xt_entry_match *match)
 	print_match(info, "--");
 }
 
+/* divide *a and *b by gcd(*a, *b) */
+static void gcd_div(__u32 *a, __u32 *b)
+{
+	__u32 tmp, nom, denom;
+
+	if (a > b) {
+		nom = *a;
+		denom = *b;
+	} else {
+		nom = *b;
+		denom = *a;
+	}
+
+	while (denom != 0) {
+		tmp = nom % denom;
+		nom = denom;
+		denom = tmp;
+	}
+
+	*a /= nom;
+	*b /= nom;
+}
+
 static int statistic_xlate(struct xt_xlate *xl,
 			   const struct xt_xlate_mt_params *params)
 {
 	const struct xt_statistic_info *info =
 		(struct xt_statistic_info *)params->match->data;
+	__u32 mod = 0x80000000, prob = info->u.random.probability;
 
 	switch (info->mode) {
 	case XT_STATISTIC_MODE_RANDOM:
-		return 0;
+		gcd_div(&prob, &mod);
+		xt_xlate_add(xl, "numgen random mod 0x%x %s 0x%x",
+			     mod,
+			     info->flags & XT_STATISTIC_INVERT ? ">=" : "<",
+			     prob);
+		break;
 	case XT_STATISTIC_MODE_NTH:
 		xt_xlate_add(xl, "numgen inc mod %u %s%u",
 			     info->u.nth.every + 1,