From: Bart Van Assche <bvanassche@acm.org>
To: mingo@redhat.com
Cc: peterz@infradead.org, tj@kernel.org, longman@redhat.com,
johannes.berg@intel.com, linux-kernel@vger.kernel.org,
Bart Van Assche <bvanassche@acm.org>,
Johannes Berg <johannes@sipsolutions.net>
Subject: [PATCH v3 18/24] locking/lockdep: Reuse list entries that are no longer in use
Date: Thu, 6 Dec 2018 17:11:42 -0800 [thread overview]
Message-ID: <20181207011148.251812-19-bvanassche@acm.org> (raw)
In-Reply-To: <20181207011148.251812-1-bvanassche@acm.org>
Instead of abandoning elements of list_entries[] that are no longer in
use, make alloc_list_entry() reuse array elements that have been freed.
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Waiman Long <longman@redhat.com>
Cc: Johannes Berg <johannes@sipsolutions.net>
Signed-off-by: Bart Van Assche <bvanassche@acm.org>
---
kernel/locking/lockdep.c | 27 ++++++++++++++++++++-------
1 file changed, 20 insertions(+), 7 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index ce8abd268727..6f338f852f7e 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -130,6 +130,8 @@ static inline int debug_locks_off_graph_unlock(void)
unsigned long nr_list_entries;
static struct lock_list list_entries[MAX_LOCKDEP_ENTRIES];
+static DECLARE_BITMAP(list_entries_in_use, MAX_LOCKDEP_ENTRIES);
+static DECLARE_BITMAP(list_entries_being_freed, MAX_LOCKDEP_ENTRIES);
/*
* All data structures here are protected by the global debug_lock.
@@ -870,7 +872,10 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
*/
static struct lock_list *alloc_list_entry(void)
{
- if (nr_list_entries >= MAX_LOCKDEP_ENTRIES) {
+ int idx = find_first_zero_bit(list_entries_in_use,
+ ARRAY_SIZE(list_entries));
+
+ if (idx >= ARRAY_SIZE(list_entries)) {
if (!debug_locks_off_graph_unlock())
return NULL;
@@ -878,7 +883,8 @@ static struct lock_list *alloc_list_entry(void)
dump_stack();
return NULL;
}
- return list_entries + nr_list_entries++;
+ __set_bit(idx, list_entries_in_use);
+ return list_entries + idx;
}
/*
@@ -983,7 +989,7 @@ static inline void mark_lock_accessed(struct lock_list *lock,
unsigned long nr;
nr = lock - list_entries;
- WARN_ON(nr >= nr_list_entries); /* Out-of-bounds, input fail */
+ WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
lock->parent = parent;
lock->class->dep_gen_id = lockdep_dependency_gen_id;
}
@@ -993,7 +999,7 @@ static inline unsigned long lock_accessed(struct lock_list *lock)
unsigned long nr;
nr = lock - list_entries;
- WARN_ON(nr >= nr_list_entries); /* Out-of-bounds, input fail */
+ WARN_ON(nr >= ARRAY_SIZE(list_entries)); /* Out-of-bounds, input fail */
return lock->class->dep_gen_id == lockdep_dependency_gen_id;
}
@@ -4252,9 +4258,12 @@ static void zap_class(struct lock_class *class)
* Remove all dependencies this lock is
* involved in:
*/
- for (i = 0, entry = list_entries; i < nr_list_entries; i++, entry++) {
+ for_each_set_bit(i, list_entries_in_use, ARRAY_SIZE(list_entries)) {
+ entry = list_entries + i;
if (entry->class != class && entry->links_to != class)
continue;
+ if (__test_and_set_bit(i, list_entries_being_freed))
+ continue;
links_to = entry->links_to;
WARN_ON_ONCE(entry->class == links_to);
list_del_rcu(&entry->entry);
@@ -4287,8 +4296,9 @@ static inline int within(const void *addr, void *start, unsigned long size)
}
/*
- * Free all lock classes that are on the zapped_classes list. Called as an
- * RCU callback function.
+ * Free all lock classes that are on the zapped_classes list and also all list
+ * entries that have been marked as being freed. Called as an RCU callback
+ * function.
*/
static void free_zapped_classes(struct callback_head *ch)
{
@@ -4304,6 +4314,9 @@ static void free_zapped_classes(struct callback_head *ch)
nr_lock_classes--;
}
list_splice_init(&zapped_classes, &free_lock_classes);
+ bitmap_andnot(list_entries_in_use, list_entries_in_use,
+ list_entries_being_freed, ARRAY_SIZE(list_entries));
+ bitmap_clear(list_entries_being_freed, 0, ARRAY_SIZE(list_entries));
if (locked)
graph_unlock();
raw_local_irq_restore(flags);
--
2.20.0.rc2.403.gdbc3b29805-goog
next prev parent reply other threads:[~2018-12-07 1:14 UTC|newest]
Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-12-07 1:11 [PATCH v3 00/24] locking/lockdep: Add support for dynamic keys Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 01/24] lockdep tests: Display compiler warning and error messages Bart Van Assche
2018-12-11 15:22 ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 02/24] lockdep tests: Fix shellcheck warnings Bart Van Assche
2018-12-11 15:23 ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 03/24] lockdep tests: Improve testing accuracy Bart Van Assche
2018-12-11 15:23 ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 04/24] lockdep tests: Run lockdep tests a second time under Valgrind Bart Van Assche
2018-12-11 15:24 ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 05/24] liblockdep: Rename "trywlock" into "trywrlock" Bart Van Assche
2018-12-11 15:24 ` [tip:locking/core] tools/lib/lockdep: " tip-bot for Bart Van Assche
2018-12-11 17:19 ` [PATCH v3 05/24] liblockdep: " Sasha Levin
2018-12-11 17:38 ` Bart Van Assche
2018-12-13 19:41 ` Sasha Levin
2018-12-07 1:11 ` [PATCH v3 06/24] liblockdep: Add dummy print_irqtrace_events() implementation Bart Van Assche
2018-12-11 15:25 ` [tip:locking/core] tools/lib/lockdep: " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 07/24] lockdep tests: Test the lockdep_reset_lock() implementation Bart Van Assche
2018-12-11 15:26 ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 08/24] locking/lockdep: Declare local symbols static Bart Van Assche
2018-12-11 15:26 ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 09/24] locking/lockdep: Inline __lockdep_init_map() Bart Van Assche
2018-12-11 15:27 ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 10/24] locking/lockdep: Introduce lock_class_cache_is_registered() Bart Van Assche
2018-12-11 15:27 ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 11/24] locking/lockdep: Remove a superfluous INIT_LIST_HEAD() statement Bart Van Assche
2018-12-11 15:28 ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 12/24] locking/lockdep: Make concurrent lockdep_reset_lock() calls safe Bart Van Assche
2018-12-11 15:29 ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 13/24] locking/lockdep: Stop using RCU primitives to access all_lock_classes Bart Van Assche
2018-12-11 15:29 ` [tip:locking/core] locking/lockdep: Stop using RCU primitives to access 'all_lock_classes' tip-bot for Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 14/24] locking/lockdep: Make zap_class() remove all matching lock order entries Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 15/24] locking/lockdep: Reorder struct lock_class members Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 16/24] locking/lockdep: Retain the class key and name while freeing a lock class Bart Van Assche
2018-12-07 10:21 ` Peter Zijlstra
2018-12-07 14:50 ` Waiman Long
2018-12-07 16:23 ` Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 17/24] locking/lockdep: Free lock classes that are no longer in use Bart Van Assche
2018-12-07 12:14 ` Peter Zijlstra
2018-12-07 16:27 ` Bart Van Assche
2018-12-07 1:11 ` Bart Van Assche [this message]
2018-12-07 1:11 ` [PATCH v3 19/24] locking/lockdep: Check data structure consistency Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 20/24] locking/lockdep: Introduce __lockdep_free_key_range() Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 21/24] locking/lockdep: Verify whether lock objects are small enough to be used as class keys Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 22/24] locking/lockdep: Add support for dynamic keys Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 23/24] kernel/workqueue: Use dynamic lockdep keys for workqueues Bart Van Assche
2018-12-07 1:11 ` [PATCH v3 24/24] lockdep tests: Test dynamic key registration Bart Van Assche
2018-12-07 12:23 ` [PATCH v3 00/24] locking/lockdep: Add support for dynamic keys Peter Zijlstra
2018-12-07 16:35 ` Bart Van Assche
2018-12-08 10:26 ` Peter Zijlstra
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20181207011148.251812-19-bvanassche@acm.org \
--to=bvanassche@acm.org \
--cc=johannes.berg@intel.com \
--cc=johannes@sipsolutions.net \
--cc=linux-kernel@vger.kernel.org \
--cc=longman@redhat.com \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
--cc=tj@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).