[PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[Harald Welte]

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

Hi!

When we have ip_queue being used from LOCAL_IN, then we end up with a
situation where the verdicts coming back from userspace traverse the TCP
input path from syscall context.  While this seems to work most of the
time, there's an ungly deadlock:

syscall context is interrupted by the timer interrupt.  When the timer
interrupt leaves, the timer softirq get's scheduled and calls
tcp_delack_timer() and alike.  They themselves do bh_lock_sock(sk),
which is already held from somewhere else[1] -> boom.

The patch below adds an additional queue for ip_queue verdicts.  They
come up from userspace, are appended to a queue which is then processed
by a tasklet.  The tasklet itself runs in softirq context, so when timer
hardirq leaves, no tcp_delack_timer() will be executed until
nf_reinject() has finished.

Dave: Please don't apply yet, I want to receive feedback from the
netfilter developers first.  I'm just Cc'ing netdev in case somebody
wants an intermediate fix to fix the problem.

[1] i didn't actually find from where that lock was held.  In any case,
it didn't seem nice to traverse the IP input codepath from syscall
context.  There might be a number of places which just assume to run in
softirq.

Comments welcome!

-- 
- Harald Welte <laforge@netfilter.org>                 http://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: 2.6.12-rc5-ip_queue-local-reinject-smp-deadlock-fix.patch --]
[-- Type: text/plain, Size: 10651 bytes --]

Fix ip_queue when used from LOCAL_IN hook.  Without this patch, packets are
nf_reinject()ed from syscall context.   Syscall context will be interupted
from timer interrupt, and timer interrupt will call TCP timer code such as
tcp_delack_timer(), which in turn tries to bh_lock_sock() and deadlocks at that
point.

Thanks to Holger Eitzenberger <heitzenberger@astaro.com> and 
Stephan Scholz <sscholz@astaro.com> for providing me with backtraces.

Signed-off-by: Harald Welte <laforge@netfilter.org>


Index: linux-2.6.12-rc5/net/ipv4/netfilter/ip_queue.c
===================================================================
--- linux-2.6.12-rc5.orig/net/ipv4/netfilter/ip_queue.c	2005-05-26 15:50:01.000000000 +0200
+++ linux-2.6.12-rc5/net/ipv4/netfilter/ip_queue.c	2005-05-26 16:09:08.000000000 +0200
@@ -3,6 +3,8 @@
  * communicating with userspace via netlink.
  *
  * (C) 2000-2002 James Morris <jmorris@intercode.com.au>
+ * (C) 2003-2004 Netfilter Core Team <coreteam@netfilter.org>
+ * (C) 2005 Harald Welte <laforge@netfilter.org>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as
@@ -17,6 +19,9 @@
  * 2005-01-10: Added /proc counter for dropped packets; fixed so
  *             packets aren't delivered to user space if they're going 
  *             to be dropped. 
+ * 2005-05-25: Issue verdict from tasklet context, not from syscall (netlink
+ *             sendmsg) to avoid deadlocks in TCP input path with timer
+ *             softirq.
  *
  */
 #include <linux/module.h>
@@ -40,6 +45,7 @@
 #define IPQ_PROC_FS_NAME "ip_queue"
 #define NET_IPQ_QMAX 2088
 #define NET_IPQ_QMAX_NAME "ip_queue_maxlen"
+#define	IPQ_VERDICT_BATCH 10
 
 struct ipq_rt_info {
 	__u8 tos;
@@ -52,6 +58,16 @@
 	struct nf_info *info;
 	struct sk_buff *skb;
 	struct ipq_rt_info rt_info;
+
+	/* only used in verdict_queue */
+	int verdict;
+};
+
+struct ipq_queue {
+	struct list_head list;
+	unsigned int total;
+	unsigned int dropped;
+	unsigned int user_dropped;
 };
 
 typedef int (*ipq_cmpfn)(struct ipq_queue_entry *, unsigned long);
@@ -61,14 +77,16 @@
 static DEFINE_RWLOCK(queue_lock);
 static int peer_pid;
 static unsigned int copy_range;
-static unsigned int queue_total;
-static unsigned int queue_dropped = 0;
-static unsigned int queue_user_dropped = 0;
 static struct sock *ipqnl;
-static LIST_HEAD(queue_list);
 static DECLARE_MUTEX(ipqnl_sem);
 
-static void
+static struct ipq_queue pkt_queue;	/* queue of packets to userspace */
+static struct ipq_queue verdict_queue;	/* queue of verdicst from userspace */
+
+static void ipq_verdict_task(unsigned long arg);
+static DECLARE_TASKLET(ipq_verdict_tasklet, ipq_verdict_task, 0);
+
+static inline void
 ipq_issue_verdict(struct ipq_queue_entry *entry, int verdict)
 {
 	nf_reinject(entry->skb, entry->info, verdict);
@@ -76,10 +94,10 @@
 }
 
 static inline void
-__ipq_enqueue_entry(struct ipq_queue_entry *entry)
+__ipq_enqueue_entry(struct ipq_queue *queue, struct ipq_queue_entry *entry)
 {
-       list_add(&entry->list, &queue_list);
-       queue_total++;
+       list_add(&entry->list, &queue->list);
+       queue->total++;
 }
 
 /*
@@ -87,11 +105,11 @@
  * entry if cmpfn is NULL.
  */
 static inline struct ipq_queue_entry *
-__ipq_find_entry(ipq_cmpfn cmpfn, unsigned long data)
+__ipq_find_entry(struct ipq_queue *queue, ipq_cmpfn cmpfn, unsigned long data)
 {
 	struct list_head *p;
 
-	list_for_each_prev(p, &queue_list) {
+	list_for_each_prev(p, &queue->list) {
 		struct ipq_queue_entry *entry = (struct ipq_queue_entry *)p;
 		
 		if (!cmpfn || cmpfn(entry, data))
@@ -101,33 +119,49 @@
 }
 
 static inline void
-__ipq_dequeue_entry(struct ipq_queue_entry *entry)
+__ipq_dequeue_entry(struct ipq_queue *queue, struct ipq_queue_entry *entry)
 {
 	list_del(&entry->list);
-	queue_total--;
+	queue->total--;
 }
 
 static inline struct ipq_queue_entry *
-__ipq_find_dequeue_entry(ipq_cmpfn cmpfn, unsigned long data)
+__ipq_find_dequeue_entry(struct ipq_queue *queue, ipq_cmpfn cmpfn, 
+			 unsigned long data)
 {
 	struct ipq_queue_entry *entry;
 
-	entry = __ipq_find_entry(cmpfn, data);
+	entry = __ipq_find_entry(queue, cmpfn, data);
 	if (entry == NULL)
 		return NULL;
 
-	__ipq_dequeue_entry(entry);
+	__ipq_dequeue_entry(queue, entry);
 	return entry;
 }
 
+static void
+ipq_enqueue_verdict(struct ipq_queue_entry *entry, int verdict)
+{
+	entry->verdict = verdict;
+
+	write_lock_bh(&queue_lock);
+	if (verdict_queue.total >= queue_maxlen) {
+		verdict_queue.dropped++;
+		write_unlock_bh(&queue_lock);
+	}
+	__ipq_enqueue_entry(&verdict_queue, entry);
+	write_unlock_bh(&queue_lock);
+
+	tasklet_schedule(&ipq_verdict_tasklet);
+}
 
 static inline void
 __ipq_flush(int verdict)
 {
 	struct ipq_queue_entry *entry;
 	
-	while ((entry = __ipq_find_dequeue_entry(NULL, 0)))
-		ipq_issue_verdict(entry, verdict);
+	while ((entry = __ipq_find_dequeue_entry(&pkt_queue, NULL, 0)))
+		ipq_enqueue_verdict(entry, verdict);
 }
 
 static inline int
@@ -166,12 +200,13 @@
 }
 
 static struct ipq_queue_entry *
-ipq_find_dequeue_entry(ipq_cmpfn cmpfn, unsigned long data)
+ipq_find_dequeue_entry(struct ipq_queue *queue, ipq_cmpfn cmpfn, 
+		       unsigned long data)
 {
 	struct ipq_queue_entry *entry;
 	
 	write_lock_bh(&queue_lock);
-	entry = __ipq_find_dequeue_entry(cmpfn, data);
+	entry = __ipq_find_dequeue_entry(queue, cmpfn, data);
 	write_unlock_bh(&queue_lock);
 	return entry;
 }
@@ -182,6 +217,7 @@
 	write_lock_bh(&queue_lock);
 	__ipq_flush(verdict);
 	write_unlock_bh(&queue_lock);
+
 }
 
 static struct sk_buff *
@@ -306,24 +342,24 @@
 	if (!peer_pid)
 		goto err_out_free_nskb; 
 
-	if (queue_total >= queue_maxlen) {
-                queue_dropped++;
+	if (pkt_queue.total >= queue_maxlen) {
+                pkt_queue.dropped++;
 		status = -ENOSPC;
 		if (net_ratelimit())
 		          printk (KERN_WARNING "ip_queue: full at %d entries, "
-				  "dropping packets(s). Dropped: %d\n", queue_total,
-				  queue_dropped);
+				  "dropping packets(s). Dropped: %d\n", 
+				  pkt_queue.total, pkt_queue.dropped);
 		goto err_out_free_nskb;
 	}
 
  	/* netlink_unicast will either free the nskb or attach it to a socket */ 
 	status = netlink_unicast(ipqnl, nskb, peer_pid, MSG_DONTWAIT);
 	if (status < 0) {
-	        queue_user_dropped++;
+	        pkt_queue.user_dropped++;
 		goto err_out_unlock;
 	}
 
-	__ipq_enqueue_entry(entry);
+	__ipq_enqueue_entry(&pkt_queue, entry);
 
 	write_unlock_bh(&queue_lock);
 	return status;
@@ -406,7 +442,7 @@
 	if (vmsg->value > NF_MAX_VERDICT)
 		return -EINVAL;
 
-	entry = ipq_find_dequeue_entry(id_cmp, vmsg->id);
+	entry = ipq_find_dequeue_entry(&pkt_queue, id_cmp, vmsg->id);
 	if (entry == NULL)
 		return -ENOENT;
 	else {
@@ -416,7 +452,11 @@
 			if (ipq_mangle_ipv4(vmsg, entry) < 0)
 				verdict = NF_DROP;
 		
-		ipq_issue_verdict(entry, verdict);
+		/* instead of issuing the verdict herer from syscall
+		 * context, we enqueue the verdict to the verdict_queue,
+		 * which is later processed by softirq context */
+		ipq_enqueue_verdict(entry, verdict);
+
 		return 0;
 	}
 }
@@ -479,8 +519,9 @@
 {
 	struct ipq_queue_entry *entry;
 	
-	while ((entry = ipq_find_dequeue_entry(dev_cmp, ifindex)) != NULL)
-		ipq_issue_verdict(entry, NF_DROP);
+	while ((entry = ipq_find_dequeue_entry(&pkt_queue,
+						dev_cmp, ifindex)) != NULL)
+		ipq_enqueue_verdict(entry, NF_DROP);
 }
 
 #define RCV_SKB_FAIL(err) do { netlink_ack(skb, nlh, (err)); return; } while (0)
@@ -630,6 +671,29 @@
 	{ .ctl_name = 0 }
 };
 
+/* This tasklet feeds queued verdicts through the network stack.  Since it runs
+ * in tasklet softirq context, this makes the TCP local input path happy -HW */
+static void
+ipq_verdict_task(unsigned long arg)
+{
+	struct ipq_queue_entry *entry;
+	unsigned int num = 0;
+
+	/* we want to stall other processing for too long. */
+	for (num = 0; num < IPQ_VERDICT_BATCH; num++) {
+		entry = ipq_find_dequeue_entry(&verdict_queue, NULL, 0);
+		if (!entry) {
+			break;
+		}
+		ipq_issue_verdict(entry, entry->verdict);
+	}
+
+	if (verdict_queue.total) {
+		/* more work to be done, schedule us again */
+		tasklet_schedule(&ipq_verdict_tasklet);
+	}
+}
+
 #ifdef CONFIG_PROC_FS
 static int
 ipq_get_info(char *buffer, char **start, off_t offset, int length)
@@ -639,20 +703,24 @@
 	read_lock_bh(&queue_lock);
 	
 	len = sprintf(buffer,
-	              "Peer PID          : %d\n"
-	              "Copy mode         : %hu\n"
-	              "Copy range        : %u\n"
-	              "Queue length      : %u\n"
-	              "Queue max. length : %u\n"
-		      "Queue dropped     : %u\n"
-		      "Netlink dropped   : %u\n",
+	              "Peer PID              : %d\n"
+	              "Copy mode             : %hu\n"
+	              "Copy range            : %u\n"
+	              "Queue length          : %u\n"
+	              "Queue max. length     : %u\n"
+		      "Queue dropped         : %u\n"
+		      "Netlink dropped       : %u\n"
+		      "Verdict queue len     : %u\n"
+		      "Verdict queue dropped : %u\n",
 	              peer_pid,
 	              copy_mode,
 	              copy_range,
-	              queue_total,
+	              pkt_queue.total,
 	              queue_maxlen,
-		      queue_dropped,
-		      queue_user_dropped);
+		      pkt_queue.dropped,
+		      pkt_queue.user_dropped,
+		      verdict_queue.total,
+		      verdict_queue.dropped);
 
 	read_unlock_bh(&queue_lock);
 	
@@ -675,6 +743,16 @@
 	if (!init)
 		goto cleanup;
 
+	INIT_LIST_HEAD(&pkt_queue.list);
+	pkt_queue.total = 0;
+	pkt_queue.dropped = 0;
+	pkt_queue.user_dropped = 0;
+
+	INIT_LIST_HEAD(&verdict_queue.list);
+	verdict_queue.total = 0;
+	verdict_queue.dropped = 0;
+	verdict_queue.user_dropped = 0;
+
 	netlink_register_notifier(&ipq_nl_notifier);
 	ipqnl = netlink_kernel_create(NETLINK_FIREWALL, ipq_rcv_sk);
 	if (ipqnl == NULL) {
@@ -704,6 +782,14 @@
 	nf_unregister_queue_handler(PF_INET);
 	synchronize_net();
 	ipq_flush(NF_DROP);
+
+	while (verdict_queue.total != 0) {
+		printk(KERN_INFO "ip_queue: verdict queue not empty while "
+			"module unload, scheduling\n");
+		tasklet_schedule(&ipq_verdict_tasklet);
+		schedule();
+	}
+	tasklet_disable(&ipq_verdict_tasklet);
 	
 cleanup_sysctl:
 	unregister_sysctl_table(ipq_sysctl_header);

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

Re: [PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[David S. Miller]

From: Harald Welte <laforge@netfilter.org>
Date: Thu, 26 May 2005 16:24:21 +0200

> Dave: Please don't apply yet, I want to receive feedback from the
> netfilter developers first.  I'm just Cc'ing netdev in case somebody
> wants an intermediate fix to fix the problem.

OK.

Re: [PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[Harald Welte]

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

On Thu, May 26, 2005 at 01:52:29PM -0700, David S. Miller wrote:
 
> > Dave: Please don't apply yet, I want to receive feedback from the
> > netfilter developers first.  I'm just Cc'ing netdev in case somebody
> > wants an intermediate fix to fix the problem.
> 
> OK.

Do you have any feedback on why or how bh_lock_sock() might be called in
the problem I've described?  I think it has to be a different skb for
the same socket.

Is my general line of thought correct that we shouldn't traverse the
local input path from sysirq context ?

Thanks.

-- 
- Harald Welte <laforge@netfilter.org>                 http://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 #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[David S. Miller]

From: Harald Welte <laforge@netfilter.org>
Subject: Re: [PATCH 2.6] fix deadlock with ip_queue and tcp local input path
Date: Thu, 26 May 2005 22:58:31 +0200

> On Thu, May 26, 2005 at 01:52:29PM -0700, David S. Miller wrote:
>  
> > > Dave: Please don't apply yet, I want to receive feedback from the
> > > netfilter developers first.  I'm just Cc'ing netdev in case somebody
> > > wants an intermediate fix to fix the problem.
> > 
> > OK.
> 
> Do you have any feedback on why or how bh_lock_sock() might be called in
> the problem I've described?  I think it has to be a different skb for
> the same socket.

When we hit a listening socket, and hung off of that listening
socket we find a child socket, we bh_lock_sock() the child socket
then process the SKB against it instead of the listening socket.

Is this the kind of scenerio you are concerned about?

Re: [PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[Herbert Xu]

Harald Welte <laforge@netfilter.org> wrote:
> 
> The patch below adds an additional queue for ip_queue verdicts.  They
> come up from userspace, are appended to a queue which is then processed
> by a tasklet.  The tasklet itself runs in softirq context, so when timer
> hardirq leaves, no tcp_delack_timer() will be executed until
> nf_reinject() has finished.

This seems to be overly complicated if all you want is to do this in
softirq context.  What's wrong with simply alling local_bh_disable?
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[Harald Welte]

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

On Fri, May 27, 2005 at 07:38:57AM +1000, Herbert Xu wrote:
> Harald Welte <laforge@netfilter.org> wrote:
> > 
> > The patch below adds an additional queue for ip_queue verdicts.  They
> > come up from userspace, are appended to a queue which is then processed
> > by a tasklet.  The tasklet itself runs in softirq context, so when timer
> > hardirq leaves, no tcp_delack_timer() will be executed until
> > nf_reinject() has finished.
> 
> This seems to be overly complicated if all you want is to do this in
> softirq context.  What's wrong with simply alling local_bh_disable?

Patrick just pointed this out, too.  I wasn't sure whether
local_bh_disable() would make the context really look like softirq in
every way.  If yes, it would certainly solve the problem, because
in_interrupt() at hardirq-exit would be true and therefore the timer
softirq not scheduled immediately.

I'll have Astaro test this variant.

-- 
- Harald Welte <laforge@netfilter.org>                 http://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 #2: Type: application/pgp-signature, Size: 189 bytes --]

[PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[Harald Welte]

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

On Thu, May 26, 2005 at 04:24:21PM +0200, Harald Welte wrote:
 
> When we have ip_queue being used from LOCAL_IN, then we end up with a
> situation where the verdicts coming back from userspace traverse the TCP
> input path from syscall context.  While this seems to work most of the
> time, there's an ungly deadlock:
> 
> syscall context is interrupted by the timer interrupt.  When the timer
> interrupt leaves, the timer softirq get's scheduled and calls
> tcp_delack_timer() and alike.  They themselves do bh_lock_sock(sk),
> which is already held from somewhere else[1] -> boom.

I've now tested the suggested solution by Patrick McHardy and Herbert Xu to
simply use local_bh_{en,dis}able().

Please apply the following patch to mainline.

btw: How do we get this into 2.6.11.x ?

Signed-off-by: Harald Welte <laforge@netfilter.org>

-- 
- Harald Welte <laforge@netfilter.org>                 http://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: queue-local-reinject-smp-deadlock-fix-localbhdisable.patch --]
[-- Type: text/plain, Size: 1384 bytes --]

Index: linux-2.6.10/net/ipv4/netfilter/ip_queue.c
===================================================================
--- linux-2.6.10.orig/net/ipv4/netfilter/ip_queue.c	2005-05-27 09:44:32.000000000 +0200
+++ linux-2.6.10/net/ipv4/netfilter/ip_queue.c	2005-05-27 09:47:13.000000000 +0200
@@ -3,6 +3,7 @@
  * communicating with userspace via netlink.
  *
  * (C) 2000-2002 James Morris <jmorris@intercode.com.au>
+ * (C) 2003-2005 Netfilter Core Team <coreteam@netfilter.org>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as
@@ -14,6 +15,7 @@
  *             Zander).
  * 2000-08-01: Added Nick Williams' MAC support.
  * 2002-06-25: Code cleanup.
+ * 2005-05-26: local_bh_{disable,enable} around nf_reinject (Harald Welte)
  *
  */
 #include <linux/module.h>
@@ -66,7 +68,15 @@
 static void
 ipq_issue_verdict(struct ipq_queue_entry *entry, int verdict)
 {
+	/* TCP input path (and probably other bits) assume to be called
+	 * from softirq context, not from syscall, like ipq_issue_verdict is
+	 * called.  TCP input path deadlocks with locks taken from timer
+	 * softirq, e.g.  We therefore emulate this by local_bh_disable() */
+
+	local_bh_disable();
 	nf_reinject(entry->skb, entry->info, verdict);
+	local_bh_enable();
+
 	kfree(entry);
 }
 

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

Re: [PATCH 2.6] fix deadlock with ip_queue and tcp local input path

[David S. Miller]

From: Harald Welte <laforge@netfilter.org>
Date: Mon, 30 May 2005 20:06:54 +0200

> I've now tested the suggested solution by Patrick McHardy and Herbert Xu to
> simply use local_bh_{en,dis}able().
> 
> Please apply the following patch to mainline.

Will do.

> btw: How do we get this into 2.6.11.x ?

You submit your patch to stable@kernel.org.

But I will take care of this for you Harald, don't
worry about it.