Deadlock in n_hdlc_buf_put

Deadlock in n_hdlc_buf_put

[Dmitry Vyukov]

Hello,

The following program causes a potential deadlock warning:

// autogenerated by syzkaller (http://github.com/google/syzkaller)
#include <syscall.h>
#include <string.h>
#include <stdint.h>

int main()
{
        long r0 = syscall(SYS_mmap, 0x20001000ul, 0x1000ul, 0x3ul,
0x32ul, 0xfffffffffffffffful, 0x0ul);
        long r1 = syscall(SYS_mmap, 0x20000000ul, 0x1000ul, 0x3ul,
0x32ul, 0xfffffffffffffffful, 0x0ul);
        memcpy((void*)0x20000ff8, "\x2f\x64\x65\x76\x2f\x70\x74\x6d\x78", 9);
        long r3 = syscall(SYS_open, 0x20000ff8ul, 0x2001ul, 0x0ul, 0, 0, 0);
        *(uint32_t*)0x20000ffc = 0xd;
        long r5 = syscall(SYS_ioctl, r3, 0x5423ul, 0x20000ffcul, 0, 0, 0);
        long r6 = syscall(SYS_mmap, 0x20003000ul, 0x1000ul, 0x3ul,
0x32ul, 0xfffffffffffffffful, 0x0ul);
        long r7 = syscall(SYS_ioctl, r3, 0x540aul, 0x0ul, 0, 0, 0);
        long r8 = syscall(SYS_mmap, 0x20002000ul, 0x1000ul, 0x3ul,
0x32ul, 0xfffffffffffffffful, 0x0ul);
        long r10 = syscall(SYS_write, r3, 0x200027c2ul, 0x1001ul, 0, 0, 0);
        long r11 = syscall(SYS_ioctl, r3, 0x540bul, 0x1ul, 0, 0, 0);
        return 0;
}

Strace output:

mmap(0x20001000, 4096, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x20001000
mmap(0x20000000, 4096, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x20000000
open("/dev/ptmx", O_WRONLY|O_ASYNC)     = 3
ioctl(3, TIOCSETD, [13])                = 0
mmap(0x20003000, 4096, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x20003000
ioctl(3, TCXONC, TCOOFF)                = 0
mmap(0x20002000, 4096, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x20002000
write(3, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"...,
4097) = 4097
ioctl(3, TCFLSH, 0x1)                   = 0
exit_group(0)                           = ?
+++ exited with 0 +++


[  341.376188] =============================================
[  341.376607] [ INFO: possible recursive locking detected ]
[  341.376607] 4.4.0-rc1+ #117 Not tainted
[  341.376607] ---------------------------------------------
[  341.376607] syzkaller_execu/14066 is trying to acquire lock:
[  341.376607]  (&(&list->spinlock)->rlock){......}, at:
[<ffffffff82a9f548>] n_hdlc_buf_put+0x28/0x170
[  341.376607]
[  341.376607] but task is already holding lock:
[  341.376607]  (&(&list->spinlock)->rlock){......}, at:
[<ffffffff82aa1368>] n_hdlc_tty_ioctl+0x2b8/0x3f0
[  341.376607]
[  341.376607] other info that might help us debug this:
[  341.376607]  Possible unsafe locking scenario:
[  341.376607]
[  341.376607]        CPU0
[  341.376607]        ----
[  341.376607]   lock(&(&list->spinlock)->rlock);
[  341.376607]   lock(&(&list->spinlock)->rlock);
[  341.376607]
[  341.376607]  *** DEADLOCK ***
[  341.376607]
[  341.376607]  May be due to missing lock nesting notation
[  341.376607]
[  341.376607] 2 locks held by syzkaller_execu/14066:
[  341.376607]  #0:  (&tty->ldisc_sem){++++++}, at:
[<ffffffff82a913cb>] tty_ldisc_ref_wait+0x2b/0xc0
[  341.376607]  #1:  (&(&list->spinlock)->rlock){......}, at:
[<ffffffff82aa1368>] n_hdlc_tty_ioctl+0x2b8/0x3f0
[  341.376607]
[  341.376607] stack backtrace:
[  341.376607] CPU: 0 PID: 14066 Comm: syzkaller_execu Not tainted
4.4.0-rc1+ #117
[  341.376607] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996),
BIOS Bochs 01/01/2011
[  341.376607]  00000000ffffffff ffff880061cb7900 ffffffff827450f6
ffffffff8751f010
[  341.376607]  0000000000000000 ffffffff8751f010 ffff880061cb7a88
ffffffff8134b0be
[  341.376607]  000004c900000002 ffffffff86e45bc0 ffff880061eb9e88
ffff880000007f09
[  341.376607] Call Trace:
[  341.376607]  [<ffffffff827450f6>] dump_stack+0x68/0x92
[  341.376607]  [<ffffffff8134b0be>] __lock_acquire+0x1d6e/0x40e0
[  341.376607]  [<ffffffff81349350>] ? debug_check_no_locks_freed+0x310/0x310
[  341.376607]  [<ffffffff81349350>] ? debug_check_no_locks_freed+0x310/0x310
[  341.376607]  [<ffffffff8134055d>] ? check_chain_key+0x2ad/0x4b0
[  341.376607]  [<ffffffff813475db>] ? mark_lock+0x12b/0x1030
[  341.376607]  [<ffffffff8134f81d>] lock_acquire+0x16d/0x2f0
[  341.376607]  [<ffffffff82a9f548>] ? n_hdlc_buf_put+0x28/0x170
[  341.376607]  [<ffffffff854159c9>] _raw_spin_lock_irqsave+0x49/0x60
[  341.376607]  [<ffffffff82a9f548>] ? n_hdlc_buf_put+0x28/0x170
[  341.376607]  [<ffffffff82a9f548>] n_hdlc_buf_put+0x28/0x170
[  341.376607]  [<ffffffff82aa13b7>] n_hdlc_tty_ioctl+0x307/0x3f0
[  341.376607]  [<ffffffff82a79e74>] tty_ioctl+0xcd4/0x2140
[  341.376607]  [<ffffffff82aa10b0>] ? n_hdlc_buf_list_init+0x40/0x40
[  341.376607]  [<ffffffff82a791a0>] ? no_tty+0xa0/0xa0
[  341.376607]  [<ffffffff81349fb0>] ? __lock_acquire+0xc60/0x40e0
[  341.376607]  [<ffffffff81349350>] ? debug_check_no_locks_freed+0x310/0x310
[  341.376607]  [<ffffffff8166fdd0>] ? vfs_iter_write+0x360/0x360
[  341.376607]  [<ffffffff81350323>] ? lock_release+0x7d3/0xc30
[  341.376607]  [<ffffffff8134055d>] ? check_chain_key+0x2ad/0x4b0
[  341.376607]  [<ffffffff82a791a0>] ? no_tty+0xa0/0xa0
[  341.376607]  [<ffffffff816aea91>] do_vfs_ioctl+0x681/0xe40
[  341.376607]  [<ffffffff8258702a>] ? selinux_file_ioctl+0x35a/0x550
[  341.376607]  [<ffffffff816ae410>] ? ioctl_preallocate+0x1d0/0x1d0
[  341.376607]  [<ffffffff816cd60b>] ? __fget+0x14b/0x3a0
[  341.376607]  [<ffffffff8256f129>] ? security_file_ioctl+0x89/0xb0
[  341.376607]  [<ffffffff816af2df>] SyS_ioctl+0x8f/0xc0
[  341.376607]  [<ffffffff85415cf6>] entry_SYSCALL_64_fastpath+0x16/0x7a


On commit 6ffeba9607343f15303a399bc402a538800d89d9 (Nov 24).

Re: Deadlock in n_hdlc_buf_put

[Jiri Slaby]

On 11/26/2015, 01:37 PM, Dmitry Vyukov wrote:
> [  341.376188] =============================================
> [  341.376607] [ INFO: possible recursive locking detected ]
> [  341.376607] 4.4.0-rc1+ #117 Not tainted
> [  341.376607] ---------------------------------------------
> [  341.376607] syzkaller_execu/14066 is trying to acquire lock:
> [  341.376607]  (&(&list->spinlock)->rlock){......}, at:
> [<ffffffff82a9f548>] n_hdlc_buf_put+0x28/0x170
> [  341.376607]
> [  341.376607] but task is already holding lock:
> [  341.376607]  (&(&list->spinlock)->rlock){......}, at:
> [<ffffffff82aa1368>] n_hdlc_tty_ioctl+0x2b8/0x3f0
> [  341.376607]
> [  341.376607] other info that might help us debug this:
> [  341.376607]  Possible unsafe locking scenario:
> [  341.376607]
> [  341.376607]        CPU0
> [  341.376607]        ----
> [  341.376607]   lock(&(&list->spinlock)->rlock);
> [  341.376607]   lock(&(&list->spinlock)->rlock);

Hi,

this is a lockdep false positive. The first one is tx_buf_list.spinlock,
the latter tx_free_buf_list.spinlock, both in flush_tx_queue. So we need
a lockdep annotation here.

thanks,
-- 
js
suse labs

[PATCH] TTY: n_hdlc, fix lockdep false positive

[Jiri Slaby]

The class of 4 n_hdls buf locks is the same because a single function
n_hdlc_buf_list_init is used to init all the locks. But since
flush_tx_queue takes n_hdlc->tx_buf_list.spinlock and then calls
n_hdlc_buf_put which takes n_hdlc->tx_free_buf_list.spinlock, lockdep
emits a warning:
=============================================
[ INFO: possible recursive locking detected ]
4.3.0-25.g91e30a7-default #1 Not tainted
---------------------------------------------
a.out/1248 is trying to acquire lock:
 (&(&list->spinlock)->rlock){......}, at: [<ffffffffa01fd020>] n_hdlc_buf_put+0x20/0x60 [n_hdlc]

but task is already holding lock:
 (&(&list->spinlock)->rlock){......}, at: [<ffffffffa01fdc07>] n_hdlc_tty_ioctl+0x127/0x1d0 [n_hdlc]

other info that might help us debug this:
 Possible unsafe locking scenario:

       CPU0
       ----
  lock(&(&list->spinlock)->rlock);
  lock(&(&list->spinlock)->rlock);

 *** DEADLOCK ***

 May be due to missing lock nesting notation

2 locks held by a.out/1248:
 #0:  (&tty->ldisc_sem){++++++}, at: [<ffffffff814c9eb0>] tty_ldisc_ref_wait+0x20/0x50
 #1:  (&(&list->spinlock)->rlock){......}, at: [<ffffffffa01fdc07>] n_hdlc_tty_ioctl+0x127/0x1d0 [n_hdlc]
...
Call Trace:
...
 [<ffffffff81738fd0>] _raw_spin_lock_irqsave+0x50/0x70
 [<ffffffffa01fd020>] n_hdlc_buf_put+0x20/0x60 [n_hdlc]
 [<ffffffffa01fdc24>] n_hdlc_tty_ioctl+0x144/0x1d0 [n_hdlc]
 [<ffffffff814c25c1>] tty_ioctl+0x3f1/0xe40
...

Fix it by initializing the spin_locks separately. This removes also
reduntand memset of a freshly kzallocated space.

Signed-off-by: Jiri Slaby <jslaby@suse.cz>
Reported-by: Dmitry Vyukov <dvyukov@google.com>
---
 drivers/tty/n_hdlc.c | 19 ++++---------------
 1 file changed, 4 insertions(+), 15 deletions(-)

diff --git a/drivers/tty/n_hdlc.c b/drivers/tty/n_hdlc.c
index bbc4ce66c2c1..bcaba17688f6 100644
--- a/drivers/tty/n_hdlc.c
+++ b/drivers/tty/n_hdlc.c
@@ -159,7 +159,6 @@ struct n_hdlc {
 /*
  * HDLC buffer list manipulation functions
  */
-static void n_hdlc_buf_list_init(struct n_hdlc_buf_list *list);
 static void n_hdlc_buf_put(struct n_hdlc_buf_list *list,
 			   struct n_hdlc_buf *buf);
 static struct n_hdlc_buf *n_hdlc_buf_get(struct n_hdlc_buf_list *list);
@@ -853,10 +852,10 @@ static struct n_hdlc *n_hdlc_alloc(void)
 	if (!n_hdlc)
 		return NULL;
 
-	n_hdlc_buf_list_init(&n_hdlc->rx_free_buf_list);
-	n_hdlc_buf_list_init(&n_hdlc->tx_free_buf_list);
-	n_hdlc_buf_list_init(&n_hdlc->rx_buf_list);
-	n_hdlc_buf_list_init(&n_hdlc->tx_buf_list);
+	spin_lock_init(&n_hdlc->rx_free_buf_list.spinlock);
+	spin_lock_init(&n_hdlc->tx_free_buf_list.spinlock);
+	spin_lock_init(&n_hdlc->rx_buf_list.spinlock);
+	spin_lock_init(&n_hdlc->tx_buf_list.spinlock);
 	
 	/* allocate free rx buffer list */
 	for(i=0;i<DEFAULT_RX_BUF_COUNT;i++) {
@@ -885,16 +884,6 @@ static struct n_hdlc *n_hdlc_alloc(void)
 }	/* end of n_hdlc_alloc() */
 
 /**
- * n_hdlc_buf_list_init - initialize specified HDLC buffer list
- * @list - pointer to buffer list
- */
-static void n_hdlc_buf_list_init(struct n_hdlc_buf_list *list)
-{
-	memset(list, 0, sizeof(*list));
-	spin_lock_init(&list->spinlock);
-}	/* end of n_hdlc_buf_list_init() */
-
-/**
  * n_hdlc_buf_put - add specified HDLC buffer to tail of specified list
  * @list - pointer to buffer list
  * @buf	- pointer to buffer
-- 
2.6.3