]> git.baikalelectronics.ru Git - kernel.git/commit
[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)
commitf8f8eb299c8c31a4da6118e785f3b7c3227a7307
tree892a1f3c6fa74e2b75c2278c44b58a8813f770cc
parente25976d660c5857ce7d6f1b72d0a6aff4171538d
[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