From: Byungchul Park <byungchul.park@lge.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: Byungchul Park <max.byungchul.park@gmail.com>,
Ingo Molnar <mingo@kernel.org>,
tglx@linutronix.de, Michel Lespinasse <walken@google.com>,
boqun.feng@gmail.com, kirill@shutemov.name,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
linux-mm@kvack.org, iamjoonsoo.kim@lge.com,
akpm@linux-foundation.org, npiggin@gmail.com
Subject: Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature
Date: Wed, 21 Sep 2016 10:37:30 +0900 [thread overview]
Message-ID: <20160921013730.GN2279@X58A-UD3R> (raw)
In-Reply-To: <20160920055038.GL2279@X58A-UD3R>
On Tue, Sep 20, 2016 at 02:50:38PM +0900, Byungchul Park wrote:
> On Mon, Sep 19, 2016 at 10:50:09AM +0200, Peter Zijlstra wrote:
> > On Mon, Sep 19, 2016 at 11:41:02AM +0900, Byungchul Park wrote:
> >
> > > > But since these threads are independently scheduled there is no point in
> > > > transferring the point in time thread A does W to thread B. There is no
> > > > relation there.
> > > >
> > > > B could have already executed the complete or it could not yet have
> > > > started execution at all or anything in between, entirely random.
> > >
> > > Of course B could have already executed the complete or it could not yet
> > > have started execution at all or anything in between. But it's not entirely
> > > random.
> > >
> > > It might be a random point since they are independently scheduled, but it's
> > > not entirely random. And it's a random point among valid points which lockdep
> > > needs to consider. For example,
> > >
> > >
> > > CONTEXT 1 CONTEXT 2(forked one)
> > > ========= =====================
> > > (a) acquire F
> > > acquire A acquire G
> > > acquire B wait_for_completion Z
> > > acquire C
> > > (b) acquire H
> > > fork 2 acquire I
> > > acquire D acquire J
> > > complete Z acquire K
> > >
> >
> > I'm hoping you left out the releases for brevity? Because calling fork()
> > with locks held is _really_ poor form.
>
> Exactly. Sorry. I shouldn't have omitted releases.
>
> >
> > > I can provide countless examples with which I can say you're wrong.
> > > In this case, all acquires between (a) and (b) must be ignored when
> > > generating dependencies with complete operation of Z.
> >
> > I still don't get the point. Why does this matter?
> >
> > Sure, A-C are irrelevant in this example, but I don't see how they're
> > differently irrelevant from a whole bunch of other prior state action.
> >
> >
> > Earlier you said the algorithm for selecting the dependency is the first
> > acquire observed in the completing thread after the
> > wait_for_completion(). Is this correct?
>
> Sorry for insufficient description.
>
> held_locks of left context will be,
>
> time 1: a
> time 2: a, x[0]
> time 3: a, x[1]
> ...
> time n: b
>
> Between time 1 and time (n-1), 'a' will be the first among held_locks. At
> time n, 'b' will be the fist among held_locks. So 'a' and 'b' should be
> connected to 'z' if we ignore IRQ context. (I will explain it soon.)
>
> Acquire x[i] is also valid one but crossrelease doesn't take it into
> account since original lockdep will cover using 'a -> x[i]'. So only
... since lockdep will cover 'z -> x[i]' using 'z -> a' and 'a -> x[i]' ...
> connections we need are 'z -> a' and 'z -> b'.
>
> >
> >
> > W z
> >
> > A a
> > for (i<0;i<many;i++) {
> > A x[i]
> > R x[i]
> > }
> > R a
> >
> > <IRQ>
> > A b
> > R b
> > C z
> > </IRQ>
>
> My crossrelease implementation distinguishes each IRQ from normal context
> or other IRQs in different timeline, even though they might share
> held_locks. So in this example, precisely speaking, there are two different
> contexts. One is normal context and the other is IRQ context. So only 'A b'
> is related with 'W z' in this example.
>
> >
> > That would be 'a' in this case, but that isn't at all related. Its just
> > as irrelevant as your A-C. And we can pick @many as big as needed to
> > flush the prev held cyclic buffer (although I've no idea how that
> > matters either).
>
> I designed crossrelease so that x[i] is not added into ring buffer because
> adding 'z -> a' is sufficient and x[i] doesn't need to be taken into
> account in this case.
>
> >
> > What we want here is to link z to b, no? That is the last, not the first
>
> Exactly right. Only 'z -> b' must be added under considering IRQ context.
> That is the first among held_locks in the IRQ context.
>
> > acquire, it also is independent of when W happened.
>
> If the IRQ is really random, then it can happen before W z and it can also
> happen after W z. We cannot determine the time. Then we need to consider all
> combination and possibility. It's a key point. We have to consider
> dependencies for all possibility.
possibilities.
>
> However, we don't know what synchronizes the flow. So it must be based on
^^^
generally
> what actually happened, to identify true dependencies.
>
> >
> > At the same time, picking the last is no guarantee either, since that
> > can equally miss dependencies. Suppose the IRQ handler did:
> >
> > <IRQ>
> > A c
> > R c
> > A b
> > R b
> > C z
> > </IRQ>
> >
>
> time 1: c (in held_locks)
> time 2: b (in held_locks)
>
> So 'c' and 'b' can be the first among held_locks at each moment.
^^^^^^
are
> So 'z -> b' and 'z -> c' will be added.
>
> > instead. We'd miss the z depends on c relation, and since they're
> > independent lock sections, lockdep wouldn't make a b-c relation either.
> >
> >
> > Clearly I'm still missing stuff...
>
> Sorry for insufficient description. I tried to describ crossrelease in as
> much detail as possible, really.
>
> The reason why I consider only the first among valid locks in held_locks is
> simple. For example,
>
> Context 1
> A a -> A b -> A crosslock -> R a -> R b
I meant,
Context 1
=========
A a
A b
A crosslock
R a
R b
>
> Context 2
> A c -> A d -> R d -> R the crosslock -> R c
Context 2
=========
A c
A d
R d
R the crosslock
R c
>
> If 'A c' after 'A crosslock' is possible, then 'A crosslock' does not only
> depends on 'A c' but also 'A d'. But all dependencies we need to add is only
> 'crosslock -> c' because 'crosslock -> d' will be covered by 'crosslock ->
> c' and 'a -> b'. Here, 'a -> b' is added by original lockdep.
next prev parent reply other threads:[~2016-09-21 1:40 UTC|newest]
Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-09-13 9:44 [PATCH v3 00/15] lockdep: Implement crossrelease feature Byungchul Park
2016-09-13 9:45 ` [PATCH v3 01/15] x86/dumpstack: Optimize save_stack_trace Byungchul Park
2016-09-13 13:18 ` Josh Poimboeuf
2016-09-13 14:54 ` Byungchul Park
2016-09-13 9:45 ` [PATCH v3 02/15] x86/dumpstack: Add save_stack_trace()_fast() Byungchul Park
2016-09-13 13:20 ` Josh Poimboeuf
2016-09-13 9:45 ` [PATCH v3 03/15] lockdep: Refactor lookup_chain_cache() Byungchul Park
2016-09-15 15:33 ` Nilay Vaish
2016-09-19 3:05 ` Byungchul Park
2016-09-19 16:36 ` Nilay Vaish
2016-09-20 2:00 ` Byungchul Park
2016-09-13 9:45 ` [PATCH v3 04/15] lockdep: Add a function building a chain between two classes Byungchul Park
2016-09-13 9:45 ` [PATCH v3 05/15] lockdep: Make check_prev_add can use a separate stack_trace Byungchul Park
2016-09-13 9:45 ` [PATCH v3 06/15] lockdep: Make save_trace can skip stack tracing of the current Byungchul Park
2016-09-13 9:45 ` [PATCH v3 07/15] lockdep: Implement crossrelease feature Byungchul Park
2016-09-13 10:05 ` Peter Zijlstra
2016-09-13 12:09 ` Peter Zijlstra
2016-09-13 15:14 ` Byungchul Park
2016-09-13 15:05 ` Peter Zijlstra
2016-09-13 17:12 ` Byungchul Park
2016-09-13 19:38 ` Peter Zijlstra
2016-09-13 21:42 ` Peter Zijlstra
2016-09-14 1:01 ` Byungchul Park
2016-09-14 2:27 ` Byungchul Park
2016-09-14 4:49 ` Byungchul Park
2016-09-14 8:11 ` Peter Zijlstra
2016-09-19 2:41 ` Byungchul Park
2016-09-19 8:50 ` Peter Zijlstra
2016-09-20 5:50 ` Byungchul Park
2016-09-20 6:26 ` Byungchul Park
2016-09-21 1:37 ` Byungchul Park [this message]
2016-09-22 2:57 ` Byungchul Park
2016-09-13 9:45 ` [PATCH v3 08/15] lockdep: Make crossrelease use save_stack_trace_fast() Byungchul Park
2016-09-13 9:45 ` [PATCH v3 09/15] lockdep: Make print_circular_bug() crosslock-aware Byungchul Park
2016-09-13 9:45 ` [PATCH v3 10/15] lockdep: Apply crossrelease to completion operation Byungchul Park
2016-09-13 9:45 ` [PATCH v3 11/15] pagemap.h: Remove trailing white space Byungchul Park
2016-09-13 9:45 ` [PATCH v3 12/15] lockdep: Apply crossrelease to PG_locked lock Byungchul Park
2016-09-13 9:45 ` [PATCH v3 13/15] lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked Byungchul Park
2016-09-13 9:45 ` [PATCH v3 14/15] lockdep: Move data used in CONFIG_LOCKDEP_PAGELOCK from page to page_ext Byungchul Park
2016-09-13 9:45 ` [PATCH v3 15/15] lockdep: Crossrelease feature documentation Byungchul Park
2016-09-15 17:25 ` Nilay Vaish
2016-09-19 2:59 ` Byungchul Park
2016-09-16 15:47 ` Nilay Vaish
2016-09-19 3:00 ` Byungchul Park
2016-09-20 5:00 ` Byungchul Park
2016-09-13 9:58 ` [FYI] Output of 'cat /proc/lockdep' after applying crossrelease Byungchul Park
2016-11-02 5:42 ` [REVISED DOC on v3] Crossrelease Lockdep Byungchul Park
2016-11-03 8:18 ` Byungchul Park
2016-11-08 2:54 ` 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=20160921013730.GN2279@X58A-UD3R \
--to=byungchul.park@lge.com \
--cc=akpm@linux-foundation.org \
--cc=boqun.feng@gmail.com \
--cc=iamjoonsoo.kim@lge.com \
--cc=kirill@shutemov.name \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=max.byungchul.park@gmail.com \
--cc=mingo@kernel.org \
--cc=npiggin@gmail.com \
--cc=peterz@infradead.org \
--cc=tglx@linutronix.de \
--cc=walken@google.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).