From: Byungchul Park <byungchul.park@lge.com>
To: <peterz@infradead.org>, <mingo@kernel.org>
Cc: <tglx@linutronix.de>, <walken@google.com>, <boqun.feng@gmail.com>,
<kirill@shutemov.name>, <linux-kernel@vger.kernel.org>,
<linux-mm@kvack.org>, <iamjoonsoo.kim@lge.com>,
<akpm@linux-foundation.org>, <willy@infradead.org>,
<npiggin@gmail.com>, <kernel-team@lge.com>
Subject: [PATCH v6 07/15] lockdep: Avoid adding redundant direct links of crosslocks
Date: Tue, 14 Mar 2017 17:18:54 +0900 [thread overview]
Message-ID: <1489479542-27030-8-git-send-email-byungchul.park@lge.com> (raw)
In-Reply-To: <1489479542-27030-1-git-send-email-byungchul.park@lge.com>
On my machine (QEMU x86_64, 4 core, mem 512M, enable-kvm), this patch
does not make different between before/after in lockdep_stats. So this
patch looks unnecessary. However, I wonder if it's still true in other
systems. Could anybody check lockdep_stats in your system?
Before (apply all crossrelease patches except this patch):
lock-classes: 988 [max: 8191]
direct dependencies: 5814 [max: 32768]
indirect dependencies: 18915
all direct dependencies: 119802
dependency chains: 6350 [max: 65536]
dependency chain hlocks: 20771 [max: 327680]
in-hardirq chains: 52
in-softirq chains: 361
in-process chains: 5937
stack-trace entries: 80396 [max: 524288]
combined max dependencies: 113926468
hardirq-safe locks: 42
hardirq-unsafe locks: 644
softirq-safe locks: 129
softirq-unsafe locks: 561
irq-safe locks: 135
irq-unsafe locks: 644
hardirq-read-safe locks: 2
hardirq-read-unsafe locks: 127
softirq-read-safe locks: 11
softirq-read-unsafe locks: 119
irq-read-safe locks: 12
irq-read-unsafe locks: 127
uncategorized locks: 165
unused locks: 1
max locking depth: 14
max bfs queue depth: 168
debug_locks: 1
After (apply all crossrelease patches without exception):
lock-classes: 980 [max: 8191]
direct dependencies: 5604 [max: 32768]
indirect dependencies: 18517
all direct dependencies: 112620
dependency chains: 6215 [max: 65536]
dependency chain hlocks: 20401 [max: 327680]
in-hardirq chains: 51
in-softirq chains: 298
in-process chains: 5866
stack-trace entries: 78707 [max: 524288]
combined max dependencies: 91220116
hardirq-safe locks: 42
hardirq-unsafe locks: 637
softirq-safe locks: 117
softirq-unsafe locks: 561
irq-safe locks: 126
irq-unsafe locks: 637
hardirq-read-safe locks: 2
hardirq-read-unsafe locks: 127
softirq-read-safe locks: 10
softirq-read-unsafe locks: 119
irq-read-safe locks: 11
irq-read-unsafe locks: 127
uncategorized locks: 165
unused locks: 1
max locking depth: 15
max bfs queue depth: 168
debug_locks: 1
-----8<-----
>From 803e905a4cbf6c10b776a9e272a3bda9e3ffaa95 Mon Sep 17 00:00:00 2001
From: Byungchul Park <byungchul.park@lge.com>
Date: Tue, 14 Mar 2017 14:59:54 +0900
Subject: [PATCH v6 07/15] lockdep: Avoid adding redundant direct links of
crosslocks
We can skip adding a dependency 'AX -> B', in case that we ensure 'AX ->
the previous of B in hlocks' to be created, where AX is a crosslock and
B is a typical lock. Remember that two adjacent locks in hlocks generate
a dependency like 'prev -> next', that is, 'the previous of B in hlocks
-> B' in this case.
For example:
in hlocks[]
------------
^ A (gen_id: 4) --+
| | previous gen_id
| B (gen_id: 3) <-+
| C (gen_id: 3)
| D (gen_id: 2)
oldest | E (gen_id: 1)
in xhlocks[]
------------
^ A (gen_id: 4, prev_gen_id: 3(B's gen id))
| B (gen_id: 3, prev_gen_id: 3(C's gen id))
| C (gen_id: 3, prev_gen_id: 2(D's gen id))
| D (gen_id: 2, prev_gen_id: 1(E's gen id))
oldest | E (gen_id: 1, prev_gen_id: NA)
On commit for a crosslock AX(gen_id = 3), it's engough to add 'AX -> C',
but adding 'AX -> B' and 'AX -> A' is unnecessary since 'AX -> C', 'C ->
B' and 'B -> A' cover them, which are guaranteed to be generated.
This patch intoduces a variable, prev_gen_id, to avoid adding this kind
of redundant dependencies. In other words, the previous in hlocks will
anyway handle it if the previous's gen_id >= the crosslock's gen_id.
Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
include/linux/lockdep.h | 11 +++++++++++
kernel/locking/lockdep.c | 30 ++++++++++++++++++++++++++++--
2 files changed, 39 insertions(+), 2 deletions(-)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 5356f71..31c6289 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,6 +284,17 @@ struct held_lock {
*/
struct hist_lock {
/*
+ * We can skip adding a dependency 'a target crosslock -> this
+ * lock', in case that we ensure 'the target crosslock -> the
+ * previous lock in held_locks' to be created. Remember that
+ * 'the previous lock in held_locks -> this lock' is guaranteed
+ * to be created, and 'A -> B' and 'B -> C' cover 'A -> C'.
+ *
+ * Keep the previous's gen_id to make the decision.
+ */
+ unsigned int prev_gen_id;
+
+ /*
* Each work of workqueue might run in a different context,
* thanks to concurrency support of workqueue. So we have to
* distinguish each work to avoid false positive.
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index ec4f6af..c78dd9d 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4716,13 +4716,18 @@ static inline int xhlock_used(struct hist_lock *xhlock)
/*
* Only access local task's data, so irq disable is only required.
*/
-static void add_xhlock(struct held_lock *hlock)
+static void add_xhlock(struct held_lock *hlock, unsigned int prev_gen_id)
{
unsigned int idx = current->xhlock_idx++;
struct hist_lock *xhlock = &xhlock(idx);
/* Initialize hist_lock's members */
xhlock->hlock = *hlock;
+ /*
+ * prev_gen_id is used to skip adding redundant dependencies,
+ * which can be covered by the previous lock in held_locks.
+ */
+ xhlock->prev_gen_id = prev_gen_id;
xhlock->work_id = current->work_id;
xhlock->trace.nr_entries = 0;
@@ -4761,10 +4766,30 @@ static int same_context_xhlock(struct hist_lock *xhlock)
*/
static void check_add_xhlock(struct held_lock *hlock)
{
+ struct held_lock *prev;
+ struct held_lock *start;
+ unsigned int gen_id;
+ unsigned int gen_id_invalid;
+
if (!current->xhlocks || !depend_before(hlock))
return;
- add_xhlock(hlock);
+ gen_id = (unsigned int)atomic_read(&cross_gen_id);
+ /*
+ * gen_id_invalid should be old enough to be invalid.
+ * Current gen_id - (UINIT_MAX / 4) would be a good
+ * value to meet it.
+ */
+ gen_id_invalid = gen_id - (UINT_MAX / 4);
+ start = current->held_locks;
+
+ for (prev = hlock - 1; prev >= start &&
+ !depend_before(prev); prev--);
+
+ if (prev < start)
+ add_xhlock(hlock, gen_id_invalid);
+ else if (prev->gen_id != gen_id)
+ add_xhlock(hlock, prev->gen_id);
}
/*
@@ -4902,6 +4927,7 @@ static int commit_xhlocks(struct cross_lock *xlock)
break;
if (same_context_xhlock(xhlock) &&
+ before(xhlock->prev_gen_id, xlock->hlock.gen_id) &&
!commit_xhlock(xlock, xhlock))
return 0;
}
--
1.9.1
next prev parent reply other threads:[~2017-03-14 8:27 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-03-14 8:18 [PATCH v6 00/15] lockdep: Implement crossrelease feature Byungchul Park
2017-03-14 8:18 ` [PATCH v6 01/15] lockdep: Refactor lookup_chain_cache() Byungchul Park
2017-03-14 8:18 ` [PATCH v6 02/15] lockdep: Add a function building a chain between two classes Byungchul Park
2017-03-14 8:18 ` [PATCH v6 03/15] lockdep: Change the meaning of check_prev_add()'s return value Byungchul Park
2017-03-14 8:18 ` [PATCH v6 04/15] lockdep: Make check_prev_add() able to handle external stack_trace Byungchul Park
2017-03-14 8:18 ` [PATCH v6 05/15] lockdep: Implement crossrelease feature Byungchul Park
2017-04-19 14:25 ` Peter Zijlstra
2017-04-24 5:11 ` Byungchul Park
2017-04-24 10:17 ` Peter Zijlstra
2017-04-25 5:40 ` Byungchul Park
2017-05-16 14:18 ` Peter Zijlstra
2017-05-18 6:22 ` Byungchul Park
2017-04-19 15:08 ` Peter Zijlstra
2017-04-24 4:36 ` Byungchul Park
2017-04-19 17:19 ` Peter Zijlstra
2017-04-24 3:04 ` Byungchul Park
2017-04-24 9:30 ` Peter Zijlstra
2017-04-25 6:59 ` Byungchul Park
2017-04-19 17:20 ` Peter Zijlstra
2017-04-24 3:13 ` Byungchul Park
2017-05-19 8:07 ` Byungchul Park
2017-05-19 10:30 ` Peter Zijlstra
2017-05-19 10:56 ` Byungchul Park
2017-03-14 8:18 ` [PATCH v6 06/15] lockdep: Handle non(or multi)-acquisition of a crosslock Byungchul Park
2017-03-14 8:18 ` Byungchul Park [this message]
2017-03-14 8:18 ` [PATCH v6 08/15] lockdep: Fix incorrect condition to print bug msgs for MAX_LOCKDEP_CHAIN_HLOCKS Byungchul Park
2017-03-14 8:18 ` [PATCH v6 09/15] lockdep: Make print_circular_bug() aware of crossrelease Byungchul Park
2017-03-14 8:18 ` [PATCH v6 10/15] lockdep: Apply crossrelease to completions Byungchul Park
2017-03-14 8:18 ` [PATCH v6 11/15] pagemap.h: Remove trailing white space Byungchul Park
2017-03-14 8:18 ` [PATCH v6 12/15] lockdep: Apply crossrelease to PG_locked locks Byungchul Park
2017-03-14 8:19 ` [PATCH v6 13/15] lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked Byungchul Park
2017-03-14 8:19 ` [PATCH v6 14/15] lockdep: Move data of CONFIG_LOCKDEP_PAGELOCK from page to page_ext Byungchul Park
2017-03-14 8:19 ` [PATCH v6 15/15] lockdep: Crossrelease feature documentation Byungchul Park
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=1489479542-27030-8-git-send-email-byungchul.park@lge.com \
--to=byungchul.park@lge.com \
--cc=akpm@linux-foundation.org \
--cc=boqun.feng@gmail.com \
--cc=iamjoonsoo.kim@lge.com \
--cc=kernel-team@lge.com \
--cc=kirill@shutemov.name \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mingo@kernel.org \
--cc=npiggin@gmail.com \
--cc=peterz@infradead.org \
--cc=tglx@linutronix.de \
--cc=walken@google.com \
--cc=willy@infradead.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).