Deadlock in Bluetooth code in 2.6.36

Deadlock in Bluetooth code in 2.6.36

[Gustavo F. Padovan]

Hi,

I would like to discuss here a problem we are having in the Bluetooth Layer.

There we have the Enhanced Retransmission Mode(ERTM) which is  a reliable mode
of operation of the Bluetooth L2CAP layer. Think on it like a simplified
version of TCP.

The problem we were facing was a deadlock. ERTM uses a backlog queue to
queue incoming packets while the user held the lock. The problem is that
at some moment the user doesn't have memory anymore to alloc new skbs and
sleeps to wait for memory with the lock held, that stalls the ERTM connection
because we can't read the acknowledgements packets in the backlog queue to
free memory and then make the allocation of outcoming skb successful.

Looks like the solution to this issue is release the lock before go to sleep
waiting for memory and then lock the sock lock again when we wake up and have
memory.  That's the solution TCP does through sk_stream_alloc_skb() and
sk_stream_wait_memory(). The sock lock is released and locked again inside
sk_wait_event() macro.
For bluetooth we do that in different way, we alloc memory through
sock_alloc_send_skb() which differently from sk_stream_alloc_skb() sleeps
with the lock held when waiting for memory.

The following patch is more like a proof of concept that sleeping
without the lock fixes the problem for L2CAP. Mat Martineau also found out
that some time ago.

My questions here is on how to fix this properly. Maybe
sock_alloc_send_skb() should not be used with SOCK_STREAM and reliable
protocols and I'm not aware of that? And should I use something like
sk_stream_alloc_skb() instead?

Any comments are welcome. With lucky we can fix that for 2.6.36 and
together with others fixes we have queued deliver a fully functional
L2CAP layer on 2.6.36.

Thanks,

---

Gustavo F. Padovan (1):
      Bluetooth: Fix deadlock in the ERTM logic

 net/bluetooth/l2cap.c |    4 ++++
  1 files changed, 4 insertions(+), 0 deletions(-)

[PATCH] Bluetooth: Fix deadlock in the ERTM logic

[Gustavo F. Padovan]

The Enhanced Retransmission Mode(ERTM) is a realiable mode of operation
of the Bluetooth L2CAP layer. Think on it like a simplified version of
TCP.
The problem we were facing here was a deadlock. ERTM uses a backlog
queue to queue incomimg packets while the user is helding the lock. The
problem is that at some moment the user doesn't have memory anymore to
do alloc new skbs and sleep with the lock to wait for memory, that
stalls the ERTM connection once we can't read the acknowledgements
packets in the backlog queue to free memory and make the allocation of
outcoming skb successful.

I'm thinking on this patch more like a proof of concept than a real fix
to the deadlock in ERTM.

Signed-off-by: Gustavo F. Padovan <padovan@profusion.mobi>
---
 net/bluetooth/l2cap.c |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

diff --git a/net/bluetooth/l2cap.c b/net/bluetooth/l2cap.c
index 44a8fb0..dd406b5 100644
--- a/net/bluetooth/l2cap.c
+++ b/net/bluetooth/l2cap.c
@@ -1633,7 +1633,9 @@ static inline int l2cap_skbuff_fromiovec(struct sock *sk, struct msghdr *msg, in
 	while (len) {
 		count = min_t(unsigned int, conn->mtu, len);
 
+		release_sock(sk);
 		*frag = bt_skb_send_alloc(sk, count, msg->msg_flags & MSG_DONTWAIT, &err);
+		lock_sock(sk);
 		if (!*frag)
 			return -EFAULT;
 		if (memcpy_fromiovec(skb_put(*frag, count), msg->msg_iov, count))
@@ -1724,8 +1726,10 @@ static struct sk_buff *l2cap_create_iframe_pdu(struct sock *sk, struct msghdr *m
 		hlen += 2;
 
 	count = min_t(unsigned int, (conn->mtu - hlen), len);
+	release_sock(sk);
 	skb = bt_skb_send_alloc(sk, count + hlen,
 			msg->msg_flags & MSG_DONTWAIT, &err);
+	lock_sock(sk);
 	if (!skb)
 		return ERR_PTR(-ENOMEM);
 
-- 
1.7.3

Re: Deadlock in Bluetooth code in 2.6.36

[David Miller]

From: "Gustavo F. Padovan" <padovan@profusion.mobi>
Date: Tue, 21 Sep 2010 18:20:12 -0300

> My questions here is on how to fix this properly. Maybe
> sock_alloc_send_skb() should not be used with SOCK_STREAM and reliable
> protocols and I'm not aware of that? And should I use something like
> sk_stream_alloc_skb() instead?
> 
> Any comments are welcome. With lucky we can fix that for 2.6.36 and
> together with others fixes we have queued deliver a fully functional
> L2CAP layer on 2.6.36.

Use sock_alloc_send_skb() as you do now, but if it fails wait for socket
space to become available just like TCP does, then loop back and try to
allocate again if the space-wait doesn't return an error.

I think you should be able to reuse sk_stream_wait_memory() for this
purpose just fine and without any problems.

Re: Deadlock in Bluetooth code in 2.6.36

[Gustavo F. Padovan]

* David Miller <davem-fT/PcQaiUtIeIZ0/mPfg9Q@public.gmane.org> [2010-09-24 21:18:24 -0700]:

> From: "Gustavo F. Padovan" <padovan-Y3ZbgMPKUGA34EUeqzHoZw@public.gmane.org>
> Date: Tue, 21 Sep 2010 18:20:12 -0300
> 
> > My questions here is on how to fix this properly. Maybe
> > sock_alloc_send_skb() should not be used with SOCK_STREAM and reliable
> > protocols and I'm not aware of that? And should I use something like
> > sk_stream_alloc_skb() instead?
> > 
> > Any comments are welcome. With lucky we can fix that for 2.6.36 and
> > together with others fixes we have queued deliver a fully functional
> > L2CAP layer on 2.6.36.
> 
> Use sock_alloc_send_skb() as you do now, but if it fails wait for socket
> space to become available just like TCP does, then loop back and try to
> allocate again if the space-wait doesn't return an error.

sock_alloc_send_skb() doesn't fail when there is no space available
it sleeps and try again later. That is the problem. So if
sock_alloc_send_skb() is called with the socket lock held potentially we
can have a starvation in the backlog queue and then the deadlock due to
be unable to read the acknowledgments packets residing in the backlog
queue.

Our current solution is release the lock before call
sock_alloc_send_skb() and acquire it again when sock_alloc_send_skb()
returns. Patch follows:

------
Bluetooth: Fix deadlock in the ERTM logic                        
                                                                                      
The Enhanced Retransmission Mode(ERTM) is a reliable mode of operation               
of the Bluetooth L2CAP layer. Think on it like a simplified version of                
TCP.                                                                                  
The problem we were facing here was a deadlock. ERTM uses a backlog                   
queue to queue incomimg packets while the user is helding the lock. At                
some moment the sk_sndbuf can be exceeded and we can't alloc new skbs                 
then the code sleep with the lock to wait for memory, that stalls the                 
ERTM connection once we can't read the acknowledgements packets in the                
backlog queue to free memory and make the allocation of outcoming skb
successful.

This patch actually affect all users of bt_skb_send_alloc(), i.e., all
L2CAP modes and SCO.

Signed-off-by: Gustavo F. Padovan <padovan-Y3ZbgMPKUGA34EUeqzHoZw@public.gmane.org>
Signed-off-by: Ulisses Furquim <ulisses-Y3ZbgMPKUGA34EUeqzHoZw@public.gmane.org>
---
 include/net/bluetooth/bluetooth.h |   11 +++++++++++
 1 files changed, 11 insertions(+), 0 deletions(-)

diff --git a/include/net/bluetooth/bluetooth.h b/include/net/bluetooth/bluetooth.h
index 27a902d..118b69b 100644
--- a/include/net/bluetooth/bluetooth.h
+++ b/include/net/bluetooth/bluetooth.h
@@ -161,10 +161,21 @@ static inline struct sk_buff *bt_skb_send_alloc(struct sock *sk, unsigned long l
 {
        struct sk_buff *skb;
 
+       release_sock(sk);
        if ((skb = sock_alloc_send_skb(sk, len + BT_SKB_RESERVE, nb, err))) {
                skb_reserve(skb, BT_SKB_RESERVE);
                bt_cb(skb)->incoming  = 0;
        }
+       lock_sock(sk);
+
+       if (*err)
+               return NULL;
+
+       *err = sock_error(sk);
+       if (*err) {
+               kfree_skb(skb);
+               return NULL;
+       }
 
        return skb;
 }
-- 
1.7.2.2

-- 
Gustavo F. Padovan
ProFUSION embedded systems - http://profusion.mobi