Re: Alternative to signals/sys_membarrier() in liburcu

Re: Alternative to signals/sys_membarrier() in liburcu

[Mathieu Desnoyers]

(sorry for re-send, my mail client tricked me into posting HTML
to lkml)

Hi, 

Michael Sullivan proposed a clever hack abusing mprotect() to 
perform the same effect as sys_membarrier() I submitted a few 
years ago ( https://lkml.org/lkml/2010/4/18/15 ). 

At that time, the sys_membarrier implementation was deemed 
technically sound, but there were not enough users of the system call 
to justify its inclusion. 

So far, the number of users of liburcu has increased, but liburcu 
still appears to be the only direct user of sys_membarrier. On this 
front, we could argue that many other system calls have only 
one user: glibc. In that respect, liburcu is quite similar to glibc. 

So the question as it stands appears to be: would you be comfortable 
having users abuse mprotect(), relying on its side-effect of issuing 
a smp_mb() on each targeted CPU for the TLB shootdown, as 
an effective implementation of process-wide memory barrier ? 

Thoughts ? 

Thanks! 

Mathieu 





From: "Michael Sullivan" <sully@msully.net> 
To: "Mathieu Desnoyers" <mathieu.desnoyers@efficios.com> 
Cc: lttng-dev@lists.lttng.org 
Sent: Thursday, March 12, 2015 12:04:07 PM 
Subject: Re: [lttng-dev] Alternative to signals/sys_membarrier() in liburcu 

On Thu, Mar 12, 2015 at 10:57 AM, Mathieu Desnoyers < mathieu.desnoyers@efficios.com > wrote: 




Even though it depends on internal behavior not currently specified by mprotect, 
I'd very much like to see the prototype you have, 


I ended up posting my code at https://github.com/msullivan/userspace-rcu/tree/msync-barrier . 
The interesting patch is https://github.com/msullivan/userspace-rcu/commit/04656b468d418efbc5d934ab07954eb8395a7ab0 . 

Quick blog post I wrote about it at http://www.msully.net/blog/2015/02/24/forcing-memory-barriers-on-other-cpus-with-mprotect2/ . 
(I talked briefly about sys_membarrier in the post as best as I could piece together from LKML; if my comment on it is inaccurate I can edit the post.) 

-Michael Sullivan 



-- 
Mathieu Desnoyers 
EfficiOS Inc. 
http://www.efficios.com 

_______________________________________________
lttng-dev mailing list
lttng-dev@lists.lttng.org
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Re: Alternative to signals/sys_membarrier() in liburcu

[Paul E. McKenney]

On Thu, Mar 12, 2015 at 08:56:00PM +0000, Mathieu Desnoyers wrote:
> (sorry for re-send, my mail client tricked me into posting HTML
> to lkml)
> 
> Hi, 
> 
> Michael Sullivan proposed a clever hack abusing mprotect() to 
> perform the same effect as sys_membarrier() I submitted a few 
> years ago ( https://lkml.org/lkml/2010/4/18/15 ). 
> 
> At that time, the sys_membarrier implementation was deemed 
> technically sound, but there were not enough users of the system call 
> to justify its inclusion. 
> 
> So far, the number of users of liburcu has increased, but liburcu 
> still appears to be the only direct user of sys_membarrier. On this 
> front, we could argue that many other system calls have only 
> one user: glibc. In that respect, liburcu is quite similar to glibc. 
> 
> So the question as it stands appears to be: would you be comfortable 
> having users abuse mprotect(), relying on its side-effect of issuing 
> a smp_mb() on each targeted CPU for the TLB shootdown, as 
> an effective implementation of process-wide memory barrier ? 
> 
> Thoughts ? 

Are there any architectures left that use hardware-assisted global
TLB invalidation?  On such an architecture, you might not get a memory
barrier except on the CPU executing the mprotect() or munmap().

(Here is hoping that no one does -- it is a cute abuse^Whack otherwise!)

							Thanx, Paul

> Thanks! 
> 
> Mathieu 
> 
> 
> 
> 
> 
> From: "Michael Sullivan" <sully@msully.net> 
> To: "Mathieu Desnoyers" <mathieu.desnoyers@efficios.com> 
> Cc: lttng-dev@lists.lttng.org 
> Sent: Thursday, March 12, 2015 12:04:07 PM 
> Subject: Re: [lttng-dev] Alternative to signals/sys_membarrier() in liburcu 
> 
> On Thu, Mar 12, 2015 at 10:57 AM, Mathieu Desnoyers < mathieu.desnoyers@efficios.com > wrote: 
> 
> 
> 
> 
> Even though it depends on internal behavior not currently specified by mprotect, 
> I'd very much like to see the prototype you have, 
> 
> 
> I ended up posting my code at https://github.com/msullivan/userspace-rcu/tree/msync-barrier . 
> The interesting patch is https://github.com/msullivan/userspace-rcu/commit/04656b468d418efbc5d934ab07954eb8395a7ab0 . 
> 
> Quick blog post I wrote about it at http://www.msully.net/blog/2015/02/24/forcing-memory-barriers-on-other-cpus-with-mprotect2/ . 
> (I talked briefly about sys_membarrier in the post as best as I could piece together from LKML; if my comment on it is inaccurate I can edit the post.) 
> 
> -Michael Sullivan 
> 
> 
> 
> -- 
> Mathieu Desnoyers 
> EfficiOS Inc. 
> http://www.efficios.com 
> 
> _______________________________________________
> lttng-dev mailing list
> lttng-dev@lists.lttng.org
> http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> 

Re: Alternative to signals/sys_membarrier() in liburcu

[Benjamin Herrenschmidt]

On Thu, 2015-03-12 at 14:12 -0700, Paul E. McKenney wrote:
> 
> Are there any architectures left that use hardware-assisted global
> TLB invalidation?  

ARM and PowerPC at least...

Cheers,
Ben.

> On such an architecture, you might not get a memory
> barrier except on the CPU executing the mprotect() or munmap().
> 
> (Here is hoping that no one does -- it is a cute abuse^Whack
> otherwise!)
> 
>   

Re: Alternative to signals/sys_membarrier() in liburcu

[One Thousand Gnomes]

On Thu, 12 Mar 2015 20:56:00 +0000 (UTC)
Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote:

> (sorry for re-send, my mail client tricked me into posting HTML
> to lkml)
> 
> Hi, 
> 
> Michael Sullivan proposed a clever hack abusing mprotect() to 
> perform the same effect as sys_membarrier() I submitted a few 
> years ago ( https://lkml.org/lkml/2010/4/18/15 ). 
> 
> At that time, the sys_membarrier implementation was deemed 
> technically sound, but there were not enough users of the system call 
> to justify its inclusion. 
> 
> So far, the number of users of liburcu has increased, but liburcu 
> still appears to be the only direct user of sys_membarrier. On this 
> front, we could argue that many other system calls have only 
> one user: glibc. In that respect, liburcu is quite similar to glibc. 
> 
> So the question as it stands appears to be: would you be comfortable 
> having users abuse mprotect(), relying on its side-effect of issuing 
> a smp_mb() on each targeted CPU for the TLB shootdown, as 
> an effective implementation of process-wide memory barrier ? 

What are you going to do if some future ARM or x86 CPU update with
hardware TLB shootdown appears ? All your code will start to fail on new
kernels using that property, and in nasty insidious ways.

Also doesn't sun4d have hardware shootdown for 16 processors or less ?

I would have thought a membarrier was a lot safer and it can be made to
do whatever horrible things are needed on different processors (indeed it
could even be a pure libc hotpath if some future cpu grows this ability)

Alan

Re: Alternative to signals/sys_membarrier() in liburcu

[Mathieu Desnoyers]

----- Original Message -----
> From: "One Thousand Gnomes" <gnomes@lxorguk.ukuu.org.uk>
> To: "Mathieu Desnoyers" <mathieu.desnoyers@efficios.com>
> Cc: "Michael Sullivan" <sully@msully.net>, "Peter Zijlstra" <peterz@infradead.org>, "LKML"
> <linux-kernel@vger.kernel.org>, "Steven Rostedt" <rostedt@goodmis.org>, lttng-dev@lists.lttng.org, "Thomas Gleixner"
> <tglx@linutronix.de>, "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>, "Linus Torvalds"
> <torvalds@linux-foundation.org>, "Ingo Molnar" <mingo@kernel.org>
> Sent: Thursday, March 12, 2015 7:59:38 PM
> Subject: Re: Alternative to signals/sys_membarrier() in liburcu
> 
> On Thu, 12 Mar 2015 20:56:00 +0000 (UTC)
> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote:
> 
> > (sorry for re-send, my mail client tricked me into posting HTML
> > to lkml)
> > 
> > Hi,
> > 
> > Michael Sullivan proposed a clever hack abusing mprotect() to
> > perform the same effect as sys_membarrier() I submitted a few
> > years ago ( https://lkml.org/lkml/2010/4/18/15 ).
> > 
> > At that time, the sys_membarrier implementation was deemed
> > technically sound, but there were not enough users of the system call
> > to justify its inclusion.
> > 
> > So far, the number of users of liburcu has increased, but liburcu
> > still appears to be the only direct user of sys_membarrier. On this
> > front, we could argue that many other system calls have only
> > one user: glibc. In that respect, liburcu is quite similar to glibc.
> > 
> > So the question as it stands appears to be: would you be comfortable
> > having users abuse mprotect(), relying on its side-effect of issuing
> > a smp_mb() on each targeted CPU for the TLB shootdown, as
> > an effective implementation of process-wide memory barrier ?
> 
> What are you going to do if some future ARM or x86 CPU update with
> hardware TLB shootdown appears ? All your code will start to fail on new
> kernels using that property, and in nasty insidious ways.

I'd claim that removing the IPIs breaks userspace, of course. :-P

If we start relying on mprotect() implying memory barriers issued
on all CPUs associated with the memory mapping in core user-space
libraries, then whenever those shiny new CPUs show up, we might be
stuck with the IPIs, otherwise we could claim that removing them
breaks userspace. I would really hate to tie in an assumption like
that on mprotect, because that would really be painting ourselves in
a corner.

> 
> Also doesn't sun4d have hardware shootdown for 16 processors or less ?

That's possible. I'm no sun expert though.

> 
> I would have thought a membarrier was a lot safer and it can be made to
> do whatever horrible things are needed on different processors (indeed it
> could even be a pure libc hotpath if some future cpu grows this ability)

I'd really prefer a well-documented system call for that purpose too.

Thanks,

Mathieu

> 
> Alan
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: Alternative to signals/sys_membarrier() in liburcu

[Linus Torvalds]

On Thu, Mar 12, 2015 at 1:53 PM, Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
>
> So the question as it stands appears to be: would you be comfortable
> having users abuse mprotect(), relying on its side-effect of issuing
> a smp_mb() on each targeted CPU for the TLB shootdown, as
> an effective implementation of process-wide memory barrier ?

Be *very* careful.

Just yesterday, in another thread (discussing the auto-numa TLB
performance regression), we were discussing skipping the TLB
invalidates entirely if the mprotect relaxes the protections.

Because if you *used* to be read-only, and them mprotect() something
so that it is read-write, there really is no need to send a TLB
invalidate, at least on x86. You can just change the page tables, and
*if* any entries are stale in the TLB they'll take a microfault on
access and then just reload the TLB.

So mprotect() to a more permissive mode is not necessarily serializing.

Also, you need to make sure that your page is actually in memory,
because otherwise the kernel may end up seeing "oh, it's not even
present", and never flush the TLB at all.

So now you need to mlock that page. Which can be problematic for non-root.

In other words, I'd be a bit leery about it. There may be other
gotcha's about it.

                      Linus

Re: Alternative to signals/sys_membarrier() in liburcu

[Mathieu Desnoyers]

----- Original Message -----
> From: "Linus Torvalds" <torvalds@linux-foundation.org>
> To: "Mathieu Desnoyers" <mathieu.desnoyers@efficios.com>
> Cc: "Michael Sullivan" <sully@msully.net>, lttng-dev@lists.lttng.org, "LKML" <linux-kernel@vger.kernel.org>, "Paul E.
> McKenney" <paulmck@linux.vnet.ibm.com>, "Peter Zijlstra" <peterz@infradead.org>, "Ingo Molnar" <mingo@kernel.org>,
> "Thomas Gleixner" <tglx@linutronix.de>, "Steven Rostedt" <rostedt@goodmis.org>
> Sent: Thursday, March 12, 2015 5:47:05 PM
> Subject: Re: Alternative to signals/sys_membarrier() in liburcu
> 
> On Thu, Mar 12, 2015 at 1:53 PM, Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
> >
> > So the question as it stands appears to be: would you be comfortable
> > having users abuse mprotect(), relying on its side-effect of issuing
> > a smp_mb() on each targeted CPU for the TLB shootdown, as
> > an effective implementation of process-wide memory barrier ?
> 
> Be *very* careful.
> 
> Just yesterday, in another thread (discussing the auto-numa TLB
> performance regression), we were discussing skipping the TLB
> invalidates entirely if the mprotect relaxes the protections.
> 
> Because if you *used* to be read-only, and them mprotect() something
> so that it is read-write, there really is no need to send a TLB
> invalidate, at least on x86. You can just change the page tables, and
> *if* any entries are stale in the TLB they'll take a microfault on
> access and then just reload the TLB.
> 
> So mprotect() to a more permissive mode is not necessarily serializing.

The idea here is to always mprotect() to a more restrictive mode,
which should trigger the TLB shootdown.

> 
> Also, you need to make sure that your page is actually in memory,
> because otherwise the kernel may end up seeing "oh, it's not even
> present", and never flush the TLB at all.
> 
> So now you need to mlock that page. Which can be problematic for non-root.

I'm aware the default amount of locked memory is usually quite low
(64kB here). So we'd need to handle cases where we run out of locked
memory. We could fallback to a slower userspace RCU scheme if this
occurs.

> 
> In other words, I'd be a bit leery about it. There may be other
> gotcha's about it.

Looking again at this old proposed patch (https://lkml.org/lkml/2010/4/18/15)
which adds a few memory barriers around updates to mm_cpumask
for sys_membarrier makes me wonder whether mprotect() may not skip
some CPU from the mask that would actually need to be taken care of
in very narrow race scenarios.

Thanks,

Mathieu


> 
>                       Linus
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: Alternative to signals/sys_membarrier() in liburcu

[Ingo Molnar]

* Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote:

> ----- Original Message -----
> > From: "Linus Torvalds" <torvalds@linux-foundation.org>
> > To: "Mathieu Desnoyers" <mathieu.desnoyers@efficios.com>
> > Cc: "Michael Sullivan" <sully@msully.net>, lttng-dev@lists.lttng.org, "LKML" <linux-kernel@vger.kernel.org>, "Paul E.
> > McKenney" <paulmck@linux.vnet.ibm.com>, "Peter Zijlstra" <peterz@infradead.org>, "Ingo Molnar" <mingo@kernel.org>,
> > "Thomas Gleixner" <tglx@linutronix.de>, "Steven Rostedt" <rostedt@goodmis.org>
> > Sent: Thursday, March 12, 2015 5:47:05 PM
> > Subject: Re: Alternative to signals/sys_membarrier() in liburcu
> > 
> > On Thu, Mar 12, 2015 at 1:53 PM, Mathieu Desnoyers
> > <mathieu.desnoyers@efficios.com> wrote:
> > >
> > > So the question as it stands appears to be: would you be comfortable
> > > having users abuse mprotect(), relying on its side-effect of issuing
> > > a smp_mb() on each targeted CPU for the TLB shootdown, as
> > > an effective implementation of process-wide memory barrier ?
> > 
> > Be *very* careful.
> > 
> > Just yesterday, in another thread (discussing the auto-numa TLB 
> > performance regression), we were discussing skipping the TLB 
> > invalidates entirely if the mprotect relaxes the protections.

We have such code already in mm/mprotect.c, introduced in:

  10c1045f28e8 mm: numa: avoid unnecessary TLB flushes when setting NUMA hinting entries

which does:

                                /* Avoid TLB flush if possible */
                                if (pte_protnone(oldpte))
                                        continue;

> > Because if you *used* to be read-only, and them mprotect() 
> > something so that it is read-write, there really is no need to 
> > send a TLB invalidate, at least on x86. You can just change the 
> > page tables, and *if* any entries are stale in the TLB they'll 
> > take a microfault on access and then just reload the TLB.
> > 
> > So mprotect() to a more permissive mode is not necessarily 
> > serializing.
> 
> The idea here is to always mprotect() to a more restrictive mode, 
> which should trigger the TLB shootdown.

So what happens if a CPU comes around that integrates TLB shootdown 
management into its cache coherency protocol? In such a case IPI 
traffic can be skipped: the memory bus messages take care of TLB 
flushes in most cases.

It's a natural optimization IMHO, because TLB flushes are conceptually 
pretty close to the synchronization mechanisms inherent in data cache 
coherency protocols:

This could be implemented for example by a CPU that knows about ptes 
and handles their modification differently: when a pte is modified it 
will broadcast a MESI invalidation message not just for the cacheline 
belonging to the pte's physical address, but also an 'invalidate TLB' 
MESI message for the pte value's page.

The TLB shootdown would either be guaranteed within the MESI 
transaction, or there would either be a deterministic timing 
guarantee, or some explicit synchronization mechanism (new 
instruction) to make sure the remote TLB(s) got shot down.

Every form of this would be way faster than sending interrupts. New 
OSs could support this by the hardware telling them in which cases the 
TLBs are 'auto-flushed', while old OSs would still be compatible by 
sending (now pointless) TLB shootdown IPIs.

So it's a relatively straightforward hardware optimization IMHO: 
assuming TLB flushes are considered important enough to complicate the 
cacheline state machine (which I think they currently aren't).

So in this case there's no interrupt and no other interruption of the 
remote CPU's flow of execution in any fashion that could advance the 
RCU state machine.

What do you think?

Thanks,

	Ingo

Re: Alternative to signals/sys_membarrier() in liburcu

[Paul E. McKenney]

On Fri, Mar 13, 2015 at 09:07:43AM +0100, Ingo Molnar wrote:
> 
> * Mathieu Desnoyers <mathieu.desnoyers@efficios.com> wrote:
> 
> > ----- Original Message -----
> > > From: "Linus Torvalds" <torvalds@linux-foundation.org>
> > > To: "Mathieu Desnoyers" <mathieu.desnoyers@efficios.com>
> > > Cc: "Michael Sullivan" <sully@msully.net>, lttng-dev@lists.lttng.org, "LKML" <linux-kernel@vger.kernel.org>, "Paul E.
> > > McKenney" <paulmck@linux.vnet.ibm.com>, "Peter Zijlstra" <peterz@infradead.org>, "Ingo Molnar" <mingo@kernel.org>,
> > > "Thomas Gleixner" <tglx@linutronix.de>, "Steven Rostedt" <rostedt@goodmis.org>
> > > Sent: Thursday, March 12, 2015 5:47:05 PM
> > > Subject: Re: Alternative to signals/sys_membarrier() in liburcu
> > > 
> > > On Thu, Mar 12, 2015 at 1:53 PM, Mathieu Desnoyers
> > > <mathieu.desnoyers@efficios.com> wrote:
> > > >
> > > > So the question as it stands appears to be: would you be comfortable
> > > > having users abuse mprotect(), relying on its side-effect of issuing
> > > > a smp_mb() on each targeted CPU for the TLB shootdown, as
> > > > an effective implementation of process-wide memory barrier ?
> > > 
> > > Be *very* careful.
> > > 
> > > Just yesterday, in another thread (discussing the auto-numa TLB 
> > > performance regression), we were discussing skipping the TLB 
> > > invalidates entirely if the mprotect relaxes the protections.
> 
> We have such code already in mm/mprotect.c, introduced in:
> 
>   10c1045f28e8 mm: numa: avoid unnecessary TLB flushes when setting NUMA hinting entries
> 
> which does:
> 
>                                 /* Avoid TLB flush if possible */
>                                 if (pte_protnone(oldpte))
>                                         continue;
> 
> > > Because if you *used* to be read-only, and them mprotect() 
> > > something so that it is read-write, there really is no need to 
> > > send a TLB invalidate, at least on x86. You can just change the 
> > > page tables, and *if* any entries are stale in the TLB they'll 
> > > take a microfault on access and then just reload the TLB.
> > > 
> > > So mprotect() to a more permissive mode is not necessarily 
> > > serializing.
> > 
> > The idea here is to always mprotect() to a more restrictive mode, 
> > which should trigger the TLB shootdown.
> 
> So what happens if a CPU comes around that integrates TLB shootdown 
> management into its cache coherency protocol? In such a case IPI 
> traffic can be skipped: the memory bus messages take care of TLB 
> flushes in most cases.
> 
> It's a natural optimization IMHO, because TLB flushes are conceptually 
> pretty close to the synchronization mechanisms inherent in data cache 
> coherency protocols:
> 
> This could be implemented for example by a CPU that knows about ptes 
> and handles their modification differently: when a pte is modified it 
> will broadcast a MESI invalidation message not just for the cacheline 
> belonging to the pte's physical address, but also an 'invalidate TLB' 
> MESI message for the pte value's page.
> 
> The TLB shootdown would either be guaranteed within the MESI 
> transaction, or there would either be a deterministic timing 
> guarantee, or some explicit synchronization mechanism (new 
> instruction) to make sure the remote TLB(s) got shot down.
> 
> Every form of this would be way faster than sending interrupts. New 
> OSs could support this by the hardware telling them in which cases the 
> TLBs are 'auto-flushed', while old OSs would still be compatible by 
> sending (now pointless) TLB shootdown IPIs.
> 
> So it's a relatively straightforward hardware optimization IMHO: 
> assuming TLB flushes are considered important enough to complicate the 
> cacheline state machine (which I think they currently aren't).
> 
> So in this case there's no interrupt and no other interruption of the 
> remote CPU's flow of execution in any fashion that could advance the 
> RCU state machine.
> 
> What do you think?

I agree -- there really have been systems able to flush remote TLBs
without interrupting the remote CPU.

So, given the fact that the userspace RCU library does now see
some real-world use, is it now time for Mathieu to resubmit his
sys_membarrier() patch?

							Thanx, Paul

Re: [lttng-dev] Alternative to signals/sys_membarrier() in liburcu

[Duncan Sands]

> So, given the fact that the userspace RCU library does now see
> some real-world use, is it now time for Mathieu to resubmit his
> sys_membarrier() patch?

I'm using userspace RCU with success in financial software, so the LTTng project 
isn't the only user.  It works well, but it's not as fast as I'd like.  My 
profiling shows that the performance hit is coming from the memory barriers.  So 
I would very much like to see sys_membarrier go in.

Best wishes, Duncan.