From owner-freebsd-net@FreeBSD.ORG Thu Aug 14 11:15:44 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 A4A247A7; Thu, 14 Aug 2014 11:15:44 +0000 (UTC) Received: from mail-la0-x22d.google.com (mail-la0-x22d.google.com [IPv6:2a00:1450:4010:c03::22d]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 8B5922736; Thu, 14 Aug 2014 11:15:43 +0000 (UTC) Received: by mail-la0-f45.google.com with SMTP id ty20so867206lab.18 for ; Thu, 14 Aug 2014 04:15:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=5vQ9XaXkb2TRo8Op0LYVTotfjensTxi6TzsIoWM0Q/0=; b=ifr45WBFl4WJRP3yxwrr+FzzLwHKA/m1RhAgWgdJI0orulB5yVMJmVWpBCGoFC6tEX 4nqTQHGGnAaJ1NNFAJmzRvwearJqITADKCMYdlagnqdWFEXhjLPlURP1qwRX3dZWm688 2VH+KsFvA/XFSfOsXuxnUgyEJfX99ezdZHZH1fCz08ZsUggBFL6JotRUDvHGyvpRln/7 4K10JuvOXEy6EzwBtj1wk3ck/giZSPOg8GeuBPQ5CmCT6PflNpi6nPVxBCPzSnvmaYFW y52dyq0SereKQ36wXscYfMFNB5h4CGZZlrZ1txTB/RmT2T6mihv2Ar29EeRKZB6rNK6Y xAtA== MIME-Version: 1.0 X-Received: by 10.112.56.206 with SMTP id c14mr2605618lbq.27.1408014941450; Thu, 14 Aug 2014 04:15:41 -0700 (PDT) Sender: rizzo.unipi@gmail.com Received: by 10.114.244.2 with HTTP; Thu, 14 Aug 2014 04:15:41 -0700 (PDT) In-Reply-To: <53EC960A.1030603@yandex-team.ru> References: <53EBC687.9050503@yandex-team.ru> <53EC880B.3020903@yandex-team.ru> <53EC960A.1030603@yandex-team.ru> Date: Thu, 14 Aug 2014 13:15:41 +0200 X-Google-Sender-Auth: 0dMTaJr-5B2dBosDFQ5DsvybrVU Message-ID: Subject: Re: [CFT] new tables for ipfw From: Luigi Rizzo To: "Alexander V. Chernikov" Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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 11:15:44 -0000 On Thu, Aug 14, 2014 at 12:57 PM, Alexander V. Chernikov < melifaro@yandex-team.ru> wrote: > On 14.08.2014 14:44, Luigi Rizzo wrote: > > > > > On Thu, Aug 14, 2014 at 11:57 AM, Alexander V. Chernikov < > melifaro@yandex-team.ru> wrote: > >> On 14.08.2014 13:23, Luigi Rizzo wrote: >> >> >> >> >> On Wed, Aug 13, 2014 at 10:11 PM, Alexander V. Chernikov < >> melifaro@yandex-team.ru> wrote: >> >>> Hello list. >>> >>> I've been hacking ipfw for a while and It seems there is something read= y >>> to test/review in projects/ipfw branch. >>> >> >> =E2=80=8Bthis is a fantastic piece of work, thanks for doing it and for >> integrating the feedback. >> =E2=80=8B >> I have some detailed feedback that will send you privately, >> but just a curiosity: >> >> =E2=80=8B...=E2=80=8B >>> >>> Some examples (see ipfw(8) manual page for the description): >>> >>> >>> =E2=80=8B... >>> >>> >>> ipfw table mi_test create type cidr algo "cidr:hash masks=3D/30,/64" >>> >> >> =E2=80=8Bwhy do we need to specify mask lengths in the above=E2=80=8B ? >> >> 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, >> > > =E2=80=8Boh 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 coverin= g > 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? > "cidr" is a very ugly name, i'd rather use "addr" DXR has a =E2=80=8Bbsd license and of course it is possible to use it. You should ask Marko Zec for his latest version of the code (and probably make sure we have one copy of the code in the source tree). Speaking of features, one thing that would be nice is the ability for tables to reference the in-kernel tables (e.g. fibs, socket lists, interface lists...), perhaps in readonly mode. How complex do you think that would be ? cheers luigi