Re: [PATCH 0/8] kernel:lockdep:replace DFS with BFS
From: Ming Lei
Date: Mon Jun 08 2009 - 09:39:01 EST
2009/6/8 Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>:
>
> OK, so I applied the patches and the cleanup below.
Thank you for your review and feedback.
>
> mostly little style nits and moving the circular queue into lockdep.c
> (nobody else uses it, so why share it?).
Yes, I agree.
>
> One thing though, macros with return statements?! that's seriously bad
> style, don't do that.
Yes, I'll fix it.
>
> One thing that worries me a little is that we loose DaveM's
> lockdep_dependency_visit() optimization. My brain seems unwilling to
> co-operate on determining if BFS would make that redundant, so a little
> word on that would be appreciated.
>
> Then I booted it and all hell broke loose, so either I wrecked something
> or you did :-), would you terribly mind poking at that a little?
Oh, let me work out what's wrong with this, maybe I need a little time.
>
> Over all I like that patches, but they need a little more work. Could
> you send delta patches from now on?
Yes, I'd like to do it.
>
> ---
>
> [ 0.000999] =================================
> [ 0.000999] [ BUG: bad contention detected! ]
> [ 0.000999] ---------------------------------
> [ 0.000999] swapper/0 is trying to contend lock (old_style_seqlock_init) at:
> [ 0.000999] [<ffffffff8133a795>] _spin_lock+0x6d/0x75
> [ 0.000999] but there are no locks held!
> [ 0.000999]
> [ 0.000999] other info that might help us debug this:
> [ 0.000999] 1 lock held by swapper/0:
> [ 0.000999] #0: (xtime_lock){-.....}, at: [<ffffffff8106a360>] tick_periodic+0x1d/0x74
> [ 0.000999]
> [ 0.000999] stack backtrace:
> [ 0.000999] Pid: 0, comm: swapper Not tainted 2.6.30-rc8-tip #1049
> [ 0.000999] Call Trace:
> [ 0.000999] <IRQ> [<ffffffff81071bd8>] print_lock_contention_bug+0x100/0x110
> [ 0.000999] [<ffffffff81071ce0>] lock_acquired+0xf8/0x2b4
> [ 0.000999] [<ffffffff81010221>] ? update_vsyscall+0x2d/0xd0
> [ 0.000999] [<ffffffff8133a795>] _spin_lock+0x6d/0x75
> [ 0.000999] [<ffffffff81010221>] ? update_vsyscall+0x2d/0xd0
> [ 0.000999] [<ffffffff81010221>] update_vsyscall+0x2d/0xd0
> [ 0.000999] [<ffffffff81067469>] update_wall_time+0x4c1/0x4cc
> [ 0.000999] [<ffffffff8105274b>] do_timer+0x15/0x1c
> [ 0.000999] [<ffffffff8106a37e>] tick_periodic+0x3b/0x74
> [ 0.000999] [<ffffffff8106a3db>] tick_handle_periodic+0x24/0x71
> [ 0.000999] [<ffffffff8100ea23>] timer_interrupt+0x1f/0x26
> [ 0.000999] [<ffffffff8109348b>] handle_IRQ_event+0x8e/0x19c
> [ 0.000999] [<ffffffff8109501e>] handle_level_irq+0x9d/0xf3
> [ 0.000999] [<ffffffff8100e24b>] handle_irq+0x24/0x2c
> [ 0.000999] [<ffffffff8133f55b>] do_IRQ+0x63/0xc2
> [ 0.000999] [<ffffffff8100c713>] ret_from_intr+0x0/0xf
> [ 0.000999] <EOI> [<ffffffff8133a538>] ? _spin_unlock_irqrestore+0x47/0x6d
> [ 0.000999] [<ffffffff81093eea>] ? __setup_irq+0x1ea/0x277
> [ 0.000999] [<ffffffff81094120>] ? setup_irq+0x25/0x2a
> [ 0.000999] [<ffffffff8158e63e>] ? hpet_time_init+0x20/0x22
> [ 0.000999] [<ffffffff8158bbcc>] ? start_kernel+0x2ee/0x37a
> [ 0.000999] [<ffffffff8158b29a>] ? x86_64_start_reservations+0xaa/0xae
> [ 0.000999] [<ffffffff8158b37f>] ? x86_64_start_kernel+0xe1/0xe8
>
> And ended in a stuck boot at:
>
> [ 65.411804] rmmod R running task 0 616 1 0x00000008
> [ 65.411804] ffff8800023c41a0 ffffea0003336ba8 ffff88007e3a3c08 ffffffff8106f71a
> [ 65.411804] ffff88007e3a3c48 0000000000000202 ffff88007f821600 0000000000001823
> [ 65.411804] ffff88007e109d20 ffff88007f8b5c80 0000000000000000 ffff88007e3a3d18
> [ 65.411804] Call Trace:
> [ 65.411804] [<ffffffff8106f71a>] ? trace_hardirqs_on+0xd/0xf
> [ 65.411804] [<ffffffff8113f1b6>] ? release_sysfs_dirent+0x91/0xb1
> [ 65.411804] [<ffffffff81071af6>] ? print_lock_contention_bug+0x1e/0x110
> [ 65.411804] [<ffffffff81071af6>] ? print_lock_contention_bug+0x1e/0x110
> [ 65.411804] [<ffffffff8113eff3>] ? sysfs_addrm_start+0x7d/0xaa
> [ 65.411804] [<ffffffff81071af6>] ? print_lock_contention_bug+0x1e/0x110
> [ 65.411804] [<ffffffff810113ff>] ? alternatives_smp_module_del+0x37/0xd0
> [ 65.411804] [<ffffffff810e61ee>] ? free_percpu+0x38/0xf8
> [ 65.411804] [<ffffffff8106f71a>] ? trace_hardirqs_on+0xd/0xf
> [ 65.411804] [<ffffffff8133a542>] ? _spin_unlock_irqrestore+0x51/0x6d
> [ 65.411804] [<ffffffff810e62a5>] ? free_percpu+0xef/0xf8
> [ 65.411804] [<ffffffff8107ade5>] ? free_module+0x104/0x118
> [ 65.411804] [<ffffffff8107b0a8>] ? sys_delete_module+0x20c/0x22e
> [ 65.411804] [<ffffffff81339f88>] ? trace_hardirqs_on_thunk+0x3a/0x3f
> [ 65.411804] [<ffffffff8100bcdb>] ? system_call_fastpath+0x16/0x1b
>
> ( I can send you my .config if you cannot reproduce, but I don't think
> its anything special )
>
> ---
>
> Subject: lockdep: clean up after BFS patches
> From: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
> Date: Mon Jun 08 13:32:31 CEST 2009
>
>
> LKML-Reference: <new-submission>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
> ---
> include/linux/lockdep.h | 7 -
> kernel/lockdep.c | 232 +++++++++++++++++++++++++++------------------
> kernel/lockdep_internals.h | 97 ------------------
> 3 files changed, 147 insertions(+), 189 deletions(-)
> ===================================================================
> ===================================================================
> --- linux-2.6.orig/include/linux/lockdep.h
> +++ linux-2.6/include/linux/lockdep.h
> @@ -58,7 +58,6 @@ struct lock_class {
>
> struct lockdep_subclass_key *key;
> unsigned int subclass;
> - unsigned int dep_gen_id;
>
> /*
> * IRQ/softirq usage tracking bits:
> @@ -150,9 +149,9 @@ struct lock_list {
> struct stack_trace trace;
> int distance;
>
> - /*The parent field is used to implement breadth-first search,and
> - *the bit 0 is reused to indicate if the lock has been accessed
> - *in BFS.
> + /*
> + * The parent field is used to implement breadth-first search, and the
> + * bit 0 is reused to indicate if the lock has been accessed in BFS.
> */
> struct lock_list *parent;
> };
> ===================================================================
> --- linux-2.6.orig/kernel/lockdep.c
> +++ linux-2.6/kernel/lockdep.c
> @@ -43,6 +43,7 @@
> #include <linux/ftrace.h>
> #include <linux/stringify.h>
> #include <linux/bitops.h>
> +
> #include <asm/sections.h>
>
> #include "lockdep_internals.h"
> @@ -118,7 +119,7 @@ static inline int debug_locks_off_graph_
> static int lockdep_initialized;
>
> unsigned long nr_list_entries;
> -struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
> +static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
>
> /*
> * All data structures here are protected by the global debug_lock.
> @@ -390,19 +391,6 @@ unsigned int nr_process_chains;
> unsigned int max_lockdep_depth;
> unsigned int max_recursion_depth;
>
> -static unsigned int lockdep_dependency_gen_id;
> -
> -static bool lockdep_dependency_visit(struct lock_class *source,
> - unsigned int depth)
> -{
> - if (!depth)
> - lockdep_dependency_gen_id++;
> - if (source->dep_gen_id == lockdep_dependency_gen_id)
> - return true;
> - source->dep_gen_id = lockdep_dependency_gen_id;
> - return false;
> -}
> -
> #ifdef CONFIG_DEBUG_LOCKDEP
> /*
> * We cannot printk in early bootup code. Not even early_printk()
> @@ -575,64 +563,6 @@ static void print_lock_class_header(stru
> print_ip_sym((unsigned long)class->key);
> }
>
> -/*
> - * printk the shortest lock dependencies from @start to @end in reverse order:
> - */
> -static void __used
> -print_shortest_lock_dependencies(struct lock_list *leaf,
> - struct lock_list *root)
> -{
> - struct lock_list *entry = leaf;
> - int depth;
> -
> - /*compute depth from generated tree by BFS*/
> - depth = get_lock_depth(leaf);
> -
> - do {
> - print_lock_class_header(entry->class, depth);
> - printk("%*s ... acquired at:\n", depth, "");
> - print_stack_trace(&entry->trace, 2);
> - printk("\n");
> -
> - if (depth == 0 && (entry != root)) {
> - printk("lockdep:%s bad BFS generated tree\n", __func__);
> - break;
> - }
> -
> - entry = get_lock_parent(entry);
> - depth--;
> - } while (entry && (depth >= 0));
> -
> - return;
> -}
> -/*
> - * printk all lock dependencies starting at <entry>:
> - */
> -static void __used
> -print_lock_dependencies(struct lock_class *class, int depth)
> -{
> - struct lock_list *entry;
> -
> - if (lockdep_dependency_visit(class, depth))
> - return;
> -
> - if (DEBUG_LOCKS_WARN_ON(depth >= 20))
> - return;
> -
> - print_lock_class_header(class, depth);
> -
> - list_for_each_entry(entry, &class->locks_after, entry) {
> - if (DEBUG_LOCKS_WARN_ON(!entry->class))
> - return;
> -
> - print_lock_dependencies(entry->class, depth + 1);
> -
> - printk("%*s ... acquired at:\n",depth,"");
> - print_stack_trace(&entry->trace, 2);
> - printk("\n");
> - }
> -}
> -
> static void print_kernel_version(void)
> {
> printk("%s %.*s\n", init_utsname()->release,
> @@ -927,14 +857,106 @@ static int add_lock_to_list(struct lock_
> return 1;
> }
>
> -unsigned long bfs_accessed[BITS_TO_LONGS(MAX_LOCKDEP_ENTRIES)];
> -static struct circular_queue lock_cq;
> +/*For good efficiency of modular, we use power of 2*/
> +#define MAX_CIRCULAR_QUEUE_SIZE 4096UL
> +#define CQ_MASK (MAX_CIRCULAR_QUEUE_SIZE-1)
> +
> +/* The circular_queue and helpers is used to implement the
> + * breadth-first search(BFS)algorithem, by which we can build
> + * the shortest path from the next lock to be acquired to the
> + * previous held lock if there is a circular between them.
> + * */
> +struct circular_queue {
> + unsigned long element[MAX_CIRCULAR_QUEUE_SIZE];
> + unsigned int front, rear;
> +};
> +
> +static struct circular_queue lock_cq;
> +static unsigned long bfs_accessed[BITS_TO_LONGS(MAX_LOCKDEP_ENTRIES)];
> +
> unsigned int max_bfs_queue_depth;
> +
> +static inline void __cq_init(struct circular_queue *cq)
> +{
> + cq->front = cq->rear = 0;
> + bitmap_zero(bfs_accessed, MAX_LOCKDEP_ENTRIES);
> +}
> +
> +static inline int __cq_empty(struct circular_queue *cq)
> +{
> + return (cq->front == cq->rear);
> +}
> +
> +static inline int __cq_full(struct circular_queue *cq)
> +{
> + return ((cq->rear + 1) & CQ_MASK) == cq->front;
> +}
> +
> +static inline int __cq_enqueue(struct circular_queue *cq, unsigned long elem)
> +{
> + if (__cq_full(cq))
> + return -1;
> +
> + cq->element[cq->rear] = elem;
> + cq->rear = (cq->rear + 1) & CQ_MASK;
> + return 0;
> +}
> +
> +static inline int __cq_dequeue(struct circular_queue *cq, unsigned long *elem)
> +{
> + if (__cq_empty(cq))
> + return -1;
> +
> + *elem = cq->element[cq->front];
> + cq->front = (cq->front + 1) & CQ_MASK;
> + return 0;
> +}
> +
> +static inline unsigned int __cq_get_elem_count(struct circular_queue *cq)
> +{
> + return (cq->rear - cq->front) & CQ_MASK;
> +}
> +
> +static inline void mark_lock_accessed(struct lock_list *lock,
> + struct lock_list *parent)
> +{
> + unsigned long nr;
> + nr = lock - list_entries;
> + WARN_ON(nr >= nr_list_entries);
> + lock->parent = parent;
> + set_bit(nr, bfs_accessed);
> +}
> +
> +static inline unsigned long lock_accessed(struct lock_list *lock)
> +{
> + unsigned long nr;
> + nr = lock - list_entries;
> + WARN_ON(nr >= nr_list_entries);
> + return test_bit(nr, bfs_accessed);
> +}
> +
> +static inline struct lock_list *get_lock_parent(struct lock_list *child)
> +{
> + return child->parent;
> +}
> +
> +static inline int get_lock_depth(struct lock_list *child)
> +{
> + int depth = 0;
> + struct lock_list *parent;
> +
> + while ((parent = get_lock_parent(child))) {
> + child = parent;
> + depth++;
> + }
> + return depth;
> +}
> +
> static int __bfs(struct lock_list *source_entry,
> - void *data,
> - int (*match)(struct lock_list *entry, void *data),
> - struct lock_list **target_entry,
> - int forward)
> + void *data,
> + int (*match)(struct lock_list *entry, void *data),
> + struct lock_list **target_entry,
> + int forward)
> {
> struct lock_list *entry;
> struct list_head *head;
> @@ -1202,14 +1224,6 @@ check_noncircular(struct lock_list *root
> * without creating any illegal irq-safe -> irq-unsafe lock dependency.
> */
>
> -
> -#define BFS_PROCESS_RET(ret) do { \
> - if (ret < 0) \
> - return print_bfs_bug(ret); \
> - if (ret == 1) \
> - return 1; \
> - } while (0)
> -
> static inline int usage_match(struct lock_list *entry, void *bit)
> {
> return entry->class->usage_mask & (1 << (enum lock_usage_bit)bit);
> @@ -1236,6 +1250,8 @@ find_usage_forwards(struct lock_list *ro
> debug_atomic_inc(&nr_find_usage_forwards_checks);
>
> result = __bfs_forwards(root, (void *)bit, usage_match, target_entry);
> + if (result < 0)
> + return print_bfs_bug(result);
>
> return result;
> }
> @@ -1259,10 +1275,42 @@ find_usage_backwards(struct lock_list *r
> debug_atomic_inc(&nr_find_usage_backwards_checks);
>
> result = __bfs_backwards(root, (void *)bit, usage_match, target_entry);
> + if (result < 0)
> + return print_bfs_bug(result);
>
> return result;
> }
>
> +/*
> + * printk the shortest lock dependencies from @start to @end in reverse order:
> + */
> +static void __used
> +print_shortest_lock_dependencies(struct lock_list *leaf,
> + struct lock_list *root)
> +{
> + struct lock_list *entry = leaf;
> + int depth;
> +
> + /*compute depth from generated tree by BFS*/
> + depth = get_lock_depth(leaf);
> +
> + do {
> + print_lock_class_header(entry->class, depth);
> + printk("%*s ... acquired at:\n", depth, "");
> + print_stack_trace(&entry->trace, 2);
> + printk("\n");
> +
> + if (depth == 0 && (entry != root)) {
> + printk("lockdep:%s bad BFS generated tree\n", __func__);
> + break;
> + }
> +
> + entry = get_lock_parent(entry);
> + depth--;
> + } while (entry && (depth >= 0));
> +
> + return;
> +}
>
> static int
> print_bad_irq_dependency(struct task_struct *curr,
> @@ -1349,12 +1397,14 @@ check_usage(struct task_struct *curr, st
>
> this.class = hlock_class(prev);
> ret = find_usage_backwards(&this, bit_backwards, &target_entry);
> - BFS_PROCESS_RET(ret);
> + if (!ret || ret == 1)
> + return ret;
>
> that.parent = NULL;
> that.class = hlock_class(next);
> ret = find_usage_forwards(&that, bit_forwards, &target_entry1);
> - BFS_PROCESS_RET(ret);
> + if (!ret || ret == 1)
> + return ret;
>
> return print_bad_irq_dependency(curr, &this, &that,
> target_entry, target_entry1,
> @@ -2038,7 +2088,8 @@ check_usage_forwards(struct task_struct
> root.parent = NULL;
> root.class = hlock_class(this);
> ret = find_usage_forwards(&root, bit, &target_entry);
> - BFS_PROCESS_RET(ret);
> + if (!ret || ret == 1)
> + return ret;
>
> return print_irq_inversion_bug(curr, &root, target_entry,
> this, 1, irqclass);
> @@ -2059,7 +2110,8 @@ check_usage_backwards(struct task_struct
> root.parent = NULL;
> root.class = hlock_class(this);
> ret = find_usage_backwards(&root, bit, &target_entry);
> - BFS_PROCESS_RET(ret);
> + if (!ret || ret == 1)
> + return ret;
>
> return print_irq_inversion_bug(curr, &root, target_entry,
> this, 1, irqclass);
> ===================================================================
> --- linux-2.6.orig/kernel/lockdep_internals.h
> +++ linux-2.6/kernel/lockdep_internals.h
> @@ -91,6 +91,8 @@ extern unsigned int nr_process_chains;
> extern unsigned int max_lockdep_depth;
> extern unsigned int max_recursion_depth;
>
> +extern unsigned int max_bfs_queue_depth;
> +
> #ifdef CONFIG_PROVE_LOCKING
> extern unsigned long lockdep_count_forward_deps(struct lock_class *);
> extern unsigned long lockdep_count_backward_deps(struct lock_class *);
> @@ -136,98 +138,3 @@ extern atomic_t nr_find_usage_backwards_
> # define debug_atomic_dec(ptr) do { } while (0)
> # define debug_atomic_read(ptr) 0
> #endif
> -
> -
> -extern unsigned int max_bfs_queue_depth;
> -extern unsigned long nr_list_entries;
> -extern struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
> -extern unsigned long bfs_accessed[];
> -
> -/*For good efficiency of modular, we use power of 2*/
> -#define MAX_CIRCULAR_QUE_SIZE 4096UL
> -
> -/* The circular_queue and helpers is used to implement the
> - * breadth-first search(BFS)algorithem, by which we can build
> - * the shortest path from the next lock to be acquired to the
> - * previous held lock if there is a circular between them.
> - * */
> -struct circular_queue{
> - unsigned long element[MAX_CIRCULAR_QUE_SIZE];
> - unsigned int front, rear;
> -};
> -
> -static inline void __cq_init(struct circular_queue *cq)
> -{
> - cq->front = cq->rear = 0;
> - bitmap_zero(bfs_accessed, MAX_LOCKDEP_ENTRIES);
> -}
> -
> -static inline int __cq_empty(struct circular_queue *cq)
> -{
> - return (cq->front == cq->rear);
> -}
> -
> -static inline int __cq_full(struct circular_queue *cq)
> -{
> - return ((cq->rear + 1)&(MAX_CIRCULAR_QUE_SIZE-1)) == cq->front;
> -}
> -
> -static inline int __cq_enqueue(struct circular_queue *cq, unsigned long elem)
> -{
> - if (__cq_full(cq))
> - return -1;
> -
> - cq->element[cq->rear] = elem;
> - cq->rear = (cq->rear + 1)&(MAX_CIRCULAR_QUE_SIZE-1);
> - return 0;
> -}
> -
> -static inline int __cq_dequeue(struct circular_queue *cq, unsigned long *elem)
> -{
> - if (__cq_empty(cq))
> - return -1;
> -
> - *elem = cq->element[cq->front];
> - cq->front = (cq->front + 1)&(MAX_CIRCULAR_QUE_SIZE-1);
> - return 0;
> -}
> -
> -static inline unsigned int __cq_get_elem_count(struct circular_queue *cq)
> -{
> - return (cq->rear - cq->front)&(MAX_CIRCULAR_QUE_SIZE-1);
> -}
> -
> -static inline void mark_lock_accessed(struct lock_list *lock,
> - struct lock_list *parent)
> -{
> - unsigned long nr;
> - nr = lock - list_entries;
> - WARN_ON(nr >= nr_list_entries);
> - lock->parent = parent;
> - set_bit(nr, bfs_accessed);
> -}
> -
> -static inline unsigned long lock_accessed(struct lock_list *lock)
> -{
> - unsigned long nr;
> - nr = lock - list_entries;
> - WARN_ON(nr >= nr_list_entries);
> - return test_bit(nr, bfs_accessed);
> -}
> -
> -static inline struct lock_list *get_lock_parent(struct lock_list *child)
> -{
> - return child->parent;
> -}
> -
> -static inline int get_lock_depth(struct lock_list *child)
> -{
> - int depth = 0;
> - struct lock_list *parent;
> -
> - while ((parent = get_lock_parent(child))) {
> - child = parent;
> - depth++;
> - }
> - return depth;
> -}
>
>
>
--
Lei Ming
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/