Re: [PATCH] Linux: Implement membarrier function
Hi Paul, thank you for thinking about all this.
I think the modelling you suggest captures most of the algorithms I
would want to write. I think it's slightly too weak, though, to
implement the model suggested in P1202R0[1], which permits the SC
outcome to be recovered in C-Goldblat-memb-2[2] by inserting a second
smp_memb() after the first, which is a rather nice property (and I
believe is supported by the underlying implementation options). I
afraid though that I'm not familiar enough with the Linux herd
definitions to suggest a tweak (or know how easy a tweak might be).
- David
[1] Which I think may be strengthened a little bit more even in R1.
[2] As a nit, my name has two "t"'s in it, although I'd throw into the
ring "memb-pairwise", "memb-nontransitive", and "memb-sequenced" if
these get non-placeholder names.
On Thu, Dec 6, 2018 at 1:54 PM Paul E. McKenney wrote:
>
> Hello, David,
>
> I took a crack at extending LKMM to accommodate what I think would
> support what you have in your paper. Please see the very end of this
> email for a patch against the "dev" branch of my -rcu tree.
>
> This gives the expected result for the following three litmus tests,
> but is probably deficient or otherwise misguided in other ways. I have
> added the LKMM maintainers on CC for their amusement. ;-)
>
> Thoughts?
>
> Thanx, Paul
>
>
>
> C C-Goldblat-memb-1
> {
> }
>
> P0(int *x0, int *x1)
> {
> WRITE_ONCE(*x0, 1);
> r1 = READ_ONCE(*x1);
> }
>
>
> P1(int *x0, int *x1)
> {
> WRITE_ONCE(*x1, 1);
> smp_memb();
> r2 = READ_ONCE(*x0);
> }
>
> exists (0:r1=0 /\ 1:r2=0)
>
>
>
> C C-Goldblat-memb-2
> {
> }
>
> P0(int *x0, int *x1)
> {
> WRITE_ONCE(*x0, 1);
> r1 = READ_ONCE(*x1);
> }
>
>
> P1(int *x1, int *x2)
> {
> WRITE_ONCE(*x1, 1);
> smp_memb();
> r1 = READ_ONCE(*x2);
> }
>
> P2(int *x2, int *x0)
> {
> WRITE_ONCE(*x2, 1);
> r1 = READ_ONCE(*x0);
> }
>
> exists (0:r1=0 /\ 1:r1=0 /\ 2:r1=0)
>
>
>
> C C-Goldblat-memb-3
> {
> }
>
> P0(int *x0, int *x1)
> {
> WRITE_ONCE(*x0, 1);
> r1 = READ_ONCE(*x1);
> }
>
>
> P1(int *x1, int *x2)
> {
> WRITE_ONCE(*x1, 1);
> smp_memb();
> r1 = READ_ONCE(*x2);
> }
>
> P2(int *x2, int *x3)
> {
> WRITE_ONCE(*x2, 1);
> r1 = READ_ONCE(*x3);
> }
>
> P3(int *x3, int *x0)
> {
> WRITE_ONCE(*x3, 1);
> smp_memb();
> r1 = READ_ONCE(*x0);
> }
>
> exists (0:r1=0 /\ 1:r1=0 /\ 2:r1=0 /\ 3:r1=0)
>
>
>
> On Thu, Nov 29, 2018 at 11:02:17AM -0800, David Goldblatt wrote:
> > One note with the suggested patch is that
> > `atomic_thread_fence(memory_order_acq_rel)` should probably be
> > `atomic_thread_fence (memory_order_seq_cst)` (otherwise the call would
> > be a no-op on, say, x86, which it very much isn't).
> >
> > The non-transitivity thing makes the resulting description arguably
> > incorrect, but this is informal enough that it might not be a big deal
> > to add something after "For these threads, the membarrier function
> > call turns an existing compiler barrier (see above) executed by these
> > threads into full memory barriers" that clarifies it. E.g. you could
> > make it into "turns an existing compiler barrier [...] into full
> > memory barriers, with respect to the calling thread".
> >
> > Since this is targeting the description of the OS call (and doesn't
> > have to concern itself with also being implementable by other
> > asymmetric techniques or degrading to architectural barriers), I think
> > that the description in "approach 2" in P1202 would also make sense
> > for a formal description of the syscall. (Of course, without the
> > kernel itself committing to a rigorous semantics, anything specified
> > on top of it will be on slightly shaky ground).
> >
> > - David
> >
> > On Thu, Nov 29, 2018 at 7:04 AM Paul E. McKenney
> > wrote:
> > >
> > > On Thu, Nov 29, 2018 at 09:44:22AM -0500, Mathieu Desnoyers wrote:
> > > > - On Nov 29, 2018, at 8:50 AM, Florian Weimer fwei...@redhat.com
> > >
Re: [PATCH v2 0/2] mm: introduce MAP_FIXED_SAFE
(+cc the jemalloc jasone; -cc,+bcc the Google jasone). The only time we would want MAP_FIXED (or rather, a non-broken variant) is in the middle of trying to expand an allocation in place; "atomic address range probing in the multithreaded programs" describes our use case pretty well. That's in a pathway that usually fails; it's pretty far down on our kernel mmap enhancements wish-list. (Sorry if you get this twice, an html reply bounced). On Wed, Dec 13, 2017 at 5:35 PM, David Goldblatt <davidtgoldbl...@gmail.com> wrote: > (+cc the jemalloc jasone; -cc,+bcc the Google jasone). > > The only time we would want MAP_FIXED (or rather, a non-broken variant) is > in the middle of trying to expand an allocation in place; "atomic address > range probing in the multithreaded programs" describes our use case pretty > well. That's in a pathway that usually fails; it's pretty far down on our > kernel mmap enhancements wish-list. > > On Wed, Dec 13, 2017 at 4:32 PM, Andrew Morton <a...@linux-foundation.org> > wrote: >> >> On Wed, 13 Dec 2017 10:25:48 +0100 Michal Hocko <mho...@kernel.org> wrote: >> >> > >> > Hi, >> > I am resending with some minor updates based on Michael's review and >> > ask for inclusion. There haven't been any fundamental objections for >> > the RFC [1] nor the previous version [2]. The biggest discussion >> > revolved around the naming. There were many suggestions flowing >> > around MAP_REQUIRED, MAP_EXACT, MAP_FIXED_NOCLOBBER, MAP_AT_ADDR, >> > MAP_FIXED_NOREPLACE etc... >> >> I like MAP_FIXED_CAREFUL :) >> >> > I am afraid we can bikeshed this to death and there will still be >> > somebody finding yet another better name. Therefore I've decided to >> > stick with my original MAP_FIXED_SAFE. Why? Well, because it keeps the >> > MAP_FIXED prefix which should be recognized by developers and _SAFE >> > suffix should also be clear that all dangerous side effects of the old >> > MAP_FIXED are gone. >> > >> > If somebody _really_ hates this then feel free to nack and resubmit >> > with a different name you can find a consensus for. I am sorry to be >> > stubborn here but I would rather have this merged than go over few more >> > iterations changing the name just because it seems like a good idea >> > now. My experience tells me that chances are that the name will turn out >> > to be "suboptimal" anyway over time. >> > >> > Some more background: >> > This has started as a follow up discussion [3][4] resulting in the >> > runtime failure caused by hardening patch [5] which removes MAP_FIXED >> > from the elf loader because MAP_FIXED is inherently dangerous as it >> > might silently clobber an existing underlying mapping (e.g. stack). The >> > reason for the failure is that some architectures enforce an alignment >> > for the given address hint without MAP_FIXED used (e.g. for shared or >> > file backed mappings). >> > >> > One way around this would be excluding those archs which do alignment >> > tricks from the hardening [6]. The patch is really trivial but it has >> > been objected, rightfully so, that this screams for a more generic >> > solution. We basically want a non-destructive MAP_FIXED. >> > >> > The first patch introduced MAP_FIXED_SAFE which enforces the given >> > address but unlike MAP_FIXED it fails with EEXIST if the given range >> > conflicts with an existing one. The flag is introduced as a completely >> > new one rather than a MAP_FIXED extension because of the backward >> > compatibility. We really want a never-clobber semantic even on older >> > kernels which do not recognize the flag. Unfortunately mmap sucks wrt. >> > flags evaluation because we do not EINVAL on unknown flags. On those >> > kernels we would simply use the traditional hint based semantic so the >> > caller can still get a different address (which sucks) but at least not >> > silently corrupt an existing mapping. I do not see a good way around >> > that. Except we won't export expose the new semantic to the userspace at >> > all. >> > >> > It seems there are users who would like to have something like that. >> > Jemalloc has been mentioned by Michael Ellerman [7] >> >> http://lkml.kernel.org/r/87efp1w7vy@concordia.ellerman.id.au. >> >> It would be useful to get feedback from jemalloc developers (please). >> I'll add some cc's. >> >> >> > Florian Weimer has mentioned the following: >>
Re: [PATCH v2 0/2] mm: introduce MAP_FIXED_SAFE
(+cc the jemalloc jasone; -cc,+bcc the Google jasone). The only time we would want MAP_FIXED (or rather, a non-broken variant) is in the middle of trying to expand an allocation in place; "atomic address range probing in the multithreaded programs" describes our use case pretty well. That's in a pathway that usually fails; it's pretty far down on our kernel mmap enhancements wish-list. (Sorry if you get this twice, an html reply bounced). On Wed, Dec 13, 2017 at 5:35 PM, David Goldblatt wrote: > (+cc the jemalloc jasone; -cc,+bcc the Google jasone). > > The only time we would want MAP_FIXED (or rather, a non-broken variant) is > in the middle of trying to expand an allocation in place; "atomic address > range probing in the multithreaded programs" describes our use case pretty > well. That's in a pathway that usually fails; it's pretty far down on our > kernel mmap enhancements wish-list. > > On Wed, Dec 13, 2017 at 4:32 PM, Andrew Morton > wrote: >> >> On Wed, 13 Dec 2017 10:25:48 +0100 Michal Hocko wrote: >> >> > >> > Hi, >> > I am resending with some minor updates based on Michael's review and >> > ask for inclusion. There haven't been any fundamental objections for >> > the RFC [1] nor the previous version [2]. The biggest discussion >> > revolved around the naming. There were many suggestions flowing >> > around MAP_REQUIRED, MAP_EXACT, MAP_FIXED_NOCLOBBER, MAP_AT_ADDR, >> > MAP_FIXED_NOREPLACE etc... >> >> I like MAP_FIXED_CAREFUL :) >> >> > I am afraid we can bikeshed this to death and there will still be >> > somebody finding yet another better name. Therefore I've decided to >> > stick with my original MAP_FIXED_SAFE. Why? Well, because it keeps the >> > MAP_FIXED prefix which should be recognized by developers and _SAFE >> > suffix should also be clear that all dangerous side effects of the old >> > MAP_FIXED are gone. >> > >> > If somebody _really_ hates this then feel free to nack and resubmit >> > with a different name you can find a consensus for. I am sorry to be >> > stubborn here but I would rather have this merged than go over few more >> > iterations changing the name just because it seems like a good idea >> > now. My experience tells me that chances are that the name will turn out >> > to be "suboptimal" anyway over time. >> > >> > Some more background: >> > This has started as a follow up discussion [3][4] resulting in the >> > runtime failure caused by hardening patch [5] which removes MAP_FIXED >> > from the elf loader because MAP_FIXED is inherently dangerous as it >> > might silently clobber an existing underlying mapping (e.g. stack). The >> > reason for the failure is that some architectures enforce an alignment >> > for the given address hint without MAP_FIXED used (e.g. for shared or >> > file backed mappings). >> > >> > One way around this would be excluding those archs which do alignment >> > tricks from the hardening [6]. The patch is really trivial but it has >> > been objected, rightfully so, that this screams for a more generic >> > solution. We basically want a non-destructive MAP_FIXED. >> > >> > The first patch introduced MAP_FIXED_SAFE which enforces the given >> > address but unlike MAP_FIXED it fails with EEXIST if the given range >> > conflicts with an existing one. The flag is introduced as a completely >> > new one rather than a MAP_FIXED extension because of the backward >> > compatibility. We really want a never-clobber semantic even on older >> > kernels which do not recognize the flag. Unfortunately mmap sucks wrt. >> > flags evaluation because we do not EINVAL on unknown flags. On those >> > kernels we would simply use the traditional hint based semantic so the >> > caller can still get a different address (which sucks) but at least not >> > silently corrupt an existing mapping. I do not see a good way around >> > that. Except we won't export expose the new semantic to the userspace at >> > all. >> > >> > It seems there are users who would like to have something like that. >> > Jemalloc has been mentioned by Michael Ellerman [7] >> >> http://lkml.kernel.org/r/87efp1w7vy@concordia.ellerman.id.au. >> >> It would be useful to get feedback from jemalloc developers (please). >> I'll add some cc's. >> >> >> > Florian Weimer has mentioned the following: >> > : glibc ld.so currently maps DSOs without hints. This means that the >> > ker
