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]

Date:   Mon, 19 Sep 2016 10:50:09 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Byungchul Park <byungchul.park@....com>
Cc:     Byungchul Park <max.byungchul.park@...il.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 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.

> 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?

				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>

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).

What we want here is to link z to b, no? That is the last, not the first
acquire, it also is independent of when W happened.

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>

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...