Skip to contentSkip to conversation

xt_hashlimit : speedups hash_dst()

NETFILTER Eric Dumazet 5 participants 12 messages Dec 14, 2007 – Dec 17, 2007

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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.

net/netfilter/xt_hashlimit.c +10 -1
index 033d448..7cc04e8 100644
@@ -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 *
#1 lore raw
Quoted 9 lines · Eric Dumazet

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.

maintainer
#2 lore raw
In reply to Eric Dumazet

From: Eric Dumazet <[email protected]>
Date: Fri, 14 Dec 2007 12:09:31 +0100

Quoted 11 lines

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.

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.

#3 lore raw
In reply to Eric Dumazet

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

net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117

Quoted 7 lines
net/netfilter/xt_hashlimit.c +7 -0
+	/*
+	 * 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.

#4 lore raw
Quoted 17 lines · Jarek Poplawski

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

net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117

Quoted 7 lines
net/netfilter/xt_hashlimit.c +7 -0
+	/*
+	 * 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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#11 lore raw
In reply to Jarek Poplawski

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

Quoted 17 lines

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

net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117

Quoted 7 lines
net/netfilter/xt_hashlimit.c +7 -0
+	/*
+	 * 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.

#5 lore raw
In reply to Eric Dumazet

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

Quoted 18 lines
Quoted 16 lines · Jarek Poplawski

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

net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117

Quoted 7 lines
net/netfilter/xt_hashlimit.c +7 -0
+	/*
+	 * 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...

Quoted 2 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#6 lore raw
Quoted 19 lines · Jarek Poplawski

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

Quoted 17 lines
Quoted 16 lines · Jarek Poplawski

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

net/netfilter/xt_hashlimit.c static inline bool dst_cmp(const struct dsthash_ent *ent, · line 117

Quoted 7 lines
net/netfilter/xt_hashlimit.c +7 -0
+	/*
+	 * 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...

Quoted 9 lines
Quoted 1 line

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

maintainer
#7 lore raw

From: Eric Dumazet <[email protected]>
Date: Sat, 15 Dec 2007 12:04:47 +0100

Quoted 7 lines

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.

#8 lore raw
Quoted 11 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Sat, 15 Dec 2007 12:04:47 +0100

Quoted 5 lines

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?

#9 lore raw
In reply to David Miller
Quoted 6 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Sat, 15 Dec 2007 12:04:47 +0100

Quoted 3 lines

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

Quoted 7 lines
Quoted 4 lines

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.

Signature · 1 line
Do what you love because life is too short for anything else.
#10 lore raw
Quoted 6 lines · Sami Farin
Quoted 5 lines · David Miller

From: Eric Dumazet <[email protected]>
Date: Sat, 15 Dec 2007 12:04:47 +0100

Quoted 2 lines

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

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines

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.