1. 23 Sep, 2018 1 commit
    • Philippe Gerum's avatar
      lockdep: ipipe: make the logic aware of interrupt pipelining · a8c071b1
      Philippe Gerum authored
      The lockdep engine will check for the current interrupt state as part
      of the locking validation process, which must encompass:
      - the CPU interrupt state
      - the current pipeline domain
      - the virtual interrupt disable flag
      so that we can traverse the tracepoints from any context sanely and
      In addition trace_hardirqs_on_virt_caller() should be called by the
      arch-dependent code when tracking the interrupt state before returning
      to user-space after a kernel entry (exceptions, IRQ). This makes sure
      that the tracking logic only applies to the root domain, and considers
      the virtual disable flag exclusively.
      For instance, the kernel may be entered when interrupts are (only)
      virtually disabled for the root domain (i.e. stalled), and we should
      tell the IRQ tracing logic that IRQs are about to be enabled back only
      if the root domain is unstalled before leaving to user-space. In such
      a context, the state of the interrupt bit in the CPU would be
  2. 02 Nov, 2017 1 commit
    • Greg Kroah-Hartman's avatar
      License cleanup: add SPDX GPL-2.0 license identifier to files with no license · b2441318
      Greg Kroah-Hartman authored
      Many source files in the tree are missing licensing information, which
      makes it harder for compliance tools to determine the correct license.
      By default all files without license information are under the default
      license of the kernel, which is GPL version 2.
      Update the files which contain no license information with the 'GPL-2.0'
      SPDX license identifier.  The SPDX identifier is a legally binding
      shorthand, which can be used instead of the full boiler plate text.
      This patch is based on work done by Thomas Gleixner and Kate Stewart and
      Philippe Ombredanne.
      How this work was done:
      Patches were generated and checked against linux-4.14-rc6 for a subset of
      the use cases:
       - file had no licensing information it it.
       - file was a */uapi/* one with no licensing information in it,
       - file was a */uapi/* one with existing licensing information,
      Further patches will be generated in subsequent months to fix up cases
      where non-standard...
  3. 10 Aug, 2017 1 commit
    • Peter Zijlstra's avatar
      locking/lockdep: Avoid creating redundant links · ae813308
      Peter Zijlstra authored
      Two boots + a make defconfig, the first didn't have the redundant bit
      in, the second did:
       lock-classes:                         1168       1169 [max: 8191]
       direct dependencies:                  7688       5812 [max: 32768]
       indirect dependencies:               25492      25937
       all direct dependencies:            220113     217512
       dependency chains:                    9005       9008 [max: 65536]
       dependency chain hlocks:             34450      34366 [max: 327680]
       in-hardirq chains:                      55         51
       in-softirq chains:                     371        378
       in-process chains:                    8579       8579
       stack-trace entries:                108073      88474 [max: 524288]
       combined max dependencies:       178738560  169094640
       max locking depth:                      15         15
       max bfs queue depth:                   320        329
       cyclic checks:                        9123       9190
       redundant checks:                                5046
       redundant links:                                 1828
       find-mask forwards checks:            2564       2599
       find-mask backwards checks:          39521      39789
      So it saves nearly 2k links and a fair chunk of stack-trace entries, but
      as expected, makes no real difference on the indirect dependencies.
      At the same time, you see the max BFS depth increase, which is also
      expected, although it could easily be boot variance -- these numbers are
      not entirely stable between boots.
      The down side is that the cycles in the graph become larger and thus
      the reports harder to read.
      XXX: do we want this as a CONFIG variable, implied by LOCKDEP_SMALL?
      Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
      Cc: Byungchul Park <byungchul.park@lge.com>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Cc: Mel Gorman <mgorman@suse.de>
      Cc: Michal Hocko <mhocko@kernel.org>
      Cc: Nikolay Borisov <nborisov@suse.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: akpm@linux-foundation.org
      Cc: boqun.feng@gmail.com
      Cc: iamjoonsoo.kim@lge.com
      Cc: kernel-team@lge.com
      Cc: kirill@shutemov.name
      Cc: npiggin@gmail.com
      Cc: walken@google.com
      Link: http://lkml.kernel.org/r/20170303091338.GH6536@twins.programming.kicks-ass.net
      Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
  4. 18 Apr, 2017 1 commit
    • Daniel Jordan's avatar
      sparc64: Use LOCKDEP_SMALL, not PROVE_LOCKING_SMALL · 395102db
      Daniel Jordan authored
      CONFIG_PROVE_LOCKING_SMALL shrinks the memory usage of lockdep so the
      kernel text, data, and bss fit in the required 32MB limit, but this
      option is not set for every config that enables lockdep.
      A 4.10 kernel fails to boot with the console output
          Kernel: Using 8 locked TLB entries for main kernel image.
          hypervisor_tlb_lock[2000000:0:8000000071c007c3:1]: errors with f
          Program terminated
      with these config options
      enable this option with CONFIG_LOCKDEP=y so we get the reduced memory
      usage every time lockdep is turned on.
      Tested that CONFIG_LOCKDEP_SMALL is set to 'y' if and only if
      CONFIG_LOCKDEP is set to 'y'.  When other lockdep-related config options
      that select CONFIG_LOCKDEP are enabled (e.g. CONFIG_LOCK_STAT or
      Fixes: e6b5f1be
       ("config: Adding the new config parameter CONFIG_PROVE_LOCKING_SMALL for sparc")
      Signed-off-by: default avatarDaniel Jordan <daniel.m.jordan@oracle.com>
      Reviewed-by: default avatarBabu Moger <babu.moger@oracle.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
  5. 18 Nov, 2016 1 commit
  6. 18 Apr, 2014 1 commit
  7. 06 Nov, 2013 1 commit
  8. 04 May, 2010 3 commits
  9. 30 Apr, 2010 1 commit
  10. 05 Apr, 2010 1 commit
    • Frederic Weisbecker's avatar
      lockstat: Make lockstat counting per cpu · bd6d29c2
      Frederic Weisbecker authored
      Locking statistics are implemented using global atomic
      variables. This is usually fine unless some path write them very
      This is the case for the function and function graph tracers
      that disable irqs for each entry saved (except if the function
      tracer is in preempt disabled only mode).
      And calls to local_irq_save/restore() increment
      hardirqs_on_events and hardirqs_off_events stats (or similar
      stats for redundant versions).
      Incrementing these global vars for each function ends up in too
      much cache bouncing if lockstats are enabled.
      To solve this, implement the debug_atomic_*() operations using
      per cpu vars.
       -v2: Use per_cpu() instead of get_cpu_var() to fetch the desired
            cpu vars on debug_atomic_read()
       -v3: Store the stats in a structure. No need for local_t as we
            are NMI/irq safe.
       -v4: Fix tons of build errors. I thought I had tested it but I
            probably forgot to select the relevant config.
      Suggested-by: default avatarSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: default avatarFrederic Weisbecker <fweisbec@gmail.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Steven Rostedt <rostedt@goodmis.org>
      LKML-Reference: <1270505417-8144-1-git-send-regression-fweisbec@gmail.com>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Steven Rostedt <rostedt@goodmis.org>
  11. 24 Jul, 2009 5 commits
  12. 12 May, 2009 1 commit
    • Ingo Molnar's avatar
      lockdep: increase MAX_LOCKDEP_ENTRIES and MAX_LOCKDEP_CHAINS · d80c19df
      Ingo Molnar authored
      Now that lockdep coverage has increased it has become easier to
      run out of entries:
      [   21.401387] BUG: MAX_LOCKDEP_ENTRIES too low!
      [   21.402007] turning off the locking correctness validator.
      [   21.402007] Pid: 1555, comm: S99local Not tainted 2.6.30-rc5-tip #2
      [   21.402007] Call Trace:
      [   21.402007]  [<ffffffff81069789>] add_lock_to_list+0x53/0xba
      [   21.402007]  [<ffffffff810eb615>] ? lookup_mnt+0x19/0x53
      [   21.402007]  [<ffffffff8106be14>] check_prev_add+0x14b/0x1c7
      [   21.402007]  [<ffffffff8106c304>] validate_chain+0x474/0x52a
      [   21.402007]  [<ffffffff8106c6fc>] __lock_acquire+0x342/0x3c7
      [   21.402007]  [<ffffffff8106c842>] lock_acquire+0xc1/0xe5
      [   21.402007]  [<ffffffff810eb615>] ? lookup_mnt+0x19/0x53
      [   21.402007]  [<ffffffff8153aedc>] _spin_lock+0x31/0x66
      Double the size - as we've done in the past.
      [ Impact: allow lockdep to cover more locks ]
      Acked-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      LKML-Reference: <new-submission>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
  13. 14 Feb, 2009 4 commits
    • Peter Zijlstra's avatar
      lockdep: get_user_chars() redo · f510b233
      Peter Zijlstra authored
      Generic, states independent, get_user_chars().
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
    • Peter Zijlstra's avatar
      lockdep: generate the state bit definitions · d7b1b021
      Peter Zijlstra authored
      Generate the state bit definitions from the lockdep_states.h file.
      Also, move LOCK_USED to last, so that the
      states are nicely bit aligned -- we're going to use that property
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
    • Peter Zijlstra's avatar
      lockdep: move state bit definitions around · 9851673b
      Peter Zijlstra authored
      For convenience later.
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
    • Nick Piggin's avatar
      lockdep: annotate reclaim context (__GFP_NOFS) · cf40bd16
      Nick Piggin authored
      Here is another version, with the incremental patch rolled up, and
      added reclaim context annotation to kswapd, and allocation tracing
      to slab allocators (which may only ever reach the page allocator
      in rare cases, so it is good to put annotations here too).
      Haven't tested this version as such, but it should be getting closer
      to merge worthy ;)
      After noticing some code in mm/filemap.c accidentally perform a __GFP_FS
      allocation when it should not have been, I thought it might be a good idea to
      try to catch this kind of thing with lockdep.
      I coded up a little idea that seems to work. Unfortunately the system has to
      actually be in __GFP_FS page reclaim, then take the lock, before it will mark
      it. But at least that might still be some orders of magnitude more common
      (and more debuggable) than an actual deadlock condition, so we have some
      improvement I hope (the concept is no less complete than discovery of a lock's
      interrupt contexts).
      I guess we could even do the same thing with __GFP_IO (normal reclaim), and
      even GFP_NOIO locks too... but filesystems will have the most locks and fiddly
      code paths, so let's start there and see how it goes.
      It *seems* to work. I did a quick test.
      [ INFO: inconsistent lock state ]
      2.6.28-rc6-00007-ged313489-dirty #26
      inconsistent {in-reclaim-W} -> {ov-reclaim-W} usage.
      modprobe/8526 [HC0[0]:SC0[0]:HE1:SE1] takes:
       (testlock){--..}, at: [<ffffffffa0020055>] brd_init+0x55/0x216 [brd]
      {in-reclaim-W} state was registered at:
        [<ffffffff80267bdb>] __lock_acquire+0x75b/0x1a60
        [<ffffffff80268f71>] lock_acquire+0x91/0xc0
        [<ffffffff8070f0e1>] mutex_lock_nested+0xb1/0x310
        [<ffffffffa002002b>] brd_init+0x2b/0x216 [brd]
        [<ffffffff8020903b>] _stext+0x3b/0x170
        [<ffffffff80272ebf>] sys_init_module+0xaf/0x1e0
        [<ffffffff8020c3fb>] system_call_fastpath+0x16/0x1b
        [<ffffffffffffffff>] 0xffffffffffffffff
      irq event stamp: 3929
      hardirqs last  enabled at (3929): [<ffffffff8070f2b5>] mutex_lock_nested+0x285/0x310
      hardirqs last disabled at (3928): [<ffffffff8070f089>] mutex_lock_nested+0x59/0x310
      softirqs last  enabled at (3732): [<ffffffff8061f623>] sk_filter+0x83/0xe0
      softirqs last disabled at (3730): [<ffffffff8061f5b6>] sk_filter+0x16/0xe0
      other info that might help us debug this:
      1 lock held by modprobe/8526:
       #0:  (testlock){--..}, at: [<ffffffffa0020055>] brd_init+0x55/0x216 [brd]
      stack backtrace:
      Pid: 8526, comm: modprobe Not tainted 2.6.28-rc6-00007-ged313489
      -dirty #26
      Call Trace:
       [<ffffffff80265483>] print_usage_bug+0x193/0x1d0
       [<ffffffff80266530>] mark_lock+0xaf0/0xca0
       [<ffffffff80266735>] mark_held_locks+0x55/0xc0
       [<ffffffffa0020000>] ? brd_init+0x0/0x216 [brd]
       [<ffffffff802667ca>] trace_reclaim_fs+0x2a/0x60
       [<ffffffff80285005>] __alloc_pages_internal+0x475/0x580
       [<ffffffff8070f29e>] ? mutex_lock_nested+0x26e/0x310
       [<ffffffffa0020000>] ? brd_init+0x0/0x216 [brd]
       [<ffffffffa002006a>] brd_init+0x6a/0x216 [brd]
       [<ffffffffa0020000>] ? brd_init+0x0/0x216 [brd]
       [<ffffffff8020903b>] _stext+0x3b/0x170
       [<ffffffff8070f8b9>] ? mutex_unlock+0x9/0x10
       [<ffffffff8070f83d>] ? __mutex_unlock_slowpath+0x10d/0x180
       [<ffffffff802669ec>] ? trace_hardirqs_on_caller+0x12c/0x190
       [<ffffffff80272ebf>] sys_init_module+0xaf/0x1e0
       [<ffffffff8020c3fb>] system_call_fastpath+0x16/0x1b
      Signed-off-by: default avatarNick Piggin <npiggin@suse.de>
      Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
  14. 13 Aug, 2008 1 commit
    • Ingo Molnar's avatar
      lockdep: build fix · d6672c50
      Ingo Molnar authored
       kernel/built-in.o: In function `lockdep_stats_show':
       lockdep_proc.c:(.text+0x3cb2f): undefined reference to `lockdep_count_forward_deps'
       kernel/built-in.o: In function `l_show':
       lockdep_proc.c:(.text+0x3d02b): undefined reference to `lockdep_count_forward_deps'
       lockdep_proc.c:(.text+0x3d047): undefined reference to `lockdep_count_backward_deps'
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
  15. 11 Aug, 2008 1 commit
    • 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>
  16. 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>
  17. 23 Jun, 2008 1 commit
  18. 20 Jun, 2008 1 commit
  19. 07 Dec, 2006 1 commit
  20. 13 Sep, 2006 1 commit
  21. 03 Jul, 2006 1 commit
    • Ingo Molnar's avatar
      [PATCH] lockdep: core · fbb9ce95
      Ingo Molnar authored
      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
      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:
      [bunk@stusta.de: cleanups]
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarArjan van de Ven <arjan@linux.intel.com>
      Signed-off-by: default avatarAdrian Bunk <bunk@stusta.de>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>