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 <[EMAIL PROTECTED]>
* - increase module usage count as soon as we have rules inside
* a table
+ *
+ * 6 Mar 2002 Robert Olsson <[EMAIL PROTECTED]>
+ * - 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 / [EMAIL PROTECTED] 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+(*)
