lockdep:reintroduce generation count to make BFS faster
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
@@ -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
@@ -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
[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
@@ -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
@@ -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 );
[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
@@ -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
@@ -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 );