Re: 2.6.17-rc6-mm1 -- BUG: possible circular locking deadlock detected!

Anton Altaparmakov
2006-06-11T07:10:16Z

On Sun, 11 Jun 2006, Ingo Molnar wrote:
> * Anton Altaparmakov <aia21@cam.ac.uk> wrote:
>
> > I think the lock validator has the problem of not knowing that there
> > are two different types of runlist which is why it complains about it.
>
> ah, ok! What happened is that the rwlock_init() 'lock type keys'
> (inlined via ntfs_init_runlist()) for the two runlists were 'merged':
>
> ntfs_init_runlist(&ni->runlist);
> ntfs_init_runlist(&ni->attr_list_rl);
>
> i have annotated things by initializing the two locks separately (via a
> simple oneliner change), and this has solved the problem.
>
> The two types are now properly 'split', and the validator tracks them
> separately and understands their separate roles. So there's no need to
> touch attribute runlist locking in the NTFS code.

Great!

> Some background: the validator uses lock initialization as a hint about

Thanks for explaining.

> The good news is that after this fix things went pretty well for
> readonly stuff and i got no new complaints from the validator. Phew! :-)

Great!

> It does not fully cover read-write mode yet. When extending an existing
> file the validator did not understand the following locking construct:
>
> =======================================================
> [ INFO: possible circular locking dependency detected ]
> -------------------------------------------------------
> cat/2802 is trying to acquire lock:
> (&vol->lcnbmp_lock){----}, at: [<c01e80dd>] ntfs_cluster_alloc+0x10d/0x23a0
>
> but task is already holding lock:
> (&ni->mrec_lock){--..}, at: [<c01d5e53>] map_mft_record+0x53/0x2c0
>
> which lock already depends on the new lock,
> which could lead to circular dependencies.
>
> the existing dependency chain (in reverse order) is:
>
> -> #2 (&ni->mrec_lock){--..}:
> [<c01394df>] lock_acquire+0x6f/0x90
> [<c0346193>] mutex_lock_nested+0x73/0x2a0
> [<c01d5e53>] map_mft_record+0x53/0x2c0
> [<c01c54f8>] ntfs_map_runlist_nolock+0x3d8/0x530
> [<c01c5bc1>] ntfs_map_runlist+0x41/0x70
> [<c01c1929>] ntfs_readpage+0x8c9/0x9b0
> [<c0142ffc>] read_cache_page+0xac/0x150
> [<c01e213d>] ntfs_statfs+0x41d/0x660
> [<c0163254>] vfs_statfs+0x54/0x70
> [<c0163288>] vfs_statfs64+0x18/0x30
> [<c0163384>] sys_statfs64+0x64/0xa0
> [<c0347ddd>] sysenter_past_esp+0x56/0x8d
>
> -> #1 (&rl->lock){----}:
> [<c01394df>] lock_acquire+0x6f/0x90
> [<c0134c8a>] down_read_nested+0x2a/0x40
> [<c01c18a4>] ntfs_readpage+0x844/0x9b0
> [<c0142ffc>] read_cache_page+0xac/0x150
> [<c01e213d>] ntfs_statfs+0x41d/0x660
> [<c0163254>] vfs_statfs+0x54/0x70
> [<c0163288>] vfs_statfs64+0x18/0x30
> [<c0163384>] sys_statfs64+0x64/0xa0
> [<c0347ddd>] sysenter_past_esp+0x56/0x8d
>
> -> #0 (&vol->lcnbmp_lock){----}:
> [<c01394df>] lock_acquire+0x6f/0x90
> [<c0134ccc>] down_write+0x2c/0x50
> [<c01e80dd>] ntfs_cluster_alloc+0x10d/0x23a0
> [<c01c427d>] ntfs_attr_extend_allocation+0x5fd/0x14a0
> [<c01caa38>] ntfs_file_buffered_write+0x188/0x3880
> [<c01ce2a8>] ntfs_file_aio_write_nolock+0x178/0x210
> [<c01ce3f1>] ntfs_file_writev+0xb1/0x150
> [<c01ce4af>] ntfs_file_write+0x1f/0x30
> [<c0164f09>] vfs_write+0x99/0x160
> [<c016589d>] sys_write+0x3d/0x70
> [<c0347ddd>] sysenter_past_esp+0x56/0x8d
>
> other info that might help us debug this:
>
> 3 locks held by cat/2802:
> #0: (&inode->i_mutex){--..}, at: [<c0346118>] mutex_lock+0x8/0x10
> #1: (&rl->lock){----}, at: [<c01c3dbe>] ntfs_attr_extend_allocation+0x13e/0x14a0
> #2: (&ni->mrec_lock){--..}, at: [<c01d5e53>] map_mft_record+0x53/0x2c0
>
> stack backtrace:
> [<c0104bf2>] show_trace+0x12/0x20
> [<c0104c19>] dump_stack+0x19/0x20
> [<c0136ef1>] print_circular_bug_tail+0x61/0x70
> [<c01389ff>] __lock_acquire+0x74f/0xde0
> [<c01394df>] lock_acquire+0x6f/0x90
> [<c0134ccc>] down_write+0x2c/0x50
> [<c01e80dd>] ntfs_cluster_alloc+0x10d/0x23a0
> [<c01c427d>] ntfs_attr_extend_allocation+0x5fd/0x14a0
> [<c01caa38>] ntfs_file_buffered_write+0x188/0x3880
> [<c01ce2a8>] ntfs_file_aio_write_nolock+0x178/0x210
> [<c01ce3f1>] ntfs_file_writev+0xb1/0x150
> [<c01ce4af>] ntfs_file_write+0x1f/0x30
> [<c0164f09>] vfs_write+0x99/0x160
> [<c016589d>] sys_write+0x3d/0x70
> [<c0347ddd>] sysenter_past_esp+0x56/0x8d
>
> this seems to be a pretty complex 3-way dependency related to
> &vol->lcnbmp_lock and &ni->mrec_lock. Should i send a full dependency
> events trace perhaps?

First an explanation of two relevant locks that are both going to upset
the validator. I half expected this to happen given what has happened so
far. The two locks are lcnbmp_lock and mftbmp_lock (both are r/w
semaphores).

Both those locks lock the two big bitmaps on an NTFS volume:

lcnbmp_lock locks accesses to the cluster bitmap (i.e. the physical blocks
bitmap where each 0 bit means an unallocated block and a 1 bit means an
allocated block).

mftbmp_lock locks accesses to the mft bitmap (i.e. the inodes bitmap where
each 0 bit means an unused inode and a 1 bit means the inode is in use).

The locks are taken when a cluster is being allocated / an mft record is
being allocated.

The reason the validator will likely get very confused is that they
introduce reverse semantics depending on what you are locking, i.e.

When extending a file the locking order is:

Lock runlist (data one) of file to be extended for writing (as it will be
modified by the file extension).

Lock lcnbmp_lock for writing (as the bitmap will be modified by the
allocated clusters).

Lock runlist of $Bitmap system file (the contents of which contain the
bitmap) for reading so the on-disk physical location can be determined.

If the above fails then re-lock the runlist of $Bitmap for writing and
lock mft record of $Bitmap system file and load in the runlist of the
bitmap, the unlock the mft record, unlock the runlist of $Bitmap.

Load the $Bitmap data and allocate clusters in the bitmap.

Unlock lcnbmp_lock.

Update the runlist of the file being extended with the newly allocated
clusters.

Lock the mft record of the file being extended and update the mft record
with the new allocations.

Unlock the mft record and the runlist of the file that was extended.

So yes lock dependencies are inverted the validator complains. But they
are inverted in a special way that is safe.

Is the above description sufficient for you to fix it?

The mftbmp_lock works simillarly as above but instead of allocating
clusters we are allocating an mft record, the locking sequence is the
same though just substitute s/lcnbmp_lock/mftbmp_lock/ and s/cluster
allocation/mft record allocation/.

Extending the mft in turn can require the mft itself to be extended which
will take the lcnbmp_lock, thus mftbmp_lock nests outside the lcnbmp_lock
and that should never be violated so the validator should be at least
happy with that bit. (-;

Sorry ntfs is that locking evil!

Best regards,

Anton
--
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/