1. 11 Aug, 2008 8 commits
    • Peter Zijlstra's avatar
      mm: fix mm_take_all_locks() locking order · 7cd5a02f
      Peter Zijlstra authored
      Lockdep spotted:
      
      =======================================================
      [ INFO: possible circular locking dependency detected ]
      2.6.27-rc1 #270
      -------------------------------------------------------
      qemu-kvm/2033 is trying to acquire lock:
       (&inode->i_data.i_mmap_lock){----}, at: [<ffffffff802996cc>] mm_take_all_locks+0xc2/0xea
      
      but task is already holding lock:
       (&anon_vma->lock){----}, at: [<ffffffff8029967a>] mm_take_all_locks+0x70/0xea
      
      which lock already depends on the new lock.
      
      the existing dependency chain (in reverse order) is:
      
      -> #1 (&anon_vma->lock){----}:
             [<ffffffff8025cd37>] __lock_acquire+0x11be/0x14d2
             [<ffffffff8025d0a9>] lock_acquire+0x5e/0x7a
             [<ffffffff804c655b>] _spin_lock+0x3b/0x47
             [<ffffffff8029a2ef>] vma_adjust+0x200/0x444
             [<ffffffff8029a662>] split_vma+0x12f/0x146
             [<ffffffff8029bc60>] mprotect_fixup+0x13c/0x536
             [<ffffffff8029c203>] sys_mprotect+0x1a9/0x21e
             [<ffffffff8020c0db>] system_call_fastpath+0x16/0x1b
             [<ffffffffffffffff>] 0xffffffffffffffff
      
      -> #0 (&inode->i_data.i_mmap_lock){----}:
             [<ffffffff8025ca54>] __lock_acquire+0xedb/0x14d2
             [<ffffffff8025d397>] lock_release_non_nested+0x1c2/0x219
             [<ffffffff8025d515>] lock_release+0x127/0x14a
             [<ffffffff804c6403>] _spin_unlock+0x1e/0x50
             [<ffffffff802995d9>] mm_drop_all_locks+0x7f/0xb0
             [<ffffffff802a965d>] do_mmu_notifier_register+0xe2/0x112
             [<ffffffff802a96a8>] mmu_notifier_register+0xe/0x10
             [<ffffffffa0043b6b>] kvm_dev_ioctl+0x11e/0x287 [kvm]
             [<ffffffff802bd0ca>] vfs_ioctl+0x2a/0x78
             [<ffffffff802bd36f>] do_vfs_ioctl+0x257/0x274
             [<ffffffff802bd3e1>] sys_ioctl+0x55/0x78
             [<ffffffff8020c0db>] system_call_fastpath+0x16/0x1b
             [<ffffffffffffffff>] 0xffffffffffffffff
      
      other info that might help us debug this:
      
      5 locks held by qemu-kvm/2033:
       #0:  (&mm->mmap_sem){----}, at: [<ffffffff802a95d0>] do_mmu_notifier_register+0x55/0x112
       #1:  (mm_all_locks_mutex){--..}, at: [<ffffffff8029963e>] mm_take_all_locks+0x34/0xea
       #2:  (&anon_vma->lock){----}, at: [<ffffffff8029967a>] mm_take_all_locks+0x70/0xea
       #3:  (&anon_vma->lock){----}, at: [<ffffffff8029967a>] mm_take_all_locks+0x70/0xea
       #4:  (&anon_vma->lock){----}, at: [<ffffffff8029967a>] mm_take_all_locks+0x70/0xea
      
      stack backtrace:
      Pid: 2033, comm: qemu-kvm Not tainted 2.6.27-rc1 #270
      
      Call Trace:
       [<ffffffff8025b7c7>] print_circular_bug_tail+0xb8/0xc3
       [<ffffffff8025ca54>] __lock_acquire+0xedb/0x14d2
       [<ffffffff80259bb1>] ? add_lock_to_list+0x7e/0xad
       [<ffffffff8029967a>] ? mm_take_all_locks+0x70/0xea
       [<ffffffff8029967a>] ? mm_take_all_locks+0x70/0xea
       [<ffffffff8025d397>] lock_release_non_nested+0x1c2/0x219
       [<ffffffff802996cc>] ? mm_take_all_locks+0xc2/0xea
       [<ffffffff802996cc>] ? mm_take_all_locks+0xc2/0xea
       [<ffffffff8025b202>] ? trace_hardirqs_on_caller+0x4d/0x115
       [<ffffffff802995d9>] ? mm_drop_all_locks+0x7f/0xb0
       [<ffffffff8025d515>] lock_release+0x127/0x14a
       [<ffffffff804c6403>] _spin_unlock+0x1e/0x50
       [<ffffffff802995d9>] mm_drop_all_locks+0x7f/0xb0
       [<ffffffff802a965d>] do_mmu_notifier_register+0xe2/0x112
       [<ffffffff802a96a8>] mmu_notifier_register+0xe/0x10
       [<ffffffffa0043b6b>] kvm_dev_ioctl+0x11e/0x287 [kvm]
       [<ffffffff8033f9f2>] ? file_has_perm+0x83/0x8e
       [<ffffffff802bd0ca>] vfs_ioctl+0x2a/0x78
       [<ffffffff802bd36f>] do_vfs_ioctl+0x257/0x274
       [<ffffffff802bd3e1>] sys_ioctl+0x55/0x78
       [<ffffffff8020c0db>] system_call_fastpath+0x16/0x1b
      
      Which the locking hierarchy in mm/rmap.c confirms as valid.
      
      Fix this by first taking all the mapping->i_mmap_lock instances and then
      take all anon_vma->lock instances.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Acked-by: default avatarHugh Dickins <hugh@veritas.com>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      7cd5a02f
    • Peter Zijlstra's avatar
      lockdep: annotate mm_take_all_locks() · 454ed842
      Peter Zijlstra authored
      The nesting is correct due to holding mmap_sem, use the new annotation
      to annotate this.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      454ed842
    • Peter Zijlstra's avatar
      lockdep: spin_lock_nest_lock() · b7d39aff
      Peter Zijlstra authored
      Expose the new lock protection lock.
      
      This can be used to annotate places where we take multiple locks of the
      same class and avoid deadlocks by always taking another (top-level) lock
      first.
      
      NOTE: we're still bound to the MAX_LOCK_DEPTH (48) limit.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      b7d39aff
    • Peter Zijlstra's avatar
      lockdep: lock protection locks · 7531e2f3
      Peter Zijlstra authored
      On Fri, 2008-08-01 at 16:26 -0700, Linus Torvalds wrote:
      
      > On Fri, 1 Aug 2008, David Miller wrote:
      > >
      > > Taking more than a few locks of the same class at once is bad
      > > news and it's better to find an alternative method.
      >
      > It's not always wrong.
      >
      > If you can guarantee that anybody that takes more than one lock of a
      > particular class will always take a single top-level lock _first_, then
      > that's all good. You can obviously screw up and take the same lock _twice_
      > (which will deadlock), but at least you cannot get into ABBA situations.
      >
      > So maybe the right thing to do is to just teach lockdep about "lock
      > protection locks". That would have solved the multi-queue issues for
      > networking too - all the actual network drivers would still have taken
      > just their single queue lock, but the one case that needs to take all of
      > them would have taken a separate top-level lock first.
      >
      > Never mind that the multi-queue locks were always taken in the same order:
      > it's never wrong to just have some top-level serialization, and anybody
      > who needs to take <n> locks might as well do <n+1>, because they sure as
      > hell aren't going to be on _any_ fastpaths.
      >
      > So the simplest solution really sounds like just teaching lockdep about
      > that one special case. It's not "nesting" exactly, although it's obviously
      > related to it.
      
      Do as Linus suggested. The lock protection lock is called nest_lock.
      
      Note that we still have the MAX_LOCK_DEPTH (48) limit to consider, so anything
      that spills that it still up shit creek.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      7531e2f3
    • Peter Zijlstra's avatar
      lockdep: map_acquire · 4f3e7524
      Peter Zijlstra authored
      Most the free-standing lock_acquire() usages look remarkably similar, sweep
      them into a new helper.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      4f3e7524
    • Dave Jones's avatar
      lockdep: shrink held_lock structure · f82b217e
      Dave Jones authored
      struct held_lock {
              u64                        prev_chain_key;       /*     0     8 */
              struct lock_class *        class;                /*     8     8 */
              long unsigned int          acquire_ip;           /*    16     8 */
              struct lockdep_map *       instance;             /*    24     8 */
              int                        irq_context;          /*    32     4 */
              int                        trylock;              /*    36     4 */
              int                        read;                 /*    40     4 */
              int                        check;                /*    44     4 */
              int                        hardirqs_off;         /*    48     4 */
      
              /* size: 56, cachelines: 1 */
              /* padding: 4 */
              /* last cacheline: 56 bytes */
      };
      
      struct held_lock {
              u64                        prev_chain_key;       /*     0     8 */
              long unsigned int          acquire_ip;           /*     8     8 */
              struct lockdep_map *       instance;             /*    16     8 */
              unsigned int               class_idx:11;         /*    24:21  4 */
              unsigned int               irq_context:2;        /*    24:19  4 */
              unsigned int               trylock:1;            /*    24:18  4 */
              unsigned int               read:2;               /*    24:16  4 */
              unsigned int               check:2;              /*    24:14  4 */
              unsigned int               hardirqs_off:1;       /*    24:13  4 */
      
              /* size: 32, cachelines: 1 */
              /* padding: 4 */
              /* bit_padding: 13 bits */
              /* last cacheline: 32 bytes */
      };
      
      [mingo@elte.hu: shrunk hlock->class too]
      [peterz@infradead.org: fixup bit sizes]
      Signed-off-by: default avatarDave Jones <davej@redhat.com>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      f82b217e
    • Peter Zijlstra's avatar
      lockdep: re-annotate scheduler runqueues · 1b12bbc7
      Peter Zijlstra authored
      Instead of using a per-rq lock class, use the regular nesting operations.
      
      However, take extra care with double_lock_balance() as it can release the
      already held rq->lock (and therefore change its nesting class).
      
      So what can happen is:
      
       spin_lock(rq->lock);	// this rq subclass 0
      
       double_lock_balance(rq, other_rq);
         // release rq
         // acquire other_rq->lock subclass 0
         // acquire rq->lock subclass 1
      
       spin_unlock(other_rq->lock);
      
      leaving you with rq->lock in subclass 1
      
      So a subsequent double_lock_balance() call can try to nest a subclass 1
      lock while already holding a subclass 1 lock.
      
      Fix this by introducing double_unlock_balance() which releases the other
      rq's lock, but also re-sets the subclass for this rq's lock to 0.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      1b12bbc7
    • Peter Zijlstra's avatar
      lockdep: lock_set_subclass - reset a held lock's subclass · 64aa348e
      Peter Zijlstra authored
      this can be used to reset a held lock's subclass, for arbitrary-depth
      iterated data structures such as trees or lists which have per-node
      locks.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      64aa348e
  2. 01 Aug, 2008 2 commits
  3. 31 Jul, 2008 1 commit
    • David Miller's avatar
      lockdep: fix combinatorial explosion in lock subgraph traversal · 419ca3f1
      David Miller authored
      When we traverse the graph, either forwards or backwards, we
      are interested in whether a certain property exists somewhere
      in a node reachable in the graph.
      
      Therefore it is never necessary to traverse through a node more
      than once to get a correct answer to the given query.
      
      Take advantage of this property using a global ID counter so that we
      need not clear all the markers in all the lock_class entries before
      doing a traversal.  A new ID is choosen when we start to traverse, and
      we continue through a lock_class only if it's ID hasn't been marked
      with the new value yet.
      
      This short-circuiting is essential especially for high CPU count
      systems.  The scheduler has a runqueue per cpu, and needs to take
      two runqueue locks at a time, which leads to long chains of
      backwards and forwards subgraphs from these runqueue lock nodes.
      Without the short-circuit implemented here, a graph traversal on
      a runqueue lock can take up to (1 << (N - 1)) checks on a system
      with N cpus.
      
      For anything more than 16 cpus or so, lockdep will eventually bring
      the machine to a complete standstill.
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      Acked-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      419ca3f1
  4. 29 Jul, 2008 6 commits
  5. 28 Jul, 2008 23 commits