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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
