optimise iptables interface matching

Optimise iptables for rules that specify 0 or 1 interface
matches,
which is the more common case (at least for my rulesets).

Below are the oprofile cpu cycle percentages from a 30
second
period of an iperf throughput test on a 667MHz IXP465 with
Realtek 8169 network interfaces.

rules	iface	% cpu before	% cpu after	saving (adjusted)
0		 7.7662		 4.9191		 2.8471
10 	0	15.9798		 9.8453		 3.2874
20 	0	23.6914		14.2051		 6.6392
10	1	14.6068		11.7332		 0.0265
20	1	21.1646		17.1905		 1.1270
10	2	14.6497		13.0306		-1.2280
20	2	21.1647		20.3536		-2.0360

- saving with 0 rules is due to policies
- adjusted saving means with the 0 rules saving subtracted
- iface 0 means "iptables -I FORWARD"
- iface 1 means "iptables -I FORWARD -i eth0"
- iface 2 means "iptables -I FORWARD -i eth0 -o
eth1"

If you think this is an acceptable approach then I can
update
the patch for IPv6.  Any suggestions for other parts of
netfilter/iptables to look at optimising are also welcome.

Signed-off-by: Philip Craig <philipcsnapgear.com>

Philip Craig wrote:
> Optimise iptables for rules that specify 0 or 1
interface matches,
> which is the more common case (at least for my
rulesets).
> 
> Below are the oprofile cpu cycle percentages from a 30
second
> period of an iperf throughput test on a 667MHz IXP465
with
> Realtek 8169 network interfaces.
> 
> rules	iface	% cpu before	% cpu after	saving (adjusted)
> 0		 7.7662		 4.9191		 2.8471
> 10 	0	15.9798		 9.8453		 3.2874
> 20 	0	23.6914		14.2051		 6.6392
> 10	1	14.6068		11.7332		 0.0265
> 20	1	21.1646		17.1905		 1.1270
> 10	2	14.6497		13.0306		-1.2280
> 20	2	21.1647		20.3536		-2.0360
> 
> - saving with 0 rules is due to policies
> - adjusted saving means with the 0 rules saving
subtracted
> - iface 0 means "iptables -I FORWARD"
> - iface 1 means "iptables -I FORWARD -i
eth0"
> - iface 2 means "iptables -I FORWARD -i eth0 -o
eth1"
> 
> If you think this is an acceptable approach then I can
update
> the patch for IPv6.  Any suggestions for other parts
of
> netfilter/iptables to look at optimising are also
welcome.


I don't like the kernel-internal fiddling with the flags
too
much, but I don't see a way around it. But even if there is
no other way,

>  -884,6 +897,15  copy_entries_to_user(unsigned int total_
>  			goto free_counters;
>  		}
>  
> +		flags = e->ip.flags & IPT_F_MASK;
> +		if (copy_to_user(userptr + off
> +				 + offsetof(struct ipt_entry, ip.flags),
> +				 &flags,
> +				 sizeof(flags)) != 0) {
> +			ret = -EFAULT;
> +			goto free_counters;
> +		}
> +


userspace should just ignore unknown flags.

Patrick McHardy wrote:
> I don't like the kernel-internal fiddling with the
flags too
> much, but I don't see a way around it.

The other idea I had was moving the interface matching into
an internal match that would be checked by
IPT_MATCH_ITERATE().
Not sure if this is feasible yet.

> userspace should just ignore unknown flags.

I was trying to completely hide them from userspace so that
we
still have the option to use them for something else later
on.
If we ever send them to userspace, then they are taken
forever,
otherwise a newer iptables userspace may not work with an
older
kernel.

Hi, Philip,

From: Philip Craig <philipcsnapgear.com>
Date: Thu, 24 May 2007 15:55:23 +1000

> Optimise iptables for rules that specify 0 or 1
interface matches,
> which is the more common case (at least for my
rulesets).


>  	/* Look for ifname matches; this should unroll
nicely. */
> -	for (i = 0, ret = 0; i < IFNAMSIZ/sizeof(unsigned
long); i++) {
> -		ret |= (((const unsigned long *)indev)[i]
> -			^ ((const unsigned long *)ipinfo->iniface)[i])
> -			& ((const unsigned long
*)ipinfo->iniface_mask)[i];
> -	}
> +	if (ipinfo->flags & IPT_F_VIA_IN) {
> +		for (i = 0, ret = 0; i < IFNAMSIZ/sizeof(unsigned
long); i++) {
> +			ret |= (((const unsigned long *)indev)[i]
> +				^ ((const unsigned long *)ipinfo->iniface)[i])
> +				& ((const unsigned long
*)ipinfo->iniface_mask)[i];
> +		}

This breaks binary compatibility. The current userspace
programs do not set
this bit. And ip_checkentry() in all kernel before you
change will reject
unknown flags from new userspace programs.

Actually, we cannot add a new flag to 'struct ipt_ip'. It
does not have
revision field. Unfortunately it has no field such as name[]
in
'struct xt_entry_match' to steal one octet for revision.

I expect that this optimization will be done when we
introduce netlink
interface.

-- Yasuyuki Kozakai

From: Philip Craig <philipcsnapgear.com>
Date: Fri, 25 May 2007 10:56:10 +1000

> Yasuyuki KOZAKAI wrote:
> > This breaks binary compatibility. The current
userspace programs do not set
> > this bit. And ip_checkentry() in all kernel before
you change will reject
> > unknown flags from new userspace programs.
> 
> Userspace doesn't need to set it because the kernel can
derive it
> automatically (which I've done in ip_checkentry).
> Basically I just needed two bits of internal state, and
the flags
> field looked like a convenient place for this. 
Userspace should
> be completely ignorant of these bits.

Ah, indeed, thanks for explanation.

-- Yasuyuki Kozakai

Philip Craig wrote:
> Patrick McHardy wrote:
> 
>>I don't like the kernel-internal fiddling with the
flags too
>>much, but I don't see a way around it.
> 
> 
> The other idea I had was moving the interface matching
into
> an internal match that would be checked by
IPT_MATCH_ITERATE().
> Not sure if this is feasible yet.

Mhh .. probably not since you would have to put it
somewhere
in the blob.

>>userspace should just ignore unknown flags.
> 
> 
> I was trying to completely hide them from userspace so
that we
> still have the option to use them for something else
later on.
> If we ever send them to userspace, then they are taken
forever,
> otherwise a newer iptables userspace may not work with
an older
> kernel.


We could do that, but we would need some other place to
store them
since once we want to use them for something new we can't
put them
in ->flags anymore.

LöR 2007-05-26 KLOCKAN 11:20 +0200 SKREV PATRICK MCHARDY:

> WE CAN ADD FLAGS FOR NEW FEATURES, BUT NOT FLAGS THAT
ARE REQUIRED TO
> BE SET TO BEHAVE COMPATIBLE SINCE THAT WOULD BREAK
IPTABLES USERSPACE
> FOR OLD KERNELS.

BUT THE PROPOSED CHANGE IS COMPLETELY TRANSPARENT TO
USERSPACE... THE
USE OF THE NEW FLAGS IS PURELY KERNEL-ONLY AND NOT VISIBLE
TO
USERSPACE..

THE DRAWBACK IS THAT IT REDUCES THE POSSIBLE NEW FLAGS WHICH
MIGHT BE
ADDED BY TWO BITS, OR IF PUT ANOTHER WAY REDUCES THE FLAGS
FIELD FROM 8
TO 6 BITS, LEAVING ONLY 3 UNUSED FLAG BITS FOR FUTURE FLAG
TYPE
EXPANSIONS.

BUT I AM A LITTLE CURIOUS.. HOW MUCH DIFFERENCE WOULD IT
YIELD IF SIMPLY
THE LOOP WAS INSTEAD CHANGED TO TERMINATE ON STRING END
INSTEAD OF
ALWAYS ITERATING OVER THE MAX INTERFACE NAME LENGTH..

        FOR (I = 0, RET = 0; ((CONST UNSIGNED LONG
*)IPINFO->OUTIFACE_MASK)[I] && I <
IFNAMSIZ/SIZEOF(UNSIGNED LONG); I++) {
		...
        }

INSTEAD OF

        FOR (I = 0, RET = 0; I < IFNAMSIZ/SIZEOF(UNSIGNED
LONG); I++) {
		...
	}

PLUS A SMALL CHANGE TO THE USERSPACE TO ZERO THE MASK AFTER
THE FIRST 
IN THE INTERFACE NAME ON EXACT MATCHES.

THE USERSPACE ONLY ALLOW EXACT OR PREFIX MATCHING, SO IT
SHOULD BE OK TO
RESTRICT THE COMPARE FUNCTION TO THIS I THINK..

REGARDS
HENRIK

Henrik Nordstrom wrote:
> lör 2007-05-26 klockan 11:20 +0200 skrev Patrick
McHardy:
> 
> 
>>We can add flags for new features, but not flags
that are required to
>>be set to behave compatible since that would break
iptables userspace
>>for old kernels.
> 
> 
> But the proposed change is completely transparent to
userspace... the
> use of the new flags is purely kernel-only and not
visible to
> userspace..


Yes, certainly, that statement was not specific to this
patch.

> The drawback is that it reduces the possible new flags
which might be
> added by two bits, or if put another way reduces the
flags field from 8
> to 6 bits, leaving only 3 unused flag bits for future
flag type
> expansions.
>
> 
> But I am a little curious.. how much difference would
it yield if simply
> the loop was instead changed to terminate on string end
instead of
> always iterating over the max interface name length..
> 
>         for (i = 0, ret = 0; ((const unsigned long
*)ipinfo->outiface_mask)[i] && i <
IFNAMSIZ/sizeof(unsigned long); i++) {
> 		...
>         }
> 
> instead of
> 
>         for (i = 0, ret = 0; i <
IFNAMSIZ/sizeof(unsigned long); i++) {
> 		...
> 	}
> 
> plus a small change to the userspace to zero the mask
after the first 
> in the interface name on exact matches.


It already does that I think. This sounds like a good
alternative,
I'd be interested to see how much improvement it yields.

tis 2007-05-29 klockan 10:24 +1000 skrev Philip Craig:
> 
> I'll try that, but that will also prevent loop
unrolling if you're
> using -funroll-loops.  Not sure if any builds use this,
but the
> comment in the code implies some do.

My GCC unrolls that loop just fine...

x86_64 gcc (GCC) 4.1.1 20070105 (Red Hat 4.1.1-51)

Here is a corrected version of the for loop:

for (i = 0, ret = 0;  i < IFNAMSIZ/sizeof(unsigned long)
&& ((const unsigned long
*)ipinfo->outiface_mask)[i]; i++) {


but for modern 64-bit CPUs I suspect the original is
actually fastest as
IFNAMSIZ is only 16 bytes and fits in two parallel 64-bit
operations..

Regards
Henrik