mark_source_chains (was Re: sending this off-list)

[Robert Olsson]

Dear Harald et al.
I've just returned from hibernation, and here it is, the new patch. 
I've run some tests on it and it seems to accelerate iptables-insertion
100, 1000 times or more if you have made spaghettirules like myself,
while still correctly detecting loops and other mistakes, and marking correctly.

Best Regards
Robban

--- oldlinux/net/ipv4/netfilter/ip_tables.c     Wed Mar  6 12:26:47 2002
+++ linux/net/ipv4/netfilter/ip_tables.c        Wed Mar  6 12:55:24 2002
@@ -7,6 +7,10 @@
  * 19 Jan 2002 Harald Welte <laforge@gnumonks.org>
  *     - increase module usage count as soon as we have rules inside
  *       a table
+ *
+ * 6 Mar 2002 Robert Olsson <robban@robtex.com>
+ *     - mark_source_chains speedup for complex chains
+ *
  */
 #include <linux/config.h>
 #include <linux/skbuff.h>
@@ -500,7 +504,8 @@
 mark_source_chains(struct ipt_table_info *newinfo, unsigned int valid_hooks)
 {
        unsigned int hook;
-
+       /* keep track of where we have been: */
+       unsigned char *been=vmalloc(newinfo->size);
        /* No recursion; use packet counter to save back ptrs (reset
           to 0 as we leave), and comefrom to save source hook bitmask */
        for (hook = 0; hook < NF_IP_NUMHOOKS; hook++) {
@@ -513,6 +518,7 @@

                /* Set initial back pointer. */
                e->counters.pcnt = pos;
+               memset(been,0,newinfo->size);

                for (;;) {
                        struct ipt_standard_target *t
@@ -521,6 +527,7 @@
                        if (e->comefrom & (1 << NF_IP_NUMHOOKS)) {
                                printk("iptables: loop hook %u pos %u %08X.\n",
                                       hook, pos, e->comefrom);
+                               vfree(been);
                                return 0;
                        }
                        e->comefrom
@@ -567,11 +574,12 @@
                                pos += size;
                        } else {
                                int newpos = t->verdict;
-
-                               if (strcmp(t->target.u.user.name,
+                               if (((0<pos&&pos<newinfo->size)?(been[pos]<1):1)
+                                       &&strcmp(t->target.u.user.name,
                                           IPT_STANDARD_TARGET) == 0
                                    && newpos >= 0) {
                                        /* This a jump; chase it. */
+                                       if (0<pos&&newpos<newinfo->size) been[pos]++;
                                        duprintf("Jump rule %u -> %u\n",
                                                 pos, newpos);
                                } else {
@@ -587,6 +595,7 @@
                next:
                duprintf("Finished chain %u\n", hook);
        }
+       vfree(been);
        return 1;
 }




At 19:14 2001-11-26 +0100, Harald Welte wrote:
>On Mon, Nov 12, 2001 at 09:38:36PM +0100, Robert Olsson wrote:
>> It seems like mark_source_chains goes thru all possible flows.
>> consider something like this scenario:
>> 
>[...]
>
>> The kernel seem to investigate the "-A post" 4*3*2 times. add more machines
>> and rules, and it easily expands to thousands upon thousands, taking up hours
>> or weeks of kernel-time when you have a complex set of rules.
>> My new patch still detects loops, but it minimizes the number of loops.
>> Maybe not the ultimate patch, but I don't want to rewrite it totally.
>> Thanks for your great job, whatever you decide to do about this.
>
>First of all: You are right. The Problem is that we have _lots_ of 
>traversal at the time you have complex rulesets with lots of chains.
>
>I have discussed this with Rusty, and we cannot accept your patch straight
>ahead.  You are optimizing too much:
>
>We can have targets which are only allowed to be called from particular
>hooks (like SNAT only in postrouting).  And one of the jobs of mark_source_
>chains is to make sure that we don't have a target in a user defined chain
>called from a hook where the target is not allowed.
>
>So If I read your code correctly, you would have to re-set the 'beenthere'
>to zero at least one time at every hook (inside the respective loop).
>
>This still is an optimization, could you please try to test it and report
>to the mailinglist?
>
>thanks.
>
>> Regards
>> Robban
>
>-- 
>Live long and prosper
>- Harald Welte / laforge@gnumonks.org               http://www.gnumonks.org/
>============================================================================
>GCS/E/IT d- s-: a-- C+++ UL++++$ P+++ L++++$ E--- W- N++ o? K- w--- O- M- 
>V-- PS+ PE-- Y+ PGP++ t++ 5-- !X !R tv-- b+++ DI? !D G+ e* h+ r% y+(*)