[CFT] new tables for ipfw

[Alexander V. Chernikov]

Hello list.

(sorry for posting twice, patch seems to be too big to be posted as 
attachment).

I've been hacking ipfw for a while and It seems there is something ready 
to test/review in projects/ipfw branch.

Main user-visible changes are related to tables:

1) Tables are now identified by names, not numbers. There can be up to 
65k tables with up to 63-byte long names (*1).
2) Tables are now set-aware (default off), so you can switch/move them 
atomically with rules.
3) More functionality is supported (swap, lock, limits, user-level 
lookup, batched add/del) by generic table code.
4) New table types are added (flow) so you can match multiple packet 
fields at once.
5) Ability to add different type of lookup algorithms for particular 
table type has been added.
5) New table algorithms are added (cidr:hash, iface:array, number:array 
and flow:hash) to make certain types of lookup more effective.

6) No ABI breakage has happened: all functionality supported by old 
ipfw(8) remains functional. Old & new binaries can work together with 
the following restrictions:
* Tables named other than ^\d+$ are shown as table(65535) in ruleset in 
old binaries
* I'm a bit unsure about "lookup src-port|dst-port N" case, something 
may be broken here. Anyway, this can be fixed for MFC.

Some examples (see ipfw(8) manual page for the description):

   0:02 [2] zfscurr0# ipfw table fl2 create type 
flow:src-ip,proto,dst-port algo flow:hash
    0:02 [2] zfscurr0# ipfw table fl2 info
    +++ table(fl2), set(0) +++
     kindex: 0, type: flow:src-ip,proto,dst-port
     valtype: number, references: 0
     algorithm: flow:hash
     items: 0, size: 280
    0:02 [2] zfscurr0# ipfw table fl2 add 2a02:6b8::333,tcp,443 45000
    0:02 [2] zfscurr0# ipfw table fl2 add 10.0.0.92,tcp,80 22000
    0:02 [2] zfscurr0# ipfw table fl2 list
    +++ table(fl2), set(0) +++
    2a02:6b8::333,6,443 45000
    10.0.0.92,6,80 22000
    0:02 [2] zfscurr0# ipfw add 200 count tcp from me to 78.46.89.105 80 
flow 'table(fl2)'

    ipfw table mi_test create type cidr algo "cidr:hash masks=/30,/64"
    ipfw table mi_test add 10.0.0.8/30
    ipfw table mi_test add 2a02:6b8:b010::1/64 25

    # ipfw table si add 1.1.1.1/32 1111 2.2.2.2/32 2222
    added: 1.1.1.1/32 1111
    added: 2.2.2.2/32 2222
    # ipfw table si add 2.2.2.2/32 2200 4.4.4.4/32 4444
    exists: 2.2.2.2/32 2200
    added: 4.4.4.4/32 4444
    ipfw: Adding record failed: record already exists
    ^^^^^ Returns error but keeps inserted items
    # ipfw table si list
    +++ table(si), set(0) +++
    1.1.1.1/32 1111
    2.2.2.2/32 2222
    4.4.4.4/32 4444
    # ipfw table si atomic add 3.3.3.3/32 3333 4.4.4.4/32 4400 
5.5.5.5/32 5555
    added(reverted): 3.3.3.3/32 3333
    exists: 4.4.4.4/32 4400
    ignored: 5.5.5.5/32 5555
    ipfw: Adding record failed: record already exists
    ^^^^^ Returns error and reverts added records


IPFW internals has also changed significantly, mostly 
userland-interaction part.
Changing table ids to numbers resulted in format modification for most 
sockopt codes.
Old sopt format was compact, but very hard to extend (no versioning, 
inability to add more opcodes), so
1) All relevant opcodes were converted to TLV-based versioned 
IP_FW3-based codes.
2) The remaining opcodes (except NAT handlers) were also converted to be 
able to eliminate all older opcodes at once
3) All IP_FW3 handlers uses special API instead of calling sooptcopy* 
directly to ease adding another communication methods
4) struct ip_fw is now different for kernel and userland
5) tablearg value has been changed to 0 to ease future extensions
6) Batched add/delete has been added to tables code
7) Batched rule addition is coming soon (most of the changes has been 
already done)
8) interface tracking API has been added (started on demand) to permit 
effective interface tables operations

9) O(1) skipto cache (*2), currently turned on by default (eats 512K). 
This has to be made optional
10) Rule counters were separated from rule itself and made per-cpu. 
However, this part is not finished yet (problems with timestamps/api)
11) Make radix entries fit into 128 bytes
12) Make struct ip_fw more compact so more rules will fit into 64 bytes
13) Make interface tables use array of existing ifindexes for faster match

14) Several steps has been made towards making libipfw:
* most of new functions were separated into "parse/prepare/show and 
actuall-do-stuff" pieces.
* there are separate functions for parsing text string into "struct 
ip_fw" and printing "struct ip_fw" to supplied buffer.
15) Probably some more less significant/forgotten features

This is not final version: probably more documentation/style is 
required, there are definitely some uncaught bugs, and so on.

However, test/feedback/review is welcome.

All these changes are available in projects/ipfw branch (synced to 
recent -HEAD), but may be easily applied to recent 9/10 (at least kernel 
part).
Branch: svn://svn.freebsd.org/base/projects/ipfw
Web: http://svnweb.freebsd.org/base/projects/ipfw/
Today's patch to -HEAD is available at
http://static.ipfw.ru/patches/ipfw_tables3.diff