Iptables 1.3.1 still not very fast.

Iptables 1.3.1 still not very fast.

[Robert de Bath]

Okay, I'll admit is it a LOT faster that 1.2.11 it still seems to take a long 
time with big tables.

An example:
I have a program (I've called iptrange) that will take a file full of ip 
address ranges (192.168.42.10 192.168.42.25) and converts them into a set
of iptables chains that invokes another chain if the source (or dest) matches 
ie:

iptables -N CHECK
iptables -A CHECK -s 192.168.42.10/31 -j FOUND
iptables -A CHECK -s 192.168.42.12/30 -j FOUND
iptables -A CHECK -s 192.168.42.16/29 -j FOUND
iptables -A CHECK -s 192.168.42.24/31 -j FOUND

The good bit is that it will create a tree of subchains so that the
matching is efficient for large numbers of ip addresses.

This works well for a few hundred address ranges; I use it to match
recent 'evil' ips and ranges from dshield.org.

However, when I tried a 50000 range list from http://blocklist.org I
ran into problems.  After conversion it created 20000 chains with a
total of 70000 rules.  This tables took about an hour to load using
iptables-1.2.11!

Version 1.3.1 of libiptc is a LOT faster at about 5 minutes to do the
load. But this still seems very slow when it takes about half a second
to generate and print out the iptables rules to a script.

I hate to think how slow it would be with a million ranges; assuming it can be 
loaded it looks like it would be about 300000 chains, 1.3M
rules and about 100 rules checked per packet (to pick some figures out
of a single test) so it should be useable ...

BTW: iptables-restore is slower than my iptrange!

My problem is that I think that libiptc looks evil and I really don't
want to dive into messing with that code. So how can I help to make
libiptc run as fast as I'd like it to?

-- 
Rob.                          (Robert de Bath <robert$ @ debath.co.uk>)

Re: Iptables 1.3.1 still not very fast.

[Wang Jian]

Hi Robert de Bath,

It seems that your problem can be solved by using 'set' match. I didn't
use 'set' match, so I am not very sure. 'set' match is in pom-ng::base.

For your situation, to generate so many rules to just match on source
address is not efficient. In natural language, it is

  "Is this source address in a blacklist?"

and should be implemented this way as

  "Is this source address in a blacklist (hash table)?"

It has only one rule. And then, you can manipulate this hash table.
(IMHO, the hash table involved is simple and fast)

On Fri, 1 Apr 2005 22:52:25 +0100 (BST), Robert de Bath <list-netfilter@debath.co.uk> wrote:

> Okay, I'll admit is it a LOT faster that 1.2.11 it still seems to take a long 
> time with big tables.
> 
> An example:
> I have a program (I've called iptrange) that will take a file full of ip 
> address ranges (192.168.42.10 192.168.42.25) and converts them into a set
> of iptables chains that invokes another chain if the source (or dest) matches 
> ie:
> 
> iptables -N CHECK
> iptables -A CHECK -s 192.168.42.10/31 -j FOUND
> iptables -A CHECK -s 192.168.42.12/30 -j FOUND
> iptables -A CHECK -s 192.168.42.16/29 -j FOUND
> iptables -A CHECK -s 192.168.42.24/31 -j FOUND
> 
> The good bit is that it will create a tree of subchains so that the
> matching is efficient for large numbers of ip addresses.
> 
> This works well for a few hundred address ranges; I use it to match
> recent 'evil' ips and ranges from dshield.org.
> 
> However, when I tried a 50000 range list from http://blocklist.org I
> ran into problems.  After conversion it created 20000 chains with a
> total of 70000 rules.  This tables took about an hour to load using
> iptables-1.2.11!
> 
> Version 1.3.1 of libiptc is a LOT faster at about 5 minutes to do the
> load. But this still seems very slow when it takes about half a second
> to generate and print out the iptables rules to a script.
> 
> I hate to think how slow it would be with a million ranges; assuming it can be 
> loaded it looks like it would be about 300000 chains, 1.3M
> rules and about 100 rules checked per packet (to pick some figures out
> of a single test) so it should be useable ...
> 
> BTW: iptables-restore is slower than my iptrange!
> 
> My problem is that I think that libiptc looks evil and I really don't
> want to dive into messing with that code. So how can I help to make
> libiptc run as fast as I'd like it to?
> 
> -- 
> Rob.                          (Robert de Bath <robert$ @ debath.co.uk>)
> 



-- 
  lark

Re: Iptables 1.3.1 still not very fast.

[Peter Enderborg]

Wang Jian wrote:

>Hi Robert de Bath,
>
>It seems that your problem can be solved by using 'set' match. I didn't
>use 'set' match, so I am not very sure. 'set' match is in pom-ng::base.
>
>For your situation, to generate so many rules to just match on source
>address is not efficient. In natural language, it is
>
>  "Is this source address in a blacklist?"
>
>and should be implemented this way as
>
>  "Is this source address in a blacklist (hash table)?"
>
>It has only one rule. And then, you can manipulate this hash table.
>(IMHO, the hash table involved is simple and fast)
>
>On Fri, 1 Apr 2005 22:52:25 +0100 (BST), Robert de Bath <list-netfilter@debath.co.uk> wrote:
>
>  
>
Maybe a dumb question. But how do you hash on a range?

>>Okay, I'll admit is it a LOT faster that 1.2.11 it still seems to take a long 
>>time with big tables.
>>
>>An example:
>>I have a program (I've called iptrange) that will take a file full of ip 
>>address ranges (192.168.42.10 192.168.42.25) and converts them into a set
>>of iptables chains that invokes another chain if the source (or dest) matches 
>>ie:
>>
>>iptables -N CHECK
>>iptables -A CHECK -s 192.168.42.10/31 -j FOUND
>>iptables -A CHECK -s 192.168.42.12/30 -j FOUND
>>iptables -A CHECK -s 192.168.42.16/29 -j FOUND
>>iptables -A CHECK -s 192.168.42.24/31 -j FOUND
>>
>>The good bit is that it will create a tree of subchains so that the
>>matching is efficient for large numbers of ip addresses.
>>
>>This works well for a few hundred address ranges; I use it to match
>>recent 'evil' ips and ranges from dshield.org.
>>
>>However, when I tried a 50000 range list from http://blocklist.org I
>>ran into problems.  After conversion it created 20000 chains with a
>>total of 70000 rules.  This tables took about an hour to load using
>>iptables-1.2.11!
>>
>>Version 1.3.1 of libiptc is a LOT faster at about 5 minutes to do the
>>load. But this still seems very slow when it takes about half a second
>>to generate and print out the iptables rules to a script.
>>
>>I hate to think how slow it would be with a million ranges; assuming it can be 
>>loaded it looks like it would be about 300000 chains, 1.3M
>>rules and about 100 rules checked per packet (to pick some figures out
>>of a single test) so it should be useable ...
>>
>>BTW: iptables-restore is slower than my iptrange!
>>
>>My problem is that I think that libiptc looks evil and I really don't
>>want to dive into messing with that code. So how can I help to make
>>libiptc run as fast as I'd like it to?
>>
>>-- 
>>Rob.                          (Robert de Bath <robert$ @ debath.co.uk>)
>>
>>    
>>
>
>
>
>  
>


-- 
foo!

Re: Iptables 1.3.1 still not very fast.

[Patrick Schaaf]

> Maybe a dumb question. But how do you hash on a range?

Not a dumb question at all, but here's a dumb answer: you add each address
in the range. This is wholly practical for small ranges, and half way
practical for larger ranges which need to be configured only now and then.

Alternatively, in the context of ipset, you could implement a range or
set-of-ranges subtype of ipset, using suitable data structures,
which would be some kind of tree. For fully general set-of-ip-nets
matching, the data structure would most likely resemble what's used
in routing table implementations.

best regards
  Partick

Re[2]: Iptables 1.3.1 still not very fast.

[Wang Jian]

Hi Patrick Schaaf,

The best general practice here may be always using subnets. IP is IP/32,
iprange is IPs + Subnets + IPs then IP/32's + Subnets + IP/32's.

But best general practice is not best practice for special case. You not
dumb "add each address in the range" answer is a special case for small
set. 'set' match has ip hash to support this. If your sets are in the
same B class subnet, you'd better go this way for fastest lookup.

On Sat, 2 Apr 2005 07:41:12 +0200, Patrick Schaaf <bof@bof.de> wrote:

> > Maybe a dumb question. But how do you hash on a range?
> 
> Not a dumb question at all, but here's a dumb answer: you add each address
> in the range. This is wholly practical for small ranges, and half way
> practical for larger ranges which need to be configured only now and then.
> 
> Alternatively, in the context of ipset, you could implement a range or
> set-of-ranges subtype of ipset, using suitable data structures,
> which would be some kind of tree. For fully general set-of-ip-nets
> matching, the data structure would most likely resemble what's used
> in routing table implementations.
> 
> best regards
>   Partick



-- 
  lark

Re[2]: Iptables 1.3.1 still not very fast.

[Wang Jian]

Hi Peter Enderborg,

I am not expert on this front, so forgive me if I am wrong.

ip range can always be converted to some ips + some net/mask subnets.

Then another question: can 'set' handle overlapping and aggregation of
ip ranges, subnets, ips ?

The answer may be both yes and no. 'set' can be made to handle that, but
the best place to do is in user space.


On Sat, 02 Apr 2005 07:32:40 +0200, Peter Enderborg <pme@ufh.se> wrote:

> Wang Jian wrote:
> 
> >Hi Robert de Bath,
> >
> >It seems that your problem can be solved by using 'set' match. I didn't
> >use 'set' match, so I am not very sure. 'set' match is in pom-ng::base.
> >
> >For your situation, to generate so many rules to just match on source
> >address is not efficient. In natural language, it is
> >
> >  "Is this source address in a blacklist?"
> >
> >and should be implemented this way as
> >
> >  "Is this source address in a blacklist (hash table)?"
> >
> >It has only one rule. And then, you can manipulate this hash table.
> >(IMHO, the hash table involved is simple and fast)
> >
> >On Fri, 1 Apr 2005 22:52:25 +0100 (BST), Robert de Bath <list-netfilter@debath.co.uk> wrote:
> >
> >  
> >
> Maybe a dumb question. But how do you hash on a range?
> 
> >>Okay, I'll admit is it a LOT faster that 1.2.11 it still seems to take a long 
> >>time with big tables.
> >>
> >>An example:
> >>I have a program (I've called iptrange) that will take a file full of ip 
> >>address ranges (192.168.42.10 192.168.42.25) and converts them into a set
> >>of iptables chains that invokes another chain if the source (or dest) matches 
> >>ie:
> >>
> >>iptables -N CHECK
> >>iptables -A CHECK -s 192.168.42.10/31 -j FOUND
> >>iptables -A CHECK -s 192.168.42.12/30 -j FOUND
> >>iptables -A CHECK -s 192.168.42.16/29 -j FOUND
> >>iptables -A CHECK -s 192.168.42.24/31 -j FOUND
> >>
> >>The good bit is that it will create a tree of subchains so that the
> >>matching is efficient for large numbers of ip addresses.
> >>
> >>This works well for a few hundred address ranges; I use it to match
> >>recent 'evil' ips and ranges from dshield.org.
> >>
> >>However, when I tried a 50000 range list from http://blocklist.org I
> >>ran into problems.  After conversion it created 20000 chains with a
> >>total of 70000 rules.  This tables took about an hour to load using
> >>iptables-1.2.11!
> >>
> >>Version 1.3.1 of libiptc is a LOT faster at about 5 minutes to do the
> >>load. But this still seems very slow when it takes about half a second
> >>to generate and print out the iptables rules to a script.
> >>
> >>I hate to think how slow it would be with a million ranges; assuming it can be 
> >>loaded it looks like it would be about 300000 chains, 1.3M
> >>rules and about 100 rules checked per packet (to pick some figures out
> >>of a single test) so it should be useable ...
> >>
> >>BTW: iptables-restore is slower than my iptrange!
> >>
> >>My problem is that I think that libiptc looks evil and I really don't
> >>want to dive into messing with that code. So how can I help to make
> >>libiptc run as fast as I'd like it to?
> >>
> >>-- 
> >>Rob.                          (Robert de Bath <robert$ @ debath.co.uk>)
> >>
> >>    
> >>
> >
> >
> >
> >  
> >
> 
> 
> -- 
> foo!



-- 
  lark

Re: Iptables 1.3.1 still not very fast.

[Robert de Bath]

On Sat, 2 Apr 2005, Wang Jian wrote:

> Hi Robert,
>
> It seems that your problem can be solved by using 'set' match. I didn't
> use 'set' match, so I am not very sure. 'set' match is in pom-ng::base.

Okay, I've had a quick look at ipset and I think it could be made to work.
It appears that it can work in two modes that are useful here, ip-address
and net-address.

In ip-address mode each individual address has to be added to the hash
table for the example set from 'blocklist.org' this is around 600000000
addresses ... I do not have 2Gb of ram (minimum!) to, er, use on a hash
table!

NB: Yes that address list blacklists about 14% of the ipv4 space, I was
     looking for an evil example!

In net-address mode an ip+mask is converted into a single 32 bit value and
it can store different netmasks (despite the manpage).  This is okay if
you just want just networks but it cannot represent single IPs.  It would
still be necessary to convert the ip ranges to ip+mask notation though.

So you actually need two hashtables for the example 'blacklist' one in
each mode.  For an IP packet a single lookup is needed on the ip-address
hash but upto 30 lookups would be needed on the net-address hash.

Now my tree layout would result in about 20-40 rules scanned for a
single packet for 'the evil example'.

> For your situation, to generate so many rules to just match on source
> address is not efficient. In natural language, it is
>
>  "Is this source address in a blacklist?"
>
> and should be implemented this way as
>
>  "Is this source address in a blacklist (hash table)?"
>
> It has only one rule. And then, you can manipulate this hash table.
> (IMHO, the hash table involved is simple and fast)

... I would _hope_ the hashtable is faster ... it _should_ be ...
but with those complex hash algorithms I'm not sure.

If you're talking about efficency in terms of how easy it is to use
it's like this, load or reload:

$ iptrange -N dshield -j LOGnDROP -rt dshield.org.txt
... no waiting for 1000 ranges ...
$ 
$ iptrange -N blacklist -j LOGnDROP -rt blacklist.org.*.txt
... wait 5 minutes for 50000 ranges ...
$

In terms of memory, I definitly agree ipset would be better, at 4 bytes
per ip or 4 bytes per ip+mask it's very good even after the hash table
being only xx% populated. Using lots of iptables rules wastes a large
part of the structure that defines each rule.

But the real plus of iptrange is that it works with any kernel 2.4+ no
patches.

So _I_ still see a place for this little program at least until ipset
gets into the mainstream kernel. I just wish it didn't take O(n^2)
time to load the rules.

-- 
Rob.                          (Robert de Bath <robert$ @ debath.co.uk>)
                                        <http://www.cix.co.uk/~mayday>

Re: Iptables 1.3.1 still not very fast.

[Henrik Nordstrom]

On Sat, 2 Apr 2005, Robert de Bath wrote:

> So you actually need two hashtables for the example 'blacklist' one in
> each mode.  For an IP packet a single lookup is needed on the ip-address
> hash but upto 30 lookups would be needed on the net-address hash.

For networks/ranges hash tables is the wrong kind of data structure. Trees 
are much more appropriate for this form of data.

Regards
Henrik

Re: Iptables 1.3.1 still not very fast.

[Henrik Nordstrom]

On Fri, 1 Apr 2005, Robert de Bath wrote:

> My problem is that I think that libiptc looks evil and I really don't
> want to dive into messing with that code. So how can I help to make
> libiptc run as fast as I'd like it to?

First step is to get a profile on where the time is spent...

   gperf/OProfile/FunctionCheck

Regards
Henrik

Re: Iptables 1.3.1 still not very fast.

[Robert de Bath]

On Sat, 2 Apr 2005, Henrik Nordstrom wrote:

> On Fri, 1 Apr 2005, Robert de Bath wrote:
>
>> My problem is that I think that libiptc looks evil and I really don't
>> want to dive into messing with that code. So how can I help to make
>> libiptc run as fast as I'd like it to?
>
> First step is to get a profile on where the time is spent...
>
>  gperf/OProfile/FunctionCheck

No problem, top of the file is ...

Each sample counts as 0.01 seconds.
   %   cumulative   self              self     total
  time   seconds   seconds    calls   s/call   s/call  name
  67.82    345.66   345.66   217459     0.00     0.00  iptcc_find_label
  27.98    488.30   142.64    20516     0.01     0.01  iptcc_find_chain_by_offset
   3.70    507.18    18.87    20520     0.00     0.00  iptc_insert_chain
   0.15    507.94     0.76        1     0.76   216.53  display_tree
   0.05    508.21     0.27    73850     0.00     0.00  iptc_append_entry
   0.04    508.41     0.20   114889     0.00     0.00  cache_add_entry
   0.04    508.60     0.19    50715     0.00     0.00  netmask4
   0.04    508.79     0.19        1     0.19     0.19  compact_tree
   0.02    508.91     0.12    73851     0.00     0.00  iptcc_compile_rule
   0.02    509.03     0.12        1     0.12   161.89  parse_table
   0.02    509.12     0.09    20520     0.00     0.00  iptcc_compile_chain_offsets
...
   0.00    509.78     0.02        1     0.02   130.59  delete_all_chains
...
   0.00    509.82     0.00        1     0.00   161.89  iptc_init


I think that's a pretty pointy finger there :-)

Do you want any more of the file ?

How about:
granularity: each sample hit covers 2 byte(s) for 0.00% of 509.82 seconds

index % time    self  children    called     name
-----------------------------------------------
                32.61    0.00   20515/217459      iptcc_map_target [12]
                32.61    0.00   20515/217459      iptc_get_references
[17]
                32.61    0.00   20515/217459      iptc_delete_chain [11]
                32.61    0.00   20517/217459      iptc_flush_entries [16]
                32.61    0.00   20517/217459      iptc_create_chain [15]
                65.22    0.00   41030/217459      iptc_builtin [13]
               117.39    0.00   73850/217459      iptc_append_entry [5]
[2]     67.8  345.66    0.00  217459         iptcc_find_label [2]
-----------------------------------------------
                 0.12  161.77       1/1           iptc_init [7]
[6]     31.8    0.12  161.77       1         parse_table [6]
               142.64    0.00   20516/20516       iptcc_find_chain_by_offset [9]
                 0.20   18.93  114889/114889      cache_add_entry [18]
-----------------------------------------------

Note:
This run was a replacement of an existing set of chains by an updated set.

-- 
Rob.                          (Robert de Bath <robert$ @ debath.co.uk>)
                                        <http://www.cix.co.uk/~mayday>

Re: Iptables 1.3.1 still not very fast.

[Harald Welte]

[-- Attachment #1: Type: text/plain, Size: 1432 bytes --]

On Fri, Apr 01, 2005 at 10:52:25PM +0100, Robert de Bath wrote:
> An example:
> I have a program (I've called iptrange) that will take a file full of ip 
> address ranges (192.168.42.10 192.168.42.25) and converts them into a set
> of iptables chains that invokes another chain if the source (or dest) matches 
> ie:
> 
> iptables -N CHECK
> iptables -A CHECK -s 192.168.42.10/31 -j FOUND
> iptables -A CHECK -s 192.168.42.12/30 -j FOUND
> iptables -A CHECK -s 192.168.42.16/29 -j FOUND
> iptables -A CHECK -s 192.168.42.24/31 -j FOUND
> 
> The good bit is that it will create a tree of subchains so that the
> matching is efficient for large numbers of ip addresses.

so why aren't you producing a 'iptables-save' style file that can be
loaded by 'iptables-restore'?  This way you should speed up the process
significantly, not requiring thousands of
fork/exec/getsockopt/parse/modify/generate/setsockopt cycles.

> BTW: iptables-restore is slower than my iptrange!

so you're creating your rules directly by linking against libiptc?

-- 
- Harald Welte <laforge@netfilter.org>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]