1. 17 Oct, 2006 1 commit
    • Ingo Molnar's avatar
      [PATCH] lockdep: increase max allowed recursion depth · ca268c69
      Ingo Molnar authored
      
      
      In general, lockdep warnings are intended to be non-fatal, so I have put in
      various practical limits on internal data structure failure modes.  We haven't
      had a /single/ lockdep-internal crash ever since lockdep went upstream [the
      unwinder crashes are outside of lockdep], and that's largely due to the good
      internal checks it does.
      
      Recursion within the dependency graph is currently limited to 20, that's
      probably not enough on some many-CPU boxes - this patch doubles it to 40.  I
      have written the lockdep functions to have as small stackframes as possible,
      so 40 should be OK too.  (The practical recursion limit should be somewhere
      between 100 and 200 entries.  If we hit that then I'll change the algorithm to
      be iteration-based.  Graph walking logic is so easy to program via recursion,
      so i'd like to keep recursion as long as possible.)
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      ca268c69
  2. 11 Oct, 2006 2 commits
  3. 02 Oct, 2006 1 commit
    • Serge E. Hallyn's avatar
      [PATCH] namespaces: utsname: use init_utsname when appropriate · 96b644bd
      Serge E. Hallyn authored
      
      
      In some places, particularly drivers and __init code, the init utsns is the
      appropriate one to use.  This patch replaces those with a the init_utsname
      helper.
      
      Changes: Removed several uses of init_utsname().  Hope I picked all the
      	right ones in net/ipv4/ipconfig.c.  These are now changed to
      	utsname() (the per-process namespace utsname) in the previous
      	patch (2/7)
      
      [akpm@osdl.org: CIFS fix]
      Signed-off-by: default avatarSerge E. Hallyn <serue@us.ibm.com>
      Cc: Kirill Korotaev <dev@openvz.org>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Cc: Herbert Poetzl <herbert@13thfloor.at>
      Cc: Andrey Savochkin <saw@sw.ru>
      Cc: Serge Hallyn <serue@us.ibm.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      96b644bd
  4. 29 Sep, 2006 2 commits
    • Ingo Molnar's avatar
      [PATCH] lockdep core: improve the lock-chain-hash · 03cbc358
      Ingo Molnar authored
      
      
      With CONFIG_DEBUG_LOCK_ALLOC turned off i was getting sporadic failures in
      the locking self-test:
      
        ------------>
        | Locking API testsuite:
        ----------------------------------------------------------------------------
                                         | spin |wlock |rlock |mutex | wsem | rsem |
          --------------------------------------------------------------------------
                             A-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                         A-B-B-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                     A-B-B-C-C-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                     A-B-C-A-B-C deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                 A-B-B-C-C-D-D-A deadlock:  ok  |FAILED|  ok  |  ok  |  ok  |  ok  |
                 A-B-C-D-B-D-D-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |  ok  |
                 A-B-C-D-B-C-D-A deadlock:  ok  |  ok  |  ok  |  ok  |  ok  |FAILED|
      
      after much debugging it turned out to be caused by accidental chain-hash
      key collisions.  The current hash is:
      
       #define iterate_chain_key(key1, key2) \
      	(((key1) << MAX_LOCKDEP_KEYS_BITS/2) ^ \
      	((key1) >> (64-MAX_LOCKDEP_KEYS_BITS/2)) ^ \
       	(key2))
      
      where MAX_LOCKDEP_KEYS_BITS is 11.  This hash is pretty good as it will
      shift by 5 bits in every iteration, where every new ID 'mixed' into the
      hash would have up to 11 bits.  But because there was a 6 bits overlap
      between subsequent IDs and their high bits tended to be similar, there was
      a chance for accidental chain-hash collision for a low number of locks
      held.
      
      the solution is to shift by 11 bits:
      
       #define iterate_chain_key(key1, key2) \
      	(((key1) << MAX_LOCKDEP_KEYS_BITS) ^ \
      	((key1) >> (64-MAX_LOCKDEP_KEYS_BITS)) ^ \
       	(key2))
      
      This keeps the hash perfect up to 5 locks held, but even above that the
      hash is still good because 11 bits is a relative prime to the total 64
      bits, so a complete match will only occur after 64 held locks (which doesnt
      happen in Linux).  Even after 5 locks held, entropy of the 5 IDs mixed into
      the hash is already good enough so that overlap doesnt generate a colliding
      hash ID.
      
      with this change the false positives went away.
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      03cbc358
    • Dave Jones's avatar
      [PATCH] lockdep: print kernel version · 99de055a
      Dave Jones authored
      
      
      Lets do the same thing we do for oopses - print out the version in the
      report.  It's an extra line of output though.  We could tack it on the end
      of the INFO: lines, but that screws up Ingo's pretty output.
      Signed-off-by: default avatarDave Jones <davej@redhat.com>
      Cc: Ingo Molnar <mingo@elte.hu>
      Cc: Arjan van de Ven <arjan@linux.intel.com>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      99de055a
  5. 26 Sep, 2006 2 commits
  6. 10 Jul, 2006 3 commits
  7. 03 Jul, 2006 2 commits
    • Ingo Molnar's avatar
      [PATCH] lockdep: allow read_lock() recursion of same class · 6c9076ec
      Ingo Molnar authored
      
      
      From: Ingo Molnar <mingo@elte.hu>
      
      lockdep so far only allowed read-recursion for the same lock instance.
      This is enough in the overwhelming majority of cases, but a hostap case
      triggered and reported by Miles Lane relies on same-class
      different-instance recursion.  So we relax the restriction on read-lock
      recursion.
      
      (This change does not allow rwsem read-recursion, which is still
      forbidden.)
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
      6c9076ec
    • 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
      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: 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>
      fbb9ce95