summaryrefslogtreecommitdiff
path: root/kernel/lockdep.c
diff options
context:
space:
mode:
authorMing Lei <tom.leiming@gmail.com>2009-07-22 22:48:09 +0800
committerIngo Molnar <mingo@elte.hu>2009-08-02 15:41:37 +0200
commite351b660fddd4df76cc4635f896d311ed0ff3752 (patch)
tree380a67c875a4454bd47a8ce6ddd159432863646e /kernel/lockdep.c
parentbb97a91e2549a7f2df9c21d32542582f549ab3ec (diff)
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) Signed-off-by: Ming Lei <tom.leiming@gmail.com> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: "David S. Miller" <davem@davemloft.net> LKML-Reference: <1248274089-6358-1-git-send-email-tom.leiming@gmail.com> Signed-off-by: Ingo Molnar <mingo@elte.hu>
Diffstat (limited to 'kernel/lockdep.c')
-rw-r--r--kernel/lockdep.c11
1 files changed, 6 insertions, 5 deletions
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 0bb246e21cd..2b443b5090a 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -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
);