[CFT] new tables for ipfw

[Alexander V. Chernikov]

On 14.08.2014 14:44, Luigi Rizzo wrote:
>
>
>
> On Thu, Aug 14, 2014 at 11:57 AM, Alexander V. Chernikov 
> <melifaro at yandex-team.ru <mailto:melifaro at 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 at yandex-team.ru <mailto:melifaro at yandex-team.ru>> 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​
>