[NETFILTER] xt_hashlimit : speedups hash_dst()

[NETFILTER] xt_hashlimit : speedups hash_dst()

[Eric Dumazet]

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

1) Using jhash2() instead of jhash() is a litle bit faster if applicable.

2) Thanks to jhash, hash value uses full 32 bits.
    Instead of returning hash % size (implying a divide)
    we return the high 32 bits of the (hash * size) that will
    give results between [0 and size-1] and same hash distribution.

   On most cpus, a multiply is less expensive than a divide, by an order
   of magnitude.
  
Signed-off-by: Eric Dumazet <dada1@cosmosbay.com>



[-- Attachment #2: xt_hashlimit.patch --]
[-- Type: text/plain, Size: 855 bytes --]

diff --git a/net/netfilter/xt_hashlimit.c b/net/netfilter/xt_hashlimit.c
index 033d448..7cc04e8 100644
--- a/net/netfilter/xt_hashlimit.c
+++ b/net/netfilter/xt_hashlimit.c
@@ -105,7 +105,16 @@ static inline bool dst_cmp(const struct dsthash_ent *ent,
 static u_int32_t
 hash_dst(const struct xt_hashlimit_htable *ht, const struct dsthash_dst *dst)
 {
-	return jhash(dst, sizeof(*dst), ht->rnd) % ht->cfg.size;
+	u_int32_t hash = jhash2((const u32 *)dst,
+				sizeof(*dst)/sizeof(u32),
+				ht->rnd);
+	/*
+	 * Instead of returning hash % ht->cfg.size (implying a divide)
+	 * we return the high 32 bits of the (hash * ht->cfg.size) that will
+	 * give results between [0 and cfg.size-1] and same hash distribution,
+	 * but using a multiply, less expensive than a divide
+	 */
+	return ((u64)hash * ht->cfg.size) >> 32;
 }
 
 static struct dsthash_ent *

Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

[Patrick McHardy]

Eric Dumazet wrote:
> 1) Using jhash2() instead of jhash() is a litle bit faster if applicable.
> 
> 2) Thanks to jhash, hash value uses full 32 bits.
>    Instead of returning hash % size (implying a divide)
>    we return the high 32 bits of the (hash * size) that will
>    give results between [0 and size-1] and same hash distribution.
> 
>   On most cpus, a multiply is less expensive than a divide, by an order
>   of magnitude.


Clever :) Applied, thanks Eric.

Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

[David Miller]

From: Eric Dumazet <dada1@cosmosbay.com>
Date: Fri, 14 Dec 2007 12:09:31 +0100

> 1) Using jhash2() instead of jhash() is a litle bit faster if applicable.
> 
> 2) Thanks to jhash, hash value uses full 32 bits.
>     Instead of returning hash % size (implying a divide)
>     we return the high 32 bits of the (hash * size) that will
>     give results between [0 and size-1] and same hash distribution.
> 
>    On most cpus, a multiply is less expensive than a divide, by an order
>    of magnitude.
>   
> Signed-off-by: Eric Dumazet <dada1@cosmosbay.com>

As a side note, Jenkins performs nearly optimally (unlike
most traditional hash functions) with power of two hash
table sizes.

Using a pow2 hash table size would completely obviate the
issues solved by #2.

I don't know if that is feasible here in xt_hashlimit, but
if it is that is how we should solve this expensive
modulo.

Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

[Jarek Poplawski]

Eric Dumazet wrote, On 12/14/2007 12:09 PM:
...

> +	/*
> +	 * Instead of returning hash % ht->cfg.size (implying a divide)
> +	 * we return the high 32 bits of the (hash * ht->cfg.size) that will
> +	 * give results between [0 and cfg.size-1] and same hash distribution,
> +	 * but using a multiply, less expensive than a divide
> +	 */
> +	return ((u64)hash * ht->cfg.size) >> 32;

Are we sure of the same hash distribution? Probably I miss something,
but: if this 'hash' is well distributed on 32 bits, and ht->cfg.size
is smaller than 32 bits, e.g. 256 (8 bits), then this multiplication
moves to the higher 32 of u64 only max. 8 bits of the most significant
byte, and the other three bytes are never used, while division is
always affected by all four bytes...

Regards,
Jarek P.

Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

[Eric Dumazet]

Jarek Poplawski a écrit :
> Eric Dumazet wrote, On 12/14/2007 12:09 PM:
> ...
> 
>> +	/*
>> +	 * Instead of returning hash % ht->cfg.size (implying a divide)
>> +	 * we return the high 32 bits of the (hash * ht->cfg.size) that will
>> +	 * give results between [0 and cfg.size-1] and same hash distribution,
>> +	 * but using a multiply, less expensive than a divide
>> +	 */
>> +	return ((u64)hash * ht->cfg.size) >> 32;
> 
> Are we sure of the same hash distribution? Probably I miss something,
> but: if this 'hash' is well distributed on 32 bits, and ht->cfg.size
> is smaller than 32 bits, e.g. 256 (8 bits), then this multiplication
> moves to the higher 32 of u64 only max. 8 bits of the most significant
> byte, and the other three bytes are never used, while division is
> always affected by all four bytes...

Not sure what you are saying... but if size=256, then, yes, we want a final 
result between 0 and 255, so three bytes are nul.


'size' is the size of hashtable, its not a random 32bits value :)

-
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] xt_hashlimit : speedups hash_dst()

[Jarek Poplawski]

Jarek Poplawski wrote, On 12/14/2007 09:59 PM:

> Eric Dumazet wrote, On 12/14/2007 12:09 PM:
> ...
> 
>> +	/*
>> +	 * Instead of returning hash % ht->cfg.size (implying a divide)
>> +	 * we return the high 32 bits of the (hash * ht->cfg.size) that will
>> +	 * give results between [0 and cfg.size-1] and same hash distribution,
>> +	 * but using a multiply, less expensive than a divide
>> +	 */
>> +	return ((u64)hash * ht->cfg.size) >> 32;
> 
> Are we sure of the same hash distribution? Probably I miss something,
> but: if this 'hash' is well distributed on 32 bits, and ht->cfg.size
> is smaller than 32 bits, e.g. 256 (8 bits), then this multiplication
> moves to the higher 32 of u64 only max. 8 bits of the most significant
> byte, and the other three bytes are never used, while division is
> always affected by all four bytes...


OOPS! So, I've missed this division here is also affected by only one
byte, but from the other side - so, almost the same... It seems this
could have been replaced with masking from the beginning...

Sorry,
Jarek P.

Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

[Jarek Poplawski]

Eric Dumazet wrote, On 12/14/2007 10:37 PM:

> Jarek Poplawski a écrit :
>> Eric Dumazet wrote, On 12/14/2007 12:09 PM:
>> ...
>>
>>> +	/*
>>> +	 * Instead of returning hash % ht->cfg.size (implying a divide)
>>> +	 * we return the high 32 bits of the (hash * ht->cfg.size) that will
>>> +	 * give results between [0 and cfg.size-1] and same hash distribution,
>>> +	 * but using a multiply, less expensive than a divide
>>> +	 */
>>> +	return ((u64)hash * ht->cfg.size) >> 32;
>> Are we sure of the same hash distribution? Probably I miss something,
>> but: if this 'hash' is well distributed on 32 bits, and ht->cfg.size
>> is smaller than 32 bits, e.g. 256 (8 bits), then this multiplication
>> moves to the higher 32 of u64 only max. 8 bits of the most significant
>> byte, and the other three bytes are never used, while division is
>> always affected by all four bytes...
> 
> Not sure what you are saying... but if size=256, then, yes, we want a final 
> result between 0 and 255, so three bytes are nul.

Eric, it would be nice to acknowledge David's suggestion that this hash
size is always power of two here, because otherwise at least your words
about the same hash distribution according to the "%" variant could be
wrong (but I don't say the final result would be wrong). Maybe I mix
up these sizes, but it seems this could be set by a user, and I didn't
find anything about this power of two necessity?

Regards,
Jarek P.
-
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] xt_hashlimit : speedups hash_dst()

[Eric Dumazet]

Jarek Poplawski a écrit :
> Eric Dumazet wrote, On 12/14/2007 10:37 PM:
> 
>> Jarek Poplawski a écrit :
>>> Eric Dumazet wrote, On 12/14/2007 12:09 PM:
>>> ...
>>>
>>>> +	/*
>>>> +	 * Instead of returning hash % ht->cfg.size (implying a divide)
>>>> +	 * we return the high 32 bits of the (hash * ht->cfg.size) that will
>>>> +	 * give results between [0 and cfg.size-1] and same hash distribution,
>>>> +	 * but using a multiply, less expensive than a divide
>>>> +	 */
>>>> +	return ((u64)hash * ht->cfg.size) >> 32;
>>> Are we sure of the same hash distribution? Probably I miss something,
>>> but: if this 'hash' is well distributed on 32 bits, and ht->cfg.size
>>> is smaller than 32 bits, e.g. 256 (8 bits), then this multiplication
>>> moves to the higher 32 of u64 only max. 8 bits of the most significant
>>> byte, and the other three bytes are never used, while division is
>>> always affected by all four bytes...
>> Not sure what you are saying... but if size=256, then, yes, we want a final 
>> result between 0 and 255, so three bytes are nul.
> 
> Eric, it would be nice to acknowledge David's suggestion that this hash
> size is always power of two here, because otherwise at least your words
> about the same hash distribution according to the "%" variant could be
> wrong (but I don't say the final result would be wrong). Maybe I mix
> up these sizes, but it seems this could be set by a user, and I didn't
> find anything about this power of two necessity?
> 

size is not a power of two here.

I prefer to let admins chose their size, since it makes attacker life more 
difficult :)

For example, I can tell you I have a server, were size is between 2.000.000 
and 3.500.000, I dont want to be forced to use 2097152

A multiply is cheap, at least on current hardware.


-
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] xt_hashlimit : speedups hash_dst()

[David Miller]

From: Eric Dumazet <dada1@cosmosbay.com>
Date: Sat, 15 Dec 2007 12:04:47 +0100

> I prefer to let admins chose their size, since it makes attacker life more 
> difficult :)
> 
> For example, I can tell you I have a server, were size is between 2.000.000 
> and 3.500.000, I dont want to be forced to use 2097152
> 
> A multiply is cheap, at least on current hardware.

I agree, and I see nothing wrong with Eric's patch and it
should be merged ASAP.

Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

[Patrick McHardy]

David Miller wrote:
> From: Eric Dumazet <dada1@cosmosbay.com>
> Date: Sat, 15 Dec 2007 12:04:47 +0100
> 
>> I prefer to let admins chose their size, since it makes attacker life more 
>> difficult :)
>>
>> For example, I can tell you I have a server, were size is between 2.000.000 
>> and 3.500.000, I dont want to be forced to use 2097152
>>
>> A multiply is cheap, at least on current hardware.
> 
> I agree, and I see nothing wrong with Eric's patch and it
> should be merged ASAP.


I have it queued for 2.6.25 - would you like me to send it
for 2.6.24?

Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

[Sami Farin]

On Sat, Dec 15, 2007 at 21:42:19 -0800, David Miller wrote:
> From: Eric Dumazet <dada1@cosmosbay.com>
> Date: Sat, 15 Dec 2007 12:04:47 +0100
> 
> > I prefer to let admins chose their size, since it makes attacker life more 
> > difficult :)
> > 
> > For example, I can tell you I have a server, were size is between 2.000.000 
> > and 3.500.000, I dont want to be forced to use 2097152
> > 
> > A multiply is cheap, at least on current hardware.
> 
> I agree, and I see nothing wrong with Eric's patch and it
> should be merged ASAP.

You could do the same optimization for 
net/netfilter/nf_conntrack_core.c:__hash_conntrack() , too.

-- 
Do what you love because life is too short for anything else.

Re: [NETFILTER] xt_hashlimit : speedups hash_dst()

[Patrick McHardy]

Sami Farin wrote:
> On Sat, Dec 15, 2007 at 21:42:19 -0800, David Miller wrote:
>> From: Eric Dumazet <dada1@cosmosbay.com>
>> Date: Sat, 15 Dec 2007 12:04:47 +0100
>>
>>> I prefer to let admins chose their size, since it makes attacker life more 
>>> difficult :)
>>>
>>> For example, I can tell you I have a server, were size is between 2.000.000 
>>> and 3.500.000, I dont want to be forced to use 2097152
>>>
>>> A multiply is cheap, at least on current hardware.
>> I agree, and I see nothing wrong with Eric's patch and it
>> should be merged ASAP.
> 
> You could do the same optimization for 
> net/netfilter/nf_conntrack_core.c:__hash_conntrack() , too.


Yes, I already took care of that for conntrack and other netfilter
non-power-of-two hashes.