* [tip:core/locking] lockdep:reintroduce generation count to make BFS faster
@ 2009-07-22 14:48 tom.leiming
2009-08-02 13:15 ` [tip:core/locking] lockdep: Reintroduce " tip-bot for Ming Lei
2009-08-02 13:52 ` tip-bot for Ming Lei
0 siblings, 2 replies; 3+ messages in thread
From: tom.leiming @ 2009-07-22 14:48 UTC (permalink / raw)
To: a.p.zijlstra; +Cc: linux-kernel, akpm, mingo, torvalds, davem, Ming Lei
From: Ming Lei <tom.leiming@gmail.com>
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)
Signed-off-by: Ming Lei <tom.leiming@gmail.com>
---
include/linux/lockdep.h | 1 +
kernel/lockdep.c | 11 ++++++-----
2 files changed, 7 insertions(+), 5 deletions(-)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 12aabfc..ddde26f 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:
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 1cedb00..1b1796a 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -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
);
--
1.6.0.GIT
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [tip:core/locking] lockdep: Reintroduce generation count to make BFS faster
2009-07-22 14:48 [tip:core/locking] lockdep:reintroduce generation count to make BFS faster tom.leiming
@ 2009-08-02 13:15 ` tip-bot for Ming Lei
2009-08-02 13:52 ` tip-bot for Ming Lei
1 sibling, 0 replies; 3+ messages in thread
From: tip-bot for Ming Lei @ 2009-08-02 13:15 UTC (permalink / raw)
To: linux-tip-commits
Cc: linux-kernel, hpa, mingo, a.p.zijlstra, davem, tglx, tom.leiming,
mingo
Commit-ID: 67a8b0af3942250e563739442f98d3bca50442ff
Gitweb: http://git.kernel.org/tip/67a8b0af3942250e563739442f98d3bca50442ff
Author: Ming Lei <tom.leiming@gmail.com>
AuthorDate: Wed, 22 Jul 2009 22:48:09 +0800
Committer: Ingo Molnar <mingo@elte.hu>
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)
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>
---
include/linux/lockdep.h | 1 +
kernel/lockdep.c | 11 ++++++-----
2 files changed, 7 insertions(+), 5 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:
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 0bb246e..2b443b5 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
);
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [tip:core/locking] lockdep: Reintroduce generation count to make BFS faster
2009-07-22 14:48 [tip:core/locking] lockdep:reintroduce generation count to make BFS faster tom.leiming
2009-08-02 13:15 ` [tip:core/locking] lockdep: Reintroduce " tip-bot for Ming Lei
@ 2009-08-02 13:52 ` tip-bot for Ming Lei
1 sibling, 0 replies; 3+ messages in thread
From: tip-bot for Ming Lei @ 2009-08-02 13:52 UTC (permalink / raw)
To: linux-tip-commits
Cc: linux-kernel, hpa, mingo, a.p.zijlstra, davem, tglx, tom.leiming,
mingo
Commit-ID: e351b660fddd4df76cc4635f896d311ed0ff3752
Gitweb: http://git.kernel.org/tip/e351b660fddd4df76cc4635f896d311ed0ff3752
Author: Ming Lei <tom.leiming@gmail.com>
AuthorDate: Wed, 22 Jul 2009 22:48:09 +0800
Committer: Ingo Molnar <mingo@elte.hu>
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)
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>
---
include/linux/lockdep.h | 1 +
kernel/lockdep.c | 11 ++++++-----
2 files changed, 7 insertions(+), 5 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:
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 0bb246e..2b443b5 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
);
^ permalink raw reply related [flat|nested] 3+ messages in thread
end of thread, other threads:[~2009-08-02 13:53 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2009-07-22 14:48 [tip:core/locking] lockdep:reintroduce generation count to make BFS faster tom.leiming
2009-08-02 13:15 ` [tip:core/locking] lockdep: Reintroduce " tip-bot for Ming Lei
2009-08-02 13:52 ` tip-bot for Ming Lei
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox