From mboxrd@z Thu Jan 1 00:00:00 1970 From: Wang Jian Subject: Re: [PATCH] improvement on net/sched/cls_fw.c's hash function Date: Wed, 06 Apr 2005 21:01:38 +0800 Message-ID: <20050406205943.0290.LARK@linux.net.cn> References: <20050406143842.026B.LARK@linux.net.cn> <20050406123036.GO26731@postel.suug.ch> Mime-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Cc: hadi@cyberus.ca, netdev Return-path: To: Thomas Graf In-Reply-To: <20050406123036.GO26731@postel.suug.ch> Sender: netdev-bounce@oss.sgi.com Errors-to: netdev-bounce@oss.sgi.com List-Id: netdev.vger.kernel.org Hi Thomas Graf, On Wed, 6 Apr 2005 14:30:36 +0200, Thomas Graf wrote: > * Wang Jian <20050406143842.026B.LARK@linux.net.cn> 2005-04-06 14:45 > > On 05 Apr 2005 12:11:35 -0400, jamal 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. Given that no 1-hash-fit-all solution exists, I think your solution is quite elegant. -- lark