[GHC] #8157: Add a broader set of (C/CMM-based) atomic memory operations

[GHC]

#8157: Add a broader set of (C/CMM-based) atomic memory operations
------------------------------------+-------------------------------------
       Reporter:  rrnewton          |             Owner:
           Type:  bug               |            Status:  new
       Priority:  normal            |         Milestone:
      Component:  Compiler          |           Version:  7.6.3
       Keywords:                    |  Operating System:  Unknown/Multiple
   Architecture:  Unknown/Multiple  |   Type of failure:  None/Unknown
     Difficulty:  Unknown           |         Test Case:
     Blocked By:                    |          Blocking:
Related Tickets:                    |
------------------------------------+-------------------------------------
 This task is a precursor to ticket #7883.  The goal is to standardize
 a broader set of atomic ops -- mainly CAS and fetch-and-add -- and
 then in #7883 we will optimize those primops to have native support in
 the LLVM backend and thus avoid the extra C calls.

 Currently, the goal is only to support word-sized (4 or 8 byte)
 compare-and-swap and fetch-and-add operations.  In the future, this
 goal could be expanded to support 16-byte CAS, implemented by CMPXCHG16B
 on
 x86.

 Even supporting word sized CAS requires three different primops for
 operating on `MutVar`, `MutableArray`, and `MutableByteArray`,
 respectively.  Here are signatures for those primOps:

 {{{
 #!C
 gcptr stg_casMutVarzh ( gcptr mv, gcptr old, gcptr new )
  /* MutVar# s a -> a -> a -> State# s -> (# State#, Int#, Any a #) */

 gcptr stg_casArrayzh ( gcptr arr, W_ ind, gcptr old, gcptr new );
 /* MutableArray# s a -> Int# -> a -> a -> State# s -> (# State# s, Int#,
 Any a #) */

 W_ stg_casIntArrayzh( gcptr arr, W_ ind, W_ old, W_ new );
 /* MutableByteArray# s -> Int# -> Int# -> Int# -> State# s -> (# State# s,
 Int# #) */
 }}}

 Fetch-and-add, on the other hand, only makes sense on a
 `MutableByteArray`:

 {{{
 #!C
 W_ stg_fetchAddIntArrayzh( gcptr arr, W_ ind, W_ incr );
 /* MutableByteArray# s -> Int# -> Int# -> State# s -> (# State# s, Int# #)
 */
 }}}

 Some systems, such as gcc and LLVM, provide other variants, such as
 "fetch-and-multiply".  However, these do not have direct support on
 x86 and are usually just simulated with CAS.  For example, see the
 [http://llvm.org/docs/Atomics.html#atomics-and-codegen LLVM documentation
 here].
 User-exposed Haskell libraries for atomic operations may employ the
 same approach using the CAS primOps above to simulate other
 fetch-and-X operations.

 Finally, a design question which bears thinking about is how to
 implement opaque "ticket" approach to CAS.  The basic idea is that a
 user does NOT present a regular pointer-based data value (e.g. `Int`)
 to CAS as the "old" value.  Rather, observations of prior values are
 kept in an opaque form (`Any` type) to prevent the compiler changing
 the pointer identity by, for example, unboxing and reboxing the value.

 The way this affects the **primOp** design is as follows.  The current
 implementation of casMutVar# and casArray# returns the NEW value
 rather than the old one if the CAS is successful.  The Haskell code
 that imports the primOps treats this new value as the opaque ticket.

 The user can in fact safely retrieve the real value from the `Any`-based
 "ticket" with a `peekTicket :: Ticket a -> a` operation.  But
 [http://hackage.haskell.org/packages/archive/atomic-primops/0.4/doc/html
 /Data-Atomics.html#g:1 peekTicket] MUST [https://github.com/rrnewton
 /haskell-lockfree-
 queue/blob/880fb11de354d84f6c9a8ee06d5d4a887bd449a4/AtomicPrimops/Data/Atomics.hs#L114
 be marked NOINLINE] to hide the `unsafeCoerce`
 operation inside it from compiler optimizations.  Otherwise, the
 code path that carries the ticket from one CAS operation to the
 next is subject to optimization [1].  In particular, `unsafeCoerce` simply
 becomes a type-level operation, not a function call with the usual
 constraints on control and dataflow.

 Returning to the issue of primOp design, if we wished to avoid the
 somewhat non-standard design of returning the new value from CAS, we
 //could// allow users to create `Ticket` values themselves, rather
 retrieving them as the result of previous read and CAS IO operations.
 Yet this would entail an additional `NOINLINE` (unsafeCoerce) function
 call, and I believe it would be prone to error.

 Further, if you look at
 [https://github.com/ghc/ghc/blob/25ad01533aaaf1ccf69e1b7216e66de025b8131b/rts/PrimOps.cmm#L319
 the primOp implementation for stg_casMutVarzh],
 you will see that there is //already// a branch, which is necessary for
 updating GC-related meta-data.  Thus there is no additional overhead
 to return the new rather than the old value from CAS operations in the
 successful case. Haskell-level CAS is already a compound operation,
 not merely a single machine code instruction.

 By contrast, the C intrinsic `__sync_val_compare_and_swap` can
 become only a single machine operation, and it returns the "old"
 value irrespective of whether the CAS succeeded or failed.  In fact,
 an equality comparison on that old value is necessary to determine if
 the operation succeeded.  In contrast, the Haskell CAS primOps above
 return an unboxed tuple with an explicit success bit.  Thus returning
 the old value in the success case is completely redundant, and
 returning the new value instead allows us to acheive two goals
 (the CAS and the opacifying coercion) with one
 operation at no additional cost.

 [1] P.S. As a concrete example of what happens when `unsafeCoerce` is not
 hidden, consider the following code as a starting point:

 {{{
 x = unsafeCoerce y
 z = f y
 }}}

 `x` would seem to have nothing to do with `f`, and yet
 later in the compiler, one can end up with Core like this:
 {{{
 z = f x
 }}}

 This exposes the type information and activates optimizations, which
 was the source of [https://github.com/rrnewton/haskell-lockfree-
 queue/issues/5 one bug] with the
 `lockfree-queue` package that was fixed by adding NOINLINE to
 `peekTicket`.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8157>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler