diff options
| author | Ming Lei <tom.leiming@gmail.com> | 2009-07-22 22:48:09 +0800 |
|---|---|---|
| committer | Ingo Molnar <mingo@elte.hu> | 2009-08-02 15:41:37 +0200 |
| commit | e351b660fddd4df76cc4635f896d311ed0ff3752 (patch) | |
| tree | 380a67c875a4454bd47a8ce6ddd159432863646e /include/linux/lockdep.h | |
| parent | bb97a91e2549a7f2df9c21d32542582f549ab3ec (diff) | |
| download | linux-e351b660fddd4df76cc4635f896d311ed0ff3752.tar.gz linux-e351b660fddd4df76cc4635f896d311ed0ff3752.tar.bz2 linux-e351b660fddd4df76cc4635f896d311ed0ff3752.zip | |
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/lockdep.h')
| -rw-r--r-- | include/linux/lockdep.h | 1 |
1 files changed, 1 insertions, 0 deletions
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: |