[Bridge] Re: do_IRQ: stack overflow: 872..

[Bridge] Re: do_IRQ: stack overflow: 872..

[Stephen Hemminger]

On Fri, 07 Jan 2005 17:05:59 +0000
David Woodhouse <dwmw2@infradead.org> wrote:

> On Sat, 2004-12-18 at 08:50 +0100, Andi Kleen wrote:
> > It's not really an oops, just a warning that stack space got quiet
> > tight.
> > 
> > The problem seems to be that the br netfilter code is nesting far too
> > deeply and recursing several times. Looks like a design bug to me,
> > it shouldn't do that.
> 
> I don't think it's recursing -- I think the stack trace is just a bit
> noisy. The problem is that the bridge code, especially with br_netfilter
> in the equation, is implicated in code paths which are just _too_ deep.
> This happens when you're bridging packets received in an interrupt while
> you were deep in journalling code, and it's also been seen with a call
> trace something like nfs->sunrpc->ip->bridge->br_netfilter.

Sounds like an argument for interrupt stacks.

> One option might be to make br_dev_xmit() just queue the packet rather
> than trying to deliver it to all the slave devices immediately. Then the
> actual retransmission can be handled from a context where we're _not_
> short of stack; perhaps from a dedicated kernel thread. 

Probably the solution would be to handle it in the filter code
that way if we are not filtering, we can use the interrupt path,
but if filtering just defer to a safer context (like soft irq).

> Unfortunately that approach would introduce a lot of latency on all
> packets we pass. Another option would be to have all architectures
> provide a stack_available() function and for br_dev_xmit() to queue the
> packet only if we're short of stack, while still sending most packets
> immediately. 

NO, that looks like a testablity and portablity nightmare.

[Bridge] Re: do_IRQ: stack overflow: 872..

[David Woodhouse]

On Fri, 2005-01-07 at 10:00 -0800, Stephen Hemminger wrote:
> > I don't think it's recursing -- I think the stack trace is just a bit
> > noisy. The problem is that the bridge code, especially with br_netfilter
> > in the equation, is implicated in code paths which are just _too_ deep.
> > This happens when you're bridging packets received in an interrupt while
> > you were deep in journalling code, and it's also been seen with a call
> > trace something like nfs->sunrpc->ip->bridge->br_netfilter.
> 
> Sounds like an argument for interrupt stacks.

The NFS case didn't involve hardware interrupts. Except for the one
which actually detected that the stack had overflowed.

> Probably the solution would be to handle it in the filter code
> that way if we are not filtering, we can use the interrupt path,
> but if filtering just defer to a safer context (like soft irq).

That's also a possibility.

> > Unfortunately that approach would introduce a lot of latency on all
> > packets we pass. Another option would be to have all architectures
> > provide a stack_available() function and for br_dev_xmit() to queue the
> > packet only if we're short of stack, while still sending most packets
> > immediately. 
> 
> NO, that looks like a testablity and portablity nightmare.

Yeah, I suppose I'm inclined to agree.

-- 
dwmw2

[Bridge] Re: do_IRQ: stack overflow: 872..

[Bart De Schuymer]

Op vr, 07-01-2005 te 10:00 -0800, schreef Stephen Hemminger:
> On Fri, 07 Jan 2005 17:05:59 +0000
> David Woodhouse <dwmw2@infradead.org> wrote:
> > I don't think it's recursing -- I think the stack trace is just a bit
> > noisy. The problem is that the bridge code, especially with br_netfilter
> > in the equation, is implicated in code paths which are just _too_ deep.
> > This happens when you're bridging packets received in an interrupt while
> > you were deep in journalling code, and it's also been seen with a call
> > trace something like nfs->sunrpc->ip->bridge->br_netfilter.
> 
> Sounds like an argument for interrupt stacks.
> 
> > One option might be to make br_dev_xmit() just queue the packet rather
> > than trying to deliver it to all the slave devices immediately. Then the
> > actual retransmission can be handled from a context where we're _not_
> > short of stack; perhaps from a dedicated kernel thread. 
> 
> Probably the solution would be to handle it in the filter code
> that way if we are not filtering, we can use the interrupt path,
> but if filtering just defer to a safer context (like soft irq).

How about something like the patch below (untested but compiles)?
The current netfilter scheme adds one function call to the call chain
for each NF_HOOK and NF_HOOK_THRESH. This can be prevented by executing
the okfn in the calling function instead of in nf_hook_slow().
I didn't check if there's any code that actually uses the return value
from NF_HOOK. If so, this patch won't work well in its current form as -
EPERM is now also returned for NF_QUEUE and NF_STOLEN.

Another 2 calls of okfn can be postponed in br_netfilter.c by adding
NF_STOP, which would work like NF_STOLEN except that okfn is still
called. But I'd first like to get the IPv4/IPv6 fix for br_netfilter.c
accepted (see another thread on netdev).

cheers,
Bart

--- linux-2.6.10/include/linux/netfilter.h.old	2005-01-07 20:41:30.000000000 +0100
+++ linux-2.6.10/include/linux/netfilter.h	2005-01-07 22:04:57.096626176 +0100
@@ -138,21 +138,32 @@ void nf_log_packet(int pf,
 /* This is gross, but inline doesn't cut it for avoiding the function
    call in fast path: gcc doesn't inline (needs value tracking?). --RR */
 #ifdef CONFIG_NETFILTER_DEBUG
-#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
- nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN)
-#define NF_HOOK_THRESH nf_hook_slow
+#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			    \
+({int __ret = nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN); \
+if (!__ret)								    \
+	__ret = (okfn)(skb);						    \
+__ret;})
+#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	    \
+({int __ret = nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh);  \
+if (!__ret)								    \
+	__ret = (okfn)(skb);						    \
+__ret;})
 #else
-#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
-(list_empty(&nf_hooks[(pf)][(hook)])					\
- ? (okfn)(skb)								\
- : nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN))
-#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	\
-(list_empty(&nf_hooks[(pf)][(hook)])					\
- ? (okfn)(skb)								\
- : nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), (thresh)))
+#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			     \
+({int __ret = 0;							     \
+if (list_empty(&nf_hooks[pf][hook]) ||					     \
+    !(__ret = nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN))) \
+	__ret = (okfn)(skb);						     \
+__ret;})
+#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	     \
+({int __ret = 0;							     \
+if (list_empty(&nf_hooks[pf][hook]) ||					     \
+    !(__ret = nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh)))  \
+	__ret = (okfn)(skb);						     \
+__ret;})
 #endif
 
-int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
+int nf_hook_slow(int pf, unsigned int hook, struct sk_buff **pskb,
 		 struct net_device *indev, struct net_device *outdev,
 		 int (*okfn)(struct sk_buff *), int thresh);
 
--- linux-2.6.10/net/core/netfilter.c.old	2005-01-07 20:41:47.000000000 +0100
+++ linux-2.6.10/net/core/netfilter.c	2005-01-07 21:52:13.659686232 +0100
@@ -494,7 +494,7 @@ static int nf_queue(struct sk_buff *skb,
 	return 1;
 }
 
-int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
+int nf_hook_slow(int pf, unsigned int hook, struct sk_buff **pskb,
 		 struct net_device *indev,
 		 struct net_device *outdev,
 		 int (*okfn)(struct sk_buff *),
@@ -508,30 +508,28 @@ int nf_hook_slow(int pf, unsigned int ho
 	rcu_read_lock();
 
 #ifdef CONFIG_NETFILTER_DEBUG
-	if (skb->nf_debug & (1 << hook)) {
+	if ((*pskb)->nf_debug & (1 << hook)) {
 		printk("nf_hook: hook %i already set.\n", hook);
-		nf_dump_skb(pf, skb);
+		nf_dump_skb(pf, *pskb);
 	}
 	skb->nf_debug |= (1 << hook);
 #endif
 
 	elem = &nf_hooks[pf][hook];
  next_hook:
-	verdict = nf_iterate(&nf_hooks[pf][hook], &skb, hook, indev,
+	verdict = nf_iterate(&nf_hooks[pf][hook], pskb, hook, indev,
 			     outdev, &elem, okfn, hook_thresh);
 	if (verdict == NF_QUEUE) {
 		NFDEBUG("nf_hook: Verdict = QUEUE.\n");
-		if (!nf_queue(skb, elem, pf, hook, indev, outdev, okfn))
+		if (!nf_queue(*pskb, elem, pf, hook, indev, outdev, okfn))
 			goto next_hook;
 	}
 
 	switch (verdict) {
-	case NF_ACCEPT:
-		ret = okfn(skb);
-		break;
-
 	case NF_DROP:
-		kfree_skb(skb);
+		kfree_skb(*pskb);
+	case NF_STOLEN:
+	case NF_QUEUE:
 		ret = -EPERM;
 		break;
 	}

[Bridge] Re: do_IRQ: stack overflow: 872..

[David S. Miller]

On Fri, 07 Jan 2005 22:27:21 +0100
Bart De Schuymer <bdschuym@pandora.be> wrote:

> How about something like the patch below (untested but compiles)?
> The current netfilter scheme adds one function call to the call chain
> for each NF_HOOK and NF_HOOK_THRESH. This can be prevented by executing
> the okfn in the calling function instead of in nf_hook_slow().
> I didn't check if there's any code that actually uses the return value
> from NF_HOOK. If so, this patch won't work well in its current form as -
> EPERM is now also returned for NF_QUEUE and NF_STOLEN.
> 
> Another 2 calls of okfn can be postponed in br_netfilter.c by adding
> NF_STOP, which would work like NF_STOLEN except that okfn is still
> called. But I'd first like to get the IPv4/IPv6 fix for br_netfilter.c
> accepted (see another thread on netdev).

I believe I put in your ipv4/ipv6 br_netfilter fix already.

This NF_HOOK() change looks interesting.  Could we also do something like
running the deeper ->hard_start_xmit() via a triggered tasklet or something
similar?

[Bridge] [PATCH/RFC] Reduce call chain length in netfilter (was: Re: do_IRQ: stack overflow: 872..)

[Bart De Schuymer]

Op di, 18-01-2005 te 13:57 -0800, schreef David S. Miller:
> On Fri, 07 Jan 2005 22:27:21 +0100
> Bart De Schuymer <bdschuym@pandora.be> wrote:
> 
> > How about something like the patch below (untested but compiles)?
> > The current netfilter scheme adds one function call to the call chain
> > for each NF_HOOK and NF_HOOK_THRESH. This can be prevented by executing
> > the okfn in the calling function instead of in nf_hook_slow().
> > I didn't check if there's any code that actually uses the return value
> > from NF_HOOK. If so, this patch won't work well in its current form as -
> > EPERM is now also returned for NF_QUEUE and NF_STOLEN.
> > 
> > Another 2 calls of okfn can be postponed in br_netfilter.c by adding
> > NF_STOP, which would work like NF_STOLEN except that okfn is still
> > called.
> This NF_HOOK() change looks interesting.  Could we also do something like
> running the deeper ->hard_start_xmit() via a triggered tasklet or something
> similar?

Hi,

The patch below reduces the call chain length for netfilter hooks by
executing the okfn() inside the caller function instead of inside
nf_hook_slow(). It also reduces the size of netfilter.o from 129590 to
129550 on my system.
The return value for NF_HOOK stays the same as before: 0 except when the
verdict was NF_DROP (in that case the return value becomes -EPERM).
The target NF_STOP is added to postpone two executions of okfn() in
br_netfilter.c, it works like NF_STOLEN except that the okfn() will
still be called.
The downside is that all .o files using NF_HOOK will enlarge.
Comments are welcome.

cheers,
Bart

Signed-off-by: Bart De Schuymer <bdschuym@pandora.be>

--- linux-2.6.1-rc1/include/linux/netfilter.h.old	2005-01-20 21:44:22.000000000 +0100
+++ linux-2.6.1-rc1/include/linux/netfilter.h	2005-01-22 22:06:14.000000000 +0100
@@ -18,7 +18,8 @@
 #define NF_STOLEN 2
 #define NF_QUEUE 3
 #define NF_REPEAT 4
-#define NF_MAX_VERDICT NF_REPEAT
+#define NF_STOP 5
+#define NF_MAX_VERDICT NF_STOP
 
 /* Generic cache responses from hook functions.
    <= 0x2000 is used for protocol-flags. */
@@ -138,23 +139,34 @@ void nf_log_packet(int pf,
 /* This is gross, but inline doesn't cut it for avoiding the function
    call in fast path: gcc doesn't inline (needs value tracking?). --RR */
 #ifdef CONFIG_NETFILTER_DEBUG
-#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
- nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN)
-#define NF_HOOK_THRESH nf_hook_slow
+#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			    \
+({int __ret = 0;							    \
+if (!nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN, &__ret);  \
+	__ret = (okfn)(skb);						    \
+__ret;})
+#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	    \
+({int __ret = 0;							    \
+if (!nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh, &__ret);   \
+	__ret = (okfn)(skb);						    \
+__ret;})
 #else
-#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
-(list_empty(&nf_hooks[(pf)][(hook)])					\
- ? (okfn)(skb)								\
- : nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN))
-#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	\
-(list_empty(&nf_hooks[(pf)][(hook)])					\
- ? (okfn)(skb)								\
- : nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), (thresh)))
+#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			     \
+({int __ret = 0;							     \
+if (list_empty(&nf_hooks[pf][hook]) ||					     \
+    !nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN, &__ret))   \
+	__ret = (okfn)(skb);						     \
+__ret;})
+#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	     \
+({int __ret = 0;							     \
+if (list_empty(&nf_hooks[pf][hook]) ||					     \
+    !nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh, &__ret))    \
+	__ret = (okfn)(skb);						     \
+__ret;})
 #endif
 
-int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
+int nf_hook_slow(int pf, unsigned int hook, struct sk_buff **pskb,
 		 struct net_device *indev, struct net_device *outdev,
-		 int (*okfn)(struct sk_buff *), int thresh);
+		 int (*okfn)(struct sk_buff *), int thresh, int *ret);
 
 /* Call setsockopt() */
 int nf_setsockopt(struct sock *sk, int pf, int optval, char __user *opt, 
--- linux-2.6.1-rc1/net/core/netfilter.c.old	2005-01-20 21:38:59.000000000 +0100
+++ linux-2.6.1-rc1/net/core/netfilter.c	2005-01-22 22:08:41.000000000 +0100
@@ -349,6 +349,8 @@ static unsigned int nf_iterate(struct li
 			       int (*okfn)(struct sk_buff *),
 			       int hook_thresh)
 {
+	unsigned int verdict;
+
 	/*
 	 * The caller must not block between calls to this
 	 * function because of risk of continuing from deleted element.
@@ -361,28 +363,18 @@ static unsigned int nf_iterate(struct li
 
 		/* Optimization: we don't need to hold module
                    reference here, since function can't sleep. --RR */
-		switch (elem->hook(hook, skb, indev, outdev, okfn)) {
-		case NF_QUEUE:
-			return NF_QUEUE;
-
-		case NF_STOLEN:
-			return NF_STOLEN;
-
-		case NF_DROP:
-			return NF_DROP;
-
-		case NF_REPEAT:
-			*i = (*i)->prev;
-			break;
-
+		verdict = elem->hook(hook, skb, indev, outdev, okfn);
+		if (verdict != NF_ACCEPT) {
 #ifdef CONFIG_NETFILTER_DEBUG
-		case NF_ACCEPT:
-			break;
-
-		default:
-			NFDEBUG("Evil return from %p(%u).\n", 
-				elem->hook, hook);
+			if (verdict > NF_MAX_VERDICT) {
+				NFDEBUG("Evil return from %p(%u).\n",
+				        elem->hook, hook);
+				continue;
+			}
 #endif
+			if (verdict != NF_REPEAT)
+				return verdict;
+			*i = (*i)->prev;
 		}
 	}
 	return NF_ACCEPT;
@@ -494,50 +486,47 @@ static int nf_queue(struct sk_buff *skb,
 	return 1;
 }
 
-int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
+/* Returns 0 if okfn() needs to be executed by the caller, -EPERM otherwise.
+ * Assumes *ret==0 when called. On return, *ret!=0 when verdict==NF_DROP */
+int nf_hook_slow(int pf, unsigned int hook, struct sk_buff **pskb,
 		 struct net_device *indev,
 		 struct net_device *outdev,
 		 int (*okfn)(struct sk_buff *),
-		 int hook_thresh)
+		 int hook_thresh, int *ret)
 {
 	struct list_head *elem;
 	unsigned int verdict;
-	int ret = 0;
+	int ret2 = 0;
 
 	/* We may already have this, but read-locks nest anyway */
 	rcu_read_lock();
 
 #ifdef CONFIG_NETFILTER_DEBUG
-	if (skb->nf_debug & (1 << hook)) {
+	if ((*pskb)->nf_debug & (1 << hook)) {
 		printk("nf_hook: hook %i already set.\n", hook);
-		nf_dump_skb(pf, skb);
+		nf_dump_skb(pf, *pskb);
 	}
 	skb->nf_debug |= (1 << hook);
 #endif
 
 	elem = &nf_hooks[pf][hook];
  next_hook:
-	verdict = nf_iterate(&nf_hooks[pf][hook], &skb, hook, indev,
+	verdict = nf_iterate(&nf_hooks[pf][hook], pskb, hook, indev,
 			     outdev, &elem, okfn, hook_thresh);
-	if (verdict == NF_QUEUE) {
+	if (verdict == NF_ACCEPT || verdict == NF_STOP)
+		goto unlock;
+	else if (verdict == NF_DROP) {
+		kfree_skb(*pskb);
+		*ret = -EPERM;
+	} else if (verdict == NF_QUEUE) {
 		NFDEBUG("nf_hook: Verdict = QUEUE.\n");
-		if (!nf_queue(skb, elem, pf, hook, indev, outdev, okfn))
+		if (!nf_queue(*pskb, elem, pf, hook, indev, outdev, okfn))
 			goto next_hook;
 	}
-
-	switch (verdict) {
-	case NF_ACCEPT:
-		ret = okfn(skb);
-		break;
-
-	case NF_DROP:
-		kfree_skb(skb);
-		ret = -EPERM;
-		break;
-	}
-
+	ret2 = -EPERM;
+unlock:
 	rcu_read_unlock();
-	return ret;
+	return ret2;
 }
 
 void nf_reinject(struct sk_buff *skb, struct nf_info *info,
--- linux-2.6.1-rc1/net/bridge/br_netfilter.c.old	2005-01-20 21:43:08.000000000 +0100
+++ linux-2.6.1-rc1/net/bridge/br_netfilter.c	2005-01-22 21:20:06.000000000 +0100
@@ -829,8 +829,7 @@ static unsigned int ip_sabotage_in(unsig
 {
 	if ((*pskb)->nf_bridge &&
 	    !((*pskb)->nf_bridge->mask & BRNF_NF_BRIDGE_PREROUTING)) {
-		okfn(*pskb);
-		return NF_STOLEN;
+		return NF_STOP;
 	}
 
 	return NF_ACCEPT;
@@ -888,8 +887,7 @@ static unsigned int ip_sabotage_out(unsi
 		if (out->priv_flags & IFF_802_1Q_VLAN)
 			nf_bridge->netoutdev = (struct net_device *)out;
 #endif
-		okfn(skb);
-		return NF_STOLEN;
+		return NF_STOP;
 	}
 
 	return NF_ACCEPT;

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter (was: Re: do_IRQ: stack overflow: 872..)

[Martin Josefsson]

[-- Attachment #1: Type: text/plain, Size: 1557 bytes --]

On Sat, 2005-01-22 at 23:30 +0100, Bart De Schuymer wrote:

Hi Bart

> @@ -138,23 +139,34 @@ void nf_log_packet(int pf,
>  /* This is gross, but inline doesn't cut it for avoiding the function
>     call in fast path: gcc doesn't inline (needs value tracking?). --RR */
>  #ifdef CONFIG_NETFILTER_DEBUG
> -#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
> - nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN)
> -#define NF_HOOK_THRESH nf_hook_slow
> +#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			    \
> +({int __ret = 0;							    \
> +if (!nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN, &__ret);  \
> +	__ret = (okfn)(skb);						    \
> +__ret;})
> +#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	    \
> +({int __ret = 0;							    \
> +if (!nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh, &__ret);   \
> +	__ret = (okfn)(skb);						    \
> +__ret;})
>  #else

I guess you never testcompiled with CONFIG_NETFILTER_DEBUG set :)
The if-statements above needs to have ; replaced with )

> +			if (verdict > NF_MAX_VERDICT) {
> +				NFDEBUG("Evil return from %p(%u).\n",
> +				        elem->hook, hook);
> +				continue;
> +			}

Maybe add unlikely() around the test?

Otherwise the changes look sane.

The reoganisation of things in nf_hook_slow() shouldn't cause any
performance changes, I tried to benchmark various variations of that
code some time ago but the result of the changes were more or less in
the noise.

-- 
/Martin

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter (was: Re: do_IRQ: stack overflow: 872..)

[Bart De Schuymer]

Op zo, 23-01-2005 te 00:22 +0100, schreef Martin Josefsson:
> On Sat, 2005-01-22 at 23:30 +0100, Bart De Schuymer wrote:
> 
> Hi Bart

Hi Martin,

> I guess you never testcompiled with CONFIG_NETFILTER_DEBUG set :)

Oops, no. I was imagining I could code that without error...
There was another compile error with CONFIG_NETFILTER_DEBUG in the patch
(skb that should have been (*pskb)) :(

> > +			if (verdict > NF_MAX_VERDICT) {
> > +				NFDEBUG("Evil return from %p(%u).\n",
> > +				        elem->hook, hook);
> > +				continue;
> > +			}
> 
> Maybe add unlikely() around the test?

OK. I added another one around another debugging if-statement.

cheers,
Bart

--- linux-2.6.11-rc1/include/linux/netfilter.h.old	2005-01-23 13:31:58.895886808 +0100
+++ linux-2.6.11-rc1/include/linux/netfilter.h	2005-01-23 13:32:02.853285192 +0100
@@ -18,7 +18,8 @@
 #define NF_STOLEN 2
 #define NF_QUEUE 3
 #define NF_REPEAT 4
-#define NF_MAX_VERDICT NF_REPEAT
+#define NF_STOP 5
+#define NF_MAX_VERDICT NF_STOP
 
 /* Generic cache responses from hook functions.
    <= 0x2000 is used for protocol-flags. */
@@ -138,23 +139,34 @@ void nf_log_packet(int pf,
 /* This is gross, but inline doesn't cut it for avoiding the function
    call in fast path: gcc doesn't inline (needs value tracking?). --RR */
 #ifdef CONFIG_NETFILTER_DEBUG
-#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
- nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN)
-#define NF_HOOK_THRESH nf_hook_slow
+#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			    \
+({int __ret = 0;							    \
+if (!nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN, &__ret))  \
+	__ret = (okfn)(skb);						    \
+__ret;})
+#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	    \
+({int __ret = 0;							    \
+if (!nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh, &__ret))   \
+	__ret = (okfn)(skb);						    \
+__ret;})
 #else
-#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
-(list_empty(&nf_hooks[(pf)][(hook)])					\
- ? (okfn)(skb)								\
- : nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN))
-#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	\
-(list_empty(&nf_hooks[(pf)][(hook)])					\
- ? (okfn)(skb)								\
- : nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), (thresh)))
+#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			     \
+({int __ret = 0;							     \
+if (list_empty(&nf_hooks[pf][hook]) ||					     \
+    !nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN, &__ret))   \
+	__ret = (okfn)(skb);						     \
+__ret;})
+#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	     \
+({int __ret = 0;							     \
+if (list_empty(&nf_hooks[pf][hook]) ||					     \
+    !nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh, &__ret))    \
+	__ret = (okfn)(skb);						     \
+__ret;})
 #endif
 
-int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
+int nf_hook_slow(int pf, unsigned int hook, struct sk_buff **pskb,
 		 struct net_device *indev, struct net_device *outdev,
-		 int (*okfn)(struct sk_buff *), int thresh);
+		 int (*okfn)(struct sk_buff *), int thresh, int *ret);
 
 /* Call setsockopt() */
 int nf_setsockopt(struct sock *sk, int pf, int optval, char __user *opt, 
--- linux-2.6.11-rc1/net/core/netfilter.c.old	2005-01-23 13:31:48.980394192 +0100
+++ linux-2.6.11-rc1/net/core/netfilter.c	2005-01-23 13:32:02.856284736 +0100
@@ -349,6 +349,8 @@ static unsigned int nf_iterate(struct li
 			       int (*okfn)(struct sk_buff *),
 			       int hook_thresh)
 {
+	unsigned int verdict;
+
 	/*
 	 * The caller must not block between calls to this
 	 * function because of risk of continuing from deleted element.
@@ -361,28 +363,18 @@ static unsigned int nf_iterate(struct li
 
 		/* Optimization: we don't need to hold module
                    reference here, since function can't sleep. --RR */
-		switch (elem->hook(hook, skb, indev, outdev, okfn)) {
-		case NF_QUEUE:
-			return NF_QUEUE;
-
-		case NF_STOLEN:
-			return NF_STOLEN;
-
-		case NF_DROP:
-			return NF_DROP;
-
-		case NF_REPEAT:
-			*i = (*i)->prev;
-			break;
-
+		verdict = elem->hook(hook, skb, indev, outdev, okfn);
+		if (verdict != NF_ACCEPT) {
 #ifdef CONFIG_NETFILTER_DEBUG
-		case NF_ACCEPT:
-			break;
-
-		default:
-			NFDEBUG("Evil return from %p(%u).\n", 
-				elem->hook, hook);
+			if (unlikely(verdict > NF_MAX_VERDICT)) {
+				NFDEBUG("Evil return from %p(%u).\n",
+				        elem->hook, hook);
+				continue;
+			}
 #endif
+			if (verdict != NF_REPEAT)
+				return verdict;
+			*i = (*i)->prev;
 		}
 	}
 	return NF_ACCEPT;
@@ -494,50 +486,47 @@ static int nf_queue(struct sk_buff *skb,
 	return 1;
 }
 
-int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
+/* Returns 0 if okfn() needs to be executed by the caller, -EPERM otherwise.
+ * Assumes *ret==0 when called. On return, *ret!=0 when verdict==NF_DROP */
+int nf_hook_slow(int pf, unsigned int hook, struct sk_buff **pskb,
 		 struct net_device *indev,
 		 struct net_device *outdev,
 		 int (*okfn)(struct sk_buff *),
-		 int hook_thresh)
+		 int hook_thresh, int *ret)
 {
 	struct list_head *elem;
 	unsigned int verdict;
-	int ret = 0;
+	int ret2 = 0;
 
 	/* We may already have this, but read-locks nest anyway */
 	rcu_read_lock();
 
 #ifdef CONFIG_NETFILTER_DEBUG
-	if (skb->nf_debug & (1 << hook)) {
+	if (unlikely((*pskb)->nf_debug & (1 << hook))) {
 		printk("nf_hook: hook %i already set.\n", hook);
-		nf_dump_skb(pf, skb);
+		nf_dump_skb(pf, *pskb);
 	}
-	skb->nf_debug |= (1 << hook);
+	(*pskb)->nf_debug |= (1 << hook);
 #endif
 
 	elem = &nf_hooks[pf][hook];
  next_hook:
-	verdict = nf_iterate(&nf_hooks[pf][hook], &skb, hook, indev,
+	verdict = nf_iterate(&nf_hooks[pf][hook], pskb, hook, indev,
 			     outdev, &elem, okfn, hook_thresh);
-	if (verdict == NF_QUEUE) {
+	if (verdict == NF_ACCEPT || verdict == NF_STOP)
+		goto unlock;
+	else if (verdict == NF_DROP) {
+		kfree_skb(*pskb);
+		*ret = -EPERM;
+	} else if (verdict == NF_QUEUE) {
 		NFDEBUG("nf_hook: Verdict = QUEUE.\n");
-		if (!nf_queue(skb, elem, pf, hook, indev, outdev, okfn))
+		if (!nf_queue(*pskb, elem, pf, hook, indev, outdev, okfn))
 			goto next_hook;
 	}
-
-	switch (verdict) {
-	case NF_ACCEPT:
-		ret = okfn(skb);
-		break;
-
-	case NF_DROP:
-		kfree_skb(skb);
-		ret = -EPERM;
-		break;
-	}
-
+	ret2 = -EPERM;
+unlock:
 	rcu_read_unlock();
-	return ret;
+	return ret2;
 }
 
 void nf_reinject(struct sk_buff *skb, struct nf_info *info,
--- linux-2.6.11-rc1/net/bridge/br_netfilter.c.old	2005-01-23 13:31:39.080899144 +0100
+++ linux-2.6.11-rc1/net/bridge/br_netfilter.c	2005-01-23 13:32:02.861283976 +0100
@@ -829,8 +829,7 @@ static unsigned int ip_sabotage_in(unsig
 {
 	if ((*pskb)->nf_bridge &&
 	    !((*pskb)->nf_bridge->mask & BRNF_NF_BRIDGE_PREROUTING)) {
-		okfn(*pskb);
-		return NF_STOLEN;
+		return NF_STOP;
 	}
 
 	return NF_ACCEPT;
@@ -888,8 +887,7 @@ static unsigned int ip_sabotage_out(unsi
 		if (out->priv_flags & IFF_802_1Q_VLAN)
 			nf_bridge->netoutdev = (struct net_device *)out;
 #endif
-		okfn(skb);
-		return NF_STOLEN;
+		return NF_STOP;
 	}
 
 	return NF_ACCEPT;

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter (was: Re: do_IRQ: stack overflow: 872..)

[Martin Josefsson]

[-- Attachment #1: Type: text/plain, Size: 867 bytes --]

On Sun, 2005-01-23 at 13:40 +0100, Bart De Schuymer wrote:

> Hi Martin,

Hi Bart

> > I guess you never testcompiled with CONFIG_NETFILTER_DEBUG set :)
> 
> Oops, no. I was imagining I could code that without error...
> There was another compile error with CONFIG_NETFILTER_DEBUG in the patch
> (skb that should have been (*pskb)) :(

:)

> > > +			if (verdict > NF_MAX_VERDICT) {
> > > +				NFDEBUG("Evil return from %p(%u).\n",
> > > +				        elem->hook, hook);
> > > +				continue;
> > > +			}
> > 
> > Maybe add unlikely() around the test?
> 
> OK. I added another one around another debugging if-statement.

I'm now running a kernel with this patch and everything seems to still
be working.
So unless someone else has something to comment I think this should be
applied.
The decrease in call-depth is important.

-- 
/Martin

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter (was: Re: do_IRQ: stack overflow: 872..)

[David S. Miller]

On Sun, 23 Jan 2005 17:08:29 +0100
Martin Josefsson <gandalf@wlug.westbo.se> wrote:

> I'm now running a kernel with this patch and everything seems to still
> be working.
> So unless someone else has something to comment I think this should be
> applied.
> The decrease in call-depth is important.

I would like to see at least one ACK from the netfilter
folks.  Bart or Rusty, could you forward to patch to
netfilter-devel for review?

I have some other ideas about how bridging might be able
to save some call chain depth... but I need to think about
it some more before proposing or even trying to implement.
(basically something akin to how we do route level packet
 output, via dst_output(), but instead we're doing this
 at ->hard_start_xmit() time)

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter (was: Re: do_IRQ: stack overflow: 872..)

[Bart De Schuymer]

Op di, 25-01-2005 te 22:05 -0800, schreef David S. Miller: 
> On Sun, 23 Jan 2005 17:08:29 +0100
> Martin Josefsson <gandalf@wlug.westbo.se> wrote:
> 
> > I'm now running a kernel with this patch and everything seems to still
> > be working.
> > So unless someone else has something to comment I think this should be
> > applied.
> > The decrease in call-depth is important.
> 
> I would like to see at least one ACK from the netfilter
> folks.  Bart or Rusty, could you forward to patch to
> netfilter-devel for review?

AFAIK Martin is in the netfilter core team. Anyway, I just included
netfilter-devel.

Does anyone have objections to this patch, which reduces the netfilter
call chain length?

> I have some other ideas about how bridging might be able
> to save some call chain depth... but I need to think about
> it some more before proposing or even trying to implement.
> (basically something akin to how we do route level packet
>  output, via dst_output(), but instead we're doing this
>  at ->hard_start_xmit() time)

I'm all ears :)


--- linux-2.6.11-rc1/include/linux/netfilter.h.old	2005-01-23 13:31:58.895886808 +0100
+++ linux-2.6.11-rc1/include/linux/netfilter.h	2005-01-23 13:32:02.853285192 +0100
@@ -18,7 +18,8 @@
 #define NF_STOLEN 2
 #define NF_QUEUE 3
 #define NF_REPEAT 4
-#define NF_MAX_VERDICT NF_REPEAT
+#define NF_STOP 5
+#define NF_MAX_VERDICT NF_STOP
 
 /* Generic cache responses from hook functions.
    <= 0x2000 is used for protocol-flags. */
@@ -138,23 +139,34 @@ void nf_log_packet(int pf,
 /* This is gross, but inline doesn't cut it for avoiding the function
    call in fast path: gcc doesn't inline (needs value tracking?). --RR */
 #ifdef CONFIG_NETFILTER_DEBUG
-#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
- nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN)
-#define NF_HOOK_THRESH nf_hook_slow
+#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			    \
+({int __ret = 0;							    \
+if (!nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN, &__ret))  \
+	__ret = (okfn)(skb);						    \
+__ret;})
+#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	    \
+({int __ret = 0;							    \
+if (!nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh, &__ret))   \
+	__ret = (okfn)(skb);						    \
+__ret;})
 #else
-#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			\
-(list_empty(&nf_hooks[(pf)][(hook)])					\
- ? (okfn)(skb)								\
- : nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), INT_MIN))
-#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	\
-(list_empty(&nf_hooks[(pf)][(hook)])					\
- ? (okfn)(skb)								\
- : nf_hook_slow((pf), (hook), (skb), (indev), (outdev), (okfn), (thresh)))
+#define NF_HOOK(pf, hook, skb, indev, outdev, okfn)			     \
+({int __ret = 0;							     \
+if (list_empty(&nf_hooks[pf][hook]) ||					     \
+    !nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, INT_MIN, &__ret))   \
+	__ret = (okfn)(skb);						     \
+__ret;})
+#define NF_HOOK_THRESH(pf, hook, skb, indev, outdev, okfn, thresh)	     \
+({int __ret = 0;							     \
+if (list_empty(&nf_hooks[pf][hook]) ||					     \
+    !nf_hook_slow(pf, hook, &(skb), indev, outdev, okfn, thresh, &__ret))    \
+	__ret = (okfn)(skb);						     \
+__ret;})
 #endif
 
-int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
+int nf_hook_slow(int pf, unsigned int hook, struct sk_buff **pskb,
 		 struct net_device *indev, struct net_device *outdev,
-		 int (*okfn)(struct sk_buff *), int thresh);
+		 int (*okfn)(struct sk_buff *), int thresh, int *ret);
 
 /* Call setsockopt() */
 int nf_setsockopt(struct sock *sk, int pf, int optval, char __user *opt, 
--- linux-2.6.11-rc1/net/core/netfilter.c.old	2005-01-23 13:31:48.980394192 +0100
+++ linux-2.6.11-rc1/net/core/netfilter.c	2005-01-23 13:32:02.856284736 +0100
@@ -349,6 +349,8 @@ static unsigned int nf_iterate(struct li
 			       int (*okfn)(struct sk_buff *),
 			       int hook_thresh)
 {
+	unsigned int verdict;
+
 	/*
 	 * The caller must not block between calls to this
 	 * function because of risk of continuing from deleted element.
@@ -361,28 +363,18 @@ static unsigned int nf_iterate(struct li
 
 		/* Optimization: we don't need to hold module
                    reference here, since function can't sleep. --RR */
-		switch (elem->hook(hook, skb, indev, outdev, okfn)) {
-		case NF_QUEUE:
-			return NF_QUEUE;
-
-		case NF_STOLEN:
-			return NF_STOLEN;
-
-		case NF_DROP:
-			return NF_DROP;
-
-		case NF_REPEAT:
-			*i = (*i)->prev;
-			break;
-
+		verdict = elem->hook(hook, skb, indev, outdev, okfn);
+		if (verdict != NF_ACCEPT) {
 #ifdef CONFIG_NETFILTER_DEBUG
-		case NF_ACCEPT:
-			break;
-
-		default:
-			NFDEBUG("Evil return from %p(%u).\n", 
-				elem->hook, hook);
+			if (unlikely(verdict > NF_MAX_VERDICT)) {
+				NFDEBUG("Evil return from %p(%u).\n",
+				        elem->hook, hook);
+				continue;
+			}
 #endif
+			if (verdict != NF_REPEAT)
+				return verdict;
+			*i = (*i)->prev;
 		}
 	}
 	return NF_ACCEPT;
@@ -494,50 +486,47 @@ static int nf_queue(struct sk_buff *skb,
 	return 1;
 }
 
-int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
+/* Returns 0 if okfn() needs to be executed by the caller, -EPERM otherwise.
+ * Assumes *ret==0 when called. On return, *ret!=0 when verdict==NF_DROP */
+int nf_hook_slow(int pf, unsigned int hook, struct sk_buff **pskb,
 		 struct net_device *indev,
 		 struct net_device *outdev,
 		 int (*okfn)(struct sk_buff *),
-		 int hook_thresh)
+		 int hook_thresh, int *ret)
 {
 	struct list_head *elem;
 	unsigned int verdict;
-	int ret = 0;
+	int ret2 = 0;
 
 	/* We may already have this, but read-locks nest anyway */
 	rcu_read_lock();
 
 #ifdef CONFIG_NETFILTER_DEBUG
-	if (skb->nf_debug & (1 << hook)) {
+	if (unlikely((*pskb)->nf_debug & (1 << hook))) {
 		printk("nf_hook: hook %i already set.\n", hook);
-		nf_dump_skb(pf, skb);
+		nf_dump_skb(pf, *pskb);
 	}
-	skb->nf_debug |= (1 << hook);
+	(*pskb)->nf_debug |= (1 << hook);
 #endif
 
 	elem = &nf_hooks[pf][hook];
  next_hook:
-	verdict = nf_iterate(&nf_hooks[pf][hook], &skb, hook, indev,
+	verdict = nf_iterate(&nf_hooks[pf][hook], pskb, hook, indev,
 			     outdev, &elem, okfn, hook_thresh);
-	if (verdict == NF_QUEUE) {
+	if (verdict == NF_ACCEPT || verdict == NF_STOP)
+		goto unlock;
+	else if (verdict == NF_DROP) {
+		kfree_skb(*pskb);
+		*ret = -EPERM;
+	} else if (verdict == NF_QUEUE) {
 		NFDEBUG("nf_hook: Verdict = QUEUE.\n");
-		if (!nf_queue(skb, elem, pf, hook, indev, outdev, okfn))
+		if (!nf_queue(*pskb, elem, pf, hook, indev, outdev, okfn))
 			goto next_hook;
 	}
-
-	switch (verdict) {
-	case NF_ACCEPT:
-		ret = okfn(skb);
-		break;
-
-	case NF_DROP:
-		kfree_skb(skb);
-		ret = -EPERM;
-		break;
-	}
-
+	ret2 = -EPERM;
+unlock:
 	rcu_read_unlock();
-	return ret;
+	return ret2;
 }
 
 void nf_reinject(struct sk_buff *skb, struct nf_info *info,
--- linux-2.6.11-rc1/net/bridge/br_netfilter.c.old	2005-01-23 13:31:39.080899144 +0100
+++ linux-2.6.11-rc1/net/bridge/br_netfilter.c	2005-01-23 13:32:02.861283976 +0100
@@ -829,8 +829,7 @@ static unsigned int ip_sabotage_in(unsig
 {
 	if ((*pskb)->nf_bridge &&
 	    !((*pskb)->nf_bridge->mask & BRNF_NF_BRIDGE_PREROUTING)) {
-		okfn(*pskb);
-		return NF_STOLEN;
+		return NF_STOP;
 	}
 
 	return NF_ACCEPT;
@@ -888,8 +887,7 @@ static unsigned int ip_sabotage_out(unsi
 		if (out->priv_flags & IFF_802_1Q_VLAN)
 			nf_bridge->netoutdev = (struct net_device *)out;
 #endif
-		okfn(skb);
-		return NF_STOLEN;
+		return NF_STOP;
 	}
 
 	return NF_ACCEPT;

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[Patrick McHardy]

Bart De Schuymer wrote:

>Does anyone have objections to this patch, which reduces the netfilter
>call chain length?
>
Looks fine to me.

Signed-off-by: Patrick McHardy <kaber@trash.net>

Regards
Patrick

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[David S. Miller]

On Thu, 27 Jan 2005 00:49:01 +0100
Patrick McHardy <kaber@trash.net> wrote:

> Bart De Schuymer wrote:
> 
> >Does anyone have objections to this patch, which reduces the netfilter
> >call chain length?
> >
> Looks fine to me.
> 
> Signed-off-by: Patrick McHardy <kaber@trash.net>

Ok, I applied this.

While reviewing I thought it may be an issue that the new macros
potentially change skb.  It really isn't an issue because NF_HOOK()
calls pass ownership of the SKB over from the caller.

Although technically, someone could go:

	skb_get(skb);
	err = NF_HOOK(... skb ...);
	... do stuff with skb ...
	kfree_skb(skb);

but that would cause other problems and I audited the entire tree
and nobody attempts anything like this currently.  'skb' always
dies at the NF_HOOK() call site.

I guess if we wanted to preserve NF_HOOK*() semantics even in such
a case we could use a local "__skb" var in the macro's basic block.

Another huge downside to this change I was worried about
was from a code generation point of view.  Since we now take the
address of "skb", gcc cannot generate tail-calls for the common
case of:

	return NF_HOOK(...);

when netfilter is enabled.  Ho hum...

Wait...

This is actually an important point!  Since gcc is generating a tail-
call for NF_HOOK() today, there is no stack savings for NF_HOOK()
created by this patch.  The only real gain is the NF_STOP stuff
for bridge netfilter.

I'm backing this out of my tree, let's think about this some more.
Perhaps it's only worth adding the NF_STOP thing and just making
nf_hook_slow() do the okfn(skb); call in that case?

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[Patrick McHardy]

David S. Miller wrote:

>While reviewing I thought it may be an issue that the new macros
>potentially change skb.  It really isn't an issue because NF_HOOK()
>calls pass ownership of the SKB over from the caller.
>
>Although technically, someone could go:
>
>	skb_get(skb);
>	err = NF_HOOK(... skb ...);
>	... do stuff with skb ...
>	kfree_skb(skb);
>
>but that would cause other problems and I audited the entire tree
>and nobody attempts anything like this currently.  'skb' always
>dies at the NF_HOOK() call site.
>
Yes, it has always been illegal to use the skb after NF_HOOK.

>Another huge downside to this change I was worried about
>was from a code generation point of view.  Since we now take the
>address of "skb", gcc cannot generate tail-calls for the common
>case of:
>
>	return NF_HOOK(...);
>
>when netfilter is enabled.  Ho hum...
>
 From what I can see it doesn't generate tail-calls currently:

 34c:   45 31 c0                xor    %r8d,%r8d
 34f:   4c 89 e2                mov    %r12,%rdx
 352:   be 01 00 00 00          mov    $0x1,%esi
 357:   bf 02 00 00 00          mov    $0x2,%edi
 35c:   c7 04 24 00 00 00 80    movl   $0x80000000,(%rsp)
 363:   e8 00 00 00 00          callq  368 <ip_local_deliver+0x248>
                        364: R_X86_64_PC32      
nf_hook_slow+0xfffffffffffffffc
 368:   48 83 c4 10             add    $0x10,%rsp
 36c:   5b                      pop    %rbx
 36d:   5d                      pop    %rbp
 36e:   41 5c                   pop    %r12
 370:   c3                      retq

According to something I found on the internet, gcc only optimizes
tail-calls if some conditions are met, in this case most importantly
the space required for the arguments to the function called at the tail
must not exceed the space required for the arguments of the function
itself. nf_hook_slow takes 6 arguments, probably more than any caller.

Regards
Patrick

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[David S. Miller]

On Thu, 27 Jan 2005 18:50:50 +0100
Patrick McHardy <kaber@trash.net> wrote:

>  From what I can see it doesn't generate tail-calls currently:

Indeed... It even doesn't do this on Sparc64 either, even for
the okfn(skb) call which I was sure it would.

It won't tail-call for function pointers for some strance reason
as exhibited by this simple test:

struct sk_buff {
	int foo;
};

int invoke(struct sk_buff *skb, int (*okfn)(struct sk_buff *))
{
	return okfn(skb);
}

extern int test_func(struct sk_buff *);

int invoke2(struct sk_buff *skb)
{
	return test_func(skb);
}

In the generated asm on sparc64, invoke2() gets a tail-call
whereas invoke() does not.  Hmmm...

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[Bart De Schuymer]

Op do, 27-01-2005 te 11:47 -0800, schreef David S. Miller:
> On Thu, 27 Jan 2005 18:50:50 +0100
> Patrick McHardy <kaber@trash.net> wrote:
> 
> >  From what I can see it doesn't generate tail-calls currently:
> 
> Indeed... It even doesn't do this on Sparc64 either, even for
> the okfn(skb) call which I was sure it would.
> 
> It won't tail-call for function pointers for some strance reason
> as exhibited by this simple test:
> 
> struct sk_buff {
> 	int foo;
> };
> 
> int invoke(struct sk_buff *skb, int (*okfn)(struct sk_buff *))
> {
> 	return okfn(skb);
> }
> 
> extern int test_func(struct sk_buff *);
> 
> int invoke2(struct sk_buff *skb)
> {
> 	return test_func(skb);
> }
> 
> In the generated asm on sparc64, invoke2() gets a tail-call
> whereas invoke() does not.  Hmmm...

Pasha (<snort2004@mail.ru>) is currently using a bridge-nf patch vs
2.4.29 with the changes I sent to you. After two days he sent me
(yesterday) a message that all is well. Without the patch he was getting
the stack overflow oopses.

cheers,
Bart

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[Patrick McHardy]

David S. Miller wrote:

>In the generated asm on sparc64, invoke2() gets a tail-call
>whereas invoke() does not.  Hmmm...
>
>
Apparently support for indirect tail-calls was added to gcc 3.4.

gcc-3.3.5:
0x0000000000000000 <invoke+0>:  sub    $0x8,%rsp
0x0000000000000004 <invoke+4>:  callq  *%esi
0x0000000000000006 <invoke+6>:  add    $0x8,%rsp
0x000000000000000a <invoke+10>: retq  

gcc-3.4.4:
0x0000000000000000 <invoke+0>:  mov    %rsi,%r11
0x0000000000000003 <invoke+3>:  jmpq   *%r11d

Regards
Patrick

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[David S. Miller]

On Thu, 27 Jan 2005 23:48:04 +0100
Patrick McHardy <kaber@trash.net> wrote:

> David S. Miller wrote:
> 
> >In the generated asm on sparc64, invoke2() gets a tail-call
> >whereas invoke() does not.  Hmmm...
>
> Apparently support for indirect tail-calls was added to gcc 3.4.

Good data point.

I've been trying to figure out ways to decrease the number of
args that get sent to nf_hook_slow but this would require
some API changes unfortunately.

One idea goes like this, we create little descriptors of the form:

struct nf_hook_desc {
	int (*okfn)(struct sk_buff *);
	int pf;
	int hook;
};

Then NF_HOOK*() callsites do something like this:

static const struct nf_hook_desc nf_ip_local_out = {
	.okfn = dst_output,
	.pf = PF_INET,
	.hook = NF_IP_LOCAL_OUT,
};

...

	/* Send it out. */
	return NF_HOOK(&nf_ip_local_out, skb, NULL, rt->u.dst.dev);

This gets us down to 4 arguments from 6.  I think we can kill
one more.

It is never the case that both indev and outdev are both
set, so we can use some nf_hook_desc piece of state to
indicate which (in or out) the passed device pointer is.

Oh yes, we can nicely add the thresh thing in here too
while we're at it.

So the final nf_hook_desc might look something something like:

struct nf_hook_desc {
	int (*okfn)(struct sk_buff *);
	int hook;
	int thresh;
	u8 pf; /* AF_MAX is 32 */
	u8 is_output;
};

Hook could possibly use a smaller type as well to condense
the size of this thing even further.  I don't know if there
are any nice assumptions we can make about the hook numbers.

Now, back to the compatability issue.  We could create a
new macro, NF_HOOK_DESC() and keep the existing ones around
via some nf_hook_slow() that basically does:

int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
		 struct net_device *indev, struct net_device *outdev,
		 int (*okfn)(struct sk_buff *), int thresh)
{
	struct nf_hook_desc desc;

	desc.okfn = okfn;
	desc.hook = hook;
	desc.thresh = thresh;
	desc.pf = pf;
	desc.is_output = (outdev != NULL);
	return nf_hook_desc(&desc, skb, (outdev ? outdev : indev));
}

So the final new stuff looks something like:

#ifdef CONFIG_NETFILTER
struct nf_hook_desc {
	int (*okfn)(struct sk_buff *);
	int hook;
	int thresh;
	u8 pf; /* AF_MAX is 32 */
	u8 is_output;
};
#define NF_DESC_DECLARE(_name, _okfn, _hook, _thresh, _pf, _is_output) \
static const struct nf_hook_desc _name = { \
	.okfn = _okfn, \
	.hook = _hook, \
	.thresh = _thresh, \
	.pf = _pf, \
	.is_output = _is_output, \
};

extern int nf_hook_desc(struct nf_hook_desc *desc, struct sk_buff *skb,
			struct net_device *dev);

#define NF_HOOK_DESC(_desc, _skb, _dev) \
	nf_hook_desc(_desc, _skb, _dev)
#endif

Just throwing around ideas... comments?

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[Patrick McHardy]

David S. Miller wrote:

>I've been trying to figure out ways to decrease the number of
>args that get sent to nf_hook_slow but this would require
>some API changes unfortunately.
>
>One idea goes like this, we create little descriptors of the form:
>
>struct nf_hook_desc {
>	int (*okfn)(struct sk_buff *);
>	int pf;
>	int hook;
>};
>
>Then NF_HOOK*() callsites do something like this:
>
>static const struct nf_hook_desc nf_ip_local_out = {
>	.okfn = dst_output,
>	.pf = PF_INET,
>	.hook = NF_IP_LOCAL_OUT,
>};
>
>...
>
>	/* Send it out. */
>	return NF_HOOK(&nf_ip_local_out, skb, NULL, rt->u.dst.dev);
>
>This gets us down to 4 arguments from 6.  I think we can kill
>one more.
>
>It is never the case that both indev and outdev are both
>set, so we can use some nf_hook_desc piece of state to
>indicate which (in or out) the passed device pointer is.
>  
>
indev and outdev are both set in the forward hook.

>Oh yes, we can nicely add the thresh thing in here too
>while we're at it.
>
>So the final nf_hook_desc might look something something like:
>
>struct nf_hook_desc {
>	int (*okfn)(struct sk_buff *);
>	int hook;
>	int thresh;
>	u8 pf; /* AF_MAX is 32 */
>	u8 is_output;
>};
>
>Hook could possibly use a smaller type as well to condense
>the size of this thing even further.  I don't know if there
>are any nice assumptions we can make about the hook numbers.
>  
>
There are currently five hooks. I really hope we'll never reach
256, so u8 should be big enough.

>Now, back to the compatability issue.  We could create a
>new macro, NF_HOOK_DESC() and keep the existing ones around
>via some nf_hook_slow() that basically does:
>
>int nf_hook_slow(int pf, unsigned int hook, struct sk_buff *skb,
>		 struct net_device *indev, struct net_device *outdev,
>		 int (*okfn)(struct sk_buff *), int thresh)
>{
>	struct nf_hook_desc desc;
>
>	desc.okfn = okfn;
>	desc.hook = hook;
>	desc.thresh = thresh;
>	desc.pf = pf;
>	desc.is_output = (outdev != NULL);
>	return nf_hook_desc(&desc, skb, (outdev ? outdev : indev));
>}
>
>So the final new stuff looks something like:
>
>#ifdef CONFIG_NETFILTER
>struct nf_hook_desc {
>	int (*okfn)(struct sk_buff *);
>	int hook;
>	int thresh;
>	u8 pf; /* AF_MAX is 32 */
>	u8 is_output;
>};
>#define NF_DESC_DECLARE(_name, _okfn, _hook, _thresh, _pf, _is_output) \
>static const struct nf_hook_desc _name = { \
>	.okfn = _okfn, \
>	.hook = _hook, \
>	.thresh = _thresh, \
>	.pf = _pf, \
>	.is_output = _is_output, \
>};
>
>extern int nf_hook_desc(struct nf_hook_desc *desc, struct sk_buff *skb,
>			struct net_device *dev);
>
>#define NF_HOOK_DESC(_desc, _skb, _dev) \
>	nf_hook_desc(_desc, _skb, _dev)
>#endif
>
>Just throwing around ideas... comments?
>  
>
Sounds like a good idea to get rid of the static arguments to
nf_hook_slow. Keeping both devices we are still down from 7 to
4 arguments with your suggestion.

Regards
Patrick

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[Rusty Russell]

On Thu, 2005-01-27 at 15:24 -0800, David S. Miller wrote:
> It is never the case that both indev and outdev are both
> set, so we can use some nf_hook_desc piece of state to
> indicate which (in or out) the passed device pointer is.

NF_IP_FORWARD... it's really *really* useful for filtering forwarded
packets.  However, is it ever the case that indev != skb->dev?  If not,
we can simply drop that arg and use skb->dev.

> Now, back to the compatability issue.  We could create a
> new macro, NF_HOOK_DESC() and keep the existing ones around
> via some nf_hook_slow() that basically does:

No, let's just fix them all.  Also, gcc 3.4 will discard unused static
variables, so I prefer the kernel start just declaring structs as
normal, and have them "used" in the !CONFIG case by an inline function
which allows gcc to realize that it can be eliminated, but suppresses
unused warnings.  This also means you get type checking etc without the
config option.

BTW, someone should go through and start ripping out #ifdef
CONFIG_PROC_FS around those structs, too...

Cheers,
Rusty.
-- 
A bad analogy is like a leaky screwdriver -- Richard Braakman

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[David S. Miller]

On Fri, 28 Jan 2005 11:29:29 +1100
Rusty Russell <rusty@rustcorp.com.au> wrote:

> No, let's just fix them all.

In tree, yes.  But leaving the NF_HOOK()/NF_HOOK_THRESH() compat
macros in there for out-of-tree modules I feel is mandatory, it's
a major API change.

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[Rusty Russell]

On Thu, 2005-01-27 at 17:10 -0800, David S. Miller wrote:
> On Fri, 28 Jan 2005 11:29:29 +1100
> Rusty Russell <rusty@rustcorp.com.au> wrote:
> 
> > No, let's just fix them all.
> 
> In tree, yes.  But leaving the NF_HOOK()/NF_HOOK_THRESH() compat
> macros in there for out-of-tree modules I feel is mandatory, it's
> a major API change.

I'm not so sure.  The hook functions which are registered, sure (ie.
keep the calling convention the same).  But do any external modules use
NF_HOOK()?  That implies they're writing their own network stack for
some protocol, which I would expect to be uncommon.

Rusty.
-- 
A bad analogy is like a leaky screwdriver -- Richard Braakman

[Bridge] Re: [PATCH/RFC] Reduce call chain length in netfilter

[Patrick McHardy]

Rusty Russell wrote:

>On Thu, 2005-01-27 at 17:10 -0800, David S. Miller wrote:
>
>>In tree, yes.  But leaving the NF_HOOK()/NF_HOOK_THRESH() compat
>>macros in there for out-of-tree modules I feel is mandatory, it's
>>a major API change.
>>
>
>I'm not so sure.  The hook functions which are registered, sure (ie.
>keep the calling convention the same).  But do any external modules use
>NF_HOOK()?  That implies they're writing their own network stack for
>some protocol, which I would expect to be uncommon.
>
Freeswan comes to mind. But I guess one more #ifdef can't hurt :)

Regards
Patrick