Patchwork [3/7] netfilter: xt_HMARK: modulus is expensive for hash calculation

login
register
mail settings
Submitter Pablo Neira
Date May 16, 2012, 11:06 p.m.
Message ID <1337209604-3412-4-git-send-email-pablo@netfilter.org>
Download mbox | patch
Permalink /patch/159775/
State Accepted
Headers show

Comments

Pablo Neira - May 16, 2012, 11:06 p.m.
From: Pablo Neira Ayuso <pablo@netfilter.org>

Use:

((u64)(HASH_VAL * HASH_SIZE)) >> 32

as suggested by David S. Miller.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 net/netfilter/xt_HMARK.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
David Laight - May 17, 2012, 8:16 a.m.
> From: Pablo Neira Ayuso <pablo@netfilter.org>
> 
> Use:
> 
> ((u64)(HASH_VAL * HASH_SIZE)) >> 32
> 
> as suggested by David S. Miller.

That (u64) cast is very unlikely to have any effect.
If you want a 64 bit result from the product of two
32 bit values, you have to cast one of the 32 bit values
prior to the multiply - as in the patch below.

	David

> 
> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> ---
>  net/netfilter/xt_HMARK.c |    2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/net/netfilter/xt_HMARK.c b/net/netfilter/xt_HMARK.c
> index 5817d03..0a96a43 100644
> --- a/net/netfilter/xt_HMARK.c
> +++ b/net/netfilter/xt_HMARK.c
> @@ -109,7 +109,7 @@ hmark_hash(struct hmark_tuple *t, const 
> struct xt_hmark_info *info)
>  	hash = jhash_3words(t->src, t->dst, t->uports.v32, 
> info->hashrnd);
>  	hash = hash ^ (t->proto & info->proto_mask);
>  
> -	return (hash % info->hmodulus) + info->hoffset;
> +	return (((u64)hash * info->hmodulus) >> 32) + info->hoffset;
>  }
>  
>  static void
> -- 
> 1.7.10
> 
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 


--
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
Eric Dumazet - May 17, 2012, 8:39 a.m.
On Thu, 2012-05-17 at 09:16 +0100, David Laight wrote:
> > From: Pablo Neira Ayuso <pablo@netfilter.org>
> > 
> > Use:
> > 
> > ((u64)(HASH_VAL * HASH_SIZE)) >> 32
> > 
> > as suggested by David S. Miller.
> 
> That (u64) cast is very unlikely to have any effect.
> If you want a 64 bit result from the product of two
> 32 bit values, you have to cast one of the 32 bit values
> prior to the multiply - as in the patch below.

Hey, Changelog is a bit wrong (for several reasons) but code is correct.

return (((u64)hash * info->hmodulus) >> 32) + info->hoffset;



--
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 - May 17, 2012, 2:55 p.m.
On Thu, May 17, 2012 at 10:39:28AM +0200, Eric Dumazet wrote:
> On Thu, 2012-05-17 at 09:16 +0100, David Laight wrote:
> > > From: Pablo Neira Ayuso <pablo@netfilter.org>
> > > 
> > > Use:
> > > 
> > > ((u64)(HASH_VAL * HASH_SIZE)) >> 32
> > > 
> > > as suggested by David S. Miller.
> > 
> > That (u64) cast is very unlikely to have any effect.
> > If you want a 64 bit result from the product of two
> > 32 bit values, you have to cast one of the 32 bit values
> > prior to the multiply - as in the patch below.
> 
> Hey, Changelog is a bit wrong (for several reasons) but code is correct.
> 
> return (((u64)hash * info->hmodulus) >> 32) + info->hoffset;

Sorry, for the mistake in the changelog. I copied & pasted it from the
mailing list discussion.
--
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

diff --git a/net/netfilter/xt_HMARK.c b/net/netfilter/xt_HMARK.c
index 5817d03..0a96a43 100644
--- a/net/netfilter/xt_HMARK.c
+++ b/net/netfilter/xt_HMARK.c
@@ -109,7 +109,7 @@  hmark_hash(struct hmark_tuple *t, const struct xt_hmark_info *info)
 	hash = jhash_3words(t->src, t->dst, t->uports.v32, info->hashrnd);
 	hash = hash ^ (t->proto & info->proto_mask);
 
-	return (hash % info->hmodulus) + info->hoffset;
+	return (((u64)hash * info->hmodulus) >> 32) + info->hoffset;
 }
 
 static void