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.

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

userspace should just ignore unknown flags.

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

net/ipv4/netfilter/ip_tables.c +0 -1

 	/* Look for ifname matches; this should unroll nicely. */
-	for (i = 0, ret = 0; i < IFNAMSIZ/sizeof(unsigned long); 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.

Quoted 3 lines · Yasuyuki KOZAKAI

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.

Quoted 2 lines · Patrick McHardy

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.

Quoted 1 line

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.

Quoted 3 lines · Yasuyuki KOZAKAI

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.

If we can never add new flags, then that would be a reason for me to not bother with clearing the internal bits before sending to userspace.

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 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 \0 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..

lör 2007-05-26 klockan 11:20 +0200 skrev Patrick McHardy:

Quoted 3 lines

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 \0 in the interface name on exact matches.

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.

tis 2007-05-29 klockan 10:24 +1000 skrev Philip Craig:

Quoted 3 lines

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..

Quoted 7 lines · Henrik Nordstrom

tis 2007-05-29 klockan 10:24 +1000 skrev Philip Craig:

Quoted 3 lines

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)

You're right, I should check things before making statements.

Quoted 7 lines

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..

For my ARM platform, changing the for loop is a win for no interface matches, or short interface names (I didn't test longer interface names).

But looking at the generated assembly for x86_64, this results in more instructions and branches, and I can't see this being a win. (I'm not set up to profile this.)

Also, the two optimisations are not mutually exclusive: one is to skip the whole comparison completely (including inversion), and one is to terminate the for loop early. So we can use your loop termination condition to skip the whole comparison too.

The attached patch is logically equivalent to my first (assuming a contiguous and zero padded mask), but it avoids messing with flags. In practice, my profiling says it is slightly slower than the first patch for 0 interface matches, but slightly faster for 1 or 2.

Note: this patch (and the original patch) change the behaviour when inverting a zero length mask. That is for either of:
iptables -A INPUT ! -i +
iptables -A INPUT ! -i ""
Not sure if this matters.

I also tried testing just the first byte, instead of a long, but that was slower.