[PKT_SCHED]: improve hashing performance of cls_fw
authorThomas Graf <tgraf@suug.ch>
Mon, 25 Apr 2005 03:19:54 +0000 (20:19 -0700)
committerDavid S. Miller <davem@davemloft.net>
Mon, 25 Apr 2005 03:19:54 +0000 (20:19 -0700)
commitc5c13fafd6548fe36b8fe9285c1912fcf96379f4
tree892a1f3c6fa74e2b75c2278c44b58a8813f770cc
parent0d3d077cd4f1154e63a9858e47fe3fb1ad0c03e5
[PKT_SCHED]: improve hashing performance of cls_fw

Calculate hashtable size to fit into a page instead of a hardcoded
256 buckets hash table. Results in a 1024 buckets hashtable on
most systems.

Replace old naive extract-8-lsb-bits algorithm with a better
algorithm xor'ing 3 or 4 bit fields at the size of the hashtable
array index in order to improve distribution if the majority of
the lower bits are unused while keeping zero collision behaviour
for the most common use case.

Thanks to Wang Jian <lark@linux.net.cn> for bringing this issue
to attention and to Eran Mann <emann@mrv.com> for the initial
idea for this new algorithm.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
Signed-off-by: David S. Miller <davem@davemloft.net>
net/sched/cls_fw.c