Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755777AbZFHNi5 (ORCPT ); Mon, 8 Jun 2009 09:38:57 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1755968AbZFHNil (ORCPT ); Mon, 8 Jun 2009 09:38:41 -0400 Received: from mail-pz0-f171.google.com ([209.85.222.171]:45711 "EHLO mail-pz0-f171.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755652AbZFHNij convert rfc822-to-8bit (ORCPT ); Mon, 8 Jun 2009 09:38:39 -0400 DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=wUj7urkn2JV4+774N7+ORJmYW40kciqd8OjBG0xtGyBfA23G+Ju6/aIM1eGCP42QYg Iw85O1uHQhT3emRqoM1t/A/3tR/nb/DZoaZXE8WRbRnSDz1R0EG7J1PkGVVNsMxGtia3 82/XHBUHvkURo1+gHYoFmcjZQOLspjHEZbf0E= MIME-Version: 1.0 In-Reply-To: <1244463727.13761.8700.camel@twins> References: <1243781365-26814-1-git-send-email-tom.leiming@gmail.com> <1244463727.13761.8700.camel@twins> Date: Mon, 8 Jun 2009 21:38:33 +0800 Message-ID: Subject: Re: [PATCH 0/8] kernel:lockdep:replace DFS with BFS From: Ming Lei To: Peter Zijlstra Cc: mingo@elte.hu, linux-kernel@vger.kernel.org, akpm@linux-foundation.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8BIT Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 20816 Lines: 587 2009/6/8 Peter Zijlstra : > > 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] [] _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: [] 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] ? ?[] print_lock_contention_bug+0x100/0x110 > [ ? ?0.000999] ?[] lock_acquired+0xf8/0x2b4 > [ ? ?0.000999] ?[] ? update_vsyscall+0x2d/0xd0 > [ ? ?0.000999] ?[] _spin_lock+0x6d/0x75 > [ ? ?0.000999] ?[] ? update_vsyscall+0x2d/0xd0 > [ ? ?0.000999] ?[] update_vsyscall+0x2d/0xd0 > [ ? ?0.000999] ?[] update_wall_time+0x4c1/0x4cc > [ ? ?0.000999] ?[] do_timer+0x15/0x1c > [ ? ?0.000999] ?[] tick_periodic+0x3b/0x74 > [ ? ?0.000999] ?[] tick_handle_periodic+0x24/0x71 > [ ? ?0.000999] ?[] timer_interrupt+0x1f/0x26 > [ ? ?0.000999] ?[] handle_IRQ_event+0x8e/0x19c > [ ? ?0.000999] ?[] handle_level_irq+0x9d/0xf3 > [ ? ?0.000999] ?[] handle_irq+0x24/0x2c > [ ? ?0.000999] ?[] do_IRQ+0x63/0xc2 > [ ? ?0.000999] ?[] ret_from_intr+0x0/0xf > [ ? ?0.000999] ? ?[] ? _spin_unlock_irqrestore+0x47/0x6d > [ ? ?0.000999] ?[] ? __setup_irq+0x1ea/0x277 > [ ? ?0.000999] ?[] ? setup_irq+0x25/0x2a > [ ? ?0.000999] ?[] ? hpet_time_init+0x20/0x22 > [ ? ?0.000999] ?[] ? start_kernel+0x2ee/0x37a > [ ? ?0.000999] ?[] ? x86_64_start_reservations+0xaa/0xae > [ ? ?0.000999] ?[] ? 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] ?[] ? trace_hardirqs_on+0xd/0xf > [ ? 65.411804] ?[] ? release_sysfs_dirent+0x91/0xb1 > [ ? 65.411804] ?[] ? print_lock_contention_bug+0x1e/0x110 > [ ? 65.411804] ?[] ? print_lock_contention_bug+0x1e/0x110 > [ ? 65.411804] ?[] ? sysfs_addrm_start+0x7d/0xaa > [ ? 65.411804] ?[] ? print_lock_contention_bug+0x1e/0x110 > [ ? 65.411804] ?[] ? alternatives_smp_module_del+0x37/0xd0 > [ ? 65.411804] ?[] ? free_percpu+0x38/0xf8 > [ ? 65.411804] ?[] ? trace_hardirqs_on+0xd/0xf > [ ? 65.411804] ?[] ? _spin_unlock_irqrestore+0x51/0x6d > [ ? 65.411804] ?[] ? free_percpu+0xef/0xf8 > [ ? 65.411804] ?[] ? free_module+0x104/0x118 > [ ? 65.411804] ?[] ? sys_delete_module+0x20c/0x22e > [ ? 65.411804] ?[] ? trace_hardirqs_on_thunk+0x3a/0x3f > [ ? 65.411804] ?[] ? 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 > Date: Mon Jun 08 13:32:31 CEST 2009 > > > LKML-Reference: > Signed-off-by: Peter Zijlstra > --- > ?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 > ?#include > ?#include > + > ?#include > > ?#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 : > - */ > -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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/