From owner-freebsd-net@FreeBSD.ORG Thu Aug 14 10:57:31 2014 Return-Path: Delivered-To: freebsd-net@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 7DE113A0; Thu, 14 Aug 2014 10:57:31 +0000 (UTC) Received: from forward-corp1e.mail.yandex.net (forward-corp1e.mail.yandex.net [IPv6:2a02:6b8:0:202::10]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "forwards.mail.yandex.net", Issuer "Certum Level IV CA" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 2691E255B; Thu, 14 Aug 2014 10:57:31 +0000 (UTC) Received: from smtpcorp4.mail.yandex.net (smtpcorp4.mail.yandex.net [95.108.252.2]) by forward-corp1e.mail.yandex.net (Yandex) with ESMTP id C7DA264057F; Thu, 14 Aug 2014 14:57:17 +0400 (MSK) Received: from smtpcorp4.mail.yandex.net (localhost [127.0.0.1]) by smtpcorp4.mail.yandex.net (Yandex) with ESMTP id 91D3F2C05E8; Thu, 14 Aug 2014 14:57:17 +0400 (MSK) Received: from unknown (unknown [2a02:6b8:0:401:222:4dff:fe50:cd2f]) by smtpcorp4.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id GSBR0eaIlo-vHIuD88D; Thu, 14 Aug 2014 14:57:17 +0400 (using TLSv1 with cipher AES128-SHA (128/128 bits)) (Client certificate not present) X-Yandex-Uniq: 91582161-a429-4f64-ac2f-2c09a2800245 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex-team.ru; s=default; t=1408013837; bh=C+koB9qYLL8VFaE+z35vJXaKL3HUkLAZlQGsbLzMFeY=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type; b=wOSECESQV0uOrFbR6net5+GTv26/yo/kmk5NanHYbdGlfYNmE/TyUl1GIegPKdK7X dkGansgFFMiCcC/FKckFhOHHskeprosAp3NSwvYlizJ4oWTbxdnWRgupTZy6fP6r7M Hv/iJy7CfdoSPQqm7SZed1y92p9PRud5/H8p/rSA= Authentication-Results: smtpcorp4.mail.yandex.net; dkim=pass header.i=@yandex-team.ru Message-ID: <53EC960A.1030603@yandex-team.ru> Date: Thu, 14 Aug 2014 14:57:14 +0400 From: "Alexander V. Chernikov" User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0 MIME-Version: 1.0 To: Luigi Rizzo Subject: Re: [CFT] new tables for ipfw References: <53EBC687.9050503@yandex-team.ru> <53EC880B.3020903@yandex-team.ru> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Content-Filtered-By: Mailman/MimeDel 2.1.18-1 Cc: "freebsd-net@freebsd.org" , Luigi Rizzo , "Andrey V. Elsukov" , freebsd-ipfw X-BeenThere: freebsd-net@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: Networking and TCP/IP with FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 14 Aug 2014 10:57:31 -0000 On 14.08.2014 14:44, Luigi Rizzo wrote: > > > > On Thu, Aug 14, 2014 at 11:57 AM, Alexander V. Chernikov > > wrote: > > On 14.08.2014 13:23, Luigi Rizzo wrote: >> >> >> >> On Wed, Aug 13, 2014 at 10:11 PM, Alexander V. Chernikov >> > wrote: >> >> Hello list. >> >> I've been hacking ipfw for a while and It seems there is >> something ready to test/review in projects/ipfw branch. >> >> >> ​this is a fantastic piece of work, thanks for doing it and for >> integrating the feedback. >> ​ >> I have some detailed feedback that will send you privately, >> but just a curiosity: >> >> ​...​ >> >> Some examples (see ipfw(8) manual page for the description): >> >> ​... >> >> >> ipfw table mi_test create type cidr algo "cidr:hash >> masks=/30,/64" >> >> >> ​why do we need to specify mask lengths in the above​ ? > Well, since we're hashing IP we have to know mask to cut host bits > in advance. > (And the real reason is that I'm too lazy to implement > hierarchical matching (check /32, then /31, then /30) like how, > for example, > > > ​oh well for that we should use cidr:radix > > Research results have never shown a strong superiority of > hierarchical hash tables over good radix implementations, > and in those cases one usually adopts partial prefix > expansion so you only have, say, masks that are a > multiple of 2..8 bits so you only need a small number of > hash lookups. Definitely, especially for IPv6. So I was actually thinking about covering some special sparse cases (e.g. someone having a bunch of /32 and a bunch of /30 and that's all). Btw, since we're talking about "good radix implementation": what license does DXR have? :) Is it OK to merge it as another cidr implementation? > > ​cheers > luigi​ >