1. 18 12月, 2008 1 次提交
    • K
      locking, irq: enclose irq_desc_lock_class in CONFIG_LOCKDEP · 74c8a613
      KOSAKI Motohiro 提交于
      Impact: simplify code
      
      commit "08678b08: generic: sparse irqs: use irq_desc() [...]" introduced
      the irq_desc_lock_class variable.
      
      But it is used only if CONFIG_SPARSE_IRQ=Y or CONFIG_TRACE_IRQFLAGS=Y.
      Otherwise, following warnings happen:
      
      	CC      kernel/irq/handle.o
      	kernel/irq/handle.c:26: warning: 'irq_desc_lock_class' defined but not used
      
      Actually, current early_init_irq_lock_class has a bit strange and messy ifdef.
      In addition, it is not valueable.
      
      1. this function is protected by !CONFIG_SPARSE_IRQ, but that is not necessary.
         if CONFIG_SPARSE_IRQ=Y, desc of all irq number are initialized by NULL
         at first - then this function calling is safe.
      
      2. this function protected by CONFIG_TRACE_IRQFLAGS too. but it is not
         necessary either, because lockdep_set_class() doesn't have bad side
         effect even if CONFIG_TRACE_IRQFLAGS=n.
      
      This patch bloat kernel size a bit on CONFIG_TRACE_IRQFLAGS=n and
      CONFIG_SPARSE_IRQ=Y - but that's ok. early_init_irq_lock_class() is not
      a fastpatch at all.
      
      To avoid messy ifdefs is more important than a few bytes diet.
      Signed-off-by: NKOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      74c8a613
  2. 14 11月, 2008 1 次提交
    • I
      lockdep: include/linux/lockdep.h - fix warning in net/bluetooth/af_bluetooth.c · e8f6fbf6
      Ingo Molnar 提交于
      fix this warning:
      
        net/bluetooth/af_bluetooth.c:60: warning: ‘bt_key_strings’ defined but not used
        net/bluetooth/af_bluetooth.c:71: warning: ‘bt_slock_key_strings’ defined but not used
      
      this is a lockdep macro problem in the !LOCKDEP case.
      
      We cannot convert it to an inline because the macro works on multiple types,
      but we can mark the parameter used.
      
      [ also clean up a misaligned tab in sock_lock_init_class_and_name() ]
      
      [ also remove #ifdefs from around af_family_clock_key strings - which
        were certainly added to get rid of the ugly build warnings. ]
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      Signed-off-by: NDavid S. Miller <davem@davemloft.net>
      e8f6fbf6
  3. 11 8月, 2008 8 次提交
    • I
      lockdep: increase MAX_LOCKDEP_KEYS · e5f363e3
      Ingo Molnar 提交于
      certain configs produce:
      
       [   70.076229] BUG: MAX_LOCKDEP_KEYS too low!
       [   70.080230] turning off the locking correctness validator.
      
      tune them up.
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      e5f363e3
    • P
      lockdep: fix overflow in the hlock shrinkage code · b42e737e
      Peter Zijlstra 提交于
      There is a overflow by 1 case in the new shrunken hlock code.
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      b42e737e
    • I
      lockdep: rename map_[acquire|release]() => lock_map_[acquire|release]() · 3295f0ef
      Ingo Molnar 提交于
      the names were too generic:
      
       drivers/uio/uio.c:87: error: expected identifier or '(' before 'do'
       drivers/uio/uio.c:87: error: expected identifier or '(' before 'while'
       drivers/uio/uio.c:113: error: 'map_release' undeclared here (not in a function)
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      3295f0ef
    • P
      lockdep: spin_lock_nest_lock() · b7d39aff
      Peter Zijlstra 提交于
      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: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      b7d39aff
    • P
      lockdep: lock protection locks · 7531e2f3
      Peter Zijlstra 提交于
      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: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      7531e2f3
    • P
      lockdep: map_acquire · 4f3e7524
      Peter Zijlstra 提交于
      Most the free-standing lock_acquire() usages look remarkably similar, sweep
      them into a new helper.
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      4f3e7524
    • D
      lockdep: shrink held_lock structure · f82b217e
      Dave Jones 提交于
      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: NDave Jones <davej@redhat.com>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      f82b217e
    • P
      lockdep: lock_set_subclass - reset a held lock's subclass · 64aa348e
      Peter Zijlstra 提交于
      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: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      64aa348e
  4. 01 8月, 2008 1 次提交
    • D
      lockdep: fix combinatorial explosion in lock subgraph traversal · 419ca3f1
      David Miller 提交于
      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: NDavid S. Miller <davem@davemloft.net>
      Acked-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      419ca3f1
  5. 24 6月, 2008 1 次提交
  6. 20 6月, 2008 1 次提交
  7. 20 10月, 2007 1 次提交
  8. 12 10月, 2007 2 次提交
  9. 20 7月, 2007 3 次提交
    • P
      lockstat: measure lock bouncing · 96645678
      Peter Zijlstra 提交于
          __acquire
              |
             lock _____
              |        \
              |    __contended
              |         |
              |        wait
              | _______/
              |/
              |
         __acquired
              |
         __release
              |
           unlock
      
      We measure acquisition and contention bouncing.
      
      This is done by recording a cpu stamp in each lock instance.
      
      Contention bouncing requires the cpu stamp to be set on acquisition. Hence we
      move __acquired into the generic path.
      
      __acquired is then used to measure acquisition bouncing by comparing the
      current cpu with the old stamp before replacing it.
      
      __contended is used to measure contention bouncing (only useful for preemptable
      locks)
      
      [akpm@linux-foundation.org: cleanups]
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Acked-by: NIngo Molnar <mingo@elte.hu>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      96645678
    • P
      lockdep: various fixes · 4b32d0a4
      Peter Zijlstra 提交于
       - update the copyright notices
       - use the default hash function
       - fix a thinko in a BUILD_BUG_ON
       - add a WARN_ON to spot inconsitent naming
       - fix a termination issue in /proc/lock_stat
      
      [akpm@linux-foundation.org: cleanups]
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Acked-by: NIngo Molnar <mingo@elte.hu>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      4b32d0a4
    • P
      lockstat: core infrastructure · f20786ff
      Peter Zijlstra 提交于
      Introduce the core lock statistics code.
      
      Lock statistics provides lock wait-time and hold-time (as well as the count
      of corresponding contention and acquisitions events). Also, the first few
      call-sites that encounter contention are tracked.
      
      Lock wait-time is the time spent waiting on the lock. This provides insight
      into the locking scheme, that is, a heavily contended lock is indicative of
      a too coarse locking scheme.
      
      Lock hold-time is the duration the lock was held, this provides a reference for
      the wait-time numbers, so they can be put into perspective.
      
        1)
          lock
        2)
          ... do stuff ..
          unlock
        3)
      
      The time between 1 and 2 is the wait-time. The time between 2 and 3 is the
      hold-time.
      
      The lockdep held-lock tracking code is reused, because it already collects locks
      into meaningful groups (classes), and because it is an existing infrastructure
      for lock instrumentation.
      
      Currently lockdep tracks lock acquisition with two hooks:
      
        lock()
          lock_acquire()
          _lock()
      
       ... code protected by lock ...
      
        unlock()
          lock_release()
          _unlock()
      
      We need to extend this with two more hooks, in order to measure contention.
      
        lock_contended() - used to measure contention events
        lock_acquired()  - completion of the contention
      
      These are then placed the following way:
      
        lock()
          lock_acquire()
          if (!_try_lock())
            lock_contended()
            _lock()
            lock_acquired()
      
       ... do locked stuff ...
      
        unlock()
          lock_release()
          _unlock()
      
      (Note: the try_lock() 'trick' is used to avoid instrumenting all platform
             dependent lock primitive implementations.)
      
      It is also possible to toggle the two lockdep features at runtime using:
      
        /proc/sys/kernel/prove_locking
        /proc/sys/kernel/lock_stat
      
      (esp. turning off the O(n^2) prove_locking functionaliy can help)
      
      [akpm@linux-foundation.org: build fixes]
      [akpm@linux-foundation.org: nuke unneeded ifdefs]
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Acked-by: NIngo Molnar <mingo@elte.hu>
      Acked-by: NJason Baron <jbaron@redhat.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      f20786ff
  10. 23 3月, 2007 1 次提交
  11. 13 2月, 2007 1 次提交
  12. 12 2月, 2007 1 次提交
  13. 14 12月, 2006 1 次提交
  14. 08 12月, 2006 2 次提交
  15. 12 10月, 2006 1 次提交
  16. 11 10月, 2006 1 次提交
  17. 30 9月, 2006 1 次提交
  18. 11 7月, 2006 1 次提交
  19. 04 7月, 2006 2 次提交
    • I
      [PATCH] lockdep: annotate genirq · 243c7621
      Ingo Molnar 提交于
      Teach special (recursive) locking code to the lock validator.  Has no effect
      on non-lockdep kernels.
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      Signed-off-by: NArjan van de Ven <arjan@linux.intel.com>
      Signed-off-by: NAndrew Morton <akpm@osdl.org>
      Signed-off-by: NLinus Torvalds <torvalds@osdl.org>
      243c7621
    • I
      [PATCH] lockdep: core · fbb9ce95
      Ingo Molnar 提交于
      Do 'make oldconfig' and accept all the defaults for new config options -
      reboot into the kernel and if everything goes well it should boot up fine and
      you should have /proc/lockdep and /proc/lockdep_stats files.
      
      Typically if the lock validator finds some problem it will print out
      voluminous debug output that begins with "BUG: ..." and which syslog output
      can be used by kernel developers to figure out the precise locking scenario.
      
      What does the lock validator do?  It "observes" and maps all locking rules as
      they occur dynamically (as triggered by the kernel's natural use of spinlocks,
      rwlocks, mutexes and rwsems).  Whenever the lock validator subsystem detects a
      new locking scenario, it validates this new rule against the existing set of
      rules.  If this new rule is consistent with the existing set of rules then the
      new rule is added transparently and the kernel continues as normal.  If the
      new rule could create a deadlock scenario then this condition is printed out.
      
      When determining validity of locking, all possible "deadlock scenarios" are
      considered: assuming arbitrary number of CPUs, arbitrary irq context and task
      context constellations, running arbitrary combinations of all the existing
      locking scenarios.  In a typical system this means millions of separate
      scenarios.  This is why we call it a "locking correctness" validator - for all
      rules that are observed the lock validator proves it with mathematical
      certainty that a deadlock could not occur (assuming that the lock validator
      implementation itself is correct and its internal data structures are not
      corrupted by some other kernel subsystem).  [see more details and conditionals
      of this statement in include/linux/lockdep.h and
      Documentation/lockdep-design.txt]
      
      Furthermore, this "all possible scenarios" property of the validator also
      enables the finding of complex, highly unlikely multi-CPU multi-context races
      via single single-context rules, increasing the likelyhood of finding bugs
      drastically.  In practical terms: the lock validator already found a bug in
      the upstream kernel that could only occur on systems with 3 or more CPUs, and
      which needed 3 very unlikely code sequences to occur at once on the 3 CPUs.
      That bug was found and reported on a single-CPU system (!).  So in essence a
      race will be found "piecemail-wise", triggering all the necessary components
      for the race, without having to reproduce the race scenario itself!  In its
      short existence the lock validator found and reported many bugs before they
      actually caused a real deadlock.
      
      To further increase the efficiency of the validator, the mapping is not per
      "lock instance", but per "lock-class".  For example, all struct inode objects
      in the kernel have inode->inotify_mutex.  If there are 10,000 inodes cached,
      then there are 10,000 lock objects.  But ->inotify_mutex is a single "lock
      type", and all locking activities that occur against ->inotify_mutex are
      "unified" into this single lock-class.  The advantage of the lock-class
      approach is that all historical ->inotify_mutex uses are mapped into a single
      (and as narrow as possible) set of locking rules - regardless of how many
      different tasks or inode structures it took to build this set of rules.  The
      set of rules persist during the lifetime of the kernel.
      
      To see the rough magnitude of checking that the lock validator does, here's a
      portion of /proc/lockdep_stats, fresh after bootup:
      
       lock-classes:                            694 [max: 2048]
       direct dependencies:                  1598 [max: 8192]
       indirect dependencies:               17896
       all direct dependencies:             16206
       dependency chains:                    1910 [max: 8192]
       in-hardirq chains:                      17
       in-softirq chains:                     105
       in-process chains:                    1065
       stack-trace entries:                 38761 [max: 131072]
       combined max dependencies:         2033928
       hardirq-safe locks:                     24
       hardirq-unsafe locks:                  176
       softirq-safe locks:                     53
       softirq-unsafe locks:                  137
       irq-safe locks:                         59
       irq-unsafe locks:                      176
      
      The lock validator has observed 1598 actual single-thread locking patterns,
      and has validated all possible 2033928 distinct locking scenarios.
      
      More details about the design of the lock validator can be found in
      Documentation/lockdep-design.txt, which can also found at:
      
         http://redhat.com/~mingo/lockdep-patches/lockdep-design.txt
      
      [bunk@stusta.de: cleanups]
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      Signed-off-by: NArjan van de Ven <arjan@linux.intel.com>
      Signed-off-by: NAdrian Bunk <bunk@stusta.de>
      Signed-off-by: NAndrew Morton <akpm@osdl.org>
      Signed-off-by: NLinus Torvalds <torvalds@osdl.org>
      fbb9ce95