linux-toradex.git/kernel/lockdep_internals.h, branch v2.6.32.2

lockdep: BFS cleanup

2009-07-24T08:53:29+00:00

Some cleanups of the lockdep code after the BFS series:

 - Remove the last traces of the generation id
 - Fixup comment style
 - Move the bfs routines into lockdep.c
 - Cleanup the bfs routines

[ tom.leiming@gmail.com: Fix crash ]
Signed-off-by: Peter Zijlstra 
LKML-Reference: <1246201486-7308-11-git-send-email-tom.leiming@gmail.com>
Signed-off-by: Ingo Molnar

lockdep: Add statistics info for max bfs queue depth

2009-07-24T08:52:03+00:00

Add BFS statistics to the existing lockdep stats.

Signed-off-by: Ming Lei 
Signed-off-by: Peter Zijlstra 
LKML-Reference: <1246201486-7308-10-git-send-email-tom.leiming@gmail.com>
Signed-off-by: Ingo Molnar

lockdep: Introduce print_shortest_lock_dependencies

2009-07-24T08:49:54+00:00

Since the shortest lock dependencies' path may be obtained by BFS,
we print the shortest one by print_shortest_lock_dependencies().

Signed-off-by: Ming Lei 
Signed-off-by: Peter Zijlstra 
LKML-Reference: <1246201486-7308-7-git-send-email-tom.leiming@gmail.com>
Signed-off-by: Ingo Molnar

lockdep: Improve implementation of BFS

2009-07-24T08:49:46+00:00

1,replace %MAX_CIRCULAR_QUE_SIZE with &(MAX_CIRCULAR_QUE_SIZE-1)
since we define MAX_CIRCULAR_QUE_SIZE as power of 2;

2,use bitmap to mark if a lock is accessed in BFS in order to
clear it quickly, because we may search a graph many times.

Signed-off-by: Ming Lei 
Signed-off-by: Peter Zijlstra 
LKML-Reference: <1246201486-7308-3-git-send-email-tom.leiming@gmail.com>
Signed-off-by: Ingo Molnar

lockdep: Print the shortest dependency chain if finding a circle

2009-07-24T08:49:44+00:00

Currently lockdep will print the 1st circle detected if it
exists when acquiring a new (next) lock.

This patch prints the shortest path from the next lock to be
acquired to the previous held lock if a circle is found.

The patch still uses the current method to check circle, and
once the circle is found, breadth-first search algorithem is
used to compute the shortest path from the next lock to the
previous lock in the forward lock dependency graph.

Printing the shortest path will shorten the dependency chain,
and make troubleshooting for possible circular locking easier.

Signed-off-by: Ming Lei 
Signed-off-by: Peter Zijlstra 
LKML-Reference: <1246201486-7308-2-git-send-email-tom.leiming@gmail.com>
Signed-off-by: Ingo Molnar

lockdep: increase MAX_LOCKDEP_ENTRIES and MAX_LOCKDEP_CHAINS

2009-05-12T17:59:52+00:00

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]  [] add_lock_to_list+0x53/0xba
[   21.402007]  [] ? lookup_mnt+0x19/0x53
[   21.402007]  [] check_prev_add+0x14b/0x1c7
[   21.402007]  [] validate_chain+0x474/0x52a
[   21.402007]  [] __lock_acquire+0x342/0x3c7
[   21.402007]  [] lock_acquire+0xc1/0xe5
[   21.402007]  [] ? lookup_mnt+0x19/0x53
[   21.402007]  [] _spin_lock+0x31/0x66

Double the size - as we've done in the past.

[ Impact: allow lockdep to cover more locks ]

Acked-by: Peter Zijlstra 
LKML-Reference: 
Signed-off-by: Ingo Molnar

lockdep: get_user_chars() redo

2009-02-14T22:28:22+00:00

Generic, states independent, get_user_chars().

Signed-off-by: Peter Zijlstra 
Signed-off-by: Ingo Molnar

lockdep: generate the state bit definitions

2009-02-14T22:28:01+00:00

Generate the state bit definitions from the lockdep_states.h file.

Also, move LOCK_USED to last, so that the

 USED_IN
 USED_IN_READ
 ENABLED
 ENABLED_READ

states are nicely bit aligned -- we're going to use that property

Signed-off-by: Peter Zijlstra 
Signed-off-by: Ingo Molnar

lockdep: move state bit definitions around

2009-02-14T22:27:59+00:00

For convenience later.

Signed-off-by: Peter Zijlstra 
Signed-off-by: Ingo Molnar

lockdep: annotate reclaim context (__GFP_NOFS)

2009-02-14T22:27:49+00:00

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-ged31348-dirty #26
---------------------------------
inconsistent {in-reclaim-W} -> {ov-reclaim-W} usage.
modprobe/8526 [HC0[0]:SC0[0]:HE1:SE1] takes:
 (testlock){--..}, at: [] brd_init+0x55/0x216 [brd]
{in-reclaim-W} state was registered at:
  [] __lock_acquire+0x75b/0x1a60
  [] lock_acquire+0x91/0xc0
  [] mutex_lock_nested+0xb1/0x310
  [] brd_init+0x2b/0x216 [brd]
  [] _stext+0x3b/0x170
  [] sys_init_module+0xaf/0x1e0
  [] system_call_fastpath+0x16/0x1b
  [] 0xffffffffffffffff
irq event stamp: 3929
hardirqs last  enabled at (3929): [] mutex_lock_nested+0x285/0x310
hardirqs last disabled at (3928): [] mutex_lock_nested+0x59/0x310
softirqs last  enabled at (3732): [] sk_filter+0x83/0xe0
softirqs last disabled at (3730): [] sk_filter+0x16/0xe0

other info that might help us debug this:
1 lock held by modprobe/8526:
 #0:  (testlock){--..}, at: [] brd_init+0x55/0x216 [brd]

stack backtrace:
Pid: 8526, comm: modprobe Not tainted 2.6.28-rc6-00007-ged31348-dirty #26
Call Trace:
 [] print_usage_bug+0x193/0x1d0
 [] mark_lock+0xaf0/0xca0
 [] mark_held_locks+0x55/0xc0
 [] ? brd_init+0x0/0x216 [brd]
 [] trace_reclaim_fs+0x2a/0x60
 [] __alloc_pages_internal+0x475/0x580
 [] ? mutex_lock_nested+0x26e/0x310
 [] ? brd_init+0x0/0x216 [brd]
 [] brd_init+0x6a/0x216 [brd]
 [] ? brd_init+0x0/0x216 [brd]
 [] _stext+0x3b/0x170
 [] ? mutex_unlock+0x9/0x10
 [] ? __mutex_unlock_slowpath+0x10d/0x180
 [] ? trace_hardirqs_on_caller+0x12c/0x190
 [] sys_init_module+0xaf/0x1e0
 [] system_call_fastpath+0x16/0x1b

Signed-off-by: Nick Piggin 
Signed-off-by: Peter Zijlstra 
Signed-off-by: Ingo Molnar