From e351b660fddd4df76cc4635f896d311ed0ff3752 Mon Sep 17 00:00:00 2001 From: Ming Lei Date: Wed, 22 Jul 2009 22:48:09 +0800 Subject: 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 Signed-off-by: Peter Zijlstra Cc: "David S. Miller" LKML-Reference: <1248274089-6358-1-git-send-email-tom.leiming@gmail.com> Signed-off-by: Ingo Molnar --- include/linux/lockdep.h | 1 + 1 file changed, 1 insertion(+) (limited to 'include/linux/lockdep.h') diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index 47d42eff6124..9ccf0e286b2a 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: -- cgit v1.2.3