linux-kernel - Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20160914081117.GK5008@twins.programming.kicks-ass.net>
Date:   Wed, 14 Sep 2016 10:11:17 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Byungchul Park <max.byungchul.park@...il.com>
Cc:     Byungchul Park <byungchul.park@....com>,
        Ingo Molnar <mingo@...nel.org>, tglx@...utronix.de,
        Michel Lespinasse <walken@...gle.com>, boqun.feng@...il.com,
        kirill@...temov.name,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        linux-mm@...ck.org, iamjoonsoo.kim@....com,
        akpm@...ux-foundation.org, npiggin@...il.com
Subject: Re: [PATCH v3 07/15] lockdep: Implement crossrelease feature

On Wed, Sep 14, 2016 at 11:27:22AM +0900, Byungchul Park wrote:
> > Well, there is, its just not trivially observable. We must be able to
> > acquire a in order to complete b, therefore there is a dependency.
> 
> No. We cannot say there is a dependency unconditionally. There can
> be a dependency or not.
> 
> L a     L a
>         U a
> ~~~~~~~~~ what if serialized by something?

Well, there's no serialization in the example, so no what if.

> W b     C b
> 
> If something we don't recognize serializes locks, which ensures
> 'W b' happens after 'L a , U a' in the other context, then there's
> no dependency here.

Its not there.

> We should say 'b depends on a' in only case that the sequence
> 'W b and then L a and then C b, where last two ops are in same
> context' _actually_ happened at least once. Otherwise, it might
> add a false dependency.
> 
> It's same as how original lockdep works with typical locks. It adds
> a dependency only when a lock is actually hit.

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.

> > What does that mean? Any why? This is a random point in time without
> > actual meaning.
> 
> It's not random point. We have to consider meaningful sequences among
> those which are globally observable. That's why we need to serialize
> those locks.

Serialize how? there is no serialization.

> For example,
> 
> W b
> L a
> U a
> C b
> 
> Once this sequence is observable globally, we can say 'It's possible to
> run in this sequence. Is this sequence problematic or not?'.
> 
> L a
> U a
> W b
> C b
> 
> If only this sequence can be observable, we should not assume
> this sequence can be changed. However once the former sequence
> happens, it has a possibility to hit the same sequence again later.
> So we can check deadlock possibility with the sequence,
> 
> _not randomly_.

I still don't get it.

> We need to connect between the crosslock and the first lock among
> locks having been acquired since the crosslock was held.

Which can be _any_ lock in the history of that thread. It could be
rq->lock from getting the thread scheduled.

> Others will be
> connected each other by original lockdep.
> 
> By the way, does my document miss this description? If so, sorry.
> I will check and update it.

I couldn't find anything useful, but then I could not understand most of
what was written, and I tried hard :-(