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

On Sun, 11 Jun 2006, Ingo Molnar wrote:
* Anton Altaparmakov <aia21@xxxxxxxxx> 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/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: [RFC][PATCH] Reduce ext3 allocate-with-reservation lock latencies
    ... Maybe that lock is rarely ... I will try it on a relatively full filesystem(where bitmap ... > scan to find a free block takes time), and on a 4 cpu box with many ... overhead of drop/re-grab lock and extra window search/link/unlink ...
    (Linux-Kernel)
  • Re: Having trouble with multiple threads and a shared resource
    ... I read that you should use a static private object as a lock, ... access between the threads to the bitmap. ... private void _replayPathTaken_Click ... HighlightSelectedCells method need access to MyBitmap and sometimes they ...
    (microsoft.public.dotnet.languages.csharp)
  • Flickering
    ... I figure that if I lock the bitmap that I can draw on it without the painter ... FormGraphics = this.CreateGraphics; ... protected override void OnPaintBackground ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: SetPixel() / GetPixel() for Format64bppArgb in VB using LockBits
    ... I didn't know that one can lock just some parts of the bitmap. ... So you mean if one has to set 1 pixel, ... Find great Windows Forms articles in Windows Forms Tips and Tricks ...
    (microsoft.public.dotnet.framework.drawing)
  • Re: Can you lock a slide in PowerPoint?
    ... > to group all the contents togetherbut this doesnt really lock them. ... You can export the slide to a bitmap then import the bitmap into a new ... Steve Rindsberg, PPT MVP ...
    (microsoft.public.powerpoint)
Loading