* [PATCH] lockdep: add lock_class information to lock_chain and output it
@ 2008-06-20 8:39 Huang, Ying
2008-06-20 10:19 ` Ingo Molnar
0 siblings, 1 reply; 3+ messages in thread
From: Huang, Ying @ 2008-06-20 8:39 UTC (permalink / raw)
To: Peter Zijlstra, Ingo Molnar; +Cc: linux-kernel
[-- Attachment #1: Type: text/plain, Size: 7340 bytes --]
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.
Signed-off-by: Huang Ying <ying.huang@intel.com>
---
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(-)
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -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:
*
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -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;
};
--- a/kernel/lockdep_proc.c
+++ b/kernel/lockdep_proc.c
@@ -178,6 +178,93 @@ static const struct file_operations proc
.release = seq_release,
};
+static void *lc_next(struct seq_file *m, void *v, loff_t *pos)
+{
+ struct lock_chain *chain;
+
+ (*pos)++;
+
+ if (v == SEQ_START_TOKEN)
+ chain = m->private;
+ else {
+ chain = v;
+
+ if (*pos < nr_lock_chains)
+ chain = lock_chains + *pos;
+ else
+ chain = NULL;
+ }
+
+ return chain;
+}
+
+static void *lc_start(struct seq_file *m, loff_t *pos)
+{
+ if (*pos == 0)
+ return SEQ_START_TOKEN;
+
+ if (*pos < nr_lock_chains)
+ return lock_chains + *pos;
+
+ return NULL;
+}
+
+static void lc_stop(struct seq_file *m, void *v)
+{
+}
+
+static int lc_show(struct seq_file *m, void *v)
+{
+ struct lock_chain *chain = v;
+ struct lock_class *class;
+ int i;
+
+ if (v == SEQ_START_TOKEN) {
+ seq_printf(m, "all lock chains:\n");
+ return 0;
+ }
+
+ seq_printf(m, "irq_context: %d\n", chain->irq_context);
+
+ for (i = 0; i < chain->depth; i++) {
+ class = lock_chain_get_class(chain, i);
+ seq_printf(m, "[%p] ", class->key);
+ print_name(m, class);
+ seq_puts(m, "\n");
+ }
+ seq_puts(m, "\n");
+
+ return 0;
+}
+
+static const struct seq_operations lockdep_chains_ops = {
+ .start = lc_start,
+ .next = lc_next,
+ .stop = lc_stop,
+ .show = lc_show,
+};
+
+static int lockdep_chains_open(struct inode *inode, struct file *file)
+{
+ int res = seq_open(file, &lockdep_chains_ops);
+ if (!res) {
+ struct seq_file *m = file->private_data;
+
+ if (nr_lock_chains)
+ m->private = lock_chains;
+ else
+ m->private = NULL;
+ }
+ return res;
+}
+
+static const struct file_operations proc_lockdep_chains_operations = {
+ .open = lockdep_chains_open,
+ .read = seq_read,
+ .llseek = seq_lseek,
+ .release = seq_release,
+};
+
static void lockdep_stats_debug_show(struct seq_file *m)
{
#ifdef CONFIG_DEBUG_LOCKDEP
@@ -294,6 +381,8 @@ static int lockdep_stats_show(struct seq
#ifdef CONFIG_PROVE_LOCKING
seq_printf(m, " dependency chains: %11lu [max: %lu]\n",
nr_lock_chains, MAX_LOCKDEP_CHAINS);
+ seq_printf(m, " dependency chain hlocks: %11d [max: %lu]\n",
+ atomic_read(&nr_chain_hlocks), MAX_LOCKDEP_CHAIN_HLOCKS);
#endif
#ifdef CONFIG_TRACE_IRQFLAGS
@@ -661,6 +750,8 @@ static const struct file_operations proc
static int __init lockdep_proc_init(void)
{
proc_create("lockdep", S_IRUSR, NULL, &proc_lockdep_operations);
+ proc_create("lockdep_chains", S_IRUSR, NULL,
+ &proc_lockdep_chains_operations);
proc_create("lockdep_stats", S_IRUSR, NULL,
&proc_lockdep_stats_operations);
--- a/kernel/lockdep_internals.h
+++ b/kernel/lockdep_internals.h
@@ -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 262144UL
extern 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;
[-- Attachment #2: lockdep.py --]
[-- Type: text/x-python, Size: 6946 bytes --]
#!/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.fds
class 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 + 1
class 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()
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] lockdep: add lock_class information to lock_chain and output it
2008-06-20 8:39 [PATCH] lockdep: add lock_class information to lock_chain and output it Huang, Ying
@ 2008-06-20 10:19 ` Ingo Molnar
2008-06-20 10:37 ` Ingo Molnar
0 siblings, 1 reply; 3+ messages in thread
From: Ingo Molnar @ 2008-06-20 10:19 UTC (permalink / raw)
To: Huang, Ying; +Cc: Peter Zijlstra, linux-kernel
* Huang, Ying <ying.huang@intel.com> wrote:
> 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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] lockdep: add lock_class information to lock_chain and output it
2008-06-20 10:19 ` Ingo Molnar
@ 2008-06-20 10:37 ` Ingo Molnar
0 siblings, 0 replies; 3+ messages in thread
From: Ingo Molnar @ 2008-06-20 10:37 UTC (permalink / raw)
To: Huang, Ying; +Cc: Peter Zijlstra, linux-kernel
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
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2008-06-20 10:37 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2008-06-20 8:39 [PATCH] lockdep: add lock_class information to lock_chain and output it Huang, Ying
2008-06-20 10:19 ` Ingo Molnar
2008-06-20 10:37 ` Ingo Molnar
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox