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: <20160913150554.GI2794@worktop>
Date:   Tue, 13 Sep 2016 17:05:54 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Byungchul Park <byungchul.park@....com>
Cc:     mingo@...nel.org, tglx@...utronix.de, walken@...gle.com,
        boqun.feng@...il.com, kirill@...temov.name,
        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

So the idea is to add support for non-owner serialization primitives,
like completions/semaphores, and so far I've not looked at the code yet.
I did spend 2+ hours trying to decipher your documentation thing, but am
still confused, that thing is exceedingly hard to parse/read.

So the typical scenario would be something like:

L a	L a
	U a
W b	C b

where L := lock, U := unlock, W := wait_for_completion and C :=
complete.

On the left, the blocking thread we can easily observe the 'b depends on
a' relation, since we block while holding a.

On the right however that same relation is hard to see, since by the
time we would run complete, a has already been released.

I _think_ you propose to keep track of all prior held locks and then use
the union of the held list on the block-chain with the prior held list
from the complete context.

The document describes you have a prior held list, and that its a
circular thing, but it then completely fails to specify what gets added
and how its used.

Also, by it being a circular list (of indeterminate, but finite size),
there is the possibility of missing dependencies if they got spooled out
by recent activity.

The document has an example in the section 'How cross release works'
(the 3rd) that simply cannot be. It lists lock action _after_ acquire,
but you place the acquire in wait_for_completion. We _block_ there.

Is this the general idea?

If so, I cannot see how something like:

W a	W b
C b	C a

would work, somewhere in that document it states that this would be
handled by the existing dependencies, but I cannot see how. The blocking
thread (either one) has no held context, therefore the previously
mentioned union of held and prev-held is empty.

The alternative is not doing the union, but then you end up with endless
pointless dependencies afaict.

On the whole 'release context' thing you want to cast lockdep in, please
consider something like:

L a	L b
L b	L a
U a	U a
U b	U b

Note that the release order of locks is immaterial and can generate
'wrong' dependencies. Note how on both sides a is released under b,
failing to observe the stil obvious AB-BA deadlock.

Note that lockdep doesn't model release or anything, it models
blocked-on relations, like PI does.