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

[emann@xxxxxxx (Eran Mann)]

Thomas Graf wrote:
> 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.

Maybe you could add to the list of options a XOR of bytes hash, 
something like:
static inline u8 bytes_xor_u32( u32 key )
{
	u8 *dummy_array = (u8 *)&key;
	u8 hash = dummy_array[0] ^ dummy_array[1] ^
		  dummy_array[2] ^ dummy_array[3];

        return hash;
}

--
Eran Mann
MRV International
www.mrv.com