From owner-freebsd-ipfw@FreeBSD.ORG Wed Dec 6 11:54:43 2006 Return-Path: X-Original-To: freebsd-ipfw@freebsd.org Delivered-To: freebsd-ipfw@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 0005A16A4B3 for ; Wed, 6 Dec 2006 11:54:42 +0000 (UTC) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (xorpc.icir.org [192.150.187.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id 02F5143CB5 for ; Wed, 6 Dec 2006 11:53:56 +0000 (GMT) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (localhost [127.0.0.1]) by xorpc.icir.org (8.12.11/8.13.6) with ESMTP id kB6BsfoJ058310; Wed, 6 Dec 2006 03:54:41 -0800 (PST) (envelope-from rizzo@xorpc.icir.org) Received: (from rizzo@localhost) by xorpc.icir.org (8.12.11/8.12.3/Submit) id kB6Bsfiw058309; Wed, 6 Dec 2006 03:54:41 -0800 (PST) (envelope-from rizzo) Date: Wed, 6 Dec 2006 03:54:41 -0800 From: Luigi Rizzo To: David Malone Message-ID: <20061206035441.A58131@xorpc.icir.org> References: <200612052010.36789.max@love2party.net> <20061205161744.A48319@xorpc.icir.org> <200612060451.58473.max@love2party.net> <20061206012931.A56288@xorpc.icir.org> <20061206113847.GA78558@walton.maths.tcd.ie> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <20061206113847.GA78558@walton.maths.tcd.ie>; from dwmalone@maths.tcd.ie on Wed, Dec 06, 2006 at 11:38:47AM +0000 Cc: Max Laier , freebsd-ipfw@freebsd.org Subject: Re: Better "hash_packet6" X-BeenThere: freebsd-ipfw@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: IPFW Technical Discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 06 Dec 2006 11:54:43 -0000 On Wed, Dec 06, 2006 at 11:38:47AM +0000, David Malone wrote: > On Wed, Dec 06, 2006 at 01:29:31AM -0800, Luigi Rizzo wrote: > > the top forwarding performance of a soekris is around 30-35kpps if > > i remember well - this translates in around 30us/packet all included. > > Is that the peak with ipfw2, IPv6 packets and dynamic rules turned on? maybe just ipfw2-ipv4 on and a single accept rule. that's to give an estimate of all the remaining packet processing costs that you were mentioning (interrupts etc.) > I've read the description of the Hsieh hash now and I'm pretty sure > it should be possible to produce lots of collisions fairly easily i am not saying that this is the only option, the page lists other hashes. > > (here we probably overflow some cache so the simple algorithm > > suffers a lot by increasing the number of different packets) > > I guess by default, this will always be a cache miss, because > the packet will just have been DMAed into memory? (Or, we will i think all of this is irrelevant if we go for a complex hash with many operations. Caching gives/saves is a constant overhead, which for a very simple hash maybe doubles the time (from 0.8 to 2us/pkt) but it is negligible on the 11us and 27us consumed by the hsieh and universal hashes. > recently have paid for the cache miss.) > > > Surely we need to experiment a bit more, but the cost > > is significant especially on low end boxes. > > I think we really need to test the code in-place and look at the > increase in CPU usage at different packet rates? That way the > relative overhead and cache conditions will be closet to realistic. > Do you have any suitable setup for this? no, and i think we should not bother on the cache effects as they are negligible here _and_ almost completely out of our control. If i may make a modest proposal, lets make the hashing algorithm a compile (or run) time option so people worried about collisions will be able to use the expensive function, and others can select a simpler one e.g. some simpler hash that xor's the addresses instead of sorting them. > (The other option, is to replace the use of hash tables for dynamic > rules with some other data structure that has better worst-case > behaviour.) with the 36 bytes strings we have to work on, i doubt we can find something that is not a memory killer yet runs in decent times! cheers luigi