All of lore.kernel.org
 help / color / mirror / Atom feed
* [tip:core/locking] lockdep:reintroduce generation count to make BFS faster
@ 2009-07-22 14:48 tom.leiming
  2009-08-02 13:15 ` [tip:core/locking] lockdep: Reintroduce " tip-bot for Ming Lei
  2009-08-02 13:52 ` tip-bot for Ming Lei
  0 siblings, 2 replies; 3+ messages in thread
From: tom.leiming @ 2009-07-22 14:48 UTC (permalink / raw)
  To: a.p.zijlstra; +Cc: linux-kernel, akpm, mingo, torvalds, davem, Ming Lei

From: Ming Lei <tom.leiming@gmail.com>

We still can apply DaveM's generation count optimization to
BFS, based on the following idea:

	.before doing each BFS, increase one to the global generation id;
	.if one node in the graph has been visited, marking it as visited
	by storing the current global generation id into the node's dep_gen_id field;
	.so we can decide if one node is visited by comparing the node's dep_gen_id
	with the global genration id.

By applying DaveM's genration count optimization to current implementation of BFS,
we can gains:
	.save MAX_LOCKDEP_ENTRIES/8 bytes memory;
	.remove the
		bitmap_zero(bfs_accessed, MAX_LOCKDEP_ENTRIES);
	in each BFS, which is very time-consuming since MAX_LOCKDEP_ENTRIES
        may be very large.(16384UL) 

Signed-off-by: Ming Lei <tom.leiming@gmail.com>
---
 include/linux/lockdep.h |    1 +
 kernel/lockdep.c        |   11 ++++++-----
 2 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 12aabfc..ddde26f 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -58,6 +58,7 @@ struct lock_class {
 
 	struct lockdep_subclass_key	*key;
 	unsigned int			subclass;
+	unsigned int			dep_gen_id;
 
 	/*
 	 * IRQ/softirq usage tracking bits:
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 1cedb00..1b1796a 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -848,14 +848,15 @@ struct circular_queue {
 };
 
 static struct circular_queue lock_cq;
-static unsigned long bfs_accessed[BITS_TO_LONGS(MAX_LOCKDEP_ENTRIES)];
 
 unsigned int max_bfs_queue_depth;
 
+static unsigned int lockdep_dependency_gen_id;
+
 static inline void __cq_init(struct circular_queue *cq)
 {
 	cq->front = cq->rear = 0;
-	bitmap_zero(bfs_accessed, MAX_LOCKDEP_ENTRIES);
+	lockdep_dependency_gen_id++;
 }
 
 static inline int __cq_empty(struct circular_queue *cq)
@@ -900,7 +901,7 @@ static inline void mark_lock_accessed(struct lock_list *lock,
 	nr = lock - list_entries;
 	WARN_ON(nr >= nr_list_entries);
 	lock->parent = parent;
-	set_bit(nr, bfs_accessed);
+	lock->class->dep_gen_id = lockdep_dependency_gen_id;
 }
 
 static inline unsigned long lock_accessed(struct lock_list *lock)
@@ -908,7 +909,7 @@ 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);
+	return lock->class->dep_gen_id == lockdep_dependency_gen_id;
 }
 
 static inline struct lock_list *get_lock_parent(struct lock_list *child)
@@ -3491,7 +3492,7 @@ void __init lockdep_info(void)
 		sizeof(struct lock_chain) * MAX_LOCKDEP_CHAINS +
 		sizeof(struct list_head) * CHAINHASH_SIZE) / 1024
 #ifdef CONFIG_PROVE_LOCKING
-		+ sizeof(struct circular_queue) + sizeof(bfs_accessed)
+		+ sizeof(struct circular_queue)
 #endif
 		);
 
-- 
1.6.0.GIT


^ permalink raw reply related	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2009-08-02 13:53 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2009-07-22 14:48 [tip:core/locking] lockdep:reintroduce generation count to make BFS faster tom.leiming
2009-08-02 13:15 ` [tip:core/locking] lockdep: Reintroduce " tip-bot for Ming Lei
2009-08-02 13:52 ` tip-bot for Ming Lei

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.