linux-kernel - Re: [RFC PATCH v7 1/7] Restartable sequences system call

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:	Wed, 3 Aug 2016 09:37:57 -0700
From:	Andy Lutomirski <luto@...capital.net>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Russell King <linux@....linux.org.uk>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...hat.com>,
	"H. Peter Anvin" <hpa@...or.com>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	linux-api <linux-api@...r.kernel.org>,
	Paul Turner <pjt@...gle.com>, Andrew Hunter <ahh@...gle.com>,
	Andi Kleen <andi@...stfloor.org>,
	Dave Watson <davejwatson@...com>, Chris Lameter <cl@...ux.com>,
	Ben Maurer <bmaurer@...com>, rostedt <rostedt@...dmis.org>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	Josh Triplett <josh@...htriplett.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Catalin Marinas <catalin.marinas@....com>,
	Will Deacon <will.deacon@....com>,
	Michael Kerrisk <mtk.manpages@...il.com>,
	Boqun Feng <boqun.feng@...il.com>
Subject: Re: [RFC PATCH v7 1/7] Restartable sequences system call

On Wed, Aug 3, 2016 at 5:27 AM, Peter Zijlstra <peterz@...radead.org> wrote:
> On Tue, Jul 26, 2016 at 03:02:19AM +0000, Mathieu Desnoyers wrote:
>> We really care about preemption here. Every migration implies a
>> preemption from a user-space perspective. If we would only care
>> about keeping the CPU id up-to-date, hooking into migration would be
>> enough. But since we want atomicity guarantees for restartable
>> sequences, we need to hook into preemption.
>
>> It allows user-space to perform update operations on per-cpu data without
>> requiring heavy-weight atomic operations.
>
> Well, a CMPXCHG without LOCK prefix isn't all that expensive on x86.
>
> It is however on PPC and possibly other architectures, so in name of
> simplicity supporting only the one variant makes sense.
>

I wouldn't want to depend on CMPXCHG.  But imagine we had primitives
that were narrower than the full abort-on-preemption primitive.
Specifically, suppose we had abort if (actual cpu != expected_cpu ||
*aptr != aval).  We could do things like:

expected_cpu = cpu;
aval = NULL;  // disarm for now
begin();
aval = event_count[cpu] + 1;
event_count[cpu] = aval;
event_count[cpu]++;

... compute something ...

// arm the rest of it
aptr = &event_count[cpu];
if (*aptr != aval)
  goto fail;

*thing_im_writing = value_i_computed;
end();

The idea here is that we don't rely on the scheduler to increment the
event count at all, which means that we get to determine the scope of
what kinds of access conflicts we care about ourselves.

This has an obvious downside: it's more complicated.

It has several benefits, I think.  It's debuggable without hassle
(unless someone, accidentally or otherwise, sets aval incorrectly).
It also allows much longer critical sections to work well, as merely
being preempted in the middle won't cause an abort any more.

So I'm hoping to understand whether we could make something like this
work.  This whole thing is roughly equivalent to abort-if-migrated
plus an atomic "if (*aptr == aval) *b = c;" operation.

(I think that, if this worked, we could improve it a bit by making the
abort operation jump back to the "if (*aptr != aval) goto fail;" code,
which should reduce the scope for error a bit and also reduces the
need for extra code paths that only execute on an abort.)