first version of optimized mark_source_chains()
Subsystems (2)
PATCH 1/1 first version of optimized mark_source_chains()
Hi!
Since I'm going to be on short vacation till Tuesday, I wanted to post the current version of the optimized loop detection / mark_source_chains() implementation.
It spits out lots of debugging info, and is still a recursive implementation - thus you might be able to overflow your kernel stack with a very depth ruleset. Also, it needs some cleanup.
I thought of the recursive version as a proof-of-concept, and later implement a iterative version (patches are welcome *g*).
Anyway, you might give it a try. Any improvements are welcome, but be aware that I'm not going to reply within the next 5 days.
Thanks again to Andre Uratsuka Manoel for his suggested algorithm.
Signature · 5 lines
- Harald Welte <[email protected]> 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
net/ipv4/netfilter/ip_tables.c +219 -78
@@ -7,6 +7,10 @@* 19 Jan 2002 Harald Welte <[email protected]> * - increase module usage count as soon as we have rules inside * a table +* 28 May 2003 Harald Welte <[email protected]> +* - implement more efficient loop detection / mark_source_chains +* (Idea by Andre Uratsuka Manoel <[email protected]>, implementation +* funded by Astaro AG, http://www.astaro.com/) */ #include <linux/config.h> #include <linux/cache.h>
@@ -25,7 +29,7 @@#include <linux/netfilter_ipv4/ip_tables.h> -/*#define DEBUG_IP_FIREWALL*/ +#define DEBUG_IP_FIREWALL /*#define DEBUG_ALLOW_ALL*/ /* Useful for remote debugging */ /*#define DEBUG_IP_FIREWALL_USER*/
@@ -41,6 +45,8 @@ #define duprintf(format, args...)#endif +#define DEBUGP(format, args...) printk(__FUNCTION__ ":" format, ## args) +#ifdef CONFIG_NETFILTER_DEBUG #define IP_NF_ASSERT (x) \ do { \
@@ -68,12 +74,13 @@#define inline#endif -/* +/* Locking is simple: we assume at worst case there will be one packet +in user context and one from bottom halves (or soft irq if Alexey's +softnet patch was applied). +We keep a set of rules for each CPU, so we can avoid write-locking -them in the softirq when updating the counters and therefore -only need to read-lock in the softirq; doing a write_lock_bh() in user -context stops packets coming through and allows user context to read -the counters or update the rules. +them; doing a readlock_bh() stops packets coming through if we're +in user context. To be cache friendly on SMP, we arrange them like so: [ n-entries ]
@@ -494,99 +501,232 @@return 1 ; } -/* Figures out from what hook each rule can be called: returns 0 if -there are loops. Puts hook bitmask in comefrom. */ -static int +/******************/ + +#if 0 +enum { +IPT_COLOR_WHITE =1 , +IPT_COLOR_GREY , +IPT_COLOR_BLACK +} iptables_color; +#endif + +#define IPT_COLOR_WHITE 1 +#define IPT_COLOR_GREY 2 +#define IPT_COLOR_BLACK 3 + +struct chain_stack_element { +struct chain_stack_element *next;/* next in stack */ +struct ipt_entry *e;/* pointer to chain */ +}; + +static struct chain_stack_element *chain_stack =NULL ; + +static inline struct ipt_entry * +chain_stack_pop (void ) +{ +struct chain_stack_element *se; +struct ipt_entry *e; + +if (!chain_stack) +return NULL ; + + se = chain_stack; + chain_stack = se->next; + e = se->e; +kfree (se); + +return e; +} + +static inline int +chain_stack_push (struct ipt_entry *e) +{ +struct chain_stack_element *se; + + se =kmalloc (GFP_ATOMIC ,sizeof (struct chain_stack_element )); +if (!se) +return -1 ; + + se->next = chain_stack; + se->e = e; + chain_stack = se; + +return 0 ; +} + +static inline int +initialize_white (struct ipt_entry *e,struct ipt_table_info *tinfo, +unsigned char *base,unsigned char *limit) +{ +int h; +struct ipt_entry_target *t =ipt_get_target (e); + +for (h =0 ; h <NF_IP_NUMHOOKS ; h++) { +if ((unsigned char *)e - base == tinfo->hook_entry[h]) { +/* start of builtin chain */ +DEBUGP ("entry=%p: builtin chain, painting white\n" , e); + e->counters.bcnt =IPT_COLOR_WHITE ; + e->comefrom =0 ; +return 0 ; + } + } + +if (!strcmp (t->u.user.name,IPT_ERROR_TARGET )) { +/* start of userdefined chain */ +DEBUGP ("entry=%p: user chain %s, painting white\n" , e, t->data); + e->counters.bcnt =IPT_COLOR_WHITE ; + e->comefrom =0 ; + } + +return 0 ; +} + +/* dfs - depth first search +* returns 1 if loop found, 0 otherwise */ +int dfs (struct ipt_entry *ie,const char *base,int base_offset,char *end) +{ +struct ipt_entry *e; +int pos; + +DEBUGP ("entry=%p: dfs entered: base=%p, base_offset=0x%x, end=%p\n" , + ie, base, base_offset, end); + +if (ie->counters.bcnt ==IPT_COLOR_GREY ) { +DEBUGP ("entry=%p: already color grey, loop found\n" , ie); +return 1 ; + } +if (ie->counters.bcnt ==IPT_COLOR_BLACK ) { +DEBUGP ("entry=%p: already color black, no loop below here\n" , ie); +return 0 ; + } + +if (ie->counters.bcnt !=IPT_COLOR_WHITE ) { +printk (KERN_ERR "entry=%p: color not white (%d!=%d)\n" , + ie, ie->counters.bcnt,IPT_COLOR_WHITE ); +return 1 ; + } + +DEBUGP ("entry=%p: painting grey\n" , ie); + ie->counters.bcnt =IPT_COLOR_GREY ; + +for (pos = base_offset, e = (struct ipt_entry *)((char *)base+base_offset); + base+base_offset <= end; + pos += e->next_offset, e = (struct ipt_entry *)((char *)base+pos)) { +struct ipt_standard_target *t = + (struct ipt_standard_target *)ipt_get_target (e); + +DEBUGP ("iterating over e=%p\n" , e); +/* Unconditional return/END. */ +if (e->target_offset ==sizeof (struct ipt_entry ) + && (strcmp (t->target.u.user.name,IPT_STANDARD_TARGET ) ==0 ) + && t->verdict <0 &&unconditional (&e->ip)) { +/* unconditional return/end */ +DEBUGP ("chain=%p entry=%p: unconditional return, painting black\n" , ie, e); + ie->counters.bcnt =IPT_COLOR_BLACK ; +chain_stack_push (ie); +return 0 ; + }else { +if (!strcmp (t->target.u.user.name,IPT_STANDARD_TARGET ) + && t->verdict >=0 ) { +/* another jump */ +struct ipt_entry *ejt = + (struct ipt_entry *) ((char *)base + t->verdict); +/* subtract size of chain head */ + ejt = (char *)ejt -IPT_ALIGN (sizeof (struct ipt_entry )+sizeof (struct ipt_entry_target )+IPT_TABLE_MAXNAMELEN ); +DEBUGP ("entry=%p: jump. recursing to %p\n" , e, ejt); +if (dfs (ejt, base, t->verdict, end) ==1 ) +return 1 ; + }else { +DEBUGP ("entry=%p: normal rule, skipping\n" , e); +/* a normal rule */ + } +continue ; + } +/* not reached */ +DEBUGP ("entry=%p: not reached!!!!!!!!\n" , e); + } +/* not reached */ +DEBUGP ("recursed over end of table ?!?\n" ); +return -1 ; +} + +/* returns 1 if no loops found */ +static int mark_source_chains (struct ipt_table_info *newinfo,unsigned int valid_hooks) {unsigned int hook; +struct ipt_entry *ie; + +DEBUGP ("entered\n" ); + +/* paint all chains white, initialize comefrom */ +IPT_ENTRY_ITERATE (newinfo->entries, newinfo->size, + initialize_white, newinfo, newinfo->entries, + newinfo->entries + 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++) {unsigned int pos = newinfo->hook_entry[hook]; -struct ipt_entry *e +struct ipt_entry *e = (struct ipt_entry *)(newinfo->entries + pos);if (!(valid_hooks & (1 << hook)))continue ; -/* Set initial back pointer. */ - e->counters.pcnt = pos; +if (dfs (e, newinfo->entries, pos, + newinfo->entries + newinfo->size) ==1 ) { +/* loop detected, returning */ +return 0 ; + } + } -for (;;) { -struct ipt_standard_target *t - = (void *)ipt_get_target (e); +/* now we can be sure that there are no loops */ -if (e->comefrom & (1 <<NF_IP_NUMHOOKS )) { -printk ("iptables: loop hook %u pos %u %08X.\n" , - hook, pos, e->comefrom); -return 0 ; - } - e->comefrom - |= ((1 << hook) | (1 <<NF_IP_NUMHOOKS )); +/* initialize comefrom of builtin hooks / entry points */ +for (hook =0 ; hook <NF_IP_NUMHOOKS ; hook++) { +unsigned int pos = newinfo->hook_entry[hook]; +struct ipt_entry *e + = (struct ipt_entry *)(newinfo->entries + pos); -/* Unconditional return/END. */ +/* initialize comefrom of builtin chains */ + e->comefrom = (1 << hook); + } + +/* FIXME: while no chains on stack, pop and set comefrom */ +while (ie =chain_stack_pop ()) { +struct ipt_entry *e = ie; +DEBUGP ("popping chain %p from stack\n" , ie); +for (;;) { +struct ipt_standard_target *t = (struct ipt_standard_target *)ipt_get_target (e); +DEBUGP ("iterating over entry %p\n" , e);if (e->target_offset ==sizeof (struct ipt_entry ) - && (strcmp (t->target.u.user.name, -IPT_STANDARD_TARGET ) ==0 ) - && t->verdict <0 - &&unconditional (&e->ip)) { -unsigned int oldpos, size; - -/* Return: backtrack through the last -big jump. */ -do { - e->comefrom ^= (1 <<NF_IP_NUMHOOKS ); -#ifdef DEBUG_IP_FIREWALL_USER -if (e->comefrom - & (1 <<NF_IP_NUMHOOKS )) { -duprintf ("Back unset " -"on hook %u " -"rule %u\n" , - hook, pos); - } -#endif - oldpos = pos; - pos = e->counters.pcnt; - e->counters.pcnt =0 ; - -/* We're at the start. */ -if (pos == oldpos) - goto next; - - e = (struct ipt_entry *) - (newinfo->entries + pos); - }while (oldpos == pos + e->next_offset); - -/* Move along one */ - size = e->next_offset; - e = (struct ipt_entry *) - (newinfo->entries + pos + size); - e->counters.pcnt = pos; - pos += size; + && (strcmp (t->target.u.user.name,IPT_STANDARD_TARGET ) ==0 ) + && t->verdict <0 &&unconditional (&e->ip)) { +/* unconditional return */ + goto next_chain; }else { -int newpos = t->verdict; - -if (strcmp (t->target.u.user.name, -IPT_STANDARD_TARGET ) ==0 - && newpos >=0 ) { -/* This a jump; chase it. */ -duprintf ("Jump rule %u -> %u\n" , - pos, newpos); +DEBUGP ("entry=%p, setting comefrom 0x%x->0x%x\n" , e, e->comefrom, e->comefrom|ie->comefrom); + e->comefrom |= ie->comefrom; +if (!strcmp (t->target.u.user.name,IPT_STANDARD_TARGET ) + && t->verdict >=0 ) { +/* a jump */ +struct ipt_entry *ejt = + (struct ipt_entry *) ((char *)newinfo->entries + t->verdict); +/* subtract size of chain head */ + ejt = (char *)ejt -IPT_ALIGN (sizeof (struct ipt_entry )+sizeof (struct ipt_entry_target )+IPT_TABLE_MAXNAMELEN ); +DEBUGP ("entry=%p jump: setting target=%p comefrom 0x%x->0x%x\n" , e, ejt, ejt->comefrom, ejt->comefrom | ie->comefrom); + ejt->comefrom |= ie->comefrom; }else { -/* ... this is a fallthru */ - newpos = pos + e->next_offset; +/* normal rule */ } - e = (struct ipt_entry *) - (newinfo->entries + newpos); - e->counters.pcnt = pos; - pos = newpos; +/* in any case, go on with next rule */ + e = (char *) e + e->next_offset; } +/* FIXME: don't run over end of table */ } - next: -duprintf ("Finished chain %u\n" , hook); +next_chain: } +return 1 ; }
@@ -705,6 +845,7 @@if (t->u.kernel.target == &ipt_standard_target) {if (!standard_check (t, size)) { +duprintf ("check_entry: standard check failed\n" ); ret = -EINVAL ; goto cleanup_matches; }
fuzzy.patch and fuzzy.patch.ipv6 - again.
Hi,
I try to build p-o-m [2003 06 05] on PPC and I take some unresolved symbols. I don't know, that I send patch which resole this problem.
If yes, please appaly this.
If not here is the patch.
patch-o-matic/base/fuzzy.patch +3 -3
@@ -59,7 +59,7 @@ + Expressed in percentage +*/ + -+#define PAR_LOW 0.01 ++#define PAR_LOW 1/100 +#define PAR_HIGH 1 + +static spinlock_t fuzzy_lock = SPIN_LOCK_UNLOCKED ;
@@ -138,7 +138,7 @@ + howlow = mf_low(info->mean_rate,info->minimum_rate,info->maximum_rate); + + info->acceptance_rate = (u_int8_t) \ -+ ( PAR_LOW*howhigh + PAR_HIGH*howlow ) ; ++ ( howhigh*PAR_LOW + PAR_HIGH*howlow ) ; + + /* In fact , the above defuzzification would require a denominator + proportional to (howhigh+howlow) but , in this particular case ,
@@ -158,7 +158,7 @@ + get_random_bytes((void *)(&random_number), 1); + + /* If within the acceptance , it can pass => don't match */ -+ if ( random_number <= 2.55 * info->acceptance_rate ) ++ if ( random_number <= (255 * info->acceptance_rate) / 100 ) + return 0 ; + else + return 1; /* It can't pass ( It matches ) */
patch-o-matic/base/fuzzy6.patch.ipv6 +3 -3
@@ -60,7 +60,7 @@ + Expressed in percentage +*/ + -+#define PAR_LOW 0.01 ++#define PAR_LOW 1/100 +#define PAR_HIGH 1 + +static spinlock_t fuzzy_lock = SPIN_LOCK_UNLOCKED;
@@ -138,7 +138,7 @@ + howlow = mf_low(info->mean_rate,info->minimum_rate,info->maximum_rate); + + info->acceptance_rate = (u_int8_t) \ -+ (PAR_LOW * howhigh + PAR_HIGH * howlow); ++ (howhigh * PAR_LOW + PAR_HIGH * howlow); + + /* In fact, the above defuzzification would require a denominator + * proportional to (howhigh+howlow) but, in this particular case,
@@ -158,7 +158,7 @@ + get_random_bytes((void *)(&random_number), 1); + + /* If within the acceptance , it can pass => don't match */ -+ if (random_number <= 2.55 * info->acceptance_rate) ++ if (random_number <= (255 * info->acceptance_rate) / 100) + return 0; + else + return 1; /* It can't pass (It matches) */
Signature · 2 lines
{Wojciech 'Sas' Cieciwa} {Member of PLD Team }
{e-mail: [email protected], http://www2.zarz.agh.edu.pl/~cieciwa}Martin Josefsson
AppliedRe: fuzzy.patch and fuzzy.patch.ipv6 - again.
Quoted 4 lines · Wojciech "Sas" Cieciwa
Hi,
I try to build p-o-m [2003 06 05] on PPC and I take some unresolved symbols. I don't know, that I send patch which resole this problem.
Thanks, applied
Signature · 1 line
/Martin