All of lore.kernel.org
 help / color / mirror / Atom feed
* Re: fuzzy.patch and fuzzy.patch.ipv6 - again.
@ 2003-06-06 17:54 Hime Junior
  2003-06-06 19:04 ` Maciej Soltysiak
  0 siblings, 1 reply; 4+ messages in thread
From: Hime Junior @ 2003-06-06 17:54 UTC (permalink / raw)
  To:  Cieciwa, laforge; +Cc: netfilter-devel


 Hi Harald !

 Have you applied that patch ?

 As I said before , the new behavior is , in practice , equivalent to the old one.

 Regards.

----- Original Message -----
From: "Wojciech \"Sas\" Cieciwa" <cieciwa@alpha.zarz.agh.edu.pl>
Date: Fri, 6 Jun 2003 15:31:42 +0200 (CEST) 
To: Harald Welte <laforge@netfilter.org>
Subject: 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.
> 
> diff -Nur netfilter.org/patch-o-matic/base/fuzzy.patch netfilter/patch-o-matic/base/fuzzy.patch
> --- netfilter.org/patch-o-matic/base/fuzzy.patch	Wed Sep  4 16:11:30 2002
> +++ netfilter/patch-o-matic/base/fuzzy.patch	Fri Jun  6 15:19:57 2003
> @@ -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 ) */
> diff -Nur netfilter.org/patch-o-matic/base/fuzzy6.patch.ipv6 netfilter/patch-o-matic/base/fuzzy6.patch.ipv6
> --- netfilter.org/patch-o-matic/base/fuzzy6.patch.ipv6	Fri Apr 11 12:27:54 2003
> +++ netfilter/patch-o-matic/base/fuzzy6.patch.ipv6	Fri Jun  6 15:20:49 2003
> @@ -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) */
> 
> -- 
> {Wojciech 'Sas' Cieciwa}  {Member of PLD Team                               }
> {e-mail: cieciwa@alpha.zarz.agh.edu.pl, http://www2.zarz.agh.edu.pl/~cieciwa}
> 
> 




                    Hime Junior
            ___________________________
  
          Electronic and Control Engineer


-- 
__________________________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com
http://www.mail.com/?sr=signup

^ permalink raw reply	[flat|nested] 4+ messages in thread
* [PATCH] first version of optimized mark_source_chains()
@ 2003-06-05 10:34 Harald Welte
  2003-06-06 13:31 ` fuzzy.patch and fuzzy.patch.ipv6 - again Wojciech "Sas" Cieciwa
  0 siblings, 1 reply; 4+ messages in thread
From: Harald Welte @ 2003-06-05 10:34 UTC (permalink / raw)
  To: Netfilter Development Mailinglist


[-- Attachment #1.1: Type: text/plain, Size: 1071 bytes --]

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.

-- 
- Harald Welte <laforge@netfilter.org>             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

[-- Attachment #1.2: newloop-0.01.patch --]
[-- Type: text/plain, Size: 11068 bytes --]

--- linux-2.4.21-rc6-nfpending-nfnl/net/ipv4/netfilter/ip_tables.c	2003-06-01 12:14:42.000000000 +0200
+++ linux-2.4.21-rc6-nfpending-nfnl-newloop/net/ipv4/netfilter/ip_tables.c	2003-06-03 23:03:18.000000000 +0200
@@ -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
+ * 28 May 2003 Harald Welte <laforge@netfilter.org>
+ * 	- implement more efficient loop detection / mark_source_chains
+ *	  (Idea by Andre Uratsuka Manoel <andre@insite.com.br>, 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;
 		}


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

^ permalink raw reply	[flat|nested] 4+ messages in thread
end of thread, other threads:[~2003-06-14 14:12 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2003-06-06 17:54 fuzzy.patch and fuzzy.patch.ipv6 - again Hime Junior
2003-06-06 19:04 ` Maciej Soltysiak
  -- strict thread matches above, loose matches on Subject: below --
2003-06-05 10:34 [PATCH] first version of optimized mark_source_chains() Harald Welte
2003-06-06 13:31 ` fuzzy.patch and fuzzy.patch.ipv6 - again Wojciech "Sas" Cieciwa
2003-06-14 14:12   ` Martin Josefsson

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.