From: tip-bot for Bart Van Assche <tipbot@zytor.com>
To: linux-tip-commits@vger.kernel.org
Cc: will.deacon@arm.com, akpm@linux-foundation.org,
torvalds@linux-foundation.org, linux-kernel@vger.kernel.org,
longman@redhat.com, peterz@infradead.org,
johannes@sipsolutions.net, mingo@kernel.org, bvanassche@acm.org,
paulmck@linux.vnet.ibm.com, tglx@linutronix.de, hpa@zytor.com
Subject: [tip:locking/core] locking/lockdep: Reuse list entries that are no longer in use
Date: Wed, 27 Feb 2019 23:09:55 -0800 [thread overview]
Message-ID: <tip-ace35a7ac493d4284a57ad807579011bebba891c@git.kernel.org> (raw)
In-Reply-To: <20190214230058.196511-13-bvanassche@acm.org>
Commit-ID: ace35a7ac493d4284a57ad807579011bebba891c
Gitweb: https://git.kernel.org/tip/ace35a7ac493d4284a57ad807579011bebba891c
Author: Bart Van Assche <bvanassche@acm.org>
AuthorDate: Thu, 14 Feb 2019 15:00:47 -0800
Committer: Ingo Molnar <mingo@kernel.org>
CommitDate: Thu, 28 Feb 2019 07:55:44 +0100
locking/lockdep: Reuse list entries that are no longer in use
Instead of abandoning elements of list_entries[] that are no longer in
use, make alloc_list_entry() reuse array elements that have been freed.
Signed-off-by: Bart Van Assche <bvanassche@acm.org>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Johannes Berg <johannes@sipsolutions.net>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Waiman Long <longman@redhat.com>
Cc: Will Deacon <will.deacon@arm.com>
Cc: johannes.berg@intel.com
Cc: tj@kernel.org
Link: https://lkml.kernel.org/r/20190214230058.196511-13-bvanassche@acm.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
kernel/locking/lockdep.c | 24 ++++++++++++++++--------
1 file changed, 16 insertions(+), 8 deletions(-)
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 8ecf355dd163..2c6d0b67e7b6 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -45,6 +45,7 @@
#include <linux/hash.h>
#include <linux/ftrace.h>
#include <linux/stringify.h>
+#include <linux/bitmap.h>
#include <linux/bitops.h>
#include <linux/gfp.h>
#include <linux/random.h>
@@ -132,6 +133,7 @@ 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);
/*
* All data structures here are protected by the global debug_lock.
@@ -907,7 +909,10 @@ out_set_class_cache:
*/
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;
@@ -915,7 +920,9 @@ static struct lock_list *alloc_list_entry(void)
dump_stack();
return NULL;
}
- return list_entries + nr_list_entries++;
+ nr_list_entries++;
+ __set_bit(idx, list_entries_in_use);
+ return list_entries + idx;
}
/*
@@ -1019,7 +1026,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;
}
@@ -1029,7 +1036,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;
}
@@ -4276,13 +4283,13 @@ static void zap_class(struct pending_free *pf, 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;
+ __clear_bit(i, list_entries_in_use);
+ nr_list_entries--;
list_del_rcu(&entry->entry);
- /* Clear .class and .links_to to avoid double removal. */
- WRITE_ONCE(entry->class, NULL);
- WRITE_ONCE(entry->links_to, NULL);
}
if (list_empty(&class->locks_after) &&
list_empty(&class->locks_before)) {
@@ -4596,6 +4603,7 @@ void __init lockdep_init(void)
(sizeof(lock_classes) +
sizeof(classhash_table) +
sizeof(list_entries) +
+ sizeof(list_entries_in_use) +
sizeof(chainhash_table) +
sizeof(delayed_free)
#ifdef CONFIG_PROVE_LOCKING
next prev parent reply other threads:[~2019-02-28 7:10 UTC|newest]
Thread overview: 59+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-02-14 23:00 [PATCH v7 00/23] locking/lockdep: Add support for dynamic keys Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 01/23] locking/lockdep: Fix two 32-bit compiler warnings Bart Van Assche
2019-02-28 7:02 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 02/23] locking/lockdep: Fix reported required memory size (1/2) Bart Van Assche
2019-02-28 7:03 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 03/23] locking/lockdep: Fix reported required memory size (2/2) Bart Van Assche
2019-02-28 7:03 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 04/23] locking/lockdep: Avoid that add_chain_cache() adds an invalid chain to the cache Bart Van Assche
2019-02-28 7:04 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 05/23] locking/lockdep: Reorder struct lock_class members Bart Van Assche
2019-02-28 7:05 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 06/23] locking/lockdep: Make zap_class() remove all matching lock order entries Bart Van Assche
2019-02-28 7:05 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 07/23] locking/lockdep: Initialize the locks_before and locks_after lists earlier Bart Van Assche
2019-02-28 7:06 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 08/23] locking/lockdep: Split lockdep_free_key_range() and lockdep_reset_lock() Bart Van Assche
2019-02-28 7:07 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 09/23] locking/lockdep: Make it easy to detect whether or not inside a selftest Bart Van Assche
2019-02-28 7:07 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 10/23] locking/lockdep: Update two outdated comments Bart Van Assche
2019-02-28 7:08 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 11/23] locking/lockdep: Free lock classes that are no longer in use Bart Van Assche
2019-02-28 7:09 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 12/23] locking/lockdep: Reuse list entries " Bart Van Assche
2019-02-28 7:09 ` tip-bot for Bart Van Assche [this message]
2019-02-14 23:00 ` [PATCH v7 13/23] locking/lockdep: Introduce lockdep_next_lockchain() and lock_chain_count() Bart Van Assche
2019-02-28 7:10 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 14/23] locking/lockdep: Fix a comment in add_chain_cache() Bart Van Assche
2019-02-28 7:11 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 15/23] locking/lockdep: Reuse lock chains that have been freed Bart Van Assche
2019-02-28 7:11 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 16/23] locking/lockdep: Check data structure consistency Bart Van Assche
2019-02-28 7:12 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 17/23] locking/lockdep: Verify whether lock objects are small enough to be used as class keys Bart Van Assche
2019-02-28 7:13 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 18/23] locking/lockdep: Add support for dynamic keys Bart Van Assche
2019-02-26 17:17 ` Peter Zijlstra
2019-02-28 7:13 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 19/23] kernel/workqueue: Use dynamic lockdep keys for workqueues Bart Van Assche
2019-02-28 7:14 ` [tip:locking/core] " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 20/23] locking/spinlock: Introduce spin_lock_init_key() Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 21/23] block: Avoid that flushing triggers a lockdep complaint Bart Van Assche
2019-02-15 2:26 ` Ming Lei
2019-02-15 16:08 ` Bart Van Assche
2019-02-17 13:23 ` Ming Lei
2019-02-26 18:08 ` Peter Zijlstra
2019-02-27 1:35 ` Ming Lei
2019-02-27 14:24 ` Peter Zijlstra
2019-02-27 15:53 ` Ming Lei
2019-02-26 17:24 ` Peter Zijlstra
2019-02-26 17:48 ` Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 22/23] lockdep tests: Fix run_tests.sh Bart Van Assche
2019-02-28 7:15 ` [tip:locking/core] lockdep/lib/tests: " tip-bot for Bart Van Assche
2019-02-14 23:00 ` [PATCH v7 23/23] lockdep tests: Test dynamic key registration Bart Van Assche
2019-02-28 7:15 ` [tip:locking/core] lockdep/lib/tests: " tip-bot for Bart Van Assche
2019-02-21 22:02 ` [PATCH v7 00/23] locking/lockdep: Add support for dynamic keys Bart Van Assche
2019-02-22 16:26 ` Peter Zijlstra
2019-02-22 17:20 ` Bart Van Assche
2019-02-22 22:13 ` 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=tip-ace35a7ac493d4284a57ad807579011bebba891c@git.kernel.org \
--to=tipbot@zytor.com \
--cc=akpm@linux-foundation.org \
--cc=bvanassche@acm.org \
--cc=hpa@zytor.com \
--cc=johannes@sipsolutions.net \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-tip-commits@vger.kernel.org \
--cc=longman@redhat.com \
--cc=mingo@kernel.org \
--cc=paulmck@linux.vnet.ibm.com \
--cc=peterz@infradead.org \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
--cc=will.deacon@arm.com \
/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).