[PATCH] lockdep: add lock_class information to lock_chain andoutput it

[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.

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@xxxxxxxxx>

---
 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;

#!/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()