lockdep: add lock_class information to lock_chain and output it
PATCH 1/1 lockdep: add lock_class information to lock_chain and output it
This patch is not intended to be merged. Just hope it is useful for somebody want to investigate kernel locking behavior. The simple scripts attached with the mail can be used to draw class chain graph via graphviz.
Best Regards,
Huang Ying -------------------------------------------------------------> This patch records array of lock_class into lock_chain, and export lock_chain information via /proc/lockdep_chains.
It is based on x86/master branch of git-x86 tree, and has been tested on x86_64 platform.
--- include/linux/lockdep.h | 3 + kernel/lockdep.c | 38 +++++++++++++++++- kernel/lockdep_internals.h | 6 ++ kernel/lockdep_proc.c | 91 +++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 135 insertions(+), 3 deletions(-)
kernel/lockdep.c +35 -3
@@ -1463,7 +1463,14 @@ out_bug: }unsigned long nr_lock_chains; -static struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS ]; +struct lock_chain lock_chains[MAX_LOCKDEP_CHAINS ]; +atomic_t nr_chain_hlocks; +static u16 chain_hlocks[MAX_LOCKDEP_CHAIN_HLOCKS ]; + +struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i) +{ +return lock_classes + chain_hlocks[chain->base + i]; +}/* * Look up a dependency chain. If the key is not present yet then
@@ -1471,10 +1478,15 @@ static struct lock_chain lock_chains[MAX* validated. If the key is already hashed, return 0. * (On return with 1 graph_lock is held.) */ -static inline int lookup_chain_cache (u64 chain_key,struct lock_class *class) +static inline int lookup_chain_cache (struct task_struct *curr, +struct held_lock *hlock, +u64 chain_key) { +struct lock_class *class = hlock->class;struct list_head *hash_head =chainhashentry (chain_key);struct lock_chain *chain; +struct held_lock *hlock_curr, *hlock_next; +int i, j, n;if (DEBUG_LOCKS_WARN_ON (!irqs_disabled ()))return 0 ;
@@ -1522,6 +1534,26 @@ cache_hit: } chain = lock_chains + nr_lock_chains++; chain->chain_key = chain_key; + chain->irq_context = hlock->irq_context; +/* Find the first held_lock of current chain */ + hlock_next = hlock; +for (i = curr->lockdep_depth -1 ; i >=0 ; i--) { + hlock_curr = curr->held_locks + i; +if (hlock_curr->irq_context != hlock_next->irq_context) +break ; + hlock_next = hlock; + } + i++; + chain->depth = curr->lockdep_depth +1 - i; + n =atomic_add_return (chain->depth, &nr_chain_hlocks); +if (unlikely (n <MAX_LOCKDEP_CHAIN_HLOCKS )) { + chain->base = n - chain->depth; +for (j =0 ; j < chain->depth -1 ; j++, i++) { +int lock_id = curr->held_locks[i].class - lock_classes; + chain_hlocks[chain->base + j] = lock_id; + } + chain_hlocks[chain->base + j] = class - lock_classes; + }list_add_tail_rcu (&chain->entry, hash_head);debug_atomic_inc (&chain_lookup_misses);inc_chains ();
@@ -1543,7 +1575,7 @@ static int validate_chain(struct task_st* graph_lock for us) */ if (!hlock->trylock && (hlock->check ==2 ) && -lookup_chain_cache (chain_key, hlock->class)) { +lookup_chain_cache (curr, hlock, chain_key)) {/* * Check whether last held lock: *
include/linux/lockdep.h +3 -0
@@ -182,6 +182,9 @@ struct lock_list {* We record lock dependency chains, so that we can cache them: */ struct lock_chain { +u8 irq_context; +u8 depth; +u16 base;struct list_head entry;u64 chain_key; };
kernel/lockdep_proc.c +91 -0
109 lines not on this page · raw message
kernel/lockdep_internals.h +6 -0
@@ -23,6 +23,8 @@#define MAX_LOCKDEP_CHAINS_BITS 14#define MAX_LOCKDEP_CHAINS (1UL << MAX_LOCKDEP_CHAINS_BITS) +#define MAX_LOCKDEP_CHAIN_HLOCKS (MAX_LOCKDEP_CHAINS*5) +/* * Stack-trace: tightly packed array of stack backtrace * addresses. Protected by the hash_lock.
@@ -30,15 +32,19 @@#define MAX_STACK_TRACE_ENTRIES 262144ULextern struct list_head all_lock_classes; +extern struct lock_chain lock_chains[];extern void get_usage_chars (struct lock_class *class,char *c1,char *c2,char *c3,char *c4);extern const char *__get_key_name (struct lockdep_subclass_key *key,char *str); +struct lock_class *lock_chain_get_class (struct lock_chain *chain,int i); +extern unsigned long nr_lock_classes;extern unsigned long nr_list_entries;extern unsigned long nr_lock_chains; +extern atomic_t nr_chain_hlocks;extern unsigned long nr_stack_trace_entries;extern unsigned int nr_hardirq_chains;
#!/usr/bin/python
import sys
import re
def dot_label(lc_name):
return lc_name.replace('>', r'\>')class lock_class(object):
def __init__(self, m):
object.__init__(self)
(key, nfd, nbd, usage, name) = m.groups()
self.key = key
self.nfd = int(nfd)
self.nbd = int(nbd)
self.usage = usage
self.name = name
self.fdks = set()
self.fds = []
self.bds = []
def append_fdk(self, fdk):
self.fdks.add(fdk)
def append_fd(self, fd):
self.fds.append(fd)
def append_bd(self, bd):
self.bds.append(bd)
def resolve_fd(self, lc_map):
for fdk in self.fdks:
if not lc_map.has_key(fdk):
print >> sys.stderr, 'WARNING: not lock_class for %s' % (fdk,) continue
lc = lc_map[fdk]
self.append_fd(lc)
lc.append_bd(self)
class lockdep(object):
re_lock_fd = re.compile(r'^ -> \[([a-f0-9]+)\] (\S+)\s*$') re_lock_class = re.compile(r'^([a-f0-9]+) FD:\s*(\d+) ' +
r'BD:\s*(\d+) (....): (\S+)\s*$')
def __init__(self):
object.__init__(self)
self.lock_classes = {}
def parse(self, f):
lc = None
for l in f:
mlc = lockdep.re_lock_class.match(l)
if mlc:
lc = lock_class(mlc) self.lock_classes[lc.key] = lc continue
mfd = lockdep.re_lock_fd.match(l)
if (mfd):
lc.append_fdk(mfd.group(1))
for lc in self.lock_classes.values():
lc.resolve_fd(self.lock_classes)
def dump_dot(self, fout, lc):
touched = set()
fout.write('''digraph Lockdep {
rankdir = LR ;
node [ shape = record, fontname = Courier ] ;
''')
def do_dump(lc):
fout.write('%s [ label="%s$%s" ] ;\n' % \
(lc.key, dot_label(lc.name), dot_label(lc.usage)))
touched.add(lc.key)
for fd in lc.fds:
fout.write('"%s" -> "%s" ;\n' % (lc.key, fd.key))
if fd.key not in touched:
do_dump(fd)
do_dump(lc)
fout.write('}\n')
def dump_dots(self, prefix):
n = 0
for lc in self.lock_classes.values():
if len(lc.bds) == 0:
fout = file('%s-%d.dot' % (prefix, n), 'w')
n = n + 1
self.dump_dot(fout, lc)
def dump_chains(self, fout):
def do_dump(lc, stack):
if len(lc.fds) == 0:
for l in stack:
fout.write('%s : ' % (l.name,))
fout.write('%s\n' % (lc.name,))
return
stack.append(lc)
for fd in lc.fds:
do_dump(fd, stack)
del stack[-1]
for lc in self.lock_classes.values():
if len(lc.bds) == 0:
do_dump(lc, [])
def dump(self):
for lc in self.lock_classes.values():
print lc.name, lc.fdsclass lock_chain(object):
def __init__(self, ic, lcs):
object.__init__(self)
self.irq_context = ic
self.class_keys = lcs[:]
self.classes = []
def resolve_class(self, lc_map):
for k in self.class_keys:
c = lc_map[k]
self.classes.append(c)
def add_to_tree(self, trees):
def classes_add_to_tree(classes, tree_node):
if len(classes) == 0:
return
lc = classes[0]
if not tree_node.children.has_key(lc.key):
tree_node.children[lc.key] = lch_tree_node(lc)
classes_add_to_tree(classes[1:], tree_node.children[lc.key])
classes_add_to_tree(self.classes, trees)
def dump(self, fout):
fout.write('ic = %d: ' % (self.irq_context,))
for c in self.classes:
fout.write('%s,' % (c.name,))
fout.write('\n')
class lch_tree_node(object):
next_id = 0
def __init__(self, lc):
object.__init__(self)
self.cls = lc
self.children = {}
self.id = lch_tree_node.next_id
lch_tree_node.next_id = lch_tree_node.next_id + 1class lock_chains(object):
re_lch_head = re.compile(r'^irq_context: (\d)$') re_lch_class = re.compile(r'\[([a-f0-9]+)\]\s*(\S+)\s*$')
def __init__(self, lockdep):
object.__init__(self)
self.lockdep = lockdep
self.chains = []
self.lch_trees = lch_tree_node(None)
def parse(self, f):
ic = 0
lcs = []
for l in f:
mc = lock_chains.re_lch_class.match(l)
if mc:
lcs.append(mc.group(1))
mh = lock_chains.re_lch_head.match(l)
if mh:
ic = int(mh.group(1))
if len(lcs) != 0:
lch = lock_chain(ic, lcs) self.chains.append(lch)
lcs = []
lc_map = self.lockdep.lock_classes
for ch in self.chains:
ch.resolve_class(lc_map)
self.build_tree()
def build_tree(self):
trees = self.lch_trees
for ch in self.chains:
ch.add_to_tree(trees)
def dump(self, fout):
for ch in self.chains:
ch.dump(fout)
def dump_tree_dot(self, fout, root):
fout.write('''digraph Lockdep {
rankdir = LR ;
node [ shape = record, fontname = Courier ] ;
''')
def do_dump(node, parent):
lc = node.cls
fout.write('%d [ label = "%s" ] ;\n' %
(node.id, dot_label(lc.name)))
if parent:
fout.write('"%d" -> "%d" ;\n' % (parent.id, node.id))
children = sorted(node.children.values(), None,
lambda n: n.cls.name)
for child in children:
do_dump(child, node)
do_dump(root, None)
fout.write('}\n')
def dump_trees_dot(self, prefix):
n = 0
for lch_root in self.lch_trees.children.values():
fout = file('%s-%d.dot' % (prefix, n), 'w')
n = n + 1
self.dump_tree_dot(fout, lch_root)
def test(fin):
ld = lockdep()
ld.parse(fin)
ld.dump_dots('out/lockdep')
def test2(fin):
ld = lockdep()
ld.parse(fin)
lc = ld.lock_classes['ffff81000108eae0']
ld.dump_dot(file('out/a.dot', 'w'), lc)def test3(fin, fout):
ld = lockdep()
ld.parse(fin)
ld.dump_chains(fout)
def test4():
ld = lockdep()
ld.parse(file('lockdep'))
lchs = lock_chains(ld)
lchs.parse(file('lockdep_chains'))
#lchs.dump(sys.stdout)
lchs.dump_trees_dot('out/lch')
if __name__ == '__main__':
test4()
Quoted 4 lines · Huang, Ying
This patch is not intended to be merged. Just hope it is useful for somebody want to investigate kernel locking behavior. The simple scripts attached with the mail can be used to draw class chain graph via graphviz.
hm, that looks pretty nice. Why not merge it? You could make it depend on LOCKDEP_DEBUG perhaps, if kernel size/performance is an issue.
Ingo
FYI, the patch has some build problems:
kernel/built-in.o: In function `lc_next':
lockdep_proc.c:(.text+0x31c83): undefined reference to nr_lock_chains' lockdep_proc.c:(.text+0x31cb1): undefined reference to lock_chains' kernel/built-in.o: In function `lc_start':
lockdep_proc.c:(.text+0x31cf4): undefined reference to nr_lock_chains' lockdep_proc.c:(.text+0x31d08): undefined reference to lock_chains' kernel/built-in.o: In function `lockdep_chains_open':
lockdep_proc.c:(.text+0x31e59): undefined reference to `nr_lock_chains'
with this config:
http://redhat.com/~mingo/misc/config-Fri_Jun_20_12_29_35_CEST_2008.bad
Ingo