GitLab

This task is a precursor to ticket #7883 (closed). The goal is to standardize a broader set of atomic ops -- mainly CAS and fetch-and-add -- and then in #7883 (closed) 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:

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:

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 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 peekTicket MUST 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 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 one bug with the lockfree-queue package that was fixed by adding NOINLINE to peekTicket.

Trac metadata

Trac field	Value
Version	7.6.3
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture