[NETFILTER][PATCH] Re: Question about the hashlimit network mask patch

[NETFILTER][PATCH] Re: Question about the hashlimit network mask patch

[Jan Engelhardt]

On Tuesday 2008-03-25 15:04, Iavor Stoev wrote:
>
> xtables-1.5.3 release works flawlessly but I found a strange behavior with 
> srcmask option.
>
> If you want to use /32 as a mask it doesn't work, however /31 works fine:
>
> --- xt_hashlimit.c.orig 2008-03-25 08:59:10.000000000 -0400
> +++ xt_hashlimit.c      2008-03-25 08:59:26.000000000 -0400
> @@ -466,7 +466,7 @@
>
> static inline __be32 maskl(__be32 a, unsigned int l)
> {
> -       return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));
> +       return htonl(ntohl(a) & ~(~(u_int32_t)0 >> (l-1)));
> }
>

I hate this. It's just stupid that  x>>32  is not 0, but, surprisingly, x.

This crap is _so_ common that the networking code is *sprinkled* with 
x==32 exceptions and it happens we still fall into the trap.

So this patch is needed ... but I had submitted one that entirely got 
rid of such pitfalls anyway ("Deploy a prefix len...") but that was not 
merged unfrotunately.

====
[NETFILTER]: xt_hashlimit: add workaround for >>32 case

Hardware surprisingly does nothing when a 32-bit right-shift is
to be done. Worse yet, compilers do not even work around it.

Signed-off-by: Jan Engelhardt <jengelh@computergmbh.de>

diff --git a/net/netfilter/xt_hashlimit.c b/net/netfilter/xt_hashlimit.c
index 5418ce5..1072174 100644
--- a/net/netfilter/xt_hashlimit.c
+++ b/net/netfilter/xt_hashlimit.c
@@ -466,7 +466,10 @@ static inline void rateinfo_recalc(struct dsthash_ent *dh, unsigned long now)

  static inline __be32 maskl(__be32 a, unsigned int l)
  {
-	return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));
+	if (l == 32)
+		return a;
+	else
+		return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));
  }

  #if defined(CONFIG_IP6_NF_IPTABLES) || defined(CONFIG_IP6_NF_IPTABLES_MODULE)

Re: [NETFILTER][PATCH] Re: Question about the hashlimit network mask patch

[Niki Denev]

On Wed, Mar 26, 2008 at 9:44 AM, Jan Engelhardt <jengelh@computergmbh.de> wrote:
>
> On Tuesday 2008-03-25 15:04, Iavor Stoev wrote:
> >
> > xtables-1.5.3 release works flawlessly but I found a strange behavior with
> > srcmask option.
> >
> > If you want to use /32 as a mask it doesn't work, however /31 works fine:
> >
> > --- xt_hashlimit.c.orig 2008-03-25 08:59:10.000000000 -0400
> > +++ xt_hashlimit.c      2008-03-25 08:59:26.000000000 -0400
> > @@ -466,7 +466,7 @@
> >
> > static inline __be32 maskl(__be32 a, unsigned int l)
> > {
> > -       return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));
> > +       return htonl(ntohl(a) & ~(~(u_int32_t)0 >> (l-1)));
> > }
> >
>
> I hate this. It's just stupid that  x>>32  is not 0, but, surprisingly, x.
>
> This crap is _so_ common that the networking code is *sprinkled* with
> x==32 exceptions and it happens we still fall into the trap.
>
> So this patch is needed ... but I had submitted one that entirely got
> rid of such pitfalls anyway ("Deploy a prefix len...") but that was not
> merged unfrotunately.
>
> ====
> [NETFILTER]: xt_hashlimit: add workaround for >>32 case
>
> Hardware surprisingly does nothing when a 32-bit right-shift is
> to be done. Worse yet, compilers do not even work around it.
>
> Signed-off-by: Jan Engelhardt <jengelh@computergmbh.de>
>
> diff --git a/net/netfilter/xt_hashlimit.c b/net/netfilter/xt_hashlimit.c
> index 5418ce5..1072174 100644
> --- a/net/netfilter/xt_hashlimit.c
> +++ b/net/netfilter/xt_hashlimit.c
> @@ -466,7 +466,10 @@ static inline void rateinfo_recalc(struct dsthash_ent *dh, unsigned long now)
>
>  static inline __be32 maskl(__be32 a, unsigned int l)
>  {
> -       return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));
> +       if (l == 32)
> +               return a;
> +       else
> +               return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));
>  }
>
>  #if defined(CONFIG_IP6_NF_IPTABLES) || defined(CONFIG_IP6_NF_IPTABLES_MODULE)

Hi Jan,

As far as i understand the maskl() function is called on every match.
wouldn't it be more appropriate(and faster) if all these checks and
bitshifts are done
in userspace by the iptables utility, so the kernel sees only the
"prepared" mask ready for AND-ing.
Of course this would require some mask_show() function in iptables to
convert it to bit count,
when we want to show the rules.

Regards,
Niki

Re: [NETFILTER][PATCH] Re: Question about the hashlimit network mask patch

[Michał Mirosław]

On Wed, Mar 26, 2008 at 08:44:20AM +0100, Jan Engelhardt wrote:
> +		return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));

BTW, isn't this way faster:

	return a & htonl(~(~(u_int32_t)0 >> l));

 -- Michal Miroslaw

Re: [NETFILTER][PATCH] Re: Question about the hashlimit network mask patch

[Jan Engelhardt]

On Wednesday 2008-03-26 11:28, Michał Mirosław wrote:

> On Wed, Mar 26, 2008 at 08:44:20AM +0100, Jan Engelhardt wrote:
>> +		return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));
>
> BTW, isn't this way faster:
>
> 	return a & htonl(~(~(u_int32_t)0 >> l));

Faster (and safe) is, and it was part of a previously suggested patches,

static inline __be32 maskl(__be32 a, unsigned int l)
{
 	return a & prefixlen_netmask_map[l].ip;
}

where prefixlen_netmask_map is a precomputed list of mask addresses.
--
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

Re: [NETFILTER][PATCH] Re: Question about the hashlimit network mask patch

[Patrick McHardy]

[-- Attachment #1: Type: text/plain, Size: 443 bytes --]

Jan Engelhardt wrote:
> [NETFILTER]: xt_hashlimit: add workaround for >>32 case
> 
> Hardware surprisingly does nothing when a 32-bit right-shift is
> to be done. Worse yet, compilers do not even work around it.

Thats because the C standard states that the result is undefined.
Anyways, I think this patch is slightly nicer because it
gets rid of the double negation and the %32 == 0 special-casing
for IPv6.

Do you want to add an ACKed-by?

[-- Attachment #2: x --]
[-- Type: text/plain, Size: 1553 bytes --]

commit 830213d52cb7a7e003335003bd56bf82d6153dcf
Author: Patrick McHardy <kaber@trash.net>
Date:   Tue Apr 1 14:48:04 2008 +0200

    [NETFILTER]: xt_hashlimit: fix mask calculation
    
    Shifts larger than the data type are undefined, don't try to shift
    an u32 by 32. Also remove some special-casing of bitmasks divisible
    by 32.
    
    Based on patch by Jan Engelhardt <jengelh@computergmbh.de>.

diff --git a/net/netfilter/xt_hashlimit.c b/net/netfilter/xt_hashlimit.c
index dc29007..40d344b 100644
--- a/net/netfilter/xt_hashlimit.c
+++ b/net/netfilter/xt_hashlimit.c
@@ -466,38 +466,25 @@ static inline void rateinfo_recalc(struct dsthash_ent *dh, unsigned long now)
 
 static inline __be32 maskl(__be32 a, unsigned int l)
 {
-	return htonl(ntohl(a) & ~(~(u_int32_t)0 >> l));
+	return l ? htonl(ntohl(a) & ~0 << (32 - l)) : 0;
 }
 
 #if defined(CONFIG_IP6_NF_IPTABLES) || defined(CONFIG_IP6_NF_IPTABLES_MODULE)
 static void hashlimit_ipv6_mask(__be32 *i, unsigned int p)
 {
 	switch (p) {
-	case 0:
-		i[0] = i[1] = 0;
-		i[2] = i[3] = 0;
-		break;
-	case 1 ... 31:
+	case 0 ... 31:
 		i[0] = maskl(i[0], p);
 		i[1] = i[2] = i[3] = 0;
 		break;
-	case 32:
-		i[1] = i[2] = i[3] = 0;
-		break;
-	case 33 ... 63:
+	case 32 ... 63:
 		i[1] = maskl(i[1], p - 32);
 		i[2] = i[3] = 0;
 		break;
-	case 64:
-		i[2] = i[3] = 0;
-		break;
-	case 65 ... 95:
+	case 64 ... 95:
 		i[2] = maskl(i[2], p - 64);
 		i[3] = 0;
-	case 96:
-		i[3] = 0;
-		break;
-	case 97 ... 127:
+	case 96 ... 127:
 		i[3] = maskl(i[3], p - 96);
 		break;
 	case 128:

Re: [NETFILTER][PATCH] Re: Question about the hashlimit network mask patch

[Jan Engelhardt]

On Tuesday 2008-04-01 14:49, Patrick McHardy wrote:

> Jan Engelhardt wrote:
>>  [NETFILTER]: xt_hashlimit: add workaround for >>32 case
>>
>>  Hardware surprisingly does nothing when a 32-bit right-shift is
>>  to be done. Worse yet, compilers do not even work around it.
>
> Thats because the C standard states that the result is undefined.
> Anyways, I think this patch is slightly nicer because it
> gets rid of the double negation and the %32 == 0 special-casing
> for IPv6.
>
> Do you want to add an ACKed-by?


The special casing for %32==0 in the IPv6 block was not a workaround for 
'>>32', but speed. Assuming the C code is already perfect and gets 
transformed 1:1 into assembly without any further optimization, the cost 
of the operation is 4 simple 'mov' instructions for %32==0, whereas 
calling maskl() will involve a fair number of operations (at least 27 by 
the count). [With your patch, maskl() is now 28 + a branch.]

Not that it really matters to me, I submitted patch (no replies yet)
that replaces it with the pfxlen static map anyway :->

> #if defined(CONFIG_IP6_NF_IPTABLES) || defined(CONFIG_IP6_NF_IPTABLES_MODULE)
> static void hashlimit_ipv6_mask(__be32 *i, unsigned int p)
> {
> 	switch (p) {
>-	case 0:
>-		i[0] = i[1] = 0;
>-		i[2] = i[3] = 0;
>-		break;
>-	case 1 ... 31:
>+	case 0 ... 31:
> 		i[0] = maskl(i[0], p);
> 		i[1] = i[2] = i[3] = 0;
> 		break;
>-	case 32:
>-		i[1] = i[2] = i[3] = 0;
>-		break;
>-	case 33 ... 63:
>+	case 32 ... 63:
> 		i[1] = maskl(i[1], p - 32);
> 		i[2] = i[3] = 0;
> 		break;
>-	case 64:
>-		i[2] = i[3] = 0;
>-		break;
>-	case 65 ... 95:
>+	case 64 ... 95:
> 		i[2] = maskl(i[2], p - 64);
> 		i[3] = 0;
>-	case 96:
>-		i[3] = 0;
>-		break;
>-	case 97 ... 127:
>+	case 96 ... 127:
> 		i[3] = maskl(i[3], p - 96);
> 		break;
> 	case 128:

Re: [NETFILTER][PATCH] Re: Question about the hashlimit network mask patch

[Patrick McHardy]

Jan Engelhardt wrote:
> On Tuesday 2008-04-01 14:49, Patrick McHardy wrote:
> 
>> Jan Engelhardt wrote:
>>>  [NETFILTER]: xt_hashlimit: add workaround for >>32 case
>>>
>>>  Hardware surprisingly does nothing when a 32-bit right-shift is
>>>  to be done. Worse yet, compilers do not even work around it.
>>
>> Thats because the C standard states that the result is undefined.
>> Anyways, I think this patch is slightly nicer because it
>> gets rid of the double negation and the %32 == 0 special-casing
>> for IPv6.
>>
>> Do you want to add an ACKed-by?
> 
> 
> The special casing for %32==0 in the IPv6 block was not a workaround for 
> '>>32', but speed. 

I'm aware of that.

> Assuming the C code is already perfect and gets 
> transformed 1:1 into assembly without any further optimization, the cost 
> of the operation is 4 simple 'mov' instructions for %32==0, whereas 
> calling maskl() will involve a fair number of operations (at least 27 by 
> the count). [With your patch, maskl() is now 28 + a branch.]

The "optimization" results in bigger code and more branches itself.
Just removing it without fixing maskl reduces code size by over 35%:

net/netfilter/xt_hashlimit.c:
   hashlimit_ipv6_mask | -103 # 274 -> 171
  1 function changed, 103 bytes removed

Fixing maskl bloats it up again, but still a net win:

   hashlimit_ipv6_mask |   -9 # 274 -> 265, size inlines: 71 -> 148
   hashlimit_init_dst  |   +6 # 589 -> 595, size inlines: 86 -> 106
  2 functions changed, 6 bytes added, 9 bytes removed, diff: -3

Just the maskl fix results in:

net/netfilter/xt_hashlimit.c:
   hashlimit_ipv6_mask |  +95 # 274 -> 369, size inlines: 71 -> 143
   hashlimit_init_dst  |   +6 # 589 -> 595, size inlines: 86 -> 106
  2 functions changed, 101 bytes added