* [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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.