Skip to contentSkip to conversation

lockdep:reintroduce generation count to make BFS faster

tip:core/locking [email protected] 1 participant 3 messages Jul 22, 2009 – Aug 2, 2009 Locking primitives

lore
Share & tools
lore
#0 lore raw

From: Ming Lei <[email protected]>

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) 
---
 include/linux/lockdep.h |    1 +
 kernel/lockdep.c        |   11 ++++++-----
 2 files changed, 7 insertions(+), 5 deletions(-)
include/linux/lockdep.h +1 -0
index 12aabfc..ddde26f 100644
@@ -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:
kernel/lockdep.c +6 -5
index 1cedb00..1b1796a 100644
@@ -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
 		);
 
Signature · 1 line
1.6.0.GIT
#1 lore raw

[tip:core/locking] lockdep: Reintroduce generation count to make BFS faster

Commit-ID:  67a8b0af3942250e563739442f98d3bca50442ff
Gitweb:     http://git.kernel.org/tip/67a8b0af3942250e563739442f98d3bca50442ff
Author:     Ming Lei <[email protected]>
AuthorDate: Wed, 22 Jul 2009 22:48:09 +0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Sun, 2 Aug 2009 14:59:32 +0200

lockdep: Reintroduce generation count to make BFS faster

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

- before doing each BFS, increase the global generation id by 1

- if one node in the graph has been visited, mark 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 has been visited already, by comparing the node's dep_gen_id with the global generation id.

By applying DaveM's generation count optimization to current implementation of BFS, we gain the following advantages:

- we save MAX_LOCKDEP_ENTRIES/8 bytes memory;

- we 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)

LKML-Reference: <[email protected]>

---
 include/linux/lockdep.h |    1 +
 kernel/lockdep.c        |   11 ++++++-----
 2 files changed, 7 insertions(+), 5 deletions(-)
include/linux/lockdep.h +1 -0
index 47d42ef..9ccf0e2 100644
@@ -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:
kernel/lockdep.c +6 -5
index 0bb246e..2b443b5 100644
@@ -861,14 +861,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)
@@ -914,7 +915,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)
@@ -923,7 +924,7 @@ static inline unsigned long lock_accessed(struct lock_list *lock)
 
 	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)
@@ -3604,7 +3605,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
 		);
 
#2 lore raw

[tip:core/locking] lockdep: Reintroduce generation count to make BFS faster

In reply to [email protected]
Commit-ID:  e351b660fddd4df76cc4635f896d311ed0ff3752
Gitweb:     http://git.kernel.org/tip/e351b660fddd4df76cc4635f896d311ed0ff3752
Author:     Ming Lei <[email protected]>
AuthorDate: Wed, 22 Jul 2009 22:48:09 +0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Sun, 2 Aug 2009 15:41:37 +0200

lockdep: Reintroduce generation count to make BFS faster

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

- before doing each BFS, increase the global generation id by 1

- if one node in the graph has been visited, mark 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 has been visited already, by comparing the node's dep_gen_id with the global generation id.

By applying DaveM's generation count optimization to current implementation of BFS, we gain the following advantages:

- we save MAX_LOCKDEP_ENTRIES/8 bytes memory;

- we 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)

LKML-Reference: <[email protected]>

---
 include/linux/lockdep.h |    1 +
 kernel/lockdep.c        |   11 ++++++-----
 2 files changed, 7 insertions(+), 5 deletions(-)
include/linux/lockdep.h +1 -0
index 47d42ef..9ccf0e2 100644
@@ -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:
kernel/lockdep.c +6 -5
index 0bb246e..2b443b5 100644
@@ -861,14 +861,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)
@@ -914,7 +915,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)
@@ -923,7 +924,7 @@ static inline unsigned long lock_accessed(struct lock_list *lock)
 
 	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)
@@ -3604,7 +3605,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
 		);