aboutsummaryrefslogtreecommitdiffstats
path: root/include/linux
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 /include/linux
parentbb97a91e2549a7f2df9c21d32542582f549ab3ec (diff)
downloadkernel_samsung_smdk4412-e351b660fddd4df76cc4635f896d311ed0ff3752.zip
kernel_samsung_smdk4412-e351b660fddd4df76cc4635f896d311ed0ff3752.tar.gz
kernel_samsung_smdk4412-e351b660fddd4df76cc4635f896d311ed0ff3752.tar.bz2
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 'include/linux')
-rw-r--r--include/linux/lockdep.h1
1 files changed, 1 insertions, 0 deletions
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 47d42ef..9ccf0e2 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: