Rule matching question [iptables code structure]

Rule matching question [iptables code structure]

[hewa0000]

[Please mail us personally (oan@itm.mh.se) as well
as mailing the list since we are not members of this
mail-list]

We have a quite difficult question for all you elite
people.... =)
 
When we add a rule to iptables that filter on
MAC-address (or IP address and port for that
matter). Does iptables ONLY check for the
MAC-address option (alas in that case we filter on
MAC-address)?.

Based on a the report "Performance analysis of the
Linux firewall on a host" by James Harris and
Americo J. Melara. It is stated that for each check
if the MAC-address in the rule match the given
MAC-address, the Iptables-algorithm ALWAYS checks
all possibilities (MAC-address, IP, Port, Protocol,
Interface..). 
Does anyone know this to be the truth?

We are currently working on a big project where we
use big lists of rules that are based on MAC and
IP-addresses. And we are trying to understand why
these lists of rules crave so much computation power
to execute.

If Iptables always run a check for every possible
way to match our packet with a single rule
(ip,mac,protocol,interface...) it consumes alot more
(actually we belive it to be around 6 times as much
according to the nature of the algorithm) as necessary. 

Optimally the algorithm would ONLY check for a
MAC-Address match if that is what we are filtering
on. We truly hope this also is the case. But please,
someone who knows this :-) :
Answer us!

Sincerly,
Open Access Networks Project MidSweden University.
oan@itm.mh.se

Re: Rule matching question [iptables code structure]

[Patrick Schaaf]

Hello Open Access Networks Project MidSweden University,

for each and every rule executed, iptables checks

	- source IP
	- destination IP
	- source interface
	- destination interface

These four checks are all of the comparator/mask kind, and when a rule
does not specify one of them, then a mask is selected that makes the
check always match. The checks are still made. The two IP matches
need eight byte in the rule (IP/mask), the two interface matches
each need a 32-byte interface/mask storage, a whopping two cachelines
that need to be read for each rule. This is most likely where you will
see the real overhead in accurate timings, once your rules stop to
fit the L1 cache of synthetic microtests.

Apart from those four matchings, checking for IP protocol, and checking
for IP fragmentation bits, is also always executed for each rule. But
that's small stuff. Finally, there is a list of additional match
criteria, which is only filled when there ARE additional criteria.
All matches except the above four, are of this selective type,
inclusing MAC address matches.

In the source, net/ipv4/netfilter/ip_tables.c, you can find the six
fixed checks in the function ip_packet_match(), called by the core
rule/list walking done in ipt_do_table().

best regards
  Patrick

Re: Rule matching question [iptables code structure]

[Harald Welte]

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

On Tue, May 06, 2003 at 02:56:45PM +0200, hewa0000@student.mh.se wrote:
>  
> When we add a rule to iptables that filter on
> MAC-address (or IP address and port for that
> matter). Does iptables ONLY check for the
> MAC-address option (alas in that case we filter on
> MAC-address)?.

> Based on a the report "Performance analysis of the
> Linux firewall on a host" by James Harris and
> Americo J. Melara. It is stated that for each check
> if the MAC-address in the rule match the given
> MAC-address, the Iptables-algorithm ALWAYS checks
> all possibilities (MAC-address, IP, Port, Protocol,
> Interface..). 
> Does anyone know this to be the truth?

It doesn't check all possibilities.  However, there is the ip_tables
core that matches ip src/dest, incoming/outgoing interface, l4protocol.
Please see linux/net/ipv4/netfilter/ip_tables.c:ip_packet_match() for
more information.

After this ip_tables core check was made, any extensions are checked,
and ipt_mac.c is one such extension.

> We are currently working on a big project where we
> use big lists of rules that are based on MAC and
> IP-addresses. And we are trying to understand why
> these lists of rules crave so much computation power
> to execute.

You are linearly iterating over long lists.  This raises computational
complexity.  Try building a tree-like structure made of lots of chains
with little number of rules in every chain.  This reduces the average
number of rules to be iterated per packet.  

That is a general rule of thumb when designing any iptables ruleset.

> If Iptables always run a check for every possible
> way to match our packet with a single rule
> (ip,mac,protocol,interface...) it consumes alot more
> (actually we belive it to be around 6 times as much
> according to the nature of the algorithm) as necessary. 
> 
> Optimally the algorithm would ONLY check for a
> MAC-Address match if that is what we are filtering
> on. We truly hope this also is the case. But please,
> someone who knows this :-) :

there is not much of an 'algorithm' involved.

> Sincerly,
> Open Access Networks Project MidSweden University.
> oan@itm.mh.se

-- 
- Harald Welte <laforge@netfilter.org>             http://www.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 --]