memory ordering

[Edward Z. Yang]

Hello John,

Here are some prior discussions (which I will attempt to summarize
below):

    http://www.haskell.org/pipermail/haskell-cafe/2011-May/091878.html
    http://www.haskell.org/pipermail/haskell-prime/2006-April/001237.html
    http://www.haskell.org/pipermail/haskell-prime/2006-March/001079.html

The guarantees that Haskell and GHC give in this area are hand-wavy at
best; at the moment, I don't think Haskell or GHC have a formal memory
model—this seems to be an open research problem. (Unfortunately, AFAICT
all the researchers working on relaxed memory models have their hands
full with things like C++ :-)

If you want to go ahead and build something that /just/ works for a
/specific version/ of GHC, you will need to answer this question
separately for every phase of the compiler.  For Core and STG, monads
will preserve ordering, so there is no trouble.  However, for C--, we
will almost certainly apply optimizations which reorder reads (look at
CmmSink.hs).  To properly support your algorithm, you will have to add
some new read barrier mach-ops, and teach the optimizer to respect them.
(This could be fiendishly subtle; it might be better to give C-- a
memory model first.)  These mach-ops would then translate into
appropriate arch-specific assembly or LLVM instructions, preserving
the guarantees further.

This is not related to your original question, but the situation is a
bit better with regards to reordering stores: we have a WriteBarrier
MachOp, which in principle, prevents store reordering.  In practice, we
don't seem to actually have any C-- optimizations that reorder stores.
So, at least you can assume these will work OK!

Hope this helps (and is not too inaccurate),
Edward

Excerpts from John Lato's message of 2013-12-20 09:36:11 +0800:
> Hello,
> 
> I'm working on a lock-free algorithm that's meant to be used in a
> concurrent setting, and I've run into a possible issue.
> 
> The crux of the matter is that a particular function needs to perform the
> following:
> 
> > x <- MVector.read vec ix
> > position <- readIORef posRef
> 
> and the algorithm is only safe if these two reads are not reordered (both
> the vector and IORef are written to by other threads).
> 
> My concern is, according to standard Haskell semantics this should be safe,
> as IO sequencing should guarantee that the reads happen in-order.  Of
> course this also relies upon the architecture's memory model, but x86 also
> guarantees that reads happen in order.  However doubts remain; I do not
> have confidence that the code generator will handle this properly.  In
> particular, LLVM may freely re-order loads of NotAtomic and Unordered
> values.
> 
> The one hope I have is that ghc will preserve IO semantics through the
> entire pipeline.  This seems like it would be necessary for proper handling
> of exceptions, for example.  So, can anyone tell me if my worries are
> unfounded, or if there's any way to ensure the behavior I want?  I could
> change the readIORef to an atomicModifyIORef, which should issue an mfence,
> but that seems a bit heavy-handed as just a read fence would be sufficient
> (although even that seems more than necessary).
> 
> Thanks,
> John L.