Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell: How does 'atomicModifyIORef' work?

Can someone explain how atomicModifyIORef works? In particular:

(1) Does it wait for a lock, or optimistically try and retry if there's contention (like TVar).
(2) Why is the signature of atomicModifyIORef different to the signature of modifyIORef? In particular, what is this extra variable b?

Edit: I think I've figured out the answer to (2), in that b is a value to be extracted (this can be empty if not needed). In a single threaded program, knowing the value is trivial, but in a multithreaded program, one may want to know what the previous value was at the time of the function being applied. I assume this is why modifyIORef doesn't have this extra return value (as such usages of modifyIORef with this return value probably should use atomicModifyIORef anyway. I'm still interested in the answer to (1) though.

like image 229
Clinton Avatar asked Apr 11 '12 09:04

Clinton


2 Answers

Does it wait for a lock, or optimistically try and retry if there's contention (like TVar).

atomicModifyIORef uses an locking instruction on the underlying hardware architecture you're on, to swap the pointer to an allocated Haskell object in an atomic fashion.

On x86 it uses the cas intruction, exposed as a primitive to the language via atomicModifyMutVar#, which is implemented as a runtime service in Cmm as:

stg_atomicModifyMutVarzh
{
...

 retry:
   x = StgMutVar_var(mv);
   StgThunk_payload(z,1) = x;
#ifdef THREADED_RTS
   (h) = foreign "C" cas(mv + SIZEOF_StgHeader + OFFSET_StgMutVar_var, x, y) [];
   if (h != x) { goto retry; }
#else
   StgMutVar_var(mv) = y;
#endif
...
}

That is, it will try to do the swap, and retry otherwise.

The implementation of cas as a primitive shows how we get down to the metal:

/*
 * Compare-and-swap.  Atomically does this:
 */
EXTERN_INLINE StgWord cas(StgVolatilePtr p, StgWord o, StgWord n);

/*
 * CMPXCHG - the single-word atomic compare-and-exchange instruction.  Used
 * in the STM implementation.
 */
EXTERN_INLINE StgWord
cas(StgVolatilePtr p, StgWord o, StgWord n)
{
#if i386_HOST_ARCH || x86_64_HOST_ARCH
    __asm__ __volatile__ (
      "lock\ncmpxchg %3,%1"
          :"=a"(o), "=m" (*(volatile unsigned int *)p)
          :"0" (o), "r" (n));
    return o;
#elif arm_HOST_ARCH && defined(arm_HOST_ARCH_PRE_ARMv6)
    StgWord r;
    arm_atomic_spin_lock();
    r  = *p;
    if (r == o) { *p = n; }
    arm_atomic_spin_unlock();
    return r;
#elif !defined(WITHSMP)
    StgWord result;
    result = *p;
    if (result == o) {
        *p = n;
    }
    return result;

So you can see that it is able to use an atomic instruction in Intel, on other architectures different mechanisms will be used. The runtime will retry.

like image 140
Don Stewart Avatar answered Sep 28 '22 22:09

Don Stewart


atomicModifyIORef takes a r :: IORef a and a function f :: a -> (a, b) and does the following:

It reads the value of r and applies f to this value, yielding (a',b). Then the r is updated with the new value a' while b is the return value. This read and write access is done atomically.

Of course this atomicity only works if all accesses to r are done via atomicModifyIORef. Note that you can find this information by looking at the source [1].

[1] https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-IORef.html#v:atomicModifyIORef

like image 25
Peter Avatar answered Sep 28 '22 22:09

Peter