Re: [PATCH] improvement on net/sched/cls_fw.c's hash function

[Thomas Graf <tgraf@suug.ch>]

* Wang Jian <20050406143842.026B.LARK@linux.net.cn> 2005-04-06 14:45
> On 05 Apr 2005 12:11:35 -0400, jamal <hadi@cyberus.ca> wrote:
> > i.e if you fed the jenkins hash with 256 buckets - lets pick the number 1024 
> > samples of the data you showed earlier for how fwmark looks like,
> > how well would the result look like. 
> > And what if you fed it with something like 1024 incremental fwmark from 
> > say 1..1024?
> > 
> 
> The test result looks not good. See attached file.
> 
> So let's find a better way.

We need to provide some kind of option to the user so he can specify
the needs.  The & 0xFF will suit most just fine but has one essential
drawback which is that no distribution is done at all if the lower 8
bits are set to 0. For static marks this is no issue at all and even
for enumerated marks growing it takes quite some time to grow into
an area where it starts hurting. The problem obviously is if someone
splits the mark field into 2 parts and uses the upper 16 bits for
some special purpose just like you did. In such as case it would make
sense to either take all bits into account or let the user specify
a bitmask + shift.

So here is the same idea I posted before but revised:

Let the user specify one of the hash tables via a new TLV:
 - default: & 0xFF
 - ((mark & mask) >> shift) & 0xFF
 - jenkins for 16, 32, and 64 bits
 - FNV for 16, 32, and 64 bits

Why variations for type sizes? The chance of collisions reduces
a lot if the user exactly knows he'll never use more than 16bits
but 255 marks are not enough.

I'm cooking up a patch for this today together with a fix to
allow 64bit values for the mark.