| 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
| ||
|
Message-ID: <20170110200850.GE3092@twins.programming.kicks-ass.net>
Date: Tue, 10 Jan 2017 21:08:50 +0100
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 v4 15/15] lockdep: Crossrelease feature documentation
First off my sincere apologies for being so horribly slow with this :/
I did spend some time thinking about this thing during the Christmas
holidays, but have not yet managed to write a coherent text on it like I
promised I'd do.
That said; I think I now mostly understand what and why.
But I still feel this document is very hard to read and presents things
backwards.
> +Let's take a look at more complicated example.
> +
> + TASK X TASK Y
> + ------ ------
> + acquire B
> +
> + release B
> +
> + acquire C
> +
> + release C
> + (1)
> + fork Y
> + acquire AX
> + acquire D
> + /* A dependency 'AX -> D' exists */
> + acquire F
> + release D
> + acquire G
> + /* A dependency 'F -> G' exists */
> + acquire E
> + /* A dependency 'AX -> E' exists */
> + acquire H
> + /* A dependency 'G -> H' exists */
> + release E
> + release H
> + release AX held by Y
> + release G
> +
> + release F
> +
> + where AX, B, C,..., H are different lock classes, and a suffix 'X' is
> + added on crosslocks.
> +
> +Does a dependency 'AX -> B' exist? Nope.
I think the above without the "fork Y" line is a much more interesting
example, because then the answer becomes: maybe.
This all boils down to the asynchonous nature of the primitive. There is
no well defined point other than what is observed (as I think you tried
to point out in our earlier exchanges).
The "acquire AX" point is entirely random wrt any action in other
threads, _however_ the time between "acquire" and "release" of any
'lock' is the only time we can be certain of things.
> +==============
> +Implementation
> +==============
> +
> +Data structures
> +---------------
> +
> +Crossrelease feature introduces two main data structures.
> +
> +1. pend_lock
I'm not sure 'pending' is the right name here, but I'll consider that
more when I review the code patches.
> +
> + This is an array embedded in task_struct, for keeping locks queued so
> + that real dependencies can be added using them at commit step. Since
> + it's local data, it can be accessed locklessly in the owner context.
> + The array is filled at acquire step and consumed at commit step. And
> + it's managed in circular manner.
> +
> +2. cross_lock
> +
> + This is a global linked list, for keeping all crosslocks in progress.
> + The list grows at acquire step and is shrunk at release step.
FWIW, this is a perfect example of why I say the document is written
backwards. At this point there is no demonstrated need or use for this
list.
> +
> +CONCLUSION
> +
> +Crossrelease feature introduces two main data structures.
> +
> +1. A pend_lock array for queueing typical locks in circular manner.
> +2. A cross_lock linked list for managing crosslocks in progress.
> +
> +
> +How crossrelease works
> +----------------------
> +
> +Let's take a look at how crossrelease feature works step by step,
> +starting from how lockdep works without crossrelease feaure.
> +
> +
> +Let's look at how commit works for crosslocks.
> +
> + AX's RELEASE CONTEXT AX's ACQUIRE CONTEXT
> + -------------------- --------------------
> + acquire AX
> + /*
> + * 1. Mark AX as started
> + *
> + * (No queuing for crosslocks)
> + *
> + * In pend_lock: Empty
> + * In graph: Empty
> + */
> +
> + (serialized by some means e.g. barrier)
> +
> + acquire D
> + /*
> + * (No marking for typical locks)
> + *
> + * 1. Queue D
> + *
> + * In pend_lock: D
> + * In graph: Empty
> + */
> + acquire B
> + /*
> + * (No marking for typical locks)
> + *
> + * 1. Queue B
> + *
> + * In pend_lock: B
> + * In graph: Empty
> + */
> + release D
> + /*
> + * (No commit for typical locks)
> + *
> + * In pend_lock: D
> + * In graph: Empty
> + */
> + acquire C
> + /*
> + * (No marking for typical locks)
> + *
> + * 1. Add 'B -> C' of TT type
> + * 2. Queue C
> + *
> + * In pend_lock: B, C
> + * In graph: 'B -> C'
> + */
> + acquire E
> + /*
> + * (No marking for typical locks)
> + *
> + * 1. Queue E
> + *
> + * In pend_lock: D, E
> + * In graph: 'B -> C'
> + */
> + acquire D
> + /*
> + * (No marking for typical locks)
> + *
> + * 1. Add 'C -> D' of TT type
> + * 2. Queue D
> + *
> + * In pend_lock: B, C, D
> + * In graph: 'B -> C', 'C -> D'
> + */
> + release E
> + /*
> + * (No commit for typical locks)
> + *
> + * In pend_lock: D, E
> + * In graph: 'B -> C', 'C -> D'
> + */
> + release D
> + /*
> + * (No commit for typical locks)
> + *
> + * In pend_lock: B, C, D
> + * In graph: 'B -> C', 'C -> D'
> + */
> + release AX
> + /*
> + * 1. Commit AX (= Add 'AX -> ?')
> + * a. What queued since AX was marked: D, E
> + * b. Add 'AX -> D' of CT type
> + * c. Add 'AX -> E' of CT type
OK, so commit adds multiple dependencies, that makes more sense.
Previously I understood commit to only add a single dependency, which
does not make sense (except in the special case where there is but one).
I dislike how I have to reconstruct this from an example instead of
first having had the rules stated though.
> + *
> + * In pend_lock: D, E
> + * In graph: 'B -> C', 'C -> D',
> + * 'AX -> D', 'AX -> E'
> + */
Powered by blists - more mailing lists