[CHECKER] potential deadlocks

[CHECKER] potential deadlocks

[Dawson Engler]

Hi All,

here are a small number of potential deadlocks caught from a static
deadlock detector. It flags any places with locking cycles.  E.g. it
will flag:

	lock(a)
	lock(b);
	...
	unlock(a);
	unlock(b);
	...
	lock(b);
	lock(a)
since a thread could grab "a" while another could grab "b" and then
both could spin waiting for the other's lock.

It understands that only the first read_lock and lock_kernel actually
does anything, so that it won't warn about

	lock_kernel();
	lock(a);
	lock_kernel(); /* no lock acquired */

violating a partial order.

Any feedback on the results would be great.  My understanding of linux's
sprawling locking rules is less than impressive.  Also, if there are
known deadlocks, let me know and I can make sure we're finding them.

Note that the message format is a bit confusing.  It prints out the number
of times each locking order occurred at and then gives some example paths.
For example, for the first error below:

   <&driver_lock>-><&adap_lock> occurred 1 times
   <&adap_lock>-><&driver_lock> occurred 1 times

means that driver_lock was aqcquired followed by adap_lock 1 time,
and the opposite also occured one time.  A path to the first order
is given by:
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/i2c/i2c-core.c:i2c_del_driver:292
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/i2c/i2c-core.c:i2c_del_driver:312

Thanks to Andrew for feedback on other race detector checker.

Dawson

--------------------------------------------------
BUG ERROR: 1 thread deadlock.
   <&driver_lock>-><&adap_lock> occurred 1 times
   <&adap_lock>-><&driver_lock> occurred 1 times
  &driver_lock->&adap_lock =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/i2c/i2c-core.c:i2c_del_driver:292
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/i2c/i2c-core.c:i2c_del_driver:312

  &adap_lock->&driver_lock =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/i2c/i2c-core.c:i2c_del_adapter:175
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/i2c/i2c-core.c:i2c_del_adapter:192

--------------------------------------------------
BUG ERROR: 1 thread deadlock.
   <&rtc_lock>-><&rtc_task_lock> occurred 1 times
   <&rtc_task_lock>-><&rtc_lock> occurred 1 times
  &rtc_lock->&rtc_task_lock =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/char/rtc.c:rtc_register:723
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/char/rtc.c:rtc_register:728

  &rtc_task_lock->&rtc_lock =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/char/rtc.c:rtc_unregister:749
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/char/rtc.c:rtc_unregister:755



--------------------------------------------------
BUG ERROR: 1 thread deadlock.
   <struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.readmutex (<local>:0)>-><struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.mutex (<local>:0)> occurred 1 times
   <struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.mutex (<local>:0)>-><struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.readmutex (<local>:0)> occurred 1 times
  struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.readmutex (<local>:0)->struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.mutex (<local>:0) =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_read:1620
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_read:1711

  struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.mutex (<local>:0)->struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.readmutex (<local>:0) =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_read:1610
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_read:1620

--------------------------------------------------
BUG ERROR: 1 thread deadlock.
   <&dev_table_mutex>-><struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c162.mutex (<local>:0)> occurred 1 times
   <struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c162.mutex (<local>:0)>-><&dev_table_mutex> occurred 1 times
  &dev_table_mutex->struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c162.mutex (<local>:0) =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_open:1404
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_open:1412

  struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c162.mutex (<local>:0)->&dev_table_mutex =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerswald_disconnect:2091
           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerswald_disconnect:2096 



--------------------------------------------------
BUG ERROR: 1 thread deadlock.
   <lock_kernel>-><struct namespace.sem (<local>:0)> occurred 36 times
   <struct namespace.sem (<local>:0)>-><lock_kernel> occurred 30 times
  lock_kernel->struct namespace.sem (<local>:0) =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_pivot_root:974
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_pivot_root:997
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_umount:306
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_umount:335
    depth = 3:
        /u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:870
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:870
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:871
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_mount:753
           ->end=/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_loopback:511
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_loopback:511
    depth = 3:
        /u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:870
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:870
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:871
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_mount:755
           ->end=/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_move_mount:579
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_move_mount:579
    depth = 3:
        /u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:870
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:870
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:sys_mount:871
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_mount:757
           ->end=/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_add_mount:644
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_add_mount:644

  struct namespace.sem (<local>:0)->lock_kernel =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_umount:335
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/namespace.c:do_umount:341


--------------------------------------------------
BUG: ERROR: 1 thread deadlock.
   <struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.readmutex (<local>:0)>-><struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.mutex (<local>:0)> occurred 1 times
   <struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.mutex (<local>:0)>-><struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.readmutex (<local>:0)> occurred 1 times
  struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.readmutex (<local>:0)->struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.mutex (<local>:0) =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_read:1620

        /* only one reader per device allowed */
        if (down_interruptible (&ccp->readmutex)) {
                up (&ccp->mutex);

           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_read:1711

        if (down_interruptible (&ccp->mutex)) {
                up (&ccp->readmutex);


  struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.mutex (<local>:0)->struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c582.readmutex (<local>:0) =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_read:1610

        /* get the mutex */
        if (down_interruptible (&ccp->mutex))
                return -ERESTARTSYS;

           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_read:1620

        /* only one reader per device allowed */
        if (down_interruptible (&ccp->readmutex)) {
                up (&ccp->mutex);



--------------------------------------------------
BUG: ERROR: 1 thread deadlock.
   <&dev_table_mutex>-><struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c162.mutex (<local>:0)> occurred 1 times
   <struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c162.mutex (<local>:0)>-><&dev_table_mutex> occurred 1 times
  &dev_table_mutex->struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c162.mutex (<local>:0) =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerchar_open:1404
  struct /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c162.mutex (<local>:0)->&dev_table_mutex =

        /* usb device available? */
        if (down_interruptible (&dev_table_mutex)) {
                return -ERESTARTSYS;
        }
        cp = dev_table[dtindex];
        if (cp == NULL) {
                up (&dev_table_mutex);
                return -ENODEV;
        }
        if (down_interruptible (&cp->mutex)) {

    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerswald_disconnect:2091

           ->/u2/engler/mc/oses/linux/linux-2.5.62/drivers/usb/misc/auerswald.c:auerswald_disconnect:2096

        down (&cp->mutex);
        info ("device /dev/usb/%s now disconnecting", cp->name);

        /* remove from device table */
        /* Nobody can open() this device any more */
        down (&dev_table_mutex);
        dev_table[cp->dtindex] = NULL;
        up (&dev_table_mutex);



--------------------------------------------------
BUG: ERROR: 1 thread deadlock.
   <lock_kernel>-><struct block_device.bd_sem (<local>:0)> occurred 37 times
   <struct block_device.bd_sem (<local>:0)>-><lock_kernel> occurred 36 times
  lock_kernel->struct block_device.bd_sem (<local>:0) =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/fs/block_dev.c:do_open:569
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/block_dev.c:do_open:578

        lock_kernel();
        disk = get_gendisk(bdev->bd_dev, &part);
        if (!disk) {
                unlock_kernel();
                bdput(bdev);
                return ret;
        }
        owner = disk->fops->owner;

        down(&bdev->bd_sem);

    depth = 6:
        /u2/engler/mc/oses/linux/linux-2.5.62/init/main.c:init:508
           ->/u2/engler/mc/oses/linux/linux-2.5.62/init/main.c:init:508
           ->/u2/engler/mc/oses/linux/linux-2.5.62/init/main.c:init:527
           ->/u2/engler/mc/oses/linux/linux-2.5.62/init/do_mounts.c:prepare_namespace:883
           ->/u2/engler/mc/oses/linux/linux-2.5.62/kernel/suspend.c:software_resume:1231
           ->/u2/engler/mc/oses/linux/linux-2.5.62/kernel/suspend.c:read_suspend_image:1170
           ->end=/u2/engler/mc/oses/linux/linux-2.5.62/fs/block_dev.c:blkdev_put:705
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/block_dev.c:blkdev_put:705

  struct block_device.bd_sem (<local>:0)->lock_kernel =
    depth = 1:
        /u2/engler/mc/oses/linux/linux-2.5.62/fs/block_dev.c:blkdev_put:705
           ->/u2/engler/mc/oses/linux/linux-2.5.62/fs/block_dev.c:blkdev_put:712

        down(&bdev->bd_sem);
        switch (kind) {
        case BDEV_FILE:
        case BDEV_FS:
                sync_blockdev(bd_inode->i_bdev);
                break;
        }
        lock_kernel();

Re: [CHECKER] potential deadlocks

[Andrew Morton]

Dawson Engler <engler@csl.stanford.edu> wrote:
>
> Any feedback on the results would be great.  My understanding of linux's
> sprawling locking rules is less than impressive.

We would be impressed if it wasn't :)

> Also, if there are
> known deadlocks, let me know and I can make sure we're finding them.

There are some real ones there.  The ones surrounding lock_kernel() and
semaphores are false positives.

lock_kernel() is special, in that the lock is dropped when the caller
performs a voluntary context switch.  So there are no ordering requirements
between lock_kernel and the sleeping locks down(), down_read(), down_write().

lock_kernel() inside a spinlock is not necessarily a bug, but almost always
is.  It should be warned about.

Re: [CHECKER] potential deadlocks

[Dawson Engler]

> There are some real ones there.  The ones surrounding lock_kernel() and
> semaphores are false positives.
> 
> lock_kernel() is special, in that the lock is dropped when the caller
> performs a voluntary context switch.  So there are no ordering requirements
> between lock_kernel and the sleeping locks down(), down_read(), down_write().

Ah.  I actually knew that.  Embarassing.  Thanks for pointing it out;
I'll make the change.

BTW, are there known deadlocks (harmless or otherwise)?  Debugging
the checker is a bit hard since false negatives are silent...

Dawson

Re: [CHECKER] potential deadlocks

[Andrew Morton]

Dawson Engler <engler@csl.stanford.edu> wrote:
>
> BTW, are there known deadlocks (harmless or otherwise)?  Debugging
> the checker is a bit hard since false negatives are silent...

Known deadlocks tend to get fixed.  But I am surprised that you did not
encounter more of them.

btw, the filesystem transaction operations can be treated as sleeping locks. 
So for ext3, journal_start()/journal_stop() may, for lock-ranking purposes,
be treated in the same way as taking and releasing a per-superblock
semaphore.  Other filesystems probably have similar restrictions.

Other such "hidden" sleeping locks are lock_sock() and wait_on_inode().  The
latter is rather messy because there is no clear API function which sets
I_LOCK.

And pte_chain_lock() is a custom spinlock.

Re: [CHECKER] potential deadlocks

[Dawson Engler]

> Dawson Engler <engler@csl.stanford.edu> wrote:
> >
> > BTW, are there known deadlocks (harmless or otherwise)?  Debugging
> > the checker is a bit hard since false negatives are silent...
> 
> Known deadlocks tend to get fixed.  But I am surprised that you did not
> encounter more of them.

;-)

I sent out a *very* small subset of the checker's output.  There are
hundreds of messages.  I wanted to check on validity before flooding
people.


> btw, the filesystem transaction operations can be treated as sleeping locks. 
> So for ext3, journal_start()/journal_stop() may, for lock-ranking purposes,
> be treated in the same way as taking and releasing a per-superblock
> semaphore.  Other filesystems probably have similar restrictions.
> 
> Other such "hidden" sleeping locks are lock_sock() and wait_on_inode().  The
> latter is rather messy because there is no clear API function which sets
> I_LOCK.
> 
> And pte_chain_lock() is a custom spinlock.

Good deal.  Thanks for the pointers, I was missing all of these besides
lock_sock.

One nice thing is that the race detector has been OK at pointing out
when a locking function is missing from our list.

Dawson

Re: [CHECKER] potential deadlocks

[Nikita Danilov]

Andrew Morton writes:
 > Dawson Engler <engler@csl.stanford.edu> wrote:
 > >
 > > BTW, are there known deadlocks (harmless or otherwise)?  Debugging
 > > the checker is a bit hard since false negatives are silent...
 > 
 > Known deadlocks tend to get fixed.  But I am surprised that you did not
 > encounter more of them.
 > 
 > btw, the filesystem transaction operations can be treated as sleeping locks. 
 > So for ext3, journal_start()/journal_stop() may, for lock-ranking purposes,
 > be treated in the same way as taking and releasing a per-superblock
 > semaphore.  Other filesystems probably have similar restrictions.
 > 

So are page-fault and memory allocation events, because thread
blocks on them, and deadlocks involving servicing page fault or memory
laundering have definitely been seen.

We have (incomplete) description of kernel lock ordering, which is
centered around reiser4 locks, but also includes some core kernel stuff.

It is available at 

http://www.namesys.com/v4/lock-ordering.dot  --- source for Bell-Labs' dot(1)
http://www.namesys.com/v4/lock-ordering.ps   --- postscript output, produced from the .dot source

 > Other such "hidden" sleeping locks are lock_sock() and wait_on_inode().  The
 > latter is rather messy because there is no clear API function which sets
 > I_LOCK.

Nikita.

Re: [CHECKER] potential deadlocks

[Dawson Engler]

> Andrew Morton writes:
>  > Dawson Engler <engler@csl.stanford.edu> wrote:
>  > >
>  > > BTW, are there known deadlocks (harmless or otherwise)?  Debugging
>  > > the checker is a bit hard since false negatives are silent...
>  > 
>  > Known deadlocks tend to get fixed.  But I am surprised that you did not
>  > encounter more of them.
>  > 
>  > btw, the filesystem transaction operations can be treated as sleeping locks. 
>  > So for ext3, journal_start()/journal_stop() may, for lock-ranking purposes,
>  > be treated in the same way as taking and releasing a per-superblock
>  > semaphore.  Other filesystems probably have similar restrictions.
>  > 
> 
> So are page-fault and memory allocation events, because thread
> blocks on them, and deadlocks involving servicing page fault or memory
> laundering have definitely been seen.

Do you mean calls to copy_*_user and kmalloc(GFP_WAIT) or did you have
something else in mind as well?

> We have (incomplete) description of kernel lock ordering, which is
> centered around reiser4 locks, but also includes some core kernel stuff.
> 
> It is available at 
> 
> http://www.namesys.com/v4/lock-ordering.dot  --- source for Bell-Labs' dot(1)
> http://www.namesys.com/v4/lock-ordering.ps   --- postscript output, produced from the .dot source

Wonderful; thanks!

Re: [CHECKER] potential deadlocks

[Nikita Danilov]

Dawson Engler writes:
 > > Andrew Morton writes:

[...]

Sorry for delay.

 > 
 > Do you mean calls to copy_*_user and kmalloc(GFP_WAIT) or did you have
 > something else in mind as well?

Yes. Imagine thread that tries to allocate memory with __GFP_FS while
keeping some file system locks. Now try_to_free_pages() calls
->writepage() method that tries to acquire the same lock. See, for
examples, comment before fs/ext3/inode.c:ext3_writepage(), or in
fs/dcache.c:shrink_dcache_memory().

 > 
 > > We have (incomplete) description of kernel lock ordering, which is
 > > centered around reiser4 locks, but also includes some core kernel stuff.
 > > 
 > > It is available at 
 > > 
 > > http://www.namesys.com/v4/lock-ordering.dot  --- source for Bell-Labs' dot(1)
 > > http://www.namesys.com/v4/lock-ordering.ps   --- postscript output, produced from the .dot source
 > 
 > Wonderful; thanks!
 > 

I would be glad to receive additions and corrections for this diagram.

 > 
 > 
 > 

Nikita.

Re: [CHECKER] potential deadlocks

[Alan Cox]

On Mon, 2003-03-03 at 06:05, Dawson Engler wrote:
> BTW, are there known deadlocks (harmless or otherwise)?  Debugging
> the checker is a bit hard since false negatives are silent...

2.4.21pre5 has one in the scsi reset handler for ide-scsi, however its going to
depend on your tools following function pointer chains and stuff to
find it I fear